Particle Swarm Optimization Inspired Computer Science Essay

Published:

1Abstract-In this paper, a novel method based on Binary Particle Swarm Optimization BPSO inspired probability is proposed to solve the camera placement problem. Ensuring accurate visual coverage of the monitoring space with a minimum number of cameras is sought. The visual coverage is defined by realistic and consistent assumptions taking into account camera characteristics. In total, seven evolutionary algorithms based on Binary Particle Swarm optimizations and genetic techniques are adapted to solve this visual coverage based camera placement problem. All these techniques are introduced in a new and effective framework dealing with constrained optimizations. The performance of the BPSO inspired probability technique is compared with the performances of the adapted stochastic variants (genetic algorithm based, immune systems based...etc) of optimization based particle swarm algorithms. Simulation results for 2D and 3D scenarios show the efficiency of the proposed technique. Indeed, in a large scale dimension case, BPSO inspired probability gives better results than the ones obtained by adapting all other variants of BPSO techniques.

Index Terms- Evolutionary computation, Particle swarm optimization, Sensor networks.

NTRODUCTION

Lady using a tablet
Lady using a tablet

Professional

Essay Writers

Lady Using Tablet

Get your grade
or your money back

using our Essay Writing Service!

Essay Writing Service

Sensor networks are deployed and used in different civilian and military applications for which networked sensors are treated as a shared infrastructure that can serve multiple users. One of those important applications is surveillance and security in public places where there has been a surge in the number of surveillance' cameras put in service recently. Networking these cameras deployed at judicious locations should guarantee coverage as well as image quality to the networked video streams.

Sensor placement is formulated to satisfy coverage constraints based on the subject to be covered (area versus discrete points) and the sensor deployment mechanisms (random versus deterministic). Identifying an optimal configuration of multiple sensors in order to observe the maximum space with a given number of sensors is a combinatorial optimization problem that is NP-hard [1]. This means that simple enumeration and search techniques will likely have a great difficulty in identifying optimal placement configurations. Placement of surveillance cameras using optimization techniques requires optimizing sensor configuration and a visibility analysis across the scene space.

Standard Linear Programming methods can be applied to solve this placement problem. However, it will be infeasible for large scale problem due to the large number of enumerating solutions. To remedy for this issue, evolutionary techniques, which are known as good optimizers especially in large scale, are envisaged. Binary Particle Swarm Optimization (BPSO), [2] [3] [4], is an ideal candidate as it seems to be more efficient than others evolutionary algorithms for solving such a binary problem. Having said this, Particle Swarm Optimization techniques still suffer in guaranteeing global optimums. In order to avoid local optimum, we present in this paper an efficient Binary Particle Swarm optimization inspired probability 'BPSO-IP' based approach for optimizing the spatial visual coverage of a 2D and 3D security monitoring environment.

The rest of the paper is given as follows: Section II reviews the associated literature on this topic. In Section III, modeling the vision sensor placement and formulating its optimization problem is proposed. 'BPSO-IP' algorithm and some modified 'BPSO' techniques are given in Section IV, while section V assesses and discusses the results obtained for different scenarios. The last section concludes the paper by elaborating on the importance of the work and suggests envisaged research extensions.

Background

In modern society, security monitoring is a necessity. The increasing social demand for security leads to a growing need for surveillance activities in various environments, such as transport infrastructure and public places like banks, museums, department stores and parking lots. As cameras are used in greater numbers to monitor large areas, the deployment efficiency of such equipments becomes critical and crucial as it can directly impact the best use of these allocated resources in terms of cost and surveillance objectives. In video sensor networks, the layout of cameras should assure a minimum level of image quality to satisfy certain surveillance tasks, for instance: sufficient spatial resolution, field of view depth, servo speed for pan-tilt-zoom cameras,...etc.

Related work on terrain model acquisition for motion planning has focused on the movement of a robot in an unexplored 'sensor field' [5]. While knowledge of the terrain is vital for surveillance, it does not directly solve the sensor placement problem. Self-deployment of mobile sensors based on the notion of potential fields is presented in [6]. However, self deployment does not provide a solution in case of static sensors that need to be deployed in a specific configuration for applications such as scene monitoring.

Lady using a tablet
Lady using a tablet

Comprehensive

Writing Services

Lady Using Tablet

Plagiarism-free
Always on Time

Marked to Standard

Order Now

In Computational Geometry, very good progress has been made in solving optimal guard location problems for a polygonal area, e.g., Art Gallery Problem (AGP) and its variants, where the task is to determine a minimal number of guards and their static positions, such that all points in a polygon are observed [7]. In a similar vein, Floodlight Illumination Problems deal with the illumination of planar regions by light sources [8]. Current solutions to AGP and its variants employ unrealistic assumptions about camera's capabilities such as unlimited field of view, infinite depth of field, and/or infinite servo precision and speed. These assumptions make these algorithms unsuitable for most real-world computer vision applications. In fact, one objective of our work is to bridge the gap between the highly theoretical, well-established computational geometry and more realistic requirements of computer vision.

A survey of sensor planning methods that employ more realistic assumptions is given in [9]. In the latest published works, [10] presented a probabilistic sensor planning framework with a 'visibility analysis' which evaluates the visibility of potential subjects over possible camera configurations. Their approach differs from our approach in a number of points. They model environments with a given object density and we model environments with a given set of coverage and cost constraints. They use a local optimization method to solve a highly nonlinear constrained optimization problem. We employ a global optimization method to solve a linear optimization problem over binary variables.

The problem of determining the coverage provided by a given placement of sensors has also been discussed in [11]. Sensor placement on two-and three-dimensional grids has been formulated as a combinatorial optimization problem, and solved using integer linear programming [12]. Some other works in the area of coverage problems and sensor deployment, with sensors sensing events that occur within a distance of the sensing range of the sensor, are presented in [13] and [14].

In [15] authors presented a new and more realistic visual sensor model in two and three dimensional cases. A Binary Integer linear programming 'BILP' approach to determine the minimum cost of a sensor array (fixed sensors with pan and tilt freedom) that covers a given full space is presented there. However, this kind of approaches, [15], [16] suffers from computational complexity that makes them infeasible on large scale problems that we deal with in this work.

Problem Definition

The problem of optimal camera placement to achieve de-sired vision tasks on a monitoring space is presented in this work. We focus on the static camera placement problem, where the objective is to determine the number of cameras and their optimal positioning for a region to be observed, given a set of task-specific constraints, and a set of possible camera types to use in the layout. This camera placement solution takes place off-line to support the task-specific requirements of on-line computer vision surveillance systems.

A. Modeling a camera's field of view (FoV) in 2D space

We assume that a network of N vision sensors (Si=1…N) to be deployed in a given space, which is approximated by a polygonal field A. In our work, examples focus on square discretized fields. For each deployed sensor Si, we know its location (XSi,YSi) in the 2D space as well as its orientation parameters necessary to model the sensor Field of View (FOV). We model the FOV Γi, as inspired from [15] using an isosceles triangle as shown in Fig.1.

For each sensor Si, the parameter φ is the horizontal angle to the bisection of the FoV angle, which defines the pose of the camera. α is the FoV vertex angle, which defines the aperture of the camera and wd defines the sensor working distance. Fig.2 describes the relationship between the fundamental parameters of a sensor imaging system. The parameters of the triangle, in Fig.1, are calculated, given the camera intrinsic parameters and the desired viewing resolution.

Defining the field of view by a triangle allows describing the area covered by each camera Si, positioned at (XSi,YSi) and orientation φ, with three linear constraints:

(1)

(2)

(3)

Thus, each point (x, y) of the discretized monitoring space can be viewed by a camera Si if the three constraints (1), (2) and (3) are satisfied.

Lady using a tablet
Lady using a tablet

This Essay is

a Student's Work

