快速正交搜索算法（共5篇）
快速正交搜索算法 篇1
快速正交搜索 (Fast Orthogonal Search, FOS) 算法能够最大限度地减小估算量相对于目标数据的均方误差[1]。与神经网络相比, FOS算法不是依靠耗时的迭代实现最小化, 而是直接在一次迭代中就选择出合适的候选函数, 并且计算出相应的系数。该算法的实现是在所有的候选函数中选择基础函数, 能够使均方误差的减小量最大的候选函数被确定为合适的基础函数, 并从候选函数中移除;在剩余的候选函数中重复上述选择过程, 直到相应的停止条件满足时结束选择[2]。与普通的最小二乘法相比, FOS算法的优势是能够用更少的模型项建立一个精确的模型, 模型项减少的同时也减小了噪声的干扰, 从而使系统估算更为准确。目前, FOS算法已经有了很多的实际应用, 包括递归滤波去除图像中的高斯噪声和脉冲噪声, 语音信号的压缩, 磁共振成像和正电子发射断层扫描, 以及非线性系统的控制和基因的识别及其对治疗的反应的预测等[3]。
笔者从非线性预测控制的角度出发, 利用FOS算法对非线性系统进行辨识, 利用辨识模型建立预测控制器, 实现基于FOS算法的预测控制。
1 FOS算法和系统辨识*
一个非线性系统可以表示为:
式中e (k) ———系统误差, 数据记录的时间长度n=0, …, N;
F[·]———形式未知的连续非线性函数;
N、L———输入和输出的阶次;
y (k) ———系统的输出。
在FOS算法中, 式 (1) 可以进一步改写为:
式中am———Pm (k) 的权值系数。
此时, 系统的均方误差mse可以表示为:
上式上方的短横线表示数据记录在时间长度的平均值, 该算法在所有的候选函数Pm (k) 中进行搜索, 选择对均方误差贡献最大的候选函数作为模型项, 添加到构建的辨识模型当中。
为了实现这一搜索过程, 首先要得到未知结构的非线性系统模型, 利用格拉姆·施密特正交方法[4], 可以将式 (2) 改写为:
其中gm是wm (k) 的权值, e (k) 为误差, wm (k) 是利用格拉姆·施密特正交方法将非正交函数Pm (k) 正交化后得到的两两正交的函数序列。其计算过程具体如下:
其中正交系数:
此时系统的均方误差可以改写为:
正交函数的权值系数gm可以表示成:
这种正交方法的好处是它不需要输入上有自动校正功能, 在数据记录的时间内没有引入任何误差。然而, 正交函数的计算非常耗费时间, 而且需要内存有相当大的数据存储空间[5]。
为了避免上述问题, FOS算法采用隐式正交法, 不用单独计算出每一个正交函数wm (k) , 只需计算出正交系数αmr。
因此, 不用计算基础正交函数wr (k) 就能得出式 (4) 的分子, 类比式 (3) 可得:
同样, 式 (4) 的分母可以表示成:
这样, αmr的值就可以通过式 (6) 、 (7) 计算出来。同理, 式 (5) 的分子、分母也可以改写为如下形式:
从而gm就可以由式 (8) 、 (9) 计算出来。
根据式 (5) 可知, 在增加第m个函数wm (k) 后, 均方误差mse的减小量可以表示为:
因此增加一个模型项后, 剩余的均方误差mse可以表示成:
这就使得每一个非正交候选函数Pm (k) 对系统均方误差的影响清楚地展现出来。在所有候选函数中, 对应产生减小量Qm最大的一个被选为模型项, 并从候选函数中去除。接下来算法继续在剩余的候选函数中重复上述搜索过程, 直到停止搜索的条件满足时结束搜索。
停止的条件主要有:当系统的剩余误差达到足够小;一定数量的模型项已经被选出;剩余的候选函数不能使系统的误差产生足够的减小量[6]。
当搜索完成时, 利用αmr和gm可以计算出被选出的模型项Pm (k) 的系数am, 即:
2 FOS算法步骤
通过上面的讨论, FOS算法将会不断搜索适合的候选函数直到一些预定义的停止条件得到满足为止。FOS算法的步骤为:
a.将非正交候选函数序列Pm (k) 经过隐式正交化后得到正交函数序列wm (k) ;
b.计算正交函数wm (k) 的权值系数gm, 计算每一个候选函数相对于均方误差的减小量Qm, 选择Qm最大的候选函数作为模型项;
c.重复步骤a、b, 直到任何一个终止条件得到满足为止;
d.由得出的gm和αmr递归计算am, 完成对非线性系统辨识模型的构建。
3 基于FOS算法的预测控制
一个非线性系统可以表示为:
式中F[·]———连续非线性函数[7];
N、L———输入和输出的阶次。
函数模型通常是未知的, 经过FOS算法进行辨识, 可以得到一个新模型:
是辨识模型[8]对系统输出y (k) 的逼近, 且, 从而可以得出k+1时刻的模型为:
用yr (k+1) 代替y (k+1) , yr (k+1) 为设定值的柔化序列, 以期望辨识系统的输出逼近设定值, 则上式可以改写成:
可以得出:
引入性能指标[9]为:
其中λ为控制加权因子。对性能指标进行滚动优化[10], 每次优化计算出u (k) , 并将u (k) 作为控制信号输入, 计算出实际的输出y (k+1) 。
4 仿真实例
选取非线性系统模型:
采用FOS算法进行训练时, 模型项数量M=5, 设定的输出序列为方波信号, 柔化因子α=0.4。辨识结果如图1所示。
利用上述辨识模型建立预测控制器, 对非线性系统进行预测控制, 同时与广义预测控制效果进行对比, 结果如图2所示。
5 结束语
采用FOS算法对非线性系统进行辨识, 从辨识的结果可以看出, FOS算法得出的估算模型对非线性系统有良好的跟随效果。利用估算模型建立预测模型, 对系统进行闭环优化控制。通过对实际的非线性模型进行仿真实验, 验证了所提方法的可行性和有效性。
参考文献
[1]Korenberg M J.A Robust Orthogonal Algorithm for System Identification and Time-series Analysis[J].Biological Cybernetics, 1989, 60 (4) :267~276.
[2]Korenberg M J, Paarmann L D.Orthogonal Approaches to Time-series Analysis and System Identification[J].IEEE Signal Processing Magazine, 1991, 8 (3) :29~43.
[3]Korenberg M J, Paarmann L D.Applications of Fast Orthogonal Search:Time-series Analysis and Resolution of Signals in Noise[J].Annals of Biomedical Engineering, 1989, 17 (3) :219~231.
[4]Mc Gaughey D R, Korenberg M J, Adeney K M, et al.Using the Fast Orthogonal Search with First Term Reselection to Find Subharmonic Terms in Spectral Analysis[J].Annals of Biomedical Engineering, 2003, 31 (6) :741~751.
[5]Mikael Eklund J, Korenberg M J, James Mc Lellan P.Nonlinear System Identification and Control of Chemical Processes Using Fast Orthogonal Search[J].Journal of Process Control, 2007, 17 (9) :742~754.
[6]Osman A H, Noureldin A, El-Shafie A, et al.Fast Orthogonal Search Approach for Distance Protection of Transmission Lines[J].Electric Power Systems Research, 2010, 80 (2) :215~221.
[7]舒迪前.预测控制系统及其应用[M].北京:机械工业出版社, 1996.
[8]陈增强, 袁著祉, 张燕.基于神经网络的非线性预测控制综述[J].控制工程, 2002, 9 (4) :7~11.
[9]张兴会, 陈增强, 袁著祉.基于神经网络模型的非线性多步预测学习控制器[J].控制与决策, 2002, 17 (z11) :820~822, 828.
[10]张燕, 陈增强, 袁著祉.基于Taylor逼近的非线性系统PID型多步预测控制[J].控制与决策, 2004, 19 (4) :448~451.
搜索模式自适应快速运动估计算法 篇2
视频编码标准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.
快速正交搜索算法 篇3
虹膜识别包括虹膜图像的采集、预处理以及虹膜图像的特征提取与匹配。预处理主要包括虹膜定位和归一化，其中虹膜定位是整个虹膜识别过程中非常关键的一个环节，虹膜定位的好坏与速度直接影响虹膜识别的精度与实时性。目前主流的虹膜定位算法有微积分方法[2]、Hough变换[3]方法和一些改进的算法[4,5]。Daugman提出的微积分算法定位精度和鲁棒性高，但是对输入图像的质量要求较高，计算量较大且耗时较多;Hough变换容易受睫毛以及光斑等随机噪声的影响导致定位准确率降低，其计算量与存储容量和参数空间成指数关系，故其实时性不高。
本文提出一种简单快速的虹膜定位算法，定位速度得到较大的提高，且定位精度也能够满足要求。算法的思路是：对于虹膜内边缘定位，二值化虹膜图像，采取有效措施去除噪声，运用投影法粗略得到瞳孔的圆心位置和半径，然后采用本文设计的算法精确定位出虹膜内边缘的圆心和半径;对于虹膜外边缘定位，利用虹膜内边缘定位得到的圆周参数以及外边缘半径的先验知识对边缘图像进行去噪处理，再运用定位内边缘同样的方法定位出虹膜外边缘的圆心及半径。实验结果表明，这种定位方法相比于其他方法，在保证定位精度的前提下定位速度得到了明显的提高，并且还具有较强的抗干扰能力。
1 虹膜定位
1.1 虹膜内边缘定位
采集到的虹膜图像除了包括虹膜环状区域外，还有可能包括眼皮、睫毛、光斑等噪声信息，所以在进行定位之前必须对这些噪声信息进行处理。首先对虹膜瞳孔内的光斑进行处理。本文采取区域生长法[6]处理瞳孔内的光斑。区域生长是串行区域生长的一种，就是从某个像素开始，按照一定的准则逐步加入临近元素，直到满足一定条件后区域生长终止。
虹膜的灰度分布具有一定的特点，一般是呈阶梯状分布，由内到外，瞳孔灰度比虹膜低，虹膜灰度比巩膜低，瞳孔的边界较为明显(图1(a))。根据这个特点，可以很方便的采用二值化方法分离出瞳孔。首先使用最大类间方差法[7]确定阈值，再对虹膜图像进行二值化，得到瞳孔和部分包括眼睫毛的二值化图像(图1(b))，将得到的二值化图像用数学形态学的方法进行连续的开闭运算以除去眼睫毛的影响(图1(c))，然后再对分离出来的瞳孔图像运用投影法[8]粗略得到瞳孔的圆心和半径。粗定位具体实现：将分离出来的瞳孔图像分别投影到X轴和Y轴上，得到投影图像坐标的最大值和最小值为Xmax、Xmin和Ymax、Ymin，则可以得到瞳孔粗定位的圆心坐标为：
半径为：
这样初步得到虹膜内边界的圆周参数，即粗定位圆心坐标为M(X'0,Y'0)，半径为R'0。
粗定位得到内圆圆心及半径后,运用Sobel边缘检测算子对原始虹膜图像进行边缘提取得到虹膜的边缘图像(图2(a))。从图2(a)可以看出,图像中含有大量的噪声信息及其它信息,这些噪声信息主要是由眼睫毛带来的,为了使虹膜内边缘定位更加准确,必须对这些噪声信息进行处理,处理过程为:已知瞳孔粗定位圆心坐标为M(X'0,Y'0),半径为R'0。将以M为圆心,R=R'0+Δr为半径(Δr为实验经验值,在图像分辨率为320×280时,Δr取5个像素)的圆以外所有灰度值为1的点都赋值为0,这样就得到了去噪后的瞳孔边缘图像(图2(b))。从图2(b)可以看出,大部分噪声信息都被去除,瞳孔的边缘信息被完全保留,这样为后面虹膜内边缘精定位的定位速度和精度提供了保障。
得到瞳孔的边缘图像后，就可以对瞳孔进行精定位。在CASIA虹膜数据库中进行大量实验，实验表明，用上面的去噪方法对边缘图像去噪后，瞳孔粗定位得到的圆心M和精定位得到的圆心O偏离不会太大，一般偏离大小在8个像素之内，所以在提取的瞳孔边缘图像中选取以粗定位圆心M为中心的一个[2×8+1]×[2×8+1]大小的区域作为瞳孔精定位圆心O的候选区域。在该区域内逐点搜索，以找到最精确的虹膜内边缘圆心。对于每个候选点，具体的搜索步骤如下：
1)计算该候选点与边缘图像中所有灰度值为1的点的欧式距离，并将这些距离进行排序，计算中间部分的方差(为了减少非边界点的影响);
2)对于候选区域内所有点进行步骤1的运算，得到一组方差值，方差值最小所对应的那个候选点即为精定位的瞳孔圆心点O;
3)确定内圆圆心O后，再计算O点到各边缘点的距离，取所有距离的平均值作为内圆半径，这样就得到内圆精定位圆心坐标为O(X0,Y0)，半径为R0。
这种方法能够简单快速的定位出虹膜内边缘，避免了传统定位方法对边缘点搜索的盲目性。定位结果如图2(c)所示。对于虹膜内边缘定位，本文粗定位算法与精定位算法都能够定位出质量较好的虹膜图像，而对于质量较差的虹膜图像，粗定位算法定位就会出现偏差，精定位算法的鲁棒性更好。粗定位与精定位结果对比如图2(d)。
1.2 虹膜外边缘定位
虹膜图像的虹膜区域很容易受到上、下眼睑以及眼睫毛的遮挡，本文在定位虹膜外边缘之前先采取一定的措施尽量减少眼睑及眼睫毛等噪声对虹膜外边缘定位的影响。首先利用Canny算子对虹膜图像进行边缘提取(图3(a))，从图3(a)可以看出，边缘图像中含有大量的噪声点，这些噪声点主要由眼睑、眼睫毛及其他噪声点组成，为了减少噪声点对外边缘定位的影响，根据虹膜外边缘半径的先验知识，将图3(a)中虹膜外边缘半径最大值以外及虹膜外边缘半径最小值以内的所有灰度值为1的点赋值为0，这样就得到了仅剩虹膜外边缘边界点及少量噪声点的边缘图像(图3(b))。通过图3(b)可知，大部分噪声点被去除，但是上下眼睑及眼睫毛仍然带有部分噪声点。再以内边缘定位得到的半径为基础，将上下眼睑所含区域去除掉，则外边缘左右两侧的边界点被完整的保留下来，这样就可以利用定位虹膜内边缘的方法来定位虹膜外边缘。
在CASIA虹膜数据库中进行大量实验，实验表明，虹膜内边缘圆心O和外边缘圆心I之间偏差不会太大，一般偏差在10个像素以内，所以在提取的虹膜外边缘图像中选取以内边缘圆心O为中心的一个[2×10+1]×[2×10+1]大小的区域作虹膜外边缘圆心的候选区域。在该区域内逐点搜索，以找到最合适的虹膜外边缘圆心。对于每个候选点，具体的搜索步骤同虹膜内边缘定位。这样就能够得到虹膜外边缘圆心I(Xi,Yi)以及虹膜外边缘半径Ri，最终得到的虹膜外边缘定位图如图3(d)所示。
2 算法的抗干扰性
获取的虹膜图像，有可能瞳孔内会有亮斑的存在，这些亮斑对虹膜定位的准确性会产生一定的影响，甚至可能导致定位的失败;同样的，眼睫毛以及眼睑的影响也不容忽视。所以本文运用区域生长法对瞳孔内的亮斑进行填充，以消除亮斑对定位的影响;再应用粗定位得到的瞳孔半径及外边缘半径的先验知识对眼睑及眼睫毛进行处理，以减少眼睫毛及眼睑的干扰作用。去除亮斑具体步骤：第一阶段，填补白色光斑点。首先，定位光斑内一点记为初始种子点。以种子点为中心取适当邻域大小，求出此邻域内所有像素的灰度平均值，如果此值大于阈值T1，将此点记为候选点;在找出的所有候选点中，分别求其左、右两侧适当区域内像素的灰度平均值H1、H2，如果这两个值中存在一个值小于阈值T2，则将此点标记为真正光斑点。其次，填充光斑。选择一个真正光斑点为种子点并将该点像素灰度值赋值为0;以该点为中心，考虑与其相邻的4邻域像素点，如果其中的某个像素点的灰度值为255，则将此像素点与该点合并，并将其灰度值赋值为0;将所有符合条件的像素点合并，直到图像中每个光斑都填充完毕。第二阶段，填充瞳孔区域。由于光斑的存在，使瞳孔内光斑的附近像素的灰度值也比较高，所以需要进一步对整个瞳孔区域进行填充，具体的思想与第一阶段相同。实验随机抽取了几副有明显噪声的图像，对于瞳孔内含有亮斑的图像定位如图4(a);有眼睫毛及眼睑影响的图像定位如图4(b);既有亮斑又有眼睫毛及眼睑影响的图像定位如图4(c)。实验表明，采用本文的算法能够快速准确的定位出这些含有噪声的虹膜图像，说明本文算法具有较强的抗干扰能力。
3 实验结果及分析
实验使用的计算机CPU为AMD 2800+,内存为512M,编程工具为MATLAB7.0,实验采用的图像为中科院自动化所提供的CASIA虹膜数据库。利用本文提出的算法,在MATLAB 7.0上精确的实现了虹膜内、外边缘的定位,相比于其他算法,定位速度有了显著提高。本文算法与微积分算法、Hough变换算法以及文献5的算法比较如表1所示。
由表中数据可以看出,利用本文提出的算法定位速度有着明显提高,并且本文算法在定位准确率上也能够满足要求。微积分算法和Hough变换算法对虹膜图像的质量要求比较高,当虹膜图像质量下降时,算法的定位准确率急剧下降;文献[5]的算法主要是对低质量图像进行定位,定位准确率得到了保证,但是定位速度不及本文算法,本文算法对虹膜图像内的亮斑和眼睫毛及眼睑进行了处理,所以本文算法在改善了虹膜识别实时性的同时还具有一定的抗干扰性。
4 结论
虹膜定位在虹膜识别实时性要求上起着关键性的作用。本文针对虹膜图像数据量大、易受光斑眼睫毛等噪声影响，提出了一种简单快速的虹膜定位算法。该算法减少了噪声点对定位过程的影响，利用先验知识及实验数据将待搜索圆心缩小在一定范围，利用最小方差搜索圆心最终完成虹膜内、外边缘的精确定位。实验结果表明，该算法在满足定位精度的前提下大大缩短了定位时间，提高了虹膜识别的实时性。
本文作者创新点：使用投影法粗定位内圆圆心和半径，缩小精定位圆心的搜索范围，采用最小方差法搜索内外圆圆心，完成内外圆的精确定位。
摘要：为了改善虹膜识别的实时性,提出一种新的快速虹膜定位方法。首先对虹膜图像进行去噪处理,然后采用类间方差法对图像进行阈值分割,再运用投影方法粗略得到虹膜内边缘圆心和半径,最后根据粗定位得到内边缘圆周参数,采用所提出的算法对虹膜内边缘进行精定位;对于外边缘定位,依据先验知识以及内边缘圆周参数去掉虹膜图像多余的边缘点及噪声点,缩小搜索范围,然后采用同样的算法对外边缘进行精定位。实验结果表明,该方法能够准确快速的定位出虹膜内外边缘,定位速度较传统算法提高了十倍左右,并且减少了传统定位算法搜索的盲目性。
关键词：虹膜定位,去噪,阈值分割,投影,最小方差
参考文献
[1]常卫东,刘完芳,鄢喜爱,等.虹膜识别的研究现状与发展趋势[J].中国科技信息,2007(1):246-247.
[2]Daugman J.High confidential visual recognition by test of statistical independence[J].IEEE Trans on pattern analysis and machine in-telligence,1993,15(11):1148-1161.
[3]Wildes R P.Iris recognition:an emerging biometric technology[J].IEEE,1997,85(9):1348-1363.
[4]吴建华,邹德凯,李静辉.基于小范围搜索的虹膜定位算法[J].仪器仪表学报,2008,29(8):1704-1708.
[5]王洪,曾文.一种改进的虹膜定位算法研究[J].武汉理工大学学报,2008,30(6):846-848.
[6]Gonzalez Rafael C.Digital image processing[M].Beijing:Publishing house of electronics industry,2006:519-530.
[7]Otsu N.Threshold Selection Method from Gray-level Histograms[J].IEEE Transactions on Systems,Man and Cybernetics,1979,SMC-9(1):62-66.
快速正交搜索算法 篇4
H.264/AVC由ITU-T视频编码专家组 (VCEG) 与ISO/IEC MPEG组成的JVT (Joint Video Team) 联合开发, 沿用了基于块的混合编码技术, 但在技术细节上做了很大改进, 采用了多参考帧预测编码、多种可变块大小的帧间编码模式、1/4像素精度的运动补偿等先进技术。由于上述先进编码技术的引进, H.264/AVC成为近年来最为高效的一个视频压缩标准, 与MPEG-2、MPEG-4相比, H.264/AVC的压缩效率为它们的2倍[1]。但与此同时也造成了运算量的大幅增加。由于运动是视频序列所固有的根本特征, 通过充分利用与运动特征相适应的运动估计算法, 可以显著提高编码技术在搜索速度和编码效率方面的性能。
本研究提出一种搜索模式自适应快速运动估计算法 (PAFME) 。
1 典型的运动估计算法
早期的快速搜索算法有:三步搜索法 (TSS) 、新三步搜索法 (NTSS) 、二维对数搜索法 (LOGS) 、十字搜索算法 (CS) 、四步搜索法 (FSS) 、菱形搜索 (DS) 、六边形搜索等。在上述算法中, 最高效、最常用的是减少搜索点数的新三步法[2]、菱形法[3]与六边形法[4]等。此类快速算法基于如下假设:运动矢量为中心偏离分布, 且搜索点在接近全局最优点时对应的匹配误差单调下降。由于上述假设条件并不总能成立, 特别在运动较大时, 此类算法容易陷入局部极小, 会显著降低视频质量。近几年发展起来的基于运动矢量预测的快速运动估计算法, 如预测运动矢量场自适应搜索算法 (PMVFAFST) [5]、增强的预测带状搜索 (Enhanced Predictive Zonal Search, EPZS) [6]与具有匹配预判的自适应不规则模式搜索算法 (Adaptive Irregular Pattern Search with Matching Prejudgment, AIPS-MP) [7]和UMHS算法 (hybrid Unsymmetrical-cross Multi-Hexagon-grid Search) [8,9]等, 显示出了更好的编码性能和较快的搜索速度。此类算法利用运动矢量的相关性预测初始搜索中心, 基于“初始搜索中心接近全局最优点”的假设, 仅在初始搜索中心附近按特定搜索模式进行局部搜索;此外常引入匹配预判方法提前终止局部搜索, 以进一步节省计算开销。显然, 其性能依赖于初始搜索中心预测的可靠性及搜索模式的设计, 且与块的局部运动特征密切相关。
而在H.264/AVC参考软件中使用的就是UMHS算法。UMHS算法采用了基于运动矢量预测的快速运动估计技术的基本思想, 只是在初始搜索点、搜索模板及搜索中止准则的设计上, 充分利用了H.264中多块尺寸运动补偿模式与多参考帧的特点, 以解决因减少搜索点数而容易陷入局部极小的问题。UMHS算法主要步骤如下:
(1) 初始搜索点预测—空域的中值预测、上一层块尺寸类型的预测、相邻参考帧间的预测与时域预测, 搜索以上所有的初始搜索点, 判断是否满足提前中止准则;
(2) 不对称十字形搜索, 并判断是否满足提前中止准则;
(3) 多六边形栅格搜索, 包括半径为2像素的正方形模板与多个六边形 (16像素) 模板;
(4) 可延伸的基于六边形的搜索, 包括六边形模板与菱形模板。
其中, 提前中止准则基于3种RDC预测方式—中值预测、上层块尺寸类型预测与相邻参考帧的预测, 并且为量化参数的函数。此算法中每一步都是以前一步搜索所得的最佳匹配点为搜索中心。
可见, UMHS算法利用了H.264中多块尺寸运动补偿模式与多参考帧的特点;采用了块尺寸类型间运动矢量预测方法以及相邻参考帧间运动矢量预测方法, 提高了初始搜索点预测的准确性;采用了不对称十字形、多六边形栅格、六边形搜索等搜索模板, 以尽量避免陷入局部极小;设计了基于块尺寸类型间RDC预测与相邻参考帧间RDC预测的中止准则, 使得在运动矢量预测准确时能快速中止。
2 PAFME算法
经过大量实验测试和深入分析发现, UMHS算法的搜索策略仍存在一些缺点和不足, 即对于不同的运动序列都采用固定的搜索模板和相同的搜索策略, 这样虽能保证较高的搜索精度, 但由于没有充分利用不同序列及不同块的特征, 不能自适应地结束搜索, 存在较多的冗余搜索点, 产生很多不必要的搜索, 从而造成搜索开销增大。笔者结合H.264/AVC标准采用的变块尺寸运动估计的特点, 提出了一种改进算法即搜索模式自适应的快速运动估计算法 (PAFME) , 并通过仿真测试了算法的性能。PAFME算法针对UMHS算法的特点做了3个方面的改进:初始搜索点预测;多搜索模式选择;利用经验阈值调整搜索模式的使用。
2.1 初始搜索点预测
在初始搜索点预测方面, 其仅采用了空域的中值预测与上一层块尺寸类型的预测;如图1所示, 对运动矢量采用中值预测, 利用位于当前块左边、上边、右上 (或左上) 相邻块的预测值来预测当前块的运动矢量。
pred_mv=median (Mv_A, Mv_B, Mv_C) (1)
预测运动矢量为 (pred x, predy) 。当A块位于图片或宏块边界以外时, 其运动矢量将被 (0, 0) 所替代;若C块位于图片或宏块边界以外, 则被D块的运动矢量所替代, 而当B和C都不在边界之内时, 则将被第3块的运动矢量所替代。
在H.264变尺寸块匹配运动估计中, 同一块在不同编码模式下所得运动矢量也具有相关性[10]。编码模式为m的块, 其上层块尺寸类型下运动矢量集合记为MVUP, m=1时对应空集, 其具体构成如下:
undefined
式中 MVm—编码模式m下此块的运动矢量。
2.2 多搜索模式选择
搜索模板的大小和形状不但影响运动估计速度, 而且直接关系到算法的性能。为了获得更好的搜索速度和性能, 确定搜索模板的类型, 必须分析运动矢量分布的状况。
视频图像序列的运动矢量分布一般具有如下特性:
(1) 约有81.80%的运动矢量位于以中值预测点为中心的正方形搜索窗口内;77.52%的运动矢量位于菱形区域, 特别是有45.44%的运动矢量是零矢量。这说明绝大部分的图像块是静止或准静止的, 运动矢量分布具有中心偏置特性[11]。
(2) 运动矢量的概率分布是以中值预测点为中心向四周递减的;
(3) 运动矢量分布在水平和垂直方向的概率要比分布在相同半径下的其他方向大。
根据上述运动矢量的分布特性, 在PAFME算法中先后采用了局部3×3正方形搜索模式 (如图2所示) 、小菱形搜索模式 (如图3所示) 以实现小运动矢量的快速搜索;对于运动较大的块, 采用六边形搜索模式 (如图4所示) 可以实现搜索范围和搜索速度的折衷;另外对于运动剧烈或运动矢量分布不规则的区域, 为了在搜索中避免陷入局部极小, 采用“十”字形模式 (如图5所示) 和多层六边形模式进行大范围的稀疏搜索。在算法的执行过程中通过使用一些经验阈值自适应地调整搜索模式。
2.3 利用经验阈值调整搜索模式的使用
根据RDC选择搜索模式, RDC阈值采用简单的经验阈值 (Jth, 由经验得到的整数型常数作为基值, 其经验阈值的计算方法参见文献[12]) , 通过J
(1) 收敛条件:若满足收敛条件 (J
(2) 密集搜索条件:若满足密集搜索条件, 则进行密集搜索以避免搜索到的是局部最优。
3 测试结果与分析
为验证新算法的有效性, 把新算法嵌入到H.264的标准参考软件中进行测试比较。测试过程中选用的H.264视频编码器版本为JM12.4。测试条件如下:基本框架 (baseline profile) 下, 采用RDO、SATD, 搜索范围为16像素, 1/4像素精度, 针对所有编码模式, 参考帧数设为1, 第1帧为I帧, 其余各帧都为P帧。测试序列为:Silent (QCIF) , 帧率15 fps, 150帧;Forman (QCIF) , 帧率10 fps, 100帧;Paris (CIF) , 帧率15 fps, 100帧;Mobile (CIF) 与Football (SIF) , 帧率30 fps, 100帧。这些测试序列的纹理和运动复杂度各不相同, 格式从QCIF到CIF, 帧率也有差异, 以充分测试算法对不同内容视频序列在不同目标应用下的性能。为在较大码率变化范围下测试算法的性能, 量化参数QP设置为8、18、28与38。QP=28时PAFME算法与JM12.4参考软件中的UMHS算法在亮度信号的峰值信噪比 (PSNRY) 变化情况、比特率 (Bit-rate) 变化情况、整数像素精度运动估计总时间 (Time) 变化情况等方面的比较结果如表1所示。Foreman序列和Football序列的率失真曲线如图6、图7所示。
从表1中可以看出, 对所有测试序列采用PAFME算法的情况与采用JM12.4FME算法时相比, 具有以下特点:
(1) 亮度信号的PSNR损失平均为0.018 dB, 最大不超过0.088 dB, 对视频重建质量的影响可以忽略;
(2) 比特率的增加很小, 最大不超过0.7%, 编码效率基本不变;
(3) 整像素精度运动估计的耗时平均降低了33%左右。
以上仿真结果同时表明, 搜索模式选择规则的有效性受量化参数影响较小, 主要依赖于序列的运动特征。与JM12.4FME算法相比, 所提出的搜索模式自适应的快速运动估计算法显著降低了计算量, 同时保持了编码效率基本不变。
4 结束语
在分析现有算法的优势和不足之处的基础上, 本研究提出了一种搜索模式自适应的快速运动估计算法。针对H.264采用的变块尺寸运动估计技术的特点, 笔者利用运动矢量在时域、空域及不同编码模式间的相关性, 设计了初始搜索中心预测方法, 并引入了搜索模式自适应调整的方法。通过测试发现:自适应的搜索模式选择规则可以显著地加快运算速度, 并保持视频质量和码率基本不变。
参考文献
[1]OSTERMANN J, BORMANS J, LIST P, et al.Video cod-ing with H.264/AVC:tools, performance, and complexity[J].IEEE Circuits and Systems Magazine, 2004, 4 (1) :7-28.
[2]LI R X, ZENG B, LIOU M L.A new three-step search al-gorithm for block motion estimation[J].IEEE Transac-tions on Circuits and Systems for Video Technology, 1994, 4 (4) :438-442.
[3] ZHU S, MA K K. A new diamond search algorithm for fast block-matching motion estimation[J]. IEEE Transactions on Image Processing, 2000, 9 (2) :287-290.
[4] ZHU C, LIN X, CHAU L P. Hexagon-based search pattern for fast block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2002, 12 (5) :349-355.
[5]TOURAPIS A M, AU O C, LIOU M L.Predictive MotionVector Field Adaptive Search Technique (PMVFAST) -En-hancing Block based Motion Estimation[C].Proceedings ofVisual Communications and Image Processing 2001 (VCIP-2001) .San Jose:[s.n.], 2001.
[6]TOURAPIS AM, AUO C, LIOUML.Highly efficient pre-dictive zonal algorithms for fast block-matching motion esti-mation[J].IEEE Transactions on Circuits and Systemsfor Video Technology, 2002, 12 (10) :934-947.
[7]NIE Y, MA K K.Adaptive irregular pattern search withmatching prejudgment for fast block-matching motion estima-tion[J].IEEE Transactions on Circuits and Systems forVideo Technology, 2005, 15 (6) :789-794.
[8] CHEN Z, ZHOU P, HE Y. Fast Motion Estimation for JVT, Doc. JVT-G016[C]. 7th JVT meeting 2003. Pattaya:[s.n.], 2003.
[9] CHEN Z B, ZHOU P, HE Y. Fast Integer Pel and Fractional Pel Motion Estimation in for JVT, Doc. JVT-F017[C]. 6th JVT Meeting 2002. Awaji: [s.n.], 2002.
[10]CHEN Z, ZHOU P, HE Y.Fast Motion Estimation forJVT, Doc.JVT-G016[C].7th JVT meeting 2003.Pat-taya:[s.n.], 2003.
[11]CHEUNG C H, PO I M.A novel cross-diamond search al-gorithm for fast block motion estimation[J].IEEETransactions on Circuits and Systerns for Video Tech-nology, 2002, 12 (12) :1168-1177.
快速正交搜索算法 篇5
提高H.264[1,2]帧间预测运动估计算法效率的主要技术可以归纳为3类:起始搜索点的选择,更高效的块匹配准则,减少搜索点数的搜索策略。以第3类效率最高、使用最多,较典型的算法有交叉法(CSA)[3]、菱形搜索法(DS)[4]、六边形搜索法(HEXBS)以及非对称十字形多六边形搜索法(UMHexagonS)[5]等。这些算法考虑到相邻帧之间的相关性,对最有可能出现匹配位置的区域进行优先搜索,如CSA,DS,HEXBS优先搜索预测中心;UMHexagonS优先搜索中心和水平方向的匹配点。然后根据局部收敛原理,搜索全局最优匹配。
笔者通过研究任意点关系来判断附近点阵是否存在最优匹配和次最优匹配点,并在此基础上提出了新的快速搜索算法。实验表明,该算法在没有视频运动估计模型先验概率的基础上依然有较好的峰值信噪比(PSNR)和比JM提供的快速算法更快的搜索效率。
2 搜索点匹配的方法
每个分割运动矢量(MV)的编码需要相当数目的比特。为减少传输比特数,可利用邻近分割较强的相关性,MV可由邻近已编码分割的MV预测而得。预测矢量差异基于已计算的MV和MVD(预测与当前的差异)。同时传输运动补偿残差也将需要大量的比特[6]。检验搜索算法优劣有3个主要指标:运算时间、PSNR和编码比特数。H.264采用MV编码比特和运动残差求和计算搜索区域各点的编码消耗。由于分割MV编码计算相对简单,H.264对其优先计算。如果某点MV编码消耗大于已经计算的匹配点编码总消耗,该点不是匹配点,就不用进行后续计算。
为便于分析,以4×4大小的待编码图像为例,只考虑各像素点亮度,而忽略色度值,并假定待编码宏块/子宏块图像水平方向灰度变化最慢。某搜索点残差值用SAD(Sum of Absolute Difference)方式编码。匹配点的SAD比非匹配点的大,将消耗更多编码比特。设Bn(x,y)为第n帧图像中的一个待编码宏块,定义Bn(x,y)在4×4帧间编码模式下的SAD为
式中:Y和分别为当前和参考图像的灰度值,(u,v)为宏块的运动矢量。
2.1 待编码宏块纹理方向计算
定义待编码图像水平方向纹理特征值为
式中:B为像素灰度差数目,对4×4水平方向,值为12,竖直和对角方向可类似分析,得到4个方向的纹理特征值。取最小值判断待编码图像纹理方向。如只有一个方向具有最小值,则认为其为该方向纹理。如有两个以上方向有相同最小值,则认为其为不确定方向纹理。4×8,8×4,8×8,16×8,8×16,16×16等分割方式可用类似方法讨论。这样得到5种可能的纹理类型。待编码图像为方向纹理的概率大,为不确定方向纹理的概率小。
如果有参考图像区域的帧内预测模式选择类型数据组,可以设计待编码宏块的加速算法。
2.2 匹配块附近纹理特征
对于4×4待编码图像,假定某点SAD值已预测,有
式(3)为其左侧邻近点的SAD值。比较两值大小,若(x,y)点的SAD大于(x-1,y)点的SAD,则有
不妨设公式(2)值为0,代入公式(4)。由假定,该4×4大小待编码图像为水平方向纹理,则水平方向有最小的TSAD值。在H.264中多细节区域采用小尺寸分割,平坦区域有大分割尺寸。4个方向的TSAD值总和应在均值附近正态分布。水平方向TSAD值最小,则一定有水平方向像素灰度值近似相等。
较小,所以该点的SAD值须进行计算。对于点(u+1,v),则一定有较大SAD值。对于(u+2,v),(u-3,v),(u+3,v)点可同样分析。
继续分析(u,v-1),(u,v+1),若(u,v)SAD值较小,由于待匹配图像为水平方向纹理,则(u,v-1),(u,v+1)一定有较大SAD。对于(u-1,v-1),(u+1,v-1),(u-1,v+1),(u+1,v-1)分析类似。
2.3 该方法特点
用某点和其附近点SAD关系在已知待编码图像的TSAD关系条件下,可以估计附近点SAD较小值点阵区域。由于MV编码对于邻近点变化连续,SAD变化对于小区域运动估计是主要因素,可以用运动估计编码总比特代替SAD比特作为判决条件。
该方法具有一定的误差,但对于快速搜索算法根据局部收敛的原理,搜索全局最优匹配的方法,可以设计出具有较小误差的快速搜索算法。
3 新的搜索算法———CMFS
运动估计时间的长短与搜索点阵的数目和初始搜索位置有关。UMHexagonS的搜索方法是按运动概率模型,对水平运动多搜索,安排了一个非对称初始搜索阵列。然后在最优匹配点附近做2次六边形和1次菱形搜索。由于真实场景水平运动较多,垂直运动少,该初始搜索阵列显然对真实场景有较好的匹配。但对于动画及垂直运动较多的场景就很难搜索到全局最优的匹配点。
3.1 CMFS局部搜索区域点阵
由以上分析,可得到对当前最优匹配位置附近可能出现全局最优匹配位置的局部搜索区域点阵,如图1。
3.2 速度最优的CMFS算法初始点阵
由于初始搜索阵列与实际视频特性有关,需要视频序列的先验概率模型。这里暂时给出基于速度最优的CMFS。根据速度最优原则,各局部搜索区域点阵拼接应能覆盖整个搜索区域。这样得到了速度最优的初始搜索点阵。对于不同的纹理类型有不同的初始点阵。对于水平方向纹理的待编码宏块,搜索范围为16,搜索区域为33×33的参考图像,搜索初始点阵如图2所示。
黑点为中央25个优先搜索点,对于多数视频序列,中央区域出现匹配点的概率很大。所以必须首先搜索。菱形位置为剩余的初始点阵,并且用图1的局部搜索点阵代替菱形位置可以覆盖绝大部分搜索区域。对于不能覆盖覆盖的少量边缘区域的点可以用全搜索处理,也可以不考虑。因为这些位置出现匹配点的概率太低,而且很多针对搜索范围的优化算法减少的正是边缘搜索点数。对于其他3个方向的初始点阵可同理得到。为得到更好的估计效果,可增加更多的初始搜索点。初始点的选取应根据视频序列先验知识得到。
3.3 CMFS的搜索策略
根据初始搜索位置的编码比特情况可以推测局部搜索区域点阵范围的其他位置的编码比特情况,从而得出这个局部范围的编码比特具有相关性。而目前大部分快速搜索算法则是根据参考图像编码比特局部相关的性质进行搜索的。整个CMFS算法步骤概括如下:
1)进行待编码图像纹理方向判断。判断方法可以由参考图像帧内预测模式选择得到,也可以直接用TSAD计算得到最小值进行判断。这大约为4个搜索点的计算量。然后进入步骤2)。
2)根据判断结果选择相应方向的初始搜索点阵。然后进入步骤2)。如果判断结果为不确定方向纹理,则进行全搜索算法或是利用其他的快速搜索算法。出现这种可能的概率非常小,接近零,进入步骤5)。
3)计算初始点阵各点的编码比特。得到最小的3个编码比特位置。进入步骤4)。
4)将相应的局部搜索区域点阵代替这3个最小编码比特位置,对这些位置进行全搜索。得到的最小编码比特位置即为匹配点,相应的MV为对应的运动矢量。进入步骤5)。
5)对不确定方向纹理进行全搜索算法或是利用其他的快速搜索算法。对方向纹理搜索的边缘剩余进行全搜索算法或是利用其他的快速搜索算法。
该算法是自适应的搜索算法,如果具有先验知识还可以进行相应的优化。
4 实验结果
实验采用JVT的JM14.0作为实验平台,主要的编码设置如下:帧格式为4∶2∶0,图像序列以30 f/s(帧/秒)的速度进行编码,量化步长QP值分别为28,28和30,对carphone,coastguard,foreman,grandma,highway,motherdaughter,salesman,silent,suzie共9个QCIF图像序列均用9帧图像进行测试。选取全搜索算法(Full),JM自带快速搜索算法(Fast)与CMFS进行性能对比。CMFS用TSAD判断纹理方向,初始搜索阵列为速度最优阵列,对不确定方向纹理进行全搜索,对搜索剩余位置不予搜索,得到如表1所示数据。
从表1见:CMFS速度优势明显,对9帧图像(其中1帧为I帧)编码效率比全搜索快近2倍,比快速搜索算法快1倍。对于carphone,salesman,suzie序列,CMFS的PSNR值略有降低,编码比特值略有提高。说明参考图像最优匹配点附近有灰度跳变的视频类型用速度最优的初始搜索阵列会有少量的比特率提高和质量下降。应尽量避免待编码宏块纹理数据集中于宏块边缘,根据跳变先验特性增加初始搜索点。对于coastguard,foreman,grandma,mother-daughter,silent序列,CMFS的PSNR值未降低,编码比特也无明显变化。这表明CMFS算法的普适性很好。对特定视频还可设计不同的CMFS算法。
5 结束语
笔者在研究H.264搜索算法的基础上,提出了基于待编码图像纹理分析搜索点是否匹配的方法,进而给出了一种新的快速搜索方法,并对其中速度最优的一种普适算法特例进行了实验研究。实验结果表明,该算法在保证编码质量没有明显下降的同时,运动估计速度有了显著提高;在处理中,算法跳变少,易于硬件实现,是一种综合性能优良的快速运动估计算法。而且该算法具有自适应性,同时能够根据不同视频特性设计不同的CMFS算法,利于商业化应用。
摘要：为减小H.264帧间预测运动估计算法复杂度,提出了一种基于待编码宏块纹理特性以排除部分搜索位置的方法。该方法可以大大减少待搜索位置的数目,缩短帧间预测时间。同时给出了一种基于宏块纹理的自适应快速搜索算法。实验表明,新算法在重建图像质量没有明显下降的前提下,编码速度有所提高。
关键词：H.264标准,视频编码,运动估计,纹理特性,CMFS
参考文献
[1]ITU-T Recommend H.264/ISO/IEC11496-10.Draft ITU-T Rec-ommendation and FinalDraft International Standard of Joint Video Specification(Advanced Video Coding)[S].2003.
[2]WIEGAND T.Overview of the H.264 video coding standard[J].IEEE Trans.Circuits and Systems for Video Technology,2003,13(7):1-19.
[3]GHANBARI M.The cross-search algorithm for motion estimation[J].IEEE Trans.Communication,1990,38(7):950-953.
[4]ZHU Shan,MA Kai-kuang.A new diamond search algorithm for fast block matching motion estimation[J].IEEE Trans.Image Pro-cessing,2000,9(2):287-290.
[5]CHEN Zhi-bo,ZHOU Peng,HE Yun.Fast integer pel and frac-tional pel motion estimation for JVT[C]//JVT-F017:Joint Video Team(JVT)of ISO/IEC MPEG&ITU-T VCEG6th Meeting,Awaji,Island,JP:JVT,2002.