Skip to content

Speeding up the searchđź”—

There are different ways you can speed up the search.

  • Restricting the search space
  • Using subsampling
  • Using a “greedy” search to reject candidates early
  • Limiting the number of candidates directly or by requiring a minimal score

Restricting the search spaceđź”—

An important concept in the context of finding objects is that of the so-called search space. Quite literally, this term specifies where to search for the object.

Depending on the matching approach, this space encompasses not only the two dimensions of the image, but also other parameters like the possible range of scales and orientations or the question of how much of the object must be visible. The more you can restrict the search space, the faster the search will be.

The most obvious way to restrict the search space, which is suitable for all matching approaches, is to apply the operator that is used to find the model in an image to an ROI instead of the whole image.

Other parameters that can be used to restrict the search space depend on the specific matching approach. Some approaches are already very strict, others allow different changes of the object like rotation or scale and thus a restriction of the search space is strongly recommended.

Shape-based matching, for example, allows arbitrary orientation and scale changes as well as occlusions of the model instances in the search images. Thus, for shape-based matching also the range of orientation and scale as well as the visibility, that is, the amount of allowed occlusions of the model instance in the image, should be restricted to speed up the search.

About subsamplingđź”—

The image pyramid can be used to speed-up the search. In order to benefit from the subsampling, the images should have as much contrast as possible.

The parameter NumLevels, which you already specified when creating the model, allows you to use a different (in most cases a more restrictive) value in the search process. By using the value 0 for NumLevels, the value specified when creating the model is used.

Optionally, NumLevels can contain a second value, so that you can specify not only the highest but also the lowest pyramid level used for the search. If the search is finished on a pyramid level that is higher than the first pyramid level, which corresponds to the original, full-sized image, the search becomes faster.

On the other hand, the search is then also less robust and less accurate. If objects should also be found in images of poor quality, for example, if the object is defocused, deformed, or noisy, you can activate the increased tolerance mode by specifying the second value negatively. Then, the matches on the lowest pyramid level that still provides matches are returned.

In case high noise is affecting the matching results you can also use adapt_shape_model_high_noise in order to estimate the lowest pyramid level for the shape model.

About greedinessđź”—

Affected parameter

Greediness

Greediness is a trade between thoroughness and speed.

With the parameter Greediness you can influence the search algorithm itself and thereby trade thoroughness against speed. If you select the value 0, the search is thorough, that is, if the object is present (and within the allowed search space and reaching the minimum score), it will be found.

In this mode, however, even very unlikely match candidates are also examined thoroughly, thereby slowing down the matching process considerably.

The main idea behind the “greedy” search algorithm is to abort the comparison of a candidate with the model when it seems unlikely that the minimum score will be reached. In other words, the goal is not to waste time on hopeless candidates.

This greediness, however, can have unwelcome consequences: In some cases a perfectly visible object is not found because the comparison “starts out on a wrong foot” and is therefore classified as a hopeless candidate and aborted.

You can adjust the Greediness of the search, that is, how early the comparison is aborted, by selecting values between 0 (no abort: thorough but slow) and 1 (earliest abort: fast but unsafe).

Note

Note that the parameters Greediness and MinScore interact, that is, you may have to specify a lower minimum score in order to use a greedier search. Generally, you can reach a higher speed with a high greediness and a sufficiently lowered minimum score.

Limiting number of candidatesđź”—

Affected parameters

MinScore, NumMatches

The search speed can be increased by limiting the number of candidates tracked through the pyramid levels. Both parameters MinScore and NumMatches have the intention to limit the number of tracked and returned candidates, but they do in different ways.

With MinScore you set a required score every candidate must have on every level of the pyramid. Thus, when a candidate gets a lower score on a higher pyramid level it gets rejected. As a consequence the candidate does not get tracked down to the lowest level, even if he would obtain the best score on the original image.

With NumMatches you limit the number of instances to be returned to a maximum of the set number. This limit generally applies to every pyramid level (with exceptions as for example the top level - where NumMatches does not restrict the number of candidates to be considered - or shape-based matching with clutter set which is explained in set_generic_shape_model_param). The interplay with MinScore may lead to unwanted rejections.

Example

Assume our pyramid has three levels and we find 3 suitable candidates on the top pyramid level: A, B, and C. They are tracked to the second pyramid level, where they get the scores
\(S_A^2\): \(0.92\),
\(S_B^2\): \(0.82\),
\(S_C^2\): \(0.81\).

On the lowest pyramid level, level 1, they get the score
\(S_A^1\): \(0.93\),
\(S_C^1\): \(0.79\),
\(S_C^1\): \(0.80\).

What happens when we would have set for this search MinScore = 0.8 and NumMatches = 2?

On the top level we find 3 all candidates.

We track them all to the second level, where we keep only the best 2 candidates A and B, while C gets rejected. The search continues on the next lower pyramid level. Tracking the candidates down, they get a new score on this lower level. So we reject B and end up with A, thus only 1 match. C would have got a score high enough but we rejected it already earlier.

If we would have kept all 3 candidates from the top level, thus not reject C, we would have found 2 matches. This explains why the number of matches or even the found match can differ when setting NumMatches.

Also the candidate with the highest score on a higher level is not necessarily the candidate with the highest score on the lowest level. For this reason the returned instance for NumMatches = 1 can differ from the instance with the highest score returned when more matches are returned by setting NumMatches to a value higher 1.

As a consequence we recommend to return several instances and then select the instance with the highest score in case multiple objects with a similar score are expected, but only the one with the highest score is of interest.