X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/blobdiff_plain/03f2db2f776786ee6e9435d3c0f603b248cdd2ae..a05ecbe2dbd49fe88dc0a12c322846037525d95c:/complexity.tex?ds=inline diff --git a/complexity.tex b/complexity.tex index 304ab32..4499857 100644 --- a/complexity.tex +++ b/complexity.tex @@ -1,10 +1,14 @@ This section aims at justifying the lightweight attribute of our approach. -To be more precise, we compare the complexity of our schemes to the - best available steganographic scheme, namely HUGO~\cite{DBLP:conf/ih/PevnyFB10}. +To be more precise, we compare the complexity of our schemes to some of +current state of the art of +steganographic scheme, namely HUGO~\cite{DBLP:conf/ih/PevnyFB10}, +WOW~\cite{conf/wifs/HolubF12}, and UNIWARD~\cite{HFD14}. +Each of these scheme starts with the computation of the distortion cost +for each pixel switch and is later followed by the STC algorithm. +Since this last step is shared by all, we do not add its complexity. +In all the rest of this section, we consider a $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\times 343^2)$ due to the calculation of the difference arrays and next of the 686 features (of size 343). @@ -24,6 +28,29 @@ 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)))$. + + + +Let us focus now on WOW. +This scheme starts to compute the residual +of the cover as a convolution product which is in $O(n^2\ln(n^2))$. +The embedding suitability $\eta_{ij}$ is then computed for each pixel +$1 \le i,j \le n$ thanks to a convolution product again. +We thus have a complexity of $O(n^2 \times n^2\ln(n^2))$. +Moreover the suitability is computed for each wavelet level +detail (HH, HL, LL). +This distortion computation step is thus in $O(6n^4\ln(n))$. +Finally a norm of these three values is computed for each pixel +which adds to this complexity the complexity of $O(n^2)$. +To summarize, the complixity is in $O(6n^4\ln(n) +n^2)$ + +What follows details the complexity of the distortion evaluation of the +UNIWARD scheme. This one is based to a convolution product $W$ of two elements +of size $n$ and is again in $O(n^2 \times n^2\ln(n^2))$ and a sum $D$ of +these $W$ which is in $O(n^2)$. +This distortion computation step is thus in $O(6n^4\ln(n) + n^2)$. + + Our edge selection is based on a Canny Filter. When applied on a $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. @@ -31,8 +58,10 @@ Computing gradients is in $O(4Tn)$ since derivatives of each direction (vertical 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 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 @@ -40,12 +69,17 @@ in $O(2^h.n)$ where $h$ is the size of the duplicated matrix. Its complexity is thus negligible compared with the embedding map construction. +To summarize, for the embedding map construction, the complexity of Hugo, WOW +and UNIWARD are dramatically larger than the one of our scheme: +STABYLO is in $O(n^2)$ +whereas HUGO is in $O(n^2\ln(n)$, and WOW and UNIWARD are in $O(n^4\ln(n))$. +Thanks to these complexity results, we claim that STABYLO is lightweight. + -Thanks to these complexity results, we claim that STABYLO is lightweight.