running time of Dijkstra’s algorithm on a graph with edges
E
and vertices
V
can be expressed as a function of
|
E
|
and
|
V
|
using big-O notation (Cormen
et al.
, 2001). The running
time of Dijkstra’s algorithm depends on how the min-priority
queue is implemented. The simplest implementation of the
Dijkstra’s algorithm stores the vertices of set
Q
in an ordinary
linked list or array, and each extract_min(
Q
) (line 10) opera-
tion is simply a linear search through all vertices in
Q
. In this
case, the running time is
Θ
(|
V
|*|
V
|+|
E
|).
For a sparse graph, i.e., graphs with far fewer than
Θ
(|
V
|*|
V
|) edges, Dijkstra’s algorithm can be improved by
implementing the min-priority queue with a binary min-heap.
The pseudo-code for Dijkstra’s algorithm with a binary min-
heap is presented in Algorithm 2. Each extract_min_with_
min- priority(
Q
) (line 11) operation then takes time
Θ
(lg|
V
|).
As before, there are |
V
|
such operations. The time to build
the binary min-heap is
Θ
(lg|
V
|). Each
Q
.decrease_min-
priority(
v
, dist[
v
]) operation (line 16) takes time
Θ
(lg|
V
|),
and there are still at most |
E
| such operations. Therefore, the
algorithm requires
Θ
((|
V
|+|
E
|)lg|
V
|) time (Fredman and Tar-
jan, 1987; Cherkassky
et al.
, 1996; Cormen
et al.
, 2001; Chen
et al.
, 2007). To apply Dijkstra’s algorithm to seamline deter-
mination, each node has eight neighboring nodes. The graph
is sufficiently sparse where the number of the edges is 8*|
V
|.
Therefore, we use the min-priority queue with a binary min-
heap to improve the efficiency of Dijkstra’s algorithm.
Experimental Results and Discussion
The proposed method has been implemented in C++ in
Microsoft Visual C++ 6.0. The Geospatial Data Abstraction
Library (
GDAL
) is used to read and write image files. A desktop
computer with an Intel(R) Core(TM) i3-540 M 3.07
GHz
pro-
cessor, 6
GB
of internal memory and a hard disk with a 500
GB
capacity, a 16
MB
cache and 7200 r/min speed was used for
data processing. The proposed method was performed with
T
=0.65
and
A
= 15, where
T
is the scale factor for the marker
extraction and
A
is the area of the smallest discernible object.
The results of the proposed method were compared with
Dijkstra’s (Dijkstra, 1959), Chon’s (Chon
et al.
, 2010) and
Pan’s (Pan
et al.
, 2014b) algorithms. The experiment of Data
Set 1 is shown in Figure 3 to Figure 6; and the experiment
of Data Set 2 is shown in Figure 7 to Figure 10. All of the
methods were performed without an image pyramid except
Pan’s method. Pan’s method builds one pyramid level with a
3×3 average filter (Pan
et al.
, 2014b). In Figure 3 and Figure
7, (a) and (b) show the overlapping area of the left and right
image, respectively; (c) shows the
POA
s (white areas) overlaid
on the overlapping area of the left image. In Figure 3c and
Figure 7c, a technique for minimizing the maximum object
cost is adopted to determine the
POA
s. The technique is to
find a connected region between the start object and the end
object for which the maximum object cost in the region is a
minimum. Therefore, obvious objects, especially the build-
ings and high bridges, are excluded as much as possible from
the determined
POA
s. In Figure 4 and Figure 8, (a) compares
the seamlines determined by Dijkstra’s algorithm with those
of the proposed method, (b) shows the details of the marked
rectangles in (a), (c) compares the seamlines determined by
Chon’s algorithm and those determined by the proposed
method, (d) shows the details of the marked rectangles in (c),
(e) compares the seamlines determined by Pan’s algorithm
and those determined by the proposed method, and (f) shows
the details of the marked rectangles in (e). The reasonable
seamline should avoid crossing obvious objects as much as
possible, e.g., buildings and high bridges. Relief displacement
mainly occurs because a
DTM
does not contain elevations for
these obvious objects (Pan
et al.
, 2014b; Chen
et al.
, 2014). In
Figure 4, the proposed method successfully avoided crossing
most of the obvious objects, and the seamlines were mainly
along the roads or low bridges. The seamline only crossed one
end of the bridge, which was shown in Figure 4b. Dijkstra’s
algorithm crossed several bridges. Chon’s method went across
one bridge and two buildings, which was shown in Figure 4d.
Pan’s method had a good result in Data Set 1. In Figure 8, the
proposed method also successfully avoided crossing most of
the obvious objects, and the seamlines were mainly along the
road. Dijkstra’s algorithm crossed several buildings, which
was shown in Figure 8b. Chon’s method went across several
buildings, which was shown in Figure 8d. Pan’s method went
across several buildings, which was shown in Figure 8f. Ac-
cording to the Figure 4 and Figure 8, compared with the other
three methods, the seamlines determined by the proposed
method were more reasonable and successfully avoided
crossing most of the obvious objects, and the seamlines were
mainly along the roads or low bridges. The final resultant
mosaicked images using different seamline determination
Algorithm 1: Dijkstra’s Algorithm
1 Dijkstra
(
G
,
s
)
2
dist[
s
] = 0
3 for each
vertex
v
∈
V
4 if
v
≠
s
5
dist[
v
] =
∞
6
pre [
v
] = undefined
7
S
= Ø
8
Q
=
V
9 while
Q
≠
Ø do
10
u = extract_min(
Q
)
11
S
=
S
∪
{
u
}
12 for
each
vertex
v
∈
Adj(
u
) do
13
dist[
v
] = min(dist[
v
], dist[
u
]+
w
(
u
,
v
))
14
pre[
v
] =
u
Algorithm 2: Dijkstra’s Algorithm with Binary Min-heap
1 Dijkstra_Binary_Min-heap
(
G
,
s
)
2
dist[
s
] = 0
3 for each
vertex
v
∈
V
4 if
v
≠
s
5
dist[
v
] =
∞
6
pre [
v
] = undefined
7
Q
.add_with_min-priority(
v
, dist[
v
])
8
S
= Ø
9
Q
=
V
10 while
Q
≠
Ø do
11
u
= extract_min_with_min- priority(
Q
)
12
S
=
S
∪
{
u
}
13 for
each
vertex
v
∈
Adj(
u
) do
14
dist[
v
] = min(dist[
v
], dist[
u
]+
w
(
u
,
v
))
15
pre[
v
] =
u
16
Q
.decrease_min-priority(
v
, dist[
v
])
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
February 2016
125
