The 𝒩𝒫-hard minimum set cover problem (SCP) is a very typical model to use when attempting to formalise optimal camera placement (OCP) applications. In a generic form, the OCP problem relates to the positioning of individual cameras such that the overall network is able to cover a given area while meeting a set of application-specific requirements (image quality, redundancy, ...) and optimising an objective, typically minimum cost or maximum coverage. In this paper, we focus on an application called global or persistent surveillance: camera networks which ensure full coverage of a given area. As preliminary work, an instance generation pipeline is proposed to create OCP instances from real-world data and solve them using existing literature. The computational cost of both the instance generation process and the solving algorithms however highlights a need for more efficient methods for decision makers to use in real-world settings. In this paper, we therefore propose to review the suitability of the approach, and more specifically to question two key elements: the impact of sampling frequencies and the importance of rigid full-coverage constraints. The results allow us to quickly provide decision makers with an overview of available solutions and trade-offs.
Keywords: Combinatorial optimization, optimal camera placement, set cover problem
@article{RO_2021__55_4_2069_0,
author = {Kritter, Julien and Br\'evilliers, Mathieu and Lepagnot, Julien and Idoumghar, Lhassane},
title = {On the computational cost of the set cover approach for the optimal camera placement problem and possible set-cover-inspired trade-offs for surveillance infrastructure design},
journal = {RAIRO. Operations Research},
pages = {2069--2091},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {4},
doi = {10.1051/ro/2021092},
mrnumber = {4282587},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021092/}
}
TY - JOUR AU - Kritter, Julien AU - Brévilliers, Mathieu AU - Lepagnot, Julien AU - Idoumghar, Lhassane TI - On the computational cost of the set cover approach for the optimal camera placement problem and possible set-cover-inspired trade-offs for surveillance infrastructure design JO - RAIRO. Operations Research PY - 2021 SP - 2069 EP - 2091 VL - 55 IS - 4 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021092/ DO - 10.1051/ro/2021092 LA - en ID - RO_2021__55_4_2069_0 ER -
%0 Journal Article %A Kritter, Julien %A Brévilliers, Mathieu %A Lepagnot, Julien %A Idoumghar, Lhassane %T On the computational cost of the set cover approach for the optimal camera placement problem and possible set-cover-inspired trade-offs for surveillance infrastructure design %J RAIRO. Operations Research %D 2021 %P 2069-2091 %V 55 %N 4 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021092/ %R 10.1051/ro/2021092 %G en %F RO_2021__55_4_2069_0
Kritter, Julien; Brévilliers, Mathieu; Lepagnot, Julien; Idoumghar, Lhassane. On the computational cost of the set cover approach for the optimal camera placement problem and possible set-cover-inspired trade-offs for surveillance infrastructure design. RAIRO. Operations Research, Tome 55 (2021) no. 4, pp. 2069-2091. doi: 10.1051/ro/2021092
[1] and , Wireless sensor deployment for 3D coverage with constraints. In: 2009 Sixth International Conference on Networked Sensing Systems (INSS). IEEE (2009). | DOI
[2] , and , Optimal deployment of cameras for video surveillance systems. In: 2007 IEEE Conference on Advanced Video and Signal Based Surveillance. IEEE (2007). | DOI
[3] , An algorithm for set covering problem. Eur. J. Oper. Res. 31 (1987) 85–93. | MR | Zbl | DOI
[4] , OR-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41 (1990) 1069–1072. | DOI
[5] , A lagrangean heuristic for set covering problems. In: Combinatorial Optimization. Springer, Berlin Heidelberg (1992) 325–326. | MR | Zbl | DOI
[6] and , Enhancing an algorithm for set covering problems. Eur. J. Oper. Res. 58 (1992) 293–300. | Zbl | DOI
[7] , and , Multi-camera positioning to optimize task observability. In: Proceedings IEEE Conference on Advanced Video and Signal Based Surveillance, 2005. IEEE (2005). | DOI
[8] , , and , Parallel preprocessing for the optimal camera placement problem. Int. J. Model. Optim. 8 (2018) 33–40.
[9] , , , and , Hybrid differential evolution algorithms for the optimal camera placement problem. J. Syst. Inf. Technol. 20 (2018) 446–467. | DOI
[10] , A greedy heuristic for the set-covering problem. Math. Oper. Res. 4 (1979) 233–235. | MR | Zbl | DOI
[11] and , Camera placement using particle swarm optimization in visual surveillance applications. In: 2009 16th IEEE International Conference on Image Processing (ICIP). IEEE (2009).
[12] and , Automatic sensor placement from vision task requirements. IEEE Trans. Pattern Anal. Mach. Intell. 10 (1988) 407–416. | DOI
[13] , A note on two problems in connexion with graphs. Numer. Math. 1 (1959) 269–271. | MR | Zbl | DOI
[14] and , Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements. Comput. Vision Image Understand. 103 (2006) 156–169. | DOI
[15] and , Coverage in Arbitrary 3D Environments: The Art Gallery Problem in Shooter Games. IEEE (2013).
[16] , A threshold of ln for approximating set cover. J. ACM 45 (1998) 634–652. | MR | Zbl | DOI
[17] and , A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8 (1989) 67–71. | MR | Zbl | DOI
[18] , , and , An efficient local search heuristic with row weighting for the unicost set covering problem. Eur. J. Oper. Res. 246 (2015) 750–761. | MR | DOI
[19] , and , A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4 (1968) 100–107. | DOI
[20] and , Approximating optimal visual sensor placement: In 2006 IEEE International Conference on Multimedia and Expo. IEEE (2006). | DOI
[21] IBM. IBM CPLEX Optimiser. https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer. Accessed: 2018-12-03.
[22] , , and , Optimal sensor placement for surveillance of large spaces. In: 2009 Third ACM/IEEE International Conference on Distributed Smart Cameras (ICDSC). IEEE (2009). | DOI
[23] , Reducibility among combinatorial problems. In: Complexity of Computer Computations. Springer, US (1972) 85–103. | MR | Zbl | DOI
[24] and , Optimal configuration of PTZ camera networks based on visual quality assessment and coverage maximization. In: 2013 Seventh International Conference on Distributed Smart Cameras (ICDSC). IEEE (2013). | DOI
[25] , , and , On the optimal placement of cameras for surveillance and the underlying set cover problem. Appl. Soft Comput. 74 (2019) 133–153. | DOI
[26] , , and , On the real-world applicability of state-of-the-art algorithms for the optimal camera placement problem. In: 6th 2019 International Conference on Control, Decision and Information Technologies (CoDIT). IEEE (2019).
[27] , , and , On the use of human-assisted optimisation for the optimal camera placement problem and the surveillance of urban events. In: 7th 2020 International Conference on Control, Decision and Information Technologies (CoDIT). IEEE (2020).
[28] , and , An effective and simple heuristic for the set covering problem. Eur. J. Oper. Res. 176 (2007) 1387–1403. | MR | Zbl | DOI
[29] , and , Recent advances in camera planning for large area surveillance. ACM Comput. Surv. 49 (2016) 1–37. | DOI
[30] and , An iterated heuristic algorithm for the set covering problem. In: 2nd Workshop on Algorithm Engineering (WAE98). Saarbreucken (1998) 155–166.
[31] MeshLab. http://www.meshlab.net. Accessed: 2018-12-03.
[32] and , Fast, minimum storage ray-triangle intersection. J. Graphics Tools 2 (1997) 21–28. | DOI
[33] , and , On the best interceptor placement for an optimally deployed visual sensor network. In: 2010 IEEE International Conference on Systems, Man and Cybernetics. IEEE (2010). | DOI
[34] and , Coverage algorithms for visual sensor networks. ACM Trans. Sensor Netw. 9 (2013) 1–36. | DOI
[35] , , , and , Coverage optimization to support security monitoring. Comput. Environ. Urban Syst. 31 (2007) 133–147. | DOI
[36] and , Optimal camera placement for accurate reconstruction. Pattern Recogn. 35 (2002) 927–944. | Zbl | DOI
[37] OpenStreetMap, Elements – OpenStreetMap wiki. https://wiki.openstreetmap.org/wiki/Elements. Accessed: 2018-12-03.
[38] OpenStreetMap. Map features – OpenStreetMap wiki. https://wiki.openstreetmap.org/wiki/Map_Features. Accessed: 2018-12-03
[39] , Art Gallery Theorems and Algorithms. In: Vol. 3 of International Series of Monographs on Computer Science. Oxford University Press (1987). | MR | Zbl
[40] OSM2World, OSM2World. http://osm2world.org. Accessed: 2018-12-03
[41] , , and , Exact biobjective optimization methods for camera coverage problem in three-dimensional areas. IEEE Sensors J. 16 (2016) 3323–3331. | DOI
[42] , , and , Finding a “kneedle’’ in a haystack: detecting knee points in system behavior. In: 2011 31st International Conference on Distributed Computing Systems Workshops. IEEE (2011).
[43] , and , A 3-flip neighborhood local search for the set covering problem. Eur. J. Oper. Res. 172 (2006) 472–499. | MR | Zbl | DOI
[44] , , , , and , Sensor planning for automated and persistent object tracking with multiple cameras. In: 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE (2008). | DOI
[45] , , , , , , and , An optimized placement algorithm for collaborative information processing at a wireless camera network. In: 2013 IEEE International Conference on Multimedia and Expo (ICME). IEEE (2013). | DOI
Cité par Sources :
