On the real-world applicability of state-of-the-art algorithms for the optimal camera placement problem
Authors:
- 1 April 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1103-1108
Abstract
Optimal camera placement (OCP) is one of many practical applications of a core $\mathcal{NP}$ -complete problem in the field of combinatorial optimisation: set cover (SCP). In a generic form, the OCP problem relates to the positioning and setting up of individual cameras such that the overall network is able to cover a given area while meeting a set of application-specific constraints (such as image quality or redundancy) and optimising an objective, typically minimum cost or maximum coverage, depending on the application's focus. In this paper, we consider the problem of positioning and orienting a minimal number of cameras such that the network is able to reach full coverage. More specifically, we introduce a framework for OCP instance generation which leaves the common realm of academic study cases and models the problem in real-world settings, using 8 West-European cities for numerical tests. A baseline is established by running several basic algorithms, which serve as a starting point for a more focused benchmark involving various state-of-the-art algorithms from both OCP and SCP literature. The results are then discussed and several elements highlighted for future research.
Keywords
This publication has 23 references indexed in Scilit:
- Coverage algorithms for visual sensor networksACM Transactions on Sensor Networks, 2013
- A New Formulation of the Set Covering Problem for Metaheuristic ApproachesISRN Operations Research, 2013
- A Sensor Placement Approach for the Monitoring of Indoor Scenes2007
- An effective and simple heuristic for the set covering problemEuropean Journal of Operational Research, 2007
- Automated camera layout to satisfy task-specific and floor plan-specific coverage requirementsComputer Vision and Image Understanding, 2006
- A 3-flip neighborhood local search for the set covering problemEuropean Journal of Operational Research, 2006
- Fast, Minimum Storage Ray-Triangle IntersectionJournal of Graphics Tools, 1997
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- A probabilistic heuristic for a computationally difficult set covering problemOperations Research Letters, 1989
- An algorithm for set covering problemEuropean Journal of Operational Research, 1987