張?濤，陳有志，雷志春

?

基于時空特性自適應插值的混合去隔行方法

張?濤1，陳有志1，雷志春2

(1. 天津大學電氣自動化與信息工程學院，天津 300072；2. 天津大學微電子學院，天津 300072)

為了實現(xiàn)隔行掃描到逐行掃描的視頻格式轉換，需要使用去隔行插值技術．針對傳統(tǒng)運動補償插值算法的誤差傳遞、運動估計不準、計算復雜度較高等缺陷，提出一種基于奇偶一致性搜索的運動補償去隔行方法；針對傳統(tǒng)基于邊緣方向插值算法的邊緣定位不準等缺陷，提出一種基于梯度輔助的場內多方向插值方法．將上述兩種方法與場合并插值和行平均插值相結合，提出一種新的基于時空特性自適應插值的混合去隔行方法．該方法能夠利用視頻中的時空特性，有效地解決傳統(tǒng)去隔行算法因運動估計錯誤和邊緣定位不準導致的插值失真等問題．實驗結果表明，與傳統(tǒng)去隔行算法相比，該方法能夠在降低總體計算復雜度的情況下獲得0.7,dB左右的PSNR提升．

時空特性；奇偶一致性；梯度輔助；去隔行

在視頻信號的傳輸過程中，為了減少傳輸帶寬，通常采用隔行掃描的方式處理視頻信號，例如主流電視廣播系統(tǒng)NTSC、PAL和SECAM等[1]．但是隔行掃描會造成鋸齒現(xiàn)象、邊緣閃爍和場間混疊等視覺上的問題．為了解決這些問題，并且填補缺失的像素，人們提出了各種各樣的去隔行算法[2-11]．它們可以粗略地分為3類：時域插值算法、空域插值算法和時空混合插值算法．

時域插值算法一般是利用場間信息進行去隔行插值，主要有場合并、場平均、運動補償?shù)人惴?，其中場合并、場平均算法運算簡單，在靜止區(qū)域表現(xiàn)良好，但在運動區(qū)域會產生羽化等不良現(xiàn)象[2]．運動補償算法是一種比較特殊的時域插值算法，它通過場間信息預測出物體的運動軌跡，然后沿著運動軌跡進行像素插補，是目前性能較好的一種去隔行算法，但是這類算法容易受到運動矢量誤差的干擾而導致重建圖像質量低下，另外還存在誤差傳遞和計算復雜度較高等缺陷[2-3]．

空域插值算法是利用場內信息進行去隔行插值，主要包括行平均、行復制、基于邊緣方向插值等算法．其中行平均和行復制算法結構簡單，應用范圍較廣，但容易造成鋸齒、褶皺等插補缺陷．而基于邊緣方向插值算法則利用人眼對物體邊緣敏感的特性，沿著邊緣方向進行插值，較好地保護了邊緣的連續(xù)性和銳利度，從而明顯增加圖像的主觀質量效果，例如ELA[2]、MELA[4]和FELA[5]等算法．但是這些算法基本都是通過像素值相似度信息預測邊緣，由于使用的信息較少，導致邊緣方向預測不準確．

時空混合插值算法利用場間信息和場內信息進行去隔行插值，主要表現(xiàn)形式是結合時域插值算法和空域插值算法，形成一個混合的去隔行算法．目前一般是通過運動檢測或者權值來結合時域插值和空域插值算法，比如Trocan等[6]使用運動檢測結合運動補償插值、基于邊緣方向插值和行平均插值等算法，Chang等[7]利用權值自適應結合場內插值算法和運動補償插值算法．這些算法取得了一定的去隔行效果，但是結合過程中的判決較為復雜，總體的計算復雜度還需要降低．

鑒于以上問題，本文提出一種基于時空特性自適應插值的混合去隔行方法．其中對運動補償算法和基于邊緣方向插值算法進行改進，并且通過運動檢測和邊緣檢測進行算法融合，較好地利用視頻中的時空特性保護圖像邊緣的銳利度和連續(xù)性，抑制因運動估計不準而造成插值失真現(xiàn)象的發(fā)生．

