Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Extended target tracking using PHD filters
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.ORCID iD: 0000-0002-3450-988X
2012 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The world in which we live is becoming more and more automated, exemplified by the numerous robots, or autonomous vehicles, that operate in air, on land, or in water. These robots perform a wide array of different tasks, ranging from the dangerous, such as underground mining, to the boring, such as vacuum cleaning. In common for all different robots is that they must possess a certain degree of awareness, both of themselves and of the world in which they operate. This thesis considers aspects of two research problems associated with this, more specifically the Simultaneous Localization and Mapping (SLAM) problem and the Multiple Target Tracking (MTT) problem.

The SLAM problem consists of having the robot create a map of an environment and simultaneously localize itself in the same map. One way to reduce the effect of small errors that inevitably accumulate over time, and could significantly distort the SLAM result, is to detect loop closure. In this thesis loop closure detection is considered for robots equipped with laser range sensors. Machine learning is used to construct a loop closure detection classifier, and experiments show that the classifier compares well to related work.

The resulting SLAM map should only contain stationary objects, however the world also contains moving objects, and to function well a robot should be able to handle both types of objects. The MTT problem consists of having the robot keep track of where the moving objects, called targets, are located, and how these targets are moving. This function has a wide range of applications, including tracking of pedestrians, bicycles and cars in urban environments. Solving the MTT problem can be decomposed into two parts: one part is finding out the number of targets, the other part is finding out what the states of the individual targets are.

In this thesis the emphasis is on tracking of so called extended targets. An extended target is a target that can generate any number of measurements, as opposed to a point target that generates at most one measurement. More than one measurement per target raise interesting possibilities to estimate the size and the shape of the target. One way to model the number of targets and the target states is to use random finite sets, which leads to the Probability Hypothesis Density (PHD) filters. Two implementations of an extended target PHD filter are given, one using Gaussian mixtures and one using Gaussian inverse Wishart (GIW) mixtures. Two models for the size and shape of an extended target measured with laser range sensors are suggested. A framework for estimation of the number of measurements generated by the targets is presented, and reduction of GIW mixtures is addressed. Prediction, spawning and combination of extended targets modeled using GIW distributions is also presented. The extended target tracking functions are evaluated in simulations and in experiments with laser range data.

Abstract [sv]

Den värld i vilken vi lever har med tiden blivit allt mer automatiserad. Ett av många tecken på detta är det stora antal robotar, eller autonoma farkoster, som verkar bland annat i luften, på land, eller i vatten. De här robotarna kan utföra ett brett spektrum av olika uppgifter, allt ifrån direkt farliga, som underjordisk gruvdrift och sanering av havererade kärnreaktorer, till alldagliga och tråkiga, som dammsugning och gräsklippning. På samma sätt som en människa behöver använda sina sinnen och sitt medvetande för att hantera vardagen, måste alla typer av robotar ha en viss medvetenhet för att kunna utföra sina uppgifter. Det krävs bland annat att robotarna kan uppfatta och förstå sin arbetsmiljö.

I den här avhandlingen behandlas ett antal delar av två stycken övergripande forskningsproblem som är relaterade till detta. Det första forskningsproblemet kallas för samtidig positionering och kartering, vilket på engelska heter Simultaneous Localization and Mapping och förkortas SLAM. Det andra forskningsproblemet kallas för målföljning.

SLAM-problemet går ut på att låta roboten skapa en karta av ett område, och samtidigt som kartan skapas positionera sig i den. Exakt vad som menas med karta i det här sammanhanget varierar beroende på robotens specifika arbetsuppgift. Exempelvis kan det, för en inomhusrobot, röra sig om en virtuell modell av var golv, väggar och möbler finns i ett hus. En oundviklig del av SLAM-problemet är att roboten hela tiden gör små fel, vilket påverkar kartan som skapas, samt hur väl roboten kan positionera sig. Enskilda fel har inte särskilt stor inverkan, men om felen ackumuleras under en längre tid kan det leda till att kartan förvrängs, eller att roboten helt enkelt inte kan finna sin position i kartan.

