Image Thresholding Using Weighted Parzen-Window Estimation

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, histogram-based methods, entropy-based 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 Parzen-window 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 Parzen-window 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 Parzen-window estimation procedure. In this way, the number of the samples used in Parzen-window estimation decreases greatly, which may further reduce the computational burden and storage requirements of image thresholding.

IMAGE THRESHOLDING USING PARZEN-WINDOW ESTIMATION

With excellent performance and solid theoretical foundation, the Parzen-window estimation is a well-known non-parametric approach for probability estimation. Here, we state a novel thresholding algorithm based on Parzen-window 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 two-dimensional space. According to the Parzen-window estimation, for the point space ω_i, the probability density function p (x, y, ω_i) can be approximated using the following formulas:

(1)

(2)

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:

(3)

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:

(4)

(5)

According to the concept of entropy in information theory, the entropy of pixel (x, y) could be computed as follows:

(6)

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:

(7)

Where, Ω = [1, m]x[1, n].

The Parzen-window 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 PARZEN-WINDOW 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 Parzen-window 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:

(8)

The training procedure for a single gray-level: In order to find a set of appropriate reference pixels for effective weighted Parzen-window estimation, we derive a training procedure based on the idea of hierarchical clustering. We state the training procedure as the following pseudo-code:

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 sub-routine getNearestPair () returns two nearest pairs r₁, r₂ and store their weights into w₁ and w₂, respectively. Then r₁, r₂ are merged in the sub-routine mergePair ().

The sub-routine mergePair () involves the following key issues. Firstly,

and ω₀ = ω_i+ω_j

are inserted into R_i and W_i, respectively. Meanwhile, r₁, r₂ 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₀ to each reference pixel in DM except r₀.

According to the newly generated reference vector r₀ and ω₀, Pm is updated in UpdatePm () and the error e is recalculated using

in the sub-routine ComputeError ().

The temporary vector R₀, W₀ and variable m₀ are used to back up the past values of R_i, W_i and m. As we can see from above pseudo-code, they take the last values of R_i, W_i and m, which have been updated in the sub-routine mergePair (). R_i, W_i and m will recover to their past values from R₀, W₀ and m₀ if e exceeds e_max.

The proposed algorithm WPWT: To derive the new version of p (x, y) using weighted Parzen-window estimation, the following Gaussian kernel function is introduced:

(9)

For Gaussian Kernel function, the following two important results are used (Torkkola, 2003):

(10)

Thus with the obtained reference pixels and weights, we can have:

(11)

Furthermore, we have:

(12)

Similarly, we have:

(13)

(14)

For ease of computation, let:

(15)

We have:

(16)

(17)

(18)

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:

(19)

Based on the above, we summarize the novel image thresholding method WPWT as follows:

Fig. 1:	The training procedure

Fig. 2:	Upper triangular matrix of M