From d67ddfb670a8d832dcf94f66044f3bb2ac8add39 Mon Sep 17 00:00:00 2001 From: couchot Date: Tue, 17 Dec 2013 13:29:39 +0100 Subject: [PATCH] kl --- complexity.tex | 46 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) create mode 100644 complexity.tex diff --git a/complexity.tex b/complexity.tex new file mode 100644 index 0000000..6932afa --- /dev/null +++ b/complexity.tex @@ -0,0 +1,46 @@ + +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}. + + +In what follows, we consider an $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 +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, +andthe 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 a 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} +$O(2.n^2(343^2 + \ln(n)))$. + +Our edge selection is based on a Canny Filter, +whose complexity is in $O(2n^2.\ln(n))$ thanks to the convolution step +which can be implemented with FFT. +To summarize, for the embedding map construction, the complexity of Hugo is +at least $343^2/\ln{n}$ times higher than +our scheme. For instance, for a squared image with 4M pixel per slide, +this part of our algorithm is more than 14100 faster than Hugo. + +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 +construction. + +Thanks to these complexity result, we claim that STABYLO is lightweight. + + + + + -- 2.39.5