THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 ADAPTIVE GRAY SCALE MAPPING TO REMOVE REGISTRATION NOISE IN DIFFERENCE PICTURES Edward J. Delp and Thomas F. Knoll CRL*TR-S-84 JANUARY 1984 Room 1079, East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 763-8000 1Tbis research was partially sponsored by the Biomedical Research Council and the Office of the Vice-President for Research, University of Michigan. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agency.

03,"I

Adaptive Gray Scale Mapping to Remove Registration Noise in Difference Pictures Edward J. Delp and Thomas F. Knoll Computer, Information, and Control Engineering and Department of Electrical and Computer Engineering University of Michigan Ann Arbor, Michigan Abstract Difference pictures are used in various image processing applications such as change detection, radar imaging, remote sensing, and biomedical image analysis. The difference picture, or difference image, is found by subtracting one image from another. One practical problem with difference pictures is that, if the images are not in perfect spatial registration before subtraction, the difference picture will contain artifacts caused by incomplete cancellation of the unchanged background objects. These artifacts (registration noise) show up as extraneous light and dark regions on either side of the background objects. Usually, this noise is ignored, or is reduced by either smoothing (blurring), or thresholding the difference image. This paper describes a new method to reduce registration noise using adaptive gray scale mapping. This simple digital filter reduces registration noise as well as, or better than, previous methods, without degrading the real difference image.

-21. Introduction The difference picture can be simply thought of as an image that indicates change between two images. The difference picture is found by spatially aligning the two images as well as possible and, pixel by pixel, subtracting one image from the other. To avoid having to process negative gray level values, the difference picture gray levels are often offset so that zero (no difference) is represented as middle gray. We shall assume in this paper that there is no appreciable illumination difference between the two images, so that the difference picture can be used as a measure of what is actually different between the two scenes. In many applications one would have to adjust for illumination effects before the difference picture could be found. Difference pictures have been used to detect changes in aerial photographs [9], radar images [6], Landsat images [8], and x-rays of bones [10]. They are also used in dig:tal subtraction angiography [1], [5]. All of these applications rely on the fact that aly featurce that has not changed between the two images is canceled in the difference picture. This cancellation is useful, either because it greatly reduces the number of features that need to be considered (by human or machine) in later analysis, or because features that were obscured in the background are revealed in the difference picture. Another application of difference pictures is motion detection [2], [3], [7]. This application is different from the above applications in that, instead of features or objects appearing or disappearing (or changing size), they are moving. If the frames are closely spaced in time compared to the object speeds, the objects will have moved only a few pixels between the frames. There will be areas in the difference picture at the leading edges of the objects, caused by the objects covering the background, and areas at the trailing edges, caused by the background being uncovered. These areas present a problem, as they look exactly like registration

-3noise. (Registration noise is also caused by a displacement between the two frames-it is as if the entire background is moving). It is impossible for any local operation to remove registration noise from these types of difference pictures without destroying the motion information. This situation will not be considered in this paper. However, if the frames are widely spaced in time compared to the object speeds, the objects will have moved a large distance (several object diameters) between the frames. This can be thought of as simple change detection; objects have disappeared from some locations, and other objects have appeared at different locations. This paper will consider the removal of registration noise from these difference pictures. We have used difference pictures to detect molecules in tissue samples [4]. Two consecutive slices are used as samples, so they are similar in shape and features. One sample is digested with an enzyme that removes a specific molecule, while the other sample is untreated. Areas that contains the molecule will be darker in the control sample than in the treated sample, whereas areas that do not contain the molecule will have the same gray level in both samples. Thus the difference picture shows the locations and densities of the removed molecule. One practical problem with difference pictures is that, if the two images are not in perfect spatial registration before subtraction, the difference picture will contain registration noise. Objects in the two images will not line up perfectly, causing extraneous light and dark areas in the difference picture. (We shall assume in this paper that the misregistration is due to changes in camera angle or small translational motion of objects in the scene, and not to changes in camera distance or perspective). Each misregistered object will have corresponding light and dark areas beside it. Which side the light and dark areas are on depends on the direction of the registration error, and on whether the object is lighter or darker than the

