Find the best matches of multiple shape models.

The operator find_shape_models finds the best NumMatches instances of the shape models that are passed in the tuple ModelIDs in the input image Image. The models must have been created previously by calling create_shape_model or read_shape_model.

Hence, in contrast to find_shape_model, multiple models can be searched in the same image in one call. This changes the semantics of all input parameters to some extent. All input parameters must either contain one element, in which case the parameter is used for all models, or must contain the same number of elements as ModelIDs, in which case each parameter element refers to the corresponding element in ModelIDs. (NumLevels may also contain either two or twice the number of elements as ModelIDs; see below.) As usual, the domain of the input image Image is used to restrict the search space for the reference point of the models ModelIDs. Consistent with the above semantics, the input image Image can therefore contain a single image object or an image object tuple containing multiple image objects. If Image contains a single image object, its domain is used as the region of interest for all models in ModelIDs. If Image contains multiple image objects, each domain is used as the region of interest for the corresponding model in ModelIDs. In this case, the image matrix of all image objects in the tuple must be identical, i.e., Image cannot be constructed in an arbitrary manner using concat_obj, but must be created from the same image using add_channels or equivalent calls. If this is not the case, an error message is returned. The above semantics also hold for the input control parameters. Hence, for example, MinScore can contain a single value or the same number of values as ModelIDs. In the first case, the value of MinScore is used for all models in ModelIDs, while in the second case the respective value of the elements in MinScore is used for the corresponding model in ModelIDs. An extension to these semantics holds for NumMatches and MaxOverlap. If NumMatches contains one element, find_shape_models returns the best NumMatches instances of the model irrespective of the type of the model. If, for example, two models are passed in ModelIDs and NumMatches = 2 is selected, it can happen that two instances of the first model and no instances of the second model, one instance of the first model and one instance of the second model, or no instances of the first model and two instances of the second model are returned. If, on the other hand, NumMatches contains multiple values, the number of instances returned of the different models corresponds to the number specified in the respective entry in NumMatches. If, for example, NumMatches = [1,1] is selected, one instance of the first model and one instance of the second model is returned. For a detailed description of the semantics of NumMatches, see below. A similar extension of the semantics holds for MaxOverlap. If a single value is passed for MaxOverlap, the overlap is computed for all found instances of the different models, irrespective of the model type, i.e., instances of the same or of different models that overlap too much are eliminated. If, on the other hand, multiple values are passed in MaxOverlap, the overlap is only computed for found instances of the model that have the same model type, i.e., only instances of the same model that overlap too much are eliminated. In this mode, models of different types may overlap completely. For a detailed description of the semantics of MaxOverlap, see below. Hence, a call to find_shape_models with multiple values for ModelIDs, NumMatches and MaxOverlap has the same effect as multiple independent calls to find_shape_model with the respective parameters. However, a single call to find_shape_models is considerably more efficient.

The type of the found instances of the models is returned in Model. The elements of Model are indices into the tuple ModelIDs, i.e., they can contain values from 0 to |ModelIDs|-1. Hence, a value of 0 in an element of Model corresponds to an instance of the first model in ModelIDs.

The position and rotation of the found instances of the model is returned in Row, Column and Angle. The coordinates Row and Column are the coordinates of the origin of the shape model in the search image. By default, the origin is the center of gravity of the domain (region) of the image that was used to create the shape model with create_shape_model. A different origin can be set with set_shape_model_origin. Additionally, the score of each found instance is returned in Score. The score is a number between 0 and 1, which is an approximate measure of how much of the model is visible in the image. If, for example, half of the model is occluded, the score cannot exceed 0.5.

The domain of the image Image determines the search space for the reference point of the model, i.e., for the center of gravity of the domain (region) of the image that was used to create the shape model with create_shape_model. A different origin set with set_shape_model_origin is not taken into account. The model is searched within those points of the domain of the image, in which the model lies completely within the image. This means that the model will not be found if it extends beyond the borders of the image, even if it would achieve a score greater than MinScore (see below). The parameters AngleStart and AngleExtent determine the range of rotations for which the model is searched. If necessary, the range of rotations is clipped to the range given when the model was created with create_shape_model. In particular, this means that the angle ranges of the model and the search must truly overlap. The angle range in the search is not adapted modulo 2*pi. To simplify the presentation, all angles in the remainder of the paragraph are given in degrees, whereas they have to be specified in radians in find_shape_models. Hence, if the model, for example, was created with AngleStart = -20° and AngleExtent = 40° and the angle search space in find_shape_models is, for example, set to AngleStart = 350° and AngleExtent = 20°, the model will not be found, even though the angle ranges would overlap if they were regarded modulo 360°. To find the model, in this example it would be necessary to select AngleStart = -10°.

