Extraction of Motion Information from Occupancy Grid Map Using Keystone Transform

Hongqi Fan; Dawei Lu; Yanwen Jiang; Achim J. Lilienthal

doi:10.62762/CJIF.2024.361892

Article Information

Published in Chinese Journal of Information Fusion

Volume/Issue Volume 1, Issue 1, 2024

Pages 63-78

Cited by 3 (Crossref) 3 (Scopus)

Abstract

Considering the tractability of OGM (Occupancy Grid Map) and its wide use in the dynamic environment representation of mobile robotics, the extraction of motion information from successive OGMs are very important for many tasks, such as SLAM (Simultaneously Localization And Mapping), DATMO (Detection and Tracking of Moving Object) and informaiton fusion for situation awareness. In this paper, we propose a novel motion extraction method based on the signal transform, called as S-KST (Spatial Keystone Transform), for the motion detection and estimation from successive noisy OGMs. It extends the KST in radar imaging or motion compensation to 1D spatial case (1DS-KST) and 2D spatial case (2DS-KST) combined multiple hypotheses about possible directions of moving obstacles. Meanwhile, the fast algorithm of 2DS-KST based on Chirp Z-Transform (CZT) is also given, which five steps, i.e. spatial FFT, directional filtering, CZT, spatial IFFT and Maximal Power Detector (MPD) merging and its computational complexity is proportional to the 2D-FFT. Simulation test results for the point objects and the extended objects show that SKST has a good performance on the extraction of sub-pixel motions in very noisy environment, especially for those slowly moving obstacles.

Graphical Abstract

Extraction of Motion Information from Occupancy Grid Map Using Keystone Transform

Keywords

mobile robotics occupancy grid map moving object keystone transform 2DS-KST velocity estimation situation informaiton fusion

Data Availability Statement

Data will be made available on request.

Funding

This work was supported in part by the National Natural Science Foundation of China under Grant 62303478; in part by the ATR Foundation under Grant 2035250204; in part by the Key Lab. Foundation under Grant 220302.

Conflicts of Interest

The authors declare no conflicts of interest.

Ethical Approval and Consent to Participate

Not applicable.

References

