算法-计算机视觉 | 基于二值图像数字矩阵的距离变换算法

Hi，大家好，我是半亩花海。本实验基于 OpenCV 实现了二值图像数字矩阵的距离变换算法。首先生成一个 480x480 的黑色背景图像（定义黑色为0，白色为1），在其中随机选择了三个白色像素点作为距离变换的原点，利用 OpenCV 中 distanceTransform 等相关函数计算并输出这些原点到其他像素点的欧氏距离、D4 距离和 D8 距离及其相应的距离矩阵，并将距离变换结果可视化。

一、导入必要库

导入必要的库（cv2、numpy、matplotlib.pyplot），为后续的图像处理任务做准备。

#!/usr/bin/env python
# coding: utf-8
import cv2
import numpy as np
import matplotlib.pyplot as plt

# 用来设置字体样式(黑体)以正常显示中文标签
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False

二、初始化输入图像和变换结果图像

自定义 480x480 二值图，随机生成图案，初始值都是 0（黑色），并显示原始图像。

• 图像数字化：
  通过传感器获得的图像是平面坐标 $(x,y)$ 的连续函数 $f(x,y)$，它的值图像对应位置的亮度。为了能够让计算机来处理，需要对图像进行采样，并且对亮度值进行量化。

  • 采样： 对连续函数 $f(x,y)$ 进行采样，就是分别对 $x$ 轴和 $y$ 轴，按照固定间隔取值，得到平面坐标上的 $M\times N$ 个点，将其函数值作为元素生成 $M$ 行 $N$ 列的矩阵。

  • 量化亮度值。 将 $f(x,y)$ 的值转化为等价的整数值的过程称为量化，量化的级别越高，图像越细致。通常将亮度值表示为 0～255 之间的整数。

# 创建一个大小为 480x480 的全黑图像（确保数据类型为 8 位无符号整数）
mat = np.zeros((480, 480), dtype=np.uint8)

# 给输入图像指定三个像素点设置为白色像素，作为距离变换原点（区域块）
mat[100, 200] = 1
mat[200, 100] = 1
mat[300, 300] = 1

# 显示原始图像和距离变换结果
plt.figure(figsize=(15, 5))
plt.scatter([100, 200, 300], [200, 100, 300], color='white', marker='o')  # 添加三个白点表示出三个像素点的坐标
plt.imshow(mat, cmap='gray')
plt.title('原始图像', fontsize=16)

# 将输入图像中 1（白色）和 0（黑色）调换，使得原点距离为 0
mat = 1 - mat

三、根据二值图计算并输出距离矩阵

• 距离： 距离是描述图像两点像素之间的远近关系的度量，常见的度量距离有欧式距离（Euchildean distance）、城市街区距离（City block distance）、棋盘距离（Chessboard distance）。以下以两坐标点 $a=(i,j)$ 和 $b=(k,l)$ 的距离为例，来说明各种距离的定义方式。

（1）欧式距离 $D_e$： 欧式距离的定义源于经典的几何学，与我们数学中所学的简单几何的两点之间的距离一致，为两个像素点坐标值的平方根。欧式距离的优点在于其定义非常地直观，是显而易见的，但缺点在于平方根的计算是非常耗时的。

$$D_e(a,b)=\sqrt{\left((i-k{)}^2\right)+(j-l{)}^2}$$

（2）城市街区距离 $D_4$： 距离描述的是只允许像素坐标系平面中横向和纵向的移动距离，4表示在这种定义下，像素点是 4 邻接的，即每个点只与它的上、下、左、右相邻的 4 个点之间的距离为 1。

$$D_4(a,b)=|i-k|+|j-l|$$

（3）棋盘距离 $D_8$： 如果允许在图像坐标系中像素点的对角线方向的移动，就可以得到棋盘距离，8 表示在这种定义下，像素点是 8 邻接的，即每个点只与它的上、下、左、右、四个对角线方向相邻的 8 个点之间的距离为 1。

D 8 ( a , b ) = max ⁡ { ∣ i − k ∣ , ∣ j − l ∣ } D_8(a, b)=\max \{|i-k|,|j-l|\} D8​(a,b)=max{∣i−k∣,∣j−l∣}

• 距离变换

距离变换也叫作距离函数或者斜切算法。它是距离概念的一个应用，图像处理的一些算法以距离变换为基础。距离变换描述的是图像中像素点与某个区域块的距离，区域块中的像素点值为 0，临近区域块的像素点有较小的值，离它越远值越大。

