%\subsection{\emph{Split} degli stati}



Come accennato nell'introduzione, dai dati di ingresso è possibile solo dire da quali telecamere il target è visto nei vari istanti di campionamento ma non si ha una informazione precisa di locazione spaziale. In particolare, in due diversi istanti è possibile avere la stessa osservazione ma l'oggetto può appartenere a due aree di visione fisicamente distinte, ad esempio perchè il cono di visibilità di una telecamera è ""tagliato'' da quello di un'altra (vedi Figura \ref{fig:vcc incrociate}). 
In casi come questo sarebbe oppurtuno avere due stati distinti che riferiscono alla stessa osservazione, perchè la traiettoria futura potrebbe essere anche sostanzialmente diversa, dato che sono diversi sia gli stati confinanti, sia le probabilità di transizione associate. 
Questa quindi è una prima motivazione per fare uno \emph{split} (cioè scissione) di alcuni stati, e lo si può indicare come \emph{split} di tipo ""fisico''. \\
\begin{figure}
	\begin{center}
	\includegraphics[width=0.5\textwidth]{pictures/2TelecamereIncrociate}
	\end{center}
	\mycaption{Schema per lo \emph{split} fisico. Le aree evidenziate con lo stesso colore generano la stessa osservazione.}
	\label{fig:vcc incrociate}
\end{figure}
Un altro caso che si può presentare è più legato alla traiettoria compiuta dal target. Si abbia ad esempio un corridoio, e questo sia percorso sempre interamente da un capo all'altro (senza tornare indietro dalla zona centrale per intendersi) come schematizzato in Figura \ref{fig:corridoio schematico} (in questa e in altre rappresentazioni che seguiranno, per semplicità non sono riportati gli archi degli autoanelli, ma vanno considerati sempre presenti, addirittura sono quelli con i valori più alti). 

\begin{figure}[!h]
	\begin{center}
	\includegraphics[width=0.9\textwidth]{pictures/Corridoio}
	\end{center}
	\mycaption{Schema per lo \emph{split} logico.}
	\label{fig:corridoio schematico}
\end{figure}

Qui le videocamere sono state volutamente poste in modo da scansionarlo ortogonalmente, quando invece potrebbe bastarne una che lo inquadri longitudinalmente. In genere il fatto di trovarsi nel cono di visione di una telecamera porta a identificare una probabiltà 1/2 di spostarsi in quello di destra e 1/2 in quello di sinistra, supponendo che non ci sia una direzione di percorrenza privilegiata. 
Se si introduce però l'informazione di quale è il capo del corridoio da cui si arriva, ad esempio quello di destra, allora per la prima ipotesi si può certamente dire che ci si sposterà verso il capo opposto, e quindi si ha probabilità 1 di andare nel cono di sinistra e 0 in quello di destra. Anche in questo caso ha senso fare una divisione di alcuni stati perchè il comportamento futuro è diverso data la posizione (osservazione) presente e la traiettoria passata. Questo si può indicare allora come \emph{split} di tipo ""logico''. Si osserva inoltre che gli stati che possono essere scissi con questa motivazione spesso comprendono anche quelli del caso precedente.\\ 
In entrambi i casi segue un aumento del numero di stati e di archi del grafo, nonchè una opportuna sistemazione delle probabilità di transizione. 

