基于支持向量機的版面分割問題研究

逯瑜嬌 方建軍 張姍 劉彩霞

摘 ?要： 版面分割是版面分析的重要組成部分，實現復雜版面的快速、有效分割是目前亟待解決的問題。針對復雜版面分割問題，文中將相位一致性統計特征和改進灰度共生矩陣的紋理特征相結合，得到一種新的組合特征向量。將該組合特征向量作為訓練樣本，最終得到基于支持向量機的復雜圖像分割算法。實驗結果表明，與其他方法相比，基于支持向量機的方法在版面分割任務中表現出了較好的召回率與準確率，能有效區分復雜圖像中的各類不同區域，該方法為如何提高復雜版面的分割準確率提供了理論參考。

關鍵詞： 版面分割; 支持向量機; 特征向量; 圖像分割算法; 圖像識別; 對比驗證

中圖分類號： TN911?34; TP312 ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）02?0149?05

Research on layout segmentation based on support vector machine

LU Yujiao1， FANG Jianjun2， ZHANG Shan1， LIU Caixia1

Abstract： The layout segmentation is an important part of the layout analysis. The rapid and effective segmentation of complex layout is an urgent problem to be solved. As for the problem of complex layout segmentation， a new combined feature vector is obtained in combination with the phase consistency statistical features and the texture features of the improved gray level co?occurrence matrix. The combined feature vector is taken as the training sample to obtain the complex image segmentation algorithm based on the support vector machine. The experimental results show that in comparison with other methods， the method based on the support vector machine has better recall rate and accuracy in the layout segmentation task， which can effectively distinguish the different regions in the complex images. It provides a theoretical reference for how to improve the segmentation accuracy of the complex layouts.

Keywords： layout segmentation; support vector machine; feature vector; image segmentation method; image recognition; comparison verification

0 ?引 ?言

版面分割是版面分析的研究熱點，當前的版面分割算法主要是對文本圖像的灰度、紋理等[1]。基于支持向量機SVM（Support Vector Machine）在圖像處理領域取得了較好的效果，是版面分割常用技術之一[2?4]。魏鴻磊等將灰度值特征作為基礎，提出了基于統計學和灰度統計特征相結合的方法[5];但由于這些方法均是基于像素進行分類的，忽略了圖像變化邊緣等因素，從而造成了分割效果的明顯減弱。

近來，基于卷積神經網絡的模型在多種高級感知任務上取得了令人注目的效果。在這樣的潮流影響之下，卷積神經網絡也被應用于版面分割任務。Chen Kai等提出只使用一個卷積層的卷積神經網絡處理版面分割[6]，雖然取得了較好的結果，但仍沒有全部利用卷積神經網絡的性能，因為卷度神經網絡需要深度的網絡學習具有區分性、語義性的特征。Ahmad Droby等使用具有更多卷積層的全卷積神經網絡處理版面分割[7]。Wick Christoph等使用基于全卷積神經網絡的編碼器——解碼器結構處理版面分割任務[8]。雖然這些基于卷積神經網絡的算法取得了較好的結果，但其并不像在其他計算機視覺中的應用一樣適合于版面分割。首先，卷積神經網絡需要較大的數據集來學習樣本之中的統計特征。當樣本量較少或者測試樣本不存在于訓練樣本的統計分布時，模型的泛化能力并不理想[9?10]。其次，基于卷積神經網絡的方法需要大量的訓練時間以及調整參數、數據增益、數據預處理等繁瑣的工作。而使用手工設計的特征與支持向量機，則可以在使用少量樣本快速訓練的情況下保持良好的泛化能力。因此，免去了基于卷積神經網絡方法中的繁瑣數據處理工作。為解決上述問題，本文將相位一致性統計特征和改進灰度共生矩陣的紋理特征相結合，得到一種新的組合特征向量。將該組合特征向量作為訓練樣本，最終得到了基于支持向量機的復雜圖像分割算法，并得到了良好的應用效果。

1 ?特征提取

1.1 ?相位一致及其統計特征提取

相位一致方法通過計算圖像的相位一致性來檢測圖像中的特征，可以有效保留邊緣信息。近年來，已經有學者采用相位一致方法處理了計算機視覺中的應用，例如車輛號碼牌識別，充分證明了相位一致方法的有效性。

