04_第四章_图像变换

第四章 图象变换,4.1 积分变换 4.2 连续傅立叶变换 4.3 离散傅立叶变换 4.4 快速傅立叶变换 4.5 二维离散傅立叶变换 4.6 正交变换的一般表示形式 4.7 其它离散正交变换 4.8 小波变换,傅立叶变换,4.1、积分变换 4.2、连续傅立叶变换 4.3、二维离散傅立叶变换 4.4、快速傅立叶变换,积分变换概念,积分变换(integral transform)就是通过积分，把一个函数f(t)变成另一个函数F(s)： 称F(s)为象函数(quadrantal function)， 称f(t) 为原函数（或象原函数）。 如果积分限a和b是有界的，则称F(s)是f(t)的有限积分变换式。 式中，K(s, t)是s和t的已知函数，称为积分变换的核(transpositional core)。,傅立叶变换的定义(一维),f(x)为连续可积函数，其傅立叶变换定义为：,其反变换为：,F(u)=R(u)+jI(u),幅度谱： 相位谱：,一维离散傅立叶变换(DFT),一维离散傅立叶变换公式为：,逆变换为：,二维傅立叶变换,二维傅立叶变换由一维傅立叶变换推广而来：,逆变换：,幅度谱： 相位谱：,F(u,v)=R(u,v)+jI(u,v),二维离散傅立叶变换,对于二维离散傅立叶变换，其形式为：,逆变换为：,幅谱(频谱)、相谱：,傅立叶谱： |F(u,v)|= R2(u,v)+I2(u,v)1/2,相位: (u,v)= arctan(I(u,v)/R(u,v),图像矩阵 实数,频域矩阵 复数,幅度谱的屏幕显示,原图像,频域中的高频和低频与空间域的对应关系,二维离散傅立叶变换的性质,1. 线性性质：,2. 比例性质：,3. 可分离性：,4. 空间位移：,5. 频率位移：,图像中心化：,当u0=v0=N/2时，,平均值,平均值定义：,由傅立叶变换定义：,因此，f(x,y)的平均值与傅立叶变换系数的关系为：,频率位移性质,当图像在频率域时移动时需要用到频率位移性质：,图像中心化,把图像进行傅立叶变换后，往往要把中心移到u0=v0=N/2的位置上,平移性,FT,则：,即：,同理：,未移中的变换：,移中的变换：,能量集中于中心（示意图）,原图像f（x，y）,6. 周期性： F(u,v)=F(u+aN,v+bN), f(x,y)=f(x+aN,y+bN),7. 共轭对称性：,8. 旋转不变性：,9. 平均值：,旋转不变性,10. 卷积定理： f(x,y)*h(x,y) F(u,v)H(u,v) f(x,y)h(x,y) F(u,v)*H(u,v),11. 相关定理： 互相关：f(x,y)Og(x,y) F(u,v)G*(u,v) f(x,y)g*(x,y) F(u,v) OG(u,v) 自相关：f(x,y)Of(x,y) |F(u,v)|2 |f(x,y)|2 F(u,v) OF(u,v),12. 帕塞瓦定理（能量定理）：,若f1(x,y)=f2(x,y)=f(x,y)，则有：,可分离性,需要N 次复数乘法，N-1次复数加法。,因此总共需要N 2 次复数乘法，N(N-1)次复数加法。,1965年，Cooley和Tukey提出快速算法，算法时间复杂度为 N log2 N。,4.4 快速傅立叶变换,记,则有：,单位园表示：,设N=2m，f(x)的定义域分为偶数部分和奇数部分， 即f(2x)和f(2x+1),记为：,u = 0, 1, 2, , N/2-1,对于N=N/2, N/2, , N-1,由Fe(u)和Fo(u)的原式，它们以N/2为周期：,而由W的性质：,所以：,WNux的性质：,(1) 对称性：,(2) 周期性：,(3) 可分性：,快速傅立叶变换（FFT）流程图,基2、时间抽取算法，N=8,码位倒置,F（u）,乘法次数：,如何提高FFT的速度？,（1）减少乘法次数；（2）基4、基8算法；（3）实数FFT； （4）硬件实现（DSP芯片，FFT集成块）,因为：,提高FFT速度新流程图,基2、时间抽取算法，N=8,乘法次数：5次,第四章 图象变换,4.1 积分变换 4.2 连续傅立叶变换 4.3 离散傅立叶变换 4.4 快速傅立叶变换 4.5 二维离散傅立叶变换 4.6 正交变换的一般表示形式 4.7 其它离散正交变换 4.8 小波变换,可分离变换,一、 可分离变换 二、 哈达玛变换 三、 沃尔什变换 四、 离散余弦变换 五、 KL变换 六、 小波变换,一维可分离变换 正变换和正向变换核 反变换和反向变换核,一、 可分离变换,正变换核,反变换核,二维可分离变换 正变换和正向变换核 反变换和反向变换核,正变换核,反变换核,可分离变换性质 1. 可分离变换核 2. 对称核,二维正变换核可分离且对称时,用矩阵表示：,F=AfA,类似的，对于MN的二维函数f(x,y),基图像,反变换,图像f(x,y)可以用N2个基图像的加权和来表示,可分离变换矩阵表达,F：NN图像矩阵,A：NN对称变换矩阵,B：NN反变换矩阵,B=A-1时，图像可完全由变换恢复,BA-1时，F的一个近似,其元素为aij=g1(i,j),一维沃尔什变换 正变换和正向变换核 反变换和反向变换核,二、 沃尔什变换,沃尔什变换,二维沃尔什变换 正变换和正向变换核 反变换和反向变换核,比较:,傅立叶变换: 快速算法, 复数运算, 乘法, 速度慢,可硬件实现, 精度高 Walsh变换: 快速算法, 实数运算, 加减法, 速度快,可硬件实现, 精度低,拉德梅克(Rademacher)函数的定义:,其中：n为序号，n=0，1，N-1 t为连续时间变量,拉德梅克(Rademacher)函数:,(1)Walsh序的Walsh函数,定义:,其中:,(1)Walsh序的Walsh函数,二进制码 格雷码 n b2b1b0 g2g1g0 0 000 000 1 001 001 2 010 011 3 011 010 4 100 110 5 101 111 6 110 101 7 111 100,(1)Walsh序的Walsh函数,二进制码 格雷码 n b2b1b0 g2g1g0 0 000 000 1 001 001 2 010 011 3 011 010 4 100 110 5 101 111 6 110 101 7 111 100,Walsh序的Walsh函数的特点: (1)是完备的正交函数, 序号为偶数的是偶函数,序号为奇数的是奇函数;可用于正交变换。 (2)一个周期内,过零点数与序号一致.,Walsh函数,(2)Paley序的Walsh函数(略) (3)Hadamard序的Walsh函数,二进制码 倒序码 n b2b1b0 I2I1I0 0 000 000 1 001 100 2 010 010 3 011 110 4 100 001 5 101 101 6 110 011 7 111 111,连续Walsh函数的定义,(3)Hadamard序的Walsh函数,定义:,离散Walsh函数的定义,定义:,(1)Walsh序的离散Walsh函数,其中:,离散Walsh函数的定义,定义:,(1)Walsh序的离散Walsh函数,例: N=8, n=0,1,7 , t= 0,1,7 计算WW(4,0),n=4=(100)2 t=0=(000)2 t的格雷码g=(000)2,(1)Walsh序的离散Walsh函数,例: N=8, n=0,1,7 , t= 0,1,7 计算WW(4,t),同理，可求出：,实际上，这个序列就是从连续的Walsh序的Walsh函数WW（4，t）在等间距的N个点上的抽样（取中间值）,(1)Walsh序的离散Walsh函数,例: N=8, n=0,1,7 , t= 0,1,7,同理，可求出： WW(n,t),离散Walsh函数的定义,定义:,(2)Hadamard序的离散Walsh函数,例: N=8, n=0,1,7 , t= 0,1,7 计算WH(4,t),这个序列可看成从连续的Hadamard序的Walsh函数WH（4，t）在等间距的N个点上的抽样而得到。,(2)Hadamard序的离散Walsh函数,Hadamard序的Walsh矩阵,3. Walsh矩阵,(1)Walsh序的Walsh矩阵,(2)Hadamard序的Walsh矩阵,(2)Hadamard序的Walsh矩阵,一般来说：,一维离散Walsh变换(WT),1. 定义,正变换:,反变换:,注意: Walsh正、反变换的变换核都一样！,一维离散Walsh变换的矩阵算法,正变换:,展开：,2.一维离散Walsh变换的矩阵算法,正变换:,令：,IWT：,注意: (1)正反变换的变换矩阵W都一样； (2)W代表Walsh序的Walsh矩阵。,注意: 当变换矩阵为Hadamard矩阵HN时,称为Hadamard序的 Walsh变换。变换矩阵如下写法：,IWHT：,其中H为Hadamaed序的Walsh矩阵。,反变换：,用WHT：,用WT：,结果为Walsh序,结果为Hadamard序,对应关系 W序 H序 0 0 1 2 2 3 3 1,Walsh序和Hadamard序的相互转换,变换结果为Hadamard序的，要转换为Walsh序,可以推导出以下转换方法（N=4）：,二进制码格雷码倒序码 00 00 00 01 01 10 10 11 11 11 10 01 （W序） （H序）,对应关系 W序 H序 0 0 1 2 2 3 3 1,Walsh序和Hadamard序的相互转换,N=8时的转换方法：,二进制码 格雷码倒序码 000 000 000 001 001 100 010 011 110 011 010 010 100 110 011 101 111 111 110 101 101 111 100 001 （W序） （H序）,对应关系 W序 H序 0 0 1 4 2 6 3 2 4 3 5 7 6 5 7 1,Walsh序和Hadamard序的相互转换,变换结果为Hadamard序的，要转换为Walsh序,对应关系 W序 H序 0 0 1 2 2 3 3 1,用WHT：,一维Walsh变换的物理意义,正如一维傅立叶变换（连续）是将一个函数分解成无穷个正弦波的叠加，而傅立叶幅度谱是这些正弦波的幅度系数。,一维Walsh变换（连续）是将一个函数分解成无穷个Walsh函数（方波）的叠加，而F(u)是这些Walsh函数的幅度系数.,一维Walsh变换的物理意义,一维哈达玛变换 正变换和正向变换核 反变换和反向变换核,三、 哈达玛变换,正变换核,反变换核,阶（序） 列中符号变换的次数,正变换核,三、 哈达玛变换,二维哈达玛变换 正变换和正向变换核 反变换和反向变换核,三、 哈达玛变换,哈达玛矩阵的迭代,三、 哈达玛变换,当f(x)或f(x,y)为偶函数时，变换的计算公式只有余弦项。 一个任意函数采样从0,1,2,N-1，若向负方向折叠形成2N采样的偶函数，就可以进行2N的偶函数傅立叶变换。 余弦变换是简化傅立叶变换的一种方法,四、 离散余弦变换,一维余弦变换, 离散序列f(x), x = 0, 1, 2, , N-1，以-1/2为折点，形成-N至-1的序列，与原序列合并形成2N偶函数序列，此时的变换核为：,离散傅立叶变换的虚部为零，上式剩下余弦项,一维离散余弦变换,离散余弦变换,二维离散余弦变换,二维余弦变换, 偶对称偶函数：, 为关于(-1/2, -1/2)对称的偶函数。, 归一化(使得基向量的模为1)：, 偶对称偶函数的变换核的基函数正交 核可分离 余弦变换的能量向低频集中, 奇对称偶函数：, 折叠镜像序列。, 上述折叠函数的傅立叶变换：, 上式归一化后即为奇对称函数的余弦变换：, 反变换：, 这个变换同样也是正交的和可分离的，可以用两次一维变换来执行, 正变换矩阵为：, N=4时,余弦变换的性质, 余弦变换为实的正交变换CC*，C-1=CT。, 序列的余弦变换是DFT的对称扩展形式。, 余弦变换有快速变换，和傅立叶变换一样，分奇偶组：,此处：,JPEG,1. 开始，压缩程序把图象划分为88的象素块。由于使用了JPEG方法压缩图象所需要的时间是方块中象素数目的函数，所以对若干个小块象素进行处理要比一次性对整个图象进行处理快得多。,2. 使用 “离散余弦变换”的公式对象素值进行处理。DCT把与图象不同点相应的88颜色值矩阵变换为与不同的正弦波频率相对应的88幅度值矩阵。矩阵中靠近左上角的位置与低频率相对应，靠近右下角的位置与高频率相对应。,3. 用户输入的质量因子插入到一个公式中，由此产生了另一个称为“量化矩阵”的88的矩阵。质量因子的值越小，矩阵中数值越大。,4. DCT输出的矩阵中的每个数值除以量化矩阵中相应的数值，结果再四舍五入取最接近的整数。量化矩阵的右下角部分的数值越大意味着图象的高频信息丢弃得越多。矩阵的右下角部分现在大部分都是零。,5. 计算机按“之”字形扫描矩阵并使用保真压缩方法压缩数据，基本上去掉了矩阵右下角部分的零。较低的质量因子相应地在矩阵中产生较多的零，同时也