# 计算机视觉中svd

## 计算机视觉和图像处理框架

2016-09-02 10:13:43 u012521552 阅读数 4115
• ###### 极线几何

掌握极线几何模型及本质矩阵的意义 掌握基于双目视觉进行三维重构的步骤 了解基于k-d树的特征匹配方法，了解RANSAC的基本思想

1825人学习 CSDN就业班
免费试看

# 计算机视觉和图像处理框架

#### 二、计算机视觉基本流程

1、数据采集（输入）
2、预处理: 去噪、增强
3、特征提取；
4、检测/跟踪/分割；
5、高级操作（分类、识别等）（输出）

#### 四、为我所用

Boosting、clustering、CS（Compressive Sensing）、DT（Decision Trees）、DP（Dynamical Programimg）、EM、GM（Graphical Model）、HMM、ICA、PCA、RF（random forest）、RANSAC、SVD（Singular Value Decomposition）、稀疏表示、SVM、小波、NN

## SVD-在计算机图像上的应用

2017-04-16 23:23:00 weixin_30349597 阅读数 20
• ###### 极线几何

掌握极线几何模型及本质矩阵的意义 掌握基于双目视觉进行三维重构的步骤 了解基于k-d树的特征匹配方法，了解RANSAC的基本思想

1825人学习 CSDN就业班
免费试看

All the information in this passage is from  course (ROBOTICS:PERCEPTION,made by university of pennsylvania) on Coursera. If by any chance it violates the rights, I will delete it upon notification as soon as possible.

So today we will start talking about D squared, and single value decomposition. D squared is a very important concept
used many times in our engineering world. It was used for example by Gauss. In his calculation of the orbits,
of earth around the sun. In computer vision D square is used in many, many different cases. What we'll study through a sequence of examples?First, we're going to take a detour. So, a computation known as singular value decomposition or SVD. It is one of the most useful tools you will encounter in our computation of vision problems in the next few lectures. Singular value decomposition, is a way of taking a matrix a, and decomposing to three separate components. So matrix A, could be of many forms, it comes from many different reasons, and physical meanings. The end results is we have a matrix a of size m, by n. Given any matrix of A, which you can think of as a transformation themselves. We can decompose this matrix, into three components U, D, and V transpose, meaning that U, multiplied by D, multiplied by V transpose will reconstruct the matrix exactly. And this is a very interesting fact. Like any matrix A can be decomposed in this following fashion.

And the U matrix that we have has a particular property. U matrix, can be thought of columns, and each columns with U, has a property that take a half part between themself equal to one, meaning that each column, the U, is a norm of one. Furthermore, if I take two columns U, and take that part out of them, the answer is zero, meaning the U's are constructed, such that all the columns, are perpendicular to each other. Second perpendicular to first, third perpendicular to both first, and second. Such you can think of the U's, essentially basis function, spanning the same space, as the columns of A.

Similarly, the draws of the V transpose, also had the following form that takes any draws of the V transpose will have perpendicular vectors. Or mathematically, one could write, U transposed times U equal to I and V transposed V equal to I. So that's, the first fact of
the singular value decomposition. That a matrix A can decompose into a set of column vectors U perpendicular to each other, a diagonal matrix D, and a set of rogue perpendicular vectors V transposed. And multiplying the three matrices, reconstruct the matrix A exactly. And we can always do this. In the math lab, this is a function called SVD.

