Method and system for object detection in digital images

• US 20020102024A1
• Filed: 11/12/2001
• Published: 08/01/2002
• Est. Priority Date: 11/29/2000
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Information Technologies Group LP (HP Inc.)
• Inventors: Viola, Paul, Jones, Michael J.
• Granted Patent: US 7,099,510 B2
• Time in Patent Office: Days
• US Class Current: 382/225
• CPC Class Codes: G06F 18/2148 characterised by the process organisation or structure, e.g. boosting cascade
• 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
• CPC Class Codes: G06V 40/165 using facial parts and geometric relationships

Abstract

An object detection system for detecting instances of an object in a digital image includes an image integrator and an object detector, which includes a classifier (classification function) and image scanner. The image integrator receives an input image and calculates an integral image representation of the input image. The image scanner scans the image in same sized subwindows. The object detector uses a cascade of homogenous classification functions or classifiers to classify the subwindows as to whether each subwindow is likely to contain an instance of the object. Each classifier evaluates one or more features of the object to determine the presence of such features in a subwindow that would indicate the likelihood of an instance of the object in the subwindow.

Claims

1. A method for detecting certain objects in an image, comprising the computer-implemented steps of:

placing a working window at different positions in an input image such that the input image is divided into a plurality of same dimension subwindows;

providing a cascade of homogenous classification functions, each of the homogenous classification functions in sequence in the cascade respectively having increasing accuracy in identifying features associated with the certain objects; and

for each subwindow, employing the cascade of homogenous classification functions to detect instances of the certain objects in the image.

2. The method of claim 1, further comprising a computer-implemented step of:

scaling the dimensions of the subwindows by changing a size of the working window;

scaling the homogenous classification functions respectively for each different size of the working window, and

for each different size of the working window, repeating the steps of placing, providing, and employing.

3. The method of claim 1, further comprising a computer-implemented step of computing an integral image representation of the input image;

and

wherein the step of employing the cascade includes utilizing the integral image representation in computing the homogenous classification functions.

4. The method of claim 1, wherein the certain objects are human faces.

5. The method of claim 1, further comprising a computer-implemented step of training the homogenous classification functions in a learning phase based on a training data set and thereby identifying optimal such functions.

6. The method of claim 5, further comprising constructing the cascade based on the optimal homogenous classification functions such that the step of employing the cascade performs at an average processing rate of less than about 200 arithmetic operations for each subwindow.

7. The method of claim 6, wherein the processing rate is independent of the dimensions of the subwindows.

8. The method claim 1, further comprising a computer-implemented step of providing to a computer output device an output image that identifies the detected instances of the certain objects based on the step of employing the cascade.

9. The method of claim 1, wherein each homogenous classification function is based on a number N of the features and a plurality of threshold functions h., each feature having one of the respective threshold functions h. identified respectively by an iterator j having values from j=1 to j=N, a given threshold function h, for a given feature defined as follows:

10. The method of claim 1 wherein the features are rectangular features.

11. An object detection system for detecting certain objects in an image, comprising:

an image scanner for placing a working window at different positions in an input image such that the input image is divided into a plurality of same dimension subwindows; and

an object detector for providing a cascade of homogenous classification functions, each of the homogenous classification functions in sequence in the cascade respectively having increasing accuracy in identifying features associated with the certain objects;

the object detector employing, for each subwindow, the cascade of homogenous classification functions to detect instances of the certain objects in the image.

12. The object detection system of claim 11, wherein the image scanner scales the dimensions of the subwindows by changing a size of the working window;

and

wherein the object detector scales the homogenous classification functions respectively for each different size of the working window, and, for each different size of the working window, (i) the image scanner repeats the placing of the scaled working window at different positions in the input image to divide the input image into a plurality of scaled same dimension subwindows, and (ii) the object detector repeats the employing of the cascade of scaled homogenous classification functions to detect the instances of the certain objects.

13. The object detection system of claim 11, further comprising an image integrator, wherein the image integrator computes an integral image representation of the input image;

and

wherein the object detector utilizes the integral image representation in computing the homogenous classification functions.

14. The object detection system of claim 11, wherein the certain objects are human faces.

15. The object detection system of claim 11, further comprising a training server, wherein the training server trains the homogenous classification functions in a learning phase based on a training data set and thereby identifying optimal such functions.

