交互式分割算法的可变形目标检测

蒲宝明, 霍　红, 杨东升, 李相泽

(1. 中国科学院 沈阳计算技术研究所, 辽宁 沈阳　110870;2. 东北大学 计算机科学与工程学院, 辽宁 沈阳　110819)



交互式分割算法的可变形目标检测

蒲宝明1, 霍红1, 杨东升1, 李相泽2

(1. 中国科学院 沈阳计算技术研究所, 辽宁 沈阳110870;2. 东北大学 计算机科学与工程学院, 辽宁 沈阳110819)

针对现有高检测精度算法效率较低的问题,提出一种利用基于水平集的交互式目标分割算法对图像进行预分割的方法,提高了对可变形目标检测的效率.算法首先使用交互式目标分割算法对图像进行初步分割,然后根据分割区域进行部件检测.对于部件模型,使用传统的梯度向量直方图来进行描述.预先对图像进行分割,可以减少检测窗口的检测范围,对于像素较高的图片尤其重要.实验结果发现,与穷举搜索的滑动窗口相比,交互式分割算法在速度方面有明显的提高.

目标检测; 图像分割; 交互式分割; 梯度向量直方图; 可变形部件模型

随着计算机技术的飞速发展,计算机视觉得到了广泛的应用.目前,在智能监控系统、军事目标检测及医学导航手术等方面,目标检测技术具有很高的应用价值[1-2].

目标检测领域中最具有代表性的算法大概分成三类:第一类是基于整体特征的算法.第二类称为基于多部位的方法[3].第三类是基于多视角的方法[4-5].这三类方法有一个共同需求就是需要一个检测窗口来处理图像中的该区域特征并进行评价.那么,由于图像中有大量的像素点,而且检测窗口不宜过大,这就使得检测窗口在图像中的遍历顺序变得很重要.目前,使用最多的是滑动窗口(Sliding window methods)[6-8].这种方法能够将目标检测结合分类器来判断矩形窗口下的图像区域是否为检测对象.

滑动窗口的一个主要检测方式就是将检测窗口置于不同尺度的图像中的每个像素点上,然后判断窗口覆盖区域是否为目标.这种穷举搜索方式的优点是保证准确率. 但是它的缺点也十分明显,主要就是计算量过大,检测效率比较低.

针对以上问题,本文基于传统的可变形部件检测模型,在描述图像特征之前预先将图像分割成若干区域,以减少滑动窗口的遍历时间.本文使用的分割方法是传统水平集方法的改进,提高了原方法的收敛速度.本文主要从两方面来介绍:①对图像进行预处理时使用的分割算法----交互式目标分割算法.②检测图像时用来描述图像特征的可变形部件模型.

1　基于水平集方法的交互式目标分割算法

交互式目标分割算法需要用户输入最初的轮廓作为初始信息.因此,模型应该既包含初期输入轮廓特征,又包含图像中目标的特征.

不管动态轮廓的形态怎么样,模型应该使现在的动态轮廓向目标轮廓尽快逼近[9].这样,该模型要包含目标轮廓的信息.可以利用基于像素值的梯度向量使附近目标尽快移动其动态轮廓.为了克服动态轮廓在靠近目标轮廓时收敛性很低的问题,本文利用GVF(Gradient Vector Flow)模型,图像上每个点的GVF方向都指向目标轮廓.如果像素点逼近目标轮廓的位置,那么GVF的幅值就会变大,而在像素值变化不大的区域中幅值相对较小.在图像中,给定目标的状态具有多样性.例如,假设目标的轮廓是模糊的,那么,在不考虑图像区域信息的情况下(也就是说,只有上述目标轮廓的信息),得到的结果会产生收缩现象,甚至被收缩到一个点[10].所以,图像区域信息是非常有价值的,这样得到正确的目标轮廓会变得比较容易.需要导入Heaviside函数.Heaviside函数定义可用式(1)表示.

(1)

包含图像区域信息的速度函数式为

(2)

高斯概率密度函数p(I(x,y))的具体展开式,可用式(3)表示:

(3)

结合轮廓信息项和区域信息项,总体的速度函数如式(4)所示.

(4)

式中,α和β随着图像的状态不同而取不同的值,图像内噪声越多越大.α和β之间的关系是α+β=1.

交互式目标分割过程,就是使用由用户输入的初期轮廓到目标的实际边缘进化轮廓的迭代过程.轮廓进化的正确性跟它的速度函数有关.该方法提出的速度函数有式(4)的形式.在具体实现过程中,使用近似函数Hε代替Heaviside函数H(φ),近似函数Hε的具体形式如下:

(5)

式中,跟CV模型一样ε=1.另外,Hε的微分δε(φ)的具体的形式如下:

(6)

2　可变形部件模型

可变形部件模型是对滑动窗口方法比较经典的应用.在可变形部件模型中,可以通过部件模型对分割出来的各个子区域进行单独判断并对该子区域评估分类.模型中的特征是用HOG来描述的.

2.1HOG算法

经典的梯度方向直方图(Histogram of Oriented Gradients,简称HOG)[11]通过描述目标特征,最终形成特征集.

文献[3]给出了图片的HOG特征表示方法.首先图片被分割成比较小的块,边长在4～8像素效果比较好.我们称这样的块为cell,并且各个cell之间是不重叠的.针对每个cell来统计该区域内的像素梯度,并把每个像素的梯度值离散化到9个方向中,加到每个方向中的权重是根据梯度大小决定的.这样,直方图可以捕获目标的形状属性,但是忽略了细小的形变.为了减少光照等背景因素的影响,HOG算法把多个cell,比如2×2,组成一个block.block之间通过相互重叠来弱化光照对梯度的影响.

通过构建HOG特征金字塔来解决图像尺度不同的问题.金字塔的顶层用来捕获目标的粗糙特征集,比如根滤波器检测目标整体.金字塔的下面几层用来捕获比较精细的特征集,比如部件滤波器对部件的评分.

2.2可变形部件模型

可变形部件模型包含一个全局根滤波器和几个部件滤波器.检测窗口的评分(score)是通过根滤波器的评分与部件滤波器在候选点区域的综合评分得到的.根滤波器和部件滤波器评分方式都是通过计算预先训练的一组权值与窗口区域中的HOG之间的点积(dot product)而得到的.每一个样本x用式(7)来计算评分:

(7)

式中:β是一个模型参数变量;z是待检测区域;H表示特征金字塔;p=(x,y,l)表示金字塔的第l层的cell;φ(H,p,w,h)表示金字塔中的w×h子窗口,这个子窗口左上角的坐标为p[12].为了方便表述,不影响理解的情况下,后文用φ(H,p)来代替φ(H,p,w,h).

假设目标模型含有n个部件,那么需要定义一个根滤波器F0和一组包含n个部件的模型(P1,…,Pn),其中Pi=(Fi,vi,si,ai,bi),Fi是第i个部件的滤波器;vi是二维向量,用来表示第i个部件候选区域的起始坐标;si给出了这个候选区域的大小;ai和bi是用来确定二次方程系数的二维向量,这个方程用于计算第i个部件在这个候选区域的评分.候选区域用z=(p0,…,pi)表示,其中pi=(xi,yi,li),当i=0时表示根滤波器的位置,当i>0时表示第i个部件的位置[13].检测的评分由根滤波器的评分加上与根相关的每个部件放置点的评分,如式(8)所示:

(8)

通过上面的介绍看出,可变形部件模型可以对目标进行分散的多部位描述.这样就方便针对分割后的比较零散的区域进行部件检测.但是,这样的检测比较依赖于分割的结果,如果分割结果不理想,检测结果也会比较差.

3　基于交互式分割的目标检测算法

这里主要介绍算法的整体流程.本文的算法主要分成两个部分:训练部分和检测部分.目前,数据集变得越来越复杂,使用简单的训练方法往往就可以达到比较好的效果,而且训练速度也比较快.综合考虑,本文使用线性支持向量机(SVM)来进行二元分类.检测部分使用的就是预分割算法和可变形部件模型.

3.1样本训练

传统的HOG算法使用线性支持向量机作为分类判别器[14].它的学习过程主要分为两个阶段:第一阶段是通过正样本训练(包含待检测目标的图片)和负样本训练(不包含待检测目标的图片)进行学习,得到初步的分类判别器.第二阶段使用已经得到的初步分类器对负的训练图像进行扫描,把扫描结果有误的图片作为误测样本,然后用正样本、负样本和误测样本组成集合,再次学习得到最终的分类判别器.我们可以使用得到的分类判别器对待检测图像进行分类.

3.2检测过程

得到分类器之后,就进入到了检测阶段.本文检测的方法是在可变形目标检测模型的基础上,对图像预先进行交互式目标分割.

