计算机视觉中鲁棒几何模型拟合方法

第1章 绪论 1.1 引言 模型拟合在统计学领域有着很长的发展历史。随着交叉学科的发展，模型拟合还涉及图像处理、机器学习、人工智能等多方面的理论与技术[1，2]。模型拟合是计算机视觉领域的一个基础学科，为该领域的其他任务提供可靠的研究依据。当前国内外高校和科研机构对计算机视觉越来越重视，而模型拟合也在扮演着越来越重要的角色。其研究成果广泛发表在 IEEE Transaction on Pattern Analysis and Machine Intelligence、 International Journal of Computer Vision、Pattern Recognition、IEEE Transaction on Image Processing、IEEE Transaction on Circuits and Systems for Video Technology等国际权威期刊和 IEEE International Conference on Computer Vision、IEEE Conference on Computer Vision and Pattern Recognition、 European Conference on Computer Vision 和 Conference and Workshop on Neural Information Processing Systems等国际顶级会议上。 人类主要通过听觉和视觉感知外部世界，其中80%以上的信息是通过视觉获得。随着科学的发展和社会的进步，计算机已经成为人类日常生活和工作不可或缺的重要工具。为了赋予计算机以人类视觉的感知功能，使其具备处理视觉信息的能力，一门新兴的学科——计算机视觉获得了广泛的关注。过去几十年，在日常生活中出现了大量基于计算机视觉的产品。例如，车牌的自动识别、数码相机的人脸检测和美化、汽车的无人驾驶、全景图合成等。 如何让计算机从图像中提取有效的信息，对计算机视觉非常重要。在大部分情况下，这些有效的信息可以通过参数模型来表示[3，4]。而模型拟合，是指从一组观测数据中估计合适的模型参数，能够用于估计参数模型。由此可见，模型拟合在计算机视觉中具有重要的地位。当前，模型拟合方法可以被用于许多计算机视觉应用中。比如，三维重构[5-9]、图片拼接[10-12]、运动分割[13-17]、目标识别[18-21]等。随着机器学习、图像处理、鲁棒统计学等研究领域的发展与交叉，模型拟合[22-25]已经取得了很大的发展。 然而，在现实中，输入的数据集往往比较复杂，且不可避免地含有一些噪声点。比如在数据采集、归纳、整理等过程中，均有可能造成一些数据缺失或编辑错误。这必然会产生一些噪声数据(不属于任何一个模型实例的离群点)。同时，数据集中也可能同时存在多个模型实例。在未知模型实例数量和各自内点比例的情况下，模型拟合问题的难度进一步增加。此外，多个模型实例之间也会相互干扰，因为其中一个模型实例的内点，对其他模型实例来说属于伪离群点[26]。上述因素对模型拟合算法的鲁棒性和有效性都提出了很大的挑战。更重要地是，大数据发展的趋势，要求模型拟合算法具有较低的计算时间复杂度。 为了阐述本书所解决的问题，本节首先介绍标准的直线拟合问题。如图1.1所示，输入的数据为未知数量的模型实例(直线模型)、未知比例的内点和离群点。基于该示例，一个鲁棒的模型拟合方法应该能够有效地拟合出数据集中所有的模型实例，并估计其数量和参数(对于一条直线 ax + by + c =0 ，它相应的参数为[a，b，c])，同时准确地区分内点和外点。 图1.1本书所阐述的模型拟合问题示例直线表示拟合的直线模型；虚线框内的点表示内点；其他点表示离群点 接着，本节介绍标准的圆形拟合问题。如图1.2所示，输入的数据为未知数量的模型实例(指圆形)和未知比例的内点和离群点。基于该示例，一个鲁棒模型拟合方法应该能够有效地拟合出数据集中所有的模型实例并估计其数量和参数(对于一个圆它相应的参数为[a，b，r]，即中心点坐标和半径 r)，并同时准确地区分内点和离群点。本节所述的模型拟合方法不限于人造数据，还包含真实图像数据。 图1.2 本书所阐述的模型拟合问题中圆形拟合示例。其中，输入的数据点分布在[0，100]，含有四个不同半径的圆和大量的离群点；输出的数据中来自真实模型实例的内点为靠近圆的数据，其他为离群点 如图1.3所示，在一个图像对上进行单应性平面估计。对于输入图像对，通过特征提取方法提取特征点，然后进行初始匹配。模型拟合的目标就是估计出该图像对的单应性平面的具体参数，然后对匹配进行分类。 图1.3本书所阐述的模型拟合问题中单应性估计示例。其中，(a)为输入的两张不同视图的图片对比；(b)为关键特征提取和相应的匹配；(c)中两个平面表示拟合的单应性平面模型；(d)中圆形和正方形的匹配对表示相应模型的内点；加号的匹配对表示离群点传统的模型拟合方法[22，27-30]主要步骤如图1.4所示。①采样一系列的*小数据子集，这里的*小数据子集是指要拟合一个模型所需要的*少数据集。比如，拟合一条直线，需要采样两个数据点；拟合一个圆形，需要采样三个数据点；拟合一个单应性，需要采样四个数据点。②基于采样的数据子集生成模型假设。基于输入的数据子集，采用直接线性变换[31]计算相应的模型假设参数。③基于生成的模型假设集拟合模型实例。步骤③包含两种方式： a)在特征空间中对数据点进行聚类或分割，然后再进行拟合模型实例； b)在参数空间中选择*有代表性的模型假设作为拟合的模型实例。 图1.4 传统模型拟合方法的主要步骤 1.2 模型拟合方法的分类与难点 从模型拟合方法的主要步骤出发，模型拟合方法主要分三大类，即采样算法[23，27，32-41]、模型选择算法[22，23，28，29，42-57]和采样与模型选择融合算法[25，30，58-60]。此外，还有一些模型拟合方法[48，61-63]，主要对用于区分内点和离群点的内点噪声尺度进行研究，如图1.5所示。但该方向与其他学科交叉较多，以下主要从上述三大类介绍当前模型拟合方法的研究现状。 1.2.1 采样算法 当前，除了随机采样算法[27]以外，其他算法均可以归为指导性采样算法。1981年，随机采样一致性(random sample consensus，RANSAC)算法被提出。该算法通过随机采样*小数据子集来生成模型假设集。简单有效，并且具有很好的鲁棒性，但只能适用于单结构数据，且在内点比例较低时，需要采样较大数目的数据子集才能保证生成对应真实模型实例的模型假设。 当前的指导性采样算法[23，32-41]主要利用空间信息、匹配信息和其他条件限制来指导整个采样过程。其中，基于空间信息的指导采样算法[32-34]充分利用了在数据的空间域中内点之间会更加紧密的先验信息对数据子集 图1.5内点噪声尺度用于直线拟合示例。当一个数据点到直线的距离小于内点噪声尺度 S，则它被认为是相应直线(图中实线)的内点(图中虚线中间的点)，反之则被认为是离群点(图中虚线外的点) 进行采样。也就是说，在找到一个内点后，其他内点可以从其周围局部区域内进一步搜索得到。该类型的指导采样算法能够在一定程度上快速地采样到全内点数据子集。但当离群点比例较高时，周围局部区域内也含有大量的离群点，会严重影响该类型指导采样算法的有效性。基于匹配信息的指导采样算法[35-38]主要利用双视图中匹配对的质量评估信息来指导采样。换句话说，匹配分数越高的匹配对被采中的概率就越大。该类型的指导采样算法能够有效提高采样的速度。然而，在处理多结构数据时，来自不同模型实例的匹配对会对采样算法产生严重干扰。基于其他条件限制的指导采样算法[23，39-41]，通过分析已采样到的数据子集含有的统计信息来指导下一步的采样。但是，只有在已采样到的数据子集含有较多内点的条件下，对其进行分析才有意义；反之，将会误导下一步采样。然而，当前的指导采样算法并无法保证采样的数据子集一定含有较多的内点。 1.2.2 模型选择算法 对于单结构数据，*简单直接的方法是选取有意义的模型假设作为拟合的模型实例[27]。然而，如何有效地区分内点和离群点是一个很大的挑战。此外，在很多情况下，数据集中不可避免地会同时存在多个真实的模型实例，这也会带来很大的挑战。 对于多结构数据，分为基于传统统计方式[22，28，42，43]、基于聚类[23，50-52]、基于参数空间[46-49]、基于能量函数[29，44，45]和基于图论[53-57]的模型选择算法。其中，基于传统统计方式的模型选择算法[22，28，42，43]通过设定拟合的标准(如内点的数目等)来选取*优的模型假设，接着从数据集中去除相应的内点，重复拟合模型，直到找到所有模型实例。该类型的模型选择算法采用了“拟合-去除”框架。然而，当前模型实例的选择准确性会直接影响到下一个模型实例的选择。此外，该类型的模型选择算法还要求重复地生成模型假设集，比较耗时。基于聚类的模型选择算法[23，50-52]通过分析数据点之间的关系，试图将来自同一个模型实例的内点聚成较大类的同时，将离群点聚成多个小类。该类型的模型选择算法对内点噪声尺度不太敏感，往往很难处理处于交叉位置的数据点。基于参数空间的模型选择算法[46-49]直接分析模型假设，从中选取*优的模型假设作为拟合的模型实例。该类型的模型选择算法对数据分布不太敏感。相比其他内点的模型选择算法，其在算法准确性上也有一些明显的优势。但该类型的模型选择算法对模型实例的选择准确性要求较高，因为内点和离群点的区分完全依赖于拟合的模型实例和相应的内点噪声尺度。基于能量函数的模型选择算法[29，44，45]将模型拟合问题转化为标签分配问题，通过优化目标函数来选取*优的标签分配。该类型的模型选择算法对算法的收敛要求较高，此外一般还含有比较多的参数。因此，对于不同的数据集，往往需要手工调整参数。基于图论的模型选择算法[53-57]将模型拟合问题转化到图论中的一些优化问题。当前的该类型模型选择算法在准确性上和计算速度上还存在一些问题，没有充分发挥出图论的优势。 1.2.3 采样与模型选择融合算法 随着模型拟合算法的快速发展，当前已有学者提出将采样与模型选择相融合的拟合算法[25，30，58-60]。该类型的拟合算法试图充分结合采样与模型选择之间的信息，提高算法的整体性能。比如，文献[30]、[58]提出采用随机聚类模型的方式生成模型假设，并通过能量优化过滤这些模型假设。同时，分析选取的模型假设信息指导下一步的采样。该算法将采样与