From: Jean-François Couchot Date: Fri, 19 Sep 2014 08:14:00 +0000 (+0200) Subject: ajout complexité WOW et UNIWARD X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/commitdiff_plain/a05ecbe2dbd49fe88dc0a12c322846037525d95c?ds=sidebyside;hp=bf273ca48657e1dd9e23cb0e5afe4b41838e3f2a ajout complexité WOW et UNIWARD --- 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.