A High Performance Architecture for Elimination of Impulse Noise in Images

A High Performance Architecture for Elimination of Impulse Noise in Images

Sabeeh Ahammed M T

Dept. of Electronics, Govt. Engineering College,

Kozhikode, India.

Jithesh C P

Dept. of Electronics, Govt. Engineering College,

Kozhikode, India.

AbstractNoise filtering and image enhancement are two active areas of research in signal processing. For the time of signal acquisition and transmission, impulse noise may corrupt the digital data. To overcome this, switching median filters are generally used which consist of impulse detection and noise filtering. In this paper, an efficient decision tree based denoising technique and a high performance architecture for FPGA prototyping is presented for the elimination of random valued impulse noise. To identify noise pixels, we propose a new tree based impulse noise detector. The proposed architecture make use of parallel computation by splitting the input image in to odd and even index pixel masks. An additional performance enhancement is achieved by introducing pipelining between processing stages. The design is implemented using XILINX ISE

1. for Virtex 5 ML507 FPGA platform which can operate at 106 MHz clock frequency. The proposed method outperforms the existing denoising techniques in terms of image quality as shown by the simulation results.

   KeywordsImproved decision tree; Impulse noise; Image denoising

   1. INTRODUCTION

      There are many applications in image processing for areas such as face recognition, remote sensing, techniques for scanning and medical imaging. The images may get corrupted by impulse noise. This could happen during acquisition and transmission. So, efficient denoising technique plays an important role in the world of image processing. The distribution of noisy pixel intensities are different in many cases. They are broadly classified into the following, fixed valued impulse noise (salt and-pepper noise) and random valued impulse noise. In the case of random valued impulse noise, the distribution is uniform and because of the random nature, it is difficult to remove them. The focus of this work is to eliminate random valued impulse noise from the corrupted images. There are different methods available for this purpose [5], [6], [7],[8],[9]. Some methods make use of standard median filter [5] or its alterations [6], [7]. The approach here is to introduce a modification of both noisy and noise-free

      pixels, which blurs the image. The methods in [8], [9] use an

      processed. The decision tree is a powerful form of multivariable analysis [10]. A complex decision is divided into smaller simpler steps. There have been several decision tree based methods [4],[12]. A novel adaptive decision tree based noise detector is presented in [2]. Here, a decision tree based noise detector is followed by an edge preserving filter.

      In this paper, we propose an improved decision tree based denoising method (IDTBDM) based on decision-trees for elimination of random-valued impulse noise. This method consists of an impulse noise detector based on improved decision tree. The experimental outcome ensures the better performance of the proposed technique, if we analyse the images with respect to the visual quality and quantitative evaluation when compared with the other denoising methods [5], [6],[7], [8], [9]. The requirement of an efficient architecture with high performance and low cost is very challenging in real-time applications. The architecture for proposed design is modelled using VHDL and implemented on Xilinx Virtex 5 ML507 FPGA. Parallel processing and pipelining are introduced in the implementation for performance enhancement. The hardware is cost effective as the design is implemented using low complexity computational blocks. Our design achieves a clock speed of 106 MHZ.

      The rest of the paper is systematized as follows: Section II describes the proposed IDTBDM. Section III describes System architecture of IDTBDM. Section IV describes the implementation results. We conclude the paper in section IV.

   2. PROPOSED IDTBDM

      In this paper, random valued impulse noise which is uniformly distributed is considered as in [5],[9] and [10]. We accept a 3×3 mask for image denoising. Let pixel which is to be denoised is at coordinate (i, j). The pixel is denoted as pi,j and its luminance value is noted as fi,j as shown in Fig. 1. In an image input sequence , we divide eight other adjacent pixel values into two groups: WT_Half and WB_Half . They are given as in equation (1) and (2).

      efficient switching strategy so as to avoid the damage on the pixels that are noise free. The method of switching median filters work in two steps. First, impulse noise is detected and then noise is filtered. The detection is done by an impulse detector, and only the pixels which are detected are further

      WT _ Half a,b,c,d

      (1)

      Fig.1. A 3 x 3 mask centered on pi, j

      WB _ Half e, f , g, h

      (2)

      1). Isolation module: If we consider a smooth region the pixel values present in that region shows only a gradual change or do not change at all. In that case, small differences exist between neighbouring pixel values. In a section, the values are distribute differently, if there exist noise or edges. The smoothness of the nearby pixels determine whether the current pixel is an isolation point or not. The pixels called as isolation point, if they have low similarity with the neighbouring pixels. Hence, difference between them is large. Following the above principles, firstly we identify the maximum and minimum intensity values in WT_Half denoted as T_H_max and T_H_min, and compute the difference between them, denoted as T_H_D.

      Our method termed as IDTBDM consists of two components: An improved impulse detector and an edge- preserving filter. The impulse detector decides pi,j is a noisy pixel or not, by using the improved decision tree and the

      To get B_H_D for WB_Half, we can use the similar idea mentioned above. In order to find out whether the nearby region belongs to a smooth area or not, the obtained differences are compared with a threshold T_a . The equations are as

      relationship between pixel pi,j and its adjacent pixels. We use edge preserving image filter to generate the reconstructed value of noisy pixel, based on direction oriented. For noise free pixel, the value will be retained. The outline of the

      T _ H _ D T _ H _ max T _ H _ min

      B _ H _ D B _ H _ max B _ H _ min

      (3)

      (4)

      IDTBDM is depicted in Fig.2

      1. Improved Decision Tree Based Impulse Detector

         true if

         Smooth or

         false

         (T _ H _ D T _ a)

         (B _ H _ D T _ a) otherwise

         (5)

         In [2] contains three modules isolation module (IM), fringe module (FM), and similarity module (SM). We propose a more effective algorithm for isolation module than mentioned in [2]. Decision tree is made by considering three combined decision of these modules. The status of pi,j can be evaluated by using equations of different modules. we begin with isolation module to decide whether the pixel goes to

         If the nearby region does not belong to a smooth area, there also have a chance, that the considering pixel might be noisy. So next, we calculate mean of neighbouring pixel values named as Mean_nbrs and the difference between Mean_nbrs and fi,j . Then, if the difference is greater than threshold T_b , we decide the pixel may be noisy.

         noisy or noise free. If the decision is false, we confirm that the

         pixel is noise free. If not, the pixel might be a noisy pixel or an

         Mean _ nbrs mean(a,b,c,d,e, f , g,h)

         (6)

         edge pixel.

         To differentiate between edge and noise pixel, fringe module is used. Fringe module gives positive result, if the pixel is on an edge (noise free) or else it shows negative. The

         N _ Smooth true

         false

         true

         if fi, j Mean_ nbrs T _ b otherwise

         if Smooth true

         (7)

         similarity module make the final decision wherein isolation and fringe module fails. Similarity module checks the likeness between each pixel and its neighbours. Accordingly we decide

         Decision1 or

         false

         N _ Smooth true otherwise

         (8)

         the pixel pi,j is a noisy pixel or not. Three modules are explained as below

         Noisy image

         Next, we take pi,j into account. At first, we must calculate two values, the difference between fi,j and T_H_max , and the difference between fi,j and T_H_min. A threshold T_b is used to compare the obtained differences. As in the case of WB_Half

         the similar method is worked. The equations are as

         Decision tree based

         true if fi, j T _ H _ max T _ b

         impulse detector

         IM _ T _ H or

         false

         fi, j

         • T _ H _ min T _ b otherwise

           (9)

           corrupted

           yes

           Edge

           preserving

           true if

           fi, j

         • B _ H _ max

           T _ b

           no

           Restored image

           .

           filter

           IM _ B _ H or

           false

           true if

           Decision2 or

           false

           fi, j B _ H _ min T _ b

           otherwise

           IM _ T _ H true

           IM _ B _ H true otherwise

           (10)

           (11)

           Fig.2. The dataflow of IDTBDM

           At the end, we can make a transient judgement whether pi,j

           belongs to a probably noisy pixel or is noise free.

           2). Fringe module: It is difficult to conclude the pixel is

           we need to define the following variables

           Minmi, j as

           Maxmi, j

           and

           noisy or situated on an edge. For solving this difficulty, four directions from E1 to E4 as illustrated in Fig. 3 is defined. For example, consider direction E1, by manipulating the absolute difference between the two pixel values along the direction and fi,j , we can decide if it is edge or not. The complete equations

           Maxmi, j 6 _ thinWi, j T _ e Minmi, j 4 _ thinWi, j T _ e

           To evaluate the status of pixel pi, j ,

           Maxmi, j and

           (17)

           (18)

           Minmi, j

           are as

           true if

           a fi. j T _ c

           (12)

           are used. We have to do some alterations in order to make the decision more perfect such as

           F _ E1

           or h fi, j T _ c

           P

           Maxmi, j

           if Maxmi, j

           MedianInWi, j

           • T _ f

             (19)

             or

             a h T _ d

             max MedianInW

             • T _ f

               otherwise

               false

               otherwise

               i, j

               P Minmi, j

               if Minmi, j

               MedianInWi, j

         • T _ f

         (20)

         true if

         c fi, j T _ c

         min

         MedianInWi, j T _ f

         otherwise

         F _ E2

         or f fi, j T _ c

         (13)

         At the end, we can conclude that Pi,j is a noise pixel, if fi,j

         or

         c f T _ d

         is not between Pmax and Pmin. For creating restored value, edge

         false

         otherwise

         preserving filter is used. For noise free pixel, we keep the same value fi,j will be the output. Equation is shown below

         true if

         b fi, j T _ c

         (14)

         Decision4 true

         if f

         i, j

         Pmax or

         fi, j

         Pmin

         (21)

         F _ E3

         or g fi, j T _ c

         or b g T _ d

         false

         otherwise

         false

         true if

         otherwise

         d fi, j T _ c

         It is clear that, in this proposed technique, the excellence of denoised images is being affected by the threshold. Take in to account our experimental analysis, the thresholds

         F _ E4 or

         or

         false

         e fi, j T _ c

         d e T _ d

         otherwise

         (15)

         Ta , Tb , Tc , Td , Te and Tf are fix as 20, 25, 30, 60, 15, and 60 respectively.

         false if F _ E1 or Decision3 or F _ E3 or

         F _ E2

         F _ E4

         (16)

      2. Edge preserving image filter

      The Fig. 4. shows, the dataflow of our edge preserving image filter. The method works as follows. Consider eight

      directional differences from Da to Dh , as illustrated in Fig. 5.

      true

      3) Similarity module:

      otherwise

      Mask W

      The similarity module is the last step in impulse detection. The intensity values in mask W might be close when it is positioned in a noise free area. In the variational sequence, impulse is generally positioned near one of its ends and median is frequently placed in the centre. So, there is a chance for noisy signals if the variational series contains very large or small values. Based on this concept, we can obtain the values (fourth, fifth, and sixth) which are near to the median in mask W, by sorting the nine values in increasing order. The 4_thinWi,j, MedInWi,j , and 6_thinWi,j are stands for fourth, fifth, and sixth values correspondingly. To perform the operation,

      Fig.3. Four directions in IDTBDM.

      Choose the edges

      Calculate edge distance

      Find out the minimum edge and

      reconstruct

      Check the reconstructed value

      Fig.4. Dataflow of edge-preserving image filter.

      Only the noise free pixels are taken into account to avoid possible false detection. Directions passing through the suspected pixels are avoided. The directional differences of the chosen directions which are calculated by the edge filter are used and the smallest among them is calculated. The equations are as follows:

      Da d a

      Db a g b

      Dc b g 2

      Dd b f

      • c g

      (22)

      De c d e f Df d 2

      Dg a 2

      Dh c f 2

      d h a e 4 if

      Da Dmin

      a g b h 4 if

      Db

      Dmin

      Fig.5. Eight directional differences of IDTBDM

      To filter the bias edge, a tuning skill is required. If the mean

      b g 2

      if Dc Dmin

      calculated sits on an edge, it will be equal to the median of g, e,

      b f c g 4 if

      f

      Dd

      Dmin

      (23)

      d and b because of the spatial relation. If not, the values of

      f i, j

      i, j

      c d e f 4 if

      De Dmin

      will be substituted by the median of g, e, d and b. Thus the

      d e 4

      if D f

      Dmin

      algorithm preserves an edge in the image. We can express

      f i, j

      f

      a h 4

      if Dg Dmin as

      c f 4

      if Dh Dmin

      f i, j

      median

      i, j

      , b, d, e, g

      (24)

      In the final block of Fig. 4, the smallest directional difference specifies that the spatial relation of pi, j , with the pixels in the

      particular direction mentioned is the strongest. So there is a greater probability for the existence of an edge in that

      direction.. So f i, j , the mean of luminance values of the pixels which belonging to the smallest directional difference is determined.

   3. SYSTEM ARCHITECTURE OF IDTBDM

      The block diagram of the system architecture for IDTBDM is shown in Fig.6. System architecture includes five modules: split module, isolation module, fringe module, similarity module and edge preserving filter.

      IDTBDM MODULE

      Ppeline registers

      Input image block

      Split

      module

      Isolation module Odd pixels

      Even pixels

      Fringe module Odd pixels

      Even pixels

      Similarity module Odd pixels

      Even pixels

      Edge preserving image filter

      Odd even pixel merging

      Output image block

      Image Buffer

      Image Buffer

      Image Buffer

      Fig.6. Block diagram of system architecture for IDTBDM

      TABLE I

      DEVICE UTILIZATION AND TIMING SUMMARY OF IDTBDM SYSTEM

      Slice logic utilization
      Number of slice registers	3158 out of 44800	2%
      Number of slice LUTs	26482 out of 44800	59%
      Number used as Logic	26410 out of 44800	58%
      IO utilization
      Number of Ios	579
      Number of bonded IOBs	515 out of 640	58%
      Specific Feature Utilization
      Number of BUFG/BUFGCTRLs	2 out of 32	6%
      Clock period	9.39ns
      Clock frequency	106.48 MHz

      To improve the performance of architecture two strategies are implemented: parallel processing and pipelining. To provide concurrent operation, parallel processing is implemented in each module by splitting the input image block in to odd and even pixels. For this, split module is introduced in the architecture as the first block which divides the input image in to odd and even index pixels. This facilitates the concurrent operation in each of the following modules. To improve clock speed, pipeline registers are placed in between modules. Image buffers are used to save the previous cycle input image block. This design not only provides clock improvement but also streams the output in every clock cycle.

      Fig.7. Noise corruption (%) vs PSNR (dB).

   4. IMPLEMENTATION RESULTS

      The proposed architecture is modelled using VHDL and implemented on Xilinx Virtex 5 ML507 FPGA. The device utilization and timing summary is shown in Table 1. To examine the distinguishing features and the quality of denoised images of different denoising algorithms, various simulations are carried out on eight-bit gray scale images having size 256×256: Lena, Blackbuck and Peppers. The corrupted image versions are generated in MATLAB environment adding random-valued impulse noise at various noise densities. Then,

      Fig.8. Results of different methods in restoring 10 percent corrupted image Blackbuck. (a) Original image (b) Noisy image (c) DTBDM (d) IDTBDM

      TABLE II

      COMPARISON OF PSNR (dB) OF IMAGES CORRUPTED BY 10 % IMPULSES

      Method/Images	Lena	Blackbuck	Peppers
      Noisy	19.18	19.62	20.12
      Median	32.51	33.12	33.64
      DTBDM	37.51	37.92	38.12
      IDTBDM	39.34	39.87	40.12

      we use different methods to find out impulse noise and restore the corrupted image. The proposed IDTBDM is compared with DTBDM by comparing the two parameters. The quantitative quality of the restored images attained from different method are analysed by observing the peak signal-to-noise ratio (PSNR). Table.2 list the restoration results in PSNR (dB) of different images corrupted by 10 percent impulses. Graphical representation of previous PSNR values and proposed PSNR values is shown in Fig.7. Comparing with those experimental results, the quantitative qualities of proposed IDTBDM are better than DTBDM. Also the experimental results demonstrate the excellent performance of IDTBDM in terms of image quality shown in Fig.8.

   5. CONCLUSION

