图像轮廓的点坐标的提取方法及VC++编程实现

刘伟学

（赤峰学院 计算机科学与技术系，内蒙古 赤峰 024000）

图像轮廓的点坐标的提取方法及VC++编程实现

刘伟学

（赤峰学院 计算机科学与技术系，内蒙古 赤峰 024000）

本文介绍了一种基于位图图像轮廓提取与跟踪的算法原理，提出了基于该原理进行提取图像轮廓的点坐标系列的方法，并分析了应用该方法可能出现的问题及相应的解决办法，最后给出了该方法的VC++编程实现.

轮廓提取；轮廓跟踪；点坐标

1 引言

近年来，学者们提出了许多光栅图像（以位图为例，以下称位图）矢量化技术在CAD/CAM系统中的应用.如绗缝图案画稿自动生成系统、刺绣画稿自动生成系统等.位图矢量化融合了计算机图形学、数字图像处理、模式识别、软件设计等多学科的技术.在各种基于位图图像轮廓的画稿自动生成系统中，其位图矢量化的一般处理流程为：除去噪声，二值化，轮廓提取，矢量轮廓图形生成.图像的去噪与二值化方法直接影响后续处理中的轮廓提取效果的好坏.本文中对此不作讨论，并以经过去噪且以恰当阀值分割后的二值图像作为图像轮廓提取处理的输入，探讨在此基础提取轮廓的点坐标系列的方法和VC++的编程实现.

2 轮廓提取与跟踪的基本原理

轮廓提取的算法非常简单，就是掏空内部点.假设二值图像中黑色为目标，白色为背景，则如果源图中有一点为黑，且它的8个相邻点都是黑色时，此点即为内部点，应将其删除.因此该算法实际是对图像的各像素进行扫描，对于这里讨论的二值图像来说则只需考虑黑点.对图像中的每个图点，考虑其上、下、左、右的八个邻点，如果其全为黑，则说明该点为物体的内部点，可以去除（变为背景点：白点），否则保留.如果前面的去噪与二值化处理的效果理想的话，该算法提取图像目标轮廓没有什么问题，这里不作详细讨论.下面重点讨论在经过轮廓提取处理后得到轮廓图像提取点坐标系列的方法.该方法基于边界跟踪算法，故下面先对边界跟踪算法作一介绍.

在识别图像中的目标时，往往需要对目标边缘作跟踪处理，也叫轮廓跟踪.顾名思义，轮廓跟踪就是通过顺序找出边缘点来跟踪边界的.若图像是二值图像或图像中不同区域具有不同的像素值，但每个区域内的像素值是相同的，则如下算法可完成基于4连通或8连通区域的轮廓跟踪.为了叙述问题的方便，假设待处理图像为二值轮廓图像，即背景点为白点，轮廓点为黑点.对于不同区域具有不同像素值的图像，其处理方法类似，或者可先将其处理为二值图像再用如下算法进行处理.

2.1 按从上到下，从左到右的顺序扫描位图图像像素矩阵，寻找没有标记跟踪结束记号的第一个界起始点A0,A0是具有最小行和列值的边界点.注意：此时的边界点其实是图像的最左下角的边界点.定义一个扫描方向变量dir,该变量用于记录上一步中沿着前一个边界点到当前边界点的移动方向，按上述扫描第一个边界点的顺序，其初始化取值为：对4连通区域取dir=0,如图 1所示；对 8连通区域取dir=7,如图2所示.

图1 四连通区域方向示意图

图2 八连通区域方向示意图

2.2 按逆时针方向搜索当前像素点的3×3邻域，如果搜索到边界点（黑点）时，则将该边界点作为新的当前像素点，且更改搜索方向，其方法为：对4连通区域取(dir-2)mod 4,对8连通区域取(dir-2)mod 8；否则以原当前像素点为中心逆时针继续搜索，由当前搜索方向求下一个搜索方向的方法为：对4连通区域取(dir+1)mod 4,对8连通区域取(dir+1)mod 8.

2.3 如果搜索的下一个像素点等于第一个边界点A0或者越界，则停止搜索，结束跟踪，否则重复步骤(2)继续搜索.

2.4 由起始边界点沿着跟踪路径再到起始边界点构成的边界即为要跟踪的边界.

其中算法中（1）所采用的准则称为“探测准则”，其作用是找出第一个边界点；(3)中所采用的准则称为“跟踪准则”，其作用是找出所有边界点.

3 图像轮廓的点坐标系列的提取方法

运用该跟踪算法提取图像轮廓的点坐标系列就是要按边界跟算法中点搜索的顺序将边界点的坐标系列存储起来.运用上述边界跟踪算法提取点坐标系列还需考虑如下问题：

