Mesh of Linear Arrays for Template Matching

ISSN： 1077-2014

Source： Real-Time Imaging, Vol.2, Iss.6, 1996-12, pp. : 373-382

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

This paper presents the architecture and the implementation of template matching on a 3-D piece-wise regular processor space that forms a two-dimensional array of linear systolic arrays. Template matching can be considered as a 2-D convolution of an image of size N x N with a kernel of size r x r. Conventional high-speed implementations use 2-D systolic arrays of size O ( r ) which compute in O ( N ) time. The drawback of this solution is that the size of the processor array follows on the size of the convolution kernel. This does not permit the allocation of more processors in order to meet the real-time requirements. With the approach used in this paper, the size of the processor array may be extended up to O ( sr ), 1 < s < N , thereby accomplishing the calculations in O ( N / s ) time. In the case when s = r , the r x r mesh of 1-D systolic arrays of size O ( r ) is yielded. The piecewise regularity of the 3-D processor array allows also easy physical realization.