We propose and evaluate a method for learning deep-sea substrate types using video recorded with a remotely operated vehicle (ROV). The goal of this work is to create a labelled spatial map of substrate types from ROV video in order to support biological and geological domain research. The output of our method describes the mixtures of geological features such as sediment and types of lava flow in images taken at a set of points chosen from an ROV dive. The main contribution of this work is the assembly of a pipeline combining several unique approaches which is able to robustly generate substrate type mixtures under the varying lighting and perspective conditions of deep-sea ROV dive videos. The pipeline comprises three main components: sampling, in which a trained classifier and spatial sampling is used to select relevant frames from the dataset; feature extraction, in which the improved local binary pattern descriptor (ILBP) is used to generate a Bag of Words (BoW) representation of the dataset; and topic modelling in which a variant of Latent Dirichlet Allocation (LDA), is used to infer the mixture of substrate types represented by each BoW. Our method significantly outperforms techniques relying on keypoint based features rather than texture based features, and k-means rather than LDA, demonstrating that our proposed pipeline accurately learns and identifies visible substrate types.