Detecting an object within an image by incrementally evaluating subwindows of the image in parallel

• US 7,738,680 B1
• Filed: 11/24/2004
• Issued: 06/15/2010
• Est. Priority Date: 11/24/2004
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Bourdev, Lubomir D.
• Primary Examiner(s): Dang; Duy M
• Application Number:
  US10/997,448
• Time in Patent Office: 2,029 Days
• Field of Search: 382/103, 382/150, 382/173, 382/205, 382/225, 382/176, 382/190, 348/169
• US Class Current: 382/103
• CPC Class Codes: G06F 18/217 Validation; Performance evaluation; Active pattern learning techniques
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/776 Validation; Performance evaluation

Abstract

One embodiment of the present invention provides a system for detecting an occurrence of an object in an image. During operation, the system selects a subwindow to be evaluated based upon a currently estimated likelihood of the object being detected within the subwindow. The system then performs an evaluation step on the subwindow to determine if the object exists in the subwindow, wherein performing the evaluation step involves updating the currently estimated likelihood of the object being detected in the subwindow. If evaluation of the subwindow is not complete after performing the evaluation step, the system stores information associated with the subwindow to facilitate subsequent evaluation of the subwindow.

Claims

1. A method for detecting an object in an image, comprising:

using a computer to perform;

selecting a subwindow to be evaluated based upon a currently estimated likelihood of the object being detected within the subwindow;

performing an evaluation step on the subwindow to determine if the object exists in the subwindow, wherein performing the evaluation step comprises updating the currently estimated likelihood of the object being detected in the subwindow; and

if evaluation of the subwindow is not complete after the evaluation step,

storing information associated with the subwindow to facilitate subsequent evaluation of the subwindow.

2. The method of claim 1, wherein storing the information associated with the subwindow comprises updating and storing the currently estimated likelihood of the object being detected within the subwindow.

3. The method of claim 2, wherein storing the information associated with the subwindow comprises:

storing the subwindow itself or location information for the subwindow; and

storing intermediate results, if any, associated with evaluation of the subwindow.

4. The method of claim 1, wherein selecting the subwindow to be evaluated comprises:

selecting a new subwindow;

or

selecting a partially evaluated subwindow.

5. The method of claim 1, wherein if the currently estimated likelihood of the object being detected in the subwindow drops below a minimum value, the method further comprises discarding the subwindow.

6. The method of claim 1, wherein if currently estimated likelihood of the object being detected in the subwindow exceeds a predetermined value, the method further comprises fully evaluating the subwindow.

7. The method of claim 1, wherein storing the information associated with the subwindow comprises:

storing the information ordered by estimated likelihood to facilitate selecting the subwindow later based on the currently estimated likelihood of the object being detected within the subwindow.

8. The method of claim 1, wherein performing the evaluation step on the subwindow comprises:

using an incrementally evaluatable detector which is based on a neural network.

9. A method for detecting an object in an image, comprising:

using a computer to perform;

performing a first evaluation step on a first subwindow in the image to determine if the object exists in the first subwindow;

performing a first evaluation step on a second subwindow in the image to determine if the object exists in the second subwindow; and

subsequently performing a second evaluation step on the first subwindow;

wherein performing the first evaluation step on the first or second subwindow or performing the second evaluation step on the first subwindow comprises;

selecting the subwindow to be evaluated based upon a currently estimated likelihood of the object being detected within the subwindow;

performing an evaluation step on the subwindow; and

if evaluation of the subwindow is not complete after the evaluation step, storing information associated with the subwindow to facilitate subsequent evaluation of the subwindow.

10. A computer-readable storage device storing instructions that when executed by a computer cause the computer to perform a method for detecting an object in an image, the method comprising:

selecting a subwindow to be evaluated based upon a currently estimated likelihood of the object being detected within the subwindow;

performing an evaluation step on the subwindow to determine if the object exists in the subwindow, wherein performing the evaluation step comprises updating the currently estimated likelihood of the object being detected in the subwindow; and

if evaluation of the subwindow is not complete after the evaluation step, storing information associated with the subwindow to facilitate subsequent evaluation of the subwindow.

11. The computer-readable storage device of claim 10, wherein storing the information associated with the subwindow comprises:

updating and storing the currently estimated likelihood of the object being detected within the subwindow.

12. The computer-readable storage device of claim 11, wherein storing the information associated with the subwindow comprises:

storing the subwindow itself or location information for the subwindow; and

