For loop to split matrix to equal sized sub-matrices

Question

Given a square matrix of say size 400x400, how would I go about splitting this into constituent sub-matrices of 20x20 using a for-loop? I can't even think where to begin!

I imagine I want something like :

[x,y] = size(matrix)

for i = 1:20:x
    for j = 1:20:y

but I'm unsure how I would proceed. Thoughts?

Disfranchise

Though you have got the answer, just for curiosity, what made you write number 30 if you are going to split the matrix into 20x20 sub-matrices – Stoical

mat2cell is good for breaking up a matrix in to sub-matrices. KlausCPH's answer is a good example. See also here. – Accountancy

@Parag Just a mistake haha! – Disfranchise

related question: https://mcmap.net/q/247396/-is-there-a-substitute-for-blockproc-in-matlab/97160 – Medlock

Answer 1

Well, I know that the poster explicitly asked for a for loop, and Jeff Mather's answer provided exactly that.

But still I got curious whether it is possible to decompose a matrix into tiles (sub-matrices) of a given size without a loop. In case someone else is curious, too, here's what I have come up with:

T = permute(reshape(permute(reshape(A, size(A, 1), n, []), [2 1 3]), n, m, []), [2 1 3])

transforms a two-dimensional array A into a three-dimensional array T, where each 2d slice T(:, :, i) is one of the tiles of size m x n. The third index enumerates the tiles in standard Matlab linearized order, tile rows first.

The variant

T = permute(reshape(A, size(A, 1), n, []), [2 1 3]);
T = permute(reshape(T, n, m, [], size(T, 3)), [2 1 3 4]);

makes T a four-dimensional array where T(:, :, i, j) gives the 2d slice with tile indices i, j.

Coming up with these expressions feels a bit like solving a sliding puzzle. ;-)

Indebted

If you have the Image Processing Toolbox, you can use blockproc to apply a function handle to subsections of an image/matrix iteratively. For example: blockproc(M, [20 20], @myAwesomeFunction) – Sterrett

Sure. But where's the fun in that? ;-) – Indebted

+1 I was curious! In fact, I tried for a few minutes, and quit :-) – Salim

@A.Donda I used your cutting up of the matrix in this answer. Although I still don't see exactly how it works... :-) – Salim

@A.Donda, Could you have a look here: #25449779 – Illona

Amazing work. +1 I expanded your answer to 3D matrices. check out! – Avram

@LuisMendo, thanks a bunch for offering this bounty, I'm honored! I think I'll take this as an incentive to try and explain the black magic... – Indebted

@A.Donda On the other hand, that would spoil its appeal a little! :-) – Salim

This is an horrible answer. Not only does it not answer the question (which explicitly requested a for loop), it's performance is terrible compared to much simpler alternatives such as KlausCPH answer to use cell2mat. – Tabling

@A.Donda I measured it from a size of 30x30 up to 10000x10000 (see my post further down). Yes, it's slightly faster at small matrix sizes but the specific 400x400 size is not really the point of the answer the OP picked it as an example. And permute, depending on the order, will create a copy. – Tabling

@carandraug, you have only looked what happens for really large matrices when they are split into a small number of submatrices. When they are split into a large number of submatrices, my method is faster again. – Right about permute though. Still, cell arrays are more complex data structure. – Indebted

@carandraug, what I'm really wondering though is why the bounty motivates you to jump in and criticize my answer, for not being efficient (my answer doesn't claim it is), for not using for loops (I stated that, and we both know that's a bad idea in Matlab most of the time). Then you write a whole answer which does not actually answer the question. – Indebted

@carandraug. You call my answer "horrible", which is a pretty strong word, and you call me implicitly a "guru", which is still not nice. Seriously, what's the big deal here? What Luis Mendo and probably most other upvoters realized is that this is an excercise in extreme vectorization, which (to me and apparently others) is interesting and entertaining. – Indebted

@carandraug, for the record, I upvoted three other answers, because they are all good in their own way. – Indebted

the bounty did not motivate the answer, it simply brought attention to the question which otherwise I wouldn't even see. And I added an answer because it was the only place to add such an extensive comment (unless you want me to edit your answer with the analysis -- I don't mind, just let me know). And how is guru not nice? That's supposed to be a compliment. The big deal is that vectorization is nice if it makes the code simpler and faster. Your does neither. It's an exercise in coming up with a difficult to maintain piece of code. – Tabling

@carandraug, a one- or two-line piece of code does not need to be immediately transparent if it is clearly documented what it does. There's nothing to maintain here, one uses the code or one doesn't. As for speed, as I pointed out, you only looked at one direction for large matrices. I do appreciate though that you didn't edit my answer. – I still don't understand why you go to such great lengths to bash my answer, which as stated was borne out of curiosity. But I guess this discussion leads nowhere, so: over and out. – Indebted

@Tabling I of course don't agree that this answer is "horrible". As A.Donda said, what I liked about it is its extreme vectorization. Your answer was interesting (I upvoted it), but I don't think "horrible" is a suitable word for this one – Salim

Answer 2

I'm sorry that my answer does not use a for loop either, but this would also do the trick:

cellOf20x20matrices = mat2cell(matrix, ones(1,20)*20, ones(1,20)*20)

You can then access the individual cells like:

cellOf20x20matrices{i,j}(a,b)

where i,j is the submatrix to fetch (and a,b is the indexing into that matrix if needed)

Regards

Slesvig

Answer 3

You seem really close. Just using the problem as you described it (400-by-400, divided into 20-by-20 chunks), wouldn't this do what you want?

[x,y] = size(M);

for i = 1:20:x
  for j = 1:20:y
    tmp = M(i:(i+19), j:(j+19));
    % Do something interesting with "tmp" here.
  end
