Slashdot Mirror
Breakthrough In JPEG Compression
Kris_J writes "The makers of the (classic) compression package Stuffit have written a program that can compress JPGs by roughly 30%. This isn't the raw image to JPG compression, this is lossless compression applied to the JPG file. Typical compression rates for JPGs are 2% to -1%. If you read the whitepaper (PDF), they are even proposing a new image format; StuffIt Image Format (SIF). Now I just need someone to write a SIF compressor for my old Kodak DC260."
I would have thought that rather than 'zipping' an existing image format to create a new one just to save 30%, they'd be better off improving the original image compression algorithm or coming up with a new one.
Quite a while ago (years!) I had a program which could compress images into a fractal image format. It was amazing - the files were much smaller than JPEGs but looked a lot better. The only drawback was that it took ages to compress the images. But with the extra CPU horsepower we have today I'm surprised fractal image compression hasn't become more prevailant. It would still probably be useless for digital cameras though as it would probably be impossible to implement the compression in hardware/firmware such that it could compress a 6+ megapixel image within the requisit 1-2 seconds.
Does anyone know what happened to fractal image format files (.fif) and why they never took off?
The linked page shows average decompression times of 6-8 seconds for 600-800 KB files, rising with the size of the file. Who would benefit from this? It's obviously too slow to speed up web pages, and would be far too CPU intensive for consumer cameras. Professional photographers would have no use for this since they would use RAW images.
I mean, it's cool and all to be able to compress JPGs by that much more, but the size gains are negated by the time it takes to decompress them. This seems just like those super high compression algorithms that have rather amazing compression rates, but take -forever- to compress or decompress, making them unusable. The difference is those are obviously and labeled as simply for scientific research into compression, but Aladdin seems to be trying to market this product for public consumption. The listed uses ( http://www.stuffit.com/imagecompression/ ) seem trivial at best.
Who's gonna be buying this?
-Cliff Spradlin
I just installed an 800Gb hard disk in my system. I have a gigabyte worth of webmail space (more than that, if you consider that I can send myself gmail invitations). Storage is, as they say in the vernacular, very inexpensive.
Even in cameras where storage is tight, the bounds of memory is expanding all the time. Whereas a couple years ago the average storage card size was a measly 64Mb, today we are talking about gigabytes of storage memory inside our *cameras*!
So let's say we can squeeze another 30% of pictures onto a card. Does that really help us? Not really, if you consider that the compression itself rides atop JPEG compression and that computing time needs to be accounted for.
Currently, the fastest continuous shooting digital camera (the Nikon D2X) can only take 4 shots in a row before its memory buffers get full and the whole camera becomes useless. Compare that with the 9 shots per second F5 and you can see that the speed of shooting isn't going to cut it for digital cameras.
We need a compression method that is lossless, not one that creates compact files. Space is cheap, CPU cycles aren't.
The linked page did not answer some of my questions:
1. Does this only work for JPEG, or also for other (compressed or plain) files?
2a. If it only works for JPEG, why?
2b. If it works for others, how well?
Anybody who can answer these?
Please correct me if I got my facts wrong.
they are even proposing a new image format; StuffIt Image Format (SIF).
Gee, I wonder where you could license that format?
Man, they could have been a little bit more covert about their intentions and named it something a little less, umm, obvious.
The current formats might not be perfect, but at least they are (relativly) free.
"The Wright brothers were the first to fly with a heavier-than-air machine, but boy did they have a lousy plane"
Stuffit repackages its expensive compression software every year (it seems). Now I would be happy to admit my mistake, but their main area of expertise seems to be marketing. Not technology. I reckon JPEG2000 or any number of other newer-than-JPEG formats already exceed whatever Stuffit purports to have accomplished. I suspect they are trying to tie their name to JPEG as a marketing gimmick to win hearts and minds. I doubt this is worth a mention on Slashdot.
We don't need any new standards unless they actually offer an improvement over recent technology. In technology years, JPEG is very old. A replacement for it should do better than 30% and offer other advantages. I suspect a company that actually specializes in imaging might have come up with a better solution a while ago.
Would this technique apply to DV video?
If you read the whitepaper you will see that their algorithm is patent pending. The patent will almost certainly be granted, and, since no one else has done additional jpg compression before, it may even be deserved.
However, do we want to subject ourselves to a new tax on images? If they make it, we don't have to go! Just say NO to patented file formats!
I have a friend who's father is a professional photographer. He has gigabytes and gigabytes of images stored for his customers, should they want to order re-prints. They're thinking about setting up raid terabyte file server. I can certainyl say that this is good news for them!
Electrons are free; it is moving them that becomes expensive.
JPEG is (roughly) a discrete cosine transform, followed by a filter on high frequencies, followed by Huffmann encoding (which is lossless). This is probably the Huffmann encoding that they did remove and replace with one of the more efficient compression algorithms, and something that could indeed be much more efficient than simple huffmann encoding. So they still take advantage of all the strengths of JPEG related to the human perception model, but they still gain in compression. Huffmann is great to compress oft-appearing sequences, and is a great general-purpose lossless encoding, but there are other that do a better job of it.
In other words, you did not understand what they did.
Okay, I do a bit of metalurgical crystalline micrography, and we keep the images in the raw bitmap format because we can't let ANY data be lost. But we also have gobs of drive space, so a good lossless, non-distorting compression format would be handy.
Bacardi + slashdot = negative karma.
An image compression comparison with no lenna? What's the world coming to?
I am trolling
The linked page shows average decompression times of 6-8 seconds for 600-800 KB files, rising with the size of the file. Who would benefit from this?
Any websites with the primary purpose of hosting images would benefit greatly from this - such as art & photography sites. (Yes, and porn sites, too.)
Why? Because 99% of the traffic they generate is for their images. Of those images, 99% of them are in JPEG format. So this compression would give a good savings in bandwidth on all those pictures.
At large sites, a 30% cut in required bandwidth could mean a very large savings. Now, if they can take a large cut off their operating expenses, and all they need to do that is to make the users wait a few extra seconds for their pictures, I think we know what they'll do.
As for the decompression time, one thing to remember is that with how slow internet connections are (even broadband), you're much more likely to be waiting for one of these images to transfer than you are to be waiting for it to decompress (so long as it allows you to start the decompression without waiting for the end of the file, of course).
--The Rizz
"Man will never be free until the last king is strangled with the entrails of the last priest." -Denis Diderot
I thought they had found a method to further compress a JPEG, while still maintaining the original format. i.e. it could still be viewed with a regular JPG viewer. That kind of optimization would've been great, especially if it could be used on webpages, forums etc.
But this is somewhat disappointing. The compression changes the format, and it must be decompressed to view it. Plus they don't intend on releasing the format, and their proposal for a new filetype which can be read by a "plugin" reeks of incompatibility issues.
StrayByte.Net
afaik, tar does not compress files, it just packages a lot of files into a single 'tarball'. thats why you'd have somefile.tar.gz - the tarball isnt compressed, so it has to be compressed by another utility like gzip.
If they've really achieved 25-30% over jpg, and it looks like they have, then its a truly amazing invention considering that jpeg has been around for so long. It would save at least about ten dollars worth of space on every digital camera. If you look at the humongous image archives that NASA and other research projects generate and the cost of tape to store them all, we're talking tens of billions of dollars of savings here.
So, a question to slashdotters: do you think this kind of invention deserves to be protected by a patent? The standard response "software is already protected by copyright, patents are unnecessary" doesn't work, because anyone can study the code (even the binary will do), describe the algorithm to someone else, who can then reimplement it. Standard cleanroom process; takes only a couple of days for a competent team.
If you're RMS, you probably believe that no one has the right to own anything and all inventions and ideas belong to the public, but the majority of us will agree that that's a tad extreme. So whaddya'll think? Myself, I'm totally undecided.
This is not in competition with JPEG - more with LZW compressed TIFF.
.x% range, yet they've apparently improved by a factor of around 6x what the previous best programs were able to achieve. I should note that I developed the audio codec with the currently highest lossless audio compression - http://lossless-audio.com/ - so have some idea of what I'm talking about here.
You're misreading the whitepaper. What they're explaining here is different and actually quite clever.
Jpeg compression can be seen as consisting of two main steps. In the first, information in the image deemed unimportant is removed from the image. In the second, the remaining information is compressed losslessly.
It was already known that the second step is not the most efficient possible. Also, the jpeg standard supports both huffman and arithmetic-coding, however due to patent reasons I think arithmetic-coding (which is more efficient) is often not used. So what they're doing is just improving the efficiency of this second step. This works much better than attempting to encode the jpg binary itself, as anything performed following entropy coding will struggle to achieve much compression, as the data has been hugely complicated by the process and it is thus much harder to find any compressible patterns etc.
They've also improved the compression by a very impressive margin. Typically in the lossless compression world, gains are in the
Anyway, the end effect is the same regardless how the compression is achieved - they're taking a lossily-compressed jpg, and reducing its size. This obviously makes little sense to be say integrated into digital cameras, for which the jpeg2000 format is available anyway and features better gains and is much faster (yet is still awaiting mainstream adoption), however from the archival and theoretical-lossless-compression perspectives what they've allegedly achieved is pretty damn interesting.
The quantised DCT coefficients of a JPEG image are compressed using a JPEG standard huffman table. From what I've seen, this table is far from optimized even for "the average of the majority" of images out there.
Ogg Vorbis stores its own huffman table in its own stream. The default encoder uses a table optimized for the general audio you can find out there. There is a utility called "rehuff" (goggle it yourself please) that will calculate and build a huffman table optimized for a particular stream and it seems that on average it reduces an Ogg Vorbis filesize by about 5-10%.
Building an optimized huffman table for individual JPEGs will probably yield such improved compression rates too. If the original JPEG tables are less optimized than the Ogg Vorbis ones, the reduction will be even higher. But 30% seems a little... optimistic.
To be honest i don't care about the 30% compression if there's the slightest danger that anyone might start a patent-war over the image-format or the compression algorithm.
I've really seen enough of that (gif, mp3, jpeg) and i prefer spending the additional storage/bandwith capacity to another uppity "IP-shop" coming out to "0wn0rz" the internet with lawyering (maybe after a management-change).
Let's have another look at that compression algorithm in 20 years or so.
"By the way if anyone here is in advertising or marketing... kill yourself." -- Bill Hicks
I wont bother going into the details of how it works (go read 'Fractal Image Compression' by Yuval Fisher*) but I concluded that fractal compression wasnt viable as there wasnt a general solution to suit all images. There are about 20 variables that you can decide, which give variable results to the final compressed image.
And one set of variables would be excellent to compressing pics of trees down 80%, another set of variables would be excellent compressing pics of animals down 80%, but using each others set would only give results equal or worse than normal compression algorithms.
Another factor at the time, five years ago, was that it took an hour to compress a 256x256 greyscale image on a 300MHz machine. Nowadays that isnt a factor.
* If anyone has this on ebook please post a link here, Im dying to read this again.
Okay, so as near as I can figure out, this is a white paper because: .SIF as basically being having everything a jpg does except higher compression.
.sif : bandwidth savings will actually be on the order of 98% (30% image size reduction, 97% website traffic savings).
It describes a new format
Some might think it's a press release, since the "White Paper"'s discussion of the new format is largely limited to the benefits "OEMs" will have in using this (soon-to-be patented) technology, and explaining how it integrates into Allume's fine line of existence and future Digital Lifestyle(tm) products.
Some might further argue that often press releases will accompany white papers, explain the point for the consuming world, and link to the paper; this "white paper" seems to do exactly that: we are invited to examine a (currently 404'd) page to see the actual data involved.
To those who think it's a press release, it's not, because:
It don't say "For Immediate Release"
Press releases are proofread for grammatical errors, and working links capable of withstanding slashdot-class bandwidth
And by the way, they don't have a chance. Sure, bandwidth cost means a lot, but for the OEM who might consider adopting this technology, it means a new standard that offers at best 30% improvement (on those little 50kb jpegs we're asked to believe), paying for it, and passing the cost on to the consumer. It may be an improvement, but if you really want to improve your image-heavy website's bandwidth usage, switch to Fractal Image Format. Not only do you reduce the size of the images; you reduce the number of people downloading them. The same for
I worked in this field for awhile, and the liscencing and other issues sent the company I was with running in the other direction. JPEG was good enough, everyone was using it, so JPEG it was.
Fractal compression is cool.. but encumbered by IP issues. Too bad.
..don't panic
Given that the software is likely to be proprietary and the algorithm will be patented, it becomes completely useless to me and it is completely unsuitable for archiving anything (smart people don't play nickel and dime games with archives and backups).
Maybe if computers were a lot faster and the compression worked on any array of pixels, not just those that have undergone the lossy transformation of JPEG compression. But even then, it would have to do better than what PNG can do in terms of all the other things PNG does and no patented format will beat PNG at its game.
In theory what you say sounds nice, but in practice I genuinely can't recall a situation where a little more compression would have allowed me to send all the photos I wanted to via e-mail. But the reasons I mentioned at the top of this post are more important reasons why this should be rejected out of hand.
What meager benefits this affords are far outweighed by the costs. I don't see this going anywhere, and for very good reason.
Digital Citizen
" Typical compression rates for JPGs are 2% to -1%. "
Does -1% mean that the file actually gets bigger?
Big Deal. With broadband ever expanding and storage being relatively cheap and inexpensive, this technology is a waste of time. Hell, I've got a $100 USB drive for X-mas that was a gig...a fucking gig.
With lossless wavelet compression. That's what I'm still waiting for. As the "2000" indicates it's nothing terribly new but as of yet still misses a big rollout. Yet I'd rather have such a new format than taking an old format with known limitations and adding another layer of crud to get sizes further down.
...its IP status is currently ambiguous. jpeg2000 is currently being attacked by some patent holders and until it's all settled nobody is going to touch it.
If this idea is what's suggested here, ie. instead of
Image -> DCT -> Truncate spectrum -> RLE encode
they use
Image -> DCT -> Truncate spectrum -> some more efficient encode
it wouldn't surprise me if the JPEG Group discussed alternate compression encodings during the standardisation meetings. In fact, I'd be extremely surprised if the matter was not raised. If it was, it's pretty clear that this patent is not novel in the slightest...
Athletic Scholarships to universities make as much sense as academic scholarships to sports teams.
The JPEG standard specifies 2 entropy coding methods; Huffman coding and arithmic coding. As arithmic coding is patented it is not in use. The patents for this arithmic coding called Q-coding http://www.research.ibm.com/journal/rd/426/mitchel l.html are in hands of IBM.
Perhaps they will allow OSS to use this patent along with the 500 other patents recently allowed?
http://www.ibm.com/ibm/licensing/patents/pledgedpa tents.pdf
The particular variant of arithmetic coding specified by the JPEG standard is called Q-coding. This variant has the advantage of not requiring any multiplications in the inner loop. Q-coding was invented a few years ago at IBM, and IBM has obtained patents on the algorithm. Thus, in order to use the JPEG arithmetic coding process, you must obtain a license from IBM. It appears that AT&T and Mitsubishi may also hold relevant patents.
wikipedia
http://en.wikipedia.org/wiki/Fractal_compression
Some sourceforge projects
http://sourceforge.net/projects/mpdslow/
http://sourceforge.net/projects/fractcompr/
for audio
http://sourceforge.net/projects/fraucomp/
It's JPEG, not JPG. JPG is the file extension used for JPEG files on DOS systems because of 3 character file-extension limitation. JPEG is the name of the format/compression and the extension (which should be) used on systems that support 3+ character file-extensions. Because of the internet the JPG extension has spread and now people ignorantly use JPG to even refer to the format/compression.
The original JPEG compression algorithm had Huffmann coding for the DCT variables, but it also had some fixed-length codes for the beginning and end of blocks. If you set your compression at about 10x then you can hardly see the difference with real images. bring it up to 15x and the changes are still modest. However, yank it much over about 22x, and the image will go to hell. The reason is the block handling codes meant that a JPEG image with no data at all - a flat tint - would only compress at about 64x, so at 22x compression these block handling codes are about 1/3 of your overall code. The fractional bit wastage you get with using Huffmannn coding instead of arithmetic coding mops up some of the rest as you are usig shorter Huffmann codes. The codes are also very regular, as about 1/3 of the code is not particularly random. The 1/3 figure also matches the 30% compression figures too, which isn't surprising.
Why didn't the original JPEG developers make a better job of this? Well, doing an experimental DCT compression used to take me hours or days when I was developing on a shared PDP-11, and there was always the worry that a dropped bit would lose your place in the code, and scramble the rest of the image. A little regular overhead was also useful for things like progressive JPEG control. I guess we all knew it was not as tight as things could have been, but it got the job done. We knew if you want to get 40x compression, then reducing your image to half size, and the compressing that by x10 will look better. Unfortunately, people who just drag a slider to get more compression don't always know that.
The right solution would be to use JPEG2000 which has a much smaller block overhead, and so fails much more gracefully at higher compressions.
You know what ? The breakthrough in JPEG compression was mainly JPEG-2000.
There had been, was, and has been possible to achieve better compression ratios, and guess what, even in the high times of JPEG we knew that what's inside, it's not the optimal solution. But there were certain aspects which made it stay the way it was, and that was good to be so. The same goes with JPEG-2000. Since the appearance of it there have been many attempts to make it better, and there have been some good results achieved (even I have read and sometimes even reviewed papers dealing with the subject).
It's really no question whether one can make an X% better compression to JPEG with the same quality (expecially today, when JPEG is so old that every joe and his dog had time to develop better ways). The question is, has it enough practical usability to justify its presence ? Is there a well-justified reason why we should use it ? Does it deliver
- better compression rates (smaller size with the same objective & subjective quality) ?
- lower compression times ?
- compatibility ?
- is it any better for hardware implementation purposes (same or lower computation times) ?
If it's just a "better" compression for the compression's own sake and not for our sakes, then this is even less news than me cleaning my room.
I am putting myself to the fullest possible use, which is all I can think that any conscious entity can ever hope to do.
is because it is a way to compress (some types of) file that are ALREADY compressed. If you've ever zip'd (or RAR's or 7Zip'd or Gzip'd etc) a jpeg, a gif, a png or even another zip file - ie. any other type of already compressed file - you'll be lucky to get any savings, or if you do it will be a few % at most. That's because most of the redundancy (ie. compressibility) has already been removed from the data in the file.
This method can compress jpg files significantly, and that is NEW, in fact it was previously though to be something that was more or less impossible (or at least, extremely difficult with little to gain).
Of course it is slow, but it works and it will find practical uses.
I'm a perfectionist but I'm trying to cut back.
Since the context was photography I should have said "true professional photographers
don't use jpeg to shoot their photos"After you have corrected the exposure, corrected the white balance, etc... and you are ready to throw away 12 bits per pixel of information... yes... jpeg may become useful.
The fact that many people doesn't care about 12 bits per pixel of information, about postprocessing degradation and so on, doesn't imply that it is good.
well rle coding (combined with huffman or whatever) would if anything make most audio files bigger. because audio is typically 16-bit (vs 8-bit for images) theres very little chance two concurrent values will be the same. my codec does use internally for the entropy part something based on range coding, which is similar to, but a little more efficient than, huffman coding, but it does a lot of other stuff as part of the entropy coding as well.
the point about stuffit's improvement is that its so huge. sure huffman is inefficient, but other methods are nowhere near 28% better i can assure you (else other state-of-the-art lossless archivers would have done better than the 4% they achieve before now).
So now I get the picture, only smaller!
After my experience there, can I expect to be led through a complicated and deceptive trick into downloading the trial version of some overpriced software, where I'm required to give up my email address, and the whole thing never works anyway? Stuffit might have great technology, but any company that wants to provide a proprietary format for anything will only be useful if *anyone* can open the format. Adobe knows that. And trying desperately to hook into people who *have* to turn to you to uncompress things and sell them things they most likely don't need isn't useful. It will just make StuffIt (.sit files) useless to people who *are* paying customers, because it's such a hassle for people to open the files.
samrolken
They have another imaging technology that they purchased from AT&T called DjVu. They've Open Sourced the viewer for that technology under the GPL.
I believe an encoder/decoder is also available under a GPL license, though LizardTech doesn't appear to be happy with the GPL because they are pro software patents, and the GPL is not. The encoder/decoder may or may not be a fractal engine, someone more knowledgeable will have to answer that question.
LizardTech may be involved in a squable over the JPEG2000 technology. Something to do with patent litigation.
= 9J =
As another person who has implemented JPEG, I vouch for his accuracy :-)
It is this last step which is not particularly efficient. There are several reasons why ZIP cannot significantly compress this data. First, ZIP is a byte-oriented compressor. Huffman codes are bit-oriented. This causes ZIP to miss many patterns that could be backreferenced simply because they fall on a weird bit position. Second, data can be highly compressible and yet have no repetitive patterns in it.
For example, consider the sequence 1,2,3,4,5,6,7,8,9,10,...,1000. It has no repeating pattern, but it would be absurd to claim that it cannot be compressed. In this case, applying the simple transform x[i] --> x[i+1] - x[i] transforms the sequence to all zeros, and that is trivially compressible. To decompress, just apply the inverse transform.
ZIP is too naive to use any sort of transforms. It really was only intended for textual data, program executables, etc.