A Comparative Study of Edge Detection in Noisy Images using BM3D Filter

A Comparative Study of Edge Detection in Noisy Images using BM3D Filter

K. M. Aishwarya1, Ajith Rao A. S.2, Dr. Vipula Singp

Department of Electronics and Communication Engineering,

R. N. Shetty Institute of Technology (RNSIT), Bangalore, India

Abstract Edge detection in noisy images is a bargain between denoising and edge preserving capability. Hence, various smoothing filters are studied in the viewpoint of edge detection too. In this paper, a method for edge detection in noisy images has been discussed which uses BM3D (Block Matching 3D) filter for image denoising. A grayscale noisy image is denoised using Gaussian, Bilateral, Median and BM3D filters for comparison. Then the edge map of the image is obtained by applying edge detection operators like Sobel, Prewitt, Roberts and Cannys and the results are analyzed in all these cases. Further, the noise level is increased and the behavior of BM3D filter is studied in the viewpoint of edge preservability. Results show that the method with BM3D filter performs better than the other methods in comparison for edge detection. The results are quantitatively verified using Pratts figure of merit and Performance Ratio.

KeywordsEdge detection; Image denoising; BM3D filter; Gaussian filter; Median filter; Bilateral filter

1. INTRODUCTION

   Edge detection in image processing and computer vision, involves intensity variations localization of a grey level image and the identification of the physical phenomena that originated them. Information so processed is utilised in many applications like 3D reconstruction, image segmentation and registration, image enhancement and restoration, image compression, and so on. The discontinuities in the physical and photometrical properties of image objects pertaining to edges in an image represent essential information. Variation in reflectance, illumination, orientation, and depth of scene surfaces of an image constitute principal edges. Intensity function is used to represent physical edges in a digital image. Steps, lines and junctions are very common intensity variation functions. Edge detection is usually performed by employing edge detectors. An edge detector accepts discrete, digitized images as input and produces an edge map as output. One very important factor to be kept in mind while performing edge detection is the reduction of noise. Many a time the edge detected image contains noise in it, which gives rise to false edges. Hence it is necessary to preserve the necessary edges and discard the noise factor in an edge detected image. This can be achieved by image filtering or image smoothing. Various denoising filters are used in smoothing the image while preserving the edge.

   In this paper, a method to obtain the best edge map from the noisy images using BM3D filter has been discussed and compared quantitatively with the other filters. This paper

   starts with the discussion of need for a better denoising filter and comments on the previous works in the field of denoising with respect to edge detection, in section II. This is followed by a brief explanation on BM3D filter in section III. Later, in section V, experimental results and observations have been presented. Finally, in section VI, the paper is concluded with the possible future improvements in the method.

2. NEED FOR BETTER FILTERS SHORTCOMINGS OF SMOOTHING FILTERS

   Real life images like satellite images, photographs of nature etc. inherently possess different types of noises (Gaussian, Salt and pepper, Speckle etc.). It is extremely difficult to extract the contours and weak edges of an image in the presence of noise. Processing the artificial noisy images by the traditional approaches like Sobel, Prewitt, and Canny with Gaussian filter yield appropriate results, the real life images with different types of edges give mixed results. Gradient operators react poorly for noisy images [5] [6] [8] [15] [16]. The usual method is to smoothen the image before applying any edge detection operators. This poses a difficulty with the fact that blurring affects the detection of sharp edges negatively. First or second order derivatives of Gaussian kernels are applied by edge detectors. But, both noise and high frequency components are intensified by this method. [14]. One way to address this problem is by varying the scale of the filter.

   Strong filtering successfully removes the noise components, however, compromising with the fine details.

   [7] [10]. Weak filtering preserves the sharp edges with the cost of unsuccessful noise removal. It is shown that the spurious edges become more visible for Gaussian smoothing as the filter scale constant () increases, while authentic edges decrease with . As the is reduced, phantom edges fade away vanishing altogether at equals to 0 [10]. Multi- scale edge detection was the proposed idea [11] to cater this, as it involves smoothing edges with operators of different sizes and scales, then aggregating the outcome for edge map [9]. However, this method came out as cumbersome due to its complexity in determining the scale size, and combining the results for edge map.

   Cannys edge detection method [6] outperforms all the other methods which are based on only gradient operator and thresholding, by involving Non-maximum Suppression and Hysteresis Thresholding. However, due to its sensitivity to weak edges, it detects spurious edges as importantly as authentic edges. When a noisy image is involved, more

   corrupted edge map is obtained due to this. The Gaussian smoothing step involved in the Cannys algorithm fails to smoothen the image to the optimum level for clear edge detection.

   An algorithm based on zero-crossing method proposed by Marr-Hildreth [5] also uses Gaussian smoothing. This performs well only if the edges are well parted. It performs poorly to noisy images and produces false edges [10]. Bergholms [9], Deng and Cahils [12] and many other approaches also [13][17][18] discuss edge detection based on Gaussian filtering. As we discussed earlier, Gaussian filtering has limitations in terms of selecting the scale size, etc. That creates a need for more robust filters for edge detectors.

   Non-linear filters like median filter [19], and bilateral filter [20] are also applied in detecting edges of noisy images

   [21] [22]. Although median filter performs well with certain quantity of noise, it fails to remove the noise when the standard deviation of Gaussian noise increases. It performs better for salt and pepper noise. Bilateral filter does a very good job in preserving the edges when compared to other filters [22]. However, noise removing capability is still not strong as it considers only pixels having intensity difference of more than 50% as noise pixels. [22]. Also, in case of bilateral filter, as the range parameter (r) increases, the bilateral filter becomes closer to Gaussian blur and hence increasing the spatial parameter (d) smooths larger features. Thus, selecting the optimum parameters also adds to the complexity.

   We observe that in order to obtain better results with edge detection of noisy images, a robust, edge preserving filter is required. A lot of work has been done in developing the state- of-the -art filters for smoothing without losing the edges and one such filter is the BM3D filter.

