Morphology

Language of set theory

Let $Z$ denote the set of all integers, and $Z^2=Z\times Z$ denote the set of integer pairs $(i,j)\in Z^2$. The coordinates of a pixel $v[i][j]$ in an image can therefore be considered as a component of $Z^2$.

Let $A$ and $B$ be two white regions in a black and white binary image. Then they can be considered as two sets in $Z^2$ space, and their components $a=(a_1,a_2)\in A$ and $b=(b_1,b_2)\in B$ are just a pixel inside each of the regions.

In a binary image, an object of a certain shape can be represented by a set of either 4- or 8-connected white pixels in white background. To carry out certain operations on the shape of the object, the object and its back ground are mathematically represented as sets.

In general, a set is defined as a group of components all having certain properties or satisfying certain conditions:

$$A=\{ a\;\vert\;\mbox{property(a)==TRUE} \}$$

• Object:
  
  $$A=\{a\;\vert\; v[a_1][a_2]==1,\;\mbox{and all $a=(a_1,a_2)$'s are connected}\}$$
  
  

• Background:
  
  $$B=\{b\;\vert\; b \neg \in A \}$$
  
  
  where $\neg \in$ means ``not belong to''.

Basic definitions:

• Translation: The translation of $A$ by $x=(x_1,x_2)$ is
  
  $$A_x=\{c\;\vert\;c=a+x, \;\;\mbox{for all }\;\; a\in A \}$$
  
  
  where $c=(c_1,c_2)=(a_1+x_1,a_2+x_2)=a+x$.
• Reflection: The reflection of $A$ is
  
  $$\hat{A}=\{-a\;\vert\;a \in A \}$$
  
  
  Here the reflection is with respect to a specific origin, such as a point center in the shape, e.g., the center of the shape.
• Complement: The complement of $A$ is
  
  $$A^c=\{c\;\vert\;c \; \neg \in A \}$$
  
  

• Difference: The difference between $A$ and $B$ is
  
  $$A-B=\{a\;\vert\;a\in A, a\in B^c \}=A\cap B^c$$
  
  

Below, a structuring element $B$ is a binary object used in varioius morphology operators. All elements $b \in B$ are measured with respect to the origin $(0,0)$ located at the center of the object. For example, if $B$ is a $5\times 5$ square, then for any $b=(b_1,b_2)\in B$, $-2\le b_1,b_2,\le 2$.

Dilation

$$D(A,B)=A\oplus B=\{ x\;\vert\;(\hat{B}_x \cap A) \ne \Phi \}$$

where $\Phi$ represents empty set. Alternatively,

$$D(A,B)=A\oplus B=\bigcup_{b\in B} A_b=\bigcup_{a\in A} B_a$$

• Find reflection $\hat{B}$ of set $B$ by flipping it about its origin. If $B$ is central symmetric, this step makes no difference;
• Translate (shift, slide) $\hat{B}$ by displacement $x$ over $A$;
• $A\oplus B$ is the set of all displacements $x$'s that keep the intersect (overlap) of $\hat{B}_x$ and $A$ non-empty (keep them ``in touch'').
• Dilation of a binary image shape $A$ by $B$ expands the shape by half of the size of $B$.

As typically the structuring element $B$ is symmetric (either central symmetric or symmetric with respect to its vertical or horizontal axis), the reflection part of the dilation definition will be dropped in the following.

For these simplest structuring elements, dilation can be carried out by setting all background pixels (with value "0") 4- or 8-connected to each object pixel (with value "1") to the value "1".

Erosion

$$E(A,B)=A\ominus B=\{ x\;\vert\;B_x \subseteq A \}$$

Alternatively,

$$E(A,B)=A\ominus B=\bigcap_{b\in B} A_b$$

• Translate (or slide) $B$ by $x$ over $A$;

• $A\ominus B$ is the set of all translations $x$'s that will keep the translated version of $B$ to be entirely contained in $A$.
• Erosion of a binary image shape $A$ by $B$ shrinks the shape by half of the size of $B$.

If the same simple structuring elements are used, erosion can be carried out by setting each object pixel (with value "1") 4- or 8-connected to a background pixel (with value "0") to the value "0".

Properties of dilation and erosion

• Commutative:
  
  $$A\oplus B=B\oplus A$$
  
  

• Non-commutative:
  
  $$A\ominus B\ne B\ominus A$$
  
  

• Associative:
  
  $$A\oplus (B\oplus C)=(A\oplus B)\oplus C$$
  
  

• 
  
  $$A\oplus (B\cup C)=(A\oplus B)\cup(A\oplus C)$$
  
  

• 
  
  $$A\ominus (B\cup C)=(A\ominus B)\cap(A\ominus C)$$
  
  

• 
  
  $$(A\ominus B)\ominus C=A\ominus (B\oplus C)$$
  
  

• The complement of the erosion of $A$ by $B$ is the same as the dilation of complement of $A$ by $B$:
  
  $${(A\ominus B)}^c = A^c \oplus B$$
  
  

• The complement of the dilation of $A$ by $B$ is the same as the erosion of complement of $A$ by $B$.
  
  $${(A\oplus B)}^c = A^c \ominus B$$
  
  

Proof:

$$(A\ominus B)^c=(\{x\;\vert\;B_x \subseteq A \})^c$$

Since set $B_x$ is contained in $A$, i.e., $B_x \subseteq A$, it has no overlap with the complement of $A$, i.e., $B_x \cap A^c=\Phi$, and the above equation can be written as:

$$(A\ominus B)^c=(\{x\;\vert\;(B_x \cap A^c) = \Phi \})^c$$

But the complement of this set of all $x's$ satisfying the condition $B_x \cap A^c=\Phi$ is the set of all $x's$ not satisfying the condition, i.e.,

$$(A\ominus B)^c=(\{x\;\vert\;B_x \cap \bar{A} = \Phi \})^c =\{x\;\vert\;(B_x \cap A^c) \ne \Phi \}=A^c \oplus B$$

Taking complement on both sides above, and replacing $A$ by $A^c$, we get the second relation.

Opening

$$O(A,B)=D(E(A,B),B),\;\;\;\;\;\;\;A \circ B=(A\ominus B)\oplus B$$

The opening of $A$ and $B$ is the dilation of the erosion of $A$ by $B$.

• Dilation and erosion are not a pair of opposite operations in the sense that their effects do not cancel each other.
• The erosion carried out first eliminates small shapes (assumed to be noise) as well as shrinking the object shape, while the following dilation grows the object back (but not the noise).

Closing

$$C(A,B)=E(D(A,B),B),\;\;\;\;\;\;\;A \bullet B=(A\oplus B)\ominus B$$

The closing of $A$ and $B$ is the erosion of the dilation of $A$ by $B$.

• The effect of dilation and erosion do not cancel each other.
• The dilation carried out first eliminates small holes inside the object shape (assumed to be noise) as well as expanding the object shape, while the following erosion shrinks the object back (but not the noise).

Grayscale dilation and erosion

Morphological operations can be generalized to grayscale images. Here neither the image nor the structuring element is binary any more, and the Boolean operations (AND and OR, union and intersect) used for binary images are replaced by addition, subtraction, maximum and minimum operations.

• Dilation:
  
  $$D[m,n]=max_{i,j} ( A[m-i,n-j]+B[i,j] )$$
  
  
  where the maximum value is taken in the neighborhood of pixel $[m,n]$ defined by the structuring element $B$. Dilation tends to grow the white regions of an image. If the structuring element has positive values, the resulting image tends to be brighter.
• Erosion:
  
  $$E[m,n]=min_{i,j} ( A[m-i,n-j]-B[i,j] )$$
  
  
  where the minimum value is taken in the neighborhood of pixel $[m,n]$ defined by the structuring element $B$. Erosion tends to shrink the white regions of an image. If the structuring element has positive values, the resulting image tends to be darker.

Applications:

• Extracting boundaries : The boundary of $A$, denoted by $\beta(A)$, can be obtained as the difference of $A$ and its erosion $A\ominus B$ or dilation $A\oplus B$:
  
  $$\beta(A)=A-(A\ominus B)\;\;\;\;\;\mbox{or}\;\;\;\;\;\beta(A)=A-(A\oplus B)$$
  
  

• Filling holes:

• Thinning:

Example:

Example:

Binary morpohology (top): original image, histogram, binary image (threshold 160), erosion, dilation;

Gray-scale morphology (bottom): original image, erosion, dilation, histogram, binary image (threshold 130).