Skip to main content

2015 | OriginalPaper | Buchkapitel

Shape Matching Based on Skeletonization and Alignment of Primitive Chains

verfasst von : Olesia Kushnir, Oleg Seredin

Erschienen in: Analysis of Images, Social Networks and Texts

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We introduce a new shape matching approach based on skeletonization and alignment of primitive chains. At the first stage the skeleton of a binary image is traversed counterclockwise in order to encode it by chain of primitives. A primitive describes topological properties of the correlated edge and consists of a pair of numbers: the length of some edge and the angle between this and the next edges. We offer to expand a primitive by the information about the radial function of the skeleton rib. To get the compact width description we interpolate radial function by Legendre polynomials and find the vector of Legendre coefficients. Thus the resulting shape representation by the chain of primitives includes not only topological properties but also the contour ones. Then we suggest the dynamic programming procedure of the alignment of two primitive chains in order to match correspondent shapes. Based on the optimal alignment we propose the pair-wise dissimilarity function which is evaluated on artificial image dataset and the Flavia leaf dataset.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Attali, D., Sanniti di Baja, G., Thiel, E.: Skeleton simplification through non significant branch removal. Image Process. Commun. 3(3–4), 63–72 (1997) Attali, D., Sanniti di Baja, G., Thiel, E.: Skeleton simplification through non significant branch removal. Image Process. Commun. 3(3–4), 63–72 (1997)
2.
Zurück zum Zitat Bai, X., Latecki, L.J.: Path similarity skeleton graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 30(7), 1282–1292 (2008)CrossRef Bai, X., Latecki, L.J.: Path similarity skeleton graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 30(7), 1282–1292 (2008)CrossRef
3.
Zurück zum Zitat Balfer, J., Schöler, F., Steinhage V.: Semantic Skeletonization for Structural Plant Analysis. Submitted to International Conference on Functional-Structural Plant Models (2013) Balfer, J., Schöler, F., Steinhage V.: Semantic Skeletonization for Structural Plant Analysis. Submitted to International Conference on Functional-Structural Plant Models (2013)
4.
Zurück zum Zitat Beghin, T., Cope, J.S., Remagnino, P., Barman, S.: Shape and texture based plant leaf classification. In: Blanc-Talon, J., Bone, D., Philips, W., Popescu, D., Scheunders, P. (eds.) ACIVS 2010, Part II. LNCS, vol. 6475, pp. 345–353. Springer, Heidelberg (2010) CrossRef Beghin, T., Cope, J.S., Remagnino, P., Barman, S.: Shape and texture based plant leaf classification. In: Blanc-Talon, J., Bone, D., Philips, W., Popescu, D., Scheunders, P. (eds.) ACIVS 2010, Part II. LNCS, vol. 6475, pp. 345–353. Springer, Heidelberg (2010) CrossRef
5.
Zurück zum Zitat Blum, H.: A transformation for extracting new descriptors of shape. Models Percept. Speech Vis. Form 19(5), 362–380 (1967) Blum, H.: A transformation for extracting new descriptors of shape. Models Percept. Speech Vis. Form 19(5), 362–380 (1967)
6.
Zurück zum Zitat Bystrov, M.Y.: Structural approach application for recognition of binary image skeleton. Proc. Petrozavodsk State Univ. 2(115), 76–80 (2011). (in Russian) Bystrov, M.Y.: Structural approach application for recognition of binary image skeleton. Proc. Petrozavodsk State Univ. 2(115), 76–80 (2011). (in Russian)
7.
Zurück zum Zitat Demirci, M.F., Shokoufandeh, A., Keselman, Y., Bretzner, L., Dickinson, S.: Object recognition as many-to-many feature matching. Int. J. Comput. Vision 69(2), 203–222 (2006)CrossRefMATH Demirci, M.F., Shokoufandeh, A., Keselman, Y., Bretzner, L., Dickinson, S.: Object recognition as many-to-many feature matching. Int. J. Comput. Vision 69(2), 203–222 (2006)CrossRefMATH
8.
Zurück zum Zitat Du, J.X., Huang, D.S., Wang, X.F., Gu, X.: Computer-aided plant species identification (CAPSI) based on leaf shape matching technique. Trans. Inst. Measur. Control 28(3), 275–285 (2006)CrossRef Du, J.X., Huang, D.S., Wang, X.F., Gu, X.: Computer-aided plant species identification (CAPSI) based on leaf shape matching technique. Trans. Inst. Measur. Control 28(3), 275–285 (2006)CrossRef
11.
Zurück zum Zitat Jänichen, S., Perner, P.: Aligning concave and convex shapes. In: Yeung, D.-Y., Kwok, J.T., Fred, A., Roli, F., de Ridder, D. (eds.) SSPR 2006 and SPR 2006. LNCS, vol. 4109, pp. 243–251. Springer, Heidelberg (2006) CrossRef Jänichen, S., Perner, P.: Aligning concave and convex shapes. In: Yeung, D.-Y., Kwok, J.T., Fred, A., Roli, F., de Ridder, D. (eds.) SSPR 2006 and SPR 2006. LNCS, vol. 4109, pp. 243–251. Springer, Heidelberg (2006) CrossRef
12.
Zurück zum Zitat Kadir, A., Nugroho, L.E., Susanto, A., Santosa, P.I.: A comparative experiment of several shape methods in recognizing plants (2011). arXiv preprint arXiv:1110.1509 Kadir, A., Nugroho, L.E., Susanto, A., Santosa, P.I.: A comparative experiment of several shape methods in recognizing plants (2011). arXiv preprint arXiv:​1110.​1509
13.
Zurück zum Zitat Klein, P., Tirthapura, S., Sharvit, D., Kimia, B.: A tree-edit-distance algorithm for comparing simple, closed shapes. In: Proceedings of the eleventh annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 696–704 (2000) Klein, P., Tirthapura, S., Sharvit, D., Kimia, B.: A tree-edit-distance algorithm for comparing simple, closed shapes. In: Proceedings of the eleventh annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 696–704 (2000)
14.
Zurück zum Zitat Kushnir, O., Seredin, O.: Parametric description of skeleton radial function by legendre polynomials for binary images comparison. In: Elmoataz, A., Lezoray, O., Nouboud, F., Mammass, D. (eds.) ICISP 2014. LNCS, vol. 8509, pp. 520–530. Springer, Heidelberg (2014) Kushnir, O., Seredin, O.: Parametric description of skeleton radial function by legendre polynomials for binary images comparison. In: Elmoataz, A., Lezoray, O., Nouboud, F., Mammass, D. (eds.) ICISP 2014. LNCS, vol. 8509, pp. 520–530. Springer, Heidelberg (2014)
15.
Zurück zum Zitat Lam, L., Lee, S.-W., Suen, C.Y.: Thinning methodologies - a comprehensive survey. IEEE Trans. Pattern Anal. Mach. Intell. 14(9), 869–885 (1992)CrossRef Lam, L., Lee, S.-W., Suen, C.Y.: Thinning methodologies - a comprehensive survey. IEEE Trans. Pattern Anal. Mach. Intell. 14(9), 869–885 (1992)CrossRef
17.
Zurück zum Zitat Lee, D.: Medial axis transformation of a planar shape. IEEE Trans. Pat. Anal. Mach. Int. PAMI 4(4), 363–369 (1982)CrossRefMATH Lee, D.: Medial axis transformation of a planar shape. IEEE Trans. Pat. Anal. Mach. Int. PAMI 4(4), 363–369 (1982)CrossRefMATH
18.
Zurück zum Zitat Mallah, C., Cope, J., Orwell, J.: Plant leaf classification using probabilistic integration of shape, texture and margin features. Computer Graphics and Imaging/798: Signal Processing, Pattern Recognition and Applications (CGIM2013), Acta Press (2013). doi:10.2316/P.2013.798-098 Mallah, C., Cope, J., Orwell, J.: Plant leaf classification using probabilistic integration of shape, texture and margin features. Computer Graphics and Imaging/798: Signal Processing, Pattern Recognition and Applications (CGIM2013), Acta Press (2013). doi:10.​2316/​P.​2013.​798-098
19.
Zurück zum Zitat Maragos, P.: Pattern spectrum and multiscale shape representation. IEEE Trans. Pattern Anal. Mach. Intell. 11(7), 701–716 (1989)CrossRefMATH Maragos, P.: Pattern spectrum and multiscale shape representation. IEEE Trans. Pattern Anal. Mach. Intell. 11(7), 701–716 (1989)CrossRefMATH
20.
Zurück zum Zitat Mestetskiy, L., Semenov, A.: Binary image skeleton - continuous approach. VISAPP 1, 251–258 (2008) Mestetskiy, L., Semenov, A.: Binary image skeleton - continuous approach. VISAPP 1, 251–258 (2008)
21.
Zurück zum Zitat Mottl, V.V., Blinov, A.B., Kopylov, A.V., Kostin, A.A.: Optimization techniques on pixel neighborhood graphs for image processing. In: Jolion, J.-M., Kropatsch, W.G. (eds.) Graph-Based Representations in Pattern Recognition. Computing Supplement, vol. 12, pp. 135–145. Springer, Wien (1998) CrossRef Mottl, V.V., Blinov, A.B., Kopylov, A.V., Kostin, A.A.: Optimization techniques on pixel neighborhood graphs for image processing. In: Jolion, J.-M., Kropatsch, W.G. (eds.) Graph-Based Representations in Pattern Recognition. Computing Supplement, vol. 12, pp. 135–145. Springer, Wien (1998) CrossRef
22.
Zurück zum Zitat Mottl, V., Seredin, O., Dvoenko, S., Kulikowski, C., Muchnik, I.: Featureless pattern recognition in an imaginary Hilbert space. In: Proceedings of 16th International Conference on Pattern Recognition, vol. 2, pp. 88–912 (2002) Mottl, V., Seredin, O., Dvoenko, S., Kulikowski, C., Muchnik, I.: Featureless pattern recognition in an imaginary Hilbert space. In: Proceedings of 16th International Conference on Pattern Recognition, vol. 2, pp. 88–912 (2002)
23.
Zurück zum Zitat Mottl, V., Krasotkina, O., Seredin, O., Muchnik, I.: Kernel fusion and feature selection in machine learning. In: Proceedings of the Eighth IASTED International Conference on Intelligent Systems and Control, Cambridge, USA, pp. 477–482 (2005) Mottl, V., Krasotkina, O., Seredin, O., Muchnik, I.: Kernel fusion and feature selection in machine learning. In: Proceedings of the Eighth IASTED International Conference on Intelligent Systems and Control, Cambridge, USA, pp. 477–482 (2005)
24.
Zurück zum Zitat Neuhaus, M., Bunke, H.: Edit distance-based kernel functions for structural pattern classification. Pattern Recogn. 39(10), 1852–1863 (2006)CrossRefMATH Neuhaus, M., Bunke, H.: Edit distance-based kernel functions for structural pattern classification. Pattern Recogn. 39(10), 1852–1863 (2006)CrossRefMATH
25.
Zurück zum Zitat Ogniewicz, R., Kubler, O.: Hierarchic voronoi skeletons. Pattern Recogn. 28(3), 343–359 (1995)CrossRef Ogniewicz, R., Kubler, O.: Hierarchic voronoi skeletons. Pattern Recogn. 28(3), 343–359 (1995)CrossRef
26.
Zurück zum Zitat Ogniewicz, R.: Automatic medial axis pruning by mapping characteristics of boundaries evolving under the euclidean geometric heat flow onto Voronoi skeletons. Harvard Robotics Laboratory Technical report, pp. 95–114 (1995) Ogniewicz, R.: Automatic medial axis pruning by mapping characteristics of boundaries evolving under the euclidean geometric heat flow onto Voronoi skeletons. Harvard Robotics Laboratory Technical report, pp. 95–114 (1995)
27.
Zurück zum Zitat Reier, I.A.: Plane figure recognition based on contour homeomorphism. Pattern Recogn. Image Anal. 11(1), 242–245 (2001) Reier, I.A.: Plane figure recognition based on contour homeomorphism. Pattern Recogn. Image Anal. 11(1), 242–245 (2001)
28.
Zurück zum Zitat Sanniti di Baja, G., Thiel, E.: Computing and comparing distance-driven skeletons. In: Aspects of Visual Form Processing, pp. 465–486 (1994) Sanniti di Baja, G., Thiel, E.: Computing and comparing distance-driven skeletons. In: Aspects of Visual Form Processing, pp. 465–486 (1994)
29.
Zurück zum Zitat Sebastian, T.B., Kimia, B.: Curves vs. skeletons in object recognition. Sig. Process. 85(2), 247–263 (2005)CrossRefMATH Sebastian, T.B., Kimia, B.: Curves vs. skeletons in object recognition. Sig. Process. 85(2), 247–263 (2005)CrossRefMATH
30.
Zurück zum Zitat Sederberg, T.W., Greenwood, E.: A physically based approach to 2-D shape blending. Comput. Graph. 26(2), 25–34 (1992)CrossRef Sederberg, T.W., Greenwood, E.: A physically based approach to 2-D shape blending. Comput. Graph. 26(2), 25–34 (1992)CrossRef
31.
Zurück zum Zitat Serra, J.: Image Analysis and Mathematical Morphology. Acad. Press, London (1982)MATH Serra, J.: Image Analysis and Mathematical Morphology. Acad. Press, London (1982)MATH
32.
Zurück zum Zitat Shen, W., Bai, X., Yang, X., Latecki, L.J.: Skeleton pruning as trade-off between skeleton simplicity and reconstruction error. Sci. China Inf. Sci. 56(4), 1–14 (2013)CrossRef Shen, W., Bai, X., Yang, X., Latecki, L.J.: Skeleton pruning as trade-off between skeleton simplicity and reconstruction error. Sci. China Inf. Sci. 56(4), 1–14 (2013)CrossRef
33.
Zurück zum Zitat Shen, W., Wang, X., Yao, C., Bai, X.: Shape recognition by combining contour and skeleton into a mid-level representation. In: Li, S., Liu, C., Wang, Y. (eds.) CCPR 2014, Part I. CCIS, vol. 483, pp. 391–400. Springer, Heidelberg (2014) Shen, W., Wang, X., Yao, C., Bai, X.: Shape recognition by combining contour and skeleton into a mid-level representation. In: Li, S., Liu, C., Wang, Y. (eds.) CCPR 2014, Part I. CCIS, vol. 483, pp. 391–400. Springer, Heidelberg (2014)
34.
Zurück zum Zitat Söderkvist, O.: Computer Vision Classification of Leaves from Swedish Trees. Diss, Linköping (2001) Söderkvist, O.: Computer Vision Classification of Leaves from Swedish Trees. Diss, Linköping (2001)
35.
Zurück zum Zitat Vizilter, Y.V., Sidyakin, S.V., Rubis, A.Y., Gorbatsevich, V.S.: Morphological shape comparison based on skeleton representations. Pattern Recogn. Image Anal. 22(3), 412–418 (2012)CrossRef Vizilter, Y.V., Sidyakin, S.V., Rubis, A.Y., Gorbatsevich, V.S.: Morphological shape comparison based on skeleton representations. Pattern Recogn. Image Anal. 22(3), 412–418 (2012)CrossRef
37.
Zurück zum Zitat Wang, C., Gui, C.-P., Liu, H.-K., Zhang, D., Mosig, A.: An image skeletonization based tool for pollen tube morphology analysis and phenotyping. J. Integr. Plant Biol. 55(2), 131–141 (2013)CrossRef Wang, C., Gui, C.-P., Liu, H.-K., Zhang, D., Mosig, A.: An image skeletonization based tool for pollen tube morphology analysis and phenotyping. J. Integr. Plant Biol. 55(2), 131–141 (2013)CrossRef
38.
Zurück zum Zitat Wang, Z., Chi, Z., Feng, D.: Shape based leaf image retrieval. Vis. Image Sig. Process. IEE Proc. 150(1), 34–43 (2003)CrossRef Wang, Z., Chi, Z., Feng, D.: Shape based leaf image retrieval. Vis. Image Sig. Process. IEE Proc. 150(1), 34–43 (2003)CrossRef
39.
Zurück zum Zitat Wu, S.G., Bao, F.S., Xu, E.Y., Wang, Y.-X., Chang, Y.-F., Xiang, Q.-L.: A leaf recognition algorithm for plant classification using probabilistic neural network. In: 2007 IEEE International Symposium on Signal Processing and Information Technology, pp. 11–16 (2007) Wu, S.G., Bao, F.S., Xu, E.Y., Wang, Y.-X., Chang, Y.-F., Xiang, Q.-L.: A leaf recognition algorithm for plant classification using probabilistic neural network. In: 2007 IEEE International Symposium on Signal Processing and Information Technology, pp. 11–16 (2007)
Metadaten
Titel
Shape Matching Based on Skeletonization and Alignment of Primitive Chains
verfasst von
Olesia Kushnir
Oleg Seredin
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-26123-2_12