Propagation de l’incertitude dimensionnelle dans le problème de l’ajustement d’ellipses. Application à la reconnaissance automatique de formes elliptiques dans les images

Propagation de l’incertitude dimensionnelle dans le problème de l’ajustement d’ellipses. Application à la reconnaissance automatique de formes elliptiques dans les images

Propagating the dimensional uncertainty in ellipse fitting. Application to the automatic detection of elliptic shapes in images

F. Dufrenois

Université du littoral côte d’opale Laboratoire d’analyse des systèmes du Littoral 50, rue Ferdinand Buisson B.P. 699 – 62228 Calais cedex – FRANCE

Page: 
119-138
|
Received: 
30 June 2000
|
Accepted: 
N/A
|
Published: 
30 June 2002
| Citation

OPEN ACCESS

Abstract: 

The conic fitting from image points is a very old topic in estimation and pattern recognition. This problem gave rise to a lot of studies and arouses interests still today. Systematically, these works have been based on the algebraic representation of the conic to establish the optimization criteria. Less studied, the polar representation of the ellipse is costlier because it needs the optimization of the parametrization. Yet, we propose in this paper some new ideas about this question. First, we show that the estimation of the parameters and the parametrization separated permit to make the problem easier leading to a direct inversion and the search of the roots of a four degree polynomial respectively. We also show that the parametrization carries the dimensional characteristics of the ellipse and when it is correctly disrupted in the minimization process, we constraint the ellipse search space. This new result gives an estimate without dimensional bias in a noised and incomplete context. A confidence envelope is then estimated to direct the search for continuations of the ellipse. At last, we propose a hierarchical grouping and fitting stage following with a fuzzy decision step to detect automatically the elliptic shapes in the images.

Résumé

L’ajustement d’une ellipse sur des données 2D est un très vieux sujet en estimation et en RDF, qui a donné lieu à de nombreuses études [2,6,10,15,16,21] et en suscite encore aujourd’hui [12,17,19,24]. D’une façon systématique, ces travaux se sont appuyés sur la représentation algébrique de la conique pour établir leur critère de minimisation. Un peu moins étudiée [5], la représentation polaire de l’ellipse constitue une alternative plus coûteuse car elle nécessite l’optimisation de sa paramétrisation. D’une représentation nécessitant au plus 5 paramètres à une autre définie par 5 + N (N étant le nombre de données), le choix semble évident. Cependant, nous proposons dans cet article de nouvelles idées sur la question. Tout d’abord, nous montrons que l’estimation séparée des paramètres et de la paramétrisation de l’ellipse permet de simplifier le problème en aboutissant respectivement à une inversion directe pour les premiers et à la recherche des racines d’un polynôme du 4ième ordre pour la seconde. Nous montrons également que la paramétrisation est « porteuse » de l’information dimensionnelle de l’ellipse et qu’en la « perturbant » correctement dans le processus de minimisation il est possible de forcer la solution à rester dans un espace paramétrique préétabli. Ce résultat nouveau permet de fournir une solution sans biais dimensionnel même dans un contexte fortement bruité et incomplet. Une enveloppe de confiance est ensuite estimée assurant à la fois un encadrement plus large de la solution et le rôle de filtre pour la recherche des segments voisins candidats potentiels pour affiner l’estimation. Enfin, nous proposons une stratégie de regroupement/ajustement suivie d’une phase de décision floue constituant ainsi un schéma robuste de détection de formes elliptiques dans les images.

Keywords: 

Least square fitting, parametrization, dimensional incertainty, fuzzy decision, ellipse detection

Mots clés

Moindres carrés, paramétrisation, incertitude dimensionnelle, décision floue, détection d’ellipses

1. État De L’art
2. Ajustement Basé Sur La Représentation Polaire De L’ellipse
3. Schéma D’extraction
4. Résultats
5. Conclusion
  References

[1] P. L. Rosin, Ellipse fitting using orthogonal hyperbolae and stirling’s oval. Graphical Models and Image Processing., 60(3) : pp. 209-213, 1998.

[2] P. D. Sampson, Fitting conic sections to ’very scattered’ data: An iterative refinement of the bookstein algorithm. Computer Graphics and Image Processing, 18(1) : pp. 97-108, 1982.

[3] R. Saffe-Rad, I Tchoukanov, B. Benhabib, Accurate parameter estimation of quadratic curves from grey level images. Computer Vision, Graphics and Image Processing: image Understanding, 54 : pp. 259-274, 1991.

[4] G. Taubin, Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations to edge and range image segmentation. IEEE Transaction on Pattern Analysis and Machine Intelligence., 13(11): pp. 1115-1138, 1991.

[5] W. Gander, G.H. Golud, and R. Strebel, Least squares fitting of circles and ellipses. BIT, 34 : pp. 558-578, 1994.

