Abstract:
A method of operating a computing machine for reducing speckle noise in video images, particularly radar images, utilizes a complementary hulling technique on vertical pixel grids of the array. The vertical pixel contours which are subjected to the complementary hulling are derived from intersections of vertical grids with conceptual superposed gray-scale surfaces which have front end values corresponding to the gray-scale pixel values. The invention provides the significant advantages of decaying small image features, such as speckle noise at a significantly faster rate than large image features, such as target returns.

Description:
BACKGROUND OF THE INVENTION 
     This invention relates generally to systems for reducing noise in video display systems, and more particularly, to a digital filter for reducing the effects of speckle noise in images such as radar images. 
     It is desirable in a variety of video applications, and particularly in synthetic aperture radar images, to reduce speckle noise. Such reductions in speckle noise assist radar image interpreters in identifying targets and to pre-process images for automatic recognition algorithms in computers. An essential goal to be achieved is the smoothing of the speckle noise while preserving features of interest such as edges and strong returns. Since the mathematical nature of speckle noise is multiplicative, a reasonable measure of the amount of speckle noise present can be achieved by determining the ratio of the deviation of the noise to its mean. In this regard, the deviation of the speckle noise can be determined as follows: 
     Let p(m,n), 1≦m,n≦N, be the pixel values. For 2≦m,n≦N-1, the local deviation is then definable as ##EQU1## This expression of the deviation is not representative of the true deviation. However, it can be computed easily and provides sufficient accuracy for the purposes herein. The local mean is then definable as: ##EQU2## Finally, the speckle index can be defined as: ##EQU3## 
     One well known filter which is used to reduce speckle noise in radar images is known as a &#34;median filter.&#34; In order to facilitate understanding of the effects of the median filter, reference is made herein to several of the figures. 
     FIG. 1 is a radar image of an area, specifically the Willow Run Airport in Southeastern Michigan. This figure depicts a synthetic aperture radar image and is an X-band strip map image which has been digitally processed on a digital processor. The transmitter and receiver were both polarized horizontally during acquisition of the radar image of FIG. 1. The resolution, measured as the half-power width of the impulse response function is 6 m. 
     FIG. 2 is a sub-image of FIG. 1 and shows the area within the square in FIG. 1. The pixel spacing in FIG. 1 is 3 m and is comprised of a pixel array having 512 by 512 pixels. 
     FIG. 3 is a representation of the image of FIG. 2 after applying a known 3×3 median filter iteratively until the image of FIG. 3 was obtained which is of period two under the median filter. Thus, one application of the median filter will change the image very slightly, and the image will not change at all under two applications of the median filter. In this known median filter system, the 3×3 median filter replaces each pixel value with the median of the 9 pixel values in its 3×3 neighborhood window. 
     FIGS. 4 and 5 are shaded and shadowed versions of the images of FIGS. 2 and 3. Thus, FIGS. 4 and 5 can be considered as two-dimensional surfaces in three-dimensional space. 
     A further known technique which has been applied to enhance imagery is known as the 8-Hull algorithm which is used to generate approximations to the convex hulls of maximal connected subsets of the foreground of a binary image. A binary image is an image having pixels with values of only 0 or 1. The pixels with value 1 are termed the &#34;foreground.&#34; 
     The convex hull of a set is the intersection of all half-planes containing it. An approximation to this, called the 8-hull, is defined as the intersection of only those half-planes which contain the set, the edges of which are either horizontal or vertical, or lie in either of the 45 degree diagonal directions. Thus, the 8-hull of a set has, at most, eight sides. 
     An iterative algorithm for generating the 8-hull of a set operates by changing the value of a pixel from a zero to a one if its neighboring pixels have ones arranged in any one of the configurations shown in FIG. 6. The blank squares can be either zeros or ones. If enough iterations of this step are performed, eventually the 8-hull of the given set will be generated and it will be invariant under further iterations. 
     FIGS. 7 to 10 illustrate a sequence which is formed while an 8-hull of a set is being produced. In these figures, the black squares represent ones and the white squares represent zeros. FIG. 7 depicts an original set, and FIG. 8 shows the results after one iteration of the 8-hull algorithm. FIGS. 9 and 10 illustrate the results after two and three iterations, respectively. The shape shown in FIG. 10 remains invariant under further iterations. 
     A still further iterative algorithm, which is used for smoothing the ragged edges of the foreground set in a binary image, shall be discussed herein as the &#34;complementary hulling algorithm.&#34; In one iteration of the complementary hulling algorithm, first, one step of the 8-hull algorithm described hereinabove is applied to the set, and then one step of the 8-hull algorithm is applied to its complement. Thus, one step of the 8-hull algorithm is applied, and then the zeros and ones are interchanged. Another step of the 8-hull algorithm is then applied, and finally the zeros and ones are interchanged again. This has the effect of gradually reducing the maximum curvature of the boundary of the set, where curvature is the inverse of the radius of curvature. More specifically, with few exceptions, the boundary of a set invariant under this algorithm can turn a maximum of 45 degrees at any vertex. The only known exceptions to this rule are the boundary segments shown in FIG. 11 and their 90-degree rotations. 
     The complementary hulling algorithm is applied herein, for purposes of illustration, to the set of FIG. 12. FIGS. 13 through 16 show the results of 1, 2, 3, and 9 iterations, respectively, The shape shown in FIG. 16 remains invariant under further iterations. 
     FIG. 17 shows a tower three pixels wide. If one imagines going up the left side of this tower, and then down the right side, a sharp U-turn must be made at the top. This U-turn has too high a curvature to be permissable. Hence, the complementary hulling algorithm reduces the curvature until it is sufficiently small. FIGS. 18 through 21 illustrate the results of 1, 2, 14, and 15 iterations, respectively, of the complementary algorithm. The shape shown in FIG. 21, which corresponds to 15 iterations, remains invariant under further iterations. 
     FIG. 22 shows a tower seven pixels wide. In this situation, the U-turn can be made without requiring too high a curvature. FIGS. 23 through 25 illustrate shapes resulting after 1, 2, and 3 iterations of the complementary hulling algorithm, respectively. The shape of FIG. 25 remains invariant under further iterations. In contrast to the invariant shape shown in FIG. 21, which corresponds to 15 iterations on a three-pixel wide tower, the seven-pixel wide tower of FIG. 25 has its corners rounded, but the height of the tower is not reduced. 
     It is, therefore, an object of this invention to provide a simple and inexpensive system for reducing speckle noise in imagery. 
     It is another object of this invention to provide an iterative system for reducing speckle noise wherein relatively few iterations are required to reduce the speckle noise. 
     It is also an object of this invention to provide a symmetrical speckle noise reduction system whereby the filling up of valleys is essentially equivalent to the tearing down of walls in a binary image. 
     It is additionally an object of this invention to provide a speckle noise reduction system wherein rapid reduction of the noise is achieved without elimination of the desired image features. 
     SUMMARY OF THE INVENTION 
     The foregoing and other objects are achieved in this invention which provides in a general aspect thereof, a method of operating a computing machine for reducing speckle noise in a video image of the type formed of an m×n array of pixel elements. Each pixel element has a respective gray-scale value (V) associated therewith, where zero is less than or equal to V which is less than or equal to K. K is a maximum gray-scale value. After the m×n gray-scale values are stored in a memory, a plurality of individual ones of gray-scale values are identified in accordance with a predetermined adjacent neighboring arrangement in the m×n array. Thus, for example, such neighboring adjacent ones of the gray-scale values can correspond to a row, column, diagonal, or any other arrangement of adjacent neighboring gray-scale values. Each of the gray-scale values in the predetermined arrangement is subjected to a value-adjustment test. In response to this test, each gray-scale value may be changed, such as by incrementing by a predetermined amount, in response to the immediately prior and subsequent adjacent gray-scale values. Thus, looking at one such gray-scale value within the predetermined neighboring arrangement, V A  is the immediately prior gray-scale value, V B  is the gray-scale value being tested, and V C  is the immediately subsequent gray scale value. In accordance with the invention, the gray-scale value under test, V B , is incremented if one of the following four conditions, which depend on a positive input parameter I, is satisfied: 
     (1) if (V B  +I)&lt;V A , then set V BN  equal to the minimum of (V A  -I) and (V B  +I); 
     (2) if V B  &lt;V A  and V B  &lt;(V C  +I), then set V BN  equal to the minimum of V A , (V B  +I), and (V C  +I); 
     (3) if V B  &lt;V C  and V B  &lt;(V A  +I), then set V BN  equal to the minimum of V C , (V B  +I), and (V A  +I); and 
     (4) if (V B  +I)&lt;V C , then set V BN  equal to the minimum of (V C  -I) and (V B  +I). 
     If any one of these conditions is satisfied, then the new value V BN  is stored in memory in place of V B . 
     The test to which the gray-scale value V B  has been subjected is repeated for every gray-scale value in the predetermined adjacent neighboring arrangement. Preferably, the four conditions are applied sequentially to the gray-scale values in the predetermined arrangement. 
     After the application of such a test, which corresponds to the first step of a hull algorithm, the gray-scale value in the predetermined arrangement are complemented by subtracting their values from K. The resulting complemented values are then subjected again to the test, with the same four conditions, and the resulting values are complement-restored by subtracting once again from K. All of the foregoing steps are then repeated on a further plurality of gray-scale values identified as a new predetermined adjacent neighboring arrangement. In a specific embodiment of the invention, the foregoing testing process is applied to all gray-scale values several times, since the plurality of neighboring arrangements correspond to all of the rows running east and west, all of the columns running north and south, all of the diagonals running southwest and northeast, and all of the diagonals running northwest and southeast. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Comprehension of the invention is facilitated by reading the following detailed description in conjunction with the annexed drawing, in which: 
     FIG. 1 is a synthetic aperture radar image of Willow Run Airport in southeastern Michigan; 
     FIG. 2 is an expanded representation of the area contained within the square of FIG. 1; 
     FIG. 3 is a representation of the image of FIG. 2 after being subjected to many iterations of a prior art median filter; 
     FIG. 4 is a shaded and shadowed version of FIG. 2; 
     FIG. 5 is a shadowed and shaded version of FIG. 3; 
     FIG. 6 illustrates eight patterns which can be used by the 8-hull algorithm; 
     FIG. 7 is an original binary image set; 
     FIGS. 8, 9, and 10 are binary image representations of the shape shown in FIG. 7 after 1, 2, and 3 iterations of an 8-hull algorithm, respectively; 
     FIG. 11 is a binary representation of exceptions to the rule that the boundary of a set which is invariant under the complementary hulling algorithm can turn a maximum of 45° at any vertex. 
     FIG. 12 is a representation of an original set of a binary image; 
     FIGS. 13, 14, 15, and 16 are binary image representations of the shape shown in FIG. 12 after 1, 2, 3, and 9 iterations of a complementary hulling algorithm, respectively; 
     FIG. 17 is a binary image representation of a tower three pixels wide; 
     FIGS. 18, 19, 20, and 21 are binary image representations of the shape shown in FIG. 17 after 1, 2, 14, and 15 iterations, respectively, of a complementary hulling algorithm; 
     FIG. 22 is a binary image representation of a tower seven pixels wide; 
     FIGS. 23, 24 and 25 are binary image representations of the shape shown in FIG. 22 after 1, 2, and 3 iterations of a complementary hulling algorithm; 
     FIG. 26 is a binary representation of a curve formed of vertical pixels; 
     FIG. 27 is a binary representation of an umbra corresponding to the curve of FIG. 26; 
     FIG. 28 is a binary representation of the complement of FIG. 27; 
     FIGS. 29 and 30 are images corresponding to FIG. 2 after 4 and 10 iterations, respectively, of the subject geometric filter; and 
     FIG. 31 is a shaded and shadowed version of FIG. 4 after 10 iterations of the present geometric filter. 
    
    
     DETAILED DESCRIPTION 
     The present invention is directed to a non-linear system which is based on geometric concepts and is particularly useful in reducing speckle noise in synthetic aperture radar images. In so doing, the present invention assists interpreters of radar images and in the pre-processing of images for automatic recognition of targets and items in the image by computers. In a specific illustrative embodiment of the geometric digital filter of the present invention, approximately ten iterations will result in optimal speckle noise reduction. However, a significant reduction in speckle-noise can be achieved with just two or three iterations. 
     The following table of speckle indices illustrates the advantageous speckle-reducing aspects of the present invention: 
     
                       TABLE I______________________________________IMAGE               SPECKLE INDEX______________________________________Original Image      1.4004 Iterations of Geometric Filter               0.38010 Iterations of Geometric Filter               0.182Period 2 Median Root               0.333______________________________________ 
    
     As previously indicated, FIG. 1 is a synthetic aperture radar image of the Willow Run Airport in southeastern Michigan. FIGS. 29 and 30 illustrate the region within the square of FIG. 1 after having been subjected to 4 and 10 iterations, respectively, of the geometric filter of the present invention. For the purposes of comparison, FIG. 3, which was discussed hereinabove, illustrates the results of applying a 3×3 median filter iteratively until an image of the period 2 under the median filter was obtained. 
     FIG. 31 is a shaded and shadowed version of FIG. 30 and illustrates that significantly greater smoothing can be achieved over the original image (See FIG. 4), and even over the period 2 median root (see FIG. 5). 
     In a specific illustrative embodiment of the invention where pixel values, or gray-scale values, are between zero and 255, inclusive, the geometric filter of the present invention operates as follows: 
     First, the reader is requested to conceptualize a gray-level radar image lying horizontally with its sides running in the north-south direction and its top and bottom running in the east-west direction. Now, imagine a gray-level surface arranged above the image such that its height above any pixel is proportional to the value of the gray-scale of that pixel. Thus, this gray-level surface has bumps and valleys in correspondence to the gray-scale values of the pixels of the original radar image. The superposed surface is then sliced by a vertical plane which contains a line of adjacent neighboring pixels running in the east-west direction. Thus, if the original radar image is deemed to be an m×n array of gray-scale values, the vertical plane extends orthogonally upward along a row of the array. 
     FIG. 26 is an illustrative binary image of a curve which is formed by vertical pixel values on the vertical plane. In essence, each black space corresponds to the particular vertical value where the superposed gray-level surface intersects the vertical plane. The points in this vertical grid will be referred to as &#34;vertical pixels.&#34; 
     FIG. 27 is a binary image representation of an umbra of the curve of FIG. 26. The umbra consists of all vertical pixels in the vertical grid on or below the curve. If a value of one is assigned to all vertical pixels in the umbra, and the value zero is assigned to all other vertical pixels in the vertical grid, then the vertical grid can be considered as a binary image. It is to be noted that the binary image discussed herein need not be formed in order to practice the present invention. It is, however, useful in assisting in conceptualization of the present invention. 
     The umbra of FIG. 27 is now subjected to the first half of an iterative step of the complementary hulling algorithm. Since we are presently concerned only with the line forming the top boundary of the umbra, only the top four configurations of FIG. 6 need to be used. More specifically, referring for the moment to FIG. 6, the central pixel containing a zero is converted to a one if its neighboring ones assume the shown configuration. The blank pixel location can be valued either as zero or one. 
     After the umbra of FIG. 27 has been subjected to the first half of the iterative step of the complementary hulling (not shown in the drawing), the complement of the umbra is formed, as shown in FIG. 28. This is achieved by reversing zeros to ones and ones to zeros. This complement of the umbra is then subjected to the second half of an iterative step of the complementary hulling algorithm, thereby using the lower four configurations shown in FIG. 6. The complementary hulling algorithm is then completed by complementing back so that a complement-restored umbra is produced (not shown in the drawing). 
     The foregoing procedure is performed on all east-west vertical grids simultaneously and the resulting gray-scale values replace the original gray-scale values. The same procedure is then repeated on all southwest-northeast diagonals, then in the south-north rows, and finally in the southeast-northwest diagonals. This completes an entire iterative step of the geometric filter of the present invention. 
     In specific illustrative embodiments of the invention which are practiced in accordance with the configurations of FIG. 6, the value of a vertical pixel is essentially incremented by one if any of the top four configurations of FIG. 6 are satisfied. However, in other embodiments, an incrementation parameter, I, may be entered into the system to control the rate of incrementation and therefore the number of iterations required to achieve the desired level of smoothing. Thus, in embodiments of the invention where very high values are permissible for the gray-scale values, illustratively between zero and 30,000, or more, the incrementation parameter may be more than one. In embodiments of the invention where the complement of the umbra is subjected to the second half of the complementary hulling algorithm, thereby using the last four configurations of FIG. 6, a decrementation parameter, D, which may be greater than one, may be used. 
     It is further to be noted that, in the practice of the invention, satisfactory results can be achieved using only a selectable one of the first four or the second four configurations of FIG. 6 if complementation of the umbra is achieved by subtracting the vertical pixel values from the maximum pixel value, K. Of course, after the complemented umbra is subjected to the hulling algorithm, it must be complement-restored to its original orientation by any of several methods, including simple subtraction of the new value from the maximum value, K. 
     In order to increase the rate of speckle noise reduction, the application of an iterative step of the 8-hull algorithm to the umbra of a vertical slice is changed as follows: 
     Instead of changing a zero to a one if any of the first four neighborhood configurations in FIG. 6 are present, these four configurations are used separately and consecutively. Thus, first a zero is changed to a one if the first of these four configurations is present, then the resulting image replaces the original image. Subsequently, the second configuration is used, the resulting image again replaces the original image, and the process continues until all such first four configurations have been used. Similarly, in embodiments of the invention where the second four configurations of FIG. 6 are used, these also are applied separately and consecutively to the complement. This results in a greater amount of modification of the image in each iterative step and therefore fewer iterations are required. In addition, a greater difference is achieved between the reduction rates of wide and narrow features. 
     In the practice of the present invention, it is recognized that speckle noise has a wormy appearance. Considering the image as a curved two-dimensional surface in a three-dimensional space, as described hereinabove, speckle noise appears as narrow winding walls and valleys. A strong target return appears as a wide tall tower. The entire body of the target appears as an even wider high plateau, although it is not as high as the tower representing a strong target return. The geometric filter of the present invention, through iterative repetition, gradually tears down the narrow walls and fills up the narrow valleys. It also tears down towers and high plateaus which are desired to be preserved. However, narrow walls and valleys are reduced faster than wide towers are reduced, and wide plateaus are reduced even more slowly than wide towers. In general, the wider any landscape feature is, such as valleys, holes, depressions, walls, towers, or plateaus, the more slowly it is reduced. Thus, only a few iterations are required to reduce the narrow speckle walls and valleys, and these few iterations have very little effect on wide high towers. Hence, strong target returns are preserved, as are wide plateaus. In this manner, target shape is preserved. 
     Since the filter of the present invention is designed to operate both on the umbra of the image surface and its complement, it is essentially symmetrical with respect to up and down, or towers and valleys. Thus, the filling up of valleys is essentially equivalent to the tearing down of walls. The following tables, tables II and III, show the rate at which the height (maximum) of walls and square towers are being reduced. 
     
                       TABLE II______________________________________Reduction Rates For Square Towers      Reduction of max. per iteration      less number of vertical pixels,Tower size i.e., units of intensity______________________________________1 × 1      162 × 2      93 × 3      64 × 4      55 × 5      46 × 6      37 × 7      28 × 8      2______________________________________ 
    
     
                       TABLE III______________________________________Reduction Rates For Walls      Reduction of max. per iteration      less number of vertical pixels,Wall Width i.e., units of intensity______________________________________1          122          63          34          35          26          1.57          0______________________________________ 
    
     As shown in Table II, the rate at which the maximum height of towers is reduced decreases as the size of the towers increase. Similarly, Table III illustrates that the reduction rate for walls decreases as the width of the walls increases. Tables II and III show the rates of reduction for square towers and walls after the first few iterations. The reduction rates may be less for the first few iterations. This lag is important for wider towers since, for example, the maximum of a 14×14 tower is not reduced at all until the fifth iteration. 
     In certain situations, a strong target return may be in the form of a tower which is almost as narrow as the speckle walls and valleys. However, such a tower is usually much higher than the speckle walls are high or valleys deep. Thus, although the strong target return may be reduced at as fast a rate as the speckle walls and valleys, the walls and valleys will still be reduced before the tower is completely torn down and hence the strong target return will still be preserved. However, the target return will be dimmer than in the original image. 
     Referring for the moment to FIG. 6, it can be seen that the first four configurations therein can be reduced to the following four inequalities: 
     (1) (V B  +2)≦V A  ; 
     (2) V C  ≧V B  &lt;V A  ; 
     (3) V A  ≧V B  &lt;V C  ; and 
     (4) (V B  +2)≦V C . 
     In similar manner, the last four configurations of FIG. 6, which are used in the second half of an iterative step of the complementary hulling algorithm, can be reduced to the following four respective complementary inequalities: 
     (1) (V BN  -2)≧V AN  ; 
     (2) V CN  ≦V BN  &gt;V AN  ; 
     (3) V AN  ≦V BN  &gt;V CN  ; and 
     (4) (V BN  -2)≧V CN . 
     In a more generalized case where incrementation is determined by the incrementation parameter I, where zero is less than I, then the first four configurations of FIG. 6 can be expressed as follows, where V BN  is the new value to be stored in the memory as replacing the old value V B . 
     (1) if (V B  +I)&lt;V A , then set V BN  equal to the minimum of (V A  -I) and (V B  +I); 
     (2) if V B  &lt;V A  and V B  &lt;(V C  +I), then set V BN  equal to the minimum of V A , (V B  +I), and (V C  +I); 
     (3) if V B  &lt;V C  and V B  &lt;(V A  +I), then set V BN  equal to the minimum of V C , (V B  +I), and (V A  +I); and 
     (4) if (V B  +I)&lt;V C , then set V BN  equal to the minimum of (V C  -I) and (V B  +I). 
     Although the invention has been described in terms of specific embodiments and applications, persons skilled in the art can, in light of this teaching, generate additional embodiments without exceeding the scope or departing from the spirit of the claimed invention. Accordingly, it is to be understood that the drawing and descriptions in this disclosure are proffered to facilitate comprehension of the invention and should not be construed to limit the scope thereof.