图像的定点FFT变换的精度分析 摘要: 目前在一些专用的 DSP系统中,要求用定点算法实现快速傅立叶变换,在这种情况下,字长对计算精度的影响无论对系统的设计还是对现有机器可以达到的精度来说都是非常重要的。本文就图像处理中的定点FFT算法所作的一种精度分析, 并导出了FFT变换引入的最大噪-信比。 并在TMS320C64x仿真器上验证了理论分析的正确性. 关键字: 图像处理 快速傅立叶变换 精度分析 Abstract : Now many DSP systems need the fixed-point FFT to improve the speed of image processing .The precision in FFT calculation brought by the word length should be thought much of in the system designing . A precision analysis was put forward in this paper about the fixed-point FFT , and the max ratio of the noise to signal was educed . The result of simulations based on TMS320DM642’s simulator are in agreement with the theoretical analysis . Keywords: Image processing FFT Precision Analysis 一、前言 如果x(n),n=0,1,2,……….,N-1是一个复数序列,则x(n)的有限傅立叶变换为下述序列:
根据Wnk<N的特性,对于定点FFT有许多不同的算法结构,但在不同类的算法中误差噪声的影响是非常相似的,在此我们只分析基-2按时间抽取算法中的精度问题。 二、一维定点FFT的分析 对于长度为N=2m的序列x(n),其中m是整数(如果不满足此条件,可以人为地增补零值点来达到),在基-2按时间抽取的快速算法中,计算DFT需用m=log2N级,在每一级序列中的N个数均由先前数列中的两个素线性组合在一起而产生。对于基-2算法的第i级蝶形运算,用Xi-1(p)和Xi-1(q)表示原来的复数,则新的一对复数Xi(p)、Xi(q)可表示为: Xi(p)= Xi-1(p)+ Xi-1(q)*W (3) Xi(p)= Xi-1(p)- Xi-1(q)*W (4) 其中, 为旋转因子, 和 表示在每个数列中数的位置(应注意,i=0指输入数列,而i=m指输出数列)。该蝶形计算的流图如图一。
在这一分析之前,我们首先假定输入序列用 位加上一个符号位表示,二进制小数点定在最左位的左边,我们把定点运算与一个加性噪声发生器联系在一起来建立误差噪声的模型(如图二),ε[i,q]代表在由第 级数列计算第 级数列的第q个素时产生的量化误差和溢出误差的和。
在上述计算过程中的主要的量化误差和溢出误差来源于: 1) 两个B位数相乘,会得到一个2B位的积。如果把该积舍入为B位,就会产生误差。当被截去的各位bB+1,…, b2B都是1时,误差最大,设误差为(e)max,
2) 两个B位数相加而有溢出时,则其和必须右移,因而失掉一位。若此位为0,则没有误差发生,若该位为1,则根据数的正、负而产生+_2-B的误差,这个误差的方差(若假定正数和负数的个数相同,则它是无偏的)为:
此外,我们还考虑原始序列中自身误差传播的影响,把这些误差的方差记为δ2。 根据参考文献[1],由每个基噪声源产生的输出噪声分量幅度的均方值相同(σ2B)。每个输出节点的全部输出噪声等于传播到该节点的噪声之和,对于长度为N的序列最多有N-1个噪声源的噪声传播至每个输出节点,因此长度为N的序列在第k个DFT值的计算中输出噪声的均方值上限为:
若假设输入序列的实部和虚部是不相关的,对于小数点定在最左位的左边的B位二进制数的幅度密度在
FFT反变换的碟形类似于上述正FFT变换,在此就不再详细分析。 三、二维定点正反FFT的分析 对于M*N二维复序列x(n1,n2)的离散傅立叶正变换及反变换为:
根据上述式子,我们可以得到对二维复序列x(n1,n2)进行正FFT变换、反FFT变换的一个流程如图三。
下面就M*N二维复序列x(n1,n2)经过上述流程变换的误差传播作一分析: 1、正变换的误差分析: (1)行FFT变换的截断误差: 该变换相当于一维长度N序列的FFT,因此在第k2个DFT值的计算中输出噪声的
(2)列FFT变换的截断误差 该变换相当于一维长度M序列的FFT,因此在第k1个DFT值的计算中输出噪
2、反变换的误差分析 (1)列IFFT变换的截断误差 该变换相当于一维长度M序列的IFFT,因此在第n1个IDFT值的计算中输出噪声
(2)行IFFT变换的截断误差 该变换相当于一维长度N序列的IFFT,因此在第 个IDFT值的计算中输出噪声的
此外,由上面一维FFT的分析可知,若假设输入二维 序列的实部和虚部是不相关的,对于小数点定在最左位的左边的B位二进制数,则行的幅度密度在
联合(15)和(16)式得正-反变换后的输出噪声-信号比为:
(19) 四、实验 实验中分别对128*128,256*256,512*512等三幅图像分别进行了二维正、反32位FFT的处理,并得出了处理后的平均信-噪比。数据见表一。 数据分析:实验数据基本上正比与理论数据,而且与理论值有一定的差距,主要在于一个是在计算量化误差分析时并没有考虑到当WrN=+_1或+_j时所做的乘法事实上没有量化误差,再一个就是实验值取的是平均值,因此实验数据验证了理论分析的正确性。
参考文献 【1】 刘树棠,黄建国 译.离散时间信号处理(第二版).西安交通大学出版社. 【2】 孙仲康 编著.快速傅立叶变换及应用(第一版) .人民邮电出版社. 【3】 W.R.Knight and R.Kaiser . A Sample Fixed-Point Error Bound for the Fast Fourier Transform . IEEE Trans.Acoustics , Speech and Signal Proc. . 作者简介: 姜玲(1977-),女(汗族),江苏赣榆人,硕士研究生在读,主要研究方向:图像的实时处理;黄 峰(1955- ),男(汉)1985年毕业于北京大学无线电子学系,获理学硕士学位,现为解放军理工大学教授,发表论文20余篇,主要研究方向:图象处理,数据压缩。
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/68070.html