A near optimal coder for image geometry with adaptive partitioning

In this paper, we present a new framework to compress the geometry of images. This framework generalizes the standard quad partitioning approaches in compression of image geometry (e.g. wedgelet) in two ways. First, we employ an adaptive rectangular partitioning rather than quadratic partitioning. Second, our coder uses an overcomplete collection of (stripe-like) atoms which contains wedgelets as a special case. We present an information-theoretical analysis based on Kolmogorov\´s e- entropy to show that this collection provides a near-optimal representation of a class of cartoon images with piecewise polynomial boundaries. Furthermore, we develop a provably near-optimal greedy algorithm that significantly reduces the complexity of the exhaustive search method required to achieve the entropy bound. Simulation results for the rate distortion shows a 1.5-2 dB improvement over the standard wedgelets for the "Cameraman" image.