# Patent

## Title
System for reducing ringing artifacts

## Abstract

A system for reducing ringing artifacts on an image.

## Background
BACKGROUND OF THE INVENTION
For image coding schemes undesirable ringing artifacts can appear in the decoded images.
Ringing artifacts tend to occur around edges in decoded images that are coded by coding schemes, such as by Joint Photographic Experts Group (JPEG) schemes and Motion Picture Experts Group (MPEG) 1/2/4 schemes. Generally, a sharp edge in the spatial domain spreads energy over nearly the entire spectrum in the frequency domain. In low bit rate Discrete Cosine. Transform Based (DCT-based) coding, however, the high frequency coefficients are either removed or quantized coarsely, resulting in Gibbs phenomena around edges in the spatial domain, which is manifested as ringing artifacts in the decoded images. Ringing artifacts are more complicated for coded image sequences because they are rendered in motion, due to a different ringing pattern for every sequential frame. In coded image sequences (e.g., motion video), the ringing artifacts are often referred to as a “mosquito” or “corona” artifacts.
Generally, a de-ringing technique removes ringing artifacts from images while maintaining the edges and details of images. Many techniques have been developed for de-ringing. These techniques typically fall into two categories: first those that perform processing within the decoding loop of the image decoder; and second those that perform processing after decoding the image.
The techniques in the first category use coding information available in the decoding loop of the image decoder. These techniques are usually based upon information associated with the coding blocks (e.g., DCT coefficients) defined by the coding scheme.
The techniques in the second category use post-processing that is independent of the decoder, and therefore can be implemented independent of the decoder. Without coding information, the post-processing techniques tend to process every pixel. Processing every pixel of the image has much more calculation load than using information contained within coding blocks.
Many post processing algorithms that are sufficiently computationally simple to be implemented in low-cost TV sets use a form of low-pass filter (LPF). Unlike traditional linear LPFs, these modified LPFs preserve sharp edges while reducing ringing artifacts. There are other sophisticated techniques such as those based on principles of maximum a posterior probability estimation (MAP) or projection onto convex sets (POCS), but these are generally not suitable for inexpensive hardware implementations.
Noise reducing techniques can be used for reducing ringing artifacts. These techniques normally do not take into account the characteristics of the ringing artifacts, so their success is somewhat limited.



BRIEF DESCRIPTION OF THE SEVERAL DRAWINGS
FIG. 1 illustrates a de-ringing technique.
FIG. 2 illustrates a de-ringing technique.
FIG. 3A illustrates a sharp edge with noise.
FIG. 3B illustrates the filtered edge of FIG. 3A.
FIG. 4 illustrates a proximity map.
FIG. 5 illustrates a sieve filter.



DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
Some embodiments of the present invention may be implemented in LCD TV sets where coding information is not generally available. For this reason, the embodiments described herein normally include post processing techniques.
As previously noted, ringing artifacts are often found around edges in decoded images that are coded at low bit rates by a frequency-based coding scheme, such as JPEG or MPEG-1/2/4. Accordingly, ringing artifacts in decoded images typically have two characteristics. First, ringing artifacts typically occur in the proximity of an edge feature of the image in the spatial domain having a high frequency. Second the present inventor came to the realization that sharper edges are typically accompanied with more serious ringing artifacts. These serious ringing artifacts tend to be stronger, cover larger areas, and are more visible to the human eye.
The design of a de-ringing technique involves a trade-off between removing ringing artifacts from images while preserving the edge details of images. Post-processing techniques may be independent from the image decoder and, therefore, may be implemented in any manner after the decoding. Without coding block information and other coding information resulting from encoding or decoding, the post-processing techniques tend to process every pixel (or a substantial number of pixels). Compared with block-based-processing, pixel-processing typically has more calculation load to process an image. To keep overall computational cost acceptable for inexpensive hardware implementation, the computation for each pixel should be relatively simple.
One of the more difficult challenges in an effective de-ringing technique is to achieve a good balance between artifact reduction and detail-preservation. In this delicate balance, the present inventor has determined that the filter and/or window characteristic in a post-processing filter-based de-ringing algorithm may be used to enhance image quality. In a typical image, with a small-size filter such as a 3×3 filter, it is difficult to totally remove ringing artifacts, although it is relatively easy to preserve detail. On the other hand, with a large-size filter such as a 15×15 filter, it is easier to remove ringing artifacts, although it is more difficult to preserve image detail.
For example, a 3×3 averaging filter may have the strongest smoothing ability among all the 3×3 filters because it only keeps the DC coefficient in the frequency spectrum of the window. Nevertheless, some ringing artifacts are still not reduced by such a 3×3 filter while image details are not fully destroyed. If the averaging filter is expanded to a 15×15 filter, all the ringing artifacts are essentially gone, but so are all the image details.
Another characteristic of ringing artifacts realized by the present inventor is that sharper edges tend to have more serious ringing artifacts. Accordingly, the present inventor realized that some form of adaptation to filter characteristic may be used to better balance ringing artifact reduction and preservation of details. A sharper edge tends to have stronger ringing artifacts in its proximity, so a filter with a larger window more readily removes ringing artifacts while maintaining image detail. More specifically, if a sharper edge is detected within a pixel's proximity, then a filter with a larger window size is applied to this pixel in order to remove the ringing artifacts; and in contrast if a weaker edge is detected, a filter with the smaller size is applied to better preserve details.
The adaptive filter-based de-ringing technique based upon the filter size permits more selective filtering. The window size used by the current technique is usually fixed to a small one. A relatively small window size tends to hinder the ringing-artifact-removing ability of a de-ringing algorithm, while a relatively large window size tends to hinder the detail-preserving ability of a de-ringing algorithm. The present inventor has determined that a desirable de-ringing algorithm should have its window size (or otherwise the characteristics of the filter) adaptive to the sharpness of edges (e.g., strength of intensity transitions). Some embodiments of the present invention embody a de-ringing algorithm that adaptively uses multiple window sizes in order to achieve a balance between reducing ringing artifacts from images and preserving details of images. In some embodiments, two window sizes are used. Selecting the window size may be automatically performed based on detected edge information.
Some embodiments of the present invention may include a technique that uses a nonlinear low-pass sieve filter. This filter preserves sharp edges, reduces ringing artifacts, and also detects the proximity of an edge.
Some exemplary embodiments of the present invention may be described with reference to FIG. 1. In these embodiments, a filter is applied to a pixel at position (x,y) 2 using two window sizes: E1 (e. g., 15×15) 4 and E2 (e. g., 3×3) 6. Other window sizes or number of windows may be used, as desired. For the bigger window E1, the filter plays two roles: low-pass filtering images (without destroying strong edges) to generate ILP1(x,y), and generating a binary decision Edge(x,y), which indicates whether the pixel is proximate to a sharp edge. The nearness of the proximity is defined by the size of E1. For the smaller window E2, the filter may only low-pass filter the image (without destroying strong edges) and generate ILP2(x,y), without generating a binary decision on edge. Compared with ILP2(x,y), ILP1(x,y) has fewer ringing artifact remnants, but preserves fewer details as well. Other filters may like be used.
In a subsequent step, the filtered intensity ILP(x,y) at position (x,y), is chosen from ILP1(x,y) 10 and ILP2(x,y) 12, depending on Edge(x,y) 8. If Edge(x,y)=1, then the pixel is in the proximity of a sharp edge (i.e., within window E1 of the pixel at (x,y), there is at least one sharp edge). Based on stronger ringing artifacts being associated with sharper edges, ILP1(x,y) 10 is chosen as the final result because ILP1(x,y) 10 is obtained from a big window and has been smoothed strongly. If Edge(x,y)=0, within window E1, there is no sharp edge. Therefore, ILP2(x,y) 12 is chosen because ILP2(x,y) 12 is from a small window and contains more details.
Some embodiments of the present invention include a sieve filter. These embodiments may be explained with reference to FIG. 2. As previously mentioned, the sieve filter may have two functionalities: edge-preserving smoothing and edge proximity detection (determining if a pixel is in the proximity of an edge).
The sieve filter of some embodiments of the present invention may comprise a 1-D or 2-D rectangular window E 20 and 22, where the current pixel, I(x,y) 24, is located at the center of the window. All the pixels I(i,j) 26 within the windows E 20 and 22 are compared with the central pixel I(x,y) 24. All the pixels whose differences with I(x,y) are smaller than a threshold T1 are averaged. The output of an exemplary sieve filter, ILP(x,y), may be represented mathematically by




  
    
      
        
          
            I
            LP
          
          ⁡
          
            (
            
              x
              ,
              y
            
            )
          
        
        =
        
          
            
              ∑
              
                
                  
                    
                      
                        (
                        
                          i
                          ,
                          j
                        
                        )
                      
                      ∈
                      E
                    
                    &
                  
                  ⁢
                  
                    
                    
                      
                        I
                        ⁡
                        
                          (
                          
                            i
                            ,
                            j
                          
                          )
                        
                      
                      -
                      
                        I
                        ⁡
                        
                          (
                          
                            x
                            ,
                            y
                          
                          )
                        
                      
                    
                    
                  
                
                <
                T1
              
            
            ⁢
            
              I
              ⁡
              
                (
                
                  i
                  ,
                  j
                
                )
              
            
          
          
            N
            ⁡
            
              (
              
                x
                ,
                y
              
              )
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




