From: couchot <jf.couchot@gmail.com>
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=inline

ajout de complexite
---

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. 
+
+
+
+
+