User:Highlandsgaucho

Boolean Convolution

In digital image processing, boolean convolution refers to the formulation of the basic operations of binary morphology (dilation and erosion) as a form of convolution over boolean images.

Background

Representation

A digital image is represented as a bi-dimensional matrix $\mathbf {A} _{R\times C}=[a_{r,c}]$, where $a_{r,c}\in \{0,1\}\;\forall r\in \{1,\ldots ,R\},\forall c\in \{1,\ldots ,C\}$. Intuitively, $r$ stands for row and $c$ stands for column. Alternatively, the following indexing notation may be used to avoid subscripts: $a_{r,c}=A[r,c]$. This notation will be adopted for the remaining of the article to ease readability.

In particular, a boolean image is a binary image whose values are interpreted in the boolean domain and manipulated with boolean algebra operations, such as NOT (${\overline {\cdot }}$), AND ($\vee$) and OR ($\wedge$).

Convolution

In digital image processing, convolution is a local operation between an image and a smaller array. It is formally stated:

$B=A*K=A\otimes K$

Basically, the operation consists of sliding a window $K$, known as the convolution kernel, across the image $A$. For each position of the window, a pixel in the new image is calculated as the weighted sum of the original pixels lying inside the window. The convolution kernel, thus, provides the weights. More formally:

$B[r,c]=\sum _{i=0}^{M-1}\sum _{j=0}^{N-1}K[i,j]\;A[r-i,c-j]$

where $K$ is of size $M\times N$. The resulting image may be smaller depending on whether the window is slid always completely inside the original image or not. If partial overlapping is allowed, then pixel values must be assigned to the area outside the original image - typically, all 0s or all 1s.

Method

In binary morphology, the basic operations are formulated in terms of a binary image and a structuring element. The latter acts as a convolution kernel with the difference that the origin of pixel coordinates is defined in its centre. Most importantly, the shape of the structuring element determines the effect achieved on the original image. Typically, structuring elements are used to define pixel connectivity. The type of connectivity is denoted $C$-connectivity, where $C$ is the size of the neighborhood of connected pixels. The notation $N_{C}$ is also used to denote a $C$-connected neighborhood.

Examples of common structuring elements.

4-connectivity

8-connectivity

Binary dilation

The dilation of a binary image $A$ by a structuring element $S$ consists of iteratively placing $S$ centered on each background pixel of $A$ and converting it into a foreground pixel if it is connected to any foreground pixel of $A$ according to the connectivity defined by $S$. This results in the expansion of the original image where any overlapping (intersection) exists between the structuring element and the image's foreground.

Formally, the dilation of $A$ by $S$ can be denoted $D(A,S)$. Each pixel of the dilated image can be calculated by a convolution expressed in terms of boolean operators as follows:

$D(A,S)[r,c]=\bigvee _{i=-\infty }^{\infty }\bigvee _{j=-\infty }^{\infty }S[i,j]\wedge A[r-i,c-j]$

where we have considered the infinite extension of the structuring element with background pixels. This enables us to show that the operation is commutative, as permitted by the boolean operators AND and OR.

$D(A,S)[r,c]=D(S,A)[r,c]=\bigvee _{i=-\infty }^{\infty }\bigvee _{j=-\infty }^{\infty }A[i,j]\wedge S[r-i,c-j]$

The following figure shows the dilation of a binary image by a 3 x 3 neighborhood ($N_{8}$). As it can be seen, this results in an expanded foreground object and in its holes being filled in.

Binary dilation example.

Original

Dilated

Binary erosion

The erosion of a binary image $A$ by a structuring element $S$ consists of iteratively placing $S$ centered on each foreground pixel of $A$ and converting it into a background pixel if it is connected to any background pixel of $A$ according to the connectivity defined by $S$. This results in the shrinkage of the original image where any overlapping (intersection) exists between the structuring element and the image's background.

Formally, the erosion of $A$ by $S$ can be denoted $E(A,S)$. By applying De Morgan's laws, it is possible to calculate each pixel of the eroded image by the following reciprocal convolution:

$E(A,S)[r,c]=\bigwedge _{i=-\infty }^{\infty }\bigwedge _{j=-\infty }^{\infty }({\overline {S[i,j]}}\vee A[r-i,c-j])$

The following figure shows the erosion of a noisy binary image by a 3 x 3 neighborhood ($N_{8}$). As it can be seen, the square object shrank and the noise was completely removed.

Binary erosion example.

Original

Eroded

Application

As it was shown in the examples, dilation is a useful tool for stuffing holes in foreground objects, whereas erosion is a useful technique for removing salty background noise. However, the most powerful applications result from the compound operations of opening (dilation after erosion) and closing (erosion after dilation).

Other combinations are also possible. For instance, dilation may be used as a form of edge detector by following its application with the subtraction of the original image. The effect is achieved by the "highlighting" provided by the pixels in the expanded region. A $N_{8}$ structuring element was used in the following example of such technique.

Use of dilation for edge detection.

Original

Edge detection

A similar effect is also possible by means of erosion and later subtraction from the original image. In this case, the boundary pixels are those in the original image that were lost in the erosion. A $N_{8}$ structuring element was used in the following example of such technique.

Use of erosion for edge detection.

Original

Edge detection

Alternatively, erosion may be used for isolating objects for later counting them with a component labelling technique. This is illustrated in the following figure, where rectangular shapes were disconnected from each other by using a 65x65 structuring element.

Use of erosion for object separation.

Original

Eroded

The same effect can be obtained on coin-shaped objects by separating them by eroding the original image with a disk of 25-pixel radius. It is worth noting that the shapes of the objects were maintained by using this other form of structuring element.

Use of erosion for object separation.

Original

Eroded

References

Category:Image processing Category:Artificial intelligence