Optimal quadtrees for image segments

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(N2 log N), where N is the side length of given images (so, N2 is the total number of pixels).

In this paper, we show an algorithm that has the optimal complexity O(N2) 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(N2) 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.

On the reconstruction of quadtree data

Image compression schemes consist of compression and decompression phases. Often, the decompression phase includes mechanisms for improving the quality of the resulting image. Quadtree compression is one such type of compression. Reconstructed quadtree images can be blocky because of the nature of the compression method, unless additional processing, generally smoothing, is performed. We propose improvements over the reconstruction method described by Shusterman and Feder. The improvements consist of the introduction of a simpler and more effective 2 x 2 reconstruction filter to replace the suggested 3 x 3 filter, and the addition of a reconstruction threshold to preserve image edges. This method is compared experimentally to the original algorithm and also to JPEG compression in terms of complexity and resulting image quality.

Image compression via improved quadtree decomposition algorithms

Quadtree decomposition is a simple technique used to obtain an image representation at different resolution levels. This representation can be useful for a variety of image processing and image compression algorithms. This paper presents a simple way to get better compression performances (in MSE sense) via quadtree decomposition, by using near to optimal choice of the threshold for quadtree decomposition; and bit allocation procedure based on the equations derived from rate-distortion theory. The rate-distortion performance of the improved algorithm is calculated for some Gaussian field, and it is examined vie simulation over benchmark gray-level images. In both these cases, significant improvement in the compression performances is shown.

Hierarchical coding of binary images

Quadtrees are a compact hierarchical method of representation of images. In this paper, we explore a number of hierarchical image representations as applied to binary images, of which quadtrees are a single exemplar. We discuss quadtrees, binary trees, and an adaptive hierarchical method. Extending these methods into the third dimension of time results in several other methods. All of these methods are discussed in terms of time complexity, worst case and average compression of random images, and compression results on binary images derived from natural scenes. The results indicate that quadtrees are the most effective for two-dimensional images, but the adaptive algorithms are more effective for dynamic image sequences.