Back

Using Discriminant Eigenfeatures for Image Retrieval

Daniel L. SwetsJohn (Juyang) Weng

article1996TPAMI1,823 citations

Proposes a Discriminant Karhunen-Loève projection framework that combines principal component analysis with linear discriminant analysis to eliminate non-informative variations like lighting and substantially improve content-based image retrieval across diverse object classes.

Listen

Rapidly finding and retrieving visual information from large multimedia databases has become essential as digital collections expand beyond alphanumeric records. Traditional image retrieval systems have relied on hand-crafted shape rules, which are difficult to generalize across varied object types, or standard feature extraction methods like Principal Component Analysis, which often capture lighting changes and visual noise rather than meaningful identity cues. The article sets out to evaluate a two-stage projection method—the Discriminant Karhunen-Loève projection—that automatically identifies "Most Discriminating Features" to accurately classify and retrieve images across diverse categories.

The authors tested this methodology by first applying Principal Component Analysis to reduce high-dimensional raw pixel data into a manageable intermediate feature space, followed by multivariate linear discriminant analysis to maximize separation between classes while minimizing within-class variation. They evaluated this framework on human facial datasets under varying expressions and lighting, as well as a combined real-world database containing various natural objects such as vehicles, street signs, human bodies, and office items, using nearest-neighbor matching on disjoint test sets.

The evaluation revealed several key findings regarding retrieval performance and efficiency. First, the proposed discriminating feature framework achieved superior classification accuracy compared to traditional principal component projections; on face datasets, it reached peak accuracy using only 15 features, whereas principal component methods required 37 features and plateaued at an 89% recognition rate. Second, the method effectively discounted non-essential variations such as illumination direction and minor facial expression shifts when those variations appeared in the training set. Third, exhaustive sequential searches across the database proved computationally slow at roughly 400.7 seconds per query on standard hardware, but organizing the feature space into a hierarchical Voronoi tessellation reduced retrieval time to 9.1 seconds while boosting top-match accuracy to 95% and top-10 accuracy to 99%.

These findings indicate that automatically learned discriminant subspaces offer a practical and scalable alternative to rigid, hand-crafted recognition rules. For organizations managing multimedia archives, adopting this approach can improve search accuracy and lower manual indexing costs, provided the feature spaces are hierarchically structured to maintain fast retrieval speeds. However, because the system relies on supervised class labels, the resulting feature space reflects only the specific categorization criteria established during training.

Organizations implementing this retrieval framework should ensure that training data adequately captures expected real-world variations, such as diverse lighting and slight angular shifts, and pair the extraction method with hierarchical indexing architectures for real-time querying. The primary limitations of this work stem from its reliance on "well-framed" images with minimal scale and position variation, as well as degraded performance when encountering unseen 3D rotations or drastic shape alterations. Further research is recommended to explore automatic object framing and the integration of edge maps alongside intensity images to improve robustness against unconstrained viewing conditions.

Augustana CollegeMichigan State Universityfisher discriminant analysisgenetic selectionimage retrievaldiscriminant eigenfeaturesimage retrievallinear discriminant analysis
Swets et al (1996).pdf
  • Paper: Face Recognition: Features Versus Templates, R. Brunelli et al. (1993). This seminal paper provides essential foundational context on evaluating eigenface representations from principal component analysis, the exact baseline method the source paper seeks to improve upon using discriminant analysis.
  • Paper: Color indexing, Michael J. Swain et al. (1991). Reading this provides the prerequisite foundations for appearance-based image retrieval and indexing against which linear projection techniques are developed and evaluated.
  • Paper: Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection, Peter N. Belhumeur et al. (1996). This landmark paper extends the concept of class-specific linear discriminant projections (Fisherfaces) to overcome illumination and expression variations in appearance-based recognition, contrasting directly with PCA.
  • Paper: Two-dimensional PCA: a new approach to appearance-based face representation and recognition, Jian Yang et al. (2004). This work generalizes appearance-based subspace projection by operating directly on 2D image matrices to eliminate the high-dimensional vectorization bottlenecks present in standard eigenfeature methods.
  • Paper: Locality Preserving Projections, Xiaofei He et al. (2003). This paper advances linear projection techniques by introducing Locality Preserving Projections to preserve neighborhood manifold geometry rather than relying solely on global variance or standard linear discrimination.
  • Paper: Face recognition using Laplacianfaces, Xiaofei He et al. (2005). This study builds directly upon linear subspace representations like Eigenfaces and Fisherfaces by incorporating manifold learning to create Laplacianfaces for improved appearance-based recognition.
  • Paper: Graph Embedding and Extensions: A General Framework for Dimensionality Reduction, Shuicheng Yan et al. (2007). This work formulates a unified graph embedding framework that generalizes classical linear dimensionality reduction techniques such as PCA and Linear Discriminant Analysis into a common formulation.
  • Paper: Neighbourhood Components Analysis, Jacob Goldberger et al. (2004). This work extends linear feature projection by learning non-parametric metric transformations tailored for nearest-neighbor classification without assuming Gaussian class distributions.
  • Paper: Robust Face Recognition via Sparse Representation, John Wright et al. (2009). This paper revisits subspace-based face recognition by demonstrating how sparse representation and convex optimization can overcome the fundamental limitations of standard linear projection methods under severe occlusions.
  • Paper: Statistical Pattern Recognition: A Review, Anil K. Jain et al. (2000). This comprehensive review provides a broader contextual evaluation of statistical pattern recognition, synthesizing linear feature selection and extraction methods within the larger classification literature.
