# Two-Phase Algorithm for Optimal Camera Placement

Authors: Jun-Woo Ahn; Tai-Woo Chang; Sung-Hee Lee; Yong Won Seo
Journal: Scientific Programming
 (2016)

---

## Abstract

As markers for visual sensor networks have become larger, interest in the optimal camera placement problem has continued to increase. The most featured solution for the optimal camera placement problem is based on binary integer programming (BIP). Due to the NP-hard characteristic of the optimal camera placement problem, however, it is difficult to find a solution for a complex, real-world problem using BIP. Many approximation algorithms have been developed to solve this problem. In this paper, a two-phase algorithm is proposed as an approximation algorithm based on BIP that can solve the optimal camera placement problem for a placement space larger than in current studies. This study solves the problem in three-dimensional space for a real-world structure.


---

## Body

## 1. Introduction

The global surveillance camera market is rapidly growing. According to the 2013 IMS Research data shown in Figure1, the surveillance camera market is expected to grow by 1.5 times or more in the next five years. This is because surveillance cameras are used for more than simply preventing and solving crime or managing traffic. They are now needed for production assembly lines or observing natural disasters [1, 2]. Moreover, with the development in big data image-processing techniques, it is also possible not only to watch the images but also to extract the necessary data from them [3].Figure 1
Surveillance Camera Market Size Prediction [20].Along with the growth of the surveillance camera market, interest in efficient camera placement has also been increasing. If the placement of cameras is inefficient, even with many installed cameras the effect can be unsatisfactory. For efficient placement of surveillance cameras, several studies [4–15] have investigated the optimal camera placement problem. The optimal camera placement problem, sometimes called the camera network deployment problem, is defined as how to adequately place cameras to maximize the coverage under certain conditions [6, 10]. This optimal camera placement problem consists of finding the minimum number of cameras that satisfies a specific coverage or finding the maximum coverage with a given number of cameras [4].Current studies [6, 7, 10, 11] hypothesized a continuous space that is simplified as a two-dimensional (2D) grid of points. Here, the grid points are discrete points on x- and y-axes by the minimum distance Δ, which takes into account the spatial sampling frequency (f
x
=
f
y
:
Δ
=
1
/
f
x
=
1
/
f
y) after simplifying real space into 2D [6]. When modeling a fixed-area terrain using the above method, the solution quality of the optimal camera placement problem with a higher resolution tends to be better than that with a lower resolution, because the ratio of the real-world terrain that is reflected in the modeling area with a high resolution (large f
a; small Δ) using a larger number of grid points is higher than that with a low resolution (small f
a; large Δ) using fewer grid points. Thus Hörster and Lienhart [6] claimed that considering a large number of grid points is necessary.Because the optimal camera placement problem is NP-hard [16], existing studies have focused on finding efficient and effective approximation algorithms rather than finding an optimal solution.The approximation algorithm proposed in previous studies solves the problem directly at the high resolution of the desired level. On the other hand, our study proposes a method of finding a solution under a low resolution using BIP, then solving the problem correctly at its desired high resolution based on the found solution. The proposed method decreases the complexity of the calculation, which can lead to faster problem-solving at a high resolution than existing methods.The reliability of setting the start point, which can cause a localized optimization in the approximate algorithm, is also improved. As a result, under the same conditions, the confidence of the proposed solution increases when compared to solving the problem at a high resolution to begin with.Additionally, rather than using the virtual modeling area generally used in existing studies, this study uses a real-world modeling area from geographic information system (GIS) data of actual terrain. The data came from the satellite pictures. Three-dimensional (3D) camera placement was selected to provide more practicality, instead of 2D camera placement which is unrealistic to apply.This paper is organized as follows. Section2 analyzes the relevant studies. Section 3 explains the spatial configuration required for the camera placement and the calculation method for the surveillance camera view and also describes the algorithm that solves the actual problem. Section 4 compares the quality of the solutions obtained from binary integer programming and from the proposed method. Section 5 presents the conclusion.


## 2. Literature Review

The art gallery problem (AGP), studied in the field of computational geometry, is the problem of placing at least one security guard to check every area of a museum or gallery. Because AGP finds the optimal placement point within the restricted viewpoint of the security guard and the optimal camera placement problem finds the optimal placement point within the restricted viewpoint of the camera, solving the optimal camera placement problem is very similar to solving AGP [17, 18].This optimal camera placement problem has been studied to solve both MIN problem, which finds the minimum number of cameras and placement conditions to satisfy the target coverage under the given conditions, and the FIX problem, which maximizes the coverage with a fixed number of cameras under the given conditions [4].In the meantime, looking from the methodological viewpoint of problem-solving, previous studies on solving the optimal camera placement problem generally have been based on binary integer programming (BIP) [5–9]. BIP offers the global optimal solution; however, the studies based on BIP only answer problems with limited, simple conditions due to the NP-hard property of the problem [4].Therefore, studies have approached the problem from various directions to solve the optimal camera placement problem within a modeling area that can reflect reality with complex conditions, and many approximation algorithms have been suggested as a result [4–15]. Previous literature in the modeling area and the camera installation area has its roots in 2D-based studies [12]. The greedy algorithm [8, 14], genetic algorithm (GA) [10, 15], particle swarm optimization (PSO) [11, 12], and so on have been used in existing studies as approximation algorithms to solve the problem. However, all the studies mentioned above have high computational complexity, for they found the solution directly at a high resolution. Table 1 lists the approximation algorithms suggested in previous studies.Table 1
Publications on the optimal camera placement problem.
Source
Year
Methods
x grid
y grid
Number of grid points
[10] Surveillance of a 2D plane area with 3D deployed cameras
2014
PSO
4
4
16
[11] Particle swarm optimization inspired probability algorithm for optimal camera network placement
2012
PSO
11
11
121
[6] Approximating optimal visual sensor placement
2006
IP
12
12
144
[13] Grid coverage for surveillance and target location in distributed sensor networks
2002
IP
13
13
169
[7] Optimal camera placement for total coverage
2009
IP
12
6
72
Model simulation 1 in this paper
Greedy
200
200
40,000
Model simulation 2 (Appendix) in this paper
Greedy
500
500
250,000Moreover, the 2D model is too simple to compute a real-world case of the optimal camera placement problem [12]; methods to solve the problem using 3D were studied in [11, 12]. However, 3D problem-solving exacerbates the issue of high computational complexity.Previous studies have consistently reported the issue of high computational complexity as they continue to use problem-solving methods at high resolution. To remove this issue, phase 1 of the two-phase algorithm proposed in this study uses BIP to find the global optimal solution of the MIN problem within the low-resolution area (small number of grid points), and phase 2 uses an approximation algorithm, hill climbing method, to solve the FIX problem at a high resolution (large number of grid points).With this process, the solution for a wider high-resolution area can be found based on the verified global optimal solution found in the low-resolution. Existing studies mainly used methods to avoid local optima, such as the genetic algorithm, particle swarm optimization, and simulated annealing, though they have high computational complexity [4]. Therefore, this study proposes using a hill climbing method, known to have low computational complexity. In general, greedy algorithms like a hill climbing method can find local optima if they are assigned the wrong starting point; however, this study proposes using the starting point found by BIP. The low computational complexity can reflect the modeling area of a large number of grid points with the same condition. Thus, this study proposes an approximation algorithm that is more likely to be used for real-world cases.


