稀疏分解和圖拉普拉斯正則化的圖像前景背景分割方法

譚婷芳，蔡萬源，蔣俊正,2,3

(1.桂林電子科技大學 信息與通信學院，廣西壯族自治區 桂林 541004；2.桂林電子科技大學 衛星導航定位與位置服務國家地方聯合工程研究中心，廣西壯族自治區 桂林 541004；3.西安電子科技大學 杭州研究院，浙江 杭州 311231)

圖像分割是將圖像劃分為若干區域的過程，每個區域都有相似的含義或特征（例如顏色、強度或紋理），并且這些區域互不相交.圖像前景背景分割作為圖像處理和計算機視覺中的一項基礎性任務，即把圖像分割為前景和背景，其有著廣泛的應用，如圖像壓縮[1]、醫學圖像分割[2]和文本提取[3].

目前，研究者們提出各種圖像分割方法.Lin 等[4]提出通過使用顏色數閾值和形狀基元提取來實現前景背景分割的方法.該方法很難找到合適的顏色數閾值，準確地將圖像分為圖像塊和文本/圖形塊.Bottou 等[5]提出K 均值聚類分割方法，該方法中前景和背景的顏色是通過對所有圖像像素進行層次化K 均值聚類提取的.該方法很難應用于背景和前景顏色強度重疊的部分.Minaee 等[6]提出最小絕對偏差（least absolute deviation,LAD）方法，該方法將平滑模型擬合到圖像上，將像素分為背景或前景.LAD 方法可以分割顏色強度重疊的部分，但是分割后的前景中存在孤立的像素點.Minaee 等[7]提出結合稀疏分解和全變差最小化（sparse decomposition with total variation minimization,SDTVM）的方法.該方法與LAD 方法相比，進一步刻畫了前景像素的連通性.該方法未能充分刻畫前景像素之間的相關性，導致分割的前景文本或圖形中存在部分缺失，存在將背景誤檢測為前景的情況.Minaee 等[8]提出使用子空間表示（subspace representation,SR）的圖像分割方法，其中圖像的每個組成部分都由其子空間或字典表示.利用該方法，無法有效地分離前景信息不明顯的圖像.上述方法雖然在圖像前景背景分割方面取得了一定的效果，但未能充分利用像素之間的關聯性，導致前景中存在較多孤立的像素點.

近年來，圖信號處理（graph signal processing，GSP）[9-11]作為處理非規則域數據的有效工具，廣泛應用于圖像處理[12-16]、計算機圖形學[10]和社交網絡分析[17]等領域.GSP 通過圖對數據的內在結構進行建模，可以有效地刻畫數據樣本間的關系.在圖像處理中，利用基于圖的表示方法，可以捕獲圖像數據的內在結構特征，如分段平滑特性（piecewise smoothness,PWS）[9,18].對于圖像數據，可以基于GSP 理論將像素點建模為圖節點，像素點的強度定義為圖節點的信號值，相鄰像素之間的相似性通過邊的權重來表征，可以充分刻畫圖像像素之間的內在關聯性.

為了對圖像像素之間的相關性進行刻畫，以提升圖像前景背景分割效果，本文對圖像數據進行圖拓撲結構和圖信號建模，提出基于稀疏分解和圖拉普拉斯正則化（sparse decomposition and graph Laplacian regularization,SDGLR）的圖像前景背景分割方法.該方法將GSP 理論的應用擴展到前景背景分割領域，采用圖拉普拉斯正則化（graph Laplacian regularization,GLR）項以刻畫前景像素的連通性.利用圖傅里葉變換（graph Fourier transform,GFT）基函數的線性組合，表示平滑的背景區域.構造稀疏分解和圖拉普拉斯正則化的約束優化問題，采用交替方向乘子法（alternating direction method of multipliers,ADMM），對SDGLR 圖像分割模型進行優化求解.為了驗證提出的前景背景分割方法的有效性，在合成圖像、MSRA[19]數據集和屏幕內容圖像[20]上進行實驗評估，與現有方法進行對比.

1 基礎知識

1.1 圖和圖信號

圖信號可以用 xG=[xG(i)]i∈VG∈RN表示，元素xG(i)為頂點 i上的信號值.信號 xG的圖傅里葉變換[9,23]定義為中的特征向量uG,1,···,uG,N為圖傅里葉變換的基向量，圖傅里葉逆變換的表達式為GFT 具有稀疏表示平滑圖信號[24]的能力，即平滑圖信號可以由少量的圖傅里葉變換基函數有效地表示.

一般來說，GLR 是與拉普拉斯矩陣相關的二次形式，可以有效地應用于相應的圖信號處理問題，如信號重建[25].對于圖 G信號 xG∈RN，GLR[26]可以定義為

