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.