Tracking in high
energy physics
Alberto Pulvirenti
http://www.ct.infn.it/~pulvir/LezioniTracking.ppt
Obiettivi della ricerca moderna
 Investigare
la struttura dell’universo
microscopico
 Studiare
collisioni ad energia sempre più
alta
 …che producono sempre più particelle ad alta energia
 Strategia
sperimentale: Tracking Detectors
 Il rivelatore non “stoppa” le particelle
 La particella viene “seguita” lungo il suo percorso
2
Tracking detectors
3
Struttura a strati (“layer”) sensibili
La particella attraversa gli strati…
…e ogni strato “prende nota” del punto in cui è stato attraversato
Output finale = insiemi di punti spaziali in ogni layer
Come visualizzare le traiettorie delle
particelle?
 Metodi “visuali”
 Camere a bolle
 Camere a scintille
 Emulsioni fotografiche
 Metodi elettronici
 Rivelatori a gas
 Rivelatori a stato solido
4
Metodi “visuali” per la rivelazione di
particelle

Materiale trasparente che reagisce al passaggio di particelle
 Analisi visuale di una immagine ottenuta impressionando lastre fotografiche
5
Metodi “visuali” per la rivelazione di
particelle

… analisi laboriosa e faticosa, difficile da automatizzare al computer
6
Rivelazione di particelle con segnali
elettronici
 Rivelatori a gas
 Contatori proporzionali
 Camere a deriva
 TPC
 Rivelatori a stato solido
 Pixel detectors
 Drift detectors
 Strip detectors
7
Dal rivelatore all’algoritmo: dati di base
1.
Survey Data (o “geometria”)

2.
Calibration Constants

3.
Costanti per convertire i segnali elettrici del rivelatore in
informazione utilizzabile per l’analisi fisica
Mappatura del campo magnetico

4.
Posizione spaziale di ogni volume (sensibile o non sensibile) del
rivelatore
Fondamentale per ricostruire l’impulso della particella in base alla
curvatura della sua traiettoria
RAW DATA ( “clusters”)

I veri e propri dati sperimentali, raccolti dal rivelatore in
seguito alla collisione generata con i fasci di particelle
8
Come ricostruire la traiettoria di una
particella?
Fit dei punti generati da una particella,
usando una opportuna equazione per la traiettoria
…ma se le tracce sono tante e vicine?
Prima di ricostruire i percorsi delle particelle, bisogna sapere
QUALI punti appartengono a ciascuna particella:
PATTERN RECOGNITION PROBLEM
9
Un caso realistico…
Questo è 1/100 di quello che potrebbe succedere in ALICE.
Contate le tracce (se ci riuscite)!
10
11
What’s “tracking”?
INPUT:
Punti spaziali
TRACKING
OUTPUT:
Particelle
(impulso, PID)
Fase 1 (track recognition):
selezione dei punti (probabilmente) prodotti da una stessa particella
Fase 2 (track reconstruction):
ricostruzione delle caratteristiche
fisiche della particella
(identificazione, impulso)
Cosa significa “pattern recognition”?

Letteralmente: “riconoscimento di modelli”

Punto di partenza: “immagine”:
 Insieme di segnali o informazioni che caratterizzano
completamente un oggetto, nel contesto in cui esso viene
analizzato.
◊ NON è ristretto alle immagini visive

Due step essenziali:
1. Definizione di un set di Immagini-Modello
2. Classificazione di ogni altra Immagine dello stesso insieme
statistico secondo il Modello cui somiglia di più (se esiste).
> Definizione di “somiglianza” o “distanza” fra immagini
12
Qualche definizione più rigorosa…

Problema di “classificazione”:
 Input: un vettore di misura (“pattern”) contenente tutte le
informazioni necessarie per definire un oggetto
◊ {Xk}, k = 1, …, N
 Output: classificazione del vettore (e quindi dell’oggetto
associato) mediante una funzione di decisione:
◊ C = d({Xk})

Pattern space ( P ):
 Spazio di tutti i possibili pattern {Xk}

Obiettivo:
 Suddividere P in regioni separate, corrispondenti alle varie
classificazioni possibili…
◊ …+ una classe per “unidentified patterns”
13
Esempio 1: lettura


Per farlo, dobbiamo prima conoscere le lettere
Pattern: segni sulla carta
 “a”, “b”, “c”, etc…


Classificazione: suono associato al segno
Dalle forme delle lettere in stampatello, possiamo “intuire”
come leggere uno scritto a mano, per analogia o
somiglianza
“Nel mezzo del cammin di nostra vita
Mi ritrovai per una selva oscura…”
…ma non sempre tutto è così scontato:
‫االتحاد األوروبي يدعو شارون لوقف العمليات العسكرية في المناطق الفلسطينية ومنح محمود عباس مزيدا من‬
‫الوقت للسيطرة على المسلحين‬
14
Esempio 2: riconoscimento visivo
Cosa è questo?
…un gatto?
COMPLIMENTI!
Avete appena eseguito
un Pattern Recognition!
15
Pattern space e Feature space

16
Definizione concettuale:
 Funzione degli elementi del pattern che consente di ridurre il numero
di parametri di cui tenere conto
◊ Riduzione dell’informazione agli elementi “essenziali”

Definizione “rigorosa”:
 Base {ek} ortogonale nello spazio dei pattern che si possa scomporre
in due blocchi {e1,…, m < N }, {em+1, …, N } tali che due pattern con le
stesse componenti nei primi m (< N ) elementi sono abbastanza
simili da poter essere considerati “identici” ai fini della classificazione
da fare

Esempio:
 N punti allineati  retta di best-fit + 2 (3 o 5 parametri)
◊ Meno informazione
◊ Si mantengono solo le informazioni “importanti”.
Vantaggi delle features

Meno elementi nel vettore da classificare

Gerarchia di importanza dei parametri.

“Residui” (gli N – m elementi “secondari”)
 Criterio di valutazione di classificabilità
 Esempio dei punti allineati:
◊ stabilire se possono essere accettati come “retta” o meno
17
Tracking e pattern recognition

Pattern: sequenze di punti restituiti dal rivelatore
 Uno per ogni strato sensibile
 Problema n! – combinatorio (n = numero di strati del rivelatore)

Feature: parametri della traiettoria della particella

Classificazione: traccia finale
 Punto di produzione della particella (vertice)
 Modulo e orientamento spaziale dell’impulso iniziale
18
Complicazioni
 L’impulso
è un numero reale
 Il numero di classi è infinito
I
punti sperimentali sono tanti
 Impossibile lavorare su tutte le combinazioni possibili
 Selezione di “track candidates”  check di validità
19
Parametrizzazione della traccia

Fondamentale per la ricostruzione

5 parametri essenziali
 Posizione (3 coordinate) + Impulso (3 componenti) - 1 (perché
può essere scelto qualsiasi punto)
 Qualsiasi set di 5 parametri è matematicamente equivalente
◊ Sconsigliabili i parametri che diventano troppo grandi
• Meglio usare 1/p piuttosto che p
◊ Attenzione ai parametri che, durante il fit, presentano discontinuità
o correlazione con altri.
 La scelta corretta è sempre dipendente dalla situazione
(apparato sperimentale, range di impulso da ricostruire, …)
20
“Disturbi” nella ricostruzione
Scattering multiplo nel mezzo: formula di Moliére
 la traccia si scosta dalla forma “regolare” (potrebbe anche non essere trovabile)

2
 x 
 0.015  z 2 x 


 
1  0.12 log 10 
 p  X 0 
 X 0 
Energy loss: formula di Bethe-Bloch
 (in presenza di campo magnetico) la traccia spiraleggia nel piano trasverso

dE
Zz 2   2me c 2 2  2 
2
   
 0.31
log 
2 
dx
A   I 1  me / M  

21
Metodi di track finding
 Metodi
22
locali
 Viene aggiunto alla traccia un punto alla volta, in base a
criteri di scelta che dipendono dalla forma prevista per la
traccia e dai punti precedentemente acquisiti
 Metodi
globali
 Viene selezionato direttamente un insieme di punti sui quali
viene operato un check unico, cosicché la traccia viene
restituita direttamente
 NB:
 è necessario in ogni caso un adattamento specifico
all’apparato sperimentale da usare.
Local vs. Global

Metodi locali:
 Scelta dei punti “step-by-step” con una informazione che rimane
parziale fino al termine della procedura
 Il risultato può dipendere dall’ordine con cui i dati vengono
