结构化Krylov-SVD分解的显著性目标检测算法

郑维佳，张荣国，胡 静，赵 建，刘小君

(1.太原科技大学 计算机科学与技术学院，山西 太原 030024；2.合肥工业大学 机械工程学院，安徽 合肥 230009)

0 引 言

显著性目标检测在图像处理领域应用广泛，如目标检测[1]、基于内容的图像检索[2]和图像压缩和重定位[3-4]。

现有的显著性模型大致分为两类：生物模型和计算模型。生物学模型通常是要找到一些最能引起人们注意的点，因此所得的显著图通常是稀疏且模糊的，并限制了它们的应用范围，主要用于预测眼球注视。相反，受生物模型启发的计算模型旨在发现从周围区域突出的物体。目前的计算模型主要分为有监督的自上而下的显著性目标检测[5]和无监督的自下而上的显著性目标检测[6]。最近，一些研究人员将自上而下的高级先验与自下而上的低级图像特征相结合，并引入到统一的显著性目标检测框架。其中具有代表性的方法是将低秩矩阵恢复理论应用于显著性目标检测[7-9]。现有的基于低秩矩阵恢复的显著性目标检测模型通常将图像分为两个部分：高度冗余的图像部分(背景区域)和稀疏的显著部分(前景区域)[10]。这些方法可以计算给定图像的显著图并检测显著目标，但是它们通常假设稀疏矩阵中的每个元素是独立的，而忽略了它们之间的潜在关系和结构，导致生成的显著图出现发散或不完整现象。

为解决这些问题，Peng等人[11]提出结合低秩和结构化稀疏矩阵分解模型(SMD)，然而该模型仍然没有解决迭代导致的高计算复杂度问题，从而限制了该模型在大规模特征矩阵应用中的可扩展能力。针对上述问题，文中提出基于无监督的低秩恢复显著性检测算法，该算法的关键思想在于：(1)提出了Krylov-SVD算法利用奇异值分解(SVD)对大型稀疏矩阵求前k个特征值的精确解；(2)提出了树形结构稀疏诱导范数来约束前景矩阵S，换句话说，先前的研究对前景矩阵中的元素默认为是相互独立、互不影响的，因此忽略了图像像素或图像块之间空间上的连续性和模式上的相似性。这就导致了模型产生的前景是离散的，不连续的，支离破碎的。为了评估算法的显著性检测性能，引入MSRA10K[12]、SOD[13]和ECSSD[14]三个数据集，并和现有的十一种算法进行对比。实验结果表明，文中提出的基于结构化低秩矩阵Krylov-SVD分解的显著性目标检测算法在显著性目标检测方面有良好表现。

1 Arnoldi模型理论基础

低秩表示为图像处理提供了新的思路和新方法。随着低秩表示在图像处理方面的深入研究，现代迭代子空间方法中Arnoldi方法是最典型的一类适用于计算大型低秩非对称矩阵的Krylov子空间法。

给定具有如下形式的线性时不变系统：

(1)

其中，a∈Rn×n是常系数矩阵，b,c∈Rn是常数向量，x(t)∈Rn是系统的状态变量，u(t)∈R是系统的输入变量，y(t)∈R是系统的输出变量。假设线性时不变系统的初始状态为零，通过拉普拉斯变换后得到传递函数为H(s)=cT(sI-a)-1b。任取s0∈C，使得s0I-a非奇异。作变换s0=s0+σ，令：

F=-(s0I-a)-1,l=(s0-a)-1b

则线性时不变系统(1)可变为如下系统：

(2)

其传递函数为H(σ)=cT(I-σF)-1l。

设V=(v1,v2,…,vr)(rn)是由F及l应用r步传统Arnoldi算法得到的标准列正交矩阵，则Q构成Krylov子空间Kr(F,l)的一组基，即：

Kr(F,l)=span{l,Fl,…,Fr-1l}=colspan{Q}

以Q作为变换矩阵，可得到线性时不变系统(2)的降阶系统。

由于Arnoldi算法只涉及矩阵与某些向量的乘积，因此可充分利用矩阵的稀疏性和其结构特征对其特征值进行求解，Krylov-SVD重启方法就是在此方法的基础上结合奇异值分解技术提出的[15-16]。

2 结构化Krylov-SVD分解的低秩矩阵表示

2.1 低秩矩阵的Krylov-SVD分解

Shen等人[17]将输入图像的特征矩阵F粗略看作是一个低秩矩阵L加上一个稀疏矩阵S，即F=L+S，通过解这一模型来获取显著性目标，即：

(3)

式中，rank(•)表示矩阵的秩函数，秩函数是一个NP难问题，为解决式(3)问题通常将求解秩函数转化为核范数的求解，并利用矩阵奇异值之和来求解该核范数，即：

假设输入图像I被划分为n个非重叠超像素P={P1,P2,…,Pn}。从每个块Pi中提取一个D维特征向量Ii∈Rm，则I可以由n个特征向量表示为F={I1,I2,…,In}∈Rm*n。利用Krylov-SVD分解可以将特征矩阵F分解为低秩矩阵L和稀疏矩阵S。

设F∈Rm*n特征矩阵的奇异值分解为：

UTFV=diag(|λ1|,|λ2|,…,|λn|)

其中，U∈Rn*n、V∈Rn*n是正交矩阵，且F的奇异值满足|λ1|≥|λ2|≥…≥|λn|。

令：

V=Udiag(ε1,ε2,…,εn)

计算出UTV的对角矩阵diag(ε1,ε2,…,εn)，其中：

由对称矩阵的谱分解及其奇异值分解之间的关系可推出：对实对称矩阵而言，其奇异值就是其特征值的绝对值。可得F的特征值为：

