改进的遗传算法应用于碎片拼接.docVIP

郑蓓蓓，郭立本 ( 上海海事大学信息工程学院，上海 200135) 摘要:碎片拼接实际用途已经越来越广泛，本文讲述传统碎片拼接的方法，引出图形匹配策略，传统的碎片拼接算法大多 需要大量繁琐的计算，大大增加了算法的时间复杂度，依据传统算法的不足，改进遗传算法应用于碎片匹配策略，提出可 以实现更高效率、更高准确率的碎片拼接算法。 关键词:碎片拼接; 图形匹配; 改进遗传算法 中图分类号:TP301． 6 文献标识码:A doi: 10． 3969 / j． issn． 1006-2475． 2011． 05． 016 Application of Improved Genetic Algorithms to Fragment Re-assembly ZHENG Bei-bei，GUO Li-ben ( College of Information Engineering，Shanghai Maritime University，Shanghai 200135，China) Abstract: Fragment re-assembly has already broadly used in various fields，traditional methods of fragment re-assembly are given to introduce shape matching algorithm and to present the defects of traditional algorithms including complex calculation procedures and a large number of time consumption． According these defects，this paper applies improved genetic algorithms to fragment re- assembly to achieve higher efficiency and accuracy． Key words: fragment re-assembly; shape matching; improved genetic algorithms 引 言 传统碎片拼接技术 传统的碎片拼接技术主要是基于局部最优的，考 虑局部边界、局部角点的情况来判断是否达到最佳匹 配的效果。图像拼接的流程包括图像配准、图像变 幻、图像拼接。对于图像处理操作主要包含图像的二 值化、轮廓图形化等操作［4］。 图像二值化是指二值图像的转换［5］，每一像素 仅用一位表示的图像。在数字图像中，二值图像占 有很重要的地位。其原因是二值图像比灰度图像的 信息小得多，因此处理速度快、处理成本低于印前图 像处理，对常见的线条稿，这种原稿在扫描时用二值 图像已经足够，即使在扫描时因某种需要而扫描成 灰度图像，可以用适当的二值化处理算法恢复到二 值图像在二值图像中，几何形态的定义较为方便，可 以用一种较为简便的方法进行图像轮廓的提取［6］。 轮廓曲线的特征表示是整个匹配算法 的 基 础［7］，起着至关重要的作用。将利用轮廓上各点与 0 1 所谓的碎片拼接是指将一组物品的碎片依据其 轮廓拼接出???品原来的形状的技术。碎片拼接技术 应用于各个领域包括文物、瓷器、照片等碎片的拼 接［1］。三维物品的碎片拼接是模式识别领域的重点 研究对象之一，对于三维物品的拼接，在采集图像信 息时需要考虑角度、光线的各个因素［2］，同样需要将 三维的物品采集成二维的图像，进行碎片的图像拼 接，所以二维图像的拼接便是三维实物拼接技术中的 关键因素［3］。 图像采集是对碎片数字化的过程，将采集的图像 转化为二值图像，对图像进行匹配处理，得到原始图 像的最优组合，从而实现碎片拼接的目的。 本文首先对碎片拼接的基本问题及过程作一个 概要的阐述，然后提出几种传统的碎片拼接方法，比 较各自的优劣，在此基础上提出改进遗传算法用于碎 片拼接，使其成为一种可行性高、准确率高的算法，同 点的像素点 p坐标为( x2，y2) ，那么对点的特征描述 表达式为: d = a( x1 － x2) 2 + b( y1 － y2) 2 其中: 当 x1 ＜ x2 时，a = -1，否则 a = 1; 当 y1 ＜ y2 时，b = -1，否则 b = 1。 经过实验，利用各点与其相差 6 个点的轮廓点之 间的关系来对轮廓进行表示时，效果较好。实际应用 时，在预处理阶段，由于轮廓曲线上各点的坐标都依 次存入数组 contour 中，在进行轮廓表示时，只要根据 下标依次对该对数组中的点进行表示就行了。例如， 若当前需要进行表示的点下标为 i，由于轮廓曲线是 闭合的，若 i +