半分辨率半路径数量的半全局匹配方法*

于　英　张永生　薛　武

(1.信息工程大学,郑州 450052；2.江西省数字国土重点实验室,抚州 344000)

0　引言

基于半全局的影像逐像素密集匹配方法，因具有匹配精度高、物体边缘匹配效果好、对图像亮度差异适应性良好以及同等匹配精度条件下匹配速度快等诸多优点，得到了多方面的关注。该方法采用多个一维路径聚合的优化策略容易在FPGA和GPU 实现并行计算，可以大幅度的提高匹配的速度[1-3]。但在基于视觉驱动的导弹匹配导航、无人机动态准实时测绘[4]等对实时性要求高的航空场合，特别需要指出的是无人机动态准实时测绘得到的影像数量多并且影像分辨率高，对影像的匹配速度提出了极高的要求，半全局匹配的速度仍达不到要求。

半全局匹配算法原文作者指出为实现较好的匹配效果，代价聚集路径的数量要为16个(最少8个)，但作者并没有说明原因。显然代价聚集路径的数量的减少，可以显著提高匹配的速度，但造成的匹配结果质量的降低程度需要进行研究分析。文献[2]尝试采用4条路径进行代价聚集，但没有认真考虑由此带来的匹配质量降低问题。文献[5]研究了半全局匹配聚集路径数量衰减与匹配质量损失的关系问题,但验证数据均采用地面数据，验证也不够充分。本文的研究旨在以无人机高分辨率影像为数据基础，系统性的研究路径数量衰减对匹配质量影响。鉴于原始影像的分辨率较高，更进一步研究了半全局匹配方法进行隔点匹配加速方法，这几乎可以提高一倍的匹配速度。

1　半全局匹配原理

半全局优化匹配算法的原理如式(1)所示：

(1)

式中，第一项表示所有像素点的匹配代价之和；第二项和第三项分别利用系数P1和P2对像素点p与其邻域内的像素点深度差存在的较小变化和较大变化两种情况进行了惩罚，即平滑约束，显然P1

附加平滑约束并通过能量函数最小化的方法是全局匹配的基本思想，半全局匹配方法实际使用时将二维图像NP(Nondeterministic Polynomial)问题的完全解问题转化为通过多个方向的一维平滑约束来近似一个二维平滑约束的方法，这极大的减少了计算量。图1中的左图为全局匹配的无向图，右图为半全局匹配的无向图，实线为匹配路径，线段间的节点为匹配路径经过的像素点，其中S为源点、T为终点。半全局匹配的路径相比全局匹配的路径要少得很多，因此得名。经典的动态规划算法只能沿着扫描行进行一维优化，使得匹配结果产生拖尾效应，在匹配算法中利用8个(或16个)方向上的一维平滑约束来近似拟合一个二维平滑约束。

图1　全局匹配与半全局匹配的无向图对比

半全局匹配算法在每一条路径上依据动态规划的思想按照式(2)和式(3)进行计算，式中的第一项表示对像素点p赋予深度d的匹配代价；第二项是当前路径上p的上一个点沿着p-r方向包含了惩罚系数的最小匹配代价，如图2所示；第三项则对最优路径的产生没有施加影响，加入这一项的目的仅仅是为了防止L过大超出计算机字节限制。

(2)

Lr(p0,d)=c(p0,d)

(3)

图2　p-r方向包含了惩罚系数的最小匹配代价

然后，将各个方向上(通常为8个方向)的匹配代价相加形成为总的匹配代价，如公式(4)，在最大视差值范围内求取S(p,d)的最小值对应的视差值dbest即为匹配的结果。

(4)

2　路径优化整合及实验

图3　8路径方向表示聚集示意图

图4　半全局单方向匹配结果

图5　两方向匹配结果

图6为4个路径方向(半路径)与8个路径方向(全路径)的匹配结果图，两组匹配结果几乎并无差异，因此选用4个路径方向进行半全局匹配已经可以满足需求，即只采用ScanA就可以得到良好的匹配结果与匹配速度，此外在匹配执行过程中只需要存储两行的代价计算结果，极大减少内存的使用量。

图6　半路径与全路径匹配结果

图7　隔点匹配中路径代价值临近拷贝示意图

3　半分辨率匹配策略及实验

图8　隔点匹配效果图

通过分析半全局的匹配结果，发现在图像中一个物体内部相邻元素的视差值基本上是不变的，也就是说可以采用隔点匹配的方法提高计算速度和内存资源。如图7所示，本文将半全局匹配方法仅作用在偶数像素上，对于奇数像素采用最简单的代价值拷贝的方式。在匹配路径数量上选择了4条路径，因为2条路径和8条路径与此并无特别之处。从图8的匹配结果可见，不进行拷贝方式的隔点匹配得到的视差图比较稀疏，而隔点匹配并拷贝的方式得到的视差图效果与图6中半路径的匹配结果基本一致。

4　结论

本文以高分辨率无人机影像为数据基础，研究了半全局匹配与路径的关系问题和半分辨率匹配的问题，研究结果表明：

1)两条路径的半全局匹配可以较好的克服单路径匹配的条纹效应和微移动效应，对匹配精度要求不高的可以使用。

2)半路径(4条路径)的匹配与全路径(8条路径)的匹配结果相当，但匹配速度得到了提高并且内存使用量极大减少。

3)半分辨率匹配的方式即隔点匹配临近拷贝的方式得到了匹配结果与半路径的匹配结果基本一致，但计算量几乎减少了一半，极大提高了匹配的速度。

[1]S.K.Gehrig，F.Eberli，and T.Meyer.A real-time low-power stereo vision engine using semi-global matching.Proc.IEEE Int.Conf.on Computer Vision (ICCV)，5815:134-143，2009

[2]I.Ernst and H.Hirschmuller.Mutual information based semi-global stereo matching on the gpu[C].In ISVC ’08: Proceedings of the 4th International Symposium on Advances in Visual Computing，pages： 228-239，2008

[3]胡亮,段发阶,丁克勤,叶声华.基于线阵CCD钢板表面缺陷在线检测系统的研究[J].计量学报，2005,26(3)

[4]张永生.现场直播式地理空间信息服务的构思与体系[J].测绘学报.2012,40(1)

[5]Hermann S，Morales S，Klette R.Half-resolution semi-global stereo matching[C].Intelligent Vehicles Symposium (IV)，IEEE，2011: 201-206

[6]Y.Ohta，T.Kanade.Stereo by two-level dynamic programming[C].Proc.Int.Joint Conf.Articial Intelligence 2 (1985)：1120-1126