文档介绍：基于半全局和全局算法的立体匹配研究
摘要:
传统的基于像素点的匹配算法常常是算出初始匹配代价后直接采用贪心策略求取视差,虽然速度较快,但往往是局部最优的,以至精确度很低。针对这一问题,目前策略主要有:(1)半全局优化算法:扫描线算法和动态规划算法;(2)全局优化算法:置信度算法和图割算法。本文旨在通过详细讨论这四种算法原理本质,算法步骤与算法运行,从而深刻分析各自的优点与缺点,为进一步改进其不足,进而研究新的算法打下基础。
关键词:半全局优化,全局优化,扫描线,动态规划,置信度,图割
立体匹配介绍
图像的立体匹配即给定同一场景的两幅图像,寻找同一场景点投影到图像中的像素之间的对应关系。根据考虑的是基于像素点的还是基于区域块,可以分为基于像素点的匹配与基于区域的匹配。立体匹配算法通常是通过构建能量函数试图获得图像的某些全局性质,即全局能量最小化,但通常很难获得能量函数的全局最小化,鉴于此,,局部小不能带来任何的全局性,所以匹配效果较差,准确率较低,基于像素点的匹配就是一种局部小的解,所以若想提高精度,研究的多是一种半全局或全局优化策略的区域匹配算法。
立体匹配的通常包括以下四步:
1) 图像预处理(Preprocessing)—由于拍摄照片的时候难免会有传感器的噪声(sensor noise)和光度的扭曲(photometric distortions)而这都会对视差的计算带来严重影响,常用的解决方法有,高斯拉普拉斯滤波(Laplacian of Gaussian (LoG) filtering)[1]直方图均衡化(Histogram Equalization/Matching),中值滤波(Subtraction of mean puted in the neighbours of each pixel)[2]双边滤波(Bilateral filtering)[3]。
2) 匹配代价计算(Matching putation)—对匹配代价的计算通常有四种方法AD(1-1)、SAD(1-2)、SD(1-3)与SSD(1-4),计算公式,从而能得到元素的不同视差匹配代价所组成的初始视差空间。
(1-1)
(1-2)
(1-3)
(1-4)
3) 视差的计算(putation)—真实的像素视差是指这两个像素点具有高的相似性,传统的WTA(Winner Takes All)算法就是每个像素点选取最小的代价来求取视差,是仅仅考虑一个像素的基于像素点匹配算法。如图(1)所示
图 1 基于像素点的视差计算
Figure 1 putation based on
the pixel to pixel stereo
图 2 视差优化
Figure 2 disparity refinement
4)视差的优化(disparity refinement.)—大多数立体匹配算法计算出来的视差是离散的,常常视差值都是整数,然而世界实际上是连续的,若想将立体匹配算法用在较高精度的场合,如机器人视觉,精密三维重建,这种离散的视差值不进行后续处理就无法达到令人满意的效果。针对这一问题,在获取初始视差后可以采用一些措施对视差进行细化,非整数视差,如匹配代价的曲线拟合如图 2 所示,或者直接采用亚像素精度法(sub-pixel disparity Estimate),即将原图像进行水平拉伸,再对行像素点进行模糊。
本文将详细研究的就是立体匹配的视差计算阶段,就是在初步计算出来的视差空间中进行半全局或全局优化,从而求出更好的视差值。
与基于像素点的匹配方法不同,基于半全局或全局的算法通常是将匹配问题转换为一个能量方程,然后通过求解该能量方程的最小值来求取视差值。能量方程通常具有以下的形式
(1-5)
其中Cdata(dx)是数据项用来约束像素点在偏移前后的变化尽量小,V(dx,dx-1)是光滑项,约束像素点在偏移前后与周围像素点的关系变化尽量小。不同的优化算法的数据项和光滑项的定义不同,本文采取的数据项计算方法为AD。而光滑项则根据不同的算法用不同的模型方法。
SO(Scanline Optimization)方法属于一种半全局能量最小化优化算法,比基于像素点匹配的算法有更好的适应性,通过最小化自身的能量方程来求得像素对应的视差,但是由于其只考虑一行的最优,并未考虑所有的像素点,所以本文称之为半全局能量最小化算法。
:
SO的能量方程的光滑项通常为:
(2-1)
(2-2)
其中opt_smooth表示图片中像素点x的光滑值,opt_grad_penalt用来对同纹理区域(灰度梯