A novel track initialization algorithm based on random sample consensus in dense clutter

Abstract

Track initialization in dense clutter environments is an important topic and still a challenging task. Most traditional track initialization techniques firstly consider all possible associated measurement combinations and select the optimal one as an initialized track. Therefore, dense clutter brings great challenges to traditional algorithms. Random sample consensus algorithm, which is different from traditional algorithms, starts from minimum measurements. It samples randomly minimum measurements to establish hypotheses and verifies them through remaining measurements. However, the randomness of sampling influences algorithm performance, especially in dense clutter. A novel track initialization based on random sample consensus, named density-based random sample consensus algorithm, is proposed. It utilizes the fact that sequential measurements originating from the same target are contiguous while clutter is separated in space–time domain. The algorithm defines the density property of measurements to decrease the randomness in sampling procedure and increase the efficiency of track initialization. The experimental results show that the density-based random sample consensus is more superior to random sample consensus, the Hough transform algorithm, and logic-based algorithm.

Introduction

Multiple target tracking (MTT) is an active and hot research area and widely applied in military and civil field. ^{1 –5} Track initialization is the fundamental part of MTT. ^{6 –9} The long distance between targets and sensors, the inferior detectivity of sensors, and the inaccuracy of received measurement bring great challenges to track initialization, especially in dense clutter. ^{10 –12}

Track initialization is the procedure by which a new target entering in sensor coverage is acquired by tracking system. Track initialization algorithm makes a decision between the two alternative hypotheses: H₀—target is absent and H₁—target is present. The common track initialization algorithm is the logic-based approach, ^13,14 which produces hypotheses during n sequential scans and confirms these hypotheses through associating measurements to predict the position of a target. The track will be initialized if success association occurs in m of n scans. There are many improvements and extensions of the logic-based approach in the literature. ^15,16 Another conventional track initialization is the Hough transform method, ^{17 –20} which is a feature extraction technique used in image analysis, computer vision, and digital image processing. The purpose of the technique is to find imperfect instances of objects within a certain class of shapes by a voting procedure. This voting procedure is carried out in a parameter space, from which object candidates are obtained as local maxima in a so-called accumulator space that is explicitly constructed by the algorithm for computing. This method receives observations of some sequential scans and extracts straight lines as target tracks. Some researchers improve the Hough transform to detect not only straight lines but also curves, circles, and ellipses, and many modified methods are proposed ^21,22 to alleviate the computation and storage burden of standard Hough transform. Track-before-detect (TBD) is a class of methods that handles the detection and tracking problems. TBD is a paradigm which combines target detection and estimation by removing the detection algorithm and supplying sensor data directly to the tracker. ²³ In addition, multiple hypothesis tracking (MHT) ^{24 –26} is also a promising approach with the capability of detecting targets, which evaluates posterior probabilities of all feasible data association hypotheses.

In dense clutter environment, most observations received by sensors are clutter. Therefore, numerous incorrect associations become a heavy computational burden, and large amounts of false tracks degrade performance of tracking algorithms. While TBD and MHT techniques are limited by unacceptable computational complexity in such case. The batch methods like the Hough transform have a good capability of avoiding the effect of dense clutter. However, this class of methods demands that observations should be more accurate. Usually, it is difficult to guarantee that sensors receive observations without any noise. Nowadays, surveillance region becomes more and more complicated and brings difficulties to track initialization algorithms.

Recently, a scholar applied random sample consensus (RANSAC) ²⁷ in MTT and presented a multi-target tracking algorithm named recursive-RANSAC (R-RANSAC). ^{28 –31} RANSAC is a method developed as a new paradigm to regression analysis given a batch of data, which separates inliers and outliers by repeating sampling randomly to obtain a consensus in a given data set. RANSAC is a traditional algorithm in computer vision and image processing community. However, the RANSAC is applied in track initialization recently.

Most traditional track initialization techniques consider all possible association combinations of measurement and select the optimal association as a target trajectory to initialize via each initialization mechanism. On the contrary, the novel thought of RANSAC utilizes a minimum number of measurements to establish hypotheses. Then, the whole measurement set is used to confirm these hypotheses. If sampled measurements all belong to the same target, the hypothesis will be supported by other measurements originating from this target. The hypothesis, which is supported by measurements in every step, is initialized as a target trajectory. This novel idea considers a part of combinations instead of all combinations, which especially in dense clutter has a computational advantage than considering all association combinations. However, randomness of sample may become an important factor influencing performance of this algorithm. The novel algorithm proposed in this article improves standard algorithm to decrease the randomness in sampling procedure and increase the efficiency of track initialization.

