Emergent Semantics through Interaction in Image Databases.
AbstractIn this paper, we briefly discuss some aspects of image semantics and the role that it plays for the design of image databases. We argue that images don't have an intrinsic meaning, but that they are endowed with a meaning by placing them in the context of other images and by the user interaction. From this observation, we conclude that, in an image, database users should be allowed to manipulate not only the individual images, but also the relation between them. We present an interface model based on the manipulation of configurations of images.
where i are terminal symbols of the record definition language, Ri are non terminal symbols,
and j is the label of the production rule, then the meaning of R is:
The meaning of the whole record depends on the production rule and on the meaning of the
non terminals on the right side of the production, but not on the syntactic structure of the non
terminals R1, . , Rn.
This property makes the analysis of the meaning of records in traditional databases conceptually
easy but, unfortunately, it does not hold for images. As Umberto Eco puts it:
The most nave way of formulating the problem is: are there iconic sentences and
phonemes? Such a formulation undoubtedly stems from a sort of verbocentric dog-
matism, but in it ingenousness it conceals a serious problem.[2]
The problem is indeed important and the answer to the question, as Eco points out, is no.
Although some images contain syntactical units in the form of objects, underneath this level it
is no longer possible to continue the subdivision, and the complete semantic characterization
of images goes beyond the simple enumeration of the objects in it and their relations (see [20]
for examples).
level beyond the objects are used very often in evocative scenarios, like art and
advertising [1]. There is, for instance, a fairly complex theory of the semantics associated with
color [5], and with artistic representational conventions [3].
The full meaning of an image depends not only on the image data, but on a complex of
cultural and social conventions in use at the time and location of the query, as well as on other
contigiencies of the context in which the user interacts with the database. This leads us to
reject the somewhat Aristotelean view that the meaning of an image is an immanent property
of the image data. Rather, the meaning arises from a process of interpretation and is the result
of the interaction between the image data and the interpreter. The process of querying the
database should not be seen as an operation during which images are filtered based on the
illusory pre-existing meaning but, rather, as a process in which meaning is created through the
interaction of the user and the images.
The cultural nature of the meaning and its dependence on the interpretation process show
that meaning is not a simple function of the image data alone. The Saussurean relation between
the signifiant and the signifie is always mediated. This relation, much like in linguistic signs,
does not stand alone, but is only identifiable as part of a system of oppositions and dierences.
In other words, the referential relation between a sign (be it an icon or a symbol) can only
stand when the sign is made part of a system. Consider the images of Fig. 1. The image at
the center is a Modigliani portrait and, placed in the context of other 20th century paintings
(some of which are portraits and some of not), suggests the notion of painting. If we take
the same image and place it in the context of Fig. 2, the context suggests the meaning Face.
These observations rule out the possibility of extracting some intrinsically determined meaning
from the images, storing it in a database, and using it for indexing. The meaning of the

Figure

1: A Modigliani portait placed in a context that suggests Painting.

Figure

2: A Modigliani portrait placed in a context that suggests Face.

Figure

3: Schematic description of an interaction using a direct manipulation interface.
image data can only emerge from the interaction with the user. The user will provide the
cultural background in which meaning can be grounded. We call this concept emergent se-
mantics. This concept has important consequences for our query model and, ultimately, for
the archtecure of image databases: the filtering approach, typical of symbolic databases, is no
longer viable. Rather, interfaces should support a process of guided exploration of the database.
The interface is no longer the place where questions are asked and answers are obtained, but it
is the tool for active manipulation of the database as a whole.
3 Interfaces for Emergent Semantics
Based on the ideas in the previous sections, we replaced the query-answer model of interaction
with a guided exploration metaphor. In our model, the database gives information about the
status of the whole database, rather than just about a few images that satisfy the query. The
user manipulates the image space directly by moving images around, rather than manipulating
weights or some other quantity related to the current similarity measure3 The manipulation
of images in the display causes the creation of a similarity measure that satisfies the relations
imposed by the user.
An user interaction using an exploratory interface is shown schematically in Fig. 3. In
Fig. 3.A the database proposes a certain distribution of images (represented schematically
as simple shapes) to the user. The distribution of the images reflects the current similarity
interpretation of the database. For instance, the triangular star is considered very similar to
the octagonal star, and the circle is considered similar to the hexagon. In Fig. 3.B the user
moves some images around to reflect his own interpretation of the relevant similarities. The
result is shown in Fig. 3.C. According to the user, the pentagonal and the triangular stars are
3The manipulation of the underlying similarity measure by explicitly setting a number of weights that characterize
it is very common in current image databases but very counterintuitive.

Figure

