13th IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP'02)
A VLSI Architecture for Object Recognition Using Tree Matching
San Jose, California
July 17-July 19
ISBN: 0-7695-1712-9
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 PE?s 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 m, 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.
Citation:
K. Sitaraman, N. Ranganathan, A. Ejnioui, "A VLSI Architecture for Object Recognition Using Tree Matching," asap, pp.325, 13th IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP'02), 2002