1.1 Related work

Almost all research so far on extracting motion information from OGMs have been done under the framework of DATMO. Petrovskaya et al. [11] propose to classify these methods in three categories: Traditional DATMO, Model-based DATMO and Grid-based DATMO. See [11] and the comprehensive survey [19] for more details about DATMO.

In this paper, we focus our attention on the detection of moving grid cells and their velocity estimation, regardless of the tracking problem on object level. According to different ways of understanding motion, we classify those techniques into three categories: Object-Oriented (OO), Cell-Oriented(CO), and OCcupancy-Oriented(OCO).

1.2 KST in radar signal processing

In this paper, we attempt to propose a different way of extracting motion information from successive OGMs based on a signal transformation, called the keystone transform (KST) , which has been popularly used in the radar signal processing community. For example, [25] employed the KST was used to remove the linear component of the range migration for the moving target in the synthetic aperture radar (SAR) imaging. [26] proposed the fast implementation of KST based on Chirp-Z transform (CZT) in order to overcome the range migration in the long time coherent accumulation for detecting the dim moving targets. Recently, the high order KST were proposed for the above applications in [27][28] and [29] to correct the three order phase migration of the radar echo signal. For extracting the motion information from the OGMs, there exist many similarities to the range migration correction in the radar signal processing, such as focusing or accumulating the moving object with the unknown velocity, and the concepts of range and Doppler in radar signal processing are like the space cell and the velocity in the OGMs. Nevertheless, there also exist several differences with the KST of radar signal processing. One significant difference is that the radar signal in the complex number field and the OGMs is in the real number field. Another important difference is the unknown motion is usually the redial motion along the line of sight of the radar, although it can be high order motion (i.e. with the non-zero acceleration). However, the spatial motion in the OGMs can be one dimensional along the street way, two dimensional along the ground, and three dimensional in the free space. For the ground mobile robotics, we consider one dimensional and two dimensional cases in this paper.

1.3 Scope of this paper

This paper tries to develop a different way of extracting motion information from successive OGMs based on a signal transformation by extending the KST in the radar signal processing community to the 1D and 2D spatial case. The main theoretic idea occurred in our conference paper [30] and this journal article was mainly enlarged from the three aspects, i.e., the more detailed survey, the fast algorithm implementation of 2DS-KST and the experiments for the extended objects. For the sake of integrity, the original point object test results are also kept in this article.

3.1 2DS-KST with multiple hypotheses

Let us still consider only one ideal point object in the sensor field of view. Assume its initial position is ${𝐫}_0={[l_0,m_0]}^T$ and it has a constant velocity $𝐕={[V_x,V_y]}^T={[V\cos \left(\theta \right),V\sin \left(\theta \right)]}^T$, in which $V_x,V_y$ satisfy the condition of $V_x,V_y\in [-V_{\max }/2,+V_{\max }/2)$. Then for a given time instant $t$, the OGM has the following form:

where $\text{Rect}(l,m)$ denote the region of the cell $(l,m)$.

For the 2D spatial case, equation (5) becomes as follows:

where $𝐢={[i,j]}^T$, ${𝐮}_{\theta }={[\cos \theta ,\sin \theta ]}^T$ and $i_{\theta }=i\cos \theta +j\sin \theta$.

As the above described, we assume there are finite possible hypotheses for $\theta$, and denote the $p$th hypothesis as ${\theta }_p$ ($p=1,\dots ,\nu$). But the real case is we don't know the actually moving direction of the object, so we need to do KST for every possible hypothesis, then we can get:

where

(4) result from the fact that the item $V{i}_{\theta }$ in (3) can be rewritten as:

Furthermore, if the hypothesis ${\theta }_p$ is true, that is to say, $\theta$ is approximately parallel to ${\theta }_p$, the last product item in (4) can be ignored further. In this case, for the ${\theta }_p$ hypothesis, (4) can be approximated as the following:

where $t^{\prime }$ is defined as:

The interpolate filter of Keystone transform is the same as 1D case, so we can get ${\tilde{f}}_n^{{\theta }_p}(l_0,m_0)$ as follows:

The counterpart of the above equation in 1D case is (17). After doing the DFT for ${\tilde{f}}_n^{{\theta }_p}(l_0,m_0)$ in terms of $n$ for every occupied grid cell ${[l_0,m_0]}^T$, we can get:

Thus, similar to 1D case, $V_{{\theta }_p}$, the magnitude of the velocity in the grid cell ${[l_0,m_0]}^T$ can be given as follows:

while the direction of the velocity in this cell is given by ${\theta }_p$, which is the assumption given in the previous, once used in (6).

3.2 Merging multiple hypotheses

The velocity measurement given by (11) is in the case of the ${\theta }_p$ hypothesis is true for this cell. In practice, we don't know which hypothesis is true for any occupied grid cell ${[l,m]}^T$ in advance, so we must merge the results of those multiple hypotheses so that the correct motion information can be given.

In fact, by 2DS-KST with multi-hypothesis, we can get $\nu$ cuboid ${\widetilde{ℱ}}^{{\theta }_p}(l,m,k)$, which is the general form of (10) for any arbitrary grid cell ${[l,m]}^T$ under the hypothesis ${\theta }_p$. That is to say, we get the two dimensional matrix ${\widetilde{ℱ}}_{l,m}({\theta }_p,k)$ for every grid cell ${[l,m]}^T$, which represents the possible velocity in this cell, including the magnitude (denoted by $k$, which can be negative) and the direction (denoted by ${\theta }_p$).

Here we use a MPD (Maximal Power Detector) based method for the purpose of extracting the motion information from ${\widetilde{ℱ}}_{l,m}({\theta }_p,k)$, which is based on the fact that the power item ${\left|{\widetilde{ℱ}}_{l,m}({\theta }_p,k)\right|}^2$ will be larger when ${\theta }_p$ and $k$ are more matched with the true value of the velocity. It can be described as the following four steps:

As the above MPD approach of merging multiple hypotheses only outputs the most likely point estimation for the velocity, it is obvious that it is only appropriate for the case when the occupancies in each grid cell only have one significant velocity during the time interval. Nevertheless, it does not affect the versatility of 2D-KST for extracting motion information. For instance, we can use the more complex GMM (Gaussian Mixture Model) instead of the point estimation in MPD method as the velocity model of occupancy, which would undoubtedly increase the robustness and the compatibility to the complex situations. In fact, which velocity model should be selected is a key problem in practice and it closely depends on the physical application.

For the more complex method of merging multiple hypotheses, it is already beyond the scope of this paper and may be an appropriate topic for the future work.

5.1 Point object test

In this experiment, we use the simulation data of point object to test the 1D-KST and 2D-KST. Considering the sensor noise and the imperfections in the OGM building process, we add to the OGMs some Poisson noise, which is uniformly distributed in the grid cells and whose number obeys the Poisson distribution. The main parameters in the simulation is shown in the Table 1, where the velocities $𝖵$ are represented in the normalized format, and the scale factor $\alpha$ in $i_c^{{\theta }_p}$ is defined as follows:

The results of the one dimensional test are shown in Figures 3 - 5. From Figure 3, we can see five objects moving at different speeds along positive direction or negative direction. The speed of the fastest one is $0.5$, which is the maximal feasible velocity given by the Nyquist sampling theorem, and the speed of the slowest moving object is $0.05$, which is very close to the velocity resolution given by (22). Through this setting, we can validate 1D-KST in terms of velocity measurement capability. Meanwhile, we set a stationary object at $l_0=20$, which can be used to check the performance on the separation of the dynamic grids from the static ones. After adding the Poisson noise, the OGMs look very noisy.

Figure 3 Sequence of the simulated one dimensional OGMs: $f(l,n)$.

(a) amplitude

(b) phase

Figure 4 Result of OGM sequence by the spatial Fourier transform: $ℱ(i,n)$.

Figure 5 Result of 1D-KST: $\widetilde{ℱ}(l,k)$. The color denotes the total power of the accumulated occupancies in this cell during the $N$ time instants. The green box on every object indicates the corresponding resolution of 1D-KST for the position and the velocity.

The result of OGM sequence by the spatial Fourier transform is shown in Figure 4. As the noise in the OGMs, it is hardly to see any change information along the time axis from Figure 4(a). However, it can still be seen from the phase of $ℱ(i,n)$ in Fig. 4(b). Moreover, it is not hardly to see the symmetry with respect to the spatial frequency axis from Figure 4 because our OGMs are all real numbers, thus from the information point of view we can only set the spatial frequency window in one side of the spatial frequency axis.

