Fractal image compression is a lossy image compression algorithm based on applying systems of iterable functions (usually affine transformations ) to images. This algorithm is known for the fact that in some cases it allows to obtain very high compression ratios with acceptable visual quality for real photographs of natural objects. Due to the difficult situation with patenting, the algorithm was not widely used.
Content
Description
The basis of the fractal coding method is the detection of self-similar sections in the image. For the first time, the possibility of applying the theory of Iterated Function Systems (IFS ) to the problem of image compression was investigated by Michael Barnsley ( Eng. Michael Barnsley [1] ) and Alan Sloan ( Eng. Alan Sloan ). They patented their idea in 1990 and 1991 ( US Patent 5,065,447 ). A. Jacquin ( Fr. Arnaud Jacquin ) introduced a fractal coding method that uses domain and range subimage blocks , square-shaped blocks covering the entire image. This approach has become the basis for most fractal coding techniques. It was developed by Yuval Fisher and a number of other researchers.
In accordance with this method, the image is divided into many non-overlapping rank subimages ( English range subimages ) and a lot of overlapping domain subimages ( English domain subimages ) are determined . For each rank block, the encoding algorithm finds the most suitable domain block and affine transform that translates this domain block into a given rank block. The image structure is mapped to a system of rank blocks, domain blocks, and transforms.
The idea is this: suppose that the original image is a fixed point of some kind of compressive mapping. Then, instead of the image itself, it is possible to remember this display in some way, and to restore it, it is enough to repeatedly apply this display to any starting image.
By Banach's theorem, such iterations always lead to a fixed point, that is, to the original image. In practice, the difficulty lies in finding the most suitable compressive display from the image and in compact storage. As a rule, mapping search algorithms (i.e., compression algorithms) are heavily brute force and require large computational costs. At the same time, recovery algorithms are quite efficient and fast.
In short, the method proposed by Barnsley can be described as follows. The image is encoded by several simple transformations (in our case affine), that is, it is determined by the coefficients of these transformations (in our case A, B, C, D, E, F).
For example, the image of the Koch curve can be encoded with four affine transformations, uniquely identifying it using only 24 coefficients.
Further, having put a black dot at any point in the picture, we apply random transformations some (sufficiently large) number of times (this method is also called fractal ping-pong).
As a result, the point will necessarily go somewhere inside the black area in the original image. After applying this operation, all black space will be filled many times, which will restore the picture.
Method Complexity
The main difficulty of fractal compression lies in the fact that in order to find the corresponding domain blocks, a complete search is required. Since in this case two arrays must be compared each time, this operation is quite lengthy. By a relatively simple transformation, it can be reduced to the operation of the scalar product of two arrays, however, even the calculation of the scalar product requires a rather long time.
Presently [ when? ] a fairly large number of search optimization algorithms that arise during fractal compression are known, since most of the articles exploring the algorithm were devoted to this problem and during active research (1992-1996), up to 300 articles were published per year. Two areas of research turned out to be the most effective: the feature extraction method and the classification of domains method.
Patents
Michael Barnsley and others have obtained several fractal compression patents in the United States and other countries. For example, 4,941,193 , 5,065,447 , 5,384,867 , 5,416,856 and 5,430,812 . These patents cover a wide range of possible changes in fractal compression and seriously hinder its development.
These patents do not limit research in this area, that is, you can invent your own algorithms based on patented ones and publish them. You can also sell algorithms to countries that are not covered by patents. In addition, the majority of patents is 17 years from the date of adoption, and it will expire for most patents in the near future, respectively, the use of the methods covered by these patents will be guaranteed free.
See also
- Fractal
- JPEG 2000
- Differential Analysis Image Compression