双目立体匹配算法的匹配代价算法和非局部立体匹配算法

摘要

本发明公开了一种双目立体匹配算法的匹配代价计算方法和一种基于可变权重MST的非局部立体匹配算法，所述匹配代价计算方法包括：S1)色彩空间归一化步骤：按照下述方法对原图像进行RGB色彩空间归一化处理获得归一化色彩空间，归一化色彩空间的像素点的R、G、B色彩值分量r、g、b满足：S2）匹配代价计算步骤：利用归一化色彩空间对图像的匹配代价进行评价。相对于现有技术，本发明的方法具有更强的鲁棒性。

说明书

技术领域

本发明涉及双目立体视频技术，尤其是涉及：双目立体匹配算法的匹配代价 算法和非局部立体匹配算法。

背景技术

计算机视觉是研究如何用摄像机和电脑代替人眼和大脑神经系统对目标进 行信息获取、场景理解、目标识别、跟踪和测量等的计算机视觉系统。计算机视 觉的研究对象是包含着三维信息的二维投影图像，目标是从这些二维图像中提取 出其所包含的三维信息，从而全面恢复三维立体场景。

立体视觉一般可以分为双目立体视觉系统、三目或者多目的立体视觉系统。 其中三目和多目立体视觉系统可以看成是由多个双目立体视觉系统构成，它们的 基本的原理都还是基于双目立体视觉原理；双目立体视觉系统可以视为是计算机 立体视觉中的最小系统。双目立体视觉中对应点匹配问题即立体匹配问题是最困 难、极富挑战性的一步，匹配的精度和速度对立体视觉系统有很大的影响。

根据约束条件的不同，当前立体匹配算法主要分为局部立体匹配和全局立体 匹配算法两大类。局部立体匹配算法通常采取支持窗口的策略，认为支持窗口内 的视差值是一样的，但是该类假设不总是成立，会造成”前景膨胀效应“。全局 立体匹配算法通常考虑局部的颜色信息和结构信息，并为图像建立全局的能量函 数，通过一些优化方法，例如BP,GC,DP来为每个像素点分配视差值。总体而言， 当前的全局立体匹配算法速度较慢，但是获取的视差值精度较高，能很好的反应 场景的深度信息，与之相比，一些局部立体匹配算法能实时实现，但在较高精度 的应用上，显得力不从心。

近来，基于树模型的立体匹配算法得到了广泛的应用，其中一个很好的例子 是Yang Q.A non-local cost aggregation method for stereo  matching[C]//Computer Vision and Pattern Recognition(CVPR),2012IEEE  Conference on.IEEE,2012:1402-1409公开的模型，在该模型中，相邻像素点 的色彩差异作为连接节点的边的权值。最后构成的树中，每一个树节点都会对其 它节点的匹配代价叠加计算产生影响，即计算每一个节点视差值的时候用到了其 他所有节点的信息，该类算法区别于原有的局部立体匹配算法和全局立体匹配算 法，能获得质量较好的视差图，被称为非局部的立体匹配算法。但是该类算法中， 将图像构造成边的四邻域图的时候，边的权值容易受图片质量影响。比如，一般 采样获取的双目图像对色彩不完全一致，受拍摄环境影响较大时，权值计算会失 真。

发明内容

本发明所要解决的技术问题是，针对前述现有技术的缺陷，提供一种双目立 体匹配算法的匹配代价计算方法，提高匹配代价计算精确性和鲁棒性。

本发明所要解决另一技术问题是，提供一种基于可变权重MST的非局部立 体匹配算法以提高视差值计算的精确性。

本发明通过下述技术方案解决前述技术问题：

一种双目立体匹配算法的匹配代价计算方法，其特征在于，包括：

S1)色彩空间归一化步骤：按照下述方法对原图像进行RGB色彩空间归一化 处理获得归一化色彩空间，归一化色彩空间的像素点的R、G、B色彩值分量r、 g、b满足：

$\left(\begin{array}{c}r=\frac{C_r}{C_r+C_g+C_d}\\ g=\frac{C_g}{C_r+C_g+C_d}\\ b=\frac{C_b}{C_r+C_g+C_d}\end{array}\right)$

