Closed timholy closed 4 years ago
Thanks for getting started on this, Tim! I'm surprised that factored_GrayN0f8
takes 50% longer than factored_N0f8
. To focus on the algorithms, might it be better to benchmark preallocated imfilter!
& mapwindow!
? Some additional benchmarks that might be worthwhile:
Kernel.gaussian(3)
gives a 13 x 13 kernel)N0f8
can fit in L1 cache, 2048 x 2048 Float64
can't fit in cache at all)might it be better to benchmark preallocated imfilter! & mapwindow!
I don't think it will matter, the allocation of the output should be trivial. And for the algorithms that use TiledIteration it's going to have to allocate tile buffers anyway.
The rest seems sensible. It's much slower now, but you're right that's all stuff we need to test. Once it finishes I'll commit the tuning file, too, just so it doesn't take forever to run.
Merging #158 into master will not change coverage. The diff coverage is
n/a
.
@@ Coverage Diff @@
## master #158 +/- ##
=======================================
Coverage 91.65% 91.65%
=======================================
Files 9 9
Lines 1222 1222
=======================================
Hits 1120 1120
Misses 102 102
Continue to review full report at Codecov.
Legend - Click here to learn more
Δ = absolute <relative> (impact)
,ø = not affected
,? = missing data
Powered by Codecov. Last update 75f89d0...916a8eb. Read the comment docs.
I ran a mini-shootout against OpenCV as a basis of comparison. Looks like we're within striking distance for kernel operations, but mapwindow(median!, img, (3,3))
is much slower than OpenCV's specialized medianBlur
.
using Conda, PyCall, BenchmarkTools, Images, Statistics
cv2 = pyimport_conda("cv2", "opencv")
np = pyimport("numpy")
timeit = pyimport("timeit")
function pybench(expr, setup, N_init=10)
N = round(Int, N_init/timeit.timeit(expr, setup=setup, number=N_init))
t = timeit.timeit(expr, setup=setup, number=N)
t/N
end
src = rand(Gray{N0f8}, 512, 512)
# median filter
cv2median = pybench("cv2.medianBlur(src, 3)", "import cv2; import numpy as np; src = np.uint8(np.random.rand(512,512))")
jlmedian = @belapsed mapwindow(median!, $src, (3,3))
# gaussian blur
cv2blur = pybench("cv2.GaussianBlur(src, (13,13), 3)", "import cv2; import numpy as np; src = np.uint8(np.random.rand(512,512))")
jlblur = @belapsed imfilter($src, KernelFactors.gaussian((3,3)))
# Sobel derivative
cv2deriv = pybench("cv2.spatialGradient(src)", "import cv2; import numpy as np; src = np.uint8(np.random.rand(512,512))")
jlderiv = @belapsed imgradients($src, KernelFactors.sobel)
jlmedian/cv2median # 112x slower
jlblur/cv2blur # 6x slower
jlderiv/cv2deriv # 14x slower
median
is expected, and would be even worse for larger filters. (I'm actually a bit surprised it's this bad for 3x3.) The lack of an efficient large-scale median filter is one of the most glaring missing elements in the ecosystem. It's fairly easy to write a fast median filter for large kernels if you have N0f8
data in any dimensionality. It gets harder for any other kind of data, because binning is no longer an obvious win. The strategy of maintaining a histogram of slices and only updating a single slice does repeated work proportional to (d-1)/d
where d
is dimensionality; repeating half your work in 2d seems OK but starts to get unsatisfying even in 3d. See #34 for an abandoned attempt. I think @tejus-gupta has some ideas in this domain.
The rest are also disappointing but I'd gotten a hint this was an issue. I suspect there's quite a lot we can do to address all these, fortunately.
I was wondering if GSOC applicants might want to do this, but there seems to be some interest in speeding this package up so we need these now. This should be good enough to get us going, anyway. CC @stillyslalom, @chriselrod.