Spatial Color Indexing and Applications.
We define a new image feature called the color correlogram and use it for image indexing and comparison. This feature distills the spatial correlation of colors and when computed efficiently, turns out to be both effective and inexpensive for content-based image retrieval. The correlogram is robust in tolerating large changes in appearance and shape caused by changes in viewing position, camera zoom, etc. Experimental evidence shows that this new feature outperforms not only the traditional color histogram method but also the recently proposed histogram refinement methods for image indexing/retrieval. We also provide a technique to cut down the storage requirement of the correlogram so that it is the same as that of histograms, with only negligible performance penalty compared to the original correlogram.We also suggest the use of color correlogram as a generic indexing tool to tackle various problems arising from image retrieval and video browsing. We adapt the correlogram to handle the problems of image subregion querying, object localization, object tracking, and cut detection. Experimental results again suggest that the color correlogram is more effective than the histogram for these applications, with insignificant additional storage or processing cost.
Introduction
In recent times, the availability of image and video
resources on the World-Wide Web has increased
tremendously. This has created a demand for effective
and flexible techniques for automatic image
retrieval and video browsing [4, 8, 9, 15, 30, 31, 33,
40]. Users need high-quality image retrieval (IR)
systems in order to find useful images from the
masses of digital image data available electroni-
cally. In a typical IR system, a user poses a query
by providing an existing image (or creating one by
drawing), and the system retrieves other "similar"
images from the image database. Content-based
video browsing tools also provide users with similar
capabilities - a user provides an interesting
frame as a query, and the system retrieves other
similar frames from a video sequence.
Besides the basic image retrieval and video processing
tasks, several related problems also need to
be addressed. While most IR systems retrieve images
based on overall image comparison, users are
typically interested in finding objects [7, 9, 6]. In
this case, the user specifies an "interesting" sub-region
(usually an interesting object) of an image
as a query. The system should then retrieve images
containing this subregion (according to human
perception) or object from a database. This
task, called image subregion querying, is made
challenging by the wide variety of effects (such as
different viewing positions, camera noise and vari-
ation, object occlusion, etc.) that cause the same
object to have drastically different appearances in
different images.
The system should also be able to solve the
localization problem (also called the recognition
problem), i.e., it should find the location of the
object in an image. The lack of an effective and
efficient image segmentation process for large, heterogeneous
image databases implies that objects
have to be located in unsegmented images, making
the localization problem more difficult.
Similar demands arise in the context of content-based
video browsing. A primary task in video
processing is cut detection, which segments a video
into different camera shots and helps to extract
key frames for video parsing and querying. A flexible
tool for browsing video databases should also
provide users with the capability to pose object-level
queries that have semantic content, such as
"track this person in a sequence of video". To
handle such queries, the system has to find which
frames contain the specified object or person, and
has to locate the object in those frames.
The various tasks described above - image re-
trieval, image subregion querying, object localization
and cut detection - become especially challenging
when the image database is gigantic. For
example, the collection of images available on the
Internet is huge and unorganized. The image data
is arbitrary, unstructured, and unconstrained; and
the processing has to be done in real-time for retrieval
purposes. For these reasons, traditional
(and often slow) computer vision techniques like
object recognition and image segmentation may
not be directly applicable to these tasks and new
approaches to these problems are required.
Consider first the basic problem of content-based
image retrieval. This problem has been
widely studied and several IR systems have been
built [8, 30, 33, 4, 31]. Most of these IR systems
adopt the following two-step approach to search
image databases [42]: (i) (indexing) for each image
in a database, a feature vector capturing certain
essential properties of the image is computed
and stored in a featurebase, and (ii) (searching)
given a query image, its feature vector is com-
puted, compared to the feature vectors in the fea-
turebase, and images most similar to the query
image are returned to the user. An overview of
such systems can be found in [3].
For a retrieval system to be successful, the feature
vector f(I) for an image I should have the
following qualities: (i) should be
large if and only if I and I 0 are not "similar",
(ii) f(\Delta) should be fast to compute, and (iii) f(I)
should be small in size.
Color histograms are commonly used as feature
vectors for images [43, 8, 30, 33]. It has been
shown that the color histogram is a general and
flexible tool that can be used for the various tasks
outlined above.
1.1. Our Results
In this paper, we propose a new color feature for
image indexing/retrieval called the color correlogram
and show that it can be effectively used in
the various image and video processing tasks described
above. The highlights of this feature are:
(i) it includes the spatial correlation of pairs of
colors, (ii) it describes the global distribution of
local spatial correlations of colors, (iii) it is easy
to compute, and (iv) the size of the feature is
fairly small. Experimental evidence shows that
this new feature (i) outperforms both the traditional
histogram method and the very recently
proposed histogram refinement method for image
indexing/retrieval, and (ii) outperforms the
histogram-based approaches for the other video
browsing tasks listed above.
Informally, a correlogram is a table indexed by
color pairs, where the k-th entry for hi; ji specifies
the probability of finding a pixel of color j
at a distance k from a pixel of color i. Such an
image feature turns out to be robust in tolerating
large changes in appearance of the same scene
caused by changes in viewing positions, changes in
the background scene, partial occlusions, camera
zoom that causes radical changes in shape, etc.
(see

Figure

4). We provide efficient algorithms to
compute the correlogram.
We also investigate a different distance metric
to compare feature vectors. The L 1 distance met-
ric, used commonly to compare vectors, considers
the absolute component-wise differences between
vectors. The relative distance metric we use calculates
3relative differences instead and in most cases
performs better than the absolute metric (the improvement
is significant especially for histogram-based
methods).
We investigate the applicability of correlograms
to image retrieval as well as other tasks like image
subregion querying, object localization, and
cut detection. We propose the correlogram intersection
method for the image subregion querying
problem and show that this approach yields significantly
better results than the histogram intersection
method traditionally used in content-based
image retrieval. The histogram-backprojection
approach used for the localization problem in [43]
has serious drawbacks. We discuss these disadvantages
and introduce the idea of correlogram correc-
tion. We show that it is possible to locate objects
in images more accurately by using local color spatial
information in addition to histogram backpro-
jection. We then use correlograms to compare
video frames and detect cuts by looking for adjacent
frames that are very different. Once again,
we show that using the correlogram as the feature
vector yields superior results compared to using
histograms.
Our preliminary results thus indicate that the
correlogram method is a more accurate and effective
approach to these tasks compared to the color
histogram method. What is more, the computational
cost of the correlogram method is about the
same as that of other simpler approaches, such as
the histogram method.
1.2. Organization
Section 2 gives a brief summary of related work.
In Section 3, we define the color correlogram and
show how to compute it efficiently. Section 4 deals
with the content-based image retrieval problem
and the use of the correlogram for this problem.
Section 5 discusses the use of the correlogram for
image subregion querying. Applications of the
correlogram to video browsing problems are described
in Section 6. Finally, Section 7 concludes
with some remarks and scope for further work.
2. Related Work
Color histograms are commonly used as image
feature vectors [43, 8, 30, 33] and have proved
to be a useful and efficient general tool for various
applications, such as content-based image retrieval
[8, 30, 33], object indexing and localization
[43, 27], and cut detection for video segmentation
[1]. A color histogram describes the global color
distribution in an image. It is easy to compute
and is insensitive to small changes in viewing positions
and partial occlusion. As a feature vector
for image retrieval, it is susceptible to false posi-
tives, however, since it does not include any spatial
information. This problem is especially acute
for large databases, where false positives are more
likely to occur. Moreover, the histogram is not
robust to large appearance changes. For instance,
the pair of images shown in Figure 1 (photographs
of the same scene taken from different viewpoints)
are likely to have quite different histograms 1 .
Color histograms are also used for image subregion
querying and object localization [43]. These
two problems are closely related to object recog-
nition, which has been studied for a long time in
computer vision [37]. Since conventional object
recognition techniques cannot recognize general
objects in general contexts (as in the natural imagery
and real videos), some work has been done
for finding objects from image databases [7, 9].
These techniques, however, are trained for some
specific tasks, such as finding naked people, grouping
trees, etc. Color histograms are also widely
used in video processing. Though there are several
sophisticated techniques for video cut detec-
tion, Boreczky and Rowe [1] report that the simple
color histogram yields consistently good results
compared to five different techniques.
We now briefly discuss some other related work
in the areas of content-based image retrieval, image
subregion querying, object localization, and
cut detection.
2.1. Content-based Image Retrieval
Several recently proposed schemes incorporate
spatial information about colors to improve upon
the histogram method [18, 40, 41, 35, 11, 32, 31].
One common approach is to divide images into
Fig. 1. Two "similar" images with different histograms.
subregions and impose positional constraints on
the image comparison. Another approach is to
augment the histogram with some spatial information