analizzati
 Necessita di un innesco ben congegnato
 Non necessita di un modello globale di traccia (traiettoria)
 Consente una trattazione ottimale dei “disturbi”

Metodi globali




La decisione viene presa sfruttando l’intera informazione
Può operare direttamente sui dati grezzi
Ha bisogno di una precisa espressione della traiettoria
Può tenere conto dei “disturbi” solo in media
23
Metodi locali

Tre possibili criteri logici:
 “segui il tuo naso”  track following method
◊ Si innesca la traccia partendo da un estremo, e si esegue una
“proiezione” nel layer successivo, selezionando il punto meglio
compatibile con essa
24
Metodi locali

Tre possibili criteri logici:
 “segui il tuo naso”  track following method
◊ Si innesca la traccia partendo da un estremo, e si esegue una
“proiezione” nel layer successivo, selezionando il punto meglio
compatibile con essa
 “congiungi gli estremi”  track road method
◊ Si determinano due punti sui layer estremi e si congiungono cercando
un percorso adeguato fra i punti del rivelatore
25
Metodi locali

Tre possibili criteri logici:
 “segui il tuo naso”  track following method
◊ Si innesca la traccia partendo da un estremo, e si esegue una
“proiezione” nel layer successivo, selezionando il punto meglio
compatibile con essa
 “congiungi gli estremi”  track road method
◊ Si determinano due punti sui layer estremi e si congiungono cercando
un percorso adeguato fra i punti del rivelatore
 “definisci una immagine”  track element method
◊ Si individuano segmenti lungo il percorso della traccia, e poi vengono
collegati fra loro in base alla compatibilità
26
Il “principe” dei metodi locali: Kalman
Filter


Base: track following
Introdotto da P. Billoir (1983)


In seguito si è compreso che tale metodo si riconduce ad un metodo
generale sviluppato da Kalman per il fit di sistemi complessi
Ingredienti:

An (5)
◊ vettore di stato contenente i 5 parametri essenziali di traccia

Vn (5x5)
◊ matrice di covarianza dei 5 parametri (5x5)

Mn = H An(2)
◊ vettore di “misura” (che passa dai parametri alla misura osservabile  punto)

Cn = H Vn HT (2x2)
◊ matrice di covarianza delle misure
27
Algoritmo del Kalman Filter
 Start:
“seeding”
 Stime ragionevoli per An e Vn a partire da alcuni punti.
 Propagazione
 stima del vettore di stato nel punto n – 1:
A*n-1 = Pn An
 viene propagata anche la matrice di covarianza, che
viene artificiosamente aumentata di un termine di
disturbo che tiene conto dello scattering multiplo:
V*n-1 = Pn ( Vn + Nn ) PnT
28
Algoritmo del Kalman Filter

Selezione di un punto candidato all’inclusione, in
un layer di rivelazione:
 Mn-1  coordinate; Cn-1  covarianza

Calcolo dei residui
RAn-1 = Mn-1 – M(A*n-1)
RCn-1 = Cn-1 – C(A*n-1)

Filtro: modifica del vettore di stato includendo
nuova informazione
 Definizione: “gain matrix” K = V*n-1 HT (Cn-1 + H V*n-1 HT)-1
An-1 = A*n-1 + K RAn-1
Vn-1 = (1 – K H) V*n-1
D2  (RAn-1)T(RCn-1)-1 RAn-1
29
Kalman Filter
 Track
finding:
 Single step:
◊ Propagazione su più punti sul layer in studio
◊ Inclusione del punto che determina il minimo D2
 Hypothesis tree:
◊ Generazione di “alberi” di punti, tenendo conto di tutte le
possibilità
◊ Selezione del percorso cui corrisponde il minimo D2 totale
(dalla somma di tutti I contributi)
 Track
fitting:
 Avviene “in itinere” durante il finding
 3D fit contemporaneo “locale”
30
Vantaggi e svantaggi del Kalman Filter
 OK
 Esegue contemporaneamente track finding e fitting
 Opera sui parametri di traccia (retta: 4, elica: 5)
◊ Niente matrici della dimensione del numero di punti del
campione
 Molto utile per collegare punti su rivelatori diversi
 E’ molto semplice introdurre gli effetti dei “disturbi”:
