Fractal Encoding with HV Partitions

In this chapter we describe a way to partition images that gives significantly better results. The method, which we call fractal encoding with HV partitioning, also includes several optimizations in the storage of the transformations, the coding, and the decompression algorithm. The partitioning method used to generate the ranges is based on rectangles. A rectangular portion of the image is subdivided, either horizontally or vertically, to yield two new rectangles. The main advantage of this method over the quadtree method is clear: the ranges are selected adaptively,1 with partitions that can correspond to image edges (at least horizontal and vertical ones). This strength also leads to the main drawback: since the domain size is a multiple of the range size, the large number of range sizes leads to a large number of domains and thus to a large number of domain-range comparisons. Also, there are many ways to select the location of the partition, and we will only describe our final implementation. Our search through all the possible implementations was neither systematic nor complete, and it is clear that further work could yield improvements. Nevertheless, this method gives results better than any similar method of which we are aware.