16. The object detection system of claim 15, wherein the training server constructs the cascade based on the optimal homogenous classification functions such that the object detector performs the employing of the cascade at an average processing rate of less than about 200 arithmetic operations for each subwindow.

17. The object detection system of claim 16, wherein the processing rate is independent of the dimensions of the subwindows.

18. The object detection system claim 11, wherein the object detector provides to a computer output device an output image that identifies the detected instances of the certain objects based on the employing of the cascade.

19. The object detection system of claim 11, wherein each homogenous classification function is based on a number N of the features and a plurality of threshold functions h_j, each feature having one of the respective threshold functions h_j identified respectively by an iterator j having values from j=1 to j=N, a given threshold function h_j for a given feature defined as follows:

20. The object detection system of claim 11, wherein the features are rectangular features.

21. A computer program product comprising:

a computer usable medium for detecting certain objects in an image; and

a set of computer program instructions embodied on the computer useable medium, including instructions to;

place a working window at different positions in an input image such that the input image is divided into a plurality of same dimension subwindows;

provide a cascade of homogenous classification functions, each of the homogenous classification functions in sequence in the cascade respectively having increasing accuracy in identifying features associated with the certain objects; and

for each subwindow, employ the cascade of homogenous classification functions to detect instances of the certain objects in the image.

22. A method for detecting certain objects in an image, comprising the computer-implemented steps of:

(i) dividing an input image into a plurality of subwindows, each subwindow having a sufficient size to allow processing of features associated with the certain objects; and

(ii) processing the subwindows at an average processing rate less than about 200 arithmetic operations for each subwindow by;

(a) evaluating the features in each subwindow; and

(b) classifying each subwindow to detect an instance of the certain objects based on the step of evaluating the features.

23. The method of claim 22, wherein the processing rate is independent of dimensions of the subwindows.

24. The method of claim 22, further comprising a computer-implemented step of computing an integral image representation of the input image and using the integral image representation to compute homogenous classification functions for use in the step of processing the subwindows.

25. The method of claim 22, wherein the step of processing the subwindows comprises:

for each subwindow, employing a cascade of optimal homogenous classification functions, each optimal homogenous classification function in sequence in the cascade respectively having increasing accuracy in identifying the features associated with the certain objects; and

,

at each optimal homogenous classification function in the cascade;

if a subject subwindow has the detected instance of the certain object, continuing to pass the subject subwindow through the cascade for further processing, and

if the subject subwindow does not have the detected instance of the certain object, ceasing to pass the subject subwindow through the cascade.

26. The method of claim 22, wherein the certain objects are human faces.

28. The object detection system of claim 27, wherein the processing rate is independent of dimensions of the subwindows.

29. The object detection system of claim 27, further comprising an image integrator,

wherein the image integrator computes an integral image representation of the input image;

and

the object detector uses the integral image representation to compute homogenous classification functions for use in the processing of the subwindows.

30. The object detection system of claim 27, wherein:

the object detector, for each subwindow, employs a cascade of optimal homogenous classification functions, each optimal homogenous classification function in sequence in the cascade respectively having increasing accuracy in identifying the features associated with the certain objects; and

,

at each optimal homogenous classification function in the cascade, the object detector;

if a subject subwindow has the detected instance of the certain object, continues to pass the subject subwindow through the cascade for further processing, and

if the subject subwindow does not have the detected instance of the certain object, ceases to pass the subject subwindow through the cascade.

31. The object detection system of claim 27, wherein the certain objects are human faces.

27. An object detection system for detecting certain objects in an image, comprising:

(i) an image scanner for dividing an input image into a plurality of subwindows, each subwindow having a sufficient size to allow processing of features associated with the certain objects; and

(ii) an object detector for processing the subwindows at an average processing rate less than about 200 arithmetic operations for each subwindow by;

(a) evaluating the features in each subwindow; and

(b) classifying each subwindow to detect an instance of the certain objects based on the step of evaluating the features.

32. A computer program product comprising:

a computer usable medium for detecting certain objects in an image; and

a set of computer program instructions embodied on the computer useable medium, including instructions to;

(i) divide an input image into a plurality of subwindows, each subwindow having a sufficient size to allow processing of features associated with the certain objects; and

(ii) process the subwindows at an average processing rate less than about 200 arithmetic operations for each subwindow by;

(a) evaluating the features in each subwindow; and

(b) classifying each subwindow to detect an instance of the certain objects based on the step of evaluating the features.