多维信号处理(第二章)

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