To make this article self-contained, this section recalls
-the basis of the Syndrome Treillis Codes (STC).
+the basis of the Syndrome Treillis Codes (STC).
+\JFC{A reader that is familar with syndrome coding can skip it.}
+
Let
-$x=(x_1,\ldots,x_n)$ be the $n$-bits cover vector of the image $X$,
+$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$.
-Let us consider that $x$ is fixed:
-this is for instance the LSBs of the image edge bits.
The objective is thus to find $y$ that minimizes $D_X(x,y)$.
Hamming embedding proposes a solution to this problem.
$m$ for a given binary matrix $H$.
Let us explain this embedding on a small illustrative example where
-$\rho_X(i,x,y)$ is equal to 1,
-whereas $m$ and $x$ are respectively a 3 bits column
-vector and a 7 bits column vector.
-Let then $H$ be the binary Hamming matrix
+$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
$$
-H = \left(
+\dot{H} = \left(
\begin{array}{lllllll}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
\end{array}
\right).
$$
-The objective is to modify $x$ to get $y$ s.t. $m = Hy$.
+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 $Hx$ is already equal to $m$, nothing has to be changed and $x$ can be sent.
-Otherwise we consider the difference $\delta = d(m,Hx)$, which is expressed
+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}
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 = Hy$.
-It is then possible to embed 3 bits in only 7 LSBs of pixels by modifying
+$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 $n$ message bits in
-$2^n-1$ pixels needs $1-1/2^n$ average changes.
-
+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.
-
-Unfortunately, for any given $H$, finding $y$ that solves $Hy=m$ and
+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{DBLP:conf/mediaforensics/FillerJF10}
+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}$ of size $h × w$ next
+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$.
+\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.
+the complete path having the minimal weight. This corresponds to traversing
+a graph and has a complexity which is linear in $n$.
\end{enumerate}
-
