ajout complexité WOW et UNIWARD

[canny.git] / complexity.tex

diff --git a/complexity.tex b/complexity.tex
index e4e6b0e91529cf167bd1f4664455054f17f5e70a..44998574f200312e1993b0f0f2402877a7475dbf 100644 (file)
--- 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)$.
 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 
 
 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.
 
 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.