International Journal of Computer Vision 56(3), 151–177, 2004

c 2004 Kluwer Academic Publishers. Manufactured in The Netherlands.

Object Detection Using the Statistics of Parts

HENRY SCHNEIDERMAN AND TAKEO KANADE∗

Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA
hws@[Link]
tk@[Link]

Received April 20, 2001; Revised February 15, 2002; Accepted March 6, 2002

Abstract. In this paper we describe a trainable object detector and its instantiations for detecting faces and cars
at any size, location, and pose. To cope with variation in object orientation, the detector uses multiple classifiers,
each spanning a different range of orientation. Each of these classifiers determines whether the object is present at
a specified size within a fixed-size image window. To find the object at any location and size, these classifiers scan
the image exhaustively.
Each classifier is based on the statistics of localized parts. Each part is a transform from a subset of wavelet
coefficients to a discrete set of values. Such parts are designed to capture various combinations of locality in space,
frequency, and orientation. In building each classifier, we gathered the class-conditional statistics of these part values
from representative samples of object and non-object images. We trained each classifier to minimize classification
error on the training set by using Adaboost with Confidence-Weighted Predictions (Shapire and Singer, 1999). In
detection, each classifier computes the part values within the image window and looks up their associated class-
conditional probabilities. The classifier then makes a decision by applying a likelihood ratio test. For efficiency, the
classifier evaluates this likelihood ratio in stages. At each stage, the classifier compares the partial likelihood ratio to a
threshold and makes a decision about whether to cease evaluation—labeling the input as non-object—or to continue
further evaluation. The detector orders these stages of evaluation from a low-resolution to a high-resolution search
of the image. Our trainable object detector achieves reliable and efficient detection of human faces and passenger
cars with out-of-plane rotation.

Keywords: object recognition, object detection, face detection, car detection, pattern recognition, machine learn-
ing, statistics, computer vision, wavelets, classification

1. Introduction Our goal in this research is not to understand how

humans perceive, but to create computer methods for
Object detection is a big part of people’s lives. We, as automatic object detection. Automated object detec-
human beings, constantly “detect” various objects such tion has many potential uses including image retrieval.
as people, buildings, and automobiles. Yet it remains Digital image collections have grown dramatically in
a mystery how we detect objects accurately and with recent years. Corbis estimates it has more than 67 mil-
little apparent effort. Comprehensive explanations have lion images in its collection. The Associated Press col-
defied psychologists and physiologists for more than a lects and archives an estimated 1,000 photographs a
century. day. Currently, the usability of these collections is lim-
ited by a lack of effective retrieval methods. To find a
∗ Thiswork was supported in part by the Advanced Research and
specific image in such a collection, people must search
Development Activity (ARDA) under contract number MDA904- using text-based captions and primitive image features
00-C-2109. such as color and texture. Automatic object detection
152 Schneiderman and Kanade

could be used to extract more information from these exists in the world at large. For example, cars vary in
images and help label and categorize them. Improved size, shape, coloring, and in small details such as the
search methods will make these databases accessible headlights, grille, and tires. The lighting, surrounding
to wider groups of users, such as law enforcement scenery, and an object’s pose affect its appearance. A
agencies, medical practitioners, graphic and multime- car detection algorithm must also distinguish cars from
dia designers, and artists. Automatic object detection all other visual patterns that may occur in the world,
could also be useful in photography. As camera tech- such as similar looking rectangular objects.
nology changes from film to digital capture, cameras
will become part optics and part computer. Such a cam- 1.2. Object Detection Using Classifiers
era could automatically focus, color balance, and zoom
on a specified object of interest, say, a human face. Also, Our method for object detection factors out variation in
detectors of a specific object have specialized uses: face the pose of the object. Our object detector uses a set of
detectors for face identification and car detectors for classifiers, each of which determines whether the object
monitoring traffic. is present at a specific pose in a fixed-size rectangular
image window. For faces, the detector uses classifiers
1.1. Challenges in Object Detection for three discrete poses: front, left profile, and right
profile. Taking advantage of facial symmetry, we only
Automatic object detection is a difficult undertaking. In needed to train classifiers for the frontal and right pro-
over 30 years of research in computer vision, progress file viewpoints shown in Fig. 1(a), and we built a left
has been limited. The main challenge is the amount profile detector by reflecting the right profile detector.
of variation in visual appearance. An object detector For cars, we use 15 discrete viewpoints, and by exploit-
must cope with both the variation within the object ing symmetry again, we only trained classifiers for the
category and with the diversity of visual imagery that eight viewpoints as shown in Fig. 1(b). These classifiers

Figure 1. Multiple classifiers are built to deal with appearance changes due to pose. (a) For faces, classifiers are trained on 2 viewpoints and
(b) for cars, classifiers are trained on 8 viewpoints.
 Object Detection Using the Statistics of Parts 153

Figure 2. Detection by scanning classifier across image in both (a) position and (b) scale.

tolerate a small range of variation in object orientation, ance. One hypothetical method is to build the classi-
size, and alignment within the image window. fier as a table, enumerating the most probable classi-
To perform detection, we scan each classifier over the fication for every combination of input variables (see
original image and a series of resized versions of the Table 1).
original image, as illustrated in Fig. 2, where the rect- Such a table would give the smallest average clas-
angular blocks indicate successive applications of the sification error, assuming we could label each input
classifier. This exhaustive scanning operation makes it appropriately. Obviously, this table is not possible in
possible to find the object over variation in location practice. Even a classifier over a 20 × 20 input win-
and size, and can be done with surprising efficiency, dow requires 256400 ≈ 10964 entries! Classifier design,
as we will describe later in Section 4. Often, the same therefore, must take advantage of the constraints of the
entity is detected by more than one view-based detec-
tor, such as the woman in the foreground of the image Table 1. Ideal but infeasible classifier.
in Fig. 3. To determine the final detection outcome the
(1, 1) (1, 2) ... (20, 20) Classification
detector combines the results from various viewpoint
classifiers by using simple arbitration heuristics, in the 0 0 ... 0 Non-object
case of Fig. 3, selecting the frontal viewpoint. 0 0 ... 1 Non-object
... ... ... ... ...
1.3. Parts-Based Representation for Classifier 35 45 ... 28 Object
... ... ... ... ...
The central research issue is how to design a ba- 255 255 ... 255 Non-object
sic classifier that can cope with variation in appear-
154 Schneiderman and Kanade

Figure 3. Combining the results from multiple view-based detectors.

visual world in order to obtain a much more compact composed from disjoint groups of variables; a vari-
representation. able can be re-used in multiple parts. In this paper, we
In choosing a representation for the classifier, we can denote parts with italics to refer to this more general
differentiate between two types of approaches: global meaning.
and parts-based. Global representations, like an ideal This parts-based approach is based on an implicit
table, try to model the joint behavior of all input vari- assumption that for a given object, each pixel is sta-
ables. Computational and storage limitations, however, tistically related with some pixels more than others.
do not allow for a fully general function of the in- Under this assumption, a global model does not make
put variables. As a practical solution, global models good use of modeling resources, as it makes no dis-
must use limited functional forms of the input vari- tinction whether a combination of pixels is useful or
ables, such as linear, quadratic, or third order. Alterna- irrelevant. A quadratic filter, for example, represents
tively, global models may reduce the dimensionality of correlation within each pair of pixels; the majority of
the input space using certain transforms or a reduction these pairs may have negligible statistical dependency.
in the number of input variables. A higher-order model A parts-based approach, in contrast, can select each
or even a non-parametric method can then describe the part to represent a small group of variables that are
joint behavior of this reduced set of variables. known to be statistically dependent. Such an approach
In the parts-based approach, the input variables are avoids devoting representational resources to weak re-
grouped into sets, where the relationships within each lationships and instead allocates richer models to the
set are more accurately modeled than those across sets. stronger relationships.
We refer to each such set as a part. For example, The parts-based assumption becomes more pro-
parts of a face, such as the eyes, nose, and mouth, nounced if statistical dependency is measured among
can be considered as parts and modeled separately. transformed variables that decorrelate the imagery
However, it should be emphasized that parts need not rather than among the original pixels. By decorrelation,
have a natural meaning to us (such as a nose or an statistical dependency will be concentrated in small sets
eye), but could be defined as a group of pixels, or of variables. We chose a wavelet basis as a transform
transform variables, that satisfy certain mathematical for decorrelation because it tends to work well on im-
properties. In addition, these parts do not have to be agery of natural scenes (Field, 1999). In particular, we
 Object Detection Using the Statistics of Parts 155

Figure 4. Pair-wise mutual information between a chosen coefficient location and all other locations in the wavelet transform for frontal faces.

