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.
The document is somewhat weird: it is very detailed for a “simple” image algorithm (it is more than 50 pages!). It does have several tips that applies to implementation of other image processing algorithms. It also has, what I believe to be, a very clear description of the Monotonic Wedge Algorithm, with code that reflects the explanation in text closely. (I had trouble understanding the algorithm from the original journal publication. And the authors provide code that was even further optimised and thus less clear to follow).
I intended to give some performance analysis and results, but other activities has robbed me of any free time. Perhaps later.
Also, the code has been edited for readability, and hence, might contain typos that were introduced in the process. If you spot any, please let me know.
Table of Contents
1 The Problem2 Exact Algorithms2.1 The Naive Algorithm2.2 The Max-Queue2.3 Implicit Queue Algorithm2.4 The Monotonic Wedge Algorithm3 Approximate Algorithms3.1 The Power Mean Approximation3.2 The Power Mean Variant Algorithm3.3 The Contra-Harmonic Mean Approximation4 Other Algorithm Concepts4.1 Separation4.2 Implementing Minimum Filters4.3 Windows with Even Diameters4.4 Filtering a Region of Interest4.5 Maximum and Minimum Filters for Binary ImagesA Image ContainersA.1 Image Class InterfaceA.2 Image LoopsA.3 Image IteratorsA.4 Image Access ModifiersB Fixed-width DequesC Max-queuesD Summed Area TablesD.1 Calculating a SATD.2 Finding a Sum from a SATD.3 Checking for Overflow 50D.4 Large SATs 53