结合图像分割的半全局立体匹配算法

鲁光明，王竞雪，2

(1.辽宁工程技术大学 测绘与地理科学学院，辽宁 阜新 123000；(2.西南交通大学 地球科学与环境工程学院，成都 611756)

0 引言

双目立体视觉作为计算机视觉的一个重要应用方向，能够在深入研究人类的视觉成像系统之后，进一步利用摄像机成像系统和计算机技术对其进行模拟[1-3]。双目立体视觉的实现需要摄像机标定、图像获取、特征提取、立体匹配和三维重建5个步骤。作为立体视觉的关键部分，立体匹配的精度直接影响视差图及深度图的质量，并在三维重建工作中占有举足轻重的地位[4-5]。Scharstein等[6]提出立体匹配算法可以由匹配代价计算、匹配代价聚合、视差选择和视差优化组成，并在此基础上将立体匹配算法分为三类[7-10]：局部立体匹配算法、全局立体匹配算法以及半全局立体匹配算法。局部立体匹配算法，即选择图像中一定区域内的像素作为计算该像素点匹配代价的约束区域，然后通常采用胜者为王(winnner take all，WTA)的视差选择策略确定该点的最优视差值，进而获取视差图；全局立体匹配算法，即通过在能量函数中建立数据项、平滑项以及遮挡项将匹配算法转化成求解全局能量函数最优值的问题，进而得到致密视差图；半全局立体匹配作为一种改进的动态规划的方法，在提高了匹配结果精度的同时实时性得到有效提升，其平等地对待多个一维路径，对各个一维路径的结果进行合并，以此来表达二维的情况。

立体匹配中实时性与精确度兼容的问题一直是研究的热点。为提升匹配效率，王云峰等[11]提出一种基于自适应权重AD-Census变换的双目立体匹配算法，实时性好，但匹配精度一般。其中的AD变换可以准确快速地表达出像素点的灰度值差异，但其鲁棒性较差[12]。为提高匹配精度，曹晓倩等[13]针对斜面参数优化全局立体匹配算法做了研究，提出全局能量函数的概念，同时利用斜面参数对视差值进行有效的替换，因此，利用该算法实现立体匹配精度较高，但欠缺对实时性的考虑。综合考虑了算法准确度和时间复杂度，Hirschmuller[14]提出了SGM算法，其主要运用多路径方式进行代价聚合值的计算，保证实时性的同时具有较好的精确度。SGM算法继承了传统动态规划的高效性，此外还具有较强的鲁棒性。而SGM算法在解决视差突变情况时，赋予一个恒定的惩罚，导致在弱纹理区域、遮挡区域发生误匹配以及边缘表达不准确的现象。葛忠孝等[15]提出了基于树形结构的SGM算法，有效地解决了弱纹理区域的误匹配以及实时性问题，但其算法对于遮挡问题、整体匹配精度和边缘区域的匹配效果有待解决和提高。以此为基础，本文提出结合图像分割的SGM算法。通过AD变换计算初始匹配代价，为解决其鲁棒性较差的问题，采用SGM算法进行代价聚合，增强鲁棒性并在原有SGM的基础上增加了图像分割，改变在视差突变区域的恒定惩罚，使其更符合实际情况，有效地降低了在弱纹理区域和遮挡区域的误匹配率，并且增加了边缘表达的完整性。通过二者结合有效地解决了实时性和精确度难以兼顾的问题。此外，由于遮挡问题的出现，减弱了匹配的有效性和完整性，故本文在保证精确度和实时性的前提下利用左右一致性对遮挡点进行检测，并在此基础上对无效值进行填充，确保结果视差图具有清晰、完整性，最后利用中值滤波对视差图进行优化使得本文算法具有较高的可行性及有效性。

1 双目立体匹配

双目立体视觉过程是利用双目立体相机获得双目立体像对，然后对所拍摄的影像进行相片畸变校正与核线校正，选用适合立体像对拍摄场景的匹配算法，建立匹配基元之间的关系，进而恢复深度到三维坐标。在双目立体视觉中，通过匹配算法寻找参考影像中的待匹配点在目标影像中对应的同名匹配点，进而获取同名点之间的位置差异，即视差。双目立体视觉利用匹配代价计算作为匹配像素点相似性的衡量参数。在进行AD变换时，左图像上待匹配点为p(x，y)，其灰度为IL(x，y)；右图像上x方向视差为d的像素点为q((x-d)，y)，其灰度为IR((x-d)，y)，则p，q2点的匹配代价C(p，q)表示如式(1)所示。

C(p，q)=IL(x，y)-IR((x-d)，y)

(1)

2 结合图像分割的SGM的立体匹配算法原理

本文首先使用AD变换计算左、右图像上对应像素的匹配代价值。由于进行代价计算的像素点是孤立的，并且计算结果是模糊的，易造成误匹配的情况，而SGM算法中全局能量最优化策略，充分利用匹配点及邻域的像素进行平滑约束，使其更符合真实场景，再通过最小路径求和得到代价聚合值。但是SGM算法在视差突变情况下给与恒定惩罚会引起误匹配现象，影响匹配精度，因此，本文通过加入均值漂移图像分割信息可以有效地较少误匹配，保证边缘的完整性，在得到初始视差图后使用双曲线拟合获得亚像素级的视差图，然后采用左右一致性检测获取遮挡点，在此基础上对无效值进行填充，最后使用中值滤波进行优化获得最优视差图，本文算法整体流程如图1所示。

图1 本文算法流程图

2.1 初始视差图生成

1)SGM算法。以左图像为基准，利用式(1)进行代价计算，得到左、右图像上对应像素p，q的匹配代价值C(p，q)。由于采用AD变换得到的匹配代价值往往是模糊的，相应像素点是孤立的，再加上噪声点以及误匹配等因素的影响极大限度地降低了匹配精度。因此，通过SGM算法对待匹配像素的邻域内进行平滑约束，从而改变像素点的孤立以及误匹配情况，在提高精度的同时还对视差变化实施了一定的约束，定义一个基于视差图D的全局能量函数E(D)，表达如式(2)所示。