chose a 5/3 linear phase wavelet filterbank (Strang and • Decomposition into parts
Nguyen, 1997).
Experiments support the validity of the parts- Given input variables, such as wavelet coefficients,
based assumption. We measured statistical dependency we form a set of parts, each consisting of a group of
among 5/3 linear phase wavelet coefficients for several variables that are statistically dependent. We then treat
viewpoints of faces and cars. For each viewpoint, we these parts as statistically independent. With this as-
collected the joint probability distribution for each pair sumption, our classifier takes the following form as a
of wavelet coefficients by using a large set of geometri- likelihood ratio test; that is, it decides that the object is
cally aligned images of the object. By quantizing each present if the left side is greater than λ:
coefficient to 5 discrete levels, we represented each dis-

Pr (partr | object)
tribution as a histogram with 25 (5×5) bins. These dis- >λ (1)
tributions allowed us to compute the mutual informa- r Pr (partr | non-object)
tion for each wavelet coefficient pair. Mutual informa-
tion measures the strength of the statistical dependence where partr is a discrete-valued variable obtained as
between the two variables. Figure 4 illustrates some of a function of a chosen group of wavelet coefficients
the results of this experiment for frontal faces. Each within the classification window, Pr (partr | object) rep-
“image” graphically represents the mutual information resents the probability distribution over the discrete
values between one chosen coefficient (indicated by range of partr conditioned on the presence of the object,
an arrow) and all the other coefficients in the wavelet and similarly, Pr (partr | non-object) is conditioned on
transform. The brightness at each location indicates the the absence of the object.
mutual information between the chosen coefficient and Strictly speaking, the assumption of statistical inde-
coefficient at that location. Notice that each coefficient pendence of the parts is not true. Yet, we still obtained
is statistically related only with a relatively small num- accurate classification results; a possible interpretation
ber of the other coefficients (Naturally, since a variable of this will be discussed in Section 2.4.
has the strongest mutual information with itself, the lo-
cation of the chosen coefficient is the brightest point.) • Probabilistic representation of parts
This phenomenon of limited statistical dependency is
typical for faces and cars. Usually, parts are thought of as being binary-valued
and deterministic. For example, an eye can either be
present or absent. However, in Eq. (1), we designed
1.4. Properties of Classifier each partr , to take a range of values. In our face
and car examples, the range was approximately 104 .
We used a combination of the following eight design Our classifier represents these values as probabilistic
choices to develop a parts-based classifier. quantities rather than deterministic quantities; that is,
156 Schneiderman and Kanade

Pr (partr | non-object) and Pr (partr | object) associate a lookup into a table representing the likelihood ratio
probabilities to each value of partr . Pr (partr | object)/Pr (partr | non-object). We can esti-
mate these probability distributions by simply count-
• Parts with locality in space, frequency, and orienta- ing the occurrences of each part value over a large
tion set of training images. A table avoids assumptions
about the distributional structure of part statistics (e.g.,
Our classifier uses a variety of parts to embody var- Gaussian), while retaining good properties for estima-
ious combinations of locality in space, frequency, and tion, including satisfaction of the Cramer-Rao lower
orientation. Some parts represent small regions over bound, closed form solution, and no bias.
high frequencies, other parts represent large regions
over low frequencies, and still other parts are spe- • AdaBoost to weight training examples
cialized in horizontal and vertical information. These
choices are designed to capture common statistical de- To build the overall classifier, we could separately
pendencies in appearance of an object. The wavelet estimate Pr (partr | non-object) and Pr (partr | object),
representation allowed us to directly design parts with and plug them into the likelihood ratio test, Eq. (1).
these locality properties. This approach would give the best possible perfor-
mance (with this functional form) if our training data
• Maximalist collection of parts is truly representative. However, the fact that we have
only a finite set of training examples will limit the esti-
Our classifier represents parts from all areas across mation accuracy, particularly for the non-object class.
the entire extent of the object. This representation could This limitation can be partially overcome by training
be considered maximalist in contrast to a minimal- the classifier to explicitly minimize classification error
ist one that relies on a few features (e.g., eyes, nose, on the training set. We chose to use a unique training
mouth). More information, if used properly, will al- method involving Adaboost with Confidence Weighted
ways improve the detection result. In particular, we Predictions (Shapire and Singer, 1999) that guarantees
have found that parts with even seemingly indistinct to minimize an upper bound on the classification error
cues such as uniform areas are indeed discriminative. on the training set. This method also has the natural in-
terpretation of re-weighting of the training examples.
• Geometric arrangement of parts This method allowed us to count weighted occurrences
of each part value, and thereby retain the advantage of
It should be noted that the geometrical relationships estimating each distribution as a table.
of the parts are implicit in Eq. (1). Each part is de-
fined as a function of a specific group of wavelet coef- • Coarse-to-fine search evaluation strategy
ficients. All wavelet coefficients are represented with
respect to a common coordinate frame affixed to the We use several strategies to make detection compu-
image window to be classified. Therefore, this repre- tationally efficient. In Fig. 2, it may appear that the
sentation captures geometry by placing all parts in a classifier completely re-evaluates each window. How-
common coordinate system. In the next section, this ever, overlapping windows share much information
geometric representation will become more explicit by that does not need to be re-computed. The classifier
an equivalent representation of Eq. (1) in terms of “lo- computes the wavelet transform and the part values
cal operators.” This representation allows for a flexible once, at most, for the entire image scale. We also avoid
configuration of parts in the object unlike a single tem- repeating computations over successive octaves in the
plate that implies a rigid configuration. search across scale. It is not necessary to re-compute
the entire wavelet transform, nor parts that are compu-
• Tables for part statistics tationally equivalent at multiple octaves. The classifier
also does not need to evaluate the complete likelihood
Our classifier represents each set of statistical dis- ratio to make a decision in most cases. A partial eval-
tributions, Pr (partr | non-object) and Pr (partr | object), uation of the likelihood ratio is often sufficient to rule
using tables. This representation is possible because we out the presence of an object. The classifier orders the
have chosen each part to have a discrete range of val- evaluation of the likelihood ratio from parts in coarse
ues. Retrieval of probability values thus involves only resolution to parts in fine resolution. First, the detector
 Object Detection Using the Statistics of Parts 157

evaluates the image at a coarse resolution, reduced by Rewriting Eq. (1) in terms of local operators gives:
a factor of 8 in both directions; that is, evaluation sites

Pr (partr | object)
are spaced 8 pixels apart in the original image. Then
the resolution is reduced by a factor of 4. Such pro- r Pr (partr | non-object)
gressive evaluation techniques enabled us to achieve

Pk ( f k (x, y), x, y | object)
significant computational savings and implement a = (2)
k x,y
Pk ( f k (x, y), x, y | non-object)
relatively efficient algorithm with little penalty in
accuracy.
where each partr corresponds to a unique combination
of k, x, and y.
The classifier then retrieves two probabilities associ-
1.5. Overview of Classifier ated with each operator output f k (x, y). It obtains these
probabilities from two pre-computed probability dis-
Let us overview how our classifier based on Eq. (1) tributions for each operator, Pk ( f k (x, y), x, y | object)
works. The description here is primarily for illustrative and Pk ( f k (x, y), x, y | non-object). Pk ( f k (x, y), x, y |
purposes, and more details can be found in Section 2. object) represents the statistical knowledge of the ob-
The classification algorithm involves three steps, as ject’s appearance. Figure 5 illustrates a case that the
shown in Fig. 5. In the first step, N local operators, probability of output value #5710 from operator “1” at
f k (x, y), k = 1, N , evaluate the image window. The position (0, 0) on the object is 0.53. The other prob-
resulting measurements are discrete-valued. Each out- ability distribution, Pk ( f k (x, y), x, y | non-object), de-
put at each location represents a separate part and the scribes the visual world other than the object.
conglomerate of the outputs from all N operators, each Note that each of these distributions is a joint func-
sampled at all locations, represent the entire set of parts. tion of operator value f k and operator position (x, y)

Figure 5. Classification algorithm overview. N local operators evaluate the image window at nm locations. Class-conditional probabilities are
retrieved for each output and combined in a likelihood ratio test.
158 Schneiderman and Kanade