图1提供了一组图片的分割.通过这组图片可以发现,每幅图片在分割后都会得到很多区域,由于后面的检测主要针对这些区域,所以本文称其为候选区域.对于一个图像,可能有很多的候选区域,有些是与目标相关的,而有些是无关的.而且,这些区域可能分布在图像的各个位置,本文优先检测分割面积较大的区域.

图1　利用交互式分割算法对图像进行的分割结果Fig.1　The result of interactive segmentation

通过对图1的观察统计可以发现,分割出的候选区域中,属于真实目标的区域相对比较紧凑.而且,这些区域在被检测出来之后可以被范围较大的根滤波器覆盖.例如,对于图1a,由于背景比较单一,所以分割效果比较好.而对于图1b而言,由于背景很复杂,分割效果不好.

对于一张分割好的图片,首先用训练好的部件模型对每一个候选区域进行匹配,并且选出每个模板评分较高的一个区域.这样,如果感兴趣的目标在图片中,就将会得到一个评分较高而且位置相对紧凑的较大区域.这时,可以使用根滤波器进行目标的整体检测,并通过式(8)计算检测的总体评分.如果该评分达到了确定的阈值,就可以认为检测到了目标.

通过以上的描述可以发现,本文的方法在检测上比较依赖于分割的结果.在分割的效果比较好的情况下,算法准确度与穷举法相比不会有影响,而检测速度可以得到提高.

4　实验结果与分析

为了验证基于分割的目标检测算法的性能,我们对算法进行了测试,并提供各个环节的结果.

测试环境选择为PASCAL VOC 2007数据集.该数据集包括9 963张图片,共分成20个目标类.程序的运行环境是Windows 10操作系统下的Matlab R2013a.

图2给出了3组图片的实验结果.每组包含图片处理的3个阶段的结果,分别标记为(a)、(b)、(c).

图2　目标检测结果Fig.2　The result of object detection (a)—原始图像; (b)—预处理后的结果; (c)—最终的检测结果.

通过实验可以看出,前2组的图片背景颜色相对简单和平滑,这对分割算法来说是比较有利的.而第3组图片由于其背景比较复杂,分割结果较不理想,这样可能导致检测失败.

表1给出了本文算法与文献[8]中算法的平均准确度(Average precision,AP)对比.AP的计算方法是首先把识别率所有值分成10等份,这样就可以得到11个边界点.然后选取11个精确度,使得它们对应的识别率分别等于这些边界点.最后,这11个精确度的平均值就是AP.对于AP的

表1　平均准确率对比

具体计算方法,可以参见官方VOCdevkit Matlab文件VOCevaldet.m.

通过表中的结果可以看出,本文算法对于背景比较简单的分类,如飞机、轿车和船的效果比较好,而对于背景比较复杂的分类,如狗、花等的检测效果比较差.这充分说明了本文算法对于分割结果的依赖是比较大的.如果背景比较利于分割,本文的检测结果会高于文献[8]中的算法.

为了分析算法的效率,表2给出了算法几个主要步骤的运行时间.

表2　各个步骤的运行时间

通过表2可以看出,算法的预处理部分在总时间中占有较大的比例.这说明了分割的速度是算法的主要瓶颈.表3给出了本文算法与文献[8]算法进行的时间对比.

表3　运行时间对比

从表3中可以看出,图像在分割之前的检测速度与文献[8]中的算法在速度上没有明显提升.但是在已经分割好的情况下,本文算法在速度上有明显优势.造成这种现象的主要原因就是,分割算法消耗时间比较多,使本文算法丧失了速度优势.

虽然分割比较耗时,但是由于本文图像分割与检测是分开的,这样如果完成了分割,结果就可以反复使用.如果需要调整检测方法,就无需再次分割.比如,如果需要迭代训练或多次调整测试时,本文方法由于只需要一次分割,速度优势就会逐渐体现出来.

5　结　　语

本文通过对图像进行分割,获得了一些目标概率比较大的区域.由于算法只针对这些大概率区域进行检测,使检测速度得到了比较大的提升.对于算法的特征描述部分,本文仍然使用HOG特征描述器结合可变形部件模型进行表述.通过样本实验可以发现,文献[8]算法的平均使用时间为4.79 s,而本文的平均算法在分割前为4.85 s,分割后为2.25 s.这可以证明,对于分割后的图像,本文算法有明显的速度提升.所以,本文算法为一些可复用的图像检测提供了一种比较快速的方法.并且如果分割速度能够得到提高,本文算法可以期待更加明显的特点.