假設信號為[Ix]，則其對應的相位一致性函數[PCx]為：

[PCx=max?x∈0，2xnAncos?nx-?xnAn] （1）

式中：[An]表示[Ix]傅里葉級數展開后第[n]個余弦分量的幅值;[?nx]為第[n]個傅里葉分量在[x]處的相位值;[?x]為加權平均值;[PC]的取值范圍為[0，1]。

高斯函數可將一維信號拓展為二維，[PCx，y]為：

[PCx，y=onWox，yAnox，yΔ?nox，y-TonAnox，y+ε] （2）

式中：[]表示值為正時值不變，否則值為0;T為噪聲干擾閾值可有效增強相位一致統計特征的魯棒性;[ε]為一個趨于0的正數，其作用是為了防止分母為零時無法進行除法操作進而造成的機器宕機;[Wox，y]為有效頻譜的度量值;[Δ?nox，y]為靈敏相位偏差函數：

[Δ?nox，y=cos?nox，y-?nox，y- ? ? ? ? ? ? ? ? ? ? ? ?sin?nox，y-?nox，y] （3）

將[m×n]大小的圖像進行相位一致計算，得到相位一致性[PC]圖像，獲取該[PC]圖像的均值[E]、方差[V]、偏度[SK]、峰度[BK]、熵[Ent]，并組合成一個向量[p=E，V，SK，BK，Ent]，即[p]為圖像相位一致性統計特征向量。

上述基于相位一致的特征尤其適合版面分割，這是由出版物的特征決定的。出版物中文字因為都是印刷體，所以通常嚴格對齊，行與行之間間距一致，字體大小也一致，即段落內文字與文字、空白與空白的頻率變化穩定。但在不同模塊間，例如標題與副標題、標題與正文之間，字體大小變化明顯，空白間距也不同。有的報紙甚至會在不同模塊之間用矩形框做明顯的分隔。因此，使用基于相位一致的特征可以有效地捕捉上述頻率變化，即更好地將文字大小一致、行距一致的部分歸為一類。

1.2 ?圖像紋理特征提取

灰度共生矩陣（GLCM）是被廣泛應用的紋理特征提取算法，將版面分割為圖像、文本和空白區域。本文通過對GLCM算法進行相應改進，解決了其稀疏矩陣特征值計算冗余大的問題，改進算法如下：

灰度共生矩陣值關于左對角線對稱，將灰度共生矩陣沿左對角線對折，得到一個[i≥j]的下三角矩陣并對其進行和差矢量的計算。相對位移[δx，δy]穩定下，和與差的定義如下：

[Sa，b=ra，b+ra+δx，b+δyda，b=ra，b-ra+δx，b+δy] （4）

和矢量定義為： [Ci;δx，δy=Csi=carda，b∈R，Sa，b=i，1≤a+δx≤A，1≤b+δy≤B] （5）

式中，[i=0，1，2，…，2G-1]。

差矢量定義為： [Cj;δx，δy=Cdj=carda，b∈R，da，b=j，1≤a+δx≤A，1≤b+δy≤B] （6）

式中，[j=0，1，2，…，G-1]。

正規化的和矢量與差矢量分別定義為：

[Si=CSiNHDj=CdjNH] （7）

[NH=i=1HsCSi=j=1HdCdj] （8）

式中，[HS]和[Hd]分別為和、差矢量的長度。紋理特征值計算公式如下：

[UNI=ipSi2?jpdj2] （9）

[COR=12ii-2μ2?pSi-jj2?pdj] （10）

[ENT=-ipSi?logpSi-jpdj?logpdj] （11）

[CON=jj2?pdj] （12）

式中，[μ=i·pSi2]。

改進后的GLCM方法可以與改進前同樣有效地表示共生灰度中的紋理特征的和與差。與此同時，還能將原始運行時間縮短至[12]左右。因此，改進后的GLCM方法可以在具有豐富紋理特征的版面分割任務中得到有效利用。

2 ?SVM版面分割方法

SVM由于其高效、適用性強等優點已被廣泛用于模式分類，比如圖像識別、文本分類等。本文將圖像相位一致和紋理特征相結合，共同構成新的特征向量，有效實現了版面的分割。分割過程如圖1所示。