## 3. Model and Solution

This paper proposes a two-phase algorithm and assumes a 3D camera installation in a 2D modeling area. Phase 1 solves the problem using BIP, which offers an optimal solution by configuring the modeling area with a low-resolution grid for simple execution. Phase 2 finds a real-world applicable answer by setting the starting point from the low-resolution solution of phase 1 and then using the hill climbing method [19] for the modeling area configured with high-resolution grids.


### 3.1. Modeling Space

This paper assumes the surveillance of a plane area without obstacles. The surveillance area is divided into grid points, as shown in [13], and a grid point is captured by the camera if it is observed from the camera. As mentioned above, grid points refer to discrete points onx- andy-axes, separated by minimum distance Δ for the spatial sampling frequency [6]. Later, the plane area is divided into camera-installable and not camera-installable areas, and the surveillance area is assigned.


### 3.2. Modeling Surveillance Area

As in previous studies [4–12], field of view (FOV) modeling is proposed prior to explaining the placement method. Finding a solution for the optimal camera placement problem is equivalent to finding the conditions that create the FOV of each properly placed camera; the problem can be solved only if the method of computing the FOV is defined beforehand.Like the study in [6], this study assumes a camera that is fixed in a certain direction so that it only surveils the same spot; therefore, a single camera has a fixed FOV depending on its installation condition. The FOV of the surveillance camera has a trapezoidal shape on the surveilled plane area, corresponding to the installation location (x
0, y
0), horizontal angle (φ), vertical angle (ψ), installation height (ε), horizontal and vertical angles of camera view (θ
1, θ
2), and maximum recognition distance (T). The horizontal and vertical angles of camera view mean the horizontal and vertical viewing angles of the scene captured by the camera.Figure2(a) shows the location of a camera which is installed at the ground coordinate P
0
(
x
0
,
y
0
) with the height ε and the recognition distance τ. Note that the actual recognition distance (τ) is less than or equal to the maximum recognition distance (τ
≤
T). Figure 2(b) shows the horizontal view angle (θ
1) and the vertical view angle (θ
2), as well as the horizontal angle (φ) and the vertical angle (ψ). Here, the horizontal angle (φ) of the camera means the direction in which the camera watches. The vertical angle (ψ) is the watching angle of the camera, measured from a line perpendicular to the ground at the installation point.Figure 2
FOV computation parameters.
(a)
(b)Based on the given camera conditions, the algorithm to compute the coordinates of the trapezoid vertices, which are the FOV of the camera, is described as follows.Step 0. τ
=
ε
/
cos
⁡
(
θ
2
+
ψ
). If θ
2
+
ψ
<
90 or τ
>
T, then stop the calculation.Step 1. If P
0
=
(
0
,
0
) and φ
=
0, FOV is made of four vertices p
1
′
,
p
2
′
,
p
3
′
,
p
4
′ (each point p
i
′ is made of {
x
i
′
,
y
i
′
}):(1)
h
×
tan
⁡
ψ
h
cos
⁡
ψ
×
+
tan
⁡
θ
1
2
h
×
tan
⁡
ψ
h
cos
⁡
ψ
×
-
tan
⁡
θ
1
2
h
×
t
a
n
⁡
ψ
+
θ
2
h
cos
⁡
ψ
+
θ
2
×
+
tan
⁡
θ
1
2
h
×
t
a
n
⁡
ψ
+
θ
2
h
cos
⁡
ψ
+
θ
2
×
-
tan
⁡
θ
1
2
=
x
1
′
y
1
′
x
2
′
y
2
′
x
3
′
y
3
′
x
4
′
y
4
′
.Step 2. Calculate vertex p
i
′
′ by rotating p
i
′ by φ
(2)
cos
⁡
φ
-
sin
⁡
φ
sin
⁡
φ
cos
⁡
φ
x
i
′
y
i
′
=
x
i
′
′
y
i
′
′
.Step 3. Actual camera installation information is added to each p
i
′
′
(3)
x
i
′
′
y
i
′
′
+
x
0
y
0
=
x
i
y
i
.Step 0 considers the maximum recognition distance (T), vertical angle (ψ), and vertical view angle (θ
2) to check whether the FOV can be computed. If τ exceeds the maximum recognition distance (T) set beforehand, FOV with such a condition does not exist and therefore is not computed. The FOV also does not exist if the sum of the vertical angle (ψ) and the vertical view angle (θ
2) exceeds 90 degrees, for the camera cannot see the floor.Step 1 explains the calculation of the coordinates for the FOV trapezoid vertices, assuming that the surveillance camera is installed in a direction parallel tox-direction from the origin. Equation (1) takes the vertical angle (ψ) of the camera installation into account, as well as the vertical view angle (θ
2) and the horizontal view angle (θ
1).Step 2 shows how to obtain the coordinates for the vertices of the FOV trapezoid by taking the horizontal angle (φ) of the installed camera into account, based on the value obtained from Step 1.Step 3 includes the equation for calculating the coordinates for the vertices of the actual FOV trapezoid after adding the ground coordinates (x
0, y
0) of the installation point to the value from Step 2.In conclusion, combining (1), (2), and (3) in Table 2 will consider the actual installation location for the camera and compute the coordinates of each vertex of the surveillance area (FOV trapezoid) of a single camera, using the matrix calculation of (4)
cos
⁡
φ
-
sin
⁡
φ
0
0
0
0
0
0
sin
⁡
φ
cos
⁡
φ
0
0
0
0
0
0
0
0
cos
⁡
φ
-
sin
⁡
φ
0
0
0
0
0
0
sin
⁡
φ
cos
⁡
φ
0
0
0
0
0
0
0
0
cos
⁡
φ
-
sin
⁡
φ
0
0
0
0
0
0
sin
⁡
φ
cos
⁡
φ
0
0
0
0
0
0
0
0
cos
⁡
φ
-
sin
⁡
φ
0
0
0
0
0
0
sin
⁡
φ
cos
⁡
φ
h
×
tan
⁡
ψ
h
cos
⁡
ψ
×
+
tan
⁡
θ
1
2
h
×
tan
⁡
ψ
h
cos
⁡
ψ
×
-
tan
⁡
θ
1
2
h
×
t
a
n
⁡
ψ
+
θ
2
h
c
o
s
⁡
ψ
+
θ
2
×
+
tan
⁡
θ
1
2
h
×
tan
⁡
ψ
+
θ
2
⁡
h
c
o
s
⁡
ψ
+
θ
2
×
-
tan
⁡
θ
1
2
+
x
0
y
0
x
0
y
0
x
0
y
0
x
0
y
0
=
x
1
y
1
x
2
y
2
x
3
y
3
x
4
y
4
.Table 2
Camera specifications for the comparison test.
Consideration
Number of options
Details
Horizontal orientations (°)
8
0,45,90
,
…
,
270,315
Vertical orientations (°)
15
1,3
,
…
,
27,29
Height (m)
1
7
Camera type
Horizontal angle of view (°)
1
80
Vertical angle of view (°)
1
80
Available sight range (m)
1
60


