Adattazione anisotropa di griglia applicata alla segmentazione di immagini

SCUOLA DI INGEGNERIA DEI SISTEMI

Corso di Laurea Magistrale in

Ingegneria Matematica

ADATTAZIONE ANISOTROPA DI GRIGLIA

APPLICATA ALLA SEGMENTAZIONE DI IMMAGINI

Relatore :

Prof. Simona PEROTTO Correlatore :

Prof. Luca FORMAGGIA

Tesi di Laurea di : Nicoletta PAPUCCI Matr. 750733

In questo lavoro di tesi consideriamo il problema della segmen-tazione delle immagini nell’ambito di una risoluzione agli ele-menti finiti. Incorporiamo il metodo Region-Scalable Fitting Ener-gy con il noto algoritmo di Split Bregman, in modo da ottenere una tecnica robusta e efficiente per la segmentazione di immagi-ni con intensit`a disomogenea. Successivamente usiamo un ap-proccio adattativo, basato su uno stimatore anisotropo a poste-riori dell’errore di discretizzazione. Attraverso diversi esempi applicativi, confrontiamo i risultati prodotti attraverso la pro-cedura adattativa con quelli ottenuti senza adattazione o con una strategia di adattazione euristica. In particolare mostriamo come le griglie adattate siano pi `u efficienti, sia in termini di co-sto computazionale (cio`e constano di un minor numero di ele-menti), sia per la maggiore regolarit`a delle segmentazioni cos`ı ottenute.

In this work we deal with the image segmentation problem by resorting to the finite element approach. We merge the Region-Scalable Fitting Energy method with the well-known Split Breg-man algorithm, in order to obtain a robust and efficient tech-nique suited to segment images with intensity inhomogeneity. Then we use an adaptive approach based on an anisotropic a posteriori error estimator for the discretization error associated to the finite element discretization. By means of several prac-tical examples, we compare the results yielded via the adapti-ve procedure with those obtained without any grid adaptation or with a heuristic mesh adaptation strategy. In particular we show that the adapted triangulations are more efficient, since they allow to improve the quality of the image contours (essen-tially in terms of smoothness), while reducing the number of mesh elements (i.e. the computational cost).

Introduzione 1

1 La segmentazione delle immagini 3

1.1 Immagini digitali . . . 4

1.2 Alcuni algoritmi euristici . . . 5

1.3 Modello di Mumford-Shah . . . 8

1.4 Metodi ai contorni attivi . . . 12

1.4.1 Metodi edge based . . . 13

1.4.2 Metodi region based . . . 19

2 Ricerca del minimo 29 2.1 Introduzione al calcolo delle variazioni . . . 29

2.2 Algoritmo iterativo di minimizzazione . . . 31

2.2.1 Metodo di Bregman . . . 31

2.2.2 Metodo di Split Bregman . . . 33

2.3 Applicazione ai problemi di segmentazione . . . 35

2.3.1 Globally Convex Segmentation . . . 35

2.3.2 Applicazione a Chan-Vese . . . 39 2.3.3 Applicazione a RSF . . . 40 3 Adattivit`a di griglia 43 3.1 Introduzione . . . 43 3.1.1 Errore di discretizzazione . . . 44 3.1.2 Tecniche di adattivit`a . . . 45 3.2 Stima dell’errore . . . 47 3.2.1 Stimatori a priori . . . 49 3.2.2 Stimatori a posteriori . . . 50 3.3 Stimatori recovery-based . . . 54 3.3.1 Operatori di recovery . . . 55

3.3.2 Tecniche di ricostruzione del gradiente . . . 58

3.3.3 Propriet`a . . . 61

4.2 Il contesto anisotropo . . . 66

4.3 Stime d’interpolazione anisotrope . . . 67

4.4 Stime anisotrope a posteriori . . . 70

4.5 Stimatore ZZ anisotropo . . . 71

4.6 Procedura di adattazione anisotropa . . . 72

5 Risultati sperimentali 75 5.1 Alcune considerazioni introduttive . . . 75

5.2 Implementazione . . . 77

5.2.1 Discretizzazione del problema parabolico . . . 78

5.2.2 Algoritmo di Split-Bregman . . . 79

5.2.3 Adattazione di griglia . . . 80

5.3 Parametri del modello . . . 83

5.4 Validazione del modello . . . 91

5.4.1 Adattazione euristica . . . 91

5.4.2 Confronto tra due tecniche di adattazione . . . 100

Conclusione e sviluppi futuri 105

Elenco delle Figure 109

Il trattamento delle immagini `e una disciplina molto vasta che comprende l’insieme delle tecniche di analisi e modifica delle immagini digitali: tra queste citiamo, a titolo d’esempio, il deblurring, il denoising, l’inpainting, la segmentazione e la ricostruzione di superfici. Lo scopo comune a queste discipline `e l’estrazione di informazioni a partire dall’immagine oppure il miglioramento della qualit`a della stessa. Le applicazioni possono essere svariate, in campo medico, artistico o tecnologico (si veda, ad esempio, [20, 38, 41]).

Lo spiccato interesse di questi problemi ha suscitato, a partire dagli anni ’90, una crescente attenzione della comunit`a scientifica nei confronti della definizione di modelli e metodi matematici in grado di descrivere e gestire tali processi. Questi modelli e questi metodi fanno essenzialmente riferi-mento alla teoria delle equazioni differenziali a derivate parziali o al cal-colo variazionale. Risulta evidente quindi la necessit`a di discretizzare le equazioni di interesse, in modo da poterne calcolare almeno una soluzio-ne approssimata. Nell’ambito del trattamento delle immagini, tra i meto-di meto-di meto-discretizzazione pi `u ricorrenti citiamo il metodo alle meto-differenze finite ([19, 22, 74]) e il metodo agli elementi finiti ([17, 58, 32]). Il primo `e quel-lo di gran lunga pi `u inflazionato a causa delle propriet`a intrinseche delle immagini digitali (ogni pixel pu `o infatti essere associato ad un nodo della griglia strutturata tipica di un metodo alle differenze finite). L’uso di una discretizzazione agli elementi finiti risulta invece sicuramente pi `u atipico.

Il presente lavoro di tesi pu `o essere collocato in questa seconda classe di contributi: si tratta di una scelta certamente innovativa, forse un po’ azzar-data, ma consapevole. Infatti competenze specifiche maturate nell’ambito dell’adattazione anisotropa di griglia, unite ad una buona dose di curio-sit`a intellettuale ci hanno spinto ad applicare ad un nuovo campo, quale quello della segmentazione delle immagini (cio`e riconoscimento dei suoi contorni), tecniche di adattazione gi`a ampliamente consolidate in svaria-ti contessvaria-ti. In parsvaria-ticolare, ricorreremo ad una adattazione anisotropa di griglia guidata da stimatori a posteriori per l’errore di discretizzazione.

L’idea alla base dell’utilizzo di tecniche di adattivit`a di griglia in questo frangente `e la seguente: i contorni degli oggetti contenuti in un’immagi-ne occupano una regioun’immagi-ne limitata della stessa, quindi sembra inutilmente

l’accuratezza della risoluzione proprio nelle aree dell’immagine corrispon-denti alla posizione dei suoi contorni. Questo obiettivo pu `o essere facil-mente raggiunto a patto di avere una griglia adattata in corrispondenza di tali contorni. In questa tesi si mira proprio a verificare, attraverso am-pia validazione numerica, come le griglie adattate permettano di ridurre la complessit`a del problema in esame. Notiamo che con una discretizzazione alle differenze finite si sarebbe potuto fare adattazione di griglia solamente usando griglie non conformi, tipologia di griglia non di nostro interesse.

Nel primo capitolo della tesi, dopo aver descritto brevemente la strut-tura delle immagini digitali, introduciamo formalmente il problema della segmentazione di un’immagine. La trattazione segue l’ordine cronologico di sviluppo dei vari modelli, a partire dal pionieristico lavoro di D. Mum-ford e J. Shah, fino alle sue evoluzioni pi `u recenti. Concludiamo descriven-do il modello, detto Region Scalable Fitting Energy, che abbiamo scelto per analizzare gli eventuali vantaggi apportati da un’adattazione di griglia.

Tutti gli approcci per la segmentazione di un’immagine presentati nel primo capitolo sono basati sulla minimizzazione di opportuni funzionali non necessariamente convessi che, come tali, non ammettono necessaria-mente un unico minimo globale. Per questo motivo nel secondo capitolo introduciamo un algoritmo di segmentazione delle immagini basato sul-l’uso di funzionali convessi, derivato da uno dei modelli presentati nel primo capitolo. In seguito descriviamo un algoritmo di minimizzazione particolarmente efficace proprio per la risoluzione di problemi convessi.

Il terzo capitolo tratta il problema dell’adattivit`a di griglia. Innanzitut-to forniamo una panoramica delle diverse tecniche di adattivit`a ricorrenti in letteratura, sia quelle euristiche, sia quelle guidate da stime dell’errore di discretizzazione. Ci soffermiamo successivamente sulla teoria dei cosid-detti stimatori a posteri di tipo recovery-based, che sono poi quelli da noi utilizzati per la segmentazione delle immagini.

