Metodi di Ricostruzione
in fisica Subnucleare
Corso di Metodologie Informatiche Per
la Fisica Nucleare e Subnucleare
A.A. 2009/2010
II Lezione, 9/11/09
S.Arcelli
1
Sommario della scorsa lezione
Concetti introduttivi:
• Cosa si intende in generale per ricostruzione
• Ricostruzione di tracce cariche: track finding e fitting
• Come si qualifica una procedura di ricostruzione:
(efficienza, frazione di fakes, qualità della stima dei
parametri...)
2
In questa lezione:
• Metodi di riconoscimento di traccia:
• Metodi Globali → Template Matching, MST, Fuzzy
Radon & Hough Transform, Neural Networks
• Metodi Locali: il track following
3
Fuzzy Radon Transform
Basato sul fatto che la densità ρ(x) della popolazione nel Pattern
Space può essere espressa come il seguente integrale:

(x)  p (x)D(p)dp
P
D( p)
Densità di popolazione
nel Feature Space,(deltafunctions in corrispondenza
dei parametri p della traccia)
p (x)
Funzione di “risposta” nel Pattern
Space (x) per una traccia descritta da
un set p di parametri (equazioni del
moto + risoluzione)
4
Fuzzy Radon Transform
Ovvero:
(x0 ,tan ) (x, z) :
(equazione di una retta)
 ( x, z)
D( x0 , tan )
D(x0, tan ) :
 (x0, tan )
0
5
Fuzzy Radon Transform
Il metodo consiste nel calcolare la trasformazione inversa, che
fornisce la densità di popolazione nello spazio delle Feature, in
base alla densità osservata ρ(x) nel pattern space e al modello
di traccia+ evenuali effetti di risoluzione, che fissano p(x)
~
D(p)  (x)p (x)dx

= Fuzzy Radon Transform
X
Ci si aspetta che i candidati di traccia generino nello spazio
delle Feature dei massimi locali nella trasformata.
6
Fuzzy Radon Transform
Esempio: una traccia in un semplice sistema di tracking con
10 layer equidistanti, in assenza di campo magnetico:
La generica retta che passa dal punto
misurato (xi,yi) è scrivibile come:
y
y i  kx i  d

y0
Questa è una retta nello spazio
dei parametri (k,d)=(tan,y0), le Feature che
descrivono le possibili tracce nel rivelatore, con:
y i  Ordinata all’origine
 x i  Coefficiente angolare
x
7
Fuzzy Radon Transform
Ogni punto misurato dà origine ad una retta nello spazio delle
Features. Se i punti misurati appartengono ad una stessa traccia
(sono collineari), le corrispondenti rette nello spazio (k,d) si
incontreranno in un punto. Si ha un massimo nella Fuzzy Radon
Transform:
esempio di una traccia dritta (B=0):
~
D(y0, tan )
p (x, y) : y  tan   x  y0
( effetti di risoluzion e)
y0
8
Fuzzy Radon Transform
Tre tracce dritte (B=0) nel sistema di tracking:
Massimi ancora ben distinguibili,
ma sviluppo di massimi locali...
occorre rifinire il criterio di
selezione dei picchi.
y0
9
Fuzzy RadonTransform(parametrizzazione alternativa)
Parametrizzazione alternativa dell’equazione della retta, per evitare valori
divergenti per angoli prossimi a 90°:
y
• r=distanza minima tra origine e retta
•=angolo polare del vettore origine-punto
di minima distanza
r  x cos   y sin 
r

x
10
Fuzzy Radon Transform
Applicazioni anche a situazioni più complesse: due tracce molto vicine,
in rivelatore a geometria cilindrica e campo magnetico assiale (piccola
differenza in impulso, stesso punto di produzione)
J. Blom et al, “A fuzzy Radon
Transform for track Recognition”,
Proc. CHEP 94, San Francisco)
Tracce ancora facilmente distinguibili nello spazio (,), se l’effetto di
risoluzione è adeguatamente descritto (qui  legato alla curvatura della traccia, 
angolo azimutale di produzione,   angolo polare della traccia, =risoluzione rivelatore)
11
Hough Transform
 Caso “semplificato” della Fuzzy Radon Transform in cui non