Considering the homology of measurements originating from a target, the distribution of these measurements will show a continuity in space and time domain that can distinguish measurements of a true target from clutter. In this article, density-based RANSAC (DB-RANSAC) algorithm is proposed as a track initialization algorithm in dense clutter. DB-RANSAC defines a density property of each measurement determined by distribution of other measurements in its space–time neighborhood. Measurements within several sequential steps form a sliding window measurement set, and the density of each measurement is calculated. In this window set, measurements are gathered as some clusters, ³² and measurements in each cluster are sampled, respectively. The measurement with a high density has the priority to be sampled because a measurement with a high density is more likely to be originated by a true target. Sampled measurements establish hypothesis to be confirmed by other measurements in cluster. The sampling procedure is repeated until obtaining the optimal hypothesis or reaching the maximum number of iteration. The proposed algorithm uses the homology of targets measurements as a prior information to direct sampling, which cuts down computational burden caused by sampling randomly and improves efficiency distinctly.

This article is organized as follows. The second section describes the problem and gives the state model and the measurement model. Basic assumptions in the proposed algorithm are present. The third section proposes DB-RANSAC algorithm and presents main steps and relevant parameters in detail. The fourth section shows simulations of the proposed algorithm in complicated environments comparing standard RANSAC and other traditional algorithms and experiments in real situations. The fifth section concludes this article and the prospect of DB-RANSAC is brought in the end.

Problem description

In this article, we consider the two-dimensional track initialization problem, but the proposed algorithm is practical to other track initialization problems as well. Define a subset of measurement space in surveillance region. Define x_i as the four-dimensional state of the i target consisting of the position and velocity components in Cartesian coordinates. ³³ The kinematic model is as follows.

The state model of the i th target at time k is given by

$x_i\left(k\right)=F{x}_i\left(k-1\right)+w_i\left(k\right)$

1

where $w_i\left(k\right)$ is wide-sense stationary, zero-mean Gaussian process noise with covariance matrix $Q\left(k\right)$ at time k. We assume that the target is moving with constant velocity (CV) and F is the state transition matrix given by

$F=\left[\begin{array}{llll}1\hfill & T\hfill & 0\hfill & 0\hfill \\ 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill & T\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right]$

where T is the sample period.

Define $y_i\left(k\right)$ as measurement of the i th target at time k. The measurement model is given by

$y_i\left(k\right)=H{x}_i\left(k\right)+v_i\left(k\right)$

2

where $v_i\left(k\right)$ is wide-sense stationary, zero-mean Gaussian measure noise with covariance $R\left(k\right)$ at time k, and H is the measurement matrix given by

$H=\left[\begin{array}{llll}1\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill & 0\hfill \end{array}\right]$

Let $P_d\in \left(0,1\right]$ be the probability of detection and define a sensor scan ${\Phi }_k$ as the set of ${\psi }_k$ observations received at time k. The observation $y_j\left(k\right),j=1,2,\dots ,{\psi }_k$ can be a measurement of a true target or clutter. We assume that the prior information of the clutter distribution is known and define that the clutter is received according to a Poisson distribution with parameter λ, where λ is the expected amount of clutter received per scan.

To establish a batch method, we form a sliding window set ${\Psi }_k$ with length L at time k. This window set consists of observations received from time $k_N=k-L+1$ to k given by

${\Psi }_k={\sum }_{i=k_N}^k{\Phi }_i,{\Phi }_i={\sum }_{j=1}^{{\psi }_i}{y}_j\left(i\right)$

3

We assume one-to-one correspondence between measurement and target. The proposed algorithm estimates the initial state using sampled measurements, which demands dynamic system is observable. The following basic assumptions are used in this article.

Each target produces at most one measurement per scan.

A measurement cannot be associated with more than one target.

Measurement originating from different targets is independent.

All targets submit to the same kinematic model $\left(F,H\right)$ and the kinematic model must be observable.

Density-based RANSAC

