Approximate techniques in solving optimal camera placement problems

Jian Zhao, Ruriko Yoshida, Sen Ching Samson Cheung, David Haws

Research output: Contribution to journalArticlepeer-review

50 Scopus citations

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.

Original languageEnglish
Article number241913
JournalInternational Journal of Distributed Sensor Networks
Volume2013
DOIs
StatePublished - 2013

ASJC Scopus subject areas

  • General Engineering
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Approximate techniques in solving optimal camera placement problems'. Together they form a unique fingerprint.

Cite this