开放科学（资源服务）标志码（OSID）：

0 概述

立体匹配是从双目或多目图像中寻找同名点并根据其视差计算场景深度信息的过程，是近年来计算机视觉领域的研究热点之一。现场可编程门阵列（Field Programmable Gate Array，FPGA）具有成本低、开发周期短、并行计算的优点，是嵌入式应用的设计平台。基于FPGA的立体匹配技术可以实现实时获取目标场景的深度信息，因此被广泛应用于智能机器人、无人驾驶、目标跟踪、三维重建等领域^[1-2]。立体匹配算法主要分为局部^[3]、全局^[4]、半全局^[5-6]、基于深度学习^[7]算法。全局和基于深度学习的算法精度高，局部和半全局算法实时性强。半全局立体匹配（Semi-Global stereo Matching，SGM）算法是全局算法的改进，其将二维图像的优化问题转化为多条路径的一维优化问题，在保留算法精度的基础上减小了计算复杂度，算法并行度高，适用于资源占用小、实时性要求高的嵌入式系统。

SCHARSTEIN等^[8]将立体匹配算法分为匹配代价计算、代价聚合、视差计算与优化、视差校正4个阶段，其中匹配代价计算通过相似性函数计算左右两点的代价值，是立体匹配算法的核心步骤。传统匹配代价计算方法有灰度差值平方和（Sum of Squared Differences，SSD）^[9]、零均值绝对误差和（Zero Sum of Absolute Differences，ZSAD）、Census变换（Census Transform，CT）^[10]等。Census变换对图像局部区域进行编码，具有结构简单、相对次序性良好的优点，在立体匹配算法中应用广泛，但该算法存在过度依赖中心点像素值及对噪声敏感的缺点。文献[11]利用十字交叉窗口内各像素灰度值的平均值代替中心像素点，增强了算法鲁棒性；文献[12]利用Census变换融合其他相似性度量方法计算匹配代价，解决了匹配窗口选择难的问题；文献[13]将灰度绝对差值（Absolute Differences，AD）与Census变换结合计算匹配代价，改善了相似纹理区域的误匹配问题。然而，Census变换对无、弱纹理区域匹配效果欠佳的问题仍未得到有效解决。左右一致性检验（Left-Right Check，LRC）是利用相同点视差相同的原理来实现对遮挡点的检测，是视差校正常用算法之一，但该算法需要同时获取左右两幅图像的视差图，占用资源量大，不适用于小型嵌入式系统中。

本文提出一种改进的基于FPGA的实时半全局立体匹配算法，以提高实时立体匹配精度。在匹配代价计算阶段，利用带权重的4方向梯度绝对值差（Absolute Differences of Gradient，ADG）和改进的Tanimoto距离相结合的算法，以提高弱纹理和边缘区域的匹配精度；在代价聚合阶段，采用4路径并行结构的SGM算法；在视差选择阶段，采用赢家通吃策略（Winner-Takes-All，WTA）；在视差校正阶段，采用阈值检测（Threshold Detection，TD）算法代替LRC算法，以减少硬件资源需求。

1 算法描述 1.1 匹配代价计算

传统基于FPGA平台的立体匹配算法多利用Census变换^[11]作为匹配代价进行计算，根据周围像素值与中心像素值的大小关系获得比特串，利用Hamming距离计算匹配代价。Census变换公式见式（1）。

$ {I}_{\mathrm{C}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{u}\mathrm{s}}\left(p\right)=\underset{q\in D}{\otimes }\xi \left[I\right(p), I(q\left)\right] $

(1)

其中：$ {I}_{\mathrm{C}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{u}\mathrm{s}}\left(p\right) $为Census变换结果；$ D $为$ I\left(p\right) $点周围邻域；$ I\left(p\right) $为中心像素灰度值；$ I\left(q\right) $为$ I\left(p\right) $周围像素点灰度值；$ \otimes $表示按位连接。当$ I\left(p\right) > I\left(q\right) $时，$ \xi \left[I\right(p), I(q\left)\right] $为1，当$ I\left(p\right) < I\left(q\right) $时为0。Hamming距离计算公式见式（2）。