within the classification window. This joint represen- design is distinctive in that we use multi-dimensional
tation explicitly models the geometric configuration of tables that jointly represent local operator output with
the parts. Recall, also, that each operator takes on a dis- operator position.
crete value, allowing us to represent each probability Much object detection work uses a coarse-to-fine
distribution as a table. search heuristic to reduce computational time (Rowley
Next, the classifier makes a decision by computing et al., 1998; Geman and Flueret, 2001; Romdhani et
a likelihood ratio test as in Eq. (2). It multiplies all the al., 2001; Viola and Jones, 2001). Such methods first
probabilities retrieved from Pk ( f k (x, y), x, y | object) evaluate the entire original image at coarse resolution
in the numerator and divides by the product of the prob- and then selectively evaluate the image at higher res-
abilities from Pk ( f k (x, y), x, y | non-object). It then olution based on the outcome of the lower-resolution
compares the resulting value to a threshold. If the value evaluations. Our coarse-to-fine strategy takes natural
is greater than the threshold, it decides that the object advantage of a wavelet-base multi-resolution image
is present in the window; otherwise, it decides it is not representation.
present.

2. Derivation of Functional Form of Classifier

1.6. Related Work
Based on the design choices we have made in the pre-
The idea of using statistical independence assumptions vious section, we will derive the actual functional form
in probabilistic modeling problems has a long history of our classification algorithm and examine implica-
in the literature of pattern recognition, beginning pos- tions of its underlying assumptions. The final form
sibly with Lewis (1959) and Chow and Liu (1966). In that we will obtain at the end of this section will
computer vision, several researchers have used a parts- be:
like decomposition with an explicit statistical indepen-
dence assumption. Recent representative work includes

Pk ( f k (x, y), [x/M], [y/M] | object)
Burl and Perona (1996), Burl et al. (1998), Geman and >λ
k x,y Pk ( f k (x, y), [x/M], [y/M] | non-object)
Flueret (2001), and Amit (2000), who use binary or
deterministic representations of the parts. Schiele and (3)
Crowley (1996, 2000) use a probabilistic representa-
tion where probability is estimated over the response to where [v] denotes the rounded integer value of v, and
Gaussian derivative filters. However, there is no notion M = 4 or 8. The derivation of Eq. (3) consists of the fol-
of geometry in Schiele and Crowley’s representation. lowing series of transformations and approximations
They only represent the probability distribution of lo- to the ideal, but infeasible, classifier we introduced in
cal operator output, whereas our classifier represents Section 1.3:
probability as a joint function of local operator output
and operator position.
Various parts-based methods differ from each other • Two generalizations to the ideal classifier form
in whether the parts are represented in a rigid or flex- • Wavelet transform of input pixels
ible configuration like ours. Lades et al. (1993) and • Three approximations:
Wiskott et al. (1997) allow for flexibility through a
◦ Statistical independence of parts
flexible graph. Burl et al. (1996, 1998) allow for flexi-
◦ Quantization of part value
bility through Gaussian models of part position. Prior
◦ Coarse quantization of part position
parts-based methods are confined to features that are
local in the spatial sense. We extend the idea of “parts”
by considering a more general concept that includes The derivation gives a complete record of all the
locality in frequency and orientation. modeling assumptions used in the design of the clas-
Using tables to represent probability distributions is sifier. The performance of the classifier then directly
not uncommon. Swain and Ballard (1991) have used depends on these assumptions and the accuracy of the
them for object recognition by color, and Schiele and statistics gathered for object and non-object classes.
Crowley (1996, 2000) for representing the quantized Explicit knowledge of these assumptions also helps us
output of Gaussian derivatives. However, our classifier decide how to collect statistics for the classifier.
 Object Detection Using the Statistics of Parts 159

2.1. Ideal Form of Classifier Table 3. Ideal classifier using separate models for object
and non-object probabilities.
We introduced the hypothetical ideal classifier as a P(Image | Object),
large table in Section 1.3. This classifier would be ideal (1, 1) (1, 2) ... (20, 20) P(Image | Non-object)
in several ways. First, it is based on a full representation
0 0 ... 0 0.00000013, 0.013
of the input: the classifier is based on a joint function
0 0 ... 1 0.00000032, 0.014
of the entire raw input, not a selected or filtered por- ... ... ... ... ...
tion of it. No information is lost from or added to the
35 45 ... 28 0.0092, 0.00045
input. Second, this table minimizes the probability of ... ... ... ... ...
classification error, assuming each entry in the table is 255 255 ... 255 0.00007, 0.03
labeled with the most probable classification. Finally,
the table concisely represents the output by simply list-
ing each input’s classification and nothing extraneous, sion rule: If the probability is greater than 0.5, the
such as probability values. Of course, such a table is not classifier decides that the object is present in the
feasible. It is not possible to enumerate every possible image.
input in a table. Although not feasible, it provides a To generalize the classification function further, we
useful point of comparison with any feasible classifier, use Bayes’ theorem to re-write the Bayes’ decision rule
in particular the final functional form of our classifier in an equivalent form as a likelihood ratio test:
Eq. (3).
P(image | object) P(non-object)
>λ= (4)
2.2. Generalizations to the Functional P(image | non-object) P(object)
Form of Ideal Classifier
If the likelihood ratio (left side) is greater than the
threshold on the right side, the classifier decides the
There are several differences between the ideal clas-
object is present. With this expansion, the classification
sifier and the final functional form of our classifier in
table would include two entries for each input image
Eq. (3). Our classifier represents object and non-object
window (see Table 3).
properties separately, whereas the ideal table does not
Writing Bayes’ decision rule as a likelihood ra-
separate them. The left side of Eq. (3) outputs a con-
tio test has several advantages. It is easier to collect
tinuous number, whereas the ideal classifier directly
statistics separately for the two class-conditional prob-
outputs a classification, object or non-object. To trans-
ability functions, P(image | object) and P(image | non-
form the ideal table into Eq. (3), we must first make the
object), since they are based on separate sets of images,
table more general. This generalization has important
than it is to directly estimate the posterior probabil-
implications for the training of the probability distri-
ity function, P(object | image). In this form, we also
butions in Eq. (3).
factor out the contributions of the prior probabilities,
Our first transformation is to generalize the output
P(object) and P(non-object), and combine them in a
of the table from a binary value (object, non-object) to
single threshold, λ. This threshold controls the sensi-
a posterior probability, P(object | image) (see Table 2).
tivity of the classifier.
To re-derive the ideal classification table from
Several disadvantages arise when using a decision
the posterior probability, we can apply Bayes’ deci-
rule based on class-conditional probabilities. They
come mostly from practical limitations in the num-
Table 2. Ideal classifier using posterior probabilities. ber of available training examples. First, by estimat-
ing P(image | object) and P(image | non-object) sep-
(1, 1) (1, 2) ... (20, 20) P(object | image)
arately, we may be estimating more parameters than
0 0 ... 0 0.000001 necessary in a direct classification function, such as
0 0 ... 1 0.000003 a posterior probability function, and as a result, our
... ... ... ... ... estimation errors for the model parameters could be
35 45 ... 28 0.87521 greater than those in a more tightly constrained clas-
... ... ... ... ... sification function. Second, it is difficult to obtain
255 255 ... 255 0.00004
a truly representative set of training images, partic-
ularly for the non-object class. Statistical estimates
160 Schneiderman and Kanade

based on these limited sets will not be as accurate 2.4. Three Approximations to the Generalized Ideal
and classification accuracy will suffer. In Section 3.4, Form of the Classifier
we will explain how the technique of AdaBoost with
Confidence Weighted Predictions (Shapire and Singer, We make three approximations to the generalized ideal
1999) partially compensates for such deficiency by form of the classifier, Eq. (4): statistical independence
weighting the training samples such that the resulting of parts, quantization of local operator outputs, and
classifier minimizes classification error on the training reduced resolution in parts position representation. We
set. also describe the design of the local operators whose
outputs form the parts.

2.3. Wavelet Transform of Image Window 2.4.1. Statistical Independence of Parts. Our most
significant approximation is to decompose the image
The classifier performs a wavelet transform on the input window into parts that are treated as statistically inde-
window using a linear phase 5/3 perfect reconstruction pendent. As illustrated in Fig. 5, various local operators
filter bank (Strang and Nguyen, 1997). This wavelet are evaluated at all possible positions within the image
transform is fully invertible, and thus this transform window, and each part corresponds to a local opera-
has no consequences in terms of information content. tor output. However, Fig. 5 is a simplified illustration.
Yet it has two advantages. First, the wavelet transform These operators actually sample a fixed arrangement
partially decorrelates natural imagery, so smaller sub- of wavelet coefficients, instead of directly sampling the
sets of variables will capture greater statistical depen- input pixels. Thus, each part represents a different, but
dency within the image. Second, the wavelet transform not necessarily disjoint, subset of wavelet coefficients.
makes it convenient to design parts with locality in An operator translates by moving its arrangement of
frequency and orientation, as well as locality in space. wavelet coefficients as a block in steps of one wavelet
The multi-resolution nature of wavelets also allows coefficient.
us to efficiently search the image in a coarse-to-fine The local operators sample the wavelet transform
manner. in many ways. For example, as shown in Fig. 6, one

