Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> In this report three thinning algorithms are developed: one each for use with rectangular, hexagonal, and triangular arrays. The approach to the development of each algorithm is the same. Pictorial results produced by each of the algorithms are presented and the relative performances of the algorithms are compared. It is found that the algorithm operating with the triangular array is the most sensitive to image irregularities and noise, yet it will yield a thinned image with an overall reduced number of points. It is concluded that the algorithm operating in conjunction with the hexagonal array has features which strike a balance between those of the other two arrays. <s> BIB001 </s> Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> Sticklike figures can be obtained through the sequential application of a set of eight masks, each one applied in parallel. During the process, components neither disconnect nor vanish. Particular emphasis is given to the simplicity and speed of the algorithm when implemented on a parallel machine. <s> BIB002 </s> Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> Abstract Removal operations play a crucial role in most algorithms which transform digital figures into stick-like ones. In this note, digital points that are candidates to deletion are examined and a necessary and sufficient condition for their removal is given. <s> BIB003 </s> Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> Abstract Given an elongated object in a digital image, a thinning transform is described to simultaneously calculate the coordinates of its medial line elements and a value for these elements equal to the width of the object at the element's coordinates. The transform is being used in the area of quantitative fractography in photo-micrographs of rock samples. <s> BIB004 </s> Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> 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. <s> BIB005 </s> Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> Abstract In recoding with three bits the pixels of objects in binary images according to some measure of distance to the background, parallel thinning is achieved using syntactic rules. The codes in a 3 × 2 window are searched for interrelations which determine the new code of the central pixel. The local structure of the codes is determined through a binary cascade of tables. To each structure corresponds a rewriting rule. The new code is the output of the cascade. A two-scan postprocessing is needed to obtain a skeleton with linear structure. <s> BIB006 </s> Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> The authors review their pseudo-one-subcycle parallel thinning algorithm. They present two improved versions of this algorithm, and describe a two-stage structure to realize the one-subcycle parallel algorithm. The first stage is to produce a perfect 8-curve excluding T-junction thin line. The second is to obtain the isotropic skeleton of an L-shaped pattern. The two stage structure consists of a thinning table and a control unit. The thinning table is used to provide the attributions for an input 3*3 local pattern. The control unit is used to check the removal of the center pixel of this local pattern, and the inputs of the control unit also comprise the outputs of other neighboring thinning tables. This structure can exactly implement the proposed one-subcycle parallel algorithms. The two improved algorithms have been implemented. Experiments confirm that the improved algorithms can produce the desired effective thin line and also show that the structure realized is feasible and practicable. > <s> BIB007 </s> Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> Two parallel thinning algorithms are presented and evaluated in this article. The two algorithms use two-subiteration approaches: (1) alternatively deleting north and east and then south and west boundary pixels and (2) alternately applying a thinning operator to one of two subfields. Image connectivities are proven to be preserved and the algorithms' speed and medial curve thinness are compared to other two-subiteration approaches and a fully parallel approach. Both approaches produce very thin medial curves and the second achieves the fastest overall parallel thinning. <s> BIB008 </s> Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> Abstract A one-pass iterative parallel thinning algorithm has been designed to reduce a two-dimensional pattern of strokes to its skeleton by removing layers of edge element until stroke has unitary thickness. An edge test computation is simulataneously carried out for each element in the two-dimensional pattern by inspecting the values of its neighbours. However, there is a degree of duplication among edge computations for elements with common neighbours. A modified algorithm described in this paper which avoids duplication at the cost of extra communication. The speed of the modified algorithm compared to the original algorithm is 1. (i) approximately 45% better on the ICL DAP; 2. (ii) approximately 30% better on the CRAY X-MP. <s> BIB009 </s> Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> A recently published parallel thinning approach [ 4 ] is evaluated. An improvement is suggested to enable preservation of certain diagonal lines which are not preserved by this algorithm. A unified notion of what is meant by an iteration (or subiteration) and parallel speed is presented, and with regard to its parallel speed this algorithm is argued to be comparable to other two-subiteration algorithms. The parallel speed of this algorithm is compared experimentally to the original algorithm that it improves [ 12 ] and it is shown that, unlike execution time on a specific machine, parallel speed is not improved. Finally, a more complete connectivity analysis is given illustrating sufficient additional conditions for applying fully in parallel the basic thinning operator used in both algorithms while maintaining all image connectivity properties. <s> BIB010 </s> Thinning methodologies−a comprehensive survey <s> IV. PARALLEL THINNING ALGORITHMS <s> Abstract This paper presents a parallel-symmetric thinning algorithm (PSTA), which is a modification of the one-pass thinning algorithm (OPTA). The OPTA is applied on raster scanned binary images to produce their skeleton, using a set of 10 predefined templates of 3 × 3 and 3 × 4 elements. The PSTA uses almost the same 10 templates of 4 × 4 elements in order to create the skeleton of the picture elements received by a parallel-symmetric manner, which applies the raster method and its vertical symmetric. Here, both the OPTA and PSTA algorithms are implemented sequentially in software for comparison purpose in accuracy (using ideal skeletons), memory requirements and execution time. <s> BIB011
In parallel thinning, pixels are examined for deletion based on the results of only the previous iteration. For this reason, these algorithms are suitable for implementation on parallel processors where the pixels satisfying a set of conditions can be removed simultaneously. Unfortunately, fully parallel algorithms can have difficulty preserving the connectedness of an image if only 3 x 3 supports are considered; for example, a horizontal rectangle two pixels in width may completely vanish in such a thinning process. Therefore, the usual practice is to use 3 x 3 neighborhoods but to divide each iteration into subiterations or subcycles in which only a subset of contour pixels are considered for removal. At the end of each subiteration, the remaining image is updated for the next subiteration. Four subcycles have been used in which each type of contour point (north, east, south, and west) is removed in each subcycle [115] , [loll, BIB004 . These have also been combined into two subiterations [115] , [136] , BIB007 , [118] , BIB008 with one subiteration deleting the north and east contour points and the other deleting the rest, for example. Other two-subcycle algorithms have been devised to operate on alternate subfields of the pattern that is partitioned in a checkerboard manner. Recently, one-subiteration algorithms have been implemented, but these invariably have to use information from a larger  . Since disjoint 4-components may be 8-connected, the removal of all pixels satisfying the above conditions does not reduce diagonal lines to unit pixel width. Additional conditions were added specifically to address this problem and to allow for deletion of pixels p with X,(p) = 4 when p lies on a diagonal line two pixels wide  , and this was proved to preserve connectedness [34] . Due to the asymmetric nature of conditions R3 and R4, the skeleton would not lie centrally; therefore, 180' rotations of these rules were introduced BIB001 to result in the following complete set of rules for the removal of It was also suggested that two subiterations should be used, where the first one deletes pixels satisfying Dl-D5, and the second deletes according to D1, D2, and D6-D8. Of course, this algorithm deletes isolated pixels. The complexity of the rules D1-D5 led to the observation  that if two consecutive 4-neighbors of p are l's, then the value of the corner pixel q in between has no effect on whether p should be deleted; therefore, q can be considered to be 1. In such cases, p can be deleted if its modified crossing number is 2 provided b(p) > 1. It should be noted that this modification of the crossing number is the corner-cutting process in  ; therefore, the resulting number is actually twice X,(p), and, of course, it measures 8-rather than 4-connectivity. The crossing number X,(p) is also used as a criterion for a filling operation before thinning. In [123] , a white pixel q with X R ( q ) 2 2 is considered to be a connecting point and is filled. Then, a 4-subiteration algorithm is implemented in which end points (having exactly one black 4-neighbor) and pixels p with X,(p) > 2 are considered skeletal, whereas nonskeletal contour pixels are deleted. The much-cited work of Zhang and Suen [136] , which is also summarized in  , is an implementation of a subset of conditions Dl-D8 in two subiterations. In the first subiteration, In the second subiteration, 23 and 2 4 are replaced by their 180' rotations. Therefore, the first subcycle deletes 4-simple pixels on the south and east borders as well as north-west corner pixels, whereas the second subcycle deletes pixels with opposite orientations. This is a simple and efficient algorithm that is also immune to contour noise BIB007 ; however, two-pixelwide diagonal lines can be seriously eroded, and 2 x 2 squares would vanish completely [70] , [71] . It was suggested that condition Z1 should be replaced by 3 5 b(p) 5 6 in order to retain such structures. As can be expected, such a modification creates problems of its own in retaining extraneous pixels; therefore, an additional pass was proposed [128] in order to thin to unit thickness, further increasing the computation time. Although excessive erosion of diagonal lines is not a topological problem, complete disappearance of a 2 x 2 square in the thinning process renders the algorithm invalid from the topological point of view. This was shown  to be the only possible configuration where the algorithm is not valid, and a modification to [136] was suggested so that all conceivable cases could be correctly processed. The modification depends on the number of black 4-neighbors of p when X , ( p ) = 2. If p has none or one such neighbor, no change would be required. If p has two or three such neighbors and p satisfies the existing conditions, then p can be deleted in the first subiteration if x 1 = 0 or 27 = 0 and in the second if 23 = 0 or x5 = 0. In [129] and [130], conditions D1, D2, and D8 from BIB001 are implemented sequentially with minor differences. The more recent algorithm does not delete isolated pixels (X,(p) = 0). It requires 2 5 b(p) 5 6, and it does not preserve 4-connectivity. Therefore, a pixel p at the vertex of a right angle formed by two 4-neighbors would be deleted, thus leading to condition x2 + 2 6 # 0 being unnecessary in rule D8(a) and analogously for D8(b). These authors also implemented a two-subcycle parallel algorithm that deletes (in the first subiteration) east or south boundary points and northwest corner points with X , ( p ) = 2 as well as contour pixels with X R (~) = 4 satisfying condition D8; pixels with opposite orientations are deleted in the second subiteration. Another two-subiteration implementation of conditions Dl-D8 of BIB001 is that of BIB007 ; it contains the same minor differences as [129] and [130] , and it claims to be an improvement over [136] in eliminating excessive erosion. In this work, the rules are implemented by table lookup; each of the 256 configurations of N ( p ) is converted into an address in the thinning tables (one for each subiteration), where the new value of p (0 or 1) is defined. In order to use only one subiteration per cycle, information from a 4 x 4 window containing p is considered  [50] solves this problem by retaining extraneous pixels and creating skeletons of more than unit width. The skeleton is then thinned (incompletely) by a second pass in [128] . Fig.   5 shows a typical example of thinning a problematic pattern using these algorithms. Necessary and sufficient conditions for preserving topology while deleting border points in parallel are given in [loo] . If only 3 x 3 local neighborhoods are considered, then an operation that deletes (for example) north border pixels would preserve topology iff the only north border points it removes are simple and have at least two l's as 8-neighbors. It is proved [124] that this operation would not change the genus Then, p is deleted iff condition H is true, where With this condition, edge information on neighboring pixels is used to prevent the disappearance of vertical lines that are two pixels wide. This algorithm is implemented BIB009 on SIMD and MIMD machines with a modification to reduce redundancy in the edge computation of elements with common neighbors. Condition H is shown [137] to be almost equivalent to , where the crossing number instead of edge information of neighboring pixels is considered. The only differences are that the earlier work stipulates b(p) 2 2, and the conditions of  would add the condition "or b ( 2 3 )  BIB003 " to R3 (and "or b ( z 1 )  BIB003 " to R4). In turn, [137] also proposes (without results) to modify the conditions R1-R4 by changing R1 to 2 5 b(p) 5 6 and the second parts of R3 and R4 to y 3 = 1 and y 1 = 1, respectively, where y 1 is the east neighbor of 5 1 , and y 3 is the north neighbor of x 3 . The first modification is also suggested by BIB010 to preserve diagonal lines in  . Besides all the modifications mentioned above, [ l ] and [ 1141 also suggest procedures to reduce, to unit thickness, the skeletons obtained by [ 1361. Therefore, the algorithm originally proposed by Rutovitz and modified by Deutsch has been implemented with various levels of changes in a number of articles, and the relationships between them are shown in Fig. 4 . Despite the somewhat baffling array of modifications proposed to the algorithm originating from Rutovitz, there are many similarities among the results. Basically, the algorithms of [103] , [136] ,  , [39], and [137] Equivalent conditions for the simplicity of a border point are given in BIB003 , where it is shown that a north border point with at least two 1's as 8-neighbors would be simple iff x 5 % 7 x 1 = 0 and ?f2k-lX2k?f2k+l = 0. These conditions are combined into "O=e in [1021. Another 4-subiteration algorithm is that of [ 171, where skeletal pixels found in each iteration are assigned the iteration number for the subsequent calculation of object width. The values of skeletal pixels from previous iterations are left unchanged, whereas those of interior pixels are incremented by one in each iteration. In the nth iteration, pixel p is tested for deletion as a north border element if 2 3 = 0, p has value n, and x 7 # 0. Such a border element p is considered skeletal if there exists x, E N ( p ) such that z, >. 0 and N ( z ; ) n N ( p ) = { p , z,}; otherwise, p is assigned the value 0 and deleted. This algorithm preserves topology but was found to be sensitive to boundary noise and the order of the subiterations. Parallel algorithms using both four and two subiterations have also been implemented by means of matching against windows analogous to those of Fig. 2 . Stefanelli and Rosenfeld [115] implemented two such algorithms and proved that they preserve topology. In each subcycle, the final (skeletal) pixels are stored. In order to avoid deletion of contour points that are also final points, all the contour points are first deleted, after which the final points are added. When four subcycles are used and north border points are considered for deletion, the final point conditions are those shown in Fig. 6 together with the 90' rotations of (a) and (b). In this and subsequent figures, pixels that are left blank may be 1 or 0 or are "don't care" pixels. The difference between window (b) here and that in Fig.  2(b) implies that the present algorithm would produce imperfectly 8-connected skeletons, as is indeed the case. The two-subcycle algorithm combines deletion of south and east contour points in the first subcycle and the rest in the second. For the second subcycle, the final point conditions are the ones given above in Fig. 6 together with those shown in Fig.  7 . Conditions (b) and (c) are added to ensure connectivity and preserve diagonal lines; however, thin horizontal or vertical lines are not preserved. The processing speed of this algorithm was found to be comparable with that of [103] , but the use of only 3 x 3 windows here allows for easier implementation on a cellular network. Another algorithm using thinning windows is BIB002 , where the masks for pixel deletion are those shown in Fig. 8 together with their 90" rotations. Each mask is applied in parallel to P, and the masks are applied in the order (a), (b), followed by their 90' rotations, and so on. Therefore, this algorithm removes pixels from eight borders in the order nw, w, etc. The asymmetric nature of mask (b) results from the requirement that P should not vanish completely in the parallel process. This algorithm was proved to operate correctly; it was especially suitable for implementation on parallel processors that have the ability to extract "1" and "0" elements having a predetermined number of "1" or "0" elements in chosen neighborhood positions, and it was implemented on a Clip 4 parallel processor [53] . Since not all deletable pixels were removed, other masks were added to produce those of Fig. 9 and their rotations. In addition, it was found [53] that superior results are obtained when removal is restricted to pixels that do not only satisfy the criteria so far but would have satisfied them at the start of the current iteration. This ensures that just one layer of pixels is removed all around P and results in a more predictable algorithm with fewer anomalies at the corners where two layers of pixels may be removed otherwise. The author calls this a border parallel operation, whereas the original is border sequential. Implementation of a border parallel algorithm on the Clip 4 processor does not involve extra computation since the 1's and 0's are detected in separate steps in any case; therefore, it is necessary only to test the 1's in the pattern at the beginning of the iteration, whereas the 0's are tested in the pattern obtained so far. The longer computation time required is the result of deleting fewer pixels in each cycle. In the same paper, it is also shown that the border parallel conditions of Fig. 9 are equivalent to the four-subiteration border parallel deletion of contour pixels with crossing number X H (~) = 1. Fig. 10 shows the results of using this crossing number to thin a pattern by the border parallel and border sequential algorithms. Fig. lO(a) shows the results after one iteration when the contour pixels are deleted according to the sequence north, east, south, and west. Typically, the border-sequential algorithm deletes more pixels at the corners; as a result, the end pixel condition may be encountered sooner with the preservation of these pixels leading to more short (and possibly noisy) branches. For this reason, the right end of the horizontal stroke is retained by this algorithm in the final skeleton shown in Fig. 10(b) , thus illustrating the tradeoff that is sometimes involved when different thinning algorithms are used. By using look-up tables, a simulation of the border parallel conditions of Fig. 9 has been implemented [112] , [113] , in which mask (c) and its rotations are omitted and endpoint conditions added. To prevent excessive erosion of two-pixelthick lines, additional information is used so that the current pixel is retained if its preceding neighbor pixel has been removed. Two recent papers [ 1181, BIB008 have implemented parallel thinning using the crossing number XH (p) to examine pixels for deletion in two subiterations. In [118], the (approximately) 4 x 4 window used is shown in Fig. 11 . Pixels removed in the first subcycle are a) deletable north contour pixels, and b) west contour pixels that are deletable after the pixels in a) have been removed. It is this latter requirement that produces more consistent results while making it necessary to increase the size of the neighborhood and the complexity of the algorithm. In this subcycle, p is deleted iff . . *** . .****. ..*..e*. .e*. .*. .***. .*. .***. .*. .***. .***. ,***. .*e*. .*e*. .**a. .... For the second subcycle, the conditions are S1, S2, and the 180' rotations of S3-S5. In BIB008 , two such algorithms are implemented. For the first one, the image is divided into two distinct subfields in a checkerboard pattern, and each subiteration deletes pixels p in a subfield iff p is a contour pixel, b(p) > 1, and X H (~) = 1. Labeling schemes have also been suggested for use in parallel thinning. In BIB006 , one-subcycle thinning is accomplished by recoding the pattern pixels to incorporate connectivity information from a 5 x 5 window into the coded pixels in N ( p ) . Two initial scans are used to recode the pixels into core, interior, rim, and skeleton points (c, i , r, and s, respectively) . The basic rule is to replace T pixels by b (background) pixels if a horizontal or vertical irb sequence is present, with exceptions made to preserve connectivity and end points. This is similar to the "ideal" method for thinning proposed in  , where p is D perfect if it belongs to a horizontal or vertical configuration ipb, where i is an interior point, and b is a background pixel. (Actually, D-perfect points satisfy one of the two conditions for regular points in [ l l ] and [ 121) . An 'I-perfect point is defined analogously in terms of a diagonal alignment with the added condition that the two pixels 4-adjacent to both p and b must both be white. This paper suggests that parallel deletion of pixels that are simple and perfect (D or I perfect) would produce well-defined pseudo skeletons that are invariant to translation and rotation. Retention of endpoints is obviously achieved because they are never perfect. Since it is impossible to determine whether a neighbor of a border point is an interior point if only 3 x 3 windows are used, additional information is incorporated [ 1251 from outside the window by defining nonend points. If SC is the set of simple contour points, and B = P -SC, then p E P is a nonend point iff T1: p is adjacent to a point in B, T2: every neighbor of p in P is in B or adjacent to a point The operation that removes simple, nonend, contour points in parallel is shown to preserve topology. In order to extend the limitations imposed by 3 x 3 local operations, hybrid schemes have also been proposed to combine distance transforms with thinning. The use of distance transforms provides more global information. It has also been argued that since thinning operations can preserve connectivity while distance transforms possess the reconstruction capability, combining the two operations would be logical if both properties are desired [125] . The suggested procedure is that for each iteration, the set I of interior points of the existing patterns P should be determined, and its expansion E ( I ) is defined as E ( I ) = {qlq E I or has a neighbor in I}. Then, the set of local maxima (in convexity) can be obtained as P -E ( I ) BIB005 , and contour points can be deleted unless they are local maxima, nonsimple, or nonend points (defined above). The remaining contour points are added to the skeletal set, and the process is repeated with I as the existing pattern. It is also argued  that such a hybrid scheme may be most efficient since a distance transform can be used initially to remove the bulk of the exterior pixels in a fixed number of passes, and then, a peeling algorithm can be used to thin the remaining image to unit width. The one-subiteration algorithms of [ 1031,  , BIB006 , and [125] have already been discussed, where all utilize information from a larger than 3 x 3 neighborhood to maintain connectedness. Other algorithms of this group are  and [22] . In  , eight thinning, two restoring, and eight trimming templates are applied in parallel in one pass in which pixels matching the 3 x 3 thinning or trimming, but not those of the 1 x 4 or 4 x 1 restoring templates, are removed. These templates are those of Fig. 12 and 90" rotations of (a) and The thinning templates delete border and corner points and the restoring templates retain 2-pixel-wide lines, whereas the trimming templates reduce noise spurs at the obvious expense of shortening branches. This algorithm is also implemented BIB011 using only 4 x 4 thinning and restoring templates (by filling in with don't care pixels). Only two iterations are used in different directions, after which postprocessing was applied to obtain a medial line that is not usually one-pixel wide. In [22] , a pseudo one-subcycle algorithm is implemented that essentially uses information from a 5 x 5 window. Despite a rather involved formulation employing many new terms that will not be included here, a pixel p is basically a candidate for deletion iff c1: x~( p ) = 1 (equivalent to L c ( p ) = Tb -1(# o)), and C2: (a) the black pixels in N ( p ) are 4-connected ( E ( p ) = (b) p belongs to a two-pixel-wide diagonal line. The conditions for C2(b) had been given in  and modified in BIB007 , and it is the latter scheme that is used here and stated as S 4 ( p ) = 2 and L ( p ) = 1. If p satisfies the conditions for deletion, then its 4-neighbors are checked for possible deletion. If these are not deletable or connectivity would not be changed, then p is removed. The information is stored in look-up tables (as in BIB007 ) for the checking process. In addition, a specially designed thinning condition can be added [23] to the algorithm to better preserve L-shaped patterns by removing more pixels from a concave corner than before. The condition is that p can be deleted if its four corner neighbors contain one white pixel while the other three have all black , comparisons are made among  , [25], and [22] in terms of thinning conditions and a connectivity-preserving function; The method in [22] is considered to be superior because it has more complete thinning conditions and a smaller ratio of cases guarded for (b). LC (P) ), or connectivity preservation (hence, fewer iterations would be required). For parallel algorithms, much of the attention in recent years has been focused on processing speed, and this has led to many comparisons either in terms of computing time or the number of iterations or subiterations used [118] , BIB011 , BIB008 , [24] . However, some comparisons of the number of iterations may not be entirely valid BIB010 . A one-pass algorithm (  , for example) is usually achieved by means of a larger support than 3 x 3, and this creates the need for computation of intermediate results or edge information on neighboring pixels. For this reason, a common framework is needed to define an "iteration" so that parallel algorithms can be meaningfully compared. The proposed scheme BIB010 assumes that in one iteration, each element of a mesh computer can compute any logical function of a 3 x 3 neighborhood, and the parallel speed of an algorithm is measured by the number of such iterations needed. Using this criterion of measurement, the parallel speed of  is not an improvement over that of two-subiteration algorithms such as [136] . In conclusion, it would appear that, as opposed to sequential algorithms, much of the complexity of parallel algorithms results from the need to preserve connectedness while using parallel operations in a small local neighborhood. This is a problem particular to the nature of parallel thinning, and it has been addressed by using subiterations (and serializing the procedure to some extent) or by enlarging the neighborhood to be examined. In either case, intermediate results are actually computed and used in some form in order to preserve more global structures.