Quadtree: Esplorazione di strutture dati gerarchiche per l'analisi delle immagini

Di Fouad Sabry

Cos'è Quadtree

Un quadtree è una struttura dati ad albero in cui ciascun nodo interno ha esattamente quattro figli. I quadtree sono l'analogo bidimensionale degli octre e vengono spesso utilizzati per partizionare uno spazio bidimensionale suddividendolo ricorsivamente in quattro quadranti o regioni. I dati associati a una cella fogliare variano in base all'applicazione, ma la cella fogliare rappresenta "un'unità di informazioni spaziali interessanti".

Come trarrai vantaggio

(I) Approfondimenti e convalide sui seguenti argomenti:

Capitolo 1: Quadtree

Capitolo 2: Octree

Capitolo 3: R-albero

Capitolo 4: Albero binario

Capitolo 5: Albero B

Capitolo 6: Albero AVL

Capitolo 7: Albero rosso-nero

Capitolo 8: Albero di ricerca binario

Capitolo 9: Heap binario

Capitolo 10: Albero dei segmenti

(II) Rispondere alle principali domande del pubblico su quadtree.

(III) Esempi del mondo reale per l'utilizzo di quadtree in molti campi.

Per chi è questo libro

Professionisti, studenti universitari e laureati, appassionati, hobbisti e coloro che desiderano andare oltre le conoscenze o le informazioni di base per qualsiasi tipo di Quadtree.

 

• Lingua: Italiano
• Editore: Un Miliardo Di Ben Informato [Italian]
• Data di uscita: 14 mag 2024

Anteprima del libro

Capitolo 1: Quadtree

La struttura dati di un quadtree è un albero in cui ogni nodo interno ha esattamente quattro discendenti. I quadtree sono l'equivalente bidimensionale degli octree e vengono in genere utilizzati per partizionare uno spazio bidimensionale in quattro quadranti o sezioni. Le informazioni associate a una cella foglia variano a seconda dell'applicazione, ma una cella foglia è una unità di informazioni spaziali interessanti.

Le zone suddivise possono avere forme arbitrarie, quadrate o rettangolari. Il 1974 vide la designazione di questa struttura di dati come quadtree da parte di Raphael Finkel e J.L. Bentley. Q-tree è un altro termine per uno schema di partizionamento simile. Tutti i tipi di quadtree hanno determinate caratteristiche:

Suddividono lo spazio in celle flessibili.

Ogni scomparto (o recipiente) ha una capacità massima. Quando viene raggiunta la capacità massima della benna, questa si separa.

La directory dell'albero è conforme alla scomposizione spaziale del quadtree.

Una piramide ad albero (piramide a T) è un albero pieno; ogni nodo della piramide T contiene quattro nodi figli, ad eccezione dei nodi foglia; Tutte le foglie sono allo stesso livello, che corrisponde ai singoli pixel di un'immagine. Analogamente a come un albero binario completo può essere archiviato in modo compatto in un array, i dati della piramide ad albero possono essere archiviati in modo compatto in un array come struttura di dati implicita.

I quadtree possono essere classificati in base ai tipi di dati che rappresentano, ad esempio aree, punti, linee e curve. I quadtree possono anche essere classificati in base al fatto che la forma dell'albero sia indipendente dall'ordine di elaborazione. Le successive sono forme frequenti di quadtree:.

Il quadtree della regione illustra una partizione bidimensionale dello spazio scomponendo la regione in quattro quadranti, sottoquadranti, ecc. uguali, con ogni nodo foglia che trasporta dati relativi a una particolare sottoregione. Ogni nodo dell'albero ha esattamente quattro figli o nessuno (un nodo foglia). Questo metodo di scomposizione (cioè la suddivisione dei sottoquadranti fintanto che ci sono dati rilevanti nel sottoquadrante per i quali si cerca un maggiore affinamento) rende l'altezza dei quadrilateri sensibile e dipendente dalla distribuzione spaziale delle aree interessanti nello spazio da scomporre. L'region quadtree è una variante della struttura dati trie.

Un quadtree di regioni con una profondità di n può essere usato per rappresentare un'immagine composta da 2n × 2n pixel, dove ogni pixel è 0 o 1.

Il nodo radice rappresenta la totalità dell'area dell'immagine.

Se i pixel in una regione non sono completamente 0 o 1, l'area viene considerata non valida, viene segmentata.

Questa è un'applicazione, Ogni nodo foglia rappresenta un blocco di pixel composto interamente da 0 o 1.

Si noti il possibile risparmio di spazio quando questi alberi vengono utilizzati per l'archiviazione delle immagini; Una caratteristica comune delle rappresentazioni visive è la presenza di numerose aree di grandi dimensioni con lo stesso valore di colore in tutto.

Invece di memorizzare un grande array 2D di ogni pixel in un'immagine, viene utilizzato un array più piccolo, un quadtree può acquisire le stesse informazioni a livelli di divisione possibilmente molti più livelli rispetto alle celle con risoluzione pixel.

