边界跟踪自动机3篇

边界跟踪自动机3篇

边界跟踪自动机第1篇

边界跟踪属于图像分割技术的范畴，是图像工程中一个有

实际应用的图像技术，受到人们广泛的重视和研究［1］。在图像

处理与模式识别中，链码是图像处理、目标分析和图像压缩等

图像研究中的一个重要工具，H.Freeman创造了二值图像的链

编码表示方法［1］o在Freeman之后已提出了多种链编码方案。

Bribiesca则对顶点链编码做了系统的研究并做了推广［3］,许

多实际的应用都使用了链码，Yuan和Suen提出了一个从一系

列链码中提取直线的0（n）级算法［4］,Tang在关于离散格林

函数的论文中给出了利用Freeman链码计算图像几何矩的算法

［5］。文献［6］和文献［7］分别给出了利用顶点链码计算图像区域

面积和探测表格倾斜角度的算法。

利用链码分析和识别图像的前提是获得图像区域边界的链

码表示，所以边界跟踪和链码抽取一直是人们研究的热点之一

［8,9,10,11,12］。

传统边界跟踪方法大致分为两类，一是基于像素的边界跟

踪方法［8］,另一是基于边过程的边界跟踪方法［12］。基于像素

的边界跟踪在追踪复杂区域边界时会发生漏追踪或重复追踪的

错误，即使给出了解决办法，处理也很复杂，Ren采用了两种

标记色分别标记边界像素和与边界近邻的背景像素，来解戾漏

追踪和重复追踪的问题［10］。吴立德和林应强给出了基于边过

程的围线追踪算法和围线的树结构的生成算法［12］。

本文定义了八近邻图像的边界跟踪自动机，通过自动机的

输出获得区域边界的顶点链码，借助辅助矩阵，自动机跟踪图

像所有区域边界的同时，获得图像围线的树结构。

1图像边界的顶点链码表示

Bribiesca提出了用边界像素的顶点来标记区域边界的方

法［3］。对于正四边形点阵上的图像，可以有三种不同性质的顶

点，如图1右图所示，分别用代码1,2,3来标记。按逆时针

或顺时针方向沿着图像边界像素的顶点行走一周，依次记录图

像边界像素顶点的代码，就得到图像边界的顶点链编码序列。

图像的边界可以被顶点链码唯一确定。图像边界的顶点链码序

列的表示为：{(x0,y0)/ef/cOcicn~l},其中(xO,yO)

是顶点链码的起始点，ci£{1,2,3}为边界像素顶点的代码，

e->E{0,1,2,3}为初始行走方向，如图1左图所示。

图1右图所示的图像的顶点链码表示为：

{(uO,vO)/0/121321312131132321131313113123}

(uO,vO)是图像边界像素的顶点P的坐标，初始行走方向

为Oo

2边界跟踪自动机

自动机由五元组组成：输入集合，输出集合，内部状态集合,

状态迁移映射，输出映射。定义自动机的内部状态集合如图2

所示。

图2表示的自动机的内部状态决定了自动机行走方向，状

态A、B、C、D对应的行走方向分别为0、1、2、3o

定义四像素模板，如图3所示，令P1的坐标为(x,y),

那么P2、P3、P4的坐标分别为(x+1,y)、(x,y+1)和

(x+1,y+1)o

用四像素模板作为自动机的输入。图4给出了图像边界上

的所有自动机的输入类型。图5给出了自动机状态A的迁移映

射及其输出，其中四像素模板为自动机的输入，右侧为下一时

刻自动机的状态，右侧的数字为自动机从当前状态迁移到下一

状态的输出。自动机的输出就是自动机经过边界像素顶点的顶

点链码。

用图3所示的四像素模板按从上到下、从左到右的顺序遍

历图像时，遇到的第一个边界像素时只可能出现图6所示的两

种情况。对于图6(a),我们设定自动机的初始内部状态为D,

对于图6(b),我们设定自动机的初始内部状态为A。

