Training an attentional cascade

• US 8,352,395 B1
• Filed: 10/21/2008
• Issued: 01/08/2013
• Est. Priority Date: 07/22/2004
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Brandt, Jonathan
• Primary Examiner(s): Starks, Wilbert L
• Application Number:
  US12/255,560
• Time in Patent Office: 1,540 Days
• Field of Search: 706/45
• US Class Current: 706/45
• CPC Class Codes: G06N 3/08 Learning methods

Abstract

Methods and apparatus, including computer program products, implementing techniques for training an attentional cascade. An attentional cascade is an ordered sequence of detector functions, where the detector functions are functions that examine a target image and return a positive result if the target image resembles an object of interest and a negative result if the target image does not resemble the object of interest. A positive result from one detector function leads to consideration of the target image by the next detector function, and a negative result from any detector function leads to rejection of the target image. The techniques include training each detector function in the attentional cascade in sequence starting with the first detector function. Training a detector function includes selecting a counter-example set. Selecting a counter-example set includes selecting only images that are at least a minimum difference from an example set.

Claims

1. A system comprising:

one or more processors configured to perform operations including;

training an attentional cascade, the attentional cascade being an ordered sequence of detector functions recorded on a machine-readable storage device, the detector functions being functions that when executed by a computer, examine a target image and return a positive result if the target image resembles an object of interest and a negative result if the target image does not resemble the object of interest, where a positive result from one detector function leads to consideration of the target image by the next detector function and a negative result from any detector function leads to rejection of the target image, wherein training the attentional cascade includes;

training each detector function in sequence starting with the first detector function, wherein training each detector function includes;

selecting a counter-example set, the counter-example set including images not resembling the object of interest, wherein selecting the counter-example set includes selecting only images that are at least a minimum difference from an example set of images, the example set including images resembling the object of interest, and where the minimum difference is specified for a distance metric for approximating a distance between particular images and images of the example set of images; and

training the detector function using only the example set and the counter-example set.

2. The system of claim 1, wherein selecting the counter-example set includes selecting only images that received a positive result from previous detector functions.

3. The system of claim 1, wherein selecting only images that are at least the minimum difference includes approximating the distance between the example set and images chosen from a universe of counter-examples.

4. The system of claim 3, wherein approximating the distance includes using a Euclidean distance.

5. The system of claim 4, wherein approximating the distance includes using a subspace determined through statistical analysis of the example set.

6. The system of claim 3, wherein approximating the distance includes using a geodesic arc length or angle metric.

7. The system of claim 6, wherein approximating the distance includes using a subspace determined through statistical analysis of the example set.

8. The system of claim 3, wherein approximating the distance includes using a Mahalanobis distance.

9. The system of claim 8, wherein approximating the distance includes using a subspace determined through statistical analysis of the example set.

10. The product of claim 3, wherein approximating the distance includes using the closest element in the example set to find the distance between the example set and images in the universe of counter-examples.

11. The system of claim 3, wherein approximating the distance includes using a clustering algorithm to partition the example set and using the nearest cluster to find distance between the example set and images in the universe of counter-examples.

12. The system of claim 11, wherein approximating the distance includes computing the centroid and the covariance of each cluster and using these statistics to compute the Mahalanobis distance to the cluster.

13. The system of claim 3, wherein selecting images that are at least the minimum difference includes creating a histogram of the distances between the example set and images chosen from the universe of counter-examples and calculating a minimum distance using statistical analysis of the distances.

14. The system of claim 3, wherein selecting images that are at least the minimum difference includes sorting images chosen from the universe of counter-examples according to their distance from the example set and calculating a minimum distance using statistical analysis of the distances.

15. The system of claim 3, where the universe of counter-examples includes only images not resembling the object of interest.

16. The system of claim 3, where the universe of counter-examples includes images resembling the object of interest.

17. The system of claim 1, wherein the target image is a portion of a larger image.

18. The system of claim 1, wherein the operations further comprise:

receiving a plurality of images;

receiving user input requesting identification of images within the plurality of images that contain the object of interest; and

performing the requested object detection using the trained attentional cascade.

19. The system of claim 1, where the minimum difference is greater for detector functions early in the sequence than for detector functions later in the sequence.

20. A system comprising:

one or more processors configured to perform operations including;

receiving an attentional cascade, the attentional cascade being an ordered sequence of detector functions recorded on a machine-readable storage device, the detector functions being functions that when executed by a computer examine a target image and return a positive result if the target image is a member of a category of objects and a negative result if the target image is not a member of the category of objects, where a positive result from one detector function leads to consideration of the target image by the next detector function and a negative result from any detector function leads to rejection of the target image; and

