As digital image and video compression technology evolves, it appears that transform based coding or compression techinques will reach asymptotic rate-distortion performance, especially with respect to linear transforms. Although nonlinear compression techniques (for example, based on Markov models) are being developed, progress has been relatively slow due to challenges in theory development. Alternatively, several research teams have produced algorithms for object-based compression (OBC), whereby an image is segmented into areas of similar color or spatial variance. Each segmented region can then be represented in terms of a small region descriptor and somewhat less compact set of boundary descriptors.
This paper examines boundary representations and complexity measures for OBC - a previous publication, also related to OBC, overviewed region segmentation techniques. Of particular interest to OBC is the evolution of boundary representations from early approaches such as chain coding or simplical complexes to transform coded descriptors such as Fourier or wavelet-based representations. These techniques precede more modern methods such as hierarchical transforms (e.g., wavelets) and direct compression of Boolean boundary representations. In this paper, the authors develop boundary compression algorithms based on concepts derived from statistical image compression theory and hierarchical codebook representations. The resulting boundary encoding technique is suitable for a wide range of compression applications, in particular, OBC. Performance criteria include computational complexity of the encoding process, as well as space complexity of intermediate and final boundary representations.