基于支持向量機(jī)的版面分割問(wèn)題研究

逯瑜嬌 方建軍 張姍 劉彩霞

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

關(guān)鍵詞： 版面分割; 支持向量機(jī); 特征向量; 圖像分割算法; 圖像識(shí)別; 對(duì)比驗(yàn)證

中圖分類號(hào)： TN911?34; TP312 ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)： 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 ?引 ?言

版面分割是版面分析的研究熱點(diǎn)，當(dāng)前的版面分割算法主要是對(duì)文本圖像的灰度、紋理等[1]?；谥С窒蛄繖C(jī)SVM（Support Vector Machine）在圖像處理領(lǐng)域取得了較好的效果，是版面分割常用技術(shù)之一[2?4]。魏鴻磊等將灰度值特征作為基礎(chǔ)，提出了基于統(tǒng)計(jì)學(xué)和灰度統(tǒng)計(jì)特征相結(jié)合的方法[5];但由于這些方法均是基于像素進(jìn)行分類的，忽略了圖像變化邊緣等因素，從而造成了分割效果的明顯減弱。

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

1 ?特征提取

1.1 ?相位一致及其統(tǒng)計(jì)特征提取

相位一致方法通過(guò)計(jì)算圖像的相位一致性來(lái)檢測(cè)圖像中的特征，可以有效保留邊緣信息。近年來(lái)，已經(jīng)有學(xué)者采用相位一致方法處理了計(jì)算機(jī)視覺(jué)中的應(yīng)用，例如車輛號(hào)碼牌識(shí)別，充分證明了相位一致方法的有效性。

假設(shè)信號(hào)為[Ix]，則其對(duì)應(yīng)的相位一致性函數(shù)[PCx]為：

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

式中：[An]表示[Ix]傅里葉級(jí)數(shù)展開(kāi)后第[n]個(gè)余弦分量的幅值;[?nx]為第[n]個(gè)傅里葉分量在[x]處的相位值;[?x]為加權(quán)平均值;[PC]的取值范圍為[0，1]。

高斯函數(shù)可將一維信號(hào)拓展為二維，[PCx，y]為：

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

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

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

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

上述基于相位一致的特征尤其適合版面分割，這是由出版物的特征決定的。出版物中文字因?yàn)槎际怯∷Ⅲw，所以通常嚴(yán)格對(duì)齊，行與行之間間距一致，字體大小也一致，即段落內(nèi)文字與文字、空白與空白的頻率變化穩(wěn)定。但在不同模塊間，例如標(biāo)題與副標(biāo)題、標(biāo)題與正文之間，字體大小變化明顯，空白間距也不同。有的報(bào)紙甚至?xí)诓煌K之間用矩形框做明顯的分隔。因此，使用基于相位一致的特征可以有效地捕捉上述頻率變化，即更好地將文字大小一致、行距一致的部分歸為一類。

1.2 ?圖像紋理特征提取

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

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

[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]。

正規(guī)化的和矢量與差矢量分別定義為：

[Si=CSiNHDj=CdjNH] （7）

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

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

[UNI=ipSi2?jpdj2] （9）

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

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

[CON=jj2?pdj] （12）

式中，[μ=i·pSi2]。

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

2 ?SVM版面分割方法

SVM由于其高效、適用性強(qiáng)等優(yōu)點(diǎn)已被廣泛用于模式分類，比如圖像識(shí)別、文本分類等。本文將圖像相位一致和紋理特征相結(jié)合，共同構(gòu)成新的特征向量，有效實(shí)現(xiàn)了版面的分割。分割過(guò)程如圖1所示。

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

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

3） 設(shè)[A，B]分別代表目標(biāo)區(qū)域和非目標(biāo)區(qū)域，則[yj]可以表示為：

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

為保證訓(xùn)練特征樣本的正確率，判別函數(shù)須滿足：

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

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

[M=2w2] （15）

此時(shí)，最優(yōu)分類問(wèn)題變?yōu)樵谑剑?3）條件下，求式（14）的最小值：

[φw=12x2] （16）

通過(guò)式（14）和式（16）求得全局最優(yōu)解[w?，b?]，則線性最優(yōu)分類判決函數(shù)為：

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

式中：[sgn]為符號(hào)函數(shù);[x]為樣本特征向量。

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

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

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

3 ?實(shí)驗(yàn)結(jié)果與分析

本文選取了報(bào)紙這種具有復(fù)雜版面的圖像，并分別使用傳統(tǒng)方法、基于卷積神經(jīng)網(wǎng)絡(luò)的方法、本文所提方法進(jìn)行對(duì)比實(shí)驗(yàn)。使用傳統(tǒng)方法（區(qū)域生長(zhǎng)方法）對(duì)圖2進(jìn)行版面分割的結(jié)果，如圖3所示;使用基于卷積神經(jīng)網(wǎng)絡(luò)方法對(duì)圖2進(jìn)行版面分割的結(jié)果，如圖4所示;使用本文方法對(duì)圖2進(jìn)行版面分割的結(jié)果，如圖5所示。

本文使用誤差度量方法計(jì)算準(zhǔn)確率與召回率。具體而言，版面分割任務(wù)中存在3種錯(cuò)誤類型：

1） 沒(méi)有檢測(cè)到文本或圖像區(qū)域，即人工標(biāo)記區(qū)域不包含于分割結(jié)果中，將此類錯(cuò)誤標(biāo)記為C;

2） 單個(gè)人工標(biāo)記區(qū)域被分割為多個(gè)區(qū)域，將此類錯(cuò)誤標(biāo)記為S;

3） 多個(gè)人工標(biāo)記區(qū)域被分割為單個(gè)區(qū)域，將此類錯(cuò)誤標(biāo)記為M。若分割后區(qū)域與標(biāo)簽區(qū)域不屬于上述3種情況，則是正確分割區(qū)域。若G為所有人工標(biāo)記樣本，D為所有分割所得區(qū)域，|X|為集合X的基數(shù)，則準(zhǔn)確率p計(jì)算公式為：

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

召回率r計(jì)算公式為：

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

本文分別采用閾值分支、邊緣檢測(cè)、區(qū)域生長(zhǎng)等傳統(tǒng)方法，以及基于卷積神經(jīng)網(wǎng)絡(luò)和本文提出的方法在所收集的報(bào)紙數(shù)據(jù)集上進(jìn)行比較。本文采用10折交叉驗(yàn)證，即將所有樣本分為10份，每次取出其中9份作為訓(xùn)練集，剩下1份為驗(yàn)證集。將10次實(shí)驗(yàn)所得召回率與準(zhǔn)確率取平均數(shù)作為最終結(jié)果，以進(jìn)行充分的分析。實(shí)驗(yàn)結(jié)果如表1所示，本文使用SVM方法取得了最高的召回率和準(zhǔn)確率，充分驗(yàn)證了該方法在版面分割任務(wù)中的有效性。

表1中，閾值分割速度最快，但無(wú)法充分利用報(bào)紙中文字與空白區(qū)域的特征，因此具有最低的召回率與準(zhǔn)確率。邊緣檢測(cè)需要瑣碎的提取特征時(shí)間，區(qū)域生長(zhǎng)以漸進(jìn)的方式逐步擴(kuò)散目標(biāo)區(qū)域，因此比SVM更耗時(shí)。邊緣檢測(cè)提取的邊緣特征以及區(qū)域生長(zhǎng)的漸進(jìn)生長(zhǎng)均能比閾值分割更好地利用出版物版面的特性，因此比閾值分割效果更好。由表1可知，SVM在版面分割任務(wù)中具有最優(yōu)的召回率與準(zhǔn)確率，以及適中的、可以接受的運(yùn)行時(shí)間。由此可以推斷，相位特征和紋理特征可以更好捕捉報(bào)紙中不同大小文字及文字與空白區(qū)域的區(qū)別。

為了更細(xì)致地分析相位一致統(tǒng)計(jì)特征和紋理特征的有效性，在版面分割任務(wù)中，設(shè)計(jì)消融實(shí)驗(yàn)得到上述特征單獨(dú)使用時(shí)的性能。由表2可知，不進(jìn)行特征組合時(shí)，單獨(dú)使用紋理特征比相位特征準(zhǔn)確率、召回率均更高。進(jìn)行特征組合時(shí)，雖運(yùn)行時(shí)間加長(zhǎng)了，但效果可以得到進(jìn)一步提高。

針對(duì)GLCM的改進(jìn)，本文設(shè)計(jì)消融實(shí)驗(yàn)驗(yàn)證其有效性。單獨(dú)使用改進(jìn)前與改進(jìn)后的GLCM測(cè)試其在版面分割任務(wù)效果，如表3所示。

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

通過(guò)多次對(duì)比實(shí)驗(yàn)分析發(fā)現(xiàn)，本文提出的方法對(duì)復(fù)雜版面的分割具有顯著優(yōu)勢(shì)。此外，在對(duì)于圖形區(qū)域的分割中，由于圖形規(guī)律性差，模糊度高，使得判定圖形與圖像間的界限準(zhǔn)確度有所降低。對(duì)于同版面的圖像由于類型較為一致，應(yīng)用該算法的準(zhǔn)確率會(huì)進(jìn)一步提高。

4 ?結(jié) ?論

針對(duì)當(dāng)前版面分割準(zhǔn)確度不高，分割效率較低等問(wèn)題，本文將相位一致性統(tǒng)計(jì)特征和改進(jìn)灰度共生矩陣的紋理特征相結(jié)合，得到一種新的組合特征向量。將該組合特征向量作為訓(xùn)練樣本，最終得到了基于支持向量機(jī)的復(fù)雜圖像分割算法。實(shí)驗(yàn)結(jié)果表明，該方法在版面分割中表現(xiàn)出了較高的準(zhǔn)確率與召回率，為解決復(fù)雜版面分割問(wèn)題提供了理論幫助。

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

參考文獻(xiàn)

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

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

[3] 張燁.基于樣本關(guān)聯(lián)度權(quán)重的增量支持向量機(jī)算法[J].電子科技，2017，30（3）：41?44.

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

[5] 魏鴻磊，歐宗瑛，張建新.采用支持向量機(jī)的指紋圖像分割[J].系統(tǒng)仿真學(xué)報(bào)，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] 肖鵬峰，馮學(xué)智，趙書(shū)河，等.基于相位一致的高分辨率遙感圖像分割方法[J].測(cè)繪學(xué)報(bào)，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.

作者簡(jiǎn)介：逯瑜嬌（1992—），女，山東濟(jì)寧人，碩士研究生，研究方向?yàn)閳D像處理、深度學(xué)習(xí)與地形識(shí)別。

方建軍（1970—），男，湖北羅田人，教授，研究方向?yàn)橹悄軝C(jī)器人技術(shù)。