QUADTREE-STRUCTURED RECURSIVE PLANE DECOMPOSITION CODING OF IMAGES

The approximation of two-dimensional highly correlated grey value functions can be performed using a linear model of the type f (x, y) = a + bx + cy. The set of plane parameters (PP's) [a, b, c] can be determined in the least squares sense for, say, a block of size N x N pixels. Starting with a block size of 2 x 2 pixels, it can be shown that the PP's obey a recursive law such that the PP's of a 2N x 2N block can be computed recursively when only the PP's of the four adjacent subblocks of size N x N in the lower decomposition level are known. This concept of "recursive plane decomposition" (RPD) is embedded in a quadtree data structure to obtain a new variable block size image coding algorithm that offers a high performance at a low computational cost. Extensive comparisons to other state-of-the-art image coding algorithms are reported in the paper. These comparisons indicate that the quadtree-RPD coding algorithm presented in this paper performs very closely to the results obtained by other important schemes, such as vector quantization and subband coding, in the range of 0.5-1.5 b per pixel. This is achieved at a coder complexity as low as 3 multiplications/pixel and 8 additions/pixel which compares favorably with the complexity of traditional methods.