基于互信息的半全局密集立体匹配算法

张桂滨，巩丹超，王仁礼，王 一

1.山东科技大学 山东省基础地理信息与数字化技术重点实验室，山东 青岛，266590；2.西安测绘研究所，陕西 西安，710054；3.航天天绘科技有限公司，陕西 西安，710100



基于互信息的半全局密集立体匹配算法

张桂滨1,3，巩丹超2，王仁礼1，王 一3

1.山东科技大学 山东省基础地理信息与数字化技术重点实验室，山东 青岛，266590；2.西安测绘研究所，陕西 西安，710054；3.航天天绘科技有限公司，陕西 西安，710100

鉴于密集匹配在三维重建中具有重要的作用，本文研究了一种基于互信息的半全局密集立体匹配算法。它利用立体像对对应像素间的互信息作为匹配代价，通过16个方向的一维搜索近似全局匹配；并通过金字塔传递、动态规划、视差优化等策略对立体像对进行逐像素匹配，确定立体像对像素间的一一对应关系。实验结果表明，本文算法对纹理贫乏、有遮挡区域影像仍可以生成精确稠密的视差图。

互信息；立体匹配；动态规划；视差图

1 引 言

三维重建在医学、虚拟现实、地质学等很多方面都有重要的作用。通过匹配方法生成大量的密集匹配点是三维重建的关键技术之一。立体匹配是在不同视点的条件下，获取同一场景的两幅或多幅图像，通过寻找同一空间景物在投影图像中像素点的一一对应关系，得到视差图和深度信息，从而恢复场景的三维立体信息。针对立体匹配在视差不连续区域、遮挡区域以及弱纹理区域匹配难以获得良好视差图的问题，很多研究学者展开了研究。Dhond[1]采用三目约束的匹配算法，降低立体匹配的歧义性。Koschan[2]等对早期的遮挡和无纹理问题及实时立体视觉的实现进行了总结与探讨。Scharstein[3]对两帧图像的稠密立体匹配算法进行了性能测试、分析和比较。Yoon和Kweon[4]提出了基于颜色信息和距离信息的自适应加权窗口的匹配算法。Rhemann等人[5]将具有边缘保护的平滑滤波技术应用到匹配算法中。

目前，根据匹配策略的不同，立体密集匹配算法大致可以分为局部优化的匹配算法和全局优化的匹配算法两类。其中，局部优化的匹配算法对无纹理区域、视差不连续区域和遮挡区域敏感，匹配效果不理想[6]，生成的视差图不连续、不紧密；全局优化匹配算法通过比较立体像对所有像素点间的灰度相关性确定其对应关系，生成稠密的视差图，但计算量大、速度慢。因此，出现了动态规划立体匹配算法[7]、Birchfield和Tomasi的BT算法[8]等。然而，传统的动态规划立体匹配算法[7]和BT算法[8]产生的视差图存在条纹瑕疵，影响视差图的质量，进而影响密集匹配的精度。本文研究的算法通过16个方向的一维搜索近似全局匹配方法，并采用金字塔传递、动态规划和视差优化等策略，解决了视差图不连续、不紧密和条纹瑕疵的问题，相对于全局优化的匹配算法在速度上也有一定的提高。

2 基于互信息的半全局立体匹配算法

本文研究算法基本流程如图1：给定两幅立体影像对，首先，采用金字塔传递的思想对待匹配的两幅立体影像和初始视差图进行分层处理；其次，从金字塔影像的最顶层出发，将待匹配的两幅相应金字塔影像Ibs和Ims，根据初始视差图Ds对像素点进行互信息代价C(p,d)的遍历计算；然后，选取16个方向路径，并对每一像素点在每个方向路径上运用动态规划的思想进行寻优逼近，获得最优路径代价Lr(p,d)；再将每一像素16个方向路径代价Lr(p,d)进行聚合得到聚合代价S(p,d)，选取最优聚合代价对应的视差d作为其最优视差；最后，将视差传递到金字塔影像第二层，作为初始视差图Ds继续进行上述过程，直到金字塔层遍历完成为止，输出最后的视差图D。

图1 算法流程图

2.1 互信息匹配代价计算

