X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/canny.git/blobdiff_plain/30a1c774eb33c1344a68625e8958dbbd8b996280..f96233fc65ad1523ba849069ed5b7daa8f5ef9b1:/complexity.tex?ds=inline

diff --git a/complexity.tex b/complexity.tex
index 6e108f8..4da4291 100644
--- a/complexity.tex
+++ b/complexity.tex
@@ -24,13 +24,15 @@ 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.
+Our edge selection is based on a Canny  Filter. When applied on a 
+$n \times n$ square image the Noise reduction steps is in $O(5^3 n^2)n$.
+Next, let $T$ be the size of the canny mask.
+Computing gradients is in $O(4Tn)$ since derivatives of each direction (vertical or horizontal) 
+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
-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.
+dramatically higher than our scheme.
 
 We are then left to express the complexity of the STC algorithm.
 According to~\cite{DBLP:journals/tifs/FillerJF11}, it  is