Abstract:
Multiple filters of a bilateral filter are decoupled to form into multple linear filtering operations, which permits faster processing. The bilateral filter is re-presented as an approximate bilateral filter, and subjected to a logarithm whose resultant components are further subjected to a series of Jensen approximations. The errors resulting from each Jensen approximation are collected into a single cumulative error factor, and it is then shown that the cumulative error may be ignored without adversed affect to the result. Thus, the original bilateral filter may be implemented as log(y 0 )=log(2−Σg j K j )+log(ΣK j f j )+log(ΣK j g j ).

Description:
BACKGROUND 
       [0001]    1. Field of Invention 
         [0002]    The present invention is related to the field of bilateral filters. More specifically, it is related to the field of approximate bilateral filters. 
         [0003]    2. Description of Related Art 
         [0004]    Bilateral filtering is a non-linear filtering technique that can combine image information from two domains. Typically, bilateral filtering combines the space domain with a feature domain in the filtering process. Thus, a bilateral filter combines information from the spatial domain and information from a feature domain. A bilateral filter can be represented as 
         [0000]    
       
         
           
             
               
                 
                   
                     y 
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       
                         Z 
                          
                         
                           ( 
                           i 
                           ) 
                         
                       
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           ∈ 
                           
                             Ω 
                             i 
                           
                         
                       
                        
                       
                         
                           I 
                            
                           
                             ( 
                             j 
                             ) 
                           
                         
                          
                         
                           K 
                            
                           
                             ( 
                             
                               i 
                               , 
                               j 
                             
                             ) 
                           
                         
                          
                         
                           g 
                            
                           
                             ( 
                             
                               
                                 I 
                                  
                                 
                                   ( 
                                   i 
                                   ) 
                                 
                               
                               , 
                               
                                 I 
                                  
                                 
                                   ( 
                                   j 
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0005]    where I and y are the input and output images respectively, i is the target pixel and j is a pixel in the symmetric neighborhood of i denoted by Ω i . K(i, j) relates to the spatial domain and measures the spatial affinity between pixels at i and j. In essence, K(i, j) may be thought of as a spatial filter component. Similarly, g(I(i), I(j)) relates to a feature domain and denotes the feature/measurement/photometric affinity, an may be thought of as a feature filter component. Z(i) is the normalization factor at i. 
         [0006]    For example in image editing, a bilateral filter may be used as an edge-preserving smoothing filter. Whereas other filters generally are convolutions in solely the image domain, the bilateral filter can also operate on the image&#39;s range domain, i.e. pixel values. Rather than simply replacing a pixel&#39;s value with a weighted average of its neighbors, as is the case for a a Gaussian filter, the bilateral filter can replace a pixel&#39;s value by a weighted average of its neighbors in both space and range (pixel value). This can preserve sharp edges by systematically excluding pixels across discontinuities from consideration. 
         [0007]    A disadvantage of bilateral filters, however, is that since they require the merging of multiple filters, they tend to be more resource intensive and require longer to process. The approximate bilateral filter, ABLF, has been developed to decrease the processing time at the expense of an introduction of some error that typically must be dealt with separately. 
         [0008]    It is an object of the present invention to provide a fast approximate bilateral filter, FABL Filter, that permits even greater gains in processing speed. 
         [0009]    It is a further object of the present invention to provide a fast approximate bilateral filter whose introduced error may be completely ignored without adverse effect to the end-result image. 
       SUMMARY OF INVENTION 
       [0010]    The present objects have been met in a method for implementing a bilateral filter, including: providing a data processing device to implement the following steps: defining said bilateral filter as 
         [0000]    
       
         
           
             
               
                 y 
                  
                 
                   ( 
                   i 
                   ) 
                 
               
               = 
               
                 
                   1 
                   
                     Z 
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                 
                  
                 
                   
                     ∑ 
                     
                       j 
                       ∈ 
                       
                         Ω 
                         i 
                       
                     
                   
                    
                   
                     
                       I 
                        
                       
                         ( 
                         j 
                         ) 
                       
                     
                      
                     
                       K 
                        
                       
                         ( 
                         
                           i 
                           , 
                           j 
                         
                         ) 
                       
                     
                      
                     
                       g 
                        
                       
                         ( 
                         
                           
                             I 
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                           , 
                           
                             I 
                              
                             
                               ( 
                               j 
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where I and y are the input and output images respectively, i is the target pixel and j is a pixel in the symmetric neighborhood of i denoted by Ω i , K(i, j) relates to first domain and g(I(i), I(j)) relates to a second domain independent of said first domain; representing the bilateral filter as a first approximate bilateral filter (ABLF) defined as 
         [0000]    
       
         
           
             
               
                 y 
                  
                 
                   ( 
                   i 
                   ) 
                 
               
               = 
               
                 
                   1 
                   
                     
                       ∑ 
                       j 
                     
                      
                     
                       
                         g 
                          
                         
                           ( 
                           
                             
                               f 
                                
                               
                                 ( 
                                 j 
                                 ) 
                               
                             
                             - 
                             
                               f 
                                
                               
                                 ( 
                                 i 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                        
                       
                         K 
                          
                         
                           ( 
                           
                             j 
                             - 
                             i 
                           
                           ) 
                         
                       
                     
                   
                 
                  
                 
                   
                     ∑ 
                     j 
                   
                    
                   
                     
                       f 
                        
                       
                         ( 
                         j 
                         ) 
                       
                     
                      
                     
                       g 
                        
                       
                         ( 
                         
                           
                             f 
                              
                             
                               ( 
                               j 
                               ) 
                             
                           
                           - 
                           
                             f 
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                         ) 
                       
                     
                      
                     
                       K 
                        
                       
                         ( 
                         
                           j 
                           - 
                           i 
                         
                         ) 
                       
                     
                   
                 
               
             
             , 
           
         
       
     
         [0000]    where f(i) is the signal point to be replaced by its filtered value y(i), j is an index over the neighborhood of the center point i, K(.) is the spatial linear filter, and g(.) is the range or photometric filter; defining a second approximate bilateral filter (ABLF) based on said first ABLF, said second ABLF being defined as: log(y 0 )=log(2−Σg j K j )+log (ΣK j f j )+log(ΣK j g j ) where y(i)         y 0 , f(i)         f 0 , f(j)         f j , f j −f 0           Δf j , g(Δf j )         g j , and K(j−i)         K j ; and applying the results of said second approximate bilateral filter in place of said bilateral filter. 
         [0011]    In this approach, K(i, j) is a spatial filter component and g(I(i),I(j)) is a featur filter component of said image. Preferably, the first domain is the spatial domain and measures the spatial affinity between pixels at i and j, and the second domain relates to a feature domain denoting feature, measurement, or photometric affinity. 
         [0012]    Also in this approach, all correction terms resulting from an application of a Jensen&#39;s inequality transformation are ignored, i.e. discarded. 
         [0013]    The present invention also provides an embodiment of a method of defining a fast approximat bilateral filter (a FABL filter) from a true bilateral filter, including: a processor to implement the following step: representing the bilateral filter as an approximate bilateral filter ABLF defined by 
         [0000]    
       
         
           
             
               y 
                
               
                 ( 
                 i 
                 ) 
               
             
             = 
             
               
                 1 
                 
                   
                     ∑ 
                     j 
                   
                    
                   
                     
                       g 
                        
                       
                         ( 
                         
                           
                             f 
                              
                             
                               ( 
                               j 
                               ) 
                             
                           
                           - 
                           
                             f 
                              
                             
                               ( 
                               i 
                               ) 
                             
                           
                         
                         ) 
                       
                     
                      
                     
                       K 
                        
                       
                         ( 
                         
                           j 
                           - 
                           i 
                         
                         ) 
                       
                     
                   
                 
               
                
               
                 
                   ∑ 
                   j 
                 
                  
                 
                   
                     f 
                      
                     
                       ( 
                       j 
                       ) 
                     
                   
                    
                   
                     g 
                      
                     
                       ( 
                       
                         
                           f 
                            
                           
                             ( 
                             j 
                             ) 
                           
                         
                         - 
                         
                           f 
                            
                           
                             ( 
                             i 
                             ) 
                           
                         
                       
                       ) 
                     
                   
                    
                   
                     K 
                      
                     
                       ( 
                       
                         j 
                         - 
                         i 
                       
                       ) 
                     
                   
                 
               
             
           
         
       
     
         [0000]    where f(i) is the signal point to be replaced by its filtered value y(i), j is an index over the neighborhood of the center point i, K(.) is a spatial linear filter, and g(.) is a range or photometric filter; using a Taylor series expansion to represent said ABLF as y 0 =(2−Σg j K j )Σf j g j K j , where the following substitution are made: y(i)         y 0 , f(i)         f 0 , f(j)         f j , f j −f 0           Δf j , g(Δf j )         g j , and K(j−i)         K j , and where the summation always goes over a neighbor hood induced by location i; applying the Jensen&#39;s inequality transformation to Σf j g j K j , collecting any resulting errors into a first correction term C 1 (f,g,K); and taking the log of result to obtain ΣK j  log(f j )+ΣK j  log(g j )+C 1 (f,g,K); applying the Jensen&#39;s inequality transformation to ΣK j  log(f j ) and collecting any resulting errors into a second correction term C 2  (f,K) to define ΣK j  log(f j )=log(ΣK j f j )−C 2  (f,K); applyng the Jension&#39;s inequality transform to ΣK j  log(g j ) and collecting any resulting errors into a third correction term C 3 (g,K) to define ΣK j  log(g j )=log(ΣK j g j )−C 3 (g,K); taking the log of both sides of y 0 =(2−Σg j K j )Σf j g j K j  and omitting error terms C 1 (f,g,K), −C 2 (f,K), and −C 3 (g,K) from the result to define the fast approximat bilateral filter as log(y 0 )=log(2−Σg j K j )+log(ΣK j f j )+log(ΣK j g j ). 
         [0014]    In the present approach, the Taylor series expansion representation of the ABLF, K is pre normalized such that ΣK j =1. 
         [0015]    Also in the present approach, the neighborhood is 10 pixels in each direction; up, down, left and right. 
         [0016]    Additionally, lookup tables may be used to determined a value of ΣK j  log(g j ). 
         [0017]    Other objects and attainments together with a fuller understanding of the invention will become apparent and appreciated by referring to the following description and claims taken in conjunction with the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0018]    In the drawings wherein like reference symbols refer to like parts. 
           [0019]      FIG. 1  illustrates the presently preferred method of constructing a fast approximate bilater filter. 
           [0020]      FIG. 2   a  shows the results of applying a full bilateral filter to an image. 
           [0021]      FIG. 2   b  shows the results of applying the presently preferred fast approximate bilateral filter to the same image as used in  FIG. 2   a , with parameters σ r   2 =0.1, σ s   2 =1, r=21. 
           [0022]      FIG. 3  uses a grayscale to illustrate the intensity difference between the image of  FIG. 2   a  and the image of  FIG. 2   b.    
           [0023]      FIG. 4  illustrates the time savings achieved by the present fast approximate BL over the full BL filter. 
           [0024]      FIG. 5  shows a pixel neighborhood around center point i. 
       
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0025]    Because of the need for combining information from two domains, bilateral filters may require more time than other filters. Efforts to speed up the processing of bilateral filters have lead to the development of the approximate bilateral filter (ABLF), which is typically much than the basic bilateral filter (BLF). The present invention provides a new, fast approximate bilateral filter. 
         [0026]    With reference to  FIG. 1 , an approximate bilateral filter may be represented as shown in equation (1), step 10: 
         [0000]    
       
         
           
             
               
                 
                   
                     y 
                      
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       
                         
                           ∑ 
                           j 
                         
                          
                         
                           
                             g 
                              
                             
                               ( 
                               
                                 
                                   f 
                                    
                                   
                                     ( 
                                     j 
                                     ) 
                                   
                                 
                                 - 
                                 
                                   f 
                                    
                                   
                                     ( 
                                     i 
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                            
                           
                             K 
                              
                             
                               ( 
                               
                                 j 
                                 - 
                                 i 
                               
                               ) 
                             
                           
                         
                       
                     
                      
                     
                       
                         ∑ 
                         j 
                       
                        
                       
                         
                           f 
                            
                           
                             ( 
                             j 
                             ) 
                           
                         
                          
                         
                           g 
                            
                           
                             ( 
                             
                               
                                 f 
                                  
                                 
                                   ( 
                                   j 
                                   ) 
                                 
                               
                               - 
                               
                                 f 
                                  
                                 
                                   ( 
                                   i 
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                          
                         
                           K 
                            
                           
                             ( 
                             
                               j 
                               - 
                               i 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where f(i) is the signal point to be replaced by its filtered value y(i). j is an index over the neighborhood of the center point i. As shown in  FIG. 5 , this neighborhood is preferably 10 pixels in each direction from i, such that the neighborhood forms a parallelogram with i at its center and extending 10 pixels up from i, 10 pixels down from i, 10 pixels left from i, and 10 pixels right from i. K(.) is the spatial linear filter, and g(.) is the range or photometric filter. To simplify explanation of the present invention, and to remove any unintended ambiguity, the following discussion will use a simplified notation, wherein, the reference is fixed at the location i, and the variables are renamed a follows: 
         [0027]    f(i)         f 0    
         [0028]    f(j)         f j    
         [0029]    f j −f 0           Δf j    
         [0030]    g(Δf j )         g j    
         [0031]    K(j−i)         K j    
         [0000]    Using the above, simplified notation, equation (1) may be rewritten as equation (2), below. 
         [0000]    
       
         
           
             
               
                 
                   
                     y 
                     0 
                   
                   = 
                   
                     
                       1 
                       
                         
                           ∑ 
                           j 
                         
                          
                         
                           
                             g 
                             j 
                           
                            
                           
                             K 
                             j 
                           
                         
                       
                     
                      
                     
                       
                         ∑ 
                         j 
                       
                        
                       
                         
                           f 
                           j 
                         
                          
                         
                           g 
                           j 
                         
                          
                         
                           K 
                           j 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Preferably, filter K is pre normalized such that ΣK j =1. 
         [0032]    It has been shown that the normalization term in the denominator can be approximated by a Taylor series expansion. Using this Taylor series expansion, the filter of equation (2) can be further written, as shown in step 12, as 
         [0000]        y   0 =(2 −Σg   j   K   j )Σ f   j   g   j   K   j   (3)
 
         [0000]    where index j is dropped from the summation for simplicity. In the following discussion, it is assumed that the summation always goes over the neighbor hood induced by location i. 
         [0033]    Lookup tables may be used with equation (3) for all possible values of g and K, thereby reducing the run-time for filtering. 
         [0034]    The presently preferred method further reduces the CPU cycle by a introducing an additional approximation. Looking at the last factor in Eqn. (3), i.e. the right term, RT, can be modified as follows: 
         [0000]    
       
         
           
             
               RT 
               ≐ 
               
                 ∑ 
                 
                   
                     f 
                     j 
                   
                    
                   
                     g 
                     j 
                   
                    
                   
                     K 
                     j 
                   
                 
               
             
             = 
             
               
                 
                   
                     ∑ 
                     
                       
                         ( 
                         
                           
                             f 
                             j 
                           
                            
                           
                             g 
                             j 
                           
                         
                         ) 
                       
                        
                       
                         K 
                         j 
                       
                     
                   
                   
                     ∑ 
                     
                       K 
                       j 
                     
                   
                 
                 ≥ 
                 
                   ∏ 
                   
                     
                       ( 
                       
                         
                           f 
                           j 
                         
                          
                         
                           g 
                           j 
                         
                       
                       ) 
                     
                     
                       
                         K 
                         j 
                       
                       
                         ∑ 
                         
                           K 
                           j 
                         
                       
                     
                   
                 
               
               = 
               
                 ∏ 
                 
                   
                     ( 
                     
                       
                         f 
                         j 
                       
                        
                       
                         g 
                         j 
                       
                     
                     ) 
                   
                   
                     K 
                     j 
                   
                 
               
             
           
         
       
     
         [0000]    Here, the mathematical transformation known as Jensen&#39;s inequality is used to switch from the equality to the inequality. As is known, Jensen&#39;s inequality transformation introduces discrepancies, or errors. If these discprencies are collected into a first correction term C 1 (f,g,K), and the logarithm of both sides is taken as shown step 14, the result is equation (4). 
         [0000]      log RT=Σ K   j  log( f   j )+Σ K   j  log( g   j )+ C   1 ( f,g,K )  (4)
 
         [0000]    Equation (4) can be exploited in multiple ways. Firstly, the term ΣK j  log(g j ) can be obtained by a lookup, and the first term on the RHS, ΣK j  log(f j ), is a convolution of the log of the image with the kernel K. As shown in step 16, one can use Jensen&#39;s inequality again to write 
         [0000]      Σ K   j  log( f   j )≦log(Σ K   j   f   j )
 
         [0000]      Σ K   j  log( f   j )=log(Σ K   j   f   j )− C   2 ( f,K )
 
         [0000]    Similarly, step 18 applies Jensen&#39;s inequality to term ΣK j  log(g j ) to obtain: 
         [0000]      Σ K   j  log( g   j )≦log(Σ K   j   g   j )
 
         [0000]      Σ K   j  log( g   j )=log(Σ K   j   g   j )− C   3 ( g,K )
 
         [0000]    Combining the above results, equation (4) can be rewritten as 
         [0000]      log RT=log(Σ K   j   f   j )+log(Σ K   j   g   j )+ C   1 ( f,g,K )− C   2 ( f,K )− C   3 ( g,K )  (5)
 
         [0000]    Returning to filter equation (3), and taking the log of both sides one gets 
         [0000]      log( y   0 )=log(2 −Σg   j   K   j )+log(Σ f   j   g   j   K   j )  (6)
 
         [0000]    Recalling that log(Σf j g j K j )=log RT, combining equations (5) and (6), and removing the correction terms, as indicated in step 20, one gets the final expression for the present fast approximate bilateral filter (i.e. FABL Filter) as 
         [0000]      log( y   0 )=log(2 −Σg   j   K   j )+log(Σ K   j   f   j )+log(Σ K   j   g   j )  (7)
 
         [0000]    This form decouples the bilateral filter into multple linear filtering operations and hence represents a step towards faster implementations of the filter. The next step is to address the correction terms that were omitted. 
         [0035]    Given the formulation of equation (7), one proceeds in the direction of identifying range g and spatial K filter pairs that reduce the approximation error. Another direction to investigate would be to incorporate the contribution of the error terms into the filter response. This is possible, if the constant terms behave deterministically for edge and non-edge regions within some reasonable kernel size. For generic bilateral filters both range and spatial filters are assumed to be Gaussian kernels with σ s &gt;&gt;σ r , where σ s  represents the variance of the spatial kernel K and σ r  represents the variance of the range kernel g. The other parameter, which is specified for such filters, is the size of the two kernels, and is denoted by r (both K and g have the same support size). 
         [0036]    It is known from the theory of maximum entropy, that the Jensen approximation error is minimum when the probability of the independent variables is exactly equal to one another. Extending the same reasoning for uniform texture regions with noise (σ&lt;&lt;σ r ), the Jensen approximation error is almost negligible and hence the magnitudes of the error constants C 1           0, C 2           0, C 3           0. Furthermore, C 1           C 2 +C 3 . Hence the response for the approximate filter closely matches the ideal bilateral filter for uniform texture regions. 
         [0037]    One next needs to examine how the present approximation filter behaves in the case of non-uniform texture regions, more commonly known as edge regions. The idea is that the more non-uniform the data is the higher is the entropy. Now, if the kernel g smooths out the data f, then the term f j g j  is smoother than the term f j . This transformation can be thought of as a bandlimited form of the Weierstrass transform, and it leads to the conclusion that C 1 &lt;C 2 +C 3  for an edge patch. Therefore, dropping correction terms C 1 −C 2 −C 3  from equation (5) in creating equation (7) essentially means adding the positive quantity |C 2 +C 3 −C 1 | to the edge region response. The net effect being that the approximation boosts edge regions, which is a desirable effect. So in principle, the approximation filter of equation (7) leads to good bilateral behavior. 
         [0038]    The following is a more detail analysis of the presently preferred approximate bilateral filter in accord with the present invention. 
         [0039]    For a uniform texture region, it is assumed that the current patch is centered at f 0 . It is also assumed that all the intensities are normalized to lie in the range (0,1). It is further assumed that the intensity values 
         [0000]      f j ˜         (f 0 ,σ)∀jεΓ 0  
 
         [0000]    where           represents the Gaussian normal distribution with mean f 0  and variance σ, and where Γ 0  is the square neighborhood induced by the location of the pixel f 0  and σ&lt;&lt;σ r . Under these assumptions, 
         [0000]    
       
         
           
             
               ∑ 
               
                 
                   ( 
                   
                     
                       f 
                       j 
                     
                      
                     
                        
                       
                         - 
                         
                           
                             
                               ( 
                               
                                 Δ 
                                  
                                 
                                     
                                 
                                  
                                 
                                   f 
                                   j 
                                 
                               
                               ) 
                             
                             2 
                           
                           
                             2 
                              
                             
                               ( 
                               
                                 
                                   σ 
                                   r 
                                   2 
                                 
                                 + 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   K 
                   j 
                 
               
             
             ≥ 
             
               ∏ 
               
                 
                   ( 
                   
                     
                       f 
                       j 
                     
                      
                     
                        
                       
                         - 
                         
                           
                             
                               ( 
                               
                                 Δ 
                                  
                                 
                                     
                                 
                                  
                                 
                                   f 
                                   j 
                                 
                               
                               ) 
                             
                             2 
                           
                           
                             2 
                              
                             
                               ( 
                               
                                 
                                   σ 
                                   r 
                                   2 
                                 
                                 + 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   
                     K 
                     j 
                   
                    
                   
                     
 
                   
                   ⇓ 
                   
                     
 
                   
                    
                   
                     ∑ 
                     
                       ( 
                       
                         
                           f 
                           j 
                         
                          
                         
                           K 
                           j 
                         
                       
                       ) 
                     
                   
                 
               
             
             ≥ 
             
               ∏ 
               
                 
                   
                     ( 
                     
                       f 
                       j 
                     
                     ) 
                   
                   
                     K 
                     j 
                   
                 
                  
                 
                   
 
                 
                 ⇓ 
                 
                   
 
                 
                  
                 
                   C 
                   1 
                 
               
             
             ≈ 
             
               C 
               2 
             
           
         
       
     
         [0040]    Now assuming that the patch contains a dominant edge, and the intensity values are drawn from a mixture of Gaussians, then 
         [0000]      f j ˜αN(f 0 ,σ 0 )+(1-α)N(μ,σ 1 )∀jεΓ 0  
 
         [0000]    This model assumes that edge and non-edge pixels are drawn from 2 different Gaussian distributions, and the center pixel f 0  is the mean of one of them. For reasonably small patches, one can relax this assumption and write 
         [0000]    
       
         
           
             
               f 
               j 
             
             ∼ 
             
               { 
               
                 
                   
                     
                       N 
                        
                       
                         ( 
                         
                           
                             f 
                             0 
                           
                           , 
                           σ 
                         
                         ) 
                       
                     
                   
                 
                 
                   
                     
                       N 
                        
                       
                         ( 
                         
                           μ 
                           , 
                           σ 
                         
                         ) 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    Now the pixels in the patch are divided into two sets, one set is similar to the central pixel f 0  and the other set contains the remaining pixels. 
         [0000]    
       
         
           
             
               
                 
                   ∑ 
                   sim 
                 
                  
                 
                   
                     ( 
                     
                       
                         f 
                         i 
                       
                        
                       
                          
                         
                           - 
                           
                             
                               
                                 ( 
                                 
                                   Δ 
                                    
                                   
                                       
                                   
                                    
                                   
                                     f 
                                     j 
                                   
                                 
                                 ) 
                               
                               2 
                             
                             
                               2 
                                
                               
                                 ( 
                                 
                                   
                                     σ 
                                     r 
                                     2 
                                   
                                   + 
                                   
                                     σ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     ) 
                   
                    
                   
                     K 
                     i 
                   
                 
               
               + 
               
                 
                   ∑ 
                   rem 
                 
                  
                 
                   
                     ( 
                     
                       
                         f 
                         j 
                       
                        
                       
                          
                         
                           - 
                           
                             
                               
                                 ( 
                                 
                                   μ 
                                   - 
                                   
                                       
                                   
                                    
                                   
                                     f 
                                     0 
                                   
                                 
                                 ) 
                               
                               2 
                             
                             
                               2 
                                
                               
                                 ( 
                                 
                                   
                                     σ 
                                     r 
                                     2 
                                   
                                   + 
                                   
                                     σ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     ) 
                   
                    
                   
                     K 
                     j 
                   
                 
               
             
             ≥ 
             
               
                 ∏ 
                 sim 
               
                
               
                   
               
                
               
                 
                   ( 
                   
                     
                       f 
                       i 
                     
                      
                     
                        
                       
                         - 
                         
                           
                             
                               ( 
                               
                                 Δ 
                                  
                                 
                                     
                                 
                                  
                                 
                                   f 
                                   j 
                                 
                               
                               ) 
                             
                             2 
                           
                           
                             2 
                              
                             
                               ( 
                               
                                 
                                   σ 
                                   r 
                                   2 
                                 
                                 + 
                                 
                                   σ 
                                   2 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   K 
                   i 
                 
                  
                 
                   
                     ∏ 
                     rem 
                   
                    
                   
                       
                   
                    
                   
                     
                       ( 
                       
                         
                           f 
                           j 
                         
                          
                         
                            
                           
                             - 
                             
                               
                                 
                                   ( 
                                   
                                     μ 
                                     - 
                                     
                                         
                                     
                                      
                                     
                                       f 
                                       0 
                                     
                                   
                                   ) 
                                 
                                 2 
                               
                               
                                 2 
                                  
                                 
                                   ( 
                                   
                                     
                                       σ 
                                       r 
                                       2 
                                     
                                     + 
                                     
                                       σ 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                      
                     
                       K 
                       j 
                     
                   
                 
               
             
           
         
       
       
         
           
             
               
                 
                   ∑ 
                   sim 
                 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       f 
                       i 
                     
                      
                     
                       K 
                       i 
                     
                   
                   ) 
                 
               
               + 
               
                 
                   ∑ 
                   rem 
                 
                  
                 
                     
                 
                  
                 
                   
                     ( 
                     
                       
                         f 
                         j 
                       
                        
                       
                          
                         
                           - 
                           
                             
                               
                                 ( 
                                 
                                   μ 
                                   - 
                                   
                                       
                                   
                                    
                                   
                                     f 
                                     0 
                                   
                                 
                                 ) 
                               
                               2 
                             
                             
                               2 
                                
                               
                                 ( 
                                 
                                   
                                     σ 
                                     r 
                                     2 
                                   
                                   + 
                                   
                                     σ 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     ) 
                   
                    
                   
                     K 
                     j 
                   
                 
               
             
             ≥ 
             
               
                 ∏ 
                 sim 
               
                
               
                   
               
                
               
                 
                   
                     ( 
                     
                       f 
                       i 
                     
                     ) 
                   
                   
                     K 
                     i 
                   
                 
                  
                 
                   
                     ∏ 
                     rem 
                   
                    
                   
                       
                   
                    
                   
                     
                       ( 
                       
                         
                           f 
                           j 
                         
                          
                         
                            
                           
                             - 
                             
                               
                                 
                                   ( 
                                   
                                     μ 
                                     - 
                                     
                                         
                                     
                                      
                                     
                                       f 
                                       0 
                                     
                                   
                                   ) 
                                 
                                 2 
                               
                               
                                 2 
                                  
                                 
                                   ( 
                                   
                                     
                                       σ 
                                       r 
                                       2 
                                     
                                     + 
                                     
                                       σ 
                                       2 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                      
                     
                       K 
                       j 
                     
                   
                 
               
             
           
         
       
     
         [0000]    Now equating the approximation errors, one can write 
         [0000]    
       
         
           
             
               C 
               1 
             
             = 
             
               
                 
                   ∑ 
                   sim 
                 
                  
                 
                     
                 
                  
                 
                   
                     K 
                     i 
                   
                    
                   log 
                    
                   
                       
                   
                    
                   
                     f 
                     i 
                   
                 
               
               + 
               
                 
                   ∑ 
                   rem 
                 
                  
                 
                     
                 
                  
                 
                   
                     K 
                     j 
                   
                    
                   log 
                    
                   
                       
                   
                    
                   
                     f 
                     j 
                   
                 
               
               - 
               
                 
                   K 
                   j 
                 
                  
                 
                   
                     ∑ 
                     rem 
                   
                    
                   
                       
                   
                    
                   
                     
                       
                         ( 
                         
                           μ 
                           - 
                           
                             f 
                             0 
                           
                         
                         ) 
                       
                       2 
                     
                     
                       2 
                        
                       
                         ( 
                         
                           
                             σ 
                             r 
                             2 
                           
                           + 
                           
                             σ 
                             2 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
           
         
       
       
         
           
             
               C 
               1 
             
             = 
             
               
                 C 
                 2 
               
               - 
               
                 
                   K 
                   j 
                 
                  
                 
                   
                     ∑ 
                     rem 
                   
                    
                   
                       
                   
                    
                   
                     
                       
                         ( 
                         
                           μ 
                           - 
                           
                             f 
                             0 
                           
                         
                         ) 
                       
                       2 
                     
                     
                       2 
                        
                       
                         ( 
                         
                           
                             σ 
                             r 
                             2 
                           
                           + 
                           
                             σ 
                             2 
                           
                         
                         ) 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    Thus the edge regions are boosted by a factor 
         [0000]    
       
         
           
             
               K 
               j 
             
              
             
               
                 ∑ 
                 rem 
               
                
               
                   
               
                
               
                 
                   
                     ( 
                     
                       μ 
                       - 
                       
                         f 
                         0 
                       
                     
                     ) 
                   
                   2 
                 
                 
                   2 
                    
                   
                     ( 
                     
                       
                         σ 
                         r 
                         2 
                       
                       + 
                       
                         σ 
                         2 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0041]    This confirms the basic trait of the present approximation, wherein the edge regions are boosted and the flat regions essentially remain the same. In the next section, experiments that exemplify these features are presented. 
         [0042]      FIG. 2   a  shows the results of applying a full bilateral filter to an image.  FIG. 2   b  shows the results of applying the present fast approximate bilateral filter to the same image, with parameters σ r   2 =0.1, σ s   2 =1, r=21. 
         [0043]      FIG. 3  uses a grayscale to illustrate the intensity difference between the image of  FIG. 2   a  (created with the full BL filter) and the image of  FIG. 2   b  (created with the present approximate fast BL). As shown, the majority of the image shows very little intensity difference. Intensity differences are notable primarily only in the border areas of the white shirt, and even in these areas, the intensity difference remains predominantly between +/−0.1. 
         [0044]      FIG. 4  illustrates the time savings achieved by the present fast approximate BL over the full BL filter. The graph shows the execution time along the vertical for a given range varience σ r   2 , while maintaining parameter σ s   2  and r fixed at σ s   2 =1 and r=21. As shown, the present approximte fast BL, indicated by line 13, is consistantly about 30% faster than the full BL filster, indicated by line 11. 
         [0045]    While the invention has been described in conjunction with several specific embodiments, it is evident to those skilled in the art that many further alternatives, modifications and variations will be apparent in light of the foregoing description. Thus, the invention described herein is intended to embrace all such alternatives, modifications, applications and variations as may fall within the spirit and scope of the appended claims.