《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 其他 > 設(shè)計(jì)應(yīng)用 > 基于JM模型的UMHexagonS算法的改進(jìn)
基于JM模型的UMHexagonS算法的改進(jìn)
來源:微型機(jī)與應(yīng)用2012年第3期
賀艷春,林其偉
(華僑大學(xué) 信息科學(xué)與工程學(xué)院,福建 廈門 361021)
摘要: 為了提高運(yùn)動估計(jì)的搜索效率,提出了一種基于JM模型的UMHexagonS算法的改進(jìn)方案。該方案減少了搜索點(diǎn)數(shù),從而減小了運(yùn)算量。經(jīng)過實(shí)驗(yàn)測試,改進(jìn)后的UMHexagonS算法在保證編碼圖像的質(zhì)量基本不變的同時,能顯著減少搜索時間。
Abstract:
Key words :

摘  要: 為了提高運(yùn)動估計(jì)的搜索效率,提出了一種基于JM模型的UMHexagonS算法的改進(jìn)方案。該方案減少了搜索點(diǎn)數(shù),從而減小了運(yùn)算量。經(jīng)過實(shí)驗(yàn)測試,改進(jìn)后的UMHexagonS算法在保證編碼圖像的質(zhì)量基本不變的同時,能顯著減少搜索時間。
關(guān)鍵詞: UMHexagonS算法;運(yùn)動估計(jì);運(yùn)動矢量

 運(yùn)動估計(jì)中的塊匹配算法因運(yùn)算簡單、容易實(shí)現(xiàn)而成為目前運(yùn)動估計(jì)的主流。其中的全搜索算法(FS),因其窮盡搜索每個像素點(diǎn),搜索精度最高,但計(jì)算太復(fù)雜,不能滿足實(shí)時性要求;而三步法(TSS)、四步法(FSS)以及交叉搜索法(CSS)等,相對FS,減少了搜索點(diǎn)數(shù),滿足實(shí)時性要求,但不利于小的運(yùn)動塊的搜索;新三步法(NTSS)、六邊形法(HEX)、鉆石法(DS)、新四步法(NFSS)等,雖然提高了運(yùn)動估計(jì)的速度,解決了早期算法不利于小運(yùn)動塊搜索的問題,但易陷入局部最優(yōu)點(diǎn),且不能很好地處理圖像的運(yùn)動類型[1]。針對這些問題,CHEN Z B等[2]人提出了UMHexagonS算法,它是一種混合型搜索算法,綜合了非對稱十字形法、六邊形法、菱形法等,相對FS,其均峰值信噪比(PSNR)保持基本不變,而運(yùn)動估計(jì)時間減少了近90%,是目前運(yùn)動估計(jì)搜索效率最高的快速搜索算法,己被JVT正式采納。
1 UMHexagonS算法簡介
 UMHexagonS算法的搜索路徑如圖1[3]所示,它主要分4步進(jìn)行搜索:
 (1)初始搜索點(diǎn)預(yù)測。包括中值預(yù)測、上層預(yù)測、前幀預(yù)測以及鄰近參考幀預(yù)測,得到最佳的初始搜索點(diǎn)。
 (2)以步驟(1)得到的最佳初始搜索點(diǎn)為中心,進(jìn)行非對稱的十字形搜索,取絕對差值和(SAD值)最小的點(diǎn)為當(dāng)前最佳匹配點(diǎn)。其中水平方向的搜索范圍為窗口寬度,垂直方向的搜索范圍為窗口寬度的一半,如圖1的step2所示。

?。?)以步驟(2)得到的最佳匹配點(diǎn)為搜索中心,進(jìn)行5×5共25點(diǎn)的正方形螺旋搜索,如圖1的step3-1所示。接著進(jìn)行多層六邊形格點(diǎn)搜索,取最小SAD值所對應(yīng)的點(diǎn)為最佳匹配點(diǎn),如圖1的step3-2所示。
?。?)該步驟分兩步進(jìn)行:①以步驟(3)獲得的最佳匹配點(diǎn)為搜索中心,進(jìn)行擴(kuò)展的六邊形搜索。若當(dāng)前最小SAD值點(diǎn)位于六邊形的中心,則轉(zhuǎn)到b;否則返回a繼續(xù)進(jìn)行六邊形搜索,直到最小SAD值點(diǎn)位于六邊形的中心,如圖1的step4-1所示。②以步驟(3)的中心點(diǎn)為搜索中心,進(jìn)行小菱形搜索,直到最小SAD值點(diǎn)位于小菱形的中心時,停止搜索,如圖1的step4-2所示。
 雖然UMHexagonS算法具有很高的編碼效率,但仍存在兩種不足:
