Detecting objects in images using a soft cascade

• US 7,634,142 B1
• Filed: 01/24/2005
• Issued: 12/15/2009
• Est. Priority Date: 01/24/2005
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Bourdev, Lubomir D., Brandt, Jonathan
• Primary Examiner(s): Strege; John B
• Application Number:
  US11/042,942
• Time in Patent Office: 1,786 Days
• Field of Search: 382/118, 382/224, 382/228, 382/181
• US Class Current: 382/224
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers

Abstract

Systems, methods, and computer program products, implementing techniques for detecting objects using a soft cascade. The techniques include receiving a digital data segment and determining whether the digital data segment resembles an object of interest by passing the digital data segment through a cascade. The cascade includes an ordered sequence of stages and a rejection function after each stage that determines whether to reject the digital data segment at the current stage as not resembling the object of interest, or to allow the digital data segment to pass to the next stage of evaluation. The rejection function allows the digital data segment to fail the current stage and still pass to the next stage.

Claims

1. A computer program product, tangibly stored on a computer-readable medium, the computer program product comprising instructions operable to cause a programmable processor to perform operations comprising:

receiving a digital data segment; and

determining whether the digital data segment resembles an object of interest by passing the digital data segment through a cascade, the cascade including an ordered sequence of stages and a rejection function after each stage that determines whether to reject the digital data segment at a current stage as not resembling the object of interest, or to allow the digital data segment to pass to the next stage of evaluation, wherein the rejection function uses output from the current stage to determine whether to reject the digital data segment, wherein the output from the current stage is based upon an amount by which the digital data segment passed or failed the current stage, and wherein the rejection function allows the digital data segment to fail the current stage and still pass to the next stage.

2. The computer program product of claim 1, wherein:

the rejection function further uses output from one or more prior stages to determine whether to reject the digital data segment.

3. The computer program product of claim 2, wherein:

the rejection function computes a sum of the outputs from the current stage and the one or more prior stages and compares the sum against a threshold value.

4. The computer program product of claim 1, wherein:

each stage outputs a scalar value.

5. The computer program product of claim 4, wherein:

the scalar value is proportional to how important the stage is and an amount by which the digital data segment passed or failed the stage.

6. The computer program product of claim 1, further comprising:

receiving user input specifying a target accuracy or speed; and

calibrating the cascade to operate at the target accuracy or speed.

7. The computer program product of claim 6, wherein:

the target accuracy is specified as a false positive rate, a detection rate, or both.

8. The computer program product of claim 6, wherein:

calibrating the cascade includes determining an ordering for the stages of the cascade, and determining a rejection threshold to be used by the rejection function after each stage of the cascade.

9. The computer program product of claim 8, wherein the stages are ordered based on speed.

10. The computer program product of claim 8, wherein the stages are ordered based on detection rate.

11. The computer program product of claim 8, wherein the rejection threshold is selected to match a target detection rate or false positive rate.

12. The computer program product of claim 6, wherein calibrating the cascade is an iterative process that includes:

a first iteration where all stages of the cascade are tested against a calibration set of positive digital data segments and negative digital data segments, the positive digital data segments being digital data segments corresponding to the object of interest, the negative digital data segments being digital data segments not corresponding to the object of interest, and one of the stages is selected to be the first stage of the cascade; and

one or more subsequent iterations where the remaining, unselected stages of the cascade are tested against the calibration set and another one of the stages is selected to be the next stage of the cascade.

13. The computer program product of claim 12, wherein the calibration process further includes:

during each iteration of the calibration process, adding additional negative digital data segments to the calibration set.

14. The computer program product of claim 12, wherein the calibration process further includes:

prior to the first iteration of the calibration, compiling a set of additional negative digital data segments, adding the set of additional negative digital data segments to the calibration set to form an extended calibration set, and using the extended calibration set for all iterations of the calibration.

15. The computer program product of claim 14, wherein the calibration process further includes:

assigning a weight to each of the additional negative digital data segments.

16. The computer program product of claim 1, wherein the digital data segment is an image.

17. A computer-implemented method comprising:

receiving a digital data segment;

determining whether the digital data segment resembles an object of interest by passing the digital data segment through a cascade, the cascade including an ordered sequence of stages and a rejection function after each stage that determines whether to reject the digital data segment at a current stage as not resembling the object of interest, or to allow the digital data segment to pass to the next stage of evaluation, wherein the rejection function uses output from the current stage to determine whether to reject the digital data segment, wherein the output from the current stage is based upon an amount by which the digital data segment passed or failed the current stage, and wherein the rejection function allows the digital data segment to fail the current stage and still pass to the next stage; and

wherein the determining is performed by one or more processors.

18. The computer-implemented method of claim 17, wherein:

the rejection function further uses output from one or more prior stages to determine whether to reject the digital data segment.

19. The computer-implemented method of claim 18, wherein:

the rejection function computes a sum of the outputs from the current stage and the one or more prior stages and compares the sum against a threshold value.

20. The computer-implemented method of claim 17, wherein:

