CN102184540B - 基于尺度空间的亚像素级立体匹配方法 - Google Patents

Abstract

本发明提供的是一种基于尺度空间的亚像素级立体匹配方法。(1)为立体像对构建尺度空间；(2)为尺度空间中当前层级参考图像的每一点确定匹配窗口大小；(3)根据上一层级视差为本层级参考图像的每一点计算视差搜索范围；(4)计算尺度空间中当前层级的整数级视差；(5)利用基于二分搜索的亚像素级匹配方法计算亚像素级视差。本发明使用了小基高比条件下生成的立体像对进行匹配，在匹配过程中采用了离散尺度空间以提高匹配效率，并利用混合式窗口选择策略减少匹配过程中所产生的“粘合”现象，最后使用了基于二分搜索的亚像素级匹配方法获得亚像素级视差，不但可以保证较高的亚像素级精度，而且还很大程度上提高了算法的匹配效率。

Description

基于尺度空间的亚像素级立体匹配方法

技术领域

本发明涉及计算机视觉、信号处理、立体测绘方法，是一种亚像素级立体匹配方法。

背景技术

三维场景的深度差异会在不同视点获得的视图上产生几何位移，立体匹配就是基于这一原理通过匹配两幅或多幅不同视点的视图来获得对应点的视差，再通过三角测量原理计算出景物的深度信息。立体匹配是计算机视觉领域中的一个热点问题，它在机器人导航、立体测绘、航空摄影测量、遥感等领域有着广泛的应用。

传统大基高比条件下形成的立体像对会存在着较多的遮挡、较大的辐射差异和几何畸变以及由于场景中运动目标而产生的相对位置变化，这些因素在一定程度上增加了匹配难度，导致了大量的误匹配。

为减弱上述因素对匹配产生的不利影响，小基高比条件下的立体匹配技术应运而生。基高比是指摄影基线与摄像机高度的比值，小基高比则是指在摄像机高度一定时，两次拍照的时间间隔较短即两次成像时光心间的距离较小，在这种条件下形成的立体像对可以减弱由于运动而产生景物之间的相对位置变化、辐射差异与几何畸变等因素对匹配的影响以提高立体匹配的准确度。深度信息、基高比和视差满足dz＝dε/(b/h)，当视差精度给定的条件下，基高比越大，深度误差越小，因此，在立体观测中大多选择较大的基高比以减少由于视差精度不够而导致深度误差的增加，但与此同时，大基高比又增加了匹配难度，导致了大量的误匹配。2007年J.Delon和B.Roug在《Journal of Mathematical Imaging and Vision》的第28卷，第3期上发表了“Small Baseline Stereovision”论文，在该论文中首次提出了基于小基高比立体匹配方法，该方法提出了一种自适应窗口策略为参考图像中的每一点自适应的确定窗口大小，再利用“胜者全取”策略计算每一点视差，然后利用质心校正来减少立体匹配中的“粘合”现象，最后在频域中计算相关系数的连续表达形式来获得亚像素级视差。它与本发明的区别在于本发明提出了混合式窗口选择策略来减少立体匹配中的“粘合”现象，并提出了基于二分搜索的亚像素级匹配方法来获得亚像素级视差。

发明内容

本发明的目的在于提供一种可以提高匹配精度，可以获得较高精度的亚像素级视差，而且还具有较低的时空复杂度的基于尺度空间的亚像素级立体匹配方法。

本发明的目的是这样实现的：

(1)为立体像对构建尺度空间；

该步骤中，根据视差范围为立体像对中的左右图像构建尺度空间，构建尺度空间的公式如下：

$u_N(x,y)=\frac{\underset{(m,n)\∈S(x,y)}{\mathrm{\Σ}}{u}_{N-1}(m,n)}{4},$

S(x，y)＝{(2x，2y)，(2x+1，2y)，(2x，2y+1)，(2x+1，2y+1)}

式中，u_N表示尺度空间中第N层尺度图像，其中，u₀(N＝0)表示尺度空间中底层图像即原始图像；

(2)为尺度空间中当前层级参考图像的每一点确定匹配窗口大小；

该步骤中，根据尺度空间中当前层级参考图像的每点相关密度确定该点匹配窗口大小。相关密度计算公式如下：

