Detector tree of boosted classifiers for real-time object detection and tracking

• US 7,203,669 B2
• Filed: 03/26/2003
• Issued: 04/10/2007
• Est. Priority Date: 03/17/2003
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Liang, Luhong, Lienhart, Rainer W., Kuranov, Alexander
• Primary Examiner(s): Hirl; Joseph P
• Assistant Examiner(s): Buss; Benjamin
• Application Number:
  US10/401,125
• Publication Number:
  US 20040186816A1
• Time in Patent Office: 1,476 Days
• Field of Search: 706/20, 706/17, 706/45, 706/48, 348169-172, 375/240.08, 375/240.12, 375/240.16, 382/103
• US Class Current: 706/48
• CPC Class Codes: G06F 18/2148 characterised by the process organisation or structure, e.g. boosting cascade
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06V 40/20 Movements or behaviour, e.g. gesture recognition recognition of facial expressions G06V40/16

Abstract

A tree classifier may include a number of stages. Some stages may include monolithic classifiers, and other stages may be split into two or more classifiers.

Claims

1. A method comprising:

building a tree classifier, which rejects non-object patterns in input data representing real world objects, including a plurality of parent nodes, wherein the tree classifier is stored on a machine-readable medium and is trained to perform human south detection and tracking in video sequences; and

for a parent node in the tree classifier, selecting between a monolithic classifier as a child node and a plurality of specialized classifiers as child nodes for said parent node;

wherein said selecting comprises;

determining a computational complexity of a monolithic classifiers trained with a plurality of positive and negative samples; and

determining a computational complexity of a plurality of specialized classifiers trained with the plurality of positive and negative samples, each of the specialized classifiers being trained with the plurality of negative samples and a different subset of the plurality of positive samples; and

wherein human mouth detection and tracking in video sequences occurs when other tree classifier is executed.

2. The method of claim 1, wherein said determining a computational complexity of the monolithic classifier comprises determining a number of features used by the monolithic classifier, and

wherein said determining a computational complexity of the plurality of specialized classifiers comprises determining a number of features used by the plurality of specialized classifiers.

3. The method of claim 1, further comprising training the monolithic classifier and the plurality of specialized classifiers with a boosting algorithm.

4. The method of claim 1, further comprising training the monolithic classifier and the plurality of classifiers to have a selected hit rate and a selected false alarm rate.

5. A method comprising:

building a tree classifier, which rejects non-object patterns in input data representing real world objects, wherein the tree classifier is stored on a machine-readable medium and is trained to perform human mouth detection and tracking in video sequences, the building including;

identifying a plurality of positive samples and the plurality of negative samples in a plurality of patterns;

passing the plurality of positive samples and the plurality of negative samples to a node in the tree classifier;

determining a number of features used by a monolithic classifier trained with said plurality of positive samples and said plurality of negative samples;

clustering the plurality of positive samples into a plurality of subsets;

training each of a plurality of specialized classifiers with the plurality of negative samples and a different one of said plurality of subsets;

determining a number of features used by the plurality of specialized classifiers; and

selecting the plurality of specialized classifiers in response to the number of features used by the plurality of specialized classifiers being smaller than the number of features used by the monolithic classifier; and

wherein human mouth detection and tracking in video sequences occurs when the tree classifier is executed.

6. The method of claim 5, further comprising:

training each of the plurality of specialized classifiers with a boosting algorithm.

7. The method of claim 5, further comprising repeating elements of the method until a desired depth is achieved.

8. An article, comprising a machine-readable medium including machine-executable instructions operative to cause a machine to perform operations comprising:

build a tree classifier, which rejects non-object patterns in input data representing real world objects, including a plurality of parent nodes, wherein the tree classifier is stored on a machine-readable medium and is trained to perform human mouth detection and tracking in video sequences; and

for a parent node in the tree classifier, select between a monolithic classifier as a child node and a plurality of specialized classifiers as child nodes for said parent node;

wherein the instructions operative to cause the machine to select comprise instructions operative to cause the machine to;

determine a computational complexity of a monolithic classifier trained with a plurality of positive and negative samples; and

determine a computational complexity of a plurality of specialized classifiers trained with the plurality of positive and negative samples, each of the specialized classifiers being trained with the plurality of negative samples and a different subset of the plurality of positive samples; and

perform human mouth selection and tracking in video sequences using the trained tree classifier.

9. The article of claim 8, wherein the instructions operative to cause the machine to determine a computational complexity of the monolithic classifier comprise instructions operative to cause the machine to determine a number of features used by the monolithic classifier, and the instructions operative to cause the machine to determine a computational complexity of the plurality of specialized classifiers comprise instructions operative to cause the machine to determine a number of features used by the plurality of specialized classifiers.

10. The article of claim 8, wherein the instructions operative to cause a machine to perform operations further comprise instructions operative to cause the machine to train the monolithic classifier and the plurality of specialized classifiers with a boosting algorithm.

11. The article of claim 8, wherein the instructions operative to cause a machine to perform operations further comprise instructions operative to cause the machine to train the monolithic classifier and the plurality of classifiers to have a selected hit rate and a selected false alarm rate.

12. An article comprising a machine-readable medium including machine-executable instructions operative to cause a machine to perform operations comprising:

build a tree classifier, which rejects non-object patterns in input data representing real world objects, wherein the tree classifier is stored on a machine-readable medium and is trained to perform human mouth detection and tracking in video sequences, the building including;

identify a plurality of positive samples and a plurality of negative samples in a plurality of patterns;

pass the plurality of positive samples and the plurality of negative samples to a node in the tree classifier;

determine a number of features used by a monolithic classifier trained with said plurality of positive samples and said plurality of negative samples;

cluster the plurality of positive samples into a plurality of subsets;

train each of a plurality of specialized classifiers with the plurality of negative samples and a different one of said plurality of subsets;

determine a number of features used by the plurality of specialized classifiers; and

select the plurality of specialized classifiers in response to the number of features used by the plurality of specialized classifiers being smaller than the number of features used by the monolithic classifier; and

perform human mouth detection and tracking in video sequences using the trained tree classifier.

13. The article of claim 12, further comprising instruction operative to cause the machine to:

train each of the plurality of specialized classifiers with a boosting algorithm.