Nel quarto capitolo ci concentriamo dapprima sul contesto anisotropo per l’adattazione di griglia. Successivamente forniamo alcuni esempi di stime anisotrope sia a priori sia a posteriori per l’errore di discretizzazione. Infine spieghiamo come tali stime possano essere utilizzate nella pratica per guidare un’adattazione anisotropa di griglia.

L’ultimo capitolo `e dedicato alla descrizione dell’algoritmo implemen-tato e all’analisi dei diversi casi test. In un primo momento ci focalizziamo sui vantaggi apportati da un’adattivit`a di griglia di tipo euristico rispetto alla soluzione del problema su una griglia non adattata. Confrontiamo poi tali risultati con quelli ottenuti usando una procedura pi `u rigorosa, guidata da uno stimatore a posteriori anisotropo dell’errore.

La segmentazione delle

immagini

Le immagini che popolano la vita quotidiana - in fotografie, giornali o film - non sono altro che proiezioni bidimensionali di oggetti tridimensionali. Nella realt`a tali oggetti sono facilmente riconoscibili come entit`a distinte, grazie alle loro caratteristiche geometriche e alla loro posizione nello spa-zio. Questo processo innato di separazione effettuato dal nostro cervello pu `o essere riprodotto in maniera automatica sulle immagini digitali tramite la cosiddetta segmentazione, il cui studio sar`a argomento di questo capitolo. Lo scopo della segmentazione `e proprio quello di semplificare la rappre-sentazione delle immagini suddividendole nelle loro regioni pi `u significa-tive, che possono essere localizzate sfruttando caratteristiche salienti come la posizione dei bordi o l’intensit`a del colore. Pi `u precisamente, la segmen-tazione `e il processo con il quale si classificano i pixel dell’immagine che hanno caratteristiche (colore, intensit`a, texture) comuni, separandoli dalle regioni adiacenti con caratteristiche significativamente differenti.

L’ambito `e ovviamente quello del trattamento delle immagini e le appli-cazioni sono svariate. Ad esempio, l’impiego delle tecniche di segmenta-zione `e molto diffuso in medicina, dove tali tecniche possono essere sfrut-tate per effettuare diagnosi, misurare l’estensione di un tessuto o eseguire operazioni chirurgiche assistite dal computer [57]. Inoltre, il riconoscimen-to di conriconoscimen-torni effettuariconoscimen-to su una sequenza di immagini, come quella forni-ta da una risonanza magnetica, permette di ricostruire la forma tridimen-sionale degli oggetti [76]. Altri campi di applicazione sono l’intelligenza artificiale o la machine vision, scienza che si occupa di fornire tecnologie di controllo e applicazioni industriali basate sull’analisi automatica delle immagini [69].

Grazie alla variet`a di applicazioni e a causa della difficolt`a del proble-ma, nel tempo sono stati sviluppati numerosi algoritmi per la segmenta-zione delle immagini e la ricerca `e a tutt’oggi ancora attiva. Nella

Sezio-ne 1.2 citiamo gli approcci principali, per poi concentrare l’attenzioSezio-ne sui metodi basati su equazioni a derivate parziali nelle sezioni successive. In particolare, il modello di Mumford e Shah, ricordato nella Sezione 1.3, ha rappresentato il primo tentativo di inquadrare il problema della segmen-tazione come minimizzazione di un funzionale il cui valore dipende dalle informazioni estrapolate dall’immagine. Esso ha posto le basi dei metodi di segmentazione sviluppati negli anni successivi, i pi `u noti dei quali sono presentati in questo capitolo in ordine cronologico.

I metodi ai contorni attivi, dettagliati nella Sezione 1.4, mirano ad ot-tenere una descrizione precisa della geometria dei contorni sfruttando la nozione di funzione di level-set. Come si vedr`a nel seguito il vantaggio di tali metodi rispetto a quello di Mumford-Shah risiede nella maggiore semplicit`a della loro trattazione teorica.

Un problema quasi insormontabile nell’ambito del trattamento delle immagini deriva dalle caratteristiche fortemente differenti che possono as-sumere le figure! Infatti esistono immagini dai contorni molto ben definiti, altre invece in cui i contorni non esistono e sono difficilmente riconoscibili anche ad occhio nudo (si pensi, ad esempio, alla rappresentazione di una galassia). Per questo motivo si vedr`a che non esiste un approccio sempre vincente; nella trattazione si cercher`a di evidenziare i limiti di ogni metodo e di introdurre la tecnica che permette di sormontarli, nel caso essa esista.

Purtroppo gli approcci presentati in Sezione 1.4 sono basati sulla mini-mizzazione di funzionali non necessariamente convessi, di cui quindi non `e possibile trovare un minimo globale tramite le usuali tecniche del calcolo delle variazioni. Gli algoritmi che permettono di riformulare questi meto-di come problemi meto-di minimizzazione convessa e meto-di trovarne la soluzione unica verranno presentati nel prossimo capitolo.

1.1

Immagini digitali

L’acquisizione di un’immagine `e il processo di conversione analogico-digi-tale della stessa. Tale processo `e composto da una prima fase di filtraggio, a cui segue il campionamento del segnale continuo, e infine la quantizza-zione dei campioni. Cos`ı facendo si ottiene una rappresentaquantizza-zione discreta dell’immagine, che pu `o essere di tipo vettoriale o bitmap.

Alla prima categoria appartengono le immagini formate da un insieme di primitive geometriche (quali punti, linee, poligoni), assemblate poi per ottenere le forme pi `u complesse. Le immagini vettoriali sono immagazzi-nate nei computer attraverso le equazioni matematiche di tali forme geo-metriche, e non hanno una risoluzione fissa. Possono infatti essere risca-late arbitrariamente per produrre una figura con la risoluzione desiderata. Questo tipo di rappresentazione `e adatto per descrivere figure semplici, ed `e particolarmente utilizzato per il rendering tridimensionale.

Diversamente, le immagini bitmap sono costituite da una matrice di punti, detti pixel (dall’inglese picture element), a ognuno dei quali `e asse-gnato un valore ottenuto con il processo di quantizzazione. Tale valore di-pende dalle caratteristiche di intensit`a e di colore della sorgente analogica nel punto corrispondente al pixel. La descrizione dell’immagine `e quindi effettuata punto per punto; il numero dei pixel, corrispondente al livello di discretizzazione, influenza la risoluzione e di conseguenza la qualit`a del-l’immagine. Si possono distinguere diversi tipi di immagini in base alle informazioni processate per assegnare un valore ai pixel. Le pi `u comuni sono due:

• immagini in scala di grigi: ogni pixel assume un valore che indica l’intensit`a del grigio di quel punto.

• immagini a colori: ogni pixel contiene informazioni sul livello di in-tensit`a dei colori fondamentali. Nel modello di colore RGB, uno dei pi `u utilizzati, i colori fondamentali sono tre: rosso, verde e blu. Il numero di toni di grigio (o di colori) che possono essere rappresenta-ti dipende dalla quanrappresenta-tit`a di bit urappresenta-tilizzarappresenta-ti per descrivere un pixel. Questo numero, la cosiddetta profondit`a p, limita il numero dei valori i che pu `o assumere l’intensit`a luminosa in ogni pixel:

i∈N : i ≤2p−1.

Per p=1 si ottiene un’immagine in bianco e nero, per p =8 un’immagine a 256 toni di grigio (o colori), e infine per p=24 un’immagine costituita da 16,7 milioni di toni.

Concentreremo la nostra trattazione sulle immagini bitmap a scala di grigi, in quanto ogni immagine a colori possiede un’analoga rappresentazione in scala di grigi che non compromette l’esito della segmentazione.

Al fine di inquadrare formalmente il problema della segmentazione, in-troduciamo una rappresentazione analitica delle immagini digitali. Innan-zitutto il dominio aperto e limitato Ω ⊂ R2 _{`e il supporto dell’immagine}

stessa, spesso costituito da un semplice rettangolo. L’immagine pu `o essere pensata come una funzione

u(x):Ω→ [0, 255], ∀x∈ Ω

il cui valore in x corrisponde all’intensit`a locale della luce.

1.2

Alcuni algoritmi euristici

