2016-07-04 10:38:28 qq_26499769 阅读数 22242


2.3.3 赋范空间


每个实数或复数,都有相对应的绝对值或者模,每一个n维矢量,也都可以定义其长度。如果把“长度”的概念推广到一般抽象空间中的元素上,就可以得到范数这个概念。



本节完。



2.3.6 希尔伯特空间


定义:在由内积所定义的范数意义下完备的内积空间称为希尔伯特(Hilbert)空间
希尔伯特空间是一类性质非常好的线性赋范空间,在工程上有着非常广泛的应用,而且在希尔伯特空间中最佳逼近问题可以得到比较完满的解决。




傅立叶变换以高等数学(微积分)中的傅立叶级数为基础发展而来,它是信号处理(特别是图像处理)中非常重要的一种时频变换手段,具有重要应用。在图像编码、压缩、降噪、数字水印方面都有重要意义。此外,快速傅立叶变换算法还位列20世纪十大算法之列,它是“动态规划”策略在算法设计中的杰出代表。本文将详细介绍图像中的傅立叶变换及其快速算法。对于傅立叶变换的数学原理还不是很理解的同学,建议参考本系列前面已经发布的傅立叶级数相关内容,争取彻底搞懂相关数学原理。一知半解、不求甚解,都是自欺欺人的表现。


6.1.2   数字图像的傅立叶变换

为了在科学计算和数字信号处理等领域使用计算机进行傅立叶变换,必须将函数f(t)定义在离散点而非连续域内,且须满足有限性或周期性条件。这种情况下,使用离散傅立叶变换。将连续函数f(t)等间隔采样就得到一个离散序列f(x),假设采样N次,则这个离散序列可以表示为{f(0),f(1),f(2),...,f(N-1)}。如果令x为离散实变量,u为离散频率变量,则一维离散傅立叶变换的正变换定义为



图像的频率是表征图像中灰度变化剧烈程度的指标,是灰度在平面空间上的梯度。从傅立叶频谱图上看到的明暗不一的亮点,实际上图像上某一点与邻域点差异的强弱,即梯度的大小,也即该点的频率的大小(可以这么理解,图像中的低频部分指低梯度的点,高频部分相反)。通常,梯度大则该点的亮度强,否则该点亮度弱。这样通过观察傅立叶变换后的频谱图,也叫功率图。在功率图中我们可以看出图像的能量分布,如果频谱图中暗的点数更多,那么实际图像是比较柔和的(因为各点与邻域差异都不大,梯度相对较小),反之,若频谱图中亮的点数多,那么实际图像一定是尖锐的,边界分明且边界两边像素差异较大的。对频谱移频到原点以后,可以看出图像的频率分布是以原点为圆心,对称分布的。变换最慢的频率成分(u = v = 0)对应一幅图像的平均灰度级。当从变换的原点移开时,低频对应着图像的慢变换分量,较高的频率开始对应图像中变化越来越快的灰度级。这些是物体的边缘和由灰度级的突发改变(如噪声)标志的图像成分。通常在进行傅立叶变换之前用(-1)^(x+y)乘以输入的图像函数,这样便可将傅立叶变换的原点(0,0)移到(M/2,N/2)上。


6.1.3  快速傅立叶变换的算法


离散傅立叶变换(DFT)已经成为数字信号处理和图像处理的一种重要手段,但是DFT的计算量太大,速度太慢,这令其实用性大打折扣。1965年,Cooley和Tukey提出了一种快速傅立叶变换算法(Fast Fourier Transform,FFT),极大地提供了傅立叶变换的速度。正是FFT的出现,才使得傅立叶变换得以广泛地应用。


FFT并不是一种新的变换,它只是傅立叶变换算法实现过程的一种改进。FFT中比较常用的是蝶形算法。蝶形算法主要是利用傅立叶变换的可分性、对称性和周期性来简化DFT的运算量。下面就来介绍一下蝶形算法的基本思想。


由于二维离散傅立叶变换具有可分离性, 即它可由两次一维离散傅立叶变换计算得到,因此仅研究一维离散傅立叶变换的快速算法即可。一维离散傅立叶变换的公式为





上述FFT是将f(x)序列按x的奇偶进行分组计算的,称之为时间抽选FFT。如果将频域序列的F(u)按u的奇偶进行分组计算,也可实现快速傅立叶计算,这称为频率抽选FFT。

通过对图6-6的观察可以发现,蝶形算法的频率域是按照正常顺序排列的,而空间域是按照一种叫做“码位倒序”的方式排列的。这个倒序的过程可以采用下面的方法来实现:将十进制的数转化成二进制,然后将二进制的序列倒序重排,最后再把颠倒顺序后的二进制数转换成十进制数。倒序重排的程序是一段经典程序,它以巧妙的构思、简单的语句用完成了倒序重排的功能。表6-1给出了倒序重排的示例。






6.4.3 主成分变换的实现


本小节通过一个算例验证一下之前的推导。在前面给出的例子中,各点在原始的

由于方程是齐次的,所以不独立。因为系数矩阵有零行列式,所以方程有非无效解。从两个方程的任何一个可见

现在考虑该结论该如何解释。特征向量g1和g2是在原坐标系中用来定义主成分轴的向量,如图6-20所示,其中,e1和e2分别是水平和垂直的方向向量。显而易见,这些数据在新坐标系中是非相关的。该新坐标系是原坐标系的旋转,出于这种原因,可以将主成分变换理解为旋转变换(即使在高维空间上亦是如此)。

6.4.4 基于K-L变换的图像压缩

从图像压缩的角度出发,我们必然希望变换系数协方差矩阵Σ中除对角线外的所有协方差均为零,成为对角线矩阵,即原来像素间的相关性经变换后全部解除,或者至少大部分协方差要等于或接近于零。为此,需要选择适当的变换矩阵,它作用于Σx 后使其变成对角线型。通过前面的分析和推导,可知这样的变换矩阵是存在的。如果用协方差矩阵Σx 的特征向量作变换的基向量,即由Σx 的特征向量作为正交变换的变换矩阵,就可以得到对角线型的变换域协方差矩阵Σy 。K-L变换就是采用这种矩阵进行变换的正交变换,它可以在变换域完全解除相关性,因此是理论上的最佳变换。同时,换一个角度也可以证明,K-L变换是均方误差最小准则下的最佳变换,即当压缩比确定的情况下,采用K-L变换后,重建图像的均方误差比采用任何其他正交变换的都小。

