数 字 图 像 处 理 与
分 析 基 础
第五章 图像变换
Image Transforms
ISBN 7-5084-2930-3
新世纪电子信息与自动化系列课程改革教材
黄爱民 安向京 骆力
中国水利水电出版社
数字图像处理与分析基础
第五章 图像变换
? 概述和分类
? 离散 Fourier变换
? 快速算法
? 其它可分离图像变换
? Hotelling变换
? 作业
数字图像处理与分析基础
5.1概述和分类
图像变换 ——图像转换到另一种空间处理，特有性质
图像处理和分析的数学基础
图
像
变
换
可分离变换
统计变换
Fourier变换 (DFT)
DCT
WHT
ST
HT,Wavlet Transform
Hotelling
数字图像处理与分析基础
5.2 离散 Fourier变换
? 定义
? 性质
? 快速算法
? 应用
数字图像处理与分析基础
5.2.1 2DFT
(Two Dimensions Fourier Transform）
2
1
22 )],(),([),( vuIvuRvuF ??
)].,(),,(a r c t a n [),( vuRvuIvu ??
),(),(),( 22 vuIvuRvuE ??
1??j
相位谱：
R(u,v)和 I(u,v)分别是 F(u,v)的实部与虚部。
? ??
?
?
?
?????
1
0
1
0
1,..,2,1,0,],/)(2e x p [),(1),(
N
x
N
y
NvuNvyuxjyxfNvuF ?
? ??
?
?
?
???? 1
0
1
0
1,.,,2,1,0y,x],/)(2e x p [),(1),( N
u
N
v
NNvyuxjvuFNyxf ?
能量谱：
u,v-- Frequency variable,|F(u,v)|-- Fourier Spectrum,
数字图像处理与分析基础
图 5-2 Fourier基函数
0
1
2
3
4
5
6
7
8
0 4 8 12 16
(a)正弦分量（前 1/2）
0
1
2
4
5
6
7
0 4 8 12 16
3
8
(b)余弦分量（前 1/2）
数字图像处理与分析基础
例,DFT的计算
一维函数的四个采样值为 f(0)=2,f(1)=3,f(2)=f(3)=4.
25.3]4432[
4
1
)]3()2()1()0([
4
1
]0e x p [)(
4
1
)0(
3
0
?????
????? ?
?
ffffxfF
x
]2[
4
1
]4432[
4
1
]4/2e x p [)(
4
1
)1(
2/32/0
3
0
jeeee
xjxfF
jjj
x
???????
??
???
?
?
???
?
]01[
4
1
]4432[
4
1
]4/4e x p [)(
4
1
)2(
320
3
0
jeeee
xjxfF
jjj
x
???????
??
???
?
?
???
?
]2[
4
1
]4432[
4
1
]4/6e x p [)(
4
1
)3(
2/932/30
3
0
jeeee
xjxfF
jjj
x
???????
??
???
?
?
???
?
f(x)全部值对 FT
都产生影响；反
之，全部变换系
数对反变换也产
生影响。
数字图像处理与分析基础
数字图像处理与分析基础
5.2.2 付立叶变换的性质
Properties of the Fourier Transform
1,付立叶频谱的显示 Fourier Spectrum Display：
D(u,v)=log[1+|F(u,v)|] (5-5)
2,可分离性 Separable Product
F(u,v)=1/N?x?y f(x,y)exp[- j2?(ux+vy)/N] (5-6)
=1/N ?xexp[- j2?ux/N]? ?y f(x,y) exp[- j2?vy/N]
=1/N ?x F(x,v) exp[- j2?ux/N]
其中 F(x,v)=N[1/N ?y f(x,y) exp(- j2?vy/N)]。
数字图像处理与分析基础
Fourier变换的分离性
yN-1
N-1 f(x,y)
0
x
N-1
N-1 F(x,v)
0
x
N-1
N-1 F(u,v)
0
u
行变换 列变换
v v
数字图像处理与分析基础
变换的基函数可分解：
}/)(2s in {}/)(2c o s {
}/)(2e x p {),;,(
},/)(2s in {}/)(2c o s {
}/)(2e x p {),;,(
NvyuxjNvyux
NvyuxjvuyxB
NvyuxjNvyux
NvyuxjvuyxA
????
??
????
???
??
?
??
?
数字图像处理与分析基础
3,The Shift Theorem
? 频移性
? 平移性
数字图像处理与分析基础
频移性
? f(x,y)exp[j2?(u0x+v0y)/N]?F(u-u0,v-v0)
? 当 u0=v0=N/2时，
exp[j2?(u0x+v0y)/N]=(-1)x+y,
则 f(x,y) (-1)x+y ?F(u-N/2,v-N/2)
频谱原点移到中心
? 正向 Fourier变换前需要进行数据处理
数字图像处理与分析基础
平移性
f(x-x0,y-y0) ?F(u,v)exp[- j2?(u0x+v0y)/N].
|F(u,v)exp[j2?(ux0+vy0)/N]|=|F(u,v)|
? 图像平移不影响频谱
数字图像处理与分析基础
数字图像处理与分析基础
4,变换域的周期性 Periodicity,T=N,
F(u,v)=F(u+N,v)=F(u,v+N)=F(u+mN,v+nN).
5,对称共轭性 Conjugate Symmetry,
F(u,v)=F*(-u,-v),|F(u,v)|=|F(-u,-v)|.
6,旋转 Rotation,
x=rcos?,y=rsin?,u=?cos?,v=?sin?,
f(r,? + ?0) ? F(?,?+ ?0)，对连续、离散均
成立。
?
数字图像处理与分析基础
注意观察对应关系
数字图像处理与分析基础
图 5-6 Jean Buptiste Joseph
Fourier和他的付立叶变换
(a)输入图像
(b)幅值谱
(c)相位谱
(d)由幅值谱重构的图象
(e)由相位谱重构的图象
结论,相位谱可能具有
更重要的应用
数字图像处理与分析基础
7,Rayleigh’s Theorem:
? define energy=? (-?,+ ?) |f(t)|2dt,
? then,
? (-?,+ ?) |f(t)|2dt=? (-?,+ ?) |F(s)|2ds.
? Power,
? (-?,+ ?) f(x)g*(x)dx=? (-?,+ ?) F(s)G(s)ds
数字图像处理与分析基础
（ 1）相加性
F{f1(x,y)+f1 (x,y)}=F{f1(x,y)}+F{f2(x,y)},
F{f1 (x,y)f2 (x,y)}!= F{f1 (x,y)}F{f2 (x,y)}.
（ 2）尺度变换
设 a,b是两标量，
af(x,y) ? aF(u,v),
f(ax,by) ? 1/|ab|F(u/a,v/b).
8,The Addition Theorem and
The Similarity Theorem
数字图像处理与分析基础
9,The Average
)0,0(1),(1),(
1
0
1
0
2 FNyxfNyxf
N
x
N
y
? ??
?
?
?
??
2
2
2
2
2 ),(
y
f
x
fyxf
?
??
?
???
10,Laplacian
),()()2()},({ 2222 vuFvuyxfF ???? ?
数字图像处理与分析基础
空域和频率域之间的关系
（ 1） The Convolution
f(x)*g(x)?F(u)G(u),
f(x)g(x)?F(u)*G(u),
? ???? ?? ??? dxgfxgxf )()()(*)(
11,The Convolution and Correlation
Theorem
数字图像处理与分析基础
The Theorem, 离散信号 f(x),A； g(x),B
扩展成周期函数 fe(x),ge(x),,M?A+B-1
?
?
?
???
???
?
?
?
?
???
???
?
.1,0
,10),(
)(
.1,0
,10),(
)(
MxA
Axxg
xg
MxA
Axxf
xf
e
e
?
?
?
????
1
0
1,...,1,0),()()(*)(
M
m
eeee Mxmxgmfxgxf
卷积定理的效能：点数 ?32时,FFT方法较快。
数字图像处理与分析基础
???? ??
??
?? dxgfxgxf )()()()( ?
?
?
?
????
1
0
1,...,2,1,0),()()()(
M
m
eeee Mxmxgmfxgxf ?
Theorem,f(x,y)?g(x,y) ?F(u,v)G*(u,v),
f(x,y)g*(x,y) ?F(u,v) ? G(u,v),
“*”表示复共轭。
（ 2） Correlation
数字图像处理与分析基础
5.2.3快速算法
（ 1）因子分解：稀疏矩阵
（ 2） 1D FFT算法：“逐次加倍”，“蝶形
算法”
数字图像处理与分析基础
逐次加倍算法
1,.,,,2,1,0
},)12(
1
)2(
1
{
2
1
})12(
1
)2(
1
{
2
1
)(
2
1
)(
.,2 ;,2
]./2e x p [,)(
1
)(
2
1
0
1
0
WW
)12(
2
1
0
)2(
2
1
0
,
2
12
0
1
0
ux
M
2 u x
2M
??
???
???
?
????
???
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
Mu
WWxf
M
Wxf
M
Wxf
M
Wxf
M
Wxf
M
uFt h e n
NMMNNnNl e t
NjWWxf
N
uF
u
M
ux
M
M
x
ux
M
M
x
xu
M
M
x
xu
M
M
x
odde v e n
ux
M
M
x
n
N
ux
N
N
x
?
数字图像处理与分析基础
}.)()({
2
1
)(
,,
})()({
2
1
)(
2
22
2
u
Moe
u
M
Mu
M
u
M
Mu
M
u
Moe
WuFuFMuF
WWWW
WuFuFuFt h e n
???
???
??
??
1,.,,,2,1,0
,)12(
1
)(
,)2(
1
)(,
1
0
1
0
??
??
?
?
?
?
?
?
?
Mu
Wxf
M
uF
Wxf
M
uFd e f
ux
M
M
x
o
ux
M
M
x
e
数字图像处理与分析基础
逐次加倍 FFT来源：两点变换由两个一点变换算
出，四点变换由两个两点变换算出，对于 N等于
2的整数幂都成立。
Xm(p) X m+1(p)
Xm(q) X m+1(q)WNr
图 5-7 只要求一次复数乘法的简化蝶形图
运算量分析
数字图像处理与分析基础
WN0
WN0
WN0
WN2
-1
-1
-1
-1
WN0
WN0
WN0
WN2
-1
-1
-1
-1
WN0
WN1
WN3
WN2
-1
-1
-1
-1
X(0)
X(4)
X(2)
X(6)
X(1)
X(7)
X(3)
X(5)
y(0)
y(7)
y(6)
y(5)
y(4)
y(3)
y(2)
y(1)
图 5-18利用蝶形图构成的 8点 DFT的流程图
数字图像处理与分析基础
同址计算，输出正常次序，
输入倒位序，序数的二进
制码。
(n2n1n1)--(n0n1n2),
x0(000)=x(000),
x0(001)=x(100),
x0(010)=x(010),
x0(011)=x(110),
x0(100)=x(001),
x0(101)=x(101),
x0(110)=x(011),
x0(111)=x(111),
X(n2 n1 n0)
X(000)
X(100)
X(010)
X(110)
X(101)
X(011)
X(111)
X(001)
0
1
1 1
1
1
1
0
0
0
0
图 5-9描述倒位序的树状图
偶数取样在上半部，奇数取样在下半部。
不断将离散付立叶变换分解成较小的离散
付立叶变换造成序列 x(n)倒位序。
数字图像处理与分析基础
5.2.4 要点小结
? 1、付立叶变换是线性积分变换，在时间（或
空间）域的复数函数和频率域的复数函数间建
立起唯一对应。
? 2、付立叶变换保持奇偶性。
? 3、函数和的付立叶变换等于它们分别变换再
求和（加法定理）。
? 4、平移函数的原点将在 Fourier谱中引入一个
相位移（与频率成正比），它改变了谱的实部
和虚部的能量分配，但不改变总能量（位移定
理）。
数字图像处理与分析基础
? 5、两个函数的卷积对应于它们付立叶变换相乘
（卷积定理）。
? 6、压缩一个函数会扩展它的付立叶变换，反之
亦然（尺度变换定理）。
? 7、函数的能量同其付立叶变换谱的能量相等。
? 8、能量有限的输入信号可被分解为有限多个正
余弦函数的和差。
? 9、旋转二维函数，它的付立叶变换也旋转相同
的角度。
? 10、自相关函数的付立叶变换是能量谱。
数字图像处理与分析基础
5.3 线性变换
g(x,u)称为 正变换核 。
h(x,u)称为 反变换核 。
If g(x,y,u,v)=g1(x,u)g2(y,v),则核 可分离 ;
If g1=g2,则核 加法对称 。
??
?
?
1
0
),()()(
N
x
uxgxfuT
??
?
?
1
0
),()()(
N
u
uxhuTxf
? ??
?
?
?
?
1
0
1
0
),,,(),(),(
N
x
N
y
vuyxgyxfvuT
? ??
?
?
?
?
1
0
1
0
),,,(),(),(
N
u
N
v
vuyxhvuTyxf
数字图像处理与分析基础
分离性
? 所有具有可分离核的二维变换与离散
Fourier变换一样，可以分成两个一维变
换分步进行。
? 沿着 f(x,y)的每一行作一维变换，得到：
? 沿着 T(x,v)的每一列作一维变换，得到
?
?
?
?
1
0
2 ),(),(),(
N
y
vygyxfvxT
??
?
?
1
0
1 ),(),(),(
N
x
uxgvxTvuT
数字图像处理与分析基础
图像变换的矩阵表示
设 f为数字图像 f(x,y)的灰度值方阵，大小为 N?N，显然
f是实数矩阵。实数矩阵总可以经过一系列初等变换，
找到它的同型矩阵 F，使得：
F=PfQ
式中 F,f是 N?N方阵,P,Q是 N?N的满秩方阵，且 P、
Q不唯一 。
由于 P,Q满秩，它们有逆矩阵 P-1,Q-1，分别用 P-1左
乘，右乘 Q-1上 式，得：
f=P-1FQ-1
表明：数字图像可以从它的正交变换中完整地恢复 。
数字图像处理与分析基础
图像变换的矩阵表达式与代数表达式本
质相同
? ?
?
?
?
?
?
1
0
1
0
),(),(),(),(
N
x
N
y
vyQyxfuxPvuF
]/2e x p [1),(),( 1 NuxjNuxguxP ????
]/2e x p [1),(),( 2 NvyjNvygvyQ ????
数字图像处理与分析基础
如果 g(x,y,u,v)可分离，则有 T=AFAT；
设 FN*N为图像,AN*N为变换矩阵,
其中 aij=g1(i,j),TN*N为结果,
如果 A=AT,T=AFA,
存在反变换矩阵 B,BTB=BAFAB，
?数字图像可以从它的变换中完整地恢复
?变换矩阵可分解成稀疏矩阵的乘积形式，
由此构造快速算法 --分解方法。
数字图像处理与分析基础
3、正交变换的本质
数字图像表示成矩阵的形式时，可以将图像变换看作若干
个图像的加权和。如果将 P,Q用列矢量表示
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
?
1
0
1
0
1
1
0
110
),(
)1,1()0,1(
)1,1()0,1(
)1,0()00(
)(
N
i
N
j
T
ji
T
N
T
T
N
qpjif
q
q
q
NNfNf
Nff
Nff
pppF
?
?
???
?
?
?
，
数字图像处理与分析基础
3、正交变换的本质
数字图像表示成矩阵的形式时，可以将图像变换看作若干
个图像的加权和。如果将 P,Q用列矢量表示
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
?
1
0
1
0
1
1
0
110
),(
)1,1()0,1(
)1,1()0,1(
)1,0()00(
)(
N
i
N
j
T
ji
T
N
T
T
N
qpjif
q
q
q
NNfNf
Nff
Nff
pppF
?
?
???
?
?
?
，
数字图像处理与分析基础
5.4 正弦型变换
? 基函数为正 -余弦波的正交变换
? 如离散余弦变换（ Discrete Cosine Transform，
DCT）
? JPEG图像压缩标准的基本推荐算法。
? 离散正弦变换（ DST ）
? 离散哈特利（ Hartley）
? 快速算法
数字图像处理与分析基础
5.4.1 DCT（次最优正交变换）
一维离散余弦变换的正变换核为：
??
?
??
? ??
N
uxuauxg
2
)12(c o s)(),( ?
1,...,1,0 ?? Nx
，
1,...,2,1 ?? Nu
?
?
?
??
??
1,,2,1,/2
0,/1)(
NuN
uNua
?当
当
??
?
??
? ?? ? ?
? N
uxxfuauC N
x 2
)12(c o s)()()( 1
0
?
。
数字图像处理与分析基础
反变换
一维 DCT的反变换核与正变换核一致，即
),(),( uxguxh ?
反变换表示为：
??
?
??
? ?? ? ?
? N
uxuCuaxf N
u 2
)12(c o s)()()( 1
0
?
一维余弦函数的基函数的图形与 Fourier基函数类似
数字图像处理与分析基础
2D DCT
??
?
??
? ?
??
?
??
? ??
N
vy
N
uxvauavuyxg
2
)12(c o s
2
)12(c o s)()(),,,( ??
?
?
?
??
??
1,,2,1,/2
0,/1)(
NuN
uNua
?当
当
a(v)与 a(u)定义类似。
DCT的反变换核与正变换核一致：
).,,,(),,,( vuyxgvuyxh ?
数字图像处理与分析基础
2D DCT变换对
??
?
??
? ?
??
?
??
? ?? ? ??
?
?
? N
vy
N
uxyxfvauavuC N
x
N
y 2
)12(c o s
2
)12(c o s),()()(),( 1
0
1
0
??
??????
?
??????
?? ? ??
?
?
? N
vy
N
uxvuCvauayxf N
u
N
v 2
)12(c o s
2
)12(c o s),()()(),( 1
0
1
0
??
数字图像处理与分析基础
2D DCT基图像
图 5.4.1 二维 DCT基图像
数字图像处理与分析基础
性质
? 可分离性、对称性
? 快速算法
? 代数分解：蝶形图
? 矩阵分解：稀疏矩阵的积，不唯一
数字图像处理与分析基础
数字图像处理与分析基础
5.5 离散 KL变换 (Karhunen-Loeve)(DKT)
? Hotelling变换、特征向量变换
(Eigenvector-Based Transform)、主分
量变换。
? 利用图像的统计性质，统计模型。
? 应用
? 数据压缩
? 图形旋转
数字图像处理与分析基础
5.5.1 定义
图像 f N?N (x,y),传输 M次，
接收集合 {fi(x,y),i=1,2,…,M}
统计总体，通道特征、干扰性质。
采样图像,Xi=(xi1,xi2,…,xiN2)T,
按行或按列依次排列，
协方差矩阵 CX=E{(X-Mx)(X-Mx)T},
Mx为均值向量,Mx=E{X}，
近似表示：
?
?
?
?
??
???
M
i
T
XX
T
ii
M
i
T
XiXiX
MMXX
M
MXMX
M
C
1
1
][
1
))((
1
?
?
??
M
i
iX XMXEM
1
1}{
数字图像处理与分析基础
?
?
?
?
?
?
?
?
?
?
?
2222
2
21
11211
NNNN
N
eee
eee
A
?
?
?
令 ei,?i,i=1,2,…,N2分别表示矩阵的特征矢量与特
征值，将 ?i减序排列,?1> ?i2>…?N2,
构造变换矩阵：
K-L变换定义,Y=A(X-MX).
Y为新产生的图像向量。
数字图像处理与分析基础
1）半正定矩阵的性质
CX实对称矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
???
?
2
0
0
}))({(;0
2
1
N
T
X
T
YY
Y
AAC
mYmYEC
m
?
?
?
?
5.4.2 Property
数字图像处理与分析基础
2）最优变换
CX实对称矩阵，总可以找到标准正交的特征向量集
合构成 A,A-1=A’,由 Y利用 X=A’Y+MX 重建 X。
压缩,k个大的 ?i,Ak,
离散 K-L变换在最小平方误差的意义上最优。
???
????
?????
??
22
111
2 })?{(;
N
kj
j
k
j
j
N
j
j
X
T
k
XXER
mTAX
???
数字图像处理与分析基础
缺点
1）非分离，计算 CX,及其特征值、特征向量；
2）无快速算法。
作用：
1）比较其它方法（在编码及图像压缩等方面）的
效率。
2）图像标准化（旋转）
数字图像处理与分析基础
5.4.3Application in Image Rotate
? 第一基向量与数据中最大变化的方向相
对应。
? 目标已抽出，希望与某个标准的、或不
变的方向对准。右手坐标系。
? 处理对象：目标中各像素的坐标。
数字图像处理与分析基础
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
??
??
??
??
??
??
??
c o ss i n
s i nc o s
c o ss i n
s i nc o s
c o ss i n
s i nc o s
2221
1211
2
1
2
1
212
211
ee
ee
A
AX
x
x
y
y
Y
xxy
xxy
数字图像处理与分析基础
1,K-l变换用于图像旋转
(a) (b)
(c)
x1
y1y
2
x2
0
e1
e2 y1
y1
y1
y1
二维目标的旋转。 (a)原始数据的散布指明单位特征
向量的方向； (b)利用变换 Y=AX作数据旋转； ( c)利
用变换 Y=A(X-MX)作数据旋转和中心化
数字图像处理与分析基础
例 设图像目标区域由四个像素构成
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
? ?
??
?
?
?
?
? ?
?
4
2
,
3
1
,
1
1
,
0
2
23
21
xx
xx
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
??
?
?
?
?
? ?
??
?
?
?
?
? ?
?
?? ?
?
2
0
4
2
3
1
1
1
0
2
4
1
4
1
}{
4
1i
i
XXEM
4
3
21
1 2-2 -1 X1
y
(a)原始空间
数字图像处理与分析基础
向量的均值非零，将每个数据点减去均值向量后
可实现中心化,Y=X-M
??
?
??
?
?
??
??
?
??
??
??
?
??
? ??
??
?
??
??
2
2
2
0
0
2
2
1
1 y
yY,
??
?
??
?
?
??
??
?
??
??
??
?
??
? ??
1
1
2
0
1
1
2Y
,
??
?
??
??
??
?
??
??
??
?
??
??
1
1
2
0
3
1
3Y
,
??
?
??
??
??
?
??
??
??
?
??
??
2
0
2
0
4
2
4Y
y1
2
1
1 2
-2 -1
y2
(b)中心化
数字图像处理与分析基础
? ? ? ? ? ? ? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
????
?
?
?
?
?
?
?
????
?
?
?
?
?
?
?
?? ?
?
?
4
10
4
10
4
10
4
10
22
2
2
11
1
1
11
1
1
22
2
2
4
1
4
1
4
1
T
i
i
i
iy
YYC
设协方差矩阵的特征值为 ?，有,0?? IC
y ?
式中 I为单位矩阵，因此有：
0
4
10
4
10
4
10
4
10
?
?
?
?
?
数字图像处理与分析基础
由此得到变换方程：
0
4
10
4
10 22 ?
?
?
??
?
???
?
??
?
? ? ?
化简得：
0)5( ????
因此特征值是,?1=5,?2=0。
数字图像处理与分析基础
下面求对应于每个特征值的特征矢量 Y=(y1,y2)T：
令
YYC Y 1??
得
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2
1
2
1
5
4
10
4
10
4
10
4
10
y
y
y
y
化简后两个方程具有相同的形式：
021 ?? yy
不失一般性，取,TY )1 1(
1 ?
这是与 ?1=5相对应的特征向量。
数字图像处理与分析基础
类似方法得到与 ?1=0对应的特征向量 Y2：
TY )1- 1(1 ?
将特征向量归一化：
??
?
??
?
????
?
??
??
1
1
2
1,
1
1
2
1
21 YY
转换矩阵 A为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2
1
2
1
2
1
2
1
A
数字图像处理与分析基础
?
?
?
?
?
? ?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
0
8
2
2
2
1
2
1
2
1
2
1
11 AYZ
变换值为,Z=AY
,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
0
8
0
2
0
2
4
3
2
Z
Z
Z
z1
1
2
-2 -1
z2
(c)沿特征矢量旋转
数字图像处理与分析基础
减少数据量、运算量
人脸图像
样本库
人脸特征
样本库
待识人脸图像
变换矩阵
特征变化
特征匹配
K-L变换
身份
确认
2,K-L变换用于图像压缩 --人脸识别 --
特征脸
数字图像处理与分析基础
5.5 Walsh Transform
? Walsh函数系是 完备正交函数系，只取
两种值，在归一化条件下只取 +1,-1。
? 典型非正弦正交变换，方波变换
? 分三类，区别于编号,Walsh,Paley,
Hadamard
数字图像处理与分析基础
5.5.1 Walsh编码的离散形式
当 N=2n时,W(u),f(x)的正交变换核,
,)1(1),( )()(
1
0
1 ubxb
n
i
ini
Nuxg
?????
?
?
x,u=0,1,…,N-1,N=2n,
bk(x)表示 x的二进制码的第 k位值,
)()(1
0
1)1(),( ubxb
n
i
iniuxh ?????
?
?
数字图像处理与分析基础
二维：
g(x,y,u,v)=g1(x,u)g1(y,v)
=h1(x,u)h2(y,v)=h(x,y,u,v)
快速算法：
与 FFT类似，所有指数项改为 1。只有实数加减。
数字图像处理与分析基础
?
?
?
?
?
?
??
??
1
0
1
0
)()(
)()(
)1(),(
,)1(
1
),(
n
i
ii
n
i
ii
ubxb
ubxb
uxh
N
uxg
构造具有递推形式,N=2，
222,11
11 HH
HH
HHHH
N
NN
NN
n ????
?
??
?
????
?
??
?
??
5.5.2 Hadamard
N<200,Hadamard变换均存在
数字图像处理与分析基础
7
6
5
4
3
2
1
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
22
1
5
2
6
1
4
3
7
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
22
1
8
8
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
????
????
????
????
????
????
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
????
????
????
????
????
????
?
H
W
数字图像处理与分析基础
)()()(
,
),()()(
),()(
,)1(
1
),(
011
211
10
)()(
1
0
ububup
ububup
ubup
N
uxg
n
nn
n
upxb
n
i
ii
??
??
?
???
?
??
?
?
?
?
Hadamard矩阵有列率（ the sequence of the
row:the number of sign changes along the
correnponding row） 性，通常写成按列率 u增加
而增加的函数。模 2加法。
数字图像处理与分析基础
5.5.3 快速算法
1）提取公共项
例：序列 (x0,x1,x2,x3)
的 Walsh变换：
6次加减代替 12次
)]()[(
4
1
)(
4
1
)]()[(
4
1
)(
4
1
)]()[(
4
1
)(
4
1
)]()[(
4
1
)(
4
1
,
1111
1111
1111
1111
4
1
312032103
312032102
312032101
312032100
3
2
1
0
3
2
1
0
xxxxxxxxy
xxxxxxxxy
xxxxxxxxy
xxxxxxxxy
x
x
x
x
y
y
y
y
????????
????????
????????
????????
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
数字图像处理与分析基础
2)矩阵分解技术：找公共项，利用直积形式分解，用
中间 结果计算
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
73
62
51
40
4
7
6
5
4
4
3
2
1
0
4
7
6
5
4
73
62
51
40
4
7
6
5
4
4
3
2
1
0
4
3
2
1
0
44
44
8
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
,8
xx
xx
xx
xx
H
x
x
x
x
H
x
x
x
x
H
y
y
y
y
xx
xx
xx
xx
H
x
x
x
x
H
x
x
x
x
H
y
y
y
y
X
HH
HH
XHYN
T
数字图像处理与分析基础
3）应用矩阵因子分解, HN分解成几个稀疏矩阵
的乘积，
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
10001000
01000100
00100010
00010001
10001000
01000100
00100010
00010001
,
1010
0101
0010
0101
0
0
1010
0101
1010
0101
,
11
11
11
11
0
0
11
11
11
11
2
10
F
FF
W8=F0F1F2
数字图像处理与分析基础
5.8 要点小结
1、一个 N*N变换矩阵的行是 N维向量空间的一组正交
基向量。
2、线性酉变换产生一个含有 N个变换系数的向量，每
个变换系数是输入向量与变换矩阵的某行的内积。
3、反变换也是通过变换系数向量与变换矩阵的行的内
积生成的。
4、反变换也可以看作是构造基向量的一个加权和，变
换系数就是权。
5、二维对称可分离的酉变换，基图像是变换图像不同
行之间的外积。
分 析 基 础
第五章 图像变换
Image Transforms
ISBN 7-5084-2930-3
新世纪电子信息与自动化系列课程改革教材
黄爱民 安向京 骆力
中国水利水电出版社
数字图像处理与分析基础
第五章 图像变换
? 概述和分类
? 离散 Fourier变换
? 快速算法
? 其它可分离图像变换
? Hotelling变换
? 作业
数字图像处理与分析基础
5.1概述和分类
图像变换 ——图像转换到另一种空间处理，特有性质
图像处理和分析的数学基础
图
像
变
换
可分离变换
统计变换
Fourier变换 (DFT)
DCT
WHT
ST
HT,Wavlet Transform
Hotelling
数字图像处理与分析基础
5.2 离散 Fourier变换
? 定义
? 性质
? 快速算法
? 应用
数字图像处理与分析基础
5.2.1 2DFT
(Two Dimensions Fourier Transform）
2
1
22 )],(),([),( vuIvuRvuF ??
)].,(),,(a r c t a n [),( vuRvuIvu ??
),(),(),( 22 vuIvuRvuE ??
1??j
相位谱：
R(u,v)和 I(u,v)分别是 F(u,v)的实部与虚部。
? ??
?
?
?
?????
1
0
1
0
1,..,2,1,0,],/)(2e x p [),(1),(
N
x
N
y
NvuNvyuxjyxfNvuF ?
? ??
?
?
?
???? 1
0
1
0
1,.,,2,1,0y,x],/)(2e x p [),(1),( N
u
N
v
NNvyuxjvuFNyxf ?
能量谱：
u,v-- Frequency variable,|F(u,v)|-- Fourier Spectrum,
数字图像处理与分析基础
图 5-2 Fourier基函数
0
1
2
3
4
5
6
7
8
0 4 8 12 16
(a)正弦分量（前 1/2）
0
1
2
4
5
6
7
0 4 8 12 16
3
8
(b)余弦分量（前 1/2）
数字图像处理与分析基础
例,DFT的计算
一维函数的四个采样值为 f(0)=2,f(1)=3,f(2)=f(3)=4.
25.3]4432[
4
1
)]3()2()1()0([
4
1
]0e x p [)(
4
1
)0(
3
0
?????
????? ?
?
ffffxfF
x
]2[
4
1
]4432[
4
1
]4/2e x p [)(
4
1
)1(
2/32/0
3
0
jeeee
xjxfF
jjj
x
???????
??
???
?
?
???
?
]01[
4
1
]4432[
4
1
]4/4e x p [)(
4
1
)2(
320
3
0
jeeee
xjxfF
jjj
x
???????
??
???
?
?
???
?
]2[
4
1
]4432[
4
1
]4/6e x p [)(
4
1
)3(
2/932/30
3
0
jeeee
xjxfF
jjj
x
???????
??
???
?
?
???
?
f(x)全部值对 FT
都产生影响；反
之，全部变换系
数对反变换也产
生影响。
数字图像处理与分析基础
数字图像处理与分析基础
5.2.2 付立叶变换的性质
Properties of the Fourier Transform
1,付立叶频谱的显示 Fourier Spectrum Display：
D(u,v)=log[1+|F(u,v)|] (5-5)
2,可分离性 Separable Product
F(u,v)=1/N?x?y f(x,y)exp[- j2?(ux+vy)/N] (5-6)
=1/N ?xexp[- j2?ux/N]? ?y f(x,y) exp[- j2?vy/N]
=1/N ?x F(x,v) exp[- j2?ux/N]
其中 F(x,v)=N[1/N ?y f(x,y) exp(- j2?vy/N)]。
数字图像处理与分析基础
Fourier变换的分离性
yN-1
N-1 f(x,y)
0
x
N-1
N-1 F(x,v)
0
x
N-1
N-1 F(u,v)
0
u
行变换 列变换
v v
数字图像处理与分析基础
变换的基函数可分解：
}/)(2s in {}/)(2c o s {
}/)(2e x p {),;,(
},/)(2s in {}/)(2c o s {
}/)(2e x p {),;,(
NvyuxjNvyux
NvyuxjvuyxB
NvyuxjNvyux
NvyuxjvuyxA
????
??
????
???
??
?
??
?
数字图像处理与分析基础
3,The Shift Theorem
? 频移性
? 平移性
数字图像处理与分析基础
频移性
? f(x,y)exp[j2?(u0x+v0y)/N]?F(u-u0,v-v0)
? 当 u0=v0=N/2时，
exp[j2?(u0x+v0y)/N]=(-1)x+y,
则 f(x,y) (-1)x+y ?F(u-N/2,v-N/2)
频谱原点移到中心
? 正向 Fourier变换前需要进行数据处理
数字图像处理与分析基础
平移性
f(x-x0,y-y0) ?F(u,v)exp[- j2?(u0x+v0y)/N].
|F(u,v)exp[j2?(ux0+vy0)/N]|=|F(u,v)|
? 图像平移不影响频谱
数字图像处理与分析基础
数字图像处理与分析基础
4,变换域的周期性 Periodicity,T=N,
F(u,v)=F(u+N,v)=F(u,v+N)=F(u+mN,v+nN).
5,对称共轭性 Conjugate Symmetry,
F(u,v)=F*(-u,-v),|F(u,v)|=|F(-u,-v)|.
6,旋转 Rotation,
x=rcos?,y=rsin?,u=?cos?,v=?sin?,
f(r,? + ?0) ? F(?,?+ ?0)，对连续、离散均
成立。
?
数字图像处理与分析基础
注意观察对应关系
数字图像处理与分析基础
图 5-6 Jean Buptiste Joseph
Fourier和他的付立叶变换
(a)输入图像
(b)幅值谱
(c)相位谱
(d)由幅值谱重构的图象
(e)由相位谱重构的图象
结论,相位谱可能具有
更重要的应用
数字图像处理与分析基础
7,Rayleigh’s Theorem:
? define energy=? (-?,+ ?) |f(t)|2dt,
? then,
? (-?,+ ?) |f(t)|2dt=? (-?,+ ?) |F(s)|2ds.
? Power,
? (-?,+ ?) f(x)g*(x)dx=? (-?,+ ?) F(s)G(s)ds
数字图像处理与分析基础
（ 1）相加性
F{f1(x,y)+f1 (x,y)}=F{f1(x,y)}+F{f2(x,y)},
F{f1 (x,y)f2 (x,y)}!= F{f1 (x,y)}F{f2 (x,y)}.
（ 2）尺度变换
设 a,b是两标量，
af(x,y) ? aF(u,v),
f(ax,by) ? 1/|ab|F(u/a,v/b).
8,The Addition Theorem and
The Similarity Theorem
数字图像处理与分析基础
9,The Average
)0,0(1),(1),(
1
0
1
0
2 FNyxfNyxf
N
x
N
y
? ??
?
?
?
??
2
2
2
2
2 ),(
y
f
x
fyxf
?
??
?
???
10,Laplacian
),()()2()},({ 2222 vuFvuyxfF ???? ?
数字图像处理与分析基础
空域和频率域之间的关系
（ 1） The Convolution
f(x)*g(x)?F(u)G(u),
f(x)g(x)?F(u)*G(u),
? ???? ?? ??? dxgfxgxf )()()(*)(
11,The Convolution and Correlation
Theorem
数字图像处理与分析基础
The Theorem, 离散信号 f(x),A； g(x),B
扩展成周期函数 fe(x),ge(x),,M?A+B-1
?
?
?
???
???
?
?
?
?
???
???
?
.1,0
,10),(
)(
.1,0
,10),(
)(
MxA
Axxg
xg
MxA
Axxf
xf
e
e
?
?
?
????
1
0
1,...,1,0),()()(*)(
M
m
eeee Mxmxgmfxgxf
卷积定理的效能：点数 ?32时,FFT方法较快。
数字图像处理与分析基础
???? ??
??
?? dxgfxgxf )()()()( ?
?
?
?
????
1
0
1,...,2,1,0),()()()(
M
m
eeee Mxmxgmfxgxf ?
Theorem,f(x,y)?g(x,y) ?F(u,v)G*(u,v),
f(x,y)g*(x,y) ?F(u,v) ? G(u,v),
“*”表示复共轭。
（ 2） Correlation
数字图像处理与分析基础
5.2.3快速算法
（ 1）因子分解：稀疏矩阵
（ 2） 1D FFT算法：“逐次加倍”，“蝶形
算法”
数字图像处理与分析基础
逐次加倍算法
1,.,,,2,1,0
},)12(
1
)2(
1
{
2
1
})12(
1
)2(
1
{
2
1
)(
2
1
)(
.,2 ;,2
]./2e x p [,)(
1
)(
2
1
0
1
0
WW
)12(
2
1
0
)2(
2
1
0
,
2
12
0
1
0
ux
M
2 u x
2M
??
???
???
?
????
???
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
Mu
WWxf
M
Wxf
M
Wxf
M
Wxf
M
Wxf
M
uFt h e n
NMMNNnNl e t
NjWWxf
N
uF
u
M
ux
M
M
x
ux
M
M
x
xu
M
M
x
xu
M
M
x
odde v e n
ux
M
M
x
n
N
ux
N
N
x
?
数字图像处理与分析基础
}.)()({
2
1
)(
,,
})()({
2
1
)(
2
22
2
u
Moe
u
M
Mu
M
u
M
Mu
M
u
Moe
WuFuFMuF
WWWW
WuFuFuFt h e n
???
???
??
??
1,.,,,2,1,0
,)12(
1
)(
,)2(
1
)(,
1
0
1
0
??
??
?
?
?
?
?
?
?
Mu
Wxf
M
uF
Wxf
M
uFd e f
ux
M
M
x
o
ux
M
M
x
e
数字图像处理与分析基础
逐次加倍 FFT来源：两点变换由两个一点变换算
出，四点变换由两个两点变换算出，对于 N等于
2的整数幂都成立。
Xm(p) X m+1(p)
Xm(q) X m+1(q)WNr
图 5-7 只要求一次复数乘法的简化蝶形图
运算量分析
数字图像处理与分析基础
WN0
WN0
WN0
WN2
-1
-1
-1
-1
WN0
WN0
WN0
WN2
-1
-1
-1
-1
WN0
WN1
WN3
WN2
-1
-1
-1
-1
X(0)
X(4)
X(2)
X(6)
X(1)
X(7)
X(3)
X(5)
y(0)
y(7)
y(6)
y(5)
y(4)
y(3)
y(2)
y(1)
图 5-18利用蝶形图构成的 8点 DFT的流程图
数字图像处理与分析基础
同址计算，输出正常次序，
输入倒位序，序数的二进
制码。
(n2n1n1)--(n0n1n2),
x0(000)=x(000),
x0(001)=x(100),
x0(010)=x(010),
x0(011)=x(110),
x0(100)=x(001),
x0(101)=x(101),
x0(110)=x(011),
x0(111)=x(111),
X(n2 n1 n0)
X(000)
X(100)
X(010)
X(110)
X(101)
X(011)
X(111)
X(001)
0
1
1 1
1
1
1
0
0
0
0
图 5-9描述倒位序的树状图
偶数取样在上半部，奇数取样在下半部。
不断将离散付立叶变换分解成较小的离散
付立叶变换造成序列 x(n)倒位序。
数字图像处理与分析基础
5.2.4 要点小结
? 1、付立叶变换是线性积分变换，在时间（或
空间）域的复数函数和频率域的复数函数间建
立起唯一对应。
? 2、付立叶变换保持奇偶性。
? 3、函数和的付立叶变换等于它们分别变换再
求和（加法定理）。
? 4、平移函数的原点将在 Fourier谱中引入一个
相位移（与频率成正比），它改变了谱的实部
和虚部的能量分配，但不改变总能量（位移定
理）。
数字图像处理与分析基础
? 5、两个函数的卷积对应于它们付立叶变换相乘
（卷积定理）。
? 6、压缩一个函数会扩展它的付立叶变换，反之
亦然（尺度变换定理）。
? 7、函数的能量同其付立叶变换谱的能量相等。
? 8、能量有限的输入信号可被分解为有限多个正
余弦函数的和差。
? 9、旋转二维函数，它的付立叶变换也旋转相同
的角度。
? 10、自相关函数的付立叶变换是能量谱。
数字图像处理与分析基础
5.3 线性变换
g(x,u)称为 正变换核 。
h(x,u)称为 反变换核 。
If g(x,y,u,v)=g1(x,u)g2(y,v),则核 可分离 ;
If g1=g2,则核 加法对称 。
??
?
?
1
0
),()()(
N
x
uxgxfuT
??
?
?
1
0
),()()(
N
u
uxhuTxf
? ??
?
?
?
?
1
0
1
0
),,,(),(),(
N
x
N
y
vuyxgyxfvuT
? ??
?
?
?
?
1
0
1
0
),,,(),(),(
N
u
N
v
vuyxhvuTyxf
数字图像处理与分析基础
分离性
? 所有具有可分离核的二维变换与离散
Fourier变换一样，可以分成两个一维变
换分步进行。
? 沿着 f(x,y)的每一行作一维变换，得到：
? 沿着 T(x,v)的每一列作一维变换，得到
?
?
?
?
1
0
2 ),(),(),(
N
y
vygyxfvxT
??
?
?
1
0
1 ),(),(),(
N
x
uxgvxTvuT
数字图像处理与分析基础
图像变换的矩阵表示
设 f为数字图像 f(x,y)的灰度值方阵，大小为 N?N，显然
f是实数矩阵。实数矩阵总可以经过一系列初等变换，
找到它的同型矩阵 F，使得：
F=PfQ
式中 F,f是 N?N方阵,P,Q是 N?N的满秩方阵，且 P、
Q不唯一 。
由于 P,Q满秩，它们有逆矩阵 P-1,Q-1，分别用 P-1左
乘，右乘 Q-1上 式，得：
f=P-1FQ-1
表明：数字图像可以从它的正交变换中完整地恢复 。
数字图像处理与分析基础
图像变换的矩阵表达式与代数表达式本
质相同
? ?
?
?
?
?
?
1
0
1
0
),(),(),(),(
N
x
N
y
vyQyxfuxPvuF
]/2e x p [1),(),( 1 NuxjNuxguxP ????
]/2e x p [1),(),( 2 NvyjNvygvyQ ????
数字图像处理与分析基础
如果 g(x,y,u,v)可分离，则有 T=AFAT；
设 FN*N为图像,AN*N为变换矩阵,
其中 aij=g1(i,j),TN*N为结果,
如果 A=AT,T=AFA,
存在反变换矩阵 B,BTB=BAFAB，
?数字图像可以从它的变换中完整地恢复
?变换矩阵可分解成稀疏矩阵的乘积形式，
由此构造快速算法 --分解方法。
数字图像处理与分析基础
3、正交变换的本质
数字图像表示成矩阵的形式时，可以将图像变换看作若干
个图像的加权和。如果将 P,Q用列矢量表示
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
?
1
0
1
0
1
1
0
110
),(
)1,1()0,1(
)1,1()0,1(
)1,0()00(
)(
N
i
N
j
T
ji
T
N
T
T
N
qpjif
q
q
q
NNfNf
Nff
Nff
pppF
?
?
???
?
?
?
，
数字图像处理与分析基础
3、正交变换的本质
数字图像表示成矩阵的形式时，可以将图像变换看作若干
个图像的加权和。如果将 P,Q用列矢量表示
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
?
?
?
1
0
1
0
1
1
0
110
),(
)1,1()0,1(
)1,1()0,1(
)1,0()00(
)(
N
i
N
j
T
ji
T
N
T
T
N
qpjif
q
q
q
NNfNf
Nff
Nff
pppF
?
?
???
?
?
?
，
数字图像处理与分析基础
5.4 正弦型变换
? 基函数为正 -余弦波的正交变换
? 如离散余弦变换（ Discrete Cosine Transform，
DCT）
? JPEG图像压缩标准的基本推荐算法。
? 离散正弦变换（ DST ）
? 离散哈特利（ Hartley）
? 快速算法
数字图像处理与分析基础
5.4.1 DCT（次最优正交变换）
一维离散余弦变换的正变换核为：
??
?
??
? ??
N
uxuauxg
2
)12(c o s)(),( ?
1,...,1,0 ?? Nx
，
1,...,2,1 ?? Nu
?
?
?
??
??
1,,2,1,/2
0,/1)(
NuN
uNua
?当
当
??
?
??
? ?? ? ?
? N
uxxfuauC N
x 2
)12(c o s)()()( 1
0
?
。
数字图像处理与分析基础
反变换
一维 DCT的反变换核与正变换核一致，即
),(),( uxguxh ?
反变换表示为：
??
?
??
? ?? ? ?
? N
uxuCuaxf N
u 2
)12(c o s)()()( 1
0
?
一维余弦函数的基函数的图形与 Fourier基函数类似
数字图像处理与分析基础
2D DCT
??
?
??
? ?
??
?
??
? ??
N
vy
N
uxvauavuyxg
2
)12(c o s
2
)12(c o s)()(),,,( ??
?
?
?
??
??
1,,2,1,/2
0,/1)(
NuN
uNua
?当
当
a(v)与 a(u)定义类似。
DCT的反变换核与正变换核一致：
).,,,(),,,( vuyxgvuyxh ?
数字图像处理与分析基础
2D DCT变换对
??
?
??
? ?
??
?
??
? ?? ? ??
?
?
? N
vy
N
uxyxfvauavuC N
x
N
y 2
)12(c o s
2
)12(c o s),()()(),( 1
0
1
0
??
??????
?
??????
?? ? ??
?
?
? N
vy
N
uxvuCvauayxf N
u
N
v 2
)12(c o s
2
)12(c o s),()()(),( 1
0
1
0
??
数字图像处理与分析基础
2D DCT基图像
图 5.4.1 二维 DCT基图像
数字图像处理与分析基础
性质
? 可分离性、对称性
? 快速算法
? 代数分解：蝶形图
? 矩阵分解：稀疏矩阵的积，不唯一
数字图像处理与分析基础
数字图像处理与分析基础
5.5 离散 KL变换 (Karhunen-Loeve)(DKT)
? Hotelling变换、特征向量变换
(Eigenvector-Based Transform)、主分
量变换。
? 利用图像的统计性质，统计模型。
? 应用
? 数据压缩
? 图形旋转
数字图像处理与分析基础
5.5.1 定义
图像 f N?N (x,y),传输 M次，
接收集合 {fi(x,y),i=1,2,…,M}
统计总体，通道特征、干扰性质。
采样图像,Xi=(xi1,xi2,…,xiN2)T,
按行或按列依次排列，
协方差矩阵 CX=E{(X-Mx)(X-Mx)T},
Mx为均值向量,Mx=E{X}，
近似表示：
?
?
?
?
??
???
M
i
T
XX
T
ii
M
i
T
XiXiX
MMXX
M
MXMX
M
C
1
1
][
1
))((
1
?
?
??
M
i
iX XMXEM
1
1}{
数字图像处理与分析基础
?
?
?
?
?
?
?
?
?
?
?
2222
2
21
11211
NNNN
N
eee
eee
A
?
?
?
令 ei,?i,i=1,2,…,N2分别表示矩阵的特征矢量与特
征值，将 ?i减序排列,?1> ?i2>…?N2,
构造变换矩阵：
K-L变换定义,Y=A(X-MX).
Y为新产生的图像向量。
数字图像处理与分析基础
1）半正定矩阵的性质
CX实对称矩阵
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
???
?
2
0
0
}))({(;0
2
1
N
T
X
T
YY
Y
AAC
mYmYEC
m
?
?
?
?
5.4.2 Property
数字图像处理与分析基础
2）最优变换
CX实对称矩阵，总可以找到标准正交的特征向量集
合构成 A,A-1=A’,由 Y利用 X=A’Y+MX 重建 X。
压缩,k个大的 ?i,Ak,
离散 K-L变换在最小平方误差的意义上最优。
???
????
?????
??
22
111
2 })?{(;
N
kj
j
k
j
j
N
j
j
X
T
k
XXER
mTAX
???
数字图像处理与分析基础
缺点
1）非分离，计算 CX,及其特征值、特征向量；
2）无快速算法。
作用：
1）比较其它方法（在编码及图像压缩等方面）的
效率。
2）图像标准化（旋转）
数字图像处理与分析基础
5.4.3Application in Image Rotate
? 第一基向量与数据中最大变化的方向相
对应。
? 目标已抽出，希望与某个标准的、或不
变的方向对准。右手坐标系。
? 处理对象：目标中各像素的坐标。
数字图像处理与分析基础
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
??
??
??
??
??
??
??
c o ss i n
s i nc o s
c o ss i n
s i nc o s
c o ss i n
s i nc o s
2221
1211
2
1
2
1
212
211
ee
ee
A
AX
x
x
y
y
Y
xxy
xxy
数字图像处理与分析基础
1,K-l变换用于图像旋转
(a) (b)
(c)
x1
y1y
2
x2
0
e1
e2 y1
y1
y1
y1
二维目标的旋转。 (a)原始数据的散布指明单位特征
向量的方向； (b)利用变换 Y=AX作数据旋转； ( c)利
用变换 Y=A(X-MX)作数据旋转和中心化
数字图像处理与分析基础
例 设图像目标区域由四个像素构成
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
? ?
??
?
?
?
?
? ?
?
4
2
,
3
1
,
1
1
,
0
2
23
21
xx
xx
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
??
?
?
?
?
? ?
??
?
?
?
?
? ?
?
?? ?
?
2
0
4
2
3
1
1
1
0
2
4
1
4
1
}{
4
1i
i
XXEM
4
3
21
1 2-2 -1 X1
y
(a)原始空间
数字图像处理与分析基础
向量的均值非零，将每个数据点减去均值向量后
可实现中心化,Y=X-M
??
?
??
?
?
??
??
?
??
??
??
?
??
? ??
??
?
??
??
2
2
2
0
0
2
2
1
1 y
yY,
??
?
??
?
?
??
??
?
??
??
??
?
??
? ??
1
1
2
0
1
1
2Y
,
??
?
??
??
??
?
??
??
??
?
??
??
1
1
2
0
3
1
3Y
,
??
?
??
??
??
?
??
??
??
?
??
??
2
0
2
0
4
2
4Y
y1
2
1
1 2
-2 -1
y2
(b)中心化
数字图像处理与分析基础
? ? ? ? ? ? ? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
?
?
????
?
?
?
?
?
?
?
????
?
?
?
?
?
?
?
?? ?
?
?
4
10
4
10
4
10
4
10
22
2
2
11
1
1
11
1
1
22
2
2
4
1
4
1
4
1
T
i
i
i
iy
YYC
设协方差矩阵的特征值为 ?，有,0?? IC
y ?
式中 I为单位矩阵，因此有：
0
4
10
4
10
4
10
4
10
?
?
?
?
?
数字图像处理与分析基础
由此得到变换方程：
0
4
10
4
10 22 ?
?
?
??
?
???
?
??
?
? ? ?
化简得：
0)5( ????
因此特征值是,?1=5,?2=0。
数字图像处理与分析基础
下面求对应于每个特征值的特征矢量 Y=(y1,y2)T：
令
YYC Y 1??
得
?
?
?
?
?
?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2
1
2
1
5
4
10
4
10
4
10
4
10
y
y
y
y
化简后两个方程具有相同的形式：
021 ?? yy
不失一般性，取,TY )1 1(
1 ?
这是与 ?1=5相对应的特征向量。
数字图像处理与分析基础
类似方法得到与 ?1=0对应的特征向量 Y2：
TY )1- 1(1 ?
将特征向量归一化：
??
?
??
?
????
?
??
??
1
1
2
1,
1
1
2
1
21 YY
转换矩阵 A为：
?
?
?
?
?
?
?
?
?
?
?
?
?
?
2
1
2
1
2
1
2
1
A
数字图像处理与分析基础
?
?
?
?
?
? ?
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
0
8
2
2
2
1
2
1
2
1
2
1
11 AYZ
变换值为,Z=AY
,
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
0
8
0
2
0
2
4
3
2
Z
Z
Z
z1
1
2
-2 -1
z2
(c)沿特征矢量旋转
数字图像处理与分析基础
减少数据量、运算量
人脸图像
样本库
人脸特征
样本库
待识人脸图像
变换矩阵
特征变化
特征匹配
K-L变换
身份
确认
2,K-L变换用于图像压缩 --人脸识别 --
特征脸
数字图像处理与分析基础
5.5 Walsh Transform
? Walsh函数系是 完备正交函数系，只取
两种值，在归一化条件下只取 +1,-1。
? 典型非正弦正交变换，方波变换
? 分三类，区别于编号,Walsh,Paley,
Hadamard
数字图像处理与分析基础
5.5.1 Walsh编码的离散形式
当 N=2n时,W(u),f(x)的正交变换核,
,)1(1),( )()(
1
0
1 ubxb
n
i
ini
Nuxg
?????
?
?
x,u=0,1,…,N-1,N=2n,
bk(x)表示 x的二进制码的第 k位值,
)()(1
0
1)1(),( ubxb
n
i
iniuxh ?????
?
?
数字图像处理与分析基础
二维：
g(x,y,u,v)=g1(x,u)g1(y,v)
=h1(x,u)h2(y,v)=h(x,y,u,v)
快速算法：
与 FFT类似，所有指数项改为 1。只有实数加减。
数字图像处理与分析基础
?
?
?
?
?
?
??
??
1
0
1
0
)()(
)()(
)1(),(
,)1(
1
),(
n
i
ii
n
i
ii
ubxb
ubxb
uxh
N
uxg
构造具有递推形式,N=2，
222,11
11 HH
HH
HHHH
N
NN
NN
n ????
?
??
?
????
?
??
?
??
5.5.2 Hadamard
N<200,Hadamard变换均存在
数字图像处理与分析基础
7
6
5
4
3
2
1
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
22
1
5
2
6
1
4
3
7
0
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
22
1
8
8
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
????
????
????
????
????
????
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
????
????
????
????
????
????
????
?
H
W
数字图像处理与分析基础
)()()(
,
),()()(
),()(
,)1(
1
),(
011
211
10
)()(
1
0
ububup
ububup
ubup
N
uxg
n
nn
n
upxb
n
i
ii
??
??
?
???
?
??
?
?
?
?
Hadamard矩阵有列率（ the sequence of the
row:the number of sign changes along the
correnponding row） 性，通常写成按列率 u增加
而增加的函数。模 2加法。
数字图像处理与分析基础
5.5.3 快速算法
1）提取公共项
例：序列 (x0,x1,x2,x3)
的 Walsh变换：
6次加减代替 12次
)]()[(
4
1
)(
4
1
)]()[(
4
1
)(
4
1
)]()[(
4
1
)(
4
1
)]()[(
4
1
)(
4
1
,
1111
1111
1111
1111
4
1
312032103
312032102
312032101
312032100
3
2
1
0
3
2
1
0
xxxxxxxxy
xxxxxxxxy
xxxxxxxxy
xxxxxxxxy
x
x
x
x
y
y
y
y
????????
????????
????????
????????
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
数字图像处理与分析基础
2)矩阵分解技术：找公共项，利用直积形式分解，用
中间 结果计算
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
73
62
51
40
4
7
6
5
4
4
3
2
1
0
4
7
6
5
4
73
62
51
40
4
7
6
5
4
4
3
2
1
0
4
3
2
1
0
44
44
8
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
,8
xx
xx
xx
xx
H
x
x
x
x
H
x
x
x
x
H
y
y
y
y
xx
xx
xx
xx
H
x
x
x
x
H
x
x
x
x
H
y
y
y
y
X
HH
HH
XHYN
T
数字图像处理与分析基础
3）应用矩阵因子分解, HN分解成几个稀疏矩阵
的乘积，
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
10001000
01000100
00100010
00010001
10001000
01000100
00100010
00010001
,
1010
0101
0010
0101
0
0
1010
0101
1010
0101
,
11
11
11
11
0
0
11
11
11
11
2
10
F
FF
W8=F0F1F2
数字图像处理与分析基础
5.8 要点小结
1、一个 N*N变换矩阵的行是 N维向量空间的一组正交
基向量。
2、线性酉变换产生一个含有 N个变换系数的向量，每
个变换系数是输入向量与变换矩阵的某行的内积。
3、反变换也是通过变换系数向量与变换矩阵的行的内
积生成的。
4、反变换也可以看作是构造基向量的一个加权和，变
换系数就是权。
5、二维对称可分离的酉变换，基图像是变换图像不同
行之间的外积。
