距离变换图和骨架图生成算法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,距离变换图和骨架图生成算法,6.8,距离变换图和骨架图生成算法,1,、距离变换图算法,距离变换图算法,是一种针对栅格图像的特殊变换，是把二值图像变换为灰度图像，其中每个像素的灰度值等于它到栅格地图上相邻物体的最近距离。,6.8,距离变换图和骨架图生成算法,1,、距离变换图算法,（,1,）基本思想,是把离散分布在空间中的目标根据一定的距离定义方式生成距离图,其中每一点的距离值是到所有空间目标距离中最小的一个。,对于距离的量度是通过,四方向距离,（又称,“,城市块距离,”,或,“,出租车距离,”,）的运算来实现的，即只允许沿四个主方向而不允许沿对角方向进行跨栅格的最小路段的计数。因此，每个路段为一个像元边长。,6.8,距离变换图和骨架图生成算法,1,、距离变换图算法,（,2,）基于“欧几里德距离”公式的距离变换图算法,在二维平面上定义两点，那么他们之间的欧氏距离表示为,：,在二值图像中，,1,代表目标点，,0,代表背景；在灰度图像中，栅格的灰度值表示该栅格点到最近目标点的距离值。这样一张,M,N,的图像可以表示为一个二维数组,A,M,N,，其中,A,i,j,=1,对应的栅格表示目标点，,A,i,j,=0,对应的栅格表示背景点。设,B,=(,x,y,)|,A,i,j,=1,为目标点集合，则欧氏距离变换就是对,A,中所有的栅格点求：,其中,从而得到二值图像,A,的欧氏距离变换图。,欧氏距离变换,1,加权欧氏距离变换,欧氏距离变换效果图,(3,张,),欧氏距离变换,2,加权,欧氏距离变换,6.8,距离变换图和骨架图生成算法,1,、距离变换图算法,（,2,）基于“欧几里德距离”公式的距离变换图算法,栅格空间中的,“,欧几里德距离,”,距离变换公式：,其中，点,P,1,(,i,，,j,),和,P,2,(,m,，,n,),的坐标值,i,j,m,n,都是整数。,只要图中,a,、,b,、,c,的取值满足,1,b,/,a,2,，,1,c,/,b,2,，那么它就是欧几里德距离的一个在栅格空间中的整数近似值。,6.8,距离变换图和骨架图生成算法,1,、距离变换图算法,（,3,）基于栅格图像间的运算,获取距离变换图的算法,基于栅格图像间的运算获取距离变换图算法的基本方法是：反复对原图进行,“,减细,”,和将减细结果与中间结果作算术,“,叠加,”,两种基本运算。其终止条件是：,“,若对原图再减细，则将成为全零矩阵,”,。,6.8,距离变换图和骨架图生成算法,2,、骨架图算法,骨架图就是从距离变换图中提取出具有相对最大灰度值的那些像元所组成的图像。,骨架图算法是一种简洁、直观的目标表示方法，它综合利用了目标的,外部轮廓,和,内部区域信息,，在描述目标形状方面具有传统表示方法不可比拟的优势，且骨架图,“,山脊线,”,的连接关系保留了,空间拓扑结构,的完整，从而极大地扩展了骨架图算法的应用领域。,6.8,距离变换图和骨架图生成算法,2,、骨架图算法,自,1967,年,Blum,提出中轴的概念以来，骨架已经成为表示和识别物体的重要手段之一，骨架组合了目标的轮廓喝中药区域信息，反映了目标的重要视觉线索，因而，寄语骨架的目标表示和识别技术成为牧师识别和计算机视觉的重要研究内容。,为了准确的对物体进行识别，要求骨架要求具有如下性质：,（,1,）保留原物体的拓扑。,（,2,）骨架点的位置精确，要靠近物体的中心。,（,3,）骨架的连通性。,（,4,）获得骨架的半径值。,（,5,）骨架能表达物体在人类视觉中的重要部分。,6.8,距离变换图和骨架图生成算法,2,、骨架图算法,骨架图算法实现的途径主要有两条，其一是,基于灰度图像的骨架图算法,，其二是直接,从灰度图像提取目标骨架的算法,。,其中，基于灰度图像的骨架图算法主要有,3,类,：,(1),从距离变换中提取骨架,即通过计算灰度图像的距离变换，从距离变换图中检测并连接骨架点得到目标的骨架，其缺点是难以设计恰当的邻域条件，需要较多的后处理。,6.8,距离变换图和骨架图生成算法,2,、骨架图算法,(2),采用,边界模型,提取骨架，即采用离散边界模型在逼近真实形状的同时提取骨架，可得到在噪声环境下稳健的骨架。但是，运用该方法时因构造离散边界模型比较困难，提取出的骨架有时可能是不连通的。,6.8,距离变换图和骨架图生成算法,2,、骨架图算法,(3),基于区域标记的方法。其典型代表是,Liu,等人（,2000,）提出的基于,Arcelli,的,“,非脊点下降,”,算子的骨架提取算法。该算法通过并行地对图像中的所有非脊点进行下降，将图像分别标记为骨架点和背景点，可以获得单像素宽的、与原始图像同伦的骨架。但该算法有时不能提取一些规则目标的完整骨架，而且算法对边界噪声比较敏感（陈晓飞等，,2003,）。,6.8,距离变换图和骨架图生成算法,2,、骨架图算法,基于距离变换的骨架图生成算法,6.8,距离变换图和骨架图生成算法,3,、距离变换图和骨架图的应用,距离变换图常用于地图制图、地理空间的各种量度（如面积、密度、坡度、坡向等）及空间分析（如缓冲区分析、,Voronoi,分析、,DEM,分析等）等方面。,