杭朱飞,潘峥嵘(兰州理工大学 电气工程与信息工程学院,甘肃 兰州 730050)
基于自适应mean shift算法的多人头检测
杭朱飞,潘峥嵘
(兰州理工大学 电气工程与信息工程学院,甘肃 兰州730050)
基于均值偏移(mean shift)分割算法需人工进行带宽选择和耗时长问题,本文利用直方图密度估计与真实密度之间局部协方差最小来进行自动带宽计算方法。将该方法应用于彩色图像多人头的检测中,可以有效克服因发色模型检测出现的漏检现象,该方法首先利用mean shift自动分割图像,然后利用图像的灰值形态学来增强发色的灰度特性后进行二值化,在此基础上,采用二值形态学的膨胀腐蚀算法进行预处理,从而得到若干个候选区域 最后利用轮廓的几何特征综合判断这些区域是否为人头。实验结果表明:自适应带宽的mean shift算法可快速完成,并具有较好的分割,该方法显示了良好的适用性,在检测目标发色出现白发和染色情况下,不会造成漏检,克服了发色模型检测的缺陷。
均值偏移;直方图密度估计;协方差;形态学;发色模型
在复杂背景下进行人头检测(Head Detection)是智能视觉处理系统的重要组成部分。在现实中,基于单一特征(如头部轮廓、发色及相关统计特征等)的头部检测方法容易出现目标区域的误检测,因此基于多特征的头部目标检测是研究的热点。
常用的人头检测算法有两大类:一是基于先验规则的,比如发色模型形状[1]和肤色等[2];另一类是基于特征和分类器的检测方法,比如寻找人头轮廓,然后采用支持向量机SVM(support vector machine)、AdaBoost[3]、神经网络等分类器进行训练。
基于先验规则的方法,其主要思想是通过对大量的实验数据统计,得出一个模型,然后利用提取出的模型来准确地检测人头;但是,先验模型的提取容易受到光照影响,造成获取的模型不准确,从而导致人头检测方法失败。基于特征提取和分类器训练的方法具有良好的鲁棒性,人头检测的正确率也很高;但是分类器的训练比较耗费时间,如果特征数目比较多还会增加空间复杂度。基于上述两类方法的基础上,本文提出利用mean shift的彩色图像分割算法的人头检测方法,文中采用的自适应mean shift算法是一种特征空间聚类算法[4],它的一个突出优点是不须人为地设定过多参数而可以得到较为客观的分割结果。灰度图像处理包括选择式掩模平滑和灰值形态学进行处理,以提高头部目标的灰度与背景的区别,为阈值分割的预处理和为轮廓特征进行人头检测提供基础。
1.1mean shift基本算法
Mean shift算法是一种非参数密度梯度估计过程,也是一种有效的统计迭代算法,最早由 Fukunaga和 Hostelel提出,而后由 Cheng以及Meer[5]等改进了mean shift算法中的核函数和权重函数,并将其应用于聚类和全局优化,才扩大了该算法的应用范围,得到了进一步发展[6]。
mean shift算法的基本思想是通过沿着特征空间内样本密度梯度方向进行反复迭代搜索,使各样本点最终收敛于临近的局部密度极大点。对于d维欧式空间Rd中的一个特征数据点中xi,i=1…n,假定d×d带宽矩阵为Hi,它量化不确定的特征数据点xi,密度估计的核函数用高斯核函数,则在Rd空间中点x估计的密度概率值为:
其中,D2(x,xi,Hi)≡(x-xi)TH-1i(x-xi)表示马氏距离从 x 到xi。
让Hh为在每个数据加入权重得:
其中权重:
满足则fv密度梯度估计为:
将式(4)左乘
由式(6)可得,均值平移向量与概率密度估计成反比,因此均值平移向量的方向总是指向概率密度增加最大的方向,即均值朝附近数据样本密集区域移动。因此,n采样点可以漂移到概率密度函数的局部极大值点[7]。
假如带宽矩阵Hi等于固定带宽H,则式(1)减少了Hi变量,转化为:
而式(6)变为:
在固定带宽下,通过迭代运算进行模点搜索,为了找到每个数据点到类中心[8],而以模点的颜色来代替本类数据点的颜色,从而平滑图像,也正是因为固定带宽导致了迭代运算复杂而耗时长。在理论上,可变带宽的分割效果会更加好,但是它要依靠带宽矩阵Hi的选择,下面将会讨论合适估计带宽矩阵Hi。
当给定核函数、允许误差ε及初始点x,通过mean shift算法不停迭代,核函数的中心点将收敛到数据空间中密度最大的点,其迭代过程如下[9]:
1)计算mean shift矢量m(x);
2)计算样本均值与像素点之间的偏移量m(x)-x;
3)判断如果‖m(x)-x‖<ε,结束循环,否则把m(x)赋值给采样点x执行(1)继续,直到满足条件。
1.2带宽自适应
在聚类中,带宽h决定了核函数的影响范围,带宽h对核函数估计过程以及最终的聚类结果都有很大影响。如果h取值太过下,密度函数相当于n个数据点最后聚类为很多类,也就是过分分割。如果h很大,所有像素的密度接近与1且聚类成很少的类,这样就失去分割的意义,也会导致耗时。所以,尽可能准确的密度估计结果和聚类结果来自于带宽h的选择。选择窗宽h时应尽可能的使密度函数体现原始数据的分布特性。
1.2.1直方图
文中使用直方图密度估计对图像的像素点的特征进行统计,直方图是一种统计图,对于一幅图像来说,通过统计图像中各个像素点的数量,从而对图像的像素分布有一个直观了解。这种办法存在很多缺陷,例如估计出来的密度概率密度有很多毛刺,不是连续光滑的曲线,需要进行平滑处理,比较的直观的表现如图1所示。
图1 直方图光滑处理
对于一幅彩色图像来说,不同与灰度图像是单通道图像,它是包含RGB的三通道,但是获取步骤是相同的,计算其二维直方图就可以[10]。对于RGB图像,由于其处理是计算量较大,先将其转化为LUV空间,根据文献[11]LUV和Lab彩色空间最接近人对色彩的感官认识。基于这种原因,选用LUV作为 mean shift分割的目标彩色空间,L分量表示图像的亮度,U、V分量表示图像的色差。而对于一幅图像的直方图定义如下:
一幅图片在范围[0,G]内共有L个灰度级,其直方图定义为离散函数h(rk)=nk,其中rk是区间[0,G]内的第K级亮度,nk是灰度级为rk的图像中的像素数。
1.2.2带宽选择理论
有数学知识可知基本特性的标准梯度正态分布,它是估计成比例向下偏移的[12]。利用此属性导致的直接结果是:在大样本近似范围之内,估计偏差值可以被取消,使得潜在分布的数据,在确定的范围内有协方差估计。如果假设:在数据点x位置的附近,不确定的偏移值μ和协方差矩阵是服从多态正态分布的。协方差矩阵直接估计通常很难的,因为局部自适应正态分布需要一个领域大小范围内拟合参数是估计的先验知识。如果估计值是领域范围内的,则需要拟合最优的规模不变测度。然而下面的理论对于这个问题提出了一个简洁解决办法。这个理论就是:假设数据点的真实分布f是服从正态分布N(μ,∈),固定带宽的mean shift计算使用标准高斯核函数KH,那么当带宽H=∈时,均值偏移向量的模值最大值,因此样本服从正态分布时,可以自动计算出带宽H=∈。而由数理统计的知识可知,在样本量较大时,一般认为其服从正态分布。
文献[7]可知因为真实分布f和协方差矩阵∈是服从多态正态分布,所以密度概率值也是服从正态分布的和协方差∈+H。同样的,密度梯度估计是线性转换得到可知在样本量较大时,均值偏移的协方差相对较小,由式(8)可得:
带宽的mean shift的规范由下式给出如下,具体的证明过程可看文献[14]:
该理论导致一个有趣的比例选择规范:基本分布具有局部的协方差等于带宽最大化的归一化mean shift矢量的幅度[13]。由于该理论是应用在求取每个模点中,一个解决方案(最小二乘法[14])可以通过使用获得mean shift轨迹表示多个测量所有数据点会聚到相同模点。归纳带宽矩阵选择的办法如下:
假设n个数据点表示为xi,i=1…n,相应的带宽为减少计算量区比例单位阵形式
1)在直方图的分区级别内进行带宽估计,对于每个带宽Hj,i=1…k,
①用mean shift算法迭代;
②使用模点的均值和协方差组成(μju,∈ju)对每个分割得的模点u进行估计;
③关联每个数据点xi均值和它模点的协方差;
2)在数据层进行带宽估计,对每个数据点xi。s
①依靠估计集合(μ1,∈1)…(μk,∈k),定义相应的正态分布p1…pk;
②通过周围分布最小的Jensen-Shannon divergence间距离来选择最稳定的一种估计(μ,∈)。∈表示对xi选择的带宽。
算法的复杂度是k次,大于使用mean shift分析一个级别的数据分割复杂度。直接使用mean shift分析所有的直方图密度级的复杂度为O(n2),其中n数据点的数量。用空间不规则密度和估计数据点的轨迹线去选择一组q个去代表数据点,那么mean shift算法会减小复杂度O(qn),其中q<<n。这样带宽自适应的mean shift算法,对于运算的时间有了较大的提高,本文使用的参考软件是Peter Meer开发的EDISON这个软件,从分割效果和性能两方面综合考虑,hs=7和hr=6.5为图像分割的最优核带宽[15]。而本文自适应的带宽会在执行时自适应,具体的效果如图2所示和具体的参数如表1所示。
图2 举例说明EDISON和本文的mean shift
表1 EDISON和本文的mean shift时间比较
2.1人头检测算法的总体框架
本研究的整体流程如图3所示,主要包括mean shift分割、灰度处理、轮廓特征提取和特征判断4大部分。
图3 人头检测算法流程图
2.2mean shift分割
根据mean shift算法进行分割,由上文的推倒公式(1)~(11)可知:影响mean shift算法主要性能的主要因素是带宽H大小的选择和K(x)核函数形式的选择。文献[12]表明:在实际应用中,不同形式的核函数对分割结果的影响远没有带宽大小的影响大。通过mean shift算法实际物理意义的理解,带宽H控制着影响当前数据点的影响半径,不同的带宽对分割效果影响很大。在带宽比较小的时候,图像处于过分割状态(即过度分类),分割后的区域数最多,看不出明显的聚类特征,使得本来应该属于一个类别的特征点被分散成多个类别,但耗时最短。随着带宽的增加,耗时增加,分割区域数逐渐减小。因此,只有使用合适的带宽,才能将数据集进行很好的分类,应用本文提出的自适应mean shift有比较好的结果,看上文。
2.3灰度处理
灰度处理包括图像平滑和灰度形态学。平滑是一种实用的图像处理技术,能减弱或消除图像中高频率分量,可是不影响低频率分量。因为高频率分量主要对应图像中的区域边缘等灰度值具有较大较快变化的部分,平滑滤波将这些分量滤去可以减少局部灰度起伏,使图像变得比较平滑。本文使用选择式掩模平滑,它克服了尖锐变化的边缘或线条变得模糊的缺陷,可以保留一定的边缘信息。灰度形态学中的膨胀即以结构元素f(x,y)为模板,搜寻图像在结构基元大小范围内的灰度和的极大值。腐蚀运算过程则是以结构元素f(x,y)为模板,搜寻图像在结构基元大小范围内的灰度差的极小值。
2.4轮廓特征提取
利用阈值分割后得到二值化处理后的图像中存在着若干连通区域,即人头候选区域。此时这些区域中可能存在孔洞或者边缘存在毛刺,故首先对二值图像使用膨胀、腐蚀算子进行形态学闭运算操作,结构元素选择经典的3×3的模板;然后对闭运算的结果图像进行边缘检测。
2.5特征判断
对于上一步得到的轮廓序列进行逐个判断筛选。判断的条件为一些先验知识,分别有离散度、占空比、面积、周长等。离散度C的定义为C=P2/AO,占空比Z的定义为Z=AO/AR其中,P是轮廓的周长,AO是轮廓包围区域的面积,AR是轮廓的外接矩形的面积。这些先验知识中的面积和周长需要根据实际采集的图像中人头的大小范围进行设定。而离散度和占空比是一个比值,理想状态下不会根据人头的大小而改变。本研究对实际获取的人头图像进行反复实验,选定离散度阈值为18、占空比阈值为 0.8时效果比较好。完全符合这4个特征指标的轮廓即可判定为人头区域。
在VS2012+VC++环境下,对于垂直摄像头下采集的视频进行处理,进而验证本研究的可行性和有效性。具体实验结果见图4。
图4中,(a)至(e)为不同发色的多人头处理结果。(a)为彩色原始图像,(b)为用了Mean shift算法对图像进行分割的结果,比较完整地分割出了头部目标区域,但是同时也分割出了部分伪目标区域,(c)是s经过灰度化处理和阈值分割后获得区域的结果,(d)是对(c)进行了二值形态(腐浊和膨胀)的结果,(e)为轮廓提取之后进行特征判断的结果图像。(f)至(j)为发色和衣服颜色类似的多人头处理结果。(f)为彩色原始图像,(g)为用了Mean shift算法对图像进行分割的结果,出现了因衣服颜色和发色类似的灰度级出现了伪目标区域,(h)是经过灰度化处理和阈值分割后获得区域的结果,(i)是对(h)进行了二值形态(腐浊和膨胀)的结果,(j)为轮廓提取之后进行特征判断的结果图像,特征条件的离散度是关键。
图4 人头检测结果
本研究带宽自适应mean shift分割算法同EDISON软件使用的算法进行比较,由图2和表s1能知道:在分割效果基本相同的情况下,执行mean shift的时间缩短明显。本文将其应用在多人头检测下,能有效地去除非人头区域的干扰,同时不会因为发色出现漏检的现象,与利用发色模型进行头部目标检测存在优势。而获得的目标候选区域利用的是提取轮廓的特征(离散度、占空比、面积、周长等)进行判断,与利用Hough变换建立圆存在性模型来说有更加好的实用性和适用性。
[1]Min Zhao,Dihua Sun,Hengpan He.Hair-color modeling and head detection[C].Proceedings of the 7th World Congress on Intelligent Control and Automation,2008:7768-7772.
[2]McKenna J,Gong S,Raja Y.Modeling facial color and identity with Gaussian mixtures[J].Pattern Recognition,1998,31(12): 1883-1892.
[3]孙棣华,闫川,赵敏,等.结合梯度与彩色直方图的人头识别[J].重庆工学院学报:自然科学版,2007,21(12):1-5.
[4]Fukunaga K,Hostetler L D.The estimation of the gradient of a density function with applications in pattern recognition[J]. IEEE Trans on information Theory,1975,21(1):32-40.
[5]Comaniciu D,Ramesh V,Meer P.Kernel-Based Object Tracking[J].IEEE Trans on Pattern Analysis and Machine Intelligence,2003,25(5):564-575.
[6]周芳芳,樊晓平,叶榛.均值漂移算法的研究与应用[J].控制与决策,2007,22(8):841-847.
[7]文志强,蔡自兴.Mean shift算法的收敛分析[J].Journal of Software,2007,18(2):205-212.
[8]Comaniciu D,Meer P.Mean shift:A Robust Approach toward Feature Space Analysis[J].Pattern Analysis Machine Intelligence,2002,24(5):603-619.
[9]熊平,白云鹏.带宽自适应Mean shift图像分割算法[J].计算机工程与应用,2013,49(23):174-176.
[10]马瑜,梁慧琳,张艳宁.自适应的均值漂移分割算法[J].激光与红外,2013,43(10):1162-1165.
[11]贲志伟,赵勋杰.基于Mean Shift算法提取彩色图像有意义区域[J].激光与红外,2009,39(9):1004-1008.
[12]Stoker T.Smoothing Bias in Density Derivative Estimation[J]. Statistical Assoc,1993,88(423):855-863.
[13]Comaniciu D,Ramesh V,Meer P.The Variable Bandwidth Mean Shift and Data-Driven Scale Selection[J].International Conference on Computer Vision-ICCV,2001:438-445.
[14]Dorin Comaniciu.An algorithm for Data-Driven bandwidth selection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(2):281-288.
[15]赵敏.单目视觉多行人目标检测与跟踪计算研究[D].重庆:重庆大学,2010.
Multi head target detection based on adaptive mean shift algorithm
HANG Zhu-fei,PAN Zheng-rong
(College of Electrical and Information Engineering,Lanzhou University of Technology,Lanzhou 730050,China)
Segmentation algorithm based on mean shift(mean shift)need to manually select the bandwidth parameters timeconsuming problem,In the paper,method use the histogram density estimation between tap density and the local minimum covariance to automatic bandwidth calculation.The method is applied to a color image for detecting Multiplayer head,it Can effectively overcome undetected phenomenon for hair color model.Firstly,the mean shift algorithm to automatic image segmentation,Then use the gray value morphology image to enhance hair color gradation characteristic binarization,On this basis,the use of expansion algorithm binary morphology of corrosion pretreatment,To yield a final outline of several candidate regions use geometric features integrated to determine whether the region is to succeed.Experimental results show that: adaptive bandwidth mean shift algorithm can be done quickly.it have good applicability in the detection target appears under white hair and hair color staining,will not cause missed,hair color model to overcome the defects detected.
mean shift;histogram density estimation;covariance;morphology;hair color model
TN919.8
A
1674-6236(2016)11-0189-05
2016-02-04稿件编号:201602013
甘肃省自然科学研究基金计划项目(1308RJZA273)
杭朱飞(1989—),男,浙江海宁人,硕士。研究方向:图像处理,嵌入式。