A New Model for Graphical Object Description Operating in the Image Space or in the Cosine Discrete Space. Description d’un Objet Graphique: Proposition d’un Modèle Opérant dans L’Espace Image ou dans L’Espace Cosinus Discret

A New Model for Graphical Object Description Operating in the Image Space or in the Cosine Discrete Space

Description d’un Objet Graphique: Proposition d’un Modèle Opérant dans L’Espace Image ou dans L’Espace Cosinus Discret

Patrick Franco Jean-Marc Ogier  Pierre Loonis  Rémy Mullot 

Laboratoire Informatique, Image, Interaction (L3I), Université de la Rochelle – Pôle Sciences et Technologies, 17042 La Rochelle Cedex 1 – France

Page: 
13-27
|
Received: 
9 June 2006
|
Accepted: 
N/A
|
Published: 
28 February 2007
| Citation

OPEN ACCESS

Abstract: 

In this article a new shape descriptor – based on minimal graphs – is proposed and its properties are checked through the problem of graphical symbols recognition.Recognition invariance in front shift and multi-oriented noisy object was studied in the context of small and low resolution binary images.The approach seems to have many interesting properties,even if the construction of graphs induces an expensive algorithmic cost.In order to reduce time computing an alternatively solution based on image compression concepts is provided.The recognition is realized in a compact space,namely the Cosine Discrete space.The use of blocks discrete cosine transform is discussed and justified.The experimental results led on the GREC2003 database show that the proposed method is characterized by a good discrimination power,a real robustness to noise with an acceptable time computing.

Résumé

Cet article propose un nouveau modèle de description d’un objet dans une image. Ce modèle s’appui sur la construction d’un arbre minimal,ses propriétés sont étudiées à travers le problème de la reconnaissance de symboles complexes. L’invariance de la reconnaissance – face aux translations et rotations de symboles dégradés – est vérifiée dans un contexte d’images binaires à faible résolution. Si les résultats sont concluant, le coût algorithmique peut être assez élevé. Une alternative consiste à exprimer l’objet cible dans l’espace Cosinus Discret (Transformation en Cosinus Discrète). La technique opère non plus dans l’espace image mais dans un espace compact où les données sont mieux décorrélées. Certains de nos choix font référence à des concepts de compression d’images. Cette piste conduit à une diminution sensible du coût tout en conservant un niveau de discrimination significatif. Ces résultats sont d’abord observés lors d’une expérience élémentaire puis confirmés par un test à moyenne échelle,mettant en jeu 500 symboles issus de la base de données Graphics Recognition – GREC2003. 

Keywords: 

Document analysis,Graphical symbol recognition,Feature extraction,Minimal graphs,Discrete Cosine Transform,Image Compression.

Mots clés 

Analyse de documents,Reconnaissance de symboles,Extraction de caractéristiques,Arbres minimaux, Transformation en Cosinus Discrète,Compression d’Image

1.Introduction
2.Organisation de l’Article
3.Reconnaissance de Symboles par Arbres Minimaux Construits sur le Mmélange
4.Réduction du Coût Algorithmique
5.Reconnaissance de Symboles Graphiques dans l’Espace «Compressé»
6.Conclusion
  References

[ADA 01] ADAM S., OGIER J.-M., CARIOU C., MULLOT R., GARDESJ., LECOURTIER, «Utilisation de la transformée de Fourier-Mellin pour la reconnaissance de formes multi-orientées et multi-échelles: application à l'analyse automatique de documents techniques», Traitement du Signal, vol. 18, n° 1, 2001, p. 17-33. 

[AHM 74] AHMED N., NATARAJAN T., RAO K., «On image processing and a discrete cosine transform», IEEE Transactions on Computers, vol. C-23, n° 1, 1974, p. 90-93. 

[AHS 01] AH-SOONC.,TOMBREK.,«Architectural symbol recognition using a network of constraints», Pattern Recognition Letters, vol. 22, n° 2, 2001, p. 231-248. 

[AIR 95] AIRAULT S., JAMET O., «Détection et restitution automatique du réseau routier sur des images aériennes», Traitement du Signal, vol. 12, n° 2, 1995, p. 189-200. 

[BHA 94] BHATTACHARJEE S., MONAGAN G., «Recognition of cartographic symbols», IAPR Workshop on Machine Vision Applications, Japan 1994, p. 226-229. 

[BUN 00] BUNKE H., «Recent developments in graph matching», In the 15th International Conference on Pattern Recognition, vol. 2, Spain 2000, p. 117-125.

[CHE 84] CHEN W., PRATT K., «Scene adaptative coder», IEEE Transactions on Communications, vol. COM-32, 1984, p. 225-232. 

