临近匹配算法

临近匹配算法（精选3篇）

临近匹配算法 篇1

1. 局部匹配算法

局部匹配算法主要包括区域匹配法、特征法。

1.1 区域匹配算法原理

区域匹配算法是以基准图像中待匹配点为中心像素创建一个大小为m×n窗口, 由该窗口内的像素灰度值来表征该像素。在第二幅图像中, 沿极线在视差搜索范围内取出与基准点同样大小的邻域, 依次与匹配点的窗口进行比较, 其最大相似性对应的点就是最佳匹配。

区域匹配算法的重点是匹配代价的计算和匹配代价的累积。匹配代价计算就是选取相似性测度函数, 而匹配代价的累积体现在支撑窗口的选取上。几乎所有的区域匹配算法都要关注这两个问题:

1) 选取相似性测度函数。常用的相似性测度函数如下:

(1) 最小绝对差算法SAD

(2) 最小平方差算法SSD

2) 选取支撑窗口大小。一方面窗口的尺寸要尽量的大, 以便为可靠的匹配包容足够的灰度变化;另一方面, 窗口太大则包含视差的较大变化, 则会因左右图像上不同的投影畸变, 使得匹配位置不准确。

1.2 区域匹配实验结果

分别用SAD相似性测度函数对Tsukuba匹配源图像对进行匹配, 采用3×3、5×5两种窗口。实验结果如图1.1所示:

2. 全局匹配算法

大部分全局算法基于能量最小化的思想, 寻找视差函数d, 使全局能量最小化。本文对一种常用的全局算法--动态规划法做重点研究, 与区域匹配算法进行比较。

2.1 动态规划算法

动态规划匹配算法在外极线单调顺序约束下寻找视差空间图像 (DSI) 上的最小代价路径。最优路径的代价是所有子路径的和, 这些子路径所经过点的匹配代价由相似性度量因子决定。

2.2 动态规划实验结果

针对Birchfield的动态规划算法, 所产生的视差图如图2.1所示。

3. 总结

基于区域匹配中匹配窗口较小时, 误匹配较多, 而窗口较大时, 边缘处又显得很模糊, 所以窗口大小与形状必须具有较强的适应性。动态规划是对一条扫描线计算全局匹配代价, 提高了匹配的准确性。但是动态规划有一个很大的局限性, 它缺乏对水平连续性约束和垂直连续性约束的融合。从匹配性能上看, 动态规划算法在边缘不连续区域有较高的误匹配, 而在其它区域的误匹配百分比都较基于区域匹配算法低;从匹配速度上看, 基于区域匹配相对于全局匹配较小的计算量, 使其匹配速度明显加快, 更适合对实时性要求较高的应用。

摘要：立体匹配是立体视觉中的关键技术之一, 能否有效地解决该问题影响着立体视觉的发展。本文研究了相似性测度函数和邻域窗口对基于区域匹配算法的影响, 实现了具有代表性的全局匹配算法——动态规划, 并与基于区域匹配算法进行了比较。

关键词：立体匹配,基于区域的匹配算法,动态规划

参考文献

[1]张广军.机器视觉[M].北京:科学出版社, 2005.

[2]S·Birchfield, C·Tomasi.“Depth discontinuities by pixel-to-pixel stereo”[J].International Journal of Computer Vision, 1999, 35 (3) :269.

临近匹配算法 篇2

地形匹配技术是地形辅助导航的关键技术之一,它在航空领域应用广泛,在水下运载体的海底地形匹配定位、机器人导航定位以及陆地车辆导航等方面也有着广阔的应用前景。

地形匹配的过程,实际上是将实时测出的地形高程图(实时图)与飞行器内预先制备的基准地形高程图(基准图)在空间上进行对准的过程,以获取飞行器精确导航定位信息。经典的平均绝对差(MAD)、平均均方差(MSD)和互相关(COR)等地形轮廓匹配算法可以完成匹配定位。但是这些方法是基于对应点之间的差值关系计算相关度的,要求两幅地形图是在相同尺度的坐标系下,并且待匹配两图之间不存在旋转变换。但是多数情况下,由于生成手段、时间等因素的不同,同一区域的不同时相DEM覆盖区域不可能完全重合,可能存在一定的未重合区域和定量的旋转、平移、缩放等变换。解决存在缩放、旋转条件下的地形匹配问题,可大大降低三维实时地形图测量的要求,增强地形匹配的适应性,具有非常重要的现实意义。

本文提出了改良的树描述符匹配算法,用树描述符对地形特征(山谷线)进行重建,通过搜索树描述符中最长公共子串的方法获得最大同构子树,建立2个同构子树之间的匹配关系完成匹配工作。该算法可应用于存在缩放、旋转条件下的地形匹配问题。

