# A Novel Track Initiation Method Based on Prior Motion Information and Hough Transform

Jun Liu, Yu Liu, Wei Xiong

► To cite this version:

Jun Liu, Yu Liu, Wei Xiong. A Novel Track Initiation Method Based on Prior Motion Information and Hough Transform. 9th International Conference on Intelligent Information Processing (IIP), Nov 2016, Melbourne, VIC, Australia. pp.72-77, 10.1007/978-3-319-48390-0_8. http-01614982

HAL Id: hal-01614982

https://inria.hal.science/hal-01614982

Submitted on 11 Oct 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# A Novel Track Initiation Method Based on Prior Motion Information and Hough Transform

Jun Liu¹, Yu Liu¹,², Wei Xiong¹

1 Research Institute of Information Fusion, Naval Aeronautical and Astronautical University, Yantai 264001, China
2 School of Electronic and Information Engineering, Beihang University, Beijing 100191, China
{18615042187@163.com, liuyu77360132@126.com, xiongwei@csif.org.cn}

**Abstract.** This paper deals with the problem of track initiation in dense clutters. A novel Hough transform method based on prior motion information is proposed. Firstly, with time sequence of the measurements and targets' kinematic information considered, the single scan data accumulation effect is avoided, and the initiated tracks are more reliable. Then, measurements in observation space only vote to part of the lines that pass through them, which can effectively reduce the computational cost, and improve the initiation speed. Simulation results indicate that the proposed method is superior to the traditional algorithms in terms of detection probability, computational cost and robustness.

**Keywords:** track initiation, prior information, Hough transform, target tracking

## 1 Introduction

Track initiation is the primary problem of multi-target tracking, especially for establishing the records for new targets and terminating the records of inexistent targets [1,2]. Because of the long distance between the radar and targets, it is hard for the targets to be accurately measured by sensors, and there is no statistical rule to judge whether the measure is from target or clutter, track initiation itself is a very difficult issue. It is hoped that target tracks are initiated as early as possible, because the operators can get an early situation picture for the surveillance area. On the other hand, it is hoped that false track initiation rate is as low as possible. False tracks cause waste of radar resources, because radar beams for track maintenance are assigned to the area where there is no target [3]. In addition, to detect modern dim targets, radar needs to lower the threshold. Therefore, the false alarm rate will be very high, and how to deal with the track initiation of targets moving in such circumstance has been a challenging task now.

## 2 Review of current techniques

During the past several decades, a lot of research has been contributed to track initiation, and there are two main series, one is sequential data processing technique, such as the heuristic rule method [4], logic-based method[1]; another is batch data
processing technique, such as multiple hypothesis tracking method [5], integrated
probabilistic data association algorithm [6], the Hough transform technique [7], and the
modified Hough transform technique [8]. The former method has low computational
cost, and is easy to apply. However, it is just suitable for initiation in sparse clutter.
Though the latter method has a better performance than the former method, and is
effective in reducing false alarm probability, it has much more computational cost than
the former method, in addition, it is difficult to apply.

As is known, Hough Transform has low sensitivity to local fault and good ability in suppressing noise and clutters. Because of this advantage, it has been widely applied to track initiation in dense clutter environment. As a batch data processing method, Hough transform has the disadvantage of huge computation and memory. A lot of research has been done to reduce computation and memory by researchers, and many advanced methods have been put forward, such as modified Hough transform, random Hough transform, etc. A novel method for fast track initiation in dense clutters by divide and Hough transform method is proposed in this paper and this method is very effective in decreasing computation and memory. The measurement's time sequence information and targets' kinematics information also have been effectively utilized.

3 Our approach

For Hough Transform, any point in data space is corresponding to the only one curve in
parameter space, and points of the same line in data space are corresponding to
different curves in parameter space, and those curves intersect at one point in
parameters. If Aᵢ, Aᵢ+₁, Aᵢ+₂ denotes as an echo in the ith, (i+1)th, (i+2)th scan
respectively, then Aᵢ and Aᵢ+₁ are connected to form a line AᵢAᵢ+₁, which is
corresponding to a point C₁ in parameter space with Hough Transform. In the same way,
Aᵢ+₁ and Aᵢ+₂ are connected to form a line Aᵢ+₁Aᵢ+₂, which is corresponding to a point
C₂ in parameter space with Hough Transform. If Aᵢ, Aᵢ+₁, Aᵢ+₂ are collinear, C₁ and
C₂ must coincide as shown in Fig. 1. If Aᵢ, Aᵢ+₁, Aᵢ+₂ are approximately collinear, then
C₁ and C₂ will be very close, conversely, they will be far apart. According to this
principle, a track can be detected through the intensive degree of point distribution in
parameter space.

<figure><img src="image_2.png" /><figcaption>Fig.1. Three collinear points and the corresponding curves</figcaption></figure>

