Partitioned iterated function systems with division and a fractal dependence graph in recognition of 2D shapes

Gdawiec, K. ; Domańska, D.

International Journal of Applied Mathematics and Computer Science, Tome 21 (2011) no. 4, pp. 757-767.

Résumé

One of the approaches in pattern recognition is the use of fractal geometry. The property of self-similarity of fractals has been used as a feature in several pattern recognition methods. All fractal recognition methods use global analysis of the shape. In this paper we present some drawbacks of these methods and propose fractal local analysis using partitioned iterated function systems with division. Moreover, we introduce a new fractal recognition method based on a dependence graph obtained from the partitioned iterated function system. The proposed method uses local analysis of the shape, which improves the recognition rate. The effectiveness of our method is shown on two test databases. The first one was created by the authors and the second one is the MPEG7 CE-Shape-1PartB database. The obtained results show that the proposed methodology has led to a significant improvement in the recognition rate.

Détail

Keywords: fractal, partitioned iterated function system, shape recognition, dependence graph
Mots-clés : fraktale, układ funkcji iteracyjnej, rozpoznawanie kształtu, graf zależności

Bibliographie

[1] Attalla, E. and Siy, P. (2005). Robust shape similarity retrieval based on contour segmentation polygonal multiresolution and elastic matching, Pattern Recognition 38(12): 2229-2241.

[2] Barni, M. (2006). Document and Image Compression, CRC Press, Boca Raton, FL.

[3] Barnsley, M. (1988). Fractals Everywhere, Academic Press, Boston, MA.

[4] Belongie, S., Malik, J. and Puzicha, J. (2002). Shape matching and object recognition using shape contexts, IEEE Transactions on Pattern Analysis and Machine Intelligence 24(4): 509-522.

[5] Bruno, O. M., Plotze, R. D. O., Falvo,M. and Castro, M.D. (2008). Fractal dimension applied to plant identification, Information Science 178(12): 2722-2733.

[6] Burger, W. and Burge, M. J. (2008). Digital Image Processing: An Algorithmic Introduction Using Java, Springer, New York, NY.

[7] Chandran, S. and Kar, S. (2002). Retrieving faces by the PIFS fractal code, 6th IEEE Workshop on Applications of Computer Vision, Orlando, FL, USA, pp. 8-12.

[8] Chang, Y. F., Lee, J. C., Mohd Rijal, O. and Syed Abu Bakar, S.A.R. (2010). Efficient online handwritten Chinese character recognition system using a two-dimensional functional relationship model, International Journal of Applied Mathematics and Computer Science 20(4): 727-738, DOI: 10.2478/v10006-010-0055-x.

[9] Dey, P. (2005). Basic principles and applications of fractal geometry in pathology-A review, Analytical Quantitative Cytology Histology 27(5): 284-290.

[10] Domaszewicz, J. and Vaishampayan, V. A. (1995). Graph theoretical analysis of the fractal transform, 1995 International Conference on Acoustics, Speech, and Signal Processing, Detroit, MI, USA, Vol. 4, pp. 2559-2562.

[11] Erra, U. (2005). Toward real time fractal image compression using graphics hardware, in G. Bebis, R. Boyle, D. Koracin and B. Parvin (Eds.), Advances in Visual Computing, Lecture Notes in Computer Science, Vol. 3804, Springer, Heidelberg, pp. 723-728.

[12] Felzenszwalb, P. F. and Schwartz, J. (2007). Hierarchical matching of deformable shapes, IEEE Conference on Computer Vision and Pattern Recognition, Minneapolis, MN, USA, Vol. 1, pp. 1-8.

[13] Fisher, Y. (1995). Fractal Image Compression: Theory and Application, Springer-Verlag, NewYork, NY.

[14] Gdawiec, K. (2009a). Fractal interpolation in modeling of 2D contours, International Journal of Pure and Applied Mathematics 50(3): 421-430.

[15] Gdawiec, K. (2009b). Local Fractal Analysis in Recognition of 2D Shapes, Ph.D. thesis, University of Silesia, Sosnowiec, (in Polish).

[16] Ghazel, M., Freeman, G. H. and Vrscay, E. R. (2003). Fractal image denoising, IEEE Transactions on Image Processing 12(12): 1560-1578.

[17] Golub, G. H. and van Loan, C. F. (1996). Matrix Computations, 3rd Edn., The Johns Hopkins University Press, Baltimore, MD.

[18] Harris, J. M., Hirst, J. L. and Mossinghoff, M. J. (2008). Combinatorics and Graph Theory, 2nd Edn., Springer, New York, NY.

