# Binary Structuring Elements Decomposition Based on an Improved Recursive Dilation-Union Model and RSAPSO Method

Authors: Yudong Zhang; Shuihua Wang; Yi Sun; Genlin Ji; Preetha Phillips; Zhengchao Dong
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper proposed an improved approach to decompose structuring elements of an arbitrary shape. For the model of this method, we use an improved dilation-union model, adding a new termination criterion, as the sum of   3-by-3 matrix should be less than 5. Next for the algorithm of this method, we introduced in the restarted simulated annealing particle swarm optimization method. The experiments demonstrate that our method can find better results than Park's method, Anelli's method, Shih's SGA method, and Zhang's MFSGA method. Besides, our method gave the best decomposition tree of different SE shapes including “ship,” “car,” “heart,” “umbrella,” “vase,” “tree,” “cat,” “V,” “bomb,” and “cup.”


---

## Body

## 1. Introduction

Mathematical morphology (MM) is a theory and technique for the analysis and processing of geometrical structures based on set theory, lattice theory, topology, and random functions. MM not only is commonly applied to digital images, but also can be employed to graphs, surface meshes, solids, and many other spatial structures [1].In these applications, the inherent strategy in MM is to explore the characteristics of an object by probing its microstructure with various forms, known as structuring element (SE). Most image processing architectures adapted to morphological operations use SEs of a limited size. However, implementation becomes difficult when a large-sized SE is employed. Hence, the techniques for decomposing a large-sized SE into combined small-sized SEs are of importance [2].In the last decade, techniques have been proposed for the decomposition of SE, but they are intricate and sometimes suffer from indecomposable cases [3]. Hashimoto and Barrera indicated that traditional algorithms have the disadvantage of being unable to decompose many simply connected decomposable SEs [4]. Shih and Wu developed a method for decomposing arbitrarily shaped binary SEs by standard genetic algorithm (SGA). The algorithm performed an iterative process to create new ones that minimize a predefined fitness function [2]. Zhang and Wu proposed a recursive model and used the migration fitness scaling genetic algorithm (MFSGA) for SE decomposition [5].The abovementioned SGA and MFSGA algorithms are time-consuming, and they can be easily trapped into local optimal points, leading to a wrong solution. Particle swarm optimization (PSO) is an efficient algorithm compared to SGA [6–8]. Zhang and Wu proposed a restarted simulated annealing PSO (RSAPSO) algorithm [9] for further improvement. In their paper, they reported that (
1
) RSAPSO combined the global search ability of PSO and the local search ability of restarted simulated annealing (RSA) algorithm, and (
2
) RSAPSO offset the weakness of both PSO and RSA. They also proved that the RSAPSO is superior to SGA, RSA, and PSO by six benchmark functions. In this paper, we proposed to introduce the recursive model and the RSAPSO algorithm for SE decomposition.The rest of the paper is organized as follows. Section2 described the methodology, including the concept of SE decomposition, the recursive dilation-union model, the encoding strategy, and the objective function. We also introduced the RSAPSO algorithm. Experiments in Section 3 compared the RSAPSO algorithm with Park’s method, Shih’s method, Anelli’s SGA method, and Zhang’s MFSGA method. Finally, Section 4 is devoted to discussions and conclusions.


## 2. Methodology

### 2.1. Concept of SE Decomposition

SupposeA denotes a binary image and S denotes a SE. If we decompose S into S
1
⊕
S
2
⊕
⋯
⊕
S
k, the dilation and erosion will become as follows according to associative law:
(1)
A
⊕
S
=
A
⊕
(
S
1
⊕
S
2
⊕
⋯
⊕
S
k
)
=
(
(
(
A
⊕
S
1
)
⊕
S
2
)
⋯
⊕
S
k
)
,
A
⊝
S
=
A
⊝
(
S
1
⊕
S
2
⊕
⋯
⊕
S
k
)
=
(
(
(
A
⊝
S
1
)
⊝
S
2
)
⋯
⊝
S
k
)
.

The computational cost (CC) for dilation/erosion operators is equal to the number of nonzero element of S. Usually the CC of S is extremely large; however, the sum of CC of S
1
,
S
2
,
… and S
k are relatively small. Therefore, the SE decomposition can dramatically reduce the CC.


#### 2.1.1. Dilation Model

Dilation model is to decompose SE by only dilation operator. SupposeS is decomposed into S
1
⊕
S
2
⊕
⋯
⊕
S
k; the serial computational cost (SCC) of dilation model is equal to the sum of CC of S
1
,
S
2, and S
k.Consider(2)
min
⁡
SCC
=
CC
(
S
1
)
+
CC
(
S
2
)
+
⋯
+
CC
(
S
k
)
s
.
t
.
i
S
=
S
1
⊕
S
2
⊕
⋯
⊕
S
k
.
Figure 1 shows three examples. The first decomposes a square SE of size 3
×
3 into a row vector of size 1
×
3 and a column vector of size 3
×
1. The SCC decreases from 9 to 3
+
3
=
6. The second decomposes a square SE of size 5
×
5 into two row vectors of size 1
×
3 and two column vectors of size 3
×
1, and the SCC decreases from 25 to 3
+
2
+
3
+
2
=
10. The third example decomposes a diamond SE of diameter 7 into three small SEs of size 3
×
3, and the SCC decrease from 25 to 5
+
4
+
4
=
13.Figure 1
Examples of SE decomposition based on dilation model: (a)3
×
3 square; (b) 5
×
5 square; (c) 7
×
7 diamond.


#### 2.1.2. Dilation-Union Model

Dilation-union model is to decompose SE by both dilation and union operators. There are two types of computational cost for dilation-union model: the SCC and the parallel computational cost (PCC).Consider(3)
PCC
=
max
⁡
(
CC
(
S
1
)
+
CC
(
S
2
)
,
CC
(
S
3
)
)
s
.
t
.
S
=
S
1
⊕
S
2
∪
S
3
.
Suppose S can be decomposed into the union of S
1
⊕
S
2 and S
3; then the SCC is equal to the sum of CC of S
1, S
2, and S
3; the PCC is equal to the maximal value of CC
(
S
1
)
+
CC
(
S
2
) and CC
(
S
3
). Figure 2 gives an example; here the subscript (−1, −1) denotes that this square matrix should be translated −1 at both the x-axis and the y-axis. The SCC decreases from 14 to 3
+
4
+
2
=
9. The PCC decreases from 14 to max (
3
+
4,2
)
=
7.Figure 2
An example of SE decomposition based on dilation-union model.


#### 2.1.3. Recursive Dilation-Union Model

