# Fast Threshold Selection Algorithm of Infrared Human Images Based on Two-Dimensional Fuzzy Tsallis Entropy

Authors: Dong-xue Xia; Chun-gui Li; Shu-hong Yang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Infrared images are fuzzy and noisy by nature; thus the segmentation of human targets in infrared images is a challenging task. In this paper, a fast thresholding method of infrared human images based on two-dimensional fuzzy Tsallis entropy is introduced. First, to address the fuzziness of infrared image, the fuzzy Tsallis entropy of objects and that of background are defined, respectively, according to probability partition principle. Next, this newly defined entropy is extended to two dimensions to make good use of spatial information to deal with the noise in infrared images, and correspondingly a fast computation method of two-dimensional fuzzy Tsallis entropy is put forward to reduce its computation complexity fromO
(
L
2
) to O
(
L
). Finally, the optimal parameters of fuzzy membership function are searched by shuffled frog-leaping algorithm following maximum entropy principle, and then the best threshold of an infrared human image is computed from the optimal parameters. Compared with typical entropy-based thresholding methods by experiments, the method presented in this paper is proved to be more efficient and robust.


---

## Body

## 1. Introduction

Image segmentation is an important topic in the field of digital image process. It intends to extract objects from background based on some pertinent characteristics in an image such as gray level, color, texture, and location [1]. Thresholding is one of the most popular segmentation approaches because of its simplicity [2, 3]. It serves a variety of applications such as biomedical image analysis, character identification, and change detection [3]. Compared with visible images, the intensity of human targets in infrared images is obviously different from that of background. Therefore, segmenting infrared human images by threshold selection is feasible [4]. Moreover, the intensity of human targets in infrared image is mainly determined by its temperature and radiated heat and is independent of the current light conditions, so the detection system can be applied indiscriminately in both day and night [4]. However, infrared images are not perfect either. Due to the limitations in camera technology, most infrared images have lower spatial resolution and less sensitivity than visible images, which often leads to poor image quality, such as blurring, low target-to-background contrast, and great noise. Therefore, it is a complex challenge to make precise segmentation of human targets in infrared images by threshold selection [5].


## 2. Related Work

Excellent reviews on early thresholding methods can be found in [6]. Among all the thresholding methods, entropy-based method is widely studied and is considered effectively [3]. Recently, Tsallis entropy was applied to the field of image thresholding for its excellent performance in the description of nonadditive information existing in images [7]. Later, this work in one-dimensional histogram was extended to two-dimensional one with much better effects [8]. Fuzzy sets play a significant role in many systems because of their capability to model nonstatistical imprecision. The notion of entropy, in the theory of fuzzy sets, was first introduced by De Luca and Termini [9]. There are numerous applications of fuzzy entropies in image segmentation. Cheng et al. proposed fuzzy homogeneity vectors to perform multilevel thresholding [10]. Tao et al. presented an approach to segmenting objects in infrared images based on ant colony optimization algorithm and fuzzy entropy [11]. Cheng et al. presented a thresholding approach by performing fuzzy partition of a two-dimensional histogram based on fuzzy relation [12]. Zhao et al. presented an entropy function based on fuzzy c-partition (FP) and probability partition (PP) [13] to perform image thresholding.Considering the fuzzy nature of infrared image and the excellent performance of Tsallis entropy in the description of nonadditive information, in this paper, we present a fast infrared human image thresholding method based on two-dimensional fuzzy Tsallis entropy. We first transform Tsallis entropy into fuzzy domain and then extend it to two-dimensional histogram, and thus 2-D FTE (two-dimensional fuzzy Tsallis entropy) is defined and applied to the field of threshold selection. To handle the exponential increase in computation time brought about by extending one-dimensional method to two-dimensional one, we provide a fast algorithm to reduce the computation complexity of 2-D FTE fromO
(
L
2
) to O
(
L
) for an image with L gray levels. And then SHLA (shuffled frog-leaping algorithm) [14] is employed to speed up the search of optimal threshold. The comparison between the proposed method and other typical entropy-based methods demonstrates that the former is more effective and robust.


## 3. The Fuzzy Entropy of Images

### 3.1. The Fuzzy Set of Images

LetR
=
{
1,2
,
…
,
M
}, C
=
{
1,2
…
,
N
}, and G
=
{
1,2
,
…
,
L
-
1
}; then for an image I
=
f
(
r
,
c
) of size M
×
N with L gray levels, its domain can be expressed as D
=
{
(
r
,
c
)
∣
r
∈
R
,
c
∈
C
}. Let D
k
=
{
(
r
,
c
)
∣
f
(
r
,
c
)
=
k
,
(
r
,
c
)
∈
D
,
k
∈
G
} and denote T as a threshold by which an image is segmented into object (
O
) and background (
B
). Then Π
2
=
{
O
,
B
} is an unknown probability partition of D, and its probability distribution is described as p
O
=
P
(
O
), p
B
=
P
(
B
), respectively. For each k
∈
G, let
(1)
D
k
O
=
{
(
r
,
c
)
:
f
(
r
,
c
)
>
T
,
(
r
,
c
)
∈
D
k
}
,
D
k
B
=
{
(
r
,
c
)
:
f
(
r
,
c
)
≤
T
,
(
r
,
c
)
∈
D
k
}
,
then the following equations hold [11]:
(2)
p
k
O
=
P
(
D
k
O
)
=
p
k
*
p
O
∣
k
p
k
B
=
P
(
D
k
B
)
=
p
k
*
p
B
∣
k
,
where p
O
∣
k and p
B
∣
k denote the conditional probability of a pixel that is classified into the classes O and B, respectively, obviously p
O
∣
k
+
p
B
∣
k
=
1.To threshold an image in fuzzy domain, we first transform the image into fuzzy domain by fuzzy membership function. Suppose the fuzzy memberships of a pixel with grey levelk belonging to classes O and B are μ
O
(
k
) and μ
B
(
k
), respectively; then μ
O
(
k
)
+
μ
B
(
k
)
=
1. We can decide the class of the pixel by the value of μ
O
(
k
) and μ
B
(
k
). According to [11], let
(3)
μ
O
(
k
)
=
p
O
∣
k
,
μ
B
(
k
)
=
p
B
∣
k
,
and by substituting (3) into (2), we get
(4)
p
O
=
P
(
O
)
=
∑
k
=
0
L
-
1
p
k
O
=
∑
k
=
0
L
-
1
p
k
*
μ
O
(
k
)
,
p
B
=
P
(
B
)
=
∑
k
=
0
L
-
1
p
k
B
=
∑
k
=
0
L
-
1
p
k
*
μ
B
(
k
)
.We selectS-function and Z-function as the fuzzy membership functions because they are smoother than other fuzzy membership functions, such as Triangle function and Π-function. The standard S-function and Z-function used in this paper are shown in the following:
(5)
μ
O
(
k
)
=
S
(
k
,
a
,
c
)
=
{
0
k
≤
a
(
k
-
a
)
2
(
c
-
a
)
2
/
2
,
a
≤
k
≤
a
+
c
2
1
-
(
c
-
k
)
2
(
c
-
a
)
2
/
2
,
a
+
c
2
≤
k
≤
c
1
c
≤
k
,
μ
B
(
k
)
=
Z
(
k
,
a
,
c
)
=
1
-
S
(
k
,
a
,
c
)
.


### 3.2. The Fuzzy Tsallis Entropy of Images

In the domainD of an image, let h
(
k
)
=
|
D
k
|
/
(
N
*
M
), in which |
·
| denotes the cardinality of a set. Then the histogram of an image can be expressed as H
=
{
h
(
k
)
∣
k
∈
G
}, and H is transformed into fuzzy domain; that is, F
=
{
μ
(
k
)
h
(
k
)
∣
k
∈
G
}. Consequently, the fuzzy distribution of object O and background B can be obtained as
(6)
F
O
:
μ
O
(
0
)
h
(
0
)
p
O
,
…
,
μ
O
(
L
-
1
)
h
(
L
-
1
)
p
O
F
B
:
μ
B
(
0
)
h
(
0
)
p
B
,
…
,
μ
B
(
L
-
1
)
h
(
L
-
1
)
p
B
,
where p
O, and p
B are defined in (4).According to the definition of Tsallis entropy, we define the fuzzy Tsallis entropy of objectO and background O, respectively, as follows:
(7)
FT
O
q
(
t
)
=
1
q
-
1
(
1
-
∑
l
=
0
L
-
1
(
μ
O
(
l
)
h
(
l
)
p
O
)
q
)
FT
B
q
(
t
)
=
1
q
-
1
(
1
-
∑
l
=
0
L
-
1
(
μ
B
(
l
)
h
(
l
)
p
B
)
q
)
,
where q
∈
R
+ and q
≠
1.It can be proved that the limiting case of the fuzzy Tsallis entropy defined in this paper is equal to the fuzzy Shannon entropy defined by Tao et al. [11]. Take limit
q
→
1
FT
O
q
(
t
), for example, when q
→
1; then
(8)
lim
⁡
q
→
1
FT
o
q
=
lim
⁡
q
→
1
1
q
-
1
(
1
-
∑
l
=
0
L
-
1
(
μ
O
(
l
)
h
(
l
)
p
O
)
q
)
=
lim
⁡
q
→
1
1
(
q
-
1
)
′
{
1
-
∑
l
=
0
L
-
1
(
μ
O
(
l
)
h
(
l
)
p
O
)
q
}
′
=
-
∑
l
=
0
L
-
1
μ
O
(
l
)
h
(
l
)
p
O
*
ln
⁡
{
μ
O
(
l
)
h
(
l
)
p
O
}
=
H
d
.Similarly, we can prove thatlim
⁡
q
→
1
FT
B
q
=
H
b, where H
d and H
b are the fuzzy Shannon entropy of object and background defined by Tao. Therefore, we can say that the fuzzy entropy defined by Tao is a special case of the fuzzy Tsallis entropy defined in this paper.


## 3.1. The Fuzzy Set of Images

LetR
=
{
1,2
,
…
,
M
}, C
=
{
1,2
…
,
N
}, and G
=
{
1,2
,
…
,
L
-
1
}; then for an image I
=
f
(
r
,
c
) of size M
×
N with L gray levels, its domain can be expressed as D
=
{
(
r
,
c
)
∣
r
∈
R
,
c
∈
C
}. Let D
k
=
{
(
r
,
c
)
∣
f
(
r
,
c
)
=
k
,
(
r
,
c
)
∈
D
,
k
∈
G
} and denote T as a threshold by which an image is segmented into object (
O
) and background (
B
). Then Π
2
=
{
O
,
B
} is an unknown probability partition of D, and its probability distribution is described as p
O
=
P
(
O
), p
B
=
P
(
B
), respectively. For each k
∈
G, let
(1)
D
k
O
=
{
(
r
,
c
)
:
f
(
r
,
c
)
>
T
,
(
r
,
c
)
∈
D
k
}
,
D
k
B
=
{
(
r
,
c
)
:
f
(
r
,
c
)
≤
T
,
(
r
,
c
)
∈
D
k
}
,
then the following equations hold [11]:
(2)
p
k
O
=
P
(
D
k
O
)
=
p
k
*
p
O
∣
k
p
k
B
=
P
(
D
k
B
)
=
p
k
*
p
B
∣
k
,
where p
O
∣
k and p
B
∣
k denote the conditional probability of a pixel that is classified into the classes O and B, respectively, obviously p
O
∣
k
+
p
B
∣
k
=
1.To threshold an image in fuzzy domain, we first transform the image into fuzzy domain by fuzzy membership function. Suppose the fuzzy memberships of a pixel with grey levelk belonging to classes O and B are μ
O
(
k
) and μ
B
(
k
), respectively; then μ
O
(
k
)
+
μ
B
(
k
)
=
1. We can decide the class of the pixel by the value of μ
O
(
k
) and μ
B
(
k
). According to [11], let
(3)
μ
O
(
k
)
=
p
O
∣
k
,
μ
B
(
k
)
=
p
B
∣
k
,
and by substituting (3) into (2), we get
(4)
p
O
=
P
(
O
)
=
∑
k
=
0
L
-
1
p
k
O
=
∑
k
=
0
L
-
1
p
k
*
μ
O
(
k
)
,
p
B
=
P
(
B
)
=
∑
k
=
0
L
-
1
p
k
B
=
∑
k
=
0
L
-
1
p
k
*
μ
B
(
k
)
.We selectS-function and Z-function as the fuzzy membership functions because they are smoother than other fuzzy membership functions, such as Triangle function and Π-function. The standard S-function and Z-function used in this paper are shown in the following:
(5)
μ
O
(
k
)
=
S
(
k
,
a
,
c
)
=
{
0
k
≤
a
(
k
-
a
)
2
(
c
-
a
)
2
/
2
,
a
≤
k
≤
a
+
c
2
1
-
(
c
-
k
)
2
(
c
-
a
)
2
/
2
,
a
+
c
2
≤
k
≤
c
1
c
≤
k
,
μ
B
(
k
)
=
Z
(
k
,
a
,
c
)
=
1
-
S
(
k
,
a
,
c
)
.


## 3.2. The Fuzzy Tsallis Entropy of Images

In the domainD of an image, let h
(
k
)
=
|
D
k
|
/
(
N
*
M
), in which |
·
| denotes the cardinality of a set. Then the histogram of an image can be expressed as H
=
{
h
(
k
)
∣
k
∈
G
}, and H is transformed into fuzzy domain; that is, F
=
{
μ
(
k
)
h
(
k
)
∣
k
∈
G
}. Consequently, the fuzzy distribution of object O and background B can be obtained as
(6)
F
O
:
μ
O
(
0
)
h
(
0
)
p
O
,
…
,
μ
O
(
L
-
1
)
h
(
L
-
1
)
p
O
F
B
:
μ
B
(
0
)
h
(
0
)
p
B
,
…
,
μ
B
(
L
-
1
)
h
(
L
-
1
)
p
B
,
where p
O, and p
B are defined in (4).According to the definition of Tsallis entropy, we define the fuzzy Tsallis entropy of objectO and background O, respectively, as follows:
(7)
FT
O
q
(
t
)
=
1
q
-
1
(
1
-
∑
l
=
0
L
-
1
(
μ
O
(
l
)
h
(
l
)
p
O
)
q
)
FT
B
q
(
t
)
=
1
q
-
1
(
1
-
∑
l
=
0
L
-
1
(
μ
B
(
l
)
h
(
l
)
p
B
)
q
)
,
where q
∈
R
+ and q
≠
1.It can be proved that the limiting case of the fuzzy Tsallis entropy defined in this paper is equal to the fuzzy Shannon entropy defined by Tao et al. [11]. Take limit
q
→
1
FT
O
q
(
t
), for example, when q
→
1; then
(8)
lim
⁡
q
→
1
FT
o
q
=
lim
⁡
q
→
1
1
q
-
1
(
1
-
∑
l
=
0
L
-
1
(
μ
O
(
l
)
h
(
l
)
p
O
)
q
)
=
lim
⁡
q
→
1
1
(
q
-
1
)
′
{
1
-
∑
l
=
0
L
-
1
(
μ
O
(
l
)
h
(
l
)
p
O
)
q
}
′
=
-
∑
l
=
0
L
-
1
μ
O
(
l
)
h
(
l
)
p
O
*
ln
⁡
{
μ
O
(
l
)
h
(
l
)
p
O
}
=
H
d
.Similarly, we can prove thatlim
⁡
q
→
1
FT
B
q
=
H
b, where H
d and H
b are the fuzzy Shannon entropy of object and background defined by Tao. Therefore, we can say that the fuzzy entropy defined by Tao is a special case of the fuzzy Tsallis entropy defined in this paper.


## 4. Fast Threshold Selection Based on 2D FTE

### 4.1. The Definition of 2-D FTE (Two-Dimensional Fuzzy Tsallis Entropy)

To define the 2D FTE (fuzzy Tsallis entropy) for an image of sizeM
×
N with L gray levels, we first calculate the 2-D histogram of the image by
(9)
p
i
j
=
n
i
j
(
M
×
N
)
,
where n
i
j denotes the number of pixels whose gray level equals i and local average gray level equals j [8]. The 2-D histogram can be viewed as a full Cartesian product of two sets X and Y, where X represents the gray levels and Y represents the local average gray levels; that is, X
=
Y
=
{
0,1
,
2
,
…
,
L
-
1
}. Each axis of the 2-D histogram can be transformed into fuzzy domain using S-function and Z-function, and then four fuzzy sets are defined as follows [12]:
(10)
O
X
=
∑
x
∈
X
u
O
X
x
=
∑
x
∈
X
S
(
x
,
a
,
c
)
x
,
O
Y
=
∑
y
∈
Y
u
O
Y
y
=
∑
y
∈
Y
S
(
y
,
a
,
c
)
y
,
B
X
=
∑
x
∈
X
u
B
X
(
x
)
x
=
∑
x
∈
X
Z
(
x
,
a
,
c
)
x
,
B
Y
=
∑
y
∈
Y
u
B
Y
(
y
)
y
=
∑
y
∈
Y
Z
(
y
,
a
,
c
)
y
.The fuzzy relationO (object) and B (background) are subsets of the full Cartesian product space X
×
Y, respectively; that is, O
=
O
X
×
O
Y
⊂
X
×
Y, B
=
B
X
×
B
Y
⊂
X
×
Y. The 2-D fuzzy membership functions μ
O
(
x
,
y
) and μ
B
(
x
,
y
) can be obtained as follows [12]:
(11)
μ
O
(
x
,
y
)
=
μ
O
X
×
O
Y
(
x
,
y
)
=
min
⁡
(
μ
O
X
,
μ
O
Y
)
,
μ
B
(
x
,
y
)
=
μ
B
X
×
B
Y
(
x
,
y
)
=
min
⁡
(
μ
B
X
,
μ
B
Y
)
.Then mapping the 2-D histogram into fuzzy domain employingμ
O
(
x
,
y
), μ
B
(
x
,
y
) obtained above, we get two fuzzy distributions of classes O and B as follows:
(12)
FP
O
:
μ
O
(
0,0
)
h
(
0,0
)
p
O
,
…
,
μ
O
(
L
-
1
,
L
-
1
)
h
(
L
-
1
,
L
-
1
)
p
O
,
FP
B
:
μ
B
(
0,0
)
h
(
0,0
)
p
B
,
…
,
μ
B
(
L
-
1
,
L
-
1
)
h
(
L
-
1
,
L
-
1
)
p
B
.
By the similar way used in the deducing of (4), p
O and p
B can be computed by
(13)
p
O
=
∑
x
=
0
L
-
1
∑
y
=
0
L
-
1
μ
O
(
x
,
y
)
h
(
x
,
y
)
,
p
B
=
∑
x
=
0
L
-
1
∑
y
=
0
L
-
1
μ
B
(
x
,
y
)
h
(
x
,
y
)
.According to the definition of two-dimensional Tsallis entropy [8], we extend the fuzzy Tsallis entropy defined in (7) to two-dimensional ones and define the 2-D FTE of classes O and B as follows:
(14)
FH
O
q
=
1
-
∑
x
=
0
L
-
1
∑
y
=
0
L
-
1
(
μ
O
(
x
,
y
)
h
(
x
,
y
)
/
p
O
)
q
q
-
1
,
FH
B
q
=
1
-
∑
x
=
0
L
-
1
∑
y
=
0
L
-
1
(
μ
B
(
x
,
y
)
h
(
x
,
y
)
/
p
B
)
q
q
-
1
.According to the nonadditivity rule of Tsallis entropy, the total two-dimensional fuzzy Tsallis entropy of an image can be obtained by(15)
FH
q
=
FH
O
q
+
FH
B
q
+
(
1
-
q
)
·
FH
O
q
·
FH
B
q
.We follow maximum entropy principle [8] to search for the optimal threshold by
(16)
t
opt
=
arg
max
⁡
(
a
,
c
)
[
FH
q
]
.


### 4.2. Fast Computation of Two-Dimensional Fuzzy Tsallis Entropy

The proposed segmentation method involves the optimization of (16), and thus the 2-D FTE needs to be computed once for each pair of parameters (
a
,
c
) according to (14)~(15). For an image with L gray levels, the time complexity of this computation is O
(
L
2
), which is too much even for a heuristic search algorithm like SHLA. Therefore, we present a fast algorithm to speed up the calculation. We take the derivation of the fast computation of FH
O
q as an example here; the derivation of FH
B
q is similar. We divide the 2-D histogram of image into two parts by the diagonal line from (
0,0
) to (
L
-
1
,
L
-
1
) as illustrated in Figure 1.Figure 1
The division and accumulation of 2D histogram.For convenience,S
(
x
,
a
,
c
) is denoted as S
(
x
) hereafter. As S-function is a monotonically nondecreasing function, from (11), we get
(17)
μ
O
(
x
,
y
)
=
μ
O
X
×
O
Y
(
x
,
y
)
=
min
⁡
(
μ
O
X
,
μ
O
Y
)
=
min
⁡
(
S
(
x
)
,
S
(
y
)
)
=
S
(
min
⁡
(
x
,
y
)
)
.
In Figure 1, R
1
=
{
(
x
,
y
)
,
x
⩽
y
} and R
2
=
{
(
x
,
y
)
,
x
>
y
}; then, we get
(18)
μ
O
(
x
,
y
)
=
S
(
min
⁡
(
x
,
y
)
)
=
S
(
x
)
,
(
x
,
y
)
∈
R
1
,
μ
O
(
x
,
y
)
=
S
(
min
⁡
(
x
,
y
)
)
=
S
(
y
)
,
(
x
,
y
)
∈
R
2
.When the two-dimensional histogram is obtained, we first compute the four accumulation arrays, which just need to be done once for each input image:(19)
U
[
x
]
=
∑
y
=
x
L
-
1
h
(
x
,
y
)
,
x
∈
{
0,1
,
…
,
L
-
1
}
,
R
[
y
]
=
∑
x
=
y
+
1
L
-
1
h
(
x
,
y
)
,
y
∈
{
0,1
,
…
,
L
-
1
}
,
(20)
U
p
[
x
]
=
∑
y
=
x
L
-
1
[
h
(
x
,
y
)
]
q
,
x
∈
{
0,1
,
…
,
L
-
1
}
,
R
p
[
y
]
=
∑
x
=
y
+
1
L
-
1
[
h
(
x
,
y
)
]
q
,
y
∈
{
0,1
,
…
,
L
-
1
}
,
where U
[
x
] means accumulating all the elements in R
1 to the upper side of the 2-D histogram along vertical lines like C
D in Figure 1. In the similar manner, R
[
y
] means accumulating all the elements in R
2 to the right side along horizontal lines like A
B.ForU
p
[
x
] and R
p
[
y
], we first compute [
h
(
x
,
y
)
]
q for each element of the 2-D histogram and then accumulate them to the upper and right side in the same way as U
[
x
] and R
[
y
].For each pair of fuzzy parameters(
a
,
c
), we first calculate S
(
l
) and [
S
(
l
)
]
q for each l
∈
{
0,1
,
…
,
L
-
1
}. Then from (14) and (18), we get
(21)
p
O
=
∑
(
x
,
y
)
∈
R
1
μ
O
(
x
,
y
)
h
(
x
,
y
)
+
∑
(
x
,
y
)
∈
R
2
μ
O
(
x
,
y
)
h
(
x
,
y
)
=
∑
x
=
0
L
-
1
{
S
(
x
)
∑
y
=
x
L
-
1
h
(
x
,
y
)
}
+
∑
y
=
0
L
-
1
{
S
(
y
)
∑
x
=
y
+
1
L
-
1
h
(
x
,
y
)
}
.
Substituting (19) into (21), we get
(22)
p
O
=
∑
x
=
0
L
-
1
S
(
x
)
U
(
x
)
+
∑
y
=
0
L
-
1
{
S
(
y
)
R
(
y
)
}
=
∑
l
=
0
L
-
1
S
(
l
)
(
U
[
l
]
+
R
[
l
]
)
.
In a similar manner, we get
(23)
∑
x
=
0
L
-
1
∑
y
=
0
L
-
1
(
μ
O
(
x
,
y
)
h
(
x
,
y
)
)
q
=
∑
l
=
0
L
-
1
[
S
(
l
)
]
q
(
U
p
[
l
]
+
R
p
[
l
]
)
.
Substituting (22) and (23) into (7), we get
(24)
FH
O
q
=
1
1
-
q
{
1
-
∑
l
=
0
L
-
1
[
S
(
l
)
]
q
(
U
p
[
l
]
+
R
p
[
l
]
)
{
∑
l
=
0
L
-
1
S
(
l
)
(
U
[
l
]
+
R
[
l
]
)
}
q
}
.Therefore, the computation ofFH
O
q for each pair of fuzzy parameters (
a
,
c
) is sped up from O
(
L
2
) to O
(
L
).


### 4.3. Thresholding Based on 2-D FTE and SHLA

To obtain the optimal threshold it is required to find the optimal combination of the fuzzy parameters. Therefore, the segmentation problem can be formulated as an optimization problem. SHLA [14] is an excellent global optimization algorithm proposed recently. It combines the benefits of the genetic-based memetic algorithm and the social behavior-based particle swarm optimization algorithms. In SFLA, the population consists of a set of frogs (solutions) that is partitioned into subsets referred to as memeplexes. The different memeplexes are considered as different cultures of frogs, each performing a local search. Within each memeplex, the individual frogs hold ideas that can be influenced by the ideas of other frogs and evolve through a process of memetic evolution. After a defined number of memetic evolution steps, ideas are passed among memeplexes in a shuffling process. The local search and the shuffling processes continue until defined convergence criteria are satisfied. Due to its rather fast convergence speed compared with other algorithm [15], SHLA is used to select the optimal fuzzy parameters in this paper. The major steps consist of the following.Step 1.
Calculate the 2-D histogram of the input image by (9) and produce four accumulating arrays by (19) and (20).Step 2.
Search the optimal fuzzy parameters(
a
,
c
) by SHLA, in which the fitness function is calculated according to (15).Step 3.
Set the threshold to be the crossover point of the membership function which has membership 0.5 implying the largest fuzziness [12], and segment the input image.


## 4.1. The Definition of 2-D FTE (Two-Dimensional Fuzzy Tsallis Entropy)

To define the 2D FTE (fuzzy Tsallis entropy) for an image of sizeM
×
N with L gray levels, we first calculate the 2-D histogram of the image by
(9)
p
i
j
=
n
i
j
(
M
×
N
)
,
where n
i
j denotes the number of pixels whose gray level equals i and local average gray level equals j [8]. The 2-D histogram can be viewed as a full Cartesian product of two sets X and Y, where X represents the gray levels and Y represents the local average gray levels; that is, X
=
Y
=
{
0,1
,
2
,
…
,
L
-
1
}. Each axis of the 2-D histogram can be transformed into fuzzy domain using S-function and Z-function, and then four fuzzy sets are defined as follows [12]:
(10)
O
X
=
∑
x
∈
X
u
O
X
x
=
∑
x
∈
X
S
(
x
,
a
,
c
)
x
,
O
Y
=
∑
y
∈
Y
u
O
Y
y
=
∑
y
∈
Y
S
(
y
,
a
,
c
)
y
,
B
X
=
∑
x
∈
X
u
B
X
(
x
)
x
=
∑
x
∈
X
Z
(
x
,
a
,
c
)
x
,
B
Y
=
∑
y
∈
Y
u
B
Y
(
y
)
y
=
∑
y
∈
Y
Z
(
y
,
a
,
c
)
y
.The fuzzy relationO (object) and B (background) are subsets of the full Cartesian product space X
×
Y, respectively; that is, O
=
O
X
×
O
Y
⊂
X
×
Y, B
=
B
X
×
B
Y
⊂
X
×
Y. The 2-D fuzzy membership functions μ
O
(
x
,
y
) and μ
B
(
x
,
y
) can be obtained as follows [12]:
(11)
μ
O
(
x
,
y
)
=
μ
O
X
×
O
Y
(
x
,
y
)
=
min
⁡
(
μ
O
X
,
μ
O
Y
)
,
μ
B
(
x
,
y
)
=
μ
B
X
×
B
Y
(
x
,
y
)
=
min
⁡
(
μ
B
X
,
μ
B
Y
)
.Then mapping the 2-D histogram into fuzzy domain employingμ
O
(
x
,
y
), μ
B
(
x
,
y
) obtained above, we get two fuzzy distributions of classes O and B as follows:
(12)
FP
O
:
μ
O
(
0,0
)
h
(
0,0
)
p
O
,
…
,
μ
O
(
L
-
1
,
L
-
1
)
h
(
L
-
1
,
L
-
1
)
p
O
,
FP
B
:
μ
B
(
0,0
)
h
(
0,0
)
p
B
,
…
,
μ
B
(
L
-
1
,
L
-
1
)
h
(
L
-
1
,
L
-
1
)
p
B
.
By the similar way used in the deducing of (4), p
O and p
B can be computed by
(13)
p
O
=
∑
x
=
0
L
-
1
∑
y
=
0
L
-
1
μ
O
(
x
,
y
)
h
(
x
,
y
)
,
p
B
=
∑
x
=
0
L
-
1
∑
y
=
0
L
-
1
μ
B
(
x
,
y
)
h
(
x
,
y
)
.According to the definition of two-dimensional Tsallis entropy [8], we extend the fuzzy Tsallis entropy defined in (7) to two-dimensional ones and define the 2-D FTE of classes O and B as follows:
(14)
FH
O
q
=
1
-
∑
x
=
0
L
-
1
∑
y
=
0
L
-
1
(
μ
O
(
x
,
y
)
h
(
x
,
y
)
/
p
O
)
q
q
-
1
,
FH
B
q
=
1
-
∑
x
=
0
L
-
1
∑
y
=
0
L
-
1
(
μ
B
(
x
,
y
)
h
(
x
,
y
)
/
p
B
)
q
q
-
1
.According to the nonadditivity rule of Tsallis entropy, the total two-dimensional fuzzy Tsallis entropy of an image can be obtained by(15)
FH
q
=
FH
O
q
+
FH
B
q
+
(
1
-
q
)
·
FH
O
q
·
FH
B
q
.We follow maximum entropy principle [8] to search for the optimal threshold by
(16)
t
opt
=
arg
max
⁡
(
a
,
c
)
[
FH
q
]
.


## 4.2. Fast Computation of Two-Dimensional Fuzzy Tsallis Entropy

The proposed segmentation method involves the optimization of (16), and thus the 2-D FTE needs to be computed once for each pair of parameters (
a
,
c
) according to (14)~(15). For an image with L gray levels, the time complexity of this computation is O
(
L
2
), which is too much even for a heuristic search algorithm like SHLA. Therefore, we present a fast algorithm to speed up the calculation. We take the derivation of the fast computation of FH
O
q as an example here; the derivation of FH
B
q is similar. We divide the 2-D histogram of image into two parts by the diagonal line from (
0,0
) to (
L
-
1
,
L
-
1
) as illustrated in Figure 1.Figure 1
The division and accumulation of 2D histogram.For convenience,S
(
x
,
a
,
c
) is denoted as S
(
x
) hereafter. As S-function is a monotonically nondecreasing function, from (11), we get
(17)
μ
O
(
x
,
y
)
=
μ
O
X
×
O
Y
(
x
,
y
)
=
min
⁡
(
μ
O
X
,
μ
O
Y
)
=
min
⁡
(
S
(
x
)
,
S
(
y
)
)
=
S
(
min
⁡
(
x
,
y
)
)
.
In Figure 1, R
1
=
{
(
x
,
y
)
,
x
⩽
y
} and R
2
=
{
(
x
,
y
)
,
x
>
y
}; then, we get
(18)
μ
O
(
x
,
y
)
=
S
(
min
⁡
(
x
,
y
)
)
=
S
(
x
)
,
(
x
,
y
)
∈
R
1
,
μ
O
(
x
,
y
)
=
S
(
min
⁡
(
x
,
y
)
)
=
S
(
y
)
,
(
x
,
y
)
∈
R
2
.When the two-dimensional histogram is obtained, we first compute the four accumulation arrays, which just need to be done once for each input image:(19)
U
[
x
]
=
∑
y
=
x
L
-
1
h
(
x
,
y
)
,
x
∈
{
0,1
,
…
,
L
-
1
}
,
R
[
y
]
=
∑
x
=
y
+
1
L
-
1
h
(
x
,
y
)
,
y
∈
{
0,1
,
…
,
L
-
1
}
,
(20)
U
p
[
x
]
=
∑
y
=
x
L
-
1
[
h
(
x
,
y
)
]
q
,
x
∈
{
0,1
,
…
,
L
-
1
}
,
R
p
[
y
]
=
∑
x
=
y
+
1
L
-
1
[
h
(
x
,
y
)
]
q
,
y
∈
{
0,1
,
…
,
L
-
1
}
,
where U
[
x
] means accumulating all the elements in R
1 to the upper side of the 2-D histogram along vertical lines like C
D in Figure 1. In the similar manner, R
[
y
] means accumulating all the elements in R
2 to the right side along horizontal lines like A
B.ForU
p
[
x
] and R
p
[
y
], we first compute [
h
(
x
,
y
)
]
q for each element of the 2-D histogram and then accumulate them to the upper and right side in the same way as U
[
x
] and R
[
y
].For each pair of fuzzy parameters(
a
,
c
), we first calculate S
(
l
) and [
S
(
l
)
]
q for each l
∈
{
0,1
,
…
,
L
-
1
}. Then from (14) and (18), we get
(21)
p
O
=
∑
(
x
,
y
)
∈
R
1
μ
O
(
x
,
y
)
h
(
x
,
y
)
+
∑
(
x
,
y
)
∈
R
2
μ
O
(
x
,
y
)
h
(
x
,
y
)
=
∑
x
=
0
L
-
1
{
S
(
x
)
∑
y
=
x
L
-
1
h
(
x
,
y
)
}
+
∑
y
=
0
L
-
1
{
S
(
y
)
∑
x
=
y
+
1
L
-
1
h
(
x
,
y
)
}
.
Substituting (19) into (21), we get
(22)
p
O
=
∑
x
=
0
L
-
1
S
(
x
)
U
(
x
)
+
∑
y
=
0
L
-
1
{
S
(
y
)
R
(
y
)
}
=
∑
l
=
0
L
-
1
S
(
l
)
(
U
[
l
]
+
R
[
l
]
)
.
In a similar manner, we get
(23)
∑
x
=
0
L
-
1
∑
y
=
0
L
-
1
(
μ
O
(
x
,
y
)
h
(
x
,
y
)
)
q
=
∑
l
=
0
L
-
1
[
S
(
l
)
]
q
(
U
p
[
l
]
+
R
p
[
l
]
)
.
Substituting (22) and (23) into (7), we get
(24)
FH
O
q
=
1
1
-
q
{
1
-
∑
l
=
0
L
-
1
[
S
(
l
)
]
q
(
U
p
[
l
]
+
R
p
[
l
]
)
{
∑
l
=
0
L
-
1
S
(
l
)
(
U
[
l
]
+
R
[
l
]
)
}
q
}
.Therefore, the computation ofFH
O
q for each pair of fuzzy parameters (
a
,
c
) is sped up from O
(
L
2
) to O
(
L
).


## 4.3. Thresholding Based on 2-D FTE and SHLA

To obtain the optimal threshold it is required to find the optimal combination of the fuzzy parameters. Therefore, the segmentation problem can be formulated as an optimization problem. SHLA [14] is an excellent global optimization algorithm proposed recently. It combines the benefits of the genetic-based memetic algorithm and the social behavior-based particle swarm optimization algorithms. In SFLA, the population consists of a set of frogs (solutions) that is partitioned into subsets referred to as memeplexes. The different memeplexes are considered as different cultures of frogs, each performing a local search. Within each memeplex, the individual frogs hold ideas that can be influenced by the ideas of other frogs and evolve through a process of memetic evolution. After a defined number of memetic evolution steps, ideas are passed among memeplexes in a shuffling process. The local search and the shuffling processes continue until defined convergence criteria are satisfied. Due to its rather fast convergence speed compared with other algorithm [15], SHLA is used to select the optimal fuzzy parameters in this paper. The major steps consist of the following.Step 1.
Calculate the 2-D histogram of the input image by (9) and produce four accumulating arrays by (19) and (20).Step 2.
Search the optimal fuzzy parameters(
a
,
c
) by SHLA, in which the fitness function is calculated according to (15).Step 3.
Set the threshold to be the crossover point of the membership function which has membership 0.5 implying the largest fuzziness [12], and segment the input image.


## 5. Experiments and Discussions

In order to verify the validity of the presented method, it is tested on a variety of synthetic and real images. To make purposeful yet effective comparisons, the selected thresholding methods for comparison are all entropy-based thresholding methods. They are Tao’s 1D fuzzy Shannon entropy method [11], Sahoo’s 2-D nonfuzzy Tsallis entropy method [8], and Cheng’s 2-D fuzzy Shannon entropy method [12]. Additionally, the parameter q in (15) is set to be 0.7 as Sahoo did in [8], and the parameters of SHLA are set to be the values recommended in [14].In order to evaluate the performance of the competing methods objectively, we conduct quantitative analysis on the results. There is no universally accepted objective criterion to evaluate the performance of segmentation methods. In this paper, our primary interest is the integrality and accuracy of object segmentation. Therefore, as Tao et al. did in [11], we also use the absolute error ratio as the comparison criterion. The absolute error ratio is defined as the ratio between the absolute error n
diff and the total number of pixels, N, of an image; that is,
(25)
r
err
⁡
=
n
diff
N
×
100
%
,
where the absolute error n
diff is defined as the absolute difference in the number of object pixels between the ground truth image and the thresholding image obtained by each method [11].


### 5.1. Experiments on Synthetic Image

The image in Figure2(a) is a simple synthetic image with 240
×
240 pixels and shows an English character “H” (with gray level 80) on grey background (with gray level 160). Ideal segmentation is shown in Figure 2(b). Figure 2(c) is the image into which Gaussian noises with zero mean and 0.005 variance are added, and the histogram of Figure 2(c) is shown in Figure 2(d).Synthetic images: (a) original image, (b) ground truth image, (c) noisy image, and (d) histogram of the noisy image.
(a)
(b)
(c)
(d)The results obtained by the competing methods corresponding to Figure2(c) are shown in Figure 3. It can be found that, as a 1-D method, Tao’s method obtains the worst result; however the proposed method obtains the best one. Table 1 shows the thresholds and absolute errors obtained by competing methods. From Table 1, we can find that the absolute error ratio of the proposed method is lower than those of other methods.Table 1
Thresholds andr
err
⁡ of different methods in Figure 2(c).
Method
Tao
Sahoo
Cheng
Proposed
Threshold
77
121
120
116
r
err
⁡
14.34%
1.26%
0.99%
0.55%Thresholding results of noisy image obtained by different methods: (a) Tao’s result, (b) Sahoo’s result, (c) Cheng’s result, and (d) our result.
(a)
(b)
(c)
(d)


### 5.2. Experiments on Real Images

In order to further verify the validity of the presented method, we tested it on a variety of real images including those selected from IEEE OT CBSV WS Series Bench [16] and those captured by ourselves using a Guide IR928 thermal camera. According to the method used in [11, 17], the average of the segmentation results got by five people familiar with thermal imagery is used as ground truth images here. The original images are shown in Figure 4, where (a)~(d) are selected from the public dataset and (e), (f) are captured by ourselves. Those images are captured in different seasons under different weather conditions and light strengths. It can be observed that the human targets in (a)~(c) are smaller while those in (d)~(f) are bigger. The corresponding ground truth images are shown in Figure 5. The results of the four competing methods are shown in  Figures 6–9. The thresholds obtained by different methods are shown in Table 2, and absolute error ratios of the four competing methods are shown in Table 3.Table 2
Thresholds obtained by different methods on images in Figure4.
Figure4(a)
Figure4(b)
Figure4(c)
Figure4(d)
Figure4(e)
Figure4(f)
Tao
170
153
207
76
189
181
Sahoo
153
66
58
65
103
130
Cheng
151
44
116
77
126
144
Proposed
167
128
102
128
122
128Table 3
r
err
⁡ of different methods when segmenting images in Figure 4.
Figure4(a)
Figure4(b)
Figure4(c)
Figure4(d)
Figure4(e)
Figure4(f)
Tao
0.30%
0.07%
1.13%
35.22%
4.09%
5.81%
Sahoo
0.36%
90.44%
90.99%
47.64%
0.68%
0.66%
Cheng
0.37%
97.99%
0.66%
33.88%
0.23%
1.44%
Proposed
0.29%
0.06%
0.65%
0.28%
0.07%
0.65Original images.
(a)
(b)
(c)
(d)
(e)
(f)Ground truth images.
(a)
(b)
(c)
(d)
(e)
(f)The results of Tao’s method.
(a)
(b)
(c)
(d)
(e)
(f)The results of Sahoo’s method.
(a)
(b)
(c)
(d)
(e)
(f)The results of Cheng’s method.
(a)
(b)
(c)
(d)
(e)
(f)The results of our method.
(a)
(b)
(c)
(d)
(e)
(f)From Figures6–9, it can be found out that for image (a) all the four competing methods get rather good segmentation results by both visual inspection and quantitative analysis. However, for image (b), both Sahoo’s method and Cheng’s method fail. For image (c), Sahoo’s method fails again, and Tao’s method classifies nearly all the pixels as background. For image (d), only the proposed method segments out the infrared human targets successfully. For images (e) and (f), the results of Tao’s method express some kind of over-segmentation. For all the six images, the results of the proposed method are rather reasonable.As for the analysis of time complexity, Sahoo’s method used a purely exhaustive algorithm whose time complexity isO
(
L
4
). Cheng’s method calculated the 2-D fuzzy entropy by exhaustive algorithm and then selected the fuzzy parameter sets by genetic algorithm, so the time complexity of Cheng’s method is O
(
G
*
P
*
L
2
), in which G denotes the number of iterative generation and P denotes the size of population. Tao’s method is a 1-D method in which ant colony optimization is adopted, and thus its time complexity is O
(
G
*
P
*
L
). By reducing the time complexity of the computation of 2D FTE from O
(
L
2
) to O
(
L
) and employing SHLA to search for the optimal parameters of fuzzy membership function, the time complexity of our method is also O
(
G
*
P
*
L
).When the experiments are carried out in Matlab (R2013a) on a computer with Intel Core  i7-2600 CPU@2.93 GHz and 16 GB RAM, the running times (second) of different methods are listed in Table4. It can be found from Table 4 that Sahoo’s method takes the most time among all the methods, and the running time of our method is nearly equal to that of Tao’s 1-D method.Table 4
Computation time of different methods for test images in Figure4 (Second).
Figure4(a)
Figure4(b)
Figure4(c)
Figure4(d)
Figure4(e)
Tao
0.05282
0.03961
0.04594
0.05091
0.05371
Sahoo
186.32
153.47
156.37
162.63
145.67
Cheng
1.3048
1.0358
1.2547
1.09641
1.0846
Proposed
0.05094
0.04259
0.04807
0.04986
0.05237


## 5.1. Experiments on Synthetic Image

The image in Figure2(a) is a simple synthetic image with 240
×
240 pixels and shows an English character “H” (with gray level 80) on grey background (with gray level 160). Ideal segmentation is shown in Figure 2(b). Figure 2(c) is the image into which Gaussian noises with zero mean and 0.005 variance are added, and the histogram of Figure 2(c) is shown in Figure 2(d).Synthetic images: (a) original image, (b) ground truth image, (c) noisy image, and (d) histogram of the noisy image.
(a)
(b)
(c)
(d)The results obtained by the competing methods corresponding to Figure2(c) are shown in Figure 3. It can be found that, as a 1-D method, Tao’s method obtains the worst result; however the proposed method obtains the best one. Table 1 shows the thresholds and absolute errors obtained by competing methods. From Table 1, we can find that the absolute error ratio of the proposed method is lower than those of other methods.Table 1
Thresholds andr
err
⁡ of different methods in Figure 2(c).
Method
Tao
Sahoo
Cheng
Proposed
Threshold
77
121
120
116
r
err
⁡
14.34%
1.26%
0.99%
0.55%Thresholding results of noisy image obtained by different methods: (a) Tao’s result, (b) Sahoo’s result, (c) Cheng’s result, and (d) our result.
(a)
(b)
(c)
(d)


## 5.2. Experiments on Real Images

In order to further verify the validity of the presented method, we tested it on a variety of real images including those selected from IEEE OT CBSV WS Series Bench [16] and those captured by ourselves using a Guide IR928 thermal camera. According to the method used in [11, 17], the average of the segmentation results got by five people familiar with thermal imagery is used as ground truth images here. The original images are shown in Figure 4, where (a)~(d) are selected from the public dataset and (e), (f) are captured by ourselves. Those images are captured in different seasons under different weather conditions and light strengths. It can be observed that the human targets in (a)~(c) are smaller while those in (d)~(f) are bigger. The corresponding ground truth images are shown in Figure 5. The results of the four competing methods are shown in  Figures 6–9. The thresholds obtained by different methods are shown in Table 2, and absolute error ratios of the four competing methods are shown in Table 3.Table 2
Thresholds obtained by different methods on images in Figure4.
Figure4(a)
Figure4(b)
Figure4(c)
Figure4(d)
Figure4(e)
Figure4(f)
Tao
170
153
207
76
189
181
Sahoo
153
66
58
65
103
130
Cheng
151
44
116
77
126
144
Proposed
167
128
102
128
122
128Table 3
r
err
⁡ of different methods when segmenting images in Figure 4.
Figure4(a)
Figure4(b)
Figure4(c)
Figure4(d)
Figure4(e)
Figure4(f)
Tao
0.30%
0.07%
1.13%
35.22%
4.09%
5.81%
Sahoo
0.36%
90.44%
90.99%
47.64%
0.68%
0.66%
Cheng
0.37%
97.99%
0.66%
33.88%
0.23%
1.44%
Proposed
0.29%
0.06%
0.65%
0.28%
0.07%
0.65Original images.
(a)
(b)
(c)
(d)
(e)
(f)Ground truth images.
(a)
(b)
(c)
(d)
(e)
(f)The results of Tao’s method.
(a)
(b)
(c)
(d)
(e)
(f)The results of Sahoo’s method.
(a)
(b)
(c)
(d)
(e)
(f)The results of Cheng’s method.
(a)
(b)
(c)
(d)
(e)
(f)The results of our method.
(a)
(b)
(c)
(d)
(e)
(f)From Figures6–9, it can be found out that for image (a) all the four competing methods get rather good segmentation results by both visual inspection and quantitative analysis. However, for image (b), both Sahoo’s method and Cheng’s method fail. For image (c), Sahoo’s method fails again, and Tao’s method classifies nearly all the pixels as background. For image (d), only the proposed method segments out the infrared human targets successfully. For images (e) and (f), the results of Tao’s method express some kind of over-segmentation. For all the six images, the results of the proposed method are rather reasonable.As for the analysis of time complexity, Sahoo’s method used a purely exhaustive algorithm whose time complexity isO
(
L
4
). Cheng’s method calculated the 2-D fuzzy entropy by exhaustive algorithm and then selected the fuzzy parameter sets by genetic algorithm, so the time complexity of Cheng’s method is O
(
G
*
P
*
L
2
), in which G denotes the number of iterative generation and P denotes the size of population. Tao’s method is a 1-D method in which ant colony optimization is adopted, and thus its time complexity is O
(
G
*
P
*
L
). By reducing the time complexity of the computation of 2D FTE from O
(
L
2
) to O
(
L
) and employing SHLA to search for the optimal parameters of fuzzy membership function, the time complexity of our method is also O
(
G
*
P
*
L
).When the experiments are carried out in Matlab (R2013a) on a computer with Intel Core  i7-2600 CPU@2.93 GHz and 16 GB RAM, the running times (second) of different methods are listed in Table4. It can be found from Table 4 that Sahoo’s method takes the most time among all the methods, and the running time of our method is nearly equal to that of Tao’s 1-D method.Table 4
Computation time of different methods for test images in Figure4 (Second).
Figure4(a)
Figure4(b)
Figure4(c)
Figure4(d)
Figure4(e)
Tao
0.05282
0.03961
0.04594
0.05091
0.05371
Sahoo
186.32
153.47
156.37
162.63
145.67
Cheng
1.3048
1.0358
1.2547
1.09641
1.0846
Proposed
0.05094
0.04259
0.04807
0.04986
0.05237


## 6. Conclusion

In this paper, a thresholding method of infrared human image is developed based on 2-D Tsallis entropy and fuzzy sets theory. In the presented method, both the fuzziness of image and the spatial information of 2-D histogram are considered. To relieve the huge computation burden brought about by extending 1-D method to 2-D one, a fast algorithm is designed to reduce the time complexity of the computation of 2-D FTE fromO
(
L
2
) to O
(
L
). And then SHLA is employed to speed up the search of optimal threshold further. The experiments on both synthetic and real images show that the presented method is robust and effective.



---

*Source: 308164-2014-01-16.xml*