end

Sterrett

Thanks, this was very helpful. And thanks everybody else for the other answers but was looking to use a for loop in this particular case. Some very interesting ideas being discussed! – Disfranchise

@user3058703, if this answer does what you were looking for, you should accept it (click the outlined check mark so it becomes green). – Indebted

Answer 4

Even though the question is basically for 2D matrices, inspired by A. Donda's answer I would like to expand his answer to 3D matrices so that this technique could be used in cropping True Color images (3D)

A = imread('peppers.png');       %// size(384x512x3)
nCol = 4;                        %// number of Col blocks
nRow = 2;                        %// number of Row blocks
m = size(A,1)/nRow;              %// Sub-matrix row size (Should be an integer)
n = size(A,2)/nCol;              %// Sub-matrix column size (Should be an integer)

imshow(A);                       %// show original image

out1 = reshape(permute(A,[2 1 4 3]),size(A,2),m,[],size(A,3));
out2 = permute(reshape(permute(out1,[2 1 3 4]),m,n,[],size(A,3)),[1 2 4 3]);

figure;
for i = 1:nCol*nRow
    subplot(nRow,nCol,i); imshow(out2(:,:,:,i));
end

The basic idea is to make the 3rd Dimension unaffected while reshaping so that the image isn't distorted. To achieve this, additional permuting was done to swap 3rd and 4th dimensions. Once the process is done, the dimensions are restored as it was, by permuting back.

Results:

Original Image

Subplots (Partitions / Sub Matrices)

---

Advantage of this method is, it works good on 2D images as well. Here is an example of a Gray Scale image (2D). Example used here is MatLab in-built image 'cameraman.tif'

Avram

Answer 5

With some many upvotes for the answer that makes use nested calls to permute, I thought of timing it and comparing to the other answer that makes use of mat2cell.

It is true that they don't return the exact same thing but:

• the cell can be easily converted into a matrix like the other (I timed this, see further down);
• when this problem arises, it is preferable (in my experience) to have the data in a cell since later on one will often want to put the original back together;

Anyway, I have compared them both with the following script. The code was run in Octave (version 3.9.1) with JIT disabled.

function T = split_by_reshape_permute (A, m, n)
  T = permute (reshape (permute (reshape (A, size (A, 1), n, []), [2 1 3]), n, m, []), [2 1 3]);
endfunction

function T = split_by_mat2cell (A, m, n)
  l = size (A) ./ [m n];
  T = mat2cell (A, repmat (m, l(1), 1), repmat (n, l (2), 1));
endfunction

function t = time_it (f, varargin)
  t = cputime ();
  for i = 1:100
    f(varargin{:});
  endfor
  t = cputime () - t;
endfunction

Asizes = [30 50 80 100 300 500 800 1000 3000 5000 8000 10000];
Tsides = [2 5 10];
As = arrayfun (@rand, Asizes, "UniformOutput", false);

for d = Tsides
  figure ();

  t1 = t2 = [];
  for A = As
    A = A{1};
    s = rows (A) /d;

    t1(end+1) = time_it (@split_by_reshape_permute, A, s, s);
    t2(end+1) = time_it (@split_by_mat2cell, A, s, s);

  endfor

  semilogy (Asizes, [t1(:) t2(:)]);
  title (sprintf ("Splitting in %i", d));
  legend ("reshape-permute", "mat2cell");
  xlabel ("Length of matrix side (all squares)");
  ylabel ("log (CPU time)");
endfor

Note that the Y axis is in log scale

Performance

Performance wise, using the nested permute will only be faster for smaller matrices where big changes in relative performance are actually very small changes in time. Note that the Y axis is in log scale, so the difference between the two functions for a 100x100 matrix is 0.02 seconds while for a 10000x10000 matrix is 100 seconds.

I have also tested the following which will convert the cell into a matrix so that the return values of the two functions are the same:

function T = split_by_mat2cell (A, m, n)
  l = size (A) ./ [m n];
  T = mat2cell (A, repmat (m, l(1), 1), repmat (n, l (2), 1), 1);
  T = reshape (cell2mat (T(:)'), [m n numel(T)]);
endfunction

This does slow it down a bit but not enough to consider (the lines will cross at 600x600 instead of 400x400).

Readability

It is so much more difficult to get your head around the use of the nested permute and reshape. It's mad to use it. It will increase maintenance time by a lot (but hey, this is Matlab language, it's not supposed to be elegant and reusable).

Future

The nested calls to permute does not expand nicely at all into N dimensions. I guess it would require a for loop by dimension (which would not help at all the already quite cryptic code). On the other hand, making use of mat2cell:

function T = split_by_mat2cell (A, lengths)
  dl = arrayfun (@(l, s) repmat (l, s, 1), lengths, size (A) ./ lengths, "UniformOutput", false);
  T = mat2cell (A, dl{:});
endfunction

Edit (and tested in Matlab too)

The amount of upvotes on the answer suggesting to use permute and reshape got me so curious that I decided to get this tested in Matlab (R2010b). The results there were pretty much the same, i.e., it's performance is really poor. So unless this operation will be done a lot of times, in matrices that will always be small (less than 300x300), and there will always be a Matlab guru around to explain what it does, don't use it.

Tabling

Answer 6

If you want to use a for loop you can do this:

[x,y] = size(matrix)

k=1; % counter

for i = 1:20:x
    for j = 1:20:y

        subMatrix=Matrix(i:i+19, j:j+19);

        subMatrixCell{k}=subMatrix;  % if you want to save all the
                                    % submatrices into a cell array
        k=k+1;

    end
end   

Gyron