Mesh of Linear Arrays for Template Matching

✍ Scribed by Toomas P. Plaks

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 124 KB
• Volume: 2
• Category: Article
• ISSN: 1077-2014
• DOI: 10.1006/rtim.1996.0038

✦ Synopsis

Mesh of Linear Arrays for Template Matching

his paper presents the architecture and the implementation of template matching on a 3-D piecewise regular processor space that forms a two-dimensional array of linear systolic arrays.

TTempl ate matching can be considered as a 2-D convolution of an image of size N ϫ N with a kernel of size r ϫ r. Conventional high-speed implementations use 2-D systolic arrays of size O(r 2 ) which compute in O(N 2 ) 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 2 ), 1 ≤ s ≤ N, thereby accomplishing the calculations in O(N 2 /s) time.

In the case when s = r, the r ϫ 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.