IMAGE COMPRESSION USING BINARY SPACE PARTITIONING TREES

For low bit-rate compression applications, segmentation-based coding m ethods provide, in general, high compression ratios when compared with traditional (e.g., transform and subband) coding approaches. In this paper, we present a new segmentation-based image coding method that di vides the desired image using binary space partitioning (BSP). The BSP approach partitions the desired image recursively by arbitrarily orie nted lines in a hierarchical manner, This recursive partitioning gener ates a binary tree, which is referred to as the BSP-tree representatio n of the desired image. The most critical aspect of the BSP-tree metho d is the criterion used to select the partitioning lines of the BSP tr ee representation. In previous works, we developed novel methods for s electing the BSP-tree lines, and showed that the BSP approach provides efficient segmentation of images. In this paper, we describe a hierar chical approach for coding the partitioning lines of the BSP-tree repr esentation. We also show that the image signal within the different re gions (resulting from the recursive partitioning) can be represented u sing low-order polynomials. Furthermore, we employ an optimum pruning algorithm to minimize the bit rate of the BSP tree representation (for a given budget constraint) while minimizing distortion. Simulation re sults and comparisons with other compression methods are also presente d.