The second, a fact of this decomposition is that the singular value matrix is diagonal forms. Meaning the elements are zero, and the non-zero elements sits, on the diagonal.  And one can always sort it, from large to small. So sigma one, larger than sigma two, all the way bigger than zero. So all the values on diagonals are positive, or zero. We will see cases when the last element is zero, or several of the elements are zero. The U matrix is going to be the size of same, as A and by n. The diagonal matrix singular value matrix is size, m by m, and the V transposed matrix is size m by m.  We can think of the U matrix, as set of basis. For example, if A is made of curve, and since this space where every column of A is a curve, we can think of the U matrix enclose the basis function, where the first base is, for example, is a horizontal curve, and the second basis function is a curve going down. And the third basis encode a curve going up, and down. Then we can think of the matrix V together with the singular value D, provides a coefficient for every column A. So, the coefficient of the beta1, beta2, beta3. So through a scaling of a beta1, beta2, beta3, it provides a reconstruction in column of A, which is represented by a curve here. As such we can think of U is basis, the columns of V transpose provide us the addresses. Multiply to the scale factor, give us the beta1 to beta n. So, the first factor we can think of is SVD, as transforming matrix A, into it's basis function, and the transformed addresses. So let's just think of this painting by Mondrian, what is the SVD of this painting? Well first of all, what is this painting? The painting in our world is in fact a matrix. Where rows, and columns are pixels. And Mondrian, paintings are very good illustration of this basis, because all the Mondrian paintings are made of rows, and columns. So let's take this Mondrian painting, and first convert a colored image to a gray skull image, shown on the top left. Right here use the colormap jet in the matlab illustration, where red indicated bright pixels, blue means dark pixels. So this is a Mondrian in the black, and white world, but illustrated in the colormap jet. And we were take SVD of this image, which is made of thousands rows, many thousand columns, we see that we can construct SVD of this matrix. And to reconstruct from it a U matrix. And here, I illustrated only the first four columns of the U to highlight what it looks like. So first note, the first columns are almost uniforming it's values. The second column we can see, has some positive value which indicated in orange, and some negative values indicated in blue. As such, you can see that this perpendicular to the first column. In the image, what it's capturing, it's saying that Mondrian paintings are made of two halves.On the top half, which are one color, and the bottom part of the image is another color. Move out to the third column of U, we see, again, is made of some value, positive mean indicated in red, blue indicating the negative values. Again, this vector is perpendicular, to the first two columns. And again if you look at this picture, what it is indicating is telling us the Mondrian paintings for this picture has several rows have the same color, hence we have a basis vector with uniform color in it. Now just take in the four columns of SVD of this picture I can reconstruct this picture by taking the first four columns of U. The first four by four matrix of a singular value matrix D, and the four rows of V. And reconstructing the matrix through the matrix multiplication is shown in the bottom right. As you can see, this is not exactly the same but it's a very close approximation than where we started. As such, we can think of SVD is a process of simplifying what's in the matrix, very large matrix and then using a set of basis functions, illustrating U and using a set of addresses in V.   If I were to take more rows and more columns view matrix but not all of them. For example, I only take the first 20 columns of the U matrix, I can reconstruct the Mondrian painting fairly closely. In the center at what I've shown here is the log of the singular values. As you can see, the log of a single values drop off pretty rapidly, indicating that many dimensions in the basis function has a scale factor near 0. And we're going to use this factor for many different cases. And we're going to use this for using SVD as a clean up process of cleaning up a matrix. Or we can use this factor to approximate a large dimensional matrix with a few basis functions. So now let's look at Gauss himself in rows and columns. So Gauss is not painted by Mondrian so he has many orientations edges horizontal, not lines with horizontal vertical directions, but nonetheless we can take Gauss' image as a matrix and reconstruct itself. So on the middle we have a Gauss image reconstructed with more basis functions and the right we see a Gauss image reconstruct with a few vectors. And this is shown in grayscale. As you can see, it still captured the structure of his face fairly reasonably with on a few basis functions. And this is because many rows and many columns of this image are redundant, they are not exactly the same but it can be represented by a few basis vectors.  So this is a look at a picture as a matrix where there are thousands rows and thousands of columns. One can also look at a picture as a vector by taking all of the rows, all of the columns and stacking them into one, long vector. So if I have a 1000 by 1000 image, that would be a vector of a million dimension long. This is illustrating here images not as a matrix, but image as a vector. As such that I can take many, many pictures, many, many pictures of people's face for example. Each one forms a vector and I can stack the vector together each one, 1 million direction long, 1 dimensional long, and then maybe thousand peoples, we have a million by thousand matrix. I can take a single value decomposition with that matrix that gives me a set of basic function U, and it reshape the use back to the image space. And this is what happens when we do that. On the left we have a set of images of the face. Each one stretch into vector space, placed column-wise next to each other. We computed SVD of this matrix, and we take the first few columns of U, and reshape back to the image space. And this is called eigenfaces, as you can see those eigenfaces capture different characteristics of the face. For example some capture the hair, some capture the mouth. And from those basis functions, one can re-express our faces as addresses in those spaces.   Here is a set of images captured by an artist for people in Berlin. On the left we have the first basis function for the man. On the right we have a first basis picture of the woman. Taking a view of eigenvectors as well as addresses, we can see here are three faces reconstructed by the same eigenvector or use different coefficients on this eigenvector. So, here we show different ethnic group it will show you by this eigenvector, address from one point address space to another point address space. Here we have a different eigenvector corresponding to the age changes. Again, as we change the address on this eigenvectors faces transform itself. So now we are seeing eigenvectors, singular value vectors, as our basis functions and as such that we can think of it as our basis functions and their addresses and together they reconstructed the matrix or in this case image for me. Once we have decomposed a matrix A into a singular value decomposition, U times D times V transpose, we can also understood the concept of rank and row space. A rank of matrix A is simply defined as the number of the non-zero singular values in the matrix D. So we call that r, rank of A equal to r. The number of elements non-zero on the diagonal. And r is going to be less than equal to the dimension of m or n. The null space is corresponding to exactly those elements associated with singular values equal to zero. So if the rank is r, then the columns in V or rows in V transpose associated with those dimensions where single value is 0, are the null space. So we take the columns, from r plus one all the way to n. If r is the rank, r plus one to n columns of V is the null space of A. And we have the following property that A Times the nullspace V, r plus one to n, equal to 0. ## 奇异值分解(SVD)详解及其应用

