该论文发表于IPCV(Image Processing and Computer Vision)1984年，是细化算法的经典算法。我们亲切的称它为Zhang算法，后续的细化算法大多都是基于该算法的改进。今天就来看看这篇论文吧。没错，我就是喜欢挖坟。

---

---

             A Fast Parallel Algorithm for Thinning Digital Patterns

ABSTRACT：本文提出了一种快速并行细化算法。 它由两个子项组成：一个旨在删除东南边界点和西北角点，另一个旨在删除西北边界点和东南角点。 保留端点和像素连接。 每个图案都被减薄为单一厚度的“骨架”。 实验结果表明，该方法非常有效。

1、INTRODUCTION

众所周知，模式识别的一般问题在于从模式中提取区别特征的有效性和效率。笔划分析方法是识别某些类型的数字模式（如字母数字字符和表意文字）的有效方法。应该注意，由硬件或软件稀疏的笔划伴随着不同类型的失真。不同的细化算法会产生不同程度的失真[1-5,7-12]。
关于薄度的确切定义，文献中没有普遍的一致意见。 Pavlidis [6]描述了一种通过局部操作确定骨架像素的细化算法。同时，标记像素，以便可以从其骨架重建原始图像。本文的目标是找到一种更快，更有效的并行细化算法。失真应该尽可能少。实验结果表明，该方法可用于细化各种数字模式。

2、PARALLEL PICTURE PROCESSING

二进制数字化图像由矩阵定义，其中每个像素是1或0。该图案由具有值1的那些像素组成。图案中的每个笔划都是多于一个元素的厚度。迭代变换根据一小组相邻点的值逐点地应用于矩阵。假设点的邻居是。如图1所示。在并行图像处理中，在第n次迭代中给予点的新值取决于它自己的值以及在第（n-1）次迭代中它的八个邻居的值，以便可以同时处理所有图像点。这是一个使用3*3窗口，每个元素都和它的8个相邻元素相关联。本文中的算法要求只需要简单的计算。(说白了就是八连通区域)

3、THINNING ALGORITHM

我们用于提取图片骨架的方法就是：删除除了那些属于骨架的点之外的所有图像点。 为了保留骨架的连接，我们将每次迭代分成两个子项。 在第一个子迭代中，如果边缘点满足如下条件，它就会从图像中删除：

就是有序集合中的01模式的数量，而是非0邻居的数量。

如果不满足任何条件，例如，图2中P2，P3，P4，··· P9的值，那么

因此，图片中的P1就没有没删除掉。

在第二个子迭代中，只有条件（c）和条件（d）被改变了，其他都不变。如下式子：

根据第一个子迭代的条件（c）和条件（d）可以看出，第一个子迭代只是去除了东南边界点和西北中心点，不能得到完美的骨架。

有关第一个子迭代的证明已经给出，也就是，需要被删除的点满足的条件：

等式（1）和（2）的解是P4 = 0或P6 = 0或（P2 = 0且P8 = 0）。因此，已被移除的点P1可能是东或南边界点或西北角点。类似地，可以证明在第二个子迭代中删除的点P1可以是西北边界点或东南角点。例如，两个子迭代处理字符“H”的结果如图4（a）和4（b）所示。标有“.”的点已被删除。最终结果如图4（c）所示。

条件（a）表示骨架线的端点被保留。此外，条件（b）可以防止删除位于骨架线端点之间的那些点，如图5所示。迭代继续进行，直到不再能够移除任何点。

所提出的细化算法的流程图如图6所示。最初，原始图像存储在矩阵IT中，计数器C设置为0.处理后的图像的结果存储在矩阵IT中。为了节省存储空间，我们的计算中只使用了两个矩阵IT和M.图7（a）-7（c）分别显示了我们的算法对汉字“”，字母“B”和数字“移动体”的结果。骨架点标有“*”或“@”，并且在细化过程中已删除的所有点都标有“ . ”。

上述算法在连接性和轮廓噪声抗扰度方面产生非常好的结果。此外，搜索应从模式中删除的那些点的条件非常简单。为了评估我们算法的性能，我们选择了Stefanelli和Rosenfeld [11]给出的算法进行比较。这两种算法都是用FORTRAN编写的，在同一台CDC Cyber​​ 172计算机上运行，​​并使用相同的数字化模式进行测试。结果表明，我们算法的执行时间仅为给定算法的50％[11]。可以预测，执行时间取决于模式的复杂程度和笔画的粗细：中文字符为“0.505 CPU秒”字母“B”为“〜”0.454 CPU秒，移动体为1.163秒。

4、SUMMARY

本文提出了一种细化不同类型数字模式的并行算法。 每次迭代分为两个子项，删除数字模式的边界和角点。 经过几次迭代后，只剩下图案的骨架。
所提出的算法在数字模式的细化方面似乎非常有效，并且它与[11]中描述的算法相比有利。 表I中的结果表明，我们的方法比[11]中描述的四步法和两步法快1.5至2.3倍，而得到的骨架看起来非常相似。

 

------------------------------------------------END-------------------------------（下）讲实现--------------------------------------------------------------