stc.tex

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