In this new method, any two observed data from different cycles is connected, which
avoids loss of echo data. If only observed data from two adjacent cycles can be
connected, when the target echo appears flashing, for example, a target echo is lost every other cycle, then echo data from two adjacent cycles can not be connected, which will cause loss of target information. However, not all observed data from two different cycles are from the same target, only when distance between the two points satisfies some condition, they can be from the same target. If $z_1(x_1, y_1)$, $z_2(x_2, y_2)$ is the measurement in time $t_1, t_2$ respectively, then distance between the two points is

$$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} \qquad (1)$$

where d is the distance. Then the average speed is

$$v = \frac{d}{|t_2 - t_1|} \qquad (2)$$

where v denotes as the average speed. If v satisfies

$$v_{\min} \le v \le v_{\max} \qquad (3)$$

$z_1$ and $z_2$ can be from the same target. In formula (3), $v_{\min}$ and $v_{\max}$ denote as the minimum and maximum speed of the target respectively. Through this process, the number of combinations is greatly reduced. If $z_1$ and $z_2$ satisfy the above condition, then the corresponding curve through Hough Transform in parameter space is

$$\begin{cases} \rho = x_1 \cos(\theta) + y_1 \sin(\theta), \\ \rho = x_2 \cos(\theta) + y_2 \sin(\theta). \end{cases} \qquad (4)$$

By solving equations (4), the intersection of the line consisting of $z_1$ and $z_2$ in parameter space is

$$\tan \theta = - \frac{x_2 - x_1}{y_2 - y_1} \qquad (5)$$

Let $a = -\frac{x_2 - x_1}{y_2 - y_1}$, because $\theta \in [0, \pi]$, then

$$\theta = \begin{cases} -\arctan(a) & a > 0, \\ -\arctan(a) + \pi & a \le 0. \end{cases} \qquad (6)$$

Bring formula (6) back into equations (4), $\rho$ is obtained.

$$\rho = \frac{|x_2 y_1 - x_1 y_2|}{d} \qquad (7)$$

During the initiation period, targets are far away from sensors, so they are often thought to move in a straight line. According to the above discussion, any two measurements from a target must be mapped to the same $(\rho, \theta)$ in the parameter space. However, because of target's motion and measurement error, it is impossible that all $(\rho, \theta)$ is the same, but they will be concentrated in a small area. These small areas can be detected through the density of point distribution in the parameter space, and then the corresponding tracks are detected.

Suppose there are N intersections in parameter space, to detect target trajectory from observed data, the $\rho-\theta$ parameter space is equidistantly quantized into $N_{\rho} \times N_{\theta}$ cells with distance interval $\Delta\rho$ and angle interval $\Delta\theta$. Define parameter space array
according to $\Delta\rho$ and $\Delta\theta$, if an intersection votes to accumulated cell $A(k,l)$, $A(k,l) = A(k,l)+1$. Search for the peak values in accumulated cells, and $N_\xi$ denotes as the threshold. If $A(k,l)$ satisfies

$$A(k,l) > N_{\xi} \qquad (8)$$

output the corresponding observed data as the initial tracks of targets.

## 4 Simulation and results

In this section, suppose the surveillance area is 100000m long and 100000m wide. And assume 5 targets move in a straight line with constant velocity, and these targets are tracked with 2D radar. The initial position of 5 targets are (55000m, 55000m), (45000m, 45000m), (35000m, 35000m), (45000m, 25000m), (55000m, 15000m), and 5 targets move in the same speed, $v_x=500m/s$, $v_y=0m/s$. And assume radar's PRI is T=5s, azimuth observation square root error is $\sigma_\theta = 0.3^\circ$, while distance observation square error is $\sigma_r = 40$ m. For a fair comparison, we make $N' = 100$ independent Monte Carlo runs, and the number of false measurements in the surveillance area satisfies the passion distribution with density $\lambda$.

Define the false track initiation probability as

$$P_F \triangleq \sum_{i=1}^{N'} f_i / \sum_{i=1}^{N'} n_i \qquad (9)$$

where $N'$ is the number of Monte Carlo simulation, $f_i$ is number of false tracks in $i^{th}$ Monte Carlo simulation, and $n_i$ is number of all tracks in $i^{th}$ Monte Carlo simulation. In the same way, the detection probability of target t is given as

