Method and apparatus for determining representative chrominance components

A method and apparatus for determining representative values for the chrominance components to be associated with a plurality of luminance components in a horizontally shrunken or stretched image for graphics controllers wherein display image data is stored in a buffer memory in a form associating a single set of U and V chrominance components with a plurality of Y luminance values. For a four to one shrinkage of an image in a format associating one set of chrominance components with four pixel luminance values wherein each pixel luminance value in the shrunken image initially has as associated set of chrominance components U.sub.0, U.sub.1, U.sub.2 and U.sub.3 and V.sub.0, V.sub.1, V.sub.2 and V.sub.3, the multiple values of the chrominance components are sequentially accumulated in a 3/4:1/4 ratio in such a manner as to provide an approximate average value for U and V for each set of four pixel luminance values in the shrunken image. Circuitry for processing the chrominance components making use of interpolation circuitry already used for interpolation between pixels for a stretched image is disclosed.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The present invention relates to the field of graphics controllers, and 
more particularly to graphics controllers having the capability of 
replicating pixels and of interpolating between pixels. 
2. Prior Art 
Certain prior art graphics controllers manufactured by Cirrus Logic, Inc., 
assignee of the present invention, have used a graphics data format 
referred to as AccuPak.RTM.. As may be seen in FIG. 1, in this format, 
pixel data is stored 4 pixels for every 32-bit word for display purposes 
as the 32-bit words are read out in sequence. Thus, data must be stored in 
the AccuPak.RTM. format for display purposes, even though this format does 
not directly lend itself to replicating pixels, and particularly to 
interpolating between pixels. Accordingly, when manipulating image data to 
stretch or shrink a video image in one or both directions, the video data 
in AccuPak.RTM. is first converted to YUV-444 format, the replication or 
interpolation required is then carried out on the YUV-444 data, and then 
the same is reconverted to the AccuPak.RTM. format. 
As may be seen in FIG. 1, each 32-bit word of video data consists of four 
5-bit components, such as Y.sub.0 through Y.sub.3, each representing in 5 
bits the luminance value of the corresponding pixel of the respective four 
pixels 0 through 3. U.sub.0 and V.sub.0, on the other hand, are each 6-bit 
components of the 32-bit word and comprise the two chrominance components 
which will be used for all four pixel luminance values of the 32-bit word. 
Thus, in the AccuPak.RTM. format, luminance values are represented by a 
5-bit component and can vary pixel to pixel, whereas the chrominance 
values are 6-bit components, and are fixed for each group of four pixels. 
The four pixels, of course, are four successive pixels in a raster scan 
image. The ability to use the same chrominance information for four 
successive pixels is due to the fact that the human eye is less sensitive 
to chrominance information, a fact utilized also in ordinary TV 
broadcasts, wherein the in-phase and quadrature chrominance signals on the 
chroma subcarrier have a substantially lower bandwidth than the luminance 
signal. 
The conversion from AccuPak.RTM. to YUV, and more particularly YUV-444, is 
very simple, as illustrated in FIG. 2. In particular, for each of four 
pixel luminance values such as Y.sub.0 through Y.sub.3, the respective two 
values of chrominance U.sub.0 and V.sub.0 are directly associated, so that 
now each pixel is represented by a luminance value followed by its two 
chrominance values, even though the two chrominance values remain constant 
for four successive pixels. Also in this conversion, the 5 and 6-bit 
components are expressed in 8-bit byte form by padding the unoccupied bits 
with zeros. 
In the prior art graphics controllers being described, circuitry was 
provided to reformat image data to stretch the image in either direction 
by a factor of 2, 4 or 8. This stretching, of course, is on a pixel to 
pixel basis. In a specific example, assume that an image is to be 
stretched 10% in the horizontal direction. Here, it is desired to convert 
the pixel data for ten successive pixels to pixel data for eleven 
successive pixels. This is done in the prior art graphics controller by 
interpolating between two adjacent pixels in the series of ten pixels, so 
that pixel data for an 11th pixel is provided. This provides a smoother 
transition than merely replicating one of the pixels, as replication, 
particularly as the stretching gets larger, gives the image a grainy 
appearance. 
In the following table, Table 1, the manner in which such horizontal 
interpolation is carried out in the prior art may be seen. 
TABLE 1 
______________________________________ 
1-to-1 
stretch 
2-to-1 stretch 
4-to-1 stretch 
8-to-1 stretch 
______________________________________ 
Y.sub.0, U.sub.0, 
Y.sub.0, U.sub.0, V.sub.0 
Y.sub.0, U.sub.0, V.sub.0 
Y.sub.0, U.sub.0, V.sub.0 
V.sub.0 
Y.sub.1, U.sub.0, V.sub.0 
1 #STR1## 
2 #STR2## Y.sub.0, U.sub.0, V.sub.0 
Y.sub.2, U.sub.0, V.sub.0 
Y.sub.1, U.sub.0, V.sub.0 
1 #STR3## 
2 #STR4## 
Y.sub.3, U.sub.0, V.sub.0 
3 #STR5## 
4 #STR6## 
5 #STR7## 
Y.sub.4, U.sub.1, V.sub.1 
Y.sub.2, U.sub.0, V.sub.0 
Y.sub.1, U.sub.0, V.sub.0 
1 #STR8## 
Y.sub.5, U.sub.1, V.sub.1 
6 #STR9## 
7 #STR10## 
1 #STR11## 
. . . Y.sub.3, U.sub.0, V.sub.0 
3 #STR12## 
4 #STR13## 
8 #STR14## 
9 #STR15## 
4 #STR16## 
Y.sub.4, U.sub.1, V.sub.1 
Y.sub.2, U.sub.0, V.sub.0 
Y.sub.1, U.sub.0, V.sub.0 
0 #STR17## 
1 #STR18## Y.sub.1, U.sub.0, V.sub.0 
Y.sub.5, U.sub.1, V.sub.1 
2 #STR19## 
7 #STR20## 
. . . 
3 #STR21## 
7 #STR22## 
Y.sub.3, U.sub.0, V.sub.0 
3 #STR23## 
4 #STR24## 
3 #STR25## 
5 #STR26## 
9 #STR27## 
6 #STR28## 
7 #STR29## 
Y.sub.4, U.sub.1, V.sub.1 
Y.sub.2, U.sub.0, V.sub.0 
8 #STR30## Y.sub.2, U.sub.0, V.sub.0 
. . . 
9 #STR31## 
9 #STR32## 
______________________________________ 
With no stretching (1-to-1), of course, the YUV-444 data is merely the YUV 
data for each successive pixel, as shown. For a 2-to-1 stretch, an 
interpolation is made so that data for an additional pixel is determined 
and effectively interposed between the data for adjacent pixels in the 
1-to-1 version of the image data. This is done by taking the average of 
the luminance values of the two successive pixels (1/2Y.sub.0 
+1/2Y.sub.1). In the example of the Figure, U.sub.0 and V.sub.0 are 
already applicable to both Y.sub.0 and Y.sub.1 and, accordingly represent 
"an average" for these two pixels already. Obviously, when interpolating 
between the fourth and fifth pixels, U.sub.0 and U.sub.1 could be 
averaged, as could V.sub.0 and V.sub.1, though this was not done because 
of the extra hardware required for minimal gain in visual appearance of 
the display. 
For a 4-to-1 stretch, pixel data for three additional pixels are calculated 
and effectively interposed between each two pixels in the 1-to-1 image 
representation. These additional three pixels are also interpolations 
between two adjacent pixels in the 1-to-1 image data, calculated by a 
3/4:1/4 weighting, a 1/2:1/2 weighting, and a 1/4:3/4 weighting, 
respectively in both the luminance and the two chrominance components. 
Again, U.sub.0 and V.sub.0 actually represent that weighting, as U.sub.0 
and V.sub.0 are applicable to both pixel 0 and 1 in Table 1. As to 
interpolating between Y.sub.3 and Y.sub.4, the U and V values associated 
with one luminance value were used, not an interpolation between the two 
sets of values, as repacking the AccuPak.RTM. requires the same U and V 
values for four successive pixels. Finally, the 8-to-1 stretch is 
accomplished by merely replicating each pixel obtained from a 4-to-1 
stretch. 
The net effect of the foregoing is that circuitry for interpolating two 
adjacent values of Y, U and V by a 3/4:1/4, 1/2:1/2, and a 1/4:3/4 
weighting already exists in the prior art products. 
In the case of shrinking an image dimension, however, the problem is 
somewhat different. For instance, assume that an image dimension is to be 
shrunk to one-fourth of its original size. This may be readily done by 
merely picking each fourth pixel of the 1-to-1 image for display, such as 
is shown in Table 2. 
TABLE 2 
______________________________________ 
4-to-1 shrink 
______________________________________ 
Y.sub.3,U.sub.0,V.sub.0 
Y.sub.7,U.sub.1,V.sub.1 
Y.sub.11,U.sub.2,V.sub.2 
Y.sub.15,U.sub.3,V.sub.3 
Y.sub.19,U.sub.4,V.sub.4 
Y.sub.23,U.sub.5,V.sub.5 
Y.sub.27,U.sub.6,V.sub.6 
Y.sub.31,U.sub.7,V.sub.7 
______________________________________ 
Note, however, that in the 4-to-1 shrink, each successive pixel for display 
is taken from a different 32-bit image data word, and from its prior 
AccuPak.RTM. format, has its own unique value of U and V associated with 
it. Consequently, when converting from YUV-444 back to AccuPak.RTM., a 
value for U and V must be selected as representative for four successive 
pixels, such as Y.sub.3, Y.sub.7, Y.sub.11 and Y.sub.15 in the example 
shown. In the prior art devices, an arbitrary choice was made to always 
use one of the four sets of values for U and V to avoid the necessity of 
having to calculate anything different. Note, however, that such a choice 
in essence is associating a single set of values U.sub.n and V.sub.n to 
the equivalent of sixteen successive pixels of the original 1-to-1 image 
data. This has the effect of some image distortion and loss of image 
features that may have been brought out by the chrominance values there 
between. 
Interpolation or shrinking in the vertical direction does not present the 
same problems, in that since each four successive (horizontal) pixels have 
the same values of U and V, interpolation of U and V in the vertical 
direction or skipping of entire lines will yield the same new values of U 
and V for each four successive horizontal pixels in the line or lines 
added by interpolation between two lines of the 1-to-1 image, or used in 
the shrunken image. In essence, an AccuPak.RTM. or AccuPak.RTM.-like 
formatting accommodates different values of U and V between all vertically 
adjacent pixels, but not horizontally adjacent pixels. In general, in the 
prior art, image size adjustment was done first in the vertical direction, 
then in the horizontal direction. 
BRIEF SUMMARY OF THE INVENTION 
A method and apparatus for determining representative values for the 
chrominance components to be associated with a plurality of luminance 
components in a horizontally shrunken image for graphics controllers 
wherein display image data is stored in a buffer memory in a form 
associating a single set of U and V chrominance components with a 
plurality of Y luminance values are disclosed. For a four to one shrinkage 
of an image in a format associating one set of chrominance components with 
four pixel luminance values wherein each pixel luminance value in the 
shrunken image initially has as associated set of chrominance components 
U.sub.0, U.sub.1, U.sub.2 and U.sub.3 and V.sub.0, V.sub.1, V.sub.2 and 
V.sub.3, the multiple values of the chrominance components are 
sequentially accumulated in a 3/4:1/4 ratio in such a manner as to provide 
an approximate average value for U and V for each set of four pixel 
luminance values in the shrunken image. Circuitry for processing the 
chrominance components making use of interpolation circuitry already used 
for interpolation between pixels for a stretched image is disclosed.

