A comparative study of multiple hypothesis and Viterbi based track stitching

Abstract

The track stitching problem can be divided into two tasks, namely target tracking to create track fragments, and track stitching to stitch the resulting track fragments together. In this study a tracking algorithm is developed to track multiple targets and to create track fragments. The track fragments are generated through the use of a Markov model where a target can be assumed to be in an occluded or a visible state. The track fragments are modelled as nodes in a state diagram, which in turn is used to create a time dependent trellis diagram. The columns in the trellis diagram represents the time when a particular track fragment appeared while the nodes represent certain kinematic features of the track fragments themselves. This trellis is then solved using a sequential Viterbi algorithm and using each node exactly once, to obtain the most viable track fragment to track fragment associations. Each solution path through the trellis diagram represents a set of track fragments which where created by a specific target. Results are presented by simulating multiple crossing targets with fragmented tracks. It is shown that the algorithm successfully stitches track fragments together in the presence of false tracks caused by noisy observations. Further evaluation of the performance of the algorithm is presented with a number of scenarios where increasingly ambiguous track fragment to track fragment associations exist. The sequential Viterbi track stitching algorithm is also compared against a multiple hypothesis track fragment stitching algorithm. This algorithm was extended from the classic hypothesis based multiple hypothesis tracking algorithm (MHT) by, performing track fragment to track associations instead of observation to track associations. In these comparisons, the code used to run the simulations have been optimised and vectorised as far as possible to ensure a fair comparison. It is shown that the Viterbi based track stitching algorithm performs somewhat better that the multiple hypothesis track stitching algorithm for similar execution times. The Viterbi based track stitching algorithm is also shown to produce more consistently acceptable results.Die volgersegmentsamevoegingprobleem kan verdeel word in twee hooftake, naamlik teikenvolging, waar die volgersegmente geskep word en volgersegmentstikking, waar die geskepte segmente met mekaar geassosieer word. In hierdie studie word ?n volgeraloritme ontwikkel om veelvuldige teikens te volg en om volgersegmente te skep. Die volgersegmente word geskep deur gebruik te maak van ?n Markov-model waar ?n teiken in ?n versteekte of ?n sigbare toestand kan wees. Die volgersegmente word gemodelleer as nodes in ?n toestandsdiagram, wat omgeskakel word in ?n tyd-afhanklike latwerkdiagram. Die kolomme in hierdie diagram stel die tyd voor wanneer ?n spesifieke volgersegment sigbaar geword het, terwyl die nodes die volgersegmente voorstel. Hierdie latwerk diagram word dan opgelos deur gebruik te maak van ?n sekwensi?le Viterbi-algoritme waar elke node slegs een keer in die oplossing gebruik word om die mees waarskynlike paaie te verkry. Elke pad deur die diagram stel ?n groep volgersegmente voor wat deur ?n spesifieke teiken gegenereer is. Resultate word voorgel? deur veelvuldige kruisende teikens te genereer waarvan die teikenwaarnemings yl is. Daar word aangetoon dat die algoritme die volgersegmente korrek met mekaar assosieer in die teenwoordigheid van vals volgersegmente wat deur valsalarmwaarnemings veroorsaak is. Verdere evaluering, volgens die prestasie van die algoritme, word aangetoon deur ?n aantal gevalle te simuleer waar die assosiasies tussen die volger segmente meer dubbelsinning is. Die opeenvolgende Viterbi-volgersegmentstikkingalgorithme word laastens vergelyk met ?n veelvuldige-hipotese volgersegmentstikkingalgorithme wat uitgebrei is uit die hipotese-gebaseerde veelvuldige-hipotese volgeralgoritme om segment met segment te assosieer in plaas daarvan om waarnemings met volgers te assosieer. In hierdie vergelykings is die kode gebruik is om die simulasies uit te voer so ver moontlik geoptimeer om sodoende ?n eerlike vergelyking te kan tref. Die Viterbi-gebaseerde algoritme vaar ietwat beter as die veelvuldige-hipotese algoritme in gevalle waar die uitvoertye soortgelyk is. Die Viterbi-gebaseerde algoritme blyk ook meer konsekwent te wees, en lewer dus meer aanvaarbare resultate.