0 概述

在计算机视觉领域, 立体匹配技术一直是研究的热点和难点。现有的立体匹配方法主要分为局部匹配和全局匹配2类。全局立体匹配方法通过建立能量方程并对其进行最小化来获取视差, 采用的技术主要有置信度传播^[1]、动态规划^[2-3]、图割^[4-6]等。虽然全局匹配方法能获得很好的视差, 但是其复杂度较高, 应用性不强。局部立体匹配方法只考虑像素邻域范围内的像素点, 与全局立体匹配方法相比复杂度较低。文献[7]把局部匹配方法分为代价计算、代价聚集、视差求取、视差求精4个步骤, 其中, 代价聚集被认为是局部立体匹配方法的核心。

文献[8]利用O(1)复杂度的双边滤波器进行代价聚合, 因其受制于快速双边滤波时的量化手段, 算法的运行结果并不好。文献[9]提出将原始的彩色图作为导向图来进行导向滤波代价聚集, 由于其假设视差数据在结构上和导向图相似, 因此该方法的效果比双边滤波更好。文献[10]依据像素相似度, 对每个像素建立支撑区域, 其代价聚集取得了良好的效果。基于窗口或支撑区域的方法, 其待聚集区域在本质上是局部的, 文献[11-12]提出非局部代价聚集的思想, 将图像像素点看作图的节点, 像素点的颜色差异作为边的权重, 来建立最小生成树。该方法考虑了图像中全局像素对于待聚集像素的影响, 因此取得了较好的效果。文献[13]将卷积神经网络应用于代价聚集, 而文献[14]采用多棵最小分离树来进行3D代价聚集, 虽然两者都取得了良好的效果, 但其依赖于数据驱动或强大的硬件设备, 时间成本较高。

文献[15]以超像素作为节点进行随机游走, 本文将其与文献[11-12]采用的非局部代价聚集方法相结合, 提出一种改进的代价聚集算法。通过简单线性迭代聚集(Simple Linear Iterative Cluster, SLIC)算法进行超像素分割, 构建超像素最小生成树, 计算超像素代价。以一定的权重融合初始像素代价和超像素代价, 采用winner take all进行视差后处理, 得到立体匹配结果。

1 基于超像素的快速代价聚集

本文提出的代价聚集方法流程如图 1所示。

应用SLIC算法生成图像的超像素。利用克鲁斯卡尔算法生成超像素最小生成树, 通过树形滤波器生成超像素代价。基于权重融合AD-Census代价匹配得到的像素代价C_PIXEL⁰(u, v, d)和超像素代价C_SUPERPIXEL¹(sup u, sup v, d), 生成像素代价C_PIXEL¹(u, v, d), 应用winner take all策略得到视差数据。

1.1 AD-Census代价匹配

采用AD-Census代价计算的方法生成初始像素代价C_PIXEL⁰(u, v, d)。AD-Census代价由2个部分构成:绝对误差(Absolute Difference, AD)变换和Census变换。

AD变换通过计算双目图像中2个像素的颜色差异得到匹配代价, 计算过程如下:

$ {C_{{\rm{AD}}}}\left( {u, v, d} \right) = \frac{1}{3}\sum\limits_{i \in R, G, B} {\left| {I_i^{{\rm{Left}}}\left( {u, v} \right) - I_i^{{\rm{Right}}}\left( {i - d, v} \right)} \right|} $

(1)

Census变换是一种非参数变换。首先对待匹配双目图像进行Census变换, 然后比较双目图像中2个像素的Census编码, 得到汉明距离并将其作为匹配代价。本文采用5×5的窗口对图像进行Census变换。任一像素点(u, v)的Census变换通过衡量它与周边像素的亮度差异得到, 过程如下:

$ Census\left( {u, v} \right) = \mathop \otimes \limits_{\left( {m, n} \right) \in N\left( {u, v} \right)} \varepsilon \left( {I\left( {m, n} \right), I\left( {u, v} \right)} \right) $

(2)