◊ Multiple scattering: incremento sulla matrice di covarianza
◊ Energy loss: variazione “locale” della curvatura, step per step
 KO
 Richiede una procedura ottimale di ricerca dei punti
 E’ fortemente dipendente dalle condizioni iniziali
31
Metodi globali
 Combinatorio totale
 Analisi di tutte le possibilità
 Template matching
 Confronto con modelli
 Histogramming
 Ricerca di configurazioni ripetitive
 Metodi neurali o neural-like
 Associazioni locali
32
Template matching
 Applicazione
“nativa” del pattern recognition
 Definizione di “template”:
◊ Definire parametri iniziali di traccia
◊ Stabilire che punti produrranno
 Confronto con lo schema di punti ottenuto
sperimentalmente:
◊ Individuazione dei template presenti nel campione
◊ Nessun processing aggiuntivo: i parametri finali della traccia
sono quelli del matched template
 Applicabilità molto limitata
◊ Solo in caso di poche combinazioni possibili
33
Template matching  recursive tree
search

Procedura iterativa con diverse gerarchie di template, via
via più precise, in modo da operare l’incremento del
dettaglio solo nei sottoinsiemi di pattern che si adattano, via
via, al template precedente che è stato riscontrato nei dati.
1
2
3
4
34
Complete combinatorial method

L’algoritmo concettualmente più semplice:
 Costruire tutte le possibili sequenze di punti (1 per layer)
 Valutare la compatibilità con il modello di traccia previsto
◊ Fit e calcolo del 2  parametro di qualità
 Ordinare le combinazioni secondo il parametro di qualità
 Stabilire un criterio di accettazione:
◊ Quantitativo: i primi N elementi
• (se si ha una idea della molteplicità da attendere in un evento)
◊ Qualitativo: tutti gli elementi per cui 2 < 2max

Applicabilità fortemente dipendente dal numero di
punti per layer e dal numero di layer stessi
 Crescita fattoriale della complessità
 Inapplicabile nella quasi totalità dei casi
35
Histogramming: Radon Transform
Distribuzione dei punti nel rivelatore:
 x    p x Dpd p
 p
Risposta media del rivelatore per una particella
con una data configurazione di parametri {p}
Popolazione tipica dello spazio delle features (param. di traccia),
per la feature corrispondente a una particella [delta function]
Problema di inversione:

36
~
Dp    x p x dx
X
Conoscenza dettagliata della risposta dei rivelatori
 Presenza di una precisa forma teorica della traccia
Hough Transform  histogramming

Estensione del caso della trasformata di Radon.
 Dipendenza dalla sola forma teorica della traccia

Base: espressione teorica della traiettoria
 Caso 1: (B = 0)  retta  4 parametri
 Caso 2: (B = costante)  elica  5 parametri

Ipotesi dell’algoritmo:
 Se N punti appartengono alla stessa traccia, estraendo i parametri
di traccia da qualsiasi loro sottoinsieme otterrò valori simili a quelli
che otterrei dall’intero insieme.
 Se i punti non appartengono ad una specifica traccia, estrarrò
parametri casuali, che si distribuiranno a caso nello spazio delle
features
37
Hough Transform: procedimento

Esempio: rette nel piano da un punto fisso
 Equazione: y = mx [m = tan()]
1. Estrazione di  da tutte le coppie di punti  istogramma
2. Ricerca di picchi nell’istogramma
> corrispondenti a tante coppie “concordi”  stessa traccia
38
Pro e contro della Hough Transform
PRO
 Semplice e veloce
 Non richiede un cluster finding
 Può lavorare direttamente con i dati grezzi
CONTRO
 Dimensionalità dello spazio delle features
 Nel caso più semplice (retta) serve un istogramma a 4D


Necessità di una equazione “teorica” della traccia
Necessità di una quantità di layer del rivelatore
abbastanza grande da evidenziare gli
addensamenti
39
40
Digressione: cos’è una rete neurale
SINAPSI


Sistema distribuito di “processing units”
collegate fra loro in modo da scambiarsi
informazioni.
Due costituenti di base:
 Il nodo di calcolo: neurone
◊ raccoglie segnali in input da altri elementi della rete
◊ restituisce un output (“attivazione”) in risposta al segnale
ricevuto
 Veicolo di scambio di informazioni: sinapsi pesata
