EXEMPLAR-BASED HETEROGENEOUS COMPOSITIONAL METHOD FOR OBJECT CLASSIFICATION

• US 20080310737A1
• Filed: 06/10/2008
• Published: 12/18/2008
• Est. Priority Date: 06/13/2007
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Han, Feng, Cheng, Hui, Sawhney, Harpreet Singh, Xiao, Jiangjian
• Granted Patent: US 8,233,704 B2
• Time in Patent Office: Days
• US Class Current: 382/224
• CPC Class Codes: G06F 18/214 Generating training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06F 18/254 of classification results, e.g. of results related to same input data
• CPC Class Codes: G06V 10/255 Detecting or recognising potential candidate objects based on visual cues, e.g. shapes
• CPC Class Codes: G06V 10/774 Generating sets of training patterns; Bootstrap methods, e.g. bagging or boosting
• CPC Class Codes: G06V 10/809 of classification results, e.g. where the classifiers operate on the same input data

Abstract

A method for automatically generating a strong classifier for determining whether at least one object is detected in at least one image is disclosed, comprising the steps of: (a) receiving a data set of training images having positive images; (b) randomly selecting a subset of positive images from the training images to create a set of candidate exemplars, wherein said positive images include at least one object of the same type as the object to be detected; (c) training a weak classifier based on at least one of the candidate exemplars, said training being based on at least one comparison of a plurality of heterogeneous compositional features located in the at least one image and corresponding heterogeneous compositional features in the one of set of candidate exemplars; (d) repeating steps (c) for each of the remaining candidate exemplars; and (e) combining the individual classifiers into a strong classifier, wherein the strong classifier is configured to determine the presence or absence in an image of the object to be detected.

Claims

1. A method for automatically generating a strong classifier for determining whether at least one object is detected in at least one image, comprising the steps of:

(a) receiving a data set of training images having positive images;

(b) randomly selecting a subset of positive images from the training images to create a set of candidate exemplars, wherein said positive images include at least one object of the same type as the object to be detected;

(c) training a weak classifier based on at least one of the candidate exemplars, said training being based on at least one comparison of a plurality of heterogeneous compositional features located in the at least one image and corresponding heterogeneous compositional features in the one of set of candidate exemplars;

(d) repeating steps (c) for each of the remaining candidate exemplars; and

(e) combining the individual classifiers into a strong classifier, wherein the strong classifier is configured to determine the presence or absence in an image of the object to be detected.

2. The method of claim 1, further comprising the steps of:

before step (c), selecting a set of weights based on at least the positive images and, after step (d) and before step (e);

(f) computing error rate of the trained weak classifier;

(g) repeating steps (c), (d), and (f) for each of the remaining candidate exemplars;

(h) selecting the trained weak classifier with a lowest error rate; and

(i) repeating steps (c), (d), and (f) through (h) using another set of weights until all the trained weak classifiers have been selected.

3. The method of claim 1, wherein step (c) further comprises the steps of:

(j) generating a plurality of single heterogeneous features from the at least one image;

(k) clustering single heterogeneous features about a set of centers to obtain a set of composite heterogeneous feature clusters, each of the feature clusters becoming a composition candidate entry in a candidate compositional codebook;

(l) selecting at least one of the candidate compositions based on a best match to the one of the candidate exemplars to obtain an exemplar-based composition codebook;

(m) encoding spatial relationships between each of the entries in an exemplar based compositional codebook to produce an exemplar based geometric template;

(n) comparing the entries in exemplar based composition codebook to the entries in candidate compositional codebook using histogram quantization to obtain a bag of compositional features representation;

(o) computing differences between distances and orientations of the spatial relationships of the exemplar based geometric template and distances and orientations in the candidate compositions codebook to form a global shape deformation; and

(p) feeding the bag of compositional features representation and the global shape deformation to a supporter vector machine (SVM), the SVM outputting the weak classifier.

4. The method of claim 3, wherein step (k) further comprises the step of performing a k-means clustering on Scale Invariant Feature Transformation (SIFT) features, region features, and curve features detected in the plurality of single heterogeneous features to obtain SIFT, region, and curve codebooks.

5. The method of claim 4, further comprising the step combining the SIFT, region, and curve codebooks into the candidate compositional codebook.

6. The method of claim 5, further comprising the step of using Gestalt laws to generate compositional feature candidates.

7. The method of claim 6, wherein using Gestalt laws to generate compositional feature candidates further comprises the steps of grouping local single features with neighboring features that are not farther away than 60-100 pixel and performing a k-means clustering to generate a general codebook of compositional features for all the object instances in one category.

8. The method of claim 7, further comprising the step of refining the general codebook of compositional features to generate an exemplar-oriented compositional codebook by removing those entries whose best matches on a given exemplar are below some predefined threshold.

9. The method of claim 3, wherein step (m) further comprises the step encoding the spatial relationships in a pair-wise spatial relationship representation (PSR), wherein the distance of one objects in the exemplar-based compositional codebook from the PSR of the exemplar used to obtain the codebook is encoded.

10. The method of claim 9, wherein encoding the spatial relationships employs histogram quantization.

11. The method of claim 1, wherein step (e) employs an AdaBoost method.

12. A system for automatically generating a strong classifier for determining whether at least one object is present in at least one image, comprising:

a camera for receiving at least one image of an object to be detected; and

a processor communicatively connected to said camera, said processor being configured for;

(a) receiving a data set of training images having positive images;

(b) randomly selecting a subset of positive images from the training images to create a set of candidate exemplars, wherein said positive images include at least one object of the same type as the object to be detected;

(c) training a weak classifier based on at least one of the candidate exemplars, said training being based on at least one comparison of a plurality of heterogeneous compositional features located in the at least one image and corresponding heterogeneous compositional features in the one of set of candidate exemplars;

(d) repeating steps (c) for each of the remaining candidate exemplars; and

(e) combining the individual classifiers into a strong classifier, wherein the strong classifier is configured to determine the presence or absence in an image of the object to be detected.

13. The system of claim 12, further comprising:

before step (c), selecting a set of weights based on at least the positive images and, after step (d) and before step (e);

(f) computing error rate of the trained weak classifier;

(g) repeating steps (c), (d), and (f) for each of the remaining candidate exemplars;

(h) selecting the trained weak classifier with a lowest error rate; and

(i) repeating steps (c), (d), and (f) through (h) using another set of weights until all the trained weak classifiers have been selected.

14. The system of claim 12, wherein step (c) further comprises the steps of:

(j) generating a plurality of single heterogeneous features from the at least one image;

(k) clustering single heterogeneous features about a set of centers to obtain a set of composite heterogeneous feature clusters, each of the feature clusters becoming a composition candidate entry in a candidate compositional codebook;

(l) selecting at least one of the candidate compositions based on a best match to the one of the candidate exemplars to obtain an exemplar-based composition codebook;

(m) encoding spatial relationships between each of the entries in an exemplar based compositional codebook to produce an exemplar based geometric template;

(n) comparing the entries in exemplar based composition codebook to the entries in candidate compositional codebook using histogram quantization to obtain a bag of compositional features representation;

(o) computing differences between distances and orientations of the spatial relationships of the exemplar based geometric template and distances and orientations in the candidate compositions codebook to form a global shape deformation; and

(p) feeding the bag of compositional features representation and the global shape deformation to a supporter vector machine (SVM), the SVM outputting the weak classifier.

15. The system of claim 12, wherein step (e) employs an AdaBoost method.

16. A computer-readable medium carrying one or more sequences for automatically generating a strong classifier for determining whether at least one object is present in at least one image, wherein execution of the one of more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

(a) receiving a data set of training images having positive images;

(b) randomly selecting a subset of positive images from the training images to create a set of candidate exemplars, wherein said positive images include at least one object of the same type as the object to be detected;

(c) training a weak classifier based on at least one of the candidate exemplars, said training being based on at least one comparison of a plurality of heterogeneous compositional features located in the at least one image and corresponding heterogeneous compositional features in the one of set of candidate exemplars;

(d) repeating steps (c) for each of the remaining candidate exemplars; and

(e) combining the individual classifiers into a strong classifier, wherein the strong classifier is configured to determine the presence or absence in an image of the object to be detected.

17. The computer readable medium of claim 16, further comprising:

before step (c), selecting a set of weights based on at least the positive images and, after step (d) and before step (e);

(f) computing error rate of the trained weak classifier;

(g) repeating steps (c), (d), and (f) for each of the remaining candidate exemplars;

(h) selecting the trained weak classifier with a lowest error rate; and

(i) repeating steps (c), (d), and (f) through (h) using another set of weights until all the trained weak classifiers have been selected.

18. The computer readable medium of claim 16, wherein step (c) further comprises the steps of:

(j) generating a plurality of single heterogeneous features from the at least one image;

(k) clustering single heterogeneous features about a set of centers to obtain a set of composite heterogeneous feature clusters, each of the feature clusters becoming a composition candidate entry in a candidate compositional codebook;

(l) selecting at least one of the candidate compositions based on a best match to the one of the candidate exemplars to obtain an exemplar-based composition codebook;

(m) encoding spatial relationships between each of the entries in an exemplar based compositional codebook to produce an exemplar based geometric template;

(n) comparing the entries in exemplar based composition codebook to the entries in candidate compositional codebook using histogram quantization to obtain a bag of compositional features representation;

(o) computing differences between distances and orientations of the spatial relationships of the exemplar based geometric template and distances and orientations in the candidate compositions codebook to form a global shape deformation; and

(p) feeding the bag of compositional features representation and the global shape deformation to a supporter vector machine (SVM), the SVM outputting the weak classifier.

19. The computer readable medium of claim 16, wherein step (e) employs an AdaBoost method.