si tiene conto esplicitamente degli effetti di risoluzione. Molto
più popolare...Utilizzato per la prima volta in esperimenti in
Camere a Bolle (Hough, 1959).
 La ricerca di massimi nella distribuzione trasformata nel
Feature space si fa analizzando istogrammi (dati binnati). Ogni
punto misurato incrementa una serie di celle nell’istogramma
sullo spazio dei parametri (la scelta del binning e del “range”
dell’istogramma deve essere fatta secondo criteri appropriati...).
12
Hough Transform-Esempio
Tracce cariche in un sistema di tracciamento nella proiezione
trasversa xy, campo magnetico uniforme lungo z
(traiettorie=archi di circonferenza passanti per l’origine, tracce
primarie )
Applicando la trasformazione:
x' 
x
2
2
x y
, y'  
y
x2  y2
E tenendo presente che le tracce sono
archi di circonferenza:
R2  (x  xc )2  (y  yc )2
13
Hough Transformspazio trasformato
Si ottengono delle rette:
xc
1
y'  
 x'
yc
2yc
1
1

yc
P
N.B. quanto minore è l’impulso,
tanto meno le tracce trasformate
puntano verso la nuova origine
14
Hough Transform-Esempio
Entries
Analisi della distribuzione in angolo nello spazio trasformato
(1-D Hough Transform)
Larghezza dei picchi
dipende dalla risoluzione
e dall’impulso
Tracce di basso momento
più difficilmente individuabili

15
Hough Transform-Esempio
Equazioni parametriche dei punti
misurati (x,y)(r,):
r  2R sin(  )
Archi di cerchio descritti in termini
dei parametri(1/R,):
1/R
Istogramma 2D:
16

Hough Transform

In questo modo (versione “2-D”), si riesce a recuperare la
sensibilità a tracce di basso momento, utilizzando anche
l’informazione del “parametro d’ impatto” nelle coordinate
trasformate

Stima dell’impulso della traccia, che, ad esempio, mi dà
l’informazione se nell’evento sono state prodotte tracce di
alta energia (algoritmi di High Level Trigger).

E’ spesso usato per avere un metodo di track finding veloce,
efficace nel discriminare sul fondo e non troppo sensibile ad
inefficienze, ma con richieste di precisione non stringenti
sulla stima dei parametri di traccia. Utilizzato in HLT (as es.
ALICE), come seed finder per procedure di tracking locale
(OPERA, HERA-B,...) .
17
Hough Transform

Se la ricognizione di traccia deve essere in 3D nel pattern
space (xyz), perchè la granularità del rivelatore non è
sufficiente per la separazione in una proiezione 2D, si puo’
segmentare la ricerca in intervalli dell’altra proiezione (ad es,
ricerca in xy in diversi intervalli dell’ angolo polare lungo z)

Possibile l’analisi anche con più parametri, ma la
individuazione dei massimi diventa sempre più complessa. Di
solito ci si limita a 2-D nel Feature Space

Tempo di elaborazione: dipende dal numero di misure, dalla
dimensionalità del feature space, dal binning
18
Neural Networks Techniques:
NN: modellizzazione matematica ispirata alle connessioni e alla
funzionalità dei neuroni in sistemi biologici. Concetti di base:



I nodi, artificial neurons
Le connessioni, relazioni tra in nodi
Funzione di trasferimento, che in base all’input che arriva su un nodo
da tutti gli altri nodi, ne determina l’output (elaborazione pesata
dell’input+meccanismo di thresholding)
Applicando un processo di apprendimento su campioni di
riferimento per il training della rete, si determinano i pesi
massimizzando una funzione che caratterizza la qualità
decisionale del meccanismo
19
Neural Networks Techniques
Hopfield Network:

Topologia “fully coupled”, interazioni simmetriche

Lo stato S del neurone è di due tipi: se il neurone è attivato,
Si=1, altrimenti Si=0.

