图像分割是将图像划分为若干区域的过程，每个区域都有相似的含义或特征（例如颜色、强度或纹理），并且这些区域互不相交. 图像前景背景分割作为图像处理和计算机视觉中的一项基础性任务，即把图像分割为前景和背景，其有着广泛的应用，如图像压缩^[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]上进行实验评估，与现有方法进行对比.

给定加权无向图$ G = \left\{ {{V_G},{E_G},{{\boldsymbol{A}}_G}} \right\} $. 其中V_G表示图$ G $上$ N $个节点的集合, $ {V_G} = \left\{ {1, \cdots ,N} \right\} $；$ {E_G} $为边的集合；A_G为加权邻接矩阵，$ {{\boldsymbol{A}}_G} = [a{\left( {i,j} \right)]_{i,j \in {V_G}}} $,元素$ a\left( {i,j} \right) \geqslant 0 $为连接顶点$ i $和$ j $之间边的权重^[21-22]. 度矩阵定义为$ {{\boldsymbol{D}}_G} = {\rm{diag}}\;\left( {{d_i}} \right) $，其中$ {d_i} = \displaystyle \sum\nolimits_j {a\left( {i,j} \right)} $. 图$ G $的组合拉普拉斯矩阵定义为$ {{\boldsymbol{L}}_G} = {{\boldsymbol{D}}_G} - {{\boldsymbol{A}}_G} $，$ {{\boldsymbol{L}}_G} $为实对称矩阵，因此$ {{\boldsymbol{L}}_G} $可以特征分解为$ {{\boldsymbol{L}}_G} = {{\boldsymbol{U}}_G}{{\boldsymbol{\varLambda }}_G}{\boldsymbol{U}}_G^{ - {{1}}} $. 其中${\boldsymbol{U}}_G $为特征向量矩阵，$ {{\boldsymbol{U}}_G} = { [ {\boldsymbol{u}}_{G,n} ] _{n = 1, \cdots ,N}} $，${\boldsymbol{\varLambda }}_G$为特征值矩阵，$ {{\boldsymbol{\varLambda }}_G} = {\rm{diag}} \left[ {{\lambda _{G,1}}, \cdots ,{\lambda _{G,N}}} \right] $，其特征值按升序排列为$ {\lambda _{G,1}} \leqslant \cdots \leqslant {\lambda _{G,N}} $.

图信号可以用$ {{\boldsymbol{x}}_G} = {\left[ {{x_G}\left( i \right)} \right]_{i \in {V_G}}} \in {{\bf{R}}^N} $表示，元素$ {x_G}\left( i \right) $为顶点$ i $上的信号值. 信号$ {{\boldsymbol{x}}_G} $的图傅里叶变换^[9,23]定义为$ {\widehat {\boldsymbol{x}}_G} = {\boldsymbol{U}}_G^{\rm{T}}{{\boldsymbol{x}}_G} $，$ {{\boldsymbol{U}}_G} $中的特征向量$ {{\boldsymbol{u}}_{G,1}}, \cdots ,{{\boldsymbol{u}}_{G,N}} $为图傅里叶变换的基向量，图傅里叶逆变换的表达式为$ {{\boldsymbol{x}}_G} = {{\boldsymbol{U}}_G}{\widehat {\boldsymbol{x}}_G} $. GFT具有稀疏表示平滑图信号^[24]的能力，即平滑图信号可以由少量的图傅里叶变换基函数有效地表示.

一般来说，GLR是与拉普拉斯矩阵相关的二次形式，可以有效地应用于相应的图信号处理问题，如信号重建^[25]. 对于图$ G $信号$ {{\boldsymbol{x}}_G} \in {{\bf{R}}^N} $，GLR^[26]可以定义为

(1)$ {\boldsymbol{x}}_G^{\rm{T}}{{\boldsymbol{L}}_G}{{\boldsymbol{x}}_G} = \sum\limits_{\left( {i,j} \right) \in {E_G}} {a(i,j){{\left( {{x_G}(i) - {x_G}(j)} \right)}^2}.} $

GSP是可以表示、分析和处理数据的工具，数据样本之间的相关性可以通过图模型来捕获. 图模型可以用来捕捉图像的内在几何结构，图像像素点之间的相关性可以通过图结构^[27]进行有效刻画.

