Computing discrete 2D convolutions is an important problem in image processing. In mathematical morphology, an important variant is that of computing binary convolutions, where 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 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 computer binary convolutions more efficiently than would normally be possible for large kernels, 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 technique do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's line-drawing algorithm and prefix-sums to update the convolution efficiently as the kernel is moved from one position to another across the image.
Given two simple polygons P and Q in the plane and a translation vector t (epsilon) R2, the area-of-overlap function of P and Q is the function A(t) equals Area[P (t + Q)], where t + Q denotes Q translated by t. This function has a number of applications and interpretations. We present a number of mathematical and computational results regarding this function.
Given a convex polygon P, an m-envelope is a convex m-sided polygon that contains P. Given any convex polygon P, and any sequence of m >= 3 angles A equals ((alpha) 1, (alpha) 2, ..., (alpha) m) we consider the problem of computing the minimum area m- envelope for P whose counterclockwise sequence of exterior angles is given by A. We show that such envelopes can be computed in O(nm log m) time. The main result on which the correctness of the algorithm rests is a flushness condition stating that for any locally minimum enclosure with specified angles, one of its sides must be collinear with one of the sides of P.
Proceedings Volume Editor (8)
This will count as one of your downloads.
You will have access to both the presentation and article (if available).
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.