1Department of Scientific Computing, Florida State University, 2US Army Natick Soldier Research, Development and Engineering Center
Saturday All day, Clinch Concourse
The now-familiar approach of landmark-based morphometric analysis is problematic for many anthropological (and other) data sets. Many structures of interest lack meaningful and repeatably identifiable landmarks. At the same time, it is becoming increasingly easy to collect data via surface scans for ever larger samples of specimens, making manual landmark placement for superimposition and other analyses impractically time consuming. One way to address this is through the use of landmark-free methods, such as the Iterative Closest Point (ICP) algorithm, to directly process the surface scans.
ICP relies on a nearest neighbor search (NNS), which is very computationally intensive. A simple NNS requires on the order of n2 operations, where n can reach easily into the hundreds of thousands. This poster presents a computationally efficient approach to ICP that yields a substantial reduction in computation costs. In this efficient method, we cluster the vertices in one scan into small groups, tracking cluster creation to form a spatial tree. Searches performed with these trees dramatically decreases the computational cost, to order n*log(n). For instance, superimposing two scans of 23,000 points using the new process was approximately sixty times faster than the naïve method.
The algorithm has been demonstrated here by fitting a sample of 40 bald head scans, provided by the US Armed Services, to a reference template to show regional variability. While the ICP algorithm is dependent on initialization, the conventional coordinate axes in the scans provide adequate initialization parameters. This method is applicable to most landmark-sparse structures.
This work was funded, in part, by Cooperative Research Agreement W911QY-12-2-0004 between Florida State University and the U.S. Army Natick Soldier Research, Development, and Engineering Center.