将图像划分为一系列大小为$ l \times l $的非重叠图像块. 对于每个图像块，像素点建模为图节点，像素点的强度定义为图节点上的信号值，图像块中的每个像素点都与其4个邻居相连，相连的像素点之间的边的权重用来刻画像素之间的关联性. 为了捕捉相邻节点之间的强度相似性，2个相连的节点$ i $、$ j $之间的权重由高斯核计算^[18,28].

(2)$ a(i,j) = \exp \left( { - \frac{{{{\left| {{x_G}(i) - {x_G}(j)} \right|}^2}}}{{{\sigma ^2}}}} \right). $

式中：$ \sigma $为用于控制相似性的内核参数. 利用式（2）可以得到邻接矩阵$ {{\boldsymbol{A}}_G} $. 从式（2）可知，2个像素之间的像素强度差异越小，对应的权重越大，表明相似性或相关性越强. 随着像素强度差异的增加，相似性或相关性减弱. 通过高斯核计算节点之间边的权重，可以反映节点之间适当相似关系的强度.

将每个顶点$ i $的像素映射到信号分量$ {x_G}(i) $，可得每个图像块的图信号表示$ {{\boldsymbol{x}}_G} = \left[ {x_G}(1),{x_G}\left( 2 \right), \cdots , {x_G}\left( {{l^2}} \right) \right]^{\rm{T}} \in {{\bf{R}}^{{l^2} \times 1}} $.

利用图信号处理理论和稀疏分解模型，将前景文本/图形与背景分离，该方法适合背景平滑变化的图像. 这类图像通常描述为2个分量的叠加，即具有平滑变化特性的背景分量和具有稀疏性、连通性的前景分量. 其中平滑变化的背景区域可以用部分GFT基函数的线性组合来表示.

将图像划分为$ {r_{\max }} $个非重叠块，每个图像块的大小为$ l \times l $. 第$ r $个图像块$ {{\boldsymbol{F}}_r}\left( {x,y} \right) $表示为

(3)$ {{\boldsymbol{F}}_r}\left( {x,y} \right) = \sum\nolimits_{m = 1}^M {{\alpha _{r,m}}} {{\boldsymbol{P}}_{r,m}}\left( {x,y} \right)+{{\boldsymbol{S}}_r}\left( {x,y} \right). $

式中：$ r = 1, \cdots ,{r_{\rm{{max}}}} ,$$ x $和$ y $分别为横坐标和纵坐标；$ M $为GFT基函数的数量；$ \displaystyle \sum\nolimits_{m = 1}^M {{\alpha _{r,m}}} {{\boldsymbol{P}}_{r,m}}\left( {x,y} \right) $对应于背景，$ {{\boldsymbol{P}}_{r,m}}\left( {x,y} \right) $为GFT基函数,$ {\alpha _{r,m}} $为模型参数；$ {{\boldsymbol{S}}_r}\left( {x,y} \right) $对应于前景. 通过将矩阵矢量化，式(3)改写为

(4)$ {{\boldsymbol{f}}_r} = {{\boldsymbol{P}}_r}{{\boldsymbol{\alpha }}_r}+{{\boldsymbol{s}}_r}. $

式中：$ {{\boldsymbol{f}}_r} $和$ {{\boldsymbol{s}}_r} $分别对应于$ {{\boldsymbol{F}}_r}\left( {x,y} \right) $和$ {{\boldsymbol{S}}_r}\left( {x,y} \right) $的矢量化；$ {{\boldsymbol{P}}_r} $为大小为$ {l^2} \times M $的矩阵，第$ m $列对应于$ {{\boldsymbol{P}}_{r,m}}\left( {x,y} \right) $的矢量化；$ {{\boldsymbol{\alpha }}_r} = {\left[ {{\alpha _{r,1}}, \cdots ,{\alpha _{r,M}}} \right]^{\rm{T}}} $.

