基于SIFT描述子的自适应聚合权重立体匹配算法

何 凯，王晓文，葛云峰

（天津大学电子信息工程学院，天津 300072）

基于SIFT描述子的自适应聚合权重立体匹配算法

何 凯，王晓文，葛云峰

（天津大学电子信息工程学院，天津 300072）

针对传统局部立体匹配算法在深度不连续区域和低纹理区域匹配精度不高的问题，提出了一种基于SIFT描述子的自适应聚合权重立体匹配算法.算法首先采用梯度域的幅值和相位获取初始匹配代价；然后利用相似性区域判决准则获得各个中心点的自适应矩形聚合窗口，并利用各点SIFT描述子的L1范数进行自适应聚合权重计算.仿真实验结果表明，该算法能够有效地提高低纹理区域和深度不连续区域的立体匹配精度，获得较高精度的视差图.

立体匹配；梯度；聚合权重；SIFT描述子

立体匹配根据从同一场景获得的两幅或者多幅图像寻找相应的匹配点，利用匹配算法计算图像各点的深度信息，从而达到三维重建的目的.目前，立体匹配技术已经广泛应用于各个领域［1］，如视频监控、3D跟踪、机器人控制等，并受到了广泛的关注.

近年来，各国学者在立体匹配领域进行了深入的研究，并提出了许多算法，主要可分为2大类：基于局部约束的立体匹配算法和基于全局约束的立体匹配算法.其中，基于全局约束的立体匹配算法在本质上属于优化算法，它是将立体匹配问题转化为寻找全局能量函数的最优化问题，其代表算法主要有图割算法［2］、置信度传播算法［3］和协同优化算法［4］等.全局算法能够获得较低的总误匹配率［5］，但算法复杂度较高，不利于在实际工程中使用.

基于局部约束的立体匹配算法主要是利用匹配点周围的局部信息进行计算，由于其涉及到的信息量较少，匹配时间较短，因此受到了广泛关注，其代表算法主要有SAD、SSD、NCC［6］等.近年来，部分学者提出了一些改进算法，如De-Maeztu等［7］提出利用窗口内像素的颜色信息来自适应计算窗口匹配权值，在一定程度上改善了匹配精度.Veksler［8］采用一种自适应窗口大小、形状和权值的方法进行匹配，提高了匹配精度，但参数过多，自适应性较差.Einecke等［9］提出了一种基于标准互相关函数进行匹配代价聚合的方法，在提高匹配精度的同时，降低了时间冗余度.Kang等［10］采用了多窗口技术来对兴趣点进行匹配，提高了匹配精度，但在最优窗口的选取上耗时较多.Zhang等［11］提出了一种基于正交积分图像的局部立体匹配算法，能够实现不规则窗口匹配代价聚合的快速计算.Mattoccia等［12］引入了基于联合双边滤波的自适应权值方法，降低了算法的计算复杂度，并提高了匹配代价聚合的可靠性.此外，岳斌等［13］根据Panum融合原理，提出了一种立体视差调整的快速估计算法，能快速准确地计算视差调整范围，消除了影响立体感的双眼复视.Joglekar等［14］提出了一种基于概率神经网络的特征匹配算法，利用SIFT特征描述子实现匹配过程中兴趣点的自动检测，该算法收敛速度快，对二维旋转和尺度变换具有较高的鲁棒性.

上述算法在高纹理区域均能获得比较理想的匹配效果，但是在低纹理区域、遮挡区域以及物体边界等深度不连续区域，其匹配效果往往不够理想.本文尝试利用相似性区域判决准则获得各个中心点的自适应矩形聚合窗口，利用图像各点的SIFT特征描述子的L1范数计算自适应权重，以提高低纹理区域和深度不连续区域的立体匹配效果.

1　传统匹配代价计算

传统的立体匹配算法是利用像素点的颜色差值，或基于census变换［15］、rank变换［16］的方法来计算匹配代价，容易受到噪声和局部光照变化的影响.鉴于图像梯度域对噪声和局部光照变化具有较强的鲁棒性［17］，本文采用梯度域的梯度幅值和相位来计算匹配代价，以提高算法的鲁棒性.基于梯度域的联合匹配代价函数定义为

式中：ξ、η为平衡因子，且η+ξ=1，本文ξ取为0.15；μ取为10；Cc（x, y, d）为基于图像像素大小的非相似性测度；Cg（x, y, d）、Cp（x, y, d）分别为基于图像梯度域的幅值和相位的非相似性测度；Tc、Tg和Tp分别为Cc（x, y, d）、Cg（x, y, d）和Cp（x, y, d）的截断阈值.

Cc（x, y, d）、Cg（x, y, d）和Cp（x, y, d）的计算公式为

2　本文算法

2.1自适应聚合窗口计算

固定窗口的局部算法效果与窗口大小有关，窗口选择过小，则匹配代价区分度过低，在低纹理区域容易出现误匹配；反之，若窗口选择过大，在深度不连续区域又会出现较高的误匹配.为解决上述问题，本文提出利用相似性区域判决准则来自适应获得各个中心点的矩形聚合窗口，以获得最佳的聚合效果.

本文用相互正交的水平和垂直扫描线进行分割，以得到某个中心点像素p（x, y）的聚合窗口win（p）.若考虑中心点像素周围所有方向上像素对其聚合的影响，得到的自适应窗口大多为非规则的窗口，致使计算复杂度增加.为了兼顾匹配代价聚合的精度与复杂度，自适应窗口选择矩形窗口.本文根据色彩视差一致性假设提出2个判决准则，以确定某中心点p（x, y）的相似性区域，进而获得聚合窗口左、右、上、下4个端点P1、P2、P3、P4的位置（见图1）.

图1　自适应聚合窗口计算过程示意Fig.1Frame of calculation process of adaptive supportwindow

以点P1的求解过程为例，首先计算中心点左侧某点q（x1, y1）与中心点p（x,y）的色彩差异，即

式中：λ为权衡因子，本文设为0.8；Ik（p）、Ik（q）分别为中心点及其左侧某点在RGB空间中的像素值；∇xI（p）、∇xI（q）分别为p和q像素点在x方向的梯度.式（5）中第1项用于限定q与p的像素差异性，第2项用于限定q与p的梯度差异性.

本文判定准则可概括如下.

（1）判定点q是否满足Dc（p, q）＜ψ.其中ψ为阈值，本文设为25.

（2）判定点q是否满足Ds（p, q）＜ξ.其中，Ds（p, q）=|p-q|表示p与q之间的空间距离，ξ为q的最大搜索范围，本文设为20，防止出现过平滑现象.

选择满足上述2个判定准则的最左q点作为P1的位置.同理，分别选择满足上述2个准则的最右点、最上点和最下点作为P2、P3和P4的位置.值得注意的是，当计算P3和P4的位置时，式（5）中的∇xI（p）、∇xI（q）应改为点p和q在y方向的梯度∇yI（p）、∇yI（q）.

2.2SIFT描述子的计算

SIFT特征描述子是利用特征点邻域图像窗口内梯度方向的统计直方图来构造特征描述向量，该特征描述子对图像的仿射变换具有较强的鲁棒性，为此，本文提出基于SIFT特征描述子来计算自适应聚合权重.具体作法如下.

以某个像素点（x, y）为中心选取8×8的矩形窗口，计算窗口内每个像素点梯度的幅值和方向，即

式中：g（x, y）、θ（x, y）分别为点（x, y）处梯度的幅值和方向；I（x, y）为点（x, y）处像素值的大小.

对窗口内每个像素点梯度的幅值利用标准差为1的高斯函数进行加权，其目的是提高中心像素点的权重.在每个4×4的子窗口将图像梯度方向直方图量化到8个平均分配的方向，即将像素点的梯度投影到离其最近的一个方向上，归一化后生成每个像素点的32维SIFT描述子.

2.3基于SIFT描述子的自适应权重计算

首先提取待匹配图像中每个像素点的SIFT特征描述子，利用其视觉和光照不变性的特点，实现各像素之间相似性测度的计算.设win（p）为以点p（x, y）为中心点的聚合窗口，则该聚合窗口内的任意一点pm（xm,ym）的自适应聚合权重系数可以通过计算pm与p的SIFT特征描述子的相似性来求解，即

计算获得像素点p（x, y）的自适应窗口及聚合权重后，本文利用权重聚合的方式实现像素点p（x, y）匹配代价的优化，定义如下：

式中：pij为聚合窗口内的某个像素点pij（i, j）；wij为利用SIFT描述子计算的某个像素点pij的自适应权重；win（p）为中心点像素p（x, y）基于相似性区域判决准则获得的自适应窗口.

2.4本文算法步骤

（1） 首先利用式（1）计算各点的匹配代价；

（2） 利用相似性区域判决准则获得各个中心点的自适应矩形聚合窗口；

（3） 计算图像中每个像素点的32维SIFT特征描述子；

