Browse Prior Art Database

Two-Dimensional Convolution Processor

IP.com Disclosure Number: IPCOM000042581D
Original Publication Date: 1984-May-01
Included in the Prior Art Database: 2005-Feb-04
Document File: 3 page(s) / 53K

Publishing Venue

IBM

Related People

Engbersen, A: AUTHOR

Abstract

For a two-dimensional convolution, e.g., for processing of images by considering each pixel with its neighbor pixels, blocks of m x n elements (out of a large matrix of values) must each be multiplied by m x n weighting coefficients, and the products must be accumulated. Each block of values partially overlaps with other blocks, but the block of weighting coefficients remains the same for each convolution. It is proposed to optimize operations and to eliminate storage accesses by providing an arithmetic unit which has m parallel multiplier/ALU input registers for m weighting coefficients (plus one data input register) and n parallel ALU accumulators for intermediate results. This will allow the maintenance of the same weighting coefficient for several multiplications (partial products) at the arithmetic unit input.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Two-Dimensional Convolution Processor

For a two-dimensional convolution, e.g., for processing of images by considering each pixel with its neighbor pixels, blocks of m x n elements (out of a large matrix of values) must each be multiplied by m x n weighting coefficients, and the products must be accumulated. Each block of values partially overlaps with other blocks, but the block of weighting coefficients remains the same for each convolution. It is proposed to optimize operations and to eliminate storage accesses by providing an arithmetic unit which has m parallel multiplier/ALU input registers for m weighting coefficients (plus one data input register) and n parallel ALU accumulators for intermediate results. This will allow the maintenance of the same weighting coefficient for several multiplications (partial products) at the arithmetic unit input. In two-dimensional signal processing, filtering often consists of a convolution operation for every data point, involving the eight neighbors of this data point and the point itself. The spatial convolution algorithm produces a spatial one-to-one mapping of data points, where the output data for a specific point is obtained by evaluating the weighted sum of the original data in a neighborhood of the corresponding input point. In two- dimensional signal processing, these processes are known as "local filtering" or "neighborhood operations". Consider Figs. 1 and 2. In Fig. 1, a part of a two- dimensional data field is shown. The grid comprising elements U1...U9 is the 3 x 3 element neighborhood of point U5. In Fig. 2, a weight-coefficient matrix is shown, comprising coefficients H1...H9 for an arbitrary convolution. Computation of the convolution is as follows: Each of the nine elements Ux is multiplied by the corresponding weight-coefficient Hx, and all partial products are accumulated to obtain the convolution value for U5. Thus, nine multiplications and eight additions are required. More generally, for a kernel of m x n elements (as indicated in Fig. 1), m x n multiplications and (m x n - 1) additions would be required for each convolution. In the previous convolution i - 1 for the 3 x 3 case, data elements U-2...U6 had to be processed with coefficients H1...H9 to obtain the value for U2. In the subsequent convolution i + 1, data elements U4...U12 will be processed with the same coefficients to obtain the value for U8. Thus, it can be seen that...