Method and system for detecting and classifying objects in an image

• US 6,501,857 B1
• Filed: 07/20/1999
• Issued: 12/31/2002
• Est. Priority Date: 07/20/1999
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Elad, Michael, Keren, Daniel, Gotsman, Craig
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US09/357,692
• Time in Patent Office: 1,260 Days
• Field of Search: 382/115-119, 382/133, 382/155, 382/159, 382/160, 382/173, 382/181, 382/190, 382/195, 382/197, 382/209, 382/218, 382/219, 382/220, 382/224-225, 382/227, 382/254, 382/263-264, 382/276, 382/278-279, 382/282, 382/305, 707/1-10
• US Class Current: 382/224
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

This disclosure provides a system for classifying images, used in image detection, image recognition, or other computer vision. The system processes directory images to obtain eigenvectors and eigenvalues, and selects a set of “smooth” basis vectors formed by linear combinations of these eigenvectors to be applied against a target image. Contrary to conventional wisdom, however, a group of the eigenvectors having the weakest eigenvalues are used to select the basis vectors. A second process is then performed on this group of “weakest” eigenvectors to identify a set of candidate vectors, ordered in terms of “smoothness.” The set of basis vectors (preferably 3-9) is then chosen from the candidate vectors in order of smoothness, which are then applied in an image detection or image recognition process. Unlike some conventional systems where “strong” directory presence and thresholds are used to detect possible matches, the present system uses smooth, weak vectors to ideally produce zero or near zero results for matches.

Claims

1. A method of classifying at least a portion of a target image using a digital processor and a directory of image examples, comprising:

processing image examples with the digital processor and deriving therefrom a set of component vectors;

using vectors from the set of component vectors to select a set of basis vectors; and

using the digital processor to compare at least one vector in the set of basis vectors against the target image to yield comparison results and classifying portions of the target image in dependence upon the comparison results;

wherein selecting basis vectors includes

using the digital processor to perform an operation upon at least some vectors to determine strength of correlation with image examples in the directory,

using the digital processor to perform an operation upon at least some vectors to determine strength of correlation with smooth image transitions,

responsive to the operations, selecting the set of basis vectors to include only vectors which relatively weakly correlate with image examples in the directory and which relatively strongly correlate with smooth image transitions.

2. A method according to claim 1, wherein:

processing image examples and deriving therefrom vectors includes determining eigenvectors for the directory of image examples;

selecting the set of basis vectors includes performing a first cut of eigenvectors to eliminate eigenvectors that correlate by more than a predetermined amount with image examples; and

selecting the set of basis vectors includes transforming remaining eigenvectors in a manner that emphasizes smoothness and selecting a specific number Y of transformed vectors in order of strongest correlation with smooth image transitions.

3. A method according to claim 1, wherein selecting the set of basis vectors includes:

applying a weighting function to vectors, the weighting function emphasizing both weakness of correlation with image examples and vector smoothness, to thereby develop a weight for each vector; and

selecting the set of basis vectors includes using weights developed from application of the weighting function to identify a specific set of Y vectors associated with strongest weights from application of the weighting function.

4. A method according to claim 1, wherein:

processing image examples includes processing image examples and deriving therefrom eigenvectors;

performing the operation upon vectors to determine which most strongly correlate with image examples in the directory includes determining values associated with each eigenvector, each value indicative of how strongly the associated eigenvector correlates with image examples in the directory, and

selecting the set of basis vectors includes excluding from consideration at least those eigenvectors corresponding to at least the strongest fifty percent of correlation with image examples in the directory, and selecting a set of basis vectors dependent upon all remaining eigenvectors not excluded from consideration.

5. A method according to claim 4, wherein selecting the set of basis vectors includes determining eigenvectors responsible for at least ninety-five percent of correlation with the image example, and excluding those eigenvectors from consideration.

6. A method according to claim 4, wherein selecting the set of basis vectors includes determining eigenvectors responsible for at least ninety-nine percent of correlation with the image example, and excluding those eigenvectors from consideration.

7. A method according to claim 1, further using one of software or firmware that implements a singular value decomposition function, and wherein selecting the set of basis vectors includes:

applying the singular value decomposition function to image examples in the directory, to thereby generate a set of eigenvectors and a set of associated weights;

selecting a group of eigenvectors having the smallest associated weights;

applying a measure to at least those eigenvectors in the group using the digital processor, to thereby produce candidate vectors which have been processed to emphasize smoothness; and

responsive to relative smoothness, choosing the set of basis vectors to be a set of Y smoothest candidate vectors.

8. A method according to claim 1, wherein classifying portions of the target image includes:

convolving the smoothest vector from the set of basis vectors with the target image, to thereby derive a set of products, wherein the set of products is characterized as being near zero substantially only for image regions representing likely presence of image examples from the directory in the target image.

9. A method according to claim 8, further comprising:

convolving the second smoothest vector from the set of basis vectors with the target image, at least in areas associated with near zero products as a result of convolution of the smoothest vector with the target image.

10. A method according to claim 1, wherein:

said method further comprises, during a training phase, determining mapping of each vector in the set of basis vectors to each image example in the directory; and

classifying images includes image recognition, by recognizing a mapping between vectors in the set of basis vectors to the target image which is substantially similar to mapping between a specific image example in the directory.

11. A method according to claim 1, wherein said method further comprises, during a training phase, selection of the set of basis vectors through a single minimization function having two singular value decomposition components.

12. A method of classifying at least a portion of a target image using a digital processor and a directory of image examples, comprising:

processing image examples with the digital processor and deriving therefrom a set of component vectors;

using component vectors to select a set of basis vectors; and

using the digital processor to compare at least one vector in the set of basis vectors against the target image to yield comparison results and classifying portions of the target image in dependence upon the comparison results;

wherein selecting the set of basis vectors includes

selecting only vectors for the set of basis vectors which, when convolved with portions of the target image having matches with a image example in the directory, tend to produce a result that is substantially zero and not selecting vectors that tend to produce a result that is substantially non-zero.

13. A method according to claim 12, wherein the digital processor includes a computer and a memory device, further comprising:

inputting a set of image examples which are formed by two-dimensional pixel arrays to the computer, such that the image examples are represented by matrices;

processing the matrices with the computer to realize an orthogonal linear subspace of the matrices, defined by eigenvectors that weakly correlate with the image examples;

using the computer to identify smooth vectors from the orthogonal linear subspace and to select from the smooth vectors a set of smoothest vectors; and

outputting the set of smoothest vectors to a memory device for use as the set of basis vectors.

14. A method according to claim 13, wherein processing the matrices is performed by:

applying a singular value decomposition function to the matrices, to yield eigenvectors and associated eigenvalues; and

selecting a group of eigenvectors having the smallest eigenvalues, the orthogonal linear subspace identified by the selected group of