将关于前景和背景的一些先验知识引入优化问题的约束条件中. 由于背景部分的GFT基函数的数量未知，可以在模型(3)中选择足够的基函数；通过使用$ {l_0} $范数来最小化参数$ {{\boldsymbol{\alpha }}_r} $的非零项. 当背景非常光滑时，$ {{\boldsymbol{\alpha }}_r} $的非零元素的数量会非常少. 前景是稀疏的，因此$ {{\boldsymbol{s}}_r} $的非零元素的数量很少. 采用GLR可以刻画前景文本和图形的连通性，保持清晰的前景文本和图形轮廓. 综上所述，图像前景背景分割问题表述为

(5)$\left. \begin{split} &\mathop {\min }\limits_{{{\boldsymbol{s}}_r},\;{{\boldsymbol{\alpha }}_r}}\; {\left\| {{{\boldsymbol{\alpha }}_r}} \right\|_0}+\tau {\left\| {{{\boldsymbol{s}}_r}} \right\|_0}+\gamma {\text{GLR}}\left( {{{\boldsymbol{s}}_r},{G_r}} \right); \\ & {\rm{s.t.}}\quad {{\boldsymbol{f}}_r} = {{\boldsymbol{P}}_r}{{\boldsymbol{\alpha }}_r}+{{\boldsymbol{s}}_r}.\end{split}\right\} $

式中：$ \tau $和$ \gamma $为2个非负的参数；$ {\left\| \cdot \right\|_0} $为向量的$ {l_0} $范数；$ {\text{GLR}}\left( {{{\boldsymbol{s}}_r},{G_r}} \right) $是矩阵的二次形式，本文选择前$ M $个GFT基函数来构造矩阵$ {{\boldsymbol{P}}_r} $，由于$ {l_0} $范数是非凸的，使用$ {l_1} $范数作为$ {l_0} $范数的凸近似值来代替$ {l_0} $范数. 式(5)重新表述为

(6)$\left.\begin{aligned} & \mathop {\min }\limits_{{{\boldsymbol{s}}_r},\;{{\boldsymbol{\alpha }}_r}} \;{\left\| {{{\boldsymbol{\alpha }}_r}} \right\|_1}+\tau {\left\| {{{\boldsymbol{s}}_r}} \right\|_1}+\gamma {{\boldsymbol{s}}_r}^{\rm{T}}{{\boldsymbol{L}}_{{G_r}}}{{\boldsymbol{s}}_r}; \\ &{\rm{s.t.}}\quad {{\boldsymbol{f}}_r} = {{\boldsymbol{P}}_r}{{\boldsymbol{\alpha }}_r}+{{\boldsymbol{s}}_r}. \end{aligned} \right\}$

式中：$ {\left\| \cdot \right\|_1} $为向量的$ {l_1} $范数.

利用ADMM^[29]，可以有效求解式(6)中的优化问题. 根据ADMM，式(6)重写为

(7)$ \left.\begin{aligned} &\mathop {\min }\limits_{{{\boldsymbol{\alpha }}_r},{{\boldsymbol{x}}_r},{{\boldsymbol{y}}_r},{{\boldsymbol{s}}_r}} {\left\| {{{\boldsymbol{x}}_r}} \right\|_1}+\tau {\left\| {{{\boldsymbol{y}}_r}} \right\|_1}+\gamma {{\boldsymbol{s}}_r}^{\rm{T}}{{\boldsymbol{L}}_{{G_r}}}{{\boldsymbol{s}}_r} ; \\& {\rm{s.t.}}\quad {{\boldsymbol{x}}_r} = {{\boldsymbol{\alpha }}_r},\;{{\boldsymbol{y}}_r} = {{\boldsymbol{f}}_r} - {{\boldsymbol{P}}_r}{{\boldsymbol{\alpha }}_r},\;{{\boldsymbol{y}}_r} = {{\boldsymbol{s}}_r}.\end{aligned} \right\}$

式(7)中的增广拉格朗日函数表示为

(8)$\begin{split} &\ell \left( {{{\boldsymbol{\alpha }}_r},{{\boldsymbol{x}}_r},{{\boldsymbol{y}}_r},{{\boldsymbol{s}}_r},{{\boldsymbol{u}}_r},{{\boldsymbol{v}}_r},{{\boldsymbol{w}}_r}} \right) = {\left\| {{{\boldsymbol{x}}_r}} \right\|_1}+\tau {\left\| {{{\boldsymbol{y}}_r}} \right\|_1}+ \\ &\gamma {{\boldsymbol{s}}_r}^{\rm{T}}{{\boldsymbol{L}}_{{G_r}}}{{\boldsymbol{s}}_r}+\left\langle {{{\boldsymbol{u}}_r},{{\boldsymbol{x}}_r} - {{\boldsymbol{\alpha }}_r}} \right\rangle + \\& \left\langle {{{\boldsymbol{v}}_r},{{\boldsymbol{y}}_r}+{{\boldsymbol{P}}_r}{{\boldsymbol{\alpha }}_r} - {{\boldsymbol{f}}_r}} \right\rangle +\left\langle {{{\boldsymbol{w}}_r},{{\boldsymbol{y}}_r} - {{\boldsymbol{s}}_r}} \right\rangle + \\ &\frac{\rho }{2}(\left\| {{{\boldsymbol{x}}_r} - {{\boldsymbol{\alpha }}_r}} \right\|_2^2+\left\| {{{\boldsymbol{y}}_r}+{{\boldsymbol{P}}_r}{{\boldsymbol{\alpha }}_r} - {{\boldsymbol{f}}_r}} \right\|_2^2+\left\| {{{\boldsymbol{y}}_r} - {{\boldsymbol{s}}_r}} \right\|_2^2).\end{split} $

式中：$ \left\| \cdot \right\|_2^2 $为向量$ {l_2} $范数的平方，$ {{\boldsymbol{u}}_r} $、$ {{\boldsymbol{v}}_r} $和$ {{\boldsymbol{w}}_r} $为对偶变量的拉格朗日乘子，$ \left\langle \cdot \right\rangle $表示内积，$ \rho $为大于零的惩罚项参数. 提出的优化过程是交替优化式(8)中的变量，即迭代优化增广拉格朗日函数(8)中的一个变量，同时固定其他变量. 在第k+1次迭代中，具体的更新变量如下.

1）更新$ {{\boldsymbol{\alpha }}_r} $. 从式(8)中去除不包含$ {{\boldsymbol{\alpha }}_r} $的项，可以推导出

(9)$ \begin{split} & {\boldsymbol{\alpha }}_r^{(k+1)} = \mathop {\arg \min }\limits_{{{\boldsymbol{\alpha }}_r}} \;\Biggl\{\left\langle {{\boldsymbol{u}}_r^{(k)},{\boldsymbol{x}}_r^{(k)} - {{\boldsymbol{\alpha }}_r}} \right\rangle + \\& \left\langle {{\boldsymbol{v}}_r^{(k)},{\boldsymbol{y}}_r^{(k)}+{{\boldsymbol{P}}_r}{{\boldsymbol{\alpha }}_r} - {{\boldsymbol{f}}_r}} \right\rangle + \\& \frac{\rho }{2}\left( {\left\| {{\boldsymbol{x}}_r^{(k)} - {{\boldsymbol{\alpha }}_r}} \right\|_2^2+\left\| {{\boldsymbol{y}}_r^{(k)}+{{\boldsymbol{P}}_r}{{\boldsymbol{\alpha }}_r} - {{\boldsymbol{f}}_r}} \right\|_2^2} \right)\Biggl\}.\end{split}$

式(9)中的问题是最小二乘问题，有以下闭式解：

(10)$ {\boldsymbol{\alpha }}_r^{(k+1)} = {\boldsymbol{A}}_r^{ - 1}\left( {{\boldsymbol{u}}_r^{(k)}} \right. - {\boldsymbol{P}}_r^{\rm{T}}{\boldsymbol{v}}_r^{(k)}+ \rho {\boldsymbol{x}}_r^{(k)}\left. {+\rho {\boldsymbol{P}}_r^{\rm{T}}\left( {{{\boldsymbol{f}}_r} - {\boldsymbol{y}}_r^{(k)}} \right)} \right). $

式中：$ {{\boldsymbol{A}}_r} = {{\rho {\boldsymbol{I}}}}+{{\rho }}{{\boldsymbol{P}}_r}^{\rm{T}}{{\boldsymbol{P}}_r} $，其中$ {\boldsymbol{I}} $为单位矩阵.