4: Interaction involving the creation of concepts.
are quite similar to each other, and the circle is quite dierent from both of them.
As a result of the user assessment, the database will create a new similarity measure, and
re-order the images, yielding the configuration of Fig. 3.D. The pentagonal and the triangular
stars are in this case considered quite similar (although they were moved from their intended
position), and the circle quite dierent. Note that the result is not a simple rearrangement of
the images in the interface. For practical reasons, an interface can't present more than a small
fraction of the images in the database. Typically, we display the 100-300 images most relevant
to the query. The reorganization consequent the user interaction involves the whole database.
Some images will disappear from the display (the hexagon in Fig. 3.A), and some will appear
(e.g. the black square in Fig. 3.D).
A slightly dierent operation on the same interface is the definition of visual concepts. In
the context of our database, the term concept has a more restricted scope than in the common
usage. A visual concept is simply a set of images that, for the purpose of a certain query, can be
considered as equivalent or almost equivalent. Images forming a visual concept can be dragged
into a concept box and, if necessary, associated with some text (the text can be used to
retrieve the concept and the images similar to it). The visual concept can be then transformed
into an icon and placed on the screen like every other image.
Fig. 4 is an example of interaction involving the creation of visual concepts. Fig. 4.A contains
the answer of the database to a user query. The user considers the red and green images as
two instances of a well defined linguistic concept. The user opens a concept box and drags the
images inside the box. The box is then used as an icon to replace the images in the display
space.
From the point of view of the interface, a concept is a group of images that occupy the
same position in the display space. In addition, it is possible to attach metadata information
to a concept. For instance, if a user is exploring an art database, he can create a concept
called medieval crucifixion. The words medieval and crucifixion can be used to replace
the actual images in a query. This mechanism gives a way of integrating visual and non visual
queries. If an user looks for medieval paintings representing the crucifixion, she can simply
type in the words. The corresponding visual concept will be retrieved from memory, placed in
the visual display, and the images contained in the concept will be used as examples to start a
visual query.
The interface, as it is presented here, is but a skeleton for interaction that can be extended
along many directions. Its main limitation (and the relative opportunities for improvement)
are the following:
Visual concepts can't be nested: a visual concept can't be used as part of the definition
of another visual concept (although the images that are part of it can).
With the exception of visual concept, which can be stored, the system has no long term
memory, that is, no context information can be transported from one user session to
another.
Contexts (distributions of images) can't be saved and restored, not even within a session.
The system does not allow cooperation between users. There is no possibility of defining
a user profile that can be used to retrieve contexts from other users and use them for
some form of social filtering [].
All these limitations can be overcome without changing tha nature or the basic design of
the interface, by adding appropriate funtions to the system. In this paper we will not consider
them, and we will limit the discussion to the basic interface. Further study is necessary to
determine which solutions are useful, useless, or (possibly) detrimental.
An exploration interface requires a dierent and more sophisticated organization of the
database. In particular, the database must accommodate arbitrary (or almost arbitrary) similarity
measures, and must automatically determine the similarity measure based on the user
interface. In the following section we describe in greater details the principles behind the design
of exploratory interfaces.
4 Exploration Operators
The exploration interface is composed of three spaces and a number of operators [4]. The
operators can be transformations of a space onto itself or from one space to another. The three
space on which the interface is based are:
The Feature space F. This is the space of the coecients of a suitable representation of
the image. The feature space topological, but not metric. There is in general no way to
assign a distance to a pair of feature vectors.

Figure

