4－连通序贯连通成份算法-linux内核设计与实现 原书第3版 完整版带书签目录下载

算法 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． 扫描图像，用等价表中的最低标记取代每一标记．