但是回顾之前进行的K-L变换,哪个步骤可以称为图像压缩的切入点呢?一幅大小为M×N的图像,它的协方差矩阵Σx大小为MN×MN。由上述K-L变换理论可知,对X进行K-L变换的变换矩阵就是Σx的特征向量矩阵,该矩阵大小亦为MN×MN,其大小远远大于原始图像数据矩阵。而且要在解码时恢复原图像,不但需要变换后的系数矩阵Y,还需要知道逆变换矩阵(也就是变换矩阵的转置)。如果不经过任何处理就这样直接将K-L变换用于数字图像的压缩编码,不但达不到任何数据压缩的效果,还极大的增加了数据量。即使仅保留一个最大的特征值,变换矩阵中和该特征值对应的特征向量为M×N维,系数矩阵 Y 保留的元素为一个。要重建图像数据,需要保留的元素个数为仍大于原矩阵,所以达不到压缩的目的。另外,求一个矩阵的协方差矩阵和特征向量矩阵,都是非常复杂的运算过程,需要大量的计算。当X比较大时,运算时间的耗用可能是非常大的。有时甚至会出现因为过于复杂而导致Σx和变换矩阵无法求解的情况。


要解决上述问题,可以考虑将图像分成若干个小块,然后对每个小块分别进行K-L变换(这与本章前面的处理方式基本保持一致)。这样使得Σx和变换矩阵都比较小,计算机处理起来比较容易而且速度快。这里仍然将图像划分为多个不重叠的8×8小块(当图像垂直和水平方向的像素数不是8的倍数时补0,使之均为8的倍数)。然后再分别对每一个小块执行K-L变换,变换矩阵的数目为K个,每个矩阵大小为64×64,仅变换矩阵就要记录K×64×64个数据,还是远远大于原始数据的个数M×N。是否可以让变换矩阵的数量变得少些,最好只保留一个变换矩阵。回忆前面做K-L变换的例子,变换矩阵的大小与输入矩阵的维度有关,而与样本数量无关,据此可以将每个8×8小块变成一个行向量(也就是一个64维的数组),原图中的每一个小方块都是一个64维的样本。所以最后只需要一个64×64的变换矩阵即可,它对于原图像的任意一个数据块都适用。这样的处理方式并不是完全意义上的K-L 变换,因为采用分块的处理方式,各个数据块之间的相关性是没有消除的。但实验亦表明,这样的K-L 变换虽然不能完全消除图像各像素点之间的相关性,也能达到很好的去相关效果,在去相关性性能上优于离散余弦变换。


图像数据经K-L变换后,得到的系数矩阵Y大部分系数都很小,接近于零。只有很少的几个系数的数值比较大,这正是K-L变换所起到的去除像素间的相关性,把能量集中分布在较少的变换系数上的作用的结果。据此,在图像数据压缩时,系数矩阵Y保留M个分量,其余分量则舍去。在实际编程开发中,经K-L变换后的系数矩阵中的数值都是按从大到小的顺序排列的,所以直接舍去后面的64M个分量即可。通过这一步的处理,便可动态地调节压缩编码系统的压缩比和重建图像的质量。解码时,首先做K-L逆变换,然后将上述过程逆转,可以得到重建后的图像数据矩阵。


我们在MATLAB中编写的示例程序演示了运用上述方法对图像实施基于K-L变换的压缩处理的过程。最后可以通过编程实现基于K-L变换的图像压缩算法并测试其压缩效果,所得之测试结果如图6-22所示。该程序验证了三种不同的压缩比,即舍去排序后的系数矩阵中的32/64(对应压缩比50%)、48/64(对应压缩比75%)以及56/64(对应压缩比87.5%)。相关测试程序源码读者可以从本书的在线支持资源中下载得到。


最后需要补充说明的是尽管K-L变换可以将数据之间的相关性完全去除,所以理论上是一种最理想的数据压缩方案,但它在实际应用过程中仍然受到很大局限。例如,它没有快速算法,不同的图像所对应的变换矩阵也不同,从这个角度来说,单纯将K-L变换直接应用于图像数据压缩的理论价值要大于实际价值。它的存在意义,一方面是可以作为理论验证的参考模板,另一方面就是需要对原始算法加以改进后再付诸应用。




6.4.2 主成分变换的推导

前面提到的一国经济增长与城市化水平关系的问题是典型二维问题,而协方差也只能处理二维问题,那维数多了自然就需要计算多个协方差,所以自然会想到使用矩阵来组织这些数据。为了帮助读者理解上面给出的协方差矩阵定义,在此举一个简单的三维的例子,假设数据集有 {x,y,z} 三个维度,则协方差矩阵为


可见,协方差矩阵是一个对称的矩阵,而且对角线是各个维度上的方差。下面通过一个例子来尝试演算协方差矩阵(很多数学软件都为该操作提供了支持)。需要提醒读者注意的是,协方差矩阵计算的是不同维度之间的协方差,而不是不同样本之间的。例如有一个样本容量为 9 的三维数据,如下


根据公式,计算协方差需要计算均值,那是按行计算均值还是按列呢,前面也特别强调了,协方差矩阵是计算不同维度间的协方差,要时刻牢记这一点。样本矩阵的每行是一个样本,每列为一个维度,所以要按列计算均值。经过计算,不难得到上述数据对应的协方差矩阵如下


众所周知,为了描述一个点在直角坐标系中的位置,至少需要两个分量。图6-17所示是两个二维数组,其中左图显示的各个点之间相关性微乎其微,而右图所示的各个点之间则高度相关,显然数据散布在一定角度内较为集中。对于右图而言,只要知道某个点一维分量的大小就可以大致确定其位置,两个分量中任一分量的增加或者减少都能引起另一分量相应的增减。相反,左图中的情况却不是这样。


