Similarity Measures.
AbstractWith complex multimedia data, wesee the emergence of database systems in which the fundamental operation is similarity assessment. Before database issues can be addressed, it is necessary to give a definition of similarity as an operation. In this paper, we develop a similarity measure, based on fuzzy logic, that exhibits several features that match experimental findings in humans. The model is dubbed Fuzzy Feature Contrast (FFC) and is an extension to a more general domain of the Feature Contrast model due to Tversky. We show how the FFC model can be used to model similarity assessment from fuzzy judgment of properties, and we address the use of fuzzy measures to deal with dependencies among the properties.
Introduction
Comparing two images, or an image and a model, is the fundamental operation for many Visual
Information Retrieval systems. In most systems of interest, a simple pixel-by-pixel comparison
won't do: the difference that we determine must bear some correlation with the perceptual difference
of the two images, or with the difference between two adequate semantics associated to the two
images.
Measuring meaningful image similarity is a dichotomy that rests on two elements: finging a set
of features which adequately encodes the characteristics that we intend to measure, and endowing
the feature space with a suitable metric. Since the same feature space can be endowed with an
infinity of metrics, the two problems are by no means equivalent, nor does the first subsume the
second.
In this paper we consider the problem of measuring dissimilarities in feature spaces. In a number
of cases, after having selected the right set of features, and having characterized an image as a point
in a suitable vector space, researchers make some uncritical and unwarranted assumption about
the metric of the space. Typically, the feature space is assumed to be Euclidean.
We set to analyze alternatives to this assumption. In particular, we will analyze some similarity
measures proposed in the psychological literature to model human similarity perception, and will
show that all of them challenge the Euclidean distance assumption in non trivial ways.
We will consider the problem of (dis)similarity measurement, as opposed to matching . Matching
and dissimilarity measurement are not seldom based on the same techniques, but they differ in
emphasis and applications. Matching techniques are developed mostly for recognition of objects
To appear on IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999
under several conditions of distortion [22]. Similarity measures, on the other hand, are used in
applications like image databases, in which the query image is just a very partial model of the
user's desires and the user looks for for images similar, according to some defined criterion, to it [1].
In query by example, the user selects an image, or draws a sketch, that reminds her in some way of
the image she wants to retrieve. Images similar to the example according to the given criteria are
retrieved and presented.
In a typical matching application, we expect a comparison to be successful for images very
close to the model, and unsuccessful for images different from the query. The degree of similarity
of images different from the model is of no interest to us, as long as it remains below a suitable
acceptance threshold. On the other hand, database applications require a similarity measure that
will accurately predict perceptual similarity for all images "reasonably" similar to the query.
This paper presents and analyzes various definitions of similarity measures for feature spaces.
We will specifically consider the determination of similarity between images, but the measures that
we present apply in more general situations. It is obviously impossible to decouple the choice
of the similarity measure from the choice of features. In this paper, however, we will leave the
features in the background. There is an extensive literature that deals with the choice of features
for most problems of interest, and to which we refer the reader [8, 9]. We are interested in finding
characteristics of the distance measure that are relatively independent of the choice of the feature
space.
This paper is organized as follows. Section 2 is an overview of psychological models of similarity.
Section 3 introduces our Fuzzy Feature Contrast model, which is the extension of one of the
psychological models from Section 2. Section 4 presents some evaluation of the model. Conclusions
are drawn in Section 5.
Theories
In this section, we present some results on human similarity judgment introduced by psycholo-
gists, and discuss merits and flaws of the various approaches. We try to put all these theories in
perspective, and collect them in a unified framework.
The most important concept to do so is that of geometric distance and the related distance
axioms. Theories differ in the way they deal with the properties of geometric distance, and by the
number and nature of distance axioms they accept or refuse. The next subsection discusses the
distance axioms from the perspective of similarity measurements.
2.1 The metric axioms
A number of similarity measures proposed in the literature explain similarity (or, more properly,
dissimilarity) as a distance in some suitable feature space 1 , that is assumed to be a metric space.
A distinction is made between perceived similarity, d, and judged similarity, ffi [2]. If A and B
are the representations of the stimuli a and b in the feature space, then d(A; B) is the perceptual
1 The (metric or otherwise) space in which the stimuli are represented is referred to using a number of different
names, not necessarily equivalent, from perceptual space to psychological space. We will adhere to the generic name
feature space.
distance between the two, while the judged distance is
being a suitable monotonically non-decreasing function of its argument. Note that only the judged
distance ffi is accessible to experimentation.
Stimuli are represented as points in a metric space, and d(A; B) is the distance function of this
space ([20, 24].) This model postulates that the perceptual distance d satisfies the metric axioms,
the empirical validity of which has been experimentally challenged by several researchers.
The first requirement for a distance function is that
for all stimuli (constancy of self-similarity.) This hypothesis can be tested using the judged sim-
ilarity, since it implies ffi(A; B). The constancy of self-similarity has been refuted by
Krumhansl [11].
A second axiom of the distance model is minimality:
again, this hypothesis is open to experimental investigation since, due to the monotonicity of the
relation between d and ffi, it implies ffi(A; B) - ffi(A; A). Tversky [25] argued that this assumption
is violated in some recognition experiments.
A third axiom states that the distance between stimuli is symmetrical:
Just as in the previous cases, this axiom is subject to experimental investigation, since it implies
number of investigators have attacked this assumption with direct similarity
experiments [16] and observing asymmetries in confusion matrices [17]. This phenomenon has been
often attributed to the different "saliency" or "goodness of form" of the stimuli. In general, the
less salient stimulus is more similar to the more salient (more prototypical) than the more salient
stimulus is similar to the less salient [25].
The final metric axiom is the triangle inequality:
Epistemologically, this is the weakest axiom. The functional relation between d and ffi does not
guarantee that satisfaction or violation of the triangular inequality for d will translate into a similar
property for ffi.
The ordinal relation between distances is invariant with respect to all the transformations of
the type (1) if g is monotonically increasing. A consequence of this is that the triangular inequality
cannot be tested based on ordinal measurements only. It is however generally acknowledged that
at least for some types of stimuli the triangular inequality does not hold [2, 26].
Tversky and Krantz [27] proved that, if the distance axioms are verified, and the distance is
additive along straight lines in the feature space, then d is a Minkowski distance, that is, a distance
of the form:
BN g, and p ? 0 is a constant which characterizes the
distance function.
From these notes, it seems like the situation for geometric models is quite desperate: of the four
basic axioms of the distance function, two are questionable, one is untenable, and the fourth is not
ascertainable.
In spite of these problems, metric models are widely used in psychology, with some adjustments
to account for the failure of the distance axioms.
2.1.1 The debatable Euclidean nature of Perception
In a very influential 1950 paper [3], Fred Attneave investigated the perception of similarity among
a group of rectangles that were allowed to change along two dimensions: area and tilt. The results
were inconsistent with the Euclidean model of distance, but partial agreement was found with a
city-block distance model of the type
where the two dimensions of the feature space represent area and tilt angle. Attneave found some
discrepancy in the predictions of the model, which he attributed to nonlinearities in the feature
space.
An important class of metric models was introduced by by Thurstone [23] and Shepard [21].
Shepard's model is based on generalization data 2 : given a series of stimuli S i and a corresponding
series of learned responses R i , the similarity between S i and S j (in the absence of any bias) is
related to the probability that the stimulus S i elicit the response associated with stimulus
Shepard does not work directly with these quantities, but uses normalized and symmetric generalization
data, defined as:
The model assumes that the generalization data are generated as:
where g is the generalization function, and d is a suitable perceptual distance between the two
stimuli.
Shepard assumed that there exists, for each type of stimulus, a suitable underlying feature space
such that (1) the function g is universal (it has the same form for all the types of stimuli), and
(2) the function d is a metric. Note that, without the second requirement, the condition can be
trivially satisfied for any monotonically decreasing function
2 The term generalization is used here in a slightly different way than in most Machine Learning papers. In ML,
generalization means usually a correct inference whereby the response appropriate in a given situation is extended to
cover other situations for which that response is suitable. In Shepard's papers, generalization refers to the incorrect
extension of a response from the stimulus for which it was intended to other similar stimuli.
If we assume that the function g is monotonic, then from the generalization data g ij it is possible
to derive the ordering of the stimuli in the perceptual space with respect to any arbitrary reference.
Shepard uses ordering data, and nonmetric multidimensional scaling [24] to determine the lowest
dimensional metric space that can explain the data. He assumes this space as the feature space
for the model. There is good agreement with the experimental data if the feature space has a
Minkowski metric (defined in (6)), and the generalization function is exponential:
One important observation, at the core of Shepard's 1987 paper [21] is that, given the right
feature space, the function g is universal that is, the same exponential behavior (with different
values of the parameter - in (10)) can be found in the most diverse situations, ranging from visual
stimuli to similarity of pitch in sounds.
A relevant qualitative characteristic of the model is that, as two stimuli grow apart in the feature
space, the dissimilarity 1 \Gamma g(d) does not increase indefinitely, but it flattens out to a finite limit.
A detailed discussion of of the properties of the Thurstone-Shepard model can be found in [7].
2.2 Abandoning the distance axioms
The distance axioms seem to provide an unnecessarily rigid system of properties for similarity
measures. In particular, it seems epistemologically futile to impose on the perceptual distance d
some properties-like the triangle inequality-that may fail to translate into similar properties of
the judged similarity ffi and are therefore beyond experimental validation. We propose the following
definition regarding the epistemologically valid properties for perceptual distance functions:
D be the class of monotonically increasing functions from IR to IR. A logic
predicate P over the distance functions d is an ordinal property if, for all
Tversky and Gati [26] identified three ordinal properties, and used them to replace the metric
axioms in what they call a monotone proximity structure. Suppose, for the sake of simplicity,
that the feature space has two dimensions x and y, and let d(x 1 y be the perceived distance
between the stimuli proximity structure is characterized
by three properties:
Dominance: i.e. the two dimensional dissimilarity
exceeds both one dimensional projections of that distance.
Consistency: for all x
and
that is, the ordinal relation between dissimilarities along one dimension is independent of the
other coordinate.
To introduce the third property, we give the following definition:
is said to be between x 1 and
Note that, in view of consistency, "betweenness" is well defined since it is independent of the
coordinate y that appears in the definition.
The third property of a monotone proximity structure is the following:
Transitivity: If x 1 jx 2 jx 3 and x 2 jx 3 jx 4 , then it is x 1 jx 2 jx 4 and x 1 jx 3 jx 4 .
This framework is more general than the geometric distance: while all distance measures have
dominance, consistency, and transitivity, not all the proximity structures satisfy the distance ax-
ioms. Dominance is a weak form of the triangle inequality that applies along the coordinate axes.
Consistency ensures that certain ordinal properties related to the ordering of the features x do not
change when y is changed (see [18] for details.) Transitivity ensures that the "in between" relation
behaves as in the metric model, at least when moving along the axes of the feature space.
Note that in the Euclidean model-which is isotropic-every property holds (or does not hold)
for a series of collinear points irrespective of the direction of the line that joins them. In measuring
the perceptual distance, the directions of the feature axes have a special status.
Most of the distance measures proposed in the literature, as well as the feature contrast model
predict that dominance consistency and transitivity hold.
To help discriminate among the different models, Tversky and Gati proposed a fourth ordinal
axiom, that they call the corner inequality. If x 1 jx 2 jx 3 and y 1 jy 2 jy 3 , the corner inequality holds if
and
or
and
From Fig. 1 it is easy to see that the corner equality holds if the "corner" path from x 1 y 1 to x 3 y 3
is longer than the diagonal path. Minkowski metrics satisfy the corner inequality, so observed
violations of the corner inequality would falsify models based on Minkowski metrics. Tversky and
Gati present evidence that, under certain conditions, experiments show violations of the corner
inequality, thus seemingly invalidating most geometric models of similarity.
2.2.1 Set-Theoretic Similarity
In a 1977 paper [25], Amos Tversky proposed his famous feature contrast model. Instead of considering
stimuli as points in a metric space, Tversky characterized them as sets of binary features.
In other words, a stimulus a si characterized by the set A of features that the stimulus possesses.
Equivalently, a feature set is the set of logic predicates which are true for the stimulus in question.
Let a, b be two stimuli, A, B the respective sets of features, and s(a; b) a measure of the similarity
between a and b. Tversky's theory is based on the following assumptions:
x yx y
x y

Figure

1: The corner inequality; the "corner" path x 1 longer than the path
is inside the rectangle.
Matching:
Monotonicity: A.
A function that satisfies matching and monotonicity is called a matching function. Let the
expression F (X; Y; Z) be defined whenever there are A, B such that
exist X;Y; Z such that one or more of the following holds:
F (X; V;
The pairs of stimuli (a; b) and (c; d) are said to agree on one (two, three) components whenever
one (resp. two, three) of the following hold:
Based on these definitions, Tversky postulates a third property of the similarity measure:
Independence: Suppose the pairs (a; b) and (c; d), as well as the pairs (a
the same two components, while the pairs (a; b) and (a d) and (c
on the remaining (third) component. Then:
We refer to [25] for details. An example of independence is in Fig. 2. In this case, the independence
property states that if (a; b) are "closer" than (c; d), then (a
hypothesis, with some caveat about the selection of features, can be checked experimentally.
The main result of Tversky's paper is the following representation theorem:
a b a' b'
c d c' d'

Figure

2: An example of independence. If a and b are considered more similar than a 0 and b 0 , then
c and d will appear more similar than c 0 and d 0
Theorem 1 Let s be a similarity function for which matching, monotonicity and independence
hold. Then there are a similarity function S and a non-negative function f and two constants
This result implies that any similarity ordering that satisfies matching, monotonicity and independence
can be obtained using a linear combination (contrast) of a function of the common
features and of the distinctive features This representation is called
the contrast model.
This model can account for violation of all the geometric distance axioms. In particular, S(a; b)
is asymmetric if ff 6= fi. If S(a; b) is the answer to the question "how is a similar to b?" then, when
making the comparison, subjects focus more on the features of a (the subject) than on those of
b (the referent.) This corresponds to the use of Tversky's measure with ff ? fi: in this case the
model predicts
this implies that the direction of the asymmetry is determined by the relative "salience" of the
stimuli: if b is more salient than a, then a is more similar to b than vice versa. In other words,
the variant is more similar to the prototype than the prototype to the variant, a phenomenon that
confirmed experimentally. In addition, the feature contrast model accounts for violation
of the corner inequality.
3 Fuzzy Set-theoretic Measures
Tversky's experiments showed that the feature-contrast model has a number of desirable properties,
most noticeably, it explains violation of symmetry and of the corner equality.
One serious problem for the adoption of the feature-contrast model in visual information systems
is its characterization of features. In Tversky's theory, each stimulus is characterized by the presence
or absence of features. This convention forces Tversky to adopt complex mechanisms for the
representation of numerical quantities. For instance, positive quantities-such as a length-are
discretized into a sequence l i and represented as a collection of feature sets such that if l 1
. Quantities that can be either positive or negative are represented by
even more complex constructions.
In computer vision, the assumption of binary features would leave us with the problem of
evaluating logic predicates based on some continuous and noisy measurements, yielding brittle and
unreliable features.
In the next subsection we introduce the use of fuzzy predicates in the feature contrast model.
The use of fuzzy logic will allow us to extend Tversky's results to situations in which modeling by
enumeration of features is impossible or problematic.
Not all the stimuli influence similarity perception according to the same mechanism [2]. Tver-
sky's feature contrast model applies to a particular type of features: those can be expressed as
predicates over the stimuli domain. In this section we will consider only this type of features. A
unification of all types of stimuli in a geometric framework can be found in [19].
3.1 Fuzzy features contrast model
Consider a typical task in computer vision: assessing the similarity between faces. A face is
characterized by a number of features of different types but, for the following discussion, we will
only consider geometric features like the size of the mouth, the shape of the chin, and so on.
A predicate like the mouth of this person is wide can be modeled as a fuzzy predicate whose
truth is based on the measurement of the width of the mouth. For instance, we can measure the
width of the mouth x in Fig. 3.a and use two truth functions (see below) like those in Fig. 3.b to
determine the truth value of the predicates "the mouth is wide" and "the mouth is narrow."
"x is small"01
(a) (b)
"x is big"
x/a
x/a
a
x

Figure

3: Determination of the truth value of the predicates "the mouth is wide" and "the mouth
is narrow." The width of the mouth x is measured and normalized with respect to the distance
between the eyes a. Then, two membership functions are used to determine the truth value of the
two predicates.
In general, we have an image I and a number of measurements OE i on the image. We want to use
these measurements to assess the truth of n fuzzy predicates. Some care must be taken to define
the truth value of a fuzzy predicate. We use the following definition:
Let\Omega be a set, and OE
a set of measurements on the elements
of\Omega . Let
P! be a predicate about the element !
2\Omega . The truth of the predicate P! is
In the example above, for instance, we say that the truth value of the predicate "The mouth of
X is wide" depends on measurements of the face (viz. the measurement of the mouth width.)
From the measurements OE we derive the truth values of p fuzzy predicates, and collect them
into a vector:
We call -(OE) the (fuzzy) set of true predicates on the measurements OE. The set is fuzzy in that a
predicate belongs to -(OE) to the extent - j (OE).
In order to apply the feature contrast model to the fuzzy sets -(OE) and -(/) of the predicates
true for the measurements OE and /, we need to choose a suitable salience function f , and compute
the fuzzy sets -(OE) "
We assume that the saliency of the fuzzy set is given by its cardinality:
The intersection of the sets -(OE) and -(/) is defined in the traditional way:
The difference between two sets A and B is traditionally defined as maxf-A g. This
definition, however, leads to some undesired effects [18] that can be avoided by requiring that the
relation continue to hold in our fuzzy domain. A possible definition that makes the
relation true is:
With these definitions, we can write the Tversky's similarity function between two fuzzy sets
-(OE) and -(/) corresponding to measurements made on two images as:
The Tversky dissimilarity is defined as
We refer to the model defined by eq. (23) and (24) as the Fuzzy Features Contrast
It is easy to see that the fuzzy feature contrast model can be asymmetric (if ff 6= fi.) It is also
easy to find an example of violation of the corner inequality. Consider Fig. 1 with x
1. Let the membership function in the FFC model be
Then we have:
1Condition 13 is violated if fi ? fiand while condition 14 is violated if fi ? 3fi \Gamma1and
fi. Thus, the corner inequality is violated for fi ! 1.
A property similar to the representation theorem can be proven for the fuzzy case. Let y 2 IR
and
Then the following theorem holds:
Theorem 2 Let F : be an analytic function such that the following properties hold:
1. F (x; y; z) is monotonically nondeincreasing in x and monotonically nonincreasing in y and
z. The partial derivatives of F are nonzero almost everywhere.
2. For all
3. For all s, the sets ftjF are closed in the product topology of
4. F (y i
Then there are functions G
and F (x;
Proof (sketch)
By theorem 3 in [5], continuity and conditions 1-3 guarantee that F can be written as
with V monotonically increasing. Because of monotonicity, V is irrelevant for ordinal properties,
and F can be replaced by
~
Property 4 (which is analogous to Tverky's [25]) implies that, for i 6= j,
By the monotonicity properties of F , the derivatives of f i and f j have either the same sign or
opposite signs for all the values for which they are non zero. Assume, without loss of generality,
that they have the same sign. Also, since the derivatives are zero almost everywhere, then for
almost all x 1 and almost all y 1 it is possible to find x 2 and y 2 for which (30) holds. Considering
two sequences y implies, in the limit of n !1,
almost everywhere. By fixing y 1 , this implies that f 0
almost everywhere, so, by
continuity, f i (note that the form (29) implies that, if condition 4 holds for one
u, it holds for all u). The constants c i can be collected together and eliminated, since they are
irrelevant for ordering. fl
The complete proof of this theorem can be found in [18].
3.2 Feature Dependencies
Our translation of Tversky's measure suffers from a serious drawback: it considers all the features
as independent. For instance, in our model the truth of the statement "the mouth is wide" depends
only on the width of the mouth, and not on the other measurements. This independence property
is easily proved to be false for human perception. For instance, in the famous visual illusion of
(a)
(b)

Figure

4: A proof that the truth of a fuzzy predicate can depend on measures of quantities different
from the subject of the predicate: in this case, the truth of the predicate "the line is long" must
be different in the two cases, since the predicate "line A is longer than line B" has a truth value
different from zero. Yet, the length of the two lines is the same. Therefore, the truth of the
predicate depends on other measures.
Fig. 4, the line (a) appears longer than the line (b), although measurement reveals that the two
have the same length. This has important consequences for our fuzzy definition.
Let us assume that the the truth of the predicate "line A is longer than line B" is given by a
fuzzy inference rule like
If line A is long and line B is short, then line A is longer than line B.
We will use the following fuzzy implication rule: if we have two predicates "X is A," with a
truth value -A (X), and a predicate "Y is B," with a truth value -B (Y ), then the truth value of
the implication "if X is A then Y is B" is given by:
be the truth value of the predicate "line A is longer than line B," and -A , -B be the
truth values of the predicates "line A is long" and "line B is long" respectively. We have:
Since the predicate "line A is longer than line B" is perceived as true, we have
the implication is valid, therefore, -) ? 1=2. This implies
This relation must be true for all the values of -A . In particular, the effect is strong when the line
A is not judged neither "long" nor "short" that is, when 1=2. In this case, for the inequality
to be true, we must have -B ! 1=2 that is line B is perceived as shorter than line A.
This fact cannot be explained if the arguments of -A and -B are simply the length of the
respective lines. But since the length of a line can be judged when the line is presented in isolation,
the values -A and -B must be completely determined by the length of the respective lines.
We assume that the truth of each predicate is not affected by the truth of other predicates, but
the way the predicates interact is: if two predicates tend to be true together, they reinforce each
other. This model applies to the following situation: imagine you know the length of the segment
(a) in Fig. 4 (possibly its length relative to the whole figure); then you can express a judgment on
whether the predicate "segment (a) is long" is true. This judgment does not depend on the other
features on the image, and, if x is the length of the segment, it is has truth value - a
However, when the whole image is perceived, the length of the segment is perceived differently
depending on the presence or absence of other features (like the existence of outwardly pointing
diagonal segments.) We postulate that, although the truth of the predicate "the horizontal line is
long" is still the same, the measure of the set of true features is changed because of the interaction
between different predicates.
The latter model can be defined mathematically by replacing the function f in the definition
of the fuzzy feature contrast similarity with a fuzzy integral defined over a suitable fuzzy measure.
We use a Choquet Integral, and a fuzzy measure that models the interaction between the different
predicates [15].
be a finite universe. A fuzzy measure m is a set function
subsets A and B of X, A ' B )
indicates the power set of X that is, the set of all subsets of X.
be a fuzzy measure on X. The discrete Choquet integral of a function f :
with respect to m is defined as:
Z
where the notation : (i) means that the indices have been permutated so that
defined to be 0, and
Let X be the universe of fuzzy predicates x is a measurement vector, and
- i the truth function for the i-th predicate. Also, let f be the identity function us
suppose, for the ease of notation, that the predicates are already ordered so that
and let us define the dummy predicate - 0 that is always false, i.e. - 0
Lemma 1 The fuzzy cardinality of the set of true predicates is equal to n times the Choquet integral
of the identity function when m is additive and equidistributed (i.e. sets of the same cardinality
have equal
Proof:
is equidistributed, we have m(f- i because of additivity,
we have
therefore, the Choquet integral can be written as:
Z
=n
which, since - by definition, is the desired result. fl
Thus, when the measure is additive and equidistributed, the Cocquet integral reduces to the
cardinality of the fuzzy set, which is the saliency function we used in (23.) To see how we can use a
non-additive measure to model dependence between predicates, suppose that all the predicates are
independent except for - n\Gamma1 and - n . Assume that the fact that - n is true increases the possibility
that - n\Gamma1 be also true. Referring to Fig. 4, the two predicates might be:
diagonal lines point strongly outward."
horizontal line is long."
What is the effect of this dependency on the fuzzy measure? Since the perception of the outwardly
pointing diagonal lines increases the perception of the length of the line, the predicate P 2 is, in a
sense, "more true" due to the truth of P 1 . In terms of the fuzzy measure, we can say that it is:
where is a coefficient that models the dependence between the two predicates. Consider
an equidistributed measure:
with the dependency between x
Also, suppose that all the other measures are additive, that is
if either x n\Gamma1 or x n do not belong to fx i 1
g, and
if they do.
When we compute the Choquet integral, we order the predicates by their truth value. Suppose
that the value -(x n\Gamma1 ) is the h-th in the ordering, and that -(x n ) is the k-th
In this case, in the Choquet integral, there will be subsets that
contain both x n\Gamma1 and x n , therefore:
Z
In the following, we will assume a fuzzy measure of the form:
Y
The
uniquely characterize the measure, and must be
determined experimentally.
The fl parameters must let the measure satisfy the three requirements of definition 4. In
particular, the measure of a set must be greater or equal the measure of all its subsets. Let us
consider, without loss of generality, the two sets
Then we have:
Y
Y
By definition of fuzzy measure, it must be m(B) - m(A) and, therefore,
Y
Y
From this relation it is possible to derive the relation between fl A and
Y
In the case of an equidistributed measure (m(fx i
whenever A ' B.
Given a fuzzy measure m that takes into account the dependence among features, we can define
the Tversky similarity as:
Z
Z
Z
Both this measure and (23) reduce to the usual Tversky similarity if the features are binary
and the measure is additive and equidistributed.
In this section, we present a comparison between some of the similarity measures introduced so far.
We will consider the Euclidean Distance, the Attneave city-block distance, the Thurstone-Shepard
model, and the Fuzzy feature contrast model.
4.1 Similarity of Faces
In this experiment, we use the similarity measures to characterize the similarity between face-like
stimuli. Similarity of faces is a complex issue, that depend on a number of factors, like the color
and the shape of the hair, the texture of the skin, the geometry of the face components, and so on.
In this experiment, we have chosen a simplified approach, and we will determine similarity based
only on geometric measurements. The features are computed on simple image sketches like those
in Fig. 5. Our set consisted of ten such sketches. The reason for using these sketches rather than
full face images is the poverty of our feature set. Face images contain very important clues that
are not characterized by our geometric features (hair and skin color, etc.) These features tend to
bias the human judgment of faces, so it is impossible to compare the result of human judgment
with those of geomatric features in these conditions. Since we are evaluating similarity measures
and not features, and since the geometric features that we use are powerful enough to characterize
the face sketches that we use, we believe that in this case the simplification is epistemologically
justified.

Figure

5: Three face sketches used in our face similarity experiment.
a
c
d
e

Figure

These 5 measures are taken from a face image to provide support to the fuzzy predicates
used for the similarity assessment.
4.1.1 Distance Measures
The geometric measurements we derive from a face image are described in Fig. 6. All the measurements
are normalized dividing them by the distance between the eyes. These measurements
provide support for the 5 predicates of Tab. 1 (see also [4] for the rationale behind this choice.)
The predicates can be collected in a set of features, and used to compute Tversky similarity. The
Supporting quantity
Long face a
Long chin b
Long nose d
Large face e

Table

1: Predicates used for similarity evaluation, and measured quantities that support their
truth. All these measures are normalized with respect to the distance between the eyes.
FFC similarity model uses the truth value of the predicates, while metric distances are based on
the geometric measurements.
4.1.2 Method
The experiment was organized as follows. We selected 4 subjects with no knowledge of our activity
in similarity measures. Each subject was asked to rank 9 of the sketches (like those in Fig. 5) for
similarity with respect to the 10th (the "query" sketch.) The query sketch was chosen at random,
and each subject was asked to give a total of three rankings with respect to three different query
sketches. Each subject was also asked to divide the ranked images in three groups: the first group
consisted of faces judged "very similar" to the query, the second group consisited of faces judged
"not very similar" to the query, and the third of "completely different" faces. The reason for this
classification will be clear in the following. Whenever possible (for 2 subjects out of 4), the subject
was asked to repeat the experiment with the same query sketches after two weeks, to check for
stability.
The ordering given by any subject was compared with the orders obtained on the same sketch by
the Euclidean distance, the Attneave distance, the Thurstone-Shepard distance, and two versions of
the FFC distance: one without feature interaction and one with feature interaction. We compared
the orderings using the weighted displacement measures proposed in [6].
Assume that we have a query q which operates on a database of n images. We consider the
ordering given by the human subject as the "ground truth." Let L g be this ordering.
In addition, we have a measure of relevance 0 - S(I; q) - 1 such that, for the real order,
In our case, we use the categorization given by the subject as a relevance measure, and set S(I
0:8 for images "very similar" to the query, S(I images "not very similar" to the query,
and images "completely different."
Because of imperfections, the database is not giving us the ordering O t , but an order L
is a permutation of n. The displacement of I i in O d is defined

Table

2: Average (-) and variance (oe 2 ) of the weighted displacement for the 5 measures considered.
A: Attneave. E: Euclid. TS: Thurstone-Shepard. FFC1: Fuzzy Feature contrast without feature
interaction. FFC2: Fuzzy Feature contrast with feature interaction.

Table

3: The F ratio for the pairwise comparison of the similarity measures.
as d q j. The relative weighted displacement of L d is defined as
2c is a normalization factor. W q is zero if L
The results relative to the first subject were used to adjust the parameters of the distances.
For the Thurstone-Shepard model, the best results were obtained when the underlying Minkowski
metric had exponent 2. Since this coincides with the Euclidean distance we decided not to
optimize the Thurston-Shepard model, but to use 0:3 as a contrast to the other metric models.
For the FFC models, the best results were obtained with We also
introduced an interaction between the fatures "long face" and "large mouth", with ~
4.1.3 Results
The results relative to the other three subjects were used for comparison. For every ranking
provided by a subject, the ordering relative to the same query sketch was obtained using each of
the 5 similarity measures and the weighted displacement was computed. The results were then
averaged. Table 2 shows the average and the variance for the 5 similarity measures. In order to
estabilish whether the differences are significant, we performed an analysis of the variance, with
an hypothesis acceptance level . For the whole ensemble we obtained
which leads to the conclusion that the differences are indeed significative. In order to estabilish
which differences are significative, we computed the F ratio for each pair of distances. The results
are shown in Table 3. The difference between two measures should be considered significant if
the F value at the intersection of the respective row and column is greater than 4:75 (for the
determination of this value, see [10].)
3 Given the null hypothesis "all the measures provide the same result," means that we are accepting a 5%
chance of rejecting the null hypothesis what this is in fact true. A 5% level is the norm in psychology and behavioral
sciences.

Table

4: The values for the pairwise -
calculations. The quantity -
measures the fraction of
the variance that is due to actual differences in the experimental conditions, rather than random
variations between the subjects. Most of the values are around 0:5 or greater, indicating a strong
dependence of the variance on actual differences between the similarity measures.
The -
(the fraction of the variance due to actual differences among the measures) gives
the results in Table 4 The quantity -
measures the fraction of the variance that is due to actual
differences in the experimental conditions, rather than random variations between the subjects.
Most of the values are around 0:5 or greater, indicating a strong dependence of the variance on
actual differences between the similarity measures. The results of the comparison between the two
feature contrast measures is not as strong as the difference between these and the other measures,
although a value -
still indicates a significant effect.
This experiment is of course not conclusive, and it represent only a first step in the evaluation
of the similarity measures, for several reasons. First, due to a number of constraints, it was
possible only to check two of our subjects for stability. Since for both the subjects the ordering was
found stable (weighted displacement less than 0.02), we extrapolated to the other subjects. More
importantly, we didn't accurately determine the influence of the parameters on the evaluation,
although partial results seem to indicate that the performance is relatively stable in the presence
of changes. On the other hand, the relatively small number of subjects is not a serious problem in
this case since due to the high value of -
the sensitivity of the experiment is around 0.8, which is
considered an acceptable value [10].
4.2 Similarity of Textures
In this section, we consider the determination of similarity of texture images. Texture identification
is an important problem in computer vision which has received considerable attention (see, for
instance, [13, 14].) In this experiment, we are concerned with texture similarity: given a texture
sample, find similar samples in a database.
We used 100 images from the MIT VisTex texture database [28]. The database contains images
extracted from different classes of textures, like bark, bricks, fabric, flowers, and so on. Textures
were characterized using the Gabor features introduced in [14]. These features work on graylevel im-
ages, so color was disregarded for the whole experiment (e.g. human subjects were shown graylevel
versions of the texture images.) Also, based on the results of the previous experiment, we tested
only the Euclidean and the Fuzzy Feature Contrast metrics.
4.2.1 Distance Measurement
Manjunath and Ma's features [14]) are collected in a vector of 60 elements. If we measure the
Euclidean distance between two raw vectors, we could encounter scale problems: features that have
an inherently larger scale would be predominant. This is especially a problem for the Euclidean
distance, since FFC normalized all the features in [0, 1] via the membership function. In order to
provide a more objective comparison, we tried two types of Euclidean measure: normalized and
not normalized. Let x the feature vector of the i-th image.
We compute the componentwise averages
and the componentwise standard deviation
"N
With these definitions, the scaled Euclidean distance is defined as:
Experimentally, the two distances gave similar results, the scaled distance being slightly better than
the unscaled. In the rest of this section we will only consider the scaled Euclidean distance (from
now on we will just call it the Euclidean distance for the sake of brevity.) The distance measure
for FFC is given by (24) with membership function
4.2.2 Method
Due to the substantially larger size of the database in this example, it was unpractical to use
the same method as in the previous example. While it is feasible to ask a subject to order 10
sketches with respect to a stimulus, it is unfeasible to ask to rank 100 texture images. Therefore,
we followed a different procedure. For a given experiment, we selected one query image, x q , ordered
the database using both the Euclidean and the FFC measures, and, for each measure, collected the
images closer to the query. Let AE and A T be the sets of the ten images closer to the query
using the Euclidean and the FFC measures respectively. We then considered the set
of the images returned by either of the queries. In our case this set contained between 12 and
images, depending on the number of images common to the two queries.
The set A was presented to our subjects, asking them to rank the images with respect to
the query. We then took the first 10 images ranked by the subjects and compared them with
the ordering obtained by the two similarity measures using the same measure as in the previous
experiment.
Euclid
Subject

Figure

7: Similarity results for one of the textures in the database. Orderings obtained by the FFC
distance, the Euclidean distance, and a human subject.

Table

5: Average ( -
of the weighted displacement for the 2 measures consid-
ered. E: Euclid. FFC: Fuzzy Feature contrast.
Note that with this technique it is impossible to provide an absolute measure of the performance
of a certain similarity measure with respect to human performance. This is because our subjects
don't see the whole database. There might be images in the database that a person would judge
very similar to the query but, if both our distance measures miss them, the subject will never see
them. The only results that this technique can give is a measurement of the relative performace of
two similarity measures.
Fig. (7) shows a sample experiment. The first row contains the top 10 images returned by the
FFC distance. The second row contains the top 10 images returned by the Euclidean distance. All
images contained in the first two rows were shown to one of our subjects and she was asked to rank
them. The results are shown in the third row of Fig. 7.
4.2.3 Results
The average value ( -
and the variance (oe 2 ) of the weighted displacement measure for the Euclidean
and the FFC distances are reported in Table 5
This experiment gave us a value which implies that the difference is statistically
significant with
conventionally, means tha the effect to the distance
measure is "large" (a significant portion of the variance is due to the distance measure and not to
subject variation.)
Conclusions
In visual information systems it is important to define exactly the operation of similarity assessment.
While matching is defined essentially on logic grounds, the definition of similarity assessment must
have a strong psychological component. Whenever a person interrogates a data repository asking
for something close, or related, or similar to a certain description or to a sample there is always
the understatement that the similarity at stake is perceptual similarity. If our systems have to
respond in an "intuitive" and "intelligent" manner, they must use a similarity model resembling
the humans'.
One problem with the psychological view is that often we don't have mathematical or computational
models that can be applied to artificial domains. In this paper we have explored the
psychological theories that are closer in spirit to the needs of computer scientists.
Most of the similarity theories proposed in literature reject some or all the geometric distance
axioms. The more troublesome axiom is the triangle inequality, but other properties, like symmetry
and the constancy of self similarity have been challenged. Also, nonlinearities enter in the similarity
judgment both at the feature level (Fechner's law [12]) and during similarity measurement.
One of the most successful models of similarity is Tversky's feature contrast which, incidentally,
is also the most radical in the refusal of the distance axioms. In this paper we have used fuzzy logic
to extend the field of applicability of the model. Also, the use of fuzzy logic allows us to model
the interference between the features upon which the similarity is based. By interference we mean
that the judged truth of a property, like the fact that a line is long, does not depend only on the
measured length of the line, but also on the relationships between the line and the other elements
in the image. We have shown that it is possible to model this interference using a suitable fuzzy
measure.
An important problem that we could not address in this paper is the determination of the
parameters of the similarity measure. The parameters ff and fi in (23), the constants fl in (47),
and the parameters of the membership function influence the similarity measure. This topic is
considered in [18].

Acknowledgments

The authors gratefully acknowledge the anonymous reviewers for the many helpful comments and
criticism on earlier drafts of the paper.



--R


Toward a unified theory of similarity and recognition.
Dimensions of similarity.
Perception and the Repreentative Design of Psychological Experiments.
Topological methods in cardinal utility theory.
Benchmarking multimedia databases.
A multidimensional stochastic theory of similarity.
Fundamental of Digital Image Processing.
Machine Vision.
Design and Analysis.
Concerning the applicability of geometric models to similarity data: The interrelationship between similarity and spatial density.
The Wave Theory of Difference and Similarity.

Texture features for browsing and retrieval of image data.
Modeling of natural objects including fuzziness and application to image understanding.
Cognitive reference points.
A measure of stimulus similarity and errors in some paired-associate learning tasks
The use of psychological similarity measure for queries in image databases.
Similarity is a geometer.
The analysis of proximities: Multidimensional scaling with unknown distance function.
Toward a universal law of generalization for physical science.
Color indexing.
A law of comparative judgement.
Multidimensional scaling of similarity.
Features of similarity.

The dimensional representation and the metric structure of similarity data.
Web Page.
--TR

--CTR
Antonio Adan , Miguel Adan, A Flexible Similarity Measure for 3D Shapes Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.11, p.1507-1520, November 2004
Suchendra M. Bhandarkar , Feng Chen, Similarity Analysis of Video Sequences Using an Artificial Neural Network, Applied Intelligence, v.22 n.3, p.251-275, May       2005
Jrgen Assfalg , Alberto Del Bimbo , Pietro Pala, Retrieval of 3D objects by visual similarity, Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval, October 15-16, 2004, New York, NY, USA
Yi Zhao , Wolfgang Halang, Rough concept lattice based ontology similarity measure, Proceedings of the 1st international conference on Scalable information systems, p.15-es, May 30-June 01, 2006, Hong Kong
Joo-Hwee Lim , Jian Kang Wu , Sumeet Singh , Desai Narasimhalu, Learning Similarity Matching in Multimedia Content-Based Retrieval, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.846-850, September 2001
Mario G. C. A. Cimino , Beatrice Lazzerini , Francesco Marcelloni, A novel approach to fuzzy clustering based on a dissimilarity relation extracted from data using a TS system, Pattern Recognition, v.39 n.11, p.2077-2091, November, 2006
Raghu Krishnapuram , Swarup Medasani , Sung-Hwan Jung , Young-Sik Choi , Rajesh Balasubramaniam, Content-Based Image Retrieval Based on a Fuzzy Approach, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1185-1199, October 2004
Tamalika Chaira , A. K. Ray, Fuzzy approach for color region extraction, Pattern Recognition Letters, v.24 n.12, p.1943-1950, August
Joselto J. Chua , Peter E. Tischer, A similarity measure based on causal neighbours and mutual information, Design and application of hybrid intelligent systems, IOS Press, Amsterdam, The Netherlands,
Huizhong Long , Wee Kheng Leow, Perpetual consistency improves image retrieval performance, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.434-435, September 2001, New Orleans, Louisiana, United States
Horst Eidenberger, Distance measures for MPEG-7-based retrieval, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California
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
Byeong Hwan Jeon , Kyoung Mu Lee , Sang Uk Lee, Face detection using a first-order RCE classifier, EURASIP Journal on Applied Signal Processing, v.2003 n.1, p.878-889, January
Artur Ziviani , Serge Fdida , Jos F. de Rezende , Otto Carlos M. B. Duarte, Improving the accuracy of measurement-based geographic location of internet hosts, Computer Networks and ISDN Systems, v.47 n.4, p.503-523, 15 March 2005
Wai-Tak Wong , Frank Y. Shih , Jung Liu, Shape-based image retrieval using support vector machines, Fourier descriptors and self-organizing maps, Information Sciences: an International Journal, v.177 n.8, p.1878-1891, April, 2007
Goran Nenadi , Irena Spasi , Sophia Ananiadou, Automatic discovery of term similarities using pattern mining, COLING-02 on COMPUTERM 2002: second international workshop on computational terminology, p.1-7, August 31, 2002
Zhizhen Liang , Pengfei Shi, Similarity measures on intuitionistic fuzzy sets, Pattern Recognition Letters, v.24 n.15, p.2687-2693, November
Behrooz Kamgar-Parsi , Behzad Kamgar-Parsi , Anil K. Jain , Judith E. Dayhoff, Aircraft Detection: A Case Study in Using Human Similarity Measure, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.12, p.1404-1414, December 2001
Rainer Lienhart , Wolfgang Effelsberg , Ramesh Jain, VisualGREP: A Systematic Method to Compare and RetrieveVideo Sequences, Multimedia Tools and Applications, v.10 n.1, p.47-72, January 2000
Noureddine Abbadeni, Content representation and similarity matching for texture-based image retrieval, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California
Simone Santini , Amarnath Gupta , Ramesh Jain, Emergent Semantics through Interaction in Image Databases, IEEE Transactions on Knowledge and Data Engineering, v.13 n.3, p.337-351, May 2001
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
Yixin Chen , Henry L. Bart, Jr. , Fei Teng, A content-based image retrieval system for fish taxonomy, Proceedings of the 7th ACM SIGMM international workshop on Multimedia information retrieval, November 10-11, 2005, Hilton, Singapore
Dietrich Van der Weken , Mike Nachtegael , Etienne Kerre, Combining neighbourhood-based and histogram similarity measures for the design of image quality measures, Image and Vision Computing, v.25 n.2, p.184-195, February, 2007
Jaeyeon Lee , Se Yoon Jeong , Kyu Seo Han , Byung Tae Chun , Younglae J. Bae, Image Navigation: A Massively Interactive Model for Similarity Retrieval of Images, International Journal of Computer Vision, v.56 n.1-2, p.131-145, January-February 2004
Eike Schallehn , Kai-Uwe Sattler , Gunter Saake, Efficient similarity-based operations for data integration, Data & Knowledge Engineering, v.48 n.3, p.361-387, March 2004
John Zachary , S. S. Iyengar , Jacob Barhen, Content based image retrieval and information theroy: a general approach, Journal of the American Society for Information Science and Technology, v.52 n.10, p.840-852, August 2001
Dorin Comaniciu , Peter Meer , David Tyler, Dissimilarity computation through low rank corrections, Pattern Recognition Letters, v.24 n.1-3, p.227-236, January
Masoud Saeed , Hossein Nezamabadi-Pour, Fuzzy color quantization and its application in content-based image retrieval, Proceedings of the 2nd WSEAS International Conference on Circuits, Systems, Signal and Telecommunications, p.60-66, January 25-February 27, 2008, Acapulco, Mexico
Pascal Matsakis , James M. Keller , Ozy Sjahputera , Jonathon Marjamaa, The Use of Force Histograms for Affine-Invariant Relative Position Description, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.1, p.1-18, January 2004
Zoran Steji , Yasufumi Takama , Kaoru Hirota, Mathematical aggregation operators in image retrieval: effect on retrieval performance and role in relevance feedback, Signal Processing, v.85 n.2, p.297-324, February 2005
Leonid Kompanets, Some advances and challenges in live biometrics, personnel management, and other "Human being" applications, Enhanced methods in computer security, biometric and artificial intelligence systems, Springer-Verlag, London, 2005
Bertrand Zavidovique , Vito Di Ges, The S-kernel: A measure of symmetry of objects, Pattern Recognition, v.40 n.3, p.839-852, March, 2007
Nezamabadi-pour , E. Kabir, Image retrieval using histograms of uni-color and bi-color blocks and directional changes in intensity gradient, Pattern Recognition Letters, v.25 n.14, p.1547-1557, 15 October 2004
H. Bustince , M. Pagola , E. Barrenechea, Construction of fuzzy indices from fuzzy DI-subsethood measures: Application to the global comparison of images, Information Sciences: an International Journal, v.177 n.3, p.906-929, February, 2007
Yacov Hel-Or , Hagit Hel-Or, Real-Time Pattern Matching Using Projection Kernels, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.9, p.1430-1445, September 2005
A. Engbers , Arnold W. M. Smeulders, Design Considerations for Generic Grouping in Vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.4, p.445-457, April
Arnold W. M. Smeulders , Marcel Worring , Simone Santini , Amarnath Gupta , Ramesh Jain, Content-Based Image Retrieval at the End of the Early Years, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.12, p.1349-1380, December 2000
image distances;content-based retrieval;similarity measures;image databases;perceptual similarity