基于游程法的二值图像Blob 分析算法

按照处理对象的不同， 目前典型的连通性分析算法包括基于像素的方法和基于游程的方法。后者是对像素法的一种改进，它充分利用了区域各部分之间的连通关系，搜索空间得到压缩，整体效率高于前者， 因此近年来得到了更多的关注。在具体实现上，这两类方法都可采用递归法或序贯算法。递归法实现起来简单，但运行时需要消耗大量堆栈， 除了效率低，在实际应用中还容易因堆栈资源耗尽而造成算法不稳定。序贯法在扫描过程中会出现标记冲突现象，为此，常规的做法是对图像( 或子图像) 进行二次或多次扫描， 并利用冲突等价表等辅助措施来消除标记冗余 。由于等价表结构复杂，增加内存消耗; 利用等价表进行标记合并及重复扫描时间开销很大，不利于实时性要求较高的应用。

简单来说，本文采用步进式动态扫描方式，每个游程仅需扫描一次，且不必与相邻行的所有游程进行比较， 算法的搜索空间得到压缩; 游程连通性比较的分支少，简化了判断过程， 提高了操作效率; 所设计的游程及目标对象的数据结构允许由任一游程节点快速访问其所属链表的首部和尾部， 不仅为后续的数据访问提供了便利， 且提高了标记冲突时链表合并的操作速度，避免了冲突等价表的介入。实验结果表明该算法具有鲁棒、 高效的特性。

2. 算法描述

2.1 游程及 Blob 目标对象数据结构定义

不失一般性，设分割得到的二值图像中，背景像素灰度为0，目标像素灰度为 1。一行中灰度值连续为 1 的像素构成一个游程数据单元。定义如下的游程数据结构对之进行描述:

struct RLE { short r，s，e; RLE * pn; BLOB ＊＊ppB}

其中: r 代表游程所在行号，s 为游程像素在该行的起始位置，e 为其在该行的终止位置。因每个游程数据单元必属于且仅属于某个唯一的 Blob 对象，将同属一个目标对象的所有游程数据单元组织成一个线性链表， 每个游程数据单元即为链表中的一个节点，用指针 pn 来指向链表中的下一游程节点。数据域 ppB 为间接指向其所属 Blob 对象的二级指针， 通过它可快速检索到其所属链表的头部和尾部， 用以解决标记冲突时对链表的快速合并操作， 具体过程将在后文详述。Blob 目标对象定义为:

struct BLOB { RLE * ph; RLE * pt; }

其中: ph 指向链表的头部( header) ，pt 指向链表的尾部( tail) 。可见，一个 BLOB 对象实际上描述了一个 RLE 链表， 通过它可访问同属该目标的所有 RLE 对象。算法结束后， 将动态生成一个 BLOB 链表，它描述了一幅图像中的全部目标对象。

2.2 数据准备

顺序扫描二值图像的每一行，可得到整幅图像的 RLE 表达形式。为了能够快速访问各行的游程数据， 为图像的每行维护一个一维的动态数组，数组元素类型为 RLE* ，即该行游程数据单元指针构成的索引; 若某行不存在游程数据( 即全部为背景像素) ，则数组为空。

2.3 连通性判据

相邻两行的任意两个游程连通， 当且仅当其中一个游程存在至少一个像素与另一个游程中的像素连通。游程连通性有 4 连通和 8 连通之分， 本文仅考虑 8 连通性。对于第 i － 1行和第 i 行的两个游程 RLE［ i － 1］ 与 RLE［i］,可用式( 1) ～( 2) 进行连通性判断若同时满足式( 1) ～ ( 2) ， 则两者连通; 否则不连通［ 2］ 。

RLE［ i］.s≤RLE［ i － 1］.e + 1 ( 1)

RLE［ i］.e + 1≥RLE［ i － 1］.s ( 2)

2. 4 算法流程

算法约定: 设二值图像高度为 H， 记第 i 行的游程个数为size( i) 。从第 0 行开始， 按照从左到右的顺序扫描该行的游程数组。算法每次取出当前行( i) 的第 k 个及上一行( i － 1)

的第 k'个游程数据( 记为 RLE( k) ， RLE( k') ， 分别称为当前游程和参考游程) 进行比较。为方便描述， 约定以符号 ＆ 表示取对象的地址，* 表示对该地址所指向的对象进行操作。

算法完整步骤描述如下:

第 1 步 如果 i≥H， 即图像所有行已经分析完毕， 则算法结束; 否则初始化当前游程和参考游程的索引 k、 k'←0， 转第 2 步。

第 2 步 如果 k≥size( i) ， 即当前行的游程已经分析完毕，则将行号 i 加 1，转第 1 步; 否则转第 3 步。

第 3 步 如果 k' ≥size( i － 1) ， 说明上一行的游程已经比较完毕，则执行第 3.1 步; 否则转第 4 步。

