ajout complexité WOW et UNIWARD

[canny.git] / stc.tex

diff --git a/stc.tex b/stc.tex
index e98589facf56445e0f8a40c6ffa0399863a1e3b1..db985853fa8dd98b21b8c676d242e8f4d65e4f63 100644 (file)
--- a/stc.tex
+++ b/stc.tex
@@ -1,13 +1,14 @@
+To make this article self-contained, this section recalls
+the basis of the Syndrome Treillis Codes  (STC).
+

 Let 
 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$.
 $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. 
 The objective is thus to find $y$ that minimizes $D_X(x,y)$.
 
 Hamming embedding proposes a solution to this problem. 


@@ -17,10 +18,12 @@ 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$ for a given binary matrix $H$. 
 
 Let us explain this embedding on a small illustrative example where

-$\rho_X(i,x,y)$ is identically 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 $0$ otherwise).  
+
+Let  $H$ be the binary Hamming matrix  

 $$
 H = \left(
 \begin{array}{lllllll}
 $$
 H = \left(
 \begin{array}{lllllll}


@@ -51,32 +54,33 @@ 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$.
 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
+It is then possible to embed 3 bits in 7 LSBs of pixels by modifying

 at most 1 bit.
 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 embeding is really efficient to very small payload and is 
+not well suited when the size of the message is larger, as in real situation.
+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$. 
 that minimizes $D_X(x,y)$, has an exponential complexity with respect to $n$. 

-The Syndrome-Trellis Codes  (STC) 
-presented by Filler \emph{et al.} in~\cite{DBLP:conf/mediaforensics/FillerJF10} 
+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$.
 
 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 et al. compute the matrix $H$
-by placing a small sub-matrix $\hat{H}$ of size $h × w$ next
-to each other and shifted down by one row. 
+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
 Thanks to this special form of $H$, one can represent

-every solution of  $m=Hy$ as a path through a trellis.
+any solution of  $m=Hy$ as a path through a trellis.

 
 

-Next, the  process of finding $y$ consists of two stages: a forward and a backward part.
+Next, the  process of finding $y$ consists in two stages: a forward and a backward part.

 \begin{enumerate}
 \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 
 \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} 
 
 
 \end{enumerate} 
 
 

-