### 3.3. Two-Phase Algorithm

Our two-phase algorithm (a) generates the grid model of the candidate locations of camera installation and the target area for surveillance; (b) solves the small scale of phase 1 at a low-resolution; (c) sets the starting value of phase 2 based on the solution from the previous step; and (d) solves the large scale problem of phase 2 at a high-resolution.


#### 3.3.1. Phase 1

In phase 1, the minimum number of cameras that satisfies the specific condition given with the grid points of the simulation area is obtained; it is then used to solve the MIN problem to find the location of each camera and the installation condition. We approached the problem using a further-developed method based on BIP formulas [6] for the existing 2D placement problem to solve the 3D placement problem. The detailed procedure is as follows.(1) First, decision variables are assigned, just as when solving a general BIP.(5)
x
i
j
d
e
t
=
1
,
If there exists a camera at position
i
with horizontal orientation
j
vertical orientation
d
,
height
e
,
and angle of view
A
O
V
t
,
0
,
Otherwise,
y
k
=
1
,
I
f the target at position
k
is covered by a camera,
0
,
Otherwise.Thus,x
i
j
d
e
t is 1 if there exists a camera at position i with horizontal angle j, vertical angle d, height e, and AOV t and 0 if not and y
k equals 1 if the surveillance area k is watched with x
i
j
d
e
t and 0 if not.(2) Other parameters required for the formula are defined as follows:(6)
v
i
j
d
e
t
k
=
1
,
if the target at position
k
is visible from camera position
i
with horizontal orientation
j
,
vertical orientation
d
,
height
e
,
and AOV
t
,
0
,
Otherwise.
N
C: number of camera positions.
N
hD: number of horizontal orientations.
N
vD: number of vertical orientations.
N
E: number of heights.
N
A: number of camera types.
N
T: number of target positions.
CVR: given minimal coverage rate.(3) The objective function minimizes the number of cameras as follows:(7)
min
⁡
​
∑
i
=
1
N
C
∑
j
=
1
N
h
D
∑
d
=
1
N
v
D
∑
e
=
1
N
E
∑
t
=
1
N
A
x
i
j
d
e
t
.(4) The following constraints are also necessary:(8)
∑
i
=
1
N
C
∑
j
=
1
N
h
D
∑
d
=
1
N
v
D
∑
e
=
1
N
E
∑
t
=
1
N
A
v
i
j
d
e
t
k
·
x
i
j
d
e
t
≥
y
k
for
∀
k
1
,
…
,
N
T
,
(9)
∑
i
=
1
N
C
∑
j
=
1
N
h
D
∑
d
=
1
N
v
D
∑
e
=
1
N
E
∑
t
=
1
N
A
v
i
j
d
e
t
k
·
x
i
j
d
e
t
≤
N
C
·
y
k
for
∀
k
1
,
…
,
N
T
,
(10)
∑
k
=
1
N
A
y
k
≥
N
T
·
C
V
R
.Equations (8) and (9) are the constraints to obtain y
k and (10) is a constraint such that the sum of y
k must be greater than or equal to the product of the minimum coverage rate and the target surveillance area.


#### 3.3.2. Phase 2

