A new computation of shape moments via quadtree decomposition

摘要

The main contribution of this paper is in designing an optimal and/or optimal speed-up algorithm for computing shape moments. We introduce a new technique for computing shape moments. The new technique is based on the quadtree representation of images. We decompose the image into a number of non-overlapped squares, since the moment computation of squares is easier than that of the whole image. The proposed sequential algorithm reduces the computational complexity significantly. By integrating the advantages of both optical transmission and electronic computation, the proposed parallel algorithm can be run in O(1) time using N×N1+1/c processors when the input image is complicated. If the input image is simple (i.e., the image can be represented by a few quadtree nodes), the proposed parallel algorithm can be run in O(1) time using N×N processors. In the sense of the product of time and the number of processors used, the proposed parallel algorithm is time and cost optimal and achieves optimal speed-up.