La risoluzione e le dimensioni dell'albero sono limitate dalle dimensioni in pixel e dall'immagine.

Un quadtree di regione può anche essere utilizzato per rappresentare un campo dati con risoluzione modificabile. Ad esempio, un quadtree può essere utilizzato per registrare le temperature in una regione, con ogni nodo foglia che memorizza la temperatura media per la sottoregione che rappresenta.

Il quadtree di punti

Di seguito è riportato come vengono costruiti i quadtree di punti. Dato il punto successivo da inserire, viene individuata la cella corrispondente e il punto viene aggiunto all'albero. Il nuovo punto viene inserito in modo che la cella che lo contiene sia suddivisa in quadranti dalle linee verticali e orizzontali che lo attraversano. Le celle sono quindi rettangolari, ma non sempre quadrate. Ogni nodo in questi alberi contiene uno dei punti di input.

A causa del fatto che la partizione del piano è determinata dall'ordine di inserimento dei punti, l'altezza dell'albero è sensibile e dipende dall'ordine di inserimento. L'inserimento in un ordine errato può risultare in un albero la cui altezza è proporzionale al numero di punti di input (a quel punto diventa una lista collegata). La pre-elaborazione può essere utilizzata per generare un albero con altezza bilanciata se l'insieme di punti è statico.

Un nodo di un quadtree di punti è simile a un nodo di un albero binario, con la distinzione principale che ha quattro puntatori (uno per ogni quadrante) invece di due (sinistra e destra) come in un albero binario convenzionale. Inoltre, una chiave è in genere divisa in due componenti che fanno riferimento alle coordinate x e y. Di conseguenza, un nodo contiene i seguenti dati:

quattro puntatori: quad['NW'], quad['NE'], quad['SW'] e quad['SE']

punto; che contiene a sua volta:

identificatore; tipicamente indicato come coordinate x, y

un valore, ad esempio un nome

I quadtree della regione puntiforme (PR) assomigliano molto da vicino ai quadtree della regione. La differenza sta nel tipo di dati relativi alle celle salvati. In un quadtree di regione, viene mantenuto un valore che si applica all'intera area di una cella foglia. Tuttavia, le celle di un quadtree PR contengono un elenco di punti che risiedono all'interno di una cella foglia. Come affermato in precedenza, l'altezza degli alberi che impiegano questo approccio di decomposizione dipende dalla distribuzione spaziale dei punti. Analogamente al quadtree di punti, il quadtree PR può avere un'altezza lineare quando viene fornito un set cattivo.

I quadtree di bordo (simili ai quadtree PM) sono impiegati per mantenere le linee anziché i punti. Le celle sono suddivise con una risoluzione estremamente fine per approssimare le curve, con precisione fino a quando non c'è un singolo segmento di linea per cella. I quadtree di spigolo continueranno a dividersi fino a raggiungere il loro massimo livello di decomposizione in prossimità di angoli/vertici. Ciò può portare ad alberi gravemente sbilanciati che negano l'obiettivo dell'indicizzazione.

La mappa poligonale quadtree (o PM Quadtree) è una variante di quadtree utilizzata per contenere gruppi di poligoni potenzialmente degeneri (il che significa che hanno vertici o bordi isolati). Una distinzione significativa tra quadtree PM e quadtree edge è che la cella in esame non è partizionata se i segmenti all'interno della cella si intersecano in corrispondenza di un vertice.

Esistono tre tipi principali di PM Quadtree, che differiscono in base ai dati memorizzati in ciascun nodo nero. I quadtree PM3 possono contenere un numero arbitrario di spigoli non intersecanti e un singolo punto al massimo. I quadtree PM2 sono identici ai quadtree PM3, con l'eccezione che tutti gli spigoli devono terminare nella stessa posizione. I quadtree PM1 sono simili ai quadtree PM2, ma i nodi neri possono includere un punto e i relativi spigoli o solo un insieme di spigoli che condividono un punto, ma un punto e un insieme di spigoli che non contengono il punto non sono consentiti.

Questa sezione fornisce un riassunto di un capitolo del libro di Sariel Har. Di Peled.

Se dovessimo memorizzare ogni nodo corrispondente a una cella suddivisa, la necessità di archiviazione sarebbe proibitiva, potremmo finire per immagazzinare un numero considerevole di nodi vuoti.

Possiamo ridurre le dimensioni di questi alberi radi salvando solo i sottoalberi le cui foglie includono dati interessanti (es.

sottorami significativi).

Possiamo effettivamente ridurre le dimensioni molto di più.

Quando manteniamo solo i sottoalberi essenziali, La procedura di potatura può lasciare lunghi percorsi nell'albero con nodi intermedi di grado due (un collegamento a un genitore e un figlio).

Si scopre che abbiamo solo bisogno di memorizzare il nodo u all'inizio di questo percorso (e associare alcuni metadati ad esso per rappresentare i nodi rimossi) e collegare il sottoalbero radicato alla sua fine a u .

