快速模式匹配算法分析

《快速模式匹配算法分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、广西师范大学硕士研究生学位论文3．4直线段的特征构造⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯213．5基于直线特征的匹配算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．253．5．1相似性度量⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯_⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯273．5．2算法流程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯273．6实验及分析⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯283．6．1实验数据⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

2、⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯283．7总结与讨论⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯3l第4章总结⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯32参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯一：⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯33致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯36V广西师范大学硕士研究生学位论文第1章绪论对图像的描述和对图像之间的匹配问题一直是计算机视觉领域研究的热点问题，同时也是从底层视觉到高层视觉的关键步骤之一。图像中的基

3、元及其相互关系组成了图像的信息特征，而图像的几何结构可以表达图像的本质内容和性质，图像中相对稳定的信息特征一般包含在图像的几何结构里。按照匹配基元的不同，把模式匹配基元分为：区域基元、相位基元、特征基元。特征基元相对于其他两种基元来说，相对稳定，而且更加健壮。点和线作为图像中两个最重要的特征基元，而且它们之间的相互关系构成的特征，可以很好的作为表达图像的结构信息。特征基元包括块特征、特征线以及特征点等等，但是其中的特征点和特征线是使用最广泛，也是最重要的特征。由于特征基元有计算量小、速度快、鲁棒性好等等特点

4、，因此备受大家追捧。1．1课题背景及研究意义从特征匹配问题中抽象出来的点模式匹配问题是一个更加基础、更加具体的问题，是目前研究的热点问题之一。两个点集一一对应关系的寻找是点模式匹配的目的所在。这普遍存在于目标识别、航空、医学图像配准、遥感图像配准、生物计算机以及计算机视觉领域，因此这是一个普遍存在的基础性问题，而且有很广泛的应用前景。图像中的轮廓、目标的边界，物体的骨架都可以作为线段特征，而且线特征作为高层次的几何特征，能够对图像的几何结构进行高效的描述，。对于降低误匹配度含有巨大的作用。对图像的线进行合理

5、的描述，还有助于对图像内容的理解和后续的高层处理。线特征对于解决图像识别、描述、匹配等问题上具有很大的优势。首先，相对而言特征线段在图像上很少，但是同时具备更强的鲁棒性和稳定性，可以加快匹配的速度；其次，线特征反映了目标的语义信息。例如，导航图像、物体轮廓、人造的一些规则场景，这些物体都具有明显线特征。目前，在文献中对线匹配研究有一定的成果，但是对图像中线的描述仅仅是线段本身的特征，对线与线之间的相互关系研究有限。因此，对线与线之间的相互关系展开研究，以此形成线特征，对基于线特征的模式匹配的研究十分有必要。

6、1．2点模式匹配的研究现状由于点模式匹配研究技术和方法的不同，各文献对分类方法也各个不一样。谭志呼·】等按照不同的求解方法将点模式匹配分为：基于计算几何的方法、基于谱图理论的方法、基于特征不变性的方法、基于智能计算的方法。本文将点模式匹配分为以下几类：1．2．1基于空间变换参数匹配方法点模式匹配问题可以归结于一个组合优化问题，其实质是在两个点集间寻找一一对应广西师范大学硕士研究生学位论文关系。采用搜索算法是实现基于空间变换匹配方法最常用的方法之一。在解决基于参数变换的点模式匹配方法中，最早是M．A．Fisc

7、hler等【2】提出了随机抽样一致性算法。该算法可以在包含离群值的数据中，使用迭代的方式来估计模型的参数。这是一种局部最优算法，因此为了尽可能的达到全局最优解就必须提高迭代次数。RANSAC算法有如下缺点：首先，需要提高迭代次数才能有比较大的概率得到正确的结果；其次，如果一个数据集中包含多个模型，那么只能从数据集中估计一个模型出来。虽然有很多文献对于随机抽样一致性算法进行了改进和优化，但是随着各种复杂图像的出现，随机抽样一致性算法难以适用于变换复杂以及特征点多的图像间的点模式匹配问题。Besl等【3】提出构

8、造简单、计算复杂度低的迭代最近点算法(IterativeClosestPoint)。迭代最近点算法首先在点集中搜索最近距离的点对，然后通过分配点与点之间的对应关系，计算估计得到的变换模型，再次迭代变换模型重新确定对应关系。虽然该算法思想简单、收敛速度快，但是点集中存在噪声抖动、离群值时，很容易出现误匹配现象。为了优化ICP算法，文献【4】提出了一种新的点集匹配算法，即LM．ICP算法。算法误匹配的消除直接通过非线