Object finder for two-dimensional images, and system for determining a set of sub-classifiers composing an object finder

• US 20040066966A1
• Filed: 10/07/2002
• Published: 04/08/2004
• Est. Priority Date: 10/07/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Carnegie Mellon University
• Inventors: Schneiderman, Henry
• Granted Patent: US 7,194,114 B2
• Time in Patent Office: Days
• US Class Current: 382/159
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/52 Scale-space analysis, e.g. wavelet analysis multi-scale boundary representations G06V10/42
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

Systems and methods for determining a set of sub-classifiers for a detector of an object detection program are presented. According to one embodiment, the system may include a candidate coefficient-subset creation module, a training module in communication with the candidate coefficient-subset creation module, and a sub-classifier selection module in communication with the training module. The candidate coefficient-subset creation module may create a plurality of candidate subsets of coefficients. The coefficients are the result of a transform operation performed on a two-dimensional (2D) digitized image, and represent corresponding visual information from the 2D image that is localized in space, frequency, and orientation. The training module may train a sub-classifier for each of the plurality of candidate subsets of coefficients. The sub-classifier selection module may select certain of the plurality of sub-classifiers. The selected sub-classifiers may comprise the components of the detector. Also presented are systems and methods for detecting instances of an object in a 2D (two-dimensional) image.

Claims

1. A system for determining a set of sub-classifiers for a detector of an object detection program, comprising:

a candidate coefficient-subset creation module;

a training module in communication with the candidate coefficient-subset creation module; and

a sub-classifier selection module in communication with the training module.

2. The system of claim 1, wherein:

the candidate coefficient-subset creation module is for creating a plurality of candidate subsets of coefficients;

the training module is for training a sub-classifier for each of the plurality of candidate subsets of coefficients; and

the sub-classifier selection module is for selecting certain of the plurality of sub-classifiers.

3. The system of claim 2, wherein the candidate coefficient-subset creation module is for creating a plurality of candidate subsets of coefficients that are statistically related.

4. The system of claim 2, wherein the candidate coefficient-subset creation module is for creating a plurality of candidate subsets of wavelet coefficients that are statistically related.

5. The system of claim 2, wherein the candidate coefficient-subset creation module is for creating a plurality of candidate subsets of coefficients by:

selecting a plurality of subsets of statistically related coefficients based on a statistical relationship between groups of two coefficients in the subsets;

selecting a first subset of coefficients from the plurality of subsets of coefficients based on a first criterion;

computing a second criterion based on the first criterion and the first subset; and

selecting a second subset of coefficients from the plurality of subsets of coefficients based on the second criterion.

6. The system of claim 2, wherein the sub-classifier selection module is for selecting certain of the plurality of sub-classifiers by:

performing a first test on the plurality of sub-classifiers;

selecting a first set of sub-classifiers based on the first test;

performing a second test on the first set of sub-classifiers; and

selecting a second set of sub-classifiers from the first set based on the second test.

7. The system of claim 6, wherein the first test is less computationally intensive than the second set.

8. The system of claim 2, wherein the training module is for training the set of sub-classifiers based on non-object training examples.

9. The system of claim 8, wherein the non-object training examples include non-object training examples selected by bootstrapping and non-object training examples selected randomly.

10. A system for determining a set of sub-classifiers for a detector of an object detection program, comprising:

means for creating a plurality of candidate subsets of coefficients;

means for training a sub-classifier for each of the plurality of candidate subsets of coefficients; and

means for selecting certain of the plurality of sub-classifiers.

11. The system of claim 10, wherein the means for creating a plurality of candidate subsets of coefficients includes means for creating a plurality of candidate subsets of coefficients that are statistically related.

12. The system of claim 10, wherein the means for creating a plurality of candidate subsets of coefficients includes means for creating a plurality of candidate subsets of wavelet coefficients that are statistically related.

13. The system of claim 10, wherein the means for selecting certain of the plurality of candidate subsets of coefficients includes means for:

selecting a plurality of subsets of statistically related coefficients based on a statistical relationship between groups of two coefficients in the subsets;

selecting a first subset of coefficients from the plurality of subsets of coefficients based on a first criterion;

computing a second criterion based on the first criterion and the first subset; and

selecting a second subset of coefficients from the plurality of subsets of coefficients based on the second criterion.

14. The system of claim 10, wherein the means for selecting certain of the plurality of candidate sub-classifiers of coefficients includes means for:

performing a first test on the plurality of sub-classifiers;

selecting a first set of sub-classifiers based on the first test;

performing a second test on the first set of sub-classifiers; and

selecting a second set of sub-classifiers from the first set based on the second test.

