结合最小生成树的立体匹配算法

北方民族大学电气信息工程学院 沈书好 白伟华

结合最小生成树的立体匹配算法

北方民族大学电气信息工程学院 沈书好 白伟华

结合最小生成树的立体匹配算法能够得到更精确的视差图，先运用相对灰度差与Census变换提取特征，以颜色和空间距离为权值建立最小生成树，以此进行匹配代价聚合，获得结果视差图。

最小生成树MST；视差图；Census变换；相对灰度差

1 算法流程

校正过左、右图像之后，先通过相对灰度差匹配和Census变换加权提取特征，再运用最小生成树进行匹配代价聚合，再滤除坏点视差更新，得到视差图。主要算法框图如图1所示。

图1 立体匹配框图

2 相对灰度差匹配

首先，对左、右两幅图像进行横轴方向的sobel边缘检测，固定截断阈值，得到左、右横向灰度梯度图。

再计算半像素点的梯度值，即水平方向上两个相邻像素点梯度值的平均。然后拿每一点与前、后半像素点的梯度值进行比较，求出极值。最后计算从左向右的相对灰度差匹配代价C(p,d)，如式(1)：

其中p为左图中一点，q为右图中一点，q横坐标比p小d个像素。IL(P)、IR(P)分别为点p、点q的灰度梯度值。ILmin(P)、ILmax(P)与IRmin(q)、IRmax(q)分别为p与点q的梯度极小值、极大值。

3 Census变换

传统Census变换是比较一点像素值和它四周的点的像素值，然后进行汉明编码，即四周的点的像素值大于等于中心点，编码为1；反之，编码为0。再对点与点之间汉明码进行异或运算求得汉明距离作为匹配代价。

也可依据高斯分布在左图某点周围进行偶数多次采样；每两个采样点合成一组，以组集作为该点的模板，组内进行比较，再对结果进行0、1编码[1]。在设置不同的视差d时，对以左图某点同样模板对右图中比该点横坐标小d的点进行编码，并这两汉明码的距离作为左图这点视差为d的匹配代价。

4 最小生成树MST代价聚合

D(s,v)与s、v两点距离和颜色的差值相关，构建最小生成树每两点之间的权值w设置如式(2)所示：

如式(3)，计算自底向上聚合代价，其中sc是s的子节点。

再自顶向下代价进行聚合，如式(4)，其中spr是s的父节点[2]。

由以上两式两步可以对整张图进行全局代价聚合，也可以通过shift-means颜色分割图像，再对分割的每个小块进行这两步代价聚合。对于每个点选取最小聚合代价所对应的视差为最终视差，得到左图视差图。

根据上述对右图点进行最小生成树的代价聚合，中得到右图视差图。最后，通过左右一致性进行检测，视差一致的点视为稳定点。再对所得视差图以公式(5)设置不同视差d下的代价聚合。其中当s是稳定点时，D(s)代表它在左视差图中算得的视差。

5 总结

本文采取最小生成树MST进行匹配代价聚合，可以获得更高的视差图精度。

[1]雷磊,郑江滨,宋雪梅．基于改进Census变换的立体匹配算法[J]．计算机应用研究,2013,30(10):3185-3188．

[2]Yang Q．A non-local cost aggregation method for stereo matching[C]//Computer Vision and Pattern Recognition(CVPR),2012 IEEE Conference on．IEEE,2012:1402-1409．