A Maximum-Likelihood Strategy for Directing Attention during Visual Search.
AbstractA precise analysis of an entire image is computationally wasteful if one is interested in finding a target object located in a subregion of the image. A useful attention strategy can reduce the overall computation by carrying out fast but approximate image measurements and using their results to suggest a promising subregion. This paper proposes a maximum-likelihood attention mechanism that does this. The attention mechanism recognizes that objects are made of parts and that parts have different features. It works by proposing object part and image feature pairings which have the highest likelihood of coming from the target. The exact calculation of the likelihood as well as approximations are provided. The attention mechanism is adaptive, that is, its behavior adapts to the statistics of the image features. Experimental results suggest that, on average, the attention mechanism evaluates less than 2 percent of all part-feature pairs before selecting the actual object, showing a significant reduction in the complexity of visual search.
Introduction
Object recognition algorithms often have two phases: a selection phase where a region (or a subset of image
features) is chosen, and a verication phase where the algorithm veries whether the object is present in the
chosen region. The algorithm speed depends on the strategy used for selecting regions. We call this strategy an
\attention strategy" since its task is to direct computational \attention" to promising parts of the image.
Classical object recognition algorithms have xed attention strategies. For example, template matching and
Hough Transform process the image in a xed raster fashion 1 . Fixed strategies can be slow, and to speed them
practical implementations employ ad-hoc preprocessing such as color thresholding. The ad-hoc procedures
are really attention strategies, since their purpose is to direct computation to the promising regions of the image.
Ad-hoc pre-processing techniques are useful, but they have two serious limitations:
1. Because they are ad-hoc, we are never sure that they are doing the best that can be done.
2. Ad-hoc techniques are usually unable to adapt to image statistics. For example, consider the strategy of
thresholding on color. If an object has a prominent red part, the image may be thresholded on the specic
hue of red. This can be problematic if the background also contains red objects. In that case, it may be
better to threshold on some other color provided some part of the object has that color.
This capacity to adapt the attention mechanism to the statistics of the image is critical for a good attention
algorithm. We know that the human visual attention system has this capacity. Most ad-hoc algorithms do
not and are easily confounded when faced with certain backgrounds.
Interpretation trees search subtrees with a xed priority.
Our aim is to propose an attention algorithm to overcome these two limitations. We replace ad-hoc strategies
with strategies based on probabilistic decision theory. In particular, we investigate a strategy based on the
maximum-likelihood (ML) decision rule. The ML rule turns out to give an adaptive strategy.
We formulate the problem as follows. We assume that the object recognition system is composed of three
sub-systems: (1) a pre-attentive system, (2) an attention mechanism, and (3) a post-attentive system.
The pre-attentive system is a fast feature detector. It operates over the entire image and detects simple image
features (color, edge roughness, corner angles etc). Some of the detected features come from the target object,
the rest come from other objects in the image called distractors. We assume that the object is composed of parts
and each part gives rise to single feature in the image.
The role of the attention mechanism is to choose an object part, pair it with an image feature and to hypothesize
that this pairing is due to the presence of the object in the image. This hypothesis is passed to the post-attentive
system which uses the full geometric knowledge of the object and explores the image around the feature to nd the
object. The post-attentive system is just a traditional object recognition algorithm. It indicates to the attention
mechanism whether the hypothesis is valid or not. If the hypothesis is not valid, the attention mechanism takes
this into account and proposes the next hypothesis. The post-attentive system now focuses on this region of
the image. The process terminates either when the object is found or when all features in the image have been
exhausted.
Post-attentive
System
Pre-attentive
System
Attention
Mechanism
Features
Hypothesis
Validation
Object Model
Slow processing
of the region of interest

Figure

