Analysing and reducing the cost of exhaustive correspondence search

摘要

Correspondence matching is regarded as reliable, but computationally expensive. Previous methods that reduce the expense of interpretation tree search have been designed to detect a model that is present in the scene. Performance when the model is absent is inferior, and has not been studied in such depth. This paper analyses the search for an absent model, and from this develops methods that reduce the number of interpretations tested to less than (number of scene features)2. The methods are tested on 2D image data; results show that previous assumptions made in the analysis of interpretation tree (IT) search are significantly optimistic in estimating the computational cost for larger problems and the reliability of model detection. Methods for the synthesis of realistic test data and results of tests on them in scenes containing up to 1000 features are described. Tests of the methods on the synthesised scenes show a reduction in node count from previous methods of several orders of magnitude, so that correspondence search is viable in scenes of this size and larger.