Matrix "Zigzag" Reordering

Question

I have an NxM matrix in Matlab that I would like to reorder in similar fashion to the way JPEG reorders its subblock pixels:

(referenced from here)

I would like the algorithm to be generic such that I can pass in a 2D matrix with any dimensions. I am a C++ programmer by trade and am very tempted to write an old school loop to accomplish this, but I suspect there is a better way to do it in Matlab.

Update: I'd be more than happy with an algorithm that worked on an NxN matrix and go from there.

Example:

1 2 3
4 5 6  -->  1 2 4 7 5 3 6 8 9
7 8 9

Answer 1

Let's assume for a moment that you have a 2-D matrix that's the same size as your image specifying the correct index. Call this array idx; then the matlab commands to reorder your image would be

[~,I] = sort (idx(:)); %sort the 1D indices of the image into ascending order according to idx
reorderedim = im(I);

I don't see an obvious solution to generate idx without using for loops or recursion, but I'll think some more.

Answer 2

Here's a way how to do this. Basically, your array is a hankel matrix plus vectors of 1:m, where m is the number of elements in each diagonal. Maybe someone else has a neat idea on how to create the diagonal arrays that have to be added to the flipped hankel array without a loop.

I think this should be generalizeable to a non-square array.

% for a 3x3 array 
n=3;

numElementsPerDiagonal = [1:n,n-1:-1:1];
hadaRC = cumsum([0,numElementsPerDiagonal(1:end-1)]);
array2add = fliplr(hankel(hadaRC(1:n),hadaRC(end-n+1:n)));

% loop through the hankel array and add numbers counting either up or down
% if they are even or odd
for d = 1:(2*n-1)
   if floor(d/2)==d/2
      % even, count down
      array2add = array2add + diag(1:numElementsPerDiagonal(d),d-n);
   else
      % odd, count up
      array2add = array2add + diag(numElementsPerDiagonal(d):-1:1,d-n);
   end
end

% now flip to get the result
indexMatrix = fliplr(array2add)

result =
     1     2     6
     3     5     7
     4     8     9

Afterward, you just call reshape(image(indexMatrix),[],1) to get the vector of reordered elements.

EDIT

Ok, from your comment it looks like you need to use sort like Marc suggested.

indexMatrixT = indexMatrix';   % ' SO formatting
[dummy,sortedIdx] = sort(indexMatrixT(:));

sortedIdx =
     1     2     4     7     5     3     6     8     9

Note that you'd need to transpose your input matrix first before you index, because Matlab counts first down, then right.

Answer 3

Consider the code:

M = randi(100, [3 4]);                      %# input matrix

ind = reshape(1:numel(M), size(M));         %# indices of elements
ind = fliplr( spdiags( fliplr(ind) ) );     %# get the anti-diagonals
ind(:,1:2:end) = flipud( ind(:,1:2:end) );  %# reverse order of odd columns
ind(ind==0) = [];                           %# keep non-zero indices

M(ind)                                      %# get elements in zigzag order

An example with a 4x4 matrix:

» M
M =
    17    35    26    96
    12    59    51    55
    50    23    70    14
    96    76    90    15

» M(ind)
ans =
    17  35  12  50  59  26  96  51  23  96  76  70  55  14  90  15

and an example with a non-square matrix:

M =
    69     9    16   100
    75    23    83     8
    46    92    54    45
ans =
    69     9    75    46    23    16   100    83    92    54     8    45

Answer 4

Here's a non-loop solution zig_zag.m. It looks ugly but it works!:

function [M,index] = zig_zag(M)
  [r,c] = size(M);
  checker = rem(hankel(1:r,r-1+(1:c)),2);
  [rEven,cEven] = find(checker);
  [cOdd,rOdd] = find(~checker.'); %'#
  rTotal = [rEven; rOdd];
  cTotal = [cEven; cOdd];
  [junk,sortIndex] = sort(rTotal+cTotal);
  rSort = rTotal(sortIndex);
  cSort = cTotal(sortIndex);
  index = sub2ind([r c],rSort,cSort);
  M = M(index);
end

And a test matrix:

>> M = [magic(4) zeros(4,1)];

M =

    16     2     3    13     0
     5    11    10     8     0
     9     7     6    12     0
     4    14    15     1     0

>> newM = zig_zag(M)    %# Zig-zag sampled elements

newM =

    16
     2
     5
     9
    11
     3
    13
    10
     7
     4
    14
     6
     8
     0
     0
    12
    15
     1
     0
     0