◊ implementa le correlazioni (o competizioni) fra neuroni
◊ agisce come un fattore moltiplicativo sul segnale ricevuto da
ogni unità (“peso sinaptico”)
NEURONI
Come opera la rete neurale
RN a connessione completa
a i   0,1 
wij  0 correlazione  incremento attivazione
wij  0 competizione  decremento attivazione


a i  1  exp 





j
wij a j 


T

1
La variazione nell’attivazione diminuisce di ciclo in ciclo
1
Stabilizzazione finale 
N
Dai
i a  
i
41
Come opera la rete neurale
42
Mappa di attivazioni reali comprese fra 0 e 1
Confronto con una soglia fissa di attivazione S
Mappa binaria di attivazioni (“on” / “off”)
abin
1 se areal  S

0 altrimenti
43
Implementazione del Tracking Neurale
Punti nel rivelatore  Neuroni = segmenti fra coppie di punti
Competizione  peso inibitorio costante
Nessuna relazione fra
segmenti non contigui
wI  B
Concatenamento  peso
eccitatorio dipendente
dall’allineamento
wE  A 1  sin  
n
CATTIVO
allineamento:
wE  0
BUON
allineamento:
wE  A
Tracking neurale: work flow
 Lettura
punti sui layer
 Creazione segmenti
“accettabili” (cut)
 La rete neurale “spegne” i
segmenti sbagliati,
lasciando “accesi” quelli
giusti, che producono le
catene di segmenti che poi
verranno passate al fit della
traccia.
44
Elastic Arms

Combinazione di metodo neurale e “template matching”


Definizione di N templates (Hough Transform)
Calcolo di una funzione “energia”:
◊ E = S SiaMia
•
•

S = condizione di appartenenza del punto “i” alla traccia “a”
M = distanza del punto “i” dalla traccia “a”
Tale funzione deve essere minimizzata in due step:
1. Correzione dei parametri dei template a partire dai punti
◊ Refit
2. “Riassegnazione” dei punti secondo il template più vicino
◊ (rete neurale dei fattori Sia pesati in base ai valori M ia)
◊
Convergenza  ciascun punto viene assegnato al template migliore.
45
Come si valuta la bontà di un
algoritmo?
 Simulazione
 Insieme di punti “assegnati” a ogni traccia
 Confronto fra le associazioni vere e quelle dedotte dal tracking
 Classificazione
delle tracce trovate:
 Perfect Track
◊ Solo cluster con lo stesso ID traccia
• Tutti quelli presenti nell’evento  Complete Perfect Track
• Alcuni punti mancanti  Incomplete Perfect Track
 Imperfect Track
◊ Cluster con ID di tracce diversi (si assegna quello di
maggioranza)
• “Sufficiente” maggioranza di un ID  Majority Good Track
(accettabile)
• “Insufficiente” maggioranza di un ID  Majority Fake Track
(non accettabile)
46
Come si valuta la bontà di un
algoritmo?
47
Classificazione degli indici di traccia simulata
Track ID
Perfect Track
Class 1:
Perfect
Complete
Imperfect Track
Class 2:
Perfect
Incomplete
Class 3:
Majority Good
Class 5:
Not Found
Class 4:
Majority Fake
Efficienza
Tracce Trovate vs. Tracce Simulate
 “Event
by event”
 # tracce trovate correttamente / # tracce generate
 Criterio
di massima resa su un campione
 # eventi ricostruiti al 100% / # eventi generati
 Criterio
di resa sufficiente su un campione
 # eventi ricostruiti al 90% (o meno) / # eventi generati
48
49
Efficienza
 Non
tutte le tracce generate sono “trovabili”:
 Limiti dell’algoritmo
 Eccessivo effetto distorcente di EL e MS
 Quantità insufficiente di segnale nei rivelatori
 Efficienza
“del metodo”
 Calcolata sul campione delle sole tracce “trovabili”
 Efficienza
“globale”
 Calcolata sul campione delle tracce generate
E’ importante che l’algoritmo non
sia “troppo” limitato!
Esempio: efficienza di un algoritmo di
tracking
good
fake
50
Track fitting
 Una
volta assegnati i punti ad una
particella…
 …bisogna ricostruire I parametri fisici
dei punti con l’equazione della
traiettoria
 Best-Fit
 M. Locali (Kalman)  fit progressivo
 M. Globali  fit “globale”
 Caso
