## 2D Minimum and Maximum Filters: Algorithms and Implementation Issues

A while back I needed to implement fast minimum and maximum filters for images. I devised (what I thought was) a clever approximation scheme where the execution time is not dependent on the window size of the filter. But the method had some issues, and I looked at some other algorithms. In retrospect, the method I used seems foolish. At the time, I did not realise the obvious: a 1D filter could be applied to first the rows, and then the columns of an image, which makes the slow algorithm faster, or allows you to use one of the many published fast 1D algorithms.

I wanted to write down my gained knowledge, and started to work on a blog post. But soon it became quite long, so I decided to put it into a PDF document instead. You can download it below.

## Region Quadtrees in C++

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.

## Catching Common Image Processing Programming Errors with Generic Unit Tests

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.

## Simple, Fast* Approximate Minimum / Maximum Filters

*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.

## Experimental Tool for Removing Unwanted Artefacts in Textures

Many textures used for 3D art start from photographs. Ideally, such textures should be uniformly lit so that the texture does not interfere with the lighting applied by the 3D software. Often, lighting artefacts must be removed by hand. This can be tedious and time consuming.

The tool provided here aims to automate this process. It is still in an experimental phase, so it is very crude. Below you can see some of the before and after pictures.

## Poisson Disk Sampling Example Code

I decided to put the Poisson disk sampling code here for download since the site that hosted it is down. The code accompanies the tutorial on Dev.Mag: Poisson Disk Sampling.

 poisson_disk_java.zip (184 KB) poisson_disk_python.zip (912 KB) poisson_disk_ruby.zip (59 KB)

## Getting More out of Seamless Tiles

I wrote an article for Dev.Mag covering some techniques for working with seamless tile sets such as making blend tiles, getting more variety with procedural colour  manipulation, tile placement strategies, and so on.

Check it out!

The Python Image Code has also been updated with some of the algorithms explained in the article.

## Faster Code

A while back I wrote about a simple texture algorithm that I have been exploring. The Python implementation was very slow – so much, that I decided to implement it in C++ to see what performance gain I would get. Surprisingly, the C++ version is about 100 faster, if not more. I expected a decent increase, but what once took several hours can now be done in a minute!

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.