一旦确定了区域边界上自动机的初始位置和初始行走方向，

自动机就可以根据图5所示的迁移映射沿区域边界行走，跟踪

该边界，当自动机回到初始位置时停止，记录自动机的输出就

获得了区域边界的顶点链码。自动机沿区域边界行走可以体现

为一个四像素模板沿区域边界移动。表1给出了四像素模板随

自动机行走方向的坐标增量映射关系。

3自动机跟踪所有边界并生成围线树结构

对于区域边界像素顶点P,用cp表示点P的顶点链编码,

用ep表示自动机在点P的行走方向。对于八近邻图像，定义区

域边界的左右上下顶点如下：

定义1对于顶点P,如果cp=2andep=3或者cp=land

(ep=0orep=3),那么称点P为左顶点,如图7所示。

定义2对于顶点P,如果cp=2andep=l或者cp=land

(ep=lorep=2),那么称点P为右顶点，如图8所示。

定义3对于顶点P,如果cp=2andep=2,那么称点P为上

顶点，如图9(a)所示。

定义4对于顶点P,如果cp=2andep=0,那么称点P为下

顶点，如图9(b)所示。

创建大小为(IWidth+l)X(IHeight+l)的int型的辅助

矩阵M,这里IWidth和IHeight分别为原图像的宽和高。

要利用边界跟踪自动机跟踪图像所有的区域边界，并生成

围线树结构，要解决发现新边界、避免边界的漏追踪和重复追

踪及生成围线树结构的问题。我们通过在矩阵M上标记边界的

上下左右顶点来实现。以下分别给出具体实况的方法。

定义围线类如下：

ClassCLayer{

intm_direction；〃顶点链码的初始方向

intm_x；〃顶点链码的起始点坐标的x分量

intm_y；〃顶点链码的起始点坐标的y分量

CStringm_sChaincode；〃图像区域边界的顶点链码序列

CArray<CLayer*,CLayer*>mLayerlist；〃该围线所包

含的子围线的围线类指针数组

CLayer*m_pParent；〃包含该围线的父围线类指针

);

•跟踪图像所有边界并生成围线树结构的算法

第一步：给原图像增加一圈背景像素，并创建辅助矩阵M,

初始化为0,初始化边界跟踪顺序中间变量layerCount为10,

初始化父围线指针变量pParentLayer=NULL,初始化链码树的

根指针变量root,定义围线类中间数组变量layerArrayo

第二步：用图3定义的四像素模板，按从上到下，从左到右

的顺序遍历增广图像。

for(inti=l,i<IWidth；i++){

pParentLayer=root；

for(intj=l,j<lHeight；J++){

if(M[i][j]>=10){

〃四像素模板所在位置是区域边界，且区域边界已被跟踪

过，

〃重新设定父围线类指针pParentLayero

〃根据矩阵M在该顶点的取值，从围线类数组取出该围线

的指针pLayer,

第三步：设定变量父围线的值。

pLayer=layerArray[M[i][j]];

if(pLayer==pParentLayer)

pParentLayer=pParentLayer->pParent；

elsepParentLayer=pLayer；

)

else{

第四步：启动边界跟踪自动机跟踪区域边界，并标记矩阵

如果当前位置满足新发现边界判断条件，那么，启动自动

机，跟踪该边界，抽取该边界的顶点链码。layerCount增加1,

当自动机经过边界上顶点为上下顶点时，则在矩阵M上标记值

2,对边界的左右顶点，在矩阵M上标记layerCount,把该围

线类指针赋值pParentLayer,并把自己加入到父的子队列中。

)

)

)

新发现边界判断条件：

(1)当模板满足图6(a)时，且矩阵M在该点的值为0。

(2)当模板满足图6(b)时，且矩阵M在该点及其该点的

右边和下边相邻的点的值为0o

4实验结果

图10为放大并显示网格的原始图像，利用本算法获得的区

