Object finder for photographic images

• US 20020159627A1
• Filed: 02/28/2001
• Published: 10/31/2002
• Est. Priority Date: 02/28/2001
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Carnegie Mellon University
• Inventors: Schneiderman, Henry, Kanade, Takeo
• Granted Patent: US 6,829,384 B2
• Time in Patent Office: Days
• US Class Current: 382/154
• CPC Class Codes: G06F 18/24155 Bayesian classification
• CPC Class Codes: G06T 7/73 using feature-based methods
• 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

Abstract

An object finder program for detecting presence of a 3D object in a 2D image containing a 2D representation of the 3D object. The object finder uses the wavelet transform of the input 2D image for object detection. A pre-selected number of view-based detectors are trained on sample images prior to performing the detection on an unknown image. These detectors then operate on the given input image and compute a quantized wavelet transform for the entire input image. The object detection then proceeds with sampling of the quantized wavelet coefficients at different image window locations on the input image and efficient look-up of pre-computed log-likelihood tables to determine object presence. The object finder'"'"'s coarse-to-fine object detection strategy coupled with exhaustive object search across different positions and scales results in an efficient and accurate object detection scheme. The object finder detects a 3D object over a wide range in angular variation (e.g., 180 degrees) through the combination of a small number of detectors each specialized to a small range within this range of angular variation.

Claims

1. A method to detect presence of a 3D (three dimensional) object in a 2D (two dimensional) image containing a 2D representation of said 3D object, said method comprising:

receiving a digitized version of said 2D image;

selecting one or more view-based detectors;

for each view-based detector, computing a wavelet transform of said digitized version of said 2D image, wherein said wavelet transform generates a plurality of transform coefficients, and wherein each transform coefficient represents visual information from said 2D image that is localized in space, frequency, and orientation;

applying said one or more view-based detectors in parallel to respective plurality of transform coefficients, wherein each view-based detector is configured to detect a specific orientation of said 3D object in said 2D image based on visual information received from corresponding transform coefficients;

combining results of application of said one or more view-based detectors; and

determining orientation and location of said 3D object from said combination of results of application of said one or more view-based detectors.

2. The method of claim 1, further comprising developing said one or more view-based detectors from a pre-selected set of training images.

3. The method of claim 2, wherein developing said one or more view-based detectors includes the following for at least one of said one or more view-based detectors:

selecting at least one correction factor, wherein said at least one correction factor is configured to correct the light intensity level of at least one of said training images;

selecting a first value for said at least one correction factor;

applying said first value for said at least one correction factor to said at least one of said training images;

examining an effect on appearance of said at least one of said training images after application of said first value of said at least one correction factor thereto;

selecting a second value of said at least one correction factor based on said effect on the appearance of said at least one of said training images; and

continuing selection, application, and examination until a desired effect on the appearance of said at least one of said training images is obtained.

4. The method of claim 3, wherein selecting at least one correction factor includes selecting two correction factors, and wherein each of said two correction factors is applied to a different half of said at least one of said training images.

5. The method of claim 2, wherein developing said one or more view-based detectors includes the following for at least one of said one or more view-based detectors:

defining a plurality of attributes;

selecting an image window, wherein said image window is configured to be placed at a plurality of locations on each of said training images;

for each attribute, determining corresponding attribute values at a plurality of coordinates at one of said plurality of locations of said image window by training a plurality of instances of said at least one view-based detector on said pre-selected set of training images;

for each of said plurality of instances, computing a respective weight to be applied to corresponding attribute values for said each attribute at said one of said plurality of locations of said image window;

for each of said plurality of instances, applying said respective weight to corresponding attribute values for each attribute at said plurality of coordinates at said one of said plurality of locations of said image window, thereby generating a set of weighted attribute values for each attribute for each of said plurality of coordinates at said one of said plurality of locations of said image window; and

for each of said plurality of coordinates and for each attribute, combining corresponding weighted attribute values in said set of weighted attribute values, thereby generating a single attribute value for each attribute at said each of said plurality of coordinates at said one of said plurality of locations of said image window.

6. The method of claim 1, wherein computing said wavelet transform includes:

computing said wavelet transform for a first scale of said 2D image, thereby generating a plurality of wavelet transform levels at said first scale; and

reusing at least one of said plurality of wavelet transform levels as part of said wavelet transform for a second scale of said 2D image when computing said wavelet transform for said second scale.

7. The method of claim 6, wherein said first and said second scales differ from one another by one octave.