The innovation of the proposed algorithm is that the distribution of measurements in space and time is utilized as a prior information, which directs sampling. It avoids meaningless random samples and improves the efficiency of algorithm to find the optimal estimate. First, distribution information of measurements is extracted. Then, measurements are sampled according to distribution information and measurements sampled establish a hypothesis, which is confirmed by remaining measurements. Regard this hypothesis as the optimal hypothesis if the number of measurements supporting this hypothesis meets the specific condition. Otherwise, repeat sampling until obtaining the optimal hypothesis or reaching the maximum number of repeat times. Finally, the optimal hypothesis is initialized as a target trajectory.

The density of measurement

The process of extracting distribution information of measurements refers to density-based spatial clustering of applications with noise. ³² We define the space–time neighbor of measurement p as $N\left(p\right)$ and the density property of p as $|N\left(p\right)|$ . The density property is determined by the number of other measurements in $N\left(p\right)$ , which reveals distribution of other measurements in $N\left(p\right)$ . We define ${\epsilon }_{\text{d}}$ and ${\epsilon }_{\text{t}}$ as the threshold of distance and the threshold of time difference, respectively. If distance and time difference of two measurements are both less than or equal to ${\epsilon }_{\text{d}}$ and ${\epsilon }_{\text{t}}$ simultaneously, each measurement is in the others neighborhood mutually. When $|N\left(p\right)|⩾\text{min}Pts$ , the density of p is greater than or equal to a threshold $\text{min}Pts$ , p is qualified into one cluster with measurements in its space–time neighbor, where $\text{min}Pts$ is the discriminant threshold to evaluate whether an underlying target appears in $N\left(p\right)$ or not. Adjacent measurements in space and time are likely to be classified into the same cluster to be sampled later and measurements with no measurement in its neighborhood are considered as clutter and removed. The process is summarized in Algorithm 1.

Algorithm 1.

Process of calculating density of measurements and clustering at time k.

Require: The measurement window set ${\Psi }_k$ ;

Ensure: measurement clusters ${\varphi }_k^i$ , density of measurements $|N|$ ;

1: cluster number $i=0$

2: repeat

3:  select an unvisited measurement p from ${\Psi }_k$ ; calculate $|N\left(p\right)|$ , select another unvisited measurement q from ${\Psi }_k$ and define $dis(p,q)$ , $timediff(p,q)$ as distance and time difference between p and q. $N\left(p\right)=\left\{q\in {\Psi }_k|and(dis\left(p,q\right)⩽{\epsilon }_d,timediff\left(p,q\right)⩽{\epsilon }_t)\right\}$

4:  if $|N\left(p\right)|⩾\text{min}Pts$ then

5:    $i=i+1$ , form a new cluster

6:  else

7:   define p as clutter

8:  end if

9:  repeat

10:   select an unvisited measurement l from $N\left(p\right)$ , and process in the same way from step 3 to step 11, expect that l is classified into ${\varphi }_i$ if $|N\left(l\right)|⩾\text{min}Pts$ instead of forming a new cluster.

11:  until no unvisited measurement in $N\left(p\right)$

12: until no unvisited measurement in ${\Psi }_k$

13: return ${\varphi }_k^j,j=1,\cdots ,i$ , and $N\left(p\right),p\in {\Psi }_k$

The value of ${\epsilon }_{\text{d}}$ , ${\epsilon }_{\text{t}}$ ,and $\text{min}Pts$ are dependent on circumstances. Thresholds of distance and time difference determine the range of measurement’s neighbor, which should be adjusted as clutter density changing and $\text{min}Pts$ is related to length L of sliding window set. Generally, let ${\epsilon }_{\text{t}}$ be one or two sample periods and ${\epsilon }_{\text{d}}\hspace{0.17em}\text{=}\hspace{0.17em}{\epsilon }_{\text{t}}\hspace{0.17em}\times \hspace{0.17em}{V}_{\text{max}}$ , where V _max is the maximum velocity of target and $\text{min}Pts\hspace{0.17em}\text{=}\hspace{0.17em}\text{2}\hspace{0.17em}\times \hspace{0.17em}{\epsilon }_t\hspace{0.17em}+\hspace{0.17em}1$ .

Sample in measurement cluster

The next step is sampling in each measurement cluster according to the density of each measurement. A minimum number b of measurements are selected to establish the hypothesis, which is the initial state estimated by selected measurements. The minimum number b is the observability index of target dynamic system and it submits to $\text{rank}\left(O_b\right)\hspace{0.17em}=\hspace{0.17em}\text{rank}\left(O_{b\hspace{0.17em}+\hspace{0.17em}1}\right)$