2. 地形匹配技术的原理

地形匹配技术的依据是地形的凹凸不平特征与地理位置之间的对应关系,利用这种地形特征,在运动载体实时测量得到的地形图与已知的三维地形基准图进行配准,从而确定载体自身的位置信息。本文通过提取匹配图的山谷线作为待匹配的地形特征。

将山谷线的矢量图映射到树结构中存储其拓扑结构,通过两者之间特征对的匹配,也就是树结构匹配,就可以获取两种DEM中的特征对应关系,从而确定两种DEM是否达到粗匹配的要求。

3. 树描述符匹配算法

为了更简单、高效地进行树的匹配,本文提出了树描述符算法对树进行拓扑匹配。树描述符包含了物体的形状特征和拓扑特征。

3.1 树描述符

定义对由匹配树深度优先搜索产生的节点序列中的所有节点用其孩子数替换,替换后得到的新序列即为树描述符。

3.2 树描述符匹配算法

对于2个匹配树T1,T2,我们初步建立的匹配算法如下:

(1)深度优先遍历匹配树T1、T2;

(2)用树描述符重建树,描述符分别为s1、s2;

(3)在基准树T1中搜索待匹配树T2的最大同构子树T,即找出s1、s2的最长公共子串;

(4)如果最长公共子串和被匹配树T2的描述符s2相等,说明T1、T2之间存在匹配关系,建立2个同构子树之间的匹配关系则匹配完成;

(5)由匹配关系得到对应点之间的坐标关系,建立两图之间的坐标对应关系,完成目标对准过程。

3.3 算法改进

上述匹配算法只能解决匹配模型中的子树匹配问题,不能解决松弛匹配的问题,如图1所示。为了得到更全面、更准确的匹配结果,提高算法的查全率,我们有必要改进这种匹配方法,才能得到正确的拓扑结构匹配结果。

经分析,上述匹配算法需要对第三个步骤中的搜索最大同构子树过程加以改进,以解决松弛匹配问题。改进的搜索最大同构子树算法如下:

(1)搜索出s1中的所有叶子节点(描述符为0的节点),并进行标识;

(2)用字符串匹配算法搜索s1、s2中最长公共子串;

(3)字符串匹配算法:

a.如果s2中字符等于0(叶子节点),则查询到s1中与之对应的字符值为n,则s1向后移n位,后移的时候如果继续遇到非零值n1,n2…,则s1再向后移n1+n2+…位,然后s1、s2同时下移一位并继续进行下一位的字符匹配,如果下一位是s2到达结束符,则匹配成功。

b.如果s2中字符值不等于0,且s2的字符值等于s1中的字符值,则s1、s2同时下移一位,如果s2的字符值m小于s1中的字符值p,则s2向后移m位,s1向后移p位,然后再同时下移一位,继续匹配直到找到最大同构子树,匹配成功。

c.如果s2中字符不等于0,且s2的字符值大于s1中的字符值,则匹配不成功。

3.4 结果分析

以图1为例,分别用树描述符算法以及改进的树描述算法进行树结构匹配,其搜索最长公共子串匹配过程如图2和图3所示:

图中上行是T1中被框部分的树描述符,下行是T2的描述符,按照改进的匹配算法,我们可以得到正确的匹配结果,T2中的每一个节点都能在T1中得到匹配。说明改进的算法是有效和可行的,能够得到与实际情况一致的匹配结果。

4. 结束语

树描述符算法使用了树描述符来描述树,完整表达了树的形状和拓扑结构,避免了复杂的运算,基于树描述符的同构子树匹配方法简单而快速,建立的拓扑匹配关系具有地形的旋转、大小、平移不变性,一般情况下,也不受地形小的扭曲变形的影响,因为高程的细微改变是不会改变拓扑形状的,除非是经过严重的地质灾害,改变了地形的基本面貌,那就另当别论了。该方法能够获得快速而最优最准确的匹配结果。

摘要：提出了改良的树描述符匹配算法,用树描述符对地形特征(山谷线)进行重建,通过搜索树描述符中最长公共子串的方法获得最大同构子树,建立2个同构子树之间的匹配关系完成匹配工作。该算法可应用于存在缩放、旋转条件下的地形匹配问题,可大大降低三维实时地形图测量的要求,增强地形匹配的适应性,具有非常重要的现实意义。

关键词：地形匹配,树描述符,山谷线,拓扑结构匹配

参考文献

[1]刘文予,刘俊涛.基于骨架树描述符匹配的物体相似性度量方法[J].红外与毫米波学报,2005,24(6):432-436.