1?基于奇偶一致性搜索的運動補償場間插值

傳統(tǒng)的運動補償去隔行算法大部分使用塊匹配、全搜索的方式進行插值，同時參考幀一般會選取之前的重建圖像，但是這樣會產生誤差傳遞、運動估計不準、計算復雜度較高等問題，因而也嚴重影響了去隔行性能，比如時域遞歸(time recursive，TR)去隔行算法[2]等．本文針對這些問題提出一種基于奇偶一致性搜索的運動補償場間插值算法．

在該算法中，選取與當前待插值場相鄰的前一個重建圖像為參考幀，同時選取大小為4像素×3像素的待匹配塊和16像素×15像素的搜索窗，采用奇偶一致性搜索方式進行搜索．其中如圖1所示，上下相鄰待匹配塊共用一行．圖2是匹配示意圖，當18與18最接近時，就認為該匹配塊是最佳匹配塊，那么待匹配塊中14就由14進行填充，進而獲得運動補償?shù)牟逯?，其中，參考塊與待匹配塊接近程度用式(1)表示，即當SAD值最小時就認為對應的參考塊是最佳匹配塊．

圖2?塊匹配過程示意

針對搜索過程，本文引入了奇偶一致性搜索的概念．本文中的奇偶一致性是指參考塊與待匹配塊之間相對應像素點都處在原始圖像中的奇行或偶行，而滿足該要求的搜索過程稱之為奇偶一致性搜索，如圖2所示，參考塊中的已插值像素18和待匹配塊的原始像素18同屬于原始圖像中的奇行或偶行．部分實驗結果表明，在這種情況下，參考塊與待匹配塊之間的相關性比不符合奇偶一致性的參考塊與待匹配塊之間的相關性更大．相比較全搜索，奇偶一致性搜索在計算復雜度上減少了50%,，針對部分測試序列，PSNR提升了0.2,dB左右．這是因為全搜索方法搜索出來的最佳匹配塊是SAD值最小的參考塊，但這個塊可能不滿足奇偶一致性特征，因而獲得的運動補償值可能并不準確．

雖然搜索過程考慮了奇偶一致性，但是仍然存在因運動估計錯誤而導致運動補償插值失真的情況．針對這一問題，采用4抽頭的中值濾波在一定程度上抑制這種情況的發(fā)生．傳統(tǒng)上，針對運動補償失誤所使用的中值濾波一般是3抽頭，即運動補償值和待插值位置的上下最相鄰的2個像素值[2]，比如使用3抽頭中值濾波的時域遞歸去隔行算法(TR_MID)[2].因為最近的相鄰像素具有最高的相似性，從而使得行平均算法具有較好的客觀性能[8]，因此本文考慮行平均算法的插值結果，采用4抽頭的中值濾波．具體如式(2)所示，其中MC(，)是上述運動補償獲得的插值，(－1，)和(＋1，)是該插值位置垂直方向上最相鄰的2個像素值，LA(，)是利用行平均算法獲得的該點的插值，(，)是最終的插值結果．

?????(2)

2?基于梯度輔助的場內多方向插值

傳統(tǒng)的基于邊緣方向插值算法主要是通過像素值相似性來確定邊緣方向，可以大致分為兩類：基于像素點差值求邊緣方向和基于像素塊差值求邊緣方向．基于像素點差值求邊緣方向靈敏度高，但易于受到噪聲干擾，比如ELA、EFLA等；基于像素塊差值求邊緣方向對噪聲有較強的抵抗力，但針對一些窄邊緣卻難以檢測出來，比如MELA、HEDI[9]等．因此，近幾年有一些新的算法引入了相鄰像素之間的梯度相似性信息進行邊緣預測，取得了較好的去隔行效果，比如FDD[10]、FSID[8]、GGI[11]等．本文結合梯度信息與像素值相似性信息，提出一種基于梯度輔助的場內多方向插值方法．