对之前给出的协方差矩阵定义式稍加改写,以使其获得计算上更为直观的便利。则有在X矢量空间(或坐标系下),协方差矩阵Σx的无偏计算公式为


表6-2给出了对于图6-17中左图所示的6个样本点的集合,以及经计算后求得的样本集协方差矩阵和相关矩阵的结果。应当注意,协方差矩阵和相关矩阵二者都是沿对角线对称的。从相关矩阵来看,各个数据分量间存在不相关关系的明显事实就是协方差矩阵(以及相关矩阵)中非对角线元素都是零。

最终计算可得





1.1.3 函数的极限


本小节介绍两个重要的函数极限,并讨论它们的应用。

重要极限1:


此外,该重要极限的另一种形式也常常被用到,即


综上,结论得证。
由此,也很容易推出如下结论,证明从略,有兴趣的读者可以自行尝试推导




1.3.2 内积与外积


因为cos(π/2)=0。当然,这也是众多教科书上介绍向量内积最开始时常常用到的一种定义方式。但必须明确,这种表示方式仅仅是一种非常狭隘的定义。如果从这个定义出发来介绍向量内积,其实是本末倒置的。因为对于高维向量而言,夹角的意义是不明确的。例如,在三维坐标空间中,再引入一维时间坐标,形成一个四维空间,那么时间向量与空间向量的夹角该如何解释呢?所以读者务必明确,首先应该是给出如本小节最开始时给出的内积定义,然后才能由此给出二维或三维空间下的夹角定义。在此基础上,我们来证明余弦定律。



若根据a·b = |a||b|cosθ这个定义,因为0<=cosθ<=1,显然柯西-施瓦茨不等式是成立的。但是这样的证明方式同样又犯了本末倒置的错误。柯西-施瓦茨不等式并没有限定向量的维度,换言之它对于任意维度的向量都是成立的,这时夹角的定义是不明确的。正确的思路同样应该从本小节最开始的定义出发来证明柯西-施瓦茨不等式,因为存在这样一个不等式关系,然后我们才会想到内积与向量模的乘积之间存在一个介于0和1之间的系数,然后我们才用cosθ来表述这个系数,于是才会得到a·b = |a||b|cosθ这个表达式。下面就来证明柯西-施瓦茨不等式。


证明:

与内积类似,向量a,b的外积也可以狭义地定义为






1.4.5   卷积定理及其证明


卷积定理是傅立叶变换满足的一个重要性质。卷积定理指出,函数卷积的傅立叶变换是函数傅立叶变换的乘积。换言之,一个域中的卷积对应于另一个域中的乘积,例如,时域中的卷积对应于频域中的乘积。


这一定理对拉普拉斯变换、Z变换等各种傅立叶变换的变体同样成立。需要注意的是,以上写法只对特定形式的变换正确,因为变换可能由其它方式正规化,从而使得上面的关系式中出现其它的常数因子。
下面我们来证明时域卷积定理,频域卷积定理的证明与此类似,读者可以自行证明。
证明:将卷积的定义


傅立叶变换的作用在频域对信号进行分析,我们可以把时域的信号看做是若干正弦波的线性叠加,傅立叶变换的作用正是求得这些信号的幅值和相位。既然固定的时域信号是若干固定正弦信号的叠加,在不改变幅值的情况下,在时间轴上移动信号,也就相当于同时移动若干正弦信号,这些正弦信号的相位改变、但幅值不变,反映在频域上就是傅立叶变换结果的模不变、而相位改变。所以,时移性质其实就表明当一个信号沿时间轴平移后,各频率成份的大小不发生改变,但相位发生变化。
既然这里提到了傅立叶变换的性质,这里我们还将补充一些关于帕塞瓦尔定理的有关内容。该定理最早是由法国数学家帕塞瓦尔(Marc-Antoine Parseval)在1799年推导出的一个关于级数的理论,该定理随后被应用于傅立叶级数。帕塞瓦尔定理的表述是这样的:




综上所述,原结论得证。
前面我们也介绍过复数形式的傅立叶级数,下面我们来推导与复数形式傅立叶变换相对应的帕塞瓦尔等式。这里再次给出傅立叶级数的复数形式表达式,具体推导过程请读者参阅前文



帕塞瓦尔定理把一个信号的能量或功率的计算和频谱函数或频谱联系起来了,它表明一个信号所含有的能量(功率)恒等于此信号在完备正交函数集中各分量能量(功率)之和。换言之,能量信号的总能量等于各个频率分量单独贡献出来的能量的连续和;而周期性功率信号的平均功率等于各个频率分量单独贡献出来的功率之和。


1.1.2 级数的敛散


关于上面这个级数敛散性的讨论,在数学史上曾经是一个非常有名的问题。大数学家莱布尼兹曾经在惠更斯的指导下对级数的敛散性进行过研究。后来莱布尼兹的学生伯努利兄弟(雅各·伯努利和约翰·伯努利)从他们老师的某些研究成果出发,最终证明了调和级数的发散性,以及几何级数的收敛性。但是几何级数最终收敛到多少这个问题却一直困扰着他们。最终,雅各布也不得不带着几分绝望的恳求宣告了他的失败:“如果有人能够发现并告知我们迄今为止尚未解出的难题的答案,我们将不胜感谢。”所幸的是,几何级数到底等于多少这个难题最终被约翰·伯努利的学生欧拉所破解。欧拉使用了一种极其巧妙的方法得出





1.1 极限及其应用


极限的概念是微积分理论赖以建立的基础。在研究极限的过程中,我们一方面会证明许多在图像处理中将要用到的公式,另一方面还会得到所谓的自然常数(或称纳皮尔常数)。图像处理技术中的很多地方都会遇到它,例如用来对图像进行模糊降噪的高斯函数,以及泊松噪声中都会有自然常数出现。而且在本文稍往后的内容还会讲到欧拉公式,届时自然常数还将会再次出现。

1.1.1 数列的极限






1.3.7 曲面积分





