几种经典的细化算法

类别

Hilditch 算法

Hilditch细化算法为是串行处理方法的一种,最终得到的是 8 条近 邻连接线条。其主要原理是每次扫描并删除图像上满足一定的条件的轮 廓像素，直到图像上不存在可删除的轮廓像素为止。该方法适用于二值图像，即像素为 1 的区域为目标区 域,像素为 0的区域为背景区域的图像。在此算法中，目标像素 P若同 时满足以下条件即为可删除像素：

1. P0+P2+P4+P6≤3
2. Nc=1；
3. Pk（0≤k≤7） 中至少有 一个目标像素为 1；
4. P2=1 或 Nc2=1；Nc2 为假定 P2=0 时 P的联 结数；
5. P4=1或Nc4=1。Nc4为假定P4=0时P的联结数。 联结数就是八邻域中互相分离的联结成分的个数。

Deutch 细化算法

Deutch细化算法采用的处理方式为并行处理方式,其算 法也是采用两层子循环。在开始的子循环中，目标像素P删除的条件是:

1. ∑Pk= 0（0≤k≤7）；
2. Nc=1；
3. P0+P2+P4+P6≤3； 若条件满足，则该点P标记为可删除像素。在接下来的子循环中， 扫描整幅图像，将所有这样的像素删除。该算法得到的骨架为不完全的 8- 连接，可以看作是具有可删除点的8- 连接图形。

Pavlidis细化

Pavlidis细化算法也是并行算法的一种，它通过与两 个模板进行匹配逐层剥掉边界像素，所得到的骨架形态是 8- 连接的。

Pavlidis异步细化算法是通过并行和串行算法混合处理来实现细化。采 用比特运算进行特定模式的匹配，所得到的骨架形态是8- 连接的。

Zhang快速并行算

Zhang 快速并行算法是 Zhang 在 1984 年于文献[2]中提出来的。 以二值图像为例，判断一个点该不该删除时要根据它的八个相邻点的情 况来判断。总结一下，有如下的判据：

1. 内部点不能删除；
2. 孤立点 不能删除；
3. 直线端点不能删除；
4. 如果P是边界点，去掉P后，如 果连通分量不增加，则P可以删除。

该算法的步骤如下：
假设一幅图像中的一个3* 3区域，对各点标记名称P1，P2…P9， 其中P1位于中心，如下表所示：

其中 P1=1为黑点，如果同时满足以下四个条件，则删除P1，即 令 P1=0：

1. P1 周围的 8 个点中，白点个数介于 2 至 6 间 ，即 2≤N (P1)≤6 ；其中，N (P1)=P2+P3+P4+P5+P6+P7+P8+P9； 这一步是为了排除孤立点和内部点；
2. 设Z（P1） 是以 P2，P3，…， P9为序时这些点的值从0到 1变化的次数，即Z（P1） = l ；当对所有 边界点都检验完毕后，将所有标记了的点除去。；
3. 继续向下删除，即 P2* P4* P8=0 or Z(P2)!= 1；
4. 继续向右删除，即 P2* P4* P6=0 or Z (P4)!= 1；
5. 继续向左删除，即 P6* P8* P2=0orZ(P8)!= 1；
6. 继续向 上删除，即P6* P4* P8=0orZo(P6)!= 1。 对图像中的每个点重复此步骤，直到所有的点都不可删除为止。

研究意义

用骨架来表示线划图像能够有效地减少数据量，减少图像的存储难度和识别难度。目前线划图(包括纸质地图、线画稿、手绘图等)的存储是非常麻烦的，存储和使用起来都很不方便。例如，一张A4大小的线划图存储需要IM的容量，另外一些比较严重的问题就是数据的修改、更新和显示。矢量化是解决这些问题的方法，但这些图的宽度经常是大于一个像素的，这会导致矢量化结果有非常大的问题，为了解决这些问题，细化就成了模式识别和矢量化的先决条件。

细化技术的一个主要应用领域是位图矢量化的预处理阶段，相关研究表明，利用细化技术生成的位图的骨架质量受到多种因素的影响，其中包括图像自身的噪声、线条粗细不均匀、端点的确定以及线条交叉点选定等，因而对线划图像进行细化从而生成高质量骨架的方法进行研究具有现实意义。

一般要求：

1. 保证细化后骨架的连通性;
2. 对原图像的细节特征要保持的较好;
3. 细化的结果是原线条的中心线;
4. 线条的端点保留完好;
5. 线条交叉点不能发生畸变;
6. 细化所用时间不能太长。

细化算法改进

Hilditch 算法的改进

Hilditch算法最大的缺点是：只适用于二值图像，比较普通，且在 判断某一象素是否为边缘点及是否应被删除时，判断依据太多，有些条 件不够简洁、有效，判决条件之间有重复，这样造成处理速度慢、通用 性差。
Pavlidis细化算法与Hilditch算法类似，基于两种算法的 优点，根据腐蚀原理，在考虑每个点周围8个相邻点的同时，考虑这些 点各自周围点的情况，并根据点点之间关联关系对Hilditch算法的删除 条件进行了一些限定，从而能充分考虑图像上的像素信息，在删除点的 时候，可以根据新的判断条件高效地去除图像上多余的像素，而不丢失 关键的特征点。

Zhang快速并行算法的改进

Zhang 快速算法所代表的基于数学形态学的细化方法是利用彼此 相互独立并列的结构元素进行二值图象的细化，因此更易于实现且计算 简单。但同时，我们也应该看到 Zhang 快速算法存在细化宽度不能保 证为单像素宽的缺陷，原图像会有很多毛刺，这对于以后的查找细化图 像的分差点带来了很大的困难。

在保持 Zhang 快速算法优点的 基础上，单独实现单像素化细化字符和断裂笔划连接，从而得到连通的 单像素宽的细化结果。其中，在对细化字符进行单像素化操作时，通过 设置一个初始值为零的变量和种子队列，灵活的实现了对原像素点及其 邻域点的保存与删除；在对细化字符进行断裂笔划连接时，通过给原图 增加四条两个像素宽的黑边及对8- 邻域、25- 邻域的分别扫描操作， 将得到的位置点置为1，实现了断裂笔划的连接。