[信息与通信]多维信号处理第二章.ppt

多维数字信号处理,主讲：陈绵书,2019/4/19,图像与视频处理实验室,2,第二章 多维信号的离散傅里叶分析,研究内容 研究多维离散傅里叶变换（DFT），考察其与傅里叶变换之间的关系； 研究计算有限区域序列的离散傅里叶变换的几个FFT算法。 多维DFT的两个要点 是有限区域序列的一种准确的傅里叶表示，也是多维周期序列的傅里叶级数展开； 变换存在潜在的周期性，可以开发有效算法。,2019/4/19,图像与视频处理实验室,3,2.1 矩形周期序列的 离散傅里叶级数表示,矩形周期序列 满足条件 其中 和 是正整数。满足上式最小的 和 称为序列的水平周期和垂直周期。 基本周期,2019/4/19,图像与视频处理实验室,4,2.1 矩形表示（续1）,二维离散傅里叶级数展开 复正弦 是矩形周期的，水平周期为 垂直周期为 为傅里叶级数系数,2019/4/19,图像与视频处理实验室,5,2.1 矩形表示（续2）,周期序列的傅里叶级数与傅里叶变换的不同 周期序列没有傅里叶变换，不是绝对可和； 傅里叶级数系数公式上下限有限，且频率是整数； 离散傅里叶级数是可计算的变换。,2019/4/19,图像与视频处理实验室,6,2.1 矩形表示（续3）,例 有周期序列， ， ， ， ， ，确定离散傅里叶级数的系数。 解,2019/4/19,图像与视频处理实验室,7,2.2 多维离散傅里叶变换,定义 有限区域序列生成周期序列 有限区域序列 ，支撑区为 ，则可以生成周期序列 同时有 将周期序列 看成有限区域傅里叶级数系数序列 的周期延拓,2019/4/19,图像与视频处理实验室,8,2.2 多维离散傅里叶变换（续1）,同时有 和 可以通过下式计算,2019/4/19,图像与视频处理实验室,9,2.2 多维离散傅里叶变换（续2）,离散傅里叶正变换 离散傅里叶逆变换,2019/4/19,图像与视频处理实验室,10,2.2 多维离散傅里叶变换（续3）,傅里叶变换和离散傅里叶变换的关系 抽样定理 空域抽样可以表示频域限带信号，如果频域非限带，则空域抽样的频谱会造成混叠； 频域抽样可以表示空域限制信号，如果空域非限制，则频域抽样的时域信号会造成混叠；,2019/4/19,图像与视频处理实验室,11,2.2 多维离散傅里叶变换（续4）,M维离散傅里叶变换 定义M维序列，其支撑区为 令对角矩阵 则M维DFT为,2019/4/19,图像与视频处理实验室,12,2.2 多维离散傅里叶变换（续5）,例 计算以下 点阵的三维DFT 解 可以表示为 令 则,2019/4/19,图像与视频处理实验室,13,2.2 多维离散傅里叶变换（续6）,2019/4/19,图像与视频处理实验室,14,2.2 多维离散傅里叶变换（续7）,例 计算 点阵的二维离散傅里叶反变换 其中， 解,2019/4/19,图像与视频处理实验室,15,2.2 多维离散傅里叶变换（续8）,2019/4/19,图像与视频处理实验室,16,2.2 多维离散傅里叶变换（续9）,离散傅里叶变换的性质 线性 如果 与 是任意有限区域序列，且 和 是任意复常数，则 支撑区的确定 若 的支撑区为 ， 的支撑区为 ，令 ，,2019/4/19,图像与视频处理实验室,17,2.2 多维离散傅里叶变换（续10）,定义两个区域已增大的序列为 序列 和 的支撑区为 ，且,2019/4/19,图像与视频处理实验室,18,2.2 多维离散傅里叶变换（续11）,循环移位 若一个有限区域序列循环移位，则DFT要乘上一个复指数 考虑周期序列 ，水平周期 ，垂直周期 ，离散傅里叶级数系数 。 令 是 的移位序列 则 和 的离散傅里叶级数系数的关系为,2019/4/19,图像与视频处理实验室,19,2.2 多维离散傅里叶变换（续12）,则定义 的循环移位序列为 即 其中 表示整变量 对 取模运算。 循环移位：从支撑区左边（或顶部）移出的抽样值，又重新出现在右边（或底部）。,2019/4/19,图像与视频处理实验室,20,2.2 多维离散傅里叶变换（续13）,DFT 定义为 循环移位离散傅里叶变换对为,2019/4/19,图像与视频处理实验室,21,2.2 多维离散傅里叶变换（续14）,实 的对称性 如果 是实的，则有 其中 表示复共轭运算。因为 所以 是Hermitian对称的,2019/4/19,图像与视频处理实验室,22,2.2 多维离散傅里叶变换（续15）,对于复有限区域序列，定义Hermitian对称分量和反对称分量 由于 则可得,2019/4/19,图像与视频处理实验室,23,2.2 多维离散傅里叶变换（续16）,反射性 如果 则 Parseval定理,2019/4/19,图像与视频处理实验室,24,2.2 多维离散傅里叶变换（续17）,对偶性 如果 则 证明 调制性,2019/4/19,图像与视频处理实验室,25,2.2 多维离散傅里叶变换（续18）,循环卷积 定义 有两个有限区域序列 和 ，支撑区是 序列满足 令 是 点DFT，表示为 问题是如何确定,2019/4/19,图像与视频处理实验室,26,2.2 多维离散傅里叶变换（续19）,讨论：考虑所有序列的周期延拓 由于 离散傅里叶级数反变换得 由于 所以,2019/4/19,图像与视频处理实验室,27,2.2 多维离散傅里叶变换（续20）,由于 所以 称 是 与 的循环卷积 另一种形式 二维循环卷积运算符,2019/4/19,图像与视频处理实验室,28,2.2 多维离散傅里叶变换（续21）,循环卷积推导线性卷积 令 支撑区为 ， 支撑区为 ， 为二者卷积 则其支撑区为 若取 则循环卷积 为,2019/4/19,图像与视频处理实验室,29,2.2 多维离散傅里叶变换（续22）,的周期延拓为 所以 则 方括号中是线性卷积，可以用 表示，所以 令 则,2019/4/19,图像与视频处理实验室,30,2.2 多维离散傅里叶变换（续23）,利用DFT计算线性卷积步骤： （1）选择 和 ，满足 （2）把 增加足够的零值抽样，以便填满 区域 （3）用类似的方法增加 的零值抽样点 （4）计算 及 的 点DFT （5）计算乘积 （6）计算 的 点反DFT,2019/4/19,图像与视频处理实验室,31,2.2 多维离散傅里叶变换（续24）,例 令 ， ， 表示列的标号， 表示行的标号， 在左下角。 解 循环卷积,2019/4/19,图像与视频处理实验室,32,2.2 多维离散傅里叶变换（续25）,代入 和 ，得 线性卷积,2019/4/19,图像与视频处理实验室,33,2.2 多维离散傅里叶变换（续26）,2019/4/19,图像与视频处理实验室,34,2.3 离散傅里叶变换的计算,直接计算 算式 其中 复杂度 每个抽样需要 次复乘数和几乎一样的复加数 总的需要 次复乘数和复加数 M维情况下，需要 次复乘数和复加数,2019/4/19,图像与视频处理实验室,35,2.3 离散傅里叶变换的计算（续1）,行-列分解法 算式 复杂度 每个抽样需要 的复乘数和复加数 总的需要 的复乘数和复加数,2019/4/19,图像与视频处理实验室,36,2.3 离散傅里叶变换的计算（续2）,M情况 算式 分解出其中最后一维 复杂度 每个抽样需要 的复乘数和复加数，总的需要 的复乘数和复加数,2019/4/19,图像与视频处理实验室,37,2.3 离散傅里叶变换的计算（续3）,算式 分解出最后二维 复杂度 每个抽样需要 的复乘数和复加数，总的需要 的复乘数和复加数,2019/4/19,图像与视频处理实验室,38,2.3 离散傅里叶变换的计算（续4）,算式 分解M维 复杂度 每个抽样需要 的复乘数和复加数，总的需要 的复乘数和复加数,2019/4/19,图像与视频处理实验室,39,2.3 离散傅里叶变换的计算（续5）,算法复杂度对比 理论复乘数 点的二维DFT的复乘数,2019/4/19,图像与视频处理实验室,40,2.3 离散傅里叶变换的计算（续6）,矢量快速傅里叶变换 原理：将一个二维DFT连续地分成更小的二维DFT，直到分为只需计算无足轻重的二维DFT时为止。 方法：分解成四个和式，一个是 为偶数 为偶数，一个是 为偶数 为奇数，一个是 为奇数 为偶数，一个是 为奇数 为奇数。,2019/4/19,图像与视频处理实验室,41,2.3 离散傅里叶变换的计算（续7）,示例： 其中,2019/4/19,图像与视频处理实验室,42,2.3 离散傅里叶变换的计算（续8）,的周期性 水平周期为 ，垂直周期为,2019/4/19,图像与视频处理实验室,43,2.3 离散傅里叶变换的计算（续9）,由于 ，所以 上式称为蝶形运算，是基 的蝶形。,2019/4/19,图像与视频处理实验室,44,2.3 离散傅里叶变换的计算（续10）,复杂度是3次复乘和8次复加 复乘 复加,2019/4/19,图像与视频处理实验室,45,2.3 离散傅里叶变换的计算（续11）,计算 的全部抽样需要 个蝶形,2019/4/19,图像与视频处理实