Hybrid differential evolution algorithms for the optimal camera placement problem
| Date | 12 November 2018 |
| DOI | https://doi.org/10.1108/JSIT-09-2017-0081 |
| Published date | 12 November 2018 |
| Pages | 446-467 |
| Author | Mathieu Brévilliers,Julien Lepagnot,Lhassane Idoumghar,Maher Rebai,Julien Kritter |
| Subject Matter | Information & knowledge management,Information systems,Information & communications technology |
Hybrid differential evolution
algorithms for the optimal camera
placement problem
Mathieu Brévilliers,Julien Lepagnot and Lhassane Idoumghar
IRIMAS –Université de Haute-Alsace, Mulhouse, France
Maher Rebai
Ecole Supérieure d’Ingénieurs Léonard de Vinci, Paris, France, and
Julien Kritter
IRIMAS –Université de Haute-Alsace, Mulhouse, France
Abstract
Purpose –This paper aims to investigateto what extent hybrid differential evolution (DE) algorithmscan
be successfulin solving the optimal camera placementproblem.
Design/methodology/approach –This problem is statedas a unicost set coveringproblem (USCP) and
18 problem instances are defined accordingto practical operational needs. Three methods are selected from
the literature to solve these instances: a CPLEX solver, greedy algorithm and row weighting local search
(RWLS). Then, it is proposed to hybridize these algorithms with two hybrid DE approaches designed for
combinatorial optimizationproblems. The first one is a set-based approach (DEset) from the literature. The
second one is a new similarity-basedapproach (DEsim) that takes advantage of the geometriccharacteristics
of a camera to find better solutions.
Findings –The experimental study highlights that RWLS and DEsim-CPLEX are the best proposed
algorithms. Both easily outperform CPLEX, and it turns out that RWLS performs better on one class of
problem instances, whereas DEsim-CPLEX performs better on another class, depending on the minimal
resolutionneeded in practice.
Originality/value –Up to now, the efficiency of RWLS and the DEset approach has been investigated
only for a few problems. Thus, the first contributionis to apply these methods for the first time in the context
of camera placement. Moreover, new hybrid DE algorithms are proposed to solve the optimal camera
placement problem when stated as a USCP. The second main contribution is the design of the DEsim
approachthat uses the distance between camera locations to fully benefit from the DE mutationscheme.
Keywords Hybridization, Differential evolution, Combinatorial optimization,
Optimal camera placement, Row weighting local search, Unicost set covering problem
Paper type Research paper
1. Introduction
Nowadays, camera networks are widely used to monitor areas of interest. When connected
to an intelligent video surveillance system, it can help to automatically identify targets,
events or risks, depending on the given operational requirements. In this context,
determining the optimal placement of the cameras is of high importance because of the
underlying costs.
This work was supported by the French Agence Nationale de la Recherche (ANR) as part of the
OPMoPS project (ANR-16-SEBM-0004).
JSIT
20,4
446
Received29 September 2017
Revised31 January 2018
Accepted5 March 2018
Journalof Systems and
InformationTechnology
Vol.20 No. 4, 2018
pp. 446-467
© Emerald Publishing Limited
1328-7265
DOI 10.1108/JSIT-09-2017-0081
The current issue and full text archive of this journal is available on Emerald Insight at:
www.emeraldinsight.com/1328-7265.htm
For this kind of optimization problem, the area to be monitored and the camera
parameters (space coordinates and orientation angles) can be discretized to define the
following decision problem: given a set of candidate camera locations that cover some
discrete points of the area, find an optimal subset that satisfies the operational constraints
(Horster and Lienhart,2009).
Up to now, several coverage models have beenproposed in the literature (Mavrinac and
Chen, 2013;Zhang et al.,2015).In this paper, the problem is stated as a unicost set covering
problem (USCP), and this USCP model is used together with a three-dimensional model of
the monitored area. As already noticedin the literature, this 3D setting allows to avoid blind
spot due to major simplifications in a 2D setting (Zhang et al.,2013), but it leads to a
significant increase of the computational cost (Liu et al.,2016). For example, a bi-objective
variant of the problem (minimizing the total cost of the camera network while maximizing
the area coverage) has been recentlysolved optimally with exact methods (Rebai et al.,2016),
but at least 4 h of computation were needed for the largest instance, which was limited to a
3D grid of 15 15 7 discrete 3D points. It is, thus, of high interest to design new
algorithms that can find high-quality solutions in this much larger 3D search space.In this
work, the full coverage constraint is also considered: on the one hand, no blind spot is
allowed (which can be a strict requirement for some applications), and on the other hand, it
is known to make easier thedevelopment of person tracking algorithms (Liu et al.,2016).
According to a recent comprehensive survey (Liu et al., 2016), a wide range of methods
have already been implemented to solve different variants in this class of problems.
Actually, the optimal camera placement problem is often tackled by using binary integer
programming methods at first (David et al.,2007;Horster and Lienhart, 2009). However, as
soon as the size of the problem increases, these methods cannot find an optimal solution
within a reasonable run time. That is why approximation methods were also designed,
including greedy heuristics (Horster and Lienhart, 2009;Zhao, 2011), semi-definite
programming (Ercan et al.,2006;Zhao, 2011), simulated annealing algorithms (Zhao, 2011;
Liu et al.,2014), genetic algorithms (David et al., 2007;Van den Hengel et al., 2009), particle
swarm optimization algorithms (Morsly et al.,2012;Konda and Conci, 2013) and artificial
bee colony algorithms(Chrysostomou and Gasteratos, 2012).
This article focuses on a metaheuristic called differential evolution (DE), which was
originally designed for solving continuous optimization problems (Storn and Price, 1997).
This simple and efficient evolutionaryalgorithm is able to solve various theoretical and real-
world optimization problems (Das et al.,2016). In DE, a population of individuals (i.e.
candidate solutions)is evolving from generation to generation to converge on theglobal best
solution. A generation is composed of three evolutionary operators. Firstly, a mutation
operator creates a mutant individual by adding weighted differences to a reference
individual. The most common DE mutation scheme, called DE/rand/1, is formulated as
follows. For each variablejof each individual iof the population Pop:
Muti;j¼Popr1;jþFPopr2;jPopr3;j
(1)
where Mut refers to the mutant population, r1,r2and r3to three randomly chosen
individuals of Pop such that r16¼ r26¼ r36¼ iand F
e
0;1
½
to the DE scaling factor. As soon
as a variable gets out of the search space due to equation (1), a new appropriate random
value is generated. Secondly, a crossover operator is applied, generating a trial individual
from a current individual andits corresponding mutant individual by using the classical so-
called binomial crossover. Thirdly, a selection operator replaces any current individual in
Pop with its corresponding trialindividual, if the latter performs better.
Optimal
camera
placement
problem
447
To continue reading
Request your trial