在本方法中，使用像素值相似度信息和梯度信息預測邊緣方向．如圖3所示，本文先使用相鄰像素之間的像素值相似度信息確定大致的邊緣方向．其中，和由式(3)計算所得，分別表示鈍角方向和銳角方向的像素塊絕對差值和．如果＞，那么邊緣方向的角度是銳角，在此基礎上，若利用梯度的相位信息求得邊緣方向的角度為鈍角，那么使用該角的補角；如果＜，那么邊緣方向的角度是鈍角，在此基礎上，若利用梯度的相位信息求得邊緣方向的角度為銳角，那么使用該角的補角；如果＝，那么中心待插值像素采用行平均的方法進行插值．在確定了大致的邊緣方向之后，利用梯度信息中的相位信息進行更小范圍的邊緣方向預測．本文使用的梯度算子是sobel算子，如式(4)所示．

圖3?像素值相似度信息確定大致的邊緣方向

???(3)

???(4)

???(5)

因此利用梯度信息中的相位信息求得的邊緣方向dir＝tan，然后取與方向dir最接近的數(shù)，作為最終的插值方向．其中，如圖4所示，插值方向∈{-5，-4，-3，-2，-1，-1/2，0，1/2，1，2，3，4，5}．如果超過這個集合的范圍就認為插值方向與水平方向接近平行，那么此時就使用行平均算法處理該種情況．根據(jù)最終求得的插值方向，由式(6)獲得最終的插值結果．

???(6)

圖4?插值方向示意

3?自適應插值的混合去隔行方法

時域插值算法和空域插值算法一般是通過運動檢測或者權值進行結合，比如文獻[7]提出使用權值自適應地結合多種時域和空域插值算法，但是權重計算異常復雜，往往難以很好地結合這些算法的優(yōu)點，有時候會導致總體算法性能的降低．鑒于這種情況，本文利用運動檢測和邊緣檢測對圖像進行劃分，自適應結合基于奇偶一致性搜索的運動補償場間插值、場合并插值、基于梯度輔助的場內多方向插值和行平均插值等算法．

3.1?運動檢測

本文采取的運動檢測方法通過比較當前圖像和前一個圖像對應位置大小為4像素×3像素的塊之間差值diff確定圖像不同區(qū)域的運動情況．具體如式(7)所示．

(7)

式中：表示當前待測的4像素×3像素區(qū)域；th_low和th_high為設定的閾值．

3.2?邊緣檢測

本文采用的邊緣檢測方法是比較閾值與當前像素點的水平方向梯度G和垂直方向梯度G之間的大小，來確定當前像素是否處于邊緣區(qū)域．具體如式(8)所示．

???(8)

式中：表示當前待測像素點；TH為設定的閾值．

3.3?自適應插值

通過上述的運動檢測和邊緣檢測對圖像進行劃分，針對不同區(qū)域使用不同的去隔行方法，因而自適應地結合了時域插值和空域插值的優(yōu)點．本文主要把圖像分為3類：靜止區(qū)域、運動幅度較小區(qū)域、運動幅度較大區(qū)域．針對靜止區(qū)域使用場合并的方式進行插值，提高圖像的垂直分辨率，恢復視頻圖像原有的幀結構．針對運動幅度較小區(qū)域，使用基于奇偶一致性搜索的運動補償場間插值方法進行插值，使得該區(qū)域的插補像素值更加精確．針對運動幅度較大區(qū)域，通過邊緣檢測再一次劃分為邊緣區(qū)域和平滑區(qū)域，邊緣區(qū)域使用基于梯度輔助的場內多方向插值方法進行插值，較好地保護物體邊緣的連續(xù)性和銳利度，平滑區(qū)域使用客觀性能較好的行平均算法進行插值，降低總體算法的計算復雜度．如圖5所示．

圖5?本文所提算法的流程