关于这部分内容的讨论,既阐明了第二类曲面积分的实际意义,其实也明确了两类曲面积分之间的关联。需要说明的是,在后面的介绍中,我们将更多地采用通量这个提法来替代此前所用的流量。通量是更广义的说法,如果考虑的向量场是流速场的话,那么通量就是流量,如果考虑的是电场或者磁场的话,那么通量就是电通量或者磁通量。






在泛函分析中,索伯列夫空间并不像 巴拿赫空间或者希尔伯特空间那么引入注意。但是在图像处理中,索伯列夫空间在介绍BV空间(有界变差函数空间)时,会被提到。而BV函数空间对于理解TV算法(偏微分方程在图像处理中的重要内容)至关重要!所以我特别在“图像处理中的数学原理详解”系列文章中留出一个小节来对索伯列夫空间进行必要的介绍。


2.3.7 索伯列夫空间



由广义导数的定义可以看出,这种导数不是关于函数的个别点处局部性质反映,因为它是通过在整个区间上积分的极限来确定的,而积分是一种关于函数的整体性质的概念。但也应该指出,广义导数其实是对通常意义下导数概念的推广。如果函数本身是通常意义下可微的,则其导函数与广义导数是一致的。






2.3.5 内积空间

      前面我们已经讨论过关于内积的话题,此处以公理化的形式给出内积的定义。





2.3.2 距离空间
        尽管在线性空间上我们已经可以完成简单的线性运算,但这仍然不能满足我们的需求。为了保证数学刻画的精确性,还必须引入距离的概念。本文最初是从极限开始讲起的,它是因此微积分的必备要素之一,而极限的概念显然也是基于距离上无限接近这样一种角度来描述的。



       由此,在距离空间中,可以引入“任意逼近”的概念,即极限概念。一般来说,一个集合如果能够在其中确切地引入任意逼近的概念,就称之为“拓扑空间”。而距离空间是一种最常用的拓扑空间。





2.3  泛函与抽象空间

牛顿说:“把简单的问题看得复杂,可以发现新领域;把复杂的问题看得简单,可以发现新规律。”而从历史的角度来看,一个学科的发展也亦是如此。随着学科的发展,最开始的一个主干方向会不断衍生出各自相对独立的分支,这也就是所谓“把简单的问题看得复杂”的过程。然而,一旦学科发展到一定程度之后,某些分支学科又开始被抽象综合起来,这也就是所谓“把复杂的问题看得简单”的过程。例如,在很长一段时间里,物理学家们都把电和磁看成是两种独立的物理现象在研究,当学科研究积累到一定程度时,麦克斯韦就创立了电磁学从而完成了物理学中的一次大综合。而在数学发展的历史中,几何与代数也曾经在很长的一段时间里是彼此独立的。直到笛卡尔引入了直角坐标系的概念之后,人们才开始建立了一种代数与几何之间的联系,也就是所谓的解析几何。泛函分析也是对以往许多数学问题或者领域进行高度抽象和综合的结果,其主要研究对象之一是抽象空间。其实在学习线性代数的过程中,读者已经建立了一种从矩阵到线性方程组之间的一种联系。而在泛函分析中,实数系、矩阵、多项式以及函数族这些看似关联不大的概念都可以抽成空间。由于泛函分析是一门比较晦涩抽象的学问,读者应该注意联系以往学习中比较熟悉的一些已知的、具体的概念,从而帮助自己理解那些全新的、抽象的概念。此外,需要说明的是本部分内容的重点在于有关定义或者概念的介绍,希望读者能够努力领会这些定义或者概念。

2.3.1  线性空间



2018-04-27 14:41:53 jayandchuxu 阅读数 350

矩阵的特征值、特征向量的概念

这里,我们讨论的是n阶的方阵A

定义

从向量的定义可知,它是方向和长度的结合体。当一个线性变换A作用在n维线性空间V中的某一非零向量x上时,便是对该向量的长度和方向进行变化。然而,存在一些向量,线性变换A并没有改变其方向,而只是改变了长度,这种向量,叫做线性变换A特征向量,它在变换中被改变的倍数,叫做它的特征值。用数学公式表示这一概念,即:

Ax=λx(1)

其中,λ的个线性变换A的某一个特征值。从公式上可以轻易发现,如果某一向量x是线性变换A的特征向量,那么与其方向相同的任意长度(不为零)向量,都是A的特征向量,并且属于同一个特征值λ。由于相同方向的特征向量具有相同特征值,我们可以同特征值来描述这一族向量(同一个特征值,可以有多个方向的特征向量)。
从公式(1)中,可以看出特征向量和特征值的计算方法:
|λEA|=0(2)
(λEA)x=0(3)

对应于同一个线性变换A,可以有多个特征向量(方向不同),但是有多个特征向量可以对应同一个特征值。 一个向量是一个方向,两个不同方向的向量就可以张成一个空间。在相同特征值的特征向量张成的空间内,任何一个向量在变换A下,都有相同的放大倍数λ

公式(2)的左侧,总可以展成如下形式的多项式:

|λEA|=λn(a11+a22++ann)λn1++(1)n|A|

所以求特征值就是求下面方程的解:

λn(a11+a22++ann)λn1++(1)n|A|=0(4)

关于从方程(4)得到的特征值,有几个比较重要的结论(参考资料1):

  1. n阶矩阵在复数范围内,一定有n个特征值(重特征值按重数计算个数)。
  2. n阶矩阵在实数范围内有多少个特征值是不一定的
  3. n阶实对称矩阵可以看成是一个特例,因为它一定有n个实特征值(重特征值按重数计算个数)。如果其中一个特征值λ=0,矩阵的秩r(A)=k,(0<k<nk是正整数),则λ=0恰为Ank重特征值。
  4. 如果 n阶矩阵A不是对称矩阵,那么,λ=0至少为Ank重特征值。

关于特征值和特征向量的理解,参考资料3写的也很好,知乎上有很多大神的回答直击要害,对问题的理解很有帮助。

作用

