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.
Scalar Quantization
Loading...
Из курса от партнера Northwestern University
Fundamentals of Digital Image and Video Processing
665 оценки
Из урока
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
Hello and welcome to week nine.
This is the beginning of the second week
covering the exciting topic of image and video compression.
Image and video compression represents one of
the major topics in image and video processing.
Compression is one of the enabling technologies
behind the multimedia revolution we are experiencing.
Last week, we talked about lossless compression, and this week
we will see how it is used in loss recompression.
As I mentioned last week, what
distinguishes lossy and lossless compression, is not
the exploitation of the correlation of the
data, since it's shared by both approaches.
but the removal of the perceptually relevant information.
This is done through quantization.
This is the topic of this week's first two segments.
It's actually requantization since the data is already in digital form.
We will then cover predictive quality, more specifically, DPCM.
Fractal encoding, transform encoding, and also the well
known image compression standard JPEG and sub-band encoding.
We will see that each and every image and
video lossy compression system consists of three building blocks.
The first one to perform redundancy removal.
Followed by one to reduce entropy.
And finally on to perform entropy coding.
What therefore, differentiates lossy and lossless compression, is the middle block.
While, what differentiates the values lossy
compression techniques we just mentioned above, is
the first block of redundancy removal
via prediction or self similarity or decorrelation.
While, the other two blocks remain the same.
We will cover both scalar and vector quantization.
Both techniques are part of any logical operation system or
they can be implemented on their own right as compression techniques.
In this firs segment we will discuss scalar quantization.
We discuss uniform quantizers but also a PDF optimized
non-uniform quantizer also refered to as the max loyd quantizer.
We will also talk about the principle of compounding
based on which non-uniform quantizers implemented utilizing a uniform quantizer.
So let us start with this exciting topic.
In the Lossy Data Compression System, be it the
speech, audio, still image, or video compression system, and
we'll be starting the last two during this and
next week, consists of the three building blocks shown here.
According to the first one, the redundance in the data is removed.
As we mentioned earlier, the existence of redundance in the
data is one of the two reasons data is compressible.
The second building block is the reduction of the entropy of the data.
There is only one to take this step is that
according to the Shannon Coding Theorem we covered last week,
the smaller the entropy of the source the fewer the
number of bits we need to encode such as source.
This is the step that reduces the bit rate in representing the symbols of the source.
The final building block is the further reduction of the bits in representing the
source symbols, by using a lossless coding scheme which ideally will achieve entropy.
More specifically, two important mechanism to remove redundancy is prediction
and, transformation, we talked about linear prediction last week.
The main idea is to utilize the
correlation in the data, in performing prediction of
a pixel based on the values of its
either special or temporal or special temporal neighbor.
The idea behind the use of a transformation is to decorrelate the data.
Then, it's easier to tell which transfer coefficients are
more important than others, and in the next step,
try to keep the important ones in pristine shape
while discarding or heavily quantizing the less important ones.
Entropy reduction is achieved through quantization, the process
that turns the continuous values of a discrete signal
into discrete values, or requantization when discrete values are
further restricted into a smaller set of discrete values.
In designing such quantizers the properties of the visual system are
taken into account, so as to remove the perception irrelevant information.
The second usually mentioned earlier for the data being compressible.
Finally, in performance lossless encoding, of the, either quantized
prediction error or the transfer coefficient, any of the lossless
techniques we covered during last week, such as Huffman,
LZW, and Arithmetic coding and then variants can be utilized.
This center block of quantization, distinguishes lossless and loss encoding.
In other words, if it's not present, the system is
lossless, like for example, lossless JPEG that we covered last week.
With that, if you recall, a predictor was used
out of a set of predictors for redundancy removal.
and arithmetic coding for the lossless representation
of the source symbols representing prediction errors.
We will cover quantization in this lecture.
It's an irreversible process, and contributes the
most towards the reduction of the B trait.
So, in summary a loss compression scheme, we will cover in these two weeks.
And the other one that is not covered in
this class consists of these three building blocks shown here.
This week, we are going to cover the following
topics: we will talk about quantization, both scalar and vector.
We will then describe some approaches which are called
basic approaches, such as subsampling and pulse code modulation.
We will revisit differential or predictive encoding, and more
specifically you will derive the expression for differential PCM.
We will talk about fractal encoding, a
very interesting approach in its own right,
continue with transform coding and its application
to the well known standard of JPEG.
And finally, we will discuss sub-band coding.
There are other topics that we'll not have time to cover
here, such as wavelength based coding, which relates to sub-band coding.
So how does a quantizer look like?
Here is an eight level uniform midrise quantizer.
So, it's a midrise because it rises here in the middle,
as opposed to a midstop or one with a dead zone.
On the horizontal axis, you see the input intensity values of
an image or the amplitude values of a signal in general.
They can be continuous numbers or discrete numbers.
According to the mapping defined by this function all the input values say between
delta and two delta are mapped into this value three delta over two.
If this values, input values continues, then we
have infinitely many values between delta and 2-delta.
That they're all mapped into this one value 3-delta over 2.
If on the other hand, they're discrete.
Then a finite number of them are mapped into this one value.
So, for example, if delta equals 10.
Then the values here between 10 and 19 we close the
interval on this side and keep it open on this side are all
mapped into this value which is going to be equal to 15.
It's clearly an irreversible process.
If we know the number 15, we cannot tell which of the ten values in this 10 to
the 19th range was quantized to the value 15.
It is a uniform quantizer, because the steps, these are the steps.
Except of these one at the end here and here are all the same.
They have a, exactly the same values and the
output has only A discrete values the quantization levels.
So to define this quantizer we need to know that
the decision boundaries, these are the decision
boundaries, as well as the quantization levels.
Of course in this case that we have a uniform quantizer as far as the decision
boundaries go all we need to know is the step of the quantizer denoted by delta.
And clearly, if the range of values of the input is finite, let's
say between -255 and 255, then we can make all these steps exactly equal.
Here's another view of the uniform quantizer.
The quantization levels here are denoted by R of i.
And the decision boundaries are shown
here, they're typically closed on one side.
And open on the other so the interpretation is that all
the values inside this interval here are mapped to r of i.
Now suppose we know the distribution of the intensity values of
the input image by computing for example the histogram of the image.
So assume that this distribution looks like this, so we have many more
values concentrated in this region than in these regions over here.
When we design a quantizer we fix the number of quantization levels.
And we want the error we are in carrying,
the quantization error to be as small as possible.
So then how shall we design a quantizer in this case.
Shall we make the quantizer step sizes the same as before.
Shall we design in other words a uniform quantizer.
Or, can we do better than this?
What does our intuition tell us about it?
If we think for a second, we have
many more values around here than in these regions.
And we would like for these values the
quantization error to be as small as possible.
Since we have many of them and the overall quantization error is the sum of
the quantization errors per region in the quantizer or per bean as it is called.
For the values that are in here, again, we want a small quantization error while we.
With the values out here, we can allow larger quantization errors.
Now, how can we have a small quantization error?
We can do that by using a smaller step size, or in other words by doing finer.
Quantization here in the middle, where most of the values are concentrated.
And doing coarser quantization, larger step sizes, in the regions out here.
Our intuition is actually correct, because as
you'll see, the quantizer that gives us this wallace
quantization error, is a non unioniful quantizer.
As shown here against small quantization step sizes
here in the center and larger step sizes, in, the region
where this probe density function has small volumes.
And this can be mathematically derived as we'll show right away.
And again, it confirms our intuition.
But first let's define the quantization problem a bit more rigorously.
Here's the definition of the quantizer q of x.
x is the input to the quantizer a continuous number representing
the amplitude or intensity value of a sample or a pixel.
According to it the values of x between.
B-i minus 1 and b of i, the decision boundaries
are represented by the quantized or reconstruction level y of it.
Assume we want to design an m level quantize.
The variance of the quantization error is equal to this.
Inside two consecutive boundaries, bi minus 1 and b of i which are referred
to as a bin, B-I-N, the variance of the error is equal to the error squared.
x, all the values x are represented by y over i.
So this is the error squared, times the
probability that's the function of the random variable x.
This is just the definition of the variance.
Since I have M levels for the quantizer or M beans.
The variance of the total quantization error is the sum of the
individual bean error variances since the
quantization for beans is done independently.
In the quantization process, we are interested in counting beans, or
in other words, in encoding the quantization levels y of i.
These are the symbols of the source, the problem we covered last week.
The bit rate associated with this quantizer is given by this expression, so
L of I is the length of the code word which is used to encode the level Y of I.
And this is multiplied with the area under
the probability density function curve inside this beam.
From bi minus one b of i.
So this is sum over all beams here m
and therefore gives us the average code word length.
So formally the optimal quantiser results from the
minimization of the variance of the quantization
error with respect to the decision boundaries,
the reconstruction levels, as well as the
binary codes, subject to a rate constraint.
Or we can deal with the dual problem, which
is the dual formulation which is the minimization of the
rate, with request to decision boundaries reconstructive levels, and
binary codes, subject to constrained on the allowable quantization errors.
[BLANK_AUDIO].
We show here again a scalar quantizer with f representing the
input signal with continuous amplitude values or intensity
values and r of i representing the construction levels.
While d of i, r minus one d of i are the decision boundaries.
We will derive next the solution of the optimal quantizer,
assuming the fixed codes are used to represent the construction levels.
In other words, we're not optimizing over the
bit rate for representing the quantization or reconstruction levels.
We are solving therefore a simplified version of
the general problem we described in the previous slide.
The problem now it's unconstrained.
So assuming that we use fix codes to represent the construction levels.
We want to design an l level quantizer,
so, in other words, we're going to find the
d of i's and r of i's so that the variance of the quantization error is minimized.
So this is the statement of the design problem of the optimal quantizer.
Here is the expression of the variance of the quantization
error p of f is the probability density function of
the input intensities and again, we have L beans or
L-levels and this is an expression we saw earlier.
We want to find the minimum of this expression, they are now
constrained again now since we used
fixed codes to represent the reconstruction levels.
The necessary conditions for obtaining a minimum are but the
partial derivability of this variance of the quantization error with
respect to the reconstruction levels are of k is equal
to zero, and we have capital L such reconstruction levels.
And also, the partial derivatives with respect to
the decision boundaries are also equal to zero.
We have M plus 1 decision boundaries.
However, the first and last decision boundaries are known
and therefore we only have L minus 1 unknowns.
We will find next what these partial derivatives are equal to.
Let
us first look at the partial derivative of the variance of
the quantization error with respect to the construction level r of k.
If we look at the expression of D, is the sum of those integrals.
R of k appears only in this integral from dk minus 1 to d of k because
when f is inside this interval, then all these values are mapped to r of k.
The differentiation operation comes inside the integral and
then I have r of k minus f squared.
So, the derivative is two times the term, R of K, minus F times the derivative of R
of K minus F, which is equal to one, and therefore, I end up with this expression.
So, now if I split the integral into two, that's how this form looks like R of K,
clearly is a constant with respect to the integration,
which is done with respect to them D of F.
Therefore, if I solve for R of K, I end up with this expression.
What this expression is telling me is that the reconstruction level is the
centroid of the probability mass in this quantization interval.
We want now to evaluate the partial derivative of the
variance of the quantization error with respect to the decision boundary.
Things become a bit more complicated, simply because
the decision bounders appear as the limits of integration.
We need, therefore, a formula to let us know how to
carry out this differentation and this formula is due to Leibritz.
So, the derivative with respect to A of this expression here, equals the integral
here of the partial derivative of the
integrand with respect to A, plus the integrand
evaluated at the upper limit of integration
times the derivative of the upper limit
with respect to A, minus the integrand
evaluated at the lower limit of integration times
the derivative of, of the lower limit.
We will apply this formula to find again the partial of the
variance of the quantization error that I showed a few slides earlier.
If we look at that formula we see that there are two terms that depend on d of k.
This first one where d of k is the upper limit of integration
and the next one where d of k is the lower limit of integration.
For values of f between d of k minus 1 and d
of k, they are all mapped or quantized into r of k.
While when f is between d of k and d k plus one,
all of the values of f are quantized into r of k plus one.
If we apply Leibnitz's formula to carrying out the
partial of these two terms, what we obtain is this.
Let's work through the first partial derivative here, here's the integrant.
If I take the derivative of this, the partial with respect to d of k, is equal
to zero since there's no dependant d of k so this first term is going to be zero.
Then, I have the integral evaluated at d of k,
so instead of f here, I would put d of k.
Instead of f here, I would put d of k, times the
derivative of d of k with respect to d of k right?
It's a bit of an unfortunate notation here.
Too many ds with, you might say.
Minus the integrant evaluated at dk minus 1 times the derivative
of dk minus 1 with respect to dfk which is equal to 0.
So the derivative of the first term gives rise to just one term here.
And similarly, the variative of the second term would give rise to this second term.
And you can go through the steps here in a rather straightforward way.
we see that p of d of k is a common factor, it's constant, and clearly
these derivatives are equal to one and therefore
what I'm left with is this expression here.
If I apply the identity a minus b squared equals a minus b times a plus b.
Then I obtain is this expression d of k is
cancelled out, therefore this is a constant does not depend on d of k and
from the second term i obtain that d of k equals to this
and this is just the midpoint of two neighboring reconstruction levels.
We see now that if the intensities of input image follow a uniform
distribution, or in other words, p of f is a constant, then if we use the formula.
That gives us the reconstruction levels, it's very straight
forward to see that R of K is the midpoint
of the two consecutive decision levels.
And since we have that for any distribution, D
of K is the midpoint of the reconstruction levels.
We see that, in this case, the resulting quantizer is a uniform quantizer.
So this is a interesting result that the optimal
quantizer, when the PDF is uniform, is the uniform quantizer.
Uniform quantizers are used widely because they're
very easy and straight forward to use.
When we cover the enhancement we call the
[UNKNOWN] that it has a uniformed PDF of intensities.
An image with equalized histogram, and therefore when we do quantization,
if we given an image and we perform histogram equalization then.
We know that the uniform quantizer we can apply to such an image is
the best possible one in terms of
minimizing the variance of the quantization error.
So, here is another potential use of the histogram quantization
technique that we covered when we talked about image enhancement.
If we were to apply uniform quantizer in quantizing
sources with different distributions, we can obtain the optimum
step size by minimizing the variance of the quantization
error, with respect to delta, the quantizer step size.
So the steps are shown here, in this table, for different alphabet sizes.
That is when the number of quantization levels are equal to 2, 4, 8, and 16.
The sigma to noise ratio is shown as well for all these three distributions.
For a uniform distribution of amplitudes, a close form expression can
be obtained for the SNR, in terms of the quantization level.
More specifically, the SNR equal 6.02 N, where N is
the number of bits to represent the quantization levels.
So here I have m equals 2 to the 1st,
equals 2 squared, equals 2 to the 4th.
So see that for m, here, equal 1 I have 60 b, for n equal 2, I have 2 times 6.
M equals 3, M equals 4.
For the SNRs, for the Gaussian and
Laplacian distributions, they are obtained based on experiments.
We see that the best performance is achieved
when a uniform quantizer is used for the uniform
distribution of the input data, because as we saw,
a few slides earlier, this is the optimal quantizer.
We showing this table, the values of the decision boundaries.
d of i and the construction levels r of i for two different distributions
of input data, Gaussian and Laplacian, as a function of the
number of the construction levels, four, six, eight.
These results were obtained by using iteratively the two relationships for
the optimal Max Lloyd quantizer that we derived a few slides ago.
The distributions that have, heavier tails, that
is the Laplasian have larger outer step sizing.
If compare this step size to this, this one is larger.
While the same quantizers have smaller inner step sizes.
So this one is smaller than this because they're more heavily picked.
The s and l values are also shown.
Comparing this SIL values to the table in the previous slide where PDF optimized
uniform quantizer were shown, we'll see that
these are center values are considerably improved.
This is to be expected because these are
the optimal quantizers for these two distributions while the
uniform quantizer was not optimal for the Gaussian and
the Laplacian while was optimal for the uniform distribution.
We show here the effects of uniform quantization
on this eight bits per pixel original image.
When an one bit per pixel quantizer is used, here is the resulting image.
This particular quantizer has this shape.
The input values range from zero to 255,
since again, it's an eight bit per pixel image.
And then, the, values between 0
and 127, are mapped onto the mid point of this region, which is equal to 64.
While the values from 128 to 255 are mapped into
the midpoint of this region, which is equal to 196.
When two bits per pixel are used, here is the resulting quantized image.
Three bits per pixel and four bits per pixel are shown here.
Clearly, in this case, we see this artificial conturing effects.
They're not as visible when three bits per pixel are used while for
this four bit per pixel image it looks quite similar to the original one.
Therefore this uniform requantization is a simple, naive maybe, means to.
Active compression in this last case the compression factor is equal
to 2 since we go from make bits per pixel to four bits per pixel.
We see demel, the problem I discussed earlier
in the course was used in generating these results.
[BLANK_AUDIO].
We're still going to derive the optimal quantizer, but the step size is small.
We are performing fine quantization in the
regions where the input lies with high probability.
In other words, the probability density function has large values.
Instead of doing this, we can make the
interval what the input lies with high probability large.
This is the idea behind compounded quantization
as shown in the globe diagram here.
The idea of the compressor is to stretch the high probability regions close
to the origin, and correspondedly compress the
low probability regions away from the origin.
So, this region here is stretched while this region here,
[BLANK_AUDIO]
is compressed.
[BLANK_AUDIO].
Therefore, regions close to the origin in the input of the compressor
occupy a greater fraction of the total region covered by the compressor.
The output of the compressor is quantized using the uniform quantizer
and the quantized value is transformed with the use of an expander.
So the overall effect is the same as using a non-uniform quantizer.
We clearly encounter this compressor expander
mappings when we cover image enhancement.
[BLANK_AUDIO].
Two companding characteristics the co, widely used today
are the so called mu-law companding and A-law companding.
The compressor and expander functions have specific forms in this case.
The mu-law is used in North America and Japan, and
the rest of the world is using the A-law characteristics.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
