Modelli e Metodi Per La Visione Artificiale

Appunti di Modelli e Metodi per la VisioneArtificiale

12 giugno 2011

Indice

1 Introduzione 31.1 Concetti Iniziali . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 I Livelli di Visione . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Acquisizione 62.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Risoluzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 Modello di Colore e Profondit . . . . . . . . . . . . . . . . . . . 8

2.4.1 Immagini Monocromatiche . . . . . . . . . . . . . . . . . 92.5 Telecamere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Elaborazioni di Basso Livello 113.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 Operatori Puntuali . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3.2.1 Look Up Table (LUT) . . . . . . . . . . . . . . . . . . . . 123.2.2 Istogramma dei livelli di grigio . . . . . . . . . . . . . . . 123.2.3 Contrast Stretching . . . . . . . . . . . . . . . . . . . . . 133.2.4 Equalizzazione dellIstogramma . . . . . . . . . . . . . . . 143.2.5 Modificare la luminosit . . . . . . . . . . . . . . . . . . . 153.2.6 Thresholding . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.3 Operatori Locali . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.3.1 Operatori Morfologici . . . . . . . . . . . . . . . . . . . . 16

3.4 Filtraggio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4 Elaborazioni di Medio Livello 374.1 Sogliatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.1.1 Sogliatura con soglia globale . . . . . . . . . . . . . . . . 374.1.2 Evidenziare listogramma . . . . . . . . . . . . . . . . . . 414.1.3 Tecniche alternative di sogliatura . . . . . . . . . . . . . . 41

4.2 Segmentazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.2.1 Definizione Formale . . . . . . . . . . . . . . . . . . . . . 424.2.2 Algoritmi di segmentazione . . . . . . . . . . . . . . . . . 434.2.3 Tecniche basate su discontinuit . . . . . . . . . . . . . . 434.2.4 Tecniche basate sul gradiente . . . . . . . . . . . . . . . . 464.2.5 Tecniche basate sul Laplaciano . . . . . . . . . . . . . . . 54

4.3 Tecniche di Regionalizzazione . . . . . . . . . . . . . . . . . . . . 554.3.1 Labeling di componenti connesse . . . . . . . . . . . . . . 55

1

INDICE 2

4.3.2 Region Growing . . . . . . . . . . . . . . . . . . . . . . . 584.3.3 Region Splitting and Merging . . . . . . . . . . . . . . . . 584.3.4 K-Means . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.3.5 Segmentazione Wathershed . . . . . . . . . . . . . . . . . 60

4.4 Individuazione dei punti di interesse: Feature Points . . . . . . . 614.4.1 Harris Corner Detector . . . . . . . . . . . . . . . . . . . 63

4.5 Scale Invariant Feature Transform (SIFT) . . . . . . . . . . . . . 674.5.1 Il Metodo di Lowe . . . . . . . . . . . . . . . . . . . . . . 68

4.6 Speeded Up Robust Feature (SURF) . . . . . . . . . . . . . . . . 694.6.1 Individuazione dei punti di interesse . . . . . . . . . . . . 704.6.2 Descrizione e matching dei punti di interesse . . . . . . . 75

5 OpenCV 795.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.2 Organizzazione della libreria . . . . . . . . . . . . . . . . . . . . . 795.3 Convenzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805.4 Strutture Dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5.4.1 CvArr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805.4.2 IplImage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815.4.3 CvScalar . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.5 Spazi di colore . . . . . . . . . . . . . . . . . . . . . . . . . . . . 835.6 Accesso ai pixel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

5.6.1 Metodo indiretto . . . . . . . . . . . . . . . . . . . . . . . 845.6.2 Metodo diretto . . . . . . . . . . . . . . . . . . . . . . . . 84

Capitolo 1

Introduzione

1.1 Concetti InizialiPer visione artificiale si intende linsieme dei processi che mirano a costrui-re una descrizione del mondo a partire da immagini, cercando di emulare glieffetti della visione umana attraverso, lacquisizione, lelaborazione e la succes-siva comprensione delle immagini. La visione artificiale un campo altamentemultidisciplinare che comprende competenze di:

image processing

pattern recognition

intelligenza artificiale

neurofisiologia

psicologia

fisica

etc . . .

Un sistema di visione artificiale ostituito dallintegrazione di componentiottiche, elettroniche e meccaniche che permettono di acquisire, registrare edelaborare immagini sia nello spettro della luce visibile che al di fuori di essa(infrarosso, ultravioletto, raggi X, ecc. . . ). Il risultato dellelaborazione ilriconoscimento di determinate caratteristiche dellimmagine per varie finalit dicontrollo, classificazione, selezione, ecc. . .

Lobiettivo di produrre sistemi artificiali che manifestano un comporta-mento visivo con prestazioni paragonabili quelle di un sistema biologico.

Un problema classico nella visione artificiale quello di determinare se lim-magine contiene o no determinati oggetti o attivit. Il problema pu essererisolto efficacemente e senza difficolt per oggetti specifici in situazioni specifi-che per esempio il riconoscimento di specifici oggetti geometrici come poliedri,riconoscimento di volti o caratteri scritti a mano. Le cose si complicano nel casodi oggetti arbitrari in situazioni arbitrarie. Nella letteratura troviamo differentivariet del problema:

3

CAPITOLO 1. INTRODUZIONE 4

Recognition uno o pi oggetti prespecificati o memorizzati possono essere ri-condotti a classi generiche usualmente insieme alla loro posizione 2D o 3Dnella scena.

Identification viene individuata unistanza specifica di una classe. (Es. Iden-tificazione di un volto, impronta digitale o veicolo specifico.)

Detection Limmagine scandita fino allindividuazione di una condizione spe-cifica. (Es. Individuazione di possibili cellule anormali o tessuti nelleimmagini mediche)

Le applicazioni possono toccare svariati campi come:

Industriale (ricerca di difetti, classificazione e scelta, guida di robot, etc. . . ).

Controllo veicoli autonomi.

Video sorveglianza.

Modellazione di oggetti o ambienti.

Medicina.

1.2 I Livelli di Visione

Consideriamo il sistema di visione umano, esso formato da tre livelli di visione:

Visione Retinica consiste in tutta una serie di pre-elaborazioni effettuatedirettamente dallocchio, come la messa a fuoco.

Visione Corticale a questo livello avviene una sorta di estrazione delle infor-mazioni visuali ottenute dellocchio.

Visione Intelligente lultimo di livello si occupa di effettuare delle analisi sul-le informazioni, come il riconoscimento, apprendimento, ragionamento,associazione con modelli precedentemente acquisiti, etc. . .

Allo stesso modo potremmo pensare di strutturare un sistema di visione artifi-ciale in maniera analoga:

Acquisizione come ottenere limmagine, questo problema relativo solo allavisione artificiale, in quanto esiste tutta una serie di problematiche relativea come acquisire in maniera ottimale limmagine.

Basso livello si occupa dellimage processing, cio linsieme delle operazionisvolte sulle immagini a fine di migliorare la qualit e di selezionare leinformazioni utili che verranno elaborate al livello successivo.

CAPITOLO 1. INTRODUZIONE 5

Medio livello si occupa dellimage analysys, cio linsieme dei processi di estra-zione delle informazioni simboliche dalle immagini preelaborate e le tec-niche di analisi delle caratteristiche visuali degli oggetti presenti nellestesse

Alto livello lo scopo di questo livello quello di arrivare ad una forma dicomprensione della scena osservata, come il riconoscimento di oggetti o leloro relazioni spaziali. Spesso, a questo scopo, vengono utilizzate tecnichedi intelligenza artificiale.

Capitolo 2

Acquisizione

2.1 IntroduzioneLo scopo dellacquisizione quello di ottenere limmagine che, a seconda deltipo di strumento usato, pu essere analogica oppure direttamente digitale. Ingenerale, un immagine, un segnale bidimensionale analogico che deve essereopportunamente elaborato per ottenere la rappresentazione digitale, cio comematrice limitata MxN. Ogni elemento nella matrice rappresenta una quantitcampionata e quantizzata del valore misurato dal sensore e viene detto pixel(picture element).

La conversione dal segnale analogico a quello digitale avviene secondi trepassi:

1. Campionamento Spaziale: questo ha lo scopo di trasformare delle funzionicontinue in un insieme di valori detti campioni dellimmagine, se il processoviene effettuato rispettando il vincoli imposti dal Teorema di Shannon nonsi verificano fenomeni che possono provocare la perdita delle informazioni.

2. Quantizzazione: ogni campione ottenuto dallimmagine ha una profondi-t di colore che continua. Tramite la quantizzazione rappresentiamo i

6

CAPITOLO 2. ACQUISIZIONE 7

singoli campioni con un numero finito di livelli Q. Dobbiamo ricordare chequesta operazione comporta un errore che proporzionale a Q.

3. Codifica: dopo aver effettuato la quantizzazione, per poter memorizzarelimmagine su un calcolatore necessario codificare i livelli Q assegnati aivari campioni dellimmagine.

2.2 Aliasing

Laliasing un problema derivante sia da operazioni di sottocampionamento(quando la frequenza di campionamento inferiore a quella consigliata dallaShannon), sia da operazioni di ricampionamento (quando si campiona un segnalegi campionato). Per ridurre gli effetti dellaliasing si pu ricorrere ad un filtropassa-basso, cio ridiciamo, prima di campionare, la massima frequenza presentenellimmagine. Questa operazione risulta necessaria quando la frequenza dicampionamento necessaria troppo elevata, e quindi per evitare laliasing siriduce la frequenza massima dellimmagine. Per evitare di dover usare un filtropassa-basso digitale si pu agire anche direttamente sul sistema di acquisizione.

2.3 RisoluzioneQuando parliamo di risoluzione spaziale dellimmagine intendiamo il numero dicampionamenti del piano immagine, e solitamente viene espressa in termini didimensione della matrice MxN ottenuta dopo il campionamento. La risoluzionepu essere espressa anche in termini di densit di pixel che formano limmagine


(dpi). Pi in generale essa dipende direttamente dallapplicazione e dal sistemadi acquisizione, ad esempio:

Riconoscimento caratteri : 64x64

Immagini biomediche: da 512x512

Immagini satellitari : da 4096x4096

Ovviamente una stessa immagine pu essere rappresentata con un nume-ro differente di pixel, ma bene ricordare che se il questo numero troppobasso la risoluzione spaziale pu risultare scadente e presentare delle disconti-nuit nellimmagine. Con laumentare della densit di pixel limmagine presentasempre meno discontinuit fino a dare limpressione di essere continua (quandola dimensione dei pixel diventa pi piccola della risoluzione spaziale del siste-ma visivo umano). In generale non possibile definire a priori il numero dipixel necessari a garantire una buona qualit dellimmagine, ma sicuramentela dimensione dei pixel deve essere piccola in relazione alla scala degli oggettirappresentati nellimmagine. Il fatto che la qualit sia buona o meno dipendefortemente dallapplicazione.

