基于生物信息学中双DNA序列比对算法的图像立体匹配及其实现精.docx
《基于生物信息学中双DNA序列比对算法的图像立体匹配及其实现精.docx》由会员分享，可在线阅读，更多相关《基于生物信息学中双DNA序列比对算法的图像立体匹配及其实现精.docx（16页珍藏版）》请在冰点文库上搜索。
基于生物信息学中双DNA序列比对算法的图像立体匹配及其实现精
第15卷 第1期
2007年1月 光学精密工程
OpticsandPrecisionEngineering
Vol.15 No.1
Jan.2007
收稿日期:
2006204210;修订日期:
2006206206.
基金项目:
国家自然科学基金资助项目（No.50405046和No.60605028;上海市科委资助项目（No.045107031;上
海市优秀青年教师培养计划资助项目（No.04Y0HB094;上海大学优秀青年教师后备人选科研项目
文章编号 10042924X（20070120106206
基于生物信息学中双DNA序列比对
算法的图像立体匹配及其实现
谢少荣1,王东红2,罗 均1,龚振邦1
（1.上海大学机电工程与自动化学院,上海200072;2.广西财经学院,广西南宁530002
摘要:
提出了一种基于生物信息学中双DNA序列比对算法的图像立体匹配新方法DNA序列比对的实质都是在匹配准则下搜索最佳匹配基元,。
首先介
有限定值,进行了算法改进,极大地减少了计算量,最后采用4组不同的图像对进行了实验验证。
生成的视差图效果表明双序列比对算法为图像立关 键 词:
序列;双序列比对;对应点中图分类号:
Q2334;文献标识码:
A
Novelstereomatchingalgorithmbasedonpair2wiseDNA
alignmentalgorithminbioinformaticsanditsimplementation
XIEShao2rong1,WANGDong2hong2,LUOJun1,GONGZhen2bang1
（1.SchoolofMechatronicsEngineeringandAutomation,ShanghaiUniversity,Shanghai200072,China;
2.GuangxiUniversityofFinanceandEconomics,Nanning530002,China
Abstract:
Anovelstereomatchingalgorithmbasedonpair2wiseDNAalignmentalgorithmispresen2ted.Theessentialofbothstereomatchingandpair2wiseDNAalignmentinbioinformaticsisthatthecorrespondencepointsaresearchedbymatchingcriteria,sothepair2wiseDNAalignmentalgorithmisintroducedtodesignanewstereomatchingalgorithm.Firstly,theprincipleofthedynamicprogram2mingandimplementationoftheproposedalgorithmarepresented.Then,thisalgorithmissignificant2lyimprovedtoreducethecalculationdrastically,becausethereisamaximumpossibledisparitywhosevaluecanbederivedfromthefieldofviewofthecameras,thephysicaldistancebetweenthetwocam2eras,andthefocallengthofthecameras.TheflowofthealgorithmisdesignedindetailwithVC6.0.Finally,thedisparitymapsofseveraldifferenttestimagesbymeansofthisalgorithmareshown,theadvantagesarelowcomputercomplexityandparallelprocessing.Theresultsshowthattheproposedalgorithmisusefuland
effective.
Keywords:
stereomatching;stereovision;DNAsequence;pair2wisealignmentalgorithm;correspon2dencepoints
1 引 言
基于立体视觉恢复景物的深度信息,在机器人避障导航、运动目标跟踪、识别和生物医学等领域有着广阔的应用前景。
显然,由景物深度信息z与视差（Disparityd的关系（d=BF/z,式中B为基线距离;F为相机焦距不难看出,若两个相机的相对位置及焦距已知,由视差图（Disparitymap能很容易地计算出场景中景物的深度信息,其关键在于如何快速、准确寻找同一场景在相机拍摄的左右两幅图像上的对应点[122],
问题。
因此,
一个热点研究问题,
出了很多匹配算法,
域[324]、基于特征[527]和基于相位[8210]3类方法,其实质都是在匹配准则下搜索最佳匹配基元。
这些方法都各有其优缺点:
基于特征的匹配是对图像对的特征区域进行匹配,其优点是速度快、能得到比较精确的匹配,但只能得到稀疏的视差图,无法处理特征不明显的场景图像;基于区域的匹配可以直接产生致密的视差图,但其主要缺点是计算复杂度大;基于相位的匹配,是利用具有局域频率特征的相位信号作为匹配基元进行匹配,具有从粗到精的多分辨率特性,也可以进行每个像素的匹配,但一般只能得到景物的粗糙结构,有时还需进行特殊处理。
无独有偶,在现代生物信息学中,通过序列比较,在已知结构和功能的序列数据库中找出与新测定序列具有相似性的同源序列,从而以足够的可信度确定新序列的结构和功能信息,因而寻求更快更灵敏的生物序列相似性比对算法也一直是生物信息学的研究热点。
经过40多年的发展,双序列比对算法已基本实现,序列比对的未来发展方向是基因组比较,双序列比对是其重要基础。
该比对方法具有较低的计算复杂度和适宜于并行计算的特点[11215]。
图像立体匹配和序列比对的实质相同,都是在匹配准则下搜索最佳匹配基元。
因此,本文新颖地将生物信息学中双DNA序列比对算法引入
图像立体匹配,该方法具有较低的计算复杂度和适宜于并行计算的特点。
2 生物信息学中双DNA序列比对算法
一。
在生物学研究中,
,根据同时进行比对的序。
经过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=
S（i-1,j+g
S（i,j-1+g
S（i-1,j-1+P（i,j, （1由式（1可以看出,从三个方向可以到达矩阵元素（i,j:
对角线方向元素、同一行或同一列
的元素。
在得分矩阵中,到达位置为（i,j的某一个元素有三种可能的路径:
通过位置（i-1,j-1的对角方向,没有空位罚分;通过列j的垂直701第1期谢少荣,等:
基于生物信息学中双DNA序列比对算法的图像立体匹配及其实现
方向和通过行i的水平方向,空位罚分取g。
再
取3个分值中的最大值作为该矩阵元素的得分,进行递归计算,实现动态规划。
对于边界初始分数取值为:
S（i,0=S（0,i=g3i,
（2依据上述计分函数所得得分矩阵如表1所示:
表1 双DNA序列比对得分矩阵
Tab.1 Scorematrixofpair-wiseDNAalignment
algorithm
（i=m,j=n开始,通过动态规划回溯法,追溯序列比对的最优结果,其路径见表（1中箭头所示。
若箭头为对角线,则在比对后的序列中两个碱基相对应;若箭头为水平方向,则在s序列的相应位置插入一个空格‘2’;若箭头为垂直方向,则在t序列的相应位置插入一个空格‘2’。
比对结果有两种情况:
s’2TGCGT和 2 TGCGTt’ATG-GT
ATGG-T
表2 改变误匹配罚分值后的得分矩阵
Tab.2 Scorematrixwhenmismatchis-
2
显然,后一种结果不是最优的,主要原因在于有误匹配,因此通过加大误匹配时的罚分值能改进上述比对。
误匹配时,按分数减2计算的得分矩阵如表2所示。
表2中箭头所示回溯路径即为最优比对结果。
3 基于双序列比对算法的立体匹配
方法
假设左右两幅图像是由两个完全相同的摄像
机同时拍摄同一场景所得,且两个图像平面位于同一个平面上,两摄像机坐标系的x轴平行,光轴相互平行,这样场景中的同一特征点在两个摄像机图像平面上的成像位置只具有水平视差,而且外极线与图像行平行。
因此,可以将两幅图像,其特征B,将双序列比对算,插入。
如图1所示,场。
左图像中的一极线上的像素灰度值为（0,0,0,0,0,255,255,255,0,0,同时在右图像中相应极线上的像素灰度值为（0,0,0,255,255,255,0,0,0,0。
应用第2部分中的比对算法得到的最优比对结果为
:
图1 图像的字符串表示
Fig.1 Intensity（brightnessvaluesofagrayscale
image（orRGBvaluesofacolorimagecanbeinterpretedasthecharactersofthestrings
0000025525525522 000002225525525500
00
显然,从左图像中的第4个像素开始,增加了2个像素视差。
实际图像易受噪声、光照的影响,会造成左右两幅图像中对应像素点的灰度值或RGB值有些差异,为了保证该匹配算法的稳定性、容错性,可视实际情况设定匹配/误匹配的灰度值或RGB值的差异阈值。
8
01 光学 精密工程
第15卷
4 算法改进
从序列比对的实际意义出发,如果两个序列较为相似,那么最优比对只需沿得分矩阵的对角线（左上至右下,在其上下一定范围内进行规划就可以得到。
对于表1和表2,假定最大视差值为1,则不需要计算全部的动态规划表,如表3所示,只计算对角线及其上/下移一个位置的元素。
因此,可将计算复杂度从O（mn缩减至O（dm或O（dn,取m、n中较大者。
在实际图像立体匹配中,摄像机的视场、两个摄像机间的物理距离和摄像机的焦距长度都是一定的,所以其最大视差是一个有限的定值,因而也可利用上述改进算法
来大大减少搜索空间,缩小计算量。
图2 基于双序列比对算法的立体匹配流程图
Fig.2 Flowofanovelstereomatchingbasedonpair2
wisealignmentalgorithm
表3 限定了动态规划范围的得分矩阵
Tab.3 Scorematrixlimitedbydynamicprogrammingrange
j
0 1 2345
0 0-1T
1-1
-1 1
G2-2
03C3-1
22G41
43 经以上设计,基于生物信息学中双序列比对算法的图像立体匹配新方法在VC6.0中的实现流程如图2所示。
5 实验结果
为了便于和其他算法进行横向比较,检验序列比对算法的立体匹配效果,本文选用了立体匹配实验常用的一对下载自德国波恩大学计算机视觉研究小组的网页http:
//www2dbv.informa2tik.uni2bonn.decorridor,图像大小是256×256,如图,在P4/1.6GHz/（亮度小的点表示;灰度值越大（亮度大的点,即深度越小,例如视差图中的球、圆锥和走廊尽头的墙壁,其灰度是由浅到深,深度信息相当明显。
图中上部分的文本框是输入信息,包括左右原图像、视差范围
、匹配分数、补偿间隔等。
图3 corridor原始像对
Fig.3 Originalimages
图4 用本文算法得到的视差图
Fig.4 Ourdisparitymap
与采用基于遗传算法和基于Hopfield网络的实验结果（如图5所示相比较,本文算法生成
9
01第1期
谢少荣,等
:
基于生物信息学中双DNA序列比对算法的图像立体匹配及其实现
的视差图效果明显优于这两者,非常清楚地把图
像对中的各个景物按深度信息分开了层次。
在硬件条件相当的情况下,基于Hopfield网络的匹配时间是39.7s,而本文算法的运行时间是1.56s,比基于区域的灰度相关算法的运行时间减少了30~50倍。
对实际图像（如图6（a和（b所示匹配的效果如图6（c所示,计算产生的视差图密度大,定位精度高。
综上所述,本文算法是一种匹配质量高、速度快的图像立体匹配算法
。
（a遗传算法（（aGenetic（bHopfieldnetwork
图5 其他算法所得corridor的视差图
Fig.5 Otherdisparity
maps
（a （b
（c
图6 实际图像对及其视差图
Fig.6 Trueimagesanddisparitymap
本文提出的基于序列比对的立体匹配算法已
实际应用于远距离场景中动态目标深度信息的实
时获取。
图7和图8分别是目标距离为54m和
57m处的获取情况。
像对中白框所标示的动态目标正在向左侧路边靠近,图像对上方的文本框中是实时获取的深度信息显示
。
图7 目标距离54m
Fig.7 Objectof54
m
图8 目标距离57m
Fig.8 Objectof57m
根据实际应用情况,每对像对只取动态目标
周围50×50的区域进行匹配,处理速度为10pixel/s,完全能满足机器人动态避障的应用要求。
6 结 论
本文将生物信息学中已成功实现的双序列比
对算法引入图像立体匹配,该方法具有较低的计算复杂度和适宜于并行计算的特点。
实验证明该算法给立体匹配提供了一个既具有低计算复杂度又能生成致密视差图的实用方法,匹配质量高、速度快。
11 光学 精密工程
第15卷
第1期谢少荣,等:
基于生物信息学中双DNA序列比对算法的图像立体匹配及其实现111参考文献:
[1]GDANG.Pointmatchingunderlargeimagedeformationsandilluminatinchanges[J].IEEEComput.Soc.,BO[2]朱明,鲁剑锋,胡硕.采用DSP的电视测量跟踪器的研制[J].光学精密工程,2005,13（Supp.:
2322235.[7]徐瑞鑫,刘伟宁.基于自适应模板的实时跟踪算法[J].光学精密工程,2002,10（4:
3652369.369.（inChinese[11]张敏.生物序列比对算法研究现状与展望[J].大连大学学报,2004,25（4:
75279.79.（inChinese1975,18（6:
3412343.263.net1999,70:
1292139.（4:
4632466.（inChinese（2:
2072212.（inChineseConferenceonPatternRecognition,1996,4512455.[3]KANADET,OKUTOMIM.Astereomatchingalgorithmwithanadaptivewindow:
theoryandexperiment[J].[4]SUNCH.Afaststereomatchingmethod[C].DigitalImageComputingandApplications,1997:
952100.[10]叶海加,陈罡,邢渊.双目CCD结构光三维测量系统中的立体匹配[J].光学精密工程,2004,12（1:
71275.[12]王宏漫,欧宗瑛.进化算法在DNA序列比对中的应用[J].数据采集与处理,2002,17（4:
4632466.WANGHM,OUZY.Evolutionalgorithmforsequencealignment[J].J.DataAcquis.[15]唐玉荣,汪懋华.基于动态规划的快速比对算法[J].生物数学学报,2005,20（2:
2072212.Opt.PrecisionEng.,2004,12（1:
71275.（inChineseces.,1997,6（10:
146021464.IEEETrans.PatternAnal.Mach.Intel.,1994,16（9:
9202932.PrecisionEng.,2004,12（3:
3112315.（inChinese作者简介:
谢少荣（1972-,女,湖北天门人,博士,副教授,主要研究方向为计算机视觉和智能控制等.E2mail:
srxie@[5]CANDOCIAF,ADJOUADIMA.Similaritymeasureforstereofeaturematching[J].IEEETrans.Imag.Pro2[6]姜凯,陈海霞,刘立峰,汤建华.基于模板抽样的快速图像匹配算法[J].光学精密工程,2004,12（3:
3112315.[J].Mach.VisionAppl.,1998,11（2:
83295.JIANGK,CHENHX,LIULF,TANGJH.Fastimagematchingalgorithmbasedontemplatesampling[J].Opt.[8]FROHLINGHAUST,BUHMANNJM.Regularizingphase2basedstereo[C].ProceedingsoftheInternationalYEHJ,CHENG,XIANGY.Stereomatchingin3DmeasurementsystemusingdoubleCCDstructuredlight[J].[13]DAVIDRP.Aversatiledivideandconquertechniqueforoptimalstringalignment[J].Inform.Proces.Lett.,[14]HIRSCHBERGD.Alinearspacealgorithmforcomputingmaximalcommonsubsequences[J].Comm.ACM,[9]CRESPIB,ALEXG.Analogcomputationforphase2baseddispari
升级会员 