参考资料4中,认为矩阵的变换有三个作用:旋转拉伸投影
A是一个n×n方阵时,只涉及到旋转,拉伸。如果矩阵在实数域内可以得到n个特征值(重特征值按重数计算个数),那么利用其对应的特征向量(单位化后)组成矩阵正交Q可以使得:

A=QΛQ1

其中正交矩阵Q起到旋转作用(旋转矩阵都是正交矩阵,且行列式都为1),对角矩阵Λ起拉伸作用。
当矩阵不是方阵而是m×n时,可以对其进行SVD分解
在之前,想研究一下正交矩阵。

正交矩阵

按照定义,正交矩阵是QQT=E,它的行列式为1或者-1。

正交矩阵的性质

了解正交矩阵的性质,在很多计算方面,能够更深入了解所进行的运算的意义。
我们这里说的都是有限维欧式空间内的正交矩阵

  1. 正交矩阵的转置伴随矩阵、之间的积矩阵都是正交矩阵;
  2. .每一行(列)都是单位向量
  3. 任意两行或两列相互垂直
  4. 其行列式等于±1

假设n维欧式空间Rn中,一个正交变换Q存在一个一一对应的正交矩阵Q。所以研究正交变换的性质,可以转为研究正交矩阵。
根据正交矩阵行列式的值,将其分为两类:|Q|=1,为第一类;|Q|=1,为第二类。
第一类正交矩阵,当其左乘一个向量时,几何意义是使该量在Oxyz坐标系下旋转;
第一类正交矩阵,当其左乘一个向量时,几何意义是使该向量沿Oxyz某一轴(点)进行反射;[5]
无论是哪一类正交矩阵,其左乘向量,均不会改变向量的长度,即|Qv|=|Q||v|=|v|
所以上面将矩阵A拆成A=QΛQ1的形式后,由于Q是正交矩阵,它作用在向量v上,只是对其进行旋转或者反射,而对向量长度有影响的是矩阵Λ。其上的元素由矩阵A的特征值组成。
需要注意的是,只有当矩阵A能够在实数域内有n个特征值(重数也计入)的情况下,可以如此分解。但是,对更多的一般性矩阵A,在实数域内没有n个实特征根,或者是更一般的m×n维矩阵,此时,我们用SVD分解的方法进行研究。

SVD分解

协方差

假设有两个变量XY,他们的取值为X={x1,x2,,xn}Y={y1,y2,,yn},他们的平均值(期望)记为是E(X)=X¯=1nxiE(Y)=Y¯=1nyiXY的协方差就是研究两个变量之间的相关关系。比如当一个的取值不断增大时,另一个变量的取值如何变化,知乎上的一篇文章( 如何通俗易懂地解释「协方差」与「相关系数」的概念?)讲的很好。

根据奇异值分解

n×n阶矩阵按特征值分解相似,任一m×n阶矩阵A也可以写成类似的形式:

A=UΣVT(5)

那么得到的U是一个m×m的方阵(里面的向量是正交的,U里面的向量称为左奇异向量),Σ是一个m×n的矩阵(除了对角线的元素都是0,对角线上的元素称为奇异值),VT(V的转置)是一个n×n的矩阵,里面的向量也是正交的,V里面的向量称为右奇异向量)。

求法

利用如下公式可以计算出各矩阵:

(ATA)vi=λivi(6)

δi=λi(7)

ui=1δiAvi(8)

对方程计算,得到的v,就是的右奇异向量σ就是奇异值u就是左奇异向量

作用

当矩阵A=UΣVT左乘一个向量v时,只有Σ对向量的长度进行了拉伸(收缩),而矩阵UV都只是对其进行旋转或反射。当作用在图像上时,也只有Σ对图像进行了各个方向上的伸缩改变。

用奇异值分解图像

这里写图片描述
用奇异值的方法,将这幅图像进行分解,得形如A=UΣVT格式的矩阵。其中Σ是由矩阵奇异值由大到小排列组成的对角矩阵。
我们分别保留前10,30,100,300个奇异值,其余奇异值设为0,比较图像的变化:
奇异值保留前10
奇异值保留前10
奇异值保留前30
奇异值保留前30
奇异值保留前100
奇异值保留前100
奇异值保留前300
奇异值保留前300。

代码

import cv2
import numpy as np
from numpy import linalg as la  # 用到别名
from scipy.misc import imsave

import scipy
im = cv2.imread('lena512.bmp')
print(im.shape)
gray = cv2.cvtColor(im, cv2.COLOR_BGR2GRAY)
U, Sigma, VT = la.svd(gray)
print('矩阵U的形状:', U.shape, '    矩阵Sigma的形状:',
      Sigma.shape, '    矩阵VT的形状:', VT.shape)
se = np.eye(512, dtype=np.float64)
n = 512
i = 0
k = 30  # 保留特征值数目
# 改变特征值
while i < n:
    if i > k - 1:
        Sigma[i] = 0
    se[i, i] = Sigma[i]
    i += 1

svt = np.dot(se, VT)
usvt = np.dot(U, svt)
imsave('USVT_Sigma=30m.bmp', usvt)

参考资料

  1. 秦川, 李小飞. 方阵的秩与特征值的关系[J]. 课程教育研究:学法教法研究, 2015(27):120-120.
  2. 如何通俗易懂地解释「协方差」与「相关系数」的概念?
  3. 如何理解矩阵特征值?马同学的回答
  4. 矩阵的特征值分解与奇异值分解的几何意义
  5. 杜美华, 孙建英. 正交变换的几何意义及其应用[J]. 哈尔滨师范大学自然科学学报, 2014, 30(3):36-39.
2013-09-26 23:21:17 F_SUNNY 阅读数 2167

     从事图像处理这个行当也已经有一段时间了,对于一个自动化毕业的本科生,确实是磕磕绊绊的走到现在了,前期的基础图像处理还基本上能够轻松上手,越到后面的机器学习算法,用到的数学知识也就越深了,所以越到后面会越困难的。现在回想下之前的图像处理基础算法,其实是可以归纳到数学各个领域的。下面简单介绍下一些基础图像处理算法,当然主要是讲自己对其的归类理解,有不对的之处,大伙一起探讨。如果想要这些算法的具体实现,给推荐几个博客(百度的),我也是从这些类似的博客起步的:

