Abstract

While the theoretical foundation of the optimal camera placement problem has been studied for decades, its practical implementation has recently attracted significant research interest due to the increasing popularity of visual sensor networks. The most flexible formulation of finding the optimal camera placement is based on a binary integer programming (BIP) problem. Despite the flexibility, most of the resulting BIP problems are NP-hard and any such formulations of reasonable size are not amenable to exact solutions. There exists a myriad of approximate algorithms for BIP problems, but their applications, efficiency, and scalability in solving camera placement are poorly understood. Thus, we develop a comprehensive framework in comparing the merits of a wide variety of approximate algorithms in solving the optimal camera placement problems. We first present a general approach of adapting these problems into BIP formulations. Then, we demonstrate how they can be solved using different approximate algorithms including greedy heuristics, Markov-chain Monte Carlo, simulated annealing, and linear and semidefinite programming relaxations. The accuracy, efficiency, and scalability of each technique are analyzed and compared in depth. Extensive experimental results are provided to illustrate the strength and weakness of each method.

Document Type

Article

Publication Date

11-1-2013

Notes/Citation Information

Published in International Journal of Distributed Sensor Networks, v. 2013, article ID 241913, p. 1-15.

Copyright © 2013 Jian Zhao et al.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Digital Object Identifier (DOI)

https://doi.org/10.1155/2013/241913

Download

Share

COinS