ANN: ReduceWindows.jl

I am happy to announce ReduceWindows.jl. The package allows to apply reduce over a sliding window. From the Readme:

Usage

using ReduceWindows
x = [1,2,3,4,5]
reduce_window(+, x, (-1:1,))
# [3, 6, 9, 12, 9]
reduce_window(max, x, (-1:1,))
# [2, 3, 4, 5, 5]
reduce_window(min, x, (-3:0,))
# [1, 1, 1, 1, 2]

x = [1 2 3; 4 5 6]
reduce_window(*, x, (0:1,0:1))
# 40  180  18
# 20   30   6

Speed

This package has very competitive performance, especially for large windows.

arr = randn(500,500)
window = (-50:50, -50:50)
using ImageFiltering: mapwindow
mapwindow(maximum, arr, window) # warmup
out1 = @showtime mapwindow(maximum, arr, window)

using ReduceWindows
reduce_window(max, arr, window) # warmup
out2 = @showtime reduce_window(max, arr, window)
@assert out1 == out2
mapwindow(maximum, arr, window): 2.075822 seconds (1.26 M allocations: 227.561 MiB, 0.76% gc time)
reduce_window(max, arr, window): 0.002320 seconds (14 allocations: 7.630 MiB)

Naively reducing a windows of size k over an array of size n is O(k*n).
However the algorithm implemented here is O(log(k)*n) making it practical to reduce over large windows.

arr = randn(500,500)
window = (-50:50, -50:50)
using ImageFiltering: mapwindow
using ReduceWindows
const OPCOUNT = Ref(0)
function mymax(x,y)
    OPCOUNT[] += 1
    max(x,y)
end

mapwindow(w->reduce(mymax, w), arr, window)
opcount_naive = OPCOUNT[]
OPCOUNT[] = 0
reduce_window(mymax, arr, window)
opcount_reduce_window = OPCOUNT[]
@show opcount_naive
@show opcount_reduce_window
opcount_naive = 2550010200
opcount_reduce_window = 4775000

Alternatives

9 Likes

Pay attention that the documentation links doesn’t work in both MeanFilters.jl and ReduceWindows.jl.

I think you should mention what’s 0 index is or other way to describe the anchor of the window.
Also it would be nice to have non allocating ability to set the boundary (Replicate, Constant, etc…).

Thanks, but for me both of them work. Now I see what you mean. I removed them.

That would be nice. Do you have a good suggestion what you want to read about “anchor” and zero index?

1 Like

This is what I get:

Could it be that the address is available only to you as a user of GitHub and the owner of the domain?

From what I saw if the input and output arrays are the same size.
Also if I got it right, the anchor is the zero index. If I got it right, I think it should be mentioned.

On top of that, it would be great to be able to chose how to handle boundaries.
If I got it right, for now, you just ignore them. Which is OK.
But it would be great to have something like other modes. You may have a look on StaticKernels.jl.
You also should compare performance with it. As far as I could see ImageFiltering.jl is not fast in some cases, so StaticKernels.jl might be a better reference (For small windows).

1 Like

I misunderstood you. You were right. The readme is the only docs. I removed the links.

Yes you got that right.

Sure that would be a great PR.

Ah great. Yeah this package was designed with big windows in mind. For small windows no doubt StaticKernels.jl is better. Will add it to the README.

By the way, I can’t find the announcement of MeanFilters.jl.