Algorithms for Moment Computation
Jan Flusser
Institute of Information Theory and Automation, Czech Academy of Sciences, Prague, Czech Republic
Search for more papers by this authorTomáš Suk
Institute of Information Theory and Automation, Czech Academy of Sciences, Prague, Czech Republic
Search for more papers by this authorBarbara Zitová
Institute of Information Theory and Automation, Czech Academy of Sciences, Prague, Czech Republic
Search for more papers by this authorJan Flusser
Institute of Information Theory and Automation, Czech Academy of Sciences, Prague, Czech Republic
Search for more papers by this authorTomáš Suk
Institute of Information Theory and Automation, Czech Academy of Sciences, Prague, Czech Republic
Search for more papers by this authorBarbara Zitová
Institute of Information Theory and Automation, Czech Academy of Sciences, Prague, Czech Republic
Search for more papers by this authorSummary
This chapter focuses on the computational aspects of moments of digital images. In digital image processing, all quantities have to be converted from the continuous to the discrete domain, and efficient algorithms for dealing with discrete quantities must be developed. The chapter shows how the definition of image moments can be converted from the continuous domain to the discrete one. The methods for fast computation of the moments of binary images can be divided into two groups referred to as the boundary-based methods and the decomposition methods. A majority of the boundary-based methods use the Green's theorem, which evaluates the double integral over the object by means of line integration along the object boundary. The decomposition algorithms are more time-consuming. Decomposition into rectangular blocks can only be applied to the objects in volumetric representation. Approximation methods are algorithms for computation of moments of graylevel images that reach low complexity at the expense of accuracy.
References
-
W. K. Pratt, Digital Image Processing. Wiley Interscience, 4th ed., 2007.
10.1002/0470097434 Google Scholar
- M. Šonka, V. Hlaváč, and R. Boyle, Image Processing, Analysis and Machine Vision. Thomson, 3rd ed., 2007.
- W. G. Lin and S. Wang, “A note on the calculation of moments,” Pattern Recognition Letters, vol. 15, no. 11, pp. 1065–1070, 1994.
- J. Flusser, “Refined moment calculation using image block representation,” IEEE Transactions on Image Processing, vol. 9, no. 11, pp. 1977–1978, 2000.
- S. X. Liao and M. Pawlak, “On image analysis by moments,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 18, pp. 254–266, 1996.
- K. Chen, “Efficient parallel algorithms for the computation of two-dimensional image moments,” Pattern Recognition, vol. 23, no. 1–2, pp. 109–119, 1990.
- K. L. Chung, “Computing horizontal/vertical convex shape's moments on reconfigurable meshes,” Pattern Recognition, vol. 29, no. 10, pp. 1713–1717, 1996.
- B.-C. Li and J. Shen, “Fast computation of moment invariants,” Pattern Recognition, vol. 24, no. 8, pp. 807–813, 1991.
- X. Y. Jiang and H. Bunke, “Simple and fast computation of moments,” Pattern Recognition, vol. 24, no. 8, pp. 801–806, 1991.
- W. Philips, “A new fast algorithm for moment computation,” Pattern Recognition, vol. 26, no. 11, pp. 1619–1621, 1993.
- G. Y. Tang, “A discrete version of Green's theorem,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 4, no. 3, pp. 242–249, 1982.
- L. Yang and F. Albregtsen, “Fast and exact computation of Cartesian geometric moments using discrete Green's theorem,” Pattern Recognition, vol. 29, no. 11, pp. 1061–1073, 1996.
- J. H. Sossa-Azuela, I. Mazaira, and J. I. Zannatha, “An extension to Philip's algorithm for moment calculation,” Computación y Sistemas, vol. 3, no. 1, pp. 5–16, 1999.
- J. Flusser, “Fast calculation of geometric moments of binary images,” in Proceedings of the 22nd Workshop on Pattern Recognition and Medical Computer Vision OAGM'98, pp. 265–274, ÖCG, 1998.
- R. Mukundan and K. R. Ramakrishnan, “Fast computation of Legendre and Zernike moments,” Pattern Recognition, vol. 28, no. 9, pp. 1433–1442, 1995.
- J. G. Leu, “Computing a shape's moments from its boundary,” Pattern Recognition, vol. 24, no. 10, pp. 949–957, 1991.
- M. H. Singer, “A general approach to moment calculation for polygons and line segments,” Pattern Recognition, vol. 26, no. 7, pp. 1019–1028, 1993.
- J. Flusser, “Effective boundary-based calculation of object moments,” in Proceedings of the International Conference on Image and Vision Computing '98 New Zealand IVCNZ '98 , pp. 369–374, The University of Auckland, 1998.
- L. Yang, F. Albregtsen, and T. Taxt, “Fast computation of three-dimensional geometric moments using a discrete divergence theorem and a generalization to higher dimensions,” Graphical Models and Image Processing, vol. 59, no. 2, pp. 97–108, 1997.
- B. C. Li and S. D. Ma, “Efficient computation of 3D moments,” in Proceedings of the 12th International Conference on Pattern Recognition ICPR'94, vol. I, pp. 22–26, IEEE, 1994.
- S. A. Sheynin and A. V. Tuzikov, “Explicit formulae for polyhedra moments,” Pattern Recognition Letters, vol. 22, no. 10, pp. 1103–1109, 2001.
- B. C. Li, “The moment calculation of polyhedra,” Pattern Recognition, vol. 26, no. 8, pp. 1229–1233, 1993.
- A. G. Mamistvalov, “ -dimensional moment invariants and conceptual mathematical theory of recognition -dimensional solids,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no. 8, pp. 819–831, 1998.
- T. Suk, C. Höschl IV, and J. Flusser, “Decomposition of binary images – a survey and comparison,” Pattern Recognition, vol. 45, no. 12, pp. 4279–4291, 2012.
-
P. Campisi and K. Egiazarian, Blind Image Deconvolution: Theory and Applications. CRC Press, 2007.
10.1201/9781420007299 Google Scholar
- A. Levin, R. Fergus, F. Durand, and W. T. Freeman, “Image and depth from a conventional camera with a coded aperture,” in Special Interest Group on Computer Graphics and Interactive Techniques Conference SIGGRAPH'07, (New York, NY, USA), ACM, 2007.
-
W. Liou, J. Tan, and R. Lee, “Minimum partitioning simple rectilinear polygons in O(n log log n)-time,” in Proceeding of the fifth Annual ACM symposium on Computational Geometry SoCG'89, (New York, NY, USA), pp. 344–353, ACM, 1989.
10.1145/73833.73871 Google Scholar
- K. D. Gourley and D. M. Green, “A polygon-to-rectangle conversion algorithm,” IEEE Computer Graphics and Applications, vol. 3, no. 1, pp. 31–36, 1983.
- M. F. Zakaria, L. J. Vroomen, P. Zsombor-Murray, and J. M. van Kessel, “Fast algorithm for the computation of moment invariants,” Pattern Recognition, vol. 20, no. 6, pp. 639–643, 1987.
- M. Dai, P. Baylou, and M. Najim, “An efficient algorithm for computation of shape moments from run-length codes or chain codes,” Pattern Recognition, vol. 25, no. 10, pp. 1119–1128, 1992.
- B. C. Li, “A new computation of geometric moments,” Pattern Recognition, vol. 26, no. 1, pp. 109–113, 1993.
- I. M. Spiliotis and B. G. Mertzios, “Real-time computation of two-dimensional moments on binary images using image block representation,” IEEE Transactions on Image Processing, vol. 7, no. 11, pp. 1609–1615, 1998.
- E. Kawaguchi and T. Endo, “On a method of binary-picture representation and its application to data compression,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 2, no. 1, pp. 27–35, 1980.
- J. Flusser, “An adaptive method for image registration,” Pattern Recognition, vol. 25, no. 1, pp. 45–54, 1992.
- C.-H. Wu, S.-J. Horng, and P.-Z. Lee, “A new computation of shape moments via quadtree decomposition,” Pattern Recognition, vol. 34, no. 7, pp. 1319–1330, 2001.
- J. H. Sossa-Azuela, C. Yáñez-Márquez, and J. L. Díaz de León Santiago, “Computing geometric moments using morphological erosions,” Pattern Recognition, vol. 34, no. 2, pp. 271–276, 2001.
- T. Suk and J. Flusser, “Refined morphological methods of moment computation,” in 20th International Conference on Pattern Recognition ICPR'10, pp. 966–970, IEEE, 2010.
- G. Borgefors, “Distance transformations in digital images,” Computer Vision, Graphics, and Image Processing, vol. 34, no. 3, pp. 344–371, 1986.
- M. Seaidoun, A fast exact euclidean distance transform with application to computer vision and digital image processing . PhD thesis, Northeastern University, Boston, Massachusetts, USA, 1993. Advisor John Gauch.
- T. E. Schouten and E. L. van den Broek, “Incremental distance transforms (IDT),” in 20th International Conference on Pattern Recognition ICPR'10, pp. 237–240, IEEE, 2010.
-
J. M. Keil, “Polygon decomposition,” in Handbook of Computational Geometry, pp. 491–518, Elsevier, 2000.
10.1016/B978-044482537-7/50012-7 Google Scholar
- W. Lipski Jr., E. Lodi, F. Luccio, C. Mugnai, and L. Pagli, “On two-dimensional data organization II,” in Fundamenta Informaticae, vol. II of Annales Societatis Mathematicae Polonae, Series IV , pp. 245–260, 1979.
- T. Ohtsuki, “Minimum dissection of rectilinear regions,” in Proceedings of the IEEE International Conference on Circuits and Systems ISCAS'82, pp. 1210–1213, IEEE, 1982.
- L. Ferrari, P. V. Sankar, and J. Sklansky, “Minimal rectangular partitions of digitized blobs,” Computer Vision, Graphics, and Image Processing, vol. 28, no. 1, pp. 58–71, 1984.
- H. Imai and T. Asano, “Efficient algorithms for geometric graph search problems,” SIAM Journal on Computing, vol. 15, no. 2, pp. 478–494, 1986.
- D. Eppstein, “Graph-theoretic solutions to computational geometry problems,” in 35th International Workshop on Graph-Theoretic Concepts in Computer Science WG'09, vol. LNCS 5911, pp. 1–16, Springer, 2009.
- A. V. Goldberg and S. Rao, “Beyond the flow decomposition barrier,” Journal of the Association for Computing Machinery, vol. 45, no. 5, pp. 783–797, 1998.
- A. V. Goldberg and R. E. Tarjan, “A new approach to the maximum-flow problem,” Journal of the Association for Computing Machinery, vol. 35, no. 4, pp. 921–940, 1988.
- J. Edmonds and R. M. Karp, “Theoretical improvements in algorithmic efficiency for network flow problems,” Journal of the Association for Computing Machinery, vol. 19, no. 2, pp. 248–264, 1972.
- J. D. Zhou, H. Z. Shu, L. M. Luo, and W. X. Yu, “Two new algorithms for efficient computation of Legendre moments,” Pattern Recognition, vol. 35, no. 5, pp. 1143–1152, 2002.
-
Y. Xin, M. Pawlak, and S. Liao, “Image reconstruction with polar Zernike moments,” in Proceedings of the International Conference on Advances in Pattern Recognition ICAPR'05 (S. Singh, M. Singh, C. Apté, and P. Perner, eds.), vol. 3687 of
Lecture Notes in Computer Science
, pp. 394–403, Springer, 2005.
10.1007/11552499_45 Google Scholar
- K. M. Hosny, M. A. Shouman, and H. M. A. Salam, “Fast computation of orthogonal Fourier-Mellin moments in polar coordinates,” Journal of Real-Time Image Processing, vol. 6, no. 2, pp. 73–80, 2011.
- C. Höschl IV and J. Flusser, “Close-to-optimal algorithm for decomposition of 3D shapes,” Computational Geometry, 2016 (to appear).
- V. J. Dielissen and A. Kaldewaij, “Rectangular partition is polynomial in two dimensions but NP-complete in three,” Information Processing Letters, vol. 38, no. 1, pp. 1–6, 1991.
- G. A. Papakostas, E. G. Karakasis, and D. E. Koulouriotis, “Efficient and accurate computation of geometric moments on gray–scale images,” Pattern Recognition, vol. 41, no. 6, pp. 1895–1904, 2008.
- I. M. Spiliotis and Y. S. Boutalis, “Parameterized real-time moment computation on gray images using block techniques,” Journal of Real-Time Image Processing, vol. 6, no. 2, pp. 81–91, 2011.
- K.-L. Chung and P.-C. Chen, “An efficient algorithm for computing moments on a block representation of a grey-scale image,” Pattern Recognition, vol. 38, no. 12, pp. 2578–2586, 2005.
- R. Mukundan, “Some computational aspects of discrete orthonormal moments,” IEEE Transactions on Image Processing, vol. 13, no. 8, pp. 1055–1059, 2004.
- H. Zhu, H. Shu, J. Zhou, L. Luo, and J.-L. Coatrieux, “Image analysis by discrete orthogonal dual Hahn moments,” Pattern Recognition Letters, vol. 28, no. 13, pp. 1688–1704, 2007.
- H. Zhu, H. Shu, J. Liang, L. Luo, and J.-L. Coatrieux, “Image analysis by discrete orthogonal Racah moments,” Signal Processing, vol. 87, no. 4, pp. 687–708, 2007.
- M. Al-Rawi, “Fast Zernike moments,” Journal of Real–Time Image Processing, vol. 3, no. 1–2, pp. 89–96, 2008.
- C.-W. Chong, R. Paramesran, and R. Mukundan, “A comparative analysis of algorithms for fast computation of Zernike moments,” Pattern Recognition, vol. 36, no. 3, pp. 731–742, 2003.
- A. Prata and W. V. T. Rusch, “Algorithm for computation of Zernike polynomials expansion coefficients,” Applied Optics, vol. 28, no. 4, pp. 749–754, 1989.
- E. C. Kintner, “On the mathematical properties of Zernike polynomials,” Journal of Modern Optics, vol. 23, no. 8, pp. 679–680, 1976.
- G. R. Amayeh, A. Erol, G. Bebis, and M. Nicolescu, “Accurate and efficient computation of high order Zernike moments,” in Proceedings of the First International Symposium on Advances in Visual Computing ISVC'05, vol. LNCS 3804, pp. 462–469, Springer, 2005.
- S.-K. Hwang and W.-Y. Kim, “A novel approach to the fast computation of Zernike moments,” Pattern Recognition, vol. 39, no. 11, pp. 2065–2076, 2006.
- H. Shu, L. Luo, X. Bao, W. Yu, and G. Han, “An efficient method for computation of Legendre moments,” Graphical Models, vol. 62, no. 4, pp. 237–262, 2000.
- P.-T. Yap and R. Paramesran, “An efficient method for the computation of Legendre moments,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 12, pp. 1996–2002, 2005.
- G. Wang and S. Wang, “Parallel recursive computation of the inverse Legendre moment transforms for signal and image reconstruction,” IEEE Signal Processing Letters, vol. 11, no. 12, pp. 929–932, 2004.
- G. Wang and S. Wang, “Recursive computation of Tchebichef moment and its inverse transform,” Pattern Recognition, vol. 39, no. 1, pp. 47–56, 2006.
- L. Kotoulas and I. Andreadis, “Fast computation of Chebyshev moments,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 16, no. 7, pp. 884–888, 2006.
- H. Shu, H. Zhang, B. Chen, P. Haigron, and L. Luo, “Fast computation of Tchebichef moments for binary and grayscale images,” IEEE Transactions on Image Processing, vol. 19, no. 12, pp. 3171–3180, 2010.
- K.-H. Chang, R. Paramesran, B. Honarvar, and C.-L. Lim, “Efficient hardware accelerators for the computation of Tchebichef moments,” IEEE Transactions on Circuits and Systems for Video Technology, vol. 22, no. 3, pp. 414–425, 2012.
- B. Honarvar, R. Paramesran, and C.-L. Lim, “The fast recursive computation of Tchebichef moment and its inverse transform based on Z-transform,” Digital Signal Processing, vol. 23, no. 5, pp. 1738–1746, 2013.
- K. M. Hosny, “Exact Legendre moment computation for gray level images,” Pattern Recognition, vol. 40, no. 12, pp. 3597–3605, 2007.
- K. M. Hosny, “Fast computation of accurate Zernike moments,” Journal of Real-Time Image Processing, vol. 3, no. 1, pp. 97–107, 2010.
- K. M. Hosny, “Fast computation of accurate Gaussian-Hermite moments for image processing applications,” Digital Signal Processing, vol. 22, no. 3, pp. 476–485, 2012.
- K. M. Hosny, “Image representation using accurate orthogonal Gegenbauer moments,” Pattern Recognition Letters, vol. 32, no. 6, pp. 795–804, 2011.
- G. Zhang, Z. Luo, B. Fu, B. Li, J. Liao, X. Fan, and Z. Xi, “A symmetry and bi-recursive algorithm of accurately computing Krawtchouk moments,” Pattern Recognition Letters, vol. 31, no. 7, pp. 548–554, 2010.
- A. Venkataramana and P. Ananth Raj, “Fast computation of inverse Krawtchouk moment transform using Clenshaw's recurrence formula,” in International Conference on Image Processing ICIP'07, vol. 4, pp. 37–40, IEEE, 2007.
- B. Honarvar and J. Flusser, “Fast computation of Krawtchouk moments,” Information Sciences, vol. 288, pp. 73–86, 2014.
- M. Sayyouri, A. Hmimid, and H. Qjidaa, “A fast computation of novel set of Meixner invariant moments for image analysis,” Circuits Systems and Signal Processing, vol. 34, no. 3, pp. 875–900, 2014.
-
A. Venkataramana and P. Ananth Raj, “Computation of Hahn moments for large size images,” Journal of Computer Science, vol. 6, no. 9, pp. 1037–1041, 2010.
10.3844/jcssp.2010.1037.1041 Google Scholar
- M. Sayyouri, A. Hmimid, and H. Qjidaa, “Improving the performance of image classification by Hahn moment invariants,” Journal of the Optical Society of America A, vol. 30, no. 11, pp. 2381–2394, 2013.
- J. Gu, H. Z. Shu, C. Toumoulin, and L. M. Luo, “A novel algorithm for fast computation of Zernike moments,” Pattern Recognition, vol. 35, no. 12, pp. 2905–2911, 2002.
- C.-W. Chong, P. Raveendran, and R. Mukundan, “An efficient algorithm for fast computation of pseudo-Zernike moments,” International Journal of Pattern Recognition and Artificial Intelligence, vol. 17, no. 06, pp. 1011–1023, 2003.
- S. O. Belkasim, M. Ahmadi, and M. Shridhar, “Efficient algorithm or fast computation of Zernike moments,” Journal of the Franklin Institute, vol. 333(B), no. 4, pp. 577–581, 1996.
- G. A. Papakostas, Y. S. Boutalis, D. A. Karras, and B. G. Mertzios, “Fast numerically stable computation of orthogonal Fourier-Mellin moments,” IET Computer Vision, vol. 1, no. 1, pp. 11–16, 2007.
- B. Fu, J.-Z. Zhou, Y.-H. Li, B. Peng, L.-Y. Liu, and J.-Q. Wen, “Novel recursive and symmetric algorithm of computing two kinds of orthogonal radial moments,” Image Science Journal, vol. 56, no. 6, pp. 333–341, 2008.
- E. Walia, C. Singh, and A. Goyal, “On the fast computation of orthogonal Fourier-Mellin moments with improved numerical stability,” Journal of Real-Time Image Processing, vol. 7, no. 4, pp. 247–256, 2012.
- C. Singh and R. Upneja, “Accurate computation of orthogonal Fourier-Mellin moments,” Journal of Mathematical Imaging and Vision, vol. 44, no. 3, pp. 411–431, 2012.
- R. Upneja and C. Singh, “Fast computation of Jacobi-Fourier moments for invariant image recognition,” Pattern Recognition, vol. 48, no. 5, pp. 1836–1843, 2015.
- C. Camacho-Bello, C. Toxqui-Quitl, A. Padilla-Vivanco, and J. J. Báez-Rojas, “High-precision and fast computation of Jacobi-Fourier moments for image description,” Journal of the Optical Society of America A, vol. 31, no. 1, pp. 124–134, 2014.
- Y. Jiang, Z. Ping, and L. Gao, “A fast algorithm for computing Chebyshev-Fourier moments,” in International Seminar on Future Information Technology and Management Engineering FITME'10, pp. 425–428, IEEE, 2010.
- H. Shu, L. Luo, W. Yu, and J. Zhou, “Fast computation of Legendre moments of polyhedra,” Pattern Recognition, vol. 34, no. 5, pp. 1119–1126, 2001.
- K. M. Hosny, “Fast and low-complexity method for exact computation of 3D Legendre moments,” Pattern Recognition Letters, vol. 32, no. 9, pp. 1305–1314, 2011.
- K. M. Hosny and M. A. Hafez, “An algorithm for fast computation of 3D Zernike moments for volumetric images,” Mathematical Problems in Engineering, vol. 2012, pp. 1–17, 2012.
- J. M. Pozo, M.-C. Villa-Uriol, and A. F. Frangi, “Efficient 3D geometric and Zernike moments computation from unstructured surface meshes,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 3, pp. 471–484, 2011.