Walsh functions and lossy compression.

Walsh functions are best introduced via Hadamard matrices.

Hadamard matrices :

Clear[H];H[0]=1;

H[k_]:=H[k]=ArrayFlatten[{{H[k-1],H[k-1]},{H[k-1],-H[k-1]}}]

Table[Print["H[",j,"]=",H[j]//MatrixForm],{j,1,4}]

Walsh-1D functions :

Walsh functions are given by the rows (equivalently the columns) of the Hadamard matrices.

Walsh1D[s_,j_]:=H[s][[j]]

Two examples : s = 3 (8 functions) and s = 4 (16 functions) :

GraphicsGrid[Partition[Table[Show[BarChart[Walsh1D[3,j],BarSpacing->None],PlotRange->{-1,1}],{j,8}],4]]

GraphicsGrid[Partition[Table[Show[BarChart[Walsh1D[4,j],BarSpacing->None],PlotRange->{-1,1}],{j,16}],4]]

Walsh functions are orthonormed with respect to the following scalar product :

a_⊙b_:=Total[a b,2]

Table[((2^(-3/2))Walsh1D[3,i])⊙((2^(-3/2))Walsh1D[3,j]),{i,8},{j,8}]//MatrixForm

An arbitrary binary 1D-function (say {1,1,1,1,1,1,-1,-1} if s = 3)  is expandable in the basis of 1D-Walsh functions :

{1,1,1,1,1,1,-1,-1}==(∑_(j=1)^8)(((2^(-3/2))Walsh1D[3,j])⊙{1,1,1,1,1,1,-1,-1})((2^(-3/2))Walsh1D[3,j])

Walsh-2D functions :

Walsh2D[s_,i_,j_]:=Outer[Times,Walsh1D[s,i],Walsh1D[s,j]]

GraphicsGrid[Table[ArrayPlot[Walsh2D[3,i,j],ColorRules->{-1->Black,1->White}],{i,8},{j,8}]]

The following character, R, is pixellized in a 64x64 grid :

Rpixels=ImageData[,"Bit"]/.{{1,1,1}->1,{0,0,0}->-1};

Rpixels//MatrixForm

Image[ Rpixels]

coefficientsR[i_,j_]:=Walsh2D[6,i,j]⊙Rpixels

The walsh coefficients for the letter R :

Table[coefficientsR[i,j],{i,1,64},{j,1,64}]

The walsh coefficients for the letter R, sorted in decreasing order (absolute value) :

Sort[Flatten[Table[Abs[coefficientsR[i,j]],{i,1,64},{j,1,64}]],Greater]

An arbitrary binary 2D-function (say Rpixels)  is expandable without loss in the basis of 2D-Walsh functions :

Image[Sum[coefficientsR[i,j]Walsh2D[6,i,j],{i,64},{j,64}]/4096]

64*64

Light truncation :

Image[Sum[If[Abs[coefficientsR[i,j]]>20,coefficientsR[i,j],0]Walsh2D[6,i,j],{i,64},{j,64}]/4096]

Length[Select[Flatten[Table[coefficientsR[i,j],{i,64},{j,64}]],Abs[#]>20&]]

Light truncation with greylevels erased :

char=Sum[If[Abs[coefficientsR[i,j]]>20,coefficientsR[i,j],0]Walsh2D[6,i,j],{i,64},{j,64}]/4096

resu=Table[1,{i,64},{j,64}];Do[If[char[[i,j]]≤0,resu[[i,j]]=0,Continue],{i,64},{j,64}];

Image[resu]

Medium truncation :

Image[Sum[If[Abs[coefficientsR[i,j]]>100,coefficientsR[i,j],0]Walsh2D[6,i,j],{i,64},{j,64}]/4096]

Length[Select[Flatten[Table[coefficientsR[i,j],{i,64},{j,64}]],Abs[#]>100&]]

Medium truncation with greylevels erased :

char=Sum[If[Abs[coefficientsR[i,j]]>100,coefficientsR[i,j],0]Walsh2D[6,i,j],{i,64},{j,64}]/4096;

resu=Table[1,{i,64},{j,64}];Do[If[char[[i,j]]≤0,resu[[i,j]]=0,Continue],{i,64},{j,64}];

Image[resu]

Strong truncation :

Image[Sum[If[Abs[coefficientsR[i,j]]>200,coefficientsR[i,j],0]Walsh2D[6,i,j],{i,64},{j,64}]/4096]

Length[Select[Flatten[Table[coefficientsR[i,j],{i,64},{j,64}]],Abs[#]>200&]]

Strong truncation with greylevels erased :

char=Sum[If[Abs[coefficientsR[i,j]]>200,coefficientsR[i,j],0]Walsh2D[6,i,j],{i,64},{j,64}]/4096;

resu=Table[1,{i,64},{j,64}];Do[If[char[[i,j]]≤0,resu[[i,j]]=0,Continue],{i,64},{j,64}];

Image[resu]