8. The method of claim 6, wherein said plurality of wavelet transform levels includes three levels, and wherein said wavelet transform for said second scale reuses two lower resolution levels from said three wavelet transform levels for said first scale.

9. The method of claim 1, wherein applying said one or more view-based detectors in parallel includes the following for at least one of said one or more view-based detectors:

defining a plurality of attributes, wherein each attribute is configured to sample and quantize each of a predetermined number of transform coefficients from said plurality of transform coefficients;

selecting an image window, wherein said image window is configured to represent a fixed size area of said 2D image;

placing said image window at one of a plurality of locations within said 2D image;

selecting two correction factors, wherein each of said two correction factors is configured to correct the light intensity level for a corresponding half of said image window at said one of said plurality of locations;

selecting a predetermined number of correction values for each of said two correction factors;

for each of said two correction factors and for each of said predetermined number of correction values therefor, evaluating the total log-likelihood value for said plurality of attributes for the corresponding half of said image window at said one of said plurality of locations;

for each half of said image window at said one of said plurality of locations, selecting the largest total log-likelihood value for said plurality of attributes; and

adding corresponding largest total log-likelihood value for said each half of said image window to estimate the presence of said 3D object.

10. The method of claim 1, wherein applying said one or more view-based detectors in parallel includes the following for at least one of said one or more view-based detectors:

defining a plurality of attributes, wherein each attribute is configured to sample and quantize each of a predetermined number of transform coefficients from said plurality of transform coefficients;

selecting an image window, wherein said image window is configured to represent a fixed size area of said 2D image;

placing said image window at a first one of a first plurality of locations within said 2D image;

for each of said plurality of attributes, determining a corresponding attribute value at each of a first plurality of coordinates within said image window at said first location;

for each of said plurality of attributes, obtaining a first class-conditional probability for an object class and a second class-conditional probability for a non-object class at said each of said first plurality of coordinates based on said corresponding attribute values determined at said first plurality of coordinates;

estimating presence of the 3D object in said image window at said first location based on a ratio of a first product and a second product, wherein said first product includes a product of all of said first class-conditional probabilities and wherein said second product includes a product of all of said second class-conditional probabilities;

moving said image window to a second one of said first plurality of locations within said 2D image; and

continuing determination of said corresponding attribute values and said first and said second class-conditional probabilities, and estimation of the presence of said 3D object in said image window at said second location and at each remaining location in said first plurality of locations within said 2D image.

11. The method of claim 10, wherein said first and said second class-conditional probabilities are obtained by looking-up a pre-computed set of log-likelihood tables using corresponding attribute values.

12. The method of claim 10, wherein said image window is rectangular.

13. The method of claim 10, wherein said plurality of attributes includes seventeen attributes.

14. The method of claim 10, wherein said each attribute is configured to sample and quantize eight transform coefficients.

15. The method of claim 10, wherein said each attribute quantizes said each of said predetermined number of transform coefficients into three levels.

16. The method of claim 10, further comprising the following for at least one of said one or more view-based detectors:

scaling said 2D image to one of a predetermined number of scale levels, thereby generating a scaled image;

placing said image window at a third one of a second plurality of locations within said scaled image;

for each of said plurality of attributes, determining said corresponding attribute value at each of a second plurality of coordinates within said image window at said third location;

for each of said plurality of attributes, obtaining a third class-conditional probability for said object class and a fourth class-conditional probability for said non-object class at said each of said second plurality of coordinates based on said corresponding attribute values determined at said second plurality of coordinates;

estimating presence of the 3D object in said image window at said third location based on a ratio of a third product and a fourth product, wherein said third product includes a product of all of said third class-conditional probabilities and wherein said fourth product includes a product of all of said fourth class-conditional probabilities;

moving said image window to a fourth one of said second plurality of locations within said scaled image; and

continuing determination of said corresponding attribute values and said third and said fourth class-conditional probabilities, and estimation of the presence of said 3D object in said image window at said fourth location and at each remaining location in said second plurality of locations within said scaled image.

17. The method of claim 16, wherein said predetermined number of scale levels is determined based on the size of the 2D image.

18. The method of claim 16, wherein scaling said 2D image is continued until the scaled version of said 2D image is smaller than the size of said image window.

19. The method of claim 1, wherein applying said one or more view-based detectors in parallel includes the following for at least one of said one or more view-based detectors:

defining a plurality of attributes, wherein each attribute is configured to sample and quantize each of a predetermined number of transform coefficients from said plurality of transform coefficients;

