基于图谱的点模式匹配算法研究

《基于图谱的点模式匹配算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、安徽大学硕士学位论文基于图谱的点模式匹配算法研究一般地，人们把对具体的一些事物进行检测所得到的具有空间和时间分布的信息称之为模式，并把同一类中模式的总体或者模式所属的类别称为模式类[3]。而模式识别就是指依照具体研究对象的共同特征和属性进行的分析和分类。它主要研究以下两点问题：一是研究生物体感知对象的方式方法；二是在给定的任务下，研究如何用计算机来实现模式识别的方法。模式识别最主要的目标是如何将具体的模式划分到不同的类别中[4]。信号处理理论出现以后，人们尝试用照相机或摄像机来获取图像，然后把它转换为数字信号，并使用计算机来实现对获得的该视觉信息处理的目的，由此引发了计算机

2、视觉这门学科的兴起[5]。计算机视觉研究的是如何找出在各种复杂场景中识别物体所需要的视觉信息，并研究怎样从图像中来获取这些信息的一门科学技术。简单地说，计算机视觉就是指通过得到的图像来理解所拍摄对象的形状和几何尺寸，以及该对象距观察者的距离和运动速度和多个对象间的相互关系等，也就是用两维的图像来研究三维空间中的三维对象[6]。图像匹配是遥感图像处理、三维重建、目标识别和机器人视觉等研究领域中的一个关键技术。其常用方法分为基于灰度的方法[7,8]与基于特征的方法[9,10]。由于图像的几何特征可以用一系列反映图像特征的离散点来表示，而且图又是一种重要且有效的结构特征信息表示方

3、法之一，所以基于特征点(例如边缘点、角点)的图像匹配即点模式匹配近年来逐渐成为图像匹配的重要研究内容之一。点模式匹配是模式识别、计算机视觉等研究领域中的重要课题,它能够有效避免图像匹配中计算量过大、匹配时间长等缺点。在点模式匹配过程中，首先需要解决的问题是怎样提取反映图像特征信息的特征点，也就是特征提取的过程，其次是进行特征点匹配算法的研究，并采用一些适当的方法进行算法优化，以此来减少计算复杂度，提高匹配精度。基于图谱的点模式匹配方法的主要思想是：从待匹配图像中提取能够反映图像结构特征的几何基元（角点、边缘点或通过其它方式获取的离散点），通过点与点之间的连接关系抽象出能够反

4、映待匹配图像特征的结构图，如邻接矩阵（AdjacencyMatrix）、Laplace矩阵或关联矩阵等，然后计算出反映图像结构特征的谱，结合特征值、特征向量与图像特征点之间的关系，最后通过构造匹配关系矩阵来实现图像的匹配。其具体步骤如图1-1表示：2安徽大学硕士学位论文第一章绪论图像特征点集结构图图匹配图像匹配图1-1点模式匹配的基本流程Fig.1-1BasicflowofPointPatternmatching由图1-1可见，图像匹配问题可以转化为图的匹配问题，其中图匹配这一步是图像匹配的研究重点。将图谱应用于图匹配问题中，已经取得了许多重要成果，为了降低计算复杂度并提高

5、匹配精度，本文在已有的基于Laplace谱的点模式匹配算法的基础上进行了改进和优化，提出了三种匹配方法，并通过对不同图像进行的大量实验，验证了这些算法的可行性和有效性。本章围绕着本文所研究的内容，先对图谱理论的相关概念、发展历史及其在图像处理中的一些应用做一个简单叙述，然后说明图像匹配的研究方法以及在实际生活中的重要应用，最后概括下本文的主要内容和组织结构。1.1图谱理论1.1.1图谱相关概念1．图的相关概念图G是由两个集合V和E组成的，记为G=(V,E)，其中，V是顶点的有穷非空集合，E是顶点与顶点之间边的有穷集。通常地，V(G)和E(G)分别表示图G的顶点集和边集。E(

6、G)可以是空集，如果E(G)为空集，则表示图G只有顶点而没有边。对于图G，若边集E(G)为有向边的集合，则称该图G为有向图。相对的，若边集为无向边的集合，则该图为无向图。在无向图中，如果存在一条边，则称v，ijiv为这条边的两个端点，j且称它们互为邻接点。图中顶点的度定义为以该顶点为一个端点的所有边的个数，记为D(v)。对有向图而言，顶点v的度分为入度和出度，其中入度是指以该顶点为终点的入边3安徽大学硕士学位论文基于图谱的点模式匹配算法研究个数；出度是指以该顶点为起点的出边个数，该顶点的度就是其入度和出度之和。假设图有n个顶点，则含有n(n−1)/2条边的无向图称

7、为无向完全图；而含有nn−条边的有向图称为有向完全图。(1)2．邻接矩阵邻接矩阵是一种用来表示顶点之间相邻关系的矩阵。设具有n个顶点的图G=(V,E)，记它的顶点序号依次为0,1,2,L,n−1，则G的邻接矩阵为具有如下定义的n阶方阵A：Aij[][]对于无向图，vv或vv∈EG对于有向图,∈EG1,(,)(,)();,()ijjiij=0,其他情况3．Laplace矩阵设图G=(V,E)的邻接矩阵定义为A(G)=(a)，其中，当u和v相邻时1a=，uvuv而当u和v不相邻时a=0。记(){:}D