Method and System for Interpolating Missing Picture Elements in a Single Color Component Array Obtained From a Single Color Sensor

This invention relates to interpolation of intensity values for picture elements of an image and, more particularly, to interpolating intensity values for array elements in a single color component array.

Image capture devices, such as cameras, which use single-chip charge-coupled-devices ("CCD") are well known. These devices include an aperture through which light from the image being captured is transmitted and sensed by a CCD. The CCD is comprised of a plurality of sensor elements. Each sensor element senses the intensity of the light which impinges upon the sensor element. The intensity sensed by each sensor element within the CCD is transferred and stored in a memory or the like for image development. The intensities that are sensed by the sensor elements of the CCD correspond to gray scale values for a black and white image.

To obtain color images from a camera using a single CCD, a color filter array ("CFA") is interposed between the aperture of the camera and the CCD. The color filter array is comprised of a plurality of filter elements in a one to one correspondence with the sensor elements of a CCD. Each filter element allows only one type of colored light to pass through the element. This colored light then strikes a sensor element of the CCD which senses the intensity of the colored light on the sensor element. As a result, the data derived from a sensor element of the CCD has an intensity value and a color identifier since each sensor element corresponds to a color filter element.

Filter elements for a typical CFA normally allow three colors through. The most common colors for a CFA are red-green-blue ("RGB") or luminance-yellow-cyan ("L-Y-C"). By segregating intensity values for the same color into corresponding locations of an array of the same size as the CCD, three incomplete color component arrays are generated for an image. To generate a complete color image, however, a complete color array is required for each color component since the red, green and blue array elements are used to generate a single pixel of a color image. In order to generate intensity values for the undefined color component array elements, interpolation techniques have been developed.

The most common interpolation technique is bilinear interpolation. This interpolation is an average of the four intensity values actually sensed by the CCD which are closest to the undefined array element. This method assumes that the intensity values of the same color in the vicinity of the undefined array element are related to the undefined value. This technique may result in a poor approximation for the array element, especially on textured surfaces and at edges. This problem in interpolating intensities for array elements at these locations arises from the disparity in intensities for neighboring array elements at edges or other uneven surfaces. In effect, the interpolated intensity value becomes a bridge between different structures rather than being absorbed in one structure or the other. The resulting inaccuracy in intensity values may generate an artifact in the image.

An improvement over the bilinear method is disclosed in U.S. Pat. No. 5,382,976 to Hibbard. That patent is directed to the interpolation of array elements for a high frequency color component array. As is well known, the green color components of an RGB color component system, which is sometimes referred to as the luminance components, are thought to be the color component to which the human eye is most sensitive. This sensitivity means that the human eye discerns most of the detail in an image from the green color component or luminance of an image. So that a CCD captures detail to which the human eye responds, most CFAs include at least twice as many green or luminance color filter elements as other color filter elements.

The interpolation technique of U.S. Pat. No. 5,382,976 relies on the dominance of the green component to interpolate the green intensity values for the array elements in the green component array which did not receive a green intensity value that was actually sensed. The technique of this patent classifies the green component array elements having intensity values actually sensed for the green component proximate to the array element for which an intensity value is to be interpolated into a horizontal and a vertical class. The horizontal class is comprised of the intensity values for the array elements which are located on the same row as the array element for which a value is to be interpolated. The vertical class includes the intensity values for the green component which lie in the same column as the array element for which a value is to be interpolated. A gradient is determined for each class and the gradient corresponds to the absolute difference between the intensity values of the array elements in the same class. These gradients are then compared to a threshold. If the gradients for both classes are less than the threshold or if the gradients are both greater than the threshold, then the bilinear interpolation value is computed and used for the array element. If the gradient for only one class is below the threshold value, then only the intensities for the class corresponding to the gradient which is less than the threshold are used to interpolate the array element value. To interpolate array element intensity values for the color components other than green, called chromas in the patent, the interpolated green intensity values are subtracted from the corresponding intensities in a chroma color array. The array elements for which there are no intensity values in the chroma color array are then interpolated using the bilinear method. The resulting intensities for the chroma color component are called color differences in the patent and these are summed with the corresponding intensity values in the green or luminance color component array to obtain intensity values for the chroma color component arrays.

While the technique disclosed in U.S. Pat. No. 5,382,976 improves the image quality over those derived using the bilinear interpolation method alone, artifacts still result in images generated from this method. In particular, color artifacts arise when a gradient comparison results in an interpolated value for a green array element which is lower than it should be to accurately represent the image and the corresponding red or blue component improperly dominates the composite color image. This may be particularly noticeable at edges where an array element should be included in a horizontal or vertical edge but the bilinear interpolations for the elements of the chroma color component array includes intensities in both the horizontal and vertical classes.

