2014-01-10 15:41:56 OPPOA113 阅读数 8321
  • 机器学习算法实战——神秘奥妙的支持向量

    支持向量机算法是机器学习的重要算法,如今已应用在图像处理、 语音识别和自然语言处理等方面。本课程详细讲解支持向量机的原理、相关概念、 推导过程和代码实战。包括:Logistic函数、最大化间隔、凸二次优化、核函数、 数据中的噪声点处理等知识。最后用了手写字分类实例,详细讲解了相关的代码实战。

    85 人正在学习 去看看 穆辉宇

注:以下为个人学习笔记、知识整理

1.特征值

从线性变换入手,把一个矩阵当作一个线性变换在某一组基下的矩阵,而最简单的线性变换就是数乘变换。

特征值的意义就是:目的就是看看一个线性变换对一些非零向量的作用是否能够相当于一个数乘变换,特征值就是这个数乘变换的变换比。

特征值得简单理解就是:输入x到系统A中,输出得到的是输出x的landa倍。

2.特征向量

公式当中的x就是特征向量。

我们更关心的是把原先的线性空间(如A)分解成一些和特征向量相关的子空间的直和。

这样我们的研究就可以分别限定在这些子空间上来进行,这和物理中在研究运动的时候将运动分解成水平方向和垂直方向的做法是一个道理!

 特征值是针对方阵而言的。

3.特征值和特征向量在图像处理的含义

我们知道,一个变换可由一个矩阵乘法表示,那么一个空间坐标系也可视作一个矩阵,而这个坐标系就可由这个矩阵的所有特征向量表示,用图来表示的话,可以想象就是一个空间张开的各个坐标角度,这一组向量可以完全表示一个矩阵表示的空间的“特征”,而他们的特征值就表示了各个角度上的能量(可以想象成从各个角度上伸出的长短,越长的轴就越可以代表这个空间,它的“特征”就越强,或者说显性,而短轴自然就成了隐性特征),因此,通过特征向量/值可以完全描述某一几何空间这一特点,使得特征向量与特征值在几何(特别是空间几何)及其应用中得以发挥。

4.矩阵论之图像处理

矩阵论在图像中的应用比如有PCA( Principal Component Analysis)主成分析方法,选取特征值最高的k个特征向量来表示一个矩阵,从而达到降维分析+特征显示的方法。一般而言,这一方法的目的是寻找任意统计分布的数据集合之主要分量的子集。相应的基向量组满足正交性且由它定义的子空间最优地考虑了数据的相关性。将原始数据集合变换到主分量空间使单一数据样本的互相关性降低到最低点。

5.PCA例子说明

      对于一个k维的feature来说,相当于它的每一维feature与其他维都是正交的(相当于在多维坐标系中,坐标轴都是垂直的),那么我们可以变化这些维的坐标系,从而使这个feature在某些维上方差大,而在某些维上方差很小。例如,一个45度倾斜的椭圆,在第一坐标系,如果按照x,y坐标来投影,这些点的x和y的属性很难用于区分他们,因为他们在x,y轴上坐标变化的方差都差不多,我们无法根据这个点的某个x属性来判断这个点是哪个,而如果将坐标轴旋转,以椭圆长轴为x轴,则椭圆在长轴上的分布比较长,方差大,而在短轴上的分布短,方差小,所以可以考虑只保留这些点的长轴属性,来区分椭圆上的点,这样,区分性比x,y轴的方法要好!

所以我们的做法就是求得一个k维特征的投影矩阵,这个投影矩阵可以将feature从高维降到低维。投影矩阵也可以叫做变换矩阵。新的低维特征必须每个维都正交,特征向量都是正交的。通过求样本矩阵的协方差矩阵,然后求出协方差矩阵的特征向量,这些特征向量就可以构成这个投影矩阵了。特征向量的选择取决于协方差矩阵的特征值的大小。

举一个例子:

对于一个训练集,100个sample,特征是10维,那么它可以建立一个100*10的矩阵,作为样本。求这个样本的协方差矩阵,得到一个10*10的协方差矩阵(解释在第6),然后求出这个协方差矩阵的特征值和特征向量,应该有10个特征值和特征向量,我们根据特征值的大小,取前四个特征值所对应的特征向量,构成一个10*4的矩阵,这个矩阵就是我们要求的特征矩阵,100*10的样本矩阵乘以这个10*4的特征矩阵,就得到了一个100*4的新的降维之后的样本矩阵,每个sample的维数下降了。