selecting an image window, wherein said image window is configured to represent a fixed size area of said 2D image;

placing said image window at a plurality of locations within said 2D image;

for each attribute in a subset of said plurality of attributes, determining a corresponding attribute value at each of a plurality of coordinates within said image window at each of said plurality of locations;

for each attribute in said subset of said plurality of attributes, obtaining a first class-conditional probability for an object class and a second class-conditional probability for a non-object class at said each of said plurality of coordinates at said each of said plurality of locations based on said corresponding attribute values determined at said plurality of coordinates;

computing a plurality of ratios, wherein each ratio corresponds to a different one of said plurality of locations of said image window, wherein said each ratio is a division of a first product and a second product, and wherein said first product includes a product of all of said first class-conditional probabilities and wherein said second product includes a product of all of said second class-conditional probabilities at corresponding one of said plurality of locations of said image window;

determining which of said plurality of ratios are above a predetermined threshold value; and

estimating presence of said 3D object at only those of said plurality of locations where corresponding ratios are above said predetermined threshold value.

20. The method of claim 1, wherein applying said one or more view-based detectors in parallel includes the following for at least one of said one or more view-based detectors:

defining a plurality of attributes, wherein each attribute is configured to sample and quantize each of a predetermined number of transform coefficients from said plurality of transform coefficients;

for each of said plurality of attributes, determining a corresponding attribute value at each of a plurality of coordinate locations within said 2D image;

selecting an image window, wherein said image window is configured to represent a fixed size area of said 2D image;

placing said image window at a first one of a plurality of locations within said 2D image;

for each of said plurality of attributes, selecting those corresponding attribute values that fall within said first location of said image window;

for each of said plurality of attributes, obtaining a first class-conditional probability for an object class and a second class-conditional probability for a non-object class based on said selected attribute values that fall within said first location of said image window;

estimating presence of the 3D object in said image window at said first location based on a ratio of a first product and a second product, wherein said first product includes a product of all of said first class-conditional probabilities and wherein said second product includes a product of all of said second class-conditional probabilities;

moving said image window to a second one of said plurality of locations within said 2D image; and

continuing selection of corresponding attribute values, determination of said first and said second class-conditional probabilities, and estimation of the presence of said 3D object in said image window at said second location and at each remaining location in said plurality of locations within said 2D image.

21. The method of claim 1, wherein said 3D object is a human face.

22. The method of claim 1, wherein said 3D object is a car.

23. The method of claim 1, further comprising placing a marker at said location of said 3D object upon detecting said location in said 2D image.

25. The computer-readable storage medium of claim 24 having stored thereon instructions, which, when executed by the processor, cause the processor to further perform the following:

evaluate a subset of said plurality of visual attributes at said each of said first plurality of locations of said image window using corresponding transform coefficients; and

estimate the presence of said 3D object only at those of said first plurality of locations of said image window where the likelihood ratio for said subset of said plurality of visual attributes is above a predetermined threshold value.

26. The computer-readable storage medium of claim 24 having stored thereon instructions, which, when executed by the processor, cause the processor to further perform the following:

generate a scaled version of said 2D image;

place said image window of fixed size at a second plurality of locations within said scaled version of said 2D image;

evaluate said plurality of visual attributes at each of said second plurality of locations of said image window using corresponding transform coefficients; and

estimate the presence of said 3D object in said scaled version of said 2D image based on evaluation of said plurality of visual attributes at said each of said second plurality of locations.

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

29. The method of claim 28, further comprising:

determining orientation of said 3D object in said 2D image; and

sending information about said orientation as part of said notification

30. The method of claim 28, further comprising charging a fee for sending said notification.

31. The method of claim 28, wherein said communication network is the Internet.

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

digitize a 2D (two dimensional) image, wherein said 2D image contains a 2D representation of a 3D (three dimensional) object;

compute a wavelet transform of said digitized version of said 2D image, wherein said wavelet transform generates a plurality of transform coefficients, and wherein each transform coefficient represents corresponding visual information from said 2D image;

place an image window of fixed size at a first plurality of locations within said 2D image;

evaluate a plurality of visual attributes at each of said first plurality of locations of said image window using corresponding transform coefficients; and

estimate the presence of said 3D object in said 2D image based on evaluation of said plurality of visual attributes at said each of said first plurality of locations.

28. A method of providing assistance in detecting the presence of a 3D (three dimensional) object in a 2D (two dimensional) image containing a 2D representation of said 3D object, said method comprising:

receiving a digitized version of said 2D image from a client site and over a communication network;

