Template block matching using a similarity function and incremental threshold

摘要

A method of matching a template to a signal using a similarity function (SF) giving a measure of similarity between the template and a block (e.g. of image pixels) of the signal, having dimensions of the template, comprises: calculating an initial lower bound on the similarity function (SF) for a number of blocks; determining a threshold (e.g. such as T1-T3, shown against Euclidean distance in Figure 4); rejecting blocks for which the lower bound is greater than the threshold; recalculating an improved lower bound on the similarity function for remaining blocks; and repeating the threshold determination and later steps until a predetermined number of blocks remain. The method is further characterised in that the threshold is given by calculating the similarity function value between template and block having the nth lowest bound, and adding an increment to this value. The similarity function may be a function of Euclidian distance. The nth lowest bound may be the lowest lower bound. The method, and an equivalent apparatus, serves to improve digital image block matching by optimising choice of rejection threshold.