在本门课程中，您将学习图像和视频处理的基本概念，以及如何用这些概念解决商业或科学中的实际问题。 数字图像和视频现已无处不在：在科技（例如航天、生物医学等领域）、消费、工业、艺术等领域都有应用；而且已经涵盖了电磁频谱中很大一部分：从可见光、红外线到伽马射线，甚至更远。因此，处理图像和视频信号的能力对于工科和理科学生、程序员、科学家来说已经成为了必须掌握的重要技能。数字图像和视频处理使我们正在经历的多媒体技术革命成为可能。几个重要的图像和视频处理的例子：图像劣化的去除（例如将快速移动的汽车的照片去模糊），为了节约存储和高校传输对图像和视频进行的压缩和变换（如果你观看网络视频，或者用社交网络分享图片，那么你就已经用到了这些技术）。 本课程将涵盖图像和视频处理的基础部分。我们会介绍描述和分析2D/3D图像和视频的数学框架，包括空间域、时空域、频域。在本课程中，您将学到基础图像和视频处理方法背后的理论，包括图像/视频增强、回复、压缩，您也将学到如何使用最新工具将这些方法用于实际的任务。从优化工具到统计方法，我们会介绍并使用很多这样的工具。我们也会介绍在现代图像和视频处理中扮演重要角色的“稀疏性”。在所有案例中，特定应用下的示例图像和视频都会被用到。
Matrix-Vector Notation for Images
Loading...
来自 Northwestern University 的课程
数字图像和视频处理基础
716 个评分
从本节课中
Image Recovery: Part 1
In this module we study the problem of image and video recovery. Topics include: introduction to image and video recovery, image restoration, matrix-vector notation for images, inverse filtering, constrained least squares (CLS), set-theoretic restoration approaches, iterative restoration algorithms, and spatially adaptive algorithms.
与讲师见面
Aggelos K. KatsaggelosJoseph Cummings Professor
Department of Electrical Engineering and Computer Science
In this segment, we introduce a means to
represent all pixel in an image as a vector.
This then introduces an alternative way for
representing the degradation equation in the restoration problem.
It becomes a vector matrix equation.
If the degradation is LSI.
Then this degradation matrix has a specific form.
It is a block circulant matrix.
It is straightforward to describe this matrix in the
spectral domain, by finding its eigen values and eigen vectors.
We study this property which allows us to
take the degradation equation to the frequency domain,
something of course we know we can do,
based on the material we covered in week three.
The reason of course we devoted this lecture to study this alternative
representation of images and the matrix
vector version of the degradation equation.
Is not to just do some math, but because they
provide the flexible representation of images and systems that crosses them.
And they're also useful since we can now easily borrow tools and the results from
linear algebra optimization theory, in providing solutions
to these inverse problems we are interested in.
Before we proceed I would like to introduce a vector notation
for images and then make this vector notation for the convolution equation.
So let's assume we have an image,
of dimensions N by M.
So this is the image here.
The standard way we've been using, so far, to represent an image is xm1 and 2.
Where n1 ranges from 0 to n minus 1 and 2, from 0 to m minus 1.
We
would like to represent this two dimensional array.
This image as a 1 dimensional vector.
So I'd like to write this image as a vector x.
And now vectors can be shown in bold
face, or sometimes with an underbar or an overbar.
It should be clear from the context that a vector is involved.
So one way to do it, is to take each row of the original image, so here's row
0, row 1, row N minus 1.
And
turn each row into a column vector, so this is row 0 transpose.
So it comes here.
Row 1 transpose
all the way do to row M minus 1 transpose.
So the n by m image is now converted into an nm times 1 vector.
So this is the process of stacking an image into a vector.
And if the stacking is, shown here.
I stack by rows.
Then it's also referred to as lexicographic
ordering.
So it should be clear.
From now on, that this functional representation
x function of n 1 and 2, and
this vector representation can mean the same
thing, mean the same thing in what follows.
[SOUND] Let us consider the one dimensional
convolution of two one dimensional signals, x of n convolved with h of n.
Let's call the resulting quote y of n, and we know that this is equal to
the sum of the k, x of k h n minus k.
Let's assume for simplicity that x of n, here support from 0 to n minus 1.
And samples in other words.
H of n is support from 0 to L minus 1.
And as we know, the result of the convolution will
have support the sum of the limits of the support.
So from 0 to N
plus L minus 2.
I would like to consider all the values of a signal y, and stack them into a vector.
So I'd like to form the vector y 0, y 1, all the
way to y N plus L minus 2.
So this vector.
Is, n plus l minus 1 by 1 vector.
So this will be equal to matrix here,
that will multiply the signal x, so here is x
0, x 1, x of n minus 1.
So x clearly has dimensions N by 1.
And therefore, this matrix has dimensions N plus L minus 1 times N.
So, if we follow the steps of the convolution, we take age, we
flip it around, find H of minus k and then shift it by n.
You can see that y 0 is equal to H 0 times x 0.
y 1 is equal to H 1 times x 0 plus H 0 times x 1.
Then I'll have here, this row of H's.
[SOUND]
[BLANK_AUDIO]
And the rest of the values here not shown, they're all zero.
So if I call this a vector y, and call
this matrix H, and then a vector X, I wrote.
In matrix form, is out of the convolution,
because then all the values of, of the signals.
I can, kind of combine them all into this matrix vector form again, Y equals HX.
We observe at H, here's this specific form
that is the values along each diagonal are equal.
And this is referred to as a [INAUDIBLE] matrix.
We will see next that by modifying
the signal and the matrix, we can write indeed that the matrix vector form
for, for the central convolution and then this matrix H
is going to have another form which we call circulant matrix.
I would like to perform the circular convolution of x of n with h of n.
So that the result of the circular
convolution equals that of the linear convolution.
In order for this to be the case, I should carry
out the circular convolution with period N plus L minus 1.
Let's call this Y of N again.
So if this means I should pad X of N with
L minus 1 0s and then carry out the [INAUDIBLE] convolution.
So, if I do the same thing here now, which
is to put all the values of Y into a vector.
[SOUND]
This will
be equal
to a square matrix.
It's now multiplying x.
And x i'll have the original values of x.
0, 1, all the way to n minus 1.
And then I'll add it with zeros.
And the number of zeros is equal to l minus 1.
So if we look at the structure of h here this matrix.
It will have h 0 on its main diagonal.
[SOUND] h 1 on the diagonal below it.
[SOUND] All the way.
2 H L minus 1.
Would be 0 here and then, in this corner
would be H1, H2, H L minus 1.
[SOUND]
And I'll have let's say here H, at minus 1.
And Z everywhere else.
It is to verify that indeed that the values you
ob, obtain here by getting out this matrix vector multiplication
are equal this Y values to the values you obtain
from the linear convolution as shown in the previous slide.
So again, I can write y equals H x.
H now has also a special structure.
The structure now is that if I take any row of H,
and I circularly shift it by one to the right, then, and
circular means that the element that leaves the matrix due to this
shift to the right, wraps around and appears at the other end.
Of the, of the row
at the beginning of the row.
And I'll do, I can do this for all rows including the last row.
So if I set to receive the last row, I'll obtain the first row.
So this matrix is called the circulant [SOUND] matrix, and
here's some useful properties that we, we will talk about next.
[SOUND].
We found in the previous slide, that if I use a matrix
vector presentation of secular convolution, I
end up with a secular matrix.
Here's a simple example of a 4 by 4, secular matrix.
So the element of the first row are these, a1, a2, a3, a4.
I generate the 2nd row by circulating shift the first shifting the first one.
So this is a1, a2, a3.
a4 wraps around and comes this place.
a1, a2, a3, a4 wrap around.
And finally, a1,
a4, a3, a2.
So clearly for this 4 by 4 matrix if I know the
elements of its first row, I can define the whole matrix, since again.
Qundro Ichero is generated by the secular shift of the row above it.
So if I look at the general matrix h it's a circular matrix.
The elements of the first row are h 0 to h.
M minus 1 I don't write the remaining of
the rows in again secular shifts of the first one.
For any secular matrix finding it's Hegan values and Hegan
vectors which is by and large a difficult problem, is rather straight forward.
And this is so.
Because, let me first denote
by lump in W,
it's E convectors or the Ws and.
And lambda, the eigenvalues.
So the eigenvec, vectors of any circulant matrix are known in advance.
The nth eigenvector is equal to this.
[SOUND].
And one should recognize right away that these are the
basis vectors of a discrete Fourier transform, these complex exponentials.
And the set of eigenvalues,
are simply, the discrete Fourier transform values of the first throw of the matrix.
[NOISE]
So again a very straightforward and important property of circulant matrices.
So the singular value composition of the original matrix,
is simply equal to this.
I put the Eigen vectors here as column vectors of the matrix.
The Eigen-values become the diagonals.
Element of a diagonal matrix.
[SOUND] And this
matrix is the first one, actually should be 0 here, on the first one.
[SOUND] Minus 1, it's an inverted matrix.
So I can write any secular matrix H as WDW
minus 1, but again these this diagonal
matrix that has it at it's diagonal.
The discreet fully transformed of the first row of the matrix.
Based on what you've seen, let's assume I have the secular convulsion of x of n
circular length n with h of n.
Lets call this y over n.
We know from the study of the discrete fourier transform that they can
take this equation to the discrete
frequency domain, where the convolution becomes multiplication.
So these are the discrete fourier transforms of
the corresponding quantities and this is an endpoint DFT.
So k goes from zero to n minus 1.
Now we saw that I can take this equation
here and write it as a, matrix vector form.
Where H is a block circular matrix.
And we did see that H can be written
also, its singular value composition is equal to this.
Therefore from here, if I multiply by w
minus one both sides this becomes equal to this.
It can be easily shown that w minus one
signal is the discreet fully transformed of the signal.
So, this is the DFT.
[SOUND] Of y, all the values.
And this is the DFT of x.
[SOUND]
So this gives me, this is a vector clearly, so
this vector gives me all the values of the DFT
of Y.
And D is a diagonal that has as its element the DFT of H,
so this is H(0) to H(N-1).
And here's the tft of x.
So we see whether we're waiting with a point wise here version
of a circular convolution or the matrix vector form of the circular convolution.
By either taking the d f d here, in a straightforward way, I
end up with a point wise relationship in the discrete frequency domain shown
here, or by considering the spectral decomposition of the matrix age, which is
second, I end up with the matrix
vector representation of the Discrete Fourier Transform.
So this is something very important to keep in
mind that we will be making use a multiple times.
Based on what we have discussed so far, if I, if
I have a linear system H that accepts f as its input.
And the noise is added that it's output to form the preservation y.
I can represent this system in the matrix vector format shown here by stacking
lexicogrhaphically more specifically stacking the images into vectors.
Now the system in addition to be linear is also specially invariant.
Then the input output relationships are represented
by the familiar by now two dimensional convulsion.
In this case the matrix h has
a special structures, it's now block circular matrix.
Which means that it is circular circular at the block level,
so you see if I take the first row of blocks.
And shifted circularly, I will obtain the second row of blocks and they
keep going if I take the last row of blocks and secondly shifted.
I will obtain the first row of blocks.
But each block is also a circulant matrix.
And that's a definition of a block circulant matrix.
If let's say for simplicity, H here,
has a first quadrant support.
And this is the 0th row, this is the 1st row
of the impulse response, this is the N minus 1 row.
Then the zero'th row would be used to form the sub-matrix h zero.
The first row of the sub-matrix h 1 and all the way to the sub-matrix h n minus 1.
So this simple response that I show here.
Is all that's needed to form this block circular matrix.
Because for each block I need its first row, and then,
that's all I need, because it's circular at the block level.
The story with block circular matrices is the
same as with circular matrices I mentioned earlier.
So if H is a block circular matrix.
It can be decomposed as shown here.
W has as elements, the eigenvectors of age, which
are the two-dimensional complex
exponentials, also the two-dimensional DFT.
And D here is a diagonal matrix.
With elements that stack values of the two dimensional dxd of hij, so
then if I started with the observation equation as shown here, I
substitute the value of the decomposition of h here and then.
I pre-multiply with W minus 1 to, to obtain this.
So W minus 1 y is, represents the stacked values of the two dimensional DFT of y.
And similarly, W minus 1 f represents the stacked into a vector values of the.
That could be measure of DFT of F.
So in another words, this equation is equal to Y equals D, F plus M,
where again here, I have start the two dimensional DFT of the image y.
I have stuck in the vector here two dimensional DFT values of the
image f and these are diagonal matrix that has the DFT of h.
If I look one element of y since this diagonal is going to
give me one element of the discrete fully transfer of the image y.
So each entry of this vector y Y
represents the point ys here, frequency u, v.
These, these are the discrete frequencies, of, of the DFT.
In what follows we're going to need some very basic
elements of linear algebra that I would like to mention.
So given a N dimensional column vector, X,
the L2
norm of the vector squared is simply X transpose X.
It's a scaler.
And this is equal to the sum
of xi squared.
So, applying this to a term like this, [SOUND].
The definition of the norm that is, this is y minus hx transpose.
Y minus hx.
And if I carry out all the cross multiplication this is equal to this
[NOISE]
right these are all scalers these are inner products.
And the one is the transpose of the other therefore they're equal and
this becomes equal to y transpose y minus
2 x transpose
H transpose y plus x transpose H transpose H.
H x.
We'll also need the notion of the gradient over function all over norm.
This is, by definition, this is a vector, intimation of vector that has.
The partial respect for x 1 of the norm squared, all the
way to the past with respect to x squared of the norm squared.
And if I use the expression for the norm, I just showed in the beginning
it's the sum of the a x of y squared.
Then clearly if I look at any of these partial derivatives
only one term that depends on a particular x or y.
So the first term, there's only one term depending on x 1.
So this is 2 x1, down here it's 2 xN, so this equal to 2 x.
So applying this definition you should be able to verify that the gradient
with, gradient with respect to x of x transpose y is equal to y.
Y, the great, in respect to x of the quadratic term here
is equal to 2 times H transpose H x.
