Lucas-Kanade

Il metodo di stima del flusso ottico di Lucas-Kanade (LK81) è un metodo per stimare il movimento di caratteristiche interessanti in scene successive di un video. L'obiettivo è quello di associare un vettore movimento $(u,v)$ ad ogni pixel “interessante” della scena confrontando due immagini consecutive.

L'algoritmo fa le seguenti assunzioni:

• La luminosità tra immagini consecutive non cambia;
• Le due immagini devono essere temporalmente vicine in maniera che gli oggetti non abbiano uno scostamento significativo (l'algoritmo lavora bene con oggetti in lento movimento);
• L'immagine contiene oggetti con sufficiente tessitura in scala di grigi (l'algoritmo originale non usa esplicitamente il colore) il cui gradiente cambia graduatamente.

Partendo dell'equazione del flusso ottico per ogni punto $(x,y)$:

$$I (x + u\delta t, y + v\delta t, t + \delta t) = I(x,y,t)$$ (8.2)

dove $I(t)$ è un immagine e $I(t + \delta t)$ la consecutiva. Con l'espansione in serie di taylor al primo ordine:

$$\begin{array}{l} I (x + u\delta t, y + v\delta t, t + \de... ...t) v + \frac{\partial I}{\partial t} (x,y,t) = 0 \end{array}$$ (8.3)

L'algoritmo di Lucas-Kanade assume che il cambiamento di luminosità di un pixel della scena venga totalmente compensato dal gradiente della scena stessa ovvero

$$I_x u + I_y v + I_t = 0$$ (8.4)

dato il gradiente temporale $I_t$ e il gradiente spaziale $(I_x,I_y)$.

Ovviamente il singolo pixel non contiene abbastanza informazione per risolvere questo problema. Per raccogliere più osservazioni viene assunto che un intorno del pixel abbbia lo stesso moto, ovvero

$$\begin{bmatrix} I_x(\mathbf{p}_1) & I_y(\mathbf{p}_1) \\... ...thbf{p}_2) \\ \vdots \\ I_t (\mathbf{p}_n) \end{bmatrix}$$ (8.5)

dove $\mathbf{p}_1 \ldots \mathbf{p}_n$ sono i punti nell'intorno del punto da stimare. La soluzione può essere ottenuta attraverso il metodo delle normal equations

$$\begin{bmatrix} \sum I_x^2 & \sum I_x I_y \\ \sum I_x... ...in{bmatrix} \sum I_x I_t \\ \sum I_y I_t \end{bmatrix}$$ (8.6)

Se si nota questa è anche la matrice dei punti caratteristici sfruttata poi da Shi-Tomasi o da Harris (vedi 6.2): i punti caratteristici di questa matrice sono punti che vengono facilmente tracciati con l'algoritmo di Lucas-Kanade.

Quando il moto è più grande di un pixel è necessario un algoritmo iterativo per risolvere il problema e un approccio coarse-to-fine per evitare i minimi locali: esisterà una scala per la quale il moto del pixel sarà inferiore ad un pixel.

L'algoritmo originale di Lucas-Kanade assume che lo spostamento tra due immagini consecutive sia sufficientemente piccolo da poter essere approssimato mediante lo sviluppo di Taylor al primo ordine. Quando il moto supera alcuni pixel tale ipotesi non risulta più valida e la procedura può convergere verso minimi locali indesiderati.

Per superare questo limite vengono normalmente utilizzate rappresentazioni piramidali dell'immagine. Il moto viene inizialmente stimato alle risoluzioni più basse, nelle quali gli spostamenti apparenti risultano ridotti, e successivamente raffinato ai livelli di dettaglio superiori. Questo approccio, noto come Pyramidal Lucas-Kanade, rappresenta ancora oggi una delle implementazioni più diffuse del metodo.

Un ulteriore problema riguarda la scelta dei punti da tracciare. Come osservato da Tomasi e Kanade, non tutti i punti dell'immagine forniscono una stima affidabile del moto. Zone uniformi o contenenti un solo bordo generano infatti sistemi mal condizionati e producono risultati instabili. Per questo motivo è conveniente selezionare preventivamente punti caratteristici che presentino variazioni significative dell'intensità in più direzioni.

Questa osservazione portò allo sviluppo del tracker Kanade-Lucas-Tomasi (KLT), nel quale un rilevatore di punti caratteristici, tipicamente Shi-Tomasi o Harris, viene utilizzato per selezionare le caratteristiche da tracciare mentre Lucas-Kanade viene impiegato per stimarne il moto tra immagini successive. Il tracker KLT è stato per molti anni uno degli strumenti fondamentali per la visual odometry, il tracking di caratteristiche locali e le applicazioni di Structure from Motion.