假设基准影像为Ib，待匹配影像为Im，基准影像上像素点p的灰度值为Ibp，p在Im中的对应像素点为q，像素灰度值为Imq。像素之间存在下述关系：q=ebm(p,d)，表示影像Ib中像素点p通过视差d映射到影像Im中的对应像素点为q，则基于互信息的匹配代价CMI公式如下：

CMI(p,d)=miIbfD(Im)(Ibp,Imq)

(1)

其中，miIbfD(Im)(Ibp,Imq)为互信息，计算公式如下：

miI1I2(i,k)=hI1(i)+hI2(k)-hI1I2(i,k)

(2)

式中，hI1和hI2为两幅影像像素点的独立熵，hI1I2为两幅影像对应像素点的联合熵。

对于比较好配准的影像，一个影像的像素可以通过另一幅影像对应像素很好地预测到。在立体匹配的过程中，一个影像需要根据视差图D进行映射来找到左右两幅影像对应的像素点，如I1=Ib和I2=fD(Im)，从而达到左右两幅影像立体匹配的目的。两幅影像对应像素点的联合熵hI1I2可以通过对应灰度的联合概率分布PI1I2计算得到。为了减少运算量，先对其进行一次二维高斯卷积(表示为⊗g(i,k))；取对数后，再对其进行一次二维的卷积。本文算法中的卷积核取为5×5，由于0的对数没有定义，我们把0元素的值用一个很小的数来替代，则计算公式如下：

hI1I2(i,k)=log(PI1I2(i,k)⊗g(i,k))⊗g(i,k)

(3)

式(2)中，两幅影像像素点的独立熵hI1和hI2可以仿照联合熵hI1I2的方法求出。

2.2 16个方向代价聚合函数

假设r代表16个方向的任一方向，则每一方向路径的每一像素点p的路径代价计算公式如下：

(4)

其中，Lr表示沿r方向搜索的路径代价能量函数。C(p,d)作为数据项，是像素点p视差为d时的基于互信息的匹配代价，min()函数部分作为平滑项。Lr(p,d)为像素点p视差为d时沿r方向搜索的路径代价。式(4)中增加了路径前一像素点p-r在视差范围内的最小代价。当视差范围变化为1时加上一个P1，当视差范围变化大于1时加上一个P2，其中P1、P2为不连续的惩罚项，二者为常数且P1

(5)

聚合代价S(p,d)表示为每个像素点p的16个方向路径代价Lr(p,d)的和。视差d的取值则可以通过将16个一维搜索路径聚合代价求和最小来获取，即d=dminS(p,d)。

图2 视差空间示意图

如图2所示，一个三维的视差空间，xy平面为影像的二维平面，平面中的每一点代表像素坐标，纵轴d表示视差范围，r表示搜索路径的方向。沿着纵轴d从上往下看，空间中的每一节点存储视差值为d时左图像与右图像对应的互信息匹配代价C(p,d)。xy平面中展示了像素点p(x,y)视差确定过程中16个简单的路径方向，方向路径可以任意选择。网格切面展示了像素点 两个方向路径视差的搜索过程，从切面可以看出，这两个路径不是简单的直线路径。0～9为随意给出的一个视差搜索范围，这里只画出了像素点p(x,y)两个方向视差确定过程的最优路径纵切面。当像素点p(x,y)的16个方向路径代价的聚合代价最小时，对应的视差d即为最优视差。

在代价计算的过程中，图像中每个像素被访问16次，这16次是从不同的方向开始，通过这16个方向的一维搜索近似全局匹配，使本文算法比传统动态规划立体匹配算法[7]、Birchfield和Tomasi的BT算法[8]在生成视差图的精度上有很大的优势，相比于全局匹配方法在速度上也有一定的优势。通常情况下，搜索方向越多，越接近于全局匹配方法；得到的视差图精度越高，视差值越精确。本文研究算法单从16个方向出发，也可以达到很好的效果。

2.3 视差优化

为了避免生成的视差图包含错误的点位，需要对视差图剔除错误的视差点。本文采取的视差优化方法是左右一致性检查方法，具体过程如下：首先以左图为基准影像，右图为待匹配影像，用本文的匹配算法生成视差图Db；然后以右图为基准影像，左图为待匹配影像进行同样的步骤，得到视差图Dm；再根据左右一致性约束的要求，如以左图像为基准图像进行匹配，左图像中的某个点对应的匹配点是右图像中的一个点，那么当以右图像为基准图像进行匹配时，右图像中的这个点对应的匹配点也应该是左图像中的那个点。根据这一要求，将Db中的每一点的视差与它对应的Dm中的视差进行比较， 如果它们差值的绝对值小于等于1，我们就赋予Dbp的值；否则，视为无效的值Dinv。具体公式如下：

