How to accelerate Non-linear filters like median-filter in Halide？

[mhua97]

In the field of image processing, Halide appears to be more suitable for linear filtering operations, such as Gaussian filtering. However, for non-linear filters that involve operations like swapping and sorting, how to accelerate them in Halide？

[abadams]

There's nothing about Halide that's specific to linear operations. I wrote this paper on fast median filtering entirely using Halide (even the interpreter): https://dl.acm.org/doi/10.1145/3450626.3459773

The way to swap two values in-place are the scatter/gather intrinsics. You can implement small support median filters using just min and max, but if you want to allocate a buffer and then do a bunch of swaps in it, you end up writing code like this (for a bubble-sort sorting network, probably with a bunch of off-by-one errors, because I didn't test it, but this is the rough shape of code like this):

f(x, y, i) = ... // Some data we want to sort along i
RDom r(size - 1, size - 1);
r.where(r.x < size - r.y);
f(x, y, scatter(r.x, r.x + 1)) = gather(min(f(x, y, r.x), f(x, y, r.x+1)), max(f(x, y, r.x), f(x, y, r.x+1)));