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

diff --git a/ourapproach.tex b/ourapproach.tex
index 5d16fd0..249e1be 100644
--- a/ourapproach.tex
+++ b/ourapproach.tex
@@ -3,12 +3,13 @@ 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 then presented  (Sect.~\ref{sub:extract}) and a running example ends this section (Sect.~\ref{sub:xpl}). 
+The message extraction is then presented  (Sect.~\ref{sub:extract}) while a running example ends this section (Sect.~\ref{sub:xpl}). 
 
 
 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.
+STABYLO, which stands for STe\-ga\-no\-gra\-phy with 
+Adaptive, Bbs, binarY embedding at LOw cost.
 What follows are successively some details of the inner steps and the flows both inside 
  the embedding stage (Fig.~\ref{fig:sch:emb}) 
 and inside the extraction one (Fig.~\ref{fig:sch:ext}).
@@ -16,21 +17,20 @@ Let us first focus on the data embedding.
 
 \begin{figure*}%[t]
   \begin{center}
-    \subfloat[Data Embedding.]{
-      \begin{minipage}{0.49\textwidth}
+    \subfloat[Data Embedding]{
+      \begin{minipage}{0.4\textwidth}
         \begin{center}
-          %\includegraphics[width=5cm]{emb.pdf}
-          \includegraphics[scale=0.45]{emb.ps}
+            %\includegraphics[scale=0.45]{emb}
+            \includegraphics[scale=0.4]{emb}
         \end{center}
       \end{minipage}
       \label{fig:sch:emb}
     } 
-
-    \subfloat[Data Extraction.]{
+\hfill
+    \subfloat[Data Extraction]{
       \begin{minipage}{0.49\textwidth}
         \begin{center}
-          %\includegraphics[width=5cm]{rec.pdf}
-          \includegraphics[scale=0.45]{rec.ps}
+            \includegraphics[scale=0.4]{dec}
         \end{center}
       \end{minipage}
       \label{fig:sch:ext}
@@ -48,13 +48,13 @@ Let us first focus on the data embedding.
 
 
 \subsection{Security considerations}\label{sub:bbs}
-Among methods of the message encryption/decryption 
+Among the 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 
+It has been 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 
@@ -89,7 +89,7 @@ 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, 
+In first order methods like Sobel, Canny~\cite{Canny:1986:CAE:11274.11275}, and so on, 
 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.
@@ -97,30 +97,31 @@ As far as fuzzy edge methods are concerned, they are obviously based on fuzzy lo
 
 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 fast, well known, has been studied in depth, and is implementable
-on many  kinds of architectures like FPGAs, smartphones,  desktop machines, and
+on many  kinds of architectures like FPGAs, smart phones,  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$. 
+More precisely, only $b$ most significant bits are concerned by this step, 
+where the parameter $b$ is practically set with $6$ or $7$. 
+Notice that 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.
 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.
-
-
-
+Moreover, to provide edge gradient value, 
+the Canny algorithm computes derivatives  
+in the two directions with respect to a mask of size $T$. 
+The higher $T$ is, the coarse the approach is. Practically, 
+$T$ is set with $3$, $3$, or $7$.
+In our flowcharts, this step is represented by ``Edge Detection(b, T, X)''.
 
 
 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.
+The next  section presents how to adapt our scheme 
+when the size of $x$  is not sufficient for the message $m$ to embed.
 
 
  
@@ -129,57 +130,43 @@ adapts  when the size of $x$  is not sufficient for the message $m$ to embed.
 
 
 \subsection{Adaptive embedding rate}\label{sub:adaptive}
-Two strategies have been developed in our scheme, 
+Two strategies have been developed in our approach, 
 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.
+Canny algorithm with parameters $b=7$ and $T=3$.
 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
+If $x$ is 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. 
 
- 
 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 
+a set of edge pixels related to increasing values of $T$ and 
 until its cardinality
-is sufficient. 
+is sufficient. Even in this situation, our scheme is adapting 
+its algorithm to meet all the user's requirements. 
 
 
-
-Two methods may further be applied to select bits that 
-will be modified. 
+Once the map of possibly modified pixels is computed, 
+two methods may further be applied to extract bits that 
+are really modified. 
 The first one randomly chooses the subset of pixels to modify by 
 applying the BBS PRNG again. This method is further denoted  as a \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}. 
+The second method considers the last significant bits of all the pixels 
+inside the previous map. It next directly applies the STC 
+algorithm~\cite{DBLP:journals/tifs/FillerJF11}. 
 It  is further referred to as \emph{STC} and is detailed in the next section.
 
 
 
 
 
-% 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.   
-
-
-
-
 
 
 
@@ -222,11 +209,13 @@ 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 
+More precisely,  let $b$ be the most significant bits and 
+$T$ be the size of the canny mask, both be given as a key.
+Thus, the same edge detection is applied on a stego content $Y$ 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.
+This inverse function takes the $\hat{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.
@@ -245,21 +234,21 @@ Lena and the first verses are given in Fig.~\ref{fig:lena}.
 \begin{center}
 \begin{minipage}{0.49\linewidth}
 \begin{center}
-\includegraphics[scale=0.20]{Lena.eps}
+\includegraphics[scale=0.20]{lena512}
 \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
+$\qquad$ The leaves they were crisped and sere—\linebreak
+$\qquad$ The leaves they were withering and sere;\linebreak
 It was night in the lonesome October\linebreak
-$~$ Of my most immemorial year;\linebreak
+$\qquad$ Of my most immemorial year;\linebreak
 It was hard by the dim lake of Auber,\linebreak
-$~$ In the misty mid region of Weir—\linebreak
+$\qquad$ 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.
+$\qquad$ In the ghoul-haunted woodland of Weir.
 \end{scriptsize}
 \end{flushleft}
 \end{minipage}
@@ -268,8 +257,11 @@ $~$ In the ghoul-haunted woodland of Weir.
 \end{figure}
 
 The edge detection returns 18,641 and 18,455 pixels when $b$ is
-respectively 7 and 6. These edges are represented in Figure~\ref{fig:edge}.
-
+respectively 7 and 6 and $T=3$.
+These edges are represented in Figure~\ref{fig:edge}.
+When $b$ is 7, it remains one bit per pixel to build the cover vector.
+This configuration leads to a cover vector of size  18,641 if b is 7 
+and 36,910 if $b$ is 6.  
 
 \begin{figure}[t]
   \begin{center}
@@ -277,7 +269,7 @@ respectively 7 and 6. These edges are represented in Figure~\ref{fig:edge}.
       \begin{minipage}{0.49\linewidth}
         \begin{center}
           %\includegraphics[width=5cm]{emb.pdf}
-          \includegraphics[scale=0.20]{edge7.eps}
+          \includegraphics[scale=0.20]{edge7}
         \end{center}
       \end{minipage}
       %\label{fig:sch:emb}
@@ -286,22 +278,31 @@ respectively 7 and 6. These edges are represented in Figure~\ref{fig:edge}.
       \begin{minipage}{0.49\linewidth}
         \begin{center}
           %\includegraphics[width=5cm]{rec.pdf}
-          \includegraphics[scale=0.20]{edge6.eps}
+          \includegraphics[scale=0.20]{edge6}
         \end{center}
       \end{minipage}
       %\label{fig:sch:ext}
     }%\hfill
   \end{center}
-  \caption{Edge detection wrt $b$}
+  \caption{Edge detection wrt $b$ with $T=3$}
   \label{fig:edge}
 \end{figure}
 
 
 
-Only 9,320 bits (resp. 9,227 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 
+The STC algorithm is optimized when the rate between message length and 
+cover vector length is lower than 1/2. 
+So, only 9,320 bits  are available for embedding 
+in the  configuration where $b$ is 7.
+
+When $b$ is 6, we could have considered 18,455 bits for the message.
+However, first experiments have shown that modifying this number of bits is too 
+easily detectable. 
+So, we choose to modify the same amount of bits (9,320) and keep STC optimizing
+which bits to change among  the 36,910 ones.
+
+In the two cases, about the third part of the poem is hidden into the cover. 
+Results with \emph{adaptive} and \textit{STC} strategies are presented in 
 Fig.~\ref{fig:lenastego}.
 
 \begin{figure}[t]
@@ -310,7 +311,7 @@ Fig.~\ref{fig:lenastego}.
       \begin{minipage}{0.49\linewidth}
         \begin{center}
           %\includegraphics[width=5cm]{emb.pdf}
-          \includegraphics[scale=0.20]{lena7.eps}
+          \includegraphics[scale=0.20]{lena7}
         \end{center}
       \end{minipage}
       %\label{fig:sch:emb}
@@ -319,7 +320,7 @@ Fig.~\ref{fig:lenastego}.
       \begin{minipage}{0.49\linewidth}
         \begin{center}
           %\includegraphics[width=5cm]{rec.pdf}
-          \includegraphics[scale=0.20]{lena6.eps}
+          \includegraphics[scale=0.20]{lena6}
         \end{center}
       \end{minipage}
       %\label{fig:sch:ext}
@@ -344,6 +345,8 @@ V_{ij}= \left\{
 \right..
 $$
 This function allows to emphasize differences between contents.
+Notice that 
+
 
 \begin{figure}[t]
   \begin{center}
@@ -351,21 +354,28 @@ This function allows to emphasize differences between contents.
       \begin{minipage}{0.49\linewidth}
         \begin{center}
           %\includegraphics[width=5cm]{emb.pdf}
-          \includegraphics[scale=0.20]{diff7.eps}
+          \includegraphics[scale=0.20]{diff7}
         \end{center}
       \end{minipage}
-      %\label{fig:sch:emb}
+      \label{fig:diff7}
     }%\hfill
     \subfloat[$b$ is 6.]{
       \begin{minipage}{0.49\linewidth}
         \begin{center}
           %\includegraphics[width=5cm]{rec.pdf}
-          \includegraphics[scale=0.20]{diff6.eps}
+          \includegraphics[scale=0.20]{diff6}
         \end{center}
       \end{minipage}
-      %\label{fig:sch:ext}
+      \label{fig:diff6}
     }%\hfill
   \end{center}
   \caption{Differences  with Lena's cover  wrt $b$}
   \label{fig:lenadiff}
 \end{figure}
+
+
+Notice that since $b$ is 7 in Fig.~\ref{fig:diff7}, the embedding is binary 
+and this image only contains 0 and 75 values.
+Similarly, when $b$ is 6 as in Fig.~\ref{fig:diff6}, the embedding is ternary 
+and the image contains all the values in $\{0,75,150,225\}$.
+