Trackbeforedetect techniques based on dynamic programming have provided solutions for detecting targets from a sequence of images. In its application to airborne threat detection, dynamic programming solutions should take into account the distinguishable properties of objects in a collision course. This paper describes the development of a new track scoring function that accumulates scores for airborne targets in Bayesian framework. Numerical results show that the proposed scoring function has slightly better detection capabilities.
1. Introduction
Sense and avoid is one of the most basic responsibilities for aircraft operations. Pilots who operate aircraft are always required to maintain a high level of situation awareness in order to avoid a midair collision. Increased traffic densities and large speed differentials in airspace can have high potentials for air collisions even in daylight and in visual flight rule conditions. Thus, an autonomous collision detection and avoidance capability is a critical capability for a variety of unmanned aerial vehicle applications in airspace. In order to aid pilots or autonomous flight computers much effort has been made in developing robust collision detection algorithms. Recent improvements in the field of image processing and computer vision have raised interest in the use of image sequences from passive optical sensors for detecting potential threats
[1

5]
.
Most of the studies have been carried out by using a trackbeforedetect (TBD) technique and this technique, integrates the sensor data about a tentative target over time by combining target detection and estimation. Unlike other conventional detection techniques such as probabilistic data association (PDA) and multiple hypotheses testing (MHT), a signal is tracked before declaring it as a target. In the literature, TBD methods based on dynamic programming (DP) have been proposed for dim target detection and tracking in highly cluttered environments where the signaltoratio (SNR) is relatively low
[1

6]
. The DPbased TBD methods effectively integrate the observations along possible trajectories and those trajectories for which the tracking score exceeds a given threshold are returned as possible targets
[6]
. The DP solution proposed by Barniv is one of the first papers in the literature
[1]
that has provided a fundamental approach to detect and track dim moving targets simultaneously as registered in an image set. Arnold et al.
[3]
improved the existing solutions in terms of computational efficiency and performance against non Gaussian noise characteristics. The analysis of the DPbased TBD was carried out by using extreme value theory in
[6]
. On the other hand, Nichtern et al.
[7]
dealt with some practical issues on setting the parameters of dynamic programming solutions in order to maximize the tracking capability. Although, there have been efforts to solve the various important TBD problems, the problem of developing track scoring functions has received less attention, particularly when it applies to airborne target detection on the flight path. As collision threats have a few geometric features from their relative dynamics, incorporating these features into track scoring functions is important to enhance the detection performance.
The fundamental technique presented in this paper is based on the DP solutions that were proposed in
[1
,
3]
. However, our current work has led to some technical innovations in its application to the problem of airborne collision threat detection. In particular, a new track scoring function is proposed to improve the collision detection performance. This is done by reflecting two distinguishable properties of a nonmaneuvering target in a collision course. First, a target on a nearcollision course remains stationary in image view as collision occurs when the lineofsight between aircrafts is maintained almost stationary. Second, the rate of image expansion for a collision course target is approximately inversely proportional to the time to collision
[8]
. As a result, the main problem of concern is in the development of a DPbased TBD technique that takes in to account these two properties for early airborne target detection.
This paper is organized as follows. In Section 2, the basic approach to DPbased TBD is described. Section 3 illustrates the development and implementation of a track score function of a DP solution for airborne target detection. Section 4 presents the numerical results and its performance assessment of the proposed method. The final section summarizes the overall discussion.
2. Dynamic Programming Solutions for Airborne Target Detection
The objective of airborne target detection is to determine the trajectories that are most likely to have originated from the actual threat by using the measured image sequence of
K
frames. Solutions for this problem should be able to provide high detection performance. Here, the size of threats can vary from subpixel to a few pixels in the presence of a background clutter. This section describes the outline of the DP algorithm and its application to solve TBD problem.
 2.1 Overall procedure
The DPbased target detection algorithm has been divided into three steps. In the first step, the raw image sequence passes through preprocessing stages. It emphasizes the potential targets and provides a fourdimensional target intensity measurement set with the spatial and velocity resolution cells. Spatial resolution corresponds to the image sensor resolution. The velocity resolution depends on the design parameter which is related to a threedimensional data processing stage. In this step, a closeminusopen filter which is one of the morphological filtering algorithms is employed to extract peak regions in images and to generate a nonnegative output
[9]
. The second step is the DPbased target detection stage that operates on the unthresholded data set that is provided by the preprocessing step. Basically, the DP approach provides a single optimization procedure that includes both data association and track detection as it avoids a thresholding process. Moreover, it also preserves all the signal information in the raw image data. The DPbased TBD method presented hereafter is based on the approaches that are described in
[1
,
3]
. The final decision on the target presence and position is made in the third step by evaluating the criteria for both threshold values and uniqueness of track histories over a certain length of image frames.
 2.2 Target and Sensor Models
