2.3 数字图像性质

2.3.1 距离度量与距离变换

一般来说，一幅数字图像可以被认为是由有限大小的像素组成的，像素反映图像特定位置处的亮度信息。通常，像素按照矩形采样栅格布置。我们用二维矩阵来表示这样的数字图像，矩阵的元素是自然数，对应于亮度范围的量化级别。假设有来自数字图像 I ( x , y ) 的3个像素 p 、 q 、 r ，如果函数 D 作用于这3个像素后能够满足以下3个条件，则该函数 D 可以被认为是一种距离度量或度量。

（1）同一性： D ( p , q )≥0，当且仅当 p = q 时， D ( p , q )=0。

（2）对称性： D ( p , q )= D ( q , p )。

（3）三角不等式： D ( p , r )≤ D ( p , q )+ D ( q , r )。

一般来说，对于两个像素坐标( i , j ) 和( h , k ) 之间的距离度量，可以有以下3种形式：欧氏距离（Euclidean Distance） D _E 、城市街区（City Block）距离 D ₄ 、棋盘（Chessboard）距离 D ₈ ，如图2-8所示。

在经典几何学中， D _E 定义为

欧氏距离的优点是直观，缺点则是平方根的计算复杂度较高，并且其值不是整数。

两个像素点之间的距离也可以表示为在数字栅格上从起点移动至终点所需的最少步数。如果只允许横向和纵向移动，则这个距离就是 D ₄ 。由于这种移动方式类似于在具有栅格状街道和封闭房子块的城市中两个位置间的移动，因此 D ₄ 也称为城市街区距离，其定义为

D ₄ [( i , j ),( h , k )]=| i − h |+| j − k |

（2-8）

如果在数字栅格中允许对角线方向的移动，则这个距离就是 D ₈ ，常称为棋盘距离。 D ₈ 等于国际象棋中国王在棋盘上从一处移动至另一处所需的步数，即以这两点为一条对角线的矩形较长的那条边，其定义为

D ₈ [( i , j ),( h , k )]=max{| i − h |,| j − k |}

（2-9）

距离变换也称为距离函数、斜切算法或简单斜切，它是距离概念的一个简单应用。距离变换提供了像素与某个图像子集（可能表示物体或某些特征）的距离。所产生的图像在该子集元素位置处的像素为0，距离图像子集近的像素具有较小的值，而距离图像子集远的像素具有较大的值。

考虑一幅二值图像，其中，1表示物体，0表示背景。定义该图像的每个像素到最近物体的距离为 D ₄ 距离变换。物体内部的像素的距离变换等于0。距离变换示意图如图2-9所示，其中，输入图像如图2-9（a）所示， D ₄ 距离变换结果如图2-9（b）所示。

对于距离度量 D ₄ 和 D ₈ ，有学者提出了一个计算距离变换的两遍算法。它的思想是用一个小的局部掩膜遍历图像。第一遍计算从左上角开始，先水平从左到右直至图像边界，然后返回下一行开始处继续。第二遍计算从右下角开始，使用一个不一样的掩膜从右到左、从下到上进行遍历。该算法有效性源于以波浪状的方式传播前一步勘测的数值，掩膜示意图如图2-10所示。

在图2-10中，像素 p 位于中心，左侧的邻域用于第一遍计算（从上到下，从左到右），右侧的邻域用于第二遍计算（从下到上，从右到左）。

两遍算法的步骤如下。

（1）按照一种距离度量 D （ D 是 D ₄ 或 D ₈ ），对大小为 M × N 的图像的一个子集 S 计算距离变换，建立一个 M × N 的数组 F 并进行初始化。子集 S 中的像素置为0，其他像素置为 ∞ 。

（2）按行遍历图像，从上到下，从左到右，对于上方和左面的邻接像素（图2-10所示的AL集合），设 。

（3）按行遍历图像，从下到上，从右到左，对于下方和右面的邻接像素（图2-10所示的BR集合），设 。

（4）数组 F 中得到的是子集 S 的斜切。

两遍算法在图像边界处需要做出调整，因为在边界处，掩膜不能全部覆盖图像，这时可以将掩膜中没有对应像素的位置的值当作0来处理。 +QXsQikTnnYObno1FkWgF9wxU2Z7CPJXz/Y0oV8VXo8+VMo0Z8vubvVj2PtQj3hV