$ {D}_{\mathrm{H}}(a, b)=\frac{1}{N}\sum\limits _{i=1}^{N}\left({a}_{i} \oplus {b}_{i}\right) $

(2)

其中：$ {D}_{\mathrm{H}}(a, b) $为Hamming距离计算结果；$ N $为窗口大小；$ {a}_{i} $和$ {b}_{i} $为左右图经过Census变换获得的比特串；$ \oplus $为按位异或操作。

Census算法对灰度变化范围大的区域匹配效果较好，但对灰度变化小的弱纹理区域匹配效果较差，且对中心点像素值依赖性强。目前对此改进的方法主要有更换中心像素点^{[12, 15]}、多匹配代价融合^{[13, 16]}、选用自适应窗口^[17-18]等，算法对中心点的依赖性得到改善，但仍存在对弱纹理、边缘区域的像素点区分度低、误匹配率高的缺点。

本文引入Tanimoto距离替代传统Hamming距离作为匹配代价计算方法，Tanimoto距离计算公式见式（3）。

$ {D}_{\mathrm{T}}(a, b)=\left\{\begin{array}{l}1\text{，}a=b=0\\ 1-\frac{\sum a\bigcap b}{\sum a\bigcup b}\text{，}\mathrm{其}\mathrm{他}\end{array}\right. $

(3)

其中：$ {D}_{\mathrm{T}}(a, b) $为Tanimoto距离；a和b为像素点比特串。像素点p在视差为d时的Tanimoto距离记为$ {D}_{\mathrm{T}}(p, d) $。

改进Tanimoto算法附加权重如图 1所示。以3×3窗口为例，Tanimoto距离与Hamming距离的比较结果见表 1，经Census变换获得的比特串位数为8位，为方便对比，表 1中将Hamming距离除以比特位数进行计算。

Tanimoto距离与Hamming距离的区别在于，Tanimoto距离在分母中去掉了对两个比特位同时为零的计数，因此当比特串位变化很小时，Tanimoto距离具有更高的区分度，可有效减少Census变换在弱纹理区域的误匹配率，但这样同时也降低了当比特串位变化很大时（$ \sum a\bigcap b=0 $）的区分度，影响了匹配效果。针对这一问题，本文对Tanimoto距离进行改进，改进后的Tanimoto距离计算公式见式（4）。

$ {D}_{\mathrm{W}\mathrm{T}}(a, b)=\left\{\begin{array}{l}1\text{，}a=b=0\\ {W}_{i}\times \left(\frac{\sum a\bigcup b}{n}\right), \sum a\bigcup b=0\\ 1-{W}_{i}\times \left(\frac{\sum a\bigcap b}{\sum a\bigcup b}\right)\text{，}\mathrm{其}\mathrm{他}\end{array}\right. $

(4)

算法先按照图 1（a）的加权模板为特定位增加权重，i=1，2，W₁=1，W₂=2，再对$ \sum a\bigcap b=0 $的情况进行处理以增大在比特串位变化很大时的区分度。在利用式（4）计算的过程中，对图中灰色像素部分乘以权重2，相当于特定位计数两次，其他位保持不变。由图 1（b）可知，经过加权后的比特位权重由“11111111”变为“12122121”，n由8变为12。加权重的改进Tanimoto距离计算结果见表 1，可以看出，改进算法进一步细化了匹配代价值分布，增大了区分度，同时保持了弱纹理区域和纹理充足区域的匹配效果；同时，为有效解决Census变换引起的算法依赖中心点和对噪声敏感的问题，研究者引入梯度绝对值差（ADG）。LI所提的改进ADG算法^[19]由于根据窗口内0°和90°两方向的像素梯度绝对值差计算匹配代价，因此仅对这两个方向的图像边缘处理效果较好，但对其他方向的边缘不敏感，导致匹配效果欠佳，为解决上述问题，考虑到图像边缘多为45°和135°两个方向，本文提出改进的4方向ADG算法，在0°和90°基础上，添加45°和135°两个方向的梯度并增加权重进行计算，进一步提高算法在边缘处的匹配效果，且3×3小窗口算法对中心像素点的依赖性较小，对噪声具有鲁棒性。本文算法计算公式见式（5）。

$ \begin{array}{l}G(p, d)={W}_{i}\times \sum\limits _{i\in \{0°, 45°, 90°, 135°\}}\left(\left|{\nabla }_{i}\right({I}_{l}\left(p\right))-{\nabla }_{i}({I}_{r}(p, d)\left)\right|\right)\\ \end{array} $

(5)

其中：$ G(p, d) $为梯度绝对值差；$ \left|{\nabla }_{i}\right({I}_{l}\left(p\right))-{\nabla }_{i}({I}_{r}(p, d)\left)\right| $为4个方向的梯度绝对值差；$ {W}_{i} $为方向权重。考虑到算法的实时性和占用资源情况，将45°和135°的计算结果左移一位以增加权重，增加了匹配点在边缘区域的区分度。最后将相同像素点的ADG和Tanimoto距离的乘积作为该点的初始匹配代价值，计算式见式（6）。

$ {C}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}(p, d)=G(p, d)\times {D}_{\mathrm{W}\mathrm{T}}(p, d) $

(6)

1.2 SGM代价聚合

代价聚合通过对相邻像素的代价值进行聚合以及施加惩罚，以达到避免选择错误同名点的效果，代价聚合能量函数定义见式（7）。

$ \begin{array}{l} E\left(D\right)=\sum\limits _{p}C(p, {D}_{p})+\sum\limits _{q\in {N}_{p}}{P}_{1}T\left[\right|{D}_{p}-{D}_{q}|=1]+\\ \ \ \ \ \ \ \ \ \ \ \ \ \sum\limits _{q\in {N}_{p}}{P}_{2}T\left[\right|{D}_{p}-{D}_{q}| > 1] \end{array} $

(7)

其中：$ E\left(D\right) $全局能量函数；$ p $是目标像素点；$ q $为$ p $邻域中一点；$ {D}_{p} $和$ {D}_{q} $为两点视差；$ C(p, {D}_{p}) $为视差图$ D $下所有像素点的匹配代价；$ {P}_{1} $和$ {P}_{2} $分别为平滑约束惩罚因子和边缘约束惩罚因子。当相邻视差等于1$ \left(\right[|{D}_{p}-{D}_{q}|=1\left]\right) $时添加$ {P}_{1} $惩罚因子；当相邻视差大于1$ \left(\right[|{D}_{p}-{D}_{q}| > 1\left]\right) $时添加$ {P}_{2} $惩罚因子，且满足$ {P}_{2} \gg {P}_{1} $。

SGM算法^[20]是全局算法的改进，其通过平等的聚合来自8至16条路径的匹配代价，将二维图像优化问题转变为多路径一维优化问题。当路径为$ r $、视差为$ d $时，可得到像素点$ p $的代价聚合函数，计算公式见式（8）。

$ \begin{array}{l} {L}_{r}(p, d)={C}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}(p, d)+\mathrm{m}\mathrm{i}\mathrm{n}\left\{\begin{array}{c}{L}_{r}(p-r, d)\mathrm{ }, \\ {L}_{r}(p-r, d\pm 1)+{p}_{1}, \\ \underset{k}{\mathrm{m}\mathrm{i}\mathrm{n}}\ {L}_{r}(p-r, k)+{p}_{2}\end{array}\right\}-\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \underset{k}{\mathrm{m}\mathrm{i}\mathrm{n}}\ {L}_{r}(p-r, k) \end{array}$

(8)

其中：第1项$ {C}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}(p, d) $为初始匹配代价；第2项是路径$ r $上的前一个像素点$ p-r $的最小匹配代价；第3项是防止代价聚合值过大而减去的固定值。最后将像素点$ p $在各个路径上的聚合值相加即为该点在经过代价聚合后的匹配代价值，计算公式见式（9）。

$ E(p, d)=\sum\limits _{r}{L}_{r}(p, d) $

(9)

1.3 视差选择

本文选择传统立体匹配算法均采用的WTA算法进行视差选择，得到像素点的初始视差值，计算公式见式（10）。

$ {d}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}\left(p\right)=\underset{d\in [0, {d}_{\mathrm{m}\mathrm{a}\mathrm{x}}]}{\mathrm{a}\mathrm{r}\mathrm{g}\ \mathrm{m}\mathrm{i}\mathrm{n}}\ E(p, d) $

(10)

其中：$ {d}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}\left(p\right) $为初始视差值；$ {d}_{\mathrm{m}\mathrm{a}\mathrm{x}} $为最大视差范围；$ E(p, d) $为经过代价聚合后的代价值，最小代价值所在位置即为该点的视差值，$ {d}_{\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}}\left(p\right)\in [0, {d}_{\mathrm{m}\mathrm{a}\mathrm{x}}] $。