Phase 2 solves the FIX problem, which finds the combination for maximum coverage with the constraint of the number of cameras determined from phase 1, with the result obtained from phase 1 as the initial value. This study uses the hill climbing method [19]. Since the objective function is nongradient, a direct-search method was applied; among the different direct-search methods, the alternating variable search method was used, as the problem has a multidimensional variable. This study proposes a hill climbing method, as [19] proposed such a method.Since phase 2 aims to maximize the coverage rate with the minimum number of cameras obtained in phase 1, the number of cameras does not change; only the conditions for each camera change. Eachx
i
j
d
e
t has the specification data for the x-coordinate, y-coordinate, horizontal angle (φ), vertical angle (ψ), installation height (ε), horizontal view angle (θ
1), and vertical view angle (θ
2) according to the camera type, as well as the maximum recognition distance. Each piece of information is both variable and dimensional. A flowchart of this phase is shown in Figure 3 and a hill climbing method of phase 2 is described as follows.Figure 3
Flowchart of Phase 2.The notations and their meaning are as follows:X: set of x
i
j
d
e
t
X
t: set of optimal solutions found in the tth operation
t: the number of operations
s
t: the number of iterations that have an identical objective value
U
X
t: coverage rate of camera set X at tth trial
n: index of a camera
m: index of a camera setting variable (one of i
,
j
,
d
,
e
,
t). (i has both x- and y-coordinate properties, therefore treated as two different variables).Step 0 (initialization). Establish a starting point X
0
∗ and set t
=
0, s
t
=
0.Step 1 (variant search). Set t
=
t
+
1.InX, the nth variable x
i
j
d
e
t is selected. For each index (i
,
j
,
d
,
e
,
t) of x
i
j
d
e
t, the variants are generated by numerically changingmth index of x
i
j
d
e
t to the ± direction. The objective function for each variant is evaluated, and the best one among the tried variants is taken upon comparing the values of the objective function.Step 1.0 (initialization). Establish a starting point X
t and set n
=
0, m
=
0.Step 1.1 (selection of a camera and calculation of the coverage rate)Forn
=
1: n
(
X
t
);
LetX
t
b
e
s
t
=
X
t;
Letx
n
=
nth variable in X
t
Form
=
1 : 6
LetX
t
n
m
+ to be a variant solution generated by numerically increase the value of themth index of x
n, U
X
t
n
m
+ to be the coverage rate of X
t
n
m
+;
LetX
t
n
m
- to be a variant solution generated by numerically decrease the value of themth index of x
n, and U
X
t
n
m
- to be the coverage rate of X
t
n
m
-;
UpdateX
t
b
e
s
t to be argmax
X
∈
X
t
b
e
s
t
,
X
t
n
m
+
,
X
t
n
m
-
U
X, where in case of a tie one is randomly selected
End of Form
End of Forn.Step 1.2 (solution improvement). Set X
t
=
X
t
b
e
s
t.Step 2 (check for improvement)IfU
X
t
>
U
X
t
-
1, then set X
t
+
1
=
X
t, s
t
=
0 and go to Step 1.
Otherwise sets
t
=
s
t
+
1.Step 3 (termination criterion)Ifs
t
>
1, then X
∗
=
X
t; terminate the search.
Otherwise go to Step 4.Step 4 (check for equivalent)IfU
X
t
<
U
X
t
-
1, then set X
t
+
1
=
X
t
-
1, s
t
=
0; and go to Step 1.
Otherwise setX
t
+
1
=
X
t and go to Step 1.Step 0 sets the initial starting point. Here,t and s
t are set to 0.Step 1 finds the best variant to improve the objective function, among the variants generated by increasing or decreasing the indices of eachx
i
j
d
e
t in the solution set X
t. Here, t is increased by 1. Step 1.0 initializes the current optimal solution X
t to be the starting point of this iteration. Step 1.1 finds the best solution which gives the highest coverage rate among the variants of X
t, generated by changing each of indices if x
i
j
d
e
t is in X
t.Step 2 checks if the coverage rate ofX
t found in Step 1 actually increased compared to the coverage rate of X
t
-
1. If it is increased, X
t
+
1 stays as X
t and s
t becomes zero. If not, s
t is increased by 1.Step 3 checks whether the terminating conditions have been met. Here, ifs
t is greater than 1, the optimal solution of phase 2 becomes X
∗
=
X
t and the solution search is completed.Step 4 checks if the coverage rate ofX
t decreased from the coverage rate of X
t
-
1. If decreased, X
t
+
1 is reverted to X
t
-
1 and moves to Step 1; if not, meaning that the values are the same, X
t
+
1 stays at X
t and Step 1 is repeated.The existing alternating variable search method [19] assigns the variable of the changing dimension; when it changes, the moving direction and the magnitude of change for the dimension variable where the objective function value improved the most are found. However, the method adapted for this study preassigns the magnitude of change for the dimension variable, and then finds which dimension variable in which direction improves the value of the objective function most. This method was utilized because the existing method vibrates near the optimal point, causing prolonged computation. Thus, it was more desirable to stop the computation at a proper point and use the solution than to continue the computation until it finished [19]. The method developed in this study eliminates the vibrating solution problem.


## 3.1. Modeling Space

This paper assumes the surveillance of a plane area without obstacles. The surveillance area is divided into grid points, as shown in [13], and a grid point is captured by the camera if it is observed from the camera. As mentioned above, grid points refer to discrete points onx- andy-axes, separated by minimum distance Δ for the spatial sampling frequency [6]. Later, the plane area is divided into camera-installable and not camera-installable areas, and the surveillance area is assigned.


## 3.2. Modeling Surveillance Area

As in previous studies [4–12], field of view (FOV) modeling is proposed prior to explaining the placement method. Finding a solution for the optimal camera placement problem is equivalent to finding the conditions that create the FOV of each properly placed camera; the problem can be solved only if the method of computing the FOV is defined beforehand.Like the study in [6], this study assumes a camera that is fixed in a certain direction so that it only surveils the same spot; therefore, a single camera has a fixed FOV depending on its installation condition. The FOV of the surveillance camera has a trapezoidal shape on the surveilled plane area, corresponding to the installation location (x
0, y
0), horizontal angle (φ), vertical angle (ψ), installation height (ε), horizontal and vertical angles of camera view (θ
1, θ
2), and maximum recognition distance (T). The horizontal and vertical angles of camera view mean the horizontal and vertical viewing angles of the scene captured by the camera.Figure2(a) shows the location of a camera which is installed at the ground coordinate P
0
(
x
0
,
y
0
) with the height ε and the recognition distance τ. Note that the actual recognition distance (τ) is less than or equal to the maximum recognition distance (τ
≤
T). Figure 2(b) shows the horizontal view angle (θ
1) and the vertical view angle (θ
2), as well as the horizontal angle (φ) and the vertical angle (ψ). Here, the horizontal angle (φ) of the camera means the direction in which the camera watches. The vertical angle (ψ) is the watching angle of the camera, measured from a line perpendicular to the ground at the installation point.Figure 2
FOV computation parameters.
(a)
(b)Based on the given camera conditions, the algorithm to compute the coordinates of the trapezoid vertices, which are the FOV of the camera, is described as follows.Step 0. τ
=
ε
/
cos
⁡
(
θ
2
+
ψ
). If θ
2
+
ψ
<
90 or τ
>
T, then stop the calculation.Step 1. If P
0
=
(
0
,
0
) and φ
=
0, FOV is made of four vertices p
1
′
,
p
2
′
,
p
3
′
,
p
4
′ (each point p
i
′ is made of {
x
i
′
,
y
i
′
}):(1)
h
×
tan
⁡
ψ
h
cos
⁡
ψ
×
+
tan
⁡
θ
1
2
h
×
tan
⁡
ψ
h
cos
⁡
ψ
×
-
tan
⁡
θ
1
2
h
×
t
a
n
⁡
ψ
+
θ
2
h
cos
⁡
ψ
+
θ
2
×
+
tan
⁡
θ
1
2
h
×
t
a
n
⁡
ψ
+
θ
2
h
cos
⁡
ψ
+
θ
2
×
-
tan
⁡
θ
1
2
=
x
1
′
y
1
′
x
2
′
y
2
′
x
3
′
y
3
′
x
4
′
y
4
′
.Step 2. Calculate vertex p
i
′
′ by rotating p
i
′ by φ
(2)
cos
⁡
φ
-
sin
⁡
φ
sin
⁡
φ
cos
⁡
φ
x
i
′
y
i
′
=
x
i
′
′
y
i
′
′
.Step 3. Actual camera installation information is added to each p
i
′
′
(3)
x
i
′
′
y
i
′
′
+
x
0
y
0
=
x
i
y
i
.Step 0 considers the maximum recognition distance (T), vertical angle (ψ), and vertical view angle (θ
2) to check whether the FOV can be computed. If τ exceeds the maximum recognition distance (T) set beforehand, FOV with such a condition does not exist and therefore is not computed. The FOV also does not exist if the sum of the vertical angle (ψ) and the vertical view angle (θ
2) exceeds 90 degrees, for the camera cannot see the floor.Step 1 explains the calculation of the coordinates for the FOV trapezoid vertices, assuming that the surveillance camera is installed in a direction parallel tox-direction from the origin. Equation (1) takes the vertical angle (ψ) of the camera installation into account, as well as the vertical view angle (θ
2) and the horizontal view angle (θ
1).Step 2 shows how to obtain the coordinates for the vertices of the FOV trapezoid by taking the horizontal angle (φ) of the installed camera into account, based on the value obtained from Step 1.Step 3 includes the equation for calculating the coordinates for the vertices of the actual FOV trapezoid after adding the ground coordinates (x
0, y
0) of the installation point to the value from Step 2.In conclusion, combining (1), (2), and (3) in Table 2 will consider the actual installation location for the camera and compute the coordinates of each vertex of the surveillance area (FOV trapezoid) of a single camera, using the matrix calculation of (4)
cos
⁡
φ
-
sin
⁡
φ
0
0
0
0
0
0
sin
⁡
φ
cos
⁡
φ
0
0
0
0
0
0
0
0
cos
⁡
φ
-
sin
⁡
φ
0
0
0
0
0
0
sin
⁡
φ
cos
⁡
φ
0
0
0
0
0
0
0
0
cos
⁡
φ
-
sin
⁡
φ
0
0
0
0
0
0
sin
⁡
φ
cos
⁡
φ
0
0
0
0
0
0
0
0
cos
⁡
φ
-
sin
⁡
φ
0
0
0
0
0
0
sin
⁡
φ
cos
⁡
φ
h
×
tan
⁡
ψ
h
cos
⁡
ψ
×
+
tan
⁡
θ
1
2
h
×
tan
⁡
ψ
h
cos
⁡
ψ
×
-
tan
⁡
θ
1
2
h
×
t
a
n
⁡
ψ
+
θ
2
h
c
o
s
⁡
ψ
+
θ
2
×
+
tan
⁡
θ
1
2
h
×
tan
⁡
ψ
+
θ
2
⁡
h
c
o
s
⁡
ψ
+
θ
2
×
-
tan
⁡
θ
1
2
+
x
0
y
0
x
0
y
0
x
0
y
0
x
0
y
0
=
x
1
y
1
x
2
y
2
x
3
y
3
x
4
y
4
.Table 2
Camera specifications for the comparison test.
Consideration
Number of options
Details
Horizontal orientations (°)
8
0,45,90
,
…
,
270,315
Vertical orientations (°)
15
1,3
,
…
,
27,29
Height (m)
1
7
Camera type
Horizontal angle of view (°)
1
80
Vertical angle of view (°)
1
80
Available sight range (m)
1
60


