Chapter 3 FILTERS - Biomathematics and Statistics …

1 Chapter 3 FILTERSMost images are a ected to some extent bynoise, that is unexplained variation in data:disturbances in image intensity which are either uninterpretable or not of interest. Imageanalysis is often simpli ed if this noise can be ltered out. In an analogous way lters areused in chemistry to free liquids from suspended impurities by passing them through a layerof sand or charcoal. Engineers working in signal processing have extended the meaning of theterm lterto include operations which accentuate features of interest in data. Employingthis broader de nition, image lters may be used to emphasiseedges| that is, boundariesbetween objects or parts of objects in images. FILTERS provide an aid to visual interpretation ofimages, and can also be used as a precursor to further digital processing, such as segmentation( Chapter 4).Most of the methods considered in Chapter 2 operated on each pixel separately. FILTERS changea pixel's value taking into account the values of neighbouring pixels too.

2 They may either beapplied directly to recorded images, such as those in Chapter 1, or after transformation of pixelvalues as discussed in Chapter 2. To take a simple example, Figs (b){(d) show the results ofapplying three lters to the cashmere bres image, which has been redisplayed in Fig (a). Fig (b) is a display of the output from a 5 5moving average lter. Each pixelhas been replaced by the average of pixel values in a 5 5 square, orwindowcentred onthat pixel. The result is to reduce noise in the image, but also to blur the edges of the bres. A similar e ect can be produced by looking at Fig (a) through half-closed eyes. If the output from the moving average lter is subtracted from the original image, on apixel-by-pixel basis, then the result is as shown in Fig (c) (which has been displayedwith the largest negative pixel values shown as black and the largest positive pixel val-ues shown as white). This lter (the original image minus its smoothed version) is aLaplacian lter.}

3 It has had the e ect of emphasising edges in the image. Fig (d) shows the result produced when output from the Laplacian lter is added tothe original image, again on a pixel-by-pixel basis. To the eye, this image looks clearerthan Fig (a) because transitions at edges have been magni ed | an e ect known asunsharp 3. FILTERSWe will consider these three lters in more detail above lters are alllinear, because output values are linear combinations of the pixels inthe original image. Linear methods are far more amenable to mathematical analysis than arenonlinear ones, and are consequently far better understood. For example, if a linear lter isapplied to the output from another linear lter, then the result is a third linear lter. Also, theresult would be the same if the order in which the two lters were applied was reversed. Thereare two, complementary, ways of studying linear lters, namely in thespatialandfrequencydomains.

4 These approaches are considered respectively. The less mathematicalreader may prefer to This can be done without losing the sense of the rest of lters| that is, all lters which are not linear | are more diverse and di cultto categorize, and are still an active area of research. They are potentially more powerful thanlinear lters because they are able to reduce noise levels without simultaneously blurring , their theoretical foundations are far less secure and they can produce features whichare entirely spurious. Therefore care must be taken in using them. , some nonlinearsmoothing lters are considered, and , nonlinear edge-detection lters are , the key points of the Chapter are summarized Linear lters in the spatial domainThe moving average, orbox lter, which produced Fig (b) is the simplest of all replaces each pixel by the average of pixel values in a square centred at that pixel. Alllinear lters work in the same way except that, instead of forming a simple average, a weightedaverage is formed.

5 Using the terminology of Chapter 1, letfij;fori; j=1;:::;n, denote thepixel values in the image. We will useg, with pixel valuesgij, to denote the output from the lter. A linear lter of size (2m+1) (2m+1), with speci ed weightswklfork; l= m;:::;m,givesgij=mXk= mmXl= mwklfi+k;j+lfori; j=(m+1);:::;(n m):For example, ifm= 1, then the window over which averaging is carried out is 3 3, andgij=w 1; 1fi 1;j 1+w 1;0fi 1;j+w 1;1fi 1;j+1+w0; 1fi;j 1+w0;0fi;j+w0;1fi;j+1+w1; 1fi+1;j 1+w1;0fi+1;j+w1;1fi+1;j+ full generality, the weights (w) can depend oniandj, resulting in a lter which varies acrossthe image. However, the linear lters considered in this Chapter will all be spatially , all the lters will have windows composed of odd numbers of rows and columns. It ispossible to have even-sized windows, but then there is a half-pixel displacement between theinput and output LINEAR FILTERS IN THE SPATIAL DOMAIN3(a)(b)(c)(d)Figure : Application of linear lters to cashmere image:(a)original image,(b)output from5 5 moving average lter,(c)result of subtracting output of 5 5 moving average lter fromoriginal image,(d)result of adding original image to the di erence between the output from5 5 moving average lter and the original 3.