其中，C_r，C_g，C_b分别表示原图像对应像素点的R、G、B色彩值分量；

S2）匹配代价计算步骤：利用归一化色彩空间对图像的匹配代价进行评价， 评价方法如下：

图像中任意点（i,j）在视差假设为d的匹配代价

$\cos t(i,j,d)=\underset{c\in \{r,g,b\}}{\Sigma }\mathrm{abs}(I_{\mathrm{leftC}}(i,j)-I_{\mathrm{rightC}}(i+d,j)),$其中，三通道的色 彩强度I_leftC、I_rightC分别表示左右图归一化色彩空间的像素点的R、G、B色彩 值分量r、g、b。

现有匹配代价计算主要是考虑匹配点对的色彩差异，该类方法的劣势在于容 易受原始图像对的影响。由于实验条件的限制，一般采集获得的双目图像对存在 一定的色彩偏差，主要表现为视场中的一点在左右图像中的色彩值存在偏差，这 会给匹配对的选择带来影响。本发明的上述方案提出了将色彩空间进行归一化， 利用归一化色彩空间的值进行匹配代价计算，从而能够有效减弱采样对匹配结果 的影响，使得匹配更加准确。

现有技术匹配代价计算的另一个缺陷是匹配代价的计算没有考虑到局部的 结构信息，如此会可能导致无匹配。为克服该缺陷，本发明在前述技术方案的基 础上，提出了将像素点周围结构信息的相对梯度信息作为匹配代价的一部分。即： 在前述方案基础上增加下述步骤：

S3）相对梯度差异计算步骤：根据图像的色彩信息计算图像中每一个像素点 的梯度信息；对图像中的每一个像素点，为它建立支持窗口，在支持窗口内，找 出最大的梯度值，并计算该像素点的相对梯度：

$\mathrm{rg}(i,j)=\frac{\mathrm{grad}\mathrm{ient}(i,j)}{\max \left(\mathrm{grad}\mathrm{ient}(i,j)\right)+1},$其中gradient(i,j)表示像素点(i,j)的梯度 值，max(gradient(i,j))表示像素点(i,j)的支持窗口内的最大的梯度值；

然后根据下述公式计算匹配点对的相对梯度差异RG(i,j,d)：

RG(i,j,d)＝|rg_left(i,j)-rg_right(i+d,j)|；其中，rg_left(i,j)表示左图中坐标为（i,j） 点的相对梯度值，rg_right(i+d,j)表示计算右图中对应点（i+d，j）点的相对梯度值；

S4)匹配代价Cost(i,j,d)计算步骤：图像中任意点（i,j）在视差假设为d的 匹配代价Cost(i,j,d)＝λcost(i,j,d)+（1-λ）RG(i,j,d)，其中λ∈[0,1]。

优选λ＜0.5。

相对于现有技术，上述技术方案能够同时解决左右图像色彩偏差和无匹配的 问题，相对于现有技术更鲁棒。

本发明的基于可变权重MST的非局部立体匹配算法，包括视差图计算，其 特征在于，所述视差图计算包括以下步骤：

S1）色彩空间归一化步骤：按照下述方法对原图像进行RGB色彩空间归一 化处理获得归一化色彩空间，归一化色彩空间的像素点的R、G、B色彩值分量 r、g、b满足：

$\left(\begin{array}{c}r=\frac{C_r}{C_r+C_g+C_d}\\ g=\frac{C_g}{C_r+C_g+C_d}\\ b=\frac{C_b}{C_r+C_g+C_d}\end{array}\right)$

其中，C_r，C_g，C_b分别表示原图像对应像素点的R、G、B色彩值分量；

S2)初始匹配代价计算步骤：利用归一化色彩空间对图像的初始匹配代价进 行评价，评价方法如下：

图像中任意点（i,j）对应视差d的匹配代价

$\cos t(i,j,d)=\underset{c\in \{r,g,b\}}{\Sigma }\mathrm{abs}(I_{\mathrm{leftC}}(i,j)-I_{\mathrm{rightC}}(i+d,j)),$其中，三通道的色彩强 度I分别表示归一化色彩空间的像素点的R、G、B色彩值分量r、g、b；

