segmentazione immagine

[omniaforever]

ragazzuoli, ho un'altra domanda per voi..

sostanzialmente ho una immagine che possiamo trattare benissimo come matrice di valori..l'immagine ha solo 2 colori: il nero ed un altro colore (quindi concettualmente può essere trattata come una immagine in bianco e nero)

vorrei suddividerla in tanti immagini in base a varie regioni...cioè se l'immagine ha gli oggetti rossi(e sfondo nero) e tutti gli oggetti sono TOTALMENTE SEPARATI (ossia non hanno nemmeno un pixel in comune, se ce l'hanno sarà trattato come lo stesso oggetto), ogni oggetto deve essere riportata su una immagine a parte (con solo quell'oggetto rosso e il resto nero)..anche se c'è un pixel rosso isolato teoricamente dovrà costituire una nuova immagine (in quel caso poi io applico un filtro)..

che procedimento algoritmico grezzo basato su matrice potrei usare? se avete una soluzione usando le librerie opencv sarebbe meglio, ma anche in modo grezzo va bene lo stesso(non ho esigenze di computazione veloce, ma semplicemente che l'algoritmo funzioni)

grazie

[WarDuck]

Interessante, ci si potrebbe fare un contest :D, vediamo qualcosa che mi viene di primo acchitto...

Supponiamo tu abbia X oggetti Rossi:

[ R N N R ]
[ N R N N ]
[ N R N N ]

Affinchè un elemento da solo costituisca un immagine non deve avere vicino (a distanza 1) un elemento del colore opposto.

Credo ci sia bisogno di 2 liste, una globale G per tenere traccia degli R visti e una locale L per poter costruire l'immagine.

Coordinate 0,0 (aggiungo in G ed L) -> leggo R:

R N
N R

Tra i vicini c'è un R, lo seguo -> posizione (1,2) (aggiungo in G ed L)

Controllo i vicini di quell'R:
R N N
N R N
N R N

Correzione: vanno calcolati ricorsivamente tutti i vicini ->
abbozzo funzione:


vicini(x, y, Set):
passo base:
non ho vicini R oppure (x,y) già in Set, esco
passo ricorsivo:
per ogni vicino R (x1, y1):
Set.addAll(vicini(x1, y1, Set))


Poiché il vicino 0,0 è nella lista G seguo R in (2,2):

Vicini:

N R N
N R N

Non ho altre posizioni da aggiungere alla lista L (e G).

In base alla lista L creo una nuova immagine:
R in (0,0) (1,2) (2,2)

Svuoto la lista L e a questo punto passo ad analizzare (0,1), se trovo vicini R nelle posizioni che ho visto prima (grazie a G li tengo) li scarto e vado avanti...

Trovi un R in (3,1) che è nuovo, lo aggiungi ad L, controlli i vicini, non ha nessun R, quindi crei una nuova immagine.

E via così credo che ce la potresti fare.

Data la tarda ora non assicuro che l'algoritmo sia infallibile, anzi :asd: .

Sicuramente si può migliorare l'efficienza se tieni traccia di più informazioni, ora però vado a letto :D.

Edit: oh ora che ci sto pensando, va sciolta la questione di quale R scegliere nel caso alla prima mossa ti ritrovassi con due R vicini, tipo:

[R R N R]
[N R N N]
[N R N N ]

Nel primo caso bisognerebbe seguire 0,1 e non 1,2, quindi un ipotesi è quella di seguire il vicino di riga.

Tuttavia proviamo un'altra situazione:

[N R R N]
[R R N N]
[N N N N]

In questo caso è evidente una cosa:

Bisogna avere una lista di tutti i vicini R e visitarli tutti.

R in 0,1 -> vicini rossi (0,3) (1,2) (0,1)

Che a loro volta potrebbero avere altri vicini.

Ricordati che quelli che visiti li metti in L così da:
a) controllare quali hai già visitato
b) consentirti di creare alla fine l'immagine

Credo che questa cosa si possa migliorare, ma ora non ci sto con la testa :D.

[wingman87]

Io però invece di tenere in G i nodi visitati ci terrei tutti i nodi e li toglierei mano a mano che li visito. Penso che renda le cose più facili.

[omniaforever]

mmmm non lo so, non mi convince..cioè i problema è quando un pixel rosso comunica con più di un pixel rosso..io sceglierò una strada, ma poi il pixel che non ho scelto?e la sua strada?cioè mi sa che mi ritroverò tante immagine al posto di una reale..anche se lo hai spiegato dopo, ma non ho capito molto..uno schizzo in pseudo codice? :D

[WarDuck]

Io però invece di tenere in G i nodi visitati ci terrei tutti i nodi e li toglierei mano a mano che li visito. Penso che renda le cose più facili.

Non vorrei sbagliarmi ma intuitivamente dal punto di vista computazionale dovrebbe essere la stessa cosa.

mmmm non lo so, non mi convince..cioè i problema è quando un pixel rosso comunica con più di un pixel rosso..io sceglierò una strada, ma poi il pixel che non ho scelto?e la sua strada?cioè mi sa che mi ritroverò tante immagine al posto di una reale..anche se lo hai spiegato dopo, ma non ho capito molto..uno schizzo in pseudo codice? :D

Si esatto non devi seguirne qualcuno in particolare ma li devi vedere tutti.

Purtroppo nei prossimi giorni ho qualcosa come 3 esami e non posso perderci troppo tempo, sforzati un pochino, fatti venire in mente qualcosa anche a te, lo spunto credo di averlo dato.

Cmq è molto interessante come cosa :D.

[omniaforever]

Non vorrei sbagliarmi ma intuitivamente dal punto di vista computazionale dovrebbe essere la stessa cosa.



Si esatto non devi seguirne qualcuno in particolare ma li devi vedere tutti.

Purtroppo nei prossimi giorni ho qualcosa come 3 esami e non posso perderci troppo tempo, sforzati un pochino, fatti venire in mente qualcosa anche a te, lo spunto credo di averlo dato.

Cmq è molto interessante come cosa :D.

grazie..vediamo cosa riesco a fare :cool:

[wingman87]

Non vorrei sbagliarmi ma intuitivamente dal punto di vista computazionale dovrebbe essere la stessa cosa.

Forse sì, però dal punto di vista implementativo mi sembra più semplice. Comunque non sono sicuro che sia la stessa cosa dal punto di vista computazionale. Bisognerebbe scrivere l'algoritmo per poter confrontare e anch'io oggi non ho tempo per scriverlo (e ieri notte ero stanco).

[WarDuck]

Come procede?

Ho avuto tempo di fare un implementazione e sembra funzionare abbastanza bene.

Questa è la parte centrale:

public static ArrayList<Point> contigui(int x, int y, HashSet<Point> viewed) {
ArrayList<Point> vicini = new ArrayList();

boolean quit = true;

for (int i=-1; i<=1; i++) {
int a = x+i; // coordinata X1 del vicino
if (a>=0 && a<mat.length) {

for (int j=-1; j<=1; j++) {

int b = y+j; // cordinata Y1 del vicino

if (b>=0 && b<mat[0].length && mat[a][b]==1) {

Point v = new Point(a, b);

if (!viewed.contains(v)) {
vicini.add(v);
if (viewed.add(v)) {
quit = false;
}
}
}
}
}
}

if (!quit) {
for (int k=0; k<vicini.size(); k++) {
Point p = vicini.get(k);
vicini.addAll(contigui(p.x, p.y, viewed));
}
}

return vicini;
}

Tramite questa funzione sostanzialmente trovo tutti gli 1 contigui alla posizione X,Y.

In pratica:


mi trovo tutti i vicini di (X,Y)
per ognuno di essi, chiamiamoli (Xv, Yv) mi calcolo la funzione contigui(Xv, Yv).


La ricorsione termina quando non aggiungo più nuovi vicini.

Una piccola nota su come genero i vicini del generico punto P(X,Y):

a) Definiamo vicino V di coordinate (A,B) l'elemento da cui P dista 1.
b) Definiamo Delta la varazione di una singola coordinata (es. X+1, delta X = 1).

Ora appare abbastanza evidente che i possibili Delta sulle coordinate saranno [-1, 1].

Per cui con quei due cicli for mi genero tutti i delta calcolandomi le coordinate del vicino V(A,B):