当给定一个测试的特征集之后,比如1*10维的特征,乘以上面得到的10*4的特征矩阵,便可以得到一个1*4的特征,用这个特征去分类。

所以做PCA实际上是求得这个投影矩阵,用高维的特征乘以这个投影矩阵,便可以将高维特征的维数下降到指定的维数。

6.协方差矩阵

	定义是变量向量减去均值向量,然后乘以变量向量减去均值向量的转置再求均值。例如x是变量,μ是均值,协方差矩阵等于E[(x-μ)(x-μ)^t],物理意义是这样的,例如x=(x1,x2,...,xi)那么协方差矩阵的第m行n列的数为xm与xn的协方差,若m=n,则是xn的方差。如果x的元素之间是独立的,那么协方差矩阵只有对角线是有值,因为x独立的话对于m≠n的情况xm与xn的协方差为0。另外协方差矩阵是对称的。
一般多变量分布的时候(例如多元高斯分布)会用到协方差矩阵,工程上协方差矩阵也用来分析非确定性平稳信号的性质以及定义非确定性向量的距离(马哈拉诺比斯范数)。



2018-07-24 11:54:48 zshluckydogs 阅读数 2184
  • 机器学习算法实战——神秘奥妙的支持向量

    支持向量机算法是机器学习的重要算法,如今已应用在图像处理、 语音识别和自然语言处理等方面。本课程详细讲解支持向量机的原理、相关概念、 推导过程和代码实战。包括:Logistic函数、最大化间隔、凸二次优化、核函数、 数据中的噪声点处理等知识。最后用了手写字分类实例,详细讲解了相关的代码实战。

    85 人正在学习 去看看 穆辉宇

在做图像检索时,需要提取图像的特征向量。传统的局部特征描述子如SIFT、SURF等,如果不做别的处理,往往会得到大量的特征向量,虽然特征向量的数目越多,对图像的描述越精确,检索的准确率较高,但是这也会增加硬件成本同时也会耗费大量的计算时间。

从博主的试验结果来看,单张图384×256大小,提取出的SIFT平均有200个,如果直接和库中的数据进行相似度计算,大概要1分钟的时间。对于时间要求很高的产业,这是不能接受的。所以,在不进行压缩图像损失信息的前提下,大大减少SIFT的数目是很有必要,也是很有价值的。

在查阅了大量的资料后,博主发现在做keypoint的compute之前,用MSER 检测出的keypoint代替SIFT检测出的keypoint,可以大大减少SIFT 的数目。对MSER 有疑问的,可以在找几篇相关的博客看一看,不是很复杂。

简单的说一下MSER(最大稳定值检测),基于分水岭的概念,对图像进行二值化,阈值范围[0,255],然后不断变化阈值,变化量可以自己设置,二值图像就会经历一个从全黑0到全白255的过程,就像水位不断上升时陆地和海平面的俯瞰图。在这个过程中,有些连通区域面积随着阈值的变化量很小或基本不变,这些区域就叫MSER 。关于MSER的算法细节和具体实现就不在这说了,有兴趣的可以自己研究一下。

当用MSER检测出keypoint之后,就可以利用SIFT的方式计算这些keypoint的描述子了。

import cv2
import numpy as np
import skimage.io as io
import matplotlib.pyplot as plt
filename="/home/mysj/文档/testpicture"
str=filename+"/*.jpg"
mat=io.ImageCollection(str)
img=mat[0]
##创建一个MSER检测器,并检测图像的MSER区域
##kpkp保存检测到的keypoint
mser=cv2.MSER_create()
regions,boxes=mser.detectRegions(img)
kpkp=mser.detect(img)
print len(mser.detect(img))
##用红框框出检测到的MSER区域,boxes保存这些区域的左上角的坐标和区域的宽和高
for i in range(len(boxes)):
    x,y,w,h=boxes[i]
    cv2.rectangle(img,(x,y),(x+w,y+h),(255,0,0),2)
#创建一个SIFT特征提取器
siftt=cv2.xfeatures2d.SIFT_create()

print len(regions)
print len(boxes)
kp=siftt.detect(img,None)
##计算kpkp的局部描述子
des=siftt.compute(img,kpkp)
print len(des[0])
##在图像上画出这些keypoint
cv2.drawKeypoints(img,kpkp,mat[0])
plt.imshow(mat[0])    

