On the optimal placement of cameras for surveillance and the underlying set cover problem

摘要

Given a delimited surveillance area, represented in either 2D or 3D, and a set of feasible camera locations and orientations, the optimal camera placement problem (OCP) is that of identifying camera configurations which optimise a predefined objective under a set of application-specific constraints. While this problem appears in many modern applications such as area surveillance, target tracking, photogrammetry or traffic and crowd analysis, it finds its roots in one of Karp's 21 original NP-complete problems: set cover (SCP). If the two problems are often structurally identical, many papers dealing with optimal camera placement use this relationship implicitly, and a lot of the work done on the SCP has yet to find its way into the literature of the applied problem. In this survey, we review both in terms of problem modelling, preprocessing and solving approaches, and attempt to bring them together by suggesting open lines of research for future works. (C) 2018 Elsevier B.V. All rights reserved.