
\section{Appendix}
\label{AppendixIH}

We recall in this appendix some state of the 
art information hiding schemes. One should find more details in~\cite{Fridrich:2009:SDM:1721894}.
 
 
 
\subsection{YASS}
YASS (\emph{Yet Another Steganographic Scheme})~\cite{DBLP:conf/ih/SolankiSM07} is a 
steganographic approach dedicated to JPEG cover. 
The main idea of this algorithm is to hide data 
into $8\times 8$ randomly chosen inside $B\times B$ blocks 
(where $B$ is greater than 8) instead of choosing standard 
$8\times 8$ grids used  by JPEG compression.
The self-calibration process commonly embedded into blind steganalysis schemes
is then confused by the approach.
In the paper~\cite{SSM09}, further variants of YASS have been proposed
simultaneously to enlarge the embedding rate and to improve the 
randomization step of block selecting.
More precisely let be given a message $m$ to hide, a size $B$, $B \ge 8$, 
of blocks . 
The YASS algorithm follows: 
\begin{enumerate}
\item computation of $m'$ which is 
  the Repeat-Accumulate error correction code of $m$
\item in each big block of size $B \times B$ of cover, successively:
  \begin{enumerate}
\item random selection of an $8 \times 8$ block $b$ using w.r.t. a secret key. 
\item two-dimensional DCT transformation of $b$ and normalisation of coefficient
  w.r.t a  predefined quantization table. 
  Matrix is further referred to as $b'$. 
\item a fragment of $m'$ is embedded in some LSB of $b'$. Let $b''$ be the resulting matrix.
\item The matrix $b''$ is  decompressed back to the spatial domain leading to a new $B \times B$ block.
\end{enumerate}
\end{enumerate}



\subsection{nsF5}
The nsF5 algorithm~\cite{DBLP:conf/mmsec/FridrichPK07} extends the F5 
algorithm~\cite{DBLP:conf/ih/Westfeld01}.
Let us first have a closer look  on this latter

First of all, as far as we know, F5 is the first steganographic approach 
that solves the problem of remaining unchanged a part (often the end) 
of the file. 
To achieve this, a subset of all the LSB is computed thanks to a 
pseudorandom number generator seeded with a user defined key. 
%Such a feature is thus close to our that is based on chaos.
Next, this subset is split into blocks of $x$ bits.
The algorithm takes benefit of binary matrix embedding to
increase it efficiency. 
Let us explain this embedding on a small illustrative example where 
a part $m$ of the message  has to be embedded into this $x$ LSB of pixels   
which are respectively  a 3 bits column vector and a 7 bits column vector. 
Let then $H$ be the binary Hamming matrix  
$$
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 = Hy$.
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 
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  we obtain 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 = Hy$.
It is then possible to embed 3 bits in only 7 LSB of pixels by modifying 
on average $1-2^3$ changes. 
More generally, the F5 embedding efficiency should theoretically be 
$\frac{p}{1-2^p}$.

However, the event when the coefficient resulting from this LSB switch
becomes zero (usually referred to as \emph{shrinkage}) may occur.
In that case, the recipient cannot determine 
whether the coefficient was -1, +1 and has changed to 0 due to the algorithm or 
was  initially 0. 
The F5 scheme solves this problem first by defining a LSB  
with the  following (not even) function:
$$
LSB(x) = \left \{ 
\begin{array}{l}
1 - x \mod 2 \textrm{ if }  x< 0 \\
x \mod 2 \textrm{ otherwise.}
\end{array}
\right..
$$
An next, if the coefficient has to be changed to 0, the same bit message 
is re-embedded in the next group of $x$ coefficient LSB.

The scheme nsF5 focuses on steps of Hamming coding and ad'hoc shrinkage 
removing. It replaces them with a \emph{wet paper code} approach 
that is based on a random binary matrix. More precisely,
let $D$ be a random binary matrix of size $x \times n$ without replicate nor 
null columns: consider for instance a subset of $\{1, 2^x\}$ of cardinality $n$ 
and write them as binary numbers. The subset is generated thanks to a PRNG 
seeded with a shared key. In this block of size $x$, one choose to embed only 
$k$ elements of the message $m$. By abuse, the restriction of the message is again called $m$. It thus remains $x-k$ (wet) indexes/places where 
the information shouldn't be stored. Such indexes are generated too with the 
keyed PRNG. Let $v$ be defined by the following equation 

\begin{equation}
 Dv = \delta(m,Dx).
\end{equation}
This equation may be solved by Gaussian reduction or other more efficient
algorithms. If there is a solution, one have the list of indexes to modify 
into the cover. The nsF5 scheme implements such a optimized algorithm  
that is to say the LT codes.


\subsection{MMx}
Basically, the MMx algorithm~\cite{DBLP:conf/ih/KimDR06} embeds message 
in a selected set of LSB cover coefficients using Hamming
codes as the F5 scheme. However,
instead of reducing as many as possible the number of modified elements, 
this scheme aims at reducing the embedding impact. To achieve this it allows 
to modify more than one element if this leads to decrease distortion.

Let us start again with an example with a $[7,4]$ Hamming codes, \textit{i.e},
let us embed 3 bits into 7 DCT coefficients, $D_1, \ldots, D_7$. 
Without details, let $\rho_1, \ldots, \rho_7$ be the embedding impact whilst 
modifying coefficients $D_1, \ldots, D_7$ (see~\cite{DBLP:conf/ih/KimDR06} 
for a formal definition of $\rho$). Modifying element at index $j$ 
leads to a distortion equal to $\rho_j$. However, instead of switching 
the value at index $j$, one should consider to find all other columns  
of $H$, $j_1$, $j_2$ for instances, s.t. the sum of them 
is equal to the $j$th column and to compare $\rho_j$ with 
$\rho_{j_1} + \rho_{j_2}$. If one of these sums is less than $\rho_j$,
the sender has to change these coefficients instead of the $j$ one.
The number of searched indexes (2 for the previous example) gives the name 
of the algorithm. For instance in MM3, one check whether the message can be 
embedded by modifying each time 3 pixel or less.


\subsection{HUGO}
The HUGO~\cite{DBLP:conf/ih/PevnyFB10} steganographic scheme is mainly designed to minimize 
distortion caused by embedding. To achieve this, it is firstly based on an
image model given as SPAM~\cite{DBLP:journals/tifs/PevnyBF10}
features and next integrates image
correction to reduce much more distortion. 
What follows discuss on these two steps.

The former first computes the SPAM features. Such  calculi
synthesize the probabilities that the difference  
between consecutive horizontal (resp. vertical, diagonal) pixels 
belongs in a set of pixel values which are closed to the current pixel value
and whose radius is a parameter of the approach.  
Thus a fisher linear discriminant method defines the radius and  
chooses between directions (horizontal, vertical\ldots) of analyzed pixels
that gives the best separator for detecting embedding changes.
With such instantiated coefficients, HUGO can synthesize the embedding cost 
as a function $D(X,Y)$ that evaluates distortions between $X$ and $Y$. 
Then  HUGO computes the matrices of 
$\rho_{i,j} = \max(D(X,X^{(i,j)+})_{i,j}, D^-(X,X^{(i,j)-})_{i,j})$ 
such that $X^{(i,j)+}$ (resp. $X^{(i,j)+}$ ) is the cover image $X$ where 
the the $(i,j)$th pixel has been increased (resp. has been decreased) of 1.

The order of modifying pixel is critical: HUGO surprisingly 
modifies pixels in decreasing order of $\rho_{i,j}$. 
Starting with $Y=X$, it increases or decreases its $(i,j)$th pixel
to get the minimal value of 
$D(Y,Y^{(i,j)+})_{i,j}$ and  $D^-(Y,Y^{(i,j)-})_{i,j}$. 
The matrix $Y$ is thus updated  at each round.
