DECOMPOSITION PRINCIPLE FOR ANALYZING REGION QUADTREES

摘要

Given a binary image of square size, it is desirable to identify the amount of shift of the foreground pixels such that it minimizes the total number of leaves of the region quadtree that represents the image. This problem is called quadtree normalization. For this problem, the best known algorithms have time complexities O(N~2) logN), where N is the side length of given images (so, N~2 is the total number of pixels). In this paper, we show an algorithm that has the optimal complexity O(N~2) for some class of images. Our strategy consists of two stages: decomposing the given image into axis-parallel rectangles at first and integrating the contributions of individual rectangles afterwards. To do this, we derive the necessary and sufficient condition on any decomposition scheme, in a conditional form of the well-known Inclusion-Exclusion Principle. It turns out that the generated primitives must be "strictly overlapped" to some extent. The optimal linear-time complexity can be achieved in the case when the total area of the decomposed rectangles is bounded by O(N~2) e.g. for the class of images whose foreground part is drawn with the finite number of rectangles. We only sketch the outline of the first decomposition stage of the new algorithm, but the last integrating stage is described in details.