# 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 at 0:29
You can format inline code and code blocks by selecting the code and clicking the {} button above the edit window. The edit window help button ? is also useful for learning how to format your questions and answers. You may also find this this meta Q&A helpful – Michael E2 Mar 13 at 0:49

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 at 14:09
@RamyaMendharkar See the update. – Michael E2 Mar 13 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.

-