Another interpolation technique is disclosed in U.S. Pat. No. 4,642,678 to Cok. That patent discloses a method of interpolation in which a median rather than an average value is used unless the array element for which an intensity value is to be interpolated conforms to a particular pattern. The median value for an array element is obtained by examining the four intensity values for the green or luminance color component proximate to the undefined array element which were actually sensed by the CCD elements. The largest and smallest intensity values are eliminated from the interpolation calculation and the remaining two intensity values are averaged to generate the interpolated value. The two patterns which are otherwise processed are known as stripe and corner patterns. When an intensity value for an array element corresponding to one of these two patterns is interpolated, the interpolation includes a calculation where the median value is adjusted according to an intensity value average corresponding to intensity values for array elements which are more remote than the four closest ones. While this method includes interpolation of intensity values for array elements at comers or within stripe patterns, the resulting images are still subject to color artifacts.

What is needed is an interpolation method which reduces the occurrence of color artifacts.

What is needed is a method of interpolation which more accurately interpolates values for the chroma color components.

The above limitations of prior interpolation methods are overcome by a method and system of the present invention. The method of the present invention includes the steps of using first color component intensities to determine a first and a second gradient for an array element which sensed a second color component intensity, comparing the first and second gradients to a predetermined threshold, selecting an interpolation direction in correspondence to the comparison between the first and second gradients and the predetermined threshold, and interpolating a first color component intensity value for the array element using first color component intensity values for one of the gradients and second color component intensity values which correspond to the selected interpolation direction. By using the color component intensity values for two color components in the vicinity of the array element for which an intensity value is being interpolated, more accurate interpolated intensity values for the color component are generated. The inclusion of the other color component intensity values in the interpolation process is thought to reduce the likelihood of color generated artifacts.

The method of the present invention may also include using second color component intensity values to determine a third and fourth gradient for the array element for which a first color component intensity is to be interpolated and selecting the interpolation direction in accordance with the third and fourth gradients whenever the first and second gradients are less than the predetermined threshold. By using gradients derived from color component intensities which are not the same color as the color intensity to be interpolated, determination of the direction for selecting the color component intensities to be included in the interpolation is further improved.

The method of the present invention may be used for a high frequency color component such as a green or luminance color component array of a color image. Likewise, the same approach may be used on one of the chroma color component arrays as well. Use of the method of the present invention more effectively interpolates intensity values for array elements because it incorporates the intensity values of two different color components in the vicinity of the array element for which a value is being interpolated.

A system which performs in accordance with the method of the present invention includes memory for the storage of the incomplete color component arrays and an interpolation processor performing under the control of a computer program. The interpolation processor identifies each array element of the array for which there is no intensity value and performs the above-described method for interpolating the intensity value for the identified array element.

FIG. 1 is a schematic of a camera incorporating the system and method of the present invention;

FIG. 2 is a depiction of illustrative 2G rectangular arrangements of filter elements in the color filter array of FIG. 1;

FIG. 3 is a depiction of illustrative 3G rectangular arrangements of filter elements in the color filter array of FIG. 1;

FIG. 4 is a depiction of triangular arrangements of filter elements in the color filter array of FIG. 1;

FIG. 5 is a flowchart of the preferred method for interpolating color intensity values from intensity values of a first and second color component array; and

FIG. 6 is an exemplary illustration of array elements in a chroma array and a high frequency color array used to interpolate an intensity value for an undefined element in a chroma array.

A simplified camera construction utilizing the system and method of the present invention is shown in FIG. 1. The camera 10 includes an aperture 12 through which light from an image passes. Light rays 14 impinge upon the color filter array (CFA) 16. Each filter element 18 within CFA 16 allows only one chromatic wavelength of light through. The filtered light rays 22 then strike a single color sensor 24. Preferably, the single color sensor 24 is a charge coupled device ("CCD"). Each sensor element 28 of CCD 24 generates a signal which is indicative of the intensity of the light impinging upon a CCD element. These signals are transferred through sense circuitry 32 to a memory 34 in which the color component arrays are stored. An interpolation processor 36 executing a program implementing the method of the present invention is used to generate interpolated intensity values for array elements in a color component array for which a sensor element 28 in sensor 24 did not sense a color component intensity. The interpolated values may then be stored in memory 34 or alternatively, the color component arrays with the interpolated and actual intensity values may be stored in memory 38 for further processing and use.

The filter elements 18 of CFA 16 may be arranged in a number of known ways such as the Bayer 2G (G-R-B ratio of 2:1:1) patterns shown in FIG. 2 or the 3G (G-R-B ratio of 3:1:1) pattern shown in FIG. 3. These patterns are well known arrangements for rectangular CFAs. In one aspect of the present invention, filter elements 18 of CFA 16 may be arranged in a triangular pattern such as those shown in FIGS. 4(a)-(c). The filter element patterns of FIGS. 4a, 4b, and 4c have the ratios (1:1:1), (4:1:1), and (2:1:1), respectively. These triangular arrangements are previously unknown arrangements of the filter elements for a CFA which are thought to further enhance the interpolation of intensity values for color component array elements determined in accordance with the method of the present invention.

