Speeding up shape-based matching with "Greediness"

The parameter "Greediness" defines a tradeoff between speed and completeness. On the one hand, the search speed can be increased by discarding candidates earlier based on a less strict criterion, while on the other hand, it might occur that no matches of the previously defined shape model are found even though suitable candidates are present in the image.

The shape model's contour consists of N points. For each point a gradient direction is calculated. The score is computed during the search for results as the (normalized) sum of the products of gradient vectors at the N model points and their corresponding gradients in the search image. Thus, if all gradient vectors are equal, the score is 1.0 (perfect match).

To save run time, shape-based matching does not include all points at once. Instead, the number of points used is gradually increased. Therefore, a candidate can already be discarded if you know that the current computed score cannot reach the MinScore anymore with the remaining points. Besides, a candidate can be accepted as soon as you know that the score will not drop below the MinScore.

For Greediness=0, the candidate is discarded only, if it is sure that the MinScore cannot be reached anymore. This is the case if the remaining terms of the sum are smaller or equal to 1. Thus, the match can be discarded safely if:

<code>Score_j < MinScore - (1-j/N)</code>

with j = number of currently used points for the calculation, N = number of all model points, and Score_j = currently computed score based on the first j points. Hence,

<code>1-j/N</code> is the score that can be achieved at maximum based on the remaining points.

For Greediness=1, the candidate is already discarded if:

<code>Score_j < MinScore * j/N</code>

In this case, the rejection is based on the assumption (certain probability) that the MinScore cannot be reached even with the remaining points. There might however still be a chance to reach the MinScore but, in order to save run time, the candidate is discarded nevertheless.

Greediness values between 0 and 1 combine both approaches, such that the criterion for discarding the candidate in not as hard as setting Greediness = 1, but the search is not continued until the safe criterion is reached (Greediness = 0).

In conclusion, it's possible to find an optimal set of MinScore and Greediness in terms of tradeoff between detection rate and speed. For this task, HDevelop's matching assistant can be a suitable option (see screenshot). Further information on speedup vs. robustness and advanced parameters can be found in this tutorial video.