Thinning methodologies−a comprehensive survey <s> z=1 <s> An improved method for automatic chromosome analysis consists of a preprocessing procedure and a boundary algorithm. The starting point is a transparency, converted by a flying spot scanner into an array of about 6*105 points, with a six-bit grey scale. Preprocessing applies to each grey level a Laplacian operator extended to a suitable region, corresponding to a high pass filter. This makes the threshold selection less critical and partially restores the degradation of the imaging process. The boundary algorithm isolates connected regions of the array by following isodensity contours and codes the boundary using three successive chains. From these chains the arm tips and centromeres are localized. A symmetry index is defined to check the reliability of the localizations. <s> BIB001 </s> Thinning methodologies−a comprehensive survey <s> z=1 <s> Abstract Binary pictures are taken into account and an algorithm which transforms a digital figure into a set of 8-simple digital arcs and curves, by employing local sequential operations, il illustrated. The adopted procedure considers the removal of suitable contour elements of the given figure and it is repeated on every current set of 1-elements as long as the final thinned figure is obtained. The notion of local elongation is employed to find, at every step of the process, those contour regions which can be regarded as significant protrusions. Then such regions are detected before applying the removal operations, contributing hence to the isotropic behavior of the proposed thinning transformation. Further refinements of the algorithm are also discussed. <s> BIB002 </s> Thinning methodologies−a comprehensive survey <s> z=1 <s> Abstract A fast thinning algorithm is proposed which achieves its increase in speed by applying any existing thinning algorithm to a greatly reduced amount of image information. The procedure compacts the image, applies an optimal thresholding routine, thins the result, and then expands the skeleton to its original scale. Results of testing the algorithm on a number of images are shown. <s> BIB003
However, use of the above conditions by themselves would give spurious end points and erode corners. Therefore, a solution is proposed in  to test p for deletion according to the configuration of contour pixels in N ( p ) . A "second level" crossing number C N N ( p ) represents the number of transitions from a contour pixel to a noncontour one (and vice-versa) when the points of N ( p ) are traversed in order, and procedures are derived for the deletion of p based on X R (~) , C N N ( p ) , and the number of 8-adjacent pairs of contour pixels among the 4-neighbors of p . Further work in preserving significant contour protrusions or prominences in the thinning process are developed by Arcelli and Sanniti di Baja  , [SI, where prominences are first detected and labeled. These significant protrusions are defined as connected subsets of the contour that are beyond a threshold distance from the interior or core (the noncontour pixels of P). They are retained while the other contour pixels with X , ( p ) = 2 are removed iteratively according to the conditions in  as long as they are not necessary for maintaining connectedness between the core and the prominences. When a set Sf with an empty core is obtained, a label e(p) = 2 ( 2 5 + 2 3 ) + 2 1 + 2 7 + 1 is assigned to each remaining pixel p in Sf. The nonmaxima pixels under this label are removed, resulting in a skeleton that is, at most, two pixels wide; then a final pass can be made to destroy 4-connectedness in favor of 8-connectedness. The skeletons obtained this way can be unduly influenced at the end of a branch by the presence of a sharp protrusion on one side (see Fig. 21a in BIB003 ). In BIB003 , a compression phase was also implemented to represent each 3 x 3 window of P by a grey-scale value derived from the number of black pixels in the window. The reduced grey-scale image is then thresholded with the connectivity constraints of Fig. 2 to a binary image on which thinning is performed by an implementation of BIB002 modified to preserve T junctions with length greater than one pixel [109] . The skeleton is then expanded to the original scale. When contour pixels ' p are traced sequentially and labeled, multiple pixels, where a pattern "folds" onto itself, can be easily determined [85] . Pixel p is multiple if at least one of the following conditions holds: P1: p is traversed more than once during tracing (connectivity number > 1). P2: p has no neighbors in the interior. P3: p has at least one 4-neighbor that belongs to the contour but is not traced immediately before or after p. Since P1 includes pixels with a connectivity number greater than 1, P2 includes end points, and P3 contains lines two pixels wide, the concept of multiple pixels is quite inclusive. However, if the contour is traced repeatedly and only the multiple pixels from every tracing are retained, the result may not be a connected skeleton. Therefore, in [85] , multiple pixels are called skeletal, as are 8-neighbors of skeletal pixels from a previous iteration. These pixels form a skeleton that may be too thick (and thus requires editing), but the algorithm was proved. to be correct-it does terminate and produces connected skeletons. In [86] and [87] , the characterization of multiple pixels is redefined in terms of local neighborhoods and can therefore be determined in sequence or parallel by comparison against a set of masks. This requires the addition of window (c) to those of Fig. 2 to produce the neighborhood patterns of Fig.  3 and their 90' rotations for multiple pixels. The definition of multiple pixels is slightly modified in [88] . It is also proposed that a combination of sequential and parallel operations may be more efficient for images where most of the pixels do not require much processing. For such images, the pattern can be divided into fields where each is assigned to a processor. Each processor operates on the pixels of its field sequentially, and when certain steps have been completed, it waits until all other processors have completed the same steps 3 . Configurations of multiple pixel p . Each group of pixels marked x or y must contain a nonzero element. In (c), at least one of the pixels marked 2 must be nonzero; if they are both nonzero, pixels marked x or y can have any value. The pixel marked d is a contour pixel. so that the processors can b e resynchronized. The above algorithm essentially ensures skeleton connectedness by detecting and assigning multiple pixels M to the skeleton S and then finding and assigning to S suitable (skeletal, nonmultiple) pixels to connect M to the interior of P. Since this may result in unacceptably thick skeletons when P is not initially almost thin, an alternative algorithm that deletes the nonmultiple pixels from the contour C and retains the remaining set as S is proposed [lo] . At the same time, contour information is used to determine whether a contour pixel should be a) regarded as noise and not labeled multiple or b) considered to be a significant convexity and assigned to S even though it is not multiple. These are accomplished by computing the n codes BIB001 of contour pixels from the Freeman chain codes obtained in contour tracing. The 1-code cz of pixel pi is the difference (modulo 8) between the chain codes at pi, and for n > 1, the n code determines the curvature of the contour at p,. The value of c, is used to determine a), and if c; exceeds a threshold, then p, is assigned to S so that it can represent a significant convexity. Naturally, if the threshold value is lower, the algorithm would be more sensitive to contour protrusions. Other works to preserve such prominences have already been discussed  , In [ 111-[ 131, the concept of multiple pixels is developed from another point of view; it is thought of as being the opposite of curve simplicity. In the continuous plane, a (closed) curve is simple if and only if it never crosses itself; consequently, a simple curve divides the plane into two connected sets called the inside and the outside. This notion is extended to the contour C of a digital pattern P for a simply connected pattern in [ l l ] and  and for a multiply connected figure in [13] . In particular, C is considered to be simple, provided that it neither touches nor overlaps itself, and this global concept was found to be equivalent to the following local conditions. If we consider P -C to be the inside of C and P to be the outside of C, then C is simple, provided that every p in C satisfies the following conditions: Al: N ( p ) n C consists of one (8-connected) component on the inside and one (4-connected) component on the outside. A2: N ( p ) n C contains at least two pixels that are horizontally or vertically aligned: one belonging to the outside and the other to the inside.