Quadtree Encoding (a Simple Compression Algorithm)

The quadtree encoding allows us to describe a $2^N \times 2^N$ black and white image as a sequence of bits (0 and 1). Those sequences are to be read from left to right like this:
the first bit deals with the complete $2^N \times 2^N$ region;
“0” denotes a split:
the current $2^n \times 2^n$ region is divided into $4$ sub-regions of dimension $2^{n – 1} \times 2^{n – 1}$,
the next bits contains the description of the top left, top right, bottom left and bottom right sub-regions – in that order;
“10” indicates that the current region contains only black pixels;
“11” indicates that the current region contains only white pixels.Consider the following $4 \times 4$ image (colored marks denote places where a split can occur):

This image can be described by several sequences, for example :
“001010101001011111011010101010”, of length $30$, or
“0100101111101110”, of length $16$, which is the minimal sequence for this image.
For a positive integer $N$, define $D_N$ as the $2^N \times 2^N$ image with the following coloring scheme:
the pixel with coordinates $x = 0, y = 0$ corresponds to the bottom left pixel,
if $(x – 2^{N – 1})^2 + (y – 2^{N – 1})^2 \le 2^{2N – 2}$ then the pixel is black,
otherwise the pixel is white.What is the length of the minimal sequence describing $D_{24}$?

This calculation requires knowledge of the image structure and properties of quadtree encoding. Since this is a quadtree encoding problem, the image is split into 4 quadrants: top left, top right, bottom left and bottom right. If a quadrant contains all black or all white, it can be encoded with “10” or “11”, respectively. If there are both black and white pixels in a quadrant, it must be split further and it is encoded with “0”.

The given image D_{24} is a circle contained in a square (a pixel with coordinates x = 0, y = 0 corresponds to the bottom left pixel). This image’s equivalent influence on each quadrant, giving us symmetry between all four quadrants. The image is split into quadrants and then each quadrant is split further whenever there are both black and white pixels in it.

Because of the symmetry, we can calculate the minimal sequence for one quadrant and multiply it by 4 to get the minimal sequence for the whole image.

For any $2^N \times 2^N$ image, there’s always an initial “0” denoting the split. Then, we are left with four $2^{N-1} \times 2^{N-1}$ quadrants.

The sequence structure for each quadrant is like the following:

1. outermost ring – this ultimately contains both black and white pixels, so we need to split and depict each quadrant – represented as “0”

2. next ring, only black pixels since it is inside the circle – represented as “10”

3. innermost part – wholly within the circle, black pixels – represented as “10”

Counting these up, to describe each quadrant of the $2^N \times 2^N$ region:

– Outer ring : $2^{N-1} – 1$ times “0”,
– Inner Black Circle : $2^{N-1} – 1$ time “10”,
– Whole Black Circle : 1 time “10”.

Total of $3 * (2^{N-1} – 1) + 1$ bits.

For the whole $2^N \times 2^N$ region, the initial “0” plus four-quadrant each require $3 * (2^{N-1} – 1) + 1$ bits, giving us the minimal sequence length $4 * [3 * (2^{N-1} – 1) + 1] + 1$ bits.

Substituting $N=24$ into the above formula, the length of minimal sequence describing $D_{24}$ is $4 * [3 * (2^{24-1} – 1) + 1] + 1 = 150994949$.

So, the minimal sequence describing $D_{24}$ has a length of 150994949 bits.

More Answers: