第十一部分图像拓补学课程.pptVIP

第十一章 图像拓补学 11.1引言 我们常常对一幅图像的仅仅非常基本的方面感兴趣：一个特别目标的出现次数，是否有孔，等等。对一幅图像的这些基本性质的研究称为数字拓扑或者图像拓扑，在这章我们将研究这个课题的一些更基本的方面。 例如，考虑一幅显示斑点集合的用形态开阈值处理并清洁的图像。 11.2邻居和邻接 一个首要的任务是定义邻接的概念：在什么条件下一个像素可以被当作靠近另一个像素。在这一章，仅关心二值图像，并且因此我们将仅处理像素的位置。 一个像素有4个4-邻居： 与8个8-邻居： 如果它们互为4-邻居，两个像素P与Q是4邻接的，以及如果它们有互为8-邻居，它们是8邻接的。 11.3 路径与元素 假设P和Q为任意两个（不需要相邻）元素，并假设P和Q能被如图所示的一系列像素联接： 如果路径包含仅仅4-邻居像素，如上面示意图中路径所做的，那么P和Q是4-连接。如果路径包含8-邻居像素，那么P和Q是8-连接。下面画面显示了一个8-连接像素的例子。 一个像素的集合，全部互为4-连接，称为一个4-分量。如果全部像素是8-连接，集合是一个8-分量。 例如，下列图像有两个4-分量（一个分量包含左两列的全部像素），另一个分量包含右两列全部像素，但仅仅一个8-分量。 我们能更正式地定义路径如下： 一个从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如果 这是自反的（一个集合是它自己的一个子集）以及传递的，但不是对称的。如果 那么 不必须是真。 等价关系的重要性在于它提供我们一个非常好的处理连通问题的方式。我们需要另一个定义。一个等价类是一个其中全部目标互相等价的一个集合。 我们现在能将一幅二值图像的各组成部分定义为连通等价关系的等价类。 11.5分量标记 在这一节我们给一个标记一幅二值图像全部4-分量的一个算法，开始于左上角并横穿与向下。如果p是当前像素，令u是它的上面4-邻居，l是它的左4-邻居： 为了描述的目的，图像中的一个像素将被称为一个前台像素。一个不在图像中的像素将被称为一个后台像素。现在给出算法： 1、检查p的状态。如果它是一个后台像素，移至下一个扫描位置。如果它是一个前台像素，检查u和l的状态。如果它们都是后台像素，给p分配一个新的标记。（这是当遇到一个新的分量的情况） 如果u和l中仅仅一个是前台像素，将它的记号分配给p. 如果u和l都是前台像素并且有同样记号，将记号分配给p. 如果u和l都是前台像素，但有不同记号，两个记号中的任何一个分配给p并记下两个记号是等价的（因为u和l属于同样的连接通过p的4-组分） 2、在扫描的末尾，全部前台像素都被做记号了，但一些记号可以是等价的。我们现在将记号排序为等价类并为每个类分配一个不同记号。 3、第二遍穿过图像，将前台像素上的记号用上个步骤中分配给等价类的记号代替。 在第二行，第一个（前景）像素又一次是它的上面或者左邻居为背景或不存在，所以我们给它分配一个新的记号-2。 第二行的第二个（前台）像素现在有它的上面及左邻居为前台像素。然而，它们有不同的记号。我们因此将这两个记号之一分配给第二个像素，譬如记号1，并且做一个记号1和记号2等价的备忘。 第二行的第三个前台像素上面及左面的邻居都是背景像素，所以我们为它分配一个新的记号-3。 在第三行，第一个前台像素有它的上面及左邻居都是背景像素，因此我们为它分配一个新的记号-4。第三行的第二个（前台）像素现在有它的上面与左面邻居都是前台像素。然而，它们有不同的记号。我们因此将这两个记号的任何一个分配给这个第二个像素，譬如记号3，并且做一个记号3和记号4是等价的备忘。 在第四行中，第一个像素