I numerosi approcci alla segmentazione presenti in letteratura derivano dalla richiesta di segmentare immagini intrinsecamente molto diverse tra loro. Infatti non esiste una soluzione universale al problema della segmen-tazione, e spesso `e necessario combinare tecniche differenti per ottenere i

risultati desiderati. L’obiettivo di questa sezione `e innanzitutto quello di fornire una panoramica di alcuni metodi di segmentazione che chiamere-mo euristici, per poi proseguire con l’introduzione di un’ambientazione pi `u formale.

Thresholding

Si tratta della forma pi `u semplice di segmentazione, largamente diffusa nei software di grafica. In pratica consiste nel confrontare l’intensit`a di ogni pi-xel con un dato valore di soglia: se inferiore, il pipi-xel apparterr`a allo sfondo, altrimenti sar`a in primo piano. Come si pu `o immaginare, i risultati ottenu-ti con questo metodo sono molto approssimaottenu-tivi, e la ricerca del valore di tolleranza ottimale non `e immediata [67].

Clustering

Il clustering consiste nella suddivisione del dominio iniziale in sottodomini attraverso una tecnica iterativa. L’algoritmo pi `u diffuso `e il K-mean: inizial-mente si partiziona l’immagine in K regioni (o cluster) e si trovano i loro centri. Poi ogni pixel viene associato al cluster il cui centro `e pi `u vicino in termini di colore, intensit`a, posizione o una media pesata di questi fattori. In seguito si ricalcola il valore centrale dei cluster e si ripete lo step pre-cedente fino a convergenza. La soluzione ottenuta non `e necessariamente quella ottima. Esistono diversi algoritmi di clustering, che si differenziano sia per il criterio con cui si sceglie il numero di cluster, sia per il tipo di logica iterativa (fuzzy, probabilistica, split and merge) [48].

Region-growing

Il primo metodo di questo tipo comparso in letteratura `e il cosiddetto see-ded region growing [1]. Questo metodo richiede in input una serie di regioni (dette semi), ognuna corrispondente ad un oggetto da segmentare. In se-guito le regioni vengono allargate aggiungendo il pixel tra quelli confinan-ti con l’intensit`a pi `u simile al valore medio della regione; si procede cos`ı finch´e non si allocano tutti i pixel. Una variante di tale metodo sfrutta le informazioni statistiche di ogni regione per valutare, tramite test d’ipotesi, quali pixel inglobare. Altre varianti invece non richiedono l’imposizione delle condizioni iniziali, cio`e l’assegnazione dei seeds [61].

Edge-detection

Il riconoscimento dei contorni `e un campo a s´e stante e ben sviluppato del trattamento delle immagini. La sola individuazione dei bordi non permette tuttavia di riconoscere le regioni significative di un’immagine: infatti molti bordi possono non essere chiusi o formare complesse intersezioni. Si tratta comunque di un buon punto di partenza, motivo per cui queste tecniche vengono spesso usate come basi per altri metodi di segmentazione [80].

(a) Immagine originale

(b) Thresholding multiplo (c) Clustering

(d) Edge detection (e) Split-and-Merge

Figura 1.1: Confronto tra diverse tecniche di segmentazione. I valori in ros-so indicano la media pesata della distanza tra gli oggetti originali e quelli trovati con segmentazione.

Grafi

In questo caso l’immagine viene rappresentata come un grafo pesato, in cui i nodi sono associati ad uno o pi `u pixel e i pesi dei lati indicano la somiglianza tra i pixel adiacenti. Per partizionare in modo efficace i nodi si possono sfruttare vari algoritmi (random walker, minimum spanning tree, tagli...) [68, 44].

Split and Merge

Questo algoritmo iterativo analizza l’immagine iniziale e, nel caso essa non sia omogenea, la divide in quattro sottodomini; procede poi in modo analo-go sui sottodomini cos`ı individuati. Viceversa, se quattro sottodomini sono omogenei, vengono uniti. Questo procedimento ricorsivo si applica finch´e non si ottiene l’immagine segmentata [46].

In Figura 1.1 si riporta uno studio comparativo tra quattro delle tec-niche di segmentazione citate, tratto da [65], in cui si possono apprezzare pregi e difetti di ciascun metodo. In 1.1(b) si utilizza un metodo di thre-sholding multiplo, cio`e si fissano pi `u valori di soglia: quando il numero di classi da separare `e troppo alto si perde precisione e, come risultato, anche i contorni dell’immagine vengono segmentati. Molto pi `u preciso `e il clu-stering mostrato in 1.1(c), nonostante soffra di dipendenza dai dati iniziali e sia necessario effettuarlo pi `u volte per ottenere un buon risultato. La

seg-mentazione basata sul riconoscimento dei contorni mostrata in figura 1.1(d) non riesce ad identificare con precisione tutti i contorni: si nota infatti che i bordi evidenziati sono leggermente disconnessi. Il risultato peggiore `e mo-strato in 1.1(e), in cui l’algoritmo di split-and-merge con un unico valore di soglia non riesce a catturare la complessit`a dell’immagine. Si noti infine co-me nessuno di questi co-metodi riesca a riconoscere, in particolare, i contorni interni della lettera P e del numero 9.

La scarsa qualit`a della segmentazione ottenuta attraverso tali metodi euristici giustifica l’esigenza di un’analisi pi `u teorica del problema. Seg-mentare un’immagine significa trovare una curvaΓ che partiziona il domi-nioΩ nell’insieme delle sue componenti connesse Ωj:

Ω= [

j

Ωj

in modo tale che l’immagine iniziale u0 sia discontinua attraverso i

bor-di Γ e viceversa le sue variazioni all’interno di ogni regione Ωj siano di

piccola entit`a. Ogni Ωj corrisponde ad un oggetto fisico, o ad una forma

geometrica facilmente distinguibile di cui si vuole determinare il contorno

∂Ωj.

L’obiettivo quindi `e duplice: si vuole ottenere una partizione dell’im-magine nelle sue regioni significative{Ω<sub>j</sub>, j = 1, . . .}e, allo stesso tempo, descrivere il contorno Γ di tali regioni come entit`a geometrica. La diffi-colt`a risiede proprio nel formulare un unico problema che risponda ad en-trambe queste necessit`a. Una soluzione formalmente rigorosa si basa sulla minimizzazione di un opportuno funzionale energia ed `e descritta nella prossima sezione.

1.3

Modello di Mumford-Shah

Mumford e Shah proposero nel 1989 un modello di segmentazione inno-vativo: per la prima volta un’analisi teorica rigorosa unifica la ricerca delle regioni di un’immagine a quella del loro contorno [53]. Nonostante questo metodo soffra di una trattazione teorica abbastanza complicata e la buona positura del problema sia garantita unicamente in uno spazio funzionale piuttosto ristretto, esso ha posto le basi per le pi `u recenti evoluzioni nel campo della segmentazione.

Il problema `e formulato come minimizzazione di un funzionale ener-gia rispetto alle incognite u e K, rispettivamente approssimazione continua a tratti dell’immagine e insieme dei contorni ossia delle discontinuit`a di u. Richiedere a priori la regolarit`a di K sarebbe troppo restrittivo; si cer-ca quindi la soluzione in una classe pi `u ampia di funzioni non continue, dove la lunghezza `e data dalla misura di Hausdorff (N-1)-dimensionale

Definizione: Per ogni sottoinsieme F diRned ogni numero reale non negativo s la misura di Hausdorff s dimensionale di F `e data da

Hs_{(F) = lim} δ→0+ H_δs(F) =sup δ>0 Hs δ(F) dove, per 0< δ< +∞, Hs_δ(F) = ωs 2s inf    +∞

∑

con diam Uj =sup{|x−y|: x, y∈Uj}. La costante

ωs =πs/2

Z ∞

0 e

−x_xs/2_dx

−1

`e positiva e finita per ogni s.

Si cerca quindi la coppia(u, K)che minimizza il funzionale F(u, K) = Z Ω\K (u−u0)2dx+α Z Ω\K |∇u|2_dx+ βHN−1(K), (1.1)

dove K `e un insieme chiuso, u0 `e l’immagine iniziale, α e β sono delle

co-stanti di scala positive che giocano il ruolo di fattori di penalizzazione e u ∈ H1_{(Ω\K). Si noti che, nel seguito, si usa la notazione standard per}

indicare gli spazi di funzioni Lebesgue misurabili [64]: • Cn,α_{(Ω), con n intero non negativo e 0 ≤}

α ≤ 1, `e lo spazio delle

funzioni f che soddisfano, insieme con le loro derivate fino all’ordine n-esimo, la condizione di H ¨older:

|f(x) − f(y)| ≤C|x−y|α

per qualche costante positiva C.