LetS
N
N denote a SE of size N
×
N. The first level decomposition is written as
(4)
S
N
N
=
V
(
N
-
2
)
(
N
-
2
)
⊕
F
33
∪
R
N
N
.
Here we use the dilation-union model: V denotes the variable-size matrix, F denotes the fixed-size prime component, and R denotes the residue component. The R can be easily decomposed into union of factors of size 3
×
3 because the size 3
×
3 is the golden standard as the elementary structuring component for decomposition in the literature.Consider(5)
S
N
N
=
V
(
N
-
2
)
(
N
-
2
)
⊕
F
33
PC
∪
[
(
R
33
1
)
(
x
1
,
y
1
)
∪
(
R
33
2
)
(
x
2
,
y
2
)
∪
⋯
∪
(
R
33
n
)
(
x
n
,
y
n
)
]
.
Here n denotes the number of 3-by-3 residual matrix. The subscript (
x
i
,
y
i
) denotes that the R
i should be translated by (
x
i
,
y
i
). Therefore, the iteration continues until the termination criteria are satisfied. In Zhang and Wu’s paper [5], they defined the termination criteria (TC) as that the size of S is smaller than or equal to 3
×
3:(6)
TC
1
:  size
(
S
)
≤
3
.
However, this is not perfect because the 3
×
3 binary SE can be decomposed further as shown in Figure 1(a). So our new criterion is set as
(7)
TC
2
:  size
(
S
)
≤
3
,
sum
(
S
)
≤
5
.
We improved the TC by adding the rule sum
(
S
)
≤
5. The reason is that any 3-by-3 SE with less than five 1s is indecomposable.The flowchart of the recursive dilation-union model is depicted in Figure3, which indicates that we record 4 variables (
V
k
,
F
k
,
R
k
,
and
P
k
) at each iteration level k, and the decomposition tree can be depicted via those variables. The following task is to develop an effective method to perform formulas (4) and (5).Figure 3
Flowchart of recursive dilation-union model.


### 2.2. Optimization Problem

The SE decomposition problem can be transformed into an optimization problem with the help of dilation-union model. In what follows we will briefly discuss the encoding strategy and the objective function of the optimization problem.


#### 2.2.1. Encoding Strategy

Formula (4) or formula (5) can be regarded as an optimization problem. We transform the prime component F
k into a row vector string of chromosomes. For any SE at any iteration, the F
k is a 3-by-3 two-value image; therefore, the chromosome can be written as
(8)
ξ
=
vector
(
F
)
=
f
1
f
2
⋯
f
9
.
Here ξ denotes the chromosome and f
i denotes the locus. Figure 4(a) illustrates the numbering scheme for ξ, namely, from left to right and then from top to bottom. Two examples are shown in Figures 4(b)-4(c), and their 1D strings of chromosomes are “001001101” and “101110101,” respectively.(a) Encoding order: left to right and then top to bottom; (b) an example of “001001101”; (c) an example of “101110101.”
(a)
(b)
(c)


#### 2.2.2. Objective Function

Since the prime componentF is encoded, variable matrix of SEV and residual matrix R can be obtained through the following formula:
(9)
V
=
S
⊝
F
,
R
=
S
-
V
⊕
F
.
Then, we can extract two different types of costs, SCC and PCC, as follows:
(10)
SCC
=
∑
V
+
∑
F
+
∑
R
,
PCC
=
max
⁡
(
∑
V
+
∑
F
,
∑
R
)
.
Note that those variables satisfy the equality as S
=
V
⊕
F
∪
R. In this paper we choose SCC as the objective function, since the PCC needs pipelined architecture, which is difficult to implement in practice.


### 2.3. RSAPSO Algorithm

Now that the encoding strategy and objective function are established, we employed the RSAPSO algorithm [9] to search the optimal points. PSO is a method that optimizes a problem by iteratively improving a candidate solution with regard to a given measure of quality [10]. It is commonly known as metaheuristic method as it makes few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions. However, PSO does not use the gradient of the problem being optimized, which means that PSO does not require the optimization problem to be differentiable as is required by classic optimization methods such as gradient descent and quasi-Newton methods [11]. PSO can therefore also be used in optimization problems that are partially irregular, noisy, adaptive, and so forth [12].Simulated annealing (SA) was chosen as the local search method. SA comes from annealing in metallurgy [13], a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects [14]. The heat causes the atoms to become unstuck from their initial positions (a local minimum of the internal energy) and wander randomly through states of higher energy; the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one [15]. We introduced the restarted simulated annealing (RSA) technique to improve the performance of SA.The proposed algorithm RSAPSO combines both the exploitation ability from RSA and the exploration ability from PSO. It divides the population into two halves: one half runs PSO and the other half runs RSA. In what follows, we will describe those three algorithms in depth.


#### 2.3.1. Particle Swarm Optimization

PSO is a population based stochastic optimization technique, which simulates the social behavior of a swarm of bees, a flock of birds, or a school of fish. By randomly initializing the algorithm with candidate solutions, the PSO successfully leads to a global optimum [16]. This is achieved by an iterative procedure based on the processes of movement and intelligence in an evolutionary system [17]. Figure 5(a) shows the flow chart of a PSO algorithm.Flowchart of the (a) PSO; (b) RSA; and (c) RSAPSO.
(a)
(b)
(c)In PSO, each potential solution is represented as a particle. Two properties (positionx and velocity v) are associated with each particle. Suppose that x and v of the ith particle are given as
(11)
x
=
(
x
i
1
,
x
i
2
,
…
,
x
i
N
)
,
v
=
(
v
i
1
,
v
i
2
,
…
,
v
i
N
)
,
where N stands for the dimensions of the problem. In each iteration, a fitness function is evaluated for all the particles in the swarm [18]. The velocity of each particle is updated by keeping track of the two best positions: one is the best position a particle has traversed so far and is called “p
Best” and the other is the best position that any neighbor of a particle has traversed so far. It is a neighborhood best called “n
Best.” When a particle takes the whole population as its neighborhood, the neighborhood best becomes the global best and is accordingly called “g
Best.” Hence, a particle’s velocity and position are updated as follows:
(12)
v
=
ω
·
v
+
c
1
r
1
(
p
Best
-
x
)
+
c
2
r
2
(
n
Best
-
x
)
,
x
=
x
+
v
Δ
t
,
where ω is called the “inertia weight” that controls the impact of the previous velocity of the particle on its current one. The parameters c
1 and c
2 are positive constants, called “acceleration coefficients.” The parameters r
1 and r
2 are random numbers that are uniformly distributed in the interval [
0
,
1
]. These random numbers are updated every time when they occur. The parameter Δ
t stands for the given time step. The population of particles is then moved according to (12) and tends to cluster together from different directions. However, a maximum velocity v
max
⁡ should not be exceeded by any particle to keep the search within a meaningful solution space [19]. The PSO algorithm runs through these processes iteratively until the termination criterion is satisfied [20–22].


#### 2.3.2. Restarted Simulated Annealing

