Discrete Polynomial Moments and Savitzky-Golay Smoothing

Authors: Paul O'Leary, Matthew Harker

Abstract:

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.

Keywords: Gram polynomials, Savitzky-Golay Smoothing, Discrete Polynomial Moments

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078873

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.