How to speed this kind of for-loop?

Question

I would like to compute the maximum of translated images along the direction of a given axis. I know about ordfilt2, however I would like to avoid using the Image Processing Toolbox.

So here is the code I have so far:

imInput = imread('tire.tif');
n = 10;

imMax = imInput(:, n:end);
for i = 1:(n-1)
    imMax = max(imMax, imInput(:, i:end-(n-i)));
end

Is it possible to avoid using a for-loop in order to speed the computation up, and, if so, how?

First edit: Using Octave's code for im2col is actually 50% slower.

Second edit: Pre-allocating did not appear to improve the result enough.

sz = [size(imInput,1), size(imInput,2)-n+1];

range_j = 1:size(imInput, 2)-sz(2)+1;
range_i = 1:size(imInput, 1)-sz(1)+1;

B = zeros(prod(sz), length(range_j)*length(range_i));

counter = 0;
for j = range_j % left to right
    for i = range_i % up to bottom
        counter = counter + 1;
        v = imInput(i:i+sz(1)-1, j:j+sz(2)-1);
        B(:, counter) = v(:);            
    end
end

imMax = reshape(max(B, [], 2), sz);

Third edit: I shall show the timings.

Amro · Answer 1 · 2011-06-24T17:00:54.997

3

For what it's worth, here's a vectorized solution using IM2COL function from the Image Processing Toolbox:

imInput = imread('tire.tif');
n = 10;

sz = [size(imInput,1) size(imInput,2)-n+1];
imMax = reshape(max(im2col(imInput, sz, 'sliding'),[],2), sz);
imshow(imMax)

screenshot

You could perhaps write your own version of IM2COL as it simply consists of well crafted indexing, or even look at how Octave implements it.

edited Jun 24 '11 at 17:00

answered Jun 24 '11 at 15:48

Amro

123,847
25
243
454

Thanks, but it is actually 50% slower. :'( – Wok Jun 24 '11 at 16:09
@wok: I wasn't implying that its the best implementation possible... Looking at the code you posted, the matrix `B` is dynamically increasing in size, it obviously would get much faster if you preallocate. – Amro Jun 24 '11 at 16:21
Without seeing the timing results (I doubt the difference to be that significant), I suggest you then stick with your original for-loop. After all, it does have the advantage of minimal space requirement... – Amro Jun 24 '11 at 16:46
Pre-allocation does improve the result, but not that much. I guess a mex-file will be the way to go then. Anyway, thanks for `im2col`, it should be useful. – Wok Jun 24 '11 at 21:19

score 2 · Accepted Answer · edited May 23 '17 at 12:13

2

Check out the answer to this question about doing a rolling median in c. I've successfully made it into a mex function and it is way faster than even ordfilt2. It will take some work to do a max, but I'm sure it's possible.

Rolling median in C - Turlach implementation

edited May 23 '17 at 12:13

Community

1
1

answered Jun 24 '11 at 23:12

Rich C

3,164
6
26
37

How to speed this kind of for-loop?

2 Answers2