$O_b={\left[\begin{array}{llll}H\hfill & HF\hfill & \dots \hfill & H{F}^{b\hspace{0.17em}-\hspace{0.17em}1}\hfill \end{array}\right]}^T$

4

In RANSAC, there are all $C_{{\Psi }_k}^b$ combinations when b measurements are selected from ${\Psi }_k$ measurements but we are only interested in some combinations consisting of all b measurements originating from the same target. If b measurements are not homologous, this initial state estimation won’t be supported by most of measurements. Resample b measurements and estimate the initial state until the optimal estimation is obtained or the terminate criterion is satisfied. The maximum number of iterations is M. Let m be the number of iteration before that optimal estimation is obtained and w be the possibility of selecting a right measurement among a batch of measurements. The expectation of m is

$\begin{array}{l}E\left(m\right)=w^b+2\times \left(1-w^b\right)\times w^b+3\times \left(1-w^b\right)\times w^b\\ \hspace{1em}\hspace{1em}+\dots +i\times \left(1-w^b\right)\times w^b+\dots \end{array}$

5

In the proposed algorithm, measurements are divided into several measurement clusters, and measurements with larger density are prior to be sampled. Measurement’s density determines the probability to be sampled for one measurement. Define the probability that measurement p is sampled as $P_s\left(p\right)$

$P_s\left(p\right)=\frac{N\left(p\right)}{\sum _{q\in \Psi }N\left(q\right)}$

6

In Figure 1, one target moves with a CV and clutter appears randomly. Therefore, measurements of this target are contiguous while distribution of clutter is uniform. After clustering based on density, clutter is filtered partly. In a cluster containing a target, target’s measurements generally have a higher density and a higher $P_s$ than clutter. Thus, introducing density property makes sampling more efficient. Considering the robustness of algorithm and improving the tolerance of sampling failure, let expectation of M be one or two times $E\left(m\right)$

Figure 1.

Set a measurement set within several steps. Circles represent target’s measurements and stars represent clutter. Larger size in picture means a higher density.

The initial state estimation

Consider single target initialization problem and the probability of detection $P_{\text{d}}=1$ , b measurements are used to estimate the initial state given by

$\left[\begin{array}{c}y\left(k_N\right)\hspace{0.17em}\\ y\left(k_N+1\right)\\ ⋮\\ y\left(k\right)\end{array}\right]\hspace{0.17em}=\hspace{0.17em}\left[\begin{array}{c}Hx\left(k_N\right)\\ Hx\left(k_N+1\right)\\ ⋮\\ Hx\left(k\right)\end{array}\right]\hspace{0.17em}+\hspace{0.17em}\left[\begin{array}{c}v\left(k_N\right)\\ v\left(k_N+1\right)\\ ⋮\\ v\left(k\right)\end{array}\right]$

7

where $Y_k\hspace{0.17em}=\hspace{0.17em}{\left[y\left(k_N\right),\dots ,y\left(k\right)\right]}^T$ , $W_k={\left[w\left(k_N\right),\dots ,w\left(k\right)\right]}^T$ , and $V_k\hspace{0.17em}=\hspace{0.17em}{\left[v\left(k_N\right),\dots ,v\left(k\right)\right]}^T$ .

$O={\left[\begin{array}{cccc}H& HF& \dots & H{F}^{N-1}\end{array}\right]}^T$

8

$G=\left[\begin{array}{cccc}0& 0& 0& 0\\ 0& H& 0& 0\\ ⋮& ⋮& ⋮& ⋮\\ 0& H{F}^{N-2}& H{F}^{N-3}& H\end{array}\right]$

9

where dimension of O is $mN\times N$ , and it describes the expected measurement evolving from the initial step to current step. G is $mN\times nN$ and propagates the process noise. We can get

$Y_k\hspace{0.17em}=\hspace{0.17em}Ox\left(k_N\right)\hspace{0.17em}+\hspace{0.17em}{\xi }_k$

10

where ${\xi }_k=G{W}_k+V_k$ is the combination of the propagated process noise and the measure noise. The noise term ξ is also zero-mean Gaussian because w and v are independent identically distributed. Its covariance is Ξ given by

