zigzag scan: Image processing function

[zigzag.m]
## Copyright (C) 2006, June, Muthiah Annamalai, <muthiah.annamalai@...>

##

## This program is free software; you can redistribute it and/or modify

## it under the terms of the GNU General Public License as published by

## the Free Software Foundation; either version 2 of the License, or

## (at your option) any later version.

##

## This program is distributed in the hope that it will be useful,

## but WITHOUT ANY WARRANTY; without even the implied warranty of

## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

## GNU General Public License for more details.

##

## You should have received a copy of the GNU General Public License

## along with this program; if not, write to the Free Software

## Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

##

## -*- texinfo -*-

## @deftypefn {Function File} {} zigzag (@var{M})

##

## Returns the zig-zag scanned coefficients of given matrix @var{M}.

## Function of ZigZag scan is to accumulate the transform (DCT like)

## coefficients in the LF->HF in that order, from a square matrix. 

## 

## An exmaple of the use of @code{zigzag} is

## @example

## @group

##   x=[1:4]'*[1:4];

##   zigzag(x)

## @end group

## @end example

## @end deftypefn

% (C) 2006 June, Muthiah Annamalai, <muthiah.annamlai@...>

% 

% For a simple case_ we can use a ZZ scan using many loops, to

% generate the indices. 

% eg: case_ 4x4 we have ZZ scan indices being (in that order)

% (each of the rows have sums of 2:8) i.e 2:2S)

% (each row of t=2:2S has sum= (t-1) elements if_ t<S+2, and  sum=2S+1-t, elsewhere)

% (each row contains all the permutations summing up to t, in that order)

% (permutations are equidistant)

% (permutations are ordered as oddrows have descending in  x)

% (even rows have ascending in x)

% (if_ even row & non-multiple of 3, increase y index, else_ x index \

%   for_ first element of row.)

% (all odd rows have to increase x component first)

% (if_ only with first element, we can get the rest of the elements)

% (odd rows only have odd no of elements, even rows have only even no

%   of elements)

%

%1 (1,1),2

%2 (1,2) (2,1),3,x:y,y:x

%3 (3,1),(2,2),(1,3),4

%4 (1,4),(2,3),(3,2),(4,1),5

%5 (4,2),(3,3),(2,4),6

%6 (3,4),(4,3),7

%7 (4,4),8

%

%

%1 (1,1),2

%2 (1,2) (2,1),3,x:y,y:x

%3 (3,1),(2,2),(1,3),4

%4 (1,4),(2,3),(3,2),(4,1),5

%5 (5,1),(4,2),(3,3),(2,4),(1,5),6

%

%6 (3,4),(4,3),7

%7 (4,4),8

%

function rval=zigzag(mtrx)

  if (nargin < 1) 

    error('usage: zigzag_opt(square-matrix)')

  else

    S=issquare(mtrx);

    if(S <= 0)

      error('usage: zigzag_opt(square-matrix)')

    end

  end

  x=1;

  y=1;

  itrx=1;

  rval=zeros(1,S*S);

  rval(itrx)=[mtrx(x,y)];

  iseven=true;

  for itr=2:2*S-1

    %[x,y]

    %itr

    iseven=~iseven;

    %predicting the first element 

    %is the trick!

    if(iseven)

      if(itr > S)

        x=x+1;

        y=y;

      else

        x=x;

        y=y+1;

      end

    else

      %odd row

      if(itr <= S)

        y=y;

        x=x+1;

      else

        y=y+1;

        x=x;

      end

    end

    %[x,y]

    %compute nelem for_ this row.

    if(itr <S+1)

      nelem=itr;

    else

      nelem=2*S-itr;

    end

    rval(itrx+1)=mtrx(x,y);

    %compute target sum

    tgt_sum=itr;    

    %generate the elements

    if(iseven)

      %even rows ascend in X,

      %and have only even no of elements

      for itr2=2:nelem

        x=x+1;

        y=y-1;

        %[x,y]

        rval(itrx+itr2)=mtrx(x,y);

      end

    else

      %odd rows ascend in Y,

      for itr2=2:nelem

        y=y+1;

        x=x-1;

        %[x,y]

        rval(itrx+itr2)=mtrx(x,y);

      end

    end

    itrx=itrx+itr2;

  end

end