估计算法（精选11篇）
估计算法 篇1
伴随着通信技术、电子技术和计算机技术的迅速发展,信号处理理论引起学术界的广泛关注,很多学者从不同的角度对信号处理理论进行了丰富和完善,提出了各种新算法、新理论。而SNR(信噪比)算法估计因为其具有的各种优点成为是信号处理领域的一个重要内容。SNR是指接收信号中声音信号和噪声的功率之比,也可看成是最大不失真声音信号强度与噪音强度之间的比率。SNR算法估计利用信号处理和参数估计的理论与方法,对接收信号的功率或能量进行测定和估算,计算有益信号功率和影响该信号的噪声功率之比,SNR值越大说明音频产品的信号处理能力越好。SNR算法估计的功能在于可以提供功率控制、信道分配等所需的信道质量信息,SNR算法估计的众多优点在于可以促进自适应的采用更有效的解调算法提高解调性能,很多其它的算法也需要基于SNR的先验知识来优化性能。
SNR算法估计从20世纪60年代被首次提出以来,经过不断的发展已经成为无线通信领域的一个重要研究领域。一般地,SNR估计是从基带、采样和接收信号数据获得的。整体上SNR估计算法可以分为两类:一类基于数据辅助,称为DA(Data-Aided)算法,对算法的估计依赖于传输数据的先验知识。即在传输过程中周期性地发送已知的序列(导频),接收端比较已知的序列和接收到序列来获取信噪比信息;另一类是无数据辅助的,是通过未知数据和对接收信号进行分析从而得到的SNR估计,即接收端在接收数据的同时对接收到的数据进行盲估计,称为NDA(Non Data-A ided)算法。DA算法的优点在于具有较高的性能,对信道的数据传输效率不会产生额外影响,并且估计精度较NDA方法好,但缺点是占用额外的带宽,通常不被采用。NDA算法主要包括自相关矩阵分解算法、高阶矩估计、ML、平方信噪方差比估计、SVR、EVM、SSME算法等。前面几种算法的缺点是计算量太大,对于主要以FPGA进行接收机设计的状况,单纯依靠矩阵求逆、高次方运算来实现,复杂度高且对资源占用太大;而SSME算法估计对每个符号有较高的过采样率,比较合适在符号率低的情况下应用,缺点是局限于估计AWGN信道中的BPSK信号,在高速率数据传输系统中很难达到这个要求[1,2]。
1 国内外SNR估计算法研究现状
国内对SNR估计技术的研究现对较少,目前采用的主要方法包括信号子空间投影法、子空间特征值分解法等。Huilin Xu,Guo Wei等将ML、MMSE方法应用于OFDM系统,并给出了新的SNR估计方法。另外Hua Jinyu,Hua Han[3]等人给出了基于白噪声条件下的频域SNR估计方法,但是该方法是在假设噪声的频谱是平坦的,在色噪声环境下理论上不可行。胡茂海和杨晓春[4]建立了Kalman滤波算法的理论模型,提出一种基于图像像素的Kalman滤波算法,实现了实时化的Kalman滤波器。实验模拟结果发现该算法能够有效地提高共焦显微镜信噪比,但是以牺牲时间为代价。鲍祥生等人利用江苏油田实际资料的研究结果表明时间域SVD法估算实际信噪比较为可靠。
国外对SNR估计技术的研究相对较多。一般地,SNR估计是从基带、采样及接收信号数据得出的。ML估计理论被提出后,Kerr[5]首先将ML估计理论应用于SNR算法估计。Thomas在分析最大似然估计的概率密度函数基础上,针对实信道的情况,发现该估计存在一定的偏差,建议通过修正因子从而减小估计误差,并给出了修正因子。Pauluzzi和Beaulieu[6]针对复AWGN信道中的高阶调制模式-MPSK信号,把ML估计法应用到其中,给出了修正后的计算公式。理论上SNV估计基于匹配滤波器输出端的采样,并通过修正因子来减少原始算法存在偏差。Pauluzzi和Beaulieu[6]最早提出复信道中的高阶调制BPSK信号的SNV估计,推广了该算法,并设计了修正后的计算公式。Brandao等针对多径衰落信道的信道质量监控问题,提出了SVR估计,SVR估计法是一种基于多阶矩的有效的估计方法。Pauluzzi和Beaulieu[6]则进一步地把SVR估计应用到实信道。1986年,Simon和Mileant提出了SSME估计法,该方法主要是针对AWGN信道中的BPSK信号在宽带AWGN信道中的SNR估计,Shah和Hinedi[7]将SSME估计法应用于带限信道,Shah和Holmes[8]通过改进SSME估计法,将其应用于窄带信道中的性能。Pauluzzi和Beaulieu[6]提出方差方法,该方差方法基于SSME估计法,提高了SSME方法应用于窄带信道中的性能。并分实信道和复信道,在同一模型下应用例证对信噪比估计算法作了详细的比较和讨论。Beualieu[9]等人还针对QPSK信号提出了四种信噪比估计算法,并比较了四种信噪比估计算法的性能。
2 对SNR估计算法的评价
对于SNR估计算法的研究,鉴于性能、度量和测试条件等的不统一,其性能优劣比较,不可一概而论之。“最佳”的供给依赖于观测数据长度、每符号采样率、调制类型以及实际的信噪比范围、复杂度、实时性、和稳健等重要指标。另外,AR过程作为输入的信号SNR估计和色噪声环境下的SNR估计也有待进一步研究。但是SNR作为自适应无线通信中信道质量的主要参数,可以更好地控制通信频率或调制方式切换。另外SNR估计的正确与否直接影响软件无线电的调制识别系统的正确识别率。随着信号处理的快速发展,人们对参数估计的要求也越来越高,提出精度更高、分辨能力更好、稳健性更强、计算更简便的估计方法一直是众多学者不断努力的方向。SNR算法是在PHY层中直接选择一个最佳传输速率,虽然SNR本身是个随机性很大的量,利用起来会比较复杂,但SNR是直接对信道状况的反应,其优点是不存在滞后的问题。整体上研究SNR估计技术仍然有很大的现实意义。
摘要：基于大量相关文献的研究,总结了SNR估计算法研究的国内外现状,阐述了SNR的定义和分类,并评价了SNR估计算法的性能。
关键词：SNR算法,无线通信,信号处理
参考文献
[1]杜瑜.一种基于矩特性的SNR估计方法[J].电讯技术,2008(08):102-104.
[2]彭刚.AWGN信道中的信噪比估计算法[D].南京:南京理工大学,2005.
[3]Hua Jin-yu,Hua Han,Meng Qung-min,et al.A scheme for the SNR estimation and its application in Dcppler shift estimation of mobilecommunication systems[C].Vehicular Technology Conference,2004:24-27.
[4]胡茂海,杨晓春.一种提高共聚焦显微镜信噪比算法的研究[J].应用光学,2010(1):70-72.
[5]Kerr P B.On signal and noise level estimation in a coherent PCM channel[C].IEEE Trans.Aerosp.Electron.Syst.,1966:450-454
[6]Pauluzzi D R,Beaulieu N C.A comparison of SNR estimation techniques for the AWGN channel[J].Communications IEEE Transaction,2000,48(10):1681-1691.
[7]Shah B,Hined S.The split symbol moments SNR estimator in narrow-band channel[C].IEEE Trans.Aerosp.Electron.Syst.,Vol.AES-26:1900.
[8]Shah B,Holmes J K.Improving the Split-Symbol Moments SNR Estimator[C].Jet Propulsion Lab.,Pasadena,CA,Interoffice Memo.3338-90-223.
[9]Beualieu N C,Toms A S,Pauluzzi D R.Comparison of four SNR estimations[J].IEEE Commun Letters,2002,4(2):43-45.
估计算法 篇2
针对洪水演算的马斯京根模型参数估计问题, 首先将其归结为非线性参数优化问题, 然后利用自适应加速差分进化算法进行求解.计算结果表明, 自适应加速差分进化算法具有求解速度快、计算精度高、算法控制参数设置简便、通用性强等优点,与现有马斯京根模型参数估计方法相比, 该算法显示出更好的优化性能, 从而为准确估计马斯京根模型参数提供了一种更为有效的方法.该算法也可以广泛应用于其他各种复杂非线性模型的`优化问题, 特别是在洪水预报方面有很好的应用前景.
作 者：许小健 钟翔熹 XU Xiao-jian ZHONG Xiang-xi 作者单位：许小健,XU Xiao-jian(芜湖市勘察测绘设计研究院,安徽,芜湖,241000)
钟翔熹,ZHONG Xiang-xi(水利部湖南水利水电勘测设计研究院,长沙,410007)
估计算法 篇3
【关键词】H.264；运动估计；模式选择
2003年ITU-T视频编码专家组（VCEG）和ISO/IEC运动图像专家组（MPEG）共同推出了H.264视频编码标准。与此前的H.263等标准相比，具有更高的编码效率和强大的容错处理能力。但是这些性能都是以计算的高度复杂为代价的，严重制约其在实际中的应用。
统计学的结论表明，在通常的视频图象序列中，大部分运动矢量为零矢量或运动很小的矢量。对运动矢量为零的块在这里称其为静止块；运动矢量很小的块称其为准静止块；而其它的块的称为运动块。那么有超过80%的块可被看作静止或准静止块。因此，可设一个阈值T，当运动矢量的值小于T时认为当前块为静止块或者准静止块，可用小交叉型搜索法直接进行精确定位，找出最优点；当运动矢量的值大于T时，认为是运动块，可用大六边形搜索算法找出最优点。由于一个运动物体会覆盖多个分块，所以空间域相邻块的运动矢量具有很强的相关性。同时由于运动物体运动具有连续性，运动矢量在时间域也存在一定的相关性，因此可以用邻近参考帧的运动矢量来预测。运动矢量空间域的预测方式有运动矢量中值预测（Median Prediction）、空间域的上层块模式运动矢量（Uplayer Prediction）两种。运动矢量在时间域的预测方式有前帧对应块运动矢量预测和时间域的邻近参考帧运动矢量预测两种。
为了便于寻找匹配块的运动矢量，减少计算复杂度，在本文中采用的是运动矢量中值预测。根据与当前块E相邻的左边块A，上边块B和右上边块C的运动矢量，取其中值作为当前块的预测运动矢量。把预测运动矢量作为运动估计的初始搜索位置。
设E为当前要编码的块，E的运动矢量为MVP，A的运动矢量为MV1，B的为MV2，C的为MV3，如果运动矢量的值MVP≤T，则认为与E块相邻的各块（子块）间运动的相关性较高，表明该区域的变化比较平缓。如果运动矢量的值MVP>T，则认为与E块相邻的各块间运动的相关性较低，表明该区域变化比较剧烈。
根据预测的运动矢量和相邻块间的运动相关性的不同（阈值T的不同），采用两个不同的模板，分别为小交叉（SCSA Small Cross Search Algorithm）搜索模板和大六边形（LHSP Large Hexagon Search Pattern）搜索模板。SCSA搜索模板以起始搜索点为中心，并由4个周围点组成，如果计算的最小值点为中心点，则停止搜索，中心点即为最终的运动矢量。如果最小值点在边缘上，则以该最小值点为中心，和其相邻的4个周围点进行下一次的搜索计算，直到最小值点为中心点。同时，由于H.264采用的是多种块划分的模式，可以根据块的不同形状和大小采用不同的步长。
搜索步骤如下：
Step1：设定当前块的预测运动矢量和起始搜索点，并判断相邻块间的相关性。
Step2：如果相邻块间的运动相关性较高，预测的运动矢量值较小或为零，则转入Step5。否则，进入Step3。
Step3：利用LHSP模板进行搜索，计算7个点的SAD值，同时利用排除准则进行条件判断。如果最小值MBD为中心点，则转到Step4，否则重复Step3。
Step4：以中心点周围的上、下、左、右四个点组成一个小的菱形，计算5个点的SAD值，同时利用排除准则进行条件判断。SAD值最小的点即为最终的运动矢量。
Step5：利用SCSA模板进行搜索，计算5个点的SAD值，重复点将不再计算，同时利用排除准则进行条件判断。如果最小值MBD为中心点，该点对应的运动矢量即为最终的运动矢量。如果最小值点为边缘点，重复Step5。
这种搜索算法将四边形搜索和六边形搜索结合起来，明显的降低了计算量，加快了编码速度，同时图像质量得到了很好的保存，是一种可行的算法，若在算法中加入类似UMHS算法的早期终止策略，编码效率会进一步提高，这也将是算法进一步完善的主要突破点.而且可以得到本算法与其他算法相比搜索点数明显减少，有效地减少搜索数目，提高编码效率。通过对最小绝对差（MAD）、最小均方误差（MSE）、归一化互相关函数（NCCF）和求和绝对误差（SAD）的计算。这种算法在编码效率上比提高20%。但算法本身也存在不足，比如在有关宏块划分的阈值确定方面，只能依靠经验设定，不一定满足所有视频的特点，当出现极端情况时，码率可能会有很大程度的上升，这也是算法以后需要改进的方向之一。
参考文献
[1]智西湖，智艾娣.H.264编码的运动估计快速搜索算法.计算机应用，2004年4月，第4期：72-74.
[2]朱冬冬，戴琼海.H.264快速帧间编码模式选择算法.电子设计应用，2004年4月，第4期：36-38.
[3]张翔，李锐，江珊，喻占武.H.264标准的码率控制算法研究，武汉大学学报（信息科学版）12期，2004-12-4（6）.
[4]Halbach Till.The H.264 Video Compression Standard.In Proceedings Norwegian Signal Processing Symposium（NORSIG），Bergen（Norway），October 2003.
[5]D.Wu，S.Wu，K.P.Lim，et al.Block Inter Mode Decision for Fast Encoding of H.264.Proc.of IEEE.
MUSIC算法估计性能分析 篇4
智能天线技术是当前无线移动通信领域颇为关注和研究的热点领域之一,他可将无线电的信号导向到具体的方向上,产生空间定向波束,使天线主波束对准用户信号到达方向,旁瓣或零陷对准干扰信号的到达方向,起到充分高效利用移动用户信号并删除或抑制干扰信号的目的。而波束形成的关键是要准确知道信号的到达方向,即波达方向,所以波达角估计(DOA)是波束形成的基础。
本文着重分析了用于DOA估计的典型算法——MUSIC(Multiple Signal Classification)算法,然后对不同的条件下MUSIC算法的性能进行了Matlab的仿真和分析。
2 MUSIC算法
MUSIC方法是Schmidt在1979年首先提出的,并于1986年重新发表。该方法和Roy于1986年提出的Esprit方法都是早期经典的超分辨率DOA估计方法(即超瑞利限的方法),他们同属特征结构的子空间方法。子空间方法建立在这样一个基本观察之上:若传感器个数比信源个数多,则阵列数据的信号分量一定位于一个低秩的子空间。在一定条件下,这个子空间将惟一确定信号的波达方向,并且可以使用数值稳定的奇异值分解精确确定波达方向。由于把线性空间的概念引入到DOA 估计中,子空间方法实现了波达方向估计分辨率的突破。
我们在本文中假设有ULA天线模型——平面等间距线性天线阵列,他的阵列间距为d,阵元数为n。模型如图1所示。
图1中每一个天线阵元产生的方向向量表示如下:
undefined
每个阵元的接收信号可以表示如下:
undefined
其中J是信号源的数目。则对于J个信号源波达方向θ的方向矩阵可以表示为:
undefined
如果将天线上各阵元的第k次快拍采样写成向量形式,就有:
undefined
计算x(k)的协方差矩阵Rxx,并对其进行特征值分解,得到:
undefined
一方面,由于σ2和Un是协方差矩阵R的特征值和对应的特征向量,故有特征方程:
undefined
另一方面,用Un右乘式(6),又有:
undefined
综合上面两个式子可以得到:
undefined
这就说明,矩阵A的各个列向量与噪声空间正交,故有:
undefined
同时他也与阵列输出向量的协方差矩阵信号特征向量组成的子矩阵Us所张成的子空间相同。
于是,可以定义MUSIC的空间谱为:
undefined
当然,空间谱PMUSIC(θ) 并不是任何意义下的真实谱,严格来说,他只是信号方向向量与噪声子空间之间的“距离”。尽管如此,他却能够在真实波达方向的附近出现“谱峰”,超分辨地准确表达各信号的波达方向。
3 MUSIC算法实现
MUSIC算法的实现步骤分为以下5步:
(1) 产生信号模型:x(k)=As(k)+n(k);
(2) 求取x(k)的协方差矩阵Rxx;
(3) 计算Rxx的特征值;
(4) 对特征值矩阵由小到大排序,求出对应的信号子空间;
(5) 形成undefined。
4 MUSIC算法仿真分析
(1) 仿真条件:阵元数为8,阵元间距为0.5波长,3个信号源,入射角度为-45°,0°,45°。
从图2中可以明显地看出图中的图谱明显对应入射角,谱线明显,说明MUSIC算法拥有可靠的准确性。
(2) 仿真条件:阵元数为8,阵元间距为0.6波长,3个信号源,入射角度为-45°,0°,45°。
通过图3可以明显地看出MUSIC算法所估计的图谱已经出现栅瓣,不能正确地反映入射角度,说明阵元间距大于半波长时,MUSIC算法已经不再准确。
(3) 仿真条件:阵元数为8,阵元间距为0.2波长,3个信号源,入射角度为-45°,0°,45°。
通过图4可以看出,当阵元间距小于半波长时,通过MUSIC算法得出的角度估计还是可以正确地反映波达角的,只是准确度有所下降。
(4) 仿真条件:阵元数为4,阵元间距为0.5波长,3个信号源,入射角度为-45°,0°,45°。
图5是在阵元数为4时得到的仿真谱线,从图上可以看出当阵元数下降时,MUSIC算法的准确度也随之下降。如果当阵元数等于信源数时,MUSIC算法所基于的子空间降不存在,他也就不能正确地描述波达角。
(5) 仿真条件:阵元数为8,阵元间距为0.5波长,3个信号源,入射角度为0°,45°,47°。
图6反映出当信源高度相关或入射角过于接近时,MUSIC算法比较难以区分入射角度,仿真图上的谱线已经不对应入射角度。
图7,图8两幅仿真图是不同阵元间距和不同阵元数时的性能曲线图。采用的是MUSIC算法仿真出的图谱的波峰与波谷距离比,入射信号源:-10°,10°。
图7是阵元间距不同时的性能曲线图,阵元间距从0.1个波长开始到0.8个波长结束,间隔0.05个波长取一次值。图8是不同阵元数时的性能曲线图,从3个阵元开始到14个阵元结束,每次递增一个阵元。从两副图中可以看出,当阵元间距小于0.5个波长时,MUSIC算法的DOA估计效果呈现一个增长趋势,但是当他超过0.5的波长以后,估计性能逐步区域平稳。从图8中可以看出,从3个阵元到10个阵元,估计效果有较大的提升,超过10个阵元后,性能曲线趋于平稳。
5 结 语
通过仿真图,可以得到以下4点结论:
(1) MUSIC算法有很高的分辨能力,但他需要十分精确的阵列校准;
(2) MUSIC算法的精确度与阵元间距和阵元数有着密切的关系;
(3) 当入射角过于接近时,传统的MUSIC算法失效;
(4) 当入射信号高度相关时,由于协方差矩阵变成奇异,MUSIC算法将失效。
参考文献
[1]张贤达,保铮.通信信号处理[M].北京:国防工业出版社,2000.
[2]张贤达.现代信号处理[M].北京:清华大学出版社,2002.
[3]郑洪.MUSIC算法与波达方向估计研究[D].成都:四川大学,2005.
[4]张娟.智能天线中DOA估计算法的研究[D].哈尔滨:哈尔滨工业大学,2006.
[5]Hao Ye,DeGroatD.Maxi mum Likelihood DOA Esti mation andAsymptotic Cramer-Rao Bounds for Additive Unknown Col-ored Noise[J].IEEE Transactions on SP,1995,43(4):938-949.
估计算法 篇5
仅用星敏感器的卫星姿态估计UKF算法研究
针对无陀螺或陀螺失效等情况下的卫星姿态确定问题,应用基于Unscented变换的.Unscented滤波理论,提出了仅利用星敏感器矢量观测信息来确定无陀螺卫星姿态的Unscented卡尔曼滤波算法,并进行了数学仿真,仿真结果表明了所提出的UKF算法在无陀螺情况下对卫星姿态估计的有效性和可靠性.
作 者：孙兆伟 李晖 张世杰 SUN Zhao-wei LI Hui ZHANG Shi-jie 作者单位：哈尔滨工业大学,卫星技术研究所,黑龙江,哈尔滨,150080刊 名：飞行力学 ISTIC PKU英文刊名：FLIGHT DYNAMICS年，卷(期)：200624(3)分类号：V448.22关键词：姿态估计 Unscented卡尔曼滤波器 星敏感器
估计算法 篇6
关键词： 线性阵列； 非圆信号； MUSIC； DOA估计
中图分类号： TN911.7文献标识码： A文章编号： 1673-5048（2016）04-0036-06
Abstract： Direction of arrival （DOA） estimation for noncircular （NC） signals has been widely studied and used in communications. Considering the high computational complexity of NC multiple signal classification （MUSIC） algorithm， reduceddimension NCMUSIC algorithm is proposed for DOA estimation of NC signals. Compared with conventional 2DNCMUSIC algorithm which needs twodimension search， the proposed algorithm only requires onedimension search， which reduces the computational complexity. Simulation results illustrate that the proposed algorithm outperforms the conventional MUSIC algorithm and has close estimation performance to the 2DNCMUSIC algorithm.
Key words： linear array； NC signal； MUSIC； DOA estimation
0引言
在阵列信号处理中， DOA估计是一个主要的研究方向， 已广泛应用于通信、 雷达、 声纳和医学图像等领域[1-4]。 传统的DOA估计算法包括MUSIC算法[5] 、 ESPRIT算法[6-8] 、 Capon算法[9-10]及PM算法[11]等， 均已经有了较为成熟的理论， 但估计性能却越来越难以满足要求。 为了提高估计性能， 开始利用信号的非圆特征估计信号的DOA[12-19]。 非圆信号是指在星座图中振幅只有同相分量而正交分量为零的信号， 诸如二进制相移键控（Binary Phase Shift Keying， BPSK）和调幅（Amplitude Modulation， AM）信号等 [20]。 当信源发出非圆信号时， 利用非圆特性， 可以有效地将接收的数据矩阵维数加倍， 从而在提高参数估计性能的同时还能估计出更多的信号源。 因此， 非圆信号的非圆特性已被广泛用于提高DOA估计性能。 文献[12]提出一种非圆MUSIC算法实现DOA估计（NC-MUSIC）。 文献[13]提出非圆信号求根MUSIC算法（Root-NC-MUSIC）， 避免了谱峰搜索。 文献[14]提出一种用ESPRIT实现非圆信号的定位算法， 该算法（NC-ESPRIT）无需谱峰搜索， 复杂度较低。 文献[17]则对非圆信号DOA估计提出一种非圆PM算法， 该算法（NC-PM）比传统的PM算法[12]有着更好的性能。
上述算法的计算复杂度均较高， 尤其是文献[12]提出的2D-NC-MUSIC算法， 需要对DOA和非圆相位进行二维搜索， 计算复杂度较高， 难以应用到实际中。
因此， 为了降低计算复杂度， 在文献[21]面阵降维MUSIC算法的启发下， 结合2D-NC-MUSIC算法二维搜索的特征， 提出了降维NC-MUSIC算法。 仿真结果证明了降维NC-MUSIC算法的有效性。
本文其余部分的结构如下： 第2节介绍了信号的数据模型； 第3节提出了降维NC-MUSIC算法； 第4节对算法进行性能分析； 在第5节中， 仿真结果证明了算法的有效性； 第6节为本文的总结。
1数据模型
一个有M个阵元的线性阵列如图1所示。
降维NC-MUSIC算法的主要步骤如下：
（1） 通过式（4）扩展信号矩阵；
（2） 通过式（28）构造扩展信号的协方差矩阵R^， 并对R^进行特征分解得到噪声子空间U^N， 计算复杂度为O（4M2L+8M3）；
（3） 通过式（29）进行谱峰搜索， 估计信号的DOA， 计算复杂度为O（8M3-4M2K+8（M2+M）n）。
3性能分析
3.1复杂度分析
本文提出的降维NC-MUSIC算法的计算复杂度为O（4M2L+16M3-4M2K+8（M2+M）n）， 而2D-NC-MUSIC算法的计算复杂度为O（4M2L+16M3-4M2K+（4M2+2M）n2）， 其中n为搜索次数。 因此， 降维NC-MUSIC算法比2D-NC-MUSIC算法的计算复杂度低。
在K=3， n=6 000， M=8的情况下， 两种算法的复杂度比较如图2所示。 可以看出， 降维NC-MUSIC算法复杂度较低。
3.2主要优点
本文提出的降维NC-MUSIC算法有如下优点：
（1） 与传统的MUSIC算法相比， 降维NC-MUSIC算法有较好的估计性能， 同时能够估计更多的信号；
（2） 与2D-NC-MUSIC算法相比， 降维NC-MUSIC算法计算复杂度更低；
（3） 与2D-NC-MUSIC算法相比， 降维NC-MUSIC算法拥有相似的估计性能；
（4） 降维NC-MUSIC算法不需要估计非圆相位， 就能很好地估计DOA。
上述讨论中， 假设非圆信号个数K已知。 假设在K未知的情况下， 也能通过信息论中的算法、 矩阵分解算法、 平滑排位算法或者盖氏圆盘算法估计信号个数K[24-27]。
4仿真结果
通过仿真来评估降维NC-MUSIC算法的角度估计性能。
5结论
本文提出了降维NC-MUSIC算法估计非圆信号的DOA。 与传统的MUSIC算法相比， 该算法拥有更好的估计性能， 且能够估计更多的信号。 与2D-NC-MUSIC算法相比， 该算法只需要一维搜索， 在保持估计性能的同时， 有着较低的计算复杂度。 仿真结果证明了算法的有效性。
参考文献：
[1] Krim H， Viberg M. Two Decades of Array Signal Processing Research： The Parametric Approach[J]. IEEE Signal Processing Magazine， 1996， 13（4）： 67-94.
[2] Applebaum S R. Adaptive Arrays[J].IEEE Transactions on Antennas and Propagation， 1976， 24（5）： 585-598.
[3] Li Jianfeng， Zhang Xiaofei. ClosedForm Blind 2DDOD and 2DDOA Estimation for MIMO Radar with Arbitrary Arrays[J]. Wireless Personal Communications， 2013， 69（1）： 175-186.
[4] Bekkerman I， Tabrikian J.Target Detection and Localization Using MIMO Radars and Sonars[J].IEEE Transactions on Signal Processing， 2006， 54（10）： 3873-3883.
[5] Schmidt R O. Multiple Emitter Location and Signal Parameter Estimation[J].IEEE Transactions on Antennas and Propagation， 1986， 34（3）： 276-280.
[6] Zheng Guimei， Chen Baixiao， Yang Minglei. Unitary ESPRIT Algorithm for Bistatic MIMO Radar [J]. Electronics Letters， 2012， 48（3）： 179-181.
[7] Bencheikh M L， Wang Y. Joint DODDOA Estimation Using Combined ESPRITMUSIC Approach in MIMO Radar [J]. Electronics Letters， 2010， 46（15）： 1081-1083.
[8] Zoltowski M D， Haardt M， Mathews C P. ClosedForm 2D Angle Estimation with Rectangular Arrays in Element Space or Beamspace via Unitary ESPRIT [J]. IEEE Transactions on Signal Processing， 1996， 44（1）： 326-328.
[9] 张保锋. 几种DOA估计算法的性能分析[J]. 现代电子技术， 2003（9）： 35-37.
[10] Stoica P， Hndel P， Sderstrm T. Study of Capon Method for Array Signal Processing[J]. Circuits， Systems and Signal Processing， 1995， 14（6）： 749-770.
[11] Marcos S， Marsal A， Benidir M. The Propagator Method for Source Bearing Estimation[J].Signal Processing， 1995， 42（2）： 121-138.
[12] Abeida H， Delmas J P. MUSICLike Estimation of Direction of Arrival for Noncircular Sources[J].IEEE Transactions on Signal Processing， 2006， 54（7）： 2678-2690.
[13] Chargé P， Wang Y D， Saillard J. A Noncircular Sources Direction Finding Method Using Polynomial Rooting[J].Signal Processing， 2001， 81（8）： 1765-1770.
[14] Zoubir A， Chargé P， Wang Yide. Non Circular Sources Localization with ESPRIT[C]∥Proceedings of European Conference on Wireless Technology， Munich， Germany， 2003.
[15] Steinwandt J， Roemer F， Haardt M. Performance Analysis of ESPRITType Algorithms for NonCircular Sources[C]∥International Conference on Acoustics， Speech， and Signal Processing， Vancouver， BC， 2013.
[16] Haardt M， Rmer F. Enhancements of Unitary ESPRIT for NonCircular Sources[C]∥Proceedings of 29th IEEE International Conference on Acoustics， Speech， and Signal Processing， Montreal， Quebec， Canada， 2004.
[17] 孙心宇， 周建江. 非圆传播算子DOA估计算法[J]. 数据采集与处理， 2013， 28（3）： 313-318.
[18] Zhang Xiaofei， Cao Renzheng， Zhou Ming. NoncircularPARAFAC for 2DDOA Estimation of Noncircular Signals in Arbitrarily Spaced Acoustic VectorSensor Array Subjected to Unknown Locations[J]. EURASIP Journal on Advances in Signal Processing， 2013（1）： 1-10.
[19] Liu J， Huang Z T， Zhou Y Y. Azimuth and Elevation Estimation for Noncircular Signals[J]. Electronic Letters， 2007， 43（20）： 1117-1119.
[20] Delmas J P， Abeida H. CramerRao Bounds of DOA Estimates for BPSK and QPSK Modulated Signals[J]. IEEE Transactions on Signal Processing， 2006， 54（1）： 117-126.
[21] Zhang Xiaofei， Xu Lingyun， Xu Lei， et al. Direction of Departure （DOD） and Direction of Arrival （DOA） Estimation in MIMO Radar with ReducedDimension MUSIC[J]. IEEE Communications Letters， 2010， 14（12）： 1161-1163.
[22] 张小飞，汪飞，陈华伟. 阵列信号处理的理论与应用[M].北京： 国防工业出版社， 2013.
[23] Zhong Manli， Fan Zheyi. DirectionofArrival Estimation for Noncircular Signals[C]∥Proceedings of the International Conference on Computer Networks & Communication Engineering， 2013， 30： 634-637.
[24] Wax M， Kailath T. Detection of the Signals by Information Theoretic Criteria[J]. IEEE Transactions on Acoustics， Speech， and Signal Processing， 1985， 33（2）： 387-392.
[25] Di Angzhao. Multiple Sources Location——A Matrix Decomposition Approach[J]. IEEE Transactions on Acoustics， Speech， and Signal Processing， 1985， 35（4）： 1086-1091.
[26] Huang Lei， Long Teng， Mao Erke， et al. MMSEBased MDL Method for Robust Estimation of Number of Sources without Eigendecomposition[J].IEEE Transactions on Signal Processing， 2009， 57（10）： 4135-4142.
[27] Wu H T， Yang J F， Chen F K. Source Number Estimator Using Gerschgorin Disks[C]∥Proceedings of ICASSP， Adelaide， Australia， 1994.
采用BCZT的时延估计算法 篇7
定义式为:
频谱的细化程度是由N1决定的, K1是所要计算的起始频谱, M是所要计算频谱的点数, N0是信号点数。
1 BCZT算法
由于在很多实际系统中, 时延量总是处于有限范围内, 并且能够确定最大时延值, 相关函数的主峰处在零点附近, 因此, 只要根据最大时延量Tmax和时延分辨率△t′确定N=Tmax/△t′, 对于N2点的r (n) , 只需计算零点的前N点与后N点, 组合成新的满足系统要求的相关函数r2n (n) , 可以大大降低计算量, 新的相关函数表示如下:
其中R2 (k) =R1﹡ (2K1+M-1-k) 是R1 (k) 的共轭翻转后得到。
同样令rn2=D (n) +E (n)
令k′=k- (N2+1-2K1-M) 则可得
由以上分析可知, 此方法使相关函数的分辨率提高N2/N1倍, 可以根据实际需要计算相应的时延点数, 大大减少计算量。
2 BCZT算法仿真
假设输入的窄带信号中心频率为1.44MHz, SNR=5dB, 理论时延值为1e-007s, 色噪声叠加到窄带信号上, 进行10次仿真, 图1为利用BCZT算法计算的相关系数图, 图2为利用BCZT算法计算的时延估值。
由仿真图可以看出, 当输入信号频率较高时, 采用BCZT算法对信号频谱进行细化, 可以提高时延估计精度。
3 结语
实现运动估计算法的优化技术 篇8
运动估计算法软件实现的一个关键问题是运算复杂度和压缩性能之间的权衡。即使使用快速搜索算法,运动估计仍然是软件视频编解码器中计算最复杂、最耗时的操作,其执行速度根本性地决定了整个编码器的实时性能。针对H.263编码器,讨论软件实现提高运动估计算法效率的优化技术,通过实验验证新思想的有效性。
1 运动估计优化技术
1.1 残差块预先判零技术
视频图像相关性较大,补偿后的残差很小,大量的块在DCT和量化处理后成为全零块。通常的编码方案,对于全零块的判断是在DCT和量化后统计完成的。若能提供一个判决准则在DCT运算之前就进行全零块的判断,就能省去对其的DCT、量化、反量化和反DCT等处理操作,大幅度提高编码器的效率[1]。
经典的预先判零方案是在运动搜索之后、DCT之前进行的,并没有考虑如何利用全零块提前检测和运动搜索的结合来提高运动搜索的效率。文献[2]提出的基于全零块发现的运动搜索算法把预先判零技术和运动搜索相结合,从而在节省DCT和量化模块时间的同时,进一步提高了运动搜索模块的效率和速度。
1.2 基于SAD阈值的提前结束搜索
通过研究大量的弱活动性视频序列的运动搜索结果,可以发现视频序列很平滑,变化缓慢,最佳匹配块的运动矢量大都基于当前块的中心位置分布,50%的块运动矢量为零,高达80%的块运动矢量小于4,另一方面,在不同应用环境中,对视频质量和压缩速度的要求是不同的。对于视频质量要求不高而实时性高的应用场合,可以牺牲运动估计的精度来换取搜索速度的提高,即在搜索最优匹配点的过程中,若当前匹配块的失真度满足一定的门限,可以提前结束搜索,将当前匹配块作为最优匹配块。
对于以SAD作为匹配准则的运动搜索,SAD值反映了当前匹配块的匹配程度,当SAD<TH(TH为设定的门限)时,可以认为当前块为静止块或当前搜索块已满足匹配精度,可以作为最优匹配块,本文称此方法为基于SAD阈值的提前结束搜索算法。采用基于SAD阈值的提前结束搜索算法后,大量静止宏块的运动搜索只需进行一个匹配点的运算,而在非静止块的运动搜索中根据匹配块的失真度情况提前结束搜索,也能减少搜索点数,提高编码速度。
1.3 非匹配块的提前判定
基于预判零技术和基于SAD阈值的提前结束运动搜索算法都是对匹配宏块的一种提前判定,即当判定某搜索点满足匹配条件时,则停止对本宏块的匹配搜索运算而开始下一宏块的运动估计。而如果能够在运动搜索中提前判定当前搜索点对应的块为非匹配块,就可以跳过该搜索点后续的误差累计运算,加快搜索速度[3]。利用该思想提出基于MBD点的SAD值比较非匹配块的提前判定算法。
运动估计中广泛使用的SAD匹配准则是通过累加待编码块和待匹配块像素值之差的绝对值得到的,并把得到的和作为这两个数据块相关性的量度。对于H.263标准所定义的16×16宏块,计算一个搜索点的SAD值需要256次的加法和256次的求绝对值运算。可见,在运动搜索的过程中,对每个搜索点的匹配运算都需要相当大的运算量。然而,运动搜索目的是找到一个与当前宏块相关性最强的预测宏块,并不需要计算它与每个宏块的相关系数。在当前搜索点的SAD值的累加运算过程中,若判断此时的SAD值已大于前面搜索过的最小块误差(MBD)点的SAD值,则断定此点不是寻求的全局MBD点,即其所对应的块不是全局最优匹配块,停止本点的SAD值的后续计算而转向搜索窗中下一个搜索点的匹配计算,从而减少运动搜索的运算量,提高搜索效率。
1.4 重复搜索点的识别
基于模板的块匹配中,可能要多次重复使用模板,而模板在移动过程中必然会有重复点,若不在算法实现时加以识别,必然会造成不必要的重复搜索,增加搜索的时间复杂度。由块匹配运动估计的原理可知,当对一个16×16宏块进行匹配搜索时,一个搜索点的重复就意味着增加256次的加法和256次的求绝对值运算,造成大量的计算浪费。因此,提出一种简洁高效的位标识方法来避免搜索点的重复。取N×N(N≤32)的运动估计搜索窗,将搜索窗内的N×N个点都一一标识,在搜索某一点时查看它的标识,若标识无效,表示该点已搜索过,跳过此点;否则对此点进行搜索运算,并在匹配结束后将其标识置为无效。那么,如何标识搜索窗内的各点是一个关键问题。简单的想法是定义一个N×N的二维数组,将矩阵的元素与搜索窗内各点一一对应。但是这样每个数组元素只有0,1两种值,造成了一定的存储空间的浪费。因此,可以考虑定义一个无符号整数一维数组(unsigned int Flag[N]),每个数组元素依次对应搜索窗的1行,元素的每位数字依次对应搜索窗内该行的N个点。这种方法节省存储空间,对标识的置位与查询都是基于CPU的逻辑运算,所以快速而准确。
1.5 搜索模板中各点的搜索顺序优化
由于使用了一系列的提前结束搜索技术,搜索模板内的各点的搜索顺序同样影响搜索匹配的时间。根据运动矢量的分布规律合理地安排模板内各点的搜索顺序是很有必要的。分析发现,视频序列图像的运动矢量在时间、空间上具有中心倾向分布特性、运动相关性和SAD值的方向性。现有的一些经典运动估计搜索模板较好地利用了上述运动矢量分布特性,性能良好。但它们都认为运动矢量均匀分布于搜索中心的各个方向。
针对不同运动速度和背景的18个不同类型标准测试序列在15×15搜索窗范围的实验统计数据证明除(0,0)矢量之外运动矢量分布的非均匀性:水平方向概率最大,垂直方向其次,对角方向概率较小,称之为运动矢量分布方向性中心偏移特性。根据此特性,设置搜索模板内各点的搜索顺序,一般先搜索水平方向上的点,然后是垂直方向上的点,最后搜索对角方向上的点,当然对于一些特殊的序列,如垂直运动较多的Tennis序列,可以考虑先搜索垂直方向上的点。
2 源代码优化
优化代码和提高速度实际上是一对矛盾,一般地,适度代码优化能够提高执行速度,而过度优化可能会引起代码长度的膨胀,不但会造成运行速度的下降,还会增加编程工作量,从而有悖于优化的初衷。在代码优化过程中,必须掌握适度原则,寻找一个平衡点,力争以最小的代价换取最大的性能。
2.1 计算SAD的代码部分优化
由块匹配运动估计的原理可知,当对一个16×16宏块进行匹配搜索时,一个搜索点就意味着进行256次的加法和256次的求绝对值运算。要加快运动搜索速度,一方面可以在保持精度的前提下尽可能的减少搜索点数,另一方面考虑加快单个搜索点的处理时间。从软件编程的角度考虑,可以对计算SAD的这部分代码进行优化,尽可能提高CPU的利用率。
2.2 数据方面的优化
在数据方面的优化主要从以下几个方面进行:
(1) 数据结构的优化。
合理安排数据结构,减少不必要的数组定义和空间分配,应该尽量减少在函数内部定义临时数组。在数据类型上,应尽量使用短数据类型和整型类型,避免浮点类型。浮点数据运算时,可以以有限的误差作为代价;采用整型的数据格式进行处理时则采用整数运算,换取更快的运算速度。
(2) 数据的初始化。
在运动估计过程中,数据的初始化和复位是必须要进行的工作,虽然其占据的运行时间不会太长,但在运动估计过程中还是占据了一定的开销。对这一问题的解决方法,一是在申请空间时,尽量减少申请的次数,对于可以重复使用的地址空间,只需要申请1次重复利用;二是避免零散的内存分配,对于数据的读/写以及内存的分配是十分耗时的,所以尽可能给一个变量分配一个连续区域的内存;三是同时拷贝一块数据,而不是利用循环对每一个数据进行赋值,从而加快初始化或数据复位的速度。
(3) 数据存取。
对文件的访问是影响程序运行速度的一大因素,提高其速度的主要办法是采用内存缓冲。在数据读/写时,利用了缓冲,每一次尽可能多地将数据读入缓存区内以便数据运用,或等到缓冲区中的数据存入足够多时将数据一次性写入文件,这样可减少读写文件的次数,从而加快整个软件的运行速度。此外,数据的读取以一定长度如4个字节为单位、而不是以位为单位读取,然后通过移位的方法,得到需要的数据段。
2.3 其他方面的优化[4]
(1) 循环分支优化。首先,尽可能减少循环的出现;其次,尽可能减少循环语句的嵌套,在平衡了循环次数和代码长度后,将循环内部操作适当展开;第三,当相邻两个循环相关,且循环的次数也有一定的关联,可利用循环操作的并行性;第四,当条件分支与循环分支嵌套时,尽量将条件分支移出循环分支。
(2) 函数使用优化。由于函数的调用是一个跳转的过程,不仅要传递参数,还要保护现场,所以减少函数之间的相互调用以及传递参数也是必要的。对于一些操作简单、调用次数不多的函数,可将被调用到的函数体直接放到主调函数中,或用宏定义表示,或用内联函数;减少函数的传递参数,将运算的最后结果作为函数的返回值直接赋值。
(3) 用指针优化数组的寻址,特别是多维数组及连续访问数组中的元素时。
(4) 利用累加器,减少加法器使用,即多使用自加、自减指令和复合赋值表达式,生成高质量程序代码。
3 优化方案性能测试
为测试上述优化方案的性能,进行了优化前和采用上述优化方案后的DS算法性能的实验[5,6],统计了优化前后的运动估计整像素和半像素搜索点数、恢复图形的PSNR、平均每帧的编码码长和平均每帧的编码时间。表1给出了实验统计结果。从表1的实验结果可以看出,采用上述优化方案后,H.263编码器的恢复图像的PSNR稍有下降,但整像素和半像素搜索点数均有较大的减少,平均每帧的压缩时间大大缩短,而且平均每帧的编码码长也有不同程度的缩短。实验结果验证了上述一系列的运动估计算法软件实现优化方案的有效性。
4 结 语
运动估计作为软件视频编解码器中计算最复杂、最耗时的模块,其软件实现的效率决定着整个编解码器的性能。这里针对H.263编码器,研究了软件实现时提高运动估计算法效率的一些优化技术,详细总结了基于残差块预判零技术和SAD阈值的提前结束运动搜索方案,以及基于MBD点的SAD值比较的非匹配块的提前判定方法,给出了一种基于位标识的重复搜索点的识别方法,提出了根据运动矢量各向非均匀分布特性设置模板搜索点顺序的思想。各项实验结果验证了上述优化方案的有效性。
参考文献
[1]周漩,谭径微,余松煌.H.263中预先判别全零系数的新方法[J].上海交通大学学报,1998,32(9):107-109.
[2]兰军强,何芸,曹志刚.H.263中基于全零块发现的运动搜索方法[J].中国图像图形学报,2000,5(11):925-927.
[3]Iain E.G.Richardson.视频编解码器设计:开发图像与视频压缩系统[M].欧阳合,韩军,译.长沙:国防科技大学出版社,2005.
[4]徐丽琨,黄登山.基于H.263标准的视频压缩算法的优化及研发[J].电力系统通信,2005,26(153):31-34.
[5]魏星,蒋建国,齐美彬.基于选择预测的自适应运动估计算法[J].中国图像图形学报,2005,10(7):873-877.
[6]丁贵广,计文平,郭宝龙,等.Visual C++6.0数字图像编码[M].北京:机械工业出版社,2004.
[7]OH H S,LEE H K..Block-matching algorithm based onan adaptive reduction of the search area for motion estima-tion[J].Real-Time Imaging,2000,6(5):407-414
[8]徐丽琨,黄登山.基于H.263视频压缩的新钻石搜索算法[J].微计算机应用,2005,26(5):516-520.
[9]贾洪骏.视频编码中基于模板块匹配的运动估计快速算法研究[D].北京:清华大学,2004.
一种相干目标角度快速估计算法 篇9
传统的DOA估计算法有很多,如最大似然法、子空间拟合法、MUSIC法,ESPRIT法,其中MUSIC法和ESPRIT法已经成为DOA估计中经典的方法。ESPRIT算法的计算复杂度远小于MUSIC算法,因此ESPRIT更实用。但是,常规的ESPRIT算法需要得到信号子空间,必须进行矩阵的分解,在有相干信源时,还需要额外的算法,才能估计波达方向。
多级维纳滤波器[2]是Goldstein等人提出的一种有效的降维技术。与主分量法(PC)[3]和互谱法(CS)[4]等降维技术相比,多级维纳滤波器具有很多优点,如允许MSWF的级数远远小于信源数,可以应用在小样本支撑的信号环境中,收敛速度快,能够对时变信号进行快速跟踪,不用对协方差矩阵作特征值分解,使得其运算量大大降低,因而引起了学者浓厚的研究兴趣并得到广泛应用[5,6,7,8]。
在进行信号阵列处理时,必须要解决相干信号角度的估计问题。最初的办法是通过空间平滑来达到解相干的目的,但是此类算法降低了系统自由度且计算量较大。目前针对相干信号源的非降维类处理算法有很多[9,10]。文献[9]、[10]通过构建Toeplitz矩阵,实现了DOA估计,提高了估计性能,不损失阵列孔径。但这类算法计算量仍较大,主要是因为特征值分解。
本文为了实时估计相干信源的波达方向,提出了一种新算法,将多级维纳滤波器引入ESPRIT算法的预处理,通过构造Toeplitz矩阵,得到信号子空间,并结合ESPRIT算法得到波达方向。该算法计算复杂度低,能快速估计信号的DOA,具有一般性。
1 信号模型
如图1所示,假设有个窄带信号(P<L),为远场点目标,入射角度为θi(i=1,2,L P),波长为λ。均匀线阵阵元间距为d,阵元个数为L。则阵列接收矢量可以表示为
x(t)、S(t)、n(t)、A分别为阵列输出矢量、入射信号矢量、阵列噪声矢量和阵列流型矢量,假设n(t)服从零均值,方差为σ2的复高斯白噪声。且有
2 DOA估计算法
2.1 预处理结构
首先要构造维纳滤波器的预处理结构,本文构造的Toeplitz矩阵,与一般的估计协方差矩阵所用的计算量相同,没有增加多余的运算量,并且构造的Toeplitz矩阵的秩等于信号源个数,不存在秩亏损情况,能够起到解相干的目的,再把构造的Toeplitz矩阵作为多级维纳滤波器的预处理部分。
文献[10]证明,利用接收数据构造的Toeplitz矩阵的秩等于信号源个数,不再受信号相干性的影响,仅和入射信号的个数有关。构造的Toeplitz矩阵如下:
2.2 求信号子空间
1)子空间的估计算法。
多级维纳滤波求解信号子空间的主要原理是:对观测数据进行正交空间投影,一个子空间是通过参考信号di(k)与观测信号Xi(k)的互相关向量得到的称为信号相关空间,另一子空间正交于这个子空间。然后把观测数据投影到信号相关空间得到新的参考信号,投影到另一子空间得到新的观测数据,然后按照上述方法继续投影。互相关向量只能提取di(k)和Xi(k)相关的信号分量,由于信号是相关的,而噪声则是无关的,因此互相关向量只提取了信号分量rX0d0,噪声分量对互相关向量是没有贡献的。因此,通过不断的投影,信号分量将被全部提取,di(k)和Xi(k)只包含噪声,达到把信号和噪声分离的目的。
多级维纳滤波器,只需要各级数据Xi(k)和di(k)参考信号估计互相关向量rX0d0,并且只有标量求逆(倒数)运算,因此多级维纳滤波器的计算量较小,特别是对大型阵、协方差矩阵求逆计算量较大时,多级维纳滤波器可有效降低计算量。另外,MSWF很容易应用降秩处理,将多级维纳滤波器在r级分解处截断,得到降秩MSWF。
具体步骤如下:
2)信号子空间的估计。
1:确定信号子空间估计所需的滤波器级数。
根据信噪比的高低调节多级维纳滤波器的级数,通过如下语句可以判断:
2.3 DOA估计
2.4 算法步骤
步骤1:根据式(13)构造Toeplitz矩阵;
步骤2:将2.2节初始化中公式的矩阵代替为步骤1中构造的Toeplitz矩阵,再通过余下过程得到信号子空间;
步骤3:根据2.3DOA估计方法,通过ESPRIT算法得到信源的波达方向。
2.5 算法的计算量分析
下面对本文算法(方法1)、文献[10](方法2)进行分析和比较。
方法1的计算量:①通过数据估计协方差矩阵的计算量为NL2②从3.2节的求解过程中可以看出多级维纳滤波器一次前向递推所需的计算量为2L2+2L,共有P次前向递推,因此,所需的计算量为NL2+(2L2+2L)P。
方法2的计算量:①通过数据估计协方差矩阵的计算量为NL2;②对得到的协方差矩阵作对称QR迭代计算得到三对角阵[11],其计算量为8L3/3;③对三对角阵做Givens旋转得到对角阵,计算量为3L3+L3-4L;④将对称QR迭代所得到的变换矩阵和旋转矩阵相乘,以得到特征向量矩阵,其计算量为L3。由此可知,基于协方差矩阵特征分解估计噪声子空间所需的计算量为NL2+20L3/3+L2-4L。
3 实验仿真
从图2、图3、图4中可以看出,不论对于不相干,全相干还是部分相干信号,本文算法都能估计出正确的角度,证明了本文算法的有效性。本文算法通过构造Toeplitz矩阵达到解相干的目的,不需要额外操作,且直接利用MSWF得到子空间,避免计算量较大的矩阵分解过程,在保证算法性能的前提下,极大的降低了算法计算量。
实验2本文算法、文献[10]算法及空间平滑算法估计结果及性能比较
三个波长为λ的信号的全相干信号,入射角度为-45°,-30°,60°,阵列个数L=8,信噪比从0d B变化到25d B,M=100,比较三种算法的RMSE,仿真结果如图5。
由图5可以看出,本文算法与文献[10]算法的RMSE相当,低于空间平滑算法。说明本文算法在运算量较低时能达到与文献[10]相同的性能。本文算法与文献[10]算法的性能都高于空间平滑算法,这是因为空间平滑算法在解相干时,会造成孔径亏损,而本文算法与文献[10]算法通过构造Toeplitz矩阵达到解相干的目的,没有造成孔径损失,算法的性能较好。
实验3两种算法的计算量的比较
设快拍数为N=256,阵元数L在8至25之间改变,P=3,仿真结果如图6。
从图6可以看出,随着阵元数的增大,本文算法的运算量会远远小于文献[10]算法的运算量,因为本文算法不需要矩阵分解,计算量较低,特别是适用于高纬度矩阵,因此适合于大阵列天线。
4 总结
本文针对均匀线阵估计相干信源实时性问题,提出了一种基于多级维纳滤波器的相干信源估计算法。首先,通过构造Toeplitz矩阵作为去相干结构,达到了解相干的目的。将多级维纳滤波器引入ESPRIT算法的预处理中,多级维纳滤波器是一种有效的降维算法,可以得到信号子空间,避免了协方差矩阵的分解。本文提出的算法,不通过特征值分解,能够实时估计相干信源,且本文算法,适合于基于子空间方法的一大类DOA估计。
参考文献
[1]Puska H,Saarn Isaarih Inattij.Serial Search Code Acquisition Using an Art Antennas with Single Correlator or Matched Filter[J].IEEE Transations on Communication(S0090-6778),2008,56(2):299-307.
[2]Schmidt R O.Multiple emitter location and single parameter estimation[J].IEEE Trans AP,1986,34(3):276-280.
[3]Goldstein J S,Reed I S,Scharf L L.A multistage representation of the wiener filter based on orthogonal projections[J].IEEE Transactions on Information Theory,1998,44(7):2943-2959.
[4]Hotelling H.Analysis of a complex of statistical variables into principal components[J].J.Educ.Psychol.,1933,24:417-441,498-520.
[5]Goldstein J S,Reed I S.Reduced rank adaptive filtering[J].IEEE Trans.Signal Processing,1997,45:492-496.
[6]包志强.快速稳健的参数估计及波束形成技术研究[D].西安电子科技大学,2006.
[7]于红旗,黄知涛,周一宇,等.一种不需要特征值分解的MUSIC方法[J].国防科技大学学报,2007,29(4),91-94.
[8]黄磊.快速子空间估计方法研究及其在阵列信号处理中的应用[D].西安:西安电子科技大学,2005.
[9]梁浩,李小波,王磊.采用单次快拍数实现信源DOA估计[J].数据采集与处理,2013,28(1),58-63.
[10]唐玲,宋宏,陈明举,等.基于Teoplitz矩阵重构的相干信源DOA估计算法[J].航天电子对抗,2010,26(4):15-17.
视频压缩中运动估计算法的研究 篇10
近年来,多媒体技术的飞速发展,在众多应用领域,对视频图像的实时压缩提出了更高的要求,快速、高效的压缩算法是解决这一问题的关键。
运动估计是视频压缩编码系统中非常重要的模块,它直接影响到视频数据压缩编码的效率和编码质量。运动估计越准确,编码的效率就越高,解码出来的视频质量就越好。同时,运动估计的计算复杂度在整个视频数据压缩编码系统中最大,占整个系统计算量的50%以上。因此,运动估计性能的好坏不仅很大程度上决定了视频图像压缩编码的质量,还根本性地决定了整个视频压缩编码系统的实时性能。
研究高效的运动估计算法对提高视频数据压缩编码的效率有着非常重要的实际意义,是解决目前视频数据中高效压缩问题的有效途径。因此,运动估计作为实现视频压缩的核心技术,一直是视频压缩领域的研究热点。
1 MVFAST算法
Hosur和Kai-Kuang Ma等人在1999年提出了动矢量场自适应搜索算法(motion vector field adaptive search technology,MVFAST)[1]。在2000年3月的MPEG Noordwijkerhout会议上,MVFAST作为运动估计的核心算法被纳入MPEG-4新增的第7部分。
1.1 算法基本思想
MVFAST算法的基本思想是以视频运动的时空相关性为基础,首先通过搜索起始点的预测使当前块的初始运动矢量有可能接近最终运动矢量;其次通过简单有效的视频分类和合适的搜索模式,使其能根据视频运动的类型进行自适应的搜索;最后采用高效的搜索中止准则以保证搜索结果在这个预测的起点附近结束时具有足够的精度,从而实现快速且精度高的运动矢量搜索。
1.2 基本方法
大菱形搜索模式的方法如下:
Step 1:按照图1(a)的点位近9点搜索,如果中心点的SAD值最小,则转到Step 3,否则转到Step 2。
Step 2:将搜索中心移到在上次搜索中得到的最小SAD值对应的点位上,再进行1次大菱形搜索,如果中心点的SAD值最小,则转到Step 3;否则,重复执行Step 2。
Step 3:将大菱形搜索模式转换为小菱形搜索模式,并将搜索中心移到在上次搜索中得到的最小SAD值对应的点位上,只进行1次小菱形搜索,将得到的最小SAD值对应的点位设置为最终的运动矢量值。
小菱形搜索模式的方法如下:
Step 1:按照图1(b)的点位进行5点搜索,如果中心点的SAD值最小,则中心点对应的位置就是最后的运动矢量值,否则转到Step 2。
Step 2:将搜索中心移到在上次搜索中得到的最小SAD值对应的点位上,再进行1次小菱形搜索,如果中心点的SAD值最小,则选择中心点的位置为最终的运动矢量;否则,重复执行Step 2。
MVFAST算法考虑几个相邻块的运动矢量确定菱形搜索的起始点,并根据宏块的不同运动强度自适应地选择大小模板来进行匹配搜索,在图像质量和速度上都表现出了好的性能,而且不需要辅助内存来存储搜索点和运动矢量。
2 改进算法思想
2.1 块运动类型划分的改进
运动物体的整体性和视频运动的连续性致使视频的运动具有时间和空间上的相关性,这种相关性可以用来预测当前块的运动方向和运动大小,因此对当前块的运动类型进行划分。一般而言,当前块与前一帧对应位置块的像素值绝对差和SAD在一定程度上反映出图像变化的剧烈程度。SAD值大,反映图像变化大,运动速度快;SAD值小,反映图像改变小,图像变化不明显。因此可利用与前一帧对应位置块的SAD值来进行块运动类型划分[2]。为更准确地划分块运动类型,改进算法综合使用这两类依据,使得当相邻参考块与当前块的相关性较弱时,不至于引起不准确的运动类型划分。
改进算法的块运动类型划分依据如下:设参考块的运动矢量集合为V={V0,V1,V2,V3,V4}。其中,V0=(0,0),Vi=(xi,yi)(i≠0)为图2中的1,2,3和4块的运动向量。对于V中的所有候选矢量,令li=|xi|+|yi|,L=max{l1,l2,l3,l4},设定阈值L1和L2。令当前块与前一帧对应位置块中像素值的SAD值为SAD0,设定阈值T1和T2。当SAD0≤T1时,当前块被认为是静止块;当T1
这种划分方法相对MVFAST算法中的方法加强了划分的条件判断,但并未因使用与前一帧对应位置块的SAD值而增加计算量和存储复杂度,因为当前块与前一帧对应位置块中像素值的SAD值SAD0在进行静止块检测时已计算出,而且在静止块检测后,就可以进行此块运动类型的判断,无需存储SAD0值。
2.2 起始搜索点预测
改进算法采用了MVFAST算法中起始搜索点的选取方式,即搜索起始点根据当前块的运动类型进行设定:如果当前块为小运动块或中等运动块时,意味着子块的最优运动矢量位于(0,0)附近较小的区域内,无需进行起始点预测;如果当前块为大运动类型块,其最优运动矢量往往偏离中心点(0,0)较远,精确预测的搜索起始点更接近物体的真实运动矢量,从而减少搜索点数。
视频运动的时空相关性可以用来对搜索起点进行预测[3,4],其基本思想是:用空间位置上相邻且已经编码的块或时间上相邻且已编码的块的运动来预测当前块的初始运动矢量,再以此为起点做进一步的搜索。综合考虑计算量和预测效果等因素,选择左上,右上3个空间相邻块(如图2中的1,2,3)和上一帧对应位置块(如图2中的4)中运动矢量的对应点作为候选点进行预测。
搜索起点预测的主要方法有中值法、加权法和SAD比较法。因为SAD比较法的预测精度最好,能够最快地寻找到最优矢量,同时它所得出的预测起始点必然是某个相邻块的运动矢量,使得运动矢量场具有连续性,利于差分编码,所以改进算法采用了SAD比较法来预测搜索起始点。
2.3 大运动块的相对运动类型划分
改进算法加强判定小、中等运动类型的条件,使得更多的块判定为大运动块,要进行起始点的预测。这样,一方面更多的块由于使用预测的起始点进行匹配搜索而减少搜索点数,加快搜索速度;另一方面,由于块间相关性的不同,预测的准确性必然不同,若对这些大运动块采用相同的搜索策略,必然造成搜索不足或搜索冗余。因此考虑将大运动块在搜索起始点预测后进行相对预测点的相对运动类型的划分,将大运动块分为相对静止块、相对小运动块和相对大运动块。为避免复杂条件计算,其判别仅利用当前块与预测起始点对应块的像素值的SAD值,令其为SADp。如果SADp≤T1,则判定当前块为相对静止块;如果T1
2.4 搜索模式
搜索模式根据图像宏块的移动剧烈程度不同而不同,但是搜索模式也不宜复杂。在兼顾速度和精度的要求下,改进算法根据预测的运动剧烈程度选用不同的搜索模式:小运动使用简化的小菱形搜索模式,即只进行一次小菱形搜索;中运动使用小菱形搜索模式;大运动根据起始搜索点预测的准确性自适应地选择搜索模式,相对小运动块使用简化的小菱形搜索模式,相对大运动块使用小菱形搜索模式。
2.5 搜索中止准则
为提高算法的速度,一些算法使用了SAD阈值作为搜索中止的条件,即当SAD值小于某一阈值时中止搜索过程。MVFAST采用固定的阈值,PMVFAST则以当前块中左边、上边和右上边相邻块的最小SAD的最小值作为阈值。事实上,固定的阈值不具有普适性,而当前帧相邻块的最小SAD分布在数值上也没有很明确的相关性。但相邻帧对应位置块的最小SAD值间普遍存在着某种比例关系,其平均比值在0.95～1.07之间。为此,改进算法的搜索中止准则是:以参考帧对应位置块的最小SAD值乘以某个系数作为SAD阈值,即若SAD
3 改进算法描述[7,8,9,10]
改进算法的具体描述如下:
(1)初始化阈值。根据实验经验值选取阈值L1=1,L2=2。若当前块为第一个P帧内的块,阈值T1设为512,否则,T1=a×Ref_SAD,其中,a为常数,设定为0.95,Ref_SAD为参考帧对应位置块的最小SAD值。若T1<512,设定T1=512;若T1>1 024,设定T1=1 024。阈值T2设定为T2=T1+256。
(2)静止块检测。搜索零矢量位置(0,0)点,得出该点的SAD值SAD0,如果SAD0≤T1,则判定该块为静止块,(0,0)位置即为最优运动矢量。
(3)运动类型检测。对于非静止块,计算L,当T1
(4)初始搜索点的选取。根据当前块的运动类型设定搜索起始点,如果当前块为小运动块或中等运动块时,无需进行起始点预测,以中心点(0,0)为搜索起点;如果当前块为大运动类型,计算运动矢量集合V中的每个运动矢量对应的SAD值,将最小SAD值对应的运动矢量Vn所对应的点作为搜索起始点。
(5)执行搜索。对于小运动块,只使用1次小菱形搜索,就输出运动矢量,并保存最小SAD值。对于中等运动块,使用小菱形搜索至最优点在小菱形中心点,输出运动矢量,并保存最小SAD值;对于大运动块,在搜索起点预测后,计算SADp,当SADp≤T1时,当前块被认为是相对静止块,提前结束搜索;当T1
4 改进算法性能测试
采用改进算法分别对Mother and daughter序列中,Foreman序列的前100帧和Football序列的前90帧进行实验。表1、表2列出FS,MVFAST,PMV-FAST和改进算法的实验结果。其中,各项评估标准均为序列各帧的平均值,加速倍数和ΔPSNR均以FS算法的搜索结果为基准。
dB
表1、表2实验数据表明,与FS算法相比,改进算法在PSNR稍有下降的情况下,搜索速度得到大幅度提高;与MVFAST和PMVFAST算法相比,改进算法在PSNR稍有下降的情况下,搜索点数分别平均下降1.86个和1.09个。
图3给出了压缩前Foreman序列的第98帧图像及其解码后的恢复图像。可以看出,改进算法在加快运动估计搜索速度的同时,图像质量并没有明显下降。
实验结果表明,本文提出的改进运动矢量场自适应运动估计算法具有搜索速度上的明显优势,但恢复图像质量只稍有下降。
5 结语
基于对MVFAST算法的分析,充分利用视频图像的特点和运动矢量分布特性,提出了一种改进的运动矢量场自适应运动估计算法。改进算法基于MVFAST分级搜索的思想,优化了运动强度的划分方法,引入了相对运动类型的划分来对大运动块自适应地选择搜索模式,搜索中尽量使用简单策略,并自适应地提前结束搜索。实验结果表明,改进算法具有搜索速度上的明显优势,但恢复图像质量稍有下降。
摘要：MVFAST算法是视频压缩中一种重要的运动估计算法,但其缺乏是对图像时域相关性的考虑会造成不恰当的运动类型划分。因此,针对这个问题提出一种改进的运动矢量场自适应运动估计算法。该算法基于MVFAST分级搜索的思想,通过优化运动强度的划分方法,引入相对运动类型的划分来对大运动块自适应地选择搜索模式,使用简单的搜索策略,自适应地提前结束搜索。实验结果表明,该改进算法与MVFAST算法相比,在图像质量稍有下降的前提下,具有搜索速度上的明显优势。
关键词：视频压缩,运动估计,块匹配,搜索策略
参考文献
[1]HOSUR P I,MA K K.Motion vector field adaptive fast motion estimation[C]//Proc.2nd Int.Conf.Information, Communications and Signal Processing.Singapore:ICICSP, 1999:79-88.
[2]魏星,蒋建国,齐美彬.基于选择预测的自适应运动估计算法[J].中国图像图形学报,2005,10(7):873-877.
[3]HSIEH C H,LU P C,SHYN J S,et al.Motion estimation algorithm using interblock correlation[J].Electronics Letters, 1990,26(5):276-277.
[4]施建良,潘健,余松煌.区域运动相关性的运动估计方法[J].上海交通大学学报,1998,32(9):6-9.
[5]徐丽琨,黄登山.基于H.263视频压缩的新钻石搜索算法[J].微计算机应用,2005,26(5):516-520.
[6]徐丽琨,黄登山.基于H.263标准的视频压缩算法的优化及研发[J].电力系统通信,2005,26(7):31-34,41.
[7]武媛媛,郭英,苏兮,等.改进的十字菱形搜索算法[J].中国体视学与图像分析,2009(2):168-172.
[8]刘锋,庄奕琪,何威.一种新的算法可编程的运动估计协处理器[J].电路与系统学报,2007(5):126-130.
[9]何军球,赵欢.基于运动复杂度的快速模式选择算法[J].计算机工程与应用,2009(7):79-81.
[10]黎仁国.基于图像复杂度SAD计算的H.264全搜索快速算法[J].绵阳师范学院学报,2009,28(1):88-90.
搜索模式自适应快速运动估计算法 篇11
视频编码标准H.264/AVC的压缩效率比MPEG-2、MPEG-4提高了近1倍[1],与此同时也造成了运算量的大幅增加,因此高效快速的运动估计算法成为H.264实时编码器实现的关键。由于运动是视频序列固有的根本特征,所以有效利用和适应运动特征的运动估计算法可以显著提高搜索速度和编码效率。
目前,典型的快速搜索算法有三步搜索法、四步搜索法、菱形搜索法、六边形搜索法、预测运动矢量场自适应搜索算法(PMVFAST)、具有匹配预判的自适应不规则模板搜索算法(AIPS-MP)等。此外,我国研究人员还提出了非对称十字型多层次六边形网格搜索算法(UMHexagonS)[2,3],这种算法采用整数像素运动估值,在高码率、大运动图像序列编码中能保持较好率失真性能,运算量很低,已被H.264标准采纳。
2 PAFME算法
实验发现,UMHexagonS算法的搜索策略也存在一些缺点和不足,如:对于不同的运动序列都采用固定的搜索模板和相同的搜索策略,这样虽能保证较高的搜索精度,但由于没有充分利用不同序列及不同块的特征,不能自适应地结束搜索,因此存在较多的冗余搜索点,造成搜索开销增大。笔者结合H.264标准采用的可变块尺寸运动估计技术的特点,提出了一种搜索模式自适应的快速运动估计算法(Search Pattern Adaptive Fast Motion Estimation,PAFME),并通过实验测试了算法性能。PAFME算法主要采用以下核心技术:初始搜索点预测,多搜索模式选择,利用经验阈值调整搜索模式的使用。
该算法的主要思想是在保证图像质量的前提下,减少算法中的冗余搜索点,从而加快运行速度。在该算法中使用由经验得到的整数型常数作为基值;对不同尺寸的块类型,采用对基值进行简单的移位操作,以作为不同的判断阈值。
在搜索的过程中,首先对初始预测点集中的部分预测点(中值预测点及原点)进行搜索,包括小菱形四点搜索和可能的密集搜索步骤;仍不满意,再搜索上层块类型预测点,而后按当前最佳点进行小菱形搜索或可延伸的六边形和小菱形搜索步骤。算法流程如图1所示。
3 实验结果与分析
把新算法嵌入到H.264的标准参考软件JM12.4中进行测试比较,以验证其有效性。测试条件:在基本框架下,采用SATD和RDO指标,搜索范围为所有编码模式,1/4像素精度,参考帧数为1,第一帧为I帧,其余为P帧。测试序列有:Forman(QCIF,10 f/s(帧/秒)),Paris(CIF,15 f/s),Football(SIF,30 f/s),各100帧。之所以选用纹理和运动复杂度各不相同的3种测试序列,格式、帧率均有差异,是为了充分测试算法对不同内容的视频序列在不同目标下的应用性能,并且选用4种量化参数以测试算法在不同码率下的性能。
采用亮度信号的峰值信噪比(PSNRY)、比特率、整数像素精度运动估计总时间(t)等指标对PAFME算法与JM12.4参考软件采用的快速算法(JM12.4FME)的性能进行比较,实验结果详见表1。可见,PAFME算法具有以下特点:1)PSNRY平均损失0.018 d B,最大不超过0.088 dB,所以新算法对视频重建质量的影响可忽略;2)比特率的增加未超过0.7%,所以新算法对编码效率影响很小;3)运算量有较大降低,整像素精度运动估计速度提升明显,耗时平均减少33%。
对上述测试序列,在不同量化参数下,PAFME算法与JM12.4FME相比,其整像素精度运动估计的耗时百分比(tPAFME/tJM12.4FME)见图2。由图可见,在不同量化参数下,PAFME算法性能稳定,即新算法的有效性受量化参数影响较小。对不同特征的信号序列,算法性能有所差异,对运动一致性较好的序列,整像素精度运动估计的耗时可减少35%以上,搜索速度较快。
4 小结
笔者针对现有算法的不足,提出搜索模式自适应的快速运动估计算法PAFME,结合H.264标准采用的可变块尺寸运动估计算法的特点,利用运动矢量在时空域及不同编码模式间的相关性,设计了初始搜索中心的预测方法。通过测试发现:自适应的搜索模式选择规则可以显著地加快运算速度,并保持了视频质量和码率基本不变,为高速的运动估计提供了一种新的方向。
摘要：提出了一种搜索模式自适应快速运动估计算法(PAFME),首先利用变块尺寸运动估计的特点与运动矢量的时空域相关性,预测初始搜索中心;采用多种搜索模式以适应不同运动特征,提出了搜索模式自适应的选择机制,以节省不必要的搜索点加快搜索速度;又能避免陷入局部极小。实验结果表明,与H.264/AVC的参考软件JM12.4相比,该算法使整像素精度运动估计的速度提高了30%～40%,同时保持了图像质量和码率基本不变。
关键词：运动估计,搜索模式自适应,H.264
参考文献
[1]OSTERMANN J,BORMANS J,LIST P,et al.Video coding with H.264/AVC:tools,performance,and complexity[J].IEEE Circuits and Systems Magazine,2004,4(1):7-28.
[2]CHEN Zhibo,ZHOU Peng,HE Yun.Fast motion estimation for JVT,Doc.JVT-G016[C]//Proc.7th JVT Meeting,2003.Pattaya,Thailand:JVT,2003.