Encoding JPEG Images Losslessly: A Surprising Result

Joshua McGee Blog posts 2 comments

We all know that JPEG is a “lossy” image format: when you save a bitmap as a JPEG, you end up with an image that is subtly different from the original. This is why you always want to do your image editing work with raw bitmaps (perhaps saving intermediate files in something like PNG or GIF, which are pixel-for-pixel copies of the bitmap but use less space.)

Reliable sites around the Internet will tell you this exact thing. Here is a sampling (pages retrieved 2013-06-01):

OK. So, quick: what do these images have in common?

Answer: Each of these JPEG files, at a quality setting of 85, is pixel-for-pixel the same as its source BMP.

Skeptical? Save one of the above images as in.jpg and try this with ImageMagick (basically the best software package in the whole world, and totally free):

convert in.jpg out.bmp
convert out.bmp -quality 85 out.jpg
compare -verbose -metric mae in.jpg out.bmp /dev/null
compare -verbose -metric mae out.bmp out.jpg /dev/null

You will get this (in version 6.8.0-10 2013-03-03):

in.jpg JPEG 240x170 240x170+0+0 8-bit DirectClass 13.9KB 0.000u 0:00.000
out.bmp BMP 240x170 240x170+0+0 8-bit DirectClass 123KB 0.000u 0:00.000
Image: in.jpg
  Channel distortion: MAE
    red: 0 (0)
    green: 0 (0)
    blue: 0 (0)
    all: 0 (0)
in.jpg=>/dev/null JPEG 240x170 240x170+0+0 8-bit DirectClass 0.130u 0:00.019

out.bmp BMP 240x170 240x170+0+0 8-bit DirectClass 123KB 0.000u 0:00.000
out.jpg JPEG 240x170 240x170+0+0 8-bit DirectClass 13.9KB 0.000u 0:00.000
Image: out.bmp
  Channel distortion: MAE
    red: 0 (0)
    green: 0 (0)
    blue: 0 (0)
    all: 0 (0)
out.bmp=>/dev/null BMP 240x170 240x170+0+0 8-bit DirectClass 0.060u 0:00.019

The analysis above tells you the error in each color channel — how much the two images differ. There is no difference. The images are exactly the same on the pixel level, according to ImageMagick, and round-trip in and out of BMP with no loss of fidelity. Therefore, the strongest statement that can be made is that JPEG is “typically lossy”.

I generated the above images accidentally. I was exploring the JPEG format, and wanted to figure out how much an image degrades over a ridiculously large number of saves. I wrote a tiny shell script that would take a JPEG, convert it to a bitmap, and export it as a JPEG (at a given quality setting; I used 85, which is OK-but-not-great), then delete the intermediate file to save disk space. I let the script run on the image 10,000 times and visually compared the first and last images, expecting a smeary blur. In actuality, there was very little loss of image quality.

I changed the script so that it didn’t delete the intermediate image every hundredth iteration, and saw that every intermediate image has exactly the same size in bytes. Huh? That is very unlikely, mathematically. So I used the compare program and saw that, while the 100th iteration was indeed different from the 0th, the 100th was the same as the 200th, which was the same as the 300th, which was the same as the 10,000th.

I changed the script again so that it ran for only 100 iterations and saved every intermediate image, and was startled by how quickly the file sizes stabilized. In the vast majority of cases, if you save a JPEG as a bitmap and save it back to a JPEG, the conversion stops being lossy after fewer than 50 iterations, but there are exceptions:

    Took 9 iterations
    Took 17 iterations
    Took 6 iterations
    Took 202 iterations

So, I wrote a new script. This script takes an image and iterates until it finds a stable image — one that can be converted to and from a bitmap without any pixel differences:

#!/bin/bash

i=0
inb=$(printf '%s_%05d.bmp' $1 $i)
convert $1 $inb

if [ $2 ]; then
  QUALITY=$2
else
  QUALITY=85
fi

ITERATIONS=1000

until (( "$i" > "$ITERATIONS" )); do
  # echo "Processing $i..."
  let j=i+1
  inb=$(printf '%s_%05d.bmp' $1 $i)
  inj=$(printf '%s_%05d.jpg' $1 $i)
  outb=$(printf '%s_%05d.bmp' $1 $j)
  outj=$(printf '%s_%05d.jpg' $1 $j)
  convert $inb -quality $QUALITY $outj
  convert $outj $outb
  E=`diff $inb $outb`
  
  if [ "$E" = "" ];
  then
    echo "*** Iteration $i produces a perfect JPEG at quality $QUALITY"
    echo "*** Comparison:"
    outfile=$(printf '%s-iteration-%d' $1 $i)
    cp $outb $outfile.bmp
    cp $outj $outfile.jpg
    compare -verbose -metric mae $outfile.bmp $outfile.jpg /dev/null
    echo "*** Images saved as $outfile.bmp and $outfile.jpg"
    rm $1_*
    exit;
  fi
  let i=i+1
done
echo "Stable image was not found after $ITERATIONS iterations"

Curiously, the “stable” pair is different for different versions of ImageMagick. I used 6.8.0-10 2013-03-03, because it’s the newest as of this writing, but 6.7.7-10 2012-08-17 yields a different stable pair of bitmap and JPEG; there is a difference between the outputs of one and the outputs of the other. Could some/all of this be ImageMagick artifacts? Could it just be a difference in how the “quality” setting is implemented?

There is much room left to explore. How does the quality setting affect convergence speed? Are there any source images that never converge? Why does this convergence script work in the first place? I’m fascinated, and need to do more research. Feel free to play with the script, and if you find any interesting images (ones that don’t converge, ones that take an exceedingly long time to converge, etc.) please upload them somewhere and paste the link.

Edit 1: Received this comment on Google Plus:

He’s not comparing the final JPEG with the original image though. He’s starting with a JPEG, converting that to a BMP, and then from the BMP back to a JPEG. That BMP has already lost any fine grained detail that would be lost by JPEG compression.

Whilst I’m somewhat surprised, I’m no where near as surprised as if he’d started with a complex image that hadn’t already been through the compression process.

This is a good point. So at his suggestion, I generated this complex bitmap in a graphics editor (converted here to a lossless PNG for browser support):

It took 22 iterations to converge to this:

This is well in the range of starting with a JPEG.

Edit 2, also from Google Plus:

When you convert [a photo], a JPEG compression algorithm will partition it into many smaller squares and fourier transform those to frequency spectra. Then, having the frequency spectra of these, the algorithm can just null all frequencies out, which are very small anyway. (So you won’t notice after fourier transforming this back) The threshold for nulling out depends on the quality you chose. In the next step, the resulting sparse spectra will be saved in a compact format. There you have your compression.

This means that JPEG is indeed per definition a lossy format. However, you will not experience quality loss, if you convert pictures which have simple content. This is because the fourier transforms of all its subsquares will be very “digital” from the beginning, so there’s not much to null out.

And if you convert “complicated” pictures very often, they will end up in a format where your JPEG algorithm doesn’t find any possibilities to further compress it while staying at the quality level you chose.

“lossy” means, that IF your JPEG algorithm achieves size reduction of the source image, it will INEVITABLY reduce its quality. Same size <-> same quality.

This precise definition of “lossy” was very helpful; clearly I was using the term imprecisely. What fascinated me was that, contrary to popular wisdom, there was not inevitable decay in image quality. Understanding the compression mechanism clarifies this.