In this class you will learn the basic principles and tools used to process images and videos, and how to apply them in solving practical problems of commercial and scientific interests. Digital images and videos are everywhere these days – in thousands of scientific (e.g., astronomical, bio-medical), consumer, industrial, and artistic applications. Moreover they come in a wide range of the electromagnetic spectrum - from visible light and infrared to gamma rays and beyond. The ability to process image and video signals is therefore an incredibly important skill to master for engineering/science students, software developers, and practicing scientists. Digital image and video processing continues to enable the multimedia technology revolution we are experiencing today. Some important examples of image and video processing include the removal of degradations images suffer during acquisition (e.g., removing blur from a picture of a fast moving car), and the compression and transmission of images and videos (if you watch videos online, or share photos via a social media website, you use this everyday!), for economical storage and efficient transmission. This course will cover the fundamentals of image and video processing. We will provide a mathematical framework to describe and analyze images and videos as two- and three-dimensional signals in the spatial, spatio-temporal, and frequency domains. In this class not only will you learn the theory behind fundamental processing tasks including image/video enhancement, recovery, and compression - but you will also learn how to perform these key processing tasks in practice using state-of-the-art techniques and tools. We will introduce and use a wide variety of such tools – from optimization toolboxes to statistical techniques. Emphasis on the special role sparsity plays in modern image and video processing will also be given. In all cases, example images and videos pertaining to specific application domains will be utilized.
Transform Coding
Loading...
Из курса от партнера Northwestern University
Fundamentals of Digital Image and Video Processing
857 оценки
Из урока
Image Compression
In this module we cover fundamental approaches towards lossy image compression. Topics include: scalar and vector quantization, differential pulse-code modulation, fractal image compression, transform coding, JPEG, and subband image compression.
Познакомьтесь с преподавателями
Aggelos K. KatsaggelosJoseph Cummings Professor
Department of Electrical Engineering and Computer Science
Welcome back.
One way to acknowledge that there is correlation of the data
is to perform a transformation which will decorrelate them.
Then the transfer coefficients are uncorrelated and
each of them conveys unique information about deimite.
Some of them convey significant amount of information as measured, for example,
by their variance or their contribution to the local energy of the image,
while other have contributions close to zero.
The latter ones can therefore be ignored or
heavily quantized when compression is performed.
This is the topic of the segment.
We first discussed the decomposition of a nimite using an orthonormal basis.
This is a straightforward extension of such a decomposition
when we deal with vectors.
Now, if we place the requirement that the resulting coefficients of this
decomposition are uncorrelated, then we end up with Karhunen–Loève transformation.
This is the optimal transformation for our purposes, but
it has the major disadvantage that its bases are not fixed, but
their functions of the autocorrelation of deimite that is,
they're different for each image wherein it is encoding.
This makes the K-L transform impractical.
And instead, the transform of choice is the Discrete Cosine Transform or DCT.
We show with a simple experiment the usefulness of the correlating transforms
such as the DCT in deciding which part of the data to keep and which to discard.
So, let us proceed with this interesting material.
We covered in this segment transform based coding.
This is a useful and popular approach,
which as been adopted by most if not all image and video compression standards.
We show here the three building blocks of any encoder.
As mentioned multiple times, data compressible because they're correlated.
With predictive approaches such as DPCM,
this correlation is taken into account directly.
For example, we are solving for the linear prediction coefficients
by utilizing values of the autocorrelation function of an image.
With transform based coding,
we take the transformation of the data of an image or an image block.
The objective is to obtain transfer coefficients which
ideally are statistically independent.
So the contribution of each coefficient towards the original image
is independent from the contribution of the remaining coefficients.
We then look at the relative
importance of contribution of these coefficients towards the original image.
For those coefficients that contribute more, we treat them gently.
We quantize them with a fine quantizer.
And for those coefficients that contribute considerably less,
they're quantized coarsely or they're discarded.
So this is the purpose of the quantizer here.
We say that the quantizer has a spectral shape.
It's uniform but the step varies depending on the frequency of each coefficient.
The quantize transfer coefficients here are entropy encoded using
any of the techniques we covered last week such as half one and arithmetic coding.
It is therefore this bit stream that is sent to the decoder.
Now, the decoder is undoing the steps of the encoder.
So, the binary bit stream is entropy decoded and here the symbols
which are dequantized transform coefficients are inverse quantized.
This is actually a misnomer because quantization is an irreversible process.
What it's referring to is to the fact that when quantization is performed,
we divide the number,
the value of the coefficient by the step of the uniform quantizer.
And what is sent to the decode that is the quotient of this division.
Therefore, inverse quantization or dequantization refers to the fact
that this quotient is multiplied back by the step of the uniform quantizer
to obtain the actual value of the coefficient.
And then finally,
we perform inverse transformation to obtain the reconstructed image block.
So, let's look first at the characteristics of such transformations.
So what are some of the important characteristics of such transformations?
They should decorrelate the data.
So in principle,
the transform coefficients should be statistically independent.
At the same time, they should perform an energy compaction,
which means the small number of such coefficients should represent the majority
of the energy in an image.
The basis that forms such transformations should be
independent of the image we try to encode.
Otherwise, this basis should need to be transmitted to the decoder to
perform the decoding.
And finally, as always maybe, we would like to have fast implementation of such
transforms since they're clearly part of both the encoder and the decoder.
We show here a comparison of such transformations or
the shown here is the log variance of each coefficient
in the vertical axis and the coefficient number in the horizontal axis.
So, the image is broken into sub-images.
And then for each sub-image the transformation is found.
So therefore we have as a result,
another image with the same number of sub-images.
So then we'll take the, let's say, zero zero coefficient from each block
and find its variance.
We'll take next the coefficient next with the same coefficient location or
logs find its variance, and so on.
Then we order the coefficients from
largest variance here to smallest variance, as is clear from this log.
The idea is that coefficients with the larger variance will contribute more
towards the total energy of the image.
So, a transformation that decays faster is a more desirable one in the sense
that fewer coefficients represent a larger percentage of the energy.
So, we compare here, the so-called K-L, or Karhunen-Loeve transform,
which results in statistically dependent coefficients.
However, the bases in this case, are functions of the image,
more specifically, of the autocorrelation function of the the image.
We also show here the performance of the DCT, the Discrete Cosine Transform,
the Fourier transform, and the Haddamard transform.
In comparing the Fourier transform and the Discrete Cosine Transform, a clear,
distinguishing factor is that the Fourier transform coefficients are complex
numbers, while the DCT coefficients are real numbers.
And we much prefer working with real numbers than complex ones.
So, the DCT has this distinct advantage over the Fourier transform.
But more than that, the DCT is a transformation of choice,
is used in many of the image and video compression standards.
Summarizing what I already said in the previous Slide the KL
transform results in statistically independent transfer coefficients.
However, the main disadvantage is that the basis function,
so KLT of the function of the image that needs to be encoded.
The DCT is the transformation of choice.
It's close to KLT for typical images and actually there theoretical is out that
show that for a specific model for the image DCT and KLT coincide.
The basis functions, functions of cosines of independent of the image,
therefore do not need to be transmitted through the decoder.
Since it's widely used in standards such as JPEG,
the family of H.26x standards with the compression standards and
the family of MPEG standards, they're also efficient implementations of the DCT.
Embedded implementations or
even dedicated chips to perform the discrete cosine transform.
Before we proceed, let's establish some notation.
Assume we have two n by n matrices, and here,
for this segment, they're denoted like this.
So it's the matrix phi, and the matrix gamma.
So the inner product is formed by multiplying the corresponding
elements one by one.
So I'll multiply this times this element,
and then this times this, and then this times this, and I will add them up.
So the dot or inner product is clearly a scalar.
Since in general I deal with complex matrices, then
here I take the complex conjugate of each and every element of this second matrix.
Then if I have a family of matrices, they are parametrized by u and v here.
These matrices, they're orthonormal if when I take their inner product,
it's equal to zero, when u is different than r, and v is different than s,
and it's equal to one, when u equals r, and v equals s.
So the inner product of a matrix from this family of matrices with itself,
is one, that's where the normal, orthonormal parts comes from and
then a product of one matrix with any other matrix is equal to zero.
Given a family of orthonormal matrixes, phi u, v,
that we just defined in the previous slide, then given any image f,
it can be decomposed in terms of the spacing.
These often are one matrices.
So I can write f as shown here.
So this means that the image f is a co-efficient here,
f of zero,zero times phi of zero,zero, which is a matrix.
Plus F of 0, 1 and
then the phi 0, 1.
And so on all the way to f n minus 1.
N minus one phi.
N minus one, N minus one.
So it's the weighted sum where these are the weights here,
the F's, of the basis function, these normal matrices.
How does one find the coefficients here F of u, v.
We have to perform the projection of the image f onto each and
every of these bases phi.
And this projection,
this inner product we define, will give rise to this coefficient.
We have seen the composition before with vectors, not matrices.
So we're all familiar with the fact that If I have
here an orthonormal basis, so this is vector e1,
e2, and given a vector x, then I project x onto here.
Let's say this is alpha 1, and this is
alpha2, and to simply say that vector x equals alpha1 vector e1.
I can put bars here to denote that these are vectors,
plus alpha2 vector e2.
So this is the extension of this composition that they assume
you're familiar with when now we have matrices and not vectors as bases.
Here's a toy example.
We have this image of a smiley face and there's bases, we use Hadamard bases.
I'll say a few more things later on.
By projecting this image of the smiley face into each end of these bases,
we obtain this altered coefficients.
Only four of those are shown, and therefore, again,
I can decompose this image as the weighted sum
of these bases functions and these other corresponding ways.
So, the main idea is that if these bases are known,
the Hadamard base is to both encoder and
decoder, all I need to send to the decoder are these projection coefficients.
And the decoder utilizing these coefficients can reconstruct
the image just using this expression shown here.
I want to mention here the KL transformation for completeness.
Our objective is to find the family of orthonormal basis, I call them phi UV,
so that the resulting coefficients, capital FUV that are obtained
by projecting the image onto these orthonormal bases are uncorrelated.
So according to the KL theorem, if I have such an image f of m,n,
and R of m,n,p,q is its autocorrelational function,
then I can find this family of orthonormal matrices that will resulted
in uncorrelated coefficients by solving this equation.
What this equation tells us is that these orthonormal bases
are the argon functions of the auto correlation function.
And this delta uv it's simply the expected value of the magnitude
of the coefficient square.
So we have a specific
procedure in obtaining these orthonormal matrices we are after.
However, they depend on the auto correlation of the image, and
although I can compute these files at the encoder, the decoder has no way of
perform the same computation therefore this phi u,v is to be sent to the decoder.
So it is mathematically optimal transform for
our purposes, however is not practical one,
because if I have to send the bases this defeats the purpose of compression.
In the classic [FOREIGN] lesson, I prove all these
relationships however they're clearly beyond the scope of this particular class.
We see here that 64 eight by eight basis functions of the discreet cosine transfer.
Here is the interpretation of the colors.
So in this first row, we have in one dimensional
cosine that increases in frequency horizontally,
so vertically here it's constant.
And in this column we have a one dimensional cosine that
increases in frequency vertically.
For the rest of the basis, we have a two dimensional cosine
whose frequency increases both horizontally and vertically.
And down here is the basis with the highest frequency into dimensions,
I showed exactly this same plot back in week two when we talked about
complex exponential signals, and I did make the comment at that point
that would be encountering this basis functions when we talk about compression.
Now is the time to do so.
So as I have explained already given an eight by eight image block or image patch,
we just find its projection to all these 64 bases.
And if for example I find the projection or
the inner product between this base and the eight by eight patch,
a number will result which we denoted by F(u,v).
And this is the coefficient.
Clearly the projection of the patch into this here basis, it's black so
all it's value set equal to one will give us the sum of the intensities here.
If I divide by 64, it will give us the average value of the patch.
So instead of having 64 density values here I have 64 such coefficients.
These, by the way, are real, talk about the DCT transform.
The advantage of working with the F(u,
v)s instead of the F(m, n), as we denoted earlier,
is that now if somebody asks us to keep let's say
15% of the pixel values which are more important.
We have no way of knowing which 15% of the 64 pixel values are more
important than others.
However, when we look at the DCT coefficients Is rather straightforward to
keep the 15% of the 64 but have the largest values.
These coefficients again are in principle uncorrelated and
therefore keeping the ones with the largest value,
we will do a very good job in representing the original patch and
also in preserving most of the energy in the original patch.
Here we show this 64 eight by eight Hadamard basis functions.
Here's the abbreviation of the colors, only two values.
Plus and -1.
So it's a similar description as with DCT.
I should mention that in both cases, these bases are orthonormal.
So in other words, the inner product of this with this is 0.
This with any other is 0, but with itself is equal to 1.
If it's normalized appropriately.
So the story's the same.
Given an eight by eight image patch it can find the projections under this basis of
the Hadamard transformation coefficient which again are less correlated than
the original image and therefore can serve our purposes for compressing the image.
In order to demonstrate experimentally the effectiveness,
the power of this correlating property of the transformations,
we conduct here a very simple experiment.
Given this image, we are asked to break it into eight by eight blocks.
And then out of each of these blocks, we are allowed to keep only
8 pixels or 8 coefficients and we're supposed to throw the rest of them away.
So trying to decide in the special domain here which 8 out of
64 coefficients are more important is very difficult.
I have no means of doing it.
However, if we go to the frequency domain,
we keep pair block the eight largest coefficients.
And if we do so by defining a threshold and
keeping only eight out of the 64 pair block that are above the threshold.
We are just the threshold so only eight are above the threshold.
Here is the image.
So we keep 8 and set the rest equal to 0.
We see here that this is very close to the original one.
We do the same experiment when now the location of the 8
coefficients are based on this Zonal description.
So, if this is an eight by eight block in the Cosine domain,
then we keep the 8 coefficients of our closest to the.
So the 8 low frequence coefficients.
Clear the thresholding by and large should give better results than the zonal
approximation simply because there might be a large value coefficient down here,
larger than any of the ones that they get here, but I have neglected.
However when thresholding his used I have in addition to the coefficients transmit
the location so beats for the location while this location for
is fixed here when the zonal approximation is used.
So if I look at the difference between the original and
encoded versions Here is the difference scaled appropriately.
And what you can see is that the difference is really
large at the edges because the edges represent high frequency information
which was discarded in this particular case.
We conduct the same experiment when now only 4 coefficients out of 64 I've kept.
And here is the result of thresholding, zonal.
In this case, the same comments can be made as before, but I believe it's
clearer here, that the zonal approximation results in a larger error,
if we look at the intensity, or the error done, the method using thresholding.
And again, it's the same experiment we're now only 2
out of 64 coefficients are kept, and I believe it's quite impressive that
even though 2 out of 64 coefficients are kept, still we obtained the constructions
here that convey quite a lot of information about the original image.
You start seeing these [INAUDIBLE] artifacts clearly,
but nevertheless, these, again,
images are conveying quite a bit of information about the original image.
Here, I believe the error is much more pronounced with the zonal approximation
than when using thresholding.
So this is the basic idea behind transform based encoding and
as we'll see next when we discuss JPEG,
these are exactly the steps taken by JPEG or any transform based encoding scheme.
By and large, the difference is how to perform quantization.
How to decide which coefficients to keep and which to throw away.
But more specifically how to decide how to encode each and
every coefficient, with a fine or a coarse quantized.
Here these are simple ideas to just demonstrate the effectiveness
of the correlation, but again, where the innovation and
the novelty comes in is in the way, as you'll see, of quantizing these,
quantizing as well as entropy encoding these resulting coefficients.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2019 Все права защищены.
