基于多窗体的改进视差图算法及其应用

熊邦书，程 骏

(无损检测技术教育部重点实验室(南昌航空大学)，南昌330063)

0 引言

随着摄像硬件设备性能的提高，立体视觉技术广泛应用于三维测量领域，而视差图计算又是立体视觉技术中的关键技术，决定三维测量的精度和效率，近年来得到国内外学者的广泛关注。视差图算法按照不同的匹配基元，可分为全局匹配算法［1-4］和区域匹配算法［5-12］2 类。全局匹配算法利用了图像的全局约束信息，对于局部区域敏感度小、匹配精度高，但它的计算代价很高，很难应用到有实时性要求的工程中，典型的全局匹配算法有图割算法［4］和置信传播算法［3］2类。局部匹配算法选取特征点邻域内的1个或多个子窗口(又称为聚合窗)，在另一幅图像中的1个区域内，根据某种相似性判断依据，寻找与子窗口图像最为相似的子图，对应的像素点为该特征点的匹配点，其优点是效率高，但对于遮挡和单一纹理图像误匹配率高、鲁棒性不佳。局部匹配算法可分为自适应聚合窗(Adaptive Window)算法［8-9］、自适应权值聚合窗算法［10］和多窗聚合(Multi-window)算法［11］等。传统的多窗算法采用大小为3的聚合窗，对左右视图的图像进行匹配代价计算，并选择匹配度最好的像素作为匹配像素。由于其聚合窗尺寸小无法有效过滤图像的噪声以及景物边缘影响，导致算法的误匹配率高，无法满足工业检测的精度需求，因此提出了使用大型聚合窗的多窗算法［11］。使用大窗的多窗算法在匹配代价计算过程中，并未对传统多窗算法进行改进，仅采用了尺寸为9的大型聚合窗进行匹配代价计算，随着聚合窗的尺寸增大，图像在匹配过程中能够更好的过滤噪声并减小边缘影响，但计算量大，这也导致算法时间度增加，无法将其应用在时间度要求较高的工程中。通过提取图像边缘，缩小目标像素匹配范围，并对传统的多窗算法进行改进及优化，以提高本算法的精度和效率。

1 算法描述

本算法的主要步骤有:1)边缘提取，对左右视图的图像进行边缘提取，缩小像素点的可能匹配区域;2)匹配代价计算(代价聚合)，利用改进的多窗算法［1-2，11］对左右视图进行匹配代价计算;3)视差选择，按照WTA(winner takes all)胜者为王算法［1-2］对匹配代价进行选择，确定视差图。

1.1 边缘提取

根据立体视觉中极线理论［1-2，13］的约定，左右视图的同一个像素点必然处于同一根扫描线上(在两幅扫描线对齐的图像意味着处于同一水平线上)，则左视图中的像素点(图像坐标为(x，y))一定出现在右视图中图像坐标为(x+1，y)至(x+d，y)这一段区域中，d的取值可以在双目摄像机标定时进行估算。传统的多窗算法为了确定一对匹配像素点，需要进行d次匹配代价计算，增加了算法的计算时间。

首先通过Canny算子提取图像边缘，然后为左视图的每一个像素点，在右视图中遍历1到d这一区域，找出灰度值相同的点，由此区分边缘与背景像素的匹配范围，边缘区域只需针对边缘匹配区域范围进行匹配代价计算，背景区域只需针对背景匹配区域范围进行匹配代价计算。

1.2 匹配代价计算

匹配代价计算是视差图算法最重要的一步，匹配代价计算的好坏直接影响到将来视差计算的正确与否。本算法的匹配代价计算采用SAD算法［1］，SAD算法在聚合窗覆盖范围内对每对像素点进行AD运算(差的绝对值)，然后累加得到结果，该算法具有计算简单以及运算速度快的特点，其计算公式为

其中，IL(x+i，y+j)代表左视图中像素点(x+i，y+j)处的灰度值，IR(x+d+i，y+j)代表右视图中像素点(x+d+i，y+j)处的灰度值，N代表聚合窗的大小。

在匹配代价的计算过程中，大型的聚合窗能很好地过滤噪声和曝光强度影响，但计算量大导致算法的速度无法保证，而小型聚合具有较快的计算速度，但对于噪声和曝光强度的影响表现很敏感，容易产生误匹配。经过大量的试验分析，本算法使用大小为9的聚合窗，具有较好的过滤噪声及曝光强度的效果，并通过优化算法提高算法的效率，图1为优化算法聚合窗的示意图。