SIFT-SIFT方式提取的特征点有243个,MSER-SIFT提取的特征点有57个,虽然精度会有些下降,但是带来的时间上的提升是很客观的。时间缩短为原来的1/4,相当于原来跑一张的时间现在可以跑4张图。红框是MSER区域。

                                       图一 SIFT-SIFT

 

                                    图二 MSER-SIFT

 

2014-01-08 22:45:10 utimes 阅读数 2120
  • 机器学习算法实战——神秘奥妙的支持向量

    支持向量机算法是机器学习的重要算法,如今已应用在图像处理、 语音识别和自然语言处理等方面。本课程详细讲解支持向量机的原理、相关概念、 推导过程和代码实战。包括:Logistic函数、最大化间隔、凸二次优化、核函数、 数据中的噪声点处理等知识。最后用了手写字分类实例,详细讲解了相关的代码实战。

    85 人正在学习 去看看 穆辉宇

特征向量有很明确的几何意义,矩阵或方阵乘以一个向量的结果仍是同维数的一个向量,因此,矩阵乘法对应了一个变换,把一个向量变成同维数的另一个向量.

我们想知道变换的效果是什么呢?这当然与方阵的构造有密切关系,如可以取适当的二维方阵,使得这个变换的效果就是将平面上的二维向量逆时针旋转30度,这时我们可以问一个问题,有没有向量在这个变换下不改变方向呢?可以想 一下,除了零向量,没有其他向量可以在平面上旋转30度而不改变方向的,所以这个变换对应的矩阵(或者说这个变换自身)没有特征向量(注意:特征向量不能是零向量),所以一个变换的特征向量是这样一种向量,它经过这种特定的变换后保持方向不变,只是进行长度上的伸缩而已。如果特征向量的原始定义Ax= cx,那么,cx是方阵A对向量x进行变换后的结果,但显然cx和x的方向相同。而且x是特征向量的话,ax也是特征向量(a是标量且不为零),所以所谓的特征向量不是一个向量而是一个向量族.

另外,特征值只不过反映了特征向量在变换时的伸缩倍数而已,对一个变换而言,特征向量指明的方向才是很重要的,特征值不是那么重要,虽然我们求这两个量时先求出特征值,但特征向量才是更本质的东西!

例如:平面上的一个变换,把一个向量关于横轴做镜像对称变换,即保持一个向量的横坐标不变,但纵坐标取相反数,把这个变换表示为矩阵就是[1 0;0 -1],其中分号表示换行,显然[1 0;0 -1]*[a b]'=[a -b]',其中上标'表示取转置,这正是我们想要的效果。而这个矩阵的特征向量是什么?什么向量在这个变换下保持方向不变,显然,横轴上的向量在这个变换下保持方向不变(记住这个变换是镜像对称变换,那镜子表面上(横轴上)的向量当然不会变化),所以可以直接猜测其特征向量是 [a 0]'(a不为0),还有纵轴上的向量,这时经过变换后,其方向反向,但仍在同一条轴上,所以也被认为是方向没有变化,所以[0 b]'(b不为0)也是其特征向量,去求求矩阵[1 0;0 -1]的特征向量即可。


关于Image Engineering & Computer Vision的更多讨论与交流,敬请关注本博客和新浪微博songzi_tea.

2017-07-31 20:36:36 woainishifu 阅读数 33798
  • 机器学习算法实战——神秘奥妙的支持向量

    支持向量机算法是机器学习的重要算法,如今已应用在图像处理、 语音识别和自然语言处理等方面。本课程详细讲解支持向量机的原理、相关概念、 推导过程和代码实战。包括:Logistic函数、最大化间隔、凸二次优化、核函数、 数据中的噪声点处理等知识。最后用了手写字分类实例,详细讲解了相关的代码实战。

    85 人正在学习 去看看 穆辉宇

在线性代数的最后,我们都会学矩阵的特征值分解,我们知道一个方阵A经过特征值分解后就得到特征向量和特征值了。那么,这个所谓的特征值和特征向量到底是什么东西呢?


我们一上来就会学到这样的一个公式:

Ax = λx,其中x是一个向量

这个式子是如此的简单粗暴,以致于从这个公式来看,给向量x乘上一个矩阵A,只是相当于给这个向量乘上了一个系数λ。偌大一个矩阵A对向量x的作用竟然本质上不过只是和一个小小的数字λ相同而已!!!


所以这个矩阵分解方法到底具有什么样的意义?