2）更新$ {{\boldsymbol{x}}_r} $. 从式(8)中去除不包含$ {{\boldsymbol{x}}_r} $的项，可以推导出

(11)$ \begin{split} {\boldsymbol{x}}_r^{(k+1)} =& \mathop {\arg \min }\limits_{{{\boldsymbol{x}}_r}} \;\Biggl\{{\left\| {{{\boldsymbol{x}}_r}} \right\|_1}+ \\ &\left\langle {{\boldsymbol{u}}_r^{(k)},{{\boldsymbol{x}}_r} - {\boldsymbol{\alpha }}_r^{(k+1)}} \right\rangle +\frac{\rho }{2}\left\| {{{\boldsymbol{x}}_r} - {\boldsymbol{\alpha }}_r^{(k+1)}} \right\|_2^2\Biggl\} = \\ &\mathop {\arg \min }\limits_{{{\boldsymbol{x}}_r}} \;\Biggl\{{\left\| {{{\boldsymbol{x}}_r}} \right\|_1}+\frac{\rho }{2}\left\| {{{\boldsymbol{x}}_r} - \left( {{\boldsymbol{\alpha }}_r^{(k+1)} - \frac{{{\boldsymbol{u}}_r^{(k)}}}{\rho }} \right)} \right\|_2^2\Biggl\}.\end{split} $

引入如下软阈值算子：

