基于改进型像素标记算法的目标定位

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于改进型像素标记算法的目标定位范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：提出新的像素标记算法,与以前的像素标记算法不同，该算法首先对目标点进行分类,然后根据不同的标记规则对不同的目标点进行标记。该算法不仅在算法复杂度上有所减少,只需一次扫描就能完成目标的描述,而且能够得到目标的面积、重心和边界坐标等信息。该算法已经应用于带钢表面缺陷检测，具有快速、准确等特点。

关键词：图像处理; 二值图像; 像素标记; 目标定位

中图分类号：

TN911.7334; TP317.4

文献标识码：A

文章编号：1004373X(2012)05

0052

03

Objective orientation based on improved pixel mark algorithm

SONG Nan1, ZHAO Jing2

(1.Beijing Information Science and Technology University, Beijing 100101，China； 2.Xi’an University of Technology, Xi’an 710048, China)

Abstract：

A novel pixel mark algorithm is proposed and the algorithm is different. The novel algorithm frist classified the objective,and then marked different target according to different mark rules. The novel algorithm not only decreased the algorithm complexity, accomplished description of objective only one time, and gained the target area, center of gravity and boundary coordinates and other information. The algorithm has been used in the strip surface defects detection,and has the characteristics of fast speed and accuracy.

Keywords： image processing; binary image; pixel mark;objective orientation

收稿日期：20111021

基金项目：国家自然科学基金(61072151)；陕西省自然科学基金(2009JQ8007)

0 引 言

对二值图像中连通区域进行标记有两种比较实用的方法:像素标记算法\[1\]和游程连通性算法。游程连通性分析法是通过分析由连续扫描线得到的游程连通性来标记目标的方法。其条件是在扫描前已经形成了灰度相同的像素块即游程。像素标记算法与游程连通算法不同的是，它不需要事先对图像进行处理，就可以对二值图像进行标记，过程极为简便。考虑到实时性要求，本文只对像素标记法进行了研究。

近年来出现了一些改进的像素标记算法如扩展像素标记算法\[2\]、带标记校正的像素标记算法\[3\]、快速目标描述方法\[4\]、一种改进的二值图像的象素标记算法\[5\]、基于递归的二值图像连通域像素标记算法\[6\]、带标记矫正的二值图象连通域像素标记算法\[3\]、一种基于链表的二值图像像素标记改进算法\[7\]、基于等价对的图像连通域标记算法\[8\]、一种图像分割的快速目标描述方法 \[4\]。扩展像素标记算法需要进行两次扫描才能完成。带标记校正的像素标记算法对包含向上分叉的图形不能在一次扫描中完成标记。快速目标描述方法借用像素标记的思想确定目标的边界，但其算法较复杂，得到的目标特征信息较少。本文提出的算法只需要对图像进行一次扫描就能完成目标的描述，对于复杂形状的目标也能正确处理。通过存储目标中像素的坐标，不仅达到了像素标记的目的，而且得到目标的面积、重心和边界坐标等信息。该算法已经用VC实现，用于带钢表面缺陷检测。

1 典型的像素标记算法

下面介绍典型的像素标记算法。在对图像进行分割以后，得到了一幅二值图像，为了检测不同的目标区域，需要对灰度值为1的像素点进行标记，然后检查邻近像素间的连通性，将具有连通关系的像素点合并到同一个目标区域。考虑8连通的情况，根据以上建立的概念可按如下方法对图像进行标记：对图像逐像素扫描，假如当前像素的灰度值为0，就移到下一个扫描位置。假如当前像素的灰度值是1，检查它左方、上方、左上和右上和四个近邻像素(根据所采用的扫描次序，当扫描到达当前像素时这四个近邻像素已被处理过了)。这四个像素灰度值和标记的组合中有四种情况要考虑:

(1) 它们的灰度值都是0，给当前像素一个新的标记(根据已有信息,直到目前这是该连通区域第一次被扫描到)；