式中，u(x)表示图像函数，u′(x)表示图像函数u(x)的导数，

表示以x₀为中心的支撑窗口，图像函数u(x)的范数

的计算公式如下：

u(x)与其导数u′(x)的内积计算公式如下：

计算匹配窗口大小的公式如下：

式中，

表示参考图像，g为高斯函数，σ_b为噪声标准差，λ为匹配精度，

的计算公式如下：

(3)根据上一层级视差为本层级参考图像的每一点计算视差搜索范围；

为尺度空间中当前层级参考图像的每一点计算视差搜索范围，首先根据上一层级的整数级视差计算本层级的初始视差，初始视差的计算公式如下：

d_N-1(i，j)＝2·d_N(m，n)，

(i，j)∈{(2m，2n)，(2m+1，2n)，(2m，2n+1)，(2m+1，2n+1)}

式中，d_N(i，j)为第N层级(i，j)位置的整数级视差；然后，根据最大视差值d_max计算本层级的最大视差值d_N，max，其计算公式如下：

式中，

表示大于等于x的最小整数。

(4)计算尺度空间中当前层级的整数级视差；

该步骤中，根据步骤(2)中为每一点确定的匹配窗口大小和步骤(3)中获得的视差搜索范围，针对混合式窗口选择策略确定的每一个匹配窗口位置，在相应的视差搜索范围内依据NCC计算匹配窗口的相似性获得每个窗口位置下所对应的最优视差值，并在这些窗口位置下所计算的视差中选取相似性最大的视差作为最终视差。

NCC计算公式如下：

$C_k(x,y,d)=\frac{\underset{(i,j)\∈W_k}{\mathrm{\Σ}}u(x+i,y+j)\·\tilde{u}(x+i+d,y+j)}{\sqrt{\underset{(i,j)\∈W_k}{\mathrm{\Σ}}u{(x+i,y+j)}^2\·\underset{(i,j)\∈W_k}{\mathrm{\Σ}}\tilde{u}{(x+i+d,y+j)}^2}}$

式中，u(x，y)和

分别代表立体像对中的左右图像，W_k表示相应的匹配窗口。每个窗口位置所对应的视差计算公式如下：

$d_k(x,y)=\underset{d}{\arg }\max C_k(x,y,d)$

式中，d_k(x，y)表示(x，y)点在第k个匹配窗口下的最优视差，相应的最优成本表示为C_k，opt(x，y)。

最终视差的计算公式如下：

$d_{\mathrm{opt}}(x,y)=\underset{d_k(x,y)}{\arg }\max C_{k,\mathrm{opt}}(x,y)$

式中，d_opt(x，y)表示(x，y)点的最终视差。

(5)利用基于二分搜索的亚像素级匹配方法计算亚像素级视差。

该步骤中，根据在多尺度空间中计算的整数级视差，再利用二分搜索法计算优于指定精度的亚像素级视差，其二分搜索法的计算公式如下：

$d^{A+1}\left(x_0\right)=\underset{m\∈S}{\arg }\max N_{x_0}\left(m\right)$

S＝{d^A(x₀)，d^A(x₀)+1/2^A，d^A(x₀)-1/2^A}

式中，A≥1为迭代次数，d^A(x₀)表示x₀点第A次迭代的亚像素级视差，d¹(x₀)(A＝1)表示x₀点的整数视差，表示参考窗口

与匹配窗口

的规范互相关系数，其计算公式如下：

在保证匹配精度的前提下减少计算时间提高匹配效率，本发明把立体匹配过程嵌入到“由粗到精”的离散尺度空间当中。尺度空间中的大尺度图像提供了图像的整体信息，而小尺度图像提供了图像的细节信息；在大尺度下求得的视差为近似视差，而在小尺度下求得的视差为精确视差。基于尺度空间的立体匹配就是在匹配过程中利用尺度空间中上层尺度的近似视差指导本层尺度进行匹配进而求得本层尺度视差的过程。在匹配过程中支撑窗口的大小会影响匹配精度，为得到可靠的视差支撑窗口内应有一定的灰度变化，在图像的非纹理区域内支撑窗口应尽可能的大以包含足够的灰度信息，而在纹理区域内支撑窗口应足够小以保证窗口内视差恒定。为此，本发明在匹配过程中引入了自适应窗口技术，而自适应过程只改变了窗口大小没有改变其形状，这会导致支撑窗口跨越物体边界而产生“粘合”现象。为避免匹配过程中支撑窗口跨越物体边界，本发明提出了混合式窗口选择策略，混合式窗口选择策略不但可以自适应的选择窗口大小以满足匹配所需的灰度变化范围，而且还增加了匹配窗口形状的多样性以避免窗口跨越边界，在一定程度上可以提高匹配精度。

