DECOMPOSITION OF CONVEX POLYGONAL MORPHOLOGICAL STRUCTURING ELEMENTS INTO NEIGHBORHOOD SUBSETS

Mathematical morphology provides an effective tool for image analysis. Many parallel image computers support basic morphological operations. To efficiently implement morphological operations on a parallel computer, a structuring element often needs to be decomposed into smaller structuring element that can be easily handled by the particular machine. In this paper, we discuss the decomposition of convex polygon-shaped structuring elements into neighborhood subsets. Such decompositions will lead to efficient implementation of corresponding morphological operations on neighborhood-processing-based parallel image computers. It is proved in this paper that all convex polygons are decomposable. Efficient decomposition algorithms are developed for different machine structures. An O(1) time algorithm, with respect to the image size, is developed for the four-neighbor-connected mesh machines; a linear time algorithm for determining the optimal decomposition is provided for the machines that can quickly perform 3 x 3 morphological operations.