(2)

式中：第一项C(p,Dp)是在视差图D下所有像素点的匹配代价，Dp代表像素点p的视差量；第二项中Np为像素点p的邻域，Dq为像素点q的视差量。第二项是对像素点p邻域内的所有像素点q进行平滑。此时，平滑分为2种情况：根据视差变化量大小的情况分别对其进行恒定的较大惩罚P2和较小的惩罚P1。T[]为截断函数，根据判断条件的是否成立，分别对其赋值为1和0。但在客观真实条件下，引起视差突变的原因有很多种，仅仅给予一种恒定的惩罚会导致匹配精确度的降低，于是本文在原有算法的基础上加入均值漂移图像分割信息。

2)均值漂移图像分割。均值漂移算法是一种基于密度梯度上升的非参数方法，通过迭代运算找到目标位置，实现目标分割。它显著的优点是算法计算量小，简单易实现，适用于图像分割。均值漂移是一种有效的迭代算法，对图像中的像素进行迭代，进而对其进行不同块的划分，处于同一分割块的像素具有相同的标记，标记的不同表明分割区域的不同，由此作为分割依据，获得的分割图具有精确的边界定位，并且具有有效的区域分割，根据视差突变的区域是否在同一分割块的情况与SGM算法结合可以降低代价聚合过程中在弱纹理及遮挡区域的误匹配率，同时得到更完整的边缘部分，提高算法的精确度。

3)改进的SGM算法。基于图像分割信息可以对图像进行有效准确的划分定位，本文将其与全局能量函数进行有机结合，在原有SGM算法对视差突变区域进行恒定惩罚的基础上，根据其是否在同一分割块分别给予不同的惩罚值λ1、λ2。通过上述准确清晰的判断后，全局能量函数有了全新的表达(式(3)、式(4))。

(3)

(4)

但是在实际情况中，最小化的问题不能用一些常规的数学方法有效解决。因此，SGM算法对于任一方向上的路径代价聚合都是由一维进行，并且在每个方向上的处理方式相同。像素点p在深度为d时的聚合代价S(p，q)是由所有一维最小代价路径上的代价累加得到的，具体说明如图2所示。

图2 匹配代价的聚合

在方向r中，像素点p在视差d处的代价L′r(p，d)定义为式(5)。

(5)

式中：左、右图像上对应像素点间的匹配代价值C由AD变换求得。等式右边的第二项部分分别表示的是在路径上的前一个点p-r的最小代价、p-r点的视差差值为1的代价聚合值进行的较小惩罚和p-r点的视差差值大于1的代价聚合值进行较大的惩罚。沿着路径r，L′的值一直增加，为避免结果较大的问题，将整个公式减去前一个像素点的最小路径代价，由此将式(5)变换为式(6)。