[6] F. Bookstein. Fitting conic sections to scattered data. Computer Vision, Graphics and Image Processing., 9 : pp. 56-71, 1979.

[7] P. L. Rosin. Analysing error of fit functions for ellipses. Pattern Recognition Letters, 17 : pp. 1461-1470, 1996.

[8] Z. Zhang. Parameter estimation techniques: a tutorial with application to conic fitting. Image and Vision Computing, 15(1): pp. 57-76, 1997.

[9] A. W. Fitzgibbon and R.B. Fisher. A buyer’s guide to conic fitting. Proc. Sixth British Machine Vision Conf., D. Pycock ed., 2 : pp. 513-522, 1995.

[10] S. S. Rao. Optimization: Theory and applications. Wiley Eastern, 2 edition., 1984.

[11] P. L. Rosin. A note on the least square fitting of ellipses. Pattern Recognition Letters., 14 : pp. 799-808, 1993.

[12] P. L. Rosin and G.A.W. West. Segmenting curves into elliptic arc and straight lines. Third Int’l Conf. Computer Vision, Japan, pp. 75-78, 1990.

[13] H. Bendtsen and I. Wright. Fitting ellipses to noisy spatial data. Technical report, Dept. of Mathematics and Statistics, Curtin University, 1992.

[14] A. W. Fitzgibbon, M. Pilu, and R.B. Fisher. Direct least squares fitting of ellipses. IEEE Transaction on Pattern Analysis and Machine Intelligence, 21(5): pp. 476-480, 1999.

[15] R. Halir and J. Flusser. Numerically stable direct least squares fitting of ellipses. Proceedings of the 6th International Conference in Central Europe on Computer Graphics and Visualisation, WSG’98, pp. 103-108, 1998.

[16] J. Porill. Fitting ellipses and predicting confidence envelopes using bias corrected kalman filter. Image and Vision Computing, 8(1): pp. 37-41, 1990.

[17] T. Ellis, A. Abbood, and B. Billault. Ellipse detection and matching with uncertainty. Image and Vision Computing, 10(5): pp. 271-276, 1992.

[18] K. Kanatani. Renormalisation for unbiased estimation. In Proc. 4th Int’l Conf. Comput. Vision (Berlin), pp. 599-606, 1993.

[19] W. Chojnacki, M. Brooks, and A. Van den Hengel. On the fitting of surfaces to data with covariances. IEEE Transaction on Pattern Analysis and Machine Intelligence., 22(11): pp. 1294-1303, 2000.

[20] J. Cabrera and P. Meer, Unbiased estimation of ellipses by bootstrapping. IEEE Transaction on Pattern Analysis and Machine Intelligence, 18(7): pp. 752-756, 1996.

[21] C. Daul, P. Graebling, and Ernest Hirsch. From the hough transform to a new approach for the detection and approximation of elliptical arcs. Computer Vision and Image Understanding, 72(3) : pp. 215-236, 1998.

[22] R. N. Dave and K. Bhaswan. Adaptive fuzzy c-shells clustering and detection of ellipses. IEEE Transactions on Neural Networks, 3(5) : pp. 643-662, 1992.

[23] R. Krishnapuram and J. Keller. A possibilistic approach to clustering. IEEE Transactions on Fuzzy Systems., 1(2) : pp. 98-110, 1993.

[24] I. Gath and D. Hoory. Fuzzy clustering of elliptic ring-shaped clusters. Pattern recognition letters, 16(3) : pp. 727-741, 1995.

[25] E. Lutton and P. Martinez. A genetic algorithm for the detection of 2d geometric primitives in images. Rapport INRIA, (2110), 1993.

[26] P. Y. Yin. A new circle/ellipse detector using genetic algorithms. Pattern recognition letters, 20 : pp. 731-740, 1999.

[27] P. J. Rousseeuw and A.M. Leroy. Robust regression and outlier detection. John Wiley and Sons, New-york, 1987.

[28] M. Li. Minimum description length based 2d shape description. 4th. Proc. International Conference on Computer Vision, pp. 512-517, 1993.

[29] R. Deriche. Fast algorithms for low-level vision. IEEE Transaction on Pattern Analysis and Machine Intelligence, 1(12): pp. 78-88, 1990.

[30] K. Sohn, W.E. Alexander, J.H. Kim, and W.E. Snyder. A constrained regularization approach to robust corner detection. IEEE Transaction on Pattern Analysis and Machine Intelligence, 24(5): pp. 820-828, 1994.

[31] D. M. Wuescher and K.l. Boyer. Robust contour decomposition using a constant curvature criterion. IEEE Transaction on Pattern Analysis and Machine Intelligence, 13(1): pp. 41-51, 1991.