(2) 它们中间只有一个灰度值为1，把该像素的标记赋给当前像素；

(3) 它们的灰度值都为1且具有相同的标记,就将该标记赋给当前像素；

(4) 它们的灰度值都为1但具有不同的标记,就将其中的一个标记赋给当前像素并做个记号表明这两个标记等价。

在扫描终结时所有灰度值为1的点都已有了标记但有些标记可能是等价的。此时所需做的就是将所有等价的标记对结合，对各个对赋一个不同的标记。然后第2次扫描图像，将每个标记用它所在等价对的标记代替。

2 改进的像素标记算法

本文提出了一种改进型像素标记方法，该算法使像素标记在单次扫描中完成，而且能够得到目标的面积、重心以及边界坐标。在扫描之前，首先对图像进行扩展，使图像中的每个点都具有完整的8邻域。对于二值图像中的目标点，分成三种情况：第一种是开始点，它的左方、左上、上方、右上的点均为0；第二种是内部点，它左方的点为1；第三种是边界点，它左方的点为0，但其左上，上方，右上至少有一个点为1。

为了说明像素标记的过程，首先定义如下数据类型：

m：当前像素点的行坐标，n：当前像素点的列坐标；

E(m,n)：当前扫描像素点灰度值；

S(m,n)：当前像素点的目标标记；

Br(S(m,n))：当前像素所属标记的等效标记；

MS(m,n) (m,n)：M用来存储目标标记S(m, n)中像素点的坐标；

为了说明改进型像素标记算法的标记流程，首先介绍三种点的标记规则和有效目标标记的定义。

(1) 开始点标记规则

当遇到一个开始点时，将其标记记为1，同时等效标记也为1，将该点的坐标存入数组M1中。后面开始点的标记依次加1。

(2) 内部点标记规则

若当前点为内部点，该点的标记记S(m,n)等于S(m,n-1)，并将该点的坐标记入数组MS(m,n )。进一步判断，若上方为0，右上方为1，且右上方标记的等效标记和当前点的标记不同，就令右上方点标记的等效标记Br(S(m-1,n+1))等于S(m,n)，并将数组MS(m-1,n+1)并入数组MS(m,n )。

(3) 边界点标记规则

首先判断该点左上方是否为1，若为1，则当前点的标记S(m,n)等于S(m-1,n-1)。并将当前点的坐标写入数组MS(m,n )。进一步判断，若正上方为0且右上方点均为1，则令右上方点标记的等效标记Br(S(m-1,n+1))等于S(m,n)，并将数组MS(m-1,n+1)并入数组MS(m,n )。

若左上方为0，正上方为1，则当前点标记S(m,n)等于S(m-1,n)，并将当前点的坐标写入数组MS(m,n )。

若左上方为0，正上方为0，右上方为1，则当前点标记S(m,n)等于S(m-1,n+1)，并将当前点的坐标写入数组MS(m,n )。

(4) 有效目标标记的定义

对图像扫描完成后，找出那些没有被合并的标记，即自身的标记号与它的等效标记相同，这些标记的存储数组M中存储了属于该标记的所有点的坐标，根据这些坐标就可以计算出目标的边界、重心和面积。

该算法只用一次扫描就能达到像素标记的目的，而且三种目标点有各自的标记规则，这些规则定义了像素标记和标记合并的原则，在扫描完后，要判断哪些标记是有效标记，哪些标记被合并，同时计算出有效标记的边界、重心和面积。

3 改进的像素标记法验证

为了验证算法的有效性，本文对复杂图形的目标标记过程进行了分析，图1给出了一个复杂图形实例，该图形包含了二值图像中会遇到的大部分情况。

图1 复杂图形实例

下面就对图1中图形的像素标记过程进行说明：

(1) 从第一行进行扫描，像素点(1,3)满足开始点的要求，令其目标标记为1，同时目标标记1的等效标记为1，将该点的坐标存入M1中。像素点(1,14)满足开始点的要求，令其目标标记为2，同时目标标记2的等效标记为2，将该点的坐标存入M2中。