## 3.3. Two-Phase Algorithm

Our two-phase algorithm (a) generates the grid model of the candidate locations of camera installation and the target area for surveillance; (b) solves the small scale of phase 1 at a low-resolution; (c) sets the starting value of phase 2 based on the solution from the previous step; and (d) solves the large scale problem of phase 2 at a high-resolution.


### 3.3.1. Phase 1

In phase 1, the minimum number of cameras that satisfies the specific condition given with the grid points of the simulation area is obtained; it is then used to solve the MIN problem to find the location of each camera and the installation condition. We approached the problem using a further-developed method based on BIP formulas [6] for the existing 2D placement problem to solve the 3D placement problem. The detailed procedure is as follows.(1) First, decision variables are assigned, just as when solving a general BIP.(5)
x
i
j
d
e
t
=
1
,
If there exists a camera at position
i
with horizontal orientation
j
vertical orientation
d
,
height
e
,
and angle of view
A
O
V
t
,
0
,
Otherwise,
y
k
=
1
,
I
f the target at position
k
is covered by a camera,
0
,
Otherwise.Thus,x
i
j
d
e
t is 1 if there exists a camera at position i with horizontal angle j, vertical angle d, height e, and AOV t and 0 if not and y
k equals 1 if the surveillance area k is watched with x
i
j
d
e
t and 0 if not.(2) Other parameters required for the formula are defined as follows:(6)
v
i
j
d
e
t
k
=
1
,
if the target at position
k
is visible from camera position
i
with horizontal orientation
j
,
vertical orientation
d
,
height
e
,
and AOV
t
,
0
,
Otherwise.
N
C: number of camera positions.
N
hD: number of horizontal orientations.
N
vD: number of vertical orientations.
N
E: number of heights.
N
A: number of camera types.
N
T: number of target positions.
CVR: given minimal coverage rate.(3) The objective function minimizes the number of cameras as follows:(7)
min
⁡
​
∑
i
=
1
N
C
∑
j
=
1
N
h
D
∑
d
=
1
N
v
D
∑
e
=
1
N
E
∑
t
=
1
N
A
x
i
j
d
e
t
.(4) The following constraints are also necessary:(8)
∑
i
=
1
N
C
∑
j
=
1
N
h
D
∑
d
=
1
N
v
D
∑
e
=
1
N
E
∑
t
=
1
N
A
v
i
j
d
e
t
k
·
x
i
j
d
e
t
≥
y
k
for
∀
k
1
,
…
,
N
T
,
(9)
∑
i
=
1
N
C
∑
j
=
1
N
h
D
∑
d
=
1
N
v
D
∑
e
=
1
N
E
∑
t
=
1
N
A
v
i
j
d
e
t
k
·
x
i
j
d
e
t
≤
N
C
·
y
k
for
∀
k
1
,
…
,
N
T
,
(10)
∑
k
=
1
N
A
y
k
≥
N
T
·
C
V
R
.Equations (8) and (9) are the constraints to obtain y
k and (10) is a constraint such that the sum of y
k must be greater than or equal to the product of the minimum coverage rate and the target surveillance area.


### 3.3.2. Phase 2

