（计算数学专业论文）图像碎片自动拼接技术研究.pdf

j e 鏖至重点堂亟竺焦边塞 虫窒埴墨 中文摘要 摘要：图像碎片自动拼接技术是借助计算机把大量的不规则的图像碎片重新拼接 成初始图像的完整模型。这一问题在考古、刑侦、古生物学以及壁画保存等方面 具有广泛的应用。要从成千上万的图像碎片中找到相互邻接的图像碎片，并最终 拼接成完整的模型，没有计算机辅助是很难实现的。 本文对二维图像碎片的自动拼接问题展开研究，介绍了图像碎片预处理及图 像碎片拼合的理论与技术，并重点研究了图像碎片拼接的核心问题图像碎片匹配 算法。文中提出了种基于角序列的二维图像碎片轮廓匹配算法，用于获得图像 碎片最可能的拼接结果，并将该算法与多尺度空间结合，提高计算效率。与现有 的曲率序列匹配算法相比，角序列匹配算法不但有效地解决了图像碎片拼合过程 中的尖角问题，还提高了计算效率。最后，本文应用m a t l a b 程序设计，实现了图 像碎片的自动拼接。 关键词：角序列；轮廓匹配；图像碎片拼接 分类号：t p 3 9 1 a b s t r a c t a b s r r a c i 。： r e a s s e m b l i n gu n k n o w i n gb r o k e no b i t sw i t ht h ea s s i s t a n c eo fc o m p u t e rf r o ma l a r g ec o l l e c t i o no f i r r e g u l a ri m a g ef r a g m e n t sa r i s e si ns e v e r a lf i e l d ss u c ha sa r c h a e o l o g y , c r i m i n a l d e t e c t i o n , p a l e o n t o l o g y , c o n s e r v a t i o n ( m u r a lp a i n t i n g ) ，a n ds oo n i tw a s i m p o s s i b l ei ft h e r ew t w er i oc o m p u t e r st oa s s i s ti nr e a s s e m b l i n gt h e s et e n so ft h o u s a n d s o f r a n d o m l ys h a p e da n df e a t u r e l e s si m a g ef r a g m e n t s 2 di m a g ef r a g m e n tm a t c h i n gi sd e e p l yi n v e s t i g a t e di nt h i st h e s i s t h em e t h o d so f p r e t r e a l m e n ta n dr e a s s e m b l yo fi m a g ef r a g m e n t sa r ei n t r o d u c e d a n dw er e s e a r c hm o r e o ni m a g ef r a g m e n t sm a t c h i n gm e t h o dw h i c hi st h ec o r eo f i m a g ef r a g m e n t s r e a s s e m b l y am e t h o df o r2 dc o n t o u r sm a t c h i n gb a s e do na n g l e - s e q u e n c ei sp r e s e n t e di nt h i st h e s i s ， w h i c hc a l lb eu s e dt oo b t a i nt h eb e s tp a i r w i s em a t c h i n go f i m a g ef r a g m e n t s m u h i s e a l e t e c h n i q u ei su s e dw i t ho u rm e t h o dt oi m p r o v ec o m p u t a t i o n a ls p e e d c o m p a r e dw i t h e u l n a l l f f e s e q u e n c e ，i tn o to n l yr e s o l v e st h ep r o b l e mo fs h a r pc o l l l e l 瞎i nt h ep r o c e s so f i m a g ef r a g m e n t sm e r g i n g , b u ta l s oi m p r o v e sc o m p u t a t i o n a ls p e e d f i n a l l y , t h ei m a g e f r a g m e n t sa r er e a s s e m b l e dw i t hp r o g r a mo f m a t l a b k e y w o r d s ：a n g l e - s e q u e n c e ；c o n t o t i rm a t c h i n g ；i m a g ef r a g m e n tr e a s s e m b l y c l a s s n o ：t p 3 9 1 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：导师签名： 签字e t 期：年 月日签字日期：年月日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字日期：年月日 致谢 本论文的工作是在我的导师黄晓鸣副教授的悉心指导下完成的，在此衷心感 谢两年来黄老师对我的关心和指导。 在两年多的学习和生活中，黄老师给了我许多有益的指导和细致入微的关怀， 没有他的帮助，我根本不可能完成本文。黄老师严谨的治学态度，广博的知识， 精益求精的科研作风，敏锐的学术思想和忘我的工作精神极大的影响并鞭策了我。 更重要的是使我学到了许多治学和做人的道理，将使我受益终生。我将铭记黄老 师的教诲，努力工作，不断进取。 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业。 韭 廛 銮通太堂 亟 堂焦途童曼l 直 1 引言 1 1 研究背景和意义 图像碎片自动拼接技术的研究是一个有很大实用价值的课题。如，考古研究 中对破碎珍贵文物的修复，公安机关破案时遇到的破碎证物的修复等。图像碎片 自动拼接就是从许多散乱的图像碎片中，借助于计算机，通过特征匹配技术来识 别出相邻接的图像碎片，进而重现整个物体的原貌。 图像碎片拼接的方法很多，根据特征可以分为基于色彩、纹理、材质、轮廓 等图像碎片拼接；根据形状特征又可以分为规则图像碎片和不规则图像碎片的拼 接：根据空间特征还可分为二维图像碎片拼接和三维图像碎片拼接。 图像碎片拼接的主要工作流程可概括为以下三个步骤： ( 1 ) 对图像碎片进行预处理，即对物体碎片数字化，得到碎片的数字图像。 和( 2 3 ) 是从同一点按照相同方向( 逆时针) 对同一条闭合线采样的结果，故 而应该为相同的序列，即 己己一。己一：己。最。异己，b e 日昂) 和 qq i q 2 g 一g q ，+ i q 艉一，绒一：级。幺 一一对应。分析两个序列的下标变化可以看出， 当i + j = m + 0 = ( m 一1 ) + l 一= o + m = 朋时，逆时针采样的第，点和顺时针的 第i 点是同一个点。那么在匹配时，只需要将其中一个序列逆向处理就可以解决方 向所带来的影响。 后续的图像碎片取样序列的匹配拼合的研究工作中，涉及到方向性问题，均 按照上述的处理方法进行，不再单独说明。 7 3 图像碎片匹配理论与技术 图像碎片拼接技术的研究包括对图像碎片匹配算法、拼合算法等的研究。本 章将针对图像碎片匹配的理论和技术进行深入研究。 3 1 图像碎片复原模型 为了更好的讨论描述，我们将构建一个基于形状匹配的，由散乱图像碎片重 组复原的完整的图像碎片复原模式。图像碎片复原模型主要是以根据图像碎片边 缘提取的轮廓信息为基础的。在这里，首先需要定义两个实体模型，一个是对理 想图像碎片模型，另一个就是实际图像碎片模型。 3 1 1 理想图像碎片模型 理想图像碎片模型( 图3 1 ) 是指图像碎片重新拼接复原后的实体和原来的物体 完全一致，不存在缺损和误差，并且图像碎片的表面厚度为0 ，也就是说，原始物 体具有较好的光滑表面，该表面被一些无规则的0 宽度的线即理想碎裂线分割成 两块或多块理想图像碎片，同时理想图像碎片将原始物体的边界线分割成若干个 小的边界曲线。如果两块图像碎片共享同一段碎裂线，就称它们是相邻图像碎片， 认为它们是可以匹配的。 一个理想图像碎片的边界是一条理想的轮廓线，它是由多条理想边界线连接 而成。理想图像碎片的理想边界线可能是由于破碎造成的碎裂线，也可能是原始 物体边界线的一部分，三条及三条以上的图像碎片边界线的交点构成一个理想角 点。 原始边界线 图3 1 理想碎裂示意图 8 理想碎裂线 3 1 2 真实图像碎片模型 当然，理想图像碎片和理想轮廓线都只是抽象的说法，并不能给予绝对精确 的说明或是定义。事实上，由于诸多自然的或是人为的原因，如：细小图像碎片的 遗失，自然磨损，表面不规则性，边缘的毛刺、倒钩及拐边，以及数字化过程中 带来的视差、投影误差和采样误差等原因的存在，从图像或实物中提取出来的实 际轮廓线通常和理想状态有着一定的差别。正是由于这些差别的存在，两块相匹 配的图像碎片在复原重组过程中邻接关系的确证变得比较困难。 图3 2 给出了真实情况下图像碎片的碎裂示意图。下面结合该图对文中将要 涉及到的一些概念予以说明。 匹配 图3 2 真实碎裂示意图 实际轮廓线是图像碎片的边界线，是一条闭合的线( 如图3 2 所示的图像碎片4 的实际轮廓曲线) 。本文将轮廓线的一部分称为轮廓线段。如果有一对分掰位于两 个实际轮廓线上的轮廓线段在最大程度上具有相似性，则称该两个轮廓线段为一 对匹配轮廓线段，两个轮廓线段对应的一对图像碎片互为对方的匹配图像碎片， 两者共同构成一个匹配对。图中图像碎片2 的和图像碎片3 的加粗部分轮廓线段， 在最大程度上相似于理想碎裂曲线，故而称2 ，3 在该两段曲线段相邻接，互为对 方的匹配图像碎片，两者共同构成一个匹配对；该两段加粗轮廓线段称为一对匹 配轮廓线段：图像碎片2 的匹配图像碎片有l 、3 、4 。 由于诸多人为和自然的原因可能会导致图像碎片的遗失发生。在碎裂示意图 中本文把图像碎片的遗失分为两类：大图像碎片和小图像碎片的遗失。通常沿着 大图像碎片边缘由于破碎过程和磨损等造成的小图像碎片可以看成是噪音处理， 如图中遗失图像碎片2 。面对于遗失图像碎片l 这样的图像碎片，如果当其是噪音 处理的话，不符合实际情况，会给复原工作带来较大的误差，通常认为该图像碎 9 片不存在或是被遗失，此类遗失图像碎片将被单独处理。 3 2 图像碎片匹配准则 平面图像碎片的匹配应该满足以下准则：需要真匹配，去掉假匹配，除了完 整的圆和直线外最后的匹配的唯一性，匹配的顺序，规范性。 第一、需要真匹配。在两个图像碎片的边界匹配中，应该保持匹配的正确性， 为了达到这个目标，在匹配时，会遇到许多问题，其中一个很重要的问题就是误 差的控制，虽然匹配中误差确实存在，但是应该把误差控制在一定的范围之内， 如果误差超过了一定的范围，那么就小再是误差，而是错误。 第二、去掉假的匹配。在匹配的过程中，有许多似是而非的匹配，应该去掉。 否则会对最后的匹配结果造成破坏性的影响。 第三、除了整圆和直线以外，最后的匹配的结果具有唯一性。由于整圆和直 线具有特殊性，所以除此以外，最后的结果应该具有唯一性。因为我们是把图像 碎片重新匹配成一个整体，这个整体应该是破碎之前的原形，而原形只有一个， 所以应该保持最后匹配结果的唯一性。 第四、匹配的顺序性。在匹配查找中，图像碎片的同一段轮廓线段可能同时 和几段轮廓线段相匹配，在这种情况下，本文中选取匹配长度最长的轮廓线段作 为匹配轮廓线段，即最长匹配优先准则。 第五、匹配的规范性。原来的物体应该是一个具有规范形状的整体，如果匹 配出来的结果是一个乱七八糟的东西，那么匹配的结果就值得怀疑。 3 3 图像碎片匹配算法 轮廓线的特征串表示是匹配算法的基础。特征值的选取及计算直接影响匹配 的结果。同时，由于每块图像碎片是独立，其方向也是任意的，因此其轮廓线的 特征表示必须是旋转和平移不变的。图像碎片拼接问题是轮廓线的局部匹配，必 须采用局部边界描述符。由于角度在刚体运动下不变，并且是轮廓线上点的局部 描述，因此可以采用角度值作为轮廓线的特征串表示。 3 3 1 角序列匹配算法 利用轮廓检测方法，将轮廓线表示为平面上一列有序点集合： 1 0 j b 塞窑亟厶望亟堂鱼j 金塞国傻礁丘匹酲理论当莛苤 s = 僻= ，乃) i i = 1 , 2 ，n ) ( 3 1 ) 这里我们定义，轮廓线上点只的邻域半径：是指从点卑出发沿轮廓线逆时针和顺 时针，个像素点的范围。则，c + ，= ( 靠，y 。) ，0 = ( ，y ，) 是点只沿轮廓线的逆 时针和顺时针第，个像素点。( ，称为邻域半径，对于，的取值，我们可以根据图像 碎片的具体情况而定，一般在5 到1 5 之间，这样既可以有效的描述点只的局部角 度特征，又可以降低图像碎片数字化过程中产生的角度偏差。) 如图3 3 p i ， 、一一一，、_ 毋一 图3 3 轮廓上点的向量表示 设= 么& ，曷异，i - - - 1 2 ，以，又有耳瓦的坐标表示为瓯，一而，y i + ，一乃) ， 只只- ，的坐标表示为o 。，- - x i ，门。- y 1 ) 。则根据向量积 卑j 弓j 刊只只，i j 异j ，- ，l e o s _ z , “只墨， ( 3 2 ) 可碍 ：a ，c c o 。11 垒! 三量圣兰垒三兰! 坚丝些三些! ! 兰耋! 三些!( 3 3 ) o f + ，一一) 2 + ( y “，一y 1 ) 2 ( j ，_ ，一t ) 2 + o h - y f ) 2 。 此时，图像碎片的轮廓便可表示成其角序列的集合： 忸ff = 1 , 2 ，拧) a j “o , l 】( 3 4 ) 3 3 ，2 改进的角序列匹配算法 3 1 1 节中描述的算法，在一定程度上是可以把图像碎片轮廓表示为其角序列 的集合，但是此算法的鲁棒性较差( 鲁棒性，即不会因局部小的扰动而使表述发 生剧烈变化) 。因此，此算法在鲁捧性上还有待改进。我们知道，目前国内外在研 究图像碎片拼接方面大都是通过特征点的曲率值来描述图像碎片轮廓线的，这是 因为曲率既是刚体运动不变量，又是局部边界描述符，特别是曲率描述了轮廓线 的变化趋势，其鲁棒性较好。然而，对于3 1 1 节给出的角度算法只是给出了轮廓 线一种不稳定的表示方法，随着轮廓线上点的邻域半径的变化，轮廓线会得到多 种不同的角序列表示。也就是，取不同值时，他ii i = 1 , 2 ，厅 也会不同，对于两个 图像碎片的轮廓线来说，就有可能得出不同的匹配结果，这就需要更多地人为判 断，的取值，找出最佳的匹配结果。特别是，图像预处理时可能产生的噪音会引起 局部小的扰动，这会使所求得的角度值产生较大的误差，加大误匹配的可能，影 响最终的拼接。因此，我们在3 1 1 算法的基础上进行了改进，增强此算法的鲁棒 性，又提出了一种改进算法，具体如下： 由3 1 1 算法可得出对于点只可以求出其邻域半径为岫q 角度嘶，即3 3 式 ：。c o 。1 1 垒三量塑垒妄望坚丝些丝兰! ；丝 ( 札，一) 2 + ( y “，一y f ) 2x ( x i l - - x f ) 2 + ( y h 一) ，) 2 在改进的算法中，我们对邻域半径重新定义：从点只出发沿轮廓线逆时针r 个 像素点的范围定义为只点的逆邻域半径；从点只出发沿轮廓线顺时针f 个像素点的 范围定义为只点的顺邻域半径。这样对于e 点的特征角度值可以表示为： ”级月2 意导慧筹畿筹鬟舞b 5 ，0 缸。一曲z + 臼。一力1 b 。一曲2 + b m 一访i 对于，和t 的不同取值，口。也对应不同的值，这些值都在一定程度上表示了b 点在轮廓线上的角度值。在改进的算法中，我们对于，和f 的不同取值，可以求得 多个口。的值，这些值都是c 点在轮廓线上的角度值，对e 点处的轮廓线的变化趋 势有不同程度的描述。为了更好的用p 点的特征值表示轮廓线特征，我们采用了 均值法，即对这些角度值求平均值，只点的特征值就是它的平均角度值。 为了更有效的表示p 点在轮廓线上的角度，我们取r = t = ，。此时我们可以求 出关于异点的一个角度集合位。f ，1 j 2 , ，zf = 1 , 2 ，? ) ，集合中共有 异2 = l ( t 一1 ) + f 个元素，对这个集合中所有元素求平均值即可求得只点的平均角度 值。 lf， 即 口，= ( 口。) ( ，( ，一1 ) + ，) ( 3 6 ) 这里的，的取值是人为设定的，功取值主要根据轮廓线的形状判断。如果轮 廓线相对光滑，则，的值可设置大些；反之，则岫值可设置的小些。同时，实验 证明在求两图像碎片轮廓线匹配段时，值越小所得的匹配点越多，误匹配点也就 越多，值越大所得的匹配点越少，误匹配点也随之越少。这也与所获得的角序列 的鲁棒性相对应的，当f 值较小时鲁棒性就会较差，反之鲁棒性会较好。因此，在 实际操作时可以人为的调整j 值来获得最佳的匹配效果。 1 2 此时，图像碎片的轮廓线便可表示成其轮廓线上的点的角度平均值序列的集 合 a fi = 1 , 2 ，月) q o ，7 】 ( 3 7 ) 改进的角序列算法不仅有效的表示了轮廓线上点的角度值，还表示了在此点 处的轮廓线的变化趋势，降低了由于图像预处理时产生的噪声的干扰。这不仅能 够很好的描述轮廓线上的尖角，同时也增强了算法的鲁棒性。 3 3 3 多尺度方法 单尺度轮廓线匹配算法是针对每个轮廓线上每个点处理，这在效率上很费时。 如果一个图像碎片的轮廓线由个点表示，那么找两个图像碎片的最佳匹配时， 时间复杂度至少为“2 ) ，若有霞个图像碎片则总的时间复杂度至少为职矗2 2 ) 。 该算法在少量的轮廓线匹配时还可以，但当面对大量的轮廓线，每个轮廓线又有 大量的样本点数时( 即r 与的值很大时) ，如果每任意两条轮廓线之间的匹配比 较都用单尺度匹配算法的话，将会是一个很庞大的工作量。 为了减少时间复杂度，这里我们采用了多尺度技术，提出了一种多尺度角序 列算法。根据不同的尺度进行匹配，尽量减少匹配时间。通过对轮廓线的重采样， 不同的采样数目可以确定不同的尺度空间。比较粗糙的尺度的匹配时问明显的少， 而比较精细的尺度的匹配时间会较长。在轮廓线少的情况下，可以使用较为精细 的尺度来计算匹配，而轮廓线多的时候，则需要尽量的减少轮廓线上的采样点数， 即采用较为粗糙的尺度来计算匹配。当面对大量的数据时，我们考虑利用粗糙尺 度首先进行数据的筛选，再逐步的细化尺度。通过多次处理，不断的清除明显不 匹配的轮廓线数据，减少轮廓线匹配的数据量。 设定一个阀值r ，t 【o ，厅】，称r 为尺度阀值。当对轮廓线重采样时，只保留角 口i 小于r 的点，这样当r 从小到大取值时，轮廓线上的采样点的数量也随之从少 到多。即当尺度阀值r 取不同数值时，可在不同的尺度空间里对轮廓线进行描述， 实现多尺度角序列算法。设在尺度r 下，经过从采样的轮廓线描述为 麒”j k = 1 , 2 ，) ，( 3 8 ) 其中厦de 缸，f i l 2 , ，对且砖ns l 是= 1 , 2 ，辨 3 3 4 最长公共子序列算法 根据上面的角度计算方法，分别计算两块图像碎片的轮廓线上每个点的角度 值( 两块图像碎片的轮廓线的方向相反，一条是顺时针方向，一条是逆时针方向) 。 对于取定的尺度阀值丁，设重采样的两条轮廓线分别表示为角度串： 4 = 忙；”l i = l ，2 ，m ) 和b = 6 7 l = 1 ，2 ，) ，( 3 9 ) 其中，m 和分别是两条重采样轮廓线所包含的点数。如果l 口 ”一6 ：nl 占，其中s 是容许误差，则认为第一条轮廓线的第i 个点与第二条轮廓线的第_ ，个点在丁尺度 空间匹配。这样可以把a 和b 看作两个字符串，求得这两个字符串的最长公共子串， 就相当于求得了两条轮廓线之间完全匹配的一段区间 ，d 臀，a 品 和 科 ，“2 ，。b ，( + r ，) ，i ，m 为最多匹配的点数。但是最长公共子串要求不能插入、删 除其中的点，由于物体破碎时非常可能丢失一些较小的图像碎片，同时由于数字 化过程中离散采样的误差，这样完全匹配的区间非常小，不适合物体图像碎片的 拼合。因此，我们采用最长公共子串的一般形式，即最长公共子序列方法。其在 匹配的字符串中允许插入、删除字符，可以用来估计两个字符串的相似程度。这 相当于允许对轮廓线进行拉伸、缩短操作，符合物体图像碎片的拼接情况。我们 利用最长公共子序列算法便可获得最优匹配结果。 下面我们具体描述最长公共子序列算法： 设8 = 扣，l i = 1 , 2 ，珑) 、b = 6 p 1 ，= l ，2 ，n ) 分别代表两个轮廓，各有m 和 h 个采样点。我们建立一个肘排列的d p ( 动态规划d y n a m i c p r o g r a m m i n g ) 表， 匹配的起始点用( ；”，6 ，) 表示。该表的行用m 表示1 s m s m ，列用野表示 1 n n ，行与列相交用( m ，h ，) 表示。交叉点( 肌，。，n ，。) 与( m ，n ，) 的连线表示相 匹配的一系列点，则两轮廓的匹配段可分别表示为：0 ( m ，) ，口( ”o 。+ 1 ) ，a ( m ，) ) 、 ( 6 ( n ，i ) ，6 ( n 。q + 1 ) ，- 一，b ( n 。) ) 。 如果是两个轮廓很相似的话，相匹配点的角度值应该相等，考虑误差的存在， 匹配点的角度差就趋近于0 。 我们应用动态规划算法( d y n a m i cp r o 掣a m m i n g ) ，即在两个序列 a = 4 ；7 j i = 1 ，2 ，m ) 、b = 6 i y = 1 ，2 ， ) 中搜索最长的公共子序列。用c ( f ，- ，) 记录序列a 和序列b 的公共子序列的长度。当m = 0 或n = 0 时，空序列是a 和b 的 最长公共子序列，故c ( m ，n ) = 0 。其它情况下，可以建立如下的递归关系： 1 0当f = o 骑= 伽寸 一1 ，歹一1 ) + 1当即= 芬w ( 3 1 0 ) 【m a x ( c ( f ，_ ，一1 ) ，c o 一1 ，_ ，) )当可n 0 仃) 时 4 图像碎片拼接及实现 经过图像碎片匹配后，我们找到了相互匹配的图像碎片，同时也得到了图像 碎片的匹配段。接下来我们要将相互匹配的图像碎片拼合起来，重现物体的原貌， 下文提出一种图像碎片拼合算法，并就图像碎片拼合显示时涉及的坐标变换等相 关方面问题进行研究。 4 1 图像碎片拼接算法 考虑到遗失图像碎片的存在及相应的虚拟重建，图像碎片的拼合除了满足演 示、观测的需求还需要保证图像碎片间匹配轮廓线段拼接的严密性。另外针对 不同的图像碎片，局部坐标系是不同的，对于构成匹配对的两个图像碎片来说， 按照共有的轮廓线段进行拼合时，需要将其转换到同一坐标系中。这就涉及到局 部坐标系的建立以及坐标转换中的平移旋转等刚性运动的考虑。 局部坐标系的建立 图4 1 变换前的图像碎片 如图4 1 所示，图像碎片f 和图像碎片，构成一对匹配对，只是图像碎片f 上的轮廓线段，卑p ，是图像碎片，上的轮廓线段，两者共同构成匹配轮廓线段。 图像碎片f 的边界点为 ( 而，咒) 1 0 f 一1 ) ，图像碎片f 。的边界点为 ( x i ，r ；) l o - 1 ) 0 眵1 ) ) i f e ( i 0 , j 0 ) = = e ( i 0 i j o ) i 0 一i 0 1 ： e l s e i f f _ ( i o j 0 ) = = e ( i o j 0 一1 1 j o j o 一1 ； e l s e f 咄3 ) = d ( i 0 - 1 ，) | f ( g , 1 户d ( i 0 1 ，1 ) ； 磁 2 ) = d ( i o l 2 ) ； f ( g a ) = d 0 0 0 - 1 ，1 ) ；