$\Xi =GQ{G}^T+R$

11

when $w=v=0$ , $Y_k=Ox\left(k_N\right)$ . Use least square to estimate the initial state given by

$x\left(k_N\right)\hspace{0.17em}=\hspace{0.17em}{\left(O^{T}O\right)}^{-1}{O}^T{Y}_k$

12

Considering the process noise and the measurement noise, the maximum likelihood estimation of $x\left(k_N\right)$ and its covariance are given by

$\widehat{x}\left(k_N\right)\hspace{0.17em}=\hspace{0.17em}{\left(O^T\Xi O\right)}^{-1}{O}^T{\Xi }^{-1}{Y}_k$

13

$P\left(k_N\right)\hspace{0.17em}=\hspace{0.17em}{\left(O^T{\Xi }^{-1}O\right)}^{-1}$

14

Considering tracking multi-target in dense clutter and $P_d\in \left(0,1\right)$ , there is measurements of multi-target and clutter in the window set ${\Psi }_k$ . Define an $m{\Psi }_k\hspace{0.17em}\times \hspace{0.17em}nN$ matrix ${\Phi }_k$ to associate selected measurements to all measurements in the window set. Define $1_{{\psi }_k}$ as a column vector of ${\psi }_k$ ones and $I_m$ be an m × m identity matrix. Define ⊗ as Kronecker product. ${\Phi }_k$ is given by

${\Phi }_k=\left[\begin{array}{cccc}{1}_{{\psi }_{k_N}}\otimes I_m& 0& \cdots & 0\\ 0& 1_{{\psi }_{k_N+1}}\otimes I_m& \ddots & ⋮\\ ⋮& \ddots & \ddots & 0\\ 0& \cdots & 0& 1_{{\psi }_k}\otimes I_m\end{array}\right]$

15

The equation (10) is rewritten by

$Y_k={\Phi }_{k}Ox\left(k_N\right)+{\Phi }_k{\xi }_k$

16

We set a binary indicator matrix B(d) to record index of selected measurements, where $d={\left[d_1,\hspace{0.17em}\dots \hspace{0.17em},d_b\right]}^T$ is the vector of sample index

$B\left(d\right)\hspace{0.17em}=\hspace{0.17em}\left[\begin{array}{ccc}{0}_{m\hspace{0.17em}\times \hspace{0.17em}m\left(d_1\hspace{0.17em}-\hspace{0.17em}1\right)}& I_m& 0_{m\hspace{0.17em}\times \hspace{0.17em}m\left({\Psi }_k-d_1\right)}\\ ⋮& ⋮& ⋮\\ 0_{m\hspace{0.17em}\times \hspace{0.17em}m\left(d_d\hspace{0.17em}-\hspace{0.17em}1\right)}& I_m& 0_{m\hspace{0.17em}\times \hspace{0.17em}m\left({\Psi }_k-d_d\right)}\end{array}\right]$

17

Let a sample index be q. Hence, ${\overline{Y}}_k=B\left(q\right)Y_k$ , $\overline{O}=B\left(q\right){\Phi }_{k}O$ , and ${\overline{\xi }}_k=B\left(q\right){\Phi }_k{\xi }_k$ . The equation (16) can be rewritten as

${\overline{Y}}_k=\overline{O}x\left(k_N\right)+{\overline{\xi }}_k$

18

where the noise term ${\overline{\xi }}_k$ has covariance $\overline{\Xi }$ given by

$\begin{array}{c}\overline{\Xi }=E\left({\overline{\xi }}_k{{\overline{\xi }}_k}^T\right)=B\left(q\right){{\Phi }_k\Xi {\Phi }_k}^{T}B{\left(q\right)}^T\end{array}$

19

The initial state and covariance are estimated by maximum likelihood estimation as

$\widehat{x}\left(k_N\right)={\left({\overline{O}}^T\overline{\Xi }\overline{O}\right)}^{-1}{\overline{O}}^T{\overline{\Xi }}^{-1}{\overline{Y}}_k$

20

The support of estimation

After estimating the initial state and covariance, the other measurements in cluster are utilized to confirm this estimation. We define the inlier as the measurement whose residual is less than a threshold ${\tau }_R$ . Define the support degree of this estimation $\chi \left(k\right)$ as the number of inliers

