TEASAR: tree-structure extraction algorithm for accurate and robust skeletons

Abstract

We introduce the TEASAR algorithm which is a treestructure extraction algorithm delivering skeletons that are accurate and robust. Volumetric skeletons are needed for accurate measurements of length along branching and winding structures. Skeletons are also required in automatic virtual navigation, such as traveling through human organs (e.g., the colon) to control movement and orientation of the virtual camera. We introduce a concise but general definition of a skeleton, and provide an algorithm that finds the skeleton accurately and rapidly. Our solution is fully automatic, which frees the user from having to engage in data preprocessing. We present the accurate skeletons computed on a number of test datasets. The algorithm is efficient as demonstrated by the running times on a single 194 MHz MIPS R10000 CPU which were all below five minutes.