Abstract:
Off-grid interpolation in image processing. The present invention provides for a more perceptually pleasing resultant image when compared to conventional image processing systems that employ on-grid interpolation. In one embodiment, the present invention is operable on a digital image generated using a mask having a Bayer pattern distribution. Off-grid RGB triplets are generated using the raw data received from the Bayer pattern mask. The undesirable mosaic-type images as well as the bright and dark discontinuities within the image that are often generated using conventional on-grid interpolation to generate RGB triplet are avoided when using the present invention. The undesirable cross talk effects that are practically unavoidable to some degree within all digital image masks are also substantially minimized. Bi-linear interpolation and cubic linear interpolation are employed to achieve a digital image having a high visually perceptual quality. The invention ensures that very thin contours and lines within the image will maintain a consistent intensity and uniformity. Where the implementation of conventional on-grid interpolations image processing systems often compromises the quality of such objects, e.g., thin lines can get a broken or dashed appearance, the present invention ensures that they maintain an accurate perceptual consistency.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     The following U.S. patent application is incorporated by reference in its entirety and made part of this U.S. patent application for all purposes. U.S. patent application Ser. No. 10/102,105, entitled “IMAGE RESOLUTION CONVERSION USING PIXEL DROPPING,” filed Mar. 20, 2002. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention relates to image processing and, more particularly, relates to off-grid interpolation performed in image processing. 
     2. Related Art 
     Conventional image processing systems that perform interpolation within a Bayer pattern seek to perform interpolation to generate a triplet that is located actually on the various pixel locations within the Bayer pattern. For an illustrative example, four of the centrally located pixels within the 5×4 pixel Bayer pattern shown below are used to create RGB triplets using this conventional approach. 
     The four bold faced locations within the Bayer pattern shown below: 
     R 0 , G 0 , R 1 , G 1 , R 2   
     G 2 , B 0 , G 3 , B 1 , G 4   
     R 3 , G 5 , R 4 , G 6 , R 5   
     G 7 , B 2 , G 8 , B 3 , G 9   
     can be used generate the following RGB triplets: 
     
         
         (¼*(R 0 +R 1 +R 3 +R 4 ), ¼*(G 0 +G 2 +G 3 +G 5 ), B 0 ) (½*(R 1 +R 4 ), G 3 , ½*(B 0 +B 1 )) 
         (½*(R 3 +R 4 ), G 5 , ½*(B 0 +B 2 )) (R 4 , ¼*(G 5 +G 3 +G 6 +G 8 ), ¼(B 0 +B 1 +B 3 +B 2 )) 
       
    
     Alternative methods of performing the RGB generation within the Bayer pattern are also performed in conventional interpolation image processing systems as shown below.
     (½*(R 1 +R 3 ), ½*(G 0 +G 5 ), B 0 ) (½* (R 1 +R 4 ), G 3 , ½*(B 0 +B 1 ))   (½*(R 3 +R 4 ), G 5 , ½*(B 0 +B 2 )) (R 4 , ½*(G 3 +G 8 ), ½*(B 1 +B 2 ))   

     Depending on how many adjacent or neighboring pixels are to be used, the color shown by the RGB triplet may or may not be an accurate representation of the actual image that was acquired by the mask. Other methods of performing the generation of on-grid RGB triplets are also performed in conventional image processing systems. 
     In addition, the conventional methods of performing on-grid interpolation result in other perceptual and qualitative deficiencies. For example, for very thin lines within an input image, the intensity of the line is sometimes inconsistent, and it even becomes a broken line in some cases. In addition, non-uniformity in the image due to mismatches of the mask performing the image acquisition can also result in mosaic-type of images within conventional image processing systems. Moreover, cross talk between adjacent pixels within the mask, during image acquisition, can also result in many undesirable artifacts within the input image. Each of these deficiencies result in the deleterious effects of improper and often poor image representation using RGB triplets of a Bayer pattern distributed mask. 
     Similarly, gray scale images will suffer from deleterious effects such as inconsistent line intensity and sometimes being shown as a broken line when performing on-grid interpolation as known in the art of image processing. 
     SUMMARY 
     Various aspects of the present invention can be found in an off-grid interpolation image processing system. The off-grid interpolation image processing system includes a processing circuitry. The processing circuitry is operable to perform image processing of raw input data to generate off-grid data points. The processing circuitry selects a fixed number of neighboring pixels within the raw input data to generate at least one of the off-grid data points. The processing circuit performs bi-linear interpolation on red pixels and on blue pixels within the raw input data. The processing circuit performs cubic interpolation on green pixels within the raw input data. The off-grid data points are RGB triplets. 
     In certain embodiments of the invention, a number corresponding to the neighboring pixels to be selected is programmed within the processing circuitry. The locations corresponding to the off-grid data points are programmed within the processing circuitry. The locations corresponding to the off-grid data points are adaptively selected based on the fixed number of neighboring pixels within the raw input data. The fixed number of neighboring pixels within the raw input data is the nearest four pixels or the nearest sixteen pixels. One of the off-grid data points is centrally located between locations of other of the raw input data. One of the off-grid data points is not located in a vicinity of the fixed number of neighboring pixels within the raw input data. 
     Other aspects of the present invention can be found in an off-grid interpolation image processing system. The off-grid interpolation image processing system includes a processing circuitry that is operable to perform image processing of raw input data to generate off-grid data points. The processing circuitry selects a fixed number of neighboring pixels within the raw input data to generate one of the off-grid data points. The processing circuit performs pixel interpolation using the fixed number of neighboring pixels, and at least one of the off-grid data points is centrally located between locations of other of the raw input data. 
     In certain embodiments of the invention, the processing circuit performs bi-linear interpolation on red pixels and on blue pixels within the raw input data, and the processing circuit performs cubic interpolation on green pixels within the raw input data. The locations corresponding to the off-grid data points are programmed within the processing circuitry. One of the off-grid data points is off-centrally located between locations of other of the raw input data. The fixed number of neighboring pixels within the raw input data is the nearest four pixels. One of the off-grid data points is located in a vicinity of the fixed number of neighboring pixels within the raw input data. The off-grid interpolation image processing system also includes a mask that performs image capture of the plurality of raw input data in a Bayer pattern format. 
     Other aspects of the present invention can be found in a method to perform off-grid interpolation. The method involves inputting raw input data to generate off-grid data points, selecting a fixed number of neighboring pixels within the raw input data to generate one of the off-grid data points, performing pixel interpolation using the fixed number of neighboring pixels to generate the off-grid data points, and one of the off-grid data points is centrally located between locations of other of the plurality of raw input data. 
     In certain embodiments of the invention, the method also involves performing bi-linear interpolation on red pixels and on blue pixels within the raw input data, and performing cubic interpolation on green pixels within the raw input data. Locations corresponding to the off-grid data points are programmed within the processing circuitry are predetermined. The locations corresponding to the off-grid data points are programmed within the processing circuitry and are adaptively selected as a function of the fixed number of neighboring pixels within the raw input data. The fixed number of neighboring pixels within the raw input data is the nearest four pixels. 
     Other aspects, advantages and novel features of the present invention will become apparent from the following detailed description of the invention when considered in conjunction with the accompanying drawings. 
     Other systems, methods, features and advantages of the invention will be or will become apparent to one with skill in the art upon examination of the following figures and detailed description. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the invention, and be protected by the accompanying claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The components in the figures are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention. In the figures, like reference numerals designate corresponding parts throughout the different views. 
         FIG. 1  is a system diagram illustrating an embodiment of off-grid interpolation. 
         FIG. 2  is a system diagram illustrating another embodiment of off-grid interpolation. 
         FIG. 3  is a system diagram illustrating another embodiment of off-grid interpolation on a Bayer pattern image. 
         FIG. 4  is a system diagram illustrating another embodiment of off-grid interpolation on a Bayer pattern image. 
         FIG. 5  is a system diagram illustrating another embodiment of an off-grid interpolation system. 
         FIG. 6  is a system diagram illustrating another embodiment of an off-grid interpolation system. 
         FIG. 7  is a system diagram illustrating an embodiment of bi-linear interpolation. 
         FIG. 8  is a system diagram illustrating an embodiment of one dimensional (1-D) cubic interpolation. 
         FIG. 9  is a functional block diagram illustrating an embodiment of an off-grid interpolation method. 
         FIG. 10  is a functional block diagram illustrating another embodiment of an off-grid interpolation method. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  is a system diagram illustrating an embodiment of off-grid interpolation  100 A performed in accordance with the present invention. A number of pixels  1 - 20  are shown as being distributed from left to right and top to bottom in the FIG.  1 . The off-grid locations A, B, C, and D illustrate off-grid interpolation of adjacent pixels wherein the off-grid locations A, B, C, and D are centrally located between the adjacent pixels. Pixels  7 ,  8 ,  9 ,  12 ,  13 ,  14 ,  17 ,  18 , and  19  that are located within a region # 1   110 A are used to calculate the off-grid pixel locations A, B, C, and D. 
     The off-grid locations A 1 , A 2 , A 3 , and A 4  illustrate off-grid interpolation of adjacent pixels wherein the off-grid locations A 1 , A 2 , A 3 , and A 4  are not centrally located between the adjacent pixels. They are all located off center based on the distribution of the pixel grid shown by the pixels  1 - 20 . Pixels  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  9 ,  10 ,  11 ,  12 ,  13 ,  14 , and  15  that are located within a region # 2   120 A are used to calculate the off-grid pixel locations A 1 , A 2 , A 3 , and A 4 . Other ways of clustering and grouping the pixels within the  FIG. 1  are also used in various embodiments of the invention. The particular weighting of the neighboring pixels to generate the off-grid locations of A, B, C, and D as well as A 1 , A 2 , A 3 , and A 4  is also controllable within the invention. 
       FIG. 2  is a system diagram illustrating another embodiment of off-grid interpolation  100 B performed in accordance with the present invention. A number of pixels  1 - 20  are shown as being distributed from left to right and top to bottom in the FIG.  2 . The off-grid locations A, B, C, and D illustrate off-grid interpolation of adjacent pixels wherein the off-grid locations A, B, C, and D are centrally located between the adjacent pixels. Pixels  2 ,  3 ,  4 ,  7 ,  8 ,  9 ,  12 ,  13 ,  14 ,  17 ,  18 , and  19  that are located within a region # 3   130 B are used to calculate the off-grid pixel locations A, B, C, and D. Similarly, the off-grid locations B 1 , B 2 , B 3 , and B 4  illustrate off-grid interpolation of adjacent pixels wherein the off-grid locations B 11 , B 2 , B 3 , and B 4  are not centrally located between the adjacent pixels. They are all located off center based on the distribution of the pixel grid shown by the pixels  1 - 20 . 
     The same pixels within the region # 3   130 B are also used to calculate the off-grid pixel locations B 1 , B 2 , B 3 , and B 4 . The region # 3   130 B shows one example of how the pixels clustered within a region are used to calculate off-grid locations (B 1  and B 4  particularly) where those off-grid locations are outside of the region (the region # 3   130 B particularly). Other ways of clustering and grouping the pixels within the  FIG. 2  are also used in various embodiments of the invention. The particular weighting of the neighboring pixels to generate the off-grid locations of A, B, C, and D as well as B 1 , B 2 , B 3 , and B 4  are also controllable within the invention. 
       FIG. 3  is a system diagram illustrating another embodiment of off-grid interpolation  200 A performed in accordance with the present invention on a Bayer pattern image. A number of pixels are shown as being distributed, from left to right and top to bottom, in a Bayer pattern as shown as having the pixels, R 0 , G 0 , R 1 , G 1 , R 2 , G 2 , B 0 , G 3 , B 1 , G 4 , R 3 , G 5 , R 4 , G 6 , R 5 , G 7 , R 4 , G 6 , R 5 , G 7 , B 2 , G 8 , B 3 , and G 9 . The off-grid locations A, B, C, and D illustrate off-grid interpolation of adjacent pixels wherein the off-grid locations A, B, C, and D are centrally located between the adjacent pixels. Pixels B 0 , G 3 , B 1 , G 5 , R 4 , G 6 , B 2 , G 8 , and B 3  that are located within a region # 1   210 A are used to calculate the off-grid pixel locations A, B, C, and D. 
     The off-grid locations A 1 , A 2 , A 3 , and A 4  illustrate off-grid interpolation of adjacent pixels wherein the off-grid locations A 1 , A 2 , A 3 , and A 4  are not centrally located between the adjacent pixels. They are all located off center based on the distribution of the pixel grid shown by the above-referenced pixels. Pixels B 0 , G 3 , B 1 , G 5 , R 4 , G 6 , B 2 , G 8 , and B 3  that are located within a region # 2   220 A are used to calculate the off-grid pixel locations A 1 , A 2 , A 3 , and A 4 . Other ways of clustering and grouping the pixels within the  FIG. 3  are also used in various embodiments of the invention. The particular weighting of the neighboring pixels to generate the off-grid locations of A, B, C, and D as well as A 1 , A 2 , A 3 , and A 4  are also controllable within the invention. 
       FIG. 4  is a system diagram illustrating another embodiment of off-grid interpolation  200 B performed in accordance with the present invention on a Bayer pattern image. A number of pixels are shown as being distributed, from left to right and top to bottom, in a Bayer pattern as shown as having the pixels, R 0 , G 0 , R 1 , G 1 , R 2  G 2 , B 0 , G 3 , B 1 , G 4 , R 3 , G 5 , R 4 , G 6 , R 5 , G 7 , B 2 , G 8 , B 3 , and G 9 . The off-grid locations A, B, C, and D illustrate off-grid interpolation of adjacent pixels wherein the off-grid locations A, B, C, and D are centrally located between the adjacent pixels. Pixels G 0 , G 1 , G 3 , G 5 , G 6 , G 7 , and G 9  that are located along a number of trajectories  230 B are used to calculate the off-grid pixel locations A, B, C, and D. Similarly, the same pixels located along number of trajectories  230 B also used to calculate the off-grid pixel locations B 1 , B 2 , B 3 , and B 4 . Other ways of clustering, grouping, and trajectories among the pixels within the  FIG. 4  are also used in various embodiments of the invention. The particular weighting of the neighboring pixels to generate the off-grid locations of A, B, C, and D as well as BI. B 2 . B 3 , and B 4  is also controllable within the invention. 
     In certain embodiments of the invention, in off-grid interpolation performed in accordance with the present invention as shown above in the  FIGS. 3 and 4 , the Bayer pattern grid of the interpolated image does not lie directly on the top of the imager grid. Instead, each of the off-grid pixel locations A, B, C, and D positions within both the  FIGS. 3 and 4  are a half a pixel away from the imager grid in both directions. All of the color values are interpolated from multiple pixel values of the imager. 
     A basic off-grid interpolation method can be expressed by using the equations below. The red color within the triplet is interpolated from 4 red pixels forming a square that encloses the interpolated point. For example, R 0 , R 1 , R 3  and R 4  are used in interpolating the red value at the off-grid location A. This is similarly true for the blue value. The green value is only generated from the 2 closest green pixels by performing linear interpolation. 
     One way to perform the calculation of R A , G A , and B A  is described in the equations below. 
       R   A = 1/16·(9 ·R   4 +3·( R   1   +R   3 )+ R   0 )
 
 G   A =½·( G   5   +G   3 )
 
 B   A = 1/16·(9 ·B   0 +3·( B   1   +B   2 )+ B   3 )
 
     Similarly, the calculation of R B , G B , and B B  is described in the equations below.
 
 R   B = 1/16·(9 ·R   4 +3·( R   1   +R   5 )+ R   2 )
 
 G   B =½·( G   3   +G   6 )
 
 B   B = 1/16·(9 ·B   1 +3·( B   0   +B   3 )+ B   2 )
 
     There are 4 different types of locations in the interpolation image. Equations for only locations A and B are given here, but the equations for locations C and D are obtained similarly. 
     This off-grid interpolation scheme generates results that sometimes look slightly more blurred than those obtained with conventional on-grid interpolation methods. However, it is important to keep in mind that some of the textures on an interpolated image from on-grid interpolation are in fact artifacts, and not in fact portions of the actual image itself. 
     The invention provides for enhancement of the edges of an image by performing cubic interpolation on green pixels within the image. No additional line buffers are required to perform this enhancement. The cubic interpolation is only performed one dimensionally. In generating the green value at location A and B, the following equations are used.
 
 G   A = 1/16·(9·( G   5   +G   3 )−( G   1   +G   7 ))
 
 G   B = 1/16·(9·( G   3   +G   6 )−( G   0   +G   9 ))
 
       FIG. 5  is a system diagram illustrating another embodiment of an off-grid interpolation  334  system  300 . The off-grid interpolation system  300  operates on a number of raw data  305  to generate a number of off-grid data points  395 . The off-grid interpolation system  300  itself contains, among other things, a pixel processing circuitry  310  to perform the image processing on the raw data  305 . The pixel processing circuitry itself employs processing circuitry  350  to perform various image processing operations including pixel selection  320 , pixel interpolation  330 , and triplet generation  340 . The pixel interpolation  330  performs one or both of bi-linear interpolation  332  and cubic interpolation  334  on the raw data  320  to generate the off-grid data points  395 . 
       FIG. 6  is a system diagram illustrating another embodiment of an off-grid interpolation system  400 . The off-grid interpolation system  400  operates on a number of on-grid raw data  405  to generate a number of off-grid triplets (R, G, B)  495 . The off-grid interpolation system  400  itself contains, among other things, a pixel processing circuitry  410  to perform the image processing on the on-grid raw data  405 . The pixel processing circuitry  410  itself employs processing circuitry  450  to perform various image processing operations including pixel selection  420 , pixel interpolation  430 , and triplet generation  440 . The pixel interpolation  430  performs one or both of bi-linear interpolation  432  and cubic interpolation  434  on the raw data selected from pixel selection  420  to generate the off-grid triplets (R, G, B)  495 . 
     The pixel selection  420  includes selecting a predetermined number of pixels including the nearest 4 pixels as shown in a block  422  or the nearest 16 pixels as shown in an optional block  424 . The predetermined values as shown in the blocks  422  and  424  are programmed as shown by a block  426  in certain embodiments of the invention. In other embodiments, the pixel selection  420  is adaptive as shown in a block  428 . The pixel selection  420  that is shown as adaptive  428  is performed as a function of neighboring pixels within the on-grid raw data  405 . 
       FIG. 7  is a system diagram illustrating an embodiment of bi-linear interpolation  500  performed by finding a value within a rectangle using the values at four vertices of the rectangle as shown in the FIG.  5 . The four vertices are shown as R 0 , R 1 , R 2 , and R 3 , and the rectangle is partitioned into four regions as shown by the sub-rectangles having lengths and widths as follows: x and y, 1−x and y, x and 1−y, and 1−x and 1−y. 
               R   =         (         R   0     ·     (     1   -   x     )       +       R   1     ·   x       )     ·     (     1   -   y     )       +       (         R   2     ·     (     1   -   x     )       +       R   3     ·   x       )     ·   y                   =         R   0     ·     (     1   -   x     )     ·     (     1   -   y     )       +       R   1     ·   x   ·     (     1   -   y     )       +       R   2     ·     (     1   -   x     )     ·   y     +       R   3     ·   x   ·   y                         
     If the embodiment where both x and y are ¼, then the preceding equation is reduced to the following: 
       R   =           R   0     ·   9     +       (       R   1     +     R   2       )     ·   3   ·   y     +     R   3       16         
 
       FIG. 8  is a system diagram illustrating an embodiment of one dimensional (1-D) cubic interpolation  600  performed in accordance with the present invention. The cubic interpolation  600  predicts the value of an interpolated point using more supporting points with the hope that the interpolated image is more visually pleasing or perceptually pleasing. The implementation of cubic interpolation  600  is operable to provide for sharper features on an interpolated image than using straightforward linear interpolation. 
     One-dimensional cubic interpolation at a middle point is described as shown below. 
     For illustrative purposes, the values of four equal-distanced points are as follows: G 0 , G 1 , G 2 , and G 3 . The following equations are used in order to find the cubic function that passes through all four points, assuming the general cubic equation y=a 3 ·x 3 +a 2 ·x 2 +a 1 ·x 1 +a 0· a 0  is equal to the interpolated value at point. 
       {                   a   3     ·       (     -   3     )     3       +       a   2     ·       (     -   3     )     2       +       a   1     ·       (     -   3     )     1       +     a   0       =     G   0                       a   3     ·       (     -   1     )     3       +       a   2     ·       (     -   1     )     2       +       a   1     ·       (     -   1     )     1       +     a   0       =     G   1                       a   3     ·       (     +   1     )     3       +       a   2     ·       (     +   1     )     2       +       a   1     ·       (     +   1     )     1       +     a   0       =     G   2                       a   3     ·       (     +   3     )     3       +       a   2     ·       (     +   3     )     2       +       a   1     ·       (     +   3     )     1       +     a   0       =     G   3                       
 
     Two new equations can be generated for these four equations. 
       {                   a   2     ·   18     +       a   0     ·   2       =       G   0     +     G   3                         a   2     ·   2     +       a   0     ·   2       =       G   1     +     G   2               ⁢           
     ⁢       a   0     =         9   ·     (       G   1     +     G   2       )       -     (       G   0     +     G   3       )       16               
 
       FIG. 9  is a functional block diagram illustrating an embodiment of an off-grid interpolation method  700 . The off-grid interpolation method  700  operates on input data  705  to generate output data  795 . In a block  710 , a number of pixels are selected. In a block  720 , pixel interpolation is performed on the pixels selected in the block  710 . In a block  730 , off-grid data points are generated using the pixel interpolation that is performed in the block  720 . Output off-grid data points  795  are finally generated by the off-grid interpolation method  700 . 
       FIG. 10  is a functional block diagram illustrating another embodiment of an off-grid interpolation method  800 . The off-grid interpolation method  800  operates on input data  805  to generate output data  895 . In a block  810 , a number of pixels are selected. In a block  820 , pixel interpolation is performed on the pixels selected in the block  810 . In a block  830 , off-grid data points are generated using the pixel interpolation that is performed in the block  820 . Output off-grid data points  895  are finally generated by the off-grid interpolation method  800 . Within the block  810 , in one of the various embodiments of the invention, the nearest 4 pixels to the particular pixel being processed are selected as shown in a block  812 . Within the block  820 , bi-linear interpolation, as described above in various embodiments of the invention, is performed on the red and blue pixels within the mask as shown in a block  822 . In addition, within the block  820 , cubic interpolation, as described above in various embodiments of the invention, is performed on the green pixels within the mask as shown in a block  814 . Within the block  830  triplet off-grid location selection is performed in accordance with the present invention as shown in a block  832 . For example, as shown above in the various embodiments, the off-grid locations between the on-grid locations are chosen as being at various locations including equidistant between the on-grid locations and at other non-centered locations between the on-grid locations. 
     While various embodiments of the invention have been described, it will be apparent to those of ordinary skill in the art that many more embodiments and implementations are possible that are within the scope of this invention.