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

1、距离变换图和骨架图生成算法距离变换图和骨架图生成算法 6.8 距离变换图和骨架图生成算法 1 1、距离变换图算法、距离变换图算法 距离变换图算法是一种针对栅格图像的特 殊变换，是把二值图像变换为灰度图像，其中 每个像素的灰度值等于它到栅格地图上相邻物 体的最近距离。 6.8 距离变换图和骨架图生成算法 1 1、距离变换图算法、距离变换图算法 （1 1）基本思想）基本思想 是把离散分布在空间中的目标根据一定的 距离定义方式生成距离图, 其中每一点的距离 值是到所有空间目标距离中最小的一个。 对于距离的量度是通过四方向距离（又称 “城市块距离”或“出租车距离”）的运算来 实现的，即只允许沿四个主方

2、向而不允许沿对 角方向进行跨栅格的最小路段的计数。因此， 每个路段为一个像元边长。 6.8 距离变换图和骨架图生成算法 1 1、距离变换图算法、距离变换图算法 （2）基于“欧几里德距离”公式的距离变换图算法 在二维平面上定义两点，那么他们之间的欧氏距离表示为 ： 在二值图像中，1代表目标点，0代表背景；在灰度图像中，栅格的灰度值 表示该栅格点到最近目标点的距离值。这样一张MN的图像可以表示为 一个二维数组AMN，其中Aij=1对应的栅格表示目标点，Aij=0对应 的栅格表示背景点。设B=(x,y)|Aij=1为目标点集合，则欧氏距离变换 就是对A中所有的栅格点求： 其中 从而得到二值图像A的欧

3、氏距离变换图。 欧氏距离变换1欧氏距离变换2 加权欧氏距离变换 6.8 距离变换图和骨架图生成算法 1 1、距离变换图算法、距离变换图算法 （2）基于“欧几里德距离”公式的距离变换图算 法 22 21 )()(),(),(jnimnmjifPPD 栅格空间中的“欧几里德距离”距离变换公式： 其中，点P 1 ( i，j )和P 2 (m，n) 的坐标值i, j ,m , n 都是整数。 只要图中a、b、c 的取值满足1 b/a 2， 1c/b 2， 那么 它就是欧几里德距离的一个在栅格空间中的整数近似值。 6.8 距离变换图和骨架图生成算法 1 1、距离变换图算法、距离变换图算法 （3）基于栅格

4、图像间的运算 获取距离变换图的算法 基于栅格图像间的运算获取距离变换图算法的基本方法是：反 复对原图进行“减细”和将减细结果与中间结果作算术“叠加”两种基 本运算。其终止条件是：“若对原图再减细，则将成为全零矩阵” 。 6.8 距离变换图和骨架图生成算法 2 2、骨架图算法、骨架图算法 骨架图就是从距离变换图中提取出具有相对 最大灰度值的那些像元所组成的图像。 骨架图算法是一种简洁、直观的目标表示 方法，它综合利用了目标的外部轮廓和内部区 域信息，在描述目标形状方面具有传统表示方 法不可比拟的优势，且骨架图“山脊线”的连 接关系保留了空间拓扑结构的完整，从而极大 地扩展了骨架图算法的应用领域。

5、 6.8 距离变换图和骨架图生成算法 2 2、骨架图算法、骨架图算法 自1967年Blum提出中轴的概念以来，骨架已经成为表示和识别 物体的重要手段之一，骨架组合了目标的轮廓喝中药区域信息，反 映了目标的重要视觉线索，因而，寄语骨架的目标表示和识别技术 成为牧师识别和计算机视觉的重要研究内容。 为了准确的对物体进行识别，要求骨架要求具有如下性质： （1 1）保留原物体的拓扑。）保留原物体的拓扑。 （2 2）骨架点的位置精确，要靠近物体的中心。）骨架点的位置精确，要靠近物体的中心。 （3 3）骨架的连通性。）骨架的连通性。 （4 4）获得骨架的半径值。）获得骨架的半径值。 （5 5）骨架能表达物

6、体在人类视觉中的重要部分。）骨架能表达物体在人类视觉中的重要部分。 6.8 距离变换图和骨架图生成算法 2 2、骨架图算法、骨架图算法 骨架图算法实现的途径主要有两条，其一是基 于灰度图像的骨架图算法，其二是直接从灰度图像 提取目标骨架的算法。 其中，基于灰度图像的骨架图算法主要有3类： (1) 从距离变换中提取骨架,即通过计算灰度图像 的距离变换，从距离变换图中检测并连接骨架点得 到目标的骨架，其缺点是难以设计恰当的邻域条件， 需要较多的后处理。 6.8 距离变换图和骨架图生成算法 2 2、骨架图算法、骨架图算法 (2) 采用边界模型提取骨架，即采用离散边 界模型在逼近真实形状的同时提取骨架

7、，可 得到在噪声环境下稳健的骨架。但是，运用 该方法时因构造离散边界模型比较困难，提 取出的骨架有时可能是不连通的。 6.8 距离变换图和骨架图生成算法 2 2、骨架图算法、骨架图算法 (3) 基于区域标记的方法。其典型代表是Liu等人 （2000）提出的基于Arcelli的“非脊点下降”算子 的骨架提取算法。该算法通过并行地对图像中的所 有非脊点进行下降，将图像分别标记为骨架点和背 景点，可以获得单像素宽的、与原始图像同伦的骨 架。但该算法有时不能提取一些规则目标的完整骨 架，而且算法对边界噪声比较敏感（陈晓飞等， 2003）。 6.8 距离变换图和骨架图生成算法 2 2、骨架图算法、骨架图算法 基于距离变换的骨架图生成算法 6.8 距离变换图和