loading...
Optimal Local Weighted Averaging Methods in Contour Smoothing
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/34.608276August 1997 (vol. 19 no. 8) pp. 801-817
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Raymond Legault, Ching Y. Suen, "Optimal Local Weighted Averaging Methods in Contour Smoothing," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 8, pp. 801-817, August, 1997.
 
 
BibTex
x
 
@article{ 10.1109/34.608276,
author = {Raymond Legault and Ching Y. Suen},
title = {Optimal Local Weighted Averaging Methods in Contour Smoothing},
journal ={IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume = {19},
number = {8},
issn = {0162-8828},
year = {1997},
pages = {801-817},
doi = {http://doi.ieeecomputersociety.org/10.1109/34.608276},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - Optimal Local Weighted Averaging Methods in Contour Smoothing
IS - 8
SN - 0162-8828
SP801
EP817
EPD - 801-817
A1 - Raymond Legault,
A1 - Ching Y. Suen,
PY - 1997
KW - Contour smoothing; optimal local weighted averaging; digitization noise modeling; Gaussian smoothing.
VL - 19
JA - IEEE Transactions on Pattern Analysis and Machine Intelligence
ER -
 

Abstract—In several applications where binary contours are used to represent and classify patterns, smoothing must be performed to attenuate noise and quantization error. This is often implemented with local weighted averaging of contour point coordinates, because of the simplicity, low-cost and effectiveness of such methods. Invoking the "optimality" of the Gaussian filter, many authors will use Gaussian-derived weights. But generally these filters are not optimal, and there has been little theoretical investigation of local weighted averaging methods per se. This paper focuses on the direct derivation of optimal local weighted averaging methods tailored towards specific computational goals such as the accurate estimation of contour point positions, tangent slopes, or deviation angles. A new and simple digitization noise model is proposed to derive the best set of weights for different window sizes, for each computational task. Estimates of the fraction of the noise actually removed by these optimum weights are also obtained. Finally, the applicability of these findings for arbitrary curvature is verified, by numerically investigating equivalent problems for digital circles of various radii.

[1] 801 M. Worring and A.W.M. Smeulders, "Digitized Circular Arcs: Characterization and Parameter Estimation," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 6, pp. 587-598, 1995.
[2] D.-M. Tsai and M.-F. Chen, "Curve Fitting Approach for Tangent Angle and Curvature Measurements," Pattern Recognition, vol. 27, no. 5, pp. 699-711, 1994.
[3] H. Freeman, "On the Encoding of Arbitrary Geometric Configurations," IRE Trans. Electron. Comput., vol. 10, pp. 260-268, 1961.
[4] T. Sakai, M. Nagao, and H. Matsushima, "Extraction of Invariant Picture Sub-Structures by Computer," Comp. Graphics and Image Proc., vol. 1, no. 1, pp. 81-96, 1972.
[5] M.J. Eccles, M.P.C. McQueen, and D. Rosen, "Analysis of the Digitized Boundaries of Planar Objects," Pattern Recognition, vol. 9, pp. 31-42, 1977.
[6] H. Freeman, "On the Digital Computer Classification of Geometric Line Patterns," Proc. Nat'l Electronics Conf., vol. 18, pp. 312-324, 1962.
[7] G. Gallus and P.W. Neurath, "Improved Computer Chromosome Analysis Incorporating Preprocessing and Boundary Analysis," Physics in Medicine and Biology, vol. 15, no. 3, pp. 435-445, 1970.
[8] J.W. McKee and J.K. Aggarwal, "Computer Recognition of Partial Views of Curved Objects," IEEE Trans. Computers, vol. 26, pp. 790-800, 1977.
[9] N.I. Badler and C. Dane, "The Medial Axis of a Coarse Binary Image Using Boundary Smoothing," Proc. IEEE Conf. Pattern Recognition and Image Processing, pp. 286-291, 1979.
[10] P. Kammenos, "Performances of Polar Coding for Visual Localisation of Planar Objects," Proc. Eighth Int'l Symp. Industrial Robots,Stuttgart, Germany, pp. 143-149, 1978.
[11] J.D. Dessimoz, "Curve Smoothing for Improved Feature Extraction From Digitized Pictures," Signal Processing, vol. 1, pp. 205-210, 1979.
[12] T.J. Ellis, D. Proffitt, D. Rosen, and W. Rutkowski, "Measurements of the Lengths of Digitized Curved Lines," Comp. Vision, Graphics and Image Proc., vol. 10, pp. 333-347, 1979.
[13] A.R. Dill, M.D. Levine, and P.B. Noble, "Multiple Resolution Skeletons," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 9, no. 4, pp. 495-503, 1987.
[14] N. Ansari and K.-W. Huang, "Non-Parametric Dominant Point Detection," Pattern Recognition, vol. 24, no. 9, pp. 849-862, 1991.
[15] C.H. Teh and R.T. Chin, “On the Detection of Dominant Points on Digital Curves,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, pp. 859-872, 1989.
[16] S.-C. Pei and J.-H. Horng, "Fitting Digital Curve Using Circular Arcs," Pattern Recognition, vol. 28, no. 1, pp. 107-116, 1995.
[17] A. Witkin, "Scale-Space Filtering," Proc. Int'l Joint Conf. AI, pp. 1,019-1,022, 1983.
[18] J.J. Koenderink, "The Structure of Images," Biological Cybernetics, vol. 50, pp. 363-370, 1984.
[19] H. Asada and M. Brady, "The Curvature Primal Sketch," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 1, pp. 2-14, 1986.
[20] F. Mokhtarian and A. Mackworth, "Scale-Based Description and Recognition of Planar Curves and Two-Dimensional Shapes," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 1, pp. 34-43, 1986.
[21] D.M. Wuescher and K.L. Boyer,“Robust contour decomposition using a constant curvature criterion,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 1, pp. 41-51, 1991.
[22] P. Saint-Marc, J. Chen, and G. Medioni, "Adaptive Smoothing: A General Tool for Early Vision," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, 1991.
[23] P. Maragos, "Pattern Spectrum and Multiscale Shape Representation," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, pp. 701-716, 1989.
[24] M. Chen and P. Yan,“A multiscaling approach based on morphological filtering,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 11, no. 7, pp. 694-700, July 1989.
[25] J.A. Bangham, P. Ling, and R. Harvey, “Scale-Space from Nonlinear Filters,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 5, pp. 520-528, May 1996.
[26] C.M. Reinsch, "Smoothing by Spline Functions," Numerische Mathematik, vol. 10, pp. 177-183, 1967.
[27] I.J. Schoenberg, "Spline Functions and the Problem of Graduation," Proc. Nat'l Academy of Science, vol. 52, pp. 947-950, 1964.
[28] T. Poggio, H. Voorhees, and A. Yuille, "A Regularized Solution to Edge Detection," Tech. Rep., MIT AI Laboratory, AI Memo 776, 1985.
[29] J.F. Canny, "A Computational Approach to Edge Detection," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679-698, 1986.
[30] J. Babaud, A.P. Witkin, M. Baudin, and R.O. Duda, "Uniqueness of the Gaussian Kernel for Scale-Space Filtering," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 1, pp. 26-33, 1986.
[31] A.L. Yuille and T.A. Poggio, "Scaling Theorems for Zero Crossings," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 1, pp. 15-25, 1986.
[32] A.K. Mackworth and F. Mokhtarian, "The Renormalized Curvature Scale Space and the Evolution Properties of Planar Curves," Proc. Comp. Vision and Pattern Recognition, pp. 318-326,Ann Arbor, Mich., June 1988.
[33] L. Wu and Z. Xie, "Scaling Theorems for Zero-Crossings," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, pp. 46-54, Jan. 1991.
[34] V. Anh, J.Y. Shi, and H.T. Tsui, "Scaling Theorems for Zero Crossings of Bandlimited Signals," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 3, pp. 309-320, Mar. 1996.
[35] T. Lindeberg,“Scale-space for discrete signals,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 3, pp. 234–254, 1990.
[36] E.J. Pauwels, L.J. Van Gool, P. Fiddelaers, and T. Moons, "An Extended Class of Scale-Invariant and Recursive Scale Space Filters," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 7, pp. 691-701, 1995.
[37] J.A. Bangham, P. Chardaire, C.J. Pye, and P.D. Ling, “Mulitscale Nonlinear Decomposition: The Sieve Decomposition Theorem,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 5, pp. 529-539, May 1996.
[38] B. Shahraray and D. Anderson, "Optimal estimation of contour properties by cross-validated regularization," IEEE Trans. Pattern Anal. Machine Intell., vol. 11, no. 6, pp. 600-610, June 1989.
[39] B. Shaharay and D.J. Anderson, "Optimal Smoothing of Digitized Contours," Proc. Comp. Vision and Pattern Recognition, pp. 210-218,Miami Beach, Fla., June 1986.
[40] D. Lee and T. Pavlidis,“One-dimensional regularization with discontinuities,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 10, pp. 822-829, 1986.
[41] M.-H. Chen and R.T. Chin, "Partial Smoothing Splines for Noisy Boundaries With Corners," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 11, pp. 1,208-1,216, 1993.
[42] M. Brady, J. Ponce, A. Yuille, and H. Asada, "Describing Surfaces," Comp. Vision, Graphics and Image Proc., vol. 32, pp. 1-28, 1985.
[43] B.K.P. Horn and E.J. Weldon, Jr., "Filtering Closed Curves," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8, no. 5, pp. 665-668, 1986.
[44] D.G. Lowe, "Organization of Smooth Image Curves at Multiple Scales," Int'l J. Computer Vision, vol. 3, pp. 119-130, 1989.
[45] J. Oliensis, "Local reproducible smoothing without shrinkage," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 3, pp. 307-312, Mar. 1993.
[46] M.D. Wheeler and K. Ikeuchi, "Iterative Smoothed Residuals: A Low-Pass Filter for Smoothing With Controlled Shrinkage," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 3, pp. 334-337, 1996.
[47] X. Li and T. Chen, "Optimal L1 Approximation of the Gaussian Kernel With Application to Scale-Space Construction," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 10, pp. 1,015-1,019, 1995.
[48] T. Kasvand and N. Otsu, "Regularization of Digitized Plane Curves for Shape Analysis and Recognition," Proc. SPIE Conf. Architecture and Algorithms for Digital Image Processing, pp. 44-52,San Diego, Calif., Aug. 1983.
[49] R. Legault and C.Y. Suen, "Refining Curvature Feature Extraction to Improve Handwriting Recognition," Proc. Third Int'l Workshop Frontiers in Handwriting Recognition, pp. 31-40,Buffalo, N.Y., May 1993.
[50] B. Blesser, "Multistage Digital Filtering Utilizing Several Criteria," U.S. Patent 4-375-081, Feb. 1983.
[51] C.Y. Suen, C. Nadal, R. Legault, T.A. Mai, and L. Lam, "Computer Recognition of Unconstrained Handwritten Numerals," Proc. IEEE, Special Issue on Optical Character Recognition, vol. 80, no. 7, pp. 1,162-1,180, July 1992.
[52] C.C. Tappert, "Speed, Accuracy, Flexibility Trade-Offs in On-Line Character Recognition," IBM Research Report RC13228 (#59158), T.J. Watson Research Center, Yorktown Heights, N.Y., 1987.
[53] A.E. Taylor and W.R. Mann, Advanced Calculus.New York: John Wiley&Sons, 1983.
[54] Z. Kulpa, "On the Properties of Discrete Circles, Rings, and Disks," Comp. Graphics and Image Proc., vol. 10, pp. 348-365, 1979.
[55] B.K.P. Horn, "Circle Generators for Display Devices," Comp. Graphics and Image Proc., vol. 5, pp. 280-288, 1976.
[56] Z. Kulpa, "A Note on the Paper by B.K.P. Horn: Circle Generators for Display Devices," Comp. Graphics and Image Proc., vol. 9, pp. 102-103, 1979.
[57] M. Doros, "Algorithms for Generation of Discrete Circles, Rings, and Disks," Comp. Graphics and Image Proc., vol. 10, pp. 366-371, 1979.

Index Terms:
Contour smoothing; optimal local weighted averaging; digitization noise modeling; Gaussian smoothing.
Citation:
Raymond Legault, Ching Y. Suen, "Optimal Local Weighted Averaging Methods in Contour Smoothing," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 8, pp. 801-817, Aug. 1997, doi:10.1109/34.608276
Usage of this product signifies your acceptance of the Terms of Use.