基于双序列比对算法的立体图像匹配方法开题报告

1. 研究目的与意义

提出了一种基于生物信息学中双DNA序列比对算法的图像立体匹配新方法。图像立体匹配和生物信息学中双DNA序列比对的实质都是在匹配准则下搜索最佳匹配基元,因而新颖地将双序列比对算法引入图像立体匹配。首先介绍了基于动态规划的双序列比对算法原理及其用于图像立体匹配的实现方法,然后根据左右摄像机的最大视差是一个有限定值,进行了算法改进,极大地减少了计算量,并给出了VC6.0中的实现流程,最后采用4组不同的图像对进行了实验验证。该方法具有较低的计算复杂度和适宜于并行计算的特点,生成的视差图效果表明双序列比对算法为图像立体匹配提供了一个实用有效的方法.

在分析现有立体匹配方法的基础上,提出一种基于双序列比对算法的立体图像匹配方法。将立体图像对中同名极线上的像素灰度值看做是一对字符序列,使用基于动态规划思想的双序列比对算法对这些对字符序列进行匹配,以获取立体图像视差。为验证该方法的可行性和适用性,采用人脸立体图像对进行实验。实验结果表明,使用该方法进行立体图像匹配能获得光滑的、稠密的视差图。基于动态规划思想的双序列比对算法能够有效地解决立体图像匹配问题,从而为图像的立体匹配提供了一个实用有效的方法。

2. 国内外研究现状分析

创建人物模型，道具和游戏场景基于立体视觉恢复景物的深度信息,在机器人避障导航、运动目标跟踪、识别和生物医学等领域有着广阔的应用前景。

显然,由景物深度信息z与视差(disparity)d的关系(d=bf/z,式中b为基线距离;f为相机焦距)不难看出,若两个相机的相对位置及焦距已知,由视差图(disparitymap)能很容易地计算出场景中景物的深度信息,其关键在于如何快速、准确寻找同一场景在相机拍摄的左右两幅图像上的对应点[,即立体匹配问题。

因此,立体匹配一直是计算机视觉领域的一个热点研究问题,国内外广大研究人员已经提出了很多匹配算法,归纳起来,主要可分为基于区域、基于特征[和基于相位3类方法,其实质都是在匹配准则下搜索最佳匹配基元。

3. 研究的基本内容与计划

序列比对是生物信息学的核心研究内容之一。在生物学研究中,通过判断两个序列是否具有足够的相似性,从而判断两者是否具有同源性,常常需要进行序列比对,根据同时进行比对的序列数目分为双序列比对和多序列比对。经过40多年的发展,双序列比对问题已基本解决。本文正是拟将双序列比对算法引入图像立体匹配。dna序列由a、t、c、g四种碱基组成,从而一个dna序列就可视为由这4个字母组成的字符串。双序列比对算法,就是根据给定的计分函数计算在待比对的两个字符串中插入空格2的适当位置和数量,从而得到两个序列之间的最大相似性排列,也就是实现了最优比对。插入空格 2的数量可视为左右两幅图像中对应点间的视差。例如两条dna序列tgcgt和atggt,希望通过对每条字符序列插入空格,得到使两条序列的匹配字符数最大的最佳比对,具体算法过程如下:用s表示待比较的前一序列,t表示后一序列,s(i,j)表示得分矩阵中s的第i个字符和t的第j个字符的最佳队列的分数,g表示一个间隔分数,表示s中第i个字符与t中第j个字符匹配的分数。在生物信息学中,当正确匹配时,分数加2;误匹配时,分数减1,间隔罚分g取-1。

给定计分函数:

s(i,j)=max

4. 研究创新点

从序列比对的实际意义出发,如果两个序列较为相似,那么最优比对只需沿得分矩阵的对角线(左上至右下),在其上下一定范围内进行规划就可以得到。

对于表1和表2,假定最大视差值为1,则不需要计算全部的动态规划表,如表3所示,只计算对角线及其上/下移一个位置的元素。

因此,可将计算复杂度从o(mn)缩减至o(dm)或o(dn),取m、n中较大者。