NDLI: VLSI Systolic Implementation of the Transportation Simplex Algorithm for Texture Distance Computation

Content Provider	IEEE Xplore Digital Library
Author	Giridbar, M. Tandri, S. Abd-El-Barr, M.H. Raafat, H.M.
Copyright Year	1988
Description	Author affiliation: University of Saskatchewan (Giridbar, M.)
Abstract	Systolic structures, first introduced by Kung and Leiserson in 1978, consist of a large number of simple processing elements, which are connected in a regular way such that higher performance is achieved through extensive concurrent and pipeline use of data items. These structures lend themselves to the involved computations needed in computer vision applications. In the context of texture analysis, a new and effective method for texture representation and classification has been developed by the last author. The method is based primarily on the idea of using a transportation problem-like structure to model the event matching distance, at a given resolution level, is between two histograms each representing the distribution of feature events within an image block of a specific size. The matching process is thus reduced to finding a solution to the streamlined transportation simplex problem. In this paper, a systolic solution to the transportation problem is proposed. A square mesh-connected cells, each having the initial supply and demand values for the row and the column to which it belongs, are used to model the case of n sources and n destinations. Two algorithms, which constitute a solution to the problem, are developed. First, the Russell's technique for selecting an initial basic feasible solution is introduced. Only local communication between a a cell and any of its neighbors is needed. Global commamications between a control unit and the cells are kept to a minimum. The second algorithm tests the optimality of the initial basic feasible solution from the Russell's method. An algorithm for computing the chain reaction caused by increasing the entering basic variable(s) and which iteratively computes the final solution to the problem is then developed. The algorithms are shown to take 0(n/sup 2/) time for execution.
Starting Page	1136
Ending Page	1140
File Size	1120254
Page Count	5
File Format	PDF
ISBN	7800030393
DOI	10.1109/ICSMC.1988.712896
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1988-08-08
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Very large scale integration Transportation Histograms Computer vision Iterative algorithms Image resolution Hardware Concurrent computing High performance computing Pipelines
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

VLSI pipelined trees and pyramids for image processing

A parallel VLSI algorithm for a high throughput systolic array VLSI implementation of type IV DCT

A parallel skeletonization algorithm and its VLSI architecture

A new systolic array algorithm for memory-based VLSI array implementation of DCT

A systolic algorithm for integer GCD computation

Efficient parallel algorithms and VLSI architectures for manipulator Jacobian computation

An integrated circuit for texture distance computation

An efficient systolic array algorithm for the VLSI implementation of a prime-length DHT

A bit-serial systolic algorithm and VLSI implementation for RSA

VLSI Systolic Implementation of the Transportation Simplex Algorithm for Texture Distance Computation

Similar Documents

VLSI pipelined trees and pyramids for image processing

A parallel VLSI algorithm for a high throughput systolic array VLSI implementation of type IV DCT

A parallel skeletonization algorithm and its VLSI architecture

A new systolic array algorithm for memory-based VLSI array implementation of DCT

A systolic algorithm for integer GCD computation

Efficient parallel algorithms and VLSI architectures for manipulator Jacobian computation

An integrated circuit for texture distance computation

An efficient systolic array algorithm for the VLSI implementation of a prime-length DHT

A bit-serial systolic algorithm and VLSI implementation for RSA

VLSI Systolic Implementation of the Transportation Simplex Algorithm for Texture Distance Computation