第三章图像变换 ChapTER 3 OIMAGE TRANSFORM §1傅里叶变换(F斤「和性质) §2可分离的图像变换 §3 Hotelling变换 版权所有,1997(c) Dale Carnegie& Associates,nc
第三章 图像变换 版权所有， 1997 (c) Dale Carnegie & Associates, Inc. •CHAPTER 3 •IMAGE TRANSFORM •§1 傅里叶变换(FFT和性质) •§2 可分离的图像变换 •§3 Hotelling变换
83.1傅里叶变换 傅里叶变换在图像处理中应用较多。 §3,1.1傅里叶变换:(仅考虑离散情况)。 1D傅里叶变换对 正变换: F(u)=(1/N)∑f(X)exp[-2jux/N],u=0,…N-1 F(u)是复函数,即 F(U =R (u) +jI (u)=F(u explo(ul F(u)|=[R(u)2+I(u)2]2;幅度函数(傅里叶频谱) d(u=arct [I (U)/R(u)]: 相位角 反变换:f(u)=∑F(u)exp[-2jux/N],x=0,…N-1;
§3.1 傅里叶变换 傅里叶变换在图像处理中应用较多。 §3.1.1 傅里叶变换：（仅考虑离散情况）。 一、 1D傅里叶变换对 正变换： F（u）= （1/N） f（x）exp[-2jux/N] ，u=0,…,N-1； F（u）是复函数，即 F（u） = |R（u）+j I（u）| = |F（u）| exp[j(u)] ； |F（u）| = [R（u）2+I（u）2 ] 1/2；幅度函数（傅里叶频谱） (u) = arctg [I（u）/R（u）]； 相位角 反变换：f（u）= F（u）exp[-2jux/N] ，x=0,…,N-1；
§3.1.1傅里叶变换(续1) 、二维傅里叶变换对 正变换F(uM)=(1/N2)2∑f(x,y)exp-2jπ(u+w)/N u=0,…,N-1;V=0,…,N-1 反变换f(xy)=∑∑F(u)exp-2jπ(ux+wy)/N], x=0…,N-1;y=0,…,N-1 §3.1.2傅里叶变换性质 分离性 exp[-2jT(UX+vy)/N]= exp[-2jTuX/N] exp[-2jTVy/N] F(X,V)=((1/N) 2 f(,y) exp[-2jTVy/N]S,V=0,,N-1 F(u, v)=f(1/N) 2F (X, v) exp[-2jTUXN]],u=0,, N-1 ∴一个2D傅里叶变换可由连续2次运用1D傅里叶变换来实现, 先进行y(列)变换,后进行x(行)变换;
§3.1.1 傅里叶变换（续1） 二、二维傅里叶变换对 正变换 F（u,v）= （1/N2） f（x,y）exp[-2j（ux+vy）/N] ，u=0,…,N-1；v=0,…,N-1 反变换f（ x,y ）= F（u,v）exp[-2j（ux+vy）/N]， x=0,…,N-1；y=0,…,N-1 §3.1.2 傅里叶变换性质 一、分离性： ∵ exp[-2j（ux+vy）/N] = exp[-2jux/N] exp[-2jvy/N] F（x,v）= {（1/N） f（x,y）exp[-2jvy/N] }，v=0,…,N-1 F（u,v）= {（1/N）F（x,v）exp[-2jux/N] }，u=0,…,N-1 ∴一个2D傅里叶变换可由连续2次运用1D傅里叶变换来实现， 先进行y（列）变换，后进行x（行）变换；
33.12傅里叶变换性质(续1) 平移性(不影响幅值,由级数展开可得出对应关系◇) f(X,y) exp[-2jT(uoX+Voy)/N]F(u-Uo/V-Vo 表明原f(xy)用f(xy)exp[-2jπ(uox+Vy)/N]替换后 进行傅里叶变换,则变换后的频域中心平移到了新位置 类似:f(Xx0yy0)F(u)exp-2j(uxo+w0)/N] 表明F(u,)与一个指数项相乘后再进行傅里叶反变换,则 变换后的空域中心平移到了新位置。 三、周期性和共轭对称性 F(Uv)=F(u+Nv)=F(Uv+N=F(u+NV+N) 利用周期性和共轭对称性,只需一个周期的变换就可确定f (xy)或反之,方便了分析和计算
§3.1.2 傅里叶变换性质（续1） • 二、平移性（不影响幅值，由级数展开可得出对应关系 ） f（x,y）exp[-2j（u0x+v0y）/N]F（u-u0 ,v-v0） • 表明原f（x,y）用f（x,y ）exp[-2j（u0x+v0y）/N]替换后 进行傅里叶变换，则变换后的频域中心平移到了新位置。 类似：f（x-x0 ,y-y0） F（u,v）exp[-2j（ux0+vy0）/N] • 表明F（u,v）与一个指数项相乘后再进行傅里叶反变换，则 变换后的空域中心平移到了新位置。 • 三、周期性和共轭对称性 • F（u,v）= F（u+N,v）= F（u,v+N）= F（u+N,v+N） • 利用周期性和共轭对称性，只需一个周期的变换就可确定f （x,y ）或反之，方便了分析和计算
83.1,2傅里叶变换性质(续2) 四、旋转性质(借助极坐标变换可证明) f(r0+00)=F(φ+0); 将f(xy)旋转0度对应于将F(uV)也旋转0;反之一样。 五、卷积 1.fe和g的含义 设一维时f采样长为A的序列,g采样长为B的序列 当M=A+B-1时,卷积周期M才不会重叠,且是相邻接的 若A〈M,B〈M,需扩展f,g为M序列,方法是补充0 即 e(x) f(x 0≤X<A-1 (X)=0 A<X<M-1
§3.1.2 傅里叶变换性质（续2） 四、旋转性质（借助极坐标变换可证明） f（r, +0）= F（+0）； 将f（x,y）旋转0度对应于将F（u,v）也旋转0 ；反之一样。 五、卷积 1. f e 和g e的含义 设一维时f 采样长为A 的序列，g 采样长为B 的序列； 当M=A+B-1时，卷积周期M才不会重叠，且是相邻接的； 若A〈 M，B〈 M，需扩展f , g 为M序列，方法是补充0； 即： f e（x）= f（x） 0 x A-1 f e（x）= 0 A x M-1
3.1.2傅里叶变换性质(续3) 2.卷积的定义 维卷积的定义: f(x)*B。(x)=(1/M)∑f(m)g。(x-m),m=0,…,M-1 维卷积的定义: fe(x,y)*g。(x,y)=(1/MN)∑∑f。(m,n)B。(x-m,y-n), m=0,…,M-1,n=0,,N-1; ·3.卷积与傅里叶变换的关系 fe (x, y) *g (x, y) F(u, v)G(u, v) 两个函数卷积的傅里叶变换对应于两个函数傅里叶变换的乘积 fe (x, y) g(x, y) F(u, v)*G(u, v) 两个函数乘积的傅里叶变换对应于两个函数傅里叶变换的卷积
§3.1.2 傅里叶变换性质（续3） • 2. 卷积的定义 • 一维卷积的定义： • fe（x）*ge（x）=（1/M） fe（m）ge（x-m），m=0,…,M-1 • 二维卷积的定义： • fe（x,y）*ge（x,y）=（1/MN） fe（m,n）ge（x-m,y-n）， m=0,…,M-1，n=0,…,N-1； • 3. 卷积与傅里叶变换的关系 • fe（x,y）*ge（x,y） F（u,v）G（u,v） • 两个函数卷积的傅里叶变换对应于两个函数傅里叶变换的乘积； • fe（x,y）ge（x,y） F（u,v）* G（u,v） • 两个函数乘积的傅里叶变换对应于两个函数傅里叶变换的卷积；
3.13快速傅里叶变换 思路 将傅里叶变换分成二个步骤计算,每个步骤用一个1D变换实现; 先算行,后算列; 1D变换的逐次加倍法 已知F(u)=(1/N)∑f(x)exp[-2jux/N], 令WN=exp[2ji/N,得F(u)=(1/N)∑f(x)WN; 再令N=2M,得F(u)=(1/2M)∑f(x)W2Mx; (1/2){(1/M)∑f(2X)W2M1"(2×+ ;偶部分 (1/M)∑f(2X+1)W2Mu(2x+1)};奇部分 (1/2) (u)+F odd (u) 2M
§3.1.3 快速傅里叶变换 • 一、思路 • 将傅里叶变换分成二个步骤计算，每个步骤用一个1D变换实现； 先算行，后算列； • 二、1D变换的逐次加倍法 • 已知F（u）= （1/N） f（x）exp[-2jux/N] ， • 令WN= exp[-2j/N]，得F（u）= （1/N） f（x） WN ux ； • 再令N=2M，得F（u）= （1/2M） f（x） W2M ux ； • =（1/2）{（1/M） f（2x） W2M u（2x）+ ；偶部分 • （1/M） f（2x+1） W2M u（2x+1） } ；奇部分 • = （1/2）{Feven（u）+ Fodd（u） W2M u }；
83.1.3快速傅里叶变换(续1) 算法实现 关键是输入数据的排列次序(奇偶分组排列) 以N=8为例,介绍位对换规则 位对换规则:如果二进制位正读存在相应的反读,两者位置互换; X(0) 000 000不变 (4) 001 100对换 (2) →X(2) 010 010不变 (3) X(6) 011 110对换 x(4) X(1) 100 001对换 X(5) X(5) 101 101不变 X(6) x(3) 110 011对换 X(7) 111 111不变
§3.1.3 快速傅里叶变换（续1） 三、算法实现 • 关键是输入数据的排列次序（奇偶分组排列） • 以N=8为例，介绍位对换规则。 • 位对换规则：如果二进制位正读存在相应的反读，两者位置互换； • x（0） x（0） 000 000 不变 • x（1） x（4） 001 100 对换 • x（2） x（2） 010 010 不变 • x（3） x（6） 011 110 对换 • x（4） x（1） 100 001 对换 • x（5） x（5） 101 101 不变 • x（6） x（3） 110 011 对换 • x（7） x（7） 111 111 不变
§3.2可分离图像变换 傅里叶变换是可分离变换的一个特例 §3.21可分离变换的一般形式 T(uv)=∑∑f(xy)g(xyuV),x,y=0…,N-1;uv=0…,N-1 f(xy)=∑∑T(uv)h(xyuv),uv=0…,N-1;xy=0,…,N-1 g(xy,u,V)、h(xyu)分别称为正向变换核和反向变换核 是变换中进行级数展开的基本函数。 如果g(xyu)=g1(x,u)g2(yV),则称正向变换核是可分离的 如果h(xyu)=h1(xu)h2(yV),则称反向变换核是可分离的;
§3.2 可分离图像变换 傅里叶变换是可分离变换的一个特例。 §3.2.1 可分离变换的一般形式 T（u,v）= f（x,y）g（x,y,u,v），x,y=0,…,N-1；u,v=0,…,N-1 f（x,y）= T（u,v）h（x,y,u,v），u,v=0,…,N-1；x,y=0,…,N-1 g（x,y,u,v）、h（x,y,u,v）分别称为正向变换核和反向变换核； 是变换中进行级数展开的基本函数。 如果g（x,y,u,v）= g1（x,u）g2（y,v），则称正向变换核是可分离的； 如果h（x,y,u,v）= h1（x,u）h2（y,v），则称反向变换核是可分离的；
32.2沃尔什变换( Walsh) 沃尔什变换(WT)的变换核(由美国数学家 Walsh提出) 维变换核:g(xu)=(1/N)∏(-1)(x)bn1(o;i=0…n-1,N=2n W(u)=∑f(x)∏(-1)(bn1o;x=0,…N-1 式中b(z)是z的二进制表达中的第k位(取0或1值); ◆由沃尔什变换核组成的矩阵(略去常数,仅用符号表示+1、-1) 矩阵是一个对称矩阵,且行和列正交 ◆反变换核与正变换核只差一个常数1/N 反变换核h(xu)=∏(-1)(x)bn10o;i=0…,n-1 所以,反变换f(x)=∑W(u)∏(-1)1(x)bn1(u;u=0,,N-1,N=2n。 ◆由于反变换与正变换只相差一个常数,故算法可通用
§3.2.2 沃尔什变换（Walsh） 沃尔什变换（WT）的变换核（由美国数学家Walsh提出） ◆ 一维变换核：g（x,u）= （1/N）∏ (-1)bi (x)bn-i-1(u)；i=0,…,n-1，N=2n W（u）= f（x）∏ (-1)bi (x)bn-i-1(u)； x=0,…,N-1 式中bk (z）是z的二进制表达中的第k位（取0或1值）； ◆由沃尔什变换核组成的矩阵（略去常数，仅用符号表示+1、-1） 矩阵是一个对称矩阵，且行和列正交。 ◆反变换核与正变换核只差一个常数1/N； 反变换核 h（x,u）= ∏ (-1)bi (x)bn-i-1(u)；i=0,…,n-1； 所以，反变换f（x）= W（u）∏ (-1)bi (x)bn-i-1(u)；u=0,…,N-1，N=2n。 ◆ 由于反变换与正变换只相差一个常数，故算法可通用