US20090210362A1

US20090210362A1 - Object detector trained using a working set of training data

Info

Publication number: US20090210362A1
Application number: US12/030,876
Authority: US
Inventors: Rong Xiao; Xiao-ou Tang
Original assignee: Microsoft Corp
Current assignee: Microsoft Technology Licensing LLC
Priority date: 2008-02-14
Filing date: 2008-02-14
Publication date: 2009-08-20
Also published as: US8099373B2

Abstract

An object detector that includes a number of weak classifiers can be trained using a subset (a “working set”) of training data instead of all of the training data. The working set can be updated so that, for example, it remains representative of the training data. A decision to update the working set may be made based on the false positive sample rate—if that rate falls below a threshold value, an update of the working set can be triggered.

Description

BACKGROUND

Automated object detection and/or recognition (ODR) can be used to detect types or classes of physical objects—from simple objects such as geometric shapes to more complex objects such as geographic features and faces—in raw image data (still or video). ODR can also be used to detect audio objects such as songs or voices in raw audio data. A myriad of different techniques have been developed for ODR.
Face detection in particular has attracted much attention due to the potential value of its applications as well as its theoretical challenges. Techniques known by names such as boost cascade and boosting have been somewhat successful for face detection. Still, robust detection is challenging because of variations in illumination and expressions.
A boost cascade detector uses a number of “weak” classifiers that are unified to produce a “strong” classifier. A large set of training data can be used to train the weak classifiers to recognize the possible variations in the features of the object to be detected. However, the computational costs and memory demands of training a detector on a large set of training data are unacceptably high. To put this in perspective, weeks have been spent to train a detector with 4297 features on a training set of 4916 faces. To date, the largest known set of positive samples used for training contains 20,000 face samples.

SUMMARY

An object detector that includes a number of weak classifiers can be trained using a subset (a “working set”) of training data instead of all of the training data. The working set can be updated so that, for example, it remains representative of the training data. A decision to update the working set may be made based on the false positive sample rate - if that rate falls below a threshold value, an update of the working set can be triggered.
This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings, which are incorporated in and form a part of this specification, illustrate embodiments and, together with the description, serve to explain the principles of the embodiments:

FIG. 1 is a block diagram showing one embodiment of a computer system environment.

FIG. 2 is a block diagram showing inputs and outputs for training an object detector in one embodiment.

FIG. 3 is a flowchart of one embodiment of a computer-implemented method for training an object detector.

FIGS. 4 and 5 are flowcharts of embodiments of computer-implemented methods for updating a working set of training data.

FIG. 6 is a flowchart of one embodiment of a method for classifying a sample using an object detector.

FIG. 7 is a flowchart of a method for building a Bayesian Stump.

DETAILED DESCRIPTION