Lady Using Tablet

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Examples of our work

B. Modeling a camera's FoV in 3D space

The camera FoV can be represented by a pyramid, as shown in Fig.3. Horizontal and vertical viewable angles of the camera can be determined by the focal length of the lens and the size of the Coupled Charge Detector (CCD) element as follows:

(4)

where and define the horizontal and vertical viewable angles of the camera FoV represented by a pyramid. sh, sv are the horizontal and vertical dimensions of the CCD element, and f is the focal length of the lens. The camera working distance wd is the depth of the pyramid and can be calculated from the focal length of the lens f and image resolution requirement.

The camera position S(xs,ys,zs) and pose ψ(ψh, ψv) describe the camera's extrinsic parameters where ψh and ψv define its azimuth and elevation respectively.

In the world frame, the target object and camera position and pose are described in Cartesian coordinates. In the camera view, a spherical coordinate system is applied. The distance l between camera position and a given target position in the monitoring space is:

(5)

The azimuth and elevation of the target with respect

to camera position are given by:

(6)

Figure 1. Field-of-view Γi of sensor Si in 2D space.

In order for the point to be covered by the camera's FoV, the following constraints must be fulfilled [17]:

(7)

In the spherical coordinate systems, the range of the camera's FoV is directly determined by and , which makes it easy to dynamically compute FoV according to the changing of the focal length f.

C. Space Modeling

Theoretically, cameras can be proposed to be placed anywhere in the space since the sensor variables XSi , YSi and φ are continuous variables. Practically, an approximation of the monitoring space by a two-dimensional (three-dimensional) grid of points is used to solve the formulated optimization in discrete representation. The minimum distance ω between two grid points in the x and y directions is determined by the spatial sampling frequencies: . Thus, cameras are constrained to be placed only at these discrete grid points, and coverage is ensured relatively to these grid points.

The problem turns, then, into a grid coverage problem. When fx →∞ and fy→∞, the approximated discrete solution converges to the continuous-case solution.

D. Camera placement problem

Camera placement is an optimization problem by definition [18]. Let T be the given task and let C be the set of all constraints imposed by T as: spatial coverage

constraints, temporal constraints in the case of active cameras, or quality of service constraints like resolution constraints.

Let the vector represents the camera i intrinsic and extrinsic parameters. The challenge is to find where to place a set of cameras in a predefined area A with the minimum cost satisfying the set of constraints C:

(8)

Figure 2. Fundamental parameters of an Imaging System.

Figure 3. The spherical coordinates system and FoV of a camera in 3D space.

where S = {S1....SN}, N is the number of cameras to be placed in A and G(S) is the objective function.

In this work, we want to place the minimum number of cameras in the optimal locations (position and orientation) such that coverage is maximized. To solve this visual sensor placement, we derive the following model, which is based on the study presented in [16].

Let a binary variable be defined as:

(9)

The total number of cameras N in 2D space is then

given by:

(10)

where fφ, fx, fy are the orientation and the spatial sampling frequencies.

The total number of cameras in 3D space is:

(11)

For simplicity, we focus on the modeling of 2D case without

loosing generalization for 3D case. We define a binary variable to refer to the points viewed by the different cameras in the 2D space.

(12)

Our camera placement problem can then be formulated by

the following model:

(13)

Subject to

, (14)

, (15)

Equations (14) and (15) ensure that each grid point of the monitoring space is covered by at least one camera and that camera is necessarily located on a grid point. In addition, only one camera can be placed on each grid point. In the case of different types of cameras such as cameras with different sensor resolutions and optics (i.e. focal lengths), the camera placement problem is similar to the problem described above. In this case, the objective is to find the configuration and the number of cameras with different FoV parameters that minimize the total cost while ensuring coverage.

This optimization problem is formulated as follows:

Min (16)

Subject to

(17)

where NC is the total number of cameras and Knc is the individual cost of each camera.

To insure that at each grid point only one camera can be placed, we add the constraint below:

, (18)

PARTICLE SWARM OPTIMIZATION (PSO)

Evolutionary computation techniques such as, evolutionary programming and genetic algorithms [19] are motivated by the evolution of nature. A population of individuals, which encode the problem solutions, are manipulated according to the rule of the survival of the fittest through genetic operations. The best solution is evolved through generations.

These techniques have been successfully used in a number of different applications. Lately, authors in [2], [3] and [4] developed a technique called Particle Swarm Optimization (PSO) inspired from social behaviors. This technique has been introduced as an optimization tool dealing with real numbers initially and with integers lately.

A. Standard Particle Swarm Optimization (SPSO)

Particle Swarm Optimization is inspired from the manner in which a flock of birds moves with various individuals leading the flock during the travel at different periods of time. The PSO algorithm consists of a group of individuals named particles. Each 'particle' is a potential solution to the n-dimensional optimization problem. A particle i, has a memory to record the current solution Xij , the previous personal best solution Yij and a velocity Vij on the jth dimension, that represents the speed at which the particle is 'flying' through the current search space. The algorithm operates on each particle by determining its fitness and then sharing the information with the rest of particles within the particle's neighborhood. The neighborhood best particle is denoted by. This social information sharing causes a change in the direction vector, directing the particle towards more optimal solutions in the search space. This process continues until some stopping condition is met.

The position and velocity of each particle are updated following the two equations below:

(19)

where ω is the inertia weight, C1 and C2 are constant values, r1 and r2 are random numbers between 0 and 1.

B. Binary Particle Swarm Optimization (BPSO)

As our problem of camera placement is treated in discrete optimization space where variables can take a value of only 0 or 1, we focus our study on the case of Binary Particle Swarm Optimization (BPSO).

1) Standard Binary Particle Swarm Optimization (SBPSO):

This standard BPSO technique slightly modifies the original particle swarm algorithm. The position variables can take only 0 or 1 based on the particle velocity, which acts as a probability threshold. Such a threshold keeps the variable range [0, 1] by using the sigmoid function, which squashes its input into the requisite range:

(20)

The position variable is set to 1 if a random number r drawn from a uniform distribution between 0 and 1 is less than the value from the sigmoid function or set to 0 otherwise, as in the following equation:

(21)

2) Improved Binary Particle Swarm Optimization (IBPSO):

To enhance the S-BPSO search ability by avoiding the particle to converge to local optima, an improved BPSO algorithm for partner selection has been proposed in [20]. While the velocity updating formula, Eq. (17) remains unchanged, the position updating of each particle is defined as follows:

- If new velocity is average, then the location stays the same.

(22)

- If new velocity is below average, then new location is 0.

(23)

- If new velocity is above average, then new location is 1.

(24)

where δ is positive variable defined by the following linear variation rule:

(25)

tmax represents the maximal number of iterations, t is the current iteration and δinitial , δfinal represent the initial and final values of δ respectively. δ can take a value between 0 and 0.5, and as the iteration continues, its value decreases gradually to enhance the local fine-tuning search ability. Equation (22) makes each particle to keep its own inertia and to avoid that all the particles tend to move towards the same position and to trap in a local optima.

3) Novel Binary Particle Swarm Optimization (N-BPSO):

Authors in [21] have presented a Novel Binary Particle Swarm Optimization (N-BPSO). It differs from the two methods presented above in the interpretation of the velocity. Two velocity values are introduced representing the probability of changing from 0 to 1 and from 1 to 0. The choice of the velocity value depends on the previous position of the particle as shown in (26):

(26)

The velocity values are updated based on the following equations:

(27)

(28)

In this algorithm, if the jth bit in the global best particle or the jth bit in the best value registered for a particle 'i' is zero, , which is the probability of changing from 1 to 0, increases. The probability of changing from 0 to 1, , decreases at the same rate. The computation of the position is based on a selection of a random number such as if it is less than the sigmoid of velocity, the corresponding bit value of the position at time t +1 will be the complement of the value at time t. If not, it keeps its previous position:

(29)

where rij is a random variable in the range of [0, 1].

C. Binary Particle Swarm Optimization using an Artificial

Immune System (BPSO-AIS)

BPSO version presented in [22] is inspired from immunity concept of biological systems. This method differs from SBPSO in the calculation of velocity and particle movements. The position and velocity vectors are calculated with logical operations such as 'AND', 'OR', 'XOR',...etc., rather than applying a probability threshold to the binary variables. The different bits between the particle position and two desired positions (the globally best position and particle's best position) are identified by using a 'XOR' operation, as in equations (30) and (31). Each bit in the difference vector shows whether this bit is different from the desired one or not (i.e. the Hamming distance). Randomness has been added into the method by creating two random bit strings that will be processed with different vectors by an 'and' operation. The velocity vector, that shows which bits should be changed is produced as in (32), by an 'OR' operation between the two bit strings resulted from the 'AND' operation of the previous step. Then, a new position will be computed by applying a 'XOR' operation between the velocity vector and the particle's current position vector, as in (33).

This method has all the major characteristics of the standard BPSO. In addition, the total number of '1s' is converted to '0s' when the limit is exceeded. This process is called negative selection and is inspired from biological immunity systems. However, the primary interest in this method is in the calculation of the velocity and the position vectors using logical operators.

(30)

(31)

(32)

(33)

1) BPSO-AIS based on Negative Selection (BPSO-AIS-NS):

In order to control the maximal velocity of particles (Vmax) in the S-BPSO algorithm, we introduced the theory of negative selection of artificial immune systems. The negative selection is drawn from this question: 'How does the immune system behave when it is facing a self antigen?.' The discussion here is restricted to the thymic negative selection of T-cells as illustrated in Fig.(4). This process is responsible of eliminating all T-cells whose receptors recognize and bind with self antigens presented in the thymus [23]. The immune system with its stochastic cell production produces more cells to be able to get out of the thymus.

Figure 4. Simplified view of the thymic negative selection.

The naive T-cells that recognize self antigens are purged from the repertoire. In contrast, those that do not recognize any self antigen become immune competent cells and are released to the blood stream. In this problem the antigens are velocity vectors (Vn(t)) which are produced using the algorithm introduced above. For indicating self and non-self antigens, the following equations based on length of velocity vector are used:

(34) (35)

From (35), the self antigens cannot be used in the next steps. For a self antigen (>Vmax), a manipulation such as the stochastic production of cells (random process) is requiredin order to reduce the length of the velocity vector L(Vn(t)).

The pseudo code for this process is as follows:

1) calculate C (Number of 1s in V)

2) if C > Vmax

calculate I (int(random (1,C))

clear Ith 1 in V

Goto 1

End

2) BPSO-AIS based on Compatibility Degree (BPSO-AISCD):

Biology immune system has the properties of clonal variation, immunity self-regulation and immunological memory in terms of information processing. Immune algorithm (IA) is formed by simulating properties of biologic immune system as in [24]. In order to improve the colony's diversity and convergence of BPSO, authors in [25] introduced self-regulation of immune system and immunological memory mechanism to form an immune BPSO algorithm. Immune self-adjustment means that immune system can maintain the balance of immune mechanism and efficiently accelerates antibody with low antigen concentration and big compatibility degree. However, the antibody is restrained with high antigen concentration and small compatibility degree. In this paper, antigen is regarded as optimal particle while antibody is regarded as selected particle. Consequently, compatibility degree between antibody and antigen is assimilated with approach degree between optimal and selected particles. Compatibility degree reflects the satisfaction degree of our constrained optimization problem. Compatibility degree between antibodies is assimilated with similitude degree between particles of colony and it can reflect diversity of particle swarm and concentration of the same classical antibodies [25].

Compatibility degree Cd between antibody k and antibody l (similitude degree) is evaluated as follows:

(36)

