INTRODUCTION
The problem of image segmentation throws great challenges for pattern
recognition and image processing community. Image thresholding is the
simplest technique for image segmentation and its primary task is to find
the optimal threshold which could separate objects from background well.
With the advantage of simple and easy implementation, the global thresholding
is still a popular technique over the past years. Several successful thresholding
methods such as OTSU methods, histogrambased methods, entropybased method
become popular (Sezgin and Sankur, 2004; Zhang, 2001; de Albuquerque et
al., 2004; Sarkar and Soundararajan, 2000; Yang and Yang, 2004). Considering
the analogy between clustering and image segmentation, some clustering
procedures based on pdf estimation have been successfully applied to image
segmentation. Recently, a novel thresholding method based on Parzenwindow
estimation (i.e., PWT) has been proposed by Wang et al. (2008).
This method effectively integrates spatial information on pixels of different
gray levels into the process pdf estimation which also the base of our
work here.
In this study, the concept of weighted Parzenwindow estimation is presented
and a novel image thresholding method based on this concept is accordingly
proposed. By combining several pixels which are close to each other, a
reference pixel is generated and it will be used in the weighted Parzenwindow
estimation procedure. In this way, the number of the samples used in Parzenwindow
estimation decreases greatly, which may further reduce the computational
burden and storage requirements of image thresholding.
IMAGE THRESHOLDING USING PARZENWINDOW ESTIMATION
With excellent performance and solid theoretical foundation, the Parzenwindow
estimation is a wellknown nonparametric approach for probability estimation.
Here, we state a novel thresholding algorithm based on Parzenwindow technique
in Wang et al. (2008) as follows:
Assuming f (x, y) is the gray level of the pixel with its location (x,
y) in image, an mxn sized image with L gray levels could be expressed
as {f(x, y)  xε{1, 2, ..., m}, yε{1, 2, ..., n}}. Let ω_{i}
= {(x, y)  f(x, y) = i, x ε{1, 2, ..., m}, yε{1, 2, ..., n},
i ε{1, 2, ..., L}} and C_{i} denotes the number of pixels
in ω_{i}, i = 1, 2..., L, we have {f (x, y)  xε {1,
2, ..., n}}, then
Obviously, ω_{i} is defined in a twodimensional space.
According to the Parzenwindow estimation, for the point space ω_{i},
the probability density function p (x, y, ω_{i}) can be approximated
using the following formulas:
Where:
hc_{i} 
= 
Window width of the ith gray level set 
(x_{j},
y_{j}) 
= 
The jth pixel in ω_{i}, 
Vc_{i} 
= 
The volume of the corresponding hypercube with h_{ci} as its length of each edge, i.e., Vc_{i} = Hc_{i}^{2} for an image and 
is a good choice; p(ω_{i}) can be approximated by C_{i}/N,
1≤i≤L and φ(·) is a kernel function.
Because of the continuous distribution of pixels with same gray level
in images, a pixel’s possibility of having gray level i is in inverse
proportion to its Euclidean distance to other pixels whose gray levels
are i. The following Gaussian function for φ(·) reflects this
fact well:
Let p(x, y) be the probability density of pixel (x, y) belonging to the
background class and r(x, y) be the probability density of pixel (x, y)
belonging to the object, we have:
According to the concept of entropy in information theory, the entropy
of pixel (x, y) could be computed as follows:
bviously, H(x, y) is maximized when p(x, y) = r(x, y) is satisfied. It
implies that the smaller p (x, y)r(x, y) takes, the larger H(x, y)
gets. Therefore, In order to make class p and class r well separated,
the following criterion function was used:
Where, Ω = [1, m]x[1, n].
The Parzenwindow estimation for p(x, y) and r(x, y) reflects the fact that
the pixel’s possibility of being gray level i is determined by its distance
to other pixels with same gray level i. However, in order to compute p(x, y)
and r(x, y) for a pixel at (x, y) in an image, all the pixels except itself
will be considered and this will bring very big computational burden.
WEIGHTED PARZENWINDOW METHOD FOR IMAGE THREDSHOLDING
In order to accelerate the PWT procedure and reduce the computational
burden, we will derive its enhanced version i.e., image thresholding WPWT
based on weighted Parzenwindow estimation. In the proposed method WPWT,
a training procedure is performed to obtain a set of the reference pixels
and weights at each gray level, which undoubtly yields errors into the
computation of t_{opt}. However, by controlling the upper bound
of errors we can make thresholding results acceptable.
The set of the reference pixels at gray level i is denoted
as:
Accordingly, the set of the weights for the reference pixels
at gray level i is denoted as:
So, as an approximation of (1), p (w, y  ω_{i}) in (1)
can be computed as:
Where:
w_{ij} 
= 
Weight of the jth reference pixel at gray level i, which
is equal to the number of the original training samples that were collapsed
into (x_{ij}^{(r)}, y_{ij}^{(r)}) 
The training procedure for a single graylevel: In order to find
a set of appropriate reference pixels for effective weighted Parzenwindow
estimation, we derive a training procedure based on the idea of hierarchical
clustering. We state the training procedure as the following pseudocode:
n 
: 
:Number of the pixels at each gray level 
m 
: 
Number of the reference pixels at each gray level 
R_{i} 
: 
Vector of the reference pixels at gray level i 
r_{ij} 
: 
The jth reference pixel of gray level i 
W_{i} 
: 
Vector of weights for the reference pixels at gray level i 
w_{ij} 
: 
Weight of the jth reference pixel at gray level i 
DM 
: 
Distance matrix of the reference pixels at each gray level 
For the above training procedure, we give more details as follows.
This procedure initializes R_{i} with the pixels of gray level
i in the image. Then R_{i} is updated by combining two nearest
pixels until the error e exceeds e_{max} or only one reference
pixel remains.
The subroutine getNearestPair () returns two nearest pairs r_{1},
r_{2} and store their weights into w_{1} and w_{2},
respectively. Then r_{1}, r_{2} are merged in the
subroutine mergePair ().
The subroutine mergePair () involves the following key issues. Firstly,
and ω_{0} = ω_{i}+ω_{j}
are inserted into R_{i} and W_{i}, respectively. Meanwhile,
r_{1}, r_{2} are removed from R_{i} and so ω_{i}
and ω_{j} are done from W_{i}. Then, m is decreased
by 1. Finally, the distance matrix DM is updated by calculating the distance
from the newly generated reference pixel r_{0} to each reference
pixel in DM except r_{0}.
According to the newly generated reference vector r_{0} and ω_{0},
Pm is updated in UpdatePm () and the error e is recalculated using
in the subroutine ComputeError ().
The temporary vector R_{0}, W_{0} and variable m_{0}
are used to back up the past values of R_{i}, W_{i} and
m. As we can see from above pseudocode, they take the last values of
R_{i}, W_{i} and m, which have been updated in the subroutine
mergePair (). R_{i}, W_{i} and m will recover to their
past values from R_{0}, W_{0} and m_{0} if e exceeds
e_{max}.
The proposed algorithm WPWT: To derive the new version of p (x,
y) using weighted Parzenwindow estimation, the following Gaussian kernel
function is introduced:
For Gaussian Kernel function, the following two important results are
used (Torkkola, 2003):
Thus with the obtained reference pixels and weights, we can have:
Furthermore, we have:
Similarly, we have:
For ease of computation, let:
We have:
Due to the symmetry of elements in M, we only show the upper triangular
matrix in Fig. 2. As we can readily see, for some t,
(16), (17) and (18) corresponds to the sums of elements in area A, B and
C, respectively.
Thus, t_{opt} can be computed as:
Based on the above, we summarize the novel image thresholding method
WPWT as follows:
• 
Construct the histogram for an N = mxn image with L gray levels. 
• 
For each gray level, compute the reference pixels using the training
algorithm in Fig. 1. 
• 
Construct the matrix M using (15). 
• 
For each gray level, compute the corresponding t and find t_{op} 
• 
Segment the image with t_{opt }and output the segmented
image accordingly 