1） 將待分割圖像分成[W]個[M×N]的子圖像塊，每個子圖像塊通過本文改進的GLCM和基于相位一致統計特征方法提取出長度分別為240和130的特征，并連接在一起構成一個特征向量[xi]。

2） 在特征向量[xi]中選取能代表目標及非目標區域的特征向量作為訓練特征向量，表示為[xj，yj]。其中，[j∈1，2，…，W]，[yj]是類別標志。人工選取的作用是挑選出容易被算法混淆的樣本，進而只使用高質量的樣本訓練分類器。研究表明，高質量的訓練樣本可以顯著提升分類器的性能[11]。

3） 設[A，B]分別代表目標區域和非目標區域，則[yj]可以表示為：

[yj=1， ? ? ? xj∈A-1， ? ?xj∈B] （13）

為保證訓練特征樣本的正確率，判別函數須滿足：

[yjwTxj+b-1≥0] （14）

式中：[w]是權重向量;[b]是常量。兩類樣本的分類空隙[M]的間隔大小為：

[M=2w2] （15）

此時，最優分類問題變為在式（13）條件下，求式（14）的最小值：

[φw=12x2] （16）

通過式（14）和式（16）求得全局最優解[w?，b?]，則線性最優分類判決函數為：

[fx=sgnw?x+b?] （17）

式中：[sgn]為符號函數;[x]為樣本特征向量。

4） 將待分類的特征向量集[xi]代入式（17）中，[fxi=1]，[xi]屬于A類，否則[xi]屬于B類。將每個屬于[AB]類的特征向量變成一個像素值[10]，大小為[M×N]的二值矩陣。

在步驟3）中，常用于SVM中的非線性函數包括線性核函數、多項式核函數、高斯核函數等。通常的原始特征在原始空間中無法做到線性可分，非線性函數將其映射至高維，高斯核函數甚至將原始特征映射至無限維，保證線性可分。

上述分割方法，使用圖像作為輸入/輸出分割后的版面結果。因此在使用時無需多余的預處理或者后處理工作，可以有效減少使用時間。相比于近來基于卷積神經網絡的方法，只需少量的訓練樣本即可獲得良好的泛化能力。卷積神經網絡需使用梯度下降方法進行耗時的最優解搜索，而SVM可以直接使用閉式解計算出結果，可以避免大量訓練時間。由上述分析可知，本文提出的SVM方法比以往的卷積神經網絡更適合版面分割任務。

3 ?實驗結果與分析

本文選取了報紙這種具有復雜版面的圖像，并分別使用傳統方法、基于卷積神經網絡的方法、本文所提方法進行對比實驗。使用傳統方法（區域生長方法）對圖2進行版面分割的結果，如圖3所示;使用基于卷積神經網絡方法對圖2進行版面分割的結果，如圖4所示;使用本文方法對圖2進行版面分割的結果，如圖5所示。

本文使用誤差度量方法計算準確率與召回率。具體而言，版面分割任務中存在3種錯誤類型：

1） 沒有檢測到文本或圖像區域，即人工標記區域不包含于分割結果中，將此類錯誤標記為C;

2） 單個人工標記區域被分割為多個區域，將此類錯誤標記為S;

3） 多個人工標記區域被分割為單個區域，將此類錯誤標記為M。若分割后區域與標簽區域不屬于上述3種情況，則是正確分割區域。若G為所有人工標記樣本，D為所有分割所得區域，|X|為集合X的基數，則準確率p計算公式為：

[p=1-C+S+MD] （18）

召回率r計算公式為：

[r=D-C-S-MG] （19）

本文分別采用閾值分支、邊緣檢測、區域生長等傳統方法，以及基于卷積神經網絡和本文提出的方法在所收集的報紙數據集上進行比較。本文采用10折交叉驗證，即將所有樣本分為10份，每次取出其中9份作為訓練集，剩下1份為驗證集。將10次實驗所得召回率與準確率取平均數作為最終結果，以進行充分的分析。實驗結果如表1所示，本文使用SVM方法取得了最高的召回率和準確率，充分驗證了該方法在版面分割任務中的有效性。

