传统及新型全局优化算法在点匹配及相关问题中的应用

Point matching refers to the problem of finding the correspondence between two sets of point features extracted from two images and the relevant spatial transformation. Most of the existing matching algorithms are heuristic based. Although being efficient, these methods are generally not robust and can easily fail when problems become difficult. In contrast, matching methods based on globally optimal algorithms will have the advantages of being robust and suitable for difficult problems. Because of this reason, we seek to apply global optimization algorithms to matching problems, proposing robust algorithms and extending our algorithms to solving other types of problems. The research plan is as follows: 1) Construction of branch-and-bound (BnB) based matching algorithms. Based on our previous study, we will further apply BnB to solving the problem where there is only partial overlap between two point sets and where the relative pose between two point sets is unknown, and the problem where the spatial transformation is nonlinear. We will also speed up existing matching algorithms using parallel techniques. 2) Construction of matching methods based on other types of global optimization techniques. We will explore applying techniques such as polynomial optimization, low rank/sparse optimization and multi-objective evolutionary computing to solving matching problems. 3) We will apply globally optimal algorithms to other types of problems such as histogram based image matching, robust parameter estimation, self-paced learning and image segmentation whose models are similar to those of the matching problems. The expected achievements of our project will greatly benefit the development of the field of matching and other relevant fields both in theory and practice.

点匹配指找到图像中的点特征之间的对应关系及空间变换。现有匹配算法大多基于启发式思想，虽然速度快，但鲁棒性不强，当问题变难时，容易失败。而采用全局优化的匹配算法将具有鲁棒性强、适用于高难度问题的特点。因此，我们拟将全局优化技术应用于匹配问题，提出鲁棒性强的算法并推广用于解决其他问题。研究内容包括：1）基于分支定界法的匹配算法构造。在前期研究基础上，我们进一步将分支定界法用于解决两点集只有部分重叠、对空间变换不变的匹配问题，采用非线性空间变换的匹配问题，以及通过并行加速现有匹配算法。2）基于其他类型全局优化技术的匹配算法构造。我们探讨把多项式优化、低秩/稀疏、多目标进化计算等技术应用于匹配问题。3）全局优化算法用于解决同匹配问题有类似模型的其他问题，包括基于直方图的图像匹配、鲁棒参数估计、自步学习、图像分割等问题。本项目的成果将在理论和应用两方面极大地促进匹配及相关领域的发展。

点集配准指找到使两点集的对应点在空间上一致的空间变换。该问题是计算机视觉、模式识别和医学图像处理等领域的一个基本问题。本项目主要研究了很有挑战性的两点集只有部分重叠，配准算法对相应空间变换不变的问题。针对该问题，我们共发表了3篇SCI论文、1篇中文核心论文。其中，（1）在分支定界法构造方面，我们提出2种采用分支定界法的算法，分别可以解决对平移不变和对相似变换不变的配准问题；（2）在新型优化算法构造方面，我们提出基于多面体扩张的算法、基于路径跟踪的算法，可以解决对仿射/相似变换不变的2D/3D配准问题；（3）在边集合匹配算法构造方面，我们提出一种采用支撑树的具有全局最优的算法，可以解决2D相似不变配准问题。现有主流的具有全局最优的点集配准算法通常只针对3D刚体变换问题。本项目的算法可以处理2D仿射变换和2D/3D相似变换问题，由此，显著扩展了现有算法的适用范围。另外，本项目首次将多面体扩张技术应用到计算机视觉领域。本项目算法的普遍缺点是运行效率仍然偏低，未来将在这方面尝试取得改进。除了点集配准问题，我们还在神经网络构造、视频跟踪、时间序列和粒子滤波领域发表了8篇SCI论文。