Hsu et al. [18] select two representative colors
signifying the "background" and the principal
"object" in an image. The maximum entropy algorithm
is then used to partition an image into
rectangular regions. Only one selected color dominates
a region. The similarity between two images
is the degree of overlap between regions of the
same color. The method is tested on a small image
database. Unfortunately, this method uses coarse
color segmentation and is susceptible to false positives

Smith and Chang [40] also partition an image,
but select all colors that are "sufficiently" present
in a region. The colors for a region are represented
by a binary color set that is computed using
histogram back-projection [43]. The binary color
sets and their location information constitute the
feature. The absolute spatial position allows the
system to deal with "region" queries.
Stricker and Dimai [41] divide an image into
five fixed overlapping regions and extract the first
three color moments of each region to form a feature
vector for the image. The storage requirements
for this method are low. The use of overlapping
regions makes the feature vectors relatively
insensitive to small rotations or translations.
Pass et al. [32, 31] partition histogram bins by
the spatial coherence of pixels. A pixel is coherent
if it is a part of some "sizable" similar-colored re-
gion, and incoherent otherwise. A color coherence
vector (CCV) represents this classification for each
color in the image. CCVs are fast to compute and
perform much better than histograms. A detailed
comparisons of CCV with the other methods mentioned
above is given in [32].
The notion of CCV was further extended in
[31] where additional feature(s) are used to further
refine the CCV-refined histogram. One such
extension uses the center of the image (the center-
most 75% of the pixels are defined as the "center")
as the additional feature. The enhanced CCV is
called CCV with successive refinement (CCV(s))
and performs better than CCV.
Since the image partitioning approach depends
on pixel position, it is unlikely to tolerate large
image appearance changes. The same problem occurs
in the histogram refinement method, which
depends on local properties to further refine color
buckets in histograms. The correlogram method,
however, takes into account the local spatial correlation
between colors as well as the global distribution
of this spatial correlation and this makes the
correlogram robust to large appearance changes
(see

Figure

4). Moreover, this information is not
a local pixel property that histogram refinement
approaches can capture.
2.2. Other Image/Video Problems
The image subregion querying problem is closely
related to the object recognition problem, which
has been studied for a long time by the computer
vision community [37]. Some of the early work in
object recognition and detection was pioneered by
Marr [26], who suggest that geometric cues such
as edge, surface and depth information be identified
before object recognition is attempted. Most
of such object recognition systems compare the
geometric features of the model with those of an
image using various forms of search (some of which
are computationally quite intensive [24, 13]).
Such geometric information is hard to extract
from an image, however, because geometric and
photometric properties are relatively uncorrelated
[34], and the central tasks involved in this approach
- edge detection and region segmentation
are difficult for unconstrained data in the context
of image retrieval and video browsing.
An alternative approach to model-based recognition
is appearance matching. First, a database
of object images under different view positions
and lighting conditions is constructed. Then,
principal component analysis is used to analyze
only the photometric properties and ignore geometric
properties [29, 23, 34]. This model-based
method is effective only when the principal components
capture the characteristics of the whole
database. For instance, it yields good results on
the Columbia object database in which all images
have a uniform known background. If there is a
large variation in the images in a database, how-
ever, a small set of principal components is unlikely
to do well on the image subregion querying
task. In addition, the learning process requires
homogeneous data and deals poorly with outliers.
Therefore, this approach seems suitable only for
domain-specific applications, but not for image
subregion querying from a large heterogeneous image
database such as the one used in [31, 21].
Since the color information (e.g. histogram) is
very easy to extract from an image, it has been
successfully used for object indexing, detection,
and localization [43, 8, 30, 27, 39, 2, 44, 9]. We
briefly review some of these approaches below.
Swain and Ballard [43] propose histogram
intersection for object identification and histogram
backprojection for object localization.
The technique is computationally easy, does
not require image segmentation or even fore-
ground/background separation, and is insensitive
to small changes in viewing positions, partial oc-
clusion, and object deformation. Histogram back-projection
is a very efficient process for locating
an object in an image. It has been shown that
this algorithm is not only able to locate an object
but also to track a moving object. The advantages
and disadvantages inherent to histograms in
general are discussed in detail in Section 5.
One disadvantage of color histograms is that
they are sensitive to illumination changes. Slater
and Healey [39] propose an algorithm that computes
invariants of local color distribution and
uses these invariants for 3-D object recognition.
Illumination correction and spatial structure comparison
are then used to verify the potential
matches.
Matas et al. [27] propose the color adjacency
graph (CAG) as a representation for multiple-
colored objects. Each node of a CAG represents
a single color component of the image. Edges of
the CAG include information about adjacency of
color components. CAGs improve over histograms
by incorporating coarse color segmentation into
histograms. The set of visible colors and their adjacency
relationship remain stable under changes
of viewpoint and non-rigid transformations. The
recognition and localization problems are solved
by subgraph matching. Their approach yields excellent
results, but the computational cost of sub-graph
matching is fairly high.
Forsyth et al. [9] offer different object models
in order to achieve object recognition under
general contexts. Their focus is on classification
rather than identification. The central process is
based on grouping (i.e., segmentation) and learn-
ing. They fuse different visual cues such as color
and texture for segmentation; texture and geometric
properties for trees; color, texture and specialized
geometric properties for human bodies.
Cut detection, as a first step to video segmentation
and video querying, has been given much attention
[1]. The simple histogram approach gives
reasonably good results on this problem. His-
tograms, however, are not robust to local changes
in images. Dividing an image into several subregions
may not overcome the problem [15] either.
3. The Correlogram
A color correlogram (henceforth correlogram) expresses
how the spatial correlation of color changes
with distance. A color histogram (henceforth his-
captures only the color distribution in an
image and does not include any spatial correlation
information. Thus, the correlogram is one kind of
the spatial extension of the histogram. 2
3.1. Notation
Let I be an n \Theta n image. (For simplicity of expo-
sition, we assume that the image is square.) The
colors in I are quantized into m colors c
(In practice, m is deemed to be a constant and
hence we drop it from our running time analysis.)
For a pixel its
color. Thus, the notation p 2 I c is synonymous
with For convenience, we use the
L1-norm to measure the distance between pix-
els, i.e., for pixels
define
jg. We
denote the set f1; ng by [n].
3.2. Definitions
The histogram h of I is defined for i 2 [m] by
p2I
For any pixel in the image, h c i (I)=n 2 gives the
probability that the color of the pixel is c i . The
histogram can be computed in O(n 2 ) time, which
is linear in the image size.
Let a distance d 2 [n] be fixed a priori. Then,
the correlogram of I is defined for
[d] as
p22I
Given any pixel of color c i in the image, fl (k)
gives the probability that a pixel at distance k
away from the given pixel is of color c j . Note
that the size of the correlogram is O(m 2 d). The
autocorrelogram of I captures spatial correlation
between identical colors only and is defined by
c;c
This information is a subset of the correlogram
and requires only O(md) space.
While choosing d to define the correlogram, we
need to address the following. A large d would
result in expensive computation and large storage
requirements. A small d might compromise the
quality of the feature. We consider this issue in
Section 4.1.
Example 1. Consider the simple case when
8. Two sample images are shown
in

Figure

2. The autocorrelograms corresponding
to these two images are shown in Figure 3. The
change of autocorrelation of the foreground color
(yellow) with distance is perceptibly different for
these images. 3
3.3. Distance Metrics
The L 1 and L 2 norms are commonly used distance
metrics when comparing two feature vectors. In
practice, the L 1 norm performs better than the L 2
norm because the former is more robust to outliers
[38]. Hafner et al. [14] suggest using a more
sophisticated quadratic form of distance metric,
which tries to capture the perceptual similarity
between any two colors. To avoid intensive computation
of quadratic functions, they propose to
use low-dimensional color features as filters before
using the quadratic form for the distance metric.
We will use the L 1 norm for comparing histograms
and correlograms because it is simple and
robust. The following formulae are used to compute
the distance between images I and I
From these equations, it is clear that the contributions
of different colors to the dissimilarity are
equally weighted. Intuitively, however, this contribution
should be weighted to take into account
some additional factors.
Example 2. Consider two pairs of images
Even though the absolute difference in the pixel
count for color bucket i is 50 in both cases, clearly
the difference is more significant for the second
pair of images.
Thus, the difference jh c i Equation
(4) should be given more importance if
small and vice versa. We
could therefore consider replacing the expression
Equation 4 by
(the 1 in the denominator is added to prevent division
by zero).
This intuition has theoretical justification in
[17] which suggests that it is sometimes better
Fig. 2. Sample images: image 1, image 2.
Fig. 3. Autocorrelograms for images in Figure 2.
to use a "relative" measure of distance d - . For
defined by
It is straightforward to verify that (i) d - is a
metric, (ii) for
d- can be applied to feature vectors also. We
have set 1. So the d 1 distance metric for
histograms and correlograms is:
3.4. An Algorithm
In this section, we look at an efficient algorithm
to compute the correlogram. Our algorithm is
amenable to easy parallelization. Thus, the computation
of the correlogram could be enormously
speeded up.
First, to compute the correlogram, it suffices to
compute the following count (similar to the cooccurrence
matrix defined in [16] for texture analysis
of gray images)
because,
The denominator is the total number of pixels at
distance k from any pixel of color c i . (The factor
8k is due to the properties of L1 -norm.) The
naive algorithm would be to consider each
of color c i and for each k 2 [d], count all
of color c j with Unfortunately,
this takes O(n 2 d 2 ) time. To obviate this expensive
computation, we define the quantities
which count the number of pixels of a given color
within a given distance from a fixed pixel in the
positive horizontal/vertical directions.
Our algorithm works by first computing - c j ;v
and - c j ;h
. We now give an algorithm with a running
time of O(n 2 d) based on dynamic programming

The following equation is easy to check
with the initial condition
p (k) is computed for all p 2 I and for each
using Equation 14. The correctness
of this algorithm is obvious. Since we do O(n 2 )
work for each k, the total time taken is O(n 2 d).
In a similar manner, - c;v
can also be computed
efficiently. Now, modulo boundaries, we have
This computation takes just O(n 2 ) time.
The hidden constants in the overall running
time of O(n 2 d) are very small and hence this algorithm
is extremely efficient in practice for small
d.
3.5. Some Extensions
In this section, we will look at some extensions
to color correlograms. The general theme behind
the extensions are: (1) improve the storage efficiency
of the correlogram while not compromising
its image discrimination capability, and (2) use additional
information (such as edge) to further refine
the correlogram, boosting its image retrieval
performance. These extensions can not only be
used for the image retrieval problem, but also in
other applications like cut-detection (see Section
6.2).
3.5.1. Banded Correlogram In Section 3.4, we
saw that the correlogram (resp. autocorrelogram)
takes m 2 d (resp. md) space. Though we will
see that small values of d actually suffices, it will
be more advantageous if the storage requirements
were trimmed further. This leads to the definition
of banded correlogram for a given b. (For simplic-
ity, assume b divides d.) For
In a similar manner, the banded autocorrelogram
can also be defined. The space requirements
for the banded correlogram (resp. banded
that when measures the density of a
color c j near the color c i , thus suggesting the local
structure of colors.) The distance metrics defined
in Equation 5 is easily extended to this case.
Note that banded correlograms are seemingly
more susceptible to false matches since
which follows by triangle inequality. Although the
banded correlograms have less detailed information
as correlograms, our results show that the
approximation of fl by fl has only negligible effect
on the quality of the image retrieval problem and
other applications.
3.5.2. Edge Correlogram The idea of exploiting
spatial correlation between pairs of colors can also
be extended to other image features such as edges.
In the following, we augment the color correlogram
with edge information. This new feature,
called the edge correlogram, is likely to have increased
discriminative power.
is the edge information
of image I, i.e., is on an edge and 0
otherwise. (Such information can be obtained using
various edge-detection algorithms.) Now, the
question is if this useful information can be combined
with (auto)correlograms so as to improve
the retrieval quality even further. We outline one
scheme to do this. In this scheme, each of the m
color bins is refined to get I 0 with 2m bins.
I
ae
It is easy to see that the definition of both correlograms
and autocorrelograms directly extend to
this case. The storage requirements become 4m 2 d
(resp. 2md) for correlograms (resp. autocorrelo-
grams). Note however that the number of p such
that usually very small. Since we
mostly deal with autocorrelograms, the statistical
importance of ff (k)
c+ becomes insignificant, thus
rendering the whole operation meaningless. A solution
to this problem is to define edge autocorrelogram
in which cross correlations between c + and
are also included. The size of edge autocorrelogram
is thus only 4md. We can further trim the
storage by the banding technique in Section 3.5.1.
4. Image Retrieval using Correlograms
The image retrieval problem is the following: let S
be an image database and Q be the query image.
Obtain a permutation of the images in S based on
Q, i.e., assign rank(I) 2 [jSj] for each I 2 S, using
some notion of similarity to Q. This problem
is usually solved by sorting the images I 2 S according
to jf(I) \Gamma f(Q)j, where f(\Delta) is a function
computing feature vectors of images and j \Delta j f is
some distance metric defined on feature vectors.
Performance Measure Let fQ be the
set of query images. For a query Q i , let I i be
the unique correct answer. The following are two
obvious performance measures:
1. r-measure of a method which sums up over all
queries, the rank of the correct answer, i.e.,
use the average r-
measure which is the r-measure divided by the
number of queries q.
2. -measure of a method which is given by
the sum (over all
queries) of the precision at recall equal to 1.
The average p 1 -measure is the p 1 -measure divided
by q.
Images ranked at the top contribute more to the
Note that a method is good if it has
a low r-measure and a high p 1 -measure.
3. Recall vs. Scope: Let Q be a query and let
a be multiple "answers" to the query (Q
is called a category query). Now, the recall r is defined
for a scope s ? 0 as jfQ 0
Since it is very hard to identify all relevant images
in a huge database like ours, using this measure
is much simpler than using the traditional recall
vs. precision. Note however that this measure still
evaluates the effectiveness of the retrieval [18, 40].
Organization Section 4.1 lists some efficiency
considerations we take into account while using
correlograms for image retrieval. Section 4.2 describes
our experimental setup and Section 4.3
provides the results of the experiments.
4.1. Efficiency Considerations
As image databases grow in size, retrieval systems
need to address efficiency issues in addition to the
issue of retrieval effectiveness. We investigate several
general methods to improve the efficiency of
indexing and searching, without compromising effectiveness

Parallelization The construction of a featurebase
for an image database is readily parallelizable. We
can divide the database into several parts, construct
featurebases for these parts simultaneously
on different processors, and finally combine them
into a single featurebase for the entire database.
Partial Correlograms In order to reduce space
and time requirements, we choose a small value
of d. This does not impair the quality of correlograms
or autocorrelograms very much because
in an image, local correlations between colors are
more significant than global correlations. Some-
times, it is also preferable to work with distance
sets, where a distance set D is a subset of [d]. We
can thus cut down storage requirements, while still
using a large d. Note that our algorithm can be
modified to handle the case when D ae [d].
Though in theory the size of a correlogram is
d) (and the size of an autocorrelogram is
O(md)), we observe that the feature vector is not
always dense. This sparsity could be exploited to
cut down storage and speed up computations.
Filtering There is typically a tradeoff between
the efficiency and effectiveness of search algo-
rithms: more sophisticated methods which are
computationally more expensive tend to yield better
retrieval results. Good results can be obtained
without sacrificing too much in terms of efficiency
by adopting a two-pass approach [14]. In the first
pass, we retrieve a set of N images in response to
a query image by using an inexpensive (and possibly
crude) search algorithm. Even though the
ranking of these images could be unsatisfactory,
we just need to guarantee that useful images are
contained in this set. We can then use a more
sophisticated matching technique to compare the
query image to these N images only (instead of the
entire database), and the best images are likely
to be highly ranked in the resulting ranked list.
It is important to choose an appropriate N in
this approach 4 - the initially retrieved set should
be good enough to contain the useful images and
should be small enough so that the total retrieval
time is reduced.
4.2. Experimental Setup
The image database consists of 14,554 color JPEG
images of size 232 \Theta 168. This includes 11,667 images
used in Chabot [30], 1,440 images used in
QBIC [8], and 1,005 images from Corel. It also
includes a few groups of images in PhotoCD format
and a number of MPEG video frames from
the web [31]. Our heterogeneous image database
is thus very realistic and helps us evaluate various
methods. It consists of images of animals, hu-
mans, landscapes, various objects like tanks, flags,
etc.
We consider the RGB colorspace with quantization
into 64 colors. To improve performance, we
first smooth the images by a small amount. We
use the distance set
computing the autocorrelograms. We use
for the banded autocorrelogram. This results in a
feature vector that is as small as the histogram.
Our query set consists of 77 queries. Each of
these queries was manually picked and checked to
have a unique answer. Therefore they serve as
ground truth for us to compare different methods
in a fair manner. In addition, the queries are chosen
to represent various situations like different
views of the same scene, large changes in appear-
ance, small lighting changes, spatial translations,
etc. We also run 4 category queries, each with
a
Query
movie scenes), and Query 4 moving car
images). The correct answers to the unique answer
queries are obtained by an exhaustive manual
search of the whole image database.
We use the L 1 norm for comparing feature
vectors. The feature vectors we use are histograms
coherent vectors with successive
refinement (ccv(s))[31], autocorrelograms
(auto), banded autocorrelograms (b-auto), edge
autocorrelograms (e-auto), and banded edge auto-
correlograms (be-auto). Examples of some queries
and answers (and the rankings according to various
methods) are shown in Figure 4. The query
response time for autocorrelograms is under 2 sec
on a Sparc-20 workstation (just by exhaustive linear
search).
4.3. Results
4.3.1. Unique Answer Queries Observe that all
the correlogram-related methods are on par in
terms of performance and significantly better than
histogram and CCV(s). On average, in the
autocorrelogram-based method, the correct answer
shows up second while for histograms and
CCV-based methods, the correct answer shows up
at about 80th and 40th places. The banded au-
tocorrelograms perform only slightly worse than
the original ones. With the same data size as the
histograms, the banded autocorrelograms retrieve
the correct answers more than 79 rank lower than
histograms. Since the autocorrelograms achieve
really good retrieval results, the edge correlograms
do not generate too much improvement.
Also note that the banded edge autocorrelo-
grams have higher p 1 -measure than the edge au-
tocorrelograms. This is because most of the ranks
go higher while only a few go lower. Though the r-
measure becomes worse, the p 1 -measure becomes
better. It is remarkable that banded autocorrelogram
has the same amount of information as the
histogram, but seems lot more effective than the
latter.
hist: 496. ccv(s): 245. auto: 2.
b-auto: 2. e-auto: 2. be-auto: 2.
hist: 411. ccv(s): 56. auto: 1.
b-auto: 1. e-auto: 1. be-auto: 1.
hist: 367. ccv(s): 245. auto: 1.
b-auto: 1. e-auto: 8. be-auto: 9.
hist: 310. ccv(s): 160. auto: 5.
b-auto: 5. e-auto: 1. be-auto: 1.
(Fig. 4. Sample queries and answers with ranks for various methods. (Lower ranks are better.) (Continued on next page))
hist: 198. ccv(s): 6. auto: 12.
b-auto: 13. e-auto: 5. be-auto: 4.
hist: 119. ccv(s): 25. auto: 2.
b-auto: 3. e-auto: 1. be-auto: 1.
hist: 19. ccv(s): 74. auto: 1.
b-auto: 1. e-auto: 1. be-auto: 1.
hist: 78. ccv(s): 7. auto: 2.
b-auto: 2. e-auto: 2. be-auto: 2.
Fig. 5. continued