6 FILTERSNote that thebordersofg, that isgijwhere eitheriorj=1;:::;mor (n m+1);:::;n;have not been de ned above. Various possibilities exist for dealing with them:1. They could be discarded, resulting ingbeing smaller The pixels in the borders ofgcould be assigned the same values as those in the The border pixels ingcould be set to The lter could be modi ed to handle incomplete neighbourhoods, for example:(a) by ignoring those parts of the neighbourhood which lie outside the image,(b) by re ecting the input image (f) along its rst and last row and column, so thatpixel valuesfi;n+1=fi;n 1etc,(c) by wrapping-round the input image so thatfi;n+1=fi;1etc, as though it were on this Chapter we will take option 2 for smoothing lters and option 3 for edge-detection lters, except where we will make use of option 4(c). Strictly speaking, this wrap-roundapproach is the only valid option for the mathematical results on linear lters to be applicableover the whole all the elements inwarepositive, then the e ect of the lter is to smooth the image.

7 Thetwo most commonly-used lters of this type, the moving average and the Gaussian, will beconsidered If some weights arenegative, then the lter outputs a di erence betweenpixel values, which can have the e ect of emphasising edges. FILTERS of this type will be SmoothingFor the moving average lter,wkl=1=(2m+1)2. Figs (a), (c) and (e) show the results ofapplying moving average lters with windows of size 3 3, 5 5 and 9 9 to the transformed X-ray image in Fig (b). As can be seen, the bigger the window the greater the noise reductionand e ciency is an important consideration in image analysis because of the sizeof data sets. In total, there are (2m+1)2additions and multiplications per pixel involved inderivinggfromf. However, some lters can be computed more quickly. A lter is said to beseparableif it can be performed by rst ltering the image inside a (2m+1) 1 window, andthen inside a 1 (2m+1) window. In other words, it can be separated into a column operation:hij=mXk= mwckfi+k;jfori=(m+1);:::;(n m);j=1;:::;n; LINEAR FILTERS IN THE SPATIAL DOMAIN5(a)(b)(c)(d)(e)(f)Figure : Linear smoothing lters applied to X-ray image:(a)3 3 moving average,(b)Gaussian, 2=23,(c)5 5 moving average,(d)Gaussian, 2=2,(e)9 9 moving average,(f)Gaussian, 2= 3.

8 FILTERS using column weightswc m;:::;wcm, followed by a row operation:gij=mXl= mwrlhi;j+lfori; j=(m+1);:::;(n m);using row weightswr m;:::;wrm. In order for this to be possible, the array of weights,wkl, mustbe expressible as the product of the column and row weights, as follows:wkl=wckwrlfork; l= m;:::;m:The number of operations per pixel has been reduced from (2m+1)2to 2(2m+ 1). Thereforea separable lter can be computed more quickly than one that is not separable, even whenm= the moving-average lter is separable (withwck=wrl=1=(2m+ 1)), there exists ayet more e cient algorithm. This uses arecursiveimplementation, that is, one in which theoutput from the lter at location (i; j) is updated to obtain the output at location (i+1;j).In contrast, the formulae we have considered so far involve calculating from scratch the outputat each location. Speci cally, the rst (2m+ 1) pixel values in columnjare averaged:hm+1;j=12m+12m+1Xk=1fkj:Then, the pixel value in the rst row (f1j) is dropped from the average and the pixel in row(2m+ 2) is added.

9 This operation is repeated for every value in columnj, so that:hij=hi 1;j+fi+m;j fi m 1;j2m+1fori=(m+2);:::;(n m):This procedure is repeated for each columnj=1;:::;n, to obtainh. Then the same algorithmis applied along each row ofh, to obtaing. The number of operations per pixel has beenreduced to 4irrespective of the lter size(m).Table gives times for the general, separable and moving average algorithms consideredabove, implemented in a Fortran77 program to run on a SUN Sparc2 computer. (Timings for lters to be discussed later in the Chapter are also included.) Separable and, in particular,moving average lters run much more quickly than the general linear lter, particularly whenimage and window sizes are the moving average lter is simple and fast, it has two drawbacks:1. It is notisotropic( circularly symmetric), but smooths further along diagonals thanalong rows and Weights have an abrupt cut-o rather than decaying gradually to zero, which leavesdiscontinuities in the smoothed introduced by the square window can be seen in Fig (e), particularly aroundthe sheep's backbone.

10 Drawback 1 could be overcome by calculating the average in a LINEAR FILTERS IN THE SPATIAL DOMAIN7approximation to a circular, rather than a square, neighbourhood. Such a lter with constantweights would not be separable, but could be implemented reasonably e ciently using a 2-Dversion of the recursive ltersare the only ones which are separable and, at least to a lattice approximation,circularly symmetric. They also overcome the other stated drawback of moving average ltersbecause weights decay to zero. Gaussian lters have weights speci ed by the probability densityfunction of a bivariate Gaussian, or Normal, distribution with variance 2, that iswij=12 2exp( (i2+j2)2 2)fori; j= [3 ];:::;[3 ];for some speci ed positive value for 2. Here `exp' denotes the exponential function and [3 ]represents the `integer part' of 3 . Limits of 3 are chosen because Gaussian weights arenegligibly small beyond them. Note, that the divisor of 2 2ensures that the weights sum tounity (approximately), which is a common convention with smoothing lters.