1 Modélisation d'images par des graphes plans Émilie Samuel, Colin de la Higuera, Jean-Christophe Janodet

1

Modélisation d'images par des graphes plans

Émilie Samuel, Colin de la Higuera, Jean-Christophe

Janodet

SATTIC, juillet 2010 2

Plan

1. Enjeux2. Méthode3. Définitions4. Les sommets du graphe5. Les arêtes du graphe6. Du graphe à l’image7. Résultats expérimentaux8. Questions ouvertes


1 Enjeux et objectifs

Extraire des graphes à partir des images

Graphes plans Autres possibilités ?


Pourquoi des graphes ?

Plus grande richesse de représentation que les mots et les arbres

Plus grande complexité algorithmique


Quelques alternatives (1)

Les sommets sont les centres (?) de zones (de segmentation ?) et les arêtes signifient « frontière commune »



Les sommets sont des points d’intérêt et les arêtes sont obtenues par triangulation


L’image originale



On segmente. Les sommets sont des points d’intersection et les arêtes sont obtenues par suivi des frontières

Même graphe


Graphes plans

Travaux de Damiand, de la Higuera, Janodet, Samuel & Solnon

Intérêt : les problèmes d’isomorphisme et de sous-isomorphisme deviennent solvables en temps polynomial


Enjeux

Extraire des graphes plans sémantiquement intéressants et robustes

Sémantiquement intéressants= Le graphe « ressemble à l’image » Le graphe permet une compression de

l’image


2 Méthode

1. Segmenter une image2. Extraire des pixels d’intérêt3. Convertir ces pixels en pointels4. Choisir des arêtes correspondant aux

lignels5. Ajouter des arêtes par triangulation

dans chaque zone


3 Quelques définitions

Pointels et lignels Graphes plans Perte



Graphes plans

a

cd

b

ef

g

k

j

hi

l

a

c

b

gj

hi

l


p(I,i,j) : le pixel en position i, j de l’image I

dp(p1,p2): la différence entre les pixels p1 et p2

perte(I1, I2) =i,j dp(p(I1, i, j), p(I2, i, j))

n ∗ m

Les images sont de taille n*m


4 Choix des sommets

Utilisation d’un extracteur de pixels d’intérêt

Mais sur des images segmentées Convertir les pixels d’intérêt en pointels

d’intérêt


Le pingouin

Le bruit influeDonc d’abord segmenter ce qui contribue à lisser l’image


Segmentation

?? px

Image segmentée, 7 régions)


Autre segmentation

autre image du contour d'une segmentation du manchot (10 régions)


Extraction de pixels d’intérêt sur les images segmentées

50 sommets

200 sommets

100 sommets


Sur image originale


Comparaison (100 pixels)

Image segmentée Image originale


Des pixels aux pointels

Enjeu: travailler dans R Quel(s) pointels associer à un pixel? Algorithme

1. Compléter les pixels par les pixels de coins2. Ajouter les pixels d’intersection3. Pour chaque pixel prendre les pointels qui

font « coin »


Choix des pointels associés à un pixel


Exemple


Points d’intérêt extraits


Ajouts de pixels supplémentaires


Pixels en pointels


Pointels retenus


RésuméIllustration des pixels extraits automatiquement, ajoutés aux pointels d'intersection, aux coins, et aux pixels non retenus


5 Choix des arêtes

On dispose d’un ensemble de sommets, comment choisir les arêtes ? De façon à « retrouver » l’image De façon à ce que les arêtes consolident

l’image (triangulation)


Pointels retenus


Suivi de frontière


Sur le pingouin

81 sommets

145 sommets


Pourquoi ajouter les pointels d’intersection

Avec Sans


Deux graphes plans isomorphes

Mais qui cessent de l’être si on triangule


Triangulation


6 Du graphe à l’image

Pour pouvoir vérifier la qualité de notre graphe, il faut pouvoir reconstruire une image derrière

Attention : il s’agit de graphes enrichis avec 2 informations : Position des sommets Couleurs des zones

Im(G,C,P)


Du graphe à l’image

principe de la reconstruction d'une image à partir d'un graphe : pour les pixels non traversés par une ou des arêtes, il s'agit de la moyenne des couleurs des pixels de la région. Pour les pixels traversés, on considère chaque pointel. Chaque pointel a une couleur égale à la moyenne des 4 couleur de ses 4 pixels adjacents (couleur de la segmentation). Le pixel a alors comme couleur la moyenne des couleurs de ses 4 pointels.


Segmentation

145 sommets 81 sommets

Segmentation de base


7 Résultats expérimentaux Berkeley Segmentation Dataset 300 images (481x321 RGB) du Corel Dataset 1633 segmentations différentes Nombre de régions de 2 à 20 D. Martin, C. Fowlkes, D. Tal, and J. Malik. A

database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In Proc. 8th Int. Conf. Computer Vision, volume 2, pages 416–423.

http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/.


7.1 La base

I Ik


Perte en fonction de la segmentation

perte de l'image d'origine à l'image segmentée, en fonction du nombre de régions de la segmentation, et écarts-types.