SA algorithm is a probabilistic hill-climbing technique that is based on the annealing/cooling process of metals [23]. This annealing process occurs after the heat source is removed from a molten metal and its temperature starts to decrease. As the temperature decreases, the energy of the metal molecules reduces, and the metal becomes more rigid. The procedure continues until the metal temperature has reached the surrounding ambient temperature, at which stage the energy has reached its lowest value and the metal is perfectly solid [24].The SA procedure begins by generating an initial solution at random. At initial stages, a small random change is made in the current solutionX
c. The new solution is called X
n. The perturbation depends on a temperate parameter T and a scaling constant k.Consider(13)
pert
(
T
)
=
k
×
T
×
r
3
.
Here r
3 is a random value between 0 and 1 with uniform distribution. The temperature T decreases with each iteration of the algorithm, thus reducing the size of the perturbations as the search progresses. This mechanism produces large perturbation in the initial stages of the search and ensures that the resulting parameters are fine-tuned towards the end of the optimization [25].A move is made to the new solutionX
n if it has smaller energy F or if the probability function has a higher value than a randomly generated number. Otherwise a new solution is generated, evaluated, and compared again. The probability p of accepting a new solution X
n which is called “Metropolis law” is given as follows:
(14)
p
=
{
1
,
if
F
(
X
n
)
<
F
(
X
c
)
,
exp
⁡
(
F
(
X
c
)
-
F
(
X
n
)
T
)
,
otherwise
.
In order to avoid getting trapped at local extrema points, the reduction rate of T should be slow enough. In this study the following method to reduce the temperature has been used:
(15)
T
n
=
T
0
×
β
n
.
Here T
0 is the initial temperature, β is the reduction constant, and n is the number of iterations. In general, most worsening moves may be accepted at initial stages, but at the final stage only improving ones are likely to be allowed. This can help the procedure jump out of a local minimum.However, sometimes it is better to move back to a former solution that was significantly better rather than always moving from the current state. This process is called “restarting” of SA [26]. To do this we set the temperature to a former value and restart the annealing schedule. The decision to restart can be based on several criteria, including whether a fixed number of steps had passed, whether the current energy is too high compared with the best obtained so far, or whether the random number falls within prescribed range (randomly restart). In this paper, we restart the SA when the current energy is too high compared with the best energy because it performs best among all criterions [27]. The flowchart of RSA is shown in Figure 5(b).


#### 2.3.3. Pseudocodes of RSAPSO

Traditional PSO algorithm suffers from getting trapped at the early stage [28]. On the other hand, RSA accepts a worse solution so it can escape from a local minimum, resist premature convergence, and increase the diversity [12]. Therefore, a new hybrid strategy was proposed and referred to as RSAPSO [9]. The proposed RSAPSO algorithm offsets the weaknesses of PSO and RSA. The main idea lies in the fact that it divides the population into two halves: one half runs PSO and the other half runs RSA. During each step, the results are combined and updated by the best result that is picked up from the whole population. The flowchart of RSAPSO is depicted in Figure 5(c), and its pseudocodes are given as follows.Step 1 (initialization).
Generate the population randomly.Step 2 (evaluation).
Evaluate each particle’s objective functionf.Step 3 (segmentation).
Halve the population randomly: one half was updated by PSO according to formula (12) and the other half was updated by RSA according to formulas (13) and (14).Step 4 (update).
Updatep
Best and g
Best; update T according to formula (15).Step 5 (repeat).
Repeat Step2 to Step 4 until the termination criterion is satisfied.Step 6 (output).
Output the final results.


## 2.1. Concept of SE Decomposition

SupposeA denotes a binary image and S denotes a SE. If we decompose S into S
1
⊕
S
2
⊕
⋯
⊕
S
k, the dilation and erosion will become as follows according to associative law:
(1)
A
⊕
S
=
A
⊕
(
S
1
⊕
S
2
⊕
⋯
⊕
S
k
)
=
(
(
(
A
⊕
S
1
)
⊕
S
2
)
⋯
⊕
S
k
)
,
A
⊝
S
=
A
⊝
(
S
1
⊕
S
2
⊕
⋯
⊕
S
k
)
=
(
(
(
A
⊝
S
1
)
⊝
S
2
)
⋯
⊝
S
k
)
.

The computational cost (CC) for dilation/erosion operators is equal to the number of nonzero element of S. Usually the CC of S is extremely large; however, the sum of CC of S
1
,
S
2
,
… and S
k are relatively small. Therefore, the SE decomposition can dramatically reduce the CC.


### 2.1.1. Dilation Model

Dilation model is to decompose SE by only dilation operator. SupposeS is decomposed into S
1
⊕
S
2
⊕
⋯
⊕
S
k; the serial computational cost (SCC) of dilation model is equal to the sum of CC of S
1
,
S
2, and S
k.Consider(2)
min
⁡
SCC
=
CC
(
S
1
)
+
CC
(
S
2
)
+
⋯
+
CC
(
S
k
)
s
.
t
.
i
S
=
S
1
⊕
S
2
⊕
⋯
⊕
S
k
.
Figure 1 shows three examples. The first decomposes a square SE of size 3
×
3 into a row vector of size 1
×
3 and a column vector of size 3
×
1. The SCC decreases from 9 to 3
+
3
=
6. The second decomposes a square SE of size 5
×
5 into two row vectors of size 1
×
3 and two column vectors of size 3
×
1, and the SCC decreases from 25 to 3
+
2
+
3
+
2
=
10. The third example decomposes a diamond SE of diameter 7 into three small SEs of size 3
×
3, and the SCC decrease from 25 to 5
+
4
+
4
=
13.Figure 1
Examples of SE decomposition based on dilation model: (a)3
×
3 square; (b) 5
×
5 square; (c) 7
×
7 diamond.


### 2.1.2. Dilation-Union Model

Dilation-union model is to decompose SE by both dilation and union operators. There are two types of computational cost for dilation-union model: the SCC and the parallel computational cost (PCC).Consider(3)
PCC
=
max
⁡
(
CC
(
S
1
)
+
CC
(
S
2
)
,
CC
(
S
3
)
)
s
.
t
.
S
=
S
1
⊕
S
2
∪
S
3
.
Suppose S can be decomposed into the union of S
1
⊕
S
2 and S
3; then the SCC is equal to the sum of CC of S
1, S
2, and S
3; the PCC is equal to the maximal value of CC
(
S
1
)
+
CC
(
S
2
) and CC
(
S
3
). Figure 2 gives an example; here the subscript (−1, −1) denotes that this square matrix should be translated −1 at both the x-axis and the y-axis. The SCC decreases from 14 to 3
+
4
+
2
=
9. The PCC decreases from 14 to max (
3
+
4,2
)
=
7.Figure 2
An example of SE decomposition based on dilation-union model.


### 2.1.3. Recursive Dilation-Union Model

LetS
N
N denote a SE of size N
×
N. The first level decomposition is written as
(4)
S
N
N
=
V
(
N
-
2
)
(
N
-
2
)
⊕
F
33
∪
R
N
N
.
Here we use the dilation-union model: V denotes the variable-size matrix, F denotes the fixed-size prime component, and R denotes the residue component. The R can be easily decomposed into union of factors of size 3
×
3 because the size 3
×
3 is the golden standard as the elementary structuring component for decomposition in the literature.Consider(5)
S
N
N
=
V
(
N
-
2
)
(
N
-
2
)
⊕
F
33
PC
∪
[
(
R
33
1
)
(
x
1
,
y
1
)
∪
(
R
33
2
)
(
x
2
,
y
2
)
∪
⋯
∪
(
R
33
n
)
(
x
n
,
y
n
)
]
.
Here n denotes the number of 3-by-3 residual matrix. The subscript (
x
i
,
y
i
) denotes that the R
i should be translated by (
x
i
,
y
i
). Therefore, the iteration continues until the termination criteria are satisfied. In Zhang and Wu’s paper [5], they defined the termination criteria (TC) as that the size of S is smaller than or equal to 3
×
3:(6)
TC
1
:  size
(
S
)
≤
3
.
However, this is not perfect because the 3
×
3 binary SE can be decomposed further as shown in Figure 1(a). So our new criterion is set as
(7)
TC
2
:  size
(
S
)
≤
3
,
sum
(
S
)
≤
5
.
We improved the TC by adding the rule sum
(
S
)
≤
5. The reason is that any 3-by-3 SE with less than five 1s is indecomposable.The flowchart of the recursive dilation-union model is depicted in Figure3, which indicates that we record 4 variables (
V
k
,
F
k
,
R
k
,
and
P
k
) at each iteration level k, and the decomposition tree can be depicted via those variables. The following task is to develop an effective method to perform formulas (4) and (5).Figure 3
Flowchart of recursive dilation-union model.


## 2.1.1. Dilation Model

Dilation model is to decompose SE by only dilation operator. SupposeS is decomposed into S
1
⊕
S
2
⊕
⋯
⊕
S
k; the serial computational cost (SCC) of dilation model is equal to the sum of CC of S
1
,
S
2, and S
k.Consider(2)
min
⁡
SCC
=
CC
(
S
1
)
+
CC
(
S
2
)
+
⋯
+
CC
(
S
k
)
s
.
t
.
i
S
=
S
1
⊕
S
2
⊕
⋯
⊕
S
k
.
Figure 1 shows three examples. The first decomposes a square SE of size 3
×
3 into a row vector of size 1
×
3 and a column vector of size 3
×
1. The SCC decreases from 9 to 3
+
3
=
6. The second decomposes a square SE of size 5
×
5 into two row vectors of size 1
×
3 and two column vectors of size 3
×
1, and the SCC decreases from 25 to 3
+
2
+
3
+
2
=
10. The third example decomposes a diamond SE of diameter 7 into three small SEs of size 3
×
3, and the SCC decrease from 25 to 5
+
4
+
4
=
13.Figure 1
Examples of SE decomposition based on dilation model: (a)3
×
3 square; (b) 5
×
5 square; (c) 7
×
7 diamond.


## 2.1.2. Dilation-Union Model

Dilation-union model is to decompose SE by both dilation and union operators. There are two types of computational cost for dilation-union model: the SCC and the parallel computational cost (PCC).Consider(3)
PCC
=
max
⁡
(
CC
(
S
1
)
+
CC
(
S
2
)
,
CC
(
S
3
)
)
s
.
t
.
S
=
S
1
⊕
S
2
∪
S
3
.
Suppose S can be decomposed into the union of S
1
⊕
S
2 and S
3; then the SCC is equal to the sum of CC of S
1, S
2, and S
3; the PCC is equal to the maximal value of CC
(
S
1
)
+
CC
(
S
2
) and CC
(
S
3
). Figure 2 gives an example; here the subscript (−1, −1) denotes that this square matrix should be translated −1 at both the x-axis and the y-axis. The SCC decreases from 14 to 3
+
4
+
2
=
9. The PCC decreases from 14 to max (
3
+
4,2
)
=
7.Figure 2
An example of SE decomposition based on dilation-union model.


## 2.1.3. Recursive Dilation-Union Model

LetS
N
N denote a SE of size N
×
N. The first level decomposition is written as
(4)
S
N
N
=
V
(
N
-
2
)
(
N
-
2
)
⊕
F
33
∪
R
N
N
.
Here we use the dilation-union model: V denotes the variable-size matrix, F denotes the fixed-size prime component, and R denotes the residue component. The R can be easily decomposed into union of factors of size 3
×
3 because the size 3
×
3 is the golden standard as the elementary structuring component for decomposition in the literature.Consider(5)
S
N
N
=
V
(
N
-
2
)
(
N
-
2
)
⊕
F
33
PC
∪
[
(
R
33
1
)
(
x
1
,
y
1
)
∪
(
R
33
2
)
(
x
2
,
y
2
)
∪
⋯
∪
(
R
33
n
)
(
x
n
,
y
n
)
]
.
Here n denotes the number of 3-by-3 residual matrix. The subscript (
x
i
,
y
i
) denotes that the R
i should be translated by (
x
i
,
y
i
). Therefore, the iteration continues until the termination criteria are satisfied. In Zhang and Wu’s paper [5], they defined the termination criteria (TC) as that the size of S is smaller than or equal to 3
×
3:(6)
TC
1
:  size
(
S
)
≤
3
.
However, this is not perfect because the 3
×
3 binary SE can be decomposed further as shown in Figure 1(a). So our new criterion is set as
(7)
TC
2
:  size
(
S
)
≤
3
,
sum
(
S
)
≤
5
.
We improved the TC by adding the rule sum
(
S
)
≤
5. The reason is that any 3-by-3 SE with less than five 1s is indecomposable.The flowchart of the recursive dilation-union model is depicted in Figure3, which indicates that we record 4 variables (
V
k
,
F
k
,
R
k
,
and
P
k
) at each iteration level k, and the decomposition tree can be depicted via those variables. The following task is to develop an effective method to perform formulas (4) and (5).Figure 3
Flowchart of recursive dilation-union model.


## 2.2. Optimization Problem

The SE decomposition problem can be transformed into an optimization problem with the help of dilation-union model. In what follows we will briefly discuss the encoding strategy and the objective function of the optimization problem.


### 2.2.1. Encoding Strategy

Formula (4) or formula (5) can be regarded as an optimization problem. We transform the prime component F
k into a row vector string of chromosomes. For any SE at any iteration, the F
k is a 3-by-3 two-value image; therefore, the chromosome can be written as
(8)
ξ
=
vector
(
F
)
=
f
1
f
2
⋯
f
9
.
Here ξ denotes the chromosome and f
i denotes the locus. Figure 4(a) illustrates the numbering scheme for ξ, namely, from left to right and then from top to bottom. Two examples are shown in Figures 4(b)-4(c), and their 1D strings of chromosomes are “001001101” and “101110101,” respectively.(a) Encoding order: left to right and then top to bottom; (b) an example of “001001101”; (c) an example of “101110101.”
(a)
(b)
(c)


### 2.2.2. Objective Function

Since the prime componentF is encoded, variable matrix of SEV and residual matrix R can be obtained through the following formula:
(9)
V
=
S
⊝
F
,
R
=
S
-
V
⊕
F
.
Then, we can extract two different types of costs, SCC and PCC, as follows:
(10)
SCC
=
∑
V
+
∑
F
+
∑
R
,
PCC
=
max
⁡
(
∑
V
+
∑
F
,
∑
R
)
.
Note that those variables satisfy the equality as S
=
V
⊕
F
∪
R. In this paper we choose SCC as the objective function, since the PCC needs pipelined architecture, which is difficult to implement in practice.


## 2.2.1. Encoding Strategy

Formula (4) or formula (5) can be regarded as an optimization problem. We transform the prime component F
k into a row vector string of chromosomes. For any SE at any iteration, the F
k is a 3-by-3 two-value image; therefore, the chromosome can be written as
(8)
ξ
=
vector
(
F
)
=
f
1
f
2
⋯
f
9
.
Here ξ denotes the chromosome and f
i denotes the locus. Figure 4(a) illustrates the numbering scheme for ξ, namely, from left to right and then from top to bottom. Two examples are shown in Figures 4(b)-4(c), and their 1D strings of chromosomes are “001001101” and “101110101,” respectively.(a) Encoding order: left to right and then top to bottom; (b) an example of “001001101”; (c) an example of “101110101.”
(a)
(b)
(c)


## 2.2.2. Objective Function

Since the prime componentF is encoded, variable matrix of SEV and residual matrix R can be obtained through the following formula:
(9)
V
=
S
⊝
F
,
R
=
S
-
V
⊕
F
.
Then, we can extract two different types of costs, SCC and PCC, as follows:
(10)
SCC
=
∑
V
+
∑
F
+
∑
R
,
PCC
=
max
⁡
(
∑
V
+
∑
F
,
∑
R
)
.
Note that those variables satisfy the equality as S
=
V
⊕
F
∪
R. In this paper we choose SCC as the objective function, since the PCC needs pipelined architecture, which is difficult to implement in practice.


## 2.3. RSAPSO Algorithm

Now that the encoding strategy and objective function are established, we employed the RSAPSO algorithm [9] to search the optimal points. PSO is a method that optimizes a problem by iteratively improving a candidate solution with regard to a given measure of quality [10]. It is commonly known as metaheuristic method as it makes few or no assumptions about the problem being optimized and can search very large spaces of candidate solutions. However, PSO does not use the gradient of the problem being optimized, which means that PSO does not require the optimization problem to be differentiable as is required by classic optimization methods such as gradient descent and quasi-Newton methods [11]. PSO can therefore also be used in optimization problems that are partially irregular, noisy, adaptive, and so forth [12].Simulated annealing (SA) was chosen as the local search method. SA comes from annealing in metallurgy [13], a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects [14]. The heat causes the atoms to become unstuck from their initial positions (a local minimum of the internal energy) and wander randomly through states of higher energy; the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one [15]. We introduced the restarted simulated annealing (RSA) technique to improve the performance of SA.The proposed algorithm RSAPSO combines both the exploitation ability from RSA and the exploration ability from PSO. It divides the population into two halves: one half runs PSO and the other half runs RSA. In what follows, we will describe those three algorithms in depth.


### 2.3.1. Particle Swarm Optimization

PSO is a population based stochastic optimization technique, which simulates the social behavior of a swarm of bees, a flock of birds, or a school of fish. By randomly initializing the algorithm with candidate solutions, the PSO successfully leads to a global optimum [16]. This is achieved by an iterative procedure based on the processes of movement and intelligence in an evolutionary system [17]. Figure 5(a) shows the flow chart of a PSO algorithm.Flowchart of the (a) PSO; (b) RSA; and (c) RSAPSO.
(a)
(b)
(c)In PSO, each potential solution is represented as a particle. Two properties (positionx and velocity v) are associated with each particle. Suppose that x and v of the ith particle are given as
(11)
x
=
(
x
i
1
,
x
i
2
,
…
,
x
i
N
)
,
v
=
(
v
i
1
,
v
i
2
,
…
,
v
i
N
)
,
where N stands for the dimensions of the problem. In each iteration, a fitness function is evaluated for all the particles in the swarm [18]. The velocity of each particle is updated by keeping track of the two best positions: one is the best position a particle has traversed so far and is called “p
Best” and the other is the best position that any neighbor of a particle has traversed so far. It is a neighborhood best called “n
Best.” When a particle takes the whole population as its neighborhood, the neighborhood best becomes the global best and is accordingly called “g
Best.” Hence, a particle’s velocity and position are updated as follows:
(12)
v
=
ω
·
v
+
c
1
r
1
(
p
Best
-
x
)
+
c
2
r
2
(
n
Best
-
x
)
,
x
=
x
+
v
Δ
t
,
where ω is called the “inertia weight” that controls the impact of the previous velocity of the particle on its current one. The parameters c
1 and c
2 are positive constants, called “acceleration coefficients.” The parameters r
1 and r
2 are random numbers that are uniformly distributed in the interval [
0
,
1
]. These random numbers are updated every time when they occur. The parameter Δ
t stands for the given time step. The population of particles is then moved according to (12) and tends to cluster together from different directions. However, a maximum velocity v
max
⁡ should not be exceeded by any particle to keep the search within a meaningful solution space [19]. The PSO algorithm runs through these processes iteratively until the termination criterion is satisfied [20–22].


### 2.3.2. Restarted Simulated Annealing

SA algorithm is a probabilistic hill-climbing technique that is based on the annealing/cooling process of metals [23]. This annealing process occurs after the heat source is removed from a molten metal and its temperature starts to decrease. As the temperature decreases, the energy of the metal molecules reduces, and the metal becomes more rigid. The procedure continues until the metal temperature has reached the surrounding ambient temperature, at which stage the energy has reached its lowest value and the metal is perfectly solid [24].The SA procedure begins by generating an initial solution at random. At initial stages, a small random change is made in the current solutionX
c. The new solution is called X
n. The perturbation depends on a temperate parameter T and a scaling constant k.Consider(13)
pert
(
T
)
=
k
×
T
×
r
3
.
Here r
3 is a random value between 0 and 1 with uniform distribution. The temperature T decreases with each iteration of the algorithm, thus reducing the size of the perturbations as the search progresses. This mechanism produces large perturbation in the initial stages of the search and ensures that the resulting parameters are fine-tuned towards the end of the optimization [25].A move is made to the new solutionX
n if it has smaller energy F or if the probability function has a higher value than a randomly generated number. Otherwise a new solution is generated, evaluated, and compared again. The probability p of accepting a new solution X
n which is called “Metropolis law” is given as follows:
(14)
p
=
{
1
,
if
F
(
X
n
)
<
F
(
X
c
)
,
exp
⁡
(
F
(
X
c
)
-
F
(
X
n
)
T
)
,
otherwise
.
In order to avoid getting trapped at local extrema points, the reduction rate of T should be slow enough. In this study the following method to reduce the temperature has been used:
(15)
T
n
=
T
0
×
β
n
.
Here T
0 is the initial temperature, β is the reduction constant, and n is the number of iterations. In general, most worsening moves may be accepted at initial stages, but at the final stage only improving ones are likely to be allowed. This can help the procedure jump out of a local minimum.However, sometimes it is better to move back to a former solution that was significantly better rather than always moving from the current state. This process is called “restarting” of SA [26]. To do this we set the temperature to a former value and restart the annealing schedule. The decision to restart can be based on several criteria, including whether a fixed number of steps had passed, whether the current energy is too high compared with the best obtained so far, or whether the random number falls within prescribed range (randomly restart). In this paper, we restart the SA when the current energy is too high compared with the best energy because it performs best among all criterions [27]. The flowchart of RSA is shown in Figure 5(b).


### 2.3.3. Pseudocodes of RSAPSO

Traditional PSO algorithm suffers from getting trapped at the early stage [28]. On the other hand, RSA accepts a worse solution so it can escape from a local minimum, resist premature convergence, and increase the diversity [12]. Therefore, a new hybrid strategy was proposed and referred to as RSAPSO [9]. The proposed RSAPSO algorithm offsets the weaknesses of PSO and RSA. The main idea lies in the fact that it divides the population into two halves: one half runs PSO and the other half runs RSA. During each step, the results are combined and updated by the best result that is picked up from the whole population. The flowchart of RSAPSO is depicted in Figure 5(c), and its pseudocodes are given as follows.Step 1 (initialization).
Generate the population randomly.Step 2 (evaluation).
Evaluate each particle’s objective functionf.Step 3 (segmentation).
Halve the population randomly: one half was updated by PSO according to formula (12) and the other half was updated by RSA according to formulas (13) and (14).Step 4 (update).
Updatep
Best and g
Best; update T according to formula (15).Step 5 (repeat).
Repeat Step2 to Step 4 until the termination criterion is satisfied.Step 6 (output).
Output the final results.


## 2.3.1. Particle Swarm Optimization

PSO is a population based stochastic optimization technique, which simulates the social behavior of a swarm of bees, a flock of birds, or a school of fish. By randomly initializing the algorithm with candidate solutions, the PSO successfully leads to a global optimum [16]. This is achieved by an iterative procedure based on the processes of movement and intelligence in an evolutionary system [17]. Figure 5(a) shows the flow chart of a PSO algorithm.Flowchart of the (a) PSO; (b) RSA; and (c) RSAPSO.
(a)
(b)
(c)In PSO, each potential solution is represented as a particle. Two properties (positionx and velocity v) are associated with each particle. Suppose that x and v of the ith particle are given as
(11)
x
=
(
x
i
1
,
x
i
2
,
…
,
x
i
N
)
,
v
=
(
v
i
1
,
v
i
2
,
…
,
v
i
N
)
,
where N stands for the dimensions of the problem. In each iteration, a fitness function is evaluated for all the particles in the swarm [18]. The velocity of each particle is updated by keeping track of the two best positions: one is the best position a particle has traversed so far and is called “p
Best” and the other is the best position that any neighbor of a particle has traversed so far. It is a neighborhood best called “n
Best.” When a particle takes the whole population as its neighborhood, the neighborhood best becomes the global best and is accordingly called “g
Best.” Hence, a particle’s velocity and position are updated as follows:
(12)
v
=
ω
·
v
+
c
1
r
1
(
p
Best
-
x
)
+
c
2
r
2
(
n
Best
-
x
)
,
x
=
x
+
v
Δ
t
,
where ω is called the “inertia weight” that controls the impact of the previous velocity of the particle on its current one. The parameters c
1 and c
2 are positive constants, called “acceleration coefficients.” The parameters r
1 and r
2 are random numbers that are uniformly distributed in the interval [
0
,
1
]. These random numbers are updated every time when they occur. The parameter Δ
t stands for the given time step. The population of particles is then moved according to (12) and tends to cluster together from different directions. However, a maximum velocity v
max
⁡ should not be exceeded by any particle to keep the search within a meaningful solution space [19]. The PSO algorithm runs through these processes iteratively until the termination criterion is satisfied [20–22].


## 2.3.2. Restarted Simulated Annealing

SA algorithm is a probabilistic hill-climbing technique that is based on the annealing/cooling process of metals [23]. This annealing process occurs after the heat source is removed from a molten metal and its temperature starts to decrease. As the temperature decreases, the energy of the metal molecules reduces, and the metal becomes more rigid. The procedure continues until the metal temperature has reached the surrounding ambient temperature, at which stage the energy has reached its lowest value and the metal is perfectly solid [24].The SA procedure begins by generating an initial solution at random. At initial stages, a small random change is made in the current solutionX
c. The new solution is called X
n. The perturbation depends on a temperate parameter T and a scaling constant k.Consider(13)
pert
(
T
)
=
k
×
T
×
r
3
.
Here r
3 is a random value between 0 and 1 with uniform distribution. The temperature T decreases with each iteration of the algorithm, thus reducing the size of the perturbations as the search progresses. This mechanism produces large perturbation in the initial stages of the search and ensures that the resulting parameters are fine-tuned towards the end of the optimization [25].A move is made to the new solutionX
n if it has smaller energy F or if the probability function has a higher value than a randomly generated number. Otherwise a new solution is generated, evaluated, and compared again. The probability p of accepting a new solution X
n which is called “Metropolis law” is given as follows:
(14)
p
=
{
1
,
if
F
(
X
n
)
<
F
(
X
c
)
,
exp
⁡
(
F
(
X
c
)
-
F
(
X
n
)
T
)
,
otherwise
.
In order to avoid getting trapped at local extrema points, the reduction rate of T should be slow enough. In this study the following method to reduce the temperature has been used:
(15)
T
n
=
T
0
×
β
n
.
Here T
0 is the initial temperature, β is the reduction constant, and n is the number of iterations. In general, most worsening moves may be accepted at initial stages, but at the final stage only improving ones are likely to be allowed. This can help the procedure jump out of a local minimum.However, sometimes it is better to move back to a former solution that was significantly better rather than always moving from the current state. This process is called “restarting” of SA [26]. To do this we set the temperature to a former value and restart the annealing schedule. The decision to restart can be based on several criteria, including whether a fixed number of steps had passed, whether the current energy is too high compared with the best obtained so far, or whether the random number falls within prescribed range (randomly restart). In this paper, we restart the SA when the current energy is too high compared with the best energy because it performs best among all criterions [27]. The flowchart of RSA is shown in Figure 5(b).


## 2.3.3. Pseudocodes of RSAPSO

Traditional PSO algorithm suffers from getting trapped at the early stage [28]. On the other hand, RSA accepts a worse solution so it can escape from a local minimum, resist premature convergence, and increase the diversity [12]. Therefore, a new hybrid strategy was proposed and referred to as RSAPSO [9]. The proposed RSAPSO algorithm offsets the weaknesses of PSO and RSA. The main idea lies in the fact that it divides the population into two halves: one half runs PSO and the other half runs RSA. During each step, the results are combined and updated by the best result that is picked up from the whole population. The flowchart of RSAPSO is depicted in Figure 5(c), and its pseudocodes are given as follows.Step 1 (initialization).
Generate the population randomly.Step 2 (evaluation).
Evaluate each particle’s objective functionf.Step 3 (segmentation).
Halve the population randomly: one half was updated by PSO according to formula (12) and the other half was updated by RSA according to formulas (13) and (14).Step 4 (update).
Updatep
Best and g
Best; update T according to formula (15).Step 5 (repeat).
Repeat Step2 to Step 4 until the termination criterion is satisfied.Step 6 (output).
Output the final results.


## 3. Experiments and Discussions

The experiments were carried out on the platform of P4 IBM with 2.2 GHz Intel Core i3-2330 M CPU and 6 GB RAM, running under 64-bit Windows 7 operating system. The algorithm was in-house developed via the global optimization toolbox of MATLAB 2013a. Readers can repeat the results of the experiment on any desktop installing MATLAB.


### 3.1. Parameters Setting

We compared the proposed method RSAPSO with Park’s method, Anelli’s method, Shih’s SGA method, and Zhang’s MFSGA method. Some important parameters are obtained through trial-and-error method and listed in Table1. Here, Ndenotes the number of population, P
C denotes the crossover probability, P
M denotes the mutation probability, M
I denotes the migration interval, and M
R denotes the migration rate.Table 1
Parameters setting.
Algorithm
Parameters
SGA
N = 20, P
C = 0.8, P
M = 0.1
MFSGA
N = 20, P
C = 0.8, P
M = 0.1, M
I = 10, M
R = 2
RSAPSO
N = 20,ω = 0.6, c
1 = 1, c
2 = 1, T
0 = 100, β = 0.95


### 3.2. Comparison with Park’s Method

The SE in Figure6 is indecomposable by Park’s algorithm [4]. Its original SCC is 21. We ran our RSAPSO method 20 times, and all runs obtained the optimal decomposition shown in Figure 6(a) with SCC as 10. Besides, we ran SGA and MFSGA 20 times for comparison. Their results were shown in Table 2. The second row shows the result of all 20 runs. Take SGA as an example; “19
(
10
)
+
1
(
11
)” represents that 19 runs obtained SCC as 10 and the left one run obtained SCC as 11. The third row “Averaged SCC” shows either the averaged SCC result of heuristic methods or the SCC result of deterministic methods. Table 2 shows that SGA obtained optimal result (
10
) 19 times and one suboptimal result (
11
) as shown in Figure 6(b). MFSGA obtained optimal result (
10
) 19 times and one suboptimal result (
11
) as shown in Figure 6(c). The SCC of the two suboptimal SE decomposition results was 11. The averaged SCC of SGA, MFSGA, and RSAPSO were 10.05, 10.05, and 10, respectively.Table 2
Decomposition of Park’s SE (20 runs).
Original
Park’s
SGA
MFSGA
RSAPSO
SCC
19 (1
0) + 1 (11)
19 (10) + 1 (11)
20  (9)
Averaged SCC
21
21
10.05
10.05
10Decomposition tree of Park’s SE (SCC = 21): (a) a successful run (SCC = 10); (b) a failed run by SGA (SCC = 11); and (c) a failed run by MFSGA (SCC = 11).
(a)
(b)
(c)


### 3.3. Comparison with Anelli’s Method

We compared the proposed RSAPSO with Anelli’s method [29], SGA, and MFSGA. We ran SGA, MFSGA, and RSAPSO 20 times, since the distribution of their initial population is random.Figures7(a) and 7(b) show two successful decomposition trees of Anelli’s SE, and both of their SCC are 18. Figures 7(c) and 7(d) show two failed decomposition trees, of which their SCC are 22 and 23, respectively.Decomposition tree of Anelli’s SE (SCC = 41): (a) a successful run (SCC = 18); (b) another successful run (time = 18); (c) a failed run (SCC = 22); and (d) a failed run (SCC = 23).
(a)
(b)
(c)
(d)The comparison results are shown in Table3. The SCC of original SE was 41. Anelli’s method reduced it to 22, and the corresponding decomposition tree can be found in [29]. Among 20 runs, SGA obtained 15 times of optimal results, MFSGA obtained 17 times of optimal results, while the proposed RSAPSO method obtained all 20 successful runs. The averaged SCC of SGA, MFSGA, and RSAPSO were 19.05, 18.6, and 18, respectively.Table 3
Decomposition of Anelli’s SE (20 runs).
Original
Anelli’s
SGA
MFSGA
RSAPSO
SCC
15 (1
8) + 4 (22) + 1 (23)
17 (18) + 3 (22)
20  (13)
Averaged SCC
41
22
19.05
18.6
18


### 3.4. Comparison with SGA

Shih’s paper proclaimed that the optimal SCC results of decomposed trees for “ship” and “car” shapes by SGA were 47 and 46, respectively. After searching by RSAPSO, we obtained better results (see Table5). For the “ship” shape, the original SCC was 125, the optimal SCC found by SGA was 47, and our method found better SCC result as 44 (see 2nd row in Table 4). For the “car” shape, the original SCC was 168, the optimal SCC by SGA was 46, and our method achieved better SCC as 43 (see the 3rd row in Table 4).Table 4
Two-SE decomposition by RSAPSO.
Name
SE
Decomposition by RSAPSO
SCC
Original
SGA
RSAPSO
Ship
125
47*
44
Car
168
46*
43
*Data from Shih and Wu [2].Table 5
Two-SE decomposition by RSAPSO.
Name
SE
Decomposition by RSAPSO
SCC
Original
MFSGA
RSAPSO
Heart
142
32*
30
Umbrella
94
44*
41
*Data from Zhang and Wu [5].


### 3.5. Comparison with MFSGA

In what follows, we compared the proposed RSAPSO with MFSGA method. Zhang et al. proclaimed that the optimal SCC for “heart” and “umbrella” by MFSGA were 32 and 44, respectively. Using RSAPSO, we obtained better results. For SE of “heart,” the original SCC was 142. MFSGA minimized SCC to 32. Our method obtained better SCC result as 30. For SE of “umbrella,” the original SCC was 94. MFSGA minimized SCC to 44. Our method obtained better result as 41.


### 3.6. Other Examples

We used the RSAPSO for six other benchmarks SEs of different shapes, such as vase, tree, cat, V, bomb, and cup. The results were shown in Table6. For the “vase” shape, the SCC of the original and decomposed SE was 149 and 32, respectively. For the “tree” shape, the SCC of the original and decomposed SE was 73 and 26, respectively. For the “cat” shape, the SCC of the original and decomposed SE was 102 and 30, respectively. For letter “V,” the SCC of the original and decomposed SE was 94 and 34, respectively. For the “bomb” shape, the SCC of the original and decomposed SE was 91 and 26, respectively. For the “cup” shape, the SCC of the original and decomposed SE was 113 and 25, respectively.Table 6
Six-SE decomposition examples by our RSAPSO method.
Name
Original
Decomposition
SE
SCC
Tree
SCC
Vase
149
32
Tree
73
26
Cat
102
30
V
94
34
Bomb
91
26
Cup
113
25


## 3.1. Parameters Setting

We compared the proposed method RSAPSO with Park’s method, Anelli’s method, Shih’s SGA method, and Zhang’s MFSGA method. Some important parameters are obtained through trial-and-error method and listed in Table1. Here, Ndenotes the number of population, P
C denotes the crossover probability, P
M denotes the mutation probability, M
I denotes the migration interval, and M
R denotes the migration rate.Table 1
Parameters setting.
Algorithm
Parameters
SGA
N = 20, P
C = 0.8, P
M = 0.1
MFSGA
N = 20, P
C = 0.8, P
M = 0.1, M
I = 10, M
R = 2
RSAPSO
N = 20,ω = 0.6, c
1 = 1, c
2 = 1, T
0 = 100, β = 0.95


## 3.2. Comparison with Park’s Method

The SE in Figure6 is indecomposable by Park’s algorithm [4]. Its original SCC is 21. We ran our RSAPSO method 20 times, and all runs obtained the optimal decomposition shown in Figure 6(a) with SCC as 10. Besides, we ran SGA and MFSGA 20 times for comparison. Their results were shown in Table 2. The second row shows the result of all 20 runs. Take SGA as an example; “19
(
10
)
+
1
(
11
)” represents that 19 runs obtained SCC as 10 and the left one run obtained SCC as 11. The third row “Averaged SCC” shows either the averaged SCC result of heuristic methods or the SCC result of deterministic methods. Table 2 shows that SGA obtained optimal result (
10
) 19 times and one suboptimal result (
11
) as shown in Figure 6(b). MFSGA obtained optimal result (
10
) 19 times and one suboptimal result (
11
) as shown in Figure 6(c). The SCC of the two suboptimal SE decomposition results was 11. The averaged SCC of SGA, MFSGA, and RSAPSO were 10.05, 10.05, and 10, respectively.Table 2
Decomposition of Park’s SE (20 runs).
Original
Park’s
SGA
MFSGA
RSAPSO
SCC
19 (1
0) + 1 (11)
19 (10) + 1 (11)
20  (9)
Averaged SCC
21
21
10.05
10.05
10Decomposition tree of Park’s SE (SCC = 21): (a) a successful run (SCC = 10); (b) a failed run by SGA (SCC = 11); and (c) a failed run by MFSGA (SCC = 11).
(a)
(b)
(c)


## 3.3. Comparison with Anelli’s Method

We compared the proposed RSAPSO with Anelli’s method [29], SGA, and MFSGA. We ran SGA, MFSGA, and RSAPSO 20 times, since the distribution of their initial population is random.Figures7(a) and 7(b) show two successful decomposition trees of Anelli’s SE, and both of their SCC are 18. Figures 7(c) and 7(d) show two failed decomposition trees, of which their SCC are 22 and 23, respectively.Decomposition tree of Anelli’s SE (SCC = 41): (a) a successful run (SCC = 18); (b) another successful run (time = 18); (c) a failed run (SCC = 22); and (d) a failed run (SCC = 23).
(a)
(b)
(c)
(d)The comparison results are shown in Table3. The SCC of original SE was 41. Anelli’s method reduced it to 22, and the corresponding decomposition tree can be found in [29]. Among 20 runs, SGA obtained 15 times of optimal results, MFSGA obtained 17 times of optimal results, while the proposed RSAPSO method obtained all 20 successful runs. The averaged SCC of SGA, MFSGA, and RSAPSO were 19.05, 18.6, and 18, respectively.Table 3
Decomposition of Anelli’s SE (20 runs).
Original
Anelli’s
SGA
MFSGA
RSAPSO
SCC
15 (1
8) + 4 (22) + 1 (23)
17 (18) + 3 (22)
20  (13)
Averaged SCC
41
22
19.05
18.6
18


## 3.4. Comparison with SGA

Shih’s paper proclaimed that the optimal SCC results of decomposed trees for “ship” and “car” shapes by SGA were 47 and 46, respectively. After searching by RSAPSO, we obtained better results (see Table5). For the “ship” shape, the original SCC was 125, the optimal SCC found by SGA was 47, and our method found better SCC result as 44 (see 2nd row in Table 4). For the “car” shape, the original SCC was 168, the optimal SCC by SGA was 46, and our method achieved better SCC as 43 (see the 3rd row in Table 4).Table 4
Two-SE decomposition by RSAPSO.
Name
SE
Decomposition by RSAPSO
SCC
Original
SGA
RSAPSO
Ship
125
47*
44
Car
168
46*
43
*Data from Shih and Wu [2].Table 5
Two-SE decomposition by RSAPSO.
Name
SE
Decomposition by RSAPSO
SCC
Original
MFSGA
RSAPSO
Heart
142
32*
30
Umbrella
94
44*
41
*Data from Zhang and Wu [5].


## 3.5. Comparison with MFSGA

In what follows, we compared the proposed RSAPSO with MFSGA method. Zhang et al. proclaimed that the optimal SCC for “heart” and “umbrella” by MFSGA were 32 and 44, respectively. Using RSAPSO, we obtained better results. For SE of “heart,” the original SCC was 142. MFSGA minimized SCC to 32. Our method obtained better SCC result as 30. For SE of “umbrella,” the original SCC was 94. MFSGA minimized SCC to 44. Our method obtained better result as 41.


## 3.6. Other Examples

We used the RSAPSO for six other benchmarks SEs of different shapes, such as vase, tree, cat, V, bomb, and cup. The results were shown in Table6. For the “vase” shape, the SCC of the original and decomposed SE was 149 and 32, respectively. For the “tree” shape, the SCC of the original and decomposed SE was 73 and 26, respectively. For the “cat” shape, the SCC of the original and decomposed SE was 102 and 30, respectively. For letter “V,” the SCC of the original and decomposed SE was 94 and 34, respectively. For the “bomb” shape, the SCC of the original and decomposed SE was 91 and 26, respectively. For the “cup” shape, the SCC of the original and decomposed SE was 113 and 25, respectively.Table 6
Six-SE decomposition examples by our RSAPSO method.
Name
Original
Decomposition
SE
SCC
Tree
SCC
Vase
149
32
Tree
73
26
Cat
102
30
V
94
34
Bomb
91
26
Cup
113
25


## 4. Conclusions

In this paper, a novel decomposition method for arbitrarily shaped SE was proposed. The SE decomposition problem was first transformed into an optimization problem with virtue of the improved recursive dilation-union model that contains a new termination criterion. Afterwards, the RSAPSO method was introduced as the searching algorithm. In the experiments, we compared our method with Park’s method [4], Anelli’s method [29], Shih’s SGA method [2], and Zhang’s MFSGA method [5]. The results based on several benchmark shapes showed that our method was more robust than the aforementioned algorithms and was able to find the optimal decomposition tree.The contribution of the paper lies in the following 4 aspects:(
1
) we proposed improved termination criteria for the recursive dilation-union model, adding the rule “sum
(
S
)
≤
5”; (
2
) we used the serial computational time as the objective function; (
3
) we introduced the RSAPSO algorithm and proved it is superior to Park’s method, Anelli’s method, SGA, and MFSGA for SE decomposition application; and (
4
) we gave the best decomposition results for the shapes “heart,” “ship,” and “car” among all the state-of-the-art SE decomposition methods.The future tentative research will focus on other optimization algorithms, such as cuckoo search [30], harmony search [31], genetic pattern research [32], Tabu search [33], firefly algorithm [34], honey bee mating [35], and artificial bee colony [36, 37]. We will also try other termination criteria [38] and check the effectiveness of the new SE decomposition methods.



---

*Source: 272496-2014-04-27.xml*