15. The system of claim 14, wherein the first test is less computationally intensive than the second test.

16. The system of claim 10, wherein the means for training includes means for training the set of sub-classifiers based on non-object training examples.

17. The system of claim 16, wherein the non-object training examples include non-object training examples selected by bootstrapping and non-object training examples selected randomly.

18. A computer readable medium having stored thereon instructions, which, when executed by a processor, cause the processor to:

create a plurality of candidate subsets of coefficients;

train a sub-classifier for a detector of an object detection program for each of the plurality of candidate subsets of coefficients; and

select certain of the plurality of sub-classifiers.

19. The medium of claim 18, having further stored thereon instructions which when executed by the processor, cause the processor to create a plurality of candidate subsets of coefficients that are statistically related.

20. The medium of claim 18, having further stored thereon instructions which when executed by the processor, cause the processor to create a plurality of candidate subsets of wavelet coefficients that are statistically related.

21. The medium of claim 18, having further stored thereon instructions which when executed by the processor, cause the processor to create a plurality of candidate subsets of coefficients by:

selecting a plurality of subsets of statistically related coefficients based on a statistical relationship between groups of two coefficients in the subsets;

selecting a first subset of coefficients from the plurality of subsets of coefficients based on a first criterion;

computing a second criterion based on the first criterion and the first subset; and

selecting a second subset of coefficients from the plurality of subsets of coefficients based on the second criterion.

22. The medium of claim 18, having further stored thereon instructions which when executed by the processor, cause the processor to select certain of the plurality of sub-classifiers by:

performing a first test on the plurality of sub-classifiers;

selecting a first set of sub-classifiers based on the first test;

performing a second test on the first set of sub-classifiers; and

selecting a second set of sub-classifiers from the first set based on the second test.

23. The medium of claim 22, wherein the first test is less computationally intensive than the second set.

24. The medium of claim 18, having further stored thereon instructions which when executed by the processor cause the processor to train the set of sub-classifiers based on non-object training examples.

25. The medium of claim 24, having further stored thereon instructions which when executed by the processor cause the processor to select the non-object training examples by bootstrapping and randomly.

26. A method for determining a set of sub-classifiers for a detector of an object detection program, comprising:

creating a plurality of candidate subsets of coefficients;

training a sub-classifier for each of the plurality of candidate subsets of coefficients; and

selecting certain of the plurality of sub-classifiers.

27. The method of claim 26, wherein creating a plurality of candidate subsets of coefficients includes creating a plurality of candidate subsets of coefficients that are statistically related.

28. The method of claim 26, wherein creating a plurality of candidate subset of coefficients includes creating a plurality of candidate subsets of wavelet coefficients that are statistically related.

29. The method of claim 26, wherein creating a plurality of candidate subset of coefficients includes:

selecting a plurality of subsets of statistically related coefficients based on a statistical relationship between groups of two coefficients in the subsets;

selecting a first subset of coefficients from the plurality of subsets of coefficients based on a first criterion;

computing a second criterion based on the first criterion and the first subset; and

selecting a second subset of coefficients from the plurality of subsets of coefficients based on the second criterion.

30. The method of claim 26, wherein selecting certain of the plurality of sub-classifiers includes:

performing a first test on the plurality of sub-classifiers;

selecting a first set of sub-classifiers based on the first test;

performing a second test on the first set of sub-classifiers; and

selecting a second set of sub-classifiers from the first set based on the second test.

31. The method of claim 30, wherein the first test is less computationally intensive than the second set.

32. The method of claim 26, wherein training a sub-classifier for each of the plurality of candidate subsets of coefficients includes providing lighting correction after evaluation of an overcomplete wavelet transformation.

33. The method of claim 26, wherein training includes training the set of sub-classifiers based on non-object training examples.

34. The method of claim 33, wherein the non-object training examples include non-object training examples selected by bootstrapping and non-object training examples selected randomly.

35. A method for detecting instances of an object in a 2D (two-dimensional) image, the method comprising:

for each of a plurality of view-based classifiers, computing a transform of a digitized version of the 2D image containing a representation of an object, wherein the transform includes a representation of the spatial frequency content of the image as a function of position in the image, and wherein the transform generates a plurality of transform coefficients, and wherein each transform coefficient represents corresponding visual information from the 2D image that is localized in space, frequency, and orientation;

applying the plurality of view-based classifiers to the plurality of transform coefficients, wherein each view-based classifier is configured to detect a specific orientation of the object in the 2D image based on visual information received from corresponding transform coefficients, and wherein each of the plurality of view-based classifiers includes a plurality of cascaded sub-classifiers;

combining results of the application of the plurality view-based classifiers; and

