Tensor voting

Questa voce o sezione sull'argomento algoritmi non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Il tensor voting è un algoritmo utilizzato nella visione artificiale, che permette di inferire informazioni riguardanti le strutture geometriche descritte da un insieme parziale di dati. Si ispira ai principi della Gestalt riguardanti il sistema visivo animale: l'individuo riceve continuamente informazioni parziali, informazioni errate o corrotte dal rumore, ma ha la capacità di distinguere il rumore, per poterlo eliminare, e di ricostruire le informazioni mancanti.

Si ipotizzi di avere a disposizione una nuvola di punti appartenenti a una o più strutture geometriche in ${\displaystyle \Re ^{n}}$, si ipotizzi inoltre che i punti forniti siano affetti da rumore additivo e contengano una certa percentuale di outlier.

Gli scopi dell'algoritmo consistono nel:

1. identificare gli outlier per poterli rimuovere,
2. stimare la dimensionalità delle strutture geometriche descritte dai dati,
3. stimare le orientazioni delle strutture geometriche,
4. consentire un'accurata ricostruzione di tali strutture.

Tutto ciò viene effettuato grazie all'utilizzo di due principi percettivi fondamentali della Gestalt:

• prossimità: la vicinanza tra elementi geometrici (ad esempio punti) porta il sistema percettivo a raggrupparli nel tentativo di descrivere un'unica struttura geometrica;
• proseguimento: l'orientazione di strutture geometriche, di cui si hanno sufficienti informazioni, viene diffusa alle entità geometriche circostanti.

La distanza fra punti, euclidea o di differente natura, può essere utilizzata per sfruttare il principio di prossimità. Il principio di proseguimento, invece, può essere sfruttato solamente se si ha la possibilità di rappresentare, tramite una entità geometrica, la dimensionalità e l'orientazione delle strutture geometriche di cui ogni punto fa parte.

Una possibile scelta, per la rappresentazione dell'orientazione di una struttura geometrica a m dimensioni in ${\displaystyle \Re ^{n}}$, è quella di utilizzare i tensori del secondo ordine, simmetrici e definiti positivi (d'ora in poi verranno indicati semplicemente come tensori). Queste entità geometriche possono essere rappresentate tramite delle matrici quadrate simmetriche definite positive. Questo tipo di matrici identifica un sistema di autovalori ed autovettori in cui i primi risultano sempre non negativi mentre secondi sono sempre ortogonali fra di loro. Queste proprietà di un tensore permettono di rappresentare, in uno spazio di dimensionalità arbitraria, sia un'orientazione che una confidenza per ognuna delle direzioni descritte dagli autovalori. Si osservi che la seguente matrice degli autovettori:

${\displaystyle X=[e_{1}|e_{2}|\dots |e_{m}]}$

di cui gli autovalori ${\displaystyle e_{1}\dots e_{n}}$ ne costituiscono le colonne, è una matrice di rotazione essendo gli autovettori ortonormali fra loro.

Essendo la somma di matrici simmetriche ancora una matrice simmetrica, sommando due tensori elemento a elemento si ottiene ancora un tensore dello stesso tipo, che rappresenta ancora una volta delle orientazioni e delle confidenze. L'analisi relativa alla combinazione lineare di queste entità mostra quanto i tensori di questo tipo risultino naturalmente portati ad essere utilizzati per la gestione delle orientazioni. In particolare il tensore T può essere ottenuto dalla matrice degli autovettori X e dalla matrice diagonale degli autovalori ${\displaystyle \Lambda }$, in cui gli autovalori son riportati in ordine non crescente e gli autovettori sono ordinati di conseguenza. In particolare vale la seguente scomposizione:

${\displaystyle T=X\Lambda X^{T}=\sum _{i=1}^{n}\lambda _{i}e_{i}e_{i}^{T}=\sum _{i=1}^{n-1}\left((\lambda _{i}-\lambda _{i+1}\sum _{j=1}^{i}e_{j}e_{j}^{T})\right)+\lambda _{n}e_{n}e_{n}^{T}}$

L'ultima espressione dell'uguaglianza rappresenta la scomposizione di un tensore in altri tensori dello stesso tipo in cui sono presenti ${\displaystyle 1,2,\dots ,n}$ autovalori non nulli, si tratta di tensori elementari ottenuti dalla composizione di sole ${\displaystyle 1,2,\dots ,n}$ direzioni di interesse egualmente pesate.