2.4 Modello di Colore e ProfonditUn modello di colore un modello matematico astratto che permette di rappre-sentare i colori in forma numerica, tipicamente utilizzando tre o quattro valorio componenti cromatiche. Un modello di colore si serve cio di unapplicazio-ne che associa ad un vettore numerico un elemento in uno spazio dei colori. Imodelli di colore pi diffusi sono:

RGB (Red, Green, Blue): modello di colori di tipo additivo, unendo itre colori con la loro intensit massima si ottiene il bianco.

CMYK (Cyan, Magenta, Yellow, Key black): modello di colori di tiposottrattivo, i colori ottenibili con la quadricromia sono un sottoinsiemedella gamma visibile, quindi non tutti i colori che vediamo possono essererealizzati con la quadricromia, cos come non tutti i colori realizzati conlinsieme RGB hanno un corrispondente nellinsieme CMYK. Il 100% ditutte e tre le componenti (CMYK 100,100,100,0) non genera solitamenteil nero, bens il bistro, colore simile a una tonalit di marrone molto scura.

La profondit di colore (color depth) la quantit di bit necessari per rap-presentare il colore di un singolo pixel in unimmagine bitmap, questa si misurain bit per pixel (bpp) ed il valore memorizzato per ciascun bit generalmenteun indice in una mappa di colori o tavolozza:

1 bpp (21 = 2 colori)

2 bpp (22 = 4 colori)

8 bpp (28 = 256 colori)


Con laumentare del numero di bit per pixel aumenta anche la quantit di coloripossibili, rendendo sempre pi scomodo luso delle tavolozze. Per le profonditpi alte si preferisce perci codificare i colori direttamente nei valori corrispon-denti alla luminosit relativa dei canali rosso, verde e blu secondo il modelloRGB (oppure seguendo altri modelli di colore).

2.4.1 Immagini MonocromaticheIl valore dei pixel rappresentato con valori interi (k bit) che indicano il livellodella quantit misurata, adeguatamente campionata e quantizzata. Solitamentesi indica con risoluzione a livelli di grigio il numero di livelli distinguibili anchese la quantit misurata non luminosa.

2.5 TelecamereLe immagini posso derivare dalla digitalizzazione di segnali provenienti da di-versi sensori. Uno dei sensori pi diffusi sono le telecamere che possono essereclassificate in due categorie principali:

Analogiche generano un segnale analogico che fornisce informazioni sullim-magine riga per riga. I segnali devono essere successivamente campionatie quantizzati.

Digitali generano un segnale digitale.

Tra le telecamere digitali sono largamente diffuse quelle basate su sensoriallo stato solido CCD (Charge-Coupled Device) che forniscono una immaginegi campionata spazialmente (e temporalmente) a causa del numero finito difotorecettori. Unalternativa nascente sono invece le telecamere basate su sen-sori CMOS (Complementary Metal-Oxide Semiconductor) che permettono disuperare alcuni problemi legati ai sensori CCD come linterlacciamento ed ilconsumo, ma la qualit non ancora comparabile ai primi. Generalmente il se-gnale video delle telecamere CCD interlacciato, cio vengono trasmesse prima


le linee dispari e poi quelle pari, questo permette di ridurre il fenomeno del flic-kering (disturbo elettrico percepito come uno sfarfallio). Mentre il numero N dirighe fissato dallo standard il numero di righe M dipende dal campionamentodel frame grabber (strumento che trasforma il segnale video analogico prodottoda una telecamera in un segnale digitale). Esistono tre tipi di standard:

NTSC (National Television Standard Committee)

SECAM (Squentiel Couleur Mmoire - colore sequenziale con memo-ria)

PAL (Phase Alternating Line).

NTSC SECAM PAL

Immagini al secondo 30 (29.97) 25ms per immagine 33.37 40 40linee per immagine 525 625 625aspect ratio h:v 4:3 4:3 4:3

CCD CMOS

alta qualit minore qualitbasso rumore alto rumoremolto sensibili ridotta sensibilitalto consumo basso consumo

tecnologia matura tecnologia innovativaelevato numero di pixel numero di pixel ridotto

Un altro aspetto fondamentale da considerare durante la fase di acquisizione il rumore, questo pu essere determinato da vari fattori:

Sensori: tipicamente modellato come rumore bianco o gaussiano.

Trasmissione.

Quantizzazione.

Impulsivo (sale e pepe).

Capitolo 3

Elaborazioni di Basso Livello

3.1 IntroduzioneLelaborazione di basso livello ha lo scopo di migliorare la qualit dellimmagineottenuta dalla fase acquisizione (es. eliminazione del rumore, compressione,etc. . . ) e di effettuare una serie di operazione al fine di facilitare lelaborazionedi medio livello.

. . ....

......

......

... . . . 172 172 173 169 170 168 . . .. . . 172 172 173 169 170 168 . . .. . . 165 165 170 170 169 168 . . .. . . 159 160 150 150 170 159 . . .. . . 160 160 150 150 170 158 . . .. . . 160 158 150 150 170 159 . . .

...

......

......

.... . .

A questo livello limmagine rappresentata come una matrice di pixel su cui

possibile applicare degli operatori, che posso essere di tre tipi:

Operatori Puntuali ogni pixel dellimmagine duscita funzione solo del cor-rispondente pixel nellimmagine di ingresso. Questi operatori non altera-no le relazioni spaziali tra i punti dellimmagine. (Variazioni dei livelli digrigio, look up table, operazioni di soglia).

Operatori Locali ogni pixel dellimmagine duscita funzione del corrispon-dente pixel nellimmagine di ingresso e di un suo intorno locale (dettokernel). In questa classe ricadono i filtraggi e gli operatori morfologici.

Operatori Globali ogni pixel dellimmagine duscita funzione di tutti i pixeldellimmagine di ingresso. (Trasformazioni varie).

11

CAPITOLO 3. ELABORAZIONI DI BASSO LIVELLO 12

3.2 Operatori Puntuali

3.2.1 Look Up Table (LUT)Nelle LUT ogni colore o livello di grigio memorizzato in una tabella insieme conil colore o il livello di grigio corrispondente. Gli operatori puntuali possono essererealizzati mediante look-up table (LUT). Tipicamente le schede di acquisizionemettono a disposizione delle LUT personalizzabili dallutente che consentono larealizzazione in hardware di operatori puntuali.

3.2.2 Istogramma dei livelli di grigioListogramma dei livelli di grigio di unimmagine una funzione che associaa ciascun livello il numero di pixel dellimmagine aventi quel livello di gri-gio. Listogramma misura quindi la frequenza di occorrenza dei livelli di grigiodellimmagine.

i n t h i s t o [ 2 5 6 ] ;. . .

f o r ( i n t i = 0 ; i < N; i++){f o r ( i n t j = 0 ; j < M; j++){

k = Image [ i ] [ j ] ;h i s t o [ k ] = h i s t o [ k ]+1;

}}

Il calcolo dellistogramma viene effettuato definendo un vettore di dimen-sione pari al numero dei livelli di grigio dellimmagine. Ciascun elemento delvettore rappresenta il contatore dei pixel aventi livello di grigio uguale allindicedellelemento. Quindi si scandisce limmagine e si incrementa lelemento delvettore avente indice pari al livello di grigio del pixel corrente.


3.2.3 Contrast StretchingQuesto operatore viene utilizzato per migliorare la qualit di immagini carat-terizzate da debole contrasto. Loperatore migliora il contrasto dellimmagineespandendo la dinamica dei livelli di grigio su un intervallo pi ampio.

Detti Gmin e Gmax i livelli di grigio minimo e massimo dellimmagine inizia-le, viene utilizzata una funzione di mapping lineare per espandere la dinamicanellintervallo desiderato [Gmin, Gmax]:

Pout = (Pin Gmin) Gmax GminGmax Gmin

+Gmin

Tipicamente la dinamica viene espansa su tutto lintervallo disponibile [0,255]:

Pout = (Pin Gmin) 255

Gmax GminLa funzione di mapping precedentemente definita poco robusta rispetto

alla eventuale presenza di pixel fuori range (livello di grigio molto basso o moltoalto). Difatti lintervallo [Gmin, Gmax] risulter pi esteso di quanto effettiva-mente necessario, riducendo leffetto di miglioramento del contrasto. In questicasi di preferisce determinare Gmin e Gmax selezionando degli opportuni va-lori percentuali sullistogramma dei livelli di grigio (ad esempio 5% e 95%).Se loperazione deve essere effettuata in tempo reale mediante look-up table suuna sequenza di immagini, Gmin e Gmax non possono essere ricalcolati per ogniimmagine. Di conseguenza, una volta determinati Gmin e Gmax a partire da uninsieme rappresentativo di immagini, i valori dellimmagine corrente fuori dalrange vengono trasformati negli estremi dellintervallo:


Pout =

Gmin se Pin < Gmin(Pin Gmin) G

maxG

min

GmaxGmin +Gmin se Gmin < Pin < Gmax

Gmax se Pin > Gmax

3.2.4 Equalizzazione dellIstogrammaLobiettivo delloperazione di equalizzazione dellistogramma quello di ottene-re unimmagine risultato avente un istogramma uniforme (piatto). Questacaratteristica generalmente implica unespansione della dinamica dei livelli digrigio e quindi un incremento del contrasto, in pratica aumenta i contrasti vici-no ai massimo e li diminuisce vicino ai minimi. La procedura di equalizzazioneconsidera listogramma come un distribuzione di probabilit dei livelli di grigioed esegue i seguenti passi:

1. Calcolo dellistogramma cumulativo

2. Si dividono i valori ottenuti al passo 1 con il numero di pixel

3. Si moltiplicano i valori ottenuti al passo 2 per il massimo livello di grigio

4. Si mappano i livelli di grigio originali sui valori ottenuti al passo 3 con unacorrispondenza 1 a 1.

In realt una distribuzione perfettamente uniforme dei livelli di grigio non puessere ottenuta a causa della natura discreta delle grandezze trattate. Bisognafare attenzione perch quando il contrasto originale dellimmagine molto bassopu provocare effetti di sgranatura o comparsa di false regioni.

In generale lapparenza dellimmagine pu essere migliorata anche con altretecniche di modifica del contrasto, ma lequalizzazione ha il vantaggio di esseredel tutto automatica.


3.2.5 Modificare la luminosit

Variare la luminosit significa spostare listogramma verso il massimo o versoil minimo, questo pu provocare effetti di saturazione verso gli estremi. Pos-siamo notare la variazione: la prima immagine sulla sinistra quella originale,mentre laltra leffetto di un aumento del 10%.

3.2.6 ThresholdingLoperazione di soglia serve a binarizzare unimmagine, cio a passare da unarappresentazioni in livelli di grigio ad una rappresentazione in bianco e nero. Inparticolare loperazione consiste nello scegliere un livello di soglia e tutti i pixelche si trovano al di sotto della soglia vengono impostati a 0, mentre tutti quellimaggiori o uguali ad 1 (o meglio al livello massimo che pu essere anche 255).


Ibinaria(x) =

