Ultrasound Group, Siemens Medical Systems, Inc., Issaquah, WA 98027-7002, USA.
IEEE Trans Image Process. 2000;9(5):749-59. doi: 10.1109/83.841511.
Performing morphological operations such as dilation and erosion of binary images, using very long line structuring elements is computationally expensive when performed brute-force following definitions. We present two-pass algorithms that run at constant time for obtaining binary dilations and erosions with all possible length line structuring elements, simultaneously. The algorithms run at constant time for any orientation of the line structuring element. Another contribution of this paper is the use of the concept of orientation error between a continuous line and its discrete counterpart. The orientation error is used in determining the minimum length of the basic digital line structuring element used in obtaining what we call dilation and erosion transforms. The transforms are then thresholded by the length of the desired structuring element to obtain the dilation and erosion results. The algorithms require only one maximum operation for erosion transform and only one minimum operation for dilation transform, and one thresholding step and one translation step per result pixel. We tested the algorithms on Sun Sparc Station 10, on a set of 240x250 salt and pepper noise images with probability of a pixel being a 1-pixel set to 0.25, for orientations of the normals of the structuring elements in the range [pi/2,3pi/2] and lengths, in pixels, in the range [5,145]. We achieved a speed up of about 50 (and for special orientations theta in {(pi/2), (3pi/4), pi, (5pi/4), (3pi/2)} a speed up of about 100) when the structuring elements had lengths of 145 pixels, over the brute-force methods in these experiments. We compared the results of our dilation algorithm with those of the algorithm discussed by Soille et al. (see IEEE Trans. Pattern Anal. Machine Intell., vol.18, p.562-67, 1996) and showed that for binary dilation (and erosion since it is just the dilation of the background with the reflected structuring element) our algorithm performed better and achieved a speed up of about four when dilation or erosion transform alone is obtained.
对二值图像执行形态学操作，如膨胀和腐蚀，如果按照定义进行暴力运算，使用非常长的线结构元素会非常耗费计算资源。我们提出了两种两阶段算法，可以在恒定时间内同时获得具有所有可能长度线结构元素的二进制膨胀和腐蚀。这些算法对于线结构元素的任何方向都以恒定时间运行。本文的另一个贡献是使用连续线与其离散对应物之间的方向误差的概念。方向误差用于确定用于获得我们称之为膨胀和腐蚀变换的基本数字线结构元素的最小长度。然后通过所需结构元素的长度对变换进行阈值处理，以获得膨胀和腐蚀结果。这些算法对于腐蚀变换仅需要一次最大运算，对于膨胀变换仅需要一次最小运算，并且对于每个结果像素仅需要一次阈值处理步骤和一次平移步骤。我们在 Sun Sparc Station 10 上对算法进行了测试，使用了一组 240x250 的椒盐噪声图像，其中像素为 1 的概率设置为 0.25，结构元素法线的方向在 [pi/2,3pi/2] 范围内，长度在 [5,145] 范围内。当结构元素的长度为 145 像素时，我们在这些实验中获得了约 50 倍（对于特殊方向 theta 在 {(pi/2), (3pi/4), pi, (5pi/4), (3pi/2)} 时，速度提高了约 100 倍）的加速，而不是暴力方法。我们将我们的膨胀算法的结果与 Soille 等人讨论的算法（请参阅 IEEE Trans. Pattern Anal. Machine Intell.，第 18 卷，第 562-67 页，1996 年）的结果进行了比较，并表明对于二进制膨胀（以及腐蚀，因为它只是背景的膨胀与反射结构元素），我们的算法表现更好，并且在单独获得膨胀或腐蚀变换时，速度提高了约四倍。
