Fractal-based encoding & decoding

[Vario]

Hi folks,

Over ten years ago people were all excited about fractal-based image compression. At the time computers were really too slow to either encode or decode quickly. Of course now, that has changed.

But I wonder if anyone has even considered implementing something like the following for films? This guy got 24:1 compression for images.

http://www.verrando.com/pulcini/gp-uw1.html

-Vario

[LoRd_MuldeR]

With good old JPEG I can get 24:1 compression for images easily, but it doesn't take 6 minutes. So what?

[Koorogi]

I think one of the more interesting features that's been touted about fractal compression is it's spatial scalability. That is, since it (I believe) works by finding regions of self-similarity between the full size image and a downsized version of the image, you can use this same information to scale the image up and decode it at a larger size, with (it's been argued) better quality than traditional upscaling methods. But it seems fractal encoding never left the realm of being a toy for academics, I imagine mostly because of the abysmal speed.

[Reimar]

Too lazy to read the papers, but an obvious question is how does this differ from wavelet-compressions as used in JPEG-2000, Dirac and snow?

[*.mp4 guy]

Mostly by being completly different in every important way. Also by being useless.

[edit] Additionally, this isn't real fractal compression (which has never been accomplished) its pseudo-block-fractal compression, which is more akin to a bad multiscale vector quantization scheme then anything else.

[Mug Funky]

i wonder if it could be applied to DCT's or some other abstracted frequency plot of the image (or part of it).

sort of like finding "harmonics" and encoding to the nearest deterministic version? like a kind of super-slow-possibly-useless trellis quantization?

it seems doing it on an image is pointless because the vast array of natural images only contain self-similarity of the type needed in areas completely ignored by the human visual system. images seem to be best represented as quantized frequencies. but maybe fractals can work on that data rather than the raw image data?

[*.mp4 guy]

The "bragzone (http://links.uwaterloo.ca/bragzone.base.html)" has a comprehensive collection of comparisons of wavelet, laplacian pyramid, dct and "fractal" based image encoders.

[benwaggoner]

Mostly by being completly different in every important way. Also by being useless.

[edit] Additionally, this isn't real fractal compression (which has never been accomplished) its pseudo-block-fractal compression, which is more akin to a bad multiscale vector quantization scheme then anything else.
Yeah. Even Iterated Systems, who started the whole "fractal codec" nonsense many years ago, and actually launched a product with ClearVideo, gave up and used DCT for their first real video codec. The only thing of real market interest they came up with was "fractal" based scaling, which let you scale up in the frequency domain (in essence) instead of by pixels, which reduced blocking.

I spent waaay to much time working with Iterated's technologies ~12 years ago...

[Nil Einne]

I think Genuine Fractals achieved some degree of success in the image fractal compression domain. While it's primarily been in the scaling field I believe their compression format did get some degree of use since it was quite high at the time for lossless compression (I remember testing it in ~1997 and it was the best of all those I tested at the select few files I used). Now that size is no longer an issue for most people when it comes to images give the price of HDDs etc I suspect this had died down but I think they had some success. Their big problem was probably that size was never an extremely great issue when it came to images for many people and so the risk of using a proprietary and undocuments image compression format was too great. I mean heck even JPEG2000 never took off in most areas.

One interesting is that it looks like fractal compression has been largely ignored for the past 10+ years and many of the original patents are surely close to expiring. Perhaps it's actually a good area for someone who's looking to make a patent free video codec to explore?

[dadix]

i know about this : FIASCO ([F]ractal [I]mage [A]nd [S]equence [CO]dec)
Is open source but not for windows.

http://www.linuxjournal.com/node/4367/print
https://github.com/megatherion/Fiasco

[CruNcher]

Yeah. Even Iterated Systems, who started the whole "fractal codec" nonsense many years ago, and actually launched a product with ClearVideo, gave up and used DCT for their first real video codec. The only thing of real market interest they came up with was "fractal" based scaling, which let you scale up in the frequency domain (in essence) instead of by pixels, which reduced blocking.

I spent waaay to much time working with Iterated's technologies ~12 years ago...

Though the way ClearVideo looks is interesting i mean the look and feel though it's not really surprising if you used to MPEG block based codecs or even wavelet and for the first time see these fractals building up a picture (especially when that whole thing is happening in motion), everyone should have seen that once it is something unique visually :)

And yeah they later became successful with Genuine Fractals for Image Scaling :)
One of those iterated Marketing guys does Digital Video Solution Reviews these days for Streaming Media and he evaluated Mainconcept H.264 vs x264 that's quiet funny http://www.streamingmedia.com/Articles/Editorial/Reviews/Sorenson-Squeeze-8-A-Video-Tutorial-80112.aspx ;)



