We propose
a structured approach to the problem of retrieval of images by content and
present a description logic that has been devised for the semantic indexing and
retrieval of images containing complex objects.
As other approaches do, we
start from lowlevel features extracted with image analysis to detect and
characterize regions in an image. However, in contrast with featurebased
approaches, we provide a syntax to describe segmented regions as basic objects
and complex objects as compositions of basic ones. Then we introduce a
companion extensional semantics for defining reasoning services, such as
retrieval, classification, and subsumption. These services can be used for both
exact and approximate matching, using similarity measures.
Using our logical approach
as a formal specification, we implemented a complete clientserver image retrieval
system, which allows a user to pose both queries by sketch and queries by
example. A set of experiments has been carried out on a testbed of images to
assess the retrieval capabilities of the system in comparison with expert users
ranking. Results are presented adopting a wellestablished measure of quality
borrowed from textual information retrieval.
Image
retrieval is the problem of selecting, from a repository of images, those
images fulfilling to the maximum extent some criterion specified by an end
user. In this paper, we concentrate on contentbased image retrieval,
in which criteria express properties of the appearance of the image itself, i.e., on
its pictorial characteristics.
Most of the research in
this field has till now concentrated in devising suitable techniques for
extracting relevant cues with the aid of image analysis algorithms. Current
systems result effective when the specified properties are socalled lowlevel
characteristics, such as color distribution, or texture. For example, systems
such as IBM's QBIC^{1} can easily retrieve, among others, stamps containing the picture of a
brown horse in a green field, when asked to retrieve images of stamps with
brown central area over a greenish background.
Nevertheless, present
systems fail at treating correctly highlevel characteristics of an
image  such as, ``retrieve stamps with a galloping horse". First of all,
most systems cannot even allow the user to specify such queries, because they
lack a language for expressing highlevel features. Usually, this is
overcome with the help of examples: ``retrieve images similar to this
one". However, examples are quite ambiguous to interpret: which are the
features in the example that should appear in retrieved images? This ambiguity
produces a lot of ``false positives", as any one can experience.
Even if relevant features
are pointed out in the example, the system cannot tell whether what is pointed
out is the color distribution, or its interpretation  after all, a galloping
brown horse produces a color distribution which is more similar to a running
brown fox than to a galloping white horse. In this aspect, image
retrieval faces the same problems of object recognition, which is a
central problem in robotics and artificial vision. The only effective solution
overcoming this problem is to associate to a query some significant keywords,
which should match keywords attached in some way to images in the repository.
Here ambiguities in image understanding are just transferred to text
understanding, as now a brown portrait of Crazy Horse  the famous Indian chief
 could be considered relevant.
Resorting to human experts
to specify the expected output of a retrieval algorithm can, in our opinion,
only worsen these ambiguities, since it makes the correctness of an approach to
depend from a subjective perception of what an image retrieval system should
do. What is needed is a formal, highlevel specification of the image retrieval
task. This need motivates the research we report here.
We approach the problem of
image retrieval from a knowledge representation perspective, and in particular,
we refer to a framework already successfully applied by Woods and
Schmolze (1992) to conceptual modeling and semantic data
models in databases [ Calvanese, Lenzerini, & Nardi 1998].
We consider image retrieval as a knowledge representation problem, in which we can
distinguish the following aspects:
Interface: the user is given a simple visual
language to specify (by sketch or by example) a geometric composition of basic
shapes, which we call description. The composite shape description intuitively
stands for a set of images (all containing the given shapes in their relative
positions); it can be used either as a query, or as an index for a relevant
class of images, to be given some meaningful name.
Syntax and semantics: the system has an internal syntax
to represent the user's queries and descriptions, and the syntax is given an
extensional semantics in terms of sets of retrievable images. In contrast with
existing image retrieval systems, our semantics is compositional, in the sense
that adding details to the sketch may only restrict the set of retrievable
images. Syntax and semantics constitute a Semantic Data Model, in which the
relative position, orientation and size of each shape component are given an
explicit notation through a geometric transformation. The extensional semantics
allows us to define a hierarchy of composite shape descriptions, based on set
containment between interpretations of descriptions. Coherently, the
recognition of a shape description in an image is defined as an interpretation
satisfying the description.
Algorithms and
complexity: based
on the semantics, we prove that subsumption between descriptions can be carried
out in terms of recognition. Then we devise exact and approximate algorithms
for composite shapes recognition in an image, which are correct with respect to
the semantics. Ideally, if the computational complexity of the problem of
retrieval was known, the algorithms should also be optimal with reference
to the computational complexity of the problems. Presently, we solved the
problem for exact retrieval, and propose an algorithm for approximate retrieval
which, although probably nonoptimal, is correct.
Experiments: while the study of the complexity
of the problem is ongoing, the syntax, semantics, and suboptimal algorithms
obtained so far are already sufficient to provide the formal specification of a
prototype system for the experimental verification of our approach. The
prototype has been used to carry out a set of experiments on a test database of
images, which allowed us to verify the effectiveness of the proposed approach
in comparison with expert users ranking.
We believe that a knowledge
representation approach brings several benefits to research in image retrieval.
First of all, it separates the problem of finding an intuitive semantics for
query languages in image retrieval from the problem of implementing a correct
algorithm for a given semantics. Secondly, once the problem of image retrieval
is semantically formalized, results and techniques from Computational Geometry
can be exploited in assessing the computational complexity of the formalized
retrieval problem, and in devising efficient algorithms, mostly for the approximate
image retrieval problem. This is very much in the same spirit as finite model
theory has been used in the study of complexity of query answering for
relational databases [ Chandra & Harel, 1980].
Third, our language borrows from object modeling in Computer Graphics the
hierarchical organization of classes of images [ Foley, van Dam, Feiner, &
Hughes, 1996].
This, in addition to an interpretation of composite shapes which one can
immediately visualize, opens our logical approach to retrieval of images of
3Dobjects constructed in a geometric language [ Paquet & Rioux, 1998],
which is still to be explored. Fourth, our logical formalization, although
simple, allows for extensions which are natural in logic, such as disjunction
(OR) of components. Although alternative components of a complex shape are
difficult to be shown in a sketch, they could be used to specify moving (i.e., nonrigid)
parts of a composite shape. This exemplifies how our logical approach can shed
light to extensions of our syntax suitable for, e.g., video
sequence retrieval.
The rest of the paper is
organized as follows. In the next section, we review related work on image
retrieval. In Section 3 we describe our formal language, first its syntax,
then its semantics, and we start proving some basic properties. In the
following section, we analyze the reasoning problems and the semantic relations
among them, and we devise algorithms that can solve them. Then in Section 5 we illustrate the architecture of
our system and propose some examples pointing out distinguishing aspects of our
approach. In Section 6 we present a set of experiments to assess retrieval
capabilities of the system. Last section draws the conclusions and proposes
directions for future work.
ContentBased Image Retrieval (CBIR) has recently become a widely
investigated research area. Several systems and approaches have been proposed;
here we briefly report on some significant examples and categorize them in
three main research directions.
Largest
part of research on CBIR has focused on lowlevel features such as color,
texture, shape, which can be extracted using image processing algorithms and
used to characterize an image in some feature space for subsequent indexing and
similarity retrieval. In this way the problem of retrieving images with
homogeneous content is substituted with the problem of retrieving images
visually close to a target one [ Hirata & Kato, 1992; Niblack et
al., 1993; Picard &
Kabir, 1993; Jacobs, Finkelstein, & Salesin, 1995; Flickner
et al., 1995; Bach et al.,
1996; Celentano & Di Sciascio, 1998; Cox
et al., 2000; Gevers &
Smeulders, 2000].
Among the various projects,
particularly interesting is the QBIC system [ Niblack et al., 1993; Flickner
et al., 1995;], often cited as the ancestor of all other
CBIR systems, which allows queries to be performed on shape, texture, color, by
example and by sketch using as target media both images and shots within
videos. The system is currently embedded as a tool in a commercial product, ULTIMEDIA MANAGER. Later versions have introduced an automated
foreground/background segmentation scheme. Here the indexing of an image is
made on the principal shape, with the aid of some heuristics. This is an
evident limitation: most images do not have a main shape, and objects are often
composed of various parts.
Other researchers, rather
than concentrating on a main shape, which is typically assumed located in the
central part of the picture, have proposed to index regions in images; so that
the focus is not on retrieval of similar images, but of similar regions within
an image. Examples of this idea are VISUALSEEK [ Smith & Chang, 1996], NETRA
[
Ma & Manjunath, 1997] and BLOBWORLD [ Carson et al.1999]. The problem is that although all
these systems index regions, they lack of a higher level description of images.
Hence, they are not able to describe  and hence query for  more than a single
region at a time in an image.
In order to improve
retrieval performances, much attention has been paid in recent years to
relevance feedback. Relevance feedback is the mechanism, widely used in textual
information systems, which allows improving retrieval effectiveness by
incorporating the user in the queryretrieval loop. Depending on the initial
query the system retrieves a set of documents that the user can mark either as
relevant or irrelevant. The system, based on the user preferences, refines the
initial query retrieving a new set of documents that should be closer to the
user's information need.
This issue is particularly
relevant in featurebased approaches, as on one hand, the user lacks of a
language to express in a powerful way her information need, but on the other
hand, deciding whether an image is relevant or not takes just a glance.
Examples of systems using relevance feedback include MARS [ Rui, Huang,
& Mehrotra, 1997], DRAWSEARCH [ Di Sciascio & Mongiello,
1999] and PICHUNTER [ Cox et al., 2000].
This type of approach to
the problem of image retrieval concentrates on finding the similarity of images
in terms of spatial relations among objects in them. Usually the emphasis is
only on relative positions of objects, which are considered as ßymbolic
images" or icons, identified with a single point in the 2Dspace.
Information on the content and visual appearance of images are normally
neglected.
Chang,
Shi, and Yan (1983) present the modeling of this type of images in
terms of 2Dstrings, each of the strings accounting for the position of
icons along one of the two planar dimensions. In this approach retrieval of
images basically reverts to simpler string matching.
Gudivada
and Raghavan (1995)
consider the objects in a symbolic image associated with vertexes in a weighted
graph. Edges  i.e., lines connecting the centroids of a pair of
objects  represent the spatial relationships among the objects and are
associated with a weight depending on their slope. The symbolic image is
represented as an edge list. Given the edge lists of a query and a database
image, a similarity function computes the degree of closeness between the two
lists as a measure of the matching between the two spatialgraphs. The
similarity measure depends on the number of edges and on the comparison between
the orientation and slope of edges in the two spatialgraphs. The algorithm is
robust with respect to scale and translation variants in the sense that it
assigns the highest similarity to an image that is a scale or translation variant
of the query image. An extended algorithm includes also rotational variants of
the original images.
More recent papers on the
topic include those by Gudivada (1998) and by ElKwae and Kabuka (1999), which basically propose extensions
of the strings approach for efficient retrieval of subsets of icons. Gudivada
(1998) defines qRstrings, a logical representation of an image. Such representation
also provides a geometrybased approach to iconic indexing based on spatial
relationships between the iconic objects in an image individuated by their
centroid coordinates. Translation, rotation and scale variant images and the
variants generated by an arbitrary composition of these three geometric
transformations are considered. The approach does not deal with object shapes,
nor with other basic image features, and considers only the sequence of the
names of the objects. The concatenation of the objects is based on the euclidean
distance of the domain objects in the image starting from a reference point.
The similarity between a database and a query image is obtained through a
spatial similarity algorithm that measures the degree of similarity between a
query and a database image by comparing the similarity between their qRstrings. The algorithm recognizes rotation, scale and translation
variants of the image and also subimages, as subsets of the domain objects. A
constraint limiting the practical use of this approach is the assumption that
an image can contain at most one instance of each icon or object.
ElKwae
and Kabuka (1999)
propose a further extension of the spatialgraph approach, which includes both
the topological and directional constraints. The topological extension of the
objects can be obviously useful in determining further differences between
images that might be considered similar by a directional algorithm that
considers only the locations of objects in term of their centroids. The
similarity algorithm they propose extends the graphmatching one previously
described by Gudivada and Raghavan (1995). The similarity between two images is based on
three factors: the number of common objects, the directional and topological
spatial constraint between the objects. The similarity measure includes the
number of objects, the number of common objects and a function that determines
the topological difference between corresponding objects pairs in the query and
in the database image. The algorithm retains the properties of the original
approach, including its invariance to scaling, rotation and translation and is
also able to recognize multiple rotation variants.
With reference to previous
work on Vision in Artificial Intelligence, the use of structural descriptions
of objects for the recognition of their images can be dated back to Minsky's
frames, and some work by Brooks (1981). The idea is to associate parts of
an object (and generally of a scene) to the regions an image can be segmented
into. The hierarchical organization of knowledge to be used in the recognition
of an object was first proposed by Marr (1982). Reiter and Mackworth (1989)
proposed a formalism to reason about maps as sketched diagrams. In their
approach, the possible relative positions of lines are fixed and highly
qualitative (touching, intersecting).
Structured descriptions of
threedimensional images are already present in languages for virtual reality
like VRML [ Hartman &
Wernecke, 1996] or hierarchical object modeling. However, the semantics of such
languages is operational, and no effort is made to automatically classify
objects with respect to the structure of their appearance.
Meghini,
Sebastiani, and Straccia (2001) proposed a formalism integrating Description Logics and image and text
retrieval, while Haarslev, Lutz, and Möeller (1998) integrate Description Logics with
spatial reasoning. Further extensions of the approach are described by Moeller, Neumann, and Wessel (1999). Both proposals build on the clean integration of Description Logics
and concrete domains of Baader and Hanschke (1991). However, neither of the formalisms
can be used to build complex shapes by nesting more simple shapes. Moreover,
the proposal by Haarslev et al. (1998) is based on the logic of spatial
relations named RCC8, which is enough for specifying meaningful relations in a
map, but it is too qualitative to specify the relative sizes and positions of
regions in a complex shape.
Also for Hacid and Rigotti (1999) description logics and concrete
domains are at the basis of a logical framework for image databases aimed at
reasoning on query containment. Unfortunately, the proposed formalism cannot
consider geometric transformations neither determine specific arrangements of
shapes.
More similar to our approach is the proposal by Ardizzone, Chella, and Gaglio (1997), where parts of a complex shape are described with a description logic.
However, the composition of shapes does not consider their positions, hence
reasoning cannot take positions into account.
Relative position of parts of a complex shape can be expressed in a
constraint relational calculus in the work by Bertino and Catania (1998). However, reasoning about queries (containment and emptiness) is not
considered in this approach. Aiello (2001) proposes a multimodal logic, which
provides a formalism for expressing topological properties and for defining a
distance measure among patterns.
Spatial relation between parts of medical tomographic images are
considered by Tagare
et al. (1995). There, medical images are formed
by the intersection of the image plane and an object. As the image plane
changes, different parts of the object are considered. Besides, a metric for
arrangements is formulated by expressing arrangements in terms of the Voronoi
diagram of the parts. The approach is limited to medical image databases and
does not provide geometrical constraints.
Compositions of parts of an image are considered in the work by Sanfeliu and Fu (1983) for character recognition. However, in recognizing characters, line
compositions are ``closed", in the sense that one looks for the specified
lines, and no more. Instead in our framework, the shape ``F" composed by
three lines, is subsumed by the shape ``G"  something unacceptable in recognizing characters. Apart from
the different task, this approach does not make use of an extensional semantics
for composite shapes, hence no reasoning is possible.
A logicbased multimedia retrieval system was proposed by Fuhr,
Gövert, and Rölleke (1998); the method, based on an objectoriented
logic, supports aggregated objects but it is oriented towards a highlevel
semantic indexing, which neglects lowlevel features that characterize images
and parts of them.
In the field of computation theories of recognition, we mention two
approaches that have some resemblance to our own: Biederman's structural
decomposition and geometric constraints proposed by Ullman, both described by Edelmann (1999). Unfortunately, neither of them
appears suitable for realistic image retrieval: the structural decomposition
approach does not consider geometric constraints between shapes, while the
approach based on geometric constraints does not consider the possibility of
defining structural decomposition of shapes, hence reasoning on them.
Starting with the reasonable assumption that the recognition of an
object in a scene can be eased by previous knowledge on the context, in the
work by Pirri and Finzi (1999), the recognition task, or the interpretation of an image, takes
advantage of the information a cognitive agent has about the environment, and by
the representation of these data in a highlevel formalism.
In this section we present the
formalism dealing with the definition of composite shape descriptions, their semantics,
and some properties that distinguish our approach from previous ones.
We remark that our formalism deals with image features, like shape,
color, texture, but is independent of the way features are extracted
from actual images. For the interested reader, the algorithms we used to
compute image features in our implementation of the formalism are presented in
the Appendix.
Our main syntactic objects are basic shapes, position of shapes,
composite shape descriptions, and transformations. We also take into account
the other features that typically determine the visual appearance of an image,
namely color and texture.
Basic shapes are denoted with the letter B, and have an edge contour e(B)
characterizing them. We assume that e(B) is described as a single, closed
2Dcurve in a space whose origin coincides with the centroid of B. Examples of
basic shapes can be circle, rectangle, with the contours e(circle)= ⃝, e(rectangle)=⃞, but also any complete, rough contour
 e.g., the one of a ship  is a basic shape. To make our language
