# Introduction

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.


# II. Computational Model Architecture

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


# 4.

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. 

,.,??  


# Example:

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.


# CONCLUSION

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.


# [FU97]:

FU A. M. N., and YAN H. Effective classification of planar shapes based on curve
1![Figure 1: (a) Concerned model, (b) possible configurations](image-2.png "Figure 1 :")
2![Figure 2: Elementary Processors (PEs) arranged in the form of a set of points representing points of an image matrix.The algorithm for determining the convex hull consists of 7 steps:](image-3.png "Figure 2 :")
3![Figure 3: Step 1, Step 2 and Step 3.](image-4.png "Figure 3 :")
![Step 1: Determination of points: ?? ?? ,?? ?? ,?? ?? , ?? ?? and points A, B, C, D, E, F, G and H (Figure3).2. Step2: Determination of points: ?? 1 ? , ?? 2 ? , ?? 3 ? et ?? 4 ? : (Figure 10). 3. Step 3: Determination of points: ?? 1 , ?? 2 , ?? 3 et ?? 4 :](image-5.png "1.")
74![Figure 4 a: One PE in Crosse Bridge](image-6.png "7 .Figure 4")
45![Figure 4: The (i m , i M , j m , j M ) are all determined in ?(1) time and the corresponding PEs are: ???? (?? ?? ,?? ?? ) , ???? (?? ?? ,?? ?? ) , ???? (?? ?? ,?? ?? ) , ???? (?? ?? ,?? ?? ) b) All the PEs in each line go into Simple Bridge (SB)and make a MIN for the columns j then a Max for the columns j. We will have in each line at most two Marked PEs (???? ?? ). (Figure5-a). For example, for the line i m:](image-7.png "Figure 4 :Figure 5 b:")
5![Figure 5: Summits: ???? (?? ?? ,?? ?? ) , ???? (?? ?? ,?? ?? ) , ???? (?? ?? ,?? ?? ) , ???? (?? ?? ,?? ?? ) et ???? ?? ? ?? ?? {A, B, C, D, E, F, G, H}. belonging to the sides of the quadrilateral encompassing the set of points of the image.](image-8.png "Figure 5 :")
![(a) -SB: NS (b)-SB: WE c) All PEs in the image matrix are configured as (SB) on their line (Figure6-b).](image-9.png "")
7![Figure 7: Determination of points?? 1 , ?? 2 , ?? 3 and ?? 4 .](image-10.png "Figure 7 :")
8![Figure 8 a: Delimitation of P 1 area.](image-11.png "Figure 8 a:")
6![Figure 6: SB Rows and columns configuration (a) -SB: NS; (b)-SB: WE b) The PE A sends a code indicating the position of the column where it is located. So, all the PEs in this column will receive this code (Figure 7: quadrant P1).](image-12.png "Figure 6 :")
![All the PEs in zone P1 are configured in Crosse Bridge (CB) state. The ???? ?? 1 transmits an identifier code of the zone P1(Figure8.b).](image-13.png "F")
8![Figure 8 b: Labeling of area P1](image-14.png "Figure 8 b")
8![Figure 8: Delimitation and labeling of the zones P 1 , P 2 , P 3 and P 4.](image-15.png "Figure 8 :")
![a) All the PEs in the image matrix go into state (CB) except the PE I' 1. b) The ?????? 1](image-16.png "")
7910![Figure 9: Treatment of the area P 1 (Quadrant NW)](image-17.png "Step 7 :Figure 9 :Figure 10 :??")
2![In the line L 2 , the PE ?? 23 will have the Max. 3. In the line L 3 , the PE ?? 37 will have the Max. 4. In the line L 4 the PE ?? 47 will have the Max. 5. In the line L 5 the PE ?? 57 will have the Max. 6. In the line L 6 the PE ?? 6 7 will have the Max. g) All unmarked PEs, having already calculated ???? ?? ?? , execute a Max [ELMES91] of the value ?? = ?? ?? ? ?? ?? on their column ?? ?? .](image-18.png "2 .")
![3. L 1 , ?? 1 3 transmits through the open bus to the PE ?? 1 2](image-19.png "")
11![Figure 11:Max on the line index on the samecolumn Figure 12: Result of the P1 zone The Marked PEs (???? ?? ) Result: The Marked PEs (?PE?_M) : A_2 , A_4 , A_(5 ) and A_(6 ) are eliminated, the ?PE?_M A_1 , A_3 and A_(7)belong to the convex hull of the area](image-20.png "Figure 11 :")
1? The proposed method guarantees constant timeprocessing because all steps are executed in ?"¨ (1)time, while most existing algorithms are based onimage processing multiple times.? The proposed provides the convex hull not only fora set of points but also for images with two graylevels.
			© 2021 Global Journals
			( )Year 2021
			( )Year 2021
		
		
			

				