In this paper, a high performance architecture for FPGA prototyping is proposed for the removal of random valued impulse noise. The main advantage of this architecture is that it is of a very low complexity. Our design achieves clock speed of 106 MHZ. It provides better results in terms of PSNR and image quality.

REFERENCES

1. R. C. Gonzalez and R. E. Woods, Digital Image Processing. Pearson Education, Upper Saddle River, New Jersey, 2007

2. Chih-Yuan Lien, Chien-Chuan Huang, Pei-Yin Chen, Member, IEEE, and Yi-Fan Lin An Efficient Denoising Architecture for Removal of Impulse Noise in Images, IEEE transactions on computers, vol. 62, no. 4, april 2013.

3. H. Hwang and R.A. Haddad, Adaptive Median Filters: New Algorithms and Results, IEEE Trans. Image Processing, vol. 4, no. 4, pp. 499-502,Apr. 1995.

4. S. Zhang and M.A. Karim, A New Impulse Detector for Switching Median Filter, IEEE Signal Processing Letters, vol. 9, no. 11, pp. 360- 363, Nov. 2002.

5. T. Nodes and N. Gallagher, Median Filters: Some Modifications and Their Properties, IEEE Trans. Acoustics, Speech, Signal Processing, vol. ASSP-30, no. 5, pp. 739-746, Oct. 1982.

6. S.-J. Ko and Y.-H. Lee, Center Weighted Median Filters and Their Applications to Image Enhancement, IEEE Trans. Circuits Systems, vol.38, no. 9, pp. 984-993, Sept. 1991.

7. T. Sun and Y. Neuvo, Detail-Preserving Median Based Filters in Image Processing, Pattern Recognition Letters, vol. 15, pp. 341-347, Apr. 1994.

8. E. Abreu, M. Lightstone, S.K. Mitra, and K. Arakawa, A New Efficient Approach for the Removal of Impulse Noise from Highly Corrupted Images, IEEE Trans. Image Processing, vol. 5, no. 6, pp. 1012-1025, June 1996.

9. T. Chen and H.R. Wu, Adaptive Impulse Detection Using Center- Weighted Median Filters, IEEE Signal Processing Letters, vol. 8, no.1, pp. 1-3, Jan. 2001.

10. B. De Ville, Decision Trees for Business Intelligence and Data Mining, SAS Publishing, 2007.

11. S. Rasoul Safavian and D. Landgrebe, A Survey of Decision Tree Classifier Methodology, IEEE Trans. Systems Man, Cybernetics, vol. 21, no. 3, pp 660-674, May 1991.

12. H.-H. Tsai, X.-P. Lin, and B.-M. Chang, An Image Filter with a Hybrid Impulse Detector Based on Decision Tree and Particle Swarm Optimization, Proc. IEEE Intl Conf. Machine Learning and Cybernetics,July 2009.

13. H.-L. Eng and K.-K. Ma, Noise Adaptive Soft-Switching Median Filter, IEEE Trans. Image Processing, vol. 10, no. 2, pp. 242-251, Feb. 2001.