图1 聚合窗示意图Fig.1 Sketch map of aggregation window

传统的多窗算法通过在聚合窗上滑动核来改变聚合窗的覆盖范围，减小聚合窗在物体边缘位置时由背景所产生的匹配误差。为了保证匹配的精度，不固定核的位置，聚合窗上的每一个位置都可以作为核位置，这也使得算法无法使用大型聚合窗，曝光和噪声的影响也随着增大。本算法在传统的多窗算法基础上进行改进，沿用大窗多窗算法所使用的大型聚合窗，通过对聚合窗分析及大量实验，发现通过固定核的位置可以得到9个特殊位置的聚合窗(图2)，用它们替代传统多窗算法的聚合窗，可大幅度减小算法计算量，提高了算法计算速度。

匹配代价的具体计算方法是，分别计算每对像素9个聚合窗的匹配代价，取最佳匹配代价作为左右视图像素的匹配代价结果，并由此得到视差。为进一步提高本算法速度，将9个聚合窗分为3类:核位于最上层的聚合窗，称之为第一类聚合窗(图2a～图2c);核位于中间的聚合窗，称之为第二类聚合窗(图2d～图2f);核位于最下层的第三类聚合窗(图2g～图2i)，采用计算机缓存技术存储中间计算结果，提高了匹配代价的计算效率。

图2 特殊聚合窗示意图Fig.2 Sketch maps of special aggregation window

以第二类聚合窗为例，匹配代价计算的主要过程如下:

1)先计算核位于中间聚合窗的SAD值，如图3a所示。将该聚合窗分为3个区域，分别用白色、黑色及黑白相间像素点区分，白色和黑色区域分别覆盖了另两个聚合窗的相应颜色像素区域，黑白相间区域为3个聚合窗的公共区域，通过计算分别得到白色区域匹配代价Csad_left-common(x，y)、黑色区域匹配代价Csad_right-common(x，y)、黑白相间匹配代价Ccommon(x，y)，将其保存在内存中。该窗的SAD值为白色区域匹配代价、黑色区域匹配代价与黑白相间区域匹配代价之和。

2)计算核位于左侧聚合窗SAD值，如图3b所示。由于已知 Csad_right-common(x，y)和 Ccommon(x，y)，只需计算右边新增四列像素的匹配代价，命名为Cnew_left(x，y)，如图3b阴影部分所示，将3者相加即可得到该窗SAD值。

3)计算核位于右侧聚合窗SAD值，如图3c所示。计算方法与计算核位于左侧聚合窗相类似，只需计算左边新增四列像素的SAD值，命名为Cnew_right(x，y)，如图3c阴影部分所示。

经过实验证明，本算法将原始计算量减少了接近一半，提高了算法的效率。

改进的多窗算法计算公式如式(2)所示，其中，Ccenter(x，y)、Cleft(x，y)、Cright(x，y)分别代表同一类聚合窗的3个匹配代价。

图3 改进算法示意图Fig.3 Sketch maps of improved algorithm

1.3 视差选择

本算法的视差选择步骤采用WTA算法［1-2］(Winner Takes All，胜者为王算法)。在匹配过程中，每对像素点都可得到一个匹配代价数组，保存该对像素点在9个聚合窗下的匹配代价，由于SAD算法的特性，在这9个匹配代价中选择最小的匹配代价作为该对像素点的匹配代价。由于左视图中的一个像素点可能出现在右视图的某个区域内(根据极线理论，处于同一条扫描线的一段线段中)，因此对于一个目标像素点，可能存在多个匹配像素对，将每对像素点的匹配代价保存在新数组中，数组的长度由像素对个数决定，对该数组再次进行比较，取最小匹配代价的像素点对作为正确匹配像素对，进而确定视差。WTA算法的计算公式如式(3)，N代表匹配像素的个数，d代表左右视图像素点的匹配区域。

2 实验结果与分析

