>> 吴 波，2006，自适应三角形约束下的立体影像可靠匹配方法
摘 要
数字摄影测量技术正被广泛地应用于从二维数字立体影像中获取三维空间目标的几何信息、辐射信息和语义信息。随着大量影像数据的日益普遍可得和对三维空间信息不断增长的应用需求，对数字摄影测量技术的高自动化、高效率和高可靠性要求也越来越迫切。而长期以来制约数字摄影测量自动化与可靠性的一个关键问题就是立体影像匹配，即由计算机来代替（或模拟）人眼进行立体观察，自动确定同名像点的过程。立体影像匹配也一直是计算机视觉和图像理解领域所共同关心的学术前沿和难点问题。
现有大多数立体影像匹配方法对于地形平滑的开阔地带具有较高的可靠性，然而，面对从千变万化的自然界所摄取的影像，现有的匹配方法仍然存在许多问题，尤其是在植被茂密、建筑物密集和水域等区域，影像匹配的可靠性还不高，一些建筑物的角点和地物的主要边界点还不能正确地匹配出来，自动生成的数字表面模型中存在着许多异常值，需要进行大量的人工编辑处理，这在很大程度上制约了数字摄影测量自动化水平的提高。针对立体影像自动匹配的可靠性问题，Zhu et al. (2005)和赵杰（2004）提出了一种自适应三角形约束下的立体影像匹配方法。该方法首先在立体像对的重叠区域提取特征点，然后利用一定数量的种子点构建Delaunay三角网，对每一对同名三角形范围内的特征点，在三角形约束下对特征点进行互相关匹配，将新匹配得到的同名点插入到Delaunay三角网中，通过Delaunay三角网的不断动态细化，使得局部几何约束区域的大小自动适应影像纹理特征的变化，从而得到更加可靠的匹配结果。在Zhu et al. (2005) 和赵杰（2004）已有研究工作的基础上，本文对其中的关键问题和实现中的技术细节进行了更加系统深入的研究和实验分析，具体包括：
- 具有良好重复率与信息量的特征点提取方法。本文分析了数字摄影测量领域常见的几种特征点提取算子，并从特征点的重复率与信息量两个方面对这些特征点提取算子进行了实验比较；基于有关实验结果，针对Harris-Laplace算子，本文提出了一种与影像纹理特征相关的筛选策略，通过有效筛除Harris-Laplace算子所提取的特征点中兴趣值较小的特征点，进一步提高其重复率与信息量，使之更有利于后续的立体影像匹配和人工地物目标的三维重建，有关的实验分析证明了这种特征点筛选策略的有效性；
- 特征点子像素精确定位方法。针对基于Harris原理提取的特征点的定位精度只能达到1个像素的问题，本文提出了一种基于Harris兴趣值的特征点子像素精确定位方法。该方法利用一个二次抛物面在灰度空间内对特征点的Harris兴趣值进行最小二乘拟合，通过计算拟合曲面的极值来确定特征点的精确像素坐标。这种方法能够适用于角点、交叉点、明显点、圆状点等所有具有二维重要纹理特征的特征点的精确定位，理论和实际的精度分析证明该方法的定位精度能够达到0.15像素，并且该方法还具有良好的抗噪声干扰性、旋转不变性和良好的处理效率；
- 三角形约束下的互相关匹配。本文提出了三角形约束下的互相关匹配方法的理论框架，并设计了其具体实现的算法。首先分析了三角形约束下的互相关匹配方法中基本的匹配约束条件，集成这些约束条件定义了匹配的可靠性测度指标，并深入分析了各种约束条件对匹配可靠度的贡献；针对纹理缺乏区域、纹理相似区域以及遮挡区域等困难纹理条件下的匹配可靠性问题，进一步研究了减少错误匹配的策略，并通过实验验证了这些策略的实际效果；
- 匹配传播策略。匹配传播策略是本文提出的影像匹配方法的核心。本文分析和总结了现有影像匹配方法中不同的匹配传播方式，提出了一种新的“三角形－三角形”的匹配传播思路。首先，针对匹配传播过程中的种子点选取问题，通过实验分析研究了不同数量与分布的种子点所构成的初始三角网对匹配结果的影响，进而提出了不同影像条件下的种子点选取策略和一种自动提取一定数量、满足一定分布均匀度的种子点自动选取算法；其次，研究了海量数据情况下同名三角网的快速构建、数据组织存储与局部动态更新的方法；在此基础上，本文提出了随机传播、基于三角形拓扑关系的邻近传播和顾及纹理特征的自适应传播等三种传播策略，分别介绍了其详细的实现算法，并通过实验分析对这几种传播策略进行了比较，实验结果证明自适应传播方法在匹配的可靠性上最优。
基于本文所研究提出的影像匹配方法的有关理论、方法与算法设计，用VC++ 6.0编程实现。选取不同纹理特征的实际立体影像进行了系统的实验分析，有关实验结果证明本文的影像匹配方法能有效处理各种纹理特征的立体像对，影像区域内主要人工地物的边界点与地形特征点能自动匹配出来，匹配得到的结果三角网与影像的纹理特征相适应。实验结果还证明，在未剔除粗差的情况下，通过本文的影像匹配方法所获取的数字表面模型的精度要优于现有有关的方法。
本文提出的自适应三角形约束下的立体影像可靠匹配方法将一种新的、动态的三角形几何约束引入到影像匹配中来，为影像匹配的可靠性问题提供了一条新的解决途径。本文的研究成果为直接扩展和增强现有数字摄影测量系统的有关功能提供了理论依据，有关的方法和算法能直接应用于现有数字摄影测量系统中。
关键词：
立体影像匹配；三角形约束；特征点；匹配传播
Abstract
Digital photogrammetry technology is now generally used for the derivation of geometric, radiometric, and semantic information of objects in the 3D real world from 2D digital stereo images. Along with the easy availability of more image data and the increasing requirements for the application of 3D space information, the performances of perfect automaticity, good efficiency and high reliability to the digital photogrammetry are more considered in nowadays. One of the difficult tasks in digital photogrammetry is stereo image matching, which is the process to automatically search for the corresponding points in the overlapping area of the stereo pairs by making use of computers to substitute or simulate human eyes, so as to compute object coordinates in a 3D ground coordinate system. Stereo image matching is also one of the most important and challenging subjects in computer vision and image understanding.
The existing image matching methods work well in open areas with relatively smooth terrain. However, they still meet many problems in the case of larger scale images of nature, especially in the dense city centers, forestry areas and the textureless regions such as water bodies. The reliability of image matching is still a big issue in these cases. For example, the corners of buildings and some object boundary points sometimes cannot be matched successfully, and there are many blunders in the automatically derived digital surface models that need to be manually removed, which leads to the decrease of the automaticity in digital photogrammetry. For the purpose of reliable image matching, Zhu et al. (2005) and Zhao (2004) presented a novel stereo image matching method based on the self-adaptive triangle constraint. They firstly triangulate a few seed points on the edge of irregular areas to form a coarse corresponding Delaunay triangulation pair, each triangle in these triangulations is considered as a local continuous area; then detect certain amount of interest points within each triangle, match these interest points under the triangle constraint, and obtain a pair of corresponding points with maximum reliability; after that, insert the new matched corresponding points into the triangulations, and update the triangulations dynamically, then handle the next pair of triangles, and repeat the same matching process until the termination conditions of the propagation are met. Because the most distinctive point is always successfully matched first, the dynamic updating of triangulations is just the process of self-adaptive matching propagation. Along with the matching propagation, the local geometry constraint of the dynamically updated triangles can adapt to the changes in image textures automatically, and will finally produce more reliable matching results. Based on the previous works of Zhu et al. (2005) and Zhao (2004), this dissertation researches further the key issues of this reliable image matching method and the technical details in realizing this method as follows:
- An interest point detecting method with good repeatability and information content. This dissertation introduces several stereo image interest point detectors generally used in digital photogrammetry, and compares them with respect to their repeatability and information content through experimental analysis. The Harris-Laplace detector gives better results than other detectors in areas of good texture; however, in areas of poor texture, the Harris-Laplace detector may be not the best choice. A feature-related filtering strategy is then designed for the Harris-Laplace detector to improve the repeatability and information content for imagery with both good and poor texture by picking out those points with less interest strength, which benefits the subsequent stereo image matching and the 3D object reconstruction. The performance of this filtering strategy is supported by experimental analysis with actual stereo images.
- A subpixel location method for interest points. The interest points detected by the Harris-Laplace detector are preferable for stereo image matching and the 3D object reconstruction. However, Harris-Laplace detector clearly suffers from delocalization and forgets a part of the shape. So, this dissertation presents a subpixel location method to improve the precision of the interest points by means of the Harris interest strength. Firstly, a least squares fit of a paraboloid function to the Harris interest strength in the image grayscale surface is designed. Then, the precise coordinates of the interest points are obtained by calculating the extremities of the fitting surface. This method can be used to locate interest points including corners, junction points, dominant points, blob-like points and all other types of distinctive points with important two-dimensional texture features. Experimental analysis from the theoretical and the practical point of view both prove that the location accuracy of 0.15 pixels is obtained. Results from intensiveexperimental work also indicate that this method has the desired performance of anti-interference, is invariant to image rotation and is highly efficient.
- Triangle constrained cross-correlation (TC3) matching. This dissertation proposes the theoretical framework of the TC3 matching method, and designs the detailed TC3 algorithm. Firstly, the essential matching constraints of TC3are introduced. Then, the measurement criteria of matching reliability in TC3 is defined by integrating these matching constraints, the contribution of different constraint to the matching reliability is also experimental analyzed. Furthermore, this dissertation studies the matching strategies to decrease the mismatching problems in difficult texture areas such as in textureless areas, homogeneous texture areas, surface discontinuity areas and image occlusion areas, and the actual performance of these strategies is confirmed by experimental analysis with actual stereo images.
- Matching propagation. The matching propagation is the most important issue in the self-adaptive triangle constrained image matching method. This dissertation summarizes the different matching propagation manners in the existing image matching methods, and proposes a novel image matching propagation strategy of “triangle-to-triangle”. Firstly, because the triangle constrained matching propagation begins with the initial corresponding triangulations formed by a few seed points in the stereo pairs, this dissertation studies the affects of different numbers and different distributions of seed points on the image matching results through experimental analysis, and proposes a seed point selection strategy for different image texture conditions, an automatic selection algorithm is also designed that gives good distribution quality for a defined number of seed points. Then, to carry out the triangle constrained matching propagation, the fast construction method, the data structure and storage manners as well as the local dynamic updating method of the corresponding Delaunay triangulations with mass data are introduced. Based on these former works, this dissertation proposes three propagation strategies: the stochastic propagation, the adjacent propagation based on the topological relationship of triangles, and self-adaptive propagation, which considers the texture feature. The detailed algorithms of these three propagation strategies are also presented. To compare these propagation strategies, an intensive experimental analysis is illustrated with different stereo pairs, and the results prove that the self-adaptive propagation gives best matching reliability than the others due to the “best first” strategy.
The stereo image matching method this dissertation proposed is programmed using VC++ 6.0, and several typical stereo pairs that cover different texture areas are selected to test the performance of this method. From the experimental results, this method is preferable to process aerial stereo pairs with different texture features, the main object boundary points and the terrain feature points can be matched successfully, and the matched result triangulation is accommodated to the image textures. Experimental analysis also proves that the precison of the derived digital surface models from this method is better than the existing methods without eliminating the blunders.
This dissertation proposes a reliable stereo image matching method based on the self-adaptive triangle constraint, which employs a novel dynamic triangle constraint to the image matching. This method gives a new solution for the reliable stereo image matching, and the research of this dissertation provides a theoretical foundation for extending and enhancing some of the related functions in the digital photogrammetry system, some methods and algorithms in this dissertation can be applied to the existing digital photogrammetry workstation directly.
Key words: Stereo image matching; triangle constraint; interest point; matching propagation
