楊春玲 熊光銀 戴超

(華南理工大學 電子與信息學院， 廣東 廣州 510640)

視頻壓縮感知中基于快速搜索的迭代多假設(shè)算法*

楊春玲 熊光銀 戴超

(華南理工大學 電子與信息學院， 廣東 廣州 510640)

針對觀測域和像素域兩階段多假設(shè)預(yù)測重構(gòu)方案在低采樣率時重構(gòu)效果不理想，且對于運動劇烈的序列預(yù)測精度不夠、時間復雜度較高等問題，在兩階段多假設(shè)預(yù)測的基礎(chǔ)上，提出了基于快速搜索的迭代多假設(shè)預(yù)測重構(gòu)算法.該算法利用像素域分塊的靈活性，基于重疊塊在像素域迭代預(yù)測重構(gòu)；針對運動較快的序列，采用十字形聯(lián)合區(qū)域搜索方法以減小大范圍搜索的算法復雜度；同時利用圖像空間相關(guān)性進行幀間/幀內(nèi)自適應(yīng)假設(shè)塊的模式選擇與已有算法相比，文中重構(gòu)算法進一步削弱了塊效應(yīng)，降低了大范圍搜索的運算復雜度，提高了重構(gòu)性能.

視頻壓縮感知；多假設(shè)預(yù)測；假設(shè)塊；像素域；迭代預(yù)測；預(yù)測精度；時間復雜度

在傳統(tǒng)的視頻壓縮信號采集模式中，若想無失真的恢復視頻信號，采樣率必須滿足奈奎斯特采樣定理.Donoho、Candès等[1- 3]提出的壓縮感知(CS)理論打破了傳統(tǒng)采樣率限制，其基本思想是：對于可壓縮信號，在編碼端通過一個不相關(guān)的觀測矩陣采樣得到少量的觀測值，在解碼端利用信號在變換域稀疏表示的先驗信息，通過壓縮感知重構(gòu)算法可以高概率地恢復原信號.

壓縮感知理論提出之后，許多學者不斷深入研究其在視頻采集和壓縮領(lǐng)域的應(yīng)用.文獻[4]提出將視頻幀分割為關(guān)鍵幀和非關(guān)鍵幀，其中關(guān)鍵幀采樣率較高，并在解碼端獨立重構(gòu)以獲得重構(gòu)質(zhì)量較高的圖像幀.非關(guān)鍵幀將與其比較相關(guān)的幀以及相鄰兩端的關(guān)鍵幀作為參考幀進行聯(lián)合重構(gòu).因此對于非關(guān)鍵幀重構(gòu)，如何充分利用幀間相關(guān)性提升重構(gòu)質(zhì)量是研究視頻壓縮感知的關(guān)鍵點，而多假設(shè)預(yù)測方法由于其充分挖掘幀間相關(guān)性信息的特性，逐漸成為視頻壓縮感知中主流方法之一.在多假設(shè)預(yù)測中，關(guān)鍵點是假設(shè)塊的選擇和權(quán)值計算問題.文獻[5- 6]提出對當前幀中的每一個非重疊圖像塊，以歐氏距離為基準在多參考幀中搜尋多個較好的假設(shè)塊，理論分析將多個假設(shè)塊通過相應(yīng)的權(quán)值結(jié)合，得到近似預(yù)測值，并提出了Tikhonov正則項來優(yōu)化求解假設(shè)塊的權(quán)值計算.在上述研究基礎(chǔ)上，文獻[7- 8]分別將I1范數(shù)、I2范數(shù)和權(quán)值向量稀疏性融入到假設(shè)塊權(quán)值求解問題中，不但保證了稀疏性，而且提高了預(yù)測準確性.此外，為了避免相關(guān)性較弱的假設(shè)塊影響重構(gòu)質(zhì)量，文獻[9- 10]均提出需要對假設(shè)塊集合進行篩選，即只保留與當前重構(gòu)塊最相關(guān)的若干匹配塊，從而避免相關(guān)程度較低的匹配塊的干擾，進一步提高對當前幀的預(yù)測精度.但是文獻[5- 8]中假設(shè)塊的選取形式過于單一，相關(guān)性信息利用不充分，于是文獻[9]作者提出了多參考幀多假設(shè)預(yù)測算法(MRMH)，文獻[10]中也提出了擴充更新多假設(shè)塊集合的算法，使得假設(shè)塊的選取有了更多的選擇.

