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”

Simple, Fast* Approximate Minimum / Maximum Filters

minmax

*Fast = not toooo slow…

For the image restoration tool I had to implement min and max filters (also erosion and dilation—in this case with a square structuring element). Implementing these efficiently is not so easy. The naive approach is to simply check all the pixels in the window, and select the maximum or minimum value. This algorithm’s run time is quadratic in the window width, which can be a bit slow for the bigger windows that I am interested in. There are some very efficient algorithms available, but they are quite complicated to implement properly (some require esoteric data structures, for example monotonic wedges (PDF)), and many are not suitable for floating point images.

So I came up with this approximation scheme. It uses some expensive floating point operations, but its run time is constant in the window width.

Continue reading “Simple, Fast* Approximate Minimum / Maximum Filters”

Cellular Automata for Simulation in Games

header

A cellular automata system is one of the best demonstrations of emergence. If you do not know what cellular automata (CA) is, then you should go download Conway’s Game of Life immediately:

Conway’s Game of Life

Essentially, CA is a collection of state machines, updated in discrete time intervals. The next state of one of these depends on the current state as well as the states of neighbours. Usually, the state machines correspond to cells in a grid, and the neighbours of a cell are the cells connected to that cell. For a more detailed explanation, see the Wikipedia article.

Even simple update rules can lead to interesting behaviour: patterns that cannot be predicted from the rules except by running them. With suitable rules, CA can simulate many systems:

  • Natural phenomena: weather, fire, plant growth, migration patterns, spread of disease.
  • Socio-economic phenomena: urbanisation, segregation, construction and property development, traffic, spread of news.

Continue reading “Cellular Automata for Simulation in Games”