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

谭婷芳，蔡万源，蒋俊正,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 方法，能够更好地刻画图像像素中的相关性，在视觉和定量评估方面取得了优异的效果.在接下来的工作中，将基于图模型的图像前景背景分割方法扩展到其他场景，如视频的前景背景分割.