Template matching using correlative auto-predicative search

A device for determining a fixed step size which is used for stepping through a search area to select a subset of window areas within a search area to be evaluated for locating a match between a subject template of data and the search area of data, the subject template including a first plurality of data points, the search area including a second plurality of data points exceeding in number the first plurality of data points, the device comprising:

• means for creating a created template from the subject template without use of the search area data;
• and
• means for correlating the subject template to window areas within the created template to derive the fixed step size for stepping through the search area;
• wherein the creating means comprises means for padding the subject template with additional data to enlarge the subject template into the created template, wherein a first window area within the created template is formed by the subject template and includes the first plurality of data points.

An apparatus for estimating a location of a first template of data within a search area of data, the first template including a first plurality of data points, the search area including a second plurality of data points exceeding in number the first plurality of data points, the apparatus comprising:

• a processor which pads the first template with additional data to enlarge the template into a padded template, wherein a first window area within the padded template is formed by the first template and includes the first plurality of data points;
• a correlator which correlates the first template to window areas within the padded template to derive a first step size;
• a selector which steps though the search area using the first step size to select window areas within the search area;
• and
• an evaluator which evaluates the selected window areas for locating a match between the first template of data and the search area of the data.

A method for locating a match between a first template of data and a search area of data, the first template including a first plurality of data points, the search area including a second plurality of data points exceeding in number the first plurality of data points, the method comprising the steps of:

• padding the first template with additional data to enlarge the template into a padded template, wherein a first window area within the padded template is formed by the first template and includes the first plurality of data points;
• correlating the first template to window areas within the padded template along a first axis to derive a first step size;
• stepping through the search area using the first step size for selecting window areas within the search area;
• and
• evaluating the selected window areas for locating a match between the first template of data and the search area of the data.