$\chi \left(k\right)\hspace{0.17em}=\hspace{0.17em}\left\{\begin{array}{l}\kappa \in \left\{1,\dots ,{\Psi }_k\right\}\hfill \\ {\Vert B\left(\kappa \right)Y_k-B\left(\kappa \right){\Phi }_{k}O\widehat{x}\left(k_N\right)\Vert }_{\infty }\hspace{0.17em}<\hspace{0.17em}{\tau }_R\hfill \end{array}\right\}$

21

Assume $\alpha \in \left(0,1\right)$ . The estimation is regarded as an optimal hypothesis, if $\chi \left(k\right)\ge \alpha \times L$ . Assume $\beta \in \left(\alpha \mathrm{,1}\right)$ and the estimation is good enough to stop iteration ahead of the maximum number of iterations, if $\chi \left(k\right)\hspace{0.17em}\ge \hspace{0.17em}\beta \hspace{0.17em}\times \hspace{0.17em}L$ . The assignment of ${\tau }_R$ , α, and β depends on specific tracking situations. Increasing α and β will reduce false trace produced by clutter and increase missed detection of some targets probably at the same time. Then, optimal estimation is initialized to form a trace.

The proposed algorithm can be summarized in Algorithm 2.

Algorithm 2.

DB-RANSAC track initialization algorithm at time k.

Require: The measurement window set ${\Psi }_k$ ;

Ensure: initialized tracks;

1: cluster measurements and calculate the density of measurement in ${\Psi }_k$ using Algorithm 1

2: for each measurement cluster i do

3: repeat

4:  sample b measurements according to $|N|$ of each measurement in i measurement cluster

5:  estimate $\widehat{x}(k_N)$ and $P(k_N)$ using b sampled measurements

6:  calculate the support of this estimation using remain measurement in cluster

7:  if the support of estimation > threshold $\beta *L$     then

8:   confirm this estimation $\widehat{x}(k_N)$ and $P(k_N)$ and      return it as a track

9:   break

10:  else

11:   if the support of estimation > threshold $\alpha *L$      then

12:    set this estimation as a candidate track

13:   end if

14:  end if

15: until the maximum number of iteration M is reached

16: return the estimation with the highest support as a track of target among candidate tracks

17: end for

Experiment results

In this section, some simulations and real data experiments are conducted to verify the performance of the proposed algorithm. This section focuses on comparison with standard algorithm referring to R-RANSAC ²⁸ and other traditional track initialization algorithms. The proposed algorithm aims at track initialization in practical environments, which brings a great challenge to many theoretical methods.

First, simulation experiment is comparing the proposed algorithm with standard algorithm for the reason that the proposed algorithm is developed based on RANSAC. The simulation background is a two-dimensional surveillance region, $x\in \left(0,\hspace{0.17em}500\right),\hspace{0.17em}y\hspace{0.17em}\in \hspace{0.17em}\left(0,\hspace{0.17em}500\right)$ . Experiment sets a single target appearing with random location and velocity in surveillance region. The target persists throughout the five-step simulation. Relative parameter setup shows in Table 1.

Table 1.

Parameters in simulation scenario.

X	[0, 500] (m)
Y	[0, 500] (m)
The total step of simulation	5
The number of targets	1
The density of clutter	5 × 10−5
The probability of detection	1
The minimum velocity of target	0
The maximum velocity of target	50 (m/s)
The covariance of process noise	5
The covariance of measure noise	10

We assume that the motion model of target is CV motion. The setup of DB-RANSAC and standard algorithm is presented in Table 2. Simulation result is presented in Figure 2. The simulation result illustrates that DB-RANSAC successfully samples measurements originating from the target and produces a trajectory, while standard RANSAC produces a trajectory and misses a forth step measurement. In dense clutter, standard RANSAC with random sampling mechanism tends to initialize a false trace, and DB-RANSAC firstly excludes measurements like the fifth measurement of standard RANSAC trace in Figure 2 through density clustering. So the robustness of algorithm is improved.

Table 2.

Parameters in DB-RANSAC and RANSAC.

Parameters	DB-RANSAC	RANSAC
The window length, L	5	5
The sample number, b	2	2
The threshold, ${\epsilon }_{\text{d}}$	100	—
The threshold, ${\epsilon }_{\text{t}}$	2	—
The threshold, ${\tau }_R$	20	20
The threshold, α	0.7	0.7
The threshold, β	0.9	0.9