(12)$ {\text{soft}}\;(\phi ,\lambda ) = \left\{ {\begin{array}{*{20}{l}} {\phi - \lambda ,\;\phi \geqslant \lambda ;} \\ {\phi +\lambda ,\;\phi \leqslant - \lambda ;} \\ {0,\qquad \left| \phi \right|{\text{ }} ＜ \lambda .\quad } \end{array}} \right. $

式中：$ \phi \in \bf{R} $，$ \lambda > 0 $. 式（11）的优化解可以表示为

(13)$ x_{ri}^{(k + 1)} = {\mathop{\rm soft}\nolimits} \left( {\alpha _{ri}^{(k + 1)} - \frac{{u_{ri}^{(k)}}}{\rho },\;\frac{1}{\rho }} \right). $

式中：${x_{ri}} $、${\alpha _{ri}} $和${u_{ri}} $分别为向量${{\boldsymbol{x}}_r} $、${{\boldsymbol{\alpha }}_r} $和${{\boldsymbol{u}}_r} $的第i个元素。

3）更新$ {{\boldsymbol{y}}_r} $. 从式(8)中去除不包含$ {{\boldsymbol{y}}_r} $的项，可以推导出

(14)$ \begin{aligned}{\boldsymbol{y}}_r^{(k + 1)} = & \mathop {\arg \min }\limits_{{{\boldsymbol{y}}_r}} \;\{\tau {\left\| {{{\boldsymbol{y}}_r}} \right\|_1} + \\ & \left\langle {{\boldsymbol{v}}_r^{(k)},{{\boldsymbol{y}}_r} + {{\boldsymbol{P}}_r}{\boldsymbol{\alpha }}_r^{(k + 1)} - {{\boldsymbol{f}}_r}} \right\rangle + \left\langle {{\boldsymbol{w}}_r^{(k)},{{\boldsymbol{y}}_r} - {\boldsymbol{s}}_r^{(k)}} \right\rangle + \\ & \left.\frac{\rho }{2}\left(\left\| {{{\boldsymbol{y}}_r} + {{\boldsymbol{P}}_r}{\boldsymbol{\alpha }}_r^{(k + 1)} - {{\boldsymbol{f}}_r}} \right\|_2^2 + \left\| {{{\boldsymbol{y}}_r} - {\boldsymbol{s}}_r^{(k)}} \right\|_2^2\right) \right\}= \\ & \mathop {\arg \min }\limits_{{{\boldsymbol{y}}_r}} \;\{\tau {\left\| {{{\boldsymbol{y}}_r}} \right\|_1} + \\ & \left.\rho \left\| {{{\boldsymbol{y}}_r} - \frac{1}{2}({{\boldsymbol{f}}_r} + {\boldsymbol{s}}_r^{(k)} - {{\boldsymbol{P}}_r}{\boldsymbol{\alpha }}_r^{(k + 1)} - {\rho^{-1} }({\boldsymbol{v}}_r^{(k)} + {\boldsymbol{w}}_r^{(k)}))}\right\} \right\|_2^2 = \\ & \mathop {\arg \min }\limits_{{{\boldsymbol{y}}_r}} \;\{\tau {\left\| {{{\boldsymbol{y}}_r}} \right\|_1} + \rho \left\| {{{\boldsymbol{y}}_r} - {\boldsymbol{b}}} \right\|_2^2\}.\end{aligned} $

式中：${\boldsymbol{b}} = ({{\boldsymbol{f}}_r} + {\boldsymbol{s}}_r^{(k)} - {{\boldsymbol{P}}_r}{\boldsymbol{\alpha }}_r^{(k + 1)} - {\rho ^{-1}}({\boldsymbol{v}}_r^{(k)} + {\boldsymbol{w}}_r^{(k)}))/2 $，且${\boldsymbol{b}} = \left[ {{b_1}} \right., \cdots ,{b_i},{\left. \cdots \right]^{\rm{T}}} $，则有$y_{ri}^{(k + 1)} = {\mathop{\rm soft}\nolimits}\; ({b_i},{\tau }/{{(2\rho) }}). $其中${y_{ri}} $表示向量${{\boldsymbol{y}}_r} $的第i个元素。

4）更新$ {{\boldsymbol{s}}_r} $. 从式(8)中去除不包含$ {{\boldsymbol{s}}_r} $的项，可以推导出

(15)$ \begin{split} {\boldsymbol{s}}_r^{(k+1)} = &\mathop {\arg \min }\limits_{{{\boldsymbol{s}}_r}}\Biggl\{ \gamma {{\boldsymbol{s}}_r}^{\rm{T}}{{\boldsymbol{L}}_{{G_r}}}{{\boldsymbol{s}}_r}+ \\ &\left\langle {{\boldsymbol{w}}_r^{(k)},{\boldsymbol{y}}_r^{(k+1)} - {{\boldsymbol{s}}_r}} \right\rangle +\frac{\rho }{2}\left\| {{\boldsymbol{y}}_r^{(k+1)} - {{\boldsymbol{s}}_r}} \right\|_2^2\Biggl\}.\end{split} $

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

(16)$ {\boldsymbol{s}}_r^{(k+1)} = {\left( {2\gamma {{\boldsymbol{L}}_{{G_r}}}+\rho {\boldsymbol{I}}} \right)^{ - 1}}\left( {{\boldsymbol{w}}_r^{(k)}+\rho {\boldsymbol{y}}_r^{(k+1)}} \right). $

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

(17)$ {\boldsymbol{u}}_r^{(k+1)} = {\boldsymbol{u}}_r^{(k)}+\rho \left( {{\boldsymbol{x}}_r^{(k+1)} - {\boldsymbol{\alpha }}_r^{(k+1)}} \right). $

(18)$ {\boldsymbol{v}}_r^{(k+1)} = {\boldsymbol{v}}_r^{(k)}+\rho \left( {{\boldsymbol{y}}_r^{(k+1)}+{{\boldsymbol{P}}_r}{\boldsymbol{\alpha }}_r^{(k+1)} - {{\boldsymbol{f}}_r}} \right). $

(19)$ {\boldsymbol{w}}_r^{(k+1)} = {\boldsymbol{w}}_r^{(k)}+\rho \left( {{\boldsymbol{y}}_r^{(k+1)} - {\boldsymbol{s}}_r^{(k+1)}} \right). $

6）迭代终止条件如下：

(20)$ {\left\| {{\boldsymbol{x}}_r^{(k+1)} - {\boldsymbol{\alpha }}_r^{(k+1)}} \right\|_\infty } \leqslant {\varepsilon _1}, $

(21)$ {\left\| {{\boldsymbol{y}}_r^{(k+1)}+{{\boldsymbol{P}}_r}{\boldsymbol{\alpha }}_r^{(k+1)} - {{\boldsymbol{f}}_r}} \right\|_\infty } \leqslant {\varepsilon _2}, $

(22)$ {\left\| {{\boldsymbol{y}}_r^{(k+1)} - {\boldsymbol{s}}_r^{(k+1)}} \right\|_\infty } \leqslant {\varepsilon _3}. $

式中：$ {\varepsilon _1}、{\varepsilon _2}、{\varepsilon _3} $为误差参数. 若迭代解不满足迭代终止条件，则按上述迭代步骤更新变量$ {{\boldsymbol{\alpha }}_r} $、$ {{\boldsymbol{x}}_r} $、$ {{\boldsymbol{y}}_r} $、$ {{\boldsymbol{s}}_r} $、$ {{\boldsymbol{u}}_r} $、$ {{\boldsymbol{v}}_r} $和$ {{\boldsymbol{w}}_r} $，直至满足条件.

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

对于式(8)中的变量$ \rho $，将其初始值设置为$ \rho = {10^{ - 2}} $，最大值设置为$ {\rho _{\max }} = {10^6} $，并在每次迭代中将其更新为$ \rho : = \min \;\left\{ {\eta \rho ,\;{\rho _{\max }}} \right\} $^{[18, 30-31]}.

假设图像块大小为$ l \times l $，基函数的数量为$ M $，向量$ {{\boldsymbol{f}}_r} $、$ {{\boldsymbol{s}}_r} $和$ {{\boldsymbol{\alpha }}_r} $的大小分别为$ {l^2} \times 1 $、$ {l^2} \times 1 $和$ M \times 1 $，矩阵$ {{\boldsymbol{P}}_r} $的大小为$ {l^2} \times M $. 由式（10）、（16）可知，第1、4个变量更新涉及矩阵乘法和逆运算. 对于大小为$ d \times d $的矩阵逆运算，计算复杂度为$ O\left( {{d^3}} \right) $，因此所提方法对于大小为$ l \times l $的图像块的完整计算复杂度为$ O\left( {{M^3}+M+{l^2}M+{l^6}} \right) $. 由于$ M $为基函数的数量，$ M < {l^2} $，所提方法对于图像块的复杂度为$ O\left( {{l^6}} \right) $.

对于给定大小为$ m \times n $的图像，假设$ m $和$ n $远大于$ l $，则大约有$ {{mn}}/{{{l^2}}} $个图像块，所提方法的整体计算复杂度为$ O\left( {mn\left( {{{{M^3}}}/{{{l^2}}}+{M}/{l^2}+M+{l^4}} \right)} \right) $. 因为$ M < {l^2} $，所提方法的整体计算复杂度为$ O\left( {mn{l^4}} \right) $.

采用合成图像、MSRA^[19]数据集和屏幕内容图像，评估所提SDGLR方法的性能. 合成图像是一组人工生成的图像，即在图像上手动添加文本. MSRA^[19]数据集是基准数据集. 屏幕内容图像是一组利用屏幕快照捕获的图像^[32].

实验采用准确率P (precision)、召回率R (recall)和F1指数作为评价指标，定义如下.

(23)$ {{P = }}\frac{{{\text{TP}}}}{{{\text{TP+FP}}}} \times 100{\text{%}} . $

(24)$ {{R = }}\frac{{{\text{TP}}}}{{{\text{TP+FN}}}} \times 100{\text{%}} . $

(25)$ {\text{F1 = 2}}\frac{{{{P}} {{R}}}}{{{{P+R}}}} \times 100{\text{%}} . $

式中：TP、FP和FN分别为真阳性(true positive)、假阳性(false positive)和假阴性(false negative)的像素数量.

为了验证所提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方法，使用交叉验证法选择参数$ \tau $、$ \gamma $和$ M $. 图像块的大小选择为与HEVC^[34]标准中的最大编码单元（coding units, CU）相同，$ l = 64 $. 对于SD-GFT，GFT基函数的数量$ M $和图像块大小$ l $与SDGLR算法中的设置相同，正则化参数$ \tau = 0.15 $.

如图1~3所示为不同方法在测试图像中的分割结果. 与LSRD、LAD、SDTVM和SR方法相比，SD-GFT和SDGLR方法采用图模型来捕捉图像的内在几何结构，能够更充分地刻画像素之间的相关性. 相对于LAD、SDTVM和SR方法，采用一组离散余弦变换基函数的线性组合表示背景部分，SD-GFT和SDGLR方法采用一组图傅里叶变换基函数的线性组合表示背景部分，利用图模型建立像素之间的联系. 这使得SD-GFT和SDGLR方法比采用离散余弦变换基函数表示背景的方法更加灵活，能够更好地利用像素之间的关联信息，获得更好的图像分割性能. 相对于SDTVM方法采用前景分量的全变差来促进前景像素的连通性，SDGLR方法采用GLR正则化项来刻画前景像素的连通性，使得相邻像素节点之间的信号值更加相似，促进前景文本和图形更加连续. 相对于SD-GFT方法，SDGLR方法添加了GLR正则化项来刻画前景像素的连通性，这使得前景的连通性有了明显的改善，例如图1第1幅测试图像中“strategic”一词的字母“st”和图1第2幅测试图像中“Thrones”一词的字母“s”. 这表明引入GLR项后，前景像素之间的连通性得到了增强. 当前景和背景是由不可区分的子空间表示时，SR不能实现有效的分割. 例如对于图2的第2张测试图像，利用SR方法不能有效地分割.

如表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的第1张测试图像为例，对SDGLR方法中需要调整的参数进行分析讨论.

正则项参数$ \tau $的灵敏性分析. 在SDGLR方法中，采用参数$ \tau $来权衡背景模型参数$ {{\boldsymbol{\alpha }}_r} $和前景$ {{\boldsymbol{s}}_r} $. 如图4所示为当$ \tau $为[0, 1.0]时的F1指数. 可以看出，当$ \tau = 0.15 $时，该方法的分割性能最佳.

正则项参数$ \gamma $的灵敏性分析. $ \gamma $为用于惩罚前景像素连通性的参数. 如图5所示为当$ \gamma $为[0, 1.0]时的分割效果. 可以看出，当$ \gamma = 0.5 $时，分割性能最佳.

GFT基函数的数量$ M $. 为了评估$ M $对最终分割结果的影响，如图6所示为使用不同数量基函数导出的分割结果图. 可以看出，当$ M = 10 $时，分割效果最佳.

图像块大小$ l $和数量. 在HEVC^[34]标准中，最大编码单元（coding units, CU）通常被设定为$ 64 \times 64 $或$ 32 \times 32 $. 选取较小的图像块可以降低运算复杂度，但是图像质量受到限制. 较大的图像块可以提高图像质量，但需要增加计算量. CU为$ 64 \times 64 $的图像块能够在计算复杂度和图像质量间取得较好的平衡点. 因为HEVC是比较成熟的标准，选择CU为$ 64 \times 64 $的图像块，可以使研究工作与已有研究工作保持一致. 如图7所示为由不同$ l $导出的分割结果. 可见，当$ l = 64 $时，分割性能最佳. 图像块的数量由原图像大小和图像块大小$ l $决定，给定$ l $的情况，原图越大，图像块数量越多，程序运行时间越长.

如图8所示为实验中F1与迭代次数N_i的关系. 从图8的F1变化趋势可以看出，在一定迭代次数后，指标的变化速度逐渐减缓，最终趋于稳定的常数值. 这表明所提出的方法在一定程度上已经收敛. 特别地，在保持较高F1的情况下，该方法能够在第12次迭代后达到收敛状态. 这说明所提方法的收敛效率较高，即在相对较少的迭代次数内取得较优的分割效果.

本文提出基于图信号处理和稀疏分解的图像前景背景分割方法，旨在将图像的前景与背景分离. 在SDGLR模型中，趋于平滑的背景区域可以通过GFT基函数的线性组合有效地表示. 在目标函数中添加GLR项来惩罚前景中的孤立点，以加强前景像素的连通性. 实验结果表明，利用提出的SDGLR方法，能够更好地刻画图像像素中的相关性，在视觉和定量评估方面取得了优异的效果. 在接下来的工作中，将基于图模型的图像前景背景分割方法扩展到其他场景，如视频的前景背景分割.