Partitioning and mapping B-spline surface fitting algorithm into fixed-size VLSI arrays

Po-Rong Chang; Share-Young Lee

doi:10.1117/12.19735

1 August 1990 Partitioning and mapping B-spline surface fitting algorithm into fixed-size VLSI arrays

Po-Rong Chang, Share-Young Lee

Proceedings Volume 1251, Curves and Surfaces in Computer Vision and Graphics; (1990) https://doi.org/10.1117/12.19735
Event: Electronic Imaging: Advanced Devices and Systems, 1990, Santa Clara, CA, United States

Abstract

A method of solving the uniform bicubic B-spline surface fitting algorithm is proposed which introduces parallelism in a way that may be effectively exploited by a suitable parallel architecture. This method is based on the observation that a tensor product spline surface fitting problem can be split into two spline curve fitting problems and each of these problems can be realized by a macropipeline of fixed size VLSI arrays. In fact, the heart of curve fitting problem consists of a block tridiagonal linear system. Based on the state-of-art electronic and packaging technologies, the size of VLSI arithmetic devices is limited due to the bounded chip area and I/O packaging constraints. A modular approach to achieve VLSI matrix arithmetic solution for the block tridiagonal linear system is amenable from the viewpoints of feasibility and applicability. A matrix partitioning approach is presented to overcome those technological constraints imposed by the number of I/O pins. A block tridiagonal linear system of size mn is then divided into m simple tridiagonal systems of size n and n simple tridiagonal systems of size m by the Dc Boor partitioning theorem. Each of the simple tridiagonal linear systems could be partitioned and mappied into a series of two fixed size primitive VLSI matrix arithmetic arrays including L-U decomposer and triangular system solver. The L-U decomposer and triangular system solver could be realized by a hex-connected processor array and an inverse perfect shuffle machine respectively. It would be shown that a B-spline surface fitting problem for a grid of mn points can be solved by m hex-connected processor arrays having 4 processors, m inverse perfect shuffle machines having n processors and n inverse perfect shuffle machines having m processors in (3(m+n)+2({logzn1 +flog2n)+4J units of time.

Citation Download Citation

Po-Rong Chang and Share-Young Lee "Partitioning and mapping B-spline surface fitting algorithm into fixed-size VLSI arrays", Proc. SPIE 1251, Curves and Surfaces in Computer Vision and Graphics, (1 August 1990); https://doi.org/10.1117/12.19735

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
5 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Very large scale integration

Array processing

Visualization

Computer graphics

Computer vision technology

Machine vision

Packaging

Show All Keywords

Keywords/Phrases

Search In:

Publication Years