非迭代收縮多方向預測的空域錯誤隱藏算法

王凱巡,劉 浩,2

(1.東華大學 信息科學與技術學院，上海 201620； 2.上海交通大學 人工智能教育部重點實驗室，上海 200240)

圖像通信按光柵掃描順序執行分塊編解碼，在傳輸過程中存在塊丟失現象.信宿端的錯誤隱藏不需要對信源端進行任何改變，在恢復丟失像素的過程中完全不需要信源端的參與，屬于圖像通信的一類后處理技術，由于不需要增加編碼冗余或改變碼流結構而受到廣泛關注[1-2].大多數自然圖像具有較強的空域相關性，空域錯誤隱藏算法需要通過可用信息來高效地預測丟失像素，提高可視質量[3].

快速的空域錯誤隱藏算法均采用了低復雜度的線性插值機制，基本原理是利用已正確接收的鄰域像素來進行加權預測.作為圖像通信廣泛使用的空域錯誤隱藏算法，高級視頻編碼(Advanced Video Coding,AVC)插值算法[4]利用受損塊的鄰近像素進行雙線性插值，通過計算上、下、左、右4個鄰近像素的加權平均值來估計丟失像素，其權重與像素間的距離成反比.AVC算法難以恢復邊緣較多或紋理較豐富的圖像區域.內容自適應劃分(Content Adaptive Division,CAD)插值算法[5]利用邊緣檢測算子來評估受損塊的邊緣強度，根據強度大小將受損塊分成三種類型：平滑塊、紋理塊和邊緣塊，分別選取相應的插值方式進行恢復，其計算復雜度較低.作為對象移除應用的典型技術，耗時的圖像補全機制主要關注視覺主觀效果，但在松散的時間約束下也有學者將其用于解決錯誤隱藏問題，Chung等[6]提出了一種聯合圖像補全和線性插值(Hybird Inpainting Interpolation,HII)算法，并為兩種機制的切換提供了判決門限.由于邊緣結構比單一紋理在視覺上更為重要，邊緣導向插值(Edge Guided Interpolation,EGI)算法[7]首先通過自適應閾值Sobel算子估計顯著的邊緣信息，然后選擇邊緣效應最強的候選邊緣進行多方向插值.對于存在強邊緣的受損塊，EGI算法有助于增強其邊緣信息，然而要找到所有邊緣的準確位置是非常困難的.多方向插值算法具有運行速度快與通用性好的優點，但當塊間內容變化較大時，候選像素與權重具有不穩定性，影響恢復質量.

大多數自然圖像具有低通特性，圖像塊可以被建模為基函數的線性組合.基于塊的雙邊濾波(Block-based Bilateral Filtering, BBF)算法[8]利用一對高斯函數來估計受損塊的邊緣信息：一個基函數用于測量受損塊和可用鄰域的相似度，另一個基函數用于測量兩者的空域差異性，BBF算法的復雜度較低.基于最小均方誤差估計器，Koloda等[9]提出了一種多模式基函數(Multi-Mode Kernel,MMK)算法，通過計算受損塊的概率密度函數，利用鄰域信息來確定支撐模型階數，通過耗時的迭代逼近機制來預測丟失像素.

近年來，信號稀疏表達廣泛用于圖像處理.稀疏線性預測(Sparse Linear Prediction,SLP)算法[10]根據當前受損塊的鄰域情況調整掃描順序和候選像素集合的形狀，并用貝葉斯信息準則來確定預測器的階數，預測器階數的增加會導致復雜度呈指數級增長.隨著機器學習的興起，雙稀疏表達(Dual Sparsity Regularization,DSR)算法[11]通過主成分分析進行字典構建，解決了因圖像數據不足造成字典訓練無法完成的難題.DSR算法利用歐式距離小于某一閾值來確定用于字典構建的候選像素集合和模板像素集合，但固定閾值導致的候選塊選取不準問題會降低預測模型的通用性.進一步地，聯合稀疏學習(Joint Sparse Learning,JSL)算法[12]改進了稀疏表達的字典構建與系數求解，利用自適應閾值來提高搜索候選像素集合和模板像素集合的準確性.目前，基于稀疏表達的錯誤隱藏算法均采用線下訓練的字典構建，在實際應用中需要大量圖像作為訓練數據，難以適用于各種丟失模式.即使不考慮模型訓練的耗時與泛化性問題，當前稀疏模型類錯誤隱藏算法的計算復雜度仍然過高.