E' ovvio che, nota la distribuzione delle telecamere e di conseguenza delle regioni individuate, gli stati da scindere per motivo fisico siano riconoscibili abbastanza facilmente, ma pensare a un algoritmo che li individui autonomamente non è cosa semplice. 
Si è deciso di arricchire il grafo in modo che contenga, per ogni stato (all'inizio unico perchè corrispondente alle osservazioni), anche un minimo di informazione circa la storia passata e futura,  legata alla traiettoria che si utilizza per la creazione dello stesso. 
In particolare, ignorando gli autoanelli, si memorizzano tutte le possibili combinazioni di stati passati-futuri che si verificano, nonchè il numero di volte che accadono, intesi come quegli stati legati al nodo in questione da cammini di lunghezza 1. \\
Schematicamente, per un generico nodo $S_i$ si può costruire una tabella che, letta per colonne, dia tali combinazioni di nodi passati $S_{i-1}$ e futuri $S_{i+1}$ legati a tale stato:
\begin{table}[!h]
\centering
\begin{tabular}{l | c c c c r}
\hline
$S_{i-1}$ & $S_a$ & $S_b$ & $S_b$ & $S_c$ & $S_c$ \\
$S_{i+1}$ & $S_b$ & $S_a$ & $S_c$ & $S_a$ & $S_c$ \\
\hline
\end{tabular}
\end{table}\\
\no Corrispondentemente si costruisce un'altra tabella con il numero di volte che si verifica ogni coppia:
\begin{table}[!h]
\centering
\begin{tabular}{ l  c | c c r |}
  &  & \multicolumn3{c|}{$S_{i-1}$}\\
  &  & $S_a$ & $S_b$ & $S_c$ \\
\hline
\multirow{3}*{ $S_{i+1}$} & $S_a$  &  0   &   2   &   4 \\
   & $S_b$  &  5   &   0   &   0 \\
   & $S_c$  &  0   &   3   &   1 \\
\hline
\end{tabular}
\end{table}\\
\no In questo esempio si ha che lo stato futuro è $S_b$ solo quando si proviene da $S_a$ mentre gli stati futuri sono  $\left\lbrace S_a , S_c \right\rbrace $ solo quando si proviene da $\left\lbrace S_b , S_c \right\rbrace $.

L'idea è stata quella di passare ad un'interpretazione di carattere di algebra lineare: nell'esempio si osserva che  la prima colonna è ortogonale alle altre due e rappresenta la parte in verde di Figura \ref{fig:schema_esempio_colorato}, mentre le colonne 2 e 3 sono invece ""simili'' tra loro e descrivono la parte in rosso. Si ottiene così che il nodo $S_i$ può essere suddiviso in due sottostati separati $S_i'$ e $S_i''$. 
Un altro modo per visualizzare la separazione è considerare i passati e i futuri dello stato: si individuano infatti dei sottoinsiemi ben precisi, come mostrato in Figura \ref{fig:schema_esempio_sottoinsiemi}.
\begin{figure}[h]
	\begin{center}
	\includegraphics[width=0.8\textwidth]{pictures/schema_esempio_colorato}
	\end{center}
	\mycaption{Rappresentazione riguardo l'esempio proposto.}
	\label{fig:schema_esempio_colorato}
\end{figure}
\begin{figure}[h]
	\begin{center}
	\includegraphics[width=0.5\textwidth]{pictures/schema_esempio_sottoinsiemi}
	\end{center}
	\mycaption{Rappresentazione riguardo l'esempio proposto.}
	\label{fig:schema_esempio_sottoinsiemi}
\end{figure}

Quel che si cerca è allora un indice che dia una ""misura di ortogonalità'' tra questi vettori colonna, e in particolare si è scelto, rifacendosi alla geometria, il coseno dell'angolo tra due vettori $a$ e $b$ definito come:
\begin{equation}
\label{eq:indiceortogonalità}
\sigma_{ab}=\frac{a^T\cdot b}{\Vert a \Vert \Vert b\Vert}
\end{equation}
e che vale 0 quando sono otogonali, 1 quando sono paralleli.\\
In una matrice (che risulta simmetrica) si raccolgono poi questi valori per ogni coppia di vettori, e si decide di fare uno \emph{split} per il nodo in questione quando si trova uno 0 (questa è una condizione abbastanza forte ma che dà una certa sicurezza che l'operazione non sia fatta inutilmente; successivamente si sono fatte prove rilassando il valore di $\sigma$ a 0.1 e 0.2).
Significa infatti (ricordando che la tabella è letta per colonne) che i due stati del passato che determinano tale 0 producono un comportamento del tutto diverso. 
Detti $S_{P_1}$ e $S_{P_2}$ tali stati, si distribuiscono tutti gli altri passati del nodo $S_i$ a seconda che siano più ""paralleli'' a uno o all'altro sempre secondo l'indice (\ref{eq:indiceortogonalità}). 
In questo modo si costruisce un sottoinsieme di passati associato al nuovo nodo $S_i'$ e uno associato a $S_i''$, che contengono rispettivamente anche $S_{P_1}$ e $S_{P_2}$. 
Ne risulta, inoltre, una naturale divisione in due sottoinsiemi  anche dei futuri (come nel precedente esempio). 

C'è poi il problema di assegnare le nuove probabilità di transizione. Si è deciso di lavorare non direttamente su di esse, bensì sul numero delle varie transizioni da uno stato all'altro, e spartirle sempre secondo gli indici trovati in precedenza. La matrice $A$ viene poi ricalcolata sulla base di questi nuovi valori. \\
Riferendosi allo schema generale della procedura di \emph{split} in Figura \ref{fig:schemasplit}, si potrebbe immaginare, da quello che si è detto sopra, che non ci siano archi tra il sottoinsieme di passati legati a $S_{P_1}$ e il nodo $S_i''$, perchè di fatto $S_{P_1}$ transita verso $S_i'$. 
Si decide invece  di porre una probabilità non nulla (ma bassa) per tali transisioni, sia perchè non si possono escludere deterministicamente, sia perchè in tale insieme possono esserci stati che non hanno ""distanza'' 0 da $S_{P_2}$ e quindi non sono del tutto slegati da  $S_i''$. 
Alla fine gli unici elementi di $A$ che vengono modificati sono, com'è intuibile, quelli delle righe e colonne relativi ai due nuovi stati, in particolare in tale matrice $S_i'$ prende il posto di $S_i$ e si aggiunge una colonna a destra e una riga in basso per $S_i''$, lasciando gli altri stati inalterati. \\
Per la matrice $B$ l'aggiornamento riguarda solo il numero di colonne, infatti le osservazioni (sulle righe) rimangono le stesse: la colonna relativa a $S_i$ diventa quella di $S_i'$ e se ne aggiunge una a destra, uguale a questa, per $S_i''$.


\begin{figure}[]
	\begin{center}
	\includegraphics[width=\textwidth]{pictures/splitnodogenerico}
	\end{center}
	\mycaption{Schema che rappresenta l'operazione di \emph{split} per un generico nodo $S_i$.}
	\label{fig:schemasplit}
\end{figure}


