The coding, storage, and reconstruction of images is a major concern in the application of computer technology to technical and scientific problems. In such applications it is highly desirable to reduce the storage and transmission requirements for image data. An image can be coded compactly when it is possible to exploit self similar redundancy in the image. Our research has focused on the development of a `fractal'' method for compressing image data. Our approach to image compression, similar to Jacquin, is to tessellate the image with a tiling which varies with the local image complexity, and to check for self similarity among the tiles. Self similarities are coded as systems of affine transformations which can be stored far more compactly than the original image. This method is inherently lossy, since the self similarities are never exact. We have tested our encoding scheme on a variety of test images, gaining good compression ratios. At high compression ratios, the scheme yields better signal to noise ratios than are reported for other techniques. Our scheme is versatile in that it allows a trade- off between compression, reconstructed image fidelity and encoding time. Our methods are computationally intensive but are feasible for non-real time applications on workstations or main frame computers. We are currently studying applications such as multimedia systems and CD-ROM mass storage systems. The algorithms can be accelerated considerably by dedicated hardware for real time requirements. Fractal compression is a promising approach to image compression. Within a very short development time, fractal techniques have yielded results which rival the best examples of data compression afforded by other methods. Although fractal encoding of images is complex and may require specialized hardware for real time applications, the decoding process can be widely utilized because it is simple, fast, and suitable for software implementation. Thus, it can be run on workstations or personal computers without special requirements. This report contains a description and motivation of the encoding algorithm, a description of a new decoding algorithm, results, comparison with results in the literature, and a discussion of generalizations to the algorithm.
|