Parallel decomposition algorithm using decimation operation for 2D discrete convolution operation

Shinping Robert Wang; Pepe Siy

doi:10.1117/12.205483

23 March 1995 Parallel decomposition algorithm using decimation operation for two-dimensional discrete convolution operation

Shinping Robert Wang, Pepe Siy

Author Affiliations +

Proceedings Volume 2421, Image and Video Processing III; (1995) https://doi.org/10.1117/12.205483
Event: IS&T/SPIE's Symposium on Electronic Imaging: Science and Technology, 1995, San Jose, CA, United States

Abstract

The proposed decomposition algorithm follows the divide-and-conquer approach. Specifically, operands of discrete convolution operation are decomposed into smaller units, computed separately, and then combined for the final result. The decomposition of the operands is based on integer modular arithmetic from Number Theory. Operands are treated as ordered set, and integer modular arithmetic is used to partition these sets into congruent subsets. It is basically a Decimation by p operation, where p is the common factor of the operands' sizes. Since the proposed decomposition algorithm is an isomorphism, the decomposed convolution operation is equivalent to the original one. Processing speed is increased by implementing these decomposed convolution operations in parallel. The proposed algorithm is similar to the well- known Block convolution except that it is more suitable for parallel implementation. Because the decomposed operations are highly regular and independent, it is also suitable for VLSI implementation.

Citation Download Citation

Shinping Robert Wang and Pepe Siy "Parallel decomposition algorithm using decimation operation for two-dimensional discrete convolution operation", Proc. SPIE 2421, Image and Video Processing III, (23 March 1995); https://doi.org/10.1117/12.205483

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

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
12 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Convolution

Matrices

Algorithm development

Reconstruction algorithms

Very large scale integration

Radon

Signal processing

Show All Keywords

Keywords/Phrases

Search In:

Publication Years