(6)

其中，q=ebm(p,Dbp)表示基准影像Ib中像素点p通过视差Dbp映射到待匹配影像Im中对应的像素点q。通过公式(6)进行点对点的检查，能剔除大部分误匹配的点，使生成的视差图更加精确。由于将误匹配的点赋予无效值，因此生成的视差图可能会有很多的空洞，这些空洞即为错误的匹配点。本文通过内插的方法填充空洞，使生成的视差图连续紧密。

3 实验结果与分析

图3 Tsukuba(左)和Sawtooth(右)

如图3所示，Middlebury大学数据库中提供的Tsukuba(视差范围设为16个像素)和Sawtooth(视差范围设为20个像素)两组近景摄影测量立体像对数据，大小分别为384×288像素和434×380像素。其中Tsukuba图像纹理丰富，存在遮挡现象，如人物雕像后面及台灯下面大部分黑色阴影区域即为遮挡区域；Sawtooth图像纹理贫乏，大部分地方为弱纹理区域。为了验证本文算法在遮挡区域和纹理贫乏区域密集匹配的适应性以及准确率，现分别采用SAD+DP(传统的基于灰度差的绝对值和的动态规划方法)、BT+DP(Birchfield和Tomasi[6]提出的BT算法)和本文算法对两组数据进行对比实验。

对于密集匹配结果的准确率，可以根据Scharstein[3]文献中的错误匹配率公式，通过将真实视差图与三种算法得到的视差图进行计算，得到错误匹配率，计算公式如下：

(7)

其中，N是像素总数，δd是判断视差对错的阈值，通常经验值为1.0，dC(x,y)为相应算法得到的视差图中像素点(x,y)处对应的视差值，dT(x,y)为数据库中提供的真实视差图中像素点(x,y)处对应的视差值。两组数据的实验结果如图4和表1所示。

图4 真实视差图及各算法生成的视差图

表1 各算法错误率及效率统计表

数据算法SAD+DP算法BT+DP算法本文算法错误率%用时s错误率%用时s错误率%用时sTsukuba6．583．1406．513．0472．863．437Sawtooth5．203．7344．413．8292．494．234

图4为真实视差图与各算法生成视差图的结果。图中分别展示了Tsukuba和Sawtooth两组近景摄影测量立体像对数据在SAD+DP算法、BT+DP算法和本文算法下生成的视差图。将各算法对Tsukuba和Sawtooth两组数据生成的视差图与真实视差图对比可以看出，对于Tsukuba数据中人物雕像后面及台灯下面大部分黑色阴影区域(遮挡区域)和Sawtooth数据中的纹理贫乏区域，如图3所示，本文算法都能生成连续、紧密的视差图。虽然对Tsukuba数据中的遮挡区域和Sawtooth数据中的纹理贫乏区域采用SAD+DP算法和BT+DP算法也能生成视差图，但是SAD+DP算法与BT+DP算法生成的视差图会产生条纹瑕疵和空洞瑕疵，这势必会影响视差图的精度，而在本文的算法下生成的视差图不会产生条纹瑕疵和空洞瑕疵，视差图连续、紧密与真实视差图最为接近，这也表明本文算法生成的视差图精度最高。所以对于存在遮挡区域和纹理贫乏的影像，本文算法较SAD+DP算法和BT+DP算法具有更好的适应性。

表1为算法错误率及效率统计表，由表1可以看出，本文算法在Tsukuba和Sawtooth两组数据的匹配错误率上明显比SAD+DP算法和BT+DP算法低，说明本文算法的匹配结果最好，精度最高。这也间接验证了本文算法生成的视差图与真实视差图最为接近这一结论。在匹配算法的效率上，本文算法的效率稍微低于其它两种算法，这是因为本文算法是在16个方向的约束条件下实现的，约束条件的增加使本文算法的效率略有降低，但匹配精度却有很大提高。

由图4和表1实验结果可知，本文算法效率虽略有降低，但是相比SAD+DP算法和BT+DP算法，其在精度上却具有很大的优势，可以在密集匹配中发挥更好的作用。