在空域錯誤隱藏應用中，每個受損塊相對較小但序號明確，恢復目標是在較低復雜度的約束下使重構誤差達到可接受的程度.迭代類隱藏算法以高復雜度換取了恢復質量的輕微提升；一些隱藏算法專門針對特定的丟失模式進行模型訓練或算法優化，難以適用于各種各樣的丟失模式.因此，有必要提出一種新的空域錯誤隱藏算法，以更好地平衡通用性、計算復雜度和恢復質量等性能指標.

1 問題描述

1.1 塊的丟失模式

在圖像通信中，為了便于碼流傳輸，多個塊封裝成一個包，一幅圖像通常編碼成若干獨立的包，每個包可以單獨恢復，當一幅圖像出現了包丟失，信宿端根據受損塊的位置，利用鄰域的無錯塊或已隱藏塊進行恢復.空域錯誤隱藏不同于圖像去噪或對象移除等應用，圖像通信的信宿端能夠獲取受損塊在圖像中的具體位置.在光柵掃描順序下，一個丟失像素的重構不僅依賴于正確接收的像素，也依賴于已經隱藏處理過的像素.為了便于描述，“可用像素”表示正確接收的像素或者已經隱藏過的像素；如果某種塊丟失情形在接收圖像中重復出現，本文稱之為“規則”丟失.現有的錯誤隱藏算法均能很好地應對低丟失率的情形.根據受損塊在圖像中的整體分布情況，可歸為4種丟失模式：規則間隔丟失模式、規則連續丟失模式、隨機突發丟失模式、隨機行丟失模式.

對于圖像塊的丟失，圖1展示了4種具有代表性的丟失模式，圖中每個方塊代表一個8×8或16×16或其他像素大小的圖像塊，正確接收的塊用白色標記，受損塊用黑色標記.如圖1(a)所示，規則間隔丟失模式是一種廣為運用的丟失模式，受損塊在圖像中的分布比較離散，其8個相鄰塊都已經被正確接收，由于可用的鄰域信息比較充分，許多錯誤隱藏算法都能對此種丟失模式進行有效的恢復.圖1(b)給出了規則連續丟失模式的塊分布情形，其中，當前受損塊的4個相鄰塊被正確接收.圖1(c)給出了隨機突發丟失模式的示意圖.圖1(d)展示了隨機行丟失模式的一個示例，受損塊集中出現在圖像中的某些整行，由于受損塊水平方向的鄰域信息已經損失，可資利用的相關信息較少，許多隱藏算法針對此丟失模式都達不到滿意的效果.

圖1 典型的丟失模式.正確接收的塊采用白色方塊標記，受損塊采用黑色方塊標記

空域錯誤隱藏的主要應用場合是圖像通信的實時后處理.對于現有的空域錯誤隱藏機制，一方面，插值機制的計算復雜度較低，但圖像細節恢復的效果一般；而稀疏表達機制的計算復雜度較高，不太適合實時性要求嚴格的場合.另一方面，許多空域錯誤隱藏算法只針對特定的丟失模式進行優化，難以適應不同的丟失模式.因此，有必要在通用性、計算復雜度和恢復質量之間尋求更具競爭力的算法.

1.2 最大后驗預測

延拓區域的像素相關性通常被建模為一個條件隨機過程，空域錯誤隱藏可以采用最大后驗準則來估計當前受損塊的像素[4,12].從統計學的觀點來看，錯誤隱藏問題可以等價為在一個延拓區域內，通過一個可用像素子集{qm} (1≤m≤M)的信息來預測當前丟失像素子集{pk} (1≤k≤K).K和M的大小關系取決于不同的隱藏策略.{pk}的最大后驗估計能表示為最大化聯合條件概率ρ(p1,…,pK|q1,…,qM)，但是K或M的取值范圍通常是比較大的，難以進行準確地建模，在實際應用中獲得這一聯合條件概率幾乎是不可能的.由于一個延拓區域通常是一幅圖像的小塊區域，往往能夠近似成為一個準平穩過程，上述最大后驗估計的簡化策略是基于線性加權的方式來預測每個丟失像素.

(1)