Figure 6. We may define many operators, each of which samples a certain arrangement of wavelet coefficients. In this figure, operator “1”
samples a block of coefficients from within one subband and operator “2” combines spatially registered blocks from two subbands.
 Object Detection Using the Statistics of Parts 161

operator samples a block of wavelet coefficients within why this is true, Domingos and Pazzani show that the
one wavelet subband. Another operator combines two classifier is optimal for conjunctions and disjunctions
blocks from two different subbands. In the next sub- and other problems in which statistical independence
section we describe all the types of local operators our does not necessarily hold.
classifier uses.
Under the assumption of parts independence, the
form of classifier, Eq. (4), now becomes: 2.4.2. Design of Local Operators. At this point in
the derivation, the central question we face is how to


Pk ( f k (x, y), x, y | object) design local operators. Our goal is to design local op-
>λ (5) erators that capture common statistical dependencies.
k x,y Pk ( f k (x, y), x, y | non-object)
We emphasize the notion of common for two reasons.
where f k (x, y) is the kth operator output at position First, we seek to represent statistical dependencies that
(x, y). exist both for the object (e.g., face) and in the rest of
This assumption of statistical independence greatly the world (e.g., non-face). Second, since the local op-
reduces the complexity of the classifier. We believe this erators are each scanned over the full extent of the in-
is a reasonable assumption because for faces, cars, and put window, we need local operators that are not just
many other objects, a given coefficient on the object specialized to one site but useful at all sites on the
is strongly statistically dependent only on a few other object.
coefficients and is weakly related with the rest. We hope Our approach is to make educated guesses about the
to capture the stronger dependencies by appropriate types of statistical dependency we might encounter.
choices of parts and pay a limited penalty by neglecting We would expect statistical dependencies are stronger
the weaker dependencies among the coefficients. in localized regions, and that as pixels are farther apart,
We can gain another perspective on this simplifi- dependency decreases. We therefore emphasize local-
cation by taking the logarithm of Eq. (5) making the ity in position when designing local operators. In par-
classifier a sum of log probabilities: ticular, we want operators to be capable of capturing
the statistical dependencies that exist in small, highly
  
Pk ( f k (x, y), x, y | object) detailed structures, such as the eyes, nose, and mouth
log > log λ on a human face or the headlights and grille on a car.
k x,y
Pk ( f k (x, y), x, y | non-object)
(6) However, statistical dependency can exist over large re-
In this form, we can interpret the classifier as a linear gions as well. In these larger regions, the dependencies
discriminator: usually involve lower-frequency attributes. For exam-
ple, on a face we would expect that the eye sockets

wk (x, y)t ak (x, y) > log λ would be darker than the forehead and cheeks. To rep-
k x,y resent dependencies over both small and large regions,
we combine spatial locality with locality in frequency.
where wk (x, y) is a vector concatenating the log like- Some operators represent large areas at coarse resolu-
lihood values corresponding to each value of operator tion (localized coefficients in the upper levels of the
k at position (x, y) and ak (x, y) selects the appropri- wavelet transform) and others represent smaller areas
ate log likelihood value from this vector, given by the at high resolution (localized coefficients in the lower
computed value of operator k, by assigning ‘1’ to one levels of the transform). Locality in orientation is an-
of its elements and ‘0’ to the remaining elements. other factor we need to combine in operator design.
We can also view Eq. (5) as a modification of the Since the physical world tends to be continuous, we
naı̈ve Bayes classifier. The naı̈ve Bayes classifier mod- would expect horizontal edges to co-occur with other
els all variables as statistically independent, whereas horizontal edges. Similarly, we would expect vertical
our approach models groups of variables as statisti- edges to co-occur with other vertical edges.
cally independent. Domingos and Pazzani (1997) have We have defined 17 local operators that comprise
demonstrated that the naı̈ve Bayes classifier performs various combinations of locality in space, frequency,
surprisingly well in a number of classification prob- and/or orientation. Each operator consists of a mov-
lems, even when there is significant statistical depen- ing arrangement of wavelet coefficients. As an opera-
dency among the independently modeled components. tor scans across the image window, this arrangement
Although there is not a full theoretical understanding of moves as a block.
162 Schneiderman and Kanade

Figure 7. Different local operator types.

The operators are divided into four categories1 Table 5. Inter-orientation operators Opo (level, orientation1 ,
orientation2 ).
by the composition of their arrangements of
wavelet coefficients: intra-subband, inter-orientation, Operator Orientations Level
inter-frequency, and combined inter-frequency/inter-
7 LL (horizontal), 3
orientation arrangement. They are illustrated in Fig. 7.
LL (vertical)
See Appendix for a description of the notation we
8 LH, HL 3
use for describing the components of the wavelet
transform. 9 LH, HL 2
The first six operators (see Table 4) out of 17 are 10 LH, HL 1
intra-subband operators, Opb (level, orientation). These
operators sample a contiguous block of coefficients
within one subband specified by the (level, orientation) Table 6. Inter-frequency subbands Op f (level1 , level2 , orientation).
combination. Such operators capture features that are Operator Levels Orientation
jointly localized in space, frequency, and orientation.
The next four operators (see Table 5) are of 11 3 LL (horizontal), 3 LH
type inter-orientation, Opo (level, orientation1 , 12 3, 2 LH
orientation2 ). These operators combine coefficients 13 2, 1 LH
from two subbands of different orientation but within 14 3 LL (vertical), 3 HL
the same level (frequency) in the transform. These 15 3, 2 HL
capture features that have both horizontal and vertical 16 2, 1 HL
components but are otherwise localized in space and
frequency.
The next six operators (see Table 6) are inter- Table 7. Inter-orientation operators Opo f (level1 , level2 ,
frequency operators, Op f (level1 , level2 , orientation). orientation1 , orientation2 ).
These jointly sample from two subbands of the same Operator Level1 Level2 Orientation1 Orientation2

17 3 2 LH HL
Table 4. Intra-subband operators,
Opb (level, orientation).

Operator Level Orientation

orientation but different levels (or frequencies). They
1 3 LH capture features that have broad frequency content,
2 3 HL such as edges.
3 2 LH Finally the last operator (see Table 7) combines co-
4 2 HL efficients across multiple subbands in both orienta-
5 1 LH tion and frequency, Opo f (level1 , level2 , orientation1 ,
6 1 HL
orientation2 ). The operator, called a combined inter-
orientation/inter-frequency operator, is useful for
 Object Detection Using the Statistics of Parts 163

features that combine horizontal and vertical informa- tions of hyperplanes to a first approximation. It is
tion and information across frequency. not clear whether such decision boundaries will be
good for separating two or more classes in a high
2.4.3. Quantization of Local Operator Output. The dimensional space (Gori and Scarselli, 1998; Kung,
output of each operator is a discrete value of finite range 1993).
representing the combination of wavelet coefficients. In Table representation of a probability distribution is
this section we explain why we choose a discrete rep- almost as flexible as various non-parametric methods.
resentation and describe how we quantize each subset Tables have the advantage of being able to retrieve
of wavelet coefficients to a discrete value. Our clas- probabilities directly by one table look-up rather than a
sifier uses a discrete representation of operator output computation over the entire set of training data. Estima-
because it permits us to represent the statistics of oper- tion of a table is relatively straightforward. We simply
ator output using a table. build a histogram by counting how often each value oc-
There are alternative statistical representations to a curs in the training data. This process involves just one
table-based representation. The most flexible ones are pass through the training images. The resulting esti-
non-parametric ones, such as nearest-neighbor, Parzen mates are statistically optimal—maximum likelihood,
windows, and other kernel-density models. These mod- no bias, consistent, and efficient, satisfying the Cramer-
els, however, have a high computational cost for prob- Rao lower bound. The main drawback of a table is that
ability retrieval. Probability retrieval, for a given in- we can only represent probability over a limited range
put, involves a large computation requiring compari- of discrete values; the amount of training data and the
son of the input to every example in the entire train- size of memory impose limitations on the size of the
ing data. Another alternative would be to use a flex- probability table. To get reasonably accurate estimates
ible parametric distribution, such as a mixture model for our tables, we limited ourselves to approximately
or a multi-layer perceptron (artificial neural network). 10,000 discrete values per operator. This limitation re-
Each of these has flexibility to model multi-modal dis- stricts the number of wavelet coefficients each operator
tributions and acts as a universal approximator as its samples and the resolution at which the operator quan-
resource size (i.e., hidden units or nodes) increases. tizes its subset of coefficients.
However, there are no closed form solutions for fit- Our compromise is to quantize the output of each
ting these models to a set of training examples; their operator to 38 discrete values. We do so by having each
parameters must be estimated by iterative procedures, operator sample the arrangements of 8 coefficients and
such as gradient descent (backpropagation) and E- quantize each coefficient to three levels. Note that the
M. These parameter estimates could become trapped quantization threshold may differ from operator to op-
in local minima and become sub-optimal. Also, it is erator, so different operators may sample the same co-
questionable whether such models are appropriate for efficient but quantize it differently. The 3-level quan-
the task of detection. For example, a multi-layer per- tization is fairly coarse but still retains the informa-
ceptron forms decision boundaries that are combina- tion content of the image. Figure 8 shows several pairs

