An efficient algorithm for boundary tracing and feature extraction

Abstract

An algorithm is described that traces and labels the boundaries of objects whose images are stored as a condensed linear array of coordinate values defining the successive intersections of a linear raster with the object boundaries. The vector distances between adjacent boundary points are summed to give perimeter values, which, for closed Euclidean curves, converge to within 3.0% of the boundary length as the raster spacing is decreased. Similarly, estimates for areas within closed boundaries converge to within 0.1% of true values. Intercept lengths and moments of intercept lengths for areas of different composition or gray level within each labeled object are determined, as well as measures of contact area within volume, and of transition probabilities between all compositional pairs. An approximate maximum caliper diameter is simply derived, as well as an ellipse that is the best least-squares fit to the object perimeter points. A variety of stereological and statistical measures for individual objects can be developed from the results provided by the algorithm, and a number of population distributions can be constructed by their combination.