Systems, Man, and Cybernetics

 

Home

• [P642] Using Exact Bounds for Fixed Time Template Matching
  Author(s): Robert Finis Anderson, Haim Schweitzer
  
  

  Abstract
  The problem of finding a match for an image (or 'template') within a larger image is known as template matching and is key to a variety of Computer Vision applications. Typically template matching algorithms either run in fixed time, or are guaranteed to find an optimal match. We present an algorithm capable of finding the optimal match for a template which also finds an optimal or near-optimal match when terminated early. This allows the algorithm to run in a fixed time (a.k.a. hard real time) environment, as the algorithm can be halted after a fixed run time, regardless of the nature of the input. The implementation we test uses the Walsh Transform to progressively approximate match values, though any method of obtaining progressively tighter bounds on the match value is suitable. We analyze the algorithm's average performance on many image template pairs with varying levels of noise and and show that it typically produces optimal results in fixed time. We vary the run-time given to the algorithm and show that it typically finds an optimal match very quickly when a "good" (low noise) match exists.

  
   

Full Text (PDF)