X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/blobdiff_plain/5e6f9e49a26cec4970434722a595a7b44197120f..80ed315cbcd8cb8806910d30bc116bfdb4f87fb8:/stc.tex diff --git a/stc.tex b/stc.tex index 7ce100b..5e5b66e 100644 --- a/stc.tex +++ b/stc.tex @@ -1,28 +1,32 @@ +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 of the image $X$, -$m$ be the message to embed and +$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 embbeding impact of replacing $x$ by $y$ in $X$ +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$ -expressed 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. +$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. -Some steganographic +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 -$\rho_X(i,x,y)$ is identically equal to 1, $m$ and $x$ are respectively a 3 bits column -vector and a 7 bits column vector. -Let then $H$ be the binary Hamming matrix +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 \\ @@ -30,11 +34,11 @@ H = \left( \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} @@ -45,38 +49,39 @@ $$ \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$, +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 = Hy$. -It is then possible to embed 3 bits in only 7 LSB of pixels by modifying -1 bit at most. -In the general case, when comunicating $n$ message bits in -$2^n-1$ pixels needs $1-1/2^n$ average changes. - +$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. - -Unfortunately, for any given $H$, finding $y$ that solves $Hy=m$ and that -that minimizes $D_X(x,y)$ has exponential complexity with respect to $n$. -The Syndrome-Trellis Codes (STC) -presented by Filler et al. in~\cite{DBLP:conf/mediaforensics/FillerJF10} +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 resspect to $n$. +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 -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 a forward and a backward part: +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 Backward determinization of $y$ which minimizes $D$ starting with -the complete path with minimal weight +\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} -