對于公式(1)中的加權系數αn和βm，自適應系數相比于固定系數能更好地表達圖像的局部相關性.作為錯誤隱藏問題的一個一般性假設，空域錯誤隱藏算法大都假設合成的邊緣在穿越受損塊時是準直線的，因此可利用多方向插值來恢復受損邊緣.在光柵掃描順序下，多方向插值逐一地估計受損塊在不同方向上的像素相關性，然后對鄰域像素值與相關系數進行加權疊加.每個當前受損塊對應著一個延拓區域.如圖2所示，一個延拓區域A含有3×3個塊：當前受損塊C位于中心，其它8個塊分別屬于以下3種類型之一：正確接收的無錯塊E、已經執行錯誤隱藏的已隱藏塊R、還未進行錯誤隱藏的后續受損塊S.

圖2 一個延拓區域A的例子，該延拓區域包含當前受損塊C、無錯塊E、已隱藏塊R、后續受損塊S

2 所提算法

本文提出了一種非迭代收縮多方向預測(Non-iterative Shrinkage Multi-directional,NSM)算法，所提算法吸收了現有多方向插值與稀疏模型學習的優點，通過引入自適應的鄰域梯度特征學習機制，高效地獲取受損塊的鄰域信息，隨后通過精細設計的收縮填充次序進行逐像素的多方向插值.

2.1 基于梯度特征的自適應學習

現有的空域錯誤隱藏算法表明，根據梯度特征對受損塊進行自適應插值，可以較好地保持圖像的結構和邊緣信息.所提NSM算法通過在當前延拓區域的無錯塊E和已隱藏塊R中執行梯度特征統計過程，累計當前延拓區域的梯度分布；基于無錯塊E和已隱藏塊R，分別累計8個方向中各方向上的梯度幅值.pi,j表示位于坐標(i,j)的像素，梯度檢測可以表示如下：

(2)

式中，gx(i,j)和gy(i,j)分別表示在x水平方向和y垂直方向的像素強度變化率.現有空域錯誤隱藏算法的梯度檢測采用了各向異性的Sobel或Canny算子，以利于檢出較為準確的邊緣信息.而本文算法僅需統計受損塊鄰域的總體梯度特征，各個方向的像素之間距離越遠、相關性越小，掩模位置的加權系數應與到中心像素的距離成反比，而與方向無關，各向同性梯度檢測器更有利于實現這一目標.因此，本文采用的各向同性梯度檢測器含有兩個3×3像素的梯度掩模算子，中心像素pi,j的梯度分量gx(i,j)和gy(i,j)對其鄰域執行如下兩個3×3像素的梯度掩模算子.

(3)

(4)

基于NSM算法，圖3所示的例子說明了如何利用各向同性梯度檢測器來計算像素pi,j的水平梯度gx(i,j)和垂直梯度gy(i,j)，其中，各向同性的梯度掩模算子用于計算各個延拓區域的水平或垂直梯度分布.各個鄰域像素對中心像素的影響效應并不相同，所以不同的掩模位置有著不同的加權系數.

圖3 各向同性梯度檢測器

在獲取中心像素pi,j的梯度分量gx(i,j)和gy(i,j)之后，坐標(i,j)處的梯度幅值可通過如下公式推導：

(5)

θi,j=arctan[gy(i,j)/gx(i,j)].

(6)

研究表明，超過8個預測方向已難以提升錯誤隱藏的恢復質量[7].因此，每個梯度角度被歸入到8個方向中的某一角度，每個方向的角度范圍是成對的22.5°.在當前延拓區域的無錯塊E和已隱藏塊R中，每個像素對應的梯度幅值和梯度角度分別通過式(5)和式(6)進行計算，由此為8預測方向累計梯度幅值.在獲得延拓區域的梯度分布信息之后，非迭代收縮填充過程將對當前受損塊的所有像素逐一執行多方向預測.

2.2 非迭代收縮填充

對于當前受損塊中的不同像素，它們的填充先后次序會影響最終的恢復質量，因為已經隱藏過的像素可能導致錯誤擴散.對于由外至內的受損塊像素填充，現有的空域錯誤隱藏算法預設了與受損塊無關的像素填充次序，并沒有考慮不同的丟失模式應具有差異化的像素填充次序.因此，本文算法在像素級可用度的基礎上，新增了鄰域級可用度的定義，從而設計出模式自適應的“收縮填充次序”.在大多數情況下，正確接收的像素和已經完成錯誤隱藏的像素有著相似的利用價值.對于任一像素pl，它的像素級可用度α(pl)被定義為