2016-10-24 22:58:49 shenziheng1 阅读数 44420
• ###### 极线几何

掌握极线几何模型及本质矩阵的意义 掌握基于双目视觉进行三维重构的步骤 了解基于k-d树的特征匹配方法，了解RANSAC的基本思想

1825人学习 CSDN就业班
免费试看

# 2.奇异值分解详解

1 特征值   它其实对应的线性变换是下面的形式： 因为这个矩阵M乘以一个向量(x,y)的结果是：   2 奇异值： 假设A是一个N * M的矩阵，那么得到的U是一个N * N的方阵（里面的向量是正交的，U里面的向量称为左奇异向量），Σ是一个N * M的矩阵（除了对角线的元素都是0，对角线上的元素称为奇异值），V’(V的转置)是一个N * N的矩阵，里面的向量也是正交的，V里面的向量称为右奇异向量），如下图所示：    r是一个远小于m、n的数，这样矩阵的乘法看起来像是下面的样子： 右边的三个矩阵相乘的结果将会是一个接近于A的矩阵，在这儿，r越接近于n，则相乘的结果越接近于A。而这三个矩阵的面积之和（在存储观点来说，矩阵面积越小，存储量就越小）要远远小于原始的矩阵A，我们如果想要压缩空间来表示原矩阵A，我们存下这里的三个矩阵：U、Σ、V就好了。

# 3.如何计算奇异值

奇异值的计算是一个难题，是一个O(N^3)的算法。在单机的情况下当然是没问题的，matlab在一秒钟内就可以算出1000 * 1000的矩阵的所有奇异值，但是当矩阵的规模增长的时候，计算的复杂度呈3次方增长，就需要并行计算参与了。

Lanczos迭代就是一种解对称方阵部分特征值的方法（之前谈到了，解A’* A得到的对称方阵的特征值就是解A的右奇异向量），是将一个对称的方程化为一个三对角矩阵再进行求解。

# 4.奇异值分解应用 一般来说，方差大的方向是信号的方向，方差小的方向是噪声的方向，我们在数据挖掘中或者数字信号处理中，往往要提高信号与噪声的比例，也就是信噪比。对上图来说，如果我们只保留signal方向的数据，也可以对原数据进行不错的近似了。
PCA的全部工作简单点说，就是对原始的空间中顺序地找一组相互正交的坐标轴，第一个轴是使得方差最大的，第二个轴是在与第一个轴正交的平面中使得方差最大的，第三个轴是在与第1、2个轴正交的平面中方差最大的，这样假设在N维空间中，我们可以找到N个这样的坐标轴，我们取前r个去近似这个空间，这样就从一个N维的空间压缩到r维的空间了，但是我们选择的r个坐标轴能够使得空间的压缩使得数据的损失最小。
还是假设我们矩阵每一行表示一个样本，每一列表示一个feature，用矩阵的语言来表示，将一个m * n的矩阵A的进行坐标轴的变化，P就是一个变换的矩阵从一个N维的空间变换到另一个N维的空间，在空间中就会进行一些类似于旋转、拉伸的变化。      这样我们就得到了对行进行压缩的式子。可以看出，其实PCA几乎可以说是对SVD的一个包装，如果我们实现了SVD，那也就实现了PCA了，而且更好的地方是，有了SVD，我们就可以得到两个方向的PCA，如果我们对A’A进行特征值的分解，只能得到一个方向的PCA。

# 5.感谢

1.感谢杜克大学 方贺好友

2.感谢博客园 王大田博主

3.感谢清华大学数学系 刘永中教授

## 奇异值分解SVD应用——LSI

2012-10-31 09:49:07 abcjennifer 阅读数 49917
• ###### 极线几何

掌握极线几何模型及本质矩阵的意义 掌握基于双目视觉进行三维重构的步骤 了解基于k-d树的特征匹配方法，了解RANSAC的基本思想

1825人学习 CSDN就业班
免费试看

————————————   ## 浅谈SVD的理解

2017-07-06 15:18:50 qingcaichongchong 阅读数 3353
• ###### 极线几何

掌握极线几何模型及本质矩阵的意义 掌握基于双目视觉进行三维重构的步骤 了解基于k-d树的特征匹配方法，了解RANSAC的基本思想

1825人学习 CSDN就业班
免费试看   ps：实际上应该是其减去均值后的乘积，上面是我盗的图，能说明问题，我就懒得再编辑公式了      XTA = (UVW)T(UVW) = WTVTVW，即C = VTV，得证。 