The method implemented by the interpolation processor of the present invention is shown in FIG. 5. That method begins by selecting a color component array which contains intensity values for a first color component (Block 50) and initializing the pointer to corner coordinates for one corner of the array (Block 52). The column coordinate of the pointer is incremented to look for an undefined array element not having an intensity value for the first color component (Block 56). For such an element, the absolute value of the difference between the preceding intensity value for the first color component and the next intensity value in the row of the undefined element is computed to determine a first gradient for the undefined array element (Block 58). A second color component gradient is then determined (Block 60) as the absolute value of the difference between the closest color component intensity values located above and below the location of the undefined array element. The two gradients define a first and second interpolation direction. These two gradients are then compared to a threshold .tau. (Block 64).

Preferably, the threshold is set at a number so that gradients below the threshold indicate a relatively minor change between intensity values in the first or second interpolation direction. If either gradient is equal to or greater than the predetermined threshold (Block 66), the first gradient is compared to the second gradient. If the first gradient is less than the second gradient (Block 68), the intensity values used to generate the first gradient and the corresponding intensity values in a second color component array which corresponds to the color sensed at the undefined array element are used to interpolate the intensity value for the undefined array element (Block 70). Otherwise, the array elements for the color component array being processed and the intensity values for the array elements of the color component sensed at the undefined array element are used to generate the interpolated value (Block 72).

For example, if the green color component array is being processed, the intensity values for the array elements in the same row, which are closest to the undefined array element, are used to generate the first gradient. Likewise, the intensities for the green color component which are above and below the undefined array element are used to generate the second gradient. If either gradient is equal to or greater than the predetermined threshold, the first gradient is compared to the second gradient. If the first gradient is smaller, then the intensity values for the green color component in the row with the undefined array element and the corresponding intensity values in the color component array actually sensed at the undefined array element are used to interpolate the value for the undefined array element. If the undefined array element actually sensed blue color intensity, the interpolated green value is: ##EQU1## where G.sub.preceeding is the green intensity value which precedes the undefined element in the selected interpolation direction, G.sub.following is the green intensity value which follows the undefined element in the selected interpolation direction, B.sub.o is the blue intensity value at the undefined array element, B.sub.-2 is the preceding blue intensity value in the selected interpolation direction and B.sub.2 is the following blue intensity value in the selected interpolation direction.

With further reference to FIG. 5, if both first and second gradients are less than the predetermined threshold, a third and fourth gradient corresponding to the color component actually sensed at the undefined array element are computed (Block 76). Using the preceding and following intensity values in the second color component array for the color actually sensed at the undefined array element, a third gradient is determined. Likewise, using the intensity values for the second color component which are above and below the undefined array element, the fourth gradient is determined. Preferably, the third and fourth gradients are determined as:

where B.sub.0 is the intensity value for the second color component, B.sub.-2 is the preceding intensity value in either the row or column of the undefined element and B.sub.2 is the following element in either the row or column of the undefined element B.sub.0. If the third gradient is less than the fourth gradient (Block 80), then the intensity values for the first color component being interpolated and the second color component actually sensed at the undefined array element are used to generate the interpolated value (Block 82). Otherwise, the vertical array elements of both the first color component being interpolated and the second color component actually sensed at the undefined array element are used for interpolation (Block 84). The process continues until all of the undefined array elements in the color component array have been processed.

The method shown in FIG. 5 may be used to interpolate intensity values for color components in which the color filter elements in CFA 16 are provided in a one-to-one ratio. Typically, CFA 16 uses an arrangement in which one color occurs more frequently than the other color components. In that case, the method of FIG. 5 is preferably applied to the color component array of the high frequency color component first. Following the interpolation of the undefined array elements for the high frequency color component, the process shown in FIG. 5 is performed to interpolate intensity values for the undefined array elements of the remaining color component arrays.

In interpolating the values for an undefined array element for the other color component arrays, the undefined array element generally lies along a first and a second diagonal of array elements which are generally orthogonal to one another. Such an arrangement is shown in FIG. 6a. If the high frequency color component is green, for example, the corresponding intensity values in the green color component array are those shown in FIG. 6b. To interpolate a value for the undefined array element R(2,3) in a chroma array (Blocks 100-108), the absolute value of the difference between the intensity values along the two red color component diagonals are computed to determine first and second gradients. These gradients are, respectively:

and

Similarly, the third and fourth gradients are computed from the high frequency color component according to:

and

The first and second gradients are compared to a predetermined threshold, such as that discussed above, and if either one is greater than the threshold, the two gradients are compared to one another. The intensity values for the array elements corresponding to the smallest gradient for both the chroma color component being interpolated and the high frequency color component are used to generate the interpolated value for the undefined array element. If both gradients are less than the predetermined threshold, the gradients for the high frequency color component are compared to one another. The intensity values from the chroma and high frequency color component arrays which correspond to the smallest gradient are then used to interpolate the value for the undefined array element. An intensity value for an undefined chroma element is: ##EQU2## if the .DELTA.XR diagonal direction is selected and ##EQU3## if the .DELTA.YR diagonal direction is selected.

While the present invention has been illustrated by a description of preferred and alternative embodiments and processes, and while the preferred and alternative embodiments processes have been described in considerable detail, it is not the intention of the applicants to restrict or in any way limit the scope of the appended claims to such detail. Additional advantages and modifications will readily appear to those skilled in the art.