3．5．连通成份标记.PDF

3 ．5 ．2 连通成份标记 在一幅图像中找出连通成份是机器视觉中最常见的运算之一．连通区域内的点构成表示 物体的候选区域．机器视觉中的大多数物体都有表面，显然，物体表面点投影到图像平面上 会形成空间上密集的点集．这里应该指出，连通成份算法常常会在二值视觉系统中形成瓶颈 效应，原因是连通成份运算是一个全局性的运算，这种算法在本质上是序贯的．如果图像中 仅有一个物体，那么找连通成份就没有必要；如果图像中有许多物体，且需要求出物体的特 性与位置，则必须确定连通成份． 连通标记算法可以找到图像中的所有连通成份，并对同一连通成份中的所有点分配同 一标记．图3 ．10 表示的是一幅图像和已标记的连通成份．在很多应用中，要求在标记连通 成份的同时算出连通成份的特征，如尺寸、位置、方向和外接矩形．下面介绍两种连通成份 标记算法：递归算法和序贯算法[Jain 1995]． 图3.10 一副图像及其连通成分图像 （１）递归算法 递归算法在串行处理器上的计算效率是很低的，因此，这一算法主要用于并行机上． 算法3．1 连通成份递归算法 1． 扫描图像，找到没有标记的1 点，给它分配一个新的标记L ． 3． 递归分配标记L 给1 点的邻点． 3． 如果不存在没标记的点，则停止． 4 ． 返回第一步． （２）序贯算法 序贯算法通常要求对图像进行二次处理．由于这一算法一次仅运算图像的两行，因此当 图像以文件形式存贮且空间不允许把整幅图像载入内存时也能使用这一算法．这一算法(见 算法3．2)可以查看某一点的邻点，并且可以给像素值为1 的邻点分配一个已经使用过的标 记．如果图像的邻点有两种不同的标记，则用一个等价表(equivalent table)来记录所有的等价 标记．在第二次处理过程中，使用这一等价表来给某一连通成份中所有像素点分配唯一的标 记． 本算法在从左到右、从上到下扫描图像时，算法仅能查询到某一像素点的4 －近邻中的 两个近邻点，即上点与左点．设算法已经查到了该像素的这两个近邻点，此时出现三种情况： (1) 如果这两个近邻点中没有一点为 1，则该像素点需要一个新的标记．(2) 如果这两个近 邻点中只有一点为 1，且分配了标记L，那么该像素点的标记也为L ．(3) 如果这两个邻点 都为1，且已分配了标记L，则该像素点的标记还是L ；但是当近邻点被分配了不同标记M 与N ，则这两个标记被用于了同一组元，应该把它们合并．在这种情况下，应把其中的一个 标记（一般选用最小的那个标记）分配给该像素点，并在等价表中登记为等价标记． 等价表包含了给每一连通成份分配唯一标记的信息．在第一次扫描中，所有属于同一连 通成份的标记被视为是等价的．在第二次扫描中，从一个等价集(equivalent set)中选择一个 标记并分配给连通成份中所有像素点．通常将最小的标记分配给一个连通成份．第二次扫描 将给每一连通成份分配唯一的标记． 在找到所有的连通成份后，应该统计等价表，以便删除其中的空格；然后将等价表作为 查找表对图像重新进行扫描，以便重新统计图像中的标记． 计算每一连通成份的面积、一阶矩、二阶矩是序贯连通成份算法的一个部分．当然，必 须使用分离变量来累加每一区域的矩信息．当区域合并后，每一区域的矩累计值也应加到一 起． 算法3．2 4 －连通序贯连通成份算法 1． 从左至右、从上到下扫描图像． 2 ． 如果像素点为1，则： (a) 如果上面点和左面点有一个标记，则复制这一标记． (b) 如果两点有相同的标记，复制这一标记． (c) 如果两点有不同的标记，则复制上点的标记且将两个标记输入等价表中作为等 价标记． (d) 否则给这一个像素点分配一新的标记并将这一标记输入等价表． 3． 如果需考虑更多的点，则回到第二步． 4 ． 在等价表的每一等价集中找到最低的标记． 5． 扫描图像，用等价表中的最低标记取代每一标记．