5.7.2 连通域标记
连通域标记的方法有很多，常见的方法包括Two-Pass的方法和One-Pass的方法。其中，Two-Pass指的是扫描两遍方法，通常第一遍先对连通域进行初步标记，然后在第二遍扫描中合并一些等价的标记；One-Pass就是扫描一遍的方法，主要有基于区域生成的方法和轮廓跟踪的方法。本节采用一种快速的连通域标记方法[72]，通过等价表提高扫描的速度。
建立4 邻域的扫描模板，如图5.50 所示。当扫描到当前像素点f(x，y)时，只需要按照如图中虚线箭头所示的顺序检查其左边像素点f(x-1，y)、左上边像素点f(x-1，y-1)、正上边像素点f(x，y-1)以及右上边像素点f(x+1，y-1)。定位以上这些像素点的集合为当前像素点f(x，y)的模板像素集合M(x，y)={f(x-1，y)，f(x-1，y-1)，f(x，y-1)，f(x+1，y-1)}。
在开始扫描前，需要介绍几个重要的概念：临时标签、等价标签、代表标签以及代表标签对照表。临时标签是在第一次扫描中为每个连通域分配的标签，由于单次扫描的局限性，所以可能存在同一个连通区域被分配了两个临时标签的情况，也就是说这个两个临时标签是等价的。因此为了提高扫描的效率，在单次扫描的过程中建立等价标签集合，方便后续的合并处理。同时，定义等价标签集合中的最小临时标签i为这个集合的代表标签，并可以用S(i)代表这个集合。那么，这个等价标签集合中所有的临时标签的代表标签都为i，即T[i]=i(临时标签j的代表标签是i)，这样就建立了代表标签对照表。假设在扫描过程中发现临时标签1、3、6是等价的，于是就建立等价标签集合S(1)={1，3，6}，其中最小的临时标签1就是这个集合的代表标签，并且T[1]=1，T[3]=1，T[6]=1。
图5.50 邻域扫描模板
在了解了以上概念以后，就可以对二值图像进行连通域分析了。首先，初始化临时标签l=1，然后按照4邻域模板逐行扫描二值图像中的像素点，判断当前像素点与模板中像素点的关系，公式为：(https://www.daowen.com)
其中，
是模板中第一个非0值。如果f(x，y)是一个背景像素点，则标记为背景0；否则，按照顺序检查其模板像素。如果模板像素都是背景像素0，则f(x，y)被赋予一个新的标签；如果模板像素中存在非0值，则将模板中第一个非0值赋给f(x，y)。
从以上可以看出，当前像素点可以分为三类：(1)背景像素点；(2)模板像素集合中都为背景像素点；(3)模板像素集合中至少存在一个非0标记像素。对于第(1)种像素点，只需要对其标记为0就可以了。对于第(2)种像素点，除了为其分配一个新的临时标签l以外，还需要建立相应的等价标签集合和代表标签对照表，即S(l)={l}，T[l]=l。对于第(3)种像素点，除了为其分配模板像素集合中第一个非0的临时标签j以外，可能还需要更新和修改相应的等价标签集合以及代表标签对照表。如果在模板像素集合中还存在与临时标签j不相同的临时标签k，则检查其代表标签是否相同，假设T[k]=u，T[j]=v。如果u=v，则说明临时标签j和临时标签k已经属于同一个等价集合中，合并处理已经在之前的步骤中完成，这里不需要再进行任何处理；如果u ≠v，则说明临时标签j和临时标签k 属于不同的等价集合S(v)和S(u)，因此，需要将S(v)和S(u)合并到同一个等价集合中，并修改相应的代表标签对照表。按照之前的规定，如果u＜v，则等价集合S(v)要合并到S(u)中，S(u)=S(u)∪S(v)，同时，原来S(v)中所有元素的代表标签都要从v更改为u，即对于所有的i∈S(v)，T[i]=u。
当完成二值图像中所有像素点的扫描时，就建立了所有像素点的等价标签集合和代表标签对照表。因此，在第二遍的扫描中，对于每个像素点f(x，y)只需要将其临时标签替换为代表标签，如式5.53所示。这样就得到了记好的连通域标。
将该标记方法应用到药液二值图像中，每个区域用不同的颜色表示，结果如图5.51所示。
