Fast Algorithm For Min and Max of an Array

[MikeAThon]

Does anyone know a fast algorithm for finding the minimum and maximum values in an array of values?

I am performing morphological image filtering (erosion and dilation) by moving a 5x5 kernel over a much larger array of unsigned char's. At each position of the kernel on the array, I need to find the minimum and maximum values enclosed/covered by the kernel.

I don't need the index where the min or max is located. In other words, I don't need to kow that the minimum value was located at (say) [3][2] in the kernel. I only need the value.

Right now, I do something simple. I simply traverse over the values in the array covered by the current position of the kernel, and compare each value to a max-so-far (or min-so-far) value, storing a new max or min if one is found.

Is there something faster than this?

The name of the algorithm would be enough. If code is provided, C/C++ is preferred.

Thanks,
Mike

[Zachm]

Given an array A of n elements, there is no faster algorithm to find min values in the array than the algorithm you described (complexity O(n)). This can be easily proven, since if one traverses on k elements (k<n), then it is always possible that either the min or max value (or both) are in the remaining n-k non-traversed elements.

However,

I am performing morphological image filtering (erosion and dilation) by moving a 5x5 kernel over a much larger array of unsigned char's

If there are overlaps between the different positions of the kernel, it might be possible to "cache" the min and max values taken from the overlapping part and not test this part again in the next position.

example:
Lets assume the kernel is 2x2 and the 2 dimensional array is

1 2 3 4
5 6 7 8

If the kernel is moved 1 element to the right after each pass then there is an overlap.

1st iteration, the kernel will point at:

1 2
5 6

Using the algorithm you described, 1 is clearly the min and 6 is the max, but in the overlapping part, 2 is the min and 6 is the max - lets store them for now.

2nd iteration, the kernel will point at:

2 3
6 7


At this point, it is only needed to check the values in the right column, since the min and max of the left column we stored in the 1st iteration are already known. 2 operations are saved. If the overlapping was larger than the amount of operations reduced will be higher.

I don't know if this meets your needs, but it's the best that could be done in terms of improving performance, given that the absolute min and max values must be found on each iteration.

Best of luck !

[MikeAThon]

That's very helpful. Thanks. Indeed there is overlap between successive positions of the kernel, so caching the min/max in the overlapped portion will help.

I also found that looking for the min and max simultaneously is faster than looking for the min and max separately: See "find-min-max" under "Algorithms" at http://en.wikibooks.org/wiki/Algorithms/Chapter_4

Mike

[StTwister]

You can do a preprocessing int O(N) time where N is the size of your array, by keeping the min/max of an interval in another array.

So m[i] would be the minimum of the interval 1..i.

Initially m[1] = A[1] (A is the array)
m[i] = min(m[i-1], A[i]), for each i in [2,N]
Then you can find the minimum in any interval [a,b] using the following expression:
max(m[a-1], m[b])
You can expand this idea to 2-dimensional arrays

[MikeAThon]

Thanks. I just came across something called the van Herk algorithm (or, depending on a controversy about priority, it might be called the Gil-Werman algorithm). It guarantees to find the min or max with a constant complexity, i.e., a complexity that is indepndent of the number of values in the kernel. Specifically, it finds min/max with no more than 3 comparisons per output value.

It's a two-step procedure. One description is found at http://www.leptonica.com/grayscale-morphology.html#FAST-IMPLEMENTATION

Mike

PS: Incidentally, since my focus is grayscale morphology, it would have been better if I used the term "structuring element" instead of "kernel".