Coué, C., Pradalier, C., Laugier, C., Fraichard, T., & Bessière, P. (2006). Bayesian occupancy filtering for multitarget tracking: an automotive application. The International Journal of Robotics Research, 25(1), 19-30.
[CrossRef] [Google Scholar]
Tay, M. K., Mekhnacha, K., Yguel, M., Coue, C., Pradalier, C., Laugier, C., ... & Bessiere, P. (2008). The Bayesian occupation filter. In Probabilistic Reasoning and Decision Making in Sensory-Motor Systems (pp. 77-98). Berlin, Heidelberg: Springer Berlin Heidelberg.
[CrossRef] [Google Scholar]
Kondaxakis, P., Kasderidis, S., & Trahanias, P. (2008). Tracking multiple targets from a mobile robot platform using a laser range scanner. In 2008 IET Seminar on Target Tracking and Data Fusion: Algorithms and Applications (pp. 175-184).
[CrossRef] [Google Scholar]
Vu, T. D., Burlet, J., & Aycard, O. (2008). Mapping of environment, detection and tracking of moving objects using occupancy grids. In Intelligent Vehicles Symposium (pp. 684-689). Los Alamitos: IEEE.
[Google Scholar]
Gindele, T., Brechtel, S., Schroder, J., & Dillmann, R. (2009, June). Bayesian occupancy grid filter for dynamic environments using prior map knowledge. In 2009 IEEE Intelligent Vehicles Symposium (pp. 669-676). IEEE.
[CrossRef] [Google Scholar]
Baig, Q., Perrollaz, M., & Laugier, C. (2014). Advances in the Bayesian Occupancy Filter framework using robust motion detection technique for dynamic environment monitoring. IEEE Robotics and Automation Magazine.
[Google Scholar]
Wolcott, R. W., & Eustice, R. M. (2015, May). Fast LIDAR localization using multiresolution Gaussian mixture maps. In 2015 IEEE international conference on robotics and automation (ICRA) (pp. 2814-2821). IEEE.
[CrossRef] [Google Scholar]
Behley, J., & Stachniss, C. (2018, June). Efficient surfel-based SLAM using 3D laser range data in urban environments. In Robotics: science and systems (Vol. 2018, p. 59).
[Google Scholar]
Durrant-Whyte, H., & Bailey, T. (2006). Simultaneous localization and mapping: part I. IEEE robotics & automation magazine, 13(2), 99-110.
[CrossRef] [Google Scholar]
Bailey, T., & Durrant-Whyte, H. (2006). Simultaneous localization and mapping (SLAM): Part II. IEEE robotics & automation magazine, 13(3), 108-117.
[CrossRef] [Google Scholar]
Petrovskaya, A., Perrollaz, M., Oliveira, L., Spinello, L., Triebel, R., Makris, A., ... & Bessière, P. (2012). Awareness of road scene participants for autonomous driving. Handbook of Intelligent Vehicles, 1383-1432.
[Google Scholar]
Kucner, T., Saarinen, J., Magnusson, M., & Lilienthal, A. J. (2013, November). Conditional transition maps: Learning motion patterns in dynamic environments. In 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 1196-1201). IEEE.
[CrossRef] [Google Scholar]
Wang, C. C., Thorpe, C., Thrun, S., Hebert, M., & Durrant-Whyte, H. (2007). Simultaneous localization, mapping and moving object tracking. The International Journal of Robotics Research, 26(9), 889-916.
[CrossRef] [Google Scholar]
Ess, A., Leibe, B., Schindler, K., & Van Gool, L. (2009, May). Moving obstacle detection in highly dynamic scenes. In 2009 IEEE International Conference on Robotics and Automation (pp. 56-63). IEEE.
[CrossRef] [Google Scholar]
Baig, Q., Perrollaz, M., Do Nascimento, J. B., & Laugier, C. (2012, December). Using fast classification of static and dynamic environment for improving Bayesian occupancy filter (BOF) and tracking. In 2012 12th International Conference on Control Automation Robotics & Vision (ICARCV) (pp. 656-661). IEEE.
[CrossRef] [Google Scholar]
Hahnel, D., Triebel, R., Burgard, W., & Thrun, S. (2003, September). Map building with mobile robots in dynamic environments. In 2003 IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422) (Vol. 2, pp. 1557-1563). IEEE.
[CrossRef] [Google Scholar]
Elfes, A. (1989). A probabilistic framework for robot perception and navigation. PhD thesis, Carnegie-Mellon University.
[Google Scholar]
Elfes, A. (1989). Using occupancy grids for mobile robot perception and navigation. Computer, 22(6), 46-57.
[CrossRef] [Google Scholar]
Pancham, A., Tlale, N., & Bright, G. (2011). Literature review of SLAM and DATMO. RobMech 2011. http://hdl.handle.net/10204/5457
[Google Scholar]
Baig, Q., & Aycard, O. (2012, June). Improving moving objects tracking using road model for laser data. In 2012 IEEE Intelligent Vehicles Symposium (pp. 790-795). IEEE.
[CrossRef] [Google Scholar]
Chen, C., Tay, C., Laugier, C., & Mekhnacha, K. (2006, December). Dynamic environment modeling with gridmap: a multiple-object tracking application. In 2006 9th International Conference on Control, Automation, Robotics and Vision (pp. 1-6). IEEE.
[CrossRef] [Google Scholar]
Mekhnacha, K., Mao, Y., Raulo, D., & Laugier, C. (2008, September). Bayesian occupancy filter based" fast clustering-tracking" algorithm. In IROS 2008.
[Google Scholar]
Tay, M. K., Mekhnacha, K., Chen, C., Yguel, M., & Laugier, C. (2008). An efficient formulation of the Bayesian occupation filter for target tracking in dynamic environments. International Journal of Vehicle Autonomous Systems, 6(1-2), 155-171.
[CrossRef] [Google Scholar]
Fan, H., Kucner, T. P., Magnusson, M., Li, T., & Lilienthal, A. J. (2017). A dual PHD filter for effective occupancy filtering in a highly dynamic environment. IEEE Transactions on Intelligent Transportation Systems, 19(9), 2977-2993.
[CrossRef] [Google Scholar]
Zhu, D., Li, Y., & Zhu, Z. (2007). A keystone transform without interpolation for SAR ground moving-target imaging. IEEE Geoscience and Remote Sensing Letters, 4(1), 18-22.
[CrossRef] [Google Scholar]
Zhao, Y., Wang, J., Huang, L., & Yang, R. (2011, October). Low complexity keystone transform without interpolation for dim moving target detection. In Proceedings of 2011 IEEE CIE International Conference on Radar (Vol. 2, pp. 1745-1748). IEEE.
[CrossRef] [Google Scholar]
Huang, P., Liao, G., Yang, Z., Xia, X. G., Ma, J., & Zheng, J. (2016). Ground maneuvering target imaging and high-order motion parameter estimation based on second-order keystone and generalized Hough-HAF transform. IEEE Transactions on Geoscience and Remote Sensing, 55(1), 320-335.
[CrossRef] [Google Scholar]
Huang, P., Liao, G., Yang, Z., Xia, X. G., Ma, J. T., & Ma, J. (2016). Long-time coherent integration for weak maneuvering target detection and high-order motion parameter estimation based on keystone transform. IEEE Transactions on Signal Processing, 64(15), 4013-4026.
[CrossRef] [Google Scholar]
Zhan, M., Huang, P., Zhu, S., Liu, X., Liao, G., Sheng, J., & Li, S. (2021). A modified keystone transform matched filtering method for space-moving target detection. IEEE Transactions on Geoscience and Remote Sensing, 60, 1-16.
[CrossRef] [Google Scholar]
Fan, H., Lu, D., Kucner, T. P., Magnusson, M., & Lilienthal, A. (2018, July). 2D spatial keystone transform for sub-pixel motion extraction from noisy occupancy grid map. In 2018 21st International Conference on Information Fusion (FUSION) (pp. 1-7). IEEE.
[CrossRef] [Google Scholar]
Richards, M. A. (2014). The keystone transformation for correcting range migration in range-doppler processing. pulse, 1000(1).
[Google Scholar]
Rabiner, L. R., Schafer, R. W., & Rader, C. M. (1969). The chirp z‐transform algorithm and its application. Bell System Technical Journal, 48(5), 1249-1292.
[CrossRef] [Google Scholar]
Rajmic, P., Prusa, Z., & Wiesmeyr, C. (2014, September). Computational cost of Chirp Z-transform and Generalized Goertzel algorithm. In 2014 22nd European Signal Processing Conference (EUSIPCO) (pp. 1004-1008). IEEE.
[Google Scholar]

