A constant-time algorithm for erosions/dilations with application to morphological texture feature computation

A computationally efficient algorithm for computing erosions and dilations by one-dimensional grayscale structuring elements with constant slope is pr oposed. The computational complexity of this algorithm is independent of th e size of the support of the structuring function. This is a generalization of the method proposed by Van Herk for the case of erosion and dilation by flat one-dimensional structuring elements. By appropriate combinations of these structuring elements, it is possible to approximate many useful struc turing elements. This enables efficient computation of granulometries where the number of operations depends linearly on the number of openings. Theor etical and experimental results comparing the complexity of this algorithm with other standard techniques is presented. Two memory efficient algorithm s are then presented. Several implementation issues in computing a granulom etry and moments of the associated morphological pattern spectrum are then addressed. An efficient implementation of granulometries for large images o n machines with limited memory, by dividing the image into smaller rectangu lar patches is then discussed. The optimum size of these patches is a funct ion of the specific hardware and has been obtained experimentally for three different hardware platforms. Finally, parallel implementation of the diff erent algorithms on two multiprocessor machines is discussed. (C) 2000 Acad emic Press.