(7)

如果某個像素已經被正確接收到，它的像素級可用度被設置為1.對于一個丟失像素，它的像素級可用度被初始化為0；在進行錯誤隱藏之后，它的像素級可用度被設置為1.一般而言，一個丟失像素的恢復質量會隨著它的16鄰域像素中可用像素的數量增加而提高.對于一個丟失像素Xk，它的鄰域級可用度β(Lk)被定義為在它的16鄰域像素Lk中所有像素級可用度之和

(8)

有著更高鄰域級可用度的像素應該被賦予更高的優先權.在當前受損塊里，有著相等鄰域級可用度β(Lk)的所有像素形成一個像素組，不同的像素組按照一組接一組的順序進行隱藏.根據當前受損塊內像素組的鄰域級可用度，非迭代收縮填充首先恢復第1個像素組，它的像素有著最高的鄰域級可用度.當第1個像素組內的所有像素按照先驗填充準則進行錯誤隱藏之后，非迭代收縮填充將恢復第2個像素組，它的像素在受損塊的所有像素中有著第二高的鄰域級可用度，第2個像素組的所有像素同樣按照先驗填充準則進行錯誤隱藏，以此類推.光柵掃描順序可能導致圖像中的錯誤大致地從左上塊向右下塊進行擴散.一個像素組內的所有像素具有相等的鄰域級可用度，各像素的填充順序需要預先設定，圖4給出了本文所提的先驗填充準則示意圖，圖中每個方框內的數字表示相應像素的填充次序.

圖4 一個像素組內所有像素的先驗填充準則.方框內的數字越小，表示該像素越早進行填充

在當前受損塊內，位于外層的像素組由于有著較高的鄰域級可用度,通常具有更高的優先級，因此收縮填充次序呈現出從外層像素組到內層像素組的大致趨勢.圖5(a)給出了對尺寸為8×8像素的當前受損塊進行非迭代收縮填充的一個例子，當前受損塊的相鄰塊都被正確接收，圖中顏色越深的像素越晚進行錯誤隱藏，各像素上對應的數字表示該像素的填充次序.圖5(b)給出了當前受損塊在非迭代重構過程中的次序幅度圖，有著更高幅度的像素將越晚進行錯誤隱藏.一組接一組的像素組重構將大致從受損塊的外層向內層進行，同時，丟失像素按照先驗填充準則逐個進行恢復，這種像素級的恢復順序被稱為“收縮填充次序”.

圖5 非迭代收縮填充的一個例子，一個8×8塊遇到規則間隔丟失模式(一個小方塊代表一個像素)

(9)

2.3 復雜度分析

下面分析NSM算法的計算復雜度.在當前延拓區域A中，無錯塊E和已隱藏塊R的可用像素被用于估計當前受損塊C的梯度分布，計算開銷主要是在每個可用像素處進行梯度檢測，各向同性梯度檢測器的計算復雜度取決于參與梯度掩模算子的像素數量a.假設塊大小是s2個像素，E和R的塊數量是b，則一個延拓區域包含b×s2個可用像素.因此，梯度特征學習的計算復雜度為O(a×b×s2)，各像素的梯度可供多個相鄰塊使用.為了恢復當前受損塊C，每一丟失像素執行多方向插值，相應的計算復雜度取決于該像素的16鄰域像素Lk中可用像素的數量d.對于一個受損塊，非迭代收縮填充的計算復雜度為O(d×s2).令g=a×b+d，NSM算法的計算復雜度為O(g×s2).

類似的，非迭代類AVC、CAD、BBF或EGI算法的計算復雜度均可表示為O(q×s2)，通常g或q都是較小的整數值.AVC算法的計算復雜度為O(s2)，其實時性最好；BBF算法的q值與NSM算法的g值基本相當.CAD算法采用了三種不同的隱藏算法進行錯誤掩蓋，需要預判受損塊的類型，內容自適應的預判流程增加了實現難度.EGI算法需要執行自適應的邊緣提取，然而尋找所有邊緣的準確位置是比較耗時的.因此，CAD與EGI算法的q值相對較高.當前恢復質量最好的空域錯誤隱藏算法采用了迭代逼近機制，然而每個像素的迭代重構過程是非常耗時的，迭代循環的次數往往超過100次[10-12]，雖然迭代過程可以通過窮舉法搜索出最匹配的候選者，但這一過程往往導致大量無效的重復操作，計算復雜度由此至少增長了一個數量級.