The final result of 1D-KST is shown in Figure 5. When looked together with Figure 3, it is clearly shown that all objects are well located in the grid cells at the midpoint time instant and their velocities are also measured with a high precision even for these so noisy OGMs22. Moreover, the occupies of every are well focused in the green box determined by 1D-KST's resolution, which is determined by (22) and the width of the spatial frequency window:

From this result, we can conclude that 1D-KST has a good performance for the point object in terms of OGM filtering and the extraction of motion information.

The results of the two dimensional test are shown in Figures 6 - 10. Similar to the one dimensional case, we choose the maximal feasible and minimal detectable speed to are set to evaluate the capability of 2D-KST in terms of velocity measurement. Different from one dimensional case, we use eight hypotheses of direction to match the possible moving directions in OGMs. Among all five moving objects, four are moving along the direction in the hypothesis sets, while the last one (#5) is moving near the middle direction between the hypothesis ${\theta }_p=7\pi /8$ and the reverse direction of ${\theta }_p=0$, but slightly close to ${\theta }_p=7\pi /8$. Through this setting, we can evaluate the performance when the true moving direction dose not match any hypotheses. To see the result more clearly, we decrease the map size $L=64$ in the two dimensional test. The detailed parameter setting used in this simulation can be seen in Table 1.

Figure 6 Sequence of the simulated two dimensional OGMs: $f(l,m,n)$.

Figure 7 Spatial frequency window $W_{{\theta }_p}(i,j)$. (a)-(h) are the cases of ${\theta }_p=0,\pi /8,\dots ,7\pi /8$, respectively. The x-ticks and y-ticks are both the normalized values of spatial frequency. The value of the point inside the colorful quadrangle is equal to 1, while zero for the outside point.

Figure 8 Result of 2D-KST after the first merging step of MPD: $𝒫(l,m)$. The color denotes the total power of the accumulated occupancies in this cell during the $N$ time instants.

Figure 9 Result of 2D-KST after the processing of MPD. The color has the same meaning as Figure 8. The blue arrows denote the velocities of the grid cells, whose lengths are proportional to the speed.

Figure 10 Comparison of the measurement and the true value of the velocity.

Figure 6 shows the noisy 2D-OGM sequence. It is very difficult to recognize the trajectory of each object by human eyes. To make the window $W_{{\theta }_p}(i,j)$ more intuitive than the expression (1) to the reader, we show them in Figure 7. In principle, the counterpart of the spatial frequency window here is the directional filter in optical signal processing, this is also the reason why we call the second step of 2D-KST as directional filtering.

After the first merging step of MPD, the result $𝒫(l,m)$ of 2D-KST processing is shown in Figure 8, which can be regard as the filtered OGM at the time instant $n=0$. Figure 8, we can found that the noise in the original OGM is almost filtered, and the grid cells in the vicinity of objects have a significant occupancy value. The occupancies in the yellow grid cells around each object are the leakage of occupancy in the corresponding object grid cell, which is the consequence caused by the window $W_{{\theta }_p}(i,j)$. Among all the six objects, the stationary object at $(10,10)$ behaves obviously isotropic, while the other moving objects behave the obvious directionality, which means that they have the biggest extent along their moving direction. Moreover, we can found that the grid cells near the mismatched one at $(45,50)$ have a relatively smaller value than those near the matched objects. Nonetheless, their values are at least twice as large as the values of those yellow grid cells. Thus, if we set the appropriate threshold $P_{\min }$, see (13), we can remove the leakage occupancies in the yellow cells but maintain those in the vicinity of the mismatched object grid cell. Furthermore, if our requirement is to extract the moving objects, we can filter the stationary one by setting the appropriate threshold $V_{\min }$, see (16).

The result of 2D-KST after MPD processing is shown in Figure 9, where $P_{\min }=0.3981$ (-8dB) and $V_{\min }=0.085$ are used, and where the blue arrows represent the velocity of the occupies in the corresponding cells, the length and pointing for the amplitude and the direction respectively. As can be seen from Figure 9, the stationary object has been removed successfully, although it has the maximal occupancy, while the five moving objects all persist in existing. What's more, the velocity measurements are highly in accordance with the ground truth in Table 1. To see it more obviously, the simple plot extractor is used, which extracts the local power maximum grid cells from the MPD results as the candidate detections and computes the occupancy weighted velocity as the velocity measurement of each candidate detection. The measurement results are shown in Figure 10, which suggest that 2D-KST has a good precision of velocity measurement for the point object and can be easily integrated with the plot extractor or other object clustering algorithm, such as FCTA [22].

5.2 Extend object test

The purpose of this experiment is to illustrate how the parameters of the spatial frequency window affect the output for different object sizes. Since the window parameters have the same effect on the output for the 1D and 2D cases and the 1D case is more easily to explain, we test two typical windows in one dimensional case for five different object sizes firstly. Through this test, some guidelines about how to choose the parameters for the spatial frequency window are derived. Then we validate these guidelines through 2D test for different object sizes. The size of each object used in this experiment is listed in Table 2, where the value means how many grid cells are occupied by this object. For 2D case, the two values correspond to the numbers of the occupied grid cells parallel and perpendicular to the direction of the velocity respectively. The other parameters are the same as Table 1 if without any special explanations.

The responses to the two typical windows in one dimensional case to the five object sizes are shown in Figure 11.

As can be seen from Figure 1111(a) and 11(b), the wide window has a better resolution whether for the position or for the velocity, because it has a wider window and a higher reference spatial frequency $i_c$. See (2) and (22) for the formulas about the KST resolution. But the large objects, object #0 at cell 20 and object #1 at cell 40 are split into two parts because the bandpass spatial filter is used in our KST approach. However, the two parts, the head and the tail, are both in the extent of the corresponding object which is represented by the green box. Fortunately, this split outcome may be accepted for many applications, such as CTM building [12] or DATMO using FCTA [22].

(a) Wide window

(b) Narrow window

Figure 11 Responses of the two typical windows in one dimensional case to the different sizes of objects. (a) $i_c=L/4,i_{\min }=L/8,i_{\max }=3L/8$; (b) $i_c=L/8,i_{\min }=L/16,i_{\max }=3L/16$. The color denotes the total power of the accumulated occupancies in this cell during the $N$ time instants. The length of the green box on each object along $l$ direction denotes the sum of the position resolution of 1D-KST and the extent of this object, while the length along normalized velocity direction denotes the corresponding velocity resolution of 1D-KST.

If it can not be accepted, the narrow window can be used instead. As shown in Figure 1111(b), all objects are focused in the corresponding green box. However, the velocity resolution gets worsened as the lower $i_c$ used, and the object #2 at cell 60 has a negligible occupancy inside its green box since only very little proportion of its power can enter the narrow window.

In principle, we can get the following two empirical criteria for selecting the parameters of the spatial frequency:

In practice, we can choose the appropriate parameters of spatial frequency window to meet the above two criteria. But for those applications in which the moving objects have the significant difference in size, for example, the case of Figure 11, we can use multiple windows to match different object sizes, or use a uniform window but based on the multiple resolution grid cell maps for different sizes of objects. Along this path, it will result in a multiple resolution KST approach, which is beyond the scope of this paper and maybe the next step work in the future.

Next we validate the wide window in 2D case, the parameters can be seen in Table 1, through those objects in Table 2, where the extensions of all moving objects are no larger than 3 grid cells. The corresponding results are shown in Figure 12. From these results, we can conclude that when using the appropriate setting of spatial frequency window, the 2D-KST can perform very well for the extend objects when they have no too much difference in size.

Similar to the point object test, in order to demonstrate the potential capability of integrating with FCTA or other extend target tracking algorithms, we give the result of the plot extractor, which is shown in Table 3. As can be seen from Table 3, ten detections are achieved for those five moving objects altogether, and the average position is at the center of extend object, see Table 1 for the ground truth. Moreover, the velocity measurements also have a high precision, even for the mismatch one (#5), the maximal speed error is less than 0.05 and the direction of velocity is no more than 7 degrees among those three detections generated by this object.

Above all, as the point object test, it seems that 2D-KST has a good precision of velocity measurement for the extend object and can be easily integrated with the plot extractor or any other extend object tracking algorithm.

(a) Result after the first mergering step of MPD

(b) Result after the MPD processing

Figure 12 Result of 2D-KST for extend object. The color denotes the total power of the accumulated occupancies in this cell during the $N$ time instants. The blue arrows denote the velocities of the grid cells, whose lengths are proportional to the speed.