X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/blobdiff_plain/e477428ed31d945b364bd9064476c1f0a34f86ef..fdec47fad10cd693dc899d18ba02c166c1f5349f:/ourapproach.tex?ds=inline diff --git a/ourapproach.tex b/ourapproach.tex index f86c8ae..12b3a32 100644 --- a/ourapproach.tex +++ b/ourapproach.tex @@ -3,39 +3,40 @@ 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}). +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. -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}). +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}). Let us first focus on the data embedding. -\begin{figure*}[t] +\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.5]{emb.ps} + %\includegraphics[scale=0.45]{emb} + \includegraphics[scale=0.4]{emb} \end{center} \end{minipage} \label{fig:sch:emb} - }%\hfill - \subfloat[Data Extraction.]{ + } +\hfill + \subfloat[Data Extraction]{ \begin{minipage}{0.49\textwidth} \begin{center} - %\includegraphics[width=5cm]{rec.pdf} - \includegraphics[scale=0.5]{rec.ps} + \includegraphics[scale=0.4]{dec} \end{center} \end{minipage} \label{fig:sch:ext} }%\hfill \end{center} - \caption{The STABYLO Scheme.} + \caption{The STABYLO scheme} \label{fig:sch} \end{figure*} @@ -46,18 +47,20 @@ Let us first focus on the data embedding. -\subsection{Security Considerations}\label{sub:bbs} -Among methods of message encryption/decryption +\subsection{Security considerations}\label{sub:bbs} +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} +we implement the asymmetric +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 +The main justification of this choice +is that 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 -which allows to find $x_{i-1}$ and $x_{i+L}$ with a probability greater +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, @@ -69,7 +72,7 @@ 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} +\subsection{Edge-based image steganography}\label{sub:edge} The edge-based image @@ -88,38 +91,41 @@ 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. -As for as fuzzy edge methods are concerned, they are obviously based on fuzzy logic to highlight 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 +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, 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$, $5$, 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 section presentsd 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 +with respect to the size +of the message $m$ to embed and the size of the cover $x$. + @@ -127,49 +133,40 @@ 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, -depending on the embedding rate that is either \emph{adaptive} or \emph{fixed}. +\subsection{Adaptive embedding rate}\label{sub:adaptive} +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 an 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 to short for $m$, the message is splitted 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 to \emph{sample}. -The second one is a direct application of the -STC algorithm~\cite{DBLP:journals/tifs/FillerJF11}. -It is further referred to as \emph{adaptive+STC} and is detailled in the nex section. - - - - +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 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. @@ -177,7 +174,7 @@ It is further referred to as \emph{adaptive+STC} and is detailled in the nex se -\subsection{Minimizing Distortion with Syndrome-Treillis Codes}\label{sub:stc} +\subsection{Minimizing distortion with Syndrome-Trellis Codes}\label{sub:stc} \input{stc} @@ -211,41 +208,51 @@ It is further referred to as \emph{adaptive+STC} and is detailled in the nex se -\subsection{Data Extraction}\label{sub:extract} -The message extraction summarized in Fig.~\ref{fig:sch:ext} follows data embedding +\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. -First of all, the same edge detection is applied (on the 7 first bits) to -get the set of LSBs, -which is sufficiently large with respect to the message size given as a key. -Then the STC reverse algorithm is applied to retrieve the encrypted message. + +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 $\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. 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*512 image with 256 grayscale levels. +\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 the first verses are given in Fig.~\ref{fig:lena}. +words, and 3,754 characters, \textit{i.e.}, 30,032 bits. +Lena and the first verses are given in Fig.~\ref{fig:lena}. \begin{figure} \begin{center} -\begin{minipage}{0.4\linewidth} -\includegraphics[width=3cm]{Lena.eps} +\begin{minipage}{0.49\linewidth} +\begin{center} +\includegraphics[scale=0.20]{lena512} +\end{center} \end{minipage} -\begin{minipage}{0.59\linewidth} +\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} @@ -253,9 +260,12 @@ $~$ In the ghoul-haunted woodland of Weir. \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 Fig.~\ref{fig:edge} - +The edge detection returns 18,641 and 18,455 pixels when $b$ is +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} @@ -263,7 +273,7 @@ respectively 7 and 6. These edges are represented in Fig.~\ref{fig:edge} \begin{minipage}{0.49\linewidth} \begin{center} %\includegraphics[width=5cm]{emb.pdf} - \includegraphics[scale=0.15]{edge7.eps} + \includegraphics[scale=0.20]{edge7} \end{center} \end{minipage} %\label{fig:sch:emb} @@ -272,22 +282,31 @@ respectively 7 and 6. These edges are represented in Fig.~\ref{fig:edge} \begin{minipage}{0.49\linewidth} \begin{center} %\includegraphics[width=5cm]{rec.pdf} - \includegraphics[scale=0.15]{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} -In the former configuration, only 9320 bits are available -for embeding whereas in the latter we have 9227. -In the both case, 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 {Adaptive} and {STC} strategies are presented in Fig.~\ref{fig:lenastego}. \begin{figure}[t] @@ -296,7 +315,7 @@ Fig.~\ref{fig:lenastego}. \begin{minipage}{0.49\linewidth} \begin{center} %\includegraphics[width=5cm]{emb.pdf} - \includegraphics[scale=0.15]{lena7.eps} + \includegraphics[scale=0.20]{lena7} \end{center} \end{minipage} %\label{fig:sch:emb} @@ -305,32 +324,37 @@ Fig.~\ref{fig:lenastego}. \begin{minipage}{0.49\linewidth} \begin{center} %\includegraphics[width=5cm]{rec.pdf} - \includegraphics[scale=0.15]{lena6.eps} + \includegraphics[scale=0.20]{lena6} \end{center} \end{minipage} %\label{fig:sch:ext} }%\hfill \end{center} - \caption{Stego Images wrt $b$.} + \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 pixel pair of picel $X_{ij}$ -$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 +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 \\ -75 & \textrm{if} & \abs{ (X_{ij} - Y_{ij})} = 2 \\ -225 & \textrm{if} & \abs{ (X_{ij} - Y_{ij})} = 1 +75 & \textrm{if} & \vert X_{ij} - Y_{ij} \vert = 1 \\ +150 & \textrm{if} & \vert X_{ij} - Y_{ij} \vert = 2 \\ +225 & \textrm{if} & \vert X_{ij} - Y_{ij} \vert = 3 \end{array} -\right. -$$. -This function allows to emphase differences between content. +\right.. +$$ +This function allows to emphasize differences between contents. +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, if $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\}$. + + \begin{figure}[t] \begin{center} @@ -338,21 +362,24 @@ This function allows to emphase differences between content. \begin{minipage}{0.49\linewidth} \begin{center} %\includegraphics[width=5cm]{emb.pdf} - \includegraphics[scale=0.15]{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.15]{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$.} + \caption{Differences with Lena's cover wrt $b$} \label{fig:lenadiff} \end{figure} + + +