L'idea descritta da questa scomposizione è la seguente: si immagini che un tensore rappresenti, nello spazio ${\displaystyle \Re ^{n}}$, un iper-ellissoide di cui gli autovettori moltiplicati per i relativi autovalori ne rappresentano gli assi, la decomposizione mostrata rappresenta un qualunque iper-ellissoide di questo tipo come somma di ellissoidi generici in cui alcune dimensioni sono completamente schiacciate ed altre sono descritte da assi la cui norma è identica. Ad esempio nello spazio a 3 dimensioni un ellissoide può essere scomposto come somma di una sfera, di un disco circolare e piatto, e di un ellissoide schiacciato completamente in due direzioni (una sorta di spillo). In particolare il tensore a sfera viene chiamato ball tensor, il tensore a disco viene chiamato plate tensor mentre quello a spillo viene chiamato stick tensor.

È facile comprendere che questa scomposizione consente di distinguere in ${\displaystyle \Re ^{n}}$ differenti tipi di orientazione per diversi tipi di strutture geometriche. Nel tensor voting ogni tensore rappresenta le normali alla struttura che si ipotizza che attraversi il punto in cui esso è posto: ad esempio nello spazio a 3 dimensioni un tensore di tipo stick rappresenta la normale ad una superficie, mentre il tensore plate rappresenta il piano normale ad una curva. I valori ${\displaystyle (\lambda _{i}-\lambda _{i+1})}$ e ${\displaystyle \lambda _{n}}$ vengono detti saliency e costituiscono i pesi dei tensori elementari nella combinazione lineare che consente di generare l'ellissoide (ovvero il tensore presente nel punto).

Data una nuvola di punti, inizialmente non si ha alcuna conoscenza delle orientazioni delle strutture geometriche che essi descrivono, né della loro dimensionalità; per questo motivo inizialmente si codificano in ogni punto dei ball tensor con saliency unitaria, questi oggetti sono descritti dalla matrice identità. Ogni tensore presente nello spazio genera attorno a sé un campo tensoriale che descrive l'orientazione che avrebbe una curva passante per il tensore e per ogni punto del campo. L'idea è quella di costruire i campi tensoriali, detti voting field, in maniera tale da descrivere le orientazioni delle curve percettivamente più adeguate alla posizione dei vari punti, in particolare si vogliono rappresentare le orientazioni di curve smooth (ovvero di classe ${\displaystyle {\mathcal {C}}^{2}}$) a curvatura costante.

La scelta migliore sono degli archi di circonferenza, essendo queste curve di classe ${\displaystyle {\mathcal {C}}^{2}}$ e con curvatura costante. Nel caso di un ball tensor, in cui non ci sono vincoli di orientazione, l'arco di circonferenza a curvatura minima che attraversa il tensore ed un suo generico punto p del campo generato è un segmento, ovvero un arco di circonferenza di raggio infinito e curvatura nulla. Il tensore codificato in ogni punto da un ball tensor è un tensore che definisce l'orientazione di questa curva, in particolare sia I la matrice identità in ${\displaystyle \Re ^{n}}$ e sia p il punto di interesse, si immagini di lavorare nel sistema di riferimento del tensore votante, l'orientazione X cercata può essere ottenuta semplicemente schiacciando il ball tensor lungo un'opportuna direzione fino a rendere nullo l'autovalore in quella direzione, in particolare:

${\displaystyle T_{p}=I-{\tilde {p}}{\tilde {p}}^{T}}$

dove ${\displaystyle {\tilde {p}}={\frac {p}{\|p\|}}}$ rappresenta il versore nella direzione di p. La costruzione del voting field di un tensore di base, ma non ball, è più complessa: infatti in quel caso l'orientazione è da calcolare per un arco di circonferenza non degenere.

In ${\displaystyle \Re ^{2}}$ l'unico tensore non ball è lo stick tensor, di cui un solo autovalore è non nullo: esso rappresenta la normale alla curva che passa per il tensore che genera l'orientazione, che si ipotizza essere un'ellisse centrata nell'origine, schiacciata completamente lungo l'asse delle ordinate, e passante per il punto p di interesse. È facile mostrare che il vettore normale alla circonferenza osculatrice è il seguente:

${\displaystyle v(p)={\begin{pmatrix}-\sin(2\theta )\\\cos(2\theta )\end{pmatrix}}}$

dove ${\displaystyle \theta }$ è l'angolo tra la direzione dell'unico autovettore relativo ad un autovalore non nullo ed il punto p. Dato questo vettore l'orientazione voluta è:

${\displaystyle T_{p}=v(p)v(p)^{T}}$

In ${\displaystyle \Re ^{n}}$ un tensore elementare T, posizionato nell'origine ed orientato come gli assi, è caratterizzato da un insieme di dimensioni in cui gli autovalori sono nulli e da un insieme di dimensioni in cui gli autovalori, tutti uguali, sono non nulli. Le prime verranno qui chiamate dimensioni compresse e le seconde non compresse.

Portale Matematica

Portale Neuroscienze