1.2 圖像的圖表示

GSP 是可以表示、分析和處理數據的工具，數據樣本之間的相關性可以通過圖模型來捕獲.圖模型可以用來捕捉圖像的內在幾何結構，圖像像素點之間的相關性可以通過圖結構[27]進行有效刻畫.

將圖像劃分為一系列大小為 l×l的非重疊圖像塊.對于每個圖像塊，像素點建模為圖節點，像素點的強度定義為圖節點上的信號值，圖像塊中的每個像素點都與其4 個鄰居相連，相連的像素點之間的邊的權重用來刻畫像素之間的關聯性.為了捕捉相鄰節點之間的強度相似性，2 個相連的節點 i、j之間的權重由高斯核計算[18,28].

式中：σ為用于控制相似性的內核參數.利用式（2）可以得到鄰接矩陣 AG.從式（2）可知，2 個像素之間的像素強度差異越小，對應的權重越大，表明相似性或相關性越強.隨著像素強度差異的增加，相似性或相關性減弱.通過高斯核計算節點之間邊的權重，可以反映節點之間適當相似關系的強度.

將每個頂點 i的像素映射到信號分量 xG(i)，可得每個圖像塊的圖信號表示 xG=[xG(1),xG(2),···,

2 圖像前景背景分割

2.1 問題建模

利用圖信號處理理論和稀疏分解模型，將前景文本/圖形與背景分離，該方法適合背景平滑變化的圖像.這類圖像通常描述為2 個分量的疊加，即具有平滑變化特性的背景分量和具有稀疏性、連通性的前景分量.其中平滑變化的背景區域可以用部分GFT 基函數的線性組合來表示.

將圖像劃分為 rmax個非重疊塊，每個圖像塊的大小為 l×l.第 r個圖像塊 Fr(x,y)表示為

式中：fr和 sr分別對應于 Fr(x,y)和 Sr(x,y)的矢量化；Pr為大小為l2×M的矩陣，第m列對應于Pr,m(x,y)的矢量化；αr=[αr,1,···,αr,M]T.

將關于前景和背景的一些先驗知識引入優化問題的約束條件中.由于背景部分的GFT 基函數的數量未知，可以在模型(3)中選擇足夠的基函數；通過使用 l0范數來最小化參數 αr的非零項.當背景非常光滑時，αr的非零元素的數量會非常少.前景是稀疏的，因此 sr的非零元素的數量很少.采用GLR 可以刻畫前景文本和圖形的連通性，保持清晰的前景文本和圖形輪廓.綜上所述，圖像前景背景分割問題表述為

式中：τ 和 γ為2 個非負的參數；‖·‖0為向量的 l0范數；GLR(sr,Gr)是矩陣的二次形式，本文選擇前 M個GFT 基函數來構造矩陣 Pr，由于 l0范數是非凸的，使用 l1范數作為 l0范數的凸近似值來代替 l0范數.式(5)重新表述為

式中：‖·‖1為向量的 l1范數.

2.2 算法優化

利用ADMM[29]，可以有效求解式(6)中的優化問題.根據ADMM，式(6)重寫為

式(7)中的增廣拉格朗日函數表示為

1）更新 αr.從式(8)中去除不包含 αr的項，可以推導出

式(9)中的問題是最小二乘問題，有以下閉式解：

式中：Ar=ρI+ρPrTPr，其中 I為單位矩陣.

2）更新 xr.從式(8)中去除不包含 xr的項，可以推導出

引入如下軟閾值算子：

式中：?∈R，λ ＞0.式（11）的優化解可以表示為

式中：xri、αri和 uri分別為向量 xr、αr和 ur的第i個元素。

3）更新 yr.從式(8)中去除不包含 yr的項，可以推導出

4）更新 sr.從式(8)中去除不包含 sr的項，可以推導出

式(15)有以下封閉形式的解：

5）更新拉格朗日乘子.根據ADMM 方法，拉格朗日乘子更新為

6）迭代終止條件如下：

式中：ε1、ε2、ε3為誤差參數.若迭代解不滿足迭代終止條件，則按上述迭代步驟更新變量 αr、xr、yr、sr、ur、vr和 wr，直至滿足條件.

綜上所述，基于SDGLR 的圖像前景背景分割算法流程如下所示.

對于式(8)中的變量 ρ，將其初始值設置為ρ=10-2，最大值設置為 ρmax=106，并在每次迭代中 將其更新為 ρ:=min {ηρ,ρmax}[18,30-31].

2.3 復雜度分析

假設圖像塊大小為 l×l，基函數的數量為 M，向量 fr、sr和 αr的大小分別為 l2×1、l2×1 和 M×1，矩陣 Pr的大小為 l2×M.由式（10）、（16）可知，第1、4個變量更新涉及矩陣乘法和逆運算.對于大小為 d×d的 矩陣逆運算，計算復雜度為 O(d3)，因此所提方法對于大小為 l×l的 圖像塊的完整計算復雜度為 O(M3+M+l2M+l6).由于 M為基函數的數量，M＜l2，所提方法對于圖像塊的復雜度為 O(l6).

對于給定大小為 m×n的圖像，假設 m 和 n遠大于 l，則大約有 mn/l2個圖像塊，所提方法的整體計算復雜度為 O(mn(M3/l2+M/l2+M+l4)).因為 M＜l2，所提方法的整體計算復雜度為O(mnl4).

3 實驗結果與分析

3.1 實驗數據和評價指標

采用合成圖像、MSRA[19]數據集和屏幕內容圖像，評估所提SDGLR 方法的性能.合成圖像是一組人工生成的圖像，即在圖像上手動添加文本.MSRA[19]數據集是基準數據集.屏幕內容圖像是一組利用屏幕快照捕獲的圖像[32].

實驗采用準確率P (precision)、召回率R (recall)和F1 指數作為評價指標，定義如下.

式中：TP、FP 和FN 分別為真陽性(true positive)、假陽性(false positive)和假陰性(false negative)的像素數量.

3.2 實驗設置

為了驗證所提SDGLR 方法的分割效果，將所提方法與低秩和稀疏分解（low-rank and sparse decomposition,LRSD）[33]方法、LAD[6]方法、SDTVM[7]方法以及SR[8]方法進行對比.LRSD 方法是將圖像的背景和前景分別建模為低秩和稀疏的.為了提取前景，對分割后的前景進行閾值化處理.為了驗證使用GLR 項的優勢，從式(5)中刪除該項.將沒有GLR 項的方法稱為基于GFT 基函數的稀疏分解方法（SD-GFT），它與使用離散余弦變換（discrete cosine transform,DCT）基函數[7]的分割方法不同.對比方法中的參數根據文獻[6]、[7]、[8]和[33]調整到最優.對于所提的SDGLR 方法，使用交叉驗證法選擇參數 τ、γ 和 M.圖像塊的大小選擇為與HEVC[34]標準中的最大編碼單元（coding units,CU）相同，l=64.對于SD-GFT，GFT 基函數的數量 M和圖像塊大小 l與SDGLR 算法 中的設置相同，正則化參數 τ=0.15.

3.3 對比實驗結果與分析

如圖1～3 所示為不同方法在測試圖像中的分割結果.與LSRD、LAD、SDTVM 和SR 方法相比，SD-GFT 和SDGLR 方法采用圖模型來捕捉圖像的內在幾何結構，能夠更充分地刻畫像素之間的相關性.相對于LAD、SDTVM 和SR 方法，采用一組離散余弦變換基函數的線性組合表示背景部分，SD-GFT 和SDGLR 方法采用一組圖傅里葉變換基函數的線性組合表示背景部分，利用圖模型建立像素之間的聯系.這使得SD-GFT 和SDGLR 方法比采用離散余弦變換基函數表示背景的方法更加靈活，能夠更好地利用像素之間的關聯信息，獲得更好的圖像分割性能.相對于SDTVM 方法采用前景分量的全變差來促進前景像素的連通性，SDGLR 方法采用GLR 正則化項來刻畫前景像素的連通性，使得相鄰像素節點之間的信號值更加相似，促進前景文本和圖形更加連續.相對于SDGFT 方法，SDGLR 方法添加了GLR 正則化項來刻畫前景像素的連通性，這使得前景的連通性有了明顯的改善，例如圖1 第1 幅測試圖像中“strategic”一詞的字母“st”和圖1 第2 幅測試圖像中“Thrones”一詞的字母“s”.這表明引入GLR 項后，前景像素之間的連通性得到了增強.當前景和背景是由不可區分的子空間表示時，SR 不能實現有效的分割.例如對于圖2 的第2 張測試圖像，利用SR 方法不能有效地分割.

圖1 采用不同方法得到的合成圖像分割結果對比Fig.1 Comparison of synthetic image segmentation results by using different methods

圖2 不同方法在MSRA 數據集上的分割結果對比Fig.2 Comparison of segmentation results of different methods on MSRA dataset

圖3 采用不同方法得到的屏幕內容圖像分割結果對比Fig.3 Comparison of screen content image segmentation results by using different methods

如表1、2 所示為不同方法的性能指標.在合成圖像數據（見表1）中，利用SDGLR 方法取得了最好的性能，平均準確率為99.62%，平均召回率為84.93%，平均F1 指數為91.69%，SD-GFT 算法的性能略低于SDGLR 方法.利用LAD、SDTVM和SR 方法取得了良好的性能，LRSD 方法的P、R和平均F1 指數都不大于80.0%.在MSRA 數據集（見表2）中，SDGLR 取得了良好的性能.利用提出的SDGLR 方法，取得了92.88%的平均準確率、79.88%的平均召回率和85.21%的平均F1 指數，平均召回率比LRSD 方法低約5.41%.采用GFT 基函數的線性組合有效地表示背景部分，減少將背景像素誤檢測為前景的情況.這使得SD-GFT 和SDGLR方法相對于LRSD、LAD、SDTVM 和SR 方法取得了更好的性能.提出的SDGLR 方法采用GLR 正則化項來懲罰前景像素中的孤立點，強制前景像素相連，減少了前景文本和圖形的不連續性.這使得SDGLR 方法相較于SD-GFT 方法，取得了更好的性能.總的來說，提出的SDGLR 方法較對比方法取得了相對最好的性能，這得益于用于區分前景和背景成分的圖模型和靈活的分割優化公式.

表1 不同方法在合成圖像上的分割性能對比Tab.1 Comparison of segmentation performance of different methods on synthetic image%

表2 不同方法在MSRA 數據集上的分割性能對比Tab.2 Comparison of segmentation performance of different methods on MSRA dataset%

3.4 參數分析

以圖1 的第1 張測試圖像為例，對SDGLR 方法中需要調整的參數進行分析討論.

正則項參數 τ的靈敏性分析.在SDGLR 方法中，采用參數 τ來權衡背景模型參數 αr和前景 sr.如圖4 所示為當 τ為[0,1.0]時的F1 指數.可以看出，當 τ=0.15時，該方法的分割性能最佳.正則項參數 γ的靈敏性分析.γ為用于懲罰前景像素連通性的參數.如圖5 所示為當 γ為[0,1.0]時的分割效果.可以看出，當 γ=0.5時，分割性能最佳.

圖4 參數τ 的靈敏度分析Fig.4 Sensitivity analysis of parameter τ

圖5 參數γ 的靈敏度分析Fig.5 Sensitivity analysis of parameter γ

GFT 基函數的數量 M.為了評估 M對最終分割結果的影響，如圖6 所示為使用不同數量基函數導出的分割結果圖.可以看出，當 M=10時，分割效果最佳.

圖6 不同基函數數量下提出方法的分割結果Fig.6 Segmentation results of proposed method with different number of basis functions

圖像塊大小 l和數量.在HEVC[34]標準中，最大編碼單元（coding units,CU）通常被設定為 64×64或 32×32.選取較小的圖像塊可以降低運算復雜度，但是圖像質量受到限制.較大的圖像塊可以提高圖像質量，但需要增加計算量.CU 為 64×64的圖像塊能夠在計算復雜度和圖像質量間取得較好的平衡點.因為HEVC 是比較成熟的標準，選擇CU 為 64×64的圖像塊，可以使研究工作與已有研究工作保持一致.如圖7 所示為由不同 l導出的分割結果.可見，當 l=64時，分割性能最佳.圖像塊的數量由原圖像大小和圖像塊大小 l決 定，給定 l的情況，原圖越大，圖像塊數量越多，程序運行時間越長.

圖7 不同圖像塊大小下提出方法的分割結果Fig.7 Segmentation results of proposed method with different image block sizes

3.5 收斂性分析

如圖8 所示為實驗中F1 與迭代次數Ni的關系.從圖8 的F1 變化趨勢可以看出，在一定迭代次數后，指標的變化速度逐漸減緩，最終趨于穩定的常數值.這表明所提出的方法在一定程度上已經收斂.特別地，在保持較高F1 的情況下，該方法能夠在第12 次迭代后達到收斂狀態.這說明所提方法的收斂效率較高，即在相對較少的迭代次數內取得較優的分割效果.

圖8 F1 與迭代次數的關系Fig.8 F1 value versus number iterations

4 結 語

本文提出基于圖信號處理和稀疏分解的圖像前景背景分割方法，旨在將圖像的前景與背景分離.在SDGLR 模型中，趨于平滑的背景區域可以通過GFT 基函數的線性組合有效地表示.在目標函數中添加GLR 項來懲罰前景中的孤立點，以加強前景像素的連通性.實驗結果表明，利用提出的SDGLR 方法，能夠更好地刻畫圖像像素中的相關性，在視覺和定量評估方面取得了優異的效果.在接下來的工作中，將基于圖模型的圖像前景背景分割方法擴展到其他場景，如視頻的前景背景分割.