的点即确定了扫描线上特征点的最佳匹配关系。
在具体的匹配过程中，可以引入根据顺序一致性约束条
件，该条件限制了相关系数平面中匹配路径的走向只能在０。 ～９０。的范围内，将上式进一步简化为：
Ｖ（ｚ，ｓ）一ｍａｘＥＶ（ｘ一１，５），Ｖ（ｚ一１，ｓ一１），
ｙ（ｚ，ｓ一１），Ｖ（ｚ，ｓ一１）ｌ＋Ｃ（ｘ，５）
（８）
计算机测量与控制·２。譬’１６（９）１３３２
． · ．·
文章编号：１６７１—４５９８ Ｃ２００８１０９—１３３２—０３
Ｃｏｍｐｕｔｅｒ Ｍｅａｓｕｒｅｍｅｎｔ ＆ ＣｏｎｔｒｏＩＩ
中圈分类号：ＴＰ３０１．６
文献标识码：Ｂ
ｒ磊ｉ手ＦＩ三丽 Ｉ瞒，．１似，·ｏ Ｉ
基于双目视觉的深度图立体匹配算法研究改进
在区域相关匹配的基础上，这里引入动态规划技术来选择 最优的匹配点。由于用来匹配的图像对事先已经进行外极线校 正，所有外极线等同于水平扫描线，所以匹配点只在对应的扫 描线上寻找，依次对每条水平扫描线上的像点进行匹配。对于 某一条扫描线（如第Ｙ条），取右图扫描线为视差空间图的垂 直坐标轴，取左图扫描线为水平坐标轴，图中位于坐标（ｚ， ｓ）的值等于右图像位于（ｚ，ｙ）的特征点与左图像（ｓ，ｙ） 处的特征点的支持窗口之间的区域相关值，描述右图特征点 （ｚ，ｙ）与左图特征点（ｓ，ｙ）相匹配的程度。在选定视差搜 索范围。一ｄ后，根据前面区域相关匹配的结果，若匹配时采 用的两幅图像宽度均为Ｎ，则每一条扫描线上所有特征点的 相关值构成一个Ｎ×Ｎ矩阵，所以视差空间图像平面也叫相 关系数矩阵平面。由于有视差搜索空间限制，该矩阵中也仅有 有限个元素值不为零。
（ｂ）７ ｘ７窗口 图４互相荧算法
（ｃ）９ ｘ９窗口
４．２引入改进动态规划的匹配算法实验 本实验所用的匹配源图像是立体匹配标准测试图像对，标
准测试图像选用Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｓｕｋｕｂａ提供的Ｔｓｕｋｕｂａ图像对 和Ｒ．Ｓｚｅｌｉｓｋｉ ａｎｄ Ｒ．Ｚａｂｉｈ提供的Ｍａｐ图像，实验结果如图 ５所示。
立体匹配的过程大体可分为３步；确定匹配基元，定义测 度函数，选择搜索策略。根据匹配基元的不同，立体匹配算法 分为３类：区域匹配、特征匹配和相位匹配。
２ 区域相关立体匹配算法 ２．１基本区域相关匹配算法
区域相关匹配算法［１１是一种经典的立体匹配算法，它可以 得到稠密的视差图。因为单个像紊的灰度不能够提供足够的信 息，所以该算法先以基准图中一个像素点为中心创建一个邻域 支持窗口，用邻域像素的灰度值分布来表征该像素，然后从待 匹配图中寻找这么一个像素，以其为中心创建同样的一个窗 口，使其邻域像素的灰度值分布与前者的相似性必须满足一定 的阈值条件。对于己经进行外极线校正的立体图像对，可以认 为匹配的对应点在图像的同一行上，如图１所示。
对于左图像中点Ｉｌ（ｚ，ｙ），可以从右图中同一水平扫描 线上搜索其匹配点。这之前，我们首先要定义描述两个窗口灰 度分布差异的灰度相关测度函数，当两个窗口包含的灰度信息
收稿日期：２００８—０５—０８；修回日期：２００８—０６—１０。 作者简介：周亦鸱（１９６９一），男，博士，主要从事计算机图像视觉处 理、图像算法、交通运输规划及安全方向的研究．
周亦鹏
（西北工业大学自动化学院，陕西西安７１００６８）
摘要：双目立体视觉可以直接模仿人眼与人类视觉的立体感知过程，是计算机视觉研究的核心课题之一。文章主要针对图像的立体 匹配算法研究，对区域相关算法进行了分析。在传统的ＮＣＣ基本灰度相关度测度函数的基础上，将动态规划优化理论引入到匹配中，提 高了匹配的速度和准确度。实验表明．本文算法能够满足目标跟踪试验要求，具有重要的理论意义和较高的实用价值。
Ｙ，ｄ），把
了丽一丽矗面而。圣娶－（ｘ－ｋ ｉ，ｙ＋川６）
Ｉｚ（ｚ＋ｄ，ｙ）一
—（２—ｊ二＿若生丽∑ Ｊ。（ｚ＋ｆｄ，ｙ＋歹）代ｍ（２ｎ ＋１）
＋１）ｆ幺，笪“～”一……“。
人ＣＯＴ，＇（ｚ，ｙ，ｄ）整理简化后的结果为：
ｃｏｖ（ｘ，ｙ，ｄ）一∑∑［Ｊ，（ｚ＋ｆ，，＋Ｊ）·Ｊ２（ｚ＋ｉ＋ｄ，ｙ＋』ห้องสมุดไป่ตู้一
ｍｒ（ｚ，Ｙ，Ｉ，）ｉ＝…∑一∑“［Ｊ，（ｚ＋ｆ，，＋ｊ）一ｉ百丽］２（４） ｍｒ（ｘ－－［－ｄ，Ｙ，Ｉｚ…）；一一∑≈∑［Ｊ。（ｚ＋ｉ＋ｄ，ｙ＋ｊ）一瓦ｉｉＦ丽］２
（５）
从上式可以看出，该函数的计算量相当大，但是在窗口移
动过程中存在很多重复计算，所以对上式我们可以进行一定的
简化。通过以下途径可以提高相关计算速度。计算ｃｏ”（ｚ，
（２ｍ＋ｉ１＝－）ｍ（ｉ２一ｎ＋１）１１石Ｉｙ）·五（至—千砑］
３基于动态规划的全局最优搜索策略
３．１动态规划简介 动态规划［４３是解决多阶段决策最优化问题的方法。利用最
优化原理求解多阶段决策最优化的过程，称为动态规划。适用 于动态规划方法的问题必须满足最优化原理和无后效性。动态 规划的基本思想是：将过程分成若干个互相联系的阶段，即子 问题。将各阶段按照一定的次序排列好之后，对于某个给定的 阶段状态，先求解子问题；对于重复出现的子问题，只在第一 次遇到时进行求解并把答案保存，以后遇到时直接引用答案。 ３．２引入动态规划的区域相关匹配优化
圈１区域相关匹配原理
相同或相近时，测度函数值达到最小。常见的归一化互相关算 法ＮＣＣ灰度相关测度函数如下：
（１）归一化互相关算法Ｎｅｄ胡（ＮｏｒｍａｌｉｚｅｄＣｒｏｓｓ Ｃｏｒｒｅ—
ｌａｔｉｏｎ）：
∑∑Ⅱｏ＋ｉｄ＋Ｊ）一五石ｊＩ］·［ｂ＋ｉ＋ｄ∥＋力一ｉ石干砑
，’＼一Ｊ／—＿∑Ｉ ∑Ｅｌｌｂ－４－ｉ，ｙ－４－ｊ）一…＾—砑１∑∑［ｋ＋ｉ＋ｄｄ州）一ｉ五耳劢
（ａ）原Ｔｓａｋｕｂａ图像
Ｃｏ）ＬＯＧ卷积后的图像
（ｃ）预处理后的图像
图３匹配源图像预处理
然后对预处理后的图像对进行基本区域相关匹配的实验。 应用归一化互相关灰度测度函数实验，每组实验中又选择大小 不同的窗口进行多次实验。
本实验选择的窗口为５×５，７×７和９×９大小的方形窗 口，视差搜索范围ｄ一３０，实验结果如图４所示。实验表明， 对于这种测度函数，窗口大小的选择对匹配结果的影响还是相 当大的：很明显，匹配窗口较小时，出现很多不连续点，误匹 配较多，而窗口较大时，图像边缘特征变得很模糊。所以匹配
范围限定等策略，利用从相关参数矩阵中寻找最优路径，实现 了立体匹配。可以看出，本方法在视差连续的地方效果较好， 本文研究的改进动态规划匹配算法完全可以描绘场景的深度信 息，同时也较好地满足了从视差图中把要跟踪的目标从场景中 分离的要求。
关键词：双目视觉ｔ立体匹配算法Ｉ相关匹配优化；视差范围
Ｉｍｐｒｏｖｅ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ ｔｈｅ Ｄｅｐｔｈ Ｍａｐ Ｂｉｎｏｃｕｌａｒ Ｓｔｅｒｅｏ Ｍａｔｃｈｉｎｇ
Ｚｈｏｕ Ｙｉｐｅｎｇ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ａｕｔｏｍａｔｉｏｎ，Ｎｏｒｔｈｗｅｓｔｅｒｎ Ｐｏｌｙｔｅｃｈｎｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ＇ａｎ ７１００６８，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｂｉｎｏｃｕｌａｒ ｓｔｅｒｅｏ ｖｉｓｉｏｎ ｃａｎ ｄｉｒｅｃｔｌｙ ｉｍｉｔａｔｅ ｔｈｅ ｈｕｍａｎ ｅｙｅ ａｎｄ ｈｕｍａｎ ｖｉｓｕａｌ ｐｅｒｃｅ·ｐｔｉｏｎ ｏｆ ｔｈｒｅｅ－－ｄｉｍｅｎｓｉｏｎａｌ，ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ ｉｓ ｔｈｅ ｃｏｒｅ ｔｏｐｉｃ ｏｆ ｓｔｕｄｙ．Ｔｈｉｓ ｐａｐｅｒ ｍａｉｎｌｙ ｆｏｒ ａ ｔｈｒｅｅ－ｄｉｍｅｎｓｉｏｎａｌ ｉｍａｇｅ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ｒｅｓｅａｒｃｈ，ｔｈｅ ｒｅｇｉｏｎａｌ ｃｏｒｒｅｌａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｗａｓ ａｎａｌｙｚｅｄ．Ｉｎ ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ＮＣＣ ｂａｓｉｃ ｇｒａｙ ｃｏｒｒｅｌａｔｉｏｎ ｆｕｎｃｔｉｏｎ ｏｆ ｔｈｅ ｍｅａｓｕｒｅ ｏｎ ｔｈｅ ｂａｓｉｓ ｏｆ ｄｙｎａｍｉｃ ｐｒｏｇｒａｍｍｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ ｔｈｅｏｒｙ ｗｉｌｌ ｂｅ ｉｎｔｒｏｄｕｃｅｄ ｔｏ ｔｈｅ ｍａｔｃｈ，ｉｍｐｒｏｖｅｄ ｍａｔｃｈｉｎｇ ｓｐｅｅｄ ａｎｄ ａｃｃｕｒａｃｙ．Ｅｘｐｅｒｉｍｅｎｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ｍｅｅｔ ｔｈｅ ｔｅｓｔ ｒｅｑｕｉｒｅｍｅｎｔｓ ｏｆ ｔａｒｇｅｔ ｔｒａｃｋｉｎｇ ａｎｄ ｉｔ ｉｓ ａｎ ｉｍｐｏｒｔａｎｔ ｔｈｅｏｒｅｔｉｃａｌ ａｎｄ ｐｒａｃｔｉｃａｌ ｖａｌｕｅ． Ｋｅｙ ｗｏｌｄｓ：ｂｉｎｏｃｕｌａｒ ｖｉｓｉｏｎｔ ｓｔｅｒｅｏ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ｝ｍａｔｃｈｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ；ｐａｒａｌｌａｘ ｓｃｏｐｅ
由此可见，参与比较的路径减少，再加上视差范围的限
定，使计算的复杂度大大减小，能够快速找到匹配的最佳路 径，从而实现致密视差图的恢复。
４实验及分析
４．１ 区域标准相关匹配算法窗口大小选择对结果的影响 本实验使用的匹配源图像对是由Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｓｕｋｕｂａ提
供的Ｔｓｕｋｕｂａ图像对，图像大小为３８，１＊２８８像素。实验前先 对图像进行预处理，用口＝１．０的７×７ＬＯＧ离散内核进行卷 积［６］。结果如图３所示，图中只列出了图像对中的左图的处理 结果。预处理后的图像与原图像相比较，很容易看出边缘特征 变得更加明显了。
Ｖ（ｚ一３，ｓ一１），…，］＋Ｃ（工，ｓ）
（７）
其中，ｍａｘ为求最大值符号，Ｖ（ｚ，ｓ）为阶段路径达到ｚ位
置的累积价值，Ｃ（ｚ，ｓ）为右图第ｚ个特征点与左图第ｓ个
特征点的相关值。搜索时从相关系数矩阵平面的左上角Ｖ（１，
１）出发，在选定的搜索视差范围ｄ内寻找到达右下角Ｖ（Ｎ， Ｎ）点的最佳路径，沿该路径累积的匹配价值最大，该路径上
Ｑ）
以上是区域相关立体匹配中的归一化互相关基本算法，这 种方法中窗口的选择很重要，具体的影响将在实验中分析。 ２．２区域相关匹配算法的一些改进 ２．２．１视差范围约束
这起源于心理物理实验，它表明人类视觉系统只能融合比 某个限度小的立体图像［３］。将该结果应用于立体视觉的研究 中，可以大大减少立体匹配寻找匹配点时的搜索长度，大大减 少计算时间。对于双目立体图像对‘“，如图１所示，可以预先 设定视差范围（一ｄ，＋ｄ），对于左图像中点Ｌ（ｚ，ｙ），可 以在右图中同一水平扫描线上设定视差范围内搜索其匹配点， 即从Ｌ（ｚ—ｄ，ｙ）到Ｊｚ（ｚ＋ｄ，ｊ，），这样就避免了搜索整个 扫描线，提高了效率。这种约束对于不同测度函数的区域匹配 都是适用的。 ２．２．２归一化互相关函数的加速计算方法