On Shape Recognition Thresholds
Sur les Seuils de Reconnaissance des Formes
OPEN ACCESS
A significant stake of shape query in databases of images is to define unsupervised thresholds making it possible to avoid a flood of false detections, or, on the contrary, rejections of shapes which should have been recognized. By taking as example a method of shape recognition introduced by Lisani [15, 16], we show that one can answer the following question: given a query shape and a database of images, below which distance between the query and a detected shape is one sure that the shape is recognized? This insurance is quantified by the number of false alarms associated with the pair query shape – candidate shape. Although this method only considers for the moment pieces of shape, it already leads to sure detections based on a single piece of shape.
Résumé
Un enjeu important de la recherche de formes dans une base d'images est la définition de seuils non supervisés permettant d'éviter une déferlante de fausses détections, ou, au contraire, des rejets de formes qui auraient dû être reconnues. En prenant comme exemple une méthode de reconnaissance de forme proposée par Lisani [15, 16], nous montrons que l'on peut répondre à la question suivante : étant donnée une forme requête et une base d'images, à partir de quelle distance entre la forme requête et une forme détectée est-on sûrs que la forme est reconnue ? Cette assurance est quantifiée par le nombre de fausses alarmes associé à la paire requête – forme candidate. Cette méthode ne considère pour l'instant que des morceaux de forme et permet pourtant déjà d'aboutir à des détections sûres basées sur un seul morceau de forme.
Invariant shape encoding, number of false alarms.
Mots clés
Codage invariant de forme, nombre de fausses alarmes.
[1] A. Almansa, A. Desolneux, S. Vamech, « Vanishing point detection without any a priori information » , IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 25, #4, 2003, p. 502-507.
[2] H. Alt, L. J. Guibas, « Discrete geometric shapes: Matching, interpolation, and approximation. A survey », Technical Report B 96-11, Universität Berlin, 1996.
[3] L. Alvarez, L. Mazorra, F. Santana, « Geometric invariant shape representations using morphological multiscale analysis adn applications to shape representation », Journal of Mathematical Imaging and Vision, Vol. 18, #2, 2002.
[4] D. H. Ballard, « Generalized Hough transfom to detect arbitrary patterns, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, #2, 1981, p. 111-122.
[5] F. Cao, « Good continuations in digital image level lines », To appear in Proceeding of ICCV 2003.
[6] C. Carson, S. Belongie, H. Greenspan, J. Malik, « Blobworld: Image segmentation using expecation-maximization and its application to image querying », In Third International Conference on Visual Information Systems, 1999.
[7] T. Cohignac, « Reconnaissance de formes planes », PhD thesis, Ceremade, Université Paris IX Dauphine, 1994.
[8] A. Desolneux, L. Moisan, J.-M. Morel, « Meaningful alignments », International Journal of Computer Vision, Vol. 40, #1, 2000, p. 7-23.
[9] A. Desolneux, L. Moisan, J.-M. Morel, « Edge detection by Helmholtz principle », Journal of Mathematical Imaging and Vision, Vol. 14, #3, 2001, p. 271-284.
[10] S.A. Dudani, K.J. Breeding, R.B. McGhee, « Aircraft identification by moment invariants », IEEE Transactions on Computers, Vol. 26, #1, 1977, p. 39-46.
[11] Y. Gdalyahu, D. Weinshall, « Flexible syntactic matching of curves and its application to automatic hierarchical classification of silhouettes », IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 21, #12, 1999, p. 1312-1328.
[12] W.E.L. Grimson, D.P. Huttenlocher, « On the verification of hypothesized matches in model-based recognition », IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, #12, 1991, p. 1201-1213.
[13] D.P. Huttenlocher, E.W. Jaquith, « Computing visual correspondence: incorporating the probability of a false match », In Proceedings of the Fifth International Conference on Computer Vision, 1995, p. 572-594.
[14] Y. Lamdan, H. J. Wolfson, « Geometric hashing: a general and efficient model-based recognition scheme », In 2nd International Conference on Computer Vision, 1988, p. 238-249.
[15] J.-L. Lisani, « Shape Based Automatic Images Comparison » , Thèse de doctorat, Université Paris 9 Dauphine, France, 2001.
[16] J.-L. Lisani, L. Moisan, J.-M. Morel, P. Monasse, « On the theory of planar shape », SIAM Multiscale Modeling and Simulation, Vol. 1, #1, 2003, p. 1-24.
[17] S. Loncarnic, « A survey of shape analysis techniques », Pattern Recognition, Vol. 31, #8, 1998, p. 983-1001.
[18] L. Moisan, « Affine plane curve evolution: A fully consistent scheme » , IEEE Transactions on Image Processing, Vol. 7, #3, 1998, p. 411-420.
[19] F. Mokhtarian, A. K. Mackworth, « A theory of multiscale, curvaturebased shape representation for planar curves », IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 14, #8, 1992, p. 789-805.
[20] P. Monasse, « Représentation morphologique d'images numériques et application au recalage », Thèse de doctorat, Université Paris 9 Dauphine, France, 2000.
[21] C. Olson, D.P. Huttenlocher, « Automatic target recognition by matching oriented edge pixels », IEEE Transactions on Image Processing, Vol. 6, #12, 1997, p.103-113.
[22] C.A. Rothwell, « Object Recognition Through Invariant Indexing », Oxford Science Publications, 1995.
[23] G. Sapiro, A. Tannenbaum, « Affine invariant scale-space », International Journal of Computer Vision, Vol. 11, #1, 1993, p. 25-44.
[24] C. Schmid, « A structured probabilistic model for recognition », In Proceedings of the Conference on Computer Vision and Pattern Recognition, Fort Collins, Colorado, USA, Vol. 2, 1999, p. 485-490.
[25] C. Schmid, R. Mohr, « Local greyvalue invariants for image retrievals », IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, #5, 1997, p. 530-535.
[26] C. G. Small, « The Statistical Theory of Shapes », Springer, 1996.
[27] C.V. Stewart, « MINPRAN: a new robust estimator for computer vision », IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, #10, 1995, p. 925-938.
[28] R. Veltkamp, M. Hagedoorn. « State-of-the-art in shape matching », Technical Report UU-CS-1999-27, Utrecht University, The Netherlands, 1999.
[29] R. C. Veltkamp, « Shape matching: similarity measures and algorithms », In Proceedings of Shape Modelling International, 2001, p. 188-197.
[30] A. Winter, C. Nastar, « Differential feature distribution maps for image segmentation and region queries in image databases », In CBAIVL Workshop at CVPR'99, Fort Collins, Colorado, USA, 1999.
[31] H. J. Wolfson, « Model-based object recognition », In 1st European Conference on Computer Vision, p. 526-536, Lecture Notes in Computer Vision 427, Springer, 1990.
[32] H. J. Wolfson, « On curve matching », IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, #5, 1990, p. 483-489.
[33] H. J. Wolfson, I. Rigoutsos, « Geometric hashing: an overview » , IEEE Computational Science & Engineering, October-December 1997, p. 1021.
[34] C.T. Zahn, R.Z. Roskies. « Fourier descriptors for plane closed curves », IEEE Transactions on Computers, Vol. C-21, #3, 1972, p. 269-281.