基于超像素的点互信息边界检测算法

刘胜男　宁纪锋

摘要：点互信息（PMI）边界检测算法能准确检测图像中的边界，但算法效率受制于采样点的提取。针对采样过程中存在随机性和信息冗余的问题，提出一种利用超像素分割提供的中层结构信息来指导点对选取的方法。首先使用超像素算法对图像进行初始分割，将图像划分成大小形状近似的像素块；然后选取落在相邻超像素中的像素点对，从而使样本点的选取更有目的性，在采样点数目较少时，保证样本点仍能有效完整地获取图像信息。实验通过与原始的PMI边界检测算法在伯克利分割数据库（BSDS）上进行比对验证得出，基于超像素的PMI边界检测算法在采样点对为3500时，平均精准度（AP）达到0.7917，而原始算法则需要6000个同样环境下的采样点对。基于超像素的PMI边界检测算法在保证了检测精度的同时减少了所需的采样点数目，从而能有效提高算法的实时性。

关键词：边界检测； 超像素； 点互信息； 相似度衡量； 样点选取

中图分类号：TP391.41

文献标志码：A

0引言

图像的边界是图像的重要特征之一，准确的边界检测是图像分割、目标区域识别、区域形状提取等图像分析工作的基础[1-2]，是计算机视觉系统中必不可少的重要环节[3-5]。边界检测的实质是采用某种算法提取图像中目标与背景间的边界线[6-8]。边界检测算法根据是否需要训练先验知识可分为有监督的和无监督的检测方法。其中，在无监督的边界检测算法中根据所基于的理论不同可大致分为四类：基于聚类的方法，如均值偏移（Mean Shift， MS）算法、快速偏移（Quick Shift， QS）算法等；基于图论的方法，如归一化切割算法、Felz-Hutt（Felzenswalb-Huttenlocher）算法等；基于区域合并的方法，如分层分割算法[9-10]和受压纹理（Compression-based Texture Merging， CTM）算法等；基于种子增长的方法，如全变分算法（Total Variation， TV）等。这些算法不需要提供图像的先验知识，是当前研究范围最广的主流边界检测算法。无监督的边界检测现已形成一个体系，且有公开的库和统一的评价方法。与此同时，有监督的边界检测算法利用其所构造的边界训练集，结合机器学习方法进行边界检测也受到了一定的关注，如稀疏编码梯度算法（Sparse Coding Gradient， SCG）、结构化森林边缘算法（Structured Forest Edge，SE）[11]和素描令牌算法（Sketch Tokens， ST）[12]等，都取得了良好的检测结果。

在无监督边界检测算法研究中，基于点互信息（Pointwise Mutual Information， PMI）的边界检测算法[13]利用图像中的像素点对信息构建相似度矩阵获得边界，其性能超过了有监督的边界检测算法，成为当前该领域的研究热点。PMI是信息论和数理统计中的概念，常被用来衡量两个独立事件间的相关性。在边界检测算法中，将其概念引申为图像中两个特征之间联系的紧密程度，若两个特征联系十分紧密，则可认为在该图像中从属这两个特征的像素相似度很高，应包含在同一个目标中。然而在检测图像边界时，PMI值的计算需要随机地选取足够多的点才能保证图像的特征信息不被遗漏，算法的实时性受到了制约。与此同时，完全随机的选点方式也造成了一部分采样点的冗余。

因此如何减少该边界检测算法中采样点选取的随机性，对提高其性能有重要的影响。本文将超像素图像分割与PMI相结合，利用超像素分割获得的图像中层结构信息来指导PMI算法中像素点的选取。

超像素算法可利用像素之间特征的相似程度将像素分组，如图1所示。超像素可提取图像中感知有意义的区域，或用来取代刚性结构的像素网格，从而可以通过提升图像处理底层算法加快高层认知算法。文中超像素分割获得的分割结果将用以约束PMI算法的采样过程，使得原本无序随机的采样变得有序且能摒弃冗余信息，尤其在采样点数目较少的情况下，仍能有效地获取图像的特征，使算法的精度得以提升[14-16]。

