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

人们普遍认为，识别图像中的对象和视频中的人类活动-计算机视觉中的基本问题-可以通过考虑对象（活动）部分，上下文及其时空关系来显着改善。这是因为这些约束有助于在不确定性面前解决模糊的假设。由于部件和上下文可以通过图形模型（例如，条件随机场），对象和活动识别往往制定为概率推理的图形模型。该项目开发了一个新的图形模型的理论框架，明确编码对象之间的高阶，时空，层次和上下文交互本项目的主要工作包括：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.