Concept Lattices: a Tool for Primitives Selection? Les Treillis de Galois: un Outil pour la Sélection de Primitives?

Concept Lattices: a Tool for Primitives Selection?

Les Treillis de Galois: un Outil pour la Sélection de Primitives?

Stéphanie Guillas Karell Bertet  Jean-Marc Ogier 

L31 Université de La Rochelle, av M. Crépeau, 17042 La Rochelle Cedex 1, France

19 May 2004
30 June 2005
| Citation



In this paper,we present the problem of noisy images recognition and in particular the stage of primitives selection in a classification process.This selection stage appears after segmentation and statistical describers extraction on documentary images are realized.We describe precisely the use of decision tree in order to harmonize and compare it with another less studied method based on a concept lattice.


Dans ce papier,nous présentons la problématique de la reconnaissance d'images détériorées et plus particulièrement l'étape de sélection de primitives au sein d'un traitement de classification supervisée. Cette étape de sélection a lieu après que la segmentation et l'extraction des descripteurs statistiques sur des images documentaires aient été réalisées. Nous exposons en détail l'utilisation d'un arbre de décision,afin de l'harmoniser puis la comparer avec une approche moins étudiée utilisant un treillis de Galois.


Symbol recognition,Concept lattice,Decision tree,Noisy images,Statistical describers.

Mots clés

Reconnaissance de symboles,treillis de Galois,arbre de décision,images détériorées, descripteurs statistiques.

1. Introduction
2. Contexte et Classification Supervisée
3. Arbre de Décision
4. Treillis de Galois
5. Expérimentation
6. Conclusion et Perspectives

[AOC+99] S. ADAM, J.M. OGIER, C. CARIOU, R. MULLOT, J. GARDES and Y. LECOURTIER, Multi-scaled and multi oriented character recognition: An original strategy, ICDAR'99,pages 45-48, Septembre 1999. 

[AOC+01] S. ADAM, J.M. OGIER, C. CARIOU, R. MULLOT, J. GARDES and Y. LECOURTIER, Utilisation de la transformée de Fourier-Mellin pour la reconnaissance de forme multi-orienté et multi-échelle: application l'analyse automatique de documents tecniques. Traitement du Signal, 18(1):17-33, 2001.

[AS98] C. AH SOON, Analyse de plans architecturaux. PhD thesis, Institut National Polytechnique de Lorraine, 1998. 

[BDF86] R. BAMIEH and R. DE FIGUEIREDO, A general moments invariants/attributed graph method for the three dimensional object recognition from a single image. IEEE Journal of Robotics Automation, 2:240-242, 1986. 

[BFOS84] L. BREIMAN, J.H. FRIEDMAN, R.A. OLSHEN and C.J. STONE, Classification and regtession trees. Wadsworth Inc., Belmont, California, 1984. 

[BIR67] G. BIRKHOFF, Lattice theory,volume 25. American Mathematical Society, 3rd edition, 1967. 