1基于PMI的边界检测算法

1.1PMI

PMI[13]是信息论和数理统计中被用作衡量关联性的一个可计算量。假设x和y是两个相互独立的离散型随机变量，而x、y的联合分布概率（joint distribution）和各自的独立分布概率（individual distribution）可得到，则PMI通过量化联合分布和独立分布之间的差异来衡量x事件和y事件的关联性，其数学表示为式（1）：

1.2PMI在图像处理中的应用

将PMI概念应用到图像处理过程中，则可理解为对于任意一幅图像，随机地取出N个点对，则每一个点对中的点，如图2所示，都可以看成是一个随机变量。每一个点对都可映射到特征域成为一个特征对，即点对中的一个点可以抽取特征成为特征A，另一个点可抽取特征为特征B。

其中ρ参数可以为整数，也可以为非整数，此时PMI能更贴合实际地提取特征，因此在PMI边界检测算法中经训练数据得到当ρ参数取值为1.25时，PMI模型的表现最好。

对每一幅待测图像都可以得到如图3（b）所示的PMI模型图，其中灰度较浅的区域PMI值较高。对于图3（a）中所示的待测图像，其中1号圈代表斑马身上的条纹特征对的PMI值高于2号圈代表草地特征与斑马身上的条纹特征的PMI值，则表示斑马的身体条纹特征应该融合成为一个整体。

对于每一幅图像提取N个点对就可以得到N个特征对和N个PMI值，利用特征对和PMI信息生成随机森林决策树，以获得图像中任何特征对的PMI值，即可对整张图像构建相似度矩阵。为图像中的每个像素定义一个特征向量f，则像素点i和点j间的相似度可通过代入式（3）得到式（4）表示为：

其中：k表示当前特征，M表示共有M个特征域。生成相似度矩阵后可以通过区域融合的方法完成后续边界检测或图像分割的工作[10]。

2基于超像素的PMI边界检测算法

PMI边界检测算法概念简单，直观地描述了像素点组成图像时的规律，即若两个特征频繁同时出现，则属于这两个特征的像素点相似度越高，属于同一个目标的概率越高。

PMI提取了像素点的统计学特征，这种全局特征突破了一些经典算法的局限性。当一个目标物体由多个特征值不同的像素块（如不同颜色或不同纹理等）组合而成时，若只凭特征值的突变来判断边界则会出现误判，而PMI算法可以通过判断特征间的PMI值将看似特征完全不同但实属于同一个目标的像素点融合，从而获得数字图像中目标物体的真实边界信息。

2.1原始PMI边界检测算法存在的缺点

PMI描述了像素点级别的图像特征，其概念简单、实现容易、结果精准，然而利用PMI处理图像时，为了使图像的信息尽可能地被收集、采纳，采样点的数目必须要足够多，以保证选取到的样本点能够完整地表示图像的特征。然而，样本点越多就意味着计算时间越长、运行效率越低，因此算法的性能受到制约。

另一方面，在获取图像特征时，提取的像素点随机无序地散落在图像各处，当某一个特征区域越大时，像素点落在其上的概率就越高，如图3（b）所示，坐标系对角线上的高亮部分就是落在相同特征上的点对，即特征A近似于特征B。然而除开对角线外的高频区域才是算法所关注的特征对，即特征值不同却频繁同时出现，这些点对就指向那些从属同一个目标物体，却拥有不同特征值的像素点。

2.2基于超像素的样本点选取方法

为了使PMI边界检测算法的采样过程更高效、更有目的性，避免采样点过多地落在具有相同特征的区域，更大概率地落在算法关注的区域，避免样点资源被随机分配，使采样点的选取更具有代表性，本文引入超像素的概念，利用超像素分割提供的图像中层结构信息，约束采样点的提取，即随机抽取的采样点对中的两个点必须分别落在相邻的超像素中，即对式（3）中的A、B特征作了限制，使提取的A、B特征必须位于相邻的超像素中，如式（6）：

