Constant Time Algorithm for Template Matching on a Reconfigurable Array of Processors
Open Access
- 1 January 1993
- journal article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 36 (3) , 246-253
- https://doi.org/10.1093/comjnl/36.3.246
Abstract
A reconfigurable array of processors (RAP) is defined to be an array of processors connected to a reconfigurable bus system whose configurations can be dynamically changed. For an n×n image and m×mtemplate, a constant time algorithm for template matching is proposed on a RAP with m×m×n×n×n processors when the domain of the image and the template is Boolean. Even if the domain is integer and each integer is bounded and represented by a q-bits binary sequence, a constant or O(log* m) time algorithm is still obtained. The number of processors needed is increased to 2qm2×2qm2×max {m,n}×n×n and m2×m2×max {m2,n}×n×n, respectively. An O(log m) times algorithm also derived for the domain is integer or real but the number of processors is reduced to m×m×n×n×n.Keywords
This publication has 0 references indexed in Scilit: