Elsevier

Pattern Recognition

Volume 45, Issue 8, August 2012, Pages 2952-2961
Pattern Recognition

Directed enumeration method in image recognition

https://doi.org/10.1016/j.patcog.2012.02.011Get rights and content

Abstract

The article is devoted to the problem of image recognition in real-time applications with a large database containing hundreds of classes. The directed enumeration method as an alternative to exhaustive search is examined. This method has two advantages. First, it could be applied with measures of similarity which do not satisfy metric properties (chi-square distance, Kullback–Leibler information discrimination, etc.). Second, the directed enumeration method increases recognition speed even in the most difficult cases which seem to be very important in practical terms. In these cases many neighbors are located at very similar distances. In this paper we present the results of an experimental study of the directed enumeration method with comparison of color- and gradient-orientation histograms in solving the problem of face recognition with well-known datasets (Essex, FERET). It is shown that the proposed method is characterized by increased computing efficiency of automatic image recognition (3–12 times in comparison with a conventional nearest neighbor classifier).

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 Xr=xuv(r), (u∈{1,...,U}, v∈{1,...,V}) be specified. Here U and V are the image height and width, respectively, xuv(r){0,1,,xmax} is the intensity of an image point with coordinates (u, v); r is the reference number (r=1, …, R), and xmax is the maximum intensity. It is assumed that each image Xr defines class c(Xr)∈{1, ..., C}, CR 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=constR first images {X1, X2XN}, 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μ=argminr{1,...,N}ρ(X/Xr).

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)

  • Essex Faces database,...
  • FERET dataset,...
  • R.L. Rivest

    On the Optimality of Elias's Algorithm for Performing Best-Match Searches, Information Processing

    (1974)
  • J.G. Cleary

    Analysis of an algorithm for finding nearest neighbors in euclidean space

    ACM Transactions on Mathematical Software

    (1979)
  • J.L. Bentley et al.

    Optimal expected-time algorithms for closest point problems

    ACM Transactions on Mathematical Software

    (1980)
  • J.H. Friedman et al.

    An algorithm for finding best matches in logarithmic expected time

    ACM Transactions on Mathematical Software

    (1977)
  • S. Arya et al.

    An optimal algorithm for approximate nearest neighbor searching

    Journal of the ACM

    (1998)
  • D. Lowe

    Distinctive image features from scale-invariant keypoints

    International Journal of Computer Vision

    (2004)
  • S. Arya, D.M. Mount, Approximate nearest neighbor queries in fixed dimensions, Fourth Annual ACM-SIAM Symposium on...
  • 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.

    View full text