On the Subspace of Image Gradient Orientations

Georgios Tzimiropoulos, Stefanos ZafeiriouarXiv 2010 · arXiv

Abstract

Standard Principal Component Analysis (PCA) is notoriously sensitive to outliers like shadows and occlusions because it relies on the $\ell_2$ norm. This paper introduces a robust alternative by performing PCA on image gradient orientations rather than pixel intensities. By mapping these orientations to a complex sphere and using a cosine-based distance measure, the authors create a scheme that is as computationally efficient as standard PCA but significantly more resilient to non-Gaussian noise and "gross errors."

Introduction

PCA is a cornerstone of computer vision, used for everything from dimensionality reduction to feature extraction (e.g., "Eigenfaces"). However, standard PCA has a major weakness: it assumes noise is Gaussian. In the real world, image data is messy, containing "gross errors" caused by occlusions, sharp shadows, or specular reflections.

Because standard PCA minimizes the sum of squared distances (the $\ell_2$ norm), a single large outlier can "pull" the estimated subspace away from the true data distribution. While robust versions of PCA exist (like those using the $\ell_1$ norm), they are often computationally expensive and slow when dealing with high-dimensional image data. The authors sought a method that provides robustness without sacrificing the speed of the classic algorithm.

Methodology

The proposed approach shifts both the data representation and the distance metric:

  1. Gradient Orientations: Instead of using raw pixel intensities, the method calculates the gradient orientation ($\phi$) at each pixel.
  2. Complex Mapping: To make the math work with standard PCA tools, each orientation $\phi$ is mapped to a point on a complex unit sphere using the transformation $z = e^{j\phi}$.
  3. Linear Complex PCA: Standard linear PCA is performed on this complex data. By utilizing the "Eigenfaces" trick (performing eigen-decomposition on the $n \times n$ covariance matrix instead of the $p \times p$ one), the algorithm remains efficient even when the number of pixels ($p$) is much larger than the number of samples ($n$).

The "Random Generator" Property

A core insight of this approach is that the difference between gradient orientations of two unrelated images acts like a high-quality random number generator.

Figure 2: Gradient orientation differences between dissimilar natural image patches (a, b) follow a uniform distribution (c, d).

As shown in Figure 2, when two image patches are dissimilar, the differences in their gradient orientations tend to be uniformly distributed $U[0, 2\pi)$. When you sum the cosines of these random differences in the covariance calculation, they effectively cancel each other out. This means outliers contribute near-zero weight to the final subspace estimation, providing inherent robustness without a complex rejection step.

Experimental Results

The method was evaluated using the Yale B Face Database, consisting of aligned face images under varying lighting conditions. Artificial occlusions were added by placing "Baboon" image patches at random locations to test robustness.

Figure 6: (a) Original face, (b) face with occlusion, (c) histogram of orientation differences between (a) and (b) showing a uniform distribution.

In experiments with occluded faces (Figure 6), standard $\ell_2$ PCA produced reconstructions with "ghosts" of the occluding patches. In contrast, Gradient Orientation PCA successfully ignored the occlusions, reconstructing only the face component. The method proved capable of completely separating the face subspace from the outlier subspace while maintaining the $O(n^3)$ complexity of standard PCA.

Conclusion

While the method is robust to illumination and occlusions, it relies on the ability to calculate reliable gradients. Performance might degrade in extremely low-contrast areas or images with heavy Gaussian noise. Additionally, focusing solely on orientations discards intensity information, which might contain discriminative detail. Future work could extend this framework to other statistical machine learning tasks like clustering, object recognition, and tracking.

Summary updated

Abstract

We introduce the notion of Principal Component Analysis (PCA) of image gradient orientations. As image data is typically noisy, but noise is substantially different from Gaussian, traditional PCA of pixel intensities very often fails to estimate reliably the low-dimensional subspace of a given data population. We show that replacing intensities with gradient orientations and the $\ell_2$ norm with a cosine-based distance measure offers, to some extend, a remedy to this problem. Our scheme requires the eigen-decomposition of a covariance matrix and is as computationally efficient as standard $\ell_2$ PCA. We demonstrate some of its favorable properties on robust subspace estimation.
BibTeX
@misc{tzimiropoulos2010subspace,
  author = {Georgios Tzimiropoulos and Stefanos Zafeiriou},
  title = {{On the Subspace of Image Gradient Orientations}},
  year = {2010},
  eprint = {1005.2715},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1005.2715},
}
Figure