Fig. 1: 
The training procedure 

Fig. 2: 
Upper triangular matrix of M 
RESULTS
Experiments were conducted with several images provided by MATLAB and
these images have been widely used in literature. We implemented the proposed
algorithm WPWT with MATLAB 7 and run it on the computer with P4 2.66GHz
CPU and 512M memory. In order to observe how e_{max} values affect
the performance of our algorithm, we used different e_{max} values
varying from 0.1 to 0.4 with step length 0.1.
The first experiment is used to show how different e_{max} values
affect the numbers of the generated reference pixels (Table
1).

Fig. 3: 
Segmentation results of WPWT and PWT in Wang et al. (2008) 

Fig. 4: 
Segmentation results on noisy images 
Table 1: 
The number of the reference pixels obtained by the
training procedure 

Table 2: 
Running time of WPWT and PWT (seconds) 

The second experiment is taken to show the influence of different e_{max}
values on running speed of the algorithm as well as visual effects of
the thresholding results. The complexity of both PWT and our proposed
method is O (n^{2}/L), where n is the total number of pixels in
the image and L is the number of gray levels. In our proposed method,
n is decreased greatly by controlling e_{max} so that the performance
of our algorithm can be enhanced. In order to make a comparison with PWT
in Wang et al. (2008), Table 2 shows the running
time of both WPWT and PWT with different e_{max}.
An appropriate e_{max} is vital to the running speed of Parzenwindow
estimation. According to our experiments, for many images, e_{max}
= 0.3 is a good choice for the speed up of the proposed algorithm and
the final visual effects of the segmented images. Figure 3 shows the corresponding
segmentation results of both WPWT and PWT.
Obviously, e_{max} has an important influence on the optimal
threshold t_{opt.} However, when e_{max} ε [0.2,
0.4], all the obtained segmentation results are very acceptable from the
viewpoint of the visual effects for the segmented images.
The final experiment shows the performance of our algorithm on noisy
images. In this experiment, white noise is added into the original image
and the segmentation results obtained by the WPWT method are shown in
Fig. 4. From the obtained results, we can see that the
proposed algorithm can obtain almost the same results with that the original
images, which verifies the robustness of the proposed algorithm on noisy
images.
CONCLUSION
We propose a novel image thresholding method based on weighted Parzenwindow
estimation in this study. In our method, we decrease the number of pixels
by using the Parzenwindow estimation with a hierarchical clustering procedure
which calculates a set of the reference pixels and weights by merging
the corresponding pixel pairs. During this process, the error produced
by merging pixel pairs is controlled by emax. Then the thresholding
algorithm based on weighted Parzenwindow estimation (i.e., WPWT) is presented.
Unlike PWT in Wang et al. (2008), the proposed WPWT here approximates
the probability of each pixel with the reference pixels and weights. Compared
with PWT, the experimental results here show that our method can accelerate
the image thresholding and reduce the space requirements greatly without
degrading final segmentation results a lot.
ACKNOWLEDGMENTS
This study is supported by National 973 Key Project (Grant No. 2006CB705700),
National Science Foundation of China, National 863 Project (Grant No.2007AA1Z158),
National Defense Basic Research Grant, New_century Outstanding Young Scholar
Grant of Ministry of Education of China (Grant No. NCET040496), National
KeySoft Lab. at Nanjing University, the Key Lab. of Computer Science at
Institute of Software, CAS, China, the Key Lab. of Computer Information
Technologies at JiangSu Province, the 2004 key project of Ministry of
Education of China and National Key Lab. of Pattern Recognition at Institute
of Automation, CAS, China.