9

How do I cycle elements through each index of patches of a matrix without explicitly iterating through each patch?

Example

The iterative way I can think to perform this cycling is with MATLAB's circshift function. I could iterate through each MxN patch in my matrix, and perform a circular shift on the elements of that patch.

(NOTE: circshift takes an array and moves the first (or k-th) index to the back, shifting everything forward to make room. With a matrix, you just vectorize it, shift it, and reshape back, taking advantage of MATLAB's column-major linear indexing)

That would be great if I were to iterate through every MxN window of my larger (j*M x k*N for integers j,k) matrix. However, I'd like to be able to avoid for loops and take advantage of MATLAB's vectorized code to do this in one fell swoop.

One full iteration through an example (2x2 patches in some matrix B) would be:

B =           -->   B =           -->   B =           -->   B =
[ 5 6 7 8 ]   -->   [ 5 6 7 8 ]   -->   [ 6 5 8 7 ]   -->   [ 6 5 8 7 ]
[ 5 6 7 8 ]   -->   [ 6 5 8 7 ]   -->   [ 6 5 8 7 ]   -->   [ 5 6 7 8 ]
[ 5 6 7 8 ]   -->   [ 5 6 7 8 ]   -->   [ 6 5 8 7 ]   -->   [ 6 5 8 7 ]
[ 5 6 7 8 ]   -->   [ 6 5 8 7 ]   -->   [ 6 5 8 7 ]   -->   [ 5 6 7 8 ]

Any ideas how to make this shift work without explicitly iterating through every patch? I feel like linear indexing is the key here, but I'm not sure why. I also don't care about the order of rotation as long as every patch element ends up in every patch index.

Thanks in advance!

EDIT: Here's a copy-and-paste-able toy implementation using for loops to demonstrate what I'm looking for. The only for loop that should be included in an answer is the k-iterator (controls how many shifts ultimately need to be made)

A = repmat(1:4, 4, 1); % Input matrix

% k represents the total number of shifts to be made
for k = 1:4

    % Iterate through each patch
    for i = 1:2:size(A,1)
        for j = 1:2:size(A,2)
            tmp = A(i:i+1,j:j+1); % Isolate specific patch

            % Circularly shift the vectorized patch, reshape it to a matrix
            % and insert it back into the original matrix
            A(i:i+1,j:j+1) = reshape(circshift(tmp(:),1), 2, 2);
        end
    end
    display(A) % Display each completely shifted iteration
end
2
  • It is an interesting question. You can generally consider that everything what you want can be done. But at least I am not motivated to think about how your input and output should be arranged. Please post your exact input ready for copy&paste and the output you'd like to get for that input (also ready for copy&paste). There are a lot things to clarify. e.g. do you like cell arrays as output? or 3D matrices? Commented May 2, 2015 at 11:37
  • @thewaywewalk I added a toy example for copy/paste that should hopefully demo what I'm looking for. The output should be a matrix of the same dimensions as the input. I want to avoid cell arrays unless they can be easily converted back. I thought about using cell arrays too because they're useful for partitioning a matrix into blocks, but even with that it doesn't help do the shift as far as I can tell.
    – marcman
    Commented May 2, 2015 at 14:20

1 Answer 1

2

A simple way to do this would be to use the blockproc function from the Image Processing Toolbox. blockproc divides an image (or in general: a matrix) into blocks of a defined size and applies a function to each of these blocks:

B = blockproc(A,blockSize,fun);

Using blockproc, we can divide the matrix A into 2 x 2 patches and apply the circular shift to each of those patches. Note that blockproc creates a block_struct datatype and calls fun(block_struct). To get the data, simply use the data field of the struct. This will lead to

B = blockproc(A, [2,2], @(x)reshape(circshift(x.data(:),1),2,2));

Or with the provided example code:

A = repmat(1:4, 4, 1);
for k=1:4
    A = blockproc(A, [2,2], @(x)reshape(circshift(x.data(:),1),2,2));
    display(A);
end

which creates the desired output

[ 1 2 3 4 ]      [ 2 1 4 3 ]      [ 2 1 4 3 ]      [ 1 2 3 4 ] 
[ 1 2 3 4 ]  ->  [ 1 2 3 4 ]  ->  [ 2 1 4 3 ]  ->  [ 2 1 4 3 ]  -> ...
[ 1 2 3 4 ]      [ 2 1 4 3 ]      [ 2 1 4 3 ]      [ 1 2 3 4 ] 
[ 1 2 3 4 ]      [ 1 2 3 4 ]      [ 2 1 4 3 ]      [ 2 1 4 3 ]

You can also define, how to handle cases where the matrix can not be divided into 2 x 2 blocks, e.g. if it has dimension 5 x 7 (as mentioned in comments). By setting the PadPartialBlocks to true, all partial blocks will be padded so they form full 2 x 2 blocks. You can set the PadMethod property to one of the following values, depending on what you need:

  • x where x is a number, which all additional points will be set to.
  • replicate will repeat the border elements of the matrix A
  • symmetric will pad A with symmetric reflections of itsself
2
  • How does blockproc handle edge cases? For example if the input matrix were not jM x kN but were instead 5x7 for 2x2 patches?
    – marcman
    Commented May 2, 2015 at 15:10
  • @marcman I added something on that too. If you define what behavior is desired, I can probably show how that would be done.
    – hbaderts
    Commented May 2, 2015 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.