Share Email Print
cover

Proceedings Paper

Complexity reduction on two-dimensional convolutions for image processing
Author(s): Luca Chiarabini; Jonathan Yen
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 2 January 1998
PDF: 8 pages
Proc. SPIE 3300, Color Imaging: Device-Independent Color, Color Hardcopy, and Graphic Arts III, (2 January 1998); doi: 10.1117/12.298286
Show Author Affiliations
Luca Chiarabini, Hewlett-Packard Co. (Spain)
Jonathan Yen, Hewlett-Packard Co. (United States)


Published in SPIE Proceedings Vol. 3300:
Color Imaging: Device-Independent Color, Color Hardcopy, and Graphic Arts III
Giordano B. Beretta; Reiner Eschbach, Editor(s)

© SPIE. Terms of Use
Back to Top