]> AND Private Git Repository - canny.git/blob - complexity.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
kl
[canny.git] / complexity.tex
1
2 This section aims at justifying the lightweight attribute of our approach.
3 To be more precise, we compare the complexity of our schemes to the 
4 state of the art steganography, namely HUGO~\cite{DBLP:conf/ih/PevnyFB10}.
5
6
7 In what follows, we consider an $n \times n$ square image. 
8 First of all, HUGO starts with computing the second order SPAM Features.
9 This steps is in  $O(n^2 + 2.343^2)$ due to the calculation 
10 of the difference arrays and next of the 686 features (of size 343).
11 Next for each pixel, the distortion measure is calculated by +1/-1 modifying
12 its value and computing again the SPAM 
13 features. Pixels are thus selected according to their ability to provide
14 an image whose SPAM features are close to the original one. 
15 The algorithm is thus computing a distance between each computed feature, 
16 andthe original ones
17 which is at least in $O(343)$ and an overall distance between these 
18 metrics which is in $O(686)$. Computing the distance is thus in 
19 $O(2\times 343^2)$ and this modification
20 is thus in $O(2\times 343^2 \times n^2)$.
21 Ranking these results may be achieved with a insertion sort which is in 
22 $2.n^2 \ln(n)$.
23 The overall complexity of the pixel selection is thus 
24 $O(n^2 +2.343^2 + 2\times 343^2 \times n^2 + 2.n^2 \ln(n))$, \textit{i.e}
25 $O(2.n^2(343^2 + \ln(n)))$.
26
27 Our edge selection is based on a Canny  Filter, 
28 whose complexity is in $O(2n^2.\ln(n))$ thanks to the convolution step
29 which can be implemented with FFT.
30 To summarize, for the embedding map construction, the complexity of Hugo is
31 at least $343^2/\ln{n}$ times higher than 
32 our scheme. For instance, for a squared image with 4M pixel per slide,
33 this part of our algorithm is more than 14100 faster than Hugo.
34
35 We are then left to express the complexity of the STC algorithm .
36 According to~\cite{DBLP:journals/tifs/FillerJF11}, it  is 
37 in $O(2^h.n)$ where $h$ is the size of the duplicated 
38 matrix. Its complexity is thus negligeable compared with the embedding map
39 construction.
40
41 Thanks to these complexity result, we claim that STABYLO is lightweight. 
42
43
44
45
46