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 compression-based similarity measure for texture classification that leverages MPEG-1's P-frame coding to better capture spatial relationships within image patches. This new approach significantly improves classification accuracy and speed compared to existing methods, particularly for non-stationary textures.

What Problem Does This Paper Address?

Texture classification, especially for images containing multiple textures (non-stationary), is a challenging task. 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 approach is to measure the similarity or dissimilarity between texture patches directly, often using compression-based methods. These methods, inspired by Kolmogorov complexity, approximate similarity by measuring how well one data segment can be compressed using another as a reference. However, existing compression-based methods struggle with capturing the spatial locality and connectivity of pixels in 2D images, often losing crucial information when linearizing image data for compression.

Methods

The core contribution of this paper is a new compression-based dissimilarity measure, denoted as $d_N(x,y)$. This measure is designed to overcome the limitations of previous methods by directly utilizing a 2D compressor, specifically the MPEG-1 encoder. Instead of linearizing image patches into strings, the authors treat image patches as successive frames and leverage MPEG-1's P-frame coding. P-frame coding is crucial because it encodes a frame by referencing a previous frame, inherently capturing inter-frame (and thus inter-patch) relationships, motion estimation, and differences.

The proposed measure specifically uses only P-frame coding to compute the dissimilarity. This is because P-frame coding is sensitive to the differences between frames, which directly reflects similarity. The authors bypass I-frame coding (which is independent and doesn't capture inter-frame similarity) and encode the P-frames at maximum resolution (minimum quantization scale) to prioritize capturing differences. The formula for $d_N(x,y)$ is:

$d_N(x,y) = \frac{|C_p(x|y) – C_p(y|x)|}{C(x|x) + C(y|y)}$

where $C_p(x|y)$ represents the compression achieved by encoding patch $x$ with reference to patch $y$ using P-frame coding. The denominator normalizes the distance. This approach ensures that the measure is symmetric and non-negative, and it effectively captures spatial locality and connectivity.

Datasets

The paper evaluates its method on:

  • Brodatz album: Specifically, textures D4 and D5 are used for illustrating the distance measure's effectiveness on different patch sizes.
  • Outdoor images: These are used for the supervised pixel-based texture classification experiments.
  • Combined dataset: The authors mention using a dataset consisting of texture composites from Brodatz and outdoor images, which is the same as used in reference [2].

Key Insights and Ideas

  • P-frame coding is key for 2D similarity: The paper highlights that for 2D data like images, compression techniques that explicitly consider spatial relationships between frames (like MPEG-1's P-frame) are superior to those that linearize data or rely solely on intra-frame information.
  • Bypassing I-frame coding is beneficial: By focusing solely on P-frame coding, the proposed measure avoids the influence of I-frame coding, which is based on frequency content and doesn't directly contribute to measuring similarity between patches. This leads to more accurate dissimilarity estimations.
  • Spatial locality matters: The success of the proposed method underscores the importance of preserving spatial locality and pixel connectivity in texture analysis, a weakness of many previous compression-based approaches.
  • Unified measure for different patch sizes: The proposed measure demonstrates consistent performance across both small and large patch sizes, a significant improvement over methods like $d_{ck}$ which struggle with smaller patches.

Key Results

  • Improved Classification Accuracy: The proposed method achieved significantly higher classification rates on both Brodatz and outdoor images compared to other compression-based dissimilarity measures ($d_{ck}$, NCD) and even outperformed established feature-based methods like LBP and MeasTex (Gabor, 5NN) reported in prior work. For instance, on test image Fig. 2a, the proposed method achieved 89.5% accuracy, compared to 82.1% for $d_{ck}$ and 83.3% for NCD.
  • Speed Improvement: The method offers a speed improvement of approximately 40% compared to the $d_{ck}$ method.
  • Qualitative Results: Visual results in Figure 2 show that the proposed method produces cleaner and more accurate segmentation maps for texture classification compared to the other methods.

Limitations and Future Work

  • Limitations: The paper acknowledges that the $d_{ck}$ method struggles with small patches because P-frame compression is limited for small regions, and I-frame coding dominates. While their method addresses this, it's implied that further optimization for extremely small patches might still be an area for exploration.
  • Future Work: Not explicitly detailed, but the success of using MPEG-1's P-frame coding suggests potential for exploring other advanced video compression techniques or adapting the method to different compression standards for even better performance or broader applicability. The paper also mentions that their method is symmetric and non-negative, which are desirable properties for a distance measure, implying these are well-established outcomes.

Summary updated

Abstract

Supervised pixel-based texture classification is usually performed in the feature space. We propose to perform this task in (dis)simil-arity space by introducing a new compression-based (dis)similarity measure. The proposed measure utilizes two dimensional MPEG-1 encoder, which takes into consideration the spatial locality and connectivity of pixels in the images. The proposed formulation has been carefully designed based on MPEG encoder functionality. To this end, by design, it solely uses P-frame coding to find the (dis)similarity among patches/images. We show that the proposed measure works properly on both small and large patch sizes. Experimental results show that the proposed approach significantly improves the performance of supervised pixel-based texture classification on Brodatz and outdoor images compared to other compression-based dissimilarity measures as well as approaches performed in feature space. It also improves the computation speed by about 40% compared to its rivals.
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},
}
Figure