[ 1 ] 孙锐,侯能干,陈军. 基于特征融合和交叉核SVM的快速行人检测方法[J]. 光电工程, 2014,41(2):53-62.

(SUN R,HOU N G,CHEN J. Fast pedestrian detection method based on features fusion and intersection kernel SVM[J]. Opto-Electronic Engineering, 2014,41(2):53-62.)

[ 2 ] DALAL N,TRIGGSB. Histograms of oriented gradients for human detection[C]∥IEEE Conference on Computer Vision and Pattern Recognition, 2005.

[ 3 ] FELZENSZWALB P,MCALLESTER D,RAMANAND. Object detection with discriminatively trained part-based models[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010,32(9):1627-1645.

[ 4 ] LEIBE B,SEEMANN E,SCHIELE B. Pedestrian detection in crowded scenes[C]∥IEEE Computer Society Conference on Computer Vision and Pattern Recognition, June 20-25, 2005:878-885,

[ 5 ] 魏岩,涂铮铮,郑爱华,等. 结合RGB颜色特征和纹理特征的消影算法[J]. 计算机技术与发展, 2013,23(10):72-74,79.

(WEI Y,TU Z Z,ZHENG A H. Shadow elimination algorithm of combination of RGB color feature and texture feature[J]. Computer Technology and Development, 2013,23(10):72-74,79.)

[ 6 ] WUB,NEVATIA R. Cluster boosted tree classifier for multi-view,multi-pose object detection[C]∥IEEE International Conference on Computer Vision, 2007.

[ 7 ] LAMPERT C H,BLASCHKO M B,HOFMANN T. Beyond sliding windows:object localization by efficient subwindow search[C]∥Proceedings of the 23rd IEEE Conference on Computer Vision and Pattern Recognition. Anchorage, USA, 2010:1-8.

[ 8 ] FELZENSZWALB P,MCALLESTER D,RAMANAN D. A discriminatively trained,multiscale,deformable part model[C]∥IEEE Conference on Computer Vision and Pattern Recognition, 2008.

[ 9 ] CHAN T F,VESEL A. Active contours without edges[J]. IEEE Transactions on Image Processing, 2001,10(2):266-277.

[10] OSHER S,PARAGIOS N. Geometric level set methods in imaging, vision,and graphics[M]. New York:Springer, 2003.

[11] 刘威,段成伟,遇冰,等. 基于后验HOG特征的多姿态行人检测[J]. 电子学报, 2015,43(2):217-224.

(LIU W,DUAN C W,YU B,et al. Multi-pose pedestrian detection based on posterior HOG feature[J]. Acta Electronica Sinica, 2015,43(2):217-224.)

[12] MEHNERT A,JACKWAY P. An improved seeded region growing algorithm[J]. Pattern Recognition Letters, 1997(18):1065-1071.

[13] 姚雪琴,李晓华,周激流. 基于边缘对称性和HOG的行人检测算法方法[J]. 计算机工程, 2012,8(5):179-182.

(YAO X Q,LI X H,ZHOU J L. Pedestrian detection method baesd on edge symmetry and HOG[J]. Computer Engineering, 2012,8(5):179-182.)

[14] VIJAYANARASIMHAN S,GRAUMAN K. Efficient region search for object detection[C]∥CVPR’11 Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. Washington:IEEE Computer Society, 2011:1401-1408.

【责任编辑: 祝颖】

Deformable Object Detection Based on Interactive Segmentation Algorithm

PuBaoming1,HuoHong1,YangDongsheng1,LiXiangze2

(1. Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang 110004, China; 2. School of Information Science and Engineering, Northeastern University, Shenyang 110819, China)

As low efficiency in algorithm of detection with high precision, a kind of interactive object segmentation based level-set is proposed to improve efficiency. The proposed algorithm firstly applies interactive object segmentation to preprocessing the image, and then detects every area with part-based model. Traditional histogram of oriented gradients is used to describe a component model. It’s particularly important for high resolution image to segment image in advance for reducing detecting range of the detection window. The results show that, the proposed method has obvious improvement in efficiency comparing with the exhaustive search by sliding window.

object detection; image segmentation; interactive segmentation; histogram of gradients vector; deformable part-based model

2016-01-30

国家科技重大专项资助项目(2013ZX04007031; 2012ZX01029001-002).

蒲宝明(1966-),男,辽宁沈阳人,中国科学院沈阳计算技术研究所研究员,博士生导师,博士.

2095-5456(2016)04-0296-06

TP 391.4

A