Gonzalez R. C. and Woods R. E. Digital Image Processing (Forth Edition)
基本
酉变换
一维的变换:
[mathbf{t} = mathbf{A} mathbf{f}, \
mathbf{f} = mathbf{A}^{H} mathbf{t}, \
mathbf{A}^H = {mathbf{A}^*}^{T}, mathbf{A}^Hmathbf{A} = mathbf{I}.
]
以及二维的变换:
[mathbf{T} = mathbf{A} mathbf{F} mathbf{B}^T, \
mathbf{F} = mathbf{A}^H mathbf{T} mathbf{B}^*, \
mathbf{A}^Hmathbf{A=I}, mathbf{B}^{T}mathbf{B}^* =mathbf{I}.
]
以一维的为例, 实际上就是
[t_u = sum_{x = 0}^{N-1} f_x s(x, u) = mathbf{f}^T mathbf{s}_u, u=0,1,cdots, N-1,\
mathbf{s}_u = [s(0, u), s(1, u), cdots, s(N-1, u)]^T.
]
故
[mathbf{A} = [mathbf{s}_0, cdots, mathbf{s}_{N-1}]^{T}.
]
others
[sum_{k=0}^n sin (kx) = frac{cos(frac{1}{2}x) - cos (frac{2n+1}{2}x)}{2 sin (frac{x}{2})}, quad x in (2Kpi, 2(K+1)pi)
]
proof:
[egin{array}{ll}
2sin (frac{x}{2}) sum_{k=0}^n sin (kx)
&=sum_{k=0}^n [cos (frac{2k-1}{2}x) -cos (frac{2k+1}{2}x) ]\
&= cos(frac{1}{2}x) - cos (frac{2n+1}{2}x).
end{array}
]
类似地
[sum_{k=0}^n cos (kx) = frac{sin(frac{2k+1}{2}x) + sin (frac{1}{2}x)}{2 sin (frac{1}{2}x)}, quad x in (2Kpi, 2(K+1)pi)
]
proof:
[egin{array}{ll}
2sin (frac{x}{2}) sum_{k=0}^n cos (kx)
&=sum_{k=0}^n [sin (frac{2k+1}{2}x) -sin (frac{2k-1}{2}x) ]\
&= sin(frac{2k+1}{2}x) + sin (frac{1}{2}x).
end{array}
]
Fourier-related Transforms
DFT
[s(x, u) = frac{1}{sqrt{N}} e^{frac{-j2pi xu}{N}}
]
(mathbf{s}_u^H mathbf{s}_u = 1)是显然的, 又注意到
[mathbf{s}_u^H mathbf{s}_{u'} = frac{1}{N}sum_{x=0}^{N-1} e^{frac{-j2pi x(u-u')}{N}},
]
又
[sum_{n=0}^{N-1} a^n = frac{1-a^N}{1-a},
]
由于
[e^{-j2pi x (u - u')} = 1, forall u
ot = u'.
]
DHT
DISCRETE HARTLEY TRANSFORM
[s(x, u) = frac{1}{sqrt{N}}mathrm{cas}(frac{2pi xu}{N}) = frac{1}{sqrt{N}}[cos (frac{2pi ux}{N}) + sin (frac{2pi ux}{N})].
]
[2cos (frac{2pi ux}{N})
cos (frac{2pi u'x}{N})
=cos (frac{2pi (u-u')x}{N})
+cos (frac{2pi (u+u')x}{N}) \
2sin (frac{2pi ux}{N})
sin (frac{2pi u'x}{N})
=cos (frac{2pi (u-u')x}{N})
-cos (frac{2pi (u+u')x}{N}) \
2sin (frac{2pi ux}{N})
cos (frac{2pi u'x}{N})
=sin (frac{2pi (u+u')x}{N})
-sin (frac{2pi (u-u')x}{N}) \
]
故想要证明其为标准正交基, 只需注意到:
[sum_{x=0}^{N-1} sin (frac{2pi k x}{N})
=frac{cos(frac{kpi}{N}) - cos (frac{(2N-1)kpi}{N})}{...},
]
(k ot=0)的时候, 有
[cos (frac{(2N-1)kpi}{N}) = cos (frac{kpi}{N}),
]
故
[sum_{x=0}^{N-1}sin (frac{2pi kx}{N}) =0, k
ot=0.
]
类似可得:
[sum_{x=0}^{N-1}cos (frac{2pi kx}{N}) =0, k
ot=0.
]
正交性如此是易证明的, 实际上标准性是显然的.
DCT
DISCRETE COSINE TRANSFORM
[s(x, u) = alpha (u) cos (frac{(2x + 1)upi}{2N}), \
alpha (u) =
left {
egin{array}{ll}
sqrt{frac{1}{N}}, & u=0, \
sqrt{frac{2}{N}}, & u=1,2,cdots, N-1. \
end{array}
ight .
]
其标准正交的思路和DHT是如出一辙的.
与DFT的联系
- 定义
[g(x) =
left {
egin{array}{ll}
f(x), & x = 0, 1, cdots, N-1, \
f(2N-x-1), & u=N, N+1, cdots, 2N-1. \
end{array}
ight .
]
此时(g(x) = g(2N-1-x));
- 计算DFT
[mathbf{t}_F = mathbf{A}_F mathbf{g} =
left [
egin{array}{c}
mathbf{t}_1 \
mathbf{t}_2 \
end{array}
ight ].
]
- 定义
[h(u) = e^{-jpi u / 2N}, u=0,1,cdots, N-1, \
mathbf{s} = [1 / sqrt{2}, 1, 1, cdots, 1]^T.
]
[mathbf{t}_C = mathrm{Re}{mathbf{scirc h circ t_1}}.
]
其中(mathrm{Re})表示实部, (circ)表示逐项乘法.
证明是平凡的.
DST
DISCRETE SINE TRANSFORM
[s(x, u) = sqrt{frac{2}{N+1}} sin (frac{(x+1)(u+1)pi}{N+1}).
]
与DFT的联系
- 定义
[g(x) =
left {
egin{array}{ll}
0, & x = 0, \
f(x-1), & x = 1, cdots, N, \
0, & x = N + 1, \
-f(2N-x+1), & u=N+1, cdots, 2N+1. \
end{array}
ight .
]
此时(g(x) = -g(2N + 2 - x)).
- DFT
[mathbf{t}_F = mathbf{A}_F mathbf{g} =
left [
egin{array}{c}
0 \
mathbf{t}_1 \
0 \
mathbf{t}_2 \
end{array}
ight ].
]
[mathbf{t}_S = -mathrm{Imag}{mathbf{t}_1}.
]
其中(mathrm{Imag})表虚部.