1.4 视差校正

视差校正又称为视差后处理，旨在对初始视差值中的误匹配点进行修正，传统立体匹配后处理方法主要有左右一致性检验（LRC）、中值滤波等。LRC算法通过检查左右两张视差图中同名点视差的差值来判断是否为遮挡点，算法准确有效，但该算法在FPGA上实现时，需要同时获得左右两张视差图，这将比获取一张视差图的算法多占用一倍的硬件资源，算法运算效率低。

为了解决上述问题，笔者通过对WTA获得的初始视差值分析发现，遮挡点的代价值均大于某阈值，而正确匹配点的代价值均小于该阈值，这是由于遮挡点在参考图中找不到最合适同名点，通过WTA方法只能找到次合适同名点，故其选择的最小代价值偏大。因此，提出通过设定阈值的方法来判断是否为遮挡点，计算公式见式（11）。

$ {d}_{p}=\left\{\begin{array}{l}{d}_{p}\text{，}d\left(p\right)\le \mathrm{T}\mathrm{h}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}\mathrm{o}\mathrm{l}\mathrm{d}\\ 0\text{，}\mathrm{其}\mathrm{他}\end{array}\right. $

(11)

若点$ d\left(p\right) $视差值大于该阈值，则将视差值置0，视为遮挡点，否则保持不变。这样就只需一张视差图便可基本达到和LRC一样的结果，算法占用资源少，适合FPGA实现。

完成遮挡检测步骤后需对遮挡点进行填充，遮挡点由前景物体遮挡背景造成，应填充背景视差值，遮挡点填充算法的计算公式见式（12）。

$ {d}_{p}=\left\{\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}({D}_{l}, {D}_{r})\text{，}p\ \mathrm{i}\mathrm{s}\ \mathrm{i}\mathrm{n}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{d}\\ {d}_{p}\text{，}\mathrm{其}\mathrm{他}\end{array}\right. $

(12)

其中：$ p $为遮挡点；$ {D}_{l} $为从该点开始向左第一个非遮挡点视差值；$ {D}_{r} $为从该点开始向右第一个非遮挡点视差值，选取较小的视差值对$ p $点进行填充。完成遮挡点检测和填充后的视差图会产生条纹效应，利用中值滤波对图像中其余误匹配点和条纹进行填充和改善。

2 FPGA算法实现

将算法模块封装成IP核，目标图和参考图以数据流的方式同时流入算法模块，模块与模块之间利用为乒乓缓存结构连接，算法整体硬件结构如图 2所示。

2.1 匹配代价计算模块

匹配代价模块分为Tanimoto模块和ADG模块，两模块并行运算，运算结束后得出初始匹配代价。图 3为Tanimoto算法结构。数据流首先流入FIFO行缓存，缓存足够的像素值后移入窗口缓存，进行Census变换获得比特串，按照式（4）将数据按位进行与或逻辑运算，计数后送入除法模块。经检验Census窗口过大或过小均会导致误匹配率增加，其中窗口为7×7时效果最佳，对应的Tanimoto加权模板见图 1（b）。除法模块由相减移位操作组成，被除数和除数的位宽为$ \left[\mathrm{l}\mathrm{b}\right({7}^{2}-1\left)\right]=6 $位，将被除数位宽增大到2倍，高6位为0，与除数进行相减移位操作，除法计算需迭代6次，所得结果位宽为12位，高6位为余数，低6位为商，像素与像素之间并行计算以减少延迟，满足Pipeline流水线设计要求，除法模块结构如图 3所示。

