search

brandonmpetty / Doxa

A Local Adaptive Thresholding framework for image binarization written in C++, with JS and Python bindings. Implementing: Otsu, Bernsen, Niblack, Sauvola, Wolf, Gatos, NICK, Su, T.R. Singh, WAN, ISauvola, Bataineh, Chan and Shafait.
https://brandonmpetty.github.io/Doxa/WebAssembly
Creative Commons Zero v1.0 Universal
164 stars 37 forks source link

Wan algorithm is slowly if window size more than 17? #30

Open Charltsing opened 1 year ago

Charltsing commented 1 year ago

I test Doxa::Wan::UpdateToBinary(doxaGsImage, parameters); release Wan algorithm is slowly if window size more than 17?

time , size k=0.1 0.136 , 6 0.133 , 7 0.178 , 8 0.171 , 9 0.227 , 10 0.231 , 11 0.286 , 12 0.287 , 13 0.343 , 14 0.339 , 15 0.402 , 16 0.601 , 17 0.601 , 18 0.620 , 19 0.620 , 20 0.621 , 21 0.617 , 22 0.635 , 23 0.638 , 24 0.633 , 25 0.641 , 26 0.641 , 27 0.637 , 28 0.653 , 29 0.653 , 30 0.657 , 31 0.647 , 32 0.661 , 33 0.672 , 34 0.680 , 35 0.666 , 36

brandonmpetty commented 1 year ago

@Charltsing, please look at: https://github.com/brandonmpetty/Doxa/blob/master/Doxa/Morphology.hpp

You will see that the WAN algorithm requires that we Dilate the image. For small window sizes, it is faster to iterate over the entire image to build this Dilated image. For larger window sizes the cost in time explodes higher and higher with every size increment. To solve this I developed an un-published algorithm that keeps this time relatively constant for medium to large window sizes. However, it does have some overhead. The magic window size I found was around 17, so if you are less than 17, we iterate. If you are 17 or over, we use my morpho algorithm. It may seem slow, but trust me... without it, it would be useable. I am not aware of any other algorithm capable of solving this problem, other than what I have implemented here. Again, this algorithm is un-published and to my knowledge represents a novel approach that currently achieves state-of-the-art performance. If you are aware of a way to make this process faster, please let me know.

Could you also tell me more about your hardware, compiler flags, and sample image. You might be testing a debug build without optimization. Below are my numbers using the image that comes with this repo.

My test was ran on a: AMD Phenom II 1090T Processor running Windows 10, compiled with MSBuild using /O2 /Ot

Window Size / Morpho Alg Time / Iterative Alg Time 3 | 0.091808 | 0.028856 Using the Morph implementation is slower for small windows 17 | 0.127909 | 0.134349 This is the window size which breaks in favor of Morph 25 | 0.130928 | 0.238442 1.8x faster 75 | 0.143578 | 1.652775 11.5x faster 125 | 0.146470 | 4.218453 28.8x faster 255 | 0.149844 | 15.32876 102.3x faster