0 引言

1 预备知识

2 基于惰性随机游走的显著性检测算法

图 1为基于惰性随机游走的显著性检测算法流程。第1步是图像的超像素分割及无向图的构造；第2步通过选取两条边界上的超像素作为惰性种子节点，利用惰性随机过程生成初始显著性图，有效的抑制背景；然后，利用凸包等先验信息对初始显著性图进行修正；最后，通过在初始显著性图中选取显著性最高的前景像素作为惰性节点，再次利用惰性随机游走过程生成最终的显著性图，达到突出和融合前景显著性目标的目的。

图 1 本文流程图

Fig. 1 The pipeline of our method

2.1 超像素分割及图的构造

2.2 基于惰性随机游走的显著性检测

生物视觉的研究表明，人类在观察一个场景时，总是会在自己感兴趣或是显著的目标上以较高的概率停留，而在不感兴趣的区域将有很大的概率直接转移注意力。惰性随机游走过程很好地描述了人类这一视觉感知过程。惰性随机游走是一类特殊的马尔可夫随机游走过程，在该过程中，每一个节点都以一定的概率1-α(0 < α < 1)停留在自身，以概率α转移到其他状态，如图 2所示。在基于惰性随机游走的显著性检测过程中，如果选取先验的显著性较高的像素顶点作为惰性种子节点，即赋予较小的惰性因子α，那么该节点将会以较大的概率1-α停留在原状态(显著状态)，而以较小的概率如α转移到其他状态(非显著状态)。

图 2 本文算法的自环图

Fig. 2 Our LRW algorithm with self-loops

从图 2可以看出，相较于传统随机游走算法，本文研究的惰性随机游走在每一个顶点v_i上添加了一个自环，用来表示惰性随机游走中每一个顶点v_i都有一个非零的概率停留在自身。因此新的邻接矩阵可表示为