Ett sätt att undvika att så sker är att utrusta roboten med en funktion vilken gör det möjligt för roboten att känna igen platser som den har besökt tidigare, vilket kallas platsigenkänning. När roboten känner igen en plats kan den jämföra med vad kartan och positionen säger. Om kartan och positionen inte säger att roboten är tillbaka på en plats som tidigare besökts kan denna diskrepans korrigeras. Resultatet är en karta och en position som bättre representerar verkligheten. I den här avhandlingen har platsigenkänning studerats för robotar som är utrustade med laserscanners, och en funktion för platsigenkänning har skapats. I en serie experiment har det visats att funktionen kan känna igen platser såväl inomhus i kontorsmiljö, som utomhus i stadsmiljö. Det har även visats att funktionens egenskaper jämför sig väl med tidigare arbete på området.

Den resulterande SLAM-kartan bör av naturliga skäl endast innehålla stationära föremål. Vår värld innehåller dock även rörliga föremål, och för att en robot ska kunna arbeta på ett säkert sätt måste den även hålla reda på alla rörliga föremål som finns i dess närhet. Det andra forskningsproblemet som behandlats i avhandlingen, målföljning, går ut på att utrusta roboten med funktioner som gör det möjligt för den att hålla reda på var de rörliga målen är, samt vart de är på väg att röra sig. Exempelvis kan den här typen av funktioner användas till att hålla reda på fotgängare, cyklister och bilar i en stadsmiljö.

Tidigare har forskningen inom målföljning varit fokuserad på så kallade punktmål. Vid följning av punktmål kan följningsproblemet sägas ha två delar: den ena är att räkna ut hur många rörliga mål det finns, den andra är att räkna ut var varje enskilt mål befinner sig, samt vart det är på väg.

Här har fokus istället legat på följning av vad som kallas för utsträckta mål, en typ av mål som rönt ökande uppmärksamhet i forskningsvärlden de senaste fem till tio åren. Med utsträckta mål får följningsproblemet en tredje del: att för varje enskilt mål räkna ut storleken och formen på målet, det vill säga den spatiala utsträckningen. Att känna till utsträckningen på de rörliga målen är viktigt exempelvis för en robot som ska ta sig genom ett rum där många person befinner sig. För att göra det krävs att roboten rör sig nära personerna, utan att för den skull krocka med någon. Att lösa detta på ett bra sätt kräver att roboten har kunskap inte bara om var personerna befinner sig, utan även hur mycket plats de tar upp.

I avhandlingen har ett antal aspekter av följning av utsträckta mål studerats. En viktig och komplicerande aspekt av följning av såväl punktmål, som utsträckta mål, är att roboten på förhand inte vet hur många mål som finns i dess närhet. En funktion för att hantera osäkerheterna kring antalet mål som finns, samt osäkerheterna kring var varje mål befinner sig, har implementerats.

I många situationer är det nödvändigt att kunna prediktera, eller förutsäga, var de olika målen kommer att befinna sig i den närmaste framtiden. Det kan exempelvis röra sig om en robot som ska köra genom en vägkorsning, och då måste undvika att krocka med övrig trafik. För detta ändamål har en prediktionsfunktion tagits fram.

När ett större antal mål rör sig i robotens närhet kan det bli svårt att följa varje enskilt mål. Istället kan roboten följa grupper av mål. Det blir då nödvändigt att hålla reda på vad som sker när mål lämnar gruppen, eller nya mål ansluter till gruppen. Fritt översatt från engelska till svenska kan dessa två händelser kallas för målproduktion och målkombination. Funktioner för att hantera produktion och kombination av utsträckta mål har tagits fram.

För att roboten ska kunna beräkna ett måls spatiala utsträckning krävs modeller för formen på målen. När laserscanners används kan formen på en bil sägas vara approximativt rektangulär, och formen på en person kan sägas vara approximativt elliptisk. Beräkning av storleken på rektangulära och elliptiska mål har studerats för robotar utrustade med laserscanners.