-4background. Figures 1 and 2 show two slightly different images, and Figure 3 shows their ideat (no registration noise) difference image. Notice how the objects around the edge of the image cancel completely, because they are identical in both images. However, when the image in Figure 2 is shifted slightly before subtracting it from Figure 1, the "raw" difference image is found (shown in Figure 4). Notice the registration noise, caused by the misregistered objects around the edge of the image. Even a slight misregistration will add noise to the difference image, possibly overwhelming the real differences between the images. Removing this noise will assist human or machine interpretation of the difference images. One method to reduce registration noise is to smooth the difference image; this has the side effect of blurring the real differences (see Figure 5). Another common method is to threshold the difference image, mapping all pixels in a range around middle gray to middle gray. Tlhis destroys much of the gray scale information in the picture, and is ineffective if the registration error is greater than one pixel (assuming the images contain sharp edges). Adaptive gray scale mapping (discussed later) is a new, simple digital filter that is effective in reducing registration noise, while preserving the real differences between the images. 2. Properties of Registration Noise A simple property of registration noise is that it has a zero sample mean. The corresponding light and dark areas on either side of each background object spatially average to zero. To show this, let us compute the spatial average of a difference image containing only registration noise. Let g(i,j) be the difference image between a discrete image S (i,j), containing objects on a constant background, and a shifted version of that same image. Th(ij) = fdifference image will consist totally of regisration noise. Let f(,) -e eqf(i -Ai-A ) This difference images will consist totally of registration noise. Let f (i,;) be equal

to a constant c, outside some region A EI12 (I is the set of all integers). Let region Bc IZ be the region A shifted by (Ai,Aj). Summing the difference (noise) image over all non-zero values gives E g(i,,) E f(i,j) - f (i-Ai, j -Aj) (iE) AuB (ij) EAuB E f(ij)- E> f(i-Ai,j —Aj) (,j)EAUB (i.j)EAUB = EL f (ij)- EL f(i-Ai,j-Aj) + > E c - >3 c (i j) E A (i j) EB (ij) EAnB (ij) EAnB and using the fact that regions An B and B n A have the same area = I' f(ij)- > f(i-Ai,j -Aj) (i,.j) c A (i j) B:= E' f(,j))- > fs(i,i) (tj) c A (i.j) E A =0 Thus, the registration noise caused by each object or set of objects will spatially average to zero. The above proof assumes that the images can be modeled as objects on a constant background. (Non-uniform gray level objects are allowed-they are just treated as multiple, overlapping uniform objects). An image which could not be modeled as objects on a background is an infinite step reference scale. Here the registration noise is monochromatic (all light or all dark). Fortunately, most images can be approximately modeled as objects on a background. In general, corresponding light and dark regions can be far apart, separated by as much as the largest object dimension. A large averaging neighborhood would be required for the registration noise to average out. The noise reduction problem is simplified if rmost of the corresponding light and dark areas of registration noise are close together. Then only a small neighborhood is required for the noise to spatially average to zero. Registration noise from small objects is close together, as is noise from long thin objects (if the end effects are ignored). For many images the

-6approximation that corresponding regions are near each other is a good one, because most images contain many more small objects than large objects. Small objects cause more noise per area of the object than large objects (a long thin object will cause just as much noise as a fat object of equal length). Both smoothing and adaptive gray scale mapping will use the fact that registration noise is zero mean, and will assume that corresponding light and dark regions are near each other. 3. Current Methods Used to Remove Registration Noise The best way to reduce registration noise is to register the images accurately before subtracting. Most of the work in the reduction of registration noise has addressed the problem by proposing better registration algorithms [6], [9]. Both linear and higher order geometrical transforms are used to align the images as accurately as possible. However, to completely prevent registration noise, the images must be aligned to sub-pixel accuracy. Even if the images are registered carefully beforehand, some noise is likely to remain in the difference picture. Sometimes it is not possible to align the images accurately enough before subtraction. One case is subtractive television [7]. Here the subtraction is done by the camera; the only input to the computer is the difference image. Registration error caused by non-repeatability of the camera cannot be corrected beforehand, and must be removed from the difference image. Another case where it is not possible to align the images accurately enough is our work with consecutive tissue samples [4]. Although the samples are very similar, they are not identical. While the basic outline of the sernples can be aligned, small scale features, such as cells, usually cannot. Again, the noise must be removed after computing the difference image.

