８２ 福建电脑 ２０１０年第３期
基于区域生长的时间规整立体匹配算法
傅青山．雷仲魁
（南京航空航天大学无人机学院江苏南京２１００００ １
【摘要】：针对立体匹配过程中存在的不确定性和模糊性，本文提出先利用匹配的边缘特征点对极线进行初分割。然
后利用区域生长算法进行颜色分段，在颜色段的基础上进行时间规整的立体匹配算法。根据外板线约束，在视差范围窗口内 采用颜色相似极大得到长度不相等的两个像素段作为相容的匹配序列．利用动态规划方法及连续性约束寻找一条最佳的匹
配路径，根据回溯得到匹配路径及其坐标值得到高密度视差图。实验结果表明该算法具有良好的匹配效果。
【关键词】：区域生长；立体匹配；ＤＷＴ；动态规划
引言 立体匹配问题是计算机视觉研究的热点问题之一．它是利
用计算机来模仿人类通过眼睛线索感知距离的一种方法 其中 关键的一点是解决图像上的视差计算问题．以此来恢复点的三
维坐标．进而试图重建物体的三维表面信息。目前所采用的立体 匹配方法大致可以分为两类：（１）基于区域灰度相关性的方法ｎ１
『２１，该方法可以得到稠密的视差图，但是其匹配的精确度要受到
窗口大小、纹理和光照反射的影响，而且具有可观的时间复杂 度；ｆ２）基于图像特征的匹配『３１ ，该方法更多地强调利用空间景
物的结构信息来解决匹配的歧义性．匹配特征主要为线状特征、
角特征、区域特征等．该方法只能得到稀疏可靠的视差图。动态 规划法在立体匹配中得到了普遍的应用，文献『５惨考了语音信 号处理中的时问规整算法（Ｄｙｎａｍｉｃ Ｔｉｍｅ Ｗａｒｐｉｎｇ，ＤＴＷ），以灰
度段作为匹配的基元．算法简便．利于匹配．但其灰度分段在遮 挡、光照不均和畸变的情况下会产生误分段；文献ｆ６１采用一种模
糊逻辑的方法先是进行边缘点的检测．把极线上边缘点之间的 像素都划分为一个段．然后做左右图像相容段上像素的匹配．这
样特征点匹配的准确性对整个视差图的准确性起着至关重要的
作用，且在噪声、遮挡及透视等因素影响比较严重的情况下，特 征点的精确匹配会受到干扰；文献『７１提出一种基于自适应窗口
的时间规整算法．但是没有利用像素的彩色信息和梯度信息．而 且也只是采用效果不好的比较灰度大小来分段 Ｋｏｓｃｈａｎ和
Ｒｏｄｅｈｏｒｓｔ（１９９７）认为用彩色信息代替灰度信息．立体匹配结果的 准备率能够提高２０％一２５％。为了得到精确度更高的视差图．本
文提出一种基于区域生长的时间规整立体匹配算法．先用边缘 点对极线初分段．再把待匹配图像的边缘点分段结果用区域生
长方法分割为大小不等的匹配区域序列．类似于待匹配的模板。
在图像对中的另一幅图像的视差范围的窗口中利用区域生长方 法生成若干个匹配序列．再利用颜色极小选择最佳的匹配序列．
以此两个区域作为匹配基元．再利用Ｄ 算法对匹配序列进行
基于动态规划的整体匹配。 １、区域生长方法的匹配序列划分与获取 本文基于颜色段的立体匹配算法．是将图像对中对应极线
上的图像信息按颜色信息进行分段．以颜色段作为匹配基元．利
用Ｄ聊（ｄｙｎａｍｉｃ ｔｉｍｅ ｗａｍｉｎｇ）方法进行匹配 以颜色段作为匹
配基元比点基元覆盖的图像空问要大．可以减少误匹配发生的
几率，更容易进行匹配．而且这种方法比基于特征线段、二次曲 线或任意平面代数曲线的方法计算起来要简便得多。我们希望
能够得到图像对中视差值比较相近的区域来进行匹配．这两个
区域可以称之为左右”匹配序列”。因为存在遮挡的问题，所以左
右匹配序列的尺寸并不一定相同．不可能也不应该试图找到大
小全部相等的匹配序列区域 本文算法的设计和实现遵循如下
视觉理论的约束条件：外极线约束；匹配惟一性约束；视差连续 性约束。
考虑二种得到匹配序列的方法：ｆ１１利用像素点的灰度信息
与灰度均值的差小于设定阈值的方法对图像的像素行进行分 段；（２）通过基于特征的边界检测来确定匹配序列。文献『６１首先
获得边缘特征点的视差，然后在这些特征点视差图的约束下．对 非特征点利用灰度大小进行分段。既缩小了匹配空间．又保证了 匹配的相对准确性，获得了较好的效果，但带来的问题是．由于 特征点的视差图对整个视差图的准确性起着至关重要的作用。
且在噪声、遮挡及透视等因素影响比较严重的情况下．特征点的 精确匹配会受到干扰。文献『７１设定自适应窗口，但是没有利用颜
色信息，也只是利用灰度信息进行分段．相比来说没有利用颜色
信息的区域生长的分段方法对极线的分割效果好 １．１边缘特征点匹配
边缘特征点的匹配就是要找到一幅图像中某一扫描线上的
某个边缘特征点在另一幅图像中的对应边缘特征点．但由于在 外极线的约束下．在另一幅图像中相应扫描线上．仍然存在多个
可能匹配的边缘点．因而匹配过程具有不确定性和模糊性 匹配 之前先要进行边缘特征点的检测．按照图像边缘检测所利用的
图像信息，边缘检测方法可分为两大类：基于梯度信息的图像边
缘检测和基于相位信息的图像边缘检测 相位检测计算复杂度 比较高，实时性不好：灰度梯度信息对图像中大量的噪声非常敏
感，且随着图像的对比度和亮度的改变而发生改变。我们采用 Ｃａｎｎｖ算子，同时加入色彩梯度信息，检测的准确率得到很大提
高。 我们定义颜色梯度如下：
一８ｆ（ｘ．ｙ）
８ｘ ８ｘ＋Ｊ８ｘ Ｉ＋８ｘ ｌ Ｉ Ｉ Ｉ Ｉ
＿＋ｌ＋ＩｌＩ Ｉ Ｉ Ｉ ｌ
像素总的颜色梯度可以定义为：
（ ，Ｙ）＝ （２）
（３）
我们采用经典的Ｃａｎｎｖ算子提取图像对的色彩边缘特征．
以边缘点的色彩梯度大小、方向、边缘点的色彩梯度大小相关系
数以及边缘点的颜色相关系数等４个因素作为边缘点相似性的
度量要素。然后我们利用文献『６１的方法采用模糊理论来解决边
缘点的匹配问题．它的出发点正在于能有效地处理这种不确定
性问题的模糊性 １．２极线分段 在文献［８］ｅＯＮ出了所有的１２种颜色相似度计算方法．所有
的计算方法都输入两个矢量，计算得到一个在【Ｏ．０，１．Ｏ】之间的结
果．１．Ｏ表示两种颜色完全相同．０．０表示两种颜色完全不相同。
『９１对这１２种方法进行了对比实验，证明了绝对值指数方法是最 优的。绝对值指数方法定义如下： 厂 ｐ 、 （ ， ）＝ｅｘｐＩ一 ∑ 一 ＩＪ ｆ４）
２０１０年第３期 福建 电脑 ８３
和 是两个Ｐ维颜色矢量，在ＲＧＢ颜色空间中每个点的
颜色由红绿蓝三个元素的矢量表示，所以ｐ＝ ５ ，是颜色相
似度，其中ｆｌ＞Ｏ。为了减小计算的复杂度，而且不影响计算结果，
本文中我们对绝对值指数方法进行一些改变。直接用绝对值差
的和来表征两个像素颜色的相似性。即：
（ ， ）： 』 一 ｆ （５）
ｌ 区域生长方法［１Ｏｌ将图像以像素为基本单位来进行操作。分
割步骤如下：
１、对图像进行逐行扫描，找出尚没有归属的像素；
２、以该像素为中心检查它的领域像素，即将领域中的像素 逐个与它比较，如果颜色差小于预先确定的阈值，将它们合并；
３、以新合并的像素为中心。返回到步骤２，检查新像素的领
域。直到区域不能进一步扩张； 返回到步骤１．继续扫描直到不能发现没有归属的像素．刚
结束整个生长过程
采用上述方法得到的结果对区域生长起点的选择有较大的
依赖性。为了克服这个问题可以我们采用下面的改进方法： １、设颜色差的阈值为Ｏ，用上述方法进行区域扩张，使颜色
相同像素合并： ２、求出所有领接区域之间的平均颜色差．并合具有最小颜
色差的邻接区域： ３、设定终止准则．通过反复进行上述步骤２中的操作将区
域依次合并直到终止准则满足为止。
另外．当图像中存在缓慢变化的区域时．上述方法有可能将 不同区域逐步合并而产生错误．为了克服这个问题．不用新像素
的颜色值去与领域像素的颜色值比较．而用新像素所在区域的 平均颜色去与各个领域像素的颜色进行比较。
在实际应用区域生长方法时需要解决３个问题：选择或确
定一组能正确代表所需区域的种子像素：确定在生长过程中能 将相邻像素包括进来的准则：制定让生长过程停止的条件或准 则。图像经过边缘特征点匹配后，得到图像极线各线段的的大体
分布．可以利用代表各线段分布的边界信息自动获得种子点。同
时这些边界点还可以作为生长停止的约束条件为生长过程提供
潜在的线段模型。具体的生长过程如下：（１）对应用边缘特征匹 配后的图像进行标记．取同一极线上两个边缘点的中心为种子
点，计算该种子点与其左右像素（ｘ，ｙ）的颜色距离，如果该距离小
于阈值Ｔ且生长还未到该线段的边界．则使其与种子点相同．同 时将（ｘ，ｖ）压人堆栈：（２）从堆栈中取出１个像素，把它当作种子
点．重复步骤（１），直到堆栈为空时，该区域生长过程结束。阈值
Ｔ的选择则与种子点的选择有关．以每个线段的种子点为中心 取一个小窗口．窗口的大小可调．分别计算窗口中像素点与中心
像素点的颜色距离。统计最大颜色距离值和方差，阈值则为最大
颜色距离值与方差之差 每两个边缘点中问一次生长后剩下的 部分再用其中心点作种子点生长出新的线段。
１＿３匹配序列获取 对右目图像某一极线进行分割后．接下来在左目图像对应
极线上寻找像素段的相容匹配区域。设矢量ｆ（ｘ，ｙ】是右目图像ｆｘ， ｖ１点处的ＲＧＢ矢量，即：
／（ ）＝（ （ ），厂Ｇ（ ）， （ ）） （６）
Ｒ＝｛ｆ ． ．． ｌ为右目图像某一极线上分割出的一个颜色
段．设匹配最大视差为ｄ．在左目图像中定义窗Ｉ：１ Ｌ＝
（《 十ｐ…，ｅ＋ｍ，…，ｅ＋ｍ ），所以与右图像中Ｒ颜色段相容的左图像中
的匹配序列一定是Ｌ的一个子集。我们同样对Ｌ进行区域生长分
割，得到几个颜色段，记为 ，ｋ就是与Ｒ相容的匹配序列的候选
序列族。我们取Ｌ，中与Ｒ最相关的序列就是与Ｒ相容的匹配序列。
相容匹配序列的方法通过段之间的颜色相似性来进行。 最相关序列Ｌ由（Ｌ＝ｍｉｎ ｌｌ Ｓ（ —Ｒ）：ＩＩ，ｋ＝Ｏ，１，…．Ｋ）确定。
有的图形利用边缘特征点分出来的段在某一区域都是像素很少
的段．在这种情况我们就要先进行段的合并，保证段在某一长度
之内。 ２、基于ＤＷＴ的颜色段匹配
得到了右图像中的序列Ｒ和它在左图像上的相容序列Ｌ．
我们利用ＤＷＴ算法对这两个序列进行匹配。对右图像中极线上
的所有分割．首先我们选取长度最长的段先进行匹配．这样做不 仅可以尽可能地避免匹配过程中的遮挡情况．而且可以缩小剩
余段的匹配搜索范围．剩余段的匹配在该段的左、右部分分别进
行。也同样先选长度最长的段进行匹配，像这样一直循环下去．
直到所有颜色段都完成匹配过程为止 为了使颜色段的匹配达到最佳效果．本文采用ＤＴＷ算法．
其核心思想是对匹配过程进行动态规划。设一个二维直角匹配
坐标系，把右匹配序列Ｒ作为横坐标，坐标范围为ｆ０，…，Ｍ）；把 左匹配序列Ｌ作为纵坐标，坐标范围为（０，…，Ｎ）。横坐标和纵坐
标上各点所组成的网格中．每一个交叉点表示左右匹配序列中
可能匹配的一个点对ｆｍ，ｎ）。ＤＰ算法可以归结为寻找一条通过此 网格中若干匹配交叉点的连续的路径。路径不是随意选择的．根
据约束条件中的连续性原则．匹配序列内各点的先后次序不必
改变．因此所选的路径必定从左下角某点出发．在右上角某点结 束
在使用Ｄ咧算法进行匹配之前．我们要定义两个像素点的 失真距离，失真距离越小颜色相似度就越高。设和分别是Ｒ和
Ｌ上的两个像素．根据（５）式，这两个像素的失真距离可以计算
为： Ｄ（Ａ一 ）＝∑Ｉ 一 Ｉ （７）
为了减少时问复杂度．防止过多地搜索匹配概率不大的路
径．可以对路径中各点的斜率的最大和最小值给以限制．另外．
左右两上匹配序列是通过区域生长得到的．不能保证匹配的起 点和终点为固定点．所以无论是起点还是终点都采用松驰点．可
以进一步克服不精确造成的误匹配，但是也增加了计算开销。 这样．求最佳匹配的ＤＰ算法可以归结为求～个最佳匹配
路Ｐ．使得沿匹配路径Ｐ的积累失真距离达到最小值，为了方便
表达，这里使用坐标ｆｍ，ｎ】来代表Ｒ和Ｌ的匹配关系，使用距离ｄ （ｍ，ｎ）来代表失失真距离，为了满足路径的斜率在一个小的范围
内。如果路径已经通过了ｆｍｉ一１＇ｎｉ—１）匹配点，那么下一个匹配点
（ｍｉ．ｈｉ）可以是下列三种情况之一：
（ｍ，， ）＝（” Ｈ＋１， 一 ）
（ｍ１．，Ｈｉ￣）＝（ 十１， ＋１）
（ ，， ）＝（ｍＨ， 一 ＋１） （８）
易证明．限定范围内的任一匹配点只可能有一条搜索路径 通过，通过该点的最佳路径与以后的路径无关，那么，若匹配路
径Ｐ通过节点通过（ｍ ，ｎ．．．），并延伸到下一节点（１２１ ，ｎｉ），则此路
径的累积失真表示为ａ（ｍ ｎ）＝ｄ Ｃｍ． ）＋ａ（ｍ ，ｎ．．．），这样动态规
划的基本运算可以归结为：
Ｉ （ ，， 一。）＋ （ ，ＦｌＩ．）
（ ，ｎｉ）＝ｍｉＩｌ｛ （ Ｈ， 一。）＋２ｄ（ｍｉ，ｎ￣＿ｔ） （９）
Ｉ （ ）＋ （ ，ｎｉ＿ ）
最后得到的匹配路径Ｐ的总的失真距离为：
Ｄ（ ）＝ （ ），ｋ＝ｍａｘ（Ｍ，Ⅳ）（１０）
搜索到ｒｍｂ 时，已经生成并保留一条最佳路径，通过逐点
向前回溯，可以求得整条路径Ｐ，回溯的起点即（下转第８６页）