Abstract:
An automatic method for finding mines in side scan sonar images using a two-stage detection/discrimination process is provided. This method improves the discrimination process by specialized processing of regions of interest found in the detection process to increase the probability of correctly identifying highlight and shadow regions associated with mine images. Features specifically selected for their ability to discriminate mines are then extracted from these areas for use in the Bayesian discriminator.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to a system for detecting mines and, more particularly, to a system for automatically discriminating a side-scan sonar image to determine whether or not there is a mine in the image. 
     2. Description of Prior Art 
     Mine detection typically has been performed by analysts viewing side scan sonar images in which the mine appears as a highlight area followed by a shadow area in the range direction. The difficulty of this detection task varies greatly depending on the nature of the background image. On silted areas, only a highlight appears since the background is as dark as the shadow. On the sand, the mine images as a highlight, usually followed by a well-defined shadow. In rocky areas, mines and rocks are often indistinguishable from one another. The way in which the mine lies on the ocean floor relative to the sonar platform affects the intensity and shape of the highlight. At near range, shadows may not be apparent, while at far range they can be quite long. 
     The sonar analyst must, therefore, bring a great deal of experience to the task of identifying mines using sonar images. This task becomes harder when large amounts of data must be reviewed in a short time. As the data rate increases the analyst&#39;s performance drops; that is, more objects are incorrectly classified. Moreover, analysts tend to fatigue with time on the job; a fresh analyst is correct more often than a tired analyst who has been looking at data for several hours. Accordingly, there is a need for an automatic system to aid the analyst in detecting mines. 
     Although automatic detection systems are not troubled by speed or fatigue, it is difficult to design a machine to match the visual pattern recognition talent of a human analyst. Machine mine detection systems have used a variety of means to detect mines in sonar images including matched filters, neural networks and statistically based cuers. The more successful approaches use a two stage process of detection of areas of interest followed by discrimination based on a more intensive look at the areas of interest. The discrimination phase extracts features based on the shape, texture and intensity of the highlight or shadow and feeds these to a Bayesian based classifier. General classifiers designed to discriminate between man-made objects and natural objects are not specifically optimized to the image features of mines and hence are suboptimal in their performance of mine detection. Accordingly there is a need for a discriminator specifically developed for mine detection. 
     SUMMARY OF THE INVENTION 
     The present invention sets forth an approach capable of attacking this formidable task. The main ingredients of the present approach are careful and sophisticated filtering of the data as preparation for the feature extraction task. The use of many features and the grouping of these in appropriate subsets for use in a Bayesian classifier yields a powerful method for automatic mine discrimination. 
     To overcome shortcomings in prior art detectors, the present invention sets forth a mine detection and discrimination system specifically optimized to find mines and only mines. Not only is detailed information on size and shape used, but also improvements in feature extraction by way of morphological operations such as dilation and erosion. These operators reliably identify and extract the highlight and shadow areas in low contrast and noisy environments. 
     A system for discriminating candidate mine targets detected by a side scan sonar system is provided in which the candidate mine targets consist of snippet images formed from a matrix of pixels having known greyness levels. 
     The system includes a highlight filter which expands the size of each highlight area of each snippet image by a predefined amount. Adjacent highlight areas in each snippet image are thereby coalesced to form a single highlight area. A highlight mask generator uses the highlight filtered shipper images to generate a highlight mask by computing a threshold greyness level of the unfiltered snippet images and analyzing the highlight filtered snippet images using the greyness level. A highlight feature extractor extracts highlight features of the snippet images by comparing the highlight mask and the unfiltered snippet images. 
     A shadow filter expands the size of the areas in the snippet image exhibiting speckle to coalesce those areas of the shipper image exhibiting speckle. The shadow areas in the snippet image are represented by those areas of the snippet image which exhibit a lack of speckle. A shadow mask generator uses the shadow filtered snippet images to generate a shadow mask by selecting those shadow areas in the shadow filtered shipper image which meet area and greyness requirements. A shadow feature extractor extracts shadow features of the snippet images by comparing the shadow mask and the unfiltered snippet images. 
     A joint highlight/shadow feature calculator calculates joint highlight/shadow features from the highlight features and the shadow features generated by the respective extractors. A Bayesian discriminator analyzes the highlight features, the shadow features and the joint highlight/shadow features to determine whether those features correspond to predefined results which indicate the presence of a mine. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic functional block diagram of the presently preferred mine detection system. 
     FIG. 2 is a schematic functional block diagram of the presently preferred mine discriminator used in the mine discrimination system of FIG. 1. 
     FIG. 3 is a graph showing the performance of the discriminator represented in FIG. 2 in detecting mines. 
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
     The present invention is directed to one operation in an automatic detection process in which side scan sonar data is automatically processed to detect and discriminate mines on the ocean floor. FIG. 1 shows a mine detection system which is comprised of three different functional parts: (1) Preprocessing; (2) Detection; and (3) Discrimination. 
     The present invention is concerned with the third function of discrimination in which candidate targets are categorized as either mines or not mines. A brief description of the other function parts is needed to understand the environment in which the third functional part operates. 
     Referring to FIG. 1, preprocessor 12 prepares the sonar image 14 for the detection process by eliminating the average intensity discontinuity at the water column boundary and by renormalizing the image to have a constant mean in the sonar range. This step reduces false detections by the three cuers 16, 18, and 20. 
     The target detection step uses three different target detection strategies to find mine-like objects in the sonar image. The first cuer, the highlight/shadow cuer 16, convolves an array of idealized matched filters with the whole image to obtain a detection set of clusters of the image where a target is likely. The other two cuers 18 and 20 operate on these clusters to confirm or deny the cluster. Two modes of operation can be selected; either all three cuers must confirm the cluster or two out of three must confirm the cluster. The neural net cuer 18 is trained to recognize targets from a 2D Fourier Transform of a small window that scans the clusters. The statistical cuer 20 looks for statistical outliers of greyscale statistics and highlight and shadow run-length statistics by passing a window over the clusters. It establishes a reference window by averaging the statistics of N STAT  windows randomly chosen from the frame. 
     Discriminator 22 operates only on the clusters, or snippets, 24 that have passed the detection process. The clusters 24 are rectangular regions whose shape is determined by the highlight shadow cuer 16. They represent only a small fraction of the total frame grey scale data; hence the more computer intensive functions of the discrimination process need only operate on relatively small amounts of data. 
     A general technique for discriminating man-made objects in sonar data though usable is not specifically optimized to the task of discriminating mines. Accordingly, the present system is highly tuned to find mines and only mines. Such specialization greatly improves its performance. 
     As shown in FIG. 2, mine discriminator 22 is composed of eight modules: (1) highlight emphasis filtering module 26; (2) highlight mask generation module 28; (3) highlight feature extraction module 30; (4) shadow emphasis filtering module 32; (5) shadow mask generation module 34; (6) shadow feature extraction module 36; (7) joint highlight/shadow feature calculation module 38; and (8) Bayesian discriminator 40. 
     Each module of mine discriminator 22 is specifically optimized to mine discrimination. Mine discriminator 22 is set up so that images are assumed to be in starboard format. Port-side images can be represented as starboard images using known techniques. As used in discriminator 22, the track or row index is represented by i or x, and the range or column index is represented by j or y. 
     The original shipper cluster 24 from the cuers 16, 18 and 20 is expanded on the top, left and bottom borders by Δ 1  and to the right by Δ 2 . The preferred expansion values are Δ 1  =6, and Δ 2  =20. The expansion of the snippet clusters 24 allows margins for filtering operations and captures long shadow areas. The expanded snippet is then filtered by the two dilation operations and one erosion operation. Original snippets that exceed an area bound are declared false alarms and are not processed. 
     The highlight emphasis module 26 coalesces highlight areas that are close together by using two dilation operations followed by an erosion operation. Dilation and erosion have the following definitions: 
     (1) Let points (s k , t k ) be in set S. Let I A  be an image and let I B  be the result of dilating (eroding) I A  by S. 
     (2) Dilation: 
     I B  (i,j)=maximum [I A  (i+s, j+t)](s,t)εS 
     (3) Erosion: 
     I B  (i,j)=minimum [I A  (i+s, j+t)](s,t)εS 
     The preferred choice for the set S for both dilation operations and the erosion operation for this module 26 is a disk of radius r. Thus, the set S is defined for integers s and t such that 
     
         s.sup.2 +t.sup.2 ≦r.sub.H.sup.2 
    
     where r is chosen as a function of the resolution of the sonar. For sonars used in mine hunting, a typical range is 1≦r H  ≦2. The first two dilation operations coalesce highlight areas that have small holes or that are slightly separated. The erosion operation reduces the highlight areas which have grown due to the dilation operations. 
     The highlight mask generation module 28 generates a highlight mask region by operating on the expanded, filtered, snippet 42. 
     Using the original image mean μ I  and standard deviation σ I , a highlight mask threshold 
     
         t.sub.HM =μ.sub.I +σ.sub.MH σ.sub.I 
    
     is computed (σ MH  =2.5 nominal) and used to produce a binary image where highlights equal or exceed the threshold. 
     A connectivity analysis is then done to compute the area A i , average intensity I i  and centroids x i , y i  of the blobs. Blobs whose area is less than A Hmin  (10) are eliminated. Blobs whose centroids are not within the borders of the original shipper cluster 24 before expansion are eliminated. The highlight blob with maximum product A i  I i  is then saved as the highlight mask 44 to be used in further processing. 
     The highlight feature extraction module 30 extracts highlight features 46 using the expanded but unfiltered snippet 24 and the highlight mask 44 previously generated. The following steps are used: 
     1. Let Ω H  be the points in the highlight mask 44 set and let I(i,j) be the greylevel of the unfiltered snippet 24. Set t H  =μ I  +α H  σ I  (α H  =1.0) 
     For all (i, j) εΩ H  define ##EQU1## 2. Compute Features: (a) Area: ##EQU2## (b) Moments: (i) Highlight strength: ##EQU3## (ii) Highlight Centroid: ##EQU4## (iii) Second Central Moments: ##EQU5## (iv) Major Moment: ##EQU6## (v) Minor Moment: ##EQU7## (c) Perimeter: Do a connectivity analysis of all blobs of binary image b(i,j). 
     Compute the total perimeter p H  of all blobs in b(i,j). 
     (d) Average Highlight Intensity: 
     
         I.sub.H =m.sub.o /A.sub.H 
    
     R.M.S. Error: 
     Let Ω HB  be the set where b(i,j)&gt;0. ##EQU8## 3. Compute six features for Bayesian Classifier if A H  is 2 or greater. ##EQU9## 
     The logarithm transform tends to yield a more Gaussian distribution to the features. Since λ Hmin  and e H  can be zero they are clamped at minimum values of 0.1 and 0.01 respectively. The R.M.S. error measures the noise in the highlight blob. 
     The shadow emphasis module 32 detects shadows by looking for the absence of speckle. The expanded snippet is filtered by a constant m(2) row by n(3) column low pass filter to coalesce shadow areas. The filtered shipper is dilated using a disk of radius r S  (1.5). The snippet is dilated a second time by a horizontal (range) set of length l S  (3). The second dilation step broadens small speckle blobs such that the speckle dominates the shipper except in the shadow areas. This makes it easier to detect the shadows. 
     The shadow mask generation module 34 generates a mask 50 of important shadow areas by operating on the filtered snippet 48 prepared by the shadow emphasis module 32. 
     In shadow mask generation module 34, the mean of the filtered snippet 48 is computed and a binary image of the snippet is created by setting pixels high if they are less than or equal to 0.4 μ snippet . All shadow blobs below area A Smin  (15) are deleted. Moreover, all shadow blobs whose centroid is not between the top and bottom original snippet boundaries and not to the right of the original left snippet boundary are also deleted. If the snippet was found to have a valid highlight mask 28 with centroid i Hc , j Hc  then any shadow blob whose minimum j value is less than j Hc  and whose row centroid is not within n S  pixels of i Hc  where 3≦n S  ≦j 6 is deleted. The remaining shadow mask areas are dilated by a disk of radius r SM  (1 to 2). 
     The last dilation step expands the shadow mask blobs and also coalesces some of them. Unlike the highlight mask 28 which is always a single blob, the shadow mask may be several disjoint blobs that trail the highlight. The above steps eliminate many false detections by requiring the shadow blobs to follow the highlight mask 28 where a highlight has been detected. 
     The shadow feature extraction module 36 extracts shadow features 52 using the expanded but unfiltered snippet 24 and the shadow mask 50 previously generated. The following steps are used in calculating the features: 
     1. Let Ω S  be the points in the shadow mask 50 set. 
     Set 
     
         t.sub.S =B.sub.S μ.sub.I 0.4≦B.sub.S ≦0.6 
    
     For all (i, j) εΩ S  define ##EQU10## 2. Compute features: ##EQU11## (b) Moments: (i) Shadow Centroid: ##EQU12## (ii) Second Central Moments: ##EQU13## (iii) Major Moment: 
     
         λ.sub.Smax =0.5 (a+c[(a-c).sup.2 +4b.sup.2 ].sup.1/2) 
    
     (iv) Minor Moment: 
     
         λ.sub.Smin =(ac-b.sup.2)/λ.sub.Smax 
    
     (c) Extent: 
     Find the minimum and maximum value of i for which g(i, j )=1. 
     (i) Vertical extent, a long track 
     
         Δx.sub.s =i.sub.max -i.sub.min 
    
     Find the minimum and maximum value of j for which g(i,j)=1. 
     (ii) Horizontal extent, in range 
     
         Δy.sub.s =j.sub.max -j.sub.min 
    
     (d) Perimeter: 
     Do a connectivity analysis of all blobs of binary image g(i,j). Compute total perimeter P S  of all blobs in g(i,j). 
     3. Compute six features for Bayesian discriminator 40 if A S  is 2 or greater. ##EQU14## 
     It is possible to compute the depth or darkness of the shadow in a fashion similar to the average highlight intensity. However, the grey level intensity in a shadow is a function of the noise level and thus is not highly correlated with the object producing the shadow. 
     Mine targets generally have both highlight features 46 and shadow features 52 although not always. When both do occur, a set of features 54 based on the geometrical relation of the shadow to the highlight can be calculated by the joint highlight/shadow feature extraction module 38. The following steps define these features: 
     1. From the highlight and shadow calculations, retrieve the following or compute if necessary. 
     (a) Highlight Centroid: i Hc , j Hc   
     (b) Highlight maximum extent in range: j Hmax   
     (c) Shadow Centroid i Sc , j Sc   
     (d) Shadow minimum extent in range: j Smin   
     2. Compute the following joint features: 
     (a) Average Vertical Difference: 
     
         Δx.sub.H/S= i.sub.Hc -i.sub.Sc 
    
     (b) Horizontal Separation 
     
         Δy.sub.H/S =j.sub.Hmax -j.sub.Smin 
    
     Other parameters such as percent overlap in the vertical direction of the shadow extent with the highlight extent can be defined, but the above are preferred. The use of the centroids for vertical difference is less sensitive to noise than extent measurements since it is averaged over the blob area. With these, two additional features, joint highlight/shadow feature extraction module computes the following two features for the Bayesian discriminator 40. 
     
         x.sub.13 =Δx.sub.H/S 
    
     
         x.sub.14 =Δy.sub.H/S 
    
     The logarithm transform is not used since both quantities x 13  and x 14  can be negative. 
     The Bayesian discriminator 40 processes subsets of the fourteen features previously defined to confirm or deny the snippet as a mine. The Bayesian discriminator 40 has the following functional form when discriminating between two classes: Let 
     
         r(x)=f.sub.M (x)/(f.sub.M (x)+f.sub.N (x)) 
    
     where f M  (x) is the conditional distribution of feature vector x for snippets of mines and f N  (x) is the conditional distribution of feature vector x for snippets of non-mine areas. Using a threshold t chosen to balance the risk of missed detections against the occurrence of too many false alarms, the snippet is declared a mine if 
     
         r(x)≧t. 
    
     The definitions of f M  (x) and f N  (x) depend on four possible outcomes: 
     1. Highlight and shadow detected in snippet; 
     2. Highlight only detected in snippet; 
     3. Shadow only detected in snippet; or 
     4. Neither highlight nor shadow detected in snippet. 
     The Bayesian discriminator 40 is initialized using a training set of data in which the locations of mines are known. From this set the following statistics are gathered. 
     
         ______________________________________     Mines       Non Mines                        Co-             Co-                        Var-            Var-Outcome  Features No.    Mean  iance                             No.  Mean  iance______________________________________1      x1 to x14           N.sub.M1                  μ.sub.M1                        Σ.sub.M1                             N.sub.N1                                  μ.sub.N1                                        Σ.sub.N12      x.sub.1 to x.sub.6           N.sub.M2                  μ.sub.M2                        Σ.sub.M2                             N.sub.N2                                  μ.sub.N2                                        Σ.sub.N23      x.sub.7 to x.sub.12           N.sub.M3                  μ.sub.M3                        Σ.sub.M3                             N.sub.N3                                  μ.sub.N3                                        Σ.sub.N34               N.sub.M4          N.sub.N4______________________________________ 
    
     With these statistics a multivariate normal distribution is used to approximate the distributions of the first three outcomes. 
     The dimension of x, μ and Σ is a function of the outcome. For the fourth outcome x, μ and Σ are undefined, only the number of occurrences N M4  and N N4  are defined. For i=1 to 3 the distributions are f Mi  (x)= ##EQU15## and f Ni  (x)= ##EQU16## where n i  is the number of features 54, that is, the dimension of x. For the fourth outcome, r=N M4  /(N M4  +N N4 ). 
     These algorithms were coded in C and executed on a SUN workstation. A set of 60 sonar images, 512 by 1024 pixels with some containing mines and for which ground truth on the location of the mines was known, was used to initialize the discriminator. FIG. 3 shows the performance of the discriminator in which the fraction of mines correctly classified is plotted against the fraction of false alarms incorrectly classified. 
     The use of morphological filters consisting of two dilations followed by an erosion operation on the greylevel snippet data 24 improves the detection of highlights associated with mines by coalescing highlight areas that are sometimes fractured. 
     The generation of a highlight mask 44 from the above filtered image 42 using rules concerning mask area and mask position within the snippet greatly increases the probability that the correct highlight area is identified while eliminating highlight areas of no significance. The use of a mask 44 to define the highlight area of interest allows highlight features 46 to be computed over highlights that may have disjoint segments. 
     The calculation of six highlight features 46 using the original unfiltered greyscale data within the highlight mask area makes maximal use of shape, intensity and high frequency texture data within the snippet. The use of the logarithm transformation on the calculated features not only produces variates that are approximately normal in distribution for ease in implementation in the Bayesian classifier 40, but also eliminates the need for other features which are products of powers of the basic features. Hence compactness which is defined as A/4πp 2  need not be computed since, under the logarithm transformation, it is a linear combination of log A and log p. 
     The use of a linear low pass filter on the greylevel snippet data smooths and coalesces shadow areas while at the same time removes low level speckle in the shadow areas. High level speckle in the background area, though reduced, still remains significant. The use of two morphological filters consisting of dilation by a disk and dilation by a horizontal structuring element coalesces the speckle in background areas and highlight areas. Since shadow areas have very little speckle this second filtering operation greatly increases the contrast between shadow areas and non-shadow areas. This simplifies the shadow mask generation. 
     The generation of a shadow mask 50 using rules concerning mask area, position within the snippet and geometrical relations to the highlight mask greatly increases the probability that the correct shadow areas have been identified while eliminating shadow areas of no significance. The use of a mask 50 to define shadow areas of interest allows shadow features 52 to be computed over shadow areas that may be disjoint. 
     The calculation of six shadow features 52 using the original unfiltered greyscale data within the shadow mask area makes maximal use of the shape information in the snippet. Since speckle noise sets a floor for shadow greyscale values, the shadow features do not use either intensity or noise level and thus differ from highlight features. Thus the features selected are optimized to the shadow characteristics. 
     The use of joint highlight/shadow position features 54 increases the probability of correct detection for a given false alarm rate. 
     The Bayesian discriminator 40 makes optimal use of the information found in the snippet by having a separate classifier for each of the four possible outcomes. The use of logarithm mapping functions increases the goodness of fit of the multivariate normal distribution to the experimental distributions. 
     In the foregoing specification certain preferred practices and embodiments of this invention have been set out, however, it will be understood that the invention may be otherwise embodied within the scope of the following claims.