where E is the window; N(x,y) is the count of the pixels in E that satisfy the condition of |I(i,j)−I(x,y)|<T1.

The sieve filter can smooth data while preserving sharp edges. If the amplitude of an edge is over a threshold value, T1, the edge will be preserved while other places are smoothed. Whether an edge is sharp or not is also determined by T1.
In some embodiments, the sieve filter can also determine if pixel I(x,y) is within the proximity of a sharp edge, where the proximity is determined by the window sizes E 20 and 22. Specifically, the values of the pixels that are dropped by a threshold T1 are averaged and compared with another threshold, a threshold T2. If this average is bigger than T2, then pixel I(x,y) may be determined to be in the proximity of a sharp edge and Edge(x,y)=1; otherwise, Edge(x,y)=0. Mathematically, the output of an exemplary sieve filter Edge(x,y) used in some embodiments is represented by




  
    Edge
    ⁡
    
      (
      
        x
        ,
        y
      
      )
    
  
  =
  
    
      
        
          ∑
          
            
              
                
                  
                    (
                    
                      i
                      ,
                      j
                    
                    )
                  
                  ∈
                  E
                
                &
              
              ⁢
              
                
                
                  
                    I
                    ⁡
                    
                      (
                      
                        i
                        ,
                        j
                      
                      )
                    
                  
                  -
                  
                    I
                    ⁡
                    
                      (
                      
                        x
                        ,
                        y
                      
                      )
                    
                  
                
                
              
            
            ≥
            T1
          
        
        ⁢
        
          I
          ⁡
          
            (
            
              i
              ,
              j
            
            )
          
        
      
      
        N
        -
        
          N
          ⁡
          
            (
            
              x
              ,
              y
            
            )
          
        
      
    
    >
    
      T
      ⁢
      
        
      
      ⁢
      2
    
  




where N is the total number of pixels in window E.

