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.

Continue reading “2D Minimum and Maximum Filters: Algorithms and Implementation Issues”

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++”

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”