上述算法中都是在觀測域匹配選取假設(shè)塊，假設(shè)塊大小需與采集端分塊大小一致.因此，不可避免地會引起塊效應(yīng).針對此問題，文獻[11]作者提出了兩階段多假設(shè)重構(gòu)算法(2SMHR)，即在觀測域預(yù)測殘差重構(gòu)的基礎(chǔ)上再進行一次像素域預(yù)測及殘差重構(gòu)，由于在像素域的預(yù)測分塊更加靈活，可以有效地消除觀測域非重疊塊預(yù)測引起的塊效應(yīng)，有效地提高了重構(gòu)質(zhì)量.但兩階段多假設(shè)重構(gòu)算法依然存在以下兩方面的問題：在低采樣率時依然存在明顯塊效應(yīng)；對快速運動序列，由于運動估計時搜索范圍的限制，預(yù)測精度不高，導致重構(gòu)性能不高.針對這兩個問題，本研究提出了基于快速搜索的迭代多假設(shè)預(yù)測優(yōu)化算法(IMH)，并通過實驗與現(xiàn)有算法進行了對比.

1 視頻壓縮感知中多假設(shè)預(yù)測

1.1 觀測域多假設(shè)預(yù)測

視頻壓縮感知中多采用分塊觀測[10,12]模式，其基本思想是：將每個視頻幀分成相同B×B大小的子圖像塊，對每一個子塊用高斯隨機觀測矩陣Φ進行觀測：

yi=Φxi

(1)

式中，x的第i列xi為第i個圖像塊的列向量化，Φ為M×B2維的高斯隨機矩陣，y的第i列yi為第i個圖像塊的觀測值，采樣率為M/B2.

(2)

由于MEMC/運動估計是在解碼端進行，擺脫了碼率的限制，文獻[8]提出選取多個假設(shè)塊，用這一組假設(shè)塊的線性組合作為當前塊的預(yù)測，即

(3)

(4)

式中：H為全搜索得到的假設(shè)塊列矢量集合組成的矩陣，w為相應(yīng)假設(shè)塊權(quán)值集合組成的向量.由于當前塊觀測值y的維度M較小，因此一般情況下，假設(shè)塊個數(shù)滿足k?M，故，為不定解問題(式(4))添加Tikonov正則約束項進行權(quán)值求解，如式(5)所示.

(5)

其中，

Γ=diag(‖yi-ΦH1‖2,…,‖yi-ΦHi‖2,…,

‖yi-ΦHk‖2)

(6)

其中,Hi為第i個假設(shè)塊的列向量化，λ為常數(shù)，并可得權(quán)值向量的閉式解：

w=((ΦH)T(ΦH)+λΓTΓ)-1(ΦH)Tyi

(7)

多假設(shè)預(yù)測與單假設(shè)預(yù)測對比，視頻幀重構(gòu)質(zhì)量得到提升.上述算法是在觀測域選取假設(shè)塊，預(yù)測幀分塊被局限為非重疊分塊，這將導致預(yù)測幀塊效應(yīng)明顯.針對此問題，文獻[11]提出在觀測域預(yù)測的基礎(chǔ)上，在像素域進行多假設(shè)預(yù)測過程，以彌補觀測域預(yù)測的不足.

1.2 像素域多假設(shè)預(yù)測

(8)

由于在像素域預(yù)測分塊可以重疊，充分利用這一點，基于重疊塊在像素域預(yù)測，可以進一步降低預(yù)測幀的塊效應(yīng)，得到的殘差信號更加稀疏，繼而提高視頻重構(gòu)質(zhì)量.

2 基于快速搜索的迭代多假設(shè)預(yù)測優(yōu)化算法——IMH

在文獻[11]提出的兩階段預(yù)測重構(gòu)算法(2SMHR)的基礎(chǔ)上，本研究提出了基于快速搜索的迭代多假設(shè)預(yù)測算法(IMH)，其算法結(jié)構(gòu)如圖1所示.

