多模式匹配（精选七篇）
多模式匹配 篇1
序列相似性分析一直是生物信息学中的一个研究热点。相似性分析基本采用序列比对的方法来实现。最早用于相似性分析的序列比对算法是Gibbs的点阵图法[1]。其后, Needleman和Wunsch提出了进行全局比对的Needleman-Wunsch算法[2], Smith和Waterman提出了进行局部比对的Smith-Waterman算法[3]。目前的许多算法都是在这些算法上的改进。由于序列比对算法复杂、计算量大, 2000年Randic等人首次提出非序列比对的方法实现相似性分析, 利用矩阵将复杂问题简单化, 将序列比对转化为矩阵不变量的比较[4]。另外一些学者在序列相似性分析中引入几何图形表示, 并从中提取不变量。汪挺松引入了图形曲率, 作为生物相似性比较的不变量[5], 计算量也大大降低。李梅等人采用基于DTW的DNA序列相似性度量方法能够有效地解决动态规划算法对空位罚分的主观性依赖[6]。唐晓婵采用4D图形的几何中心表示DNA序列比较的不变量[7], 在进行序列相似性分析时能够得到较好的效果。本文提出了一种基于模式匹配的多序列相似性分析的方法, 并通过两组实验证明了该方法的有效性。
2 基于模式匹配的多序列相似性分析
2.1 方法概述
利用模式匹配的序列相似性分析方法属于DNA序列相似性研究中应用最广泛的序列比对方法, 该方法基于模式匹配的序列比对结果进行相似性分析。为了使得到的进化树更加准确, 采用Kimura双参数模型和Neighbor-joining方法实现。
2.2 利用模式匹配的序列相似性分析方法的基本步骤
利用模式匹配进行序列相似性分析的基本步骤分为2个阶段:
第一阶段:基于模式匹配的序列比对
(1) 将每个序列) 等分成长度为r的子序列构成子序列 集合L , {l取值len (p1) } , k取值 O (l/logl) 。将集合L中的所有子序列构成一棵公共的模式树T。
(2) 对于公共的模式树T, 每个序列利用Aho-Corasick算法搜索T, 并记录每个序列匹配的模式号和该模式在当前序列中出现的位置。这里使用一个三维数组进行记录, 三维数组的第一维对应一个序列, 第二维包括2个一维数组, 一个数组存储匹配的模式号, 另一个数组存储该模式号在序列中出现的位置。
(3) 统计每个序列Pi (i =1, 2, ..., n) 匹配的模式号, 这里只考虑搜索T时通过非失效链接得到的模式号, 并使用一个二维数组进行统计。二维数组的第0行按顺序记录匹配成功的模式号的值。从第1行开始, 每一行对应一个序列, 该行上的每一列对应模式号在该序列中出现的次数。
(4) 依次找出匹配次数最多的那个模式号, 将没有匹配该模式号的序列从查找中心序列的队列中去除, 最后剩下的序列将是中心序列Pc 。
(5) 得到中心序列后, 将P c与Pi (i =1, 2, ..., n且i≠c) 依次进行比对。由于在步骤 (4) 中已经记录了P c和Pc 匹配的子串位置, 然后使用动态规划算法将P c和Pi 未匹配的子串进行比对。并且记录需要在P c和P i中插入空格的位置S ci和Si 。
(6) 依次比对完P c和Pi (i =1, 2, ..., n且i≠c) 后, 对所有需要插入空格的位置Sci (i ≠c) 汇总, 汇总后的位置记为S c, 分别比较S c和Sci (i =1, 2, ..., n且i≠c) , 在S i中加入新汇入的空格位置。分别根据S i中记录的空格位置将空格插入到Pi中并输出多序列比对的结果。
第二阶段:使用序列比对结构构建进化树
(1) 对结果序列集L使用Kimura双参数模型计算进化距离矩阵;
(2) 对进化距离矩阵计算并筛选最小速率校正距离, 并找出最小速率校正距离所对应的结果序列S i#'和Sj' ;
(3) 为系统进化树创建一新节点t, t的孩子节点为Si' 和S j', 从结果序列集L中删除节点S i'和节点S j'并加入新节点t;
(4) 重复3-5, 直到结果序列集L中节点个数为0时停止, 则系统进化树构建完毕。
3 实验结果分析
该组数据采用基于模式匹配的多序列比对方法进行比对, 得到8种H5N1型禽流感病毒的HA片断基因的序列比对结果, 采用Kimura双参数模型构建进化矩阵, 如表1所示。将表1给出的进化矩阵输入到PHYLIP软件包中的neighbor.exe软件中, 构造出物种的进化树, 如图1所示。
由图1可知, 在同种动物身上采集的病毒中相同年份和相同地域的相似性最高。另外, 使用CLUSTALX软件进行多序列比对, 同样采用Kimura双参数模型和neighbor.exe程序构建进化树, 这两种方法得到的进化树的结构是完全相同的。并且文献[8]使用基于BB信息离散度的DNA序列相似性分析的方法也得到了相同的结果。
4 结束语
本文在基于序列比对的基础上提出了利用模式匹配进行序列相似性分析。由于Kimura两参数模型更能体现生物的突变规律, 计算出的序列距离更为精确, 所以采用基于模式匹配的多序列比对, 使用Kimura双参数模型和Neighbor-joining方法实现相似性分析。实验结果表明, 该方法能够对DNA序列的相似性进行有效分析, 分析结果接近事实。
参考文献
[1]Gibbs A J, McIntyre G A.The diagram a method for comparing sequences its use with amino and nucleotide sequences.Eur J Biochem, 1970, 16:1-11
[2]Needleman S B, Wunsch C D.A general method applicable to the search for similarities in the amino acid sequences of two proteins.Journal of Molecular Biology, 1970, 48:443-453
[3]Smith T F, Waterman M S.Identification of common molecular subsequences.J Mol Biol, 1981, 147:195-197
[4]Randic M.Graphical representations of DNA as 2-D map.Chemical Physics Letters, 2004, 386 (2) :468-471
[5]汪挺松.曲率在生物序列相似性分析中的应用:[大连理工大学硕士学位论文].大连:大连理工大学, 2007, 42-45
[6]李梅, 白凤兰.基于DTW距离的DNA序列相似性分析.生物数学学报, 2009, 24 (2) :374-378
[7]唐晓婵.基于4D图形表示的DNA序列相似性分析.科学通报, 2010, (6) :442-446
模式匹配技术在多序列比对中的应用 篇2
随着人类基因组计划的顺利实施和信息技术的迅速发展, 基因序列数据呈指数级增长。为了更加科学有效地分析和处理这些数据, 一门融合多学科的交叉学科——生物信息学应运而生。生物信息学中, 序列比对是最基本也是最热门的问题之一。目前双序列比对可以使用动态规划算法求得最优解, 而多序列比对仍然是一个NP难题[1]。
模式匹配是指在文本序列中检索某个特定子串的所有出现位置, 即字符串的模糊匹配[2]。生物信息学中序列比对的常用方法是将基因序列看成是由有限字符集中的字符构成的文本字符串, 然后对文本字符串进行比较。所以像序列比对等相关问题可以通过将基因序列转换为文本序列之后, 使用模式匹配技术来解决[3]。本文在深入研究星比对算法和AhoCorasick搜索算法的基础上, 对基于关键字树的DNA多序列比对算法进行改进, 提出了一种基于模式匹配的多序列比对方法, 在保持生物敏感性基础上降低序列比对的运行时间。
二、星比对算法和Aho-Corasick算法
2.1星比对算法
星比对算法是一种快速的用于求解多序列比对问题的算法[4]。它需要选取一个中心序列, 比对的结果是通过中心序列与其它序列的比对建立的。利用中心序列将多序列比对转化为双序列比对, 降低了序列比对的维度。中心序列的选取采用计算所有优化比对的方法, 选取与其他所有序列相似程度最高的序列为中心序列。然后遵循“一旦为空格, 始终为空格”的原则, 把空格不断地加入到中心序列中从而使得中心序列和比对的序列达到最大匹配数。加入到中心序列中的空格是不能够移出的, 并且始终保留在中心序列中, 直到中心序列与所有序列都比对完毕。
2.2 Aho-Corasick搜索算法
Aho-Corasick算法是经典的多模式匹配算法之一[5]。该算法的处理过程分为构树和匹配两个阶段。构树阶段的主要任务是扫描模式串集合, 将集合中提供的模式串构建一棵模式树。而匹配阶段的主要任务是利用构建的模式树对文本序列进行扫描, 找出匹配的模式串并返回其位置。只需扫描一次就能找出所有匹配的模式串, 匹配的效率很高。
三、问题提出
由于星比对算法平方级的时间复杂度无法满足实际需要, 文献[6]对其进行改进, 提出了基于关键字树的DNA多序列星比对算法。其主要思想是依次将每个序列都分割成等长的子串集合, 为这个集合构建一棵模式树。除该序列的其他序列使用Aho-Corasick算法对该模式树进行模式匹配, 并记录所有模式串出现次数的总和。将出现次数总和值最大的序列定为中心序列, 然后根据星比对算法中“一旦为空格, 始终为空格”的思想, 将其他序列与中心序列的未匹配部分进行多序列比对。文献[6]虽然将星比对算法的平方级时间复杂度降到了线级, 但在选取中心序列时, 模式串的出现次数没有考虑是否为公共的模式串, 使得选取的中心序列并非为最优解。本文在文献[6]的基础上进行改进, 建立一棵公共的模式树, 所有序列都使用Aho-Corasick算法对这棵公共的模式树进行模式匹配, 并使用数组记录搜索得到的模式号, 通过对数组中的模式号的逐级筛选, 最后剩下的序列所包含的公共的模式串为最多, 增强了算法寻求最优解的能力。实验表明改进后的算法更能获得最优解。
四、模式树模型
模式树模型[7]描述如下:
定义1:由模式串集合 构成的模式树K是一棵有根树, 满足:
(1) K的每一条边由1个字符标记;
(2) 与同一节点相连的任意多条边标记的字符均不相同;
五、算法描述
基于模式匹配的多序列比对算法仍然是以星比对为基础的, 分为寻找中心序列和两两比对两个主要步骤。要寻找中心序列, 设需要进行比对的多个序列分别是 。具体操作如下:
步骤4:依次找出匹配次数最多的那个模式号, 将没有匹配该模式号的序列从查找中心序列的队列中去除, 最后剩下的序列将是中心序列Pc。
步骤5:得到中心序列后, 将Pc与 依次进行比对。由于在步骤 (4) 中已经记录了Pc和Pi匹配的子串位置, 然后使用动态规划算法将Pc和Pi未匹配的子串进行比对。并且记录需要在Pc和Pi中插入空格的位置Sci和Si。
六、实验结果与分析
实验将基于模式匹配的多序列比对算法和星比对算法、基于关键字树的DNA多序列星比对算法进行比较。实验PC的CPU为Pentium (R) Dual-Core T4200 2.00GHz, 内存为2.00GB, 操作系统为Windows7, 运行环境为Vistual Studio2008。选取了两组数据进行测试, 对每组测试数据都连续运行程序20次, 并从程序运行时间和碱基对匹配情况两个方面比较三种算法的期望时间复杂度和比对的效率。
第一组实验通过对6种西藏部分地区豆科植物的根瘤菌多序列比对, 完成DNA同源性分析。实验数据来自于NCBI (http://www.ncbi.nm.nih.gov) 上的核酸库以及文献[8]。序列的条数为6, 序列的平均长度为1428。该实验数据程序运行时间如图1所示。
统计6种西藏根瘤菌RDNA全序列的碱基对匹配情况如图2所示。
第二组实验通过对11个物种的β-球蛋白基因的第一个外显子进行多序列比对。实验数据来自于NCBI (http://www.ncbi.nm.nih.gov) 上的核酸库以及文献[9], 序列的条数为11, 序列的平均长度为92。该实验数据程序运行时间如图3所示。
统计11个物种的β-球蛋白基因第一个外显子的碱基对匹配情况如图4所示。
通过第一组实验结果可知, 在运行时间上本算法虽然略高于基于关键字树的星比对算法, 但其碱基对匹配数却远高于基于关键字树的星比对算法。因为本算法在寻找中心序列时采用的是逐级去掉希望最小的序列, 最后剩下的序列所包含的公共的子串为最多, 相对于基于关键字树的星比对算法中直接将模式串出现次数最多的序列定为中心序列的方法, 得到的结果则更接近最优解。
在第二组实验中, 本算法的碱基对匹配数也高于基于关键字树的星比对算法, 与星比对算法更为接近。在运行时间方面, 由于本实验所选取的序列相似性很高, 寻找中心序列时统计每个序列共有的模式号的个数接近k值, 所以可以认为寻找中心序列的运行时间为O (n2k) 。而基于关键字树的星比对算法的寻找中心序列运行时间为O (n2l) , k是待比较的序列所分割的段数, 取值O (l/logl) , 远小于l, 所以O (n2k) 也远小于O (n2l) 。在建立好模式树后, 本算法和基于关键字树的星比对算法一样, 将完全匹配的子串位置存储下来。所以在其他序列与中心序列逐个进行比对的过程中, 对于完全匹配的子串就不需要再进行比对。另外, 其他序列与中心序列采用动态规划算法进行比对, 其运行时间与比对的长度呈平方关系。如果相似程度非常高的序列进行比对, 匹配的子串个数与k越接近, 那么在每个序列与中心序列进行比对的长度就越短, 花费的时间也就越少。
七、结论
本文提出了一种新的生物序列比对算法——基于模式匹配的DNA多序列比对算法。此算法是在星比对算法和AhoCorasick算法的基础上, 针对基于关键字树的DNA多序列比对方法提出来的。
由于此算法是对原始星比对算法的一种改进, 所以算法的实现仍然包括两个步骤:寻找中心序列和序列两两比对。通过实验结果表明, 新算法相对于基于关键字树的DNA多序列比对算法的准确率更高, 相对于原始星比对算法的运算速度更快。
参考文献
[1]张琎, 张远.基于GC-GM的多序列比对穷举遗传算法[J].计算机应用, 2010, 30 (1) :146-149.
[2]Navarro G, Raffinot M.Flexible Pattern Matching in Strings:Practical on-line search algorithms for texts and biological sequences[M].New York:Cambridge University Press, 2002, 36-128.
[3]Shin S Y, Lee I H, Kim D, et al.Multiobjective Evolutionary Optimization of DNA Sequences for Reliable DNA Computing[J].IEEE Transactions on Evolutionary Computation, 2005, 9 (2) :143-158.
[4]Brown J W.The Ribonuclease P database[J].Nucleic Acids Research, 1999, 27 (1) :314.
[5]Aho A V, Corasick M J.Efficient string matching:an aid to bibliographic search[J].Communications of the ACM, 1975, 18 (6) :333-340.
[6]邹权, 郭茂祖, 等.基于关键字树的DNA多序列星比对算法[J].电子学报, 2009, 37 (8) :1746-1750.
[7]邓惠俊.多模式匹配算法的研究[D].合肥:合肥工业大学, 2009.
[8]王素英, 杨晓丽, 等.西藏根瘤菌新表现群的DNA同源性及16SrDNA全序列分析[J].微生物学报, 2006, 46 (1) :132-135.
多模式匹配 篇3
本文在AC算法的基础上, 结合BM算法, 提出快速的多模式匹配算法, 在匹配中, 跳过无用的字符, 使用匹配中失败的信息, 实现文本串的快速匹配, 减少算法的时间复杂度。
1 AC算法
AC算法是多模式匹配算法, 利用有限自动机把字符比较转化为状态转移。首先, 对模式串集合预处理, 构成树型有限状态自动机, 它包含一组状态, 每个状态用一个数字来表示。状态机读取文本串中的字符, 通过产生状态转移的方式或发送输出来处理文本, 只需扫描一次文本串就能够找出与其匹配的模式串。
2 BM算法
BM算法是一种精确字符串匹配算法。该算法将文本串和模式串的最左端对齐, 然后从模式串的最后一个字符与文本串开始比较, 若匹配失败, 模式串则向右滑动一段距离。
3快速的多模式匹配算法——N_AC_BM算法
为了提高速度, 利用模式匹配失败时所在的位置和距离, 增加跳跃的距离, 这就是快速的多模式匹配算法———N_AC_BM算法[1]。
3.1算法的基本思想
给定一个文本串要查找模式串, 从最右向左对模式串进行匹配, 若找到模式串尾字符, 则再从右向左比较剩余字符, 最后将指针跳过尾字符所对应的距离。
skip函数和shift函数如下所示:
3.2算法详细描述
详细算法如下:
4实验结果分析
为了验证本算法, 选5Mbit的一个文本串, 与AC算法和BM算法进行比较, 测试环境为操作系统Win XP, CPU4.8 GHz、内存4GB。实验结果如表1、表2所示。通过实验可知:本文的算法, 花费时间大约是BM算法的1/5, AC算法的1/3[4]。随着模式串长度的增加、模式串数目的增多, 本文所设计的算法所花时间更少有很大的优势。
结束语
在网络信息监控中模式匹配的速度是非常重要的。本文的快速的模式匹配算法———N_AC_BM算法, 结合有限状态自动机的工作原理, 利用单模式匹配的BM算法和多模式匹配的AC算法优点, 实现了一种快速的多模式匹配算法, N_AC_BM算法通过对匹配失效字符的判断, 减少了无效的跳转和匹配。实验证明, N_AC_BM算法大大提高了匹配速度, 具有明显的优势。
参考文献
[1]戚溥, 胡军, 李千目.面向RFID数据处理的复杂事件模式匹配方法[J].计算机科学, 2013, 40 (1) :73-76
[2]蔡晓妍, 戴冠中, 杨黎斌.改进的多模式字符串匹配算法[J].计算机应用.
多模式匹配 篇4
图像特征匹配是计算机视觉和模式识别等领域研究的基本问题以及物体识别、跟踪等应用的重要基础,广泛应用于摄影测量与遥感、资源分析、三维重建、目标识别、图像拼接、图像检索等众多领域, 一直是研究者关注的焦点, 在针对地面图像的特征匹配方面得到了深入研究,以及对运动目标轨迹提取具有较高的研究意义和应用价值。但是由于它受到天气、阳光、遮挡等外界因素的严重影响, 并且存在因不同的成像时间、角度、距离等因素而导致的图像平移、旋转、缩放等问题, 这都给目标特征检测及特征匹配的工作带来了很大的难度[1]。针对这些不足,尤其是在尺度方面的不足,David G.Lowe在2004年总结了现有的基于不变量技术的特征检测方法,提出了一种基于尺度空间的特征匹配算法——尺度不变特征变换(scale invariant feature transform,SIFT)算法[2,3]。SIFT算法检测的点特征是图像的局部特征,该特征对平移、旋转、尺度缩放、亮度变化保持不变性,对视角变化、仿射变化、噪声也保持一定程度的稳定性和适应性,而且即使是信息量较少的图像也能提取大量的SIFT特征点。然而在这些大量特征点中,也会产生一些误匹配点,从而会导致图像匹配精度,尤其是地面图像,由于其本身特征点多、乱、灰度变化不明显以及没有角点、直线、边缘、模板、区域和轮廓等明显特征,导致部分特征点会发生误配和乱配情况[4]。针对上述问题,本文提出基于多目标优化的特征匹配算法,该算法经过同一场景点投影到图像中的模板建立目标函数,根据同一幅图像中模板之间的欧氏距离建立约束条件,剔除误匹配点,实现特征点的二次精确匹配。
1 SIFT 特征匹配理论
1.1 SIFT 特征匹配的主要思想
SIFT 算法是一种基于尺度空间、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述操作数,可以理解两幅图像之间发生平移、旋转、仿射变换、光照变化情况下的匹配问题,甚至在某种程度上对任意角度拍摄的图像也具备较为稳定的特征匹配能力,从而可以实现差异较大的两幅图像之间的特征的匹配[3]。
1.2 SIFT 特征匹配步骤
SIFT操作数首先在尺度空间进行特征检测,并确定关键点的位置和关键点所处的尺度,然后使用关键点邻域梯度的主方向作为该点的方向特征,以实现操作数对尺度和方向的无关性。
(1) 尺度空间的形成。高斯卷积核实现尺度变换的惟一线形核,于是一幅二维图像的尺度空间定义为:L(x,y,σ)=G(x,y,σ)*I(x,y)式中:(x,y)是空间坐标;σ是尺度坐标,图像被平滑的越少,相应的坐标值也就越小。大尺度对应于图像的概貌特征,小尺度对应于图像的细节特征。
为了有效地在尺度空间检测到稳定的关键点,提出了高斯差分尺度空间(DOG)。DOG操作数定义为2个不同尺度的高斯核差分,DOG操作数如下:
(2) 空间极值点的检测。为了寻找尺度空间的极值点,每一个采样要和其所有相邻点比较,以确保在尺度空间和二维图像空间都检测到极值点,通过拟和三维二次函数以精确确定关键点的位置和尺度,同时去除地对比度的关键点和不稳定的边缘回应点,以增强匹配稳定性、提高抗噪声能力[4]。
(3) 关键点方向分配。利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数,使操作数具备旋转不变性。每个关键点有3个信息:位置、尺度、方向。由此确定一个SIFT特征区域。
(4) 特征点描述子生成。为了增强匹配的稳健性,对每个关键点可使用4×4共16个种子点来描述,这样对于一个关键点形成128维的SIFT特征向量[5,6,7]。
2 多目标优化理论与方法
最优化的目的是根据一定的标准(目标)在许多可供选择的方案中搜索出最好的或最令人满意的方案。如果选择时需要同时考虑的标准多于一个,最优化问题就成为多目标优化问题。多目标优化的图像处理问题是通过调节多个目标之间的权衡问题,使在一定的约束条件下同时达到最优,以此来减小图像处理领域中的一些误操作,如:增强、匹配、识别等。
式中:x称为决策向量,x=(x1,x2,…,xn)∈Ω⊆Rn通常由模型参数组成;Ω为决策空间;fi(x)为第i个目标函数;y为目标向量,y∈Y⊆Rk,Y为目标空间,ei(x)为约束条件[8]。
对于∀x∈Ω,如果∃X*∈Ω满足下式,则称向量为Pareto优解。
在图像处理多目标优化问题的可行解集中没有比Pareto优解更好的解。由Pareto优解构成的集合称为Pareto优集,Pareto优集中任何一个解都是可能的最优解。在图像处理优化时,根据图像处理者(称为决策者)对优化目标主观偏好程度与Pareto优解搜索过程之间的相互影响关系,多目标优化方法主要分为3类:先验优先权法、后验优先权法与优先权演化法[9]。
3 基于多目标优化的SIFT 特征特征匹配算法
本文结合SIFT特征的众多不变性优点,对地面图像进行特征提取与匹配,且利用改进的特征点匹配算法计算候选目标的精确位置。然而在特征匹配的过程中,受天气、光线和地面图像复杂度的影响,会出现特征点的误匹配,导致图像出现匹配误差。针对上述问题,该系统在SIFT特征匹配的基础上引入多目标优化理论。在SIFT特征点提取的基础上,利用多目标优化准则,实现2幅图像的SIFT特征点的精确匹配。
如图1所示,在进行图像处理工作时,首先分析图像处理的任务,根据实际要求建立图像处理模型并确定优化目标和约束条件;其次根据优化目标涉及的参数设计相关变量,选择设计优化算法并对变量进行优化搜索,在确定初始参数后,通过对模型参数的优化搜索和对优化结果的评价进行循环迭代,逐渐得到最优解。
在SIFT特征匹配中往往由于孤立点、噪声点和地面图像本身特征点多、乱、灰度变化不明显以及直线、边缘、轮廓等不明显特征的影响,导致部分特征点会发生误匹配和乱匹配,从而降低了特征匹配的精度。
具体算法流程如下:
(1) 利用SIFT算子对采集到的地面图像进行特征点检测,将采集到的特征点进行相似性度量,得到图像间的粗匹配;
(2) 利用多目标优化算法对粗匹配的特征点进行分析。
建立模型如下:
(1) 在相机采集的第n帧图像中,分别寻求图像右半区域3个特征点并结合周围的点组合成模板f11,f12,f13;且l1,l2分别为模板f11与f12之间的距离和f12与f13之间的距离。如图2所示,在第n+1帧图像中,根据车速以及相机的帧率估计第n帧图像中3个特征出现的范围,再从中依次遍历SIFT特征点,并以该点为中心扩展模板f21,f22,f23;l1′,l2′ 分别为f21与f22之间的距离和f22与f23之间的距离。2幅图像中的模板大小应保持一致。
(2) 确定优化设计的目标函数,如图2、图3所示,根据2幅地面图像模板之间的相互关系建立目标函数:
式中:(xi,yi)(i=1,2,3)为第n+1帧图像中的所遍历的SIFT特征点的坐标值;cov[f1i,f2i(xi,yi)]为2个对应模板之间的相关系数。
(3) 确定约束条件。对于2幅相邻的图像,其特征点的之间的距离要么不变,要么随尺度的变化同时放大和缩小,为此可以二者距离的比值作为约束条件。
4 实验验证
为了体现此改进算法匹配精度的优越性,该实验采用高速CCD相机拍取路面图像并进行闭合曲线运动。如图4所示。
在采集到的地面原始图像中提取SIFT特征点,如图5所示,从图中可以看出,在采集图像的过程中,由于地面图像其本身特征点多、乱、灰度变化不明显以及没有角点、直线、边缘、模板、区域和轮廓等明显特征,不可避免地存在部分噪声点和孤立点,导致部分特征点会发生误配和乱配的情况,从其匹配结果(见图6)可以看出这些孤立点和噪声影响到了特征匹配精度。
对粗匹配后的两幅图像进行多目标优化分析,从匹配结果(见图7)来看,剔除了易产生误匹配的特征点,几乎没有发生误匹配现象。故提取出的相机轨迹(见图8)可以看出,与实际的闭合曲线运动轨迹存在误差。从提取出的相机运行轨迹(见图9)来看,相机从某一起点出发并最终回到同一起点,较好地完成了闭合的曲线运动。
5 结 语
本文针对地面提出了一种改进的SIFT特征匹配算法。首先在采集的图像中提取出SIFT粗匹配特征点,然后再对这些特征点进行多目标优化分析,实现特征点的二次精确匹配。从实验结果可看出,这种算法效果明显,能够有效地避免地面图像中的噪声点、孤立点对图像匹配的影响,从而有效地提高了匹配精度。
摘要：SIFT算子在实际应用中,由于地面图像本身特征不明显且提取出的特征点多、乱以及灰度变化不明显等特点的影响,从而导致特征点误匹配。为此提出一种改进的SIFT图像特征匹配算法。该算法是在SIFT特征匹配的基础上,利用多目标优化算法,建立相关匹配模板,利用给定同一场景的两幅图像,寻找同一场景点投影到图像中的模板之间的相关性建立数学模型即目标函数,根据同一幅图像中模板间的距离建立边界约束条件,从而剔除一些误匹配点。实验表明,该算法可以有效地提高图像匹配精度。
关键词：SIFT,多目标优化,特征匹配,误匹配点
参考文献
[1]TOMASI C,KANADE T.Detection and tracking of pointfeature[R].Carnegie Mellon University Technical ReportCMU-CS-91-132,Pittsburgh,USA,1991.
[2]高建,黄心汉.一种简化的SIFT图像特征点提取算法[J].计算机应用研究,2008,25(7):2213-2215.
[3]LOWE David G.Distinctive image features from scale-in-variant keypoints[J].International Journal of Computer Vi-sion,2004,60(2),91-110.
[4]LOWE D G.Object recognition from local scale!invariantfeatures[C]//International Conference on Computer Vi-sion.[S.l.]:[s.n.],1999:1150-1157.
[5]王国美,陈孝威.SIFT特征匹配算法研究[J].盐城工学院学报,2007,20(2):1-5.
[6]王楠,王勇峰,刘积仁.车行轨迹曲线的实施提取与描述[J].东北大学学报,1999,10(2):111-113.
[7]张健,周晓东,张春华.空间目标运动轨迹提取算法研究[J].红外技术,2007,29(8):459-463.
[8]薛毅.最优化原理与方法[M].北京:北京工业大学出版社,2001.
[9]FLETCHER R.Practical Methods of Optimization[M].[S.l.]:Wiley,1980.
多模式匹配 篇5
地形辅助导航系统(TAN)是用于飞行器上的自助导航定位系统。它运用机载高度表测出飞行器正下方地形高度序列,并与预先存储好的地形高程数字图进行匹配,以达到定位和修正航迹的目的。
惯性导航系统(INS)是用于飞机上的主要导航设备,他不依赖于地面辅助设备,实时地为飞机提供当前位置、速度、姿态等导航信息。但惯性导航系统同样存在缺点:误差会随着飞行时间、距离的增加而增加。
目前,大多导弹采用地形匹配技术以达到导航的目的。该方法为了保证可靠的定位精度,需要采集较长的一段距离内的地形数据,从而造成较大的延迟。同时对存储的地图的数据量有较高的要求。常用的地形匹配算法有两种:一是TERCOM算法,它是以地形标高坡面图为基础;二是SITAN算法,它是以从数字地图的地形斜率为基础的[1]。
文中介绍一种地形匹配基本原理,以激光雷达多路径进行匹配,并结合TERCOM和SITAN两种算法的优势得出一种更快速、更精确的地形匹配方法。
1 地形匹配基本原理及单路径算法
1.1 地形匹配原理
地形匹配技术基本原理是运用弹载高度表测量,经平滑处理后,得出飞行器飞行离海平面的绝对高度ha;然后通过机载雷达测出飞行器距离垂直地面的高度hc;两高度数值相减即得飞行器航迹上的地形实际高程剖面(序列)hr;如图1所示。算得的高程序列结合弹载数字地图信息,运用特定算法就可以得出当前导弹的位置[2]。
1.1.1 TERCOM算法
TERCOM算法的依据是在地球陆地表面上任何地点的地理坐标, 能根据其附近地域的等高线或地貌来单值确定。TERCOM常用算法有MAD,MSD和COR。文中以MAD和MSD为例进行介绍[3]。
①平均绝对差最小算法(MAD)
②均方差最小算法(MSD)
式中,L是采样地形轮廓长度;TA(i)是通过计算得出的第i个地形高度值(i=1,2,…,L);TS(x+iτx,y+iτy)是第i个数字地图高程值;x,y是进行匹配分析的网格中心坐标;τx,τy为飞行器相邻两次采样之间飞行器在两坐标轴上分别飞行经过的距离;若飞行器均匀速度飞行,则二者者是常值。最优路径的计算是使JMAD和JMSD达到最小[4]。
TERCOM算法要求飞行器接近于匀速飞行,且系统的速度误差和航向误差低于一定数值时才会有较好的效果。
1.1.2 SITAN算法
SITAN算法采用扩展Kalman滤波器来计算测量的地形标高与预期的地形标高之差δh, 用连续估计修正系统的误差。SITAN系统由两种工作方式组成搜索模式和跟踪模式。搜索模式采用单状态并行Kalman滤波器阵列对飞行器的当前运行位置进行搜索, 其子滤波器匹配长度好坏是由平滑加权残差平方(SWRS), 并由此得出定位判据, 判断飞行器当前是否进入到跟踪模式。SWRS的详细求解过程为:
残差ek,t=Zk,t-Xk,t (3)
归一化残差平方
平滑加权残差平方SWRSk,t=αWRSk,t+(1-α)SWRSk,t (5)
式中,Zk,t和Xk,t是第k个子滤波器在t时刻的观测值和状态值;Pk,t和R是系统的状态方差阵和测量噪声方差阵,α是加权因子[5,6]。
如果正确得出飞行器的当前位置值,飞行器则由搜索模式转入跟踪模式。
Xk,t=Φk+1,kXK+Γkωk (6)
Z=HX+γ (7)
式中,X=[δx,δy,δh,δvx,δvy]T是状态变量;Φk+1,k是一步状态转移矩阵;Γk是系统噪声矩阵;H=[-hx -hy 1 0 0]是测量矩阵;hx和hy是x和y轴向的地形斜率;γ是高斯测量白噪声。
SITAN在低信噪比的地形高程数据时定位精度要比TERCOM好。且当其初始定位误差较小时,匹配精度和运算量都较为理想,但较大的初始误差会使得拟合线性化误差增大,不能使卡尔曼滤波局部线性化收敛。TERCOM算法则对初始定位精度没有精确要求[7]。
1.2 单路径地形匹配算法
①飞行器在固定一段距离会采集一次高程数据。当采集足够多的数据,例如s次,且将高程数据作为s维向量R。
②采用匹配准则MAD和MSD。
③若机载地图x轴向最大坐标值为M,y为N。则从机载地图原点开始扫描即可得到M×N个s维的航迹高程向量Axy。
④当采用MSD算法,选取结果最小的点,其坐标(x,y)为地形匹配结果。当采用COR算法,则选取结果最大的点,其坐标(x,y)即为匹配结果[8]。
2 基于TERCOM和SITAN的多路径算法
如上文所述,单一路径地形匹配算法缺点在于需要飞行器飞行较长距离才能得到足够精确度的匹配结果。因此在实际飞行中有很大局限性,特别是在救险或执行紧急任务的飞行器上。但激光雷达可有效解决该问题。它除了具有较高的测量精度外,还有能同时测量多路径的特点,可以测量其横向不同角度的高程值[9]。
如图2所示,当飞行器可同时横向测量7个不同位置高程值时,其所需飞行距离即为原来的七分之一,可大大缩小因采样数据所需飞行的距离。而其计算只需通过三角关系简单将其转换为地面测量点的相应高程值即可。
由于TERCOM算法在较大的初始位置误差下仍能得出正确匹配位置,SITAN算法允许飞行器对惯导系统进行修正,本文采用基于地形轮廓的TERCOM算法作为底下那个匹配系统搜索模式下的算法,以基于扩展Kalman滤波原理的SITAN算法作为跟踪模式下的算法。该两种算法结合形成一个适用于航空用的地形匹配算法,其工作流程如图3所示[10]。
根据该算法,首先进入搜索模式,并在该模式中进行两次分别基于MAD和MSD的地形匹配,当两次匹配结果一致时进入跟踪模式。如果两次结果未达成一致,则需继续进行匹配,直至两次匹配结果一致。具体搜索模式如图4所示[11]。
算法通过搜索模式后,进入SITAN跟踪模式。在此过程中,由于惯导速度在短时间内有很小漂移的特性会影响匹配精度。可利用INS输出的一系列位置信息,对跟踪前期结果进行校验,也可验证搜索结果的正确性[12]。
搜索模式通过后, 转入SITAN 跟踪模式。在模式的转换过程中, 为了保证匹配的精确性, 根据惯导的速度在短时间内漂移很小的特性, 利用INS 输出的一系列位置信息, 对跟踪前期的匹配结果进行检测, 同时也可进一步检测搜索结果的正确性。具体步骤如下:
①记录搜索模式下连续2次通过表决的匹配位置信息和所需时间,并以第2次的匹配结果作为SITAN跟踪算法的初始位置值。
②根据SITAN算法的状态方程、量测方程和Kalman滤波算出当前匹配的位置值λ(K)、L(K);(其中λ为经度,L为纬度)。
③根据前5次匹配结果和式(8)可推算出当前时刻的位置估计值λt(K-n)(K)、Lt(K-n)(K)(n=1,2,3,4,5)。
④将Kalman滤波算法得出的当前位置值与惯导算法得出的5个当前位置值相减,得出误差结果转化为米,如果误差小于0.5个网格的情况大于半数,则可认为Kalman滤波解出的匹配结果λ(K)、L(K)正确,否则视为错误结果。
⑤如果连续5次匹配结果都无效,则重新搜索;若连续5次匹配都有效,即可停止监测,进入跟踪模式;若5次匹配结果中有无效结果,则返回第②步。
式中,t(K)为第K次匹配的匹配时刻;vE、vN分别为惯导的东和北方向速度;RM、RN分别是子午圈和卯酉圈半径。
经过上述跟踪算法一段时间会积累较大误差,为使得SITAN算法滤波继续收敛,飞行器地形匹配系统需重新进入搜索模式。此后匹配都需在搜索和跟踪模式中交替进行。
3 算法仿真和结果分析
对上述所提出的地形匹配算法进行计算机仿真,并与单一路径单状态并行Kalman滤波所需时间比较。
仿真使用大小为2000m×1500m,间距为100m的实际数字地图。初始位置误差东向北向均为500m,飞行速度为200m/s,初始速度误差为1m/s,匹配周期为1s。雷达高度表和气压高度的噪声标准差分别为1m,2m,…,35m。共仿真10000次。
由表1可知,采用单路径地形匹配算法,正确率随着采样点数的减少而迅速下降,其中SITAN算法抗干扰能力差,噪声过大时无法得出匹配结果。每个网格内只需采样1次,因此采样频率为2。若采样次数为30,则采样所需时间为15s。若采样次数为20,则所需采样时间为10s。为得到75%以上正确率,最短采样时间10s加最短搜索时间4s得最短匹配时间为14s。
由表2可知,采用多路径地形匹配,采样10次,正确率也能达到95%以上,算法抗干扰能力强。最短采样时间5s加最短搜索时间4s得最短地形匹配时间只需9s。
4 结束语
文中采用多路径并结合SITAN和TERCOM算法各自特点,更加充分利用地形信息。在采样次数减少的情况下,仍能达到很高的正确率。并设计了基于TERCOM算法的一致性表决搜索方法,并在搜索完成情况下进入跟踪模式。在上述两点改进前提下,大大缩短了地形匹配时间,并提高飞行器在飞行情况下的连续匹配。因此该方法在航空领域具有理论意义和使用价值。
参考文献
[1]李杰.无人机INS地形匹配组合导航技术研究[D].北京航空航天大学,2007.
[2]王英钧.地形辅助导航综述[J].航空电子技术,1998(1):24.
[3]范承啸,张瑛,胡志强.数字地图在地形匹配辅助导航中的应用算法改进研究[J].2010,7:4-35.
[4]常青,马洪波,李言俊.地形辅助导航的匹配算法[J].弹箭与制导学报,2002,4:22-3.
[5]马昕,袁信.地形辅助惯性导航系统研究[J].南京航空航天大学学报,1997(6).
[6]田金文,苏康,柳健.基于局部熵差的图像匹配方法[J].宇航学报,1999(1).
[7]王志森,姜景山.一种鲁棒性雷达高度计跟踪算法研究[J].电子学报,2003:3-32.
[8]Wang Zhisen,Zhang Yunhua,Jiang Jingshan.A robust trackingsystem for imaging radar altimeter[C].Proceedings.ISAPE 2000.5th International Symposium on,15-18 Aug.2000:37-40.
[9]马洪,李娜,张藴玉.一种应用于地形匹配雷达高度表中的回波跟踪与测高算法[J].2005,11:6-26.
[10]孟海东,王祺,慕春棣,等.基于激光雷达的多路径地形匹配算法[J].2010(2):2-27.
[11]PRIESTLEY N.Terrain referenced navigation[C]Las Vegas,NV:Position Location and Navigation Symposium,1999,3:482-489.
多模式匹配 篇6
二分图也称二部图, 是图论当中一种特殊的模型。根据其定义, 它是无向图, 其顶点集V可分割为两个互不相交的子集 (X, Y) , 并且图中的每条边 (i, j) 所关联的两个顶点i和j分别属于这两个不同的顶点集 (i in X, j in Y) 。求带权二分图的最佳匹配就是根据图中两边的点之间的关系以及已存在的边的信息, 选择已存在的边当中的若干条边组成一个完备匹配, 该匹配能够使这两个不相交的子集中的某一个子集中所有的点都饱和并且该匹配是所有的匹配当中边的权值加起来和最大的一个匹配。求二分图的匹配在一些安排、调度等问题当中有重要的应用, 并且在很多情况下是求出最优解精确而高效的算法。
1 问题的提出
在多机系统中有M台处理机, 某一时刻有N个作业来请求处理, 由于每台处理机性能的不同以及作业的内容不同, 所以不同的作业在不同的处理机上所需的时间也不同, 假设第个作业在第j台处理机上处理所需的时间是t[i][j]。 (某个作业全在某个处理机上完成, 处理机只有处理完当前作业后才会去处理其它的作业)
问题:现在要你设计一个调度方案, 使这N个作业的平均回转时间最小。一个作业的回转时间为它结束时刻和它请求处理时刻 (对于上述所有作业来说, 这个时刻都是0) 的差。
2 问题的二分图匹配算法
2.1 问题的的性质
上述问题是多机调度问题当中的一种, 它不同于多机调度当中要求完成所有作业时的时刻最早的那种NP问题, 它是要使所有作业的平均回转时间最小, 这是一个P类问题, 它能够求得精确解。下面介绍用二分图匹配求得精确解的思路及算法。
先分析一台处理机的情况。假设这台处理机按顺序处理的k个作业的所花费的处理时间依次是t1, t2, t3, …, tk, 那么第i个作业的回转时间则为ri=t1+t2+t3+…+ti所以这k个作业总的回转时间是t1+ (t1+t2) + (t1+t2+t3) +…+ (t1+t2+t3+…+tk) =t1×k+t2× (k-1) +t3× (k-2) +…tk-1×2+tk从这里可以看出如果作业i是处理机j中倒数第p个处理的程序, 那么它对总的回转时间的增加量是t[i][j]*p。由上述分析可以看出, 由于同一个作业在处理机上被处理的位次不同致使其对总回转时间的增加量不同, 所以如果建立二分图的话, 就要对代表机器的点进行拆点处理, 将每个点拆成N (作业总数) 个点来表示作业在该处理机上被处理的位次。
2.2 二分图模型的建立
构造一个二分图G, 左边的N个结点为N个作业, 右边的M个结点为M台处理机, 这样就是原始的二分图了。
然后对右边的每个结点进行拆点, 将每个点换成N个子结点代替, 这些子结点表示作业在该处理机上被处理的顺序, 比如说右边第j个结点被替换成子结点后其中的第p个子结点 (记该结点为结点 (j, p) ) 表示作业在第j台处理机上倒数第p个被处理。在拆点之后就要建立边了, 每个左边的结点i和右边的结点 (j, p) 之间建立一条权值为t[i][j]*p的边, 表示第i个作业如果在第j台处理机上倒数第p个被处理就会对总的回转时间增加t[i][j]*p。这样二分图模型就建立好了。
然后求出该带权二分图的最小权匹配就能将N个作业分配完并使总的回转时间最少。
2.3 算法的实现
该调度算法包括3部分, 首先建立二分图, 然后求最小权匹配, 最后计算最小平均回转时间。具体过程如下:
先建立二分图, 设有二分图左边有ln个结点, 右边有rn个结点, 用arc[ln][rn]记录所有的边的权值。然后初始化图, 因为我们要求的是最小权匹配, 而我们现有的求二分图带权匹配的算法是求最大权匹配, 所以初始化的时候要转化一下:将边权统一设置为实际值的相反数, 即负数 (最大权匹配算法在边的权值为负时仍能得出正确解) , 在求出二分图的最大权匹配后将结果再取反就是正确的结果了, 即最小权匹配的结果。下面是初始化图的算法:
然后就是要求该二分图的最大权匹配了, 这里要用到求二分图最大权匹配的KM算法。KM算法是通过给每个顶点一个标号 (叫做顶标) 来把求最大权匹配的问题转化为求完备匹配的问题的, 设顶点Xi的顶标为lx[i], 顶点Yj的顶标为ly[j], 顶点Xi与Yj之间的边权为arc[i][j]。在算法执行过程中的任一时刻, 对于任一条边 (i, j) , lx[i]+ly[j]>=arc[i][j]始终成立。KM算法的正确性基于以下定理:若由二分图中所有满足lx[i]+ly[j]=arc[i][j]的边 (i, j) 构成的子图 (称做相等子图) 有完备匹配, 那么这个完备匹配就是二分图的最大权匹配。KM算法的具体实现如下:找rn次增广路, 每次增广时都修改遇到的点的顶标, 并且修改时利用slack[RIGHT_MAX]数组来降低修改时查找的复杂度。具体算法如下:
执行完KM算法后, 返回的结果就是二分图最大权匹配的结果, 将该结果取反就是要求的结果了, 即最小的总运转时间, 然后再将取反后的结果除以N即为最小的平均运转时间, 实现语句是min_t= (double) (-KM () ) /N。同时link[]数组中记录着匹配的信息, 也就是调度的信息。
2.4 算法的结果与复杂度分析
应用上述算法, 对M为3, N为5, 并且5个作业在3台处理机上的处理时间的t数组为t[5][3]={{7, 9, 8}, {6, 5, 4}, {3, 4, 6}, {8, 5, 7}, {6, 5, 5}}, 进行该调度算法后得出min_t即最小平均回转时间是6.2, 得出记录匹配信息的数组link[1…15]={1, 3, -1, -1, -1, 4, -1, -1, -1, -1, 5, 2, -1, -1, -1}, 其表示调度时的分配如下:机器1上依次处理作业3、作业1, 机器2上处理作业4, 机器3上依次处理作业2, 作业5。
该调度算法的时间复杂度取决于KM算法, 假设n=, 则该KM算法需要找O (n) 次增广路, 每次增广最多需要修改O (n) 次顶标, 每次修改顶标时从slack[]数组中查找O (n) 次, 所以时间复杂度为O (n3) 。该调度算法的空间复杂度为O (N2M) 。
3 结束语
综合以上分析, 整个多机调度问题的二分图匹配算法的时间复杂度为0 (N3M3) , 所占空间复杂度为O (N2M) 。该算法比搜索、动态规划等算法有更高效的时间复杂度, 并且该算法能获得精确解。该调度算法提高了计算机系统资源的利用率, 加快了用户的响应, 从而使用户获得最合理的响应时间, 满足不同用户的要求。
摘要：二分图是图论当中一种特殊的模型, 求带权二分图的最佳匹配算法对许多具有最优解的实际应用问题的解决是准确和高效的。针对多机系统的操作系统的一类多机调度问题进行了分析, 建立了该问题的二分图模型并给出了二分图匹配的算法, 对所给算法的复杂度进行了分析和讨论。实验结果验证了所提出方法的有效性。
关键词：二分图,匹配,最优解,多机调度问题
参考文献
[1]BONDY J A, MURTY U S R.Graph theory with application[M].London:Macmillan, 1976.
[2]Guizhen Liu, Binhai Zhu.Some problems on factorization with con-straints in bipartite graphs[J].Discrete Applied Math, 2003 (128) :421-423.
多模式匹配 篇7
近年来, 随着立体视觉的发展, 高精度稠密的立体匹配成为研究的一大热点。其最大的挑战在于遮挡、物体边界、精细结构部位等出现错误模糊而无法完整重现原本样貌。这很大一部分原因是低纹理或重复的纹理, 视差不连续, 以及实际中记录和照度差异等。此外, 采集的图像往往由于量化处理的原因使得到的视差只能精确到整像素级, 导致三维重建的效果呈现出栅栏现象。针对上述影响因素, 本文重点研究采用多策略融合方法解决这个病态优化问题, 在稠密匹配的基础上将匹配视差精度提高到亚像素级别, 同时尽量减少误匹配。
由middlebury立体视觉评价网[1]可知, 近年来有众多的学者在这一方面做出了努力。亚像素精度的匹配算法大体分为基于插值拟合的方法和基于相关性的方法。而基于插值拟合的算法有: 文献[2]提出对聚集代价进行抛物线拟合得到亚像素视差, 但是这个方法求得的亚像素视差明显带有像素锁定现象。而文献[3]相比文献[2], 减少了线性相似度策略产生的视差错误。文献[4]将最小均方根误差作为测度算子引入到置信度传播优化中从而匹配到亚像素精度。文献[5]提出在小的分割平面上进行视差平面拟合, 估计出亚像素视差, 但是拟合的结果受分割结果的影响很大, 而且大量的小平面拟合时间复杂度大。与此相比, Psarakis[6]提出了加强互相关算法, 通过在计算匹配代价时对邻域线性插值, 经局部一维优化, 从而得到亚像素视差, 但此算法采用局部优化, 使得计算量非常大。Nehab等[7]在此基础上提出系统偏移的实质性问题, 通过在视差空间上进行二维拟合来迭代贴近真实亚像素值。但是针对每一副图像参数都不同, 实现较繁琐。而Gong等人[8]提出基于拟合的视差梯度朝向平面来重新估计亚像素视差的方法, 虽然有效, 但是作者应用Yoon等人[9]的自适应权值方式, 拓展为三维自适应权重聚集, 需要重新计算每个像素在聚集窗内的代价值计算量太大。以上这些基于相关性的算法, 虽各有优劣, 但都不会出现像素锁定的现象。
此外, Gehrig等人[10]提出的分数视差与重力约束的概念, 使得视差精度进一步改善达到了0. 25 个像素级。而杨[11]提出非局部代价聚集策略将整幅图像看成一个最小生成树结构进行全局代价寻优, 可以得到较好的视差, 速度快, 但仅仅得到整数级视差, 同时也存在部分明显的误匹配点。本算法受此文启发而展开研究。
本文采用多策略融合的亚像素精度立体匹配算法。首先, 在匹配代价计算之前, 采用Sinc插值策略对源图像对进行scale行插值, 对应的视差范围也按scale值进行扩充, 得到扩充的图像对, 分析源图像中相邻像素的灰度梯度关系, 确定对应每个像素的视差搜索范围, 从而减少匹配代价计算量。其次, 采用最小生成树策略进行代价聚集以选取最优的分数视差。最后, 采用视差图像上对应分割区域的外点去除与视差平面拟合进行视差优化。
1 分数视差初始匹配
杨[11]等人将双线性滤波方法与匹配算法相结合, 得到较好的匹配效果, 同时使用基于树结构最优化算法能够快速有效的查找极值点。其主体思想是将整幅图像看成一棵树, 所有像素表示为节点, 通过像素之间的相似度来构造最小生成树, 确定匹配代价聚集路径。与以往算法不同的是它的每一个像素点都受到树上其它所有像素点的影响, 而不是仅仅由某个局部矩形聚集窗口中的像素点影响, 也无需计算全局算法中的能量函数。
本文在此基础上进行改进, 采用新的方式确定每个像素点的视差搜索范围, 在分数视差上聚集代价, 从而获得分数视差图像。
1. 1 Sinc插值策略对源图像对进行scale行插值
在文献[12]中, 作者已经通过傅里叶分析证明Sinc插值是目前最好的插值方法, 因此, 在本算法首先对左右图像以scale= 1, 2, 4 进行行方向上的Sinc插值, 再计算对应分数视差上的匹配代价。
1. 2 计算匹配代价
对插值后的左图I中一点pscale, 对应于右图J扫描线上的任意一点pscale' , 计算这两点的相似性即匹配代价, 计算公式如下:
其中 ( pscale, pscale') 为一对待匹配点, ‖▽Ipscale- ▽Jp'scale‖ 是对应点的灰度梯度差值, α , τcol, τgrad均为常量, τcol, τgrad分别为颜色与梯度截断阈值。
理论上, 对于图像上的每一个像素点, 对应每一个视差等级都需要求解相应待匹配点的匹配代价。而实际上, 当参考图像I的行扫描线上有两相邻点p, q, 若在右图像J中有对应匹配点p', q', 那么就有p' - q' = ( 1 + cx × px) ( p - q) 成立, 其中cx × px是一个相对恒定的值, 它由基线距离和焦距共同决定。当且仅当p, q不为遮挡点的情况下上式也可以简化为;其中有恒定满足条件的b > 1。确定阈值bth, 使得:
从而可以利用相邻像素对应匹配点之间的关系来减少视差搜索范围。
1. 3 生成视差图
匹配代价之后, 对于左右图像, 分别进行如下处理:
a) 沿着最小生成树的聚集路径, 进行匹配代价聚集, 聚集方式参考文献[11]。图上所有像素点在每一个可能的视差等级上都可以得到相应的聚集代价值。
b) 通过WTA策略求取聚集代价全局最小值, 从而得到对应的左右视差图像。
1. 4 视差后处理
由于噪声干扰常常会引起错误, 分别对结果进行加权中值滤波、左右一致性检查, 从而得到初始视差D ( p) , 并将像素分类为稳定像素点与不稳定像素点 ( 包括遮挡与误匹配) 。对于视差匹配稳定点, 本文根据式 ( 3) 进行像素间的代价更新, 使得匹配稳定点在匹配正确的视差上代价具有最小值, 而偏离正确的视差越远, 其代价越大。对于不稳定点, 则将其在任意视差等级上的代价全部重置为0。
其中thc = 0. 1 × dmax+ 0. 5 ;
若此时用WTA重新选取视差, 那么得到的视差图像D' ( p) 保持了所有稳定点的视差D ( p) , 而在不稳定点, 则全部置为0。此时, 对整张图上所有像素点, 将更新的代价值沿着MST聚集路径重新进行代价聚集, 重新进行视差选择, 就可以使得视差快速地从稳定点逐渐传播到不稳定的点。这种方式处理有两个优点, 一是直观有效, 二是不稳定点的数量即“洞”的尺寸可以不受影响, 而相比之下, 传统的采用局部滤波只能处理较小的“洞”。
通过上述处理, 再按Sinc插值的scale值进行下采样处理, 就可得到分数视差。
当scale = 1, 2, 4 时分别得到为整像素级视差, 1 /2 像素级视差和1 /4 像素级视差。
2 亚像素精度上的视差优化
在上述步骤中得到是相对正确的分数视差图像D″ ( p) , 即得到的分数视差已经达到1 /2 像素级或者1 /4 像素级。本节提出了一种新的亚像素精度下进行视差优化的方案, 进一步提高匹配精度。
由于聚集错误、噪声、遮挡等因素的影响, 上述算法实验过程中可能出现匹配错误区域, 如左右一致性检查结果是稳定点, 经过传播后获得的视差值出现明显错误区域如图1 所示: teddy视差图像黑色区域以及其边缘区域, 该类错误大多发生遮挡区域与低纹理区域。
由图2 可知, 分数视差的误匹配图像 ( 灰色区域) 与图1 中的误匹配区域 ( 黑色区域与teddy熊左边区域) 部分相同。
实验数据显示, 整数视差图像与标准视差图像比较差值大于1 的像素的误匹配率 ( % err) 为7. 04% , 而对应的分数视差图像与标准视差图像比较差值大于1 的像素的误匹配率为6. 94% , 误匹配率减少了0. 1% 。观察可知, 误差主要发生在误匹配与视差不连续区域, 而在丰富纹理区域达到了较好的效果。
针对上述问题, 在此引入Mean-Shift图像分割和视差平面拟合的思想来检测与校正错误视差, 同时在亚像素等级上进一步优化视差。视差平面公式如下:
其中 ( px, py) 为当前像素点坐标, f ( p) 为拟合平面值, a, b, c为待拟合的平面参数。
由于彩色图像在低纹理区域通常有较一致的色彩分布, 分割结果显示的区域较大的特性。与此同时, 文献[5]中给出这样一种假设: 每个分割面上的视差变化平缓, 每个分割面近似于一个平面。基于此, 这部分只针对较大的分割区域 ( 比如区域像素数量大于300) 进行迭代平面拟合操作, 而较小的分割区域自动舍弃不做处理, 从而逐步优化像素点视差。这样做一方面对低纹理区域的像素视差在亚像素等级上进行平滑, 得到连续的视差, 另一方面校正那些左右一致性检查也无法检测出的错误视差。
本算法具体做法是对每一个分割区域, 检测视差图上属于本区域的像素视差, 如果属于待处理的大区域, 那么依上式进行平面拟合, 当且仅当拟合平面值与实际的视差之间的偏差小于1 的像素数量大于本次拟合总数的90% , 则此次拟合成功, 用拟合值代替原本视差值。否则, 将挑选当前区域内邻居像素视差变化在一个像素之内的那些像素对应的视差值组合成新的待拟合数据集合进行再次拟合。与此同时, 计算得到初始平面拟合值与实际视差偏差大于10 的像素, 本算法认为这些像素点是外点outlier, 予以标记, 对应的视差值用成功拟合的平面值进行校正。上述过程可用公式表示如下:
其中seg ( i) 表示第i个分割区域, num ( seg ( i) ) 表示第i个分割区域内的像素总数, num ( | D″ ( p) - f ( p) | < 1) 表示在此次拟合过程中拟合值与拟合数据值之间差值小于1 的像素数量, 当flag = 1 时需要进行再次拟合。
在这个过程中可以看到有部分的拟合视差与实际的视差偏差大于一个视差等级, 实验可以发现这是由于彩色图像分割过程中出现的错误分割结果, 使得原本不属于同一个平面的视差值拟合为了同一个平面值。在这里不继续探讨如何更正确的分割问题, 本算法的做法是对这分割区域的视差值进行筛选, 拆分成多个视差平面数据点集, 再对每个视差点集合分别进行平面拟合。
3 实验结果与分析
系统的软件部分是基于Open CV与Open GL的应用程序, 开发环境为VS2008, 算法程序用C + + 实现, 程序运行平台为主频3 GHz, 内存1GB的PC机, 硬件部分由两台普通的数码相机平行搭建组成。本算法中用到的主要参数设置为: σ = 0. 1, bth= 1. 2, α = 0. 9, τcol= 7, τgrad= 1. 5, 本文选取Tsukuba, Venus, Teddy, Cones四对标准图像进行实验, 四组图像中每组图像分别用四幅图像来呈现效果, 依次为原整数视差图、本算法亚像素化后的视差图像、标准视差图像、获得视差图与标准视差差值为1时的误匹配图像 ( 即通常意义上的“bad pixels”) , 实验结果如图3 所示。
由上面的组图可知, 四组图像对应的第二幅与第一幅对比, 明显在错误匹配点区域所改善, 同时, 在低纹理区域视差更加平滑, 视差更加精细连续, 而不再出现层叠的条纹现象, 边界也非常的清晰。
图4 表示的是在初次视差一致性检查中未能检测到而在平面拟合优化过程中检测出来的teddy误匹配图像, 这在之后的处理过程中进行了视差校正, 如图3 ( c3) 、 ( c4) 比较可知误匹配率明显减少正确率进一步提高了; 同时, 图5 是本算法过程中得到的cones视差不连续图像, 具有较高的正确性。
由表1 和表2 的数据 ( % err表示错误匹配率, MSE为均方根误差, Before表示的是整数视差图像对应的各数值, 本表中After s = 2 表示当scale = 2 时, 处理后的视差图像对应的各个数值) 可知, 与原整数视差图像相比, 本文算法对四对实验图像处理获得的视差图像的错误匹配率与均方根误差都减少了, 其中, 平均错误匹配率减少了大概16% , 而均方根误差减少了大概20% 。综合上述实验结果可知, 本文算法在将匹配精度从整数级通过两步法提升到0. 5 或者0. 25 个像素以下的亚像素级别, 有效地实现精度改善的过程。同时, 误匹配数量的重新检测与校正, 也一定程度上改善了匹配精度。
4 结语