Phase 2 solves the FIX problem, which finds the combination for maximum coverage with the constraint of the number of cameras determined from phase 1, with the result obtained from phase 1 as the initial value. This study uses the hill climbing method [19]. Since the objective function is nongradient, a direct-search method was applied; among the different direct-search methods, the alternating variable search method was used, as the problem has a multidimensional variable. This study proposes a hill climbing method, as [19] proposed such a method.Since phase 2 aims to maximize the coverage rate with the minimum number of cameras obtained in phase 1, the number of cameras does not change; only the conditions for each camera change. Eachx
i
j
d
e
t has the specification data for the x-coordinate, y-coordinate, horizontal angle (φ), vertical angle (ψ), installation height (ε), horizontal view angle (θ
1), and vertical view angle (θ
2) according to the camera type, as well as the maximum recognition distance. Each piece of information is both variable and dimensional. A flowchart of this phase is shown in Figure 3 and a hill climbing method of phase 2 is described as follows.Figure 3
Flowchart of Phase 2.The notations and their meaning are as follows:X: set of x
i
j
d
e
t
X
t: set of optimal solutions found in the tth operation
t: the number of operations
s
t: the number of iterations that have an identical objective value
U
X
t: coverage rate of camera set X at tth trial
n: index of a camera
m: index of a camera setting variable (one of i
,
j
,
d
,
e
,
t). (i has both x- and y-coordinate properties, therefore treated as two different variables).Step 0 (initialization). Establish a starting point X
0
∗ and set t
=
0, s
t
=
0.Step 1 (variant search). Set t
=
t
+
1.InX, the nth variable x
i
j
d
e
t is selected. For each index (i
,
j
,
d
,
e
,
t) of x
i
j
d
e
t, the variants are generated by numerically changingmth index of x
i
j
d
e
t to the ± direction. The objective function for each variant is evaluated, and the best one among the tried variants is taken upon comparing the values of the objective function.Step 1.0 (initialization). Establish a starting point X
t and set n
=
0, m
=
0.Step 1.1 (selection of a camera and calculation of the coverage rate)Forn
=
1: n
(
X
t
);
LetX
t
b
e
s
t
=
X
t;
Letx
n
=
nth variable in X
t
Form
=
1 : 6
LetX
t
n
m
+ to be a variant solution generated by numerically increase the value of themth index of x
n, U
X
t
n
m
+ to be the coverage rate of X
t
n
m
+;
LetX
t
n
m
- to be a variant solution generated by numerically decrease the value of themth index of x
n, and U
X
t
n
m
- to be the coverage rate of X
t
n
m
-;
UpdateX
t
b
e
s
t to be argmax
X
∈
X
t
b
e
s
t
,
X
t
n
m
+
,
X
t
n
m
-
U
X, where in case of a tie one is randomly selected
End of Form
End of Forn.Step 1.2 (solution improvement). Set X
t
=
X
t
b
e
s
t.Step 2 (check for improvement)IfU
X
t
>
U
X
t
-
1, then set X
t
+
1
=
X
t, s
t
=
0 and go to Step 1.
Otherwise sets
t
=
s
t
+
1.Step 3 (termination criterion)Ifs
t
>
1, then X
∗
=
X
t; terminate the search.
Otherwise go to Step 4.Step 4 (check for equivalent)IfU
X
t
<
U
X
t
-
1, then set X
t
+
1
=
X
t
-
1, s
t
=
0; and go to Step 1.
Otherwise setX
t
+
1
=
X
t and go to Step 1.Step 0 sets the initial starting point. Here,t and s
t are set to 0.Step 1 finds the best variant to improve the objective function, among the variants generated by increasing or decreasing the indices of eachx
i
j
d
e
t in the solution set X
t. Here, t is increased by 1. Step 1.0 initializes the current optimal solution X
t to be the starting point of this iteration. Step 1.1 finds the best solution which gives the highest coverage rate among the variants of X
t, generated by changing each of indices if x
i
j
d
e
t is in X
t.Step 2 checks if the coverage rate ofX
t found in Step 1 actually increased compared to the coverage rate of X
t
-
1. If it is increased, X
t
+
1 stays as X
t and s
t becomes zero. If not, s
t is increased by 1.Step 3 checks whether the terminating conditions have been met. Here, ifs
t is greater than 1, the optimal solution of phase 2 becomes X
∗
=
X
t and the solution search is completed.Step 4 checks if the coverage rate ofX
t decreased from the coverage rate of X
t
-
1. If decreased, X
t
+
1 is reverted to X
t
-
1 and moves to Step 1; if not, meaning that the values are the same, X
t
+
1 stays at X
t and Step 1 is repeated.The existing alternating variable search method [19] assigns the variable of the changing dimension; when it changes, the moving direction and the magnitude of change for the dimension variable where the objective function value improved the most are found. However, the method adapted for this study preassigns the magnitude of change for the dimension variable, and then finds which dimension variable in which direction improves the value of the objective function most. This method was utilized because the existing method vibrates near the optimal point, causing prolonged computation. Thus, it was more desirable to stop the computation at a proper point and use the solution than to continue the computation until it finished [19]. The method developed in this study eliminates the vibrating solution problem.


## 3.3.1. Phase 1

In phase 1, the minimum number of cameras that satisfies the specific condition given with the grid points of the simulation area is obtained; it is then used to solve the MIN problem to find the location of each camera and the installation condition. We approached the problem using a further-developed method based on BIP formulas [6] for the existing 2D placement problem to solve the 3D placement problem. The detailed procedure is as follows.(1) First, decision variables are assigned, just as when solving a general BIP.(5)
x
i
j
d
e
t
=
1
,
If there exists a camera at position
i
with horizontal orientation
j
vertical orientation
d
,
height
e
,
and angle of view
A
O
V
t
,
0
,
Otherwise,
y
k
=
1
,
I
f the target at position
k
is covered by a camera,
0
,
Otherwise.Thus,x
i
j
d
e
t is 1 if there exists a camera at position i with horizontal angle j, vertical angle d, height e, and AOV t and 0 if not and y
k equals 1 if the surveillance area k is watched with x
i
j
d
e
t and 0 if not.(2) Other parameters required for the formula are defined as follows:(6)
v
i
j
d
e
t
k
=
1
,
if the target at position
k
is visible from camera position
i
with horizontal orientation
j
,
vertical orientation
d
,
height
e
,
and AOV
t
,
0
,
Otherwise.
N
C: number of camera positions.
N
hD: number of horizontal orientations.
N
vD: number of vertical orientations.
N
E: number of heights.
N
A: number of camera types.
N
T: number of target positions.
CVR: given minimal coverage rate.(3) The objective function minimizes the number of cameras as follows:(7)
min
⁡
​
∑
i
=
1
N
C
∑
j
=
1
N
h
D
∑
d
=
1
N
v
D
∑
e
=
1
N
E
∑
t
=
1
N
A
x
i
j
d
e
t
.(4) The following constraints are also necessary:(8)
∑
i
=
1
N
C
∑
j
=
1
N
h
D
∑
d
=
1
N
v
D
∑
e
=
1
N
E
∑
t
=
1
N
A
v
i
j
d
e
t
k
·
x
i
j
d
e
t
≥
y
k
for
∀
k
1
,
…
,
N
T
,
(9)
∑
i
=
1
N
C
∑
j
=
1
N
h
D
∑
d
=
1
N
v
D
∑
e
=
1
N
E
∑
t
=
1
N
A
v
i
j
d
e
t
k
·
x
i
j
d
e
t
≤
N
C
·
y
k
for
∀
k
1
,
…
,
N
T
,
(10)
∑
k
=
1
N
A
y
k
≥
N
T
·
C
V
R
.Equations (8) and (9) are the constraints to obtain y
k and (10) is a constraint such that the sum of y
k must be greater than or equal to the product of the minimum coverage rate and the target surveillance area.