facile: retta
 Caso difficile: elica
 Necessario un fit del cerchio nel piano trasverso
51
Track fitting: Kalman Filter

Utilizzabile anche come semplice fitter
 I punti non devono essere “cercati”
 Il filtro è “forzato” a eseguire correzioni adeguate a
includere, uno alla volta, i punti della traccia
 Vantaggio: il fit viene eseguito “all in one” in 3D
 Svantaggio: è necessario un innesco (“seed”)
 Fit preliminare con altri metodi
 Ipotesi preliminare su 2 punti (retta) o 3 punti (elica)
52
Metodi per il fit del cerchio nel piano
 Metodo
dei minimi quadrati non risolubile
esattamente (equazioni di minizzazione
complesse)
 Operazioni
di linearizzazione
 Mapping conforme
 Sfera di Riemann
53
Mapping conforme
Ipotesi: il punto (xV, yV) appartiene alla circonferenza
Utile per il fit di tracce primarie
54
x  xV
yV  y
u
, v
2
2
x  xV    y  yV 
x  xV 2   y  yV 2
Inversione dell’ordine dei layer!
55
Mapping conforme
L’equazione cartesiana del cerchio…
x  x0    y  y0 
2
2
 R2
…si trasforma in una retta (non passante per l’origine)
2xV  x0 u  2 yV  y0 v  1
 fit banale
Occhio alla propagazione degli errori!!!
  u  v
2
u
2
 
2 2
2
x
  4u v   
2
v
2 2
2
x
  4u v 
  u  v  

2
xV
2
xV
2
2 2
2
y

2
yV
2 2
2
y

2
yV


56
Sfera di Riemann
Una sfera di raggio unitario “poggiata” sul piano XY
Intersezione sulla sfera di Riemann
Dato un punto sul piano XY, si congiunge con il polo della sfera opposto al
“punto di appoggio”, e si individua il punto in cui la congiungente interseca
la sfera.
Coord. nel piano
Proprietà di base: le proiezioni dei punti di un cerchio nel piano XY stanno su un piano
57
Sfera di Riemann
Fit di un piano nello spazio
Raggio
Centro
Da minimizzare
= autovettore di A con l’autovalore più piccolo
Fit della traccia nello spazio
 Quando
si esegue un fit nel piano, bisogna
linearizzare l’equazione dell’elica nello
spazio, per completare la procedura di fit.
C r 2  D2 
2
t
z  Dz  tan   t , t  arcsin 

C
 2 1  CDt 
Curvatura
Parametro di
impatto trasverso
58
Risoluzione
Importante: conoscere l’indeterminazione sulle
proprietà della particella ricostruita (p, PID, vertice)
 Ancora una volta, confronto con la simulazione
 Confronto fra i parametri “veri” della traccia trovata
e quelli ricostruiti con il fit

 Differenza assoluta ( Pvero – Pricostruito )
 Differenza percentuale ( Pvero – Pricostruito ) / Pvero

Criterio di “accettabilità” di punti sbagliati:
 Entro che limiti un punto sbagliato “rovina” la risoluzione dei
parametri?
 E’ accettabile una quantità di punti sbagliati che non modifica
sensibilmente la risoluzione
◊ …quando ciò non significa che la procedura di ricostruzione vada
rivista perchè troppo indeterminata 
59
Esempio: risoluzione parametri
Dip angle ()
resolution (in mrad)
sigma = 3.69  0.01
Azimuthal angle ()
resolution (in mrad)
pt resolution (in % of true value)
sigma = 13.4  0.3 %
sigma = 4.71  0.01
60
Stand-alone tracking: results (III)
Longitudinal impact parameter
resolution (in microns)
sigma = 265.6  0.4
Transverse impact parameter
resolution (in microns)
sigma = 79.7  0.1
61
Summary

Strategia di analisi di eventi di collisione ad alta
energia:
 Tracking detectors
 Algoritmi di Tracking

Track finding:
 Problema di Pattern Recognition
◊ Metodologie locali e globali di riconoscimento di tracce
 Valutazione: efficienza di tracking

Track reconstruction:
 Fit non lineare in presenza di campi magnetici
◊ Splitting della procedura in più step
 Valutazione: risoluzione dei parametri di traccia
62