为获得亚像素级视差，则需要在获得整数级视差之后加入亚像素级匹配。传统的亚像素级匹配方法主要包括图像重采样法、拟合法和相位法。图像重采样法是利用插值技术对匹配图像进行插值以获得高分辨率图像，高分辨率图像中的每个像素位置代表原图像的亚像素位置，再利用立体匹配技术确定亚像素级视差，此算法具有实现简单、精度高等优点，但其计算复杂度较高。拟合法是利用最优匹配代价及其左右相邻代价，采用拟合技术获得成本函数的连续表达形式，再求其函数的极值位置，此极值点位置即为亚像素级视差位置，此算法具有实现简单，复杂度低等优点，但其亚像素精度较低。相位法是利用频域的相位信息获得像点的位移信息，但频率混叠效应会严重的影响算法的定位精度。为获得高精度的亚像素级视差，同时减少算法的计算复杂度，本发明提出了基于二分搜索的亚像素级匹配方法，该方法不但可以获得较高精度的亚像素级视差，而且还具有较低的时空复杂度。

本发明基于尺度空间的亚像素级立体匹配方法使用了小基高比条件下生成的立体像对进行匹配，在匹配过程中采用了离散尺度空间以提高匹配效率，并利用混合式窗口选择策略减少匹配过程中所产生的“粘合”现象，最后使用了基于二分搜索的亚像素级匹配方法获得亚像素级视差，该方法不但可以保证较高的亚像素级精度，而且还很大程度上提高了算法的匹配效率。与其它匹配方法相比，本发明的优势在于：

1、本发明使用小基高比条件下生产的立体像对可以减少由于景物之间的相对位置变化、立体像对间的辐射差异和几何畸变等因素所造成的误匹配；

2、本发明把匹配过程嵌入到了离散尺度空间当中，利用上级视差指导下级进行匹配，减少了计算时间，提高了匹配效率；

3、本发明提出了自适应窗口和多窗口相结合的混合式窗口选择策略，该方法很大程度上减少了匹配过程中所产生的“粘合”现象，提高了整数级视差的匹配准确率；

4、本发明提出了基于二分搜索的亚像素级匹配方法来获得亚像素级视差以弥补小基高比给三维重建所带来的误差，该方法不但可以获得较高的亚像素级精度，而且还具有较低的时空复杂度：其时间复杂度O(A)、空间复杂度为O(K²)。

附图说明

图1为基于尺度空间的亚像素级立体匹配方法流程图；

图2为多尺度空间金字塔示意图；

图3为混合式窗口选择策略示意图；

图4为基于3×3窗口的亚像素级匹配图解示意图；

图5(a)-图5(d)为本发明的实验效果图，第一列图5(a)为立体像对中的参考图像，第二列图5(b)为真实视差图，第三列图5(c)为整数级视差图，第四列图5(d)为亚像素级视差图。

具体实施方式

下面结合附图举例对本发明的技术方案做进一步的描述：

图1显示了本发明基于尺度空间的亚像素级立体匹配方法的流程图，下面结合该流程图详细说明每一步骤的具体实现方式：

(1)为立体像对构建尺度空间；

①首先根据原始立体像对的最大视差值d_max计算尺度空间的最大层级N_max，其计算公式如下：

$N_{\max }=\min \left\{n\right|\frac{d_{\max }}{2^n}<1\}$

②根据尺度空间的最大层级N_max分别为参考图像

和匹配图像u构建尺度空间

和u_N，

其构建尺度空间的计算公式如下：

${\tilde{u}}_N(x,y)=\frac{\underset{(m,n)\&Element;S(x,y)}{\mathrm{\&Sigma;}}{\tilde{u}}_{N-1}(m,n)}{4},$