域边界的顶点链码及围线树结构如图11所示，其中上箭头指向

父围线，下箭头指向子围线。

5结束语

本文给出了八近邻图像的边界跟踪自动机，通过自动机的

输出获得边界的顶点链码，在自动机跟踪图像所有边界的同时，

生成围线的树结构。该算法有以下特点：(1)自动机能正确跟

踪任意形状的图像区域，没有重复跟踪、漏跟踪和破坏连通性

现象；（2）能获得边界的顶点链码表示；（3）算法是线性的；

（4）算法还给区域轮廓的树结构。算法生成的围线树结构是以

顶点链码表示的围线类为节点的双向指针树，本文获得的围线

树结构，通过节点的父指针和子围线队列，可以直接获得围线

的父围线和子围线的顶点链码。

根据区域的外边界顶点链码和内边界顶点链码，利用相应

的区域填充算法就能提取想要的连通区域，另外通过链码转换

算法[13],还可以得到区域边界的其他链码表示及其树结构，

所以本文提供的算法具有一定的用途。

基于边界跟踪的红细胞分割与计数第2篇

随着信息技术的发展，数字图像处理技术作为一种非常有

效的手段越来越多的应用于细胞图像的研究中，在一定程度上

可提高工作效率和检验精度。本文针对已经获得的红细胞显微

图像，进行了分割和计数的算法研究，并在Matlab软件中进行

了仿真，获得了比较好的实验效果。

1细胞图像的预处理

将显微图像从RGB空间转换到HSI空间后，在饱和度高的

区域，H量化细，采用色调H的阈值进行分割；在饱和度低的区

域，H量化粗无法分割，但由于此时比较接近灰度图像，因而

可采用强度I的阈值进行分割，最后对分割后的图像合成。这

种方法利用了颜色信息，有效的获得红细胞区域。对于合并后

的红细胞区域图像，采用大津法即可得到红细胞的二值化图像,

如图1所示。

2红细胞的分割

从图1(c)中可以看出，二值化后的细胞图像中重叠和粘

连情况比较严重，针对此问题，本文采用边界跟踪的分割3方

法且进行了相应的改进进。

本文的边界跟踪算法是按照从左到右，从上到下的顺序搜

索目标，设序列数组为Ko首先从左上方开始搜索第一个目标

像素点，设为kO,则像素kO是该区域最左上角的边界像素，

也就是搜索的起点，设定搜索方向按逆时针，八邻域方向搜索。

kO设置为跟踪标志，并将kO做为序列数组的第一个元素插入，

按逆时针方向搜索下一个目标像素，并设为ko如果找不到，

则k为孤立像素区域;若k等于搜索起始边界像素kO,则按顺

序继续判断其它邻近方向上是否还有未跟踪到的边界像素，若

没有，则已回到起始点，算法结束。序列K中的边界像素点组

成一条封闭区域，将目标区域包围在内。在实验过程中，为了

提高边界跟踪的效率将搜索方向做了相应的改变。设搜索方向

变量为M,若当前M在斜角方向上，则更新M=(M+4+2)/8,否

则按照M反向方向搜索，经实验得出，运用这种方法，每跟踪

一个边界像素点只需要检测其邻近的3个像素，在一定程度上

提高了搜索速度。该基于八链码的边兄跟踪算法，可以一次扫

描获得物体边界点序列以及边界链码信息，为后续分割做好了

准备。

对于凹陷特征有明显的重叠、粘边细胞区域的分割，引入

一个概念：最短删除路径。所谓最短删除路径，是指从目标区域

某一个边界像素出发.通过区域内部，到达另一个边界像素的

最短距离。用所需要删除的像素数来衡量这一路径，用该路径

将目标区域分割所需要删除的像素数是最少的。

所以在八连通边界跟踪过程中，如果区域的删除路径的宽

度小于等于2个像素时，则跟踪过程会第二次遇到原先检测过

的边界点。如图2所示，当八连通边界跟踪检测到kl3和kl4

