Sébastien PERIN – DEA PTI

Formalisation et OpérationalisationFormalisation et Opérationalisation

de Connaissances Graphiques pourde Connaissances Graphiques pour

l’Interopérabilité en l’Interopérabilité en

analyse d’image de document.analyse d’image de document.

Sébastien PERIN – DEA PTI

15 septembre 2004 Sébastien PERIN - DEA PTI 2/23

PlanPlan

1. Introduction à l’analyse de documents graphiques,

2. Extraction de primitives graphiques,

3. Formalisme et représentation des connaissances,

4. Formalisme adopté,

5. Contributions,

6. Mise en œuvre,

7. Conclusions et perspectives,


• L’analyse d’images de documents graphiques

• L’extraction de primitives graphiques en 3 étapes.

1.1. Introduction à l’analyse de documents Introduction à l’analyse de documents graphiquesgraphiques

ExtractionExtractionApproximationApproximationConstructionConstruction

ImageImagePrimitivesPrimitives

GraphiquesGraphiques

points, lignes, arcs, courbes

A

B

D

C


2.2. Extraction de primitives graphiques (1)Extraction de primitives graphiques (1)Étude bibliographiqueÉtude bibliographique

• Les techniques d’extraction bas niveau :

• Approximation– Ligne, cercle, courbe

[Rosin,West95]

• Construction d’objets

Squelette[Lam95]

[Tombre99]

Contour[Abl,Prid00]

Mailles[Vaxivière95]

Régions[Chen94][Cao00]

Plages[Burge98]

Segmentation d’objet[Su02], [Chen00]

Reconstruction de cercle[Hilaire01]

Appariement de contour[Ramel00], [Han94]

Suivi de trait[Dori99][Song03]


2.2. Extraction de primitives graphiques (2)Extraction de primitives graphiques (2)

• Comparaison d’approches [Delalandre03]

1. Les objets manipulés proches

2. Traitements granulaires communs

3. Combinaisons: • évaluation d’approches,

• approches hybrides,

• coopération d’approches

Problématique : L’échange des connaissances Problématique : L’échange des connaissances graphiques permettant l’interopérabilité.graphiques permettant l’interopérabilité.

Analyse

Analyse

Reconnaissance 1

Reconnaissance 2

Comparaison

Analyse /Reconnaissance

ReconnaissanceConstruction

hybrideAnalyse /Reconnaissance

Analyse / Reconnaissance

Analyse Reconnaissance


3.3. Formalisme et représentation des Formalisme et représentation des connaissances (1)connaissances (1)

• Étude bibliographique :– Les différents types de formalismes [Kayser97] :

• À base de règles [Paulson99] (ex : Faire Action si Condition(s) )

• À base de frames [Minsky75] (ex: )

• À base de graphes [Lacomme03] (ex: )

• Orientés données (listes, matrices, …) [Lucas86]

– Représentations :• Formats [Wilkinson00]

• Langages de représentation [Kayser97]

j

ls.ptj

q

ac

j

jaccb

ls.pt

ls.pt


3.3. Formalisme et représentation des Formalisme et représentation des connaissances (2)connaissances (2)

• Quelques formalismes et représentations des connaissances graphiques :

• Formalisme « vectoriel et graphe » est privilégié

FormalismeFormalisme ReprésentationReprésentation

[SVG-01] Vectoriel + listes Langage balisé XML

[DXF-80] Vectoriel + listes Format de données

[CGM-97] Vectoriel + graphes+ symbolique Format de données

[Ah Soon01] Vectoriel + règles+ symbolique Langage

[Allanic00] Vectoriel + graphes Format de données

[Hilaire01] Vectoriel + graphes …

[Pasternak95] Vectoriel + règles + symbolique Langage

[Ramel00] Vectoriel + graphes …

[Song02] Vectoriel + graphes …

Formalisme choisi pour l’interopérabilité est à base Formalisme choisi pour l’interopérabilité est à base d’une structure de graphesd’une structure de graphes


4.4. Le formalisme adopté (1)Le formalisme adopté (1)

• L’objet graphique :

– Les données :

• Les attributs graphiques :

– Les données :

mdogi ,

kj ogogddd ,...,,,..., 10

og

1og 3og2og nog

1ag

ag

3ag2ag nag mdagi ,

kj agagddd ,...,,,..., 10



• L’objet graphique :

– Primitives, listes, et graphes • Les listes :

• Les graphes :

• Formalisation des connaissances graphiques par des graphes relationnels attribués pyramidaux. [Jolion90]

glsppog n ,,,...,1

mn agagogogagogls ,...,,,...,, 11

mn eeogogeog ,...,,,...,, 00

