Riassunto gerarchico delle nozioni del corso 2005-2006 di
Elaborazione Immagini e Visione Computazionale del Prof. A.
Giachetti - Università degli Studi di Cagliari, Facoltà di Scienze
Matematiche Fisiche Naturali, Dipartimento di Matematica ed
Informatica, Corso di Laurea Specialistica in Tecnologie
Informatiche
Riferimenti: E. Trucco, A. Verri, Introductory Techniques for 3-D
Computer Vision, Prentice Hall.
- elaborazione immagini
- tecniche ed algoritmi informatici per modificare immagini allo
scopo di:
- migliorarne la qualità (filtraggio, riduzione rumore)
- generare codifica utile (compressione)
- generare visualizzazioni (grafica)
- estrarre features
- ricavare informazioni/modelli
- computer vision
- ricava informazioni sul mondo esterno tridimensionale da una o più immagini digitali
- ricostruisce i dati geometrici della scena a partire dall'immagine, dai dati fotometrici e dai dati della telecamera
- computer graphics
- costruisce l'immagine a partire dai dati geometrici fotometrici della scena e dal modello della telecamera
- visione umana
- processo di interpretazione complesso ma in qualche modo "computazionale"
- si basa su informazioni a priori, innate ed acquisite
- l'informazione a priori subentra a tutti i livelli, dalle caratteristiche dei recettori a vincoli sull'interpretazione
- è difficilmente imitabile da un sistema artificiale ma si possono imitare alcune idee e procedure
- paradigmi 3D computer vision
- ricostruzionista
- la visione è un processo ben definito che implica il ricavare da una o più immagini una descrizione 3D quantitativa
- si passa attraverso rappresentazioni intermedie:
- input image
- primal sketch
- 2.5D sketch
- 3D model representation
- qualitativo
- descrizione qualitativa di oggetti o scene
- è inutile rappresentare geometrie per compiti che non ne richiedono la valutazione
- queste descrizioni sono meno sensibili a perturbazioni e rumore
- purposivism
- il punto chiave è identificare l'obiettivo
- si cercano e si descrivono solo le informazioni utili a risolvere un problema specifico
- ad esempio per la guida autonoma di un veicolo non occorre una precisa descrizione geometrica dell'ostacolo, basta un tempo di collisione
- ricostruzionista
- applicazioni pratiche elaborazione immagini e computer vision
- sorveglianza, riconoscimento, identificazione, controlli di qualità industriale, OCR, navigazione autonoma, riconoscimento ostacoli, controllo del traffico, classificazione immagini satellitari, telerilevamento, ricerca database immagini, diagnosi medica, ricostruzioni modelli 3D, applicazioni multimediali
- tecniche ed algoritmi informatici per modificare immagini allo
scopo di:
- elaborazione di immagini digitali
- immagine digitale
- matrice bidimensionale NxM dove ogni elemento (pixel = picture element) è una misura di segnale (intensità luminosa, componenti di colore)
- campionamento
- il sensore della telecamera registra il segnale ad intervalli discreti δx δy
- teorema del campionamento
- se vxmax e vymax corrispondono alle
massime frequenze x ed y del segnale, per non avere perdità di
informazione si dovrà avere:
- vcx = 1/δx ≥ 2 vxmax
- vcy = 1/δy ≥ 2 vymax
- non possiamo ricostruire frequenze superiori a 0.5 pixel
- se vxmax e vymax corrispondono alle
massime frequenze x ed y del segnale, per non avere perdità di
informazione si dovrà avere:
- aliasing
- deformazione di linee che appaiono divise in pixel
- se la frequenza di campionamento è troppo bassa si possono creare artefatti
- si può limitare con
- filtro passa basso (ottico o digitale)
- interpolazione
- filtro passa basso (ottico o digitale)
- ricampionamento
- a seconda dell'analisi richiesta si può lavorare su rappresentazioni con risoluzioni differenti
- la scala di interesse per un'applicazione corrisponde alle dimensioni dei dettagli da interpretare
- interpolazione
- processo che permette di elaborare una risoluzione continua di un'immagine NxM, o almeno subpixel
- quantizzazione
- conversione del segnale continuo misurato dal sensore in un valore discreto (normalmente potenze di 2)
- si usa solitamente 1 byte (8 bit, 256 livelli) per ogni
componente di colore:
- Grayscale 8 bit, Grayscale 16 bit, RGB 24 bit, RGB 32 bit (alpha), binarie 2bit
- nelle immagini RGB ad ogni pixel corrisponde un vettore F(x,y) di tre componenti (Red, Green, Blue), i filtraggi possono essere fatti indipendentemente su ogni canale
- legge di Grassman
- si verifica sperimentalmente che ogni radiazione elettromagnetica che entra nell'occhio può essere classificata mediante una terna di numeri che rappresentano le attivazioni dei tre tipi di coni della retina e che queste terne di numeri godono di proprietà additiva lineare.
- spazio del tristimolo
- spazio tridimensionale nel quale vengono rappresentate le componenti RGB (vettori Red, Green, Blue - tricromia)
- il sistema di riferimento dello spazio del tristimolo così definito è detto fondamentale
- gli spazi visti sono non lineari per la percezione, cioè differenze numeriche non corrispondono a differenze in percezione
- spazio HSV (Hue Saturation Value) o HSL (Hue Saturation
Lightness)
- modello alternativo a RGB o CMYK molto più vicino al modo di vedere umano
- conversione RGB-Grayscale
- Y=0.299R + 0.587G + 0.114B
- i pesi riflettono la sensitività dell'occhio umano ai colori primari
- multirisoluzione
- si tengono in memoria rappresentazioni a diverse risoluzioni così da poter analizzare ogni fenomeno alla scala adatta
- sensori
- CCD (Charge Coupled Devices)
- la carica di ogni pixel viene raccolta a turno per essere convertita in tensione, memorizzata in un buffer e fatta uscire dal chip sequenzialmente (tipicamente come segnale analogico, poi digitalizzato dal framegrabber)
- i pixel acquisiti con CCD presentano una piccola autocovarianza lungo la direzione orizzontale
- CMOS (Complemetary Metal Oxide Semiconductor)
- ogni pixel ha un convertitore carica/tensione e digitalizzatore
- l'output è già in formato digitale
- CCD (Charge Coupled Devices)
- rumore
- i sensori sono tipicamente rumorosi
- N immagini della stessa scena possono presentare variazioni dovute al rumore
- stima della deviazione standard dei valore del pixel (i,j) su n
acquisizioni:
- σ(i,j) = ((1/(n-1)) Σk=0,n-1 (E0(i,j) -
Ek(i,j))2)1/2
- E0(i,j) = (1/n) Σk=0,n-1 Ek(i,j)
- σ(i,j) = ((1/(n-1)) Σk=0,n-1 (E0(i,j) -
Ek(i,j))2)1/2
- stima della covarianza tra pixel
- CEE(i',j') = c Σi=0,Ni'Σj=0,Nj' (E(i,j) - E0(i,j))(E(i+i',j+j') - E0(i+i',j+j'))
- è tipicamente modellato come addittivo Imis(i,j) = I(i,j) + w(i,j)
- deve essere ridotto o eliminato per ricavare informazione
- è classificato in:
- gaussiano
- descritto per ogni singolo pixel da una variabile random con valor medio e deviazione standard noti
- impulsivo
- comparsa di pixel casuali nell'immagine, si vedono pixel bianchi e neri
- sale e pepe
- simulazione sintetica di rumore impulsivo
- gaussiano
- i sensori sono tipicamente rumorosi
- immagini mediche
- X-RAY
- immagine assorbimento, alta risoluzione
- CT o TAC (Tomografia Assiale Computerizzata)
- acquisizione da un sensore rotante a raggi X
- utilizza algoritmi di ricostruzione per generare pile di immagini XY spazialmente referenziate
- US - Ecografia
- riflessione di onde acustiche
- PET (Tomografia a Positroni)
- SPECT (Tomografia a Fotone Singolo)
- X-RAY
- immagini range (depth images, depth maps)
- ricostruzione della scena tridimensionale
- ogni valore di pixel codifica una distanza
- sensori:
- attivi (inviano un segnale alla scena)
- radar, sonar, triangolazione, luce strutturata, effetto moiré, focus/defocus
- passivi (ricostruzione 3D da diverse immagini - Shape from X)
- attivi (inviano un segnale alla scena)
- immagine digitale
- trasformazioni dell'immagine
- gray level transformation
- mappa globale che cambia il livello di grigio: s=T(r)
- look-up table (LUT)
- tabella che mappa la trasformazione tra livelli di grigio o tra livelli di grigio e colori
- soglia/binarizzazione
- trasforma l'immagine grayscale in una binaria (mette a zero i pixel con valore sotto una certa soglia e ad 1 i rimanenti).
- istogramma (histogram)
- funzione discreta definita sul range dei livelli di grigio
- Hl = nl / n
- nl = numero di occorrenze del livello di grigio l (stima della probabilità di occorrenza)
- n = numero totale di pixel
- mostra lo sfruttamento del range dinamico a disposizione
- consente di individuare valori per sogliatura corrispondenti presumibilmente ad oggetti
- contrast stretching
- "stira" l'istogramma in modo tale che l'immagine utilizzi tutti gli L livelli di grigio
- f'(i,j) = (L-1) x (f(i,j) - min) / (max - min)
- f(i,j) = livello di grigio nel punto (i,j) dell'immagine originale
- max = massimo livello di grigio dell'immagine originale
- min = minimo livello di grigio dell'immagine originale
- histogram equalization
- trasformazione che mappa i livelli in modo che l'istogramma dell'immagine trasformata sia costante
- se il range dinamico è alto può introdurre artefatti
- sk = (L - 1) Σj=0,k nj/n
- L = livelli di grigio dell'immagine originale
- 0 ≤ k ≤ L
- n = numero totale di pixel
- nj = numero totale di pixel col livello j
- histogram specification
- trasformazione che mappa i livelli in modo che l'istogramma dell'immagine trasformata tenda ad un istogramma noto
- histogram matching
- si rendono similari gli istogrammi di immagini non corrispondenti (immagini MRI)
- somma / media /sottrazione
- può essere utile per eliminare il rumore di acquisizione
- la sottrazione si usa tipicamente per eliminare lo sfondo (es: teleconferenze)
- elaborazioni locali
- per semplicità si considera una finestra quadrata di dimensioni dispari W=2N+1 nell'intorno di un dato pixel I(x,y)
- convoluzione
- è una trasformazione lineare
- utilizza il kernel (matrice) per mediare i valori dei pixel intorno a quello di interesse
- IF(i,j) = I * A = Σh=-M,MΣk=-M,M A(h,k)I(i-h,j-k)
- A = kernel (nucleo), è la matrice di pesi con cui mediare i valori dei pixel intorno a quello di interesse
- la convoluzione è esclusa su un bordo di spessore M=W/2-1
- esempio
- se A ha dimesioni 3x3, per un punto generico (i,j) non sul bordo:
- IF(x,y)(i,j) = A(-1,-1)I(i+1,j+1) + A(0,-1)I(i,j+1)
+ A(1,-1)I(i-1,j+1) + A(-1,0)I(i+1,j) + A(0,0)I(i,j) +
A(1,0)I(i-1,j) + A(-1,1)I(i+1,j-1) + A(0,1)I(i,j-1) +
A(1,1)I(i-1,j-1)
- le coordinate di A si considerano rispetto al punto centrale della matrice
- correlazione
- è una forma di riconoscimento, restituisce una misura della "somiglianza" con il pattern A
- posso cercare di riconoscere un modello in un'immagine cercando il massimo della correlazione
- C(i,j) = Σh=-M,MΣk=-M,M A(h,k)I(i+h,j+k)
- esempio
- se A ha dimesioni 3x3, per un punto generico (i,j) non sul bordo:
- C(i,j) = A(-1,-1)I(i-1,j-1) + A(0,-1)I(i,j-1) + A(1,-1)I(i,j-1)
+ A(-1,0)I(i-1,j) + A(0,0)I(i,j) + A(1,0)I(i+1,j) +
A(-1,1)I(i-1,j+1) + A(0,1)I(i,j+1) + A(1,1)I(i+1,j+1)
- le coordinate di A si considerano rispetto al punto centrale della matrice
- filtri lineari
- sono i filtri media e gaussiano
- eliminano il rumore, riducono i dettagli ed attenuano i contorni
- utilizzati per eliminare il rumore scorrelato
- non adatti per il rumore impulsivo e salt and pepper
- filtri di smoothing (integrativi)
- scopo
- eliminare il rumore, evitare aliasing
- mean filter
- media non pesata dei pixel vicini compreso il pixel considerato
- un filtro mean 3x3 calcola il nuovo valore di un pixel facendo la media di tutti i valori presenti nella finestra 3x3 centrata sul pixel
- kernel
- tutti i valori a 1/(W*W)
- riduce le differenze locali, cioè le alte frequenze nel segnale
- la somma di tutte i termini del kernel deve dare 1 (per evitare amplificazione)
- filtro gaussiano
- si scelgono i pesi proporzionali ad una gaussiana 2D
- ha simmetria circolare (il filtro mean introduceva direzioni privilegiate)
- massimo centrale (ridotto l'effetto sugli edge)
- il kernel gaussiano è separabile, è cioè ottenibile con la
composizione di due trasformate 1D con un risparmio computazionale:
- I * Gxy = (I * Gx) * Gy
- la composizione di due convoluzioni con gaussiana σ equivale (a meno di un fattore di scala) ad una convoluzione con gaussiana σ' = Sqrt(2σ)
- scopo
- filtri non lineari
- utilizzati per il rumore impulsivo e salt and pepper
- filtro mediano
- privilegia il valore più diffuso nel vicinato
- calcola la mediana dei valori in una finestra centrata sul pixel
- un filtro mediano 3x3 calcola il nuovo valore di un pixel cercando la mediana di tutti i valori presenti nella finestra 3x3 centrata sul pixel (ordina i valori e prende il centrale)
- introduce artefatti (piccole regioni omogenee)
- k-closest
- come per il mediano considero i valori nell'intorno ordinati e faccio la media dei k più vicini (quelli col valore di grigio più vicino a quello del pixel considerato)
- crea meno artefatti del filtro mediano ma ha un'elevato costo computazionale per l'ordinamento del vettore ed il calcolo delle distanze
- multi-finestra
- fa medie in diverse finestre contenenti il punto e si assume come valore la media nella finestra con la varianza minore
- filtri derivativi
- calcolano le derivate
- enfatizzano i livelli di grigio
- esaltano/trovano gli edges
- trasformazioni lineari
- scaling, zooming, rotazione, traslazione
- si operano attraverso il prodotto tra matrici
- gray level transformation
- analisi in frequenza
- trasformata di fourier
- è una funzione complessa
- per un segnale continuo descrive l'andamento in frequenza
- F(u) = ∫-∞,+∞ (f(x) e-j2πux dx) = R(u) + jI(u)
- spettro di fourier
- |F(u)| = Sqrt(R2(u) + I2(u))
- fase di fourier
- Φ(u) = tan-1(I(u)/R(u))
- spettro di potenza
- P(u) = |F(u)|2 = R2(u) + I2(u)
- lo spettro di potenza presenta rispetto all'immagine uno sfasamento di 90 gradi (è ruotato in senso antiorario di 90 gradi)
- lo spettro di potenza non cambia per traslazioni orizzontali o verticali dell'immagine
- se l'immagine viene ruotata di un angolo anche lo spettro di potenza ruota dello stesso angolo (mantenendo comunque lo sfasamento di 90 gradi)
- i punti dello spettro di potenza sono simmetrici rispetto al punto centrale
- esempi
- di un punto è un punto
- di una linea verticale è una linea orizzontale (c'è sempre uno sfasamento di 90 gradi - ruota a sinistra di 90 gradi)
- di una linea orizzontale è una linea verticale
- di righe verticali regolari è una linea punteggiata orizzontale con massimi periodici
- di righe orizzontali è una linea punteggiata verticale con massimi periodici
- nello spazio delle frequenze la convoluzione con un kernel equivale alla moltiplicazione con la sua trasformata
- la trasformata del prodotto di convoluzione di due funzioni
corrisponde al prodotto delle trasformate
- f(x) * g(x) ⇔ F(u)G(u)
- il prodotto di due funzioni corrisponde alla convoluzione delle
frasformate
- f(x)g(x) ⇔ F(u) * G(u)
- DFT (Direct Fourier Tranform)
- calcolo computazionalmente complesso
- F(u,v) = (1 / MN) Σx=0,M-1Σy=0,N-1
f(x)ej2π((ux/M) + (uy/N))
- x,y variabili intere con valori rispettivamente 0,1,...,M-1 e
0,1,...,N-1 corrispondenti ai campionamenti a posizioni
xsx ysy
- sx, sy sono i passi di campionamento (dimensione del pixel)
- x,y variabili intere con valori rispettivamente 0,1,...,M-1 e
0,1,...,N-1 corrispondenti ai campionamenti a posizioni
xsx ysy
- rappresenta l'andamento della funzione in frequenza, campionato a valori Δu = 1/Msx ; Δv = 1/Nsy
- FFT (Fast Fourier Tranform)
- approccio divide et impera
- necessita di dati di partenza di dimensioni potenza di 2
- complessità da N2 a Nlog2N
- proprietà
- traslazione (cambia solo la fase), periodicità, simmetria, rotazione (conserva l'angolo), distributività, scala
- funzione delta di Dirac
- campionare equivale a moltiplicare con un treno di funzioni delta di Dirac
- ∫-∞,+∞ f(x)δ(x-x0)dx = f(x0)
- convoluzione con fourier
- la trasformata della funzione di campionamento è ancora una serie di delta con periodo 1/L
- la trasformata della funzione campionata è convoluzione di delta con lo spettro
- per definizione equivale a copiare la funzione nella posizione
di ogni impulso
- se le curve non si intersecano la trasformazione è reversibile
- se le curve si sovrappongono la ricostruzione sarà poco
accurata (aliasing)
- la frequenza di campionamento deve rispettare il criterio f ≥ 2Fmax
- filtraggio nello spazio delle frequenze
- eliminazione frequenze particolari
- analisi di tessitura
- non conviene per blurring o edges
- filtro fourier gaussiano
- trasformata fourier gaussiana con ampiezza σ è una gaussiana con ampiezza σ'=1/σ
- banda non limitata: c'è sempre aliasing se campionata
- fourier: gaussiane ripetute a d=1/pixel
- il campionamento è una buona approssimazione (aliasing
trascurabile) quando 5σ che contiene il 98.86 del segnale sta dento
il limite di Nyquist:
- fc = 1/pixel ≥ 2/(5σ')
- 5σ = 5/σ
- σ ≥ 0.4 pixel
- piramide gaussiana
- si costruiscono copie dell'immagine originale a differenti scale ridotte
- ad ogni livello la dimensione è 1/4 della precedente
- ad ogni passaggio ricampioniamo evitando l'aliasing con una gaussiana con σ di 1-2 pixel
- applicazioni: ricerca di pattern, ricerca di immagini simili, inseguimento di oggetti, analisi della tessitura
- trasformata di fourier
- features
- image features
- parti dell'immagine localizzabili, identificabili, con un significato: punti, linee, contorni, regioni
- trovare image features è un compito a basso livello
- trovare le features può essere "visione" se ho delle informazioni a priori (es: sapere che le regioni scure sono cellule in un'immagine presa da un vetrino)
- segmentazione
- suddivisione dell'immagine in parti costituenti
- presuppone un'ipotesi sul tipo di scena
- edges
- punti in cui l'immagine presenta elevate variazioni locali
- si dividono in
- step (gradino _∏_)
- ridge (picco _∩_)
- roof (tetto ∧)
- edgel (edge di un singolo punto)
- edge detection
- individuazione degli edge dell'immagine escludendo quelli dovuti al rumore
- tipicamente avviene in tre fasi:
- eliminazione rumore (filtro gaussiano)
- edge enhancement (filtri derivativi)
- localizazzione degli edge (soglia sull'uscita del filtro)
- criteri ottimali
- buon riconoscimento: minimizzazione falsi positivi, massimizzazione punti corretti
- buona localizzazione: la posizione risultante deve essere la più vicina possibile a quella reale
- evitare doppi riconoscimenti: un contorno non deve essere contato due volte
- si utilizzano le derivate
- derivate e rumore
- le derivate sono molto sensibili al rumore
- per ridurre il rumore si applica un filtro di smoothing
- anziché filtrare e poi derivare possiamo anche applicare un
filtro che includa lo smoothing:
- (δ/δx) (h * f) = ((δ/δx)h) * f
- gli edge si trovano nei massimi di questa funzione
- f = segnale
- h = kernel
- h * f = convoluzione
- (δ/δx) (h * f) = ((δ/δx)h) * f
- sicuramente andranno eliminate le frequenze maggiori del doppio della frequenza di campionamento, poi dipende dal rumore
- gradiente
- grad(x) = (δI/δx δI/δy)T
- un edge è un punto caratterizzato da un alto valore della
norma:
- E(x,y) = |grad(x)| = Sqrt((δI/δx)2 + (δI/δy)2)
- il massimo del contrasto si ha lungo la normale dell'edge:
- n(x,y) = arctan(grady(x,y)/gradx(x,y))
- estrazione edges da gradiente
- metodo
- 1. calcolo delle derivate
- 2. calcolo l'intensità del gradiente
- 3. applico la soglia
- per evitare doppi bordi posso aumentare lo smoothing
- metodo
- altre maschere per il calcolo del gradiente:
- Roberts (direzioni diagonali)
- g1 = {1, -1 ; -1, 1}
- g2 = {-1, 1 ; 1, -1}
- Sobel (include smoothing laterali)
- g1 = {1, -2, -1 ; 0, 0, 0 ; 1, 2, 1}
- g2 = {-1, 0, 1 ; -2, 0, 2 ; -1, 0, 1}
- Prewitt
- g1 = {-1, -1, -1 ; 0, 0, 0 ; 1, 1, 1}
- g2 = {-1, 0, 1 ; -1, 0, 1 ; -1, 0, 1}
- Roberts (direzioni diagonali)
- le maschere sono un template dell'edge
- si possono usare anche maschere in più direzioni, calcolare le risposte, sommarle e trovare i massimi direzionali
- laplaciano
- ∇2f = (δ2f/δx2) + (δ2f/δy2)
- possiamo localizzare gli edges dove si annulla la derivata seconda (zero crossing)
- edge detector Marr-Hildreth
- applicare il laplaciano all'immagine filtrata equivale a convolvere col filtro LoG (laplaciano del kernel gaussiano)
- (δ2/δx2) (h * f) = ((δ2/δx2)h) * f)
- E(x,y) = [∇2G(x,y)] * I(x,y)
- algoritmo di Canny
- 4 passi:
- 1. filtro gaussiano per eliminare il rumore
- 2. gradiente (edge enhancement)
- calcolare il gradiente con maschere 1D
- ricavare l'intensità del gradiente E(x,y)
- ricavare la direzione dell'edge n
- la direzione del gradiente è normale all'edge
- le componenti della direzione si ottengono dalle derivate lungo la direzione x ed y
- esempio: -1, 1 = freccia in alto a sinistra; 0, 2 = freccia in basso
- 3. non maxima suppression
- considera la direzione quantizzata (0º, 45º, 90º, 135º) più vicina ad n (quella che meglio approssima E0(i,j), la normale all'edge), se nel punto E(x,y) è minore di almeno uno dei due vicini lungo n, pone EN(x,y)=0, altrimenti EN(x,y)=E(x,y)
- 4. sogliatura (tresholding)
- tengo solo i pixel con EN(x,y) > τ
- 4 passi:
- Histeresis thresholding
- è un algoritmo di "edge following" o "edge linking" utilizzato per riconoscere linee e contorni
- genera catene di edge point ordinati e connessi
- si adatta localmente a segnali più deboli
- se Em(x,y)>τ1, segui i pixel connessi (massimi non sopressi) in entrambe le direzioni perpendicolari ad n, finché Em(x,y) > τ2 marca i punti visitati e salvane la lista
- valutazione edge detectors
- si devono considerare:
- probabilità di falsi edge
- probabilità di missing edges;
- errore nella stima della direzione
- distanza dall?edge desiderato
- distorsione introdotta da angoli e giunzioni
- figura di merito (Pratt)
- funzione che calcola qualità di un edge detector
- si devono considerare:
- histogram of edge directions
- istogramma delle direzioni degli edge
- per ogni direzione quantizzata vengono riportati in istogramma il numero di edge con quella direzione
- la direzione degli edge caratterizza il tipo di immagine
- corner detection
- edge interessanti per definire contorni di regioni
- gli angoli possono essere seguiti in immagini diverse
- algoritmo di Harris
- sfrutta la matrice delle derivate direzionali
- C = {Σp∈NEx2,
Σp∈NExEy ;
Σp∈NExEy,
Σp∈NEy2} =
R-1{λ1, 0 ; 0, λ2}R
- matrice simmetrica definita positiva
- gli autovalori sono non negativi
- è diagonalizzabile mediante una rotazione
- si ha un corner quando λ1 ≥ λ2 e λ2 è abbastanza grande
- il valore degli autovalori mi da la forma dell'edge
- λ1 = λ2 = 0 : grigio costante
- λ1 alto, λ2 = 0 : step edge lungo x
- λ1 alto, λ2 circa nullo : step edge lungo direzione generica
- λ1 alto, λ2 alto : angoli (corner) o pattern complesso
- matrice simmetrica definita positiva
- algoritmo
- calcola il gradiente su tutti i pixel, per ciascuno:
- calcola la matrice C su finestre quadrate Q
- calcola l'autovalore λ2
- salva le coordinate dei punti con λ2 > τ in lista L
- ordina L in modo decrescente
- scorre L e per ogni punto elimina eventuali successivi vicini (vicinato definito da Q)
- calcola il gradiente su tutti i pixel, per ciascuno:
- SSD (Sum of Squared Differences) - somma delle differenze
quadratiche
- utilizzata per misurare la somiglianza
- minΔxΔySSD(i,j) = minΔxΔy Σh=-N,NΣk=-N,N {IL(i+h,j+k) - IR(i+h-Δx,j+k-Δy)}2
- posso salvare le differenze quadratiche tra i livelli in una look-up table e fare solo letture in tabella
- features e scala
- edges, corner, features, sono in genere calcolati con filtri derivativi delle dimensioni di pochi pixel (3,5)
- catturano solo variazioni di grigio rilevanti a quella scala
- posso non sapere a priori qual'è la scala di analisi del fenomeno, uso quindi l'analisi multirisoluzione (piramide gaussiana)
- decomposizione immagine
- esistono altri metodi per la multirisoluzione
- posso memorizzare solo le differenze tra le immagini a diverse scale e non l'immagine intera
- wavelet trasform: si utilizzano filtri che formano una base ortonormale
- image features
- fitting
- trasformata di Hough
- trasforma il riconoscimento di curve in un problema di massimo nello spazio parametrico
- risolve contemporaneamente i seguenti problemi: raggruppamento, parametri curve, numero curve
- per le linee:
- y=mx+n ci si sposta nel piano parametrico
- ogni punto (xi,yi) è una retta del piano m,n di equazione n=-xim+yi
- la retta che passa per i punti è rappresentata dall'intersezione delle rette corrispondenti nel piano parametrico
- in coordinate polari
- ρ=xcosθ+ysinθ
- ogni punto nello spazio immagine è una sinusoide nello spazio dei parametri ρ, θ
- i massimi maggiori della soglia corrispondono alle rette presenti nell'immagine
- è applicabile anche ad altre curve (coniche) ma la complessità cresce con il numero di parametri
- è un algoritmo di voting, si sceglie il candidato con più voti
- è più efficiente del confronto diretto dei pattern
- il risultato è fortemente legato a rumore su edge detection
- outliers
- punti isolati che tendono a far deviare le linee che fanno il fit di un gruppo di punti
- m-stimatori
- funzioni che assomigliano alla distanza quadratica per i punti vicini e diventano costanti per quelli lontani
- servono a minimizzare l'effetto degli outliers durante il fit
- regressione lineare classica
- soluzione analitica semplice in forma chiusa
- suppone y variabile misurata ed x senza errore ma per le immagini non è vero
- minimizza la somma delle distanze quadratiche in verticale!
- regressione totale
- risolve i problemi della regressione lineare
- si fa il fit su un modello polare xsinθ+ycosθ-ρ=0
- si minimizza la distanza quadratica punti-retta D=Σi(cosθxi + sinθyi - ρ)2
- least median squares regression
- funziona anche se quasi metà dei punti sono outliers
- si selezionano sottoinsiemi dei punti e si fa il fit su essi:
- 1. scegli K punti dell'insieme di N
- 2. esegui il fit MQ su K punti
- 3. calcola la mediana dei residui quadratici
- 4. ripeti finché la mediana non è sufficientemente bassa
- fit incrementale
- parto da un punto e lo metto in lista L
- aggiungo iterativamente punti a L (se uso edge chains e successivi)
- eseguo il fit della miglior retta su L
- quando il residuo è sopra una soglia, esco dal ciclo
- inizio una nuova lista
- risultato: tutti gli edge sono associati a segmenti
- k-means
- ipotizzo la presenza di k rette, inizializzate con parametri casuali o da una precedente stima
- fino a convergenza:
- alloco ogni punto alla retta più vicina
- ricalcolo i parametri con un fit
- non è detto che la soluzione sia quella ottimale
- coniche
- retta
- curva di primo grado
- ax + by + c = 0
- -a/b = coefficiente angolare
- coniche
- ax2 + bxy + cy2 + dx + ey + f = 0
- parabola b2 = ac
- ellisse b2 < a ; a ≠ c ; c e/o b ≠ 0
- iperbole b2 > ac
- circonferenza b2 < ac ; a = c ; b = 0
- equazione: (x - xc)2 + (y - yc)2 = r2
- se a + c = 0 è un'iperbole rettangolare
- retta
- fit di coniche
- la distanza minima non corrisponde più alla distanza euclidea dei punti della curva
- si utilizza la distanza algebrica
- adattamento di curve generiche
- uso un contorno p(s) parametrizzato dalla lunghezza dell'arco di curva
- cerco di adattarlo all'immagine facendolo evolvere con una dinamica
- definisco un potenziale E = Ec + Eimm
- un termine mantiene continua e liscia la curva
- un termine tende a far convergere la curva verso gli edge (o altre features significative)
- algoritmo greedy
- punti su posizioni intere, per ogni interazione:
- calcola il termine del potenziale sull'intorno della posizione attuale
- sposta ogni nodo nel punto di minimo potenziale
- trova i massimi della curvatura e pone βi nullo
- termina quando un numero prefissato di nodi sta in un minimo locale
- trasformata di Hough
- regioni
- sottoinsieme (cluster) dei pixel dell'immagine definito da una comune proprietà (classificati)
- ROI (Region Of Interest)
- zona dove suppongo ci sia qualcosa (spesso definita a mano)
- strutture dati per regioni
- matrice con etichette
- lista di coordinate
- pixel e relazioni spaziali
- ad un oggetto corrisponde una regione connessa
- vicinato
- ogni pixel può essere considerato connesso con quelli adiacenti (4-neighbor, 8-neighbor)
- grafo
- l'immagine digitale può essere vista come un grafo
- ogni pixel è un nodo ed ogni relazione di vicinato un arco
- l'immagine digitale può essere vista come un grafo
- pixel connessi
- lo sono se hanno una relazione di vicinato ed hanno qualche proprietà in comune
- percorso
- sequenza di punti connessi
- componente connessa
- insieme S di pixel tale che presi due punti qualsiasi esiste sempre un percorso che li unisce
- l'appartenere ad una componente connessa è una relazione di equivalenza (riflessiva, simmetrica, transitiva)
- sfondo di S
- insieme delle componenti connesse di S (complemento di S) che ha pixel vicini alla componente considerata
- soglie locali
- si utilizzano in caso di variazioni della luminosità
- si divide l'immagine in regioni e si eseguono sogliature indipendenti
- trovare regioni connesse
- algoritmo di etichettatura per trovare regioni connesse
- si scandisce l'immagine e per ogni pixel:
- se è connesso con uno o più pixel con la stessa etichetta, gli viene assegnata quest'ultima
- altrimenti se è connesso con due pixel con etichette diverse, gli si assegna una di queste e si registra l'equivalenza
- altrimenti si assegna una nuova etichetta
- al termine si effettua una nuova scansione durante la quale ogni etichetta è sostituita con quella della classe di equivalenza
- si scandisce l'immagine e per ogni pixel:
- region growing (visita di un grafo in profondità)
- definisco una lista di punti di frontiera F e ci metto il punto
iniziale (seme)
- i semi possono anche essere scelti da opportuni algoritmi
- per ogni punto p di frontiera:
- considero i vicini, se non sono classificati e rispettano la proprietà, li classifico nella regione e li inserisco in una lista L
- pongo F=L, azzero L e itero nuovamente finché F non è nulla
- definisco una lista di punti di frontiera F e ci metto il punto
iniziale (seme)
- split and merge (dividi ed unisci)
- dividi l'immagine in blocchi W/2 x H/2 finché la proprietà che uso per segmentare non è costante (struttura tipo quadtree)
- unisci le regioni vicine con valori compatibili
- merging
- scorro i pixel e creo un grafo definito dalle adiacenze delle regioni (RAG)
- considero le regioni adiacenti e se sono simili le unisco, modificando il RAG
- ripeto finché non si eseguono più operazioni
- algoritmo di etichettatura per trovare regioni connesse
- processing di regioni binarie
- una regione segmentata si può considerare come un'immagine binaria B appartenente (non appartenente) alla regione
- topologia
- studio delle proprietà non influenzate dalle deformazioni
- numero di Eulero
- E=C-H
- C = numero di componenti connesse
- H = numero di buchi
- E=C-H
- mappe distanza
- distanza tra regioni o pixel
- può essere utile classificare i pixel sulla base della loro distanza da un pixel o una linea
- si può usare un algoritmo iterativo ed una mappa di distanze
- scheletro
- applico la Medial Axis transform (MAT)
- calcolo la distanza dal bordo (dallo sfondo) e ne estraggo i massimi nell'intorno
- è sensibile al rumore
- applico la Medial Axis transform (MAT)
- thinning
- riduzione ad un pixel di spessore
- può essere fatta iterativamente dal bordo esterno, ma:
- deve preservare la topologia (numero di eulero)
- deve preservare gli estremi
- i punti che non possono essere rimossi vengono detti punti semplici
- morfologia matematica
- operazioni sulle regioni relative alla chiusura di buchi, eliminazione di regioni piccole,...
- elaborazioni basate sulla teoria degli insiemi
- elemento di struttura H
- insieme che definisce dimensione e forma del filtro
- è utilizzato per eseguire operazioni logiche con l'immagine:
- dilatazione (unione) B ⊕ H = {(x,y) | H(x,y) ∩ B ≠
∅}
- H deve avere almeno un elemento in comune con B
- erosione (intersezione) B Θ H = {(x,y) | H(x,y) ⊆ B}
- è l'insieme dei punti di B tali che H traslato in questi punti è interamente contenuto in B
- apertura = erosione + dilatazione
- chiusura = dilatazione + erosione
- dilatazione (unione) B ⊕ H = {(x,y) | H(x,y) ∩ B ≠
∅}
- geometria proiettiva - formazione immagine
- voxel (volume pixel)
- unità della informazione che appare in forma tridimensionale ed è pari a un pixel volumetrico
- metodi di acquisizione 3D
- contatto
- non distruttivi
- bracci robotizzati
- distruttivi
- sezionatura
- non distruttivi
- non contatto
- riflessivi
- non ottici
- microonde
- sonar
- ottici
- passivi
- stereo
- moto
- silhouette
- shading
- focus/defocus
- ...
- attivi (immagini range)
- luce strutturata
- triangolazione
- interferometria
- ...
- tempo di volo
- luce strutturata
- passivi
- non ottici
- trasmissivi
- tomografia computerizzata
- riflessivi
- contatto
- Shape from X
- ricostruzione 3D a partire da immagini ottiche standard
- X sta al posto della feature o constraint usata:
- stereo (metodo passivo, richiede 2 o più immagini)
- moto (metodo passivo/attivo, richiede una sequenza di immagini)
- focus/defocus (metodo attivo, richiede 2 o più immagini)
- texture (metodo passivo, richiede una singola immagine)
- contorni (metodo passivo, richiede una singola immagine)
- shading (metodo passivo, richiede una singola immagine)
- l'immagine su telecamera dipende da
- parametri ottici della lente
- fotometria della scena
- geometria della scena
- effetti della digitalizzazione
- messa a fuoco
- un immagine è a fuoco se tutta la luce emessa da un punto della scena arriva sullo stesso punto del piano immagine
- per la messa a fuoco si possono utilizzare:
- sistema di lenti
- sistema reale
- utilizza un'ottica abbastanza complessa
- raccoglie luce da un'apertura finita
- camera pinhole
- camera ideale con apertura infinitesima
- si utilizza come modello approssimato di un sistema reale
- si trascurano:
- gli effetti della sfuocatura dovuti ad un'apertura troppo grande
- gli effetti della diffrazione dovuti ad un'apertura troppo piccola
- la scarsa illuminazione
- il modello pinhole è stato introdotto sostanzialmente da Brunelleschi nel 15 secolo (prospettiva centrale)
- la dimensione apparente degli oggetti dipende dalla distanza
- immagini di linee parallele si incontrano nei punti di fuga
- punti di fuga di rette complanari sono collineari e formano orizzonte
- sistema di lenti
- modello ottico della telecamera
- scena
- scena 3D da ripresa con la telecamera
- un punto ha coordinate P(X,Y,Z)
- piano immagine
- corrisponde alla superficie del sensore
- un punto ha coordinate p(x,y,f) o p(x,y) visto che f è costante
- si trova "dietro" il centro ottico e l'immagine è rovesciata rispetto alla scena ma si può utilizzare un modello equivalente in cui il piano immagine si trova davanti al centro ottico e l'immagine risulta non rovesciata
- centro ottico
- punto corrispondente al foro della telecamera pinhole
- asse ottico
- passa per il centro ottico e corrisponde all'asse Z della scena o all'asse z del piano immagine
- distanza focale f
- minima distanza tra il centro ottico ed il piano immagine
- scena
- lenti sottili
- i raggi paralleli da un lato si incontrano nel fuoco dall'altro
- i raggi che partono dal fuoco diventano paralleli all'asse ottico dall'altro
- equazione fondamentale delle lenti sottili
- 1/p + 1/q = 1/f
- f = distanza focale
- p = distanza di un punto P dalla lente lungo l'asse ottico
- q = distanza del punto p (ottenuto come intersezione dei raggi provenienti da P) dalla lente lungo l'asse ottico
- 1/p + 1/q = 1/f
- campo visivo (field of view)
- tan w = d / 2f
- d = diametro effettivo della lente accessibile ai raggi
- f = distanza focale
- w = metà angolo sotteso dal diametro visto dal fuoco
- tan w = d / 2f
- problemi trascurati
- aberrazione sferica
- aberrazione cromatica
- profondità di campo
- radiometria
- radianza L di una superficie
- potenza per unità di area della radiazione emessa (potenza per unità di area per unità di angolo solido emessa da una superficie)
- L = energy / (time * ProjectedArea * SolidAngle)
- irradianza E di una superficie
- potenza per unità di area della radiazione assorbita (potenza per unità di area)
- riflettanza L/E (Bidirectional Reflectance Distribution
Function - BRDF)
- BRDF(θl,φl,θe,φe) = L(θl,φl) / E(θe,φe)
- radianza L di una superficie
- superfici lambertiane
- modello in cui ogni punto della superficie matiene la stessa luminosità da tutte le direzioni di osservazione
- rappresenta bene le superfici opache (non riflettenti)
- L = ρ IT n
- L = radianza della superficie lambertiana
- ρ = surface's albedo (ρ>0 sempre)
- costante dipendente dal materiale
- rapporto della luce riflessa rispetto alla luce incidente
- I = direzione ed intensità della luce incidente
- n = unità normale alla superficie
- IT n > 0 : la superficie è illuminata (non è in ombra)
- angolo solido
- corrisponde all'apertura di un cono, lo si misura in termini di rapporto tra l'area di porzione di superficie intercettata su una sfera con centro nel vertice del cono ed il quadrato del raggio della sfera stessa
- la porzione di area che sottende uno steradiante (sr) corrisponde ad 1/4π della superficie della sfera stessa
- spazio compreso tra una superficie conica con l'elemento di superficie piana perpendicolare all'asse del cono
- δω = (δA cos ψ) / r2
- δA = elemento di superficie
- ψ = angolo piano tra la superficie δA e la superficie perpendicolare all'asse del cono
- r = distanza minima (raggio) tra l'origine del cono e la superficie δA
- equazione fondamentale della formazione di un immagine
radiometrica
- E(p) = L(P) (π/4) (d/f)2 cos4α
- E(p) è la potenza (luminosità, brightness) che arriva sul piano immagine per unità di superficie (punto p)
- l'irradianza alla posizione dell'image pixel è convertita nella luminosità
- l'irradianza è proporzionale alla radianza della scena
- in questo modello la distanza dalla scena non influisce sull'irradianza (in realtà non è vero)
- la luminosità decresce con la quarta potenza del coseno dell'angolo di incidenza (α); per scarse aperture (nelle applicazioni) si trascura
- f/d detto F number: influisce sulla quantità di luce che arriva alla camera
- E(p) = L(P) (π/4) (d/f)2 cos4α
- proiezione prospettica
- è una trasformazione non lineare (non preserva distanze o angoli)
- può essere utile per cercare "invarianti geometrici" utili per il riconoscimento 3D
- posto XYZ sistema di riferimento della scena (telecamera) e xy quello del sensore:
- x = X (f/Z)
- y = Y (f/Z)
- prospettiva debole (weak-perspective)
- proiezione ortografica + scaling
- è applicabile quando la distanza δz tra due punti qualsiasi della scena lungo l'asse ottico sia molto minore della distanza media Z0 (δz < Z0/20)
- x = X (f/Z0)
- y = Y (f/Z0)
- proiezione ortografica
- approssimazione valida per grandi distanze (f, Z → ∞ ⇒ f/Z → 1)
- x = X
- y = Y
- parametri della telecamera
- parametri estrinseci
- qualunque set di parametri geometrici che identificano univocamente la trasformazione tra il sistema di riferimento sconosciuto della telecamera (camera reference frame) ed un sistema di riferimento noto (world reference frame)
- Pc = R(Pw - T)
- Pc = punto P sul piano immagine (camera frame)
- Pw = punto P sulla scena (world frame)
- T = vettore di traslazione che descrive la posizione relativa dell'origine dei due sistemi di riferimento
- R = matrice di rotazione ortogonale 3x3 (RTR =
RRT = I), che riporta i corrispondenti assi dei due
sistemi di riferimento gli uni sugli altri (3 parametri
indipendenti)
- R1 = {1, 0, 0 ; 0, cos α, - sin α ; 0, sin α, cos α }
- R2 = {cos β, 0, -sin β ; 0, 1, 0 ; -sin β, 0, cos β}
- R3 = {cos γ, -sin γ, 0 ; sin γ, cos γ, 0 ; 0, 0, 1}
- i parametri estrinseci sono: T ed R
- parametri intrinseci
- set di parametri necessari a caratterizzare l'ottica, la geometria e le caratteristiche digitali della telecamera
- le telecamere pinhole hanno 3 set di parametri intrinseci:
- proiezione prospettica (l'unico parametro è la lunghezza focale f)
- trasformazione tra le coordinate della telecamera e le coordinate dei pixel
- distorsioni geometriche introdotte dall'ottica
- trascurando le distorsioni geometriche dovute all'ottica:
- x = -(xim - ox)sx
- y = -(yim - oy)sy
- (ox, oy) = posizione in pixel del centro ottico nell'immagine
- (sx, sy) = dimensioni del pixel (in millimetri)
- (xim, yim) = coordinate dell'immagine in pixel (image reference frame)
- x ed y cambiano segno se si usa il modello con il piano immagine davanti al centro ottico (immagine non rovesciata)
- i parametri intrinseci sono: f, (ox, oy), (sx, sy), k1 coefficiente di distorsione radiale (se necessario)
- equazione matriciale lineare per proiezioni prospettiche
- [x1, x2, x3]T =
Mint Mext [Xw, Yw,
Zw, 1]T
- Mint = {-f/sx, 0, ox ; 0
-f/sy oy ; 0 0 1}
- opera la trasformazione tra la scena ed il sistema della telecamera
- Mext = {r11, r12,
r13, -R1TT ;
r21, r22, r23,
-R2TT ; r31,
r32, r33,
-R3TT}
- opera la trasformazione tra il sistema della telecamera e l'immagine
- x1 / x3 = xim
- x2 / x3 = yim
- Mint = {-f/sx, 0, ox ; 0
-f/sy oy ; 0 0 1}
- approssimazioni
- modello a proiezione prospettica (ox = oy
= 0 ; sx = sy = 1)
- M = Mint Mext = {-fr11,
-fr12, -fr13,
fR1TT ; -fr21,
-fr22, -fr23,
fR2TT ; r31,
r32, r33,
-R3TT}
- M = matrice di proiezione
- M = Mint Mext = {-fr11,
-fr12, -fr13,
fR1TT ; -fr21,
-fr22, -fr23,
fR2TT ; r31,
r32, r33,
-R3TT}
- modello weak-perspective
- M = {-fr11, -fr12, -fr13,
fR1TT ; -fr21,
-fr22, -fr23,
fR2TT ; 0, 0, 0,
R3T(P - T)}
- P = centroide dei punti P1 e P2
- M = {-fr11, -fr12, -fr13,
fR1TT ; -fr21,
-fr22, -fr23,
fR2TT ; 0, 0, 0,
R3T(P - T)}
- modello a proiezione prospettica (ox = oy
= 0 ; sx = sy = 1)
- [x1, x2, x3]T =
Mint Mext [Xw, Yw,
Zw, 1]T
- parametri estrinseci
- geometria proiettiva
- piano proiettivo (projective plane)
- estensione del piano con punti all'infinito
- i punti sono rappresentati in coordinate omogenee (terne di numeri)
- p = (X,Y,W) = (aX, aY, AW) punti equivalenti a meno di un fattore di scala
- x = X/W ; y = Y/W
- ogni punto del piano proiettivo corrisponde ad una retta passante per l'origine (origine esclusa)
- vantaggi
- punti all'infinito (o punti ideali)
- dualità con rette nel piano
- comoda rappresentazione per il calcolo di intersezioni, prodotti, ecc.
- retta
- nel piano euclideo: ax + by + c = 0
- nel piano proiettivo: aX + bY + cW = 0
- l = (a,b,c) definisce una retta
- l · p = 0 prodotto scalare
- dualità punto-retta
- p può essere interpretato come punto o come retta passante per il punto l
- intersezione di due linee (prodotto vettoriale)
- P = l1 x l2
- retta passante per due punti
- l = p1 x p2
- collinearità di tre punti
- p3 · (p1 x p2) = 0
- cioè: det(p1 p2 p3) = 0
- punto ideale (all'infinito)
- (X,Y,0)
- linea ideale
- (0,0,c)
- trasformazioni proiettive
- sono le trasformazioni del piano che legano le viste di una stessa scena mediante due differenti camere (pinhole)
- se una quantità è invariante dopo una trasformazione prospettica, può essere usata per il riconoscimento
- all'aumentare della complessità della trasformazione diminuiscono le invarianti
- cross-ratio
- è un rapporto di rapporti
- è invariante per trasformazioni proiettive da P1 a se stesso
- dati 4 punti distinti di P1 in coordinate omogenee
pi = [xi, yi]T
con i = 1,2,3,4; il cross-ratio è definito da:
- c(1,2,3,4) = d(1,2)d(3,4) / d(1,3)d(2,4)
- d(i,j) = xiyj - xjyi ; distanza euclidea tra i punti i e j
- c(1,2,3,4) = d(1,2)d(3,4) / d(1,3)d(2,4)
- piano proiettivo (projective plane)
- voxel (volume pixel)
- calibrazione telecamera
- la calibrazione consiste nel trovare i parametri (intrinseci ed estrinseci) della telecamera data la localizzazione nello spazio 3D di alcuni punti "riconosciuti" nell'immagine
- metodo: scrivere equazioni che legano le coordinate 3D di alcuni punti noti (pattern di calibrazione) alle loro proiezioni sul piano immagine e risolvere rispetto ai parametri
- i parametri intrinseci ed estrinseci della telecamera ci servono per poter ricostruire esattamente la scena, altrimenti si può fare una ricostruzione a meno di un fattore di scala
- la soluzione con SVD prevede 11 parametri indipendenti
(definita a meno di un fattore di scala)
- se N (numero di punti) ≥ 11 ed i punti non sono complanari, il rango della matrice A è 11, si può quindi ricavare la soluzione ai minimi quadrati prendendo N >> 11
- shape from X - ricostruzione 3D
- metodi per la ricostruzione 3D da immagini di intensità
- shape from shading (forma da ombre)
- è un metodo passivo che richiede un unica immagine
- utilizza dei pattern di luce ed ombre per ricavare la forma della superficie in vista
- è utilizzato in astronomia per ricostruire la superficie dei pianeti partendo dalle singole immagini provenienti dalle sonde spaziali
- può essere impiegato per raffinare le superfici ottenute con shape from stereo
- riscriviamo la radianza della superficie lambertiana L = ρiTn come Rρ,i = ρiTn
- Rρ,i è conosciuta o si ricava numericamente con esperimenti
- assunzioni
- 1. il sistema ottico è stato calibrato per compensare l'effetto del cos4α nell'equazione fondamentale per l'irradianza (la radianza della scena coincide con l'irradianza sul piano immagine)
- 2. tutti i punti visibili della superficie ricevono un'illuminazione diretta
- 3. l'oggetto è molto lontano dall'osservatore: si può approssimare con prospettiva debole weak-perspective (x=Xf/Z0 ; y=Yf/Z0)
- 4. l'asse ottico coincide con l'asse Z e Z=Z(x,y)
- equazione fondamentale dello shape from shading
- E(p) = Rρ,i(n)
- l'orientazione della superficie è legata direttamente all'intensità luminosa dei pixel
- mappa di riflettanza
- E(x,y) = Rρ,i(p,q) = (ρ /
Sqrt(1+p2+q2))iT ·
(-p,-q,1)
- p = δZ/δx
- q = δZ/δy
- n(x,y) = (-p(x,y),-q(x,y),1)/Sqrt(1+p2+q2)
- E(x,y) = Rρ,i(p,q) = (ρ /
Sqrt(1+p2+q2))iT ·
(-p,-q,1)
- il problema shape from shading consiste nello stimare p e q da E(x,y), noti i e ρ
- note
- albedo (ρ) ed illuminante (i) non sono necessariamente noti a priori e si possono stimare con un algoritmo che considera l'andamento medio del gradiente nell'immagine
- l'illuminazione su una superficie dipende anche da tutte le altre superfici nella scena
- shape from texture (forma da tessitura)
- la deformazione di singoli texel e le loro variazioni lungo l'immagine creano l'illusione 3-D
- possone essere usate misure di distorsione di texture e di variazione di distorsione (distorsion gradient)
- surface texture (tessitura della superficie)
- superficie creata tramite la ripetizione regolare di elementi o pattern chiamati surface texel
- image texture (tessitura dell'immagine)
- immagine di una surface texture, ripetizione regolare di image texel distorti dalla proiezione lungo l'immagine
- tessiture deterministice (deterministic textures)
- ripetizione fissa di una precisa forma geometrica (cerchio, quadrato, motivo decorativo, ...)
- posso usare la singola deformazione del texel noto come equazione
- tessiture statistiche (statistic textures)
- ripetizione di pattern che cambiano mantenendo fisse alcune proprietà statistiche
- occorre individuare i parametri costanti e valutarne le variazioni
- isotropia
- la probabilità delle features non dipende dall'orientazione delle stesse
- si può usare in assunzione di approssimazione ortografica
- omogeneità
- il numero di features è costante in regioni differenti
- varia in funzione dell'orientazione solo per trasformazioni prospettiche
- distorsioni
- prospettica (perpective distorsion)
- la lunghezza degli assi dell'ellisse scala inversamente alla distanza dalla superficie
- schiacciamento (foreshortening)
- cerchi su un piano non parallelo al piano immagine diventano ellissi
- prospettica (perpective distorsion)
- possibile algoritmo
- si sceglie una rappresentazione della tessitura
- si calcola la distorsione degli elementi di tessitura sull'immagine
- si ricava dalla distorsione l'orientamento della superficie
- shape from stereo
- capacità di ricavare informazione sulla scena 3D a partire da due o più immagini dello stesso soggetto con diverso punto di vista
- l'uomo usa la visione stereo
- distanza tra gli occhi b = 6cm
- per Z=100cm : min δθ = 2.42 10-5 radianti ; δZ = 0.4mm
- per Z=30cm : δZ = 0.036mm
- se si chiude un occhio diminuisce la percezione della profondità ma aumenta il dettaglio
- nell'uomo la visione stereoscopica è un processo bottom-up: avviene a basso livello senza interpretazione a partire dalla sola disparità
- conoscere l'oggetto da trovare non migliora la capacità di vedere gli oggetti negli stereogrammi
- distanza tra gli occhi b = 6cm
- sistemi artificiali
- si usano tipicamente 2 telecamere (coppie di immagini)
- limiti
- occlusioni
- diversi campi visuali
- sistema semplice
- due telecamere parallele con punto di fissazione all'infinito
- disparità
- d = xR - xL
- differenza di coordinate di punti corrispondenti sui piani immagine
- (T + xL - xR) / (Z - f) = T / Z ⇒ Z = f T
/ d
- T = distanza tra i centri ottici OL e xR
- f = distanza focale
- calibrazione
- la ricostruzione implica la calibrazione, occorre conoscere:
- parametri intrinseci
- sono i parametri intrinseci delle due telecamere
- parametri estrinseci
- posizione relativa delle due telecamere
- geometria epipolare (geometria stereo)
- geometria di due telecamere che vedono la stessa scena
- piano epipolare ( πP)
- piano che passa per i due centri ottici ed il punto P della scena
- linee epipolari coniugate
- sono formate dall'intersezione dei piani immagine (πL, πR) con il piano epipolare (πP)
- epipoli (eL, eR)
- immagine in una telecamera della proiezione del centro ottico dell'altra
- punti corrispondenti all'intersezione della retta che unisce i centri ottici (OL, OR), con i piani immagine
- proprietà degli epipoli
- con l'eccezione dell'epipolo, solo una linea epipolare passa attraverso ogni punto dell'immagine
- tutte le linee epipolari di una telecamera passano attraverso il suo epipolo
- vincolo epipolare
- punti corrispondenti stanno necessariamente su linee epipolari coniugate
- punti dell'immagine (pL,
pR)
- proiezione del punto P nei rispettivi piani immagine
- punti corrispondenti all'intersezione delle rette che uniscono i centri ottici con il punto P ed i rispettivi piani immagine
- matrice E (essenziale)
- introdotta da Longuet-Higgins ('81)
- stabilisce una relazione tra il vincolo epipolare ed i parametri intrinseci del sistema stereo
- contiene informazioni sui soli parametri estrinseci
- ha rango 2 (E=RS, S ha rango 2, R ha rango 3)
- i suoi valori singolari non nulli sono uguali
- pRT E pL
= 0
- pL = fL PL / ZL
- pR = fR PR / ZR
- retta (proiettiva) sul piano πR
- uR = E pL
- fa il mapping dei punti immagine sulle rette epipolari dell'altra immagine
- matrice F (fondamentale)
- la corrispondenza tra punti e linee epipolari può essere ricavata anche senza informazioni a priori sul sistema stereo
- contiene informazioni sia sui parametri estrinseci che sugli intrinseci
- ha rango 2 (TL e TR hanno rango pieno ed E ha rango 2)
- se riesco a stimare F dal matching di molti punti immagine corrispondenti posso ricavare la geometria epipolare senza informazioni a priori
- pRimT F
pLim = 0
- MLint, MRint = matrici dei parametri intrinseci delle telecamere
- pL = MLint pLim
- pR = MRint pRim
- proprietà
- entrambi le matrici E ed F consentono la ricostruzione completa della geometria epipolare
- F = MR-TEML-1
- Stima di E ed F
- il metodo più noto è l'algoritmo ad 8 punti
- N punti corrispondenti, N equazioni lineari omogenee da: pRimT F pLim = 0
- se N è uguale a 8 ed i punti non formano una configurazione degenere (i.e. danno origine a equazioni non indipendenti), la soluzione è quella non triviale del sistema
- se N>8 si risolve con SVD
- rischio di instabilità numerica
- un trucco può consistere nel normalizzare le coordinate dei punti corrispondenti per avere gli elementi della matrice da diagonalizzare comparabili
- il metodo più noto è l'algoritmo ad 8 punti
- calcolo degli epipoli
- F eLim = 0
- (pRimT F eLim = 0 per tutti i punti immagine pRim)
- l'epipolo è l'autovettore di F con autovalore nullo (che esite perchè F ha rango 2)
- gli epipoli si possono ricavare anche in altri modi
- gli epipoli si possono stimare senza conoscere i parametri intrinseci
- F eLim = 0
- note
- dalla corrispondenza di 8 più punti si possono sempre ricavare la matrice fondamentale e gli epipoli
- non si può risalire in generale ai parametri intrinseci ed estrinseci
- non sempre è facile trovare corrispondenze
- se avessi telecamere con gli assi paralleli e l'asse x in comune, la corrispondenza sarebbe sempre solo da cercare in orizzontale
- esistono metodi alternativi per il calcolo degli epipoli non basati sulla matrice fondamentale che richiedono al peggio almeno 6 punti di corrispondenza
- rettificazione
- procedura per la trasformazione dei piani immagine in modo che coppie di linee epipolari coniugate siano parallele e perpendicolari all'asse y
- in questo modo la ricerca delle corrispondenze è un problema 1D
sull'asse x
- gli epipoli stanno all'infinito sull'asse x, in coordinate omogenee (1,0,0) (-1,0,0)
- la coppia di immagini rettificate equivale ad immagini ottenute da camere con asse ruotato attorno al centro ottico per essere collineari
- problema: dati i parametri estrinseci R, T trovare due trasformazioni RL, RR per i piani immagine che rendano parallele e orizzontali le rette epipolari
- supposizioni
- entrambi le telecamere hanno la stessa focale f
- il centro di coordinate delle immagini corrisponde con l'origine
- coordinate immagini = coordinate pixel
- passi
- ruotare la camera sinistra per portare l'epipolo all'infinito
- applicare la stessa rotazione alla destra per riportare alla geometria precedente
- ruotare la camera destra di R per renderla parallela alla sinistra
- aggiustare i fattori di scala nei riferimenti
- algoritmo
- costruisci RL
- per i punti del piano immagine sinistro le nuove coordinate sono (x',y',z')=RLPL
- ripetere per la destra con RR=RRL
- nota
- la trasformazione diretta mi crea valori non interi per x'
- se voglio la griglia di pixel, devo fare la trasformazione inversa
- ricostruzione
- ricostruzioni in base alle conoscenze
- parametri intrinseci ed estrinseci
- ricostruzione completa (coordinate assolute)
- parametri intrinseci
- ricostruzione a meno di un fattore di scala
- nessuna informazione
- ricostruzione a meno di una trasformazione proiettiva dell'ambiente
- parametri intrinseci ed estrinseci
- stima di P (triangolazione) - caso semplice
- se conosciamo tutti i parametri intrinseci ed estrinseci, per calcolare la posizione del punto P della scena basta intersecare le rette che passano per OL pL e OR pR
- nella realtà esiste un errore che impedisce alle rette di incontrarsi esattamente
- stimo P come il punto medio della distanza minima delle due
rette l e r diretto come w:
- l = apL
- r = T + bRTpR
- w = pL x RTpR
- P = (<a>pL + T +
<b>RTpR) / 2
- (si ricavano le stime di a e b)
- stima a meno di un fattore di scala
- conosciamo solo i parametri intrinseci delle telecamere
- algoritmo (Conoscendo E e T)
- 1. costruisci w, e calcola R
- 2. ricava ZL e ZR per ciascun punto
- 3. se i segni di ZL e ZR dei punti
- a) entrambi negativi per qualche punto, cambia il segno di T e torna a punto 2
- b) differenti per qualche punto, cambia il segno degli elementi di E e torna al punto 1
- c) entrambi positivi, termina
- ZL = fL [(fRR1 - xRR3)T T] / [(fRR1 - xRR3)T pL]
- ZR = -fR [(fLR1 - xLR3)T T] / [(fLR1 - xLR3)T pR]
- uncalibrated stereo
- se non si conoscono né i parametri intrinseci né gli estrinseci, si può ricavare la struttura a meno di una trasformazione proiettiva del mondo
- ricostruzioni in base alle conoscenze
- stereo matching
- trovare pixel corrispondenti (in linee epipolari coniugate)
- non tutti i punti hanno corrispondenza
- intorno ad alcuni pixel l'informazione è scarsa
- vari algoritmi proposti, possibilità di test quantitativi con misure geometriche reali note (ground-truth data)
- posso lavorare su tutti i pixel o sulle features
- matching di tutti i pixel
- ipotesi a priori
- costanza del livello di grigio (colore)
- continuità in un intorno del punto (cerco corrispondenze tra finestre centrate sul punto)
- ricerca discreta
- considero il pattern di livelli in una finestra W di dimensioni (2N+1)x(2N+1) e in una uguale traslata lungo la scanline (o più in generale spostando in entrambe le direzioni)
- scelgo come disparità nel punto il valore che minimizza una distanza o massimizza la correlazione
- vantaggi
- ricavo una mappa densa di disparità quindi di profondità
- non ho bisogno di precedenti elaborazioni complesse
- svantaggi
- l'informazione locale è spesso insufficiente o ambigua (tessitura)
- le ipotesi di continuità e costanza grigio non sono sempre verificate
- SSD (Sum of Squared Differences)
- mindxdySSD(i,j) = mindxdy
Σk=-N,NΣl=-N,N {IL(i+k,j+l) -
IR(i+dx+k,j+dy+l)}2
- -R < dx < R ; -R < dy < R
- mindxdySSD(i,j) = mindxdy
Σk=-N,NΣl=-N,N {IL(i+k,j+l) -
IR(i+dx+k,j+dy+l)}2
- misura di differenza più semplice e computazionalmente efficiente
- ipotesi a priori
- SAD (Sum of Absolute Differences)
- mindxdySSD(i,j) = mindxdy Σk=-N,NΣl=-N,N |IL(i+k,j+l) - IR(i+dx+k,j+dy+l)|
- per velocizzare i calcoli, posso salvare una look up table con i valori di (I1-I2)2 per ogni possibile coppia di valori di grigio (se 8 bit: 256x256)
- CC (Cross Correlation)
- faccio prodotto pixel a pixel delle dei pixel delle due finestre
- problema: il valore dipende fortemente dal livello di grigio: livelli alti danno correlazioni alte; soluzione: sottrarre media e/o normalizzare
- ZCC (Zero mean Cross Correlation)
- può essere utilizzata e dare risultati accurati
- è complessa, lo zero mean impedisce di utilizzare tabelle di look-up
- NCC (Normalized Cross Correlation)
- ZSSD (Zero mean Sum of Squared Differences)
- lo zero mean impedisce di utilizzare tabelle di look-up
- LSSD (Locally scaled Sum of Squared Differences)
- problemi
- tessitura
- cosa faccio dove non c'è? nulla: è il problema maggiore.
- occlusioni
- che succede nei punti dove non c'è reale corrispondenza?
- simmetria
- cosa succede se inverto IL e IR? corrispondenza non simmetrica!
- effetti prospettici
- come potrei eliminare l'errore che introducono?
- approssimazione al pixel
- come potrei andare sotto la risoluzione del pixel?
- tessitura
- note
- per limitare dx e dy posso usare il vincolo epipolare oppure se ho usato la rettificazione posso cercare solo lungo x
- alcune misure possono ridurre l'effetto di discontinuità negli
algoritmi di corrispondenza
- es. misure non parametriche: cercano di catturare la struttura invece che le variazioni di grigio
- la dimensione delle finestre è critica:
- troppo piccole: poca informazione
- troppo grandi: effetti prospettici e discontinuità rilevanti
- questi algoritmi vanno bene anche per calcolare il moto tra due immagini di una sequenza
- matching di features
- possiamo sfruttare l'estrazione di punti/regioni salienti (features).
- troviamo la corrispondenza e la utilizziamo localmente per ricavare la posizione dell'oggetto corrispondente
- occorre scegliere le features (edge, corners, linee) decidere dove cercarle e come compararle
- per la ricerca si introducono dei vincoli (vincoli geometrici (constraint epipolare), unicità del match, continuità)
- esempio: edges (catene)
- posso considerare l'output dell'algoritmo di Canny
- misuro:
- lunghezza l
- orientazione o
- punto centrale, x,y
- valori di contrasto medio c
- problemi: immagini con grosse variazioni e tessitura rilevante creano molte features, spesso simili; rumore
- algoritmo
- estraggo le features, e i descrittori visti sopra
- misuro la distanza di ciascuna feature a sinistra con quelle dell'immagine destra nello spazio di ricerca
- salvo la corrispondenza e la relativa disparità
- ricostruzione del moto da sequenze di immagini
- relazione moto/stereo
- anche nel moto si ha la corrispondenza di punti in immagini diverse
- immagini prese in due istanti successivi sono equivalenti ad una coppia stereo
- per definire il moto occorrono molte immagini
- a differenza dello stereo, nel moto le "disparità" sono molto piccole
- per la ricostruzione non possiamo sempre assumere come rigida la trasformazione della scena tra le immagini
- ricostruzione del moto
- è uno dei problemi fondamentali della computer vision (CV)
- 2 sottoproblemi non del tutto indipendenti:
- ricostruzione "visual motion" o "flusso ottico" (basso livello)
- interpretazione: ricostruzione moto e struttura 3D (alto livello)
- forte analogia biologica: elaborazione parallela, area (VT, M5) che elabora il moto a basso livello prima della ricostruzione
- problemi
- come tutti i problemi della CV, si tratta di un problema
tipicamente mal posto: informazione insufficiente per la soluzione
esatta senza ipotesi aggiuntive:
- quantizzazione spaziotemporale
- estrapolazione di informazione 3D da dati 2D (ambiguità)
- necessità di ipotesi a priori per l'interpretazione
- spesso funzionano, come per la visione umana
- talvolta falliscono
- ambiguità prospettiche
- fattori di scala: anche se f è nota, se V doppia e d doppia, la proiezione è uguale (analogia con stereo)
- problemi di campionamento temporale
- se la frequenza di campionamento è troppo bassa rispetto al movimento che si vuole osservare, si possono trarre conclusioni sbagliate
- anche il sistema visivo umano fallisce in certe circostanze (es: ruote delle auto che sembrano cambiare senzo di rotazione quando superano una certa velocità)
- come tutti i problemi della CV, si tratta di un problema
tipicamente mal posto: informazione insufficiente per la soluzione
esatta senza ipotesi aggiuntive:
- analisi moto
- approccio storico Computer Vision: estrarre stima locale della proiezione del moto (flusso ottico) e poi procedere ad interpretazione di struttura e/o moto 3D
- ha senso estrarre informazione motoria indipendentemente dall'interpretazione
- anche i sistemi biologici utilizzano utilmente l'informazione
visuale sul moto nel piano immagine senza informazioni a priori
- prova sperimentale: nel moto di pattern "random dot" "vediamo" il moto anche senza altre informazioni, ciò mostra che "riconosciamo" il moto (e la forma in moto) solo dall'analisi temporale
- utilità di informazioni parziali
- anche applicazioni pratiche possono utilizzare semplici stime motorie senza "ricostruire" o "riconoscere" oggetti
- esempio: stima del tempo di collisione (time to impact, time to
collision)
- consideriamo una versione planare del modello di telecamera pinhole ed una barra verticale perpendicolare agli assi ottici che si muove verso la telecamera con velocità costante
- L = lunghezza della barra verticale
- V = velocità della barra
- f = lunghezza focale della telecamera
- l'origine del sistema di riferimento della scena coincide con l'origine del sistema di riferimento del piano immagine
- D(0) = D0 : posizione della barra al tempo t=0
- D = D0 + Vt : posizione della barra al tempo t > 0
- l(t) = f L/D : misura apparente della barra sul piano immagine al tempo t
- l'(t) = dl(t)/dt = -f (L/D2) (dD/dt) = f (LV/D2) : derivata di l(t)
- τ = l(t)/l'(t) = D/V : tempo di collisione
- sequenze di immagini digitali
- successione E(x,y,tk) di immagini o frames (i.e.
matrici 2D di valori di grigio o componenti cromatiche) acquisite a
istanti discreti tk=t0+kDt
- campionamento spaziale e temporale (conseguente perdita di informazione alle alte frequenze)
- variazioni temporali dovute a variazioni di illuminazione o moto
- aliasing se moto rilevante e/o frame rate basso
- successione E(x,y,tk) di immagini o frames (i.e.
matrici 2D di valori di grigio o componenti cromatiche) acquisite a
istanti discreti tk=t0+kDt
- problemi pratici in machine vision
- rilevamento (detection) del cambiamento
- stima di visual motion (campo del "flusso ottico") sul piano immagine / calcolo della corrispondenza dei punti tra frames
- ricostruzione del moto e struttura in 3D dalla corrispondenza di features o mappe di flusso ottico
- segmentazione del moto
- tracking di features oggetti o strutture
- applicazione delle soluzioni
- sorveglianza
- robotica
- guida assistita di autoveicoli
- elaborazioni mediche
- compressione video
- approccio
- ricavare da elaborazioni locali dell'immagine stime di variazione o della proiezione del moto sul piano immagine (flusso ottico)
- ricostruzione successiva di moto 3D o struttura 3D o semplicemente di parametri utili (es. tempo di collisione)
- rilevamento (detection) del cambiamento
- scopo: segmentare regioni dell'immagine dove "qualcosa cambia" nel corso della sequenza temporale (non serve calcolare il moto)
- metodo: Soglia su differenza E(t) - E(t+1)
- possiamo mediare nello spazio e nel tempo per ridurre errore
- problema: dipende fortemente dal gradiente dell'immagine (tessitura)
- motion measure (misura del moto)
- pesa il modulo del gradiente
- serve ad ovviare alle differenze di tessitura
- M = (|ET| ||∇E||) / (c + Σ||∇E||2)
- costanza della luminosità (brigthness constancy, costanza dei
livelli di grigio)
- ipotesi che in genere si fa per la stima del moto
- un punto proietta sul piano immagine sempre la stessa luminosità
- la derivata temporale del livello è nulla
- dE(x,y,t)/dt = 0
- ExVx + EyVy + Et = 0
- equazione di costanza della luminosità (image brightness
constant equation)
- Et = -v · grad(E)
- (∇E)Tv + Et = 0
- il pedice t denota derivate parziali rispetto al tempo
- note
- la differenza temporale (derivata stimata con differenza finita) nel punto è una stima della componente del moto proiettato dal punto nella direzione del gradiente moltiplicata per la norma del gradiente (aliasing permettendo...)
- da un singolo pixel possiamo stimare solo una componente del moto proiettato
- per stimare la "proiezione" del moto dei punti sul piano immagine devo estrapolare informazione dai punti circostanti
- geometria della proiezione del moto 3D
- scopo: legare le stime del moto sul piano immagine a moto e struttura in 3D
- il vettore velocità V 3D di un punto P(X,Y,Z) proiettiato sul piano immagine è il vettore velocità v del punto p(x,y,f)
- campo di moto (motion field)
- è il campo di vettori 2D delle velocità dei punti dell'immagine indotto dal movimento relativo tra la telecamera e la scena osservata
- può essere pensato come la proiezione dei campi di velocità 3D della scena sul piano immagine
- flusso ottico (optical flow)
- moto apparente dei punti dell'immagine
- stima del campo di moto a partire dai valori di grigio della sequenza di immagini
- si basa sull'equazione di costanza della luminosità dE/dt = 0
- problema dell'apertura
- la componente di velocità perpendicolare al gradiente dell'immagine non è vincolata (determinata) dall'equazione di costanza della luminosità
- vn = - Et / ||∇E|| = (∇E · v) / ||∇E||
- dobbiamo guardare in un intorno e in quell'intorno il gradiente deve variare
- l'angolo permette di eliminare l'ambiguità
- ipotesi di continuità
- se suppongo che la velocità sia continua, posso vincolare il problema utilizzando più punti in un intorno di x per la stima di v in x
- più grande è l'intorno più si spera di trovare dei punti che risolvano il problema dell'apertura (variazioni nella direzione del gradiente)
- rischio: si perdano altre ipotesi (reale continuità del moto, ad esempio)
- ipotesi (classiche) necessarie/utili alla stima
- superfici lambertiane E = ρs cos(α)
- illuminazione costante nel tempo
- tessitura rilevante almeno in qualche punto nell'intorno
- deboli effetti prospettici nella regione di stima
- moto rigido tra la scena e la telecamera
- nessuna discontinuità nel moto
- assenza di aliasing temporale: il frame rate di acquisizione è critico
- esempi negativi in cui falliscono le ipotesi classiche
- sfera che ruota sul proprio asse sotto un'illuminazione
costante
- il flusso ottico è nullo malgrado il campo di moto non lo sia
- sfera fissa illuminata da una sorgente luninosa in movimento
- il campo di moto è nullo ma il flusso ottico non lo è per via del cambiamento delle ombre
- sfera che ruota sul proprio asse sotto un'illuminazione
costante
- metodi di stima
- differenziale
- si può scrivere la equazione di costanza della luminosità per ogni pixel
- manca un constraint: continuità locale
- Lucas-Kanade (1981): v costante in un intorno (finestra NxN), soluzione ai minimi quadrati
- Horn e Shunck (1981): Funzionale con termine di smoothness da minimizzare iterativamente
- Uras et al (1987): constraint aggiuntivo da derivate seconde
- problemi
- derivazione numerica, aliasing, dimensione intorno, effetti prospettici, discontinuità
- inutile la stima ove mancano informazioni: si usa scartare i valori con misure di confidenza
- correlazione
- (es. Anandan) Come per stereo, si confrontano mediante una misura di distanza (es. SSD) delle finestre quadrate W spostate di differenti quantità tra un'immagine e la successiva; la minore distanza corrisponde al valore cercato
- filtri spaziotemporali
- (Fleet, Jepson) Filtraggi nello spazio 3D, praticamente simili a correlazione su supporto maggiore
- algoritmo di Flusso Costante (Lucas Kanade, L-K)
- è Il più semplice ed efficace (se modificato o corretto opportunamente in caso di problemi)
- v costante in una finestra W di dimensioni NxN (i.e. 7x7)
- dalla equazione di costanza della luminosità, abbiamo il
sistema di NxN eq.:
- (∇E(pi,t))T v +
Et(pi,t) = 0
- pi in W
- (∇E(pi,t))T v +
Et(pi,t) = 0
- problema ai minimi quadrati: minimizzare
- F[v] = Σi [(∇E(x,y,t))T v + Et(x,y,t)]2
- soluzione
- sistema: ATAv = ATbT
- A = [∇E(p1), ∇E(p2), ..., ∇E(pNxN)]T
- b = (Et(p1), Et(p2), ..., Et(pNxN))
- soluzione: v = (ATA)-1ATb
- varianti
- pesi ai punti: F[v] = Σi M2(x,y) [(∇E(x,y,t))Tv + Et(x,y,t)]2
- soluzione minimi quadrati pesati: v = (ATM2A)-1ATM2b
- fallisce se (ATA) è nulla o singolare (mancanza di tessitura o
problema dell'apertura, cioè il gradiente ha sempre la stessa
direzione), in quest'ultimo caso solo la componente normale al
gradiente è determinata
- si possono scartare le stime inaffidabili (flusso non denso)
- finestre ampie migliorano il condizionamento del sistema
- se v non è costante è possibile stimare dai residui la presenza di discontinuità e filtrare
- si possono scartare le stime inaffidabili (flusso non denso)
- note
- ATA è la stessa matrice utilizzata per la corner
detection
- ATA = {[ΣwEx2, ΣwExEy] , [ΣwExEy , ΣwEy2]}
- il fatto che il gradiente sia rilevante in due direzioni perpendicolari "risolve" il problema dell'apertura e consente la stima
- 1 autovalore nullo = gradiente unidirezionale, il problema dell'apertura resta
- 2 autovalori nulli = assenza di tessitura
- ATA è la stessa matrice utilizzata per la corner
detection
- problema della discontinuità
- supponiamo di usare il metodo Lucas-Kanade su finestra dimensioni W
- all'interno della finestra W si proiettano due oggetti con moto diverso
- l'algoritmo dà un risultato sbagliato
- posso dare una stima di quanto è buono il fit mediante una
misura di confidenza
- es. residuo R=F[v]
- questa stima si può utilizzare per un filtraggio non lineare
- esempio Bartolini et al.(1993):
- si calcola il flusso in 9 finestre contenenti il punto in questione e si prende come stima corretta quella che ha minor valore del residuo
- dal residuo faccio la stima di "edges" del moto
- esempio Bartolini et al.(1993):
- problema dell'aliasing
- le alte frequenze spaziali causano errore (sottostima), specialmente per le derivate temporali calcolate per differenze finite o maschere a 5 punti
- se il moto è maggiore del pixel/frame, l'errore è grande
- dovrebbe essere fmax < 1/2 Δx ; fmax < 1/2 v Δt
- possibili strategie:
- filtraggio
- multirisoluzione
- uso di tecniche di correlazione o miste
- algoritmo L-K Multiscale
- decomporre le immagini in piramide Gaussiana (filtering+subsampling) E0(x0,y0),E1,E2...
- calcolare il flusso al livello più coarse V0 alla LK con le derivate E0xE0yE0t
- usare l'approssimazione intera V0 al livello
immediatamente più fine per calcolare le derivate temporali
"shiftate" (warped) al flusso successivo
- E1t(x1 ,t) = (E(x+V0x(x1),y1 + V0y (x1),t+1) -E1t(x1-
- V0x(x1),y1-V0y(x1),t-1))/2
- usare queste derivate (e le normali derivate spaziali calcolate a quel livello) per calcolare il flusso LK al livello 1
- proseguire per tutti i livelli
- interpretazione
- al primo livello il moto è dell'ordine del pixel, quindi calcolabile con le derivate
- ai livelli successivi calcolo la differenza tra il moto e la parte intera del moto stimato al livello precedente, anche qui dell'ordine del pixel di questa scala
- efficienza temporale di L-K
- forte correlazione tra le equazioni ricavate da pixel vicini della finestra: molta ridondanza nel sistema
- sottocampionare non introduce errore apprezzabile e può ridurre la complessità di un fattore 8 senza problemi
- multirisoluzione anch'essa efficace per ridurre i calcoli
- se si usano filtri tipo multi-finestra, si possono ottimizzare per evitare operazioni ridondanti
- Horn and Schunck
- si minimizza un funzionale di errore su tutta la regione D
- soluzione iterativa scrivendo le equazioni di Gauss-Seidel
- ipotesi
- brightness constancy
- velocità circa uguali in intorni
- vantaggi
- incorpora informazione globale
- usa solo derivate prime
- svantaggi
- iterativo
- pessimo per discontinuità
- correlazione
- si massimizza una funzione di correlazione o si minimizza una differenza tra una finestra centrata in p(x,y) nell'imagine E(t) e finestre identiche spostate di quantità (dx,dy) variabili tra -D,-D e D,D nell'immagine successiva
- esempio
- Min SSD: Sw(E(x+i,y+j,t)-E(x+i+dx,y+j+dy,t))
- differenze con stereo
- spazio di ricerca in genere ridotto
- nessun vincolo (epipolare)
- note
- la complessità computazionale si può ridurre con sottocampionamento finestre
- meno problemi di aliasing (anche se presenti)
- si usa quindi per movimenti rilevanti, tracking, ecc
- necessità di finestre piuttosto ampie
- spostamenti interi
- è possibile l'uso della multirisoluzione e del sottocampionamento per risurrei lunghi tempi di calcolo dovuti alle ampie finestre
- metodi per correzione non intera
- fare media pesata dei diversi spostamenti con le più basse SSD
- usare la tecnica del warping e correggere calcolando un termine differenziale
- correlazione e feature matching
- la correlazione viene spesso utilizzata in "inseguitori" di features
- mi interessa valutare lo spostamento di uno o più punti caratteristici in varie immagini e non una mappa densa di vettori
- i punti caratteristici possono essere tutti quelli in cui la stima del moto ha senso
- Fleet and Jepson
- esistono altre famiglie di algoritmi per la stima del moto, in genere computazionalmente più pesanti e poco usati
- la "famiglia" di algoritmi più importante è basata sull'uso di
filtri spaziotemporali
- si calcola la risposta in frequenza nel volume x,y,t
- si "campiona" quello spazio mediante filtri (Gabor) specifici
- in pratica l'energia dovrebbe essere concentrata su un piano la cui normale è legata al valore del moto
- test sugli algoritmi
- si utilizzano immagini sintetiche o "calibrate" di cui si conosce il valore esatto della proiezione del moto reale
- immagini sintetiche
- molto usata Yosemite: spostamenti ampi, discontinuità e cambio luminosità globale
- sequenze reali calibrate nei lavori di Otte, Nagel
- misure di affidabilità
- differenza quadratica media
- distanza angolare di Barron
- differenziale
- dal flusso ottico all'informazione 3D
- ipotesi aggiuntive
- moti rigidi
- uso di algoritmi tipo stereo (Structure from motion)
- conoscenze a priori sulla superficie in moto (es. piana o localmente approssimabile con un piano)
- ipotesi aggiuntive
- campo di moto 2D
- proiezione delle velocità 3D sul piano immagine: V = -T-ωXP
- data f la distanza focale: v = f (ZV-VzP )/Z2
- già mal posto V da v, ma noi non abbiamo neppure v, abbiamo solo E(x,y,t)
- due differenti problemi: stimare v e stimare P e/o V da v
- stima di v da E(x,y,t) o meglio "moto visuale" dei pixel del piano immagine: flusso ottico
- proiezione prospettica del moto
- vx = ((Tzx-Txf)/Z) - ωyf + ωzy + ((ωxxy)/f) - ((ωyx2)/f)
- vy = ((Tzy-Tyf)/Z) - ωxf + ωzx + ((ωyxy)/f) - ((ωxy2)/f)
- è possibile separare la parte traslazionale da quella rotazionale
- traslazione pura (ω=0, caso particolare)
- v = f(ZV - VzP)/Z2
- vx = (Tzx - Txf)/Z = (x - x0) Tz/Z
- vy = (Tzy - Tyf)/Z = (y - y0) Tz/Z
- p0 = (fTx/Tz, fTy/Tz) = [x0, y0]T
- il campo di moto di una traslazione pura è radiale (fuoco di
espansione)
- p0
- fuoco di espansione (focus of expansion)
- è il punto di fuga della direzione di traslazione (vanishing point)
- è l'epipolo istantaneo tra coppie di immagini consecutive
- per piccoli spostamenti p0 si può calcolare senza conoscere a priori i parametri intrinseci
- p0 ≠ punto singolare (solo se pura traslazione)
- la lunghezza dei vettori è inversamente proporzionale a Z, se Tz non è nullo, la lunghezza è inversamente proporzionale alla distanza p-p0
- p0
- punti singolari
- le proprietà dei punti singolari (v=0) del campo di moto possono dare informazioni qualitative sul moto stesso (i.e. fuoco espansione -> traslazione pura; centro rotazione, ...)
- la teoria dei sistemi dinamici garantisce la stabilità strutturale delle informazioni qualitative
- campo di moto di un piano
- supponiamo piano definito da n
- P*n = d
- n = vettore unitario perpendicolare al piano π
- d = distanza tra π e l'origine (il centro ottico)
- sostituendo nell'equazione della proiezione, ottengo formule
quadratiche in x,y,(f)
- vx = (a1x2+a2xy+a3fx+a4fy+a5f2)/fd
- vy =
(a1xy+a2y2+a6fx+a7fy+a8f2)/fd
- a1 = -dωy+Tznx
- a2 = -dωx+Tzny
- a3 = Tznz-Txnx
- a4 = dωz+Txny
- a5 = -dωy+Txnz
- a6 = Tznz-Tyny
- a2 = dωx+Tynz
- il campo di moto di una superficie in movimento ad ogni istante t è un polinomio quadratico nelle coordinate (x,y,f) dei punti dell'immagine
- supponendo di conoscere v in molti punti, posso scrivere il solito sistema sovradeterminato e ricavare gli ai e poi i parametri
- ambiguità
- tranne il caso in cui n e T sono paralleli, lo stesso campo di moto può essere riprodotto da due piani differenti con velocità diverse (stessi coefficienti ai)
- d'=d ; n'=T/|T| ; T'=|T|n ; ω' = ω + n x T d
- applicazione
- se conosco la localizzazione di un piano nella scena e se conosco i parametri intrinseci della telecamera, posso ricavare i parametri del moto
- la strada vista da una telecamera su un veicolo è
approssimativamente un piano
- conosco approssimativamente l'altezza e la direzione
- il modello di moto si dice navigazione passiva
- in generale
- se ho una superficie liscia, localmente potrebbe essere approssimabile con un piano
- se ho abbastanza informazione in un intorno, posso supporre localmente valida l'approssimazione polinomiale del campo e cercare di risalire all'orientazione
- shape/structure from motion
- la stima del moto di punti selezionati o di un campo di moto
denso può essere utile per:
- data la geometria della superficie e ipotesi (es. rigidità), ricavarne il moto in 3D
- date ipotesi di rigidità, ricavarne moto e struttura 3D
- la stima del moto di punti selezionati o di un campo di moto
denso può essere utile per:
- metodi di ricostruzione
- discreto
- da corrispondenza N punti in 2 immagini (analogo stereo)
- corrispondenza 8 punti - calcolo matrice essenziale, cioè t.c. pTEp'=0 ⇒ stima forma a meno di un fattore di scala
- posso risolvere l'ambiguità di scala solo se conosco a priori il moto (i.e. muovo io la telecamera) e cerco di ricostruire la superficie
- da corrispondenza N punti in 2 immagini (analogo stereo)
- differenziale
- da flusso ottico
- in genere poco precisi a causa dei valori molto bassi degli spostamenti
- si può migliorare la stima integrando nel tempo
- vari metodi proposti in letteratura
- da flusso ottico
- discreto
- metodo di fattorizzazione
- esempio di ricostruzione da inseguimento punti dovuto a Tomasi e Kanade
- si assume:
- modello ortografico
- n punti (xij, yij), inseguiti in N immagini N≥3 ; 1≤i≤N ; 1≤j≤n
- si calcola il moto della telecamera tra un frame e il successivo (rispetto a scena rigida)
- si ricavano la matrice di rotazione e la componente di traslazione perpendicolare all'asse ottico
- generalizzabile al caso proietivo
- ricostruzione da flusso denso
- un metodo proposto si basa sulla stima della direzione di traslazione sulla base della parallasse del moto
- successivamente si calcola la componente rotazionale sulla base di calcoli sulla geometria proiettiva
- risultati meno precisi che nel metodo di fattorizzazione
- necessità di grande accuratezza nella calibrazione
- tracking (feature tracking)
- mediante una stima di moto, posso per uno o più oggetti stimare la posizione (e/o il moto derivante) di un punto su immagini successive
- la stima avrà un certo errore associato
- è possibile sfruttare la continuità od un modello del movimento e l'errore di misura per ottenere un risultato ottimale nella localizzazione del (degli) oggetti?
- ad ogni istante t discreto il mio stimatore di posizione
fornirà un valore più o meno affidabile della posizione
- es: calcolo corrispondenza mediante minima SSD: se il valore assoluto della SSD è basso la stima è affidabile, altrimenti lo è meno
- per eliminare errore posso sfruttare la "continuità": fare una previsione sulla posizione successiva in base alle stime precedenti e mediarla con la misura
- data association: se inseguo più oggetti simili, come faccio ad assicurarmi di non scambiarli? E se c'è un occlusione?
- Kalman filter
- è il filtro "ottimo"
- la tecnica utilizzata tipicamente in computer vision è basata su metodi statistici di teoria della stima
- l'ipotesi è di avere un modello di evoluzione del fenomeno (nel nostro caso la posizione del punto o feature nell'immagine), con associato errore e la serie di misure con associato errore
- metodo
- si definisce un vettore di stato
- lo si stima sulla base di una misura
- si predice il nuovo valore del vettore all'istante successivo
- si corregge la stima in base alla nuova misura
- ipotesi
- sistema lineare
- i parametri del sistema sono funzioni lineari dei parametri ad istanti precedenti
- le misure sono funzioni lineari dei parametri
- rumore
- bianco: non correlato temporalmente
- gaussiano
- parametri del sistema
- v costante
- pi = (x y vx vy)i
- modello di evoluzione (dt=1)
- pi = pi-1 + vi-1 + ξi-1
- vi = vi-1 + ηi-1
- modello di misura
- mi = H pi+ ri
- matrice di covarianza dello stato pi
- P=E((p-E(p)) (p-E(p)T)
- l'algoritmo di matching fornisce l'"osservazione" dello stato mi
- l'osservazione è rumorosa, si associa Pi non nulla
- modello del rumore
- si assumono errori gaussiani qi, ri , con associate matrici di covarianza Q, R
- system noise
- pi = A pi-1+ qi ⇒ Q = E(qiqiT)
- measurement noise
- mi = H pi + ri ⇒ R = E(ririT)
- predizione
- pi' = A pi-1
- correzione
- <pi> = pi' + K(mi -
Hpi')
- K = Kalman gain matrix (soluzione)
- K = P'HT(HP'HT+R)-1
- Pi' = APi-1'AT + Q
- minimizza l'errore atteso
- e = p - <p>
- P = E(eeT)
- limiti
- system noise << measurement noise ⇒ <pi>= pi'
- system noise >> measurement noise ⇒ <pi>= H-1mi
- K = Kalman gain matrix (soluzione)
- <pi> = pi' + K(mi -
Hpi')
- algoritmo
- date le misure ad ogni istante, calcolo iterativamente:
- Pk' = Ak-1Pk-1 Ak-1T + Qk-1
- Kk = Pk' HkT (HkPk'HkT+Rk)-1
- <p>k = Ak-1<p>k-1 + Kk(mk-HkAk-1<p>k-1)
- Pk = (I-KkHk)Pk'
- Q covarianza system noise
- R covarianza errore misura
- Pk' matrice covarianza dello stato a priori
- Pk matrice di covarianza dello stato a posteriori
- Ak-1<p>k-1 predizione
- mk-HkAk-1<p>k-1 innovazione
- date le misure ad ogni istante, calcolo iterativamente:
- problemi
- in pratica si tratta di fare una media pesata di predizione e misura
- alla fine il punto critico è stimare le matrici dell'errore su stima e misura
- spesso non si hanno i dati per farlo con eccessiva precisione
- l'errore di misura ma soprattutto quello del modello non sono praticamente mai gaussiani
- note
- si parte da una misura
- la matrice di covarianza dello stato viene aggiornata e poi converge
- il problema è inizializzarla: si usa utilizzare valori grandi arbitrari
- la matrice di covarianza della misura è ricavabile dalla precisione dello strumento/algoritmo di misura
- la matrice di covarianza del modello è problematica
- matrice covarianza modello
- per esempio: modello velocità costante
- se conosco la massima accelerazione, posso da essa ricavare la stima dell'errore
- supponiamo 1D, stato [x,v], Δx=a Δt2/2 Δv=aΔt
- se esagero mi affiderò troppo alla misura
- se ho dei valori bassi rispetto all'errore di misura, avrò altri problemi
- in generale gli oggetti possono avere variazioni improvvise, è difficile adattarsi
- per esempio: modello velocità costante
- matrice di covarianza stato
- determina una "regione" attorno alla previsione dello stato che posso utilizzare per restringere la ricerca della feature all'istante successivo
- la sua espressione è:
(p-<p>k)(Pk)-1(p-<p>k)T
< c2
- c è la probabilità che la misura sia nella regione
- si può quindi considerare la predizione p', la covarianza P' e
calcolare i limiti della regione in cui cercare la feature che poi
sono dati gli elementi diagonali della matrice di covarianza dello
stato P' (componenti relative alla posizione del target)
- queste regioni di si chiamano ellissi di incertezza ed evitano di considerare altre features
- data association
- se inseguo più features, posso avere ambiguità
- estraggo più corner o pattern noti ad istanti successivi:
- quali associo a quelli estratti al precedente per aggiornare lo stimatore?
- caso tipico in molte applicazioni: inseguimento persone, veicoli
- soluzioni
- Nearest Neighbor
- si aggiorna il filtro sempre associando a ciascun punto la misura più vicina
- Multi-Hypotesis splitting
- si creano più "path" di tracking e si scartano poi quelli che diventano improbabili secondo una misura data
- Nearest Neighbor
- riconoscimento (recognition, classificazione)
- il riconoscimento di oggetti (model-based object recognition)
si divide in due sottoproblemi
- identificazione (object identification)
- determina la natura dell'oggetto nell'immagine
- identifica quale modello di oggetto nel database (classe, categoria) corrisponde all'oggetto nell'immagine
- devo confrontare l'immagine o features estratte da essa con modelli (geometrici, statistici, training set etichettati, ...)
- localizzazione (object location)
- determina la posizione nella scena 3D dell'oggetto identificato
- identificazione (object identification)
- problemi fondamentali (possibili scenari)
- quali oggetti sono "visti" nell'immagine?
- la regione selezionata dell'immagine corrisponde ad un determinato oggetto?
- quale oggetto tra una serie di possibili modelli corrisponde a una regione selezionata?
- esiste un oggetto di una categoria nota nell'immagine?
- riconoscere in Computer Vision
- associare etichette (categorie) consistenti agli oggetti che corrispondano a raggruppamenti significativi sulla base dell'informazione visiva (pixel o features 2D o 3D estratte con gli algoritmi visti) in maniera sufficientemente robusta rispetto a variazioni di luminosità, posizione, occlusioni, ecc.
- esempi già visti
- Hough transform
- localizzavamo linee
- line/ellipse fitting
- andavamo a cercare ellissi che ben approssimassero le features
- deformable contours
- localizzavamo contorni chiusi
- correlazione
- cercavamo un oggetto dato in suo modello come pattern locale quadrato di livelli di grigio
- Hough transform
- modelli di oggetto
- il tipo di problema affrontato impone scelte differenti per la modellizzazione degli oggetti da riconoscere
- struttura 3D degli oggetti e variazioni ammesse (object posing, deformable surfaces)
- insiemi di invarianti prospettici (es. cross-ratio)
- parti scomposte con caratteristiche note e loro relazioni spaziali (i.e. grafi)
- una regione in uno spazio dei parametri (pattern recognition)
- pattern recognition
- assegnare un oggetto ad una classe (categoria) sulla base di un vettore di features misurabili
- metodo
- si estraggono un insieme di features dall'immagine
- si crea un metodo di clustering delle features in classi corrispondenti agli oggetti riconosciuti
- l'algoritmo di riconoscimento assegna le features incognite a una classe
- pattern
- è un oggetto, processo od evento cui può essere assegnata una categoria (etichetta).
- classe di pattern (categoria)
- è un insieme di pattern che condividono attributi comuni e corrispondono a uno stesso tipo di fenomeni, oggetti, ecc.
- applicazioni in visione
- OCR (Optical Character Recognition)
- feature possibili: misure di forma, topologia, mappa pixel, ecc
- riconoscimento di volti ed impronte digitali
- feature possibili: misure di forma, topologia, mappa pixel, ecc
- sistemi per la diagnosi medica (CAD, computer Aided Diagnosis
da immagini
- feature possibili: misure di tessitura, uscita filtri
- riconoscimento oggetti 3D:
- feature possibili: immagini di oggetto in N viste
- OCR (Optical Character Recognition)
- vettore di features x ∈ ℑ
- sono le osservazioni o misure sull'oggetto da riconoscere
- x è un vettore nello spazio delle fatures ℑ
- classificatore
- è una macchina che svolge la procedura di riconoscimento
- componenti
- sensori ed algoritmi di preprocessing
- algoritmi che ricavano un set di feature significative per le istanze da classificare
- classificatore
- istruttore
- assegna le etichette corrette alle istanze del training set (supervised learning)
- algoritmo di learning
- definisce (con le modalità dipendenti dal metodo implementato) la regola di decisione sulla base del training set
- sensori ed algoritmi di preprocessing
- funzioni di decisione
- un metodo di assegnazione può consistere nell'assegnare a ciascuna classe yi una funzione di decisione fi(x)
- la classe assegnata ad un insieme di features misurate sarà Yi t.c. fi(x) > fj(x) ; ∀j ≠ i
- cerco una "massima somiglianza" o "minima distanza" dalla classe
- partizionerà in genere lo spazio delle feature X in regioni
etichettate tali che:
- X = X1 ∪ X2 ∪ ... ∪ X|Y|
- X1 ∩ X2 ∩ ... ∩ X|Y| = {0}
- le regioni determinano a quale classe corrisponde l'oggetto per il quale si misurano le features x
- decision boundaries: limiti delle regioni
- esempio
- distinguere tra pomodori e zucchine da immagini
- suppongo di aver ricavato le regioni binarie e di misurare rosso/verde nei pixel corrispondenti e l'eccentricità
- gli "stati" possibili sono Y = {P,Z}
- lo spazio delle feature X = ℜ2
- classificatore lineare q(x)
- Z se (wx)+b ≥ 0
- P se (wx)+b < 0
- il riconoscimento di oggetti (model-based object recognition)
si divide in due sottoproblemi
- definizione delle classi
- modello a priori
- learning da esempi (supervised, classificazione supervisionata)
- tipicamente si sfruttano le misure fatte su un campione di pattern di cui si conosce l'etichettatura (training set) per ricavare la regola di classificazione da applicare alle nuove istanze
- clustering (unsupervised learning, classificazione non
supervisionata)
- associazione delle istanze in categorie sulla base di proprietà comuni
- non si conoscono a priori le etichettature e si cerca di ricavarle
- input: training set {x1,...,xl} senza informazioni associate sulla categoria di ciascun esempio
- le procedure che operano il clustering si chiamano algoritmi di unsupervised learning, in genere sono procedure iterative
- scelta delle features
- devono essere efficaci e minimali
- oggetti appartenenti alla stessa classe hanno valori simili delle feature
- oggetti appartenenti a classi differenti hanno valori delle feature diversi
- tipi di vettori (features) di input
- numeri reali (continuo)
- numeri interi (discreto)
- booleani
- etichette, categorie (ordinate, non ordinate)
- un mix di quelli precedenti
- approcci alla classificazione (supervisionata)
- statistici, lineari, non parametrici
- si cerca di sfruttare il modello sottostante le classi di pattern
- adatti per features numeriche
- si analizzano le features in parallelo
- strutturale (o sintattico)
- le classi di pattern sono rappresentate da strutture formali come grammatiche automi, stringhe
- si analizzano le features in serie
- reti neurali
- il classificatore è una rete di celle connesse a strati che prendono a modello i neuroni del cervello
- statistici, lineari, non parametrici
- classificatore minima distanza
- ciascuna classe ha una media associata del vettore delle features mi
- assegno ad un vettore x la classe j tale che Dj= ||x - mj|| sia minimo (distanza euclidea)
- note
- funziona solo se tutte le features sono discriminanti e nello stesso modo
- la distanza euclidea pesa proporzionalmente al valore assoluto dei dati
- dovrei pesare per rendere le grandezze confrontabili
- una possibilità è dividere le distanze di ogni feature per la deviazione standard della stessa nel training set
- la partizione dello spazio dei parametri che rappresenta le classi è un diagramma di Voronoi
- esempio
- riconoscimento cifre
- features = pixel di un immagine
- media = immagine media di una classe, i.e modello ideale di istanza
- misuro la distanza (SSD?) della nuova istanza con lo 0 medio, l'1 medio, ecc...
- ottengo pessimi risultati
- i caratteri sono troppo diversi tra loro: le feature variano molto all'interno della stessa classe
- classificatore bayesiano ottimale
- minimizza il rischio bayesiano, cioè la probabilità di sbagliare categoria
- le probabilità si stimano in genere dal training set (es. con il fitting di una gaussiana o memorizzando l'istogramma)
- dalla formula di Bayes p(Yj|x) = p(x|Yj)P(Yj)/p(x)
- funzione di decisione: Dj(x) = p(x|Yj)P(Yj)
- p(x|Yj) probabilità condizionata delle features data la classe
- P(Yj) probabilità della classe "a priori"
- rischio bayesiano
- anche sapendo l'esatta distribuzione della probabilità, se le probabilità si intersecano, il rischio non è nullo
- il minimo del rischio è detto Bayes risk
- la bontà della classificazione dipende solo dai Decision boundaries, in questo caso il classificatore dà buoni risultati anche se il fit con una gaussiana è cattivo
- alcuni approcci tralasciano il modello statistico per cercare direttamente i decision boundaries (es. Support Vector Machines); in alcuni casi o con alcuni accorgimenti le classi possono essere linearmente separabili, cioè si trova un iperpiano che separa direttamente i punti corrispondenti a due classi distinte
- distanza di Mahalanobis
- (x - mj)TCj-1(x - mj)
- si utilizza nel caso sia nota la densità Gaussiana
- misure in N dimensioni
- nota la covarianza Cj
- note le medie mj della popolazione
- la densità di probabilità è la Gaussiana N-D
- devo trovare j per cui è massimo Dj(x) = p(x|Yj)P(Yj)
- passando al logaritmo: ln Dj(x) = ln P(Yi) - 1/2 ln |Cj| - 1/2 (x - mj)TCj-1(x - mj)
- sostituisce la distanza euclidea
- pesa le componenti del vettore di features secondo la covarianza della popolazione
- vantaggi
- tiene conto delle differenti scale degli assi coordinati
- corregge l'effetto della correlazione tra features
- fornisce decision boundaries di forma diversa
- svantaggi
- occorre conoscere bene la matrice di covarianza
- complessità in memoria crescente e molto alta per molte features
- classificatori basati su istogrammi
- le densità di probabilità condizionate dalla classe, p( x / class y) sono approssimate con l'istogramma dei dati di training
- con un training set sufficiente la stima è buona
- l'istogramma può essere grande se le dimensioni salgono
- l'istogramma mostra la bontà delle features
- esempio
- trovare la pelle umana.
- dove: sui pixel
- features: le tre componenti di colore
- training set: foto varie
- calcolo probabilità: da istogramma
- K-Nearest Neighbor
- metodo non parametrico
- non si calcolano funzioni o parametri (medie, ecc.)
- si conservano in memoria i dati del training set con la loro etichetta
- si calcolano per il vettore x i K dati vj del training set più vicini
- la funzione di decisione sarà data dal numero di vj appartenenti a ciascuna classe Yi
- vantaggi
- non necessita di training
- non si calcolano medie
- svantaggi
- lento e pesante in memoria
- rimanda l'analisi del training set al runtime
- in pratica
- quando facevamo semplice riconoscimento di un modello (es. di carattere) minimizzando la distanza da un solo esempio facevamo 1-NN su un training set minimale (1 elemento per classe)
- per il riconoscimento cifre K-NN è ideale
- infatti se ho un training set rilevante, tutto etichettato, troverò come minimo un modo in cui qualcuno scrive quella cifra
- devo fare molti confronti
- dimensionalità features
- algoritmi pesanti
- devo scegliere il numero minimo di features e il più possibile
significative
- esempi
- il numero di eulero non distingue tra zucchine e pomodori
- la saturazione del colore non discrimina tra zucchine e pomodori
- esempi
- dato un training set, posso "selezionare" le feature discriminanti, oppure "estrarre" feature significative dipendenti da più misure
- estrazione features (combinazioni lineari)
- principal component analysis
- calcolare autovalori ed autovettori della matrice di covarianza delle features
- le direzioni degli autovettori corrispondenti agli autovalori più grandi sono quelle lungo cui i vettori variano maggiormente dunque sono più importanti
- non è detto che le classi siano ben separate lungo tali direzioni
- linear discriminant analysis
- riduce le dimensioni scegliendo le direzioni dello spazio delle features lungo cui le classi sono meglio differenziate
- principal component analysis
- classificatore K-Means
- è di tipo unsupervised learning (clustering)
- stesso metodo usato per trovare le K rette che meglio approssimano un insieme di edge
- lo scopo è minimizzare Σi=1,l ||xi - mq(xi)||2
- algoritmo
- spazio features euclideo
- definisci ed inizializza random K centri dei cluster mk
- 2 passi:
- 1. assegnamento
- riassegna a ciascun cluster gli elementi per cui mk è il più vicino
- 2. refitting
- ricalcola mk come media del nuovo cluster
- 1. assegnamento
- ritorna al passo di assegnazione finchè le classi variano
- convergenza
- quando c'è riassegnamento la somma delle distanze quadratiche dei dati dal centro del cluster si riduce
- dopo il refitting la somma delle distanze quadratiche dei dati dal centro del cluster si riduce
- l'iterazione termina se il passo di assegnamento non cambia i cluster
- problema: convergenza a minimi locali, cruciale inizializzazione
- riconoscimento con invarianti
- caso ad hoc in cui vogliamo risolvere un problema molto particolare
- sfruttiamo le quantità invarianti per la proiezione prospettica
- possiamo misurare sull'immagine quantità (features) dipendenti dall'oggetto che non dipendono da posizione relativa camera-oggetto
- dovremo prima costruire invarianti dalle features dell'immagine
- problema
- estratte delle features da un immagine, definire un vettore di invarianti che dipende da esse e usarli per "identificare" nell'immagine stessa istanze di modelli memorizzati nel sistema
- ipotesi
- lavoriamo in geometria proiettiva, invarianti scalari, funzioni algebriche delle features
- gli oggetti da riconoscere sono planari (ma disposti arbitrariamente in 3D)
- gli invarianti dipendono dall'estrazione di contorni approssimati con segmenti ed archi di coniche
- invarianti proiettivi
- funzione I(cm) tale che I(cm)=I(T(cm)) per ogni trasformazione proiettiva T
- T la trasformazione proiettiva che mappa su p=(x,y,1) del piano immagine i punti P (X,Y,1) di una figura piana nello spazio p=kTP
- cm descrittori di un contorno su un piano "oggetto"
- cross-ratio
- riconoscimento 3D da invarianti
- innanzitutto dobbiamo creare il database dei modelli
- suppongo N oggetti (modelli) Oi
- acquisiamo almeno 2 immagini con diversa vista dei modelli ed estraiamo linee e coniche
- per ciascun oggetto:
- per ognuna delle 2 viste:
- forma tutti i possibili gruppi di features contigue per cui è definito un invariante (es. I1-I4)
- calcola M vettori g1 ... gM dove per ciascun gruppo gk = [I1,I2,I3,I4] contenga il valore degli invarianti (alcuni non definiti)
- salva un modello formato da un'etichetta (nome del modello) e un vettore indice [g1 ... gM] ove gk = [I1k,I2k,I3k,I4k] contenga la media dei valori delle 2 viste se compatibili, o un flag che indichi inaffidabilità se erano differenti
- per ognuna delle 2 viste:
- algoritmo per riconoscere istanze del modello in una immagine
- input: descrittori di linee estratti e il database di modelli [g1 ... gM] con gk = [I1,I2,I3,I4]
- formare tutti gli R possibili gruppi di cinque linee o coniche contigue
- calcola da essi R vettori g1 ... gR di invarianti
- forma la lista di tutti gli oggetti Of indicizzati da almeno uno dei vettori
- se Of è indicizzato da più vettori, chiamo questi gf1 ... gfH
- verifica 1
- togli dalla lista gli Of per cui non esiste un'unica trasformazione proiettiva compatibile con tutte le features gf1 ... gfH
- verifica 2
- togli dalla lista gli Of per cui l'unica trasformazione proiettiva non riproietti all'indietro features simili a quelle estratte nell'immagine
- note
- abbiamo parlato di indicizzazione, ma i valori invarianti sono reali
- devo considerare range accettabili per l'identificazione
- per la verifica 1, considero tutte le linee dei gruppi di invarianti e scrivo la proiezione che lega al modello
- ottengo un sistema sovradeterminato che calcolerebbe la proiezione, se il fit lineare è buono, ok, se no scarto
- per la verifica 2 "vicino" significa entro un margine standard, in genere pochi pixel
- relazione moto/stereo