Cited By (3)

Wenting Ding, Dan Xu, Jinlong Shi, Qiang Qian. RDFT-CDUN: Image compressed sensing using complex-valued measurement matrix and complex-based deep unfolding network. Knowledge-Based Systems, 2025 , 322 .
[CrossRef]
Xin Xiong, Xiangyu Wang, Suorong Yang, Furao Shen, Jian Zhao. GMNI: Achieve good data augmentation in unsupervised graph contrastive learning. Neural Networks, 2025 , 181 .
[CrossRef]
Yong Wang, Xiaoming Dong, Jianfeng Zeng, Pengfei Du. Intelligent Driving Based on Multi-Objective Shifting Decision Method for Vehicle Transmission System. IEEE Transactions on Intelligent Transportation Systems, 2025 , 26 (10).
[CrossRef]

* Citation data provided by Crossref Cited-by.

Cite This Article

APA Style

Fan, H., Lu, D., Jiang, Y., & Lilienthal, A. J. (2024). Extraction of Motion Information from Occupancy Grid Map Using Keystone Transform. Chinese Journal of Information Fusion, 1(1), 63–78. https://doi.org/10.62762/CJIF.2024.361892

Export Citation

RIS Format

Compatible with EndNote, Zotero, Mendeley, and other reference managers

