Abstract:
The Target Separation Algorithms (TSAs) are used to improve the results of Automated Target Recognition (ATR). The task of the TSAs is to separate two or more closely spaced targets in Regions of Interest (ROIs), to separate targets from objects like trees, buildings, etc., in a ROI, or to separate targets from clutter and shadows. The outputs of the TSA separations are inputs to ATR, which identify the type of target based on a template database. TSA may include eight algorithms. These algorithms may use average signal magnitude, support vector machines, rotating lines, and topological grids for target separation in ROI. TSA algorithms can be applied together or separately in different combinations depending on case complexity, required accuracy, and time of computation.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    Imaging applications such as synthetic aperture radar (SAR) create two-dimensional maps (bitmaps) of regions, where the images consist of a two-dimensional grid of different signal strengths (magnitudes). These grids break down further into regions of interest (ROIs, also called chips), that is, regions where there is something other than background being imaged, such as objects or possible targets (objects of interest). Chips break down into clusters, that is, sets of pixels having a particular property, such as a similar signal magnitude. The chips are processed to reveal any objects (e.g., cars, trees, buildings, etc.) that the imaging application detected as well as any objects of interest (also known as targets, and include predefined objects such as tanks, planes, etc.). Automated target recognition (ATR) is a process that identifies targets based on a template database. 
         [0002]    ATR uses target images for input. Distinct target images—that is, each target separately identified and differentiated from background (clutter) or other objects—enhance ATR reliability. The differentiation of objects from background, of objects of interest (targets) from other objects, and of targets from other targets are thus important, but often difficult, processes. 
         [0003]    There is a need for improved separation of closely spaced targets in a ROI for applications such as SAR. Improved target recognition results in improved ATR. 
       SUMMARY OF THE INVENTION 
       [0004]    The system and method of the invention separate multiple objects appearing in regions of interest (ROIs) of imaging applications such as synthetic aperture radar (SAR). More specifically, the system takes images (two-dimensional grids of signal magnitudes) along with ROIs within the images (and clusters of pixels within each ROI) and identifies and separates objects from background (clutter), targets (objects of interest) from other objects, and targets from targets. In particular, in one embodiment, the system uses eight different approaches: 
         [0005]    (1) rough separation of targets and objects from clutter and shadow using average signal magnitude, 
         [0006]    (2) separation of two clusters by signal magnitude, 
         [0007]    (3) separation of multiple clusters by signal magnitude, 
         [0008]    (3A) clutter filtering (removal of small areas of clutter), 
         [0009]    (3B) target restoring (filling in of small gaps in a target), 
         [0010]    (4) target separation using support vector machines (identifying a border between two or more targets of different average signal magnitude), 
         [0011]    (5) target separation using rotating lines (rotating a line about a center of mass to separate two or more clusters), and 
         [0012]    (6) target separation using horizontal and vertical grids. 
         [0013]    The system works in two stages. Stage 1 uses average signal magnitude to do the separation, as typified by Algorithms 1, 2, 3, 3A, 3B, and 4. Stage 2 uses topological (geometrical) methods for the separation, as typified in Algorithms 5 and 6. Either stage is optional, as are any of the algorithms. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]    The foregoing and other aspects of embodiments of this invention are made more evident in the following Detailed Description of Exemplary Embodiments, when read in conjunction with the attached Drawing Figures, wherein: 
           [0015]      FIG. 1  is a functional block diagram illustrating an overview of the target recognition process in an exemplary embodiment of the invention. 
           [0016]      FIG. 2  illustrates a goal of the invention, namely the separation of two closely spaced targets in a ROI (region of interest, or chip) by a linear border. 
           [0017]      FIG. 3  depicts a more challenging objective of the invention, namely the separation of a target (object of interest) from a nearby overlapping object (in this case a tree) in a ROI, again using a linear border. 
           [0018]      FIG. 4  carries the separation goal of  FIGS. 2-3  even further, showing the separation of a target from a nearby building in a chip using a non-linear border. 
           [0019]      FIG. 5  is a functional block diagram illustrating the first part of Phase 1 of an exemplary embodiment of the invention. 
           [0020]      FIG. 6  is a functional block diagram depicting the second part of Phase 1 of an exemplary embodiment of the invention. 
           [0021]      FIG. 7  is a functional block diagram showing Phase 2 of an exemplary embodiment of the invention. 
           [0022]      FIG. 8  is a diagram of the last part of Phase 2 of an exemplary embodiment of the invention. 
           [0023]      FIG. 9  shows a continuum of signal magnitudes by which targets can be separated using an embodiment of the invention (Algorithm 1). 
           [0024]      FIG. 10  shows the pixel windows used by the clutter filtering and target restoring algorithms in an example of the invention. 
           [0025]      FIG. 11  depicts the support vector machines approach (Algorithm 4) used to do a separation of linearly separable clusters (targets) in an exemplary embodiment of the invention. 
           [0026]      FIG. 12  illustrates the use of a line (expressed in linear form) to separate two overlapping clusters using a linear border. 
           [0027]      FIG. 13  shows the separation of two targets by linear border using the rotating lines (topological) method (Algorithm 5). 
           [0028]      FIG. 14  shows the rotating lines method using a shift of the center of mass to find a more appropriate rotation point for the lines, which leads to better target separation in an exemplary embodiment of the invention. 
           [0029]      FIG. 15  shows the horizontal grids approach (Algorithm 6) used to separate two targets in an example of the invention. 
           [0030]      FIG. 16  is an illustration of an example Moving and Stationary Target Acquisition and Recognition (MSTAR) image (bitmap) containing two targets in the ROI. 
           [0031]      FIG. 17  shows the same image after clutter has been removed using average signal magnitude (Algorithm 1) in an exemplary embodiment of the invention. 
           [0032]      FIG. 18  shows the next step of processing the same image, namely clutter filtering (Algorithm 3A) in an exemplary embodiment of the invention. 
           [0033]      FIG. 19  shows the next step of processing the same image, namely target restoring (Algorithm 3B) in an exemplary embodiment of the invention. 
           [0034]      FIG. 20  depicts the rotating lines algorithm (Algorithm 5) as the next step of processing the same image in an exemplary embodiment of the invention. 
           [0035]      FIG. 21  shows the best of the separating lines from the rotating lines approach in processing the same image in an exemplary embodiment of the invention. 
           [0036]      FIG. 22  shows a similarly processed image, only with an artificial object inserted, to test the horizontal grids method (Algorithm 6). 
           [0037]      FIG. 23  shows an intermediate step of Algorithm 6 on the same processed image in an exemplary embodiment of the invention. 
           [0038]      FIG. 24  shows the rotating lines portion after the horizontal grids processing of the same image in an exemplary embodiment of the invention. 
           [0039]      FIG. 25  depicts the resulting separation after completion of the horizontal grids approach on the same image in an exemplary embodiment of the invention. 
           [0040]      FIG. 26  shows the original image with the resulting linear border from the rotating lines approach shown in  FIG. 21 . 
       
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
       [0041]    The illustrative embodiments that follow are only exemplary applications of the present invention and not intended to limit the scope of the invention. 
         [0042]    The Target Separation Algorithms (TSAs) improve the results of the Automatic Target Recognition (ATR) process in imaging applications like Synthetic Aperture Radar (SAR) bitmap interpretation. Before attempting to identify specific targets using ATR, it helps to separate the different objects and targets (objects of interest) from the background and from each other. 
         [0043]    The automatic recognition process is shown on  FIG. 1 . The input for this process is a SAR image (bitmap)  100 . Three coordinates characterize each pixel of this image: the row number x and column number y in the bitmap along with the signal magnitude P(x,y). The first step of recognition is Automated Target Cueing (ATC)  110 . In this step, the system localizes Regions of Interest (ROIs, also called chips) in the SAR bitmap. Chips are small areas on the bitmap which contain possible targets. Then ATC deletes all chips that contain no possible target images. The second step—Automated Target Recognition (ATR)  130 —recognizes each image in each chip and identifies whether the image is a target  140  (along with type and label of this target). 
         [0044]    When one chip contains two or more closely spaced targets, however, or when a target in close proximity to objects (like trees, buildings, etc.), ATR either does not recognize targets in the chip or recognizes them incorrectly. The TSAs  120  work between ATC and ATR to improve the recognition process. The TSAs separate two (or more) closely spaced targets or separate targets  140  from objects in chips (see  FIGS. 2-4 ). 
         [0045]    In  FIG. 2 , the example chip  200  contains two targets  210  that are distinguishable from the surrounding background (clutter)  220 . A linear border  230  separates the two targets. 
         [0046]      FIG. 3  is similar. There is still a chip  300 , target  310 , and clutter  320 , but another object, in this case a tree  330 , replaces the second target. Furthermore, the tree intersects with the target in an overlap region  340 . This causes the linear border  350  to intersect a small portion of the tree in this linear separation of target from tree. 
         [0047]    Finally, in  FIG. 4 , the chip  400 , target  410 , and clutter  420  are joined by a building  430 , which partially surrounds the target. In this case, a non-linear border  440  separates the target from the building. 
         [0048]    The flow of TSA processing is shown in  FIGS. 5-8 . TSA processing includes two stages: 
         [0049]    Stage 1 is optional. It comprises separating target from clutter and shadows using the average signal magnitude of pixels in the cluster (where a cluster is a set of pixels being processed). Referring to  FIG. 5 , the input to the TSA processing is a chip  500 . From this, the system uses average signal magnitude  510  to separate objects and clutter. Next, clutter filtering  520  removes spurious pieces of clutter in the processed image that mistakenly show up as an object. Continuing with  FIG. 6 , target restoring  600  removes spurious pieces of clutter in the processed image that mistakenly show up within an object. In some cases, average signal magnitude is sufficient  610  to separate these targets and objects, from both themselves and the clutter. If this is the case, the clusters are separable by average signal magnitude (defined below), so apply Support Vector Machines  620  to separate these clusters (targets) by a linear or a nonlinear border. Stage 1 is optional because it is not necessary to separate targets from clutter before separating targets in stage 2, but it can increase the accuracy of separation and create better images of targets for recognition in ATR. 
         [0050]    Stage 2 comprises separating two or more targets, or targets and objects, using topological (geometrical) methods. When average signal magnitude is insufficient to separate all the targets from the other objects and the clutter, topological (geometrical) methods  630  are used. Referring to  FIG. 7 , start first with rotating lines about a center of mass  700 , adjusting the axis of rotation outward from the center of mass to find the best such line. Alternatively, or in addition, try separating the clusters using horizontal or vertical grids  710 . Finishing with  FIG. 8 , if the clusters can be separated by topological methods (rotating lines or horizontal or vertical grids)  800 , then they are separable by a linear or non-linear border  810  (just like the separation by average signal magnitude case). 
       TSA Stage 1 
       [0051]    Consider a chip (ROI) to be a closed area A in a two-dimensional space. Set S is a set of all points (pixels) in area A. Every point K belonging to area A has coordinates (x k ,y k ) and power (signal magnitude) P(x k ,y k ) Consider any pattern in A, such as a target, an object, clutter, or shadow, to be a cluster C (subset of points in A). Assume that any cluster has its own unique average signal magnitude. 
         [0000]    Algorithm 1: Rough Separation of Targets and Objects from Clutter and Shadow 
         [0052]    Algorithm 1 is useful when targets and objects have a different average magnitude than clutter and shadow. The following is an exemplary embodiment: 
         [0053]    Step 1. Find 
         [0000]    
       
         
           
             
               P 
               min 
             
             = 
             
               
                 min 
                 
                   
                     ( 
                     
                       x 
                       , 
                       y 
                     
                     ) 
                   
                   ∈ 
                   A 
                 
               
                
               
                 ( 
                 
                   P 
                    
                   
                     ( 
                     
                       x 
                       , 
                       y 
                     
                     ) 
                   
                 
                 ) 
               
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               P 
               max 
             
             = 
             
               
                 max 
                 
                   
                     ( 
                     
                       x 
                       , 
                       y 
                     
                     ) 
                   
                   ∈ 
                   A 
                 
               
                
               
                 
                   ( 
                   
                     P 
                      
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
         [0054]    Step 2. Divide the interval [P min ,P max ] into two subintervals, [P min ,P 1 ] and (P 1 ,P max ], where P 1  is a parameter—for example, it can be a middle of interval [P min ,P max ]. Define two clusters C and D: C={(x,y):P(x,y)ε[P min ,P 1 ]} and D={(x,y):P(x,y)ε(P 1 ,P max ]}. 
         [0055]    Step 3. For all (x,y)εC, set P(x,y)=0. 
         [0056]    Algorithm 1 treats all points from cluster C in area A as possible clutter (or shadow) and deletes them from the chip while treating all points from cluster D as a possible target (or object) and leaves them alone. For an example use of Algorithm 1, see  FIGS. 16-17 .  FIG. 16  shows a Moving and Stationary Target Acquisition and Recognition (MSTAR) image (bitmap) with two closely spaced targets in the ROI.  FIG. 17  shows the same image after applying Algorithm 1 (deleting clutter and shadows). 
         [0057]    Algorithm 2: Separation of Two Clusters by Signal Magnitude 
         [0058]    Algorithm 2 can be used to separate two clusters (e.g., target and clutter, target and target) in the ROI that have different average magnitude. Though this algorithm is more complicated than Algorithm 1, it is generally more accurate. Algorithm 2 uses an iterative procedure to compute the maximum variation ΔP on the interval [P min ,P max ]. See  FIG. 9 . For some cases, Algorithm 2 can separate two targets in the ROI by using average cluster magnitude (when the average signal magnitudes for the two targets in the chip are different). Here is an example embodiment: 
         [0059]    Step 1. Find 
         [0000]    
       
         
           
             
               P 
               min 
             
             = 
             
               
                 min 
                 
                   
                     ( 
                     
                       x 
                       , 
                       y 
                     
                     ) 
                   
                   ∈ 
                   A 
                 
               
                
               
                 ( 
                 
                   P 
                    
                   
                     ( 
                     
                       x 
                       , 
                       y 
                     
                     ) 
                   
                 
                 ) 
               
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               P 
               max 
             
             = 
             
               
                 max 
                 
                   
                     ( 
                     
                       x 
                       , 
                       y 
                     
                     ) 
                   
                   ∈ 
                   A 
                 
               
                
               
                 
                   ( 
                   
                     P 
                      
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
         [0060]    Step 2. Let n represent the number of subintervals. Start with n=2. 
         [0061]    Step 3. Divide the interval [P min ,P max ] into n equal parts: [P min ,P 1   n ], (P 1   n ,P 2   n ], . . . , (P n−1   n ,P max ]. 
         [0062]    Step 4. For j=1, 2, . . . , n−1, do the following:
       1. Divide set S into two subsets, C j   n  and D j   n , as follows:       
 
         [0000]        C   j   n ={( x,y ): P   min   ≦P ( x,y )≦ P   j   n } and  D   j   n ={( x,y ): P   j   n   &lt;P ( x,y )≦ P   max }.
       If the number of pixels in either C j   n  or D j   n  falls below N min , the minimum cluster size, then skip the calculations in the next two substeps for this j and set a threshold ΔP j   n =0.   2. Calculate  P j   n   =the average P(x,y) for set C j   n  and  Q j   n   =the average P(x,y) for set D j   n .   3. Calculate the threshold ΔP j   n =  Q j   n   −  P j   n   . If ΔP j   n &lt;t min , where t min  is the tolerance used to decide if clusters are separable, then set a threshold ΔP j   n =0.       
 
         [0067]    Step 5. Calculate the maximum threshold 
         [0000]    
       
         
           
             
               Δ 
                
               
                   
               
                
               
                 P 
                 max 
                 n 
               
             
             = 
             
               
                 max 
                 
                   1 
                   ≤ 
                   j 
                   &lt; 
                   n 
                 
               
                
               
                 ( 
                 
                   Δ 
                    
                   
                       
                   
                    
                   
                     P 
                     j 
                     n 
                   
                 
                 ) 
               
             
           
         
       
     
         [0000]    and a maximum threshold index k n , where ΔP k      n     n =ΔP max   n . See  FIG. 9 . 
         [0068]    Step 6. Increase the number of subintervals: n=n+1. Return to Step 3. 
         [0069]    Repeat steps 3-6 until the value ΔP max   n  no longer increases significantly with increasing index n, that is, until ΔP max   n+1 −ΔP max   n &lt;t max , where t max  is the tolerance used to control the iterative calculation of ΔP max   n . Value ΔP k      n     n ε([P min ,P max ] on the last iteration (steps 3-6) is the best separation border point, with maximum threshold ΔP max   n , which separates set S into two clusters (objects), ΔC k      n     n , and ΔD k      n     n . Note that if ΔP max   n =0 on the last iteration, then the clusters C k      n     n  and D k      n     n  are not separable by signal magnitude P in area A. That is, Algorithm 2 can only discern one target in A in such a case. 
       Algorithm 3: Separation of r Clusters by Signal Magnitude 
       [0070]    Algorithm 3 can separate r clusters (representing several targets) in the ROI, provided the average signal magnitudes for the r targets in the chip are different. This is a generalization of the approach used for two-object separation in Algorithm 2. In particular, this algorithm does a separation of S into r clusters C 1 , C 2 , . . . , C r  in area A. Here is a sample approach: 
         [0071]    Step 1. Find 
         [0000]    
       
         
           
             
               P 
               min 
             
             = 
             
               
                 min 
                 
                   
                     ( 
                     
                       x 
                       , 
                       y 
                     
                     ) 
                   
                   ∈ 
                   A 
                 
               
                
               
                 ( 
                 
                   P 
                    
                   
                     ( 
                     
                       x 
                       , 
                       y 
                     
                     ) 
                   
                 
                 ) 
               
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               P 
               max 
             
             = 
             
               
                 max 
                 
                   
                     ( 
                     
                       x 
                       , 
                       y 
                     
                     ) 
                   
                   ∈ 
                   A 
                 
               
                
               
                 
                   ( 
                   
                     P 
                      
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
         [0072]    Step 2. Let n represent the number of subintervals. Start with n=r. 
         [0073]    Step 3. Divide the interval [P min ,P max ] into n equal parts: [P min ,P 1   n ], (P 1   n ,P 2   n ], . . . , (P n−1   n ,P max ]. 
         [0074]    Step 4. Choose r−1 values Q 1 , Q 2 , . . . , Q r−1  from {P 1   n , P 2   n , . . . , P n−1   n } and divide the interval [P min ,P max ] into r subintervals [P min ,Q 1 ], (Q 1 ,Q 2 ], . . . , (Q r−1 ,P max ]. There are 
         [0000]    
       
         
           
               
             
               ( 
               
                 
                   
                     
                       n 
                       - 
                       1 
                     
                   
                 
                 
                   
                     
                       r 
                       - 
                       1 
                     
                   
                 
               
               ) 
             
           
         
       
     
         [0000]    ways to choose such values; index these combinations 
         [0000]    
       
         
           
             1 
             , 
             2 
             , 
             … 
              
             
                 
             
             , 
             
               
                 ( 
                 
                   
                     
                       
                         n 
                         - 
                         1 
                       
                     
                   
                   
                     
                       
                         r 
                         - 
                         1 
                       
                     
                   
                 
                 ) 
               
               . 
             
           
         
       
     
       For 
       [0075]    
       
         
           
             
               j 
               = 
               1 
             
             , 
             2 
             , 
             … 
              
             
                 
             
             , 
             
               ( 
               
                 
                   
                     
                       n 
                       - 
                       1 
                     
                   
                 
                 
                   
                     
                       r 
                       - 
                       1 
                     
                   
                 
               
               ) 
             
             , 
           
         
       
     
         [0000]    take the corresponding combination of values Q 1   j , Q 2   j , . . . , Q r−1   j  and perform the following:
       1. Divide set S into r subsets S 1   j , S 2   j , . . . , S r   j  as follows:       
 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       S 
                       1 
                       j 
                     
                     = 
                     
                       { 
                       
                         
                           ( 
                           
                             x 
                             , 
                             y 
                           
                           ) 
                         
                         : 
                         
                           
                             P 
                             min 
                           
                           ≤ 
                           
                             P 
                              
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                           ≤ 
                           
                             Q 
                             1 
                             j 
                           
                         
                       
                       } 
                     
                   
                   , 
                 
               
             
             
               
                 
                   
                     
                       S 
                       2 
                       j 
                     
                     = 
                     
                       { 
                       
                         
                           ( 
                           
                             x 
                             , 
                             y 
                           
                           ) 
                         
                         : 
                         
                           
                             Q 
                             1 
                             j 
                           
                           &lt; 
                           
                             P 
                              
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                           ≤ 
                           
                             Q 
                             2 
                             j 
                           
                         
                       
                       } 
                     
                   
                   , 
                 
               
             
             
               
                 ⋮ 
               
             
             
               
                 
                   
                     S 
                     r 
                     j 
                   
                   = 
                   
                     
                       { 
                       
                         
                           ( 
                           
                             x 
                             , 
                             y 
                           
                           ) 
                         
                         : 
                         
                           
                             Q 
                             
                               r 
                               - 
                               1 
                             
                             j 
                           
                           &lt; 
                           
                             P 
                              
                             
                               ( 
                               
                                 x 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                           ≤ 
                           
                             P 
                             max 
                           
                         
                       
                       } 
                     
                     . 
                   
                 
               
             
           
         
       
       
         
           
             If the number of pixels in any of S 1   j , S 2   j , . . . , S r   j  falls below N min , the minimum cluster size, then skip the calculations in the next three substeps for this combination and set a combination threshold ΔP j =0. 
             2. Calculate  P 1   j    the average P(x,y) for set S 1   j ,  P 2   j   =the average P(x,y) for set S 2   j , . . . ,  P r   j   =the average P(x,y) for set S r   j    
             3. Calculate the individual thresholds P 1   j =  P 2   j   −  P 1   j   , ΔP 2   j =  P 3   j   −  P 2   j   , . . . , ΔP r−1   j =  P r   j   −  P r−1   j   . If any of these thresholds are less than to t min , where t min  is the tolerance used to decide if clusters are separable, then skip the calculation in the last substep and set a combination threshold ΔP j =0. 
             4. Calculate the combination threshold 
           
         
       
     
         [0000]    
       
         
           
             
               Δ 
                
               
                   
               
                
               
                 P 
                 j 
               
             
             = 
             
               
                 min 
                 
                   1 
                   ≤ 
                   i 
                   &lt; 
                   r 
                 
               
                
               
                 
                   ( 
                   
                     Δ 
                      
                     
                         
                     
                      
                     
                       P 
                       i 
                       j 
                     
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
         [0081]    Step 5. Calculate the maximum threshold 
         [0000]    
       
         
           
             
               Δ 
                
               
                   
               
                
               
                 P 
                 max 
                 n 
               
             
             = 
             
               
                 max 
                 
                   1 
                   ≤ 
                   j 
                   ≤ 
                   
                     ( 
                     
                       
                         
                           
                             n 
                             - 
                             1 
                           
                         
                       
                       
                         
                           
                             r 
                             - 
                             1 
                           
                         
                       
                     
                     ) 
                   
                 
               
                
               
                 ( 
                 
                   Δ 
                    
                   
                       
                   
                    
                   
                     P 
                     j 
                   
                 
                 ) 
               
             
           
         
       
     
         [0000]    a maximum threshold index k n , where ΔP k     n   =ΔP max   n . 
         [0082]    Step 6. Increase the number of subintervals: n=n+1. Return to Step 3. 
         [0083]    Repeat steps 3-6 until the value ΔP max   n  no longer increases significantly with increasing index n, that is, until ΔP max   n+1 −Δ max   n &lt;t max , where t max  is the tolerance used to control the iterative calculation of ΔP max   n . Values Q 1   k     n   , Q 2   k     n   , . . . , Q r−1   k     n   ε(P min ,P max ) on the last iteration (steps 3-6) are the best separation border points, with maximum threshold ΔP max   n , which separates set S into r objects S 1   k     n   , S 2   k     n   , . . . , S r−1   k     n.      
       Algorithm 3A (Clutter Filtering) 
       [0084]    After separating targets from clutter using Algorithm 1, 2, or 3 and deleting clutter from A (i.e., setting P(x,y)=0 for all clutter points (x,y), see step 3 of Algorithm 1), Clutter Filtering can “clean” area A. This procedure deletes single or small groups of separated pixels of clutter in A which were not deleted by clutter separation in Algorithm 1, 2, or 3. 
         [0085]    Referring to  FIG. 10 , create a  1010  mask window M (the shaded portion), and move this window across area A (across all columns and rows of pixels in A). The size of window M is a parameter of the Clutter Filtering algorithm. As soon as the partial image A p  (under M) in area A is identical to mask window M (that is, the portion under the shaded area is all clutter), delete the pixels from the central part (unmasked portion) of A p . 
         [0086]    For an example of Clutter Filtering, consider  1010 , a 16-pixel clutter filtering mask window M, where the mask consists of the 12 pixels on the outside edge. The four central (unmasked) pixels in the window can represent “target” (i.e., P(x,y)&gt;0) or “clutter” (where P(x,y)=0); all other pixels in M must be clutter to activate clutter filtering. Consider the MSTAR image of a ROI after clutter separation (using Algorithm 1, see  FIG. 17 ). Each time when the central part of area A p  under window M has four or fewer “target” pixels, delete these pixels (i.e., set P(x,y)=0). The results of Clutter Filtering are shown on  FIG. 17  (before filtering) and  FIG. 18  (after filtering). 
       Algorithm 3B (Target Restoring) 
       [0087]    This procedure is the opposite of Clutter Filtering, namely restoring target pixels that were either missing or inadvertently deleted from A by using Algorithm 1, 2, or 3, or by Clutter Filtering. Referring to  FIG. 10 , target restoring consists of first creating a  1000  mask window R (the unshaded portion) and moving this window across area A. As soon as the partial image A p  (under R) in area A is identical to mask window R (that is, the portion under the unshaded area is all target), restore all pixels in the central part of A p  (e.g., for each such central pixel (x,y), set P(x,y) to some suitable nonzero value, say P max ). 
         [0088]    As an example of Target Restoring,  FIG. 18  shows an MSTAR image of the ROI after Clutter Filtering and before Target Restoring.  FIG. 19  shows the same image after Target Restoring using the 16-pixel mask window R (see  1000  in  FIG. 10 ). 
       Algorithm 4: Target Separation Using Support Vector Machines 
       [0089]    After applying Algorithm 2 or 3, there may be two or more clusters with different average signal magnitudes. Assume these average signal magnitudes are also different from the average clutter magnitude. In this case, Support Vector Machines (SVM) can separate these clusters (see  FIG. 11 ) by calculating the optimal linear or nonlinear border between the clusters (targets). For a good description of SVM, see Chapter 5, Vladimir N. Vapnik, The Nature of Statistical Learning Theory, (2nd ed., Springer 1999), the contents of which is herein incorporated by reference. Before describing SVM, a definition of separable clusters and overlaps is in order: 
         [0090]    Separation of Two Clusters with Overlaps by Linear Function (See  FIG. 12 ) 
         [0091]    Suppose we have a chip  1200  with two clusters, C 1    1210  and C 2    1220 , along with linear function y=Ax+B (assume the rest of the chip is clutter  1230 ). Transform the linear function y=Ax+B to a linear form: F(x,y)=A 1 x+B 1 y+E 1 , where A 1 =A, B 1 =−1, and E 1 =B. Then clusters C 1  and C 2  are said to be separated by  1250  linear function (border) y=Ax+B (that is, C 1  and C 2  are linearly separable) if either: 
         [0000]        F ( x,y )&gt;0 for all ( x,y )ε C   1  and  F ( x,y )&lt;0 for all ( x,y )ε C   2 , or  (1)
 
         [0000]        F ( x,y )&lt;0 for all ( x,y )ε C   1  and  F ( x,y )&gt;0 for all ( x,y )ε C   2 .  (2)
 
         [0092]    If instead, in case (1) for some point (x n ,y n ) from cluster C 1 , F(x n ,y n )=d n &lt;0 (i.e., region  1260 ), then we define this point to be an overlap and the value |d n | as the overlap distance (i.e., distance from point (x n ,y n ) to  1250  border F(x,y)=0). Likewise for case (1) for some point (x m ,y m ) from cluster C 2 , F(x n ,y n )=d m &gt;0 (region  1270 ), then we define this point to also be an overlap and the value |d m | as the overlap distance. For example, the overlap region  1240  has just such points from C 2 . Similar definitions for overlap extend to case (2). 
         [0093]    We describe the idea of SVM for a simple case (linearly separable clusters). See  FIG. 11 . Suppose we have two non-overlapping clusters (targets)  1110  in a two-dimensional Euclidian space  1100  and we have to separate these two clusters using an optimal straight line  1130 . In general, this is called the optimal separating hyperplane (OSH). By optimal separation, we mean a line that separates the two clusters onto different sides of the line and that equalizes the minimum distance from these clusters to the line. The minimum distance from a cluster to the OSH is a minimum of Euclidian distances (normal vectors) from every point in the cluster to the OSH. Therefore, optimization of cluster separation means that we have to find the largest empty margin between the two clusters and in the middle of this margin, we draw a straight-line border  1130 , i.e., the OSH. More generally, separable clusters in SVM can have overlaps  1140  and the OSH can be a nonlinear curve  1120  (or surface in 3-D space). 
         [0094]    For two separated clusters (Algorithm 2), we calculate one border using SVM, which separates two closely spaced targets in a chip. In the case of r clusters (Algorithm 3), we calculate borders between every pair of clusters and then unify all borders that belong to one cluster into one unified border surrounding this cluster. In this case, we separate r targets in a chip using SVM. 
         [0095]    As mentioned before, the borders can be described by a linear function (straight lines) or nonlinear functions (usually polynomial curves). In general, linear functions minimize computations while nonlinear functions maximize accuracy. 
         [0096]    Clusters can overlap each other. This means that after separating clusters and performing border computations, some points (pixels) of a cluster can be on the opposite side of the border and belong to another cluster. If the number of these points is too large (more than a certain percentage of all points in the cluster) or the overlaps (distances from these points to the OSH) are more than the maximum tolerance, then we declare that these clusters (objects) are not separable. 
       TSA Stage 2 
       [0097]    In stage 2, we use topological methods to separate targets in a chip. These methods are based not on average cluster magnitude but on geometrical locations of clusters in the ROI. If after stage 1 the targets are not separable by signal magnitude, then there is only one cluster C of targets (objects) and all other pixels in the ROI are deleted (clutter). If we did not apply stage 1, then we use the initial image in the ROI as a cluster C for separation. We suppose that cluster C contain two (or more) sub-clusters C 1 , and C 2  (two targets or objects) for separation. 
       Algorithm 5: Target Separation Using Rotating Lines and Center Shifts 
       [0098]    Algorithm 5 is a topological method of separating targets (see  FIGS. 13-14 ). For  FIG. 13 , suppose we have a chip  1300 , a cluster consisting of two targets  1310  and  1320 , and some clutter  1330 . Rotating lines involves finding a center of mass  1340  of the cluster and doing a line rotation about the center of mass  1340 . See, for example, lines  1350  and  1390 . The idea is that when the line intersects the cluster, like with line  1390 , it is not a good choice for separating the targets. The line is rotated until a better separation is achieved, like what happens with line  1350 , which does a linear separation of targets  1310  and  1320  by line y=A·x+B, with line  1350  corresponding to points that satisfy y−(A·x+B)=0, target  1310  falling on the side  1370  of the line, corresponding to y−(A·x+B)&gt;0, and target  1320  falling on the other side  1360  of the line, corresponding to y−(A·x+B)&lt;0. Should the center of mass  1340  not be suitable, it may be desirable to do a shift of the rotation point to a different location within a center shift area  1380  about the center of mass  1340 , as discussed below and in  FIG. 14 . 
         [0099]    For  FIG. 14 , suppose we have a chip  1400 , with two clusters  1410  and  1420 , along with some clutter  1430 , a center of mass  1460  of the two clusters, and a line rotation  1480  about the center of mass. When the line forms an intersection  1440  with a cluster, it is not a good choice for separating the clusters. As mentioned above, it may be desirable to do a shift  1470  in the center of mass to some other nearby point in order to find a better rotation position. The goal is to find a border  1450  that cleanly separates the two clusters. Here is an exemplary embodiment: 
         [0100]    Step 1. Calculate coordinates of the center of mass (x c ,y c ) for cluster C: 
         [0000]    
       
         
           
             
               x 
               c 
             
             = 
             
               
                 
                   ∑ 
                   
                     k 
                     = 
                     1 
                   
                   m 
                 
                  
                 
                     
                 
                  
                 
                   
                     x 
                     k 
                   
                    
                   
                     P 
                      
                     
                       ( 
                       
                         
                           x 
                           k 
                         
                         , 
                         
                           y 
                           k 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ∑ 
                   
                     k 
                     = 
                     1 
                   
                   m 
                 
                  
                 
                     
                 
                  
                 
                   P 
                    
                   
                     ( 
                     
                       
                         x 
                         k 
                       
                       , 
                       
                         y 
                         k 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               y 
               c 
             
             = 
             
               
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       1 
                     
                     m 
                   
                    
                   
                       
                   
                    
                   
                     
                       y 
                       k 
                     
                      
                     
                       P 
                        
                       
                         ( 
                         
                           
                             x 
                             k 
                           
                           , 
                           
                             y 
                             k 
                           
                         
                         ) 
                       
                     
                   
                 
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       1 
                     
                     m 
                   
                    
                   
                       
                   
                    
                   
                     P 
                      
                     
                       ( 
                       
                         
                           x 
                           k 
                         
                         , 
                         
                           y 
                           k 
                         
                       
                       ) 
                     
                   
                 
               
               . 
             
           
         
       
     
         [0101]    where m is the number of points in cluster C, x k  and y k  are the coordinates of a point (pixel) K belonging to cluster C, and P(x k ,y k ) is the magnitude of the signal at point K. Initialize center of border rotation (x r ,y r )=(x c ,y c ). 
         [0102]    Step 2. Initialize border rotation angle α=0 and rotation index i=0. 
         [0103]    Step 3. Calculate the initial linear border between clusters C 1  and C 2 . This is a horizontal straight line L 0 : y=y c . 
         [0104]    Step 4. Calculate the number of pixels N 0  intersected by line L 0  in cluster C. 
         [0105]    Step 5. i=i+1 and α=α+Δα, where Δα=π/n is a step of angle rotation of line L 0  and n (a parameter of the algorithm) is the number of steps by which to increment α, with 0≦α&lt;π. 
         [0106]    Step 6. Rotate line L 0  on angle α counterclockwise around point (x r ,y r ). This is line L i : y=Ax+B, where A=tan α(if α=π/2, then L i  is the line x=x c ) and B=y r −Ax r . 
         [0107]    Step 7. Calculate the number of pixels N i  intersected by line L i  in cluster C. Continue steps 5-7 while α&lt;π. 
         [0108]    Step 8. Calculate the optimal separated linear border L min  that intersects the minimum number of pixels in cluster C: 
         [0000]    
       
         
           
             
               N 
               min 
             
             = 
             
               
                 min 
                 
                   0 
                   ≤ 
                   i 
                   &lt; 
                   n 
                 
               
                
               
                 
                   ( 
                   
                     N 
                     i 
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
         [0109]    Step 9. Repeat steps 2-8 on each of the possible centers of rotation (x r ,y r ) in a predefined area A c  about (x c ,y c ), where x r  is within a predetermined quantity Δx of x c  and y r  is within a predetermined quantity Δy of y c . 
         [0110]    Step 10. Calculate the optimal separated linear border L that intersects the minimum number of pixels 
         [0000]    
       
         
           
             N 
             = 
             
               
                 min 
                 
                   
                     ( 
                     
                       
                         x 
                         r 
                       
                       , 
                       
                         y 
                         r 
                       
                     
                     ) 
                   
                   ∈ 
                   
                     A 
                     c 
                   
                 
               
                
               
                 
                   ( 
                   
                     N 
                     min 
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
         [0000]    This produces the best-separated linear border between clusters C 1  and C 2 . 
         [0111]    If the number N is less than some prespecified tolerance T (a parameter of the algorithm) and the number of pixels in clusters C 1  and C 2  are roughly comparable, then L is a linear border between the two clusters and it separates two targets in the chip. Note that we use the definition of separable clusters (see above) for calculating the number of pixels in C 1  and C 2  separated by linear form F(x,y). 
         [0112]    Note also that step 9 of Algorithm 5 is optional. It increases the possibility of finding the best position for a separated linear border. Computation time can be saved by using just one rotation of straight lines around the center of mass (steps 2-8). See  FIG. 13  for an example of rotating lines without shifting the center of mass. 
         [0113]      FIGS. 20-21  show the results of Algorithm 5 (after Algorithm 1, Clutter Filtering and Target Restoring were applied to the MSTAR image with two targets ( FIG. 16 )). The targets are separated by an optimal linear vertical border ( FIG. 21 ), which was defined using rotating lines around the center of mass (steps 2-8). In this case, the number of intersections with the target clusters N=0. The result of target separation in the ROI using Algorithm 5 is shown on  FIG. 26 . 
         [0114]    Separating targets in a chip using rotating lines in Algorithm 5 is not always efficient. For instance, the two targets may have a large overlap, or they may be so closely spaced that a straight line rotating around the center of mass does not properly separate them. In these cases, Algorithm 5 can be augmented or supplanted with Algorithm 6, which uses horizontal and vertical topological grids. Algorithm 6 can be used only after target and clutter separation (stage 1). 
       Algorithm 6: Target Separation Using Horizontal and Vertical Grids 
       [0115]    Algorithm 6 is another topological method of separating targets (see  FIG. 15 ). Suppose we have a chip  1500 , with two clusters  1510  and  1520 , along with some clutter  1530 . Target separation using horizontal grids consists of setting up a grid of horizontal lines (numbered  1 - 6  in  FIG. 15 ) that encompass the clusters. Then determine where each line crosses each cluster, ignoring small gaps  1540  in clusters and small pieces of noise  1550  in clutter. For those lines that cross both clusters (lines  3  and  4  in  FIG. 15 ), find their midpoints between the clusters (e.g., midpoint  1560  on line  4  between the two clusters). Then connect these midpoints by a border  1570  to separate the two clusters. The following is an example embodiment: 
         [0116]    Step 1. Create a horizontal grid in the ROI. A horizontal grid G H  is a set of horizontal lines L 1 , L 2 , . . . , L n     H   , with a constant distance d H  between adjacent lines, which intersects separation area A. The number of lines n H  in the grid (or the distance d H  between adjacent lines) is a parameter of the algorithm (see  FIG. 15 ). Line L i  can be defined by the equation y=y i  in A. 
         [0117]    Step 2. Initialize the line number i=1. 
         [0118]    Step 3. Calculate N i , the number of times that line L i  intersects cluster C. 
         [0119]    There are two types of intersections: input and output. Moving from left to right along line L i  in A, an input intersection is a point on line L i  where clutter area changes to cluster (target) area (i.e., the left pixel is clutter and the right pixel is cluster), while an output intersection is a point on line L i  where cluster area change to clutter. Formally: 
         [0000]      Input: {( x,y )ε L   i   :P ( x −1 ,y )=0 and  P ( x+ 1 ,y )&gt;0}.
 
         [0000]      Output: {( x,y )ε L   i   :P ( x− 1 ,y )&gt;0 and  P ( x+ 1 ,y )=0}
 
         [0120]    A horizontal grid is shown on  FIG. 15 . Line L 3  has 4 intersections: 2 input and 2 output. 
         [0121]    Step 4. Let N i  be the number of intersections on line L i . These N i  intersections break up L i  into N i  intervals (line segments), label them L i (0,1), L i (1,2), . . . , L (N i −1,N i ). For j=1, 2, . . . , N i , calculate the length ΔL i  (j,j+1), in pixels, of each such interval L i (j,j+1). If ΔL i (j,j+1) is less than a prespecified tolerance T L  then consider L i  (j,j+1) to be noise on clutter or a gap in the target and skip it on the next steps of algorithm (see  FIG. 15 ). Here T L  is a parameter of the algorithm, namely the tolerance of the length of an interval (in pixels). 
         [0122]    Step 5. If N i &lt;4, then skip this line. That is, set i=i+1 and return to step 3. 
         [0123]    Step 6. Otherwise, if N i =4, calculate the y-coordinate of medium point B H   i  on interval ΔL i  (2,3) between intersections  2  and  3  (i.e., between the first output intersection and the second input intersection). If ΔL i (1,2)&gt;T L , ΔL i (2,3)&gt;T L , and ΔL i (3,4)&gt;T L , then point B H   i  belongs to the border between targets in the chip. 
         [0124]    Go to the next line. That is, set i=i+1 and return to step 3. 
         [0125]    Step 7. Finally, if N i &gt;4, determine the index j max  of the longest interval L i (j max ,j max +1) between output and input intersections, where j max  is an output intersection, j max +1 is an input intersection, and ΔL i (j max −1,j max )&gt;T L , ΔL i (j max ,j max +1)&gt;T L , and ΔL i (j max +1,j max +2)&gt;T L . The medium point B H   i  of L i (j max ,j max +1) belongs to the border between targets in the chip. 
         [0126]    Go to the next line. That is, set i=i+1 and return to step 3. 
         [0127]    Step 8. If i&gt;n H , there are no more horizontal lines, so connect all points B H   i  by a broken line B H  and extrapolate this broken line to the sides of area A. Note that there must be at least two such points B H   i . Otherwise go directly to step 10. 
         [0128]    Step 9. If line B H  does not intersect cluster C (or it has an overlap with the cluster that is less than the tolerance T N ), then B H  separates C into two sub-clusters C 1  and C 2 , and B H  is a border between the two targets in the chip. Else, continue to step 10. 
         [0129]    Step 10. Create a vertical grid G V  in the ROI in an analogous fashion to that used for the horizontal grid G H  in step 1. That is, there is a set of n V  vertical lines M 1 , M 2 , . . . , M n     v   , with a constant distance d V  between adjacent lines, which intersects separation area A, each line M i  defined by the equation x=x i . 
         [0130]    Repeat steps 2-8 for the vertical grid G V  as was done for the horizontal grid G H , resulting in a broken line B V  extrapolated to the sides of area A and going through the points B V   i  (assuming there are at least two such points). If there are not at least two such B V   i , go directly to step 12. 
         [0131]    Step 11. If line B V  does not intersect cluster C (or it has an overlap with the cluster that is less than the tolerance T N ), then B V  is a border between the two targets in the chip. Else, continue to step 12. 
         [0132]    Step 12. Calculate the coordinates of the geometrical center (x c ,y c ) for the set of points {B H   i }∪{B V   i }, assuming at least one such point: 
         [0000]    
       
         
           
             
               x 
               c 
             
             = 
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   m 
                 
                  
                 
                     
                 
                  
                 
                   x 
                   i 
                 
               
               m 
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               y 
               c 
             
             = 
             
               
                 
                   
                     ∑ 
                     
                       i 
                       = 
                       1 
                     
                     m 
                   
                    
                   
                       
                   
                    
                   
                     y 
                     i 
                   
                 
                 m 
               
               . 
             
           
         
       
     
         [0133]    Here, {B H   i }∪{B V   i } is the set of medium points, each in the form (x i ,y i ), on output-input intervals (see steps 6-7) for horizontal and vertical grids and m is the number of such points. Again, m must be nonzero, or Algorithm 6 cannot separate the cluster into sub-clusters. 
         [0134]    If lines B H  and B V  do not separate cluster C into two sub-clusters, apply rotating lines (see Algorithm 5) only using the geometrical center (x c ,y c ) as the rotating point (instead of the center of mass). We suppose that, where the previous methods have not proved satisfactory, rotating about the geometrical center (x c ,y c ) does a better cluster separation than rotating about the center of mass. 
         [0135]    Note that if computation time is restricted, processing can be limited to using only horizontal grids, or using only vertical grids, but in this case, Algorithm 6 is not effective for some positions of targets in the chip. 
         [0136]      FIGS. 22-25  demonstrate an example of Algorithm 6.  FIG. 22  shows an MSTAR image of two closely spaced targets in the ROI after stage 1. One target is real while the other target is an artificial rectangular target separated from the first target by clutter in the horizontal direction. We create this target for the demonstration of Algorithm 6.  FIG. 23  shows the set of points {B H   i } (medium points of output-input intervals for a horizontal grid).  FIG. 24  shows a rotation of straight lines around the geometrical center (x c ,y c ).  FIG. 25  shows the result of target separation in the ROI using Algorithm 6. 
         [0137]    The foregoing description has provided by way of exemplary and non-limiting examples a full and informative description of the exemplary embodiments of this invention. However, various modifications and adaptations may become apparent to those skilled in the relevant art in view of the foregoing description, when read in conjunction with the accompanying drawings and the appended claims. However, all such and similar modifications of the teachings of this invention will still fall within the scope of this invention. 
         [0138]    Furthermore, some of the features of the preferred embodiments of this invention could be used to advantage without the corresponding use of other features. As such, the foregoing description should be considered as merely illustrative of the principles of the invention, and not in limitation thereof.