8.3.3 图像距离变换
(1)图像距离变换的定义
图像距离变换是指将二值图像中目标区域像素(一般值为1)的值转化为该点到达最近的背景点的距离，离区域边界越近的边界像素点距离值越小，离区域核心越近的像素点距离值越大，转化的结果是将二值图像转化为表示距离值的灰度图。1966年Rosenfeld等人提出距离变换的概念，虽然得到的距离只是近视的欧式距离，但为后来的各类快速距离变换奠定了坚实的基础，在那之后学者们提出了各类改进的距离变换算法来提高算法速度和准确性，使得距离变换在目标细化，图像合并、分割，目标重建等图像分析和识别领域得到了广泛的应用。尤其是在颗粒图像处理中，距离变换成功地使二值颗粒重建成灰度颗粒，方便了后续的分割处理。在实际应用中，距离变换可以描述为：一幅N×N 的二值图像A=[aij]中目标区域的像素点集合为M={(x，y)|axy=1}，背景像素点集合为B={(x，y)|axy=0}，距离变换就是利用公式求得目标区域像素到背景像素之间的最短距离，得到距离变换后的图像D[dij]。
在实际的应用中，欧氏距离变换是一种精确的L2范数距离变换，具有非线性。它可以被应用于不同领域的图像处理，但由于在变换过程中计算某个像素到本图像所有背景点的最短距离是一种全局操作，对每个点进行的平方和开放次数为图像的总点数。若图像的大小为100×100dpi，不作简化直接进行距离变换，需要的计算次数最大可达到(100×100)2=108级。由于欧氏距离的计算量大、速度慢、复杂度高，因此一般采用8邻域距离D8(棋盘距离)或4邻域距离D4(街区距离)等近似的欧氏距离来代替欧氏距离。
像素(x，y)和(i，j)之间的D4距离(街区距离)定义为：
所有距像素点(x，y)的D4距离为不大于d 的像素可以组成一个中心点在(x，y)的菱形。如与点(x，y)的D4距离为小于2或等于2的像素组成的菱形如图8.23所示。
图8.23 街区距离图
像素(x，y)和(i，j)之间的D8距离(棋盘距离)定义为：
(https://www.daowen.com)
所有距像素点(x，y)的D8距离为不大于d 的像素可以组成一个中心点在(x，y)的方形。如距点(x，y)的D8距离小于或等于2的像素组成的方形如图8.24所示。
图8.24 棋盘距离图
(2)图像距离变换的实现
图像距离变换的实现函数有很多，直接进行变换计算量过大、速度慢，因此在具体实现过程中会采用并行的方法来提高效率，或者将全局操作分解为局部的操作来简化算法，如用串行扫描的方法。串行扫描的方法是在扫描的过程中利用上一次计算的结果来计算当前像素的值，扫描过程由正向扫描和反向扫描两次扫描组成。具体的扫描方式如图8.25所示。
图8.25 扫描方式
(a)正向扫描；(b)反向扫描
在实际的二维图像中，采用一个类似卷积核的模板以类似卷积的操作在图像中进行扫描来实现图像的距离变换，其过程与一维图像的距离变换相似。首先对图像进行从左到右、从上到下的正向扫描，然后再对图像进行从右到左、从下往上的反向扫描。在扫描过程中模板覆盖的每个像素点要将其值与对应的像素值相加，从而形成一个两项和的集合。对于每个当前像素点即模板中心点对应的像素点，其值为两项和集合中的最小值。图8.26是二维图像距离变换的模板，其中3×3的模板扫描计算的结果是一灰度级图像，其像素灰度级为像素点到最近背景的欧氏距离的3倍，与真实欧氏距离的偏差不超过8%。5×5的模板扫描结果其像素灰度级为像素点到最近背景的欧氏距离的5倍，与真实欧氏距离的偏差不超过2%。由于距离变换的精度与模板的大小有关，模板越大，精度也会越高。因此对于一些精度要求较高的应用领域，很多学者都利用提高模板大小的方法来提高精度，现在已有13×13的模板。另一方面，由于模板越大，计算量也会随之增大，图像处理的效率就会变低；而随着模板的变大，精度提高的效果也会越来越低，因此有必要平衡模板的大小和实际应用中对精度的需求。对于后期的分水岭算法，我们选用5×5的模板就可以满足精度的需求。
图8.26 距离变换3×3的模板与5×5的模板