Målföljningsfunktionerna som nämnts ovan har utvärderats med hjälp av såväl simulerade data, som experimentella data insamlade med laserscanners. Resultaten visar att det arbete som har utförts jämför sig väl med tidigare arbete på området.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2012. , 96 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1476
National Category
Electrical Engineering, Electronic Engineering, Information Engineering Signal Processing
Identifiers
URN: urn:nbn:se:liu:diva-82348ISBN: 978-91-7519-796-8 (print)OAI: oai:DiVA.org:liu-82348DiVA: diva2:558084
Public defence
2012-11-09, Sal Visionen, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Projects
CADICSETTCUAS
Funder
Swedish Research Council
Available from: 2012-10-15 Created: 2012-10-01 Last updated: 2014-03-27Bibliographically approved
List of papers
1. Learning to Close Loops from Range Data
Open this publication in new window or tab >>Learning to Close Loops from Range Data
2011 (English)In: The international journal of robotics research, ISSN 0278-3649, E-ISSN 1741-3176, Vol. 30, no 14, 1728-1754 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we address the loop closure detection problem in simultaneous localization and mapping (SLAM), and present a method for solving the problem using pairwise comparison of point clouds in both two and three dimensions. The point clouds are mathematically described using features that capture important geometric and statistical properties. The features are used as input to the machine learning algorithm AdaBoost, which is used to build a non-linear classifier capable of detecting loop closure from pairs of point clouds. Vantage point dependency in the detection process is eliminated by only using rotation invariant features, thus loop closure can be detected from an arbitrary direction. The classifier is evaluated using publicly available data, and is shown to generalize well between environments. Detection rates of 66%, 63% and 53% for 0% false alarm rate are achieved for 2D outdoor data, 3D outdoor data and 3D indoor data, respectively. In both two and three dimensions, experiments are performed using publicly available data, showing that the proposed algorithm compares favourably with related work.

Place, publisher, year, edition, pages
Sage Publications, 2011
Keyword
Place recognition, Loop closure, Laser, SLAM, Robotics, Learning
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-74163 (URN)10.1177/0278364911405086 (DOI)000298258500005 ()
Available from: 2012-01-20 Created: 2012-01-20 Last updated: 2017-12-08
2. Extended Target Tracking Using a Gaussian-Mixture PHD Filter
Open this publication in new window or tab >>Extended Target Tracking Using a Gaussian-Mixture PHD Filter
2012 (English)In: IEEE Transactions on Aerospace and Electronic Systems, ISSN 0018-9251, E-ISSN 1557-9603, Vol. 48, no 4, 3268-3286 p.Article in journal (Refereed) Published
Abstract [en]

This paper presents a Gaussian-mixture implementation of the phd filter for tracking extended targets. The exact filter requires processing of all possible measurement set partitions, which is generally infeasible to implement. A method is proposed for limiting the number of considered partitions and possible alternatives are discussed. The implementation is used on simulated data and in experiments with real laser data, and the advantage of the filter is illustrated. Suitable remedies are given to handle spatially close targets and target occlusion.

Keyword
Target tracking, Extended target, PHD filter, Random set, Gaussian-mixture, Laser sensor
National Category
Signal Processing Control Engineering
Identifiers
urn:nbn:se:liu:diva-71866 (URN)10.1109/TAES.2012.6324703 (DOI)000309865600030 ()
Projects
CADICSETTCUAS
Funder
Swedish Foundation for Strategic Research Swedish Research Council
Available from: 2012-10-01 Created: 2011-11-08 Last updated: 2017-12-08Bibliographically approved
3. Tracking Rectangular and Elliptical Extended Targets Using Laser Measurements
Open this publication in new window or tab >>Tracking Rectangular and Elliptical Extended Targets Using Laser Measurements
2011 (English)In: Proceedings of the 14th International Conference on Information Fusion, 2011, 592-599 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper considers tracking of extended targets using data from laser range sensors. Two types of extended target shapes are considered, rectangular and elliptical, and a method to compute predicted measurements and corresponding innovation covariances is suggested. The proposed method can easily be integrated into any tracking framework that relies on the use of an extended Kalman filter. Here, it is used together with a recently proposed Gaussian mixture probability hypothesis density (GM-PHD) filter for extended target tracking, which enables estimation of not only position, orientation, and size of the extended targets, but also estimation of extended target type (i.e. rectangular or elliptical). In both simulations and experiments using laser data, the versatility of the proposed tracking framework is shown. In addition, a simple measure to evaluate the extended target tracking results is suggested.