?。?)參考文獻(xiàn)[4]中指出,在如圖2所示的H.264的7種幀間預(yù)測模式中,有30.71%~98.03%的預(yù)測塊的運(yùn)動矢量全為0。若能在UMHexagonS算法進(jìn)行搜索之前就判決出這些零運(yùn)動矢量,就可以提前退出搜索,減少搜索時間。
 (2)候選搜索塊的運(yùn)動劇烈程度不同,其運(yùn)動矢量的分布也不同。UMHexagonS算法對所有的候選搜索塊都是進(jìn)行4層16點(diǎn)的六邊形搜索,沒有考慮到候選搜索塊的運(yùn)動劇烈程度的不同,因此搜索存在冗余。
2 基于UMHexagonS算法的改進(jìn)
?。?)針對UMHexagonS算法的第一種不足,提出了零運(yùn)動矢量提前判決的方法。
在進(jìn)行初始搜索點(diǎn)預(yù)測時,最先進(jìn)行中值預(yù)測,且所有的模板都可以使用中值預(yù)測,因此,可以判斷中值預(yù)測得到的最佳匹配點(diǎn)mv(best_x,best_y)的SAD值是否小于給定的閾值,若小于,則判決出該塊的運(yùn)動矢量為0。
 定義SAD值為:
 

 


3 實(shí)驗(yàn)結(jié)果與分析
 本文采用JM10.1模型進(jìn)行測試,分別對運(yùn)動劇烈的coastguard序列、運(yùn)動中等的foreman序列、運(yùn)動平緩的news序列以及運(yùn)動較復(fù)雜、細(xì)節(jié)較多、水平方向運(yùn)動特征明顯的Football序列進(jìn)行了測試,這些序列都采用QCIF格式。編碼100幀,IPPPP……編碼模式,采用Hardmard變換,CABAC熵編碼,QP取28,選取5幀參考幀。比較運(yùn)動估計(jì)時間Me-time和峰值信噪比PSNR值。測試數(shù)據(jù)結(jié)果如表1所示。

 表1中,△Me-time表示改進(jìn)的UMHexagonS算法的運(yùn)動估計(jì)時間減去原UMHexagonS算法的運(yùn)動估計(jì)時間得到的差值與原UMHexagonS算法的運(yùn)動估計(jì)時間的百分比;△PSNR表示改進(jìn)后與改進(jìn)前的UMHexagonS算法的PSNR值的差值;△bit-rate/(kb/s)表示表示改進(jìn)后與改進(jìn)前的UMHexagonS算法的比特率的差值,正號表示增加,負(fù)號表示減少。由表1可知,改進(jìn)后的算法與原算法相比,PSNR值基本保持不變,比特率有所增加,但是在誤差允許的范圍之內(nèi)(±0.2 kb/s);運(yùn)動估計(jì)所消耗的時間減少了10%~25%。達(dá)到了一定的改進(jìn)效果。
 本文通過分析UMHexagonS算法的一些不足,提出了零運(yùn)動矢量提前判零、自適應(yīng)選擇水平方向和垂直方向搜索范圍的相應(yīng)的改進(jìn)措施以及自適應(yīng)的選擇搜索模板。這樣的改進(jìn)在保證圖像編碼質(zhì)量基本不變的情況下,減少了運(yùn)動估計(jì)的搜索時間,從而提高了編碼效率。
參考文獻(xiàn)
[1] 袁濤.基于H.264運(yùn)動估計(jì)算法的研究[D].重慶:重慶大學(xué),2009.
[2] CHEN Z B,ZHOU P, HE Y. Fast integer pel and fractional pel motion estimation for JVT[C]. 6th meeting:Awaji,Japan. JVT-F017,2002.
[3] 畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)-H.264/AVC(第二版)[M].北京:人民郵電出版社,2009.
[4] 陳桂蘭,劉子堅(jiān). 基于H.264的運(yùn)動估計(jì)算法優(yōu)化研究[J].濮陽職業(yè)技術(shù)學(xué)院學(xué)報(bào),2010,23(2):150-153.
[5] Xie Lifen, Huang Chunqing. UMHexagonS search algorithm for fast motion estimation[C]. IEEE, 3rd International conference on ICCRD 2011 3rd Intenational Conference on ICCRD,2011,4:483-487.
[6] LAM C H, PO L M, CHEUNG C H. A novel kite-cross-diamond search algorithm for fast block motion estimation [C]. Proceeding s of 2004 IEEE International Symposium on Circuits and Systems. Canada: IEEE, 2004:729-732.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。