he problem of the convex envelope (convex hull) of a plane shape has been the subject of several studies in recent years. This very important problem concerns several areas such as image processing, pattern recognition or robotics [FU97]. The convex envelope can be used, for example, to normalize a shape, to triangulate a set of points, to extract topological characteristics, to decompose a complex shape in order to facilitate its recognition.

Compared to the very important number of works that have been realized on the use of sequential algorithms to extract the convex hull, the number of parallel algorithms to solve this problem is significantly lower. We have to wait until the beginning of the 80's to see the first parallel algorithms, which calculate the convex hull of a set of points [CHO81], [NAT81], [ALD83].Since then, several authors have presented parallel algorithms to solve this problem with different levels of complexity { {

[KIM87], [LIN93], [PRA89] and on different input data as for example on a set of points in a plane or in a space, on bi-level images, on multi-level images with a single component or several components. On the other hand, the algorithms proposed in these works, were designed for different models of machines such as the model Mesh Connected Computer [MIL85], the model Polymorphic Torus [LI89] or the model Reconfigurable Mesh Computer [HAY98].

The synthesis of these different works leads us to note that the diversity of the parameters put into play complicates any attempt at global comparison between the performances of the different approaches. Table 1 presents a synthesis of some bibliographical references on this problem by specifying each time the machine model used, the nature of the input data as well as the degree of complexity obtained.

Among the parallel algorithms for the determination of the convex hull of the connected components of a multi-level image, mention may be made of [ERR05], which describes an approach based on the structural characterization algorithm. As for the algorithm [BOU02] applies a purely geometric method. Our algorithm calculates with a complexity of ?"¨ (1) the convex hull of an image or set of points with two levels of gray. This algorithm uses a purely geometric approach. It is based solely on the projection of the coordinates of PEs retained in specific quadrants and on the application of the algorithm that determines the Min / Max in ?"¨ (1) time [ELMES91]. This allowed us to reduce the complexity of our solution compared to those proposed in the literature. The contribution of this document is summarized as follows: In this article, section 2 is devoted to the calculation model used for the implementation of the proposed algorithm. Section 3 presents the algorithm for determining the convex hull. Section 4 presents the result of determination of the convex hull of a two-level image matrix. This paper concludes with some remarks on future work.

The computational model of machine used in this paper is a parallel Reconfigurable Mesh Computer (RMC) [ELMES86] of size nxn Elementary Processors (PEs) arranged in a square matrix. It is a machine which respects the SIMD (Single instruction multiple data) model, in which each PE is located in the matrix by its row and column coordinates and can be characterized by its identifier ID = n.i + j, where i and j represent the row number and the column number respectively. In this architecture, Figure . 1 (a) refers to a set of PEs, each one is connected to its four neighbors; if they exist; through communication channels. It has a finite number of registers; of bus length log 2 (n) bits, in which it stores data to perform arithmetic and logic operations. All PEs can perform reconfiguration operations to exchange information with other PEs in the mesh. Figure1. (b) describes the set of possible configurations of each PEThe communication of each PE with its neighbors is implemented through four different operations:

Single Bridge (SB): A PE of the RMC is in the SB state, if it establishes links between two of its communication channels, either in transmitting mode or the receiving one. In addition, it may disconnect some of its communication channels. The algorithm for determining the convex hull consists of 7 steps: (Figure 3).

Step 4: The delimitation of the area P 1 (quadrant: NW), then the determination of the PEs belonging to the convex hull forming part of this zone. The procedure will be applied to zones P 2, P 3 and P 4 .

(Figure 3). 5.

Step 5: Labeling of all PEs belonging to the zones P 1, P 2, P 3 and P 4 (Figure 8). 6.

Step 6: Elimination of all PEs that do not belong to the zones P 1, P 2, P 3 and P 4 . (Figure 8). Step 2:

Step 3: a) All the PEs of the image matrix put themselves in (SB) on their column (Figure 6 -a). The PE H sends a code to all the PEs that are on his line. So, all PEs on this line will receive this code (Figure 7: quadrant P1). This operation runs for all others PEs:PE B ,PE C, PE D ,PE E, PE F and PE G. Step 4: Delimitation of the zones P 1 P 2 P 3 and P 4 : in the area P 1 (quadrant NW), all PEs that are between A and I 1 are in configuration (SB) on their column.

The PE A gives them a code indicating that they have to block the bus that connects them with the PEs that are on their right (Figure 8.a).

In the same way ???? ?? 1 communicates to the PEs that are in its line on the left, the code for disconnect PEs from the top line (Figure 8. a). This operation will be executed in the zones P 2 , P 3 and P 4. Step 5: Labeling of the zones P 1, P 2 , P 3 and P 4 : in zone P 1 , since the PEs I' 1 , A and I 1 are known, we proceed to the labeling all PEs belonging to P 1 . a) All PEs are configured in (SB) with respect to the line. (Figure 5). b) The ???? (?? ?? ,?? ?? ) , ???? (?? ?? ,?? ?? ) , transmit on the bus on their right a code indicating their presence. All unmarked PEs will receive this code, those to the right of the two PEs having (i m , j m ) and (i M , j m ). c) The ???? (?? ?? ,?? ?? ) , ???? (?? ?? ,?? ?? ) transmit on the bus to their left a code indicating their presence. All unmarked PEs will receive this code, those to the left of the two PEs having (i m , j M ) and (i M , j M ) . d) The operations indicated in (a), (b) and (c) will be done on the columns. e) Result: 4 PEs will receive 2 codes one on their line and another one on the columns and will memorize them in I' 1 , I' 2 , I' 3 and I' 4 . (Figure 5). This operation will be executed in the zones P 2 , P 3 and P 4 (Figure 8).

Consequence: All PEs in these areas are identified as part of the zones P 1 , P 2 , P 3 and P 4. Step 6: Elimination of all PEs that do not belong to the zones P 1, P 2, P 3 and P 4 . (Figure 8). ? transmits to all PEs of the image matrix the cancellation order of marking if it is a marked PE. This implies that all PEs that do not belong to zones P 1, P 2 , P 3 and P 4 will no longer be marked. Those who belong to these areas remain marked if they are.

,.,??

1. In the line ?? 1 , ?? 1 3 will be selected (it has the value (?? 3 ? ?? 1 ) which is greater than (?? 3 ? ?? 2 ) ) 2. In the line, ?? 3 7 will be selected (it has the value (?? 7 ? ?? 3 )

which is greater than (?? 7 ? ?? 4 ) > (?? 7 ? ?? 5 ) > (?? 7 ? ?? 6 ). the order to eliminate the ???? ?? (?? 2 ) on its column. 4. L 3 , ?? 3 7 transmits through the open bus to all PEs ?? 3 4 ?? 3 5 and ?? 3 6 the order to eliminate all ???? ?? on their column. In the other lines, no???? ?? will be selected. IV.

This paper has dealt with a parallel algorithm of determining the convex hull of a two-level 2D image with a complexity ?"¨ (1) time. This is executed on a parallel machine (RMC), of size n x n Elementary Processors. The algorithm is essentially based on projections and the calculation of Min / Max in ?"¨ (1) time. In a future work, we will extend this algorithm to 3D space and always in ?"¨ (1) time.

FU A. M. N., and YAN H. Effective classification of planar shapes based on curve