ajout complexité WOW et UNIWARD

[canny.git] / complexity.tex

diff --git a/complexity.tex b/complexity.tex
index e2f0203c03e9854be80a7fa38783764e5fc9a46a..e4e6b0e91529cf167bd1f4664455054f17f5e70a 100644 (file)
--- a/complexity.tex
+++ b/complexity.tex
@@ -4,9 +4,11 @@ To be more precise, we compare the complexity of our schemes to some of
 current state of the art of 
 steganographic scheme, namely HUGO~\cite{DBLP:conf/ih/PevnyFB10},
 WOW~\cite{conf/wifs/HolubF12}, and UNIWARD~\cite{HFD14}.
 current state of the art of 
 steganographic scheme, namely HUGO~\cite{DBLP:conf/ih/PevnyFB10},
 WOW~\cite{conf/wifs/HolubF12}, and UNIWARD~\cite{HFD14}.

+Each of these scheme starts with the computation of the distortion cost 
+for each pixel switch and is later followed by the STC algorithm.
+Since this last step is shared by all, we do not add its complexity.
+In all the rest of this section, we consider a $n \times n$ square image. 

 
 

-
-In what follows, we consider a $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\times 343^2)$ due to the calculation 
 of the difference arrays and next of the 686 features (of size 343).
 First of all, HUGO starts with computing the second order SPAM Features.
 This steps is in  $O(n^2 + 2\times 343^2)$ due to the calculation 
 of the difference arrays and next of the 686 features (of size 343).


@@ -26,6 +28,29 @@ The overall complexity of the pixel selection is finally
 $O(n^2 +2.343^2 + 2\times 343^2 \times n^2 + 2.n^2 \ln(n))$, \textit{i.e},
 $O(2.n^2(343^2 + \ln(n)))$.
 
 $O(n^2 +2.343^2 + 2\times 343^2 \times n^2 + 2.n^2 \ln(n))$, \textit{i.e},
 $O(2.n^2(343^2 + \ln(n)))$.
 

+
+
+
+Let us focus now on WOW.  
+This scheme starts to compute the residual 
+of the cover as a convolution product which is in $O(n^2\ln(n^2))$. 
+The embedding suitability $\eta_{ij}$ is then computed for each pixel
+$1 \le i,j \le n$ thanks to a convolution product again.
+We thus have a complexity of $O(n^2 \times n^2\ln(n^2))$.
+Moreover the suitability is computed for each wavelet level
+detail (HH, HL, LL). 
+This distortion computation step is thus in $O(6n^4\ln(n))$.
+Finally a norm of these three values is computed for each pixel 
+which adds to this complexity the complexity of $O(n^2)$.
+To summarize, the complixity is in $O(6n^4\ln(n) +n^2)$
+
+What follows details the complexity of the distortion evaluation of the 
+UNIWARD scheme. This one is based to a convolution product $W$ of two elements 
+of size $n$ and is again in   $O(n^2 \times n^2\ln(n^2))$ and a sum $D$ of 
+these $W$ which is in $O(n^2)$. 
+This distortion computation step is thus in $O(6n^4\ln(n) + n^2)$.
+
+

 Our edge selection is based on a Canny  Filter. When applied on a 
 $n \times n$ square image, the noise reduction step is in $O(5^3 n^2)$.
 Next, let $T$ be the size of the canny mask.
 Our edge selection is based on a Canny  Filter. When applied on a 
 $n \times n$ square image, the noise reduction step is in $O(5^3 n^2)$.
 Next, let $T$ be the size of the canny mask.