5
con la tecnica di filtraggio IMM. L’integrazione è stata effettuata, e si è quindi pervenuti
ad un unico algoritmo (IM3HT = IMM + MHT) che conserva le caratteristiche positive di
entrambi. Il risultato ottenuto presenta un contenuto innovativo, non essendo stato ancora
realizzato né tanto meno proposto in letteratura.
Inoltre l’algoritmo è stato codificato ed integrato al software già esistente e poi
testato, insieme con l’MHT, su alcuni scenari di prova. Sono stati considerati sette casi
con velocità costanti in modulo e con accelerazoni angolari via via crescenti, mettendo in
luce la superiorità dell’IM3HT.
La tesi è così articolata:
• Nel capitolo 1 viene introdotto l’argomento del tracking;
• Nel capitolo 2 sono descritti gli algoritmi di correlazione;
• Nel capitolo 3 sono analizzate le tecniche di filtraggio;
• Nel capitolo 4 viene descritto l’algoritmo di tracking concepito (IM3HT),
vengono illustrate le strutture dati usate per l’implementazione e viene
illustrato il programma di software che si è realizzato;
• Il capitolo 5 comprende i risultati delle simulazioni su diversi scenari,
applicati sia all’IM3HT che al solo MHT;
• Nel capitolo 6 vengono presentate le considerazioni conclusive.
• In appendice vengono presentati i listati delle principali funzioni che
compongono il programma di simulazione dell’IM3HT.
6
Capitolo 1
Il tracking
In un problema di tracking (tracciamento) un radar (o più radar inseriti in una rete
di sorveglianza, ed in tal caso il problema diventa tracking multiradar) scandisce
periodicamente un settore volumetrico di spazio aereo sotto sorveglianza e fornisce delle
detezioni (tecnicamente dette plots) che indicano la presenza di un bersaglio (detto
target). In più, il radar misura le coordinate di ogni target rilevato. Le coordinate
misurate sono affette da rumore, che è modellato come Gaussiano, a media zero e con una
varianza che è indipendente da scansione a scansione. Quando il radar ripete la scansione
del volume, si accumulano nuovi plots. La sequenza dei plots che si presume
appartengano allo stesso target, può essere elaborata in un filtro adatto a limitare il
rumore delle misure che andranno a formare la traiettoria del bersaglio.
In realtà, il tracking è complicato da varie cause:
• nello stesso volume sono presenti molti targets, i quali possono anche volare
molto vicini;
• la probabilità di detezione del radar è minore di uno, così il target può non
essere rilevato;
• la probabilità di falso allarme è maggiore di zero, così falsi plots (dovuti al
rumore del sistema, disturbi naturali e/o intenzionali) possono aggiungersi a
quelli veri;
• i bersagli possono manovrare.
Un algoritmo di tracking dovrebbe essere in grado di tenere conto di tutti questi
problemi. A questo fine è possibile individuare due fasi principali nella funzione di
tracking: la correlazione ed il filtraggio.
7
1.1 CORRELAZIONE MISURA-TRACCIA
La correlazione si riferisce alle tecniche che consentono di associare gli echi
ricevuti dal radar alle tracce, già esistenti o in via di inizializzazione.
Questa operazione è cruciale per il buon funzionamento del tracking, ed è
particolarmente insidiosa, poiché in condizioni di reale funzionamento la probabilità di
ricevere l’eco di un bersaglio è minore di uno e quella di ricevere un falso allarme è
maggiore di zero. Quindi, la correlazione deve generalmente risolvere
contemporaneamente due problemi: il primo è quello di discernere, fra i numerosi ritorni
radar ad una stessa scansione, quali sono i falsi allarmi e quali sono le misure prodotte
da bersagli reali; il secondo è quello di associare correttamente le misure radar ai
bersagli che le hanno generate (nel caso realistico di scenari che presentino più bersagli
nello stesso campo di azione del radar).
EVOLUZIONE ALGORITMICA: L’algoritmo di correlazione più semplice è il
Nearest Neighbor (NN), che associa ad ogni traccia la misura più vicina (in senso
statistico).
Questo algoritmo è tuttora il più diffuso ed utilizzato nella maggior parte dei
sistemi di tracciamento oggi in uso: ciò è dovuto alla sua semplicità ed ad un costo
computazionale relativamente poco oneroso.
Per contro, le sue prestazioni non sempre sono soddisfacenti, a causa della facilità
con cui incorre in errore, specie in scenari densi, con molti falsi allarmi e bersagli in
manovra.
Più recente è l’algoritmo Joint Probabilistic Data Association (JPDA), che
migliora decisamente le prestazioni rispetto al NN, in quanto ad ogni scansione
8
temporale non viene scelta una particolare misura ma, una media pesata di tutte le misure
che cadono in una determinata regione di interesse.
L’approccio ottimo al problema della correlazione [12] è l’algoritmo MHT
(Multiple Hypothesis Tracking), che genera tutte le possibili ipotesi di associazione
traccia-misura e rimanda la decisione definitiva per un certo numero di scansioni radar,
in modo da disporre di maggiori informazioni per effettuare la scelta.
All’aumentare del ritardo sulla decisione, aumenta il carico computazionale
dell’algoritmo, in quanto le ipotesi si ramificano in modo combinatorio: per questo
motivo l’algoritmo è ancora oggetto di studio in ambito scientifico al fine di pervenire a
soluzioni sub-ottime compatibili almeno con le risorse di calcolo disponibili sui
calcolatori odierni (es.: qualche centinaio di Mflops).
1.2 FILTRAGGIO DELLA TRACCIA
Una volta realizzata l’associazione della misura alla traccia, il filtraggio ha il
compito di ottenere la migliore stima dello stato dinamico della traccia utilizzando la
nuova misura.
Ad ogni scansione radar si effettua la predizione dello stato cinematico del
bersaglio alla scansione successiva, estrapolando posizione e velocità mediante un
modello dinamico lineare del moto del bersaglio.
A questo punto, con l’arrivo delle nuove misure, il filtraggio ha il compito di
aggiornare e migliorare la stima dello stato dinamico fornita dalla predizione, valutando
l’errore tra la posizione misurata dal radar e la posizione estrapolata.
Il termine di errore, opportunamente pesato per il guadagno del filtro, viene
utilizzato per correggere lo stato cinematico della traccia.
9
Il guadagno del filtro è un coefficiente che tiene conto dell’errore con cui è noto
lo stato cinematico attuale della traccia e dell’errore associato alla nuova misura
acquisita. In altre parole, quanto più l’errore di misura è piccolo rispetto all’incertezza
sullo stato cinematico, tanto più il guadagno è alto per dare maggiore importanza alla
misura; quanto più l’errore di misura è grande rispetto all’incertezza sullo stato, tanto più
il guadagno è piccolo per dare più confidenza alla predizione. Lo stato cinematico, così
aggiornato, costituisce l’uscita del filtro.
EVOLUZIONE ALGORITMICA: il filtro base è quello di Kalman, che fornisce la
stima ottima dello stato nel caso in cui il modello dinamico del bersaglio sia noto e
lineare ed il rumore di forzamento e gli errori di misura abbiano densità di probabilità
Gaussiana.
In realtà, se l’ipotesi di modello lineare può essere accettata, tale modello
dinamico non è noto e varia nel tempo: per questo motivo e per la sua capacità di
adattarsi al modello reale del bersaglio, risulta di particolare interesse l’algoritmo IMM
( Interacting Multiple Model ), in cui vengono utilizzati un certo numero di filtri di
Kalman, ciascuno adattato ad uno specifico modello dinamico per il moto del bersaglio
in osservazione, i quali interagiscono fra di loro per aumentare l’accuratezza della stima.
10
Capitolo 2
Algoritmi di correlazione
La fase più critica di un algoritmo di tracking è la correlazione, cioè
l’associazione degli echi ricevuti dal radar ad una determinata scansione con le tracce in
quel momento ipotizzate.
Gli algoritmi di correlazione si possono suddividere in due diverse categorie: si
parla di algoritmo hard o non Bayesiano quando ad una traccia viene associata soltanto
la misura più probabile, nonostante che le eventuali altre misure associabili abbiano
probabilità non nulle. Invece un algoritmo si dice soft o Bayesiano quando le
associazioni non sono univoche, ovvero quando una traccia viene aggiornata usando più
misure, ognuna delle quali viene pesata a seconda della probabilità di essere quella
corretta.
Una seconda suddivisione viene fatta tra algoritmi che ritardano la decisione da
prendere per alcune scansioni in modo di avere maggiori informazioni (in questo caso si
parla di algoritmi multi-scan) e fra metodi che fanno la loro scelta nella stessa scansione
in cui ricevono le misure (metodi 0-scan).
Le principali tecniche di correlazione sono:
Nearest Neighbor (NN),
Joint Probabilistic Data Association (JPDA) e,
Multiple Hypothesis Tracking (MHT).
Delle prime due tecniche si darà un breve cenno nel paragrafo 2.1, mentre l’MHT
verrà illustrato diffusamente nel paragrafo 2.2. Esse si possono suddividere fra le varie
categorie, come mostrato in tabella 2-1:
11
Hard Soft
0-scan NN JPDA
multi-scan MHT
Tabella 2-1 Quadro sinottico degli algoritmi di correlazione
Lo scopo di questa tesi è di colmare la lacuna evidenziata nella tabella, con un
nuovo algoritmo: IM3HT, che unisce la caratteristica multi-scan dell’MHT, con l’aspetto
di associazione soft, proprio dell’IMM.
La correlazione vera e propria è generalmente preceduta da una tecnica che
consente di limitare il numero di misure che è possibile associare con ogni traccia: il
gating. Questa tecnica consiste nel definire una regione nello spazio in cui si presume
debba cadere il nuovo eco del bersaglio. Questa zona, detta regione di validità
(validation gate), viene centrata intorno alla posizione predetta dal filtro alla scansione
precedente.
La forma della regione di validità è rettangolare o ellittica, in quest’ultimo caso è
definita dalla seguente equazione:
nT S-1 n ≤ g2 (2-1)
dove:
n è l’innovazione, cioè la differenza tra la posizione misurata e
quella
predetta,
S è la matrice di covarianza dell’innovazione,
12
g è una soglia prefissata.
L’algoritmo di correlazione sarà quindi applicato solo alle misure che cadono
nella regione di validità della traccia.
Un’altra tecnica, molto usata con algoritmi come MHT e JPDA che generano un
gran numero di ipotesi di associazione traccia-misura, è quella del raggruppamento
(clustering) delle tracce che hanno misure contese fra loro, ovvero di quelle le cui
regioni di validità hanno intersezioni che comprendono almeno una misura; in questo
modo si suddivide il problema in sotto-problemi meno onerosi da risolvere.
13
1
3
2
4
56
7
8
9
10
11
A
B
C
D
E
F
Figura 2-1 Una situazione in cui è necessaria una logica di correlazione.
14
Nella figura 2-1 si può vedere un esempio di come le regioni di validità
influenzino il tracking: solo nove delle undici misure cadono nei gate delle varie tracce.
Queste ultime vengono raggruppate in tre cluster: un primo gruppo comprende le tracce
A e B, un secondo le tracce D, E, F, un terzo la sola traccia C.
15
2.1 Cenni su tecniche di correlazione a decisione immediata
Le tecniche di correlazione a decisione immediata (0-scan) più utilizzate sono
due: Nearest Neighbor e Joint Probabilistic Data Association. Ne diamo qui un breve
cenno.
Nearest Neighbor (NN)
La logica di correlazione Nearest Neighbor (NN) [1, 2] è una logica hard, cioè è
una logica in cui si associa ad ogni traccia un’unica misura (se questa è stata ricevuta).
L’associazione è fatta molto semplicemente: si assegna ad ogni traccia la misura
più vicina (in senso statistico: ovvero si tiene conto della distanza fra predizione e
misura). Ovviamente ciò comporta una notevole probabilità di sbagliare con conseguenze
negative per il filtraggio (il filtro va a regime più lentamente oppure, nel caso peggiore,
diverge e perde il bersaglio).
Nel caso più generale, in cui si hanno diversi echi contesi da più tracce, ci si
trova davanti ad un classico problema di ricerca operativa: bisogna selezionare l’insieme
di coppie traccia-misura che minimizza la distanza statistica complessiva.
Un metodo rapido potrebbe essere quello di fare una graduatoria di queste
associazioni e scegliere la migliore; alle altre tracce verranno assegnati i successivi
migliori echi correlanti. Si tenga presente però che questa soluzione potrebbe molto
facilmente non essere la migliore. Inoltre sorgono problemi di calcolo legati
all’enumerazione di tutte le associazioni.
16
Joint Probabilistic Data Association (JPDA)
Il Joint Probabilistic Data Association (JPDA) [2, 4, 5, 10, 11] è un algoritmo di
correlazione di tipo 0-scan, in quanto il problema dell’associazione viene risolto nella
stessa scansione in cui vengono ricevute le misure.
In questo algoritmo le associazioni delle misure alle tracce vengono effettuate in
maniera soft o bayesiana, cioè ogni traccia non viene aggiornata considerando corretta
soltanto un’unica misura, ma tenendo conto, in maniera probabilistica, di tutte le misure
che cadono nelle regioni di validità delle tracce.
Il JPDA segue una logica target-oriented ovvero ipotizza che ogni misura
provenga solamente da una traccia già confermata o da un falso allarme e non da un nuovo
bersaglio precedentemente non rilevato; cioè si tratta di un algoritmo che non è in grado
di inizializzare il tracciamento di nuovi bersagli.
17
2.2 Correlazione a ipotesi multiple (MHT: Multiple Hypothesis Tracking)
Il Multiple Hypothesis Tracking (MHT) [2, 4, 8, 9] è un algoritmo di
correlazione di tipo multi-scan, in quanto il problema dell’associazione delle misure alle
tracce non viene risolto nella stessa scansione in cui le misure vengono ricevute ma è
ritardato di un certo numero di scansioni (approssimazione N-scan) in modo da portare
avanti una serie di ipotesi che saranno risolte utilizzando le informazioni rese disponibili
dalle scansioni successive. Se in particolare, il problema dell’assegnazione delle misure
alle tracce venisse risolto considerando tutte le possibili combinazioni delle misure
ricevute dall’istante iniziale a quello corrente e tutti i possibili modelli dinamici dei
bersagli, si otterrebbe la soluzione ottima. Per ovvi problemi legati all’enorme carico
computazionale che una soluzione del genere richiederebbe, si ricorre a metodi sub-
ottimi (per l’appunto approssimazione N-scan) che mostrano prestazioni solo
leggermente inferiori al caso ottimo per valori di N inferiori od al massimo pari a 3.
L’approssimazione N-scan può in alcuni casi non essere sufficiente a ridurre
adeguatamente il carico computazionale, rendendo necessaria l’adozione di tecniche di
riduzione del numero di ipotesi generate allo scopo di ottenere prestazioni in tempo
reale. Alcune di queste tecniche sono patrimonio comune di tutti gli algoritmi di tracking
realizzati finora, come ad esempio il gating che considera per l’associazione solo le
misure che cadono all’interno di una finestra centrata intorno alla posizione predetta
della traccia. Altre tecniche sono più specifiche della logica MHT, come ad esempio il
clustering.
Si danno ora una serie di definizioni che verranno utilizzate estesamente nel
seguito. Nelle figure 2.2-1, 2.2-2 e 2.2-3 se ne fornisce anche una illustrazione grafica.
18
Si definisce ipotesi di traccia una possibile evoluzione cinematica del bersaglio
ottenuta ipotizzando ad ogni scansione radar un modello cinematico del bersaglio e
l’associazione con un misura ricevuta nella scansione stessa. Un’ipotesi di traccia può
essere rappresentata graficamente come una successione di rami di un albero che
partendo dalla radice arriva ad una foglia (nodo terminale). Ogni ramo ipotizza un
determinato modello cinematico del bersaglio e l’associazione con una determinata
misura ricevuto alla scansione corrispondente. La radice dell’albero rappresenta la
nascita della traccia, sebbene nel caso di approssimazione N-scan, è sufficiente
mantenere solo la parte di albero relativa alle ultime N scansioni, cioè gli ultimi N livelli
dell’albero: la radice corrisponde allora all’ultima associazione definitiva fatta con una
misura per il bersaglio in questione.
Si definisce albero di traccia l’insieme delle ipotesi di traccia per un
determinato bersaglio. Ad ogni bersaglio ipotizzato viene quindi associato un albero di
traccia.
Si definisce ipotesi globale una ipotesi che individua l’origine di ciascuna misura
ricevuta nelle ultime N scansioni. Ricorrendo alla schematizzazione in alberi, l’ipotesi
globale è una combinazione ammissibile di ipotesi di traccia, ottenuta prendendo una sola
ipotesi per ciascun albero di traccia. La condizione di ammissibilità deriva dall’ipotesi
che un bersaglio fornisca al più una misura per ogni scansione, un’ipotesi globale è
quindi ammissibile se le ipotesi di traccia che la compongono non condividono nessuna
misura.
Si definisce Track Likelihood (TL) il valore numerico che esprime la
verosimiglianza di una ipotesi di traccia.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