A=X+I
B=Y+J

con I,J nell'intervallo [-1, 1].

Notare che includo anche lo 0 per poter fissare una data riga o una data colonna ed includere tutti i possibili elementi vicini.

Ovviamente le coordinate generate con questo sistema devono essere valide (devono ricadere all'interno della matrice), per questo noterete un po' di if atti a fare i dovuti controlli.

Alla lista aggiungo solo quelli marcati con un 1, ovvero del colore che mi interessa.

Poi il gioco prosegue facilmente chiamando la funzione contigua(X,Y) su ogni elemento della matrice, appena ho un altro po' di tempo vedo se c'è qualche trucco per ottimizzare il tutto (penso ci si possa ragionare su).

[omniaforever]

Come procede?

Ho avuto tempo di fare un implementazione e sembra funzionare abbastanza bene.

Questa è la parte centrale:

public static ArrayList<Point> contigui(int x, int y, HashSet<Point> viewed) {
ArrayList<Point> vicini = new ArrayList();

boolean quit = true;

for (int i=-1; i<=1; i++) {
int a = x+i; // coordinata X1 del vicino
if (a>=0 && a<mat.length) {

for (int j=-1; j<=1; j++) {

int b = y+j; // cordinata Y1 del vicino

if (b>=0 && b<mat[0].length && mat[a][b]==1) {

Point v = new Point(a, b);

if (!viewed.contains(v)) {
vicini.add(v);
if (viewed.add(v)) {
quit = false;
}
}
}
}
}
}

if (!quit) {
for (int k=0; k<vicini.size(); k++) {
Point p = vicini.get(k);
vicini.addAll(contigui(p.x, p.y, viewed));
}
}

return vicini;
}

Tramite questa funzione sostanzialmente trovo tutti gli 1 contigui alla posizione X,Y.

In pratica:


mi trovo tutti i vicini di (X,Y)
per ognuno di essi, chiamiamoli (Xv, Yv) mi calcolo la funzione contigui(Xv, Yv).


La ricorsione termina quando non aggiungo più nuovi vicini.

Una piccola nota su come genero i vicini del generico punto P(X,Y):

a) Definiamo vicino V di coordinate (A,B) l'elemento da cui P dista 1.
b) Definiamo Delta la varazione di una singola coordinata (es. X+1, delta X = 1).

Ora appare abbastanza evidente che i possibili Delta sulle coordinate saranno [-1, 1].

Per cui con quei due cicli for mi genero tutti i delta calcolandomi le coordinate del vicino V(A,B):

A=X+I
B=Y+J

con I,J nell'intervallo [-1, 1].

Notare che includo anche lo 0 per poter fissare una data riga o una data colonna ed includere tutti i possibili elementi vicini.

Ovviamente le coordinate generate con questo sistema devono essere valide (devono ricadere all'interno della matrice), per questo noterete un po' di if atti a fare i dovuti controlli.

Alla lista aggiungo solo quelli marcati con un 1, ovvero del colore che mi interessa.

Poi il gioco prosegue facilmente chiamando la funzione contigua(X,Y) su ogni elemento della matrice, appena ho un altro po' di tempo vedo se c'è qualche trucco per ottimizzare il tutto (penso ci si possa ragionare su).

grazie tantissime..in realtà mi sto muovendo utilizzando le opencv che dovrebbero avere funzioni abbastanza specifiche per queste operazioni, ma ovviamente entro questo weekend testerò la tua soluzione e se computazionalmente parlando siamo messi meglio rispetto all'uso delle opencv userò la tua soluzione manuale..in questi giorni dò un'occhiata meglio per capire meglio..in ogni caso ti ringrazio infinitamente della tua cortesia ;)

non ho capito alcune cose:

1-quando poi ciclo tutta l'immagine col coppio ciclo for in quanto matrice e richiamo contigua(X,Y, viewed), in quel viewed che metto?

2-dato che ad esempio partendo dal pixel (0,0) e richiamando la continua(x,y), mi troverò la lista di pixel concatenati a partire da (0,0)..poi mi quando nel ciclo parto da (0,1) ma se ad esempio (0,1) è contiguo a (0,0) mi ritroverò la stessa lista di pixel concatenati di prima...in sostanza dovrei evitare anche i doppioni

