Method and system for object detection in digital images

• US 7,099,510 B2
• Filed: 11/12/2001
• Issued: 08/29/2006
• Est. Priority Date: 11/29/2000
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Jones, Michael J., Viola, Paul
• Primary Examiner(s): Shah, Sanjiv
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/992,795
• Publication Number:
  US 20020102024A1
• Time in Patent Office: 1,751 Days
• Field of Search: 382/115, 382/116, 382/118, 382/157, 382/159, 382/195, 382/224, 382/279, 382/203, 382/228, 348/142, 348/152
• 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 homogeneous classifiers each represented by a respective homogenous classification function covering a plurality of features, each of the homogenous classification functions in sequence in the cascade respectively having increasing accuracy in identifying features associated with the certain objects such that one classifier identifies the plural features at one level of accuracy and a subsequent classifier in the cascade sequence identifies the same plural features at an increased level of accuracy with respect to the one classifier; and

for each subwindow, employing the cascade of homogenous classification functions to quickly detect instances of the certain objects in the image in a manner enabling real-time application, said employing including discarding subwindows that insufficiently show features of the certain objects and continuing to process through the cascade only subwindows having sufficient features that indicate a likelihood of an instance of the certain objects in the subwindows.

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 of 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_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:

$h_j=\{\begin{array}{c}1,\mathrm{if}<br><br><br><br>p_j<br><br>f_j<br><br>\left(x\right)><br><br>p_j<br><br>T_j\\ <br><br>0,\mathrm{otherwise}\end{array}$

wherein x is a vector of pixel values in a given subwindow;

wherein f_j is an evaluation function for the given feature;

wherein T_j is a predefined feature threshold for the given feature indicating a presence of the given feature in the subwindow by assigning a value of 1 to the given threshold function h_j, and wherein p_j is a polarity value having a value of +1 or −

1; and

wherein each homogeneous classification function is based on a summation function defined as follows;

$\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>w_j<br><br>h_j<br><br>\left(x\right)><br><br>\mathrm{\theta <br><br>}$

wherein w_j is a predefined weight for each threshold function h_j, and wherein θ

is a predefined global threshold that determines whether or not the summation function indicates a detection of one of the instances of the certain object in the given subwindow.

10. The method of claim 1 wherein the features are composed of weighted sums of average pixel values of a plurality of rectangles within the subwindow.

11. The method of claim 1 wherein the step of employing includes quickly identifying and discarding subwindows that do not contain instances of the certain objects.

22. An object detection as claimed in claim 11 wherein for each subwindow the object detector has twenty or fewer operations.

12. 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 homogeneous classifiers each represented by a respective homogenous classification function covering a same plurality of features, each of the homogenous classification functions in sequence in the cascade respectively having increasing accuracy in identifying features associated with the certain objects such that one classifier identifies the plural features at one level of accuracy and a subsequent classifier in the cascade sequence identifies the same plural features at an increased level of accuracy with respect to the one classifier;

the object detector employing, for each subwindow, the cascade of homogenous classification functions to quickly detect instances of the certain objects in the image in a manner enabling real-time application, including discarding a subwindow that insufficiently shows features of the certain objects and continuing to process through the cascade only subwindows having sufficient features that indicate a likelihood of an instance of the certain objects in the subwindows.

13. The object detection system of claim 12, 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.

14. The object detection system of claim 12, 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.

15. The object detection system of claim 12, wherein the certain objects are human faces.

16. The object detection system of claim 12, 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.

17. The object detection system of claim 16, 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.

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

19. The object detection system claim 12, 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.

20. The object detection system of claim 12, 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:

$h_j=\{\begin{array}{c}1,\mathrm{if}<br><br><br><br>p_j<br><br>f_j<br><br>\left(x\right)><br><br>p_j<br><br>T_j\\ <br><br>0,\mathrm{otherwise}\end{array}$

wherein x is a vector of pixel values in a given subwindow;

wherein f_j is an evaluation function for the given feature;

wherein T_j is a predefined feature threshold for the given feature indicating a presence of the given feature in the subwindow by assigning a value of 1 to the given threshold function h_j , and wherein p_j is a polarity value having a value of +1 or −

1; and

wherein each homogeneous classification function is based on a summation function defined as follows;

$\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>w_j<br><br>h_j<br><br>\left(x\right)><br><br>\mathrm{\theta <br><br>}$

wherein w_j is a predefined weight for each threshold function h_j, and wherein θ

is a predefined global threshold that determines whether or not the summation function indicates a detection of one of the instances of the certain object in the given subwindow.

21. The object detection system of claim 12, wherein the features are rectangular features.

23. 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 classifiers each represented by a respective homogeneous classification function covering a same plurality of features, each of the homogenous classification functions in sequence in the cascade respectively having increasing accuracy in identifying features associated with the certain objects such that one classifier identifies the plural features at one level of accuracy and a subsequent classifier in the cascade sequence identifies the same plural features at an increased level of accuracy with respect to the one classifier; and

for each subwindow, employ the cascade of homogenous classification functions to quickly detect instances of the certain objects in the image in a manner enabling real-time application, including discarding a subwindow that insufficiently shows features of the certain objects and continuing to process through the cascade only subwindows having sufficient features that indicate a likelihood of an instance of the certain objects in the subwindows.

24. 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) for each subwindow, evaluating the features in the subwindow at one level of accuracy followed by evaluating the same features at increasing levels of accuracy; and

(b) classifying each subwindow to detect an instance of the certain objects based on the step of evaluating the features, such that instances of the certain objects are quickly detected enabling real-time application, said classifying including discarding a subwindow that insufficiently shows features of the certain objects and continuing to evaluate only subwindows having sufficient features that indicate a likelihood of an instance of the certain objects in the subwindows.

25. The method of claim 24, wherein the processing rate is independent of dimensions of the subwindows.

26. The method of claim 24, 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.

27. The method of claim 24, 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.

28. The method of claim 24, wherein the certain objects are human faces.

29. 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) for each subwindow, evaluating the features in the subwindow at one level of accuracy followed by evaluating the same features at increasing levels of accuracy; and