agjie ,),(

jii ogogag , iji agogogf ,



• Standard :– Objet graphique :

– Attribut graphique : ...,d,lbl,li,ag

.,..cbpt,l,ac,q,og

myxpt ,,

mptptptptcb ,,,, 4321

mptptl eb ,, mtptptptac ecb ,,,,

mptptptptq ,,,, 4321

pt

pt1 pt2

pt3pt4

ptb

ptepteptb

ptc

pt1

pt2 pt3

pt4

l

l =45 pt ptd=10

l

llbl=« détail »

li

ac

ac



• Exemple :

Image de départImage de départ

pt1

pt4

pt2

pt3

pt5 pt6

pt7pt8

l1

l2

l3

l4

l5

l6

l7

l8

l9

Plusieurs représentations possibles Plusieurs représentations possibles Aucune n’est privilégiée Aucune n’est privilégiée

Représentation 1Représentation 1Représentation 2Représentation 2Représentation 3Représentation 3Représentation 4Représentation 4Représentation 5Représentation 5



• Mécanisme d’externalisation des connaissances :

mdogi , tCgm ,Lecture/ÉcritureLecture/Écriture

Exemple avec un point :

<OPoint x= "10" y= "10" />

Exemple d’une ligne :

<OLine length="14.1421" direction="0.785398">

<OPoint x="10" y="10" />

<OPoint x="20" y="20" />

</OLine>



• Mécanisme de requêtes élémentaire de type procédural, par le contenu et/ou par la structure appliqué aux graphes et/ou listes.

– Contenu : tests des types d’objet

– Structure : nombre d’objet, bouclage, etc.

• Exemple :

2,. Nbptlsrqi TraitementTraitementPolygonalisationPolygonalisation

ls.ptls.pt

ls.pt

j

ls.lj

q

ac

j

jaccb

ls.l

ls.l

j

ls.ptj

q

ac

j

jaccb

ls.pt

ls.pt

Substitution des Substitution des listes de points listes de points

par des listes de par des listes de ligneslignes

irq , ls.lls.l

ls.lsrq



• Le formalisme est codé en C++, basé sur la STL et la GTL, et s’appuie sur le polymorphisme, l’idiome de constructeur virtuel, chargement dynamique d’objet,

• 21 classes pour les objets et attributs graphiques, 7 classes pour les traitements,

• 56 fichiers 130 Ko de code.


5.5. Contributions (1)Contributions (1)

• Introduction :

– La librairie de modélisation l’échange de connaissances graphiques

– Développement plate forme de traitement basé sur la librairie modélisation :

• l’extraction de primitives graphiques

• la combinaison des différentes méthodes

– Présentation des traitement de la plate forme :

• Polygonalisation

• Appariement de contours

• Construction de courbes


5.5. Contributions (2)Contributions (2)PolygonalisationPolygonalisation

• « La corde » [Douglas,Peucker73].• Entrée : liste de points et seuil• Sortie : Liste de lignes.


5.5. Contributions (3)Contributions (3)PolygonalisationPolygonalisation

• Le « split & merge » [Pavlidis, Horowitz74] , ou division-fusion.• Entrée : liste de points et seuil• Sortie : Liste de lignes.

• Élimination des parasites


5.5. Contributions (4)Contributions (4)Appariement de contoursAppariement de contours

• L’algorithme d’appariement de contours [Han94] se décompose en 5 étapes :– Test d’appariement (critères : vecteurs non-connectés, de

sens opposés, superposition de leurs projections axiales) – Calcul de ces 3 critères logiques– Filtrage des « appariements éloignés »– Tri logique des propositions d’appariement– Appariement

• Construction de quadrilatères.[Ramel00]

ContourContour QuadrilatèresQuadrilatères


5.5. Contributions (5)Contributions (5)Construction de courbesConstruction de courbes

• Interpolation par des courbes de Bézier [Zorin02].

• Interpolation par des courbes de Bézier cubiques :

P(t) = (1-t)3.P0+3.t.(1-t)².P1+3.t².(1-t).P2+t3.P3.

– Intérêt technologique : courbures, portage vers SVG.

)()(,

0

ttP BP ni

n

ii

)1()(

, ttCBinii

nnit

)!(!

!ini

nCi

n


5.5. Contributions (6)Contributions (6)

• Le système repose sur une plate forme de traitement s’appuyant sur la modélisation

• En langage C++

• 39 fichiers 45 Ko de code


6.6. Mise en Mise en œœuvreuvre (1)(1)Exemple 1Exemple 1

ExtractionExtraction

• La mise en œuvre repose sur la chaîne de traitements suivante :

• De l’image originale l’extraction donne des listes de point, des points isolés et des jonctions potentielles.

PolygonalisationPolygonalisationConstruction Construction

de courbesde courbes


6.6. Mise en Mise en œœuvre (2)uvre (2)Exemple 1Exemple 1

• Listes de points

• La polygonalisationremplace par des listes de lignes

• Les listes de lignes sont remplacéespar des listes de courbe


6.6. Mise en Mise en œœuvre (3)uvre (3)Exemple 2Exemple 2

• Approche contour

Contour

VectorisationVectorisation

ConstructionConstruction

QuadrilatèresQuadrilatères

Effet de bordsEffet de bords


7.7. Conclusions et PerspectivesConclusions et Perspectives

• Conclusions :– L’objectif est atteint : les connaissances graphiques peuvent

circuler entre traitements l’interopérabilité– Les traitements possibles sont :

• La corde• Le Split & Merge• Appariement de contour• Interpolation par courbe de Bézier

• Perspectives :– Formaliser l’approche à base de requêtes (langage de

requête par la structure « XPath, RDF-QL »)– Développer la plate forme de traitementsPour :

• Permettre des scénarios pour la combinaison des traitements pour l’extraction de primitives graphiques

15 septembre 2004 Sébastien PERIN - DEA PTI

Bibliographie (1)Bibliographie (1)

1. [Lam95] L. Lam and C.Y. Suen, An Evaluation of Parallel Thinning Algorithms for Character Recognition, 19952. [Tombre99] K. Tombre and C. Ah-Soon and P. Dosch and G. Masini and S.Tabbone, Stable and Robust

Vectorization : How to Make the Right Choices, 19993. [Abl&Prid00] S. Ablameyko and T.P. Pridmore, Machine Interpretation of Line Drawing Images, 20004. [Dori99] D. Dori, Sparse Pixel Vectorisation : An Algorithm and its Performance Evaluation, 19995. [Song03] J. Song and M.R. Lyu and M. Cai and and S. Cai, Graphic Object Recognition from Binary Images: a

Survey and an Integrated Paradigm, 20036. [Burge98] M. Burge and W.G. Kropatsh, A Minimal Line Property Preserving Representation of Line Images,

19987. [Chen94] Y.S. Chen, Segmentation and Association Among Lines and Junctions for a Line Image, 19948. [Cao00] R. Cao and C.L. Tan, A Model of Stroke Extraction from Chinese Character Images, 20009. [Vaxivière95] P. Vaxivière and K. Tombre, Subsampling : A Structural Approach to Technical Document

Vectorisation, 199510. [Su02] Y.M. Su and J.F Wang, A Learning Process to the Identification of Feature Points on Chinese Characters,

200211. [Chen00] J. Chen and Y. Sato and S. Tamura, Orientation Space Filtering for Multiple Orientation Line

Segmentation, 200012. [Rosin,West95] P.L. Rosin and G.A.W. West, Nonparametric Segmentation of Curves Into Various

Representations, 199513. [Hilaire01] X. Hilaire, Ranvec and the Arc Segmentation Contest, 200114. [Ramel00] J.Y. Ramel, N. Vincent, H Emptoz, A structural representation for understanding line-drawing images,

2000.15. [Han94] C.C. Han, K.C. Fahn, Skeleton generation of engineering drawings via contour matching, 1994.

Références

15 septembre 2004 Sébastien PERIN - DEA PTI

Bibliographie (2)Bibliographie (2)

16. [Delalandre03] M. Delalandre, E. Trupin, J.M. Ogier, Local Structural Analysis: a Primer, GREC 2003

17. [Kayser97] D. Kayser, La Représentation des Connaissances, 1997

18. [Paulson99] L.C. Paulson, Logic and Proof, 1999

19. [Minsky75] Minsky, 1975

20. [Lacomme03] P. Lacomme, Algorithmes de Graphes, 2003

21. Lucas86] M. Lucas, Algorithmes et Représentation des Données, 1986