Because this filter drops pixels and keep some pixels for averaging, one may refer to this filter as a sieve filter. Because a sieve filter cannot satisfy the conditions of a linear filter, the sieve filter is considered nonlinear. The two thresholds T1 and T2 and the window size E may be preset to fixed values, determined by calculation of image parameters, or otherwise determined automatically.
The edge-preserving and smoothing functionality of an exemplary sieve filter is illustrated by example in FIGS. 3A and 3B. FIG. 3A shows the input of the sieve filter with a sharp edge which is corrupted with Gaussian type noise. FIG. 3B shows the filtered result of the sieve filter. Because T1 is chosen smaller than the edge amplitude but bigger than the highest fluctuation caused by the noise, the sieve filter effectively smoothes the signal while preserving the sharp edge.
The edge proximity detection functionality of the sieve filter may be illustrated with reference to FIG. 4. The input of the sieve filter is still the sharp edge with Gaussian noise shown in FIG. 3A where the edge is at position 100. As shown in FIG. 4, an area surrounding position 100, not one position, is detected as the proximity of the edge and set to 1. This result is good for the proposed de-ringing algorithm, because the proposed de-ringing algorithm wants to know what pixels are close to a sharp edge, not just the position of an edge.
The computational resource requirements for this filter are minimal.
The sieve filter essentially is an averaging filter, but only averages those pixels whose values differ from the central pixel I(x,y) by an amount within a threshold value, T1. In exemplary embodiments, this computation requires only two divisions, one for ILP(x,y) and one for Edge(x,y).
An exemplary flow diagram for one type of sieve filter is illustrated in FIG. 5. The terms and expressions which have been employed in the forgoing 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 equivalence 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.

## Claims

1. A computer implemented method for reducing ringing artifacts in an image comprising:
(a) identifying a pixel in an image;
(b) determining the proximity of said pixel to an edge feature in said image using a non-linear low-pass sieve filter that modifies said pixel using information from only those selective ones, among all those neighboring pixels within a defined two-dimensional window around said pixel, that meet a criteria defined by said sieve filter; and
(c) based upon the distance of said pixel from said edge feature, modifying said pixel with either a first filter or a second filter based upon the distance of said pixel from said edge feature.

2. The method of claim 1 wherein said first filter is said non-linear low-pass sieve filter having a first pixel window.

3. The method of claim 2 wherein said second filter is said non-linear, low-pass sieve filter having a second pixel window with a different size than said first pixel window.

4. The method of claim 3 wherein said non-linear low-pass sieve filter detects the proximity of said pixel to said edge feature uses said first pixel window and said second pixel window.

5. The method of claim 4 wherein said first pixel window has an area of 15×15 pixels.

6. The method of claim 5 wherein said second pixel window has an area 3×3 pixels.

7. A computer implemented method for reducing ringing artifacts in an image, comprising:
(a) filtering pixels of said image that are sufficiently proximate an edge feature using a first filter applied to a two-dimensional first area of pixels centered around a target pixel, where said first filter modifies said target pixel using information from only those selective ones, among all those neighboring pixels within a defined two-dimensional window around said target pixel, that meet a criteria defined by said first filter;
(b) filtering pixels of said image that are not sufficiently proximate said edge feature using a second filter applied to a two-dimensional second area of pixels centered around a target pixel, said second area including a number of pixels different than that of said first area; and
wherein said first filter determines whether said pixels are proximate to said edge feature.

8. A computer implemented method for filtering an image, comprising:
(a) identifying a pixel in said image;
(b) determining at least one of a sharpness of an edge feature in said image and a proximity of said pixel to said edge feature using a sieve filter that modifies said pixel using information from only those selective ones, among all those neighboring pixels within a defined two-dimensional window around said pixel, that meet a criteria defined by said sieve filter;
(c) based upon at least one of a determined said sharpness and a determined said proximity, filtering said pixel with either a first two-dimensional filter or a second two-dimensional filter, where at least one dimension of said first filter is at least 15 pixels in length.

9. A computer implemented method for filtering an image comprising:
(a) identifying a pixel in an image;
(b) measuring the proximity of said pixel to an edge feature with a first non-linear low pass filter, using the equation





  
    
      Edge
      ⁡
      
        (
        
          x
          ,
          y
        
        )
      
    
    =
    
      
        
          
            ∑
            
              
                
                  
                    
                      (
                      
                        i
                        ,
                        j
                      
                      )
                    
                    ∈
                    E
                  
                  &
                
                ⁢
                
                  
                  
                    
                      I
                      ⁡
                      
                        (
                        
                          i
                          ,
                          j
                        
                        )
                      
                    
                    -
                    
                      I
                      ⁡
                      
                        (
                        
                          x
                          ,
                          y
                        
                        )
                      
                    
                  
                  
                
              
              ≥
              
                T
                ⁢
                
                  
                
                ⁢
                1
              
            
          
          ⁢
          
            I
            ⁡
            
              (
              
                i
                ,
                j
              
              )
            
          
        
        
          N
          -
          
            N
            ⁡
            
              (
              
                x
                ,
                y
              
              )
            
          
        
      
      >
      
        T
        ⁢
        
          
        
        ⁢
        2
      
    
  
  ,