5: Operator algebra as a mediation between the graphical front-end and the database.
The Query space Q. When the feature space is endowed with a metric, the result is the
query space. The metric of the query space is derived from the user query, so that the
distance from the origin of the space to any image defines the dissimilarity of that image
from the current query.
The Display space D is a low dimensional space (0 to 3 dimensions) which is displayed to
the user and with which the user interacts. The distribution of images in the display space
is derived from that of the query space. We will mainly deal with two-dimensional display
spaces (as implemented in a window on a computer screen.) For the sake of convenience,
we also assume that every image in the visualization space has attached a number of labels
i drawn from a finite set. Examples of labels are the visual concepts to which an image
belongs. The conventional label is assigned to those images that have been selected and
placed in their position (anchored)by the user.
The feature space is a relatively fixed entities, and is a property of the database. The query
space, on the other hand, is created anew with a dierent metric after every interaction with
the user.
The interaction is defined by an algebra of operators between these three spaces. The operators
play more or less the same role that the query algebra plays in traditional databases
(although, as we havementioned in the previous section, the term query is in this case inap-
propriate). In all practical instances of the system, the user does not deal with these operators
directly, but through a suitable graphic front-end (see Fig. 5), whose characteristics vary
depending on the particular application. Later in this paper we will consider the graphical
front-end of our database system El Nin~o ([18]). In this section we will be concerned with the
operators that mediate the exploration of the database.
4.1 Operators in the Feature Space
A feature is an attribute obtained applying some image analysis algorithms to the image data.
Features are often numeric, collected in a feature vector, and immersed in a suitable vector
space, although this is not always the case.
We make a distinction between the raw, unprocessed vector space and spaces that are
adapted from it for reasons of convenience. This distinction is not fundamental (all feature
spaces are the result of some processing) but it will be useful to describe the operators. The
raw feature space is the set of complete feature vectors, as they come out of the image analysis
algorithms. In many cases, we need to adjust these vectors for the convenience of the database
operations. A very common example is dimensionality reduction [12]. In this case, we will say
that we obtain a (reduced-dimensional) stored view of the feature space. The operators defined
on the feature space are used for this purpose. The most common are:
Projection. The feature vector is projected on a low dimensional subspace of the raw feature
space, obtaining a low dimensional view. Operators like Singular Value Decomposition,
projection of Zernike and statistical moments belong to this class.
Quantization. These operators are used in non-vector feature spaces like the set of coe-
cients used in [18]. In this case, we reduce the dimensionality of the feature space by representing
an image with a limited number of coecients (e.g. 50 or 100). This is done by vector quantization
of the image coecients (this kind of operation will be considered more in detail in
section 5).
Apply Function. Applies the function F to all the elements of a set of numbers to create
another set of numbers of the same dimension. Filtering operations applied to color histograms
belong to this class.
These operators prepare the feature space for the database operations. They are not
properly part of the interaction that goes on in the interface, since they are applied o-line
before the user starts interacting. We have mentioned them for the sake of completeness.
4.2 The Query Space
The feature space, endowed with a similarity measure derived from a query, becomes the query
space. The score of an image is determined by its distance from the origin of this space
according to a metric dependent on the query. We assume that every image is represented as
a set of n number (which may or may not identify a vector in an n-dimensional vector space)
and that the query space is endowed with a distance function that depends on m parameters.
The feature sets corresponding to images x and y are represented by xi and yi,
and the parameters by , m. Also, to indicate a particular image in the database
we will use either dierent Latin letters, as in xi, yi or an uppercase Latin index. So, xI is
the I-th image in the database (1 I N), and xj , is the corresponding feature
I
vector.
The parameters  are a representation of the current query, and are the values that determine
the distance function. They can also be seen as encoding the current database approximation
to the user's semantic space.
Given the parameters , the distance function in the query space can be written as