storing intermediate results, if any, associated with evaluation of the subwindow.

13. The computer-readable storage device of claim 10, wherein selecting the subwindow to be evaluated comprises:

selecting a new subwindow;

or

selecting a partially evaluated subwindow.

14. The computer-readable storage device of claim 10, wherein if the currently estimated likelihood of the object being detected in the subwindow drops below a minimum value, the method further comprises discarding the subwindow.

15. The computer-readable storage device of claim 10, wherein if currently estimated likelihood of the object being detected in the subwindow exceeds a predetermined value, the method further comprises fully evaluating the subwindow.

16. The computer-readable storage device of claim 10, wherein storing the information associated with the subwindow comprises:

storing the information ordered by estimated likelihood to facilitate selecting the subwindow later based on the currently estimated likelihood of the object being detected within the subwindow.

17. The computer-readable storage device of claim 10, wherein performing the evaluation step on the subwindow comprises:

using an incrementally evaluatable detector which is based on a neural network.

18. A computer-readable storage device storing instructions that when executed by a computer cause the computer to perform a method for detecting an object in an image, the method comprising:

performing a first evaluation step on a first subwindow in the image to determine if the object exists in the first subwindow;

performing a first evaluation step on a second subwindow in the image to determine if the object exists in the second subwindow; and

subsequently performing a second evaluation step on the first subwindow;

wherein performing the first evaluation step on the first or second subwindow or performing the second evaluation step on the first subwindow comprises;

selecting the subwindow to be evaluated based upon a currently estimated likelihood of the object being detected within the subwindow;

performing an evaluation step on the subwindow; and

if evaluation of the subwindow is not complete after the evaluation step, storing information associated with the subwindow to facilitate subsequent evaluation of the subwindow.

19. An apparatus that detects an object in an image, comprising:

one or more processors; and

a memory coupled to the one or more processors and storing program instructions executable by the one or more processors to implement;

selecting a subwindow to be evaluated based upon a currently estimated likelihood of the object being detected within the subwindow;

performing an evaluation step on the subwindow to determine if the object exists in the subwindow, wherein performing the evaluation step comprises updating the currently estimated likelihood of the object being detected in the subwindow; and

if evaluation of the subwindow is not complete after the evaluation step,

storing information associated with the subwindow to facilitate subsequent evaluation of the subwindow.

20. The apparatus of claim 19, wherein the program instructions are executable by the one or more processors to implement updating and storing the currently estimated likelihood of the object being detected within the subwindow.

21. The apparatus of claim 19, wherein the program instructions are executable by the one or more processors to implement:

storing the subwindow itself or location information for the subwindow; and

storing intermediate results, if any, associated with evaluation of the subwindow.

22. The apparatus of claim 19, wherein the program instructions are executable by the one or more processors to implement:

selecting a new subwindow or a partially evaluated subwindow.

23. The apparatus of claim 19, wherein the program instructions are executable by the one or more processors to implement:

if the currently estimated likelihood of the object being detected in the subwindow drops below a minimum value, discarding the subwindow.

24. The apparatus of claim 19, wherein the program instructions are executable by the one or more processors to implement:

if the currently estimated likelihood of the object being detected in the subwindow exceeds a predetermined value, fully evaluating the subwindow.

25. The apparatus of claim 19, wherein the program instructions are executable by the one or more processors to implement:

storing the information ordered by estimated likelihood to facilitate selecting the subwindow later based on the currently estimated likelihood of the object being detected within the subwindow.

26. The apparatus of claim 19, wherein performing the evaluation step on the subwindow comprises:

using an incrementally evaluatable detector which is based on a neural network.

27. An apparatus that detects an object in an image, comprising:

one or more processors; and

a memory coupled to the one or more processors and storing program instructions executable by the one or more processors to implement;

performing a first evaluation step on a first subwindow in the image to determine if the object exists in the first subwindow;

performing a first evaluation step on a second subwindow in the image to determine if the object exists in the second subwindow; and

subsequently performing a second evaluation step on the first subwindow;

wherein performing the first evaluation step on the first or second subwindow or performing the second evaluation step on the first subwindow comprises;

selecting the subwindow to be evaluated based upon a currently estimated likelihood of the object being detected within the subwindow;

performing an evaluation step on the subwindow; and

if evaluation of the subwindow is not complete after the evaluation step, storing information associated with the subwindow to facilitate subsequent evaluation of the subwindow.