Quando vengono dati punti di input poveri, è comunque possibile che questi alberi compressi abbiano un'altezza lineare.

Sebbene una parte sostanziale dell'albero venga potata durante questa compressione, è ancora possibile la ricerca in tempo logaritmico, l'inserimento e l'eliminazione mediante l'uso di curve di ordine Z.

La curva dell'ordine Z mappa ogni cella dell'intero quadtree (e quindi anche il quadtree compresso) nel O(1) tempo su una linea unidimensionale (e la mappa anche indietro nel O(1) tempo), stabilendo un ordine completo sugli elementi.

Pertanto, possiamo memorizzare il quadtree in una struttura di dati impostata ordinata (in cui memorizziamo i nodi dell'albero).

Dobbiamo formulare un'ipotesi ragionevole prima di continuare: assumiamo che dati due numeri reali {\displaystyle \alpha ,\beta \in [0,1)} espressi come binari, possiamo calcolare nel O(1) tempo l'indice del primo bit in cui differiscono.

Assumiamo anche di poter calcolare nel O(1) tempo il più basso comune antenato di due punti/celle nel quadtree e stabilire il loro relativo ordine Z, e possiamo calcolare la funzione floor nel O(1) tempo.

Con queste premesse, la posizione di un dato punto q (ad es.

determinare la cella che conterrebbe q ), le operazioni di inserimento e cancellazione possono essere eseguite nel O(\log {n}) tempo (ad es.

tempo necessario per eseguire una ricerca all'interno della struttura di dati dell'insieme ordinato sottostante).

Per eseguire una posizione di punto per q (ad es.

trova la cella corrispondente nell'albero compresso):

Trova la cella esistente nell'albero compresso che precede q nell'  ordine Z.

Chiama questa cella v .

Se {\displaystyle q\in v} , restituisce v .

Altrimenti, trova quello che sarebbe stato l'antenato comune più basso del punto q e della cella v in un quadtree non compresso.

Chiama questa cellula antenata u .

Trova la cella esistente nell'albero compresso che precede u nell'  ordine Z e restituiscila.

Senza entrare nello specifico, per fare inserimenti ed eliminazioni, eseguiamo prima un posizionamento puntuale per l'elemento da inserire o eliminare, e poi inserirlo o rimuoverlo. È necessario prestare attenzione a rimodellare l'albero in base alle esigenze aggiungendo o rimuovendo nodi.

Rappresentazione dell'immagine

Bitmap and its compressed quadtree representation

Elaborazione di immagini

Generazione di mesh

Indicizzazione spaziale, ricerche basate su punti e su intervalli

Efficienza di rilevamento delle collisioni bidimensionale

Visualizzare i dati sull'abbattimento del frustum per il terreno

Archiviazione di dati sparsi, ad esempio informazioni sul formato per un foglio di calcolo o calcoli matriciali

Soluzione di campo multidimensionale (fluidodinamica computazionale, elettromagnetismo)

Programma per la simulazione del Gioco della Vita di Conway.

Stima dello stato

I quadtree sono utilizzati anche nell'analisi delle immagini frattali.

Numero massimo di insiemi disgiunti

I quadtree, vale a dire i quadtree regionali, si sono adattati bene alle applicazioni nell'elaborazione delle immagini. Sebbene i quadtree regionali e le procedure di elaborazione delle immagini eseguite su di essi siano ugualmente applicabili alle immagini a colori, limiteremo la nostra discussione ai dati delle immagini binarie.

Un vantaggio dell'impiego di quadtree per l'elaborazione delle immagini è che le operazioni di insiemi, come l'unione e l'intersezione, possono essere eseguite in modo rapido e semplice. Date due immagini binarie, l'unione di immagini (nota anche come sovrapposizione) produce un'immagine in cui un pixel è nero se una delle immagini di input contiene un pixel nero nello stesso punto. In altre parole, un pixel nell'immagine di output è bianco solo se il pixel corrispondente in entrambe le immagini di input è bianco; in caso contrario, è nero. Invece di eseguire l'operazione pixel per pixel, è possibile calcolare in modo efficiente l'unione utilizzando la capacità del quadtree di rappresentare più pixel con un singolo nodo. Ai fini della seguente spiegazione, se un sottoalbero contiene sia pixel bianchi che neri, affermeremo che la radice del sottoalbero è grigia.

L'algoritmo funziona attraversando i due quadtree di input ( T_{1} e T_{2} ) durante la costruzione del quadtree di output T .

Informalmente, l'algoritmo è descritto come segue:.

Si considerino i nodi {\displaystyle v_{1}\in T_{1}} e {\displaystyle v_{2}\in T_{2}} corrispondenti alla stessa regione nelle immagini.

Se v_{1} or v_{2} è nero, il nodo corrispondente viene creato in T ed è colorato di nero.

Se uno è nero e l'altro è grigio, solo uno è nero, sotto il nodo grigio ci sarà un sottoalbero.

Questo sottoalbero non è necessario da esplorare.

Se v_{1}