图 4为ADG算法结构图。将缓存窗口中的数据同时进行卷积，所得结果进行相加运算，匹配代价计算分别由Tanimoto模块和ADG模块组成，两模块虽并行计算，但所需时钟周期不同，Tanimoto模块由于除法模块的存在比ADG相加模块多消耗$ \left[\mathrm{l}\mathrm{b}\right({7}^{2}-1\left)\right]-1=5 $个时钟周期，因此在ADG模块中增加FIFO行缓存即可同步两者输出。初始匹配代价计算结构如图 5所示，所得结果以数据流形式流入下一模块。

2.2 4路径代价聚合模块

传统8方向代价聚合算法通过聚合来自8个路径的匹配代价值计算出最终代价值，但在FPGA上实现传统8方向的聚合算法将缓存大量像素值，因为图中浅灰色的4条路径不符合FPGA流水线的设计思想。图 6为4方向SGM代价聚合算法结构图。为了控制算法消耗资源量，保证算法运行效率，采用图 6中深灰色4条路径作为算法的代价聚合路径。在行缓存内有足够数据后送入4个并行计算的代价聚合模块，按式（8）计算后以数据流形式输出。

2.3 视差选择模块

图 7为WTA算法的并行化实现结构图，在最大视差范围64情况下，将整个结构分为$ \left[\mathrm{l}\mathrm{b}\ 64\right]=6 $级，共采用63个比较器单元。模块输入为匹配代价值，输出是将最小代价值所在位置作为视差值，由于后接的截断阈值检测（TD）模块须同时使用最小代价值和对应视差值，故将两者同时输出。遮挡点检测算法如图 8所示，模块由一个比较器和一个选择器组成，设置合适的截断阈值并接收WTA模块传来的最小代价值和对应视差值。若最小代价值大于设定阈值，则判定该点为遮挡点且对应视差值无效，将该点视差值置零并输出；若最小代价值小于设定阈值，则判定该点为正常点，输出视差值。

2.4 视差校正模块

视差校正模块分为无效点填充模块和中值滤波模块，其中无效点填充模块是对视差图中的异常点和遮挡点进行填充，填充分为向左填充和向右填充，分别对应两个寄存器$ {D}_{\mathrm{l}} $和$ {D}_{\mathrm{r}} $，向右填充部分首先将数据流存入大小为$ 1\times {d}_{\mathrm{m}\mathrm{a}\mathrm{x}} $的行缓存中，若判定当前像素为无效值，则取行缓存中第一个有效值存入$ {D}_{\mathrm{r}} $；向左填充部分等待数据流入并将第一个有效值存入$ {D}_{\mathrm{l}} $，$ {D}_{\mathrm{l}} $和$ {D}_{\mathrm{r}} $取最小值作为该无效点的视差值并输出。

图 9为中值滤波算法结构，选择3×3窗口内所有点的中值代替窗口内所有点的值，可以有效消除视差图中的异常点和条纹效应。算法首先需对窗口内的值进行排序，然后计算得出中值，为提高排序效率，算法分为两步，首先分别计算3行值的最大、最小和中值；然后将获得的3个值排序，获得的中值即为所有点的中值。

3 实验结果与分析

本文利用Xilinx的高级综合工具（High Level Synthesis，HLS）进行模块的设计与实现，通过SDK软件进行软硬件协同设计并生成比特流文件导入XC7Z035开发板中，采用Middleburry数据集中1/4分辨率的4幅图像Tsukuba、Venus、Teddy和Cones对算法效果进行验证，最大视差分别为16、20、64、60，将测试图像存入SD卡，经由开发板读取、运算并由HDMI显示。

3.1 匹配精度