compositional, we consider only the external contour of a region. For
example, if a region is contained in another, as in
⃝ 
, the contour of the outer region is just the
external rectangle.
The possible transformations are the simple ones that are present in any
drawing tool: rotation (around the centroid of the shape), scaling and
translation. We globally denote a rotationtranslationscaling transformation
as t. Recall that transformations can be
composed in sequences t_{1}°...°t_{n}, and they form a mathematical group.
The basic building block of our syntax is a basic shape component
ác,t,t,B ñ, which represents a region with
color c, texture t, and edge contour t(e(B)). With t(e(B)) we denote the pointwise
transformation t of the whole contour of B. For
example, t could specify to place the contour
e(B) in the upper left corner of the image, scaled by 1/2 and rotated 45
degrees clockwise.
Composite shape descriptions are conjunctions of basic shape components  each one with its own
color and texture  denoted as

We do not expect end users of our system to actually define composite shapes
with this syntax; this is just the internal representation of a
composite shape. The system can maintain it while the user draws  with the
help of a graphic tool  the complex shape by dragging, rotating and scaling
basic shapes chosen either from a palette, or from existing images (see
Figure 1).
Figure 1: The graphical interface with a query by sketch.
For example, the composite shape lightedcandle could be defined as

with t_{1},t_{2} placing the circle as a flame on top of the candle, and textures and colors
defined accordingly to the intuition.
We remark that, to the best of our knowledge, the logic we present is
the first one combining shapes and explicit transformations in one language.
In a previous paper [ Di Sciascio, Donini, & Mongiello, 2000] we presented a formalism including nested composite shapes, as it is
done in hierarchical object modeling [ Foley et al., 1996,Ch.7]. However, nested composite
shapes can always be flattened by composing their transformations. Hence in
this paper we focus on two levels: basic shapes and compositions of basic
shapes. Also, just to simplify the presentation of the semantics, in the
following section we do not present color and texture features, which we take
into account from Section 4.2 on.
We consider an extensional semantics, in which syntactic expressions are
interpreted as subsets of a domain. For our setting, the domain of interpretation
is a set of images D, and shapes and components are
interpreted as subsets of D. Hence, also an image database is a
domain of interpretation, and a complex shape C is a subset of such a domain 
the images to be retrieved from the database when C is viewed as a query.
This approach is quite different from previous logical approaches to
image retrieval that view the image database as a set of facts, or logical
assertions, e.g., the one based on Description Logics by Meghini et al. (2001). In that setting, image retrieval
amounts to logical inference. However, observe that usually a Domain
Closure Assumption [ Reiter, 1980] is made for image databases: there
are no regions but the ones which can be seen in the images themselves. This
allows one to consider the problem of image retrieval as simple model checking
 check if a given structure satisfies a description^{2}.
Formally, an interpretation
is a pair (Á,D), where D is a set of images, and Á is a mapping from shapes and
components to subsets of D. We identify each image I with the
set of regions {r_{1},...,r_{n}} it can be segmented into
(excluding background, which we discuss at the end of this section). Each
region r comes with its own edge contour e(r). An image I Î D belongs to the interpretation of a basic shape component át,B ñ^{Á} if I contains a region whose
contour matches t(e(B)). In formulae,

(1) 
The above definition is
only for exact recognition of shape components in images, due to the presence
of strict equality in the comparison of contours; but it can be extended to
approximate recognition as follows. Recall that the characteristic function
f_{S} of a set S is a function whose value is either 1 or 0; f_{S}(x)
= 1 if x Î S, f_{S}(x) = 0 otherwise. We consider
now the characteristic function of the set defined in Formula (1). Let I be an image; if I belongs
to át,B ñ^{Á}, then the characteristic function
computed on I has value 1, otherwise it has value 0. To keep the number of
symbols low, we use the expression át,B ñ^{Á}
also to denote the characteristic function (with an argument (I) to distinguish
it from the set).

Now we reformulate this
function in order to make it return a real number in the range [0,1]  as usual
in fuzzy logic [ Zadeh, 1965]. Let sim(·,·) be a similarity measure from
pairs of contours into the range [0,1] of real numbers (where 1 is perfect
matching). We use sim(·,·) instead of equality to compare edge contours. Moreover,
the existential quantification can be replaced by a maximum over all possible
regions in I. Then, the characteristic function for the approximate recognition
in an image I of a basic component, is:

Note that sim depends on
translations, rotation and scaling, since we are looking for regions in I whose
contour matches e(B), with reference to the position and size
specified by t.
The interpretation of basic
shapes, instead, includes a translationrotationscaling invariant recognition,
which is commonly used in singleshape Image Retrieval. We define the
interpretation of a basic shape as

and its approximate
counterpart as the function

The maximization over all
possible transformations max_{t} can be effectively computed by
using a similarity measure sim_{ss} that is invariant with reference
to translationrotationscaling (see Section 4.2). Similarity of color and texture
will be added as a weighted sum in Section 4.2. In this way, a basic shape B can
be used as a query to retrieve all images from D which are in
B^{Á}. Therefore, our approach generalizes the more
usual approaches for singleshape retrieval, such as Blobworld [ Carson
et al., 1999].
Composite shape
descriptions are interpreted as sets of images that contain all components of
the composite shape. Components can be anywhere in the image, as long as they
are in the described arrangement relative to each other. Let C be a composite
shape description át_{1},B_{1} ñÇ¼Çát_{n},B_{n} ñ. In exact matching, the interpretation is the intersection of the sets
interpreting each component of the shape:

(2) 
Observe that we require all
shape components of C to be transformed into image regions using the same
transformation t. This preserves the arrangement of
the shape components relative to each other  given by each t_{i}  while
allowing C^{Á} to include every image containing a
group of regions in the right arrangement, wholly displaced by t.
Figure 2: An
example of application of Formula (2).
To clarify this formula, consider Figure 2:
the shape C is composed by two basic shapes B_{1} and B_{2},
suitably arranged by the transformations t_{1} and t_{2}. Suppose now that D
contains the image I. Then, I Î C^{Á}
because there exists the transformation t,
which globally brings C into I, that is, t°t_{1} brings the rectangle B_{1}
into a rectangle recognized in I, and t°t_{2} brings the circle B_{2}
into a circle recognized in I, both arranged according to C. Note that I could
contain also other shapes, not included in C.
We can now formally define the recognition of a shape in an image.
Definition 1 [Recognition] A shape description C is recognized in an image I
if for every interpretation (Á,D) such that I Î D, it is I Î C^{Á}. An interpretation (Á,D) satisfies a composite shape description C if there exists an image I Î D such that C is recognized in I. A composite shape description is
satisfiable if there exists an interpretation satisfying it.
Observe that shape descriptions could be unsatisfiable: if two components define overlapping regions, no image can be segmented in a way that satisfies both components. Of course, if composite shape descriptions are built using a graphical tool, unsatisfiability can be easily avoided, so we assume that descriptions are always satisfiable. Anyway, unsatisfiable shape descriptions could be easily detected, from their syntactic form, since unsatisfiability can only arise because of overlapping regions (see Proposition 4).
Observe also that our setbased semantics implies the intuitive
interpretation of conjunction ``Ç"  one could easily prove that
Ç is commutative and idempotent.
For approximate matching, we modify definition (2), following the fuzzy
interpretation of Ç as minimum, and existential as
maximum:

(3) 
Observe that our interpretation of composite shape descriptions strictly
requires the presence of all components. In fact, the measure by which an image
I belongs to the interpretation of a composite shape description C^{Á} is dominated by the least similar shape component (the one with the
minimum similarity). Hence, if a basic shape component is very dissimilar from
every region in I, this brings near to 0^{3} also the measure of C^{Á}(I).
This is more strict than, e.g., Gudivada
& Raghavan's (1995)
or ElKwae & Kabuka's (1999) approaches, in which a
nonappearing component can decrease the similarity value of C^{Á}(I),
but I can be still above a threshold.
Although this requirement may seem a strict one, it captures the way
details are used to refine a query: the ``dominant" shapes are used first,
and, if the retrieved set is still too large, the user adds details to restrict
the results. In this refinement process, it should not happen that other images
that match only some new details, ``pop up" enlarging the set of
results that the user was trying to restrict. We formalize this refinement
process through the following definition.
Proposition 1 [Downward refinement] Let C be a composite shape description, and let D be a
refinement of C, that is D ≐ C Çát¢,B¢ñ. For every interpretation Á, if shapes are interpreted as in (2), then D^{Á} Í C^{Á}; if shapes are
interpreted as in (3), then for every image I it holds D^{Á}(I) £ C^{Á}(I).
Proof. For (2), the claim follows from the fact that D^{Á} considers an intersection of the same components as the one of C^{Á}, plus the set á(t°t¢),B¢ñ^{Á}. For (3), the claim analogously follows from the fact that D^{Á}(I) computes a minimum over a superset of the values considered for C^{Á}(I).

