4.1 基本概念
得到的道路，还需要进一步的细化。道路的细化就是线细化，现在我把这一部分内容介绍给大家。在叙述算法之前，要对有关的概念做一些必要的说明。
八邻域及像素符号
图4-1 八邻域图
如图4-1所示，与图象中任一像素P相邻的8个像素称为P的八邻域，用Pi(0<=i<=7)表示，其中Pn称为n-近邻。此外，为了讨论的方便，在二值图象中，用0表示背景图象，用1表示目标像素。
图4-2 联结数示例
联结数与多重像素
联结数就是八邻域中互相分离的联结成分的个数。目标像素P的联结数可表示为
图4-2给出几个像素联结数的例子，属于同一联结成分的点被圈在了一起。如果像素P的联结数Nc≠1，则称P为多重像素。多重像素决定目标连通性。
轮廓像素
设像素P∈R(R为连通的像素集合)，若P的八邻域中至少有一个像素Pi不属于R，则称P为R的轮廓像素。如果轮廓像素不同时满足多重像素的条件，则这种轮廓像素不影响目标R的连通性，在细化中可删除之。
细线
宽度为1的线称为细线，线细化的最终结果就是把所有的线目标都转变为细线，只有细线才便于线跟踪和矢量化。
4.2 细化算法
线细化，就是不断去除曲线上不影响连通性的轮廓像素的过程，在这个过程中保留曲线的多重像素，直到目标曲线所有点都是多重像素为止，对细化的一般要求是：
保证细化后曲线的连通性
细化结果是原曲线的中心线
细化处理速度快
保留细线端点
根据各种不同的应用，国内外已经发表了许多细化算法，如内接园法、经典算法、异步算法、快速并行算法及并行八边算法等，不同的算法在处理速度和效果上各有其特点。我使用的算法是在Hilditch细化算法的基础上改造而成，试验表明它有较好的细化效果和很快的处理速度。
如果目标像素P同时满足以下条件，那么P可以被标记为可删除点。
a. P0+P2+P4+P6<=3，保证P是轮廓像素。
b. Pi(i=0-7)中至少有两个目标像素，保证不是端点。
c. Nc=1，保证P不是多重像素。
算法中还要用到两个序列，一个用来描述某一像素点是否被标记为可删除点，另一个记录剩余的目标像素点。最后一个序列对提高算法的速度起着至关重要的作用，因为细化过程中，剩余的目标像素点越来越少，如果在这时候还是扫描整幅地图，必然要浪费许多的时间。算法流程如下：
Step1 扫描整幅地图，将属于道路的目标像素点记录在目标序列中。
Step2 扫描剩余的目标像素点，检测其是否需要删除，如果需要，就标记为可删除点，否则，标记为不可删除点。
Step3 把标记为可删除的目标像素点全部从目标序列中删去。
Step4 重复Step2,Step3知道没有目标像素点可以删除为止。
图4-3 宽度为2的道路
但这样有一个缺点就是宽度为2的线将全部被删除。如图4-3所示的两行像素点都满足可删除的条件。怎么办呢，我们已经知道，一个目标像素点是否可被删除，是由其八邻域中目标像素点的分布来决定的。但是，如果其八邻域中的某一目标像素点已经被标记为可删除点了，那么这个目标像素点其实就不能在当作目标像素点来对待，因为这个点注定是要删除的了。所以八邻域中的被标记为可删除点的目标像素点
就不能在作为目标像素点进行判定了。这样这个问题就解决了。如图4-3所示，第一行像素点被标记为可删除点后，在判定第二行像素点时，因第一行已经不属于目标像素点，因此，第二行像素点就不会也被判定为可删除点了。
图4-4 道路
但是这样会使细化的结果不是原曲线的中心线了，如4-4所示，第一行首先被标记为可删除点，接着第二行也被标记为可删除点，结果把第三行剩下了。下面我把目标像素点是否属于可删除点的三个判定条件再重申一下：
a. P0+P2+P4+P6<=3，保证P是轮廓像素。在这个条件中，八邻域中的目标像素点不管标没标记为可删除点，都按1处理。
b. Pi(i=0-7)中至少有两个目标像素，保证不是端点。在这个条件中，被标记为可删除点的目标像素点就要按0来处理。
c. Nc=1，保证P不是多重像素。在这个条件中，被标记为可删除点的目标像素点也要按0来处理。
图4-5 细化使道路变短
这样上述的问题就解决了。但还有一个小问题，如图4-5所示，细化后的道路短了一点，道路的端点处缩短了道路宽度的一半。其中原因，大家一看就会明白，这一点可以在算法上做一些纠正。但毕竟道路的宽度和长度比起来相差甚远，因此也可以忽略这个小错误，我目前就没有处理。
