2: Background on Morphological Shape Decomposition

2 Background on Morphological Shape Decomposition
In this section, we introduce some background on shape morphology operation.
Morphological Shape Decomposition (MSD)[14] is used to decompose
the shape by the union of all the certain disks contained in the shape. For a
common binary shape image, it contains two kinds of elements ”0”s and ”1”s,
where ”0” represents backgrounds and ”1” represents the shape information.
The basic idea of morphology in mathematics can be described as below
(M)u = {m+ u|m ∈ M}. (1)
4 C. Luyuan et al.
There are two basic morphological operations, the dilation of M by S and
the erosion of M by S, which are defined as follows:
M ⊕ S =
s∈S
(M)S (2)
and
M S =
s∈S
(M)−S. (3)
There are also two fundamental morphological operation based on dilation
and erosion operations, namely the opening of M by S(M ◦ S) and closing
of M by S(M • S). The definitions are given below:
M ◦ S = (M S) ⊕ S (4)
M • S = (M ⊕ S) S (5)
A binary shape M can be represented as a union of certain disks contained
in M
M =
N

i=0
Li ⊕ iB (6)
where LN = X NB and
Li = (M(
N

j=i+1
)) iB, 0 ≤ i <N. (7)
N is the largest integer which satisfy
M NB = ,
it can be computed by an iterative shape erosion program. B is defined as
morphological disks. We call Li loci and i as corresponding radii. We follow
the work by Pitas and Venetsanopoulos [14] to compute the Li and i. This
can give us an initial shape decomposition.






Fig. 1 An example for morphological shape decomposition.

 Shape Decomposition for Graph Representation 5
An example is shown in Figure1. Here two shapes(the left column) are
given, in which a rectangular shape can be decomposed into five parts. In the
upper-middle column of Figure 1 there are one center part and four corners.
However, different with the normal shape representation which contains two
elements, 0s and 1s, the loci part is represented by the elements of i and the
backgrounds are still 0. It is called ”Blum Ribbon”. With this representation
at hand, we can reconstruct the origin shape[14]. The right column in this
figure shows the reconstructed shapes by using the ”Morphological Ribbon”.