（计算机软件与理论专业论文）基于链编码的棋谱识别算法研究.pdf

华东师范大学硕士学位论文基于链编码的棋谱识别算法研究 摘要 随着数字图像处理和模式识别技术的不断发展与成熟，图像的编码技术得到 了飞速发展，并以其优良的特性在图像处理领域得到越来越多的运用。 本文指出了原顶点链编码算法在标定的时候存在的一些问题：在某些情况下 会漏标定链编码。本文接着提出一种新的顶点链编码标定方法及其改进方法解决 了这个问题。创新之处是通过使用边缘矩阵的结构改进了标定的方法，提高了算 法的可靠性，同时又没有牺牲算法的效率。接下来，本文在新的链编码基础上作 了一系列应用：嵌套结构分析、填充、区域统计。并且和同类算法相比，有较高 的效率。 另外，本文又将新的顶点链编码技术应用到围棋棋谱识别领域。在市场上， 有较大的需求把传统的物理介质棋谱转换为电子棋谱，但现今却没有成熟且广泛 使用的方法。 本文首先在分析了棋谱识别问题，用顶点链编码作为主框架，辅以f r e e m a n 链编码、投影法等其他模式识别技术来对棋谱进行识别。本文提出的算法，经过 实验，比市场上现存的产品在效率上和效果上有较大改进。 本文前半部分研究对象是通用算法，后半部分是在棋谱识别这个具体领域的 应用。前半部分是后半部分的基础。 关键词：链编码、区域统计、填充、围棋棋谱识别 华东师范人学硕十学位论文 基于链编码的棋谱识别算法研究 a b s t r a c t t h et e c h n o l o g yo fc o d i n gf o ri m a g eh a sar a p i dg r o w t hd u et ot h ec o n t i n u a l g r o w t ha n dm a t u r a t i o ni nt h ef i e l do f d i g i t a li m a g ep r o c e s s i n ga n dp a t t e r nr e c o g n i t i o n a n di ti su s e dm o r ea n dm o r ei nt h ef i e l do fd i g i t a li m a g ep r o c e s s i n gb e c a u s eo fi t s g o o df e a t u r e s t h i sp a p e ri n d i c a t e st h a tt h e r ea r es o m ep r o b l e m sw h e no l dv e r t e xc h a i nc o d e l a b e l i n ga l g o r i t h ml a b e l st h ec o n t o u r so fr e g i o n s s o m e t i m e so l da l g o r i t h mm a ym i s s s o m eo fc o n t o u r s s ot h i sp a p e rp r o p o s e san e wl a b e l i n ga l g o r i t h mt os o l v et h i s p r o b l e m ，a n dt h e ng i v e saf u , r t h e rs 0 1 i o nt oo p t i m i z et h i sa l g o r i t h mi ne f f i c i e n c y t h i sr 幢wm e t h o du s g sad a t as t r u c t u r en a m e de d g em a t r i xt 0i m p r o v et h eo l dm e t h o d e n h a n c et h er e l i a b i l i t yo fa l g o r i t h m ，a n dh a v eg o o de f f i c i e n c y a n dt h e n ，t h i sp a p e r a l s od e v e l o p sas e r i e so fa p p l i c a t i o n sb a s e do nv e r t e xc h a i nc o d e ：n e s t e da n a l y s i s ， r e g i o nf i l l i n ga n dr e g i o nc o u n t i n g c o m p a r e dt os i m i l a ra l g o r i t h m s ，t h e s ea l g o r i t h m s h a v eb e t t e re f f i c i e n c y t h i sp a p e ra l s ou s e sn e wv e r t e xc h a i nc o d et e c h n o l o g yt os o l v et h ep r o b l e mo f c h e s sm a n u a lr e c o g n i t i o n t h e r ea r es t r o n gd e s i r e st or e c o g l l i z ec h e s sm a n u a li np a p e r , b u tt h e r ea r e1 1 0m a t u r em e t h o dt of u l f i li t a f t e ra n a l y z i n gt h ep r o b l e mo fc h e s sm a n u a lr e c o g n i t i o n , t h i sp a p e ru s e sn e w v e r t e xc h a i nc o d et e c h n o l o g ya sm a i nf r a m e w o r k a n da l s ou s e sf r e e m a nc h a i nc o d e t e c h n o l o g y , p r o j e c t i o nm e t h o da n ds o m eo t h e ra l g o r i t h m st os o l v et h i sp r o b l e m b y a m o u n to fe x p e r i m e n t s ，t h ea l g o r i t h mp r o p o s e db yt h i sp a p e ri sp r o v e dt oh a v e o b v i o u se n h a n c e m e n tb o t hi nq u a l i t ya n de f f i c i e n c y , c o m p a r e dw i t ht h es i m i l a r p r o d u c ti nt h em a r k e t t h ef i r s th a l fo ft h i sp a p e rm a i n l yf o c u s e so nc o m n l o na l g o r i t h m s ，a n dt h e s e c o n dh a l fo ft h i sp a p e rm a i t l l yf o c u s e so ns p e c i f i cf i e l d ( c h e s sm a n u a lr e c o g n i t i o n ) t h ef i r s th a l f i st h eb a s i so f t h es e c o n dh a i f k e yw o r d s ：c h a i nc o d e ，r e g i o nc o u n t i n g ，r e g i o nf i l l i n g , c h e s sm a n u a lr e c o g n i t i o n - - ! v 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研究 成果据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经 发表或撰写过的研究成果对本文的研究做出重要贡献的个人和集体，均已在 文中作了明确说明并表示谢意 作者签钮生赴一日期：础 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版。有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅有权将学位论文的内容编入有关数据库进 行检索。有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定 学位论文作者签名：考砝 日期：幺牲 导师签名：力毛暾 日期：z 盟兰 华东师范大学硕士学位论文第一章绪论 第一章绪论 1 1 研究背景 1 1 1 顶点链编码及其应用背景 在图像处理及模式识别中，链编码是二值图像描述的一种常用方法。链编码 技术把二维图像的存储和处理变为一维链上的问题，能够不丢失信息，同时可以 较大程度地缩减数据存储空间，提高图像处理速度。另外链编码是获得图像几何 特征的重要手段，因此链编码是图像处理和图像识别中的一个重要工具。1 9 6 1 年f r e e m a n 提出了图像的链编码表示方法1 2 0 l 。此后，图像的链编码表示被大量应 用于图像处理和分析的各个分支领域中。迄今为止关于链编码理论和运用仍然是 个受关注的问题i l 击, 2 4 , 2 5 , 3 7 , 3 8 , 5 0 】。本论文的主要目的是研究棋谱的自动识别方法， 因此有必要首先研究链编码有关的算法，其中包括链编码的生成算法，连通体的 嵌套算法，区域填充和区域个数的统计算法等。 1 1 2 棋谱识别及其背景 近年来，文档识别现在正朝各个领域细分发展。除了传统的文字识别，也有 很多表格识别1 2 q 5 1 、乐谱识别1 1 和棋谱识别方面的工作。 棋谱是一种特殊的文本图像，它可以用来记录比赛赛事，也可以充当培训资 料等等。围棋棋谱被非常广泛地使用着。以往，围棋棋谱主要记录在纸张、丝绸 等物理介质上。近几年，随着计算机技术的飞速发展，出现了多种形式的电子棋 谱。 电子棋谱和传统的物理介质棋谱相比，有诸多优势。但现今还没有成熟且广 泛使用的方法将物理介质棋谱转化为电子棋谱。虽然市场上已经出现了支持围棋 棋谱识别的软件“b i g oo c r ”【4 引。它是本人唯一找到的商用棋谱识别软件。但 由于它识别速度过慢且对输入源要求过高，所以使用范围有限。目前主流的处理 方法就是依靠人手工打谱。 1 2 本文的主要工作 本文的工作由前后相继的两部分组成。前面的部分是为棋谱的识别目的而进 行的链编码相关算法的研究。包括改进了的链编码的标定算法，区域嵌套结构的 生成算法，区域统计的算法，和区域填充算法，最后一部分是对围棋棋谱识别所 华东师范大学颈士学位论文 第一章绪论 作的研究。 本文指出了原顶点链编码算法在标定的时候存在一些问题。为了避免出现漏 标定，我们设计了边缘矩阵，提高了边界标定算法的可靠性。接着我们研究了区 域嵌套结构的生成算法，区域的填充算法，和提出了一种基于区域边界跟踪的区 域统计算法。其中区域统计于同类区域统计算法相比，有较高的效率【3 2 】。我们发 展的填充算法在也比现有的种子填充算法嘲有较高的效率。 论文的后半部分是把链编码技术应用于围棋棋谱的识别。在对棋谱识别的问 题作了分析之后，我们以顶点链编码作为主框架，辅以f r e e m a n 链编码、投影法 等其他模式识别技术来对棋谱进行识别。 本文提出的算法，经过实验，比市场上的“b i g oo c r ”【4 s 】速度提高了很多 倍，并且对图像的质量要求比“b i g oo c r ”低。 1 3 本文组织结构和章节安排 本文共分七章，其中包括本章的绪论部分。整个内容结构安排如下： 第一章绪论部分，阐述了论文的研究背景，概述了论文所作的工作。 第二章详细鲍介绍了链编码技术和区域标定自动机。 第三章为了避免漏标定，提出带边缘矩阵的顶点链编码标定算法及其改进算法。 第四章提出顶点链编码在嵌套、区域统计以及填充三个方面应用的算法。 第五章介绍围棋识别问题的特性，提出了根据输入棋谱的质量将棋谱进行分类。 围棋棋谱的预处理工作，以及对围棋棋谱的其他实现方法的一些探讨。 第六章介绍以顶点链编码为核心的棋谱识别技术的详细算法。 第七章介绍棋谱识别算法的实验，包括开发环境和工具。 第八章总结全文的工作，对课题的发展进行展望。 本文前半部分( 第三章、第四章) 的研究对象是通用算法，后半部分( 第五 章、第六章和第七章) 是在棋谱识别这个具体领域的应用。前半部分是后半部分 的基础。 华东9 i | j 范大学硕士学位论文 第二章链编码及相关方法的介绍 第二章链编码及相关方法的介绍 2 1f r e e m a n 链编码和顶点链编码 h f r e e m a n 首先提出了二值图像的链编码表示方法。他同时提出了八方位链 编码和四方位链编码两种方法。八方位链编码的方法如图2 1 所示，以水平向左 方向的边为0 ，以o - 7 这8 个数字分别表示图2 1 中所示的八个方位。四方位的 链编码如图2 2 所示，在矩形点阵中，把区域的边界像素依次连接起来，以数字 1 ，2 ，3 ，4 标记，分别表示链的东、北、西、南四个走向i s 2 1 。 4、- ，。 。57 y 。y o 入r。y 2厶 o t2 356 7 8 图2 - 1f r e e m a n 八方位链编码( 右上角的小图是八个方位及其相应的链编码。图中的区域用八方位 链编码做了标定) f3 睦 另雾露矿拐科笏 b 夕 d ：1 2 2 3 2 3 3 3 4 3 4 4 4 4 4 x 4 1 1 2 2 2 1 2 1，：1 2 1 3 1 2 2 1 3 1 2 2 2 2 1 3 1 2 1 2 2 3 1 3 图2 - 2f r e e m a n 四方位链编码和顶点链编码 ( a 为原始酌连续图形。b 为矩形点阵c 是对原始圈形作了离散化后得到的区域边界。d 是图形边界编 码。e 为四个方位及其编码。f 是图形的顶点链编码g 是顶点链编码的三个元素及其编号。) - - 3 一 华东师范大学硕士学位论文第二章链编码及相关方法的介绍 链编码把二维图像的存储和处理变为一维链上的问题。对于大尺度的图像， 链编码可以大幅度地节省存储空间并提高处理速度1 1 8 - 2 4 。 在h f r e e m a n 之后又提出了多种链编码方案。e r n e s t ob r i b i e s c a 提出了顶点 链编码的编码方法，并对顶点链编码作了细致的研究嗍。在区域的边界上，沿着 边界像素的边行走，以相邻前后两个四方位编码的差加2 来标记顶点，就可得到 顶点链编码。 顶点链编码的编码方法是：先用某一种规则的单元格将图形铺满，从任意一 个节点开始，按一定的方向沿着图形边界运动，边界节点的顶点编码构成一个序 列，这个序列就是图形的顶点链编码。由于基本的数字图像是二维图像，对于全 同的多边形，只有正三边形、正方形和正六边形能铺满平面，因此可以有三种二 维图像，因此单元格可以是正方形、正三边形、正六边形。图2 3 具体提供了三 种点阵中的顶点链编码和编码规则。图中( a ) 图是正方形点阵上的顶点链编码， ( b ) 图是正三边形点阵上的顶点链编码，( c ) 图是正六边形点阵上的顶点链编 码，各个图形下面的数字串就是该图形的顶点链编码。图形上的箭头表示编码的 方向和起始点。 罄z 鹭4 1 2 1 3 2 1 2 1 3 1 1 3 3 2 1 l s l 3 1 1 2 3 2i d 2 2 4 2 2 2 1 5 s s 21 1 1 1 2 1 1 2 2 1 2 1 1 1 2 1 2 1 1 2 1 1 2 2 1 1 1 1 2 2 2 2 ( a )( b )( c ) 图2 3 顶点链编码 顶点链编码，简称为v c c ，即v e r t e xc h a l nc o d e 的缩写。顶点链编码是从任 意一个节点开始按一定的方向将图形边界上所有节点的顶点编码构成的一个序 列。因为图形边界是有限的、封闭的，所以顶点链编码实际上是一个环，与从哪 一个节点进行编码没有关系。因此，如果对图形进行旋转、映射变换，图形的顶 点链编码具有不变性，如图2 - 4 和图2 5 。 嘞毒 、， 1 l 勰1 2 1 3 2 1 2 1 3 1 1 3 3 2 1 1 3 l 31 1 2 3 2 1 2 1 3 2 1 2 1 3 1 1 3 3 2 1 1 3 1 3 ( a ) 图形和相应的v c c ( b ) 图( a ) 中图形的v c c 不随图形旋转而改变 图2 - 4 旋转独立性 - - 4 - - 华东师范大学硕士学位论文 第二章链编码及相关方法的介绍 嘞t lllt 1 k 1 1 2 3 2 1 2 j 3 2 1 2 1 3 j 1 3 3 2 1 1 3 1 s 1 1 2 3 2 1 2 1 3 2 1 2 1 3 1 1 3 ；3 2 1 1 3 1 3 ( a ) 图形和相应的v c c( b ) 图( a ) 中图形的v c c 不随图形映射而改变 图2 - 5 映射变换独立性 一般来讲，一个图形就是一个连通区域，连通区域分成单连通区域和复连通 区域两种。如图2 - 6 所示为连通区域最简单的情况，( a ) 是一单连通区域，( b ) 中黑色部分是一复连通区域。( a ) 图的单连通区域只有边界的一个顶点链编码序 列，而( b ) 中的复连通区域有内、外两个边界，因而有两个链编码序列。对于 更复杂的复连通区域，每个封闭的边界都对应一个链编码序列。 o ( a ) 单连通区域( b ) 复连通区域 图2 - 6 两种连通区域 图形的顶点链编码对于图形的标定是完备的，因此可以直接利用顶点链编码 而无需将图形转换到笛卡尔坐标系中来计算边界长度、图形的面积等。其中边界 长度的计算最为方便，它就等于链的长度。但区域面积的计算稍复杂。本文作者 所在的小组已经提出了从顶点链编码获得区域面积的一种简便方法1 。 2 2 顶点链编码的生成 一般来说，在数字图像的模式识别中待识别目标区域标定得越准确，则就越 容易提取目标的特征值和更好地对目标进行识别。顾国庆和许彦冰构造了一种区 域标定自动机1 2 5 - 2 6 1 ，可对方形点阵中的数字图像区域进行标定。该方法能方便地 得到区域边界线的顶点链编码。此后，顾国庆又推广了这一方案，构造了获得正 三边形点阵和正六边形点阵中二值图像顶点链编码的区域标定自动机【2 7 珊1 。自动 机的输入是自动机和区域边界的相对位置，自动机的输出就是顶点链编码，其结 果实现了区域边界顶点链编码的自动生成。 在二值图像中，黑色的区域( 像素值为1 ) 与白色的区域( 像素值为o ) 由 封闭的边界相区分。因此二值图像中，区域边界的标定等价于区域的标定。对于 一个由边界线确定的区域，如图2 7 所示，以区域边界上的任一点为起始点，按 华东师范大学硕士学位论文 第二章链编码及相关方法的介绍 照一定的方向沿区域边界行走，当某一点的坐标和行走方向与起始点的坐标和起 始行走方向都相同时，则判定为回到了起始点。把行走的路径记录下来即可完成 对区域的标定。 图2 - 7 二维正方形点阵图像 图2 - 8 邻接方式 二维正方形网格空间( 即用正方形铺满的空间) 存在两种相邻方式：一种为 八近邻，认为每一单元格与其周围的八个单元格都相邻；另一种为四近邻，认为 每一单元格只与其上下左右四个单元格相邻。由于二维正方形网格空间存在邻近 方式上的歧义性，对于如图2 8 所示的区域，在八近邻方式中，由于认为两个黑 色像素相邻，所以图中只有一个区域，而在四近邻方式中，则认为有两个区域。 也就是说，邻近方式不同则区域标定的结果也不同。 八近邻图像区域的标定 本文中主要考虑八近邻的图像，因此首先考虑八近邻图像区域的标定。我们 规定自动机靠左行走。经分析自动机的当前位置、前一时刻的位置和边界点之间 的关系，则只有如图2 - 9 所示的四种位置关系。状态a ，状态b ，状态c 和状态 d 就是正方形点阵区域标定自动机的内部状态集合。 卣x咱p曰l 1 4tl_j _ d 圈2 - 9 四种位置关系 图2 - 9 中表示自动机的当前位置，箭头( 一t i ) 表示前一时刻光标的位 置，箭头方向表示行走的方向( 逆时针方向) 。状态a ，b ，c ，d 构成了自动机 的内部状态集合。 对于任一种位置关系，还需要分析光标点周围其余五个单元格是否空缺。自 动机当前位置附近各像素的占有情况就是自动机的输入。假设以状态a 为例来 华东师范大学硕士学位论文第二章链编码及相关方法的介绍 围弓口誉圈奇口邕 田弓田邕圈弓口邕圈弓圈苗田弓口蔷 1 2 1 5 t 圈奇田邕圈弓口蔷 ii 旦l 里llil j 匝口一_ l l l 叵圈 图2 - 1 0 八近邻图像状态映射和输出映射 上图中，大箭头左边是自动机的当前状态和各种输入，大箭头右边是自动机 下一时刻的状态，小方框内的数字串是作为自动机的输出的顶点链编码串。 华东师范大学硕+ 学位论文第二章链编码及相关方法的介绍 田园阴邕目哼口蓍 田考田誉口号口蚤 囝弓田誉口弓留蔷 ill2 illil 巨口_i l 匿圈 华东师范大学硕士学位论文 第三章带边缘矩阵的链编码标定算法 第三章带边缘矩阵的链编码标定算法 本章首先指出在标定图像时会遇到区域边界漏标定的问题，为此我们设计了 带边缘矩阵顶点链编码标定方法。然后考虑了提高标定方法的效率问题。 3 1 漏标定的问题 链编码在很多领域中得到了应用，因此完整地生成图像中各个区域边界链编 码是必要的。 由于像素是有“宽度”的，所以两条由像素组成的边界之间的相互关系往往 比较复杂，有可能出现两条链编码的某一段“相邻接”、“相重叠”或既“相邻接” 又“相重叠”的情形，如图3 - i 。 ： i ； 一r 一 一l ( a ) 相邻援( b ) 相重叠( c ) 既相邻接又重叠 圈3 - i 两条由像素组成的边界之问的相互关系 现有的一些链编码算法是只标定像素的。这类算法在标定复杂区域的边界 时，就只能参考有限的像素颜色信息，而难以掌握全面的像素之间的位置关系。 在某些情况下，算法可能出现错误漏标定或重复标定一些区域边界。 第二章中提到的顶点链编码使用运行方向判断等方法进行辅助判断，避免了 部分区域边界的漏标定。但是该算法仍只是参考有限的像素颜色信息，仍然不能 完全消除边界的漏标定。如图3 - 2 ( a ) ，有l 的方格代表黑色像素，空白方格代 表白色像素，黑色带箭头的线代表链编码及其方向。从拓扑结构来看，两个黑色 方框中应有两条链编码：一条是外框的内围链编码，逆时钟方向：一条是内框的 外围链编码，顺时钟方向。但从像素的占有角度上来说，图中所示的两条链编码 是完全一致的。因而原有的链编码标定算法只能标出一条链。这样就出现了一条 链丢失的情况。作为对比，如图3 - 2 ( b ) ，它和图3 2 ( a ) 有着一致的拓扑结构。 在原有的链编码标定算法中，由于标定的两条链不会占用相同像素，所以它们都 是可以区分的。不会出现一条链丢失的情况。在原链编码标定算法中，图3 2 ( a ) 和图3 2 ( b ) 有着一致的拓扑结构，却有着完全不同的标定结果。 - - 9 - - 华东师范大学硕士学位论文第三章带边缘矩阵的链编码标定算法 i 】i 1 l l1 l 】1 l il ll ll l 1 个 i i 、， i ll1li 图3 - 2 ( a ) 云失链编码的例子 3 - 2 ( b ) 对比：不丢失的情况 从上面的例子可以看出，出现漏标定的根本原因，是只参考像素颜色信息， 而没有考虑像素之间的位置关系。在链编码的标定的过程中，原有方法采用的是 标记像素点的方法。事实上所有标定像素的边界标定算法可能都存在漏标定的问 题。 为了解决这个问题，本文提出一种新的方法：基于边缘矩阵的链编码标定算 法。本算法标定时记录的是像素的边缘，参考的是像素之间的位置关系，这样就 可以保证不出现漏标定和重复标定的问题。 3 2 带边缘矩阵的顶点链编码方法 3 2 1 算法概述 为了方便叙述，我们先给出几个定义： 像素边缘是像素的边界。用正方形表示像素时，像素边缘即为像素方格的 4 条边之一。 像素边缘值用来指示该像素边缘是否存在黑自边界。如果某像素及与该像 素上方( 左方) 相邻的2 个像素同为白色像素，或同为黑色像素，则初始值为0 ， 不是黑自边界；否则初始值为l ，是黑白边界。 边缘擦除在进行区域标定时，经过该像素边缘后，将边缘像素值置o ，以 表示该像素边缘已被标定过。 边缘矩阵根据以上规定记录像素颜色和边缘情况的矩阵。边缘矩阵的矩阵 元是3 b i t ( b 2 b l b o ) 的数字，用来分别记录像素颜色和像素边缘情况： b 2 记录当前像素上方边缘是否是黑白边界，o 一不是黑白边界，l 是 黑白边界； b i 记录当前像素左方边缘是否是黑白边界，卜不是黑白边界，1 是 黑白边界： b o 记录当前像素的颜色状态，o 一白色，1 黑色。 肇东师范大学硕士学位论文第三章带边缘矩阵的链编码标定算法 边缘矩阵矩阵元所代表的像素颜色和边缘状态如下图3 3 所示。图中灰色表 示黑色或白色像素。图像下面的数字即为边缘矩阵中与中心像素对应的位置处的 矩阵元。 凹口， j 一口x 1 0 01 0 1l l o l l l 图3 - 3 不同矩阵元代表的像索颜色和边缘情况 边缘矩阵主要是为标定自动机的运行提供依据。首先根据输入图像初始化边 缘矩阵，将像素的颜色和黑白边界都记录在边缘矩阵中。自动机标定链编码时， 可以根据边缘的情况来启动、标定和生成链编码。同时，在标定自动机的运行过 程中，随时擦除边缘，以免边界被重复标定。 由于图像的边界像素不存在左方像素或上方像素，因此我们沿图像的外围增 加一圈像素，形成一个增广矩阵。并不是增广矩阵中所有的点都要被记录在边缘 矩阵中。如图3 4 ，表示边缘矩阵记录的像素和像素边缘的分布情况。图中含白 色三角形的方格代表图像中原有的像素，带灰色区域的方格是新增的像素。黑色 三角形的2 条等长的边就是该像素处需记录的像素边缘。 图3 4 边缘矩阵记录的像素和像素边缘的分布情况 3 2 2 标定算法的过程 算法的实现分两步： 第一步，初始化边缘矩阵，将图像上各像素的颜色和所有黑白边界的数据都 记录在边缘矩阵中。 华东师范大学硕士学位论文第三章带边缘矩阵的链编码标定算法 第二步，从边缘矩阵的左上方开始运行标定自动机，同时生成链编码并擦除 边缘，当到达边缘矩阵的右下上为止。 在链编码标定的过程中引入标定自动机，可以给算法的实现和运行效率的提 高带来很多便利3 3 】。本方法中也采用标定自动机，但和以前的算法不同，现在自 动机是在边缘矩阵上运行，这样就可以保证不出现漏标定的问题。 圈3 - 5 算法沉程圈 本文所提出的算法首先对图像中每个像素按照从左到右，从上到下进行扫 描。定义两个变量：c u r p o i n t 用来存放当前点，p r e p o i n t 用来存放先前点。扫描 时，碰到符合条件的情况，则启动标定自动机进行标定。启动标定自动机需要经 过如下判断步骤： 1 ) 如果c u r p o i n t 在黑白边界上，转至2 ) 。否则，退出判断，继续扫描下一 点。 2 ) 判断c u r p o i n t 是否是白点。本文中标定自动机被设计成只能在白点上启 动和运行，如果c u r p o i n t 是白点，转至3 ) 。否则，退出判断，继续扫描下一点。 3 ) 判断c u r p o i n l 周围的边界是否被标定过。如果已被标定过，退出判断， 继续扫描下一点，否则，转至4 ) 。 4 ) 判断p r c p o i n t 是黑点还是白点。如果p r e p o i n t 是黑点，则该链是白链。 而如果p r c p o i n t 是白点。则该链是黑链。这个黑链和白链会在4 1 中嵌套算法中 间用到。无论判断结果是黑链还是自链，都将会启动标定自动机对区域边界进行 华东师范大学硕士学位论文 第三章带边缘矩阵的链编码标定算法 标定。当前边界标定结束后回到外层循环继续扫描下一个像素点。 算法的流程图如图3 。5 所示。 这里只考虑八近邻图像区域的标定。我们规定标定自动机沿边界的右方行 走，即：在标定外围链编码时，顺时钟方向；在标定内围链编码时，逆时钟方向。 经分析标定自动机的当前位置、前一时刻的位置和边界点之间只有如图3 - 6 所示 的四种位置关系。状态a ，状态b ，状态c 和状态d 就是正方形点阵区域标定 标定自动机的内部状态集合。 田_ 田l团 1喇田田一 a b c d 田3 - 6 四种位置关系 图3 - 6 中表示标定自动机的当前位置，箭头( 一t i ) 表示前一时刻光 标的位置，箭头方向表示行走的方向。状态a ，b ，c ，d 构成了标定自动机的 内部状态集合。 对于任一种位置关系，还需要分析光标点周围其余五个单元格是否空缺。标 定自动机当前位置附近各像素的占有情况就是标定自动机的输入。我们以状态a 为例来构造标定自动机的状态迁移映射。图3 7 中，大箭头的左边是状态a 以及 各种可能的输入，箭头右边就是下一时刻标定自动机的内部状态，深色线代表图 像的边缘。由图中可以看出，标定自动机运行时，同时把图像的边缘擦除。 用圆圈图形表示的像素是相干像素，需要检查其是否被占据。不难由对称性 得到状态b 、状态c 和状态d 的状态迁移规则。容易看出这一运算是封闭的， 因此图3 7 是一个有效的标定自动机状态迁移映射。 在实际的操作中，光标表示边界标定标定自动机的行走方向。按照图3 7 的 方式，处理周围单元格的信息，利用状态图间的映射即可获得下一步的位置关系。 一直循环下去直到当前位置和起始点相同为止，这样就完成了沿区域边界行走一 周的动作要求。把行走的路线以顶点链编码的方式记录下来，就完成了对区域边 界进行标定的工作。我们把图3 7 这种表示区域标定标定自动机状态迁移映射和 输出映射的图称为区域标定标定自动机的基本图。图中假设坐标原点在左上角。 自动机运行时输出链编码，找到一条边界以后，以，儿j ) l h q c n - 。这样 格式存储的顶点链编码边界，其中( x o ，y oj 是边界标定的首点，pj 是该顶点链编 码边界的是首个行走方向，方向定义如图3 7 ，疗是链编码的编码数，c 是第f 个 编码，其中f = 1 , 2 ，3 。 华东师范丈学硕士学位论文第三章带边缘矩阵的链编码标定算法 圈弓口邕圈专口蚤 口两口邕舀两口蔷 留哼田酱醑专田篙 3 2 3 算法举例 图3 7 八近邻图像状态映射和输出映射 在链编码标定的过程中，对像素边缘进行标定会造成边缘矩阵值的修改，下 面以单链构成的连通区域为例，说明在标定过程与像素相对应的边缘矩阵值的修 改情况。对于单链外圈的标定过程演示如图3 8 所示；对于单链内圈的标定过程 演示如图3 - 9 所示。 图3 - 8 、图3 - 9 中的有1 的方格代表黑色像素，无l 的方格代表白色像素。 加深的黑线表示初始化边缘矩阵后，记录好的黑白边界( 很多段边缘值为l 的边 缘) 。在链编码标定的过程中，不断地擦除黑白边界。直到运行到图片的右下脚， 标定自动机才停止运行。 特别值得提出的，在图3 - 9 ( b ) 到图3 - 9 ( c ) 的状态变化，根据图3 7 ，标 定自动机是先擦除一侧的边缘，然后再擦除另一侧的边缘的。这和原顶点链编码 的标定算法是有显著不同的。 专 l lll ll1 ll1 lllll 1 11 山 ll1l l1l 1ll llllllll ( b ) 华东师范大学硕士学位论文第三章带边缘矩阵的链编码标定算法 l11l lll ll1 lllll1ll ( c ) 个 llll l11 lll l1llllll ( c ) llll lll 1l1 l l l l l l 1 l 图3 - 8 单链外圈的标定过程 lll1 l 七l1 1ll lllll1i1 ( a ) 1111 ll1 l 4 -l1 l1llllll ( c ) ( d ) llll ll l l411 1ll l l l l 1 ( b ) lll1 l 山 l 1 l ll l11lllll 图3 - 9 单链内圈的标定过程 一1 5 一 ( d ) 华东师范大学硕士学位论文第三章带边缘矩阵的链编码标定算法 特别地，对于3 - 2 ( a ) ，初始化边缘矩阵后，得到如图3 1 0 的图像。可以看 出，图3 一l o 的黑自边界有两条，所以标定也会有两次。这样就会 导到两条链编 码，而不会漏标定链编码了。 i l1l 1 lf l lf 11illl 1 1 】r l11l 111lil ll lill1lll 图3 - l o 图3 - 2 ( a ) 的边缘矩阵 3 2 4 算法效率的问题 以上的算法避免了区域边界漏标定韵闯题，因此需要进一步考虑的是提高算 法效率的问题。 在空间开销上，本算法由于采用了边缘矩阵记录像素边缘的情况，所以增加 了附加内存空间。初始化边缘矩阵，则增加了时间上的开销，也需要优化。 3 3 将边缘矩阵嵌入图片的顶点链编码标定算法 3 3 1 算法概述 本节中我们将考虑边缘矩阵边界标定算法的优化问题。为此我们需对上节中 引进的几个名词作新的定义。 像素边缘值初始值为0 ，在进行区域标定时，经过该像素边缘后，将边缘 像素值置为1 ，表示该像素边缘已被标定过。 标定边缘在算法进行区域标定时，经过该像素边缘后。将边缘像素值改为 1 ，以表示该像素边缘已被标定过。用这种方法可以防止重复标定。 边缘矩阵用来记录像素颜色和像素边缘的标定情况。矩阵元的3 个b i t ( b 2 b l b o ) 的意义为： b 2 记录当前像素上边缘是否标定过，卜未标定，l 标定过： b l 记录当蔚像素左边缘是否标定过，o 一未标定，l 标定过； b o 记录当前像素的颜色状态，o 一白色，l 黑色。 与上节不同的是，我们不需单独生成边缘矩阵，而是用原图像像素的值来记 华东师范大学硕士学位论文 第三章带边缘矩阵的链编码标定算法 录边缘矩阵。该矩阵可能有8 种值( 0 0 0 - - - 1 1 1 ) ，故在图像需要用8 种对应的记号 标记。本文把这些记号称为记号0 ，记号7 。我们规定，奇数记号都是黑色 像素，偶数记号都是白色像素。记号0 和记号1 分别是原始的白色像素和黑色像 素，实际上另外需要在图上标记的是记号2 7 六种记号。 初始的图只有未被标记过的黑色和白色像素，因此只有记号0 和记号l 。在 自动机标定边缘的时候，原来是擦除边缘，现改成标记边缘。标记边缘方法是在 像素上标上相应的记号。随着标定自动机的运行，图上将会被标上新记号。其他 的手续和3 2 中的方法类似。 3 3 2 算法举例 在链编码标定的过程中，对像素边缘进行标定会造成边缘矩阵值的修改，下 面以单链构成的连通区域为例，说明在标定过程与像素相对应的边缘矩阵值的修 改情况。对于单链外圈的标定过程演示如图3 - 1 1 所示；对于单链内圈的标定过 程演示如图3 1 2 所示。 3 3 1 提到算法需要在图上标记8 种记号。下图无数字的方格代表记号0 ，有 数字的方格就表示相应的记号。加深的黑线表示标定自动机标定的线，它是为了 方便说明，特地画出来的，实际上不存在。在链编码标定的过程中，不断标记黑 白边界。算法从图像的左上方像素开始执行，到图像的右下方标定自动机停止运 行。 善 l11 l l1l l1l lll1llll 55552山 l55x 1ll llll1l1l 山 5555 lll ll1 llllll1l ( b ) 55552 1 552 1552 1ll11l1l 2 气 ( d ) 华东师范大学硕士学位论文 第三章带边缘矩阵的链编码标定算法 x 个 75552 35 52 3 552 3l11l1ll 2 44 44 4 444 图3 1 1 单链内圈的标定过程 755 52 3 ”表示外接矩形之间最直接的包含关系。在q 集上时，“ ”则表示链编码 之间最直接的包含关系。 华东师范大学硕七学位论文第四章嵌套结构区域统计和填充 求两矩形之间的包含关系 如图4 1 所示，有2 个链编码的外接矩形。图4 1 ( a ) 是黑链的外接矩形及 其4 个顶点坐标，图4 1 m ，所以也有b ， m 。 有两种可能： ( 1 ) 6 ， w ， 6 l ，岛：以 ( 代表，无法区分括号之间的元素的包含关 系) 则有：b l ，b j ( w 【6 i 1 ，b i 2 ，6 雎】) b r ( ( ) ，【】代表链之间的包含关系) 同时把数组w i ，w 2 ，w m 中的w i 标记为已处理。 ( 2 ) b j l ，6 m b j k w f 6 f l ，6 f 2 ，以 则需从 6 。b j ：，b j k ) 确定最邻近的 嵋，现在可再执行如( 1 ) ，直到最后 一个。 重复以上手续，就找到链编码之间的嵌套关系。把每个链编码看成一个树节 点，就形成了个表示嵌套关系的树结构( 通常包含多颗树，即森林) 。 另外设立一个虚拟节点，文档节点，它包含所有节点。因为文档节点包含的 都是黑链节点。所以把文档节点定义成白链节点。 在实际情况中。绝大部分( 2 ) 类情况都可以化为( 1 ) 类情况，可以用外接 矩形方法快速地解决。但某些( 2 ) 类情况，出现无法理清括号中的黑链与白链 的包含关系的情况，即无法判定自链到底是被哪个黑链包含。如下图4 0 ( a ) 和 图4 3 ( b ) ，是2 种不同包含关系的图像。图4 - 3 ( a ) 中，链b 2 w ，；在图4 3 ( b ) 中，链b l w ，。但是它们可以有完全相同的外接矩形包含关系，如图4 3 ( c ) 。 此时就不能仅通过外接矩形的办法来解决这个问题，需要采用其他方法来进行判 断。 4 1 3 角度判断法 ( b )( c ) 圈4 - 3 难以判断的包台关系 本文中我们提出用角度变化法来处理不能用外接矩形进行判断的情形。 设有两条链a 、b ，求它们之间的嵌套关系。不妨设a 被b 包含。把标定自 动机行走的方向定义为链的方向。从a 链中选一个任意一点为初始点，以初始点 为原点建立坐标系，计算自动机沿曲线行走一圈的角度增量a 8 。在标定自动机 华东师范大学硕士学位论文第四章嵌套结构、区域统计和填充 沿曲线行走一圈的过程中，如果曲线所在的象限不变，那么角度增量j 不变， 即万= 0 。如果曲线所在的象限发生变化，那么角度增量引醣着发生变化。角 度增量艿变化的意义如下：标定自动机沿曲线从第一象限移动到第二象限、从 第二象限移动到第三象限、从第三象限移动到第四象限或从第四象限移动到第一 象限，角度增量为9 0 度，即, x 8 = 9 0 ；若是相反方向，角度变量6 为一9 0 度， 即占= - 9 0 0 。自动机沿链行走一周的角度增量应为a 艿= 0 。或6 = + 3 6 0 。如果 角度增量等于o o ，那么链不包围原点( 初始点) 。如果角度增量等于3 6 0 。，那 么链就包围原点( 初始点) 。 于是我们可以用根据标定自动机沿区域边界行走一圈的角度变量来判断标 定区域是否包围初始点。如图4 - 4 所示。计算标定自动机沿曲线行走一圈的角度 增量万的变化，其中阴影部分为标定区域，箭头代表曲线方向，实心箭头处表 示标定自动机行走的起始点，行走以前标定自动机处于第一象限。 、y 励 工 沥 、y 呖象、 勉矽 矗6 9 毋啦旷 6 = 孵( _ 9 国+ 孵9 睁噼噼咄 ( a ) 一，v 缪笏j 勉坳。j ( b ) i 6 = 9 毋9 啪西9 嘞6 矿矗6 = 9 毋9 毋9 回+ ( 一旧+ 一9 由+ ( 9 + 9 毋啦矿 ( c ) ( d ) 图4 - 4 判断标定区域是否包围初始点 因为表示区域边界的两条链不相交，于是如果一条链包含了另一条链的某一 点，那么它也一定包含了该链。所以用该方法可以判断a 被b 包含是否成立。所 以本方法可以用来判断两条链的包含关系。 华东师范大学硕士学位论文第四章嵌套结构、区域统计和填充 4 1 4 综合方法及效率分析 外接矩形法速度快，但在某些情况下不能运用，此时就需要调用角度法。我 们把当外接矩形法和角度法相结合，既保证了程序的适用性，也提高了算法的效 率。将外接矩形法和角度法结合起来，就可以得到一个在正确性和效率上都较好 的方法。 先用外接矩形对各条链进行判断，如果出现不可判定的情况，则调用角度判 断法程序予以解决。这样算法的正确性是可以保证的。而且对于绝大多数情况， 外接矩形法都是能判断的，因此算法总的效率相当高。 嵌套算法的相当一部分时间是用在计算外接矩形上。如果外接矩形的计算在 其他地方也需要用到，则这一部分计算时间在其他步骤里就可以省掉。这就相当 于提高了算法的效率。 4 1 5 嵌套算法实验 在对如图4 - 5 ( a ) 的图片进行嵌套分析后，得到如图4 - 5 ( b ) 的一棵树。 图4 5 ( a ) 嵌套连通体 4 2 区域统计 4 2 1 算法介绍 图舢5 ( b ) 嵌套树 区域个数对于图像的分析和识别也是一个有用的概念。表格和棋谱的识别 中，区域个数的统计，更是有着直接的作用。最近医疗图像的区域数统计也在骨 骼的诊断上得到了应用。因此有必要提高区域个数算法的执行效率。本节中我们 华东师范大学硕士学位论文第四章嵌套结构、区域统计和填充 将介绍我们发展的区域个数统计方法。传统的区域个数统计是通过区域填充方 法。我们则采用边界跟踪方法来获得区域的数目，因此我们的新算法大幅度地提 高了执行速