[COR 94] CORMEN T., LEISERSON C., RIVEST R., Introduction to algorithms, The MIT Press, 1994. 

[DEL 94] DELLA VENTURA A., SCHETTINI R., «Graphic symbol recognition using a signature technique», In the 12th International Conference on Pattern Recognition, Israel 1994, p. 533-535. 

[EBI 94] EBI N., LAUTERBACH B., ANHEIERW., «An image analysis system for automatic data acquisition from colored scanned maps», Machine Vision and Application, 1994, p. 148-164. 

[FUK 92] FUKUMI M., OMATU S., TAKEDAN T., «Rotation invariant neural pattern recognition system with application to coin recognition», IEEE Transactions on Neural Networks, vol. 3, 1992, p. 272279. 

[GER 99] GERSHO A., GRAY R. M., Vector Quantization and Signal Compression, Kluwer Academic Publishers, Boston,1992 (6e edition, 1999). 

[GRA 85] GRAHAM R., HELL P., «On the history of minimum spanning tree problem», IEEE Annals of the History of Computing, vol. 7, n°1, 1985, p. 43-57. 

[GRE03] Fifth IAPR International Workshop on Graphics Recognition, Computer Vision Center, Barcelona, Catalonia, Spain, July 30-31, 2003.

[GUI 94] GUICHARD J., NASSE D., «Traitement des images numériques pour la réduction du débit binaire», Le Traitement du Signal – Actes des Forums de France Télécom Recherche, n° 2, 1994, p. 1-15. 

[HAA 10] HAARA., «Zur Theorie der Orthogonalen Funktionensysteme», Math. Ann., n° 69, 1910, p. 331-371. 

[HER 97] HERO A., MICHEL O., «Robust estimation of point process intensity features using k-minimal spanning trees», IEEE International Symposium on Information Theory, Germany June 1997, page 74. 

[HER 99] HEROA., MICHEL O., «Asymptotic theory of greedy approximations to minimal K-point random graphs», IEEE Transactions on Information Theory, vol. IT 45, 1999, p. 1921-1939. 

[HUA 99] HUANG C. L., LIN W., «Automatic Taiwanese municipal color reading system», Vision Interface'99, Canada, 19-21 May 1999. 

[KAR 95] KARGER D., KLEIN P., TARJAN R., «A randomized lineartime algorithm to find Minimum Spanning Trees», Journal of the Association for Computing Machinery (ACM), vol. 42, n° 2, 1995, p. 321-328. 

[KRE 94] KRESCH R., MALAH D., «Morphological reduction of skeleton redundancy», Signal Processing, vol. 38, 1994, p. 143-151. 

[LEE 92] LEE S.-W., «Recognizing hand-drawn electrical circuit symbols with attributed graph matching», H.S. Baird, H. Bunke, K. Yamamoto (eds.), Structured Document Image Analysis, Springer-Verlag, 1992, p. 340-358. 

[LIN 85] LIN X., SHIMOTSUJI S., MINOH M., SAKAI T., «Efficient diagram understanding with characteristic pattern detection», Computer Vision,Graphics and Image Processing,vol. 30,n°1,1985, p. 84-106. 

[LIN 87] LIN C., «New forms of shape invariants from elliptic Fourier Descriptors», Pattern Recognition, , n° 20, 1987, p. 535-545. 

[LLA 01] LLADÓS J., VALVENY E., SANCHEZ G., MARTÍ E., «Symbol Recognition: current advances and perspectives», GREC 2001, 2001, p. 104-127. 

[LLA 03] LLADÓS J., VALVENY E., SÁNCHEZ G., «A Case Study of Pattern Recognition: Symbol Recognition in Graphic Documents», Pattern Recognition in Information Systems, 2003, p. 1-13. 

[LLA 04] LLADÓS J., SÁNCHEZ G., «Graph matching versus graph parsing in graphics recognition – a combined approach», International Journal of Pattern Recognition and Artificial Intelligence (IJPRAI), vol. 18, n° 3, 2004, p. 455-473. 

