[canny.git] / stc.tex

To make this article self-contained, this section recalls
the basis of the Syndrome Treillis Codes  (STC). 
\JFC{A reader who is familar with syndrome coding can skip it.}

Let 
$x=(x_1,\ldots,x_n)$ be the $n$-bits cover vector issued from an image $X$, 
$m$ be the message to embed, and 
$y=(y_1,\ldots,y_n)$ be the $n$-bits stego vector.
The usual additive embedding impact of replacing $x$ by $y$ in $X$
is given by a distortion function 
$D_X(x,y)= \Sigma_{i=1}^n \rho_X(i,x,y)$, where the function $\rho_X$
expresses the cost of replacing $x_i$ by $y_i$ in $X$.
The objective is thus to find $y$ that minimizes $D_X(x,y)$.

Hamming embedding proposes a solution to this problem. 
This is why some steganographic 
schemes~\cite{DBLP:conf/ih/Westfeld01,DBLP:conf/ih/KimDR06,DBLP:conf/mmsec/FridrichPK07} are based on this binary embedding.
Furthermore this code provides a vector $y$ s.t. $Hy$ is equal to 
$m$ for a given binary matrix $H$. 

Let us explain this embedding on a small illustrative example where
$m$ and $x$ are respectively  a 3 bits column
vector and a 7 bits column vector, and where 
$\rho_X(i,x,y)$ is equal to 1 for any $i$, $x$, $y$
(\textit{i.e.}, $\rho_X(i,x,y) = 0$ if $x = y$ and $1$ otherwise).  

Let  $\dot{H}$ be the binary Hamming matrix  
$$
\dot{H} = \left(
\begin{array}{lllllll}
 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
 1 & 0 & 1 & 0 & 1 & 0 & 1 
\end{array}
\right).
$$
The objective is to modify $x$ to get $y$ s.t. $m = \dot{H}y$.
In this algebra, the sum and the product respectively correspond to
the exclusive \emph{or} and to the \emph{and} Boolean operators.
If $\dot{H}x$ is already equal to $m$, nothing has to be changed and $x$ can be sent.
Otherwise we consider the difference $\delta = d(m,\dot{H}x)$, which is expressed 
as a vector : 
$$
\delta = \left( \begin{array}{l}
\delta_1 \\
\delta_2 \\
\delta_3
\end{array} 
\right)  
\textrm{ where $\delta_i$ is 0 if $m_i = Hx_i$ and 1 otherwise.} 
$$
Let us thus consider the $j-$th column of $H$, which is equal to $\delta$.   
We denote by $\overline{x}^j$ the vector  obtained by
switching the $j-$th component of $x$, 
that is, $\overline{x}^j = (x_1 , \ldots, \overline{x_j},\ldots, x_n )$.
It is not hard to see that if $y$ is $\overline{x}^j$, then 
$m = \dot{H}y$.
It is then possible to embed 3 bits in 7 LSBs of pixels by modifying
at most 1 bit.
In the general case, communicating a message of $p$ bits in a cover of 
$n=2^p-1$ pixels needs $1-1/2^p$ average changes.

This Hamming embedding is really efficient to very small payload and is 
not well suited when the size of the message is larger, as in real situations.
The matrix $H$ should be changed to deal with higher payload.
Moreover, for any given $H$, finding $y$ that solves $Hy=m$ and  
that minimizes $D_X(x,y)$, has an exponential complexity with respect to $n$. 
The Syndrome-Trellis Codes  
presented by Filler \emph{et al.} in~\cite{FillerJF11}
is a practical solution to this complexity. Thanks to this contribution,
the solving algorithm has a linear complexity with respect to $n$.

First of all, Filler \emph{et al.} compute the matrix $H$
by placing a small sub-matrix $\hat{H}$ next
to each other and by shifting down by one row. 
Thanks to this special form of $H$, one can represent
any solution of  $m=Hy$ as a path through a trellis.

Next, the  process of finding $y$ consists in two stages: a forward and a backward part.
\begin{enumerate}
\item Forward construction of the trellis that depends on $\hat{H}$, on $x$, on $m$, and on $\rho$. This step is linear in $n$.
\item Backward determination of $y$ that minimizes $D$, starting with 
the complete path having the minimal weight. This corresponds to traversing 
a graph and has a complexity which is linear in $n$. 
\end{enumerate}