3 實驗結果

為了評估NSM算法，本文在標準測試圖像上進行了大量實驗，塊尺寸采用現有錯誤隱藏算法常用的8×8和16×16像素，并采用圖1所示的4種典型丟失模式：規則間隔丟失模式(丟失率≈25%)、規則連續丟失模式(丟失率≈50%)、隨機突發丟失模式(丟失率≈20%)、隨機行丟失模式(丟失率≈15%),這些模式也為其他錯誤隱藏算法所采用.隨機數生成器采用同一缺省種子，以便針對不同圖像產生重復的隨機突發或隨機行丟失.下列測試圖像均來自USC-SIPI圖像數據庫[13]：Aerial、Boat、Couple、Elaine、House、Lena、Mandrill、Peppers、Barbara、Lighthouse、Crowd、Bridge，包含人臉、動物、植物、房屋等多種類型，格式被統一為8位深度的512×512灰度圖像.NSM算法與緒論所述的空域錯誤隱藏算法進行了比較，包括AVC[4]、CAD[5]、HII[6]、EGI[7]、BBF[8]、MMK[9]、SLP[10]、DSR[11]和JSL[12].為了比較不同算法的計算復雜度，本文在同一實驗平臺上測試了每種算法的運行時間，該平臺包括Intel i5-4210M CPU (2.60 GHz)、8 GB內存、Windows10 的64位操作系統、MATLAB R2018b.由于這些錯誤隱藏算法采用了相似的基本指令集，它們的MATLAB程序能夠為算法復雜度的評估提供一定的參考.

兩種最常用的重構誤差測度：峰值信噪比(PSNR)和多尺度結構相似度(SSIM)用于評價受損圖像的恢復質量[14].PSNR或SSIM的評分越高，則圖像的恢復質量越好.通過在每種丟失模式下分別測試所有圖像的平均性能，表1和表2比較了不同算法的恢復質量.從表中可以看出，NSM與最好質量算法之間的平均值差距分別為0.85 dB的PSNR、0.022 1的SSIM.相比于較低復雜度的AVC、CAD、BBF和EGI算法，NSM算法分別取得了0.625 dB、3.461 dB、1.952 dB和0.506 dB的平均PSNR增益，同時取得了0.027 6、0.051、0.035 3和0.013 6的平均SSIM增益.

就計算復雜度而言，表3顯示了不同算法的運行時間比較.對于每種丟失模式，各算法的運行時間是恢復每一圖像后的平均值.從表中可以看出，AVC、CAD、BBF、EGI和NSM可以被歸為低復雜度的錯誤隱藏算法，而其它迭代類算法的運行時間至少增長了一個數量級.AVC算法的實時性最好，但其平均PSNR和平均SSIM僅高于CAD算法，恢復質量相較于其他低復雜度算法處于劣勢.BBF算法比NSM算法稍快，但由于沒有引入局部自適應的梯度特征學習機制，導致恢復質量較差.除了AVC和BBF算法，所提NSM算法相比于其他錯誤隱藏算法始終需要更少的運行時間，計算復雜度比迭代類算法低了一個數量級以上.NSM算法無需實測數據進行模型訓練，對不同的丟失模式具有良好的通用性，其平均PSNR和平均SSIM在低復雜度算法中表現最好.

表1 在各種丟失模式下，各種錯誤隱藏算法的平均PSNR比較

表2 在各種丟失模式下，各種錯誤隱藏算法的平均SSIM比較

表3 在各種丟失模式下，各種錯誤隱藏算法的平均運行時間比較

4 結論

在現有的空域錯誤隱藏算法中，運行快速的多方向插值算法在處理多種丟失模式時效果不甚理想，而恢復質量高的迭代類算法又難以滿足實時性需求.為了改進當前空域錯誤隱藏的綜合性能，本文提出了一種高效的非迭代收縮多方向預測算法，通過各向同性梯度檢測器學習每個受損塊鄰域的梯度特征，隨后根據精細的收縮填充次序逐一對丟失像素進行非迭代重構.所提算法在各種丟失模式下均能夠獲得良好的綜合性能，在通用性、計算復雜度和恢復質量之間取得了一種具有競爭力的性能折衷.