(2) 对第二行进行扫描，像素点(2,3)的标记与(1,3)点相同，同时将该点坐标存入M1中。像素点(2,5)是一个开始点，令其目标标记为3，同时目标标记3的等效标记为3，将该点坐标存入M3中，后面的像素做类似的处理。点(2,14)属于标记2。

(3) 对第三行进行扫描，根据边界点的标记规则，点(3,3)、(3,6)、(3,9)、(3,14)分别属于标记1,3,2。

(4) 对第四行进行扫描，像素点(4,1)满足开始点的要求，因此开始一个新的标记4，并令其等效标记为4，在点(4,2)处，目标标记1合并入目标标记4，使目标标记1的等效标记指向4。在带点(4,5)处，目标标记3合并入目标标记4，目标3的等效标记指向4。从(4,9)开始的点属于目标4。点(3,14)属于目标2。

(5) 第五行的点(5,4)、(5,9)、(5,11)均属于目标4，点(5,14)属于目标2。

(6) 第六行的点(6,2)满足开始点的要求，开始一个新的标志5，并令其等效标志为5，在点(6,3)处，目标标记4并入目标标记5，使目标4的等效标记为5，同时目标1和3的等效标记为4，故使目标1和3的等效标记指向5。在点(6,8)处由于目标4的等效标记指向5，不做合并，在点(6,13)处，目标2并入目标5，目标2的等效标记指向5，点(6,15)属于目标5。

(7) 根据标记规则，点(7,5)和点(7,13)属于目标5。

(8) 在点(8,1)处开始了一个新标记6，其等效标记为6，在点(8,4)处，目标5并入目标6，同时目标5的等效标记为6，考虑到目标1,2,3,4的等效标记为5，这里使它们的等效标记指向6，在点(8,12)处由于目标5的等效标记为6，故不做合并。

(9) 查看这六个标记的等效标记，只有第六个标记的等效标记与它自身序号相等，故图中只包含一个目标。

前面介绍了改进型像素标记算法，并分析了其有效性。下面采用本文提出的算法和轮廓跟踪算法、像素标记算法，分别对图2所示带钢图像中的三个缺陷进行定位，图像大小为768×280像素。

从表1,表2可以看出，三种方法找到的目标边界

坐标完全一样，而改进型像素标记算法的处理速度更快，在有实时性要求的条件下该算法更有优势。在缺陷区域定位之后，根据目标边界坐标就可以从原图中提取缺陷区域图像。

4 结 论

本文算法不仅在实时性上有优势,复杂度有所减小,而且通过实验证明在图像的缺陷区域定位之后,根据目标边界坐标就可以从原图中提取缺陷区域的图像。

参 考 文 献

［1］章毓晋.图像分割［M］.北京：科学出版社,2001.

［2］张新宇，刘广智，李建勋，等.一种图像分割的目标描述方法及实现［J］.系统工程与电子技术，2003,25(2):219222.

［3］张修军，郭霞，金心宇.带标记矫正的二值图像连通域像素标记算法［J］.中国图象图形学报，2003，8(2):198202.

［4］张庆，向健勇，赵小明，等.一种图像分割的快速目标描述方法［J］.红外技术,2004,26(6):8385.

［5］王亮,黄飞,冯少彤,等.一种改进的二值图像像素标记算法［J］.南京师范大学学报:工程技术版,2006,6(2):2325.

［6］徐正光，鲍东来，张利欣.基于递归的二值图像连通域像素标记算法［J］.人工智能及识别技术,2006,32(24):186188.

［7］李伟,何强.一种基于链表的二值图像像素标记改进算法［J］.科技风，2008(14)：5556.

［8］左敏,曾广平,涂序彦,等.基于等价对的图像连通域标记算法［J］.计算机仿真，2011(1)：1416.