《基本图像变换》PPT课件.ppt

1/85,图像处理,彭晓东,图像工程,第五章 基本图像变换,2/85,第五章 基本图像变换,本章实质:频率域变换 重中之重:傅里叶变换,3/85,第5章 图象变换基础,为了有效和快速地对图象进行处理，常常 需要将原定义在图象空间的图象以某种形式转换到另外一些空间，并利用在这些空间的特有性质方便地进行一定的加工，最后再转换回图象空间以得到所需的效果。这些转换方法就是本章要着重介绍和讨论的图象变换技术 变换是双向的，或者说需要双向的变换。在图象处理中，一般将从图象空间向其他空间的变换称为正变换，而将从其他空间向图象空间的变换称为反变换或逆变换,4/85,第5章 图象变换基础,5.1 可分离和正交图象变换 5.2 傅里叶变换 5.3 沃尔什/哈达玛变换 5.4 离散余弦变换 5.5 Radon变换,5/85,5.1 可分离和正交图象变换,分离变换目的:简化计算,6/85,5.1 可分离和正交图象变换,1-D可分离变换 正变换 反变换,正向变换核,反向变换核,7/85,5.1 可分离和正交图象变换,2-D可分离变换 （傅里叶变换是一个例子）,反向变换核,正向变换核,变换核与 原始函数及 变换后函数无关,8/85,可分离 1个2-D变换分成2个1-D变换 对称 (h1与h2的函数形式一样),5.1 可分离和正交图象变换,9/85,可分离且对称,图象矩阵,对称变换矩阵,反变换矩阵,变换结果,5.1 可分离和正交图象变换,反变换,完全恢复,不完全恢复,10/85,正交 考虑变换矩阵： 酉矩阵（*代表共轭 ）： 如果A为实矩阵，且： 则A为正交矩阵， 式(5.1.3)和式(5.1.4)构成正交变换对,5.1 可分离和正交图象变换,11/85,5.2 傅里叶变换,5.2.1 2-D傅里叶变换 5.2.2 傅里叶变换定理 5.2.3 快速傅里叶变换,12/85,5.2 傅里叶变换,周期为 的周期函数用一系列三角函数 的和来表示为:,这种展开称为谐波分析。其中， 为直流分量， 为一次谐波（又做基波），而 依次称为二次谐波，三次谐波等等。,傅里叶级数（三角级数）,13/85,5.2 傅里叶变换,若函数,以,为周期的光滑或分段光滑函数，即为,将 展开为傅里叶级数,14/85,5.2 傅里叶变换,欧拉公式:,15/85,5.2 傅里叶变换,+,复数形式的傅里叶级数,16/85,5.2 傅里叶变换,傅里叶展开的复数形式,上式的物理意义为: 一个周期为2l 的函数,可以分解,为频率为,，复振幅为,的复简谐波的叠加,称为谱点，,所有谱点的集合称为谱对于周期函数,而言，谱是离散的,17/85,5.2 傅里叶变换,傅里叶变换对(三种):,(1),(2),(3),三者之间的关系:,18/85,5.2 傅里叶变换,傅里叶谱（频谱，幅度）,傅里叶相位角,傅里叶功率谱,19/85,5.2 傅里叶变换,傅立正反变换对是怎么确立的？,假设非周期函数,是一个周期函数,的周期,时的极限情况。由此，,的傅里叶级数展开式,在,时的极限形式就是所要寻找的非周期函数,的傅里叶展开,20/85,5.2 傅里叶变换,设不连续的参量,则傅立叶级数写为：,傅里叶系数为,21/85,5.2 傅里叶变换,对于系数,，若,有限，则,对于余弦部分：,当,，不连续参变量,变为,连续参量，以符号,代替对,的求和变为对连续参量,的积分。,22/85,5.2 傅里叶变换,同理可得正弦部分,23/85,5.2 傅里叶变换,若令,则傅里叶变换可表示为：,24/85,5.2 傅里叶变换,由欧拉公式得：,反变换,25/85,5.2.1 2-D傅里叶变换,1-D正变换 对1个连续函数 f (x) 等间隔采样,26/85,5.2.1 2-D傅里叶变换,1-D反变换 变换表达 频谱（幅度） 相位角,27/85,5.2.1 2-D傅里叶变换,二维傅里叶变换 频谱（幅度） 相位角 功率谱,28/85,5.2.1 2-D傅里叶变换,傅里叶频谱图，就是图像梯度的分布图。（实际上图像上某一点与邻域点差异的强弱，即梯度的大小，也即该点的频率的大小,29/85,5.2.1 2-D傅里叶变换,频率域 由傅立叶变换和频率变量( u, v)定义的空间 基本性质 （1）变化最慢的频率成分(u=0, v=0)对应一幅图像的平均灰度 （2）低频（原点附近）对应图像灰度变化慢的像素 （3）高频（远离原点）对应图像灰度变化快的像素,30/85,5.2.1 2-D傅里叶变换,31/85,5.2.2 傅里叶变换定理,0、分离性质 1次2-D 2次1-D O(N 4)减为O(N 2),32/85,1、平移定理,5.2.2 傅里叶变换定理,33/85,5.2.2 傅里叶变换定理,2、旋转定理,借助极坐标：,表明： 对 旋转 对应于将其傅里叶变换 也旋转 。 反之亦然。,34/85,5.2.2 傅里叶变换定理,旋转定理示例,例5.2.3,35/85,5.2.2 傅里叶变换定理,3、尺度定理(相似定理),原函数在幅度方面变化导致对其傅里叶变换在幅度方面产生对应的尺度变化。 原函数在空间尺度方面的缩放导致对其傅立叶变换在频域方面的相反缩放。,36/85,5.2.2 傅里叶变换定理,尺度定理,例5.2.4,37/85,4、剪切定理 （水平方向）纯剪切 （垂直方向）纯剪切,5.2.2 傅里叶变换定理,图5.2.5 (a)与(b),38/85,5、组合剪切定理 平移旋转尺度 水平剪切 垂直剪切,5.2.2 傅里叶变换定理,图5.2.5,39/85,6、仿射定理 u = (eu dv)/D和v = ( bu + av)/D,5.2.2 傅里叶变换定理,40/85,7、卷积定理 2-D,5.2.2 傅里叶变换定理,两函数在空间的卷积与其傅立叶变换在频率域的乘积构成一对变换 两函数在空间的乘积与其傅里叶变换在频率域的卷积构成一对变换,41/85,8、相关定理 互相关：f (x) 与g(x)不是同一个函数 自相关：f (x) = g(x) 2-D,5.2.2 傅里叶变换定理,42/85,5.2.3 快速傅里叶变换,直接进行一个N N的2-D傅里叶变换需要N4次复数乘法运算和N2(N2 1) 次复数加法运算 1-D：复数乘法和加法的次数都正比于N2 快速傅里叶变换（FFT）： 将复数乘法和加法的次数减少为正比于N log2N 逐次加倍法：复数乘法次数由N2减少为(N log2 N)/2 复数加法次数由N2减少为N log2 N,43/85,5.2.3 快速傅里叶变换,考察一维有限长序列x(n)(0=n=N-1)的傅立叶变换：,或记为Wn，Wn -1,44/85,5.2.3 快速傅里叶变换,计算复杂性：一个频率分量需N次乘法，N-1次加法 整个变换需N2次乘法，N(N-1)次加法,矩阵表示：,45/85,5.2.3 快速傅里叶变换,结论：系数多数相同，且具有对称性,例：N=4,最小无重复运算,N=4,46/85,5.2.3 快速傅里叶变换,N点的DFT转化为两个求N/2点的DFT,1965年，库利-图基提出把原始的N点序列依次分解成一系列短序列，减少乘法运算,47/85,5.2.3 快速傅里叶变换,48/85,5.2.3 快速傅里叶变换,49/85,5.2.3 快速傅里叶变换,50/85,5.2.3 快速傅里叶变换,51/85,5.2.3 快速傅里叶变换,52/85,完整的蝶形图如下页：,5.2.3 快速傅里叶变换,53/85,5.2.3 快速傅里叶变换,54/85,时间复杂性：Nlog2N 注意： 输出X(m)是以m从小到大排列，而输入序列x(n)不 是以n从小到大排列。 采用码位倒序法排序： 将自然顺序数转换成二进制数，然后首尾位倒序，再转换成十进制数，那么十进制数就是输入序列中的位置。 如：N=8 X(3)的位置是：011110(6),5.2.3 快速傅里叶变换,55/85,二维FFT,逆FFT,5.2.3 快速傅里叶变换,56/85,傅立叶变换注意的问题 两个缺点： (1)要进行复数运算，计算比较费时 实用中还采用如沃尔什(Walsh)变换等。 (2)很多图像的高频项衰减的很快，在频域不清楚。 解决方法：,5.2.3 快速傅里叶变换,57/85,5.3 沃尔什/哈达玛变换,5.3.1 沃尔什变换 5.3.2 哈达玛变换 5.3.3 关于两种变换的讨论 沃尔什和哈达码变换都是可分离和正交变换,58/85,5.3.1 沃尔什变换,正变换核 N = 2n bk(z)： z 的二进制表达中的第 k 位 如 n = 3 对 z = 6（1102） 有 b0(z) = 0，b1(z) = 1，b2(z) = 1 对 z = 2（102） 有 b0(z) = ?，b1(z) = ?，b2(z) = ?,59/85,5.3.1 沃尔什变换,N=4和8时的沃尔什变换核,60/85,5.3.1 沃尔什变换,正变换 变换核组成的矩阵是一个对称矩阵 并且其行和列正交（反变换核与 正变换核只差1个常数1/N） 反变换核 反变换,61/85,2-D沃尔什变换 正 反,5.3.1 沃尔什变换,62/85,2-D沃尔什变换核：可分离且对称 都可分成两步计算,每步计算用1D变换实现,5.3.1 沃尔什变换,正变换核,反变换核,63/85,5.3.1 沃尔什变换,沃尔什变换中,正向变换核与反向变换核只依赖于x,y,u,v，而与f(x,y)或W(u,v)的值无关。这些核可看一组基本函数，一旦图像尺寸确定，这些函数也就完全确定。,N=4时的二维沃尔什变换图5.3.1,64/85,5.3.1 沃尔什变换,65/85,5.3.1 沃尔什变换,离散傅里叶变换是浮点数的运算，因此计算量会比较大，而且浮点数运算产生的误差会比较大； 沃尔什变换矩阵的系数是1或是1，只需要使用加法即可实现，计算复杂度小； 离散傅立叶转换相当于把信号拆解成在不同频率的正弦函数与余弦函数的分量，而使用沃尔什转换相当于把信号拆解成在许多不同震荡频率的方波上，因此，除非所要分析的信号拥有类似方波组合的特性，否则沃尔什转换作频谱分析的效果会比使用离散傅立叶转换分析的效果要差，这是降低运算复杂度所要付出的代价。,66/85,5.3.1 沃尔什变换,沃尔什变换具有某种能量集中。而且原始数据中数字越是均匀分布，经变换后的数据越集中于矩阵的边角上。因此沃尔什变换可以压缩图像信息。且变换比傅立叶变换快。,67/85,正变换核 bk(z)：z 的二进制表达中的第 k 位 指数上的求和以2为模 正变换,5.3.2 哈达玛变换,N=8时，哈达玛变换核表5.3.2,68/85,反变换核 反变换核与正变换核只差1个常数1/N 反变换 用于正变换的算法也可用于反变换,5.3.2 哈达玛变换,69/85,2-D变换核 2-D变换对,5.3.2 哈达玛变换,70/85,5.3.2 哈达玛变换,二维哈达玛变换（正变换和反变换）都可分成两个步骤计算，每个步骤用一个1维变换实现。,71/85,5.3.3 关于两种变换的讨论,两种变换核里的数值都是1和-1，但是在行列的秩序上两者有所不同。（下页说明） 在绝大多数图像变换应用中，常混合使用沃尔什变换和哈达玛变换，所以被统称为“沃尔什哈达玛”变换，通常用来指两者中的任意一个。,72/85,阶（序） 列中符号变换的次数 表5.3.2中8列的序依次为0，7，3，4，1，6，2，5 随 u 增加而序也增加 的哈达玛变换核,5.3.3 关于两种变换的讨论,对比表5.3.2与表5.3.3,73/85,N = 8 时经过排序的1-D哈达玛变换核的值 行和列都满足序单增的条件,5.3.3 关于两种变换的讨论,74/85,哈达玛矩阵的迭代 方便地获得变换矩阵,5.3.3 关于两种变换的讨论,同样适合于哈达玛反变换,75/85,沃尔什变换和哈达玛变换比较 可分离且对称，正反变换核相同 行列正交（即各行向量与各列向量的 内积为0） 沃尔什变换特点 有快速算法（类似快速傅里叶变换） 哈达玛变换特点 有迭代性质,5.3.3 关于两种变换的讨论,76/85,一种可分离、正交、对称的变换 1-D离散余弦变换（DCT）,5.4 离散余弦变换,77/85,2-D离散余弦变换（DCT） 图5.4.2N=4时2D的DCT基本函数 + 可分离性和对称性,5.4 离散余弦变换,78/85,5.4 离散余弦变换,79/85,原始图像 傅立叶变换 离散余弦变换 沃尔什变换,5.4 离散余弦变换,80/85,5.4 离散余弦变换,可借助离散傅里叶变换的实部计算来进行（公式5.4.6) 可减少图像分块边界处的间断，在图像压缩中（特别是JPEG标准）中得到广泛应用。 与傅立里变换一样都定义在整个空间，任意变换域点都要用到所有原始数据的信息，被认为是全局基本函数。,81/85,5.5 Radon变换,Radon(拉东)变换是投影重建（第9章）的基础。,82/85,5.5 Radon变换,radon变换大致可以这样理解： 一个平面内沿不同的直线（直线与原点的距离为p，方向角为 ）对f（x，y）做线积分，得到的像F(p, )就是函数f 的Radon变换。,83/85,5.5 Radon变换,也就是说，平面（p， ）的每个点的像函数值对应了原始函数的某个线积分值。 直观的理解是，假设你的手指被一个很强的平行光源透射，你迎着光源看到的手指图