Discrete Polynomial Moments and Savitzky-Golay Smoothing

This paper presents unified theory for local (Savitzky- Golay) and global polynomial smoothing. The algebraic framework can represent any polynomial approximation and is seamless from low degree local, to high degree global approximations. The representation of the smoothing operator as a projection onto orthonormal basis functions enables the computation of: the covariance matrix for noise propagation through the filter; the noise gain and; the frequency response of the polynomial filters. A virtually perfect Gram polynomial basis is synthesized, whereby polynomials of degree d = 1000 can be synthesized without significant errors. The perfect basis ensures that the filters are strictly polynomial preserving. Given n points and a support length ls = 2m + 1 then the smoothing operator is strictly linear phase for the points xi, i = m+1. . . n-m. The method is demonstrated on geometric surfaces data lying on an invariant 2D lattice.

Authors:

• Paul O'Leary
• Matthew Harker

Keywords:

• Gram polynomials
• Savitzky-Golay Smoothing
• Discrete Polynomial Moments

References:

[1] M.-K. Hu, "Visual pattern recognition by moment invariants," IRE
Transactions on Information Theory, pp. 179-187, 1962.
[2] A. Savitzky and M. Golay, "Smoothing and differentiation of data by
simplified least squares procedures," Analytical Chemistry, vol. 36 (8),
p. 1627..1639, 1964.
[3] M. Eden, M. Unser, and R. Leonardi, "Polynomial representation of
pictures," Signal Processing, vol. 10, pp. 385-393, 1986.
[4] G. Yang, H. Shu, G. C. Han, and L. Luo, "Efficient Legendre moment
computation for grey level images," Pattern Recognition, vol. 39, pp.
74-80, 2006.
[5] P.-T. Yap and P. Raveendren, "Image analysis by Krawtchouk moments,"
IEEE Transactions on Image Processing, vol. 12, no. 11, pp. 1367-1377,
2003.
[6] ÔÇöÔÇö, "An efficient method for the computation of Legendre moments,"
IEEE Transactions on Pattern Analysis and Maschine Intelligence,
vol. 27, no. 12, pp. 1996-2002, 2005.
[7] K. Hosny, "Exact Legendre moment computation for gray level images,"
Pattern Recognition, vol. doi:10.1016/j.patcog.2007.04.014, 2007.
[8] R. Mukundan, S. Ong, and P. Lee, "Image analysis by Tchebichef
moments," IEEE Transactions on Image Processing, vol. 10, no. 9, pp.
1357-1363, 2001.
[9] H. Zhu, H. Shu, J. Liang, L. Luo, and J.-L. Coatrieus, "Image analysis
by discrete orthogonal Racah moments," Signal Processing, vol. 87, pp.
687-708, 2007.
[10] H. Zhu, H. Shu, J. Zhou, L. Luo, and J.-L. Coatrieus, "Image analysis
by discrete orthogonal Racah moments," Pattern Recongition Letters,
vol. doi:10.1016/j.patrec.2007.04.013, 2007.
[11] R. Mukundan, "Some computational aspects of discrete orthogonal
moments," IEEE Transactions on Image Processing, vol. 13, no. 8, pp.
1055-1059, 2004.
[12] P. O-Leary and M. Harker, "An algebraic framework for discrete basis
functions in computer vision," in IEEE Indian Conference on Computer
Vision, Graphics and Image Processing, Bhubaneswar, Dec, 2008.
[13] P. O-Leary, B. M¨ortl, and M. Harker, "Discrete polynomial moments
and the extraction of 3d embossed digits for recognition," Submitted to
Journal of Electronic Imaging, 2009.
[14] H. Madden, "Comments on the Savitzky-Golay convolution method for
least-squares-fit smoothing and differentiation of digital data," Analytical
Chemistry, vol. 50 (9), p. 13831386, 1978.
[15] S. Rajagopalan and R. Robb, "Image smoothing with Savitzky-Golay
filters," in Medical Imaging 2003: Visualization, Image-Guided Procedures,
and Display, vol. Vol. 5029, May 2003, 2003, p. 773..781.
[16] P. Meer and I. Weiss, "Smoothed differentiation filters for images," in
IEEE I10th International Conference on Pattern Recognition, vol. 2,
June 1990, Atlantic City, NJ, USA, 1990, p. 121..126.
[17] P. Gorry, "General least-squares smoothing and differentiation by the
convolution (Savitzky-Golay) method," Analytical Chemistry, vol. 62,
p. 570..573, 1990.
[18] R. Barnard, G. Dahlquist, K. Pearce, L. Reichel, and K. Richards,
"Gram polynomials and the kummer function," Journal of
Approximation Theory, vol. 94, no. 1, pp. 128 - 143,
1998. [Online]. Available: http://www.sciencedirect.com/science/article/
B6WH7-45K18JY-H/2/c92d2ff697d7631c99abe5d80f281d24
[19] J. Boyd, Chebyschev and Fourier Spectral Methods. Mineola, New
York: Dover Publications Inc., 2001.
[20] A. Jerri, The Gibbs Phenomenon in Fourier Analysis, Splines and
Wavelet Approximations. Dordrecht, Netherlands: Kluver Academic
Publishers, 1998.
[21] S. Ong and P. Raveendren, "Image feature analysis by Hahn orthogonal
moments," Lecture Notes in Computer Science, vol. 3656, pp. 524-531,
2005.
[22] Z. Ping, H. Ren, J. Zou, Y. Sheng, and W. Bo, "Generic orthogonal
moments: Jackobi-Fourier moments for invariant image description,"
Pattern Recognition, vol. 40, pp. 1245-1254, 2005.
[23] B. Bayraktar, T. Bernas, P. Robinson, and B. Rajwa, "A numerical recipe
for accurate image reconstruction from discrete orthogonal moments,"
Pattern Recognition, vol. 40, pp. 659-669, 2007.
[24] J. Thurston and J. Brawn, "The filtering characteristics of least-squares
polynomial approximation for regional/residual separation," Canadian
Journal of Exploration Physics, vol. 28(2), pp. 71-80, 1992.
[25] A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing.
Engelwood Cliffs: Prentice Hall, 1989.
[26] H. Engl, M. Hanke, and A. Neubauer, Regularization of Inverse Problems,
1st ed. Dordrecht: Kluver Academic Publishers, 2000.