Fast implementations

Fast implementations of the dilation operator usually rely on a property of this operator. For instance, dilation is an associative operation, i.e.

$$X \oplus ( B \oplus B') = ( X \oplus B ) \oplus B'$$ (3.13)

Some structural elements can be decomposed into simpler elements, as illustrated at figure . Applying the dilations with the smaller elements iteratively instead of the large SE at once reduces the complexity of the dilation. The dilation of an $n \times n$ image by a SE of radius d has a O(d.n²) complexity. In addition, mono-dimension dilation can be performed in O(n²), so that the square SE's complexity is also O(n²). Unfortunately, the square and diamond SE are very poor approximations of a circle. A common improvement is to use a combination of both, which leads to an octagonal SE.

  

Figure 3.11: The square and diamond structuring elements are separable.

Another property that can be used to implement the dilation efficiently is

$$X \oplus B = X \bigcup ( \delta (X) \oplus B)$$ (3.14)

where $\delta (X)$ is the edge of X. This is valid for any connected SE that contains (0,0). If l is the length of the contour of X, then the computational complexity is reduced to o(l.d²) for a SE of radius d, plus a small O(n²) term to determine the pixels belonging to $\delta (X)$.
By combining the properties of equations () and (), we have the basis for contour-processing algorithms for decomposable SE as in Van Vliet and Verweer [173], whose complexity is further reduced to O $(l_{\max}.d)$ where $l_{\max}$ is the maximal size of the contour during the iterations with elementary SE. Finally, Vincent [169] proposes an algorithm using both contours $\delta (X)$ and $\delta (B)$, of the set X and the structural element. This algorithm has a complexity proportional to the product of the number of pixels in each contour, which means O(l.d) for a circular element of size d. It can also be expressed as O(A) where A is the cardinal of $(X \oplus B) \backslash X$ where $\backslash$ is the set difference, i.e. $X \backslash Y = X \bigcap Y^c$.
A third approach applies to structuring elements B that are balls, that are defined as

$$B = \{ b \vert dist_M(b,(0,0)) \leq d \}$$ (3.15)

then, the dilation by B can also be expressed as the threshold of a distance transformation, i.e.

$$X \oplus B = \{ x \vert DT(x) \leq d \}$$ (3.16)

where DT(x) is the distance transformation from object X. The square and diamond SE can be considered as balls for distances defined using the dist₄ and dist₈ metrics respectively. Since the corresponding DT algorithms are of a O(n²) complexity, so are the dilations.
Ragnelmam [126] proposes to combine contour processing and DT thresholding. He uses an algorithm similar to PSN, and stops it as soon as d is reached. The computational complexity is of course O(A) where A is the cardinal of $(X \oplus B) \backslash X$, i.e. the set of points reached by the propagation. Unfortunately, PSN or Ragnelmam's variant of it are approximate EDTs. As mentioned in chapter 2, the non-systematic errors of these algorithms can lead to situations where

$$X \not\subseteq ( X \bullet B )$$ (3.17)

which contradicts the axioms of mathematical morphology.