X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/blobdiff_plain/4b63033789d12bbc41ec23cb66990c458be402b0..57f6acd69b21dc27e72b1d6f5b4515e1baf56b5b:/ourapproach.tex diff --git a/ourapproach.tex b/ourapproach.tex index e87c148..636b8ba 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,7 +17,7 @@ Let us first focus on the data embedding. \begin{figure*}%[t] \begin{center} - \subfloat[Data Embedding.]{ + \subfloat[Data Embedding]{ \begin{minipage}{0.49\textwidth} \begin{center} %\includegraphics[width=5cm]{emb.pdf} @@ -26,7 +27,7 @@ Let us first focus on the data embedding. \label{fig:sch:emb} } - \subfloat[Data Extraction.]{ + \subfloat[Data Extraction]{ \begin{minipage}{0.49\textwidth} \begin{center} %\includegraphics[width=5cm]{rec.pdf} @@ -48,13 +49,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 +90,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,7 +98,7 @@ 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} @@ -112,15 +113,15 @@ 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. +and the LSBs 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. +The next section presents how to adapt our scheme + when the size of $x$ is not sufficient for the message $m$ to embed. @@ -129,7 +130,7 @@ 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. @@ -137,7 +138,7 @@ 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 +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. @@ -147,39 +148,26 @@ 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. +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. - - - - @@ -252,14 +240,14 @@ Lena and the first verses are given in Fig.~\ref{fig:lena}. \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} @@ -269,7 +257,9 @@ $~$ In the ghoul-haunted woodland of Weir. 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}. - +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} @@ -298,9 +288,18 @@ respectively 7 and 6. These edges are represented in Figure~\ref{fig:edge}. -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. +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+STC} strategy are presented in Fig.~\ref{fig:lenastego}. @@ -371,36 +370,3 @@ This function allows to emphasize differences between contents. \end{figure} - -\section{Complexity Analysis}\label{sub:complexity} -This section aims at justifying the leightweight attribute of our approach. -To be more precise, we compare the complexity of our schemes to the -state of the art steganography, namely HUGO~\cite{DBLP:conf/ih/PevnyFB10}. - - -In what folllows, we consider an $n \times n$ square image. -First of all, HUGO starts with computing the second order SPAM Features. -This steps is in $O(n^2 + 2.343^2)$ due to the calculation -of the difference arrays and next of the 686 features (of size 343). -Next for each pixel, the distortion measure is calculated by +1/-1 modifying -its value and computing again the SPAM -features. Pixels are thus selected according to their ability to provide -an image whose SPAM features are close to the original one. -The algorithm is thus computing a distance between each Feature, -which is at least in $O(343)$ and an overall distance between these -metrics which is in $O(686)$. Computing the distance is thus in -$O(2\time 343^2)$ and this mdification is thus in $O(2\time 343^2 \time n^2)$. -Ranking these results may be achieved with a insertion sort which is in $2.n^2 \ln(n)$. -The overall complexity of the pixel selection is thus -$O(n^2 +2.343^2 + 2\time 343^2 \time n^2 + 2.n^2 \ln(n))$, \textit{i.e} -$O(2.n^2(343^2 + \ln(n)))$. - -Our edge selection is based on a Canny Filter, -whose complexity is in $O(2n^2.\ln(n))$ thanks to the convolution step -which can be implemented with FFT. -The complexity of Hugo is at least $343^2/\ln{n}$ times higher than our scheme. - - - - -