吕常魁 徐岩 罗冰心

(南京航空航天大学 机电学院， 江苏 南京 210016)

基于游程的连通区域标记两次扫描快速算法*

吕常魁 徐岩 罗冰心

(南京航空航天大学 机电学院， 江苏 南京 210016)

为提高二值图像连通区域标记(CCL)的计算效率，提出快速游程标记(FRL)算法，对基于游程的两次扫描算法中的传统游程连通检测算法进行了优化；然后介绍了基于FRL与并查集的整体算法；最后对FRL的计算效率进行了实验验证，并将整体算法与RTS 与SAUF 两种典型的两次扫描CCL算法进行了比对分析.结果表明：FRL算法省去了行间游程不必要的后续比对，使得比对形式接近于链式，大幅度提高了游程标记的计算效率，时间复杂度由传统RL算法的O(mn)降为O(m+n-1)，执行时间降为与并查集运算环节同一量级；整体算法的性能明显优于RTS算法，总体上略优于SAUF算法.

连通区域标记；两次扫描算法；连通检测算法；游程标记；并查集

连通区域标记(CCL)是机器视觉、模式识别等领域的重要底层基础算法之一.CCL以像素或游程为基本处理单元，检测二值图像中属于同一连通区域的所有单元并进行区域标记.CCL按扫描模式主要可分为多次扫描算法[1- 2]、两次扫描算法[3- 12]和一次扫描算法[13- 14].常用的CCL算法以两次扫描算法为主.两次扫描算法一般分为3个阶段：① 扫描图像，检测单元间连通性，赋予各单元临时标记并记录单元间等价标记信息；② 处理等价对表，获得各临时标记的最终标记；③二次扫描各单元，赋予各单元最终标记.现代两……