http://www.cnblogs.com/drizzlecrj/archive/2008/02/25/1077494.html

http://blog.csdn.net/xizero00/article/details/6631209

     主要的基础图像处理算法有:灰度化,二值化,投影法,差影法,图像采样,增强,分割,边缘提取,匹配等。

    下面讲讲这些算法最基础实现时按照数学知识归类:

     1. 初等代数类:

  ①.灰度化:一般灰度化是用加权平均的,这个在我们小学都可以解决了,f(i,j)=0.30R(i,j)+0.59G(i,j)+0.11B(i,j));

②二值化:其实二值化就是一个分段的0-1函数;

③差影法:这类的帧差发,前景提取法,都是一个减法,当然如果有背景建模之类的,那就背景建模的算法就属于高等代数或者概率统计的知识了;

④图像锐化:一般的图像锐化算法也是相邻像素点之间的初等代数运算,运算如下:

设f(i,j)像素为(r1, g1, b1) , f(i-1,j-1)像素为(r2,g2,b2), g(i,j)像素为(r,g,b),则
r = r1 + 0.25 * |r1 - r2|
g = g1 + 0.25 * |g1 - g2|
b = b1 + 0.25 * |b1 - b2|

⑤图像的叠加,浮雕效果等也都是属于初等代数的;

    2.概率统计类:

①.投影法:像直方图统计之类的,是属于统计类的;

②.匹配算法:当然匹配算法也可以用线性代数,高等代数做,但是像方差匹配之类是属于概统的;

③图像采样:一听采样就知道是概统的,其中有图像区域采样,随机采样,分布采样,上/下采样;但是一般的采样算法都要结合代数知识进行应用,比如对图像感兴趣区域进行提取,可能还要用到插值算法进行归一化之类的;

     3.高等代数:

①边缘提取:这主要用到的是一阶二阶微分,卷积等知识,这些都是高等代数中的基础;

②图像滤波:卷积滤波,高通滤波;

这有一片关于图像卷积实现方法的文章,讲的很好:

http://blog.sina.com.cn/s/blog_4bdb170b01019atv.html

     4.几何学:

这部分主要是在于图像中物体的形态特征的描述,像圆,直线,曲线,方形等几何图形的特征描述算子,了解这些可以进行物体的特征提取判别;

还有就是角度,使用正余弦定理结合线性代数,可以进行图像线性匹配;

     5. 线性代数:

其实个人认为线性代数也是属于高等代数,线代的矩阵问题也是可以转换为高等代数的方程计算的,当然高等数学的方程,转换为矩阵的话,计算起来会更加形象化,还会有很多简化算法;

①PCA降维:这个是基础的人脸识别算法,很好的引用了矩阵的特征值,特征向量等知识,是经典算法;

②匹配:结合几何等特征,可以对图像进行线性匹配;

③非线性的线性化,通过类hogh等变换,可以将高维非线性数据,线性化进行处理,这样可以提高效率,简化算法。


在图像基础处理算法中很多其实是各种数学知识的综合,要灵活应用各种数学知识才能更加高效率的对图像数据进行处理。这也足见数学知识对于图像处理的重要性,但是一些很简单的图像处理算法,其实用很简单的数学知识就能解决,所以学起来也要有信心,从简单到困难,一步一步脚踏实地的来。

以上属于个人的一点看法,如果不对,请各位武林高手指正补充。


2018-11-20 21:50:32 StephenArk 阅读数 360

4.2 机器学习、人工智能、图像处理、图像识别导论

最近在看机器学习的书。之前一直搞不清这几个概念,而且以为都是某种“黑魔法”,但其实都是数学方法,所谓的什么“黑盒子”,其实也不黑。这些领域都是相互交错的,但每一个领域又方向不一样。

4.2.0 前导知识

上面提到许多都是数学方法,那么就需要先学习一些数学知识。将会用到的有:

  • 微积分(高数)
  • 线性代数
  • 概率论与统计
  • 离散数学(用的没有上面三门多)

下面介绍中我会指出上面这些数学的一些应用。

4.2.1 机器学习

以一个简单的线性回归的例子来直观解释一下什么是机器学习。

高中的时候不是有时候会要作线性回归图嘛(叫拟合还是什么来着),给你一些散点让你作一条线尽可能过最多的点。然后通过这条线我们就可以预测下一个x对应的y

线规图

我们假设这条直线是y=wx+by = wx + b。机器学习中喜欢用w而不是kw表示weight权重,b表示bias偏移,这对应了线代中的“仿射变换”概念,在这里不展开。

我们用yi\overline{y_i}表示(wxi+b)(wx_i + b)的预测值,用yiy_i表示每个点的实际值,那么每个点的误差就是yiyiy_i-\overline{y_i}。我们把每个点误差(残差,用eie_i表示)的平方相加,得到一个“平方损失函数”来衡量这条线拟合的“好坏”。还记得方差(统计)吗?

方差D(x)=[xE(x)]2D(x) = \sum[x-E(x)]^2,其中E(x)x的期望。方差可以衡量数据的偏离程度。

而这里损失函数loss=ei2=(yiyi)2loss = \sum e_i^2 = \sum (y_i-\overline{y_i})^2,是不是和方差很像?所以它也可以表示数据偏离程度。

我们要让曲线“最好”,就是要优化wb,让损失函数lossloss最小。如何做到呢?这里我们要调整wbloss(w, b)最小。对于w,形容wlossloss的影响的是对w的偏导(微积分):loss(w,b)w\frac{\partial loss(w, b)}{\partial w}

那么我们调整w=wαloss(w,b)ww = w - \alpha \frac{\partial loss(w, b)}{\partial w}。其中α\alpha是一个常数,称为“步长”。

同样b=bαloss(w,b)bb = b - \alpha \frac{\partial loss(w, b)}{\partial b}。可见最后w和b会逼近最佳的那两个参数,而α\alpha决定了逼近的速度。

