Slashdot Mirror
jpeg2000 Allows 200:1 Wavelet Compression
Polo writes "Here is an
EE times article about the ISO JPEG2000 standard that has been
finalized and allows a new wavelet compression scheme that gives
good results at as much as 200:1 compression ratios. It looks
pretty promising. It is royalty-free, but there is also discussion
about a second standard that allows third-party, royalty-based extensions. I wonder if motion-jpeg with wavelets could fit a movie
on a CD or something."
That was pretty much about time someone took the wavelets into image compression.
:)
I worked with wavelet transforms (Daubechies wavelets) a year and a half ago, and back then it was pretty clear that it would be possible to compress images and sound much harder using the wavelet domain rather than the Fourier domain.
For those who don't know, the trick is:
JPEG/MPEG/MP3 uses Fourier transform to transform the image/sound data into their spectral components. But this spectral representation of the data does not say anything about the _locality_ of the frequency components. Therefore representing spikes/discontinuties will require a very large number of frequency components when using Fourier domain, which in turn leads to poor compression. You can see this problem by drawing a few sharp lines in an image and compressing it hard with JPEG.
Wavelets on the other hand, represent both an equivalent of the frequency component, along with locality information. Spikes/discontinuities can be approximated well using only a few wavelets. This in turn leads to good compression.
Another nice thing about wavelet compression is, that wavelets tend to represent discontinuities well, even with hard compression (eg. a lot of missing or roughly approximated wavelet components). Therefore a very hard compressed image will still have fairly sharp edges, completely contrary to JPEG compression. This is pretty important if you compress a picture holding text.
Anyways, someone is now working on JPEG with wavelets... What about sound and video ?? There is no reason as to why wavelets should not provide equal improvements in both audio and video.
My personal conspiracy theory is, that there exists a *LOT* of expensive hardware that can do Fouries forwards and back to allow real-time encoding and decoding of MPEG movies in good quality. The companies producing these devices will lobby any standards-organisation to *NOT* consider wavelets and stick to good old Fourier. If this holds, it will take a few years until we see Wavelet compressed video
Maybe I'm just being too cynical, but I think that one of the major points of the JPEG2000 effort is to fix the "bug" in the original JPEG (or at least the universally implemented arithmetic coding-free subset) is patent free.
And basically, I agree with Tom's assessment here. While JPEG is far from perfect, it is "good enough" for photographic images, and the massive increases in bandwidth and storage capacity kinda make high compression ratios irrelevant.
Finally, a 200:1 compression ration is pretty meaningless without some kind of context. A much more meaningful comparison is how many bytes are required to get the same quality image as some other compression standard, such as the original JPEG. The figure itself reminds me of when Triada was hyping their 200:1 lossless compression. Joe Bugajski gave a talk on this at Berkeley, and started waxing raphsodic on the incredible stuff that the Library of Congress had in their collection. Books and audio materials were fine, but when he got to the Stradivarius violins, my fellow grad students just broke up laughing. It's not hard to imagine 200:1 compression of that, but uncompression is tricky at best
LILO boot: linux init=/usr/bin/emacs
The comparison in the EE times article is rigged to the point of almost being faked.
Basically, what they did is take a high resolution image and compress the shit out of it with both original JPEG and JPEG2000. Yes, JPEG does poorly at such high compression ratios.
What they neglected to point out, however, is that you can get excellent results from just shrinking the image. From what I can tell, the test image is displayed as a GIF shrunk 3x from the original "3 MB" image. A very reasonable thing to do, if you want a 19k target file size, would be to first shrink the image 3x, then compress it 17:1 using plain JPEG. I tried this, and got results entirely comparable to the JPEG2000 example (the problem with my informal test is that the GIF dithering artifacts are noticeably softened, which is basically a problem with the fact that they presented the image as a GIF instead of true color).
So the bottom line is that JPEG2000 performs a lot better if you're doing something stupid with it, but take the claims of dramatically better compression with a grain of salt.
LILO boot: linux init=/usr/bin/emacs
It doesn't matter if some of the pixels match if which ones do is random, so it is at least as hard to specify per pixel what it matches as it is to say per pixel what it is.
Understanding it that way could be complex, let me give the direct definition for a binary signal.
A source of a stream of 1's and 0's is a white noise generator if each digit is randomly (50-50 odds) and independently a 1 or a 0. The resulting signal carries the maximal information/pixel possible, and hence there can exist no compression method that is an overall win in compressing white noise.
What does this look like? Start tossing a coin and record what comes up! (OK, that is not perfect but it is close enough.)
As an image it looks like..static.
When played, the noise sounds like..static.
Any signal with a large amount of information/bit looks like white noise and hence looks like..static.
It is a fundamental fact of information theory that white noise (which resembles static) is identical with a perfectly encrypted signal is identical with a perfectly compressed signal.
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
White noise, by definition, has no redundancy.
:-)
Many things that look like white noise are not, but white noise itself?
Incidentally static is what white noise sounds like, and any efficiently compressed signal looks like white noise, which is why a modem sounds like static.
Another interesting fact - a compressed file is a pretty good source of random data, and a compressed encrypted file is substantially more secure than a file just encrypted with the same algorithm. OTOH an encrypted compressed file is a PoS. The encryption messes up the attempted compression.
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
Hang on, isn't that a 256 color GIF they used for the comparison?
Yeah, I noticed that too. Kind of like those TV ads that show an HDTV picture... they don't look too impressive on my ordinary TV set.
My guess is that they used GIF so they could control the color palette and make the presented images appear to approximate the image appearance. In other words, it's a demo.
--JT
The inventor and holder of the patents for fractal compression is Iterated Systems.
I'd thought they'd had these techniques rolled into JPEG and MPEG already but it looks like you're right, they've kept the techniques for their own products.
Consciousness is not what it thinks it is
Thought exists only as an abstraction
I remember reading about fractal compression, which was supposed to blow JPG away. It was in the early 90s, and obviously it didn't have much effect on the industry.
Because the inventor held onto the patent too closely. Fractal compression works... encoding is horribly slow but decompression isn't too bad at all. Compression ratios are amazing, better than wavelet I think. But if the inventor ever wants to see it in widespread use, he has to let go and make it free.
*sigh*
Life's a bitch but somebody's gotta do it.
Hang on, isn't that a 256 color GIF they used for the comparison?
Anyway... it sure looks promising, but I'm not really impressed by that 158:1 result on this particular image, most of it comprises of a gradient that should compress rather well with their scheme. I'd like to see results with images containing more detail.
-W
I haven't bothered checking out the spec in its entirety, but I've got to wonder about a few things:
1. Is the 2:1 5/3 'mother wavelet' truly lossless for any and all inputs?
2. What kind of 'average' compression can we expect? One poster already mentioned that the example had a simple gradient as a background which would certainly compress well.
3. How CPU intensive is it to decode these things? Will MJPEG2000 (or whatever) practically require a hardware decoder for DVD-quality playback?
Anyone care to comment,refute, or otherwise flame? *g*
Seeing a story like this makes me wonder what the time lapse is going to be between the time a standard is issued and the time it can actually spead into wide usage. Look at PNG, which has been around for around 4 years now. Sure, some people can view PNGs in their browsers, but support is still imcomplete in most implementations despite its both technical and legal improvements on the ol' GIF format. Its still not to the point where a mainstream web site would want to use it for fear of shutting out some users.
Lets see here you need updated graphics programs (I'm sure GIMP and Photoshop, et al can have this fairly quickly). You need updated browsers (should be rather easy for Netscape/Mozilla, and technically not to difficult for IE, depending on whenever MS wants to get around to it). I'm still thinking 2 to 3 years before you seed wide usage, which is unfortunate becuase the big advantage is for those of us still stuck using lousy POTS lines to connect to the internet. Ironically, those who would get the biggest benefit from this (like be on this on-a-good-day 28.8 line) will probably have broadband access of one sort or another by the time it becomes widely used for the web at least.
Then again, the whole 28.8 to 56K changeover seemed to happen rather quickly and both required upgrading your hardware, and a dueling set of standards....
DrLunch.com The site that tells you what's for lunch!
The JPEG committee page has links to more information regarding this image format. http://www.jpeg.org/public/jpeglinks.htm
Listen to yourself. What future do you really want? A future run by corporations or a future run by people? I think the answer is pretty obvious, since corporations consist of people.
Fact is one of them has to lose over the other in the future. Corporations can't grow in power without abusing people, and people can't earn and live out their rights without lost revenue to corporations.
It's as simple as that.
In their eyes, the best way for corporations to earn money is to drug us down and make us their drones. Then they can do whatever they want of society. But what is really the point of that? So that a small elite can feel powerful and rich? There should be something else to life than that, and that means power and freedom to the individuals to do what their hearts desires.
In the future DVDs WILL be copied and pirated, since we're going to count storage in Tb instead of Gb. This could have a positive effect on the movie-bussiness, as they will have to come up with better answers to people's needs. Ie, bigger cinema screens, social aspects of movie-going, physical effects etc. The initiative-takers of this will be the ones who earn money from their ideas. Upstarts and copycats without one creative idea in their mind will as previously, not.
People that claim piracy are hurting corporations, forget what side is the most human. We don't live this life for corporations to grow on us. The more power you give them, the more numerous and bigger they get. So there have to be some resistance. Call it illegal. Call it perverted, or whatever you like, but I doubt it has ever hurt the bussiness as they claim it have. When they say that, they're thinking about quite a different reality than this one.
Think about that.
- Steeltoe
PS: This is not FUD, it's just to show the extreme that could happen if we suddenly just "gave up", stopped thinking for- and talking among ourselves. In some countries this has already happened, but with governments, which is much more probable.
http://www.debunkingskeptics.com/
DeCSS (or dodrip) + a nice little mpeg2 resizer will make you what's known as a "miniDVD". That's 352*480 mpeg2 with AC3 audio. You'll need 2 or maybe 3 discs for a complete DVD movie, with _really_ good quality. So far they're only playable in very few stand-alone DVD players, but on computers they work really well.
Dodrip (or DeCSS) + another little mpeg-manipulator will make you a VCD. Worse picture quality, and "only" Dolby Surround, but most movies fit on 2 discs, and are playable in consumer DVD players.
Dodrip (or any other ripper) + some Microsoft software will make you an ASF movie. Picture quality can be anywhere from terrible to better-than-VCD depending on bitrate, sound is good (Dolby Surround). Can be 1 to 2 cds for a whole movie, again depending on bitrate.
Who in their right mind actually takes the time to copy movies this way?
The ones living in countries where the cinemas lag 6 months behind the US. The solution is of course to release movies world-wide, both cinema-wise and DVD wise. That'll kill a LOT of the piracy.
it's in my head
We tried to license Intel's Wavelet compression used by RealNetworks and Microsoft in their video players (look for the "Optimized for Intel" logo), but when we disclosed that our player was a Java based solution, they quickly refused to let us work with them. It seems that no price could get us in the game; they gave us the feeling that it was more important to keep the technology firmly rooted to the hardware than to get a license fee from their IP. Not too much of a surprise, since Intel backed out of the consortium for the Java Media Framework API after v. 1. Too bad all the IP that IBM brought to the consortium didn't have a Wavelet tool kit...
Did wavelets a few years ago in uni, so I hope I've not screwed up my information in the few years lag, but another few points to add to this excellent summary:
1) It has been proved that a wavelets can represent the theoretical minimum information for an image. Proof uses the information's counterpart of the Heisenberg's Uncertainty Principle. That's right folks - you cannot get any more compressed than that - it simply isn't possible.
2) Unfortunately, finding the coefficients for the minimum possible representation is a bit hard on the computation side - so normally certain constraints are made like fixing the angles of the wavelet. However, decompression is pretty much standard in any case - easier. But nothing quite as close as FFT.
3) JPEG chops the picture into managable bits - you may get discontinuities at boundaries. Wavelets sweep across the picture, from big to small, gradually improving the quality at smaller areas. So you can get a nice smooth degradation of details if you decrease the size of the file - or in other words, if you are downloading incrementally, your picture kinda shimmers in nicely.
4) Wavelets have a normal like-curve. Normal like curves occur frequently in nature -- for example the human face can actually be represented by very few wavelets - the eyes, nose, mouth, face all fit quite nicely. Probably good for photos.
Here are some quotes from an article about JPEG2000:
Since August of 1998, a team within the Digital Imaging Group (DIG) has been developing a rich file format for JPEG 2000
It surely took a long time to develop it. I hope it's worth it.
Image authors will also have the option of saving the picture in lossless format for archival storage
This is great! It means I no longer need to keep all of these uncomressed BMP files lying around.
Wavelet technology also provides for a continuous download stream of data that allows the user to control the amount of image resolution desired
This is also great. If I understand it correctly, it will allow you to download 30% of the image and get 30% of the quality, download %50 and get 50% quality or download it all and get full quality. But I might be mistaken.
Another innovation is that a new standard, "sRGB" will be the default colorspace for this format. In the current JPEG standard, there is no notion of default colorspace. This lack of precision contributes to inconsistent JPEG color rendering
This is a Good Thing, too. Great for printing.
The JPEG 2000 standard for metadata also provides for extensibility of the metadata properties. In other words, new functionality can be added without having to rewrite the standard. And speaking of adding information, the metadata catalog can be modified without having to rewrite the entire image file. These abilities make for a very nimble, adaptable image file format
Well, we don't seem to need this (using different formats is easier). If the format is too extensible, it can lead to the "get-the-latest-viewer-you-moron!" syndrome, like all the problems with the HTML that we have now.
If all goes as planned, the official schedule for implementation will be released in January 2000
Other good links:
.j2k files for your viewing pleasure (I wish a had a viewer :-)
JPEG2000 Requirements and profiles document, V.6.0
SEMINAR ON IMAGING SECURITY AND JPEG2000 - this is an interesting collection of documents about digital image security and watermarking. These gyus take security seriously!
JPEG2000 bitstreams - actual
JPEG2000 Decoder (Version 2.3.1) - written in Java, the source is not available yet (it will be)
Barthel said this patented variable-sized window-scanning technique has been incorporated into the JPEG2000 committee draft. Besides LuraTech, Ricoh and several other committee members found bits and pieces of their patented technology in the spec. Barthel said all involved companies have signed agreements that give developers royalty-free rights to part one of JPEG2000.
The open source community should be very conserned about this issues. We don't want the LZW patent screw-up with the GIF format to happen again. There are two sollutions: either drop the patent (I don't know if this can be done, any lawyers?), or make sure that the software using it can be GPLed forever. The word "forever" is very important, so that we won't have any problems.
I believe that we should put enough pressure on this standart and make it really free. If the screenshots are real, it is definitely worth it.
By the way, I am not completely sure that this is real. Something like this usually pops up every second year, and usually it's fake. I remember reading about fractal compression, which was supposed to blow JPG away. It was in the early 90s, and obviously it didn't have much effect on the industry.
Such advances are really great for the IT industry and the commmunity. I can't wait for downloadable high qualit movies to become available. The next big thing after MP3 will be movies. Either pirated or commercial, movies will be available on the Internet. I can see all the big movie companies making movies available for download for a small charge (even if it's $3 or $5 I will gladly pay it, instead of spending hours looking for the same movie on some pirate site. The Internet will drop the marketing and distribution costs for most of the movies, and it will make it profitable to make the files available, even if the piracy level stays high.