(b) classifying each subwindow to detect an instance of the certain objects based on the step of evaluating the features, including discarding a subwindow that insufficiently shows features of the certain objects and continuing to evaluate only subwindows having sufficient features that indicate a likelihood of an instance of the certain objects in the subwindows, said image scanner and object detector providing quick detection of instances of the certain objects in a manner enabling real-time application.

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

31. The object detection system of claim 29, 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.

32. The object detection system of claim 29, 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.

33. The object detection system of claim 29, wherein the certain objects are human faces.

34. 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 use able 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) for each subwindow, evaluating the features in the subwindow at one level of accuracy followed by evaluating the same features at increasing levels of accuracy; and

(b) classifying each subwindow to detect an instance of the certain objects based on the step of evaluating the features, including discarding a subwindow that insufficiently shows features of the certain objects and continuing to evaluate only subwindows having sufficient features that indicate a likelihood of an instance of the certain objects in the subwindow

such that instances of the certain objects are quickly detected enabling real-time application.

35. 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, 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;

$h_j=\{\begin{array}{c}1,<br><br>\mathrm{if}<br><br><br><br>p_j<br><br>f_j<br><br>\left(x\right)><br><br>p_j<br><br>T_j\\ 0,<br><br><br><br>\mathrm{otherwise}\end{array}$

wherein x is a vector of pixel values in a given subwindow;

wherein f_j is an evaluation function for the given feature;

wherein T_j is a predefined feature threshold for the given feature indicating a presence of the given feature in the subwindow by assigning a value of 1 to the given threshold function h_j, and wherein p_j is a polarity value having a value of +1 or −

1; and

wherein each homogeneous classification function is based on a summation function defined as follows;

$\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>w_j<br><br>h_j<br><br>\left(x\right)><br><br>\mathrm{\theta <br><br>}$

wherein w_j is a predefined weight for each threshold function h_j, and wherein θ

is a predefined global threshold that determines whether or not the summation function indicates a detection of one of the instances of the certain object in the given subwindow.

36. 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, 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;

$h_j=\{\begin{array}{c}1,<br><br>\mathrm{if}<br><br><br><br>p_j<br><br>f_j<br><br>\left(x\right)><br><br>p_j<br><br>T_j\\ 0,<br><br><br><br>\mathrm{otherwise}\end{array}$

wherein x is a vector of pixel values in a given subwindow;

wherein f_j is an evaluation function for the given feature;

wherein T_j is a predefined feature threshold for the given feature indicating a presence of the given feature in the subwindow by assigning a value of 1 to the given threshold function h_j, and wherein p_j is a polarity value having a value of +1 or −

1; and

wherein each homogeneous classification function is based on a summation function defined as follows;

$\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>w_j<br><br>h_j<br><br>\left(x\right)><br><br>\mathrm{\theta <br><br>}$

wherein w_j is a predefined weight for each threshold function h_j, and wherein θ

is a predefined global threshold that determines whether or not the summation function indicates a detection of one of the instances of the certain object in the given subwindow.

37. 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, 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;

$h_j=\{\begin{array}{c}1,<br><br>\mathrm{if}<br><br><br><br>p_j<br><br>f_j<br><br>\left(x\right)><br><br>p_j<br><br>T_j\\ 0,<br><br><br><br>\mathrm{otherwise}\end{array}$

wherein x is a vector of pixel values in a given subwindow;

wherein f_j is an evaluation function for the given feature;

wherein T_j is a predefined feature threshold for the given feature indicating a presence of the given feature in the subwindow by assigning a value of 1 to the given threshold function h_j, and wherein p_j is a polarity value having a value of +1 or −

1; and

wherein each homogeneous classification function is based on a summation function defined as follows;

$\underset{j=1}{\overset{N}{\sum <br><br>}}<br><br><br><br>w_j<br><br>h_j<br><br>\left(x\right)><br><br>\mathrm{\theta <br><br>}$

wherein w_j is a predefined weight for each threshold function h_j, and wherein θ

is a predefined global threshold that determines whether or not the summation function indicates a detection of one of the instances of the certain object in the given subwindow.