On the real-world applicability of state-of-the-art algorithms for the optimal camera placement problem

Optimal camera placement (OCP) is one of many practical applications of a core 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...

Full description

Saved in:
Bibliographic Details
Main Authors: Kritter, Julien, Brevilliers, Mathieu, Lepagnot, Julien, Idoumghar, Lhassane
Format: Conference Proceeding
Language:English
Subjects:
benchmark
Benchmark testing
Cameras
combinatorial optimization
Earth
Mathematical model
optimal camera placement
Optimization
set cover problem
Surveillance
Urban areas
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Optimal camera placement (OCP) is one of many practical applications of a core 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.
ISSN:2576-3555
DOI:10.1109/CoDIT.2019.8820295