-73.1. Smoothing to Remove Registration Noise The simplest way to remove registration noise is to smooth the image by replacing each pixel by the average gray level of pixels in its neighborhood. This can be either an unweighted (simple) or a weighted average. If the averaging neighborhood is large enough, it will probably contain both of the corresponding light and dark areas of registration noise. Because the noise is zero mean, it will average out and be removed. The problem with smoothing is that, if the averaging neighborhood is large enough to reduce the registration noise, it also blurs the real differences between the images. Figure 5 shows the the raw difference image in Figure 4 after simple smoothing. The registration noise is greatly reduced, but the real differences have been so blurred that they are hardly visible. 3.2. Thresllolding to Remove Registration Noise If the registration error is less than one pixel (slightly more if the images contain no sharp edges), thresholding can be used to reduce registration noise. When the regist ation error is small, the registration noise is likely to be less intense (closer to middle gray) than the real difference image. By setting pixels whose gray level is within a certain distance of middle gray to middle gray, noise can be reduced. Other pixels can either be left alone, or set to the corresponding maximum or minimum value. One problem with thresholding is that it fails if the registration error is larger than one pixel. Registration noise caused by a sharp edge and an alignment error of only one Dixel will be just as or more intense as the real differences between the images. If the inmage in Figure 4 is thresholded, it noise is totally uneffected.

-84. Adaptive Gray Scale Mapping to Remove Registration Noise Adaptive gray scale nrapp>ing is a filter Lhat, for each pixel, uses its ncighborhood to estimate whether the pixel is part of the true difference image, or part of the registration noise. A non-linear gray scale map is computed for each pixel, based on the amount of "brightness" and "darkness" in a neighborhood around that pixel. EHach pixel is then passed through its own map to produce the filtered difference image. Adaptive gray scale mapping can work much better than simple smoothing. Figure 6 shows Figure 4 after adaptive gray scale mapping. The noise is reduced just as much as in Fligure 5, but the r'eal difference image is not blurred. Imagine the difference image as a sandbox. Where the difference image is light, there is a hill; where it is dark, there is a valley. Registration noise shows up as corresponding hills and valleys. Because registration noise has a zero sample mean, each hill contains exactly as much sand as is missing from its corresponding valley. In leffect, all the registration noise does is scoop up sand from some parts of the image, leaving valleys (dark areas), and dump it in other parts, creating hills (light areas). Adaptive gray scale mapping tries to reverse this process. To remove registration noise, the sand must be removed from the hills and put back in the valleys. One way to do this is to remove sand from all the hills (in proportion to their height), and dump it into all the valleys (in proportion to their depth). This continues until either there are no more hills, or there are no more valleys. The problem with this method is that all hills and all valleys are treated alike; isolated hills (probably part of the real difference image) are chopped just as much as are hills next to valleys (which are probably registration noise). The algorithnl is refined by using the assumption that corresponding light and dark areas (hills and valleys) caused by registration noise are near one another. Sand from a hill is used to fill only the nearby valleys. Isolated hills or valleys are