where k = 1,2,…,M ; j = 1,2,…,M, M represents the swarm size and n is the dimension of each particle.

Figure 5. BPS0-AIS based on Compatibility Degree flow-chart.

The flow-chart in Fig.(5) presents the process of BPSO-AIS-

CD algorithm as follows:

1) Population initialization

Randomly produce M binary coded particles (antibodies) with length of n with theirs respective flight velocities. Then compute the fitness degree of all particles. By means of this method, we can obtain individual optimum particle Yij and global optimum particle and deposit into memory bank as immunological memory particle.

2) BPSO operation

Renew the velocity and position of each particle of the population and recompute fitness degree according to (19).

3) Immune selective operation

Renew the particles (antibody) as follows:

If the fitness degree of renewed particle k is bigger than the fitness degree of the optimum individual particle p, k becomes the optimum individual in place of p, and k joins the new swarm.

Otherwise, compute the compatibility degree between the antibody k and the antigen p.

One suppose δ and λ are thresholds, which are selected in the range [0, 1] beforehand and rand is a random number, which is uniformly distributed in the range [0, 1], then:

- If Cdkj ≤ δ, then add antibody k to the new swarm;

- If Cdkj > δ, and rand ≥ λ, then produce a new particle in place of particle k join to the new swarm and compute its fitness degree;

- If Cdkj > δ, and rand < λ, then take measures of 'Vaccination operation as in 4)'. Then, compare the fitness degree of all the antibodies, renew optimum individual particle Yij and global optimumand renew immune memory bank.

In this way, we can control the selective and inoculation probabilities, ensure the diversity of antibody, and avoid premature convergence. At the same time, we preserve the individual with high fitness degree.

4) Vaccination operation

The global best antibody is stored in the immune memory bank. Select the global best particle and tease out randomly both the number and the position of the feature component (immune gene) and modify accordingly the corresponding component in the antibody k (inoculation). Then insert it to the new swarm and compute its fitness degree.

5) Judge whether it satisfies the ending condition or not. If it does, stop action and output, otherwise switch to 2) for the next iteration.

D. Binary Particle Swarm Optimization Inspired Probability (BPSO-IP)

Although BPSO inherits the sharing of information mechanism as PSO, it has been shown that its ability to reach the global optimum is not satisfactory [26]. By analyzing the updating formula of BPSO, we can find that the position updating formulas will change the updating of the velocity as a binary bit and with changes between '0' and '1' only. This, spoils the optimization ability of BPSO. In addition, the exponential function in the position updating formula brings more computation complexity compared with PSO.

To make up for that, a novel binary particle swarm optimization inspired probability (BPSO-IP), which is based on the PSO information sharing mechanism and the idea of probability optimization algorithm is proposed. In BPSOIP, the value of each bit is determined by its corresponding probability of being '1', while this probability is updated according to the information sharing mechanism of PSO. The main steps of BPSO-IP can be described as follows (see Fig.6):

Figure 6. BPS0-IP flow-chart.

1) Initialize BPSO-IP, setting population size; generate random positions and corresponding velocities.

2) Evaluate individual best particle Yij and global best particle .

3) Generate the corresponding Xij according to its probability

Pij step by step and getting all solutions.

Firstly, we calculate the probability Pij as follows:

(37)

Where N(), N(Yij) are the global best fitness and the

fitness respectively. Then, a random number is generated and compared with the probability Pij . The value of Vij and Xij is determined according to (38), (39):

(38) (39)

With the iteration going on, Pij is changed according to (37), the randomness of Vij value will be less, and finally the algorithm converges.

4) Calculate the fitness of each individual;

5) Terminate if termination criteria are reached else going on the next step;

6) Update the individual best solution and global best solution according to the fitness value as done in PSO;

7) Go to step 3.

To enhance the local search ability of BPSO-IP and to avoid premature convergence, a mutation operator Pm is introduced in the algorithm if no change appears during some iterations. Thus, the new position is calculated as follows:

(40)