图 10为算法测试结果，从中可以看出，算法在弱纹理和深度不连续区域匹配效果有所改善，但在无纹理区域的背景部分仍存在误匹配的问题，这是因为为了保证匹配速率，算法采用7×7窗口进行匹配代价计算，遇到大面积相同像素值区域时就无法进行有效区分，导致误匹配。增大匹配窗口会导致计算量增大，但误匹配率效果改善不明显。

本文算法与其他算法误匹配率比较如表 2所示，误匹配率计算表达式见式（13）。

$ \left\{\begin{array}{l}{N}_{\mathrm{e}\mathrm{r}\mathrm{r}}(x, y)=\left\{\begin{array}{l}1, \left|{d}_{\mathrm{C}}\right(x, y)-{d}_{\mathrm{T}}(x, y\left)\right| > {\delta }_{\mathrm{d}}\\ 0, \mathrm{其}\mathrm{他}\end{array}\right.\\ \mathrm{e}\mathrm{r}\mathrm{r}=\frac{1}{N}\sum\limits _{(x, y)\in \mathrm{I}}{N}_{\mathrm{e}\mathrm{r}\mathrm{r}}(x, y)\end{array}\right. $

(13)

其中：err为误匹配率；$ N $为图像总像素个数；$ {d}_{\mathrm{C}} $为算法得到的视差值；$ {d}_{\mathrm{T}} $为真实视差值，当两者差值大于误差阈值$ {\delta }_{\mathrm{d}} $时，判定为误匹配点，$ {N}_{\mathrm{e}\mathrm{r}\mathrm{r}}(x, y)=1 $，否则为0，$ {\delta }_{d}\in \left[\mathrm{0.5, 4}\right] $，本文取1。不同算法的误匹配如表 2所示，其中，Nonocc为非遮挡区域误匹配率，All为全区域误匹配率，Disc为深度不连续区域误匹配率。由表 2可知，通过计算所有区域下各个测试集图像的误匹配率的平均值，得出算法的平均误匹配率为7.52%，算法匹配精度低于文献[11]的基于改进Census变换和动态规划的局部算法，略低于文献[19]的TAD SGM算法，普遍优于$ {\mathrm{R}}^{3} $SGM算法^[21]和传统SGM算法^[22]。

综上所述，本文所提算法在识别精度方面较传统基于FPGA算法有明显提升，优于现有基于FPGA的改进SGM算法，算法对弱纹理和深度不连续区域的误匹配情况也有所改善。

3.2 匹配速率

表 3为算法速率及资源占用情况，对比算法的误差阈值均为1，算法在最大视差为64个像素，图像大小为450×375像素且时钟频率为100 MHz时，可以达到98 frame/s，占用LUT为88K，每秒处理百万个视差数（Million Disparity Estimations per Second，MDE/s）为1 058。由表 3可知，本文算法在FPS和MDE/s上略逊于文献[21-22]算法，这是因为算法含有除法器模块，处理一个像素所用时间多于两种算法。本文算法在得到更高匹配精度的前提下仍能满足实时性要求，优于文献[23-24]算法。

4 结束语

本文提出一种新型实时半全局立体匹配算法。利用改进的Tanimoto距离代替Hamming距离并与带权重4方向的改进ADG算法相结合作为初始匹配代价，降低针对弱纹理区域和边缘区域的误匹配率。同时利用4路径的半全局代价聚合方法代替原8路径方法，在保证算法精度前提下提高了算法运行效率。此外，采用截断阈值检测算法代替左右一致性检验，只需一张视差图便可完成检测，减少了资源占用率。本文算法在Middleburry数据集上的平均误匹配率为7.52%，在FPGA上实现时吞吐率为98 frame/s，在保证实时性的前提下可使基于FPGA的双目立体匹配系统匹配精度得到提高。但由于本文算法存在除法模块，处理一个像素点需多个时钟周期，在实时性方面稍逊于其他基于FPGA的算法，并且需要保证实时性而选择小窗口，在处理大片无纹理区域时存在误匹配现象。后续将研究如何在小窗口下提高算法对于无纹理区域的匹配精度，并进一步提高算法的实时性。