Extract submatrix using a sliding window

Hi all,

I have a matrix A = [1,2,3;

4,5,6;

7,8,9;

10,11,12;

13,14,15];

I want to derive a second matrix, called A1, which has all the submatrices obtained through a sliding Window W = 2 and a shift delta = 1. I mean, starting from the A above I want to obtain something like:

A1 = [1,2,3;

4,5,6;

4,5,6;

7,8,9;

7,8,9;

10,11,12;

10,11,12;

13,14,15]

I need to do this procedure for a very large matrix A (200.000 rows x 300 columns), is there a way you can suggest me with a good response time from matlab?

Thanks

[Guillaume]

I do not understand how A1 matches your description. With a window of size 2, I'd expect 2x2 submatrices. Maybe,

A1 = cat(3, [1 2; 4 5], [2 3; 5 6], [4 5;7 8], etc.)

but certainly not the A1 you describe.

With a 200,000 x 300 matrix, have you calculated how many submatrices this would generate and how much memory that would require? Do you actually need to store these submatrices. You'll just be storing extremely redundant information.

[Gianluca Ligresti]

Starting from A I need to take the first two rows and make some processing over them, then on the next iteration I have to shift of 1, so I take the second and third row of A and make the same processing and so on, till I end the rows of A.

I tried to use a for loop that considers only two rows for each time but, obviously, from the fact that my Matrix has an high number of rows my Matlab need lots of minutes.

My problem is a time problem, because with the matrix A of my example I'm able to extract, step by step, the two rows I need.

The processing for each couple of row takes up less than 1 second, but I need to compare what I obtain with a window W = 2 and with a window W = 1000. So, when W = 1000 I take at the first iteration the rows from 1 to 1000, i make my processing, then the rows from 2 to 1001, i make my processing and so forth...but with a for loop, to do this with 200.000 rows, I never finish at all.

Answer 1

[Guillaume]

I don't see how replicating the rows is going to save you time. You're just using more memory to store the same information. However, if it's what you want to do, your A1 is easily obtained, at least for your window of height 2 with shift of 1:

A1 = repelem(A, 2, 1);  %replicate each row twice, don't replicate columns
A1 = A1(2:end-1)

For a larger window height (but still shift of 1), you can get your matrix with im2col which requires the image processing toolbox:

A1 = reshape(im2col(A.', [size(A, 2), windowheight]), size(A, 2), []).'

However, this would probably take more time than your existing loop.

For a shift > 1, you probably need to use a loop, which would take as much time as your existing loop.

[Gianluca Ligresti]

Thank you very much,

I need to compare the results I obtain also using a shift = 10, in that case how should my code look like?

[Guillaume]

how should my code look like?

more or less like the loop you've already written or using arrayfun:

A1 = arrayfun(@(startrow) A(startrow:startrow+windowheight-1, :), 1:shift:size(A, 1)-windowheight+1, 'UniformOutput', false);
A1 = vertcat(A1{:})

[Gianluca Ligresti]

Your solution is very good with not too big matrices. As you said before, if I apply the code you suggest to my 200.000x300 matrix then there is an obvious out of memory.

Starting from my A I could also extract the first submatrix, do the processing, then go to the next submatrix (overwriting the first one, so I don't have memory problems) and do the processing and so on. But can I do this ONLY with a for loop! And if, for instance, my W = 5000 and shift = 10 Matlab never finishes to work.

So did my professor ask me for something impossible to do in acceptable times? :D

[Guillaume]

Well, as I keep saying, I don't see the point of that precomputation step. Unless the processing itself can be carried out without a loop, it's not going to give you any speed advantage. If anything you may be doing twice as much wore and you're certainly storing redundant information. Even Jos' method of precomputing the indices is not going to make any significant difference. The expensive part of your loop is the processing, not the calculation of the submatrices.

So, I think you're focusing on the wrong part of the problem. What may needs optimising is that computation you do on the submatrices.

[Jos (10584)]

+1 Guillaume

Answer 2

[Jos (10584)]

My advise: create the proper index vector from windowsize and shift and use that to extract the rows

A = [1 2 3; 4 5 6 ; 7 8 9 ; 10 11 12 ; 13 14 15]
windowsize = 3
shift = 2
N = size(A,1) 
ix = (1:shift:N) + (0:windowsize-1).'
ix = ix(ix<=N)
B = A(ix,:)

[Jos (10584)]

for N = 1e5, windowsize = 5000 and shift = 10, this takes a second on my old mac :-D