V. SIMULATION

Few studies, reported in the literature, extend PSO to handle constraints in constrained optimization problems [27], [28], [29]. In this work, an effective framework to solve our constrained problem described in section III is introduced for all particle swarm based techniques. Feasibility preserving strategy is employed to deal with constraints by storing for the best generation only particles that satisfy all the constraints.

Two modifications were introduced to handle the constraints in the PSO algorithm as this later is usually used to solve unconstrained problems:

1) During the initialization process, all particles are started with feasible solutions,

2) When updating the memories (and ), all particles keep only feasible solutions in their memories.

The idea of these modifications is to transform a constrained optimization problem into an unconstrained one by adding (or subtracting) or multiplying a certain value to/from the objective function based on the amount of constraint violation present in a certain solution. This will introduce a penalty to the objective function.

The basic approach with a penalty function is to define the fitness value of a set a variables S as fitn(S) by extending the domain of the objective function G(S), (8), using:

fitn(S) = f(S) ± Pen1(S) or fitn(S) = f(S) - Pen2(S) (41)

where Pen1(S) and Pen2(S) represent a penalty for an infeasible solution.

It is assumed that if S is feasible then Pen1 = 0 and Pen2 = 1 (i.e. we do not penalize).

To evaluate and compare the effectiveness and reliability of each algorithm, we adopted two space monitoring benchmarks. According to the complexity of the problems, the PSO population size for the first benchmark is taken equal to 30 and the maximum iteration used is 500. However, we have taken a population size of 60 with a maximum iteration of 3000 for the second benchmark. Setting parameters required for all algorithms presented in this work are defined in Table I.

Table I. PARAMETERS SETTING OF THE DIFFERENT ALGORITHMS IMPLEMENTED.

Experiments were performed using the seven PSO based approaches proposed above (BPSO, I-BPSO, N-BPSO, BPSO-AIS-NS, BPSO-AIS-CD, BPSO-IP) in addition to Genetic Algorithms (GA).

Before looking at some comparison results, we present few results obtained by BPSO-IP algorithm in 2D visual deployment case. For instance, we evaluated our BPSOIP with one type of cameras in medium and large scale dimensions (Fig.7, Fig.8 and Fig.9). Then, we evaluated BPSO-IP algorithm for the placement problem with two types of cameras (Fig.10, Fig.11 and Fig.12). A cost of 180$ was assumed for the camera with the larger FoV while only 100$ was assumed for the camera with the smaller FoV.

Figure 7. Optimal placement of cameras. (1 type of camera, ,,)

In all figures, bold blue lines represent the borders of the area to be covered while the light blue lines represent the area grid. The grid nodes to be covered are the intersections points of these later lines. The camera's FoV are represented by red triangles with dotted lines. The black small squares represent the optimal position of the cameras to be placed using the proposed BPSO-IP algorithm.

fx1 and fy1 represent the sampling frequencies used to discretize the area to be covered while fx2 and fy2 represent the sampling frequencies along the x and the y axis respectively and defining the discrete area nodes of the allowed camera positions. If fx1 = fx2 and fy1 = fy2 then the allowed camera position coincide with the space grid nodes. This is assumed in Fig.7 and Fig.8 where the effect of the sampling frequency on the quality of the coverage is illustrated. Fig.8 shows that increasing the sampling frequency (smaller mesh grid) improves the quality of the coverage.

Figure 8. Optimal placement of cameras. (1 type of camera, , ,)

In Fig.8 the whole surface is covered while using the same number of cameras as in Fig.7 without additional cost (900$) since 5 cameras are used in both cases. Only the positions and the orientations of the cameras have been modified in order to take into account the larger number of points to be covered compared to Fig.7.

Fig. 9 illustrates an example where all the points of the grid are covered with an optimal placement of cameras constrained to be on the allowed black grid with sampling frequency ().

Figure 9. Optimal placement of cameras. (1 type of camera, , , ,)

