区域分割法（共7篇）
区域分割法 篇1
0引言
随着经济生产的发展,城市交通问题日益突出。为了提高现有道路利用率,保证车辆在最大限度内畅通无阻,科研人员借助计算机图像技术和人工智能技术实现了现代城市的交通智能化。
车流量监控、车速测量等都是计算机图像技术在智能交通领域中的重要应用,车道分割则是这些应用的前提。传统的区域生长法有实现方便的优势,但对于地面的大块污迹或水渍的抗干扰性差。而本文提出的基于区域生长法和霍夫变换的车道分割方法对于雨天、陈旧路面有较好的效果。
1车道分割方法
图1是方法的基本流程图,从该流程图中可以看出车道分割方法包含如下几个部分:a)用混合高斯背景建模算法获取背景图像;b)通过区域生长算法去除掉非运动区域的垂直边缘,以获得只有车道信息的垂直边缘图像;c)通过对背景图片进行垂直边缘检测获取背景环境的垂直边缘图像;d)通过霍夫变换对边缘图像进行处理,得到车道的区域分割图像。
2道路区域分离
2.1背景建模
获取准确的背景模型对于后续的图像处理具有至关重要的意义,考虑到户外存在随时间变化而产生的日光强度变化、投影位置的变化等干扰因素,本文采用混合高斯模型的建模方式对背景建模。混合高斯分布的背景模型用N个高斯分布的加权混合值来描述图像中每个像素点的背景值[1]。设某像素点(X,Y)在时刻t的观测值为Xt,于是该点的混合高斯模型计算值p(Xt)为:
其中η(Xt,ui,t,ξi,t)为t 时刻此点的第i个高斯分布概率函数;ωi,t表示t时刻第i个高斯分布的权重,且undefined;N是运算次数,N越大表明采样的数据越多,其背景模型越精确,但运算速度越慢,本文中N取了20,即选取了不同时刻的20帧图像。这种方法在光亮逐步变化的户外或室内环境的建模中都有较好的效果[2]。图2显示了通过高斯建模获取到的背景图像,注意这幅背景图像的地面上是有水渍的。
2.2获取前景图像
在获取精确的背景图像之后就可以利用背景差法获取任意一时刻的前景图像,再对此前景图像进行二值化处理,就可以获取任意时刻的前景区域。图3(a)是某时刻的原始图像,图3(b)则是经过上述方法得到的二值化前景图像。
2.3基于改进的区域生长的道路区域分离
2.3.1 改进的种子区域生长法
种子区域生长算法是假设在某一区域的像素点都相似的基础上的区域生长算法[3];它可以看作通过相似像素点而确定区域边界,最终通过区域边界来对区域进行分割的一种方法。进行有效的区域分割,要求区域有相似的灰度、色度,而种子像素又要与区域有相似的灰度、色度[4]。
由于车道积水等因素而造成图像中某一车道区域的灰度、色度与其周围区域产生明显的差别,因而误将有水或有污渍的车道区域判为非车道区域。
为了解决这个问题,我们将前景图像覆盖区域引入到区域生长法中。车辆经过的区域一是车道存在的区域,因此车辆运动区域应该成为我们判断车道存在区域的一个重要依据。所以,本文对于区域生长做法的改进是将有车辆经过的区域的相似度人为地加一个增益。这样做能更真实地反映出车道区域。
2.3.2 基于改进的区域生长法进行道路分离
我们选择种子的规则是:
(1) 种子与其领域必须有较高的相似度;
(2) 在想得到的区域内,至少能产生一颗种子;
(3) 不同区域的种子不能连接。
车辆是在车道区域中运动,种子像素就可以在运动车辆存在的区域中获得。在2.1节中,我们已经获取了二值化的前景图像,而前景图像中会包含一些面积较小的白色像素聚集的区域,这些区域往往是距离摄像机比较远的运动车辆或某些细小干扰,为此我们可以设定一个面积阈值,选取若干块面积大于阈值的聚集区域以排除干扰。
假设在t时刻的前景图像是I(x,y,t),在隔Δt时刻后的前景图像是I(x,y,t+Δt),设车辆区域的I(x,y,t)=1、非车辆区域的I(x,y,t)=0,若满足下面条件,则为运动车辆区域。
其中,R(x,y)是运动车辆区域,种子像素就可在这个区域中选取。图4就是某时刻的候选区域示意。
对于某个时间t,最好的情况是我们能够在所有车道中都获取种子像素,但最坏的情况是不能获取到种子像素,因此我们需要进行多次上述过程以在道路的不同区域获取种子像素,经过若干次累积(即分析若干帧)。
种子经生长之后能够得到若干块区域,如图5(a)所示,对其进行相似度提升然后对这些区域进行合并。合并过程为:计算所有相邻区域的距离,将这些距离放到距离表中,将距离最短的区域合并;重新计算新区域与其领域的距离,并将距离表更新;重复上述过程,直到最短的距离超出了阈值。最后,检查所有区域内的像素点个数,如果一个区域内的像素点个数在图像中所占的比例小于图像1/150,将该区域合并到最相似的领域。
但由于城市交通十字路口会存在右转弯车辆,根据如上方法还会将十字路口右转弯车辆所经过的区域判断成摄像机监控的车道,所以我们应去除这些干扰。本文采取了一个较简单而实用的方法,即在该步骤中只分析图片的底部1/4部分,这样就可以很好地排除这一干扰。图5(b)显示了利用区域生长法得到的道路区域图像。
本文也使用了传统的区域生长法进行处理,得到了一组对比图片,如图6所示。可以看到传统阈值法对于地面上的水渍不能很好地进行处理。
3车道分割
正如上节所述,车道线具有良好的直线特征,它们非常有利于我们进行直线检测以获取车道的边界。
当我们通过2.1节中介绍的方法获取到背景环境图片后,可以通过霍夫变换进行直线检测,而在霍夫变换之前又必须先对图像进行垂直边缘检测,以获取我们最需要的信息。所以本节将包含垂直边缘检测和霍夫变换两部分。
3.1垂直边缘检测
检测图像垂直边缘的方法有许多,本文采用了应用较广的索贝尔算子对背景图像进行垂直边缘检测,它是一离散性差分算子,用来计算图像亮度函数的梯度的近似值,在图像的任何一点使用此算子,将会产生对应的梯度矢量或是其法矢量[5]。
本文选取的索贝尔算子为:
undefined
。通过如下公式转换得到垂直边缘图:
可以看到检测出来的垂直边缘图片中包含了很多非道路区域中植物和其他物体的垂直边缘,这些边缘对于我们来说都是没有利用价值的信息,这些信息都可能造成对直线的误检测。而我们可以通过在第二节中检测出的道路区域去除这些没有利用价值的垂直边缘,它可以抽象为如下数学条件:
其中C(x,y)是原始的垂直边缘背景图片,R(x,y)是第二节介绍的车道区域背景图片,C′(x,y)是仅有车道区域垂直边缘的背景图片。
用索贝尔算子检测垂直边缘的关键代码如下:
通过以上算法,我们得到了如图(7)所示的垂直边缘图片。
3.2通过霍夫变换进行直线检测
经过垂直边缘检测,车道分割线就可以通过若干条相互平行的直线进行估计,而我们通过霍夫变换可以非常容易地将这些直线检测出来。
霍夫变换的基本思想是点和线的对偶性[6]。我们知道直角坐标和极坐标是存在对应关系的,霍夫变换根据这些关系把在图像空间中的检测问题转换到极坐标空间里。通过在极坐标空间里进行简单的累加统计完成检测任务。
直线的极坐标方程为:
ρ=xcosθ+ysinθ 0≤θ≤π (4)
其中ρ是原点到直线的距离,θ是直线的法线与X轴的夹角。这样,一条直线就可以用ρ值和θ值来表示。而霍夫变换就是在极坐标空间(ρ,θ)里建立一个累加数组H(ρ,θ);对二值垂直图像中每个以1表示的点(x,y),让θ取遍θ轴上所有可能的值,并根据式(4)计算对应的ρ;再根据ρ和θ的值(设都已经取整)对数组H(ρ,θ)进行累加;最后对H(ρ,θ)进行局部峰值检测,最终以统计的方法获取检测直线的ρ和θ值。
如果检测出的某些直线属于图像中的一条真实直线,那么它们将会有相似的ρ和θ值,即满足下式:
其中,Tρ,Tθ分别代表阈值。
因此将这些直线通过下式可得出真实直线的ρ和θ值:
霍夫变换的关键代码如下:
通过如上方法,可以得到如图8所示的车道直线。
3.3获取各车道区域
经过如上的方法检测出的直线往往还会包含一些非车道分割线的直线,比如某些车道会标有箭头标志,而箭头的直线也会被检测出来,于是我们还需要进行筛选。根据经验,我们知道箭头往往出现于车道的中间,而车道中间往往是车辆运动必须经过的区域,如果我们在第二节介绍的方法中加入对车辆运动区域的统计,很容易获得车辆最多通过的区域,而这个区域就是车道的中间即箭头所在的位置。通过这个方法,我们可以将该区域中所检测出来的直线去除,这样就去除了车道中间的箭头标志,而剩下来的就是车道线。
实现方法的伪代码如下:
至此,我们已经获取了道路中所有的车道线,在两车道线中间的图像区域就是车道所在的区域。
4结语
本实验采用基于达芬奇数字图像处理芯片TM320DM355的TI达芬奇开发平台。TMS320DM355由一个集成视频处理子系统、一个DSP内核和一个ARM内核组成,可提供216MHz或270MHz的时钟速度。
实验数据由江西省景德镇市交警大队提供。摄像机设于高约5.5米的立柱上,图像采集与车辆较少的时段,这有利于建立精确背景模型。经实验,对普通城市车道具有较好的分割功能,能够达到98%以上。虽然本方法是基于高清视频信号,但对于普通的标清信号也具有一定的借鉴价值,表1列出了对于不同大小的图片该算法的平均耗时。
同时,该方法也存在一些问题:如由于实际分割线老化磨损而造成的分割不准确等。这些问题还待今后的研究。
摘要：车道分割在智能交通监控系统中起着基础而重要的作用。精确地进行车道分割是车流量统计、车速测量等诸多智能交通应用的前提。以往基于种子区域生长法的车道分割方法对于较新且干燥的道路有较好的分割效果,但受地面上水渍、污渍、斑驳的影响较大,鲁棒性不强。为了解决这个问题,提出一种基于改进的种子区域生长法和霍夫变换的车道分割方法。通过改进的区域生长法,可以有效降低水渍、污渍、斑驳的干扰,提高系统的鲁棒性。
关键词：智能交通,改进的区域生长,霍夫变换,道路分割
参考文献
[1]刘静,王玲.混合高斯模型背景法的一种改进算法[J].计算机工程与应用,2010,46(13).
[2]张恒,胡文龙,丁赤飚.一种自适应学习的混合高斯模型视频目标检测算法[J].中国图象图形学报A,2010,15(4).
[3]姜慧研,司岳鹏,雒兴刚.基于改进的大津方法与区域生长的医学图像分[J].东北大学学报:自然科学版,2006,27(4).
[4]王佳男.采用基于区域的自动种子区域生长法的彩色图像分割方法[D].长春:东北师范大学,2007.
[5]庄严.移动机器人基于多传感器数据融合的定位及地图创建研究[D].大连:大连理工大学,2004.
[6]吴欣,张志伟.基于形态学和霍夫变换的文档图像倾斜检测[J].南京理工大学学报:自然科学版,2009,33(2).
基于区域分割的伪装迷彩设计研究 篇2
图像分割是将图像中的像素按照特征的不同而进行分类的过程。总体上可以分为两大类,一类是基于边缘的图像分割,即边缘检测;另一类是基于区域的图像分割,即区域分割。针对图像区域分割的具体要求已经建立了许多算法,然而至今仍无统一的理论,不能找到通用的方法能够适合于所有类型的图像。利用各种算法分割出来的区域与正确存在的分割之间可能出现误差。误差有三种类型:(1)分割后的图像增加了新的区域;(2)应有的区域未被分割出来;(3)所用的分割算法没有正确给出边界定位。
由于彩色图像提供的信息比灰度图像更加丰富,因此随着计算机处理能力的快速发展,彩色图像处理受到了人们越来越多的关注。彩色图像分割是指在一幅彩色图像中分离出主要的、色彩一致的区域。
本文在介绍区域分割相关知识的前提下,结合伪装迷彩设计的背景分割试验,验证了区域分割在迷彩图像分割中的分割效果。
1 区域分割
1.1 区域分割的算法
从某种角度来讲,图像分割的目的之一就是目标提取,即将人们感兴趣的区域提取出来。从这一点上来说,区域分割是最直接的方法,利用这种方法可以直接得到感兴趣的目标区域。基于区域的分割主要依赖于图像中区域的连续性,一般包括区域生长、分裂和分裂-合并等方法,通过计算欧几里德空间距离来比较两个像素颜色之间的差别。
根据分割过程中处理策略的不同,分割算法可分为并行算法和串行算法。在并行算法中,所有判断和决定都可独立地、同时地做出,而在串行算法中,早期的处理结果可被其后的处理过程所利用。一般串行分割算法所需要的计算时间常比并行分割算法要长,过程控制较复杂,但抗噪声能力也较强。
1.1.1 并行区域分割
并行区域分割技术是把图像分成前景和背景,采用并行的方法对目标区域进行检测实现图像分割的方法。主要有阈值分割和聚类两种方法。
阈值分割的基本思想是确定一个阈值,然后把每个像素点的像素值和阈值相比较,根据比较的结果把该像素划分成两类———前景或者背景。
由上述定义可知阈值分割方法的关键问题是选取合适的阈值。阈值一般可写成如下形式:
其中f(x,y)是在像素点(x,y)处的灰度值,p(x,y)是该点邻域的某种局部性质。即,T在一般情况下可以是(x,y),f(x,y)和p(x,y)的函数。借助上式,我们可将阈值分割方法分为以下三类:
1)如果仅根据f(x,y)来选取阈值,所得的阈值仅与各个图像像素的本身性质相关(也称全局阈值,此时确定的阈值对全图使用);
2)如果阈值是根据f(x,y)和p(x,y)来选取的,所得的阈值就是与(局部)区域性质相关的(也称局部阈值);
3)如果阈值进一步(除根据f(x,y)和p(x,y)来选取外)还与x,y有关,则所得的阈值是与坐标相关的(也称动态阈值,且可将前两种阈值对应称为固定阈值)。
无论采用何种方法确定阈值,目的只有一个,就是使分割的结果更好,但是任何一种方法都不能在理论上给予保证。
1.1.2 串行区域分割
串行区域分割是指采用串行处理策略对目标区域直接检测来实现分割的方法。
1)区域生长:区域生长是指从某一像素出发,按照一定的准则,逐步加入邻近像素,当满足一定条件时,生长终止。初始点(种子点)的选取、生长准则和终止条件的选择关系到区域生长结果的好坏。
2)分裂合并:分裂合并差不多是区域生长的逆过程:从整个图像出发,不断分裂得到各个子区域,然后再把前景区域合并,实现目标提取。分裂合并的假设是对于一幅图像,前景区域是由一些相互连通的像素组成的,因此,如果把一幅图像分裂到像素级,那么就可以判定该像素是否为前景像素,当所有像素点或者子区域完成判断以后,把前景区域或者像素合并就可得到前景目标。
1.2 颜色空间的选择
颜色空间大体可分为三类:面向设备的颜色空间,适合在输出显示场合下使用,但与人眼的视觉感知有一定的距离;面向视觉感知的颜色空间,在这里人们通过将人类对颜色的观察情况组合而建立的孟塞尔(Munsell)颜色空间是一个基本的颜色空间,它主要基于主观观察,用于艺术领域。在此基础上,人们又提出了许多对孟塞尔系统近似的比较客观的颜色空间,如HIS、HSB等。这些颜色空间与人类关于颜色的视觉感知比较接近,同时独立于设备,是非线性的。均匀颜色空间,本质上仍是面向视觉感知的颜色空间,只是在视觉感知方面更为均匀。
线性变换空间有YIQ,YUV,I1I2I3等,它们部分消除了RGB的相关性,由于其是线性变换,因此计算量小,其中,Y分量常用于边缘检测,而I1I2I3则能够更有效地用于彩色图像处理。
非线性变换空间有HIS(HSB,HSL,HSV为HIS的变形),归一化RGB,YT1T2,均匀颜色空间CIE(L*a*b)以及CIE(L*u*v)等,其中HIS与人眼的色彩感知相吻合,其在一些照明不均的场合特别有用,因色调与高亮、阴影无关,色调对区分不同颜色的物体非常有效。虽然非线性变换空间消除了3个颜色分量间的相关性,适合于图像处理,但由于是非线性变换,计算值极大。
2 区域生长法在伪装迷彩设计中的应用
在伪装迷彩设计中,为了达到好的伪装效果,迷彩颜色需与背景色调相融合,以便使人眼和光学仪器难以分辨和探测。因此,背景的准确分割是确保迷彩颜色与背景融合的前提。这里取山区高空拍摄植被的光学照片为样本,如图1所示。结合彩色图像生长法分割理论进行试验。
彩色图像分割中,区域生长法是最具代表性的方法之一。它的基本思想是将具有相似性质的像素集合起来构成区域。首先对每个需要分割的区域找出一个种子像素作为生长的起点,然后将种子像素周围邻域中与种子有相同或相似性质的像素(根据事先确定的生长或相似准则来确定)合并到种子像素所在的区域中。而新的像素继续做种子向四周生长,直到再没有满足条件的像素可以包括进来,一个区域就生长而成了。
在对图1中样本图进行区域生长法时需要解决三个问题:1)选择或确定一组能正确代表所需区域的种子像素(选取种子);2)确定在生长过程中能将相邻像素包括进来的准则(确定门限);3)确定让生长过程停止的条件或规则(停止条件)。
由于区域生长法能够直接作用于颜色空间,在分割过程中同时考虑了颜色分布以及其空域上的重新划分,因此,它较其他方法更适合于彩色图像分割。
为了提高试验的计算效率,我们在试验中,选取图1中的64*64像素作为分割区域为例,即如图2所示。选择在HIS颜色空间下进行分割试验。首先把图像中的第一个未被分配到相应颜色类别的像素作为标准像素,取该像素的颜色作为标准颜色,并定义为一新的颜色类。在图像中,按从上到下,从左到右的顺序,搜索未被分配颜色类别的像素,参照色度饱和度、亮度、颜色相似度系数以及颜色相似性判决条件判定其是否与该标准颜色的相似。
令A表示衡量像素相似程度的特征函数,Bk代表第k步时生长的区域,则Bk的区域特征函数为A(Bk)。同样,令当前像素为s(i j),其特征向量为A(s),区域增长算法的核心就是比较A(Bk)与A(s)的特征距离是否满足一定的阈值T。假如A(Bk)-F(s)
根据上述过程,对所选取的样本子图进行区域生长分割试验,得到的试验效果如图3所示。
由分割后图像我们可以看到,选取的分割区域经过生长分割后得到了几个不同的区域,各区域间有较为明显的边界。
3 总结
本文对彩色图像的分割方法以及颜色空间相关知识做了概括介绍,并应用生长法给出了试验结果。从分割试验效果可以看出,通过将一种子像素作为生长起点,然后将种子像素周围邻域中与种子像素有相同或者相似颜色特征的像素合并到种子像素所在区域,再将这些新像素当作种子像素继续上述过程,直到没有满足条件的像素可以包括进来这一算法,能够较好的实现彩色图像的分割,从而实现伪装迷彩设计中背景图像的分割。
摘要：该文主要介绍了图像分割技术的发展现状以及区域分割的方法,并对颜色空间的分类及其各类的特点做了简单的介绍。在对区域生长法原理及算法介绍的基础上,结合山地高空所拍摄植被的光学照片,进行伪装迷彩设计中的背景分割试验,从而验证区域生长法在彩色图像分割中的分割效果。
关键词：彩色图像分割,颜色空间,区域生长,伪装迷彩
参考文献
[1]朱虹.数字图像处理基础[M].北京:科学出版社,2005.
[2]章毓晋.图像工程(上册):图像处理和分析[M].北京:清华大学出版社,1999.
[3]李唯为,黄辉先.种子区域生长技术在彩色图像分割中的应用[J].小型微型计算机系统,2008,6(6):1163-1167.
[4]林开颜,吴军辉,徐立鸿.彩色图像分割方法综述[J].中国图象图形学报,2005,10(1):1-10.
[5]范立南.图像处理与模式识别[M].北京:科学出版社,2007.
基于区域分割的二次质心定位算法 篇3
关键词：初次质心定位,二次质心定位,定位误差,区域分割
0 引言
无线传感器网络WSN(Wireless Sonser Networks)作为一种全新的技术，在国防军事、交通管理、制造业、环境监测、医疗卫生、反恐抗灾等领域得到了广泛的应用，在其众多的应用中，均须知道事件发生的位置，因此，节点定位技术是无线传感器网络的主要支撑技术之一。目前，无线传感器网络的定位算法可分为基于测距的算法和无需测距的算法两种[1]。基于测距的算法通过测量节点间的距离或角度信息，使用三边测量[2]、三角测量或最大似然估计法[3]计算节点的位置;无需测距的算法则根据网络的连通度等信息来实现节点定位。无需测距的算法属于粗粒度定位，定位精度较低，但在对硬件的需求及受实际环境的影响程度上与基于测距的定位算法相比都有很大的降低，因此也得到了较为广泛的应用。
在无需测距的算法中，质心定位算法[4]由于计算成本较低、网络生存能力较强、实现简单等优点而成为众多学者研究的热点。该算法在锚节点均匀分布时表现出较好的性能，当锚节点分布不均匀的时候，质心定位算法的定位精度会大幅下降。为了解决这一问题，以文献[5,6,7,8]为代表的方法主要通过不同信标节点的不同影响力来进行改进，文献[9,10,11,12]等主要从信标节点的分布角度来进行改进。本文主要针对未知节点周围分布的锚节点不均匀而产生较大的定位误差这一问题提出了一种改进的质心定位算法，用初次质心定位的估计位置取代离未知节点距离最远的锚节点，进行二次质心定位，有效地提高了质心算法的定位精度。
1 质心定位算法
1.1 质心定位算法原理
质心定位算法是一种仅基于网络连通性的室外定位算法。信标节点周期性地向邻居节点广播包含自身标识和位置信息的数据包，当未知节点接收到来自某一信标节点的数据包数量超过某个值或接收一定的时间后，就确定该信标节点处于自身的通信范围内，并将其通信范围内的所有信标节点构成的几何质心作为自身的估计位置。设某一未知节点通信范围内的信标节点个数为n，坐标分别为(xi,yi)，其中i=1,2，…，n，该未知节点的估计位置为(xe,ye)，则有:
显然，质心定位算法完全基于网络的连通度，方法简单，运算复杂度低。
1.2 质心定位算法缺陷
为了减少运算量，质心算法一般取接收到的信号能量值较大的三个信标节点构成三角形，将三角形的质心作为未知节点的估计位置。当信标节点是均匀分布的时候，采用质心定位算法可以取得较高的定位精度。然而，在诸如森林防火、环境监测等众多的应用场合中，信标节点不可能按照一定的位置预先布置好，即信标节点往往都是随机分布的，在这种情况下，质心定位算法会产生较大的定位误差。如图1所示，信标节点A、B、C在未知节点S的通信范围内呈不均匀分布，质心算法结果将未知节点定位在I点。在图1所示的三种情况中，均是信标节点A离未知节点的实际距离较远，由于其产生的负面作用力，使得未知节点的估计位置I不同程度地偏向A点，未知节点的实际位置距A点越远，偏离程度越大。因此，在实际的定位过程中，由于信标节点的不均匀分布使得质心定位算法的定位结果向距未知节点距离较远的信标节点一侧偏移，会产生较大误差。
2 二次质心定位算法
为了解决距离较远的信标节点对未知节点估计位置的负面影响，文献[5,6,7,8]等提出给距离未知节点较远的信标节点以较小的权值，给距离较近的信标节点以较大的权值，以此来消弱较远的信标节点的影响力，使未知节点的估计位置能更接近其真实位置;文献[9,10,11,12]则采用几何空间上覆盖所有锚节点的区域来估计目标位置，来有效地控制由于锚节点分布不均匀给定位精度带来的波动，这两类改进方法在一定程度上取得了较好的效果。不同于上述方法，本文结合三角形区域分割，用初次质心定位结果取代距未知节点距离最远的信标节点，进行二次质心定位，来减小定位误差。
2.1 区域分割
在理想的条件下，RSSI值和距离之间存在着一定的衰减关系，RSSI值越大，收发两方的距离越近，反之，距离越远。对于无线传感器网络节点而言，其RSSI值又很容易获取，因此可以通过比较未知节点S在同一时刻接收到三个顶点A、B、C发送来的信号强度，进一步的判断未知节点S距哪一个顶点较远，也就是缩小未知节点S在△ABC内可能存在的区域范围，确定二次质心算法所要取代的信标节点。
详细地说，利用有效三角形的三条中垂线将三角形及其周围的区域进行分割，以三条中垂线的交点P及由三条中垂线形成的6条射线为边界，将三角形及其周围的区域分割成6个区域。有效三角形为锐角三角形、直角三角形或钝角三角形时，分割情况分别如图2(a)、(b)、(c)所示。根据中垂线上的点到两端点的距离相等和比较未知节点接收到顶点发送来的信号强度，可以进一步的判断未知节点属于哪个区域。
以图3为例，RA、RB、RC分别表示未知节点S收到来自信标节点A、B、C的信号强度，SA、SB、SC分别表示未知节点S与信标节点A、B、C之间的距离，且需找出距未知节点S距离最远的信标节点，即需比较出RA、RB、RC中哪个值最小。根据这一需求在比较三个信号强度的大小时，可能会出现如下三大类情况。
情况一检测到其中两个信号强度值均大于另外一个信号强度。若检测到RA>RB且RC>RB，则有SA>SB且SC>SB，可判断出未知节点S距B点最远，通过检测到的RA>RB可推断未知节点S在并集区域P=﹛区域1∪区域6∪区域5﹜中，通过检测到的RC>RB可以推断未知节点S在并集区域Q=﹛区域4∪区域5∪区域6﹜中，综上可以推断未知节点S在区域TB=P∩Q=﹛区域5∪区域6﹜;同理，若检测到RA>RC且RB>RC，可推断未知节点S距C点最远，且S处于区域TC=﹛区域1∪区域2﹜中;若检测到RC>RA且RB>RA，可推断未知节点S距A点最远，且S处于区域TA=﹛区域3∪区域4﹜中。通过以上分析，可知，若未知节点S与B点距离最远，则S一定处于由射线PD和射线PE组成的区域中;若S距C点距离最远，则S一定位于由射线PE和射线PF组成的区域中;若S距A点距离最远，则S一定位于由射线PD和射线PF组成的区域中。三角形ABC及其周围的区域被射线PD、PE和PF划分为3个不同的区域，如图3(b)所示。
情况二检测到其中一个信号强度大于另外两个信号强度，且较小的两个值相等。若检测到RA>RB=RC，则有SA>SB=SC，可判断出S距B和C的距离一样远，通过检测到的RA>RB，可推断节点S在并集区域P=﹛区域1∪区域6∪区域5﹜中，通过检测到的RB=RC，可推断节点S在BC边的中垂线EH上，综上可以推断未知节点S在区域P和直线EH的并集区域，即在射线PE上;同理，若检测到RB>RA=RC，可推断节点S距A点和C点的距离一样远，且S在射线PF上;若检测到RC>RB=RA，可推断节点S距A点和B点的距离一样远，且S在射线PD上。
情况三检测到三个信号强度一样大。在这种情况下，未知节点S距三个节点A、B、C的距离一样远，S位于三角形ABC的垂心P处。
2.2 二次质心算法原理
对图1进行分析可知，如果以A方向上的某个距离未知节点S更近的点来取代信标节点A进行质心定位，可在一定程度上减小未知节点估计位置向A方向的偏向程度，进一步减小定位误差。基于这一思想，根据2.1节中所述的判断方法找出A、B、C三点中距未知节点S距离最远的点，假定是C点，则未知节点S应处于由射线PE、PF组成的区域内，如图4所示，用初次定位估计位置I来取代信标节点C，结合信标节点A、B构成新的三角形进行二次质心定位，估计位置为I'。由图4可以明显看出，二次质心定位结果I'更接近于未知节点的实际位置S，即SI'<SI。
2.3 误差分析
在图5中，未知节点S与信标节点A、B、C之间的关系同图4,A是被取代的信标节点，S仍处于由射线PE、PF组成的区域内，但其在该区域中的位置不同于图4，在这种情况下，由图5可以明显看出二次质心定位误差SI'大于初次定位误差SI。因此，本文所述的二次质心算法的定位误差并不是一定总是小于初次质心定位的误差，该误差和未知节点的分布位置有关。因此，需要确定当未知节点处于由射线PE和PF围成的区域中的哪些位置时，才能使二次质心定位结果优于初次定位结果，即满足SI'<SI。
作线段II'的中垂线，分别交PE、PF于M、N点，如图6所示，根据中垂线上的点到两端点的距离相等可推断，若S处于由射线PE、射线PF及中垂线MN围成的区域，即图6中的阴影区域三角形PMN，会有SI'>SI，此时，二次质心定位误差大于一次质心定位误差。为了便于描述，将由射线PE和射线PF围成的且包含线段AB的区域定义为区域TC，将区域TC中除去三角形PMN以外的区域定义为区域O，当S处于区域O中时，会有SI'<SI，此时，二次质心定位结果优于一次质心定位结果。
按照上述原理，图7分别画出了当信标节点A、B、C组成的三角形分别为锐角、直角及钝角三角形时，二次质心定位误差大于一次质心定位误差情况下未知节点S可能存在的区域，即为图中阴影部分。当未知节点处于阴影区域之外的空白区域时，二次质心定位结果一定优于一次质心定位结果。由于未知节点S有可能处于三角形外部，综合考虑三角形内外部的所有区域，由图7可以明显看出，阴影部分的面积远小于空白部分的面积，因此，我们有理由相信，在大多数的情况下，本文所述的二次质心定位算法的误差要小于一次质心定位误差，用二次质心定位结果的整体误差一定会小于一次质心定位的整体误差。
2.4 算法描述
(1)信息收集阶段
网络节点布撒后，网络进行初始化配置。信标节点向未知节点广播消息，消息中包含信标节点在网络中的ID、自身坐标信息。为了判断和信标节点之间距离的远近，未知节点还需记录来自各信标节点的RSSI值。在信息收集的时间内，未知节点随时更新其通信半径内锚节点传来的信息，通过这种方式降低由于网络拓扑结构变化原因造成的定位出错的可能性。
(2)定位阶段
(1)未知节点将其通信半径内的所有信标节点按照其接收到的RSSI值的大小进行排序，建立自身信标节点信息表，选择RSSI值较大的3个信标节点，计算出其质心，设为I(为了便于说明，此处设较大的三个RSSI值分别为RA、RB、RC，其对应的信标节点分别为A、B、C);
(2)比较RA、RB、RC的大小，若其中两个信号强度值均大于另外一个信号强度，则用第(1)步中计算出的质心I取代RSSI值最小的信标节点构成新的三角形进行第二次质心计算，并将计算出的二次质心I’作为未知节点S的最终估计位置;
(3)若RA、RB、RC中的一个信号强度大于另外两个信号强度，且较小的两个值相等，则用第(1)步中计算出的质心I取代两个较小的RSSI值所对应的信标节点中的任意一个进行二次质心定位，并将计算出的二次质心I'作为未知节点S的最终估计位置;
(4)若三个信号强度RA、RB、RC一样大，则将三角形ABC的垂心作为未知节点S的最终估计位置。算法流程如图8所示。
3 仿真实验
利用MATLAB仿真平台，在200 m×200 m的区域内随机分布200个节点，假设节点之间均能正常通信，对二次质心定位算法进行仿真，并与传统的一次质心算法进行比较。本文主要把绝对定位误差作为评估算法的主要性能指标。
绝对定位误差:
式中，(xr,yr)是节点n的真实坐标，(xe,ye)是用算法估计出的节点n的坐标。为消除节点随机分布对算法性能的影响，每种条件下均随机仿真1000次，并取1000次定位误差的平均值最为最终的绝对定位误差。
图9给出了在200个节点里，信标节点所占比例改变时，定位误差随之变化的情况。由图9可以看出，随着信标个数的增加，一次质心定位和二次质心定位的误差都呈减小趋势，但二次定位的误差总小于一次定位的误差，当信标节点的个数增大到50%以后，两种方法的定位精度提高并不明显。值得一提的是，当信标节点比较稀疏，所占比例为20%时，二次质心定位的性能远远优于一次质心定位，定位精度提高了近10米。因此，当网络中信标节点个数较少时，未知节点通信半径内的信标节点分布的不均匀性会更高，一次质心定位会差生较大误差，采用二次质心定位方法能大大提高其定位精度。
图10给出了信标节点所占比例为40时两种定位算法的定位误差的累积概率。结果显示，二次质心定位算法绝对定位误差在15米以内的的概率超过70%，而传统的一次质心定位算法达到这种精度的概率大约只有60%。
4 结语
本文提出了一种基于区域分割的二次质心定位算法，用初次质心定位结果取代未知节点通信半径内距离最远的信标节点，来减小由于信标节点分布不均匀而导致未知节点的估计位置偏向距离较远的信标节点的现象。仿真结果表明，在信标节点较为稀疏时，二次质心定位算法的定位精度远远高于传统的一次质心定位算法，且该方法无需复杂的数学运算，实施较为简单，同时能很好地应用在三维空间的场合，具有一定的应用价值。
但是，本算法中，采用RSSI值来实现未知节点和信标节点之间距离远近的判定，但RSSI值易受环境干扰，RSSI值大，并不意味着距离就近，RSSI测距的不准确性会导致算法产生额外的误差，因此，在实际的应用中需要解决RSSI测距精度的问题。
参考文献
[1]Wang Jing,Ghosh R K,Das S K.A survey on sensor localization[J].Control Theory Appl,2010,8(1):2-11.
[2]温立.无线传感器网络定位技术研究[D].上海:复旦大学,2008.
[3]刘克中.无线传感器网络分布式节点定位方法研究[D].武汉:华中科技大学,2006.
[4]Bulusu N,Heidemann J,Estrin D.GPS-less low cost outdoor localization for very small devices[J].IEEE Personal Communications Magazine,2000(7):28-34.
[5]朱建新,高蕾娜,张新访.基于距离几何约束的二次加权质心定位算法[J].计算机应用,2009,29(2):480-483.
[6]Xia A L,Ma C W.Improved centroid detection method based on higher moment for shack-hartmann wavefront sensor[C]//Optoelectronic Imaging and Multimedia Technology,Oct,2010.
[7]郜丽鹏,朱梅冬,杨丹.基于Zigbee的加权质心定位算法的仿真与实现[J].传感技术学报,2010,23(1):149-152.
[8]朱博,陈曙.一种无线传感器网络质心定位改进算法[J].传感技术学报,2010,23(6):868-872.
[9]徐小玲,张福强,李少彪.基于APIT的无线传感器网络质心算法研究[J].传感器与微系统,2011,30(7):57-59,63.
[10]衣晓,刘瑜,邓露.一种基于PIT的无线传感器网络质心定位算法[J].传感器技术学报,2010,23(7):1012-1016.
[11]周全,朱红松,徐勇军,等.基于最小包含圆的无线传感器网络定位算法[J].通信学报,2008,29(11):84-90.
区域分割法 篇4
通过基于物质度指标进行轮廓/区域分割, Vi-cente等人在文献[7]中从数幅静态图像实现“对象联合分割”。Lee等人在文献[4]中将类似思路引入视频图像分割。该文献不仅使用文献[6]中的静态物质度指标, 还使用动态指标来衡量一个区域包含移动对象的概率。他们还指出, 视频中的对象区域的运动方式与周围是不同的。尤其是, 该文献中的指标将区域的光流柱状图与周围区域加以比较。这不需要对摄像机运动做出任何假设, 仍可保持对不同运动幅度的敏感度。对区域打分后, 每个帧中分值最高的K个区域被选出来形成一个候选区域集合C。C中许多区域属于前景对象, 也有可能包括其他区域。对候选区域集合中的每两个区域, 根据非归一化颜色柱状图计算相似度。最后, 进行光谱聚类, 对候选区域集合进行内域/外域划分。每种聚类 ( 内域) 对应于一种前景对象区域假设。然后, 根据成员区域的平均物质度分值, 对获得的聚类进行排名。平均分值越高, 该聚类包含视频主要对象的概率就越大。
然而, 候选区域集合C虽然结合了所有帧中的区域, 但是忽略了每个区域来自哪个帧及区域在该帧中的位置等重要信息。本文将对这些信息加以利用, 以获得更好的区域选择效果。具体方法是, 利用不同帧中区域的二元外观关系, 并对选择的区域施加互斥约束。为公平比较, 我们选择与文献[4]中相同的视频区域物质度定义。文中对视频主要对象区域的选择主要基于以下三种重要观点: ①从派系中选择的区域应该有较高的物质度分值 ( 一元位势) , 且在各视频帧中的外观比较类似 ( 二元位势) ; ②两个相邻帧的对象区域相对来说比较接近, 因为对象的运行一般来说比较平滑; ③主要对象会出现在每一图像帧中。它可能会由于局部遮挡或自我遮挡而改变外观或形状, 但仍会出现在每幅图像帧中。
文中提出了一种新的视频对象分割算法。该算法将区域选择问题表述成在加权图G中寻找约束条件下的最大加权派系 ( MWC) , 其中每个区域对应一个结点。G的相似度矩阵A的对角线元素表示各个结点的物质度分值。非对角线元素表示两个区域间的外观相似度。图G中的最大加权派系就是权重和最大的派系, 这表明一元位势和二元位势均被考虑。在本文算法中, 我们还对最大权重派系加以约束, 以满足非线性互斥约束条件。最后的实验结果也表明了本文算法的有效性。
1 相关工作
视频对象分割问题一直是视频应用领域的研究热点问题, 相继有众多学者提出了一系列方法, 如程淑红等［8］提出了一种基于改进的最小Tsallis交叉熵的视频对象分割算法。该算法在时域中采用帧间变化检测快速区分前景与背景, 在空域中使用改进的最小Tsallis交叉熵设置自适应阈值, 能更准确地对差分图像进行阈值分割, 克服了传统的最小Tsal-lis交叉熵法阈值化容易失效的问题, 然后利用形态学修正和差分交集技术获得精确的视频对象。高韬等［9］提出了一种基于离散冗余小波变换的立体视频对象分割算法。采用离散冗余小波变换提取特征点结合DT网格技术的视差估计方法, 获得了可靠的视差场, 再利用视差信息对立体视频中静止对象进行分割。对于立体视频序列中的运动对象, 采用离散冗余小波提取运动区域的方法进行分割。实验结果表明, 本算法对有重叠的多视频对象具有较好的分割效果, 可同时分割静止物体和运动物体, 具有较好的精确性和鲁棒性。孙季丰等［10］提出了一种基于视频分块处理的CRF视频分割算法。该算法利用像素空间相关性对原视频帧进行分块处理形成新视频帧, 然后使用CRF对新视频帧进行分割, 最后根据初始分割、前一帧分割结果和当前帧CRF分割结果实现最终的分割。实验结果表明, 在不明显增加误分割率的前提下, 文中算法能有效降低时间复杂度。
另外还有, 张晓宇等［11］针对光照变化较大时基于颜色差分直方图的视频分割算法不能有效更新背景, 导致后续输入图像前景目标分割失效的问题, 提出一种基于同态滤波抑制光照变化的视频分割算法。首先利用同态滤波算法对输入和背景图像 ( RGB) 在HSV空间中亮度分量进行同参矫正, 然后将矫正后图像转换到RGB空间, 最后利用颜色差分直方图算法进行视频分割。张洪超等［12］通过在视频空间建立跨时空域的相似性邻接关系, 提出一种新的视频分割图分割模型, 并且采用最大流/最小割算法对相应的模型进行快速求解, 从而实现视频的有效分割。该算法只需用户在视频的关键帧图像上进行少量交互, 便可自动获取整个视频分割结果。并且该分割过程不受前景对象遮挡、快速运动等情况的影响, 具有很好的稳定性。本文在已有工作的基础上, 首次将视频对象分割表述成约束条件下的MWC寻找问题, 然后提出了一种新的优化方法来实现视频对象的有效分割。
2 区域图构建
本文的目标是在不对目标建模的情况下, 对视频前景对象进行分割。由于我们没有对目标对象的尺寸、位置、形状和外观做出任何先验假设, 因此我们首先根据文献[9]为每幅帧生成多个对象“建议”。每条“建议”都是图像中的一个区域。对视频中的每个帧, 检索K个区域 ( 在本文所有实验中设置K = 300) , 对由N个帧组成的视频, 共有K × N个区域。目标就是发现在所有帧中都包含前景对象的一小组区域。构建一个加权图G = ( V, A) , 每个结点对应K × N区域中的一个区域, 且A是其邻接矩阵。结点u的权重A ( u, u) 表示区域u的“物质度”, 结点u和 υ 的权重A ( u, u) 表示两个区域的相似度。
采用文献[4]中的区域“物质度”计算方法, 对区域u有:
式 ( 1) 融合了静态帧内物质度分值sob ( u) 和动态帧间物质度分值mob ( u) 。它反映了区域包含一个通用对象的置信度。使用周围遮挡边界概率及周围像素颜色差异等静态特征来计算这一分值。
在文献[4]中, 引入了动态物质度mob ( u) 为视频静态分值提供补充。该指标可衡量区域u对应于视频中相干运动对象的置信度。在松散配置边界框内对区域u及周围像素计算光流柱状图。该分值的计算方法为:
式 ( 2) 中, 是L1- 归一化光流柱状图间的χ2- 距离。动态分值可以有效描述区域运动与最近邻区域的差别。使用分值在视频所有区域的分布对静态和动态分值做归一化处理。同时使用Lab颜色柱状图来描述各个区域。两个区域u和 υ 间的相似度的计算方法为:
式 ( 3) 中 χ2color ( u, υ) 是u和 υ 非归一化颜色柱状图的 χ2为距离, Ω 表示所有区域的 χ2为距离均值。因此, 如果两个区域的颜色或尺寸相似, 则它们的相似度就会很高。
3 区域间互斥约束
本文工作对视频分割领域的重要贡献之一就是引入了严格的互斥约束。该约束指明了哪些区域不能同时入选分割解, 从而可以避免区域的不合理配置; 由于一元位势A ( u, u) 和二元位势A ( u, u) 可靠性有限, 区域的不合理配置将会导致大规模联合位势。此外, 使用推理框架可以保证所求解满足所有的约束条件。互斥约束基于以下两个观点。
3. 1 帧内互斥约束
假设一个真正的对象应该会出现在每一幅帧中, 在每个帧中, 只有一个提议区域将被选择。然而, 对象可能被部分遮挡或自我遮挡。因此, 只为每帧选择一个候选对象区域, 对选择优质候选区域具有重要作用, 原因有两点: ①同一帧中的许多区域会出现重叠, 由于光照条件改变等帧间变化因素, 它们的相似度往往会远高于不同帧中的真实对象区域的相似度。因此, 相比于同一派系中混入同一帧的区域相似度, 来自不同帧的区域相似度更有意义。②由于我们保证过为每帧选择一个区域, 被选区域可以进一步用作先验位置。
3. 2 帧间邻近约束
同一对象在相邻帧上的位置变化应该是平滑的, 因此从两个相邻帧中选择的两个区域在空间上的距离不应太远。将这两个约束表述为一个二元互斥矩阵M, 该矩阵定义于图G的所有顶点上:
式 ( 4) 中, C ( u) 和C ( υ) 是两个区域的矩心, d是它们的像素欧几里德距离, τ 是u和 υ 间允许的最大空间位移。我们在所有实验中设置 τ = 100, 以为快速移动对象提供支持。
4 寻找约束条件下的MWC对象
本文将区域选择问题表述为约束条件下的最大权重派系问题。输入为一加权图G = ( V, A) , 其中V = { υ1, …, υn} 表示所有视频帧区域的一组结点, n是结点数量, A是所有元素非负的对称的n × n相似度矩阵, 对所有i, j = 1, …, n有Aij≥0。被选区域用指示向量X = ( x1, …, xn) ∈{ 0, 1}n标识, 对区域vi, 当且只当xi= 1 时才被选择。
对于图形顶点间的对称关系M ⊆ V × V, 将M称为互斥关系, 表示为二元矩阵M ∈ { 0, 1}n ×n。如果M ( i, j) = 1 , 则两个顶点i, j不得属于同一个最大派系。对所有顶点i有M ( i, i) = 0。一般地, 这一要求可被表示为施加于指示向量X ∈ { 0, 1}n上的一个约束: 如果M ( i, j) = 1, 则xi+ xj≤1。这一表述等同于要求XTMX = 0。对给定视频, 通过求解如下优化问题来获得主要对象区域:
使f ( x) = XTAX最大化
式 ( 5) 的目标是从图G中选择一组顶点, 使f最大化, 同时满足互斥约束条件。因为f是被选顶点集合的一元和二元相似度的和, 于是被选集合越大, f值越大。然而, 被选集合的规模受到互斥条件约束。问题 ( 5) 是个NP难解组合优化问题［13］。通过设置W = A - γM且 γ 足够大, 将问题 ( 5) 重新表述为如下对偶形式:
使XTWX = XTAX - γXTMX最大化
最后, 可以将式 ( 6) 松弛为:
使XTWX = XTAX - γXTMX最大化
第6 节将给出式 ( 7) 一种求解算法。在所有视频分割实验中, 均获得了满足所有互斥约束的离散解。
由于使用的最大派系搜索算法会收敛到局部最优, 因此需要多次初始化以提升性能。将图G中的区域根据各自一元分值A ( u, u) 进行排序, 获得排名最高的L个区域。我们每次从这L个区域中选择一个区域u来对最大派系搜索算法初始化。将初始状态表示为X ( 0) , 然后对所有i ≠ u设置 ( X ( 0) ) u=1, ( X ( 0) ) i= 0。从X ( 0) 开始, 用二元向量X*表示已经获得的一个最大派系。X*是满足X* TMX*= 0条件的XTAX的一个局部最大化因子。
因此, 将总共获得L个最大派系, 并根据XTAX选择一个最优。可以发现, 被选区域是这一解的指示向量的元素。因为这一解满足第3 节定义的约束条件M, 于是只从每一帧中选择一个区域, 并保证相邻帧中选择的每两个区域相对比较接近。这些区域反映了每个帧中对象的基本外貌和位置。
5 前景对象分割
视频对象以被选区域形式获得的分割效果并不十分准确。尤其地, 分割误差容易受到候选对象区域的下界约束［6］。出现误差可能是因为初始的超级像素提取或融合不够精确。因此, 本文采取如下策略: 利用被选区域为前景和背景展开外观模型学习。此外, 我们也利用了先验位置信息。在本算法中这一点较为简单, 因为每一帧只有一个对象区域。最后, 本文使用GrabCut［14］算法得出更加准确的像素级对象分割方法。出于效率考虑, 本文没有像文献[4]那样构建空间-时间图, 一次性为三幅连续帧对像素进行标记, 而仅是单独地为每幅帧运行Grab-Cut算法。这在本文中是完全可能的, 因为在下文定义的基于约束条件下MWC获得的数据项, 带有大量重要信息。
将每帧中的像素表示为S = { p1, …, pn} , 各自标记为f = { f1, …, fn} , fi∈ { 0, 1} 且前景时为1, 背景时为0。此时, 极小化能量函数为:
式 ( 8) 中, N由8 个空间相邻的像素组成。对于平滑项V, 使用文献[14]中定义的对比度独立函数, 该函数倾向于为颜色类似的相邻像素分配相同的标记。与文献[4]类似, 本文的数据项Di ( fi) 用标签fi定义了标记像素pi的成本:
式 ( 9) 中Pic ( fi) 是根据外表 ( 颜色) 特征用标签fi定义标记像素pi的概率, Pli ( fi) 是基于先验位置的概率。
为了计算Pic ( fi) , 首先估计RGB颜色空间两个高斯混合模型 ( GMM) , 以对前景和后景外观建模。因为颜色在视频帧中差异太大, 因此需要在所有视频帧上对模型展开学习。前景GMM模型fgcolor根据约束条件下的MWC计算所选择的区域内的像素进行学习。后景GMM模型bgcolor根据所有帧被选区域的补充区域内的像素展开学习。然后根据这两个颜色分布fgcolor和bgcolor, 对每个像素pi定义:
对于位置概率Pli ( fi) 的计算, 利用约束条件下MWC选择的对象区域。给定被选区域后 ( 每个帧, 我们只有一个区域) , 首先计算它的距离变换。设d ( pi) 表示像素pi与被选对象区域的距离。计算:
式 ( 11) 中, σ 表示先验位置的置信度; σ 越大, 置信度越低。另外还需计算Pic ( fi) ·Pli ( fi) 作为前景 ( fi= 1 ) 和后景 ( fi= 0 ) 的概率。在获得数据项D和平滑项V后, 使用文献[3]中的常见方法来确定可以实现式 ( 8) 能量函数最小化的最优f, 进而求得每幅视频帧中的最终前景对象。
6 算法描述
本节将给出一种新的约束条件下MWC确定算法。f ( x) = XTWX表示式 ( 7) 中的目标函数。本算法需访问一组连续点{ y ( k) ∈ [0, 1]n} ( k = 1, 2, …) 。每次迭代k, 文中分两个步骤。首先, 给定y ( k) , 对其任意相邻点y ∈[0, 1]n, 计算f ( y) 的一阶泰勒近似:
式 ( 12) 中的二阶f ( y ( k) ) 不依赖于y, 因此f ( y) 的一阶泰勒近似只依赖于yWy ( k) , 且yWy ( k) 是y的线性函数。这一特点使得式 ( 13) 中的离散最大化因子可以根据式 ( 14) 计算得到:
在第k次迭代的第二步, 需要验证求得的X (k) 能否作为可以使f变大的合法离散解。如果当通过线搜索, 在至y (k) 的线段上实现一维函数最大化, 以此来在连续域上估计f的局部最大化因子。可以看出, h (α) 在式 (15) 中定义的α处达到最大值。同时可以看出, 0<α<1, 这可以保证线搜索不会超出立方体范围。
然后, 本文设置如果对向量X*= y ( k + 1) 的所有坐标i均满足以下停止条件, 则本算法终止:
可以观察到, 因此, (WX*) i>0表示f的上升方向与第i个坐标的方向相同, (WX*) i<0表示方向相反。根据停止条件可知, f (X*) 在f的每种上升方向上均达到了可能的最大值。假设初始分配值y (0) 满足互斥约束, 即y (0) TMy (0) =0。因为A的所有元素非负, 所以这表明f (y (0) ) ≥0。本文算法总结于如下伪代码中:
7 实验结果
本文首先在SegTrack数据库［15］上评估本文算法。该数据库总共包含了6 个视频 ( 猴子与狗, 小鸟, 女孩, 降落中的小鸟, 跳伞者, 企鹅) 。由于这些视频的主要对象存在较大规模的变形, 而且前景和后景存在重叠, 因此对象分割难度较大。与文献[4]相同, 本文没有在企鹅视频上评估算法, 原因是一组企鹅中只有一个企鹅被识别为前景对象。
给定一个视频后, 首先根据文献[6]为每个帧生成300 个对象候选区域。本文使用Lab空间柱状图来描述每个区域的颜色。每个Lab信道有20 个接收器 ( bin) 。对前景和后景颜色模型, 我们使用RGB颜色空间, 对两个5 成分GMM进行学习, 另外, 本文采用光流柱状图来描述运动, 每x和y方向上有60 个接收器。在计算背景柱状图时, 区域边界盒扩充30 个像素大小。为对最大派系计算初始化, 每次根据A ( u, u) = ob ( u) 从最优的50 个对象区域中选择候选对象。计算Pli ( fi) 时设置 σ = 20。对本文所有实验的图像切割能量函数, 设 δ = 1。由于本文约束条件下MWC算法的高效性, 计算机配置3. 4 GHz、8 GB RAM, 算法在50 个不同初始状态下基于约束条件MWC选择区域只耗时2 min。单帧二元图像切割平均耗时约0. 1 s。
将实验结果与文献[4, 15, 16]中的三种最新算法做比较。文献[4]中的算法与本文算法均是无监督算法。它们可以自动发现图像中的主要对象, 并且自动分割出来。文献[15, 16]中的算法需要一定的人工监督, 在第一帧中需要人工标出对象。表1给出了实验结果。对5 种测试视频, 本文每帧分割平均误差最低。5 个视频中, 本文算法在3 个视频上的分割误差最小。文献[4]与本文算法一样, 对象初始化均不需手工进行, 但是与该算法相比, 本文算法在4 个视频上的实验结果更优。部分分割结果见图1。
表1 给出了相对真实分割结果计算而得的平均每帧像素误差率。具体计算方法与文献[4]相同:
式 ( 17) 中, f是给定视频每个像素的标签, GT是真实数据标签, F是给定视频的帧的总数量。由于所有视频的大小基本相同, 5 个视频的平均误差率计算为所有视频所有帧的平均值, 也就是说, 将5 个视频看成是一个视频然后再应用式 ( 17) 。
如上文所述, 即使没有第5 节描述的基于像素的对象分割, 基于第4 节约束条件下MWC所选择的对象区域也可以作为分割结果。在表2 中, 我们给出了约束条件下MWC区域分割结果的像素误差, 该误差受到文献[9]生成的候选区域准确度下限约束。下限误差计算为候选区域相对真实像素的最低误差。它反映了我们基于约束条件下MWC计算而进行区域选择所能获得的最低分割像素误差。
从图1 可以看出, 对降落的小鸟和猴子小狗视频, 只使用约束条件下MWC获得的区域可以取得非常理想的效果。此外, 除了印度豹外, 像素误差与误差下限非常接近。这表明, 本文提出的约束条件下MWC区域选择算法为视频分割提供了一种强大的工具。
如表3 所示, 如果可以表示时间/空间相干特性的帧间邻近互斥约束没有作为约束条件下MWC优化问题的输入, 则分割误差会有显著上升。本文也在图2 中, 直观阐述了这些互斥约束的重要性。本文在有互斥约束和没有互斥约束两种情况, 对约束条件下MWC区域的矩心轨迹做了对比。矩心重叠显示于第一个视频帧上。从图2 可以看出, 有约束时, 矩心的轨迹非常平滑, 被选区域总是聚集于主要对象, 也就是视频样例里的猴子上。这表明, 互斥约束明显提高了约束条件下MWC优化问题的鲁棒性, 使得我们可以去除来自低可靠性相似关系的不合理的区域选择假设, 因此对选择正确的对象区域具有重要作用。
本文也基于文献[3]中的Yu-Na Kim和Waters-ki两个视频对本文算法进行评估。文献[3]通过动态和外观特性来标识图像中的每个像素, 而本文算法在每帧中可以实现主要对象 ( 即溜冰者和滑水者) 识别和分割的自动化。定性结果见图3。
(白点与黑线相连, 覆盖于第一帧图像上)
8 结束语
区域分割法 篇5
(1)课题背景和研究意义
在城市交通压力日益增加的今天,驾驶辅助系统已然成为消费者们新的关注点。作为当今汽车制造商们都将其列为汽车驾驶辅助系统中的一大功能,实现道路交通标志的检测和识别,以辅助驾驶员在行驶过程中随时意识到当前的路况和法规。
作为全球各大智能汽车驾驶辅助系统开发商的不约而同的开发重点,交通标志识别是其中一大功能,这关乎新一代智能汽车的行车舒适性和安全性。本课题研究的问题的提出本身具有实现的价值,同时也是基于已有的可用的硬件系统,具有可产品化的潜质。据2012年的一份关于智能驾驶辅助系统中基于视觉的交通标志检测和分析的调查研究[1],Mobil Eye公司专注于协助驾驶员在驾驶过程中保障乘客安全和减少交通事故的视觉系统。作为公认的开发高级驾驶辅助系统的先行者,Mobil Eye提供芯片搭载系统和计算机视觉算法,也提供Eye Q和Eye Q2视觉处理器,允许其他的Tier1合作汽车零部件供应商可以在一个视觉处理器平台上集成多个基于计算机视觉的应用,还可包括车道偏离警告、前方碰撞预警和前方交通标志提示功能等。从而使集成产品更具商业优势。
交通标志检测和识别利用车载摄像机实时摄取道路前景图像,通过数字图像预处理和图像分割,提取出有用交通标志区域;再在感兴趣区域内进行特征提取,然后在已知的图像库中搜索来实现“识别”具体标志。
(2)本文的研究方向和主要工作
本论文的目标为寻找一个图像处理算法,实现实时的中国大陆地区的交通道路标志识别。方案应具有一定的灵活性以适应后期产品化过程中硬件的选择和不同客户需求的实现。算法主要关注快速图像分割和形状特征提取的方法、以及简而有效的基于内容的交通标志库图像检索的实现,以此来验证前述方法的有效性。最终以提供一个快速有效的综合方案。为今后以此为方向的驾驶辅助系统的研究开发工作探索继续前进的方向。
1 图像分割和形状识别
彩色图像分割是按照彩色图像的色彩规则将一幅图像分成若干个部分,将图像中有意义的特征区域提取出来。道路两旁复杂的环境(如树木、霓虹灯、特殊建筑墙体有近似颜色的、楼顶上的立体广告文字等)等众多因素使交通标志影像的背景表现及其复杂,使交通标志区域与周围环境极易混淆,从而从复杂路况背景下高效分离出有效交通标志信息是本文后续研究的基础和关键。
1.1 基于底层视觉特征的图像分割方法研究
图像分割的方法有很多,参见文献[2-7]。但又要快速又要准确地应用到交通标志检测中,仍很不理想。譬如使用边缘检测的方法,由于实际环境背景的复杂性,即使是经过了平滑处理,也不能直观地观察到太多完整的线条。因而本文针对色度和饱和度的处理提出了基于颜色直方图统计特征的快速区域分割。HSI颜色模型将图像的彩色信息和亮度信息分离开,它由三个分量组成,Hue色度(H)、Saturation饱和度(S)和Intensity亮度(I)。在HSI颜色模型中,彩色特征阈值分割针对H一个分量来处理,就能达到不错的效果。色度(H)空间是一个以红色轴为0°轴的圆盘平面,其他彩色表示为以此轴按逆时针方向旋转一定的角度到达该彩色点的位置,这个角度定义为色度值,范围为0°~360°。
1.2 新型的基于颜色直方图的区域快速分割法
根据颜色特征和处理速度问题,将原图像960×1 280按简单规横纵切割,分成N×N=10×10或20×20的小块图像,在每个小块区域内,通过颜色的区域统计特征来决定该区域是否含有有用信息。小块的具体尺寸应视实际摄像机聚焦的远近距离和希望检测的最小交通标志的大小(远近景)和原始图像的精度来确定。N不宜取太大,否则也会产生过度分割使感兴趣区域形状不规则;而N太小的话,起不到去除足够多的背景的作用。
1)区域色度特征直方图统计特征
将色度平面(0°~360°)均为划分为12个区间,并依次标号为第1~12个色度级(例:色度范围0°~30°属于色度级1)。根据实验数据库图标的全统计,可以发现各类标志的主要色度值范围和统计频数特征统计如表1所示。表中最后一行标记为图库统计的色度级,基于H分量的直方图色度级频数特征。12个色度分级足以较好地区分各不同色调,且分级相对较宽的优点还在于对因风吹雨淋导致标志牌的褪色程度的容忍性。
按照方法,本研究中将原始图像按横纵方向切割成20×20小块,计算对应每个块区域的H直方图进行统计。统计颜色特征为上表中绿色和蓝色作为标志牌上的主要背景色,其色度直方图中相应色度级(6,8)也脱颖而出;而禁令标志中只有边缘红圈部分,红色面积较小。根据以下条件可较高快速地找到标志所在的块区域,如图1所示。
根据以上统计,可以设定以下满足任一条件以判断该小块区域中是否可能含有交通标志:
(1)统计该块区域中黄色、绿色和蓝色对应的色度级像素点(1.a)频数为最大或(1.b)频数≥各级频数平均值+2倍标准差;(概率统计分布参数评估)
(2)统计该块区域中红色对应的色度级(色度级11与12的频数和)(2.a)频数为最大或(2.b)频数≥各级频数平均值。
以上图例中几乎所有标志牌区域都在第四列的初步分割后效果图中完整地被保留下来,除了白色标志区域被漏检,还部分包含了下方前车轮廓和周围树木背景,及高速路远景中景物和标志牌周围的部分树木等,但只有局部小块区域。
2)区域饱和度特征直方图统计
根据交通标志饱和度高的特点,特别可以用于区别实际环境中背景中低饱和度的景物排除。根据实际采样图像统计,区域中如果没有交通标志,各像素点的饱和度总和平均较低。根据统计,可以设定满足以下条件1)以判断该小块区域中是否可能含有交通标志,否则为背景:
统计该块区域中饱和度级为1,2,3(同Hue分量一样,将饱和度分量的度量分为12个等级,而不是256以节省计算开销)的频数和≥Tb;Tb=0.9~0.98。
所有N×N区域被标记为0为背景,1表示可能有交通标志。Tb的值越大直接滤出的背景越少;但Tb越小可以使背景更大程度地被剔除。但同上节1色度直方图特征,标志内部白色的部分仍易被错误检测为背景而产生空洞。如图2所示。
3)区域综合评价分割
综合以上两个Hue分量和Saturation分量的块区域直方图统计特征可以分别被记录下来,分别为颜色特征矩阵A_Feat_Hue_block,A_Feat_Sat_block,尺寸为N×N=20×20。
综合两个区域特征矩阵可以改善以下几种误检测:
(1)针对禁令标志的红圈在饱和度S分量中不突出的问题(有可能被误判为背景),通过判断相应色度特征值≥30,则同时设置饱和度特征为1。
(2)针对背景中树木或广告牌或立体广告文字等饱和度较高、但使用不同于本课题中关注的四种色调的物体,通过判断该块区域色度特征值等于零,则同时饱和度特征清零。
(3)针对背景中树叶颜色近似交通标志所用绿色、但因生长于道路边常有积灰等原因而饱和度值较低(<0.25)的背景物体,通过判断该块饱和度特征等于零,则同时清块色度特征值为零。
1.3 使用分层技术的感兴趣区域的细分割和使用形态学的形状识别
由于基于感兴趣区域的图像检索考虑得较多的是感兴趣目标的整体特征,而不仅仅是轮廓。因此采用的是区域技术而非边界技术。而在上节基于Hue和Saturation分量区域统计分割后,实行以下算法步骤:(1)进一步对Hue采用颜色分层技术。对标志颜色分别归纳到一个色度值;(2)这样在对重新标色后的H分量图上用阈值方法再次分割,得到更接近交通标志本身形状的感兴趣区域,而不是前步中生硬的方块;(3)结合数学形态学的膨胀运算可以针对4个颜色层图像充盈成具有平滑边界的感兴趣区域,此方法可保证最终得到的感兴趣区域包含标志边界,输出如图3所示;(4)基于此区域边界可一一地计算区域分散度(又称紧凑度即周长平方比面积P2/A,具体定义参见文献[8])特征来识别区域形状或直接丢弃过小的背景不规则形状区域。此分散度属性除了可以用来识别形状还可以排除部分前阶段中检测到的非交通标志的物体,如前车尾部上方的灯条等带状物等。
以上算法完成对当前图像的交通标志检测问题:(1)有无交通标志;(2)几个交通标志;(3)相应的标志形状。
本文使用的形态学的方法进行形状识别,可识别的目标形状对象如图4所示。
对应形状边界标记后输出给下一步检索用。输出的边界描述为{Bk,Lk,Ck,Sk},其中k=1,2,3,…用来标记检测到的交通标志区域数;Bk是对应的标志边界链码描述;Lk为经过填充后的标志区域,尺寸同原始图像960×1 280;Ck为对应标志区域的主要色调特征;Sk为形状描述。
以上结合应用数学形态学的方法,采用自下而上(bottomup)的方法,去除了位置和大小的不确定性,消除噪声造成的标志边界断裂,也使最终区域包含边界,可去除无用的形状物体,大大地节省了计算开销。结合实现边数的提取,可以成功解决检测矩形长宽比值及长条箭头形的五边形,将指路标志中这一类相关标志再细分出来。
2 图像交通标志库检索
基于内容的图像检索(Content-Based Image Retrieval)的基本思路[9]是:先通过对图像内容的分析,自动或半自动的从中抽取形状、颜色、纹理等特征,并利用基于这些特征定义的相似性度量函数计算或评价特征之间的相似性,将最相似的一些图像作为检索结果返回给用户。由于本文的研究对象很明确,为标准定义的中国大陆交通标志,而数据图库也为标准标志图,检索本身的工作并不复杂。这里对相似性量度的精度要求不是很高。
2.1 基于颜色与形状先分类
根据输出的边界描述特征对{Ck,Sk},可将检测到的交通标志先分类到红色禁令、红色指示(矩形标志),黄色警告、黄色警示(需补充数据图库),蓝色限速、蓝色指示(矩形标志),还是绿色指路标志类中。本文中所用交通标志图库目前有251个标志,按颜色分四类,每一类中按形状可再分子类。这样可以按线性倍数比例减少检索的计算开销。
2.2 基于边缘方向特征的标志库检索
使用{Bk,Lk}位置信息,将内部填充后的Lk生成区域掩码,用以在平滑滤波后的Intensity分量图像中定位交通标志,对Lk对应的标志图像提取边缘方向特征Hdir。轮廓的方向性计算参见文献[10]。
根据交通标志轮廓特征分析,可以将θ平面角度范围[-90°,90°]离散化为9个均匀的方向区间。将各像素处方向梯度对应到这9个区间构造方向直方图Hdir并且归一化,此特征具有尺度不变性和一定的旋转不变性。下一步基于内容的图像检索是要根据边缘方向特征作为图像索引计算特征相似度欧氏距离来检索所需的图像。对前章中输出的交通标志区域按分类结果与标志库中同类标志图(若此类图库个数为M251)计算M个边缘方向特征的欧氏距离。将此M个欧氏距离值按升序排列。将前三个最小欧式距离值对应的库中标志图按顺序显示给用户。
3 结束语
初步实验结果,以上基于颜色区域分割的方法对感兴趣区域的检测准确率在90%以上,形状的边界通过形态学处理后也易于通过形状属性识别。此可以扩展到大部分目前标志数据图库中涉及的绝大部分标志使用形状。
本文的算法的缺陷还在于,对白色标志检测的缺失,这将是未来工作的首要解决问题。
本文算法可期对于具有交通标志检测和识别功能的驾驶辅助系统的产品化提供一个理论基础,基于目前已做的工作,还需根据市场完善使用的标志库,并将其按颜色、形状进行细分类,对提高检测率也是至关重要的。
摘要：现在的高端汽车市场上汽车驾驶辅助摄像系统是一大亮点,研究工作致力于提供一个软件算法来实现驾驶辅助系统中实时交通标志检测和识别的功能。算法的每一步设计都尽量不影响其实时性,基于HSI颜色空间,使用了新型的基于区域的快速颜色分割,结合分层技术和简单阈值处理,可以快速地按颜色分层得到采样图像中可能含有标志的感兴趣区域;再在此区域结合数学形态学的膨胀运算以便识别区域形状。最终基于最后输出的感兴趣区域掩模原图像的亮度分量,用边缘方法提取边缘方向的统计特征,进行基于内容的图像检索(CBIR)。初步实验结果,对感兴趣区域的检测准确率在90%以上。并且算法可以扩展到大部分目前标志数据图库中涉及的绝大部分标志使用形状。
关键词：交通标志检测和识别,基于区域的图像分割,颜色直方图,HSI颜色空间,数学形态学,形状识别,基于内容的图像检索(CBIR)
参考文献
[1]A MOELMOSE M M,TRIVEDI.Vision based traffic sign detection and analysis for intelligent driver assistance systems:perspectives and survey[J].IEEE Trans.on Intelligent Transportation Systems,2012,13(4):1484-1497.
[2]徐迪红.复杂背景下的交通标志检测和分类算法研究[D].武汉:武汉大学,2011.
[3]李红林.基于HSV颜色空间的山区道路中的车牌定位[J].计算机时代,2012,30(3):22-24.
[4]FU KEREN.Automatic traffic sign recognition based on saliencyenhanced features and SVMs from incrementally built dataset[C].Vienna:IEEE ICCVE2014,2015.
[5]杨杰,黄朝兵.数字图像处理及MATLAB实现[M].北京:电子工业出版社,2011.
[6]NICOLAE DUTA.Learning-based detection,segmentation and matching of objects[D].USA:Michigan State University,2000.
[7]LIU H,LIU D,XIN J.Real-time recognition of road traffic sign in motion image based on genetic algorithm[C].Beijing:Proceedings of the First International Conference on Machine Learning and Cybernetics,2002,11:83–86.
[8]JESMIN F KHAN,SHARIF M A,BHUIYAN REZA R.Adhami.image segmentation and shape analysis for road-sign detection[J].IEEE Trans.on Intelligent Transportation Systems,2011,12(1):1-14.
[9]张华伟,孙劲光.基于颜色与形状图像检索的研究[J].计算机仿真,2009,26(11):207-210.
区域分割法 篇6
从序列化数据集中提取肝脏管道信息, 是CASP系统成功的基本前提。通常一次腹部扫描大约有200~400张图片, 采用传统区域生长法进行图像分割时, 种子点采样是基于外科医生的辅助通过人工选取完成的, 工作量大, 效率低, 很难应用于临床医学。因此, 研究肝脏血管管道的自动和半自动提取技术尤为重要。
1 区域生长法概述
在诸多图像分割算法中, 区域生长法有着简洁、有效的特点。由于肝脏血管图像的连通性、血泡的封闭性以及序列化切片的相关性, 使得基于区域生长的算法适用于血管分割。
区域生长的主导思想是基于一定约束条件, 将具有相似性质的像素点集合起来构成一个区域。首先, 为需要分割的区域选取一个种子点像素作为生长起点, 然后将种子点像素领域中符合生长规则的像素合并到种子点像素的集合中。持续上述过程, 直到没有符合约束条件的像素点可以被包含进来。其中, 约束条件的均匀性判断准则一般基于公式 (1) :
其中:I表示的是当前像素的灰度值;Iseed表示的是选取种子点的灰度值;Imax和Imin分别表示的是图像区域中最大灰度值以及最小灰度值;λ则是人工可调节参数, 用于控制像素之间的均匀性相似度门限, 并将符合上述要求的邻近像素集合增加到种子区域中。
2 改进区域生长算法
区域生长法作为一个典型的串行区域分割方式, 特点是处理过程包含多个步骤, 且后续步骤的执行要依据前期步骤结果的判定。影响区域生长法结果的因素主要有: (1) 初始生长种子点的选取; (2) 区域生长准则; (3) 终止条件。初始生长种子点的选取作为区域生长法的第一步, 也是最关键的一步, 较大程度上影响着后续步骤的执行结果。然而, 传统的区域生长法都是基于人工手动选取种子点的方式, 依赖于人体视觉的判断, 而一些肝脏序列图像的视觉效果十分不明显。因此, 初始种子点的选取成为提高区域生长法有效性和鲁棒性的重中之重。
肝脏门静脉系与肝静脉系管径具有较粗、易于识别的特点, 且门静脉左、右支走行比较恒定[2]。门脉三联管中门静脉管径最粗、变异最少。本文充分利用肝脏管道骨架线的居中性、连通性、鲁棒性的特点[3], 利用三维重建后的肝脏管道骨架线函数作为初始种子点的预判位置, 较好地实现了初始种子点的半自动选择, 提高了序列图像自动分割的效率, 得到了较为准确的分割结果。
2.1 肝脏管道骨架化
2.1.1 骨架点的由来
目前已有大部分学者对肝脏管道建模[4,5]展开了较为深入的分析与研究, 基于肝脏管道的三维重建技术较为成熟。在前人的基础上, 本文采用肝脏管道的三维骨架点进行实验, 骨架点的获取采用基于广义势场的三维骨架提取方法[6]。该方法通过构建斥力场源计算三维势场值和检测矢量场的关键点, 跟踪关键点获取骨架点的三维坐标。
设置三维空间直角坐标系O1-X1Y1 Z1, 将肝脏管道骨架点置于坐标系O1-X1Y1 Z1中, 得到骨架点三维空间坐标集{ (xi, yi, zi) │i=0, 1, …, n}。本文以我国标准可视化人体肝脏数据集作为信息采集来源, 采用基于广义势场的骨架提取方法, 得到肝脏管道骨架点种子坐标集合, 并以此坐标集作为后续预判其他序列图片种子点数目和位置的基准。本文实验骨架线有29条分支, 由于肝脏管道结构复杂, 每条分支弯曲形态和长度不同, 因此每条分支的骨架点数目也不相同。表1为本文管道骨架点坐标集示例 (同一列的3行数据是一个骨架点的x、y、z轴方向坐标) 。
2.1.2 骨架点拟合
肝脏管道是一个弯曲的空间管状系统, 其骨架线是三维连续的光滑曲线。曲线拟合是构建血管管道的前提和基础, 有逼近与插值两种方法。由于离散三维骨架点数目较多, 且对三维骨架线的提取也存在一定误差, 因此, 本文采用逼近方法对上述离散三维骨架点进行B样条曲线拟合。
B样条曲线[7]的方程定义为:
其中, Pi (i=0, 1, ..., n) 是控制多边形的顶点, Ni, k (t) (i=0, 1, ..., n) 称为k阶 (k-1次) B样条基函数, 其中每一个都称为B样条, 它是一个由称为节点矢量的非递减的参数t的序列T:t0≤t1≤…≤tn+k所决定的k阶分段多项式, 也即为k阶 (k-1次) 多项式样条。
公式 (2) 中Ni, k (t) 称为B样条基函数, 又称为de Boor-Cox公式, 其递推公式如下:
该递推公式表明:欲确定第i个k阶B样条Ni, k (t) , 需要用到ti, ti+1, …, ti+k共k+1个节点, 称区间[ti, ti+1]为Ni, k (t) 的支撑区间。曲线方程中, n+1个控制顶点Pi (i=0, 1, ..., n) 要用到n+1个k阶B样条基Ni, k (t) 。支撑区间的并集定义出这一组所有B样条基的节点矢量T=[t0, t1, …, tn+k]。
在使用时, 为了更多地减少计算量, 曲线的次数越低越好, 但是二次曲线是一条抛物线, 不能反应出曲线的拐点。本文采用3次 (4阶) B样条曲线作基元, 选取控制顶点数为28来实现三维骨架点集的拟合:
(1) 型值点:选取三维血管树骨架点集中n+1个数据点, 将获取数据点集合A={ai;i=0, 1, …, n}作为拟合B样条曲线的输入型值点。
(2) 控制点:由公式 (2) 知:
这里A=[a0 a1...an]T, P=[p0 p1...pm]T, N是结构为n×m的B样条基矩阵。已知输入点集A和B样条基矩阵N, 依据公式 (4) 可得上述线性方程组的控制点近似解集:
根据给定的控制顶点P={pi|i=0, 1, …, m}, 次数k=3, 可以定义一条k (3) 次B样条曲线。将参数t的区间[0, 1]划分为n份, 在曲线上取n个点, 并计算出每个参数t的取值;利用公式 (3) 求解出每个参数t对应的B样条基函数, 将该值返回给公式 (2) , 从而得出全部的控制顶点。依据全部控制顶点即可拟合出所求3次B样条曲线函数, 这样便可以得到基于B样条曲线的肝脏管道骨架三维结构曲线Pv (t) 。肝脏门静脉三维骨架点拟合结果图, 见图1, 其中图 (a) 为骨架点可视化结果图, 图 (b) 为骨架点拟合结果图。
2.2 种子点预判断
2.2.1 坐标系映射
2.2.2 种子点位置预测
肝脏序列图像是两两间距很小的二维切片, 以“层”为单位进行信息采集, 并通过二维切片来传递三维信息。因此, 如何获取序列图像单张肝脏血管的种子点位置成为关键。
在2.1.1小节中采样标准图片集张数为N1, 层片厚度信息为h1, 由公式 (1) 知, 两坐标系尺度转换参数如下式所示:
肝脏管道三维空间曲线函数f (x, y, z) =Pv (t) 。已知z轴坐标信息, 可求得对应点x轴与y轴坐标信息集合Pi:
2.3 区域生长
在上一小节的基础上, 初始化生长种子点位置信息, 基于公式 (1) 原则进行区域生长, 得到肝脏管道分割结果。
3 本文算法思路
(1) 获取读入图像信息, 包括序列图像张数N2与层片厚度信息h2, 由公式 (6) 计算出尺度转换参数δμ, 置于坐标系O2-X2Y2 Z2中。
(3) 利用本文算法计算出第n张数据集层片中肝脏管道预测位置的集合P, 进行区域生长, 得到该层片的分割结果, 利用相应的数据结构对本结果进行保存, 记为点集A。
(4) 判断所有切片是否已分割结束, 是则结束本过程, 否则返回步骤 (3) 。
(5) 算法流程图见图2。
4 实验结果与分析
利用Visual Studio 2010和Open CV在PC机上实现上述算法, 本文实验处理采用肝脏数据集来源于网站http://www.dicom7.com/。
首先, 设置Bursa模型初始值参数。实验采用一幅完整肝脏数据集序列图片, 序号为:DRC10C001454~DRC10C001641, 共188张切片图。依据数据集信息[8,9]知, 每层切片厚度信息为:0.33 mm。x、y、z轴平移参数均为0。由于获取预判种子空间坐标y轴表示竖直方向, 因此, 这里设置旋转参数:εx=0°, εy=90°, εz=90°。
初始化参数设置结束, 分别抽取3张不连续肝脏图像进行分割, 处理结果如图3~5所示。各图中图 (a) 为预判图像种子点结果, 图 (b) 为肝脏图像平滑处理后结果, 图 (c) 为基于预判种子点的肝脏血管管道分割结果, 图 (d) 为基于人工选取种子点的肝脏血管管道分割结果 (白色部分表示为血管) 。
实验中通过预先设置参数, 读取切片之后可直接进行分割, 体现了本算法的自动性。由于预判种子点的数目和位置都是自动生成的, 因此, 很大程度上减少了人工参与, 在效率上也有显著的提高。
结果显示, 图3中, 本算法预判断9个种子点, 分割结果为7个区域, 人工辅助选取分割结果为12个区域;图4中, 本文算法预判断12个种子点, 分割结果为10个区域, 人工辅助选取分割结果为20个区域;图5中, 本文算法预判断7个种子点, 分割结果为4个区域, 人工辅助选取分割结果为7个区域。各图 (a) 部分显示, 预判种子点坐标的排序是基于y坐标的递增来实现的。
分析各图中图 (a) 和图 (c) , 一般情况下, 基于本算法的分割结果区域数量都少于预判种子点数目, 这是由于肝脏管道分支个性化的差异, 预判断的一些种子点位置处并没有可分割的区域;分析各图中图 (c) 和图 (d) , 可以看出, 与人工辅助选取分割结果相比, 本算法可较好地分割出管道半径较粗的部分, 基于人工辅助选取的种子点十分完整、全面, 因此本算法对管道半径较细部分的预判仍有待改进。在外科手术中, 为了防止病人失血过多, 医生更多地是对病人较粗血管位置的把握。因此, 基于本算法的分割方法对外科医生术前的手术仿真具有良好的指导作用。
5 结论
针对医学图像分割过程中, 需要外科医生辅助选取种子点而导致工作量极大的问题, 本文给出了一种半自动的肝脏血管管道图像分割方法。该方法利用了肝脏血管骨架线具有代表性的特点, 利用矩阵映射来预判序列图像的种子点数目和位置, 避免了人工参与, 大大缩短了图像的分割时间, 具有良好的分割效果。与传统的人工选取种子点方法相比, 本方法可较好地实现对管道半径较粗部分的分割, 但对于半径较小血管的分割仍需改进。未来工作可以考虑对标准数据集中半径较小的血管进行骨架化处理, 获取更完整的肝脏管道骨架信息, 优化半径较小管道的分割方法, 进一步改善对序列图像整体的分割效果。
参考文献
[1]Lamade W, Glombitza G, Fischer L, et al.The impact of 3-dimensional reconstructions on operation planning in liver surgery[J].Arch Surg, 2000, 135 (11) :1256-1261.
[2]李恺, 张绍祥, 刘正津, 等.可视化肝脏横断面解剖与MR影像对照研究[J].中国医学影像技术, 2005, 21 (1) :138-141.
[3]王昌.高精度肺部气道树的分割及骨架中心线的提取[D].合肥:中国科学技术大学, 2010:37-40.
[4]晁凡, 沈若武, 张景利, 等.肝和肝血管三维重建的临床应用[J].中国当代医药, 2013, 20 (23) :4-6.
[5]Cornea ND, Silver D, Min P.Curve-skeleton properties, applications, and algorithms[J].Visualization and Computer Graphics, IEEE Transactions on, 2007, 13 (3) :530-548.
[6]Chuang JH, Tsai CH, Ko MC.Skeletonisation of threedimensional object using generalized potential field[J].Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2000, 22 (11) :1241-1251.
[7]孙家广, 胡事民.计算机图形学基础教程[M].北京:清华大学出版社, 2005.
[8]唐雷, 原林, 黄文华, 等."虚拟中国人" (VCH) 数据采集技术研究[J].中国临床解剖学杂志, 2002, 20 (5) :324-326.
区域分割法 篇7
关键词：沥青混合料,数字图像,图像分割,区域生长
1 概述
图像分割就是指根据图像中像素的特性, 如灰度、颜色、纹理等, 把图像分成各具特性的区域并提取出感兴趣目标的技术和过程[1]。图像分割是图像处理成图分析的关键步骤, 在沥青混合料的数字图像处理过程中占据一个重要的位置。一方面, 它对骨料颗粒的特征测量影响特别重要, 是明晰表达目标的基础;另一方面, 图像分割通过对图像进行抽象表达, 对图像中感兴趣的目标进行表述, 提取目标特征, 对目标参数进行测量, 从而将原始图像转化为更为抽象、紧凑的数字表达形式, 这使得研究人员能够对图像进行更高层的分析以及理解。针对沥青混合料二维数字图像, 图像分割的主要目的是将粒径较大 (通常指粒径大于2.36 mm) 的粗骨料颗粒分离, 也就是以骨料颗粒为目标, 从沥青砂浆的背景中将其提取出来, 然后判断颗粒大小, 将骨料分割为粗骨料和细骨料, 在此基础上进一步分析需要的骨料面积级配、粒度分布、形状参数等。
图像中, 在不同区域的边界上的灰度正常都是不连续的, 区域的边界主要是因为灰度的阶跃变化, 利用这一特征, 可以寻找相邻像素颜色或灰度突变的算法, 利用灰度值的不连续以及相似特征对像素点进行分割。通常来说, 分割处理大致可以采用四种不同的原理来实现。。
1) 阈值分割方法。以自动或手动指定的阈值为界, 将物体目标与背景分离。
2) 基于区域的分割。把具有相似特性、特征的像素点划分提取到一起, 形成需要的物体或者区域。
3) 基于形态学的分割方法。用具有一定形态的结构元素去度量和提取图像中的对应形状以达到对图像分析的目的。
4) 边缘检测法。通过确定的边缘像素, 将具有相似特征的像素点连接到一起, 构成所需的边界[2]。
本文主要介绍基于区域的生长方法在沥青混合料数字图像处理中的应用。
2 采用基于区域的方法进行沥青混合料图像分割
典型的两种串行区域分割技术, 分裂合并以及区域生长, 它们将全处理过程进行多步骤分解, 按照既定顺序, 依次处理, 在已完成步骤处理结果的基础上进行判断, 从而确定后续步骤的处理。在实际应用过程中, 一般是将两种方法结合起来, 基于这种思想, 本文采用这种方法, 以求达到更好的分割效果。
2.1 区域生长方法的原理
区域生长, 顾名思义, 就是将具有相同特征的小区域或像素点集合生长成较大区域, 这些像素或者小区域满足人为指定的生长法则。通常来说, 是从一组“Seed” (即种子) 点开始, 形成满足一定需求的生长区域, 也就是通过法则判断, 将与种子点具有相似特征属性 (例如指定灰度、颜色等) 的区域或像素附加到种子上[3]。新的区域集合成功后, 将其看作新的种子点, 继续循环上述过程, 直到整个区域中再没有像素可以被包含进种子区域, 这样满足既定需求的一个区域就生长成功了[1]。
图1是区域生长一个简单的示例。图1a) 代表需分割的图像, 其中, 将标为深浅不同的灰色方块的两个种子像素1, 5设为生长种子, 采用的判断准则为:如果像素与种子像素的灰度值绝对相差小于门限P, 则将该像素包括进种子像素所在区域。令P=3时, 结果如图1b) 所示, 整幅图被较好地分成2个区域;图1c) 中, 设定P=1, 某些像素则无法进行判定;当P=6时, 如图1d) 所示, 整幅图像被分在同一个区域中了。
通过上述讨论, 在区域生长算法应用过程中, 有三个问题亟需解决:
1) 选取种子像素, 其要求是能够代表目标区域的属性特征;
2) 确定生长法则, 以便于算法能够将邻近像素纳入区域;
3) 制定停止条件, 避免算法进入无限死循环。
2.2 区域生长方法的实现
结合分裂合并以及区域生长这两种基础思想, 文章编制了分割算法, 具体来说, 就是先将获取的数字图像分裂成多个方形的局部区域, 然后在每个局部区域单独使用区域生长的算法来实现分割过程, 最后再将局部区域合并, 从而达到分割的目的。这样的优点在于可以在每个局部区域分别使用迭代法获取局部的最佳阈值实现分割, 降低图像整体灰度的不均匀化对分割产生的影响, 可以达到更好的分割效果;其缺点也是显而易见的, 增大了算法的复杂性及计算时间。
文中算法中实现分割的主体函数是:
其中, fg为分割完成图像;rgrow为函数名;f为待分割图像;x, y的作用是将图像f分块, 亦即在处理过程中将图像分成 (x×y) 个小图块;bwr为设定的种子灰度值, 即f中所有该值像素点都将成为种子像素;range为生长法则, 利用range函数来定义一个全局阈值, 用来判定目标像素是否与选定种子或连接种子足够相似。
当不再有像素满足种子区域包含的准则时, 生长区域的过程就会停止, 算法终止, 生长完成。
采用上述算法对沥青混合料数字图像进行处理, 其中初始图像如图2a) 所示, 分割之后图像如图2b) 所示。
图2a) 为利用数码相机获取的沥青混合料数字图像原始灰度图像;图2b) 为利用本文的区域生长算法获取的分割图像, 其中黑色部分为各粒径混合料颗粒;图2c) 为采用基于阈值的OTSU (最大类间方差) 方法获取的分割图像, 图片中白色部分为混合料颗粒。
最大类间方差方法是阈值分割方法中较为常用且具有较优异分割效果的分割方法[4], 故而我们将其作为比较对象。
从两幅图的对比中我们可以发现, 对于大粒径的颗粒, 两种算法都能很好的将其边缘识别并从背景中分割出来, 但是在大粒径表面上, OTSU算法更容易在颗粒表面产生细小的孔洞, 这样会对后面颗粒的特征识别产生较大的影响。在细小的颗粒识别分割方面, 区域生长算法明显要比OTSU算法效果更好。OTSU算法相比于区域算法, 计算时间大大减少, 对于精度要求不是很高的分割, 是比较实用的, 在实际使用过程中, 我们应该根据实际情况选用不同的算法。
3 结语
图像的正确分割是进行图像分析的前提, 本文描述了区域生长分割方法在沥青混合料图像处理过程中的应用, 在结合了基于区域的分割方法中的区域生长及分裂合并的思想的基础上, 编制了适用于沥青混合料图像分割的区域生长算法, 可以较好地将集料颗粒从背景中分离出来。并将分割效果与采用最大类间方差方法获取的分割图像进行对比, 结果表明在细小颗粒识别分割方面, 本文编制的区域生长算法具有明显优异的分割效果。
参考文献
[1]章毓晋.图象分割[M].北京:科学出版社, 2001.
[2]张慧玲.沥青混合料特征识别与评价系统研究[D].西安:长安大学, 2005.
[3]姚秋玲.基于数字图像处理技术的沥青混合料组成特性研究[D].西安:长安大学, 2004.