determining a pose of an instance of the object from the combination of results of the application of the plurality view-based classifiers.

36. The method of claim 35, further comprising sampling each of a predetermined number of transform coefficients.

37. The method of claim 35, wherein applying the plurality of view-based classifiers to the plurality of transform coefficients further comprises linearly projecting each of a predetermined number of transform coefficients to a smaller number of projection coefficients.

38. The method of claim 35, wherein applying the plurality of view-based classifiers to the plurality of transform coefficients further comprises quantizing coefficients to one of a set of discrete values.

39. The method of claim 35, wherein applying the plurality of view-based classifiers includes applying the plurality of cascaded sub-classifiers in a series of detector stages, wherein each of the detector stages includes at least one sub-classifier.

40. The method of claim 39, wherein a first detector stage includes fewer sub-classifiers than a second detector stage.

41. The method of claim 40, wherein a first detector stage includes one sub-classifier.

42. The method of claim 40, wherein the first detector stage considers fewer coefficients than the second detector stage.

43. The method of claim 42, wherein the second detector stage considers fewer coefficients than a third detector stage.

44. The method of claim 35, wherein computing the transform includes computing a wavelet transform.

45. The method of claim 35, further comprising providing lighting correction adjustments to the transform coefficients prior to applying the plurality of view-based classifiers.

46. A computer-readable storage medium having stored thereon instructions, which, when executed by a processor, cause the processor to perform the following:

for each of a plurality of view-based classifiers, compute a transform of a digitized version of a 2D image containing a representation of an object, wherein the transform includes a representation of the spatial frequency content of the image as a function of position in the image, and wherein the transform generates a plurality of transform coefficients, and wherein each transform coefficient represents corresponding visual information from the 2D image that is localized in space, frequency, and orientation;

apply a plurality of view-based classifiers to the plurality of transform coefficients wherein each view-based classifier is configured to detect a specific orientation of the object in the 2D image based on visual information received from corresponding transform coefficients, and wherein each of the plurality of view-based classifiers include a plurality of cascaded sub-classifiers; and

combine results of the application of the plurality of view-based classifiers; and

determine a pose of an instance of the object from the combination of results of the application of the plurality view-based classifiers.

47. The computer-readable storage medium of claim 46 having stored thereon instructions, which, when executed by the processor, cause the processor to display the 2D image with a visual marker placed where the presence of the instance of the object is estimated.

48. The computer-readable storage medium of claim 46 having stored thereon instructions, which, when executed by the processor, cause the processor to store the pose of the instance of the object.

49. The computer-readable storage medium of claim 46 wherein the transform is a wavelet transform.

50. The computer-readable storage medium of claim 46, having further stored thereon instructions, which, when executed by the processor, cause the processor to provide lighting correction adjustments to the transform coefficients prior to applying the plurality of view-based classifiers.

51. A computer system, which, upon being programmed, is configured to perform the following:

for each of a plurality of view-based classifiers, compute a transform of a digitized version of a 2D image containing a representation of an object, wherein the transform includes a representation of the spatial frequency content of the image as a function of position in the image, and wherein the transform generates a plurality of transform coefficients, and wherein each transform coefficient represents corresponding visual information from the 2D image that is localized in space, frequency, and orientation;

apply the plurality view-based classifiers to the plurality of transform coefficients, wherein each view-based classifier is configured to detect a specific orientation of the object in the 2D image based on visual information received from corresponding transform coefficients, and wherein each of the series of detector stages includes a plurality of cascaded sub-classifiers combine results of the application of the plurality view-based classifiers; and

determine a pose of the object from the combination of results of application of the plurality of view-based classifiers.

52. The computer system of claim 51, which, upon being programmed, is further configured to perform the following:

establish a communication link with a client computer over a communication network;

receive the digitized version of the 2D image from the client computer over the communication network;

determine the orientation and location of an instance of the object in the 2D image received from the client computer; and

send a notification of the orientation and location of the instance of the object to the client computer over the communication network.

53. The computer system of claim 52, wherein the transform is a wavelet transform.

54. The computer system of claim 51, which, upon being programmed, is further configured to provide lighting correction adjustments to the transform coefficients prior to applying the plurality of view-based classifiers.

55. A method of generating a sub-classifier for a detector of an object detection program, comprising:

transforming pixel values to wavelet coefficients;

linearly projecting the wavelet coefficients to create projection coefficients;

quantizing the projection coefficients; and

generating a table of log-likelihood values based on the quantizing.

56. The method of claim 55, further comprising providing lighting correction adjustments to the wavelet coefficients prior to linearly projecting the wavelet coefficients.