Funzione di trasferimento:
w S  s )
Si  (

ij j
j
wij= Pesi
s j = Fattore di soglia
“Energy Function”:
1
E
2
w S S
ij i j
ij
20
Neural Networks Techniques:
Denby-Peterson Model
L’idea è di associare un neurone Sij ad ogni possibile
connessione tra due hit i e j nel rivelatore (segmenti di traccia):

Se il neurone è attivato, Sij=1, altrimenti Sij=0. Se Sij=1,
implica che i due hit facciano parte della stessa traccia.

Si deve poi definire una interazione fra neuroni, V, per cui
nello stato finale l’energia totale del sistema è minima (solo
neuroni che condividono un hit possono interagire).
V>0
V>0
V<0
21
Denby-Peterson Model

Potenziale di interazione:
V

l

jkw ijlSijSkl ,
wijl  
djl
cos ijl
dij  d jl
ijl
j
dij
i
Energy function:
1
E
2

ij
1
 jkw ijlSijSkl  ( SijSil 
2 lj

1
SijSkj ) (
2
k i


Sij  N)2
update dello stato finchè non si trova un minimo assoluto
(diversi algoritmi per la minimizzazione).
C.Peterson, “Track Finding with Neural Networks”, NIM A 279 (1989) 537,)
22
Denby-Peterson Model

Per costruzione dipende molto poco da un definito modello di traccia, e
trova efficientemente sia tracce dritte che debolmente curve, che
“sparpagliate”. Piuttosto robusta rispetto a noise e inefficienze.

E’ piuttosto pesante dal punto di vista computazionale, tipicamente il tempo
di elaborazione va come N3. Ha scarsa efficienza nel separare tracce vicine.

Funziona bene in condizioni di bassa densità di traccia. Ad esempio,
utilizzato per il tracking nella TPC dell’esperimento ALEPH (al LEP in
collisioni e+ e-). Ci sono estensioni (modifica della energy function) che
funzionano ragionevolmente anche ad alta densità di traccia (HERA-b)
23
Metodi di Track Finding Locali
I candidati di traccia sono selezionati individualmente uno dopo
l’altro (potenziale bias, ma una buona procedura è indipendente
dall’ordine in cui vengono elaborati i candidati di traccia...):

Si inizia sulla base di un numero limitato di punti misurati
(track seeds) opportunamente scelti. Si procede nella ricerca di
altri hits da associare al candidato di traccia estrapolando (o
interpolando), sulla base di un modello di traccia più o meno
rifinito.
Alcuni esempi:

Track Following
Track Road
Kalman Filter (metodo di Track Finding/Fitting simultaneo!)


24
Track Following
Il track following è ora uno dei metodi di ricognizione di traccia
più diffusi (essenzialmente nel contesto del Kalman Filter).

Metodo di tipo “percettivo”, ottimale in condizioni di
“prossimità e continuità” dei segnali delle tracce nel
sistema di tracking

Forte ridondanza nelle misure (condizione di base nel
design degli apparati moderni, caratterizzati da granularità
e precisioni elevate).

Se ben impostato, più efficiente in termini di velocità dei
metodi globali (“localizzazione” della ricerca)
25
Track Following
Ingredienti principali:

Un metodo di generazione dei seed di traccia, ovvero
candidati rudimentali, creati in base a un set limitato di
punti misurati, da cui iniziare il processo di track finding

Una descrizione parametrica della traiettoria che permetta
di estrapolare il candidato traccia da un layer di misura
all’altro durante il track following

Un criterio qualitativo, secondo cui distinguere candidati
di tracce buone da falsi candidati di traccia, ed
eventualmente interrompere l’elaborazione del candidato
26
Track Following-Generazione dei Seed

Devono fornire una prima stima (locale) dei parametri
(direzione, curvatura) del candidato di traccia, non troppo
lontana dai parametri finali

Deve essere efficiente (se non trovo l’iniziatore posso
perdere la traccia); occorre tenere un certo livello di
ridondanza ( considerare la possibilità di hit mancanti,
track faults )

Non deve essere troppo complessa (deve essere
ragionevolmente veloce).
27
Track Following-Generazione dei Seed
Diverse filosofie nella costruzione dei seed, che dipendono
significativamente dalle condizioni sperimentali (struttura del
rivelatore e sue caratteristiche, occupancy, ..). Si cerca di partire
da condizioni favorevoli, in regioni “pulite” del rivelatore.

Seeding in layer vicini

