第4章 图像基本变换.ppt

数字图像处理,延边大学工学院计算机科学与技术系 金小峰 2016年9月,Digital Image Processing,第4章 图像变换（Image Transformation）,4.1 变换特性 4.2 傅立叶（Fourier）变换 4.3 沃尔什变换和哈达玛变换 4.4 离散余弦变换 4.5 哈尔变换* 4.6 盖伯变换*,背景,图像变换：指在不同空间对图像进行的变换 目的：为了快速和有效地对图像进行处理， 通常需要：空域空间→变换空间→处理→空域空间 图像的变换空间具有特殊的性质，有利于进行滤波等处理 正变换：空域空间→变换空间 反变换（逆变换）：变换空间→空域空间,4.1 变换特性,图像变换的方法和种类很多，其原理和效果是不同的 变换不同的原因是不同变换其变换核存在差异 变换之后的有利特性有：可分离性、对称性、正交性,（1）变换核,二维情况的正反变换,𝑻 𝒖,𝒗 = 𝒙=𝟎 𝑵−𝟏 𝒚=𝟎 𝑵−𝟏 𝒇 𝒙,𝒚 𝒉 𝒙,𝒚,𝒖,𝒗 , 𝒖,𝒗=𝟎,𝟏,…,𝑵−𝟏,𝒇 𝒙,𝒚 = 𝒖=𝟎 𝑵−𝟏 𝒗=𝟎 𝑵−𝟏 𝑻 𝒖,𝒗 𝒌 𝒙,𝒚,𝒖,𝒗 , 𝒙,𝒚=𝟎,𝟏,…,𝑵−𝟏,(2) 可分离性,变换核可分离,𝒉 𝒙,𝒚,𝒖,𝒗 = 𝒉 𝟏 𝒙,𝒖 𝒉 𝟐 𝒚,𝒗,𝒙,𝒖 | 𝒚,𝒗,,2D变换=1D变换+1D变换,(3) 对称性,如果 𝐡 𝟏 和 𝐡 𝟐 的函数形式相同，则称正向变换核是对称的,𝐡 𝐱,𝐲,𝐮,𝐯 = 𝐡 𝟏 𝐱,𝐮 𝐡 𝟏 (𝐲,𝐯),反变换,𝐅=𝐁𝐀𝐅𝐀𝐁,𝐢𝐟 𝐁= 𝐀 −𝟏 , 𝐭𝐡𝐞𝐧 𝐅=𝐁𝐓𝐁 𝐞𝐥𝐬𝐞 𝐢𝐟 𝐁≠ 𝐀 −𝟏 , 𝐭𝐡𝐞𝐧 𝐅 =𝐁𝐀𝐅𝐀𝐁,利用矩阵形式的变换表示，得到的变换矩阵可分解成若干个具有较少非零元素的矩阵乘积，减少冗余和操作次数。,(4) 正交性,If 𝐀 −𝟏 = 𝐀 𝐓 , 则称A是正交矩阵。它满足 𝐀 𝐓 𝐀=𝐈, 𝐈是单位矩阵,设给定矩阵𝐟和𝐠, 则线性变换,𝐠=𝐀𝐟,称为正交变换。正交变换的逆变换仍是正交变换。,4.2 傅立叶变换,Jean Baptiste Joseph Fourier Born: 21 March 1768, France Died: 16 May 1830,任何周期函数都可以表示为不同频率的正弦和/或余弦和的形式,对非周期函数也成立（有限性条件下）,任何周期函数都可以表示为不同频率的正弦和/或余弦和的形式,http://zhuanlan.zhihu.com/wille/19763358,Fourier变换是数学棱镜，将函数基于频率分成不同成分,1-D Discrete Fourier Transform,傅立叶变换中的变量𝐮通常称为频率变量，这个名称源于欧拉公式中的指数项,𝐞𝐱𝐩 −𝐣𝟐𝛑𝐮𝐱 =𝐜𝐨𝐬𝟐𝛑𝐮𝐱−𝐣𝐬𝐢𝐧𝟐𝛑𝐮𝐱,如果把傅立叶变换的积分解释为离散项的和的极限，则易推出𝐅(𝐮)是一组𝐬𝐢𝐧和𝐜𝐨𝐬函数项的无限和，其中𝐮的每个值决定了其相应𝐜𝐨𝐬, 𝐬𝐢𝐧函数对的频率,正弦信号的傅里叶频谱,,均值为0 两条竖线（共轭对称）为频谱响应 Fourier变换得频率单位和正弦频率单位不同,空间频率,F(0,0),,,共轭 𝑭 𝒖,𝒗 = 𝑭 ∗ (−𝒖,−𝒗),|𝑭 𝒖,𝒗 |=|𝑭 −𝒖,−𝒗 |,𝑭 𝒖,𝒗,𝑭 ∗ (−𝒖,−𝒗),空间域（正弦波形的浓淡变化）,,,,,,𝑭 𝒖,𝒗 = 𝟏 𝑵 𝒙=𝟎 𝑵−𝟏 𝒚=𝟎 𝑵−𝟏 𝒇 𝒙,𝒚 𝒆𝒙𝒑 − 𝒋𝟐𝝅 𝒖𝒙+𝒗𝒚 𝑵 , 𝒖,𝒗=𝟎,𝟏,…,𝑵−𝟏,𝒇 𝒙,𝒚 = 𝟏 𝑵 𝒙=𝟎 𝑵−𝟏 𝒚=𝟎 𝑵−𝟏 𝑭 𝒖,𝒗 𝐞𝐱𝐩 𝒋𝟐𝝅 𝒖𝒙+𝒗𝒚 𝑵 𝒙,𝒚=𝟎,𝟏,…,𝑵−𝟏,𝒇 𝒙,𝒚 = 𝟏 𝑵 𝑭(𝟎,𝟎),2-D傅立叶变换的原点（零频率分量）与 𝐟 𝐱,𝐲 成正比。该分量也称为直流分量。,2-D傅立叶变换的频谱（幅度函数）、相位角和功率谱（频谱的平方）定义如下：,𝐅 𝐮,𝐯 = 𝐑 𝟐 𝐮,𝐯 + 𝐈 𝟐 (𝐮,𝐯),𝛟 𝐮,𝐯 = 𝐚𝐫𝐜𝐭𝐚𝐧 𝐈 𝐮,𝐯 𝐑 𝐮,𝐯,𝐏 𝐮,𝐯 = 𝐅 𝐮,𝐯 𝟐 = 𝐑 𝟐 𝐮,𝐯 + 𝐈 𝟐 (𝐮,𝐯),频（幅度）谱,相位角,功率谱,,img = rgb2gray(imread( tiananmen.jpg )); img = imresize(img, 0.5);fftresult = fft2(img); fftimg = fftshift(fftresult);ampfft = abs(fftimg);phasefft = angle(fftimg);ifftimg = ifft2(fftresult);figure(1); subplot(221); imshow(img); title(’原始图 ); subplot(222); imshow(255* ampfft/max(ampfft(:))); title(‘频谱图 ); subplot(223); imshow(255* phasefft/max(phasefft(:))); title(‘相位图 ); subplot(224); imshow(ifftimg,[]); title(‘复原图 );,傅立叶变换定理(考虑变换对：𝐅 𝐮,𝒗 ⇔𝐟(𝐱,𝐲)),（1）平移定理,𝐟 𝐱−𝐚,𝐲−𝐛 ⇔𝐞𝐱𝐩 − 𝐣𝟐𝛑 𝐚𝐮+𝐛𝐯 𝐍 𝐅(𝐮,𝐯),𝐅 𝐮−𝐜,𝐯−𝐝 =𝐞𝐱𝐩 𝐣𝟐𝛑 𝐜𝐱+𝐝𝐲 𝐍 𝐟(𝐱,𝐲),空域内的平移对应频域内的相乘，但是不会改变𝐅 𝐮,𝐯 的幅度,频域内的平移对应空域内的相乘，不会改变𝐟(𝐱,𝐲)的灰度值,𝐹(𝑢,𝑣)幅度未变，但是发生了平移,原点移动：原图像乘以 −𝟏 𝐱+𝐲 ,其Fourier变换的频率空间原点将移到𝐌×𝐍区域的中央,ℑ 𝒇 𝒙,𝒚 −𝟏 𝒙+𝒚 =𝑭 𝒖− 𝑴 𝟐 ,𝒗− 𝑵 𝟐,推导,𝑭 𝒖− 𝑴 𝟐 ,𝒗− 𝑵 𝟐 =ℑ 𝒇 𝒙,𝒚 −𝟏 𝒙+𝒚,= 𝟏 𝑴𝑵 𝒙=𝟎 𝑴−𝟏 𝒚=𝟎 𝑵−𝟏 𝒇 𝒙,𝒚 𝒆𝒙𝒑 −𝒋𝟐𝝅 𝒖𝒙 𝑴 + 𝒗𝒚 𝑵 +𝒋𝝅𝒙+𝒋𝝅𝒚,= 𝟏 𝑴𝑵 𝒙=𝟎 𝑴−𝟏 𝒚=𝟎 𝑵−𝟏 𝒇 𝒙,𝒚 𝒆𝒙𝒑 −𝒋𝟐𝝅 𝒖− 𝑴 𝟐 𝒙 𝑴 + 𝒗− 𝑵 𝟐 𝒚 𝑵,,(2)旋转定理,借助极坐标变换𝐱=𝐫𝐜𝐨𝐬𝛉, 𝐲=𝐫𝐬𝐢𝐧𝛉, 𝐮=𝛚𝐜𝐨𝐬𝛟, 𝐯=𝛚𝐬𝐢𝐧𝛟, 将𝐟 𝐱,𝐲 和𝐅(𝐮,𝐯)转换为 𝐟 𝐫,𝛉 和𝐅(𝛚,𝛟),𝐟 𝐫,𝛉+ 𝛉 𝟎 ⇔𝐅 𝛚,𝛟+ 𝛉 𝟎,空域内旋转 𝛉 𝟎 角度，则频域内旋转相同的角度,(3)尺度定理,𝐚𝐟 𝐱,𝐲 ⇔𝐚𝐅(𝐮,𝐯),𝐟(𝐚𝐱,𝐛𝐲)⇔ 𝟏 𝐚𝐛 𝐅 𝐮 𝐚 , 𝐯 𝐛,,,,效果相反,幅度也受影响,比较结果,(4) 纯剪切定理,纯剪切指沿水平或垂直方向的剪切。水平剪切描述了水平方向的剪切失真，垂直剪切描述了垂直方向的剪切失真 比如正方形的剪切失真结果，高度和宽度不变，具有相同面积,水平剪切定理 𝐟 𝐱+𝐛𝐲,𝐲 ⇔𝐅 𝐮,𝐯−𝐛𝐮,垂直剪切定理 𝐟 𝐱,𝐲+𝐝𝐱 ⇔𝐅 𝐮−𝐝𝐯,𝐯,对𝐟 𝐱,𝐲 的纯剪切会导致𝐔𝐕平面𝐅 𝐮,𝐯 的对应失真，失真方向仍正交 垂直 。,(5) 复合剪切定理（自学）,将平移定理和尺度定理相结合可得到复合剪切定理：,𝐟(𝐱+𝐛𝐲,𝐝𝐱+𝐲)⇔ 𝟏 𝟏−𝐛𝐝 𝐅 𝐮−𝐝𝐯 𝟏−𝐛𝐝 , −𝐛𝐮+𝐯 𝟏−𝐛𝐝,用矩阵表示复合剪切，矢量𝐱表示(𝐱,𝐲)，用矢量𝐱′表示( 𝐱 ′ , 𝐲 ′ )，则复合剪切的坐标变换可写为：,𝐱 ′ = 𝟏 𝐛 𝐝 𝟏 𝐱,不一样,(6) 仿射定理（自学）,前述5个定理实际上是仿射定理的特例。仿射定理的通用形式：,𝐠 𝐱,𝐲 =𝐟 𝐚𝐱+𝐛𝐲+𝐜,𝐝𝐱+𝐞𝐲+𝐟 ⇔,𝐆 𝐮,𝐯 = 𝟏 ∆ 𝐞𝐱𝐩 𝐣𝟐𝛑 ∆ 𝐞𝐜−𝐛𝐟 𝐮+ 𝐚𝐟−𝐜𝐝 𝐯 𝐅 𝐞𝐮−𝐝𝐯 ∆ , −𝐛𝐮+𝐚𝐯 ∆,其中，,∆= 𝐚 𝐛 𝐝 𝐞 =𝐚𝐞−𝐛𝐝,设： 𝐮 ′ = 𝐞𝐮−𝐝𝐯 ∆ , 𝐯 ′ = −𝐛𝐮+𝐚𝐯 ∆ , 则,𝐆 𝐮,𝐯 = 𝟏 ∆ 𝐞𝐱𝐩 𝐣𝟐𝛑 (𝐜 𝐮 ′ +𝐟 𝐯 ′ ) 𝐅 𝐮 ′ , 𝐯 ′,,𝐮 𝐯 = 𝐚 𝐝 𝐛 𝐞 𝐮 ′ 𝐯 ′,𝐚,𝐝是放大系数，𝐛,𝐞是剪切量，𝐜,𝐟是平移量,(7) 卷积定理,卷积定理指出，函数卷积的傅里叶变换是函数傅里叶变换的乘积。即一个域中的卷积对应于另一个域中的乘积，例如时域中的卷积对应于频域中的乘积。,𝐟 𝐱,𝐲 ⨂𝐠 𝐱,𝐲 ⟺𝐅 𝐮,𝐯 𝐆(𝐮,𝐯),,空间卷积,,频域乘积,𝐟 𝐱,𝐲 𝐠 𝐱,𝐲 ⟺𝐅(𝐮,𝐯)⨂𝐆(𝐮,𝐯),(8) 相关定理,相关定理指出：两个函数在空间的相关与它们的傅立叶变换（其中一个为其复共轭）在频域的乘积构成一个变换对，而两个函数（其中一个为其复共轭）在空间的乘积与它们的傅立叶变换在频域的相关构成一对变换。,𝐟 𝐱,𝐲 ⨁𝐠 𝐱,𝐲 ⇔ 𝐅 ∗ 𝐮,𝐯 𝐆(𝐮,𝐯),𝐟 ∗ 𝐱,𝐲 𝐠 𝐱,𝐲 ⇔𝐅 𝐮,𝐯 ⨁𝐆(𝐮,𝐯),如果𝐟 𝐱 和𝐠 𝐱 是同一个函数，称为自相关；相反，称为互相关。,相关函数是描述随机信号𝐗(𝐭),𝐘(𝐭)在任意两个不同时刻 𝐭 𝟏 ， 𝐭 𝟐 ，𝛕= 𝐭 𝟐 − 𝐭 𝟏 的取值之间的相关程度。𝐑 𝐱𝐲 𝛕 = −∞ ∞ 𝐱 𝐭 𝐲 𝐭−𝛕 𝐝𝐭 , 𝐑 𝐱𝐲 𝛕 = −∞ ∞ 𝐲 𝐭 𝐱 𝐭−𝛕 𝐝𝐭 , 𝛕= 𝐭 𝟐 − 𝐭 𝟏 自相关函数是描述随机信号𝐗(𝐭)在任意两个不同时刻 𝐭 𝟏 ， 𝐭 𝟐 ，的取值之间的相关程度。𝐑 𝐱 𝛕 = −∞ ∞ 𝐱 𝐭 𝐱 𝐭−𝛕 𝐝𝐭 , 𝛕= 𝐭 𝟐 − 𝐭 𝟏,,相关函数，是指两个信号之间相似性的一种量度,傅立叶变换可用于与卷积密切有关的相关运算（Correlation）。——匹配模板,bw = im2bw(imread( text.jpg )); a = bw(46:59, 82:93); C = real(ifft2(fft2(bw) .* fft2(rot90(a,2),256,256))); thresh = max(C(:))-11;figure subplot(131); imshow(bw); subplot(132); imshow(C,[]); subplot(133); imshow(Cthresh);,,,,另一个例子,img = rgb2gray(imread( demo4.jpg )); [r c] = size(img);img1 = img(:, floor(2*c/3):end);corr = real(ifft2(fft2(img) .* fft2(rot90(img1,2),r,c)));thresh = 1.15*mean(corr(:));figure subplot(221); imshow(img); title( orignal ); subplot(222); imshow(img1); title( cropped image ); subplot(223); imshow(corr,[]); title( correlation ); subplot(224); imshow(corrthresh,[]); title( matching points );,快速傅立叶变换,必要性：直接进行𝐍×𝐍的2D傅立叶变换需要 𝐍 𝟒 次复数乘法运算和 𝐍 𝟐 ( 𝐍 𝟐 −𝟏)次复数加法运算，相当于𝟖 𝐍 𝟒 次浮点运算。,𝐅 𝐮,𝐯 = 𝟏 𝐍 𝐱=𝟎 𝐍−𝟏 𝐲=𝟎 𝐍−𝟏 𝐟 𝐱,𝐲 𝐞𝐱𝐩 − 𝐣𝟐𝛑 𝐮𝐱+𝐯𝐲 𝐍 , 𝐮,𝐯=𝟎,𝟏,…,𝐍−𝟏,快速傅立叶变换（FFT， Fast Fourier Transform）：根据傅立叶变换的可分离性，2D变换可分解为两次连续的1D变换得到。,𝕴 𝐟 𝐱 =𝐅 𝐮 = 𝟏 𝐍 𝐱=𝟎 𝐍−𝟏 𝐟 𝐱 𝐞 − 𝐣𝟐𝛑𝐮𝐱 𝐍 , 𝐮=𝟎,𝟏,𝟐,,…,𝐍−𝟏,,计算结果存储，备查,结论,在频域中，频率越大说明原始信号变化速度越快；频率越小说明原始信号越平缓。当频率为0时，表示直流信号，没有变化。因此，频率的大小反应了信号的变化快慢。高频分量解释信号的突变部分，而低频分量决定信号的整体形象。 在图像处理中，频域反应了图像在空域灰度变化剧烈程度，也就是图像灰度的变化速度，即图像的梯度大小。 对图像而言，图像的边缘部分是突变部分，变化较快，因此反应在频域上是高频分量；图像的噪声大部分情况下是高频部分；图像平缓变化部分则为低频分量。 傅立叶变换提供另外一个角度来观察图像，可以将图像从灰度分布转化到频率分布上来观察图像的特征。即：傅里叶变换提供了一条从空域到频域自由转换的途径。,图像变换在图像处理中的应用,提取图象特征： 直流分量：𝐟(𝐱,𝐲)的平均值=𝐅(𝟎,𝟎)； 目标物边缘：𝐅(𝐮,𝐯)高频分量。 图像压缩：正交变换能量集中，对集中（小）部分进行编码。 图象增强：低通滤波，平滑噪声；高通滤波，锐化边缘。,4.3 沃尔什变换和哈达玛变换,沃尔什变换(Walsh Transform, WT),由于傅里叶变换和余弦变换的变换核由正弦、余弦函数组成，运算量大。在特定问题中，往往引进不同的变换方法，以求运算简单且变换核矩阵产生方便。 Walsh Transform 中的变换矩阵简单（只有1 和－1），占用存储空间少，产生容易，有快速算法，在需要实时处理大量数据的图像处理问题中，应用广泛。 Walsh和哈达玛变换相比傅立叶变换缺乏明确的物理意义和比较直观的解释。,1-D沃尔什变换,则离散𝒇 𝒙 𝒙=𝟎,𝟏,𝟐,…,𝑵−𝟏的沃尔什变换为,当𝑵= 𝟐 𝒏 时，Walsh的变换核，,𝒉 𝒙,𝒖 = 𝟏 𝑵 𝒊=𝟎 𝒏−𝟏 −𝟏 𝒃 𝒊 𝒙 𝒃 𝒏−𝟏−𝒊 𝒖,𝑾 𝒖 = 𝟏 𝑵 𝒙=𝟎 𝑵−𝟏 𝒇(𝒙) 𝒊=𝟎 𝒏−𝟏 −𝟏 𝒃 𝒊 𝒙 𝒃 𝒏−𝟏−𝒊 𝒖,𝒃 𝒌 𝒛 代表𝒛的二进制表示中的第𝒌位。,Example: 𝒏=𝟑, 𝒛=𝟔 = 𝟏𝟏𝟎 𝟐 ,𝒖=𝟏= 𝟎𝟎𝟏 𝟐 ,𝒃 𝟎 𝒛 =𝟎, 𝒃 𝟏 𝒛 = 𝒃 𝟐 𝒛 =𝟏.𝒃 𝟎 𝟏 =𝟏, 𝒃 𝟏 𝟏 = 𝒃 𝟐 (𝟏)=𝟎 𝒉 𝟔,𝟏 ∝ −𝟏 𝒃 𝟎 𝟔 𝒃 𝟐 𝟏 × −𝟏 𝒃 𝟏 𝟔 𝒃 𝟏 𝟏 × −𝟏 𝒃 𝟐 𝟔 𝒃 𝟎 𝟏 ∝−𝟏,𝒉 𝒙,𝒖 的取值非𝟏即−𝟏,,取值范围0或1，且只与𝑥和𝜇有关,N=8时1DWalsh变换核的值,行列正交性、对称性,1-D Walsh变换的离散形式,𝒇⇔𝑭,𝑭= 𝑾 𝑵 𝒇,𝒇= 𝑾 𝑵 𝑭,其中， 𝑾 𝑵 是变换矩阵,Example:,𝑵=𝟒;𝒏=𝟐,𝑾 𝟒 = 𝟏 𝟒 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 −𝟏 −𝟏 𝟏 −𝟏 𝟏 −𝟏 𝟏 −𝟏 −𝟏 𝟏,𝑭= 𝑾 𝟒 𝒇⇔𝒇= 𝑾 𝟒 𝑭,一维Walsh变换的物理意义,正如一维傅立叶变换（连续）是将一个函数分解成无穷个正弦波的叠加，而傅立叶幅度谱是这些正弦波的幅度系数。 一维Walsh变换（连续）是将一个函数分解成无穷个Walsh函数（方波）的叠加，而F(u)是这些Walsh函数的幅度系数,2-D Walsh变换,正反变换核,𝒉 𝒙,𝒚,𝒖,𝒗 = 𝟏 𝑵 𝒊=𝟎 𝒏−𝟏 −𝟏 𝒃 𝒊 𝒙 𝒃 𝒏−𝟏−𝒊 𝒖 + 𝒃 𝒊 𝒚 𝒃 𝒏−𝟏−𝒊 𝒗,𝒌 𝒙,𝒚,𝒖,𝒗 = 𝟏 𝑵 𝒊=𝟎 𝒏−𝟏 −𝟏 𝒃 𝒊 𝒙 𝒃 𝒏−𝟏−𝒊 𝒖 + 𝒃 𝒊 𝒚 𝒃 𝒏−𝟏−𝒊 𝒗,正反变换,𝑾 𝒖,𝒗 = 𝟏 𝑵 𝒙=𝟎 𝑵−𝟏 𝒚=𝟎 𝑵−𝟏 𝒇(𝒙,𝒚) 𝒊=𝟎 𝒏−𝟏 −𝟏 𝒃 𝒊 𝒙 𝒃 𝒏−𝟏−𝒊 𝒖 + 𝒃 𝒊 𝒚 𝒃 𝒏−𝟏−𝒊 𝒗,𝒇 𝒙,𝒚 = 𝟏 𝑵 𝒖=𝟎 𝑵−𝟏 𝒗=𝟎 𝑵−𝟏 𝑾(𝒖,𝒗) 𝒊=𝟎 𝒏−𝟏 −𝟏 𝒃 𝒊 𝒙 𝒃 𝒏−𝟏−𝒊 𝒖 + 𝒃 𝒊 𝒚 𝒃 𝒏−𝟏−𝒊 𝒗,2-D Walsh变换中，正反变换核只依赖于𝒙,𝒚,𝒖,𝒗，而与𝒇 𝒙,𝒚 𝒐𝒓 𝑾(𝒖,𝒗)的值无关。 这些核可以看作一组基本函数，一旦图像尺寸确定这些函数也完全确定。,𝑵=𝟒(𝒏=𝟐)时𝑾𝒂𝒍𝒔𝒉基本函数的图示 白色代表-1，黑色代表+1 内部小方块对应的𝒙和𝒚从0变化到3,2-D Walsh变换的矩阵形式,𝐟⇔𝐅 ⇒ 𝐅= 𝐖 𝐍 𝐟 𝐖 𝐍 𝐟= 𝐖 𝐍 𝐅 𝐖 𝐍,?,能量集中性质,𝒇= 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏 𝟏,𝑾= 𝟏 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎 𝟎,,Walsh 变换后的数据会集中于矩阵的边角上，可见此变换可以用于图像信息压缩,,哈达玛变换（Hadamard Transform）,1-D Hadamard Transform,变换核,𝒉 𝒙,𝒖 = 𝟏 𝑵 −𝟏 𝒊=𝟎 𝒏−𝟏 𝒃 𝒊 𝒙 𝒃 𝒊 (𝒖),𝒉 𝒙,𝒖 = 𝟏 𝑵 𝒊=𝟎 𝒏−𝟏 −𝟏 𝒃 𝒊 𝒙 𝒃 𝒏−𝟏−𝒊 𝒖,𝒃 𝒌 𝒛 代表𝒛的二进制表达中的第𝒌位,𝑬𝒙𝒂𝒎𝒑𝒍𝒆: 𝒉 𝟔,𝟏 ∝ −𝟏 𝒃 𝟎 𝟔 𝒃 𝟎 𝟏 + 𝒃 𝟏 𝟔 𝒃 𝟏 𝟏 + 𝒃 𝟐 𝟔 𝒃 𝟐 𝟏 ∝𝟏,,𝑯 𝒖 = 𝟏 𝑵 𝒙=𝟎 𝑵−𝟏 𝒇 𝒙 −𝟏 𝒊=𝟎 𝒏−𝟏 𝒃 𝒊 𝒙 𝒃 𝒊 𝒖,𝒇 𝒙 的离散𝑯𝒂𝒅𝒂𝒎𝒂𝒓𝒅变换,,与Walsh变换类似，Hadamard变换核组成的矩阵是一个对称矩阵且其行列正交。Hadamard正反变换核相差一个常数𝟏/𝑵, 即,𝒌 𝒙,𝒖 = −𝟏 𝒊=𝟎 𝒏−𝟏 𝒃 𝒊 𝒙 𝒃 𝒊 (𝒖),𝒇 𝒙 = 𝒙=𝟎 𝑵−𝟏 𝑯 𝒖 −𝟏 𝒊=𝟎 𝒏−𝟏 𝒃 𝒊 𝒙 𝒃 𝒊 𝒖,𝑯 𝒖 的离散𝑯𝒂𝒅𝒂𝒎𝒂𝒓𝒅反变换,Walsh变换核,Example,设：𝒙=𝟏,𝒖=𝟐,𝒏=𝟐,𝑵=𝟒,𝒌 𝟏,𝟐 = −𝟏 𝒊=𝟎 𝟐−𝟏 𝒃 𝒊 𝟏 𝒃 𝒊 𝟐 =𝟏,𝒊=𝟎 𝟏 𝒃 𝒊 𝟏 𝒃 𝒊 𝟐 = 𝒃 𝟎 𝟏 𝒃 𝟎 𝟐 + 𝒃 𝟏 𝟏 𝒃 𝟏 𝟐 =𝟏×𝟎+𝟎×𝟏=𝟎,𝑵=𝟖 时𝟏𝑫 𝑯𝒂𝒅𝒂𝒎𝒂𝒓𝒅变换核的值,N=8时1DWalsh变换核的值,行列正交性、对称性,行列正交性、对称性,2-D Hadamard Transform,𝒉 𝒙,𝒚,𝒖,𝒗 = 𝟏 𝑵 −𝟏 𝒊=𝟎 𝒏−𝟏 𝒃 𝒊 𝒙 𝒃 𝒊 𝒖 + 𝒃 𝒊 𝒚 𝒃 𝒊 𝒗,𝒌 𝒙,𝒚,𝒖,𝒗 = 𝟏 𝑵 −𝟏 𝒊=𝟎 𝒏−𝟏 𝒃 𝒊 𝒙 𝒃 𝒊 𝒖 + 𝒃 𝒊 𝒚 𝒃 𝒊 𝒗,𝑯 𝒖,𝒗 = 𝟏 𝑵 𝒙=𝟎 𝑵−𝟏 𝒚=𝟎 𝑵−𝟏 𝒇(𝒙,𝒚) −𝟏 𝒊=𝟎 𝒏−𝟏 𝒃 𝒊 𝒙 𝒃 𝒊 𝒖 + 𝒃 𝒊 𝒚 𝒃 𝒊 𝒗,𝒇 𝒙,𝒚 = 𝟏 𝑵 𝒖=𝟎 𝑵−𝟏 𝒗=𝟎 𝑵−𝟏 𝑯(𝒖,𝒗) −𝟏 𝒊=𝟎 𝒏−𝟏 𝒃 𝒊 𝒙 𝒃 𝒊 𝒖 + 𝒃 𝒊 𝒚 𝒃 𝒊 𝒗,相同,两种变换的联系,两种变换的1和-1的次序不同，但仍保持正交和对称，故Walsh-Hadamard变换指两者之一 如果变换核是可分离的和对称的函数时，变换可写成矩阵形式。Walsh和Hadamard都可以写成矩阵形式，区别在于Hadamard矩阵可用迭代方式获得。,原图像,WHT结果,二维WHT具有能量集中的特性，而且原始数据中数据越是均匀分布，经变换后的数据越集中于矩阵的边角上。因此，二维WHT可用于压缩图像信息。,Example,图像压缩示例,如果Walsh变换后的右下角存在非零元素，则按此方法复原的图像会丢失细节（高频）信息,4.4 离散余弦变换（DCT， Discrete Cosine Transform）,傅立叶变换的一个最大的问题是：它的参数都是复数，在数据的描述上相当于实数的两倍。为此，我们希望有一种能够达到相同功能但数据量又不大的变换 DCT变换是一种可分离和对称变换，可借助Fourier变换的实数部分计算。在傅里叶级数展开式中，被展开的函数是实偶函数时，其傅里叶级数中只包含余弦项，称之为余弦变换 近年来DCT得到广泛应用，尤其是图像编码（压缩）算法中,1-D DCT,Example:,如果令N=4，由一维解析式定义可得如下展开式：,𝐹(0)=0.500𝑓(0)+0.500𝑓(1)+0.500𝑓(2)+0.500𝑓(3 𝐹(1)=0.653𝑓(0)+0.271𝑓(1)−0.272𝑓(2)−0.653𝑓(3 𝐹(2)=0.500𝑓(0)−0.500𝑓(1)−0.500𝑓(2)+0.500𝑓(3 𝐹(3)=0.271𝑓(0)−0.653𝑓(1)+0.653𝑓(2)−0.271𝑓(3,写成矩阵形式：,𝐹(0 𝐹(1 𝐹(2 𝐹(3 = 0.500 0.500 0.500 0.500 0.653 0.271 −0.271 −0.653 0.500 −0.500 −0.500 0.500 0.271 −0.653 0.653 −0.271 ⋅ 𝑓(0 𝑓(1 𝑓(2 𝑓(3,𝑭 𝒖 =𝑨𝒇 𝒙 ⟺𝒇 𝒙 = 𝑨 𝑻 𝑭(𝒖),,2-D DCT,𝑪 𝒖,𝒗 =𝒂 𝒖 𝒂 𝒗 𝒙=𝟎 𝑵−𝟏 𝒚=𝟎 𝑵−𝟏 𝒇 𝒙,𝒚 𝒄𝒐𝒔 𝟐𝒙+𝟏 𝒖𝝅 𝟐𝑵 𝒄𝒐𝒔 𝟐𝒚+𝟏 𝒗𝝅 𝟐𝑵,𝒖,𝒗=𝟎,𝟏,…,𝑵−𝟏,𝒇 𝒙,𝒚 = 𝒖=𝟎 𝑵−𝟏 𝒗=𝟎 𝑵−𝟏 𝒂 𝒖 𝒂 𝒗 𝑪 𝒖,𝒗 𝒄𝒐𝒔 𝟐𝒙+𝟏 𝒖𝝅 𝟐𝑵 𝒄𝒐𝒔 𝟐𝒚+𝟏 𝒗𝝅 𝟐𝑵,𝒙,𝒚=𝟎,𝟏,…,𝑵−𝟏,2-D DCT的矩阵形式,𝑭 𝒖,𝒗 =𝑨𝒇 𝒙,𝒚 𝑨 𝑻,𝒇 𝒙,𝒚 = 𝑨 𝑻 𝑭 𝒖,𝒗 𝑨,8×8 𝐷𝐶𝑇 𝐵𝑎𝑠𝑖𝑠 𝐼𝑚𝑎𝑔𝑒𝑠,DCT的应用——压缩编码,4.5 哈尔变换(Haar Transform),Haar函数于1910年提出，其矩阵只有+𝟏,−𝟏, 𝟐 为基础的系数，是正交稀疏矩阵 Haar变换的特性与图像中的边界或线条的特性十分接近，因此图像中的边缘和线条经Haar变换后，会产生较大的变换系数，而其他部分的变换系数较小 Haar函数也是小波变换中的典型小波，也称为Haar小波。（关于小波变换参见后续课程或文献）,故，Haar函数进一步定义为,𝒉 𝟎 𝒛 = 𝒉 𝒑𝒒 𝒛 =𝒉 𝟎𝟎 𝒛 = 𝟏 𝑵 , 𝒛∈[𝟎,𝟏],𝒉 𝒌 𝒛 = 𝒉 𝒑𝒒 𝒛 = 𝟏 𝑵 𝟐 𝒑 𝟐 𝒒−𝟏 𝟐 𝒑 ≤𝒛 𝒒− 𝟏 𝟐 𝟐 𝒑 − 𝟐 𝒑 𝟐 𝒒− 𝟏 𝟐 𝟐 𝒑 ≤𝒛 𝒒 𝟐 𝒑 𝟎 𝒐𝒕𝒉𝒆𝒓,N=8时的Haar函数波形见右图，有如下特征,Haar-like特征，即很多人常说的Haar特征，是计算机视觉领域一种常用的特征描述算子。它最早是由Papageorigiou等人用于人脸描述。目前常用的Haar-like特征可以分为三类：线性特征、边缘特征、点特征（中心特征）、对角线特征。,显然，边缘特征有4种：x方向，y方向，x倾斜方向，y倾斜方向；线特征有8种，点特征有2种，对角线特征有1种。每一种特征的计算都是由黑色填充区域的像素值之和与白色填充区域的像素值之和的差值。而计算出来的这个差值就是所谓的Haar-like特征的特征值。,N=8时，Haar基图像,右下象限部分可以用来搜索图像中不同位置的小特征,Haar变换的特征： Haar函数的一个重要特性——收敛均匀而迅速 Fourier变换的基函数（变换核）仅是频率不同，Haar函数在尺度和位置上都不同。即，Haar变换具有尺度和位置的双重性 全域特性和区域特性：Haar函数系列可分为全域部分和区域部分。全域部分作用于整个变换区间，区域部分作用于局部区域,Example：,img = double(rgb2gray(imread( \lena.jpg )));[r c] = size(img);[LL LH HL HH] = dwt2(img, haar );LL = mat2gray(LL); LH = mat2gray(LH); HL = mat2gray(HL); HH = mat2gray(HH); img = [LL LH; HL HH]; figure imshow(img);,低频,水平,垂直,对角,4.6 盖伯变换*(Gabor Transform),连续Gabor变换是信号时-频分析的一个重要工具 在许多应用中，给定一个信号𝐟(𝐭) ，最感兴趣的问题是在局部时间信号的频率含量。标准的Fourier变换 𝐅 𝛚 = −∞ ∞ 𝐞 −𝐣𝛚𝐭 𝐟 𝐭 𝐝𝐭，不能由𝐅得到关于信号高频脉冲时间定位信息。 Gabor 在1946年，为了由信号的Fourier变换提取局部信息，引入了时间局部化的窗函数，得到了窗口Fourier变换。由于窗口Fourier变换只依赖于部分时间的信号，所以，现在窗口Fourier变换又称为短时Fourier变换，这个变换又称为Gabor变换。,Gabor变换的优点：,Gabor小波与人类视觉系统中简单细胞的视觉刺激响应非常相似。 它在提取目标的局部空间和频率域信息方面具有良好的特性。 Gabor小波对于图像的边缘敏感，能够提供良好的方向选择和尺度选择特性，而且对于光照变化不敏感,能够提供对光照变化良好的适应性。,Gabor滤波器和脊椎动物视觉皮层感受野响应的比较,第一行代表脊椎动物的视觉皮层感受野 第二行是Gabor滤波器 第三行是两者的残差 可见两者相差极小,(1)窗函数,令𝒓 𝒕 为一个时间窗函数，乘积𝒇 𝒕 𝒓 𝒕−𝒃 = 𝒇 𝒃 𝒕 包含了接近𝒕=𝒃处的𝒇 𝒕 的信息。,𝒇 𝒃 𝒕 = 𝒇 𝒕 𝒕∈ 𝒃−𝒔,𝒃+𝒔 𝟎 𝒐𝒕𝒉𝒆𝒓,通过改变参数𝑏，可将窗沿时间轴移动以研究函数𝑓(𝑡)在不同区间的行为。,频率窗函数𝑹(𝒘)也有类似的特性,𝒘 ∗ = 𝟏 𝑹 𝒘 𝟐 −∞ ∞ 𝒘|𝑹 𝒘 | 𝟐 𝒅𝒘,∆ 𝑹 = 𝟏 𝑹 𝒘 −∞ ∞ 𝒘− 𝒘 ∗ 𝟐 𝑹 𝒘 𝟐 𝒅𝒘 𝟏 𝟐,中心,均方根半径,𝑅 𝑤 代表频率窗函数的Fourier变换,𝑡 ∗ = 1 𝑟 𝑡 2 −∞ ∞ 𝑡 𝑟 𝑡 2 𝑑𝑡,∆ 𝑟 = 1 𝑟 𝑡 −∞ ∞ 𝑡− 𝑡 ∗ 2 𝑟 𝑡 2 𝑑𝑡 1 2,几个常用的窗函数,𝒈 𝒕 = 𝟏 𝟎≤𝒕≤𝟏 𝟎 𝒐𝒕𝒉𝒆𝒓,矩形窗函数,三角窗函数,𝒈(𝒕)= 𝟐𝒕 𝟎≤𝒕≤ 𝟏 𝟐 𝟐 𝟏−𝐭 𝟏 𝟐 ≤𝒕≤𝟏 𝟎 𝒐𝒕𝒉𝒆𝒓,Hanning窗函数,𝒈 𝒕 = 𝟏−𝒄𝒐𝒔𝟐𝝅𝒕 𝟐 𝟎≤𝒕≤𝟏 𝟎 𝒐𝒕𝒉𝒆𝒓,Hamming窗函数,𝒈 𝒕 = 𝟎.𝟓𝟒−𝟎.𝟒𝟔𝒄𝒐𝒔𝟐𝝅𝒕 𝟎≤𝒕≤𝟏 𝟎 𝒐𝒕𝒉𝒆𝒓,w=boxcar(n),w=triang(n),w=hanning(n),w=hamming(n),,,,(2)短时傅里叶变换（STFT，Short-Time Fourier Transform）,对信号𝑓(𝑡)进行Gabor变换定义为：,𝐺 𝑓 𝑎,𝑏,𝜔 = −∞ +∞ 𝑓 𝑡 𝑔 𝑎 𝑡−𝑏 𝑒 −𝑗𝜔𝑡 𝑑𝑡,其中：,当窗函数为高斯函数时，STFT称为Gabor变换,𝑔 𝑎 𝑡 = 1 2 𝑎𝜋 exp − 𝑡 4𝑎,是高斯函数；𝑎0, 𝑏0,𝑔 𝑎 (𝑡−𝑏)是一个时间局部化的窗函数。𝑏用于平行移动窗口，以便覆盖整个时域。,对𝑏积分，则有：,−∞ ∞ 𝐺 𝑓 𝑎,𝑏,𝜔 𝑑𝑏 = 𝑓 𝜔 , 𝜔∈𝑅,信号的重构表达式为,𝑓 𝑡 = 1 2𝜋 −∞ ∞ −∞ ∞ 𝐺 𝑓 𝑎,𝑏,𝜔 𝑔 𝑎 𝑡−𝑏 𝑒 𝑗𝜔𝑡 𝑑𝜔𝑑𝑏,二维Gabor滤波器,2D Gabor滤波器是由一个被二维高斯包络【𝑓 𝑥 = 1 𝜎 2𝜋 𝑒 − 𝑥−𝑢 2 2 𝜎 2 】调相的具体确定方向和频率的二维正弦平面波所构成。,常用的2D Gabor滤波器,ℎ 𝑥,𝑦 = 1 2𝜋 𝜎 𝑢 𝜎 𝑣 exp − 1 2 𝑢 2 𝜎 𝑢 2 + 𝑣 2 𝜎 2 2 cos⁡(𝜔𝑢),where,,𝑢=𝑥𝑐𝑜𝑠𝜃+𝑦𝑠𝑖𝑛𝜃, 𝑣=−𝑥𝑠𝑖𝑛𝜃+𝑦𝑐𝑜𝑠𝜃,𝜃：Gabor filter方向；,𝑢和𝑣分别是高斯包络在𝑢轴和𝑣轴上的标准差,𝜔：调制频率,二维Gabor滤波器的频率响应表达为：,𝐻 𝑢,𝑣 = exp −2 𝜋 2 𝜎 𝑥 (𝑢−𝑈)′ 2 + 𝜎 𝑦 (𝑣−𝑉)′ 2,Where,,𝑢−𝑈 ′ = 𝑢−𝑈 𝑐𝑜𝑠𝜃+ 𝑣−𝑉 𝑠𝑖𝑛𝜃,𝑣−𝑉 ′ =− 𝑢−𝑈 𝑠𝑖𝑛𝜃+ 𝑣−𝑉 𝑐𝑜𝑠𝜃,Gabor滤波器是一种依赖于图像轮廓的尺度和方向的多分辨率分析工具，具有在空间域和频率域同时取得最优局部化的优势，因此能够很好地描述对应于空间频率、空间位置及方向选择性的局部结构信息。,对一幅图像进行不同方向和尺度Gabor滤波的结果,从上至下，每行图像的尺度因子分别为 0.3,0.3 , 0.6,0.6 和 0.9,0.9 从左至右，每列图像的滤波角度分别为0°，25°，45°，75°，90°,Example：,0.3,0.6,0.9,0°,25°,45°,75°,90°,