Discriminitive learning for object detection

• US 9,098,741 B1
• Filed: 03/15/2013
• Issued: 08/04/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Toshev, Alexander Toshkov, Anguelov, Dragomir, Ramanan, Deva K., Zhu, Xiangxin
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Moyer, Andrew
• Application Number:
  US13/837,621
• Time in Patent Office: 872 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G06T 2207/20081 Training; Learning
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for object detection are disclosed. Methods can include, for each of a plurality of locations in one or more positive images, image filters are identified, each image filter representing visual features of a location in a positive image (e.g., an image that includes a particular object). Positive location feature scores and negative location feature scores are determined for locations within images. A positive location feature score is based on a similarity between the image filter and feature values for a positive image. A negative location feature score is determined based on a similarity between the image filter and feature values for a negative image. A distinctive location is identified based on the positive and negative location feature scores, and distinguishing feature values for identifying the particular object are identified for the distinctive location.

Claims

1. A method performed by data processing apparatus, the method comprising:

identifying a set of images for a root node of a decision tree, visual characteristics of each image being represented by image feature values for the image, the set of images including one or more positive images that have been deemed to include a particular object and one or more negative images that have been deemed to not include the particular object;

identifying, for each of a plurality of locations in one or more positive images from the set of images, image filters, the image filter for each location representing visual features of the location in positive images;

determining, for each of two or more image locations, a positive location feature score and a negative location feature score, the positive location feature score being determined based on a measure of similarity between the image filter and the positive image feature values for each of two or more different positive images, the negative location feature score being determined based on a measure of similarity between the image filter and the negative image feature values for each of two or more different negative images;

identifying a first distinctive location from the two or more image locations, the first distinctive location being identified based on a difference between the positive location feature score at the first distinctive location and the negative location feature score at the first distinctive location meeting a difference threshold; and

selecting a first set of distinguishing feature values for identifying the particular object based on image feature values for the first distinctive location.

2. The method of claim 1, comprising:

creating a first positive descendent node of the decision tree, the first positive descendent node being created to include a proper subset of the set of images, the proper subset including the images for which image feature values, at the distinctive location, have at least a threshold similarity to the first set of distinctive feature values for the first distinctive location; and

creating a first negative descendent node of the decision tree, the first negative descendent node being created to include a proper subset of the set of images, the proper subset including at least the images not included in the first positive descendent node.

3. The method of claim 2, comprising:

identifying a second set of distinguishing feature values for identifying the particular object, the second set of distinguishing feature values being associated with a second distinctive location of the images; and

creating a second positive descendent node that includes a proper subset of the images from the first positive descendent node, the proper subset included in the second positive descendent node being images having both;

image feature values, at the first distinctive location, that have at least a threshold similarity to the first set of distinctive feature values for the first distinctive location; and

image feature values, at the second distinctive location, that have at least a threshold similarity to the second set of distinguishing features.

4. The method of claim 3, comprising:

receiving a set of image feature values for a candidate image;

determining that image feature values for the first distinctive location of the candidate image match the first set of distinguishing feature values;

determining that image feature value for the second distinctive location of the candidate image match the second set of distinguishing feature values; and

classifying the candidate image as an image of the particular object based, at least in part, on the determination that the first set of distinguishing feature values and the second set of distinguishing feature values are both matched by image feature values for the candidate image.

5. The method of claim 1, comprising initializing a deformable parts mixture model based on the first set of distinguishing feature values.

6. The method of claim 5, wherein initializing the deformable parts mixture model comprises:

identifying the first set of distinguishing feature values as a mixture component for the deformable parts mixture model; and

identifying the first discriminative image location as a reference location for the mixture component.

7. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more data processing apparatus cause the one or more data processing apparatus to perform operations comprising:

identifying a set of images for a root node of a decision tree, visual characteristics of each image being represented by image feature values for the image, the set of images including one or more positive images that have been deemed to include a particular object and one or more negative images that have been deemed to not include the particular object;

identifying, for each of a plurality of locations in one or more positive images from the set of images, image filters, the image filter for each location representing visual features of the location in positive images;

determining, for each of two or more image locations, a positive location feature score and a negative location feature score, the positive location feature score being determined based on a measure of similarity between the image filter and the positive image feature values for each of two or more different positive images, the negative location feature score being determined based on a measure of similarity between the image filter and the negative image feature values for each of two or more different negative images;

identifying a first distinctive location from the two or more image locations, the first distinctive location being identified based on a difference between the positive location feature score at the first distinctive location and the negative location feature score at the first distinctive location meeting a difference threshold; and

selecting a first set of distinguishing feature values for identifying the particular object based on image feature values for the first distinctive location.

8. The computer storage medium of claim 7, wherein the instructions cause one or more the data processing apparatus to perform operations comprising:

creating a first positive descendent node of the decision tree, the first positive descendent node being created to include a proper subset of the set of images, the proper subset including the images for which image feature values, at the distinctive location, have at least a threshold similarity to the first set of distinctive feature values for the first distinctive location; and