S3）相对梯度差异计算步骤：根据图像的色彩信息计算图像中每一个像素点 的梯度信息；对图像中的每一个像素点，为它建立支持窗口，在支持窗口内，找 出最大的梯度值，并计算该像素点的相对梯度：

$\mathrm{rg}(i,j)=\frac{\mathrm{grad}\mathrm{ient}(i,j)}{\max \left(\mathrm{grad}\mathrm{ient}(i,j)\right)+1},$其中gradient(i,j)表示像素点(i,j)的梯度 值，max(gradient(i,j))表示像素点(i,j)的支持窗口内的最大的梯度值；

然后根据下述公式计算匹配点对的相对梯度差异RG(i,j,d)：

RG(i,j,d)＝|rg(i,j)-rg(i,j,d)|；

S4)匹配代价Cost(i,j,d)计算步骤：

Cost(i,j,d)＝λcost(i,j,d)+（1-λ）RG(i,j,d)，其中λ∈[0,1]；

S5)四邻域图构造步骤：图像中的每一个像素点和周围的四邻域像素点生成 四条边，对于连接像素点(s.i,s.j)和(r.i,r.j)的边，其权重We构造公式如下：

$w_e=\underset{c\in \{r,g,b\}}{\Sigma }\mathrm{abs}(I_c(s.i,s.j)-I_c(r.i,r.j))+\max \left(\mathrm{rg}(s.i,s.j)\right)$

S6)最小生成树构造步骤：根据步骤S5)获得的四邻域图，利用最小生成树算 法构造图像的最小生成树；

S7）匹配代价叠加步骤：对任意两个像素点p和q，在最小生成树上只有一 条路径将他们连接，令C_d(p)代表p点在视差假设为d时的匹配代价，令代表p点的叠加匹配代价，根据下述公式计算叠加匹配代价：

$C_d^A\left(p\right)=\underset{q\in O}{\Sigma }S(p,q)C_d\left(p\right),$其中$S(p,q)=\exp (-\frac{D(p,q)}{\delta }),$δ是预设的恒定 值，O为整副图像像素点的集合，D(p,q)表示像素点p和q在最小生成树上的 距离；

S8)初始视差图获取步骤：根据步骤S7)获得的叠加匹配代价，利用WTA算 法，获取初始视差图；

S9)四邻域图权重更新步骤：利用初始视差图更新私领域图边的权重，更新 方法为：对于连接像素点(s.i,s.j)和(r.i,r.j)的边，设其原有的四邻域图中的 权重为w_pre，令D(s)和D(r)分别表示两个像素点的初始视差值，更新后的权值 w_update＝(1-μ)w_pre+μ(D(s)-D(r))；其中，μ∈[0,1]；

S10)视差图更新步骤：在更新后的四邻域图的基础上，依据步骤S6)-S8)的 方法计算获得最终的视差图。

优选μ＞0.5。

优选还包括视差图后处理步骤，其包括：

对左右两路图像的视差图，通过左右一致性检测，获得图像中视差值准确的 点；对不满足左右一致性检测的点，对视差图中置滤波后，将视差值不准确的点 赋值为距其最近的视差值正确的点的视差值。

相对于现有技术，上述技术方案至少具有以下优点：1）在一些实际场景中， 尤其是一些物体的边缘，由于采样的原因，边缘模糊，色彩相近的像素点可能位 于不同的深度场景，如果只利用色彩信息，颜色和距离相近但处于不同深度的像 素点之间的边的权重就较大，而本发明利用相对梯度和色彩在归一化空间的差异 够早的边权值，可以很好地解决这种问题。2）实际场景中视差值满足平滑性约 束，本发明在获取初始视差值后，对四邻域图边的权值进行相应的调整，将平滑 性约束和权值调整结合起来，通过对四邻域图边的权值更新，构造新的最小生成 树（MST）进行匹配代价的叠加，可以获得质量更高的视差图像。

附图说明

图1是基于可变权重MST的非局部立体匹配算法的流程图；

图2是图1中步骤101的流程图；

图3是图1中步骤102的流程图；