图5 卫星立体像对数据(左)及视差图(右)

图5(左)为一组卫星立体像对数据，数据中存在纹理贫乏的平原地区和有遮挡现象的山地地区。如图5(左)立体像对数据中的左下角部分大多数为平原地区，纹理贫乏，右上角部分大多数为山地地区，遮挡现象明显。该部分利用卫星遥感数据来验证本文算法的可行性，并通过目视的方法对实验结果进行主观的评价。采用本文算法对图5(左)的卫星立体像对数据进行密集匹配，得到的视差图结果如图5(右)所示。由图5(右)视差图结果可以看出，在纹理贫乏的平原地区或者有遮挡现象的山地地区，本文算法仍然具有不错的匹配结果，仍能够生成连续紧密的视差图，进一步证明了本文算法对于纹理贫乏、有遮挡区域影像的匹配具有一定的适应性。

4 结 论

本文研究了一种基于互信息的半全局密集立体匹配算法，并利用Middlebury大学数据库中的影像数据对本文算法与动态规划立体匹配算法[7]、Birchfield和Tomasi的BT算法[8]进行对比实验。实验结果表明，本文算法对纹理贫乏、有遮挡区域影像的匹配具有一定的适应性，并有效解决了视差图的条纹和空洞瑕疵，生成的视差图更加精确稠密；最后利用实际卫星遥感影像数据对本文算法进行实验，实验结果进一步验证了本文算法对弱纹理、有遮挡区域影像匹配的可行性结论，充分表明本文算法在密集匹配中具有一定的应用价值。

[1]Dhond U R, Aggarwal J K. Structure from stereo-a review[J]. Systems, Man and Cybernetics, IEEE Transactions on, 1989, 19(6): 1489-1510.

[2]Koschan A. What is new in computational stereo since 1989: A survey on current stereo papers[M]. TechnischeUniversitat Berlin, Fachbereich 20, Informatik, 1993.

[3]Scharstein D, Szeliski R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms [J]. International journal of computer vision, 2002, 47(1-3): 7-42.

[4]YOON K J, KWE0N I S. Adaptive support weight approach for correspondence search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006，28(4) :650 - 656.

[5]RHEMANN C, H0SNI A, BLEYER M, et al. Fast cost-volume filtering for visual correspondence and beyond [C]. IEEE Conference on Computer Vision and Pattern Recognition, 2011.

[6]白明，庄严，王伟． 双目立体匹配算法的研究与进展[J]．控制与决策，2008，23( 7) : 721-729．

[7]VEKSLER O．Stereo correspondence by dynamic programming on a tree[C]. Proceedings of IEEE Computer Society Conf on Computer Vision and Pattern Recognition,San Die-go，USA，2005．

[8]Birchield S,Tomasi C. Depth discontinuities by pixel-to-pixel stereo[C]. Proceedings of the Sixth IEEE International Conference on Computer Vision, 1988.

[9]H. Hirschmuller. Accurate and efficient stereo processing by semi-global matching and mutual information[C]. in IEEE Conference on Computer Vision and Pattern Recognition, San Diego, USA,2005.

Semi-Global Dense Stereo Matching Algorithm Based on Mutual Information

Zhang Guibin1,3, Gong Danchao2, Wang Renli1, Wang Yi3

1.Shandong Provincial Key Laboratory of Geomatics and Digital Technology, Shandong University of Science and Technology, Qingdao 266590,China 2.Xi’an Research Institute of Surveying and Mapping, Xi’an 710054, China 3.Aerors Inc., Xi’an 710100,China

As the dense matching plays an important role in 3D reconstruction, the paper studies a semi-global dense stereo matching algorithm based on the mutual information. It uses the mutual information of corresponding pixels between the stereo pairs as matching cost, and does approximate global matching through one dimensional search of sixteen directions and determine the corresponding relation between the pixels of the stereo pairs through the pixelwise matching supported by pyramid passing, dynamic programming and disparity refining strategies. The experiment results show that the algorithm can still generate precise and dense disparity image which has poor texture and occlusion area image.

mutual information；stereo matching；dynamic programming；disparity Image

2015-01-27。

张桂滨(1988—)，男，硕士研究生，主要从事遥感技术与应用以及图像处理方面的研究。

P231

A