après raph

[canny.git] / complexity.tex

diff --git a/complexity.tex b/complexity.tex
index 6932afaf6883139148707cf3d1114866a2dfaa58..6e108f80c1c69feebc2c9dbb44e3b5211a43b6fa 100644 (file)
--- a/complexity.tex
+++ b/complexity.tex
@@ -4,7 +4,7 @@ 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}.
 
 
 state of the art steganography, namely HUGO~\cite{DBLP:conf/ih/PevnyFB10}.
 
 

-In what follows, we consider an $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.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.343^2)$ due to the calculation 
 of the difference arrays and next of the 686 features (of size 343).


@@ -13,12 +13,12 @@ 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, 
 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, 

-andthe original ones
+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 $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)$.

-Ranking these results may be achieved with a insertion sort which is in 
+Ranking these results may be achieved with an 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\times 343^2 \times n^2 + 2.n^2 \ln(n))$, \textit{i.e}
 $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}


@@ -32,12 +32,17 @@ 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.
 
 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.
 

-We are then left to express the complexity of the STC algorithm .
+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
 construction.
 
 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
 construction.
 

+
+
+
+
+

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