New watershed methods for isolating and characterizing discrete objects in 3D data sets

This paper introduces new algorithms for conducting and improving watershed analysis, implemented with the particular goal of improving the ability to measure the shapes of mineral grains to be subsequently be analyzed by mass spectrometry. This application requires a high degree of accuracy and fidelity in terms of both separating all touching grains and preserving their shapes. The algorithms are designed to take advantage of a vector-based programming environment. A new implementation of the Euclidean distance transform utilizes the fact that the distance from any adjacent pair of voxels to the nearest boundary must be within one voxel of each other. In practice, however, this algorithm is outperformed by a smoothed approximate distance transform that is faster to compute and results in less irregular watershed boundaries. A one-pass rainfall-based watershed algorithm is introduced that runs in linear time with the number of segmented voxels, and requires no priority queue. Unlike marker-based watershed algorithms based on the basin-filling approach, the rainfall approach finds watersheds associated with all local maxima in the distance map, even if a marking algorithm is used. A post-watershed smoothing algorithm improves watershed boundaries and eliminates small spurious watersheds. The one-pass watershed and post-watershed smoothing algorithms run in times superior or comparable to basin-fill watershed algorithms implemented in other environments, and offers excellent ability to separate touching objects efficiently while placing watershed boundaries that maximize the preservation of details of particle shape. Further time improvement could come from implementing them in a vector-based environment that allows explicit multi-threading.