{0 se Ioriginale(x) < soglia1 se Ioriginale(x) > soglia

Il parametro chiave in una sogliatura la scelta del valore di soglia. Esistonodiverse metodologie per la scelta automatica di questo valore, oppure possibi-le sceglierlo a mano. Un semplice metodo potrebbe essere quello di scegliere ilvalore medio o la mediana come valore di soglia. Questa logica pu funzionarebene in unimmagine senza alcun tipo di rumore, altrimenti si debbono utiliz-zare tecniche pi sofisticate, come ad esempio quello di creare un istogramma eosservare dove vi il punto pi basso in mezzo allistogramma; quindi si scegliequel valore come soglia. Ma questo potrebbe non funzionare in immagini pirumorose, dove forse vale la pena di utilizzare un K-means binario (algoritmo diclustering). Anche le immagini a colori possono venire sogliate, e si parla in que-sto caso di sogliatura multibanda. Un semplice approccio potrebbe essere quellodi scomporre limmagine nei suoi tre canali RGB e sogliarli tutti indipenden-temente. Le tre immagini binarie sono poi processate attraverso unoperazionelogica di and.

3.3 Operatori Locali

3.3.1 Operatori MorfologiciLa morfologia studia la forma delle piante e degli animali. Nellimage processingper processing morfologico si intende lo studio della forma e della struttura deglioggetti dalle loro immagini. Gli operatori morfologici si basano su due operazionidi base dette erosione e dilatazione di seguito definite:

Erosione Lerosione di A con lelemento strutturante (kernel) B dato informule da:

AB ={z|Bz A

}


In parole, si ha che nel traslare lelemento strutturante B su A se B tuttocompreso in A ossia se lAND logico fra B ed A pari ad 1 allora il pixelrisultante a cui associata loperazione sar nellerosione A B. Nellapratica, supponendo che lelemento strutturante sia una matrice 3x3, incui il foreground dato dai pixel con valore 1, mentre quelli con valore 0sono il background. Indichiamo con origine dellelemento strutturante ilcentro dellelemento. 1 1 11 1 1

1 1 1

Coordinate dei punti:

(1,1), (0,1), (1,1)(1, 0), (0, 0), (1, 0)(1, 1), (0, 1), (1, 1)

Come prima cosa sovrapponiamo lorigine dellelemento strutturante conil pixel di interesse nellimmagine di input, se tutti i pixel del foregroundsi sovrappongono a pixel presente nellintorno del pixel analizzato alloralasciamo questultimo invariato, altrimenti se troviamo almeno un pixelnellintorno che non sovrapposto con il foreground allora il valore delpixel di interesse viene impostato uguale a quello del background (nelnostro caso a 0).

Lerosione pu essere effettuata anche su immagini a livelli di grigio, in que-sto caso la funzione si erosione si complica in quanto dobbiamo considerarediversi livelli:

(fb)(s, t) = min{f(s+x, t+y)b(x, y)|(s+x), (ty) Df ;x, y Db

}Dove Df e Db sono rispettivamente il dominio di f ed il dominio di b,bisogna ricordare che lelemento strutturante deve essere completamentecontenuto nellinsieme da erodere. Possiamo estendere la definizione aduna funzione di una variabile ottenendo:

(f b)(s) = min{f(s+ x) b(x)|(s+ x) Df ;x Db

}


In parole, lerosione di una immagine in livelli di grigio non molto dif-ferente da quella di una immagine binaria, lunica differenza che vieneespressa in termini di funzione di due variabili. Lelemento strutturanterimane una matrice in cui sono contenuti, non pi solo valori binari, mapossono essere valori presenti nel range di valori dellimmagine di partenza.Sovrapponendo il centro dellelemento strutturante sul pixel di interesseotterremo un insieme di valori per la funzione (fb) dai pixel che si trovanonellintorno del pixel di interesse, di questi valori ottenuti prendiamo ilminimo e lo impostiamo come valore del pixel di input.

Dilatazione La dilatazione di A con lelemento strutturante B dato in formuleda:

AB ={z|Bz A 6= 0

}In parole, si ha che passando il kernel B su A se essi si toccano anche diun solo elemento non nullo allora il risultato sar pari ad 1.1 1 11 1 1

1 1 1

Consideriamo sempre il kernel precedente, possiamo notare gli effetti delladilatazione si un immagine binaria:

Analogamente al caso della erosione, possiamo applicare la dilatazione aduna immagine a livelli di grigio tramite la seguente funzione:

(fb)(s, t) = max{f(sx, ty)b(x, y)|(sx), (ty) Df ;x, y Db

}Che nel caso di una funzione ad una sola variabile si traduce in:

(f b)(s) = max{f(s x) b(x)|(s x) Df ;x Db

}Anche in questo caso la funzione (f b) viene calcolata per ogni pixelsottoposto al kernel, ma, a differenza dellerosione, viene associato al pixeldi interesse il valore massimo tra quelli ottenuti. Se tutti i valori dellele-mento strutturante sono positivi limmagine risultante sar pi luminosadi quella di partenza.


Apertura questa operazione una cascata di erosione e poi dilatazione. Quindiin formule si ha:

A B (AB)B

Il senso che prima erodo per eliminare gli oggetti grandi come lelementoB e poi dilato per ripristinare la forma degli oggetti restanti. possi-bile notare come si siano separati due oggetti che si erano erroneamenteattaccati senza alterare la forma degli oggetti stessi.

Lerosione, solitamente, permette di eliminare il rumore (salt noise) dibackground che pu presentarsi, ma ha il grosso svantaggio di agire suqualsiasi regione di pixel indiscriminatamente, quindi elimina informazionisullimmagine. Con lapertura possiamo, sommando gli effetti dei dueoperatorio precedenti, in modo da ottenere un effetto meno distruttivo(come possiamo notare dallesempio sopra).

Un altro esempio di uso delloperatore di apertura il seguente, nel qualevogliamo estrarre solo i cerchi ed eliminare gli altri elementi considerandolicome un disturbo:

Questa operazione pu essere effettuata con lapplicazione di un elementostrutturante che ripropone la figura che si vuole individuare: Solitamentenon di applica una sola volta, ma pu essere applicato in maniera itera-tiva pi volte fino ad ottenere leffetto desiderato (Nellesempio abbiamoapplicato 5 volte il kernel).


Chiusura una cascata di dilatazione e poi erosione. Quindi in formule si ha:

A B (AB)B

Il senso che prima dilato per riempire eventuali gap con lelemento B epoi erodo per ripristinare la forma degli oggetti restanti.

Un esempio di utilizzo delloperatore di chiusura (con kernel 3x3 pieno)pu essere, ad esempio, quello di isolare soltanto i cerchi grandi eliminandoquelli piccoli e il cerchio nero allinterno.


Mentre loperazione di apertura efficace con il salt noise, quello di chiu-sura efficace per il peppe noise.

Hit and Miss Transform (pattern matching e marking) questo operatore vie-ne utilizzato per ritrovare i pixel centrali degli oggetti che somigliano alle-lemento strutturante. A differenza degli operatori precedenti la somiglian-za deve essere sia sugli elementi di foreground che su quelli di background,in oltre si possono inserire anche delle zone di dont care cio in cui ipixel possono assumere qualsiasi valore. Ad esempio se volgiamo cercareesattamente gli angoli bassi possiamo usare questo kernel:

(A B) 1 0 1 10 0

In alternativa possono essere utilizzati pi kernel in OR, in modo da trova-re tutti gli elementi che corrispondono ad angoli nella figura. Ad esempiousando in OR i seguenti kernel:


Possiamo ottenere questo risultato:

Solitamente, questo tipo di operatore viene utilizzato per cercare e/o con-tare le occorrenze di un particolare pattern allinterno dellimmagine.

Thinning questa fa parte delle operazioni che si basano sul pattern matching,cio sulla corrispondenza tra lelemento strutturante e lintorno del pixeldi interesse, per cui il valore di questultimo viene assunto in base allesitodel matching con il kernel scelto (per essere ritenuto positivo il matchingdeve essere esatto). Possiamo dire quindi che lesito di questo genere dioperazioni strettamente legato alla scelta del kernel che si utilizza per ilmatching, infatti kernel diversi possono portare a risulti differenti. Lo-perazione ha come effetto lo sfinamento degli oggetti, e viene definita nelseguente modo:

AB A (A B)

Cio, fa lhit-and-miss con lelemento strutturante B, poi sottrae il ri-sultato allimmagine originale A. La sottrazione intesa in senso logico,cio:

X Y = XqY

In altre parole, quello che accade che quando viene sovrapposto il centrodel elemento strutturante sul pixel di interesse, se il suo intorno esat-tamente uguale allelemento strutturante allora il valore del pixel vieneposto uguale a quello di background (zero nel nostro caso), altrimenti vie-ne lasciato inalterato. Loperazione solitamente ripetuta pi volte finoa quando non avvengono pi cambiamenti allimmagine. Luso pi co-mune di questa operazione quello di ridurre limmagine ottenuta dallasogliatura, per essere analizzata tramite algoritmi di edge detection comeloperatore di Sobel, in quanto assottiglia le linee spesse pi pixel a lineedi singoli pixel.


Thickening possiamo definire questa operazione come la duale del thinning,infatti mentre nel caso precedente era una erosione basata su pattern mat-ching, in questo caso una dilatazione basta sullo stesso principio. Inpratica se il matching risulta positivo il pixel di interesse assume il valoredel foreground (cio uno, nel nostro caso). Loperazione cos definita:

AB A (A B)

Anche in questo caso determinante la scelta dellelemento strutturanteper il risultato che si vuole ottenere.

Due applicazioni comuni di questo operatore sono:

1. Determinare linvolucro convesso (convex hull): linvolucro convessodi una immagine si pu ottenere immaginando di stendere una ban-da elastica intorno ad essa. Questa banda elastica seguir i contorniconvessi della sagoma far da ponte sui contorni concavi. La sago-ma risultante non avr pi concavit e conterr la sagoma iniziale.Se sono presenti pi sagome lalgoritmo determiner linvolucro con-vesso di ognuna di esse. Usando i seguenti elementi strutturali conloperatore di thickening possiamo ottenere linvolucro convesso:1 1 1 0

1 0

1 1 0 10 1

Iterando 100 volte loperatore otteniamo:


2. Ricerca dello SKIZ (Skeleton by zone of influence): questa unastruttura scheletrica che divide limmagine in regioni, ognuna dellequali contiene solo un elemento distinto presente nellimmagine. Que-sto ancora conosciuto come diagramma di Varonoi. Un metodo percalcolarlo quello di determinare prima lo scheletro del backgrounde poi effettuare delle operazioni di pruning fino a rimuovere tutti irami che non creano delle forme chiuse. Tale operazione pu esse-re effettuata sia tramite il thinning che tramite il thickening (poich il suo duale) la scelta delloperatore dipende dalla polarit del-limmagine, cio se nero (foreground) su bianco (background) oviceversa.

Skeletonization/Medial Axis Trasform il processo di riduzione delle zo-ne di foreground di una immagine binaria in un residuo scheletrico chemantenga lestensione e la connessione delle zone originarie fino allelimi-nazione della maggior parte dei pixel di foreground. Per capire come fun-ziona, immaginiamo che le regioni di foreground nellimmagine di inputsiano fatte di un materiale infiammabile lentamente. Se facciamo bru-ciare contemporaneamente tutti i punti che si trovano sulla frontiera dellaregione vedremo il fuoco muoversi sempre verso linterno. Il fuoco si estin-gue nei punti in cui si toccano fiamme provenienti da direzioni differenti,unendo tutti questi punti otteniamo la linea di spegnimento (quench line),questa linea lo scheletro. Possiamo comprendere quindi, come lopera-zione di thinning (e dualmente quella di thickening) producano una sortadi scheletro. Un altro modo per immaginare lo scheletro di una regione quello di pensarlo come il luogo dei centri delle circonferenze bi-tangentiinscritte completamente allinterno della regione di foreground che stiamoconsiderando.


Mentre si parla di scheletro quando il risultato delloperazione un im-magine in bianco e nero, parliamo invece di Medial Axis Trasform (MAT)quando il risultato delloperazione unimmagine a livelli di grigio in cuilintensit di ogni punto dello scheletro rappresenta la distanza tra questoe la frontiera della regione originale.

3.4 FiltraggioUn altro gruppo di operazioni locali rappresentata dai filtri, il cui scopo quello di migliorare la qualit dellimmagine. Normalmente le operazioni di fil-traggio dei segnali avvengono tramite loperazione di convoluzione, nel caso delleimmagini digitali utilizziamo la convoluzione discreta. Per cui loperazione daeffettuare si traduce in una doppia somma tra due matrici, una rappresentantelimmagine I(i, j) e laltra rappresentate la risposta impulsiva del filtro H.

I11 I12 I13 I14 I15 I16 I17 I18 I19I21 I22 I23 I24 I25 I26 I27 I28 I29I31 I32 I33 I34 I35 I36 I37 I38 I39I41 I42 I43 I44 I45 I46 I47 I48 I49I51 I52 I53 I54 I55 I56 I57 I58 I59I61 I62 I63 I64 I56 I66 I67 I68 I69

[K11 K12 K13K21 K22 K23

]O57 = I57K11 + I58K12 + I59K13 + I67K21 + I68K22 + I69K23

O(i, j) km=k

kn=kH(m,n) I(im, j n)

Filtro di Media : un metodo molto semplice e rapido per realizzare uno-perazione di smoothing dellimmagine. Lidea alla base del filtro consistenel sostituire ad ogni pixel il valor medio dei suoi vicini (incluso il pixelstesso). Questa operazione corrisponde ad un filtraggio di tipo passa bassoche attenua le armoniche a frequenza pi elevata. Il filtro di media un


operatore lineare spazialmente invariante e pu essere descritto tramiteun kernel che rappresenta la risposta impulsiva del filtro. Tipicamentesi usano filtri basati su kernel 3x3 o 5x5. Filtraggi pi pesanti vengonorealizzati iterando loperatore elementare.

19

19

19

19

19

19

19

19

19

Dal punto di vista computazionale conviene calcolare il valor medio in ognipunto piuttosto che eseguire la convoluzione con il kernel del filtro. Inoltre, possibile implementare in modo ricorsivo il calcolo del valor medio al finedi ridurre ulteriormente il carico computazionale.

Limmagine 3.1 rappresenta una versione degradata dal rumore gaussiano.Proviamo quindi a vedere che effetto avrebbe un filtro di media: Lim-magine immagine 3.2 mostra il risultato dellapplicazione di un filtro dimedia con kernel 3x3: il rumore stato ridotto ma limmagine appare lie-vemente pi sfocata, i dettagli pi fini risultano meno evidenti. Leffettodello smoothing ancor pi evidente nella figura 3.4, che rappresenta ilrisultato ottenuto mediante un filtro di media 5x5.

Possiamo concludere dicendo che il filtro di media, essendo di tipo passa-basso, attenua le armoniche a frequenza elevata mentre lascia sostan-zialmente invariate quelle a bassa frequenza. Lattenuazione delle fre-quenze elevate causa un effetto di smussamento dei bordi delle regionidellimmagine.

Filtro Mediano Lidea alla base del filtro consiste nel sostituire ad ogni pixelil valore mediano dei suoi vicini (incluso il pixel stesso). Il valore mediano calcolato ordinando tutti i pixel dellintorno prescelto e sostituendo alpixel in esame il valore centrale dellinsieme ordinato (se lintorno contieneun numero pari di pixel si prende la media dei due valori centrali).

A differenza del filtro gaussiano e di quello di media questo un filtro nonlineare, infatti:

median[A(X) +B(X)] 6= medial[A(X)] +median[A(X)]

. . ....

......

. . .. . . 124 126 127 . . .. . . 120 150 125 . . .. . . 115 119 123 . . .. . .

......

.... . .

Lapplicazione principale del filtro mediano leliminazione del rumoreimpulsivo. Difatti il valore mediano molto pi robusto rispetto alla pre-senza di pixel corrotti della semplice media. Se il valore di un pixel significativamente diverso da quello dei vicini esso viene eliminato sen-za influenzare i pixel vicini. In oltre, limmagine filtrata mantiene dei


Figura 3.1: Degradazione dellimmagine con rumore gaussiano

Figura 3.2: Effetto del filtro di media con kernel 3x3 sullimmagine degradata

Figura 3.3: Immagine degradata con rumore impulsivo


Figura 3.4: Applicazione di un filtro con kernel 3x3 a sinistra e 5x5 a destra

Figura 3.5: Degradazione dellimmagine sopra ed applicazione del filtro media-no, 1 passo per limmagine in basso a sinistra, 2 passi per quella in basso adestra


contorni pi netti rispetto alluso di un filtro di media o di un filtro gaus-siano di pari dimensioni. Dallimmagine 3.5 notiamo come il filtro 3x3consenta di eliminare il rumore impulsivo senza produrre uno sfocamentodellimmagine.

Filtro Gaussiano Un filtro che trova larghissimo impiego nello smoothing diimmagini il filtro che ha come risposta impulsiva una funzione guassianabidimensionale di valor medio nullo e deviazione standard .

Figura 3.6: Nella a sinistra immagine notiamo il gaussiano in 2D, mentre inquella a destra in 3D

Nel caso monodimensionale la densit di probabilit gaussiana definitacome:

G(x) = 12e

x2

22

La figura mostra landamento della gaussiana monodimensionale con =1, ricordiamo che poich la funzione rappresenta una densit di probabilitlarea sottesa unitaria. La gaussiana bidimensionale ottenibile comeprodotto di due gaussiane monodimensionali orientate secondo gli assicoordinati.

G(x, y) = G(x)G(y) = 122 e x

2+y2

22

Il comportamento del filtro gaussiano determinato dal valore del para-metro : quanto pi elevato tanto maggiore leffetto di smoothing.Questa propriet pu essere compresa osservando che allaumentare di diminuiscono i pesi dei pixel pi vicini ed aumentano quelli dei pixel pilontani. Il kernel del filtro gaussiano discreto viene costruito campionan-do la risposta impulsiva del corrispondente filtro continuo. Poich il filtrocontinuo ha risposta impulsiva infinita, necessario stabilire la dimensionedel kernel tenendo presente che:

lapprossimazione discreta del filtro continuo tanto migliore quantopi il kernel ampio;

il costo computazionale delloperazione di filtraggio cresce significa-tivamente allaumentare delle dimensioni del kernel;


la risposta impulsiva del filtro continuo descresce man mano che ci siallontana dallorigine;

Inoltre, poich lestensione della gaussiana dipende da , il kernel dovressere dimensionato sulla base di tali parametro. Per una gaussiana stret-ta ( piccola) possibile usare un kernel piccolo, ma se la gaussiana siallarga ( cresce) necessario utilizzare un kernel pi largo. utile quin-di disporre di una regola che consenta di determinare la dimensione delkernel in funzione di .

Analizzando il valore dellarea sottesa dalla gaussiana 1D nellintervallo|x| n per n = 1, 2, 3 :

|x| 0.68 |x| 2 0.95 |x| 3 0.99

si deduce che scegliendo un kernel (2k+1)x(2k+1) con k = 3 si ottieneunapprossimazione molto buona della gaussiana continua. Quindi:

= 1 7x7 = 1, 5 11x11 = 2 13x13 = 3 19x19

Tipicamente al fine di ridurre il tempo di calcolo si preferisce eseguirela convoluzione con un kernel a coefficienti interi. Un kernel intero puessere ottenuto da un kernel a coefficienti reali dividendo per il coeffi-ciente reale pi piccolo (che quindi viene reso pari ad 1), arrontondandoil risultato e dividendo poi per la somma dei coefficienti ottenuti dopolarrotondamento:

k k1 = 1kmin k2 = round(k1) k2 =1

sum(k)2k2

Analogamente possiamo fare per filtro bidimensionale con = 1.

1256

1 4 7 4 14 16 26 16 47 26 41 26 74 16 26 16 41 4 7 4 1


Abbiamo visto che limplementazione del filtro gaussiano pu richiederela convoluzione con un kernel di dimensioni notevoli (gi con = 2 ilkernel 13x13). per possibile ridurre significativamente il costo com-putazionale sfruttando la propriet di separabilit del filtro gaussiano checonsente di effettuare la convoluzione 2D eseguendo una convoluzione 1Dnella direzione x (o y) seguita da una convoluzione 1D nella direzione y (ox). Con questo approccio il numero di operazioni elementari (prodotto +somma) per pixel passa da (2k + 1)2 a 2(2k + 1).

Figura 3.7: Esempio di applicazione del filtro gaussiano, a sinistra limmagineoriginale a destra quella filtrata con = 1

Lapaciano del Gaussiano In matematica, loperatore di Laplace o laplacia-no un operatore differenziale del secondo ordine. Loperatore di Laplacepu operare da due fino ad n dimensioni e pu essere applicato sia a campiscalari, che vettoriali. In coordinate cartesiane definito come la sommadelle derivate parziali seconde non miste rispetto alle coordinate. Que-sto operatore viene utilizzato spesso per la edge detection, e generalmenteviene applicato dopo una operazione di gaussian smoothing in modo daevitare che il rumore presente sullimmagine condizione lesito dellopera-zione (riduzione delle sensibilit al rumore). Solitamente questo operatoreprende in ingresso un immagine a livelli di grigio e restituisce, come output,unaltra immagine a livelli di grigio in cui sono evidenziati i contorni.Possiamo quindi definire il laplaciano L(x, y) di un immagine con valoredi insensit dei pixel I(x, y) come:

L(x, y) = 2Ix2 +

2Iy2

solitamente viene calcolato con un filtro di convoluzione, in maniera ana-loga a quanto fatto con i filtri precedenti. Esistono diversi kernel utilizzatiper approssimare le derivate seconde dellimmagine, i pi utilizzati sono iseguenti:

CAPITOLO 3. ELABORAZIONI DI BASSO LIVELLO 32 0 1 01 4 10 1 0

1 1 11 8 11 1 1

Dato che il calcolo delle derivata seconda avviene tramite luso di un filtroche ne approssima il valore, questa operazione anche molto sensibile alrumore, per cui dobbiamo prima applicare un filtro gaussiano per eliminarele componenti in alta frequenza del rumore. Ma, dato che la convoluzio-ne gode della associativit, possiamo prima effettuare una convoluzionetra il filtro gaussiano e quello di Laplace, e poi convolvere il risultato conlimmagine in modo da precalcolare il filtro ed effettuare una sola convolu-zione sullimmagine (ricordiamo che la convoluzione tra i due filtri moltorapida in quanto in kernel sono sempre molti pi piccoli dellimmagine).

Dalla convoluzione dei due filtri otteniamo quello che viene detto Lapla-ciano del Gaussiano:

LoG(x, y) = 12[1 x2+y2

22]e x

2+y2

22

0 1 1 2 2 2 1 1 01 2 4 5 5 5 4 2 11 4 5 3 0 3 5 4 12 5 3 12 24 12 3 5 22 5 0 24 40 24 0 5 22 5 3 12 24 12 3 5 21 4 5 3 0 3 5 4 11 2 4 5 5 5 4 2 10 1 1 2 2 2 1 1 0

Il Laplaciano del Gaussiano calcola le derivate seconde spaziali di unaimmagine, questo significa che nelle aree in cui limmagine presenta unaintensit costante loutput sar zero. Mentre, in prossimit di un cambia-mento di intensit la risposta sar positiva per il lato pi scuro e negativaper quello pi chiaro. Questo significa che possiamo ragionevolmente con-siderare che in corrispondenza di un bordo tra due regioni omogenee larisposta del LoG sar:


zero nei punti lontani dal bordo; positivo da un lato del bordo; negativo dallaltro lato del bordo.

Figura 3.8: Esempio su di risposta su un gradino.

Figura 3.9: LoG con kernel 7x7 = 1.0. Notiamo che limmagine contienevalori negativi e non interi, ma stata normalizzata in nel range [0 255]

Figura 3.10: Effetto di LoG con kernel 7x7 con = 1.0.

Differenza del Gaussiano (DoG) La procedura prevede di convolvere lim-magine (in scala di grigi) originale due volte tramite kernel gaussiano alfine di ottenere due immagini filtrate, ma con differente deviazione stan-dard (). Successivamente sottraiamo alla prima immagine, la seconda.Il risultato sar molto simile allapplicazione di un filtro passa-banda chetaglia quasi tutte le frequenze tranne una piccolo insieme.


DoG(x, , 1, 2) =1

12e (x)

2

221 122e (x)

2

222

Il DoG pu essere usato per aumentare la visibilit di edge o altri dettaglipresenti allinterno dellimmagine. In oltre rimuove le alte frequenze chespesso includono buona parte del rumore e questo lo rende ottimo perimmagini con alto grado di rumore.

Filtro Unsharp Questo semplicemente un operatore di sharpening che deri-va il proprio nome dal fatto che esalta i bordi (ed ogni altro componentead alta frequenza presente nellimmagine). La procedura prevede la sot-trazione di una versione morbida (senza bordi, o punti di alta frequenza)dellimmagine da quella originale:

g(x, y) = f(x, y) fsmooth(x, y)


Analizzando la risposta in frequenza di questo operatore possiamo capiremeglio come si comporta.

La figura a rappresenta il segnale originale, mentre la b la sua com-ponente a bassa frequenza. Sottraendo questultima al segnale inizialeotteniamo il segnale c, cio la sua componente ad alta frequenza (i bordi).Per mettere in evidenza i bordi basta sommare il segnale c con quello ori-ginale ottenendo un nuovo segnale in cui sono accentuate le componentealle frequenze alte.

fsmooth(x, y) = f(x, y) + k g(x, y)

dove k la costante di scala, solitamente scelta tra 0.2 e 0.7, in base quantosi voglia far risaltare il segnale ad alta frequenza.

Figura 3.11: A sinistra limmagine originale, al centro le componenti ad altafrequenza, a destra il risultato finale delloperazione con k=0.7

Un modo comune di realizzare questo filtro quello di usare linverso delLaplaciano:

Alcuni kernel che permetto di estrarre il segnale ad alta frequenza, dascalare ed aggiungere a quello originale sono i seguenti:

CAPITOLO 3. ELABORAZIONI DI BASSO LIVELLO 36 0 1 01 4 10 1 0

1 1 11 8 11 1 1

1 2 12 4 2

1 2 1

che rappresentano delle approssimazioni discrete del filtro Laplaciano.

Figura 3.12: Partendo da sinistra, limmagine originale, quella ottenuta conLoG 7x7, immagine ottenuta con il Laplaciano 7x7, immagine finale

Ovviamente il LoG pi robusto rispetto al rumore, essendo stato realiz-zato a questo scopo.

Capitolo 4

Elaborazioni di Medio Livello

4.1 SogliaturaIn numerosissime applicazioni le immagini da elaborare sono intrinsecamentebinarie: limmagine ideale della scena costituita da due soli livelli di grigiosignificativi : un livello chiaro (bianco) ed un livello scuro (nero).

Alcuni esempi di immagini intrinsecamente binarie:

Immagini di testo dattiloscritto o manoscritto.

Immagini di oggetti di spessore approssimativamente costante e superficieomogenea su sfondo omogeneo.

Immagini microscopiche di cellule, cromosomi etc..

In seguito allacquisizione mediante una telecamera si ottiene per unim-magine che occupa una porzione signicativa dellintervallo dei livelli di grigiodisponibili.

Le ragioni della comparsa di questi livelli spuri sono molteplici, ad esempio:

Illuminazione non perfettamente omogenea.

Rumore associato allacquisizione dallimmagine.

Diversa sensibilit dellobiettivo al centro ed ai bordi.

In questo contesto il primo passo dellelaborazione costituito tipicamentedalla binarizzazione dellimmagine, cio dalla trasformazione dellimmagine alivelli di grigio acquisita mediante la telecamera in unimmagine a due soli livel-li (immagine binaria) che catturi il contenuto informativo fondamentale dellascena.

4.1.1 Sogliatura con soglia globaleNei casi pi favorevoli la discriminazione fra punti dellimmagine corrispondentiad oggetti e punti di sfondo pu essere effettuata confrontando il livello di grigiodi ogni pixel con un valore di soglia opportunamente determinato. Il risultatodelloperazione unimmagine in cui i pixel delloggetto e dello sfondo sonomarcati con due livelli di grigio differenti. Listogramma dei livelli di grigio

37

CAPITOLO 4. ELABORAZIONI DI MEDIO LIVELLO 38

costituisce lo strumento fondamentale per la determinazione della soglia: sianalizza listogramma e si individua un valore adeguato ai fini della separazionefra oggetti e sfondo.

#de f i n e OBJECT 0#de f i n e BACKGROUND 255#de f i n e THRESHOLD 128

f o r ( i n t i = 0 ; i < N; i++){f o r ( i n t j = 0 ; j < M; j++){

i f ( I [ i ] [ j ] < THRESHOLD)O[ i ] [ j ] = OBJECT;

e l s e O[ i ] [ j ] = BACKGROUND;}

}

Ad esempio se consideriamo limmagine 4.1, possiamo capire che il valoredi soglia adeguato, in questo caso tra 110 e 130, per cui 120 dovrebbe essereun buon valore di soglia che ci porta al risultato dellimmagine 4.2. Fino adora abbiamo analizzato un caso ottimale, in cui si presentano due picchi bendistinti allinterno dellistogramma (istogramma bimodale), nella maggior partedei casi la soglia non cos immediata da individuare. Quanto maggiore la sovrapposizione dei modi allinterno dellistogramma tanto pi complessoscegliere il valore della soglia, ed i risultati della sogliatura sono peggiori.

La sovrapposizione fra i due modi dellistogramma associati alloggetto edallo sfondo implica lesistenza di pixel delloggetto pi chiari (scuri) di pixeldello sfondo e di pixel dello sfondo pi scuri (chiari) di pixel delloggetto. Evi-dentemente, in tale situazione il livello di grigio di un pixel non una caratte-ristica sufficiente ai fini della discriminazione fra oggetto e sfondo e limmaginenon pu essere binarizzata correttamente (cio senza errori) tramite una soglia


Figura 4.1: Immagine trattabile con soglia globale.

Figura 4.2: Risultato della sogliatura dellimmagine precedente.


globale. Tuttavia, vista limportanza delloperazione di binarizzazione, cheriduce drasticamente la quantit dei dati preservando il contenuto informati-vo primario dellimmagine, in moltissime applicazioni si cerca di determinareuna soglia globale che consenta di effettuare una binarizzazione ragionevolmen-te corretta anche in presenza di un certo grado di sovrapposizione fra i modi. importante ricordare che ci sono dei casi in cui i modi delistogramma si fon-do completamente, per cui diventa impossibile determinare un valore di sogliaglobale.

Figura 4.3: Immagine non binarizzabile tramite soglia globale.

Limmagine intrinsecamente binaria (oggetto su sfondo) ma a causa dellaforte variazione dellilluminazione nella scena i valori di intensit dello sfondoe delloggetto non sono nettamente distinti. Di conseguenza, i due modi del-listogramma sono significativamente sovrapposti. Nelle due immagini si puosservare come la scelta di un valore di soglia troppo basso porti alla classi-ficazione come sfondo dei pixel appartenenti alla parte pi chiara delloggettomentre quella di una soglia troppo alta porti a classificare come oggetto i pixelappartenenti alla parte pi scura dello sfondo.


4.1.2 Evidenziare listogrammaNei casi in cui listogramma ragionevolmente bimodale possibile ricorrere adalcune semplici elaborazioni che facilitano la scelta della soglia.

1. Istogramma Modificato: quando la sovrapposizione fra i due modi dovutaprincipalmente alle regioni di transizione fra oggetto e sfondo possibi-le evidenziare i due modi calcolando listogramma relativo ai soli pun-ti dellimmagine caratterizzati da basso valore del modulo del gradiente.Difatti, poich i punti a basso gradiente saranno situati presumibilmen-te allinterno delle regioni associate ad oggetto e sfondo, listogrammamodificato presenter due modi maggiormente separati rispetto a quellodellimmagine originaria.

2. Smoothing : quando la sovrapposizione fra i due modi dovuta princi-palmente alle fluttuazioni intorno al valor medio dei livelli di grigio deipixel appartenenti alloggetto ed allo sfondo utile eseguire unoperazio-ne di smoothing (ad esempio una semplice media con finestra 3x3) primadel calcolo dellistogramma. Difatti, loperazione di smoothing riduce lefluttuazioni intorno al valor medio. Evidentemente lelaborazione ha an-che leffetto, non desiderato, di smussare i bordi (aumentando quindi lasovrapposizione dovuta alle regioni di transizione), ma se la causa prin-cipale della sovrapposizione sono le fluttuazioni intorno al valor medioleffetto globale una maggior separazione fra i due modi dellistogrammarispetto allimmagine originaria.

4.1.3 Tecniche alternative di sogliaturaPer aggirare le problematiche della sogliatura con soglia globale, spesso ven-gono utilizzate tecniche alternative che permetto di migliorare la resa finaledellelaborazione, tra queste ricordiamo:

Calcolo automatico della soglia Analizzando listogramma, determinano au-tomaticamente la soglia per la binarizzazione.

Sogliatura con soglia variabile Lapproccio tipico a questo problema con-siste nella suddivisione dellimmagine in blocchi e nelluso di una sogliadistinta per ogni blocco. Una volta eseguita la suddivisione, la scelta dellasoglia dei singoli blocchi pu essere effettuata manualmente o medianteuno dei metodi di determinazione automatica. La suddivisione in blocchisi basa sullosservazione che quanto pi piccola larea da binarizzare tan-to pi probabile che al suo interno le condizioni di illuminazione sianouniformi. Da questo punto di vista sarebbe quindi auspicabile la scelta diblocchi piccoli. Bisogna per tenere presente che la scelta di blocchi trop-po piccoli comporta il rischio che essi contengano esclusivamente regionidelloggetto o dello sfondo. In tal caso listogramma del blocco presentaun solo modo, ed, in assenza di informazioni aggiuntive, ci porta ad unascelta errata della soglia. La scelta della dimensione del blocco dipendequindi fortemente dalle caratteristiche delle immagini di lavoro ed uncompromesso fra lesigenza di tenere il blocco piccolo al fine di limitare le


variazioni di luminosit al suo interno e di renderlo sufficientemente gran-de da contenere sia pixel appartenenti alloggetto sia pixel appartenentiallo sfondo.

Sogliatura con soglia locale Lapproccio basato sulla soglia variabile pu es-sere ulteriormente esteso fino a prevedere una soglia locale, cio una sogliaper ogni pixel dellimmagine il cui valore dipende delle caratteristiche del-limmagine in un blocco di dimensione opportuna centrato nel pixel (comeavviene per tutti gli operatori locali). Inoltre necessario ricorrere ad unmetodo automatico per la determinazione della soglia essendo impensa-bile scegliere manualmente la soglia per ogni pixel. Al fine di limitare ilcarico computazionale, si adotta generalmente un metodo semplice per ladeterminazione automatica della soglia (valor medio o mediano). Lusodi una soglia locale quindi particolarmente adeguato per immagini incui c unalta probabilit che in un blocco piccolo siano presenti sia pixeldelloggetto sia pixel dello sfondo (dattiloscritto o manoscritto).

Binarizzazione tramite due livelli di soglia Esistono metodi di binarizza-zione che prevedono il confronto del livello del pixel con due valori disoglia. Lidea consiste nello sfruttare anche le relazioni di adiacenza frai pixel al fine di introdurre una tolleranza (intervallo di isteresi) sulla so-glia di binarizzazione. Si cerca di classificare come oggetto anche i pixelsche hanno livello di grigio superiore alla soglia ma sono vicini a punti chesicuramente appartengono alloggetto.

4.2 SegmentazioneLanalisi automatica delle immagini ha lo scopo di estrarre informazioni conun appropriato grado di utilit. Segmentare significa suddividere limmagine inparti significative, per cui a basso livello pu significare identificare delle regioni,mentre ad alto livello ha come scopo quello di identificare oggetti (anche se questaoperazione di tipo semantico e difficilmente automatizzabile). Ovviamente, illivello di dettaglio della segmentazione dipende dal tipo di applicazione.

4.2.1 Definizione FormaleDetta P (x, y) una propriet dellimmagine definita localmente (intensit lumi-nosa, colore, etc . . . ), con il termine segmentazione si intende il partizionamentodellimmagine R in un insieme di regioni R1, R2, ..., RS omogenee rispetto aP. Il partizionamento deve soddisfare i seguenti vincoli:

lunione delle regioni lintera immagine:Ri = R

Le regioni sono disgiunte: RiRj = 0

La segmentazione un passo fondamentale nel processo di interpretazionepoich consente di estrarre le parti elementari dellimmagine. Tali parti pos-sono poi essere analizzate separatamente, al fine di misurare le propriet chene consentono la caratterizzazione, e globalmente, al fine di stabilire quali sonole relazioni che le legano. Possiamo dire, quindi, che la segmentazione unprocesso di classificazione in cui ogni pixel dellimmagine viene assegnato ad


una classe (regione) in funzione del valore di P. Per cui possiamo considerarela binarizzazione come un caso particolare, molto semplice, di segmentazionein cui limmagine viene partizionata in due sole regioni (sfondo e oggetto) e lapropriet il valore di intensit luminosa di ogni pixel. molto difficile stabi-lire un criterio generale che consenta di valutare le prestazioni di un algoritmodi segmentazione, poich linterpretazione dei risultati fortemente dipendentedallapplicazione. Tuttavia, gli algoritmi pi generali tendono a rispettare leseguenti regole:

Le regioni devono essere il pi possibile omogenee rispetto a P.

Le regioni non devono avere troppe lacune.

Regioni adiacenti devono essere caratterizzate da valori significativamentediversi di P.

I confini fra le regioni devono essere regolari e la loro localizzazione spazialedeve essere accurata.

4.2.2 Algoritmi di segmentazioneEsistono vari algoritmi che permettono di effettuare la segmentazione di unaimmagine e dipendono dalla propriet P che si considera e dalla classificazioneeffettuata, questi sono basati su due aspetti: similarit o discontinuit. Sullaprima si basano i metodi di sogliatura che sono anche quelli pi semplici ecomputazionalmente meno onerosi, ma forniscono risultati soddisfacenti solonel caso di immagini semplici (cio con un numero piccolo di regioni). Persuperere i limiti dellapproccio basato su sogliatura sono stati sviluppati deglialgoritmi pi complessi:

Relaxation

Region Growing

Split-and-Merge

che, a differenza dei metodi di sogliatura, sfruttano anche le relazioni di adiacen-za che sussistono fra i pixel dellimmagine. Altri approcci, ancor pi sofisticati,si basano sullestrazione di un determinato insieme n-dimensionale di caratte-ristiche locali e sullindividuazione di gruppi di pixel omogenei rispetto a talicaratteristiche (Clustering). Sulla discontinuit si basano, invece, gli algoritmiche estraggono i contorni (edge) o altre caratteristiche come i punti isolati, linee,etc . . .

4.2.3 Tecniche basate su discontinuit

Punti isolati e lineeIl metodo spesso utilizzato per individuare le discontinuit si basa su una ma-schera di pesi:

Rpuntuale =wi zi

dove wi sono ottenuti dalla matrice dei pesi e zi sono i valori dei pixel.


1 1 11 8 11 1 1

Per individuare un punto isolato si valuta la condizione |Rpuntuale| > T in

cui T una soglia opportunamente scelta. Supponiamo, infatti, che un puntoisolato abbia un valore di toni di grigio zi,j molto differente dai punti adiacenti,per questo motivo nella maschera precedente abbiamo dato un peso positivo alpunto che ci interessava. Infatti, svolgendo la sommatoria localmente sul puntosi rilever un valore elevato di |Rpuntuale|.

Per le linee omogenee spesse un pixel su sfondo uniforme possiamo usare leseguenti maschere di pesi, infatti R diventa massimo quando combacia con lalinea rappresentata dai pesi di maggior valore.1 1 12 2 2

1 1 1

Linea orizzontale1 2 11 2 11 2 1

Linea verticale 2 1 11 2 11 1 2

Linea obliqua1 1 21 2 1

2 1 1

Linea obliquaIl pi elevato valore di |Rj | associato a queste maschere indica una maggiore

probabilit che il punto in cui si applicata la maschera appartenga ad unalinea orientata nella direzione della maschera j.

Individuzione dei contorniIl contorno di un oggetto rappresenta una zona di frontiera, una separazione tralo sfondo e loggetto oppure tra questo ed altri oggetti presenti allinterno dellascena, ed il primo passo per lindividuazione di un oggetto. Un edge separadue regioni con propriet di toni di grigio distinguibili.

Gli algoritmi di edge detection funzionano meglio quando le regioni da sepa-rare sono uniformi, solitamente lindividuazione di un contorno si divide in duefasi:


1. Applicazione di filtri derivativi : il valore in ogni punto di uscita rap-presenta in modulo una stima numerica del gradiente spaziale nel puntocorrispondente nellimmagine di ingresso.

2. Sogliatura e binarizzazione.

Possiamo notare nellimmagine che il profilo dei livelli di grigio non netto, agradino, ma rappresenta una rampa con un salita molto ripida, dovuto ad effettidi blurring (offuscamento) causato dal campionamento. La derivata prima (D) eseconda (D2) sono diverse solo nelle zone di transizione, analizzandole possiamodire che:

D > 0 : da scuro a chiaro.

D < 0 : da chiaro a scuro.

D = 0 : zone a livello costante.

D2 > 0 : prossimit scura del contorno.

D2 < 0 : prossimit chiara del contorno.

D2 = 0 : zone a livello costante.

D2 presenta uno zero-crossing (cambio di segno o attraversamento dellozero) in corrispondenza delle transizioni.

Per cui, mentre la derivata prima identifica il contorno, la derivata secondalo localizza con precisione nel momento in cui attraversa lo zero e tramite ilcambio di segno possiamo dire se siamo nel versante chiaro o in quello scuro. Ilcalcolo della derivata prima e seconda dellintensit luminosa I(x, y) oneroso,per questo motivo useremo il gradiente per la derivata prima ed il laplacianoper la derivata seconda. I contorni, come abbiamo notato, non sono semprenetti, ma posso assumere la forma di una rampa (con pendenze differenti). Per


la ricerca di contorni di orientamento qualunque valgono le stesse osservazioni,considerando il profilo di grigio lungo una direzione ortogonale al contorno nelpunto desiderato:

4.2.4 Tecniche basate sul gradienteIl gradiente di una funzione di due variabili il vettore delle derivate direzionilungo le direzioni degli assi, per cui:

I(x, y) = [Gx, Gy]T = [ Ix ,Iy ]

T

ma oltre a queste informazioni siamo anche interessati al modulo ed alla dire-zione:

modulo: |I(x, y)| =G2x +G

2y |Gx|+ |Gy|

direzione: (x, y) = tan1(GxGy )

La presenza di un edge si valuta con il superamento di una soglia da parte delmodulo del gradiente. Le formule fino ad ora presentate si riferiscono a funzioniche sono continue, ma a noi interessano le stesse operazioni nel caso discreto,ilmodo pi semplice per ottenere una approssimazione discreta del gradiente quella di usare la differenza mobile oppure le differenze incrociate. Consideriamoil seguente esempio, per capire cosa rappresentano:

. . ....

......

. . . z1 z2 z3 . . .

. . . z4 z5 z6 . . .

. . . z7 z8 z9 . . .

...

......

. . .

Le componenti del gradiente nel punto z5 sono:

Gx = z5 z6

Gy = z5 z8

1. Differenza Mobile: I = (z5 z6) + (z5 z8)

2. Differenze Incrociate: I = (z5 z9) + (z5 z8)

Queste operazioni possono essere implementate con lapplicazione di ma-schere 2x2, ad esempio le differenze incrociate possono essere ottenute tramitegli operatori di Roberts, che vengono utilizzati per misurare le componenti delgradiente nelle due direzioni.

CAPITOLO 4. ELABORAZIONI DI MEDIO LIVELLO 47[1 00 1

][0 11 0

]Utilizzando la differenza mobile nellesempio degli edge a rampa o a gradino

otteniamo:

I contorni a rampa non possono essere localizzati dalledge detector a differenzamobile con la precisione del pixel, infatti nelle immagini reali otteniamo dei con-torni non ben definiti. Inoltre il metodo molto sensibile alle piccole fluttuazionidi intensit e tende ad esaltare il rumore.

Figura 4.4: Esempio di applicazione della differenza mobile. Possiamo notare ladifferenza orizzontale e quella verticale. In fondo a destra il risultato.

Per migliorare questa tecnica possiamo tenere in conto dei valori dei pixel daentrambe le parti del potenziale punto di edge, usiamo la differenza separata:

I = (z4 z6) + (z2 z8)

che porta al seguente risultato:


Operatori di Sobel e PrewittPer ottenere risultati migliori possiamo utilizzare maschere di dimensione pigrande, come quelle 3x3, queste ci permettono di effettuare simultaneamente ladifferenza lungo una direzione ed una media spaziale lungo la direzione ortogo-nale, divenendo meno sensibile alle variazioni di luminosit ed al rumore. I dueoperatori ottenuti sono chiamati:

1. Operatore di Prewitt 1 0 11 0 11 0 1

1 1 10 0 0

1 1 1

2. Operatore di Sobel 1 0 12 0 2

1 0 1

1 2 10 0 0

1 2 1

Figura 4.5: La prima immagine sulla sinistra ottenuta con loperatore di Sobel,al centro con loperatore di Prewitt, a destra con la differenza mobile. In finenotiamo la forte sensibilit al rumore.


A volte si preferisce normalizzare i gradienti di riga e di colonna in mododa avere medie pesate unitarie per i pixel posti ad entrambi i lati delleventualeedge (si moltiplica per 1/3 la maschera di Prewitt e di 1/4 la maschera di sobel).Anche questi operatori hanno dei problemi con edge che presentano rampe menoripide, in quando sono sempre del tipo a differenza separata.

Come abbiamo potuto notare, gli operatori basati sul gradiente sono pocoefficaci in presenza di rumore, per questo motivo si possono applicare preventi-vamente delle operazioni di smoothing per ridurre il rumore. Alternativamen-te possiamo aumentare larea su cui viene applicato il gradiente con masche-re di dimensione pi grande, che per aumenterebbero enormemente lonerecomputazionale delloperazione.

Canny Edge DetectorLobiettivo di John F. Canny fu quello di sviluppare un algoritmo che fosseottimale rispetto ai seguenti criteri:

1. Detection: La probabilit di individuare punti che appartengono a edgereali dovrebbe essere massimizzata, mentre la probabilit di individuarefalsi bordi dovrebbe essere minimizzata. Ci corrisponde a massimizzareil rapporto segnale/rumore.

2. Localizzazione: Il bordo individuato dovrebbe essere il pi vicino possibileal bordo reale.

3. Numero di risposte: Un solo bordo dovrebbe essere individuato, non pi diuno (Questo requisito, si pu supporre implicitamente incluso nel primo).

Questo algoritmo, a differenza degli operatori precedenti, ci restituisce edgedello spessore di esattamente un pixel. La formulazione matematica di tali criterida parte di Canny risulta ottima per una classe di problemi di individuazionedegli edge (conosciuta come step edge). Lalgoritmo lavora su cinque passi :

1. Smoothing : Limmagine viene sfocata al fine di ridurre il rumore

2. Calcolo del gradiente: Il bordo pu essere individuato come il punto in cuiil modulo del gradiente assume un modulo grande.

3. Non soppressione dei massimi : Solo i massimi locali dovrebbero esseremarcati come un bordo. Ci garantisce che i bordi siano di un pixel dispessore.

4. Doppia sogliatura: I potenziali bordi, vengono individuati attraverso unasogliatura.

5. Edge tracking by hysteresis: I bordi vengono determinati, eliminando tuttii bordi che non sono connessi ai bordi forti.

Smoothing Quando limmagine viene acquisita dalla camera impossibile evi-tare che su di essa sia presente una certa quantit di rumore. Al fine digarantire che questo rumore non porti a commettere errori in fase di in-dividuazione degli edge, il rumore deve essere ridotto. Di conseguenzalimmagine viene filtra attraverso un filtro Gaussiano. Il kernel utilizzato


da tale filtro, con deviazione = 1.4. Si noti inoltre che in generale pigrande , pi grande sar la campana e di conseguenza pi grande sarleffetto di smooth ottenuto sul immagine.

B = 1159

2 4 5 4 24 9 12 9 45 12 15 12 54 9 12 9 42 4 5 4 2

La dimensione di ha in generale impatto sulla dimensione del kernel.

Figura 4.6: Limmagine sulla sinistra quella originale, mentre sulla destranotiamo leffetto del filtro Gaussiano per lattenuazione del rumore

Calcolo del Gradiente Lalgoritmo di Canny individua i bordi, sfruttandouna grossa variazione dellintensit, allinterno di un immagine in scala digrigi. Queste aree vengono determinate calcolando il gradiente dellimma-gine. Il gradiente in ogni pixel presente nellimmagine in cui applicatoleffetto di smooth, pu essere ricavato applicando loperatore di Sobel. Ilprimo passo quello di approssimare il gradiente, lungo le direzioni x e yrispettivamente, utilizzando i kernel seguenti:

KGX =

1 0 12 0 21 0 1

KGY =

1 2 10 0 01 2 1

Lampiezza del gradiente (anche conosciuta come punti di forza del bordo)pu allora essere determinata come una misura della distanza Euclidea,applicando le leggi di Pitagora. Essa pu essere qualche volta semplificataapplicando la misura della distanza di Manhattan in modo da ridurre lacomplessit computazionale.


Distanza Euclidea: |G| =G2x +G

2y

Distanza Manhattan: |G| = |Gx|+ |Gy|

dove Gx e Gy sono i gradienti lungo le direzioni x ed y. chiaro dallafigura sopra, che limmagine del modulo del gradiente, indicano spesso ibordi abbastanza chiaramente. Tuttavia, i bordi sono tipicamente ampi edi conseguenza non indicano esattamente dove sono gli edge. Per renderepossibile ci la direzione del bordo pu essere determinata e memorizzatacome mostrato nel equazione seguente.

= arctan(|Gy||Gx| )

Figura 4.7: Calcolo delle direzioni di crescita del gradiente, ad esempio tramiteloperatore di Sobel

Come si pu notare dallimmagine sopra I bordi pi chiari, di una mag-giore intensit sono quelli di passaggio tra loggetto e lo sfondo nero. Lospessore maggiore di 1 pixel, poich a seguito del filtraggio Gaussianoi contorni non sono ben definiti, ma pi smooth. Sicuramente se aves-simo applicato un filtraggio derivativo sullimmagine originale avremmoottenuto una maggiore quantit di rumore, dei bordi pi stretti ma conun intensit maggiore. In tale immagine viene riportato pixel per pixel ilmodulo del gradiente nel punto specifico.

Non soppressione dei massimi Lo scopo di questo passo quello di con-vertire i bordi blurred nellimmagine dellampiezza del gradiente in bordisharp. Fondamentalmente, questo fatto per preservare ogni massimolocale allinterno del immagine gradiente, e cancellare ogni altra cosa.Lalgoritmo per ogni pixel dellimmagine del gradiente:

1. Calcolare , approssimando ad una delle quattro direzioni 0, 45, 90o 135. Ovviamente per gli edge, 180 = 0, 225 = 45 , etc. Cicomporta che nel range [22.5 . . . 22.5] e [157.5 . . . 202.5] verrapprossimato a = 0. Sfruttando una rappresentazione grafica,ogni bordo assume uno dei quattro colori :


(verde intorno 225, blu intorno 270 e rosso intorno ai 315) cicorrisponde allutilizzare una regione 8-connessa.

2. Confrontare la edge strenght del pixel corrente con ledge strengh deipixel lungo le direzioni positive e negative del gradiente. Quindi,verranno esaminati solo tre pixel in un intorno 3x3 del pixel (x, y):(x, y) = 0

Se (x, y) = 0, allora verranno analizzati i pixel: (x+1, y), (x, y)e (x 1, y).

Se (x, y) = 90, allora verranno analizzati i pixel: (x, y +1), (x, y) e (x, y 1).

Se (x, y) = 45, allora verranno analizzati i pixel: (x + 1, y +1), (x, y) e (x 1, y 1). Se (x, y) = 135, allora verranno analizzati i pixel: (x+ 1, y 1), (x, y) e (x 1, y + 1).

Ad esempio se la direzione del gradiente nord ((x, y) = 90) verrconfrontato con il pixel a nord e a sud.

3. Se il pixel (x, y) ha un valore del modulo del gradiente maggiorerispetto ai tre pixel esaminati, viene mantenuto come bordo. Seinvece uno dei due pixel ha un valore del modulo del gradiente pigrande, allora il pixel (x, y) non al centro del edge e perci verrscartato, non classificato come un edge pixel.

Si noti che la scelta di considerare tre pixel deriva dal fatto che nel casoideale la dimensione del bordo di un pixel, ma dato che stato applicatoun filtraggio Gaussiano il bordo non pi puntuale ma distribuito su diuna fascia di valori di cui si vuole considerare un solo pixel, il massimolocale. Per raggiungere tale risultato si prende nel punto considerato ladirezione delledge che permette di limitare la ricerca a suoli due pixel chepotrebbero essere degli edge. La localit data dal fatto che si consideraun area 3x3.

Figura 4.8: Le intensit degli edge sono indicate sia con i colori che con i numeri,le frecce invece indicano la direzione del gradiente

Un semplice esempio di non soppressione dei massimi viene mostrato nellafigura successiva. Quasi tutti i pixel hanno un gradiente con direzione chepunta verso nord. Essi vengono quindi confrontati con i pixel sopra e


Figura 4.9: In questa figura possiamo notare leffetto della soppressione, sonopreservati solo gli edge-pixel in cui il gradiente ha un massimo locale.

sotto. Il pixel che risultano essere pi grandi in questo confronto, vengonocontrassegnati come bordi bianchi. Ogni altro pixel verr soppresso.

Doppia sogliatura Gli edge-pixel rimanenti dalla fase di non soppressione deimassimi, vengono (ancora) marcati con la loro intensit pixel per pixel.Alcuni di questi, probabilmente saranno un vero bordo dellimmagine,ma taluni potrebbero essere causati dal rumore o da una variazione dicolore, per esempio a causa di superfici ruvide. Il modo pi sempliceper discernere tra questi vari casi quello di utilizzare una sogliatura, inmodo da garantire che solo i bordi che superano un certo valore vengonopreservati. Lalgoritmo di individuazione dei bordi di Canny, utilizza duesoglie. Gli Edge-pixels che superano la soglia superiore verranno marcaticome strong edge pixel pi piccoli della soglia inferiore saranno eliminati egli edge pixel che si trovano tra le due soglie verranno marcati come weak.

Figura 4.10: Leffetto sullimmagine di test con soglia rispettivamente fissata a20 e a 80

Si noti, infine, che allaumentare le soglie superiori e inferiori, lalgoritmodi Canny restituir un numero minore di edge.


Edge tracking by hysteresis Gli strong edges vengono in generale interpre-tati con bordi certi, e possono essere immediatamente inclusi nellimmaginefinale. Gli edge weak sono inclusi se e solo se sono connessi a degli ed-ges strong. Il concetto che il rumore e le altre piccole variazioni sonoimprobabili che siano presenti in un edge strong (con un opportuna con-figurazione del livello di soglia). Questi strong edge saranno (al massimo)causati dai veri bordi dellimmagine. Gli edge weak possono essere datisia dai bordi veri che dalle variazioni di colore/rumore. Questultimo tiposar probabilmente distribuito indipendentemente dai bordi su tutta lim-magine, e di conseguenza solo una piccola quantit sar situata accantoagli strong edge. I weak edge dovuti agli edge veri molto probabile chesiano connessi direttamente agli edges strong. In altre parole, i pixel in-certi devono essere classificati come appartenenti o meno al bordo. Questopu essere fatto considerando se in un intorno del pixel considerato c al-meno un pixel che appartenente al bordo. Se il pixel considerato si trovatra Thigh e Tlow e in un intorno 3x3 c almeno un pixel cha ha un valoremaggiore di Thigh, allora il pixel considerato viene marcato come edge,altrimenti allargo lintorno considerato ad una regione 5x5 e controllo sein questo nuovo intorno c un pixel maggiore di Thigh. Se la condizionericercata non viene soddisfatta sul pixel considerato, questo verr scartatoe considerato come sfondo. Il tracciamento degli edge pu essere imple-mentato tramite un analisi BLOB (Binary Large Object). Gli edge pixelvengono divisi in BLOB connessi, utilizzando regioni 8-connesse. I BLOBche contengono almeno un edge strong vengono preservati, mentre gli altriBLOB soppressi. Leffetto del tracciamento degli edge sullimmagine ditest viene mostrato nella figura seguente.

Figura 4.11: Nellimmagine possiamo vedere gli effetti delledge tracking e lef-fetto finale dellalgoritmo di Canny. Limmagine centrale nostra gli strong edgein bianco, i weak edge che sono connessi con quelli strong tramite gli edge inblu, tutti gli altri in rosso

4.2.5 Tecniche basate sul LaplacianoGli zero-crossing della derivata seconda identificano con precisione gli edge, edil segno determina lappartenenza di un pixel al versante scuro oppure a quellochiaro. Per calcolare la derivata seconda della funzione di intensit luminosaI(x,y) usiamo loperatore Laplaciano definito come:

L(x, y) = 2I(x, y) = 2Ix2 +

2Iy2

Il modo migliore per approssimare il Laplaciano nel caso discreto quello dicalcolare le differenze delle derivate prima lungo gli assi:


Figura 4.12: Tutti i passaggi dellalgoritmo di Canny

L(x, y) = [I(x, y) I(x 1, y)] [I(x+ 1, y) I(x, y)] + [I(x, y) I(x, y 1)] [I(x, y + 1) I(x, y)]

quindi:

L(x, y) = 4I(x, y) I(x 1, y) I(x+ 1, y) I(x, y 1) I(x, y + 1)

Dato che la risposta impulsiva del filtro ottenuto sfruttando i quattro vi-cini del pixel troppo soggetta al rumore ed incapace di rilevare la direzionedelledge, si sfrutta solitamente il Laplaciano del Gaussiano (LoG).

4.3 Tecniche di RegionalizzazioneQueste tecniche sono basate sullanalisi delle similarit tra pixel al fine di estrarredirettamente delle regioni. A differenza della segmentazione, questa pi forteperch aggiunge il concetto di connessione. Si suddivide limmagine R in Riregioni tali che:

Ogni pixel contenuto in una regione Ri.

Ogni regione Ri connessa.

Ogni regione Ri disgiunta dalle altre.

Tutti i pixel appartenenti ad una regione devono soddisfare le propriet in basealla quale la regione stata identificata P (Ri), ed ogni regione deve esserediversa dalle altre.

4.3.1 Labeling di componenti connesseIl concetto di componente connessa deriva dalla teoria dei grafi, e con esso anchelalgoritmo di etichettatura in cui un sotto insieme di componenti connesse vieneetichettata univocamente sulla base di una determinata euristica. Nellambitodella computer vision viene utilizzato per identificare regioni connesse allinterno


di una immagine binaria, solitamente con lo scopo di estrarre dei blob da poteranalizzare in un secondo momento per effettaure tracking, conteggio, etc . . . .Bisogna fare attenzione a non confondere il labeling delle componento connessecon la segmentazione. Due esempi di labeling potrebbero essere i seguenti.

Figura 4.13: Esempi di labeling di componenti connesse

La nozione di componente connessa dipende dal criterio di connessione adot-tato:

4-connesso: se nellanalisi della propriet comune si considera il pixel cen-trale e quelli sopra, sotto, a destra, a sinistra. In questo caso analizzaremoletichetta dei pixel a Nort e Ovest.

8-connesso: si considerano tutti i pixel intorno al pixel analizzato primadi assegnare la label. In questo caso analizziamo letichetta dei pixel aNord, Ovest, Nord-Ovest, Nord-Est.

Lalgoritmo per il labeling pi semplice prevede solo due passaggi:

1. Identificazione delle equivalenze ed assegnazione di label temporanee.

2. Valutazione delle classi di equivalenza tra le label temporanee ed assegna-zione di label definitive.

Nel caso 4-connesso possiamo riassumere le condizioni da valutare per determi-nare il valore delletichetta del pixel sotto analisi come segue:

1. Il pixel a sinistra (Ovest) del pixel corrente presenta lo stesso valore?

Si - Il pixel sotto analisi si trova nella stessa region, gli assegnamo lastessa etichetta di quello alla sua sinistra.

No - Passa alla prossima condizione.

2. Il pixel a in alto (Nord) e quello a sinistra (Ovest) del pixel corren-te presentano lo stesso valore, ma non la stessa etichetta (Conflitto traetichette)?


Si - Sappiamo che il pixel in alto e quello a sinistra appartengono allastessa regione e devono essere fusi. Assegna al pixel corrente il mini-mo tra le etichette del pixel sopra e di quello a sinistra, e memorizzala loro relazione di equivalenza.


3. Il pixele a sinistra di quello corrente presenta un valore differente e quelloin alto presenta lo stesso valore?

Si - Assegna letichetta del pixel in alto al pixel corrente.


4. Il pixel in alto e quello a sinistra presentano valori differenti?

Si - Crea una nuova etichetta ed assegnala al pixel corrente

Lalgoritmo procede in questo modo analizzando tutti i pixel dellimmagine ecreando nuove regioni dove necessario. Quando viene completata letichettaturainiziale si effettua una seconda passata per sostituire alle etichiette iniziali quelleequivalenti.

a lgor i thm TwoPass ( data )l i nked = [ ]l a b e l s = s t ru c tu r e with dimensions o f data ,

i n i t i a l i z e d with the value o f Background

F i r s t pass

f o r row in data :f o r column in row :

i f data [ row ] [ c o l ] i s not Background

ne ighbors = connected e lementswith the cur rent element s l a b e l

i f ne ighbors i s emptyl i nked [ NextLabel ] = s e t conta in ing NextLabell a b e l s [ row ] [ column ] = NextLabelNextLabel += 1

e l s e

Find the sma l l e s t l a b e l

L = ne ighbors l a b e l sl a b e l s [ row ] [ column ] = min (L)f o r l a b e l in L

l i nked [ l a b e l ] = union ( l i nked [ l a b e l ] , L)

Second pass


f o r row in dataf o r column in row

i f l a b e l s [ row ] [ column ] i s not Backgroundl a b e l s [ row ] [ column ] = min ( l i nked [ l a b e l s [ row ] [ column ] ] )

r e turn l a b e l s

4.3.2 Region GrowingIl region growing utilizza un semplice approccio, cio parte da alcuni pixel(seeds) che rappresentano regioni distinte dellimmagine (per fare ci ci si pubasare sulle informazioni fornite dallistogramma) e li accresce fino a che tut-ta limmagine risulta coperta. Per fare ci servono una regola che descriva ilmeccanismo di crescita ed una regola che controlla lomogeneit di ogni regionedopo ogni accrescimento e che verifica se possibile unire due regioni distinte.Il meccanismo di crescita funziona in questa maniera:

1. Ad ogni passo k e per ciascuna regione Ri(k), i = 1, . . . , N , si controlla seci sono pixel non classificati nel vicinato 8-connesso (in poche parole gliotto pixel che circondano quello in esame) di ciascun pixel del bordo dellaregione;

2. In caso positivo, prima di assegnare tale pixel alla regione Ri(k), si verificase la regione ancora omogenea, ovvero se ancora valida la propriet:P (Ri(k), Ux) = TRUE Un possibile esempio di test di omogeneit ilseguente: se lintensit del pixel vicina al valore medio della regione. Lascelta delle propriet P usate per la segmentazione dipende dal problemain esame e dai dati a disposizione (intensit, colore, texture).

La regola di arresto dellaccrescimento di una regione pu essere determinatada:

Assenza di pixel che soddisfano il criterio di aggregazione.

Criteri globali che tengano conto non solo delle P locali, ma anche di comesi formata la regione fino a quel momento.

4.3.3 Region Splitting and MergingQuesta tecnica prevede di partire dallimmagine intera, suddividendola in partidisgiunte sempre pi piccole, fondendo quelle adiacenti con caratteristiche simili.Il procedimento termina quando tutte le regioni soddisfano i criteri previsti perla segmentazione e ricoprono lintera immagine.

Ad ogni livello di suddivisione si verifica la propriet per tutti i quadranti,se non verificata viene ulteriormente suddiviso, e cos via.


Il solo splitting non potrebbe evitare, allultimo livello di suddivisione, lapresenza di regioni adiacenti con caratteristiche simili. Per cui, si fa il mergingdelle regioni adiacenti i cui pixel soddisfano la propriet P. Possiamo riassumerela procedura come segue. Ad ogni livello di suddivisione:

1. Suddividere in quattro quadranti ogni regione Ri per la quale P (Ri) falsa.

2. Fo

Modelli e Metodi Per La Visione Artificiale

Documents

Transcript of Modelli e Metodi Per La Visione Artificiale