RANSAC: random sample consensus; DB-RANSAC: density-based random sample consensus.

Figure 2.

The simulation result of DB-RANSAC and standard RANSAC algorithm throughout five steps. RANSAC: random sample consensus; DB-RANSAC: density-based random sample consensus.

Repeated number of sampling is a major factor influencing RANSAC performance. Less repeated sampling number to obtain correct measurement combination means fast target initialization, which is we are interested in. Fifty Monte Carlo simulations are processed in different clutter density, where clutter density increases from 1 × 10⁻⁵ to 1.1 × 10⁻⁴. The average of sampling number in different clutters is shown in Figure 3. The comparison result shows the limitation of RANSAC definitely. The performance of original RANSAC ²⁷ is influenced seriously by the number of outliers, which is the clutter density in track initialization problem. The figure shows that the performance of DB-RANSAC is remarkable compared to standard algorithm when the clutter density is less than 6 × 10⁻⁵. However, the sampling number of DB-RANSAC rises as the clutter density increasing continuously. The explosive growth of sampling number in standard RANSAC is not acceptable, while sampling number of DB-RANSAC is growing stably.

Figure 3.

The comparison repeat times of DB-RANSAC and standard RANSAC to obtain correct measurement combination as the clutter density increasing. DB-RANSAC: density-based random sample consensus; RANSAC: random sample consensus.

Logic-based target initialization and Hough transform are most popular in practical application. The next simulation is comparing the proposed algorithm to those two traditional algorithms. For the sake of fairness, we choose the modified logic-based and the modified Hough transform adding constraint of maximum and minimum velocities in simulation. Some parameters in this simulation are changed. This simulation considers 10 targets appearing in surveillance region. Therefore, surveillance region is extended, $x\in \left(0,1000\right),y\in \left(0,\hspace{0.17em}1000\right)$ , and simulation persists throughout 10 s where targets appear at random step. There are some important metrics to measure performance of track initialization algorithms.

The false alarm rate, P _f: The proportion of false traces in total initialized traces. A high false alarm rate means too many false traces, which is computational burden and an obstacle to detect and track targets we are interested in.

The missed detection rate, P _m: The proportion of missed detections of true targets in total true targets. If we want to detect and track an important target, we need an algorithm with a very low missed detection rate.

Operation time, T _o: The operation time to process measurements reflecting the efficiency of an algorithm.

The modified logic-based track initialization algorithm associates measurements by velocity information, which causes numerous false traces and a high P _f, especially in dense clutter. We set 50 Monte Carlo simulations in different densities of clutter and analyze these three metrics. The density of clutter λ increases from 1 × 10⁻⁵ to 1.1 × 10⁻⁴, and one simulation result is shown in Figure 4. Result shows that logic-based algorithm generates lots of false traces caused by dense clutter and plenty of false traces make a great trouble in detecting true targets that we are interested in. The average of P _f in 50 Monte Carlo simulations is presented in Figure 5. P _m and T _o are shown in Figure 6. As the comparison results convey, the dense clutter makes the logic-based algorithm inapplicable, while DB-RANSAC keeps a reasonable P _f when clutter density is increasing. DB-RANSAC maintains a good performance of P _f and P _m with an acceptable computational growth.

Figure 4.

The simulation result of DB-RANSAC and logic-based algorithm in the clutter density λ = 5 × 10⁻⁵. DB-RANSAC: density-based random sample consensus.

Figure 5.

The false alarm rate P _f of DB-RANSAC and logic-based algorithm in different densities of clutter. DB-RANSAC: density-based random sample consensus.

Figure 6.

The missed detection rate P _m and operation time O _t of DB-RANSAC and logic-based algorithm in different densities of clutter. DB-RANSAC: density-based random sample consensus.

The Hough transform algorithm is capable to detect and initialize underlying targets in dense clutter. Therefore, the Hough transform algorithm is not influenced by dense clutter as seriously as logic-based algorithm, which is attributed to its batch process and mechanism. However, Hough transform method has difficulty to deal with the situation that straight lines or some shapes are not standard and accompany noise. Noise is another important factor in target initialization, which is unavoidable through sensors observing. In terms of noise, we set simulations to demonstrate the performance of DB-RANSAC comparing with Hough transform algorithm in different noise environments. The covariance of measurement noise in simulations changes from 0 to 15, density of clutter λ is 5 × 10⁻⁵, and other parameters remain. Fifty Monte Carlo simulations are processed and one of the simulation results is presented in Figure 7. The missed detection rate P _m in different measurement noise is presented in Figure 8, and the false alarm rate P _f and operation time O _t are presented in Figure 9. Conclusion of simulations is that Hough transform algorithm is not applicable for the situation with serious noise and misses detections of targets. DB-RANSAC performs well with noise interference and detects the majority of targets successfully.