DETAILED DESCRIPTION OF THE INVENTION 
In accordance with the present invention, visual characteristics of a 
shrunken image are enhanced by calculating average or near average values 
of U and V for each successive group of four pixels in that shrunken image 
for repacking in AccuPak.RTM. format or an AccuPak.RTM.-like format. In 
particular, consider the 4-to-1 shrinkage of an image originally formatted 
in AccuPak.RTM. format, wherein four successive pixels in the raster scan 
image have initially associated with them a single set- of U and V values. 
The general form of YUV-444 data when expanded from AccuPak.RTM. format is 
shown in Table 2. Here, the problem consists of how to reformat the 
YUV-444 data into an AccuPak.RTM. or AccuPak.RTM.-like format with minimum 
loss of information in the chrominance values. To achieve this result, 
ideally the four sets of U and V values for four pixels would be averaged 
prior to reformatting the four pixels into the 32-bit AccuPak.RTM. format. 
Thus, using Table 2 of the prior art for reference, one would like to have 
the AccuPak.RTM. data for a 4-to-1 shrink in the form shown in Table 3 
below. 
TABLE 3 
______________________________________ 
Accupak .RTM. 
4-to-1 shrink 
______________________________________ 
0 #STR33## 
1 #STR34## 
2 #STR35## 
. . . 
______________________________________ 
Such a form gives equal weighting to the U and V chrominance values for 
each of the four pixels represented by the 32-bit AccuPak.RTM. word. While 
averaging the U and V values as shown is certainly possible, the same has 
the disadvantage that such an averaging would require additional hardware 
(circuitry) on the graphics controller, increasing the cost of the same 
more than is desirable. 
As an alternative to the averaging of the U and V values as in Table 3, the 
present invention contemplates the approximation of such averaging through 
the use of the X interpolator used in the prior art graphics controllers, 
though with some modification thereto. 
Referring now to FIG. 3, an X or horizontal interpolator modified in 
accordance with the present invention may be seen. The interpolator 
includes an A register and a B register, each of which may present the 
contents thereof less the least significant bit (A1/2, B1/2) and less the 
two least significant bits (A1/4, B1/4) as their output. Dropping the 
least significant bit is equivalent to dividing the register contents in 
half, and dropping the two least significant bits is equivalent to 
dividing the register contents by four. The divided-by-four contents of 
registers A and B may be passed through multiplexers controlled by control 
signals XCTL 13 and CTL 13 to X ADDER 0, with the output 1/4A+1/4B 
providing one input to the X ADDER 1. The other input to X ADDER 1 is 
provided by a MUX controlled by X CTL 14, which may pass either 1/2A or 
1/2B as the second input to X ADDER 1. Accordingly, depending upon the 
control signal X CTL 14, the output of X ADDER 1 under these conditions is 
either 3/4A+1/4B or 1/4A+3/4B. 
Alternatively, the control signals X CTL 13 and CTL 13 may be used to 
control the respective MUX's to pass 1/2A as one input to X ADDER 0, and 0 
as the other input to the adder X ADDER 0. Consequently, the output of X 
ADDER 0 in this condition, provided as one input to X ADDER 1, will be 
1/2A. The other input to X ADDER 1 is controlled by the control signal 
XCTL 14 to be either 1/2A or 1/2B, whereby the output of X ADDER 1 may be 
selected to be either A or 1/2A+1/2B. 
The interpolator of FIG. 3 also includes a multiplexer/holding register 
identified as MUX/HOLD in the Figure. The multiplexer/holding register is 
controlled by the control signal MIX, and has as one input thereto, 
feedback from the output of the adder X ADDER 1. Finally, there is a 
direct path from the B register to the second input of the 
multiplexer/holding register MUX/Hold. 
The circuit of FIG. 3 is used as an X interpolator during the horizontal 
stretching of an image in a manner well-known in prior art graphics 
controllers. This current technique won't correctly match up the 
chrominance when pixels having different U, V values are combined. In 
accordance with the present invention, the circuit of FIG. 3 is used in a 
novel manner to calculate approximate average values for U and V to use 
for multiple pixels when the same multiple pixels have more than one set 
of U and V values associated therewith. As an example, consider the 
approximate averaging of the U chrominance components for four successive 
pixels of a 4-to-1 shrunken image prior to reformatting in the 
AccuPak.RTM. format. Since the pixel data for the 1-to-1 image was 
originally in AccuPak.RTM. form, every fourth pixel in the YUV-444 format 
as expanded from the AccuPak.RTM. format has its own set of U and V values 
associated therewith. 
The steps to calculate the approximate average can be seen in FIG. 5. The 
interpolator of FIG. 3 is set to calculate 3/4A+1/4B, as illustrated in 
FIG. 5. Initially, the first value of U.sub.0 is provided to the B 
register, and from there via the multiplexer MUX/Hold to the A register. 
Then the second value, U.sub.1, is provided to the B register. Since the 
circuit is set to provide 3/4A+1/4B as the output of the adder X ADDER 1, 
the output of X ADDER 1 for the U.sub.0 input to the A register and the 
U.sub.1 input to the B register will be 3/4U.sub.0 +1/4U.sub.1. The 
feedback path couples that output to the A register via the MUX/Hold 
multiplexer to the input of the A register while U.sub.2 is input to the B 
register. These two inputs are then processed again in the 3/4A+1/4B 
proportion, resulting in the output of the adder X ADDER 1 of 
3/4(3/4U.sub.0 +1/4U.sub.1)+1/4U.sub.2 =9/16U.sub.0 +3/16U.sub.1 
+1/4U.sub.2. The feedback and reprocessing is continued one more time as 
the fourth value U.sub.3 is provided to the B register, again with the 
3/4A+1/4B proportion, to result in the approximate average U output from 
the adder X ADDER 1 of 3/4(9/16U.sub.0 +3/16U.sub.1 
+1/4U.sub.2)+1/4U.sub.3, or: 
EQU U.sub.avg .apprxeq.27/64U.sub.0 +9/64U.sub.1 +12/64U.sub.2 +16/64U.sub.3 
While the foregoing approximation is most heavily weighted toward the value 
of U.sub.0 and least heavily weighted toward the value of U.sub.1, clearly 
all values of U have a significant contribution to the approximation. 
Further, the relative weighting in this approximation, particularly with 
the most heavily weighted and least weighted values of the chrominance 
components being adjacent to each other, provides a very substantial 
advantage over merely selecting one of the values U.sub.0 through U.sub.3 
as the only value considered. Further, the extent of complication added to 
the interpolator already in the graphics controller to achieve the 
approximation is minimal, yet image features which in the prior art may be 
lost in the unconsidered chrominance values, are substantially preserved 
in the compressed image using the approximation of the U and V values of 
the present invention. In that regard, obviously the V values may be 
processed the same as the U values to provide the same form of 
approximation: 
EQU V.sub.avg .apprxeq.27/64V.sub.0 +9/64V.sub.1 +12/64V.sub.2 +16/64V.sub.3 
Finally, with respect to a 2-to-1 compression, rather than a 4-to-1 
compression of the image, if the same approximation is used, the 
corresponding values of U and V processed will provide an approximate 
average value for U of 27/64U.sub.0 +9/64U.sub.0 +12/64U.sub.1 
+16/64U.sub.1 =9/16 U.sub.0 +7/16U.sub.1, quite a good average. 
Pixel stretching in a horizontal direction has the same properties as when 
a shrink operation occurs. Consider the consequence of a 2 to 1 stretch 
operation where combinations of pixels with different chrominance values 
are recombined. From the example of the stretch operation in Table 1, when 
the "2-to-1 stretch" operation is recombined into 32 bit AccuPak.RTM. 
format, the first 32 bits have matching U and V values for all the Y 
values. In the second set of four pixels, there is a combination of 
Y.sub.3 and Y4. This mixes the chrominance values with different luminance 
values. To more accurately reflect the resultant image, the existing 
interpolation unit is set to 3/4 first pixel+1/4 second pixel as is 
accomplished in a shrink operation. This operation has the effect of 
blending the color changes more uniformly and is more pleasing to the eye. 
For purposes of illustration, consider the two image data words in 
AccuPak.RTM. format: 
EQU Y.sub.0 Y.sub.1 Y.sub.2 Y.sub.3 U.sub.0 V.sub.0 
EQU Y.sub.4 Y.sub.5 Y.sub.6 Y.sub.7 U.sub.1 V.sub.1 
For the first four pixels in the 2 to 1 stretch: 
______________________________________ 
##STR36## 
3 Y.sub.1 
4 #STR37## 
Y.sub.0 
U.sub.0 
V.sub.0 
______________________________________ 
For the second four pixels 
______________________________________ 
##STR38## 
5 Y.sub.3 
6 #STR39## 
Y.sub.2 
See below 3/4U.sub.0 + 1/4U.sub.1 
See below 3/4V.sub.0 
______________________________________ 
+ 1/4V.sub.1 
As the four pixels are processed into the AccuPak.RTM. format, the 
following formulas apply: 
EQU 3/4(3/4(3/4U.sub.0 +1/4U.sub.0)+1/4U.sub.0)+1/4U.sub.1 
EQU 3/4(3/4(3/4V.sub.0 +1/4V.sub.0)+1/4V.sub.0)+1/4V.sub.1 
These reduce to 27/64 U.sub.0 +9/64U.sub.0 +12/64U.sub.0 +16/64U.sub.1 or 
3/4 U.sub.0 +1/4 U.sub.1, and 27/64 V.sub.0 +9/64 V.sub.0 +12/64V.sub.0 
+16/64 V.sub.1 or 3/4 V.sub.0 +1/4 V.sub.1. 
This algorithm works for all stretch operations, and the 3/4U.sub.n 1/4 
U.sub.n+1 and 3/4 V.sub.n 1/4 V.sub.n+1 would be used for averaging 
between pixels which traverse packet boundaries. It should be noted that 
stretch and shrink values can be non-integer quantities (e.g. 3.06) for 
this invention. 
In the foregoing approximation, the interpolator processed the values in a 
fixed 3/4 A+1/4 B format. If desired, the weighting of the chrominance 
components and the feedback of the sum could be altered to perhaps provide 
an even superior approximation. However, the prior art interpolator does 
not include the capability of altering the weighting during the 
processing, and the approximation attained without adding such additional 
control is adequate for the purposes intended without complicating the 
control circuitry for this purpose.