以二值图像为例，其中区域块内部的像素值为 1，其他像素值为 0。距离变换给出每个像素点到最近的区域块边界的距离，区域块内部的距离变换结果为0。输入图像如图 1 所示， $D_4$ 距离的距离变换结果如图 2 所示。

下面来讨论距离变换算法，其核心是利用两个小的局部掩膜遍历图像。第一遍利用掩模1，左上角开始，从左往右，从上往下。第二遍利用第二个掩模，右下角开始，从右往左，从下往上。掩模形状如下图所示：

按照某种距离（如：$D_4$ 距离或 $D_8$ 距离）对大小为 $M\times N$ 的图像中的区域块作距离变换，算法过程如下：

（1） 建立一个大小为 $M\times N$ 的数组 $F$，作如下的初始化：将区域块中的元素设置为 0，其余元素设置为无穷；

（2） 利用掩模1（mask1），左上角开始，从左往右，从上往下遍历数组，将掩模中P点对应的元素的值作如下更新：

F ( P ) = min ⁡ q ∈ mask1 ⁡ { F ( P ) , D ( P , q ) + F ( q ) } F(P)=\min _{q \in \operatorname{mask1}}\{F(P), D(P, q)+F(q)\} F(P)=q∈mask1min​{F(P),D(P,q)+F(q)}

（3） 利用掩模2（mask2），右下角开始，从右往左，从下往上遍历数组，将掩模中P点对应的元素的值作如下更新：

F ( P ) = min ⁡ q ∈ mask2 ⁡ { F ( P ) , D ( P , q ) + F ( q ) } F(P)=\min _{q \in \operatorname{mask2}}\{F(P), D(P, q)+F(q)\} F(P)=q∈mask2min​{F(P),D(P,q)+F(q)}

最终得到的更新后的数组即为距离变换的结果。

这个算法过程在图像的边界处需要做出调整，因为在边界处，掩模不能全部覆盖图像，这时可以将掩模中没有对应元素的位置的值当作 0 来处理，即maskSize=0。

在 OpenCV 中，distanceTransform 函数是用于计算二进制图像中每个非零像素到最近零像素的距离的函数。这个函数通常用于图像处理中的形态学操作和特征提取。下面是 distanceTransform 函数的一般形式：

dist_transform = cv2.distanceTransform(src, distanceType, maskSize)

• src： 是输入的二进制图像（该图像应该是一个 8 位单通道图像）。

• distanceType： 是指定距离度量的类型。

• maskSize： 是指定计算距离时使用的卷积核的大小。

# 分别利用欧式距离、D4 距离和 D8 距离作距离变换
transMatE = cv2.distanceTransform(mat, distanceType=cv2.DIST_L2, maskSize=0)  # 计算欧氏距离变换
transMatD4 = cv2.distanceTransform(mat, distanceType=cv2.DIST_L1, maskSize=0)  # 计算 D4 距离变换
transMatD8 = cv2.distanceTransform(mat, distanceType=cv2.DIST_C, maskSize=0)  # 计算 D8 距离变换

# 输出欧式、D4 和 D8 的距离矩阵
print("欧氏距离的变换矩阵:\n", transMatE)
print("城区距离-D4的变换矩阵:\n", transMatD4)
print("棋盘距离-D8的变换矩阵:\n", transMatD8)

四、将距离矩阵转换为可视化图片

因为经过距离矩阵变换之后，变换结果的数据类型为 float32（32 位浮点数），而在 OpenCV 中，采用 imshow 函数显示图像时需要使用 uint8 数据类型（8 位无符号整数），使得像素值的范围是从 0～255，可以表示灰度图像中的所有可能像素值。而 Matplotlib 可以直接处理 float32 类型的图像数据，因此并不需要将图像数据类型转换为 uint8 类型。

plt.figure(figsize=(15, 5))

plt.subplot(1, 3, 1)
plt.imshow(transMatE, cmap='gray')
plt.title('欧氏距离', fontsize=16)
plt.colorbar(shrink=0.8)

plt.subplot(1, 3, 2)
plt.imshow(transMatD4, cmap='gray')
plt.title('城区距离-D4', fontsize=16)
plt.colorbar(shrink=0.8)

plt.subplot(1, 3, 3)
plt.imshow(transMatD8, cmap='gray')
plt.title('棋盘距离-D8', fontsize=16)
plt.colorbar(shrink=0.8)

plt.tight_layout()
plt.show()