Keyword
Multiple target tracking, Extended targets, Probability hypothesis density, PHD, Gaussian mixture, Kalman filter, Laser range data, Rectangle, Ellipse, Intersection over union
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-70031 (URN)978-1-4577-0267-9 (ISBN)
Conference
14th International Conference on Information Fusion, Chicago, IL, USA, 5-8 July, 2011
Funder
Swedish Research Council
Note

©2011 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. Karl Granström, Christian Lundquist and Umut Orguner, Tracking Rectangular and Elliptical Extended Targets Using Laser Measurements, 2011, Proceedings of the 14th International Conference on Information Fusion, 592-599.

Available from: 2011-08-23 Created: 2011-08-15 Last updated: 2014-03-27Bibliographically approved
4. A PHD Filter for Tracking Multiple Extended Targets using Random Matrices
Open this publication in new window or tab >>A PHD Filter for Tracking Multiple Extended Targets using Random Matrices
2012 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 60, no 11, 5657-5671 p.Article in journal (Refereed) Published
Abstract [en]

This paper presents a random set based approach to tracking of an unknown number of extended targets, in the presence of clutter measurements and missed detections, where the targets extensions are modeled as random matrices. For this purpose, the random matrix framework developed recently by Koch et al. is adapted into the extended target PHD framework, resulting in the Gaussian inverse Wishart PHD (GIW-PHD) filter. A suitable multiple target likelihood is derived, and the main filter recursion is presented along with the necessary assumptions and approximations. The particularly challenging case of close extended targets is addressed with practical measurement clustering algorithms. The capabilities and limitations of the resulting extended target tracking framework are illustrated both in simulations and in experiments based on laser scans.

Place, publisher, year, edition, pages
IEEE Signal Processing Society, 2012
Keyword
Gaussian distribution, PHD filter, Target tracking, Extended target, Inverse Wishart distribution, Laser sensor, Occlusion, Probability of detection, Random matrix, Random set
National Category
Signal Processing Control Engineering
Identifiers
urn:nbn:se:liu:diva-82000 (URN)10.1109/TSP.2012.2212888 (DOI)000310139900004 ()
Projects
CADICSETTCUAS
Funder
Swedish Research Council, 621-2010-4301Swedish Foundation for Strategic Research
Note

funding agencies|Swedish Research Council|621-2010-4301|Foundation for Strategic Research (SSF)||

Available from: 2012-10-01 Created: 2012-09-27 Last updated: 2017-12-07Bibliographically approved
5. Estimation and Maintenance of Measurement Rates for Multiple Extended Target Tracking
Open this publication in new window or tab >>Estimation and Maintenance of Measurement Rates for Multiple Extended Target Tracking
2012 (English)In: Proceedings of the International Conference on Information Fusion (FUSION), IEEE Press, 2012, 2170-2176 p.Conference paper, Published paper (Refereed)
Abstract [en]

In Gilholm et al.'s extended target model, the number of measurements generated by a target is Poisson distributed with measurement rate γ. Practical use of this extended target model in multiple extended target tracking algorithms requires a good estimate of γ. In this paper, we first give a Bayesian recursion for estimating γ using the well-known conjugate prior Gamma-distribution. In multiple extended target tracking, consideration of different measurement set associations to a single target makes Gamma-mixtures arise naturally. This causes a need for mixture reduction, and we consider the reduction of Gamma-mixtures by means of merging. Analytical minimization of the Kullback-Leibler divergence is used to compute the single Gamma distribution that best approximates a weighted sum of Gamma distributions. Results from simulations show the merits of the presented multiple target measurement-rate estimator. The Bayesian recursion and presented reduction algorithm have important implications for multiple extended target tracking, e.g. using the implementations of the extended target PHD filter.

Place, publisher, year, edition, pages
IEEE Press, 2012
National Category
Signal Processing
Identifiers
urn:nbn:se:liu:diva-82001 (URN)978-0-9824438-4-2 (ISBN)978-1-4673-0417-7 (ISBN)
Conference
15th International Conference on Information Fusion, July 9-12, Singapore
Projects
CADICSETTCUAS
Available from: 2012-10-01 Created: 2012-09-27 Last updated: 2014-03-27Bibliographically approved
6. On the Reduction of Gaussian inverse Wishart Mixtures
Open this publication in new window or tab >>On the Reduction of Gaussian inverse Wishart Mixtures
2012 (English)In: Proceedings of the International Conference on Information Fusion (FUSION), IEEE Press, 2012, 2162-2169 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper presents an algorithm for reduction of Gaussian inverse Wishart mixtures. Sums of an arbitrary number of mixture components are approximated with single components by analytically minimizing the Kullback-Leibler divergence. The Kullback-Leibler difference is used as a criterion for deciding whether or not two components should be merged, and a simple reduction algorithm is given. The reduction algorithm is tested in simulation examples in both one and two dimensions. The results presented in the paper are useful in extended target tracking using the random matrix framework.