为验证本算法的有效性，采用由Tsukuba大学网站上提供的双目立体视觉视差图研究的图源进行实验，如图4所示，其中4a和4b分别为左右视差图，4c为标准视差图，并将本算法与传统的多窗算法［11］和大窗多窗算法［10］进行对比实验，其结果分别如图4d、4e、4f所示，从图中可以看出本算法具有较高的匹配精度，对具有复杂纹理的图像区域有较好的鲁棒性，在图像边缘区域减小了噪声对匹配精度的影响，并提高了算法的速度。

为了量化评估本算法的性能，本试验采用平方根误差算法［1］量化评估视差图，平方根误差算法计算公式如式(4)所示。

其中，dC(x，y)代表算法视差图中位置为(x，y)处的像素灰度值，dT(x，y)代表标准视差图中位置为(x，y)处的像素灰度值，N代表视差图的像素总数。采用计算机CPU运算时间评估算法效率，所有实验均在 Intel酷睿2双核 CPU(主频2.4 GHz)及2 G内存环境下进行。

传统多窗视差图算法、大窗多窗视差图算法以及改进多窗视差图算法的量化对比结果如表1所示，从表中可以看出本算法相对于传统多窗视差图算法具有更好的匹配精度，相对于大窗多窗算法具有更快的运算速度。经过大量试验证明，本算法匹配精度高、效率高，能有效过滤图像中背景所造成的误匹配，对于背景复杂图像具有较好的匹配结果，鲁棒性好。

表1 试验所用算法的运行参数Table 1 Parameters of the algorithm

图4 试验结果Fig.4 Results by test

3 结论

1)在传统的多窗视差图算法和大窗视差图算法上进行改进，提出了一种基于多窗体的改进视差图算法，通过边缘提取和固定聚合窗的方式，提高了算法的匹配精度和效率。

2)在本算法的匹配代价计算过程中，采用了计算机缓存技术，将特殊聚合窗分为3类，通过保存中间计算结果优化算法的计算量，进一步提高了算法的效率。

3)本算法相对于传统的多窗体视差图算法和大窗多窗视差图算法具有更高的运算效率和匹配精度，对于复杂背景以及图像噪声具有较好的去除效果，可应用于背景复杂、精度要求较高的工业、计算机立体视觉领域。

［1］Scharstein D，Szeliski R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms［J］.International Journal of Computer Vision，2002，46(1):7－42.

［2］Richard S.Computer Vision:Algorithms and Applications［M］.Springer，2001:1 －812.

［3］Klaus A，Sormann M，Karner K.Segment-based stereo matching using belief propagation and a selfadapting dissimilarity measure［C］. Proceeding ofInternationalConference on Pattern Recognition，2006，3:15－18.

［4］Hong L，Chen G.Segment-based stereo matching using graph cuts［C］.IEEE Computer Society Conference on Computer Vision and Pattern Recognition，2004，1:74－81.

［5］Mattoccia S.A locally global approach to stereo correspondence［C］.IEEE 12th International Conference on Computer Vision Workshops，2009，10:1763－1770.

［6］Stefano L D，Marchionni M，Mattoccia S.A fast area-based stereo matching algorithm ［J］.Image and Vision Computing，2004，22(12):983－1005.

［7］Hirschmuller H，Innocent P R，Garibaldi J.Real time correlation based stereo vision with reduced border errors［J］.International Journal of Computer Vision，2001，47(1/2/3):229－246.

［8］Veksler O.Fast variable window for stereo correspondence using integral images［C］.Proceeding of IEEE Conference on Computer Vision and Pattern Recognition，2003，1:556－561.

［9］Kanade T，Okutomi M.A stereo matching algorithm with an adaptive window:theory and experiment［J］.IEEE Transactions Pattern Analysis and Machine Intelligence，1994，16(9):920 －932.

［10］Federico T，Stefano M，Luigi D S，et al.Classification and evaluation of cost aggregation methods for stereo correspondence［C］//IEEE Conferenceon ComputerVision and Pattern Recognition，2008:1 －8.

［11］Fusiello A，Roberto V.Efficient stereo with multiple windowing［C］//IEEE ConferenceOnComputerVisionandPattern Recognition，1997:858－863.

［12］刘维罗，桂娥杨，欣荣.一种快速鲁棒区域匹配算法［J］.微计算机信息(测控自动化)，2009，25:184－191.

［13］王爱红，王琼华，李大海，等.立体显示中立体深度与视差图获取的关系［J］.光学精密工程，2009，17:433－438.