[LOE 89] LOEFFLERC.,LIGTENBERGA.,MOSCHYTZG.,«Practical Fast 1-D DCT Algorithms with 11 Multiplications», International Conference on Acoustics, Speech, and Signal Processing (ICASSP '89), 1989, p. 988-991. 

[MA 00] MA B., HEROA., GORMAN J., MICHEL O., «Image registration with minimal spanning tree algorithm», IEEE International Conference on Image Processing, Vancouver October 2000. 

[MAL 89] MALLAT S. G., «Theory for Multiresolution Signal Decomposition:The Wavelet Representation», IEEE Transactions on PAMI, vol. 11, n° 7, 1989, p. 674-693. 

[MAR 86] MARAGOS P., SHAFER R., «Morphological skeleton representations and coding of binary images», IEEE Transactions on Accoustics, Speach and Signal Processing, vol. 34, n° 5, 1986, p.1228-1244. 

[MAR 97] MARIANI R., LECOURT F., DESEILLIGNY M., LABICHEJ., LECOURTIER Y., «Interprétation de cartes géographiques. Algorithme de reconstruction des réseaux hydrographiques et routiers», Traitement du Signal, vol. 14, n° 3, 1997, p. 317-335. 

[MER 97] MERCY P., TACONET B., MAINI J.-L., «Une méthode de vectorisation de dessin techniques adaptée aux plans mécaniques», 16ième colloque GRETSI, Grenoble, 15-19 septembre 1997, p. 869872.

[OGI 95] OGIER J.-M., MULLOT R., LABICHE J., LECOURTIER Y., «Interprétation de document par cycles perceptifs de construction d'objets cohérents. Application aux données cadastrales», Traitement du Signal, vol. 12, n° 6, 1995, p. 627-637. 

[PAS 96] PASTERNAK B., «Adaptierbares kernsystem zur interpretation von zeichnungen», Dissertation zur erlangung des akademischen grades eines doktors der naturwissenschaften (Dr. rer. nat.), Universität Hamburg,April 1996. 

[PEI 92] PEI S., LIN C., «Normalisation of rotationally symmetric shapes for pattern recognition», Pattern Recognition, n° 25, 1992, p. 913-920. 

[PEN 93] PENNEBAKERW., MITCHELL J., The JPEG Still Image Data Compression Standard, Van Nostrand Reinhold, New York, 1993. 

[RAO 90] RAO K., YIP P., Discrete Cosine Transforms – Algorithms, Advantages, Applications,Academic Press, Boston, 1990. 

[RED 94] REDMOND C., YUKICH J., «Limit theorems and rates of convergence for Euclidean functionals», Annals of Applied Probability, vol. 4, n°4, 1994, p. 1057-1073. 

[RÉN 61] RÉNY A., «On measures of entropy and information», Symposium on Mathematics Statistics and Probabilities, Berkeley 1961, p. 547-561. 

[SER 88] SERRA J., Image analysis and mathematical morphology Volume 2: Theoretical Advances,Academic Press, London, 1988. 

[SOS 98] SOSS M., «On the size of the sphere on influence graph», PhD thesis, Mc Gill University Scholl of Computer Science Montreal, 1998. 

[STE 88] STEELE J., «Growth rate of euclidean minimal spanning trees with power weigghted edges», Annals of Probability, vol. 16, 1988, p. 1767-1787. 

[TAB 01a]TABBONE S., WENDLING L., TOMBRE K., «Indexing of technical line drawings based on F-signatures», In the 6th International Conference on Document Analysis and Recognition, Seattle (Washington, USA), 2001, p. 1220-1224. 

[TAB 01b]TABBONE S., WENDLING L., TOMBRE K., «Indexing of technical line drawings based on F-Signatures», 6th International Conference on Document Analysis and Recognition (ICDAR), Seattle, Washington, USA Sept 2001, p. 1220-1224. 

[TAB 04] TABBONE S., WENDLING L., «Recognition of symbols in grey level line drawings from an adaptation of the Radon transform», In the 17th International Conference on Pattern Recognition, Cambridge (UK), 2004, p. 570-573. 

[TAX 90] TAXT T., OLAFSDOTTIR J., DAEHLEN M., «Recognition of handwritten symbols», Pattern Recognition, vol. 23, 1990, p. 11551166. 

[TOM 03] TOMBRE K., LAMIROY B., «Graphics Recognition – from Re-engineering to Retrieval», In 7th International Conference on Document Analysis and Recognition (ICDAR 2003), IEEE Computer Society, 2003, p. 148-156. 

[TRI 96] TRIER D., JAINA., TAXT T., «Features extraction methods for character recognition – a survey», Pattern Recognition, vol. 29, 1996, p. 641-662. 

[VET 95] VETTERLI M., KOVACEVIC J., Wavelets and Subband Coding, Englewood Cliffs, Prentice Hall, 1995. 

[WAL 91] WALLACE G., «The JPEG still picture compression standard», Communications of the Association for Computing Machinery, vol.34, n° 4, 1991, p. 30-44. 

[YU 94] YUY., SAMALA., SETH S., «Isolating symbols from connected lines in a class of engineering drawings», Pattern Recognition, vol. 27, n° 3, 1994, p. 391-404.