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）DE、城市街区（City Block）距离D4、棋盘（Chessboard）距离D8，如图2-8所示。

在经典几何学中，DE定义为

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

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

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

（2-8）

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

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

（2-9）

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

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

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

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

两遍算法的步骤如下。

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

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

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

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

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

2.3.2　像素邻接性和区域性质

像素邻接性（Adjacency）是数字图像中的一个重要概念。如果任意两个像素之间的距离D4(p,q)=1，则称彼此是4-邻接的。类似地，如果任意两个像素之间的距离D8(p,q)=1，则称彼此是8-邻接的。中间灰色像素的邻接性如图2-11所示。

由一些彼此邻接的像素组成的重要集合称为区域（在集合论中，区域是一个连通集）。如果定义从像素p到q的路径为一个点序列A1,A2,⋯,An，其中，A1=p，An=q，且Ai+1是Ai的邻接点，i=1,2,⋯,n−1，那么区域是指这些点序列的集合，其中，任意两个像素之间都存在完全属于该集合的路径。

如果两个像素之间存在一条路径，那么这些像素就是连通的。因此，可以说区域是彼此连通的像素的集合。连通关系是自反的、对称的、传递的，因此，它定义了集合（图像）的一个分解，即等价类（区域）。如图2-12所示，一幅二值图像按照连通关系分解为3个区域。

假设Ri是连通关系产生的不相交的区域，为了避免特殊情况，进一步假设这些区域与图像边界不接触。设区域R是所有这些区域Ri的并集，RC是R相对于图像的补集合。我们称包含图像边界的RC的连通子集合为背景，称RC的其他部分为孔。如果区域中没有孔，则该区域称为简单连通区域。等价地，简单连通区域的补集合是连通的，有孔的区域称为复连通。我们常称图像中的一些区域为物体。

一个区域是凸（Convex）的是指区域内的任意两点连成一条线段，这条线段完整地在区域内，如图2-13（a）所示。区域的凸性将所有区域划分为两个等价类：凸的和非凸的。一个区域的凸包（Convex Hull）是指包含输入区域（可能是非凸的）的一个最小凸区域。图2-13（b）所示为一个形状类似于字母B的物体，这个物体的凸包如图2-13（b）的右半部分所示。

一个区域的边缘（Edge）和边界（Border）也是数字图像中的重要概念。边缘是一个像素和其邻接邻域的局部性质，是一个具有大小和方向的向量。边缘表明在一个像素的小邻域内图像亮度变化的快慢，边缘计算的对象是具有很多亮度级别的图像，计算边缘的方式是计算图像函数的梯度。边缘的方向与梯度的方向垂直，梯度的方向指向函数增长的方向。

区域的边界是它自身的一个像素集合，其中的每个像素具有一个或更多个区域外的邻接点。该定义与人们对边界的直观理解相对应，即边界是区域的边界点的集合，称这类边界为内部边界。外部边界是区域的背景（区域的补集合）的边界。内部边界和外部边界如图2-14所示，其中，白色圆点表示内部边界，黑色方格表示外部边界。

边缘与边界虽然相关，但它们不是同一个概念，边缘只表示图像函数的局部性质，而边界是与区域有关的全局概念。

定义在方形栅格上的邻接性和连通性会产生一些悖论，如图2-15所示。

图2-15（a）给出了4条45°的数字直线。一种悖论是，如果使用4-邻接，则直线上的点都是不连通的。其中，显示了一种与直线性质的直觉理解相矛盾的更糟糕的情况：两条相互垂直的直线在一种情况下（左边）的确相交，但在另一种情况下（右边）不相交，这是因为它们根本没有任何共同点，即它们的交集为空集。

另一种悖论是，在欧氏几何学中，每个封闭曲线将平面分割成两个不连通区域。如果图像数字化为一个8-邻接的方形栅格，则可以从封闭曲线的内部到其外部画一条线但不与该曲线相交，如图2-15（b）所示。这意味着曲线的内部和外部构成一个区域，这是因为线上的所有点都属于一个区域。

对于方形栅格，这些悖论是很典型的。但是，对于六边形栅格，很多问题就不存在了，因为六边形栅格中的任何点与其6个邻接点的距离都是相同的。但是，六边形栅格很难用傅里叶变换表示，为了简单和易于处理，多数数字化转换器使用方形栅格。解决邻接性和连通性悖论的一种方法是对物体使用4-邻接处理，而对背景使用8-邻接处理（或反过来）；另一种方法是使用基于单元复合的离散拓扑。

2.3.3　拓扑性质

不同于上述几个基于距离的性质，数字图像的拓扑性质不是基于距离概念的，它对于Homeomorphic变换具有不变性。对图像而言，Homeomorphic变换可以解释为橡皮面变换（Rubber Sheet Transformations）。以在一个表面上绘制了物体的小橡皮球为例，物体的拓扑性质是指在橡皮表面任意伸展时都具有不变性的那部分性质。伸展不会改变物体各部分的连通性，也不会改变区域中孔的数目。区域的拓扑性质用于描述对小变化具有不变性质的定性性质，如凸性的性质。严格来说，一个任意的Homeomorphic变换可以将凸区域变为非凸区域，反之亦然。

非规则形状的物体可以用一组它的拓扑分量来表示。凸包中非物体的部分称为凸损（Deficit of Convexity），它可以分解为两个子集：完全被物体包围的湖（Lakes）和与物体凸包的边界连通的海湾（Bays）。