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.
Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors
Number of Pages
Article; Proceedings Paper
Source API URL
Sitaraman, K.; Ranganathan, N.; and Ejnioui, A., "A Vlsi Architecture For Object Recognition Using Tree Matching" (2002). Scopus Export 2000s. 2730.