$ \varepsilon \left( {a, b} \right) = \left\{ \begin{array}{l} 1, \;\;\;b > a\\ 0, \;\;\;b \le a \end{array} \right. $

(3)

通过异或操作比较双目图像中2个像素的二进制串, 从而生成汉明距离。对于5×5的窗口, 汉明距离为0代表 2个像素的相似度最高, 汉明距离为25代表其相似度最低。由此可以得到Census变换的代价计算公式:

$ \begin{array}{l} {C_{{\rm{CENSUS}}}}\left( {u, v, d} \right) = Ham\left( {Censu{s^{{\rm{Left}}}}\left( {u, v} \right), } \right.\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left. {Censu{s^{{\rm{Right}}}}\left( {u - d, v} \right)} \right) \end{array} $

(4)

文献[13]提到Census变换对于噪声和光照变换的鲁棒性高, 而对于重复纹理区域以及弱纹理区域的匹配效果较差。而AD变换的特性恰好能够和Census变换进行互补, 因此可以通过级联AD与Census组成AD-Census算法, 从而获得鲁棒性更高的初始像素代价, 具体如下:

$ \begin{array}{l} C_{{\rm{PIXEL}}}^0\left( {u, v, d} \right) = p\left( {{C_{{\rm{CENSUS}}}}\left( {u, v, d} \right), {\lambda _{{\rm{CENSUS}}}}} \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;p\left( {{C_{{\rm{AD}}}}\left( {u, v, d} \right), {\lambda _{{\rm{AD}}}}} \right) \end{array} $

(5)

其中, λ_CENSUS和λ_AD是融合系数, p代表代价和融合系数相乘。

1.2 超像素最小生成树

通过AD-Census方法计算得到的像素代价中包含噪声, 因此需要通过代价聚集步骤来降低匹配的模糊性和代价中的噪声。代价聚集方法基于相似的区域具有相似的视差这一特征, 传统的代价聚集方法都是针对像素代价计算进行的, 其复杂度依赖于像素数目。文献[15]引入超像素分割的思想, 将相似的像素组成超像素, 由于超像素数目远小于像素数目, 因此超像素代价聚集计算比像素代价聚集计算的速度更快。文献[15]通过像素代价构造超像素代价, 并重启随机游走算法对其进行迭代优化。随机游走过程需要进行多次迭代, 并且超像素构成的大型邻接稀疏矩阵每次都要参与运算, 因此, 算法的时间性能和空间复杂度都较差。本文算法基于超像素分割生成超像素最小生成树, 并通过树形滤波器进行代价聚集。在代价聚集的过程中, 只需要进行少量计算就可获得代价聚集结果。

采用超像素进行代价聚集是基于2个方面的考虑。首先, 超像素按照相似度对图像进行分割, 超像素代价C_SUPERPIXEL⁰(sup u, sup v, d)通过属于同一区域的像素代价C_PIXEL⁰(u, v, d)生成, 因此, 它的抗噪鲁棒性比像素代价C_PIXEL⁰(u, v, d)高。其次, 超像素的数量远小于像素的数量, 其代价聚集的时间大幅缩短, 同时也节约了内存。

本文采用SLIC算法^[16]进行超像素分割, 将一幅图像分割为若干小块, 且小块中像素的相似度很高, 超像素实质上代表一块图像区域。图 2所示为对一幅450像素×375像素的图像进行超像素分割后的效果, 该图被分割为200个超像素。

由图 2可以看出, 图像中450×375=168 750个像素被划分到200个超像素中, 传统的代价聚集方法需要在168 750个像素上进行D次, 现在只需在200个超像素上进行D次。所生成的超像素的颜色、亮度以及超像素代价如下:

$ \left\{ \begin{array}{l} Color\left( {\sup \;u, \sup \;v} \right) = \frac{{\sum\limits_{\left( {u, v} \right) \in \left( {\sup \;u, \sup \;v} \right)} {Color\left( {u, v} \right)} }}{{\sum\limits_{\left( {u, v} \right) \in \left( {\sup \;u, \sup \;v} \right)} 1 }}\\ Intensity\left( {\sup \;u, \sup \;v} \right) = \frac{{\sum\limits_{\left( {u, v} \right) \in \left( {\sup \;u, \sup \;v} \right)} {Intensity\left( {u, v} \right)} }}{{\sum\limits_{\left( {u, v} \right) \in \left( {\sup \;u, \sup \;v} \right)} 1 }}\\ C_{{\rm{SUPERPIXEL}}}^0\left( {\sup \;u, \sup \;v, d} \right) = \frac{{\sum\limits_{\left( {u, v} \right) \in \left( {\sup \;u, \sup \;v} \right)} {C_{{\rm{PIXEL}}}^0\left( {u, v, d} \right)} }}{{\sum\limits_{\left( {u, v} \right) \in \left( {\sup \;u, \sup \;v} \right)} 1 }} \end{array} \right. $

(6)

为了生成超像素最小生成树, 可以把超像素看作是图, 将超像素点看作图的一个节点, 相邻2个超像素构成边, 代表 2个超像素的相邻关系。边上的值为超像素之间的亮度差值, 差值越小, 超像素的相似度越高。其计算过程如下:

$ \Delta {I_{AB}} = Intensity\left( A \right) - Intensity\left( B \right) $

(7)

将亮度差值作为边的权重, 构造最小生成树, 如图 3所示。2个超像素在图中只有一条连通的路径, 该路径是连接这2个超像素的所有路径中边权重最小的, 代表这条路径中的超像素具有最好的相似度并且超像素间不易跨越边缘。利用该路径组成的超像素进行代价聚集, 聚集后的视差空间能够较好地保持边缘特性。

1.3 基于超像素最小生成树的代价聚集

文献[11]将整幅图像中的像素作为图的节点, 像素间为4邻域或8邻域, 构建最小生成树。文献[12]在局部区域建立多棵最小生成树。与文献[11-12]相比, 本文利用超像素最小生成树建立代价聚集时, 由于超像素数目远小于像素数目, 因此其速度较快。同时, 本文加入超像素作为匹配基础, 所以最终生成的像素代价C_PIXEL¹(u, v, d)由超像素代价C_SUPERPIXEL¹(sup u, sup v, d)和像素代价C_PIXEL⁰(u, v, d)组成。对生成的超像素最小生成树, 通过2次遍历最小生成树进行代价聚集。初始时需要从最小生成树的叶子节点, 依据超像素的孩子节点自底向上更新其代价值, 使超像素在代价聚集时受到其底端节点的影响。当第1次遍历到达最小生成树的根节点后, 进行自顶向下的代价更新, 从而增加父节点对子节点代价聚集的影响。图 4展示了基于超像素最小生成树的代价聚集过程。

在代价聚集时, 将超像素之间的高斯权重作为相邻超像素对当前超像素的贡献权重, 计算过程如下:

$ Gauss\left( {A, B} \right) = \exp \left( { - \frac{{Intensity\left( A \right) - Intensity\left( B \right)}}{{2sigm{a^2}}}} \right) $

(8)

其中, A、B代表 2个超像素, sigma代表方差, exp代表指数, Gauss(A, B)为超像素之间的高斯权重。

对于超像素A, 在其自底向上的代价聚集过程中, 超像素的代价更新公式如下:

$ \begin{array}{l} C_{{\rm{SUPERPIXEL}}}^ \uparrow \left( {A, d} \right) = C_{{\rm{SUPERPIXEL}}}^0\left( {A, d} \right) + \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{Q \in N\left( A \right)} {Gauss\left( {A, Q} \right)} \times C_{{\rm{SUPERPIXEL}}}^0\left( {Q, d} \right) \end{array} $

(9)

其中, N(A)表示超像素A的邻域。

在进行自顶向下的代价聚集之后, 超像素代价如下:

$ \begin{array}{l} C_{{\rm{SUPERPIXEL}}}^1\left( {A, d} \right) = Gauss\left( {\mathit{Pr}\left( A \right), A} \right) \times \\ \;\;\;\;\;\;\;\;\;C_{{\rm{SUPERPIXEL}}}^1\left( {\mathit{Pr}\left( A \right), d} \right) + C_{{\rm{SUPERPIXEL}}}^ \uparrow \left( {A, d} \right) \times \\ \;\;\;\;\;\;\;\;\;\left( {1 - Gaus{s^2}\left( {\mathit{Pr}\left( A \right), A} \right)} \right) \end{array} $

(10)

其中, Pr(A)代表超像素A的父节点。

在代价更新的过程中, 超像素节点都直接或间接对其他超像素节点的代价更新有影响, 由于其计算过程只需要进行少量的加、减、乘运算, 因此能高效地进行代价聚集。得到超像素代价C_SUPERPIXEL¹(sup u, sup v, d)之后, 利用式(11)将其与初始代价C_PIXEL⁰(u, v, d)进行融合, 最终得到像素代价C_PIXEL¹(u, v, d):

$ \begin{array}{*{20}{c}} {C_{{\rm{PIXEL}}}^1\left( {u, v, d} \right) = {\lambda _{{\rm{SUPERPIXEL}}}}C_{{\rm{SUPERPIXEL}}}^1\left( {\sup u, \sup v, d} \right) + }\\ {{\lambda _{{\rm{PIXEL}}}}C_{{\rm{PIXEL}}}^0\left( {u, v, d} \right)} \end{array} $

(11)

其中, (u, v)∈(sup u, sup v)。

利用winner take all策略^[7]对像素代价C_PIXEL¹(u, v, d)进行计算, 得到视差, 并采用文献[17]的视差后处理方法对视差求精。

2 实验结果与分析

为验证本文算法的优越性, 在Intel corei5-6400 2.7 GHz的CPU、内存8 GB的Windows平台下使用C++实现算法。由于本文算法在CPU端具有很好的并行性, 在实际编码过程中利用Intel TBB技术对算法进行加速, 其在求取分辨率为640像素×480像素, 视差等级为30的立体视觉对的视差时, 速度可达30 frame/s。实验选取Middlebury测试集中的Tsukuba、Venus、Teddy、Cones作为算法测试集, 将误匹配率作为测试指标。同时, 将本文算法的实验结果与ST算法^[12]、MST算法^[11]、ARW算法^[15]进行比较。为验证本文算法在实际场景中的处理效果及其时间优越性, 还对自然场景下拍摄的分辨率为640像素×480像素、最大视差为30的立体视觉对进行测试。

在利用Middlebury测试集进行评测时, 选取误差阈值为1个像素的非遮挡区域nonocc进行比较, 结果如表 1所示。由表 1可以看出, 在立体匹配时, 本文算法的误匹配率稍差于MST算法和ST算法。这是由于本文算法的代价聚集基于超像素进行, 而MST算法和ST算法则以像素为基础进行代价聚集。与ARW算法相比, 本文算法的误匹配率较优。这是因为本文算法利用树形滤波器对超像素进行代价聚集, 而ARW算法以随机游走方式进行代价聚集。同时, 本文算法包含良好的分割信息, 相较于ARW算法, 其保边性能更好, 因此评价系数的提升较为显著。

本文算法对于Tsukuba、Venus、Teddy、Cones测试集生成的视差伪彩图如图 5所示。

与Middlebury测试集的立体视觉对相比, 自然场景下拍摄的立体视觉对的处理难度更大。本文算法对于自然场景下拍摄的图片也表现出较好的立体匹配效果, 如图 6所示。

基于本文算法在自然场景下的优越性能, 结合合理的相机选型, 可实现精确物体测距、背景虚化等应用。图 7展示了本文算法用于物体测距和测尺寸的效果。得到的测量结果为:高H=1 747.66 mm, 与相机的距离D=1 503.77 mm, 与实际值(H=1 745.00 mm, D=1 548.00 mm)较为接近。

本文算法在保证处理效果的前提下, 使用TBB技术对其进行加速。图 8给出5种算法处理立体视觉对的耗时情况, 其中, FA是未经过加速的本文算法, FA-TBB是采用TBB技术加速后的本文算法。

由图 8可以看出, ARW算法由于使用随机游走进行迭代求解, 其速度最慢。ST算法、MST算法的速度可达2 frame/s。而本文算法在未经优化的情况下处理速度为13 frame/s, 经过TBB加速后可达30 frame/s, 其能在保证处理效果的前提下, 提高速度。

3 结束语

本文提出一种改进的代价聚集快速立体匹配算法。通过AD-Census进行初始像素代价计算, 并利用SLIC进行超像素分割, 构建超像素初始代价。以超像素之间的亮度差异为权重生成超像素最小生成树, 通过树形滤波器进行超像素代价聚集, 再以一定的权重将其与初始像素代价融合。采用winner take all进行视差后处理, 生成视差图。实验结果表明, 该算法能够取得较好的立体匹配效果, 大幅减小时间代价。下一步将考虑用递归非全局保持滤波器改进超像素代价聚集过程, 加快算法速度。