从序列到网格
数字图像或矩形网格上的数值解是二维数组,而不是单一序列。振荡可以沿任一坐标发生,也可以同时沿两个方向发生。二维离散傅里叶(Fourier)变换(DFT)用网格上的波来描述同一个有限数组。精确算术下,反变换能恢复每个数值;但仅靠变换本身,我们无法知道网格点之间或观测矩形之外发生了什么。
设 为正整数,复数数据 的索引满足 、。第一个索引表示行,第二个表示列。以下固定采用这一约定。
定义 2.6.1
( 数组的二维 DFT)
的变换是数组
两个频率索引分别按模 和模 理解。
零频值 ,因此样本平均数是 。有些软件在正变换或两个方向都加入归一化;比较数值振幅前须先比较其定义。
反变换与正交性
定理 2.6.2
(反变换)
对上述任意数组,
证明
(分开两个等比和)
代入正变换,交换有限求和次序。 的系数为
由有限等比级数公式,每个括号在对应差值可被其长度整除时等于该长度,否则为零。由于索引均在各自范围内,两个整除条件同时成立恰好意味着 且 。因此只剩下该项。即使其中一个维度为一,论证仍然成立。
索引 的基向量(网格波)是 ,其反变换系数为 。指定范围内不同索引对的网格波互相正交,每个波的范数平方为 ;这 个波构成 维复数数组空间的一组基。
可分离计算
指数可分解成行坐标与列坐标的因子。先沿列方向变换每一行:
第二步变换 的每一列。交换有限和可见,反过来先变换各列也得到相同结果。写成矩阵形式,这就是两边各乘一个一维 DFT 矩阵,详见下文。这个张量积结构是计算方法,并非假设数据可分解成两个一维数组的乘积。
直接从所有 个输入计算所有 个输出,需要 次算术运算。分离后直接计算的成本为 。若两个方向采用合适的一维 FFT,对非平凡维度,其合计成本通常为 ;确切成本和存储需求视长度及实现而定。FFT 重新排列的是同一个有限变换,但浮点结果未必精确。
例题 2.6.3
(二乘二数组)
取 。二点 DFT 把 映为 。逐行变换得 ,再逐列变换得
例如, 是带符号的行对比,而 是列对比。 处的反变换为 ;完整反变换恢复原来四个数值。若交换轴的标签,两个非对角系数也会交换。
例题 2.6.4
(平移二乘二数组)
把同一数组的行循环平移 、:。逐行变换得 和 ,再逐列变换得
由于 ,平移应把 的第 行乘以 ;确实只有 变号。所有模都不变:循环平移在 中看不见,完全由相位承载。下面最后一题证明一般规律。
反例模式
幅值相同并不迫使两者相差一个平移
断言:若每个频率格都有 ,则 是 的循环平移。在 网格上,令 的第一行为 , 的第一行为 ,两者第二行均为零。于是
所以两个频谱每一行的幅值都是 。然而 的四个列方向平移是 、、、,而行方向平移会把非零行移走; 不是其中任何一个。幅值相同只表示 ;平移恰好对应于关于 为线性的相位 。
能量、对称性与频率格
定理 2.6.5
(离散 Parseval 等式)
在上述惯例下,。
证明
(展开模平方)
把反变换展开式代入左边并展开模平方。两个坐标的正交性消去不同频率对之间的交叉项。每个留下的网格波范数平方为 ,故系数模平方和乘上 ,得到结论。采用其他归一化时,因子也会改变。
概念视角代数
把变换看成矩阵夹乘
令 为 矩阵,其元素为 , 同理。两者都是对称矩阵,而一维等比和恒等式说明 。定义于是写成 ;这里转置不取复共轭。反变换成为矩阵恒等式 ;又因为 和 是酉矩阵,Frobenius 范数满足 ,这正是 Parseval 等式。若把 的各列叠成一个向量,同一映射就是乘以 Kronecker 积 ,所以可分离计算是精确的,而不是近似。
若 为实数,对正变换取复共轭可得频谱的一种对称性。
定理 2.6.6
(实数据的共轭对称性)
若每个 都是实数,则对所有
证明
(对正变换取共轭)
由于 ,对定义取共轭就把每个指数 换成 。指数只按模 依赖于 ,所以结果正是 处的变换值。
若一个频率格在两个坐标上都与自身配对,它的值必为实数。例如零索引与偶数长度的中点索引都是自配对的。其余频率格成复共轭对。
常见错误
(只把一个频率变号)
两个坐标须同时变号;只改一个未必得到复共轭。对在 处为 、其余为零的实 数组,。 的配对是 ,而 。但 ,并不等于 。
常见错误
(实数输入不代表每个系数都是实数)
只有自配对的频率格才一定是实数。 数组 的 。
例题 2.6.7
(二乘四网格上的自配对频率格)
令 的第一行为 ,第二行为零。则对 有 。由于 ,两个行索引都是自配对的; 时列索引 和 也是,所以 的四个频率格必为实数:它们等于 和 。其余频率格按 配对,而确实 。数一数实参数:四个实频率格加两组共轭对,共 ,与 的八个实数元素相符。
较大的索引如 可代表频率 ,因为两者在网格上取值相同。若行间距为 ,代表元 对应该坐标的物理频率 ,单位为每单位长度的周期数;列方向类似。偶数长度的中点频率,其正负代表元在网格上重合,解读时须选定惯例。有些图把零频移到中央,这只是频谱的排列,并非另一种变换。图像显示也可能转置轴;须记录每个索引对应的物理方向。
网格无法提供什么
对整数 ,把波的频率 换成 ,网格样本和 DFT 都不变。因此不同连续波可以产生相同数据;没有额外假设,任何变换都无法区分它们。矩形截取会被视为周期数组的一个周期。边界不匹配可令能量散布至多个频率格;乘上窗函数会改变泄漏,也会改变振幅。补零增加的是零而非新的测量,并会改变数组及频率网格。用频谱相乘计算卷积时,除非按预期线性操作选择补零和边界惯例,否则会出现周期性折返。
练习与解答
快速检查
(求常数数组 的变换。)
每个坐标的和都是等比和。
解答 · 答案
两个坐标的和在非零剩余类上都为零,所以 ,其余频率格全为零。反变换在每点给出 。
快速检查
(在 网格上令 。求其非零频率格。)
数组是一个行因子与一个列因子的乘积。
解答 · 答案
行方向的和 在 时为 ,在 时为零。列方向的和在 时为 ,其他情况为零。因此 ,其余全为零;其反变换系数为 。
快速检查
(验证二乘二例子的 Parseval 等式,并解释这里为什么不能直接把频谱模平方相加。)
把两个和与因子 比较。
解答 · 答案
样本能量为 ,频谱模平方和为 ;除以 后得 。所选约定下的正变换不是酉变换。
快速检查
(对整数 ,设 。求其变换 与 的关系。)
代入平移后的求和索引。
解答 · 答案
分别按模代换 、;这只是重新排列求和索引,而指数可以分离,因此 。相位改变,模不变。所以仅凭模不能定位数组:任何非平凡的循环位移都有相同的频谱模。