Additional results, which illustrate the case where we have a complex shape area than a rectangular one to be covered, are shown in Fig.11 and Fig.12. In these figures, we can observe the effect of using two camera types with different FoVs. Two cameras with large FoV and one with small FoV are required to cover all the grid points in the case of Fig.11 while another one with small FoV is required in the case of Fig.12.

Figure 10. Optimal placement of cameras. (2 types of camera, , , , )

Figure 11. Optimal placement of cameras for complex shape N-1. (2 type of cameras, , , ,)

Figure 12. Optimal placement of cameras for complex shape N-2. (2 type of cameras,,,,)

In all the illustrated cases from Fig.7 to Fig.12, all the grid nodes are covered and each node is covered by at least one camera. However, some small regions in some cases are not covered. This situation can be avoided by increasing the grid sampling frequencies in x and y directions.

Figure 13. 3D view of an optimal placement of cameras in the 3D space. (1 type of camera,, ,,,)

Results of the proposed BPSO-IP algorithm for a 3D space case are illustrated in Fig.13 and Fig.14. In this case, camera FoV is represented by a pyramid and similar results as those presented for the 2D case confirm the good behavior of the proposed algorithm in 3D.

Table II shows the different results obtained for the two space monitoring benchmarks in 2D case using all presented algorithms. Each algorithm has been run for 100 times.

For each algorithm run, the optimal fitness and the number of iterations to reach solution are recorded when successful. The success rate, the average number of iteration, the best fitness and the average fitness are then derived for each algorithm.

For the first benchmark, the best success rate that has been recorded is the one obtained by using BPSO-IP (100%). In addition, the best known solution has been reached (5 cameras) with an average number of 191.3 iterations for all BPSO-IP runs.

Figure 13. Top view of an optimal placement of cameras in the 3D space. (1 type of camera, , , ,,)

The first benchmark uses 640 variables, and for this case, the best solution is known to be 5 cameras. While the second benchmark uses 2250 variables and the best solution is known to be 6 cameras. Remark that the second benchmark presents much more complex optimization problem.

Figure 15. Computation time comparison

For the second benchmark, the best success rate has also been recorded using the proposed BPSO-IP algorithm. As we are dealing with a very large scale problem in this benchmark, for 45% of runs only the best known solution has been reached (6 cameras) with an average number of iterations of 2187. Note that in this case, neither the BPSO nor the BPSO-AIS-CD nor the GA algorithms reached the best known solution.

In both benchmarks, we observe that BPSO-IP outperforms all the other algorithms. Nevertheless, its performances decrease with the growing of dimension of the population although it keeps its superiority when compared with the remaining algorithms presented in this paper.

Fig.15 presents a comparison in term of computation time between the seven proposed algorithms for different number

of optimization variables. For a large number of variables, BPSO-IP algorithm largely outperforms the rest of algorithms. Indeed, the computation time gap between BPSO-IP and the rest of the algorithms increases with the number of variables involved in the camera deployment problem.

VI. CONCLUSION

In this paper, we addressed the issue of automatic visual sensor placement using evolutionary techniques. The different simulations proved the effectiveness of the proposed algorithm based on Binary Particle Swarm

Table II. BENCHMARK TEST COMPARISON

Optimization inspired probability to solve coverage problem especially for large scale dimensions where techniques such as Binary Integer Programming can explode in term of memory and computing time. Since all the proposed methods are stochastic, the major problem was to guarantee the global optimum. For this reason, this study permitted to clarify that obtaining the global optimum for particle swarm based optimization techniques is well linked with two factors:

1) The initializations of the different particles since those are generated randomly.

2) The computation of the particle positions is based on heuristics and differs from the continuous case since it closely depends on a random variable.

The work proposed in this paper opens for us new challenges in the future to improve the robustness of the BPSOIP technique. We will investigate the possibility to combine BPSO-IP algorithm with other formal evolutionary techniques to accelerate the convergence process in meeting global optimum requirements of the camera placement optimization problem.