2. 智能技术与系统国家重点实验室, 北京 100084 ;
3. 清华信息科学与技术国家实验室, 北京 100084
2. State Key Laboratory of Intelligent Technology and Systems, Beijing 100084, China ;
3. Tsinghua National Laboratory for Information Science and Technology, Beijing 100084, China
显著性检测重在模拟人类的视觉注意机制,是计算机视觉、机器人技术以及计算机图形学等多个领域的重要研究课题; 在定位物体、排除干扰、提高计算效率等方面具有重要的理论研究价值和实际应用价值。当前显著性检测算法已经在物体检测[1]、图像分割[2]、图像检索[3]以及物体识别、图像和视频压缩、基于内容的图像编辑、注意机制引导的人机交互等多个领域得到广泛应用。
尽管显著性检测[4]已经有近20年的研究历史,也取得了长足进步,但当前面对的最大挑战包括: 1) 图像背景杂乱; 2) 图像背景中包含有与显著物体相同的颜色或纹理等表观特征; 3) 图像构成与一般的构图经验不符,例如图像中的显著物体过大或者过小。
当前,多数显著区域检测算法通过直接计算图像中每个像素或图像块与其一定范围内邻域的对比度来判断像素或图像块的显著性。根据邻域范围的不同,这些算法可以分为局部对比度先验和全局对比度先验。前者指与邻近的部分差异越大则显著性越强,而后者指与全图其他所有部分的差异和越大则显著性越强。另外,为了克服像素级显著性检测带来的问题如计算速度慢、无法引入表征区域性质的图像特征等,并进一步提高显著性检测算法的性能,当前越来越多的显著区域检测算法开始采用图像块作为基本的处理单元。即先对原始图像进行初始的过分割,得到小块的近似同质的过分割区域(称为超像素或者图像块); 然后在这些过分割区域的基础上进行局部特征或者全局特征的对比度计算,以判断过分割区域的显著性。
当图像背景杂乱时,如果基于局部对比度先验进行显著区域检测,得到的显著图中背景噪声就会很强,而且显著物体内部也无法得到较好的凸显,仅能在一定程度上凸显显著物体与背景的边界。但如果采用全局对比度先验进行显著性检测,当图像背景中包含有与显著物体相同的颜色或纹理等表观特征时,算法仍然无法有效处理。另外,当图像构成与一般的构图经验不符如图像中的前景物体过大时,常用的全局对比度先验即全局稀有性先验就不成立。因此,现有的显著区域检测算法同样不尽如人意。
另外,在图像的初始过分割时,为了保证显著物体与图像背景之间的边界不被划分到过分割区域的内部,即避免过分割区域同时横跨显著物体和图像背景,一般的过分割区域面积均较小。实际上,在图像的初始过分割之后,一个更合理的选择是将过分割区域聚类成更大的区域,以抑制图像中杂乱背景引起的强噪声。
文[5]假设图像的背景区域比显著物体内的区域分布更分散。首先利用均值漂移算法在图像的Lab颜色空间提取超像素; 然后利用Gauss混合模型(GMM)将超像素聚为8类,即形成8个大的超像素簇; 再计算每个簇的紧凑性,空间分布越紧凑的簇则显著性越强; 最后利用排序算法[6]在不同的类别中进行显著性传播。由于GMM算法中并没有考虑超像素的空域位置关系; 而且不同场景的图像,其内容差异很大。因此,采用固定的簇个数必然会引进额外的检测误差,从而导致文[5]仍然不能有效处理具有杂乱背景的图像。文[7]也利用流形排序(manifold ranking)来计算图像的显著性,但直接利用图像四周边界上的超像素作为背景查询项; 而且为了提高算法性能,采用两级排序过程进行显著性传播。
本文提出基于过分割区域再聚类的显著区域检测算法框架。首先利用SLIC[8]算法将图像过分割为具有感知意义的超像素; 然后直接将超像素聚类成大的超像素簇; 再从所有超像素簇中选出可能的背景簇,此处的背景簇指内含的超像素多数属于图像背景的簇; 最后,将选出的背景簇中的超像素作为查询项,利用排序算法来估计其他超像素与查询项的关联度得分,该关联度得分即为最终的显著值。
1 超像素聚类谱聚类[9]的基本思想是将样本作为顶点,样本间的相似度作为边的权重,从而将聚类问题变换为图分割的问题: 寻找一种图分割的方法使得连接不同组的边的权重尽可能低即最小化类间相似度,而组内的边的权重尽可能高即最大化类内相似度。
与当前绝大多数显著区域检测算法一样,本文首先对原始图像进行初始过分割: 利用SLIC[8]算法将图像过分割为超像素集合P={p1,p2,…,pNs},其中的每一个超像素包含一组空域相近、表观相似的像素。对于一幅典型的300×400像素分辨率的图像,超像素个数设为Ns=600。
1.1 图的构建以超像素为节点V,构建一个2级邻域连接无向加权图G=(V,E)。 所谓2 级邻域连接是指超像素i与其所有的邻接超像素、以及其邻接超像素的邻接超像素之间都存在一个边E。另外,在多数情况下,图像的四周边界都是背景。因此,在G中将所有的边界超像素(如果一个超像素与图像的四周边界有重叠,则称其为边界超像素)都用边连在一起。
在确定了G中顶点之间的连接方式后,就可以确定邻接矩阵。任意2个超像素pi和pj之间的相似度定义为2个超像素在 Lab颜色空间下平均颜色的 Euclid距离d(pi,pj)。 定义图的邻接矩阵为
$W\left( i,j \right)=exp\left( ~-\frac{{{d}^{2}}({{p}_{i}},{{p}_{j}})}{2{{\sigma }^{2}}} \right).$ | (1) |
其中尺度参数σ一般采用手动设置。 σ值越大,越可能把差异大的超像素聚到一类中。因此,当图像中像素的颜色变化较大时,应该选取较大的σ值; 反之,则应选取较小的σ值。如果设置为固定的σ,必然会降低谱聚类算法的性能。因此,本文算法依据超像素颜色的差异来自适应计算σ值。经实验发现,当σ在 [8, 12] 范围内时,算法性能较好。因此,定义σ为
$\sigma =\left\{ \begin{matrix} 12,m\ge 12; \\ 8,m\le 8; \\ m,其他. \\\end{matrix} \right.\text{ }$ | (2) |
其中:
$m=\frac{1}{4N_{s}^{2}}\sum\limits_{~i,j=1}^{{{N}_{s}}}{d({{p}_{i}},{{p}_{j}})}.$ | (3) |
在所有的聚类算法中,准确选择聚类个数k都是最核心的问题。当数据中噪声较强或者不同类别之间有重合、而又没有一定的类数先验时,k的准确选择尤其重要。本文的目标是利用谱聚类算法来对任意一幅图像产生近似物体级别的超像素簇,因此选择合适的k非常关键。不准确的k会将整幅图像过分割或者欠分割,并对后续的背景簇选择带来较大难度,从而影响整个显著区域检测算法的性能。
本文采用颜色名称(color name,CN)描述子[10]来统计图像中主要颜色的个数。CN是用来描述大自然中所有存在颜色的语言标签。在计算机视觉领域,通过自动学习由图像搜索得到的大量图像,文[10] 将RGB颜色值映射为CN描述子。CN描述子为11维的颜色概率表示向量,其元素总和为1。本文首先将每个超像素的平均颜色映射为一个CN描述子,然后计算全图所有超像素的平均CN描述子:
${{m}_{CN}}=\frac{1}{{{N}_{s}}}~\sum\limits_{i=1}^{{{N}_{s}}}{C{{N}_{i}}}.$ | (3) |
对于图像I,mCN是一个11维的向量:
${{m}_{CN}}=[p(c{{n}_{1}}|I),\text{ }p(c{{n}_{2}}|I),\ldots ,\text{ }p(c{{n}_{11}}|I)].$ | (4) |
其中: cni表示第i个颜色名称,p(cni|I)表示cni在原始图像I中所占的比例。因此,当p(cni|I)值较大(即原始图像中包含较多的cni颜色的像素)时,cni即可认为是原始图像的一个主要颜色,该颜色可以较好地表达该原始图像。当p(cni|I)的值偏小时,则意味着原始图像中含有较少或者没有cni颜色的像素,cni即被认为是非主要颜色。因此,本文将mCN向量中所有元素的平均值作为阈值T。 当p(cni|I)≥T时,即认为cni是原始图像中的一个主要颜色。
在得到图像的主要颜色种类后,令Nc表示原始图像T中主要颜色的个数,本文定义谱聚类中的聚类个数为
$k=\left\{ \begin{matrix} 3,{{N}_{c}}\le 3; \\ {{N}_{c}},其他. \\\end{matrix} \right.$ | (5) |
在构建好图模型、设定好聚类个数后,就可以采用具体的Laplace矩阵来对全图的所有超像素进行聚类。不同的Laplace矩阵对应于不同的谱聚类算法[9]。经过大量试验对比发现,本文算法中采用非归一化的Laplace矩阵的效果要优于采用归一化的Laplace矩阵的。因此,本文采用非归一化的Laplace矩阵来实现谱聚类。
非归一化的Laplace矩阵定义如下:
$L=D-W$ | (6) |
其中D为对角阵,其(i,i)位置的元素等于邻接矩阵W的第i行的和。首先计算Laplace矩阵L的前k个特征向量u1,u2,…,uk; 然后将u1,u2,…,uk作为列向量构造矩阵U∈$\mathbb{R}$Ns×k; 再将U的行向量表示为yi(i=1,2,…,Ns); 最后,对行向量yi采用k-均值算法进行聚类,并记聚类结果为R={r1,r2,…,rk}。 则r1,r2,…,rk即为不相交的超像素子集,对应于原始图像中的k个超像素簇。
2 背景簇选择超像素聚类后,原始图像被聚类为k个近似物体级的超像素簇r1,r2,…,rk。 接下来就需要确定每一个簇究竟是背景还是前景。根据文[13-14],靠近图像四周边界的超像素多数是背景即背景先验。本文同样采用背景先验来选择背景簇。
背景簇的选取主要基于以下2个主要原则: 1) 一个簇越接近图像的四周边界则属于背景的概率越大; 2) 一个簇与已确定的背景簇差异越大则属于前景的概率越大。
详细的背景簇选择算法流程如图 1所示。算法的输入包括: 超像素聚类得到的k个簇r1,r2,…,rk、 每个簇内的超像素个数和边界超像素个数、每对簇之间的直方图χ2距离以及簇之间相似度的阈值Thd(本文所有实验中,Thd设为常数0.35)。 注意,边界超像素是指与图像四周边界有重叠的超像素; 如果一个簇中包含有边界超像素则称为边界簇,否则称为非边界簇; bg和fg分别表示背景簇和前景簇; bgP和fgP分别表示临时的候选背景簇集合和临时的候选前景簇集合; ratioB 表示每个簇中边界超像素个数与该簇中总超像素个数的比值。
本文主要依据上述2个背景簇选取原则来选取背景簇。首先从边界簇集合中选取包含最多边界超像素个数的簇作为初始的背景簇,然后依据其他簇的分布以及簇之间的颜色差异来选取候选背景簇和候选前景簇,最后从候选簇中选出可能的背景簇集合bg={rbg1,rbg2,…,rbgq}并输出。
3 显著性估计
在节2中,通过簇选择算法从图像的不同簇中选出了可能的背景簇集合bg。 在自然图像中,显著物体(前景)总和背景具有一定差异。因此,接下来就可以根据与bg中的超像素的相关程度来确定其他超像素的显著性。与bg中的超像素相关程度越高的超像素,属于背景的可能性越大,则显著性越低; 反之,则属于前景的可能性越大,显著性越高。可以利用超像素之间的表观信息来评价一个超像素与已知的bg之间的相关性,但是仅仅考虑表观而不考虑位置关系,结果必然不尽如人意。只有同时考虑超像素之间的表观和位置信息,才可能较准确地估计超像素之间的相关性。为此,本文采用了流形排序算法。
3.1 流形排序原理流形排序最早由Zhou等[14-15]在研究半监督学习时提出,希望依据少数已标注的和大量未标注的数据共同体现的内在结构来设计足够光滑的分类函数。此处所指的内在结构即内在的全局流形结构,因此称其为流形排序。
给定任意一组m维的数据点集合X={x1,x2,…,xq,xq+1,…,xn},其中xt∈$\mathbb{R}$m,t=1,2,…,n。 不失一般性,假设x1,x2,…,xq为初始的查询项。所谓查询项即根据先验知识或者其他算法已经确定或标注的具有同一属性的数据,而其他数据为未标注的数据。例如,假设x1,x2,…,xq同为图像中已经标注的前景像素点(查询项),而xq+1,xq+2,…,xn为同一图像中其他未标注的像素,可能是背景也可能是前景。本文所谓的排序问题就是要寻找一个排序(打分)函数f: X↦$\mathbb{R}$,以提供其他数据点与查询项之间的关联度度量: 2个数据点xi和xj的排序得分fi和fj越接近,则表示二者的关联度越高即越相似。
可以将排序函数f看做一个列向量f=[f1,f2,…,fn]T; 同时,定义指示向量y=[y1,y2,…,yn]T,如果xi为查询项则yi=1,否则yi=0。 流形排序就是要在给定数据点集合X、 数据点之间的距离度量d(xi,xj)以及指示向量y的基础上,对任意一个xi∈X计算其排序得分fi∈f。 流形排序可以通过迭代算法实现[12]。该迭代算法也可以用优化问题来解释,具体可参考文[13]。该优化问题的解析解为[13]
${{f}^{*}}={{(I-\alpha {{D}^{-1}}A)}^{-1}}y,$ | (7) |
其中: I为单位矩阵; D为对角阵,其(i,i)位置的元素等于相似度矩阵A的第i行的和。
3.2 基于流形排序的显著性估计与节1.1一样,本文利用P作为顶点构建G,且所有边界超像素互相连接。此处图的相似度矩阵定义为
$A\left( i,j \right)=exp\left( -\frac{{{d}^{2}}({{p}_{i}},{{p}_{j}})}{{{\sigma }^{2}}} \right).$ | (8) |
其中: 超像素之间的平均颜色距离d(pi,pj)和尺度参数σ的取值与式(1)相同; σ越小,表示排序时越重视局部信息。
由于节2已经选出了可能的背景簇集合 bg,因此,这里采用背景簇集合中的每个簇单独作为查询项进行流形排序,以估计其他超像素的显著性。然后将所有背景簇的排序结果进行融合。
以下以背景簇集合 bg中的簇r bg1为例进行介绍。首先将簇r bg1中所包含的超像素对应的指示向量yi置为1,剩余其他所有超像素对应的指示向量yi置为0; 然后由式(7)计算排序得分f*。 由于r bg1为背景簇,因此由式(7)计算得到的排序得分越大,表示超像素与r bg1的相关性越大即属于背景的可能性越大。基于此,以r bg1为查询项时任一超像素pi的显著值为
${{S}_{1}}(pi)=1-{{{\hat{f}}}^{*}}i.$ | (9) |
其中${\hat{f}}$i*表示fi*的归一化结果。
采用相同方法分别计算以 bg中其他各簇为查询项的显著性估计,再通过式(10)融合即可得到超像素pi最终的显著值S(pi)。
$S({{p}_{i}})={{S}_{1}}({{p}_{i}})\times {{S}_{2}}({{p}_{i}})\times \ldots \times {{S}_{q}}({{p}_{i}}).$ | (10) |
最后,对同一超像素内的所有像素赋以相同的显著值即得到最终的显著图。
4 实验结果为了验证本文算法的有效性,分别在ASD[14]和CSSD[15]数据集上进行了结果评测。对比的显著区域检测算法包括RC[16]、SF[17]、HS[15]、MR[7]和wCtr[11]等。其中,RC、HS和wCtr*的结果均来自于公开提供的原始可执行程序,SF在CSSD数据集上的结果以及算法MR[7]的结果均来自文[11]提供的可执行程序。SF在ASD数据集上的结果来自于文[17]作者网站。
ASD是显著区域检测中被广泛采用的一个数据集。该数据集共包含1 000幅图像,每一幅图像均包含一个清晰无歧义的物体。CSSD为复杂场景显著性检测数据集。与ASD数据集相比,CSSD数据集中包含更多结构复杂的自然场景图像,大大增加了显著区域检测的难度。
4.1 评价指标介绍由于显著图一般采用灰度图表示,而数据集提供的真值图为二值图。因此一般采用如下2种方式来进行量化比较。
4.1.1 固定阈值分割首先采用0~255等固定的整数阈值对显著图进行二值化以得到显著区域的分割; 然后根据数据集提供的真值计算每幅二值图下的精确度p和召回率r。 再利用精确度和召回率计算二者的加权调和函数即F-measure 指标:
$F=\frac{(1+{{\beta }^{2}})pr}{{{\beta }^{2}}p+r}.$ | (11) |
与文[14]一致,本文设定β2=0.3来强调精确度指标。 F值越大,则说明算法性能越好。
4.1.2 自适应阈值分割在显著区域检测的算法评测中,一般采用显著图中所有像素灰度平均值的2倍作为自适应阈值来分割显著图[15]。 然后同样计算分割结果的p、 r和F等指标。对整个数据集中所有图像的p、 r和F结果进行累加平均,即可得到算法在自适应阈值分割时的性能。
4.2 ASD数据集实验结果本文首先在ASD数据集上对所有算法的显著图分别进行固定阈值分割和自适应阈值分割指标评价。
当采用固定阈值分割时,结果如图 2所示。本文算法的F在[203, 255]的阈值区间明显优于其他算法的,在其他阈值区间与其他算法最好的结果相近。
当采用自适应阈值分割时,结果如表 1所示。本文算法的p和F均优于其他5种算法的。
算法 | p | r | F | |||
ASD | CSSD | ASD | CSSD | ASD | CSSD | |
本文 | 0.890 | 0.670 | 0.881 | 0.703 | 0.888 | 0.678 |
wCtr* | 0.871 | 0.667 | 0.930 | 0.776 | 0.884 | 0.689 |
MR | 0.879 | 0.650 | 0.902 | 0.767 | 0.884 | 0.674 |
HS | 0.878 | 0.694 | 0.840 | 0.669 | 0.869 | 0.688 |
SF | 0.876 | 0.664 | 0.718 | 0.534 | 0.834 | 0.629 |
RC | 0.828 | 0.666 | 0.580 | 0.446 | 0.754 | 0.598 |
4.3 CSSD数据集实验结果
当采用固定阈值分割时,结果如图 3所示。本文算法的F在 [63,96]和[174, 255]的阈值区间明显优于其他算法的,在其他阈值区间与其他算法最好的结果相近。而且本文算法的F曲线比其他算法的都更平坦。
当采用自适应阈值分割时,结果如表 1所示,本文算法与其他算法具有相近的性能。
综合来看,本文算法在2个差异较大的数据集上均能获得相对较为平坦的F曲线。这说明了本文算法在不同图像上能获得相对较好的一致性。另外,所有算法在CSSD 数据集上的结果都不如ASD 数据集上的,这说明了CSSD 数据集比ASD 数据集更富有挑战性。
4.4 算法耗时本文在ASD 数据集上用配置为英特尔酷睿 i7-2600 3.4 GHz 处理器、 4 GB 内存的计算机对比了所有算法的平均计算时间。其中MR的代码来自文[11],其他算法的代码来自公开的代码; 本文算法、wCtr*和MR均为Matlab代码,其他算法为C++代码。本文算法、wCtr*、 MR、 HS、 SF和RC的平均每幅图像计算时间分别为0.734、 0.847、 0.434、 0.719、 0.349和0.216 s。相比性能相近的wCtr*算法,本文算法的耗时减少13%。
5 结 论本文提出了一种融合聚类与排序的显著区域检测算法。直接在图像过分割得到的超像素上进行再聚类,以得到较大的超像素簇,从而降低了图像中噪声的干扰。同时,通过统计整幅图像的主要颜色来估计聚类算法的类数,使得聚类的结果更加鲁棒。另外,在将全图超像素聚类成较大的簇之后,通过簇选择算法从聚类结果中选出可能的背景簇,再通过其他超像素与背景簇中的超像素的相关性来计算全图的显著性。
在ASD和CSSD这2个公开的显著区域检测数据集上的实验结果表明: 本文算法在不同的数据集上能够实现稳定的显著区域检测结果; 而且在部分指标上明显优于其他5种算法。
[1] | Papageorgiou C, Poggio T. A trainable system for object detection[J]. International Journal of Computer Vision , 2000, 38 (1) : 15–33. DOI:10.1023/A:1008162616689 |
[2] | Mishra A K, Aloimonos Y, Cheong L F, et al. Active visual segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2012, 34 (4) : 639–653. DOI:10.1109/TPAMI.2011.171 |
[3] | ZHENG Liang, WANG Shengjin, LIU Z, et al. Fast image retrieval: Query pruning and early termination[J]. IEEE Transactions on Multimedia , 2015, 17 (5) : 648–659. DOI:10.1109/TMM.2015.2408563 |
[4] | LIU Jie, WANG Shengjin. Salient region detection via simple local and global contrast representation [J]. Neurocomputing[J]. Neurocomputing , 2015, 147 (1) : 435–443. |
[5] | REN Zhixiang, GAO Shenghua, Chia L T, et al. Region-based saliency detection and its application in object recognition[J]. IEEE Transactions on Circuits and Systems for Video Technology , 2014, 24 (5) : 769–779. DOI:10.1109/TCSVT.2013.2280096 |
[6] | Brin S, Page L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks & Isdn Systems , 1998, 30 (98) : 107–117. |
[7] | YANG Chuan, ZHANG Lihe, LU Huchuan, et al. Saliency detection via graph-based manifold ranking [C]//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Portland, OR, USA: IEEE, 2013: 3166-3173. |
[8] | 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 |
[9] | Von Luxburg U. A tutorial on spectral clustering[J]. Statistics and computing , 2007, 17 (4) : 395–416. DOI:10.1007/s11222-007-9033-z |
[10] | Van De Weijer J, Schmid C, Verbeek J, et al. Learning color names for real-world applications[J]. IEEE Transactions on Image Processing , 2009, 18 (7) : 1512–1523. DOI:10.1109/TIP.2009.2019809 |
[11] | ZHU Wangjiang, LIANG Shuang, WEI Yichen, et al. Saliency optimization from robust background detection [C]//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Columbus, OH, USA: IEEE, 2014: 2814-2821. |
[12] | ZHOU Dengyong, Weston J, Gretton A, et al. Ranking on data manifolds[J]. Advances in Neural Information Processing Systems , 2004, 16 (1) : 169–176. |
[13] | ZHOU Dengyong, Bousquet O, Lal T N, et al. Learning with local and global consistency[J]. Advances in Neural Information Processing Systems , 2004, 16 (16) : 321–328. |
[14] | Achanta R, Hemami S, Estrada F, et al. Frequency-tuned salient region detection [C]//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Miami, FL, USA: IEEE, 2009: 1597-1604. |
[15] | SHI Jianping, YAN Qiong, XU Li, et al. Hierarchical image saliency detection on extended CSSD[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2016, 38 (4) : 717–729. DOI:10.1109/TPAMI.2015.2465960 |
[16] | CHENG Mingming, Mitra N J, HUANG Xiaolei, et al. Global contrast based salient region detection[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2015, 37 (3) : 569–582. DOI:10.1109/TPAMI.2014.2345401 |
[17] | Perazzi F, Krähenbühl P, Pritch Y, et al. Saliency filters: Contrast based filtering for salient region detection [C]//Proc of IEEE Conference on Computer Vision and Pattern Recognition. Providence, RI, USA: IEEE, 2012: 733-740. |