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.

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.

Download

minmax_filters.pdf (230 KB)

Table of Contents

1 The Problem

2 Exact Algorithms

2.1 The Naive Algorithm

2.2 The Max-Queue

2.3 Implicit Queue Algorithm

2.4 The Monotonic Wedge Algorithm

3 Approximate Algorithms

3.1 The Power Mean Approximation

3.2 The Power Mean Variant Algorithm

3.3 The Contra-Harmonic Mean Approximation

4 Other Algorithm Concepts

4.1 Separation

4.2 Implementing Minimum Filters

4.3 Windows with Even Diameters

4.4 Filtering a Region of Interest

4.5 Maximum and Minimum Filters for Binary Images

A Image Containers

A.1 Image Class Interface

A.2 Image Loops

A.3 Image Iterators

A.4 Image Access Modifiers

B Fixed-width Deques

C Max-queues

D Summed Area Tables

D.1 Calculating a SAT

D.2 Finding a Sum from a SAT

D.3 Checking for Overflow 50

D.4 Large SATs 53