A new algorithm is introduced to compute the curve skeleton of 3D objects by using the notion of local convexity. The centers of maximal balls detected on the distance transform of the object are filtered to select as anchor points only those located on sharp local convexities of the object's boundary. Then, the skeleton is obtained by means of topology preserving removal operations. Pruning is finally accomplished to remove from the skeleton scarcely significant peripheral branches.

In this paper an iris detection scheme for noisy images acquired by means of mobile devices is presented. Iris segmentation is accomplished by exploiting the use of the watershed transform with the purpose of identifying the iris boundary as much precisely as possible. After a pre-processing step aimed at color/illumination correction, the watershed transform is computed and suitably binarized. Circle fitting is then accomplished to identify the limbus boundary by using curvature approximation and a cost function for circle scoring. The watershed transform is furthermore employed to distinguish, in the zone delimited by the best fitting circle, the regions actually belonging to the iris from those belonging to eyelids and sclera. Finally, pupil detection is accomplished by means of circle fitting and by using a voting function based on homogeneity and separability criteria. The suggested iris detection scheme has a positive impact on an the accuracy in computing the iris code, which has in turn a positive impact on the performance of iris recognition.

A new pruning algorithm is introduced to remove peripheral branches of scarce relevance from the curve skeleton of 3D objects, while keeping the more relevant branches untouched. The algorithm does not require fine tuning of the parameters involved in the criteria suggested to evaluate branch significance and, in the average, produces satisfactory results.

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 technique for color quantization is described, which consists of two processes. The first process is based on the analysis of the histograms of the three color components of the RGB input image. The second process performs clustering of the colors quantized by the first process, based on their Euclidean distance. At the end of the second process, the output image is obtained by replacing the color of each pixel of the input image with the closest representative color. The obtained results are satisfactory from both the qualitative and the quantitative point of view.

This work concerns the development of a virtual training application in the medical field; it is based on augmented reality and image analysis techniques. Specifically, we tackled the problem of instructing the surgery staff to follow correctly the hand washing procedure necessary before accessing the operating theater, and of monitoring the correctness of the procedure performed by the physicians. This procedure is recommended by the World Health Organization (WHO) and is adopted by all health institutions of civilized countries. Lack of strict fulfillment of this recommendation is one of the major causes of infection risk in the operating rooms. By segmenting the scene captured by a webcam and by using image analysis tools, we detect the position of the forearms of the surgeon with respect to the basin and the water flow, and identify the beginning and the end of each phase of the hand washing procedure performed by the surgeon. The correct execution of the various phases, performed by a puppet in 3D, is projected so as to overlap the real scene captured by the webcam, while the correct procedure is also displayed as text. The application is developed under the supervision of the Risk-Management Department of the European Institute of Oncology (IEO) in Milan, Italy, and is designed to be used within the Surgical Care Area, directly in the washing area.

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.

This paper proposes to use case-based-reasoning for grey-level image segmentation. Different approaches to image segmentation have been proposed in the literature. The selection of the segmentation approach and the assignment of the values to the parameters involved in the selected algorithm depend on image domain and on the specific application. Case-based-reasoning seems a promising way to make the above selection automatic. In this paper, we describe the results of a preliminary study done in this respect. In particular, we refer to the automatic selection of the values of the parameters for a new watershed image segmentation algorithm.

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.

We suggest a tool to decompose 3D discrete objects into simpler parts. Decomposition is guided by object thickness and is based on region growing. Region growing starts from a set of seeds suitably identified in the innermost regions of the object. Our tool originates a decomposition into nearly convex and elongated parts. The decomposition is not affected remarkably by object rotation and has a limited computational cost. Since different recent imaging techniques give easier and cheaper access to 3D images, it is likely to believe that voxel-based decomposition tools, like the one here introduced, are of interest for future applications.

The paper presents a novel procedure to hierarchically decompose a multiscale discrete skeleton. The skeleton is a linear pattern representation that is generally recognized as a good shape descriptor. For discrete images, the discrete skeleton is often preferable. Multiresolution representations are convenient for many image analysis tasks. Our resulting skeleton decomposition shows two different types of hierarchy. The first type of hierarchy is one of different scales, as the original pattern is converted into an AND-pyramid and the skeleton is computed for each resolution level. The second type of hierarchy is established at each level of the pyramid by identifying and ranking skeleton subsets according to their permanence, where permanence is a property intrinsically related to local pattern thickness. To achieve the decomposition, both bottom-up and top-down analysis in the sense of moving from higher to lower resolution and vice versa are used. The bottom-up analysis is used to ensure that a part of the skeleton that is connected at a higher resolution level is also connected (if at all present) in the next, lower resolution level. The top-down analysis is used to build the permanence hierarchy ranking the skeleton components. Our procedure is based on the use of (3/spl times/3) local operations in digital images, so it is fast and easy to implement. This skeleton decomposition procedure is most effective on patterns having different thickness in different regions. A number of examples of decompositions of multiscale skeletons (with and without loops) are shown. The skeletons are, in most cases, nicely decomposed into meaningful parts. The procedure is general and not limited to any specific application.

