Corso di laurea magistrale in Informatica Multimedia Prof ... 10... · Questo metodo segmenta con...

Corso di laurea magistrale in Informatica

Multimedia - Prof. F.Stanco

Segmentazione

A cura di Andrea Tambone

Lo scopo della segmentazione è suddividere un immagine in regioni contenenti pixel simili per valore, ovvero in

regioni che ci consentano di individuare superfici e oggetti dall’immagine di partenza.

La segmentazione può esser utilizzata per object recognition, la stima di occlusion boundary, compressione di

immagini, image editing e image database look-up.

Introduzione

A cura di Andrea Tambone 16 Dicembre 2013

16 Dicembre 2013 A cura di Andrea Tambone

Posta R un’intera regione spaziale,

occupata da un immagine, possiamo

vedere la segmentazione come un

processo di partizionamento di R in n sottoregioni:

R1 , R2 , … , Rn


Requisiti

1) L’unione delle partizioni di R dev’essere uguale ad R stesso.

2) Ogni singola partizione di R dev’essere un insieme connesso.

3) L’intersezione tra tutti gli insieme di R dev’esser l’insieme vuoto (ovvero tutti gli insiemi devono essere disgiunti).

4) L’insieme dei pixel di ogni singola regione deve avere la stessa intensità.

5) I pixel di due partizioni adiacenti devono avere intensità differente.


Una buona segmentazione è solitamente quella in cui:

- Pixel della stessa categoria hanno simili valori in scala di grigi di intensità multivariata e formano una regione

connessa.

- Pixel vicini appartenenti a categorie differenti, hanno valori differenti.

La segmentazione a volte è una fase critica nell’analisi delle immagini, e molto spesso gli algoritmi automatici hanno

un successo solo parziale, tuttavia alcuni interventi manuali possono favorire una buona segmentazione.


Approcci:

EDGE BASED Un filtro di Edge viene applicato all’immagine, in base all’output i pixel vengono classificati come

“edge” o “non edge” e i pixel che non sono separati da quelli di edge vengono inglobati nella

medesima categoria.

THRESHOLDING BASED I Pixel sono allocati nelle varie categorie in base al range di valori in cui giaciono nell’istogramma

dell’immagine. Questo metodo segmenta con maggior successo le immagini in due tipi di categorie.


Approcci:

REGION BASED

Gli algoritmi di segmentazione operano iterativamente raggruppando i pixel vicini con valori simili e separando i

gruppi di pixel di valore non simile.

NON ESISTE UN APPROCCIO PERFETTO, OGNUNO DI QUESTI HA DELLE PECCHE

Etichettatura dei pixel di un immagine in edge e non edge, i non edge che formano regioni connesse vengono

allocati alla stessa categoria.

L’etichettatura avviene per mezzo di filtri di Edge-detection.

Edge Based Methods



Operatori di Edge- Detection

Prewitt Sobel Canny


Connected Components Algorithms

Tutti i pixel sono visitati a turno, partendo dall’angolo in alto a sinistra e scorrendo lungo tutte le righe, finendo

nell’angolo in basso a destra.

Per ogni pixel non-edge, (i,j), le seguenti condizioni sono verificate:

Se i suoi vicini già visitati – (i-1,,j) e (i, j-1) nel caso di 4-connessi e anche (i-1,j-1) e (i-1,j+1) nel caso degli 8-connessi

– sono tutti pixel di edge, allora viene creata una nuova categoria ed è allocata in (i,j). Alternativamente, se tutti i pixel

vicini appartenenti ad una singola categoria sono non-edge, allora (i,j) viene piazzato nella stessa categoria.

Nel caso in cui un pixel vicino appartenga a due o più categorie, (i,j) viene assegnato ad uno di esse e viene segnato che

le due categorie sono connesse e potrebbero essere considerate un’unica categoria.

Thresholding


Posto un valore soglia di luminanza o media o varianza o altra proprietà in un’immagine, questa strategia suddivide la stessa (attraverso una o più soglie) in due o più tipi di categorie.

La soglia può essere fissata arbitrariamente, o in maniera automatica in base a criteri usualmente statistici.

Può essere globale o locale.


Vantaggi:

Semplicità di Implementazione;

Velocità computazionale;

Svantaggi:

Impreciso su immagini a colori;

Perdita di informazioni di prossimità.


L’immagine A è pura da qualsiasi rumore, come si può notare dal suo istrogramma, l’immagine B presenta

un rumore Gaussiano di media 0 e una deviazione standard di 10 livelli di intensità, l’immagine C presenta

un rumore Gaussiano di media 0 e di 50 livelli di intensità.

Ruolo del rumore