The parameter MinScore determines what score a potential match must at least have to be regarded as an instance of the model in the image. The larger MinScore is chosen, the faster the search is. If the model can be expected never to be occluded in the images, MinScore may be set as high as 0.8 or even 0.9.

The maximum number of instances to be found can be determined with NumMatches. If more than NumMatches instances with a score greater than MinScore are found in the image, only the best NumMatches instances are returned. If fewer than NumMatches are found, only that number is returned, i.e., the parameter MinScore takes precedence over NumMatches.

If the model exhibits symmetries it may happen that multiple instances with similar positions but different rotations are found in the image. The parameter MaxOverlap determines by what fraction (i.e., a number between 0 and 1) two instances may at most overlap in order to consider them as different instances, and hence to be returned separately. If two instances overlap each other by more than MaxOverlap only the best instance is returned. The calculation of the overlap is based on the smallest enclosing rectangle of arbitrary orientation (see smallest_rectangle2) of the found instances. If MaxOverlap=0, the found instances may not overlap at all, while for MaxOverlap=1 all instances are returned.

The parameter SubPixel determines whether the instances should be extracted with subpixel accuracy. If SubPixel is set to 'none' (or 'false' for backwards compatibility) the model's pose is only determined with pixel accuracy and the angle resolution that was specified with create_shape_model. If SubPixel is set to 'interpolation' (or 'true') the position as well as the rotation are determined with subpixel accuracy. In this mode, the model's pose is interpolated from the score function. This mode costs almost no computation time and achieves an accuracy that is high enough for most applications. In some applications, however, the accuracy requirements are extremely high. In these cases, the model's pose can be determined through a least-squares adjustment, i.e., by minimizing the distances of the model points to their corresponding image points. In contrast to 'interpolation', this mode requires additional computation time. The different modes for least-squares adjustment ('least_squares', 'least_squares_high', and 'least_squares_very_high') can be used to determine the accuracy with which the minimum distance is being searched. The higher the accuracy is chosen, the longer the subpixel extraction will take, however. Usually, SubPixel should be set to 'interpolation'. If least-squares adjustment is desired, 'least_squares' should be chosen because this results in the best tradeoff between run time and accuracy.

The number of pyramid levels used during the search is determined with NumLevels. If necessary, the number of levels is clipped to the range given when the shape model was created with create_shape_model. If NumLevels is set to 0, the number of pyramid levels specified in create_shape_model is used. Optionally, NumLevels can contain a second value that determines the lowest pyramid level to which the found matches are tracked. Hence, a value of [4,2] for NumLevels means that the matching starts at the fourth pyramid level and tracks the matches to the second lowest pyramid level (the lowest pyramid level is denoted by a value of 1). This mechanism can be used to decrease the runtime of the matching. It should be noted, however, that in general the accuracy of the extracted pose parameters is lower in this mode than in the normal mode, in which the matches are tracked to the lowest pyramid level. Hence, if a high accuracy is desired, SubPixel should be set to at least 'least_squares'. If the lowest pyramid level to use is chosen too large, it may happen that the desired accuracy cannot be achieved, or that wrong instances of the model are found because the model is not specific enough on the higher pyramid levels to facilitate a reliable selection of the correct instance of the model. In this case, the lowest pyramid level to use must be set to a smaller value. If the lowest pyramid level is specified separately for each model, NumLevels must contain twice the number of elements as ModelIDs. In this case, the number of pyramid levels and the lowest pyramid level must be specified interleaved in NumLevels. If, for example, two models are specified in ModelIDs, the number of pyramid levels is 5 for the first model and 4 for the second model, and the lowest pyramid level is 2 for the first model and 1 for the second model, NumLevels = [5,2,4,1] must be selected. If exactly two models are specified in ModelIDs, a special case occurs. If in this case the lowest pyramid level is to be specified, the number of pyramid levels and the lowest pyramid level must be specified explicitly for both models, even if they are identical, because specifying two values in NumLevels is interpreted as the explicit specification of the number of pyramid levels for the two models.

The parameter Greediness determines how ``greedily'' the search should be carried out. If Greediness=0, a safe search heuristic is used, which always finds the model if it is visible in the image. However, the search will be relatively time consuming in this case. If Greediness=1, an unsafe search heuristic is used, which may cause the model not to be found in rare cases, even though it is visible in the image. For Greediness=1, the maximum search speed is achieved. In almost all cases, the shape model will always be found for Greediness=0.9.

If the parameter values are correct, the operator find_shape_models returns the value 2 (H_MSG_TRUE). If the input is empty (no input images are available) the behavior can be set via set_system('no_object_result',<Result>). If necessary, an exception is raised.

find_shape_models is reentrant and processed without parallelization.

add_channels, create_shape_model, read_shape_model, set_shape_model_origin

find_scaled_shape_models, find_shape_model, find_scaled_shape_model, best_match_rot_mg

Template matching