3.1 完成一次跟踪只能提取一段边界.对于有若干不连续的边界，必须重复跟踪，而对于已跟踪的边界必须去除.去除的可能办法有二种：一是边跟踪边去除，二是跟踪完一段后再一起去除.实验中发现第一种方法不可行，其原因是在边跟踪边去除边界点时，无法满足上述算法中（3）所述搜索终止条件.故宜采用第二种方法.

3.2 对于跟踪的边界点坐标须用一点坐标数组存储起来，点坐标系列顺序按跟踪顺序保存，这一顺序即是将边界图像矢量化为矢量图元的顺序.

3.3 边界点坐标的数据结构.因为边界图像可能有若干不连续边界，故记录这些不连续的边界点坐标通常有两种方法.一是采用链表的形式，链中每一结点两个字段：一个边界段的点坐标数组及该边界段的点数组成的结构体，指向下一个结点的指针.二是用线性表的形式，一个点坐标数组存储所有边界点的坐标，另用一个结构体记录边界点总点数，总段数及每段的坐标点数.对于这两种数据结构的选择取决于边界图像是否为最终目标图像边界，如是，则采用线性表的形式处理更容易；如不是，即后续处理中还需对边界进行修正，则采用链表的形式处理更方便.

3.4 对于非常少的点数的边界段的处理问题.通常这类边界往往是噪声形成的，应该在处理中去除.但也不尽然，在细节较为丰富的边界图像中，可能这些较少点数的边界段也是有用信息.故实验中采取人机交互的办法.通过对话框让用户根据不同特征的边界图像提供一个临界值来确定多少个点数组成的边界为噪声.

3.5 对确定为噪声的边界段去除办法.应根据边界点的数据结构作相应处理.

4 VC++程序实现

轮廓跟踪提取边界点坐标系列的算法函数TraceDIB()原型如下：

下面对其作简要说明.CsplitProc为类名，TraceDIB为该类的成员函数，函数输入为二值图像的句柄，输出有：轮廓总点数，总段数，轮廓点坐标以及各段点数.函数参数说明：hDIB为待处理的图像句柄，由此可访问到图像中各像素的灰度值；dwCountPints为图像轮廓的点数，为引用型变量，函数中对此变量的修改即是对所引用的变量的修改；dw-CountSg为图像的轮廓的段数（这里把根据上述轮廓跟踪算法结束时得到的轮廓段称为一段），也采用引用型变量，其含义同上；lpPoints为指向点坐标数组的指针，为指针型变量，函数中通过该指针即可访问到存放点坐标的数组；lpSg-Points为指向存放各段点数的双字型数组，函数中通过该指针可访问到存放各段点数的数组.函数实现方法简述如下：按上述轮廓跟踪算法不断跟踪图像轮廓：每跟踪到一个点时，记录该点坐标，轮廓点数增1；每跟踪完一段后，段数增1，数并记录该段的点数；直到所有轮廓点跟踪完毕.为了在轮廓跟踪过程中对某些少数点组成的图段（可能为噪声）去除，可在处理时提供对话框由用户设定噪声边界点数的临界值，这样既可去除噪声，又不至于将有用的细节丢失.如图3所示的源图像，经过该函数处理后，将其边界点坐标系列信息保存于文件中，将其重新绘制得到的边界图形如图4所示.可见源图像的噪声得到了去除，但同时也损失了一些边界细节.此时的噪声边界点数临界值为100，适当修改该值，可得到不同的处理效果.

图3 待处理的含有噪声的轮廓图

图4 提取轮廓点坐标后重新绘制图形

4 结论与展望

上述运用轮廓跟踪提取边界点坐标系列的方法通过实验表明在一定条件下是可行的.对于噪声与图像有用边界很分明的图像去噪效果很好，但对于图像细节与噪声难以分辨的图像去噪与保留细节是一对矛盾.对于边界中无交叉的情况提取点坐标系列无重复边界点，否则按此边界搜索算法将会有重复边界点.以上问题仍需进一步研究，如采用人工交互的办法去除噪声点，对有交叉点的边界应予以特殊处理，去除重复边界点等.

〔1〕高守传.VisualC++实践与提高－数字图像处理与工程应用篇[M].中国铁道出版社,2006.

〔2〕余学军，彭立中.二值图像曲线轮廓提取的新算法[J].中国图像图形学报，2002（3）.

〔3〕孙景荣，许录平.一种改进的图形矢量化方法[J].计算机工程及应用，2004（1）.

〔4〕刘安心，余跃庆，等.三维机器视觉测量系统图像边缘提取算法研究 [J].机械制造与自动化，2006，35(1)：101-103,106.

TP39

A

1673-260X（2011）03-0039-02