3.6 Densificazione
3.6.1 CMVS/PMVS
CMVS/PMVS `e una coppia di algoritmi che consentono di aumentare la
for Multi-View Stereo) suddivide le immagini in gruppi (cluster ) gestibili da un algoritmo MVS, dall’altro PMVS (Patch-based Multi-View Stereo) sfrutta i cluster generati da CMVS per costruire un insieme di patch rettangolari densi che ricoprono le superfici visibili nelle immagini di input. Mentre al- tri algoritmi MVS usano tutte le immagini simultaneamente per costruire un modello 3D, rendendo inapplicabile una ricostruzione quando l’insieme
dei dati di input `e molto grande, CMVS/PMVS effettuano una selezione e
clustering delle immagini e ogni gruppo viene gestito in modo indipendente, rendendo questa tecnica da un lato parallelizzabile, dall’altro scalabile verso insiemi massicci di foto.
CMVS
Assumiamo che le immagini di input {Ii} siano state elaborate da un
algoritmo SFM per la generazione di una nuvola sparsa di punti{Pj}, ognu-
no dei quali `e visibile in un insieme di immagini {Vj}. L’algoritmo CMVS
individua un certo numero di cluster {Ck} di immagini con sovrapposizione
parziale tali che valgono le seguenti tre propriet`a [16]:
• compattezza: le immagini ridondanti devono essere escluse dalla com-
putazione. Formalmente, si vuole minimizzare P
k|Ck|;
• dimensione: ogni cluster deve avere una dimensione gestibile da un algoritmo MVS. Formalmente:
∀k, |Ck| ≤ α (3.9)
dove α `e una costante che definisce le risorse computazionali e di memoria;
• copertura: la ricostruzione con cluster deve portare a perdite di detta- glio minime rispetto al risultato ottenibile dall’elaborazione dell’intero insieme di immagini. Formalmente:
3.6 Densificazione 105
∀i{# di punti coperti in Ii}
{# di punti in Ii} ≥ δ
(3.10)
cio`e la quantit`a di punti coperti (ossia ricostruibili in almeno un cluster ) rispetto al numero totale di punti deve essere maggiore o uguale a una certa costante δ.
L’algoritmo esegue 4 passi, dei quali gli ultimi due vengono ripetuti iterativamente finch´e le propriet`a precedentemente dette non sono rispettate:
1. Fusione di punti : partendo da un insieme di punti, casualmente si fon- de un punto con i suoi vicini, eliminando il punto e i vicini dall’input set, finch´e quest’ultimo non `e vuoto. Questa fase riduce significativa- mente la dimensione dell’input set e il tempo di esecuzione dei tre passi successivi;
2. Rimozione di immagini ridondanti : si verifica per ogni immagine se il vincolo di copertura vale ancora se l’immagine viene scartata; in caso affermativo, essa viene eliminata dall’insieme delle immagini di input. Le immagini sono ordinate per risoluzione crescente, in modo che quelle a bassa qualit`a vengano eliminate per prime;
3. Divisione dei cluster : Ogni cluster che viola il vincolo di dimensione viene suddiviso in componenti pi`u piccole. Si rappresenta un cluster come un grafo, dove i nodi sono le immagini, mentre gli archi misurano con i loro pesi il contributo di ciascuna coppia di immagini per la ri- costruzione MVS di alcuni punti. Quest’operazione elimina quindi gli archi con pesi pi`u bassi di una certa soglia;
4. Inserimento di immagini : si aggiungono immagini in ciascun cluster per garantire il vincolo di copertura, che pu`o essere stato violato nella fase precedente. Si costruisce una lista di azioni di inserimento di im- magini, ognuna delle quali misura l’efficacia nell’inserire un’immagine
in un cluster per incrementare la copertura. Le azioni sono quindi or- dinate in ordine decrescente di efficacia ed eseguite finch´e il vincolo di copertura non `e soddisfatto.
PMVS
Calcolati i cluster, l’algoritmo PMVS [17] ricostruisce i punti 3D per ciascun cluster indipendentemente. Esso sfrutta i cluster prodotti da CMVS per costruire patch rettangolari coi quali aumentare la densit`a della nuvola di punti. Definiamo un patch p come un rettangolo con centro c(p) e normale n(p) orientata verso la camera che lo osserva. Per ogni patch si pu`o definire:
• un’immagine di riferimento R(p);
• un insieme di immagini S(p) dove p dovrebbe essere visibile ma pu`o non esserlo in pratica a causa di motion blur, highlights o ostacoli in movimento;
• un insieme di immagini T (p) in cui il patch `e individuato (R(p) ∈ T (p)). Per ogni immagine, invece, si definisce una griglia regolare di celle Ci,j, in
ognuna delle quali l’algoritmo cerca di ricostruire almeno un patch, adottando una procedura match-expand-and-filter :
• Matching: i keypoint calcolati vengono collegati (matched) tra le di- verse immagini tramite gli operatori Harris e Difference-of-Gaussians (DoG ), producendo un insieme sparso di patch;
• Expansion: una tecnica di espansione aumenta il numero di pixel in ogni regione, portando a un insieme denso di patch;
• Filtering: i filtri di qualit`a e visibilit`a eliminano gli abbinamenti errati che non sarebbero visibili nella mesh finale.
Nella prima fase, si utilizzano gli operatori Harris e DoG per individuare gli angoli e i blob in ciascuna immagine. Per ogni cella di un’immagine,
3.6 Densificazione 107
si calcolano gli n massimi locali dei due operatori con le risposte maggiori. Individuate queste feature, esse vengono collegate in modo da costruire un insieme sparso di patch.
Nella fase di espansione, iterativamente si aggiungono nuovi vicini ai patch esistenti finch´e tutte le superfici del modello non sono coperte. Intuitiva- mente, due patch p e p0 sono considerati vicini se appartengono a due celle adiacenti C(i, j) e C(i0, j0) della stessa immagine. Il patch p0 viene inizializ- zato con i valori di p, quindi R(p0) = R(p), T (p0) = T (p) e n(p0) = n(p). Il centro c(p0) corrisponde al punto in cui il raggio di vista che passa attraverso il centro di C(i0, j0), cio`e la cella a cui appartiene p0, si interseca con il piano contenente il patch p. Il centro e la normale di p0 sono raffinate tramite una procedura di ottimizzazione, quindi si calcolano gli insiemi S(p0) e T (p0). Il patch p0 viene accettato e inserito nella nuvola densa di punti se|T (p0)| ≥ γ, cio`e se il patch viene individuato in almeno γ immagini.
Nell’ultima fase, vengono applicati due filtri: un filtro di qualit`a e uno di visibilit`a [16]:
• Il filtro di qualit`a filtra i cluster pi`u distanti dal modello che hanno una densit`a di punti minore rispetto ai cluster pi`u vicini. Il filtro calcola per ogni cluster un istogramma {Hl} dove Hl `e la somma delle precisioni
di ricostruzione dei punti contenuti. Vengono quindi filtrati i punti i cui valori nell’istogramma sono minori della met`a del valore massimo; • Il filtro di visibilit`a calcola quante volte la ricostruzione di un punto da
parte di un cluster entra in conflitto con le ricostruzioni di altri cluster. Il punto viene quindi scartato se tale numero `e maggiore di una certa tolleranza.