4?實驗結果及討論

本節(jié)從視頻質量評價和計算復雜度兩個方面分析本文所設計的混合去隔行算法的性能，其中參與比較的傳統(tǒng)去隔行算法有LA、ELA、MELA、FDD、TR_MID．參與比較的典型測試視頻序列如下：352像素×288像素(akiyo)，720像素×576像素(clown、horsecab、rally、splash)，1,280像素×720像素(sailormen、spincalendar)，1,920像素×1,080像素(kimono)．實驗使用C++語言，在VS2010上進行，CPU為Intel i3-4160，3.60,GHz．表1是針對這些典型測試視頻序列，各個去隔行算法獲得的視頻平均PSNR值．

由表1可以發(fā)現(xiàn)，本文算法相比較這幾個傳統(tǒng)的經(jīng)典去隔行算法，在平均PSNR上提升0.7,dB左右，展現(xiàn)了較好的去隔行效果．其中，相比較使用中值濾波的運動補償插值算法TR_MID，本方法獲得了0.7,dB左右的PSNR提升；相比較使用梯度信息插值的FDD算法，本方法獲得將近0.8,dB左右的PSNR提升；而比較傳統(tǒng)的基于邊緣方向插值算法，本方法則獲得1,dB左右的PSNR提升．這些說明使用像素值相似性和梯度信息結合的方式進行邊緣預測是有效的，同時也說明了本文算法能夠較好地融合時域插值和空域插值的優(yōu)點．

圖6是各種去隔行算法對測試序列rally處理后所得結果的部分截圖，從這些圖中得出的初步主觀感受可以發(fā)現(xiàn)，ELA、MELA、FDD和TR_MID等算法由于不正確的邊緣估計和運動估計，導致車身邊緣出現(xiàn)了褶皺問題．而在本文算法的效果中，物體的邊緣和原圖基本一致，并沒有出現(xiàn)褶皺現(xiàn)象．這說明本文算法的運動估計和邊緣處插值方向的估計更加準確，基本保持了物體邊緣的連續(xù)性，因而也在一定程度上提升了圖像的清晰度和銳利度．

表1?各種去隔行算法的平均PSNR比較

Tab.1?Comparison of average PSNR of different de-interlacing algorithms

圖6?各種去隔行算法的主觀效果比較

關于計算復雜度，表2是各種去隔行算法處理每場圖像所需平均時間的比較．從表中數(shù)據(jù)可得，對使用到的所有測試視頻序列，LA、ELA、MELA這3種算法所需的平均處理時間都要比其他3種算法所需平均處理時間短，展現(xiàn)出計算復雜度較低的特點．而本文所提算法在處理akiyo這類包含較多靜止場景內容的測試視頻序列時，所需平均處理時間也要短于FDD和TR_MID算法的平均處理時間，同樣具有計算復雜度較低的特點．在處理horsecab這類包含較多運動場景內容的測試視頻序列時，本文所提算法需要的平均處理時間要比FDD算法的平均處理時間稍高，但是遠少于TR_MID算法的平均處理時間，這也展示本文所提算法的計算復雜度不是很高的特點．總體上，與這幾個傳統(tǒng)的去隔行算法相比，本文所提算法的計算復雜度適中．

表2?各種去隔行算法處理每場圖像所需平均時間比較

Tab.2?Comparison of average computation time of different de-interlacing algorithms

5?結?語

本文通過運動檢測和邊緣檢測對圖像的內容進行劃分，自適應地結合時域插值算法(基于奇偶一致性搜索的運動補償場間插值、場合并插值)和空域插值算法(基于梯度輔助的場內多方向插值、行平均插值)．其中基于奇偶一致性搜索的運動補償場間插值算法考慮了參考塊與待匹配塊之間對應像素點的奇偶一致性關系，基于梯度輔助的場內多方向插值算法考慮了像素值相似性信息和梯度信息．這些措施降低了算法的計算復雜度，同時在一定程度上避免了因為錯誤的運動矢量和不正確的邊緣方向造成的插補問題，表現(xiàn)了比傳統(tǒng)算法更優(yōu)良的性能．但是，在算法中像素值相似性信息和梯度信息的結合使用還有改進的空間，另外運動檢測和邊緣檢測的性能還可進一步加強．