[19] Huang, K. and Yan, H. (2000). Signature verification using fractal transformation, 15th International Conference on Pattern Recognition, Barcelona, Spain, Vol. 2, pp. 855-858.

[20] Kolumbán, J., Soós, A. and Varga, I. (2003). Self-similar random fractal measures using contraction method in probabilistic metric spaces, International Journal of Mathematics and Mathematical Sciences 2003(52): 3299-3313.

[21] Kouzani, A. Z. (2008). Classification of face images using local iterated function systems, Machine Vision and Applications 19(4): 223-248.

[22] Latecki, L. J., Lakamper, R. and Eckhardt, T. (2000). Shape descriptors for non-rigid shapes with a single closed contour, IEEE Conference on Computer Vision and Pattern Recognition, Hilton Head, SC, USA, Vol. 1, pp. 424-429.

[23] Ling, H. and Jacobs, D. W. (2005). Using the inner-distance for classification of articulated shapes, IEEE Conference on Computer Vision and Pattern Recognition, San Diego, CA, USA, Vol. 2, pp. 719-726.

[24] Linnell, T. A. and Deravi, F. (2004). Mapping vector accumulator: fractal domain feature for character recognition, Electronic Letters 40(22): 1406-1407.

[25] Mandelbrot, B. (1983). The Fractal Geometry of Nature, W. H. Freeman and Company, New York, NY.

[26] Meng, D., Cai, X., Su, Z. and Li, J. (2009). Photorealistic terrain generation method based on fractal geometry theory and procedural texture, 2nd IEEE International Conference on Computer Science and Information Technology, Beijing, China, pp. 341-344.

[27] Mokhtarian, F. and Bober, M. (2003). Curvature Scale Space Representation: Theory, Applications, and MPEG-7 Standardization, Springer, Heidelberg.

[28] Mozaffari, S., Faez, K. and Faradji, F. (2006). One dimensional fractal coder for online signature recognition, 18th International Conference on Pattern Recognition, Hong Kong, China, Vol. 2, pp. 857-860.

[29] Neil, G. and Curtis, K. M. (1997). Shape recognition using fractal geometry, Pattern Recognition 30(12): 1957-1969.

[30] Nikiel, S. (2007). A proposition of mobile fractal image decompression, International Journal of Applied Mathematics and Computer Science 17(1): 129-136, DOI: 10.2478/v10006-007-0012-5.

[31] Peters, E. E. (1994). Fractal Market Analysis: Applying Chaos Theory to Investment and Economics, John Wiley Sons Inc., New York, NY.

[32] Plotze, R. D. O., Falvo, M., Páuda, J.G., Bernacci, L. C., Vieira, M. L. C., Oliveira, G. C. X. and Bruno, O. M. (2005). Leaf shape analysis using the multiscale Minkowski fractal dimension, a new morphometric method: A study with passiflora (passifloraceae), Canadian Journal of Botany 83(3): 287-301.

[33] Prusinkiewicz, P. and Lindenmayer, A. (1996). The Algorithmic Beauty of Plants, Springer-Verlag, New York, NY.

[34] Skarbek, W. and Ignasiak, K. (1996). Asynchronous nonlinear fractal operators and their applications, Image Processing Communications 2(2): 3-20.

[35] Skarbek,W., Ignasiak, K. and Ghuwar, M. (1996). Fractal representation of planar shapes, in S. Miguet, A. Montanvert and S. Ubéda (Eds.), Discrete Geometry for Computer Imagery, Lecture Notes in Computer Science, Vol. 1176, Springer, Heidelberg, pp. 73-84.

[36] Tu, Z. and Yuille, A. L. (2004). Shape matching and recognition using generative models and informative features, 8th European Conference on Computer Vision, Prague, Czech Republic, pp. 195-209.

[37] Witten, I. H. and Frank, E. (2005). Data Mining-Practical Machine Learning Tools and Techniques, 2nd Edn., Morgan Kaufmann Publishers, San Francisco, CA.

[38] Xu, C., Liu, J. and Tang, X. (2009). 2D shape matching by contour flexibility, IEEE Transactions on Pattern Analysis and Machine Intelligence 31(1): 180-186.

[39] Yokoyama, T., Sugawara, K. and Watanabe, T. (2004). Similarity-based image retrieval system using partitioned iterated function system codes, Artifical Life and Robotics 8(2): 118-122.

[40] Zhao, G., Cui, L. and Li, H. (2007). Gait recognition using fractal scale, Pattern Analysis Applications 10(3): 235-246.