组合图优化理论、算法及其在模式分析中的应用研究

Many important problems in pattern analysis are inherently NP-hard combinatorial graph optimization problems, such as graph matching and energy minimization. The relaxation (continuous) method is currently one of the major approaches to solve such problems and has attracted much attention in recent years. By introducing both the convex and concave relaxations of the problem, recently we have summarized and proposed the convex-concave relaxation procedure (CCRP). The CCRP has been proved to be strictly equivalent to the original discrete problem; by contrast, such a merit does not hold for the conventional relaxation approaches. However, the CCRP involves explicitly both convex and concave relaxations, which are typically difficult to find and thus greatly hinder its practical applications. Consequently, we have also proposed the simplified CCRP (SCCRP), which realizes exactly a type of CCRP but its concave relaxation can be realized in an inexplicit way. In the project we are to further investigate how to construct the convex relaxation also in an inexplicit way, so that the CCRP can be realized without involving the convex or concave relaxation explicitly; this actually implies a general algorithmic framework for different combinatorial graph optimizations. The new strategy provides not only a general way to construct state-of-the-art algorithms for different combinatorial optimization problems, but also a unified viewpoint to analyze them, which traditionally seem to have little relationship between each other. Though this project will focus on two typical combinatorial graph optimization problems in pattern analysis, graph matching and energy minimization, the idea can be generalized to other combinatorial optimization problems effortlessly, such as clustering, which inherently belongs also to combinatorial optimization.

模式分析中的很多重要问题本质为NP-hard组合图优化问题，如图匹配和能量最小化等。近年来松弛（连续）法逐渐成为求解这些问题的主要方法之一。通过引入问题的凸松弛及凹松弛函数，近期我们总结提出了凸凹松弛过程CCRP，它在理论上严格等价于原离散问题，这一优势是传统松弛法所不具备的。但CCRP需要构建凸\凹松弛函数，这一点其实非常困难。因此，我们随后提出了简化凸凹松弛过程，以一种简洁的方式实现了CCRP,其中的凹松弛函数可以自主构建。本课题将进一步研究凸松弛函数的自主构建方法，使得凸\凹松弛函数都无需显性构建，这也就意味着提出了一种通用的组合图优化问题解决框架。基于此框架我们将不仅可以用同一种方式提出不同问题的凸凹松弛算法，还能分析它们之间的内在联系。本课题将以图匹配和能量最小化这两个模式分析中的重要问题为主要实例来研究组合图优化问题，同时也将分析聚类等其它几个机器学习中本质为组合优化的问题。

模式分析中的很多重要问题本质为NP-hard组合图优化问题，如图匹配和能量最小化等。但多年来这些问题皆是从不同的角度出发，造成了方法不统一、彼此几乎没有联系、方法限制多以及效率低下等系列问题。本项目旨在提出一个统一的组合图优化问题的求解框架。.项目的主要研究内容如下：研究a)高效统一的组合图优化模型算法框架;b)针对不同应用场景下的图匹配模型和算法;c)高效通用的图匹配算法;d)通用的能量最小化算法等。.本项目的主要研究成果在于原创提出了一个组合图优化的高效、统一的组合图优化算法框架：渐非凸渐凹化过程GNCCP，并基于这个框架发展了针对多种不同应用场景的图匹配算法、二次指派算法、以及针对计算机视觉中的能量最小化问题提出了基于GNCCP的能量最小化算法。相对于常见的图匹配和能量最小化算法（如图割法和置信度传播算法等），基于GNCCP的算法不仅效率高效果好，并且适用范围大幅扩大。.总体来看，GNCCP不仅在理论上为不同的组合图优化问题提供了一个统一高效的松弛法框架，也在算法层面提供了一种简洁普适的实现方法（简洁到只需求取目标函数的梯度）。同时，在图匹配、能量最小化和二次指派等几个典型问题上验证了GNCCP的易用、高效和普适性。因此，无论在理论还是算法层面，GNCCP都是组合图优化研究的一个重要进展和创新，具有重要的科学意义。.在本项目的支持下，项目组成员在项目执行期内一共发表和接收了20余篇学术论文，包括SCI国际期刊论文16篇（其中12篇论文项目负责人为第一或者通讯作者），包括IEEE TPAMI、IJCV、IEEE TNNLS、IEEE T-cybernetics、PR等领域顶级期刊。成果也得到了多位IEEE Fellow和国内外院士的好评。