相對于2SMHR 算法，本研究算法提出3點改進方案：①提出了像素域的多次迭代預(yù)測方法及迭代終止條件，以提高低采樣率時的預(yù)測重構(gòu)性能；②提出了一種用于假設(shè)塊匹配的快速搜索算法，對于運動劇烈的序列，在保證重構(gòu)質(zhì)量的前提下，大大減少了算法的復雜度；③在假設(shè)塊匹配過程中增加了幀內(nèi)假設(shè)塊選擇，提出了自適應(yīng)假設(shè)塊選擇模式，以提高在前后參考幀中得不到較好假設(shè)塊時的預(yù)測性能.

圖1 基于快速搜索的迭代多假設(shè)預(yù)測算法框架

2.1 像素域迭代預(yù)測

在2SMHR算法中，其在觀測域預(yù)測重構(gòu)后增加了像素域預(yù)測重構(gòu)步驟，對視頻重構(gòu)質(zhì)量提升較高.但對于低采樣率情況，重構(gòu)質(zhì)量還相對較差，文中通過深入研究，在2SMHR基礎(chǔ)上提出了像素域多次迭代預(yù)測重構(gòu)算法，進一步提升了視頻序列的重構(gòu)性能.具體步驟如下：

步驟1 像素域多假設(shè)預(yù)測.第k次迭代利用上一次的重構(gòu)結(jié)果(若是首次迭代則利用觀測域多假設(shè)預(yù)測重構(gòu)結(jié)果)，對每個重疊圖像塊在多個參考幀中選取n個最優(yōu)假設(shè)塊集合，記為Hk，通過式(9)求解權(quán)值向量wk：

(9)

2.2 區(qū)域快速搜索方案

在視頻壓縮感知多假設(shè)預(yù)測算法中，假設(shè)塊的獲取至關(guān)重要，尤其對于劇烈運動的序列，較大的搜索范圍可以匹配到較好的假設(shè)塊，但同時也帶來了巨大的計算負擔.因此本研究基于傳統(tǒng)視頻編碼中非對稱十字形搜索方案[14]，針對劇烈運動序列提出了快速搜索方案，以降低快速運動序列匹配塊搜索的計算復雜度，其步驟如下.

初步搜索：以當前圖像塊為中心的非對稱十字區(qū)域內(nèi)間隔s像素點搜索當前圖像塊的最佳匹配塊.

聯(lián)合搜索：分別以當前圖像塊位置和步驟1搜索到的最佳匹配塊位置為中心，在較小范圍內(nèi)逐點匹配搜索，得到多假設(shè)匹配塊組.

圖2中十字形陰影區(qū)域為初步搜索范圍，區(qū)域1為以當前圖像塊為中心的搜索區(qū)域，區(qū)域2為以最佳匹配塊為中心的搜索區(qū)域，R表示為十字搜索區(qū)域半徑，r為區(qū)域1和區(qū)域2的搜索區(qū)域半徑.

圖2 搜索區(qū)域示意圖

2.3 自適應(yīng)假設(shè)塊模式選擇

由于視頻序列中場景變化的不確定性，在當前幀中可能會出現(xiàn)新的圖像塊信息[12].對這些新信息，無法在參考幀中找到與其較匹配的假設(shè)塊.此時若仍利用參考幀中得到的次優(yōu)匹配塊，則可能無法達到像素域增強預(yù)測的目的.對于這些圖像塊，文中提出利用圖像空間相關(guān)性在當前幀中搜索并篩選最優(yōu)假設(shè)塊，稱之為幀內(nèi)模式.基于此，文中提出了自適應(yīng)假設(shè)塊模式選擇思路，即利用閾值TSSIM自適應(yīng)選擇圖像塊的多假設(shè)預(yù)測模式(幀間預(yù)測(Inter-mode)/幀內(nèi)預(yù)測模式(Intra-mode)).利用結(jié)構(gòu)相似度SSIM(i,j)作為當前圖像塊xi與第j個假設(shè)塊的匹配準則，若滿足式(10)則選擇幀間預(yù)測模式，反之，選擇幀內(nèi)預(yù)測模式.

