Radiol Oncol 1995 ; 29: 58-64. Edge-enhancement performance of the histogram shifting filter Biagio Gino Fallone and lan Crooks Depts. of Radiation Oncology and Diagnostic Radiology and The Medical Physics Unit, McGill University, Montreal General Hospital, 1650 Cedar Ave., Montral, Canada, H3G 1A4 A quantitative evaluation of the edge-enhancement properties of the histogram shifting (HS) filter is presented, and compared to more common edge-enhancers such as linear high-pass, unsharp masking, homomorphic and statistical differencing filters. Parameters related to noise and edge levels were calculated from simulated noise-free and noisy test images to determine the relative merits of the various filters. The HS edge-enhancer tends to change the relative intensities of the upper and lower level of an edge which may cause difficulties when absolute intensity levels are required. However, the HS filter appears to offer good edge enhancement with the lowest noise amplification when compared to results of other filters, and may thus be very beneficiat in practical situations where, in general, noise amplification is not desired. Key words: radiographic image enhancement; filter comparison, image processing, algorithm performance Introduction Various forms of image enhancement techniques exist to improve the visual appearance of a medical image. Edge enhancement is one of these forms and accentuates edges of an image to make it more subjectively pleasing to the human eye.1 These edge-enhancers may include linear high-pass filters,2 3 unsharp masking,4 5 homomorphic filtering6 and statistical differencing7' 8 techniques. We have recently developed Correspondence to: B.G. Fallone, Ph.D., FCCPM, Dept. of Radiation Oncology and Diagnostic Radiology and The Medical Physics Unit, McGill University, Montreal General Hospital, 1650 Cedar Ave., Montreal, Canada, H3G 1A4. UDC: 616-073.755.2 an algorithm which we have labeled histogram shifting (HS) that is capable of edge-detection or edge-enhancement depending on the value of a parameter. 9 In this paper, we will quantitatively evaluate the HS algorithm as an edge-enhancer by comparing its performance with that of the other four edge-enhancers mentioned above. Materials and methods The test images were generated by a "C" program we wrote on a Silicon Graphics Incorporated (Mountain View, Calif. 940939-7311) 4D20 Personal Iris workstation (SGI). We also wrote the high-pass, HS, unsharp masking, statistical differencing and the homomorphic filtering algorithms in "C" on the SGI. Clinical Edge-enhancement performance of the histogram .shifting filter 59 radiographs were entered into a 386 PC by a VDC3874 (Sanyo Electric Inc., Japan) video camera connected to a Matrox (Montreal, Canada) IM 1280 video digitizer and transferred to the SGI via Ethernet. All images were 256 x 256 by 8 bits, and filter kernel sizes were all 3 X 3. Edge enhancement algorithms The histogram shifting algorithm was compared to a number of existing edge enhancement algorithms presently used for image processing purposes. As mentioned, these include three kernel-based linear high-pass filters, unsharp masking, statistical differencing, and the homo-morphic filters using the previously-mentioned high-pass kernels. A brief overview of the filters studied follows. Histogram shifting in accomplished by subtracting a fraction, f, of the minimum pixel value of a neighbourhood around each pixel as follows: XU = Xkrfmin (X,v)] (1) where X',/ is the new grey level of the pixel located at k,! in the image, Xk,/ is the original value of the pixel located at k,! in the image, and min (X;) is the minimum of the pixel values located at i,j in the neighbourhood surrounding the target pixel. The factor, J controls the amount the histogram local to each pixel is shifted towards the zero value. When f = l.O, the histogram will be shifted such that the minimum value is zero and edge-detection will be produced. The HS algorithm for f = 1.0 should then be compared to well known edge-detectors, such as Laplacian and Sobel filters. In this case, however, the HS filter is basically equivalent to the erosion-residue morphological edge detector. IO As the value of f is lowered towards zero, edge enhancement will result with lessor degrees of enhancement. In this study, we present images processed with f = 0.9, 0.7, and 0.5 labeled HS 0.9, HS 0.7, and HS 0.5, respective- ly, to represent the useful range of enhancement prodeced by this algorithm. Three conventional linear high-pass kernels of the following forms: HPl = HP3 = O -1 O -1 5 -1 0 -1 O " l -2 1' --2 5 --2 1 -2 1 HP2 = -1 -l -1 -1 9 -1 -1 -1 -1 (2) were evaluated. We also implemented the above kernels (Eq. 2) in a homomorphic fashion by taking the logarithm of the pixel values before applying the kernels and then taking the inverse logarithm of the result. The homomorphic filters are labeled HMl, HM2 and HM3 corresponding to the kernels PHl, HP2 and HP3, respectively. Unsharp masking is a non-linear edge enhancement technique in which a blurred version of the image is subtracted from the original image itself as follows: 11 Xk.i — - 2c-l -X l- k,t 2 c -/ X' k,t (3) where c is a weighting factor typically between 0.6 and 0.8 and X^/ is the value of the pixel located at k,l in the blurred image. For this study, we used a 3 X 3 averaging kernel to blur the image and values for c of 0.8, 0.7, and 0.6, labeled UM 0.8, UM 0.7 and UM 0.6, respectively. Statistical differencing7' 8 is a method of edge enhancement which modifies each pixel value according to the mean and standard deviation of the neighbouring pixels. We have implemented this technique as follows: X'A-./ — [X1cr(Xk.,)] a ,,Sk!-Sd a,i,Sd + r=.=Xu (4) where (Xk/) and Sk,/ are the mean and standard deviation of the values of the pixels in a neigh- 60 Fallone B G and Crooks I bourhood centered at k,l in the image, a is a factor between O.O and 1.0 controlling the degree of edge enhancement, Sd is a factor representing the desired standard deviation of the resulting image, and r is a scaling factor between O.O and 1.0 which varies the degree of contribution of the original image to the processed image. We designed statistical differencing filters with a r of 0.5, an Sd of 85 with an a of 0.1, 0.5 and 0.8 labeled SD 0.1, SD 0.5 and SD 0.8, respectively. Method of analysis To analyse the performance of the edge enhancement algorithms is a quantitative manner, we applied two test to images processed by the algorithms. The algorithms were applied to two dimensional step images. The step images were obtained by dividing each test image into two equal-sized sections, one section with uniform low pixel values and the other with uniform high pixel values. The low pixel value in all our test images was 50, while the high pixel value was either 75, 100 or 150. This resulted in three test images with steps from 50 to 100 (50-100), 50 to 75 (50-75), and 50 to 150 (450-150) pixel values, respectively. We only show results obtained with test images of steps 50-100 pixel values, but the results are very similar for the other step values. The step images were corrupted by Gaussian in one set of studies, and uniformly distributed additive noise in another set of studies. The Gaussian noise had a zero mean and a variance of 96 while the uniformly distributed noise had a zero mean and a variance of 123. For the first test, we measured the increase in noise induced by the enhancement process by determining the mean Yf, Yf, and standard deviation of the pixel values within a 50-pixel square region of interest in the "low" and "high" regions of the step images (Figure 1), respectively. The subscripts l and h correspond to the "low" and "high" regions, respectively. Each of the square regions are 235 pixels from the edge. The value of the standard devia- tion indicates the degree of noise amplification within the image caused by the enhancement process. In the second test, we calculated the degree of edge enhancement by the algorithm in the following manner. The mean of 50-pixel values, Zet, Z eh along a one-pixel thick linear region at the top and bottom of the edge (see Figure 1), respectively were found, and a figure of merit M describing the degree of edge enhancement was calculated: M ■■ _(Zet- Zeb) ' (Yh-Y) (5) The figure of merit is the ratio of the edge height to the step height and indicates the amount of overshoot at the edge caused by the algorithm. A larger value of M indicates increased overshoot which implies that the edges are more pronounced. Results and discussion A. Noise-free images Results of our calculation are shown in Tables 1 to 3. In Table 1, which represents a step without noise, the a/ and a;, are all zeroes, and M = l for the original unprocessed image. The HP, UM and HM algorithms do not change the values of Yi and Yf, except for the slight changes produced by UM 0.7 ( Y/, from 50 to 49; and Y,„ from 100 to 99) . The SD algorithm x. xh low region high region Figure l. Schematic of the step edge profile with a pictorial definition of the parameters discussed in the text. Edge-enhancement performance of the histogram .shifting filter 61 Table l. Results of calculation of the quantitation parameters for a noise-free image composed of a step. The step function is comprised of values of 50 to values of 100. Algorithm Yi O/ M original 50.00 0.00 100.00 0.00 1.00 HS0.5 25.00 0.00 50.00 0.00 2.00 HS0.7 15.00 0.00 30.00 0.00 3.33 HS0.9 5.00 0.00 10.00 0.00 10.00 HPl 50.00 0.00 100.00 0.00 3.00 HP2 50.00 0.00 100.00 0.00 5.00 HP3 50.00 0.00 100.00 0.00 1.00 UM0.8 50.00 0.00 100.00 0.00 1.22 UM0.7 49.00 0.00 99.00 0.00 1.50 UM0.6 50.00 0.00 100.00 0.00 2.30 MHl 50.00 0.00 100.00 0.00 3.57 MH2 50.00 0.00 100.00 0.00 5.08 MH3 50.00 0.00 100.00 0.00 1.00 SD 0.1 25.00 0.00 50.00 0.00 10.20 SD 0.5 25.00 0.00 50.00 0.00 4.80 SD0.8 25.00 0.00 50.00 0.00 4.28 Table 2. Results of calculation of the quantitation parameters for a step image with Gaussian noise. The step function is comprised of values of 50 to values of 100. Algorithm Yi O/ ~Yh o1, M original 49.13 94,36 99.63 94.02 0.97 HS0.5 31.38 91.80 56.85 82.19 1.82 HS0.7 22.44 95.29 39.66 96.07 2.93 HS0.9 1.7.36 100.85 22.64 102.48 8.21 HPl 54.11 1997.39 100.26 2615.39 2.78 HP2 65.85 4708.23 104.05 6055.23 5.32 HP3 57.74 2719.52 101.40 3739.26 1.05 UM0.8 49.23 158.43 99.37 158.27 1.18 UM0.7 49.37 268.22 99.45 270.11 1.44 UM0.6 50.66 714.33 100.56 764.96 2.17 MHl 75.43 4580.86 112.62 3061.84 4.16 MH2 99.24 9107.73 124.25 6613.41 8.18 MH3 82.68 6484.45 116.44 4347.08 1.22 SDO.l 57.39 4970.33 74.43 5841.47 12.19 SD0.5 29.86 775.10 51.93 993.48 5.86 SD0.8 27.83 540.0 50.90 674.53 5.09 Table 3. Results of calculation of the quantitation parameters for a step image with white i noise (uniformly distributed). The step function is comprised of values of 50 to values of 100. Algorithm Yi 0/ Yh 01, M original 49.37 126.14 99.65 124.99 0.96 HS0.5 32.13 120.07 57.43 121.47 1.81 HS0.7 25.16 119.38 40.34 121.98 2.92 HS0.9 18.48 120.12 23.62 123.58 8.43 HPl 56.29 2519.58 100.13 3570.09 2.73 HP2 72.34 5753.50 107.20 7862.34 5.36 HP3 60.89 3526.19 102.54 5009.62 1.00 UM0.8 49.08 208.77 99.36 209.87 1.16 UM0.7 49.25 349.93 99.43 356.38 1.43 UM0.6 50.38 947.19 100.43 1007.41 2.09 HIM 1 83.50 6207.03 116.73 4234.16 4.08 HM2 107.88 11038.52 128.32 8250.66 9.77 HM3 90.39 8325.30 120.31 5657.07 1.14 SD 0.1 67.27 6230.23 82.16 7558.15 12.42 SD0.5 32.52 1035.39 52.77 1493.46 6.31 SD0.8 29.66 750.62 51.21 1069.39 5.50 62 Fallone B G and Crooks I halves the values of both Y/ and Y¡„ while the HS algorithms significantly decreases Y1 and Y/, as the shifting factor f approaches the value of 1 when the HS algorithm can be considered a strict edge detector. Except for HP3 and HM3, all algorithms show an increase in the figure of merit M with respect to the unprocessed image. The HP and its related HM filter show virtually identical increase in M. There is marginal increase in M for the UM filters, although greater increase would perhaps have been noted if a weighting factor of c < 0.6 would have been used. However, a c of 0.6 is the smallest value commonly used in unsharp masking. The remaining filters, SD and HS show possibilities of producing the greatest edge enhancements with the largest figure of merit (i.e., MHSo.9 - Msvo. i -10). Both these filters achieve this figure of merit by keeping constant at least the relative values of Yi and Y/,. One should note, however, that the absolute values of Y1 and Y/, at which this figure of merit is achieved are much lower in the HS algorithm than they are in the SD algorithm. B. Noisy images We can see from Tables 2 and 3 that results with a noisy image are quite different, although whether that noise is Gaussian or white does not appear to significantly effect the performance of the algorithms. As expected, the standard deviations ol and a1, of the original and the processed images have significantly increased with respect to the original images. An important observation is that the HS filter has kept the values of o, and ah very close to those of the original images, while all other filters have significantly increased the value of this parameter with respect to those obtained from the unprocessed images. The filters, HP, HM and SD have increased the values of o, and a/, by much more than an order of magnitude with respect to those calculated from the unprocessed images. Although the UM has not drastically increased the values of o/ and a1, the parameters, it generally produced the lowest figure of merit. The HP3 produced the lowest figure of merit with a significant increase in o/ and ok with respect to those calculated from the unprocessed images. The figure of merits for the HM and SD filters increase with noisy images, but the values have slightly decreased for the others studied, including the HS filter. It appears from these tables that the HS filter delivers reasonably high figure of merits with the lowest amplification of noise. Although, the SD filter offers larger figures of merit, this is produced at the expense of extremely large noise amplification. The HS 0.9 filter delivers a high figure of merit but the relative Y1 and Y/, values have drastically decreased from the original image, and from that produced in the noise-free image. As discussed, the HS filters, at least keep the relative X1,/, values constant in the noise-free image but deviates from this value in noisy images, especially when the f factor approaches l. C. Clinical images Typical results of the edge-enhancement processes studied are shown in Figure 2. Although, the images in this figure are only 8 bit deep, the results should be representative to images of greater depth, since we are comparing the results of processing with the original unprocessed 8 bit image. This is a case of bronchiectasis where the number and size of distorted bronchi and vessels is clinicaly important. Results of the three HS filters studied, and the most visually detailed results of the other filters studied are displayed. As expected, the distorted bronchi are more noticeable within the processed images. The significant noise amplification of the HP, HM and SD filters are also well exemplified in these images. The HS in UM filters offer less noise amplification with reasonable edge enhancement. As expected from our discussion above, the images resulting from the HS filters do not appear to exhibit great noise amplification. One notices that although edges are more enhanced within the image resulting from UM processing (Figure 1 (f)) than they are with the image enhanced with HS processing, areas in the images processed from the HS filter (Figure Edge-enhancement performance of the histogram .shifting filter 63 1 (b)) apear to offer a greater range of intensity. This is especially noticeable in the regions of the heart. Figure 2. Typical results of the HS algorithm compared to those of others studied. (a) An original chest radiograph of a case of bronchiestasis. Result after processing with histogram shifting of (b) f = 0.9, HS 0.9. (c) f = 0.7, HS 0.7, and (d) f = 0.5, HS 0.5. Result after processing with (e) linear high pass filter, HP2; (f) unsharp masking, UM 0.6; (g) homomorphic; HM2; and (h) statistical differencing, SD 0.1. Conclusion The edge-enhancement properties of the HS algorithm have been quantitatively compared with several proven algorithms (linear highpass, unsharp masking, homomorphoric and statistical differencing). Unsharp masking produced low noise amplification and has the advantage of tending to keep the relative intensity of edges more constant, but with the slight disadvantage of sometimes not offering the same range of grey-Ievel intensities as does the HS process. The HS algorithm appears to offer good edge-enhancement, and has the distinct advantage of accomplishing this with the lowest noise amplification when compared to the other filters studied and without saturating enhanced areas of the image. Like all edge-enhancement filters, the HS algorithm must be applied judiciously to each particular case, but because of its properties and simplicity of the algorithm can become an important part of an image processing system. Acknowledgements We wish to thank Dr. N. Khan for supplying us with the clinical chest radiograph. This work is partly supported by the medical Research Council (Canada) and The Sterling-Winthrop Imaging Research Institute (Canada). References 1. Pratt WK. Digital Image Processing. New York: Wiley, 1991: .30.3. 2. Arcese A„ Mengert PH., Trombini EW. Image detection through bipolar correlation. IEEE Trans Inf Theory 1970; IT-16: 534-41. 3. Prewitt JMS. Object enhancement and extraction. In: Lipkin BS and Rosenfeld A eds. Picture Processing and Psychopictorics. New York: Academic Press, l 976. 4. Lee JS. Digital image enhancement and noise filtering by use of local statistics. IEEE Trans Pattern and Machine Intelligence 1980; PAMI-2: 165-8. 64 Fallone B G and Crooks I 5. Schreiber WF. Wirephoto quality improvement by unsharp masking. J Pattern Recognition 1970; 2: 111-21. 6. Oppenheim AV, Schaefer RW, Stockham TG. Nonlinear filtering of multiplied and convolved signals. Proc IEEE 1968; 56: 1264-91. 7. Pratt WK. Digital Image Processing. New York: Wiley, 1991: 305. 8. Wallis RH. An approach for the space variant restoration and enhancement of images. In: Proc Symp Mathematical Problems in Image Science. Monterey, Calif: 1976. 9. Crooks I., Fallone BG. A novel algorithm for the edge-detection and edge-enhancement of medical images. Med Phys 1993; 20: 993-7. 10. Serra J. Image analysis and mathematical morphology. London: Academic, 1982. 11. Pratt WK. Digital Image Processing. New York: Wiley, 1991: 304.