-9not effected, whereas areas that contain both hills and valleys that are near each other are smoothed out. The final image will now contain some areas with only hills, some areas with only valleys, but no areas with both hills and valleys. This algorithm cannot be implemented exactly as described. The sand moving process is parallel and continuous. Sand is moved from all the hills to all the valleys at the same time. F'or a given hill and valley, the rate of sand transfer between them will depend inversely on their distance, and their current (not initial) height and depth. The algorithm would have to be approximated by many iterations, each moving a small amount of sand. The algorithm is speeded by, instead of actually moving the "brightness" (sand) around, the final gray level of a pixel is estimated from the amount of "brightness" and "darkness" in the neighborhood around that pixel. For example, if a pixel is below the reference level (in a valley), and there is equal brightness and darkness (sand in hills and sand missing from valleys) in its neighborhood, the pixel is mapped to the reference level (the valley is filled in). Or, if there is twice as much darkness as brightness, the pixel is mapped to a gray level halfway between its current level and the reference level (the valley is halfway filled in). A non-linear gray scale map is computed for' each neighborhood, based of the amount of brightness and darkness in it, and its center pixel is then mapped to a new value. 4.1. Implementation of Adaptive Gray Scale Mapping Adaptive gray scale mapping has two parameters. The first is the radius A, of the square neighborhood around each pixel that sand could be moved to or from. If the neighborhood is too small, it will not contain both the light and dark regions of registration noise, and the algorithm will not remove the noise. However, for an object in the real difference image is not to be effected by the filter, it must be isolated from regions of opposite color by at least the neighborhood radius. As the radius is increased, more and more of the real difference image will not be isolated

- 10 - enough, and will be n-mistakenly dimmed or completely removed. The ideal radius is large enough to reduce noise, but smnall enough to not excessively dim the real difference image. It must, in general, be found by trial and error for each class of difference images. The second parameter is the reference gray level r, used to separate hills and valleys. A pixel brighter than the reference is considered to be part of a hill; a pixel darker is considered to be part of a valley. Normally, the reference level is set to the gray level in the difference picture that corresponds to no difference between the two input images. Areas that contain only registration noise will contain equal moments above and below this reference level. Because both moments are equal, the noise will be con-pletely removed. If the reference level is set to some other level, the moments will not be equal, arid the noise will be only partially removed. Ilowevar, if the background gray level has changed between the two images, a different rctference level will achieve greater noise reduction. Registration noise in these area; will nriot average to zero, )but instead to the difference in the background levels. Maximum noise reduction is then achieved when the reference level is set to the difference in background levels. Two conditional local moments are computed for each pixel in the difference image. The first is the brightness moment i A jA A b(i j) = (f (mn)-r) If (n,n)>r m= - n=j --- where I is the indicator function. Pixels outside the image are assumed to be at the reference level. In the sand model, the brightness moment corresponds to the amount of sand in tl'e hill:-; near the pixel. The other moment computed is the darkness mn o ment i4a jA a deij)=> =( If mn))f(m,)<r m=i- n=j — I This corresponds to the amount of negative sand, or air, in the valleys near the

