基于递归的二值图像连通域像素标记算法

基于递归的二值图像连通域像素标记算法

徐正光，鲍东来，张利欣

(

北京科技大学信息工程学院，北京

100083)

摘

要：

在研究以前二值图像连通算法的基础上，提出了一种基于递归方法的二值图像连通域像素标记算法。通过对二值图像的扫描和分

析可得到二值图像中的连通域划分和连通域的数目。算法主要包括两个步骤：对输入的二值图像进行一次扫描，得到所有目标像素的连通

域划分和标记的等价对表；利用递归对等价对表进行分析，得到正确的连通标记划分和连通区域数目。实验结果表明，该算法对于任意复

杂形状、任意数目

(

小于

1 000)

的连通区域都能正确检测。

关键词：

二值图像；像素标记；递归

Pixel Labeled Algorithm Based on Recursive Method of Connecting 

Area in Binary Images 

XU Zhengguang, BAO Donglai, ZHANG Lixin 

(School of Information Engineering, University of Science and Technology Beijing, Beijing 100083)

【

Abstract

】

On the foundation of studying former connecting area algorithms, the paper presents a pixel labeled algorithm based on recursive

method of connecting area in binary images. The algorithm determines the distribution and count of connecting areas through once scanning of

image. It mainly includes two steps in the algorithm. Firstly, scanning the input binary image is used to get the whole connecting labeled area and the

equal marks list. The second step is to analyze the equal marks list by recursive method to ascertain the right distribution and count of connecting

areas. Experiments show that it can exactly detect any connecting areas in binary images, which contains complicated shapes and random number

(less than 1 000). 

【

Key words

】

Binary image; Pixel labeling; Recursion 

计

算

机

工

程

Computer Engineering

第

32

卷

第

24

期

Vol.32    No.24

2006

年

12

月

December 2006

·

人工智能及识别技术

·

文章编号：

1000

—

3428(2006)24

—

0186

—

03

文献标识码：

A  

中图分类号：

TP391.41

1 

概述

二值图像的连通域标记处理操作就是从白色像素

(

通常

二值图像用

“

1

”

，

灰度图像用

“

255

”

来表示

) 

和黑色像素

(

通

常用“

0

”来表示

) 

组成的一幅点阵图像中，将互相邻接

(

一

般研究

4-

邻接或

8-

邻接

) 

的具有像素值“

1

”或“

255

”的像

素集合提取出来，并为图像中不同的连通域填入不等的数字

标记，同时统计连通域的数目。该过程是计算机视觉和模式

识别、图像处理中一个非常重要的基础操作，有着广泛的应

用领域。

目前已有很多文献介绍连通标记算法。文献将已有标记

算法划分为两类：一类是局部邻域算法，这类算法有多种不

同形式，基本思想是从局部到整体，要逐个检查每个连通成

分，对每一个都要先确定一个“种子点”，再向周围邻域扩

展地填入标记；另一类是“分而治之”算法，基本思想是从

整体到局部，先确定不同的连通成分，再对每一个用区域填

充方法填入标记。例如，采用区域分割方法或者轮廓追踪方

法，都可以区分出不同的连通域。两类方法都很难避免对图

像做多趟扫描，因此一般都效率不高。文献首先采用标记矫

正来减少图像扫描次数，

然后再对标记采用

RLE

游程编码来

提高合并效率。这种改进算法对大多数形状目标可以在一次

扫描中完成像素的标记，但是该算法不能对所有复杂的连通

形状

(

如分叉

)

采取一种通用方式处理，对于不同分叉方向只

能采用不同扫描方式来处理，不具有普遍性。另外还有一些

文献中介绍连通标记算法只适合标记圆形、矩形等规则的形

状，或者不能识别大量数目

(

大于

100)