Adaptive Filter Based on Image Region Characteristics for Optimal Edge Detection

Adaptive Filter Based on Image Region Characteristics for Optimal Edge Detection Lussiana ETP, Yuhilza Hanum Sarifuddin Madenda Faculty of Computer Science and Information Technology Gunadarma University, Jakarta, Indonesia {ussie, yuhilza}@staff.gunadarma.ac.id Département d’Informatique et d’Ingénierie UQO, Québec, Canada m.sarifuddin@uqo.ca Abstract A number of edge detection filters developed recently have included a parameter to reduce noise in an image. Noise reduction depends on the parameter value keyed-in by an operator. Therefore, the detected edge relies on the accuracy of the operator in determining the parameter value. The parameter is also used to reduce noise in the image as a whole. The resulted edge is not optimal, since each region of the image doesn’t have the same noise disturbance as others. This paper describe the development of adaptive edge detection method based on image region characteristics. Filter’s parameter is determined automatically for every region according to its noise and blur characters. In other words, filter parameter becomes more adaptive based on image region characteristics. The result of the experiment shows that the adaptive method developed in this paper is more optimal than the previous methods. 1. Introduction Image processing has been applied in many fields, such as medicine, photography, military, and geophysics. One of the essential steps in image processing is edge detection. Determining an image’s edge is not easy. It relies on the image’s condition. An image’s edge can be easily detected if there’s no noise. The problem resulted from the existence of noise is error or inaccuracy in determining the edge. Errors in following analysis processes will be therefore possible. Addressing this problem, a number of methods has been developed, such as Canny edge detector [1], Deriche filter [2], Bourennane [3], and Laggoune [4]. Every edge detecting filter and operator uses one noise parameter and apllies it to reduce noise in the overall image. According to Madenda [5], image as a result of acquisition has a variety of characteristics (i.e., sharp, blurred, noisy) and differs from one region to another in the same image. Based on this fact, Madenda developed an edge detecting filter by adding one more parameter, i.e., blur parameter. Operationally, this filter needs two inputs, noise and blur parameters, and applied to the whole image. From the description of the above methods, it can be concluded that the accuracy of the operator determines the accuracy of edge detection result. It is highly possible that the parameter values don’t fit with the image’s condition. Therefore, the result is inaccurate and influenced further analysis. Furthermore, the use of one parameter on the whole image may result in disappearance of the edge since noise reduction doesn’t confirm with the image region characteristics. Conclusively, it is essential to develop edge detection method based on image region characteristics, where the filter parameters can be determined automatically and adaptively according to the image region characteristics. This is the main topic of this paper. 2. Edge detection method Basically, an edge can be defined as a boundary between two regions (two adjacent pixels) that have sharp (high) intensity difference [7]. On the other hand, according to [5], this definition doesn't fully hold in the case of blur effect on the edges. This effect may result in sloped change at the boundary. The previous definition doesn't fully hold for noisy boundaries either. Since noise intensity is random, its existence results in the appearance of other edges around the original edge and may shift the real edge position. 2008 IEEE International Conference on Signal Image Technology and Internet Based Systems 978-0-7695-3493-0/08 $25.00 © 2008 IEEE DOI 307 2008 IEEE International Conference on Signal Image Technology and Internet Based Systems 978-0-7695-3493-0/08 $25.00 © 2008 IEEE DOI 307 2008 IEEE International Conference on Signal Image Technology and Internet Based Systems 978-0-7695-3493-0/08 $25.00 © 2008 IEEE DOI 10.1109/SITIS.2008.78 307 2008 IEEE International Conference on Signal Image Technology and Internet Based Systems 978-0-7695-3493-0/08 $25.00 © 2008 IEEE DOI 10.1109/SITIS.2008.78 307 Authorized licensed use limited to: Xi'an University of Technology. Downloaded on March 15, 2009 at 01:47 from IEEE Xplore. Restrictions apply. Image Regionization smoothing Edge detection Input image Output image In 1986, John Canny [1] proposed three criteria as basis for developing the filter which optimize edge detection of noisy images. The three criteria are: 1. Good detection. The objective is to maximize the value of signal to noise ratio (SNR) in order to well detect all edges and none is missing. 2. Good localisation. The detected edge is in the correct position, that is, the distance between the detected edge's position and the real position is minimum. (ideally = 0). 3. Low multiplicity of the response or ”one response to single edge”. The detector doesn't produce edges that are not the real ones Canny succeeded in optimizing these three criteria and produced equation (1), but it is difficult to implement. )sin( 4 )cos( 3 )sin( 2 )cos( 1 )( xxeaxxeaxxeaxxeaxh ωαωαωαωα −+−++= (1) so that Canny still used Gaussian filter to reduce noise and continued to compute the first derivative and thresholding hysteresis. Deriche used step-shaped edge model [2] and the three Canny criteria to develop a smoothing filter as well as a detecting filter, which become the final solution of Deriche and the answer to Canny's problem. The smoothing h(x) and detecting h’(x) filter are shown by equation (2) and (3) respectively: x exkxh α α − += )1()( , )221( 2)1( ααα α − − −+ − − = ee ek (2) x xekxh α− −= ')(' , α α − − − = e ek 2)1(' (3) k: normalization constant, k’: normalization constant, and α: noise parameter. Numerical implementation of this filter can be done by Z transformation In response to the development of filtering method, and to face the problems of filtering effects, in 2006, Madenda et. al conducted some research about image information contents, especially the edge characteristics of an image. Madenda [5] concluded that an image mainly has regions with different characteristics, i.e, blurred, sharp, and noisy. This means that the development of an edge detecting filter has to consider noise level and blurred level of the detected edge. Based on this consideration, a blurred crest-line edge modelling is developed mathematically, which is given by the following equation: ))cos( )sin( ()( x x KexC x αββ αβλα −+= − (4) There exist parameters α and β in the equation, where 0<β<1 is the blur parameter, and α>0 is the noise parameter, while K and λ are normalization factors. The caharacteristics of parameter α are the same as parameter α in Canny and Deriche filters. The value of parameter β With the assumption that this model is able to represent an is small (approaching zero) for low blur level and larger (approaching one) for high blur level. image’s edge for the three characteristics, blurred, sharp, and noisy, the edge can be determined by using its first derivative: ))sin()1()cos(2()()( 2 xxeK x xCxf x αββ β αβλα α −+−−= ∂ ∂ = − (5) where f(x) represent an image’s edge detecting filter, which in practice, an edge is the product of the convolution between filter f(x) with the image itself or the smoothed one. By applying boundary condition that must be fulfilled by a detector filter, equation (6) is obtained: ))sin( 2 )1)cos(1()sgn()( 2 1 xxeKxxf x αββ β αβα −+−−= − (6) However, the weakness of all methods developed so far is filter application (with one noise parameter value and one blur parameter value) to the whole image. This has a bad result in a noiseless image region or one with lower noise level than the others. Another risky thing is manually determined parameter value which is based on operator’s intuition, The result is different noise parameter from one operator to another for the same noise level. This is done repetitively if the parameter value is not yet satisfactory. 3. Proposed method To address the problems mentioned above, this paper proposes a development of image’s edge detection optimized method based on optimal filter [5-6]. This method begins with region characteristics analysis by segmenting the image by its noise and blur level, followed by the determination of noise and blur level according to noise and blur content of the region. The next step is region edge detection using noise and blur parameter that confirms with the image region characteristics. The proposed image’s edge detection method process can be illustrated as shown in Figure 1: Figure 1. The development of an image’s edge detection method Detailed regionization process is illustrated in Figure 2: 308308308308 Authorized licensed use limited to: Xi'an University of Technology. Downloaded on March 15, 2009 at 01:47 from IEEE Xplore. Restrictions apply. Figure 2. Detailed regionization process 3.1. Image region segmentation The regionization process starts with image region segmentation. This process divides the image region into four smaller regions. This is done by dividing the image into two parts, horizontally and vertically. 3.2. Entropy and contrast calculation After the segmentation, the next step is calculating the random level of data in a region that is related to the noise level. Contrast value is also calculated, which is connected to the blur level. Grey level intensity value is represented by zk, so that the probability of a grey level value can be represented by (7) [8]: n n zp kk =)( , 10 ≤≤ kz , and 1,..,1,0 −= Lk (7) where p(zk) is the probability of k-th grey level, nk is the frequency of grey level, n is the total number of pixels in the image, and L = 2nb , where nb = the number of bits per pixel. If there exists a random intensity value in an image, the image entropy can be calculated. Entropy is a representation of randomness in an image, which can be calculated by using equation (8): ∑− = −= 1 0 2 )(log)( L k kk zpzpe (8) While contrast is calculated based on image moment 2nd order, by [7]: ∑− = −= 1 0 )()( L k k n kn zpmzμ (9) 2μ=contrast for n=2, (10) ∑− = = 1 0 )( L k kk zpzm (11) where m is the intensity average. 3.3. Validating and forming region and binary tree The validation process is the process of dividing image/region into four smaller regions, and the process of evaluating characteristics difference levels of the four regions. Examination is conducted by calculating the difference of entropy and contrast value of one region to the other. If there exist regions with significantly different entropy and contrast values, the segmentation process (into 4 parts) is validated. This process is repeated for every region until a certain region size is reached. The validating process is not conducted if the differences are not significant (the four regions have similar characteristics). In order to make analysis and exploration of image’s regions easier, this research adopted Depth First Search method of binary tree [9]. Hence, every validation of four regions will be stored and registered in four branches of a binary tree. New region partition process is conducted by searching every formed branches. The determination of region partition validation follows the condition of: Actual region size ? ≥ referenced region size & ThEE ? minmax <− where Emax: maximum entropy value of the four actual analyzed region, Emin: minimum entropy value of the four actual analyzed region, Th : threshold value, which is determined at calibration (Th = 0.23), Actual region size : the size of the explored region, Referenced region size: smallest region size. If actual region size < referenced region size and the difference in entropy is less than Th, the region partition is stopped (not validated), on the other hand, if actual region size ≥ referenced region size and the difference in entropy is larger than or equal to Th, the region divided again into four sub regions (region partition validated). The process is repeated until one of the two conditions is not fulfilled. After all region partition with the same characteristics is formed, the method continues with parameter calculation. 3.4. Parameter calculation for every region To determine the relationship of noise parameter and noise level in an image, a test is conducted on a variety of images by its noise level changes. An experiment is done by giving different noise levels to the test image. Gaussian noise is used in this research. Figure 3 shows the graphic resulted from relationship experiment between entropy level and noise level of an image. Image Region Segmentation Calculation of parameter α and β for every i Entropy and contrast calculation Validating and Forming region and binary tree i 309309309309 Authorized licensed use limited to: Xi'an University of Technology. Downloaded on March 15, 2009 at 01:47 from IEEE Xplore. Restrictions apply. Figure 3. Average entropy graph Figure 3 shows that the change in entropy value can be seen clearly for low noise level, while for high noise level, the change is not significant. Therefore, the chart can be divided into 3 groups of noise level that corresponds to noise parameter, i. e.: • Group I : for noise level of 0-20 • Group II : for noise level of 20-45 • Group III : for noise level of higher than 45 (noise level > 45) Based on noise level characteristics and their division, and referring to noise parameter characteristics of optimal filter which has been well tested experimentally and theoretically, the relationship between noise parameter (α) and entropy value is as follows: Group I : )25.4(7525.065.0 regE−+=α Group II : )09.5(2381.045.0 regE−+=α Group III : )39.5(3327.035.0 regE−+=α where Ereg: entropy value of a certain region An experiment to determine the relationship between blur parameter and contrast value of an image has also been done (see figure 4). Figure 4. Contrast level vs the change in blur level Figure 4 shows that for contrast value of < 2.75, the relationship between blur parameter and contrast value is almost linear, so that mathematically this chart can be represented by the equation: )75.2(3089.0056.0 −−= reg Kβ where Kreg is the contrast value of a certain region. 4. Results and analysis We implemented the adaptive algorithm and taken several experiments using several images including the image of Lena. Figure 5 shows the original image of Lena (512x512 pixels) that has sharp, blurred, and noisy characteristics. Figure 6 shows an example of the segmentation result of level 1 binary tree with smallest region size is 256x256 pixels. Figure 5. Original image Figure 6. Segmentation result of level 1 binary tree with smallest region size is 256x256 pixels Average entropy graphic 0 1 2 3 4 5 6 0 1 3 4 6 7 9 10 12 Noise Level E n t r O p y A v e r a g e E n t r o p y C o n t r a s t Contrast Vs Blur Level Blur Level 01 02 03 04 310310310310 Authorized licensed use limited to: Xi'an University of Technology. Downloaded on March 15, 2009 at 01:47 from IEEE Xplore. Restrictions apply. Table 1 represents the values of parameters α and β for each region of figure 6, while figure 7 shows the edges of figure 6 by applying Madenda filter and parameters α and β per region. Tabel 1. Calculation result of parameters α and β Region Ereg Kreg α β (01) 2.2510 11.4322 3.112 0.0488 (02) 3.0078 16.4568 1.5847 0.75 (03) 2.2428 4.34127 3.1376 0.0842 (04) 2.1182 12.13277 3.5538 0.0453 Figure 7. Edge detection result with smallest region of 256x256 pixels Figure 7 shows that the image’s noise is clearly detected. This explains that a minimum of 256x256 pixels region has a high probability of inability to show unique characteristics, or still have some characteristics. This is further explained in Table 1, which shows a difference in Ereg >Th (Emax-Emin>Th). After some observations, it is concluded that optimal detection will be obtained in smallest of 8x8 pixels region. Figure 8 shows image regions which are formed as segmentation result of level 6 binary tree with smallest region of 8x8 pixels. It can be seen that every formed region has more homogenous character compared to the one in Figure 6. Figure 8. Segmentation result of level 6 binary tree with smallest region of 8x8 pixels Figure 9. Using proposed method Figure 9 shows the edge detection result of the image in Figure 8. This is a much better result than the one in Figure 7, with the disappearance of the noise. To see the performance of the adaptive method developed in this paper, the result is compared with edge detection results of Canny, Deriche, and Madenda filters. The result of edge detection of Lena image by using Canny, Deriche, and Madenda filters, are: 311311311311 Authorized licensed use limited to: Xi'an University of Technology. Downloaded on March 15, 2009 at 01:47 from IEEE Xplore. Restrictions apply. Figure 10. Using Canny filter, σ =1.5 Figure 11. Using Deriche filter, α= 0.75 Figure 12. Using Madenda filter α= 0.75, β= 0.75 Figure 10 is the result of edge detection by Canny filter. This figure shows that noise is well filtered, but some edges are not well detected, such as an edge at the top part of the picture (the hat) and on the hair part. The missing edge is a result of the use of one parameter value for the whole image region without considering the difference in characteristics. Figure 11 is an image resulted from edge detection by Deriche filter. The figure shows undetected edges that also resulted from the use of one parameter value for the whole image region. Figure 12 is the result of edge detection by using Madenda filter. The resulted edges have stronger blur character compared to the one resulted from Canny filter. Edges in noisy region are also well detected. Nevertheless, there are still exist edges that are not well detected, such as the hat line. This shows that the existence of blur parameter results in sharper detection, while the use of one noise parameter for the whole image region still results in missing image edges. The edges in Figure 9, which are the result of the proposed method show that this method is better than the previous method (using Canny, Deriche or Madenda filter). In blurred image regions, edges are well detected. The same goes for noisy regions. In the parts of hairs and hat, some unseen edges in Figures 10, 11, and 12. 5. Conclusions Based on the test on blurred, sharp, and noisy image, the proposed method gives more optimized results compared to common filtering methods (the use of one parameter value for the whole image region). Another advantage of this metho