\documentclass[jair,twoside,11pt,theapa]{article}
\usepackage{jair}
\usepackage[dvips]{graphics}
\usepackage{graphicx}
\usepackage{theapa}
\usepackage{epsfig}

% some macros ======
\def\exsty#1{\mbox{\texttt{#1}}} %defines the style for examples and
\def\per{\mbox{\textbf{.}}}
\def\qed{\hfill\fbox{\space}\\ \vskip 1\baselineskip}

\newcommand{\dd}[3]{#1_{1}{#3}\dots{#3}#1_{#2}} % makes x1 o ... o xn
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}

\def\ie{\textit{i.e.},\ }
\def\eg{\textit{e.g.},\ }
\def\wrt{with reference to\ }
\def\centr#1{centr(#1)} % centroid of #1
\def\p{\textbf{\textrm{p}}}    % style for points (centroids)
\def\u{\textbf{\textrm{u}}}
\def\v{\textbf{\textrm{v}}}
\newcommand{\llist}[1]{\langle #1 \rangle}
\newcommand{\AND}{\ensuremath{\sqcap}}
\newcommand{\ALL}[2]{\exsty{ALL} #1 \per #2}
\newcommand{\SOME}[2]{\exists (#1) \per #2}
\newcommand{\proof}[1]{\textsl{Proof.} #1 \qed}

\newcommand{\fourcomponent}[4]{\langle #1,#2,#3,#4 \rangle}
\newcommand{\twocomponent}[2]{\langle #1,#2 \rangle}
\def\I{{\ensuremath{\cal I}}}
\newcommand{\Int}[1]{#1^\I}             % argument^I
                                        % interpretation function
\newcommand{\INT}[1]{(#1)^\I}           % (argument)^I,
                                        % interpretation function
%%%%%%%%%%%%%%%%%%%%%%%%

\jairheading{16}{2002}{209-257}{5/01}{3/02}
%%%%%%%%%%%%%%%%%%%%%%%%

\ShortHeadings{Structured Knowledge Representation for Image
Retrieval} {Di Sciascio, Donini \& Mongiello}

\firstpageno{209}

\begin{document}

% Definition of title page:
\title{Structured Knowledge Representation for Image Retrieval}
\author{\name Eugenio Di Sciascio \email disciascio@poliba.it \\
    \name Francesco M. Donini \email donini@poliba.it \\
    \name Marina Mongiello \email mongiello@poliba.it \\
        \addr Dipartimento di Elettrotecnica ed Elettronica,
    Politecnico di Bari \\
    Via Re David, 200 -- 70125 BARI Italy}

%\date{}    % optional

\maketitle

\begin{abstract}
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 low-level features extracted
with image analysis to detect and characterize regions in an
image. However, in contrast with feature-based 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 client-server 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 well-established measure of quality borrowed from
textual information retrieval.
\end{abstract}


\section{Introduction}\label{sec:intro}
%\section{Introduction}

% di cosa ci occupiamo

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 \emph{content-based} image retrieval, in which criteria express
properties of the appearance of the image itself, \ie\ on its
pictorial characteristics.

% dove si e' arrivati finora

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 so-called \emph{low-level}
characteristics, such as color distribution, or texture.  For
example, systems such as IBM's QBIC\footnote{See \eg
\texttt{http://wwwqbic.almaden.ibm.com/cgi-bin/stamps-demo}} 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.

% cosa manca

Nevertheless, present systems fail at treating correctly
\emph{high-level} 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 \emph{high-level}
features. Usually, this is overcome with the help of examples:
``retrieve images similar to \emph{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 \emph{white} horse. In
this aspect, image retrieval faces the same problems of
\emph{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, high-level
specification of the image retrieval task. This need motivates the
research we report here.

% cosa proponiamo noi

\subsection{Contributions of the Paper}

We approach the problem of image retrieval from a knowledge
representation perspective, and in particular, we refer to a
framework already successfully applied by \citeA{wood-schm-92} to
conceptual modeling and semantic data models in databases
\cite{calv-lenz-nard-98}.  We consider image retrieval as a
knowledge representation problem, in which we can distinguish the
following aspects:

\textbf{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.

\textbf{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.


\textbf{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 \wrt the computational complexity of the problems.  Presently,
     we solved the problem for exact retrieval, and propose an algorithm
     for approximate retrieval which, although probably non-optimal, is
     correct.

\textbf{Experiments:} while the study of the complexity of the
problem
     is ongoing, the syntax, semantics, and sub-optimal 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.

% quali benefici otteniamo

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
\emph{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
\cite{chan-hare-80}.  Third, our language borrows from object
modeling in Computer Graphics the hierarchical organization of
classes of images \cite{fole-etal-96}.  This, in addition to an
interpretation of composite shapes which one can immediately
visualize, opens our logical approach to retrieval of images of
3D-objects constructed in a geometric language
\cite{paqu-riou-99}, 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 (\ie\ non-rigid) parts of a composite shape.  This
exemplifies how our logical approach can shed light to extensions
of our syntax suitable for, \eg video sequence retrieval.

\subsection{Outline of the Paper}

The rest of the paper is organized as follows.  In the next
section, we review related work on image retrieval.  In
Section~\ref{sec:syntax} 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~\ref{sec:prototype} 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.


\section{Related Work}\label{sec:related}
Content-Based 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.
\subsection{Feature-based Approaches}
Largest part of research on CBIR has focused on low-level 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
\cite{Hirata-92,Niblak-93,Picard-93,Jacobs-95,Flickner-95,Bach-96,Celentano-98,Cox-00,Gevers-00}.

Among the various projects, particularly interesting is the
\textsc{QBIC} system \cite{Niblak-93,Flickner-95}, 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,
\textsc{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
\textsc{VisualSeek} \cite{Smith-96}, \textsc{NETRA}
\cite{ma-manj-97} and \textsc{Blobworld} \cite{cars-99}. 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 query-retrieval 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 feature-based 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 \textsc{MARS}
\cite{Rui-97}, \textsc{DrawSearch} \cite{disc-mong-99} and
\textsc{PicHunter} \cite{Cox-00}.

\subsection{Approaches Based on Spatial Constraints}

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
"symbolic images" or icons, identified with a single point in the
2D-space. Information on the content and visual appearance of
images are normally neglected.

\citeA{chang-83} present the modeling of this type of images  in
terms of \emph{2D-strings}, 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.

\citeA{gudi-ragh-95} consider the objects in a symbolic image
associated with vertexes in a weighted graph. Edges --- \ie  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
spatial-graphs. The similarity measure depends on the number of
edges and on the comparison between the orientation and slope of
edges in the two spatial-graphs. 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 \citeA{gudi-99}
and by \citeA{elkw-kabu-99}, which basically propose extensions of
the strings approach for efficient retrieval of subsets of icons.
\citeA{gudi-99} defines  $\theta$R-strings, a logical
representation of an image. Such representation also provides a
geometry-based 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
$\theta$R-strings. 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.

\citeA{elkw-kabu-99} propose a further extension of the
spatial-graph 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
graph-matching one previously described by \citeA{gudi-ragh-95}.
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.

\subsection{Logic-based and Structured Approaches}

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 \citeA{broo-81}. 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 \citeA{marr-82}. \citeA{reit-mack-89} 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 three-dimensional images are already
present in languages for virtual reality like VRML \cite{VRML} 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.

\citeA{Meghini01} proposed a formalism integrating Description
Logics and image and text retrieval, while
\citeA{haar-lutz-moel-98} integrate Description Logics with
spatial reasoning. Further extensions of the approach are
described by \citeA{moel-neum-wess-99}. Both proposals build on
the clean integration of Description Logics and \emph{concrete
domains} of \citeA{baad-hans-91}. However,  neither of the
formalisms can be used to build complex shapes by nesting more
simple shapes. Moreover, the proposal by \citeA{haar-lutz-moel-98}
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 \citeA{Hacid99} 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 \citeA{ardi-97},
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
\citeA{bert-cata-98}. However, reasoning about queries
(containment and emptiness) is not considered in this approach.
\citeA{aiello-01} proposes a multi-modal 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 \citeA{taga-vos-95}. 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
\citeA{sanf-fu-83} 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 ``$\mathrm{\Gamma}$" --- 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 logic-based multimedia retrieval system was proposed by
\citeA{Fuhr98}; the method, based on an object-oriented logic,
supports aggregated objects but it is oriented towards a
high-level semantic indexing, which neglects low-level 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 \citeA{Edelmann99}. 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 \citeA{pirri-finzi-99}, 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 high-level formalism.


\section{Syntax and Semantics}\label{sec:syntax}
%\section{The formal language}

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 \emph{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.


\subsection{Syntax}

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.

\emph{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 2D-curve in a space whose origin
coincides with the centroid of $B$.  Examples of basic shapes can
be \exsty{circle}, \exsty{rectangle}, with the contours
$e(\exsty{circle})=\bigcirc$,
$e(\exsty{rectangle})=\framebox{\phantom{aaa}}$, 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
\emph{external} contour of a region. For example, if a region is
contained in another, as in \framebox{~$\bigcirc$~}, 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
rotation-translation-scaling transformation as $\tau$.  Recall
that transformations can be composed in sequences
$\dd{\tau}{n}{\circ}$, and they form a mathematical group.

The basic building block of our syntax is a \emph{basic shape
component} ${\fourcomponent{c}{t}{\tau}{B}}$, which represents a
region with color $c$, texture $t$, and edge contour $\tau(e(B))$.
With $\tau(e(B))$ we denote the pointwise transformation $\tau$ of
the whole contour of $B$. For example, $\tau$ 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.

 \emph{Composite shape descriptions} are conjunctions of basic shape
 components --- each one with its own color and texture --- denoted as
\[
C = \fourcomponent{c_{1}}{t_{1}}{\tau_{1}}{B_{1}} \AND \cdots \AND
\fourcomponent{c_{n}}{t_{n}}{\tau_{n}}{B_{n}}
\]
We do not expect end users of our system to actually define
composite shapes with this syntax; this is just the
\emph{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~\ref{fig:syntax}).

%\begin{figure}
%\vspace{10cm}
%\hspace{2cm}
%\special{bmp:candelac.bmp x=13.5cm y=10cm}
%\caption{The graphical interface with a query by sketch.
%{\label{fig:syntax}}}
%\end{figure}

\begin{figure}
\centerline{\includegraphics[width=6.0in]{candelac.eps}}
\caption{The graphical interface with a query by sketch.
\label{fig:syntax}}
\end{figure}

For example, the composite shape \exsty{lighted-candle} could be
defined as
\[
\exsty{lighted-candle} =
\fourcomponent{c_{1}}{t_{1}}{\tau_{1}}{\exsty{rectangle}} \AND
\fourcomponent{c_{2}}{t_{2}}{\tau_{2}}{\exsty{circle}}
\]
with $\tau_{1},\tau_{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 \cite{disc-doni-mong-00} we presented a
formalism including nested composite shapes, as it is done in
hierarchical object modeling \cite[Ch.7]{fole-etal-96}.  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~\ref{subsec:algo-approx} on.

\subsection{Semantics}

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 $\Delta$,
and shapes and components are interpreted as subsets of $\Delta$.
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, \eg the one based on Description Logics by
\citeA{Meghini01}.  In that setting, image retrieval amounts to
logical inference.  However, observe that usually a \emph{Domain
Closure Assumption} \cite{reit-80} 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\footnote{%
Obviously, a Domain Closure Assumption on regions is not valid in
artificial vision, dealing with two-dimensional images of
three-dimensional 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.  }.

Formally, an interpretation is a pair $(\I,\Delta)$, where
$\Delta$ is a set of images, and $\I$ is a mapping from shapes and
components to subsets of $\Delta$.  We identify each image $I$
with the set of regions $\{\dd{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\in \Delta$ belongs to the interpretation of a basic
shape component $\Int{\twocomponent{\tau}{B}}$ if $I$ contains a
region whose contour matches $\tau(e(B))$.  In formulae,
\begin{equation}
    \label{basic-exact-int}
\Int{\twocomponent{\tau}{B}}=\{ I\in \Delta ~|~ \exists r \in I :
e(r) = \tau(e(B)) \}
\end{equation}
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 \emph{characteristic
function} $f_{S}$ of a set $S$ is a function whose value is either
1 or 0; $f_{S}(x) = 1$ if $x\in S$, $f_{S}(x) = 0$ otherwise. We
consider now the characteristic function  of the set defined in
Formula~(\ref{basic-exact-int}).  Let $I$ be an image; if $I$
belongs to $\Int{\twocomponent{\tau}{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
$\Int{\twocomponent{\tau}{B}}$ also to denote the characteristic
function (with an argument $(I)$ to distinguish it from the set).
\[
\Int{\twocomponent{\tau}{B}}(I) =
   \left\{
   \begin{array}{cc}
       1 & \mbox{if } \exists r \in I : e(r) = \tau(e(B))  \\
       0 & \mbox{otherwise}
   \end{array}
   \right.
\]
Now we reformulate this function in order to make it return a real
number in the range $[0,1]$ --- as usual in fuzzy logic
\cite{zade-??}. Let $sim(\cdot,\cdot)$ be a similarity measure
from pairs of contours into the range $[0,1]$ of real numbers
(where 1 is perfect matching). We use $sim(\cdot,\cdot)$ 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:
\[
\Int{\twocomponent{\tau}{B}}(I) = \max_{r\in I} \{sim(e(r),
\tau(e(B))) \}
\]
 Note that $sim$ depends on
translations, rotation and scaling, since we are looking for
regions in $I$ whose contour matches $e(B)$, \wrt\ the position
and size specified by $\tau$.

The interpretation of basic shapes, instead, includes a
translation-rotation-scaling invariant recognition, which is
commonly used in single-shape Image Retrieval.
 We define the
interpretation of a basic shape as
\[
\Int{{B}}=\{ I\in \Delta ~|~ \exists\tau ~\exists r \in I : e(r) =
\tau(e(B)) \}
\]
and its approximate counterpart as the function
\[
\Int{{B}}(I) = \max_{\tau} \max_{r\in I} \{ sim(e(r), \tau(e(B)))
\}
\]
The maximization over all possible transformations $\max_{\tau}$
can be effectively computed by using a similarity measure
$sim_{ss}$ that is invariant \wrt\ translation-rotation-scaling
(see Section~\ref{subsec:algo-approx}).  Similarity of color and
texture will be added as a weighted sum in
Section~\ref{subsec:algo-approx}. In this way, a basic shape $B$
can be used as a query to retrieve all images from $\Delta$ which
are in $\Int B$.  Therefore, our approach generalizes the more
usual approaches for single-shape retrieval, such as Blobworld
\cite{cars-99}.

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.
% \footnote{Recall that in the syntax
% we did not include a ``composite shape component"
% $\fourcomponent{c}{t}{\tau}{C}$ --- this would be necessary only if we
% used a composite shape description as a (grouped) component in a more
% complex shape, see \cite{disc-doni-mong-00}.}.
Let $C$ be a composite shape description
$\twocomponent{\tau_{1}}{B_{1}}\AND \cdots \AND
\twocomponent{\tau_{n}}{B_{n}}$. In exact matching, the
interpretation is the intersection of the sets interpreting each
component of the shape:
\begin{equation}
    \Int{C}=\{ I\in \Delta ~|~ \exists\tau: I \in \cap_{i=1}^n
    \Int{\twocomponent{(\tau\circ\tau_{i})}{B_{i}}}\}
    \label{composite-exact-int}
\end{equation}
Observe that we require all shape components of $C$ to be
transformed into image regions using the same transformation
$\tau$.  This preserves the arrangement of the shape components
relative to each other --- given by each $\tau_{i}$ --- while
allowing $\Int C$ to include every image containing a group of
regions in the right arrangement, wholly displaced by $\tau$.

%\begin{figure}
%  \vspace{10cm}
   %\hspace{2cm}
%   \special{bmp:formula2.bmp x=13.5cm y=10cm}
%   \caption{An example of application of Formula~(\protect{\ref{composite-exact-int}}).
%   {\label{fig:formula2}}}
%\end{figure}

\begin{figure}
\centerline{\includegraphics[height=3.5in]{formula2.eps}}
\caption{An example of application of
Formula~(\protect{\ref{composite-exact-int}}).\label{fig:formula2}}
\end{figure}


To clarify this formula, consider Figure~\ref{fig:formula2}: the
shape $C$ is composed by two basic shapes $B_{1}$ and $B_{2}$,
suitably arranged by the transformations $\tau_{1}$ and
$\tau_{2}$. Suppose now that $\Delta$ contains the image $I$.
Then, $I \in \Int{C}$ because there exists the transformation
$\tau$, which globally brings $C$ into $I$, that is, $\tau \circ
\tau_{1}$ brings the rectangle $B_{1}$ into a rectangle recognized
in $I$, and $\tau \circ\tau_{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.
\begin{definition}[Recognition]\label{def:recognition}
    A shape description $C$ is \emph{recognized} in an image $I$ if for every
    interpretation $(\I,\Delta)$ such that $I \in \Delta$, it is $I \in \Int C$.
    An interpretation $(\I,\Delta)$ \emph{satisfies} a composite shape description
    $C$ if there exists an image $I \in \Delta$ such that $C$ is recognized
    in $I$.  A composite shape description is \emph{satisfiable} if
    there exists an interpretation satisfying it.
\end{definition}
%
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~\ref{prop:unsat}).

Observe also that our set-based semantics implies the intuitive
interpretation of conjunction ``$\AND$" --- one could easily prove
that $\AND$ is commutative and idempotent.
%The semantics implies also the existence
%of equivalent descriptions.  Namely, if $C$ and $C'$ have the same
%components in different order, they have the same interpretation,
%hence $C \equiv C'$.

For approximate matching, we modify
definition~(\ref{composite-exact-int}), following the fuzzy
interpretation of $\AND$ as minimum, and existential as maximum:
\begin{equation}
    \Int{C}(I) = \max_\tau~\{ \min_{i=1}^n~\{
    \Int{\twocomponent{(\tau\circ\tau_{i})}{B_{i}}}(I)\}\}
\label{composite-fuzzy-int}
\end{equation}
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 $\Int 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\footnote{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.} also the measure of $\Int
C(I)$.  This is more strict than, \eg Gudivada \& Raghavan's
\citeyear{gudi-ragh-95} or El-Kwae \& Kabuka's
\citeyear{elkw-kabu-99} approaches, in which a non-appearing
component can decrease the similarity value of $\Int 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" \emph{enlarging} the set of results
that the user was trying to restrict.  We formalize this
refinement process through the following definition.

\begin{proposition}[Downward refinement]\label{down}
    Let $C$ be a composite shape description, and let $D$ be a refinement
    of $C$, that is $D \doteq C \AND \twocomponent{\tau'}{B'}$.  For every
    interpretation $\I$, if shapes are interpreted as
    in~(\ref{composite-exact-int}), then $\Int D \subseteq \Int C$; if
    shapes are interpreted as in~(\ref{composite-fuzzy-int}), then for
    every image $I$ it holds $\Int D(I) \le \Int C(I)$.
\end{proposition}
%
\textsl{Proof.} For (\ref{composite-exact-int}), the claim follows
from the fact that $\Int D$ considers an intersection of the same
components as the one of $\Int C$, plus the set
$\Int{\twocomponent{(\tau\circ\tau')}{B'}}$.  For
(\ref{composite-fuzzy-int}), the claim analogously follows from
the fact that $\Int D(I)$ computes a minimum over a superset of
the values considered for $\Int C(I)$. \qed

The above property makes our language fully \emph{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 \cite{gudi-ragh-95,elkw-kabu-99} this
property does not hold. We illustrate the problem in
Figure~\ref{fig:noi-gudy}.  Starting with shape description $C$,
we may retrieve (among many others) the two images $I_{1}, I_{2}$,
for which both $\Int C(I_{1})$ and $\Int C(I_{2})$ are above a
threshold $t$, while another image $I_{3}$ is not in the set
because $\Int 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, $\Int D(I_{3}) \le \Int 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
$\Int D(I_{3}) > t > \Int 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.

%\begin{figure}[t]
%    \centering
%    \vspace{10cm}
%    \special{bmp:dw2.bmp x=11cm y=11cm}
%    \caption{Downward refinement: the thin arrows denote membership in
%    exact recognition, and non-zero similarity in approximate
%    recognition. The tick arrow denotes a refinement. \protect\label{fig:noi-gudy}}
%\end{figure}

\begin{figure}
\centerline{\includegraphics[height=3.5in]{dw2.eps}}
\caption{Downward refinement: the thin arrows denote non-zero
similarity in approximate recognition.  The thick arrow denotes a
refinement. \protect\label{fig:noi-gudy}}
\end{figure}

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 \cite{doni-etal-96}, and
its fuzzy extensions \cite{yen-91,Straccia01}.

\begin{definition}[Subsumption]
    A description $C$ \emph{subsumes} a description $D$ if for every
    interpretation $\I$, $\Int D \subseteq \Int C$.  If
    (\ref{composite-fuzzy-int}) is used, $C$ subsumes $D$ if for every
    interpretation $\I$ and image $I\in\Delta$, it is $\Int D (I) \le \Int C
    (I)$.
\end{definition}
%
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 \emph{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 \cite{ullm-88}, it becomes even more important in an
image retrieval setting, since the recognition of specific
features in an image can be computationally demanding.
%\begin{figure}
%\vspace{10cm}
%\hspace{2cm}
%\special{bmp:sub.bmp x=11cm y=11cm}
%\caption{An example of subsumption hierarchy of shapes,
%      and images in which the shapes can be recognized.\label{fig:subsumption}}
%\end{figure}

%\begin{figure}[t]
%       \includegraphics[\textwidth,\textheight]{sub.eps}
%      \protect\caption{An example of subsumption hierarchy of shapes,
%      and images in which the shapes can be recognized.\label{fig:subsumption}}
%\end{figure}

\begin{figure}
\centerline{\includegraphics[height=3.5in]{sub.eps}} \caption{An
example of subsumption hierarchy of shapes (thick arrows),
        and images in which the shapes can be recognized (thin
        arrows).\label{fig:subsumption}}
\end{figure}


Figure~\ref{fig:subsumption} 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 \emph{background}, it could be
added to our framework as a special basic component
$\fourcomponent{c}{t}{\underline{~}}{\exsty{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.


\section{Reasoning and Retrieval}\label{sec:reasoning}
%\section{Reasoning services}

We envisage several reasoning services that can be carried out in
a logic for image retrieval:
\begin{enumerate}

    \item shape recognition: Given an image $I$ and a shape description
    $D$, decide if $D$ is recognized in $I$.

    \item image retrieval: given a database of images and a shape
    description $D$, retrieve all images in which $D$ can be recognized.

    \item image classification: given an image $I$ and a collection of
    descriptions $D_{1},\ldots,D_{n}$, find which descriptions can be
    recognized in $I$.  In practice, $I$ is classified by finding the
    \emph{most specific} descriptions (\wrt\ subsumption) it satisfies.
    Observe that classification is a way of ``preprocessing" recognition.

%     \item  description satisfiability: verify if a given description may
%   contain at least one image --- e.g., there are no overlapping regions
%   in the description;

    \item description subsumption (and classification): given a (new)
    description $D$ and a collection of descriptions $D_{1},\ldots,D_{n}$,
    decide whether $D$ subsumes (or is subsumed by) each $D_{i}$, for
    $i=1,\ldots,n$.

\end{enumerate}
%
While services 1--2 are standard in an image retrieval system,
services 3--4 are less obvious, and we briefly discuss them below.

The process of image retrieval is quite expensive, and systems
usually perform off-line processing of data, amortizing its cost
over several queries to be answered on-line.  As an example, all
document retrieval systems for the web\footnote{\eg Altavista,
QBIC, NETRA, Blobworld, but also Yahoo (for textual documents).},
both for images and text, use spiders to crawl the web and extract
some relevant features (\eg 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, \wrt
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},\ldots,D_{n}$ and all
images in the database were already classified \wrt\
$D_{1},\ldots,D_{n}$, then it may suffice to classify $D$ \wrt\
$D_{1},\ldots,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 \cite{nebe-90}.

For example, to answer the query asking for images containing an
\exsty{arch}, a system may classify \exsty{arch} and find that it
subsumes \exsty{threePortalsGate} (see
Figure~\ref{fig:subsumption}). 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.


\subsection{Exact Reasoning on Images and Descriptions}\label{subsec:algo-exact}
%\section{Computing satisfiability, recognition and subsumption}

We start with a reformulation of (\ref{composite-exact-int}), more
suited for computational purposes.

\begin{theorem}[Recognition as mapping]\label{thm-recognition}
    Let $C=\twocomponent{\tau_{1}}{B_{1}}\AND \cdots \AND
    \twocomponent{\tau_{n}}{B_{n}}$ be a composite shape description, and
    let $I$ be an image, segmented into regions $\{\dd{r}{m}{,}\}$. Then
    $C$ is recognized in $I$ iff there exists a transformation $\tau$
    and an injective mapping $j : \{1,\ldots,n\} \rightarrow \{1,\ldots, m \}$
    such that for $i=1,\ldots,n$ it is $$e(r_{j(i)}) =
    \tau(\tau_{i}(e(B_{i})))$$
\end{theorem}
%
\proof{
    From~(\ref{composite-exact-int}), $C$ is recognized in  $I$ iff
\[
\exists \tau [ I \in \bigcap_{i=1}^n
\Int{\twocomponent{(\tau\circ\tau_{i})}{B_{i}}}] \mbox{~which is
equivalent to~} \exists \tau [ \bigwedge_{i=1}^n I \in
\Int{\twocomponent{(\tau\circ\tau_{i})}{B_{i}}}]
\]
Expanding $\Int{\twocomponent{(\tau\circ\tau_{i})}{B_{i}}}$ with
its definition~(\ref{basic-exact-int}) yields
\[
\exists \tau [ \bigwedge_{i=1}^n \exists r\in I .
e(r)=\tau(\tau_{i}(e(B_{i})))]
\]
and since regions in $I$ are $\{\dd{r}{m}{,}\}$ this is equivalent
to
\[
\exists \tau [ \bigwedge_{i=1}^n \bigvee_{j=1}^m
e(r_{j})=\tau(\tau_{i}(e(B_{i})))]
\]
Making explicit the disjunction over $j$ and conjunctions over
$i$, we can arrange this conjunctive formula as a matrix:
\begin{equation}
\exists \tau \left[ \begin{array}{ccccccc}
                      (e(r_{1})=\tau(\tau_{1}(e(B_{1}))) & \vee & \cdots &
                      \vee &
                      e(r_{m})=\tau(\tau_{1}(e(B_{1})))) & ) & \wedge  \\
              \vdots & \vee & \vdots & \vee & \vdots &  & \wedge \\
                      (e(r_{1})=\tau(\tau_{n}(e(B_{n}))) & \vee & \cdots &
                      \vee &
                      e(r_{m})=\tau(\tau_{n}(e(B_{n})))) & ) &
          \end{array}
          \right]
          \label{matrix:exact}
\end{equation}
Now we note two properties in the above matrix of equalities:
\begin{enumerate}
    \item For a given transformation, at most one region among
    $\dd{r}{m}{,}$
    can be equal to each component.  This means that in each row, at most
    one disjunct can be true for a given $\tau$.

    \item  For a given transformation, a region can match at most one
    component. This means that in each column, at most one equality
    can be true for a given $\tau$.

\end{enumerate}
We observe that these properties do not imply that regions have
all different shapes, since the equality of contours
\emph{depends} on any translation, rotation, and scaling.  We use
equality to represent true overlap, and not just equal shape.

Properties 1--2 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,\ldots,n\} \rightarrow
\{1,\ldots,m\}$. Hence, Formula~(\ref{matrix:exact}) can be
rewritten into the claim:
\begin{equation}
\exists \tau [ \exists j:\{1..n\} \rightarrow \{1..m\}
\bigwedge_{i=1}^n e(r_{j(i)})=\tau(\tau_{i}(e(B_{i}))) ]
    \label{eqn:tau:mapping:exact}
\end{equation}
%
%     From~(\ref{composite-exact-int}), $I$ satisfies $C$ iff there exists a
% transformation $\hat{\tau}$ such that
% \[
% I \in \cap_{i=1}^n \Int{\twocomponent{(\hat{\tau}\circ\tau_{i})}{B_{i}}}
% \]
% From~(\ref{basic-exact-int}), the above membership of $I$ to the intersection
% set implies that there are $n$ regions
% $\{r_{q_{1}},\ldots,r_{q_{n}} \}$ in $I$  such that
% $e(r_{q_{k}})= \hat{\tau}\circ \tau_{k} ( e ( B_{k}))$   for
% $k=1,\ldots,n$. Then let $j(k) = q_{k}$  for $k=1,\ldots,n$. Since regions are mapped to
% non-overlapping components, the same region cannot appear twice in the
% sequence $\{r_{q_{1}},\ldots,r_{q_{n}} \}$. Hence, $j$ is injective.
} % fine della dimostrazione
\noindent 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)},\ldots,r_{j(n)}$ for each possible mapping $j$.

Observe that $j$ injective implies $m \ge n$, as one would expect.
The above proposition leaves open which one between $\tau$ 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 $\tau$. 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.

% also a different computational formulation could be
% given, considering first subsets of $k$ regions from the $n$
% regions in the image, and then verifying if there exists a matching transformation
% from the components of $C$ to the subset of regions. This corresponds
% to exchanging the existential quantifiers in the above proposition.
%
% \begin{proposition}[Exact recognition, II]
%   Let $C=\twocomponent{\tau_{1}}{B_{1}}\AND \cdots \AND
%   \twocomponent{\tau_{n}}{B_{k}}$ be a composite shape description, and
%   let $I$ be an image, segmented into regions $\{\dd{r}{n}{,}\}$. Then
%   $C$ is recognized in $I$ iff
%   there exists a subset $\{\dd{j}{k}{,}\}$ of $\{1,\ldots,n\}$ such
%   that there exists a transformation $\tau$
%         such that for each $i \in 1..k$
%   $\tau(\tau_{i}(e(B_{i})))=e(r_{j_{i}})$.
% \end{proposition}
% %
% We will not make use of this formulation now; but observe that
%  when approximate recognition
% is computed.
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~(\ref{basic-exact-int}) are skolemized with their
prototypical contours.  Formal definitions follow.
%
\begin{definition}[Prototypical image]
    Let $B$ be a basic shape.  Its \emph{prototypical image} is
    $I(B)=\{e(B)\}$.
    Let $C=\twocomponent{\tau_{1}}{B_{1}}\AND \cdots
    \AND \twocomponent{\tau_{n}}{B_{n}}$ be a composite shape description.
    Its \emph{prototypical image} is $I(C) = \{ \tau_{1}(e(B_{1})),\ldots,
    \tau_{n}(e(B_{n})) \}$.
\end{definition}
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 query-by-sketch 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 \wrt\ the semantics.

Prototypical images have some important properties.  The first is
that they satisfy (in the sense of
Definition~\ref{def:recognition}) the shape description they
exemplify --- as intuition would suggest.
%
\begin{proposition}
    \label{D-is-in-its-proto-image}
    For every composite shape description $D$, if $D$ is satisfiable then
    the interpretation $\langle\I,\{I(D)\}\rangle$ satisfies $D$.
\end{proposition}
\proof{From Theorem~\ref{thm-recognition}, using an identical
transformation $\tau$ and the identity mapping for $j$.
} % fine dimostrazione

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.

\begin{proposition}\label{prop:unsat}
    A shape description $D$ is satisfiable iff its prototypical image
    $I(D)$ contains no overlapping regions.
\end{proposition}

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.
%
\begin{theorem}\label{thm:subs-via-rec}
A composite shape description $C$ subsumes a description $D$ if
and only if $C$ is recognized in the prototypical image $I(D)$.
\end{theorem}
%
\proof{ Let $C=\twocomponent{\tau_{1}}{B_{1}}\AND \cdots \AND
\twocomponent{\tau_{n}}{B_{n}}$, and let $D =
\twocomponent{\sigma_{1}}{A_{1}}\AND \cdots \AND
\twocomponent{\sigma_{m}}{A_{m}}$. Recall that $I(D)$ is defined
by $I(D) = \{ \sigma_{1}(e(A_{1})),\ldots, \sigma_{m}(e(A_{m}))
\}$. To ease the reading, we sketch the idea of the proof in
Figure~\ref{fig:subs-via-recognition}.

\begin{figure}[t]
    \centering
    {\tt    \setlength{\unitlength}{0.8pt}
\begin{picture}(458,326)
\thinlines
% text
              \put(120,164){$\hat{\sigma}\circ\hat{\tau}$}
              \put(324,180){$\hat{\tau}$}
              \put(205,91){$\hat{\sigma}$}
              \put(169,307){(prototypical image of) $C$}
              \put(282,50){prototypical image $I(D)$}
              \put(33,12){image $J$}
% upper image C
              \put(157,199){\framebox(184,100){}} % frame
              \put(244,267){\circle{34}} % tree
              \put(238,217){\framebox(12,32){}}

% lower image D
          \put(264,63){\framebox(184,100){}} % frame
              \put(359,136){\circle{34}} % tree
          \put(355,99){\framebox(8,24){}}
              \put(330,74){\framebox(84,24){}} % base

% lower left image J
              \put(10,26){\framebox(184,100){}} % frame
              \put(154,107){\circle{20}} % sun on the right
              \put(39,82){\line(-1,1){11}} % roof of the left tower
              \put(17,82){\line(1,1){11}}
              \put(64,73){\framebox(5,26){}} % windows in the right tower
              \put(53,73){\framebox(5,26){}}
              \put(17,31){\framebox(22,51){}} % left tower
              \put(45,31){\framebox(33,80){}} % right tower
              \put(97,79){\circle{18}} % tree
              \put(93,50){\framebox(7,20){}}
              \put(79,31){\framebox(60,18){}}  % base

% transformations
              \put(139,40){\line(4,1){190}} % sigma
              \put(106,78){\line(4,1){238}}
              \put(100,51){\line(4,1){255}}
              \put(347,143){\line(-3,4){87}} % tau
              \put(355,108){\line(-3,4){105}}
              \put(100,57){\line(3,4){135}} % tau+sigma
              \put(100,87){\line(3,4){128}}

\end{picture}}

    \caption{A sketch of the If-proof of Theorem~\ref{thm:subs-via-rec}}
    \label{fig:subs-via-recognition}
\end{figure}

%\begin{figure}
%\vspace{10cm}
%\hspace{2cm}
%\special{bmp:figura4.bmp x=11.5cm y=10cm}
%\caption{A sketch of the If-proof of Theorem~\ref{thm:subs-via-rec}.\label{fig:subs-via-recognition}}
%\end{figure}

%\begin{figure}
%\centerline{\includegraphics[height=3.5in]{spatial.eps}}
%\caption{Representation of angles used for computing spatial similarity of component 1
%     and region $r_{j(1)}$. \label{fig:spatial}}
%\end{figure}

\textbf{If.} Suppose $C$ is recognized in $I(D)$, that is, $I(D)
\in \Int C$ for every interpretation $(\I,\Delta)$ such that
$I(D) \in \Delta$.  Then, from Theorem~\ref{thm-recognition} there
exists a transformation $\hat{\tau}$ and a suitable injective
function $j$ from $\{1,\ldots,n\}$ into $\{1,\ldots,m\}$ such that
\begin{eqnarray*}
e(r_{j(k)})= \hat{\tau}\circ \tau_{k} ( e ( B_{k})) &   &\mbox{
for } k=1,\ldots,n
\end{eqnarray*}
Since $I(D)$ is the prototypical image of $D$, we can substitute
each region with the basic shape of $D$ it comes from:
\begin{eqnarray}
    \sigma_{j(k)}(e(A_{j(k)}))= \hat{\tau}\circ \tau_{k} ( e (
B_{k})) &  & \mbox{    for } k=1,\ldots,n
    \label{sigma-A-tau-B}
\end{eqnarray}
Now suppose that $D$ is recognized in an image $J = \{ \dd s p
,\}$, with $J \in \Delta$. We prove that also $C$ is recognized in
$J$. In fact, if $D$ is recognized in $J$ then there exists a
transformation $\hat{\sigma}$ and another injective mapping $q$
from $\{1,\ldots,m\}$ into $\{1,\ldots,p\}$ selecting from $J$
regions $\{ s_{q(1)},\ldots,s_{q(m)}\}$ such that
\begin{eqnarray}
    e(s_{q(h)})= \hat{\sigma}\circ \sigma_{h} ( e ( A_{h})) &  & \mbox{     for }
h=1,\ldots,m
    \label{s-sigma-A}
\end{eqnarray}
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
\begin{eqnarray}
    e(s_{q(j(k))})= \hat{\sigma}\circ \sigma_{j(k)} ( e ( A_{j(k)})) &  & \mbox{     for }
k=1,\ldots,n
    \label{q-composed-j}
\end{eqnarray}
Then, substituting equals for equals from~(\ref{sigma-A-tau-B}),
one finally gets
\begin{eqnarray*}
    e(s_{q(j(k))})= \hat{\sigma}\circ \hat{\tau}\circ \tau_{k} ( e (
B_{k})) &  & \mbox{     for } k=1,\ldots,n
\end{eqnarray*}
which proves that $C$ too is recognized in $J$, using
$\hat{\sigma}\circ \hat{\tau}$ as transformation of its
components, and $q(j(\cdot))$ as injective mapping from
$\{1,\ldots,n\}$ into $\{1,\ldots,p\}$. Since $J$ is a generic
image, it follows that $\Int D \subseteq \Int C$. Since
$(\I,\Delta)$ is generic too, $C$ subsumes $D$.

\textbf{Only if.} The reverse direction is easier: suppose $C$
subsumes $D$. By definition, this amounts to $\Int D \subseteq
\Int C$ for every collection of images $\I$. For every $\I$ that
contains $I(D)$, then $I(D) \in \Int D$ for
Proposition~\ref{D-is-in-its-proto-image}. Therefore, $I(D) \in
\Int C$, that is, $C$ is recognized in $I(D)$.
} % fine dimostrazione

This property allows us to compute subsumption as recognition, so
we concentrate on complex shape recognition, using
Theorem~\ref{thm-recognition}.
%% -------- QUANDO FAREMO PIU' LIVELLI-----------
 % For recognizing a complex shape $D$ in an image $\I$, we concentrate on complex
 % shapes made of basic components only. This is without loss of
 % generality, since every complex shape can be
 % transformed into a complex shape whose components are basic ones,
 % just composing the transformations.
 % \begin{proposition}
 %         For every complex shape $C$, there exists an equivalent complex shape $C'$ such
 %         that the components of $C'$ are only basic ones.
 % \end{proposition}
 % where equivalence is considered \wrt  the semantics given. For
 % example,
 % \begin{eqnarray*}
 % \SOME{R_{1},\tau_{1}}{ (\SOME{R_{2},\tau_{2},c_{2}}{B2} \AND
 % \SOME{R_{3},\tau_{3},c_{3}}{B3})} \equiv \\
 % \SOME{(R_{1}R_{2}),(\tau_{1}\circ\tau_{2}),c_{2}}{B2} \AND
 % \SOME{(R_{1}R_{3}),(\tau_{1}\circ\tau_{3}),c_{3}}{B3})
 % \end{eqnarray*}
 % Based on the above property, we may assume that $D$ is always
 % formed by basic components.
 %
 %%
Our concern is how to decide whether there exists a transformation
$\tau$ and a matching $j$ having the properties stated in
Theorem~\ref{thm-recognition}.  It turns out that for exact
recognition, a quadratic upper bound can be attained for the
possible transformations to try.

\begin{theorem}\label{thm:only:m:m-1:groups}
    Let $C=\twocomponent{\tau_{1}}{B_{1}}\AND \cdots \AND
    \twocomponent{\tau_{n}}{B_{n}}$ be a composite shape description, and
    let $I$ be an image, segmented into regions $\{\dd{r}{m}{,}\}$.  Then,
    there are at most $m(m-1)$ 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.
\end{theorem}

\proof{ A transformation $\tau$ 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 $\tau$. Now $\tau$ 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 $\tau$ exists between the centroids of
the basic components and the centroids of some of the regions,
then $\tau$ 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
$\textbf{p}_{1}$, $\textbf{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 $\textbf{v}_{j(1)}$,
$\textbf{v}_{j(2)}$, denote their centroids. There is only one
transformation $\tau$ solving the point equations (each one
mapping a point into another)
%
\[\left\{\begin{array}{ccc}
\tau(\tau_{1}(\textbf{p}_{1})) & = &
\textbf{v}_{j(1)}\\
\tau(\tau_{2}(\textbf{p}_{2})) & = & \textbf{v}_{j(2)}
\end{array}
\right.\] Hence, there are only $m(m-1)$ such transformations.
For the second claim, once a $\tau$ matching the centroids is
found, one checks that the \emph{edge contours} of basic
components and regions coincide, \ie that
$\tau(\tau_{1}(e(B_{1}))) = e(r_{j(1)})$,
$\tau(\tau_{2}(e(B_{2}))) = e(r_{j(2)})$, and for $k=3,\ldots,n$
that $\tau(\tau_{k}(e(B_{k}))$ coincides with the contour of some
region $e(r_{j(k)})$.

Recalling Formula~(\ref{eqn:tau:mapping:exact})  in the proof of
Theorem~\ref{thm-recognition}, this means that we can eliminate
the outer quantifier in (\ref{eqn:tau:mapping:exact}) using a
computed $\tau$, and conclude that $C$ is recognized in $I$ iff:
\[
\exists j:\{1..n\} \rightarrow \{1..m\} \bigwedge_{i=1}^n
e(r_{j(i)})=\tau(\tau_{i}(e(B_{i})))
\]
} % fine della dimostrazione

Observe that, to prune the above search, once a $\tau$ has been
found as above, one can check for $k=3,\ldots,n$ that
$\tau(\tau_{k}(\centr{B_{k}}))$ coincides with a centroid of some
region $r_{j}$, before checking contours.

Based on Theorem~\ref{thm:only:m:m-1:groups}, we can devise the
following algorithm:
\begin{tabbing}
    \textbf{Algorithm} Recognize ($C$,$I$);\\
    \textbf{input} \= a composite shape description
    $C=\twocomponent{\tau_{1}}{B_{1}}\AND \cdots \AND
    \twocomponent{\tau_{n}}{B_{n}}$, and\\
    \> an image $I$, segmented into regions $\dd{r}{m}{,}$\\
    \textbf{output} True if $C$ is recognized in $I$, False otherwise\\
    \textbf{beg}\=\textbf{in}\\
    (1)\>   compute the centroids $\dd{\textbf{v}}{m}{,}$ of $\dd{r}{m}{,}$\\
    (2)\>   compute the centroids $\dd{\textbf{p}}{n}{,}$ of the
    components of $C$\\
    (3)\>   \textbf{for} \= $i,h \in \{1,\ldots,m \}$ with $i < h$ \textbf{do}\\
    \+\+\kill
        compute the transformation $\tau$ such that
            $\tau(\textbf{p}_{1})=\textbf{v}_{i}$ and
             $\tau(\textbf{p}_{2})=\textbf{v}_{h}$;\\
       \textbf{if} \= \textbf{for every} $k \in \{1,\ldots,n\}$ \\
         \> $\tau(\tau_{k}(e(B_{k})))$ coincides (for some $j$) with a region
         $r_{j}$ in $I$\\
        \textbf{then return} True\\
        \-\kill
        \textbf{endfor}\\
    \textbf{return} False\\
    \-\kill
    \textbf{end}
\end{tabbing}

The correctness of Recognize ($C$,$I$) follows directly from
Theorems~\ref{thm-recognition} and~\ref{thm:only:m:m-1:groups}.
Regarding the time complexity, step (1) requires to compute
centroids of segmented regions.  Several methods for computing
centroids are well known in the literature \cite{handbook-pr}.
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})$.

\begin{theorem}
    Let $C=\twocomponent{\tau_{1}}{B_{1}}\AND \cdots \AND
    \twocomponent{\tau_{n}}{B_{n}}$ be a composite shape description, and
    let $I$ be an image with $N_{h}\times N_{v}$ pixels, segmented into
    regions $\{\dd{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\cdot f(N_{h},N_{v})+n+m^{2}\cdot n
    \cdot N_{h} \cdot N_{v})$.
\end{theorem}
\proof{From the assumptions, Step (1) can be performed in time
$O(m\cdot f(N_{h},N_{v}))$.  Instead, Step (2) can be accomplished
by extracting the $n$ translation vectors from the transformations
$\dd{\tau}{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} \cdot N_{v})$, using a suitable
marking of pixels in $I$ with the region they belong to.  Hence,
we obtain the claim.
} % fine dimostrazione

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 feature-level image processing.

\newtheorem{corollary}{Corollary}[theorem]

%\begin{corollary}
%    Let $C$ and $D$ be two composite shape descriptions, with $n$ and $m$
%    components respectively, and let $I(D)$ be an image with $N_{h}\times
%    N_{v}$ pixels.  Then, subsumption between $C$ and $D$ can be decided
%    in $O(m^{2}\cdot n\cdot N_{h} \cdot N_{v})$.
%\end{corollary}


\subsection{Approximate Recognition}\label{subsec:algo-approx}
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~\ref{thm-recognition}, and  in particular the
matrix of equalities~(\ref{matrix:exact}). Using the semantics for
approximate recognition~(\ref{composite-fuzzy-int}), the expanded
formula for evaluating $\Int{C}(I)$ becomes now the following:
\[
\max_{\tau} \min \left\{ \begin{array}{cccc}
                      \max \{sim(e(r_{1}),\tau(\tau_{1}(e(B_{1})))) , &
                      \ldots, &
                      sim(e(r_{m}),\tau(\tau_{1}(e(B_{1}))))) &
                      \}   \\
              \vdots  & \vdots  & \vdots &  \\
                      \max \{sim(e(r_{1}),\tau(\tau_{n}(e(B_{n}))) , & \ldots, &
                      sim(e(r_{m}),\tau(\tau_{n}(e(B_{n})))) & \}
          \end{array}\right\}
\]
Now Properties 1--2 stated for exact recognition can be
reformulated as hypotheses about $sim$, as follows.
\begin{enumerate}
    \item For a given transformation, we assume that at most one region
    among $\dd{r}{m}{,}$ is maximally similar to each component.  This
    assumption can be justified by supposing its negation: if there are
    two regions both maximally similar to a component, then this maximal
    value should be a very low one, lowering the overall value because of the
    external minimization.  This means that in maximizing each row, we can
    assume that the maximal value is given by one index among
    $1,\ldots,m$.

    \item For a given transformation, we assume that a region can yield a
    maximal similarity for at most one component.  Again, the rationale of
    this assumption is that when a region yields a maximal similarity with
    two components in two different rows, this value can be only a low
    one, which propagates along the overall minimum.  This means that in
    minimizing the maxima from all rows, we can consider a different
    region in each row.

\end{enumerate}
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
\[
\max_{\tau} \max_{j:\{1..n\} \rightarrow \{1..m\}} \min_{i=1}^n\{
sim( e(r_{j(i)}),\tau(\tau_{i}(e(B_{i}))) ) \}
\]
The choices of $\tau$ and $j$ for the two maxima are independent,
hence we can consider groups of regions first:
\begin{equation}
   \max_{j:\{1..n\} \rightarrow \{1..m\}} \max_{\tau}
   \min_{i=1}^n\{ sim( e(r_{j(i)}),\tau(\tau_{i}(e(B_{i}))) ) \}
   \label{groups-first-approx}
\end{equation}
Differently from the exact recognition, the choice of an injective
mapping $j$ does not directly lead to a transformation $\tau$,
since now $\tau$ depends on how the similarity of transformed
shapes is computed, that is, the choice of $\tau$ 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,\fourcomponent{c}{t}{\tau}{B})$ be a similarity measure
that takes a region $r$ (with its color $c(r)$ and texture $t(r)$)
and a component $\fourcomponent{c}{t}{\tau}{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 1--2 above. Accordingly,
Formula~(\ref{groups-first-approx}) becomes
\begin{equation}
    \max_{j:\{1..n\} \rightarrow \{1..m\}} \max_{\tau}
    \min_{i=1}^n\{
    sim(r_{j(i)},\fourcomponent{c}{t}{(\tau\circ\tau_{i})}{B_{i}} )
    \}
    \label{eqn-approx-recognition-complete}
\end{equation}
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 \cite{gudi-99} 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.

\vskip 1\baselineskip In spite of the assumptions made, finding an
algorithm for computing the ``best" $\tau$ in
Formula~(\ref{eqn-approx-recognition-complete}) proved for us a
difficult task.  The problem is that there is a continuous
spectrum of $\tau$ to be searched, and that the best $\tau$ 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
\citeA{card-schu-98} solve the nearly-exact point matching with
efficient randomized methods, but without scaling.  They also
observe that best match is a more difficult problem than
nearly-exact match. Also \citeA{chew-etal-97} 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,\fourcomponent{c}{t}{\tau}{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 (rotation-translation-scale
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~(\ref{eqn-approx-recognition-complete}); 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),\tau(e(B))$
represents how similar in scale are the region and the transformed
component, while $sim_{rotation}(e(r),\tau(e(B))$ denotes how
$e(r)$ and $\tau(e(B)$ are similarly (or not) rotated \wrt\ the
arrangement of the other components.  Finally,
$sim_{spatial}(e(r),\tau(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:
\begin{eqnarray*}
    sim(r,\fourcomponent{c}{t}{\tau}{B}) & = &
                             sim_{spatial}(e(r),\tau(e(B))\cdot\alpha + \\
                     & &     sim_{shape}(e(r),e(B)) \cdot\beta + \\
                     & &     sim_{color}(c(r),c) \cdot\gamma +\\
                      & &     sim_{rotation}(e(r),\tau(e(B)) \cdot\delta + \\
                    & &     sim_{scale}(e(r),\tau(e(B))\cdot\eta + \\
                     & &     sim_{texture}(t(r),t) \cdot\epsilon
\end{eqnarray*}
where coefficients $ \alpha, \beta, \gamma, \delta,\eta, \epsilon
$ weight the relevance each feature has in the overall similarity
computation.  Obviously, we impose $ \alpha + \beta + \gamma +
\delta + \eta + \epsilon = 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
\ref{table:parameters} in Section~\ref{sec:experi}.

Because of the difficulties in computing the best $\tau$, we do
not compute a maximum over all possible $\tau$'s.  Instead, we
evaluate whether there \emph{can be} a rigid transformation with
scaling from $\tau_{1}(e(B_{1})),\ldots,\tau_{n}(e(B_{n}))$ into
$r_{j(1)},\ldots,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~(\ref{eqn-approx-recognition-complete}) we evaluate the
following simpler formula:
\begin{equation}
    \max_{j:\{1..n\} \rightarrow \{1..m\}}
    \min_{i=1}^n\{ sim( r_{j(i)},\fourcomponent{c}{t}{\tau_{i}}{B_{i}} )
    \}
    \label{eq:approx-recognition-without-tau}
\end{equation}
interpreting pose similarities in a different way. We now describe
in detail how we estimate pose similarities.

Let $C = \fourcomponent{c_{1}}{t_{1}}{\tau_{1}}{B_{1}}) \AND
\cdots \AND \fourcomponent{c_{n}}{t_{n}}{\tau_{n}}{B_{n}})$, and
let $j$ be an injective function from $\{1..n\}$ into $\{1..m\}$,
that matches components with regions $\{r_{j(1)},\ldots,r_{j(n)}
\}$ respectively.

\subsubsection{Spatial Similarity}

For a given component --- say, component 1 --- we compute all
angles under which the other components are seen from 1.
Formally, let $\alpha_{\widehat{i1h}}$ be the
counter-clockwise-oriented 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(n-1)/2$ such
angles.

Then, we compute the correspondent angles for region $r_{j(1)}$,
namely, angles $\beta_{\widehat{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~\ref{fig:spatial}.

%\begin{figure}
%  \vspace{8.97cm}
%  \begin{center}
%   %\hspace{2cm}
%     \special{bmp:image5.bmp x=13cm y=8.97cm}
%     \caption{Representation of angles used for computing spatial similarity of component 1
%     and region $r_{j(1)}$.
%     {\label{fig:spatial}}}
%   \end{center}
%\end{figure}[bb=14 13 581 829]

\begin{figure}
\centerline{\scalebox{.7}{\includegraphics[bb=13 407 581
790]{spatial.eps}}} \caption{Representation of angles used for
computing spatial similarity of component 1
     and region $r_{j(1)}$. \label{fig:spatial}}
\end{figure}


%
Then we let the difference
$\Delta_{spatial}(e(r_{j(1)}),\tau_{1}(e(B_{1}))$ be the maximal
absolute difference between correspondent angles:
\[
\Delta_{spatial}(e(r_{j(1)}),\tau_{1}(e(B_{1})) =
   \max_{i,h = 2,\ldots,n, i\neq h} \{ | \alpha_{\widehat{i1h}} -
   \beta_{\widehat{j(i)j(1)j(h)}} |  \}
\]
We compute an analogous measure for components 2,\ldots,$n$, and
then we select the maximum of such differences:
\begin{equation}
   \Delta_{spatial}[j] = \max_{i=1}^n \{
   \Delta_{spatial}(e(r_{j(i)}),\tau_{i}(e(B_{i}))\}
   \label{delta-spatial}
\end{equation}
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 $\Phi$ described in the Appendix. This minimal
similarity is then assigned to every
$sim_{spatial}(e(r_{j(i)}),\tau_{i}(e(B_{i}))$, for
$i=1,\ldots,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 \wrt\ the other arrangement, the higher
its maximum difference. The reason why we use the maximum of all
differences as similarity for each pair component-region will be
clear when we prove later that this measure obeys Downward
Refinement property.

\subsubsection{Rotation Similarity}

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
$\tau_{1}$. Let $\vec{h}$ denote such a rotated vector. For
$i=2,\ldots,n$ let $\gamma_{\widehat{i1\vec{h}}}$ the
counter-clockwise-oriented angle with vertex in the centroid of
component 1, and formed by $\vec{h}$ and the line linking the
centroid of component 1 with the centroid of component $i$.

For region $r_{j(1)}$, the analogous $\vec{u}$ of $\vec{h}$ can be
constructed by finding the rotation phase for which
cross-correlation attains a maximum value (see Appendix).  Then,
for $i=2,\ldots,n$ let $\delta_{\widehat{j(i)j(1)\vec{u}}}$ be the
angles with vertex in the centroid of $r_{j(1)}$, and formed by
$\vec{u}$ and the line linking the centroid of $r_{j(1)}$ with the
centroid of $r_{j(i)}$. Figure~\ref{fig:rotation} clarifies the
angles we are computing.
%\begin{figure}
%  \vspace{5.66cm}
%  \begin{center}
   %\hspace{2cm}
%     \special{bmp:rot1.bmp x=13cm y=5.66cm}
%     \caption{Representation of angles used for computing rotation
%     similarity of component 1
%     and region $r_{j(1)}$.
%     {\label{fig:rotation}}}
%   \end{center}
%\end{figure}14 13 581 829

\begin{figure}
\centerline{\scalebox{.7}{\includegraphics[bb=13 580 581
820]{rot.eps}}} \caption{Representation of angles used for
computing rotation similarity of component 1 and region
$r_{j(1)}$.  \label{fig:rotation}}
\end{figure}

%\begin{figure}
%\centerline{\scalebox{.6}\includegraphics[bb=13 580 581
%829]{rot.eps}} \caption{Representation of angles used for
%computing rotation similarity of component 1 and region
%$r_{j(1)}$. \label{fig:rotation}}
%\end{figure}


%\begin{figure}
%  \vspace{8cm}
%  \begin{center}
  %\hspace{2cm}
%   \special{eps:rot1.eps x=13cm y=5.66cm}
%     \caption{Representation of angles used for computing rotation
%     similarity of component 1
%     and region $r_{j(1)}$.
%     {\label{fig:rotation}}}
%   \end{center}
%\end{figure}


Then we let the difference
$\Delta_{rotation}(e(r_{j(1)}),\tau_{1}(e(B_{1}))$ be the maximal
absolute difference between correspondent angles:
\[
\Delta_{rotation}(e(r_{j(1)}),\tau_{1}(e(B_{1})) =
   \max_{i= 2,\ldots,n} \{ | \gamma_{\widehat{i1\vec{h}}} -
   \delta_{\widehat{j(i)j(1)\vec{u}}} |  \}
\]
If there is more than one orientation of $r_{j(1)}$ for which
cross-correlation yields a maximum --- \eg 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:
\begin{equation}
   \Delta_{rotation}[j] = \max_{i=1}^n \{
   \Delta_{rotation}(e(r_{j(i)}),\tau_{i}(e(B_{i}))\}
   \label{delta-rotation}
\end{equation}

Finally, as for spatial similarity, we transform
$\Delta_{rotation}[j]$ into a minimal similarity with the help of
$\Phi$.  This minimal similarity is then assigned to every
$sim_{rotation}(e(r_{j(i)}),\tau_{i}(e(B_{i}))$, for
$i=1,\ldots,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 \wrt 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.


\subsubsection{Scale Similarity}
We concentrate again on component 1 to ease the presentation.  Let
$m_{1}$ be the \emph{size} of component 1, computed as the mean
distance between its centroid and points on the contour.
Moreover, for $i=2,\ldots,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~\ref{fig:scale} pictures the quantities
we are computing.
%\begin{figure}
%  \vspace{6.42cm}
%  \begin{center}
   %\hspace{2cm}
%     \special{bmp:scala1.bmp x=13cm y=6.42cm}
%     \caption{Sizes and distances for scale similarity computation of component 1
%     and region $r_{j(1)}$.
%     {\label{fig:scale}}}
%   \end{center}
%\end{figure}

%\begin{figure}
%\centerline{\scalebox{.6}\includegraphics[bb=13 550 581
%820]{scala.eps}} \caption{Sizes and distances for scale similarity
%computation of component 1
%     and region $r_{j(1)}$. \label{fig:scale}}
%\end{figure}

\begin{figure}
\centerline{\scalebox{.8}{\includegraphics[bb=50 550 581
790]{scala.eps}}} \caption{Sizes and distances for scale
similarity computation of component 1
     and region $r_{j(1)}$.  \label{fig:scale}}
\end{figure}

We define the difference in scale between $e(r_{j(1)})$ and
$\tau_{1}(e(B_{1})$ as:
\[
\Delta_{scale}(e(r_{j(1)}),\tau_{1}(e(B_{1})) =
   \max_{i= 2,\ldots,n} \left\{ \left| 1 -
   \frac{\min\{ M_{j(1)}/D_{j(1)j(i)} , m_{1}/d_{1i}\}}%
   {\max\{ M_{j(1)}/D_{j(1)j(i)} , m_{1}/d_{1i}\}} \right|  \right\}
\]
We repeat the process for components 2 to $n$, and we select the
maximum of such differences:
\begin{equation}
   \Delta_{scale}[j] = \max_{i=1}^n \{
   \Delta_{scale}(e(r_{j(i)}),\tau_{i}(e(B_{i}))\}
   \label{delta-scale}
\end{equation}

Finally, as for the other similarities, we transform
$\Delta_{scale}[j]$ into a minimal similarity with the help of
$\Phi$.  This minimal similarity is then assigned to every
$sim_{scale}(e(r_{j(i)}),\tau_{i}(e(B_{i}))$, for $i=1,\ldots,n$.

\subsubsection{Discussion of Pose Similarities}

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.

\begin{theorem}
    \label{thm:down:approx}
    Let $C$ be a composite shape description, and let $D$ be a refinement
    of $C$, that is, $D \doteq C \AND \fourcomponent{c'}{t'}{\tau'}{B'}$.
    For every image $I$, segmented into regions $\dd{r}{m}{,}$, if
    $\Int{C}(I)$ and $\Int{D}(I)$ are computed as
    in~(\ref{eq:approx-recognition-without-tau}) using similarities
    defined above, then it holds $\Int D(I) \le \Int C(I)$.
\end{theorem}
%
\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)
\in \{1,\ldots,m \}$ be a suitable region index not in the range
of $j$. Since $\Int D(I)$ is computed over such extended mappings,
it is sufficient to show that values computed in
Formula~(\ref{eq:approx-recognition-without-tau}) do not increase
\wrt the values computed for $C$.

Let $j_{1}$ be the mapping for which the maximum value $\Int C(I)$
is reached.  Every extension $j_{1}'$ of $j_{1}$ leads to a
minimum value $\min_{i=1}^{n+1}$ in
Formula~(\ref{eq:approx-recognition-without-tau}) which is lower
than $\Int C(I)$.  In fact, all pose differences
(\ref{delta-spatial}), (\ref{delta-rotation}),
(\ref{delta-scale}), 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
non-maximum value $v_{2} < \Int C(I)$ in
Formula~(\ref{eq:approx-recognition-without-tau}).  Using the
above argument about pose differences (\ref{delta-spatial}),
(\ref{delta-rotation}), (\ref{delta-scale}), every extension
$j_{2}'$ leads to a minimum value $v_{2}' \le v_{2}$.  Since
$v_{2} < \Int C(I)$, also every extension of every mapping $j$
different from $j_{1}$ yields a value which is less than $\Int
C(I)$. This completes the proof.
} % fine dimostrazione



\section{A Prototype System}\label{sec:prototype}
In order to substantiate our ideas we have developed a prototype
system, written in C++. The system is a client-server application
working in a MS-Windows  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
\ref{fig:client-server}. It is made up of three main modules:
sketch, communication and configuration.
%\begin{figure}
%\vspace{16.3cm}
%%\hspace{2cm}
%\special{bmp:server.bmp x=12cm y=16.3cm}
%\caption{Architecture of the prototype system.
%{\label{fig:client-server}}}
%\end{figure}

\begin{figure}
\centerline{\includegraphics[width=6.0in]{server.eps}}
\caption{Architecture of the prototype system.
\label{fig:client-server}}
\end{figure}


The communication module manages the communication with the server
side, using a simple application-level 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.

%\begin{figure}
%\vspace{9cm}
%%\hspace{2cm}
%\special{bmp:oggetti.bmp x=15cm y=9cm}
%\caption{The process of reclassification of images when a new
%description is inserted:
%a) before insertion of description (No. 9); b) after insertion.
%{\label{fig:grafo}}}
%\end{figure}

\begin{figure}
\centerline{\includegraphics[width=6.0in]{oggetti.eps}}
\caption{The process of reclassification of images when a new
description is inserted: a) before insertion of description (No.
9); b) after insertion.
 \label{fig:grafo}}
\end{figure}


The system keeps 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.
%\begin{center}
%\begin{figure}
%\vspace{8cm}
%\special{bmp:qruote.bmp x=12cm y=8cm}
%\caption{A query and the retrieved set of images.{\label{fig:car}}}
%\end{figure}
%\end{center}
%
\begin{figure}
\centerline{\includegraphics[width=5.9in]{qruote.eps}} \caption{A
query and the retrieved set of images.
 \label{fig:car}}
\end{figure}

%\begin{center}
%\begin{figure}
%\vspace{8cm}
%%\hspace{2cm}
%\special{bmp:qmacch.bmp x=12cm y=8cm}
%\caption{Downward refinement (contd.): A more detailed query,
%picturing a car,
%and the retrieved set of images.{\label{fig:macchina}}}
%\end{figure}
%\end{center}

The server side, which is also shown in
Figure~\ref{fig:client-server}, is composed by concurrent threads
that manage the server-side 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:

\begin{enumerate}
\item the image features extractor that contains an image
segmentation module and a region data extraction one; \item the
image classifier that is composed by a classifier module and a
module used in the image reclassification; \item the database
management system.
\end{enumerate}

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~\ref{fig:grafo}.

\begin{figure}
\centerline{\includegraphics[width=5.9in]{qmacch.eps}}
\caption{Downward refinement (contd.): A more detailed query,
picturing a car, and the retrieved set of images.
 \label{fig:macchina}}
\end{figure}


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 keeps 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~\ref{fig:car} 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.
%
%\begin{center}
%\begin{figure}
%\vspace{17.2cm}
%%\hspace{2cm}
%\special{bmp:image6.bmp x=13cm y=17.2cm}
%\caption{A Subsumption example: increasing the number of objects in
%the query leads to a correct reduction in the retrieved set.
%{\label{fig:image6}}}
%\end{figure}
%\end{center}

\begin{figure}
\centerline{\includegraphics[width=6.0in]{image6.eps}} \caption{A
Subsumption example: increasing the number of objects in the query
leads to a correct reduction in the retrieved set.
\label{fig:image6}}
\end{figure}


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~\ref{fig:macchina}. 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, \eg using the sketch
in Figure~\ref{fig:macchina}, 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.
%\begin{center}
%\begin{figure}
%\vspace{12cm}
%%\hspace{2cm}
%\special{bmp:query27.bmp x=12cm y=9.1cm}
%\caption{A query by example and retrieved images.
%{\label{fig:forbici}}}
%\end{figure}
%\end{center}


Subsumption is another distinguishing feature of our system.
Figure \ref{fig:image6} shows  queries composed of basic shapes
that have been obtained by segmentation of an image picturing
aircrafts, \ie 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
\citeA{gudi-ragh-95} and \citeA{gudi-99}. 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 B2-Spirit) in the
second image of Figure \ref{fig:image6}-b), 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~\ref{fig:forbici}.
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.

\begin{figure}
\centerline{\includegraphics[width=5.9in]{query27.eps}} \caption{A
query by example and retrieved images. \label{fig:forbici}}
\end{figure}



\section{Experiments and Results}\label{sec:experi}
%
%\begin{center}
%\begin{figure}
%\vspace{9.37cm}
%%\hspace{2cm}
%\special{bmp:sample.bmp x=10cm y=9.375cm}
%\caption{A sample of the images used in the experiments.
%{\label{fig:sample}}}
%\end{figure}
%\end{center}
%

\begin{figure}
\centerline{\includegraphics[width=6.0in]{sample.eps}} \caption{A
sample of the images used in the experiments. \label{fig:sample}}
\end{figure}%


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
\citeA{gudi-ragh-95}. 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~\ref{fig:sample}, while the complete
set is available at URL:
\begin{quote}
http://www-ictserv.poliba.it/disciascio/jair\_images.htm.
\end{quote}

Images have been acquired using a digital camera, combining 18
objects, either simple objects (\ie a single shape) or composite
ones, of variable size and color. All images had size 1080
${\times}$ 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, \eg 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~\ref{table:example}. Notice that images grouped
together in the same cell have been given the same relevance.
%
\begin{table}
\tiny
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}\hline
{user} & \multicolumn{5}{c|} {ranking} \\ \hline
 & \textbf{1st} & \textbf{2nd} & \textbf{3rd} & \textbf{4th} &
\textbf{5th} \\ \hline 1& 1 & 44, 88 & 2, 3, 68, 80 & 26 & 24 \\
\hline 2& 1 & 44, 88 & 3, 68, 80 & 2, 26 &     \\ \hline 3& 1 &
44, 88 & 3, 68, 80 & 2, 26 &     \\ \hline 4& 1 & 44, 88 & 2, 3,
68, 80 & 26 & 24 \\ \hline 5& 1 & 44, 88 & 2, 3, 68, 80 & 24 26 &
\\ \hline \textbf{final}& 1 & 44, 88 & 3, 68, 80 & 2, 26 & \\
\hline
\end{tabular}
\normalsize \caption{Users rankings for query $nr.$1}
\label{table:example}
\end{center}
\end{table}
%
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 \ref{table:parameters}. The
parameters reported here are described in the Appendix. Notice
that, dealing with well-defined objects, we gave an  higher
relevance to shape and spatial features and a reduced relevance to
scale, rotation, color and texture.
%
\begin{table}
\begin{center}
\tiny
\begin{tabular}{|l|c|}\hline
%
\textbf{Parameter}              &   \textbf{Value}  \\ \hline
Fourier descriptors threshold               &       0.98    \\
\hline Circular symmetry threshold             &       0.99    \\
\hline
Spatial similarity threshold                &       0.30    \\
Symmetry maxima threshold           &       0.10    \\ \hline
Spatial similarity weight $ \alpha $        &           0.30    \\
Spatial similarity sensitivity $f{x}$       &       90.0    \\
spatial similarity sensitivity $f{y}$       &       0.40    \\
\hline
shape similarity weight $\beta$             &       0.30    \\
shape similarity sensitivity $f{x}$     &       0.005   \\
shape similarity sensitivity $f{y}$     &       0.20    \\ \hline
color similarity weight $\gamma$            &       0.11    \\
color similarity sensitivity $f{x}$     &       110.0   \\
color similarity sensitivity $f{y}$     &       0.40    \\ \hline
rotation similarity weight $\delta$         &       0.11    \\
rotation similarity sensitivity $f{x}$      &       90.0    \\
rotation similarity sensitivity $f{y}$      &       0.40    \\
\hline
texture similarity weight $\epsilon$        &       0.07    \\
texture similarity sensitivity $f{x}$   &       110.0   \\
texture similarity sensitivity $f{y}$   &       0.40    \\ \hline
scale similarity weight $\eta$              &       0.11    \\
scale similarity sensitivity $f{x}$     &       0.50    \\
scale similarity sensitivity $f{y}$     &       0.40    \\ \hline
global similarity threshold                 &       0.70    \\
\hline
%
\end{tabular}
\normalsize \caption{Configuration parameters, grouped by feature
type.} \label{table:parameters}
\end{center}
\end{table}

The resulting classification gave us what was called a
system-provided ranking. We then adopted the $R_{norm}$ as quality
measure of the retrieval effectiveness. $R_{norm}$ has been first
introduced in the LIVE-Project \cite{Bollmann-85} 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.
% terza figura
To make the paper self-contained we recall here how $R_{norm}$ is
defined.

Let $G$ be a finite set of images with a user-defined preference
relation $\geq$ that is complete and transitive. Let
$\Delta^{usr}$ be the rank ordering of $G$ induced by the user
preference relation. Also, let $\Delta^{sys}$  be  a
system-provided ranking.
% some rank ordering of $G$ induced by the
% similarity values computed by the image retrieval system.
 The formulation of $R_{norm}$ is:
\[
R_{norm}(\Delta^{sys})=
\frac{1}{2}\cdot(1+\frac{S^{+}-S^{-}}{S_{max}^{+}})
\]
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 $\Delta^{sys}$
relative to the ranking of corresponding image pairs in
$\Delta^{usr}$.

$R_{norm}$ values are in the range [0,1]; a value of 1 corresponds
to a system-provided 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~\ref{table:rnorm} 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).
%
\begin{table}
\begin{center}
\tiny
\begin{tabular}{|c|c|c|}\hline
\textbf{Query $nr.$} & \textbf{Image $nr.$}       &
\textbf{$R_{norm}$} \\ \hline
\dag1   &   1   &   0.92    \\
\dag2   &   2   &   0.92    \\
\dag3   &   3   &   0.93    \\
\dag4   &   4   &   0.95    \\
\dag5   &   5   &   0.99    \\
\dag6   &   6   &   0.94    \\
\dag7   &   7   &   0.93    \\
\dag8   &   10  &   0.93    \\
\dag9   &   11  &   0.95    \\
\dag10  &   12  &   0.74    \\
\dag11  &   13  &   0.60    \\
\dag12  &   14  &   0.84    \\
\dag13  &   15  &   0.83    \\
\dag14  &   18  &   0.99    \\
\dag15  &   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    \\
\dag27  &   41  &   0.93    \\
28  &   42  &   0.98    \\
29  &   50  &   1.00    \\
\dag30  &   78  &   0.88    \\
\dag31  &   79  &   1.00    \\
\textbf{Average $R_{norm}$} &   &   \textbf{0.92}   \\ \hline
\end{tabular}
\normalsize \caption{$R_{norm}$ values. \textit{(\dag indicates
single-object queries)}} \label{table:rnorm}
\end{center}
\end{table}
%

As a comparison, the average $R_{norm}$ resulted 0.98 in the
system  presented by \citeA{gudi-ragh-95}, 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
\cite{gudi-99}. 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~\ref{fig:sim13} 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 sugar-drop with
a wrist-watch, which resulted in a false positive. As a matter of
fact in various images the sweet-drops 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 sugar-drop, and
gave a lower ranking to images (with sugar-drops) 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.
%

%\begin{center}
%\begin{figure}
%\vspace{9.1cm}
%%\hspace{2cm}
%\special{bmp:sim13.bmp x=12cm y=9.1cm}
%\caption{Query results for query 11, which had the lowest
%$R_{norm}$=0.60. {\label{fig:sim13}}}
%\end{figure}
%\end{center}

\begin{figure}
\centerline{\includegraphics[width=6.0in]{sim13.eps}}
\caption{Query results for query 11, which had the lowest
$R_{norm}$=0.60. \label{fig:sim13}}
\end{figure}



\section{Conclusion}\label{sec:conclusion}
%\hoffset=0in  %creates a left margin of 0in (1in+(-1.5in))
%\setlength{\oddsidemargin}{.8in}
We proposed a Knowledge Representation approach to Image
Retrieval. We started from the observation that current
sketch-based 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 (translation-rotation-scale), 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 (\ie 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 \wrt 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 polynomial-time 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 state-of-the-art 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 logic-oriented
connectives --- \eg 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, large-scale experiments might prove useful in
understanding the relative importance attributed by end users to
the various features of a composite shape.
\hoffset=0in  %creates a left margin of 0in (1in+(-1.5in))

\subsection*{Acknowledgements}
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, ex-MURST)
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".



\appendix\label{sec:appendix}
%\section{}
%\newcommand{\treincolonna}[3]{\begin{array}{c} {#1}\\ {#2}\\ {#3}
%\end{array}}
%\newcommand{\treincolonna}[3]{#2_{#3}^{#1}}

\section{}

In this appendix we briefly revise the methods we used for the
extraction of image features.  We also describe the smoothing
function $\Phi$ and the way we compute similarity for the image
features that were introduced in Section~\ref{subsec:algo-approx}.

\subsection{Extraction of Image Features}

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
self-contained we start defining a  generic color image as
 $\{ \overrightarrow {I}(x,y)  ~|~ 1\leq x\leq N_{h} , 1\leq y\leq N_{v}\}$,
where $N_{h}$, $N_{v}$ are the horizontal and vertical dimensions,
respectively, and $\overrightarrow {I}(x,y)$ is a three-components
tuple $(R,G,B)$. We assume that the image $I$ has been partitioned
in $m$ regions $(r_{i}), i=1,\ldots,m $ satisfying the following
properties:
\begin{itemize}
    \item  $I= \bigcup (r_{i}), i=1,2,\ldots,m$

    \item  $\forall$ $i$ $\in \{1,2,\ldots,m \}$, $r_{i}$ is a nonempty and
connected set

    \item  $r_{i}\cap  r_{j} = \emptyset$  iff $i \neq j$

    \item  each region satisfies heuristic and physical requirements.
\end{itemize}

We characterize each region $r_{i}$ with the following attributes:
shape, position, size, orientation, color and texture.

\emph{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,\ldots, N_{b}$, with $N_{b}$ the number of boundary
sample points.  Following the approach proposed by \citeA{Rui-96}
we define the Discrete Fourier Transform (DFT) of $z(t)$ as:
\[
Z(k)= \sum_ {t=1}^{N_{b}} z(t)e^{ -j \frac{2 \pi
tk}{N_{b}}}=M(k)e^{j\theta (k)}
\]
with $k=1, \ldots, 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, non-uniform set
of points of the boundary as:
\[
z_{dense}(t)= \sum_{k=-N_c}^{N_{c}} Z(k)e^{ -j \frac{2 \pi
tk}{N_{b}}}
\]
with $t=1,\ldots, N_{dense}$.\

We then interpolate these samples to obtain uniformly spaced
samples $z_{unif}(t)$, $t=0,\ldots, N_{unif}$. We compute again
the FFT of $z_{unif}(t)$ obtaining Fourier coefficients
$Z_{unif}(k)$, $k= -N_{c},\ldots, N_c $. The shape-feature of a
region is hence characterized by a vector of $2N_{c}+1 $ complex
coefficients.

\emph{Position and Size.} Position is determined as the region
centroid computed via moment invariants \cite{Pratt}. Size is
computed as the mean distance between region centroid and points
on the contour.
%aid
%of moment invariants \cite{Pratt}. In order to simplify notation, let
%us assume
%that the extracted external contour of
%each region $r_{i}$, is placed in a new image $I_{r_{i}}$ having the
%same
%size of the original image, with a uniform background. Let us also
%suppose the new images be binarized, \ie discretized with two
%levels. The $(p,q)th$ spatial moment of each $I_{r_{i}}$ can be
%defined as:
%\[
%M_u(p,q)= \sum_{y=1}^{N_v } \sum_{x=1}^{N_{h}}
%x^{p}y^{q}I_{r_{i}}
%\]
% The  $(p,q)th$ scaled spatial moment can be defined as:
%$$M(p,q)=\frac{M_u(p,q)}{N_{v}^q N_{h}^p}$$
%
%The definition of size is just the zero moment
%$M(0,0)$.
%The position is obtained with reference to the region centroid,
%having coordinates:
%\[
%\overline{x}=\frac{M(1,0)}{M(0,0)} ~~~
%\overline{y}=\frac{M(0,1)}{M(0,0)}
%\]

\emph{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, \eg 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
cross-correlation:

\[
C(t)=\frac{1}{2N_{c}+1}\sum_{k=0}^{2N_{c}}Z_{B}(k)Z_{r_{i}}(k)\cdot
e^{j\frac{2\pi}{2N_{c}}kn} \mbox{ with } t \in 0,\ldots ,2N_{c}
\]

\emph{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:
\[
R_{r_{i}}= \sum_{p \in r_i} R(p) ~~~ G_{r_{i}}= \sum_{p \in r_i}
G(p) ~~~ B_{r_{i}}= \sum_{p \in r_i} B(p)
\]

\emph{Texture.} We extract texture information for each region
$r_{i}$ with a method based on the work by \citeA{Pok-99}.
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:
\[
h(x,y)=\frac{1}{2\pi\sigma^{2}}\cdot
e^{-\frac{x^{2}+y^{2}}{2\sigma^{2}}}\cdot e^{j2\pi(Ux+Vy)}
\]
%
where $(U,V)$ represents the filter location in the
frequency-domain, $\lambda$ is the central frequency, $\sigma$ is
the scale factor, and $\theta$ the orientation, defined as:
\[
\lambda=\sqrt{U^{2}+V^{2}} ~~~ \theta=\arctan{U/V}
\]


The processing allows to extract a 24-components feature vector,
which characterizes each textured region.

\subsection{Functions for Computing Similarities}

%
\textbf{Smoothing function $\Phi$.} In all similarity measures, we
use the function $\Phi(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$.

\[
\Phi(x,fx,fy)= \left\{
\begin{array}{ll}
    fy+(1-fy)\cdot\cos(\frac{\pi x}{2\cdot fx}) & \mbox{ if } 0\le x
    < fx  \\
    fy\cdot \left[ 1-\frac{\arctan[
              \frac{\pi\cdot(x-fx)\cdot(1-fy)}{fx\cdot fy}]}{\pi}
\right] &
          \mbox{ if } x > fx
\end{array}\right.
\]
where $fx > 0$ and $0 < fy < 1$.

\vskip 1\baselineskip


The input data to the approximate recognition algorithm are a
shape description $D$, containing $n$ components
$\fourcomponent{c_{k}}{t_{k}}{\tau_{k}}{B_{k}}$ and an image $I$
segmented into $m$ regions $\dd{r}{m}{,}$. The algorithm provides
a measure for the approximate recognition of $D$ in $I$.

The first step of the algorithm in Section
\ref{subsec:algo-approx} 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,\ldots,x_{2N_{c}})$ and
$Y=(y_1,\ldots,y_{2N_c})$

\[
sim_{ss}(B_k,r_i)=\frac{ \sum_ {l=1}^{2N_{c}} x_{l}y_{l}}
{\sqrt{\sum_ {l=1}^{2N_{c}} x_{l}^2 \times  \sum_ {l=1}^{2N_{c}}
y_{l}^2}}
\]

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

\[
sim_{shape}=\Phi(\max_{k=1}^{n}
\lbrack{1-sim_{ss}(B_{k},r_{j(k)})}\rbrack,fx_{shape},fy_{shape})
\]


%
\vskip 1\baselineskip \textbf{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, $\Delta_{color}(k).R$
denotes the difference in the red color component between the
$k$-th component of $D$ and the region $r_{j(k)}$, and similarly
for the green and the blue color components.

\[
\Delta_{color(k)}= \sqrt{\lbrack\Delta_{color}(k).R\rbrack^{2}+
\lbrack\Delta_{color}(k).G\rbrack^{2}+
\lbrack\Delta_{color}(k).B\rbrack^{2}}
\]

Then the function $\Phi$ takes the maximum of the differences to
obtain a similarity:

\[
sim_{color}=\Phi(\max_{k=1}^{n} \{ \Delta_{color}(k)
\},fx_{color},fy_{color})
\]

\vskip 1\baselineskip \textbf{Texture Similarity.} Finally,
$sim_{texture}$ measures the similarity between the texture
features in the components of $D$ and in the corresponding
regions.

$\Delta_{texture}(k)$ denotes the sum of differences in the
texture components between the $k$-th component of $D$ and the
region $r_{j(k)}$ and dividing by the standard deviation of the
elements.

\[
sim_{texture}=\Phi(\max_{k=1}^n\Delta_{texture}(k),fx_{texture},fy_{texture})
\]


\bibliographystyle{theapa}
%\bibliography{long,jair}
\begin{thebibliography}{}

\bibitem[\protect\BCAY{Aiello}{Aiello}{2001}]{aiello-01}
Aiello, M. \BBOP2001\BBCP.
\newblock \BBOQ Computing spatial similarity by games\BBCQ\
\newblock In Esposito, F.\BED, {\Bem Proceedings of the Eighth Conference of
  the Italian Association for Artificial Intelligence (AI*IA'99)},
  \lowercase{\BNUM}\ 2175 in Lecture Notes in Artificial Intelligence, \BPGS\
  99--110. Springer-Verlag.

\bibitem[\protect\BCAY{Ardizzone, Chella,\ \BBA\ Gaglio}{Ardizzone
  et~al.}{1997}]{ardi-97}
Ardizzone, E., Chella, A., \BBA\ Gaglio, S. \BBOP1997\BBCP.
\newblock \BBOQ Hybrid computation and reasoning for artificial vision\BBCQ\
\newblock In Cantoni, V., Levialdi, S., \BBA\ Roberto, V.\BEDS, {\Bem
  Artificial Vision}, \BPGS\ 193--221. Academic Press.

\bibitem[\protect\BCAY{Baader\ \BBA\ Hanschke}{Baader\ \BBA\
  Hanschke}{1991}]{baad-hans-91}
Baader, F.\BBACOMMA\  \BBA\ Hanschke, P. \BBOP1991\BBCP.
\newblock \BBOQ A schema for integrating concrete domains into concept
  languages\BBCQ\
\newblock In {\Bem Proceedings of the Twelfth International Joint Conference on
  Artificial Intelligence (IJCAI'91)}, \BPGS\ 452--457, Sydney.

\bibitem[\protect\BCAY{Bach, Fuller, Gupta, Hampapur, Horowitz, Humphrey,
  Jain,\ \BBA\ Shu}{Bach et~al.}{1996}]{Bach-96}
Bach, R., Fuller, C., Gupta, A., Hampapur, A., Horowitz, B.,
Humphrey, R., Jain,
  R., \BBA\ Shu, C. \BBOP1996\BBCP.
\newblock \BBOQ The {V}irage image search engine: an open framework for image
  management\BBCQ\
\newblock In {\Bem Storage and Retrieval for Image and Video Databases},
  \lowercase{\BVOL}\ 2670, \BPGS\ 76--87. SPIE.


\bibitem[\protect\BCAY{Bertino\ \BBA\ Catania}{Bertino\ \BBA\
  Catania}{1998}]{bert-cata-98}
Bertino, E.\BBACOMMA\  \BBA\ Catania, B. \BBOP1998\BBCP.
\newblock \BBOQ A constraint-based approach to shape management in multimedia
  databases\BBCQ\
\newblock {\Bem MultiMedia Systems}, {\Bem 6}, 2--16.

\bibitem[\protect\BCAY{Bollmann, Jochum, Reiner, Weissmann,\ \BBA\
  Zuse}{Bollmann et~al.}{1985}]{Bollmann-85}
Bollmann, P., Jochum, F., Reiner, U., Weissmann, V., \BBA\ Zuse,
H.
  \BBOP1985\BBCP.
\newblock \BBOQ The {LIVE-Project-Retrieval} experiments based on evaluation
  viewpoints\BBCQ\
\newblock In {\Bem Proceedings of the 8th Annual International ACM SIGIR
  Conference on Research and Developement in Information Retrieval (SIGIR
  '85)}, \BPGS\ 213--214. ACM, New York.

\bibitem[\protect\BCAY{Brooks}{Brooks}{1981}]{broo-81}
Brooks, R. \BBOP1981\BBCP.
\newblock \BBOQ Symbolic reasoning among {3-D} models and {2-D} images\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 17}, 285--348.

\bibitem[\protect\BCAY{Calvanese, Lenzerini,\ \BBA\ Nardi}{Calvanese
  et~al.}{1998}]{calv-lenz-nard-98}
Calvanese, D., Lenzerini, M., \BBA\ Nardi, D. \BBOP1998\BBCP.
\newblock \BBOQ Description logics for conceptual data modeling\BBCQ\
\newblock In Chomicki, J.\BBACOMMA\  \BBA\ Saake, G.\BEDS, {\Bem Logics for
  Databases and Information Systems}, \BPGS\ 229--264. Kluwer Academic
  Publisher.

\bibitem[\protect\BCAY{Cardoze\ \BBA\ Schulman}{Cardoze\ \BBA\
  Schulman}{1998}]{card-schu-98}
Cardoze, D.\BBACOMMA\  \BBA\ Schulman, L. \BBOP1998\BBCP.
\newblock \BBOQ Pattern matching for spatial point sets\BBCQ\
\newblock In {\Bem Proceedings of the Thirtyninth Annual Symposium on the
  Foundations of Computer Science (FOCS'98)}, \BPGS\ 156--165, Palo Alto, CA.

\bibitem[\protect\BCAY{Carson, Thomas, Belongie, Hellerstein,\ \BBA\
  Malik}{Carson et~al.}{1999}]{cars-99}
Carson, C., Thomas, M., Belongie, S., Hellerstein, J.~M., \BBA\
Malik, J.
  \BBOP1999\BBCP.
\newblock \BBOQ Blobworld: A system for region-based image indexing and
  retrieval\BBCQ\
\newblock In Huijsmans, D.\BBACOMMA\  \BBA\ Smeulders, A.\BEDS, {\Bem Lecture
  Notes in Computer Science}, \lowercase{\BVOL}\ 1614, \BPGS\ 509--516.
  Springer-Verlag.

\bibitem[\protect\BCAY{Celentano\ \BBA\ {Di~Sciascio}}{Celentano\ \BBA\
  {Di~Sciascio}}{1998}]{Celentano-98}
Celentano, A.\BBACOMMA\  \BBA\ {Di~Sciascio}, E. \BBOP1998\BBCP.
\newblock \BBOQ Features integration and relevance feedback analysis in image
  similarity evaluation\BBCQ\
\newblock {\Bem Journal of Electronic Imaging}, {\Bem 7\/}(2), 308--317.

\bibitem[\protect\BCAY{Chandra\ \BBA\ Harel}{Chandra\ \BBA\
  Harel}{1980}]{chan-hare-80}
Chandra, A.\BBACOMMA\  \BBA\ Harel, D. \BBOP1980\BBCP.
\newblock \BBOQ Computable queries for relational databases\BBCQ\
\newblock {\Bem Journal of Computer and System Sciences}, {\Bem 21}, 156--178.

\bibitem[\protect\BCAY{Chang, Shi,\ \BBA\ Yan}{Chang et~al.}{1983}]{chang-83}
Chang, S., Shi, Q., \BBA\ Yan, C. \BBOP1983\BBCP.
\newblock \BBOQ Iconic indexing by {2D} strings\BBCQ\
\newblock {\Bem {IEEE} Transactions on Pattern Analysis and Machine
  Intelligence}, {\Bem 9\/}(3), 413--428.

\bibitem[\protect\BCAY{Chew, Goodrich, Huttenlocher, Kedem, Kleinberg,\ \BBA\
  Kravets}{Chew et~al.}{1997}]{chew-etal-97}
Chew, L., Goodrich, M., Huttenlocher, D., Kedem, K., Kleinberg,
J., \BBA\
  Kravets, D. \BBOP1997\BBCP.
\newblock \BBOQ Geometric pattern matching under euclidean motion\BBCQ\
\newblock {\Bem Computational Geometry}, {\Bem 7}, 113--124.

\bibitem[\protect\BCAY{Cox, Miller, Minka,\ \BBA\ Papathomas}{Cox
  et~al.}{2000}]{Cox-00}
Cox, I., Miller, M., Minka, T., \BBA\ Papathomas, T.
\BBOP2000\BBCP.
\newblock \BBOQ The bayesian image retrieval system, {PicHunter}\BBCQ\
\newblock {\Bem {IEEE} Transactions on Image Processing}, {\Bem 9\/}(1),
  20--37.

\bibitem[\protect\BCAY{{Di~Sciascio}, Donini,\ \BBA\ Mongiello}{{Di~Sciascio}
  et~al.}{2000}]{disc-doni-mong-00}
{Di~Sciascio}, E., Donini, F.~M., \BBA\ Mongiello, M.
\BBOP2000\BBCP.
\newblock \BBOQ A {D}escription logic for image retrieval\BBCQ\
\newblock In Lamma, E.\BBACOMMA\  \BBA\ Mello, P.\BEDS, {\Bem AI*IA 99:
  Advances in Artificial Intelligence}, \lowercase{\BNUM}\ 1792 in Lecture
  Notes in Artificial Intelligence, \BPGS\ 13--24. Springer-Verlag.

\bibitem[\protect\BCAY{{Di~Sciascio}\ \BBA\ Mongiello}{{Di~Sciascio}\ \BBA\
  Mongiello}{1999}]{disc-mong-99}
{Di~Sciascio}, E.\BBACOMMA\  \BBA\ Mongiello, M. \BBOP1999\BBCP.
\newblock \BBOQ Query by sketch and relevance feedback for content-based image
  retrieval over the web\BBCQ\
\newblock {\Bem Journal of Visual Languages and Computing}, {\Bem 10\/}(6),
  565--584.

\bibitem[\protect\BCAY{Donini, Lenzerini, Nardi,\ \BBA\ Schaerf}{Donini
  et~al.}{1996}]{doni-etal-96}
Donini, F., Lenzerini, M., Nardi, D., \BBA\ Schaerf, A.
\BBOP1996\BBCP.
\newblock \BBOQ Reasoning in description logics\BBCQ\
\newblock In Brewka, G.\BED, {\Bem Foundations of Knowledge Representation},
  \BPGS\ 191--236. CSLI-Publications.

\bibitem[\protect\BCAY{Edelmann}{Edelmann}{1999}]{Edelmann99}
Edelmann, S. \BBOP1999\BBCP.
\newblock {\Bem Representation and Recognition in Vision}.
\newblock The {MIT} Press.

\bibitem[\protect\BCAY{{El-Kwae}\ \BBA\ Kabuka}{{El-Kwae}\ \BBA\
  Kabuka}{1999}]{elkw-kabu-99}
{El-Kwae}, E.\BBACOMMA\  \BBA\ Kabuka, M. \BBOP1999\BBCP.
\newblock \BBOQ Content-based retrieval by spatial similarity in image
  databases\BBCQ\
\newblock {\Bem {ACM} Transactions on Information Systems}, {\Bem 17},
  174--198.

\bibitem[\protect\BCAY{Flickner, Sawhney, Niblak, Ashley, Huang, Dom, Gorkani,
  Hafner, Lee, Petkovic, Steele, \BBA\ Yanker}
{Flickner et~al.}{1995}]{Flickner-95} Flickner, M., Sawhney, H.,
Niblak, W., Ashley, J., Huang, Q., Dom, B., Gorkani,
  M., Hafner, J., Lee, D., Petkovic, D., Steele, D., \BBA\ Yanker, P.
  \BBOP1995\BBCP.
\newblock \BBOQ Query by image and video content: The {QBIC} system\BBCQ\
\newblock {\Bem IEEE Computer}, {\Bem 28\/}(9), 23--31.


\bibitem[\protect\BCAY{Foley, {van Dam}, Feiner,\ \BBA\ Hughes}{Foley
  et~al.}{1996}]{fole-etal-96}
Foley, J., {van Dam}, A., Feiner, S., \BBA\ Hughes, J.
\BBOP1996\BBCP.
\newblock {\Bem Computer Graphics}.
\newblock Addison Wesley Publ.\ Co., Reading, Massachussetts.

\bibitem[\protect\BCAY{Fuhr, G{\"overt},\ \BBA\ R{\"o}lleke}{Fuhr
  et~al.}{1998}]{Fuhr98}
Fuhr, N., G{\"overt}, N., \BBA\ R{\"o}lleke, T. \BBOP1998\BBCP.
\newblock \BBOQ {DOLORES}: A system for logic-based retrieval of multimedia
  objects\BBCQ\
\newblock In {\Bem Proceedings of the 21st Annual International ACM SIGIR
  Conference on Research and Developement in Information Retrieval (SIGIR
  '98)}, \BPGS\ 257--265, Melbourne, Australia.

\bibitem[\protect\BCAY{Gevers\ \BBA\ Smeulders}{Gevers\ \BBA\
  Smeulders}{2000}]{Gevers-00}
Gevers, T.\BBACOMMA\  \BBA\ Smeulders, A. \BBOP2000\BBCP.
\newblock \BBOQ Pictoseek: Combining color and shape invariant features for
  image retrieval\BBCQ\
\newblock {\Bem {IEEE} Transactions on Image Processing}, {\Bem 9\/}(1),
  102--119.

\bibitem[\protect\BCAY{Gudivada}{Gudivada}{1998}]{gudi-99}
Gudivada, V. \BBOP1998\BBCP.
\newblock \BBOQ $\theta${R}-string: A geometry-based representation for
  efficient and effective retrieval of images by spatial similarity\BBCQ\
\newblock {\Bem {IEEE} Transactions on Knowledge and Data Engineering}, {\Bem
  10\/}(3), 504--512.

\bibitem[\protect\BCAY{Gudivada\ \BBA\ Raghavan}{Gudivada\ \BBA\
  Raghavan}{1995}]{gudi-ragh-95}
Gudivada, V.\BBACOMMA\  \BBA\ Raghavan, J. \BBOP1995\BBCP.
\newblock \BBOQ Design and evaluation of algorithms for image retrieval by
  spatial similarity\BBCQ\
\newblock {\Bem {ACM} Transactions on Information Systems}, {\Bem 13\/}(2),
  115--144.

\bibitem[\protect\BCAY{Haarslev, Lutz,\ \BBA\ M{\"o}eller}{Haarslev
  et~al.}{1998}]{haar-lutz-moel-98}
Haarslev, V., Lutz, C., \BBA\ M{\"o}eller, R. \BBOP1998\BBCP.
\newblock \BBOQ Foundations of spatioterminological reasoning with description
  logics\BBCQ\
\newblock In {\Bem Proceedings of the Sixth International Conference on
  Principles of Knowledge Representation and Reasoning (KR'98)}, \BPGS\
  112--123.

\bibitem[\protect\BCAY{Hacid\ \BBA\ Rigotti}{Hacid\ \BBA\
  Rigotti}{1999}]{Hacid99}
Hacid, M.-S.\BBACOMMA\  \BBA\ Rigotti, C. \BBOP1999\BBCP.
\newblock \BBOQ Representing and reasoning on conceptual queries over image
  databases\BBCQ\
\newblock In {\Bem Proceedings of the Twelfth International Symposium on
  Methodologies for Intelligent Systems (ISMIS'99)}, \lowercase{\BNUM}\ 1609 in
  Lecture Notes in Artificial Intelligence, \BPGS\ 340--348, Warsaw, Poland.
  Springer-Verlag.

\bibitem[\protect\BCAY{Hartman\ \BBA\ Wernecke}{Hartman\ \BBA\
  Wernecke}{1996}]{VRML}
Hartman, J.\BBACOMMA\  \BBA\ Wernecke, J. \BBOP1996\BBCP.
\newblock {\Bem The {VRML} 2.0 Handbook}.
\newblock Addison-Wesley.

\bibitem[\protect\BCAY{Hirata\ \BBA\ Kato}{Hirata\ \BBA\
  Kato}{1992}]{Hirata-92}
Hirata, K.\BBACOMMA\  \BBA\ Kato, T. \BBOP1992\BBCP.
\newblock \BBOQ Query by visual example\BBCQ\
\newblock In Pirotte, A., Delobel, C., \BBA\ Gottlob, G.\BEDS, {\Bem Advances
  in Database Technology --- Proc. 3rd Int. Conf. Extending Database
  Technology, {EDBT}}, \lowercase{\BVOL}\ 580 of {\Bem Lecture Notes in
  Computer Science}, \BPGS\ 56--71. Springer-Verlag.

\bibitem[\protect\BCAY{Jacobs, Finkelstein,\ \BBA\ Salesin}{Jacobs
  et~al.}{1995}]{Jacobs-95}
Jacobs, C., Finkelstein, A., \BBA\ Salesin, D. \BBOP1995\BBCP.
\newblock \BBOQ Fast multiresolution image querying\BBCQ\
\newblock In {\Bem Proceedings of the 22nd Annual Conference on Computer
  Graphics and Interactive Techniques (SIGGRAPH '95)}, \BPGS\ 277--286.

\bibitem[\protect\BCAY{Jahne, Haubecker,\ \BBA\ Geibler}{Jahne
  et~al.}{1999}]{handbook-pr}
Jahne, B., Haubecker, H., \BBA\ Geibler, P. \BBOP1999\BBCP.
\newblock {\Bem Handbook of Computer Vision and Applications}.
\newblock Academic Press.

\bibitem[\protect\BCAY{Ma\ \BBA\ Manjunath}{Ma\ \BBA\
  Manjunath}{1997}]{ma-manj-97}
Ma, W.\BBACOMMA\  \BBA\ Manjunath, B. \BBOP1997\BBCP.
\newblock \BBOQ {NETRA}: A toolbox for navigating large image database\BBCQ\
\newblock In {\Bem Proceedings of the IEEE International Conference on Image
  Processing (ICIP '97)}, \lowercase{\BVOL}~1, \BPGS\ 568--571, Santa Barbara.

\bibitem[\protect\BCAY{Marr}{Marr}{1982}]{marr-82}
Marr, D. \BBOP1982\BBCP.
\newblock {\Bem Vision}.
\newblock W.H. Freeman and Co., Oxford.

\bibitem[\protect\BCAY{Meghini, Sebastiani,\ \BBA\ Straccia}{Meghini
  et~al.}{2001}]{Meghini01}
Meghini, C., Sebastiani, F., \BBA\ Straccia, U. \BBOP2001\BBCP.
\newblock \BBOQ A model of multimedia information retrieval\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 48\/}(5), 909--970.

\bibitem[\protect\BCAY{Moeller, Neumann,\ \BBA\ Wessel}{Moeller
  et~al.}{1999}]{moel-neum-wess-99}
Moeller, R., Neumann, B., \BBA\ Wessel, M. \BBOP1999\BBCP.
\newblock \BBOQ Towards computer vision with description logics: some recent
  progress\BBCQ\
\newblock In {\Bem Proceedings of the {IEEE} Integration of Speech and Image
  Understanding}, \BPGS\ 101--115.

\bibitem[\protect\BCAY{Nebel}{Nebel}{1990}]{nebe-90}
Nebel, B. \BBOP1990\BBCP.
\newblock {\Bem Reasoning and Revision in Hybrid Representation Systems}.
\newblock \BNUM\ 422 in Lecture Notes in Artificial Intelligence.
  Springer-Verlag.

\bibitem[\protect\BCAY{Niblak, Barder, Equitz, Flickner, Glasman, Petkovic,
  Yanker,\ \BBA\ Faloustos} {Niblak et~al.}{1993}]{Niblak-93}
Niblak, W., Barder, R., Equitz, W., Flickner, M., Glasman, E.,
Petkovic, D.,
  Yanker, P., \BBA\ Faloustos, C. \BBOP1993\BBCP.
\newblock \BBOQ The {QBIC} project: Querying images by content using color,
  texture, and shape\BBCQ\
\newblock In {\Bem Storage and Retrieval for Still Image and Video Databases},
  \lowercase{\BVOL}\ 1980, \BPGS\ 173--182. SPIE.


\bibitem[\protect\BCAY{Paquet\ \BBA\ Rioux}{Paquet\ \BBA\
  Rioux}{1998}]{paqu-riou-99}
Paquet, E.\BBACOMMA\  \BBA\ Rioux, M. \BBOP1998\BBCP.
\newblock \BBOQ A content-based search engine for {VRML} databases\BBCQ\
\newblock In {\Bem Proceedings of IEEE International Conference on Computer
  Vision and Pattern Recognition (CVPR'98)}, \BPGS\ 541--546, Santa Barbara,
  CA.

\bibitem[\protect\BCAY{Picard\ \BBA\ Kabir}{Picard\ \BBA\
  Kabir}{1993}]{Picard-93}
Picard, R.\BBACOMMA\  \BBA\ Kabir, T. \BBOP1993\BBCP.
\newblock \BBOQ Finding similar patterns in large image databases\BBCQ\
\newblock In {\Bem Proceedings of the IEEE International Conference on
  Acoustics Speech and Signal Processing (ICASSP '93)}, \BPGS\ 161--164,
  Minneapolis, MN.

\bibitem[\protect\BCAY{Pirri\ \BBA\ Finzi}{Pirri\ \BBA\
  Finzi}{1999}]{pirri-finzi-99}
Pirri, F.\BBACOMMA\  \BBA\ Finzi, A. \BBOP1999\BBCP.
\newblock \BBOQ An approach to perception in theory of actions: part 1\BBCQ\
\newblock In {\Bem Linkoping Electronic Articles in Computer and Information
  Science}, \lowercase{\BNUM}~41. Linkoping University Electronic Press.

\bibitem[\protect\BCAY{Pok\ \BBA\ Liu}{Pok\ \BBA\ Liu}{1999}]{Pok-99}
Pok, G.\BBACOMMA\  \BBA\ Liu, J. \BBOP1999\BBCP.
\newblock \BBOQ Texture classification by a two-level hybrid scheme\BBCQ\
\newblock In {\Bem Storage and Retrieval for Image and Video Databases VII},
  \lowercase{\BVOL}\ 3656, \BPGS\ 614--622. SPIE.

\bibitem[\protect\BCAY{Pratt}{Pratt}{1991}]{Pratt}
Pratt, W. \BBOP1991\BBCP.
\newblock {\Bem Digital Image Processing}.
\newblock J. Wiley \& Sons Inc., Englewood Cliffs, NJ.

\bibitem[\protect\BCAY{Reiter\ \BBA\ Mackworth}{Reiter\ \BBA\
  Mackworth}{1989}]{reit-mack-89}
Reiter, R.\BBACOMMA\  \BBA\ Mackworth, A. \BBOP1989\BBCP.
\newblock \BBOQ A logical framework for depiction and image
  interpretation\BBCQ\
\newblock {\Bem Artificial Intelligence}, {\Bem 41\/}(2), 125--155.

\bibitem[\protect\BCAY{Reiter}{Reiter}{1980}]{reit-80}
Reiter, R. \BBOP1980\BBCP.
\newblock \BBOQ Equality and domain closure in first-order databases\BBCQ\
\newblock {\Bem Journal of the ACM}, {\Bem 27\/}(2), 235--249.

\bibitem[\protect\BCAY{Rui, Huang,\ \BBA\ Mehrotra}{Rui et~al.}{1997}]{Rui-97}
Rui, Y., Huang, T., \BBA\ Mehrotra, S. \BBOP1997\BBCP.
\newblock \BBOQ Content-based image retrieval with relevance feedback in
  {MARS}\BBCQ\
\newblock In {\Bem Proceedings of the IEEE International Conference on Image
  Processing (ICIP '97)}, \BPGS\ 815--818.

\bibitem[\protect\BCAY{Rui, She,\ \BBA\ Huang}{Rui et~al.}{1996}]{Rui-96}
Rui, Y., She, A., \BBA\ Huang, T. \BBOP1996\BBCP.
\newblock \BBOQ Modified {F}ourier descriptors for shape representation - a
  practical approach\BBCQ\
\newblock In {\Bem Proceedings of 1st Workshop on Image Databases and
  Multimedia Search}, Amsterdam.

\bibitem[\protect\BCAY{Sanfeliu\ \BBA\ Fu}{Sanfeliu\ \BBA\
  Fu}{1983}]{sanf-fu-83}
Sanfeliu, A.\BBACOMMA\  \BBA\ Fu, K. \BBOP1983\BBCP.
\newblock \BBOQ A distance measure between attributed relational graphs for
  pattern recognition\BBCQ\
\newblock {\Bem {IEEE} Transactions on Systems, Man, and Cybernetics}, {\Bem
  13\/}(3), 353--362.

\bibitem[\protect\BCAY{Smith\ \BBA\ Chang}{Smith\ \BBA\ Chang}{1996}]{Smith-96}
Smith, J.\BBACOMMA\  \BBA\ Chang, S. \BBOP1996\BBCP.
\newblock \BBOQ {VisualSEEK}: a fully automated content-based image query
  system\BBCQ\
\newblock In {\Bem Proceedings of the fourth ACM International Conference on
  Multimedia (Multimedia'96)}, \BPGS\ 87--98.

\bibitem[\protect\BCAY{Straccia}{Straccia}{2001}]{Straccia01}
Straccia, U. \BBOP2001\BBCP.
\newblock \BBOQ Reasoning within fuzzy description logics\BBCQ\
\newblock {\Bem Journal of Artificial Intelligence Research}, {\Bem 14},
  137--166.

\bibitem[\protect\BCAY{Tagare, Vos, Jaffe,\ \BBA\ Duncan}{Tagare
  et~al.}{1995}]{taga-vos-95}
Tagare, H., Vos, F., Jaffe, C., \BBA\ Duncan, J. \BBOP1995\BBCP.
\newblock \BBOQ Arrangement: A spatial relation between parts for evaluating
  similarity of tomographic section\BBCQ\
\newblock {\Bem {IEEE} Transactions on Pattern Analysis and Machine
  Intelligence}, {\Bem 17\/}(9), 880--893.

\bibitem[\protect\BCAY{Ullman}{Ullman}{1988}]{ullm-88}
Ullman, J.~D. \BBOP1988\BBCP.
\newblock {\Bem Principles of Database and Knowledge Base Systems},
  \lowercase{\BVOL}~1.
\newblock Computer Science Press, Potomac, Maryland.

\bibitem[\protect\BCAY{Woods\ \BBA\ Schmolze}{Woods\ \BBA\
  Schmolze}{1992}]{wood-schm-92}
Woods, W.~A.\BBACOMMA\  \BBA\ Schmolze, J.~G. \BBOP1992\BBCP.
\newblock \BBOQ The {KL-ONE} family\BBCQ\
\newblock In Lehmann, F.~W.\BED, {\Bem Semantic Networks in Artificial
  Intelligence}, \BPGS\ 133--178. Pergamon Press.
\newblock Published as a special issue of {\it Computers \& Mathematics with
  Applications}, Volume 23, Number 2--9.

\bibitem[\protect\BCAY{Yen}{Yen}{1991}]{yen-91}
Yen, J. \BBOP1991\BBCP.
\newblock \BBOQ Generalizing term subsumption languages to {F}uzzy logic\BBCQ\
\newblock In {\Bem Proceedings of the Twelfth International Joint Conference on
  Artificial Intelligence (IJCAI'91)}, \BPGS\ 472--477.

\bibitem[\protect\BCAY{Zadeh}{Zadeh}{1965}]{zade-??}
Zadeh, L. \BBOP1965\BBCP.
\newblock \BBOQ Fuzzy sets\BBCQ\
\newblock {\Bem Information and Control}, {\Bem 8}, 338--353.

\end{thebibliography}


\end{document}