7.2 Comparaison avec l’extraction directe

Comparaison des valeurs des pertes avec notre méthode (bleu) ou une extraction directe des points sur l'image d'origine (rouge)


7.3 Pertes relatives

perte( I , Ik )

et

perte(G(Ik,s), Ik)

perte( , )

et

perte( , )

s = nombre de pixels extraitsk = nombre de régions de segmentationG(Ik,s) Image correspondant au graphe obtenu en extrayant s pixels sur Ik


s k |V| perte(I,Ik)) perte(Ik,G(Ik,s))

50 3 104 0.084 0.006

50 7 123 0.084 0.005

50 9 175 0.084 0.006

50 13 149 0.084 0.007

50 20 207 0.083 0.007

For one image, losses corresponding to different levels of segmentation.


Pour 2 images A et B

s k |V| Perte(I,Ik) Perte(Ik,G(Ik,s)) Perte(I,G(Ik,s))

A

80 7 182 0.084 0.004 0.088

20 18 188 0.076 0.023 0.098

B

80 11 146 0.166 0.009 0.175

20 25 145 0.166 0.022 0.188


7.4 Perte en fonction du nombre de pixels extraitsPerte de l'image segmentée à l'image du graphe, en fonction du nombre de pixels d'intérêt extraits (et écarts-types)


Combien de pointels pour un pixel ?


Combien de pixels choisir ?Influence du nombre de régions sur le nombre de pointels, en fonction du nombre de pixels extraits


Un mot sur les tailles

I est l’image (n.m) Im(G,C,P) est l’image reconstruite à partir

du graphe G à |V| sommets, du vecteur de couleurs C et du vecteur de positions P

I nmK

I(G,C,P)|V|(log n+log m+3+K)


8 Questions ouvertes

Comment mesurer la robustesse de la construction ?

Distance (d’édition) entre graphes (triangulés) plans ?

Pourquoi ajouter des pixels d’intersection (et de coin) plutôt que des pointels ?

http://labh-curien.univ-st-etienne.fr/ ~samuel/extracting_plane_graphs/

http://labh-curien.univ-st-etienne.fr/~samuel/extracting_plane_graphs/

http://labh-curien.univ-st-etienne.fr/~samuel/extracting_plane_graphs/


Bibliographie

Extracting Plane Graphs from Images. A. Rosenfeld. Adjacency in digital pictures. Infor. and Control, 26(1):24–33, 1974.

M. D. Santo, P. Foggia, C. Sansone, and M. Vento. A large database of graphs and its use for benchmarking graph isomorphism algorithms. Pattern Recognition Letters, 24(8):1067–1079, 2003.

W. Tutte. A census of planar maps. Canad. J. Math., 15:249–271, 1963.


S. Bres and J.-M. Jolion. Detection of interest points for image indexation. In Proc. VISUAL’99, pages 427–434. LNCS 1614, 1999.

D. Conte, P. Foggia, C. Sansone, and M. Vento. Thirty years of graph matching in pattern recognition. Pattern Recogn. and Artificial Intell., 18(3):265–298, 2004.

G. Damiand, C. de la Higuera, J.-C. Janodet, E. Samuel, and C. Solnon. A polynomial algorithm for submap isomorphism: Application to searching patterns in images. In Proc. GbRPR’09, pages 102–112. LNCS 5534, 2009.

C. de la Higuera, J. Janodet, E. Samuel, G. Damiand, and C. Solnon. Polynomial algorithm for open plane graph and subgraph isomorphism. Work in progress.

I. Fary. On straight-line representation of planar graphs. Acta Scientiarum Mathematicarum, 11:229–233, 1948.

A. M. Finch, R. C.Wilson, and E. R. Hancock. Matching delaunay graphs. Pattern Recognition, 30(1):123–140, 1997.

C. Harris and M. Stephens. A combined corner and edge detection. In Proceedings of the Fourth Alvey Vision Conference, pages 147–151, 1988.

X. Jiang and H. Bunke. Optimal quadratic-time isomorphism of ordered graphs.Pattern Recognition, 32(7):1273–1283, 1999.


W. Kropatsch and H. Macho. Finding the structure of connected components using dual irregular pyramids. In Proc. DGCI’95, pages 147–158, 1995. ISBN 2-87663-040-0.

P. Lienhardt. Topological models for boundary representation: a comparison with n-dimensional generalized maps. Computer-Aided Design, 23(1):59–82, 1991.

D. G. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91–110, 2004.

M. A. Lozano and F. Escolano. Protein classification by matching and clustering surface graphs. Pattern Recognition, 39(4):539–551, 2006.

K. Riesen and H. Bunke. IAM graph database repository for graph based pattern recognition and machine learning. In Proc. S+SSPR’08, pages 287–297. LNCS 5342, 2008.

K. Riesen and H. Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image Vision Comput., 27(7):950–959, 2009.

Documents

1 Modélisation d'images par des graphes plans Émilie Samuel, Colin de la Higuera, Jean-Christophe Janodet