S(x，y)＝{(2x，2y)，(2x+1，2y)，(2x，2y+1)，(2x+1，2y+1)}

$u_N(x,y)=\frac{\underset{(m,n)\&Element;S(x,y)}{\mathrm{\&Sigma;}}{u}_{N-1}(m,n)}{4},$

S(x，y)＝{(2x，2y)，(2x+1，2y)，(2x，2y+1)，(2x+1，2y+1)}

式中，表示尺度空间中第N层参考图像，其中，

表示原始参考图像

u_N表示尺度空间中第N层匹配图像，其中，U₀(N＝0)表示原始匹配图像。第N层尺度参考图像和匹配图像的高度和宽度分别为原参考图像和匹配图像的1/2^N，其尺度空间的构造过程如图2所示。

(2)为尺度空间中当前层级参考图像的每一点确定匹配窗口大小；

①在尺度空间的当前层级下，首先根据标准偏差σ计算高斯范数，其高斯范数的计算公式如下：

${\left|\right|g\left|\right|}_{L_2}=\frac{1}{2\mathrm{\&sigma;}\sqrt{\mathrm{\&pi;}}}$

式中，σ的值为0.56。

②为尺度空间中当前层级参考图像的每一点计算最优窗口大小，最优窗口的计算实质上是在窗口大小取值范围内计算满足不等式的最小窗口值，其最优窗口计算公式如下：

式中，

表示参考图像，g表示高斯函数，σ_b表示高斯噪声标准差，λ表示匹配精度，

表示参考图像的相关密度，其计算公式如下：

(3)根据上一层级的视差为本层级参考图像的每一点计算视差搜索范围；

①根据上一层级的整数级视差为本层级的每一点计算初始视差值，初始视差的计算公式如下：

d_N-1(i，j)＝2·d_N(m，n)，

(i，j)∈{(2m，2n)，(2m+1，2n)，(2m，2n+1)，(2m+1，2n+1)}

式中，d_N(i，j)为第N层(i，j)位置的整数级视差。

②根据最大视差值d_max计算本层级的最大视差值d_N，max，其计算公式如下：

式中，表示大于等于x的最小整数。

(4)计算尺度空间中当前层级的整数级视差；

根据步骤(2)中计算的匹配窗口大小和步骤(3)中计算的视差搜索范围，针对混合式窗口选择策略确定的每一窗口位置(如图3所示)，在相应的视差搜索范围内依据NCC计算匹配窗口的相似性，再利用“胜者全取”策略获得每一窗口位置所对应的最优视差，并在这些视差中选取相似性最大的视差作为最终视差。

①针对每一窗口位置，根据窗口大小和视差范围计算匹配代价，其计算公式如下：

$C_k(x,y,d)=\frac{\underset{(i,j)\&Element;W_k}{\mathrm{\&Sigma;}}u(x+i,y+j)\&CenterDot;\tilde{u}(x+i+d,y+j)}{\sqrt{\underset{(i,j)\&Element;W_k}{\mathrm{\&Sigma;}}u{(x+i,y+j)}^2\&CenterDot;\underset{(i,j)\&Element;W_k}{\mathrm{\&Sigma;}}\tilde{u}{(x+i+d,y+j)}^2}}$

式中，u和分别代表立体像对中的左右图像，W_k表示相应的匹配窗口，C_k(x，y，d)表示像素(x，y)在第k个窗口下，视差为d时的匹配代价。

②计算每个窗口位置下所对应的视差，其计算公式如下：

$d_k(x,y)=\underset{d}{\arg }\max C_k(x,y,d)$

式中，d_k(x，y)表示(x，y)点在第k个匹配窗口下的最优视差，相应的最优成本表示为C_k，opt(x，y)。

③计算最终视差，其计算公式如下：

$d_{\mathrm{opt}}(x,y)=\underset{d_k(x,y)}{\arg }\max C_{k,\mathrm{opt}}(x,y)$

式中，d_opt(x，y)表示(x，y)点的最终视差。

(5)利用基于二分搜索的亚像素级匹配方法计算亚像素级视差。

在该步骤中，根据在多尺度空间中获得的整数级视差，利用二分搜索法计算优于指定精度的亚像素级视差。

