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”

Image Restoration Tool

texture

This tool removes lighting artefacts such as shown here.

Requires

  • Windows (tested on Vista)
  • For handling JPEGs, PNGs, etc., you also need ImageMagick (download ImageMagick-6.6.1-3-Q16-windows-dll.exe) This file is about 30 MB :( This dependency will hopefully be removed in the future. Without ImageMagick, the tool still supports BMPs.

Download

WARNING: The tool is very crude, and will only report some errors—in other cases it will just crash. Use only for experimentation; a production version will be posted soon.

image_restore_v1_1.zip (504 KB)

(Includes examples)

Usage

At his stage, only a command line interface is supported. The general syntax is:

image_restore {function} {input file} {output file} {options}*

There are four basic functions

mean {inner_window_width} [outer_window_width]

Restores the mean of the image.

std {inner_window_width} [outer_window_width]

Restores the mean and standard deviation of the image.

minmax {inner_window_width} [outer_window_width]

Restores the minimum and maximum values of the image.

range {inner_window_width} [outer_window_width]

Restores the mean and range (difference between maximum and minimum values) of the image.

They all try to restore some image statistics in the smaller window to that of the larger window. If the outer window width is not supplied, the entire image is used.

These functions all process channels independently. Alternative functions provides means to process based on combined channel values instead, for example, the lightness or value of an image.

The syntax for these functions are as follows:

mean_fn {inner_window_width} [outer_window_width] {method}
std_fn {inner_window_width} [outer_window_width] {method}
minmax_fn {inner_window_width} [outer_window_width] {method}|
range_fn {inner_window_width} [outer_window_width] {method}

The {method} parameter is the method used to combine the channels. The following methods are provided:

  • value normalised Euclidean length of colour vector
  • lightness average of the three channels
  • max maximum component
  • min minimum component
  • mid (average of min and max)
  • med median component
  • red red component
  • green green component
  • blue blue component
  • y709 0.2125*R + 0.7154*G + 0.0721*B (Luminance for contemporary CRT phosphors as standardized by Recccomondation 709—see this Color FAQ for more information).

Examples

image_restore mean input/hair.jpg output/hair_mean_.png 41
image_restore mean input/wood.jpg output/wood_mean_.png 91
image_restore std input/wood.jpg output/wood_std_.png 91
image_restore mean input/paper.jpg output/paper_mean_.png 31
image_restore mean input/grass.jpg output/grass_mean_.png 11
image_restore mean input/color.jpg output/color_mean_1.png 21 41
image_restore mean input/color.jpg output/color_mean_2.png 101
image_restore mean input/paint.jpg output/paint_mean_.png 71
image_restore mean input/metal.jpg output/metal_mean_.png 31
image_restore mean input/metal2.jpg output/metal2_mean_.png 31
image_restore mean input/scene.jpg output/scene_mean.png 201
image_restore mean_fn input/scene.jpg output/scene_mean_lightness.png 21 lightness
image_restore minmax input/pebbles.jpg output/pebbles_minmax.png 41
image_restore std input/machinery.jpg output/machinery_minmax.png 75
image_restore std input/hair.jpg output/hair_std_.png 31
image_restore mean_fn input/color.jpg output/color_mean_lightness_.png 21 lightness
image_restore mean_fn input/color.jpg output/color_mean_value_.png 21 value
image_restore mean hair.jpg hair_mean_.png 41

image_restore std wood.jpg wood_std_.png 91

image_restore mean color.jpg color_mean_1.png 21 41

image_restore range scene.jpg scene_range.png 201

image_restore mean_fn scene.jpg scene_mean_lightness.png 21 lightness

image_restore minmax pebbles.jpg pebbles_minmax.png 41

image_restore std_fn machinery.jpg machinery_std.png 75 100 max

image_restore std hair.jpg hair_std_.png 31

image_restore mean_fn color.jpg color_mean_l_.png 21 lightness

image_restore mean_fn color.jpg color_mean_v_.png 21 value

Usage Guidelines

  • The four basic algorithms work best on images that are essentially one colour (or at least, where you want the output to be roughly the same colour). Thus it will process grass well, but not a grass with red flowers.
  • First see what results you get by using {mean}. If too much detail is lost in the highlights or lowlights, try using {std}. The other too functions are more extreme; {range} centres about the mean, while {minmax} does not.
  • The smaller the inner radius, the more the image will be modified.
  • The bigger the outer radius is, the more homogeneously the image will be processed. Using a relatively small outer radius can improve results on images that are multi-coloured.
  • All algorithms deal better with smooth changes—for example, soft shadows can be removed, but not hard shadows.
  • Multicolour images can sometimes be successfully processed using the _fn versions of the basic algorithms. Of all methods, {value} and {lightness} are the most useful—the others are more for interests sake.

Experimental Tool for Removing Unwanted Artefacts in Textures

texture

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.

Continue reading “Experimental Tool for Removing Unwanted Artefacts in Textures”

Poisson Disk Sampling Example Code

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

Download

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

Getting More out of Seamless Tiles

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

A simple texture algorithm – faster code and more results

header

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!

Continue reading “A simple texture algorithm – faster code and more results”

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

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”