Figure 8. Images reconstructed by inverse wavelet transform. All wavelet coeffients in LH and HL bands were quantized to three levels per
coefficient.
164 Schneiderman and Kanade

of original and reconstructed images where the recon- [y/M] | non-object), images that do not contain the
struction is done by an inverse wavelet transform of the object. Preparing the training set for the “object”
quantized wavelet values. Objects in the reconstructed class is relatively straightforward, but preparing the
images are still easily identifiable as faces and cars. training set for the “non-object” class requires some
consideration. We will discuss both a basic training
2.4.4. Reduced Resolution in Part Position. Our algorithm by which we estimated each table separately
last approximation reduces resolution in representing and an alternative training procedure that minimizes
part position (x, y). Instead of representing Pk ( f k a classification error criterion using AdaBoost with
(x, y), x, y | object) and Pk ( f k (x, y), x, y | non-object) Confidence Weighted Predictions (Shapire and Singer,
at each position (x, y) in the original resolution, we 1999).
reduce resolution by a factor of M. A given position
(x, y) is represented at reduced resolution by ([x/M], 3.1. Pre-Processing Images of the Object
[y/M]) where [v] denotes the rounded integer of v.
This approximation reduces the size of each probabil- Each training image is geometrically normalized and
ity table by a factor of M 2 . With this simplification, the aligned, corrected for lighting, and perturbed to create
final form of the classifier is (repeat of (3)): many synthetic variations.


Pk ( f k (x, y), [x/M], [y/M] | object)
>λ 3.1.1. Size Normalization and Spatial Alignment.
k x,y
P k ( f k (x, y), [x/M], [y/M] | non-object) To standardize training images, we aligned all the im-
(7) ages with respect to a prototype using pre-defined,
Or alternatively, in terms of log likelihood functions: hand-labeled landmark points on the object. For ex-
 ample, for frontal faces, we used the locations of the
L k ( f k (x, y), [x/M], [y/M]) > log λ eyes, the bridge of the nose, and the center and sides of
k x,y
the mouth. Using these landmark points, we applied the
L k ( f k (x, y), [x/M], [y/M]) (8) translation, scaling, and rotation (Arun et al., 1987) that
P( f k (x, y), [x/M], [y/M] | object) brought each image into alignment with the prototype.
= log .
P( f k (x, y), [x/M], [y/M] | non-object)
3.1.2. Intensity Normalization. We normalized the
As the reduction, we use either M = 4 or 8 depend- image intensity as well. This normalization procedure
ing on the part; for level 1 and 2 operators, we re- is object-dependent.
duce M = 4 (a factor of table reduction =16), and for For faces, we normalized the left and right sides of
level 3 parts, M = 8 (a factor of table reduction =64). each training image separately, by scaling all the inten-
We found that reducing the resolution does not drasti- sity values with specified correction factors, αleft and
cally compromise the geometric representation of the αright :
classifier. Interestingly, the resolution reduction seems
to implicitly accommodate small variations in the ar- I  (x, y) = αleft I (x, y)
rangement of parts as an unintended but positive side (9)
effect. I  (x, y) = αright I (x, y)

For a local operator that uses inputs from both sides