首先给出概念上的一种解释。所谓的特征值和特征向量,最重要的是理解“特征”这两个字,特征向量翻译为eigen vector, eigen这个单词来自德语,本义是在“本身固有的,本质的”。纯数学的定义下,并不能很明白地理解到底为什么叫做特征值和特征向量。但是举一个应用例子,可能就容易理解多了。


在图像处理中,有一种方法就是特征值分解。我们都知道图像其实就是一个像素值组成的矩阵,假设有一个100x100的图像,对这个图像矩阵做特征值分解,其实是在提取这个图像中的特征,这些提取出来的特征是一个个的向量,即对应着特征向量。而这些特征在图像中到底有多重要,这个重要性则通过特征值来表示。比如这个100x100的图像矩阵A分解之后,会得到一个100x100的特征向量组成的矩阵Q,以及一个100x100的只有对角线上的元素不为0的矩阵E,这个矩阵E对角线上的元素就是特征值,而且还是按照从大到小排列的(取模,对于单个数来说,其实就是取绝对值),也就是说这个图像A提取出来了100个特征,这100个特征的重要性由100个数字来表示,这100个数字存放在对角矩阵E中。在实际中我们发现,提取出来的这100个特征从他们的特征值大小来看,大部分只有前20(这个20不一定,有的是10,有的是30或者更多)个特征对应的特征值很大,后面的就都是接近0了,也就是说后面的那些特征对图像的贡献几乎可以忽略不计。我们知道,图像矩阵A特征值分解后可以得到矩阵Q和矩阵E:

那么反推出去,把右边的三个矩阵相乘肯定也能得到矩阵A。既然已经知道了矩阵E中只有前20个特征值比较重要,那么我们不妨试试把E中除了前20个后面的都置为0,即只取图像的前20个主要特征来恢复图像,剩下的全部舍弃,看看此时会发生什么:

原图:【注意:特征值分解要求必须是nxn的方阵,如果不是行列相等的方阵,请使用奇异值分解】


只取前10个特征值:


只取前20个特征值:


只取前50个特征值:


只取前100个特征值:



我们可以看到,在只取前20个特征值和特征向量对图像进行恢复的时候,基本上已经可以看到图像的大体轮廓了,而取到前50的时候,几乎已经和原图像无异了。明白了吧,这就是所谓的矩阵的特征向量和特征值的作用。


我们再来从数学定义上尝试去理解。对应一个给定的矩阵A,如果有一个向量v,使得矩阵A作用于v之后(即A和v相乘),得到的新向量和v仍然保持在同一直线上,像下面这样:

{\displaystyle Av=\lambda v}

那么就称向量v是矩阵A的一个特征向量,而λ就是特征向量v对应的特征值【一个特征向量一定对应有一个特征值】。

注意这个定义中的要点,我们都知道矩阵其实就是一个线性变换,向量v在经过矩阵A这个线性变换之后,新向量和原来的向量v仍然保持在同一直线上,也就是说这个变换只是把向量v的长度进行了改变而保持方向不变(在特征值是负数的情况下,新向量的方向是原来方向的反向,即180°反方向)。


为了理解这个概念,我们再看维基百科上关于特征向量给出的一个《蒙娜丽莎》的例子:

当蒙娜丽莎的图像左右翻转时,中间垂直的红色向量方向保持不变。而水平方向上黄色的向量的方向完全反转,因此它们都是左右翻转变换的特征向量。红色向量长度不变,其特征值为1。黄色向量长度也不变但方向变了,其特征值为-1。橙色向量在翻转后和原来的向量不在同一条直线上,因此不是特征向量。


所以归根结底,特征向量其实反应的是矩阵A本身固有的一些特征,本来一个矩阵就是一个线性变换,当把这个矩阵作用于一个向量的时候,通常情况绝大部分向量都会被这个矩阵A变换得“面目全非”,但是偏偏刚好存在这么一些向量,被矩阵A变换之后居然还能保持原来的样子,于是这些向量就可以作为矩阵的核心代表了。于是我们可以说:一个变换(即一个矩阵)可以由其特征值和特征向量完全表述,这是因为从数学上看,这个矩阵所有的特征向量组成了这个向量空间的一组基底。而矩阵作为变换的本质其实不就把一个基底下的东西变换到另一个基底表示的空间中么?


