基于区域增长的立体像对稠密匹配算法
第27卷 第7期2004年7月
计 算 机 学 报
CHINESEJOURNALOFCOMPUTERS
Vol.27No.7
July2004
基于区域增长的立体像对稠密匹配算法
唐 丽 吴成柯 刘侍刚 颜尧平
(西安电子科技大学ISN国家重点实验室 西安710071)
摘 要 该文提出了一种新的基于区域增长的立体像对稠密匹配算法,该算法适用于多种图像对,包括存在较大视差的未经校准的图像对和其中某些纹理稀疏的区域.首先用新的两层算法匹配图像对中的种子点,匹配关系再根据两种策略由这些种子点向图像的其余部分传播.区域增长过程中以新的加权差值平方和准则作为目标函数,模板窗的大小根据其中包含的纹理数量动态变化,而搜索窗的大小与可信系数成反比.对真实立体像对的稠密匹配结果表明了该算法具有良好的性能.
关键词 区域增长;稠密匹配;自适应窗;加权SSD中图法分类号TP391
ImageDenseStereoMatchingbyTechniqueofRegionGrowing
TANGLi WUCheng Ke LIUShi Gang YANYao Ping
(NationalKeyLaboratoryofIntegratedServiceNetworks,XidianUniversity,Xi an710071)
Abstract Anewdensestereomatchingalgorithmispresentedbasedontechniqueofregiongrowing,whichcanbeappliedtoawiderangeofimagepairsincludingthosewithlargedisparityorwithoutrec tificationevenifpartoftheimagesarelesstextured.Firstly,anumberoffeaturepointsintheimagepairarematchedusinganewtwo levelmatchingmethod.Thenthesereliablymatchedpointsaretak enastheseedsfromwhichcorrespondingrelationspropagatetowardsotherregionsoftheimagesundertwostrategies.WeightedSSD(SumofSquaredDifference)isdevelopedasthetargetfunction.Thesizeofthetemplatewindowisadaptivewithtextureswithinitandthesizeofthesearchwindowisvariedininverseproportiontotheconfidencecoefficient.Thealgorithmhasbeentestedwithrealstereoimagesandtheresultsdemonstrateitsaccuracyandefficiency.
Keywords regiongrowing;densematching;adaptivewindow;weightedSSD
重建的质量具有十分重要的意义.为了求解匹配问
1 引 言
图像匹配就是寻找两幅或多幅图像中对应点的过程,它是计算机科学领域,特别是计算机视觉领域引人注目而又极富挑战性的研究课题.稠密匹配希望在图像对之间找到尽可能多的匹配点,它对三维
题,通常需要引入一些约束条件:(1)对极几何约束,即对于左图像中的任一点,它在右图像中的匹配点必定位于相应的对极线上.(2)相似性约束,即假设对应点的灰度值或颜色是相同的,因此一般在匹配中利用的都是图像的灰度信息.(3)唯一性约束,即所求点的匹配点是唯一的.(4)连续性约束,即假设
收稿日期:2003 01 14;修改稿收到日期:2003 09 08.本课题得到国家自然科学基金(60002007)和中法合作研究基金(PRASI00 04)资助.唐 丽,女,1975年生,博士研究生,主要从事数字图像处理、计算机视觉和模式识别等方面的研究工作.E mail:[email protected].吴成柯,男,1938年生,教授,博士生导师,主要从事图像处理、图像通信和计算机视觉等方面的研究工作.刘侍刚,男,1973年生,博士研究生,主要从事数字图像处理、计算机视觉等方面的研究工作.颜尧平,男,1968年生,博士,主要从事视频压缩编码、无线视频和图像
7期唐 丽等:基于区域增长的立体像对稠密匹配算法
937
物体表面是光滑的,这意味着它们的视差(disparity)是连续变化的.区域增长就是利用这一约束条件解决稠密匹配问题的一种简洁而有效的途径.
传统的稠密匹配算法为窗匹配法,它通过比较图像间一个窗口之中相邻像素的灰度相似性来确定窗口的中心点是否匹配,而选择适合的窗口大小对得到一个光滑而清晰的深度图(depthmap)是十分关键的.最优的窗口大小选择取决于纹理和视差的局部变化量.一般说来,使用小窗口能够避免过度的平滑,然而在纹理少的区域,却难以得到可靠的匹配结果.另一方面,当窗口内视差变化时,由于投影形变,窗口内的灰度值可能并不对应.这些都是窗匹配算法中存在的主要问题.
近年来各国学者对其它一些方法也进行了不断的深入研究.在经过校准(rectification)的立体像对中,可以认为对极线与扫描线重合,这时的搜索区域由二维搜索窗减小为一维对极线(扫描线),极大地简化了搜索过程,提高了匹配算法的效率,并有效地消除了多解问题.但校准过程依赖于精确的对极几何估计,或者必须计算出对应对极线的均值和方差以确定其包络.自适应窗匹配算法[1]采用的窗口大小和形状根据灰度的局部变化和当前深度的估计值自适应地变化,提高了匹配质量,但是它的计算复杂度是很大的.使用动态规划方法解决立体匹配问题[2]将边缘作为匹配的基本元素.推广的动态规划算法[3]将立体匹配问题转化为最大流问题(maxi mum flowformulation).求解后,与最大流相关联的最短路径(minimum cut)可以一次性给出整个图像的视差表面.由这种全局算法得到的视差图比由传统的逐行算法得到的视差图更准确,也更为连贯.协同迭代算法(cooperativealgorithm)法(volumetriciterativeapproach)
[5][4]
2 种子点的鲁棒性两层匹配算法
基于区域增长的稠密匹配算法的第一步是选取一些种子点,并对种子点进行匹配.种子点匹配的准确与否直接影响了算法的性能.实验中只需要在一幅图像的中部选取几个种子点进行匹配,就可以开始区域增长了.我们对选取的种子点应用一种新的两层算法求其匹配点.首先对初始图像对应用边缘检测算子提取边缘.常用的边缘检测算子有许多种,如Canny算子、Prewitt算子等.
边缘提取之后,比较所得二值图像对的边缘相似性,取得种子点基于图像轮廓的粗略匹配,从而得到匹配种子点的大致范围.在这第一层的匹配中,通过采用较大的模板窗可以得到可靠的匹配结果,同时用稀疏矩阵表示的二值边缘图像又简化了计算.虽然使用较大的模板窗会使视差突变点处的边缘模糊,但是第一层匹配的主要目的是确定匹配点的大致范围,避免重复图案之间大的误匹配,解决匹配点可靠性的问题,而其精确性问题可以在加入灰度信息之后,通过第二层的精细匹配得到改善.
为了不丢失灰度信息,我们在边缘匹配的基础上,对种子点的灰度相似性进行比较.这时的搜索范围仅限于边缘匹配点的一个较小邻域之内.模板窗也恢复到正常大小,实现对匹配点的精确定位.这种由粗到细的匹配与人的视觉形成过程是一致的,即首先比较图像轮廓相似性,再根据局部信息比较细节相似性.用边缘匹配的结果限制灰度匹配的搜索范围,与基于三角剖分的稠密匹配算法[8]的基本思想是一致的.所不同的是,后者以特征点为顶点,将图像剖分为许多三角形,再用这些小三角形来限制搜索范围.在本算法中,第一层匹配采用的较大模板窗包含了获得可靠结果的足够多的灰度变化(边缘)信息.第二层匹配采用较小模板窗,避免了在所得到的视差图中出现过度的平滑.在第一层匹配的基础上,第二层匹配的搜索区域限制在一个较小的范围内,因此可以有效地消除多极值的出现.
总之,对种子点使用两层匹配算法的原因如下:(1)较大的模板窗可以使第一层匹配更可靠,虽然这会引起某些细节上的误差,但这些误差可以在第二层匹配中消除.由于投影形变,大窗口内的边缘可能并不完全对应,这可以通过选择合适的目标函数来度量边缘相似性而得到解决,这将在第3节讨论.(和容积迭代算
使用全局约束求
解视差图.通过引入全局约束并采用迭代算法,能得到相当好的匹配效果,且算法的复杂度比自适应窗法也有所减少,但其所需的存储空间和计算量仍然是很大的,特别是在立体像对的视差较大的时候.并且初始图像对在匹配前必须经过校准.上面提到的最大流算法也存在同样的问题.基于区域增长的稠密匹配算法
[6,7]
已表现出良好的性能,但已有算法
只能用于多纹理的图像.在比较平滑的区域,匹配关系的传播就会停止.为了解决这些问题,我们提出了一种新的算法.该算法对大视差、未经校准的图像对
938
计 算 机 学 报2004年
计算的信息量是很少的,匹配过程主要是依赖灰度值变化大的边缘或纹理等信息来完成的.所以在第一层匹配中仅使用边缘图像.这种两层匹配算法采用由粗到细的匹配过程,通过同时比较边缘相似程度和灰度相似程度来提高对应点的可靠性和准确性:从图像的轮廓到细节.种子点的可靠匹配是十分重要的,它是以后区域增长的基础.
我们可以通过观察匹配值曲线来判断计算结果的可靠性.若匹配值曲线存在几个近似相同的峰值,则选择一个错误的极值的可能性就会增加.因此引入可信系数(confidencecoefficient)的概念,定义搜索窗内匹配值曲线中最高两个峰值Emax1和Emax2之间的差别为可信系数 ,以此来衡量匹配的可靠性[9].
=
Emax1-Emax2
Emax1
(1)
间的相对位置关系将匹配迅速传播至整个图像区域.从种子点向图像对右下方的基本区域增长策略如图1所示,其中点R和B的搜索范围如图1(b)中两个粗线方框所示.这里搜索窗口的大小取为4 4像素.
图1 从种子点向图像对右下方的基本区域增长策略
在将匹配关系由种子点向图像的其余部分传播的过程中,若已知一对种子点,可以确定其相邻点的搜索区域;而若已知左图像中有两个种子点与当前点相邻,则其对应点在右图像中的搜索区域由以上两对种子点共同确定,如图2所示.在左图像中与当前点p相邻的有两个种子点s1和s2,而它们在右图像中的对应点S1与S2并不相邻,则p点的搜索区域由图2(b)中所示的两个粗线方框共同组成.以上两点就是区域增长策略.前一策略是匹配传播的基本方式,也是一般的区域增长算法所共同采用的传播策略.后一策略在确定当前点的搜索区域时不完全依赖于某一对种子点,而是由其周围种子点的匹配情况共同确定,这一项新加入的区域增长策略保证了匹配传播的可靠性和准确性.
在有重复性图案的情况下,例如一个建筑物有许多相同的窗口,匹配值曲线的形状就会像周期函数一样,这时的可信系数往往较小.第5节的实验结果表明,两层算法的可信系数大于传统的窗匹配法.所以此方法具有较好的鲁棒性,可以用于区域增长算法中种子点的匹配.
若一对匹配点的可信系数高于某一阈值,它就可以作为新的种子点,匹配关系由此开始传播.只要初始的一对匹配点足够精确,一粒种子就可以将正确的匹配关系传播至整个图像对.这里采用可信系数来度量像素之间匹配的可信度比使用匹配值本身更为合理.
3 基于区域增长的稠密匹配
3.1 稠密匹配中的区域增长策略
稠密匹配就是要尽可能多地将一个图像对的所有像素进行匹配.区域增长作为本算法的第2步,将匹配关系从种子点传播至图像的其余部分.与传统的逐点独立计算的方法相比,区域增长算法利用连续性约束极大地提高了稠密匹配的效率.其基本思想是:若已知左图像上一点s与右图像上一点S匹配,则与s相邻的r和b点的匹配点R和B必定在S点附近.这样R和B点的搜索范围就可以限制在S点的一个较小的邻域之内.通常只需要在4 4或3 3(像素)的搜索窗内计算目标函数,求得最大匹配值,即可认为是所求点的正确匹配.采用这种技术,算法的准确性和效率都可以得到极大提高.一旦
,图2 当前点搜索区域的确定
3.2 加权差值平方和准则
通常比较图像对应点之间相似程度的目标函数有两种:归一化互相关系数(normalizedcorrelationcoefficient)和差值平方和(SumofSquaredDiffer ence,SSD).这里两种匹配目标函数都是在某一支持区域内定义的,该区域就是所谓的模板窗.以像素(i0,j0)为中心的两图像中的模板窗W1(i0,j0)和W2(i0,j0)之间的归一化互相关系数定义为
7期唐 丽等:基于区域增长的立体像对稠密匹配算法
939
(i0,j0)=
(i,j)∀W(i,j)
k
!
E(i0,j0)=
[I1(i,j)- I1][I2(i,j)- I2]
2
(i,j)∀W(i,j)
k
!
w(i,j)[I1(i,j)-I2(i,j)]2
(7)
i,j)∀W(i,j)
1
[I1(i,j)- I1]
(i,j)∀W(i,j)
2
[I2(i,j)- I2]
2
上式中w(i,j)为加权系数,它服从均值为零的二维Gaussian分布
w(i,j)=
其中,wg(i,j)=e-2
2
(2)这里,I1(i,j)和I2(i,j)分别表示两图像在(i,j)点的灰度值,而 I1, I2分别是在(2n+1) (2n+1)模板窗内像素灰度的平均值.与通常互相关系数的定义相比,式(2)中每点的灰度值减去了模板窗内灰度的平均值.这样做可以提高互相关性能,但有时会使分母等于零.标准的差值平方和使用模板窗内两幅图像对应像素灰度值之差的平方和来度量像素点间的相似性,即
E(i0,j0)=
(i,j)∀W(i,j)
k
00
(i,j)∀W(i,j)
k
gwg(i,j)
2
(8)
(i+j)/(2%)
,%2为方差,它根据窗
口的大小取值.设窗口为(2n+1) (2n+1)像素,则在计算中我们取%=0.5n,如图3所示.加权后的SSD更加符合客观实际,使用这个目标函数能够显著提高匹配的准确性.
2
!
[I1(i,j)-I2(i,j)]2
(3)
这两种目标函数的不同之处在于,前者是在搜索窗中寻找互相关系数的最大值,而后者是求差值平方和的最小值
[^i,^j]T=arg(imax (i0,j0),j)∀
00
或(4)
T
[^i,^j]=arg(iminE(i0,j0),j)∀
其中 表示搜索窗区域.从式(2),(3)可以看出,差
值平方和的计算量远小于归一化互相关系数.
事实上,用两个窗口中对应像素的相似程度来判断其中心像素是否匹配这种方法,只有在窗口中的所有像素点都具有相同的深度值时才是准确的.如果它们的深度值不同,周围点的视差必然与中心点的视差不同,用它们来支持中心点的匹配会产生误差,从而导致所得视差图边界模糊,造成细节信息的丢失.不过在连续性约束下,可以近似地认为真实场景的视差是连续变化的.这时,可以利用窗口内视差分布的统计模型[1]来减小这一系统误差.d(!,∀)-d(0,0)~N(0,#!+∀)这里,#是一个代表视差变化量的常数因子,
#=
2
图3 零均值二维Gaussian加权函数
3.3 自适应的搜索窗和模板窗
在匹配传播过程中,为了避免前一个点的匹配误差对后一个点匹配精度的影响,我们提出了以下动态改变搜索窗的方法:若前一对匹配点的可信系数较大,则下一个匹配点就可以在它的较小邻域内搜索求得.反之,若前一对匹配点的可信系数较小,则下一个匹配点就需要在它的较大邻域内搜索求得.这就是说,搜索窗的大小N与可信系数 成反比
N=min{&/ ,Nmax}
(9)
这里Nmax为搜索窗的最大值,常数因子&需要根据待匹配的图像对的情况由实验确定,通常它的取值在1~2之间.采用自适应的搜索窗既可以有效地减
少计算时间,又可以提高匹配算法的准确性,同时避免了区域增长过程中匹配误差的积累.它类似于所谓的松弛算法,可以有效地避免匹配的误传播.
局部支持区域(模板窗)的大小确定了相邻像素对中心像素点的支持程度.在理想情况下,如果当前像素对应于一个正确匹配,局部支持区域应包括且仅包括对应于正确匹配的那些相邻像素.因为正确匹配事先并不知道,需要做某些假设以确定支持.,[4]
(5)
(d0(ri,sj)-d0(0,0))(6)N(i,j)∀!W(i,j)r+s00ij
N是窗口内的像素点数.这个模型假设点(∃,∀)与窗口中心点(0,0)的视差之差服从均值为零的二维Gaussian分布,其方差与这两点的距离成正比.也就
是说,点(∃,∀)的视差期望值与中心点相同,但该点距中心点越远,这种估计就可能有越大的偏离.或者,可以认为对应于窗口的小的表面是局部平滑的,且与基线平行,但是这一假设的准确程度随着窗口的增大而降低.据此,我们提出了一种新的加权SSD
940
计 算 机 学 报2004年
值表示平滑区域,1像素值表示物体的边缘.如图4所示为对图5中的#宫殿∃图像使用Canny算子进行边缘提取后得到的二值图像.我们通过统计1像素值的数量确定窗口中纹理的疏密程度.若窗口中没有提取出边缘,则可以认为其内的所有点在同一平面上.这时窗口内的纹理很少,使用小模板窗会引起误匹配,所以应增加窗口的大小以确保匹配的正确性.因为我们认为这个纹理稀少的窗口内的大部分点都在同一平面上,所以不会在所得视差图中引入太多过度的平滑.因而本算法使用了根据纹理多少自适应变化的模板窗,即窗口不断增大直至其中包含的纹理数量高于某一阈值,或窗口大小已达到了其最大值.此外,采用加权SSD作为目标函数也
可以减轻较大模板窗带来的匹配误差.实验证明,采用这种新的自适应窗,在纹理稀疏的区域同样可以应用区域增长算法
.
图4
边缘提取后的二值图像
图5 待匹配的初始#宫殿∃图像对
4 算法总结
我们的算法可以总结为如下几步.
1.种子点匹配.采用新的两层匹配算法找到一些准确可靠的匹配点对,将它们放入种子点队列中.
2.若种子点队列非空,从队首取出一对种子点,按区域增长策略确定搜索区域,根据纹理的疏密程度确定模板窗的大小,以加权SSD作为目标函数,求出与该种子点相邻8点的匹配点;否则,转到步5.
3.将新生成的匹配点对加入到种子点队列的尾部,用以产生更多的匹配点对.
4.若仍存在未匹配点,转至步2.5.图像对稠密匹配结束.
值得注意的是,它与立体像对之间视差的最大值无关,而在通常情况下,这个值是远远大于d的.
5 实验结果
实验中所用真实#宫殿∃图像对(720 576)如图5所示.在对种子点的第一层匹配中,采用加权SSD度量两幅边缘图像的轮廓相似性.计算所得的典型的匹配值曲线如图6所示.图中横轴表示搜索区域中所有点的序号,纵轴是其相应的以加权SSD作为目标函数的匹配值.可以看出,它有明显的最小值(用# ∃标记),与传统的使用灰度图像的互相关系数曲线相比,后者没有明显的最大值,如图7所示.这里横轴仍为搜索区域中所有点的序号,而纵轴表示以互相关系数作为目标函数的匹配值.这就是说,新算法具有较高的可信系数.这主要是由于在计算中使用的是边缘二值图像,其像素值与原始的灰度图像相比波动较大.图6中明显的最小值在曲线的开始部分出现,而在图7中存在许多大小相近的峰值,从其中选取最大值用# ∃标记,可以看出,它明6设待匹配的图像对的大小为s=a b像素,相邻像素间视差变化的最大值为d.这里假设模板窗与搜索窗的大小固定,因为它们是随不同的图像而变化的.由前面的分析可知,我们的算法的复杂度与图像大小成正比,而对于每一个像素,其搜索范围与d2成正比,因此总的计算复杂度为
2a222)
7期唐 丽等:基于区域增长的立体像对稠密匹配算法
941
里的第一层匹配算法比传统的互相关算法更可靠
.
图8 用新算法得到的结果图像
图6
边缘相似性曲线
图9 用标准7 7窗的SSD算法得到的结果图像
节也得到较好保持.同时,区域增长算法的效率明显高于传统的窗匹配法,因为它的搜索范围与视差的
图7 灰度相关系数曲线
最大值无关,而仅与相邻像素间视差的变化相关.如图5的最大视差约为50像素,相邻像素间视差的最大变化值不超过10像素,则对于传统的窗匹配法,每个匹配点的搜索区域均为50 50像素,而我们的算法通常只需要在10 10像素的区域内搜索匹配点就可以了,这时两种算法的效率相差25倍.
为了直观地表达稠密匹配算法的性能,如果左图像中的一点a与右图像中的一点a 匹配,则将a点的灰度值复制到结果图像中a 点的位置,这样当找到所有的匹配点后,生成的结果图像就可以反映匹配率和算法的整体性能.由于需要计算立体像对中每一点的匹配,因此需要对初始图像加一个镜像灰度的边,这样可以避免匹配值在图像边沿处发生急剧变化,也可以在图像的边沿附近逐渐缩小窗口的大小,以得到完整的匹配结果.#宫殿∃图像对的稠密匹配结果如图8所示.可以看出,虽然初始图像对中的重复图案很多,但绝大多数点的匹配是正确的(匹配率达到64.8%).图9是由标准的SSD区域相关算法得到的结果图像,计算中所用的窗口大小为7 7像素,显然其匹配率(50.4%)小于图8.这表明本文提出的算法和它相比,性能有较大提高.
虽然本算法适用于各种图像,包括未经校准的图像对,但是我们也将它应用于校准后的图像对,如图10所示为256 240的#小镇∃图像,它只包含垂直方向的视差.用新算法得到的视差图如图11所示,而由传统的窗匹配法和最大流方法得到的视差图分别如图12,13所示.可以看出,由新算法得到的
视差图是平滑的,而不同物体边缘深度不连续的细
图10 #小镇∃图像对
图11 由新算法得到的视差图
942
计 算 机 学 报2004年
的优势.设图像对的大小为a b像素,视差的最大值为D.最大流算法首先选择一个三维匹配空间a b D,该空间包含了所有可能的匹配.其中的每一个结点通过6条边与其它结点相连.根据灰度相似性和视差的连续性约束,对每条边赋予不同的权值.若找到了从#源∃(source)经过匹配空间到#汇∃(sink)的最大流,则其中包含的边的集合就给出了所求的视差图.这里三维匹配空间的大小由图像对的大小及视差范围决定.在图5所示的情况下,至少需要720 576 50的存储空间,而我们的算法则无此限制.
图14中标出了从稠密匹配的结果中随机抽取的160对匹配点.图中有一些纹理稀疏的区域,如其中部的墙壁.在这些平滑区域,使用了较大的、包含了足够多的纹理的模板窗度量灰度相似性,极大地减少了匹配错误传播的概率(匹配率达到了71.0%).
图13 由最大流方法得到的视差图
图12
由窗匹配法得到的视差图
而在文献6提出的算法中,区域增长在纹理稀疏的区域会自动停止,因此它并不是严格意义上的稠密匹配,而仅仅是一种准稠密匹配.对该图像对的实验表明,其匹配率仅为53.03%
.
新算法的匹配效果大致与最大流算法相当,但与其相比,新方法在对存储空间的需求上占有一定
图14 从稠密匹配结果中随机抽取的160对匹配点
6 结 论
以上实验结果表明,本文提出的稠密匹配算法对大视差、未经校准的图像对和图像中某些纹理稀疏的区域均适用.总地说来,基于区域增长的稠密匹配算法包括两步:一是选取种子点并对其进行匹配,二是由此根据区域增长策略找出所有的匹配点对.区域增长消除了重复图案间大的匹配误差,提高了算法的效率,特别是当图像对的视差较大时.这里对种子点应用了新的两层匹配法求其对应点.该方法将边缘相似性和灰度相似性相结合,具有较高的可靠性与准确性,适用于种子点的匹配.匹配关系根据播.其中的第二点策略在确定当前点的搜索区域时
不完全依赖于某一对种子点,而是由其周围种子点的匹配情况共同确定.匹配值计算中采用加权SSD准则作为目标函数,它通过引入窗口内视差分布的统计模型对标准SSD进行了加权修正,在减少计算量的同时提高了算法的准确性.模板窗的大小随其中的纹理数量动态变化,而搜索窗与可信系数成反比,减小了误匹配的概率.这些方法都提高了现有的区域增长算法的性能.实验结果表明,这种新的稠密匹配算法的性能优于传统算法.
致谢 感谢评审人对本文的详细评阅和修改意见.
7期唐 丽等:基于区域增长的立体像对稠密匹配算法
943
stereomatchingandocclusiondetection.CMUTechnicalReport:
参
1
考文献
CMU RI 98 30,19986
LhuillierM.,QuanL..Quasi densereconstructionfromimagesequence.In:Proceedingsofthe7thEuropeConferenceonCom puterVision,Copenhagen,2002,125~1397
LhuillierM.,QuanL..Imageinterpolationbyjointviewtriangu lation.In:ProceedingsofIEEEConferenceonComputerVisionandPatternRecognition,Ft.Collins,1999,139~1458
ShenPei Yi,WangWei,WuCheng Ke.ImagedensematchingbasedonDelaunaytriangulation.In:ProceedingsofSPIEConfer enceonMathematicalModelingandestimationTechniquesinComputerVision,SanDiego,1998,3457:109~1169
FaugerasO.,etal..Realtimecorrelation basedstereo:Algo rithm,implementationsandapplications.INRIAResearchReport2013,199310
ScharsteinD.,SzeliskiR..Stereomatchingwithnonlieardiffu sion.InternationalJournalofComputerVision,1998,28(2):155~
174
KanadeT.,OkutomiM..Astereomatchingalgorithmwithanadaptivewindow:Theoryandexperiment.IEEETransactionsonPatternAnalysisandMachineIntelligence,1994,16(9):920~932
2OhtaY.,KanadeT..Stereobyintra andinter scanlinesearchusingdynamicprogramming.IEEETransactionsonPatternAnal ysisandMachineIntelligence,1985,7(2):139~154
3RoyS.,CoxI.J..Amaximum flowformulationoftheN camerastereocorrespondenceproblem,In:IEEEProceedingsofInterna tionalConferenceonComputerVision,Bombai,1998,492~499
4ZitnickC.L.,KanadeT..Acooperativealgorithmforstereomatchingandocclusiondetection.IEEETransactionsonPatternAnalysisandMachineIntelligence,2000,22(7):675~684
5ZitnickC.L.,KanadeT..Avolumetriciterativeapproachto
TANGLi,bornin1975,Ph.D.candidate.Herresearchinterestsincludedigitalimageprocessing,computervisionandpatternrecognition,etc..
sor.Hisresearchinterestsincludeimageprocessingandcommu nication,computervision,andcomputergraphics,etc..
LIUShi Gang,bornin1973,Ph.D.candidate.Hisre searchinterestsincludeimageprocessingandcomputervision.
YANYao Ping,bornin1968,Ph.D..Hisresearchinter estsincludevideocompression,wirelessvideoandcommunica tion.
WUCheng Ke,bornin1938,professor,Ph.D.supervi Background
Stereomatchingisoneofthemostimportantandchallengesubjectsincomputervision,asitisanessentialstepformanyapplicationssuchasmosaicingand3Dreconstruction.Itistheprocessoffindingcorrespondingpointsintwoormoreimagesassociatingwiththesamephysicalpointinthescene.Fordensematching,correspondencecomputationforimagepairsisre quiredforasmanyscenepointsasitispractical.Thismadethe
problemmuchmoredifficultsincetherequirementformemoryandthecomputationaltimeisincreasedsignificantly.There searchareasofthecomputervisiongroupinvolvetheestimationofepipolargeometry,imagerectification,cameraself calibrationand3Dreconstructionetc.Densematchingisoneofthekeytopicstoachieveaccurate3Dreconstructioninthisfield.