Open johnnychen94 opened 3 years ago
Merging #193 into master will decrease coverage by
0.13%
. The diff coverage is0.00%
.
@@ Coverage Diff @@
## master #193 +/- ##
==========================================
- Coverage 91.62% 91.49% -0.14%
==========================================
Files 9 9
Lines 1385 1387 +2
==========================================
Hits 1269 1269
- Misses 116 118 +2
Impacted Files | Coverage Δ | |
---|---|---|
src/mapwindow.jl | 85.90% <0.00%> (-0.77%) |
:arrow_down: |
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 0c963dc...f0d5db9. Read the comment docs.
The speed improvement or worsening depends on the window size; I worry a 3x3 window might not show a speedup. The Lemire algorithm has a different order than naive minimum
/maximum
. The naive versions are O(M^d*N)
(in d
dimensions, where M
is the window size and N
the number of pixels) whereas my hazy memory suggests Lemire is O(MlogM*N)
. For small windows the constant factor could be important.
The other issue is that if you want both the max & min, it's clearly better to call mapwindow(extrema, ...)
once and then extract both results.
For these reasons I'd avoided implementing these shortcuts, in essence hoping to convince people to use extrema
directly. But that may not be documented, and may not even be a good idea. So this PR may be a really good idea, but I thought you should know why we don't have this already.
It is still more efficient in 3*3 case, probably contributed by less memory allocation.
julia> @btime mapwindow(maximum, $img2d, (3,3));
40.210 μs (54 allocations: 52.56 KiB)
julia> @btime mapwindow(f, $img2d, (3, 3));
109.429 μs (2350 allocations: 141.25 KiB)
I'll need to read the paper first to see if there's a better way. I mean, to only compute the maximum in a similar way. Unsure of it now.
Looks like the performance issue with maximum
isn't memory allocation (though I haven't taken the time to figure out where that comes from, it's a bit surprising), it's that it is using a more careful max
. The results for img2d = rand(10,10); img2d[5,5] = NaN
seem to differ for a 3x3 window. :frowning:
Playing with https://github.com/sairus7/MaxMinFilters.jl and it turns out to be more performant than ImageFiltering's implementation. I guess this indicates that there's still room for optimization.
julia> img2d = randn(30,30);
julia> @btime mapwindow(extrema, $img2d, (3,1));
21.749 μs (47 allocations: 44.91 KiB)
julia> @btime movmaxmin($img2d, 3);
5.271 μs (4 allocations: 14.63 KiB)
MaxMinFilters does not apply to the multidimensional case, though; it simply treats it as a vector. I'll see what I can do to get things better here. A re-reimplementation, probably, in an independent package and get used by ImageFiltering.jl.
Just took the first read on the paper and it occurs that a maximum/minimum filter is possible if we only apply the wedge update on one side. So yeah, it's doable to for mapwindow
to also support maximum/minimum.
Tweaking the implementation doesn't look like an easy job, so I'll revisit this when I finish my WNNM project. Probably months later, though...
A re-reimplementation, probably, in an independent package and get used by ImageFiltering.jl.
I'm unsure it should be a separate package...if anything, I'm inclined to go the other way (https://github.com/JuliaImages/Images.jl/issues/898). Well, I guess it could be a separate package, it's the separate repo that I find annoying.
The main reason they differ in performance is because this implementation supports multiple dimensions. More than half the time is due to this one comprehension: https://github.com/JuliaImages/ImageFiltering.jl/blob/0c963dc6bc4c465c95ef6a6bb3a49d030d3bbfce/src/mapwindow.jl#L375
But that's the foundation for multidimensional support, as it allows the filter to be separable. Almost all the rest is due internal methods of DataStructures.CircularDeqeue
. I wonder if we'd get better performance out of an immutable variant?
Anyway, I don't think we should be so quick to abandon the current implementation. There might be a quick way to make the 1d case not need the comprehension, for example.
I haven't read the Lemire paper yet so I don't know if there is a more efficient implementation for maximum/minimum, but now simply applying
first
/last
on theextrema
result still gives about ~4x boost.Hmmm, I plan to read that for my own interest in https://github.com/JuliaImages/Images.jl/issues/918.
cc @Dsantra92