max {SSIM(i,j),(j∈[1,n])}>TSSIM

(10)

3 實驗結(jié)果與分析

3.1 迭代多假設(shè)預(yù)測算法仿真實驗及性能分析

采用5組QCIF格式的標準視頻序列foreman、hall、coastguard、football和soccer的前129幀(GOP=8)進行實驗分析，實驗結(jié)果示于表1和圖3.在實驗中，像素域重疊塊分塊大小b=8；像素域多假設(shè)預(yù)測塊個數(shù)n=8；關(guān)鍵幀采樣率0.7，非關(guān)鍵幀采樣率f為0.1；自適應(yīng)幀間幀內(nèi)多假設(shè)模式選擇閾值TSSIM=0.7；搜索窗Winter=16，Wintra=8.

表1 不同采樣率下各算法的PSNR對比

Table 1 Comparison of PSNR of different algorithm with diffe-rent sampling rates

實驗序列重構(gòu)算法PSNR/dBf=0.05f=0.1f=0.15foremanMRMH31.0632.9034.322SMHR31.6233.6535.19IMH32.8035.0736.56hallMRMH30.5532.0933.342SMHR31.1332.7534.01IMH33.0234.3635.05coastguardMRMH27.3828.5629.392SMHR27.7929.0429.93IMH28.5229.8730.73footballMRMH27.0728.8729.932SMHR27.4629.2430.28IMH28.0129.5830.54soccerMRMH28.6631.2432.862SMHR29.1331.8733.51IMH30.1132.6434.07

由表1可見，不同序列在非關(guān)鍵幀的采樣率較低(0.05～0.15)的情況下，文中提出的迭代多假設(shè)算法(IMH)相比MRMH與2SMHR算法重構(gòu)質(zhì)量普遍提升了0.5～1.5 dB；但是，對比運動比較緩慢的序列(hall序列)與運動比較劇烈的視頻序列(football，soccer)發(fā)現(xiàn)，運動比較緩慢的序列重構(gòu)質(zhì)量提升更加明顯，這是因為對于運動緩慢的序列，多假設(shè)的運動估計和運動補償會更加精準.由圖3顯示的foreman局部放大圖中可以看出對于運動程度較大的嘴唇周圍部分可見2SMHR的塊效應(yīng)明顯，而IMH算法在對foreman視頻幀在像素域進行迭代預(yù)測后，能夠有效消除塊效應(yīng)，提高重構(gòu)質(zhì)量.

圖3 “foreman”第59幀重構(gòu)效果(局部)

Fig.3 Reconstruction effect of the 59th frame of foreman sequence(partial)

3.2 IMH算法性能實驗

利用實驗仿真，對比了基于快速搜索的迭代多假設(shè)預(yù)測算法與全搜索的多假設(shè)預(yù)測算法的性能，F(xiàn)S表示全搜索(FS(32,32)表示搜索窗W=32)，“IS”表示文中的優(yōu)化搜索，IS(R,r,s)表示初步搜索非對稱十字形估計區(qū)域，如圖2所示，其中R表示初步搜索窗水平方向半徑，r表示十字重疊區(qū)域半徑，s表示匹配假設(shè)塊的稀疏搜索距離.

表2給出了soccer和football兩個運動比較劇烈的序列的前129幀的實驗結(jié)果，其中，時間表示重構(gòu)時平均每幀所用時間，包括預(yù)測和重構(gòu)過程.由表2可知，文中所提快速算法在保持重構(gòu)性能的條件下，soccer和football序列重構(gòu)時間明顯下降，這是因為快速搜索方案由大范圍稀疏搜索到小范圍全搜索的模式，即通過大范圍稀疏搜索摒棄與當前塊并不相關(guān)的區(qū)域，然后通過小范圍全搜索進行精確匹配，有效地降低了預(yù)測過程中匹配塊搜索算法復雜度.這對于視頻解碼來說減少了許多不必要的負擔.

表2 不同匹配塊搜索方案重構(gòu)時間復雜度及性能對比

