Directed enumeration method in image recognition
Highlights
► Directed enumeration method is proposed to improve image recognition performance. ► The method is applied with similarity measures which do not met metric properties. ► The method increases performance in 3–12 times in comparison with nearest neighbor. ► Recognition speed is increased when many neighbors are located at similar distances.
Introduction
Automatic image recognition is an active research topic in computer vision [1], [2]. Its applications include biometrics, law enforcement, human–computer interaction systems, etc. Our focus of research is image recognition in the context of large databases [3], [4]. We define the database to be large if it contains hundreds of different classes. Conventional classifiers (artificial neural networks, template matching, the Bayes classifier, hidden Markov models, HMM) [2] are usually based on exhaustive search through all classes, hence they often cannot be implemented in real-time applications. Moreover, if the number of classes is large, the amount of model images in the database is not usually enough to train the complex classifier and achieve high accuracy. In worst cases even one sample per class [5] may happen. Thus nearest neighbor algorithms [6] are preferred [3]. As the demand of such applications increases [7], many novel image recognition methods have been proposed in the last several decades. Unfortunately, the existing algorithms cannot be used with non-traditional measures of similarity such as the naive Bayesian classifier or chi-square statistics [2]. Moreover, they show poor results in most practical cases of object recognition where many neighbors are at very similar distances [3]. To overcome these problems we proposed the directed enumeration method [4]. The method was originally applied with color histogram comparison using naive Bayesian classifier to recognize images from synthetic dataset [4]. Meanwhile, its capabilities have not been fully exploited. In particular, almost no studies have addressed the advantages of our method in real image recognition tasks. The present paper seeks to fill this gap. We propose here a new modification of our method and show that it is beneficial in terms of computational speed and memory capacity in face recognition and various feature sets (conventional color- and modern gradient orientation-histograms).
The rest of the paper is organized as follows: Section 2 reviews some related studies. Section 3 introduces the image recognition problem and desirable metric properties of decision statistics. In Section 4 we present the directed enumeration method. Section 5 describes image features and measures of similarity used in the experimental study in a problem of face recognition. In Section 6, we present the experimental results and analyze the proposed method in the face recognition problem with large databases (Essex [8] and FERET [9] data sets). Section 7 introduces new modification of the directed enumeration method which could be used to reduce necessary amount of additional memory. Finally, concluding comments are presented in Section 8.
Section snippets
Related research
In this section, we focus on the pattern recognition literature that deals specifically with prevention of an exhaustive search.
For uniformly distributed (in terms of some measure of similarity) point sets, good expected case performance can be achieved by algorithms based on simple decompositions of image space into regular grids. Rivest [10] and later Cleary [11] provided analyzes of these methods. Bentley, Weide, and Yao [12] also analyzed a grid-based method for distributions satisfying
Automatic image recognition
Let a set of R>1 grayscale model images (u∈{1,...,U}, v∈{1,...,V}) be specified. Here U and V are the image height and width, respectively, is the intensity of an image point with coordinates (u, v); r is the reference number (r=1, …, R), and is the maximum intensity. It is assumed that each image Xr defines class c(Xr)∈{1, ..., C}, C≤R is a given amount of classes. The objects belonging to each class have some common features or similar characteristics.
Directed enumeration method
Following the general computation scheme (1), (2), we reduce the image X recognition problem to a check of the N=const⪡R first images {X1, X2 … XN}, from the specified database {Xr}. After that we define the image Xμ as the closest (in terms of used measure of similarity ρ(·)) to query image X already checked database model
If Xμ meets the termination requirement (2), the enumeration will end. However, it can generally be assumed that none of the first N alternatives
Automatic face recognition
As it was stated in the introduction, automatic face recognition is one of the most difficult tasks in image recognition. Nearest neighbor face recognition can be factorized into two essential parts [18]: (1) feature extraction from facial images; and (2) similarity measure design. In this section we describe two conventional feature sets: traditional color histograms [1], [32] and modern gradient orientation histograms (modification of SIFT method [15]). For the second part we use
Experimental results
Our experiment deals with the problem of face recognition [17], [18]. The images were preliminarily processed with OpenCV library [36] to detect faces. After that the median filter with window size (3×3) was used to remove some noise in detected faces. This window size provides the best recognition accuracy for both FERET and Essex datasets and measures of similarity (12), (17).
In our earlier experiments [4], [28], [30] we found that the directed enumeration method parameter N can get out
Directed enumeration method modification
The most important limitation [30] of the described procedure (2), (3), (4), (5), (6), (7), (8) is its need to store distance matrix Ρ. Thus the directed enumeration method requires O(R2) additional memory. The modification of the directed enumeration method which needs to store only the most valuable part of this matrix is proposed in this Section. We guess that the probability p (9) should depend also on the distance between X and Xi. We could assume that image Xi contains valuable
Conclusion
In this paper we investigated the possibility of a computational speed increase in automatic image recognition in large databases [38]. It is well-known [3] that when a number of classes in the model database is large, the use of high-dimensional features [15] is critical, due to the improved level of discrimination they can provide. It is also evident that finding the nearest neighbor [6] to a query point rapidly becomes inefficient as the dimensionality of the feature space increases.
Andrey Savchenko received PhD in Mathematical Modeling (2010) in Higher School of Economics, Moscow, Russian Federation, and M.S. degree in Applied Mathematics and Informatics (2008) in Nizhniy Novgorod State Technical University, Russian Federation. Currently, he is working in National Research University Higher School of Economics, Nizhny Novgorod.
His research areas include computer vision, pattern recognition, image processing, and information retrieval.
References (40)
- et al.
Face recognition from a single image per person: a survey
Pattern Recognition
(2006) - et al.
Image retrieval: current techniques, promising directions and open issues
Journal of Visual Communication and Image Representation
(1999) - et al.
Approximative fast nearest neighbor recognition
Pattern Recognition Letters
(1983) - et al.
Combining similarity measures in content-based image retrieval
Pattern Recognition Letters
(2008) - et al.
Effective image retrieval using dominant color descriptor and fuzzy support vector machine
Pattern Recognition
(2009) - et al.
Computer Vision
(2001) - et al.
Pattern Recognition
(2009) - J. Beis, D.G. Lowe, Shape indexing using approximate nearest-neighbour search in high dimensional spaces, Conference on...
Method of directed enumeration of alternatives in the problem of automatic recognition of half-tone images
Optoelectronics, Instrumentation and Data Processing
(2009)- et al.
Nearest neighbor pattern classification
IEEE Transactions on Information Theory
(1968)
On the Optimality of Elias's Algorithm for Performing Best-Match Searches, Information Processing
Analysis of an algorithm for finding nearest neighbors in euclidean space
ACM Transactions on Mathematical Software
Optimal expected-time algorithms for closest point problems
ACM Transactions on Mathematical Software
An algorithm for finding best matches in logarithmic expected time
ACM Transactions on Mathematical Software
An optimal algorithm for approximate nearest neighbor searching
Journal of the ACM
Distinctive image features from scale-invariant keypoints
International Journal of Computer Vision
Cited by (0)
Andrey Savchenko received PhD in Mathematical Modeling (2010) in Higher School of Economics, Moscow, Russian Federation, and M.S. degree in Applied Mathematics and Informatics (2008) in Nizhniy Novgorod State Technical University, Russian Federation. Currently, he is working in National Research University Higher School of Economics, Nizhny Novgorod.
His research areas include computer vision, pattern recognition, image processing, and information retrieval.