Skip to main content
SpringerLink
Log in

A Unified Framework for Detecting Groups and Application to Shape Recognition

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

A unified a contrario detection method is proposed to solve three classical problems in clustering analysis. The first one is to evaluate the validity of a cluster candidate. The second problem is that meaningful clusters can contain or be contained in other meaningful clusters. A rule is needed to define locally optimal clusters by inclusion. The third problem is the definition of a correct merging rule between meaningful clusters, permitting to decide whether they should stay separate or unite. The motivation of this theory is shape recognition. Matching algorithms usually compute correspondences between more or less local features (called shape elements) between images to be compared. Each pair of matching shape elements leads to a unique transformation (similarity or affine map.) The present theory is used to group these shape elements into shapes by detecting clusters in the transformation space.

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. D.H. Ballard, “Generalizing the Hough transform to detect arbitrary shapes,” Pattern Recognition, Vol. 13, No. 2, pp. 111–122, 1981.

    Article  MATH  Google Scholar 

  2. H.H. Bock, “On some significance tests in cluster analysis,” Journal of Classification, Vol. 2, pp. 77–108, 1985.

    Article  MATH  MathSciNet  Google Scholar 

  3. F. Cao, P. Musé, and F. Sur, “Extracting meaningful curves from images,” Journal of Mathematical Imaging and Vision, Vol. 22, No. 2–3, pp. 159–181, 2005.

    Article  MathSciNet  Google Scholar 

  4. A. Desolneux, L. Moisan, and J.-M. Morel, “Meaningful alignments,” International Journal of Computer Vision, Vol. 40, No. 1, pp. 7–23, 2000.

    Article  MATH  Google Scholar 

  5. A. Desolneux, L. Moisan, and J.-M. Morel, “Edge detection by Helmholtz principle,” Journal of Mathematical Imaging and Vision, Vol. 14, No. 3, pp. 271–284, 2001.

    Article  MATH  Google Scholar 

  6. A. Desolneux, L. Moisan, and J.-M. Morel, “A grouping principle and four applications,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 25, No. 4, pp. 508–513, 2003.

    Article  Google Scholar 

  7. P.A. Devijver, and J. Kittler, Pattern Recognition—A Statistical Approach, Prentice Hall, 1982.

  8. R.C. Dubes, “How many clusters are best?—an experiment,” Pattern Recognition, Vol. 20, No. 6, pp. 645–663, 1987.

    Article  Google Scholar 

  9. R.O. Duda, and P.E. Hart, Pattern Classification and Scene Analysis, John Wiley and Sons, 1973.

  10. G.H. Golub, and C.F. Van Loan, Matrix Computations, Johns Hopkins University Press, 1989.

  11. A.D. Gordon, “Null models in cluster validation,” in From Data to Knowledge: Theoretical and Practical Aspects of Classification, Data Analysis, and Knowledge Organization, W. Gaul and D. Pfeifer (Eds.), Springer Verlag, 1996, pp. 32–44.

  12. A.D. Gordon, Classification. Monographs on Statistics and Applied Probability 82, Chapman & Hall, 1999.

  13. W.E.L. Grimson and D.P. Huttenlocher, “On the sensitivity of the Hough transform for object recognition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 3, pp. 255–274, 1990.

    Article  Google Scholar 

  14. W.E.L. Grimson and D.P. Huttenlocher, “On the verification of hypothesized matches in model-based recognition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, No. 12, pp. 1201–1213, 1991.

    Article  Google Scholar 

  15. D.P. Huttenlocher, and S. Ullman, “Object recognition using alignment,” In International Conference of Computer Vision, London, UK, 1987, pp. 267–291.

  16. A.K. Jain, M.N. Murty, and P.J. Flynn, “Data clustering: A review,” ACM Computing Surveys, Vol. 31, No. 3, pp. 264–323, 1999.

    Article  Google Scholar 

  17. A.K. Jain and R.C. Dubes, Algorithms for Clustering Data, Advanced Reference Series, Prentice-Hall, 1988.

  18. A.K. Jain, R.P.W. Duin, and M. Jiachang, “Statistical pattern recognition: A review,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 22, No. 1, pp. 4–36, 2000.

    Article  Google Scholar 

  19. K. Joag-Dev and F. Proschan, “Negative association of random variables, with applications,” Annals of Statistics, Vol. 11, No. 1, pp. 286–295, 1983.

    MathSciNet  Google Scholar 

  20. L. Kaufman and P. J. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley and Sons, 1990.

  21. Y. Lamdan, and H.J. Wolfson, “Geometric hashing: a general and efficient model-based recognition scheme,” in Proceedings of IEEE International Conference on Computer Vision, Tampa, Florida, USA, 1988, pp. 238–249.

  22. J.L. Lisani, Shape Based Automatic Images Comparison. PhD thesis, Université Paris 9 Dauphine, France, 2001.

  23. J.L. Lisani, L. Moisan, P. Monasse, and J.-M. Morel, “On the theory of planar shape,” SIAM Multiscale Modeling and Simulation, Vol. 1, No. 1, pp. 1–24, 2003.

    Article  MATH  MathSciNet  Google Scholar 

  24. D. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, Vol. 60, No. 2, pp. 91–110, 2004.

    Article  Google Scholar 

  25. D.G. Lowe, Perceptual Organization and Visual Recognition, Kluwer Academic Publisher, 1985.

  26. D. Marr, Vision, Freeman Publishers, 1982.

  27. G. Medioni, M. Lee, and C. Tang, A Computational Framework for Segmentation and Grouping, Elsevier, 2000.

  28. G.W. Milligan, and M.C. Cooper, “An examination of procedures for determining the number of clusters in a data set,” Psychometrika, Vol. 50, No. 2, pp. 159–179, 1985.

    Article  Google Scholar 

  29. P. Monasse, and F. Guichard, “Fast computation of a contrast invariant image representation,” IEEE Transactions on Image Processing, Vol. 9, No. 5, pp. 860–872, 2000.

    Article  Google Scholar 

  30. P. Musé, F. Sur, F. Cao, Y. Gousseau, and J.M. Morel, “An a contrario decision method for shape elements recognition,” International Journal of Computer Vision, Vol. 69, No. 3, pp. 295–315, 2006.

    Article  Google Scholar 

  31. X. Pennec, “Toward a generic framework for recognition based on uncertain geometric features,” Videre: Journal of Computer Vision Research, Vol. 1, No. 2, pp. 58–87, 1998.

    Google Scholar 

  32. C. Schmid, and R. Mohr, “Local greyvalue invariants for image retrieval,” IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. 19, No. 5, pp. 530–535, 1997.

    Article  Google Scholar 

  33. G. Stockman, S. Kopstein, and S. Benett, “Matching images to models for registration and object detection via clustering,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 4, No. 3, pp. 229–241, 1982.

    Article  Google Scholar 

  34. P.N. Tan, M. Steinbach, and V. Kumar, Introduction to Data Mining, Addison-Wesley, 2005.

  35. T. Veit, F. Cao, and P. Bouthemy, “A grouping algorithm for early motion detection and the analysis of visual motion,” Technical report, 2005, INRIA.

  36. M. Wertheimer, “Untersuchungen zur Lehre der Gestalt, II,” Psychologische Forschung, Vol. 4, pp. 301–350, 1923. Translation published as Laws of Organization in Perceptual Forms, in Ellis, W. (1938). A source book of Gestalt psychology (pp. 71–88). Routledge & Kegan Paul.

    Article  Google Scholar 

  37. H.J. Wolfson and I. Rigoutsos, “Geometric hashing: an overview,” IEEE Computational Science & Engineering, Vol. 4, No. 4, pp. 10–21, 1997.

    Article  Google Scholar 

  38. A.L. Yuille, and N.M. Grzywacz, “A theoretical framework for visual motion,” in High-Level Motion Processing Watanabe, T. (Eds.), MIT Press, 1998.