(6)

式中：k为p-r点的视差差值。如果点p为该方向上的第一个点，则该点在某一方向上的匹配代价为：Lr(p，q)=C(p，q)。聚合所有方向上的匹配代价得到总的代价为S(p，q)，表达如式(7)所示。

(7)

4)初始视差图生成。经过上述代价计算和代价聚合后得到初始视差图(粗视差图)，在对每个像素点的视差进行选择时，该点处的视差d应保证总的匹配代价S(p，q)最小，表达如式(8)所示。

DL(P)=argmindS(p，d)

(8)

2.2 视差图优化

1)双曲线拟合视差选择。通过以上公式得到的视差图的视差值是整数级的，在后续立体像对像素点深度恢复完成后，为保证其形成深度图的连续性同时还要保证得到的视差图更加符合真实实物情况，故在此部分使用抛物线拟合的方法，其原理是由当前视差值的相邻视差值构成一条抛物线，抛物线的最低点即为亚像素级视差(图3)。

图3 抛物线拟合示意图

2)视差图遮挡检测。上述部分描述的是粗视差图的生成。立体视觉领域存在的遮挡问题导致匹配结果正确率有所下降，因此解决遮挡问题是必要的。为此，首先对遮挡区域进行精确检测，然后在此基础上对视差值进行有效重估，进而可以得到完整并且准确的视差图，再通过左右一致性检测分别获取左右影像的视差图，对于左视图的点p求得其视差为Dbp，将点p在右图中的视差点p-Dbp记为点q，点q的视差值为Dmp，若|Dbp-Dmp|>1，则Dbp为无效，点p为遮挡点。得到的视差表达如式(9)所示。

(9)

式中：Dinv插差；ebm为外极线。

3)视差优化。通过左右一致性校验这一步骤，可以得到无效点的视差值，接下来对无效点进行有效的赋值。无效点可以分为2类：遮挡点及误匹配点，对这2种类型的视差赋值需要使用不同的方法。无效值类型的不同使差值方法也有所区别，以遮挡区域的某一遮挡点为例，其方法是采用背景的外插值进行填充，而对于误匹配点的情况，其方法是利用邻域内的像素值进行内插。由左右一致性校验这一步骤能够对遮挡点和误匹配点进行区分，如图4所示。结合对极几何原理对无效值的类型进行判断，即通过某一点的外极线是否穿过视差函数曲线的判断条件可以对每一个无效值进行辨别，从而进行不同的赋值。当通过某一点的外极线穿过视差函数曲线时，像素点p1是遮挡点；否则，像素点p2是误匹配点。

图4 辨别遮挡与误匹配点示意图

为了对无效点进行合理有效的填充，在进行赋值时如果误匹配点和遮挡区域相邻，则认为是遮挡点。遮挡点的出现很大程度是由于背景与前景接触时背景发生相对较小偏移量所致。进行无效值填充时与路径代价聚合方式相似。最终的视差图D′p如式(10)所示。

(10)

式中：vpi表示点的8邻域内的点；seclowi表示8邻域像素视差的第二最小值；medi表示邻域内像素视差的中值。同样，无效值类型的不同使得填充方法也具有差异性。对遮挡点而言，通过其邻域视差的第二最小值对该视差值进行填充；对误匹配点而言，采用相邻像素的中值进行有效的赋值。在视差优化部分中，使用中值滤波对视差图进行优化。

3 实验结果及分析

为验证本文算法的可行性，在Middle-bury立体匹配算法测试平台提供的标准立体图像中选取4组影像对(Tsukuba，Venus，Teddy，Conesde)。用本文算法进行测试，原始图像如图5所示。图6为所选择的标准立体图像的标准视差图。

以Tsukuba为例(图7)，分别为该数据集的真实视差图、需检测的所有视差区域、视差不连续区域、非遮挡区域检测图。

图5 原始图像

图6 标准视差图

图7 Tsukuba的检测图

在Matlab 2019a的集成环境中对本文算法进行实现。将本文实验结果分别与局部立体匹配中的块匹配算法(DM)、全局立体匹配中的动态规划匹配算法(DP)和基于树形结构的半全局立体匹配算法(T-SGM)进行比较，具体结果如图8所示。