［1］ Lee K，Lee C. High quality spatially registered vertical temporal filtering for deinterlacing[J].，2013，59(1)：182-190.

［2］ Haan G D，Bellers E B. Deinterlacing：An overview[J].，1998，86(9)：1839-1857.

［3］ Mahvash Mohammadi H，Savaria Y，Langlois J M P. Enhanced motion compensated deinterlacing algorithm [J].，2012，6(8)：1041-1048.

［4］ Kim W，Jin S，Jeong J. Novel intra deinterlacing algo-rithm using content adaptive interpolation[J].，2007，53(3)：1036-1043.

［5］ Brox P，Baturone I，Sanchez-Solano S，et al. Edge-adaptive spatial video de-interlacing algorithms based on fuzzy logic[J].，2014，60(3)：375-383.

［6］ Trocan M，Mikovicova B，Zhanguzin D. An adaptive motion-compensated approach for video deinterlacing[J].，2012，61(3)：819-837.

［7］ Chang J，Kim Y D，Shin G S，et al. Adaptive arbitration of intra-field and motion compensation methods for de-interlacing[J].，2009，19(8)：1214-1220.

［8］ Chen X，Jeon G，Jeong J. Filter switching interpolation method for deinterlacing[J].，2012，51(10)：2002-2009.

［9］ Fan Z. Hierarchical edge-directed interpolation for de-interlacing[C]// 2011Berlin，Germany，2011：249-250.

［10］ Jin S，Kim W，Jeong J. Fine directional de-interlacing algorithm using modified sobel operation[J].，2008，54(2)：587-862.

［11］ Zhang H，Rong M. Deinterlacing algorithm using gradient guided interpolation and weighted average of directional estimation[J].，2015，9(6)：450-460.

(責任編輯：王曉燕)

Hybrid De-Interlacing Algorithm with Adaptive Interpolation Based on Temporal-Spatial Characteristics

Zhang Tao1，Chen Youzhi1，Lei Zhichun2

(1. School of Electrical and Information Engineering，Tianjin University，Tianjin 300072，China；2. School of Microelectronics，Tianjin University，Tianjin 300072，China)

De-interlacing is a key technology in the process of converting a interlaced video into a progressive video．But the traditional motion compensated de-interlacing algorithms often suffer from some troubles，such as error propagation，inaccurate motion estimation and high computation complexity．Thus，a motion compensated de-interlacing algorithm based on parity consistency search was proposed．In addition，in view of the problem that the edge direction wasn’t detected exactly in the traditional de-interlacing algorithms based on the edge direction，a multi-direction interpolation algorithm based on gradient-assistance was proposed in this paper．Finally，the above proposed de-interlacing algorithms，field merging interpolation and line averaging interpolation were merged adaptively to form a hybrid de-interlace with adaptive interpolation based on temporal-spatial characteristics．Making use of the temporal-spatial characteristics of the video，the finally proposed algorithm effectively solves the problems that the wrong motion estimation and the inaccurate edge direction resulted in mistaken interpolation．The experimental results show that compared with traditional de-interlacing algorithms，the proposed algorithm could offer 0.7,dB PSNR gain under low computational complexity.

temporal-spatial characteristics；parity consistency；gradient-assistance；de-interlacing

10.11784/tdxbz201611010

TP391

A

0493-2137(2018)01-0073-06

2016-11-04；

2017-04-24.

張?濤（1975—??），男，博士，副教授．

張?濤，zhangtao@tju.edu.cn.

天津市科技支撐計劃重點資助項目(16YFZCGX00760)．

the Key Science and Technolgoy Support Program of Tianjin，China(No.,16YFZCGX00760).