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 some of
   4 current state of the art of
   5 steganographic scheme, namely HUGO~\cite{DBLP:conf/ih/PevnyFB10},
   6 WOW~\cite{conf/wifs/HolubF12}, and UNIWARD~\cite{HFD14}.
   7
   8
   9 In what follows, we consider a $n \times n$ square image.
  10 First of all, HUGO starts with computing the second order SPAM Features.
  11 This steps is in  $O(n^2 + 2\times 343^2)$ due to the calculation
  12 of the difference arrays and next of the 686 features (of size 343).
  13 Next for each pixel, the distortion measure is calculated by +1/-1 modifying
  14 its value and computing again the SPAM
  15 features. Pixels are thus selected according to their ability to provide
  16 an image whose SPAM features are close to the original ones.
  17 The algorithm thus computes a distance between each feature
  18 and the original ones,
  19 which is at least in $O(343)$, and an overall distance between these
  20 metrics, which is in $O(686)$. Computing the distance is thus in
  21 $O(2\times 343^2)$ and this modification
  22 is thus in $O(2\times 343^2 \times n^2)$.
  23 Ranking these results may be achieved with an insertion sort, which is in
  24 $2.n^2 \ln(n)$.
  25 The overall complexity of the pixel selection is finally
  26 $O(n^2 +2.343^2 + 2\times 343^2 \times n^2 + 2.n^2 \ln(n))$, \textit{i.e},
  27 $O(2.n^2(343^2 + \ln(n)))$.
  28
  29 Our edge selection is based on a Canny  Filter. When applied on a
  30 $n \times n$ square image, the noise reduction step is in $O(5^3 n^2)$.
  31 Next, let $T$ be the size of the canny mask.
  32 Computing gradients is in $O(4Tn)$ since derivatives of each direction (vertical or horizontal)
  33 are in $O(2Tn)$.
  34 Finally, thresholding with hysteresis is in $O(n^2)$.
  35 The overall complexity is thus in $O((5^3+4T+1)n^2)$.
  36 To summarize, for the embedding map construction, the complexity of Hugo is
  37 dramatically larger than our scheme.
  38
  39 We are then left to express the complexity of the STC algorithm.
  40 According to~\cite{DBLP:journals/tifs/FillerJF11}, it  is
  41 in $O(2^h.n)$ where $h$ is the size of the duplicated
  42 matrix. Its complexity is thus negligible compared with the embedding map
  43 construction.
  44
  45
  46
  47
  48
  49
  50 Thanks to these complexity results, we claim that STABYLO is lightweight.
  51
  52
  53
  54