Image Denoising Based on Soft Computing Techniques
Abstract:
Image Denoising is one of the existing problems in research area. This paper presents an interactive algorithm for image Denoising and segmentation. This paper explains the task of segmenting any given color image using soft computing techniques. The segmentation techniques used are Fuzzy Clustering (FC), Fuzzy C Means (FCM) clustering and Convolutional Networks (CN). After the image is segmented, the noise can be removed by using bilateral filtering. The denoised images are compared using image quality metrics. The image quality metrics are Peak Signal to Noise Ratio (PSNR), and Mean Average Error (MAE). The time taken for Denoising is also used as a comparison parameter. The techniques have been tested with images of different size and resolution and the results are proven to be better than the existing state-of-art algorithms.
Keywords: Denoising, segmentation, Fuzzy clustering, Fuzzy C Means (FCM), Convolutional Networks (CN), bilateral filtering.
1. Introduction
Images are often corrupted by random variations in intensity values, called noise, either because of the data acquisition process, or because of occurring phenomena at scene of interest.
The goal of image denoising methods is to recover the original image (better quality image) from a noisy one, in order to perform, in an easier and more accurate way, an image processing task as image segmentation.
In computer vision literature, various methods dealing with segmentation, and feature extraction are discussed, which can be broadly grouped into region based techniques, edge based techniques, hybrid methods which combine edge and region methods, and so on. However, because of the variety and complexity of images, robust and efficient segmentation algorithm on color images is still a very challenging task and fully automatic segmentation procedures are far from satisfying in practical situations. This paper explains the task of classifying each pixel in an image into one of a discrete level of color classes using three main soft computing techniques, namely Fuzzy clustering, Fuzzy C Means, and Convolutional networks. The results obtained by soft computing techniques are compared with traditional hard c means technique. The results are found to be more accurate and reliable than the traditional method.
The rest of this paper is explained as follows: in Section 2, the three types of soft computing techniques are explained, the use of bilateral filtering is explained in Section 3, segmentation based Denoising is explained in Section 4, the experimental results are shown in Section 5, and the conclusion is in Section 6.
2. Soft Computing Techniques:
Extracting information from an image is referred to as image analysis. Image segmentation is a preliminary step in most automatic pictorial pattern recognition and scene analysis problems. It is one of the most difficult tasks in image processing. Image segmentation is the process of partitioning a digital image into multiple regions or clusters. Each region is made up of sets of pixels. Image segmentation simplifies and changes the representation of an image. i.e. the image is transferred into something that is more meaningful and easier to analyze. Image segmentation is typically used to locate objects of interest and boundaries like lines, curves in an image.
The pixels of a color image are represented as vectors. Each pixel is represented a triplet containing red, green, blue spectral values at that position. The RGB color model is shown in fig.1. This is based on Cartesian coordinate system. A color expressed by an RGB vector is said to be a color represented in RGB space.
Fig.1.RGB Color Model.
RGB color representation is one of the numbers of color models. RGB color model is
chosen for image segmentation due to its simplicity hence the fast processing speed that could be achieved [5]. Image segmentation refers to the process of dividing the image into connected regions where pixels of a region share a common property. For color images the common property is usually considered is the red: green: blue, color ratio. This ratio must be reasonably constant over the region. The color ratio does not have smoothly varying values when the pixel intensity is low. So color image segmentation based on color ratio requires that the intensity of the image must be above a threshold value. So instead of segmentation based on color ratio other techniques have been evolved. The requirements of good color image segmentation are as follows. A single region in a segmented image should not contain significantly different colors and a connected region containing same color should not have more than one label. All significant pixels should belong to the same labeled region. The intensity of a region should be reasonably uniform. Several image segmentation techniques have been suggested for gray scale images. In this paper we suggest the neural network approach for color images.
2.1.Fuzzy Clustering
In non-fuzzy or hard clustering, data is divided into crisp clusters, where each data point belongs to exactly one cluster. In fuzzy clustering, the data points can belong to more than one cluster[3], and associated with each of the points are membership grades that indicate the degree to which the data points belong to the different clusters. Fuzzy clustering belongs to the group of soft computing techniques (which include neural nets, fuzzy systems, and genetic algorithms).
In real applications there is very often no sharp boundary between clusters so that fuzzy clustering is often better suited for the data. Membership degrees between zero and one are used in fuzzy clustering [6] instead of crisp assignments of the data to clusters. The resulting data partition improves data understanding and reveals its internal structure. Partition clustering algorithms divide up a data set into clusters or classes, where similar data objects are assigned to the same cluster whereas dissimilar data objects should belong to different clusters.
Areas of application of fuzzy cluster analysis include data analysis, pattern recognition, and image segmentation. The detection of special geometrical shapes like circles and ellipses can be achieved by so-called shell clustering algorithms.
2.2. Fuzzy C Means
The most prominent algorithm is the FCM or Fuzzy C Means algorithm. The fuzzy C means algorithm was proposed as an improvement of the classic Hard C-Means clustering algorithm The FCM algorithm receives the data or the sample space, an n x m matrix where n is the number of data and m is the number of parameters. The number of clusters c, the assumption partition matrix U, the convergence value E all must be given to the algorithm. The assumption partition matrix has c number of rows and n number of columns and contains values from 0 to 1. The sum of every column has to be 1. The first step is to calculate the cluster centers. This is a matrix v of dimension c rows with m columns. The second step is to calculate the distance matrix D. The distance matrix constitutes the Euclidean distance between every pixel and every cluster center. This is a matrix with c rows and n columns. From the distance matrix the partition matrix U is calculated. If the difference between the initial partition matrix and the calculated partition matrix is greater than the convergence value then the entire process from calculating the cluster centers to the final partition matrix. The final partition matrix is taken and is used for reconstructing the image. Let us assume as a fuzzy C-Means Functional,
(1)
where ? = { x k | k € [1,n]} is a training set containing unlabeled samples = { y j | j € [1,c]} } is the set of centers of clusters; E j (x k) is a dissimilarity measure (distance or cost) between the sample x k and the center y j of a specific cluster j;U = [u jk] is the c x n fuzzy c-partition matrix, containing the membership values of all samples in all clusters;
m € (1, ?) is a control parameter of fuzziness.
The clustering problem can be defined as the minimization of J m with respect to Y, under the probabilistic constraint:
(2)
The Fuzzy C-Means (FCM) algorithm consists in the iteration of the following formulas:
for all j
(3)
And
(4)
? ? ? 1,? if E j (x k) = 0 and u jk = 0 ? l ? j where, in the case of the Euclidean space:
E j = xk ? y j 2 (5)
It is worth noting that if one chooses m = 1 the fuzzy C-Means Functional J m
(Eq. 1) reduces to the expectation of the global error (which we denote as
(6)
and the FCM algorithm becomes the classic Hard C-Means algorithm.
2.3. Convolutional Networks
A Convolutional network is an alternating sequence of linear filtering and nonlinear transformation operations. The input and output layers include one or more images, while intermediate layers contain “hidden” units with images called feature maps that are the internal computations of the algorithm. The activity of feature map a in layer k is given by
(7)
where Ik-1;b are feature maps that provide input to Ik;a, and denotes the convolution operation. The function f is the sigmoid f(x) = 1= (1 + e -x) and ?k;a is a bias parameter. We restrict our experiments to monochrome images and hence the networks contain a single image in the input layer. It is straightforward to extend this approach to color images by assuming an input layer with multiple images (e.g., RGB color channels). For numerical reasons, it is preferable to use input and target values in the range of 0 to 1, and hence the 8-bit integer intensity values of the dataset (values from 0 to 255) were normalized to lie between 0 and 1. We also explicitly encode the border of the image by padding an area surrounding the image with values of -1.
3. Bilateral Filtering:
The idea underlying bilateral filtering is to do in the range of an image what traditional filters do in its domain. Two pixels can be close to one another, that is, occupy nearby spatial location, or they can be similar to one another, that is, have nearby values, possibly in a perceptually meaningful fashion. Closeness refers to vicinity in the domain,
Similarity to vicinity in the range. Traditional filtering is domain filtering, and enforces closeness by weighing pixel values with coefficients that fall off with distance. Similarly, we define range filtering, which averages image values with weights that decay with dissimilarity. Range filters are nonlinear because their weights depend on image intensity or color. Computationally, they are no more complex than standard nonseparable filters.
Spatial locality is still an essential notion. In fact, we show that range filtering by it selfmerely distorts an image’s color map. We then combine range and domain filtering,
and show that the combination is much more interesting. We denote the combined filtering as bilateral filtering.
Since bilateral filters assume an explicit notion of distance in the domain and in the range of the image function, they can be applied to any function for which these two
distances can be defined. In particular, bilateral filters can be applied to color images just as easily as they are applied to black-and-white ones. The CIE-Lab color space [16] endows the space of colors with a perceptually meaningful measure of color similarity, in which short Euclidean distances correlate strongly with human color discrimination
performance [16]. Thus, if we use this metric in our bilateral filter, images are smoothed and edges are preserved in a way that is tuned to human performance. Only perceptually
similar colors are averaged together, and only perceptually visible edges are preserved.
4. Self Estimation Algorithm and Parameter Settings:
If the number of clusters is manually specified, the segmentation may not be effective. Hence there must be a system to calculate the robust number of clusters. A method has been suggested for automatically finding no. of clusters with K means clustering [7]. That algorithm is modified for finding no. of clusters in our work. The self estimation algorithm used for fuzzy clustering techniques finds the Euclidean distance between the different cluster centers. If the maximum Euclidean distance between the cluster centers is greater than the specified value, then the number of cluster centers is increased by one else the clusters are merged.. The self estimation algorithm for neural network finds the difference between the weight vectors. If the difference between the weight vectors is greater than the specified value, then the number of cluster centers is increased by one else the clusters are merged.
4.1. Algorithm
Step 0: Initialize weights wij.Set topological neighborhood parameters with its radius as Set learning rate parameters.
Step 1: While stopping condition are false, do steps 2 – 6
Step 2: for each input vector x, do steps 3 – 5
Step 3: For each j, compute: D(j) = ?i (wij – xi)2
Step 4: Find index J such that D(J) is a minimum
Step 5: For all units j within a specified neighborhood of J, and for all i: wij(new) = ij(old) + ?[xi – wij(old)]
Step 6: Update learning rate
The learning rate ? is a gradually decreasing function of training epochs. The formation of the competitive occurs in two phases. In the first phase the initial formation of the correct order takes place. In the second phase the final convergence. The second phase takes much longer than the first and requires a smaller value for the learning rate. Random values may be assigned for the initial weights. If some information is available concerning the distribution of clusters that might be appropriate for a particular problem, the initial weights can be taken to reflect that prior knowledge.
4.2. Parameter Settings:
For the bilateral filtering part of the proposed method, we set the parameters as follows: Bilateral filtering with parameters ?d = 3 pixels and ?r = 50 intensity values is applied to the image in figure 3 (a) to yield the image in figure 3 (b). Notice that most of the fine texture has been filtered away, and yet all contours are as crisp as in the original image.
Figure 3 (c) shows a detail of figure 3 (a), and figure 3 (d) shows the corresponding filtered version. The two onions have assumed a graphics-like appearance, and the fine texture has gone. However, the overall shading is preserved, because it is well within the band of the domain filter and is almost unaffected by the range filter. Also, the boundaries of the onions are preserved.
Figure 3: A picture before (a) and after (b) bilateral filtering. (c,d) are details from (a,b).
5. Experimental Results:
We derive training and test sets for our experiments from natural images in the Berkeley segmentation database, which has been previously used to study denoising [20, 4]. We restrict our experiments to the case of monochrome images; color images in the Berkeley dataset are converted to grayscale by averaging the color channels. The test set consists of 100 images, 77 with dimensions 321_481 and 23 with dimensions 481 _ 321. Quantitative comparisons are performed using the Peak Signal to Noise Ratio (PSNR) and Mean Average Error (MAE) of the output image and comparisons are made based on the Error Image. The Error of the corresponding image is calculated by subtracting the original image from the image we obtained.
5.1. Peak Signal to Noise Ratio
Signal-to-noise (SNR) estimates the quality of a reconstructed image compared with the original image. The basic idea is to compute a single number that reflects the quality of the reconstructed image[4]. Reconstructed images with higher metrics are judged better. In fact, traditional SNR measures do not equate with human subjective perception. Several research groups are working on perceptual measures, but for now signal-to-noise measures are used because they are easier to compute. Also to be noted that higher measures do not always mean better quality. The actual metric that is computed in this work is the peak signal-to-reconstructed image measure, which is called PSNR. Assume a source image f(i,j) is given that contains M by N pixels and a reconstructed image F(i,j)
where F is reconstructed by decoding the encoded version of f(i,j). Error metrics are computed on the luminance signal only so the pixel values f(i,j) range between black (0) and white (255). First the mean absolute error of the reconstructed image is computed (MAE) as follows
(11)
The summation is over all pixels. PSNR in decibels (dB)[4] is computed by using
PSNR = 10 log 10 (2552 / MAE). (12)
5.2. Error Image
The other important technique for displaying errors is to construct an error image which shows the pixel-by-pixel errors. The simplest computation of this image is to create an image by taking the difference between the reconstructed and original pixels. These images are hard to see because zero difference is black and most errors are small numbers which are shades of black. The typical construction of the error image multiples the difference by a constant to increase the visible difference and translates the entire image to a gray level. The computation is E(i,j)=2[f(i,j)-F(i,j)] +128 (13).
The constant (2) or the translation (128) can be adjusted to change the image. Some people use white (255) to signify no error and difference from white as an error which means that darker pixels are bigger errors.
Figure 4: Denoising results on an image from the test set. The noisy image was generated by adding Gaussian noise with ? = 50 to the clean image. Non-blind Denoising results for the BLS-GSM, FoE, and Convolutional network methods are shown. The lower left panel shows results for the outlined region in the upper left panel. The zoomed in region shows that in some areas CN2 output has less severe artifacts than the wavelet-based results and is sharper than the FoE results. CN1 results (PSNR=24:12) are visually similar to those of CN2.
Table below shows the comparison of the three techniques on their quality metrics.
S.No. Method PSNR Execution Time
1. Fuzzy Clustering (Fuzzy) 28.24 253.14
2. Fuzzy C Means Clustering (FCM) 30.57 161.71
3. Convolutional Network (CN) 39.39 2.28
6. Conclusion:
Out of the three methods tested competitive neural network is found to be good on the basis of image reproduction because of increased PSNR as well as image compression due to the increased compression ratio. We have found that the optimal ?r value of the bilateral filter is linearly related to the standard deviation of the noise. The optimal value of the ?d is relatively independent of the noise power. Based on these results, we estimate
the noise variance at each level of the subbands decomposition and use the optimal ?r value for bilateral filtering. The key factor in the performance of the proposed method is the multiresolution application of the bilateral filter. It helped eliminating the coarse-grain noise in images. The wavelet thresholding adds power the proposed method.
This work has several applications in various scientific fields like Satellite imaging, Map determination, Medical imaging, Optical character recognition (OCR), Non-Destructive testing, etc. The program developed has been tested with various pictures and the results were proven to be fruitful. The program has also been tested for its consistency and its reliability.
References
[1] C. Rosenberger,K. Chehdi, “Unsupervised Clustering Method with Optimal Estimationof the
Number of Clusters: Application to Image Segmentation” in the proceedings of 15th
International Conference on Pattern Recognition (ICPR’00) – Volume 1 p. 1656.
[2] Sven behnke and nicolaos b. Karayiannis, 1998, “Competitive neural trees for pattern
classification”, in the IEEE transactions on neural networks, vol. 9, no. 6, pp.1352 -1369,
november 1998.
[3] Rezaee, M.R. van der Zwet, P.M.J. Lelieveldt, B.P.E. van der Geest, R.J. Reiber, J.H.C., 2000, “A multiresolution image segmentation technique based on pyramidal segmentation and fuzzy clustering” in IEEE Transactions on Image Processing, pp: 1238-1248, Vol. 9, No: 7, Jul 2000.
[4] Hung-Ching Lu, Ted Tao,2006, “Closed-loop method to improve image PSNR in pyramidal CMAC networks” in the Computer Applications in Technology 2006 – Vol. 25, No.1 pp. 22 – 29.
[5] R. Krishnapuram, J.M. Keller., 1996, The possibilistic c-means:insights & recommendations. IEEE Trans. Fuzzy Systems 4: 385-393, 1996.
[6] Songcan Chen, Daoqiang Zhang, 2004, “Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure” in IEEE Transactions on Systems, Man and Cybernetics, Vol.34,No.4,pp: 1907-1916,Aug 2004.
[7] Siddheswar Ray and Rose H Turi, 1999, “Determination of number of clusters in k-means clustering and application in colour image segmentation,” in 4th International Conference on Advances in Pattern Recognition and Digital Techniques (ICAPRDT’99), 1999.
[8]. C. Tomasi and R. Manduchi, “Bilateral filtering for gray and color images,” in Proc. Int. Conf. Computer Vision, 1998, pp.839–846.
[9]. S. G. Chang, B. Yu, and M. Vetterli, “Adaptive wavelet thresholding for image denoising and compression,” Trans. Image Processing, vol. 9, no. 9, pp. 1532–1546, September 2000.
[10]. D. L. Donoho and I. M. Johnstone, “Ideal spatial adaptation by wavelet shrinkage,” Biometrika, vol. 81, no. 3, pp. 425–455, 1994.