22. [Wilkinson00] L. Wilkinson, D.J. Rope, D.B. Carr, M.A. Rubin, The Language of Graphics, 2000

23. [AhSoon01] C. Ah-Soon, K. Tombre, Architectural Symbol Recognition Using a Network of Constraints, 2001

24. [Allanic00] H. Allanic, E. Petit, M. Villalon, F. Lopes, Un Outil d'Interprétation d'Image Basé sur un Modèle Vectoriel Topologique, 2000

25. [Pasternak95] B. Pasternak and B. Neumann, The Role of Taxonomy in Drawing Interpretation, 1995

26. [Song02] J. Song, F. Su, C. Tai, S. Cai, An Object-Oriented Progressive-Simplification based Vectorisation System for Engineering Drawings: Model, Algorithm and Performance, 2002

27. [Jolion90] J.M. Jolion, Analyse d’images : Le modèle pyramidale, Traitement du signal, vol. 7, 5-17, 1990.

28. [Douglas,Peucker73] D. H. Douglas, T. K. Peucker, Algorithm for the reduction of the number of points required to represent a digitized line or its caricature. Can. Cartographer 10(2), 112-122, 1973.

29. [Pavlidis,Horowitz74] T. Pavlidis, S. L. Horowitz, Segmentation of plane curve, IEEE Transactions on Computers, vol. C-23, 1974, 860-870.

30. [Zorin02] D. Zorin, Bezier Curves and B-splines, Blossoming, 2002.

Références

Documents

Sébastien PERIN – DEA PTI