λ(T)=diag(|λ1|,|λ2|,…,|λn|)*diag(ε1,ε2,…,εn)=diag(λ1,λ2,…,λn)

设λ(T)是SVD分解的标准型对角矩阵，其中T=diag(|λ1|,|λ2|,…,|λr|),式中u∈Rr*r、v∈Rr*r是正交矩阵，且：

v=udiag(ε1,ε2,…,εr)

其中：

则由λ(T)=(λ1,λ2,…,λr)*(ε1,ε2,…,εr)计算正交矩阵U2∈Rr*r，使得：

式中，λ(T1)=(λ1,λ2,…,λk)*(ε1,ε2,…,εk),j=1,2,…,k，即λ(T1)的特征值均位于主对角线上且按降序排列。

取其两端前k列可得：

(4)

通过Householder变换计算正交矩阵Q∈Rk*k，使得QTT1Q=Hk。经式(4)计算可得图像背景低秩矩阵L，即：

L=Q×H

2.2 结构化Krylov-SVD分解的低秩矩阵表示

图1 基于超像素构造的索引树

基于预定义的索引树，加权结构化稀疏范数定义为：

基于结构化低秩矩阵Krylov-SVD分解的显著性目标检测具体算法步骤如下所示：

输入：从给定图像数据集中选取一幅图像；

输出：经算法处理后的显著性图像。

(1)在通常情况下选择两个正整数r和k(k

(2)通过Arnoldi算法得到r步Arnoldi分解：

(5)利用Krylov-SVD重启方法以及收敛和锁定技术，产生一个长度为k的Arnoldi分解：

(6)利用Arnoldi过程将该分解扩展为一个长度为r的Arnoldi分解：

然后转步骤(2)。

3 实验结果及分析

在本节中，采用了三个数据集十一种算法进行了广泛的实验以验证算法的有效性。三个数据集为：MSRA10K数据集中包含10 000幅图像，每幅图像中有一个显著对象；SOD数据集中包含300幅图像，每幅图像中背景复杂且有多个显著对象；ECSSD包含1 000个背景混乱的图像。十一种结合先验信息的显著性检测算法为GVBS[18]、FT[19]、RPCA[20]、SF[14]、SLR[8]、RBD[21]、SMD[10]、HCN[22]、HCNs[23]、SC[24]、FBS[25],其中RPCA、SLR、SMD是基于低秩恢复的显著性算法。文中实验是在Win10，64位操作系统，Intel(R) Core(TM)i7-8750H CPU 2.2 GHz，RAM 16 GB环境下运行。

3.1 算法的稳定性和运行时间对比

实际应用中，算法的稳定性和耗时都是值得关注的问题，但是在以往研究中关于这方面的工作较少。因此，文中将使用1 000幅显著图像来分析算法的稳定性和耗时，将算法的耗时定义为：从输入图像到输出显著图所需要的时间。对1 000张图像运行1次取耗时平均值，结果如表1所示。由表1可以看出：在W×H的显著图像上，文中算法耗时低于SMD算法能达到1.24帧/秒，且在计算过程中图像像素可压缩至W×53，所以文中算法可满足实时性要求。

表1 视觉显著性模型的耗时

3.2 显著性算法对比实验

为了进一步评估算法的优越性，本节将采用PR曲线、AUC值、F-measure值以及平均绝对误差(MAE)[6]这四种评价指标和现有的十一种算法：GVBS、RPCA、 FT、SF、SLR、RBD、SC、SMD、HCN、HCNs、FBS作对比以进行系统地比较，在MSRA10K数据集、SOD数据集和ECSSD数据集上进行定性、定量测试。图2为三个数据集的ROC曲线，图3提供了显著图的定性比较。此外，表2列出了在AUC、F-measure和MAE评估指标上的评估结果。结合图表可以看出，在大多数情况下，算法在三个数据集上表现优异。

图2 ROC曲线

图3 不同显著性检测方法分别在MSRA10K、SOD、ECSSD数据集上的显著目标图

表2 不同显著性检测方法在三个数据集上的指标得分

续表2

在表2中提供的算法与其他算法的定量比较，从图2和图3的定性比较中可以看到，RPCA算法和SLR算法利用拉格朗日方法生成的低秩矩阵无法生成统一的检测结果。SMD算法优于以上两种算法，然而SMD算法使用拉普拉斯正则化生成的低秩矩阵无法得到边界清晰的显著目标图，相比之下，文中使用结构化低秩矩阵Krylov-SVD分解，更加注重图像中的空间结构，容易得到完整的显著目标。从表2的定量比较可以看出，文中的低秩恢复算法都大大优于SMD算法、RPCA算法和SLR算法。值得注意的是，在MSRA10K和SOD数据集上，文中显著性算法略优于其他显著性算法。而在ECSSD数据集上，就所有三个指标而言，文中的低秩恢复算法甚至优于层级融合的HCNs算法和HCN算法。结合图表信息可以得出两个结论：首先，结构化低秩矩阵Krylov-SVD分解算法在背景复杂的图像中表现优异。其次，Krylov-SVD分解可快速求解低秩矩阵。

4 结束语

结合低秩矩阵Krylov-SVD分解和索引树结构化，提出了一种基于结构化Krylov-SVD分解的低秩矩阵恢复算法，并将其应用于显著性目标检测。该算法通过Krylov-SVD分解求解图像低秩矩阵和索引树增加低秩矩阵的空间结构，得到最终显著图。将文中算法与现有的十一种算法，在MASK10K、SOD、ECSSD三个公开数据集上进行测试，结果表明文中算法运算快速简洁，而且可获得显著目标完整、结构紧凑的显著性分割结果。