A tree matching chip

Tree matching is an important problem used for 3D object recognition in image understanding and vision systems. It is also used in the design of on-line interpreter systems as well as code optimization in compilers. The objective of tree matching is to find the set of nodes at which a pattern tree m...

Full description

Saved in:
Bibliographic Details
Main Authors: Krishna, V., Ejnioui, A., Ranganathan, N.
Format: Conference Proceeding
Language:English
Subjects:
Computational modeling
Concurrent computing
Logic
Object recognition
Optimizing compilers
Parallel algorithms
Partitioning algorithms
Pattern matching
Systolic arrays
Terminology
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Tree matching is an important problem used for 3D object recognition in image understanding and vision systems. It is also used in the design of on-line interpreter systems as well as code optimization in compilers. The objective of tree matching is to find the set of nodes at which a pattern tree matches a subject tree. Recently, two linear systolic array algorithms have been proposed by the authors. In this paper, we propose an improved approach wherein the the systolic algorithm is based on a linear array of fixed size independent of the problem size and larger strings are partitioned and processed based on the array size. Also, the architecture is simplified by moving the logic for processing variables in each PE to a single PE attached at the end. The systolic algorithm and architecture have been verified through simulation using the Cadence design tools.
ISSN:1063-9667
2380-6923
DOI:10.1109/ICVD.1996.489611