第3章像素空间关系
3.1像素间的基本关系
图像的基本组成单元是像素,像素在图像空间中按照某种规律排列,有一定的相互联系。常见的像素间的基本关系包括像素的邻域、邻接、连接、通路和连通以及像素集合间的邻接、连接和连通。
3.1.1像素的邻域
像素的邻域是指一个像素的相邻像素构成的像素集。邻域的类型一般包括4邻域、对角邻域和8邻域,如图31所示。
图31邻域的类型
1. 4邻域
像素p的4邻域是指由像素p的水平方向(即左右)和垂直方向(即上下)共4个相邻像素所组成的集合,记为N4(p)={r1,r2,r3,r4}。若像素p的坐标为(x,y),则像素p的4邻域像素的坐标分别为r1: (x-1,y)、r2: (x,y-1)、r3: (x+1,y)和r4: (x,y+1),如图31(a)所示。
2. 对角邻域
像素p的对角邻域是指由像素p的对角方向(即左上、左下、右上、右下)共4个相邻像素所组成的集合,记为ND(p)={s1,s2,s3,s4}。若像素p的坐标为(x,y),则像素p的对角邻域像素的坐标分别为s1: (x-1,y+1)、s2: (x-1,y-1)、s3: (x+1,y-1)和s4: (x+1,y+1),如图31(b)所示。
3. 8邻域
像素p的8邻域是指由像素p的水平、垂直和对角方向(即左右、上下、左上、左下、右上、右下)共8个相邻像素所组成的集合,记为N8(p)={r1,r2,r3,r4,s1,s2,s3,s4}。若像素p的坐标为(x,y),则像素p的8邻域像素的坐标分别为r1: (x-1,y)、r2: (x,y-1)、r3: (x+1,y)、r4: (x,y+1)、s1: (x-1,y+1)、s2: (x-1,y-1)、s3: (x+1,y-1)和s4: (x+1,y+1),如图31(c)所示。
需要注意的是,如果像素p本身处于图像的边缘,则它的4邻域N4(p),对角邻域ND(p)和8邻域N8(p)中的若干个像素将位于图像之外。
3.1.2像素的邻接
像素的邻接是指一个像素与其邻域中的像素的接触关系。邻接的类型根据邻域的类型的不同一般分为4邻接、对角邻接和8邻接。
1. 4邻接
4邻接是指一个像素与其4邻域中的像素的接触关系。若两个像素为p和r,则像素p与像素r满足4邻接可表示为
p∈N4(r)(31)
注意: 像素p与像素r满足4邻接等价于像素r与像素p满足4邻接,即式(32)成立。
p∈N4(r)r∈N4(p)(32)
2. 对角邻接
对角邻接是指一个像素与其对角邻域中的像素的接触关系。若两个像素为p和r,则像素p与像素r满足对角邻接可表示为
p∈ND(r)(33)
注意: 像素p与像素r满足对角邻接等价于像素r与像素p满足对角邻接,即式(34)成立。
p∈ND(r)r∈ND(p)(34)
3. 8邻接
8邻接是指一个像素与其8邻域中的像素的接触关系。若两个像素为p和r,则像素p与像素r满足8邻接可表示为
p∈N8(r)(35)
注意: 像素p与像素r满足8邻接等价于像素r与像素p满足8邻接,即式(36)成立。
p∈N8(r)r∈N8(p)(36)
需要注意的是,邻接仅考虑了像素间的空间关系,与像素的属性值无关。
3.1.3像素的连接
两个像素的连接是指两个像素必须邻接(即接触)且它们的属性值必须满足某个特定的相似准则。属性值一般采用像素的灰度值。相似准则可以是灰度值相等,或者同在一个灰度值集合中取值,记为V。例如,在一张二值图像中,定义两个灰度值为1的像素之间的连接,可以取相似准则为灰度值集合V={1}; 在一张256色的灰度图像中,定义灰度值为100~105的像素之间的连接,可以取相似准则为灰度值集合V={100,101,102,103,104,105}。
连接的类型根据邻域的类型的不同一般分为4连接、对角连接、8连接以及混合连接。
1. 4连接
4连接是指两个像素4邻接且它们的属性值满足某个特定的相似准则。若两个像素为p和r,像素的属性值函数为f(),相似准则为V,则4连接的条件可表示为
(p∈N4(r))∧(f(p)∈V)∧(f(r)∈V)(37)
2. 对角连接
对角连接是指两个像素对角邻接且它们的属性值满足某个特定的相似准则。若两个像素为p和r,像素的属性值函数为f(),相似准则为V,则对角连接的条件可表示为
(p∈ND(r))∧(f(p)∈V)∧(f(r)∈V)(38)
3. 8连接
8连接是指两个像素8邻接且它们的属性值满足某个特定的相似准则。若两个像素为p和r,像素的属性值函数为f(),相似准则为V,则8连接的条件可表示为
(p∈N8(r))∧(f(p)∈V)∧(f(r)∈V)(39)
4. 混合连接
混合连接又称m连接,是指两个像素的属性值必须满足某个特定的相似准则且满足下列两个条件之一: ①两个像素4邻接; ②两个像素对角邻接且它们4邻域的交集在相似准则的意义下是空集。若两个像素为p和r,像素的属性值函数为f(),相似准则为V,则混合连接的条件可表示为式(310)或式(311):
(p∈N4(r))∧(f(p)∈V)∧(f(r)∈V)(310)
(p∈ND(r))∧(f(ND(p)∩ND(r))∩V=)(311)
例3.1混合连接的判定。一张4×4的二值图像模板如图32(a)所示,相似准则V={1},当图像数据如图32(b)和图32(c)取值时,判定像素p和r是否满足混合连接的条件。
图32混合连接的判定
解: 由图像模板可知,像素p和r互为对角邻接,即p∈ND(r),且像素p和r对角邻域的交集为: ND(p)∩ND(r)={c,d}。
(1) 当图像数据如图32(b)取值时,有: f(c)=0,f(d)=0,则
f(ND(p)∩ND(r))=f({c,d})=f(c)∪f(d)={0}∪{0}={0}
因此,f(ND(p)∩ND(r))∩V={0}∩{1}=
所以,像素p和r满足混合连接的条件。
(2) 当图像数据如图32(c)取值时,有: f(c)=1,f(d)=0,则
f(ND(p)∩ND(r))=f({c,d})=f(c)∪f(d)={1}∪{0}={0,1}
因此,f(ND(p)∩ND(r))∩V={0,1}∩{1}={1}≠
所以,像素p和r不满足混合连接的条件。
混合连接可以认为是8连接的一种变型,引进混合连接是为了消除使用8连接时常出现的多路问题。
例3.2多路问题示例。一张3×3的二值图像模板如图33(a)所示,相似准则V={1},像素a、b、c、d的灰度值均取1,像素e的灰度值取0。试分析采用8连接和混合连接时像素a、b、c、d的连接情况。
图33多路问题示例
解: 采用8连接时,像素a、b、c、d的连接情况如图33(b)所示。此时,像素a和c之间存在两条8连接通路,即abc和ac,导致像素a和c之间产生多路问题。
采用混合连接时,像素a、b、c、d的连接情况如图33(c)所示。此时,像素a和b之间满足混合连接条件,像素b和c之间满足混合连接条件,因此,像素a和c之间存在一条混合连接通路abc。
另外,f(ND(a)∩ND(c))=f({b,e})=f(b)∪f(e)={1}∪{0}={0,1}
因此,f(ND(a)∩ND(c))∩V={0,1}∩{1}={1}≠
所以,像素a和c之间不满足混合连接条件,即不存在混合连接通路ac。
因此,采用混合连接时,像素a和c之间不存在多路问题。
3.1.4像素的通路
从一个具有坐标(x,y)的像素p到另一个具有坐标(s,t)的像素q的一条通路定义为由一系列具有坐标(x0,y0),(x1,y1),…,(xn,yn)的独立像素组成的集合,并且满足以下条件:
(1) (x0,y0)=(x,y),(xn,yn)=(s,t);
(2) (xi,yi)与(xi-1,yi-1)邻接;
(3) 1≤i≤n,n为通路的长度。
根据邻接类型的不同,通路的类型也不同。如果像素间邻接的类型为4邻接、对角邻接或8邻接,则对应通路的类型为4通路、对角通路或8通路。
3.1.5像素的连通
像素的连通是指像素通路上所有像素的属性值均满足某个特定的相似准则。根据连接类型的不同,连通的类型也不同。如果像素间连接的类型为4连接、对角连接、8连接或混合连接,则对应连通的类型为4连通、对角连通、8连通或混合连通。
像素连接可以看作是像素连通的一种特例。当n=1时,两个连通的像素也是连接的。
3.1.6像素集合的邻接
图像可以看作是像素的集合。像素集合根据一定的规则可以划分成若干个子集,每一个子集就构成了一个子图像。对于两个图像子集S和T来说,如果S中的一个或一些像素与T中的一个或一些像素邻接,则称两个图像子集S和T是邻接的。如果像素间邻接的类型为4邻接、对角邻接或8邻接,则对应图像子集的邻接类型为4邻接、对角邻接或8邻接。
3.1.7像素集合的连接
两个图像子集S和T是连接的是指两个图像子集必须邻接且邻接像素的属性值必须满足某个特定的相似准则。也就是说,对于两个图像子集S和T来说,如果S中的一个或一些像素与T中的一个或一些像素连接,则称两个图像子集S和T是连接的。如果像素间连接的类型为4连接、对角连接、8连接或混合连接,则对应图像子集的连接类型为4连接、对角连接、8连接或混合连接。
3.1.8像素集合的连通
对于图像子集S中的两个像素p和q来说,如果存在一条完全由S中的像素组成的从p到q的通路,则称p在S中与q连通。对于S中的任一个像素p,所有与p相连通且又在S中的像素的集合(包括p)称为S中的一个连通组元。图像里同一个连通组元中的任意两个像素相互连通,而不同连通组元中的像素互不连通。
图像中每个连通组元构成图像中的一个区域。图像可以认为是由一系列区域组成。区域的边界也称区域的轮廓,是该区域的一个子集,它将该区域与其他区域分开。组成一个区域边界的像素本身属于该区域而在其邻域中存在不属于该区域的像素。
3.2像素间的距离
像素间的距离是指像素在空间的接近程度。设3个像素为p、q和r,坐标分别为(x,y)、(s,t)和(u,v),则距离量度函数D必须满足下列三个条件:
(1) D(p,q)≥0;
(2) D(p,q)=D(q,p);
(3) D(p,r)≤D(p,q)+D(q,r)。
其中,条件(1)表明两个像素之间的距离总是为正值,若D(p,q)=0当且仅当p=q; 条件(2)表明像素之间的距离与起点和终点的选择无关; 条件(3)表明像素之间的最短距离是沿直线的。
常见的距离度量方法包括欧氏距离、城区距离、棋盘距离和混合距离。
3.2.1欧氏距离
欧氏(Euclidean)距离记为DE,设像素点p的坐标为(x,y),像素点q的坐标为(s,t),则像素点p和q之间的欧氏距离的定义如下式所示:
DE(p,q)=(x-s)2+(y-t)2(312)
欧氏距离的几何意义为: 距离坐标为(x,y)的像素的DE距离小于或等于某个值d的像素都包括在以(x,y)为中心以d为半径的圆中,如图34所示。
图34欧氏距离
其中,图34(a)为距离坐标为(x,y)的像素的DE距离小于或等于3的像素所构成的圆形区域,其值为各像素点距离中心像素点的距离值,该值已经过四舍五入处理; 图34(b)为距离值对应的3D透视图。
3.2.2城区距离
城区(cityblock)距离记为D4,设像素点p的坐标为(x,y),像素点q的坐标为(s,t),则像素点p和q之间的城区距离的定义如下式所示:
D4(p,q)=|x-s|+|y-t|(313)
城区距离的几何意义为: 距离坐标为(x,y)的像素的D4距离小于或等于某个值d的像素都包括在以(x,y)为中心的菱形中,如图35所示。其中,图35(a)为距离坐标为(x,y)的像素的D4距离小于或等于3的像素所构成的菱形区域,其值为各像素点距离中心像素点的距离值; 图35(b)为距离值对应的3D透视图。
图35城区距离
由城区距离的定义可知,距离像素p的城区距离为1的像素就是像素p的4邻域像素。因此,像素p的4邻域可以通过城区距离定义为
N4(p)={r|D4(p,r)=1}(314)
式中,r为某个像素。
3.2.3棋盘距离
棋盘(chessboard)距离记为D8,设像素点p的坐标为(x,y),像素点q的坐标为(s,t),则像素点p和q之间的棋盘距离的定义如下式所示:
D8(p,q)=max(|x-s|,|y-t|)(315)
棋盘距离的几何意义为: 距离坐标为(x,y)的像素的D8距离小于或等于某个值d的像素都包括在以(x,y)为中心的正方形中,如图36所示。
图36棋盘距离
其中,图36(a)为距离坐标为(x,y)的像素的D8距离小于或等于3的像素所构成的正方形区域,其值为各像素点距离中心像素点的距离值; 图36(b)为距离值对应的3D透视图。
由棋盘距离的定义可知,距离像素p的棋盘距离为1的像素就是像素p的8邻域像素。因此,像素p的8邻域可以通过棋盘距离定义为式(316)。
N8(p)={r|D8(p,r)=1}(316)
式中,r为某个像素。