How to find good examples of triangular inequality for visual similarity?

• [cliquer ici pour la version en français]

Amos Tversky works have shown that human similarity judgement is not a metric (in a mathematic sens). In particular the following properties are not always verified:

1. Minimality : $\delta(a,b) \geq \delta(a, a) = 0.$
2. Symmetry : $\delta(a, b) = \delta(b, a)$.
3. Triangular inequality : $\delta(a, b) + \delta(b, c) \geq \delta(a, c)$.

Computer vision shows more and more interests in Tversky's results. In their introduction, many publications try to illustrate the non-verification of the previous properties. My point is that the examples of the non-verification of the triangular inequality are not correct (for images). By example, in a projet report (Graphem - in french) on the visual similarity, the authors propose these images:

A                               B                               C

According to the authors:

1. left (A) and right (C) images can be judged quite dissimilars.
2. But middle image (B) can be judged similar to (A) et à (C).
3. The distance d(A, C) would thus be greater than the sum d(A,B)+d(B,C), contradicting the triangle inequality.

I don't see in this example where is the non verification of the triangle inequality:

1. Ok for the first point, one can imagine an experience reinforcing these facts. The distance d(A, C) is thus obtained "high". It could be discussed on the precise measure. Or if the measure is d(A, C) or d(C, A). But this can be admitted.
2. If B is judged similar to A and C, the measures d(B, A) and d(B, C) must be "low", in  any case smaller than d(A, C).

For the last point, a conclusion on the triangle inequality can only be given from a comparison between d(A, C) and the sum d(B, A) + d(B, C). But the numerical values are unknown, or not given by the authors. It is thus impossible to compute the sum and thus impossible to conclude. More formally, we have: $d(B, A) \leq d(A, C)$ and $d(B, C) \leq d(A, C)$. The only possible conclusion is $d(B, A) + d(B, C) \leq 2 d(A, C)$, but not $d(B, A) + d(B, C) \geq d(A, C)$.

Other bad examples can be find. Thus in a diaporama from J.M. Jolion (in french) on the similarity between images:

According to the author: with respect to a partial registration the triangle inequality is not validated d(a, b) + d(b, c) <= d(a, c). My previous commentaries still apply, i don't understand how the author produces its conclusion.

In order to be complete, in E. Baudrier PhD thesis (p. 67) (that i supervised), the same kind of examples is reproduced:

Triangular inequality: left and center images are similar, center and right ones also. If the similarity verify the triangular inequality, the left and right images are simular. It is not the case (Baudrier, 2005)

There, the author doesn't try to compute any sum and its argument is close to Tversky one's in "Features of Similarity" :

The triangle inequality differs from minimality and symmetry in that it cannot be formulated in ordinal terms. It asserts that one distante must be smaller than the sum of the two others, and hence it cannot be readily refuted with ordinal or even interval data. However, the triangle inequality implies that if A is quite similar to B, and B is quite similar to C, then A and C cannot be very dissimilar from each other.

Here Tversky makes a confusion between transitivity and triangular inequality. Does the former implies the latter ? It is not proved! Elsewhere in its publication, Tversky points out that visual stimulus are different in nature of others stimulus (verbal ones by example). Can visual stimulus lead to a verification of the triangular inequality? I don't think so but still can't find indisputable example of this in the case of visual objects.

FMN.

Une sélection (automatique) de billets similaires :
• Transitivité ou inégalité triangulaire ?
• Plugin ImageJ minimal en Clojure: inverser une image
• Deux utilisations de la mesure de similarité locale
• Une similarité visuelle non-sémantique est-elle viable ?
• Notes sur la journée thématique GRCE "caractéristiques et similarités dans les images naturelles et les images de documents"

4 Comments

• Daniel Lemire says:

  8 June 2009 at 18:20

  Voir l'appendice B d'un papier que j'ai récemment publié dans la revue Pattern Recognition:

  http://arxiv.org/pdf/0811.3301v1

  Il ne s'agit pas d'images dans le cas de mon papier, mais le "Time Warping" se généralise sans mal aux images et formes.
• fmn says:

  9 June 2009 at 15:11

  Daniel,

  j'ai lu le papier indiqué (enfin surtout le début et l'annexe mentionnée). Si j'ai bien compris, tu indiques que le DTW dans le cas général ne vérifie pas l'inégalité triangulaire, sauf pour p=inf. Tu indiques également que le DTW est réflexif et symétrique. Je note en tout cas que la production d'exemple de non-vérification de l'inégalité triangulaire en signal 1D n'est pas non plus triviale. En fait c'est amusant, car je m'efforce au contraire de fabriquer une mesure de similarité permettant des mesures asymétriques. Je regarderai de plus près la généralisation du DTW aux images.

  ps : il me semble qu'il y a une coquille dans l'annexe B, premier paragraphe. La symétrie ne s'exprimerait-elle pas par : A ~ B => B ~ A ?
• Daniel Lemire says:

  10 June 2009 at 19:29

  C'est ça oui.

  Ensuite...

  Faut bien attendre que le papier soit publié pour trouver une telle coquille! Ah! Bon, au moins, je ferai la mise à jour sur arxiv. Et, heureusement pour moi, tout le monde peut voir que c'est une coquille bête.

Trackbacks / Pingbacks

• Transitivité ou inégalité triangulaire ? says:

  10 June 2009 at 16:49

  [...] mon billet d’hier, je mentionnais l’inadéquation de la plupart des illustrations censées montrer comment la [...]