On the Number of Rectangular Tilings

Adaptive multiscale representations via quadtree splitting and two-dimensional (2-D) wavelet packets, which amount to space and frequency decompositions, respectively, are powerful concepts that have been widely used in applications. These schemes are direct extensions of their one-dimensional counterparts, in particular, by coupling of the two dimensions and restricting to only one possible further partition of each block into four subblocks. In this paper, we consider more flexible schemes that exploit more variations of multidimensional data structure. In the meantime, we restrict to tree-based decompositions that are amenable to fast algorithms and have low indexing cost. Examples of these decomposition schemes are anisotropic wavelet packets, dyadic rectangular tilings, separate dimension decompositions, and general rectangular tilings. We compute the numbers of possible decompositions for each of these schemes. We also give bounds for some of these numbers. These results show that the new rectangular tiling schemes lead to much larger sets of 2-D space and frequency decompositions than the commonly-used quadtree-based schemes, therefore bearing the potential to obtain better representation for a given image