基于支持向量机的版面分割问题研究

逯瑜娇 方建军 张姗 刘彩霞

摘  要： 版面分割是版面分析的重要组成部分，实现复杂版面的快速、有效分割是目前亟待解决的问题。针对复杂版面分割问题，文中将相位一致性统计特征和改进灰度共生矩阵的纹理特征相结合，得到一种新的组合特征向量。将该组合特征向量作为训练样本，最终得到基于支持向量机的复杂图像分割算法。实验结果表明，与其他方法相比，基于支持向量机的方法在版面分割任务中表现出了较好的召回率与准确率，能有效区分复杂图像中的各类不同区域，该方法为如何提高复杂版面的分割准确率提供了理论参考。

关键词： 版面分割; 支持向量机; 特征向量; 图像分割算法; 图像识别; 对比验证

中图分类号： 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—），男，湖北罗田人，教授，研究方向为智能机器人技术。