图4是图1中步骤103的流程图；

图5是图1中步骤104的流程图.

具体实施方式

下面对照附图并结合优选的实施方式对本发明作进一步说明。

如图1所示，一种基于可变权重MST的非局部立体匹配算法，其包括下述 步骤：

步骤101：计算匹配代价；

步骤102：构造四邻域图，构造最小生成树，获取初始视差图；

步骤103：更新四邻域图权重，构造新的最小生成树，更新视差图；

步骤104：视差图后处理。

如图2所示，步骤101计算匹配相比以往只利用匹配对的色彩差异进行了改 进。新的方法中，利用归一化的色彩空间来评价匹配对的色彩差异，并加入相对 梯度信息，构造更加精确的匹配代价函数。主要步骤如下：

301：色彩空间的归一化。

原有的RGB色彩空间在面对有色彩偏差的图像对时，不能很好的区分匹配点对。 为了减小色彩偏差对匹配对准确性的影响，提出了一种新的衡量匹配点对色彩差 异的方法。方法如下：

归一化色彩空间的像素点的R、G、B色彩值分量r、g、b满足：

$\left(\begin{array}{c}r=\frac{C_r}{C_r+C_g+C_d}\\ g=\frac{C_g}{C_r+C_g+C_d}\\ b=\frac{C_b}{C_r+C_g+C_d}\end{array}\right)$

其中C_r，C_g，C_b分别表示原图像对应像素点的R、G、B色彩值分量。 归一化的RGB空间可以使得像素点的色彩值和照明条件无关。

那么衡量相应匹配对的匹配代价如下公式（2）所示：

$\cos t(i,j,d)=\underset{c\in \{r,g,b\}}{\Sigma }\mathrm{abs}(I_{\mathrm{leftC}}(i,j)-I_{\mathrm{rightC}}(i+d,j))$

$\left(2\right)$

其中其中，三通道的色彩强度I_leftC、I_rightC分别表示左右图归一化色彩空间 的像素点的R、G、B色彩值分量r、g、b，cost（i,j,d）表示任意点（i,j）对应视 差d的匹配代价。

302：相对梯度信息计算

匹配代价函数的第二部分是表征像素点周围结构信息的相对梯度信息。相对 梯度的计算方法如下：

首先根据图像的色彩信息计算图像中每一个像素点的梯度信息；对每一个像 素点，为它建立支持窗口，在支持窗口内，找出最大的梯度值，利用如下公式（3） 来求得该点的相对梯度大小：

$\mathrm{rg}(i,j)=\frac{\mathrm{grad}\mathrm{ient}(i,j)}{\max \left(\mathrm{grad}\mathrm{ient}(i,j)\right)+1}---\left(3\right)$

其中，gradient(i,j)表示像素点(i,j)的梯度值，分母中的 max（gradient（i,j））表示像素点（i,j）的支持窗口内的最大的梯度值。

然后按照匹配点对相对梯度差异用公式(4)计算匹配点对的相对梯度差异 RG(i,j,d)：

RG(i,j,d)＝|rg_left(i,j)-rg_right(i+d,j)|   (4)

其中，rg_left(i,j)表示左图中坐标为（i,j）点的相对梯度值，rg_right(i+d,j)表 示计算右图中对应点（i+d，j）点的相对梯度值；

303：匹配代价函数构造与计算

匹配代价构造函数如公式（5）所示：

Cost(i,j,d)＝λcost(i,j,d)+（1-λ）RG(i,j,d)   （5）

λ∈[0,1]，优选取λ＜0.5。

根据公式（5）进行匹配代价计算。

如图3所示，步骤102包括：

401：四邻域图构造

匹配代价计算后，利用测地距离来构造四邻域图边的权值。四邻域图的构造 方法即考虑每个像素点的四邻域点，每个点和其四邻域点相连接，边的权重利用 测地距离来赋值。

边权重的赋值方法比直接利用色彩差异来构造权重更合适。在一些实际场景 中，尤其是一些物体的边缘，由于采样的原因，边缘模糊，色彩相近的像素点可 能位于不同的深度场景，如果只利用色彩信息，颜色和距离相近但处于不同深度 的像素点之间的边的权重就较大，而利用相对梯度和色彩在归一化空间的差异够 早的边权值，可以很好地解决这种问题。对于本算法中的四邻域图，构造权重的 方法如下：

