Hi and welcome to the last two modules in
module eight, where we will talk about the
JPEG compression standard.
As we said before, an image stored in raw
format occupies a lot of space.
Normally, a color picture will use 24 bits
per pixels and there a lot of pixels in an
image produced by a camera today.
By contrast, an image encoded with the
JPEG standard will be encoded at
approximately 2 bits per pixel and it will
be very hard to tell the difference
between the two.
So how does this magic happen?
Jpegs achieve this remarkable result by
combining three fundamental lines of
attack.
The first one is called transform coding
and it means that we actually encode the
image in the Fourier domain rather than
the space domain.
The second is variable quantization.
We allocate a different number of bits to
different parts of the image, and this is
based on psycho-visual test that have been
carried out to determine what is important
to the eye and what is not.
And the third ingredient is called entropy
coding and it is a technique from
information theory that allows us to
shrink the size of the bit stream,
encoding the image even more.
Hi, and welcome to module 8.5 in which we
will talk about image compression.
We will review the reason why we can
compress images, namely the redundancy
that is present in natural images And
then, we will look at the fundamental
ingredients in an image coding system.
But first, let's start with a very simple
thought experiment that will convince you
that image compression is a necessity.
Consider an image of size 256 x 256,
encoded at 8 bits per pixel.
That amount of storage that an image like
that requires is on the order of 500,000
bits.
Now, from a purely combinatorial point of
view, each bit in this image can be set
independently to 0 or to 1.
So the total number of possible images of
size 256 x 256 at 8 bits per pixel, is a
staggering 2 to the power of 524,288.
To put that in perspective, we can change
the base and express this as 10 to the
power of 157, 000 and something.
Now compare this to the number of atoms in
the universe, which is estimated to be 10
to the power of 82.
This means that clearly, the subset of
meaningful images of size 256 x 256, must
be very, very, very small, compared to the
number of all possible images.
Let's take a different approach.
Assume that we can actually collect all
the images that exist in the world,
pictures, drawings and so on, so forth.
And suppose that we can list them in a
massive encyclopedia of images.
Now that we have a list and a catelog of
all possible images we can indicate each
image in the encyclopedia just be giving
the cardinal number in the list.
Now to put some numbers in this thought
experiment, let's do this very simple back
of the envelope calculation.
Current estimates say that on the internet
we have about 50 billion images and
pictures that are floating around.
Let us assume to simplify matters that all
of these images are encoded at 8 bits per
pixel and they have size 256 times 256.
Well, each of these images encoded in raw
format requires in excess of 500,000 bits.
If we use the enumeration scheme from the
encyclopedia of the image where we can
identify each image by its index, we just
need to provide this number to specify an
image.
And therefore, the cost to encode an image
is simply the log in base 2 of the number
of images in the list.
So that's about 33 bits per image to
encode.
All possible images in the internet today.
The downside to this encoding scheme is
that it requires a lot of side
information, in other words I can send an
image to you by sending you its index
number but unless you have the full
encyclopedia at your disposal you won't be
able to see the image itself.
So on the one hand we have an indication
that there is an enormous redundancy in
the amount of space that we allocate to an
image.
And on the other hand, we have a sort of
lower bound that tells us that the number
of images that make sense in theory, could
be encoded with approximately 30 bits per
image.
Neither approach gives us a solution to
the problem.
So we need to analyze the physical
properties of images in more detail.
The idea is to exploit the physical
redundancy in images to reduce the bit
budget, but of course we have to be
careful and define redundancy specifically
in terms of the human visual system.
In order to allocate bits to features that
matter, we have to find out what this
features are and thankfully researchers
have worked a lot on this on this problem
and ran lots of pyschovisual experiments
to find out things that matter the most.
With this knowledge at hand, we can go
ahead and define what is called a lossy
compression scheme.
In other words, an imaging coding system
that will discard the information that it
deems irrelevent with respect to either
the intelligibility or quality of an
image.
So let's look at the key ingredients that
will lead us to the JPEG compression
scheme.
The first is compressing the image at
block level.
We'll see this with an example in just a
second.
The second ingredient is using the
suitable transform to move the blocks into
a different domain.
So we do a change of bases that will make
it easier for us to decide which parts to
keep, and which parts to discard.
Smart quantization is the way we will go
about discarding irrelevant parts.
By allocating very few or no bits at all
to some of the transform coefficients, we
will be able to reduce the bit rate
selectively.
And finally, entropy coding is a technique
that we will borrow from information
theory.
And it will allow us to compress even more
the bit stream that we have obtained form
the previous smart quantization.
To understand the importance of block
coding, let's see what we can do if we
decide to compress an image at pixel
level.
The only thing we can do in that case is
to reduce the number of bits that we
allocate to each pixel.
This is equivalent to quantizing the image
using fewer levels and in the limit we can
not got below one bit per pixel.
So if we try and apply this to our center
image we get something that has completely
distorted the content of the original
image.
So pixel level quantization only takes us
so far before image quality is completely
compromised.
Now by comparison, let's look at a very
simple compression strategy that operates
at block level.
What we do here, is we divide the image
into blocks.
And then we code the average value with
eight bits.
We use 3 x 3 pixel blocks using eight bits
for each block.
So, we use a little bit less than one bit
per pixel, and the result is what you see
here on the right.
If you look attentively at the details,
you might perceive some jagged edges
around, for instance, here.
These are the so-called, block artifacts
and come from the fact that we have split
the image into small blocks.
But, nonetheless, the overall result is
definitely much, much better than what we
would obtain using pixel level compression
at the same bit rate.
The power of block level compression comes
from the fact that in each block we
exploit the local correlation between
neighboring pixels and at the same time,
since blocks are independent, we separate
the coding for different parts of the
image.
The block scheme we've seen just before is
a very simple naive one.
We just take the average value of the
pixel.
And the result is that we have noticeable
block artifacts even though our blocks are
very, very small, three by three.
Can we do better?
Well in order to do better we have to
introduce the second ingredient which is
transform coding.
To give you an idea of how transform
coding works, assume you have a simple one
dimensional discrete time signal and
assume that you will encode each sample
with r bits per sample.
So if the signal is like this one here,
storing the signal, as is, will require n
times r bits.
You have n samples, r bits per sample.
But now suppose you take the DFT of the
signal And it turns out the DFT looks like
this.
Well, what happened was that the signal
was a sinusoid that corresponded to one of
the bases factor for the length of the
signal.
But with this representation, in theory,
instead of having n r bits to code the
signal, we just need to code two DFT
coefficients.
Possibly together with their position.
And so the amount of bits that we spend to
encode the signal, is definitely less than
n r.
So the lesson that we get from the simple
example, is that we would like a transform
that when transform in an image block
captures the important features of the
block in just a few coefficients.
So that we can just encode those
coefficients and discard all the rest.
Also, we would like the transform to be
efficient to compute because we're
interested in efficient compression
algorithm.
The answer to these two requirements is a
transform called discrete cosine transform
or DCT for short.
Mathematically the DCT can be expressed as
such.
It is very similar to the DFT.
Except that the basis functions are based
on cosines rather than on complex
exponentials.
The advantage of this formulation is that
the transform is a purely real transform,
when applied to real signals, such as
images.
Instead of studying the structure of this
double summation.
We can just exploit our intuition about
basis expansions and realize that each
coefficient of the DCT is just the inner
product, mainly, a measure of similarity
between the image and.
Each of the basis functions.
Now remember we're operating at block
level so if for instance we're going to
split our image as a cos to[UNKNOWN] into
8 by 8 pixel blocks, it means that n here
is equal to 8.
And the same in the other direction and so
we will have 64 basis functions for the
space of 8 by 8 images.
We can actually plot this basis functions
like so and here we have increasing values
of the index K1 and of the index K2.
And we can see that by computing the DCT
we're actually correlating namely,
measuring the similarity.
Between an image block, and each one of
these patterns here.
Some patterns will capture and edge like
behavior.
Some patterns will capture a textual like
behavior.
But in general, there will be a pattern
that will be able to capture most of the
information contained in the small block.
And this is really the philosophy behind
transform coding in jpeg.
Now when it comes to smart quantization,
what we need to do Is to change a little
bit the definition of quantization that we
have seen in Module Seven.
The idea is that we want to be able to
discard as many values of the transform as
possible.
And by discarding them, we mean that we
set them to zero, and therefore, we don't
need to specify their amplitude.
This is achieved by using so called dead
zone quantizers, that we will see in just
a second.
The second part of smart quantization is
being able to change the quantization step
according to the importance of the
coefficients that we are quantizing.
So key coefficients will require a fine
grain resolution.
Therefore more bits will be allocated to
them, whereas less important coefficients
can be quantized rather coarsely.
So let's go back to the quantization model
that we saw in module seven.
Suppose that our input is bounded between
minus 2 and 2, and that we're using Two
bits to quantize the input, then we're
dividing the input range into four
intervals because we have two bits per
input sample and we are associating a
representative value to each interval
which happens to be the mid point.
Mathematically in this case, we can say
that the quantized value.
Is simply the floor of the input value
plus 0.5.
You can see however that in this model
there is no zero value in the output.
If the input signal is even slightly
positive, it will get associated to 0.5.
And if it's slightly negatve to minus 0.5
but there is no zero.
A dead zone quantizer on the other hand
uses intervals that have the same width as
a standard quantizer but centers an
interval around 0.
So all values in this case from 0.5 to
minus 0.5 will be mapped to zero.
So small values will be quantized as zero.
And then the rest proceeds with the usual
staircase so everything is shifted by 0.5.
From 0.5 to 1.5 we will have a
representative value of one.
Mathematically this is equivelant to
saying that the quantization scheme simply
rounds the input value to the nearest
integer.
You can notice now that we have an
asymmetric characteristic for the
quantizer.
So in a sense, we're wasting half a bit.
We can add level to the right side or the
left side if needs be but the advantage of
having a deadzone largely offsets the loss
of half a bit.
And finally let's go see that the last
ingredient in the success of JPEG which is
entropy coding.
The idea behind entropy coding is to
minimize the effort to encode a certain
amount of information.
And the way we do that is by associating
short symbols to values that are
frequently used.
Now this may sound familiar to you, and
the reason is, because it is familiar.
The Morse Code, that was invented in 1836,
is a typical example of a coding scheme
where we use very short symbols for
frequently used values.
So, for instance, the most common letter
in the English alphabet is the letter E,
and, therefore, the symbol that we use to
encode E is the shortest possible symbol
in the Morse alphabet, the dot.
And then we can find, for instance, which
is the second most common letter in the
English alphabet turns out to be I, which
gets two dots, and so on and so forth.
So Morse code was invented to minimize the
time that it would take to send a message
over a telegraph line, but we can use
exactly the same principle to try and
minimize the amount of memory that we must
use to encode a bit stream.
We will see this in more detail in the
next module.