Place, publisher, year, edition, pages
IEEE Press, 2012
National Category
Signal Processing
Identifiers
urn:nbn:se:liu:diva-82002 (URN)978-0-9824438-4-2 (ISBN)978-1-4673-0417-7 (ISBN)
Conference
15th International Conference on Information Fusion, July 9-12, Singapore
Projects
CADICSETTCUAS
Available from: 2012-10-01 Created: 2012-09-27 Last updated: 2014-03-27Bibliographically approved
7. A New Prediction for Extended Targets with Random Matrices
Open this publication in new window or tab >>A New Prediction for Extended Targets with Random Matrices
2012 (English)Manuscript (preprint) (Other academic)
Abstract [en]

This paper presents a new prediction update for extended targets whose extensions are modeled as random matrices. The prediction is based on several minimizations of the Kullback-Leibler divergence and allows for a kinematic state dependent transformation of the target extension. The results show that the extension prediction is a significant improvement over the previous work carried out on the topic.

National Category
Signal Processing Control Engineering
Identifiers
urn:nbn:se:liu:diva-82004 (URN)
Projects
CADICSETTCUAS
Available from: 2012-09-27 Created: 2012-09-27 Last updated: 2014-03-27Bibliographically approved
8. On Spawning and Combination of Extended/Group Targets Modeled with Random Matrices
Open this publication in new window or tab >>On Spawning and Combination of Extended/Group Targets Modeled with Random Matrices
2013 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 61, no 3, 678-692 p.Article in journal (Refereed) Published
Abstract [en]

In extended/group target tracking, where the extensions of the targets are estimated, target spawning and combination events might have significant implications on the extensions. This paper investigates target spawning and combination events for the case that the target extensions are modeled in a random matrix framework. The paper proposes functions that should be provided by the tracking filter in such a scenario. The results, which are obtained by a gamma Gaussian inverse Wishart implementation of an extended target probability hypothesis density filter, confirms that the proposed functions improve the performance of the tracking filter for spawning and combination events.

Place, publisher, year, edition, pages
IEEE Signal Processing Society, 2013
Keyword
Extended target, Random matrix, Kullback-Leibler divergence, Target spawning, Target combination
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-82005 (URN)10.1109/TSP.2012.2230171 (DOI)000314719100013 ()
Projects
CADICSETTCUAS
Funder
Swedish Research Council, 621-2010-4301Swedish Foundation for Strategic Research
Note

Funding Agencies|Swedish Research Council|621-2010-4301|Swedish Foundation for Strategic Research (SSF)||

Available from: 2012-09-27 Created: 2012-09-27 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

Extended target tracking using PHD filters(7352 kB)1335 downloads
File information
File name FULLTEXT01.pdfFile size 7352 kBChecksum SHA-512
b8970d1573fd85e28872b687cfe52df5468a35c00fd04dd9d847e1e79c2f24fac4a17ad1a7c76461cbc7df6b90a6e414bbf3286f7823cd466257e038af7c783b
Type fulltextMimetype application/pdf
omslag(173 kB)193 downloads
File information
File name COVER01.pdfFile size 173 kBChecksum SHA-512
90d8a8d394e9cc45033a2ba7b513877a89c9ef46f7e21ed4ada3d52e91824b13cd3f9bf9d1d5c8f028c0203019f7c50d3f9d20f7560b6c6c90b44d1ebd33f0e8
Type coverMimetype application/pdf

Search in DiVA

By author/editor
Granström, Karl
By organisation
Automatic ControlThe Institute of Technology
Electrical Engineering, Electronic Engineering, Information EngineeringSignal Processing

Search outside of DiVA

GoogleGoogle Scholar
Total: 1335 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 2631 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf