Compressing as Well as the Best Tiling of an Image

We investigate the task of compressing an image using different probability models for different regions of the image. In this task, using a larger number of regions would result in better compression of the coefficients of the image but would also require more bits for describing the regions and probability models in the regions. We discuss using quadtrees and windowing for performing the compression and introduce the class of tilings of an image with a small number of arbitrarily sized rectangular tiles of probability models. For an image of size n \Theta n, we give a sequential probability assignment algorithm with a computational complexity of O(Nn 3 ) and a redundancy of O(k log Nn k ) relative to the class k rectangular tiling of an image using N probability models. For the simpler class of tilings using rectangles with width no more than W , we give an algorithm with redundancy O(k log Nn k ) and a computational complexity of O(WNn 2 ). Another interesting class is the ..