Title

A Vlsi Architecture For Object Recognition Using Tree Matching

Keywords

Algorithm design and analysis; Computational complexity; Computer architecture; Hardware; Object detection; Object recognition; Pattern matching; Prototypes; Tree data structures; Very large scale integration

Abstract

The problem of tree pattern matching for object recognition in images is computationally intensive in nature. In two-dimensional images, the objects can be represented through multiscale decomposition as tree structures. The pattern tree representing an object can be matched with a subject tree representing an image in order to detect the objects within the image. In this paper, we describe a new systolic algorithm and its realization as a VLSI chip for tree pattern matching. The hardware algorithm is based on a linear array of processing elements (PEs) where the pattern matching is done in a pipelined fashion relying on nearest-neighbor communication between the PEs and the subject and pattern trees of arbitrary length can be processed using a fixed size PE array. The algorithm has an improved execution time of O(⌈m/a⌉n) required to perform the matching where in, a and n are the sizes of the pattern tree, processor array, subject tree respectively. A prototype CMOS VLSI chip implementing the proposed algorithm has been designed and verified It is shown that the hardware algorithm proposed in this work represent a significant improvement in terms of computational complexity, data flow, and architecture over the ones previously proposed for this problem.

Publication Date

1-1-2002

Publication Title

Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors

Volume

2002-January

Number of Pages

325-334

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ASAP.2002.1030731

Socpus ID

35048814008 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/35048814008

This document is currently not available here.

Share

COinS