-11 - pixe l. The gray level of each pixel in the difference image is then mapped to a new gray level r+(f/(i,)-r) b((i )-d(i,j) if f (ij)>r and b(i,j)>d(ij) b (i,j) g(ij) = r-(r -f( j)) d(ij)-b(i.) if f (ij) <r and b(ij) < d(i,j) r otherwise If a pixel is in the minority, i.e. a dark pixel in a mostly bright area, or a bright pixel in a mostly dark area, it is mapped to the reference level. If the pixel is in the majority, its contrast is toned down with a ramp function whose slope depends on the amount of disagreement in the area. For example, if there is three times as much dark as bright, the ramp will have slope two-thirds. (In the sandbox model, this corresponds to filling the valley one-third of the way). Aaaptive gray lcale mapping can be done quickly. If the conditional moment calculations arc implemented as written, execution time would be proportional to the image,area times the neighborhood area. However, by using incremental updating to corrpute the moments, the execution time is reduced so that it is proportional to only the image area. This is done by first computing column subtotals, and then summing the subtotals.'T'he moments are incrementally updated as the row is scanned, by adding in the leading subtotals, and subtracting out the trailing subtotals. When changing to the next row, each of the column subtotals is incrementally updated by looking at the leading and trailing rows of pixels. 4.2. Preservation of Neighborhood Mean Gray Level lBecause registration noise has a zero mean, it is desirable that, filter that removes registration noise should not change the mean gray level of the difference picture. We shall show in this section that adaptive gray scale mapping approximately preserves the neighborhood mean gray level.

- 12 - Computing the neighborhood sum of the difference picture around (i,j), assuming b (i,j)> (i,j) i+A j +A Z > g (mn) = m rn=i -A n =j -A b(m,n)-d(n) ((mn)r)f (mn)>rl m=i-An (=j b ( m n) Ifr,,n)l Assuming that. neighborhoods of pixels in the neighborhood of (ij) all have about the same amount of b)rightness and darkness, i.e. b (m~n) h (ij) d (m,n) d (7, Y ) This approxirnation holds well if the neighborhood size is large compared to the characteristic dimension of the texture field. Using this approximation v g(rr+,n) r +Ai +A jA + 1 b (ij) -d (ij) x >2 >2g (I,r2 Z r' x m=i-A n=j — A m=i A n=j —A b (i,j) A'> (f (rr,n)-r)I f (mn)r>r3 m =i — A nL =j — A + b(,j)-d(,j) b (i,j) M =i — A 7' j- b (ij) i+A Ji+h i+A j+A 2= 2> r + E 2 (f (m,n) )-r) n =i -- A = j - A m =i -A n =j -A -i+A *+ A = > E f((m,n) =i — A n =j -A This can also be shown when b (i,j) d(i,j). Thus the neighborhood sum, (and thus the neighborhood mean), are approximately preserved by adaptive gray scale mapping. 5. Example: Molecule DcLect.ion Using Consecutive Tissue Samples We have iused difference pict urcs to detect the locations and densities of specific molecules in tissule samples [4]. Two consecutive tissue slices are used. One is kept as a control, while the other is treated with an enzyme that digests the molec ule in question. B~olh samples are stained and photographed. The

- 13 - photographs are then digitized and registered as well as possible. The treated image is then subtracted from the control image. The resulting difference picture shows, in theory, the locations and densities of the molecule in question.'Ihe problem with this method is that the two samples are not identical. While the basic outline of the samples can be aligned, the smaller scale features, such as cells, cannot.'['his is because the cell dimensions are of the same order as the slice thickness. Although each sample will have about the same density of cells, the cells will not line up between the two images. The unfiltered (raw) difference picture will contain of lot of registration noise. Figu.res'7 and tB show the digested and the control images before subtraction. Figure 9 shows their' raw difference image. Notice how the registration noise (extraneous light and dark regions) makes it difficult to see which areas are really darker in the control imagre. The raA difrcrcnce inmage was then filtered using adaptive gray scale mapping. The refereice gray level was set to the value corresponding to no difference between the input images. The region radius was found be trial and error-starting with a small value and increasing it in steps until enough noise reduction was obtained. The resulting filtered difference image is shown in Figure 1Q. Notice how it is much easier to see where, and how much, the control sample is darker than the treated sample (and thus ihe locations and densities of the molecule in question). In this application, the texture of the tissue areas in the difference images is not important, only their mean gray levels. The texture is an artifact caused by the cells, and should be ignored.'['his texture could be removed by smoothing the difference image, but that would blur details in other areas of the difference image.

- 14- - 6. Conclusions D)ifference p)icturares are useful in dctecting change between two images. One problemrr with difference pictures is that, if the two images are not aligned perfectly before subtraction, extraneou-s light and dark regions will appear in the difference image.'I'hese artifacts are caused by the misaligned background objects in the two images not canctling completely in the difference picture. We have presented a new algorithmn u.sirg adaptive: gray scale mapping, that reduces registration noise from difference pictures. It removes noise as well as or better than existing methods, while not blurring the real differences between the images. It also preserves the mean gray level, which is desirable because registration noise does not change the mrieain grary level. We would like to thank l)r. linda Li. 13rinkley of the Department of Anatomy and Cell i3iLolog,, University for viic:higan, for suggesting the above problem and providing technical supy)port and advice.

