第２１卷第３期 ２０１１年３月 计算机技术与发展 Ｃ０ＭＰＵＴＥＲ ＴＥＣＨＮＯＬＯＧＹ ＡＮＤ ＤＥＶＥＬＯＰＭＥＮＴ Ｖｏ１．２１ Ｎｏ．３ Ｍａｒ．２０ｌ１ 一种新的立体匹配算法 毛雁明，杨慧玲 （宁德师范学院计算机与信息工程系，福建宁德３５２１００） 摘要：立体匹配是目前计算机视觉领域中最活跃的研究主题之一，在三维重构、对象识别与分类、图像对齐等应用中，立 体匹配都是一个关键步骤。为了能够更精确地对特征点进行匹配，给ｍ了一个新的匹配约束条件：匹配点距离相关性约 束，据此提出了一种新的立体匹配算法。该算法独立于特征点的检测算法，首先使用灰度相关法进行初始匹配，然后利用 最小中值平方法获得部分正确匹配点集，在此基础上加入匹配点距离相关性约束进行引导匹配，得到最后的匹配点集。 实验表明，该算法能够很好地实现特征点的正确匹配，具有很高的使用价值。 关键词：计算机视觉；Ｈａｒｒｉｓ；ＬＭｅｄＳ；立体匹配；匹配点距离相关性 中图分类号：ＴＰ３０１．６ 支献标识码：Ａ 文章编号：１６７３—６２９Ｘ（２０１１）０３—０１０５—０４ Ａ Ｎｅｗ Ｓｔｅｒｅｏ Ｍａｔｃｈｉｎｇ Ａｌｇｏｒｉｔｈｍ ＭＡＯ Ｙａｎ－ｍｉｎｇ，ＹＡＮＧ Ｈｕｉ－ｌｉｎｇ （Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｎｉｎｇｄｅ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｎｉｎｇｄｅ ３５２１００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｓｔｅｒｅｏ ｍａｔｃｈｉｎｇ ｉｓ ｓｔｉｌｌ ｔｈｅ ｍｏｓｔ ａｃｔｉｖｅ ｒｅｓｅａｒｃｈ ｔｈｅｍｅ ｉｎ ｈｅ ｔｉｅｌｆｄ ｏｆ ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ，ａｎｄ ｉｔ ｉｓ ａ ｋｅｙ ｓｔｅｐ ｉｎ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ３ｄ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ，ｏｂｊｅｃｔ ｒｅｃｏｇｎｉｔｉｏｎ ａｎｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎ，ｉｍａｇｅ ａｌｉｇｎｍｅｎｔ ａｎｄ ｓｏ ｏｎ．Ｉｎ ｏｒｄｅｒ ｔｏ ｄｏ ｍｏｒｅ ｐｒｅｃｉｓｅ ｔｏ ｔｈｅ ｓｔｅｒｅｏ ｍａｔｃｈｉｎｇ ｏｆ ｆｅａｔｕｒｅ ｐｏｉｎｔｓ，ｇａｖｅ ａ ｎｅｗ ｍａｔｃｈｉｎｇ ｃｏｎｓ￣ａｌｎｔ ｃｏｎｄｉｉｔｏｎ：ｄｉｓｔａｎｃｅ ｃｏｒｒｅｌａｔｉｏｎ ｏｆ ｍａｔｃｈｉｎｇ ｐｏｉｎｔｓ ｃｏｎｓ￣ｍｎｔ ａｎｄ ｐｒｏｐｏｓｅｄ ａ ｎｅｗ ｓｔｅｒｅｏ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ａｌｇｏｒｉｈｍ ｉｔｓ ｉｎｄｅｐｅｎｄｅｎｔ ｏｆ ｆｅａｔｕｒｅ ｐｏｉｎｔ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ，ｆｗｓｆｌｙ，ｕｓｅ ｔｈｅ ｇｒａｙ ｃｏｒｒｅｌａｔｉｏｎ ｍｅｔｈｏｄ ｔｏ ｄｏ ｉｎｉ— ｔｉａｌ ｍａｔｃｈｉｎｇ ａｎｄ ｔｈｅｎ ｕｓｅ ＬＭｅｄＳ ｍｅｔｈｏｄ ｔｏ ｇｅｔ ｐａｒｔｉｌ ｃｏｒｒａｅｃｔ ｍａｔｃｈｉｎｇ ｏｉｐｎｔｓ ｓｅｔ，ａｎｄ ｏｎ ｔｈｅ ｂａｓｉｓ，ａｄｄ ｄｉｓｔａｎｃｅ ｃｏｒｒｅｌａｔｉｏｎ ｏｆ ｍａｔｃｈｉｎｇ ｐｏｉｎｔｓ ｃｏｎｓ￣ａｌｎｔ ｔｏ ｇｕｉｄｅ ｈｅ ｔｍａｔｃｈｉｎｇ．Ｅｘｐｅｒｉｍｅｎｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ａｃｈｉｅｖｅ ｇｏｏｄ ｍａｔｃｈｅｓ ｏｆ ｆｅａｔｕｒｅ ｐｏｉｎｔｓ，ａｎｄ ｈａｓ ａ ｖｅｒｙ ｈｉｇｈ ｖａｌｕｅ． Ｋｅｙ ｗｏｒｄｓ：ｃｏｍｐｕｔｅｒ ｖｉｓｉｏｎ；Ｈａｒｒｉｓ；ＬＭｅｄＳ；ｓｔｅｒｅｏ ｍａｔｃｈｉｎｇ；ｄｉｓｔａｎｃｅ ｃｏｒｒｅｌａｔｉｏｎ ｏｆ ｍａｔｃｈｉｎｇ ｐｏｉｎｔｓ ０ 引 言 立体匹配是立体视觉系统的重要组成部分，是近 年来计算机视觉领域备受关注的前沿方向和研究热 点。它在计算机视觉、航空测绘、军事应用、医学诊断 及工业检测中有着广泛的应用前景和潜在的经济价 检测，接着使用灰度相关法获得初始匹配点集，然后利 用ＬＭｅｄＳ方法获得部分正确匹配点集，最后在此基础 上利用匹配点距离相关性约束对其它匹配点对进行引 导匹配，获得最终的匹配点集。 实验表明，该算法能够很好地实现特征点的正确 匹配，具有很高的使用价值。 值。立体匹配是指在两幅待匹配图像中寻找匹配点， 目前，立体匹配的模型和算法很多，大致可分为：基于 特征的匹配算法 “ 和基于区域的匹配算法 。 。 由于受光照条件、物理特性、噪声干扰等的影响， 要准确地对特征点进行无歧义的匹配有相当的困难。 据此。文中提出了基于ＬＭｅｄＳ与匹配点距离相关性约 束的立体匹配算法，首先使用改进的基于Ｈａｒｒｉｓ的角 点检测方法 分别对同一场景的不同图像进行角点 １初始匹配 基于灰度的匹配算法是一种经典的立体匹配算 法，是一种对图像像素以一定大小窗口的灰度阵列按 某种相似性度量顺次进行搜索匹配的方法 。若ｍ 是图像， 的特征点，ｍ：是图像，２的特征点，且ｍ。、ｍ： 的图像坐标分别为（Ｉｔ，， 。）、（ｕ：， ：），给定以ｍ 为 中心的相关窗口（２ｎ＋１）Ｘ（２ｍ＋１）在图像，２中相 应于ｍ．的位置选定（２ｄｕ＋１）Ｘ（２ｄｖ＋１）的搜索窗 收稿日期：２０１０－０７－１２：修回日期：２０１０－１０－１６ 基金项目：福建省自然科学基金资助项目（２００９Ｊ０１２９４）；宁德师范 高等专科学校科研资助项目（２００９Ｙ０３４） 作者简介：毛雁明（１９８２一），男，福建福安人，硕士研究生，讲师，研究 方向为计算机视觉、人工智能。 口，用归一化互相关算法ＮＣＣ（Ｎｏｒｍａｌｉｚｅｄ Ｃｒｏｓｓ Ｃｏｒ－ ｒｅｌａｔｉｏｎ）计算窗口内的特征点ｍ 与ｍ。的灰度相关系 数，公式如下： ・ｌ０６・ 计算机技术与发展 第２１卷 ｎ ｍ 一 一 ∑∑（，（“。一ｉ， 。一 ）一 ， （“：一ｉ， ：一 ）一， ） 常数据的比例。 当图像受到高斯噪声的影响时，ＬＭｅｄＳ方法并不 （２ｎ＋１）（２ｍ＋１）￣／ （，）ｏｒ （，） 理想… 。通常为了提高该方法的功效，增加执行一个 （１） 加权最小二乘过程，其中标准偏差为： 其中，，（ｕ，， ，）和，‘（ｕ。， ）分别为图像，，和，２特 ＝１．４８２６（１ ５） （３） 征点处的灰度值，，和，。分别为它们所在窗口的灰度 均值， （，）和ｏｒ（，’）分别是图像， 和，２在特征点处的 其中 ，是ＬＭｅｄＳ方法中的最小中值。基于上述 （２ｎ＋１）×（２ｍ＋１）窗口的标准偏差。 ，如果满足ｒ ≤（２．５Ｏｒ）。，则该匹配点对为正确匹配， 相关系数ｓｃｏｒｅ的范围从一１到１，ｓｃｏｒｅ绝对值越 否则为误匹配。 大，说明ｍ。与ｍ：的相似程度越高。如果一对特征点 由于ＬＭｅｄＳ方法比其他鲁棒方法（如ＲＡＮＳＡＣ） 匹配，那么ｓｃｏｒｅ必然较大，反之不成立，所以仅使用灰 限制更为严格，因此比其它鲁棒方法去除更多的点，基 度相关法就会产生误匹配。 本上能消除所有的误匹配，但也同时消除了一小部分 正确的匹配点，所以ＬＭｅｄＳ是所有鲁棒方法中最适合 ２最小平方中值法（ＬＭｅｄＳ） 用来消除误匹配的方法¨ 。 ＬＭｅｄＳ方法¨。。通过求解下面的非线性问题估计 参数：ｍｉｎ ｍｅｄｉａｎｒ￣，即计算整个数据集中全部数据 ３ ＬＭｅｄＳ与匹配点距离相关性约束的立体 匹配算法 的残差平方的中值，取其中最小的。 文中要求获得的同一场景的不同图像之间的旋转 给定ｎ对对应点｛（ｍ ，ｍ ）ｆ ｉ＝１，２，…，ｒｔ｝，应用 和平移都相对很小。文中的匹配方法主要是先使用改 ＬＭｅｄＳ方法获得部分正确匹配点对的主要步骤如下： 进的基于Ｈａｒｒｉｓ的角点检测方法 分别对同一场景的 ｓｔｅｐｌ：从ｎ对对应点中随机抽取ｍ个子集，每个 两幅不同图像进行角点检测，接着利用灰度相关法进 子集中有Ｐ＝７对不同的对应点对。 行初始匹配，然后利用ＬＭｅｄＳ得到部分正确匹配点 ｓｔｅｐ２：对于每个子集＿，（Ｊ＝ｌ，２，…，ｍ），应用７ 集，再加入匹配点距离相关性约束进行引导匹配。 点算法得到基本矩阵Ｆ，，每个子集对应的基本矩阵 定义匹配点距离相关性ｒｅｌａｔｉｏｎ为：假设 是含 Ｆ，要么一个或三个，如果是三个，选择匹配点对应数 有ｎ对匹配点的正确匹配点集，Ｍ＝｛（Ｐ ，ｑ。）ｆ １，２， 最多的矩阵作为基本矩阵Ｆ，的真解。 …，ｎ｝，其中（Ｐ ，ｑ。）是一对正确匹配点，（Ｐ，ｇ）是Ｍ ｓｔｅｐ３：对每个Ｆ，，计算全部数据的残差平方的中 外的一对匹配点，给定阈值６，ｍ是满足 值，表示为 ，，即： Ｉ ｄｉｓｔ（ｐ，Ｐ ）一ｄｉｓｔ（ｑ，ｑ ）１ 的Ｍ中的匹配点对个数， Ｍｊ＝ｍｉｄｉａｎ［ｄ２（ｍ ，Ｆ，ｍ。）＋ｄ２（ｍ。，Ｆ』Ｔｍ：）］（２） 则ｒｅｌａｔｉｏｎ＝．ｍ×１＿００％。 ｓｔｅｐ４：保留ｍ个肘，中最小的 ，对应的Ｆ，，其中 下面介绍如何把匹配点距离相关性应用到立体匹 ｍ＝ ｆ 可， 为全部对应点集合包含异 配方法中。如图１所示，ｌ～８是正确的匹配点对，现 ｌ１ Ｏ ９ Ｏ １２ ０ ９ Ｏ １２ ０ １１ Ｏ ７ Ｏ ７ ０ １ ｏ ５ ｏ ８ ０ １ Ｏ ５ ｏ ８ ０ ６ ｏ ６ Ｏ ２ ｏ ２ ｏ ３ ｏ ４ Ｏ ３ ０ ４ Ｏ １Ｏ ｏ １０ ｏ 图１ 匹配点距离相关性 ・１０８－ 计算机技术与发展 第２１卷 ５ 结束语 ［５］郭龙源，夏永泉，杨静宇・基于梯度的快速区域匹配方法 文中给出了一个新的立体匹配约束条件：匹配点 ［Ｊ］．计算机科学，２００７，３４（４）：２３９－２４０． 距离点距离相关性约束的立体匹配算法， 关 柬， 此 ｌ出了Ｉ ＿在使用ＬＭｅ于 ｅｄｓ与匹ｄＳ获 ７］姚Ｌ轰￣ Ａ益＂平ｔ： 颖≤，陈 ，霎 等．基于索引排序的快速动态区 篡 三 配方法 得部分正确匹配点集的基础上，再利用匹配点距离相 域匹配算法ｆ Ｊ］．计算机学报，２００９，３２（７）：１３７５—１３８１． 关性约束进行引导匹配。实验表明，ｌ文中提出的立体 ［８］毛雁明，兰荚辉，上运琼，等．一种改进的基于Ｈａｒｒｉｓ的角 匹配算法能够很好地实现特征点的正确匹配。 点检测方法［Ｊ］．汁算机技术与发展，２００９，１９（５）：１３０一 参考文献： ［９］ 王燕婷，张玮．图像匹配技术在土地利用动态监测中的 ［１］Ｌｈｕｉｌｌｉｅｒ Ｍ，Ｑｕａｎ Ｌ．Ｒｏｂｕｓｔ ｄｅｎｓｅ ｍａｌｃｈｉｎｇ ｕｓｉｎｇ ｌｏｃａｌ ａｎｄ 应用方法研究［Ｊ］．中国农学通报，２００７（６）：６０７—６１０－ ｇｌｏｂａｌ ｇｅｏｍｅｔｉｒｃ ｃｏｎｓｔｒａｉｎｔｓ［Ｃ］／／Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １６ｔｈ ［１Ｏ］Ｃｈｏｊｎａｃｋｉ Ｗ，Ｂｒｏｏｋｓ Ｍ Ｊ，Ｇａｌｗｅｙ Ｄ，ｅｔ ａ１．Ａ ｎｅｗ ａｐｐｒｏａｃｈ ｔｏ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ．Ｂａｒｃｅｌｏｎａ， ｃｏｎｓｔｒａｉｎｅｄ ｐａｒａｍｅｔｅｒ ｅｓｔｉｍａｔｉｏｎ ａｐｐｌｉｃａｂｌｅ ｔｏ ｓｏｍｅ ｃｏｍｐｕｔｅｒ Ｓｐａｉｎ：［ｓ．ｎ．］，２０００：９６８—９７２． ｖｉｓｉｏｎ ｐｒｏｂｌｅｍｓ［Ｃ］／／Ｓｔａｔｉｓｔｉｃａｌ Ｍｅｔｈｏｄｓ ｉｎ Ｖｉｄｅｏ Ｐｒｏｃｅｓｓｉｎｇ ［２］谭磊，张桦，薛彦斌．一种基于特征点的图像匹配算法 Ｗｏｒｋｓｈｏｐ Ｈｅｌｄ ｉｎ Ｃｏｎｊｕｎｃｔｉｏｎ ｗｉｔｈ ＥＣＣＶ’０２，Ｃｏｐｅｎｈａｇｅｎ， ［３］戚世贵，戚素娟．一种基于图像特征点的图像匹配算法 １１］邹定海．兰维视觉检测研究及其ＡＤＣ应用［Ｄ］．天津：天津 ［４］ 张少辉，沈晓蓉，范耀祖．一种基于特点特征点提取及匹配 ［１２］Ａｒｍａｎｇｎｅ Ｘ，Ｓａｌｖｉ Ｊ．Ｏｖｅｒａｌｌ ｖｉｅｗ ｒｅｇａｒｄｉｎｇ ｉｆｍｄａｍｅｎｔａｌ ｍａ‘ 的方法［Ｊ］．北京航空航天大学学报，２００８，３４（５）：５１６一ｔｒｉｘ ｅｓｔｉｍａｔｉｏｎ［Ｊ］．Ｉｍａｇｅ ａｎｄ Ｖｉｓｉｏｎ Ｃｏｍｐｕｔｉｎｇ，２００３，２１： （上接第１０４页） ［４］ 曹东刚，梅宏．面向Ａｓｐｅｃｔ的程序设计一一种新的编程 ［９］ Ｃｏｌｙｅｒ Ａ，Ｃｌｅｍｅｎｔ Ａ，Ｈａｒｌｅｙ Ｇ，ｅｔ ａ１．Ｅｃｌｉｐｓｅ ＡｓｐｅｃｔＪ：Ａｓｐｅｃｔ 泛型［Ｊ］．计算机科学，２００３，３０（９）：５一ｌＯ． —Ｏｒｉｅｎｔｅｄ Ｐｒｏｇｒａｍｍｉｎｇ ｗｉｔｈ ＡｓｐｅｃｔＪ ａｎｄ ｔｈｅ Ｅｃｌｉｐｓｅ ＡｓｐｅｃｔＪ ｆ５］周改霞，高尚，杨镇江．基于ＡＯＰ的Ｗｅｂ系统事务管理 Ｄｅｖｅｌｏｐｍｅｎｔ Ｔｏｏｌｓ［Ｍ］．［Ｓ．１．］：Ａｄｄｉｓｏｎ Ｗｅｓｌｅｙ Ｐｒｏｆｅｓｓｉｏｎ— 的应用研究［Ｊ］．计算机技术与发展，２０１０，２０（４）：２４６— ｌａ，２００４． ２４９． ［１０］蔡宇，赵正文．基于ＮＨｉｂｅｒｎａｔｅ和Ｌｏｇ４Ｎｅｔ实现用户登录 ［６］ 陈月娟，李慧，刘光远．基于ＡＯＰ的信息管理系统的研 合法性验证［Ｊ］．信息技术，２００８，１１：３２—３５． 究与实现［Ｊ］．计算机应用与软件，２０１０，２７（２）：１３０—１３３． ［１１］Ｈｏｆｆｍａｎ Ｋ，Ｋｒｕｇｅｒ Ｌ．Ｍｉｃｒｏｓｏｆｔ Ｖｉｓｕａｌ ｃ＃．ＮＥＴ ２００３ Ｕｎ— ［７］ 胡冰，程家兴，郭建业．一种．ＮＥＴ平台ｉ ＡＯＰ框架的实 ｌｅａｓｈｅｄ／Ｃ＃．ＮＥＴ技术内幕［Ｍ］．董梁，高猛，译．北京： 现方法［Ｊ］．计算机与现代化，２００９，１１：８５—８９． 清华大学出版社，２００６：５４４—５５６． ［８］ 陈敏智．一种基于ＡＯＰ的ＢＰＥＬ过程动态发现和绑定服务 ［１２］Ｒｏｂｉｓｏｎ Ｓ，Ｎａｇｅｌ Ｃ．ｃ＃高级编程［Ｍ］．北京：清华大学出 的方法［Ｊ］．浙江工业大学学报，２００９，３７（５）：５１１—５１４． 版社，２００４．
