Skip to main content
SpringerLink
Log in

A protocol to characterize the descriptive power and the complementarity of shape descriptors

  • Original Paper
  • Published:
International Journal on Document Analysis and Recognition (IJDAR) Aims and scope Submit manuscript

Abstract

Most document analysis applications rely on the extraction of shape descriptors, which may be grouped into different categories, each category having its own advantages and drawbacks (O.R. Terrades et al. in Proceedings of ICDAR’07, pp. 227–231, 2007). In order to improve the richness of their description, many authors choose to combine multiple descriptors. Yet, most of the authors who propose a new descriptor content themselves with comparing its performance to the performance of a set of single state-of-the-art descriptors in a specific applicative context (e.g. symbol recognition, symbol spotting...). This results in a proliferation of the shape descriptors proposed in the literature. In this article, we propose an innovative protocol, the originality of which is to be as independent of the final application as possible and which relies on new quantitative and qualitative measures. We introduce two types of measures: while the measures of the first type are intended to characterize the descriptive power (in terms of uniqueness, distinctiveness and robustness towards noise) of a descriptor, the second type of measures characterizes the complementarity between multiple descriptors. Characterizing upstream the complementarity of shape descriptors is an alternative to the usual approach where the descriptors to be combined are selected by trial and error, considering the performance characteristics of the overall system. To illustrate the contribution of this protocol, we performed experimental studies using a set of descriptors and a set of symbols which are widely used by the community namely ART and SC descriptors and the GREC 2003 database.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Terrades, O.R., Tabbone, S., Valveny, E.: A review of shape descriptors for document analysis. In: Proceedings of the International Conference on Document Analysis and Recognition—ICDAR’07, pp. 227–231 (2007)

  2. Phillips I., Chhabra A.: Empirical performance evaluation of graphics recognition systems. IEEE Trans. PAMI 21(9), 849–870 (1999)

    Google Scholar 

  3. Chhabra, A., Phillips, I.: The second international graphics recognition contest—raster to vector conversion: A report. In: Tombre, K., Chhabra, A.K. (eds.) Graphics recognition: Algorithms and Systems. LNCS, vol. 1389, pp. 390–410. Springer (1998)

  4. Chhabra, A., Phillips, I.: Performance evaluation of line drawing recognition systems. In: Proceedings of 15th. International Conference on Pattern Recognition, vol. 4, pp. 864–869. Barcelona, Spain (2000)

  5. Wenyin, L., Zhai, J., Dori, D.: Extended summary of the arc segmentation contest. In: Blostein, D., Kwon, Y.B. (eds.) Graphics Recognition: Algorithms and Applications. LNCS, vol. 2390, pp. 343–349. Springer (2002)

  6. Valveny, E., Dosch, P.: Symbol recognition contest: a synthesis. In: Lladós, J., Kwon, Y.B. (eds.) Graphics Recognition Recent Advances and Perspectives. LNCS, vol. 3088, pp. 368–385, Springer (2004)

  7. Dosch, P., Valveny, E.: Report on the second symbol recognition contest. In: Liu, W., Lladós, J. (eds.) Graphics Recognition. Ten Years Review and Future Perspectives. LNCS, vol. 3926, pp. 381–397. Springer (2006)

  8. Trier O.D., Jain A.K., Taxt T.: Feature extraction methods for character recognition—a survey. Pattern Recognit. 29(4), 41–662 (1996)

    Google Scholar 

  9. da Fontoura Costa L., Cesar R.M. Jr: Shape Analysis and Classification: Theory and Practice, pp. 685. CRC Press, Boca Raton (2001)

    MATH  Google Scholar 

  10. Zhang D., Lu G.: Review of shape representation and description techniques. Pattern Recognit. 37, 1–19 (2004)

    Article  MATH  Google Scholar 

  11. Tumer K., Ghosh J.: Analysis of decision boundaries in linearly combined neural classifiers. Pattern Recognit. 29(2), 314–348 (1996)

    Article  Google Scholar 

  12. Freund, Y., Schapire, R.E.: Experiments with a new boosting algorithm. In: Proceedings of the Thirteenth International Conference on Machine Learning, pp. 148–156 (1996)

  13. Skurichina M., Duin R.P.W.: Bagging, boosting and the random subspace method for linear classifiers. Int. J. Pattern Anal. Appl. 5(2), 121–135 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  14. Burges C.J.C.: A tutorial on support vector machines for pattern recognition. Int. J. Data. Min. Knowl. Discov. 2(2), 1–43 (1998)

    Google Scholar 

  15. Kittler, J.: A framework for classifier fusion: is it still needed? In: Proceedings of the Joint IAPR International Workshops on Advances in Pattern Recognition, pp. 45–56. Springer-Verlag (2000)

  16. Ramos O., Valveny E., Tabbone S.: Optimal classifiers fusion in a non-Bayesian probabilistic framework. IEEE Tran. PAMI 31(9), 1630–1644 (2009)

    Google Scholar 

  17. Terrades, O.R., Valveny, E., Tabbone, S.: On the combination of ridgelets descriptors for symbol recognition. In: Liu, W., Lladós, J., Ogier, J.-M. (eds.) Graphics Recognition. Recent Advances and New Opportunities. LNCS, vol. 5046, pp. 40–50. Springer (2008)

  18. Valveny E., Dosch P., Winstanley A., Zhou Y., Yang S., Yan L., Wenyin L., Elliman D., Delalandre M., Trupin E., Adam S., Ogier J.M.: A general framework for the evaluation of symbol recognition methods. Int. J. Doc. Anal. Recognit. 9(1), 59–74 (2007)

    Article  Google Scholar 

  19. Delalandre, M., Pridmore, T., Valveny, E., Locteau, H., Trupin, E.: Building synthetic graphical documents for performance evaluation. In: Liu, W., Lladós, J., Ogier, J.-M. (eds.) Graphics Recognition. Recent Advances and New Opportunities. LNCS vol. 5046, pp. 288–298. Springer (2008)

  20. Valveny, E., Tabbone, S., Terrades, O.R., Philippot, E.: Performance characterization of shape descriptors for symbol representation. In: Liu, W., Lladós, J., Ogier, J.-M. (eds.) Graphics Recognition. Recent Advances and New Opportunities. LNCS vol. 5046, pp. 278–287. Springer (2008)

  21. Jouili, S., Tabbone, S.: Evaluation of graph matching measures for documents retrieval. In: Eighth IAPR International Workshop on Graphics Recognition (GREC 09), La Rochelle (2009)

  22. Kim, W.Y., Kim, Y.S.: A new region-based shape descriptor. ISO/IEC MPEG99/M5472 Maui, Hawaii (1999)

  23. Belongie S., Malik J., Puzicha J.: Shape matching and object recognition using shape contexts. IEEE Trans. PAMI 24(4), 509–522 (2002)

    Google Scholar 

  24. Mori G., Belongie S., Malik J.: Efficient shape matching using shape contexts. IEEE Trans. PAMI 27(11), 1832–1837 (2005)

    Google Scholar 

  25. Visani, M., Garcia, C., Laurent, C.: Comparing robustness of two-dimensional PCA and eigenfaces for face recognition. In: Proceedings of the International Conference on Image Analysis and Recognition (ICIAR 04) Springer LNCS 3212, 2:717–724. Porto, Portugal (2004)

  26. Doddington, G., Liggett, W., Martin, A., Przybocki, M., Reynolds, D.: Sheep, Goats, Lambs and Wolves: a statistical analysis of speaker performance in the NIST 1998 speaker recognition evaluation. In: International Conference on Spoken Language Processing (ICSLP), Sydney, USA (1998)

  27. Kanungo T., Haralick R.M., Phillips I.: Nonlinear global and local document degradation models. Int. J. Imaging Syst. Technol. 5, 220–230 (1994)

    Article  Google Scholar 

  28. Jouili, S., Tabbone, S.: Graph matching using node signatures. In: Proceedings of the 7th workshop on graph-based representations in pattern recognition—GbRPR 2009, pp. 154–163. Venice, Italy May (2009)

  29. Robles-Kelly A., Hancock E.R.: Graph edit distance from spectral seriation. IEEE Trans. PAMI 27(3), 365–378 (2005)

    Google Scholar 

  30. Papadopoulos, A.N., Manolopoulos, Y.: Structure-based similarity search with graph histograms. In: Proceedings of International Workshop on Similarity Search (DEXA IWOSS 99), pp. 174–178 Sep (1999)

Download references

Author information

Authors and Affiliations

  1. L3I, University of La Rochelle, La Rochelle Cedex 1, France

    Muriel Visani

  2. Instituto Tecnológico de Informática, Universidad Politécnica de Valencia, Valencia, Spain

    Oriol Ramos Terrades

  3. LORIA, University of Nancy 2, Vandoeuvre-les-Nancy, France

    Salvatore Tabbone

Authors
  1. Muriel Visani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Oriol Ramos Terrades
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Salvatore Tabbone
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Salvatore Tabbone.

Additional information

Work supported by the Juan de la Cierva programme and the MITTRAL project (TIN2009-14633-C03-01).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Visani, M., Terrades, O.R. & Tabbone, S. A protocol to characterize the descriptive power and the complementarity of shape descriptors. IJDAR 14, 87–100 (2011). https://doi.org/10.1007/s10032-010-0125-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10032-010-0125-5

Keywords

Search

Navigation