# Zigzag ordered encoding of DCT co-efficients

I am doing DCT steganography. I have obtained a matrix of DCT co-efficient. I now want to perform zig-zag ordered encoding.

The matrix is as follows

({
{39, -11, 16, -1, 4, 1, 1, 1},
{-10, 2, -2, 0, -1, 0, 0, 0},
{11, -2, 3, 0, 1, 0, 0, 0},
{-1, 0, 0, 0, 0, 0, 0, 0},
{6, -1, 1, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0}
}


I want to order the elements as in the image below

• Have a look at mathematica.stackexchange.com/q/72861/2305 to get all antidiagonals (you don't want to flatten them yet though). Then you reverse every other one with either MapAt or MapIndexed, and then you flatten it. Reconstructing the matrix is going to be a bit more... fun. – Martin Ender Mar 13 '16 at 0:29

We can let Mathematica figure out the ordering by sorting the indices of the array.

Clear[cmp];
cmp[p__] := Print[p];
cmp[{x1_, x2_}, {y1_, y2_}] := (x1 + x2 < y1 + y2 ||
(x1 + x2 == y1 + y2 && If[OddQ[x1 + x2], OrderedQ[{x1, y1}], OrderedQ[{x2, y2}]]));

ClearAll[zigzag, zigzagorder];
zigzagorder[n_Integer] := zigzagorder[n] =
Ordering[Flatten[Outer[List, Range@n, Range@n], 1], All, cmp]
zigzag[mat_?SquareMatrixQ] :=
Flatten[mat, 1][[zigzagorder@Length@mat]];


Example:

m = Normal@SparseArray[{i_, j_} :> (-1)^(i + j) (10 i + j), {6, 6}];
m // MatrixForm
zarray = zigzag[m]


(*
{ 11,
-12, -21,
31,  22,  13,
-14, -23, -32, -41,
51,  42,  33,  24,  15,
-16, -25, -34, -43, -52, -61,
62,  53,  44,  35,  26,
-36, -45, -54, -63,
64,  55,  46,
-56, -65,
66}
*)


Response to comment: How to invert?

It's relatively easy to invert the processing, since Ordering returns a permutation of Range[n] of the indices of the elements. The inverse permutation can be obtained by calling Ordering on the ordering.

m2 = Partition[zarray[[Ordering@zigzagorder@6]], 6];
m2 == m
(*  True  *)


General function:

zpartition[array_List] := With[{n = Sqrt[Length@array]},
Partition[array[[Ordering@zigzagorder@n]], n] /; IntegerQ[n]
];

zpartition[zarray]
(*  same as m  *)

• can u also tell me how to convert it to original form? – Ramya Mendharkar Mar 13 '16 at 14:09
• @RamyaMendharkar See the update. – Michael E2 Mar 13 '16 at 14:27

Here's a relatively nifty way to perform the zigzag:

(* Michael's example *)
m = Array[Function[{i, j}, (-1)^(i + j) (10 i + j)], {6, 6}];

rm = Reverse /@ m; l = Length[m] - 1;
Table[If[OddQ[k], Reverse, Identity][Diagonal[rm, -k]], {k, -l, l}]
{{11},
{-12, -21},
{31, 22, 13},
{-14, -23, -32, -41},
{51, 42, 33, 24, 15},
{-16, -25, -34, -43, -52, -61},
{62, 53, 44, 35, 26},
{-36, -45, -54, -63},
{64, 55, 46},
{-56, -65},
{66}}


Apply Flatten[] if needed.