A unified framework for detecting groups and application to shape recognition

Frédéric Cao (1) , Julie Delon (2) , Agnès Desolneux (3) , Pablo Musé (2) , Frédéric Sur (4)

1 VISTA - Vision spatio-temporelle et active
2 CMLA - Centre de Mathématiques et de Leurs Applications
3 MAP5 - Mathématiques Appliquées à Paris 5
4 MAGRIT - Visual Augmentation of Complex Environments

A unified a contrario detection method is proposed to solve three classical problems in clustering analysis. The first one is to evaluate the validity of a cluster candidate. The second problem is that meaningful clusters can contain or be contained in other meaningful clusters. A rule is needed to define locally optimal clusters by inclusion. The third problem is the definition of a correct merging rule between meaningful clusters, permitting to decide whether they should stay separate or unit. The motivation of this theory is shape recognition. Matching algorithms usually compute correspondences between more or less local features (called shape elements) between images to be compared. This paper intends to form spatially coherent groups between matching shape elements into a shape. Each pair of matching shape elements indeed leads to a unique transformation (similarity or affine map.) As an application, the present theory on the choice of the right clusters is used to group these shape elements into shapes by detecting clusters in the transformation space. // Une méthode de détection a contrario est proposée pour résoudre trois problèmes classiques de clustering. Le premier est d'évaluer la validité d'un cluster candidat. Le second problème est qu'un cluster peut en contenir un autre, ou lui même être contenu dans un cluster. Une règle est nécessaire pour choisir les clusters optimaux lors de telles inclusions. Le troisième problème est la définition d'une règle de fusion correcte entre deux clusters, permettant de décider si ceux-ci doivent rester séparés ou au contraire être fusionnés. Cette étude est motivée par une application de reconnaissance des formes. Les algorithmes de mise en correspondance calculent en général des caractéristiques locales (appelées éléments de forme dans le présent article), qui sont ensuite comparées. Notre but est de montrer qu'on peut former des groupes spatialement cohérents d'éléments de formes. Chaque correspondance entre élément de forme définit en effet une unique transformation (similitude ou transformation affine dans le cas présent). Le groupement de ces transformations permet de détecter des formes à partir des éléments de formes.

Mots clés: Cluster validity; merging criterion; number of false alarms; shape recognition // Validité d'un cluster; critère de fusion; nombre de fausses alarmes; reconnaissance de formes

Domaines: Vision par ordinateur et reconnaissance de formes [cs.CV]

Frédéric Cao, Julie Delon, Agnès Desolneux, Pablo Musé, Frédéric Sur. A unified framework for detecting groups and application to shape recognition. [Research Report] PI 1746, 2005, pp.36. ⟨inria-00000360⟩