creating a first negative descendent node of the decision tree, the first negative descendent node being created to include a proper subset of the set of images, the proper subset including at least the images not included in the first positive descendent node.

9. The computer storage medium of claim 8, wherein the instructions cause one or more the data processing apparatus to perform operations comprising:

identifying a second set of distinguishing feature values for identifying the particular object, the second set of distinguishing feature values being associated with a second distinctive location of the images; and

creating a second positive descendent node that includes a proper subset of the images from the first positive descendent node, the proper subset included in the second positive descendent node being images having both;

image feature values, at the first distinctive location, that have at least a threshold similarity to the first set of distinctive feature values for the first distinctive location; and

image feature values, at the second distinctive location, that have at least a threshold similarity to the second set of distinguishing features.

10. The computer storage medium of claim 9, wherein the instructions cause one or more the data processing apparatus to perform operations comprising:

receiving a set of image feature values for a candidate image;

determining that image feature values for the first distinctive location of the candidate image match the first set of distinguishing feature values;

determining that image feature value for the second distinctive location of the candidate image match the second set of distinguishing feature values; and

classifying the candidate image as an image of the particular object based, at least in part, on the determination that the first set of distinguishing feature values and the second set of distinguishing feature values are both matched by image feature values for the candidate image.

11. The computer storage medium of claim 7, wherein the instructions cause one or more the data processing apparatus to perform operations comprising initializing a deformable parts mixture model based on the first set of distinguishing feature values.

12. The computer storage medium of claim 11, wherein initializing the deformable parts mixture model comprises:

identifying the first set of distinguishing feature values as a mixture component for the deformable parts mixture model; and

identifying the first discriminative image location as a reference location for the mixture component.

13. A system comprising:

a data store storing positive images for a particular object and negative images for the particular object, the positive images being images that have been deemed to include a particular object, the negative images being images that have been deemed to not include the particular object; and

one or more data processing apparatus that interact with the data store and execute instructions that cause the one or more data processing apparatus to perform operations comprising;

identifying, from the data store, a set of images for a root node of a decision tree, visual characteristics of each image being represented by image feature values for the image, the set of images including one or more positive images and one or more negative images;

identifying, for each of a plurality of locations in one or more positive images from the set of images, image filters, the image filter for each location representing visual features of the location in positive images;

determining, for each of two or more image locations, a positive location feature score and a negative location feature score, the positive location feature score being determined based on a measure of similarity between the image filter and the positive image feature values for each of two or more different positive images, the negative location feature score being determined based on a measure of similarity between the image filter and the negative image feature values for each of two or more different negative images;

identifying a first distinctive location from the two or more image locations, the first distinctive location being identified based on a difference between the positive location feature score at the first distinctive location and the negative location feature score at the first distinctive location meeting a difference threshold; and

selecting a first set of distinguishing feature values for identifying the particular object based on image feature values for the first distinctive location.

14. The system of claim 13, wherein the instructions cause one or more the data processing apparatus to perform operations comprising:

creating a first positive descendent node of the decision tree, the first positive descendent node being created to include a proper subset of the set of images, the proper subset including the images for which image feature values, at the distinctive location, have at least a threshold similarity to the first set of distinctive feature values for the first distinctive location; and

creating a first negative descendent node of the decision tree, the first negative descendent node being created to include a proper subset of the set of images, the proper subset including at least the images not included in the first positive descendent node.

15. The system of claim 14, wherein the instructions cause one or more the data processing apparatus to perform operations comprising:

identifying a second set of distinguishing feature values for identifying the particular object, the second set of distinguishing feature values being associated with a second distinctive location of the images; and

creating a second positive descendent node that includes a proper subset of the images from the first positive descendent node, the proper subset included in the second positive descendent node being images having both;

image feature values, at the first distinctive location, that have at least a threshold similarity to the first set of distinctive feature values for the first distinctive location; and

image feature values, at the second distinctive location, that have at least a threshold similarity to the second set of distinguishing features.

16. The system of claim 15, wherein the instructions cause one or more the data processing apparatus to perform operations comprising:

receiving a set of image feature values for a candidate image;

determining that image feature values for the first distinctive location of the candidate image match the first set of distinguishing feature values;

determining that image feature value for the second distinctive location of the candidate image match the second set of distinguishing feature values; and

classifying the candidate image as an image of the particular object based, at least in part, on the determination that the first set of distinguishing feature values and the second set of distinguishing feature values are both matched by image feature values for the candidate image.

17. The system of claim 13, wherein the instructions cause one or more the data processing apparatus to perform operations comprising initializing a deformable parts mixture model based on the first set of distinguishing feature values.

18. The system of claim 17, wherein initializing the deformable parts mixture model comprises:

identifying the first set of distinguishing feature values as a mixture component for the deformable parts mixture model; and

identifying the first discriminative image location as a reference location for the mixture component.