第三章 图像变换版权所有,1997 (c) Dale Carnegie & Associates,Inc.
CHAPTER 3
IMAGE TRANSFORM
§ 1 傅里叶变换 (FFT和性质 )
§ 2 可分离的图像变换
§ 3 Hotelling变换
§ 3.1 傅里叶变换傅里叶变换在图像处理中应用较多。
§ 3.1.1 傅里叶变换：（仅考虑离散情况）。
一,1D傅里叶变换对正变换：
F（ u） = （ 1/N）? f（ x） exp[-2j?ux/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[-2j?ux/N],x=0,…,N-1；
§ 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[-2j?ux/N] exp[-2j?vy/N]
F（ x,v） = {（ 1/N）? f（ x,y） exp[-2j?vy/N] },v=0,…,N-1
F（ u,v） = {（ 1/N）?F（ x,v） exp[-2j?ux/N] },u=0,…,N-1
∴ 一个 2D傅里叶变换可由连续 2次运用 1D傅里叶变换来实现，
先进行 y（ 列）变换，后进行 x（ 行）变换；
§ 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 ） 或反之，方便了分析和计算。
§ 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,卷积的定义
一维卷积的定义：
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.1.3 快速傅里叶变换
一、思路
将傅里叶变换分成二个步骤计算，每个步骤用一个 1D变换实现；
先算行，后算列；
二,1D变换的逐次加倍法
已知 F（ u） = （ 1/N）? f（ x） exp[-2j?ux/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 }；
§ 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.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）,则称反向变换核是可分离的；
§ 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。
◆ 由于反变换与正变换只相差一个常数，故算法可通用。
CHAPTER 3
IMAGE TRANSFORM
§ 1 傅里叶变换 (FFT和性质 )
§ 2 可分离的图像变换
§ 3 Hotelling变换
§ 3.1 傅里叶变换傅里叶变换在图像处理中应用较多。
§ 3.1.1 傅里叶变换：（仅考虑离散情况）。
一,1D傅里叶变换对正变换：
F（ u） = （ 1/N）? f（ x） exp[-2j?ux/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[-2j?ux/N],x=0,…,N-1；
§ 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[-2j?ux/N] exp[-2j?vy/N]
F（ x,v） = {（ 1/N）? f（ x,y） exp[-2j?vy/N] },v=0,…,N-1
F（ u,v） = {（ 1/N）?F（ x,v） exp[-2j?ux/N] },u=0,…,N-1
∴ 一个 2D傅里叶变换可由连续 2次运用 1D傅里叶变换来实现，
先进行 y（ 列）变换，后进行 x（ 行）变换；
§ 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 ） 或反之，方便了分析和计算。
§ 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,卷积的定义
一维卷积的定义：
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.1.3 快速傅里叶变换
一、思路
将傅里叶变换分成二个步骤计算，每个步骤用一个 1D变换实现；
先算行，后算列；
二,1D变换的逐次加倍法
已知 F（ u） = （ 1/N）? f（ x） exp[-2j?ux/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 }；
§ 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.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）,则称反向变换核是可分离的；
§ 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。
◆ 由于反变换与正变换只相差一个常数，故算法可通用。
