Quadtree Compression

2004-12-01

The most basic way to store images is to store each individual pixel’s color intensity. This method is used in the Bitmap (.bmp extension) format. Storing images this way can take up a tremendous space especially if you have a sequence of images. As you may already know there are more efficient ways to store images, just think of the other image extensions (eg: jpg, png). This utility uses a quad-tree to decrease the stored size of the image.

Application

You can also implement compression if you choose not to store color data for the pixels of the same color. Using this method you won’t have a full quadtree, and you have to store color data at every node (though you hope to have fewer nodes). This way you can store your image without the loss of any information. You can also choose to have a threshold for matching the colors of neighboring pixels. This way you can achieve even smaller size, however you loose information. The importance of the lost information is related to the threshold. You can achieve even better performance if you use some sort of psycho-visual model to evaluate the threshold.

Theory

The quad-tree is a tree data structure, where each node can have four subsequent nodes. The compression is based on the iterative tesselation of the image. You divide each inhomogeneous area to four smaller areas and assign the new areas to four new nodes in the tree. The data will be stored at the leaf nodes (each representing a rectangular area). To setup a full quadtree (a leaf node for each pixel) you need a square shaped image with the dimensions of the power of two (eg 1024x1024). If you do not want to restrict the input you can divide every image into smaller subimages (eg: 16x16 pixels) and apply the quadtree to these subimages. However not every image has a dimension dividable by a power of two. At the edges you can choose to expand the image dimensions to be a multiply of the chosen power of two. To avoid extra storage needs you could choose the color of the expanded area to match the color of the border.

  • No support for image dimensions not dividable by 16.
  • Adjustable compression threshold. No psycho-visual model.
  • Visualizing the difference of the original, and the compressed image
  • Visualizing the internals of the quadtree

quad comparison