Patent Publication Number: US-8971632-B2

Title: System for feature detection for low contrast images

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     None. 
     BACKGROUND OF THE INVENTION 
     The present invention relates to a system for feature detection suitable for low contrast images. 
     There exist many different image matching techniques that are used for image retrieval, object identification, object detection, and object characterization. One such image matching technique uses feature based identification. In particular, the feature based identification may identify corners of one or more images as being indicative of the object, and may also include a set of vectors describing each set of corresponding feature points. The corresponding vectors may be used to compare the similarity of the objects in different images. 
     In general, even if the captured object in one image is same object as that is captured in another image, the size, the rotation, the brightness and the color of each of the objects are frequently different. Some feature point detection techniques are based upon a Harris Corner Detector, SIFT, and Determinant of Hessian. 
     The Harris Corner Detector extracts feature points by using a first-order derivative of an image. The SIFT extracts feature points by uses a Difference of Gaussian (DoG), which is similar to a second order derivative, by removing points that have low contrast. The Determinant of Hessian uses a Hessian matrix, which is a second-order derivative of an image. In general, these “derivative based” techniques are able to detect feature points when the contrast remains sufficiently high. 
     Referring to  FIG. 1 , another feature point detector further includes histogram based equalization. The histogram based technique expands the global contrast of an image when the original contrast of the image is small. Then the histogram based technique calculates a histogram of code values of the whole image. Then if the difference between the maximum value of histogram and the minimum value of the histogram is sufficiently small, the technique adjusts the histogram by changing the maximum value of histogram to the maximum value of code values and changing the minimum value of histogram to the minimum value of code values. The adjusted image from the histogram based equalization may be further processed by one of the above-described derivative based feature point techniques. Unfortunately, the histogram based equalization technique tends to amplify noise in the image, thereby producing a significant number of false positives. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
         FIG. 1  illustrates histogram equalization. 
         FIG. 2  illustrates thresholds based upon standard deviation. 
         FIG. 3  illustrates a feature point detector. 
         FIG. 4  illustrates a local 8-neighbor of pixel Xc. 
         FIGS. 5A and 5B  illustrate a model image and input image. 
         FIGS. 6A and 6B  illustrate a model image and input image as a result of the detector of  FIG. 3 . 
         FIG. 7  illustrates a modified feature point detector. 
         FIG. 8  illustrates a ROI dispersion. 
         FIGS. 9A and 9B  illustrate a model image and input image as a result of the detector of  FIG. 7 . 
     
    
    
     DETAILED DESCRIPTION OF PREFERRED EMBODIMENT 
     The feature point identification process should be suitable to identify feature points, in both high contrast and low contrast situations without substantially enhancing the noise in the image. To facilitate feature identification in images having low contrast in the region proximate a feature, a regionalized processing of the image should be performed. This regionalized image processing localizes the contrast determination which increases the ability to properly identify feature points. In addition, it was determined that a measure of the amount of contrast necessary to identify a feature point is dependent on the contrast. 
     Referring to  FIG. 2 , a preferred technique for feature point determination includes using a standard deviation, a variance, or any other suitable statistical measure generally related to contrast. The standard deviation a is illustrated on the horizontal axis. When using the standard deviation σ, the system may use a function that includes a variable threshold for identifying feature points based upon the value of the standard deviation σ. The standard deviation σ based function may include a lower threshold σ Lt  and the standard deviation σ based function may include a higher threshold σ Ht . At different values of the standard deviation σ based function, an appropriate variable threshold value may be used to identify feature points. By using such a variable threshold value, the system can select an appropriate threshold value based upon the contrast in the localized region of the image. The vertical axis illustrates a variable threshold value “FP” for feature point selection. The variable threshold value for a feature point “FP” may include a lower threshold FP Th     —     Min  and the variable threshold value for a feature point “FP” may include a higher threshold FP Th     —     Max . If σ is larger than σ Ht , then the system uses FP Th     —     Max  as the threshold value above which a feature point is identified. On the other hand, if σ is smaller than σ Lt , then the system uses FP Th     —     Min  value as the threshold value a above which a feature point is identified. In the range between σ Lt  and σ Ht  a function may join the different regions. The variable threshold value function may be a linear line, a non-linear line, or any other type of function. 
     The lower limit of standard deviation σ Lt  reduces the likelihood of detecting false feature points in regions having low contrast, such as uniform regions. In other words, this reduces the likelihood of over detection of feature points in relatively uniform local regions. In relatively uniform local regions there are no corners and such a relatively uniform region will have a small standard deviation. 
     The higher limit of standard deviation σ Ht  reduces the likelihood of not detecting feature points in regions having high contrast, such as corner regions. In other words, this reduces the likelihood of under detection of feature points in relatively high contrast local regions. In relatively high contrast local regions there are corners and such a relatively high contrast location region will have a large standard deviation. 
     Referring to  FIG. 3 , by way of example, a Harris Corner Detector is used as an exemplary example for implementing a feature point detection. Other feature point detection techniques may likewise be used. An image  101  is provided to the feature point detector. The image may be obtained from any source, such as for example, it can be obtained from a camera, or it can be obtained from a file stored on a storage device. In addition, the system may include pre-stored threshold settings for the feature point detector, or may load suitable threshold settings for the feature point detector. 
     A second moment matrix A(x)  102  is calculated. The A(x) matrix  102  may be defined as illustrated in equation 1. 
     
       
         
           
             
               
                 
                   
                     A 
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         x 
                         , 
                         y 
                       
                     
                     ⁢ 
                     
                       
                         w 
                         ⁡ 
                         
                           ( 
                           
                             x 
                             , 
                             y 
                           
                           ) 
                         
                       
                       ⁡ 
                       
                         [ 
                         
                           
                             
                               
                                 
                                   L 
                                   x 
                                   2 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                             
                             
                               
                                 
                                   L 
                                   x 
                                 
                                 ⁢ 
                                 
                                   
                                     L 
                                     
                                       y 
                                       ⁢ 
                                       
                                           
                                       
                                     
                                   
                                   ⁡ 
                                   
                                     ( 
                                     x 
                                     ) 
                                   
                                 
                               
                             
                           
                           
                             
                               
                                 
                                   L 
                                   x 
                                 
                                 ⁢ 
                                 
                                   
                                     L 
                                     
                                       y 
                                       ⁢ 
                                       
                                           
                                       
                                     
                                   
                                   ⁡ 
                                   
                                     ( 
                                     x 
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   L 
                                   y 
                                   2 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     where Lx and Ly are respective derivatives of input image I(x) in the x and y direction. LxLy(x) are the product of Lx and Ly. w(x,y) is a weighting function, such as for example, a uniform or Gaussian filter as shown in equation 2. 
     
       
         
           
             
               
                 
                   
                     w 
                     ⁡ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       g 
                       ⁡ 
                       
                         ( 
                         
                           x 
                           , 
                           y 
                           , 
                           σ 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         1 
                         
                           2 
                           ⁢ 
                           πσ 
                         
                       
                       ⁢ 
                       
                         ⅇ 
                         
                           ( 
                           
                             - 
                             
                               
                                 
                                   x 
                                   2 
                                 
                                 + 
                                 
                                   y 
                                   2 
                                 
                               
                               
                                 2 
                                 ⁢ 
                                 σ 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     The determinant of A(x)  103  is calculated. Also, the trace of A(x)  104  is calculated. Based upon the determinant of A(x)  103  and the trace of A(x)  104 , a Harris measure R(x)  105  is calculated. One calculation for the Harris measure R(x) is shown in equation 3.
 
 R ( x )=det( A )−αtrace 2 ( A )  (3)
 
     The determinant of A(x)  103 , the trace of A(x)  104 , and the Harris measure R(x)  105  are preferably calculated on the entire image, as a whole. The remaining calculations for the feature point detection are preferably performed on a pixel basis. The technique checks to see if all the desired pixels are processed  107 , if yes, then the technique ends  111 . If all the desired pixels are not processed  107 , then the pixel based process continues. 
     R(x), which is a measure of the likelihood of a pixel being a feature point, is compared with FP Th     —     max    108 . If R(x) is larger than FP Th     —     max , then processing continues for the processed pixel. Otherwise, the pixel is determined not to be a feature point, and the process continues with another pixel  106 . 
     R(x) of current pixel is checked to determine if it is a local maximum or not  109 . To determine if it a local maximum, the system may compare R(X c ) with 8 neighbors around X c , as illustrated in  FIG. 4 . If a value of R(X c ) is larger than those of all of 8 neighbors, the current pixel is judged as a local maximum. If the pixel is judged to be a local maximum, then the system then selects the processed pixel as a feature point  110 . Otherwise, the pixels is not judged to be a local maximum, and thus not a feature point, and the process continues with another pixel  106 . 
     Referring to  FIGS. 5A and 5B  by way of example, a “model image” was used as a reference and an “input image” was used based upon the technique illustrated in  FIG. 3 . The model image illustrates a standard transistor and the input image illustrates a captured image of a transistor. While not shown in  FIGS. 5A and 5B , there are minor differences in the color, sharpness, and contrast between the model image and the input image. 
     Referring to  FIGS. 6A and 6B  as a result of the feature point identification technique illustrated in  FIG. 3 , many feature points were properly detected in the model image indicated by an “x”. However, many of these feature points are not detected in the input image, primarily due to a lower contrast in the input image. 
       FIG. 7  shows a modified feature point detection technique, using the Harris Corner Detector, as its processing technique. An image  201  is provided to the feature point detector. The image may be obtained from any source, such as for example, it can be obtained from a camera, or it can be obtained from a file stored on a storage device. In addition, the system may include pre-stored threshold settings for the feature point detector, or may load suitable threshold settings for the feature point detector. Some initial settings may be loaded, such as size of ROI (region of interest), RoiLen, that is used to calculate dispersion within the ROI, a threshold for feature point detector FP Th     —     Max , a higher threshold of standard deviation σ Ht , a lower threshold of standard deviation σ Li , a minimum threshold of feature point detector FP Th     —     min , and such. By way of example, the following settings may be used, RoiLen=7, FP Th     —     Max =40, σ Ht =30.0, σ Lt =5.0. FP Th     —     min =3. 
     A second moment matrix A(x)  202  is calculated. The A(x) matrix  202  may be defined as illustrated in equation 4. 
     
       
         
           
             
               
                 
                   
                     A 
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     
                       ∑ 
                       
                         x 
                         , 
                         y 
                       
                     
                     ⁢ 
                     
                       
                         w 
                         ⁡ 
                         
                           ( 
                           
                             x 
                             , 
                             y 
                           
                           ) 
                         
                       
                       ⁡ 
                       
                         [ 
                         
                           
                             
                               
                                 
                                   L 
                                   x 
                                   2 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                             
                             
                               
                                 
                                   L 
                                   x 
                                 
                                 ⁢ 
                                 
                                   
                                     L 
                                     
                                       y 
                                       ⁢ 
                                       
                                           
                                       
                                     
                                   
                                   ⁡ 
                                   
                                     ( 
                                     x 
                                     ) 
                                   
                                 
                               
                             
                           
                           
                             
                               
                                 
                                   L 
                                   x 
                                 
                                 ⁢ 
                                 
                                   
                                     L 
                                     
                                       y 
                                       ⁢ 
                                       
                                           
                                       
                                     
                                   
                                   ⁡ 
                                   
                                     ( 
                                     x 
                                     ) 
                                   
                                 
                               
                             
                             
                               
                                 
                                   L 
                                   y 
                                   2 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   x 
                                   ) 
                                 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     where Lx and Ly are respective derivatives of input image I(x) in the x and y direction. LxLy(x) are the product of Lx and Ly. w(x,y) is a weighting function, such as for example, a uniform or Gaussian filter as shown in equation 5. 
     
       
         
           
             
               
                 
                   
                     w 
                     ⁡ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       g 
                       ⁡ 
                       
                         ( 
                         
                           x 
                           , 
                           y 
                           , 
                           σ 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         1 
                         
                           2 
                           ⁢ 
                           πσ 
                         
                       
                       ⁢ 
                       
                         ⅇ 
                         
                           ( 
                           
                             - 
                             
                               
                                 
                                   x 
                                   2 
                                 
                                 + 
                                 
                                   y 
                                   2 
                                 
                               
                               
                                 2 
                                 ⁢ 
                                 σ 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     The determinant of A(x)  203  is calculated. Also, the trace of A(x)  204  is calculated. Based upon the determinant of A(x)  203  and the trace of A(x)  204 , a Harris measure R(x)  205  is calculated. One calculation for the Harris measure R(x) is shown in equation 6.
 
 R ( x )=det( A )−αtrace 2 ( A )  (6)
 
     The determinant of A(x)  203 , the trace of A(x)  204 , and the Harris measure R(x)  205  are preferably calculated on the entire image, as a whole. The remaining calculations for the feature point detection are preferably performed on a pixel basis. The technique checks to see if all the desired pixels are processed  207 , if yes, then the technique ends  214 . If all the desired pixels are not processed  207 , then the pixel based process continues. 
     The technique determines a region of interest (“ROI”)  208 , as illustrated in  FIG. 8 . The width and height of the ROI are RoiLen pixels. The technique then calculates a standard deviation a of code values in the ROI that are surrounding the current pixel X c . 
     The technique then compares σ with σ Ht    209 . If σ is larger than σ Ht , then FP Th  is set to FP Th     —     Max    209 . On the other hand, if σ is smaller than σ Ht , then FP Th  is adjusted based on σ  210 . If σ is smaller than σ Ht  and larger than σ Lt , FP Th  is calculated based on equation 8. If σ is smaller than σ Lt , then FP Th  is set to FP Th     —     Min . 
     The value of FP Th    211  can be summarized in the following three equations. 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                             
                         
                         ⁢ 
                         
                           
                             FP 
                             Th 
                           
                           = 
                           
                             FP 
                             
                               Th 
                               ⁢ 
                               _ 
                               ⁢ 
                               Max 
                             
                           
                         
                       
                     
                     
                       
                         ( 
                         
                           
                             if 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             σ 
                           
                           &gt;= 
                           
                             σ 
                             Ht 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       FP 
                       Th 
                     
                     = 
                     
                       
                         
                           
                             
                               FP 
                               
                                 Th 
                                 ⁢ 
                                 _ 
                                 ⁢ 
                                 Max 
                               
                             
                             - 
                             
                               FP 
                               
                                 Th 
                                 ⁢ 
                                 _ 
                                 ⁢ 
                                 Mi 
                                 ⁢ 
                                 n 
                               
                             
                           
                           
                             
                               σ 
                               Ht 
                             
                             - 
                             
                               σ 
                               Lt 
                             
                           
                         
                         ⁢ 
                         σ 
                       
                       + 
                       
                         
                           
                             
                               FP 
                               
                                 Th 
                                 ⁢ 
                                 _ 
                                 ⁢ 
                                 Min 
                               
                             
                             × 
                             
                               σ 
                               Ht 
                             
                           
                           - 
                           
                             
                               FP 
                               
                                 Th 
                                 ⁢ 
                                 _ 
                                 ⁢ 
                                 Max 
                               
                             
                             × 
                             
                               σ 
                               Lt 
                             
                           
                         
                         
                           
                             σ 
                             Ht 
                           
                           - 
                           
                             σ 
                             Lt 
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     ( 
                     
                       
                         If 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         σ 
                       
                       &lt; 
                       
                         
                           σ 
                           Ht 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         and 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         σ 
                       
                       &gt; 
                       
                         σ 
                         Lt 
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                             
                         
                         ⁢ 
                         
                           
                             FP 
                             Th 
                           
                           = 
                           
                             FP 
                             
                               Th 
                               ⁢ 
                               _ 
                               ⁢ 
                               Min 
                             
                           
                         
                       
                     
                     
                       
                         ( 
                         
                           
                             if 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             σ 
                           
                           &lt;= 
                           
                             σ 
                             Lt 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     The technique compares  211  R(x) with FP Th . If R(x) is larger than FP Th , it then checks for a local maximum  212 . Otherwise this pixel is judged as a non feature point, and increments a pixel position  206 . If R(x) is a local maximum  212  then the point is identified as a feature point  213 . 
     As a result of this process, the detected feature point might be like  FIGS. 9A and 9B . When comparing  FIG. 9(   a ) with  FIG. 9(   b ), there are feature points on same points on transistors. When comparing  FIG. 6(   b ) with  FIG. 9(   b ), there is a difference in feature points in low contrast area. These additional feature points provide more accurate image matching 
     The terms and expressions which have been employed in the foregoing specification are used therein as terms of description and not of limitation, and there is no intention, in the use of such terms and expressions, of excluding equivalents of the features shown and described or portions thereof, it being recognized that the scope of the invention is defined and limited only by the claims which follow.