Drzewo czwórkowe (ang. quadtree) jest strukturą danych będąca drzewem, używaną do podziału dwuwymiarowej przestrzeni na mniejsze części, dzielącą ją na cztery równe ćwiartki. Każda z następnych ćwiartek na cztery kolejne itd. Jest używana na przykład w procesie wykrywania kolizji w dwóch wymiarach. W naszym przypadku wykorzystamy ją do kompresji obrazu.

Algorytm drzewa czwórkowego najwygodniej realizować w postaci rekurencyjnej. Na każdym poziomie rekurencji będziemy w tym przypadku analizować pewien obszar obrazu (RGB lub w skali odcieni szarości) i zwracać dane drzewa opisujące ten obszar. Analizując nasz obszar, możemy się spotkać z kilkoma sytuacjami:

1. W całym obszarze mamy tylko jeden kolor (lub mamy w obszarze tylko jeden piksel) - czyli nasz obszar jest liściem i zwracamy taką informację zgodnie ze sposobem, w jakim reprezentujemy nasze dane.
2. W przeciwnym przypadku dzielimy nasz obszar na 4 pod obszary, które nie zawsze muszą być równe (ze względu na rozmiar obrazu). Dla każdego z tych obszarów wywołujemy naszą rekurencję i zbieramy wyniki jako opis całego poddrzewa opisującego ten fragment. Możemy tu jeszcze spotkać dwa wyjątki: Gdy będziemy mieć tylko jedną kolumnę lub tylko jeden wiersz. Nie mamy wtedy możliwości podzielenia tego obszaru na 4 części — w tym wypadku należy podzielić go na dwie części.

Działanie algorytmu jest identyczne bez względu na ilość warstw koloru. Jedyna różnica pomiędzy obrazem z jedną warstwą, a tym z większą ich ilością polega na tym, że gdy mamy więcej warstw to porównujemy jednoczesną identyczność dwóch zbiorów wartości (czy R równa się R, B równa się B, itd.), a zwracany kolor składa się z kilku wartości.

Kwestię sposobu przechowywania zostawiam do wyboru, kilka z nich przedstawionych zostało w kolejnej sekcji, zaraz za przykładami graficznymi.

Przykład analizy płata — krok po kroku.

Załóżmy, że w pewnym etapie analizujemy poniższą łatę \(I_x\) o rozmiarze \(4x5\):

\[ I_{x}= \begin{bmatrix} 2 & 2 & 2 & 4 & 4 \\ 2 & 2 & 2 & 4 & 0 \\ 2 & 2 & 4 & 4 & 0 \\ 1 & 2 & 2 & 4 & 4 \\ \end{bmatrix} \]

W pierwszym kroku sprawdzamy, czy w naszej łacie występuje tylko jedna wartość (w przypadku RGB sprawdzalibyśmy, czy mamy tylko jeden zestaw wartości). Jak widać, nie jest to prawdą, więc dzielimy ją na 4 części. Sposób podziału jest dowolny i może być unikalny dla waszego algorytmu. W ramach tego przykładu założymy, że po naszym podziale nowe łaty będą wyglądać tak:

\[ I_{x0}=\begin{bmatrix} 2 & 2 & 2 \\ 2 & 2 & 2 \end{bmatrix} \qquad I_{x1}=\begin{bmatrix} 4 & 4\\ 4 & 0 \end{bmatrix} \qquad I_{x2}=\begin{bmatrix} 2 & 2 & 4\\ 1 & 2 & 2 \end{bmatrix} \qquad I_{x3}=\begin{bmatrix} 4 & 0\\ 4 & 4 \end{bmatrix} \]

Na wyjściu naszego algorytmu do poprzedniego kroku musimy zwrócić teraz wartości drzewa: \(Q(I_x)=[Q(I_{x0}),Q(I_{x1}),Q(I_{x2}),Q(I_{x3})]\), gdzie \(Q\) określa nam drzewo na podstawie naszego płatu. Przeanalizujmy sobie teraz kilka poddrzew. Zaczynając od drzewa płatu \(I_{x0}\)

Tak jak w poprzednim przypadku sprawdzamy, czy w naszym płacie występuje tylko jeden kolor. Tym razem jest to prawda, więc mamy tym wypadku liść więc nasze \(Q(I_{x0})=2\), co jest wartością koloru w tym liściu.

Przejdźmy teraz do innego płatu, czyli \(I_{x2}\). Tutaj mamy, więcej niż jeden kolor, więc musimy znowu go podzielić na mniejsze części:

\[ I_{x20}=\begin{bmatrix} 2 & 2 \end{bmatrix} \qquad I_{x21}=\begin{bmatrix} 4 \end{bmatrix} \qquad I_{x22}=\begin{bmatrix} 1 & 2 \end{bmatrix} \qquad I_{x23}=\begin{bmatrix} 2 \end{bmatrix} \]

Jak widać mamy tu aż 3 liście, więc \(Q(I_{x20})=2 \qquad Q(I_{x21})=4 \qquad Q(I_{x23})=2\), natomiast płat \(I_{x22}\) musimy znowu podzielić. Jednak nie jesteśmy w stanie podzielić go na 4 części, ponieważ mamy tylko jeden wiersz, dlatego dzielimy go tylko na dwa płaty, które będą już liśćmi:

\[ I_{x220}=\begin{bmatrix} 1 \end{bmatrix} \qquad I_{x221}=\begin{bmatrix} 2 \end{bmatrix} \]

Na tej podstawie możemy kontynuować pracę nad poprzednimi płatami i całość zapisać wykorzystując odpowiadającą wam formę przechowywania tych informacji w pamięci.

Rodzaje zapisu w pamięci

Drzewo czwórkowe można zapisać w pamięci ja kilka sposobów:

• Jako przestrzenną strukturę danych w formie drzewa — pozwala wtedy ona na szybki i precyzyjny dostęp do konkretnych pikseli w obrazie (nie dołączajcie jednak do tej struktury wewnętrznych metod, bo jej rozmiar będzie się drastycznie rozrastać, ponieważ każda gałąź będzie posiadała kopię tych funkcji),
• Jako listę Łat (Patches) - zawierającą ich wierzchołki oraz kolor, jaki posiadają, dająca najlepszą kompresję i dająca prostą możliwość dalszej kompresji (zwłaszcza w przypadku listy 1D) wymagają jednak zdekodowania całości, aby otrzymać informację an temat konkretnych pikseli,
• Wszelkie rozwiązania pomiędzy tymi dwoma rozwiązaniami przy wykorzystaniu innych struktur danych: np. na listach zagnieżdżonych.