L’immagine A è ben illuminata, come si può notare dal suo istrogramma, l’immagine B presenta un una

illuminazione non uniforme, data dalla moltiplicazione dell’immagine A con una funzione di intensità

variabile, all’immagine C è stato applicato uno Shading Pattern.

Ruolo della luminosità e della riflettanza


UN OTTIMO METODO DI

THRESHOLDING GLOBALE: OTSU

In questa strategia basata sull’istogramma globale, la soglia viene scelta automaticamente, in

maniera tale da minimizzare la varianza intra-classe tra le categorie, massimizzando di fatto la

varianza interclasse.


STRATEGIA OTSU


STRATEGIA OTSU: L’ALGORITMO

1) Consideriamo un’immagine digitale MxN pixel con L distinti livelli di intensità

e sia ni il numero di pixel di intensità i.

Computa l’istogramma normalizzato di un’immagine e denota le componenti con Pi

con i compreso tra 0 e L-1.

2) Computa la somma cumulativa, P1(k),

con k compreso tra 0 e L-1 e quindi la probabilità che un pixel sia assegnato ad una certa classe.



3) Computa la media cumulativa dei valori medi di intensità dei pixel per classe, m(k),

con k compreso tra 0 e L-1.

4) Computa l’intensità media globale, MG



5) Computa la varianza intra-classe σ2B(k),

con σ2B(k) compreso tra 0 e L-1.

6) Ottieni l’istogramma di Otsu, k*, come il valore k per cui σ2B(k) è massimo. Se il massino

non è unico, ottieni k* dalla media dei valori di k corrispondenti alla varianza massima

individuata.



7) Ottieni la misura di separabilità, η*, dalla valutazione di:

con k= k*


OTSU TESTIAMOLO

SU MATLAB!

I metodi Region-based possono esser:

Merging dei pixel;

Splitting delle immagini in regioni;

Split-and-merge in uno schema di ricerca iterativo.

Region Based Methods


Region Merging

Seeded region growing

Metodo automatico o semi-automatico di tipo Merging.

Posizionato un insieme di seeds(dischi bianchi di raggio 3)

Viene applicato l’operatore Prewitt

In bianco in sovraimpressione avremo i seeds e i confini delle categorie,l’algoritmo prende il nome di watershed.

Considerazioni Per dischi di raggio minore di 3 pixel, l’operatore di Prewitt risulta meno sensibile alle fluttuazioni.

L’algoritmo nel suo utilizzo standard è totalmente automatico, attraverso l’applicazione di un filtro di varianza subito

dopo l’equalizzazione dell’istogramma.

- I seeds appariranno nei minimi locali, dopo aver scelto un peso Gaussiano abbastanza grande da assicurarci che

l’output del filtro non abbia più punti di minimo locali



WATERSHED

TESTIAMOLO

SU MATLAB!


Merging and Splitting

Primo Step – Splitting

Viene calcolata la varianza dell’intera immagine, se la varianza eccede in un determinato limite, allora l’immagine viene

suddivisa in 4 quadranti, e così ricorsivamente, fino a che l’intera immagine è composta da un insieme di quadrati di

varia dimensione, tutti sotto il limite varianza.

Considerazioni

-I quadrati sono più piccoli in parti di immagine poco uniformi.

- L’algoritmo richiede un immagine di dimensioni n, con n potenza di 2.


Merging and Splitting

Secondo Step – Merging

Comporta il fondersi dei quadrati con un bordo in comune, provvedendo a non eccedere il limite della varianza. Una

volta che tutte le fusioni sono state completate, il risultato è una segmentazione in cui ogni regione ha una varianza

minore del limite.

TESTIAMO L’ALGORITMO SU MATLAB


Altre ottime tecniche di segmentazione :

- Trasformata di Hough: potente tecnica di ricerca per linee dritte e altre forme parametrizzate.

- Le immagini possono esser spezzate in forme primitive, in maniera del tutto simile alla decomposizione di una frase in

parole, usando metodi sintattici;

- I modelli di forme da cercare può essere rappresentato come template e matchato alle immagini. I template possono

essere rigidi e la mappatura flessibile, o anche il template stesso può essere flessibile.


Grazie per l’ attenzione!


Bibliografia

- Digital Image Processing – R.C. Gonzales, R.E. Woods – Prenctice Hall 2007.

- Segmentation - Chris Glasbey - www.bioss.ac.uk/people/chris/ch4.pdf

Date post:	15-Feb-2019
Category:	Documents
Upload:	vuongkhuong
View:	212 times
Download:	0 times

Corso di laurea magistrale in Informatica Multimedia Prof ... 10... · Questo metodo segmenta con...

Documents