## 3.3.2. Phase 2

Phase 2 solves the FIX problem, which finds the combination for maximum coverage with the constraint of the number of cameras determined from phase 1, with the result obtained from phase 1 as the initial value. This study uses the hill climbing method [19]. Since the objective function is nongradient, a direct-search method was applied; among the different direct-search methods, the alternating variable search method was used, as the problem has a multidimensional variable. This study proposes a hill climbing method, as [19] proposed such a method.Since phase 2 aims to maximize the coverage rate with the minimum number of cameras obtained in phase 1, the number of cameras does not change; only the conditions for each camera change. Eachx
i
j
d
e
t has the specification data for the x-coordinate, y-coordinate, horizontal angle (φ), vertical angle (ψ), installation height (ε), horizontal view angle (θ
1), and vertical view angle (θ
2) according to the camera type, as well as the maximum recognition distance. Each piece of information is both variable and dimensional. A flowchart of this phase is shown in Figure 3 and a hill climbing method of phase 2 is described as follows.Figure 3
Flowchart of Phase 2.The notations and their meaning are as follows:X: set of x
i
j
d
e
t
X
t: set of optimal solutions found in the tth operation
t: the number of operations
s
t: the number of iterations that have an identical objective value
U
X
t: coverage rate of camera set X at tth trial
n: index of a camera
m: index of a camera setting variable (one of i
,
j
,
d
,
e
,
t). (i has both x- and y-coordinate properties, therefore treated as two different variables).Step 0 (initialization). Establish a starting point X
0
∗ and set t
=
0, s
t
=
0.Step 1 (variant search). Set t
=
t
+
1.InX, the nth variable x
i
j
d
e
t is selected. For each index (i
,
j
,
d
,
e
,
t) of x
i
j
d
e
t, the variants are generated by numerically changingmth index of x
i
j
d
e
t to the ± direction. The objective function for each variant is evaluated, and the best one among the tried variants is taken upon comparing the values of the objective function.Step 1.0 (initialization). Establish a starting point X
t and set n
=
0, m
=
0.Step 1.1 (selection of a camera and calculation of the coverage rate)Forn
=
1: n
(
X
t
);
LetX
t
b
e
s
t
=
X
t;
Letx
n
=
nth variable in X
t
Form
=
1 : 6
LetX
t
n
m
+ to be a variant solution generated by numerically increase the value of themth index of x
n, U
X
t
n
m
+ to be the coverage rate of X
t
n
m
+;
LetX
t
n
m
- to be a variant solution generated by numerically decrease the value of themth index of x
n, and U
X
t
n
m
- to be the coverage rate of X
t
n
m
-;
UpdateX
t
b
e
s
t to be argmax
X
∈
X
t
b
e
s
t
,
X
t
n
m
+
,
X
t
n
m
-
U
X, where in case of a tie one is randomly selected
End of Form
End of Forn.Step 1.2 (solution improvement). Set X
t
=
X
t
b
e
s
t.Step 2 (check for improvement)IfU
X
t
>
U
X
t
-
1, then set X
t
+
1
=
X
t, s
t
=
0 and go to Step 1.
Otherwise sets
t
=
s
t
+
1.Step 3 (termination criterion)Ifs
t
>
1, then X
∗
=
X
t; terminate the search.
Otherwise go to Step 4.Step 4 (check for equivalent)IfU
X
t
<
U
X
t
-
1, then set X
t
+
1
=
X
t
-
1, s
t
=
0; and go to Step 1.
Otherwise setX
t
+
1
=
X
t and go to Step 1.Step 0 sets the initial starting point. Here,t and s
t are set to 0.Step 1 finds the best variant to improve the objective function, among the variants generated by increasing or decreasing the indices of eachx
i
j
d
e
t in the solution set X
t. Here, t is increased by 1. Step 1.0 initializes the current optimal solution X
t to be the starting point of this iteration. Step 1.1 finds the best solution which gives the highest coverage rate among the variants of X
t, generated by changing each of indices if x
i
j
d
e
t is in X
t.Step 2 checks if the coverage rate ofX
t found in Step 1 actually increased compared to the coverage rate of X
t
-
1. If it is increased, X
t
+
1 stays as X
t and s
t becomes zero. If not, s
t is increased by 1.Step 3 checks whether the terminating conditions have been met. Here, ifs
t is greater than 1, the optimal solution of phase 2 becomes X
∗
=
X
t and the solution search is completed.Step 4 checks if the coverage rate ofX
t decreased from the coverage rate of X
t
-
1. If decreased, X
t
+
1 is reverted to X
t
-
1 and moves to Step 1; if not, meaning that the values are the same, X
t
+
1 stays at X
t and Step 1 is repeated.The existing alternating variable search method [19] assigns the variable of the changing dimension; when it changes, the moving direction and the magnitude of change for the dimension variable where the objective function value improved the most are found. However, the method adapted for this study preassigns the magnitude of change for the dimension variable, and then finds which dimension variable in which direction improves the value of the objective function most. This method was utilized because the existing method vibrates near the optimal point, causing prolonged computation. Thus, it was more desirable to stop the computation at a proper point and use the solution than to continue the computation until it finished [19]. The method developed in this study eliminates the vibrating solution problem.


## 4. Experimental Results

