Computing moments by prefix sums

Moments of images are widely used in pattern recognition, because in suitab le form they can be made invariant to variations in translation, rotation a nd size. However the computation of discrete moments by their definition re quires many multiplications which limits the speed of computation. In this paper we express the moments as a linear combination of higher order prefix sums, obtained by iterating the prefix sum computation on previous prefix sums, starting with the original function values. Thus the p'th moment m(p) =Sigma(x=1)(N)x(p)f(x) can be computed by O (N . p) additions followed by p multiply-adds. The prefix summations can be realized in time O(N) using p + 1 simple adders, and in time O(p log N) using parallel prefix computation and O(N) adders. The prefix sums can also be used in the computation of tw o-dimensional moments for any intensity function f(x,y). Using a simple bit -serial addition architecture, it is sufficient with 13 full adders and som e shift registers to realize the 10 order 3 image moment computations (m(00 ), m(01), m(10), m(02), m(20), m(12), m(21), m(03), m(30)) for a 512 x 512 size image at the TV rate. In 1986 Hatamian published a computationally equ ivalent algorithm, based on a cascade of filters performing the summations. Our recursive derivation allows for explicit expressions and recursive equ ations for the coefficients used in the final moment calculation. Thus a nu mber of alternative forms for the moment computation can be derived, based on different sets of prefix sums. It is also shown that similar expressions can be obtained for the moments introduced by Liao and Pawlak in 1996, for ming better approximations to the exact geometric moments, at no extra comp utational cost.