The distance labeled curve skeleton of a 3D object is used to guide the decomposition of the object into disjoint parts. To this aim, the skeleton is polygonally approximated by taking into account spatial coordinates and distance values of its voxels. The obtained skeleton segments are characterized by the absence of significant changes of curvature. Moreover, along each skeleton segment distance values are constant or show a linearly changing trend. Each segment can be interpreted as the spine of a simple part, which is characterized by the absence of significant curvature changes along its boundary, and by local thickness that is constant or evolves linearly along the part. By using exclusively the spatial coordinates and distance values of the vertices of the spines, quantitative information on shape, size, position and orientation of the corresponding simple parts can be obtained. Alternative decompositions of the object can be computed by selecting different values for the threshold used during polygonal approximation of the skeleton. Some criteria are also discussed for the selection of optimal threshold values originating approximated skeletons having a small number of segments, but still producing decompositions rather well adapting the input object boundary.

A distance-driven method to compute the surface and curve skeletons of 3D objects in voxel images is described. The method is based on the use of the <3,4,5> weighted distance transform, on the detection of anchor points, and on the application of topology preserving removal operations. The obtained surface and curve skeletons are centered within the object, have the same topology as the object, and have unit thickness. The object can be almost completely recovered from the surface skeleton since this includes almost all of the centers of maximal balls of the object. Hence, the surface skeleton is a faithful representation. In turn, though only partial recovery is possible from the curve skeleton, this still provides an appealing representation of the object.

A method to decompose a complex 3D object into simpler parts is presented, based on a suitable partition of the curvilinear skeleton of the object. The curvilinear skeleton is divided into subsets, by taking into account the regions of influence that can be associated with its branch points. The obtained subsets are then used to recover the parts into which the object can be decomposed.

A method to compute a linear medial representation of a complex surface in the 3D discrete space is presented. The method involves voxel classification, surface labeling, anchor point detection, and voxel removal.

We present a method to assign to either the foreground or the background the regions into which a gray-level image is partitioned by watershed transformation. Our method is inspired by visual perception in the sense that the border separating any foreground component from the background is detected in correspondence with the locally maximal gray-level changes through the image. The method is implemented as consisting of three steps. The first two steps perform a basic assignment of the regions, while the remaining step examines again some regions tentatively assigned to the background during the second step and possibly changes their status. A feature of the method is that a hierarchical ranking of the regions assigned to the foreground is also accomplished.

The repeated application of topology preserving reduction operations to a gray-tone digital image produces a homotopic image including a set S which has graphlike structure and may be regarded as a stylized version of the foreground, when it is perceived as an elongated subset of the image. To improve the capability of S to represent the foreground in a perceptually appealing way, it is convenient to modify some of the arcs of S by removing part or all of them. This regularization of S is discussed in the paper with respect to different significance measures for arc points, which allow an evaluation of the saliency of each arc. We deal with two types of regularization criteria, which are respectively applied while examining the arcs from end points and from normal points. Specific criteria depend on parameters which are allowed to vary within certain ranges and should be tuned with respect to the application at hand. Both types of criteria are concerned with the closeness of an arc to the part of the background surrounding it, but the former takes also into account the region elongation, while the latter is concerned with the indentations possibly present in the profile of the arc. Experimental work has been carried out on gray-tone images including neurons, and some results are shown.

Reduction operators iteratively applied to gray-tone pictures cause dilation of the regions, the gray-value of which is locally minimal, so that a gray-tone picture with no distinction between foreground and background is transformed into a set of bottom regions separated by ridge lines. The set of ridge lines can be understood as the skeleton of what is perceived as foreground. We describe a two-subiteration parallel skeletonization algorithm employing new reduction operators which are based on the nonridge point condition and are topology preserving. The performance of the algorithm is discussed, in particular with respect to certain critical configurations, and experimental work is reported to evaluate the thinning capability of the proposed reduction operators.

Lowering operations play a key role when skeletonizing a gray-tone picture. We define ridge points in a 3/spl times/3 neighborhood, and discuss the computational advantage obtained when lowering is accomplished by parallel operations based on a non-ridge point condition rather than on a simple point condition. Two parallel algorithms are given, respectively characterized by four subiterations and two subiterations.

