Computing rank-convolutions with a mask

Rank-convolutions have important applications in a variety of areas such as signal processing and computer vision. We define a mask as a function taking only values zero and infinity. Rank-convolutions with masks are of special interest to image processing. We show how to compute the rank-k convolution of a function over an interval of length n with an arbitrary mask of length m in O(n&sqrt;m log m) time. The result generalizes to the d-dimensional case. Previously no algorithm performing significantly better than the brute-force O(nm) bound was known. Our algorithm seems to perform well in practice. We describe an implementation, illustrating its application to a problem in image processing. Already on relatively small images, our experiments show a signficant speedup compared to brute force.