with f L2(IRn  IRn  IRm, IR+). Depending on the situation, we will write f(xi, yi) in lieu of
f(xi,
As stated in the previous section, the feature space per se is topological but not metric.
Rather, its intrinsic properties are characterized by the functional
which associates to each query  a distance function:
A query, characterized by a vector of parameters , can also be seen as an operator q
which transforms the feature space into the query space. If L is the characteristic functional of
the feature space, then is the metric of the query space. This is a very important
operator for our database model and will be discussed in section 6.
Once the feature space F has been transformed into the metric query space Q, other operations
are possible [4, 20], like:
Distance from Origin Given a feature set xi, return its distance from the query:
Distance Given a two feature sets xi, yi, return the distance between the two
Select by Distance. Return all feature sets that are closer to the query than a given distance:

k-Nearest Neighbors. Return the k images closest to the query


It is necessary to stress again that these operations are not defined in the feature space F
since that space is not endowed with a metric. Only when a query is defined does a metric
exist.
4.3 The Display Space
The display operator projects image xi on the screen position in such a way
that
We use a simple elastic model to determine the position of images in the display space, as
discussed in section 6. The result is an operator that we write:
The parameter f reminds us that the projection that we see on the screen depends on the
distribution of images in the query space which, in turn, depends on the query parameters
. The notation (XI, ) means that the image xI is placed at the coordinates xI in the
display space, and that there are no labels attached to it (viz. the image is not anchored at
any particular location of the screen, and does not belong to any particular visual concept).
A configuration of the display space is obtained by applying the display operator to the
entire query space:

where I is the set of labels associated to image I. As we said before, it is impractical to display
the whole database. More often, we display only a limited number P of image. Formally, this
can be done by applying the P-nearest neighbors operator to the space Q:

The display space D is the space of the resulting configurations. With these definitions, we can
describe the operators that manipulate the display space.
The Place Operator The place operator moves an image from one position of the display
space to another, and attaches a label to the images to anchor it to its new position. The
operator that places the I-th image in the display is I : Q Q

I (XJ, J
where X~ is the position given to the image by the user.
Visual Concept Creation A visual concept is is a set of images that, conceptually, occupy
the same position in the display space and are characterized by a set of labels. Formally, we
will include in the set of labels the keywords associated to the concept as well as the identifiers
4Capital Greek indices will span 1, l. The most frequent case, in our experience, is the simple two-dimensional
display, that is, l = 2. The arguments presented here, however, hold for any l-dimensional display. Conventionally,
refers to a browser in wihch only ordinal properties are displayed.
of the images that are included in the concept. So, if the concept contains images I1, . , Ik,
the set of labels is
where W is the set of keywords. We call X the set of concept, and we will use the letter to
represent a concept.
The creation of a concept is an operator : D X defined as:

This concept takes a set of images, in positions XJ and attached labels J , and transforms them
in an entity that formally is an image with unspecified position, and a set of labels composed of

the union of all the labels of the images ( J J ), the set of keywords associated to the concept,
and the list of the images that belong to the concept.
Visual Concept placement The insertion of a concept in a position Z of the display space
is defined as the action of the operator defined as:

Metadata Queries Visual concepts can be used to create visual queries based on semantic
categories. Suppose a user enters a set of words A. It is possible to define the distance from
the keyword set A to the textual portion of a visual concept label using normal information
retrieval techniques [13]. Let d(A, ) be such a distance. Similarly, it is possible to determine
the distance between two concepts d(1, 2). Then the textual query A can be transformed in
a configuration of the display space

XI, I (19)
where
and

The resulting metadata query operator  takes a set of keywords A and returns a configuration
of images in the display space that satisfies the relation (21):
In other words, we can use the distance between the concepts and the query, as well as the
distances between pairs of concepts, to place the corresponding images in the display space,
thus transforming the textual query in a visual query.
The description of the interaction as the action of a set of operators provides a useful algebraic
language for the description of the query process. Operators provide the necessary
grounding for the study of problems of query organization and optimization in the exploratory
framework. Operators, however, still constitute a functional description of the exploration
components. They don't (nor do they purport to) oer us an algorithmic description of the
database. The implementation of the operators requires considering a suitable image representation
in a space with the required metric characteristics. We will study this problem in the
next section.
5 Image Representation
A good image representation for image database applications should permit a flexible defini-
tion of similarity measures in the resulting feature space. There are two ways in which this
requirement can be interpreted. First, can require that some predefined distance (usually the
Euclidean distance or some other Minkowski distance) give us sound results when applied to
the feature space within a certain (usually quite narrow) range of semantic significance of these
features. Extracting features like color histograms or Gabor descriptors for textures [9] may
satisfy this requirement for certain classes of images.
A second sense in which the requirement can be understood is that of coverage. In this
case we require that the feature space support many dierent similarity criteria, and that it
be possible to switch from one criterion to another simply by changing the definition of the
distance in the feature space.
This possibility is a property both of the distance and of the feature space. On one hand,
we must define a class of distances rich enough to represent most of the similarity criteria that
we are likely to encounter in practice. On the other hand, this eort would be fruitless if the
feature space (i.e. the image representation) were not rich in information, that is, if it didn't
represent enough aspects of the images to support the definition of these similarity criteria.
To make a simple example, consider a feature space consisting of a simple histogram of the
image. No matter what similarity measure we define, in this space it is impossible to formulate
a query based on structure or spatial organization of the image.
In this section we introduce a general and ecient image representation that constitutes a
feature space with wide coverage for image database applications.
A color image is a function f : S R3. C is the color space, which we assume
endowed with a metric, whose exact characteristics depend on the specific color system adopted.
In order to measure distances, we need to endow the space F of image functions with a suitable
metric structure.
It is a well known fact that groups of transformations can be used to generate continuous
wavelet transforms of images [7]. If the transformation group from which we start is endowed
with a metric, this will naturally induce a metric in the space of transformed images.
Consider the space L2(X, m), where m is a measure on X, and a Lie group G which acts
freely and homogeneously on X[14]. We will assume that G, as a manifold, is endowed with a
Riemann metric. If g G, then a representation of G in L2(X) is a homomorphism
The irreducible unitary representation of G on L2(X, Y ) (where Y is a given smooth manifold)
is defined as

where m is a measure on X and f is a function f : X Y . This representation can be
used to generate a wavelet transform. Starting from a mother wavelet L2(X), we define
for the moment, we assume (as would be the case, for instance, for a
grayscale image), the transform of f is:
Note that the wavelet transform of f is defined on G. In the case of images, we have
In case of color images, the assumption does not hold, and it not clear how to define
the inner product f, g. A possibility, often used in literature, is to treat the color image as
three separate grayscale images, and to process them independently [6]. Another possibility,
introduced in [16], is to define an algebra of colors. In this case the values of Tf (g) in (30) are
also colors.
It is possible to extend the same definition to discrete groups [15] by consider a discrete
subgroup GD G. If G is a Lie group of dimension n, consider a set of indices I Zn. We
consider the set
under the usual closeness conditions that characterize subgroups.
Given a representation of G, : G L2(X), the restriction of to GD is obviously a
representation of GD. In particular, the canonical unitary representation of GD is

dm(g-1 . x)
and the GD-frame transform of a function f with mother wavelet is:

The system of indices j plays an important role in implementation: the discrete transform
is usually stored in a multidimensional array and accessed through the indices of the array.
We can endow the set of indices I with a group structure such that there is a homomorphism
of I into GD. This homomorphism induces a distance function in the group I by
We can now define the discrete transform

In the case of color images, if the image is divided in three independent channels, we will have
three seprate multidimensional arrays of coecients, while in the case of a color algebra we will
have a single multidimensional array whose entries are colors. In the following, we will consider
the latter case, since the former can easily be reduced to it.
Thanks to the distance dI, this transform has a metric structure just like the continuous
transform. Note that the functions will not in general form an orthogonal basis
of L2(IR2), but an overcomplete frame [8].
An image can be completely represented by the set of coecients of its transform. As we
will see in the following section, this representation is very convenient for defining metrics in the
image space, but it is too costly in terms of storage space for applications in image databases.
For instance, applying the ane group to an image of size 128128 will result in about 21, 000
coecients, each of which is a color and therefore is represented by three numbers.
Each coecient in the image representation is defined by the element g G (its position
in the group) and its color c C. Therefore, a coecient in the representation can be seen as a
both G and C are metric spaces, so is G  C. Therefore, given
two coecients 1 and 2 it is possible to define their distance d(1, 2). With this distance
function, it is possible to apply vector quantization to the set of coecients and obtain a more
compact representation [15]. In our tests, we apply Vector Quantization to represent the image
with a number of coecients between 100 and 300.
5.1 Distance Functions
The representation introduced in the previous section gives us the necessary general feature
space. In order to obtain a complete foundation for an image search engine, it is now necessary
to define a suitably comprehensive class of distances into this space. For the sake of simplicity,
we will begin by considering representations obtained from the continuous group G. In this
case, the representation of an image is a function f and the graph of the representation
if a subset of GC. Both G and C are metric spaces. If gij is the metric tensor of G interpreted
as a Riemann manifold, and cuv is the metric tensor of C, then the metric of

and the distance between two points of H isq 2
rs
where the integral is computed on a geodesic u(t) between p and q. In the discrete case d(p, q)
is the distance between two coecients of the transform.
The distance between a point x H and a set A H is defined as:
and the distance between two sets A, B H as
weighting function that we will use in the following to
manipulate the distance function. Note that with this definition the distance is not symmetric.
For a justification of this, see [19, 23]. This distance can be used to measure dissimilarities
between images.
An important property of this class of distances is given by the following theorem (proved
in [15]):
Theorem 5.1 Let H be a subgroup of G, and assume that the metric tensor in G is such that
the corresponding distance function is
If are two functions such that
then d(f1,
In other words, we can select a subgroup of transformations such that two images obtained
one from the other through a transformation in the subgroup have distance 0.
By acting on the tensors g and c and the function w it is possible to define a number of
dierent similarity criteria. Consider the following:
If we are interested in the global color of an image, we will define the distance in G to be
invariant to translation, and the metric tensor to be non-null only at low frequencies.
If we are interested in the structure of an image, we can define the tensor g to be non-null
only at high frequencies, and the tensor c to depend only on the brightness of the image.
To search for a certain object, we define the tensor to be nonzero only in the region of
the object in the query image, and enforce translation invariance.
It is possible to enforce quasi invariance: the measure is not exactly invariant to a
given transformation, but the distance increases very slowly when the images change.
Quasi-invariance gives often more robust results than complete invariance.
More importantly, it is possible to parameterize the tensors g and c and the function w and
define distances based on user interaction [15].
It is possible to extend the distance computation to the approximate representation. Let us
start with an idealized case. In vector quantization, an image is represented by a set of Voronoi
polygons that cover all G. Assume that the Voronoi polygons of the two images coincide on
the subspace G, and that they dier only in color.
We have the following:
Definition 5.1 Let the set of Voronoi polygons of an image, Sk V and
a Sk. The point a is at distance d from the border of Sk if

We will use the notation (a) = d
Definition 5.2 Let SA and SB two overlapping Voronoi polygons, and let the distance between
the colors of these polygons be . A point a SA is internal if (a) > , and is a boundary
point otherwise. The interior of SA, SA, is the set of internal points of SA, and the border of
SA, SA, is the set of boundary points.
Lemma 5.1 Let SA and SB be two overlapped Voronoi polygons with color distance . If a is
an internal point of SA, then
The distance between SA and SB is:
A aSA

A aSA aSA
If SA SA, then
d (SA, SB) (40)
(see [15]).
The assumption that the Voronoi polygons are overlapping is obviously false. Given a
Voronoi polygon VA belonging to the image A, however, it is possible to compute its distance
from image B by doing some approximation:
Assume that only a fixed number N of Voronoi polygons of image B overlap VA, and that
the area by which VB,i overlaps VA depends only on the distance between the respective
centroids.
Find the N polygons of B whose centroids are closer to that of VA, and compute the

distance di between their centroids and that of VA. Let
Let i be the distance between the color of VA and the color of VB,i.
Compute
In this way, we can compute (approximately) the distance between one of the Voronoi
polygons of image A and image B. If VA is the set of all Voronoi polygons that define A, then
the approximate distance betwen A and B is given by:
|VA|
with wV > 0 and V VA
6 Query and Projection Operators
The two operators that most characterize the exploratory approach are the projection operator
, and the query operator q. The first operator must project the images from the query space
to the image space in a way that represent as well as possible the current database similarity
(which, as we have argue, is the origin root of database semantics). The second operator must
generate a metric for the query space that reflects as well as possible the similarity relation that
the user communicated by placing images on the interface.
6.1 Projection Operator
The projection operator in its entirety is written as For the present
purposes, we can ignore the set of labels, and we can remove the explicit reference to the metric
f, so we can write XI. The distance between images xI and xJ in the query space
is f(xI, xJ ; ), while for the display space we assume that the perception of closeness is well
represented by the Euclidean distance: d(XI, XJ
As mentioned in the previous sections, we will not display the whole database, but only the
images closest to the query (with, usually, 50 P 300). Let I be the set of indices of
such images, with P. The operator needs not be concerned with all the images in the
database, but only with those that will be actually displayed.
First, we query the database so as to determine the P images closer to the query. We
imagine to attach a spring of length E(XI, images I and J.
The spring is attached only if the distance between I and J in the feature space is less than
a threshold . If the distance is greater than , the two images are left disconnected. That
is, their distance in the display space is left unconstrained. The use of the threshold can be
shown to create a more structured display space []. The operator is the solution of the
following optimization problem
E( (xI), (xJ )))2 (42)
I, J C
E((xI), (xJ
In practice, of course, the operator is only defined by the positions in which the images are
actually projected, so that the minimization problem would rewrite as
XI :II
I, J C
E(XI, XJ ) <
Standard optimization techniques can be used to solve this problem. In our prototype we use
the simplex method described in [11].
6.2 Query Operator
The query operator solves the dual problem of deriving the metric of the query space from the
examples that the user gives in the display space. Let us assume that the user has selected, as
part of the interaction, a set D of images that are deemed relevant. The relative position of the
images in the display space (as determined by the user) gives us the values
D. The determination of the query space metric is then reduced to the solution of the
optimization problem

I,JD
Note that this is the same optimization problem as in (43), with the exception of the set of
images that are considered relevant (in this case it is the set D of selected images, rather than
the set of displayed images), and the optimization is done over rather than over the projection.
The latter dierence is particularly relevant, since in general it makes the problem severely
underconstrained. In most cases, the vector can contain a number of parameters of the order
of 100, while the user will select possibly only a few images. In order to regularize the problem,
we use the concept of natural distance.
We define one natural distance for every feature space, the intuition being that the natural
distance is a uniform and isotropic measure in a given feature space. The details of the determination
of the natural distance depend on the feature space. For the remainder of this section,
let N be the natural distance function in a given feature space F, and let F be a distance
functional defined on the space of distance functions defined on F. In other words, let F (f)
be the logical statement
y, z F (d(x, y) 0 d(x,
(i.e. F (f) is true if f is a distance function in the space F). Let
The set of distance functionals in D2(F) is then

Note that for the functions F we do not require, at the present time, the satisfaction of the
distance axioms. That is, we do not require D2(F)(F ). Whether this assumption can be
made without any negative eect is still an open problem.
If we have identified a function F (we will return to this problem shortly), then the metric
optimization problem can be regularized (in the sense of Tihonov [21]) as

I,JD
that is, we try to find a solution that departs as little as possible from the natural distance in
the feature space.
For the definition of the function F , an obvious candidate is the square of the L2 metric
in the Hilbert space of distance functions:
x,y
In practice, the integral can be reduced to a summation on a sample taken from the database,
or to the set of images displayed by the database.
An alternative solution can be determined if the natural distance N belongs to the family
of distance functions f(.; ) that is, if there is a parameter vector 0 such that, for all x, y,
and if the function y. Note
that, since the only thing that changes in the family of distances f is the parameters vector
, we can think of F (f) as a function of the parameters: F (). Because of the regularity
hypothesis on f, F () is also regular in 0. In this case, we can write

,

where H is the Hessian of the function F . Since F is the square of a regular function, we
have The Hessian contains elements of the form


x,y   f(x,
x,y  0
If we define the matrix
x,y  0
we have a regularization problem of the type

I,JD
This form is particularly convenient since the matrix depends only on the natural distance
of the feature space, and therefore can be precomputed.
7 The Interface at Work
We have used the principles and the techniques introduced in he previous section for the design
of our database system El Nin~o[18, 20].
The feature space is generated with a discrete wavelet transform of the image. Depending on
the transformation group that generates the transform, the space can be embedded in dierent
manifolds. If the transformation is generated by the two dimensional ane group, then the
space has dimensions x, y, and scale, in addition to the three color dimensions R, G, B. In this
case the feature space is dieomorphic to IR6.
In other applications, we generate the transform using the Weyl-Heisenberg group [15, 22],
obtaining transformation kernels which are a generalization of the Gabor filters [7]. In this case,
in addition to the six dimensions above we have the direction of the filters, and the feature
space is dieomorphic to IR6  S1. After Vector Quantization, an image is represented by a
number of coecients between 50 and 200 (depending on the particular implementation of El
Nin~o).
El Nin~o uses a class of metrics known as Fuzzy Feature Contrast model [19], and
derived from Tversky's similarity measure [23]. Consider an n-dimensional feature space (in
our case for the ane group, and for the Weyl-Heisenberg group). We define two
types of membership functions, the first of which is used for linear quantities, the second for
angular quantities, like the angle of the Weyl-Heisenberg group.
Let xi and yi be two elements in this feature space. In other words, xi and yi are the
components of one of the coecients that define images X and Y . Define the following
and
and the quantities
xi, yi are linear features (56)
xi, yi are angular features
xi, yi are linear features
xi, yi are angular features
The distance between the two coecients is defined as

where > 0 is a weighting coecient.
The determination of the distance between two coecients depends on 13 parameters for
the six-dimensional feature space and on 15 parameters for the seven-dimensional feature space
(viz. the i's, the i's, and ). These distances must be inserted in the distance function (41).
For an image represented by 100 coecients, this would bring the total number of parameters to
up to 1,500. This large number of parameters makes the regularization problem unmanageable.
In order to reduce this number, we have collected the coecients in 10 bins, depending on their
location in the coecient space, and enforce equality of parameters within a bin. This brings
the number of independent parameters to less than 150. These parameters are set by the query
operator based on the user interaction by solving the optimization problem (48).
In El Nin~o we use two types of image selections, represented as a rectangle around the
image and as a cross, respectively. The dierence between the two is in the type of parameters
that they contributer to determine. The parameters i individuate a point in the feature space
around which the query is centered. All the other parameters determine the shape of the
space centered around this point. We noticed early on in our tests that users would like to
select images that are not relevant for their query in order to give the database a distance
reference between the query images and the rest of the database. Therefore, we introduced the
cross-selected images that contribute to the adaptation of all the parameters except the i.
The interface of El Nin~o is shown in Fig. 6 with a configuration of random images displayed.
In a typical experiment, subjects were asked to look for a certain group of car images, that
look like the image in Fig. 7 (not necessarily that particular one). The car was showed to the
subjects on a piece of paper before the experiment started, and they had no possibility of seeing
it again, or to use it as an example for the database. This procedure was intended to mimick
in a controlled way the vague idea of the desired result that users have before starting a query.
In the display of Fig. 6 there are no cars like the one we are looking for, but there are a couple
of cars. The user selected one (the subjectively most similar to the target) and marked another
one with a cross. The second car image will be used to determine the similarity measure of the
database, but it will not be considered a query example (the database will not try to return
images similar to that car).
After a few interaction, the situation is that of Fig. 8 (for the sake of clarity, from now on
we only show the display space rather than the whole interface). Two images of the type that
we are looking for have appeared. They are selected and placed very close to one another. A
third car image is placed at a certain distance but excluded from the search process. Note that
the selection process is being refined as we proceed. During some of the previous interactions,
the car image that is now excluded was selected as a positive example because, compared to

Figure

The interface of El Nin~o with the beginning of a search process.
what it was presented at the time, it was relatively similar to our target. Now that we are
zeroing in to the images that we are actually interested in, the red car is no longer similar to
what we need.
At the next iteration, the situation is that of Fig. 9. At this time we have a number
of examples of the images we are looking for. Further iterations (e.g. with the selection
represented in the figure) can be used to obtain more examples of that class of images. Note
that the negative examples are placed much farther away from the positive examples than
in the previous case. This will lead to a more discriminating distance measure which, in eect,
will try to zoom in the class of images we are lookig for.
During this interaction, the subjects' idea of what would be an answer to the query changed
continuously as they learned what the database had to oer, and redefined their goals based
on what they saw. For instance, some of the positive examples that the subjects used at the
beginning of the query-when their ideas were more generic and confused-are not valid later

Figure

7: One of our target images.
on, when they have a more precise idea of what they are looking for.
This simple experiment is intended only to give a flavor of what interaction with a database
entails, and what kind of results we can expect. Evaluation of a highly interactive system like
El Nin~o is a complex task, which could be the subject of a paper of its own. The interested
reader can find some general ideas on the subject in [17].
Conclusions
In this paper we have defined a new model of interface for image databases. The motivation
for the introduction of this model comes from an analysis of the semantics of images in the
context of an image database. In traditional databases, the meaning of a record is a function
from the set of queries to a set of truth values. The meaning of an image, on the other hand,
is a function from the cartesian product of the feature space times the set of queries to the
positive real values. This definition embodies the observation that the meaning of an image
can only be revealed by the contraposition of an image with other images in the feature space.
These observations led us to define a new paradigm for database interfaces in which the role
of the user is not just asking queries and receiving answer, but a more active exploration of the
image space. The meaning of an image is emergent, in the sense that it is a product of the dual
activities of the user and the database mediated by the interface.
We have proposed a model of interface for active exploration of image spaces. In our
interface, the role of the database is ot focus the attention of the user on certain relation that,
given the current database interpretation of image meanings, are relevant. The role of the user
is exactly the same: by moving images around, the user focuses the attention of the database
on certain relations that, given the user interpretation of meaning, are deemed important.
Our interface is defined formally as a set of operators that operate on three spaces: the
feature space, the query space, and the display space. We have formalized the work of an
interface as the action of an operators algebra on these spaces, and we have introduced a
possible implementation of the most peculiar operators of this approach.
Finally, a word on performance. Evaluating the performance of an interactive system like
this is a rather complex task, since the results depend on a number of factors of dicult
characterization. For instance, a system with a more ecient indexing (faster retrieval) but a
weaker presentation can require more iterations-and therefore be less ecient-than a slower
system with a better interface. A complete characterization of the performance of the system
goes beyond the scope of this paper, but we can oer a few observations. An iteration in a
system with our interface entails two steps: a k-nearest neighbors query to determine the k
images that will be presented to the user, and the solution of an optimization problem to place
them in the interface. The optimization problem is O(k2), but its complexity is independent
of the number of images in the database (it depends only on the number of images that will
be shown). Therefore, we don't expect it to be a great performance burden, not to present
scalability problems. Early evaluations seem to support these conclusions.


--R

Computer analysis of TV spots: The semiotics per- spective
A Theory of Semiotics.
Art and Illusion.
In search of information in visual media.
The art of Color.
Fast multiresolution image querying.


Texture features for browsing and retrieval of image data.

Numerical Recipes
Dimensionality reduction for similarity searching in dynamic databases.

Introduction to lie Groups and Lie Algebras.
Explorations in Image Databases.
Distance preservation in color image transforms.
Evaluation vademecum for visual information systems.

Similerity measures.
User interfaces for emergent semantics in image databases.
Regularization of incorrectly posed problems.

Features of similarity.
--TR

--CTR
Jeannie S. A. Lee , Nikil Jayant, Mixed-initiative multimedia for mobile devices: a voting-based user interface for news videos, Proceedings of the 14th annual ACM international conference on Multimedia, October 23-27, 2006, Santa Barbara, CA, USA
Philippe H. Gosselin , Matthieu Cord, Feature-based approach to semi-supervised similarity learning, Pattern Recognition, v.39 n.10, p.1839-1851, October, 2006
W. I. Grosky , D. V. Sreenath , F. Fotouhi, Emergent semantics and the multimedia semantic web, ACM SIGMOD Record, v.31 n.4, December 2002
Baback Moghaddam , Qi Tian , Neal Lesh , Chia Shen , Thomas S. Huang, Visualization and User-Modeling for Browsing Personal Photo Libraries, International Journal of Computer Vision, v.56 n.1-2, p.109-130, January-February 2004
Jamie Ng , Kanagasabai Rajaraman , Edward Altman, Mining emergent structures from mixed media For content retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
Rahul Singh , Rachel Knickmeyer , Punit Gupta , Ramesh Jain, Designing experiential environments for management of personal multimedia, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
Ricardo S. Torres , Celmar G. Silva , Claudia B. Medeiros , Heloisa V. Rocha, Visual structures for image browsing, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
Steffen Staab, Emergent Semantics, IEEE Intelligent Systems, v.17 n.1, p.78-86, January 2002
Zoran Steji , Yasufumi Takama , Kaoru Hirota, Genetic algorithm-based relevance feedback for image retrieval using local similarity patterns, Information Processing and Management: an International Journal, v.39 n.1, p.1-23, January
Rahul Singh , Zhao Li , Pilho Kim , Derik Pack , Ramesh Jain, Event-based modeling and processing of digital media, Proceedings of the 1st international workshop on Computer vision meets databases, June 13-13, 2004, Paris, France
Giang P. Nguyen , Marcel Worring, Query definition using interactive saliency, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California
Philippe H. Gosselin , Matthieu Cord, A comparison of active classification methods for content-based image retrieval, Proceedings of the 1st international workshop on Computer vision meets databases, June 13-13, 2004, Paris, France
Giang P. Nguyen , Marcel Worring , Arnold W. M. Smeulders, Similarity learning via dissimilarity space in CBIR, Proceedings of the 8th ACM international workshop on Multimedia information retrieval, October 26-27, 2006, Santa Barbara, California, USA
John Restrepo , Henri Christiaans, From function to context to form: precedents and focus shifts in the form creation process, Proceedings of the 5th conference on Creativity & cognition, April 12-15, 2005, London, United Kingdom

Jos L. Bosque , Oscar D. Robles , Luis Pastor , Angel Rodrguez, Parallel CBIR implementations with load balancing algorithms, Journal of Parallel and Distributed Computing, v.66 n.8, p.1062-1075, August 2006
Lina Zhou, Ontology learning: state of the art and open issues, Information Technology and Management, v.8 n.3, p.241-252, September 2007
interactive databases;relevance feedback;man-machine interface;image databases;content-based image retrieval