TY  - JOUR
AU  - Fan, Hongqi
AU  - Lu, Dawei
AU  - Jiang, Yanwen
AU  - Lilienthal, Achim J.
PY  - 2024
DA  - 2024/06/10
TI  - Extraction of Motion Information from Occupancy Grid Map Using Keystone Transform
JO  - Chinese Journal of Information Fusion
T2  - Chinese Journal of Information Fusion
JF  - Chinese Journal of Information Fusion
VL  - 1
IS  - 1
SP  - 63
EP  - 78
DO  - 10.62762/CJIF.2024.361892
UR  - https://www.icck.org/article/abs/CJIF.2024.361892
KW  - mobile robotics
KW  - occupancy grid map
KW  - moving object
KW  - keystone transform
KW  - 2DS-KST
KW  - velocity estimation
KW  - situation informaiton fusion
AB  - Considering the tractability of OGM (Occupancy Grid Map) and its wide use in the dynamic environment representation of mobile robotics, the extraction of motion information from successive OGMs are very important for many tasks, such as SLAM (Simultaneously Localization And Mapping), DATMO (Detection and Tracking of Moving Object) and informaiton fusion for situation awareness. In this paper, we propose a novel motion extraction method based on the signal transform, called as S-KST (Spatial Keystone Transform), for the motion detection and estimation from successive noisy OGMs. It extends the KST in radar imaging or motion compensation to 1D spatial case (1DS-KST) and 2D spatial case (2DS-KST) combined multiple hypotheses about possible directions of moving obstacles. Meanwhile, the fast algorithm of 2DS-KST based on Chirp Z-Transform (CZT) is also given, which five steps, i.e. spatial FFT, directional filtering, CZT, spatial IFFT and Maximal Power Detector (MPD) merging and its computational complexity is proportional to the 2D-FFT. Simulation test results for the point objects and the extended objects show that SKST has a good performance on the extraction of sub-pixel motions in very noisy environment, especially for those slowly moving obstacles.
SN  - 2998-3371
PB  - Institute of Central Computation and Knowledge
LA  - English
ER  -

BibTeX Format

Compatible with LaTeX, BibTeX, and other reference managers

@article{Fan2024Extraction,
  author = {Hongqi Fan and Dawei Lu and Yanwen Jiang and Achim J. Lilienthal},
  title = {Extraction of Motion Information from Occupancy Grid Map Using Keystone Transform},
  journal = {Chinese Journal of Information Fusion},
  year = {2024},
  volume = {1},
  number = {1},
  pages = {63-78},
  doi = {10.62762/CJIF.2024.361892},
  url = {https://www.icck.org/article/abs/CJIF.2024.361892},
  abstract = {Considering the tractability of OGM (Occupancy Grid Map) and its wide use in the dynamic environment representation of mobile robotics, the extraction of motion information from successive OGMs are very important for many tasks, such as SLAM (Simultaneously Localization And Mapping), DATMO (Detection and Tracking of Moving Object) and informaiton fusion for situation awareness. In this paper, we propose a novel motion extraction method based on the signal transform, called as S-KST (Spatial Keystone Transform), for the motion detection and estimation from successive noisy OGMs. It extends the KST in radar imaging or motion compensation to 1D spatial case (1DS-KST) and 2D spatial case (2DS-KST) combined multiple hypotheses about possible directions of moving obstacles. Meanwhile, the fast algorithm of 2DS-KST based on Chirp Z-Transform (CZT) is also given, which five steps, i.e. spatial FFT, directional filtering, CZT, spatial IFFT and Maximal Power Detector (MPD) merging and its computational complexity is proportional to the 2D-FFT. Simulation test results for the point objects and the extended objects show that SKST has a good performance on the extraction of sub-pixel motions in very noisy environment, especially for those slowly moving obstacles.},
  keywords = {mobile robotics, occupancy grid map, moving object, keystone transform, 2DS-KST, velocity estimation, situation informaiton fusion},
  issn = {2998-3371},
  publisher = {Institute of Central Computation and Knowledge}
}

Article Metrics

Citations

Crossref

3

Scopus

3

Views

6651

PDF Downloads

1054

Publisher's Note

ICCK stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and Permissions

Copyright © 2024 by the Author(s). Published by Institute of Central Computation and Knowledge. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

Chinese Journal of Information Fusion

ISSN: 2998-3371 (Online) | ISSN: 2998-3363 (Print)

[email protected]

Preserved at
Portico

User

Unlimited Downloads

Complete Library Access

Membership Eligibility

Community Leadership Opportunities