Cover for Using Discriminant Eigenfeatures for Image Retrieval

Abstract

This paper describes the automatic selection of features from an image training set using the theories of multidimensional discriminant analysis and the associated optimal linear projection. We demonstrate the effectiveness of these Most Discriminating Features for view-based class retrieval from a large database of widely varying real-world objects presented as “well-framed” views, and compare it with that of the principal component analysis.

Topics

fisher discriminant analysisgenetic selectionimage retrievalprincipal component analysis (pca)training samplelinear discriminant analysislinear discriminantsviewpoint

Keywords

discriminant eigenfeaturesimage retrievallinear discriminant analysisprincipal component analysisdiscriminant projectionface recognitionobject recognitionfeature selectionnearest neighbor

Table of Contents

  • 1 INTRODUCTION
  • 2 OPTIMAL SUBSPACE GENERATION
  • 2.1 The Most Expressive Features (MEF)
  • 2.1.1 Principal Component Analysis
  • 2.1.2 Computational Considerations
  • 2.2 The Most Discriminating Features (MDF)
  • 2.2.1 Multivariate Linear Discriminant Analysis
  • 2.2.2 Computational Considerations
  • 2.2.3 The DKL Projection
  • 2.2.4 Explanation of the MDFs
  • 2.2.5 The Clustering Effect of the MDF Subspace Using the DKL Projection
  • 2.3 Image Matching
  • 3 RESULTS
  • 3.1 A Comparison Between the MEF and the MDF Feature Spaces
  • 3.2 Combination Database: Faces and Other Objects
  • 3.3 The Power for Handling Within-Class Variation Using the MDF Subspace
  • 4 CONCLUSIONS AND FUTURE WORK
  • ACKNOWLEDGMENTS
  • REFERENCES

