How can I extract n elements from each m-by-m window of a matrix without using loops in MATLAB?

Question

I have a matrix and 2 parameters. The first parameter n is the number of elements to be selected. The second is the window size m.

I want to select n number of elements from every m-by-m window from the matrix. As a result we will have a p-by-q cell array where p is matrix_height/m and q is matrix_width/m.

Each element of the cell array contains the n greatest numbers from the corresponding window. It does not necessarily need to be a cell array, it can be anything that will store the necessary data.

You could look at |blockproc| mathworks.com/help/toolbox/images/ref/blockproc.html — Ashish Uthama

gnovice gnovice · Accepted Answer · 2011-03-15T16:35:47

One way to do this is by first finding all the unique m-by-m submatrices of your matrix using the function IM2COL, then sorting each column in descending order using the function SORT, and finally extracting the top n rows. If your initial matrix is A and your output matrix is B, this is what it would look like:

B = sort(im2col(A,[m m],'distinct'),1,'descend');
B = B(1:n,:);  %# Get the top n values

Note that B will be an n-by-m^2 matrix. If you want to turn this into a p-by-q cell array, you can do this using the functions NUM2CELL and RESHAPE:

nBlocks = ceil(size(A)./m);  %# The number of blocks in each dimension
B = reshape(num2cell(B,1),nBlocks(1),nBlocks(2));

EDIT:

If you also want to get the indices of each value with respect to the input matrix A, that is a bit more complicated. You can do it by getting the second output from SORT, which in this case will be the linear indices of the values within each m-by-m submatrix. You can convert these to subscripts using the function IND2SUB, then shift the row and column indices to account for the position of each m-by-m block:

[B,index] = sort(im2col(A,[m m],'distinct'),1,'descend');
B = B(1:n,:);                  %# Get the top n values
index = index(1:n,:);          %# Get the top n values
[r,c] = ind2sub([m m],index);  %# Convert linear indices to subscripts
nBlocks = size(A)./m;          %# The number of blocks in each dimension
r = r+repmat(0:m:(nBlocks(1)-1)*m,n,nBlocks(2));      %# Shift the row indices
c = c+kron(0:m:(nBlocks(2)-1)*m,ones(n,nBlocks(1)));  %# Shift the column indices

And now you can collect the row indices, column indices, and values together into a cell array using the functions MAT2CELL and RESHAPE:

B = mat2cell([r(:) c(:) B(:)],n.*ones(1,size(B,2)));
B = reshape(B,nBlocks(1),nBlocks(2));

Alternatively, you can create a structure array instead of a cell array using the functions NUM2CELL, STRUCT, and RESHAPE:

B = struct('rowIndices',num2cell(r,1),...
           'colIndices',num2cell(c,1),...
           'values',num2cell(B,1));
B = reshape(B,nBlocks(1),nBlocks(2));

NOTE:

The function IM2COL will pad partial blocks with zeroes in the event that a dimension of A is not an even multiple of m. If any of this zero-padding appears in the top n values for a block, one or both of the corresponding row and column indices will be out of range (i.e. have a value larger than the size of that dimension for the matrix A). Thus by checking that the row and column indices are in range you can make sure you are not including any of the zero-padding in your subsequent analysis.

How can I extract n elements from each m-by-m window of a matrix without using loops in MATLAB?

1 Answers