Fast computation of three-dimensional geometric moments using a discrete divergence theorem and a generalization to higher dimensions

The three-dimensional Cartesian geometric moments (for short 3-D moments) are important features for 3-D object recognition and shape description. To calculate the moments of objects in a 3-D image by a straightforward method requires a large number of computing operations. Some authors have proposed fast algorithms to compute the 3-D moments. However, the problem of computation has not been well solved since all known methods require computations of order N-3, assuming that the object is represented by an N x N x N voxel image. In this paper, we present a discrete divergence theorem which can be used to compute the sum of a function over an n-dimensional discrete region by a summation over the discrete surface enclosing the region. As its corollaries, we give a discrete Gauss's theorem for 3-D discrete objects and a discrete Green's theorem for 2-D discrete objects. Using a fast surface tracking algorithm and the discrete Gauss's theorem, we design a new method to compute the geometric moments of 3-D binary objects as observed in 3-D discrete images. This method reduces the computational complexity significantly, requiring computation of O(N-2). This reduction is demonstrated experimentally on two 3-D objects. We also generalize the method to deal with high-dimensional images. Some 3-D moment invariants and shape features are also discussed. (C) 1997 Academic Press.