Sparse Graph-based Transduction for Image Classification

Sheng Huang, Dan Yang, Jia Zhou, Luwen Huangfu, Xiaohong Zhang

Abstract

Motivated by the remarkable successes of Graph-based Transduction (GT) and Sparse Representation (SR), we present a novel classifier named Sparse Graph-based Classifier (SGC) for image classification. In SGC, SR is leveraged to measure the correlation (similarity) between samples, and a graph is constructed to encode these correlations. Laplacian eigenmapping is then adopted to derive the graph Laplacian. Finally, SGC is obtained by integrating the graph Laplacian into the conventional GT framework. SGC inherits the merits of both GT and SR, improving robustness and discriminating power while alleviating the undercomplete dictionary issue suffered by SR. Evaluation on four popular image databases demonstrates that SGC achieves promising performance, particularly in small training sample and noisy sample cases.

Introduction

In image classification, researchers often face two conflicting challenges: the "Small Data" problem and the "Undercomplete Dictionary" problem. Traditional supervised learners require significant labeled data. While transductive learning (GT) helps by analyzing relationships between labeled and unlabeled data, it typically relies on k-nearest-neighbor (k-NN) graphs that are easily confused by noise. Conversely, Sparse Representation (SR) is robust to noise but requires a massive "dictionary" of training samples to function effectively. SGC addresses these issues by using SR to build a superior, adaptive graph for GT.

Methodology

The core innovation of SGC is the synthesis of SR and GT through a three-step process:

  1. Sparse Graph Construction: Instead of using simple Euclidean distance, SGC employs $\ell_1$-norm minimization. For every image in the dataset (labeled and unlabeled), the algorithm finds a sparse combination of all other images that best reconstructs it. This creates an affinity matrix where edges represent meaningful, learned correlations.
  2. Laplacian Derivation: From this sparse affinity matrix, a graph Laplacian is derived to capture the underlying manifold structure of the data.
  3. Transductive Inference: This Laplacian is plugged into a standard GT framework, solving a Regularized Least Squares (RLS) problem to propagate labels from training sets to unlabeled testing samples.
Neighbor selection comparison: The sparse graph (bottom) identifies more relevant, consistent neighbors than traditional methods (top).

By including testing samples in the graph-building phase, the "dictionary" for sparse representation is effectively expanded, solving the undercomplete dictionary problem inherent in pure SR methods.

Key Insights and Ideas

  • Adaptive Neighborhoods: Unlike k-NN graphs that force a fixed number of neighbors, the sparse graph is adaptive. It connects samples based on discriminative relevance, making the graph significantly more accurate for classification.
  • Testing Data as a Resource: Testing data is treated as a structural resource. By using these samples to help build the sparse graph, the algorithm learns the "shape" of the data space more accurately.
  • Noise as a Filter: Because SR naturally ignores non-sparse noise (like random pixels), the resulting graph is much cleaner than a traditional k-NN graph, which would likely create false connections between noisy images.

Experimental Results

SGC was evaluated on the Yale, AR, and FERET face databases, as well as the Caltech256 object category dataset. The results consistently showed SGC outperforming state-of-the-art classifiers like SRC (Sparse Representation-based Classifier) and standard GT methods.

  • Accuracy: On the Yale database, SGC achieved a classification error of just 2.78%, compared to 3.33% for SRC and 8.89% for standard GT.
  • Small Sample Performance: The advantage of SGC was most pronounced when training data was limited, maintaining lower error rates than competitors even with only 10% training data.
  • Robustness: In experiments with 30% "salt-and-pepper" noise, SGC’s performance degraded gracefully, maintaining high accuracy while standard GT methods failed completely.
Samples with noise and their corresponding rank scores, demonstrating SGC's robustness.

Conclusion

SGC represents a robust marriage between Sparse Representation and Graph-based Transduction. By leveraging the strengths of both, it provides a highly effective solution for image classification in challenging environments. Future work may involve exploring more advanced regression techniques or custom loss functions to further improve the framework's scalability and precision.

Summary updated

Abstract

Motivated by the remarkable successes of Graph-based Transduction (GT) and Sparse Representation (SR), we present a novel Classifier named Sparse Graph-based Classifier (SGC) for image classification. In SGC, SR is leveraged to measure the correlation (similarity) of each two samples and a graph is constructed for encoding these correlations. Then the Laplacian eigenmapping is adopted for deriving the graph Laplacian of the graph. Finally, SGC can be obtained by plugging the graph Laplacian into the conventional GT framework. In the image classification procedure, SGC utilizes the correlations, which are encoded in the learned graph Laplacian, to infer the labels of unlabeled images. SGC inherits the merits of both GT and SR. Compared to SR, SGC improves the robustness and the discriminating power of GT. Compared to GT, SGC sufficiently exploits the whole data. Therefore it alleviates the undercomplete dictionary issue suffered by SR. Four popular image databases are employed for evaluation. The results demonstrate that SGC can achieve a promising performance in comparison with the state-of-the-art classifiers, particularly in the small training sample size case and the noisy sample case.
BibTeX
@article{huang2015sparse,
  author = {Sheng Huang and Dan Yang and Jia Zhou and Luwen Huangfu and Xiaohong Zhang},
  title = {{Sparse Graph-based Transduction for Image Classification}},
  journal = {J. Electronic Imaging},
  year = {2015},
  doi = {10.1117/1.jei.24.2.023007},
}
Figure