We reported in January that fractal image compression was gaining new respect in the industry. Confirmation of this comes from Microsoft Multimedia Publishing Group’s director of product development, Greg Riker, and Iterated Systems’ co-president, Michael Barnsley. They have announced that “at least one” forthcoming Microsoft multimedia title will utilize Iterated Systems’ fractal still-image compression technology, under a non-exclusive licensing agreement.

Riker says that for its multimedia titles, Microsoft looked for a methodology that can perform image decompression in software only, yet can display the pictures quickly. Also required were high compression ratios, enabling more images to be packed onto a compact disc, and good image quality. Jan Ozer, Iterated’s vice president of marketing and sales, indicated that the fractal approach not only met these criteria but bested the competing solutions, including JPEG products, on each count.

You can really wonder why Microsoft preferred it back then overall i guess what they talk about is Encarta (not sure) :)
i mean could they really foll Microsoft with one of the biggest Research entities in the World to use their Product quiet amazing to think about it ;)

Though i remember nothing else did Microsoft with Hollywood before FRExt was ready selling their VC-1 to Hollywood executives as the sharpest thing in Town bringing Film Grain to life, though Microsofts PSY work imho is still amazing also if it gets unnoticed most of the times in all the blocks ;)

Ben i still use your Vegas.wmv encode very often btw ;)

[benwaggoner]

Has anyone done a good comparison of fractal-based scaling compare to other modern scaling techniques.

H.264 High Profile I-frames outperform JPEG 2000 and JPEG-XR in compression efficiency, and HEVC/H.265 should be even better for still images. Bigger intra blocks are a big helper for very hgih resolution images.

One of the reasons fractals and wavelets haven't made for promising video codecs is that no one has found a good way to couple motion estimation with them. Block-based motion estimation is really strong, and having symmetry between intra and inter coding is quite valuable in compression efficiency and decoder complexity.

[CruNcher]

Has anyone done a good comparison of fractal-based scaling compare to other modern scaling techniques.

H.264 High Profile I-frames outperform JPEG 2000 and JPEG-XR in compression efficiency, and HEVC/H.265 should be even better for still images. Bigger intra blocks are a big helper for very hgih resolution images.

One of the reasons fractals and wavelets haven't made for promising video codecs is that no one has found a good way to couple motion estimation with them. Block-based motion estimation is really strong, and having symmetry between intra and inter coding is quite valuable in compression efficiency and decoder complexity.

Yup and that remembers me of the state of Point Cloud Rendering where we slowly seem to brake the last frontiers now that over years made it unpractical for Games other then Rendering enviroment i guess we advanced a lot since the iterate days so i wonder whose gonna brake those last frontiers in the future the word RESEARCHING is not without reason that word, and in a more and more heterogeneous environment it should be possible to bundle the given resources efficiently ;)

[benwaggoner]

Yup and that remembers me of the state of Point Cloud Rendering where we slowly seem to brake the last frontiers now that over years made it unpractical for Games other then Rendering enviroment i guess we advanced a lot since the iterate days so i wonder whose gonna brake those last frontiers in the future the word RESEARCHING is not without reason that word, and in a more and more heterogeneous environment it should be possible to bundle the given resources efficiently ;)
The problem with "brilliant new transform" ideas is that they have to compete with highly, highly refined implementations of almost every little detail of block-based DCT-esque encoding.

Either the transform has to be SO much better than DCT that a basic implementation of it beats modern DCT implementations, or the new transform needs to be implemented with brilliant refinement. That requires a frothy mix of genius, time, and money that is hard to find for a blue-sky, high-risk codec.

It's hard to really even evaluate new basic codec ideas for these reasons, since it's hard to predict how good a radical new idea would be once it is highly refined.