• Lp(Ω), con 1 ≤ p < ∞, `e lo spazio di Banach (per p = 2 di Hilbert) delle funzioni misurabili:

f :Ω→R t.c. kfk_p = Z Ω|f(x)| p_dx 1/p <∞.

• L∞(Ω)`e lo spazio di Banach delle funzioni limitate quasi ovunque: f :Ω→_{R t.c.} kfk_∞ =inf{C≥0 :|f(x)| ≤C q.o.

• Wk,p_{(Ω)`e lo spazio di Sobolev delle funzioni}

f :Ω→R∈ Lp(Ω) t.c. Dα_{f ∈ L}p₍Ω₎

per ogni multi-indice∀α∈N2con|α| ≤k. In particolare vale

Hk_{(Ω) =W}k,2_(Ω).

Il significato dei tre termini costituenti il funzionale F in (1.1) rispecchia gli obiettivi principali di un problema di segmentazione. Il primo termine `e il cosiddetto termine di fedelt`a, in quanto assicura che u sia una buona approssimazione in norma L2(Ω\K) dell’immagine iniziale. Il secondo permette di identificare le regioni, i cui contorni sono individuati da un valore elevato di∇u; il terzo previene un’eccessiva segmentazione.

Gli autori in [53] fanno la seguente congettura riguardo all’esistenza e alla regolarit`a della soluzione del problema di minimo (1.1):

Congettura 1(di Mumford-Shah)

Esiste una coppia(u, K)che minimizza F tale che l’insieme di discontinuit`a di K `e l’unione di un numero finito di curve C1,1. Inoltre, ogni curva pu`o terminare solo in due modi: o con un’estremit`a libera, o in una giunzione tripla in cui tre curve si incontrano con un angolo di 2π/3.

La difficolt`a nello studio di (1.1) deriva dalla diversa natura delle inco-gnite: u `e una funzione definita in uno spazio N-dimensionale, mentre K `e un insieme (N-1)-dimensionale. Per avere un risultato di esistenza e uni-cit`a del minimo servendosi del metodo diretto del calcolo delle variazioni, il problema deve essere ambientato in una topologia in cui F sia semicon-tinuo inferiormente e le sequenze minimizzanti siano compatte [70]. Sia E un insieme di Borel diRN con frontiera topologica ∂E; allora si pu `o facil-mente provare che la mappa E → HN−1<sub>(∂E)non gode di semicontinuit`a</sub>

inferiore rispetto a nessuna topologia compatta. Per ovviare a questo pro-blema `e necessario sostituire in (1.1) l’incognita K con l’insieme dei salti di u definito come Su = {t∈R : u−(t) 6= u+(t)}. Si ottiene il funzionale

G(u) = Z Ω(u−u0) 2_dx+ α Z Ω|∇u| 2_dx+ βHN−1(Su).

L’incognita u dovrebbe appartenere allo spazio BV(Ω)

BV(Ω) = {u∈ L1(Ω): V(u,Ω) < +∞}

delle funzioni a variazione limitata. La variazione totale di u si definisce come: V(u,Ω) =sup Z Ωu(x)div φ(x)dx :∀φ∈C 1 c(Ω, Rn),kφkL∞(Ω)≤1 

dove C1_c(Ω, Rn) `e lo spazio delle funzioni diRn continue e differenziabili, con supporto compatto contenuto inΩ. BV `e uno spazio di Banach dove, per ogni u∈ BV(Ω), sono definite la norma e la seminorma:

kuk_BV = kuk +V(u,Ω), |u|_BV =V(u,Ω). (1.2) Allo spazio BV appartengono alcune funzioni (come ad esempio quella di Vitali-Cantor) cosiddette patologiche a causa della loro particolarit`a di es-sere continue e monotone ma con differenziale nullo quasi ovunque. Per queste funzioni si ha che

inf

u∈BV(Ω)G

(u) =0,

quindi la ricerca di un minimo globale risulta inutile. Il minimo di G(u)

deve essere cercato in uno spazio pi `u ristretto, che escluda le funzioni pa-tologiche citate precedentemente. L’esistenza di una soluzione viene pro-vata da De Giorgi et al. in [28], introducendo il nuovo spazio funzionale SBV(Ω) delle funzioni speciali a variazione limitata. Per definire questo spazio bisogna partire dall’espressione della derivata nel senso delle distri-buzioni di u ∈ BV(Ω), che pu `o essere scomposta in tre termini nel modo seguente:

Du= ∇udx+Dju+Dcu.

Il primo termine `e la parte assolutamente continua del differenziale di u, il secondo `e la parte di salto e Dcu `e la parte di Cantor. Lo spazio di funzioni

SBV(Ω)`e il sottospazio proprio delle funzioni BV(Ω)tali per cui Dcu=0.

L’equivalenza tra i due problemi: inf u,K ( F(u, K), u∈ H1(Ω\K) ∩L∞(Ω), K⊂ Ω, K chiuso,HN−1_{(K) <∞} ) inf u {G(u), u∈SBV(Ω) ∩L ∞_(Ω)}

viene provata da Ambrosio in [3], dimostrando cos`ı l’esistenza di un mini-mo per il funzionale F. Esso pu `o essere calcolato appoggiandosi al seguen-te

Teorema 1.1

Sia(u, K)una soluzione di (1.1) che soddisfi la Congettura 1, per cui K `e composto da un numero finito di curve γi. Allora:

         α4u= −u0 suΩ\K, ∂u

∂N =0 su ∂Ω e sui due lati di ogni γi,

dove e(u) = (u−u0)2+α|∇u|2, u+ e u− sono le tracce di u su ogni

lato di K, curv(γi)`e la curvatura di γi, α e β sono le costanti di scala del

funzionale F e u0l’immagine iniziale.

La dimostrazione si pu `o trovare in [6], nella sezione 4.2.

Lo studio della regolarit`a di K assume un’importanza particolare; in-fatti, come mostrato in Figura 1.2, le condizioni di regolarit`a imposte dal-la Congettura 1 non sono in grado di garantire l’unicit`a deldal-la soluzione. La congettura di Mumford-Shah non `e dunque ancora stata dimostrata; tuttavia A. Bonnet ha fatto degli importanti progressi in questo senso [13].

L’approccio di Mumford-Shah ha una evidente limitazione pratica, in-fatti l’impossibilit`a di differenziare il funzionale in uno spazio adatto non permette di applicare le equazioni di Eulero-Lagrange; inoltre la discretiz-zazione dell’insieme di discontinuit`a risulta molto complicata. Una solu-zione numerica del funzionale di Mumford-Shah non pu `o cos`ı essere tro-vata direttamente; bisogna considerarne una sua approssimazione, quindi applicare una discretizzazione agli elementi finiti o alle differenze finite. Per trovare un funzionale che approssimi F(u, K) (o G(u)) ci si pu `o ap-poggiare alla nozione di Γ-convergenza e creare una serie convergente di funzionali regolari definiti su spazi di Sobolev. Le soluzioni presenti in let-teratura che si basano su questo metodo sono diverse, la prima nonch´e pi `u conosciuta `e dovuta ad Ambrosio e Tortorelli [4].

Figura 1.2: Due segmentazioni equivalenti per una data immagine (tratta da [6]).

1.4

Metodi ai contorni attivi

L’obiettivo dei modelli presentati in questa sezione non `e la ricerca di una partizione ottima dell’immagine come nel modello di Mumford-Shah, ben-s`ı l’individuazione delle sue frontiere. La geometria del contorno viene descritta attraverso una curva che evolve nel tempo e nello spazio, e la segmentazione si ottiene come risultato naturale di questo processo.

I metodi ai contorni attivi possono essere suddivisi in due classi prin-cipali, in base al tipo di informazioni che processano per guidare i

mo-vimenti della curva. Quelli basati sui contorni (edge-based models) usano informazioni locali sul gradiente di intensit`a per attrarre la curva verso i confini dell’oggetto da segmentare. Al contrario i metodi basati sulle re-gioni (region-based models) associano ad ogni area dell’immagine una data funzione, basandosi sulle informazioni di colore e intensit`a.

I primi studi riguardanti i metodi edge-based sono antecedenti alla for-mulazione del modello di Mumford-Shah; essi vengono introdotti nel pa-ragrafo 1.4.1 insieme alle evoluzioni successive. L’approccio al problema della segmentazione fornito da questi metodi `e del tutto innovativo; infatti l’evoluzione della curva K, l’incognita principale, viene descritta con un’e-quazione alle derivate parziali risolta con un metodo di level-set. Cionono-stante l’applicazione di tali metodi `e limitata a figure semplici con ridotte variazioni di intensit`a.

I modelli region-based godono di maggiore efficienza in quanto sono meno sensibili al rumore e permettono di processare immagini con con-torni poco definiti. Inoltre sono molto robusti rispetto all’inizializzazione della curva. Purtroppo tali modelli si basano sull’assunzione che l’intensit`a delle immagini sia statisticamente omogenea in ogni regione (PC : piecewise constant), ipotesi che limita il loro campo di applicazione. Nonostante la let-teratura dell’ultimo decennio sia ricca di metodi di segmentazione region-based, nel paragrafo 1.4.2 si `e scelto di dettagliare unicamente l’approccio proposto in [22] da Chan e Vese (in quanto utile per la trattazione succes-siva). Questi due autori propongono sia un modello PC, sia un secondo modello che permette di superare i limiti del primo grazie ad un approc-cio multifase. Qui si assume che le regioni siano descritte da funzioni lisce a tratti (PS: piecewise smooth); in questo modo diventa possibile segmenta-re immagini generiche con forti gradienti di intensit`a, seppusegmenta-re si paghi il prezzo di una bassa efficienza computazionale.

1.4.1 Metodi edge based Snakes

Il primo modello in letteratura che si propone di descrivere il movimento di una curva verso i contorni delle immagini `e dovuto a Kass, Witkin e Terzopoulos [47]. Nel 1987 questi autori hanno utilizzato un funzionale energia per controllare l’evoluzione di tale curva, a cui hanno dato il nome di snake.

Pi `u nel dettaglio, si consideri lo spazio delle curve diR2_:

C=nc :[a, b] →Ω, C1a tratti, t.c. c(a) =c(b)o, dove si vuole minimizzare l’energia data da:

J(c) = Z b a |c0(q)|2dq+β Z b a |c00(q)|2dq+λ Z b a g 2_(|∇u 0(c(q))|)dq, (1.3)

con β e λ moltiplicatori di Lagrange, e u0 immagine iniziale. La

funzio-ne g(|∇u0|), detta edge detector function, `e di fondamentale importanza in

quanto assume valori vicini allo zero nell’intorno dei contorni. Essa gode delle seguenti propriet`a:

• g :[0,+∞) → (0,+∞);

• g `e regolare e monotona decrescente; • g(0) =1, lim

s→+∞g(s) =0.

Solitamente si sceglie g(s) =1/(1+s2_).

I primi due termini in (1.3) rappresentano l’energia interna e rendono il comportamento della curva assimilabile a quello di una membrana, au-mentando la sua regolarit`a. L’ultimo termine `e l’energia esterna, che dipen-de dall’immagine iniziale u0, e indica quanto la curva tenda ad avvicinarsi

ai bordi (feature driven energy).

L’esistenza di un minimo locale nello spazio di Sobolev[W2,2(a, b)]2si prova facilmente, visto che il dominio `e chiuso e limitato. Tuttavia, non essendo il funzionale convesso, non si possono ottenere risultati di unicit`a. Un altro svantaggio di questo approccio `e la dipendenza di J dalla parame-trizzazione c della curva: `e possibile ottenere soluzioni diverse modifican-do la parametrizzazione della stessa curva iniziale.

Nella pratica questo problema pu `o essere risolto numericamente incorpo-randolo in uno schema dinamico tempo-dipendente, assimilando cio`e il movimento della curva ad un’evoluzione temporale. Si tratta per `o di uno schema instabile e con grande sensibilit`a alle condizioni iniziali.

Una variante dovuta a Cohen ([26]) introduce una forza esterna che in-duce lo snake a comportarsi come un palloncino che viene gonfiato fino ad adattarsi ai contorni dell’immagine. Il cosiddetto balloon model ridu-ce l’instabilit`a del metodo originario. Il modello si ottiene sostituendo a

(a) Contorno iniziale (b) Metodo di Kass et al. (c) Balloon method Figura 1.3: Confronto tra il modello originale degli snake e la modifica di Cohen (immagine tratta da [26]).

g2(|∇u0|)in (1.3) il termine:

F=k1N−k

∇u0

||∇u0||

dove N `e il versore normale alla curva, k1 `e un coefficiente che regola

l’in-tensit`a della forza e k una costante positiva dello stesso ordine di k1.

L’effet-to di tale forza F `e di esercitare una pressione verso l’esterno, proprio come se si stesse introducendo dell’aria in un palloncino, in modo da evitare i minimi locali. Ad esempio in Figura 1.3, si vede che nel metodo originale di Kass et al. la curva si blocca appena incontra un punto isolato, cosa che non succede invece con l’aggiunta della forza esterna.

Geodesic Active Contours

Come evidenziato dallo studio di Caselles et al. del 1997 ([18]), il secondo termine di (1.3), la cui funzione sarebbe quella di ridurre la curvatura, in realt`a `e ridondante. Infatti come si vedr`a in seguito (1.7) il modello riduce implicitamente la curvatura anche per β = 0. `E quindi naturale sostituire J(c)con il seguente funzionale definito sull’insieme C:

J1(c) = Z b a |c0(q)|2dq+λ Z b a g 2_(|∇u 0(c(q))|)dq. (1.4)

Si pu `o inoltre eliminare la scomoda dipendenza dalla parametrizzazione della curva e definire il funzionale intrinseco:

J2(c) =2 √ λ Z b a g (|∇u0(c(q))|)|c0(q)|dq. (1.5)

`E semplice mostrare che (1.5) `e intrinseco. A tale scopo si consideri una nuova parametrizzazione della curva q = φ(r), φ : [a0, b0] → [a, b], φ0 > 0 e

la si sostituisca in (1.5). Indicando c(φ(r)) = ¯c(r)si ottiene

J2(c) =2 √ λ Z b0 a0 g(|∇u0(c◦φ(r))|)φ 0₍ r) · |(c◦φ)0(r)|(φ0(r))−1dr =√λ Z b0 a0 g(|∇u0(¯c(r))|)|¯c 0_(r)|dr,

ritrovando un’espressione del tutto analoga alla (1.5).

Il funzionale (1.5) non `e altro che la definizione di lunghezza pesata di una curva, ottenuta moltiplicando la lunghezza Euclidea per il termine g(|∇u0(c(q))|).

L’equivalenza tra i due funzionali definiti in (1.4) e (1.5) non `e per `o scontata. Si ripropongono nel seguito i passi principali della dimostrazio-ne data da Aubert e Blanc-F´eraud in [5]. Si basa sulla seguente noziodimostrazio-ne di equivalenza tra problemi di minimizzazione, introdotta dagli stessi autori:

Definizione: Due problemi di minimizzazione J1(c)e J2(c)sono equivalenti se

esiste un intorno I(c)di c in cui il flusso che riduce maggiormente J1(c)riduce

anche J2(c)e viceversa.

Il primo passo per provare l’equivalenza dei due funzionali consiste nel calcolo delle loro derivate rispetto al tempo. Il parametro temporale t viene introdotto per descrivere la famiglia di curve in movimento c(t, q)

tali che c(0, q) = c(q) ∈ C; per comodit`a si pone Ji(t) = Ji(c(t, q)), con

i = 1, 2. Integrando per parti le espressioni dei funzionali e effettuando qualche passaggio algebrico si trova:

1 2J 0 1(t) = Z b a  ∂c ∂t, " −κ     ∂c ∂q     2 + hg∇g, Ni # N +  hg∇g, Ti −  T,∂ 2_c ∂q2  T  dq. 1 2J 0 2(t) = Z b a     ∂c ∂q      ∂c ∂t,h∇g, NiN−κgN  dq

dove N `e il versore normale alla curva, T quello tangenziale e κ la curva-tura. Si ricava facilmente che la direzione lungo la quale J1 si riduce pi `u

rapidamente `e data da:

∂c ∂t = κ     ∂c ∂q     2 − hg∇g, Ni ! N+  T,∂ 2_c ∂q2  − hg∇g, Ti  T (1.6) Analogamente, si trova che la direzione lungo la quale una curva con lun-ghezza pesata data da J2(c)si contrae pi `u velocemente `e:

∂c ∂t

= (κg− h∇g, Ni)N. (1.7)

Sostituendo il flusso per J1(t)dato da (1.6) nell’espressione di J20(t)e

studiando il segno dell’integranda cos`ı ottenuta, si trova che tale flusso `e una direzione di discesa anche per J2(t). Analogamente, si prova il

vice-versa e si ha cos`ı l’equivalenza dei due funzionali secondo la definizione appena data.

Il problema iniziale `e quindi sostituito dalla ricerca di un minimo glo-bale in C per il funzionale J2(c), pi `u pratico in quanto intrinseco (cio`e non

dipendente dalla particolare parametrizzazione della curva) e facilmente discretizzabile.

Il modello di Caselles et al. pu `o essere ulteriormente migliorato aggiun-gendo in (1.7) un termine con coefficiente α col doppio scopo di controllare espansione e restringimento del contorno e migliorare l’individuazione di oggetti concavi:

∂c

Cos`ı si pu `o scegliere una curvatura κ con segno non costante, che permette di individuare gli oggetti concavi, a patto che α≥0 sia abbastanza grande perch´e il segno di α+κnon cambi.

La formulazione (1.5)-(1.8) del problema di segmentazione, nota in let-teratura come Geodesic Active Contours (GAC), `e conveniente rispetto a quel-la originariamente introdotta da Kass et al.. Il suo vantaggio risiede nelquel-la possibilit`a di scrivere le equazioni di Eulero Lagrange associate al funzio-nale J2(c)in formulazione Euleriana con un approccio di tipo level set, che

non potrebbe invece essere usato per trovare un minimo di J1(c).

La nozione di level set, introdotta da Osher e Sethian in [56], gode di grande successo anche nel campo della segmentazione grazie alla sua im-mediatezza, che la rende adatta ad identificare l’insieme dei contorni di un’immagine. Questa formulazione `e basata sull’idea che una curva pu `o essere vista come il livello zero di una funzione in uno spazio di dimen-sione maggiore. Cio`e l’interfaccia ∂Σ ⊂ Rn<sub>pu `o essere vista come la linea</sub>

di livello zero di una funzione φ : Rn _{→ R (si veda la Figura 1.4). Per}

convenzione si prendeΣ= {x : φ(x) >0}.

In genere tale approccio viene utilizzato per trovare una soluzione ad equazioni del tipo:

   ∂c ∂t = JN, c(0, q) =c0(q), (1.9) che descrivono l’evoluzione di una curva c(t, q) che si muove lungo la sua componente normale con una velocit`a J. Si supponga innanzitutto l’esistenza di una funzione u :R+×R2 _{→R tale che}

u(t, c(t, q)) =0, ∀q,∀t ≥0.

Ipotizzando che u sia sufficientemente regolare, si pu `o calcolare il suo dif-ferenziale rispetto a t e sostituirvi l’espressione della velocit`a data in (1.9),

Figura 1.4: Basi del metodo di level set: una circonferenza pu `o essere vista come il livello zero di una funzione di dimensione maggiore.

ottenendo:

∂u

∂t(t, c(t, q)) +h∇u(t, c(t, q)), JNi =0.

Si pu `o considerare u come una funzione definita su tutto lo spazioR+×Ω;

quindi tenendo conto dell’espressione del vettore normale N, si riscrive la formulazione di level set (1.9) come:

           ∂u ∂t(t, x) =J|∇u(t, x)| per(t, x) ∈ (0,∞) ×Ω u(0, x) =d¯(x, c0), ∂u ∂N =0 per(t, x) ∈ (0,∞) ×∂Ω, (1.10)

dove c0(q) `e il contorno iniziale e ¯d(x, c0) `e la funzione distanza dotata di

segno: ¯ d(x, c0) = ( +d(x, c0) se x `e esterno a c0, −d(x, c0) se x `e interno a c0.

A condizione che J sia ben definita su tutto lo spazio, la curva c(t, q)che si cerca `e data dall’insieme di livello zero di u.

L’equazione (1.10) `e chiamata equazione di Hamilton-Jacobi e gode di alcune propriet`a molto interessanti. Uno dei vantaggi principali di questa formulazione `e la sua versatilit`a rispetto ai cambi di topologia di u=0. In-fatti l’insieme di livello zero pu `o modificarsi, spezzarsi o fondersi, ma tutti questi cambiamenti sono intrinseci nel modello e non devono essere pre-si in conpre-siderazione nell’approspre-simazione numerica. Inoltre tale approccio si estende facilmente a dimensioni maggiori, e gli elementi geometrici in-trinseci come la curvatura possono essere espressi in funzione di u. Que-ste propriet`a spiegano l’ampio utilizzo che si fa dei metodi di level set in svariati campi applicativi.

Ritornando alla soluzione del problema di segmentazione, il flusso in (1.8) `e del tipo (1.9). Svolgendo passaggi analoghi a quelli appena visti, si pu `o ottenere la sua formulazione di level set:

∂u ∂t = g(|∇u0|)  div  _∇ u |∇u|  +α  |∇u| + h∇g,∇ui, (1.11) con le stesse condizioni al bordo e iniziali di (1.10). L’azione del primo ter-mine ferma l’evoluzione della curva quando essa raggiunge i contorni degli oggetti. Il secondo termine invece aumenta l’attrazione della curva verso i suddetti contorni. Esistenza ed unicit`a della soluzione di questa PDE si dimostrano attraverso la teoria delle sopra- e sotto-soluzioni (si veda [6], sezione 4.3).

Analizzando l’espressione di (1.11) si nota ci `o che `e gi`a stato accennato all’inizio della sezione: la parte dell’equazione derivante dall’energia in-terna dipende in maniera importante dal gradiente dell’immagine iniziale.

(d) Contorno iniziale (e) Metodo di KWT (f) Metodo GAC

Figura 1.5: Confronto tra il metodo di Kass-Witkin e Terzopoulos e il Geo-desic Active Contour, modificando la curva iniziale (immagine ottenuta con MATLAB).

Quindi si tratta di modelli non adatti ad individuare i contorni di ti non ben definiti. Inoltre questo modello riesce a riconoscere un ogget-to unicamente quando la curva iniziale c0 circonda i suoi contorni, e non

pu `o individuare allo stesso tempo le frontiere interne ed esterne. Si pu `o concludere che questi metodi godono di propriet`a di segmentazione uni-camente locali, con un’alta sensibilit`a alle condizioni iniziali. Questo limite `e evidenziato nelle immagini di Figura 1.5: in alto il contorno iniziale non circonda l’immagine, e n´e il metodo originale di Kass, n´e quello basato sui contorni attivi riescono ad individuare le frontiere dell’oggetto. Invece in basso la scelta della curva iniziale permette al modello GAC di riconoscere i contorni dell’immagine geometrica, anche se non in maniera precisa.

Un ulteriore svantaggio dei metodi GAC si pu `o dedurre dalla partico-lare condizione iniziale imposta: u(0, x)`e una funzione distanza dotata di segno. Per `o l’equazione (1.11) non assicura che u(t, x)rimanga tale al pas-sare del tempo. Si impone quindi la necessit`a di reinizializzare regolarmen-te u risolvendo un’ulregolarmen-teriore PDE, riducendo cos`ı drasticamenregolarmen-te l’efficienza computazionale.

1.4.2 Metodi region based

Questi modelli presentano alcuni vantaggi rispetto a quelli descritti nella sezione precedente. Innanzitutto essi non si limitano a considerare le va-riazioni del gradiente, ma sfruttano le informazioni di tutta la regione cir-costante il contorno per controllare l’evoluzione della curva. La quantit`a di maggior interesse in tale contesto `e il valore medio dell’intensit`a dell’im-magine nelle regioni considerate: esso `e meno sensibile al rumore locale

e, se sfruttato adeguatamente, permette di segmentare anche immagini con contorni poco definiti. Inoltre i metodi region-based sono poco sensibili alla posizione iniziale della curva e permettono l’individuazione delle frontiere interne.

I modelli di Chan e Vese

Uno dei metodi pi `u popolari di questa classe `e stato sviluppato da Tony Chan e Luminita Vese nel 1999 ([22]). Si tratta di una combinazione tra i metodi classici ai contorni attivi e il modello di Mumford-Shah. Al con-trario dei primi per `o, il termine di arresto non dipende dal gradiente di intensit`a dell’immagine, bens`ı da una sua particolare segmentazione.

Si consideri, per semplicit`a, un’immagine come quella in Figura 1.6 composta unicamente da due regioni con intensit`a costanti a tratti, di va-lori ui₀ e uo₀ rispettivamente, e si immagini che la frontiera tra queste due aree sia il contorno C che si vuole ricostruire. Siano c1 e c2 due costanti,

che rappresentano la media dell’immagine iniziale u0 all’interno e

all’e-sterno di C, la curva in evoluzione. Nei metodi di level set quest’ultima `e il contorno di livello zero di una funzione continua φ : Ω → R, cio`e

C = {(x, y) ∈ Ω : φ(x, y) = 0}ed `e positiva all’interno di C e negativa all’esterno.

Seguendo [22] si introduce un’energia, la fitting energy, il cui minimo si trova quando la curva coincide con il contorno dell’immagine (C = C), cio`e quando i valori calcolati cisono vicini a quelli reali:

F(φ, c₁, c2) = µ Z Ωδ(φ)|∇φ| +ν Z ΩH(φ)dxdy + λ1 Z Ω|u0−c1| 2_H( φ)dxdy + λ2 Z Ω|u0−c2| 2_(1−H( φ))dxdy (1.12)

Figura 1.6: Immagine da segmentare: in nero il contorno da ricostruire e in rosso la curva in evoluzione.

dove H(·) `e la funzione di Heaviside e δ(x) = _dxd H(x)la sua derivata nel senso delle distribuzioni; µ > 0, ν ≥ 0, λ1 > 0 e λ2 > 0 sono costanti

positive. I primi due termini sono di regolarizzazione e rappresentano ri-spettivamente la lunghezza di C e l’area al suo interno, mentre i restanti due termini indicano in che misura le regioni individuate dalla curva C corrispondono con quelle da segmentare.

L’espressione delle costanti c1e c2si trova minimizzando la fitting

ener-gy per φ fissato: c1(φ) = Z Ωu0H(φ)dxdy Z ΩH(φ(x, y))dxdy , c2(φ) = Z Ωu0(1−H(φ))dxdy Z Ω(1−H(φ(x, y)))dxdy .

Si pu `o riconoscere nella prima espressione la media di u0all’interno della

regione individuata da{φ≥0}e nella seconda la sua media in{φ<0}.

Sostituendo in (1.12) queste espressioni, `e ora possibile minimizzare l’e-nergia rispetto a φ inserendo un parametro temporale che identifichi la di-rezione di massima discesa. Si ottiene la seguente equazione di Eulero-Lagrange:        ∂φ ∂t =δ(φ)  µdiv  ∇φ |∇φ|  −ν−λ1(u0−c1)2+λ2(u0−c2)2  inΩ, δ(φ) |∇φ| ∂φ ∂n =0 su ∂Ω. (1.13) Ai fini di aumentare la regolarit`a, `e necessario utilizzare nella pratica delle approssimazioni C∞di H e δ, che indichiamo rispettivamente con Hee δe,

tali che δe(x) = He0(x)nel senso delle distribuzioni. Una scelta standard

risulta la seguente: He(x) = 1 2  1+ 2 πarctan x e  , δe(x) = 1 π e e2+x2. (1.14)

Introducendo questa approssimazione non solo si semplifica il calcolo della soluzione di (1.13), ma si indirizza anche la ricerca del minimo verso il mi-nimo globale. Infatti, in questo modo, l’equazione (1.13) ha effetto su tutte le curve di livello e non unicamente su quelle di livello zero; si trova cos`ı il minimo globale indipendentemente dalla scelta del contorno iniziale. Inol-tre i contorni interni vengono individuati automaticamente. In Figura 1.7 si cerca di segmentare un’immagine priva di contorni definiti e si mette a

(a) (b) (c)

(d) Contorno iniziale (e) 500 iterazioni (f) 1000 iterazioni Figura 1.7: Confronto tra il metodo GAC (in alto) e quello di Chan e Vese (in basso). Immagine ottenuta con MATLAB.

confronto la performance di un metodo edge-based con quella di uno sche-ma region-based. Si apprezzi la precisione del modello di Chan e Vese che individua addirittura le stelle sparse nella galassia!

Esistono tuttavia alcuni aspetti critici anche di questo metodo. Sono essenzialmente due: innanzitutto, `e necessario reinizializzare φ perch´e sia una distanza rispetto alla sua curva di livello zero. Si tratta di una pro-cedura standard per un approccio di tipo level set alla quale si `e gi`a ac-cennato alla fine della sezione precedente. Generalmente viene effettuata risolvendo la seguente equazione di evoluzione (si veda [75]):

   ∂ψ ∂t =sign(φ(t))(1− |∇ψ|) ψ(0,·) =φ(t,·), (1.15)

essendo φ(t,·)la soluzione di (1.13) al tempo t. La nuova φ(t) `e data dal-la soluzione stazionaria di (1.15). Neldal-la pratica non `e necessario effettuare questa procedura ad ogni passo temporale, contenendo in questo modo l’aumento del costo computazionale associato a questa fase di restarting. Il secondo aspetto critico di questo metodo `e intrinseco nella sua formula-zione: il dominio pu `o essere suddiviso unicamente in due regioni. Non `e quindi possibile segmentare immagini presentanti topologie complesse o giunzioni triple.

Nonostante questi limiti, i risultati di segmentazione ottenuti con que-sto schema sono in generale pi `u che soddisfacenti. Nel complesso infatti

tale modello `e tra i pi `u diffusi, visto che rappresenta un ottimo compromes-so tra qualit`a dei risultati, semplicit`a di implementazione e ridotto tempo computazionale.

Come accennato nell’introduzione a questa sezione, Chan e Vese pro-pongono in [23] anche un’estensione multifase del metodo originale. Que-sto nuovo modello permette di rappresentare sia immagini PC sia PS con un numero ridotto di funzioni di level set. Nel seguito forniamo un’idea ge-nerale di questo approccio, rimandando all’articolo originale per maggiori dettagli.

Si considerino m=log n funzioni di level set φi(con i =1,· · · , m),

l’u-nione dei cui insiemi di livello zero rappresenter`a i contorni dell’immagine segmentata. Sia inoltreΦ = (φ1, . . . , φm)e H(Φ) = (H(φ1), . . . , H(φm))il

vettore delle funzioni di Heaviside in cui ogni componente pu `o assumere unicamente i valori 0 o 1. Tale vettore pu `o assumere n valori differenti, quindi si pu `o suddividere il dominioΩ in 2m fasi (o classi) definite nel se-guente modo: due pixels (x1, y1) e (x2, y2) appartengono alla stessa fase

se e solo se H(Φ(x1, y1)) = H(Φ(x2, y2)). Cos`ı ognuna delle n classi si

definisce come l’insieme dei punti

{(x, y)t.c. H(Φ(x, y)) =v∈ H(Φ(Ω)), con v vettore costante}. L’insieme delle fasi altro non `e che una copertura di Ω, ed ogni pixel ap-partiene ad una ed una sola fase.

Analogamente a quanto si ha nel modello bifase, si indica con cI la media

dell’immagine iniziale u0 per i punti appartenenti alla classe I. L’energia

da minimizzare `e quindi data da: Fn(Φ, c) =

∑

∑

essendo χIla funzione caratteristica della classe I e c il vettore costante

del-le intensit`a medie: c = (c1, . . . , cn). Si noti che con n=2 e m= 1 si ritrova

l’energia (1.12) con ν=0. Le equazioni di Eulero-Lagrange dipendono ov-viamente dal numero di fasi considerate, e sono quindi da calcolare caso per caso.

Gli autori propongono anche un’ulteriore estensione del modello al ca-so di funzioni lisce a tratti, mostrando come in questo caca-so il numero neces-sario di funzioni di level set sia ridotto, cos`ı come il costo computazionale. La scelta dell’inizializzazione delle classi e la necessit`a di ricavare le equa-zioni di Eulero-Lagrange rendono tuttavia questo metodo di scarso uti-lizzo pratico, contrariamente alla segmentazione binaria proposta in [22]. Quest’ultima gode invece di grande successo ed `e alla base di molti de-gli approcci per la segmentazione comparsi nede-gli ultimi anni, come quello descritto nel prossimo paragrafo.

(a) Originale (b) Thresholding (c) Chan-Vese

Figura 1.8: Errore di segmentazione per due immagini mediche (in alto una vena ai raggi X e in basso la RMN di un cervello). Tratta da [49].

Region Scalable Fitting (RSF)

In [49] viene presentato un nuovo modello region based a contorni attivi che processa informazioni a livello locale attraverso un parametro di scala controllabile tramite un nucleo gaussiano. Per enfatizzare l’innovativa ca-ratteristica di essere scalabile in spazio, il funzionale da minimizzare viene chiamato region-scalable fitting energy. Esso viene incorporato in una for-mulazione variazionale di level set con termine regolarizzante, che ha la funzione di preservare la regolarit`a della funzione di level set ed evitare costose procedure di reinizializzazione.

Questo metodo `e stato scelto come fulcro del presente lavoro, grazie al-le sue buone propriet`a e alla qualit`a della segmentazione risultante. Nel prossimo capitolo si studier`a nel dettaglio un algoritmo per la sua soluzio-ne numerica e, soluzio-nel seguito, si analizzeranno i risultati ottenuti applicando tale algoritmo.

Come visto nel paragrafo precedente, il modello originale di Chan e Ve-se `e limitato dall’uso dei valori mediati c1e c2che non contengono alcuna

informazione locale; quindi nel caso di immagini disomogenee il loro va-lore pu `o essere molto lontano da quello reale. La difficolt`a di segmentare immagini di questo tipo `e evidenziata dalla Figura 1.8 che mette a confron-to un meconfron-todo di thresholding e il modello PC di Chan e Vese: in nessuno dei due casi si riescono a catturare correttamente i contorni delle immagini. Il modello multifase di Chan e Vese, nonostante non presenti pi `u queste limitazioni, `e troppo complesso e costoso.

segmentazio-ne di immagini disomogesegmentazio-nee e il riconoscimento dei contorni poco defini-ti. La novit`a consiste in una serie di convoluzioni locali con una funzione nucleo K :Rn→ [0,+∞)che gode delle seguenti propriet`a:

1. K(−u) =K(u), ∀u∈Rn_; 2. R K(x)dx=1; 3. K(u) ≥K(v) ∀u, v∈_Rn_{t.c.|u| < |v|;} 4. lim |u|→∞K(u) =0.

Si noti che tali propriet`a sono soddisfatte da un nucleo gaussiano con un parametro di scala σ>0: Kσ(u) = 1 (2π)n/2_σne −|u|2_/2σ2 .

Data un’immagine u0:Ω→Rd, sia C un contorno chiuso che separaΩ

in due regioniΩ1=fuori(C)eΩ2 =dentro(C). Per un dato punto x∈ Ω si

definisce l’energia region-scalable fitting: EFit_x (C, f1(x), f2(x)) = 2

∑

dove fi(x) sono dei valori che approssimano l’intensit`a dell’immagine in

Ωi, mentre λ1 e λ2 sono costanti positive che agiscono da pesi per gli

in-tegrali, rispettivamente all’esterno e all’interno delle regioni definite da C. Nella pratica, se si vuole prevenire la nascita di nuovi contorni all’esterno di quello gi`a esistente, conviene fissare λ2 > λ1, penalizzando cos`ı

l’au-mento dell’area della regione interna. Data la natura del nucleo Kσ, i valori

di u0(y)che influenzano maggiormente l’integrale ExFitsono quelli interni

ad una regione R centrata nel punto x: R= {y: |x−y| ≤3σ}. La grandez-za di tale regione pu `o essere controllata modificando il parametro di scala

σdel nucleo gaussiano.

L’energia in (1.17) pu `o anche essere vista come l’errore quadratico medio dell’approssimazione dei valori di intensit`a all’interno e all’esterno di C, in cui ad ogni u0(y)`e assegnato il peso Kσ(x−y). Questa scalabilit`a rispetto

alla regione considerata `e una caratteristica unica e importante di questo metodo.

Per ottenere il contorno intero dell’oggetto bisogna trovare la curva che minimizza l’energia di fitting per tutti i punti nel dominio. Inoltre `e neces-sario aggiungere un termine di penalizzazione proporzionale alla lunghez-za del contorno, come accadeva gi`a nel modello di Chan e Vese. Si ottiene quindi il seguente funzionale dell’energia:

E(C, f1(x), f2(x)) =

Z

ΩE Fit

Per trovare una soluzione al problema di minimizzazione (1.18) e per gestire facilmente i cambi di topologia si introduce, in analogia a quanto gi`a fatto prima, una formulazione di tipo level set. Sia φ la funzione di level set, positiva all’esterno del contorno e negativa all’interno. Il funzionale in (1.17) pu `o essere riscritto come:

EFit_x (φ, f₁(x), f2(x)) = 2

∑

pu `o allora riformulare l’espressione dell’energia in (1.18): E(φ, f₁(x), f2(x)) = Z Ωi E_xFit(φ, f₁(x), f2(x)))dx +ν Z Ω|∇H(φ(x))|dx, (1.20)

dove l’ultimo termine valuta la lunghezza del contorno di livello zero di φ. Anche in questo contesto la funzione di Heaviside si approssima con la funzione regolare definita in (1.14), e le corrispondenti Me

i(φ)vengono

so-stituite alle funzioni Mi(φ)in (1.19), ottenendo cos`ı una forma regolarizzata

dell’energia (1.20) che denotiamo con Ee(φ, f1(x), f2(x)).

Per preservare la regolarit`a della funzione di level set `e necessario in-trodurre un termine di regolarizzazione identificato con:

P (φ) = Z Ω 1 2(|∇φ(x)| −1) 2_{dx. (1.21)}

In questo modo si assicura la stabilit`a nell’evoluzione del contorno e si evita la reinizializzazione di φ, riducendo cos`ı il costo computazionale.

Riassumendo, il funzionale che si vuole minimizzare `e:

F (φ, f1, f2) =Ee(φ, f1(x), f2(x)) +µP (φ).

Innanzitutto bisogna trovare le funzioni fi(x)che minimizzanoF (φ, f1, f2),

fissata φ. Si trova cos`ı: fi(x) =

Kσ(x) ∗ [M_ie(φ(x))u0(x)]

Kσ(x) ∗Me_i(φ(x))

, i=1, 2. (1.22) Tali funzioni sono assimilabili a delle medie pesate dell’intensit`a in un in-torno del punto considerato; la loro regolarit`a `e assicurata dalle buone pro-priet`a della convoluzione e dei nuclei gaussiani.

Ora, fissate f1e f2, si minimizza il funzionale F(φ, f1, f2)rispetto a φ,

risol-vendo l’equazione di flusso:

∂φ ∂t = −δe(λ1e1−λ2e2) +νδediv  ∇φ |∇φ|  +µ  4φ−div  ∇φ |∇φ|  (1.23)

dove δe `e la delta di Dirac regolarizzata definita in (1.14), e le ei sono le funzioni: ei(x) = Z Ωi Kσ(y−x)|u0(x) − fi(y)|2dy, i=1, 2. (1.24)

Il primo termine in (1.23) assume un’importanza fondamentale in quanto attira il contorno verso i confini degli oggetti. Inoltre, visto che δenon `e mai

nulla, esso influenza l’evoluzione della curva in tutto il dominio, rendendo possibile la formazione di nuovi contorni e velocizzando quindi il raggiun-gimento del risultato finale. Pi `u e `e grande, pi `u questo effetto viene amplifi-cato. Il secondo termine invece serve a mantenere limitata la lunghezza del contorno di livello zero, ed allo stesso tempo a lisciarlo. L’ultimo termine `e quello di regolarizzazione, senza il quale la funzione φ potrebbe crescere in maniera incontrollata attorno al contorno di livello zero. Come conse-guenza δe(φ)assumerebbe valori molto piccoli e l’evoluzione del contorno

verrebbe rallentata in maniera inesorabile .

La scelta del parametro di scala σ del nucleo Gaussiano `e fondamentale in quanto influenza la scalabilit`a in spazio, aspetto caratteristico di questo modello. Inoltre incide sulla robustezza del metodo rispetto all’inizializza-zione del contorno. Per σ abbastanza grande l’algoritmo diventa insensi-bile alla scelta di φ0, come lo sono i modelli PC; infatti il metodo di Chan

e Vese pu `o essere considerato come un caso limite di questo approccio per

σ → ∞. Per molte immagini reali, relativamente omogenee, σ ' 10 `e una

buona scelta: lascia una discreta libert`a nell’inizializzazione del contorno e riduce il numero di iterazioni necessarie alla convergenza (seppur aumenti il costo di ogni convoluzione).

I risultati sperimentali confermano le buone propriet`a di segmentazione di questo metodo. In Figura 1.9 `e mostrato il processo di segmentazione per

Figura 1.9: Evoluzione della curva nel processo di segmentazione di alcune immagini. Tratta da [49].

Figura 1.10: Confronto tra il metodo multifase di Chan e Vese (in basso) e il modello RSF (in alto).

due immagine reali con forti disomogeneit`a. In particolare la prima imma-gine di una vena ai raggi X `e stata usata anche in Figura 1.8 per evidenziare i limiti del modello di Chan-Vese. Limiti superati brillantemente dal metodo RSF, che permette di estrarre dei contorni molto precisi. La segmentazione della seconda immagine `e resa complicata dall’illuminazione non unifor-me caratterizzante l’immagine iniziale; nonostante ci `o il contorno finale `e preciso e meglio definito di quello mostrato in Figura 1.5 ottenuto invece con uno schema di tipo active contours.

Un altro confronto significativo effettuato dagli autori in [49] `e ripor-tato in Figura 1.10: si paragonano i risultati ottenuti con lo schema RSF e con il modello multifase di Chan-Vese. Il contorno iniziale `e disegnato in verde e quello finale in rosso. La segmentazione effettuata dai due meto-di `e molto simile: infatti anche il modello multifase `e capace meto-di gestire le disomogeneit`a, pur mancando di accuratezza come si pu `o notare nell’ulti-ma imnell’ulti-magine. Il vantaggio per `o pi `u significativo del metodo RSF `e il suo ridotto costo computazionale, inferiore di pi `u di un ordine di grandezza ri-spetto a quello caratterizzante il metodo di Chan-Vese, come si pu `o vedere nella Tabella 1.1.

Fig.1 Fig.2 Fig.3 Fig.4 Fig.5 Modello RSF 0.84 1.23 8.58 5.78 5.92 Modello CV 30.76 75.51 266.25 142.24 86.07

Tabella 1.1: Confronto dei costi computazionali del modello RSF e del modello di Chan e Vese (CV). Tratta da [49].

Ricerca del minimo

Questo capitolo `e strutturato in tre blocchi: la Sezione 2.1 contiene una bre-ve introduzione teorica al calcolo delle variazioni, al fine di inquadrare for-malmente i problemi di minimizzazione che si stanno analizzando. In se-guito, nella Sezione 2.2, si presenta un algoritmo di minimizzazione molto efficace per la soluzione di problemi convessi. Nella Sezione 2.3 tale algo-ritmo viene applicato ad alcuni dei modelli di segmentazione analizzati nel Capitolo 1, dopo avere sfruttato un’efficiente procedura per trasformare i funzionali concavi in funzionali convessi.

2.1

Introduzione al calcolo delle variazioni

Nel capitolo precedente abbiamo citato risultati del calcolo delle variazioni, senza darne alcuna definizione formale. Per completezza, in questa sezio-ne si colmer`a tale mancanza, introducendo i concetti principali sezio-necessari a comprendere le scelte successive. Per una trattazione pi `u ampia e completa si pu `o consultare [50].

Sia X uno spazio di Banach e F : X→R un funzionale. Per

un’introdu-zione sugli spazi di Banach, sul concetto di funzionale e sulle convergenze ivi definite si pu `o consultare [64]. Si vuole risolvere un generico problema di minimizzazione nello spazio X:

trovare x∗∈ X t.c. F(x∗) = inf

x∈XF(x). (2.1)

Prima di descrivere il risultato principale del calcolo delle variazioni inerente a tale problema, `e necessario introdurre alcune definizioni.

Definizione: Si dice che F `e inferiormente semicontinuo in x0se

F(x0) ≤lim inf n→∞ F(xn)

per ogni successione{xn}convergente a x in X. In particolare, F `e detto

La nozione di semicontinuit`a inferiore varia in relazione al tipo di con-vergenza a cui si fa riferimento: se si usa la concon-vergenza forte (rispet-tivamente debole) in X, si parla di semicontinuit`a inferiore forte (debo-le). La semicontinuit`a inferiore debole implica quella forte, ma non vale il viceversa.

Definizione: Un funzionale F : X→R `e coercivo in X se,∀x ∈R, la chiusura

dell’insieme{F ≤ x}`e sequenzialmente compatta in X, ossia se ogni successione contenuta in tale insieme ammette punto di accumulazione.

Definizione: Una successione{xn} ∈X si dice minimizzante per F in X se

inf

y∈XF(y) =nlim→∞F(xn).

Ogni funzionale F ammette almeno una successione minimizzante.

Siamo ora in grado di enunciare il metodo diretto nel calcolo delle variazioni, introdotto da Tonelli all’inizio del secolo scorso ([70]).

Teorema 2.1

Sia F : X → R un funzionale coercivo e semincontinuo inferiormente.

Allora valgono le seguenti affermazioni: (i) F ha un punto di minimo in X:

∃x∈X t.c. F(x) = inf

y∈XF(y).

(ii) Se{xn} `e una successione minimizzante per F in X per cui vale

lim

n→+∞xn =x, allora x `e un punto di minimo per F in X.

(iii) Se F non `e identicamente +∞, allora ogni sua successione

mini-mizzante ammette una sottosuccessione convergente.

Questo teorema assicura l’esistenza di una soluzione per il problema (2.1), ma non la sua unicit`a. Per avere unicit`a del punto di minimo `e neces-sario introdurre il concetto di convessit`a di un funzionale.

Definizione: Il funzionale F si dice convesso se,∀x, y∈ X, vale F(αx+ (1−α)y) ≤αF(x) + (1−α)F(y), ∀α∈ [0, 1].

Inoltre F si dice strettamente convesso se,∀x, y∈X t.c. x 6=y, vale F(αx+ (1−α)y) <αF(x) + (1−α)F(y), ∀α∈ (0, 1).

Si pu `o ora enunciare il risultato di unicit`a per il problema di minimizzazio-ne (2.1).