立体匹配（精选7篇）
立体匹配 篇1
1. 局部匹配算法
局部匹配算法主要包括区域匹配法、特征法。
1.1 区域匹配算法原理
区域匹配算法是以基准图像中待匹配点为中心像素创建一个大小为m×n窗口, 由该窗口内的像素灰度值来表征该像素。在第二幅图像中, 沿极线在视差搜索范围内取出与基准点同样大小的邻域, 依次与匹配点的窗口进行比较, 其最大相似性对应的点就是最佳匹配。
区域匹配算法的重点是匹配代价的计算和匹配代价的累积。匹配代价计算就是选取相似性测度函数, 而匹配代价的累积体现在支撑窗口的选取上。几乎所有的区域匹配算法都要关注这两个问题:
1) 选取相似性测度函数。常用的相似性测度函数如下:
(1) 最小绝对差算法SAD
(2) 最小平方差算法SSD
2) 选取支撑窗口大小。一方面窗口的尺寸要尽量的大, 以便为可靠的匹配包容足够的灰度变化;另一方面, 窗口太大则包含视差的较大变化, 则会因左右图像上不同的投影畸变, 使得匹配位置不准确。
1.2 区域匹配实验结果
分别用SAD相似性测度函数对Tsukuba匹配源图像对进行匹配, 采用3×3、5×5两种窗口。实验结果如图1.1所示:
2. 全局匹配算法
大部分全局算法基于能量最小化的思想, 寻找视差函数d, 使全局能量最小化。本文对一种常用的全局算法--动态规划法做重点研究, 与区域匹配算法进行比较。
2.1 动态规划算法
动态规划匹配算法在外极线单调顺序约束下寻找视差空间图像 (DSI) 上的最小代价路径。最优路径的代价是所有子路径的和, 这些子路径所经过点的匹配代价由相似性度量因子决定。
2.2 动态规划实验结果
针对Birchfield的动态规划算法, 所产生的视差图如图2.1所示。
3. 总结
基于区域匹配中匹配窗口较小时, 误匹配较多, 而窗口较大时, 边缘处又显得很模糊, 所以窗口大小与形状必须具有较强的适应性。动态规划是对一条扫描线计算全局匹配代价, 提高了匹配的准确性。但是动态规划有一个很大的局限性, 它缺乏对水平连续性约束和垂直连续性约束的融合。从匹配性能上看, 动态规划算法在边缘不连续区域有较高的误匹配, 而在其它区域的误匹配百分比都较基于区域匹配算法低;从匹配速度上看, 基于区域匹配相对于全局匹配较小的计算量, 使其匹配速度明显加快, 更适合对实时性要求较高的应用。
摘要：立体匹配是立体视觉中的关键技术之一, 能否有效地解决该问题影响着立体视觉的发展。本文研究了相似性测度函数和邻域窗口对基于区域匹配算法的影响, 实现了具有代表性的全局匹配算法——动态规划, 并与基于区域匹配算法进行了比较。
关键词：立体匹配,基于区域的匹配算法,动态规划
参考文献
[1]张广军.机器视觉[M].北京:科学出版社, 2005.
[2]S·Birchfield, C·Tomasi.“Depth discontinuities by pixel-to-pixel stereo”[J].International Journal of Computer Vision, 1999, 35 (3) :269.
立体匹配技术发展研究 篇2
1 局部匹配算法
局部匹配的方法所选择的匹配基元基本上分为三类, 据此局部算法分为区域匹配算法、特征匹配算法、相位匹配算法。
区域匹配算法用基准图像中点的邻域的窗口内像素的灰度值的某种分布如常用的SAD来表征待匹配点, 以在此表征下的相关程度为标准, 在对准图寻找对应的一个匹配像素点。区域匹配算法能够在平坦的丰富纹理区域获得稠密的视差图, 这是区域匹配最显著的优点。
邻域窗口选取越小, 在视差不连续区域匹配精度越高, 但在低纹理区域不能覆盖足够的灰度变化匹配, 匹配效果不好;大窗口在重复纹理区域取得较好的效果, 而在弱纹理区域中的深度差不连续的区域易造成误匹配。所以通过自适应的窗口大小[2]或自适应权重的聚合方式来改进匹配效果。为了解决弱纹理区域的匹配问题, 一些研究提出了利用图像分割区域信息对其进行改进的算法。该类方法将亮度和颜色相似的像素聚类成一个分割块, 位于同一个分割块的像素的深度进行整体求解。由于自动分割往往会出现一些错误, 所以一些方法提出采用过分割或软分割技术来试图解决不正确分割所带来的问题。
区域匹配算法仅依赖于视图中灰度信息的变化, 使得其对噪声和图像的畸变敏感。
基于特征的匹配算法在左右立体视图上把分别由同一关键场景点投影所得像素点的对应关系找出来。特征点可以是图像中灰度梯度极值或边缘线交点的角点, 也可以是直线段, 面等结构特征。
特征匹配处理算法的优点包括: (1) 匹配准确度高。特征点属于高级图像结构信息, 鲁棒性强, 受光线和噪声等方面的影响小。 (2) 由于视差的深度不连续多会反映在包括了边缘, 梯度等信息的特征算子里, 所以其对于深度视差不连续区域的匹配效果好。 (3) 由于特征点数量有限, 所以匹配速度快。
由于特征在图像中的稀疏性, 提出的特征点的数量在整图中分布比较稀疏。这使得特征匹配算法不能得到稠密的视差图;而且特征点的提取和定位效果的好坏, 将很大程度上影响匹配的精度。
特征匹配常与同其他立体匹配算法相结合使用。例如分级特征匹配算法的思想是根据图像自身的结构特点分层提取边缘特征, 逐级构建特征分组。最终算法将所有信息融合。这样逐层分级的策略减少了搜索空间, 从而减少了计算复杂度。
最晚提出的局部匹配方法是相位匹配算法, 包括相位相关法和相位差-频率法。相位匹配算法的实质是寻找局部相位相等的对应点。与上述两类传统的方法相比较, 像素的相位信息本身反映了信号的结构信息, 对图像的高频噪声和畸变都不敏感。此匹配方法主要优点是适于并行处理高效实现, 可获得亚像素级精度的致密视差.但由于其对相位的各种扰动较为敏感, 一般只能得到景物的粗糙结构。
相位匹配算法需要解决相位奇点匹配问题和相位卷绕问题。通过相位奇点的检测和去除以及最邻点视差填补的办法可以解决相位奇点的匹配问题。徐彦君在研究中选择低冗余度的质数序列作为Gabor滤波器组的波长, 将相位匹配算法的收敛范围扩大, 实现了高效的尺度自适应选择算法, 克服了相位卷绕的问题。
2 全局匹配方法
2.1 态规划的匹配算法
基于动态规划的立体匹配算法将匹配过程看成是在左右图像对应扫描线上寻找最小匹配代价路径的过程, 规划出的路径由趋于具有最小匹配代价的匹配点的集合构成, 即正确匹配点的集合。
但传统的得到的视差图中存在水平条纹瑕疵。原因是动态规划是基于扫描线进行处理, 缺乏水平连续性约束和垂直连续性。半全局的立体匹配算法被提出来, 用多个一维平滑约束来近似匹配像素的二维平滑约束, 在多个方向上进行动态规划。该算法改进了条状瑕疵现象, 但依然不能利用图像中的绝大部分像素来计算视差。例如在低纹理区域, 可能没有一条路径能够搜索到足够的纹理信息就会导致错误匹配。
2.2 图割法和置信度传播立体匹配算法
图割法和置信度传播算法本质上都是运用马尔科夫随机场来进行全局匹配的优化, 仅仅是在构图时和构造能量函数时所采用的方法不同。
置信度传播 (BP) 算法是一种基于消息传递机制的马尔科夫随机场最小化能量估计方法。置信传播算法利用最大积算法求解整幅图像全局能量最小值时的视差分布。置信传播算法的优点是能很好地处理深度不连续区域和低纹理区域。这是由于其消息传输能够适应图像中区域的特点自动调节消息传输时的距离的远近, 计入了相邻像素点以及不相邻像素点
基于Matlab Builder JA的QPSK调制解调在线仿真
程赛
(云南大学信息学院, 云南昆明650091)
摘要:阐述了基于Java Web和Matlab Builder JA开发的一般模式, 将Matlab强大的仿真计算能力应用到Web环境中。在浏览器中输入Matlab程序参数并提交给服务器, 服务器结合Web Figure图形方式的使用, 将实验结果直观地返回, 实现了交互式操作。通过这种B/S方式, 完成了二进制数字信号的QPSK调制与解调的模拟仿真。
关键词:Matlab;Builder;JA;Java;Web;QPSK;调制;解调
中图分类号:TN911.3文献标识码:A
0引言
Matlab以其强大的矩阵处理能力和丰富的图形渲染能力在工程计算和教育科研领域有着广泛的应用。其中基于Web的应用也越来越受到重视。但是, Matlab 2006b之后的版本却不再支持Matlab Web Server功能[5]。官方推荐使用Matlab Builder NE/JA来取代Web Server的功能[8]。
Matlab Builder JA用来将M函数文件创建成一个Java组件, 它支持Matlab的所有功能。将生成的Java组件作为Servlet或其他Java程序的外部添加库, 通过访问这些库中类的方法来调用MCR产生处理结果[1]。
1系统构架
Matlab的Java Web应用, 包括J2EE服务器, Matlab Build-
对目标像素点的影响。置信度传播算法不足体现在:由于基于逐个像素点之间的消息传输, 使计算量很大, 优化过程需要通过多次的迭代获得最终结果;二是单个像素点的颜色的畸变, 如在实际场景中, 由于噪声、颜色效应等原因, 造成的某些像素点颜色的突变, 从这种突变点进行消息传输, 算法精度将受到影响。
针对计算效率低下的问题, Felzenszw alb等人提出了一种分层的置信传播的方法, 缩短了一般的置信度传播算法的收敛时间。HBP得到的效果同标准BP算法相近, 运算的实时性方面可以同一些局部的方法相当。
图割方法是由Vladimir Kolmogorov等提出的将图论中的最小割算法运用到立体匹配的优化过程中, 通过求得最短路径的过程得出整幅图像的视差。步骤包括建立匹配能量函数, 构造网格图, 利用最大流求解能量函数的最小值。
图切割算法具有解决组合优化问题的良好性能, 在低纹
文章编号:1673-1131 (2012) 05-0045-02
er JA产生的Java组件和Matlab Compiler Runtime (MCR) 。MCR是一套运行经编译过的Matlab代码的库, 它允许在服务器端集成。终端用户通过Web浏览器发送请求到服务器, 服务器端程序调用Matlab Builder JA创建的Java组件, 调用MCR, 执行Matlab程序, 得到所需的结果并返回。图1显示了基于Java的Matlab Web应用的框架。
2 QPSK调制解调技术
QPSK (Quadrature Phase Shift Keying, 正交频移键控) 广泛应用于无线通信中, 是一种重要的调制解调方式。它利用载波的四种不同相位差来表征输入的数字信息, 分别有/4, 3/4, 5/4, 7/4四种载波相位, 调制时输入的是二进制数字序列, 为了配合四进制的载波相位, 则需把二进制数据变换为四进制数据, 也就是将二进制数字序列中每两个比特分成一组, 共有四种组合, 即00, 01, 10, 11, 其中每一组合称为双比特码元。每一个双比特码元是由两位二进制信息比特组成, 它们分别代表四进制四个符号中的一个符号。QPSK中每次调制可传输2个信息比特, 这些信息比特是通过载波的四种相位来传递的。解调时则根据星座图及接收到的载波信号的相位来判断发送端发送的信息比特[7]。
在QPSK调制中, 串/并变换器将输入的二进制序列分为速率减半的两个并行序列, 经电平变换后成双极性序列, 然后分别对cos t和sin t调制, 两路信号相加后得到QPSK调制信号。QPSK同相支路和正交支路可分别采用相干解调方式解调, 得到I (t) 和Q (t) 。经抽样判决和并/串变换器, 将上、下支
理区域、遮挡区域以及深度不连续区域, 能够获得相对其他方法更高的匹配精度, 因而能生产高精度的稠密视差图。另外图割方法在优化过程中收敛速度也相对更快。图割算法的计算量是非常大的, 应用中必须提高其时间效率。
摘要：比较分析了各种立体匹配算法的基本思想和各自的优点和局限性。为各种算法的融合和改进研究提供了分析指导。
关键词：立体匹配,局部匹配,全局匹配
参考文献
[1]Scharstein D, Szeliski R.A Taxonomy and Evaluation of Dense Two frame Stereo Correspondence Algorithms[J].International Journal of Computer Vision, 2002
立体匹配 篇3
立体匹配问题是计算机视觉研究的热点问题之一，它是利用计算机来模仿人类通过眼睛线索感知距离的一种方法。其中关键的一点是解决图像上的视差计算问题，以此来恢复点的三维坐标，进而试图重建物体的三维表面信息。目前所采用的立体匹配方法大致可以分为两类： (1) 基于区域灰度相关性的方法[1][2]，该方法可以得到稠密的视差图，但是其匹配的精确度要受到窗口大小、纹理和光照反射的影响，而且具有可观的时间复杂度； (2) 基于图像特征的匹配[3][4]，该方法更多地强调利用空间景物的结构信息来解决匹配的歧义性，匹配特征主要为线状特征、角特征、区域特征等，该方法只能得到稀疏可靠的视差图。动态规划法在立体匹配中得到了普遍的应用，文献[5]参考了语音信号处理中的时间规整算法 (Dynamic Time Warping, DTW) ，以灰度段作为匹配的基元，算法简便，利于匹配，但其灰度分段在遮挡、光照不均和畸变的情况下会产生误分段；文献[6]采用一种模糊逻辑的方法先是进行边缘点的检测，把极线上边缘点之间的像素都划分为一个段，然后做左右图像相容段上像素的匹配，这样特征点匹配的准确性对整个视差图的准确性起着至关重要的作用, 且在噪声、遮挡及透视等因素影响比较严重的情况下，特征点的精确匹配会受到干扰；文献[7]提出一种基于自适应窗口的时间规整算法，但是没有利用像素的彩色信息和梯度信息，而且也只是采用效果不好的比较灰度大小来分段。Koschan和Rodehorst (1997) 认为用彩色信息代替灰度信息，立体匹配结果的准备率能够提高20%-25%，为了得到精确度更高的视差图，本文提出一种基于区域生长的时间规整立体匹配算法，先用边缘点对极线初分段，再把待匹配图像的边缘点分段结果用区域生长方法分割为大小不等的匹配区域序列，类似于待匹配的模板。在图像对中的另一幅图像的视差范围的窗口中利用区域生长方法生成若干个匹配序列，再利用颜色极小选择最佳的匹配序列，以此两个区域作为匹配基元，再利用DTW算法对匹配序列进行基于动态规划的整体匹配。
1、区域生长方法的匹配序列划分与获取
本文基于颜色段的立体匹配算法，是将图像对中对应极线上的图像信息按颜色信息进行分段，以颜色段作为匹配基元，利用DTW (dynamic time warping) 方法进行匹配。以颜色段作为匹配基元比点基元覆盖的图像空间要大，可以减少误匹配发生的几率，更容易进行匹配，而且这种方法比基于特征线段、二次曲线或任意平面代数曲线的方法计算起来要简便得多。我们希望能够得到图像对中视差值比较相近的区域来进行匹配，这两个区域可以称之为左右"匹配序列"。因为存在遮挡的问题，所以左右匹配序列的尺寸并不一定相同，不可能也不应该试图找到大小全部相等的匹配序列区域。本文算法的设计和实现遵循如下视觉理论的约束条件：外极线约束；匹配惟一性约束；视差连续性约束。
考虑二种得到匹配序列的方法： (1) 利用像素点的灰度信息与灰度均值的差小于设定阈值的方法对图像的像素行进行分段； (2) 通过基于特征的边界检测来确定匹配序列。文献[6]首先获得边缘特征点的视差, 然后在这些特征点视差图的约束下, 对非特征点利用灰度大小进行分段, 既缩小了匹配空间, 又保证了匹配的相对准确性, 获得了较好的效果, 但带来的问题是, 由于特征点的视差图对整个视差图的准确性起着至关重要的作用, 且在噪声、遮挡及透视等因素影响比较严重的情况下, 特征点的精确匹配会受到干扰。文献[7]设定自适应窗口，但是没有利用颜色信息，也只是利用灰度信息进行分段，相比来说没有利用颜色信息的区域生长的分段方法对极线的分割效果好。
1.1 边缘特征点匹配
边缘特征点的匹配就是要找到一幅图像中某一扫描线上的某个边缘特征点在另一幅图像中的对应边缘特征点，但由于在外极线的约束下，在另一幅图像中相应扫描线上，仍然存在多个可能匹配的边缘点，因而匹配过程具有不确定性和模糊性。匹配之前先要进行边缘特征点的检测，按照图像边缘检测所利用的图像信息, 边缘检测方法可分为两大类：基于梯度信息的图像边缘检测和基于相位信息的图像边缘检测。相位检测计算复杂度比较高，实时性不好；灰度梯度信息对图像中大量的噪声非常敏感，且随着图像的对比度和亮度的改变而发生改变。我们采用Canny算子，同时加入色彩梯度信息，检测的准确率得到很大提高。
我们定义颜色梯度如下：
像素总的颜色梯度可以定义为：
我们采用经典的Canny算子提取图像对的色彩边缘特征，以边缘点的色彩梯度大小、方向、边缘点的色彩梯度大小相关系数以及边缘点的颜色相关系数等4个因素作为边缘点相似性的度量要素。然后我们利用文献[6]的方法采用模糊理论来解决边缘点的匹配问题，它的出发点正在于能有效地处理这种不确定性问题的模糊性。
1.2 极线分段
在文献[8]中列出了所有的12种颜色相似度计算方法，所有的计算方法都输入两个矢量，计算得到一个在[0.0, 1.0]之间的结果，1.0表示两种颜色完全相同，0.0表示两种颜色完全不相同。[9]对这12种方法进行了对比实验，证明了绝对值指数方法是最优的。绝对值指数方法定义如下：
fi和fj是两个P维颜色矢量，在RGB颜色空间中每个点的颜色由红绿蓝三个元素的矢量表示，所以p=3, S (fi, fj) ，是颜色相似度，其中β>0。为了减小计算的复杂度，而且不影响计算结果，本文中我们对绝对值指数方法进行一些改变，直接用绝对值差的和来表征两个像素颜色的相似性。即：
区域生长方法[10]将图像以像素为基本单位来进行操作。分割步骤如下：
1、对图像进行逐行扫描，找出尚没有归属的像素；
2、以该像素为中心检查它的领域像素，即将领域中的像素逐个与它比较，如果颜色差小于预先确定的阈值，将它们合并；
3、以新合并的像素为中心，返回到步骤2，检查新像素的领域，直到区域不能进一步扩张；
返回到步骤1，继续扫描直到不能发现没有归属的像素，刚结束整个生长过程。
采用上述方法得到的结果对区域生长起点的选择有较大的依赖性。为了克服这个问题可以我们采用下面的改进方法：
1、设颜色差的阈值为0，用上述方法进行区域扩张，使颜色相同像素合并；
2、求出所有领接区域之间的平均颜色差，并合具有最小颜色差的邻接区域；
3、设定终止准则，通过反复进行上述步骤2中的操作将区域依次合并直到终止准则满足为止。
另外，当图像中存在缓慢变化的区域时，上述方法有可能将不同区域逐步合并而产生错误，为了克服这个问题，不用新像素的颜色值去与领域像素的颜色值比较，而用新像素所在区域的平均颜色去与各个领域像素的颜色进行比较。
在实际应用区域生长方法时需要解决3个问题：选择或确定一组能正确代表所需区域的种子像素；确定在生长过程中能将相邻像素包括进来的准则；制定让生长过程停止的条件或准则。图像经过边缘特征点匹配后，得到图像极线各线段的的大体分布，可以利用代表各线段分布的边界信息自动获得种子点。同时这些边界点还可以作为生长停止的约束条件为生长过程提供潜在的线段模型。具体的生长过程如下：（1）对应用边缘特征匹配后的图像进行标记，取同一极线上两个边缘点的中心为种子点，计算该种子点与其左右像素（x, y）的颜色距离，如果该距离小于阈值T且生长还未到该线段的边界，则使其与种子点相同，同时将（x, y）压入堆栈；（2）从堆栈中取出1个像素，把它当作种子点，重复步骤（1），直到堆栈为空时，该区域生长过程结束。阈值T的选择则与种子点的选择有关，以每个线段的种子点为中心取一个小窗口，窗口的大小可调，分别计算窗口中像素点与中心像素点的颜色距离，统计最大颜色距离值和方差，阈值则为最大颜色距离值与方差之差。每两个边缘点中间一次生长后剩下的部分再用其中心点作种子点生长出新的线段。
1.3匹配序列获取
对右目图像某一极线进行分割后，接下来在左目图像对应极线上寻找像素段的相容匹配区域。设矢量f (x, y) 是右目图像 (x, y) 点处的RGB矢量，即：
R=fjr, frj+1, …, frj+M为右目图像某一极线上分割出的一个颜色段，设匹配最大视差为d，在左目图像中定义窗口L=fjl, flj+1, …, flj+m, …, flj+m+d，所以与右图像中R颜色段相容的左图像中的匹配序列一定是L的一个子集。我们同样对L进行区域生长分割，得到几个颜色段，记为Lk, Lk就是与R相容的匹配序列的候选序列族。我们取Lk中与R最相关的序列就是与R相容的匹配序列，相容匹配序列的方法通过段之间的颜色相似性来进行。
最相关序列L由 (L=min‖S (Lk-R) 2‖，k=0, 1，….K) 确定。有的图形利用边缘特征点分出来的段在某一区域都是像素很少的段，在这种情况我们就要先进行段的合并，保证段在某一长度之内。
2、基于DWT的颜色段匹配
得到了右图像中的序列R和它在左图像上的相容序列L，我们利用DWT算法对这两个序列进行匹配。对右图像中极线上的所有分割，首先我们选取长度最长的段先进行匹配，这样做不仅可以尽可能地避免匹配过程中的遮挡情况，而且可以缩小剩余段的匹配搜索范围，剩余段的匹配在该段的左、右部分分别进行，也同样先选长度最长的段进行匹配，像这样一直循环下去，直到所有颜色段都完成匹配过程为止。
为了使颜色段的匹配达到最佳效果，本文采用DTW算法，其核心思想是对匹配过程进行动态规划。设一个二维直角匹配坐标系，把右匹配序列R作为横坐标，坐标范围为 (0，…，M) ；把左匹配序列L作为纵坐标，坐标范围为 (0，…，N) 。横坐标和纵坐标上各点所组成的网格中，每一个交叉点表示左右匹配序列中可能匹配的一个点对 (m, n) 。DP算法可以归结为寻找一条通过此网格中若干匹配交叉点的连续的路径。路径不是随意选择的，根据约束条件中的连续性原则，匹配序列内各点的先后次序不必改变，因此所选的路径必定从左下角某点出发，在右上角某点结束。
在使用DTW算法进行匹配之前，我们要定义两个像素点的失真距离，失真距离越小颜色相似度就越高。设和分别是R和L上的两个像素，根据（5）式，这两个像素的失真距离可以计算为：
为了减少时间复杂度，防止过多地搜索匹配概率不大的路径，可以对路径中各点的斜率的最大和最小值给以限制，另外，左右两上匹配序列是通过区域生长得到的，不能保证匹配的起点和终点为固定点，所以无论是起点还是终点都采用松驰点，可以进一步克服不精确造成的误匹配，但是也增加了计算开销。
这样，求最佳匹配的DP算法可以归结为求一个最佳匹配路P，使得沿匹配路径P的积累失真距离达到最小值，为了方便表达，这里使用坐标 (m, n) 来代表R和L的匹配关系，使用距离d (m, n) 来代表失失真距离，为了满足路径的斜率在一个小的范围内，如果路径已经通过了 (mi-1, ni-1) 匹配点，那么下一个匹配点 (mi, ni) 可以是下列三种情况之一：
易证明，限定范围内的任一匹配点只可能有一条搜索路径通过，通过该点的最佳路径与以后的路径无关，那么，若匹配路径P通过节点通过‖mi-1, ni-1‖，并延伸到下一节点‖mi, ni‖，则此路径的累积失真表示为d‖mi, ni‖=d‖mi, ni‖+d‖mi-1, ni-1‖，这样动态规划的基本运算可以归结为：
最后得到的匹配路径P的总的失真距离为：
搜索到 (mk, nk) 时，已经生成并保留一条最佳路径，通过逐点向前回溯，可以求得整条路径P，回溯的起点即（下转第86页）为累计失真距离等于上式结果的匹配点，已知匹配路径P及L和R的起始坐标，不难得到各匹配像素的视差值，遍历图像后，即可以得到整个图像对的视差图。
3、实验结果及结论
在Matlab环境下，图1是对Teedy图像和Cones图像本文算法匹配结果。视差图中灰度级低 (亮度低) 的地方表示视差小，也即距视点较远，深度值大；反之，灰度级高 (亮度高) 的地方表示视差大，距视点较近，深度值小。从图中还可以看出匹配获得很好的效果，从而说明本文提出的算法是有效的。与采用基于区域的灰度相似算法的实验结果相比，本文算法明显改善了匹配效果，而且其运行时间大为减少，比基于区域的灰度相关算法的运行时间平均减少10～15倍。
通过理论分析和实验结果可以得出如下结论：（1）本文方法是基于区域生长的左右匹配序列的整体匹配处理算法，改善了匹配效率；（2）采用区域生长的算法提高了极线分割的准确性，也能够寻找到更准确的匹配序列；（3）采用绝对值指数的颜色相似测度，增加了像素的颜色信息，匹配更为准确。采用颜色作为匹配基元的优势在于，相对于点基元，覆盖了更大的图像空间，从而减少了误匹配发生的几率，更容易进行匹配，本文算法在虚拟现实和机器人视觉领域具有实用价值。
摘要：针对立体匹配过程中存在的不确定性和模糊性, 本文提出先利用匹配的边缘特征点对极线进行初分割, 然后利用区域生长算法进行颜色分段, 在颜色段的基础上进行时间规整的立体匹配算法。根据外极线约束, 在视差范围窗口内采用颜色相似极大得到长度不相等的两个像素段作为相容的匹配序列, 利用动态规划方法及连续性约束寻找一条最佳的匹配路径, 根据回溯得到匹配路径及其坐标值得到高密度视差图。实验结果表明该算法具有良好的匹配效果。
关键词：区域生长,立体匹配,DWT,动态规划
参考文献
[1]O.Veksler, "Fast variable window for stereo correspondence using inte-gral images, "in IEEE Conference on Computer Vision and Pattern Recog-nition, vol.1, 2003, pp.556-561.
[2]K.-J.Yoon and I.S.Kweon, "Adaptive support-weight approach forcorrespondence search, "IEEE Transactions on Pattern Analysis and Ma-chine Intelligence, vol.28, no.4, pp.650-656, 2006.
[3]D.G.Lowe, "Distinctive image features from scale-invariant key-points, "International Journal of Computer Vision, vol.60, no.2, pp.91-110, 2004.
[4]X.Lu and R.Manduchi, "Wide baseline feature matching using thecrossepipolar ordering constraint, "in IEEE Conference on Computer Visionand Pattern Recognition, vol.1, 2004, pp.16-23.
[5]周东翔, 蔡宣平等。基于灰度段的立体匹配算法, 软件学报, 2001, 13 (7) :1101-1106。
[6]Dongxiang Zhou, Qiongyu Wu.A Stereo Matching Algorithm Based onFuzzy Identification, Proceedings of the 2003 IEEE Intemational Confer-ence on Robotics.intelligent Systems.Changsha, China-October 2003.
[7]刘正东, 杨静宇。自适应窗口的时间规整立体匹配算法, 计算机辅助设计与图形学学报, 2005, 17 (2) :291-294。
[8]S.Barnard and M.Fischler.Computational stereo.Computing Surveys, 14 (4) :553-572, Dec 1982.
[9]K.N.Plataniotis and A.N.Venetsanopoulos.Color Image Processing and Applocations, pringer-Verlag, berlin, 2000.
基于线段分割的图割立体匹配 篇4
立体匹配是立体视觉研究热点之一,在机器人导航、虚拟现实和三维电视等诸多领域有广泛的应用。立体视觉是建立在对应点的视差基础上,因此,图像中对应点匹配关系是立体视觉中极其重要的问题[1]。立体匹配的实质是在来自同一场景的2个点集合中,寻找对应的像素点对,进而得到像素点的视差值。由于立体匹配问题的病态性特征,精确的立体匹配很困难,特别是在弱纹理区域、视差不连续区域和遮挡区域,其匹配难度更大[2]。
立体匹配方法大致可以分为2类[2]:局部方法和全局方法。局部方法是单独地在一个匹配窗内计算每个像素的视差,匹配代价通过一个匹配窗来聚合,具有最小代价总和的视差选定为该像素的视差值。因此,局部匹配方法的性能与所选取的匹配窗密切相关,利用简单的矩形窗能够得到实时视差,但其结果不理想。全局方法则把立体匹配转化为优化问题,通过最小化给定的能量函数E(f)来获取场景的视差图f,E(f)的一般形式为
E(f)=Edata(f)+Esmooth(f) (1)
式中:数据项Edata就是通过某个匹配代价来表征参考图像和目标图像的差异性,该值越小说明对应的像素亮度越相近,差异越小;平滑项Esmooth则是空间相邻像素具有不同视差的惩罚值,定义此项的缘由是图像中相邻的像素往往具有关联性,视差的变化一般是平滑的。
2 图割优化
除了某些特殊情况,式(1)优化函数是一个NP问题。根据相邻像素选取的不同,可以运用一维的动态规划进行优化,这种方法只考虑扫描线(立体校正后的外极线)上的最优,能够极大地简化式(1),其分段平滑只是在水平方向。所以问题就简化成一维的优化问题,而Esmooth不包括任何相邻的垂直方向的像素信息。假设一幅图像有n行扫描线,各行扫描线单独优化,能量函数就是n个扫描线的能量之和,这样得出的结果具有明显的拖尾现象。Veksler[3]提出的树型动态规划算法兼顾考虑了垂直方向相邻的像素,效果明显好于一维的动态规划,以及后来的一种介于全局和局部之间的半全局方法,都进行了较好的权衡。但是,以上的几种方法都会丢掉一些重要的结构信息,而当相邻像素选为4邻域结构时,则保留了相对完整的相邻像素的信息,这种4连接图利用图割优化得到的视差明显要接近真实视差[4]。
所以接下来需要解决4邻域图的优化问题。许多科研人员对其进行了研究探索,其中Boykov[4]和Kolmogorov[5]等人使用图割算法有效地得到了平滑的视差图。所谓的图割算法就是通过构造网格图使能量函数与网格图所割的容量相对应,利用最大流/最小割理论求出对应最小割,该算法在计算复杂度上属于多项式时间算法。Scharstein和Szeliski[2]将立体匹配中常用的几种优化算法进行了比较,发现与传统的算法(如模拟退火法、M-估计法等)相比,图割优化算法不仅总体精度高,并且在不连续区域和平坦区域的精度也比其他方法要高,且即使有些方法的精度与图割方法的精度可以比拟,但图割方法在优化过程中收敛速度更快。当然,图割算法的计算量是比较大的,但是,人们提出了一些方法来提高其效率。当图像大小为N,视差最大值为D时, Preflow-push[6]算法在最差情况下的计算复杂度为O(N2D2lb(ND)),比动态规划的大得多,但是Roy和Cox[6]的研究结果表明,该算法在实际运行时计算复杂度为O(N1.2D1.3),与动态规划的复杂度可以比拟。
3 线段基元的提取
前面所提到的方法都是把每个像素点视为独立的单元进行处理的,而图像中相邻像素是有关联的。Tao[7]等给出了基于彩色-空间一致性区域分割的立体匹配框架,其想法是在彩色-空间一致的分割块里面不存在大的视差不连续,但是由于彩色分割是一件很耗时的工作,而且效果与分割的结果关系很大,不同的图像分割的程度不好控制,笔者根据Li[8]和Deng[9]的算法提出在全局框架下采用彩色-空间一致的区域分割方法进行立体匹配,从文献[8]中可以知道以分割块为操作单元的全局方法要优于以像素点为操作单元的全局方法,其稳定性能要好,但是区域分割的难度大、耗时长。所以本算法根据Sun[10]和Deng的彩色-空间一致的线性分割,以分割单元为全局匹配的操作节点。因此,笔者提出从图像的彩色亮度-空间一致性入手,把扫描线上彩色亮度值相近的相邻像素作为一个处理单元,并根据通用假设,即场景的视差是分段平滑的,如图1给出3种处理单元相邻的连接情况:1) 是以单个像素为节点;2) 是以分割块为节点;3) 是本文所采用的线型分割。实线连接表示作为一个整体的处理单元,虚线连接表示相邻处理单元的连接,虚线连接的多少表示两个相邻单元的相邻像素的个数。图1b和图1c相比图1a由于考虑了结构信息,可以提高算法的稳定输出结果。
在提取线段基元时,把已经校正好的立体匹配对图作为输入,令IL表示左图,IR表示右图。由于它们是扫描线对齐的,左右对应点具有相同的纵坐标。以左图作为参考图,对参考图沿着扫描线进行分割。为了准确匹配,视差在每一个线段分割单元中应该是缓慢变化的。一个简单有效的假设就是彩色值相同的相邻的像素视差是相近的,即所谓的彩色值-视差一致性。根据这个思想建立的彩色分割示意图,如图2所示。图2中右图中的分割扫描线对应左图中的白色线。
令图2a中扫描线上的一点j为某一线段单元的左端点,k表示其右端点。只有在同时满足以下2个条件时才能将j到k的所有像素归在一个分割单元内:
1)Vc(j,k)≤λ,Vc(j,k)表示为从j到k的所有像素彩色值的方差,
2)Ds(j,k)≤dist,这里Ds(j,k)表示像素j到k的空间距离,dist给定的是每个线段单元的最大长度,空间距离定义为Ds(j,k)=k-j+1。
这两个约束条件关注点不一样,第1个约束条件保证了在一个线段区域内的彩色一致性,第2个则是长度的约束,是为了避免扫描线视差的过度平滑。每一个线段单元的位置标记可以记录保存j和k的值来表示,并且能方便后续的相关操作。为了对每个分割线段有唯一的标识,可以对j到k的所有像素的位置用一个标签l标记,这样就能是把每一个分割的线段单元用一个唯一的标号标记起来,把所有标号的集合记为L。这样每一个线段单元的亮度值用当前分割单元所包含的像素亮度的平均值来表示,对于l分割单元其亮度值表示为
由于线段分割后依然是线段,因此其相邻的分割单元就比较好确定,可以在分割当前线段时,根据上一段所分割的结果求得,并且把与之相邻的分割单元和它们之间相邻的像素个数也进行统计,这里规定在“四邻域”的范围内对相邻的分割单元进行统计,把标记为l标号相邻的所有的标号集合定义为N(l)。可知,此处的相邻一般有3种情况,如图3所示。其中,图3a和3c表示的是不在同一扫描线上的相邻的情况,而图3b表示的是同一扫描线上相邻的情况,可以看出这3种情况相邻的像素分别为3,1,6。
4 基于线段基元的图割优化
根据图割优化原理,需要构造出如式(1)优化能量函数的两个项Edata和Esmooth。如前所述,操作对象不是单个像素而是分割后的线段单元,因此,需要对全局能量函数做必要的修正,修正后的优化函数为
式中:fl∈[0,dmax],dmax为最大视差值。第一项为匹配代价的聚合Edata,第二项是空间平滑项Esmooth。在这里把每个分割单元的Dl(fl)定义为包含在该单元内的所有像素的匹配测度的和,每个像素的匹配测度定义为
式中:x为横坐标值,y为纵坐标值,d为视差值;像素点对(x,y)和(x-d,y)分别为左右图像的点;CAD(x,y,d)表示左右图像对应点像素IL(x,y)和IR(x-d,y)的亮度差,该项反应的是当前像素取对应的视差的相似度;CCensus(x,y,d)表示左右图像对经过Census变换后,两个Census图中对应点值的距离。本文算法中,该项是两个25位二进制串的Hamming距离,二进制串是各匹配图像的5×5的Census变换得来的,此项反应的是该像素匹配的亮度分布的局部结构信息。另外,为了减少奇异点的影响采用了截断函数,TAD和TCensus分别为截断阈值。之所以选择两者的结合是基于2点考虑:1) 因为它们有各自的优势,把它们结合起来比单独选其中任何一种效果都要好;2)CCensus项引入了该匹配像素的周边像素的二维结构信息,这有利于消除一维线性结构计算上的误差。
以上定义了全局优化函数的第一项数据项,下面需要定义平滑项
Vl,l′(fl,fl′)=w(l,l′)·T(fl≠fl′) (4)
式中:T(fl≠fl′)表示Potts模型函数;w(l,l′)表示惩罚权重。根据参考图像线段分割结果,相邻的线段分割单元l和l′平滑权重代价为
式中:conp(l,l′)表示l和l′相邻像素的个数。在立体匹配中可以利用图像的综合信息,如在求权值代价时,就考虑参考图的亮度分布,而不需要考虑目标图像的亮度。对于相邻的两个像素,如果它们的亮度值近似,那么它们的视差值应该相等,这就很容易想到利用图像内部上下文的关系。
式中:K是大于零的Potts模型参数,其值的大小决定了视差图的平滑程度。
5 实验及结果分析
在上面的工作都做好之后,从Middlebury学院的立体匹配测试平台[11]上得到4对标准立体图像,在同一参数下对各个立体图像对进行试验,参数表如表1。得到的匹配结果如图4所示。4行图像自上到下分别为Tsukuba,Venus,Teddy和Cones测试图像,最左列是匹配中的参考图像,中间列是真实视差图,最右列表示的是本文算法的立体匹配图。经测试平台测试,算法效果比较如表2所示。其中,GCLS表示本文算法,GC[4]是图割算法,GCocc[5]是增加遮挡项的图割算法,GCN[12]是多视点图的图割算法。本文算法得到的4个结果在非遮挡区(nonoc)、平坦区和半遮挡区(all)以及不连续区(disc)与其他3种相关算法效果进行比较,数字表示对应算法在对应区域产生误匹配的百分比。
从表2中可以看到,总体而言,在全局优化的框架下通过简单的线性分割,图割匹配结果的性能得到了较大的提高,具有明显的优势,特别对于GC算法而言,性能提高显著。对增加了遮挡考虑的算法GCocc而言, 仍然有优势,即使在all区域也得到了较好的结果,只有极个别的测试图像的某个指标相对较大些。而对于GCN[12]来说,由于其采用的不是两幅图像而是多幅图的联合,获得信息相对全面,得到的结果在一些数据上有相对优势,本算法也能很接近其结果,特别是对于Venus测试图,本算法在nonoc和all区域具有优势。其他两个测试图Teddy和Cones的各方面显然优于GCN。另外,由于本算法采用了简单快捷的分割方法,改变了优化的对象,减少了优化的节点个数,节约了整体匹配的时间,较好地保留了区域的相关性。
6 总结
本文提出了一种在能量最小化框架下对参考图像扫描线进行分割的图割立体匹配算法。该算法利用马尔科夫模型,结合图像区域相关的特点,提出在原有的以像素点为优化节点的情况下,改进以分割的线段单元为优化节点。实验结果表明,相比原来直接不进行任何操作的方法其性能得到较大的改善,即使在遮挡情况下也有了提高。虽然,结果直观可见引起轻微的拖尾现象,分析可知这是前期线性分割后进行立体匹配的原因引起的。下一步的研究重点是在全局的函数中考虑遮挡因素并且消除拖尾的发生,以提高遮挡区域的匹配精度,还有算法中参数的自适应问题也值得研究。
参考文献
[1]张令涛,曲道奎,徐方.一种基于图割的改进立体匹配算法[J].机器人,2010,32(1):104-108.
[2]SCHARSTEIN D,SZELISKI R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J].International Journal of Com-puter Vision,2002,47(1):7-42.
[3]VEKSLER O.Stereo correspondence by dynamic programming on a tree[C]//Proc.IEEE Conference on Computer Vision and Pattern Recogni-tion.[S.l.]:IEEE Press,2005(2):384-390.
[4]BOYKOV Y,VEKSLER O,ZABIH R.Fast approximate energy minimi-zation via graph cuts[J].IEEE Trans.Pattern Analysis and Machine In-telligence,2001,23(11):1222-1239.
[5]KOLMOGOROV V,ZABIH R.Computing visual correspondence with oc-clusions using graph cuts[C]//Proc.International Conference on Com-puter Vision.[S.l.]:IEEE Press,2001:508-515.
[6]ROY S,COX I J.A maximum-flow formulation of the n-camera stereocorrespondence problem[C]//Proc.International Conference on Com-puter Vision.[S.l.]:IEEE Press,1995:492-499.
[7]TAO H,SAWHNEY H S,KUMAR R.A global matching framework forstereo computation[C]//Proc.International Conference on Computer Vi-sion.[S.l.]:IEEE Press,2001:508-515.
[8]HONG L,CHEN G.Segment-based stereo matching using graph cuts[C]//Proc.IEEE Conference on Computer Vision and Pattern Recogni-tion.[S.l.]:IEEE Press,2004:74-81.
[9]DENG Y,LIN X.A fast line segment based dense stereo algorithm usingtree dynamic programming[C]//Proc.European Conference on Comput-er Vision.[S.l.]:IEEE Press,2006:201-212.
[10]SUN X,MEI X,JIAO S,et al.Stereo matching with reliable disparitypropagation[C]//Proc.IEEE International Conference on 3D DigitalImaging,Modeling,Processing,Visualisation and Transmission(3DIMPVT).[S.l.]:IEEE Press,2011:355-362.
[11]SCHARSTEIN D,SZELISKI R.A taxonomy and comparison of two-frame stereo correspondence algorithms[EB/OL].[2011-09-09].ht-tp://vision.middlebury.edu/stereo/.
立体匹配 篇5
立体匹配是模仿人类视觉系统在两幅或者两幅以上图像中寻找对应点的过程[1,2],是计算机视觉中最重要也是最困难的部分。立体匹配主要分为区域匹配和特征匹配两大类[3,4]。与区域匹配相比,特征匹配是以物体几何特征为匹配基元,受外界因素影响小,在精度、速度和稳定性等方面都有较大优势[5,6]。常用的匹配基元有边缘、角点、线段等,其中边缘检测一直是国内外学者研究的重要领域。经典的方法,有利用Roberts算子、Laplace算子、Prewitt算子进行边缘检测[7],其检测速度快,但得到的往往是间断的、不完整的边缘,不利于直接运用;基于小波的多尺度法[8,9],通过确定小波系数的局部极大模可进行图像边缘检测,但这种方法只是对图像经小波分解后的高频部分进行了边缘处理,而忽略了低频分量所包含的部分边缘信息;通过动态阈值、改进平滑模版等方法提高边缘检测准确性,减小噪声影响,如Canny检测算子,虽然经过不断地改善[10,11,12,13],但算法往往都是以牺牲运算时间为代价的。总体而言,上述算法在性能上都有不同程度的提高,但在实际运用中存在一定的局限性,尤其在立体匹配中,难以满足目标边缘定位精度高、轮廓简洁、实时处理的要求。本文提出了一种适用于立体匹配的边缘提取方法。该算法首先使用一种简单而有效的双阈值法改进Canny检测算子,根据图像边缘几何性质进行选择、标记、跟踪关键点连接边缘,最后依据多边形逼近法原理[14,15,16,17]提出直线分割算法,获得完整边缘。该方法不仅有效解决了常见的边缘间断、虚假边缘等常见问题,而且进一步实现了目标轮廓提取准确全面,局部细节清晰,在后期的立体匹配处理中取得的良好的效果。
二、算法
2.1边缘检测
Canny检测算法是目前边缘技术常用的方法之一,算法主要由图像平滑、梯度幅值和方向计算、非极大值抑制以及双阈值连接等部分组成[18]。其定位性好、单响应以及信噪比高的优点,开始逐步运用于立体匹配的边缘检测中。为了减少噪声和微小干扰对边缘检测的影响,进一步降低运算复杂度,本算法首先对双阈值选取做如下的改进。
立体匹配中每一对图像对都存在微小却不可忽略的差异,因此不能简单地确定一个固定阈值,必须根据不同图像的灰度情况决定初始灰度差值T0[19]的取值。在双阈值选取中,以一幅大小为m×n的图像为研究对象,首先引入T0,它的选取对边缘检测结果有很大影响。利用图像各像素与周围邻域的关联性,解决局部噪声干扰、边缘丢失的问题。对图像中任意一点P(x,y),分别计算该点和其8邻域各点Pi(x,y)(i=0,1,2...7)的灰度差值,记为Ti(i=0,1,2...7),将其中的最大值记为Tjmax(j=1,2,3...),平均值记为Tjavg(j=1,2,3...)。以T0为门限,如果Tjmax>T0,则将该点记数Nj(j=1,2,3...),并将Tjmax存储于最大值集合Thtot中,将Tjavg存储于平均值集合Thtot中。遍历整幅图像后,得到所有满足条件点的参数。双阈值的计算公式如下:
其中,Th是双阈值中的高阈值,Tl是双阈值中的低阈值。通过Th获得的边缘图像Th[i,j],在其断点处由Tl得到的边缘图像Tl[i,j]的8邻域位置,寻找可以连接到轮廓上的边缘,利用递归跟踪的算法不断地在Tl[i,j]中搜集边缘,直到Th[i,j]中所有的间隙都连接起来为止。
2.2边缘连接
通过改进双阈值的Canny边缘检测算法可以提取图像的边缘信息,但是在实际处理中,由于不同图像存在不同的噪声情况、不均匀的照明而产生的边缘间断以及其它由于引入虚假的亮点间断所带来的影响,使得获得的一组像素很少能完整地描绘一条边缘。因此,必须进行边缘检测等后续处理。
首先,对检测的所有边缘进行细化。为保证提取的边缘为其邻域内极值点,去除边缘孤立点,本算法采用形态学中骨骼化[20]的方法细化边缘。表达式如下:
其中A表示已经检测得到的边缘,B表示3×3的结构元素,表示对A的连续k次腐蚀,K是A被腐蚀为空集合前进行的迭带次数,Sk(A)表示第k次细化结果,S(A)表示最终获得的细化边缘。
然后对细化过的边缘进行边缘连接。在连接中,改进方法巧妙地利用了边缘几何特性来提取关键点,从而避免了以往梯度幅度和角度计算复杂的问题。再用标记跟踪连接边缘关键点,找出真正的边缘,去除虚假边缘和短小边缘。与霍夫变换以及曲线拟和[7]等连接算法相比,本算法无须已知边缘特定形状,从而避免了阈值选取的难点。关键点的判定主要是指对连接点和端点的判定。其中,连接点是两条边缘之间的转折点,端点则是一条边缘的起始点和终点。对二值图像而言每一个边缘点,在其8邻域内,从左上角逆时针扫描,如果0和1的变换次数大于或者等于6,则该点在其8邻域内与2个以上的点连接,为连接点;如果0和1变换次数等于2,则该点只与一个点连接,为端点。
最后的边缘连接中主要分为以下几个步骤:
(1)搜索起始点:对每一个边缘像素,先进行关键点判定,再线性标记。若该是关键点且为未被标记,则标记为某一线段的起始点。标记数为整数,从1开始;
(2)双向搜索next_p:从某一边缘起始点开始,在其8邻域内逆时针搜索,将搜索到的第一个未标记的连接点赋予与相同标记,即为next_p,并返回a);如果8邻域内没有连接点,但存在边缘点,则在其8邻域搜索。若其中被标记过的点少于2个,则该边缘点被赋予相同标记,即为next_p;若没有,则将其8邻域中最后一个边缘点赋予相同标记,即为next_p。若其8邻域中无边缘点,则将next_p记为0,返回a)。按此方法搜索下去,直到没有新的next_p出现,则返回该边缘起始点,以同样的方法向反方向搜索next_p。
(3)边缘连接:将所有属于同一条边缘线段,即相同标记的点连接起来,形成连续的边缘。
(4)删除边缘毛刺:比较每一个连接点的4个邻接方向上的边缘,删除长度小于某一阈值的分枝,连接其它分枝形成边缘。返回a),搜索下一段边缘。
通过上述方法提取的边缘,基本实现了边缘连续性和精确性的要求。但在立体匹配中,如果将边缘所有点都作为特征进行匹配,必然大大增加运算量,降低了匹配效率。所以,为了提高边缘提取在立体匹配的处理性能,采取了直线段处理,分段地提取边缘,在连续平滑边缘处理中,突出目标的点、线段特征,以获得有效边缘。
边缘直线段处理主要采用多边形逼近算法原理,即按照一定的规则在两个最初端点之间的边缘线段中加入分割点,如果不满足规定的测试条件,则继续分割下去,直到没有进一步分割的必要,最后将这些分割点连接,形成完整边缘。其实现流程为:
(1)将已提取的关键点作为分割点,顺序地连接这些点形成初始多边形。
(2)在每两个相邻关键点,如A、B之间,沿着边缘寻找点C,计算得到点C与线段AB的距离d,当d小于预先设定的一个阈值,那么把C点作为新的分割点。点C(x,y)到两端点A(x1,y1)、B(x1,y2)连线的距离计算方法如下:
其中x1,y1和x2,y2分别是A、B两点横、纵坐标;x,y是C点横、纵坐标;D是线段AB的长度;d是C点到线段AB的距离。
(3)对获得的每一条线段继续分割下去,直到分割的线段长度达到设定的某一阈值,迭带终止。
(4)连接所有分割点,完成边缘直线化。
三、结果及分析
采用本文提出的边缘提取算法,针对不同类型的图像进行大量的实验。选取其中三幅不同类型的图像如图1至图3(a)所示,其边缘检测结果、连接及直线化处理结果分别见图1至图3(b)、(c)和(d)。实验结果表明,边缘连接处理不仅提高了边缘连续性,而且减少了边缘复杂性。例如,图1(b)中的人脸轮廓和眼睛、嘴巴等局部边缘虽然都被检测出,但在像素比较密集的地方,如帽子外轮廓和羽毛边缘,检测的边缘往往大于一个像素而产生了短边、伪边和边缘的间断。将图1(c)连接后的边缘结果和图1(b)相比,不难发现,帽子边缘的间断被重新连接起来,而且,羽毛上的大量短边被删除,主要轮廓清晰地提取出来。
同时,实验结果反映出边缘的直线化处理可以更好地突出边缘有用信息,如点、线等,使得提取的边缘能够表现目标的清晰轮廓。如图1(d)所示,提取的边缘主要由分割点和直线段构成,轮廓完整同时细节特征并未减少。图2(d)的处理结果可以更明显地发现边缘清晰程度逐步提高,绝大部分边缘为光滑的线段,不仅消除了图2(b)中有很多短边、毛刺的辣椒边缘检测结果,而且删除了辣椒表面大部分由于光照等造成的虚假边缘,取得了令人满意的效果。
为了进一步验证改进算法在立体匹配特征点提取中所起的作用,选取常用于立体匹配的图3(a)所示的人工合成图像进行边缘提取处理,再以图3(d)中提取的边缘上的特征点、线为指导,进行立体匹配的特征点提取处理。如图4所示,所提取的特征点分布合理,定位精度到位,经统计,特征点个数只占全部边缘点个数的6.5%,从而可以大大地降低后期匹配的计算量。结果表明,本文边缘提取算法对于立体匹配的特征点提取作用是十分有效的。
四、结论
本文提出了一种用于立体匹配的边缘提取改进算法。该算法不仅保持了以往边缘检测定位准、连续性好的优点,而且进一步删除短边、毛刺以及绝大部分虚假边缘。通过直线分割处理,巧妙地利用目标几何特性,既突出了边缘的点、线特征,也降低了算法的复杂度。实验结果表明,该改进方法实现了轮廓提取准确有效,局部细节特征突出,有利于立体匹配的进一步处理。
摘要：针对立体匹配中的边缘提取,本文提出一种简单而实用的改进方法。通过Canny算子检测最初的边缘,再利用几何信息选择关键点。根据关键点所确定的标记进行边缘连接,获得完整的边缘。该方法排除了孤立边缘、虚假边缘对边缘检测的影响,并通过引入直线分段法提取有用边缘,降低了算法的复杂度。实验结果表明,改进方法的边缘提取定位精确且连续性好,轮廓全面清晰,点、线特征突出,为立体匹配打下了良好的基础。
立体匹配 篇6
立体匹配是双目立体视觉系统中最重要也是最困难的一部分, 是三维重建的核心技术。立体匹配实际上是对左右两台摄像机从不同视点看同一景物, 在左右两幅图像重叠区域寻找对应点的过程。它利用空间物体点在左右摄像机中的成像模型来获取成像偏差的过程。按照约束方式的不同, 立体匹配算法可分为区域匹配算法和全局匹配算法。按照匹配基元的不同, 立体匹配算法分为基于区域的匹配算法、基于特征的匹配算法和基于相位的匹配算法[1]。然而, 基于区域的匹配算法对光照强度和对比度的变化非常敏感, 同时匹配窗口的选取也是一个难点, 当图像存在纹理特征重复和遮挡现象比较严重的情况下, 会引起匹配混淆, 错误匹配概率较高。基于全局的匹配算法, 如图割算法[2]、置信度扩展[3,4]和动态规划[5]等算法能够对整个图像进行有效的约束, 匹配结果也较局部匹配算法精确, 但是实时性不好, 匹配时间过长。
本文主要是针对局部匹配算法和全局匹配算法的缺点和不足, 采用了一种基于区域匹配与全局匹配算法相结合的算法, 来提高双目立体匹配的效率, 增强立体匹配算法的实时性。首先, 利用均值漂移算法[6]对左右两幅图像进行彩色图像分割, 再使用NCC相似度测量计算相关度, 得到初始匹配视差图;其次, 引入置信度的概念, 针对大的遮挡区域和低纹理区域中置信度低的区域, 取邻域相关系数最大的视差值;最后, 对边缘像素进行修正, 并对整个视差图进行滤波从而得到效果精确的视差图, 用来检验匹配算法的精确性。
2 基于均值漂移算法的彩色图像分割
在双目立体匹配中, 图像分割对获取视差平面方程有着重要作用。图像分割主要是根据图像中的颜色信息, 将颜色相同或者相似的相邻像素点划分为同一个区域, 从而将整幅图像分割成颜色相同或者近似的区域, 并将同一个区域内所有像素点的视差分布用某个视差平面方程来表示, 以此得到图像的视差图。Fukunaga[7]首先提出了均值漂移算法, Cheng[8]改进了均值漂移算法中的核函数和权重函数, 并将其应用于聚类和全局优化, 从而扩大了该算法的应用范围。近年来, 均值漂移算法也被广泛应用于图像分割和追踪等计算机视觉领域, 并取得了较好的效果。
均值漂移算法是结合图像像素点的颜色信息和周围空间的分布特性之间的关系, 沿着平均梯度方向找出每个像素点的相似颜色收敛点, 根据收敛点的不同而划分不同的区域, 从而实现图像分割。
改进的均值漂移定义如下:
其中, GH (xi-x) 为不同样本点ix到中心样本点x的不同距离对偏移向量的不同贡献而引入的核函数权值,
H为一个对角矩阵,
从而, (1) 式可以变为
G (x) 为核函数, 它决定了采样点ix与核中心x之间的相似性度量;本文采用单位高斯核函数, 令
前面 (5) 式可以变为如下,
Mh (x) 表示加权平均偏移向量, 指向概率密度梯度方向, 则mh (x) 可以看成是样本点x沿着概率密度梯度方向偏移后的样本点。在已知G (x) 和w (xi) 的情况下, 根据式 (8) 进行迭代会收敛到待漂移样本点附近的概率分布密度峰值处。迭代步骤如下:
(1) 首先, 在特征空间中任意选择初始搜索区域圆, 设置其搜索半径和误差阈值;
(2) 根据式 (8) 计算圆中采样点的均值mh (x) , 判断是否满足||mh (x) -x||<ξ, 则停止循环, 否则进入步骤3) ;
(3) 令x=mh (x) , 继续返回第一步开始循环。
采用均值漂移算法对图像进行分割之后的效果图如图1所示。
3 区域匹配
区域匹配算法主要是以一幅图像中某一个待匹配点的灰度邻域作为匹配模板, 然后在另外一幅待匹配的图像中搜索具有相似灰度值分布的对应点邻域, 从而完成两幅图像的匹配。区域匹配效率高, 而且实现也比较简单。但在匹配的过程中也需要考虑匹配窗口的大小, 而且搜索过程也需要满足一定的阈值条件。区域匹配中代价函数是用来计算图像间像素的相似性的测量函数。常用的代价函数主要有绝对灰度差和SAD (sum of absolute difference) , 归一化互相关NCC (normalized cross correlation) , 灰度平方差和SSD (sum of square difference) 等。
对于立体图像对, 假设I1和I2分别表示左右图像对的灰度函数, I1 (x, y) 和I2 (x, y) 分别表示左右图像坐标为 (x, y) 的像素点的灰度值, (x, y) 为左图像中心像素点, d表示该点的视差值, 那么, 上述相似性度量函数公式为:
绝对灰度差和S A D
归一化互相关N C C
灰度平方差和S S D
经过实验结果对比, 决定选用NCC作为区域匹配的测度函数。各代价函数求得的视察效果图如图2所示。
区域匹配中, 匹配窗口的大小难以选择, 所以本文采用自适应窗算法, 该算法详细步骤如下:
(1) 设定初始匹配窗口的大小为3*3;
(2) 将窗口的沿上、下、左、右四个方向分别向外扩展一个像素点的大小, 判断此时窗口内包含的像素点是否超过规定阈值, 若超过, 则停止, 否则继续执行下一步;
(3) 记录此时窗口的大小, 以左图像的该像素区域窗口作为模板, 在右图像中进行匹配, 记录此时得到的视差值为d1, 之后再以右图像的该像素区域窗口作为模板, 在左图像中进行匹配, 记录此时得到的视差值为d2;
(4) 比较d1和d2的大小, 若d1=-d2, 则记录此像素点视差值为d=d1, 否则令d=0。
4 置信播算法进行模板视差最优分配
通过区域匹配得到的视差平面模板不够精确, 只考虑了模板内像素点之间的影响, 而没有考虑到区域块间的相互影响。本文采用全局匹配算法—置信传播算法对初始视差平面模板进行全局优化, 从而得到更加精确稠密的视差图。置信传播算法主要是利用消息传输和置信度传输机制来实现全局能量函数的最小化的。
4.1 置信传播算法原理
将马尔科夫随机场应用于立体图像对中, 将立体图像对中的参考图看成是一个无向图V, 每个像素点看成一个节点X, 每个像素点的视差值看成是该像素点的状态, 即无向图的势函数, 建立图像的马尔科夫随机场模型。此时, 求取立体图像的最优视差分布即可看成是求马尔科夫随机场的最大概率分布。通过对立体匹配过程中不同区域视差规律的分析, 利用贝叶斯定理得到的马尔科夫随机场后验概率分布可简写为:
其中D为图像的视差分布, I为立体图像对, E为全局能量函数。
由 (12) 可知, 求取马尔科夫随机场的最大概率分布的过程即是求立体匹配全局能量函数最小化的过程。即求马尔科夫随机场分布最大后验概率就相当于通过置信传播算法求取图像的精确稠密视差图。采用置信传播算法就是采用消息传输机制实现置信度最大化, 即实现马尔科夫随机场最大概率分布, 即是实现全局能量函数的最小化。
定义全局能量函数为:
其中d表示整幅图像的视差分配, N表示图像中所有像素的四邻域点集, dp表示点p所分配的视差值, 平滑项V (dp, dq) 表示两相邻像素点p和点q分配视差dp和dq时的视差不连续惩罚量, P表示图像中像素点的集合, 数据项Dp (dp) 表示p点视差为dp时非相似性测度。若某个视差分配使该全局能量函数最小, 则该视差分配即为图像的最终视差图。
置信传播算法的消息迭代传输:
mtp→q (dq) 表示第t次迭代时点p传输给视差值为dp的邻域点q的消息, Ω表示视差搜索空间范围, N (p) 表示点p的四邻域集, N (p) q表示点p的三邻域集, 它不包括接收消息的点q。
经过T次迭代后, 消息传输趋于稳定, 此时可通过置信度传输计算图像中各个像素点的置信度, 计算点p置信度的公式为:
图中各个像素点的最佳视差可以通过最小化置信度获得, 计算点p的最佳视差d*p的公式为:
4.2 置信传播算法的改进
置信传播算法是在像素点之间的置信度传播, 图像中像素点多, 数量庞大, 也大大增加了算法计算量。而且图像中可能存在单个像素点畸变, 如果使用这些畸变像素点进行消息传输, 会大大降低算法的精度。
本文引入图像分割的思想, 采用基于分割区域之间的置信度传播, 用每个分割区域代替单个像素点, 显著提高了立体匹配的速度。
5 实验结果
本文实验所采用的立体图像对来自于美国Middlebury大学计算机视觉研究中心提供的立体图像数据库。其中主要对384x288的Tsukuba测试图像进行求取视差图的仿真实验。计算机硬件条件为:双核CPU, 主频为1.99GHz, 内存为2G。软件编译环境为VC2008和Matalb2008。本文采用BM (Block Matching) 、SGBM (Semi-global BM) 以及GC (Graph Cut) 算法求得的视差图分别与本文算法所求得的视差图效果以及时间上进行比较, 视差效果图对比如图3所示, 匹配耗费时间对比列于表1。BM、SGBM速度快, 但视差图效果不好, GC视差效果好, 但熬时多, 本文匹配算法结合各种匹配算法的优缺点, 在精度和速度之间进行权衡, 得出的视差图更加精确, 且速度与单独使用全局匹配算法—GC图割算法相比, 有了很大的提高。
6 结语
本文采用的是区域匹配与全局匹配相结合的立体匹配算法, 解决了区域匹配算法存在的一些问题, 如匹配窗口的大小难以选择、若左右两幅图像存在重复结构的纹理特征或者存在遮挡现象引起的匹配混淆等。采用改进的置信传播算法, 用分割的区域块代替原始的像素点之间的匹配计算, 减少了匹配所用的时间, 同时也可以得到精确稠密的视差图。
参考文献
[1]邓红梅, 吴四夫.基于相位相关算法的研究与实现.信息技术.2005 (4) :19-20.
[2]Pedro F.Felzenszwalb, Ramin Zabih, Dynamic Programmingand Graph Cut Algorithms in Computer Vision[J].In IEEE Trans-actions on Pattern Analysis and Machine.Intelligence, 2011:721-740.
[3]Q.Yang, L.Wang, R.Yang, H.Stewenius, and D.Nister“, Stereomatching with color-weighted correlation, hierarchical beliefpropagation, and occlusion handling, ”[J].IEEE Transactions onPattern Analysis and Machine Intelligence, 2008 (31) :492-504.
[4]Klaus, A.Sormann, M.Karner, K.Segment-Based Stereo Match-ing Using Belief Propagation and a Self-Adapting DissimilarityMeasure.Pattern Recognition, 2006.ICPR2006.18th Interna-tional Conference, 2006:15-18.
[5]Y.Deng.X.Lin“.A fast line segment based dense stereo algo-rithm using tree dynamic programming”[J].In ECCV, 2006:201-212.
[6]Comaniciu D, Meer P.Mean shift analysis and applications[C].International Conference on Computer Vision, 1999:1197-1203.
[7]Fukunaga K, Hostetler L D.The estimation of the gradient ofa density function with applications in pattern recognition[J].IEEE Trans on Information Theory, 1975, 21 (1) :32-40
[8]Cheng Y Z.Mean shift, mode seeking, and clustering[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 1995, 17 (8) :790-799.
立体匹配 篇7
对应基元的立体匹配是立体视觉的关键技术,也是近年来计算机视觉领域研究的重点和难点。基于灰度(区域)的匹配方法研究开展地较早,由于借助于窗口区域中像素灰度的统计特性进行对应匹配[1,2],这类匹配方法对图像的旋转以及光强和对比度的变化等非常敏感,而图像灰度值的统计相关计算量较大也导致其存在处理速度较慢的问题。与基于灰度的匹配方法不同,基于特征的匹配方法是有选择地匹配能表示景物自身特性的特征,通过更多地强调空间景物的结构信息来解决匹配歧义性问题。近年来,基于特征的匹配在目标识别、视觉导航、运动分析等领域得到了广泛关注。
目前,用于匹配的特征主要有点特征、线特征和区域特征等。角点是最基本的特征基元,具有较高的定位精度和较好的匹配鲁棒性,但角点特征所含图像信息较少,在图像中的数目较多,因而在匹配时需要较强的约束准则和匹配策略,以克服歧义匹配和提高运算效率。文献[3]中利用灰度相关计算确定初始匹配点对,通过松弛法建立两幅图像的基本矩阵,并利用极线约束在两幅图像中寻找更多的匹配点对。文献[4]中将序列图像角点之间形成的角度作为匹配度的衡量标准,结合灰度相关计算进行角点匹配,能够获得较高的正确匹配率。与点特征相比,表现为图像边缘特征的线特征更能体现图像景物信息,更利于三维结构重建及三维目标识别,利用边缘特征作为匹配基元也能有效提高匹配速度。文献[5]中将边缘进行直线拟合后作为匹配基元,利用极线约束,通过直线方向特征、长度特征和灰度相关特征由匹配窗口实现立体匹配,文献[6]中利用Hough变换,将线匹配转化为点匹配,以确定左右图像的线特征对应关系。这两种方法由于待匹配边缘需满足特殊的直线几何特性,具有一定的局限性。文献[7]中根据边缘的首末端点和长度,利用极线约束进行边缘匹配,由于用到了边缘的端点、长度信息,该方法对噪声比较敏感,在提取的边缘端点或长度出现一定偏差时,将导致无法匹配。文献[8]中根据图像中边缘线段之间的连接关系建立匹配约束,减少匹配时搜索空间,以提高匹配精度和速度,该方法需对边缘进行直线或二次曲线拟合,所匹配的边缘必须互相连接,而使其应用受到一定限制。与线特征相比,区域特征更能体现图像中景物的全局信息,由于区域特征的立体匹配依赖于左右图像的分割区域,在对人工场景(如建筑物、室内场景)这类分割区域明显、区域变形较小的图像进行处理时,区域特征匹配能够获得较好效果[9,10],而当左右图像分割区域存在差异时,只利用区域特性进行匹配的方法会受到一定影响。
考虑到以上各类特征匹配方法的特点,本文针对自然场景图像,提出一种基于区域邻接图的快速边缘匹配算法。算法通过分水岭变换完成图像分割,根据区域边界确定图像中景物的轮廓边缘;图像边缘按所属区域进行分组,根据区域邻接图,在区域特性及边缘特征角点的约束下,采用类似区域生长的匹配策略完成边缘匹配;进而以已匹配的边缘特征角点为基准点,在其引导下实现其他边缘点的立体匹配。算法由于引入新的区域约束和边缘约束,有效减少了边缘点匹配搜索空间,而所采用的基于区域邻接图的类似区域生长的边缘匹配策略,则进一步保证了匹配的快速性和正确性。
2 基于分水岭变换的轮廓边缘提取
边缘是图像的重要特征,其能够体现图像中景物的形状轮廓信息,而大大减少所要处理的信息量。传统经典的边缘检测方法利用相邻区域像素灰度值不连续的性质,采用一阶或二阶导数来确定边缘像素点,如Sobel算子、Canny算子等。传统方法对阶跃边缘进行检测能够获得较好的效果,但由于其对噪声和细小纹理十分敏感,在对复杂图像直接进行边缘检测时,往往会受到局部细节的干扰,而无法提取出体现景物结构特征的轮廓边缘信息,造成特征信息的冗余和不稳定,影响后续的重建和识别工作。如图1中所示,采用Canny算子直接对山体模型图像进行边缘提取,得到的边缘(如图1(b))琐碎凌乱,不但难以体现山体的轮廓信息,而且也很难按照一定的数据结构归类管理进行后续立体匹配。
针对上述问题,本文从视觉感知的角度出发,采用由全局到局部的分层信息获取方式实现图像景物轮廓特征提取。首先进行图像分割,将复杂的目标图像分割成为一系列反映目标基本结构特征的简单区域,具体采用具有区域边界封闭、全局区域边缘定位特点的分水岭变换算法实现[11]。由于分水岭变换通常存在过分割现象,需要对初步分割区域进行合并,对于尺寸较大的图像,本文采用降低图像分辨率后再进行图像分割的思想,在强调图像全局特征信息的同时,降低过分割程度,提高图像分割速度。在完成低分辨率图像分水岭变换图像分割的基础上,利用Canny算子所采用的非极大点抑制和双阈值控制的方法,对原图像中区域边界进行细化,得到最终的单像素轮廓边缘。图1(c)是采用上述方法所获得的山体图像轮廓边缘,与Canny算子边缘相比,其数量少,具有更好的连续性和完整性,能够较好地体现景物的轮廓信息。
3 立体匹配算法
立体匹配的目的是寻求同一空间景物在不同视点下投影图像像素间的一一对应关系,常用的匹配约束有极线约束、唯一性约束、顺序约束等。单个特征点匹配时,在常规约束下往往会遇到左图像一点在右图像中有若干对应的问题,离散的单个特征点也容易受图像噪声等因素影响,搜索空间过大会直接影响立体匹配的精度和速度。因此,减少立体匹配搜索空间、建立新的匹配约束是改进立体匹配算法的重点,本文则以此为出发点,结合之前提取的轮廓边缘所具有的特性,基于由全局到局部、自上而下的分层匹配思想,提出一种新的快速立体匹配算法。该算法分为以下区域边缘匹配和边缘点匹配两个步骤。
3.1 区域边缘立体匹配
通过图像分割提取的轮廓边缘属于区域边界,常规的匹配思路是以两两区域之间的边界线为单位,将闭合的区域边界按分段边缘的数据结构形式进行匹配。而由于不同视点的成像差异会使左右图像分割区域通常并不严格对应,区域之间的边界线也很难一一对应,往往是左图像中一条边缘的一部分和右图像中一条边缘的其中一部分对应,出现交叉对应的复杂情况。若以分段边缘线为匹配基元,在一定程度上会造成部分边缘的丢失,而对过多的边缘线进行匹配也相对更为耗时。为此,本文以分割区域为单位,选择区域的闭合边界线(称为区域边缘)作为匹配基元进行立体匹配。匹配之前采用Harris角点探测算法[12]在轮廓边缘上提取特征角点,作为参照点。立体匹配过程首先根据区域的位置、尺寸和灰度特征建立区域约束,进而依靠区域边缘上的角点特征,根据角点匹配结果确定最终区域边缘匹配结果。
由于边界具有同时属于相邻的两个区域的特点,区域边缘能够反映图像中各分割区域的相互连接状况,反之我们也能根据区域的邻接关系来指导边缘匹配,以确定合适的匹配顺序。图像分割区域的邻接关系通常采用区域邻接图(Region Adjacency Graph,RAG)[13]的数据结构形式进行描述,如图2(a)立体图像对中分割区域的邻接关系可用图2(b)所示的RAG表示。这里定义的RAG为无向图,可具体表示为G=(V,E),其中V={v1,v2,…,vk}表示k个顶点(vertex),每个顶点代表一个区域;E⊂V×V表示RAG每条边(edge),每条边连接相邻的两个区域,代表区域之间的共有边缘。根据RAG定义,区域边缘可表示为:REi={(vi,vj)},(vi,vj)∈E,其中i,j为区域标号,i,j∈{1,2,…,k}。根据边界的共有性,(vi,vj)=(vj,vi)=REi∩REj,当区域边缘REi完成匹配的同时也确定了区域边缘REj的部分匹配,由此进而即可进行REj的匹配,以确保匹配的有效性、减少匹配搜索空间。结合图2所示的立体图像对,基于RAG的区域边缘匹配具体过程如下:
1)计算左右图像中区域重心位置、面积和灰度均值,建立区域约束,并创建待匹配区域边缘对堆栈。
2)按照边缘所属区域的序号顺序搜寻第一对待匹配区域边缘。设当前进行匹配的左右图像区域边缘为RELi和RERj,若RELi和RERj所属区域vLi和vRj满足区域约束,即二者的重心位置、面积和灰度均值之差都在一定阈值内,则转3);否则转2),继续匹配下一对区域边缘。
3)采用灰度相关和极线约束[3]对RELi和RERj的特征角点进行立体匹配,若存在匹配特征角点,则将待匹配区域边缘对RELi和RERj入栈,同时结束第一对待匹配区域边缘的搜索,转4);若不存在匹配特征角点,则转2),继续匹配下一对区域边缘。
4)对待匹配区域边缘堆栈进行出栈入栈操作,进行区域边缘及其特征角点立体匹配。弹出位于栈顶的待匹配区域边缘对RELi和RERj,对该对区域边缘的所有特征角点进行匹配,若存在匹配特征角点则表示该对区域边缘相互匹配,记录其匹配的各对特征角点,并根据角点同时所属的邻接区域边缘确定新的待匹配边缘对,若其满足区域约束,则将新的待匹配区域边缘对入栈。如图2中所示,设当前匹配边缘为REL1和RER1,若在其边缘(vL1,vL2)和(vR1,vR2)上存在匹配角点对且满足区域约束时,则将REL2和RER2作为待匹配区域边缘对入栈,同理,在匹配REL1和RER1时,根据RAG中区域的邻接关系,REL4和RER3,REL6和RER5也可能入栈。
5)若堆栈中还有待匹配区域,则转4);否则结束堆栈操作,最终确定区域边缘匹配结果及其特征角点的匹配结果。
由以上匹配步骤可知,区域边缘的匹配实质就是左右图像RAG顶点的匹配过程,轮廓边缘以区域为单位作为匹配基元会形成数据重叠,即同一段边缘将会出现在两个区域边缘数据中,因此在进行匹配时需建立标记数组,记录已经匹配过的特征,避免出现重复匹配操作。
由于该匹配方法依赖于图像分割结果,而不同视点成像图像的分割区域很难一一对应,特别是当不同视点摄像机光轴交角较大时,左右图像的分割区域之间可能会出现一对几或几对一的情况,甚至出现部分区域交错对应,因此从局部角度来看,单个区域边缘匹配后可能会出现部分边缘点无法对应的情况,例如在图2左图像中区域vL4对应的是右图像中vR3和vR6两个区域,区域边缘REL4和RER3匹配,而由于受到区域面积约束REL4和RER6无法匹配,造成二者相应边缘点无法对应。但从全局角度来看,边界的区域共有特性所引起的区域边缘部分信息重叠,能够解决部分边缘在局部区域边缘匹配时无法对应的问题,例如图2中REL4和RER6无法匹配的部分边缘在区域边缘REL6和RER5、REL7和RER7匹配时即可确定对应关系。由此可见,边缘按区域分组进行匹配不但能够根据区域约束及其邻接关系提高匹配速度,同时也能提高匹配的鲁棒性,保证匹配边缘的完整性。
3.2 边缘点立体匹配
由于轮廓边缘是任意曲线段,无法通过简单插值运算计算边缘的三维信息,因此在完成轮廓边缘匹配后,需对边缘上各像素点进行进一步立体匹配,以便按像素点逐一进行三维重建。区域边缘的匹配结果为边缘点匹配建立了边缘约束,在此基础上可将已经匹配的特征角点作为基准点,根据连续性约束逐步对各基准角点之间的边缘像素点进行立体匹配。设当前匹配的是边缘RELi和RERj上的像素点,mcLx和mcRy为其中一对已匹配的特征角点,下标x和y表示特征角点在边缘点数组中的序号,匹配时以点mcLx为基准,其相邻点mcL(x-1)(或者mcL(x+1))在右图像中所对应的边缘点应在点mcRy的邻域内,即可将对应点搜索区域限制在{mcR(y-n),…,mcR(y+n)}几个像素点内,偏移量n用来控制待匹配点邻域区域的大小。通过边缘约束大大降低边缘点匹配搜索空间后,利用极线约束和灰度相关约束即可快速完成左右图像轮廓边缘点的立体匹配。
4 实验结果
为验证算法,采用两个CCD建立双目立体视觉测量系统对山体模型进行拍摄,两个摄像机光轴夹角为8.1°,基线距为82.1 mm,镜头都为12 mm,获取立体图像对如图3(a)所示。采用本文算法进行轮廓边缘提取和立体匹配的结果如图3(b)、(c)所示,图中匹配边缘点用黑色表示,其中匹配的区域边缘数为31对,错误匹配为2对,匹配正确率能达到93.5%。匹配的边缘点总数为5 402,正确匹配点数目对为5 127,匹配正确率为94.9%。实验数据是在P4 2.4 GHz微型计算机上VC 6.0的实验环境中获得的,立体匹配过程耗时1.073 s,立体匹配速度较快。
针对人工场景,采用本文算法也进行了相应实验,对Middlebury大学图像库的Tsukuba图像进行立体匹配结果如图4所示,图中匹配边缘点用白色表示。其中匹配区域边缘数为52对,由于立体图像对是利用平行光轴系统获得的,左右图像之间除存在平移外,其他差别很小,区域边缘无误匹配出现。匹配边缘点总数为4 381,正确匹配点数目对为4 247,匹配正确率为96.9%,匹配过程耗时0.701 s。由实验结果可见,对于区域和边缘特征明显的图像,当左右图像差异不大时,本文立体匹配算法能得到更好的处理效果。表1中列出了以上实验的详细数据。
5 结论