stc.tex

   1 To make this article self-contained, this section recalls
   2 the basis of the Syndrome Treillis Codes  (STC).
   3 \JFC{A reader that is familar with syndrome coding can skip it.}
   4
   5 Let
   6 $x=(x_1,\ldots,x_n)$ be the $n$-bits cover vector issued from an image $X$,
   7 $m$ be the message to embed, and
   8 $y=(y_1,\ldots,y_n)$ be the $n$-bits stego vector.
   9 The usual additive embedding impact of replacing $x$ by $y$ in $X$
  10 is given by a distortion function
  11 $D_X(x,y)= \Sigma_{i=1}^n \rho_X(i,x,y)$, where the function $\rho_X$
  12 expresses the cost of replacing $x_i$ by $y_i$ in $X$.
  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 $m$ and $x$ are respectively  a 3 bits column
  23 vector and a 7 bits column vector, and where
  24 $\rho_X(i,x,y)$ is equal to 1 for any $i$, $x$, $y$
  25 (\textit{i.e.}, $\rho_X(i,x,y) = 0$ if $x = y$ and $1$ otherwise).
  26
  27 Let  $\dot{H}$ be the binary Hamming matrix
  28 $$
  29 \dot{H} = \left(
  30 \begin{array}{lllllll}
  31  0 & 0 & 0 & 1 & 1 & 1 & 1 \\
  32  0 & 1 & 1 & 0 & 0 & 1 & 1 \\
  33  1 & 0 & 1 & 0 & 1 & 0 & 1
  34 \end{array}
  35 \right).
  36 $$
  37 The objective is to modify $x$ to get $y$ s.t. $m = \dot{H}y$.
  38 In this algebra, the sum and the product respectively correspond to
  39 the exclusive \emph{or} and to the \emph{and} Boolean operators.
  40 If $\dot{H}x$ is already equal to $m$, nothing has to be changed and $x$ can be sent.
  41 Otherwise we consider the difference $\delta = d(m,\dot{H}x)$, which is expressed
  42 as a vector :
  43 $$
  44 \delta = \left( \begin{array}{l}
  45 \delta_1 \\
  46 \delta_2 \\
  47 \delta_3
  48 \end{array}
  49 \right)
  50 \textrm{ where $\delta_i$ is 0 if $m_i = Hx_i$ and 1 otherwise.}
  51 $$
  52 Let us thus consider the $j-$th column of $H$, which is equal to $\delta$.
  53 We denote by $\overline{x}^j$ the vector  obtained by
  54 switching the $j-$th component of $x$,
  55 that is, $\overline{x}^j = (x_1 , \ldots, \overline{x_j},\ldots, x_n )$.
  56 It is not hard to see that if $y$ is $\overline{x}^j$, then
  57 $m = \dot{H}y$.
  58 It is then possible to embed 3 bits in 7 LSBs of pixels by modifying
  59 at most 1 bit.
  60 In the general case, communicating a message of $p$ bits in a cover of
  61 $n=2^p-1$ pixels needs $1-1/2^p$ average changes.
  62
  63 This Hamming embedding is really efficient to very small payload and is
  64 not well suited when the size of the message is larger, as in real situations.
  65 The matrix $H$ should be changed to deal with higher payload.
  66 Moreover, for any given $H$, finding $y$ that solves $Hy=m$ and
  67 that minimizes $D_X(x,y)$, has an exponential complexity with respect to $n$.
  68 The Syndrome-Trellis Codes
  69 presented by Filler \emph{et al.} in~\cite{FillerJF11}
  70 is a practical solution to this complexity. Thanks to this contribution,
  71 the solving algorithm has a linear complexity with respect to $n$.
  72
  73 First of all, Filler \emph{et al.} compute the matrix $H$
  74 by placing a small sub-matrix $\hat{H}$ next
  75 to each other and by shifting down by one row.
  76 Thanks to this special form of $H$, one can represent
  77 any solution of  $m=Hy$ as a path through a trellis.
  78
  79 Next, the  process of finding $y$ consists in two stages: a forward and a backward part.
  80 \begin{enumerate}
  81 \item Forward construction of the trellis that depends on $\hat{H}$, on $x$, on $m$, and on $\rho$. This step is linear in $n$.
  82 \item Backward determination of $y$ that minimizes $D$, starting with
  83 the complete path having the minimal weight. This corresponds to traversing
  84 a graph and has a complexity which is linear in $n$.
  85 \end{enumerate}
  86
  87