PI-1594: Accurate estimates of false alarm number in shape recognition
Pablo Musé, Frédéric Sur, Frédéric Cao, Yann Gousseau, Jean-Michel Morel
http://www.irisa.fr/bibli/publi/pi/2004/1594/1594.html
38 pages - janvier 2004

Abstract
There are many shape recognition algorithms. Their Achilles heel usually
is the control of the number of false positive, or false alarms. A match
between two shapes F and F' being proposed with a distance d, we compute
the ``number of false alarms" of this match. This number is computed as
an upper bound of the expectation of the number of shapes which could
have casually a distance lower than d to F in the database. It turns
out that a simple encoding of shape elements as pieces of level lines
leads to compute numbers of false alarms for the good matches as small
as 10-13. As an application, one can decide with a parameterless method
whether any two digital images share some shapes or not.

Résumé
Il existe de nombreux algorithmes de reconnaissance de formes. De
manière générale, leur talon d'Achille est le contrôle du nombre de faux
positifs (ou nombre de fausses alarmes). Pour deux formes F et F' à
distance d, le présent article propose une définition du nombre de
fausses alarmes de la mise en correspondance de F' avec F. On montre que
ce nombre est une borne supérieure du nombre de formes qui sont
casuellement à une distance de F inférieure à d dans la base de données.
On montre expérimentalement que des éléments de formes simplement codés
à partir de lignes de niveau permettent d'atteindre des nombres de
fausses alarmes de l'ordre de 10-13. Cela permet de déterminer, sans
paramètre, si deux images partagent ou non des formes.

Keywords: Shape recognition, a contrario model, meaningful matches,
number of false alarms

Mots clefs: Reconnaissance de formes, modèle a contrario, mise en
correspondance significative, nombre de fausses alarmes