Complexity reduction on two-dimensional convolutions for image processing

Luca Chiarabini; Jonathan Yen

doi:10.1117/12.298286

2 January 1998 Complexity reduction on two-dimensional convolutions for image processing

Luca Chiarabini, Jonathan Yen

Proceedings Volume 3300, Color Imaging: Device-Independent Color, Color Hardcopy, and Graphic Arts III; (1998) https://doi.org/10.1117/12.298286
Event: Photonics West '98 Electronic Imaging, 1998, San Jose, CA, United States

Abstract

Presented here is a method for reducing the computational complexity of two-dimensional linear convolutions used in image processing like binary image scaling. This method is a hybrid of convolving at run-time and convolving by table lookup. The convolution step in image processing usually calculates a weighted average of an area of the input image by calculating the entry-by-entry multiplication of the input pixels with a weight table. This method partitions the calculations in the convolution step and stores pre-calculated partial results in lookup tables. When the convolution step takes place, a binary indexing is used to retrieve the partial results and the final result is obtained by summing up the partial results. A line cache and a double buffering scheme are designed to reduce memory access in table lookup. Space and time complexities are analyzed and compared to the conventional two-dimensional linear convolutions. We demonstrate that an order of magnitude reduction in the computational cost can be achieved. Examples, test images and performance data are provided.

Citation Download Citation

Luca Chiarabini and Jonathan Yen "Complexity reduction on two-dimensional convolutions for image processing", Proc. SPIE 3300, Color Imaging: Device-Independent Color, Color Hardcopy, and Graphic Arts III, (2 January 1998); https://doi.org/10.1117/12.298286

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

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.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available