3. Collecting Statistics of the face, we normalize the entire sample using the
value of α of the center pixel. In training, we chose these
This section describes how we gathered the statis- correction factors by hand for each training example by
tics that go into each set of tables Pk ( f k (x, y), visually comparing them to a group of prototypes.
[x/M], [y/M] | object) and Pk ( f k (x, y), [x/M], When the face detector searches for a face, the clas-
[y/M] | non-object) where k = 1 . . . 17 in Eq. (7). sifier evaluates both sides of each candidate window
We estimate each of these tables by using a large over a set of 5 discrete values for α. For each side, the
set of labeled and pre-processed training images. classifier compares the responses (sum of the log like-
For the probabilities tables conditioned on the ob- lihoods) for each value of α and chooses the largest
ject, Pk ( f k (x, y), [x/M], [y/M] | object), we use response. It then sums the two chosen responses to ob-
images of the object, and for Pk ( f k (x, y), [x/M], tain the total log likelihood for the candidate.
 Object Detection Using the Statistics of Parts 165

For cars we did not normalize the training images in 3.3. Training Method (I)—Probabilistic
intensity, because cars differ greatly in color, making Approximation
normalization difficult to compute.
The most direct way to build our classifier was to
separately estimate each of its constituent probability
3.1.3. Creating Synthetic Variants of Training Im-
distributions, Pk ( f k (x, y), [x/M], [y/M] | object) and
ages. We generated additional training data by arti-
Pk ( f k (x, y), [x/M], [y/M] | non-object). To estimate
ficially creating variations to the original training im-
these distributions, we simply counted how often each
ages. The purpose in doing so was to increase the ac-
value of local operator output value occurs at each po-
curacy of our probability estimates.
sition in the appropriate set of training examples. For a
For each image, we generated between 1,600 and
local operator, k, this process involves building a his-
6,400 synthetic variations through small, controlled
togram, Hk (i, j, f ) over a combination of operator out-
variations in position (both by positional pertur-
put values, f , and positions, i and j:
bation and overcomplete evaluation of the wavelet
Initialize all bins in histogram, Hk (i, j, f ), to zero
transform), orientation, size, aspect ratio, background
For all training images, I p
scenery, lighting intensity, and frequency content.
For each local operator, f k , k = 1 . . . N
We applied these variations after we first aligned
For each position, (x, y)
the image geometrically and corrected for the light-
ing as described above. For substitution of differ-
i ← [x/M]
ent background scenery, we segmented the objects
from the background in many of the training im- j ← [y/M]
ages. We segmented these images either by hand and f ← f k (x, y, I p )
by automatic methods when possible. Also, we mod-
Hk (i, j, f ) ← Hk (i, j, f ) + 1
ified frequency content by using various low-pass
filters.
Occasionally a bin in the histogram may receive zero
count. Since it may not be desirable to actually assign
zero probability, we simply added one to each bin in
3.2. Non-Object Images the histogram:
We collected non-object images from various photog-
Hk (i, j, f ) ← Hk (i, j, f ) + 1 for all k, i, j, f
raphy collections2 and from the World Wide Web, par-
ticularly the Washington University archive.3 We tried
to get a balance of indoor, outdoor, urban, industrial, 3.4. Training Method (II)—Minimization
and rural scenes. We used more than 2,000 such non- of Classification Error Using AdaBoost
object images.
To select non-object samples, we used the bootstrap- Training class-conditional distributions separately, as
ping technique.4 The goal of bootstrapping is to se- described above, will give the best possible perfor-
lect non-object training examples that resemble the ob- mance (with this functional form) if our training data
ject. By doing so, the training data will emphasize the is truly representative. However, a finite set of training
distinctions between the object and non-object classes data will have limitations, particularly in representing
and performance will be improved. Bootstrapping is a the non-object class. To achieve better results, we can
two-stage process. We first trained a preliminary detec- explicitly train our classifier to minimize classification
tor using non-object image windows drawn randomly error over the training set. For this purpose, we use the
from the non-object image collection. We then ran this algorithm of AdaBoost with Confidence Weighted Pre-
preliminary detector over the entire collection of non- dictions, a modification of standard AdaBoost (Freund
object images, selecting additional non-object training and Shapire, 1997). This modification of standard Ad-
examples where the detector gave a high response. For aBoost allows for the base classifier to output a con-
some detectors we repeated this process several times, tinuous value, proportional to confidence, rather than a
gathering more and more non-object samples. We then binary classification as in the standard formulation.
used the combined set of samples for training the final AdaBoost, in general, works by sequentially training
detector. multiple instances h 1 (x), h 2 (x), . . . , h T (x) of a base
166 Schneiderman and Kanade

classifier h(x). In our case, the base classifier takes the the complexity of the base classifier. We can see this
following form (modified from Eq. (8)): by directly substituting Eq. (10) in Eq. (11), giving:

h(I ) = L k ( f k (x, y), [x/M], [y/M]) − log λ 
T 

k x,y
H (I ) = αt L t,k ( f k (x, y), i(x), j(y)) − log λ
t=1 k x,y
L k ( f k (x, y), [x/M], [y/M]) (10)
L t,k ( f k (x, y), i(x), j(y))
P( f k (x, y), [x/M], [y/M] | object)
= log Pk,t ( f k (x, y), i(x), j(y) | object)
P( f k (x, y), [x/M], [y/M] | non-object) = log
Pk,t ( f k (x, y), i(x), j(y) | non-object)
Where the input to our classifier is an image window
denoted by I . And by changing the order of the summations,
Each classifier, h t (x), is trained by assigning dif- 
ferent weights to the training examples. For the first H (I ) = L k ( f k (x, y), [x/M], [y/M]) − log λ
k x,y
classifier, h 1 (x), all training examples are given equal
weight. For the subsequent classifiers h t (x), t > 1, the L k ( f k (x, y), [x/M], [y/M]) (12)
algorithm assigns more weight to training examples  T

that have been incorrectly classified by the previous = αt L t,k ( f k (x, y), [x/M], [y/M])
t=1
classifier, h t -1 (x) and, conversely, less weight to train-
ing examples that were correctly classified. AdaBoost Adaboost assigns appropriate weights for individual
then takes a weighted sum of these classifiers as the training images. Intuitively, it is not optimal to give all
final classifier H (x): the training images equal weight, particularly among
  the non-object class. Some of the non-object exam-

T
ples are more important than others for determining
H (x) = sign αt h t (x) (11)
t=1
the decision boundary. This re-weighting of the train-
ing examples is analogous to the way support vector
Both the standard AdaBoost algorithm and the Ad- machines identify the training examples that directly
aBoost with Confidence Weighted Predictions algo- affect the placement of the decision boundary (Cortes
rithm determine each αt as a function of the accuracy and Vapnik, 1995).
of h t (x) on the training data, but differ in how they do One of the issues in using AdaBoost is when to stop
this. In AdaBoost with Confidence Weighted, αt can be the iteration. It is not well understood if AdaBoost is
determined by a binary search that minimizes a func- susceptible to overfitting as the number of iterations
tion of the margin. 5 Both algorithms guarantee that the increase. Our approach was to monitor the performance
final classifier satisfies a bound on the classification of the classifier using a cross-validation image set and
error on the training set. With such a bound the clas- to stop the algorithm when performance seemed to stop
sification error can be driven toward zero after a few improving.
iterations, and thereafter the margin between the two
classes can be increased.
4. Implementation and Efficient Processing
In practice, for each h t (x), we estimate the
for Detection
distributions Pk ( f k (x, y), [x/M], [y/M] | object) and
Pk ( f k (x, y), [x/M], [y/M] | non-object) by Training
Our strategy for implementing a fast detector was to
Method (I), but instead of incrementing each histogram
re-use multi-resolution information wherever possible
bin by 1, we increment by the weight assigned to the
and to use a coarse-to-fine search strategy together with
training example. We scale and round the training im-
various other heuristics to prune out unpromising ob-
age weights to integers for this purpose.
ject candidates.
A disadvantage of Adaboost is the increased compu-
tational cost of applying all instances of the classifier
in the sum of Eq. (11). However, in our case, this sum 4.1. Exhaustive Search
of classifiers does not actually increase the complexity
of our overall classifier, Eq. (10). Since our classifier Each classifier is specialized for a specific orientation,
is linear, the linear sum in Eq. (11) actually reduces to size, alignment, and intensity of the object within an
 Object Detection Using the Statistics of Parts 167

image window. Detecting an object at any position in enough. We apply this strategy after each local operator
an image requires exhaustively scanning the classifier is applied. We set these thresholds conservatively in or-
in position, size, and intensity, as illustrated in Fig. 2. der to avoid discarding actual object candidates while
In searching across scale, the detector searches in 4 quickly removing many of the non-object candidates.
scales per octave, that is, in scale increments of 21/4 in The detector orders the local operators, evaluating first
both x and y dimensions. We chose an integer root of the coarse resolution ones (those involving coefficients
2 so we could reuse information at each octave in this from the top level of the wavelet transform). That is, in
search through scale. the first stages of evaluation, the detector evaluates the
Given an input image, it is ideal to perform inten- image over a coarse grid in which candidate windows
sity correction for each candidate. However, doing so are spaced 8 pixels apart. The remaining stages reduce
would require the classifiers to re-compute all sub- resolution by a factor of 4. Through this strategy we
sequent operations separately for each candidate. We found that we could reduce our computational require-
can reduce computation cost by sharing computation ments by 1 to 2 orders of magnitude with little loss in
among the candidates. Our normalization, therefore, accuracy.
pre-computes the operator values for 5 discrete levels The candidate windows whose likelihood ratio ex-
of intensity correction, α (see Section 3.1.2). For each ceeds the final threshold are initially marked as detec-
candidate, the classifier then evaluates the sum of the tions. Each real object in the image tends to produce
log likelihood for each half of the candidate at each of a cluster of detections. Figure 9 shows the raw output
these five different intensity corrections, and for each from Eq. (8) (before thresholding) over 4 scales. The
half, selects the α value giving the largest sum of log value shown at each pixel corresponds to the log likeli-
likelihood. hood sum associated with the window centered at that
The detector repeats this exhaustive search for each position. The responses to one face form a cluster of de-
view-based classifier and combines their results. If tections across position and scale. We now merge these
there are multiple detections at the same or adjacent lo- detections using the following strategy. We determine
cations and/or scales, the detector chooses the strongest the detection that has the highest response in the entire
detection. image and it classifies it as “object.” The detector then
discards all detections within a radius of the object and
within one half to twice the object size. The detector
4.2. Coarse-to-Fine Evaluation Strategy then continues to search among the remaining detec-
tions, finds the one with the next-highest response, and
Let us consider the computation process within one continues this process until all the candidates have ei-
resized image in the search across scale illustrated in ther been classified as “object” or discarded.
Fig. 2. We organize this process so that as much compu-
tation as possible is shared among overlapping candi-
date windows. First, rather than computing the wavelet 4.3. Re-Using Wavelet Transform in Search
transform separately for each image window, the de- Across Scale
tector computes it once for the entire image. Since the
wavelet transform is not shift invariant, we compute an In searching for the object across scale, the detector
overcomplete transform for each level of the wavelet iteratively searches resized versions of the input image
transform by expanding the (even, even) phase from the where the image is reduced in size by a factor of 21/4
previous level. We also compute local operator output in each dimension. This scaling process continues until
for each value of intensity correction, α, at every can- the scaled image is smaller than the window sent as an
didate location. The detector classifies each candidate input for the classifier. Recomputing the entire wavelet
by accessing the appropriate local operator values and transform is not necessary for obtaining the wavelet
retrieving and summing their log likelihoods according transform for each successive scale. This is illustrated
to Eq. (8). in Fig. 10. All 3 levels of the wavelet transform must
In practice, however, the detector rarely needs to to be computed for each of the first 4 scales, which
evaluate the entire log likelihood ratio. Since the left comprise the first octave of the search across scale.
side of Eq. (8) is a summation, the classifier can ex- After these first 4 scales, our detector re-uses portions
amine its value after any partial evaluation and rule of the wavelet transform computed at previous scales.
out the presence of the object if the value is not high In particular, we obtain the wavelet transform at scale
168 Schneiderman and Kanade

Figure 9. Four consecutive scales and the corresponding output before thresholding from the detector.

Figure 10. Re-using the wavelet transform at successive scalings.

 Object Detection Using the Statistics of Parts 169

Table 8. Face detection results on Kodak test set.

(Rowley, 1999) Schneiderman and Kanade (using AdaBoost)

Detection False γ Detection Detection False

(%) detections (all faces) (%) (profiles only) (%) detections

58.7 1347 0.5 80.4 86.1 105

41.3 617 1.0 70.0 69.4 7
32.6 136 1.5 63.0 61.1 1

i from the wavelet transform at scale i-4 by shifting pre-processing is sometimes useful for pruning out un-
it by one level; that is, level 3 becomes level 2, and promising candidates. This pre-processor uses 8×8×8
level 2 becomes level 1. Therefore, only level 1 has to probability tables (8 levels of quantization for each
be recomputed at scale i. color band) to represent the color distribution of skin-
color and non-skin color in RGB space and combines
4.4. Color Heuristics them into a likelihood ratio test for evaluating each
candidate location. This pre-processing improves per-
The detector we have described is designed for gray- formance speed by a factor of 2 to 4, and discarded a
scale images. When color images are available, color few candidates that would have otherwise been false

Figure 11. Face detection results.

170 Schneiderman and Kanade

detections. However, a disadvantage of using color is Each row of Table 8 shows the result by a different
that the detector removes many actual faces if the im- setting of γ , which determines λ for each classifier as
ages are poorly color balanced. follows:

4.5. Performance Time λfront = dfront + efront γ

λprofile = dprofile + eprofile γ
Using the full set of heuristics described above, one
classifier can evaluate a 240 × 256 image over a full
where the d’s and e’s were tuned by hand.
range of scalings in 5 seconds, on average, using a
Pentium II at 450 MHz.
Table 9. Face detection results on Schneiderman & Kanade test set.

With AdaBoost Without AdaBoost

5. Face Detection
Detections Detection Detection
In this section we describe specific design choices (all faces) (profiles) False (all faces) False
that comprise our face detector and discuss its accu- γ (%) (%) detections (%) detections
racy on several sets of test images. Our face detec-
0.0 92.7 92.8 700 82 137
tor is available on-line at http: // [Link]/
1.5 85.5 86.4 91 74 27
cgi-bin/demos/[Link] and it allows internet users
to submit their own images and see the detection results. 2.5 75.2 78.6 12 60 3

5.1. Local Operators, Training Images, Table 10. Frontal face detection on Sung & Poggio and Rowley &
Baluja & Kanade combined test seta .
and Training
Detection rate False
The face detector uses the 17 local operators described rate (%) detections
in Section 2.4.1. Schneiderman and Kanadeb (eigenvector) 94.4 65
We gathered a large number of face images for train- (95.8)
ing from a number of sources: FERET,6 NIST mug shot (Roth et al., 1999)c (94.8) 78
database,7 Harvard’s face database,8 and CMU’s face Schneiderman and Kanade (wavelet)c 90.2 110
collection.9 We also used many images we collected (91.8)
from the World Wide Web. Overall, we gathered about (Rowley et al., 1998) 86.0 31
2,000 images of frontal faces and 2,000 images of pro- (Viola and Jones, 2001) 93.7 167
file faces. We normalized the two sides of the face in the
a At least 10 additional human faces are not labeled in the ground
training images to compensate for situations in which
the face was illuminated unevenly. truth for this test set. We report our results in two ways. The figures
not in parentheses indicate results on just the 483 labeled faces. Any
We trained the face classifiers using Training Method additional detected faces were counted neither as detections nor false
II (the AdaBoost method) described in Section 3.4. detections. To be consistent with Roth et al. (1999), we also indicate,
in parentheses, the ratio between the total number of faces found by
computer (labeled and unlabeled) divided by the number labeled by
5.2. Results in Face Detection hand (483).
b Indicates the detection results on 125 images with ground truth of

483 labeled faces. The original MIT/CMU test set included 5 addi-
Table 8 compares the performance of our face detector
tional images of line-drawn faces.
with that reported by Rowley (1999) for the task of both c Indicates that 5 images of line-drawn faces were excluded, leav-
frontal and profile face detection using images selected ing 125 images with 483 hand-labeled faces. However, at least 10
from proprietary images Kodak provided to Carnegie additional human faces are not labeled in the ground truth for this
Mellon University. The test set consists of 17 images test set. The figures in parentheses indicate results on just the 483
labeled faces. These numbers do not include the additional faces we
with 46 faces, of which 36 are in profile view (between
detected, counting them neither as detections nor false detections.
3/4 view and full profile view). These images contain However, to be consistent with Roth et al. (1999), we also indicate,
some of the typical problems of amateur photographs in parentheses, the ratio between the total number of faces found by
including poor lighting, contrast, or focus. computer and the number labeled by hand.
 Object Detection Using the Statistics of Parts 171

Table 11. Car detection results. photographers and are generally of better quality than
False the Kodak images in terms of composition, contrast,
γ Detections Misses detections and focus. Table 9 shows the performance at different
values of γ controlling the sensitivity of the detectors.
1.05 177 (83%) 36 (17%) 7
The table also compares the performance of the de-
1.0 183 (86%) 30 (14%) 10 tectors trained with AdaBoost and without AdaBoost.
0.9 197 (92%) 16 (8%) 71 Figure 11 shows some typical results on this image set
when our detector was trained with AdaBoost and used
γ = 1.0.
To further evaluate accuracy on faces with out- The distinguishing characteristic of our face detec-
of-plane rotation we collected a larger test set con- tor is that it works for both frontal and out-of-plane
sisting of 208 images with 441 faces that vary in rotational views. To date, several researchers (Rowley
pose from full frontal to side view. This test set et al., 1998; Sung and Poggio, 1998; Osuna et al., 1998;
is available on-line at [Link] Roth et al., 1999; Viola and Jones, 2001) have had suc-
project [Link]. Of these images, approximately 347 cess developing algorithms that work for frontal views
are profiles (between 3/4 view and full profile view). of faces, but none, to our knowledge, have had success
We gathered these images from a variety of sites on with profile (side) views except Rowley (1999) which
the World Wide Web, mainly news sites such as Ya- we compare our algorithm to in Table 8.
hoo! and the New York Times. Most of these images Profile-view faces are more difficult to detect than
were unconstrained in terms of content, background frontal views for several reasons. The salient features
scenery, and lighting, but were taken by professional on the face (eyes, nose, and mouth) are not as prominent

Figure 12. Car detection results.

172 Schneiderman and Kanade

when viewed from the side as they are when viewed Table 10 compares the accuracy of our detectors with
frontally. Also, for frontal views, these features are in- those of other researchers on the MIT/CMU test set of
terior to the object, whereas on a profile, many of the frontal face images combining test images from Sung
features form the silhouette with respect to the back- and Poggio (1998) and Rowley et al. (1998).
ground. Since the background can be almost any visual In these experiments, we noticed some differences
pattern, a profile detector must accommodate much in performance between the detector described in this
more variation in the appearance of these features than paper and an improved version of the detector we de-
a frontal detector needs to accommodate for interior scribed in Schneiderman and Kanade (1998). Both
features. detectors use similar probabilistic structures, but the

(a)

Figure 13. (a) Positional response of the classifier. Green areas are “face-like” and red areas are not “face-like.” (b) Positional decomposition
of classifier response to particular profile faces. Green areas are “face-like” and red areas are not “face-like.”
(Continued on next page.)
 Object Detection Using the Statistics of Parts 173

(b)

Figure 13. (Continued.)

detector in Schneiderman and Kanade (1998) uses local 6.1. Local Operators, Training Images,
operators based on localized eigenimages rather than and Training
wavelet coefficients. The wavelet-based detector de-
scribed in this paper performs much better for profile- We used 13 of the 17 operators described in
view faces. However, the localized eigenimage-based Section 2.4.1 by excluding the four operators that in-
detector in Schneiderman and Kanade (1998) seems to volved the level 3 LL subband. We excluded these op-
be slightly more accurate on frontal faces. erators because they represent average intensities over
large areas. Since cars come in all colors and intensities,
6. Car Detection we expected these coefficients not to be informative.
We collected car images with our own camera and
We also trained a detector for finding passenger cars in from the World Wide Web, mostly from car sales and
an image. car enthusiast sites. The latter sites provided many
174 Schneiderman and Kanade

photographs of older cars. We gathered between 250 nose, and mouth regions really the most important areas
and 500 images per viewpoint with a total of over 2,000 to detect faces? To study the behavior of the classifier,
images. we computed the amount of contribution at each pixel
The car detector used Training Method (I) described (x, y) to the total log likelihood, Eq. (8). In other words,
in Section 3.3. C(x, y) is the partial sum of the total log likelihood due
to the parts centered at (x, y).

6.2. Results in Car Detection C(x, y) = L k ( f k (x, y), [x/M], [y/M])
k
To test the accuracy of the car detector, we collected,  P( f k (x, y), [x/M], [y/M] | object)
separately from the training set, a set of 104 images that = log
k
P( f k (x, y)[x/M], [y/M] | non-object)
contain 213 cars, spanning a wide variety of models,
sizes, orientations, background scenery, lighting con- (13)
ditions and some partial occlusions. We gathered these
Figure 13 shows C(x, y) as a color overlay on
images using several cameras and from sites on the
a continuum from red to green, with green indi-
World Wide Web. This image set is publicly avail-
cating positive values and red indicating negative
able at [Link]
values.
Table 11 displays our performance.
It is interesting to notice that no particular region in
The sensitivity of the detectors is controlled by
a face seemed to be consistently more influential than
γ which linearly scales the detection thresholds.
the others, and the regions of particular positive influ-
Figure 12 shows some typical results on this image
ence were not sharply localized but tend to be spread
set, evaluated at γ = 1.0.
out. Occluded areas usually contributed a negative in-
fluence. Also, characteristics that were uncommon in
7. Analysis of Positional Response of Classifier the training set, such as the mottled beard on the man
in the lower right corner of Fig. 13(b), gave negative
Since the classifier uses parts across the full extent of response.
the object, it is worth analyzing which parts or areas We performed a similar analysis for car detection.
tended to be most influential. For example, are the eyes, Figure 14 shows the influence of the parts as a function

Figure 14. Positional decomposition of classifier response to particular cars. Green areas are “car-like” and red areas are not “car-like.”
 Object Detection Using the Statistics of Parts 175

Figure 15. Doorknob detection results.

of position on the car. The areas of positive and neg- Appendix: Wavelet Transform
ative response seem to vary somewhat from example
to example, but the window posts, the grille, tires, and A wavelet transform is computed by passing an im-
silhouette often gave positive response, and the back- age through a cascade of filter bank stages. Figure 16
ground and reflections of the surrounding scenery on shows one such stage. This stage filters the image in the
the shiny surfaces often gave negative responses. vertical direction using the filter pair given by c(y) and
d(y). c(y) and d(y) are finite extent filters where c(y) is
low-pass and d(y) is high-pass. These filter outputs are
8. Conclusion down-sampled by a factor of 2 in the vertical direction.
The resulting outputs are filtered in the horizontal direc-
We have described an algorithm for object detection us- tion by an identical pairs of filters oriented horizontally,
ing a set of viewpoint specific classifiers each of which c(x) and d(x), and then down-sampled by a factor of 2
is trainable using a large set of sample images. Each horizontally. The result is a decomposition of the im-
classifier forms a log likelihood ratio as the product of age into 4 subbands denoted by LL, LH, HL, HH. Each
the log likelihoods of a large set of parts. Each part of these represents information from a different ori-
represents various local properties in space, frequency, entation. LH represents vertical information (low-pass
and orientation. filtering in horizontal direction, high-pass filtering in
This algorithm is generic and easily adaptable to new vertical direction), HL represents horizontal informa-
objects with little re-programming. We demonstrated tion (low-pass filtering in vertical direction, high-pass
its use for detecting faces and passenger cars. The same filtering in horizontal direction), HH represents diago-
algorithm was also trained to detect doorknobs for in- nal information (high-pass filtering in both directions),
door robot navigation (Fig. 15). and LL (low-pass filtering in both directions) repre-
Our goal is to develop a system that detects and rec- sents the original image at a lower resolution. Figure 17
ognizes of many kinds of objects in photographs and shows the common representation for these subbands in
video including everyday office objects, text captions an image form. These four subbands could be thought
in video, and various structures in biomedical imagery. of as one frequency band or one level in a wavelet
176 Schneiderman and Kanade

9. Collected by Henry Rowley, Shumeet Baluja, Henry

Schneiderman, and Takeo Kanade.

References

Amit, Y. 2000. A neural network architecture for visual selection.

Neural Computation, 12:1059–1089.
Arun, K.S., Huang, T.S., and Blostein, S.D. 1987. Least-Squares fit-
ting of two 3-D point sets. IEEE Transactions on Pattern Recog-
nition and Machine Intelligence, (9):698–700.
Burl, M.C. and Perona, P. 1996. Recognition of planar object classes.
In IEEE Conference on Computer Vision and Pattern Recognition,
pp. 223–230.
Burl, M.C., Weber, M., and Perona, P. 1998. A probabilistic approach
to object recognition using local photometry and global geometry.
Figure 16. One stage in a filter-bank wavelet decomposition. In Proc. of the 5th European Conf. on Computer Vision.
Chow, C.K. and Liu, C.N. 1966. Approximating discrete probability
distributions with dependence trees. IEEE Transactions on Infor-
mation Theory, IT-14(3).
Cortes, C. and Vapnik, V. 1995. Support-vector networks. Machine
Learning, 20:273–297.
Cosman, P.C., Gray, R.M., and Vetterli, M. 1996. Vector quantiza-
tion of image subbands: A survey. IEEE Transactions on Image
Processing, 5(2):202–225.
Domingos, P. and Pazzani, M. 1997. On the optimality of the sim-
ple Bayesian classifier under zero-one loss. Machine Learning,
29:103–130.
Field, D.J. 1999. Wavelets, vision and the statistics of natural scenes.
Figure 17. Representation of a one-level and two level wavelet
Philosophical Transactions of the Royal Society: Mathematical,
transform.
Physical and Engineering Sciences, 357(1760):2527–2542.
Freund, Y. and Shapire, R.E. 1997. A decision-theoretic generaliza-
tion of on-line learning and an application to boosting. Journal of
transform. To expand the decomposition in frequency, Computer and System Sciences, 55(1):119–139.
we can iterate on the LL band; that is, we decompose Geman, D. and Flueret, F. 2001. Coarse-to-fine face detection. Inter-
the LL band as we decomposed the original image by national Journal of Computer Vision, 41:85–107.
Gori, M. and Scarselli, F. 1998. Are mulilayer perceptrons adequate
passing it through another stage identical to the first.
for pattern recognition and verification. IEEE Transactions on Pat-
If the filter pair is chosen properly, the original image tern Analysis and Machine Intelligence, 20(11):1121–1132.
can be reconstructed from its transform with no loss of Kung, Y. 1993. Digital Neural Networks. Prentice-Hall.
information. Such filter banks are called perfect recon- Lades, M., Vorbruggen, J.C., Buhmann, J., Lange, J., Malsburg,
struction filter banks. Several books describe their de- C.v.d., Wurtz, R.P., and Konen, W. 1993. Distortion invariant ob-
ject recognition in the dynamic link architecture. IEEE Transac-
sign (Strang and Nguyen, 1997; Vetterli and Kovacevic,
tions on Computers, 42(3):300–311.
1995). Lewis II, P.M. 1959. Approximating probability distributions to
reduce storage requirements. Information and Control, 2:214–
225.
Notes Osuna, E., Freund, R., and Girosi, F. 1997. Training support vector
machines: An application to face detection. In IEEE Conference
1. These relationships (intra-subband, inter-subband, inter- on Computer Vision and Pattern Recognition, pp. 130–136.
frequency) were initially defined in Cosman et al. (1996). Romdhani, S., Torr, P., Scholkopf, B., and Blake, A. 2001. Compu-
2. John Krumm and Henry Rowley each provided image collections. tationally efficient face detection. In International Conference on
3. [Link] Computer Vision, pp. 695–700.
4. Introduced by Sung and Poggio (1998) for image classification Roth, D., Yang, M.-H., and Ahuja, N. 1999. A SNoW-based face
and also used by Rowley et al. (1998). detector. NPPS-12.
5. See Shapire and Singer (1999) for a complete description of the Rowley, H.A., Baluja, S., and Kanade, T. 1998. Neural network-
algorithm. based face detection. IEEE Transactions on Pattern Analysis and
6. Provided by Jonathon Phillips. Machine Intelligence, 20(1):23–38.
7. See [Link] Rowley, H. 1999. Neural network-based face detection. Ph.D thesis.
8. Provided by Woodward Yang. CMU-CS-99-117.
 Object Detection Using the Statistics of Parts 177

Schiele, B. and Crowley, J.L. 1996. Probabilistic object recogni- Sung, K.-K. and Poggio, T. 1998. Example-based learning for view-
tion using multidimensional receptive field histograms. In Inter- based human face detection. IEEE Transactions on Pattern Anal-
national Conference on Pattern Recognition. ysis and Machine Intelligence, 20(1):39–51.
Schiele, B. and Crowley, J.L. 2000. Recognition without correspon- Swain, M.J. and Ballard, D.H. 1991. Color indexing. International
dence using multidimensional receptive field histograms. Interna- Journal of Computer Vision, 7(1):11–32.
tional Journal of Computer Vision, 36(1):31–50. Vetterli, M. and Kovacevic, J. 1995. Wavelets and Subband Coding.
Schneiderman, H. and Kanade, T. 1998. Probabilistic modeling of Prentice-Hall.
local appearance and spatial relationships for object recognition. Viola, P. and Jones, M. 2001. Rapid object detection using a boosted
In IEEE Conference on Computer Vision and Pattern Recognition. cascade of simple features. In IEEE Conference on Computer Vi-
Shapire, R.E. and Singer, Y. 1999. Improving boosting algorithms us- sion and Pattern Recognition.
ing confidence-rated predictions. Machine Learning, 37(3):297– Wiskott, L., Fellous, J.-M., Kruger, N., Malsburg, C.v.d. 1997. Face
336. recognition by elastic bunch graph matching. IEEE Transac-
Strang, G. and Nguyen, T. 1997. Wavelets and Filter Banks. tions on Pattern Analysis and Machine Intelligence, 19(7):775–
Wellesley, Cambridge Press: Wellesley, MA. 779.