stc.tex

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