I'm trying to apply a sliding window minimum and maximum filter to an image of a certain window size. Actually, I'm trying to find the optimum window size for it. But I really haven't gotten the hang of it. I presume that I should be using blockproc
to implement the sliding window, but not really sure how to find the maximum and minimum filter. As to the implementation itself, should I use loops to slide the window across the entire area of the image ?
2 Answers
ordfilt2 will do this for you:
N=5;
filtered_img = ordfilt2(img, 1, true(N));
for minimum and
filtered_img = ordfilt2(img, N*N, true(N));
for the maximum. You can also use imdilate and imerode to perform maximum and minimum filters.
-
$\begingroup$ The N is for the window size ? The above commands would mean a 5x5 window size ? $\endgroup$– GamingXSep 29, 2012 at 0:36
-
$\begingroup$ Yes, N is the size of the window in one dimension. $\endgroup$– Jason BSep 29, 2012 at 4:57
-
$\begingroup$ How would I pad the borders with 1 for the minimum filter and 0 for the maximum filter ? $\endgroup$– GamingXSep 29, 2012 at 15:57
-
$\begingroup$ Basically, I am attempting to correct an image with uneven illumination by applying a sliding window minimum filter on the image and then finding the illumination or shading function, by applying sliding window maximum filter on on the output of the minimum filter. Later, I'm trying to find the 'perfect image' by dividing the original image with the illumination function. $\endgroup$– GamingXSep 29, 2012 at 16:46
old question, but here is an answer in C (not MATLAB)
an efficient sliding maximum algorithm that has computational cost that is $O(\log_2(L))$. in the code below below window_length
is $L$.
algorithm comes from:
Brookes: "Algorithms for Max and Min Filters with Improved Worst-Case Performance" IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS—II: ANALOG AND DIGITAL SIGNAL PROCESSING, VOL. 47, NO. 9, SEPTEMBER 2000
C code is mine.
#define A_REALLY_LARGE_NUMBER 3.40e38
typedef struct
{
unsigned long window_length; // array_size/2 < window_length <= array_size
unsigned long array_size; // must be power of 2 for this simple implementation
unsigned long input_index; // the actual sample placement is at (array_size + input_index);
float* big_array_base; // the big array is malloc() separately and is actually twice array_size;
} search_tree_array_data;
void initSearchArray(unsigned long window_length, search_tree_array_data* array_data)
{
array_data->window_length = window_length;
array_data->array_size = 1;
window_length--;
while (window_length > 0)
{
array_data->array_size <<= 1;
window_length >>= 1;
}
// array_size is a power of 2 such that
// window_length <= array_size < 2*window_length
// array_size = 2^ceil(log2(window_length)) = 2^(1+floor(log2(window_length-1)))
array_data->input_index = 0;
array_data->big_array_base = (float*)malloc(sizeof(float)*2*array_data->array_size); // dunno what to do if malloc() fails.
for (unsigned long n=0; n<2*array_data->array_size; n++)
{
array_data->big_array_base[n] = -A_REALLY_LARGE_NUMBER; // init array.
} // array_base[0] is never used.
}
/*
* findMaxSample(value, &array_data) will place "value" into the circular
* buffer in the latter half of the array pointed to by array_data->big_array_base .
* it will then compare the value in "value" to its "sibling" value, takes the
* greater of the two and then pops up one generation to the parent node where
* this parent also has a sibling and repeats the process. since the other parent
* nodes already have the max value of the two child nodes, when getting to the
* top-level parent node, this node will have the maximum value of all the samples
* in the big_array. the number of iterations of this loop is ceil(log2(window_length)).
*/
float findMaxSample(float value, search_tree_array_data* array_data)
{
register float* big_array = array_data->big_array_base;
register unsigned long index = array_data->array_size + array_data->input_index; // our main buffer is in the latter half of the big array.
while (index > 1UL)
{
big_array[index] = value;
register float sibling_value = big_array[index ^ 1UL]; // toggle LSB, the upper bits of the sibling address are the same.
if (value < sibling_value)
{
value = sibling_value; // use maximum of the two values
}
index >>= 1; // parent address is index/2 (drop remainder or "sibling bit")
}
array_data->input_index++;
if (array_data->input_index >= array_data->window_length)
{
array_data->input_index = 0;
}
return value;
}
-
$\begingroup$ I’m surprised that this was published in 2000, given that van Herk published an O(1) algorithm (3 comparisons per output pixel, independent of the window length) in 1992, and Gil and Werman published (independently) the same idea in 1993. Maybe this paper has a specific application where van Herk is not applicable? [PDF](pdf-s3.xuebalib.com:1262/26eDyOxu65M.pdf). $\endgroup$ Dec 5, 2021 at 15:25
-
$\begingroup$ Thanks for the link @CrisLuengo . I cannot believe that it can be as general as the Brooks alg and be $O(1)$ and not require more computation for longer windows. I am certain, that for a totally general real signal and to always find the correct max (or min) value, that it must cost $O\big(\log(L)\big)$ where $L$ is the window length. At least that is better than $O(L)$. But I am reading this Herk paper now. $\endgroup$ Dec 5, 2021 at 19:15