where N is the total number of pixels in the window E;
(c) measuring the sharpness of said edge feature;
(d) filtering said pixel with said first sieve filter when said proximity and said sharpness satisfy a criterion; and
(e) filtering said pixel with a second non-linear low-pass sieve filter when said proximity and said sharpness do not satisfy said criterion, said second sieve filter applied over a pixel window of a different size than that over which said first sieve filter is applied.

10. A computer implemented method for filtering ringing artifacts from an image, said method comprising:
(a) identifying a pixel in an image;
(b) filtering said pixel with a non-linear low-pass sieve filter with a first window size to determine an edge proximity value, where said sieve filter modifies said pixel using information from only those selective ones, among all those neighboring pixels within a defined two-dimensional window around said pixel, that meet a criteria defined by said sieve filter;
(c) using said filter with a first window size to determine a first filtered pixel value for said identified pixel;
(d) using a non-linear low-pass sieve filter with a second window size to determine a second filtered pixel value for said identified pixel;
(e) replacing said identified pixel with said first filtered pixel value when said edge proximity value meets a criterion; and
(f) replacing said identified pixel with said second filtered pixel value when said edge proximity value does not meet said criterion.

11. The method of claim 10 wherein said edge proximity value is determined by the equation:




  
    Edge
    ⁡
    
      (
      
        x
        ,
        y
      
      )
    
  
  =
  
    
      
        
          ∑
          
            
              
                
                  
                    (
                    
                      i
                      ,
                      j
                    
                    )
                  
                  ∈
                  E
                
                &
              
              ⁢
              
                
                
                  
                    I
                    ⁡
                    
                      (
                      
                        i
                        ,
                        j
                      
                      )
                    
                  
                  -
                  
                    I
                    ⁡
                    
                      (
                      
                        x
                        ,
                        y
                      
                      )
                    
                  
                
                
              
            
            ≥
            
              T
              ⁢
              
                
              
              ⁢
              1
            
          
          
            
          
        
        ⁢
        
          
        
        ⁢
        
          I
          ⁡
          
            (
            
              i
              ,
              j
            
            )
          
        
      
      
        N
        -
        
          N
          ⁡
          
            (
            
              x
              ,
              y
            
            )
          
        
      
    
    >
    
      T
      ⁢
      
        
      
      ⁢
      2
    
  



where N is the total number of pixels in the window E.

12. The method of claim 10 wherein said first filtered pixel value is determined by the equation:




  
    
      I
      LP
    
    ⁡
    
      (
      
        x
        ,
        y
      
      )
    
  
  =
  
    
      
        ∑
        
          
            
              
                
                  (
                  
                    i
                    ,
                    j
                  
                  )
                
                ∈
                E
              
              &
            
            ⁢
            
              
              
                
                  I
                  ⁡
                  
                    (
                    
                      i
                      ,
                      j
                    
                    )
                  
                
                -
                
                  I
                  ⁡
                  
                    (
                    
                      x
                      ,
                      y
                    
                    )
                  
                
              
              
            
          
          <
          T1
        
      
      ⁢
      
        I
        ⁡
        
          (
          
            i
            ,
            j
          
          )
        
      
    
    
      N
      ⁡
      
        (
        
          x
          ,
          y
        
        )
      
    
  



where E is the window; N(x,y) is the count of the pixels in E that satisfy the condition of |I(i,j)−I(x,y)|<T1.