其中SLabel是指超像素分割后位于不同超像素的像素点拥有不同的标签。如图4（b）中可看到，原本位于同一个超像素内的像素点对近似属于相同特征，利用提出的基于超像素的PMI检测算法规定位置信息后，采样点对中的两个像素点必须分别位于相邻不同超像素内，如图4（c）中所示，可知这些点有时候仍具有相同特征，有时会取到不同特征。

这样一来，就把本应落在同一超像素中的点对均匀地分布在了像素块之间，克服了采样点过程中的随机性，降低了具有相同特征的采样点对的超高频率（即PMI模型对角线上高占比部分），增加了非相同特征点对的总占比，也就是将采样点资源重新分配，适当减少了分配给相同特征的采样点，同时把这部分样点资源平均分配给了其他不相同特征间的候选区域。这种采样方式当降低总采样点数目时，由于样点资源少，所以样点的分布对边界检测的结果影响更大。

2.3基于超像素的PMI边界检测算法流程

上述边界检测算法在具体实现时，需要利用超像素分割作为图像的预处理步骤，分割结果是给图像中的每一个像素点分配一个标签（Label）用来标识当前像素应属于哪一个超像素。算法中利用随机森林决策树提供数值预测，随机森林具有训练速度快、能够处理高维数据、并行化容易、实现简单等优点为PMI边界检测算法提供了高效准确的分类决策。

基于超像素的PMI边界检测算法实现流程如下：

输入图像I；

输出图像I的边界概率图。

步骤1初始化SLIC超像素分割[14]环境，利用该算法对图像I进行预处理，为图像中每一个像素点赋一个超像素标签（Label）。

步骤2在不同特征域中对图像进行特征提取，即在LAB颜色空间和其对角协方差矩阵域中提取每个像素点的相应特征值，该值是一个三维向量。

步骤3计算图像中所有相距在一定像素距离内，且Label值不同的像素点对，并从中随机选取N对。

步骤4N个像素对共有2N个像素点，根据这些像素点及其特征向量利用核密度估计分别计算出每一种特征的概率P（x），根据式（2）计算任意两个特征间的联合分布概率P（A，B）。

步骤5根据式（3）和步骤4的结果，计算任意两个特征间的PMI（A，B）值。

步骤6根据步骤4中获得的所有特征以及步骤5中获得的任意两个特征间的PMI值构建随机森林决策树，用以决策在当前图像I中，任意两个特征间的PMI值。

步骤7将图像中任意两个像素点的特征向量输入决策树，输出当前两个像素点间的PMI值用以衡量两个像素的相似度，该值越大说明当前两像素越相似，并以此构建相似度矩阵。

步骤8将相似度矩阵输入分层分割算法[10]框架（OWT-UCM）获得边界概率图。分层分割算法框架是指将相似度矩阵利用有向分水岭变换（Oriented Watershed Transform，OWT）算法先分成若干区域，再利用超度量轮廓图（Ultrametric Contour Map，UCM）算法进行区域合并，得到最终结果。

在PMI边界检测算法中需要利用采样点的特征和相应的PMI值训练随机森林决策树，因此采样点的数目和覆盖范围会影响其提取的特征数，需要足够多的采样点才能保证图像中的特征都被提取出来。原始的PMI边界检测算法采样点完全随机分配，当某一特征占比很大时，落入其中的采样点概率会出现饱和，而小概率特征则可能出现被忽略的情况。

3实验结果与分析

3.1实验数据集及边界检测评价标准

实验数据集为伯克利分割数据库（Berkeley Segmentation Data Set，BSDS）[17]，该数据库是无监督的图像处理领域中唯一的一个可针对边界检测结果进行统计且有真值（ground truth）的图像库，因此常被当作该领域的基准。该数据库发展至今为BSDS500，有训练数据集200张图片，验证数据集100张图片，测试数据集200张图片，对于每一张图片都附有人工绘制的相应真值。