Download references

Author information

Authors and Affiliations

  1. IRISA/INRIA, France

    Frédéric Cao

  2. LTCI, Télécom Paris (CNRS UMR 5141), 46, rue Barrault, F-75634, Paris cedex 13, France

    Julie Delon

  3. MAP5/CNRS, France

    Agnès Desolneux

  4. CMLA, ENS-Cachan, France

    Pablo Musé

  5. Loria, Bâtiment C - projet Magrit, Campus Scientifique - BP 239, 54506, Vandoeuvre-lès-Nancy cedex, France

    Frédéric Sur

Authors
  1. Frédéric Cao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Julie Delon
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Agnès Desolneux
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Pablo Musé
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Frédéric Sur
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Frédéric Cao.

Additional information

Frédéric Cao graduated from the Ecole Polytechnique in 1995 and obtained a PhD in applied mathematics in Ecole Normale Supérieure de Cachan in 2000. He defended his “Habilitation à diriger des recherches" in 2004. His research interests include partial differential equations for image and shape filtering, but also statistical approaches to shape recognition and data analysis, or motion analysis.

Julie Delon was born in France in 1978. During the period 1997–2001, she has studied applied mathematics at the Ecole Normale Supérieure de Cachan. From 2001 to 2004, she prepared a Ph.D. thesis in image analysis at the CMLA (Cachan, France), and defended it in December 2004. She is currently a research scientist with CNRS at Télécom Paris.

Agnès Desolneux was born in France in 1974. She defended her PhD thesis in applied mathematics in 2000 under the direction of Jean-Michel Morel at the ENS Cachan. She is currently CNRS researcher at the MAP5, University Paris 5. She is working on statistical methods in image analysis. Web page: http://www.math-info.univ-paris5.fr/~desolneux/

Pablo Musé was born in Montevideo, Uruguay, in 1975. He received the Electrical Engineer degree from the Universidad de la República, Uruguay, in 1999, and the DEA in Mathematics, Vision and Learning from the Ecole Normale Supérieure de Cachan, France, in 2001. In 2004 he obtained his Ph.D. in Applied Mathematics, also from ENS Cachan, where he had a researcher position until May 2005. Since then he has been with Cognitech Inc., Pasadena, CA, USA.

Frédéric Sur was born in 1976. He is a former student of École Normale Supérieure de Cachan, France. In 2004, he received his PhD degree in applied mathematics and image analysis from Université Paris Dauphine. He is now an assistant professor at École des Mines de Nancy (France) and with Loria laboratory.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cao, F., Delon, J., Desolneux, A. et al. A Unified Framework for Detecting Groups and Application to Shape Recognition. J Math Imaging Vis 27, 91–119 (2007). https://doi.org/10.1007/s10851-006-9176-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-006-9176-0

Keywords

Search

Navigation