Fractal compression for generating resolution-independent images (1992)
books.google.com
books.google.com
Remember that photo-enhancing scene in Blade Runner? Are you feeling motivated yet? For me the decompression speed and small file size were nice things when I first encourntered the format back in ~1992 but jpegs were already good in that area and it was obvious that the price of storage space and bandwidth would fall (though I continue to be surprised by the progress of technology). So to critics who say it's not competitive on size or speed - quite right, no argument from me.
However, nothing I have seen in the intervening 22 years comes close to FI compression for image enhancement. It's hard to find examples online but trust me, it was this good on everything we threw at it.
Also from the original thread: http://www.verrando.com/pulcini/gp-ifs1.html < windows en/decoder (IFS-BMP) and some other resources, straight outta 1997.
If it really did that, then it would be badly wrong because for all the compressor knows it's destroying lots of useful information by rounding off all the corners. And it would be miraculous because what it's actually done turns out to make something physically plausible, when there are any number of ways of filling in the missing detail that fit the data in the 64x64 image equally well, as far as anything short of full AI could tell.
But I don't really believe it did really do that, because (1) from Barnsley's description of the algorithm it seems fantastically unlikely that it could, (2) the paper says explicitly that the original and reconstructed images are both 512x512 pixels, and (3) if fractal compression were really doing something so miraculous then Barnsley's article would have made a lot more noise about it (and in particular the discussion of "fractal zoom" that follows wouldn't make any sense if Barnsley thought he had just showed a spectacular 8x fractal zoom already).
I'm guessing that something very bad happened to Figure 2, and that the image that was actually compressed and decompressed to produce Figure 3 looked a lot more like Figure 3 than it did like Figure 2 as shown in the paper.
But the nature of iterated fractal functions is that they generate information, which is how we can get such elaborate pictures of ferns from such a small amount of starting information. When we squint at a pixelated image, we're deliberately trading off optical distortion in order to get a sense of the underlying pattern - it's not more accurate because we're inventing stuff, but it is giving us an answer to the question of 'what function would generate these shapes in a low-resolution picture?' and then going on to iterate that same function.
So while acknowledging the likelihood that you're right and I'm wrong, I'm not totally ready to come off this limb because I'm also thinking of what it was that made the resolution scaling of this technology so good - there was something more complex than mere interpolation going on. I'll have a look through the text again and think about it further.
a) there is something wrong with figure 2 in this PDF
or b) this article is a scam
I'm curious, have you seen other, better evidence that makes you believe in this technology?
It's certainly not a scam, Barnsley's a respected researcher in this field of mathematics - http://en.wikipedia.org/wiki/Barnsley_fern At worst this is a rendering problem in the PDF and some nostalgic over-enthusiasm on my part.
Here's a review of Genuine Fractals photoshop plugin w/ graphics: http://www.kenrockwell.com/tech/gf.htm
result: slightly better than bicubic
That I will believe.
See the correction after the comment below - Good reason to be confused. Fig 2 is actually the first step in decoding.
You are missing the significance of the 64x64. The point was that the picture was split into squares that were bigger than single pixels before encoding. In this case, the regions were 8x8, so there are 64x64 of them in the original 512x512 image. If the basic elements were 1x1 pixel the linear transformation encoding would have made the encoding bigger than the original! The images illustrate some of the steps in the iterative decoding process, which always starts with single intensity blocks in the basic elements (so 64x64 blocks) but iteratively gets closer to the original, finer grained image. It looks like magic, but the fractal theory is sound. It is a lossy process, so there is no guarantee that the encoded image has both limited losses and is small in size.
I was an algorithm developer, not in sales. For sales purposes they clearly could have chosen example images that were more naturally fractal at a scale below a pixel, so blowing them up looked good. I do not know how generally good the zooming in was.
So, if what your saying is true the caption is wrong? Are you saying it is the first stage of decompression? That this is the input data to the decompressor?
I'm assuming therefore that the compressor actually does use a full undownsampled (not blocky) image as it's input. Or uses it as part of it's iterative compression process. Is that correct?
There's a photoshop plugin, Genuine Fractals, that uses fractal image compression for image resizing.
One of the most notable examples of agressive enforcement of patents completely stalling research in otherwise very promising and interesting domain.
https://www.google.com/search?tbm=pts&hl=en&q=barnsley+fract...
https://www.google.com/patents/WO2004081876A1?cl=en&dq=barns...
http://arxiv.org/pdf/math/0312314v1.pdf
If I'm reading this right (but I'm no patent lawyer), Barnsley et al's most recent patent on image compression dates from 1995 and expires next summer: https://www.google.com/patents/US5867603?dq=barnsley+fractal...
It is kind of sad that the reason is so much more mundane.
The damning bits are this: "A fundamental weakness of fractal block coders is that the coders possess no control over the codebook. Codewords are too densely clustered around the very common all-zero subtree and too sparsely distributed elsewhere. This dense clustering of near-zerotrees increases codeword cost but contributes very little to image fidelity. ... At 0.25 b/pixel, over 80% of all coefficients in the 512 × 512 Lena image are assigned to zerotrees by our zerotree-augmented wavelet coder. Hence, only about 20% of the fractal coder’s codewords are significantly different from a zerotree. This redundancy is costly, since when using self-quantization we pay a substantial number of bits to differentiate between these essentially identical zero code words."
Not that I'm arguing for IFS codecs, mind, but Davis did miss the point a bit.
Davis is not the only one to make the observation (he cites two others in that paper), but he does quantify the magnitude of the problem. It's clear it requires some solution before IFS codecs have a chance of being competitive.
This is complicated by the fact that in an IFS, it's not clear which regions are smooth without doing several iterations, but the decoder needs to do all of its codebook pruning before even the first iteration. I'm not aware of a practical solution ever being demonstrated.
One way to demonstrate this (which was shown around the time of Davis's paper, if I recall correctly) is to do the IFS codec in the wavelet domain hierarchically (on quadtrees in the case of an orthonormal wavelet basis). This gives you a similar advantage of spending your encoder bits (which should still be handled by an entropy coder, regardless of method) primarily get spent where the image energy is, but does not truncate information as hard as, say, a zerotree approach.
The problems Davis points out with IFS codecs done on blocks in the spatial domain are issues with block/patch operations and with operating in the spatial domain, not with IFS per se.
The fundamental idea behind IFS codecs is that you encode a transform whose fixed point approximates your signal, you don't encode the signal directly.
The real problem is the difficulty in embedding them, and the need to iterate a few times to converge the result.. which is what you allude to I think.
[note, I really should revisit Davis's paper before discussing , because I'm operating from memory here...]
I believe it is almost the only interesting application.