事实上上面两个偏导数物理意义是梯度,详细的不展开。但是可以想象当函数越接近极小值时,它的导数也越小;另外,如果我们“走过了”,导数就会变成负数(假设一开始是正的,走过了就会变成相反),就会又“走回来”。所以我们最终会逼近这个极小值。

可见上面的例子中需要多次的重复计算,所以用计算机来解决再合适不过了。这就是机器学习,上面这个算法是经典的梯度下降算法。一般来说用机器学习来解决问题指的是将问题转化成数学模型,然后再想办法优化模型使它接近问题。这样,我们就可以用模型来“预测未来”了。

4.2.2 人工智能

人工智能主要指的是人工模拟人脑思考的科学。

我们知道人脑的工作原理是一个个神经元之间互相通电。为了模拟人脑研究者提出了模拟神经的网络结构。从最早的感知机,到各种神经网络,到SVM,都是网状结构。

从下面一个例子来直观感受一下神经网络。

神经网络工作流程

可见这里我们的样本值y是由两个“特征值”x1x2x_1 x_2决定的,既y=F(μ(x1),ν(x2))y = F(\mu(x_1), \nu(x_2))

见下图,我们的神经网络有x1x2x_1 x_2两个输入,经过线性变换到达隐藏层,隐藏层的神经元中的函数叫激活函数,一般为某种非线性变换。在这里,激活函数是两个logsig(logistic)函数:

logsig(x)=11+exlogsig(x) = \frac{1}{1+e^{-x}}

可见logsig(x)是一个属于(0, 1)的数,正好我们的样本值都是在这个区间里的。同样为了控制我们的输出属于(0, 1),我们在输出层也使用了一个logsig函数。

输出了yi\overline{y_i}后,我们同样比较它与yiy_i的误差,和上面梯度下降的例子一样,我们计算出lossloss,然后根据lossloss调整每一层的参数。这可以看作为一种“后向传播”。

流程1-2

流程3-4

流程5-6

流程7-8

流程9-10

流程11-12

其实这也是一种机器学习的算法,只不过模型比较复杂。当问题规模更大的时候层数和神经元数上涨,最后变得非常多,很难一步步的去分析每一层发生了什么,所以索性把它看成一个黑盒子,其实它不“黑”。

可见人工智能就是运用某一类机器学习算法来在某些问题上模拟人的思考,是一种机器学习的应用。

4.2.3 图像处理

图像处理叫Image Processing,要讲图像识别我们得先讲图像处理。

顾名思义,图像处理就是对图像进行各种“ps”,什么放缩旋转裁剪就不说了,还有什么高斯模糊滤镜啦,风格化啦,调明暗色调啦等等,会用ps的同学可能会更容易理解。