图像中每一个像素点和周围的四领域像素点生成四条边，边的权重用相邻像 素点的色彩差异表示。连接像素点(s.i,s.j)和(r.i,r.j)的边，其权重We构造 公式如下：

$w_e=\underset{c\in \{r,g,b\}}{\Sigma }\mathrm{abs}(I_c(s.i,s.j)-I_c(r.i,r.j))+\max \left(\mathrm{rg}(s.i,s.j)\right)---\left(6\right)$

402：最小生成树构造

利用上述方法构造好四邻域图后，利用最小生成树算法构造图像的最小生成 树MST。在最小生成树步骤中，优选采取克鲁斯-卡尔算法。最小生成树反映了 图像中像素点之间的关联特性。通过构造权值的过程，可以看出，最相似的像素 点最有可能在同一深度场景中。

403：匹配代价的叠加

对任意两个像素点p和q，在MST上只有一条路径将他们连接，令C_d(p)代表 p点在视差值假设为d时的匹配代价（即由公式5计算获得的匹配代价），令 代表p点的叠加匹配代价，如下公式（7）表示非局部的匹配代价叠加方 法：

$C_d^A\left(p\right)=\underset{q\in O}{\Sigma }S(p,q)C_d\left(p\right)---\left(7\right)$

O为整副图像像素点的集合。其中S(p,q)定义如公式（8）

$S(p,q)=\exp (-\frac{D(p,q)}{\delta })---\left(8\right)$

δ是恒定值，可以根据实验对比选择一个合适的值，例如以0.05、0.1、0.3 分别进行计算择优而定，本实施例的算法设为0.1。而D(p,q)表示p和q两个像 素点在MST上的距离，这个距离表示p和q两个像素点连在一起所要走的边的 长度。

404：初始视差图获取

利用上述公式进行匹配代价的叠加后，利用WTA算法，获取初始视差图。 过程如下：匹配代价叠加后，获得每个像素点在不同视差值假设下的匹配代价， 利用胜者为王算法（英文名称为:Winner Take All,简称为WTA算法）选出这些 匹配代价当中的最小值，而这个最小值所对应的视差值就是该点的视差值。如此， 可求得图像中每一个像素点的视差值。

如图4所示，步骤103包括：

501：更新四邻域图

利用初始视差图更新私领域图边的权重，更新方法为：对于连接像素点 (s.i,s.j)和(r.i,r.j)的边，设其原有的四邻域图中的权重为w_pre，令 D(s)和D(r)分别表示两个像素点的初始视差值，更新后的权值 w_update＝（1-μ）w_pre+μ(D(s)-D(r))   （9）

其中，μ∈[0,1]；优选μ＞0.5

在同一个视差值水平下，像素点之间的行成的边的权值应该较小，所以本发 明考虑原有权值和像素点视差值差异，并重新赋权值。

502：更新视差图

在更新后的四邻域图的基础上，依据步骤402的方法重新构造新的最小生成 树；

503：匹配代价叠加

在新的最小生成树的基础上，依据步骤403的方法进行匹配代价叠加。

504：在503获得的叠加匹配代价的基础上，利用步骤404的方法计算获得 最终的视差图。

104：视差图后处理

根据前述的方法，我们可分别求得左视图和右视图的视差图。获得左右视差 图后，可以用更多的场景信息对视差图进行有效的后处理，获得更为平滑和准确 的视差图。如图5所示，本算法中后处理过程包括下述步骤：

通过左右一致性检测，获得图像中视差值准确的点。对不满足左右一致性检 测的点采用中值滤波后，将视差值不准确的点赋值为距其最近的视差值正确的点 的视差值。

由于本算法提出的一系列措施，可以获得高质量的视差图。

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能 认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的技术人员 来说，在不脱离本发明构思的前提下，还可以做出若干等同替代或明显变型，而 且性能或用途相同，都应当视为属于本发明的保护范围。