- 15 - References [1] C. K. Chow, S. K. Ililal, K. 1'. Niebuhr: X-ray Image Subtraction by Digital Means, IBM Journal of Research and Development Vol. 17, 1973, pp. 206-218 [2] R. Jain: Extraction of Motion Information from Peripheral Processes, IEEE Transactions of Pattern AXtalysis and Machine Intelligence Vol. PAMI-3, 1981, pp. 489-503 [3] R. Jain: Dynamic Scene Analysis Using Pixel-Based Processes, Computer Vol. 14, August 19831, pp. 12-18 [41 T. F. Knoll, 1,. L. Brinkley, E. J. Delp: A Method for the Analysis of Histological Images Using Difference Pictures, Submitted to Analytical and Quantitative Cytology [5] R. S. Ledley, L. M. Arminski, IL. S. Rotolo, T. J. Golab, C. M. Park: TEXAC-Based Digital Fluoroscopy, IEEE CormpLter Society Conference on Pattern Recognition and /rn.age lProcre.ssing, 1982, pp. 530-533 [6] R. L. Lillestrand: Techniques for Change Detection, IEEE Transactions on Cormputers Vol. C-21, 19'72, pp. 654-659 [7] M. Onoe, N. FHlanano, K. Ohba: Computer Analysis of Traffic Flow Observed by Subtractive'I'elevision, Com.puter rnphics and Image Processing Vol. 2, 1973, pp. 377-392 [B] C. J. Robinove, P. S. Chavez, D. Gehring, R. Holmgren: Arid Land Monitoring Using Landsat Albedo Difference Images, Remote Sensing of Environment Vol. 11, 1981, pp. 133-156 [9] M. S. tlstad: An Algorithm for Estimating Small Scale Differences Between Two Digital Images, Pattern lreercognition Vol. 5, 1973, pp. 323-333 [10] R. IL. Webber, U. FI. Luttim-ann: I)igital Subtraction of Radiographs as an Aid for Detecting Pathologic Changes in Periodontal Bone, IEEE 1982 International Workshtop on Physics and Engineering in Medical Imaging, pp. 130-136

- 16 - Figure 1: A 256x2-)6 pixel test image Figure 2: A second test image, almost that contains both dark and light ob- the same as F'igure 1, except for the Iects on a constant backaround. center objects. Figure 3:'I'he ideal diff(zrcnc-e in-lage Figure 4:'The raw difference irrLage found by suhbtr'atinfg lgi'ir,Jr'e 2 fronm F'ig- betwen F'igu;re I and a shiftecd version ure 1. Note how he ob)je(its ifr'ord the of ligure 2. F'iure 2 has been shifted edge conlpleLely cancel oul sincer. t..hey by 4 pixels; in the horizontal direction are. tLhe s.lnle in bot[h in-Laies and'2 pixels. irn the vertical.

- 17Figure 5: The raw difference image from Figure 6: The raw difference image front Figure 4 after simple smoothing with a Figure 4 after adaptive gray level mapneighborhood of' 21 by 28i pixels. The ping with a neighborhood of 25 by 25 registration noisle is redctlcedc, butt the pixels. The registration noise is almost difference image is bklurr'(red. completely removed, and the difference image is left unchanged. Figure 7: A 256x,956 pixel image of the Figure 8: A 256x256 pixel image of the control tissue sanple. digested tissue sam>le. This sample slice is consecutive with the sample in Figure 7. This sample has been treated to removed the molecule in question.

- 18Figure 9: The raw difference image Figure 10: The filtered difference image found by subtracting Figure 8 from Fig- found by using adaptive gray scale mapure 7. Notice how the registration noise ping on Figure 9. A neighborhood radius makes it difficult to see where the im- of 7 was used. Notice how it is easier to ages are really different. see the areas where the control image is darker than the digested image.

UNIVERSITY OF MICHIGAN 1113 IIIIIIIIII 11506113 111 56111 1 3 9015 02653 5156