Knowls

  1. Knowl 1 — Discriminant Karhunen-Loève (DKL) Projection Framework

    model/method

    The Discriminant Karhunen-Loève (DKL) projection is a two-stage linear dimensionality reduction method designed for image retrieval and classification. Applying linear discriminant analysis (LDA) directly to raw image data causes the within-class scatter matrix to become singular (degenerate) because the image pixel dimension nn typically far exceeds the number of training samples ss.

    To overcome this degeneracy, the DKL projection decomposes the transformation into two sequential projections:

    1. Karhunen-Loève Projection (MEF space): The nn-dimensional input image vector XX is first projected onto an mm-dimensional Most Expressive Feature (MEF) space using projection matrix VV, where m<nm < n.
    2. Multivariate Linear Discriminant Projection (MDF space): The resulting mm-dimensional MEF vector is then projected onto a kk-dimensional Most Discriminating Feature (MDF) space using projection matrix WW, where k<mk < m.

    The overall DKL projection from the original image space to the MDF space is given by:

    Z=WTVTXZ = W^T V^T X

    where VV is the n×mn \times m matrix whose columns are the dominant eigenvectors of the training sample scatter matrix, and WW is the m×km \times k matrix whose columns maximize Fisher's criterion in the MEF space:

    max⁡Wdet⁡(WTSbW)det⁡(WTSwW)\max_W \frac{\det(W^T S_b W)}{\det(W^T S_w W)}

    Here, SbS_b and SwS_w are the between-class and within-class scatter matrices computed on the MEF-transformed vectors Y=VTXY = V^T X.

  2. Knowl 2 — Subspace Dimensionality Constraints for the DKL Projection

    theoretical result

    For a training dataset containing ss total image samples distributed across cc distinct classes, the dimensions of the Most Expressive Feature (MEF) subspace mm and the Most Discriminating Feature (MDF) subspace kk are strictly bounded by:

    k+1≤c<m≤s−ck + 1 \le c < m \le s - c

    with the MDF dimension restricted by k≤c−1k \le c - 1.

    These inequalities arise from the rank properties of the scatter matrices:

    • The MEF dimension mm cannot exceed s−cs - c so that the within-class scatter matrix SwS_w in the MEF space remains full rank and strictly invertible (nondegenerate).
    • The MEF dimension mm must be strictly greater than the number of classes cc to preserve sufficient degrees of freedom for class discrimination.
    • The between-class scatter matrix SbS_b has at most rank c−1c - 1, limiting the number of non-zero generalized eigenvalues of Sw−1SbS_w^{-1} S_b to at most c−1c - 1.

  3. Knowl 3 — Numerically Stable Simultaneous Diagonalization for Fisher's Discriminant

    algorithm

    In linear discriminant analysis, finding the optimal projection matrix requires computing the eigenvectors of Sw−1SbS_w^{-1} S_b. Because Sw−1SbS_w^{-1} S_b is generally non-symmetric, direct eigendecomposition is numerically unstable. The eigensystem is stably computed by simultaneously diagonalizing both symmetric scatter matrices SwS_w and SbS_b.

    Input: Within-class scatter matrix Sw∈Rm×mS_w \in \mathbb{R}^{m \times m}, Between-class scatter matrix Sb∈Rm×mS_b \in \mathbb{R}^{m \times m}
    Output: Projection matrix V∈Rm×kV \in \mathbb{R}^{m \times k} and eigenvalue matrix Σ∈Rk×k\Sigma \in \mathbb{R}^{k \times k}
    Compute orthogonal matrix HH and diagonal matrix Λ\Lambda such that Sw=HΛHTS_w = H \Lambda H^T
    Form the whitening transform matrix P=HΛ−1/2P = H \Lambda^{-1/2}
    Transform between-class scatter: Sb′=PTSbP=(HΛ−1/2)TSb(HΛ−1/2)S_b' = P^T S_b P = (H \Lambda^{-1/2})^T S_b (H \Lambda^{-1/2})
    Compute orthogonal matrix UU and diagonal matrix Σ\Sigma such that Sb′=UΣUTS_b' = U \Sigma U^T
    Compute simultaneous diagonalizer: V=HΛ−1/2UV = H \Lambda^{-1/2} U
    Select the kk columns of VV corresponding to the kk largest diagonal entries of Σ\Sigma
    return V,ΣV, \Sigma

    The resulting matrix VV satisfies Sw−1Sb=VΣV−1S_w^{-1} S_b = V \Sigma V^{-1}, where VV contains the eigenvectors of Sw−1SbS_w^{-1} S_b and Σ\Sigma contains the real eigenvalues.

  4. Knowl 4 — Most Expressive Features (MEF) Computation via Snapshot PCA

    model/method

    The Most Expressive Features (MEFs) represent image vectors X∈RnX \in \mathbb{R}^n by finding the orthonormal basis V=[v1,v2,…,vm]V = [v_1, v_2, \dots, v_m] that minimizes reconstruction mean-square error E[∥X−X(m)∥2]\mathbb{E}[\|X - X(m)\|^2] where X(m)=∑i=1myiviX(m) = \sum_{i=1}^m y_i v_i.

    When the number of training samples kk is smaller than the image dimension nn (k<nk < n), the n×nn \times n scatter matrix S=UUTS = U U^T (with U=[X1−Xˉ,X2−Xˉ,…,Xk−Xˉ]U = [X_1 - \bar{X}, X_2 - \bar{X}, \dots, X_k - \bar{X}]) is computationally intractable to diagonalize directly. The snapshot method solves the smaller k×kk \times k eigensystem:

    UTUwi=λiwiU^T U w_i = \lambda_i w_i

    Premultiplying by UU yields S(Uwi)=λi(Uwi)S (U w_i) = \lambda_i (U w_i), which gives the eigenvectors vi=Uwiv_i = U w_i associated with eigenvalue λi\lambda_i.

    The number of retained MEF features mm is selected by ordering the eigenvalues λ1≥λ2≥⋯≥λn\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_n and finding the smallest mm such that the residual variance is below a predefined energy threshold PP (e.g., P=5%P = 5\%):

    ∑i=m+1nλi∑i=1nλi<P\frac{\sum_{i=m+1}^n \lambda_i}{\sum_{i=1}^n \lambda_i} < P

  5. Knowl 5 — Well-Framed Image Input Assumption

    assumption

    The DKL feature extraction and retrieval framework assumes that all input images (both training exemplars and query probes) are "well-framed". That is, the object of interest is pre-centered, and only small variations in object position, scale, and 2D/3D orientation are present across the dataset.

  6. Knowl 6 — Comparative Recognition Performance of MEF vs. MDF on Facial Variations

    empirical result

    On the Weizmann Institute face dataset—consisting of frontal face images of individuals with two distinct facial expressions each captured under three different illumination directions—the MDF subspace significantly outperforms the MEF (PCA) subspace for image retrieval:

    • The MDF subspace captured 95%95\% of its total feature variance using only 15 features.
    • The MEF subspace required 37 features to account for 95%95\% of its variance.
    • Using 95%95\% of the MEF variance achieved a maximum recognition rate of 89%89\%, and adding further MEF features did not improve recognition accuracy because higher-order principal components continue to encode class-irrelevant variations (such as lighting direction).
    • The MDF subspace achieved higher recognition accuracy than MEF across all tested feature subspace dimensions (from 6 to 18 features).

  7. Knowl 7 — Retrieval Performance on Multi-Class Natural Scene and Object Dataset

    data/table

    The DKL retrieval system was evaluated on a large, heterogeneous dataset of natural scene objects (including human faces, street signs, aerial imagery, and everyday objects) where most classes had only 2 training exemplars.

    Metric / Dataset Property Value
    Total Training Images 1,316
    Total Training Classes 504
    Classes with 2 samples 504
    Classes with 3 samples 89
    Classes with 4 samples 7
    Classes with 13 samples 1
    Disjoint Test Images 298 (from 298 classes)
    Top-Choice Correct Retrieval Rate 90%
    Correct in Top 15 Retrieval Rate 98%

    Under nearest-neighbor Euclidean distance matching in the MDF space, the system achieved a 90%90\% top-1 retrieval accuracy and a 98%98\% top-15 accuracy across 298 disjoint test probes.

  8. Knowl 8 — Sensitivity of MDF Subspace to Unmodeled 3D Rotations

    limitation

    The Most Discriminating Feature subspace relies on the assumption that the training set contains representative samples of the within-class variations encountered at query time. When a query image introduces an out-of-plane three-dimensional (3D) rotation that is absent in the training exemplars for that class, linear discriminant projection fails to align the query with its correct class cluster, resulting in retrieval failure.

  9. Knowl 9 — Acceleration of Query Matching via Hierarchical Voronoi Tessellation

    empirical result

    Performing exhaustive linear search across all database images in the MDF subspace required an average of 400.7 seconds400.7\text{ seconds} per query probe (including projection time) on a Sun SPARC 20.

    When the MDF feature space was organized into a hierarchical Voronoi tessellation:

    • Average query time decreased from 400.7 seconds400.7\text{ seconds} to 9.1 seconds9.1\text{ seconds}.
    • Top-choice retrieval accuracy increased from 90%90\% to 95%95\%.
    • Top-10 retrieval accuracy reached 99%99\%.