$$P_D = \frac{\sum_{i=1}^{N_i} \sum_{i=1}^{N'} l_{it}}{N_t \times N'} \qquad (10)$$

where $l_{it}$ indicates whether track of target t is correctly initiated in $i^{th}$ Monte Carlo simulation, and $l_{it}$ is defined as

$$l_{it} = \begin{cases} 1 & \text{if target } t \text{ is correctly initiated,} \\ 0 & \text{else.} \end{cases} \qquad (11)$$

As is seen from Table 1, with the increase of clutters, when $\lambda = 100$, there are many false tracks in the former 4 algorithms. Especially in HT method, a great number of false tracks make it impossible to detect the exact tracks for targets. All these false tracks will cause a lot of trouble for subsequent target tracking and waste of radar resources. However, the method proposed in this paper is very robust to clutter interference, which can correctly initiate targets' tracks and suppress false tracks generated by clutters.

For all these methods, the proposed method always keeps the highest probability of detection in both simulation scenarios. Even when $\lambda = 100$, it still keeps 63.2%, while the highest detection probability of the remaining methods is 45.3%. These simulation
results indicate that the new method has a superior performance for track initiation, and is very robust to clutter interference.

<table><caption>Table 1 Performance comparison of 5 track initiation methods</caption><thead><tr><th colspan="2">Track initiation method</th><th>P<sub>D</sub></th><th>P<sub>F</sub></th></tr></thead><tbody><tr><td rowspan="5">λ = 50</td><td>The heuristic rule method</td><td>82.3%</td><td>57.6%</td></tr><tr><td>The logic-based method</td><td>82.5%</td><td>58.7%</td></tr><tr><td>The HT method</td><td>12.1%</td><td>88.6%</td></tr><tr><td>The modified HT method</td><td>85.2%</td><td>44.8%</td></tr><tr><td>The proposed method</td><td>89.3%</td><td>38.5%</td></tr><tr><td rowspan="5">λ = 100</td><td>The heuristic rule method</td><td>20.4%</td><td>82.7%</td></tr><tr><td>The logic-based method</td><td>25.2%</td><td>76.3%</td></tr><tr><td>The HT method</td><td>0.1%</td><td>95.2%</td></tr><tr><td>The modified HT method</td><td>45.3%</td><td>64.2%</td></tr><tr><td>The proposed method</td><td>63.2%</td><td>42.1%</td></tr></tbody></table>

To further validate the effectiveness of the proposed algorithm, describes the computational cost for methods based on Hough transform. From the table we know that the proposed method is less computational than the HT method and the modified HT method, and is more suitable for fast track initiation in dense clutters.

<table><caption>Table 2 Comparison of computational cost for HT based methods</caption><thead><tr><th colspan="2">Track initiation method</th><th>computational cost</th></tr></thead><tbody><tr><td rowspan="3">λ = 50</td><td>The HT method</td><td>4.7×10<sup>7</sup></td></tr><tr><td>The modified HT method</td><td>3.6×10<sup>6</sup></td></tr><tr><td>The proposed method</td><td>2.1×10<sup>4</sup></td></tr><tr><td rowspan="3">λ = 100</td><td>The HT method</td><td>3.3×10<sup>8</sup></td></tr><tr><td>The modified HT method</td><td>5.2×10<sup>7</sup></td></tr><tr><td>The proposed method</td><td>8.6×10<sup>5</sup></td></tr></tbody></table>

# 5 Conclusions

In this paper, a novel method for Fast track initiation in dense clutters by divide and Hough transform method is proposed, which connects any two points from different cycles and calculates the exact intersection of the two points in parameter space. With the measurement's time sequence information and targets' kinematics information considered, this new algorithm avoids a single scan data accumulation effect, and can improve the reliability of formed tracks. In this new algorithm, measurements in observation space only vote to part lines instead of all in standard Hough transform that pass through them, so it can effectively reduce computation and memory, and improve the speed of track initiation. In addition, the simulation results also validate the superior performance of the new algorithm and indicate that it can effectively eliminate the false tracks, and is more robust to clutter inference.

# Acknowledgements

This work is supported by the State Key Program for Basic Research of China (No. 613XXXXX), National Natural Science Foundation of China (No. 91538201).

# References
1. Y. Bar-Shalom, P. K. Willett, and X. Tian: Tracking and Data Fusion: A Handbook of Algorithms. Academic, New York (2011).

2. Seung-Woo Kim, Young-Taek Lim, Taek-Lyul Song: A Study of a New Data Association and Track initiation Method with Normalized Distance Squared Ordering. International Journal of Control, Automation and Systems, 9(5): 815-822 (2011).

3. Yasushi Obata, Ryoji Maekawa, et al: Track Initiation Algorithm for Dim Target Using Backward Prediction. SICE Conference, pp. 1267-1273, Japan (2013).

4. Farina, Alfonso, and Flavio A. Studer: Radar Data Processing: Introduction and Tracking. Research Studies Press Ltd, vol. 1 (1985).

5. Blackman, Samuel S: Multiple Hypothes for Multiple Target Tracking. Aerospace and Electronic Systems Magazine, 19(1): 5-18 (2004).

6. Musicki, Darko, Robin Evans, and Srdjan Stankovic: Integrated Probabilistic Data Association. Automatic Control, 39(6): 1237-1241 (1994).

7. Casasent, D.P., and Slaski, J: Optical Track Initiator for Multitarget Tracking. Appl. Opt, 27: 4546-4553 (1988).

8. Lo, T., et al.: Multitarget Track Initiation Using a Modified Hough Transform. Pointing and Tracking Systems, 1: 12-18 (1994).