convergence condition (Equation 10) of the proposed algo-
rithm ensures that the absolute values of the iteration step
sizes form a strictly decreasing sequence, which can avoid the
oscillation phenomenon occurring in Figure 8b.
The computational times of all the test schemes are shown
in Table 3. Comparing the results of the
IF
and
IDIF
schemes
with their revised versions (
RIF
and
RIDIF
schemes), we found
that the computational effort of the iterative search based on
the
Δ
x
F
criterion depends largely on the step size equation
used. The
IF
and
IDIF
schemes are not well optimized because
they employ the
CCD
pixel size to calculate the iterative step
size (Equation 14). In real scenarios, pushbroom images are
usually somewhat under- or over-sampled due to the mis-
match between the sampling frequency of the scan lines and
the aircraft speed (images are sometimes deliberately over-
sampled, e.g., the nadir image of flight strip A; see Table 1),
and the step size calculated from Equation 14 may be too small
or too large. Both situations decrease the convergence speed.
The experimental results in Table 3 show that the pro-
posed algorithm (
IFSF
and
IDSF
schemes) usually needs less
computational time than the previous methods (
IF
and
IDIF
schemes) and their revised versions (
RIF
and
RIDIF
schemes).
This result is also supported by Table 4, which illustrates
the average number of operations for each search of a ground
point. As shown by the example in Figure 8, the vertical
imaging condition assumed in Equation 7 is not always well
satisfied in real scenarios, due to unavoidable orientation
changes, and, therefore, an iterative search may not quickly
converge to sub-pixel accuracy. The proposed algorithm com-
monly requires fewer operations, mainly because a sequential
search as well as a linear interpolation is used in the fine
search stage to replace the inefficient iterative search.
As shown in Table 5, the statistical results of all the test
images confirm that the proposed scan-line search algorithm
(
IFSF
and
IDSF
schemes) is reliable and can save at least 15
percent of the computational effort when compared to the
previous approaches, and the
IDSF
scheme is only slightly
faster than the
IFSF
scheme. Given that the iterative search
based on the
D
criterion requires a time- and memory-con-
suming pre-processing procedure to segment the
CCD
line and
to determine the scan-plane equation parameters (Wang
et al
.,
2009), the
IDSF
scheme is only recommended for applications
that need to project high-density ground points.
Conclusions
The object-to-image projection plays a fundamental role in
pushbroom image processing, and its core problem is to de-
termine the corresponding scan-line coordinate of the object
point to be projected. As the scan-line search for large-format
pushbroom images is very compute-intensive, many research-
ers have developed iterative algorithms to accelerate the
calculation. However, the existing iterative scan-line search
algorithms were typically designed with the assumption of
meeting the ideal line imaging geometry. In real scenarios
affected by atmospheric turbulence, their computational ef-
ficiency is not sufficiently high and, more importantly, the
iterations may fail to converge. This paper has presented a
coarse-to-fine scan-line search algorithm that can be used for
the object-to-image projection of airborne pushbroom images
affected by strong atmospheric turbulence. The improvements
of the proposed algorithm over the previous iterative search
methods concern three aspects: (a) in the rough search stage,
a more suitable iterative step size equation taking account of
the under- and over-sampled issue in pushbroom imaging is
T
able
3. C
omputational
T
imes
(
in
S
econds
)
for
P
rojecting
1,000,000
G
round
P
oints
. T
he
T
est
P
rogram was
R
un
on
a
2.13 GH
z
I
ntel
M
obile
P
rocessor
and was
C
ompiled with
the
I
ntel
C/C++ 12.0 C
ompiler
U
sing
the
“-O3” O
ptimization
F
lag
Flight strip Image IF RIF IFSF IDIF RIDIF IDSF
A
Backward 3.33 1.96 1.40 2.16 1.77 1.40
Nadir
3.63 1.97 1.48 2.27 1.78 1.41
Forward 3.06 1.82 1.38 1.94 1.64 1.36
B
Backward 2.09 1.99 1.79 1.91 1.81 2.01
Nadir
2.14 2.02 1.74 1.79 1.79 1.71
Forward 2.07 2.06 1.69 2.02 1.98 1.71
T
able
4. A
verage
N
umber
of
O
perations
P
er
S
earch
Operation
a
Flight strip
Image
IF
RIF
IFSF
IDIF
RIDIF
IDSF
D
A
Backward
–
–
–
4.82
4.82
2.09
Nadir
–
–
–
5.22
5.22
2.24
Forward
–
–
–
4.90
4.90
2.12
B
Backward
–
–
–
6.10
6.10
2.77
Nadir
–
–
–
6.07
6.07
2.77
Forward
–
–
–
6.25
6.25
2.86
Δ
x
F
A
Backward
8.72
4.98
3.45
4.15
3.06
2.41
Nadir
10.18
5.20
3.69
4.98
3.49
2.59
Forward
9.65
5.43
3.59
4.77
3.38
2.42
B
Backward
4.94
4.54
4.08
2.60
2.54
2.36
Nadir
4.91
4.50
4.06
2.59
2.53
2.33
Forward
5.10
4.70
4.16
2.75
2.70
2.43
a The operations
D
and
Δ
x
F
refer to the point-plane distance calculation used in the search based on the
D
criterion, and the object-to-image
projection used in the search based on the
Δ
x
F
criterion, respectively.
T
able
5. E
xperimental
R
esults with
255 P
ushbroom
I
mages
(85 F
light
S
trips with
T
hree
D
ifferent
V
iews
)
IF
RIF
IFSF
IDIF
RIDIF
IDSF
Number of images containing scan-line search errors
136
110
0
116
101
0
Average time cost for projecting 1,000,000 points (s)
2.68
2.12
1.72
1.97
1.90
1.64
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
July 2015
571