Table

1. Comparison of various image retrieval methods.
Method hist ccv(s) auto b-auto e-auto be-auto
r-measure 6301 3272 172 196 144 157
avg. r-measure 81.8 42.5 2.2 2.5 1.9 2.0
p1-measure 21.25 31.60 58.06 55.77 60.26 60.88
avg. p1-measure 0.28 0.41 0.75 0.72 0.78 0.79
For 73 out of 77 queries, autocorrelograms perform
as well as or better than histograms. In
the cases where autocorrelograms perform better
than color histograms, the average improvement
in rank is 104 positions. In the four cases
where color histograms perform better, the average
improvement is just two positions. Autocor-
relograms, however, still rank the correct answers
within top six in these cases.
Statistical Significance Analysis We adopt the
approach used in [31] to analyze the statistical
significance of the improvements. We formulate
the null hypothesis H 0 which states that the autocorrelogram
method is as likely to cause a negative
change in rank as a non-negative one. Under
the expected number of negative changes
is with a standard deviation
4:39. The actual number of negative
changes is 4, which is less than M \Gamma 7oe. We can reject
H 0 at more than 99:9% standard significance
level.
For 67 out of 77 queries, autocorrelograms perform
as well as or better than CCV(s). In the
cases where autocorrelograms perform better than
CCV(s), the average improvement in rank is 66
positions. In the ten cases where CCV(s) perform
better, the average improvement is two positions.
Autocorrelograms, however, still rank the correct
answers within top 12 in these cases. Again, statistical
analysis proves that autocorrelograms are
better than CCV(s).
From a usability point of view, we make the
following observation. Given a query, the user is
guaranteed to locate the correct answer by just
checking the top two search results (on average) in
the case of autocorrelogram. On the other hand,
the user needs to check at least the top 80 search
results (on average) to locate the correct answer
in the case of histogram (or top 40 search results
for the CCV(s)). In practice, this implies that the
former is a more "usable" image retrieval scheme
than the latter two.
4.3.2. Recall Comparison Table 2 shows the
performance of three features on our four category
queries. The L 1 distance metric is used. Once
again, autocorrelograms perform the best.
4.3.3. Relative distance metric Table 3 compares
the results obtained using d 1 and L 1 distance
measures on different features (64 colors).
Using d 1 distance measure is clearly superior. The
improvement is specially noticeable for histograms
and CCV(s) (for instance, for the owl images in

Figure

6).
A closer examination of the results shows, how-
ever, that there are instances where the d 1 distance
measure performs poorly compared to the
distance measure on histograms and CCV(s).
An example is shown in Figure 7.
It seems that the failure of the d 1 measure is related
to the large change of overall image brightness
(otherwise, the two images are almost identi-
cal). We need to examine such scenarios in greater
detail. Autocorrelograms, however, are not affected
by d 1 in this case. Nor does d 1 improve the
performance of autocorrelogram much. In other
words, autocorrelograms seem indifferent to the