（4） 利用式（8）～（9）计算窗口内各像素点的聚合权重，并完成匹配代价的聚合；

（5） 采用WTA策略选取最优视差图，然后采取左右一致性检测（left right consistency，LRC）策略进行遮挡检测，利用背景填充法对检测出的误匹配点进行填充，得到最终的视差图.

3　仿真实验结果及对比分析

本文选取美国大学Middlebury大学计算机视觉研究中心提供的立体图像数据库：http： //vision.middlebury.edu/stereo作为测试图片，该图像库涵盖了容易引起误匹配的各种情况，包含低纹理区域、深度不连续区域、遮挡区域等，以验证本文方法的有效性.

图2分别为采用RTCensus 算法［18］、SNCC算法［9］、VariableCross算法［11］、HistoAggr算法［19］以及本文算法的实验结果，这几种算法均采用LRC策略进行遮挡检测，利用背景填充法对误匹配点进行填充.本实验中采用的主要参数的参考值分别设为

图2　不同方法获得的视差图效果对比Fig.2 Comparison of disparity maps with different methods

表1是以上几种算法的误匹配率实验数据对比，误差阈值取为1.其中“Nonocc”、“All”、“Disc”分别表示非遮挡区域误匹配像素比、总体误匹配像素比和深度不连续区域误匹配像素比.

表1　不同算法的误匹配率比较Tab.1 Comparison of error rate of different algorithms %,

图2（a）～图2（g）从左到右的4幅图像依次是Tsukuba、Venus、Teddy和Cones.从图中可以看出：与几种传统方法相比，本文算法在低纹理区域能够获得更好的匹配效果，如Tsukuba图像的背景墙壁和书架区域，Teddy图像的画布、屋顶部分以及Cones图像的椎体区域等.

从表1中可以看出：与几种传统立体匹配算法相比，对于4幅图像，本文算法的整体误匹配率均较低，尤其是在深度不连续区域的误匹配率，除了Tsukuba图像略高于VariableCross算法以外，其误匹配率都是最低的；在非遮挡区域，本文算法除了Tsukuba图像和Venus图像略高于VariableCross算法以外，也都获得了最低的误匹配率.

从表1和图2中可以看出，RTCensus算法在深度不连续区域处理效果较差，而本文算法可以有效提高深度不连续区域的匹配精度，取得了良好的处理效果.

4　结　语

本文提出了一种基于SIFT描述子的自适应权重立体匹配算法，利用相似性区域判决准则获得各个中心点的自适应矩形聚合窗口，利用SIFT描述子来计算窗口内各像素点的聚合权重.仿真实验结果表明，本文算法在低纹理和深度不连续区域都能获得更准确的匹配效果.

［1］ González Á，Garrido M A，Llorca D F，et al. Automatic traffic signs and panels inspection system using computer vision ［J］. IEEE Transactions on Intelligent Transportation Systems，2011，12（2）：485-499.

［2］ Saygili G，Van Der Maaten L，Hendriks E A. Featurebased stereo matching using graph cuts ［C］// Proceedings of ASCI-IPA-SIKS Tracks. Veldhoven，Netherlands，2011：1-6.

［3］ Banno A，Ikeuchi K. Disparity map refinement and 3D surface smoothing via directed anisotropic diffusion ［J］. Computer Vision and Image Understanding，2011，115（5）：611-619.

［4］ Wang Z F，Zheng Z G. A region based stereo matching algorithm using cooperative optimization ［C］// IEEE Conference on Computer Vision and Pattern Recognition（CVPR 2008）. Anchorage，AK，USA，2008：1-8.

［5］ Yang Q. A non-local cost aggregation method for stereo matching ［C］// IEEE Conference on Computer Vision and Pattern Recognition（CVPR 2012）. Providence，RI，2012：1402-1409.

［6］ 王 昕，马 岩，杨 剑，等. 区域立体匹配算法的实现及改进［J］. 光学精密工程，2008，16（10）：2002-2008. Wang Xin，Ma Yan，Yang Jian，et al. Implementation and improvement of area based stereo matching algorithm ［J］. Optics and Precision Engineering，2008，16（10）：2002-2008（in Chinese）.

［7］ De-Maeztu L，Villanueva A，Cabeza R. Stereo matching using gradient similarity and locally adaptive supportweight ［J］. Pattern Recognition Letters，2011，32（13）：1643-1651.

［8］ Veksler O. Fast variable window for stereo correspondence using integral images ［C］// Proceedings of 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Madison，WI，USA，2003，1：I-556-I-561.

