{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:39Z","timestamp":1740144519042,"version":"3.37.3"},"reference-count":45,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T00:00:00Z","timestamp":1625702400000},"content-version":"vor","delay-in-days":7,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-SEBM-0004"],"award-info":[{"award-number":["ANR-16-SEBM-0004"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2021,6,17]]},"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>The \ud835\udca9\ud835\udcab-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.<\/jats:p>","DOI":"10.1051\/ro\/2021092","type":"journal-article","created":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T08:05:26Z","timestamp":1624262726000},"page":"2069-2091","source":"Crossref","is-referenced-by-count":0,"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"],"prefix":"10.1051","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0450-4287","authenticated-orcid":false,"given":"Julien","family":"Kritter","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3175-6268","authenticated-orcid":false,"given":"Mathieu","family":"Br\u00e9villiers","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0152-6613","authenticated-orcid":false,"given":"Julien","family":"Lepagnot","sequence":"additional","affiliation":[]},{"given":"Lhassane","family":"Idoumghar","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2021,7,8]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Andersen T. and Tirthapura S., Wireless sensor deployment for 3D coverage with constraints. In: 2009 Sixth International Conference on Networked Sensing Systems (INSS). IEEE (2009).","DOI":"10.1109\/INSS.2009.5409946"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Angella F., Reithler L. and Gallesio F., Optimal deployment of cameras for video surveillance systems. In: 2007 IEEE Conference on Advanced Video and Signal Based Surveillance. IEEE (2007).","DOI":"10.1109\/AVSS.2007.4425342"},{"key":"R3","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0377-2217(87)90141-X","volume":"31","author":"Beasley","year":"1987","journal-title":"Eur. J. Oper. Res."},{"key":"R4","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1057\/jors.1990.166","volume":"41","author":"Beasley","year":"1990","journal-title":"J. Oper. Res. Soc."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Beasley J.E., A lagrangean heuristic for set covering problems. In: Combinatorial Optimization. Springer, Berlin Heidelberg (1992) 325\u2013326.","DOI":"10.1007\/978-3-642-77489-8_38"},{"key":"R6","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0377-2217(92)90215-U","volume":"58","author":"Beasley","year":"1992","journal-title":"Eur. J. Oper. Res."},{"key":"R7","unstructured":"Bodor R., Schrater P. and Papanikolopoulos N., Multi-camera positioning to optimize task observability. In: Proceedings IEEE Conference on Advanced Video and Signal Based Surveillance, 2005. IEEE (2005)."},{"key":"R8","doi-asserted-by":"crossref","first-page":"33","DOI":"10.7763\/IJMO.2018.V8.621","volume":"8","author":"Br\u00e9villiers","year":"2018","journal-title":"Int. J. Model. Optim."},{"key":"R9","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1108\/JSIT-09-2017-0081","volume":"20","author":"Br\u00e9villiers","year":"2018","journal-title":"J. Syst. Inf. Technol."},{"key":"R10","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"Chv\u00e1tal","year":"1979","journal-title":"Math. Oper. Res."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Conci N. and Lizzi L., Camera placement using particle swarm optimization in visual surveillance applications. In: 2009 16th IEEE International Conference on Image Processing (ICIP). IEEE (2009).","DOI":"10.1109\/ICIP.2009.5413833"},{"key":"R12","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1109\/34.3905","volume":"10","author":"Cowan","year":"1988","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"R13","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"R14","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/j.cviu.2006.06.005","volume":"103","author":"Erdem","year":"2006","journal-title":"Comput. Vision Image Understand."},{"key":"R15","unstructured":"Fantini E.P.C. and Chaimowicz L., Coverage in Arbitrary 3D Environments: The Art Gallery Problem in Shooter Games. IEEE (2013)."},{"key":"R16","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"Feige","year":"1998","journal-title":"J. ACM"},{"key":"R17","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0167-6377(89)90002-3","volume":"8","author":"Feo","year":"1989","journal-title":"Oper. Res. Lett."},{"key":"R18","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1016\/j.ejor.2015.05.038","volume":"246","author":"Gao","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"R19","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Horster E. and Lienhart R., Approximating optimal visual sensor placement: In 2006 IEEE International Conference on Multimedia and Expo. IEEE (2006).","DOI":"10.1109\/ICME.2006.262766"},{"key":"R21","unstructured":"IBM. IBM CPLEX Optimiser. https:\/\/www-01.ibm.com\/software\/commerce\/optimization\/cplex-optimizer. Accessed: 2018-12-03."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Indu S., Chaudhury S., Mittal N. and Bhattacharyya A., Optimal sensor placement for surveillance of large spaces. In: 2009 Third ACM\/IEEE International Conference on Distributed Smart Cameras (ICDSC). IEEE (2009).","DOI":"10.1109\/ICDSC.2009.5289398"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Karp R.M., Reducibility among combinatorial problems. In: Complexity of Computer Computations. Springer, US (1972) 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"Konda K.R. and Conci N., 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":"10.1109\/ICDSC.2013.6778202"},{"key":"R25","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.asoc.2018.10.025","volume":"74","author":"Kritter","year":"2019","journal-title":"Appl. Soft Comput."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"Kritter J., Br\u00e9villiers M., Lepagnot J. and Idoumghar L., 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).","DOI":"10.1109\/CoDIT.2019.8820295"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"Kritter J., Br\u00e9villiers M., Lepagnot J. and Idoumghar L., 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).","DOI":"10.1109\/CoDIT49905.2020.9263977"},{"key":"R28","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1016\/j.ejor.2005.09.028","volume":"176","author":"Lan","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"R29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2906148","volume":"49","author":"Liu","year":"2016","journal-title":"ACM Comput. Surv."},{"key":"R30","unstructured":"Marchiori E. and Steenbeek A., An iterated heuristic algorithm for the set covering problem. In: 2nd Workshop on Algorithm Engineering (WAE98). Saarbreucken (1998) 155\u2013166."},{"key":"R31","unstructured":"MeshLab. http:\/\/www.meshlab.net. Accessed: 2018-12-03."},{"key":"R32","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1080\/10867651.1997.10487468","volume":"2","author":"M\u00f6ller","year":"1997","journal-title":"J. Graphics Tools"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"Morsly Y., Djouadi M.S. and Aouf N., 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":"10.1109\/ICSMC.2010.5642200"},{"key":"R34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2489253.2489262","volume":"9","author":"Munishwar","year":"2013","journal-title":"ACM Trans. Sensor Netw."},{"key":"R35","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.compenvurbsys.2006.06.002","volume":"31","author":"Murray","year":"2007","journal-title":"Comput. Environ. Urban Syst."},{"key":"R36","doi-asserted-by":"crossref","first-page":"927","DOI":"10.1016\/S0031-3203(01)00076-0","volume":"35","author":"Olague","year":"2002","journal-title":"Pattern Recogn."},{"key":"R37","unstructured":"OpenStreetMap, Elements \u2013 OpenStreetMap wiki. https:\/\/wiki.openstreetmap.org\/wiki\/Elements. Accessed: 2018-12-03."},{"key":"R38","unstructured":"OpenStreetMap. Map features \u2013 OpenStreetMap wiki. https:\/\/wiki.openstreetmap.org\/wiki\/Map_Features. Accessed: 2018-12-03"},{"key":"R39","unstructured":"O\u2019Rourke J., Art Gallery Theorems and Algorithms. In: Vol. 3 of International Series of Monographs on Computer Science. Oxford University Press (1987)."},{"key":"R40","unstructured":"OSM2World, OSM2World. http:\/\/osm2world.org. Accessed: 2018-12-03"},{"key":"R41","doi-asserted-by":"crossref","first-page":"3323","DOI":"10.1109\/JSEN.2016.2519451","volume":"16","author":"Rebai","year":"2016","journal-title":"IEEE Sensors J."},{"key":"R42","doi-asserted-by":"crossref","unstructured":"Satopaa V., Albrecht J., Irwin D. and Raghavan B., Finding a \u201ckneedle\u2019\u2019 in a haystack: detecting knee points in system behavior. In: 2011 31st International Conference on Distributed Computing Systems Workshops. IEEE (2011).","DOI":"10.1109\/ICDCSW.2011.20"},{"key":"R43","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1016\/j.ejor.2004.10.018","volume":"172","author":"Yagiura","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"R44","unstructured":"Yao Y., Chen C.-H., Abidi B., Page D., Koschan A. and Abidi M., Sensor planning for automated and persistent object tracking with multiple cameras. In: 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE (2008)."},{"key":"R45","unstructured":"Zhang H., Xia L., Tian F., Wang P., Cui J., Tang C., Deng N. and Ma N., 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)."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2021092\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T08:20:44Z","timestamp":1625732444000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2021092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":45,"journal-issue":{"issue":"4"},"alternative-id":["ro190434"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2021092","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}