Figure 7.

The simulation result of DB-RANSAC and Hough transform algorithm with covariance of measurement noise $R(k)$ = 10. DB-RANSAC: density-based random sample consensus.

Figure 8.

The missed detection rate P _m of DB-RANSAC and Hough transform algorithm with different covariances of measurement noise. DB-RANSAC: density-based random sample consensus.

Figure 9.

The false alarm rate P _f and operation time O _t of DB-RANSAC and Hough transform algorithm with different covariances of measurement noise. DB-RANSAC: density-based random sample consensus.

The simulation results show that the Hough transform performs well in false alarm rate while it has an unacceptable missed detection rate. On the contrary, the logic-based algorithm has a low missed detection rate but initialized traces consist of some false traces. The proposed algorithm keeps the false alarm rate low meanwhile the probability of missed detection is closed to zero. The simulation results show that the Hough transform algorithm and the logic-based algorithm are sensitive to noise and clutter, respectively. DB-RANSAC has a great tolerance of noise and clutter, which is valuable in practical applications. Then, the next experiment is applying three algorithms on real situations.

Real data is obtained by a radar sensor. A given target appears in a 6 × 2 km² area covered by the sensor. There is a road in this area and the given target is a car driving along this road with a CV. For the reason that there is only one target that is labeled, the experiment focuses on comparing whether the given target is initialized by these algorithms and defines a target initialized rate T _i to indicate it. Set four scenarios in Figure 10 and every scenario includes 10 sequential radar scans and scanning period is 8 s. DB-RANSAC, Hough transform, and logic-based algorithm are used in these four scenarios with the same parameters in previous simulations and the threshold ${\epsilon }_d$ is changed to 200.

Figure 10.

Four different real scenarios and pentagons mark the given target and dots mark other measurements.

The result shown in Figure 11 illustrates that DB-RANSAC algorithm performs best in three algorithms. Hough transform algorithm misses the given target many times, and logic-based algorithm initializes many unknown traces. In addition to the given target, there are some traces that are originated by clutter or other targets like unknown cars and pedestrian on the road. To compare this three algorithm, generally, 30 Monte Carlo experiments are used to test three algorithms and comparison of results is shown in Figure 12. The T _i averages of DB-RANSAC, Hough transform, and logic-based algorithm are 88.6%, 23.3%, and 86.6%, respectively, and the operation average times are 0.09, 0.03, and 0.04 s, which confirms simulation results that Hough transform algorithm has a high P _m and misses target easily and logic-based has a high P _f and produces many false traces. In this real data test, experimental result shows that DB-RANSAC has stronger robustness than traditional algorithm like Hough transform and logic-based algorithm. Inaccuracy of received measurement brings Hough transform difficulties and causes missed detection of the given target. Dense clutter causes many traces we are not interested in, which is produced by logic-based algorithm. The summary of real data experiments is that DB-RANSAC has a good track initialization performance than traditional algorithms in real situations.

Figure 11.

Results of three algorithms in four different real scenarios.

Figure 12.

The target tracked rate and operation time comparison of three algorithms performance in four different real scenarios.

Conclusion

In this article, a track initialization algorithm based on RANSAC and DB-RANSAC is proposed to initialize underlying targets in complicated environment. RANSAC is a traditional algorithm in computer vision and image processing community. But it is applied on track initialization recently. DB-RANSAC uses the distribution of measurement in space and time as a prior information to direct sampling, which avoids random sampling and improves the efficiency of initialization. Simulation results show that the proposed algorithm performs well in dense clutter compared to the Hough transform algorithm and the logic-based algorithm. The superiority of DB-RANSAC is that it performs well in complicated environments, which brings great challenges to traditional algorithms. The real data experiments confirm it. The prospect of DB-RANSAC is that applications of the proposed algorithm in multiple sensors and multiple platforms are expected in future research.