X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/blobdiff_plain/4d8da06dfcc93848b57c76c1b6cff7ca52f0df4a..df4d1d843c37342838b487163589f57a1ed6e28e:/complexity.tex

diff --git a/complexity.tex b/complexity.tex
index e2f0203..4499857 100644
--- 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}.
+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).
@@ -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)))$.
 
+
+
+
+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.
@@ -33,8 +58,10 @@ Computing gradients is in $O(4Tn)$ since derivatives of each direction (vertical
 are in $O(2Tn)$.
 Finally, thresholding with hysteresis is in $O(n^2)$.
 The overall complexity is thus in $O((5^3+4T+1)n^2)$.
-To summarize, for the embedding map construction, the complexity of Hugo is
-dramatically larger than our scheme.
+
+
+
+
 
 We are then left to express the complexity of the STC algorithm.
 According to~\cite{DBLP:journals/tifs/FillerJF11}, it  is 
@@ -42,12 +69,17 @@ in $O(2^h.n)$ where $h$ is the size of the duplicated
 matrix. Its complexity is thus negligible compared with the embedding map
 construction.
 
+To summarize, for the embedding map construction, the complexity of Hugo, WOW 
+and UNIWARD are dramatically larger than the one of our scheme: 
+STABYLO is in $O(n^2)$ 
+whereas HUGO is in $O(n^2\ln(n)$, and WOW and UNIWARD are in $O(n^4\ln(n))$.
+Thanks to these complexity results, we claim that STABYLO is lightweight. 
+
 
 
 
 
 
-Thanks to these complexity results, we claim that STABYLO is lightweight.