[2]Gan Guoqiang,Qiu Zhihe.Navigation and position[M].Beijing:National Defence Industry Press,2000.

[3]O’Callaghan J F.The Extraction of Drainage Networks Digital Elevation Data[J].Computer Vision,Graphics,and Image Processing,1984(28):323-344.

[4]Golden JP.Terrain contour matching(TER COM):a cruise missile guidance aid[C]//Proceedings of the Society of Photo-Optical Instrumentation Engineers(SPIE).1980,238:10-18.

[5]李立春,苑云.三维地形不变性特征描述及其在地形匹配中的应用[J].航空学报,2009,30(11):2143-2148.

[6]陈绍顺,李彦斌,李云.地形匹配制导技术研究[J].制导与引信,2003,24(3):17-21.

[7]林应强,吴立德.基于模型的三维物体识别[J].自动化学报,1997,23(6):756-761.

概率算法求解模式匹配问题 篇3

关键词：概率算法,模式匹配,关联数,主串,模式串,时间复杂度

1 前言

给定的符号模式是否出现在是一个很长的文本中, 通常将此问题称为模式匹配。分析DNA序列和其他各种基因相关项目的结果, 涉及的算法学上的核心问题是模式匹配问题。求解模式匹配问题的常用算法有朴素算法和KMP算法。朴素算法的效率很低, 时间复杂度为O (n*m) [1,2,3,4,5]。KMP算法仅当主串与模式间存在许多“部分匹配”的情况下才能显示出它的高效率O (n+m) [1,2,3,4,5]。本文使用概率算法求解模式匹配问题, 此算法特别适用于模式串非常长的情形。

2 模式匹配问题的概率算法

2.1 算法的基本思想

模式匹配问题具体描述为, 在长度为N的主串S中查找是否存在长度为M的模式串T。概率算法求解模式匹配问题的基本思想是, 将主串S中每个长度为M的符号串关联一个数, 然后随着算法穿过S, 依次考虑每M个符号的块所关联的数与模式串T所关联的数是否相同。若某相邻M个符号所关联的数与模式串T所关联的数不相同, 则它们一定不同;如果它们所关联的数相同, 则它们不相同的概率很小, 完全可将其忽略, 认为它们是相同的。[6]为了使概率算法的时间复杂度尽可能小, 每M个符号的块所关联的数必须满足以下条

件: (1) 要比M短, 理想情况下为logM。 (2) 计算这个数所需的时间不能超过O (M) , 理想情况下为常量时间。可见, 简单地将M个符号的块翻译成数字是不能满足这两个条件的。

我们可以随机产生一个长度为logM的素数Prim, 用M个符号的块直接翻译成的数字除以Prim, 所得的余数就是M个符号的块所关联的数。可以看出, 这样所求的关联数满足上述条件 (1) , 因为M个符号的块直接翻译成的数字除以素数Prim的余数位于0到Prim-1之间, 所以它的长度不超过Prim的长度logM。下面重点看一下它是否满足上述条件 (2) 。

假定主串S和模式串T都是由26个英文字母组成的, 将它们分别看作一个很长的二十六进制数, 每位数的可能取值分别A、B、…、Z, 其中A相当于数值0、Z相当于数值25。一般情况下, 计算M位数除以某个素数Prim的余数所需的时间, 和M有关。但是, 可以利用已计算出余数的M位数, 来计算下一个M位数除以Prim的余数。为此, 需从主串S的最后一个字符开始, 即首次取出的M位数是S的倒数第M到倒数第1个字符组成的, 第2次取出的M位数是S的倒数第 (M+1) 到倒数第2个字符组成的。例如, 考虑S=“A C E F S D S E C W U YTWVBNMCCXZDEFRGGLKPOIU…..”, 令T的长度M=8, 假设我们已经到达第5个位置, 数SDSECWUY除以随机产生的素数prim的余数已经计算出来, 接下来要计算FSDSECWU除以prim的余数。因为FSDSECWU=FAAAAAAA+ (SDSECWUY-Y) ÷26, 所以FSDSECWU除以Prim的余数可通过FAAAAAAA除以Prim的余数和SDSECWU除以Prim的余数经过简单加减运算而求得。FAAAAAAA中的实际上是F×267, 这样的数共有25个, 所以可提前将它们除以P r i m的余数计算出来并存放在一个数组中。而SDSECWU除以Prim的余数可通过SDSECWUY除以prim的余数、此余数的最后一位数字及商的最后一位数字经过简单算术计算而求得。可见, 计算M个数字的数除以Prim的余数可在常数时间内完成。

总上所述, 随机产生一个长度为LogM的素数, 将每M个字符的块直接翻译成一个数, 然后用这个数除以素数所得余数, 就是M个字符的块所关联的数。而且此关联数的计算可在常数时间内完成。

