RI: Medium: Collaborative Research: Object and Activity Recognition as the Maximum Weight Subgraph Problem with Mutual Exclusion Constraints

人们普遍认为，识别图像中的对象和视频中的人类活动--计算机视觉中的基本问题--可以通过考虑对象(活动)部分、上下文及其时空关系来显著改善。这是因为这些约束有助于在面对不确定性的情况下解决模糊的假设。由于部件和上下文可以通过图形模型(例如，条件随机场)有效地建模，因此对象和活动识别通常被表示为图形模型的概率推断。该项目发展了一种新的图形模型理论框架，将对象(活动)之间的高阶、时空、层次和上下文的交互显式编码为二次互斥约束(QMC)，用于图像和视频中的对象和活动识别。该项目的主要贡献包括：1)视点不变的对象和活动识别方法；2)表示对象和人类活动的图形模型的学习和推理公式，如寻找QMC下的最大权子图(MWS)；3)求解QMC下的MWS问题的多项式时间算法；4)所提出的学习和推理算法具有明确的性能界限和紧性和收敛的理论保证。该项目框架对来自感兴趣领域的硬约束进行编码，这些约束在以前的工作中从未使用过，并使用原则性的多项式时间算法进行学习和推理。该项目的研究推进了目标和活动识别的技术水平，并使新的应用成为可能，包括视频监控、从大数据集中检索和感知移动机器人。

It has been widely acknowledged that recognizing objects in images, and human activities in video - the basic problems in computer vision - can be significantly improved by accounting for object (activity) parts, context, and their spatiotemporal relationships. This is because these constraints facilitate resolving ambiguous hypotheses in the face of uncertainty. Since parts and contexts can be efficiently modeled by graphical models (e.g., Conditional Random Field), object and activity recognition are often formulated as probabilistic inference of graphical models. The project develops a new theoretical framework of graphical models that explicitly encodes high-order, spatiotemporal, hierarchical, and contextual interactions among objects (activities) as Quadratic Mutual-Exclusion Constraints (QMCs), for the purposes of object and activity recognition in images and video.The key contributions of the project work include: 1) Approaches to view-invariant object and activity recognition; 2) Formulations of learning and inference of graphical models representing objects and human activities, as finding a maximum weight subgraph (MWS) under the QMCs; 3) Polynomial-time algorithms for solving the MWS problem subject to QMCs; and 4) Explicit performance bounds and theoretical guarantees of tightness and convergence of the proposed learning and inference algorithms. The project framework encodes hard constraints from the domain of interest that have never been used in prior work, and uses principled, polynomial-time algorithms for learning and inference. The research of this project advances the state of the art in object and activity recognition, and enables new applications including video surveillance, retrieval from large datasets, and perception of mobile robots.