①首先利用线性插值公式计算匹配窗口及其左右相邻窗口浮点位置的灰度值，其左右相邻窗口是通过将匹配窗口内的所有像素分别向左右方向平移1/2^A(A为迭代次数)形成的两个窗口，在下文中将这三个窗口分别称为：中间匹配窗口、左移匹配窗口和右移匹配窗口，其匹配窗口中浮点位置的灰度计算公式如下：

$\tilde{u}\left(x\right)=(x-[x\left]\right)(\tilde{u}\left(\right[x]+1)-\tilde{u}\left(\right[x\left]\right))+\tilde{u}\left(\right[x\left]\right)$

式中，[]表示取整。

②利用NCC相似性度量公式计算参考窗口和三个匹配窗口的相似性，其计算公式如下：

式中，m∈{d^A(x₀)，d^A(x₀)+1/2^A，d^A(x₀)-1/2^A}其中A≥1为迭代次数，d^A(x₀)表示x₀点第A次迭代的亚像素级视差，d¹(x₀)(A＝1)表示x₀点的整数级视差，

表示以x₀点为中心的参考窗口，

表示以x₀+m为中心的匹配窗口。

③根据计算获得的三个相似度值确定最优亚像素级视差，计算公式如下：

$d^{A+1}\left(x_0\right)=\underset{m\&Element;S}{\arg }\max N_{x_0}\left(m\right)$

S＝{d^A(x₀)，d^A(x₀)+1/2^A，d⁴(x₀)-1/2^A}

将求出的最优亚像素级视差作为新的中心点继续迭代搜索，直到达到给定的求解精度为止，图4显示了使用3×3窗口进行两次迭代的亚像素匹配过程。

当图像采样频率满足采样定理的情况下，二分搜索法能够达较高的亚像素级精度，在实际的立体匹配中图像的采样频率往往不满足采样定理，亚像素的精度是有限的。经实验验证，该方法能够达到1/20的亚像素级精度，即A＝5。

与重采样法的亚像素匹配方法相比本发明提出亚像素方法在时间和空间复杂度上都有了明显的改进。当亚像素精度为2^A时，重采样法的空间复杂度为S₁＝K²*2^A，而二分搜索法的空间复杂度为S₂＝3*K²，其中K为支撑窗口大小；在时间复杂度上，二分搜索法将指数级时间复杂度降低到线性时间复杂度，重采样法的时间复杂度为T＝O(2^A)，而二分搜索法的时间复杂度为T＝O(A)，该算法在时间复杂度上有了明显改进。

Claims (2)

1.一种基于尺度空间的亚像素级立体匹配方法，其特征是：

（1）为立体像对构建尺度空间；

（2）为尺度空间中当前层级参考图像的每一点确定匹配窗口大小；

①在尺度空间的当前层级下，首先根据标准偏差σ计算高斯范数，其高斯范数的计算公式如下：

${\left|\right|g\left|\right|}_{L_2}=\frac{1}{2\mathrm{\&sigma;}\sqrt{\mathrm{\&pi;}}}$

式中，σ的值为0.56；

②为尺度空间中当前层级参考图像的每一点计算最优窗口大小，其最优窗口计算公式如下：

式中，

表示参考图像，g表示高斯函数，σ_b表示高斯噪声标准差，λ表示匹配精度，表示参考图像的相关密度，其计算公式如下：

式中，u(x)表示图像函数，u'(x)表示图像函数u(x)的导数，

表示以X₀为中心的支撑窗口，图像函数u(x)的范数

的计算公式如下：

u(x)与其导数u'(x)的内积计算公式如下：

计算匹配窗口大小的公式如下：

式中，

表示参考图像，g为高斯函数，σ_b为噪声标准差，λ为匹配精度，

的计算公式如下：

（3）根据上一层级视差为本层级参考图像的每一点计算视差搜索范围；

①根据上一层级的整数级视差为本层级的每一点计算初始视差值，初始视差的计算公式如下：

d_N-1(i,j)＝2·d_N(m,n)，

(i,j)∈{(2m,2n)，(2m+1,2n),(2m,2n+1),(2m+1,2n+1)}

式中，d_N(i,j)为第N层(i,j)位置的整数级视差；

