Home

Benchmark testbed
on the Optimal Camera Placement Problem (OCP)
and the Unicost Set Covering Problem (USCP)

Introduction

The use of camera networks is now common to perform various surveillance tasks. Due to the prohibitive cost of setting or modifying such a camera network, it is required to provide a priori a configuration that minimizes the number of cameras in addition to meeting the operational needs. The optimal camera placement problem (OCP) is thus of critical importance, and can be generically formulated as follows. Given various constraints, usually related to coverage or image quality, and an objective to optimise (typically, the cost), how can the set of positions and orientations which best (optimally) meets the requirements be determined?

The objective considered here is to determine camera locations and orientations which ensure complete coverage of the area while minimizing the cost of the infrastructure. To this aim, the surveillance area is reduced to a set of three-dimensional sample points to be covered, and camera configurations are sampled into so-called candidates each with a given set of position and orientation coordinates.

Now, the OCP comes down to select the smallest subset of candidates which covers all the samples.

The OCP is structurally identical to the unicost set covering problem (USCP), which is one of Karp's well-known NP-hard problems, and which can be stated as follows: given a set of elements I (rows) to be covered, and a collection of sets J (columns) such that the union of all sets in J is I, find the smallest subset C of J such that C covers I.

Many papers dealing with the OCP use this relationship implicitly, but few works done on the USCP have been applied or adapted to the OCP, and vice versa. In very recent years however, approaches from the USCP literature have been successfully applied in the OCP context: it suggests that bridges can be built between these two bodies of literature to improve the results obtained so far on both USCP and OCP problems.

The main goal of this benchmark testbed is to encourage innovative research works in this direction, by proposing to solve OCP problem instances stated as USCP.

Short description

This benchmark testbed gathers 69 OCP problem instances:

  • A first set of 32 artificially generated instances (so-called "academic instances") is provided: various sizes and discretizations of an empty room modeled by a rectangular cuboid with cameras on the ceiling.
  • A second set of 37 real-world instances can also be found alongside the academic ones: various sizes and discretizations of urban areas with cameras on the walls of the buildings.

Actually, a subset of the academic problems listed in this benchmark was first introduced in [1], and the method used to generate all real-world instances of this benchmark is presented in [2]. For these reasons, any publication related to this benchmark testbed should refer to it by citing the articles [1, 2] and by adding a link to the benchmark website [3]:

[1] Brévilliers M., Lepagnot J., Idoumghar L., Rebai M. and Kritter J. (2018), Hybrid Differential Evolution Algorithms for the Optimal Camera Placement Problem, Journal of Systems and Information Technology, Special issue on Optimisation Solutions in Systems, Vol.20 No.4, pp.446-467, Emerald. https://doi.org/10.1108/JSIT-09-2017-0081
[2] Kritter J., Brévilliers M., Lepagnot J. and Idoumghar L. (2019), On the Real-World Applicability of State-of-the-Art Algorithms for the Optimal Camera Placement Problem, 6th International Conference on Control, Decision and Information Technologies (IEEE CoDIT’19), Paris, France. https://doi.org/10.1109/CoDIT.2019.8820295
[3] http://www.mage.fst.uha.fr/brevilliers/ocp-uscp-benchmark/

The whole benchmark testbed has been introduced for the GECCO 2020 Competition on the OCP and the USCP. A second edition of this competition has been hosted by GECCO 2021. For more information, please refer to the websites devoted to these competitions:

Documentation and data files are available for download in the section just below. History of the results obtained so far is also provided.

Please, feel free to contact the authors to update these files, whether it is to fix an error or to add new results.

Downloads

  • Documentation file (~562Kb) PDF
  • Problem instance compressed archive (~1Gb, and ~18Gb once decompressed) TAR.XZ
  • Spreadsheet file with the history of the results obtained so far (~36Kb) ODS

Authors and affiliation

Mathieu Brévilliers*, Julien Kritter, Julien Lepagnot, and Lhassane Idoumghar,
Université de Haute-Alsace, IRIMAS UR 7499, F-68100 Mulhouse, France.

*Coresponding author: mathieu.brevilliers@uha.fr.

IRIMAS

Acknowledgement

This work was funded as part of the French-German OPMoPS project, by the French Agence Nationale de la Recherche (under grant number ANR-16-SEBM-0004) and the German Bundesministerium für Bildung und Forschung.

OPMoPS
ANR BMBF

News and updates

  • July 11, 2021 : Results of the GECCO 2021 Competition on the OCP and the USCP are added in the history spreadsheet file.
  • June 29, 2021 : Update of the best known lower bounds in the history spreadsheet file.
  • June 25, 2021 : The benchmark website is online.