Seeding in layer distanti
28
Track Following
Seeding in layer vicini
•In generale, sui layer più esterni del sistema
di tracking, dove la densità di tracce è minore
• Non sempre vero! Dipende da come è fatto
il sistema di tracking. Ad esempio, in CMS
il seeding usa layer interni (Pixel, precisione
O(10μm), alta granularità, occupancy ~10-4)
•Rispetto al caso seguente, il braccio di leva
nel determinare la direzione è minore, ma
ho meno “combinatorio”.
29
Track Following
Seeding in layer distanti
•Miglior “braccio di leva”,
ma occorre considerare
anche gli effetti dello
scattering multiplo
•Più combinatorio
•Si preferisce il primo
approccio, in generale.
30
Generazione dei Seed-considerazioni

Spesso si utilizza il vincolo del vertice primario (che
aggiunge un punto con grande braccio di leva!)

Questo può essere inefficiente nel ricostruire tracce di
secondari che vengono da decadimenti. Necessario
complementare con seeding dedicato, se si è interessati a
questo tipo di segnali.
  

IP
Seeding
Il seeding ai layer esterni è invece inefficiente nel trovare
la particella “genitrice” in un decadimento
31
Generazione dei Seedaltre considerazioni

Quanti più punti si utilizzano nel seeding, tanto più si
limita il trasporto di falsi candidati di traccia.

Occorre tenere presente che alcuni canali nella regione di
seeding possono essere inefficienti. Fare la ricerca
utilizzando più combinazioni di piani.

Compromesso fra velocità e efficienza...
32
Track Following-Propagazione
Trovati i seed, occorre propagarli attraverso il detector.
Necessario un prototipo di modello di traccia che permetta di
estrapolare, sulla base della stima preliminare della direzione
data dal seed, il candidato di traccia sul layer di misura
successivo, con la relativa incertezza.
33
Track Following-Propagazione

In generale, Il modello di traccia “definitivo”, utilizzato in
fase di track fitting per la stima finale dei parametri di traccia,
deve esser il più accurato possibile: parametrizzazione della
soluzione delle equazioni del moto di una particella carica e
trattazione degli effetti del materiale (MS, perdita di energia)

Nel track following in generale, si utilizzano anche metodi
approssimati (semplici rette o parabole utilizzando
l’informazione degli ultimi punti accumulati)

Nel Kalman Filter, anche in questa fase si utilizza il modello
“definitivo”
34
Track Following-Approcci Possibili

“Naive” Track Following:

Nel layer n-simo di propagazione, si associa l’hit più
vicino all’estrapolazione della traiettoria. La propagazione
prosegue finché non si trovano più hit.

Sensibile a hit che non appartengono alla traccia, a
rumore ed inefficienze (soprattutto nelle prime fasi della
propagazione).

Può essere usato se la densità di traccia lo permette, e se in
propagazione ho buona precisione sull’estrapolazione.
35
Track Following-Approcci Possibili

Combinatorial Track Following:

ad ogni layer si considerano più hit compatibili entro una
tolleranza relativamente grande

da questi si genera un “albero” di nuovi candidati di traccia.

la selezione del candidato migliore é fatto in fase finale,
ad esempio con un fit di traccia su ciascun candidato.
Metodo molto efficiente, ma molto impegnativo dal punto
di vista computazionale
36
Track Following-Arbitration
Arbitration: criteri usati per trovare un compromesso tra i due
tipi “estremi” di track following. Ad ogni step di propagazione,
si consente la creazione di candidati multipli come nel
combinatorial track finding: tuttavia, i candidati traccia sono fatti
evolvere in parallelo, e ad ogni step:

Si limita il numero di candidati ad un numero massimo

Possibilità di un certo numero di hits mancanti (“track
faults”), consecutivi o totali

Quali candidati scegliere, si decide in base alla qualità della
traccia (numero di faults, numero di hit già accumulati, 2 )
37
Track Following-Arbitration
Seed T1
Candidati
Eliminati
Candidato
accettato
Nmaxfaults=1, Nmaxcand=3
38
Track Road
Basato sull’ interpolazione piuttosto che sull’ estrapolazione:

Utilizzando hits agli estremi della traccia (e un punto
intermedio centrale per tracce curve), si definisce la “strada”
entro una certa tolleranza, assumendo un modello di traccia
(rette o eliche). Gli hit compatibili con la track road sono
associati.

Più lento del Track Following (più combinatorio), ed è
utilizzato nel caso di bassa densità di traccia, grande distanza
fra i piani di misura del rivelatore e per rivelare tracce con un
basso numero di hit.
39