To evaluate the time efficiency and the coverage rate of the proposed two-phase algorithm, a comparison test was performed using a PC with an Intel Core i5-3337U processor, with 8 GB of DDR3 SDRAM. Matlab R2013b was used, and the BIP solution was obtained using the IBM ILOG CPLEX Optimization Studio 12.6.1. Additionally, the satellite map image of the actual landscape was transformed from an image to text (or numbers) with coordinates using Ascgen 2.0.0 from Jonathan Mathews Software.To compare the global optimal solution obtained from BIP with a solution of the proposed two-phase algorithm, the modeling area was configured as in Figure4. Figure 4(a) is the picture of the actual landscape of a 400 m × 400 m square for the modeling area. Figure 4(b) is the modeling area transformed into 2304 low-resolution grids (48 × 48), and Figure 4(c) is the one transformed into 3600 high-resolution grids (60 × 60). It can be seen that the modeling area in Figure 4(c) with higher resolution reflects the actual landscape of Figure 4(a) better than the modeling area in Figure 4(b) at low-resolution. Since the geometric feature of the Sevit Island shown in Figure 4 is quite complicated requiring a high-resolution modeling, it is adequate to test the effectiveness of the proposed algorithm. Experimental results for three other problems are shown in the appendix.Figure 4
Map of Sevit Island (683 Olympic Blvd, Seocho-gu, Seoul, Korea) width 400 m; length 400 m.
(a)
Picture of modeling area
(b)
48
×
48 grid model
(c)
60
×
60 grid modelThe specifications of cameras for the comparison test are shown in Table2. The horizontal angle for the camera l installation has eight options, starting from 0 degrees and stepping by 45 degrees; the vertical angle has 15 options, starting from 1 degree and stepping by 2 degrees. The height of the installed camera is assumed to be 7 m, the horizontal view angle (θ
1) and vertical view angle (θ
2) are 80 degrees, and the maximum recognition distance is set to 60 m.With the specifications shown in Table2, a test that solves a real-world camera placement problem was carried out and the results were compared. As mentioned before, the two-phase algorithm consists of phase 1, which finds the initial solution (Figure 5(a)) using BIP with the specifications of Table 2 in the modeling area of Figure 4(b), and phase 2, which sets the starting point (Figure 5(b)) of the hill climbing method in the modeling area in Figure 4(c), based on the solution of Figure 5(b), and finds the solution (Figure 5(c)). Figure 5(d) is the solution directly obtained by BIP in the modeling area of Figure 4(c). Consequently, results from the proposed approximation algorithm and BIP can be evaluated, respectively, by comparing Figures 5(c) and 5(d).Figure 5
Solution for each step.
(a)
(b)
(c)
(d)The coverage rate of the solution and the time required for the test in case of Sevit Island area are as follows. When using the two-phase algorithm proposed in this study, the coverage rate is 94.72%, whereas it is 96.23% when using BIP. Therefore, comparing the solutions’ coverage rates indicates that the proposed approximation algorithm obtains a solution with 98.43% of BIP’s quality. The approximation algorithm took 15,823 ms, whereas BIP took 31,724 ms. Thus, the approximation algorithm needs about 49.88% of BIP’s computing time.As shown in these results, the coverage rate of the solution computed by the two-phase algorithm was comparable to that computed by BIP. This stems from the disadvantage of using the hill climbing method, which is simpler than the metaheuristic approximation used in previous studies, which was complemented by using the optimal solution obtained by BIP in phase 1 as the starting point.Moreover, the two-phase algorithm proposed in this study solved the problem more quickly than BIP. This means that the computational complexity of our proposed model is lower than that of BIP and, as mentioned in Section2, our model is more adequate to a large-area problem, as well.For the comparison study in this passage, phase 2 was performed with the area of a 3600 grid (60 × 60), which is much smaller than the actual area that can be computed for a comparison of the solution quality. However, it would be more realistic and more accurate to approach with the higher-resolution area in phase 2, because the high-resolution terrain can reflect the actual landscape more precisely than the low-resolution terrain in the same space. Figure6 shows the solution obtained by phase 2, performed in a higher-resolution terrain (40,000 grids (200 × 200)) based on Figure 5(b). While existing studies have a difficulty in finding a solution for such a large terrain, the approximation algorithm proposed in this study can find a solution.Figure 6
Solution obtained from high-resolution terrain.We performed the test not only with Sevit Island as a modeling area, but also with other modeling areas. Table3 shows the comparison results of the two-phase algorithm (TPA) and BIP in the other modeling areas, of which solution details are described in Appendix.Table 3
Comparison test results.
Test area
Computing time (milliseconds)
Coverage rate (%)
TPA
BIP
TPA/BIP
TPA
BIP
TPA/BIP
Sevit Island
15,823
31,724
49.88%
94.72
96.23
98.43%
Gangjeong Goryeong-bo (weir)
4,378
17,030
25.71%
85.51
90.58
94.40%
Incheon port
9,896
32,665
30.30%
86.32
91.45
94.40%
Dongmyeong dock
31,403
48,785
64.37%
70.00
80.56
86.89%This study was able to find the solution for terrains with a large number of grid points because it used phase 1 and phase 2. Phase 1 finds the global optimal solution using BIP at a low resolution, and phase 2 elaborates on the solution offered in phase 1 at a high resolution. This study’s contribution is providing an effective method to solve the optimal camera placement problem for a wide, detailed area, which can be applied in real-world situations.


## 5. Conclusions

This study presented a two-phase approximation algorithm to solve the optimal camera placement problem. This algorithm had lower computational complexity than existing methods and did not reduce the quality of the solution. As a result, the optimal camera placement problem could be solved, even with wide, real-world terrain under complex conditions that could not be solved with the existing BIP method.The two-phase algorithm proposed in this study finds a global optimal solution in phase 1 to use as the starting point in phase 2; thus, the confidence for the starting point is large. A comparison study in Section4 reveals that the quality of the solution did not show significant differences from BIP.Meanwhile, the two-phase algorithm proposed in this study had too high computational complexity to solve complex problems and thus could not reflect reality. However, the low-resolution problem could be solved using BIP, which not only offered a global optimal solution but also provided the idea of applying the solution of phase 1 in higher-resolution terrains that look more like reality. Phase 2 changed the method of solving the problem so that other perspectives could be applied to problems in the future. This study used a hill climbing method in phase 2 with low computational complexity, but other methods, such as GA or PSO, could also be used in later studies.The limitation of the study was that it used a hill climbing method in phase 2, which converges to relative local optimal solutions, instead of other approximate algorithms such as SA, GA, or PSO that have a higher chance of avoiding local optima. In this regard other approximate algorithms could also be applied in later studies. To solve the optimal camera placement problem with this modeling area with a large number of grid points under realistic restrictions, one of two approaches should be chosen: (i) to solve the problem through a simple algorithm at high resolution or (ii) to solve the problem at a relatively low resolution using a different method that needs more computational resources but has a higher change of finding a global optimal solution. This paper proposed the former to solve the problem at a high resolution in a wider terrain. Finding a proper balance point by comparing the two methods is left for future work.



---

*Source: 4801784-2016-09-05.xml*