Abstract:
A color interpolation technique may use a Bayer matrix or pattern. In one embodiment, a color intensity gradient may be calculated between data from a center pixel in the Bayer pattern and the sensor spaced from the center pixel. A minimum and maximum gradient for a plurality of pixels may then be determined. Minimum and maximum intensity values for a group of pixel data values may be determined and these may be averaged to determine a value which may be utilized for interpolation purposes. The technique can use only a simple shift and does not require large dividers.

Description:
BACKGROUND 
     The invention relates generally to image processing and particularly to techniques for interpolating colors detected by pixel sensors in imaging arrays. 
     Color imaging arrays may be used in a variety of electronic devices including digital cameras, copiers, scanners and the like. The array may itself be a charge coupled device (CCD), passive pixel sensor (PPS) or an active pixel sensor (APS) array. 
     Typical red, green, blue (RGB) imaging arrays sense red, green, and blue colors. While it is possible to intersperse a full set of red, green, and blue color sensors in one array, this has been found to be impractical. Thus, various arrangements have been developed to alternate sensors for the necessary colors through the array. Each sensor (in an RGB array) senses either red, green, or blue or in some embodiments, red, green 1 , green 2 , and blue. In still other embodiments, cyan, magenta, yellow (CMY) imaging arrays can be utilized. Thus, one sensor may sense a particular color, while an adjacent sensor may sense a different color. Thereafter, it is necessary to interpolate the missing color data for each pixel. Thus, if a given sensor is a red sensor in an RGB system, it may be desirable to interpolate color intensity data values for the green and blue colors at that sensor&#39;s location in order to produce a true representation of the image with sufficient color definition. 
     One conventional technique for determining an arrangement of pixels in an imaging array is called the Bayer pattern or the Bayer matrix. A pre-determined number of color sensors are arranged in what may be called a tile. A tile may be provided for each of three colors, e.g., red, green, and blue (as well as for green 1  and green 2  if desired). The Bayer pattern distributes the sensors for each color through the tile in a way that improves the interpolation process. 
     A variety of color interpolation techniques have been utilized. One problem with these techniques is that they may require relatively complex mathematical calculations which require correspondingly complex hardware implementations. This means that the imaging system is generally cumbersome and the speed of operation may be slow. 
     Thus, there is a continuing need for a color interpolation system with reduced computational complexity. 
     SUMMARY 
     In accordance with one embodiment, a method of analyzing image data from an array of pixel sensors includes calculating color intensity gradients between data from a center pixel sensor for a first color and sensors for the first color spaced from the center pixel sensor. A minimum gradient is then determined for a plurality of pixel gradients. 
     In accordance with another embodiment, a method of interpolating color values includes calculating color intensity gradients between data from a center pixel sensor for a first color and a pixel for the first color spaced from the center pixel sensor. The gradients are compared to a threshold value. If a gradient exceeds the threshold for that color, the intensity value of the center pixel sensor is used for a pixel spaced from said center pixel sensor. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     FIG. 1 shows a schematic representation of a group of pixels, illustrating a cross pattern within that group; 
     FIG. 2 shows a schematic depiction of a group of pixels illustrating a Celtic pattern within those pixels; 
     FIG. 3 shows a Bayer pattern or matrix for the color red; 
     FIG. 4 shows a Bayer pattern or matrix for the color green 1 ; 
     FIG. 5 shows a Bayer pattern or matrix for the color green 2 ; 
     FIG. 6 shows a Bayer pattern or matrix for the color blue; 
     FIG. 7 is a block diagram showing a technique for determining a color threshold value; 
     FIG. 7A is a block diagram showing a technique for checking color thresholds; 
     FIG. 8 is a flow chart for the hardware for determining a color threshold value shown in FIG. 7; 
     FIG. 8A is a flow chart for the hardware for checking color thresholds; 
     FIG. 9 is a block diagram showing a technique for determining a contrast threshold value; 
     FIG. 10 is a flow chart showing a technique for green color interpolation; 
     FIG. 11 is a flow chart showing a technique for blue color interpolation; and 
     FIG. 12 is a flow chart showing a technique for red color interpolation. 
    
    
     DETAILED DESCRIPTION 
     A rectangular pattern of pixel data may be selected for color analysis and interpolation as shown in FIG.  1 . In FIG. 1, a 5×5 array of data from 25 pixels has been selected with the individual pixels numbered  0  to  24 . 
     A “cross pattern”, shown in FIG. 1, includes the data from the pixels  2 ,  10 ,  12 ,  14 , and  22 . Similarly, a Celtic cross pattern, shown in FIG. 2, includes the data from pixels  0 ,  4 ,  12 ,  20 , and  24 . In both FIGS. 1 and 2, the center pixel is pixel number  12 . A minimum color intensity gradient or delta from the center pixel may then be determined to aid with symmetry arbitration and to prevent over-averaging of high intensity delta boundaries. To determine the minimum cross delta, the intensity values of the pixels  2 ,  10 ,  14 , and  22  are independently subtracted from the intensity value for the center pixel  12 . Similarly, to determine the minimum Celtic delta, the intensity values for the pixels  0 ,  4 ,  20 , and  24  are separately subtracted from the center pixel  12  intensity value. The minimum cross delta or (the minimum Celtic delta) may then be referred to as the minimum cross index (or the minimum Celtic index), followed by the non-center pixel number using the numbering sequence shown in FIGS. 1 and 2. 
     FIGS. 3 through 6 show a conventional-Bayer pattern or matrix. In the illustrated embodiment, both a green 1  and a green 2  tile of 25 pixels are utilized. However, a simple red, green, blue pattern may be utilized as well, and other color sequences such as cyan magenta and yellow (CMY) may also be used. With the convention used in FIGS. 3 through 6, the pixel position is shown as a subscript and the positions of the actual (non-interpolated) pixels corresponding to the given color are underlined. The other, non-underlined color values may be used in an interpolation algorithm so that the missing color values may be computed. 
     It is also advantageous to determine a simple average of the pixel intensity values for a given tile type. A tile type corresponds to the types shown in FIGS. 3 through 6 in the illustrated embodiment. Initially, a delta circuit  10 , shown in FIG. 7, determines the deltas described above for the cross or Celtic configurations. The delta circuit  10  receives two inputs, one of which is the intensity value for the center pixel, and the other of which is one of the intensity values.of the four surrounding pixels, as described above. The deltas are then analyzed to determine whether they are to be considered as “high” or “low” delta values. A greater than and less than comparator  12  determines whether a given delta determined by the circuit  10  is a minimum or maximum value in a given series of deltas. Each time a new minimum or maximum value is determined, it is used as the new threshold value for comparison to other values in the series. Minimum and maximum values, determined by the comparator  12 , are then summed in a summer  14  and divided by two in the divider  16  to approximate a simple average. 
     The circuitry shown in FIG. 7 can be advantageous since averaging over twelve pixels would be hardware intensive, requiring the use of many adders in a multilevel network that require the divide function of twelve. The circuitry shown in FIG. 7 relies on a simple shift resulting in a considerably simpler hardware implementation. 
     Referring to FIG. 8, a flow chart for implementing the embodiment shown in FIG. 1 involves determining the deltas, as indicated in block  18 . The high and low deltas are then identified (block  20 ). The high and the low deltas are summed (block  22 ) and averaged (block  24 ). 
     For the tile type red (FIG.  3 ), the green threshold may be determined by the average (as described above) of the intensity values of the pixels  1 ,  3 ,  5 ,  7 ,  9 ,  11 ,  13 ,  15 ,  17 ,  19 ,  21 , and  23 . The blue threshold for the tile type red may be determined by the average of the intensity values of the pixels  6 ,  8 ,  16 , and  18 . For the tile type green 1  (FIG.  4 ), the blue threshold is the average of the intensity value of the pixels  5 ,  7 ,  9 ,  15 ,  17 , and  19 . The red threshold for the tile type green 1  is the average of the intensity values of the pixels  3 ,  13 ,  23 ,  21 ,  11 , and  1 . For the tile type green 2  (FIG.  5 ), the red threshold is the average of the pixels  5 ,  7 ,  9 ,  15 ,  17 , and  19 . The blue threshold for the tile type green 2  is the average of the pixels  3 ,  13 ,  23 ,  21 ,  11 , and  1 . Finally, for the tile type blue (FIG.  6 ), the green threshold is the average of the pixels  1 ,  3 ,  5 ,  7 ,  9 ,  11 ,  13 ,  15 ,  17 ,  19 ,  21 , and  23 . The red threshold for the tile type blue is the average of the pixels  6 ,  8 ,  16 , and  18 . 
     As in any such system, some color anomalies may be caused by insufficient data with which to make an effective decision. These color anomalies may be aggravated and made more noticeable in high intensity black and white pattern areas with a great deal of pattern detail, close to or exceeding the Nyquist number. A fixed contrast threshold of 150 to 200 may be applied in parallel to the center pixel delta circuit  10 . As shown in FIG. 9, a delta comparator  26  compares the delta in any given direction for the cross and Celtic configurations with a fixed contrast threshold. Any pixel gradient found to be greater than the contrast threshold results in that tile&#39;s color interpolation computation being defaulted to the center pixel intensity value, as indicated by the pixel selector  28 . For example, in the case of a red tile found to have a delta greater than the contrast threshold, the subsequent interpolation of the green and blue colors would be replaced by the intensity value of the center pixel. This has the effect of washing out high intensity color variant detail which significantly improves anomalous clusters of “color bursts.” Although it is feasible to compare the Celtic and cross configurations in all axes (i.e., in four directions), comparing only one axial direction may be equally effective with consequent reduction in hardware. 
     Thus, in one illustrative embodiment, color thresholds may be determined (block  18   a ) using the averages determined, as shown in FIG.  8 A. Namely, the high and low values in the series are determined (block  20   a ), summed (block  22   a ) and averaged (block  24   a ). Referring to FIG. 7A, the high value in the series of intensity values may be determined by the comparator  12  which feeds back a new high value for comparison until the series is exhausted. Similarly, the comparator  12   b  feeds back a new low value until the series of intensity values is exhausted. Then, the series high and low values-are output from the comparators  12   a  and  12   b , summed in the summer  14   a  and averaged in the divide by two circuit  16   a.    
     After computing the color threshold value of each color to be interpolated, each pixel is compared to that threshold as indicated in block  25  in FIG.  8 A and by the comparator  17  in FIG.  7 A. Thereafter, the pixel is regarded as either in high state ( 1 ) i.e. greater than or equal to the threshold, or the low state ( 0 ) i.e. less than the threshold. Once this comparison has been accomplished, standard digital logic may be used to detect patterns in the pixel array in the following fashion. 
     Referring to FIG. 10, an exemplary green interpolation technique is illustrated for interpolation of green in a red or blue tile. Initially, if three or more pixels are the same state (i.e., all high or all low) or if there is cross symmetry, the pixel is chosen from a minimum cross direction, as illustrated in diamond  30  and block  32 . An exception arises when the cross index is greater than the contrast threshold, in which case the interpolation value for the green center pixel is defaulted to be equal to the center color value (red or blue). There would be “cross symmetry” when, in the case of green interpolation, pixels  11  and  13  are the same state and pixels  7  and  17  are the same state but pixel  11  is not the same state as pixel  7 . 
     It would not be reasonable to use the pixel in the minimum cross delta direction in certain cases. In the case of wall symmetries where pixels  7 ,  11 , and  17  (FIG. 3) are the same state, for example, the minimum cross delta is utilized. But if the minimum cross delta suggests taking the data of the pixel farthest away from the perceived boundary,  13  in this example, then the minimum cross delta value is ignored and instead, the intensity value of one of the two pixels along the boundary is chosen. 
     If the tests set forth in the diamond  30  are not satisfied, the pre-calculated green threshold is utilized (block  34 ). Thus, if pixels  7  and  11  are the same and  17  and  13  are the same state, but pixel  11  is not the same state as pixel  17 , the pre-calculated green threshold is used. 
     An exemplary blue interpolation, shown in FIG. 11, for interpolating blue in a red tile or red in a blue tile, generally corresponds to the green interpolation (using the blue or red values respectively). The same analysis is done in diamond  36  as was done in diamond  30  in the green interpolation. Similarly, the same analysis is done in block  38  in the blue interpolation, as was done in block  32  in the green interpolation. However, if the test of diamond  36  is not met, in this blue or red interpolation, the intensity value of the pixel in minimum Celtic delta direction is utilized (block  40 ). 
     Vertical wall symmetry occurs, for blue interpolation in a red tile, where pixel  16  equals pixel  6  and pixel  8  equals  18 , but pixel  8  is not the same state as pixel  6 . With vertical wall symmetry, if there is no obvious pattern of symmetry in the green pixels ( 11 ,  7 ,  17 ,  13 ), for example, all of the green pixels are the same state, the intensity value of the pixel in the minimum Celtic delta direction is used. However, if the green pixels confirm the wall symmetry (e.g., pixel  13  or pixel  11  in FIG. 3 is the same state as the left ( 6  and  16 ) or right wall ( 8  and  18 ), then the choice of pixels is constrained to a pixel from the appropriate side (i.e., the left or right vertical wall having the green pixel that confirms the wall symmetry) and the minimum Celtic delta is utilized. Similarly, with the horizontal wall symmetry where pixels  8  and  6  are the same state and the pixels  16  and  18  are the same state and the pixel  16  is not the same state as the pixel  6 , the same technique is utilized. 
     Referring now to FIG. 12, an exemplary red or blue interpolation technique is illustrated in a green tile. In general, the green pixels are utilized to detect a pattern, and the choice of pixels is constrained to the two nearest neighboring red or blue pixels. The nearest neighbors would be one of pixels  7  or  17  in FIG. 4 (as opposed  5 ,  15 ,  9  or  19 ) in the case of the blue interpolation in green 1 . However, if symmetry is detected which is in conflict with this constraint, then the red threshold or the blue threshold is utilized. 
     If four or five pixels have equal states, as indicated in diamond  42 , then the interpolation uses the intensity value of the pixel in the minimum cross delta direction if it is reasonable to do so (block  44 ). If five pixels (e.g.,  6 ,  12 ,  18 ,  6 ,  16  in green 1 ) are equal, the intensity value of the pixel in the direction of the minimum cross delta direction is utilized, but the choice must be constrained to the nearest neighbor red or blue pixels (either pixel  7  or  17  when interpolating for red in green 2  tiles or pixels  11  or  13  when interpolating blue in green 2  or red in green 1  tiles). In the case where pixel  6  equals pixels  18 ,  16 , and  8 , the minimum cross delta is used to select the appropriate pixel intensity value, but the choice is constrained to either one of the two nearest neighbors. 
     Referring to diamond  46 , if the state of three pixels are equal to the state of the center pixel, such as pixels  6 ,  8 ,  18  and  16  (FIG. 4) are the same state, then use the red threshold for red and the blue threshold for blue. 
     If two pixels are the same state as the center pixel, as indicated in diamond  50 , then the adjacent pixel is used, or the pixel in the cross delta direction is used if reasonable (block  52 ). Thus, if pixel  6  is the same state as pixel  12  and  8  in the green 1  tile, one interpolates for red as follows. If pixel  6  is the same state as pixels  12  and  16 , then use the intensity value of pixel  11 . If pixel  8  is the same state as pixels  14  and  18 , then use the intensity value of pixel  13 . In any other case, use the cross delta direction and constrain as before. 
     If there is Celtic symmetry as indicated in diamond  54 , then the center pixel is utilized as indicated in block  56 . Otherwise, a default value is utilized as indicated in block  58 . Celtic symmetry is where pixels  6 ,  12 , and  18  are the same state or pixels  8 ,  12 , and  16  are the same state. 
     The last two pixels of each line can be interpolated simply by taking the thresholds from the computation of the previous 25-pixel frame. The last two pixels in the line are handled differently because it is not possible to position a tile around either of the last two pixels and stay within the array. The same is true of the last two lines. This may be done by using three additional flip-flops plus a counter to count pixels in the line. 
     The first two lines and the first two pixels of the third line maybe interpolated using the only data at the time of interpolation. That is, one or two lines may be used. If the averaging threshold circuits use comparators to determine the minimum and maximum, then they may be added and divided by 2. Then, providing the pipeline has been reset to zero, threshold values computed from the existing circuits are accurate. 
     While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of the present invention.