1: Attention in Visual Search.
We make the following assumptions about the attention mechanism:
1. All features detected by the pre-attentive system are available to it all the time. This is simply another way
of saying that the pre-attentive system is fast enough to process the entire image before a detailed search
with the post-attentive system begins.
2. The attention mechanism only uses the values of the features detected by the pre-attentive system. That is,
the attention mechanism does not evaluate additional geometric constraints (by looking at pairs of image
features, for example). Imposing geometric constraints is computationally expensive and we wish to avoid
this expense 2 .
3. The attention mechanism is greedy. At every stage it chooses that part-feature pair which has the highest
likelihood of coming from the object in the image. The likelihood is evaluated after taking into account all
previous pairs rejected by the post-attention mechanism.
We make no other assumptions. In particular, we do not assume any specic pre- and post- attentive systems.
The strategy that we derive can be used with a range of user-supplied modules. We demonstrate this in our
experiments, where we use corner detectors as well as color detectors as pre-attentive systems.
Post-attentive systems are slow precisely because they evaluate geometric constraints.
In this paper, we only address 2d object recognition, and we have kept the formulation as simple as possible.
This is by design - we want to emphasize basic ideas and certain approximations. The theory in this paper can
be made more sophisticated, by adding more features, by considering multiple spatial resolutions, by clustering
pre-attentive features etc. These alternatives are not pursued in this paper.
Human Visual Attention
Human vision is known to have an attention strategy that is highly eective [14, 22, 28]. Human visual attention
is adaptive in the sense discussed above. Cognitive scientists do not yet have a complete understanding of human
visual attention, but some partial understanding has emerged. Many models proposed by cognitive scientists are
similar to our model of gure 1 [22, 28]. In these models, the pre-attentive system is fast and capable of extracting
\primitive" image features (such as color, edge smoothness, and size). The post-attentive system is slower, but
can analyze image regions in detail and use the complete geometric denition of the target object for recognition.
The human attention mechanism uses the primitive features produced by the rst system to direct the second.
A key aspect of the human visual is that it seems to use only feature values or local feature density in directing
attention. It does not appear to evaluate further geometric constraints on the primitive features.
The behavior of human visual attention in two conditions, called \pop-out" and \camou
age," is particularly
interesting. If an image contains a target whose primitive features are su-ciently dierent from the distractor
features, then the time required to nd the target is independent of the number of distractors in the image [22].
This is the \pop-out" condition. In this condition, the target just seems to pop out of the image. On the other
hand, if the target has features similar to the distractors, then the time required to nd the target grows linearly
with the number of distractors. We call this the \camou
age" condition.
In section 5 we show theoretically that \pop-out" and \camou
age" are emergent properties of our algorithm.
In section 6 we conrm this experimentally.
Relation to Previous Work
Other researchers have presented strong cases for using attention in vision algorithms [23, 24]. Some researchers
have proposed specic computational mechanisms that model what is known about human visual search [10, 11].
Others have proposed search algorithms for specic cues: parallel-line groups [17], color [5, 18], texture [19],
prominent motion [25], \blobs" in scale space [12], or intermediate objects [27]. Some authors have considered
attention for scene interpretation [16]. Others have applied it to passive tracking [21] and to active vision systems
[2, 15].
Our aim is quite dierent from these studies. We do not wish to implement a specic biology-based attention
algorithm or one that is tailored to a particular cue. Instead, we ask whether it is possible to derive an attention
strategy from rst principles which can be applied to a range of cues.
Finally, we wish to address a source of confusion. Our algorithm is sometimes compared to the interpretation
tree algorithm for object recognition [1, 6, 7]. The confusion arises from an apparent similarity between the
two: both attempt to match object parts to the image. However, this similarity is only supercial. There are
substantial dierences between the two algorithms:
1. The two algorithms operate at a dierent level. We are concerned with interaction between pre- and post-
attentive modules, rather than organizing the geometric comparison of parts and features. Interpretation
trees are concerned with the latter.
2. Interpretation trees match the entire object to edges in the image. Our algorithm is concerned with evaluating
the likelihood of a single part matching a single feature, given that the object is present in the
image.
3. The interpretation tree is an explicitly geometric algorithm - its purpose is to systematically evaluate
geometric relations between image edges. On the other hand, our attention mechanism is not concerned
with geometric relations. It works for arbitrary feature types, many of which do not enforce any geometric
constraints between parts.
These comments are not meant as a criticism of interpretation trees, but are simply meant to show that
the two have dierent goals. In fact, the two can be used together, with the interpretation tree serving as the
post-attentive system capable of fully recognizing the object.
Organization of the Paper
This paper is organized as follows. Section 2 contains the denitions and notations. Section 3 contains the
likelihood calculations. The calculation of the exact likelihood is computationally expensive and section 4 contains
approximations to it. Section 5 analyzes the behavior of ML attention strategy in a special case and demonstrates
its \adaptive" nature. Section 6 contains experimental results and section 7 concludes the paper.
Denitions
2.1 Features and Parts
We begin by dening features. By a feature we mean a primitive element of an image, such as color, corner, etc.,
that can be found by simple feature detectors. A feature has a value (the RGB triple of color, angle of the corner,
etc.) which belongs to some feature space V . The set of all features in the image is F . We will refer to the value
of the k th feature by f k . Some of the features in the image come from the instance of the object we wish to
detect. These are target features. Others come from other objects in the image; these are distractor features.
The object to be recognized has M parts, fS j . The set of all parts is P . Parts need not be
dened in a geometric way. The only requirement is that the union of all parts is the entire object. A part may
be visible or may be completely occluded in an image. The prior probability that part S j is visible in the image
is (the probability of complete occlusion of the part is 1 P j ). We assume that each visible part gives rise
to a single feature in the image. Thus, multiple parts cannot contribute to a feature and a part cannot give rise
to multiple features. If a part is visible, it may still be partially occluded, and its feature value may change due
to partial occlusion. We model this by saying that, if the jth part is visible, then its feature value is a random
variable with the probability density function p j (f ).
We assume that distractor feature values are realizations of a uniform Poisson process in the feature space
. We make this assumption because we do not have any knowledge of distractors and would like to treat their
values as being \uniformly" distributed in V . The probability density of obtaining n distractor feature values
is given by
where  is the process intensity and V is the feature space volume.
2.2 The Attention Mechanism
The attention mechanism is iterative and it works as follows: During each iteration the mechanism chooses that
part-feature pair which is most likely due to the target. This choice is passed on to the post-attentive system,
which evaluates whether the pairing is really due to the occurrence of the object. If it is due to the object,
then the object has been found and the search terminates. If it is not, then the attention mechanism takes this
information into account and suggests the next most likely pair.
We will denote the pairing of part Sm with feature fn as (Sm ; fn ). Since the set of all parts of the object is P
and the set of all image features is F , the set of all possible part-feature pairings is P F . We will refer to any
which has been declared incorrect by the post-attention mechanism as a rejected pair. The set of all
rejected pairs till the j th iteration of the algorithm is denoted by R j . Thus, in the j th iteration, the set of all part
feature pairs that have not been rejected is P  F R j . With this notation, the pseudo-code for the attention
algorithm can be written as:
1. Pre-process: Extract F, the set of image features.
2. Initialize: Set ;, the empty set.
3. Loop condition: The set of pairs that remain to be tested at the j th iteration is PF
R j . If this set is empty, terminate the iteration and declare that the object is not present
in the image.
4. Candidate selection: From the set PF R j choose the pair (S which has the greatest
likelihood of coming from the target in the image:
is the likelihood that the pair (Sm ; fn ) comes from the target in
the image given the set of parts, the set of image features, and the set of rejected pairs.
This is the M.L. decision.
5. Object verication: Pass the selected pair to the post-attentive system for verification.
If the hypothesis is correct, the object has been found. Terminate the search.
Else .
6. Bookkeeping: Set R 1. Go to Step 3.
3 The Likelihood
We need a formula for p((S to execute the above algorithm. We begin with a simple calculation.
3.1 All Parts Visible
Assume for the moment that there are no rejected pairs and that all parts of the object are visible, i.e., the prior
probability
Suppose that there are N features in the feature set F . We rst evaluate the likelihood that a specic set of
features came from the M object parts, with the rest of the features being distractors. To describe the pairing
of features with parts, we introduce a part mapping function
from the indices of the parts to the indices of features. The function says that the parts are mapped
to features f (1) ;    ; f (2) . The likelihood of this with the rest of the feature set accounted for as distractors is:@ Y
Expressions such as the above occur frequently in our analysis, and we use a special notation for them. We denote
the expression by (g
are the features to be matched with respectively and H is the set of distractor
features. In this notation, the above likelihood is (f
Now, the likelihood that the single comes from the target object is the sum of all likelihoods in
which the parts are paired with features with the restriction that part Sm is always paired with part fn . This is:
;(m)=n
where the sum is over all  functions which satisfy
Next suppose that the set of rejected pairs R j is not empty. To calculate the likelihood that (Sm ; fn ) is due
to the target, we must avoid summing over those part mappings which give rise to a rejected part-feature pair.
We will say that a part mapping compatible with the set R j if (S
. Using this notion, we can write the likelihood p((S
;(m)=n
where the sum is over all part mapping functions that are compatible with R j and which satisfy,
3.2 Occluded Parts
Next, consider the possibility that some parts may be completely occluded (the prior probabilities P j are not
necessarily equal to 1). To take this into account, we introduce additional features called null features. When a
part is mapped to a null feature, we say that it is completely occluded.
We augment the feature set F by adding M null features to it. The feature set now has N +M elements. The
likelihood can be expressed as before:
;(m)=n
where, as before, the sum is over all compatible part mapping functions, but the function  is now given by
Y
in which q j and h evaluate the likelihoods that feature values come from parts and from distractors taking into
account the prior probability of occlusion and null features:
j is not a null feature
and,
where,
number of non-null features in H:
So far, we have ignored the fact that we do not know the intensity  of the distractor process ( is required
in equation (7)). However, we can estimate  from the data as follows: Since P is the probability
that part S i is visible, the average number of visible parts is
Thus, the average number of distractors is
number must be equal to V which is the average number of distractors derived from the
Poisson distribution. That is,
or,
Equations (4)-(8) completely dene the likelihood.
4 Approximations to the Likelihood
Equations (4)-(8) are computationally expensive to evaluate because they contain the combinatorics of mapping
1 parts to N 1 features. In this section, we propose two approximations. The rst involves using the
normal approximation to the Poisson distribution. This allows us to simplify the expression for the likelihood by
eliminating some terms. The second, and the more radical approximation, involves using a reduced number of
parts. That is, we consider smaller objects formed by taking r-tuples of parts from the original object, and we
calculate the likelihood that a part-feature pair comes from at least one of the simpler objects.
We nd in practice that simple case of very satisfactory results and we use this approximation in
all our experiments. For completeness, we report calculations for the general (r 1)-tuple case.
4.1 The Normal Approximation
The Poisson distribution for the distractor values can be approximated by a normal distribution when the number
of distractors is large [8]. Recall that each term being summed in equation (4) has a factor h(H) arising from
equation (5). In Appendix A, we show that if N is the number of null features mapped onto the parts, then h(H)
can be approximated as:
exp
Y
exp
Y
exp
where, C is the part of the expression that is independent of N .
Referring back to equation (5), we can see that the term C is common factor in all  terms and need not be
evaluated if we are only interested in nding the part-feature pair that maximizes the likelihood of equation (4).
With this, the likelihood becomes:
;(m)=n
where, the function  is now given by
Y
Y
exp
C
Y
is the number of null features in
j is not a null feature
if g j is a null feature, (12)
In the last step of equation (11) we dropped the C term and included the exp M
term in the denition of r j .
4.2 Matching Simpler Models
We now proceed to the second approximation. Recall that in calculating the exact likelihood for (Sm ; fn ) we
had to account for the combinatorics for all of the rest of the parts to match features. In the approximation
considered here, we only account for r 1 of the rest parts. That is, we consider all simpler objects formed by
the part Sm and r 1 tuples of other parts and evaluate the likelihood that (Sm ; fn ) comes from at least one the
simpler objects.
4.3 Approximate Likelihood for
In this case, we have M simplied objects, each object having exactly one unique part. The likelihood that the
comes from at least one of these simpler parts is equal to the likelihood that is comes from the
object having Sm as its single part. The likelihood is just r m (f n ).
4.4 Approximate Likelihood for
In this case, we have M simplied objects, each object having two parts { the part Sm and one other part, and
we calculate the likelihood that the pair (Sm ; fn ) comes from at least one of these simpler parts.
m) be one other specic part. Then, using equations (10)- (12), the joint likelihood that the pair
comes from this simplied object is
;(m)=n
where, the sum is over all part mapping functions  which (1) map the part index set fm; ig into the feature
index set, (2) are compatible with R j , and (3) satisfy n. The functions r are dened by equation
(12). This expression can be easily rewritten as
;(m)=n
where, on the right hand side, the sum is over all feature indices k for which k 6= n and the pair (S is not in
Therefore, the joint likelihood that the pair (Sm ; fn ) comes from one or more of the 2-part objects is the sum
of the above likelihood over all
The computational complexity of this expression is O(NM ).
4.5 Higher Order Approximations
Now, consider the likelihood that the pairing (Sm due to at least one simplied object formed
by the part Sm and r 1 other parts of the original object.
The expression for this likelihood is messy. To simplify its presentation, we adopt the following convention:
we represent an ordered set of r indices such that fS i 1
is one simplied object. Two
dierent sets of the type I represent two dierent combinations of r parts from the object.
Repeating the calculation for equation (13), we get
I;i m=m
;(im)=n
Y
i2I
where, the rst sum is over all I which have m, the second sum is over all part mapping functions  (which
map I to the feature index set) which are compatible with R j and for which (i m n. The complexity of
evaluating the likelihood of equation (14) is O(C N 1
r 1 ). These calculations give us likelihoods which can be used
with the attention algorithm in practice. This completes the description of the algorithm.
Next, we turn to investigate the adaptibility of the attention algorithm.
(x)Detected feature values

Figure

2: Maximum-likelihood Explanation of Pop-out.
5 Adaptation, Pop-out, and Camou
age
5.1 Adaptation
To understand the adaptive behavior of the algorithm, consider the following simple case:
1. The model has only two parts, S 1 and S 2 . Neither part is ever completely occluded (i.e.,
2. The feature space is one dimensional and the parts have uniform feature distributions over disjoint intervals
That is, the probability density that S 1 occurs with
a feature value f is
Similarly, the probability density that S 2 occurs with a feature value f is
Consider two situations in which there are 6 features in the image. In the rst case, suppose that ve of the
occur in  1 and the sixth feature f 6 occurs in  2 (illustrated in gure 2). In the second
case, reverse the situation, so that the ve features, f occur in  2 and the sixth feature f 6 occurs in  1 .
In the rst case, the likelihood that S 2 matches f 6 is a sum of ve terms. Each term corresponds to S 2 matching
matching one feature in ff 1 ;    ; f 5 g, and the rest of the features being distractors. Each term isL 2
and hence the likelihood of (S
Now consider the likelihood of (S It has a single term corresponding to S 1 matching f 1 , S 2 matching f 6
being distractor features. Its likelihood has a single
The likelihood that S 1 matches any other feature occurring in  1 is the same as above.
Clearly, the likelihood that S 2 matches f 6 is greater than the likelihood that S 1 matches f 1 or any other feature
in  1 , and the attention mechanism chooses the former.
We can simply repeat the above calculation when the ve features f are in  2 and one feature f 6 in
1 . Again we get the likelihood of part S 1 matching the feature f 6 asL 2
while the likelihood of S 2 matching any of the features in  2 isL 2
The former is clearly greater than the latter.
If  1 and  2 were ranges of red and blue colors, then the two cases can be interpreted as follows: The object
has two parts, one colored red and the other blue. In the rst case, we have an image with one blue feature
and ve red features and in the second case we have an image with one red feature and ve blue features. The
attention algorithm chooses to investigate the blue feature in the rst case, and the red feature in the second case.
Thus the algorithm \adapts" to the distribution of features in the image and chooses to investigate that feature
which is least like the distractor (i.e. background) features. This is precisely the adaptative behavior we want for
the attention algorithm, and the above calculation shows that the ML decision imparts it to our algorithm.
It is easy to check that if we use the approximation in the above calculation, the algorithm will not
adapt. In fact it is easy to check in general that adaptation (to the statistics of features in the image) is possible
if r  2.
Finally, recall that pop-out and camou
age are conditions under which the human visual system nds the
target in constant time and, in time that grows linearly with the number of distractors. Pop-out is achieved if
the target has some feature that is su-ciently dierent from the distractors. Camou
age occurs when all target
features are similar to distractor features.
The adaptive behavior discussed above demonstrates pop-out since the ML attention mechanism always chooses
that feature which is least like the distractors. In contrast, if the target and distractor had similar features { say
that there were three features in  1 and  2 { the likelihoods of all part-feature pairs would be identical and there
would be no reason to prefer one over the other. The search in this case would proceed without any strong bias
towards choosing a particular pair, and the time to nd the target will be similar to a blind serial search. It will
grow linearly with the number of distractors. This is camou
age.
Thus, it appears that the ML attention mechanism can emulate pop-out and camou
age.
6 Experimental Results
We next report experiments that evaluate the performance of the attention mechanism with real images. We
conducted three sets of experiments. In each experiment, we obtained a number of images in which a target object
was present. For each image, we calculated the net number of part-feature pairings that were possible. We then
used the attention mechanism to propose part-feature pairings from this set. The number of part-feature pairings
suggested by the attention mechanism till the object was found, expressed as a fraction of the total number of
part-feature pairings, was taken as the performance measure of the attention algorithm.
The pre-attentive system and the attention mechanism was implmented in C. On the other hand, the verication
of whether the proposed part-feature pair belonged to the target object was performed manually. For the likelihood
calculation, all priors, P j , were set to 1:0.
6.1 Corner Features
The target object used in the rst experiment is shown in Figure 3 { a cardboard cut-out of a sh. Fifty
images containing the target were produced by placing the model in a 30cm  30cm area . Commonly occurring
laboratory tools were tossed on the model. Images were taken in such a way that the model had a scale range
between 0:5 and 2:0. In all cases, the model was partially occluded in the image. The model was so heavily
occluded in two of the 50 images that none of its corners were visible. These images were discarded and the
algorithm was tested on the remaining 48 images. Figure 4 shows two of the 48 images.

Figure

3: The Model.
The preattentive system used corners of edge contours in the image as features. Corners were dened as
points of local maxima of curvature on an edge contour together with the two \arms" which abut that point.
Arms extend until the next point of high curvature along a contour, and the length of an arm is its arc length.

Figure

5(a) shows an example of a curve parsed into corners. Corners and arms were extracted from the images
automatically by edge detection followed by edge linking and curvature calculation.

Figure

4: Example Images.
Each corner feature was parameterized by a vector of 2 parameters: the length of the shorter arm, a, and the
average angle of deviation between the two arms,  (see Figure 5(b)).
The target had six corners which were chosen as the object parts. The distribution of the model features
was calculated as follows: Each target corner was occluded (in software) such that the smaller arm length after
occlusion was 100%; 80%; 60% of the unoccluded smaller arm length. For each partial occlusion, the feature
value (; a) was calculated. These values represent samples of the distribution of (; a) under partial occlusion
(a) Definition of a part (b) Features of a part
Part
Longer arm
Shorter arm
Average
angular
deviation

Figure

5: Features used in Experiments.

Figure

Attentive Search for the Object

Percentage hypothesis evaluated1030
Frequency

Figure

7: Histogram of percentage hypothesis
evaluated until recognition.
at unit magnication. The process was duplicated by changing the magnication (in software) of the model
to 2:0; 1:707; 0:5. The set of (; a) obtained in this wat was fed to a standard non-parametric density
estimator to obtain the probability distribution of corner parameters for each part.
Results That approximate ML decision rule was used (with r set to 1; 2 and 3 respectively. Figure 6 shows
a typical result of ML visual search with 2. The gure shows the sequence of corners that the algorithm
analyzed in turn until it suggested the target. The corner at the successful match is also shown in the gure.
Similar behavior was obtained for
As mentioned above, to evaluate the eectiveness of the ML attention mechanism, we measured the average
percentage of hypotheses that were processed until the correct hypothesis was suggested. On average, the
rule processed 4:67% of the possible hypotheses, the processed 1:97% of the possible hypotheses, and
the processed 2:73% of the possible hypotheses. Clearly the latter two rules outperformed the rst
rule. Since the rule does not exhibit adaptation (as discussed in section 5), it was dropped from further
consideration. Further, since performed similarly, but the r = 3 rule was slower in execution,
the rule appears to be a good compromise between eectiveness, ability to adapt, and computational
complexity. Figure 7 shows a histogram of the percentage of hypotheses processed by this rule to nd the correct
match. As mentioned above, on average, only 1:97% of the possible hypotheses were processed before the correct
hypothesis was found. In the absence of an attention mechanism, the expected proportion of hypotheses evaluated
would be 50%. This shows that the attention mechanism signicantly shortened the search time.
Pop-out and Camou
age In the second experiment, we examined the performance of the ML attention
mechanism under pop-out and camou
age conditions. As before, we used the approximate likelihood with 2.
To simulate pop-out and camou
age conditions, we created similar and dissimilar distractors. Dissimilar
distractors were created by cutting triangular pieces of cardboard. Similar distractors were created by duplicating
the target model and cutting the duplicates in half along random lines. Figure 8 shows an image where the model
is present along with the triangular dissimilar distractors. This is the pop-out condition. Figure 9 shows the
camou
age condition. Multiple images were obtained in the pop-out and camou
age conditions by increasing the
number of distractors.

Figures

8 and 9 show typical sequences in image features were searched till the target was suggested in pop-out
and camou
age conditions. Figure 10 shows the number of hypotheses processed until the target was suggested
by the attention algorithm as a function of the total number of features in the image. In the pop-out case, the
rst hypothesis was always the correct one, while in the camou
age case, the number of hypotheses increased
monotonically with the number of features in the image.

Figure

8: Search under Pop-out. Figure 9: Search under Camou
age.
50 150 250
Number of features in the image1030
Number
of
fixations
to
find
the
object
Camouflage

Figure

10: Number of Hypotheses Evaluated
vs. Image Features.
(a) (b)

Figure

11: Search paths for two Ronaldo images. In (a), Ronaldo was found immediately. In (b), Ronaldo is
squatting at the lower left.
6.2 Color Features
The third experiment used color features for nding people in photographs and video stills. The object model
had 2 parts, and the feature of each part was the color distribution of its pixels in RGB space.
First, we conducted a series of experiments for nding a member of the Brazilian soccer team, Luiz Ronaldo,
against a variety of backgrounds. The two parts correspond to the yellow and blue of his team's uniform. Color
distributions were estimated by taking a sample of each color from several images of the subject, histogramming
the samples in a coarse (32 3 ) RGB cube, smoothing, and normalizing.
Fifty images containing Ronaldo were gathered from the Internet, with images of varying sizes. Some images
were acquired from frames of MPEG movies. The criteria used to select the images were (1) the subject in
uniform should be visible in the image, and (2) the images should not be close-ups (in which case the candidate
selection task would be much too easy). The scale of the subject varied in height, in a range between 5 to 100
pixels. Figure 11 shows two of the 50 images.
We used single pixels as image features. From each image, were sampled at grid points of
the image. In 5 instances, this allowed the player to fall between gaps in the sampling, and so sampling was
quadrupled to pixels. Although this suggests that there were as many as 4800  2 match hypotheses
in any image, in reality, most of the selected pixels had RGB values that could not be produced by either color
distribution. Those pixels were discarded from the count of potential hypotheses.
Results For this experiment, only 0:86% of the possible hypotheses were evaluated by the attention algorithm,
on average, before the correct hypothesis was found. Figure 11 shows the extreme examples of pop-out and
camou
age. In (a), Ronaldo's shirt is the only yellow object in the image and it immediately pops out against
a largely green background. In (b), he is camou
aged by his teammates who oer equally good matches to the
color distributions.
Where's Waldo As a nal example, we evaluated the eectiveness of ML attention on the well-known Where's
Waldo game { a children's book series in which the goal is to nd the title character in pages lled with highly
detailed illustrations. A similar attempt was also reported in [13].
The same implementation described above was used with color densities from Waldo's shirt and shorts. Because
Waldo is a small gure in the image, pixels were sampled at full resolution (610  338). Of the 194380  2 non-
zero-probability part-pixel match possibilities, only 28 (0:007%) were examined before the algorithm suggested
the target location for Waldo. The total time for the entire search process aside from object verication took
Figure

12: Where's Waldo?
only 0:18 seconds on a 266MHz single-processor Pentium II. In Figure 12, the search sequence for nding Waldo
is overlaid on top of the image 3 .
These experiments indicate that the ML attention strategy is eective with 2. Furthermore, as we
mentioned in section 1, the strategy works with geometric as well as non-geometric pre-attentive features.
Conclusions
In this paper we proposed a maximum-likelihood technique for directing attention. The technique uses simple
features found by a fast pre-attentive module to direct a slower, but more accurate post-attentive module. The
attention mechanism recognizes that the target object is made up of parts and attempts to nd that pairing of
object part and image feature which is most likely to come from the target in the image. The resulting attention
strategy is adaptive. Its choice of the part-feature pair depends on the image feature statistics. Furthermore,
the attention strategy demonstrates \pop-out" and \camou
age" which are two important properties of human
visual attention. In experiments with real world images, the attention strategy signicantly reduces the number
of hypotheses that are required to be evaluated before target is found.

Acknowledgements

We greatly beneted from discussions with Profs. Drew McDermott, Anand Rangarajan, and Lisa Berlinger of
Yale University.
3 This particular image can be found at http://www.ndwaldo.com/city/city.asp.


--R

HYPER: a new approach for the recognition and positioning of two-dimensional objects
Ferrier N.


Finding Waldo
Localizing overlapping parts by searching the interpretation tree.
Object recognition by computer.
Handbook of the Poisson Distribution
Selective Attention in Vision






Brown C.



Wang J.





Mudge T.
Ballard D.
Cave K.
--TR

--CTR
Toshiyuki Kirishima , Kosuke Sato , Kunihiro Chihara, Real-Time Gesture Recognition by Learning and Selective Control of Visual Interest Points, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.351-364, March 2005
Fred H. Hamker, The emergence of attention by population-based inference and its role in distributed processing and cognitive control of vision, Computer Vision and Image Understanding, v.100 n.1-2, p.64-106, October 2005
H. I. Bozma , G. akirolu , . Soyer, Biologically inspired Cartesian and non-Cartesian filters for attentional sequences, Pattern Recognition Letters, v.24 n.9-10, p.1261-1274, 01 June
C. Y. Fang , C. S. Fuh , P. S. Yen , S. Cherng , S. W. Chen, An automatic road sign recognition system based on a computational model of human recognition processing, Computer Vision and Image Understanding, v.96 n.2, p.237-268, November 2004
. Soyer , H. I. Bozma , Y. Istefanopulos, APES: Attentively Perceiving Robot, Autonomous Robots, v.20 n.1, p.61-80, January   2006
object recognition;visual search;attention