2.2 算法的具体步骤

根据2.1中概率算法的基本思想, 这里给出概率算法的具体实现过程。

在长度为N的主串S中查找是否存在长度为M的模式串T的概率算法的具体步骤如下: (1) 随机产生一个含LogM位数字的二十六进制素数, 将其按位存放在数组prim中;

(2) 计算模式串T直接翻译成的数除以prim的余数, 并存放于数组tmod中;

(3) 定义整型变量s_location, 并令s_location=N-M+1;

(4) 事先计算出A×26M-1, B×26M-1, C×26M-1, ……, Z×26M-1除以prim的余数, 并存放于二维数数组mid (26行M列) 中;

(5) 将主串S的第s_location至第s_location+M-1个符号取出, 存放于字符串ss中;并计算ss直接翻译成的二十六进制数除以prim的余数, 存放于数组smod中;

(6) 判断smod与tmod是否相同, 如果不同, 转7) ;否则, 按位比较字符串ss和T, 判断ss和T是否相同, 如果相同, 说明在S中找到了T, 算法结束, 否则转7) ;

(7) s_location=s_location-1;

(8) 如果s_location等于0, 说明在S中不存在模式串T, 算法结束;否则转9) ;

(9) 取出主串S的第s_location个字符, 并将其赋给变量num;

(10) 如果主串S的第s_location+M个字符大于数组smod的最后一个元素, 则将它们的差赋给变量x;否则将它们的差加26赋给变量x;

(11) 根据x的值和prim的最后一个元素的值, 可得出前面的M个字符直接翻译成的数除以prim的商的最后一位数y;

(12) 将y*prim+smod按位赋给数组remain;并将remain的最后一位删除掉;

(13) 如果mid[num-‘A’]+remain>prim, smod=mid[num-‘A’]+remain-prim;否则smod=mid[num-‘A’]+remain;转6) 。

上述算法中的加减运算均在26进制下进行。

注意, 上述算法的前提条件是, 主串和模式串均由二十六个字母组成, 所以每M个符号所关联的数是一个二十六进制数。如果主串与模式串中的字符不止有26个可能的取值, 是一个比较大的数, 则本文的算法就不再方便了;如果主串与模式串中的字符不足26种, 例如是10种, 那么随机产生的素数就是十进制数, 而且每M个字符的块所关联的数也是十进制数了。比如, DNA序列中只有T、G、C、A四种字符, 所以如果模式匹配的是DNA序列, 每M个符号的块所关联的数就可以是四进制数。

其实, 算法中的运算均是按位进行的。所以, 是几进制数关系并不大。

3 概率算法与朴素算法比较

朴素算法的基本运算是比较。使用朴素算法最坏情况下需比较 (N-M+1) *M次。如果M非常大, 如为十亿, 则朴素算法的执行速度会非常慢。概率算法的基本运算是算术加或减。概率算法的一个核心操作是计算M个字符所关联的数, 即将M个字符直接翻译成某进制数, 并求此数除以随机素数的余数。此核心操作最坏情况下需进行算术加或减C*logM* (M-logM+1) 次, 这里C是常数, 表示数制。此核心操作在整个概率算法中最多进行C+1次, 一次是求模式串所关联的数;一次是求主串的最后M个字符所关联的数;其余是求形如“常数×CM-1”的数除以那个素数的余数。概率算法余下的操作是根据已求得的M个字符所关联的数来计算下一个M个字符的块所关联的数, 此操作最多进行N-M次, 每次需进行基本算术运算最多4* (logM+1) 次。[1,2,3,4,5]

从上面的分析可以看出, 如果M和N不很大, 本文的概率算法没有朴素算法有效;但是M和N越大, 本文的概率算法的使用价值越大。

参考文献

[1]鲁宏伟, 魏凯, 等.一种改进的KMP高效模式匹配算法[J].华中科技大学学报 (自然科学版) , 2006, 34 (10) :41-43.

[2]张治, 施鹏飞.一种有效的贪婪模式匹配算法[J].计算机研究与发展, 2007, 44 (11) :1903-1911.

[3]THATHOO R, VIRMANI A, et al.A fast exact pattern matching al-gorithm for biological sequences[J].Current Scence, 2006, 91 (1) :47-53

[4]Sheik S S, Aggarwal S K, et al.A fast pattern matching algorithm[J].Journal Chemical Information and Computer Science, 2004, 44 (4) :1251-1256.

[5]许峰, 满振梅, 等.数据集成领域中的模式匹配技术研究[J].计算机工程, 2006, 32 (6) :40-41.