| Abstract | Computing discrete two-dimensional convolutions is an important problem in image processing. In mathematicalmorphology, an important variant is that of computing binary convolutions, where the kernel of the convolution
is a 0{1 valued function. This operation can be quite costly, especially when large kernels are involved. In this
paper, we present an algorithm for computing convolutions of this form, where the kernel of the binary convolution
is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some exibility
in how it elects to digitize the convex kernel at each placement, as long as the digitization satis es certain reasonable
requirements. We say that such a convolution is valid. Given this exibility we show that it is possible to compute
binary convolutions more e ciently than would normally be possible for large kernels. Our main result is an
algorithm, which given an m n image and a k-sided convex polygonal kernel, computes a valid convolution in
time O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is
independent of the area or perimeter of K, and our techniques do not rely on computing fast Fourier transforms. Our
algorithm is based on a novel use of Bresenham's line-drawing algorithm and pre x-sums to update the convolution
e ciently as the kernel is moved from one position to another across the image.
|