Table

2. Scope vs. recall results for category queries. (Larger numbers indicate better performance.)
Recall
Query 1 Query 2
Scope hist ccv(s) auto hist ccv(s) auto
Recall
Query 3 Query 4
Scope hist ccv(s) auto hist ccv(s) auto

Table

3. Comparison of L1 and d1
Method hist ccv(s) auto hist ccv(s) auto
distance measure d 1 distance measure
r-measure 6301 3272 172 926 326 164
avg. r-measure
p1-measure 21.25 31.60 58.03 47.94 52.09 59.92
avg.
hist: 540. ccv(s): 165. auto:4. (L 1 )
hist: 5. ccv(s): 4. auto:4. (d 1 )
Fig. 6. A case where d 1 is much better than L 1 .
hist: 1. ccv(s): 1. auto: 1. (L 1 )
hist: 213. ccv(s): 40. auto: 1. (d 1 )
Fig. 7. A case where d 1 is worse than L 1 .
distance measure. This needs to be formally
4.3.4. Filtering Table 4 shows the results of applying
a histogram filter before using the autocor-
5Fig. 8. The query image, the image ranked one, and the image ranked two.
Fig. 9. The change of autocorrelation of yellow color with distance.
relogram (we use 64-color histograms and auto-
correlograms).
As we see, the quality of retrieval even improves
somewhat (because false positives are eliminated).
As anticipated, the query response time is less
since we consider the correlograms of only a small
filtered subset of the featurebase.
4.3.5. Discussion The results show that the autocorrelogram
tolerates large changes in appearance
of the same scene caused by changes in viewing
positions, changes in the background scene,
partial occlusions, camera zoom that causes radical
changes in shape, etc. Since we chose small
values f1; 3; 5; 7g for the distance set D, the auto-
Table

