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."
Maybe, but StuffIt is an archival program. If I have 10gb of existing jpgs and want to archive them, then this is whats wanted. Reencoding them as you suggest would be equivalent to converting say an mp3 to ogg format - a surefire way to lose quality with little gain.
Re fractal compression, people have been hyping it up for years but as far as I know it never really delivered. I'm dubious about any claims to some mysterious program which compresses anything amazingly well without strong evidence.
Wavelet compression however is used in jpeg2000 which is a bit better than jpeg but even that isn't supported by any digital cameras.
If StuffIt really does compress jpegs 25-30% that is a massive leap forward over the previous state-of-the-art compressors which reached I think around 3-4% - http://www.maximumcompression.com/data/jpg.php . Heres hoping their claims pan out, and that they release at least some details regarding the methods they used.
Interesting, never heard of Fractal image compression: http://netghost.narod.ru/gff/graphics/book/ch09_09 .htm
Fractal Basics
A fractal is a structure that is made up of similar forms and patterns that occur in many different sizes. The term fractal was first used by Benoit Mandelbrot to describe repeating patterns that he observed occurring in many different structures. These patterns appeared nearly identical in form at any size and occurred naturally in all things. Mandelbrot also discovered that these fractals could be described in mathematical terms and could be created using very small and finite algorithms and data.
Let's look at a real-world example. If you look at the surface of an object such as the floor currently beneath your feet, you will notice that there are many repeating patterns in its texture. The floor's surface may be wood, concrete, tile, carpet, or even dirt, but it still contains repeating patterns ranging in size from very small to very large.
If we make a copy of a small part of the floor's surface and compare it to every other part of the floor, we would find several areas that are nearly identical in appearance to our copy. If we change the copy slightly by scaling, rotating, or mirroring it, we can make it match even more parts of the floor. Once a match is found, we can then create a mathematical description of our copy, including any alterations we have made, and can store it, and the location of all of the parts of the floor it matches, as data.
If we repeat this process for the entire floor, we will end up with a set of mathematical equations called fractal codes that describe the entire surface of the floor in terms of its fractal properties. These mathematical equations can then be used to recreate an image of the entire floor.
etc...
Most existing DSLRs are at least this slow. They only seem faster because they have a frame buffer which can store 4-8 uncompressed images. The main cause of delay is writing out the images to the memory card rather than compressing the images. You can see this by looking at the flashy red light on the back of your EOS after you take 4 shots in sports mode... The camera is busy writing for several seconds after the last shot has been taken.
If the image compression algorithm was more efficient then there would be less data to write to the card and perhaps overall, it would actually be faster - even though the image compression algorithm might be slower.
For those mathematically interested fractal compression tries to find a matrix transform (A) so the serie x_n = A * x_{n - 1} converges where x is an image matrix and x_{\infty}=image to compress is a fixed point.
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
I beg your pardon? Just about every digital SLR on the market is able to handle more than 4 images in buffer at a time. My year and a half old 10D can buffer 9 RAW images, and the D70 processes JPEGs before they hit the buffer, so it can buffer JPEGs in the dozens.
I doubt this is intended for any use other than archiving of images, where it will kick ass. It's clearly processor-intensive from the timing results, but for long-term storage that makes little difference.
I've got a few TB of images in storage and I'd love to be able to save 20-30% of that space, regardless of how cheap it is. That means a little longer between burning DVDs, and having more stuff on mounted drives for reference.
Recursive: Adj. See Recursive.
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.
http://www.dpreview.com/reviews/canoneos1dmkii/
thats the fastest continuous shooting camera, you'll notice it has room for 40 JPEG frames in its buffer, and it shoots at 8.3 f/s
-ashot
> I'm dubious about any claims to some mysterious program
> which compresses anything amazingly well without strong evidence.
It's hardly mysterious. You can download trial versions and try it yourself - it's a well known compression technique that there are whole books about
There is near infinite evidence that it works so I don't know why you're doubting it. The issue isn't whether or not it works, it's why hasn't somebody made an opensource algorithm that we can all use.
The problem is that the existing fractal formats are all patented by companies that probably charge a fortune to license it.
JPEG does not use Run-length encoding as its last compression step. Quote from the faq:"The JPEG spec defines two different "back end" modules for the final output of compressed data: either Huffman coding or arithmetic coding is allowed." http://www.faqs.org/faqs/jpeg-faq/part1/section-18 .html
It goes on to say that arithmetic coding is ~10% smaller, but is patented, so don't use it.
So what they are doing is removing the known chubby huffman coding and replacing it.
IIRC the fractal format basically is done by taking a wavelet transform and then searching for IFS patterns in the tree and storing those instead of the actual leaf coefficients. However, putting in all the IFS junk just makes the math a lot harder to work with, is really quite slow, and does poorly on anything other than nature images (i.e., anything that is not visibly fractal). Simply pruning and coding the wavelet tree (e.g. jpeg2000) is a much more practical approach.
High frequencies are not exactly truncated. It just so happens that after quantisation, most of them drop to 0. If there are any outstanding high frequencies that are non-zero, it will not be truncated.
JPEG doesn't just rely on RLE, but rather it is a Huffman-RLE combination. Basically, for each element in the DCT block, JPEG will code the coefficient value together with the number of 0-coefficient elements after this, with the code taken from a Huffman table.
It has already been done. I use it all the time on OS X instead of TIFF.
http://www.jpeg.org/jpeg2000/
I really don't understand why the camera etc companies doesn't adopt it.
...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.
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/
What an idiot. He's posted almost word for word exactly what I said! Did you only read the first sentence?!
Me: The main cause of delay is writing out the images to the memory card rather than compressing the images.
You: What takes time, is writing to the memory card, not compressing the JPEG's.
etc etc....
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.
I don't know about Nikon, but Canon (Pro & Prosumer models) uses two buffers. Uncompressed are written to one buffer while the camera process them into JPEG on to the second buffer; where it's held until the image is written to the CompactFlash card.
Here ya go. If you trust the source...
Re fractal compression, people have been hyping it up for years but as far as I know it never really delivered. I'm dubious about any claims to some mysterious program which compresses anything amazingly well without strong evidence.
A program called Real Fractals has been in use by people who make very large blowups of images for years. It's pretty much standard practice to conver to Real Fractals before making a very big enlargement (like more than a few feet on a side).
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.
Whups, sorry, that's Genuine Fractals from LizardTech.
They are stored uncompressed in the frame buffer while it compresses them. The camera needs somewhere to store the RAW images while it's doing the compression. And yes, the frame buffers are fairly big. Usually 64mb + in a DSLR.
If the camera had to store the images in a small frame buffer designed for compressed images, then you wouldn't be able to save RAW images (or maybe only one - but that would make for a useless camera as they are 16mb + big and would take aaages to write out). So to me it was fairly obvious that the framebuffer was for RAW images.
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,
Nonsense, RMS has never said that. Please read a more widely before making such malicious accusations again. Don't buy into M$ marketing smear and FUD campaign.
---
It's wrong that an intellectual property creator should not be rewarded for their work.
It's equally wrong that an IP creator should be rewarded too many times for the one piece of work, for exactly the same reasons.
Reform IP law and stop the M$/RIAA abuse.
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.
I noticed the chart at the bottom of the whitepaper showed their "25-30%" figure was based on tests done on PNGs converted to JPGs at 50% quality. There is a lot of data degredation at 50% and I don't think many people regularly use anything below about 70%. I'd be much more interested in seeing what compression would be on a JPG straight out of a Digital Rebel or other camera set to highest JPG quality. They seem to have skirted that issue. They also don't explain why it doesn't work on PNGs. It makes me think the existance of the "noise" is what makes the compression possible.
I could be wrong, that's just the impression I get.
When will Windows be ready for the desktop?
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).
It certainly seems possible, except for patent issues.
The heart of JPG is the DCT transform, performed on an 8x8 block basis. This is not being changed, since they claim that the original JPG can be reconstructed bit-for-bit exact. Hence their algorithm must be "lossless." Othewise, if you apply lossy compression to lossy compression, you get even more loss.
Here is the JPEG algorithm in a nutshell...
1) Convert RGB into Brightness, Color, and Saturation (three separate monochrome images).
2) Down-sample the Color and Saturation images. (This reduces the image size by 1/2; VERY lossy but you don't notice it)
3) Break each image into 8x8 blocks.
4) Perform a 2D DCT (discrete cosine transform) on each 8x8 block separately.
5) Quantize the DCT data using the special JPEG quantizaion matrix (this is where most of the loss happens)
6) Convert each 8x8 block of DCT data into a 64-number stream using the zig-zag scan (this just shuffles the order of the data, nothing more).
7) Apply a specialiazed huffman code to compress the data (lossless compression).
8) Write the header information, and dump encoded data to the file
I could be waaaay off-base on this, but I suspect that they have found a better replacement for the zig-zag scan and huffman coding steps. Optimizing another step would still be lossy, and could not re-create the original JPEG byte-for-byte.
But I must admit that I am completely baffled how they could take a huffman code optimized for JPEG and find something 30% better. Such a thing seems to be impossible, given what I know of coding theory (which, I admit, is a but rusty).
"-1 Troll" is the apparently the same as "-1 I disagree with you."
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 =
This page has a lot of information on arithmetic coding. Very briefly, it's a way of using fractional bits to encode symbols - Huffman coding encodes each symbol to some integral number of bits (more bits for infrequent symbols, fewer bits for common symbols); arithmetic coding does the same, but each symbol can map to a non-integral number of bits; you save a fraction of a bit per symbol, which can really add up. It's not easy at first to see how this works, but the math works out.
Arithmetic coding has another advantage over Huffman coding: with Huffman coding, you first collect symbol frequency information, then you build your coding table based on that frequency information. You then have to somehow encode the coding table in your bitstream (so the decoder knows how to decode the symbols). The coding table is based on an average over (often) the whole file, so it can't adapt to changes in the symbol frequencies: if one part of the file contains just numbers, and the other part contains just letters, their statistics get mixed together so you end up with a Huffman coding table that's not optimal for either part. Adaptive Huffman coding (changing the codewords as you encode the file, based on changing statistics) is possible but painful. On the other hand, adaptive arithmetic coding is very very easy.
1) Convert RGB into Luminace (Y) and two color difference channels (Cr and Cb).
Fixed.
2) Down-sample the Color and Saturation images. (This reduces the image size by 1/2; VERY lossy but you don't notice it)
Actually, Hue and Saturation reduction leaves very noticable artifacts.
The compression that you have spoken about is known known as MrSID, from LizardTech. It is used mostly for GIS applications, as far as I know.