第十一章 图像拓补学

第十一章图像拓补学11.1引言我们常常对一幅图像的仅仅非常基本的方面感兴趣：一个特别目标的出现次数，是否有孔，等等。对一幅图像的这些基本性质的研究称为数字拓扑或者图像拓扑，在这章我们将研究这个课题的一些更基本的方面。•例如，考虑一幅显示斑点集合的用形态开阈值处理并清洁的图像。n=imread('nodules1.tif');n2=imopen(n,strel('disk',5));imshow(n2)图像n2在图11.1中显示。斑点的数目能用形态方法被确定。然而，图像拓扑的研究为这样诸如目标计数的任务提供了供选择并且非常有力的方法。拓扑为诸如邻接和距离提供非常严格的定义。如我们将看见，用拓扑方法骨架化能被容易地实现。11.2邻居和邻接•一个首要的任务是定义邻接的概念：在什么条件下一个像素可以被当作靠近另一个像素。在这一章，仅关心二值图像，并且因此我们将仅处理像素的位置。•一个像素有4个4-邻居：•与8个8-邻居：pp•如果它们互为4-邻居，两个像素P与Q是4邻接的，以及如果它们有互为8-邻居，它们是8邻接的。11.3路径与元素•假设P和Q为任意两个（不需要相邻）元素，并假设P和Q能被如图所示的一系列像素联接：Qp•如果路径包含仅仅4-邻居像素，如上面示意图中路径所做的，那么P和Q是4-连接。如果路径包含8-邻居像素，那么P和Q是8-连接。下面画面显示了一个8-连接像素的例子。Qp•一个像素的集合，全部互为4-连接，称为一个4-分量。如果全部像素是8-连接，集合是一个8-分量。•例如，下列图像有两个4-分量（一个分量包含左两列的全部像素），另一个分量包含右两列全部像素，但仅仅一个8-分量。Qp•我们能更正式地定义路径如下：•一个从P到Q的4-路径是一个像素系列•P=p0,p1,p2,…,pn=Q•使得对于每个i=0,1,…,n-1，像素pi与像素pi+1，4-邻接。•一个8-路径是连接P和Q的系列像素是8-邻接。11.4等价关系•两个目标x和y之间的一个关系x~y是一个等价关系如果关系是•自反的，对全部x，有x~x，•对称的，对于全部x和y，x~y等同于y~x•传递的，对于全部的x，y和z，如果x~y并且y~z，那么x~z•举一些例子，看下面：•对于数值相等，关系x~y如果x和y是两个数字，对于它们x=y。•除式，关系x~y如果x和y是两个用7除具有相同余数的数字。•对于集合基数，S~T如果S和T是两个带有相同数目元素的集合。•对于连通性，P~Q如果P和Q是两个连接的像素。•这里是一些不等价关系•个人的关系：定义关系x~y如果x和y是互相有关系的两个人。这不是一个等价关系。它是自反的（一个人当然与他自己或她自己有关系）并且对称，但不传递•像素邻接：这是不传递的•子集关系：定义S~T如果这是自反的（一个集合是它自己的一个子集）以及传递的，但不是对称的。如果那么不必须是真。STSTTS•等价关系的重要性在于它提供我们一个非常好的处理连通问题的方式。我们需要另一个定义。一个等价类是一个其中全部目标互相等价的一个集合。•我们现在能将一幅二值图像的各组成部分定义为连通等价关系的等价类。11.5分量标记•在这一节我们给一个标记一幅二值图像全部4-分量的一个算法，开始于左上角并横穿与向下。如果p是当前像素，令u是它的上面4-邻居，l是它的左4-邻居：我们将一行一行扫描图像，从左至右移动横穿。我们将给图像中的像素分配标记。这些标记是图像中各部分的编号。ulp•为了描述的目的，图像中的一个像素将被称为一个前台像素。一个不在图像中的像素将被称为一个后台像素。现在给出算法：1、检查p的状态。如果它是一个后台像素，移至下一个扫描位置。如果它是一个前台像素，检查u和l的状态。如果它们都是后台像素，给p分配一个新的标记。（这是当遇到一个新的分量的情况）•如果u和l中仅仅一个是前台像素，将它的记号分配给p.•如果u和l都是前台像素并且有同样记号，将记号分配给p.•如果u和l都是前台像素，但有不同记号，两个记号中的任何一个分配给p并记下两个记号是等价的（因为u和l属于同样的连接通过p的4-组分）2、在扫描的末尾，全部前台像素都被做记号了，但一些记号可以是等价的。我们现在将记号排序为等价类并为每个类分配一个不同记号。3、第二遍穿过图像，将前台像素上的记号用上个步骤中分配给等价类的记号代替。•第一步我们开始沿上面行移动。第一个前台像素是在第二个位置的点，因为它的上及左或者是背景像素或者不存在，我们给它分配记号1。•我们现在给实际中这个算法的一个例子，在二值图像上，它有两个4-组分：一个是上左方的三个像素，另一个是底右部的5个像素。•在第二行，第一个（前景）像素又一次是它的上面或者左邻居为背景或不存在，所以我们给它分配一个新的记号-2。12•第二行的第二个（前台）像素现在有它的上面及左邻居为前台像素。然而，它们有不同的记号。我们因此将这两个记号之一分配给第二个像素，譬如记号1，并且做一个记号1和记号2等价的备忘。121•第二行的第三个前台像素上面及左面的邻居都是背景像素，所以我们为它分配一个新的记号-3。1213•在第三行，第一个前台像素有它的上面及左邻居都是背景像素，因此我们为它分配一个新的记号-4。第三行的第二个（前台）像素现在有它的上面与左面邻居都是前台像素。然而，它们有不同的记号。我们因此将这两个记号的任何一个分配给这个第二个像素，譬如记号3，并且做一个记号3和记号4是等价的备忘。121343•在第四行中，第一个像素的上面及左面邻居都是背景像素，所以我们为它分配一个新的记号-5。第四行的第二个（前台）像素现在有它的上面与左面邻居为前台像素。然而，它们有不同的记号。我们因此将这些记号的任何一个分配给这个第二个像素，譬如记号4，并做一个记号4和记号5等价的备忘。这完成了第一步。12134354•第二步我们有下列记号的等价类•{1,2}和{3,4,5}。•将记号1分配给第一类并将记号2分配给第二类。•第三步从第一步带有记号1或者2的每个像素将被分配记号1，并且从第一步带有记号3，4，或者5的每个像素将被分配记号2。11122222•这完成了算法。•算法能被修改为标记一幅图像的8-组分，但在第一步我们需要考虑p的对角元素：duelp•算法与前面算法相似。第一步改变如下：•第一步如果p是一个背景像素，移到下一个扫描位置。如果它是一个前台像素，检查d,u,e,和l。如果它们全部是后台像素，为p分配一个新的记号。如果只有一个是一个前台像素，将它的记号分配给p。如果两个或者更多为前台像素，将它们记号的任何一个分配给p并做一个全部它们的记号是等价的备忘。•第二和三步如前•这个算法用bwlabel函数实现。我们将在一个小的图像上给一个例子：并且结果是：i=zeros(8,8);i(2:4,3:6)=1;i(5:7,2)=1;i(6:7,5:8)=1;i(8,4:5)=1;ii=0000000000111100001111000011110001000000010011110100111100011000•这幅图像能被看出有两个8-组分和三个4-组分。为了看见这些，我们能输入将产生ans=0000000000222200002222000022220001000000010033330100333300033000bwlabel(i,4)•以及bwlabel(i,8)•将产生ans=0000000000111100001111000011110001000000010022220100222200022000•为了用一幅真实的图像实验，让我们尝试计数图像bacteria.tif中细菌的数目。图像必须首先阈值化获得一个二值图像显示仅仅细菌然后对结果应用bwlabel。我们能找到目标的数目简单地通过找出产生的最大记号。结果被给出为38这就是输出结果，可看作目标个数。n=imread('nodules1.tif');bl=bwlabel(n);max(bl(:))11.6查表•查表提供了二值图像处理的一个非常整洁及效率高的方法。考虑一个像素的3x3邻域。因为在这个邻域中有9个像素，每个像素有两个可能状态，不同邻域的全部数目是29=512因为任何二值运算的输出将是0或1，一个查找表是一个长度为512的二值矢量，每个元素表示从相应邻域的输出。注意这与4.4节讨论的查找表略微不同。在那一节，查找表被应用于单个-像素灰度数值，这里它们被应用于邻域。•技巧是能调整全部邻域使得我们在邻域与输出数值之间有一个一一对应。这通过给邻域中的每个像素一个权完成。•通过将数值为1像素的权相加获得邻域的数值。那个数值于是为查找表的索引。例如，下面显示了邻域与它们的数值。1864216128432256010110001值=282100011111值=437•为了应用一个查找表，我们必须首先制造它。一个元素一个元素产生一个查找表是单调乏味的，所以我们使用makelut函数，它根据一个规则定义一个查找表。它的语法是•makelut（function,n,p1,p2,…）其中function函数是定义一个MATLAB矩阵函数的一个字符，n是2或3，以及p1,p2,等等是被传递给函数的选择的参数。我们注意makelut为查找表允许2x2邻域。在这个情况下查找表有仅仅16个元素。•假设我们希望找到一幅图像的4-边界。我们定义一个像素为一个边界像素，如果它是一个前台像素，它是一个后台像素的4-邻接。所以makelut中被使用的函数是一个返回1的函数当且仅当3x3邻域的中心像素是一个边界像素返回1的函数：f=inline('x(5)&~(x(2)*x(4)*x(6)*x(8))');•注意在这个函数中我们使用了单个-数值矩阵索引方案，如此使得x(5)是3x3矩阵x的中心像素，以及x(2)，x(4)，x(6)，x(8)是中心的4-邻接像素。•现在我们能制作查找表：lut=makelut(f,3);•以及将它应用于一幅图像。结果见下图。c=imread('circles.tif');cw=applylut(c,lut);imshow(c),figure,imshow(cw)•我们能容易地调整函数找到8-边界像素，这些为与后台像素8-连接的前台像素。•结果显示在图11.3。注意这是一个比较强的边界，因为更多像素被分类为边界像素。•通过上面的例子可以看到，查表法对于目标的骨架化比较有效。