2017-02-23 15:21:26 u013898698 阅读数 1012
  • 机器学习算法实战——神秘奥妙的支持向量

    支持向量机算法是机器学习的重要算法,如今已应用在图像处理、 语音识别和自然语言处理等方面。本课程详细讲解支持向量机的原理、相关概念、 推导过程和代码实战。包括:Logistic函数、最大化间隔、凸二次优化、核函数、 数据中的噪声点处理等知识。最后用了手写字分类实例,详细讲解了相关的代码实战。

    85 人正在学习 去看看 穆辉宇

第十一章基于特征向量的变换

目录

1.    主分量分析(PCA)、K-L变换(Hotelling变换)

2.    奇异值分解(SVD)

3.    DCT与K-L变换的关系


 1. 主分量分析(PCA)、K-L变换(Hotelling变换)

   一般而言,这一方法的目的是寻找任意统计分布的数据集合之主要分量的子集。相应的基向量组满足正交性且由它定义的子空间最优地考虑了数据的相关性。将原始数据集合变换到主分量空间使单一数据样本的互相关性(cross-correlation)降低到最低点。

    设是N维向量的数据集合,m是其均值向量:

 
 

 

 
 

   

    有了特征向量集合,任何数据x可以投影到特征空间(以特征向量为基向量)中的表示:

 
 

 

相反地,任何数据x可以表示成如下的线性组合形式:

 
 

 

    如果用A代表以特征向量为列向量构成的矩阵,则AT定义了一个线性变换:

 
 

 

上述去相关的主分量分析方法可以用于降低数据的维数。通过略去对应于若干较小特征值的特征向量来给y降维。例如,丢弃底下N-M行得到的矩阵B,并为简单起见假定均值m=0,则有:

 
 

 

它只是被舍弃的特征向量所对应的特征值的和。通常,特征值幅度差别很大,忽略一些较小的值不会引起很大的误差。

    上述方法是图象数据压缩的数学基础之一,通常被称为PrincipalComponent Analysis (PCA)Karhunen-Loeve (K-L)变换

    K-L变换的核心过程是计算特征值和特征向量,有很多不同的数值计算方法。一种常采用的方法是根据如下的推导:

 
 

 

由于通常s<<N,这种方法将求高阶矩阵的特征向量转化为求较低阶矩阵的特征向量的过程在图象数据分析中是很实用的。

 K-L变换是图象分析与模式识别中的重要工具,用于特征抽取,降低特征数据的维数。例如,MIT-Media Lab基于特征脸的人脸识别方法。http://www-white.media.mit.edu/vismod/demos/facerec/

(以上图片来自于MIT-Media Lab Photobook/Eigenfaces Demo)

2. 奇异值分解(SVD)

    奇异值分解(SingularValue Decomposition)是矩阵分析中正规矩阵酉对角化的推广。设矩阵A是的秩为r,它的奇异值是指n阶方阵AHA(或m阶方阵AAH)的正特征值的平方根 (AH是A的共轭转置)。奇异值分解是指如下形式的分解:

 
 

 

    对于图象数据而言,任意一个的矩阵A定义的奇异值变换为:

 
 

 

3. DCT与K-L变换的关系

马尔可夫(Markov)过程 一个静态随机序列称为一阶Markov序列,如果序列中每个元素的条件概率只依赖于它的前一个元素。一个的Markov序列的协方差矩阵具有以下形式:

其中,相邻两元素之间的相关系数:

这个协方差矩阵的特征值和特征向量(K-L变换正交矩阵的元素)为:

在ρ趋近1时有

与DCT变换相同。

    对于自然景物,通常有。这时DCT的基向量可以很好地近似K-L变换的基向量。由于这个原因,在图象压缩算法中常被用来代替K-L变换,如JPEG算法。尽管DCT在降低谱的相关性方面不如K-L变换有效,但是其好处是它的基函数是固定的,而K-L变换的基函数取决于待变换图象的协方差矩阵。

其它参考文献:

  1. Markus Grob, Visual Computing---The Integration of Computer Graphics, Visual Perception and Imaging, Springer-Verlag, 1994.
  2. 余鄂西,矩阵论,高等教育出版社,1995。

作业

  1. 推导K-L变换前后的协方差矩阵之间的关系:

 
 

 

  1. 阅读有关人脸识别中的PCA方法资料。

返回主目录 返回本章目录

清华大学计算机系 艾海舟

最近修改时间:2001年7月18日

出处:http://media.cs.tsinghua.edu.cn/~ahz/digitalimageprocess/CourseImageProcess.html

没有更多推荐了,返回首页