该数据集通过遍历尽量多的阈值计算出三个统计结果：全局最佳（Optimal Dataset Scale，ODS）、单图最佳（Optimal Image Scale，OIS）和平均精准度（Average Precision，AP）。其中：ODS指数据库所有图像使用固定同一阈值时的最佳结果；OIS是对每一幅图像使用针对当前图像最佳阈值时的结果；AP表示查准率/查全率（Precision/Recall， PR）曲线（坐标轴纵为Precision，横轴为Recall）下的面积。Precision指待测算法检测出来的边界是真边界的占比，Recall指真正的边界被检测出来的部分占比。查准率和查全率必须同时考虑才能判定算法的优劣，所以AP值是考虑两个参数后给出的综合评定标准，通常以该值为主要判定依据。该值越大说明算法的平均表现越好，真值的验证结果为0.8，即AP值越接近0.8说明当前算法的运算结果越接近人工识别的结果。PMI边缘检测算法在该数据集上与近年来其他算法的比较如表1所示，其中分层分割算法（gPb-owt-ucm）[9-10]和结构化森林边界检测算法（Structured Forests Edge，SE）[11]分别是目前无监督边界检测和有监督边界检测算法的最高水平。从表1可以看出，PMI边界检测算法作为无监督的边界检测高于分层分割算法6个百分点，比当前最好的有监督边界检测算法结构化森林边界检测算法在AP值上仍高出1个百分点，达到0.79，非常逼近真值。

3.2超像素区域尺寸的选择

基于超像素的PMI算法需要像素点落在不同的超像素上，所以超像素区域尺寸（region size）参数非常重要。若区域尺寸过大，会导致本应落在相同特征区域的像素点被裁减得过多，相应的PMI过低，最终相同特征的像素点不能融合；若区域尺寸过小，会导致裁减掉的冗余点太少，对其他非相同特征区域的影响不大，最终效果不佳。

利用BSDS500[17]中的训练数据集来训练超像素区域尺寸的取值，在采样点数固定为4000时， 超像素区域尺寸不同对检测结果的影响如表2所示。表2显示，当超像素区域尺寸为4，即像素块大小近似等于4像素×4像素时，算法取得了最优的性能，因此本文采用该参数值进行边界检测。

3.3改进的方法与原始方法检测结果比较

3.3.1定性评价

表3为原始PMI边界检测算法和本文算法在设置不同采样点数目时各自的实验结果对比。从表3中可以看出，无论输入样点参数为多少，本文算法的平均精准度都高于原算法，且在采样点越少的情况下，效果越好、提升越明显。在样点数目仅为3500时，本文算法的AP值就已达到0.79，而原算法则需要采样点数目为6000才能到达此结果，且改进的算法在6000点后采样点资源已趋近饱和，测试结果变动不大，而原算法在6000点之后检测结果仍跟随采样点数目的变动而浮动，鲁棒性不强。

实验使用的所有的测试图都来自DSBS500中的检测集，基于超像素的PMI边界检测算法与原始PMI边界检测算法的结果如图5所示，采样点数统一取1000。

当采样点为1000时，原算法和改进算法的AP值均高于0.75，对图像边缘都能进行较完整地描述，且在1000采样点时改进算法比原始算法平均精准度已高出约1.11个百分点。

从图5可以看出，本文提出的基于超像素的PMI边界检测算法在采样点数仅为1000时，仍能捕获图像中物体的细节信息，鲁棒性更强。

4结语

针对PMI边界检测算法中采样点随机性高、存在无意义样本的缺陷，本文提出一种结合超像素指导采样过程的方法，在减少过多冗余点的同时，增加有效采样点的占比，从而提升了该方法的平均精准度。实验结果表明，在同样的采样条件下，本文提出的基于超像素的PMI边界检测算法的检测结果始终优于原始PMI边界检测算法，尤其当采样点越少时，改进算法的提升越明显。

本文通过对算法采样过程的改进来提升边界检测的准确率和效率，而PMI抽象为图像特征可直接提取成为图像分割的依据，不需要预先获得边界信息。所以进一步的研究将融合PMI特征与其他全局几何特征完成更高层次的图像分割工作。

