Region Quadtrees in C++

quadtree

(Original image by GoAwayStupidAI).

Below are four C++ implementations of the region quadtree (the kind used for image compression, for example). The different implementations were made in an attempt to optimise construction of quadtrees. (For a tutorial on implementing region quadtrees, see Issue 26 [6.39 MB zip] of Dev.Mag).

  • NaiveQuadtree is the straightforward implementation.
  • AreaSumTableQuadtree uses a summed area table to perform fast calculations of the mean and variance of regions in the data grid.
  • AugmentedAreaSumTableQuadtree is the same, except that the area sum table has an extra row and column of zeros to prevents if-then logic that slows it down and makes it tricky to understand.
  • SimpleQuadtree is the same as AugmentedAreaSumTableQuadtree , except that no distinction is made (at a class level) between different node types.

Continue reading “Region Quadtrees in C++”

Catching Common Image Processing Programming Errors with Generic Unit Tests

crash test dummy

When implementing image algorithms, I am prone to make these mistakes:

  • swapping x and y;
  • working on the wrong channel;
  • making off-by-one errors, especially in window algorithms;
  • making division-by-zero errors;
  • handling borders incorrectly; and
  • handling non-power-of-two sized images incorrectly.

Since these types of errors are prevalent in many image-processing algorithms, it would be useful to develop, once and for all, general tests that will catch these errors quickly for any algorithm.

This post is about such tests.

Continue reading “Catching Common Image Processing Programming Errors with Generic Unit Tests”

Quadtrees

The code below implements some quadtree extensions, as discussed in another Dev.Mag tutorial about quadtrees (see Issue 27). The tutorial covers the following topics:

  • what to consider in choosing whether to use a quadtree or not;
  • tests to help you choose an appropriate threshold;
  • how to handle discrete data; and
  • some modifications to the basic algorithm.

Handling Discrete Data

When it comes to discrete data, the “average” of a number of pixels doesn’t make sense. However, we can give it meaning and still use it to get good approximations of the original data, as illustrated in the images below.

The original grid of discrete data. The grid contains integers from 0 to 4. Every integer is mapped to a colour in this image. (If this grid represented a tile map, every integer would be mapped to a different tile).
Here we allowed floating point numbers in the quadtree. Results of queries into the quadtree are rounded before mapping them to colours.
Here we used the floating point part of queries to bias a randomly selected integer. For example, a result of 1.25 will result in a 75% chance of yielding 2.
Here we use a quadtree with interpolation. The result is rounded before it is mapped.
Here we use a quadtree with interpolation, and use the floating point part of the number to bias a randomly selected tile, as above.

Download

Python Implementation

Download from: http://code-spot.co.za/python-image-code/ (See quadtree.py, quadtree_image.py, and quadtree_demo.py).

Force Field Editor v1.0

pull

Vector fields are used in certain AI and simulation techniques. The tool below allows you to paint a vector field. These files can be saved in XML format, that can easily be loaded into another application.

Continue reading “Force Field Editor v1.0”

Quadtrees

The quadtree is an important 2D data structure and forms the core of many spatial algorithms, including compression, collision detection, and stitching algorithms. Below you can download general purpose quadtree implementations in Java and Python.

The code accompanies the Quadtrees article in Dev.Mag. The tutorial explains how the implement a quadtree that can be use to store 2D data efficiently, lists what considerations there are in real-world applications, and gives some debugging tips.

Channels Compressed Simultaneously

bar bar_c
The original image (by smcgee). The image after being loaded into a quadtree.

Continue reading “Quadtrees”