表1中，閾值分割速度最快，但無法充分利用報紙中文字與空白區域的特征，因此具有最低的召回率與準確率。邊緣檢測需要瑣碎的提取特征時間，區域生長以漸進的方式逐步擴散目標區域，因此比SVM更耗時。邊緣檢測提取的邊緣特征以及區域生長的漸進生長均能比閾值分割更好地利用出版物版面的特性，因此比閾值分割效果更好。由表1可知，SVM在版面分割任務中具有最優的召回率與準確率，以及適中的、可以接受的運行時間。由此可以推斷，相位特征和紋理特征可以更好捕捉報紙中不同大小文字及文字與空白區域的區別。

為了更細致地分析相位一致統計特征和紋理特征的有效性，在版面分割任務中，設計消融實驗得到上述特征單獨使用時的性能。由表2可知，不進行特征組合時，單獨使用紋理特征比相位特征準確率、召回率均更高。進行特征組合時，雖運行時間加長了，但效果可以得到進一步提高。

針對GLCM的改進，本文設計消融實驗驗證其有效性。單獨使用改進前與改進后的GLCM測試其在版面分割任務效果，如表3所示。

同樣地，使用改進前與改進后的GLCM紋理特征與相位一致特征共同進行消融實驗，如表4所示。由表3和表4可見，改進后的GLAM在召回率和準確率方面幾乎沒有損失。與此同時，顯著地減少了程序運行時間。只使用GLCM特征時，改進后運行時間不及改進前運行時間的[12]，成功驗證了本文改進GLCM。

通過多次對比實驗分析發現，本文提出的方法對復雜版面的分割具有顯著優勢。此外，在對于圖形區域的分割中，由于圖形規律性差，模糊度高，使得判定圖形與圖像間的界限準確度有所降低。對于同版面的圖像由于類型較為一致，應用該算法的準確率會進一步提高。

4 ?結 ?論

針對當前版面分割準確度不高，分割效率較低等問題，本文將相位一致性統計特征和改進灰度共生矩陣的紋理特征相結合，得到一種新的組合特征向量。將該組合特征向量作為訓練樣本，最終得到了基于支持向量機的復雜圖像分割算法。實驗結果表明，該方法在版面分割中表現出了較高的準確率與召回率，為解決復雜版面分割問題提供了理論幫助。

注：本文通訊作者為方建軍。

參考文獻

[1] 許新征，丁世飛，史忠植，等.圖像分割的新理論和新方法[J].電子學報，2010，38（z2）：76?82.

[2] 吳小季.基于SVM圖像分類方法的研究[D].南京：南京信息工程大學，2011.

[3] 張燁.基于樣本關聯度權重的增量支持向量機算法[J].電子科技，2017，30（3）：41?44.

[4] 余彬，胡洛娜，王吉哲.基于支持向量機的變電站過熱故障的在線監測[J].浙江電力，2016（1）：31?34.

[5] 魏鴻磊，歐宗瑛，張建新.采用支持向量機的指紋圖像分割[J].系統仿真學報，2007，19（10）：2362?2365.

[6] CHEN K， SEURET M. Convolutional neural networks for page segmentation of historical document images [C]// 14th International Conference on Document Analysis and Recognition. Nanjing： IEEE， 2017： 16?20.

[7] DROBY A， BERAT K B， JIHAD E. Competition page layout analysis using fully convolutional networks [C]// 2nd International Workshop on Arabic and Derived Script Analysis and Recognition. Kansas： IEEE， 2018： 1?7.

[8] CHRISTOPH Wick， PUPPE Frank. Fully convolutional neural networks for page segmentation of historical document images [C]// 13th IAPR International Workshop on Document Analysis Systems. Houston： IEEE， 2018： 31?40.

[9] HU Hexiang， CHAO Weilun， SHA Fei. Learning answer embeddings for visual question answering [C]// Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Changsha： IEEE， 2018： 1?5.

[10] 肖鵬峰，馮學智，趙書河，等.基于相位一致的高分辨率遙感圖像分割方法[J].測繪學報，2012，36（2）：146?151.

[11] DODGE Samuel， LINA Karam. Understanding how image quality affects deep neural networks [C]// Eighth International Conference on Quality of Multimedia Experience. Denver： IEEE， 2016： 67?70.

作者簡介：逯瑜嬌（1992—），女，山東濟寧人，碩士研究生，研究方向為圖像處理、深度學習與地形識別。

方建軍（1970—），男，湖北羅田人，教授，研究方向為智能機器人技術。