[BK99] E. BAUER, R. KOHAVI, An empirical comparison of voting classification algorithms: Bagging, boosting, and variants. Machine Learning, 36((1-2): 105-139, 1999. 

[BM] M. BARBUT, B. MONJARDET, Ordre et classification, Algèbre et combinatoire. 

[BN04] K. BERTET, M. NEBUT, Efficient algorithms on the family associated to an implicationnal system. Discrete Mathematical and Theoretical Computer Science (DMTCS), 6(2): 315-338, 2004.

[BOR86] J.P. BORDAT, Calcul pratique du treillis de Galois d'une correspondance. Math. Sci. Hum.,96:31-47, 1986. 

[BSA91] S.O. BELKASIM, M. SHRIDAR and M. AHMADI, Pattern recognition with moment invariants: a comparative study and new results. Pattern Recognition,24:1117-1138, 1991. 

[CF04] D.R. CARVALHO and A.A. FREITAS,A hybrid decision tree/genetic algorithm method for data mining. Information Science, 163(1-3): 13-35, June 2004. 

[CLD96] Y. CHEN, N.A. LANGRANA, and A.K. DAS, Perfecting vectorized mechanical drawings. Computer Vision and Image understanding, 63(2): 273-286, 1986. 

[DBM77] S.A. DUDANI, K.J. BREDDING and R.M. MCGHEE, Aircraft identification by moment invariants. IEEE Trans on Computers, 26: 39-45, 1977. 

[DBN92] M. DAI, P. BAYLOU, and M. NAJIM, An efficient algorithm for computation of shape moments from run-length codes or chain codes. Pattern Recognition,25:1119-1128, 1992. 

[DKS95] J. DOUGHERTY, R. KOHAVI and M. SAHAMI, Supervised and unsupervised discretization of continuous features. Morgan Kaufman, 1995. 

[DP91] B.A. DAVEY and H.A. PRIESTLEY, Introduction to lattices and orders. Cambridge University Press, 2nd edition, 1991. 

[FF92] A.J. FILIPSKI and R. FLANDRENA, Automated conversion of engineering drawings to cad form. Proc. IEEE, 80(7): 1195-1209, 1992. 

[FI93] U.M. FAYYAD and K.B. IRANI, Multi-interval discretization of continuous-valued attributes for classification learning. Morgan Kaufman, 1993. 

[FK] L.A. FLETCHER and R. KASTURI,A robust algorithm for text string separation from mixed text/graphics images. IEEE Trans. on PAMI, 10(6): 910-918, 1998. 

[FOTK92] M. FUKUMI, S. OMATU, T. TAKEDA and T. KOSAKA, Rotation invariant neural pattern recognition system with application to coin recognition. IEEE Trans. on Neural Networks,3:272-279, 1992. 

[GD86] J.L. GUIGUES and V. DUQUENNE, Familles minimales d'implications informatives résultant d'un tableau de données binaires. Mathématiques et Sciences Humaines,95:5-18, 1986. 

[GEL05] A. GELY, A generic algorithm for generating closed sets of binary relation. Formal Concept Analysis, Third Int. Conf., ICFCA 2005, pages 223-234, February 2005. 

[GM93] R. GODIN and H. MILI, Building and maintening analysis-level class hierarchies using Galois lattices. OOPSLA,pages 394-410, 1993. 

[GML] V. GUNES, M. MENARD and P. LOONIS, A multiple classifier system using ambiguity rejection for clustering-classification cooperation. IJUFKS, Worl Scientific. 

[GOL89] D.E. GOLDBERG, Genetic algorithms in search, optimization and machine learning. Addison-Wesley Publishing Company, 1989.

[GRE03] GREC,, 2003. 

[GW99] B. GANTER and R. WILLE, Format concept analysis, Mathematical foundations. Springer Verlag, Berlin, 1999. 

[HOL93] R.C. HOLTE, Very simple classification rules perform well on most commonly used datasets. Machines Learning,11:63-90, 1993. 

[HU62] M.K. HU, Visual pattern recognition by moment invariants. IRE Trans. On Information Theory,8:179-187, 1962. 

[KG82] F.P. KUHL and C.R. GIARDINA, Elliptic Fourier features of closed contour. Computer Vision, Graphics and Image Processing, 18:236-258, 1982. 

[KH90a] A. KHOTANZAD and Y.H. HONG, Invariant image recognition by zernike moments. IEEE Trans. on PAMI, 12(5):489-497, 1990. 

[KH90b] A. KHOTANZAD and Y.H. HONG, Invariant image recognition using features selected via a systemaic method. Pattern Recognition, 23:1089-1101, 1990. 

[KHB+94] T. KANUNGO, R.M. HARALICK, H.S. BAIRD, W. STUETZLE and D. MADIGAN, Document degradation models : parameter estimation and model validation. In IAPR Workshop on machine vision applications,Kawasaki (Japan), pages 552-557, 1994. 

[KIT92] N. KITA, Object locating based on concentric circular description. Proc. 11th IEEE International Conference of Pattern Recognition, The Hague,1:637-641, 1992. 

[KJL+94] R. KOHAVI, G. JOHN, R. LONG, D. MANLEY and K. PFLEGER. MLC++: A machine learning library in C++. IEEE Computer Society Press, 1994. 

[KO01] S. KUZNATSOV, S. OBIEDKOV, Comparing performance of algorithms for generating concept lattices. In Proceedings of ICCS'01 workshop on Concept Lattices for Knowledge Discovery in Databases (CLKDD),volume 42, pages 35-47, July 2001. 

[LCD97] N.A. LANGRANA, Y. CHEN and A.K. DAS, Feature identification from vectorized mechanical drawings. Computer Vision and Image Understanding, 68(2): 127-145, 1997. 

[LEF99] L. LEFRERE, Contribution au Développement d'Outils pour l'Analyse Automatique de Documents Cartographiques. PhD thesis, Université de Rouen, 1999. 

[LIN87] C.H. LIN, New forms of shape invariants from elliptic Fourier descriptors. Pattern Recognition,20:535-545, 1987. 

[LK94] C.P. LAI and R. KASTURI, Detection of dimension sets in engineering drawings. IEEE Trans. on PAMI, 16(8): 848-855, 1994. 

[LP98] S.X. LIAO and M. PAWLAK. On the accuracy of zernike moments for image analysis. IEEE Trans. on PAMI, 20(12)): 1358-1364, 1998. 

