Automatic classification of objects within images

• US 7,813,561 B2
• Filed: 08/14/2006
• Issued: 10/12/2010
• Est. Priority Date: 08/14/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Hua, Jia, Menglei, Ma, Wei-Ying, Chen, Zheng, Xie, Xing
• Primary Examiner(s): Bella; Matthew C
• Assistant Examiner(s): Rush; Eric
• Application Number:
  US11/464,410
• Publication Number:
  US 20080037877A1
• Time in Patent Office: 1,520 Days
• Field of Search: 382224-228
• US Class Current: 382/225
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

A system for automatically classifying an object of a target image is provided. A classification system provides a collection of classified images along with a classification of the dominant object of the image. The classification system attempts to classify the object of a target image based on similarity of the target image to the classified images. To classify a target image, the classification system identifies the classified images of the collection that are most similar to the target image based on similarity between salient points of the target image and the classified images. The classification system selects a classification associated with the classified images that are most similar to the target image as a classification for the object of the target image.

Claims

1. A method in a computing device for classifying an object of a target image, the method comprising:

providing classified images and an associated classification for each classified image, the associated classification indicating a classification of an object represented by the classified image, each classified image being represented by feature vectors of salient points of the image;

providing a plurality of clusters of the salient points of the classified images, each cluster having salient points of a plurality of classified images whose feature vectors are within a threshold similarity of a representative feature vector of the cluster, each cluster having a mapping of each salient point of the cluster to the classified image that contains that salient point; and

after the clusters have been provided,

identifying target salient points of the target image;

generating a target feature vector for each target salient point;

identifying candidate images by, for each target salient point;

selecting the cluster whose salient points are most similar to the target salient point as indicated by a minimum distance between a feature vector of a salient point of the cluster and the target feature vector;

identifying near salient points of the selected cluster whose distance between the feature vector of the salient point and the target feature vector is below a threshold; and

marking images that contain the identified near salient points as candidate images;

identifying classified images that are most similar to the target image by

calculating a similarity between each candidate image and the target image based on similarity between feature vectors of salient points of the candidate image and the target feature vectors;

discarding candidate images whose calculated similarity does not satisfy a threshold similarity; and

after discarding the candidate images, filtering out candidate images whose arrangement of salient points is inconsistent with corresponding target salient points wherein the remaining candidate images are the identified classified images; and

selecting a classification for the object of the target image based on the classifications of the identified classified images.

2. The method of claim 1 wherein each salient point is identified using a difference of Gaussian technique and represented by a feature vector.

3. The method of claim 1 wherein the mapping is generated using a clustering technique.

4. The method of claim 3 wherein the clustering technique is based on a growing cell structures algorithm.

5. The method of claim 1 wherein the similarity is calculated according to the following equation:

6. The method of claim 1 including filtering out a matching image when an arrangement between its matching salient points and an arrangement of the corresponding similar salient points of the target image are inconsistent.

7. The method of claim 6 wherein the filtering out includes applying a RANSAC-based algorithm.

8. A computer system for classifying an object of a target image, comprising:

a classified images store containing classified images of objects and classifications of the objects;

a memory storing computer-executable instructions of

a component that generates an index that maps each salient point of the classified images to the classified image that contains that salient point;

a component that generates clusters of salient points of the classified images whose feature vectors are similar, each cluster having salient points of a plurality of classified images whose feature vectors are within a threshold similarity of a representative feature vector of the cluster;

a component that, after the clusters are generated, generates target feature vectors for target salient points of the target image;

a component that identifies, from the generated index, classified images that match the target image based on similarity between the target feature vectors of the target salient points of the target image and feature vectors of the salient points of the classified images by, for each target salient point,

identifying a cluster whose salient points have feature vectors that are most similar to the target feature vector of the target salient point;

identifying as candidate images those images that contain a salient point of the identified cluster and that are most similar to the target image based on the feature vectors of salient points of the images and the target feature vectors; and

discarding identified candidate images whose arrangement of salient points is inconsistent with an arrangement of the target salient points, wherein the not discarded candidate images are the matching classified images; and

a component that classifies the object of the target image based on the classifications of the matching classified images; and

a processor for executing the computer-executable instructions stored in the memory.

9. The computer system of claim 8 wherein the salient points are identified using a difference of Gaussian algorithm.

10. The computer system of claim 8 wherein the clusters are identified using a growing cell structures algorithm.

11. The computer system of claim 8 wherein the component that identifies classified images that match includes a component that discards matching images whose similarity is not within a threshold similarity.

12. The computer system of claim 8 wherein the component that classifies the object of the target image selects the classification of a matching classified image based on number of similar salient points.

13. A computer-readable storage medium that is not a signal containing instructions for controlling a computing device to classify an object of a target image, by a method comprising:

providing an index that maps feature vectors for salient points of classified images to the classified images and their classifications;

providing a plurality of clusters of the salient points of the classified images, each cluster having salient points of a plurality of classified images whose feature vectors are within a threshold similarity of a representative feature vector of the cluster, each cluster having a mapping of each salient point of the cluster to the classified image that contains that salient point; and

after the clusters are provided,

generating target feature vectors for target salient points of the target image;

identifying, from the provided index, classified images that match the target image based on similarity between the target feature vectors of the target salient points of the target image and the feature vectors of salient points of the classified images by identifying clusters whose salient points have feature vectors that are similar to the target feature vectors and identifying as matching images the images that contain the salient points of the identified clusters and that are most similar to the target image; and

selecting a classification for the object of the target image based on the classifications of the matching classified images.

14. The computer-readable storage medium of claim 13 wherein the identifying of classified images that match includes calculating a similarity between the target image and the matching classified images based on similar target salient points of the target image and the matching classified images.

15. The computer-readable storage medium of claim 14 wherein the selecting of a classification includes selecting a dominant classification of the matching classified images.