Coverage note — None was omitted; all contributed models, dimensionality bounds, stable eigensystem algorithms, experimental comparisons (MEF vs. MDF), large-scale dataset evaluations, and search hierarchy performance results are represented.

References

  1. 1.J.R. Bach, S. Paul, and R. Jain, "A Visual Information Management System for the Interactive Retrieval of Faces," IEEE Trans. Knowledge and Data Eng., vol. 5, no. 4, p. 619-628, Aug. 1993.
  2. 2.D. Beymer and T. Poggio, "Face Recognition from One Example View," Proc. Int'l Conf. Computer Vision, pp. 500-507, 1995.
  3. 3.C. Bregler and S.M. Omohundro, "Nonlinear Manifold Learning for Visual Speech Recognition," Proc. Int'l Conf. Computer Vision, pp. 494-499, 1995.
  4. 4.T.M. Cover and P.E. Hart, "Nearest Neighbor Pattern Classification," IEEE Trans. Information Theory, vol. 13, pp. 21-27, Jan. 1967.
  5. 5.R.A. Fisher, "The Statistical Utilization of Multiple Measurements," Annals of Eugenics, vol. 8, pp. 376-386, 1938.
  6. 6.K. Fukunaga, Introduction to Statistical Pattern Recognition, second edition. New York: Academic Press, 1990.
  7. 7.K. Ikeuche and T. Kanade, "Automatic Generation of Object Recognition Programs," Proc. IEEE, vol. 76, no. 8, pp. 1,016-1,035, 1988.
  8. 8.A.K. Jain and R.C. Dubes, Algorithms for Clustering Data. Englewood Cliffs, N.J.: Prentice Hall, 1988.
  9. 9.R. Jain and A. Hampapur, "Metadata in Video Databases," Sigmod Record: Special Issue on Metadata for Digital Media, vol. 23, p. 27, Dec. 1994.
  10. 10.I.T. Jolliffe, Principal Component Analysis. New York: Springer-Verlag, 1986.
  11. 11.M. Kirby and L. Sirovich, "Application of the Karhunen-Loève Procedure for the Characterization of Human Faces," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 1, pp. 103-108, Jan. 1990.
  12. 12.M.M. Loève, Probability Theory. Princeton, N.J.: Van Nostrand, 1955.
  13. 13.B. Moghaddam and A. Pentland, "Probabilistic Visual Learning for Object Detection," Proc. Int'l Conf. Computer Vision, pp. 786-793, 1995.
  14. 14.H. Murase and S.K. Nayar, "Illumination Planning for Object Recognition in Structured Environments," Proc. IEEE CS Conf. Computer Vision and Pattern Recognition, pp. 31-38, Seattle, June 1994.
  15. 15.E. Oomoto and K. Tanaka, "OVID: Design and Implementation of a Video-Object Database System," IEEE Trans. Knowledge and Data Eng., vol. 5, no. 4, pp. 629-643, Aug. 1993.
  16. 16.A. Pentland, B. Moghaddam, and T. Starner, "View-Based and Modular Eigenspaces for Face Recognition," Proc. IEEE CS Conf. Computer Vision and Pattern Recognition, pp. 84-91, Seattle, June 1994.
  17. 17.D.L. Swets, Y. Pathak, and J.J. Weng, "A System for Combining Traditional Alphanumeric Queries with Content-Based Queries by Example in Image Databases," Technical Report CPS-96-03, Michigan State Univ., Jan. 1996.
  18. 18.D.L. Swets, B. Punch, and J.J. Weng, "Genetic Algorithms for Object Recognition in a Complex Scene," Proc. Int'l Conf. Image Processing, pp. 595-598, Washington, D.C., Oct. 1995.
  19. 19.D.L. Swets and J.J. Weng, "Efficient Image Retrieval Using a Network with Complex Neurons," Proc. Int'l Conf. Neural Networks, Perth, Western Australia, Nov. 1995 (invited paper).
  20. 20.M. Turk and A. Pentland, "Eigenfaces for Recognition," J. Cognitive Neuroscience, vol. 3, no. 1, pp. 71-86, 1991.
  21. 21.J. Weng, N. Ahuja, and T.S. Huang, "Learning Recognition and Segmentation Using the Cresceptron," Proc. Int'l Conf. Computer Vision, pp. 121-128, Berlin, May 1993.
  22. 22.S.S. Wilks, Mathematical Statistics. New York: Wiley, 1963.

