文档介绍:基丁半全局和全局算法的立体匹配研究摘要:传统的基于像素点的匹配算法常常是算出初始匹配代价后頁接采川贪心策略求取视并,虽然速度较快,但往往是局部最优的,以至精确度很低。针对这一问题,目前策略主要有:半全局优化算法:扫描线算法和动态规划算法;(2)全局优化算法:置信度算法和图割算法。木文旨在通过详细讨论这四种算法原理本质,算法步骤与算法运行,从而深刻分析各自的优点与缺点,为进一步改进其不足,进而研究新的算法打下基础。关键词:半全局优化,全局优化,扫描线,动态规划,置信度,图割—・立体匹配介绍图像的立体匹配即给定同一场景的两幅图像,寻找同一场景点投影到图像屮的像索Z间的对应关系。根据考虑的是基于像素点的还是基于区域块,可以分为基于像素点的匹配与基于区域的匹配。立体匹配算法通常是通过构建能量函数试图获得图像的某些全局性质,即全局能量最小化,但通常很难获得能最函数的全局最小化,鉴于此,很多学者更倾向于寻找局部小的求解•然而在一般情形下,局部小不能带来任何的全局性,所以匹配效果较羌,准确率较低,基于像素点的匹配就是一种局部小的解,所以若想提高精度,研究的多是一种半全局或全局优化策略的区域匹配算法。立体匹配的通常包括以下四步:图像预处理(Preprocessing)-由于拍摄照片的时候难免会有传感器的噪声(sensornoise)和光度的扭曲(photometricdistortions)而这都会对视差的计算带来严重影响,常用的解决方法有,高斯拉普拉斯滤波(LaplacianofGaussian(LoG)filtering)'直方图均衡化(HistogramEqualization/Matching),屮值滤波(putedintheneighboursofeachpixel)'双边滤波(B订atereilfiltering)3。匹配代价计算(putation)—对匹配代价的计算通常有四种方法AD(1-1).SAD(1-2)>SD(1-3)与SSD(1-4),计算公式,从而能得到元素的不同视差匹配代价所组成的初始视差空间。CdataAD(心)=abs(IL{x)-IR{x+<))(1-1)CdataSD(dx)=(IL(x)一几(x+dx))2(1-2)CdataSAD{dx)=工abs(IL(x)-IR(x+dx))(1-3)CdataSSD(血)=工(厶(x)—A(x+<))25仃-4)视差的计算(putation)—^实的像素视弟是指这两个像素点具有高的相似性,传统的WTA(WinnerTakesAll)算法就是每个像素点选取嚴小的代价来求取视差,是仅仅考虑一个像素的基于像素点匹配算法。如图(1)putationbasedonthepixeltopixelstereo视羌的优化(disparityrefinement.)—大多数立体匹配算法计算出来的视旁是离散的,常常视并值都是整数,然而世界实际上是连续的,若想将立体匹配算法川在较高精度的场合,如机器人视觉,精密三维重建,这种离散的视差值不进行后续处理就无法达到令人满意的效果。针对这一问题,在获取初始视差后可以采用一些措施对视差进行细化,非整数视差,如匹恥代价的曲线拟合如图2所示,或者直接采用亚像索精度法(sub-pixeldisparityEstimate),即将原图像进行水平拉伸,再对行像素点进行模糊。木文将详细研究的就是立体匹配的视差计算阶段,就是在初步计算岀來的视并空间屮进行半全局或全局优化,从而求出更好的视差值。与基于像素点的匹配方法不同,基于半全局或全局的算法通常是将匹配问题转换为一个能量方稈,然后通过求解该能量方稈的嚴小值来求取视差值。能量方稈通常具有以下的形式w(1-5)E二工(Cd必(dJ+VU)x=\其屮Cdata(dJ是数据项用来约束像素点在偏移前后的变化尽量小,V(cL,是光滑项,约束像索点在偏移前丿丘与周用像索点的关系变化尽量小。不同的优化算法的数据项和光滑项的定义不同,木文采取的数据项计算方法为ADo而光滑项则根据不同的算法用不同的模型方法。(ScanlincOptimization)方法属于一种半全局能量最小化优化算法,比基于像索点匹配的算法有更好的适应性,通过最小化H身的能量方程来求得像素对应的视茅,但是由于其只考虑一行的最优,并未考虑所有的像素点,所以本文称之为半全局能量最小化算法。:so的能暈方程的光滑项通常为:y(dx-dx_l)=oifdx=dx-\opt_smoothothers(2-1)optsmoothV/v>optgradthreshopt_smooth-\ ~ ~ ~ (2-2)— [optsmooth*altyothers其||iopt_smooth表示图片屮像素点x的光滑值,