[LS91] B.C. LIN and J. SHEN, Fast computation of moment invariants. Pattern Recognition, 24): 807-813, 1991. 

[LU98] Z. LU, Detection of text regions from digital engineering drawings. IEEE Trans. on PAMI, 20(4)): 431-439, 1998. 

[LVSM01] J. LLADOS, E. VALVENY, G. SANCHEZ and E. MARTI, Symbol recognition, current advances and perceptives. Les actes de IAPR International Workshop on Graphics RECgnition (GREC), Kingston, Canada, pages 109-129, 2001.

[MNN05] E. MEPHU NGUIFO, P. NJIWOUA, Treillis des concepts et classification supervisée. In Technique et Science Informatiques (à paraître), RSTI. Herm-Lavoisier, Paris, France, 2005. 

[NB86] T. NIBLETT, I. BRATKO, Learning decision rules in noisy domains. Cambridge University Press, 1996. 

[NR99] L. NOURINE, O. RAYNAUD, A fast algorithm for building lattices. In Third International Conference on Orders, Algorithms and Applications, Montpellier, august 1999. 

[PL92] S.C. PEI, C.N. LIN, Normalisation of rotationally symmetric shapes for pattern recognition. Pattern Recognition,25:913-920, 1992. 

[PN93] B. PASTERNAK and B. NEUMANN, Adik: An adaptable drawing interpretation Kernel. Les actes de International Joint Conference on Artificial Intelligence (IJCAI), Avignon,1:531-540, 1993.

[QUI87] J.R. QUILAN, Simplifying decision trees. International Journal of ManMachine Studies,27:221-234, 1987. 

[QUI93] J.R. QUILAN. C4.5: Programs for Machine Learning. Morgan Kaufman, Los Altos, California, 1993. 

[QUI96] J.R. QUINLAN, Bagging, boosting and C4.5. AAAI Press, Menlo Park, CA, 1996. 

[RAK97] R. RAKOTOMALALA, Graphes d'induction. PhD thesis, Université Claude Bernard, Lyon I, Décembre 1997. 

[RSV96] I. ROTHE, H. SUSSE and K. VOSS, The method of normalization to determine invariants. IEEE Trans. on PAMI, 18(4): 366-379, 1996. 

[SEM04] D. SEMANI, Sélection de variables pour la caractérisation d'objets déformables en mouvement – Application à la reconnaissance temps réels de Poissons dans des séquences vidéos, Projet Aq@thèque. PhD thesis, Université de La Rochelle, 2004. 

[SHA+92] S. SHIMOTSUJI, O. HORI, M. ASANO, K. SUSUKI, F. HOHINO and T. ISHII, A robust recognition system for a drawing superimposed on a map. IEEE Computer magazine, 25(7): 56-64, 1992.

[TC88] C. TEH and R. CHIN, On image analysis by the method of moments. IEEE Trans. on PAMI,10:496-512, 1988. 

[TEA80] M. TEAGUE, Image analysis via the general theory of moments. Journal of Optical Society of America, 70:920-930, 1980. 

[TJT96] O.D. TRIER,A.K. JAIN and T. TAXT, Features extraction methods for character recognition – a survey. Pattern Recognition,29: 641662, 1996. 

[TOD90] T. TAXT, J.B. OLAFSDOTTIR, M. DAEHLEN, Recognition of hand-written symbols. Pattern Recognition,23:1155-1166, 1990. 

[TOM96] K. TOMBRE, Quelques contributions à l'interprétation de documents techniques, habilitation à diriger des recherches, 1996. 

[TT97] O.D. TRIER, T. TAXT and A.K. JAIN, Recognition of digits in hydrographic maps: binary versus topographic analysis. IEEE Trans. on PAMI, 19(4): 399-404, 1997. 

[WIL82] R. WILLE, Restructuring lattice theory: an approach based on hierarchy on contexts. Ordered sets,pages 445-470, 1982. 

[ZJ96] D. ZONGER and A. JAIN, Algorithms for feature selection: An evluation. Proceedings if ICPR 96,2:18-22, 1996.