X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/blobdiff_plain/56c2b1be255aa25e9a09a24734f332daf0176789..ef06623aa40e69d9e5332208f9ead5af2e7ea4b6:/complexity.tex

diff --git a/complexity.tex b/complexity.tex
index 4499857..d19f6e2 100644
--- a/complexity.tex
+++ b/complexity.tex
@@ -6,11 +6,12 @@ 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.
+Since this last step is shared by all, 
+we separately eavluate this complexity.
 In all the rest of this section, 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 
+This steps is in  $\theta(n^2 + 2\times 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 
@@ -18,46 +19,46 @@ features. Pixels are thus selected according to their ability to provide
 an image whose SPAM features are close to the original ones. 
 The algorithm thus computes a distance between each feature 
 and the original ones,
-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\times 343^2)$ and this modification
-is thus in $O(2\times 343^2 \times n^2)$.
+which is at least in $\theta(343)$, and an overall distance between these 
+metrics, which is in $\theta(686)$. Computing the distance is thus in 
+$\theta(2\times 343^2)$ and this modification
+is thus in $\theta(2\times 343^2 \times n^2)$.
 Ranking these results may be achieved with an insertion sort, which is in 
-$2.n^2 \ln(n)$.
+$2 \times n^2 \ln(n)$.
 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)))$.
+$\theta(n^2 +2 \times 343^2 + 2\times 343^2 \times n^2 + 2 \times n^2 \ln(n))$, \textit{i.e},
+$\theta(2 \times 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))$. 
+of the cover as a convolution product which is in $\theta(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))$.
+We thus have a complexity of $\theta(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))$.
+This distortion computation step is thus in $\theta(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)$
+which adds to this complexity the complexity of $\theta(n^2)$.
+To summarize, the complixity is in $\theta(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)$.
+of size $n$ and is again in   $\theta(n^2 \times n^2\ln(n^2))$ and a sum $D$ of 
+these $W$ which is in $\theta(n^2)$. 
+This distortion computation step is thus in $\theta(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)$.
+$n \times n$ square image, the noise reduction step is in $\theta(5^3 n^2)$.
 Next, let $T$ be the size of the canny mask.
-Computing gradients is in $O(4Tn)$ since derivatives of each direction (vertical or horizontal) 
-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)$.
+Computing gradients is in $\theta(4Tn)$ since derivatives of each direction (vertical or horizontal) 
+are in $\theta(2Tn)$.
+Finally, thresholding with hysteresis is in $\theta(n^2)$.
+The overall complexity is thus in $\theta((5^3+4T+1)n^2)$.
 
 
 
@@ -65,18 +66,25 @@ The overall complexity is thus in $O((5^3+4T+1)n^2)$.
 
 We are then left to express the complexity of the STC algorithm.
 According to~\cite{DBLP:journals/tifs/FillerJF11}, it  is 
-in $O(2^h.n)$ where $h$ is the size of the duplicated 
+in $\theta(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))$.
+The Fig.~\ref{fig:compared}
+summarizes the complexity of the embedding map construction, for Hugo, Wow 
+and Uniward. It deals with square images
+of size $n \times n$ when $n$ ranges from 
+512 to 4096. The $y$-coordinate is expressed in a logarithm scale.
+It shows that the complexity of all algorithms
+is dramatically larger than the one of the STABYLO scheme. 
 Thanks to these complexity results, we claim that STABYLO is lightweight. 
-
-
-
+\begin{figure}
+\begin{center}
+\includegraphics[scale=0.4]{complexity}
+\end{center}
+\caption{Complexity evaluation of Wow/Uniward, Hugo, and Stabylo}
+\label{fig:compared} 
+\end{figure}