1 \begin{theorem}\label{th:cplxt:hugo}
2 Le schéma HUGO a une complexité de l'ordre de
3 $\theta(2 \times n^2(343^2 + \ln(n)))$
7 First of all, HUGO starts with computing the second order SPAM Features.
8 This steps is in $\theta(n^2 + 2\times 343^2)$ due to the computation
9 of the difference arrays and next of the 686 features (of size 343).
10 Next for each pixel, the distortion measure is calculated by +1/-1 modifying
11 its value and computing again the SPAM
12 features. Pixels are thus selected according to their ability to provide
13 an image whose SPAM features are close to the original ones.
14 The algorithm thus computes a distance between each feature
15 and the original ones,
16 which is at least in $\theta(343)$, and an overall distance between these
17 metrics, which is in $\theta(686)$. Computing the distance is thus in
18 $\theta(2\times 343^2)$ and this modification
19 is thus in $\theta(2\times 343^2 \times n^2)$.
20 Ranking these results may be achieved with a quick sort, which is in
21 $\theta(2 \times n^2 \ln(n))$ for data of size $n^2$.
22 The overall complexity of the pixel selection is finally
23 $\theta(n^2 +2 \times 343^2 + 2\times 343^2 \times n^2 + 2 \times n^2 \ln(n))$, \textit{i.e},
24 $\theta(2 \times n^2(343^2 + \ln(n)))$.
29 Let us focus now on WOW.
30 This scheme starts to compute the residual
31 of the cover as a convolution product which is in $\theta(n^2\ln(n^2))$.
32 The embedding suitability $\eta_{ij}$ is then computed for each pixel
33 $1 \le i,j \le n$ thanks to a convolution product again.
34 We thus have a complexity of $\theta(n^2 \times n^2\ln(n^2))$.
35 Moreover the suitability is computed for each wavelet level
37 This distortion computation step is thus in $\theta(6n^4\ln(n))$.
38 Finally a norm of these three values is computed for each pixel
39 which adds to this complexity the complexity of $\theta(n^2)$.
40 To summarize, the complixity is in $\theta(6n^4\ln(n) +n^2)$
42 What follows details the complexity of the distortion evaluation of the
43 UNIWARD scheme. This one is based to a convolution product $W$ of two elements
44 of size $n$ and is again in $\theta(n^2 \times n^2\ln(n^2))$,
46 these $W$ which is in $\theta(n^2)$.
47 This distortion computation step is thus in $\theta(6n^4\ln(n) + n^2)$.
50 Our edge selection is based on a Canny filter. When applied on a
51 $n \times n$ square image, the noise reduction step is in $\theta(5^3 n^2)$.
52 Next, let $T$ be the size of the Canny mask.
53 Computing gradients is in $\theta(4Tn^2)$ since derivatives of each direction (vertical or horizontal)
54 are in $\theta(2Tn^2)$.
55 Finally, thresholding with hysteresis is in $\theta(n^2)$.
56 The overall complexity is thus in $\theta((5^3+4T+1)n^2)$.