Target motion is modeled to be approximately linear over the image plane of an image sensor, with allowances for curvature, acceleration, and jitter. This model illustrates the target motion onto the image plane with the resultant target dynamics and it described two differential equations of motion as shown in
Fig. 1
. The target model is defined by a discretetime statespace equation of the form,
Where,
x
_{k}
= [
x, y, u, v
]
^{T}
_{k}
is the target state vector at frame
k
. (
x, y
) ∈ [(1, 1), (
L, L
)] and (
u, v
) ∈ [(−
M
/2, −
M
/2), (
M
/2,
M
/2)] are the horizontal and vertical relative target positions and velocities in discrete image dimensions, respectively. It is assumed that the discrete states are uniformly sampled over their ranges. The target state innovations are modeled as zeromean random processes of the form,
Coordinate system for the target and sensor models. The relative target motion is defined by a discretetime statespace equation on the image plane.
where ζ
_{xk}
and ζ
_{yk}
are the unpredictable target position transitions by sensor registration errors.
and
are the unknown target acceleration components. The process noises are zeromean Gaussian white noises with unknown statistics. The state transition matrix,
F
_{k}
and
G
_{k}
are defined as follows by considering the problem of tracking a point target that moves with constant velocity in the image plane.
where Δ
t_{k}
is the time interval between the (
k
− 1)th and the
k
th image frames.
The raw image data are preprocessed to suppress clutter signals prior to the dynamic programming stage. The threedimensional convolution filter is applied to brief image sequences for the extraction of the target’s expansion rate as well. Output from the image preprocessing step consists of discrete, fourdimensional matrices, Z
_{k}
= {
q
_{k}
,
r
_{k}
}.
q
_{k}
and
r
_{k}
are the amplitude and the expansion rate measurements of the target, respectively. At time
k
, each pixel of the measurement is modeled as follows,
where
h_{k}^{(i, j)}
is the contribution of the target on each pixel and it relies on the point spread function and the state.
w_{k}
is an additive noise with known statistics and
n_{k}
is a sample from a random noise process. The noise distributions of
w_{k}
and
n_{k}
are generally independent and they are derived from different physical processes. As the rate of the target expansion is almost inversely proportional to the relative distance,
q
_{k}
can be defined as a state if the state vector includes threedimensional positions.
 2.3 Dynamic Programming Solution
As the target state is assumed as the Markov process, the result of each stage depends only on the results of the previous stage. The maximum possible value of the scoring function for collision threat is obtained by the inclusion of a sequence of intermediate functions that represent the maximum partial sum of the previous scoring functions. Based on the posterior odds formulation, the scoring function,
s
is defined as the logarithm of the ratio of posterior probabilities
where (
x
_{k}
,
x
_{k ? 1}
, …,
x
_{1}
) is the targetpresent hypothesis for the specific target state sequence that enables in state
x
_{k}
at time index
k
. The alternative hypothesis is represented by,
H
_{0}
while
Z_{k}
represents the observation set. In the form of a DP solution such a procedure can be represented by a recursive form by resembling the following equation.
In every successive DP processing stage both the maximizing value of
x
_{k ? 1}
and the corresponding maximum value
h
_{k ? 1}
are chosen. They are stored for each possible value of
x
_{k}
. The a posteriori event probabilities
P_{k│k}
(
x
_{k}
,
x
_{k ? 1}
, …,
x
_{1}
│
Z_{k}
) and
P_{k│k}
(
H_{0}│Z_{k}
) are applied to the track sequence and nulltarget hypotheses, respectively. By applying Bayes Theorem to both the numerator and denominator yields,
where
P
_{k│k ? 1}
is the prior probability of the events at the processing state
k
conditioned on the measurements up to the previous state and
p
(
z
_{k}
│
x
_{k}
) and
p
(
z
_{k}
│
H
_{0}
) are the probability density functions of the observations in stage
k
conditioned on the targethypothesis and nullhypothesis. The assumption of a firstorder Markov model for the target state innovation implies that the state
x
_{k}
is statistically independent of the previous state
x
_{k ? 1}
for the given observations. Hence, the following recursive form is derived by applying the definition of conditional probability to the second term on the righthand side of the equation (for derivation details refer to
[3]
).
It is usually quite reasonable to assume that given the true state
x
, the target amplitude is independent of the rate of the target expansion. The target amplitude of the pointlike target depends on the noise sources that are created by the change of weather such as clouds or lighting conditions. On the other hand, the rate of expansion is a function of the relative distance between the target and own aircraft
[5]
. With this assumption, the second term on the righthand side implies that
where
p
(
q
_{k}
│
x
_{k}
) ,
p
(
q
_{k}
│
H
_{0}
) ,
p
(
r
_{k}
│
x
_{k}
) , and
p
(
r
_{k}
│
H
_{0}
) are the probability density functions of the two independent observations in stage
k
. Finally, the desired DP update equation is given by reinserting the logarithm and carrying out the maximization.
In the recursive update equation, the function
h_{k}(x_{k})
can be interpreted as the score of the candidate track up to state
x
_{k}
.
 2.4 Implementation of Dynamic Programming