4. Performance of auto(L 1 ) with hist(d 1 ) filter.
Method unfiltered filtered
r-measure 172 166
correlogram distills the global distribution of local
color spatial correlations. In the case of camera
zoom (for example, the third pair of images on
the left column of Figure 4), though there are big
changes in object shapes, the local color spatial
correlations as well as the global distribution of
these correlation do not change that much. We
illustrate this by looking at how the autocorrelation
of yellow color changes with distance in the
following three images (Figure 8). Notice that the
size of yellow circular and rectangular objects in
the query image and the image ranked one are dif-
ferent. Despite this, the correlation of yellow with
yellow for the local distance of the image ranked
one is closer to that of the query image than the
image ranked, say, two (Figure 9).
5. Image Subregion Querying Using Correlogram

The image subregion querying problem is the fol-
lowing: given as input a subregion query Q of an
image I and an image set S, retrieve from S those
images Q 0 in which the query Q appears according
to human perception (denoted Q ' Q 0 ). The
set of images might consist of a database of still
images, or videos, or some combination of both.
The problem is made even more difficult than image
retrieval by a wide variety of effects that cause
the same object to appear different (such as changing
viewpoint, camera noise and occlusion). The
image subregion querying problem arises in image
retrieval and in video browsing. For example, a
user might wish to find other pictures in which a
given object appears, or other scenes in a video
with a given appearance of a person.
Performance Measure We use the following measures
to evaluate the performance of various competing
image subregion querying algorithms. If
are the query images, and for the i-th
query
a i are the only images
that "contain" Q i , (i.e., Q i "appears in" I (i)
due to the presence of false matches
the image subregion querying algorithm may return
this set of "answers" with various ranks.
1. Average r-measure gives the mean rank of the
answer-images averaged over all queries. It is
given by either of the following expressions:q
a i
rank(I (i)
a i
rank(I (i)
a i (20)
The macroaveraged r-measure given by Equation
19 treats all queries with equal impor-
tance, whereas the microaveraged r-measure
defined by Equation 20 gives greater weightage
to queries that have a larger number of
answers. In both cases a lower value of the
r-measure indicates better performance.
2. Average precision for a query Q i is given by
a i
are the answers for query Q i in the order that
they were retrieved. This quantity gives the
average of the precision values over all recall
points (with 1:0 being perfect performance).
3. Recall/Precision vs. Scope: For a query Q i
and a scope s ? 0, the recall r is defined as
jfI (i)
and the precision
p is defined as jfI (i)
These measures are simpler than the traditional
average precision measure but still evaluate
the effectiveness of the subregion query
retrieval. For both measures, higher values
indicate better performance.
Organization Section 5.1 explains our approach
to the problem. Section 5.2 describes the experimental
setup and Section 5.3 presents the results.
5.1. Correlogram Intersection
The image subregion querying problem is a harder
problem than image retrieval based on whole image
matching. To avoid exhaustive searching sub-regions
in an image, one scheme is to define intersection
of color histograms [43]. The scheme can
be interpreted in the following manner. (This interpretation
helps us to generalize the method to
correlograms easily.)
Given the histograms for a query Q and an image
I, the intersection of these two histograms can
be considered as the histogram of an abstract entity
notated as the intersection Q " I, (which will
not be defined but serves as a conceptual and notational
convenience only). With the color count
of the intersection defined as
we can define the intersection of the histograms of
Q and I as
Note that this definition is not symmetric in Q
and I. The distance is a measure
of the presence of Q in I. When Q is a subset of
all the color counts
in Q are less than those in I, and the histogram
intersection simply gives back the histogram for
Q.
In an analogous manner, we define the intersection
correlogram as the correlogram of the intersection
merely an abstract entity.)
With the count
we can define the intersection correlogram as follows

Again we measure the presence of Q in I by the
distance jQ\GammaQ"Ij fl;L 1 , say if
were chosen. If Q ' I, then the latter "should
have at least as many counts of correlating color
pairs" as the former. Thus the counts \Gamma and H for
are again those of Q, and the correlogram
of becomes exactly the correlogram of Q,
giving
We see that the distance between Q and Q " I
vanishes when Q is actually a subset of I; this
affirms the fact that both correlograms and histograms
are global features. Such a stable property
is not satisfied by all features - for instance,
spatial coherence [31] is not preserved under sub-set
operations. Therefore, methods for subregion
querying based on such unstable features are not
likely to perform as good as the histogram or correlogram
based methods.
5.2. Experiments
The image database is the same as in Section 4.2.
We use 64 color bins for histograms and autocor-
relograms. The distance set for autocorrelograms
is 7g. Our query set for this task
consists of queries. Queries have 2 to 16 answer
images with the average number of answers
per query being nearly 5. The query set is constructed
by selecting "interesting" portions of images
from the image database. The answer images
contain the object depicted in the query, but often
with its appearance significantly changed due
to changes in viewpoint, or different lighting, etc.
Examples of some queries and answers (and the
rankings according to the histogram and autocorrelogram
intersection methods) are shown in Figure
10.
5.3. Results
The histogram and autocorrelogram intersection
methods for subregion querying are compared in

Tables

5 and 6. For each of the evaluation measures
proposed above, the autocorrelogram performs
better. The average rank of the answer
images improves by over positions when the
autocorrelogram method is used, and the average
precision figure improves by an impressive
56% (see

Table

5). Table 6 shows the precision
and recall values for the two methods at various
scopes. Once again, autocorrelograms perform
consistently better than histograms at all scopes.
Doing a query-by-query analysis, we find that au-
tocorrelograms do better in terms of the average
r-measure on 23 out of the queries. Similarly,
autocorrelograms yield better average precision on
26 out of queries. Thus, for a variety of performance
metrics, autocorrelograms yield better
results. This suggests that the autocorrelogram
is a significantly superior method for subregion
querying problem.
6. Other Applications of Correlograms
6.1. Localization Using Correlograms
The location problem is the following: given a
query image (also referred to as the target or
model) Q and an image I such that Q ' I, find
the "location" in I where Q is "present". It is
hard to define the notion of location mathematically
because the model is of some size. We use
the location of the center of the model for convenience

This problem arises in tasks such as real-time
object tracking or video searching, where it is necessary
to localize the position of an object in an
image. Given an algorithm that solves the location
problem, tracking an object Q in an image
frame sequence ~ I = I I t is equivalent to
finding the location of Q in each of the I i 's. Efficiency
is also required in this task because huge
amounts of data need to be processed.
To avoid exhaustive searching in the whole image
(template matching is of such kind), histogram
backprojection was proposed to handle
the location problem efficiently. In the following,
we study the histogram backprojection algorithm
first. Then we show how the correlogram can be
used to improve the performance.
The location problem can be viewed as a special
case of the image retrieval problem in the following
manner. Let Ij p denote the subimage in I
of size Q located at position p. (The assumption
about the size of the subimage is without loss of
generality.) The set of all subimages Ij
present in I constitutes the image database and
Query auto: 1, hist: 1 auto: 6, hist:
Query auto: 2, hist: 50 auto: 5, hist: 113 auto: 9, hist: 220
Query auto: 6, hist: 6 auto: 19, hist: 48 auto: 9, hist: 57
Query auto: 4, hist: 23 auto: 6, hist:
Query auto: 1, hist: 1 auto: 3, hist: 38 auto: 28, hist:
Query auto: 1, hist: 2 auto: 2, hist: 6 auto: 3, hist: 5
Fig. 10. Sample queries and answer sets with ranks for various methods. (Lower ranks are better.)
Table

5. Performance of Histogram and Autocorrelogram Intersection methods - I. (Smaller r-measure and larger precision
are better.)
Method Avg. r-measure (macro) Avg. r-measure (micro) Avg. precision
Hist 56.3 61.3 0.386
Auto 22.5 29.1 0.602

Table

6. Performance of Histogram and Autocorrelogram Intersection methods - II. (Larger values are better.)
Hist 0.273 0.223 0.133 0.311 0.460 0.681
Auto 0.493 0.347 0.165 0.541 0.718 0.850
Q is the query image. The solution Ij p to this
retrieval problem gives p, the location of Q in I.
The above interpretation is a template matching
process. One straightforward approach to the location
problem is template matching. Template
matching takes the query Q as a template and
moves this template over all possible locations in
the image I to find the best match. This method
is likely to yield good results, but is computationally
expensive. Attempts have been made to make
template matching more efficient [36, 28, 2]. The
histogram backprojection method is one such approach
to this problem. This method has some
serious drawbacks, however. In the following, we
explain the problem with the histogram backprojection
scheme.
The basic idea behind histogram backprojection
is (1) to compute a "goodness value" for each pixel
in I (the goodness of each pixel is the likelihood
that this pixel is in the target); and (2) obtain the
subimage (and hence the location) whose pixels
have the highest goodness values.
Formally, the method can be described as fol-
lows. The ratio histogram is defined for a color c
as
The goodness of a pixel p 2 I c is defined to be
c;h (IjQ). The contribution of a subimage Ij p is
given by
Then, the location of the model is given by
p2I
The above method generally works well in prac-
tice, and is insensitive to changes of image resolution
or histogram resolution [43]. Note that
backprojecting the ratio-histogram gives the same
goodness value to all pixels of the same color. It
emphasizes colors that appear frequently in the
query but not too frequently in the image. This
could result in overemphasizing certain colors in
model image
incorrect answer
Fig. 11. False match of histogram-backprojection.
Q. A color c is said to be dominant in Q, if
c;h (IjQ) is maximum over all colors. If I has
a subimage Ij p (which may be totally unrelated
to Q) that has many pixels of color c, then this
method tends to identify Q with Ij p , thus causing
an error in some cases.

Figure

11 shows a simple example illustrating
this problem. Suppose Q has 6 black pixels and 4
white pixels, and image I has 100 black pixels and
100 white pixels. Then -
The location of the model according to the back-projection
method is in an entirely black patch,
which is clearly wrong.
Another problem with histogram backprojection
is inherited from histograms which have no
spatial information. Pixels of the same color have
the same goodness value irrespective of their posi-
tion. Thus, false matches occur easily when there
are multiple similarly colored objects, as shown in
the examples of red roses and zebras in Figure 12.
Performance Measure Let an indicator variable
loc(Q; I) be 1 if the location returned by a method
is within reasonable tolerance of the actual location
of Q in I. Then, given a series of queries
corresponding images I
the success ratio of the method is given by
For tracking an object Q in a sequence of frames
~
, the success ratio is therefore
Organization Section 6.1.1 introduces the correlogram
correction for the location problem. Section
6.1.2 contains the experiments and results.
6.1.1. Correlogram Correction To alleviate the
problems with histogram backprojection, we incorporate
local spatial correlation information by
using a correlogram correction factor in Equation
26. The idea is to integrate discriminating local
characteristics while avoiding local color template
matching [5]. We define a local correlogram
contribution based on the autocorrelogram of the
subimage Ij p so that the goodness of a pixel depends
on its position in addition to its color.
c (Q) is considered to be the average contribution
of pixel of color c in Q (for each distance
k).
For each pixel p 2 I, the local autocorrelogram
p is computed for each distance k 2 D
(D should contain only small values so that ff (k)
captures local information for each p)
where fpg represents the pixel p along with its
neighbors considered as an image. Now, the correlogram
contribution of p is defined as
In words, the contribution of p is the L 1 -distance
between the local autocorrelogram at p and the
part of the autocorrelogram for Q that corresponds
to the color of p.
Combining this contribution with Equation 26,
the final goodness value of a subimage Ij p is given
by
It turns out that the correlogram contribution
by itself is also sensitive and occasionally overemphasizes
less dominant colors. Suppose c is a less
dominant color (say, background color) that has
a high autocorrelation. If I has a subimage Ij p
(which may be totally irrelevant to Q) that has
many pixels of color c with high autocorrelations,
then correlogram backprojection has a tendency
to identify Q with Ij p , thus potentially causing
an error. Since the problems with histograms and
correlograms are in some sense complementary to
each other, the best results are obtained when the
goodness of a pixel is given by a weighted linear
combination of the histogram and correlogram
backprojection contributions - adding the local
correlogram contribution to histogram backprojection
remedies the problem that histograms do
not take into account any local information; the
histogram contribution ensures that background
colors are not overemphasized. We call this correlogram
correction.
This can also be understood by drawing an analogy
between this approach and the Taylor expan-
sion. The goodness value obtained from histogram
backprojection is like the average constant value in
the Taylor expansion; the local correlogram contribution
is like the first order term in the approx-
imation. Therefore, the best results are obtained
when the goodness value of a pixel is a weighted
linear combination of the histogram backprojection
value and the correlogram contribution.
6.1.2. Experiments and Results We use the
same database to perform the location experi-
ments. A model image and an image that contains
the model are chosen. For the location prob-
lem, 66 query images and 52 images that contain
these models are chosen and tested. Both the histogram
backprojection and autocorrelogram correction
are tried.
the parameters.
For the tracking problem, we choose three
videos bus(133 frames), clapton (44 frames), sky-
dive (85 frames). We use
0:8 for this problem.
For the location problem, Table 7 shows the results
for 66 queries, and Figure 12 shows some
examples.
For the tracking problem, Table 8 shows the result
of histogram backprojection and correlogram
correction for the three test videos. These results
clearly show that correlogram correction alleviates
many of the problems associated with simple histogram
backprojection.

Figure

13 shows sample outputs.
6.2. Cut Detection Using Correlograms
The increasing amount of video data requires automated
video analysis. The first step to the automated
video content analysis is to segment a
video into camera shots (also known as key frame
extraction). A camera shot ~ I = I I t is an
unbroken sequence of frames from one camera. If
~
J denotes the sequence of cuts, then a cut J j occurs
when two consecutive frames hI are
from different shots.
Cut detection algorithms assume that consecutive
frames in a same shot are somewhat more
similar than frames in a different shot (other gradual
transition, such as fade and dissolve, are not
studied here because certain mathematical models
can be used to treat these chromatic editing
effects). Different cut detectors use different features
to compare the similarity between two consecutive
frames, such as pixel difference, statistical
differences, histogram comparisons, edge dif-
ferences, etc [1]. One way to detect cuts using
a feature f is by ranking hI according to
I) be the number of actual
cuts in ~ I and rank(J i ) be the rank of the cut J i
according to this ranking.
Histograms are the most common used image
features to detect cuts because they are efficient to

Table

7. Results for location problem (66 queries).
Method hist auto
Success Ratio 0.78 0.96

Table

8. Results (success ratios) for the tracking problem.
Method hist auto
bus 0.93 0.99
clapton 0.44 0.78
skydive 0.96 0.96
Fig. 12. Location problem: histogram output, query image, and correlogram output.
compute and insensitive to camera motions. His-
tograms, however, are not robust to local changes
in images that false positives easily occurs in this
case (see Figure 14). Since correlograms have been
shown to be robust to large appearance changes
for image retrieval, we use correlograms for cut
detection.
Performance Measure Recall and precision are
usually used to compare the performance of cut
detection. However, it is difficult to measure the
performance of different algorithms based on recall
vs. precision curves [1]. Therefore we look
at recall and precision values separately. In order
to avoid using "optimal" threshold values, we
use precision vs. scope to measure false positives
and recall vs. scope to measure false negatives
(misses). We choose scope values to be the exact
cut number cuts( ~
I) and 2 cuts( ~
I). We also use the
excessive rank value, which is defined by
cuts( ~ I)
and the average precision value which is defined
cuts( ~ I)
Note that a smaller excessive rank value and a
larger average precision value indicate better result
(perfect performance would have values 0 and
6.2.1. Experiments and Results We use 64 colors
for histograms, and banded autocorrelograms
which have the same size as histograms. We use
5 video clips from television, movies, and com-
mercials. The clips are diverse enough to capture
different kinds of common scenarios that occur in
practice. The results are shown in Table 9 and

Table

10.
The results of our experiments show that
banded autocorrelograms are more effective than
histograms while the two have the same amount
of information. It is certainly more efficient than
dividing an image into 16 subimages [15]. Thus
the autocorrelogram is a promising tool for cut
detection.
Fig. 13. Tracking problem: histogram output, query image, and correlogram output.
Fig. 14. Cut detection: False cuts detected by histogram but not by correlogram.

Table

9. Recall vs. Scope for cut detection. (Smaller values are better.)
hist banded-auto
I) ex. rank value
Table

10. Precision vs. Scope for cut detection. (Larger values are better.)
hist banded-auto
Avg. Prec. Value cuts( ~ I) 2 cuts( ~
I) Avg. Prec. Value
7. Conclusions
In this paper, we introduced the color correlogram
- a new image feature - for solving several problems
that arise in content-based image retrieval
and video browsing. The novelty in this feature
is the characterization of images in terms of the
spatial correlation of colors instead of merely the
colors per se. Experimental evidence suggests that
this information discriminates between "different"
images and identifies "similar" images very well.
We show that correlograms can be computed, pro-
cessed, and stored at almost no extra cost compared
to competing methods, thereby justifying
using this instead of many other features to get
better image retrieval quality.
The most important application of correlograms
is to content-based image retrieval (CBIR) sys-
tems. Viewed in this context, a correlogram
is neither a region-based nor a histogram-based
method. Unlike purely local properties, such as
pixel position, and gradient direction, or purely
global properties, such as color distribution, a correlogram
takes into account the local color spatial
correlation as well as the global distribution of
this spatial correlation. While any scheme that is
based on purely local properties is likely to be sensitive
to large appearance changes, correlograms
are more stable to tolerate these changes and while
any scheme that is based on purely global properties
is susceptible to false positive matches, correlograms
seem to be scalable for CBIR. This is corroborated
by our extensive experiments on large
image collections, where we demonstrate that correlograms
are very promising for CBIR.
One issue that still needs to be resolved satisfactorily
is the following: in general, illumination
changes are very hard to handle in color-based
CBIR systems [12, 45, 10, 39]. During our experi-
ments, we encountered this problem occasionally.
Though the correlogram method performs better
on a relative scale, its absolute performance is not
fully satisfactory. The question is, can correlo-
grams, with some additional embellishments, be
made to address this specific problem?
On a related note, it also remains to be seen
if correlograms, in conjunction with other fea-
tures, can enhance retrieval performance. For in-
stance, how will the correlogram perform if shape
information is used additionally? This brings up
the question of object-level retrieval using correlo-
grams. More work needs to be done in this regard
as to finding a better representation for objects.
Further applications of color correlograms are
image subregion querying and localization, which
are indispensable features of any image management
system. Our notions of correlogram intersection
and correlogram correction seem to perform
well in practice. There is room for improvement
of course, and these need to be investigated in
greater detail. We also apply correlograms to the
problem of detecting cuts in video sequences. An
interesting question that arises here is, can this
operation be done in the compressed domain [48]?
This would cut down the computation time drastically
and make real-time processing feasible.
Another major challenge in this context is:
what distance metric for comparing images is close
to the human perception of similarity? Does a
measure need to be a metric [25]? We also plan
to use supervised learning to improve the results
of image retrieval and the subregion querying task
(we have some initial results in [19]).
In general, the algorithms we propose for various
problems are not only very simple and inexpensive
but are especially easy to incorporate into
a CBIR system if the underlying indexing scheme
is correlogram-based. It pays off more in general
if there is a uniform feature vector that is universally
applicable to providing various functionalities
expected of a CBIR system (like histograms
advocated in [43]). It is unreasonable to expect
any CBIR system to be absolutely fool-proof; fur-
thermore, it is needless to state that the correlogram
is not the panacea. The goal, however, is to
build relatively better CBIR systems. Based on
various experiments, we feel that there is a compelling
reason to use correlograms as one of the
basic building blocks in such systems.

Acknowledgements

Jing Huang and Ramin Zabih were supported
by the DARPA grant DAAL 01-97-K-0104. S
Ravi Kumar was supported by the ONR Young
award N00014-93-1-0590, the NSF
grant DMI-91157199, and the career grant CCR-
9624552. Mandar Mitra was supported by the
NSF grant IRI 96-24639. Wei-Jing Zhu was supported
by the DOE grant DEFG02-89ER45405.
Notes
1. In our database of 14,554 images, the right image is
considered the 353-rd most similar with respect to the
left image by color histogram.
2. The term "correlogram" is adapted from spatial data
analysis: "correlograms are graphs (or tables) that show
how spatial autocorrelation changes with distance."
3. Interestingly, histogram or CCV may not be able to
distinguish between these two images.
4. Equivalently, we could select some threshold image
score.



--R

"A comparison of video shot boundary detection techniques,"
"Using color templates for target identification and tracking,"
"Content-based image retrieval systems,"
"PicHunter: Bayesian relevance feed-back for image retrieval,"
"Finding waldo, or focus of attention using local color information,"
"Query analysis in a visual information retrieval context,"
"Finding naked people,"
"Query by image and video con- tent: The QBIC system,"
"Finding pictures of objects in large collections of images,"
"Color constant color in- dexing,"
"An image database system with content capturing and fast image indexing abilities,"
"Intelligent Image Databases: Towards Advanced Image Retrieval,"
"Localising overlapping parts by searching the interpretation tree,"
"Efficient color histogram indexing for quadratic form distance functions,"
"Digital video indexing in multimedia systems,"
"Statistical and structural approaches to texture,"
"Decision theoretic generalization of the PAC model for neural net and other learning appli- cations,"
"An integrated color-spatial approach to content-based image retrieval,"
"Combin- ing supervised learning with color correlograms for content-based image retrieval,"
"Spatial color indexing and applications,"
"Image indexing using color correlograms,"
"Comparing images using the Hausdorff distance,"
"Object recognition using subspace methods,"
"Object recognition using alignment,"
"Con- densing image databases when retrieval is based on non-metric distances,"
"Representation and recognition of the spatial organization of three-dimensional shapes,"
"On representation and matching of multi-colored objects,"
"Focused color intersection with efficient searching for object detection and image retrieval,"
"Visual learning and recognition of 3-D objects from appearance,"
"Chabot: Retrieval from a relational database of images,"
"Histogram refinement for content-based image retrieval,"
"Comparing images using color coherence vectors,"
"Photobook: Content-based manipulation of image databases,"
"Object indexing using an iconic sparse distributed memory,"
"Content-based image retrieval using color tuple histograms,"
"Using probabilistic domain knowledge to reduce the expected computational cost of template matching,"
"Machine perception of three-dimensional solids,"
"Robust regression and outlier detection,"
"Combining color and geometric information for the illumination invariant recognition of 3-D objects,"
"Tools and techniques for color image retrieval,"
"Color indexing with weak spatial constraints,"
"The capacity of color histogram indexing,"
"Color indexing,"
"Data and model-driven selection using color regions,"
"Indexing colored surfaces in images,"
"Spatial data analysis by example. Vol I.,"
"Color distribution analysis and quantization for image retrieval,"
"Rapid scene analysis on compressed videos,"
--TR

--CTR
L. Kotoulas , I. Andreadis, Parallel Local Histogram Comparison Hardware Architecture for Content-Based Image Retrieval, Journal of Intelligent and Robotic Systems, v.39 n.3, p.333-343, March 2004
Naofumi Wada , Shun'ichi Kaneko , Tomoyuki Takeguchi, Using color reach histogram for object search in colour and/or depth scene, Pattern Recognition, v.39 n.5, p.881-888, May, 2006
Daniel Berwick , Sang Wook Lee, Spectral gradients for color-based object recognition and indexing, Computer Vision and Image Understanding, v.94 n.1-3, p.28-43, April/May/June 2004
Ba Tu Truong , Svetha Venkatesh , Chitra Dorai, Extraction of Film Takes for Cinematic Analysis, Multimedia Tools and Applications, v.26 n.3, p.277-298, August    2005
M. Das , E. M. Riseman, FOCUS: a system for searching for multi-colored objects in a diverse image database, Computer Vision and Image Understanding, v.94 n.1-3, p.168-192, April/May/June 2004
Yun Fan , Runsheng Wang, An image retrieval method using DCT features, Journal of Computer Science and Technology, v.17 n.6, p.865-873, November 2002
Robert T. Collins , Yanxi Liu , Marius Leordeanu, Online Selection of Discriminative Tracking Features, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.10, p.1631-1643, October 2005
Dirk Neumann , Karl R. Gegenfurtner, Image retrieval and perceptual similarity, ACM Transactions on Applied Perception (TAP), v.3 n.1, p.31-47, January 2006
J. Matas , D. Koubaroulis , J. Kittler, The multimodal neighborhood signature for modeling object color appearance and applications in object recognition and image retrieval, Computer Vision and Image Understanding, v.88 n.1, p.1-23, October 2002
Hau-San Wong , Horace H. Ip , Lawrence P. Iu , Kent K. Cheung , Ling Guan, Transformation of Compressed Domain Features for Content-Based Image Indexing and Retrieval, Multimedia Tools and Applications, v.26 n.1, p.5-26, May       2005
Multiresolution Histograms and Their Use for Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.7, p.831-847, July 2004
Dorin Comaniciu , Visvanathan Ramesh , Peter Meer, Kernel-Based Object Tracking, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.564-575, May
Arnold W. M. Smeulders , Marcel Worring , Simone Santini , Amarnath Gupta , Ramesh Jain, Content-Based Image Retrieval at the End of the Early Years, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.12, p.1349-1380, December 2000
Thomas B. Moeslund , Adrian Hilton , Volker Krger, A survey of advances in vision-based human motion capture and analysis, Computer Vision and Image Understanding, v.104 n.2, p.90-126, November 2006
image indexing;model-based object recognition;spatial correlation;image features;content-based image retrieval