In this communication, we illustrate an enlarging and enhancing procedure adequate to provide the restorer with sufficiently detailed digital versions of frescos in the excavations of Pompeii and Hercolaneum, starting from the photographic prints taken and archived in the early thirties for documentation purposes. First, filtering is done to improve the quality of the input data by removing acquisition and digitisation noise. Then, enlargement is done by using bilinear approximation. Finally, enhancement can be accomplished. To enhance only edges, we distinguish in the enlarged image edge regions from nonedge regions. This goal is achieved by applying edge detection and by thresholding the computed edge image. The obtained binary image is used as a reference to apply edge sharpening onto the enlarged image, and so obtain the enhanced image as desired. Though designed for a specific application, our method is indeed rather general.

Coarse-to-fine skeletons of digital patterns in binary images are computed on a grey-level pyramid. This is built in such a way that pattern shape and topology are preserved at all resolution levels, as faithfully as possible. A key problem is spurious holes, created at lower resolutions by region merging, that would originate spurious loops in coarse skeletons. This is solved by a novel technique exploiting the grey-level pyramid.

A multiresolution skeletonization algorithm is presented. The underlying data structure is a binary AND-pyramid. Notwithstanding the fact that the AND-pyramid is likely to break pattern connectedness at lower resolution levels, the algorithm generates connected skeletons at all resolution levels. It can most conveniently be implemented on a parallel SIMD architecture, but efficient MIMD and sequential implementations are also possible. A hierarchy among skeleton branches at various resolutions levels is also introduced.

We present an algorithm to build covering polyhedra for digital 3D objects, by iteratively filling local concavities. The resulting covering polyhedron is convex and is a good approximation of the convex hull of the object. The algorithm uses 3x3x3 operators and requires a few minutes for a 128 x 128 x 128 image, when implemented on a sequential computer. Once the covering polyhedron has been obtained, the object concavities can be identified by subtracting the object from the polyhedron and suitably post-processing the set difference. Features characterising the concavities can then be extracted and used as a tool for quantitative shape analysis.

The path-based distance skeleton is used to analyse the shape of a digital silhouette, perceived as the superposition of elongated regions. The skeleton is suitably decomposed and the resulting components are used to represent and describe the corresponding regions.

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.

Presents an iterative parallel procedure for computing concavity trees of a digital shape in a multi-resolution structure. The pattern is, at all resolution levels, covered by an almost convex polygon, closely fitting the pattern itself. When the polygons have been created, a hierarchical structure is built, which points out the relations among the concavities at different resolution levels. Also some properties characterizing the added regions are computed. On the highest resolution level, a meta-concavity tree is built up. This tree can be used to analyse and hierarchically rank the shape concavities.>

A parallel algorithm for smoothing and/or decomposing binary digital shapes is presented. The method uses a multiresolution pyramid, making it particularly suitable for parallel pyramid machines. The binary shape is first converted into a resolution pyramid. The lower resolution levels are used to smooth the shape at higher resolution levels. The smoothed versions, at different resolution levels, are then used to decompose the shape. This means that the shape is decomposed into parts according to the local thickness of the shape. The small and the slice-shaped components of the decomposition are finally merged into the larger components.>

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.>

The problem of computing area and perimeter of a digital figure presented by its discrete medial axis transform (MAT) is addressed. The figure is seen as the union of the square-shaped maximal neighborhoods centered on the local maxima of the MAT. The contribution given by each maximal neighborhood to figure area and perimeter is computed while tracing the MAT. Multiple overlaps among the maximal neighborhoods are possible. However, due to the properties of the local maxima and their associated maximal neighborhoods a single tracing of the MAT is provided to be sufficient to obtain the desired result. Thus, the procedure requires O(N) time, where N is the number of MAT pixels.>

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.>

An efficient skeletonizing algorithm is presented for the hexagonal grid. The skeleton has unit width, except at crossings and in regions of the shape having even width. Otherwise the skeleton has all the properties generally required for correct skeletons. It includes all local maxima, so complete recovery of the original shape is obtained by using the reverse distance transformation. The algorithm uses only local operations. Thus it can be performed both on sequential and parallel computers. In the sequential case described only three passes through the image are necessary, two to compute the distance transform and one for the identification of skeletal pixels.>

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.