Computational complexity analysis of two target tracking algorithms

Abstract

İki hedef takibi algoritmasının işlem karmaşıklığı analizlerinin yapılması bu tezin ana konusudur. Bunlar Gholson ve Moose'un önerdiği ` Genişletilmiş Kalman Filtresi ` ve Demirbaş'ın önerdiği ` Çoklu Hipotez Karşılaştırması ile Hareket Halinde Hedef Takibi ` algoritmalarıdır. İlk algoritmaya sabit uzunlukta düzgünleştirme uygulanmış ve ikinci algoritma için bir gerçekleştirme metodu önerilmiştir. Her iki algoritmanın işlem karmaşıklığı ve hafıza gereksinimleri çıkarılmış ve sonuçlar karşılaştırılmıştır. Son olarak da, algoritmaların hedef takibi performansları ve hızları yapılan benzetimlerde gözlemlenmiştir. Anahtar Kelimeler : Kalman Filtre, Genişletilmiş Kalman Filtre, Düzgünleştirme, Hipotez Karşılaştırması, Viterbi Çözücü, Hedef Takibi, Radar. iv

The main subject of this thesis is to evaluate computational complexity of two target tracking algorithms. These are smoothed extension of` Extended Kalman Filter Algorithm ` of Gholson and Moose and ` Maneuvering Target Tracking With Multiple Hypothesis Testing ` algorithm of Demirbaş. An implementation method is proposed for the second one. Computational complexities of two algorithms are evaluated. For each algorithm, total number of operations and memory requirements are derived and then they are compared. Finally simulation results are presented to evaluate their tracking performances and implementation speeds in terms of CPU cycles. Keywords : Kalman Filter, Extended Kalman Filter, Smoothing, Hypothesis Testing, Viterbi Decoding, Target Tracking, Radar. m