$ {\widehat W_{i,j}} = \left\{ {\begin{array}{*{20}{l}} {1 - \alpha }&{i = j}\\ {\alpha {w_{i,j}}}&{i \sim j}\\ 0&{其他} \end{array}} \right. $

(3)

式中, i~j表示v_i和v_j相邻接，α是惰性因子，且α∈(0, 1)。可以看出$ \boldsymbol{\widehat W} $是一个系数对称带状矩阵且所有非零元素都为正。

根据图上的邻接矩阵$ \boldsymbol{\widehat W} $，可以定义该图的拉普拉斯矩阵

$ \boldsymbol{\widehat L} = \boldsymbol{D} - \alpha \boldsymbol{W} $

(4)

即

$ {\widehat L_{i,j}} = \left\{ {\begin{array}{*{20}{l}} {{d_i}}&{i = j}\\ { - \alpha {w_{i,j}}}&{i \sim j}\\ 0&{其他} \end{array}} \right. $

(5)

对拉普拉斯矩阵进行正则化，仍采用符号$ \boldsymbol{\widehat L} $表示, 即

$ \boldsymbol{\widehat L} = \boldsymbol{I} - \alpha {\boldsymbol{D}^{ - \frac{1}{2}}}\boldsymbol{W}{\boldsymbol{D}^{ - \frac{1}{2}}} $

(6)

与普通随机游走过程相比，修正后的邻接矩阵主对角线元素均为非零，即每一个节点都存在一个非零的概率停留在自身。这与人类的视觉观察也是一致的，人类在观察一幅图像时不可能做到直接将注意力集中在显著区域而无视背景等其他区域。每个像素都有可能获取视觉系统的注意力，只是根据自身特征及与周围区域的对比等因素导致该概率大小不同，最终通过神经系统的快速判断(类似于惰性随机游走过程)做出判断。

在惰性随机游走中，对于每一个顶点，都以(1-α)的概率停留在当前顶点，以α的概率转移到任意节点，所以相较于普通的随机游走，惰性随机游走的转移概率矩阵可表示为

$ \boldsymbol{\widehat P} = \left( {1 - \alpha } \right)\boldsymbol{I} + \alpha {\boldsymbol{D}^{ - 1}}\boldsymbol{W} $

(7)

即

$ {\widehat P_{i,j}} = \left\{ {\begin{array}{*{20}{l}} {1 - \alpha }&{i = j}\\ {\alpha {w_{i,j}}/{d_i}}&{i \sim j}\\ 0&{其他} \end{array}} \right. $

(8)

式中，I表示单位矩阵，d_i表示第i个顶点的度。

基于图上的随机游走理论，对于0 < α < 1，惰性随机游走保证收敛到唯一的稳定状态π，且满足平衡方程

$ \boldsymbol{\widehat W}\boldsymbol{\pi} = \boldsymbol{\pi} $

(9)

每个顶点的平稳状态可表示为

$ {\pi _i} = {d_i}/\sum\limits_{i \in V} {{d_i}} $

(10)

可以看出每个节点最终的平稳状态与其度成正比，而且当分布达到稳定状态后随机游走的分布就不会发生变化。惰性随机游走的往返时间描述了当该过程收敛到平稳状态时，随机游走过程从一个顶点到达另一个顶点，又返回原顶点的时间之和。往返时间描述了两个顶点之间的相似程度，往返时间越短表示两个顶点特征越相似，反之表示两个顶点存在较大的状态差异。

正则化后的往返时间表示为

$ {\widehat {CT}_{i,j}} = \left\{ {\begin{array}{*{20}{c}} 1&{i = j}\\ {1 - \widehat L_{i,j}^{ - 1}}&{i \ne j} \end{array}} \right.\; $

(11)

本文以惰性随机游走的往返时间作为显著性的判断准则。与普通随机游走过程使用的单程的期望时间或吸收时间相比，利用往返时间来度量像素的显著性更为鲁棒。

根据摄影学原则及人类观察事物的习惯，图像的边界以较大的概率为背景，这一原则在近期许多显著性研究工作中被采用和验证。因此，分别选取图像的下边界和左边界超像素作为背景种子节点(如图 2所示)，定义特征函数y={1, 1, 0, 0, …, 1}，y(i)=1表示当前超像素V_i为背景种子节点。通过对背景节点赋予较大的惰性概率1-α，而对其他节点赋予较小的惰性因子α，从而构造一个基于背景先验的惰性随机游走过程。利用式(11)可以计算出任意两个顶点V_i, V_j之间的往返时间$ {\boldsymbol{\widehat {CT}}_{i,j}} $，而每个顶点(超像素)到到背景种子顶点的往返时间可以表示为$ \boldsymbol{\widehat {CT}} * \boldsymbol{y} $。根据上面的分析，到背景种子顶点的往返时间越长就表示当前顶点(超像素)与背景顶点的差异越大，即显著性越强。因此，每个超像素顶点的显著性与该往返时间成正比，利用正则化后的往返时间来表示每个顶点的显著性，即

$ {\boldsymbol{f}_{\rm{b}}} = \boldsymbol{\widehat {CT}} * \boldsymbol{y} $

(12)

式中, f_b∈Rⁿ表示每个超像素{R_i, i=1, 2, …, n}的显著性。

算法1详细描述了以图像下边界为背景种子顶点的基于惰性随机游走的显著性检测过程。

分别利下边界及左边界超像素作为背景种子顶点计算得到显著性f_tb及f_lb，然后融合得到基于背景先验的显著图(如图 3所示)，即

$ {\boldsymbol{S}_{\rm{b}}} = {\boldsymbol{f}_{{\rm{tb}}}} \times {\boldsymbol{f}_{{\rm{lb}}}} $

(13)

图 3 基于背景的显著性检测结果

Fig. 3 The saliency map based on background ((a) input map; (b) the seed vertex made by left edge; (c) the seed vertex made by down edge; (d) fused map; (e) ground true)

算法1基于下边界背景先验的显著性检测：

1) 选取图像的下边界超像素V_t1, V_t2, …, V_tm作为背景种子顶点，m表示下边界超像素的个数，定义特征向量y；

2) 为背景顶点赋予较大的惰性概率1-α，取α=0.9；

3) 建立关于邻接矩阵$ \boldsymbol{\widehat W} $的图拉普拉斯矩阵$ \boldsymbol{\widehat L} $；

4) 计算往返时间$ {\boldsymbol{\widehat {CT}}_{i,j}} $；

5) 输出显著性${\boldsymbol{f}_{\rm{tb}}} = \boldsymbol{\widehat {CT}} * \boldsymbol{y} $。

2.3 基于先验信息的背景显著图修正

2.3.1 基于凸包的中心先验

2.3.2 基于颜色对比度的先验

研究表明人类的视觉系统对视觉信号的颜色对比度是非常敏感的，因此采用颜色对比度作为先验对背景显著性图进行修正。此先验是利用每个像素和其他像素颜色的对比度来定义的。元素的唯一性表示一个元素与其他所有元素相比的稀有性，可以表示为

$ {U_i} = \sum {w\left( {{p_i},{p_j}} \right){{\left\| {{c_i} - {c_j}} \right\|}^2}} \; $

(15)

式中，p_i表示超像素R_i的位置，c_i表示超像素R_i的颜色平均值。w(p_i, p_j)为高斯权重，表示为

$ w\left( {{p_i},{p_j}} \right) = \frac{1}{{{Z_i}}}\exp \left( { - \frac{1}{{2{\sigma ^2}}}{{\left\| {{p_i} - {p_j}} \right\|}^2}} \right)\; $

(16)

式中，Z_i是归一化因子，可以确保$ \sum {w\left( {{p_i},{p_j}} \right) = 1} $。在一幅图像中，如果一个区域从色彩上来看，明显区别于它邻近的区域，那么运用这个先验就能有效地把它给标记出来。从另一方面来看，基于颜色对比度的先验算法对于与背景没有显著颜色区别的图像将不能有效地标记显著区域。显著性表示唯一性，但反之并不成立。所以基于颜色对比度的先验还要看一个元素是否分布到一个独特的区域，元素的分布为

$ {D_i} = \sum\limits_{\left( {i,j \in E} \right)} {w\left( {{c_i},{c_j}} \right)} {\left\| {{p_i} - {\mu _i}} \right\|^2} $

(17)

式中，$ {\mu _i} = \sum\limits_{\left( {i,j \in E} \right)} {w\left( {{c_i},{c_j}} \right)} {p_j} $是颜色c_i的加权平均位置。基于颜色对比度的先验图可表示为

$ {\boldsymbol{S}_{{\rm{hc}}}} = {U_i}\exp \left( { - k \cdot {D_i}} \right)\; $

(18)

此先验对于目标背景颜色对比强烈的图具有较好的区分效果。利用上述两种先验信息对基于背景的显著性检测得到的背景显著图进行修正(图 4)，即

$ {\boldsymbol{S}_{{\rm{bc}}}} = {\boldsymbol{S}_{\rm{b}}} \times {\boldsymbol{S}_{{\rm{ce}}}} \times {\boldsymbol{S}_{{\rm{hc}}}} $

(19)

图 4 基于背景的显著图与先验图的融合

Fig. 4 Fusion with the prior map and the saliency map based on the background ((a) input map; (b) initial saliency map; (c) center prior; (d) color prior; (e) fused map; (f) ground true)

2.4 基于前景的随机游走显著性检测

基于背景先验的显著性图S_bc有效地抑制了背景，但前景显著性还比较繁冗，不能有效地突出真正的显著性目标。为此，本文研究基于前景的惰性随机游走显著性检测算法。根据得到的背景显著图S_bc筛选显著性最大的k个顶点作为前景种子顶点，通过为种子顶点赋予较大的惰性概率，再重复进行一次惰性随机游走。选取k与超像素的个数相关为k=(n)^1/2。根据2.2节，当该随机过程达到平衡时，每个超像素顶点到前景种子顶点的往返时间可表示为$ {\boldsymbol{f}_{\rm{f}}} = \boldsymbol{\widehat {CT}} * \boldsymbol{y} $，y(i)=1表示当前超像素V_i为前景超像素顶点。由于到前景种子顶点的往返时间越短表示当前超像素顶点与种子顶点的相似度越高，即显著性越高，因此基于前景的显著性与往返时间成反比，定义最终由前景得到的显著性S为

$ \boldsymbol{S} = 1 - \boldsymbol{\widehat {CT}} * \boldsymbol{y} $

(20)

本文整体算法如算法2所示。

算法2基于惰性随机游走的显著性检测：

1) 图像的超像素分割{R₁, R₂, …, R_n}及无向图构造G=(V, E)；

2) 基于左边界及下边界为背景种子顶点的显著性检测S_b=S_tb*S_lb；

3) 基于凸包及全局对比度先验的背景显著性修正S_bc=S_b*S_ce*S_hc；

4) 通过选取显著的前景顶点作为种子顶点，执行基于惰性随机游走的显著性检测$ \boldsymbol{S} = 1 - \boldsymbol{\widehat {CT}} * \boldsymbol{y} $；

5) 输出最终的显著性S。

最终的显著图与初始显著图的对比如图 5所示。

图 5 最终的显著图与初始显著图的对比

Fig. 5 Comparison of the final saliency map with the initial saliency map ((a) input map; (b) saliency map based on the background; (c) fused map; (d) saliency map based on the foreground; (e) ground true)

3 实验分析与比较

在MSRA-1000数据库上与当前比较先进的算法进行对比。这些算法包括：HS^[18]、SF^[19]、XIE^[20]，FT^[9]、MAP^[14]、GS^[11]、SVO^[21]、SER^[22]、CB^[23]、LR^[24]、SM^[25]、GB^[26]、CA^[27]、IT^[6]、SR^[10]。计算了它们的精确率—召回率曲线和F—检验的分数。并通过不断改变阈值，得到成对的精确率—召回率数据，来画出它们的曲线。使用自适应阈值算法来计算F—检验的分数，它是用平均召回率和平均精确度来定义的，定义

$ {F_\beta } = \frac{{\left( {1 + {\beta ^2}} \right)Pr \times Re}}{{{\beta ^2}Pr + Re}} $

(21)

式中，β²=0.3，用于平衡精确率和召回率的影响，Pr表示精确率(Precision)，Re表示召回率(Recall)。为了公平起见，直接使用原作者提供的结果或是根据原作者提供的代码计算出结果。

首先，通过仿真实验分析了惰性因子α对显著性结果的影响。图 6展示了α分别取0.5，0.7及0.9的不同结果。可以看出，当惰性因子α取值比较小时，惰性随机游走过程无法很好地抑制背景。随着α取值的不断增大，背景逐渐消失，前景显著性目标得到增强。在本文的其他实验中，惰性因子α均被设为0.9。

图 6 不同α取值的显著图比较

Fig. 6 Comparison of the saliency map with different α values ((a) input map; (b) α=0.5; (c) α=0.7; (d) α=0.9; (e) ground true)

进行惰性随机游走算法与普通随机游走算法^[13]及吸收随机游走算法^[14]生成的显著图的对比实验。图 7为3种算法仅进行一次随机游走的结果，可以看出，本文算法结果明显优于其他两种算法，即使只进行一次惰性随机游走，已经能够明显突出显著性区域。

图 7 3种基于随机游走的显著性检测算法效果比较

Fig. 7 Comparison of the saliency maps by three different random walk based algorithms ((a) input image; (b) saliency map based on the random walk; (c) saliency map based on markov absorption probabilities; (d) saliency map based on the lazy random walk; (e) ground true)

图 8从整体上分析了本文算法与相关算法的性能对比。无论是精确率-召回率曲线还是F—检验分数，本文算法在MSRA1000数据库取得了最好的结果。

图 8 MSRA-1000数据库上的实验结果

Fig. 8 Results on MSRA-1000 dataset ((a)(b) precision-recall curves of all test methods; (c) average)

图 9展示了本文及相关算法在不同类型图像上的视觉效果。前两行前景较暗，所以结果中很多算法不能较好地抑制背景，本文算法在这一点上做的较好。对于背景中存在异常区域的图像如第3行，由于沙子中存在黑色的石头导致基于对比度的算法HC、LC等错误的点亮背景，而与前景近似的背景又导致低秩恢复LR和边界融合LU不能有效地区分背景前景，与之相比基于随机游走的算法就更为有效地点亮前景抑制背景。第4行图像中前景与背景相差较大，但前4种算法依旧不能有效点亮前景。第58行中阴影和树影的存在也是造成结果误差较大的因素，本文算法有效地抑制了背景。第9行图像中存在几种不同的背景，本文算法能够较为明确地突出前景。在最后两行的多物品显著性检测实例中，本文结果不仅点亮了全部目标，而且能够清晰的区分每一个目标。

图 9 显著图对比示例

Fig. 9 Qualitative comparison of our method and other typical methods on some examples ((a) input map; (b) HC; (c) RC; (d) LU; (e) LR; (f) MAP; (g) saliency map based on the lazy random walk; (h) ground true)

4 结论

参考文献

[1] Rutishauser U, Walther D, Koch C, et al.Is bottom-up attention useful for object recognition?[C]//Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington DC, USA:IEEE, 2004, 2:Ⅱ-37-Ⅱ-44.[DOI:10.1109/CVPR.2004.1315142]
[2] Walther D, Koch C. Modeling attention to salient proto-objects[J]. Neural Networks , 2006, 19 (9) : 1395–1407. DOI:10.1016/j.neunet.2006.10.001
[3] Chen T, Cheng M M, Tan P, et al. Sketch2 Photo:internet image montage[J]. ACM Transactions on Graphics , 2009, 28 (5) : #124. DOI:10.1145/1618452.1618470
[4] Wang X J, Ma W Y, Li X.Data-driven approach for bridging the cognitive gap in image retrieval[C]//Proceedings of the 2004 IEEE International Conference on Multimedia and Expo.Taipei, China:IEEE, 2004, 3:2231-2234.[DOI:10.1109/ICME.2004.1394714]
[5] Mahadevan V, Vasconcelos N.Saliency-based discriminant tracking[C]//Proceedings of 2009 IEEE Conference on Computer Vision and Pattern Recognition.Miami, FL:IEEE, 2009:1007-1013.[DOI:10.1109/CVPR.2009.5206573]
[6] Itti L, Koch C, Niebur E. A model of saliency-based visual attention for rapid scene analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence , 1998, 20 (11) : 1254–1259. DOI:10.1109/34.730558
[7] Borji A, Itti L.Exploiting local and global patch rarities for saliency detection[C]//Proceedings of the 2012 IEEEConference on Computer Vision and Pattern Recognition.Providence, RI:IEEE, 2012:478-485.[DOI:10.1109/CVPR.2012.6247711]
[8] Guo C L, Ma Q, Zhang L M.Spatio-temporal saliency detection using phase spectrum of quaternion fourier transform[C]//Proceedings of 2008 IEEE Conference on Computer Vision and Pattern Recognition.Anchorage, AK:IEEE, 2008:1-8.[DOI:10.1109/CVPR.2008.4587715]
[9] Achanta R, Hemami S, Estrada F, et al.Frequency-tuned salient region detection[C]//Proceedings of 2009 IEEE Conference on Computer Vision and Pattern Recognition.Miami, FL:IEEE, 2009:1597-1604.[DOI:10.1109/CVPR.2009.5206596]
[10] Hou X D, Zhang L Q.Saliency detection:a spectral residual approach[C]//Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition.Minneapolis, MN:IEEE, 2007:1-8.[DOI:10.1109/CVPR.2007.383267]
[11] Wei Y C, Wen F, Zhu W J, et al.Geodesic saliency using background priors[C]//Proceedings of the 2th European Conference on Computer Vision.Berlin Heidelberg:Springer, 2012:29-42.[DOI:10.1007/978-3-642-33712-3_3]
[12] Shen J B, Du Y F, Wang W G, et al. Lazy random walks for superpixel segmentation[J]. IEEE Transactions on Image Processing , 2014, 23 (4) : 1451–1462. DOI:10.1109/TIP.2014.2302892
[13] Kim J S, Sim J Y, Kim C S. Multiscale saliency detection using random walk with restart[J]. IEEE Transactions on Circuits and Systems for Video Technology , 2014, 24 (2) : 198–210. DOI:10.1109/TCSVT.2013.2270366
[14] Sun J G, Lu H H, Liu X P. Saliency region detection based on Markov absorption probabilities[J]. IEEE Transactions on Image Processing , 2015, 24 (5) : 1639–1649. DOI:10.1109/TIP.2015.2403241
[15] Hu Z P, Meng P Q. Graph presentation random walk salient object detection algorithm based on global isolation and local homogeneity[J]. Acta Automatica Sinica , 2011, 37 (10) : 1279–1284. [ 胡正平, 孟鹏权. 全局孤立性和局部同质性图表示的随机游走显著目标检测算法[J]. 自动化学报 , 2011, 37 (10) : 1279–1284. DOI:10.3724/SP.J.1004.2011.01279 ]
[16] Yu J G, Tian J W. Saliency detection using midlevel visual cues[J]. Optics Letters , 2012, 37 (23) : 4994–4996. DOI:10.1364/OL.37.004994
[17] Achanta R, Shaji A, Smith K, et al. SLIC superpixels compared to state-of-the-art superpixel methods[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2012, 34 (11) : 2274–2282. DOI:10.1109/TPAMI.2012.120
[18] Yan Q, Xu L, Shi J P, et al.Hierarchical saliency detection[C]//Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.2013:1155-1162.[DOI:10.1109/CVPR.2013.153]
[19] Perazzi F, Krahenbühl P, Pritch Y, et al.Saliency filters:contrast based filtering for salient region detection[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition.Providence, RI:IEEE, 2012:733-740.[DOI:10.1109/CVPR.2012.6247743]
[20] Xie Y L, Lu H C, Yang M H. Bayesian saliency via low and mid level cues[J]. IEEE Transactions on Image Processing , 2013, 22 (5) : 1689–1698. DOI:10.1109/TIP.2012.2216276
[21] Chang K Y, Liu T L, Chen H T, et al.Fusing generic objectness and visual saliency for salient object detection[C]//Proceedings of the 2011 International Conference on Computer Vision.Barcelona:IEEE, 2011:914-921.[DOI:10.1109/ICCV.2011.6126333]
[22] Seo H J, Milanfar P. Static and space-time visual saliency detection by self-resemblance[J]. Journal of Vision , 2009, 9 (12) : 15. DOI:10.1167/9.12.15
[23] Jiang H Z, Wang J D, Yuan Z J, et al.Automatic salient object segmentation based on context and shape prior[C]//Proceedings of the 22nd British Machine Vision Conference.Dundee:BMVC, 2011.[DOI:10.5244/C.25.110]
[24] Shen X H, Wu Y.A unified approach to salient object detection via low rank matrix recovery[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition.Providence, RI:IEEE, 2012:853-860.[DOI:10.1109/CVPR.2012.6247758]
[25] Jiang Z L, Davis L S.Submodular salient region detection[C]//Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.Portland, OR:IEEE, 2013:2043-2050.[DOI:10.1109/CVPR.2013.266]
[26] Harel J, Koch C, Perona P.Graph-based visual saliency[C]//Proceedings of Advances in Neural Information Processing Systems 19.Vancouver:MIT Press, 2006:545-552.
[27] Goferman S, Zelnik-Manor L, Tal A. context-aware saliency detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2012, 34 (10) : 1915–1926. DOI:10.1109/TPAMI.2011.272
[28] Cheng M M, Zhang G X, Mitra N J, et al.Global contrast based salient region detection[C]//IEEE Transactions on Pattern Analysis&Machine Intelligence, 2011, 37(3):409-416.[DOI:10.1109/CVPR.2011.5995344]
[29] Sun J, Lu H C, Li S F.Saliency detection based on integration of boundary and soft-segmentation[C]//Proceedings of the 19th IEEE International Conference onImage Processing.Orlando, FL:IEEE, 2012:1085-1088.[DOI:10.1109/ICIP.2012.6467052]