3.3 與現(xiàn)有最優(yōu)視頻壓縮感知算法性能對比分析

將本算法性能與現(xiàn)有最優(yōu)的預(yù)測殘差重構(gòu)視頻壓縮感知算法(MH-BCS-SPL[11]，MS-wEnet[7]， Up-Se-AWEN-HHP[15])做對比實驗，仿真結(jié)果如表3所示.實驗中使用和對比文獻中完全相同的條件，標準30Hz CIF格式序列前89幀的亮度分量進行實驗.在采樣端，用正交高斯隨機觀測矩陣分塊采樣，非重疊塊分塊大小B=16，序列分組GOP=8，關(guān)鍵幀采樣率0.7，非關(guān)鍵幀采樣率0.1～0.5.在重構(gòu)端，關(guān)鍵幀使用MH-BCS-SPL算法獨立重構(gòu)，非關(guān)鍵幀假設(shè)塊搜索窗W=15，非關(guān)鍵的預(yù)測殘差信號使用BCS-SPL-DDWT[13]算法重構(gòu).

在本算法中，像素域重疊塊分塊大小b=8；像素域預(yù)測多假設(shè)塊個數(shù)n=8；自適應(yīng)幀間幀內(nèi)多假設(shè)模式選擇閾值TSSIM=0.7，搜索窗.Winter=16,Wintra=8.

表3 不同序列前89幀各算法重構(gòu)平均PSNR

從表3中可以看出，IMH與MH-BCS-SPL、MS-wEnet、Up-Se-AWEN-HHP算法相比，其重構(gòu)質(zhì)量均有明顯提升，foreman、hall、coastguard、mother-daughter在非關(guān)鍵幀為0.1的低采樣率情況下提高了1～3.5 dB，尤其是對于背景運動較簡單的hall序列，由于其紋理信息較多的圖像特征，IMH算法與Up-Se-AWEN-HHP算法相比，提升更為明顯，從表3中發(fā)現(xiàn)，隨著非關(guān)鍵幀采樣率的提升，IMH與Up-Se-AWEN-HHP的重構(gòu)性能差距越來越小.這是因為在高采樣率時，視頻幀已經(jīng)被高質(zhì)量重構(gòu)，無很明顯的塊效應(yīng)，此時在像素域進行迭代多假設(shè)預(yù)測性能的提升就不太明顯了.

4 結(jié)論

在基于多參考幀的多假設(shè)預(yù)測殘差重構(gòu)算法的基礎(chǔ)上提出了基于快速搜索的迭代多假設(shè)預(yù)測重構(gòu)算法(IMH)，即在觀測域多假設(shè)殘差重構(gòu)的基礎(chǔ)上，在像素域基于重疊分塊進行增強的多假設(shè)預(yù)測殘差重構(gòu)循環(huán)迭代，逐步消除塊效應(yīng)，提升視頻重構(gòu)質(zhì)量，并且提出了相關(guān)的自適應(yīng)假設(shè)塊模式選擇.通過對比仿真實驗可知，IMH算法相對于其他視頻壓縮感知重構(gòu)算法性能都有所提升，在較低采樣率時性能提升更為明顯；與現(xiàn)有最優(yōu)視頻壓縮感知算法Up-Se-AWEN-HHP相比，IMH算法最大提升PSNR可達2.1dB；另外，對于快速運動序列，需要大范圍搜索才能得到更好的假設(shè)塊，在這種情況下，IMH算法有效地降低了搜索算法的復雜度.這些實驗結(jié)果表明了文中提出的IMH算法具有更加優(yōu)越的視頻壓縮重構(gòu)性能.

[1] DONOHO D L. Compressed sensing [J].IEEE Transactions on Information Theory,2006,52(4):1289- 1306.

[4] KANG L W,et al.Distributed compressive video sensing [C]∥IEEE International Conference on Acoustics,Speech & Signal Processing.Taipei:IEEE Computer Socie-ty,2009:1169- 1172.

[5] CHEN C,TRAMEL E W,Fowler J E.Compressed-sensing recovery of images and video using multihypothesis predictions [C]∥Signals,Systems and Computers.Pacific Grove:IEEE,2011:1193- 1198.