each stage outputs a scalar value.

21. The computer-implemented method of claim 20, wherein:

the scalar value is proportional to how important the stage is and an amount by which the digital data segment passed or failed the stage.

22. The computer-implemented method of claim 17, further comprising:

receiving user input specifying a target accuracy or speed; and

calibrating the cascade to operate at the target accuracy or speed.

23. The computer-implemented method of claim 22, wherein:

the target accuracy is specified as a false positive rate, a detection rate, or both.

24. The computer-implemented method of claim 22, wherein:

calibrating the cascade includes determining an ordering for the stages of the cascade, and determining a rejection threshold to be used by the rejection function after each stage of the cascade.

25. The computer-implemented method of claim 24, wherein the stages are ordered based on speed.

26. The computer-implemented method of claim 24, wherein the stages are ordered based on detection rate.

27. The computer-implemented method of claim 24, wherein the rejection threshold is selected to match a target detection rate or false positive rate.

28. The computer-implemented method of claim 22, wherein calibrating the cascade is an iterative process that includes:

a first iteration where all stages of the cascade are tested against a calibration set of positive digital data segments and negative digital data segments, the positive digital data segments being digital data segments corresponding to the object of interest, the negative digital data segments being digital data segments not corresponding to the object of interest, and one of the stages is selected to be the first stage of the cascade; and

one or more subsequent iterations where the remaining, unselected stages of the cascade are tested against the calibration set and another one of the stages is selected to be the next stage of the cascade.

29. The computer-implemented method of claim 28, wherein the calibration process further includes:

during each iteration of the calibration process, adding additional negative digital data segments to the calibration set.

30. The computer-implemented method of claim 28, wherein the calibration process further includes:

prior to the first iteration of the calibration, compiling a set of additional negative digital data segments, adding the set of additional negative digital data segments to the calibration set to form an extended calibration set, and using the extended calibration set for all iterations of the calibration.

31. The computer-implemented method of claim 30, wherein the calibration process further includes:

assigning a weight to each of the additional negative digital data segments.

32. The computer-implemented method of claim 17, wherein the digital data segment is an image.

33. A system comprising:

one or more processors; and

a machine-readable storage device, comprising instructions operable to cause the one or more processors to perform the following operations;

receiving a digital data segment; and

determining whether the digital data segment resembles an object of interest by passing the digital data segment through a cascade, the cascade including an ordered sequence of stages and a rejection function after each stage that determines whether to reject the digital data segment at a current stage as not resembling the object of interest, or to allow the digital data segment to pass to the next stage of evaluation, wherein the rejection function uses output from the current stage to determine whether to reject the digital data segment, wherein the output from the current stage is based upon an amount by which the digital data segment passed or failed the current stage, and wherein the rejection function allows the digital data segment to fail the current stage and still pass to the next stage.

34. The system of claim 33, wherein:

the rejection function further uses output from one or more prior stages to determine whether to reject the digital data segment.

35. The system of claim 34, wherein:

the rejection function computes a sum of the outputs from the current stage and the one or more prior stages and compares the sum against a threshold value.

36. The system of claim 33, wherein:

each stage outputs a scalar value.

37. The system of claim 36, wherein:

the scalar value is proportional to how important the stage is and an amount by which the digital data segment passed or failed the stage.

38. The system of claim 33, further operable to perform operations comprising:

receiving user input specifying a target accuracy or speed; and

calibrating the cascade to operate at the target accuracy or speed.

39. The system of claim 38, wherein:

the target accuracy is specified as a false positive rate, a detection rate, or both.

40. The system of claim 38, wherein:

calibrating the cascade includes determining an ordering for the stages of the cascade, and determining a rejection threshold to be used by the rejection function after each stage of the cascade.

41. The system of claim 40, wherein the stages are ordered based on speed.

42. The system of claim 40, wherein the stages are ordered based on detection rate.

43. The system of claim 40, wherein the rejection threshold is selected to match a target detection rate or false positive rate.

44. The system of claim 38, wherein calibrating the cascade is an iterative process that includes:

a first iteration where all stages of the cascade are tested against a calibration set of positive digital data segments and negative digital data segments, the positive digital data segments being digital data segments corresponding to the object of interest, the negative digital data segments being digital data segments not corresponding to the object of interest, and one of the stages is selected to be the first stage of the cascade; and

one or more subsequent iterations where the remaining, unselected stages of the cascade are tested against the calibration set and another one of the stages is selected to be the next stage of the cascade.

45. The system of claim 44, wherein the calibration process further includes:

during each iteration of the calibration process, adding additional negative digital data segments to the calibration set.

46. The system of claim 44, wherein the calibration process further includes:

prior to the first iteration of the calibration, compiling a set of additional negative digital data segments, adding the set of additional negative digital data segments to the calibration set to form an extended calibration set, and using the extended calibration set for all iterations of the calibration.

47. The system of claim 46, wherein the calibration process further includes:

assigning a weight to each of the additional negative digital data segments.

48. The system of claim 33, wherein the digital data segment is an image.