②根据最大视差值d_max计算本层级的最大视差值d_N,max，其计算公式如下：

式中，

表示大于等于x的最小整数；

（4）计算尺度空间中当前层级的整数级视差；

根据步骤(2)中为每一点确定的匹配窗口大小和步骤(3)中获得的视差搜索范围，针对混合式窗口选择策略确定的每一个匹配窗口位置，在相应的视差搜索范围内依据NCC计算匹配窗口的相似性获得每个窗口位置下所对应的最优视差值，并在这些窗口位置下所计算的视差中选取相似性最大的视差作为最终视差，具体包括：

①针对每一窗口位置，根据窗口大小和视差范围计算匹配代价，其计算公式如下：

$C_k(x,y,d)=\frac{\underset{(i,j)\&Element;W_k}{\mathrm{\&Sigma;}}u(x+i,y+j)\&CenterDot;\tilde{u}(x+i+d,y+j)}{\sqrt{\underset{(i,j)\&Element;W_k}{\mathrm{\&Sigma;}}u{(x+i,y+j)}^2\&CenterDot;\underset{(i,j)\&Element;W_k}{\mathrm{\&Sigma;}}\tilde{u}{(x+i+d,y+j)}^2}}$

式中，u和

分别代表立体像对中的左右图像，W_k表示相应的匹配窗口，C_k(x,y,d)表示像素(x,y)在第k个窗口下、视差为d时的匹配代价；

②计算每个窗口位置下所对应的视差，其计算公式如下：

$d_k(x,y)=\underset{d}{\arg }\max C_k(x,y,d)$

式中，d_k(x,y)表示(x,y)点在第k个匹配窗口下的最优视差，相应的最优成本表示为C_k,opt(x,y)；

③计算最终视差，其计算公式如下：

$d_{\mathrm{opt}}(x,y)=\underset{d_k(x,y)}{\arg }\max C_{k,\mathrm{opt}}(x,y)$

式中，d_opt(x,y)表示(x,y)点的最终视差；

（5）利用基于二分搜索的亚像素级匹配方法计算亚像素级视差；

根据在多尺度空间中计算的整数级视差，再利用二分搜索法计算优于指定精度的亚像素级视差；

①首先利用线性插值公式计算匹配窗口及其左右相邻窗口浮点位置的灰度值，其左右相邻窗口是通过将匹配窗口内的所有像素分别向左右方向平移1/2^A形成的两个窗口、其中A为迭代次数，将这三个窗口分别称为：中间匹配窗口、左移匹配窗口和右移匹配窗口，其匹配窗口中浮点位置的灰度计算公式如下：

$\tilde{u}\left(x\right)=(x-[x\left]\right)(\tilde{u}\left(\right[x]+1)-\tilde{u}\left(\right[x\left]\right))+\tilde{u}\left(\right[x\left]\right)$

式中，[]表示取整；

②计算参考窗口和三个匹配窗口的相似性，其计算公式如下：

式中，m∈{d^A(x₀),d^A(x₀)+12^A,d^A(x₀)-1/2^A}其中A≥1为迭代次数，d^A(x₀)表示x₀点第A次迭代的亚像素级视差，A=1时d¹(x₀)表示x₀点的整数级视差，

表示以x₀点为中心的参考窗口，表示以x₀+m为中心的匹配窗口；

③根据计算获得的三个相似度值确定最优亚像素级视差，计算公式如下：

$d^{A+1}\left(x_0\right)=\underset{m\&Element;S}{\arg }\max N_{x_0}\left(m\right)$

S＝{d^A(x₀),d^A(x₀)+1/2^A,d^A(x₀)-1/2^A}。

2.根据权利要求1所述的基于尺度空间的亚像素级立体匹配方法，其特征是所述为立体像对构建尺度空间步骤中，构建尺度空间的公式如下：

$u_N(x,y)=\frac{\underset{(m,n)\&Element;S(x,y)}{\mathrm{\&Sigma;}}{u}_{N-1}(m,n)}{4},$

S(x,y)＝{(2x,2y),(2x+1，2y),(2x,2y+1),(2x+1,2y+1)}

式中，u_N表示尺度空间中第N层尺度图像，其中，u₀，N＝0，表示尺度空间中底层图像即原始图像。

Images