首先要讲图像的构成。一个图像其实是一个矩阵(线代),或一个二维数组,是由一个个像素组成的。而每一个像素又包括R、G、B三条通道。红绿蓝,三原色。从物理上来看呢,一个屏幕有三层,分别发出红绿蓝三种光。要让屏幕颜色不一样只需要调节三种光的亮度,三种光都最亮时就是白色,都为最暗就是黑色(大概是这么个意思,但实际屏幕发光的原理远比这要复杂)。我们认为把亮度分为了256级(8bit存储),(255, 255, 255)就是白色(#FFFFFF),(255, 0, 0)就是大红色(#FF0000)。如果R = G = B,就是不同灰度的灰色。

顺带一提,可以想象电脑屏幕可以显示的颜色有限,现实中有的颜色不能全部表示。此外,彩色印刷时采用的是另一套叫CYMK的颜色表示法,可另作了解。

那么图像处理就是对每个像素的RGB值进行处理。例如,我们让每个像素的R=G=B=R+B+G3R = G = B = \frac{R + B + G}{3},就把每个像素转换成了灰色,图像就成了灰度图。又比如,我们用一个滤波矩阵对图像进行二位卷积(线代),可以对图像进行锐化、平滑、边缘检测等,取决于滤波矩阵。

4.2.4 图像识别

图像处理可以单独视为一个应用领域,各种美图啊相机啊啥的都会用到。但是说到图像识别,也必须要用到图像处理。

比如说我们要识别手写数字,那我们希望只保留图片里面的数字,这时就要“去噪”,也就是用图像处理把其它不要动信息去掉。

图像识别又分了几个方向,有物体检测、图像分类、人脸识别等等。大部分都是用卷积神经网络实现的。卷积神经网络和我们上面说到的滤波有很大关系。

和滤波一样,我们用卷积核对图像进行卷积,可以得到一个过滤了你想要的图形之外像素的图像。

卷积核

卷积图像

然后一般的,我们有一个“池化层”,可以把图像更进一步缩小。使用这样的网络就能提取出一个特征,往往我们把许多特征识别出来,然后组合,就知道这个图像画的是个什么玩意了。下图是max-pooling池化(选每个子矩阵中最大的那个组成新矩阵):

池化层

2016-07-26 09:49:21 qq_19891827 阅读数 1227
图像处理,听起来是个十分高深的学问,貌似需要用到一些很深奥的数学知识,让人望而却步。其实在前端角度看,利用html5的canvas技术即可实现简单的图像处理,同时不需要很高深的数学知识,只要你有高中以上的数学水平,足矣。本篇博文主要探讨利用canvas技术,查找图像边缘的算法思路,同时贴出本人写出的查找边缘算法的详细代码。

在正式开始之前首先介绍两个处理图像问题常用的html5的API:

一、处理图像问题常用的html5的API.
(1).HTML5 canvas getImageData() 方法;
getImageData() 方法返回一个 ImageData 对象,该方法下的data对象,以一维数组的方式拷贝了画布指定矩形的像素数据。
对于 ImageData 对象中的每个像素,都存在着四方面的信息,即 RGBA 值:
R - 红色 (0-255)
G - 绿色 (0-255)
B - 蓝色 (0-255)
A - alpha 通道 (0-255; 0 是透明的,255 是完全可见的)。
简单来说,图像画面在网页中是以像素作为最小单位的,每幅图像以网格形式分为若干像素块,每一像素块上只有一种颜色,足够大量这样的像素块拼凑在一起形成了一幅完整的图像。以下图(左)中一朵花为例,将其放大一定倍数得到下图(右),可以看到图2中花朵被以网格形式分成若干块,这里的每一个块就是一个像素。



下面介绍一下图像颜色,网页中图像多以RGB颜色模式来呈现的,在RGB模式下图像通过3种颜色,R - 红色 (0-255),G - 绿色 (0-255),B - 蓝色 (0-255),将这3种颜色按不同比例混合后会得到其他任何颜色。
回到getImageData() 方法,该方法下data对象以一维数组形式保存了画布中所有图像的像素数据,每个像素中都保存着四个信息,除上面介绍的RGB颜色信息外,还保存了A - alpha 通道,也就是像素块的透明度情况.以画布中前两个像素为例,在data数组中的存储方式如下:data[0]="R(第一个像素点红色颜色值)",data[1]="G(第一个像素点绿色颜色值)",data[2]="B(第一个像素点蓝色颜色值)",data[3]="A(第一个像素点透明度信息)",data[4]="R(第二个像素点红色颜色值)",data[5]="G(第二个像素点绿色颜色值)",data[6]="B(第二个像素点蓝色颜色值)",data[7]="A(第二个像素点透明度信息)"......以此类推保存画布中图像的所有像素点信息。
语法:var imgData=context.getImageData(x,y,width,height);

参数 描述
x 开始复制的左上角位置的 x 坐标。
y 开始复制的左上角位置的 y 坐标。
width 将要复制的矩形区域的宽度。
height 将要复制的矩形区域的宽度

(2).putImageData() 方法:

将图像数据(从指定的 ImageData 对象)放回画布上。即将包含图像所有像素RGBA信息的对象,绘制为真实图像。
语法:context.putImageData(imgData,x,y,dirtyX,dirtyY,dirtyWidth,dirtyHeight);

参数 描述
imgData
规定要放回画布的 ImageData 对象。
x ImageData 对象左上角的 x 坐标。
y
ImageData 对象左上角的 y 坐标。
dirtyX
水平值,在画布上放置图像的位置。
dirtyY
水平值(y),在画布上放置图像的位置
dirtyWidth
在画布上绘制图像所使用的宽度
dirtyHeight
在画布上绘制图像所使用的高度

二、查找图像边缘算法思路
(1)黑白二值化:首先对图像进行黑白二值化处理,通过getImageData()方法获取画布中图像的所有像素的RGBA信息,以128为界,与data数组中每个RGBA值作对比,低于128则将其数值变为0,高于128将其数值变为255,经过此阶段处理后,图像中只保留黑、白两个颜色,图像的集合性质只与像素值为0或255的点的位置有关,不再涉及像素的多级值,使处理变得简单,而且数据的处理和压缩量小。下图(左)为原图,下图(右)为经黑白二值化处理后的图像。

               
具体前端javascript代码如下:
    

var cvs=document.getElementById('canvas');
    var HEIGHT=cvs.height;
    var WIDTH=cvs.width;
    var ctx=cvs.getContext('2d');
    var pixel = null;
    var opixel=null;
    var xpixel=null;
    var edge=[];
    var img=new Image();
    img.src='http://ui.yidaochn.com/test/zz.jpg';
    img.onload=function(){
        ctx.drawImage(img,0,0,WIDTH,HEIGHT);
        pixel = (ctx.getImageData(0, 0, WIDTH, HEIGHT));
        whiteBlack();
    };


 //黑白二值化
    function whiteBlack(){
        var red=0;
        var green=0;
        var blue=0;
        var index=null;
        var average=null;
        for(var i=0;i<HEIGHT;i++) {
            for (var j = 0; j < WIDTH; j++) {
                index=(pixel.width*i+j)*4;
                red=index;
                green=index+1;
                blue=index+2;
                average=Math.round((pixel.data[red]+pixel.data[green]+pixel.data[blue])/3);
                if(average>=128){
                    pixel.data[red]=255;
                    pixel.data[green]=255;
                    pixel.data[blue]=255;
                }else{
                    pixel.data[red]=0;
                    pixel.data[green]=0;
                    pixel.data[blue]=0;
                }
            }
        }
        ctx.putImageData(pixel,0,0);
    }


(2)边缘查找:经过黑白二值化处理后的图像仅保留两种颜色(黑、白),对存有该图像RGBA值信息的data数组进行遍历,每个像素点上的RGB值一定为黑色(0,0,0)或白色(255,255,255)。所以这里我们仅仅比较每一像素点上R值(红色值)与其上、下、左、右相邻像素点的R值是否相等即可,如改点与上下左右4个点的R值相同说明该点不是图像图形的边缘,如该点与至少上下左右4个点其中一个点R值不同,则说明该点为图形边缘,以此类推遍历所有颜色值数据即可得到图像边缘。

具体前端javascript代码如下:(为便于观察,已将边缘颜色填充为红色)
   

function imageEdge(){
        opixel=ctx.getImageData(0,0,WIDTH,HEIGHT);
        var red=0;
        var index=null;
        var redVal=null;
        var prevRedVal=null;
        var nextRedVal=null;
        var topRedVal=null;
        var bottomRedVal=null;


        for(var i=0;i<HEIGHT;i++){
            for(var j=0;j<WIDTH;j++){
                index=(pixel.width*i+j)*4;
                red=index;
                redVal=pixel.data[red];
                prevRedVal=red-4>=0?pixel.data[red-4]:pixel.data[red];
                nextRedVal=pixel.data[red+4];
                topRedVal=(red-WIDTH*4)>=0?pixel.data[red-WIDTH*4]:pixel.data[red];
                bottomRedVal=pixel.data[red+WIDTH*4];


                if(redVal!=nextRedVal||redVal!=topRedVal||redVal!=prevRedVal||redVal!=bottomRedVal){
                    opixel.data[red]=255;
                    edge.push(red);
                }
            }
        }
        ctx.putImageData(opixel,0,0);
    }

经查找边缘操作后的图像如下图所示(边缘已标红),是不是觉得算法是如此简单,有种豁然开朗的感觉。


我对数学的认识

阅读数 1730

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