cioè parto da questa immagine:
http://img411.imageshack.us/img411/8113/aa4e.jpg

e dovrò ottenere questa
http://img175.imageshack.us/img175/1261/aa2ix.jpg

e questa
http://img685.imageshack.us/img685/5679/aa3s.jpg

[WarDuck]

viewed è un insieme esterno che rimane durante tutta la scansione della matrice, per cui i dati raccolti da una passata vengono utilizzati anche per la successiva.

viewed contiene sostanzialmente tutte le posizioni in cui sono presenti 1.

Nel main faccio questo:

ArrayList<ArrayList<Point>> images = new ArrayList();

HashSet<Point> viewed = new HashSet();

for (int i=0; i<mat.length; i++) {
for (int j=0; j<mat[0].length; j++) {

ArrayList<Point> image = contigui(i, j, viewed);

if (!image.isEmpty())
images.add(image);
}
}

L'immagine ovviamente è un insieme di punti.

Come vedi fuori dal ciclo dichiaro sia l'insieme delle immagini generate sia viewed.

Nel caso non lo sapessi, ma penso di si, in Java quando passi un oggetto viene passato il riferimento (quindi viewed può essere visto come una variabile globale).

Avrei in effetti anche potuto dichiararlo come attributo statico di classe, evitandomi il passaggio per riferimento.

Per altro l'utilizzo di un HashSet già di per se non permette duplicati (qual ora tenti di inserire un elemento già nell'insieme lui semplicemente lo ignora) ;).

[omniaforever]

è uguale usare List? oppure posso usare ArrayList ma devo togliere la specializzazione a <Point>..fa lo stesso? dato che arraylist<point> in c# mi dà errore



quindi tu dici che quando fai
for (int i=0; i<mat.length; i++) {
for (int j=0; j<mat[0].length; j++) {

ArrayList<Point> image = contigui(i, j, viewed);


if (!image.isEmpty())
images.add(image);
}
}
significa che se il pixel (x,y) è stato già concatenato ad un pixel che è stato esaminato in precedenza, contigui() nella lista relativa ai contigui di (x,y) non mi restituirà nessun pixel giusto?

andando a fare il ciclo for (int i = -1; i <= 1; i++)
non darà errore in esecuzione quando siamo nei pixel di bordo dell'immagine?

[WarDuck]

è uguale usare List? oppure posso usare ArrayList ma devo togliere la specializzazione a <Point>..fa lo stesso? dato che arraylist<point> in c# mi dà errore


Si puoi usare anche una semplice List, tuttavia ogni volta devi riscansionarla per assicurarti che l'elemento non sia già presente, perdendo di efficienza.

Cmq la classe HashSet è presente anche in C#.

Point è una classe Java per gestire le coordinate dei punti 2D, ho usato quella per evitare di rifarmi la classe, cmq la puoi fare tranquillamente anche tu, anzi se usi C# puoi fare direttamente una struttura (più leggera) con i campi int x, int y.


quindi tu dici che quando fai
for (int i=0; i<mat.length; i++) {
for (int j=0; j<mat[0].length; j++) {

ArrayList<Point> image = contigui(i, j, viewed);


if (!image.isEmpty())
images.add(image);
}
}

significa che se il pixel (x,y) è stato già concatenato ad un pixel che è stato esaminato in precedenza, contigui() nella lista relativa ai contigui di (x,y) non mi restituirà nessun pixel giusto?


Lui scansiona tutti i vicini alla ricerca di R (valore 1), tuttavia se l'R è già stato visto evita di controllare i suoi vicini.

Questo aspetto credo che potrebbe essere migliorato in qualche modo, domani gli darò un'occhiata.


andando a fare il ciclo for (int i = -1; i <= 1; i++)
non darà errore in esecuzione quando siamo nei pixel di bordo dell'immagine?

Premetto che non ho scritto molto elegantemente il codice :p, cmq la risposta è NO poiché effettuo il controllo più avanti con gli altri if per valutare se le coordinate a e b siano valide, ti riporto l'esempio:

for (int i=-1; i<=1; i++) {
int a = x+i; // coordinata X1 del vicino
if (a>=0 && a<mat.length) {
...