X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/blobdiff_plain/f96233fc65ad1523ba849069ed5b7daa8f5ef9b1..03f2db2f776786ee6e9435d3c0f603b248cdd2ae:/complexity.tex

diff --git a/complexity.tex b/complexity.tex
index 4da4291..304ab32 100644
--- a/complexity.tex
+++ b/complexity.tex
@@ -1,43 +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 
-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.
-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
-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)$.
-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)$.
-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)))$.
 
 Our edge selection is based on a Canny  Filter. When applied on a 
-$n \times n$ square image the Noise reduction steps is in $O(5^3 n^2)n$.
+$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
-dramatically higher than our scheme.
+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 
-matrix. Its complexity is thus negligeable compared with the embedding map
+matrix. Its complexity is thus negligible compared with the embedding map
 construction.
 
 
@@ -45,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.