Cercando di capire Quadtree concetto e applicarlo alla memorizzazione di informazioni colorazione di un'immagine

Question

Ho letto tanti articoli, ma nessuno sembra rispondere a questa domanda. O forse sto solo non capendo. Sto tentando di costruire un quadripeso in modo che possa rappresentare un'immagine. I nodi foglia devono contenere pixel, mentre i nodi non fogliati mantengono il valore medio pixel dei suoi figli.

La mia domanda è:

Come funziona che i nodi foglia contenere solo pixel? Perché gli altri nodi non contengono i pixel? E come sappiamo quante volte suddividere il nostro nodo radice originale per rappresentare quell'immagine data? Dobbiamo solo suddividiamo n volte, dove n è l'altezza e la larghezza (per una piazza)?

Edit: Allora, come faccio a tenere traccia dei nodi foglia, quindi so quando aggiungere pixel in quella posizione? In questo momento ho una funzione di aiuto che divide le regioni per me, tenendo traccia di larghezza e altezza.

Answer 1

quadtree funzionano meglio per le immagini quadrati cui dimensione è una potenza di 2 (per esempio, la maggior parte dei tessuti). Non dovresti pensare a ciascun nodo come a un "pixel". Invece, pensalo come un "blocco quadrato di pixel di dimensione 2^k". Nel caso delle foglie finali, k è 0, quindi ogni nodo foglia rappresenta un blocco quadrato di pixel di dimensione 1, cioè un singolo pixel. I nodi interni nell'albero rappresentano sezioni di immagine sempre più grandi.

Answer 2

come funziona che i nodi foglia contengono solo i pixel? Perché gli altri nodi non contengono i pixel?

Questo dipende da cosa stai usando il Quadtree per. È possibile collegare qualsiasi tipo di informazione agli altri nodi, ad es. un puntatore all'angolo in alto a sinistra e alla larghezza/altezza del rettangolo descritto da questo nodo, ma nella maggior parte dei casi non è necessario (o hanno bisogno di cose come i valori medi che è possibile precomporre per accelerare le cose).

E come facciamo a sapere quante volte a suddividere il nostro nodo radice originale per rappresentare quella data immagine?

Con ogni suddivisione, è metà della larghezza e l'altezza di una regione, quindi per un'immagine quadrata di dimensioni n è necessario suddividere log2(n) volte, per un'immagine non quadrata di dimensioni n*m avrete bisogno al massimo max(log2(n), log2(m)) passaggi.

Answer 3

Perché solo i nodi foglia tenere pixel? Chiediti se un nodo non foglia ha un pixel, quindi cosa avrebbero in serbo i suoi figli? Dal momento che non è possibile suddividere un pixel, la risposta è ovviamente nulla - non ci possono essere nodi di questo tipo.

Come facciamo a sapere quante volte a suddividere? Bene, ci sono diversi modi per farlo, ovviamente, a seconda del motivo per cui stai costruendo il quadripeso. In generale, le aree dell'immagine con più entropia - più "dettagli" - dovrebbero essere suddivise di più, mentre le aree di entropia inferiore, "piatte" possono essere divise in meno. Esistono diversi algoritmi per scegliere quando e dove suddividere. Generalmente, confrontano i valori dei pixel all'interno di una regione e si suddividono quando le differenze superano una certa soglia.

Answer 4

Penso che il modo migliore per rispondere alla tua domanda è di rispondere a due domande che non hai chiesto.

• Che cos'è un quadtree?
• Come può essere questo applicato ai sistemi di modellazione della densità erratica ?

Un quad è un albero binario in due dimensioni. Ecco perché ci sono (fino a) quattro bambini per ogni nodo non fogliare. Ciò consente di applicare un indice a un piano proprio come un database utilizza un albero binario o una sua variante per indicizzare una singola dimensione, con le stesse proprietà di rappresentazione dello spazio di fase sparse molto vantaggiose.

L'applicazione di questa compressione dell'immagine e del display progressivo è piuttosto ovvia: se si esegue un tree-walk limitato a una profondità di n, si ottengono 4^n elementi di informazioni sull'immagine che coprono l'intero spazio dell'immagine. Se hai un livello più profondo, ogni pixel si divide in quattro. JPEG2000 funziona in questo modo, se ricordo correttamente. Ho detto "item of picture info" perché non devono essere univoci; gli oggetti potrebbero essere ARGB a 32 bit o qualsiasi altra proprietà (o proprietà) che descriva lo spazio in quel punto.