US 6,636,619 B1Grant
Computer based method and apparatus for object recognition
Issue Date:2003-10-21
•23 Claims
•8 Drawing Sheets
Abstract
A computer-based method and apparatus for recognition of objects which uses a novel subspace morphing theory, thereby obviating the need for normalization of scales prior to identification.
Metadata
Inventors
- Zhongfei Zhang
- Rohini K. Srihari
Application Information
Application Number:US 09/476,720
Filing Date:1999-12-30
Priority Date:1999-07-07
Art Unit:7
Classifications
IPC:
G06K 946
Field of Search:
382118382190382224382225382164382173
Patent Drawings (8 sheets)
Description
Priority Claim
[0002] This non-provisional patent claims the benefit under 35 U.S.C. Section 119(e) of U.S. Provisional Patent Application No. 60/142,579, filed on Jul. 7, 1999.
Source Code Listing
[0003] This patent includes a Computer Program Listing Appendix comprising the source code as found in the accompanying compact disc. The source code comprises the following files:
| File Name | Date of Creation | File Size (in KB) | |
|---|---|---|---|
| cccomp.h | Jul. 2, 1999 | 2 | |
| complex.h | Jul. 2, 1999 | 1 | |
| image_struct.h | Jul. 2, 1999 | 2 | |
| nr.h | Jul. 2, 1999 | 32 | |
| nrutil.h | Jul. 2, 1999 | 4 | |
| tiff.h | Jul. 2, 1 999 | 13 | |
| tiffio.h | Jul. 2, 1999 | 10 | |
| main_linear.c | Nov. 28, 1998 | 4 | |
| diff_linear.c | Nov. 28, 1998 | 7 | |
| sv_tif_testj.c | Jan. 26, 1997 | 4 | |
| glob_dat.c | Jul. 2, 1999 | 1 | |
| mem.c | Jul. 2, 1999 | 2 | |
| hue_mask.c | Jul. 2, 1999 | 2 | |
| tiff2RGB.c | Jul. 2, 1999 | 3 | |
| rgb2tiff.c | Jul. 2, 1999 | 3 | |
| nrutil.c | Jul. 2, 1999 | 17 | |
| svdcmp.c | Jul. 2, 1999 | 4 | |
| pythag.c | Jul. 2, 1999 | 1 | |
[0004] The source code as found in the computer program listing appendix and all the files therein, including the files listed above, is hereby incorporated by reference.
Field of the Invention
[0005] The present invention relates generally to object recognition, more specifically to computer based object recognition, and, more particularly, to a subspace morphing method for object recognition which obviates the need for normalization of images.
Background of the Invention
[0006] Although many successful techniques have been proposed in certain specific applications, object recognition, in general, remains a difficult and challenging problem. In appearance based approaches, representation of only the appearance of the object is still not sufficient for object recognition. This is because the variation space of the appearance is so huge that it is impossible to enumerate all the possible appearances (and then to index them). Depending upon the type of object at issue, the variation space comprises different variation dimensions. Existing techniques for object recognition require that the feature selection and matching be done in a predefined, dimensionally fixed space, and, if images of objects are given in different dimensions, a normalization in scale technique has to be applied to allow the feature vectors to fit into this space. Unfortunately, these normalization-based techniques have several major drawbacks, including, but not limited to an increase in processing time and resources.
[0007] In general, there are two types of variation dimensions in the appearance variation space. The first type of variation dimensions is due to the nature of the object itself, and different types of objects may result in different dimensions of variation. This type of variation dimension is referred to as an internal variation factor. In the case of a human face, for example, internal variation factors include face expression, face pose, face orientation, etc. The second type of variation dimensions is due to the environment and conditions when the object image is taken, and has nothing to do with the specific object represented by the image. This type of variation dimension is referred to as an external variation factor. Examples of external variation factors include scale (related to how close the camera is with respect to the object when the picture is taken), contrast (related to the lighting conditions when the picture is taken), and background (related to the environment where the picture is taken). External variation factors are independent of the object types to be recognized.
[0008] What is needed, then, is an object recognition method that does not require normalization of images.
Summary of the Invention
[0009] The present invention is a computer-based method and apparatus for recognition of objects. The invention uses a novel subspace morphing theory which obviates the need for normalization of scales prior to identification.
Brief Description of the Several Views of the Drawings
[0010] FIG. 1 is a first image containing a plurality of face images, with each of the face images having different scales, orientations, poses and expressions;
[0011] FIG. 2 is a second image containing a plurality of face images, with each of the face images having different scales, orientations, poses and expressions;
[0012] FIG. 3 illustrates the SVD Distance of a pair of SV morphed vectors for face images of two different individuals;
[0013] FIG. 4 illustrates the SVD Distance of a pair of SV morphed vectors for two face images of the same individual, where the individual images have different scales, orientations, poses and expressions;
[0014] FIG. 5 illustrates the SVD Distance of a pair of SV morphed vectors for two face images of the same individual, where the individual images have different scales, orientations, poses and expressions;
[0015] FIG. 6 illustrates the SVD Distance of a pair of SV morphed vectors for two face images of the same individual, where the individual images have different scales, orientations, poses and expressions;
[0016] FIG. 7 is a screen capture taken from the computer-based system of the invention, which screen capture illustrates performance of the system;
[0017] FIG. 8 is a flow chart depicting the steps of the claimed method.
Detailed Description of the Preferred Embodiment
[0018] In the description, which follows, the term “recognition” is intended to comprise detection and identification. The acronym SVD Distance as used in the following description is defined to mean the distance between two morphed SV (singular value) vectors.
[0019] The theory developed in this patent for appearance based object recognition is called subspace morphing theory. This work was motivated by the practical demand for a technique for recognizing objects collected with different scales and from different appearances. FIGS. 1 and 2 are first and second color images, respectively, each of which contains a plurality of face images, with each of the face images having different scales, orientations, poses and expressions. The images of FIGS. 1 and 2 illustrate typical “everyday life” situations. For example, FIG. 1 illustrates a group of individuals at a dinner meeting. Some individuals are seated, others are standing. Some individuals are facing the camera; others are turned at various angles with respect to the camera. Some faces are obscured or partially obscured. Similarly, FIG. 2 illustrates a group of participants at an academic seminar approaching the speaker at the conclusion of the talk. In this photographic image, only one person (third from left) is directly facing the camera. Some of the other people are facing to the left, others to the right, etc., and all face images vary in scale, appearance, pose and expression. The object of the present invention is to analyze images such as these, detect certain objects (such as faces), and then identify those objects (faces).
[0020] In the description that follows, theorems, definitions and equations are numbered for convenience.
[0021] Although the subspace morphing theory may be used for any type of object, throughout this patent, we use human face recognition as an example to demonstrate the application of this theory. In this patent, we always assume that the features we used are singular value (SV) vectors, and thus a feature space is a singular value space. Furthermore, we also assume that each SV vector has been sorted in value from the largest to the smallest. In the following description, we use R to denote a real space; thus, Rnis an n dimensional vector space, and Rm×nis an m×n dimensional matrix space (or image space). Also, we use a boldface symbol to denote a vector or matrix.
[0022] Sizing Theorem of SVD
[0023] The foundation of the subspace morphing theory and its algorithm is based on the following theorem, which we call the sizing theorem of singular value decomposition (SVD) for two arbitrary matrices (i.e. images) A1and A2:
[0024] Theorem 1 Let, A1εRm×n, A2εRm×n, W.L.O.G. m1≧n1m2≧n2. By SVD ∃SV vectors Λ and Σ for A1and A2, respectively.
[0025] Then, if n1>n2, extend the dimensionality of the vector Σ to n1by padding 0's to the rest of its dimensions; else, extend the dimensionality of Λ to n2similarly. Thus, for any positive integer n, the following holds:
[0026] ∥{square root over (m2n2)}Λ−{square root over (m1n1)}Σ∥n≦∥B1−B2∥F (1)
[0027] where B1is the matrix obtained by row-scaling m2and column-scaling n2of A1, B2is the matrix obtained by row-scaling m1and column-scaling n1of A2, and ∥.∥Fstands for matrix Frobenius norm, and ∥.∥nthe norm of an n dimensional vector.
[0028] We omit the proof of this theorem, in favor of a conceptual explanation. Given two images with different dimensions, we can always map them into a common space of imagery. This theorem establishes a relationship between the SV vectors extracted in the current spaces of these two images and the SV vectors that would be extracted after mapping them into that common space. Thus, using this theorem, we can immediately “extract” the SV vectors from that hypothetical common space based on the SV vectors obtained from the current space without actually mapping them into that common space.
[0029] Subspace Morphing
[0030] Based on the sizing theorem, we develop the subspace morphing theory. We start with the concept of vector projection from a space to another space.
[0031] Definition 1 Let v be a vector in space Rn. Let Rmbe an arbitrary space. Define vector v′ as a projection of v in space Rnto space Rmas follows. If m>n, the dimensionality of v′ is extended by padding 0's to the rest of its dimensions; if m<n, the dimensionality of v′ is truncated to m; if m=n, v′=v.
[0032] Now, we can introduce the concept of morphing an SV vector from a space to another space.
[0033] Definition 2 Given two arbitrary spaces Rm×nand Rp×q. W.L.O.G. assume m≧n, p≧q. Let AεRm×nv be its SV vector, and u′ be the projection of v in space Rnto space Rq. Define vector v′ as the morphed SV vector of v in space Rnto space Rqas follows:
[0034] where
[0035] is called the essential SV vector of v.
[0036] This is to say that v′ is the “equivalent” SV vector of a matrix in Rp×qmapped from A space Rm×n. Note that the values of the elements in an essential SV vector will always stay the same regardless whatever space it is morphed to.
[0037] Now we are ready to define the algebraic operations between two SV vectors with different dimensionalities.
[0038] Definition 3 AεRm×n, BεRm×n, W.L.O.G. assume m1≧n1m2≧n2. Let vAand vBbe their SV vectors, respectively. Given any space Rp×q, W.L.O.G. assume p≧q. Define the addition of vAand vBin space Rqas:
[0039] where uAand uBare the essential SV vectors of vAand vB, and vA′ and vB′ are the projection vectors of vAand vB, respectively.
[0040] In other words, vAand vBare first morphed to the space Rp×qbefore the addition is conducted.
[0041] Similarly, we can define the subtraction, dot product, and cross product of two SV vectors with different dimensionalities. Note that all these algebraic operations between two SV vectors are defined up to morphing them to a “common” space before the actual operation may be conducted, and this “common” space may be any arbitrary space; it does not necessarily have to be one of the original SV vector spaces or one of the essential SV vector spaces. As we will explain later, this gives us a great deal of flexibility in finding the best matching in the feature space.
[0042] Extending the binary operation between two SV vectors, we can define operations on a set of SV vectors with possibly different dimensionalities.
[0043] Definition 4 Given a set of SV vectors: viin space Rnrespectively, i=1, . . . ,k, let vi′ be the morphed vector of vifrom space Rn, respectively, to a “common” space Rq. The matrix V formed by all vi′ is called the collection matrix of v1in space Rq, i.e.
[0044] V=(v1′, . . . ,vk′)={square root over (pq)}U (5)
[0045] where U is called the essential collection matrix of vi. Let uibe the essential SV vectors of vi. Then,
[0046] U=(u1, . . . ,uk) (6)
[0047] Note that the essential collection matrix is independent of the “common” space that the given SV vectors are morphed to, except for setting a common dimensionality. Given a set of SV vectors, the essential collection matrix is different from that which would result from just directly “normalizing” the dimensionalities of these SV vectors to a common space; instead, it is obtained by “normalizing” (if we do want to use the word “normalize”) the dimensionalities of the essential SV vectors of these SV vectors to a common space.
[0048] Now we are ready to state the algorithm for object recognition using subspace morphing theory developed above. We call this algorithm SM. We first define the general scenario of the problem of object recognition, where we have N classes of objects in the model database, and each class had Nisamples collected (i=1, . . . ,N). The idea of SM is to use nearest linear combination in a morphed subspace to find the best match for a query image. Specifically, assume that each sample in the model database is represented by an essential SV vector uijextracted from the sample image in the database (here i indexes the class number, and j indexes the sample number in this class). Then we use the linear combination Uiaiof all the essential SV vectors in class i to represent the “cluster region” of this class in the feature space, where Ui is the essential collection matrix of class i, and aiis a coefficient vector in space RN. Therefore, given a query image, we can also extract the essential SV vector w. Note that all the sample images in each class may come with different dimensions (i.e., they are not normalized in scale for the reason explained below). Consequently, the SV vectors of these samples are in different dimensionalities, and so is the SV vector for the query image. Based on the subspace morphing theory, we can morph all of their essential SV vectors to an arbitrary “common” space Rq, corresponding to an arbitrary hypothetical “common” image in space Rp×q. Thus, if the query image is in class i, the following must be true for a specific ai:
[0049] {square root over (pqw)}={square root over (pq)}Uiai (7)
[0050] which immediately leads to
[0051] w=Uiai (8)
[0052] Equation 8 is only valid under this “common” morphing subspace Rq. Other than this, this constraint is independent of the hypothetical “common” image space Rp×q. This is a nice property, which enables us to conduct vector level comparison in different dimensionalities without necessarily worrying about the specific dimensions of the hypothetical “common” space. It should be noted once again that given a set of model SV vectors and a query SV vector, this constraint is different from just directly “normalizing” the dimensionalities of these SV vectors to a common space; instead, it is to “normalize” (if we do want to use the word “normalize”) the dimensionalities of the essential SV vectors of these SV vectors to a common space.
[0053] Typically, Ni<<q. That means that Equation 8 is over-determined, and usually it does not hold in equality. Instead, we need to minimize the energy function for each class i:
[0054] Ei=(wT−aiTUiT)(w−Uiai) (9)
[0055] This leads to the constraint of
[0056] which results in
[0057] ai=(UiTUi)−1UiTw (10)
[0058] Hence, we can finally classify the query image as class i if Eiis minimum over the N classes, and it is under a threshold; otherwise, classify it as unknown.
[0059] FIG. 8 depicts in graphic form the method described and enabled by the above discussion.
[0060] Since using SVD for object recognition is not new, since using nearest linear combination in object recognition is not new, why can't we just normalize all the sample and query images into a standard space and then apply the existing SVD and nearest linear combination techniques for object recognition? Why do we need to bother to do subspace morphing for object recognition? The next section is dedicated to answering these questions.
[0061] Why is Normalization to be Avoided?
[0062] Object recognition is conducted as searching and matching in a feature space (e.g., eigen features, SVD features, etc.). Since the dimensionality of this feature space is a function of the image dimensions, in order to facilitate the recognition process, all the conventional techniques focus on normalizing images in scale into standard dimensions. While this is feasible and realistic in certain applications (e.g., ID checking where all the photos are in a standard resolution), in many other applications images may be in different dimensions. This situation occurs either in the stage of data collection for constructing a model database, or in the stage of recognition per se, or both. For example, in the intelligence community, face samples are collected from “normal” pictures or video, (as shown in FIGS. 1 and 2), as opposed to mugshot or passport type images with a normalized scale. Therefore, from an application point of view, it is politically necessary to develop techniques that do not rely on a fixed, normalized feature space for object recognition. This was the motivation leading to the development of the subspace morphing theory for object recognition. Below, we show technically why the subspace morphing theory is better than the conventional, normalization-based techniques.
[0063] First, normalization requires more computation at the cost of either losing information or introducing redundancy into the normalized feature space. It is clear that conducting normalization in scale requires extra computation (i.e., scale up or down). In addition to this extra computation in the case of scaling up (i.e., transforming from a “smaller” space to a “larger” space), redundancy is introduced, as data interpolation does not bring in new information. Even worse, additional computation is required in feature extraction (e.g., SVD in this context which increases cubically. (The complexity of SVD is O(mn2) for a matrix in m×n). On the other hand, in the case of scaling down, information which is precious in object recognition has to be lost, although computation is saved in feature extraction. However, this saving is at the cost of losing precious information. In the subspace morphing theory, information is used as is given (i.e., neither is information contained in the original image lost, nor is any redundancy introduced), and no extra cost in additional computation is required.
[0064] Second, and more importantly, regardless of what features are used (e.g., either SVD or eigenfeatures), recognition in a fixed, normalized space has less recognition capability in terms of the potential number of object classes to be recognized than the subspace morphing theory has. If the feature space is fixed, say Rn, assuming that each class has the same number of samples, say Nc, the upper bound of the number of object classes these techniques are able to recognize is CNn(the combinatorial number of choosing Ncfrom n). In the subspace morphing theory, on the other hand, since the feature space Rnis not fixed, and it can be morphed to an arbitrary space dynamically in the process of matching, this upper bound is determined by the highest dimensions of the images during the recognition process. As the highest dimensions of images are open (i.e., not fixed) in subspace morphing because query images with arbitrary dimensions are expected, this upper bound is also open and in general is much higher than the fixed upper bound, resulting in much larger recognition capability than the conventional recognition techniques.
[0065] Third, and most importantly, recognition in a fixed, normalized space tends to have a higher error rate than the subspace morphing theory would have. The difference of the dimensions in images as well as the difference in dimensionalities in the resulting feature space is “extra” and precious information that not only helps enhance the recognition capability as stated above, but also helps reduce the recognition error rate. It is known that normalization may lose information (in the case of scaling down). If the feature space is fixed dimensionally, this amount of lost information may no longer be recovered, nor may it contribute to the recognition. Rather, this information loss contributes to a potential higher recognition error rate. On the other hand, in subspace morphing theory, no information is lost, and every piece of information is used to contribute to the recognition, resulting in a lower recognition error rate.
[0066] Thus, it is seen that the subspace morphing theory for object recognition is more attractive, more effective, and more robust than the conventional, normalization-based techniques. This conclusion is also supported experimentally in the next section.
[0067] Experimental Results
[0068] As mentioned previously, although the subspace morphing theory and the related technique can be applied to any types of object for object recognition, in this patent, we use face recognition as an example to demonstrate the effectiveness and robustness of this technique.
[0069] Face recognition has received intensive attention in the community of computer vision and pattern recognition research for quite a long time. Typical methods include eigenfaces and the related subspace analysis, singular value decomposition, Gabor wavelet features, neural networks, and shape and appearance-based probabilistic models. One group of researchers has combined different features together and used the mixture-distance to recognize human faces.
[0070] Since color imagery is popular in use and is easy to obtain in practice, we focus our attention only on color imagery in the following implementation and experiments of this technique, although the theory of subspace morphing can be used in intensity imagery as well. The other reason we use color imagery is that certain color features (e.g., hue and chroma as we define here) are incentives with respect to lighting conditions to a certain degree.
[0071] We previously explained conceptually why the subspace morphing technique should perform better than the conventional normalization based techniques. This also needs to be demonstrated through experimental evaluations. In order to conduct a fair comparison through experiments, it would be ideal that we could have a common testbed (i.e., a model face database, and a test face database) to test both the subspace morphing based technique and the conventional normalization based techniques. Unfortunately, all the publicly available face databases are made as normalized samples. In fact, the conventional normalization based techniques could be viewed as a trivial special case of the subspace morphing theory, in which no subspace morphing is conducted. If we used any of these face databases, that would make the essential strength of this technique impotent, and would essentially make this technique reduced to the conventional normalization based techniques.
[0072] Based on this consideration, we conducted a “self evaluation”, meaning that we collected a model face database and a test face database, and use this technique to measure the recognition rate. We collected a model face database of 112 face sample images of 25 individuals, and a test face database of 226 face sample images of these 25 individuals. Part of these face images were collected by directly using a digital camera to take the face images of the individuals. The rest of the images in these databases were collected by running a face detection system to a collection of daily-life or business images such as FIG. 1 contributed voluntarily by people, or obtained via the internet, and cropping the face samples in these pictures automatically. During the process of data collection, we paid special attention to collecting data reflecting significant variations in scale, pose, orientation, expression, contrast, and background. For all the face images collected in both databases, we leave the images “as the way they were”, i.e., no normalization in scale was performed.
[0073] The distribution of the number of images for each individual in the databases is not uniform, depending on the availability of the individuals. For those individuals whose face samples were obtained through personal contribution or through internet collection, the number of samples was very limited. On the other hand, for those individuals who were willing to let us take their face samples directly using a digital camera, we were able to collect relatively large number of samples with significantly large variations in appearances. Nevertheless, we tried to keep a relatively balanced distribution in the model face database; individuals in this database receive number of samples varied from three to seven, with most of the individuals having four or five samples.
[0074] With this model face database, we ran the SM algorithm over every face images in the test face database. Of the 226 test samples, only 18 were misclassified! That means that based on this set of evaluation, the recognition rate is about 92%. FIG. 7 is a screen capture taken from the computer system of the present invention, which shows a test image being matched by five images from the database (the system actually found six matches, but only five are shown in the screen capture). The image in the upper-left corner is the query image, and the five images shown in the bottom of the screen are the images in the database corresponding to this individual. We examined the 18 misclassification cases, and found that all of them were probably due to the biased distribution of appearance in the variation space for the sample images in the model face database. In fact, almost all the sample images in the model database were frontal or near frontal face images and were taken at the same time for each individual (i.e., the same background, e.g., hairstyle, cloths, etc.). This can be seen in FIGS. 4 to 6, which illustrate examples of recognition of the same individuals with different scales, orientations, poses and expressions. Note the significant change in appearances, scales, lighting conditions, and contrasts between the samples in the model database and the samples in the test database. Research shows that human eyes play a significant role in face recognition for human vision. Yet in one of the test images, the individual wore sunglasses to block the eyes, but this sample was still correctly recognized.
[0075] Thus, it is seen that we have developed a new computer-based method and apparatus for appearance based object recognition, based upon a new theory using subspace morphing. The robustness and effectiveness of this theory is demonstrated through face recognition experiments with a 92% recognition rate in a very complicated test database. Although this technique still needs to be evaluated in a larger scale experiment, it is not difficult to see the robustness already present through this experiment.
Claims
What we claim is:
1. A method for recognizing an image of an object, comprising:
a) extracting a singular value (SV) feature vector from said image of an object;
b) determining dimensions of said image of said object;
c) creating a first essential singular value vector (ESV) based upon said extracted singular value (SV) feature vector and said dimensions of said image of said object;
d) comparing said first ESV vector of said image of an object to be recognized with a second ESV vector stored in a database, where said second ESV vector is representative of a known object to determine a distance between said first ESV vector and said second ESV vector; and,
e) determining if said distance is within a predetermined range, which would indicate that said object to be recognized is the same as said known object represented by said second ESV vector.
2. A method for recognizing an image of an object as recited in claim 1 where said object is a face.
3. A method for recognizing an image of an object as recited in claim 1 wherein said predetermined range is determined empirically.
4. A method for recognizing an image of an object, comprising:
a) extracting a singular value (SV) feature vector from said image of an object;
b) determining dimensions of said image of said object;
c) creating a first essential singular value vector (ESV) based upon said extracted singular value (SV) feature vector and said dimensions of said image of said object;
d) comparing said first ESV vector of said image of said object to be recognized with a second ESV vector stored in a database, where said second ESV vector is representative of a first known object to determine a first distance between said first ESV vector and said second ESV vector;
e) comparing said first ESV vector of said image of said object to be recognized with a third ESV vector stored in a database, where said third ESV vector is representative of a second known object to determine a second distance between said first ESV vector and said third ESV vector; and,
f) comparing said first and second distances to determine which of said first and second distances is lower where said lower distance indicates which of said second and third ESV vectors is more likely to represent the object to be recognized.
5. A method for recognizing an image of an object as recited in claim 4 wherein said database comprises two or more ESV vectors.
6. A method for recognizing an image of an object as recited in claim 5 wherein said database comprises feature vectors which represent at least one class of objects.
7. A method for recognizing an image of an object as recited in claim 5 wherein said database comprises feature vectors which represent two or more classes of objects.
8. A method for recognizing an image of an object as recited in claim 4 where said object is a face.
9. A method for recognizing an image of an object as recited in claim 4, further comprising the step of determining if said lower distance is within a predetermined range, in which case the ESV vector corresponding to said lower distance is most likely representative of the object to be recognized.
10. A method for recognizing an image of an object, comprising:
a) extracting a singular value (SV) feature vector from said image of an object;
b) determining dimensions of said image of said object;
c) creating a first essential singular value vector (ESV) based upon said extracted singular value (SV) feature vector and said dimensions of said image of said object;
d) comparing said first ESV vector of said image of said object to be recognized with a plurality of ESV vectors stored in a database, where each of said stored ESV vectors is representative of a known object to determine a distance between said first ESV vector and each of said plurality of ESV vectors; and,
e) selecting an ESV vector from said plurality of ESV vectors having the lowest distance to said first ESV vector, where the ESV vector corresponding to said lowest distance is likely to represent the object to be recognized.
11. A method for recognizing an image of an object as recited in claim 10, further comprising the step of determining if said lower distance is within a predetermined range, in which case the ESV vector corresponding to said lower distance is most likely representative of the object to be recognized.
12. A method for recognizing an image of an object as recited in claim 10 where said object is a face.
13. A method of identifying an object within an image containing two or more objects, comprising:
a) detecting one or more candidate class(es) of objects within said image based upon a segmentation of said image;
b) selecting a specific candidate class of objects to be recognized based upon a user specification;
c) recognizing a sub-image of an object within said specific candidate class of objects, where said recognizing is accomplished by steps comprising the following:
1) extracting a singular value (SV) feature vector from said sub-image of said object to be recognized;
2) determining dimensions of said sub-image of said object to be recognized;
3) creating a first essential singular value vector (ESV) based upon said extracted SV feature vector and said dimensions of said sub-image of said object to be recognized;
4) comparing said first ESV vector of said sub-image of said object to be recognized with a second ESV vector stored in a database, where said second ESV vector is representative of a known object to determine a distance between said first ESV vector and said second ESV vector; and,
5) determining if said distance is within a predetermined range, which would indicate that said object to be recognized is identified as said known object represented by said second ESV vector.
14. A method of identifying an object within an image containing two or more objects, as recited in claim 13, wherein said segmentation is selected from the group consisting of color features, shape features and texture features of said objects.
15. A method of identifying an object within an image containing two or more objects, as recited in claim 13, wherein said segmentation comprises color features of said objects.
16. A method of identifying an object within an image containing two or more objects, as recited in claim 15, wherein said color segmentation comprises consideration of hue characteristics of said objects.
17. A method of identifying an object within an image containing two or more objects, as recited in claim 15, wherein said segmentation comprises consideration of chroma characteristics of said objects.
18. A method of identifying an object within an image containing two or more objects, as recited in claim 13, wherein said object to be identified is a face.
19. A method of organizing a first database containing representations of one or more images, where each image is associated with an object, comprising:
a) extracting a singular value (SV) feature vector from each of said one or more images;
b) determining dimensions of each of said one or more images;
c) creating an essential singular value vector (ESV) based upon said extracted singular value (SV) feature vector and said dimensions of each of said one or more images; and,
d) calculating an essential collection matrix from said ESV of each of said one or more images, where said essential collection matrix represents an image of an identical object.
20. A method of organizing a database as recited in claim 19, further comprising the step of storing said essential collection matrix in said first database.
21. A method of organizing a database as recited in claim 19, further comprising the step of storing said essential collection matrix in a second database.
22. A method of organizing a database as recited in claim 19, further comprising the step of recognizing an unknown object by comparing an extracted essential singular value vector (ESV) from an image of said object with each of said essential collection matrices stored in said database.
23. A method of organizing a database as recited in claim 22 wherein said recognizing said unknown object by comparing an extracted essential singular value vector (ESV) further comprises the step of determining the smallest distance between said ESV of said image of said object and each of said essential collection matrices of said database, where the matrix corresponding to said smallest distance represents the unknown object.
Patent Citations (10)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US5012522(A) | 1991-04-01 | Lambert | Applicant |
| US5164992(A) | 1992-11-01 | Turk et al. | Applicant |
| US5245675(A) | 1993-09-01 | Ferre et al. | Examiner |
| US5450504(A) | 1995-09-01 | Calia | Applicant |
| US5561718(A) | 1996-10-01 | Trew et al. | Applicant |
| US5642431(A) | 1997-06-01 | Poggio et al. | Applicant |
| US5699449(A) | 1997-12-01 | Javidi | Applicant |
| US5715325(A) | 1998-02-01 | Bang et al. | Applicant |
| US5802208(A) | 1998-09-01 | Podilchuk et al. | Applicant |
| US6178261(B1) | 2001-01-01 | Williams et al. | Examiner |
Non-Patent Literature (20)
- Al-Shaykh et al. “Invariant Image Analysis Based on Radon Transform and SVD.” IEEE Trans. on Circuits and Systems—II.Analog and Digital Signal Processing, vol. 43, No. 2, Feb. 1996, pp. 123-133.Applicant
- Example-Based Learning for View-Based Human Face Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, No. 1, Jan. 1998, pp. 39-51.Applicant
- Neural Network-Based Face Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, No. 1, Jan. 1998, pp. 23-38.Applicant
- Human and Machine Recognition of Faces: A Survey. Proceedings of the IEEE, vol. 83, No. 5, May 1995, pp. 703-740.Applicant
- Visionics Corporation, Innovations in Recognition Systems. http://www.faceit.com, Apr. 28, 1998.Applicant
- Face Recognition From One Example View. Proc. of IEEE International Conference on Computer Vision, IEEE Computer Society Press, 1995, pp. 500-507.Applicant
- A robust face identification scheme-KL expansion of an invariant feature space. SPIE vol. 1607 Intelligent Robots and Computer Vision X: Algorithms and Techniques, 1991, pp. 71-84.Applicant
- Probabilistic Visual Learning for Object Representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, No. 7, Jul. 1997, pp. 696-710.Applicant
- Eigenfaces vs. Fisherfaces: Recognition Using Class Specific Linear Projection. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, No. 7, Jul. 1997, pp. 711-720.Applicant
- Face Recognition: The Problem of Compensating for Changes in illumination Direction. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, No. 7, Jul. 1997, pp. 721-732.Applicant
- Linear Object Classes and Image Synthesis From a Single Example Image. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, No. 7, Jul. 1997, pp. 733-742.Applicant
- An Algorithm for the Learning of Weights in Discrimination Functions Using a Priori Constraints. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, No. 7, Jul. 1997, pp. 764-779.Applicant
- Automatic Interpretation and Coding of Face Images Using Flexible Models. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, No. 7, Jul. 1997, pp. 743-755.Applicant
- Face Recognition: Features versus Templates. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 15, No. 10, Oct. 1993, pp. 1042-1052.Applicant
- Algebraic Feature Extraction of Image for Recognition. Pattern Recognition Journal, vol. 24, No. 3, pp. 211-219, 1991.Applicant
- Mixtures of Local Linear Subspaces for Face Recognition. Proc. of International Conference on Computer Vision and Pattern Recognition, IEEE Computer Society Press, 1998, pp. 32-37.Applicant
- How Should We Represent Faces for Automatic Recognition? IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21, No. 8, Aug. 1999, pp. 725-736.Applicant
- Line-Based Face Recognition under Varying Pose. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21, No. 10, Oct. 1999, pp. 1081-1088.Applicant
- Recognizing Human Faces in Complex Context. International Conference on Imaging Science Systems and Technology, CSREA Press, Las Vegas, Nevada, Jul. 1998, pp. 218-225.Applicant
- Identifying Human Facez in General Appearances. IEEE International Conference on Systems, Man and Cybernetics, IEEE Press, San Diego, California, Oct. 1998, pp. 4318-4323.Applicant