further training the received attentional cascade to identify specific objects of interest within the category of objects to generate a trained attentional cascade, the trained attentional cascade being an ordered sequence of detector functions that when executed by a computer examine a target image and return a positive result if the target image is one of the specific objects of interest within the category of objects and a negative result if the target image is not one of the specific objects of interest within the category of objects.

21. The system of claim 20, where further training the attentional cascade includes receiving a counter-example set, the counter-example set including images not resembling the specific objects of interest, and training the detector functions using only the example set and the counter-example set, the example set including images resembling the specific objects of interest.

22. A method comprising:

training an attentional cascade, the attentional cascade being an ordered sequence of detector functions recorded on a machine-readable storage device, the detector functions being functions that when executed by a computer examine a target image and return a positive result if the target image resembles an object of interest and a negative result if the target image does not resemble the object of interest, where a positive result from one detector function leads to consideration of the target image by the next detector function and a negative result from any detector function leads to rejection of the target image, wherein training the attentional cascade includes;

training each detector function in sequence starting with the first detector function, wherein training each detector function includes;

selecting a counter-example set, the counter-example set including images not resembling the object of interest, wherein selecting the counter-example set includes selecting only images that are at least a minimum difference from an example set of images, the example set including images resembling the object of interest, and where the minimum difference is specified for a distance metric for approximating a distance between particular images and images of the example set of images; and

training the detector function using only the example set and the counter-example set.

23. The method of claim 22, wherein selecting the counter-example set includes selecting only images that received a positive result from previous detector functions.

24. The method of claim 22, wherein selecting only images that are at least the minimum difference includes approximating the distance between the example set and images chosen from a universe of counter-examples.

25. The method of claim 24, wherein approximating the distance includes using a Euclidean distance.

26. The method of claim 25, wherein approximating the distance includes using a subspace determined through statistical analysis of the example set.

27. The method of claim 24, wherein approximating the distance includes using a geodesic arc length or angle metric.

28. The method of claim 27, wherein approximating the distance includes using a subspace determined through statistical analysis of the example set.

29. The method of claim 24, wherein approximating the distance includes using a Mahalanobis distance.

30. The method of claim 29, wherein approximating the distance includes using a subspace determined through statistical analysis of the example set.

31. The method of claim 24, wherein approximating the distance includes using the closest element in the example set to find the distance between the example set and images in the universe of counter-examples.

32. The method of claim 24, wherein approximating the distance includes using a clustering algorithm to partition the example set and using the nearest cluster to find distance between the example set and images in the universe of counter-examples.

33. The method of claim 32, wherein approximating the distance includes computing the centroid and the covariance of each cluster and using these statistics to compute the Mahalanobis distance to the cluster.

34. The method of claim 24, wherein selecting images that are at least the minimum difference includes creating a histogram of the distances between the example set and images chosen from the universe of counter-examples and calculating a minimum distance using statistical analysis of the distances.

35. The method of claim 24, wherein selecting images that are at least the minimum difference includes sorting images chosen from the universe of counter-examples according to their distance from the example set and calculating a minimum distance using statistical analysis of the distances.

36. The method of claim 24, where the universe of counter-examples includes only images not resembling the object of interest.

37. The method of claim 24, where the universe of counter-examples includes images resembling the object of interest.

38. The method of claim 22, wherein the target image is a portion of a larger image.

39. The method of claim 22, wherein the operations further comprise:

receiving a plurality of images;

receiving user input requesting identification of images within the plurality of images that contain the object of interest; and

performing the requested object detection using the trained attentional cascade.

40. The method of claim 22, where the minimum difference is greater for detector functions early in the sequence than for detector functions later in the sequence.

41. A method comprising:

receiving an attentional cascade, the attentional cascade being an ordered sequence of detector functions recorded on a machine-readable storage device, the detector functions being functions that when executed by a computer, examine a target image and return a positive result if the target image is a member of a category of objects and a negative result if the target image is not a member of the category of objects, where a positive result from one detector function leads to consideration of the target image by the next detector function and a negative result from any detector function leads to rejection of the target image; and

further training the received attentional cascade to identify specific objects of interest within the category of objects to generate a trained attentional cascade, the trained attentional cascade being an ordered sequence of detector functions that when executed by a computer examine a target image and return a positive result if the target image is one of the specific objects of interest within the category of objects and a negative result if the target image is not one of the specific objects of interest within the category of objects.

42. The method of claim 41, where further training the attentional cascade includes receiving a counter-example set, the counter-example set including images not resembling the specific objects of interest, and training the detector functions using only the example set and the counter-example set, the example set including images resembling the specific objects of interest.