Citation

MLA
Swets, D. L., and J. J. Weng. “Using Discriminant Eigenfeatures for Image Retrieval”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, no. 8, 1996, pp. 831–36, https://doi.org/10.1109/34.531802.
APA
Swets, D. L., & Weng, J. J. (1996). Using discriminant eigenfeatures for image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(8), 831–836. https://doi.org/10.1109/34.531802
Chicago
Swets, D. L., and J. J. Weng. 1996. “Using Discriminant Eigenfeatures for Image Retrieval”. IEEE Transactions on Pattern Analysis and Machine Intelligence 18 (8): 831–36. https://doi.org/10.1109/34.531802.
Harvard
Swets, D.L. and Weng, J.J. (1996) “Using discriminant eigenfeatures for image retrieval”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(8), pp. 831–836. Available at: https://doi.org/10.1109/34.531802.
Vancouver
1. Swets DL, Weng JJ (1996) Using discriminant eigenfeatures for image retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence 18:831–836

BibTeX

@article{Swets_1996, title={Using discriminant eigenfeatures for image retrieval}, volume={18}, ISSN={0162-8828}, url={http://dx.doi.org/10.1109/34.531802}, DOI={10.1109/34.531802}, number={8}, journal={IEEE Transactions on Pattern Analysis and Machine Intelligence}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Swets, D.L. and Weng, J.J.}, year={1996}, pages={831–836} }
Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF