reprise STC

[canny.git] / complexity.tex

diff --git a/complexity.tex b/complexity.tex
index 6e108f80c1c69feebc2c9dbb44e3b5211a43b6fa..304ab329262c10ab37a994f979ddcc8548ab1d6e 100644 (file)
--- a/complexity.tex
+++ b/complexity.tex
@@ -1,41 +1,43 @@
 
 This section aims at justifying the lightweight attribute of our approach.
 To be more precise, we compare the complexity of our schemes to the 
 
 This section aims at justifying the lightweight 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}.
+ best available steganographic scheme, namely HUGO~\cite{DBLP:conf/ih/PevnyFB10}.

 
 
 In what follows, we consider a $n \times n$ square image. 
 First of all, HUGO starts with computing the second order SPAM Features.
 
 
 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.343^2)$ due to the calculation 
+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).
 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
 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 computed 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 
+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)$.
 $O(2\times 343^2)$ and this modification
 is thus in $O(2\times 343^2 \times n^2)$.

-Ranking these results may be achieved with an insertion sort which is in 
+Ranking these results may be achieved with an insertion sort, which is in 

 $2.n^2 \ln(n)$.
 $2.n^2 \ln(n)$.

-The overall complexity of the pixel selection is thus 
-$O(n^2 +2.343^2 + 2\times 343^2 \times n^2 + 2.n^2 \ln(n))$, \textit{i.e}
+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(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.
+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.
+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)$.

 To summarize, for the embedding map construction, the complexity of Hugo is
 To summarize, for the embedding map construction, the complexity of Hugo is

-at least $343^2/\ln{n}$ times higher than 
-our scheme. For instance, for a squared image with 4M pixel per slide,
-this part of our algorithm is more than 14100 faster than Hugo.
+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 
 in $O(2^h.n)$ where $h$ is the size of the duplicated 
 
 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 

-matrix. Its complexity is thus negligeable compared with the embedding map
+matrix. Its complexity is thus negligible compared with the embedding map

 construction.
 
 
 construction.
 
 


@@ -43,8 +45,7 @@ construction.
 
 
 
 
 
 

-Thanks to these complexity result, we claim that STABYLO is lightweight. 
-
+Thanks to these complexity results, we claim that STABYLO is lightweight.