From: couchot Date: Tue, 10 Dec 2013 10:59:16 +0000 (+0100) Subject: ajout de complexite X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/commitdiff_plain/4b63033789d12bbc41ec23cb66990c458be402b0?ds=sidebyside;hp=-c ajout de complexite --- 4b63033789d12bbc41ec23cb66990c458be402b0 diff --git a/main.tex b/main.tex index 10eaa19..0f789bd 100755 --- a/main.tex +++ b/main.tex @@ -103,6 +103,7 @@ a scheme that can reasonably face up-to-date steganalysers. \section{Presentation of the Proposed Approach}\label{sec:ourapproach} \input{ourapproach.tex} + \section{Experiments}\label{sec:experiments} \input{experiments} diff --git a/ourapproach.tex b/ourapproach.tex index 5d16fd0..e87c148 100644 --- a/ourapproach.tex +++ b/ourapproach.tex @@ -369,3 +369,38 @@ This function allows to emphasize differences between contents. \caption{Differences with Lena's cover wrt $b$} \label{fig:lenadiff} \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. + + + + +