Topology-Preserving Dimension-Reduction Methods for Image Pattern Recognition

Hayato Itoh, Tomoya Sakai, Kazuhiko Kawamoto, Atsushi ImiyaLecture Notes in Computer Science 2013 · DOI · OpenAlex

Introduction

In the field of computer vision, images are typically represented as high-dimensional vectors. For instance, a standard $192 \times 168$ pixel image translates into a space of over 32,000 dimensions. Processing such data is computationally intensive, necessitating the use of dimension reduction (DR) techniques. However, reducing dimensionality often leads to information loss. The primary challenge in DR is to preserve the topology of the original space—ensuring that images that are "close" in high-dimensional space remain close in the reduced subspace. This paper evaluates whether it is more effective to reduce dimensions by treating images as 2D matrices (tensorial approach) or by flattening them into 1D vectors first.

Methodology

The authors compare three distinct dimension-reduction strategies:

  1. Random Projection (RP): A vector-based method that utilizes a random matrix to project data. It is grounded in the Johnson-Lindenstrauss lemma, which provides mathematical guarantees for distance preservation.
  2. Two-Dimensional Random Projection (2DRP): A tensorial extension of RP that operates directly on the image matrix using two smaller random matrices.
  3. Two-Dimensional Discrete Cosine Transform (2DDCT): A standard signal processing technique that retains only the low-frequency components of an image, similar to the principles of JPEG compression.
Workflow of image and vector compression methods.

For the classification task, the study employs the Subspace Method (SM) and the Two-Dimensional Tensorial Subspace Method (TDTSM). These methods classify an input by measuring the geometric angle between the input data and a predefined subspace representing a specific class.

Geometric representation of projections used in subspace classification methods.

Experimental Setup

To ensure generalizability, the methods were tested on three diverse benchmark datasets:

  • Extended Yale B: 38 classes of human faces under varying illumination.
  • ETH80: 30 classes of physical objects (e.g., cars, cups) captured from multiple angles.
  • MNIST: 10 classes of handwritten digits.

Key Insights

  • The Advantage of Vectorization: Despite the intuitive appeal of preserving 2D structure, experiments revealed that flattening images into vectors and applying standard RP preserved relative distances more accurately than tensorial methods.
  • Theoretical vs. Practical Performance: While the authors proved that 2DRP satisfies the Johnson-Lindenstrauss property, standard RP consistently showed lower relative error in practice.
  • Energy Concentration: At extremely low dimensions, 2DDCT outperformed 2DRP. This is attributed to the fact that natural images concentrate significant information in low-frequency components, which DCT is optimized to capture.
  • Robustness Across Datasets: Random Projection's performance remained nearly identical across all three datasets, suggesting its effectiveness is a fundamental mathematical property rather than a result of dataset-specific tuning.

Results and Discussion

RP consistently demonstrated the lowest mean relative error in distance preservation across all benchmarks. In terms of recognition rates, RP and 2DDCT performed similarly well, achieving high accuracy (near 90-100% on Yale B and MNIST). Conversely, 2DRP consistently yielded the lowest recognition rates. These results indicate that vector-based classification methods generally provide higher accuracy than their image-based tensorial counterparts for these pattern recognition tasks.

Conclusion

The study concludes that standard vector-based Random Projection is a powerful and often superior tool for topology-preserving dimension reduction in image processing. While tensorial methods offer a different perspective, they do not necessarily outperform traditional vectorization in preserving critical data relationships. Future work may explore non-linear dimension-reduction techniques, such as deep-learning-based autoencoders, to further enhance performance on complex image manifolds.

Summary updated

BibTeX
@inproceedings{itoh2013topology,
  author = {Hayato Itoh and Tomoya Sakai and Kazuhiko Kawamoto and Atsushi Imiya},
  title = {{Topology-Preserving Dimension-Reduction Methods for Image Pattern Recognition}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2013},
  doi = {10.1007/978-3-642-38886-6\_19},
}
Figure