An Adaptative Method for the Smoothing of Curves Edge Detection Application
Une Méthode Adaptative pour le Lissage Decourbes Application à la Détection de Contours
OPEN ACCESS
We present a new approach to smooth discrete curves . The smoothing is realized by associating portions of regular curves which are defined on each points interval. The originality of the method consists in finding the portions of curves by minimizing the squared error over a restricted neighbourhood around each point . Adding continuityconstraints at the junction points, we obtain a direct formulation of the solution. A unique parameter allows to easily control the smoothing amplitude which can be selected between two extreme cases : interpolation or approximation. It seems like a drawer behaviour trying to join points by a curve. He can choose to join each point by a curve or only take into account the global form of the set of points.
The method is particularly adapted to fit contours defined on an image and is used as a final step of image segmentation process. The parameter controlling the smoothing amplitude is computed from the value oflocal gradient magnitude on each pixel.
Résumé
La méthode de lissage de courbes discrètes présentée est fondée sur la minimisationd'un critère d'erreur quadratique appliqué sur des portions jointives de la courbe à traiter. En imposant des contraintes géométriques au niveau des points de jonctions entre intervalles, on aboutit à une formulation directe de la solution. Un paramètreunique permet de façon simple de contrôler la force du lissage qui évolue ainsi entre 2 cas extrêmes :l'interpolation et l'approximation. La méthode simule le comportement d'un scripteur cherchant à unir des points par une courbe, il peut privilégier le passagedu tracé par chaque point ou au contraire respecter la forme globale définie par l'ensemble des points.
Cette méthode adaptative de lissage est utilisée comme étape finale d'un processus de segmentation d'images, le paramètre contrôlant la force du lissage étant défini à partir du gradient mesuré localement en chaque point .
Curve fitting, Approximation, Interpolation, Contour detection .
Mots clés
Lissage de courbes, Approximation, Interpolation, Détection de contours .
[BaP.821 F. Badii & B. Peikari, « Functional approximation of planar curves via adaptive segmentation >>, Int. J. Syst. Sci., Vol. 13, n°6, 1982, pp. 667-674.
[BBB.871 R. Bartels, J. Beatty & B. Barsky,An introduction to splines for use in computer graphics and geometric modelling, Morgan Kaufmann publishers, 1987.
[BoK.861 T. Boult & J. Kender, « Visual surface reconstruction using sparse depth data», Proc. IEEE Conf Comput. Vision and Pattern Recognit., 1986, pp. 6876.
[ChC.931 Mei-Hsing Chen & Roland T. Chin, « Partial Smoothing Splines for Noisy +Bondaries with corners », IEEE PAM!, Vol. 15, n°11, 1993, pp. 12081216.
[CrW.791 P. Craven & G. Wahba, « Smothing noisy data with spline functionsEstimating the correct degree of smothing by the method of generalized crossvalidation >>,Numerische Mathematik, n°31, 1979, pp. 377-403.
[Dav.79] L. S. Davis, « Shape matching using relaxation techniques », IEEE Trans. PAM1 Vol. 1, 1979, pp. 60-72.
[DPL.94] S. Djeziri, E. Petit et J. Lemoine, «Un algorithme de croissance de régions par déformation géométrique de contours », y°"P Congréa RFIAAFCET, Reconnaissance des Formeset IntelligenceArtificielle,Vol. 1, 1994, pp. 715-720.
[Don.91] R. Dony, Calcul des parties cachées : Approximation des courbespar la méthode de BEZIER et des B-splines,2ème édition Masson.
[DuH.73] R. O. Duda & P. E. Hart,Pattern classification and scene analysis, New York : Wiley, 1973, pp. 328-329.
[Dun.86] J. G. Dunham, « Optimum uniform piecewise linear approximation of planar curves », IEEE traps. PAM!, Vol. 8, n°1, 1986.
[FiB.86] M. A. Fischler & R. C. Bolles, « Perceptual Organization and Curve Partitioning >>, IEEE , PAMI, Vol. 8, n°l, 1986, pp. 100-105.
[FrD.77] H. Freeman & L. S. Davis, « A corner-finding algorithm for chain-coded curves», IEEE Trans. Comput., Vol. C-26, 1977, pp. 297-303.
[GuA.92] A. Guéziec & N. Vache, «Lissage et reconnaissance de courbes gauches bruitées », Traitement du Signal, Vol.9, n°6, 1992, pp. 473-490.
[Koh.81] R. R. Kohler, < A m,' menation based on thresholding >>, Computer Graphics and Image Processing, Vol. 15, 1981, pp. 319-338.
[KuD.82] Y. Kurozomi & W. A. Davis, « Polygonal approximation by the minmax method»,Comput. Graphics Image Processing, Vol. 19, 1982, pp. 248-264.
[LeP.88] D. Lee & T. Pavlidis, « One-dimensional regularization with discontinuities», IEEE PAMI. Vol. 10, n°6, 1988, pp. 822-829.
[MuS.85] D. Mumford & J. Shah, « Boundary detection by minimizing functionals >>, Proc. IEEE Conf . Comput. Vision and Pattern Recognit., 1985, PP. 22-26.
[PaH.74] T. Pavlidis & S. L. Horowitz, « Segmentation of planes curves », IEEE Trans. Comput., Vol. C-23, 1974, pp. 860-870.
[Ram.72] U. Ramer, « An iterative procedure for the polygonal approximation of planecurves», Comp. Graphics Image Processing, Vol. 1, 1972, pp. 244-256.
[RaR.91] Kr. B. Ray & Ku. S. Ray, « A new approch to polygonal approximation », Pattern Recognition Letters12, 1991, pp. 229-234.
[Rob.85] J. Roberge, « A data reduction algorithm for planar curves », Comput. Vision, Graphics, Image Processing, Vol. 29, 1985, pp. 168-195.
[RoJ.73] A.Rosenfeld&E. Johnston, « Angle detection on digital curves », IEEE Trans. Comput.,Vol. C-22, 1973, pp. 875-878.
[RoW.75] A.Rosenfeld& J.S. Weszka, « An improved method of angle detection on digital curves », IEEE Trans. Comput., Vol. C-24, 1975, pp. 940-941.
[SaS.78] P. V. Sankar & C. V. Sharma, « A parallel procedure for the detection of dominant points on a digital curve », Comput. Graphics Image Processing, Vol. 7, 1978, pp. 403-412.
[ShA.89] B. Sharayha & D. Anderson, « Optimal estimation of contour properties by cross-validated regularisation >>, IEEE PAM!, Vol. 11,n°6, 1989, pp. 600610.
[SIG.80] J. Slansky & V. Gonzalez, « Fast polygonal approximation of digitized curves », Pattern Recognition, Vol. 12, 1980, pp. 327-331.
[SMM.901 P. Saint-Marc & G. Mediani, « B-spline contour representation and symmetry detection », In First European Conference on Computer Vision (ECCV),Antibes 1990.
[Sto.74] M. Stone, « Cross-validatory choice and assessment of statistical prediction >>_I. Roy. Stat. Soc; Ser; B, Vol.36, n°2, 1974, pp. 11-147.
[TeC.89] Cho-Huak Teh & Roland T. Chin, « On the detection of dominant points on digital curves », IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 11, 1989, n°8, pp. 859-872.
[Tih.63] A. N. Tihonov, «Regularisation of incorrectly posed problems », Sov. Math. Dokl.,Vol . 4, 1963, pp. 1624-1627.
[WuW.93] Wen-Yen Wu & Mao-Jiun J. Wang, « Detecting the dominant points by the curvature based polygonal approximation », CVGIP: Graphical Models and Image Processing, Vol.55, n°2, 1993, pp. 79-88.