3. BM3D FILTER

   1. BM3D – Theory

      BM3D, which stands for Block Matching and 3-D transform domain filtering, is a denoising algorithm which is considered to be current state-of-the-art as introduced in [1]. In particular, the transform-domain denoising methods typically assume that the truesignal can be well approximated by a linear combination of few basis elements. That is, the signal is sparsely represented in the transform domain. Hence, by preserving the few high-magnitude transform coefficients that convey mostly the true-signal energy and discarding the rest which are mainly due to noise, the true signal can be effectively estimated [1]. The sparsity of the representation depends on both the transform and the true-signals properties. BM3D is a denoising method based on the fact that an image has a locally sparse representation in transform domain. This sparsity is enhanced by grouping similar 2D image patches into 3D groups. The BM3D filter exploits a specific nonlocal image modelling [2] through a procedure termed grouping and collaborative filtering [2]. Grouping finds mutually similar 2-D image blocks and stacks them together in 3-D arrays. Collaborative filtering produces individual estimates of

      all grouped blocks by filtering them jointly, through transform-domain shrinkage of the 3-D arrays (groups). In doing so, BM3D relies both on nonlocal and local characteristics [2] of natural images, namely the abundance of mutually similar patches and that the image data is locally highly correlated. The collaborative filtering algorithm consists of 2 denoising steps:

      • Basic Estimate:

   1. Block-wise estimates: The following are applied to each block in the noisy image:

      1. Grouping: 2D blocks which are similar to the one being processed are stacked together in a 3D array which is called a group [1] [4].

      2. Collaborating Hard Thresholding: 3D transform is applied to the formed group, the noise is attenuated by hard-thresholding of the transform coefficients, the 3D transform is inverted [3] to produce estimates of all grouped blocks, the estimates of the blocks are returned to their original positions.

   2. Aggregation: Computation of basic estimate of the true- image by weighted averaging all of the obtained block- wise estimates that are overlapping. [1]

   • Final Estimate: Improved grouping and collaborative Weiner filtering

   1. Block-wise estimates. For each block, do the following:

      1. Grouping: Use BM within the basic estimate to find the locations of the blocks similar to the currently processed one.

      2. Collaborative Wiener filtering: Apply a 3D transform on both groups. Perform Wiener filtering on the noisy one using the energy spectrum of the basic estimate as the true (pilot) energy spectrum. Apply inverse 3D transform on the filtered coefficients and return the estimates of the blocks to their original positions.[1]

   2. Aggregation: Computation of final estimate of the true- image by aggregating all of the obtained local estimates using a weighted average. [1][3]

4. STEPS FOLLOWED FOR COMPARITIVE ANALYSIS The following steps are implemented in the algorithm:

   1. Input: Additive White Gaussian noise is added to a grayscale image.

   2. Filtering: The image is individually applied to 4 filters: Gaussian, Median, Bilateral and BM3D.

   3. Edge Detection: The denoised images are then separately fed to edge detectors: Sobel, Prewitt Robert and Cannys.

   4. The images are compared with the help of Performance Ratio (PR) and PFOM.

   5. Same method is followed for different noise levels.

      following two parameters for statistical analysis. The analysis is done by comparing the edge images obtained in the experiment with the ground truth image shown in Fig (3). The sample image and the ground truth images are taken from Berkeley segmentation data set.

      1. Performance Ratio:

         PR = [25]

         Figure 1. Block Diagram

5. EXPERIMENTAL EVALUATION AND OBSERVATION

   Additive white Gaussian noise ( = 25) is added to a grayscale image. Then Gaussian, Median, Bilateral and BM3D filters are applied to the noisy image. Edge detection is carried out on these denoised images. Sobel, Robert, Prewitt and Canny operators are applied to obtain the edges. For comparison we have taken the following values for the scale. (BM3D filter: = 25, Gaussian filter: 3*3 matrix, = 0.5, Bilateral: Half size of Gaussian Bilateral Window=3). Edge detected images are compared and evaluated. There are three major types of errors with determination of edge:

   1. Missing valid edge points

   2. Failure to localize edge points

   3. Classification of noise fluctuation as edge points

      To study and minimize the errors, a statistical analysis of the experiment results is a must. We have considered the

      Where,

      True Edges = Edge pixels identified as edge pixels.

      False Edges = Non edge pixels identified as edge pixels and edge pixels identified as non-edges pixels.

      1. Pratts Figure of merit:

         PFOM = [24]

         Where,

         = Actual number of detected edge points

         = Number of edge points on the ideal edge

         = Distance between edge point and ideal edge

         = Scaling constant (here 1)

         The experimental results are tabulated in Table 1&2 for = 25 and SNR = 13.99. The greater the value of PR and PFOM, the better the results.

         Then the noise level is increased by varying sigma from 15 to 55 with an increment of 5 at once without altering the scale of the filter and the corresponding PR & PFOM values are plotted taking SNR values along x-axis. SNR value decreases as the noise level increases. The graphical representation is shown in Figure 5.

         Table 1. Comparison of Performance Ratio (PR) Table 2. Comparison of Pratts Figure of Merit (PFOM)

         PR Values						PFOM Values
         Filters	Canny	Roberts	Prewitt	Sobel		Filters	Canny	Roberts	Prewitt	Sobel
         Bilateral	14.0662	4.2642	7.9261	7.7905		Bilateral	0.0057	0.0138	0.0148	0.0155
         Median	13.2964	5.2863	6.7011	6.5902		Median	0.0056	0.0222	0.0172	0.0169
         Gaussian	13.9850	2.5375	7.0774	6.7992		Gaussian	0.0055	0.0072	0.0156	0.0153
         BM3D	17.6481	8.3386	8.8467	8.7832		BM3D	0.0093	0.0199	0.0178	0.0175

         [SNR Value = 13.9900, = 25] [Noise range () = 15 to 55 (5 increment)]

         The two figures below show the original noisy image and the ground truth image taken into consideration for further denoising and edge detection.

         Figure 2. Original Noisy Image ( = 25) Figure 3. Ground Truth Image

         	Sobel (a)	Roberts (b)	Canny (c)	Prewitt (d)
         BM3D (i)
         Gaussian (ii)
         Median (iii)
         Bilateral (iv)

         Figure 4. Effect of (i) BM3D (ii) Gaussian (iii) Median (iv) Bilateral filters on different Edge Operators

         	PFOM Graphs	PR Graphs
         Sobel
         Roberts
         Canny
         Prewitt

         Figure 5. Graphical Representation of PR and PFOM values. [Red- BM3D; Black- Bilateral; Blue Median; Green- Gaussian]

6. DISCUSSION AND CONCLUSION

From comparing images Fig.(4) qualitatively, it can be noticed that the edge map of noisy images appears more clear in the case of BM3D filtering. Clearly, a better edge map with considerable noise reduction is observed. From Table 1 and 2 we can see that the results obtained from BM3D filtering has much greater PR and PFOM values for all the operators. From this, we can infer that the proposed method with BM3D filter is favourable for edge detection of noisy images.

The results obtained when the noise level is raised as seen in Fig. (4) & (5) determines that the BM3D filtered images outperform the others evidently at the initial stages. However, as the noise level increases the performance decreases to that of median filter or sometimes lower. (Fig 5). From the graphs having PR values, we observe that the performance of BM3D reduces near SNR = 8 to 10. As per the PFOM results, the drop in performance starts roughly around SNR = 12. The results for different operators are obviously different. However, for Canny operator a significant better performance report can be drawn from both PR and PFOM parameters. Also we observe that the BM3D graph is less steep till SNR = 8 to 10 comparatively in Cannys operation. The variations, local minima and maxima in the graphs are attributed to the random value generator used while applying the Gaussian noise. So, it is apparent that the overall trend of the graph should be considered ignoring the small variations. Thus it can be inferred that the edge detection method, with BM3D filter as a denoising filter does a good job in preserving edges while decreasing the effect of noise at the same time.

FUTURE SCOPE

This method works well with the considered specifications of the filters. Future work may take different scales and sizes of the filters in consideration. A method can be devised to resolve the false edges. A modification in the filter itself might help in reducing the false edges.

ACKNOWLEDGMENT

The research was free of monetary demands, and, performed solely for educational and academic purposes. We thank our professors from our esteemed institution, who provided insight and expertise that greatly assisted the research and for providing us a platform to explore and research in depth on the subject.

REFERENCES

1. Kostadin Dabov, Alessandro Foi, Vladimir Katkovnik, and Karen Egiazarian Image denoising by sparse 3D transform-domain collaborative filtering, IEEE Trans. Image Processing, vol. 16, no. 8, (2007), pp. 2080-2095.

2. Kostadin Dabov, Alessandro Foi, Vladimir Katkovnik, and Karen Egiazarian BM3D Image Denoising with Shape-Adaptive Principal Component Analysis, Proc. Workshop on Signal Processing with Adaptive Sparse Structured Representations (SPARS09), Saint- Malo, France, (2009).

3. Li Dai, Yousai Zhang and Yuanjiang Li BM3D Image Denoising Algorithm with Adaptive Distance Hard-threshold, Int.Journal of Signal Process., Image Process. and Pattern Recog., Vol.6, No.6 (2013), pp.41-50.

4. Marc Lebrun, ENS Cachan, France An Analysis and Implementation of the BM3D Image Denoising Method, Published in Image Processing On Line (IPOL) on 2012-08-08, ISSN 2105- 1232.

5. D. Marr and E. Hildreth Theory of edge detection, The Royal Society, online ISSN 1471-2954, Feb 29 (1980).

6. J. Canny, A computational approach to edge detection, IEEE Trans. Pattern Analysis and Machine Intellignece, vol.:PAMI-8, Issue 6 (1986), pp. 679-698.

7. V.Aurichand, J.Weule Non-linear Gaussian filters performing edge preserving diffusion, in Proc. 17th DAGM Symp., New York, 1995, pp.538-545.

8. Juneja .M, Sandhu P.S Performance evaluation of edge detection techniques. for images

9. F. Bergholm, Edge Focusing, IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-9, pp. 726-741, June 1987

10. James J. Clark, Authenticating Edges produced by zero-crossing algorithms, IEEE Trans. Pattern Anal. Machine Intell., vol.11, pp. 43-57, Jan. 1989.

11. B.G Schunck, Edge detection with Gaussian filters at multiple scale, in Proc. IEEE Comp. Soc. Work Comp. Vis., 1987, pp.208- 210.

12. G. Deng and L.W. Cahil,An adaptive Gaussian filter for noise reduction and edge detection, in Proc. IEEE Nucl. Sci. Symp. Med. Im. Conf., 1984, pp. 1615-1619.

13. D.J Williams and M.Shah, Edge contours using multiple scales, Comput. Vis. Graph Image Process., vol. 51, pp. 256-274, 1990.

14. R.C Gonzalez, R.E Woods, Digital image processing, 3rd edition, prentice hall, 2010.

15. M. shin, O.Goldgorf, K. Bowyer, S.Nikiforou, Comparison of edge detection algorithms using a structure from motion task, IEEE Trans. On Systems, Man, and Cyberneticspart B: Cybernetics, vol.31, no.4, August 2001

16. K.W. Bowyer, C.Kranenburg, S. Dougherty, Edge detector evaluation using empirical ROC curves, Compt. Vis. Pattern Recog. (CPVR99), Fort Collins, Colorado, June 1999.

17. V.Lacroix, The primary raster: A multi-resolution image description, in Proc.10th Int. Conf. Pattern Recog.,1990,pp.903 907.

18. R.J Qian and T.S Huang, Optimal edge detection in two dimensional images, in Proc. Image Understanding Workshop,1994, pp. 1581-88.

19. Raymond H. Chan, Chung-Wa Ho, and Mia Nikolova Salt-and Pepper noise removal by median-type noise detectors and detail preserving regularization.

20. C.Tomasi, R.Manduchi, Bilateral filterring for Gray and Color images, in Proc. of the Sixth Int. Conf. on Computer Vision, pages 839846, 1998.

21. Yatendra Kashyap, Anirudh vyas, Rahul Raghuwanshi, Edge detection using sobel method with median filter, Int. Journal of Modern Trends in Engineering and research, vol.2, issue 5.

22. Syed Jahanzeb Hussain Pirzada, Ayesha Siddiqui, Analysis of Edge detection algorithms for feature extraction in Satellite images, in Proc. IEEE IconSpace, July (2013).

23. S. Chabrier, H. Laurent, C. Rosenberger, Y.J. Zhang,"Supervised evaluation of synthetic and real contour segmentation results", European Signal Processing Conference (EUSIPCO) 2006.

24. William K. Pratt, Digital Image Processing, PIKS Inside, Third Edition. William K. Pratt.

25. "A Fuzzy Set Approach for Edge Detection", International Journal of Image Processing (IJIP) , Volume 6, Issue 6, 2012.