determining the location of said 3D object in said 2D image; and

sending a notification of said location of said 3D object to said client site over said communication network.

32. A system for providing assistance in detecting the presence of a 3D (three dimensional) object in a 2D (two dimensional) image containing a 2D representation of said 3D object, said system comprising:

a client computer connected to a communication network, wherein said client computer is configured to transmit a digitized version of said 2D image over said communication network; and

a host computer in communication with the client computer and connected to said communication network, wherein said host computer is configured to perform the following;

receive over said communication network said digitized version of said 2D image from said client computer,

determine the orientation and location of said 3D object in said 2D image received from said client computer, and

send a notification of said orientation and location of said 3D object to said client computer over said communication network.

33. The system of claim 32, wherein said communication network is the Internet.

35. The computer system of claim 34, which, upon being programmed, is further configured to perform the following for each of said one or more view-based detectors:

generate a scaled version of said 2D image;

place an image window of fixed size at a plurality of locations within said scaled version of said 2D image;

evaluate a plurality of visual attributes at each of said plurality of locations of said image window using corresponding transform coefficients; and

estimate the presence of said 3D object in said scaled version of said 2D image based on evaluation of said plurality of visual attributes at said each of said plurality of locations.

36. The computer system of claim 34, which, upon being programmed, is further configured to perform the following for each of said one or more view-based detectors:

select a plurality of attributes, wherein each attribute is configured to sample and quantize each of a predetermined number of transform coefficients from said plurality of transform coefficients;

place an image window at a first one of a plurality of locations within said 2D image, wherein said image window is configured to represent a fixed size area of said 2D image;

for each of said plurality of attributes, determine a corresponding attribute value at each of a plurality of coordinates within said image window at said first location;

for each of said plurality of attributes, compute a first class-conditional probability for an object class and a second class-conditional probability for a non-object class at said each of said plurality of coordinates based on said corresponding attribute values determined at said plurality of coordinates;

estimate the presence of the 3D object in said image window at said first location based on a ratio of a first product and a second product, wherein said first product includes a product of all of said first class-conditional probabilities and wherein said second product includes a product of all of said second class-conditional probabilities;

move said image window to a second one of said plurality of locations within said 2D image; and

continue determination of said corresponding attribute values and said first and said second class-conditional probabilities, and estimation of the presence of said 3D object in said image window at said second location and at each remaining location in said plurality of locations within said 2D image.

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

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

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

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

send a notification of said orientation and location of said 3D object to said client computer over said communication network.

38. The computer system of claim 34, which, upon being programmed, is further configured to perform the following for each of said one or more view-based detectors:

select a plurality of attributes, wherein each attribute is configured to sample and quantize each of a predetermined number of transform coefficients from said plurality of transform coefficients;

place an image window at a plurality of locations within said 2D image, wherein said image window is configured to represent a fixed size area of said 2D image;

for each attribute in a subset of said plurality of attributes, determine a corresponding attribute value at each of a plurality of coordinates within said image window at each of said plurality of locations;

for each attribute in said subset of said plurality of attributes, compute a first class-conditional probability for an object class and a second class-conditional probability for a non-object class at said each of said plurality of coordinates at said each of said plurality of locations based on said corresponding attribute values determined at said plurality of coordinates;

compute a plurality of ratios, wherein each ratio corresponds to a different one of said plurality of locations of said image window, wherein said each ratio is a division of a first product and a second product, and wherein said first product includes a product of all of said first class-conditional probabilities and wherein said second product includes a product of all of said second class-conditional probabilities at corresponding one of said plurality of locations of said image window;

determine which of said plurality of ratios are above a predetermined threshold value; and

estimate the presence of said 3D object at only those of said plurality of locations where corresponding ratios are above said predetermined threshold value.

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

receive a digitized version of a 2D (two dimensional) image, wherein said 2D image contains a 2D representation of a 3D (three dimensional) object;

select one or more view-based detectors;

for each view-based detector, compute a wavelet transform of said digitized version of said 2D image, wherein said wavelet transform generates a plurality of transform coefficients, and wherein each transform coefficient represents corresponding visual information from said 2D image;

apply said one or more view-based detectors in parallel to respective plurality of transform coefficients, wherein each view-based detector is configured to detect a specific orientation of said 3D object in said 2D image based on visual information received from corresponding transform coefficients;

combine results of application of said one or more view-based detectors; and

determine orientation and location of said 3D object from said combination of results of application of said one or more view-based detectors.