TY - JOUR T1 - Approximating large convolutions in digital images JF - Image Processing, IEEE Transactions on Y1 - 2001 A1 - Mount, Dave A1 - Kanungo,T. A1 - Netanyahu,N. S A1 - Piatko,C. A1 - Silverman,R. A1 - Wu,A. Y KW - 2D KW - algorithm;binary KW - approximation;mathematical KW - convolution KW - convolution;binary KW - convolutions;Bresenham's KW - convolutions;convex KW - convolutions;geometric KW - images;discrete KW - kernel;convex KW - kernel;digital KW - line-drawing KW - morphology; KW - morphology;approximation KW - object;image KW - polygonal KW - processing;large KW - processing;mathematical KW - theory;convolution;image KW - two-dimensional AB - Computing discrete two-dimensional (2-D) convolutions is an important problem in image processing. In mathematical morphology, 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. 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 flexibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satisfies certain reasonable requirements. We say that such a convolution is valid. Given this flexibility we show that it is possible to compute binary convolutions more efficiently than would normally be possible for large kernels. Our main result is an algorithm which, given an m times;n image and a k-sided convex polygonal kernel K, computes a valid convolution in 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 (1965) line-drawing algorithm and prefix-sums to update the convolution incrementally as the kernel is moved from one position to another across the image VL - 10 SN - 1057-7149 CP - 12 M3 - 10.1109/83.974567 ER -