Color interpolation system

[0002] The invention relates generally to image processing and particularly to techniques for interpolating colors detected by pixel sensors in imaging arrays.

[0003] 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.

[0004] 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, green1, green2, 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's location in order to produce a true representation of the image with sufficient color definition.

[0005] 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 green1 and green2 if desired). The Bayer pattern distributes the sensors for each color through the tile in a way that improves the interpolation process.

[0006] 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.

[0007] Thus, there is a continuing need for a color interpolation system with reduced computational complexity.

[0008] 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.

[0009] 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.

[0010] FIG. 1 shows a schematic representation of a group of pixels, illustrating a cross pattern within that group;

[0011] FIG. 2 shows a schematic depiction of a group of pixels illustrating a Celtic pattern within those pixels;

[0012] FIG. 3 shows a Bayer pattern or matrix for the color red;

[0013] FIG. 4 shows a Bayer pattern or matrix for the color green1;

[0014] FIG. 5 shows a Bayer pattern or matrix for the color green2;

[0015] FIG. 6 shows a Bayer pattern or matrix for the color blue;

[0016] FIG. 7 is a block diagram showing a technique for determining a color threshold value;

[0017] FIG. 7A is a block diagram showing a technique for checking color thresholds;

[0018] FIG. 8 is a flow chart for the hardware for determining a color threshold value shown in FIG. 7;

[0019] FIG. 8A is a flow chart for the hardware for checking color thresholds;

[0020] FIG. 9 is a block diagram showing a technique for determining a contrast threshold value;

[0021] FIG. 10 is a flow chart showing a technique for green color interpolation;

[0022] FIG. 11 is a flow chart showing a technique for blue color interpolation; and

[0023] FIG. 12 is a flow chart showing a technique for red color interpolation.

[0024] 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.

[0025] 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.

[0026] FIGS. 3 through 6 show a conventional-Bayer pattern or matrix. In the illustrated embodiment, both a green1 and a green2 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.

[0027] 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.

[0028] 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.

[0029] 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).

[0030] 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 green1 (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 green1 is the average of the intensity values of the pixels 3, 13, 23, 21, 11, and 1. For the tile type green2 (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 green2 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.

[0031] 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'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.

[0032] Thus, in one illustrative embodiment, color thresholds may be determined (block 18a) using the averages determined, as shown in FIG. 8A. Namely, the high and low values in the series are determined (block 20a), summed (block 22a) and averaged (block 24a). 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 12bfeeds 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 12aand 12b, summed in the summer 14aand averaged in the divide by two circuit 16a.

[0033] 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. 8A and by the comparator 17 in FIG. 7A. 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.

[0034] 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.

[0035] 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.

[0036] 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.

[0037] 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).

[0038] 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.

[0039] 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 green1. However, if symmetry is detected which is in conflict with this constraint, then the red threshold or the blue threshold is utilized.

[0040] 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 green1) 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 green2 tiles or pixels 11 or 13 when interpolating blue in green2 or red in green1 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.

[0041] 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.

[0042] 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 green1 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.

[0043] 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.

[0044] 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.

[0045] 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.

[0046] 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.