为了进一步对立体匹配算法在不同区域的匹配效果进行评价，Middle-bury测试平台分别通过非遮挡区域误匹配率、所有视差区域误匹配率以及视差不连续区域误匹配率3项指标对不同匹配算法进行排名比较。本文算法的具体数据如表1所示，本文算法与其他算法比较的相关数据如表2所示。

其中，遮挡区域表示影像中被遮挡的部分，视差不连续区域表示影像中相邻像素之间的视差值不能满足一定的阈值。

表2中第2～5列的数值分别表示使用各种算法在4对测试图像的非遮挡区域误匹配点所占的百分比，最后1列数值代表每个算法在4对测试图像中非遮挡区域误匹配率、视差不连续区域误匹配率以及所有视差区域误匹配率计算得到的平均误匹配率。

图8 不同立体匹配视差结果图比较

表1 本文算法在middlebury评价结果 %

表2 4种算法的误匹配率比较 %

结合图8和表2可以看出，动态规划的匹配算法存在仅在单条扫描线上进行视差优化的问题，导致仅扫描线内的约束限制可以被有效利用，而扫描线之间的约束没有得到充分的使用，从而发生条纹拖尾现象。与之相比在本文算法中：SGM算法代价聚合方式是多个方向上的聚合，与全局立体匹配中动态规划算法(BP)比较，可以有效避免一维扫描条纹拖尾现象出现；块匹配算法(DM)的视差优化部分无法在整幅影像有效地进行，与之相比本文可以避免块匹配中的视差优化问题，提高精确度；文献[15]在代价计算部分使用BT差值算法，导致代价计算的时间较长；代价聚合部分在原有SGM算法的基础上，通过路径聚合对实时性与精确度的影响综合考虑，在原有的水平、竖直方向上的4个路径上进行分析实验，提出基于树形结构的匹配，首先在竖直方向上引用可遍历待匹配点邻域的结构作为辅助计算，然后在此基础上引入水平向的结构进行代价聚合(着重横向，弱化纵向)。经过上述的方法，SGM代价聚合的路径降至为4条。该方面的改进有效提高了运算速率，提高了在弱纹理区域的匹配精度，但利用树形结构进行路径聚合时，出现各个路径难以兼顾现象，导致竖直方向的路径没有得到充分利用最终使整体匹配精确度一般，同时遮挡问题以及边缘完整性问题没有得到有效改善。与之进行比较，本文算法处理效率更高，通过AD变换快速的进行代价计算，充分利用纹理信息，为后续代价聚合部分的路径聚合的顺利进行提供了良好的基础；精度更高，在原有SGM算法的基础上结合图像分割信息减少算法在遮挡和弱纹理区域的误匹配；图像更加清晰、完整，在遮挡区域进行左右一致性检测并在此基础上对无效值进行有效的赋值填充，最后使用中值滤波进行优化。根据上述比较，本文算法不但具有实时性、精确性，而且在遮挡、弱纹理以及边缘区域均有较高的普适性，匹配结果有效可靠。

4 结束语

本文通过AD变换和改进的SGM算法相结合得到了初始视差图，然后通过左右一致性校验对遮挡点进行检测，并在此基础上对无效值进行填充，最后利用中值滤波对视差图进行优化。实验表明，在代价计算和代价聚合部分，本文利用AD变换和增加图像分割信息的SGM算法可以解决立体匹配中实时性和精确度难以兼容的问题，使算法具有较强的鲁棒性的同时降低了其在弱纹理区域以及遮挡区域的误匹配率，此外，边缘区域能够得到较好的表达；在视差选择部分，采用抛物线拟合法使视差达到亚像素分辨率；在视差优化部分，对得到的初始视差图进行左右一致性检验可以有效地改善遮挡问题，并在此基础上对无效值进行有效的赋值。其中，误匹配点和遮挡点分别采用内插值、外插值的方法进行赋值，保证物体轮廓的完整和清晰，更加符合客观真实实物，同时采用中值滤波对其进行优化得到最优的视差图。与其他立体匹配算法比较，本文算法在弱纹理、遮挡以及边缘区域的立体匹配改善效果较好，但针对视差不连续区域有待改善，后续进行算法相关改进研究。另外，本文算法对生产中航测遥感影像欠缺实验分析，后续应对此进行深入研究。