Supervised Texture Classification Using a Novel Compression-Based Similarity Measure

Mehrdad J. Gangeh, Ali Ghodsi, Mohamed S. Kamel

TL;DR

This paper introduces a novel method for classifying textures in images by measuring their similarity in a "dissimilarity space" using MPEG-1 compression. This approach leverages the spatial information within images more effectively than previous methods, leading to significantly improved classification accuracy and a notable speedup.

What Problem Does This Paper Address?

Texture classification, especially for images containing multiple textures (nonstationary textures), is a challenging problem. Traditional methods often rely on extracting features from image patches and then classifying these features. However, defining a universal set of features that works well across all texture types is difficult. An alternative is to represent textures in a "dissimilarity space," where pairs of texture patches are compared using a similarity measure. Existing compression-based similarity measures, like Normalized Compression Distance (NCD), have shown promise but struggle with 2D image data because simply linearizing images to treat them as strings can lose crucial spatial information. While some methods use 2D compressors like JPEG, their effectiveness for similarity measures is debated. This paper aims to bridge this gap by proposing a new compression-based similarity measure that effectively captures spatial locality in 2D images.

Methods

The core of this paper is a novel compression-based dissimilarity measure, denoted as $d_N(x,y)$. This measure is designed to work in the "dissimilarity space" and utilizes the MPEG-1 video compression encoder. Unlike previous approaches that might linearize images or use both I-frames and P-frames in MPEG compression, this method specifically focuses on P-frame coding.

Here's a breakdown of the key methodological aspects:

  • MPEG-1 P-frame Coding: MPEG-1 is chosen because it's designed for video, meaning it can compress frames with reference to previous ones. This inherently captures spatial and temporal (or in this case, inter-patch) relationships. The paper specifically uses P-frame coding because it's designed to encode the differences between frames, which is crucial for measuring similarity or dissimilarity.
  • Focus on P-frame: The authors argue that I-frame coding (which is based on DCT and doesn't consider relationships between frames) doesn't contribute to measuring similarity between two distinct patches. Therefore, they bypass I-frame coding.
  • Maximum Resolution for P-frame: To ensure the P-frame coding accurately reflects the differences and thus the dissimilarity, it's performed at maximum resolution (minimum quantization scale).
  • Novel Formulation: The proposed dissimilarity measure is defined as: $$d_N(x,y) = \frac{|C_p(x|y) – C_p(y|x)|}{C(x|x) + C(y|y)}$$ Here, $C_p(x|y)$ represents the compression achieved by encoding patch $x$ with reference to patch $y$ using P-frame coding. The numerator captures the difference in compression when $x$ is encoded with $y$ versus $y$ encoded with $x$. The denominator, $C(x|x) + C(y|y)$, acts as a normalizing factor. Since $x$ and $x$ (or $y$ and $y$) are identical, P-frame coding results in zero difference, making $C(x|x)$ equivalent to the compression of $x$ itself. This formulation is designed to be symmetric and non-negative.

  • Comparison to $d_{ck}$: The paper also contrasts its method with a prior compression-based measure, $d_{ck}$, which uses both I- and P-frames and is shown to perform poorly on smaller patches due to the dominance of I-frame coding.

Datasets

The paper uses the following datasets for evaluation:

  • Brodatz Album: This is a standard dataset for texture analysis. The authors specifically mention using textures D4 and D5 from this album.
  • Outdoor Images: The paper also includes experiments on a set of outdoor images that contain texture composites. These are the same images used in a previous benchmark study [2].

The paper does not introduce new datasets but uses existing ones to demonstrate the effectiveness of its proposed method against prior work.

Key Insights and Ideas

  • Dissimilarity Space is Powerful for Textures: The paper reinforces the idea that representing textures in a dissimilarity space, rather than a feature space, can be more robust, especially for complex texture phenomena.
  • MPEG P-frame Coding Captures Spatial Locality: The key insight is that MPEG-1's P-frame coding, by design, inherently considers the spatial relationships between image patches. This is crucial for texture analysis, where local patterns and their arrangement are paramount.
  • Bypassing I-frame Coding is Key for Similarity: By focusing solely on P-frame coding, the authors effectively isolate the measure of difference between patches, avoiding the influence of raw frequency content (which I-frames capture) that can mask true textural similarity.
  • Small Patch Performance Matters: The proposed method's ability to perform well on both small and large patch sizes is a significant advantage. Previous compression-based methods like $d_{ck}$ struggled with small patches because the I-frame component dominated, obscuring the P-frame's similarity information.
  • Speed Improvement: The focus on P-frame coding and the efficient nature of MPEG compression lead to a substantial speedup (around 40%) compared to the $d_{ck}$ method.

Key Results

  • Improved Classification Accuracy: The proposed method ($d_N$) consistently achieved higher classification rates on both Brodatz and outdoor texture images compared to the $d_{ck}$ and NCD methods.
  • Superior to Feature-Based Methods: In some cases, the proposed method also outperformed established feature-based approaches like Local Binary Patterns (LBP) and MeasTex (Gabor, 5NN), which were reported in prior work [2]. For example, on one test image (Fig. 2a), the proposed method achieved 89.5% accuracy, while LBP achieved 85.4% and MeasTex achieved 83.7%.
  • Effective on Various Patch Sizes: Illustrative results show that the proposed measure consistently produces smaller distances between patches of the same texture class and larger distances between different classes, across various patch sizes (17x17 to 129x129). This contrasts with $d_{ck}$, which showed inconsistent results for smaller patch sizes.
  • 40% Speedup: The paper reports a significant improvement in computation speed, approximately 40% faster than the $d_{ck}$ method.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that while the proposed measure works well, the trade-off between patch size for smooth areas versus borders in nonstationary texture classification still exists. Larger patches are better for uniform regions, while smaller ones are needed for boundaries to avoid mixing textures.
  • The $d_{ck}$ method's limitation with small patches is highlighted as a drawback of that specific approach, which the proposed method overcomes.
  • Future Work:
    • The paper doesn't explicitly detail future work, but the success of this MPEG-based approach suggests potential for exploring other video compression standards or more advanced MPEG features.
  • Further investigation into optimizing the patch size selection for nonstationary textures could be a natural next step.
  • Extending this approach to other image analysis tasks beyond classification, such as segmentation or retrieval, could also be a promising direction.

Summary updated

Abstract

Supervised pixel-based texture classification is usually performed in the\nfeature space. We propose to perform this task in (dis)similarity space by\nintroducing a new compression-based (dis)similarity measure. The proposed\nmeasure utilizes two dimensional MPEG-1 encoder, which takes into consideration\nthe spatial locality and connectivity of pixels in the images. The proposed\nformulation has been carefully designed based on MPEG encoder functionality. To\nthis end, by design, it solely uses P-frame coding to find the (dis)similarity\namong patches/images. We show that the proposed measure works properly on both\nsmall and large patch sizes. Experimental results show that the proposed\napproach significantly improves the performance of supervised pixel-based\ntexture classification on Brodatz and outdoor images compared to other\ncompression-based dissimilarity measures as well as approaches performed in\nfeature space. It also improves the computation speed by about 40% compared to\nits rivals.\n
BibTeX
@inproceedings{gangeh2012supervised,
  author = {Mehrdad J. Gangeh and Ali Ghodsi and Mohamed S. Kamel},
  title = {{Supervised Texture Classification Using a Novel Compression-Based Similarity Measure}},
  booktitle = {ICCVG},
  year = {2012},
  doi = {10.1007/978-3-642-33564-8\_46},
}

Loading related content...

Figure