Algoritmo quad tree e java

[alderaan]

Ho un quesito da porvi.... devo sviluppare un progetto in java....in cui utilizzo l'algoritmo quadtree per manipolare una o più immagini.
Questo tipo di algoritmo non lo conosco.....dove posso trovare della documetazione in merito???

Spero che qualcuno mi risponda al più presto xchè devo iniziare a breve a scrivere il codice.


Ringrazio in anticipo per la collaborazione.

Buona giornata.


Alderaan

[pippo75]

che io mi ricordi, l'algoritmo quad Tree è questo:
prendi un'immagine (quadrata, che viene meglio) e controlli se all'interno dell'immagine tutti i pixel distano tra di loro al massimo di una certa soglia (cioè, la differenza tra il pixel + chiaro e quello + scuro è inferioe a questa soglia);
se questo è il caso, calcola la media dei pixel dell'immagine e sostituisci i valori di tutti i pixel con la nuova media;
Se invece sei al di fuori della soglia, dividi l'immagine in quattro parti uguali (per questo ho detto che sarebbe meglio un'immagine quadrata) e riapplica i confronti fatti in precedenza con le 4 immagini che hai ottenuto.

in questo modo l'immagine processata è composta da un albero a 4 rami, nella cui foglia di ogni ramo ci sta il valore medio dei pixel.

ad esempio, considera questa immagine a scala di grigi in 2 bit:

0 0 3 3
0 0 3 3
2 2 2 1
2 2 0 0

e metti che la soglia sia 0 (cioè, tutti i pixel devono avere lo stesso colore -> minima compressione dell'immagine)
al primo passo dell'algoritmo la soglia è superata -> dividi l'immagine in 4, ottenendo:

1) 0 0      2) 3 3     3) 2 2     4) 2 1
   0 0         3 3        2 2        0 0

le immagini 1), 2), e 3) sono a posto, visto che tutti i pixel sono omogenei, quindi devi solo dividere l'immagine 4

alla fine, la tua mappa dell'immagine sarà:

                      0

00(0)       01(3)           02(2)      03

                      030(2) 031(1) 032(0) 033(0)

tra parentesi sono i valori medi dei pixel, e immagina che sia una rappresentazione ad albero

qua c'è un'immagine che ti può spiegare meglio:
http://www.ncgia.ucsb.edu/education/...s/figure1.html





mandi mandi

[alderaan]

Grazie mille pippo75, la tua risposta è stata milto esauriente. Questo che mi hai scritto è molto chiaro.

Il mio problema di fondo sta nel fatto che non so proprio come partire a livello di codice java. Abbiamo da poco finito il corso all'univerità ma non è mai stato affrontato nessuna tematica di questo genere. Abbiamo affrontato tutta la sintassi del linguaggio, ma niente che riguardasse l'elaborazione delle immagini.

Ti posso chiedere 1 favore??? Ti scrivo sotto alcune specifiche del progetto che devo fare.....non è che potresti damri qualche dritta su come posso iniziare a svilupparlo???

Sono parecchio in crisi, soprattutto per la brevità del tempo a disposizione......e non so proprio come iniziarlo.


Te ne sarei molto grato. Buona giornata


Alderaan


----- SPECIFICHE PROGETTO -----

Si realizzi una applicazione con le seguenti caratteristiche:
· legge in input una immagine a livelli di grigio (in formato
PGM P2) da caricare su una matrice di interi.
le immagini devono avere dimensioni MxM con M multiplo di 2
· genera un Quad-tree per l’intero processo di splitting
· Le suddivisioni delle prime quattro sottoregioni devono
essere eseguite in parallelo da singoli processi che
lavorano ognuno su una delle sottoregioni fino a quando è
applicabile la procedura di Splitting ovvero ci sono regioni
che non soddisfano il criterio di omogeneità
· Visualizzi l’immagine di input e finale (in cui i valori di
ogni regione vengono rimpiazzati dal livello di grigio medio)
· Possa salvare la struttura dati e l’immagine elaborata
(formato PGM P2) su disco.

[alderaan]

Ciao a tutti, dove posso trovare della documentazione molto dettagliata sull'algoritmo quad tree che metta a disposizione anche le regole matematiche che vi sono alla base??????


grazie