Some portions of the detailed descriptions which follow are presented in terms of procedures, logic blocks, processing and other symbolic representations of operations on data bits within a computer memory. These descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. In the present application, a procedure, logic block, process, or the like, is conceived to be a self-consistent sequence of steps or instructions leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, although not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated in a computer system.
It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present application, discussions utilizing the terms such as “accessing,” “training,” “updating,” “initializing,” “determining,” “reducing,” “selecting,” “adjusting,” “removing,” “adding,” “bootstrapping,” “calculating” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.
Embodiments described herein may be discussed in the general context of computer-executable instructions residing on some form of computer-usable medium, such as program modules, executed by one or more computers or other devices. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. The functionality of the program modules may be combined or distributed as desired in various embodiments.
By way of example, and not limitation, computer-usable media may comprise computer storage media and communication media. Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, random access memory (RAM), read only memory (ROM), electrically erasable programmable ROM (EEPROM), flash memory or other memory technology, compact disk ROM (CD-ROM), digital versatile disks (DVDs) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store the desired information.
Communication media can embody computer-readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, radio frequency (RF), infrared and other wireless media. Combinations of any of the above should also be included within the scope of computer-readable media.
FIG. 1 is a block diagram showing elements of a computer system environment in one embodiment. FIG. 1 shows a block diagram of one embodiment of an exemplary computer system 100 upon which embodiments described herein may be implemented.
In its most basic configuration, the system 100 includes at least one processing unit 102 and a memory 104. Depending on the exact configuration and type of computing device, the memory 104 may be volatile (such as RAM), non-volatile (such as ROM, flash memory, etc.) or some combination of the two. This most basic configuration is illustrated in FIG. 1 by dashed line 106. The system 100 may also have additional features/functionality. For example, the system 100 may also include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated in FIG. 1 by removable storage 108 and non-removable storage 110.
The system 100 may also have input device(s) 114 such as a keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s) 116 such as a display, speakers, printer, etc. may also be included. All these devices are well know in the art and need not be discussed at length here.
The system 100 may operate in a networked environment using logical connections to one or more remote servers, which instead may be a personal computer (PC), a router, a network PC, a peer device or other common network node, and which may include many or all of the elements described above relative to the system 100. The logical connections may include a local area network (LAN) and a wide area network (WAN), but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet. When used in a networking environment, the system 100 can be connected to the network through communication connection(s) 112.
In the example of FIG. 1, the memory 104 includes computer-readable instructions, data structures, program modules and the like associated with an operating system 150, such as but not limited to the WINDOWS™ brand operating system. In the present embodiment, the operating system 150 forms a platform for executing software such as an object detection and/or recognition (ODR) classifier (or detector) 156 and an ODR trainer 160. However, both the detector 156 and trainer 160 need not be implemented on a single computer system. For example, the trainer 160 may be made available to the detector 156 as a suitable distributed function, perhaps distributed over several computer systems. Similarly, the training data 162 need not reside in a single database, solely on a single computer system, or on the same computer system(s) as the detector 156 and the trainer 160.
The training data 162 may include a set S of classified samples {x_i, y_u}, i=1, . . . , n, where x_iεX; x_iis a sample unit (e.g., a file or record) of raw data that either includes or does not include a particular class (type) of object; y_iis an object classification label corresponding to a classification of the sample x_i; and n is any suitable number of samples. On the space X, a set of feature extractors Φ={φ_j}, j=1, . . . , m, are defined to map X→R, where R is the one-dimensional space of real numbers and m is any suitable number. The features φ_jcan be linear (e.g., wavelet transforms) or nonlinear (e.g., local binary pattern filters). The object classification labels y_imay be taken from a set of object classification labels {ω_c}, c=1, . . . , C, where C may be any suitable number. The training data 162 may be utilized by the ODR trainer 160 to build an ODR detector 156 capable of detecting object classes {ω_c}.
As an example, the raw samples x_imay be static (still) images. In one embodiment, a training sample x_iis a 24×24 image that is cropped from a larger image. In one embodiment, a training sample is labeled as a positive sample if it contains one human face. If a training sample does not include a face or includes two or more faces, relatively small faces, or a portion of a face, then the sample is labeled as a negative sample. The set of object classification labels may be {ω₁, ω₂}, where ω₁(y_i=1) corresponds to a positive classification and ω₂(y_i=−1) corresponds to a negative classification.
FIG. 2 is a block diagram showing inputs and outputs useful for training an object detector 156 in one embodiment. In the present embodiment, the inputs include the training data 162, a target detection rate D_target, a target number T of weak classifiers, and a dynamic working set update rate f_u. The outputs include the weak classifiers h_t(t=1, 2, . . . , T) and a rejection rate r_tfor each of the weak classifiers.
The training data 162 may include billions of samples. As will be elaborated on, even for such a massive set of training data consisting of large numbers of both positive and negative samples, the ODR classifier 156 can be trained efficiently and accurately without overwhelming computational resources, and in far less time than that needed for conventional training methods. Instead of training using the entire set of training data 162, a relatively small “dynamic working set” (S_w) 210 is used. The dynamic working set consists of a subset of positive samples P_wand another subset of negative samples Q_w.
The positive and negative samples in the training data 162 are properly labeled as such. The positive samples in the dynamic working set 210 are randomly selected from the positive samples in the training data 162, and the negative samples in the dynamic working set are randomly selected from the negative samples in the training data. The remaining negative samples in the training data 162 are reserved for subsequent negative sample bootstrapping. A set of validation samples P_vis also randomly selected from the positive samples in the training data 162. As will be seen, the dynamic working set 210 can be updated with new samples if/when its distribution is less representative of the entire set of training data 162.
FIG. 3 is a flowchart 300 of one embodiment of a computer-implemented method for training an object detector. FIGS. 4 and 5 are flowcharts 400 and 500, respectively, of embodiments of computer-implemented methods for updating a working set of training data. FIG. 6 is a flowchart 600 of one embodiment of a method for classifying a sample using an object detector. FIG. 7 is a flowchart 700 of a method for building a Bayesian Stump. Although specific steps are disclosed in the flowcharts 300, 400, 500, 600 and 700 (300-700), such steps are exemplary. That is, various other steps or variations of the steps recited in the flowcharts 300-700 can be performed. The steps in the flowcharts 300-700 may be performed in an order different than presented. Furthermore, the features of the various embodiments described by the flowcharts 300-700 can be used alone or in combination with each other. In one embodiment, the flowcharts 300-700 can be implemented by the system 100 (FIG. 1) as computer-readable program instructions stored in a memory unit and executed by a processor.
With reference first to FIG. 3, in block 310, the positive samples in the training data 162 are randomly sampled to form the positive working set P_w, and the negative samples in the training data are also randomly sampled to form the negative working set Q_w, where N_pis the number of samples in the positive working set and N_qis the number of samples in the negative working set. While the training data 162 may include billions of samples, the dynamic working set 210 may include on the order of tens of thousands of samples. The target detection rate D_target, the target number T of weak classifiers, and the dynamic working set update rate f_uare user-specified values.
In block 320, a set of classifier weights is initialized. More specifically, the weight w_iof each sample x_iin the dynamic working set 210 is initialized to a value of one (1). Also, a detection rate D* is initialized to a value of 1.
Blocks 330 through 390 are performed for each weak classifier t=1, 2, . . . , T. In block 330, the weight w_t,ifor each sample x_iin the dynamic working set 210 is normalized to guarantee an initial distribution of weights while satisfying the following condition:
Σ_x _i _εP _ww_t,i=Σ_x _i _εQ _ww_t,i, (1)
Thus, initially, the sum of the weights of the positive samples and the sum of the weights of the negative samples in the dynamic working set 210 are each equal to 0.5.
In block 340, the detection rate D* for the current training stage t is updated as follows:
D _t *=D _t−1 *−v _t; (2)
v_t=1−ke^−αt/T; (3)
where v_tis the false negative rate, k is a normalization factor that satisfies the target detection rate and α is a free parameter that can be used to trade between speed and accuracy. The smaller the value of α, the faster the detector. As noted above, D₀*=1. Thus, instead of tuning the detection rates one-by-one, the false negative rate v_tis assumed to change exponentially in each stage t.
In block 350, a weak classifier is trained on the dynamic working set 210 for each feature φ_j. For face detection, the features φ_jmay be, for example, Haar-like features, Gabor wavelet features, and/or EOH (edge orientation histogram) features. In one embodiment, multiple levels of feature sets are used based on the dynamic cascade structure, with the less computationally intensive features applied first. Thus, for example, during training, Haar-like features are used first, then when the false positive rate drops below a predefined threshold, Gabor and EOH features can be used to further improve the detection rate. Consequently, computational cost can be reduced and detection accuracy improved, because most negative samples are rejected in the evaluation of the Haar-like features. Furthermore, in comparison to post-filtering methods, a global confidence output is provided, and combining classification results from multiple models is avoided, resulting in a simpler and more robust detector.
In block 360, for weak classifier t, the “best” feature φ_tis chosen and added to the detector 156. In one embodiment, the best feature φ_tis the feature with the lowest Bayesian error in comparison to the other features. In one such embodiment, Bayesian error is determined using a technique referred to herein as Bayesian Stump, which is described below in conjunction with FIG. 7.
Continuing with reference to FIG. 3, in block 370, the validation set P_vis used to adjust the rejection threshold r_tfor the feature selected in block 360, under the constraint that the detection rate does not fall below the detection rate D* determined in block 340. In other words, a rejection threshold is determined for each weak classifier, by adjusting the rejection threshold r_tfor that classifier to achieve the adjusted target detection rate D*.
In contrast to conventional methods, the false negative samples rejected in stage t are removed from the dynamic training set 210. Experimental results show that this improves the training converge rate and results in a detector with fewer features.
In block 380, the weights of the samples in the dynamic working set 210 are adjusted as follows:
$\begin{matrix} w_{t + 1, i} = {\begin{matrix} w_{t, i} e^{- y_{i} H_{t} (x_{i})}, H_{t} (x_{i}) \geq r_{t} \\ 0, H_{t} (x_{i}) < r_{t} \end{matrix}; & (4) \end{matrix}$
where H_t(x_i) is a value that is determined as described in conjunction with FIG. 6, below.
In block 390 of FIG. 3, the dynamic working set 210 is updated if the false positive rate falls below the update rate f_u. A continuous update strategy is implemented if f_u=1, and the update process is disabled if f_u=0. A value of 0.6 for f_uprovides a good trade-off between detector performance and the computational cost of training. The flowchart 300 then returns to block 330, to repeat the process for the next training stage, until a T-stage detector 156 is trained.
FIG. 4 is a flowchart 400 of an embodiment of a method for updating the positive working set P_w. As described above, in block 380 of FIG. 3, the weights of the samples in the dynamic working set 210 are adjusted. In block 410 of FIG. 4, the samples with the smallest weights are then removed from the positive working set. In one embodiment, ten percent of the total weight sum is removed.
In block 420, as mentioned above, false negative samples have also been removed from the positive working set. In block 430, a new positive working set of N_psamples is produced by randomly selecting additional positive samples from the training data 162.
FIG. 5 is a flowchart 500 of an embodiment of a method for updating the negative working set Q_w. As described above, in block 380 of FIG. 3, the weights of the samples in the dynamic working set 210 are adjusted. In block 510 of FIG. 5, the samples with the smallest weights are then removed from the negative working set. In one embodiment, ten percent of the total weight sum is removed.
In block 520, the weak classifier h_tis used to bootstrap false positive samples from the negative set of the training data 162, until the negative working set has N_qsamples. Thus, in contrast to conventional methods that bootstrap continuously at high computational cost, bootstrapping is performed relatively infrequently.
FIG. 6 is a flowchart 600 of one embodiment of a method for classifying a sample using an object detector. The detector 156 can be implemented as follows, for t=1, . . . , T:
H ₁(x)=h ₁(x); (5a)
H ₂(x)=H ₁(x)+h ₂(x)=h ₁(x)+h ₂(x); (5b)
H _t(x)=H _t−1(x)+h _t(x)=h ₁(x)+h ₂(x)+ . . . +h _t(x); and (5c)
H _T(x)=H _T−1(x)+h _T(x)=h ₁(x)+h ₂(x)+ . . . +h _T(x). (5d)
As discussed above, a rejection threshold r_tis calculated for each weak classifier. In general, a sample x_iis classified as a positive sample if all t of the results H_t(x_i) are greater than or equal to r_t. A sample x_iis classified as a negative sample if any one of the results H_t(x_i) is less than r_t. Accordingly, an object detection procedure can be implemented as follows.
Using equation (5a), in block 610, a first result H₁(x_i) is determined using a first weak classifier h₁(x_i). Also, a rejection rate r₁associated with the first weak classifier is determined as described in conjunction with FIG. 3 above. If H₁(x_i) is less than r₁, then the detection procedure is halted for the current sample and the sample is classified as negative (block 640). Otherwise, the flowchart 600 proceeds to block 620.
In block 620 of FIG. 6, based on equation (5b), a second result H₂(x_i) is determined using a second weak classifier h₁(x_i) and the result H₁(x_i) from the first weak classifier. Also, a rejection rate r₂associated with the second weak classifier is determined. If H₂(x_i) is less than r₂, then the detection procedure is halted for the current sample and the sample is classified as negative (block 640).
The process described in block 620 is repeated for each subsequent value of t until t=T. In general, a result H_t(x_i) is determined using a t^thweak classifier h_t(x_i) and the result H_t−1(x_i) from the preceding (t−1) weak classifier. Also, a rejection rate r_tassociated with the t^thweak classifier is determined. If H_t(x_i) is less than r_t, then the detection procedure is halted for the current sample and the sample is classified as negative.
In block 630, the sample x_iis classified as positive because all t of the results H_t(x_i) are greater than or equal to the respective value of r_t. Because most samples are negative, computational costs are significantly reduced, because the evaluation of many samples will not proceed through all T stages of the object detector. The steps in the flowchart 600 can be repeated for each sample to be classified.
FIG. 7 is a flowchart 700 of a method for building a Bayesian Stump. In a two-category classification problem such as face detection, the probability of error (Bayesian error, BE) is:
$\begin{matrix} BE = P (error) = \int_{- \infty}^{\infty} \min [P (ω_{1}, x), P (ω_{2}, x)] \partial x . & (6) \end{matrix}$
Because P(ω_c,x) may not be available, a histogram method referred to as Bayesian Stump is introduced to estimate probability distributions in the feature space. Each feature φ_j(x) can be discretized into K intervals σ_k=(r_k−1, r_k) having widths |σ_k|=r_k−r_k−1, kε{1, . . . , K}. {r_k}, with kε{0, . . . , K}, are the thresholds. The histogram of p(φ_j(x),ω_c), cε{1,2} is:
$\begin{matrix} p (k, ω_{c}) = \int_{φ_{j} (x) \in σ_{k}} p (φ_{j} (x), ω_{c}) \partial φ_{j} (x) = \sum_{\begin{matrix} φ_{j} (x) \in σ_{k} \\ y_{i} = ω_{c} \end{matrix}} w_{i}; & (7) \end{matrix}$
where w_iis the weight distribution of x_i.
Using these histograms, a conventional decision stump classifier can be extended to a single-node, multi-way split decision tree. In each interval σ_k, a decision is made that minimizes the Bayesian error {circumflex over (B)}Ê_k(φ_j), where:
{circumflex over (B)}Ê _k(φ_j)=min[p(k,ω ₁), p(k,ω ₂)]. (8)
The overall Bayesian error of Bayesian Stump is:
$\begin{matrix} \hat{BE} (φ_{j}) = \sum_{k = 1}^{K} {\hat{BE}}_{k} (φ_{j}) = \sum_{k = 1}^{K} \min [\sum_{\begin{matrix} φ_{j} (x_{i}) \in σ_{k}, \\ y_{i} = ω_{1} \end{matrix}} w_{i}, \sum_{\begin{matrix} φ_{j} (x_{i}) \in σ_{k}, \\ y_{i} = ω2 \end{matrix}} w_{i},] . & (9) \end{matrix}$
In order to further analyze the relationship between {circumflex over (B)}Ê(φ_j) and the expected Bayesian error BE(φ_j), the following definition is introduced: suppose σ is an interval, and f and g are two functions defined on σ. If for any x_r,x_sεσ, (f(x_r)−g(x_r))*(f(x_s)−g(x_s))≧0, then the region σ is defined to be the consistent region of functions f and g. From this definition, if ∀r_k, subject to −∞=r₀< . . . <r_k=∞, then:
{circumflex over (B)}Ê(φ_j)≧BE(φ_j), (10)
with equality if and only if ∀k, σ_kis the consistent region of f(x)=p(ω₁,φ_j(x)) and g(x)=p(ω₂,φ_j(x)). Equation (10) shows that {circumflex over (B)}Ê(φ_j) is an upper bound of the overall Bayesian error BE(φ_j). Therefore, the histogram classifier can be optimized mathematically by finding a set of thresholds {r_k} that minimize BE(φ_j).
With reference to FIG. 7, a K-bin Bayesian Stump is built. Compared to a binary-split decision stump, Bayesian Stump significantly reduces the Bayesian error and results in a boost classifier with fewer features. Moreover, Bayesian Stump can easily be extended to a lookup table (LUT) type of weak classifier by using log-likelihood output instead of binary output in every interval.
In the discussion of FIG. 7, a training set S={x_i′, y_i}, x_i′=φ(x_i), and a weight set W={w_i}, i=1, . . . , n are used. In block 710, to estimate p(x′,ω₁) and p(x′,ω₂), histograms are built by quantizing feature x′ into L bins, where L>>K.
In block 720, adjacent consistent intervals σ_land σ_l+1are merged to produce a set of consistent regions {σ′_l}, l=1, . . . , L′. More specifically, while L′>K, adjacent intervals σ′_l*−1, σ′_l*and σ′_l*+1, where l*=argmin_l|p(l,ω₁)−p(l,ω₂)|. While L′>K, the interval σ′_l*is iteratively split by maximizing mutual information gain, l*=argmax_l|min(p(l,ω₁),p(l,ω₂))|.
In block 730, on each interval σ_k, the following decision rule is used to give the binary prediction output:
P(error|x)=min[P(ω₁ |x),P(ω₂ |x)]. (11)
In this manner, an LUT function h(k) is built on intervals σ_k, k=1, . . . , K.
In summary, a robust and stable detector can be trained on a massive data set. The distribution of the massive data set can be estimated by sampling a smaller subset of the data (a working set). The detector is fully automatic without using training parameters for classifiers in each stage. The detector can be trained on large amounts of both positive and negative samples while providing a good trade-off between detection speed and accuracy. Training using multiple feature sets is supported. Also, efficient parallel distributed learning is enabled. The use of Bayesian Stump further improves efficiency.
The working set can be updated continuously, for example, after each new weak classifier is trained. Alternatively, the working set can be updated based on a threshold as described herein. Based on experimental results, performance using either of these strategies is similar. However, the use of a threshold is more computationally efficient since updates are performed less frequently (not continuously).
As a demonstration of efficiency, over 531,000 positive samples were generated and almost ten billion negative samples were collected. These samples were used to generate a dynamic working set and a validation set. Using about 30 desktop computers, it took less than seven hours to train a detector with 700 features on this massive data set.
In the foregoing specification, embodiments have been described with reference to numerous specific details that may vary from implementation to implementation. Thus, the sole and exclusive indicator of what is, and is intended by the applicant to be, the invention is the set of claims that issue from this application, in the specific form in which such claims issue, including any subsequent correction. Hence, no limitation, element, property, feature, advantage, or attribute that is not expressly recited in a claim should limit the scope of such claim in any way. Accordingly, the specification and drawings are to be regarded in an illustrative rather than a restrictive sense.

Claims

1. A computer-implemented method of training an object detector comprising a plurality of weak classifiers, said method comprising:

accessing a working set of samples selected from of a set of training data, said working set comprising a subset of positive samples that include an object class to be detected and a subset of negative samples that do not include said object class;

training a weak classifier of said object detector on said working set of samples; and

updating said working set when a false positive sample rate for said weak classifier falls below a threshold value.

2. The method of claim 1 further comprising initializing weights of samples in said working set such that the sum of weights associated with said positive samples and the sum of weights associated with said negative samples are substantially equal.

3. The method of claim 1 further comprising determining a detection rate for said weak classifier, wherein said detection rate for said weak classifier is determined by reducing a target detection rate for said object detector by a calculated value that depends on both the total number of said weak classifiers and the number of said weak classifiers trained before said weak classifier.

4. The method of claim 3 further comprising:

training said weak classifier for a plurality of features;

selecting a feature from said plurality of features, said feature useful for detecting said object class; and

adjusting a rejection threshold associated with said weak classifier to achieve said detection rate for said weak classifier.

5. The method of claim 1 further comprising:

adjusting weights assigned to samples in said working set; and

removing samples from said subset of positive samples and from said subset of negative samples according to their respective weights, wherein smallest-weighted samples are removed first.

6. The method of claim 1 further comprising removing a false negative sample from said working set.

7. The method of claim 1 wherein said updating comprises adding a sample to said subset of negative samples by bootstrapping a false positive sample from said set of training data into said subset of negative samples.

8. The method of claim 1 wherein said updating comprises adding samples to said subset of positive samples by randomly selecting positive samples from said set of training data.

9. The method of claim 1 wherein said training comprises:

using a first set of features but not a second set of features for a first part of said training; and

using said second set of features for a subsequent part of said training once said false positive sample rate falls below said threshold value.

10. A computer-implemented method of classifying a sample using a cascade object detector, said method comprising:

determining a first result by evaluating said sample using a first weak classifier;

classifying said sample as a negative sample that does not include an object class if said first result is less than a first rejection threshold associated with said first weak classifier, and otherwise determining a second result by evaluating said sample using a second weak classifier; and

classifying said sample as a negative sample that does not include an object class if said first result plus said second result is less than a second rejection threshold associated with said second weak classifier, wherein otherwise said sample is a candidate for classification as a positive sample depending on evaluation results determined using any subsequent weak classifiers.

11. The method of claim 10 further comprising training said first weak classifier for a plurality of features, said training comprising:

accessing a working set of samples selected from of a set of training data, said working set comprising a subset of positive samples that include said object class and a subset of negative samples that do not include said object class;

initializing weights of samples in said working set;

determining a first detection rate for said first weak classifier, wherein said first detection rate is determined by reducing a target detection rate for said object detector by a calculated value that depends on the total number of weak classifiers comprising said object detector and the number of said weak classifiers trained before said first weak classifier;

selecting said first rejection threshold to achieve said first detection rate; and

selecting a first feature from said plurality of features.

12. The method of claim 11 further comprising training said second weak classifier for said plurality of features, said training of said second weak classifier comprising:

adjusting said weights of said samples in said working set;

removing samples from said subset of positive samples and from said subset of negative samples according to their respective weights;

updating said working set if a false positive sample rate for said first weak classifier falls below a threshold value;

determining a second detection rate for said second weak classifier, wherein said second detection rate is determined by reducing said target detection rate by a second calculated value that depends on the total number of weak classifiers comprising said object detector and the number of said weak classifiers trained before said second weak classifier;

selecting said second rejection threshold to achieve said second detection rate; and

selecting a second feature from said plurality of features.

13. The method of claim 12 wherein said updating comprises:

adding a sample to said subset of negative samples by bootstrapping a false positive sample from said set of training data into said subset of negative samples;

adding samples to said subset of positive samples by randomly selecting positive samples from said set of training data; and

removing a false negative sample from said working set.

14. The method of claim 12 wherein said adjusting comprises calculating a new weight for said sample if said first result is not less than said first rejection threshold and otherwise assigning a weight of zero to said sample.

15. A computer-implemented method of training an object detector comprising a plurality of weak classifiers, said method comprising:

training a weak classifier of said object detector on said working set of samples;

using said weak classifier, bootstrapping a false positive sample from said set of training data into said subset of negative samples; and

removing a false negative sample identified by said weak classifier from said working set.

16. The method of claim 15 further comprising comparing a false positive sample rate for said weak classifier to a threshold value, wherein said bootstrapping is performed if said false positive sample rate falls below said threshold.

17. The method of claim 15 further comprising initializing weights of samples in said working set such that the sum of weights associated with said positive samples and the sum of weights associated with said negative samples are substantially equal.

18. The method of claim 15 further comprising determining a detection rate for said weak classifier, wherein said detection rate for said weak classifier is determined by reducing a target detection rate for said object detector by a calculated value that depends on the total number of said weak classifiers and the number of said weak classifiers trained before said weak classifier.

19. The method of claim 18 further comprising:

training said weak classifier for a plurality of features;

20. The method of claim 15 further comprising:

adjusting weights of samples in said working set; and