An algorithm for the detection of dominant points and for building a hierarchical approximation of a digital curve is proposed. The algorithm does not require any parameter tuning and is shown to perform well for a wide variety of shapes, including scaled and rotated ones. Dominant points are first located by a coarse-to-fine detector scheme. They constitute the vertices of a polygon closely approximating the curve. Then, a criterion of perceptual significance is used to repeatedly remove suitable vertices until a stable polygonal configuration, the contour sketch, is reached. A highly compressed hierarchical description of the shape also becomes available.>

A 4-subiteration parallel thinning algorithm, based on 3×3 operations, is proposed. It is shown that by taking into account bidirectional compression in each subiteration, pixels belonging to a pair of successive contours, a 4-contour and an 8-contour, are removed from the pattern in every iteration. Therefore, contour pixel removal proceeds towards the inner part of the pattern according to the octagonal metric. This provides a resulting medial line which is centered in the pattern in a quasi-Euclidean sense and is less sensitive to pattern rotation. The performance of the algorithm is discussed and compared with that of some well-known parallel algorithms.

A skeletonizing procedure is illustrated that is based on the notion of multiple pixels as well as on the use of the 4-distance transform. The set of the skeletal pixels is identified within one sequential raster scan of the picture where the 4-distance transform is stored. Two local conditions, introduced to characterize the multiple pixels are employed. Since the set of the skeletal pixels is at most two pixels wide, the skeleton can be obtained on completion of an additional inspection of the picture, during which time standard removal operations are applied. Besides being correct and computationally convenient, the procedure produces a labeled skeleton, i.e. a skeleton whose adequacy for shape description purposes is generally acknowledged.>

A smoothing method based on the simultaneous processing of the distance transforms of the figure and of its complement is described. This method can be regarded as a tool to enrich the set of the picture modifications that are achievable by using distance transformations. Both figure protrusions and dents are modified within the same process in a parallel fashion. In the standard method based on the application of a suitable sequence of shrink and expand operations, figure protrusions and dents are modified within two distinct processes. Thus, the proposed method is computationally more convenient than the sequence of the two previous processes.>

The skeleton of a digital figure can often be regarded as a convenient alternative to the figure itself. It is useful both to diminish drastically the amount of data to be handled, and to simplify the computational procedures required for description and classification purposes. Thinning a digital figure down to its skeleton is a time-consuming process when conventional sequential computers are employed. The procedure we propose allows one to speed up the thinning transformation, and to get a well-shaped skeleton. After cleaning of the input picture has been performed, the pixels of the figure are labeled according to their distance from the background, and a set, whose pixels are symmetrically placed with respect to distinct contour parts of the figure, is found. This set is then given a linear structure by applying topology preserving removal operations. Finally, a pruning step, regarding branches not relevant in the framework of the problem domain, completes the process. The resulting skeleton is a labeled set of pixels which is shown to possess all the required properties, particularly those concerning connectedness, topology, and shape. Moreover, the original figure can almost completely be recovered by means of a reverse distance transformation. Only a fixed and small number of sequential passes through the picture is necessary to achieve the goal. The computational effort is rather modest, and the use of the proposed algorithm turns out to be more advantageous the greater the width of the figure to be thinned.

In picture processing it is often convenient to deal with a stick-like version (skeleton) of binary digital images. Although skeleton connectedness is not necessary for storage and retrieval purposes, this property is desirable when a structural description of images is of interest. In this paper a parallel procedure is described which, applied to a connected image, originates a connected skeleton made by the union of simple digital arcs. The procedure involves a step by step propagation of the background over the image. At every step, contour elements either belonging to the significant convex regions of the current image or being local maxima of the original image are selected as skeleton elements. Since the final set so obtained is not ensured to be connected, the configurations in correspondence of which disconnections appear are investigated and the procedures to avoid this shortcoming are given. The presence of the whole set of local maxima among the skeleton elements ensures the possibility of recovering the original image by means of a reverse distance transform. The details of the program implementing the proposed algorithm on a parallel processor are finally included.

A computer program has been written to separate overlapping convex blobs present in a binary input picture. The procedure is based on the detection of a feature, concavity, which occurs on the intersecting contours of the overlapping blobs. In order to obtain splitting, paths are grown from these regions of concavity toward the interior until segmentation is achieved. Flow charts of the program and an example are included.