[6] ZHU J,CAO N,Meng Y.Adaptive multihypothesis prediction algorithm for distributed compressive video sensing [J].International Journal of Distributed Sensor Networks,2013,2013(7):718- 720.

[7] JIAM C,CHEN Y,DONG Q,et al.An elastic net-based hybrid hypothesis method for compressed video sensing [J].Multimedia Tools & Applications,2013,74(6):1- 24.

[8] AZGHANI M,KARIMI M,MARVASTI F.Multi-hypothesis compressed video sensing technique [J].IEEE Transactions on Circuits & Systems for Video Technology,2015,26(4):627- 635.

[9] 楊春玲，歐偉楓.視頻壓縮感知中基于多參考幀的最優(yōu)多假設(shè)預(yù)測算法研究 [J].華南理工大學學報(自然科學版)，2016,44(1):1- 8.

YANG Chun-ling,OU Wei-feng.Multi-reference frames-based optimal multi-hypothesis prediction algorithm for compressed video sensing [J].Journal of South China University of Technology (Natural Science Edition),2016,44(1):1- 8.

[10] GAN L.Block compressed sensing of natural images [C]∥International Conference on Digital Signal Processing. Wales：IEEE,2007:403- 406.

[11] OU W F,YANG C L,Li W H,et al.A two-stage multi-hypothesis reconstruction scheme in compressed video sensing [C]∥IEEE International Conference on Image Processing.Phoenix：IEEE,2016:2494- 2498.

[12] FOWLER J E,MUN S,TRAMEL E W.Block-based compressed sensing of images and video [J].Foundations & Trends & in Signal Processing,2012,4:297- 416.

[13] MUN S,FOWLER J E.Block compressed sensing of ima-ges using directional transforms [C]∥Proceedings of the 16th IEEE International Conference On Image Processing.Cairo：IEEE，2009:2985- 2988.

[14] PAN Z,KWONG S,XU L,et al.Predictive and distribution-oriented fast motion estimation for H.264/AVC [J].Journal of Real-Time Image Processing,2012,9(4):597- 607.

[15] KUO Y,WU K,CHEN J.A scheme for distributed compressed video sensing based on hypothesis set optimization techniques [J].Multidimensional Systems & Signal Processing,2017:28(1):129- 148.

FastSearching-BasedIterativeMulti-HypothesisAlgorithmAppliedtoCompressedVideoSensing

YANGChun-lingXIONGGuang-yinDAIChao

(School of Electronic and Information Engineering, South China University of Technology, Guangzhou 510640, Guangdong, China)

As the two-stage multi-hypothesis reconstruction (2sMHR) for the prediction in both measurement and pixel domains is of low reconstruction quality at low subrate as well as low prediction accuracy and high computational complexity for fast movement sequences, on the basis of 2sMHR scheme, a novel iterative multi-hypothesis (IMH) prediction reconstruction algorithm utilizing fast searching technology is proposed. This algorithm utilizes the flexibility of block partition in pixel domain to conduct overlapping block-based iterative multi-hypothesis prediction, and adopts the scheme of jointing cross-shaped and regional searching to lessen matching complexity in large-range searching for fast sequences. In addition, by utilizing the space correlation in images, an adaptive interframe/intraframe hypothesis-block selecting scheme is presented. In comparison with the existing algorithms, the proposed IMH prediction reconstruction algorithm suppresses the prediction block effect, reduces the computational complexity for large-range searching and improves the video reconstruction quality.

compressed video sensing; multi-hypothesis prediction; hypothesis block; pixel domain; iteration prediction; prediction accuracy; time complexity

2016- 07- 22

國家自然科學基金資助項目(61471173);廣東省自然科學基金資助項目(2016A030313455)

*Foundationitems: Supported by the National Natural Science Foundation of China(61471173) and the Natural Science Foundation of Guangdong Province(2016A030313455)

楊春玲(1970-)，女，博士，教授，主要從事圖像/視頻壓縮研究.E-mail:eeclyang@scut.edu.cn

1000- 565X(2017)07- 0107- 06

TP 919.8

10.3969/j.issn.1000-565X.2017.07.015