RI: Small: Distributed Combinatorial Optimization for Crowd-Scene Analysis

Project: Research project

Project Details


This project develops efficient computer vision algorithms based on distributed message passing for solving crowd-scene analysis tasks such as detection and tracking of closely spaced individuals. These and other vision tasks can be formulated as discrete combinatorial optimization problems, e.g., binary linear or quadratic programs, and studying their underlying mathematical structure can yield insights that allow larger and more challenging problem instances to be addressed. Recent theoretical work proving the correctness of message passing for some classes of binary linear programming problems is being leveraged to develop practical vision algorithms for crowd scene analysis and extended to develop algorithms for finding good approximate solutions to harder problems. The project team is also exploring approximate inference methods based on randomization and on decomposition of large-scale problems into collections of interrelated subtasks that can be solved more efficiently and in parallel.

Automated vision systems can continuously monitor crowded public spaces to provide real-time situational awareness of crowd density and to detect early signs of dangerous behavior or deviations from normal traffic flow. The ability to track individuals through a crowd and to detect the interactions of groups of people has applications in the areas of homeland security, law enforcement, and defense. Results from this project will be disseminated through collaboration with other scholars, publication of peer-reviewed articles, presentations at professional meetings, introduction of course modules into the graduate and undergraduate computer science curriculum, and through public release of source code.

Effective start/end date9/1/128/31/18


  • National Science Foundation: $450,000.00


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.