Similar to Chon
et al.
(2010), minimizing the maximum
difference is used to determine the
POA
s. To improve the
efficiency, instead of using Dijkstra’s algorithm to determine
the
POA
s, the proposed method uses the connectivity analysis
algorithm and binary search to determine the
POA
s gradually.
The proposed algorithm is summarized as below:
1. Determine the start object and end object. The start and
end objects are the objects to which the start and end
points of the seamline belong, respectively. The inter-
section points of image boundaries are determined as
the start and end points (Chon
et al.
, 2010). In Figure 2,
the start object and end objects are object I and object D.
2. Sort the cost of the objects in excluding the start and
end objects ascending. As shown in Figure 2, the sort-
ing cost array SortCost[] is [0.22, 0.24, 0.34, 0.35, 0.42,
0.45, 0.56, 0.65, 0.80, 0.85]. Set
L
to 0 and
R
to
N
−3,
where
N
is the number of objects.
3. Set the threshold:
TH
= SortCost [(
L
+
R
)/2]. An object
with a cost that is not larger than
TH
could be passed.
A connectivity algorithm is used to find if there exists a
way between the start object and the end object.
4. If a path between the start object and the end object ex-
ists, set
R
= (
L
+
R
)/2; if not, set
L
= (
L
+
R
)/2.
5. If
R−L
>1, repeat Step 3 and Step 4 until
R-L
< =1. Then,
the minimized maximum difference value
MinMaxDiff
is equal to SortCost[
R
]. The objects whose costs are not
larger than the
MinMaxDiff
together constitute the
POA
s.
Seamline Determination at the Pixel Level
The seamline optimization at the pixel level is to optimize the
seamlines in the
POA
s. Intersection points of image boundaries
are determined as the start and end points (Chon
et al.
, 2010).
NCC x y
f i j f
g i j g
x y
x y
j y
y
i x
x
( , )
[( ( , )
)( ( , )
)]
(
,
,
=
∑∑
−
−
−
−
= −
+
= −
+
2
2
2
2
f i j f
g i j g
x y
j y
y
x y
j y
y
i x
x
i
( , )
)
( ( , )
)
,
,
−
−
−
= −
+
−
= −
+
= −
+
∑
∑∑
2
2
2
2
2
2
2
2
= −
+
∑
x
x
2
2
(6)
f
f i j g
g i j
x y
j y
y
i x
x
x y
j y
y
−
= −
+
= −
+
−
= −
+
=
=
∑∑
∑
,
,
( , ),
( , )
1
25
1
25
2
2
2
2
2
2
i x
x
= −
+
∑
2
2
(7)
NCC x y
f i j g i j
f i j
g i j
j y
y
j y
y
i x
( , )
( , ) ( , )
( , )
( , )
=
∑
∑
−
= −
+
= −
+
=
1
25
2
2
2
2
−
+
= −
+
= −
+
= −
+
= −
+
∑
∑
∑∑
∑
−
2
2
2
2
2
2
2
2
2
2
2
1
25
x
i x
x
j y
y
i x
x
j y
y
f i j
f
[
( , )
(
(
i j
g i j
g i j
j y
y
i x
x
j y
y
j y
, )) ][
( , )
(
( , )
= −
+
= −
+
= −
+
= −
∑∑
∑
−
2
2
2
2
2
2
2
2
1
25
2
2
2
2
2
2
2
2
2
y
i x
x
i x
x
i x
x
+
= −
+
= −
+
= −
+
∑∑
∑
∑
) ]
(8)
A quantity called the normalized cross correlation (
NCC
)
between the overlapping area of two images is used to esti-
mate the degree of difference (Chon
et al.
, 2010). The
NCC
for a
pixel (
x
,
y
) is computed using 5×5 sub-images as expressed in
Equation 6 and Equation 7, where
f
–
x,y
and
g
–
x,y
are the average
of the 25 pixel values of the left and right image;
f
(
i,j
) and
g
(
i,j
)
are the pixel values at coordinates (
i,j
) in the left and right
image, respectively;
i
and
j
are row and column coordinates.
To improve the efficiency, the
NCC
is computed with Equation
8. The
NCC
has a range between −1.0 and 1.0. The cost (degree
of difference) at pixel (
x
,
y
), cos
t
(
x
,
y
), is defined in Equation
9. The cost value approaches 0.0 for pixels with small differ-
ences and 1.0 for pixels with large differences.
cos
t
(
x
,
y
) = [1.0 –
NCC
(
x
,
y
)]/2.0
(9)
The cost of pixel (
x,y
) in the overlapping area is defined as:
D
(
x
,
y
) = cos
t
(
x
,
y
)
f
(
x
,
y
)
∈
POAs
+
∞
otherwise
.
(10)
Instead of using the defined cost of pixels directly, the
proposed method uses the differential cost to calculate the lo-
cal cost between neighboring pixels when applying Dijkstra’s
algorithm to search for the final seamlines (Pan
et al.
, 2014b).
The local cost between two neighboring pixels is defined as:
d
uv,kl
= |
D
(
u,v
) –
D
(
k,l
)|
(11)
where (
u,v
) and (
k,l
) are two neighboring pixels;
D
(
u,v
) and
D
(
k,l
) are the costs of pixels (
u,v
) and (
k,l
), respectively,
which are defined in Equation 10. Let
NBR
(
u,v
) be the set
of neighboring nodes of (
u,v
), cos
t
(
u,v
), and cos
t
(
k,l
) be the
global minimum costs from the start pixel to (
u,v
) and (
k,l
),
respectively. Then,
cos
t
(
u,v
) = min{
d
uv,kl
+ cos
t
(
k,l
);(
k,l
)
∈
NBR
(
u,v
)}
(12)
Dijkstra’s Shortest-Path Searching Algorithm with a Binary Min-heap
Dijkstra’s algorithm is a global optimization technique that
solves the single-source shortest-path problem on a weight-
ed, directed graph
G
= (
V, E
) for the case in which all edge
weights are nonnegative (Dijkstra, 1959; Cormen
et al.
, 2001).
Given a source vertex
s
in a weighted directed graph
G
= (
V,
E
) where all edges are non-negative, the pseudo-code for
Dijkstra’s algorithm is presented in Algorithm 1. Dijkstra’s
algorithm maintains the vertices of the graph
V
in two disjoint
and complementary sets of vertices
S
⊆
V
and
Q
⊆
V
.
S
in-
cludes all vertices whose shortest path from
s
has been deter-
mined.
Q
is a priority queue initialized for all
x
∈
V
.
Q
is keyed
by dist[
x
], which is the length of the current shortest known
path from
s
to
x
∈
Q
.
w
(
u, v
) is the length of the two neighbor
nodes
u
and
v
(Cormen
et al.
, 2001). The upper bound of the
(a)
(b)
Figure 2. The demonstration of POAs determination: (a) the object cost map, and (b) the POAs (white objects) of the object cost map
124
February 2016
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