［9］ Einecke N，Eggert J. A two-stage correlation method forstereoscopic depth estimation ［C］// 2010 International Conference on Digital Image Computing：Techniques and Applications（DICTA）. Sydney，NSW，2010：227-234.

［10］ Kang S B，Szeliski R，Chai J. Handling occlusions in dense multi-view stereo ［C］// Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition（CVPR 2001）.Kauai，Hawaii，2001，1：I-103-I-110.

［11］ Zhang K，Lu J，Lafruit G. Cross-based local stereo matching using orthogonal integral images ［J］. IEEE Transactions on Circuits and Systems for Video Technology，2009，19（7）：1073-1079.

［12］ Mattoccia S，Giardino S，Gambini A. Accurate and efficient cost aggregation strategy for stereo correspondence based on approximated joint bilateral filtering［C］// Computer Vision-ACCV：9th Asian Conference on Computer Vision. Xi'an，China，2009：371-380.

［13］ 岳 斌，侯春萍. 立体视差调整的快速估计方法［J］.天津大学学报：自然科学与工程技术版，2013，46（7）：571-578. Yue Bin，Hou Chunping. A rapid stereo disparity adjustment estimate method ［J］. Journal of Tianjin University：Science and Technology，2013，46（7）：571-578（in Chinese）.

［14］ Joglekar J，Gedam S S，Mohan B K. Image matching using SIFT features and relaxation labeling technique—A constraint initializing method for dense stereo matching［J］. IEEE Transactions on Geoscience and Remote Sensing，2014，52（9）：5643-5652.

［15］ 周 龙，徐贵力，李开宇，等. 基于Census 变换和改进自适应窗口的立体匹配算法［J］. 航空学报，2012，33（5）：886-892. Zhou Long，Xu Guili，Li Kaiyu，et al. Stereo matching algorithm based on Census transform and modified adaptive windows ［J］. Acta Aeronautica et Astronautica Sinica，2012，33（5）：886-892（in Chinese）.

［16］ 赖小波，朱世强. 基于互相关信息的非参数变换立体匹配算法［J］. 浙江大学学报：工学版，2011，45（9）：1636-1642. Lai Xiaobo，Zhu Shiqiang. Mutual information based non-parametric transform stereo matching algorithm ［J］. Journal of Zhejiang University：Engineering Science，2011，45（9）：1636-1642（in Chinese）.

［17］ De-Maeztu L，Villanueva A，Cabeza R. Stereo matching using gradient similarity and locally adaptive supportweight ［J］. Pattern Recognition Letters，2011，32（13）：1643-1651.

［18］ Humenberger M，Zinner C，Weber M W，et al. A fast stereo matching algorithm suitable for embedded realtime sytems ［J］. Computer Vision and Image Understanding，2010，114（10）：1180-1202.

［19］ Min D，Lu J，Do M N. A revisit to cost aggregation in stereo matching：How far can we reduce its computational redundancy？［C］// 2011 IEEE International Conference on Computer Vision（ICCV）. Barcelona，Spain，2011：1567-1574.

（责任编辑：赵艳静）

Adaptive Support-Weight Stereo Matching Algorithm Based on SIFT Descriptors

He Kai，Wang Xiaowen，Ge Yunfeng
（School of Electronic Information Engineering，Tianjin University，Tianjin 300072，China）

Aiming at the problem of low matching accuracy in both depth discontinuities and low textured regions of traditional local stereo matching algorithms，an adaptive support-weight stereo matching algorithm based on SIFT（scale-invariant feature transform）descriptors was proposed.First，the original matching cost was calculated with gradient amplitude and gradient phase.Then the adaptive support-window for each pixel was obtained with decision criterion based on the color similarity principle.Finally，with the L1 norm of SIFT descriptors of each pixel，the adaptive support-weight was calculated.Simulation experimental results show that the proposed algorithm can effectively improve the accuracy of stereo matching algorithms in both depth discontinuities and low textured regions，thus achieving higher matching accuracy.

stereo matching；gradient；support-weight；SIFT descriptor

TP391

A

0493-2137（2016）09-0978-06

10.11784/tdxbz201505043

2015-05-07；

2015-09-17.

国家自然科学基金资助项目（61271326）.

何 凯（1972— ），男，博士，副教授.

何 凯，hekai626@163.com.

网络出版时间：2015-09-28. 网络出版地址：http：//www.cnki.net/kcms/detail/12.1127.N.20150928.1549.002.html.