In order to detect target expansion, a subwindow around each pixel was explored. The subimage that corresponds to the window is convolved with a smoothing mask. This mask performs lowpass filtering for the output considered as the measure of target strength. This measurement is obtained in terms of the increase of the target strength and it is tracked over a number of stages. The mean rate of expansion was estimated by applying least squares to the target strength.
The probability density functions of the observations are based on the prior knowledge of amplitude and noise characteristics of potential collision threats. These distributions are also adaptively determined from the observation sequence. As the given measurement noise is additive, the likelihood ratio becomes,
where
p_{t}
and
p_{n}
denote the target and noiseonly probability density functions, respectively.
and
are the anticipated target characteristics. In order to model the two output characteristics, a standard Gaussian distribution is developed, whereas the parameters of the distribution are empirically chosen from the data. Other various nonGaussian distributions can be used to more accurately reflect on the highly nonlinear characteristics of observations
[3]
.
The transition cost function accounts for the probability of target maneuvers and the noise properties of optical sensors. The transition cost is derived from both a priori models for target maneuvers and the models for state resolution cell quantization and errors in image processing steps. The transition probability is a function of the absolute difference between the expected and actual state at state
k
. Here, the expected state
x
_{k│k ? 1}
is calculated from the given target model. Thus, the definition of the state transition cost function can be written as follows,
As the innovation of the target state is assumed to be independent in time and dimension, the transition costs are separable into the product of transition probabilities of each dimension. These transition probabilities are to be computed from the difference of the Gaussian error functions that are given by,
where Δ
x
is the difference between the current state and the predicted state, Erf is the Gaussian error function,
is the floor function, σ
_{x}
is the standard deviation of the target innovations in terms of resolution cells and
x
_{res}
is the resolution of the quantized states.
3. Numerical Results
A DPbased TBD method is based on the proposed track scoring function which is implemented and evaluated by using a synthetic image sequence. In order to carry out the trial our simulation study requires, the image sequence with 100 frames and a frame size of 32 by 32 pixels at 10 frames per second. This is synthetically generated. The image sequence contains the simulation of a moving target that moves through a structured background. A motion effect is caused by jitter and an aperture effect from the optics is also added onto the overall sensor model. In this image sequence, a single artificial target with relatively bright amplitude appears at the 20th frame and it flies from the center to the lower right. The target gradually expanded from the point to the shape of a plus sign that is defined by the image intensity at each pixel position in order to emphasize the target detection capabilities for objects on a collision course.
The results of grayscale morphological filtering are
Morphological image processing sequence for artificial image data (20th, 40th, and 60th frames for each column). (a)(c) Raw input images. (d)(f ) Close images. (g)(i) Open images. (j)(l) Closeminusopen images. A combination of the two operations extracts the peak regions in images.
shown in
Fig. 2
for the three chosen images.
Figures 2
.(a) (c) shows the raw input images from the image sequence.
Figures 2
.(d)(f ) show the results of closing and this tends to preserve small brighter than the background.
Figures 2
.(g) (i) show the results of an opening and this tends to remove the bright regions that are small in size. Overall image processing results are shown in
Figs. 2
.(j)(l). They confirm that the CMO morphological filtering has removed large clutters such as clouds in the background in order to extract pointlike targets.
The simulation parameters are given in
Table 1
.
Figure 3
shows the results of the DP algorithm. The displayed intensity value has been scaled to reflect the track scoring for each spatial resolution cell in the chosen velocity plane. The target appears as a bright area which moves near the center of the image in
Figs. 3
.(b)(c). The increased signal strength reflects the consistent integration procedure by the DPbased TBD
The DPTBD method applied on the image sequence with the proposed track scoring function: (a)(c) Three frames from sequence (20th, 40th, and 60th frames). As the algorithm accumulates scores by evaluating the target’s amplitude and expansion rate, the existence and the state of the target are revealed more clearly.
Comparison of two track scoring functions from different observation sets: the solid line is the result calculated from the two observations and the dotted line is that from the amplitude observation only. (a) Signaltonoise ratio. (b) Detection errors between the true target positions and the estimated position of maximum scores.
method. This increase in both the size and amplitude of the target is considered in the track scoring function.
Figure 4
shows a comparison of the track scoring functions by taking into account the two different observation sets. The
Summary of the simulation parameters
Summary of the simulation parameters
first observation set provides both
q
and
r
observations to the DP module. The second observation set consists of only the target amplitude estimates. In each stage, the pixel that has the maximum value from DPbased track scoring functions is considered as a potential target without a decision step. As expected,
Fig. 4
.(a) indicates that the detection performance of the DPbased TBD method with the proposed track scoring function is slightly improved in terms of the SNR. The position error depicted in
Fig. 4
.(b) shows that it converges a number of frames that are advanced as two collision properties which are considered in the track scoring function.
4. Conclusion
In this paper, a track scoring function of DPbased TBD method is proposed to take account of the two distinguishable properties of airborne targets on a nearcollision course. The findings from the numerical results indicate that the signalto ratio with the modified track scoring function is slightly improved compared to the previous one. Further work is being undertaken and it includes the implementation of the DPbased TBD method applied for airborne target detection.
Acknowledgements
This research was sponsored by the Korea Aerospace Research Institute (KARI) under the VisionBased Collision Avoidance Techniques for UAVs Project.
Barniv Y.
1985
“Dynamic programming solution for detecting dim moving targets”
IEEE Transactions on Aerospace and Electronic Systems
AES21
(Issue 1)
144 
156
DOI : 10.1109/TAES.1985.310548
Barniv Y.
,
Kella O.
1987
“Dynamic programming solution for detecting dim moving targets part II: analysis”
IEEE Transactions on Aerospace and Electronic Systems
AES23
(Issue 6)
776 
788
DOI : 10.1109/TAES.1987.310914
Arnold J.
,
Shaw S. W.
,
Pasternack H.
1993
“Efficient target tracking using dynamic programming”
IEEE Transactions on Aerospace and Electronic Systems
29
(Issue 1)
44 
56
DOI : 10.1109/7.249112
Tonissen S. M.
,
Evans R. J.
1996
“Performance of dynamic programming techniques for TrackBeforeDetect”
IEEE Transactions on Aerospace and Electronic Systems
32
(Issue 4)
1440 
1451
DOI : 10.1109/7.543865
Blackman S.
,
Popoli R.
1999
Design and analysis of modern tracking systems
Artech House Norwood, MA
Johnston L. A.
,
Krishnamurthy V.
2002
“Performance analysis of a dynamic programming track before detect algorithm”
IEEE Transactions on Aerospace and Electronic Systems
38
(Issue 1)
228 
242
DOI : 10.1109/7.993242
Nichtern O.
,
Rotman S.
2008
“Parameter Adjustment for a Dynamic Programming TrackbeforeDetectBased Target Detection Algorithm”
EURASIP Journal on Advances in Signal Processing
2008
1 
19
Gandhi T.
,
Yang M.
,
Kasturi R.
,
Camps O.
,
Coraor L.
,
McCandless J.
2003
“Detection of obstacles in the flight path of an aircraft”
IEEE Transactions on Aerospace and Electronic Systems
39
(Issue 1)
176 
191
DOI : 10.1109/TAES.2003.1188902
Carnie R.
,
Walker R.
,
Corke P.
2006
“Image processing algorithms for UAV Sense and Avoid”
Proceedings of the 2006 IEEE International Conference on Robotics and Automation
Orlando, FL