时，会分别遇到已检测过的边界像素点k6和k5。一般情况下,

这正是细胞的重叠、粘连处所在。如果将跟踪获得的边界序列

点删除掉，则重叠、粘连将在此处分裂为两个细胞。以此类推,

即使两个细胞在粘连处的最小删除路径大于2个像素，只要图

像中的细胞满足类圆的凸集特性，则细胞重叠、粘边处必然会

有凹陷的情况，因此，只要等宽度地不断跟踪、删除区域边界

像素，则重叠、粘连细胞最终会分裂。

3红细胞的计数

由于分割后的一幅图像内存在多个目标区域，为每个目标

区域分配相应标号的工作被称为标记，标记结束时也就同时完

成了计数。标记的实质工作就是检查各像素与其相邻像素的连

通性，然后对连通区域进行计数，进而实现目标的自动计数。

二次扫描标记法只需要扫描两次即可完成整个的标记，如

图4所示为二次扫描标记算法示意图：

设图像的目标区域灰度为0,背景区域灰度值为1。第一次

扫描结束后，所有灰度值为0的像素点都已经被标记过了，但

是有些标记是等价的。在进行第二次扫描时，首先要根据等价

对数组整理出等价关系，然后根据等价关系对目标区域进行重

新标记。在第二次扫描结束后.所有灰度值为0的目标区域都

被赋予了不同的标记值，据此就可以将目标区分为不同的连通

区域。得到不同的连通区域的数目就是相应细胞的个数，即完

成了细胞的计数。

4结论

在MATLAB中分别对基于凹点算法、分水岭算法和本算法进

行了分析对比。其中基于凹点算法的漏识数目为26,识别效率

为87.9%；基于分水岭算法的漏识数目为17,识别效率为92.1%；

本文算法的漏识数目为11个，识别效率为94.5%0整体上看，

本文算法在计数准确度和计数速度上都有明显的优势。

摘要；在红细胞的分割与计数系统中，针对重叠、粘连细

胞在分割时凹陷信息不完备以及在分水岭算法中不能实现真正

的距离变换问题。本文从细胞的边界入手，用基于边界跟踪的

方法来实现重叠、粘连细胞的分割算法并做了相应的改进。实

验过程中引出了“最短删除距离”的概念，且获得了良好的分

割效果。在分割完毕后对分割的细胞进行了计数研究。在顺序

标记法的基础上提出了二次扫描标记法，实验结果良好。

关键词：边界跟踪，粘连细胞分割，二次扫描标记，细胞计数

参考文献

［1］秦红星，蔡绍皙.彩色血液细胞图像的分割［JL中国血

液流变学杂志，2003(13)：3.

［2］陆建峰.重叠细胞图像分享算后的设计［J］.计算机研究

与发展，2000,2,2.

［3］李盛阳.医学细胞图像分割与分析方法研究［D］.山木科

技大学,2003.

[4]IstvanCseke.Afastsegmentationschemefor

whilebloodcellimages[J].PatternRecognition,1992,3

(3)：530-533.

边界跟踪自动机第3篇

针对图像几何参数的测量，人们做了大量的研究工作。在

文献［4］中，是研究在定量金相分析系统开发过程中所需的多目

标边界追踪算法，利用Freeman码提取晶粒的数量、面积、周

长、形状因子等特征参数。文献⑸中提出的方法，利用

Freeman链码矢量分析，对边界像素标注综合处理，再进行边

界像素坐标加权求和计算，求得目标面积。该方法实现简单，

结果准确，但该方法是对单通区域的面积计算方法，但不能测

量多目标区域。

针对上述问题，本文提出了先用canny算子提取目标边缘,

再采用八邻域跟踪目标区域的几何参数测量方法。该方法能较

好的抑制图像噪声、边缘跟踪速度快、计算方法简单、测量精

度较准确。

1边缘检测

图像处理中，经典的边缘检测方法有：log检测算子、

sobel检测算子以及canny边缘检测算子。本文采用canny算

法的边缘检测算子。canny边缘检测算子能保持边缘连续性，

同时也能很好的抑制图像中的干扰噪声，得到比较完整的目标

边缘。如图1(a)是经CT扫描得到的发动机切片，利用多种

检测算子检测提取其边缘，从下图(1)可知，canny算子的检

测结果比其他检测算子更好，能较好的抑制图像噪声，获得连

续目标边缘。

2八邻域跟踪

常用的对边缘轮廓坐标点跟踪的方法有Freeman链码法扫

描线轮廓法、八邻域边界跟踪法等。Freeman链码，首先定义

像素周围的八邻域方向点，并根据链码的方向对轮廓跟踪，该

方法跟踪效率差、耗时长。扫描线轮廓法通过逐行按列对图像

进行扫描，并记录下扫描到的行列坐标，此方法扫描到的轮廓

坐标比较杂乱、排列无序，一般不用此方法做跟踪测量。本文

在canny检测得到目标边缘的基础上，采用八邻域轮廓跟踪方

法对目标边缘进行轮廓跟踪。

首先定义中心像素的八个邻域及其分别对应的八个方向，

为了对目标区域边界进行编码，首先设定目标区域为二值图象,

设目标边缘为“0"，背景为T.

选如图2(a)为目标边界，对其作八邻域跟踪。若不采取

相应的措施，经过八邻域跟踪后，都只能跟踪得到最外层的轮

廓坐标点，如图2(a)所示，必须采取相应的措施使得八邻域

算法能跟踪得到图像中的多条轮廓。在此，采用的办法是：每当

八邻域跟踪完一条轮廓后，将该轮廓上的坐标点及其周围的坐

标点置为背景色，如图2(b)所示。

3周长和面积的计算

常用的面积讦算方法有像素累加法，即累加该坐标区域内

的像素点数目作为目标区域的面积；同时，对边缘像素点做加权

累加得到目标区域的周长。但该方法计算误差较大、耗时长，

为了进一步提高测量精度。本文采用格林和欧式距离公式分别

计算目标区域的面积S和周长L。

欧氏距离公式为：

格林公式为：

经离散化后，(2)转化为：

4仿真实验结果与讨论

为了验证本文测量方法的测量精度，在256X256的正方形

区域内构造半径分别为100像素和50像素的仿真圆。如图3

(a)所示大圆面积理论值为S=冗*(D/2)2=31416(pixel2),

周长理论值为L=n*D=628.3185(pixel)o小圆理论面积为

7854(pixel2),周长理论值为314.1593。采用本文的八邻域

跟踪算法对该仿真圆边缘进行跟踪，得到一系列的有序边缘坐

标点，图3(b)所示，最后计算出仿真圆的周长和面积，如表

lo

从表1可知，本文所用方法测量精度较高，测量误差较小，

能实现复杂多封沃区域几何尺寸的测量。

5实际工件尺寸测量

本实验以实际的圆形塞规为测量对象，验证本文测量方法

对实际工件的测量精度。该测量对象是经工业CT扫描得到的塞

规切片，扫描视场直径为151.46mm,切片大小为552X552,则

每个像素大小为151.46/552=0.2744mm/pixel,像素面积为

(151.46X151.46)/(552X552)=0.0753mm2,如图4所示，

其中，左下角塞规直径为21.82mm,内嵌两个直径为4.4mm的

小圆柱：右上角塞规直径为30mm.内嵌的大圆柱直径为11.98mm。

如：表2、表3分别是塞规面积和周长测量结果，其中称

“利用canny检测提取得到切片边缘，在采用八邻域跟踪算法

获得边缘坐标点，并利用几何计算公式得到塞规面积和周长的

方法”为“本文测量方法”。

从表2、表3可知，本文测量方法可以有效的测量实际工

件尺寸，且测量精度较高，其中面枳的测量精度最高达到

0.0029,