Evolution-based methods for selecting point data for object localization: Applications to computer-assisted surgery

Object localization has applications in many areas of engineering and science. The goal is to spatially locate an arbitrarily shaped object. In many applications, it is desirable to minimize the number of measurements collected while ensuring sufficient localization accuracy. In surgery, for example, collecting a large number of localization measurements may either extend the time required to perform a surgical procedure or increase the radiation dosage to which a patient is exposed. Localization accuracy is a function of the spatial distribution of discrete measurements over an object when measurement noise is present. In previous work (J. of Image Guided Surgery, Simon et al., 1995), metrics were presented to evaluate the information available from a set of discrete object measurements. In this study, new approaches to the discrete point data selection problem are described. These include hillclimbing, genetic algorithms (GAs), and Population-Based Incremental Learning (PBIL). Extensions of the standard GA and PBIL methods that employ multiple parallel populations are explored. The results of extensive empirical testing are provided. The results suggest that a combination of PBIL and hillclimbing result in the best overall performance. A computer-assisted surgical system that incorporates some of the methods presented in this paper is currently being evaluated in cadaver trials.