* 
	
		References Références Referencias segment properties
	
	
		Pattern Recognition Lett
		
			18
			
			1997
		
	




* 
	
		A parallel algorithm for determining convex hulls of sets of points in two dimensions
		
			Chow P
		
	
	
		proc.19 th Allerton Conf. Common., Contr., Comput
				.19 th Allerton Conf. Common., Contr., Comput
		
			1981
			
		
	




* 
	
		Parallel algorithms for the convex hull in two dimensions
		
			NNath S
		
		
			NMaheshwari
		
		
			C PBhatt P
		
	
	
		Proc. Conf. Anal. Problem Classes Programming Parallel Comput
				Conf. Anal. Problem Classes Programming Parallel Comput
		
			1981
			
		
	




* 
	
		Parallel algorithms for convex hulls
		
			MAld
		
	
	
		Dep. Comput. Sci., Queens Univ
		
			1983
		
	




* 
	
		Parallel algorithms for digital geometry
		
			EKim C
		
		
			December 1987
			Pullman
		
		
			Washington State University
		
	
	CS-87-179




* 
	
		Efficient Parallel processing of image contours
		
			LingT
		
	
	
		IEEE Trans. Pattern Anal. Mach. Intelligence
		
			15
			1
			
			1993
		
	




* 
	
		Image computation on meshes with multiple broadcast
		
			ReisisK D IPrasanna V
		
	
	
		IEEE Trans. Pattern Anal. Mach. Intelligence
		
			11
			11
			
			1989
		
	




* 
	
		Geometric algorithms for digitized pictures on a mesh connected computer
		
			Miller R
		
	
	
		IEEE Trans. Pattern Anal. Mach. Intelligence
		
			7
			2
			1985
		
	




* 
	
		Polymorphic Torus Architecture for Computer Vision
		
			LiHMaresca M
		
	
	
		IEEE Trans. on PAMI
		
			11
			
			March89
		
	




* 
	
		An (O (log log n) 2 ) time algorithm to compute the convex hull of sorted point on a reconfigurable meshes
		
			Hayachi T
		
	
	
		IEEE trans. Parallel Distrib. Sys
		
			9
			12
			
			1998
		
	




* 
	
		? (1) time algorithm for structural characterization of multi-level images and its applications on a reconfigurable mesh computer
		
			Errami A
		
		
			MKhaldoun
		
		
			JElmesbahi
		
		
			BouattaneM
		
	
	
		Journal of Intelligent and Robotics Systems
		
			2005
		
	




* 
	
		A fast parallel algorithm for convex hull problem of multi-leveled images
		
			Bouattane O
		
		
			JElmesbahi
		
		
			Errami A
		
	
	
		Journal of Intelligent and Robotic Systems
		
			33
			
			2002
		
	




* 
	
		Structure Analysis for Gray level Pictures on a mesh connected computer
		
			JElmesbahi
		
		
			JCherkaoui
		
	
	
		Proc. of IEEE Internat. Conf. on SMC
				of IEEE Internat. Conf. on SMC
		
			1986
			10
			
		
	




* 
	
		(1) algorithm for image component labeling in a mesh connected computer
	
	
		IEEE Trans. Syst. Man Cybern
		J. El Mesbahi, ?
		
			21
			
			1991
		
	




* 
	
		
		10.1109/21.87089