第 3.1 步 如果当前游程的 ppB 不为空， 说明该游程已经标记，转第 3． 2 步; 否则， 应向 BLOB 链表添加一个新的BLOB 对象及其索引 Ref←＆BLOB， 并设置其 ph 和 pt 指针同时指向当前游程: BLOB.ph、 BLOB.pt←＆ RLE( k) ; 同时设置当前游程指向该 BLOB， 即 RLE( k) .ppB←＆Ref; 继续执行第3.2 步。

第 3.2 步 将当前游程索引值 k 增 1，转第 2 步。

第 4 步 此时当前游程和参考游程均有效， 利用连通性判据式( 1) 和( 2) 进行两者的比较，根据比较结果按以下 3 种情况进行处理:

情况 1

如果两个游程不连通，且当前游程像素起始位置在 参 考 游 程 像 素 终 止 位 置 右 边， 即 RLE ( k ).s ＞RLE( k') .e + 1，如图 1 所示，则将 k'加 1，转第 2 步。

图 1 当前游程在参考游程右边

情况 2

如果两个游程不连通， 且当前游程像素终止位置 在 参 考 游 程 像 素 起 始 位 置 左 边，即 RLE( k) .e + 1 ＜RLE( k').s，如图 2 所示，则转第 3.1 步。

图 2 当前游程在参考游程左边

情况 3

如果两个游程连通，根据当前游程的 ppB 域是否为空进行以下处理，然后继续第 5 步:

1) 如果当前游程的 ppB 为空， 即其尚未标记过， 此时应直接将其挂接到上行参考游程所在链表的尾部，即:

( * RLE( k') .ppB).pt.pn←＆ RLE( k)

并更新该链表的尾部，使其指向当前游程:

( * RLE( k').ppB).pt ←＆ RLE( k)

同时修改当前游程所属的 ppB 指针， 使之与参考游程相同:

RLE( k).ppB ← RLE( k').ppB

2) 如果当前游程 ppB 不为空， 即其曾经标记过， 此时应该判断当前游程所属链表是否与参考游程所属链表一致( 通过比较二者的 ppB 域是否具有相同值) 。如一致， 无需进行任何操作; 否则意味着出现标记冲突， 应合并两个链表， 为此执行下列操作:

a) 将当前游程所在的链表挂接到参考游程所在链表的尾部:

( * RLE( k').ppB).pt.pn ←( * RLE( k).ppB).ph

b) 参考游程所在链表的尾部修改为指向当前游程所在链表的尾部:

( * RLE( k').ppB).pt ←( * RLE( k).ppB).pt

c) 遍历 BLOB 索引数组， 将所有指向当前游程合并前所属 BLOB 的索引值修改为指向参考游程所属的 BLOB; 同时从BLOB 链表中删除当前游程在合并前所属的 BLOB 节点。

第 5 步 更新 k 和 k'的值: 若上行参考游程像素终止位置不在 当 前 游 程 像 素 终 止 位 置 右 边， 即 RLE ( k ).e ≥RLE( k').e，则将 k 加 1; 若参考游程像素终止位置不在当前

游程像素终止位置左边，即 RLE( k).e≤RLE( k').e， 则将 k'加 1。返回到第 2 步继续。

3 实验与结果分析

采用C + + 作为编程语言， 以 Visual Stdio 2008 为工具实现了本文算法。为便于观察，标记结果被转换成一幅 24 位的彩色位图，其中属于同一目标对象的像素被随机赋予了同一颜色值。图 3 列出了对 3 幅二值测试图像进行标记的结果。测试表明，本文算法运行稳定、 有效，对目标形状复杂、 个数不定的图像有极佳的适应性。

图 3 测试图像与标记结果图像

本文算法运行稳定、 高效， 适于实时性要求高的应用，算法主要特点为:

1) 采用动态的步进式扫描方式， 充分利用了游程相互之间的空间信息，扫描过程中当前游程不需要与上行的所有游程进行比较，进一步压缩了搜索空间; 两个游程的位置关系判断分支少，简化了比较过程，提高了比较效率。

2) 通过特殊的数据结构设计， 在游程链接及处理标记冲突时的链表合并操作中， 无需遍历链表即可从任意游程节点直接访问到其所属链表的头部和尾部，加快了分析过程，且方便了后续数据访问，提高了算法整体效率。

3) 该算法可进一步扩展为一次处理三行， 即当前行游程同时与上下两行中的游程进行比较， 其实质是对整幅图像的游程编码仅进行隔行扫描， 可进一步减少同一游程的被访问次数。

参考文献：

胡广华 面向光学薄膜瑕疵检测的二值图像快速Blob分析算法2011年10月 《计算机应用》第31卷 第10期

免责声明：本文系网络转载。版权归原作者所有。如涉及版权，请联系删除！