Method for efficiently registering object models in images via dynamic ordering of features

Abstract

An object model, having a plurality of features and described by a model state, is registered in an image. Unregistered features of the object model are dynamically selected such that the cost function of each feature search is minimized. A search is performed for a match of the selected model feature to the image, or to features within the image, to register the feature, and the model state is updated accordingly. These steps are repeated until all features have been registered. The search is performed in a region of high probability of a match. The cost function for a feature is based on the feature's basin of attraction, and in particular can be based on the complexity of the search process at each basin of attraction. A search region is based on a projected state probability distribution. In particular, the cost function is based on the “matching ambiguity,” or the number of search operations required to find a true match with some specified minimum probability. For feature-to-feature matching, the number of search operations is preferably the number of target features located within each search region. For feature-to-image matching, the matching ambiguity is computed, for each search region, by dividing the region into minimally-overlapping volumes which have the same size and shape as a basin of attraction associated with the feature, and then counting the number of volumes required to cover the regions. The model state is updated according to a propagated state probability distribution. Preferably, the propagation of the probability distribution is based on successive registered features.