A Vlsi Architecture For Object Recognition Using Tree Matching


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


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


Publication Title

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



Number of Pages


Document Type

Article; Proceedings Paper

Personal Identifier


DOI Link


Socpus ID

35048814008 (Scopus)

Source API URL


This document is currently not available here.