stc.tex

   1 Let
   2 $x=(x_1,\ldots,x_n)$ be the $n$-bits cover vector of the image $X$,
   3 $m$ be the message to embed and
   4 $y=(y_1,\ldots,y_n)$ be the $n$-bits stego vector.
   5 The usual additive embbeding impact of replacing $x$ by $y$ in $X$
   6 is given by a distortion function
   7 $D_X(x,y)= \Sigma_{i=1}^n \rho_X(i,x,y)$ where the function $\rho_X$
   8 expressed the cost of replacing $x_i$ by $y_i$ in $X$.
   9 Let us consider that $x$ is fixed:
  10 this is for instance the LSBs of the image edge bits.
  11 The objective is thus to find $y$ that minimizes $D_X(x,y)$.
  12
  13 Hamming embedding proposes a solution to this problem.
  14 Some steganographic
  15 schemes~\cite{DBLP:conf/ih/Westfeld01,DBLP:conf/ih/KimDR06,DBLP:conf/mmsec/FridrichPK07} are based on this binary embedding.
  16 Furthermore this code provides a vector $y$ s.t. $Hy$ is equal to
  17 $m$ for a given binary matrix $H$.
  18
  19 Let us explain this embedding on a small illustrative example where
  20 $\rho_X(i,x,y)$ is identically equal to 1,
  21 $m$ and $x$ are respectively  a 3 bits column
  22 vector and a 7 bits column vector.
  23 Let then $H$ be the binary Hamming matrix
  24 $$
  25 H = \left(
  26 \begin{array}{lllllll}
  27  0 & 0 & 0 & 1 & 1 & 1 & 1 \\
  28  0 & 1 & 1 & 0 & 0 & 1 & 1 \\
  29  1 & 0 & 1 & 0 & 1 & 0 & 1
  30 \end{array}
  31 \right).
  32 $$
  33 The objective is to modify $x$ to get $y$ s.t. $m = Hy$.
  34 In this algebra, the sum and the product respectively correspond to
  35 the exclusive \emph{or} and to the \emph{and} Boolean operators.
  36 If $Hx$ is already equal to $m$, nothing has to be changed and $x$ can be sent.
  37 Otherwise we consider the difference $\delta = d(m,Hx)$ which is expressed
  38 as a vector :
  39 $$
  40 \delta = \left( \begin{array}{l}
  41 \delta_1 \\
  42 \delta_2 \\
  43 \delta_3
  44 \end{array}
  45 \right)
  46 \textrm{ where $\delta_i$ is 0 if $m_i = Hx_i$ and 1 otherwise.}
  47 $$
  48 Let us thus consider the $j$th column of $H$ which is equal to $\delta$.
  49 We denote by $\overline{x}^j$ the vector  we obtain by
  50 switching the $j$th component of $x$,
  51 that is, $\overline{x}^j = (x_1 , \ldots, \overline{x_j},\ldots, x_n )$.
  52 It is not hard to see that if $y$ is $\overline{x}^j$, then
  53 $m = Hy$.
  54 It is then possible to embed 3 bits in only 7 LSB of pixels by modifying
  55 1 bit at most.
  56 In the general case, when comunicating $n$ message bits in
  57 $2^n-1$ pixels needs $1-1/2^n$ average changes.
  58
  59
  60
  61 Unfortunately,
  62
  63
  64 for any given $H$, finding $y$ that solves $Hy=m$ and that
  65 that minimizes $D_X(x,y)$ has exponential complexity with respect to $n$.
  66 The Syndrome-Trellis Codes  (STC)
  67 presented by Filler et al. in~\cite{DBLP:conf/mediaforensics/FillerJF10}
  68 is a practical solution to this complexity. Thanks to this contribution,
  69 the solving algorithm has a linear complexity with resspect to $n$.
  70
  71 First of all, Filler et al. compute the matrix $H$
  72 by placing a small sub-matrix $\hat{H}$ of size $h × w$ next
  73 to each other and shifted down by one row.
  74 Thanks to this special form of $H$, one can represent
  75 every solution of  $m=Hy$ as a path through a trellis.
  76
  77 Next, the  process of finding $y$ consists of a forward and a backward part:
  78 \begin{enumerate}
  79 \item Forward construction of the trellis that depends on $\hat{H}$, on $x$, on $m$, and on $\rho$;
  80 \item Backward determinization of $y$ which minimizes $D$ starting with
  81 the complete path with minimal weight
  82 \end{enumerate}
  83 Let us now give some details about these two parts.
  84
  85