X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/blobdiff_plain/e109e0d899bc233ae4407afe3af6ca03e1afe90a..244797b85f1e232852b9374a76fe7139ed4cccfb:/ourapproach.tex?ds=sidebyside

diff --git a/ourapproach.tex b/ourapproach.tex
index ccd297b..e6f3d4a 100644
--- a/ourapproach.tex
+++ b/ourapproach.tex
@@ -1,85 +1,371 @@
-The flowcharts given in Fig.~\ref{fig:sch} summarize our steganography scheme denoted as to
-STABYLO for STeganography with cAnny, Bbs, binarY embedding at LOw cost.
-What follows successively details all the inner steps and flow inside 
-the embedding stage (Fig.\ref{fig:sch:emb}) 
-and inside the extraction one(Fig.~\ref{fig:sch:ext}).
+This section first presents the embedding scheme through its 
+four main steps: the data encryption (Sect.~\ref{sub:bbs}),
+the cover pixel selection (Sect.~\ref{sub:edge}),
+the adaptive payload considerations (Sect.~\ref{sub:adaptive}),
+and how the distortion has been minimized (Sect.~\ref{sub:stc}).
+The message extraction is finally presented  (Sect.~\ref{sub:extract}) and a running example ends this section (Sect.~\ref{sub:xpl}). 
 
 
-\begin{figure*}[t]
+The flowcharts given in Fig.~\ref{fig:sch}
+summarize our steganography scheme denoted by
+STABYLO, which stands for STeganography with cAnny, Bbs, binarY embedding at LOw cost.
+What follows are successively details of the inner steps and flows inside 
+both the embedding stage (Fig.~\ref{fig:sch:emb}) 
+and the extraction one (Fig.~\ref{fig:sch:ext}).
+Let us first focus on the data embedding. 
+
+\begin{figure*}%[t]
   \begin{center}
     \subfloat[Data Embedding.]{
       \begin{minipage}{0.49\textwidth}
         \begin{center}
-%          \includegraphics[width=5cm]{emb.pdf}
-          \includegraphics[width=5cm]{emb.ps}
+          %\includegraphics[width=5cm]{emb.pdf}
+          \includegraphics[scale=0.45]{emb.ps}
         \end{center}
       \end{minipage}
       \label{fig:sch:emb}
-    }%\hfill
+    } 
+
     \subfloat[Data Extraction.]{
       \begin{minipage}{0.49\textwidth}
         \begin{center}
-%          \includegraphics[width=5cm]{rec.pdf}
-          \includegraphics[width=5cm]{rec.ps}
+          %\includegraphics[width=5cm]{rec.pdf}
+          \includegraphics[scale=0.45]{rec.ps}
         \end{center}
       \end{minipage}
       \label{fig:sch:ext}
     }%\hfill
   \end{center}
-  \caption{The STABYLO Scheme.}
+  \caption{The STABYLO scheme}
   \label{fig:sch}
 \end{figure*}
 
 
 
 
-\subsection{Data Embedding} 
 
 
 
 
-\subsubsection{Edge Based Image Steganography}
-Image Quality: Edge Image Steganography
-\JFC{Raphael, les fuzzy edge detection sont souvent utilisÃ©s. 
-  il faudrait comparer les approches en terme de nombre de bits retournÃ©s,
-  en terme de complexitÃ©. } \cite{KF11}
-\RC{Ben, Ã  voir car on peut choisir le nombre de pixel avec canny. Supposons que les fuzzy edge soient retourne un peu plus de points, on sera probablement plus dÃ©tectable...  Finalement on devrait surement vendre notre truc en : on a choisi cet algo car il est performant en vitesse/qualitÃ©. Mais on peut aussi en utilisÃ© d'autres :-)}
+\subsection{Security considerations}\label{sub:bbs}
+Among methods of message encryption/decryption 
+(see~\cite{DBLP:journals/ejisec/FontaineG07} for a survey)
+we implement the Blum-Goldwasser cryptosystem~\cite{Blum:1985:EPP:19478.19501}
+that is based on the Blum Blum Shub~\cite{DBLP:conf/crypto/ShubBB82} 
+pseudorandom number generator (PRNG) and the 
+XOR binary function.
+It has been indeed proven~\cite{DBLP:conf/crypto/ShubBB82} that this PRNG 
+has the property of cryptographical security, \textit{i.e.}, 
+for any sequence of $L$ output bits $x_i$, $x_{i+1}$, \ldots, $x_{i+L-1}$,
+there is no algorithm, whose time complexity is polynomial  in $L$, and 
+which allows to find $x_{i-1}$ or $x_{i+L}$ with a probability greater
+than $1/2$.
+Equivalent formulations of such a property can
+be found. They all lead to the fact that,
+even if the encrypted message is extracted, 
+it is impossible to retrieve the original one in 
+polynomial time.   
+
+Starting thus with a key $k$ and the message \textit{mess} to hide, 
+this step computes a message $m$, which is the encrypted version  of \textit{mess}.
+
+
+\subsection{Edge-based image steganography}\label{sub:edge}
+
+
+The edge-based image
+steganography schemes 
+already presented \cite{Luo:2010:EAI:1824719.1824720,DBLP:journals/eswa/ChenCL10} differ 
+in how carefully they select edge pixels, and  
+how they modify them.
+
+%Image Quality: Edge Image Steganography
+%\JFC{Raphael, les fuzzy edge detection sont souvent utilisÃ©s. 
+%  il faudrait comparer les approches en terme de nombre de bits retournÃ©s,
+%  en terme de complexitÃ©. } \cite{KF11}
+%\RC{Ben, Ã  voir car on peut choisir le nombre de pixel avec Canny. Supposons que les fuzzy edge soient retourne un peu plus de points, on sera probablement plus dÃ©tectable...  Finalement on devrait surement vendre notre truc en : on a choisi cet algo car il est performant en vitesse/qualitÃ©. Mais on peut aussi en utilisÃ© d'autres :-)}
+
+Many techniques have been proposed in the literature to  detect 
+edges in  images (whose noise has been initially reduced). 
+They can be separated in two categories: first and second order detection
+methods on the one hand, and fuzzy detectors on the other  hand~\cite{KF11}.
+In first order methods like Sobel, Canny~\cite{Canny:1986:CAE:11274.11275}, \ldots, 
+a first-order derivative (gradient magnitude, etc.) is computed 
+to search for local maxima, whereas in second order ones, zero crossings in a second-order derivative, like the Laplacian computed from the image,
+are searched in order to find edges.
+As far as fuzzy edge methods are concerned, they are obviously based on fuzzy logic to highlight edges.
+
+Canny filters, on their parts, are an old family of algorithms still remaining a state of the art edge detector. They can be well-approximated by first-order derivatives of Gaussians.
+As the Canny algorithm is well known and studied, fast, and implementable
+on many  kinds of architectures like FPGAs, smartphones,  desktop machines, and
+GPUs, we have chosen this edge detector for illustrative purpose.
+
+%\JFC{il faudrait comparer les complexites des algo fuzy and canny}
+
+
+This edge detection is applied on a filtered version of the image given 
+as input.
+More precisely, only $b$ most 
+significant bits are concerned by this step, where 
+the parameter $b$ is practically set with $6$ or $7$. 
+If set with the same value $b$, the edge detection returns thus the same 
+set of pixels for both the cover and the stego image.   
+In our flowcharts, this is represented by ``edgeDetection(b bits)''.
+Then only the 2 LSBs of pixels in the set of edges are returned if $b$ is 6, 
+and the LSB of pixels if $b$ is 7.
+
+
+
+
+
+Let $x$ be the sequence of these bits. 
+The next  section presents how our scheme 
+adapts  when the size of $x$  is not sufficient for the message $m$ to embed.
+
+
+ 
 
-There are  many techniques to  detect edges in  images. Main methods  are filter
-edge detection methods such as Sobel  or Canny filter, low order methods such as
-first order  and second order  methods, these methods  are based on  gradient or
-Laplace  operators and  fuzzy edge  methods which  are based  on fuzzy  logic to
-highlight edges.
 
-Of course, all the algorithms have  advantages and drawbacks which depend on the
-motivation  to  highlight  edges.   Unfortunately  unless testing  most  of  the
-algorithms, which  would require many  times, it is  quite difficult to  have an
-accurate idea on what would produce  such algorithm compared to another. That is
-why we have  chosen canny algorithm which is well  known, fast and implementable
-on many  kinds of architecture, such  as FPGA, smartphone,  desktop machines and
-GPU. And of course, we do not pretend that this is the best solution.
 
-Presentation des algos de detection de contour
-CaractÃ©ristiques
 
-Comparaison thÃ©oriques, rÃ©fÃ©rences
+\subsection{Adaptive embedding rate}\label{sub:adaptive}
+Two strategies have been developed in our scheme, 
+depending on the embedding rate that is either \emph{adaptive} or \emph{fixed}.
+In the former the embedding rate depends on the number of edge pixels.
+The higher it is, the larger the message length that can be inserted is.
+Practically, a set of edge pixels is computed according to the 
+Canny algorithm with a high threshold.
+The message length is thus defined to be less than 
+half of this set cardinality.
+If $x$ is then too short for $m$, the message is split into sufficient parts
+and a new cover image should be used for the remaining part of the message. 
 
-Algo de stegano basÃ© juste sur cela : (pas de bbs, pas de stc, mÃªme message).
+ 
+In the latter, the embedding rate is defined as a percentage between the 
+number of modified pixels and the length of the bit message.
+This is the classical approach adopted in steganography.
+Practically, the Canny algorithm generates  
+a set of edge pixels related to a threshold that is decreasing 
+until its cardinality
+is sufficient. 
 
-Quels paramÃ¨tres sont optimaux ? Combinaison ? 
 
 
+Two methods may further be applied to select bits that 
+will be modified. 
+The first one randomly chooses the subset of pixels to modify by 
+applying the BBS PRNG again. This method is further denoted  as to \emph{sample}.
+Once this set is selected, a classical LSB replacement is applied to embed the 
+stego content.
+The second method is a direct application of the 
+STC algorithm~\cite{DBLP:journals/tifs/FillerJF11}. 
+It  is further referred to as \emph{STC} and is detailed in the next section.
 
 
 
-\subsubsection{Security Considerations}
 
-Security aspect:
-BBS-based cryptographic version of the message 
 
-\subsubsection{Minimizing Distortion with Syndrome-Treillis Codes} 
+% First of all, let us discuss about compexity of edge detetction methods.
+% Let then $M$ and $N$ be the dimension of the original image. 
+% According to~\cite{Hu:2007:HPE:1282866.1282944},
+% even if the fuzzy logic based edge detection methods~\cite{Tyan1993} 
+% have promising results, its complexity is in $C_3 \times O(M \times N)$
+% whereas the complexity on the Canny method~\cite{Canny:1986:CAE:11274.11275} 
+% is in $C_1 \times O(M \times N)$ where  $C_1 < C_3$.
+% \JFC{Verifier ceci...}
+% In experiments detailled in this article, the Canny method has been retained 
+% but the whole approach can be updated to consider 
+% the fuzzy logic edge detector.   
 
+
+
+
+
+
+
+\subsection{Minimizing distortion with syndrome-trellis codes}\label{sub:stc}
 \input{stc}
 
 
-\subsection{Data Extraction}
+
+% Edge Based Image Steganography schemes 
+% already studied~\cite{Luo:2010:EAI:1824719.1824720,DBLP:journals/eswa/ChenCL10,DBLP:conf/ih/PevnyFB10} differ 
+% how they select edge pixels, and  
+% how they modify these ones.
+
+% First of all, let us discuss about compexity of edge detetction methods.
+% Let then $M$ and $N$ be the dimension of the original image. 
+% According to~\cite{Hu:2007:HPE:1282866.1282944},
+% even if the fuzzy logic based edge detection methods~\cite{Tyan1993} 
+% have promising results, its complexity is in $C_3 \times O(M \times N)$
+% whereas the complexity on the Canny method~\cite{Canny:1986:CAE:11274.11275} 
+% is in $C_1 \times O(M \times N)$ where  $C_1 < C_3$.
+% \JFC{Verifier ceci...}
+% In experiments detailled in this article, the Canny method has been retained 
+% but the whole approach can be updated to consider 
+% the fuzzy logic edge detector.   
+
+% Next, following~\cite{Luo:2010:EAI:1824719.1824720}, our scheme automatically
+% modifies Canny parameters to get a sufficiently large set of edge bits: this 
+% one is practically enlarged untill its size is at least twice as many larger 
+% than the size of embedded message.
+
+
+
+%%RAPH: paragraphe en double :-)
+
+
+
+
+\subsection{Data extraction}\label{sub:extract}
+The message extraction summarized in Fig.~\ref{fig:sch:ext} 
+follows the data embedding approach 
+since there exists a reverse function for all its steps.
+
+More precisely, the same edge detection is applied on the $b$ first bits  to 
+produce the sequence $y$ of LSBs. 
+If the STC approach has been selected in embedding, the STC reverse
+algorithm is directly executed to retrieve the encrypted message. 
+This inverse function takes the $H$ matrix as a parameter.
+Otherwise, \textit{i.e.}, if the \emph{sample} strategy is retained,
+the same random bit selection than in the embedding step 
+is executed with the same seed, given as a key.
+Finally, the Blum-Goldwasser decryption function is executed and the original
+message is extracted.
+
+
+\subsection{Running example}\label{sub:xpl}
+In this example, the cover image is  Lena, 
+which is a $512\times512$  image with 256 grayscale levels.
+The message is the poem Ulalume (E. A. Poe), which is constituted by 104 lines, 667
+words, and 3754 characters, \textit{i.e.},  30032 bits.
+Lena and the first verses are given in Fig.~\ref{fig:lena}.
+
+\begin{figure}
+\begin{center}
+\begin{minipage}{0.49\linewidth}
+\begin{center}
+\includegraphics[scale=0.20]{Lena.eps}
+\end{center}
+\end{minipage}
+\begin{minipage}{0.49\linewidth}
+\begin{flushleft}
+\begin{scriptsize}
+The skies they were ashen and sober;\linebreak
+$~$ The leaves they were crisped and sereâ\linebreak
+$~$ The leaves they were withering and sere;\linebreak
+It was night in the lonesome October\linebreak
+$~$ Of my most immemorial year;\linebreak
+It was hard by the dim lake of Auber,\linebreak
+$~$ In the misty mid region of Weirâ\linebreak
+It was down by the dank tarn of Auber,\linebreak
+$~$ In the ghoul-haunted woodland of Weir.
+\end{scriptsize}
+\end{flushleft}
+\end{minipage}
+\end{center}
+\caption{Cover and message examples} \label{fig:lena}
+\end{figure}
+
+The edge detection returns 18641 and 18455 pixels when $b$ is
+respectively 7 and 6. These edges are represented in Figure~\ref{fig:edge}.
+
+
+\begin{figure}[t]
+  \begin{center}
+    \subfloat[$b$ is 7.]{
+      \begin{minipage}{0.49\linewidth}
+        \begin{center}
+          %\includegraphics[width=5cm]{emb.pdf}
+          \includegraphics[scale=0.20]{edge7.eps}
+        \end{center}
+      \end{minipage}
+      %\label{fig:sch:emb}
+    }%\hfill
+    \subfloat[$b$ is 6.]{
+      \begin{minipage}{0.49\linewidth}
+        \begin{center}
+          %\includegraphics[width=5cm]{rec.pdf}
+          \includegraphics[scale=0.20]{edge6.eps}
+        \end{center}
+      \end{minipage}
+      %\label{fig:sch:ext}
+    }%\hfill
+  \end{center}
+  \caption{Edge detection wrt $b$}
+  \label{fig:edge}
+\end{figure}
+
+
+
+Only 9320 bits (resp. 9227 bits) are available for embedding 
+in the former configuration where $b$ is 7 (resp. where $b$ is 6).
+In both cases, about the third part of the poem is hidden into the cover.
+Results with \emph{adaptive+STC} strategy are presented in 
+Fig.~\ref{fig:lenastego}.
+
+\begin{figure}[t]
+  \begin{center}
+    \subfloat[$b$ is 7.]{
+      \begin{minipage}{0.49\linewidth}
+        \begin{center}
+          %\includegraphics[width=5cm]{emb.pdf}
+          \includegraphics[scale=0.20]{lena7.eps}
+        \end{center}
+      \end{minipage}
+      %\label{fig:sch:emb}
+    }%\hfill
+    \subfloat[$b$ is 6.]{
+      \begin{minipage}{0.49\linewidth}
+        \begin{center}
+          %\includegraphics[width=5cm]{rec.pdf}
+          \includegraphics[scale=0.20]{lena6.eps}
+        \end{center}
+      \end{minipage}
+      %\label{fig:sch:ext}
+    }%\hfill
+  \end{center}
+  \caption{Stego images wrt $b$}
+  \label{fig:lenastego}
+\end{figure}
+
+
+Finally, differences between the original cover and the stego images  
+are presented in Fig.~\ref{fig:lenadiff}. For each pair of pixel $X_{ij}$ and  $Y_{ij}$ ($X$ and $Y$ being the cover and the stego content respectively), 
+the pixel value $V_{ij}$ of the difference is defined with the following map
+$$
+V_{ij}= \left\{
+\begin{array}{rcl}
+0 & \textrm{if} &  X_{ij} = Y_{ij} \\
+75 & \textrm{if} &  \abs{ X_{ij} - Y_{ij}} = 1 \\
+150 & \textrm{if} &  \abs{ X_{ij} - Y_{ij}} = 2 \\
+225 & \textrm{if} &  \abs{ X_{ij} - Y_{ij}} = 3 
+\end{array}
+\right..
+$$
+This function allows to emphasize differences between contents.
+
+\begin{figure}[t]
+  \begin{center}
+    \subfloat[$b$ is 7.]{
+      \begin{minipage}{0.49\linewidth}
+        \begin{center}
+          %\includegraphics[width=5cm]{emb.pdf}
+          \includegraphics[scale=0.20]{diff7.eps}
+        \end{center}
+      \end{minipage}
+      %\label{fig:sch:emb}
+    }%\hfill
+    \subfloat[$b$ is 6.]{
+      \begin{minipage}{0.49\linewidth}
+        \begin{center}
+          %\includegraphics[width=5cm]{rec.pdf}
+          \includegraphics[scale=0.20]{diff6.eps}
+        \end{center}
+      \end{minipage}
+      %\label{fig:sch:ext}
+    }%\hfill
+  \end{center}
+  \caption{Differences  with Lena's cover  wrt $b$}
+  \label{fig:lenadiff}
+\end{figure}
