From a05ecbe2dbd49fe88dc0a12c322846037525d95c Mon Sep 17 00:00:00 2001 From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?= Date: Fri, 19 Sep 2014 10:14:00 +0200 Subject: [PATCH] =?utf8?q?ajout=20complexit=C3=A9=20WOW=20et=20UNIWARD?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- complexity.tex | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) diff --git a/complexity.tex b/complexity.tex index e4e6b0e..4499857 100644 --- a/complexity.tex +++ b/complexity.tex @@ -58,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 @@ -67,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. -- 2.39.5