The above property makes our language fully compositional.
Namely, let C be a composite shape description; we can consider the meaning of
C  when used as a query  as the set of images that can be potentially retrieved
using C. At least, this will be the meaning perceived by an end user of a
system. Downward refinement ensures that the meaning of C can be obtained by
starting with one component, and then progressively adding other components in
any order. We remark that for other frameworks cited above [ Gudivada & Raghavan, 1995; ElKwae & Kabuka, 1999]
this property does not hold. We illustrate the problem in Figure 3.
Starting with shape description C, we may retrieve (among many others) the two
images I_{1}, I_{2}, for which both C^{Á}(I_{1})
and C^{Á}(I_{2}) are above a
threshold t, while another image I_{3} is not in the set because C^{Á}(I_{3})
< t. In order to be more selective, we try adding details, and we obtain the
shape description D. Using D, we may still retrieve I_{2}, and discard
I_{1}. However, I_{3} now partially matches the new details of
D. If Downward refinement holds, D^{Á}(I_{3}) £
C^{Á}(I_{3}) < t, and I_{3}
cannot ``pop up". In contrast, if Downward refinement does not hold (as in
Gudivada & Raghavan's approach) it can be D^{Á}(I_{3})
> t > C^{Á}(I_{3}) because matched
details in D raise the similarity sum weighted over all components. In this case,
the meaning of a sketch cannot be defined in terms of its components.
Figure
3: Downward refinement: the thin arrows denote nonzero similarity in approximate
recognition. The thick arrow denotes a refinement.
Downward refinement is a property linking syntax to semantics. Thanks to
the extensional semantics, it can be extended to an even more meaningful semantic
relation, namely, subsumption. We borrow this definition from Description
Logics [ Donini, Lenzerini, Nardi, &
Schaerf, 1996], and its fuzzy extensions [ Yen, 1991; Straccia, 2001].
Definition 2 [Subsumption] A description C
subsumes a description D if for every interpretation Á, D^{Á} Í C^{Á}. If (3) is used, C subsumes D if for every
interpretation Á and image I Î D, it is D^{Á}(I) £ C^{Á} (I).
Subsumption takes into account the fact that a description might contain a syntactic variant of another, without both the user and the system explicitly knowing this fact. The notion of subsumption extends downward refinement. It enables also a hierarchy of shape descriptions, in which a description D is below another C if D is subsumed by C. When C and D are used as queries, the subsumption hierarchy makes easy to detect query containment. Containment can be used to speed up retrieval: all images retrieved using D as a query can be immediately retrieved also when C is used as a query, without recomputing similarities. While query containment is important in standard databases [ Ullman, 1988], it becomes even more important in an image retrieval setting, since the recognition of specific features in an image can be computationally demanding.
Figure
4: An example of subsumption hierarchy of shapes (thick arrows), and images in
which the shapes can be recognized (thin arrows).
Figure 4 illustrates an example of
subsumption hierarchy of basic and composite shapes (thick arrows denote a
subsumption between shapes), and two images in which shapes can be recognized
(thin arrows).
Although we did not consider a background, it could be added to
our framework as a special basic component ác,t, ,background ñ
with the property that a region b satisfies the background simply if their
colors and textures match, with no check on the edge contours. Also, more than
one background could be added; in that case background regions should not
overlap, and the matching of background regions should be considered after the
regions of all the basic shapes recognized are subtracted to the background
regions.
We envisage several reasoning
services that can be carried out in a logic for image retrieval:
While services 12 are standard in an image
retrieval system, services 34 are less obvious, and we briefly discuss them
below.
The process of image retrieval is quite expensive, and systems usually
perform offline processing of data, amortizing its cost over several queries
to be answered online. As an example, all document retrieval systems for the
web^{4}, both for images and text, use
spiders to crawl the web and extract some relevant features (e.g., color
distributions and textures in images, keywords in texts), that are used to
classify documents. Then, the answering process uses such classified, extracted
features of documents  and not the original data.
Our system can adapt this setting to composite shapes, too. In our
system, a new image inserted in the database is immediately segmented and
classified in accordance with the basic shapes that compose it, and the
composite descriptions it satisfies (Service 3). Also a query undergoes
the same classification, with reference to the queries already answered
(Service 4). The more basic shapes are present, the faster will the system
answer new queries based on these shapes.
More formally, given a query (shape description) D, if there exists a
collection of descriptions D_{1},¼,D_{n}
and all images in the database were already classified with reference
to D_{1},¼,D_{n}, then it may suffice
to classify D with reference to D_{1},¼,D_{n}
to find (most of) the images satisfying D. This is the usual way in which
classification in Description Logics  which amounts to a semantic indexing 
can help query answering [
Nebel, 1990].
For example, to answer the query asking for images containing an arch, a system may classify arch and find that it subsumes threePortalsGate
(see Figure 4). Then, the system can include in
the answer all images in which ancient Roman gates can be recognized, without
recomputing whether these images contain an arch or not.
The problem of computing subsumption between descriptions is reduced to
recognition in the next section, and then an algorithm for exact recognition is
given. Then, we extend the algorithm to realistic approximate recognition,
reconsidering color and texture.
We start with a reformulation of (2), more suited for computational
purposes.
Theorem 2 [Recognition as mapping Let C=át_{1},B_{1} ñÇ¼Ç át_{n},B_{n} ñ be a composite shape
description, and let I be an image, segmented into regions {r_{1},...,r_{m}}.
Then C is recognized in I iff there exists a transformation t and an injective mapping j : {1,¼,n} ® {1,¼, m } such that for i=1,¼,n it is

Proof. From (2), C is recognized in I iff

Expanding á(t°t_{i}),B_{i} ñ^{Á}
with its definition (1) yields

and since regions in I are {r_{1},...,r_{m}} this is
equivalent to

Making explicit the disjunction over j and conjunctions over i, we can
arrange this conjunctive formula as a matrix:

(4) 
Now we note two properties in the above matrix of equalities:
We observe that these properties do not imply
that regions have all different shapes, since the equality of contours depends
on any translation, rotation, and scaling. We use equality to represent true
overlap, and not just equal shape.
Properties 12 imply that the above formula is true iff there is an
injective function mapping each component to one region it matches with. To
ease the comparison with the formulae above we use the same symbol j as a
mapping j:{1,¼,n} ®
{1,¼,m}. Hence, Formula (4)
can be rewritten into the claim:

(5) 

Hence, even if in the previous section the semantics of a composite shape was
derived from the semantics of its components, in computing whether an image
contains a composite shape one can focus on groups of regions, one group r_{j(1)},¼,r_{j(n)}
for each possible mapping j.
Observe that j injective implies m ³
n, as one would expect. The above proposition leaves open which one between t
or j must be chosen first. In fact, in what follows we show that the optimal
choice for exact recognition is to mix decisions about j and t.
When approximate recognition will be considered, however, exchanging
quantifiers is not harmless. In fact, it can change the order in which
approximations are made. We return to this issue in the next section, when we
discuss how one can devise algorithms for approximate recognition.
Subsumption in this simple logic for shape descriptions relies on the
composition of contours of basic shapes. Intuitively, to actually decide if D
is subsumed by C, we check if the sketch associated with D  seen as an image 
would be retrieved using C as a query. From a logical perspective, the
existentially quantified regions in the semantics of shape descriptions (1)
are skolemized with their prototypical contours. Formal definitions follow.
Definition 3 [Prototypical image] Let B be a
basic shape. Its prototypical image is I(B)={e(B)}. Let C=át_{1},B_{1} ñÇ¼ Çát_{n},B_{n} ñ be a composite shape description. Its prototypical image is I(C) = { t_{1}(e(B_{1})),¼, t_{n}(e(B_{n})) }.
In practice, from a composite shape description one builds its prototypical image just applying the stated transformations to its components (and color/texture fillings, if present). Recall that we envisage this prototypical image to be built directly by the user, with the help of a drawing tool, with basic shapes and colors as palette items. The system will just keep track of the transformations corresponding to the user's actions, and use them in building the (internal) shape descriptions stored with the previous syntax. The feature that makes our proposal different from other querybysketch retrieval systems, is precisely that our sketches have also a logical meaning. So, properties about description/sketches can be proved, containment between query sketches can be stated in a formal way, and algorithms for containment checking can be proved correct with reference to the semantics.
Prototypical images have some important properties. The first is that
they satisfy (in the sense of Definition 1)
the shape description they exemplify  as intuition would suggest.
Proposition 3 For
every composite shape description D, if D is satisfiable then the
interpretation áÁ,{I(D)}ñ satisfies D.
Proof. From Theorem 2, using an identical transformation t and the identity mapping for j.

A shape description D is satisfiable if there are no overlapping regions
in I(D). Since this is obvious when D is specified by a drawing tool, we just
give the following proposition for sake of completeness.
Proposition 4 A
shape description D is satisfiable iff its prototypical image I(D) contains no
overlapping regions.
We now turn to subsumption. Observe that if B_{1} and B_{2} are basic shapes, either they are equivalent (each one subsumes the other) or neither of the two subsumes the other. If we adopt for the segmented regions an invariant representation, (e.g. Fourier transforms of the contour) deciding equivalence between basic shapes, or recognizing whether a basic shape appears in an image, is just a call to an algorithm computing the similarity between shapes. This is what usual image recognizers do  allowing for some tolerance in the matching of the shapes. Therefore, our framework extends the retrieval of shapes made of a single component, for which effective systems are already available.
We now consider composite shape descriptions, and prove the main
property of prototypical images, namely, the fact that subsumption between
shape descriptions can be decided by checking if the subsumer can be recognized
in the sketch of the subsumee.
Theorem 5
A composite shape description C subsumes a
description D if and only if C is recognized in the prototypical image I(D).
Proof. Let C=át_{1},B_{1} ñÇ¼Çát_{n},B_{n} ñ, and let D = ás_{1},A_{1} ñÇ¼Çás_{m},A_{m} ñ. Recall that I(D) is defined by I(D) = { s_{1}(e(A_{1})),¼, s_{m}(e(A_{m}))}. To ease the reading, we sketch the idea of the proof in Figure 5.
Picture Omitted
Figure
5: A sketch of the Ifproof of Theorem 5
If.
Suppose C is recognized in I(D), that is, I(D) Î
C^{Á} for every interpretation (Á,D)
such that I(D) Î D. Then, from Theorem 2
there exists a transformation [^(t)] and a suitable injective function
j from {1,¼,n} into {1,¼,m}
such that

Since I(D) is the prototypical image of D, we can substitute each region
with the basic shape of D it comes from:

Now suppose that D is recognized in an image J = { s_{1},...,s_{p}},
with J Î D. We prove that also C is recognized
in J. In fact, if D is recognized in J then there exists a transformation [^(s)]
and another injective mapping q from {1,¼,m}
into {1,¼,p} selecting from J regions { s_{q(1)},¼,s_{q(m)}}
such that

Now composing q and j  that is, selecting the regions of J satisfying
those components of D which are used to recognize C  one obtains

Then, substituting equals for equals from (6),
one finally gets

which proves that C too is recognized in J, using [^(s)]°[^(t)]
as transformation of its components, and q(j(·)) as injective mapping from {1,¼,n}
into {1,¼,p}. Since J is a generic image, it
follows that D^{Á} Í C^{Á}.
Since (Á,D)
is generic too, C subsumes D.
Only if. The reverse direction is easier:
suppose C subsumes D. By definition, this amounts to D^{Á} Í
C^{Á} for every collection of images Á.
For every Á that contains I(D), then I(D) Î
D^{Á} for Proposition 3. Therefore, I(D) Î
C^{Á}, that is, C is recognized in I(D).

This property allows us to compute subsumption as recognition, so we
concentrate on complex shape recognition, using Theorem 2.
Our concern is how to decide whether there exists a transformation t
and a matching j having the properties stated in Theorem 2.
It turns out that for exact recognition, a quadratic upper bound can be
attained for the possible transformations to try.
Theorem 6 Let
C=át_{1},B_{1} ñÇ¼Ç át_{n},B_{n} ñ be a composite shape description, and let I be an image, segmented
into regions {r_{1},...,r_{m}}. Then, there are at most m(m1) exact matches between the n basic shapes and the m regions. Moreover,
each possible match can be verified by checking the matching of n pairs of
contours.
Proof. A transformation t matching exactly basic components to regions is also an exact match for their centroids. Hence we concentrate on centroids. Each correspondence between a centroid of a basic component and a centroid of a region yields two constraints for t. Now t is a rigid motion with scaling, hence it has four degrees of freedom (two degrees for translations, one for rotation, and one for uniform scaling). Hence, if an exact match t exists between the centroids of the basic components and the centroids of some of the regions, then t is completely determined by the transformation of any two centroids of the basic shapes into two centroids of the regions.
Fixing any pair of basic components B_{1},B_{2}, let p_{1},
p_{2} denote their centroids. Also, let r_{j(1)},r_{j(2)}
be the regions that correspond to B_{1},B_{2}, and let v_{j(1)},
v_{j(2)}, denote their centroids. There is only one
transformation t solving the point equations (each
one mapping a point into another)

Hence, there are only m(m1) such transformations. For the
second claim, once a t matching the centroids is found,
one checks that the edge contours of basic components and regions
coincide, i.e., that t(t_{1}(e(B_{1}))) = e(r_{j(1)}),
t(t_{2}(e(B_{2})))
= e(r_{j(2)}), and for k=3,¼,n
that t(t_{k}(e(B_{k}))
coincides with the contour of some region e(r_{j(k)}).
Recalling Formula (5) in the proof of Theorem 2,
this means that we can eliminate the outer quantifier in (5) using a computed t,
and conclude that C is recognized in I iff:


Observe that, to prune the above search, once a t
has been found as above, one can check for k=3,¼,n
that t(t_{k}(centr(B_{k})))
coincides with a centroid of some region r_{j}, before checking
contours.
Based on Theorem 6, we can devise the following
algorithm: Algorithm Recognize (C,I);
input a composite shape
description C=át_{1},B_{1}
ñÇ¼Ç át_{n},B_{n}
ñ, and
an image I, segmented into regions r_{1},...,r_{m}
output True if C is recognized in I, False otherwise
begin
(1) compute the centroids v_{1},...,v_{m} of
r_{1},...,r_{m}
(2) compute the centroids p_{1},...,p_{n} of
the components of C
(3) for i,h Î
{1,¼,m } with i < h do
compute the transformation t such that t(p_{1})=v_{i}
and t(p_{2})=v_{h};
if for every k Î
{1,¼,n}
t(t_{k}(e(B_{k})))
coincides (for some j) with a region r_{j} in I
then return True
endfor
return False
end
The correctness of Recognize (C,I) follows directly from Theorems 2
and 6. Regarding the time complexity,
step (1) requires to compute centroids of segmented regions. Several methods for
computing centroids are well known in the literature [ Jahne, Haubecker, & Geibler, 1999].
Hence, we abstract from this detail, and assume there exists a function f(N_{h},N_{v})
that bounds the complexity of computing one centroid, where N_{h},N_{v}
are the horizontal and vertical dimensions of I (number of pixels). We report
in the Appendix how we compute centroids, and concentrate on the complexity in
terms of n, m, and f(N_{h},N_{v}).
Theorem 7 Let C=át_{1},B_{1} ñÇ¼Ç át_{n},B_{n} ñ be a composite shape description, and let I be an image with N_{h}×N_{v}
pixels, segmented into regions {r_{1},...,r_{m}}. Moreover, let
f(N_{h},N_{v}) be a function bounding the complexity of
computing the centroid of one region. Then C can be recognized in I in time
O(m·f(N_{h},N_{v})+n+m^{2}·n ·N_{h} ·N_{v}).
Proof. From the assumptions, Step (1) can be performed in time O(m·f(N_{h},N_{v})). Instead, Step (2) can be accomplished by extracting the n translation vectors from the transformations t_{1},...,t_{n} of the components of C. Therefore, it requires O(n) time. Finally, the innermost check in Step (3)  checking whether a transformed basic shape and a region coincide  can be performed in O( N_{h} ·N_{v}), using a suitable marking of pixels in I with the region they belong to. Hence, we obtain the claim.

Since subsumption between two shape descriptions C and D can be reduced
to recognizing C in I(D), the same upper bound holds for checking subsumption
between composite shape descriptions, with the simplification that also Step (1)
can be accomplished without any further featurelevel image processing.
The
algorithm proposed in the previous section assumes an exact recognition. Since
the target of retrieval are real images, approximate recognition is needed. We
start by reconsidering the proof of Theorem 2,
and in particular the matrix of equalities (4).
Using the semantics for approximate recognition (3), the expanded formula for
evaluating C^{Á}(I) becomes now the following:

Now Properties 12 stated for exact recognition
can be reformulated as hypotheses about sim, as follows.
We remark that also in the approximate case
these assumptions do not imply that regions have all different shapes, since
sim is a similarity measure which is 1 only for true overlap, not just for
equal shapes with different pose. The assumptions just state that sim should be
a function ``near" to plain equality.
The above assumptions imply that we can focus on injective mappings from
{1..n} into {1..m} also for the approximate recognition, yielding the formula

The choices of t and j for the two maxima are
independent, hence we can consider groups of regions first:

(9) 
Differently from the exact recognition, the choice of an injective
mapping j does not directly lead to a transformation t,
since now t depends on how the similarity of
transformed shapes is computed, that is, the choice of t
depends on sim.
In giving a definition of sim, we reconsider the other image features
(color, texture) that were skipped in the theoretical part to ease the
presentation of semantics. This will introduce weighted sums in the similarity
measure, where weights are set by the user according to the importance of the
features in the recognition.
Let sim(r,ác,t,t,B
ñ) be a similarity measure that takes a region r
(with its color c(r) and texture t(r)) and a component ác,t,t,B
ñ into the range [0,1] of real numbers (where 1 is
perfect matching). We note that color and texture similarities do not depend on
transformations, hence their introduction does not change Assumptions 12
above. Accordingly, Formula (9) becomes

(10) 
This formula suggests that from all the groups of regions in an image
that might resemble the components, we should select the groups that present the
higher similarity. In artificially constructed examples in which all shapes in
I and C resemble each other, this may generate an exponential number of groups
to be tested. However, we can assume that in realistic images the similarity
between shapes is selective enough to yield only a very small number of
possible groups to try. We recall that in Gudivada's approach [ Gudivada, 1998] an even stricter assumption is
made, namely, each basic component in C does not appear twice, and each region
in I matches at most one component in C. Hence our approach extends Gudivada's
one, also for this aspect  besides the fact that we consider shape, scale,
rotation, color and texture of each component.
In spite of the assumptions made, finding an algorithm for computing the
``best" t in Formula (10) proved for us a difficult task.
The problem is that there is a continuous spectrum of t
to be searched, and that the best t may not be unique. We observed that
when only single points are to be matched  instead of regions and components 
our problem simplifies to Point Pattern Matching in Computational Geometry.
However, even recent results in that research area are not complete, and cannot
be directly applied to our problem. Cardoze
and Schulman (1998) solve the nearlyexact point matching with
efficient randomized methods, but without scaling. They also observe that best
match is a more difficult problem than nearlyexact match. Also Chew et al. (1997)
propose a method for best match of shapes, but they analyze only rigid motions
without scaling.
Therefore, we adopt some heuristics to evaluate the above formula. First
of all, we decompose sim(r,ác,t,t,B
ñ) as a sum of six weighted contributions.
Three contributions are independent of the pose: color, texture and
shape. The values of color and texture similarity are denoted by sim_{color}(c(r),c)
and sim_{texture}(t(r),t), respectively. Similarity of the shapes
(rotationtranslationscale invariant) is denoted by sim_{shape}(e(r),e(B)).
For each feature, and each pair (region, component) we compute a similarity
measure as explained in the Appendix. Then, we assign to all similarities of a
feature  say, color  the worst similarity in the group. This yields a
pessimistic estimate of Formula (10); however, for such estimate the
Downward Refinement property holds (see next Theorem 8).
The other three contributions depend on the pose, and try to evaluate
how the pose of each region in the selected group is similar to the pose
specified by the corresponding component in the sketch. In particular, sim_{scale}(e(r),t(e(B))
represents how similar in scale are the region and the transformed component,
while sim_{rotation}(e(r),t(e(B)) denotes how e(r) and t(e(B)
are similarly (or not) rotated with reference to the arrangement of
the other components. Finally, sim_{spatial}(e(r),t(e(B))
denotes a measure of how coincident are the centroids of the region and the
transformed component.
In summary, we get the following form for the overall similarity between
a region and a component:

where coefficients a, b,
g, d,h,
e weight the relevance each feature has in the
overall similarity computation. Obviously, we impose a+
b+ g+ d+h+
e = 1 , and all coefficients are greater or equal
to 0. The actual values given to these coefficients in the implemented system
are reported in Table 2 in Section 6.
Because of the difficulties in computing the best t,
we do not compute a maximum over all possible t's.
Instead, we evaluate whether there can be a rigid transformation with
scaling from t_{1}(e(B_{1})),¼,t_{n}(e(B_{n})) into r_{j(1)},¼,r_{j(n)},
through similarities sim_{spatial},sim_{scale}, and sim_{rotation}.
There is a transformation iff all these similarities are 1. If not, the lower
the similarities are, the less ``rigid" the transformation should be to
match components and regions. Hence, instead of Formula (10) we evaluate the following simpler
formula:

(11) 
interpreting pose similarities in a different way. We now describe in
detail how we estimate pose similarities.
Let C = ác_{1},t_{1},t_{1},B_{1} ñ Ç¼Çác_{n},t_{n},t_{n},B_{n} ñ,
and let j be an injective function from {1..n} into {1..m}, that matches
components with regions {r_{j(1)},¼,r_{j(n)}
} respectively.
For a given component  say, component 1  we compute all angles under which
the other components are seen from 1. Formally, let a_{[^i1h]} be the counterclockwiseoriented
angle with vertex in the centroid of component 1, and formed by the lines
linking this centroid with the centroids of component i and h. There are n(n1)/2
such angles.
Then, we compute the correspondent angles for region r_{j(1)},
namely, angles b_{^j(i)j(1)j(h)}
with vertex in the centroid of r_{j(1)}, formed by the lines linking
this centroid with the centroids of regions r_{j(i)} and r_{j(h)}
respectively. A pictorial representation of the angles is given in Figure 6.
Figure
6: Representation of angles used for computing spatial similarity of component
1 and region r_{j(1)}.
Then we let the difference D_{spatial}(e(r_{j(1)}),t_{1}(e(B_{1})) be the maximal
absolute difference between correspondent angles:

We compute an analogous measure for components 2,...,n, and then we
select the maximum of such differences:

(12) 
where the argument j highlights the fact that this measure depends on
the mapping j. Finally, we transform this maximal difference  for which
perfect matching yields 0  into a minimal similarity  perfect matching yields
1  with the help of the function F described in the Appendix. This
minimal similarity is then assigned to every sim_{spatial}(e(r_{j(i)}),t_{i}(e(B_{i})), for i=1,¼,n.
Intuitively, our estimate measures the difference in the arrangement of
centroids between the composite shape and the group of regions. If there exists
a transformation bringing components into regions exactly, every difference is
0, and so sim_{spatial} raises to 1 for every component. The more an
arrangement is scattered with reference to the other arrangement,
the higher its maximum difference. The reason why we use the maximum of all
differences as similarity for each pair componentregion will be clear when we
prove later that this measure obeys Downward Refinement property.
For every basic shape one can imagine a unit vector with origin in its
centroid and oriented horizontally on the right (as seen on the palette). When
the shape is used as a component  say, component 1  also this vector is
rotated according to t_{1}.
Let [h\vec] denote such a rotated
vector. For i=2,¼,n let g_{[^i1[h\vec]]} the counterclockwiseoriented
angle with vertex in the centroid of component 1, and formed by [h\vec] and the
line linking the centroid of component 1 with the centroid of component i.
For region r_{j(1)}, the analogous [u\vec] of [h\vec] can be constructed by finding the rotation phase for which crosscorrelation attains a maximum value (see Appendix). Then, for i=2,¼,n let d_{[^j(i)j(1)[u\vec]]} be the angles with vertex in the centroid of r_{j(1)}, and formed by [u\vec] and the line linking the centroid of r_{j(1)} with the centroid of r_{j(i)}. Figure 7 clarifies the angles we are computing.
Figure
7: Representation of angles used for computing rotation similarity of component
1 and region r_{j(1)}.
Then we let the difference D_{rotation}(e(r_{j(1)}),t_{1}(e(B_{1})) be the maximal
absolute difference between correspondent angles:

If there is more than one orientation of r_{j(1)} for which
crosscorrelation yields a maximum  e.g., a square has four such orientations
 then we compute the above maximal difference for all such orientations, and
take the best difference (the minimal one).
We repeat the process for components 2 to n, and we select the maximum
of such differences:

(13) 
Finally, as for spatial similarity, we transform D_{rotation}[j] into a minimal similarity with
the help of F. This minimal similarity is then
assigned to every sim_{rotation}(e(r_{j(i)}),t_{i}(e(B_{i})), for i=1,¼,n.
Observe that also these differences drop to 0 when there is a perfect
match, hence the similarity raises to 1. The more a region has to be rotated
with reference to the other regions to match a component, the higher the
rotational differences. Again, the fact that we use the worst difference to
compute all rotational similarities will be exploited in the proof of Downward
Refinement.
We concentrate again on component 1 to ease the presentation. Let m_{1} be the size of component 1, computed as the mean distance between its centroid and points on the contour. Moreover, for i=2,¼,n, let d_{1i} be the distance between the centroid of component 1 and the centroid of component i. In the image, let M_{j(1)} be the size of region r_{j(i)}, and let D_{j(1)j(i)} be the distance between centroids of regions j(1) and j(i). Figure 8 pictures the quantities we are computing.
Figure 8: Sizes and distances for
scale similarity computation of component 1 and region r_{j(1)}.
We define the difference in
scale between e(r_{j(1)}) and t_{1}(e(B_{1}) as:

We repeat the process for
components 2 to n, and we select the maximum of such differences:

(14) 
Finally, as for the other
similarities, we transform D_{scale}[j] into a minimal similarity with the help of F. This minimal similarity is then assigned to every sim_{scale}(e(r_{j(i)}),t_{i}(e(B_{i})),
for i=1,¼,n.
Using the same worst
difference in evaluating pose similarities of all components may appear a
somewhat drastic choice. However, we were guided in this choice by the goal of
preserving the Downward Refinement property, even if we had to abandon the
exact recognition of the previous section.
Theorem 8 Let
C be a composite shape description, and let D be a refinement of C, that is, D ≐
C Ç ác¢,t¢,t¢,B¢ñ. For every image I, segmented into
regions r_{1},...,r_{m}, if C^{Á}(I) and D^{Á}(I) are computed as in (11)
using similarities defined above, then it holds D^{Á}(I) £ C^{Á}(I).
Proof. Every injective function j used to map components of C into I can be extended to a function j¢ by letting j¢(n+1) Î {1,¼,m } be a suitable region index not in the range of j. Since D^{Á}(I) is computed over such extended mappings, it is sufficient to show that values computed in Formula (11) do not increase with reference to the values computed for C.
Let j_{1} be the
mapping for which the maximum value C^{Á}(I) is reached. Every extension j_{1}¢ of j_{1} leads to a minimum value min_{i=1}^{n+1}
in Formula (11) which is lower than C^{Á}(I). In fact, all pose differences (12), (13), (14), are computed as maximums over a strictly
greater set of values, hence the pose similarities have either the same value,
or a lower one. Regarding color, texture, and shape similarities, adding
another component can only worsen the values for components of C, since we
assign to all components the worst similarity in the group.
Now consider another injective mapping j_{2} that yields a nonmaximum value v_{2} < C^{Á}(I) in Formula (11). Using the above argument about pose differences (12), (13), (14), every extension j_{2}¢ leads to a minimum value v_{2}¢ £ v_{2}. Since v_{2} < C^{Á}(I), also every extension of every mapping j different from j_{1} yields a value which is less than C^{Á}(I). This completes the proof.

In order to substantiate our ideas we have
developed a prototype system, written in C++. The system is a clientserver
application working in a MSWindows environment.
The client side avails of a
graphical user interface that allows one to carry out all the operations
necessary to query the knowledge base, including a canvas for query by sketch
composition using basic shapes and a module for query by example using new or
existing images as queries. The client also allows a user to insert new shape
descriptions and images in the knowledge base. The client has the logical
structure shown in Figure 9. It is made up of three main modules: sketch, communication and
configuration.
Figure 9: Architecture of the
prototype system.
The communication module
manages the communication with the server side, using a simple applicationlevel
protocol. The configuration module allows one to modify the parameters relative
to the preview of images and shapes transferred from the server and placed in a
cache managed with a FCFS policy for efficient display. The sketch module allows
a user to trace basic shapes as palette items, and properly insert and modify
them by varying the scale and rotation factor. The available shapes may be
basic ones such as ellipse, circle, rectangle, polygons or obtained by
composing the basic shapes or complex shapes defined during previous sessions
of the application and inserted in the knowledge base, but also shapes
extracted from segmented images.
Figure 10: The process of
reclassification of images when a new description is inserted: a) before
insertion of description (No. 9); b) after insertion.
The system kegif track of
the transformations corresponding to the user's actions, and uses them in building
the (internal) shape descriptions stored with the previously described syntax.
The color and texture of the drawn shapes can be set according to the user
requirements, as the client interface provides a color palette and the
possibility to open images in JPEG format with texture content. The user can
also load images from the local disk and transmit them to the server to
populate the knowledge base. Finally, the user can define new objects endowing
them with a textual description and insert them into the knowledge base.
Figure 11: A query and the retrieved
set of images.
The server side, which is also shown in Figure 9, is composed by concurrent threads that manage the serverside graphical interface, the connections and communications with the client applications and carry out the processing required by the client side. Obviously, the server also carries out all tasks related to the insertion of images in the knowledge base, including segmentation, feature extraction and region indexing, and allows one to properly set the various parameters involved. To this end, the server has three main subcomponents:
The feature extractor
segments and processes images to extract relevant features from each detected
region, which characterize the images in the knowledge base. Image segmentation
is carried out with an algorithm that starts with the extraction of relevant
edges and then carries out a region growing procedure that basically merges
smaller regions into larger ones according to their similarity in terms of
color and texture. Detected regions obviously have to comply with some minimal
heuristics. Each region has associated a description of the relevant features.
The classifier manages a
graph that is used to represent and hierarchically organizes shape
descriptions: basic shapes, and more complex ones obtained by combining such
elementary shapes and/or by applying transformations (rotation, scaling and
translation). The basic shapes have no parents, so they are at the top of the
hierarchy. Images, when inserted in the knowledge base after the segmentation
process, are linked to the descriptions in the structure depending on the most
specific descriptions that they are able to satisfy.
The classifier module is
invoked when a new description D has to be inserted in the system or a new
query is posed. The classifier carries out a search process in the hierarchy to
find the exact position where the new description D (a simple or a complex one)
has to be inserted: the position is determined considering the descriptions
that the new description is subsumed by. Once the position has been found, the
image reclassifier compares D with the images available in the database to
determine those that satisfy it; all the images that verify the recognition
algorithm are tied to D. This stage only considers the images that are tied to
descriptions that are direct ancestors of D, as outlined in Figure 10.
Figure 12: Downward refinement
(contd.): A more detailed query, picturing a car, and the retrieved set of
images.
As usual in Description
Logics, also the query process consists of a description insertion, as both a
query Q and a new description D are treated as prototypical images: a query Q
to the system is considered a new description D and added to the hierarchical
data structure; all images that are connected either to Q or to descriptions
below the query in the hierarchical structure are returned as retrieved images.
The database management
module simply kegif track of images and/or pointers to images.
Using the system is a
straightforward task. After logon a user can draw a sketch on the canvas
combining available basic shapes, and enrich the query with color and texture
content. After that the query can be posed to the server to obtain images
ranked according to their similarity. Figure 11 shows a query by sketch with two circles and
the retrieved set. The system correctly retrieves pictures of cars in which the
two circles are recognized in the same relative positions of the sketch and
represent the wheels, but also a snow man with black buttons.
Figure 13: A Subsumption example: increasing
the number of objects in the query leads to a correct reduction in the
retrieved set.
The introduction of more
details restricts the retrieved set: adding a chassis to the previous sketch
makes the query more precise, as well as the retrieval results, as it is shown
in Figure 12. This example points out how we expect a user will use the system.
He/she will start with a generic query with a few objects. If the number of
images in the retrieved set is still too large, he/she will increase the number
of details obtaining a downward refinement.
Notice that the presence of
regions/objects not included in the query is obviously accepted but not the
lack of a region that was explicitly introduced in the query. The idea
underlying this approach is that there is an enormous amount of available
images, and at the current stage of research and technology no system can
always ensure a complete recognition; yet we believe that the focus should be
on reducing false positives, accepting without much concern a higher ratio of
false negatives. This basically means increasing precision, even at the cost of
a possibly lower recall. In other words we believe it is preferable for a user
looking for an image containing a yellow car, e.g., using the
sketch in Figure 12, that he/she receives as result of the query a limited subset of images
containing almost for sure a yellow car, than a large amount of images
containing cars, but also several images with no cars at all.
Subsumption is another
distinguishing feature of our system. Figure 13 shows queries composed of basic shapes that
have been obtained by segmentation of an image picturing aircrafts, i.e., the
aircraft is now a basic shape for the system. Here, to better emphasize the
example, only shape and position contribute to the similarity value. The
process of subsumption is clearly highlighted: a query with just a single
aircraft retrieves images with one aircraft, but also with more than one
aircraft. Adding other aircrafts in the graphical query correctly reduces the
retrieved set. The example also points out that the system is able to correctly
deal with the presence of more than one instance of an object in images, which
is not possible in the approaches by Gudivada and Raghavan (1995) and Gudivada (1998). On the negative side it has to be
noticed that the system did not recognize the presence of a third aircraft
(indeed a strange one, the B2Spirit) in the second image of Figure 13b), which was not segmented at all
and considered part of the background.
The ability of the system
to retrieve complex objects also in images with several other different
objects, that is with no ``main shapes", can be anyway seen in
Figure 14. Here a
real image is directly submitted as query. Notice that in this case the system
has to carry out the segmentation process on the fly, and detect the composing
shapes.
Figure 14: A query by example and retrieved
images.
Figure 15: A sample of the images
used in the experiments.
In order to assess the performance
of the proposed approach and of the system implementing it, we have carried out
an extensive set of experiments on a test dataset of images. It is well known
that evaluating performances of an image retrieval system is difficult because
of lack of ground truth measures. To ease the possibility of a comparison, we
adopted the approach first proposed by Gudivada and Raghavan (1995). The experimental framework is
hence largely based on the one proposed there, which relies on a comparison of
the system performances versus the judgement of human experts.
It should be noticed that
in that work test images were iconic images, which were classified only in
terms of spatial relationships between icons; in our experiments images are
real and classification has been carried out on all image features, including
color, texture, shape, scale, orientation and spatial relationships.
The test data set consists
of a collection of 93 images; a sample of them is shown in Figure 15, while the complete set is
available at URL:
http://wwwictserv.poliba.it/disciascio/jair_images.htm.
Images have been acquired
using a digital camera, combining 18 objects, either simple objects (i.e., a
single shape) or composite ones, of variable size and color. All images had
size 1080 × 720 pixels, 24 bits/pixel. It should be noticed that actually there
were more than 18 different objects, but we considered very similar variants of
an object, e.g., two pens with a different color, as a single test
object.
We selected from the test
data set 31 images to be used as queries. The query set formed two logical
groupings.
The first one (namely
queries 1 through 15 and queries 27, 30 and 31) had as primary objective
testing the performance of the system using as query single objects composed by
various shapes. That is, assessing the ability of the system to detect and
retrieve images containing the same object, or objects similar to the query.
The query images in the
second group (remaining images in the test data set) pictured two or more
objects and they were chosen to assess the ability of the system to detect and
retrieve images according to spatial relationships existing between the objects
in the query.
Obviously the difference
between queries containing single objects composed by several shapes, and
queries containing two or more objects, is just a cognitive one: for our system
all queries are composite shapes. However, we observed that performances changed
for the two groupings.
We then separately asked
five volunteers to classify in decreasing order, according to their judgment,
the 93 images based on their similarity to each image of the selected query
set. The volunteers had never used the system and they were only briefly
instructed that rank orderings had to be based on the degree of conformance of
the database images with the query images. They were allowed to group images
when considered equivalent, and for each query, to discard images that were
judged wholly dissimilar from the query.
Having obtained five
classifications, which were not univocal, we created the final ranking merging
the previous similarity rankings according to a minimum ranking criterion. The
final ranking of each image with respect to a query was determined as the
minimum one among the five available.
As an example consider the
classification of Query nr.1, which is shown in Table 1. Notice that images grouped
together in the same cell have been given the same relevance.
ranking 


1st 
2nd 
3rd 
4th 
5th 
1 
1 
44, 88 
2, 3, 68, 80 
26 
24 
2 
1 
44, 88 
3, 68, 80 
2, 26 

3 
1 
44, 88 
3, 68, 80 
2, 26 

4 
1 
44, 88 
2, 3, 68, 80 
26 
24 
5 
1 
44, 88 
2, 3, 68, 80 
24 26 

final 
1 
44, 88 
3, 68, 80 
2, 26 

Table 1: Users rankings for query nr.1
Here
Image 2 was ranked in third position by users 1,4, and 5, but as users 2 and
3 ranked it in fourth position, it was finally ranked in position four. Notice
that for image 24 the same criterion leads to its withdrawal from ranked
images. This approach limits the weight that images badly classified by single
users have on the final ranking.
Then we submitted the same
set of 31 queries to the system, whose knowledge base was loaded only with the
93 images of the test set.
The behavior of the system
obviously depends on the configuration parameters, which determine the
relevance of the various features involved in the similarity computation. The
configuration parameters fed to the system were experimentally determined on a
test bed of approximately 500 images before starting the test phase. They are
shown in Table 2. The parameters reported here are described in the Appendix. Notice
that, dealing with welldefined objects, we gave an higher relevance to shape
and spatial features and a reduced relevance to scale, rotation, color and
texture.
Value 

Fourier descriptors threshold 
0.98 
Circular symmetry threshold 
0.99 
Spatial similarity threshold 
0.30 
Symmetry maxima threshold 
0.10 
Spatial similarity weight a 
0.30 
Spatial similarity sensitivity fx 
90.0 
spatial similarity sensitivity fy 
0.40 
shape similarity weight b 
0.30 
shape similarity sensitivity fx 
0.005 
shape similarity sensitivity fy 
0.20 
color similarity weight g 
0.11 
color similarity sensitivity fx 
110.0 
color similarity sensitivity fy 
0.40 
rotation similarity weight d 
0.11 
rotation similarity sensitivity fx 
90.0 
rotation similarity sensitivity fy 
0.40 
texture similarity weight e 
0.07 
texture similarity sensitivity fx 
110.0 
texture similarity sensitivity fy 
0.40 
scale similarity weight h 
0.11 
scale similarity sensitivity fx 
0.50 
scale similarity sensitivity fy 
0.40 
global similarity threshold 
0.70 
Table 2: Configuration parameters, grouped by
feature type.
The resulting classification gave us what was called a systemprovided
ranking. We then adopted the R_{norm} as quality measure of the
retrieval effectiveness. R_{norm} has been first introduced in the
LIVEProject [ Bollmann, Jochum, Reiner, Weissmann, & Zuse, 1985] for
the evaluation of textual information retrieval systems and it has been used in
the experiments of the above referenced paper by Gudivada and Raghavan. To make
the paper selfcontained we recall here how R_{norm} is defined.
Let G be a finite set of
images with a userdefined preference relation ³ that is
complete and transitive. Let D^{usr} be the rank ordering of G induced by the user
preference relation. Also, let D^{sys} be a systemprovided ranking. The formulation
of R_{norm} is:

where S^{+} is the number
of image pairs where a better image is ranked by the system ahead of a worse
one; S^{} is the number of pairs where a
worse image is ranked ahead of a better one and S^{+}_{max} is
the maximum possible number of S^{+}. It should be noticed that the
calculation of S^{+}, S^{}, and S^{max} is based on
the ranking of image pairs in D^{sys} relative to the ranking of corresponding image
pairs in D^{usr}.
R_{norm} values are
in the range [0,1]; a value of 1 corresponds to a systemprovided ordering of
the database images that is either identical to the one provided by the human
experts or has a higher degree of resolution, lower values correspond to a
proportional disagreement between the two.
Table 3 shows results for each query and
the final average R_{norm}=0.92. Taking a closer look at results, for
the first group of queries (single compound objects) the average value was R_{norm}=0.90,
and R_{norm}=0.94 for the second grouping (various compound objects).
(The complete set of result for users' ranking and system ranking is available
in the online appendix).
Image nr. 
R_{norm} 

f1 
1 
0.92 
f2 
2 
0.92 
f3 
3 
0.93 
f4 
4 
0.95 
f5 
5 
0.99 
f6 
6 
0.94 
f7 
7 
0.93 
f8 
10 
0.93 
f9 
11 
0.95 
f10 
12 
0.74 
f11 
13 
0.60 
f12 
14 
0.84 
f13 
15 
0.83 
f14 
18 
0.99 
f15 
20 
0.91 
16 
25 
0.89 
17 
26 
0.80 
18 
27 
1.00 
19 
28 
0.74 
20 
31 
1.00 
21 
33 
1.00 
22 
34 
0.99 
23 
35 
0.91 
24 
36 
0.89 
25 
37 
1.00 
26 
39 
0.99 
f27 
41 
0.93 
28 
42 
0.98 
29 
50 
1.00 
f30 
78 
0.88 
f31 
79 
1.00 
Average R_{norm} 

0.92 
Table 3: R_{norm} values. (f indicates singleobject queries)
As
a comparison, the average R_{norm} resulted 0.98 in the system
presented by Gudivada and Raghavan (1995), where 24 iconic images were used
both as queries and database images, and similarity was computed only on
spatial relationships between icons. We remark here that our system works on
real images and computes similarity on several image features, and we believe
that results prove the ability of the system to catch to a good extent the
users information need, and make refined distinctions between images when
searching for composite shapes. Furthermore, our algorithm is able to correctly
deal with the presence of more than one instance of an object in images, which
is not possible in other approaches [ Gudivada, 1998]. It is
also noteworthy that, though the parameters setting has been the object of
several experiments, it cannot be considered optimal yet, and we believe that
there is room for further improvement in the system performance, as it is also
pointed out in the following paragraph.
Obviously the system can
fail when segmentation does not provide accurate enough results. Figure 16 shows results for Query 11, which
was the one with the worst R_{norm}. Here the system not only did not
retrieve all images users had considered relevant, but more important wrongly
confused the sugardrop with a wristwatch, which resulted in a false positive.
As a matter of fact in various images the sweetdrops resulted not properly
segmented. Nevertheless, highly relevant images were successfully retrieved and
the wrongly retrieved one was slightly above the selection threshold.
Another observation we made
was that human users, when comparing a query with a single object, were much
more driven by the color than any other feature, including the spatial
positioning. This appeared in various queries and is again clearly visible
using as example results for Query 11. Here users selected in the highest
relevance class only images with the same color sugardrop, and gave a lower
ranking to images (with sugardrops) with closer spatial relationships but
different colors. This observation may be significant in the related field of
object recognition.
A final comment. With
reference to the system behavior in terms of retrieval time, we did not carry
out a systematic testing, as it depends on several variables: number of images
in the database, number of objects in the query, but more important depth in
the hierarchy  as the search time decreases as more basic shapes are
available. Limiting our analysis to the database loaded with the 93 test
images, the system required on average 12 secs to answer a query, on a machine
with Celeron 400 MHz CPU and 128 MB RAM running both the client and the server.
Figure 16: Query results for query
11, which had the lowest R_{norm}=0.60.
We proposed a Knowledge Representation approach
to Image Retrieval. We started from the observation that current sketchbased
image retrieval systems lack of a compositional query language  that is, they
are not able to handle queries made by several shapes, where the position,
orientation and size of the shapes relative to each other is meaningful.
To recover this, we
proposed a language to describe composite shapes, and gave an extensional
semantics to queries, in terms of sets of retrieved images. To cope with a
realistic setting from the beginning, we also generalized the semantics to
fuzzy membership of an image to a description. The composition of shapes is
made possible by the explicit use in our language of geometric transformations
(translationrotationscale), which we borrow form hierarchical object modeling
in Computer Graphics. We believe that this is a distinguishing feature of our
approach, that significantly extends standard invariant recognition of single
shapes in image retrieval. The extensional semantics allows us to properly
define subsumption (i.e., containment) between queries.
Borrowing also from
Structured Knowledge Representation, and in particular from Description Logics,
we stored shape descriptions in a subsumption hierarchy. The hierarchy provides
a semantic index to the images in a database. The logical semantics allowed us
to define other reasoning services: the recognition of a shape arrangement in
an image, the classification of an image with reference to a hierarchy of
descriptions, and subsumption between descriptions. These tasks are aside, but
can speed up, the main one, which is Image Retrieval.
We proved that subsumption
in our simple logic can be reduced to recognition, and gave a polynomialtime
algorithm to perform exact recognition. Then, for a realistic application of
our setting we extended the algorithm to approximate recognition, weighting
shape features (orientation, size, position), color and texture.
Using our logical approach
as a formal specification, we built a prototype system using stateoftheart
technology, and set up experiments both to assess the efficacy of our proposal,
and to fine tune all parameters and weights that show up in approximate
retrieval. The results of our experiments, although not exhaustive, show that
our approach can catch to a good extent the users information need and make
refined distinctions between images when searching for composite shapes.
We believe that this
proposal opens at least three directions for future research. First, the
language for describing composite shapes could be enriched either with other
logicoriented connectives  e.g., alternative components
corresponding to an OR in compositions  or to sequences of shape arrangements,
to cope with objects with internal movements in video sequence retrieval.
Second, techniques from Computational Geometry could be used to optimize the
algorithms for approximate retrieval, while a study in the complexity of the
recognition problem for composite shapes might prove the theoretical optimality
of the algorithms. Finally, largescale experiments might prove useful in
understanding the relative importance attributed by end users to the various
features of a composite shape.
We wish to
thank our former students G. Gallo, M. Benedetti and L. Allegretti for their
useful comments and implementations, Marco Aiello for comments on an earlier
draft, Dino Guaragnella for discussions on Fourier transforms, and an anonymous
referee for constructive criticism that helped us improving the paper.
This research has been
supported by the European Union, POP Regione Puglia sottomisura 7.4.1 (``SFIDA
3"), by the Italian Ministry of Education, University and Research (MIUR,
exMURST) projects CLUSTER22 subcluster ``Monitoraggio ambiente e
territorio", workpackage: ``Sistema informativo per il collocamento dei
prodotti ortofrutticoli pugliesi" and by Italian National Council for
Research (CNR), projects LAICO, DeMAnD, and ``Metodi di Ragionamento Automatico
nella modellazione ed analisi di dominio".
In this appendix we briefly
revise the methods we used for the extraction of image features. We also
describe the smoothing function F and the way we compute similarity
for the image features that were introduced in Section 4.2.
In order to deal with
objects in an image, segmentation is required to obtain a partition of the
image. Several segmentation algorithms have been proposed in the literature;
our approach does not depend on the particular segmentation algorithm adopted.
It is anyway obvious that the better the segmentation, the better our system
will work. In our system we used a simple algorithm that merges edge detection
and region growing.
Illustration of this
technique is beyond the scope of this paper; we limit here to the description
of image features computation, which assume a successful segmentation. To make
the description selfcontained we start defining a generic color image as { I
(x,y)  1 £ x £ N_{h}
, 1 £ y £ N_{v}}, where N_{h},
N_{v} are the horizontal and vertical dimensions, respectively, and I
(x,y) is a threecomponents tuple (R,G,B). We assume that the image I has been
partitioned in m regions (r_{i}), i=1,¼,m satisfying the
following properties:
We characterize each region
r_{i} with the following attributes: shape, position, size,
orientation, color and texture.
Shape. Given a connected region a point
moving along its boundary generates a complex function defined as:
z(t)=x(t)+jy(t), t=1,¼, N_{b}, with N_{b}
the number of boundary sample points. Following the approach proposed by Rui, She, &
Huang (1996) we define the Discrete Fourier Transform (DFT)
of z(t) as:

with k=1, ¼, N_{b}.
In order to address the
spatial discretization problem we compute the Fast Fourier Transform(FFT) of
the boundary z(t); use the first (2N_{c}+1) FFT coefficients to form a
dense, nonuniform set of points of the boundary as:

with t=1,¼, N_{dense}. We then interpolate these samples to obtain
uniformly spaced samples z_{unif}(t), t=0,¼, N_{unif}. We compute again the FFT of z_{unif}(t)
obtaining Fourier coefficients Z_{unif}(k), k = N_{c},¼, N_{c} . The shapefeature of
a region is hence characterized by a vector of 2N_{c}+1 complex
coefficients.
Position and Size. Position is determined as the
region centroid computed via moment invariants [ Pratt, 1991]. Size is computed as the mean
distance between region centroid and points on the contour.
Orientation. In order to quantify the
orientation of each region r_{i} we use the same Fourier
representation, which stores the orientation information in the phase values.
We obviously deal also with special cases when the shape of a region has more
than one symmetry, e.g., a rectangle or a circle. Rotational
similarity between a reference shape B and a given region r_{i} can
then be obtained finding maximum values via crosscorrelation:

Color. Color information of each region r_{i}
is stored, after quantization in a 112 values color space, as the mean RGB
value within the region:

Texture. We extract texture information for
each region r_{i} with a method based on the work by Pok and Liu
(1999). Following this approach, we extract texture features convolving the
original grey level image I(x,y) with a bank of Gabor filters, having the
following impulse response:

where (U,V) represents the
filter location in the frequencydomain, l is the central frequency, s is the scale factor, and q the orientation, defined as:

The processing allows to extract
a 24components feature vector, which characterizes each textured region.
Smoothing function F. In all
similarity measures, we use the function F(x,fx,fy). The role of this function
is to change a distance x (in which 0 corresponds to perfect matching) to a
similarity measure (in which the value 1 corresponds to perfect matching), and
to ``smooth" the changes of the quantity x, depending on two parameters
fx,fy.

where fx > 0 and 0 < fy < 1.
The input data to the approximate
recognition algorithm are a shape description D, containing n components ác_{k},t_{k},t_{k},B_{k} ñ and an image
I segmented into m regions r_{1},...,r_{m}. The algorithm
provides a measure for the approximate recognition of D in I.
The first step of the
algorithm in Section 4.2 considers all the m regions the image is
segmented into and all the n components in the shape description D and finds 
if any  all the groups of n regions r_{j(k)} satisfying the higher
shape similarity with the shape components of D. To this purpose we compute
shape similarity, based on the Fourier representation previously introduced, as
vector of complex coefficients. Such measure denoted with sim_{ss} is
invariant with respect to rotation, scale and translation and is computed as
the cosine distance between the two vectors. The similarity gives a measure in
the range [0,1] assuming the higher similarity sim_{ss}=1 for perfect
matching.
Given the vectors X and Y
of complex coefficients describing respectively the shape of a region r_{i}
and the shape of a component B_{k}, X=(x_{1},¼,x_{2Nc}) and Y=(y_{1},¼,y_{2Nc})

Shape Similarity. The quantity sim_{shape} measures
the similarity between shapes in the composite shape description and the
regions in the segmented image.

Color Similarity. The quantity sim_{color}
measures the similarity in terms of color appearance between the regions and
the corresponding shapes in the composite shape description. In the following
formula, D_{color}(k).R denotes the difference in the red color
component between the kth component of D and the region r_{j(k)}, and
similarly for the green and the blue color components.

Then the function F takes the maximum of the differences to obtain a similarity:

Texture Similarity. Finally, sim_{texture}
measures the similarity between the texture features in the components of D and
in the corresponding regions.
D_{texture}(k) denotes the sum of differences in the
texture components between the kth component of D and the region r_{j(k)}
and dividing by the standard deviation of the elements.

Aiello, M. 2001. Computing spatial similarity by games In Esposito, F., Proceedings of the Eighth Conference of the Italian Association for Artificial Intelligence (AI*IA'99), 2175 in Lecture Notes in Artificial Intelligence, 99110. SpringerVerlag.
[ Ardizzone, Chella, Gaglio 1997]
Ardizzone, E., Chella, A.,
Gaglio, S. 1997. Hybrid
computation and reasoning for artificial vision In Cantoni, V., Levialdi,
S., Roberto, V., Artificial Vision, 193221. Academic Press.
Baader, F. Hanschke, P. 1991. A schema for integrating concrete domains into
concept languages In Proceedings of the Twelfth International Joint
Conference on Artificial Intelligence (IJCAI'91), 452457, Sydney.
Bach, R., Fuller, C., Gupta, A., Hampapur, A.,
Horowitz, B., Humphrey, R., Jain, R., Shu, C. 1996. The Virage image search
engine: an open framework for image management In Storage and Retrieval
for Image and Video Databases, 2670, 7687. SPIE.
Bertino, E. Catania, B. 1998. A
constraintbased approach to shape management in multimedia databases
MultiMedia Systems, 6, 216.
Bollmann, P., Jochum, F., Reiner, U., Weissmann, V., Zuse, H. 1985. The LIVEProjectRetrieval
experiments based on evaluation viewpoints In Proceedings of the 8th
Annual International ACM SIGIR Conference on Research and Developement in
Information Retrieval (SIGIR '85), 213214. ACM, New York.
Brooks, R. 1981. Symbolic reasoning among 3D
models and 2D images Artificial Intelligence, 17, 285348.
[ Calvanese, Lenzerini, Nardi 1998]
Calvanese, D., Lenzerini, M.,
Nardi, D. 1998. Description
logics for conceptual data modeling In Chomicki, J. Saake, G.,
Logics for Databases and Information Systems, 229264. Kluwer Academic
Publisher.
Cardoze, D. Schulman, L. 1998. Pattern matching for spatial point sets
In Proceedings of the Thirtyninth Annual Symposium on the Foundations of
Computer Science (FOCS'98), 156165, Palo Alto, CA.
Carson, C., Thomas, M., Belongie, S., Hellerstein, J. M., Malik, J. 1999. Blobworld: A system for regionbased image indexing and retrieval In Huijsmans, D. Smeulders, A., Lecture Notes in Computer Science, 1614, 509516. SpringerVerlag.
[ Celentano, Di Sciascio 1998]
Celentano,
A. Di Sciascio, E. 1998. Features integration and relevance feedback analysis in image similarity
evaluation Journal of Electronic Imaging, 7 (2), 308317.
Chandra, A. Harel, D. 1980. Computable queries for relational
databases Journal of Computer and System Sciences, 21, 156178.
Chang, S., Shi, Q., Yan, C. 1983. Iconic
indexing by 2D strings IEEE Transactions on Pattern Analysis and Machine
Intelligence, 9 (3), 413428.
Chew, L., Goodrich, M., Huttenlocher, D., Kedem, K., Kleinberg, J.,
Kravets, D. 1997. Geometric
pattern matching under euclidean motion Computational Geometry, 7,
113124.
Cox, I., Miller, M., Minka, T.,
Papathomas, T. 2000. The bayesian image retrieval system, PicHunter
IEEE Transactions on Image Processing, 9 (1), 2037.
[ Di Sciascio, Donini, Mongiello 2000]
Di Sciascio, E., Donini, F. M., Mongiello, M. 2000. A Description logic for image retrieval In Lamma, E. Mello, P., AI*IA 99: Advances in Artificial Intelligence, 1792 in Lecture Notes in Artificial Intelligence, 1324. SpringerVerlag.
[ Di Sciascio, Mongiello 1999]
Di Sciascio,
E. Mongiello, M. 1999. Query by sketch and relevance feedback for contentbased image retrieval
over the web Journal of Visual Languages and Computing, 10 (6), 565584.
Donini, F., Lenzerini, M., Nardi,
D., Schaerf, A. 1996. Reasoning
in description logics In Brewka, G., Foundations of Knowledge
Representation, 191236. CSLIPublications.
Edelmann, S. 1999. Representation and
Recognition in Vision. The MIT Press.
ElKwae, E. Kabuka, M. 1999. Contentbased retrieval by spatial similarity
in image databases ACM Transactions on Information Systems, 17, 174198.
Flickner, M., Sawhney, H., Niblak, W., Ashley,
J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petkovic, D., Steele,
D., Yanker, P. 1995. Query by image and video content: The QBIC
system IEEE Computer, 28 (9), 2331.
[ Foley, van Dam, Feiner, Hughes 1996]
Foley, J., van Dam, A., Feiner, S., Hughes, J. 1996. Computer
Graphics. Addison
Wesley Publ. Co., Reading, Massachussetts.
Fuhr, N., Gövert, N., Rölleke, T. 1998.
DOLORES: A system for logicbased retrieval of multimedia objects In
Proceedings of the 21st Annual International ACM SIGIR Conference on Research
and Developement in Information Retrieval (SIGIR '98), 257265,
Melbourne, Australia.
Gevers, T. Smeulders, A. 2000.
Pictoseek: Combining color and shape invariant features for image
retrieval IEEE Transactions on Image Processing, 9 (1), 102119.
Gudivada, V. 1998. qRstring: A geometrybased representation for efficient and effective
retrieval of images by spatial similarity IEEE Transactions on Knowledge
and Data Engineering, 10 (3), 504512.
Gudivada, V. Raghavan,
J. 1995. Design and evaluation
of algorithms for image retrieval by spatial similarity ACM Transactions
on Information Systems, 13 (2), 115144.
[ Haarslev, Lutz, Möeller 1998]
Haarslev, V., Lutz, C., Möeller, R. 1998.
Foundations of spatioterminological reasoning with description logics In
Proceedings of the Sixth International Conference on Principles of Knowledge
Representation and Reasoning (KR'98), 112123.
Hacid, M.S. Rigotti, C. 1999. Representing and
reasoning on conceptual queries over image databases In Proceedings of
the Twelfth International Symposium on Methodologies for Intelligent Systems
(ISMIS'99), 1609 in Lecture Notes in Artificial Intelligence,
340348, Warsaw, Poland. SpringerVerlag.
Hartman, J. Wernecke, J. 1996. The VRML 2.0 Handbook. AddisonWesley.
Hirata, K. Kato, T. 1992. Query by
visual example In Pirotte, A., Delobel, C., Gottlob, G., Advances
in Database Technology  Proc. 3rd Int. Conf. Extending Database Technology,
EDBT, 580 of Lecture Notes in Computer Science, 5671. SpringerVerlag.
[ Jacobs, Finkelstein, Salesin 1995]
Jacobs, C., Finkelstein, A., Salesin, D. 1995. Fast multiresolution image
querying In Proceedings of the 22nd Annual Conference on Computer
Graphics and Interactive Techniques (SIGGRAPH '95), 277286.
[ Jahne, Haubecker, Geibler 1999]
Jahne, B., Haubecker, H., Geibler, P. 1999. Handbook of Computer Vision and Applications.
Academic Press.
Ma, W. Manjunath, B. 1997. NETRA: A
toolbox for navigating large image database In Proceedings of the IEEE
International Conference on Image Processing (ICIP '97), 1,
568571, Santa Barbara.
Marr, D. 1982. Vision. W.H. Freeman and Co.,
Oxford.
[ Meghini, Sebastiani, Straccia 2001]
Meghini, C., Sebastiani, F.,
Straccia, U. 2001. A
model of multimedia information retrieval Journal of the ACM, 48 (5),
909970.
[ Moeller, Neumann, Wessel 1999]
Moeller, R., Neumann, B., Wessel, M. 1999. Towards computer vision with description
logics: some recent progress In Proceedings of the IEEE Integration of
Speech and Image Understanding, 101115.
Nebel, B. 1990. Reasoning and Revision in
Hybrid Representation Systems. 422 in Lecture Notes in Artificial
Intelligence. SpringerVerlag.
Niblak, W., Barder, R., Equitz, W., Flickner,
M., Glasman, E., Petkovic, D., Yanker, P., Faloustos, C. 1993. The QBIC
project: Querying images by content using color, texture, and shape In
Storage and Retrieval for Still Image and Video Databases, 1980,
173182. SPIE.
Paquet, E. Rioux, M. 1998. A
contentbased search engine for VRML databases In Proceedings of IEEE
International Conference on Computer Vision and Pattern Recognition (CVPR'98),
541546, Santa Barbara, CA.
Picard, R. Kabir, T. 1993. Finding
similar patterns in large image databases In Proceedings of the IEEE
International Conference on Acoustics Speech and Signal Processing (ICASSP
'93), 161164, Minneapolis, MN.
Pirri, F. Finzi, A.
1999. An approach to
perception in theory of actions: part 1 In Linkoping Electronic Articles
in Computer and Information Science, 41. Linkoping University Electronic
Press.
Pok, G. Liu, J. 1999. Texture
classification by a twolevel hybrid scheme In Storage and Retrieval for
Image and Video Databases VII, 3656, 614622. SPIE.
Pratt, W. 1991. Digital Image Processing. J.
Wiley & Sons Inc., Englewood Cliffs, NJ.
Reiter, R. Mackworth, A. 1989. A
logical framework for depiction and image interpretation Artificial
Intelligence, 41 (2), 125155.
Reiter, R. 1980. Equality and domain closure in
firstorder databases Journal of the ACM, 27 (2), 235249.
Rui, Y., Huang, T., Mehrotra, S. 1997. Contentbased image retrieval with relevance
feedback in MARS In Proceedings of the IEEE International Conference on
Image Processing (ICIP '97), 815818.
Rui, Y., She, A., Huang, T. 1996.
Modified Fourier descriptors for shape representation  a practical
approach In Proceedings of 1st Workshop on Image Databases and Multimedia
Search, Amsterdam.
Sanfeliu, A. Fu, K.
1983. A distance measure
between attributed relational graphs for pattern recognition IEEE
Transactions on Systems, Man, and Cybernetics, 13 (3), 353362.
Smith, J. Chang, S. 1996.
VisualSEEK: a fully automated contentbased image query system In
Proceedings of the fourth ACM International Conference on Multimedia
(Multimedia'96), 8798.
Straccia, U. 2001. Reasoning within fuzzy
description logics Journal of Artificial Intelligence Research, 14,
137166.
[ Tagare, Vos, Jaffe, Duncan 1995]
Tagare, H., Vos, F., Jaffe, C., Duncan,
J. 1995. Arrangement: A spatial relation between parts for evaluating
similarity of tomographic section IEEE Transactions on Pattern Analysis
and Machine Intelligence, 17 (9), 880893.
Ullman, J. D. 1988. Principles of Database
and Knowledge Base Systems, 1. Computer Science Press, Potomac, Maryland.
Woods, W. A. Schmolze,
J. G. 1992. The KLONE family In Lehmann, F. W., Semantic
Networks in Artificial Intelligence, 133178. Pergamon Press. Published
as a special issue of Computers & Mathematics with Applications,
Volume 23, Number 29.
Yen, J. 1991. Generalizing term subsumption
languages to Fuzzy logic In Proceedings of the Twelfth International
Joint Conference on Artificial Intelligence (IJCAI'91), 472477.
Zadeh, L. 1965. Fuzzy sets Information
and Control, 8, 338353.
^{1}See e.g., http://wwwqbic.almaden.ibm.com/cgibin/stampsdemo
^{2}Obviously, a Domain Closure Assumption on regions
is not valid in artificial vision, dealing with twodimensional images of
threedimensional shapes (and scenes), because solid shapes have surfaces that
will be hidden in their images. But this is outside the scope of our retrieval
problem.
^{3}Not exactly 0, since every shape matches every
other one with a very low similarity measure. Similarity is often computed as
the inverse of a distance. Similarity 0 would correspond to infinite distance.
Nevertheless, the recognition algorithm can force the similarity to 0 when it
is below a threshold.
^{4}e.g., Altavista, QBIC, NETRA, Blobworld, but
also Yahoo (for textual documents).
File translated from T_{E}X by T_{T}H, version 3.05.
On 19 Apr 2002, 12:06.