参考文献：

[1]REN X， BO L. Discriminatively trained sparse code gradients for contour detection [C]// NIPS 2012： Proceedings of the 2012 Advances in Neural Information Processing Systems 25. Cambridge， MA： MIT Press， 2012： 593-601.

[2]张广燕，王俊平，邢润森，等.PSLIP新模型及在边缘检测和图像增强中的应用[J].电子学报，2015，43（2）：377-382. （ZHANG G Y， WANG J P， XING R S， et al. A new PSLIP model and its application in edge detection and image enhancement [J]. Acta Electronica Sinica， 2015， 43（2）： 377-382.）

[3]KOHLI P， LADICK L， TORR P H. Robust higher order potentials for enforcing label consistency [J]. International Journal of Computer Vision， 2009， 82（3）： 302-324.

[4]石美红，李青，赵雪青，等.一种基于保角相位的图像边缘检测新方法[J].电子与信息学报，2015，37（11）：2594-2600. （SHI M H， LI Q， ZHAO X Q， et al. A new approach for image edge detection based on conformal phase [J]. Journal of Electronics & Information Technology， 2015， 37（11）： 2594-2600.）

[5]PANTOFARU C， SCHMID C， HEBERT M. Object recognition by integrating multiple image segmentations [C]// ECCV 2008： Proceedings of the 10th European Conference on Computer Vision， LNCS 5304. Berlin： Springer-Verlag， 2008： 481-494.

[6]ROBERT L G. Machine perception of three-dimensional solids [J]. Optical and Electro-Optical Information Processing， 1965， 21（7）： 159-197.

[7]TORRE V， POGGIO T A. On edge detection [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1986， 8（2）： 147-163.

[8]何春，叶永强，姜斌，等.一种基于分数阶次微积分模版的新型边缘检测方法[J].自动化学报，2012，38（5）：776-787. （HE C， YE Y Q， JIANG B， et al. A novel edge detection method based on fractional-order calculus mask [J]. Acta Automatica Sinica， 2012，38（5）：776-787.）

[9]ARBELEZ P， HARIHARAN B， GU C， et al. Semantic segmentation using regions and parts [C]// CVPR 2012： Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2012： 3378-3385.

[10]ARBELEZ P， MAIRE M， FOWLKES C， et al. Contour detection and hierarchical image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（5）： 898-916.

[11]DOLLR P， ZITNICK C L. Structured forests for fast edge detection [C]// ICCV 13： Proceedings of the 2013 IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2013： 1841-1848.

[12]LIM J J， ZITNICK C L， DOLLR P. Sketch tokens： a learned mid-level representation for contour and object detection [C]// CVPR 2013： Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition. Washington， DC： IEEE Computer Society， 2013： 3158-3165.

[13]ISOLA P， ZORAN D， KRISHNAN D， et al. Crisp boundary detection using pointwise mutual information [C]// ECCV 2014： Proceedings of the 13th European Conference on Computer Vision， LNCS 8691. Berlin： Springer-Verlag， 2014： 799-814.

[14]LUCCHI A， SMITH K， RADHAKRISHNA A， et al. Supervoxel-based segmentation of mitochondria in EM image stacks with learned shape features [J]. IEEE Transactions on Medical Imaging， 2012， 31（2）： 474-486.

[15]ZHOU X， LI X， CHIN T-J， et al. Superpixel-driven level set tracking [C]//ICIP 2012： Proceedings of the 2012 IEEE International Conference on Image Processing. Piscataway， NJ： IEEE， 2012： 409-412.

[16]LIU L， XING J， AI H， et al. Semantic superpixel based vehicle tracking [C]// ICPR 2012： Proceedings of the 2012 21st International Conference Pattern Recognition. Piscataway， NJ： IEEE， 2012： 2222-2225.

[17]MARTIN D R， FOWLKES C， TAL D， et al. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics [C]// ICCV 2001： Proceedings of the 2001 8th IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2001， 2： 416-423.