Soft Edge Chroma-Key Generation Based Upon Hexoctahedral Color Space

The present invention relates to a chroma-key processing method and system for processing color image of various modes in the form of RGB numerical data into composite with another color image.

According to chroma-key technique used in producing a video image, a foreground object to be composited is placed in front of a background panel painted in monochrome, typically in blue, and is shot by a camera as material with blue background (hereinafter referred to as blue-back material). The shot image is variously processed into an image with key signals of blue portions being 0% and of foreground portions being 100%. The image with the key signals is supplied to a switching unit in a conversion system with a background different from that of the blue-back material to obtain a composite image. If the key signals have only binary states of either 0% or 100%, a contour of the foreground object after composite may become unnatural. In order to overcome the problem, conventionally a so-called soft chroma-key system is used to allow transitional values between 0% and 100%. According to the conventional soft chroma-key technique, key signals are generated in terms of distance on chromaticity diagram which can be quantitatively representative of hue and color saturation among three color attributes of hue, color saturation and color value. According to the Japanese Patent 1st publication No. 62-66791, data of RGB (Red, Green and Blue) three primary colors on a foreground image are converted into data (X, Z) on two-dimensional orthogonal coordinate system, using conversion equations: ##EQU1## where .phi. is an angle of hue of the background color to B-Y axis on chromaticity diagram. The values of X and Z obtained from the above equations are used to obtain value k of key signal:

where a is an adjustable parameter. In reality, the value k is further used with variable gain k, and offset ko to obtain value k' as value of key signal:

According to this technique, data pairs of X and Z will draw a parabola with a focus and a directrix being respectively on the X and Z axes of a chromaticity diagram when the value k' becomes constant.

However, the orthogonal coordinate of X and Z in the prior art provides no information on color value and therefore cannot discriminate, for example, light blue from dark blue.

With the soft chroma-key system, the value of the key signal may take transitional value to process contour and semitransparent foreground. However, since such conventional system does not handle the build-up of the blue-back image based on a specific theory, extracted results may be often unnatural and/or any extra process step such as so-called "chroma cancel" which is inherently unnecessary may be required to improve apparent image quality.

In the case of division on chromaticity diagram by means of a single non-closing line, a foreground with colors of high and low saturations in combination cannot be processed by using a background with color of transitional saturation.

It has been proposed to determine parameters by cursor-pointing background positions on a screen, using a position pointer such as a mouse or tablet. However, this solution is limited to keying processing of a hard edge. Processing of dissolve portions of soft chroma-key with variable resistance cannot be intuitively manipulated.

According to the present invention, inputted RGB three primary color data are directly handled in three-dimensional space without mapping them over two-dimensional space such as a chromaticity diagram so as to use the data without loss of information quantity. Therefore, it is a function of 3 variables which determines the key value k of a key signal and it is expressed by a scalar field in RGB thee-dimensional space. This function is called an identification function.

When RGB data of foreground image taken by blue-back shooting are plotted in RGB three-dimensional space, pixels 1 of the background are distributed in a relatively small area near B axis as shown in FIG. 1. By contrast, pixels 2 of the foreground are distributed as several sets of banana-shaped areas at positions away from the pixels 1 of the background. Pixels on the boundary between pixels 1 and 2 are distributed substantially in an area of a triangle having its base and apex constituted by the banana-like distributed pixels 2 and the background pixels 1, respectively. In scalar field representative of key value k, it is ideal that there are the banana-like distributed pixels 2 by 100% and the background pixels 1 by 0% and that values gradually increase from the apex toward the base of the triangle.

The scalar field used to express identification function is defined by two hexoctahedrons 40 and 41 as shown in FIG. 2 with a shape suitable for distribution of the image data in RGB three-dimensional space, key value k being calculated which can smoothly express contour and/or semitransparent portions. Once key value k is determined, color of the pixel 2 of foreground portions related to background color such as semitransparent portions is converted to natural foreground color according to model induced from a theory of image composite.

Since the scalar field can be defined to include any arbitrary position on RGB three-dimensional space, restriction to background color is extensively reduced: and keying may be performed if there is no back color in the foreground color.

After chroma-key parameters have been set for hard edge, parameters for soft edge are specified for portions where even foreground may become transparent. Then, portions which are not to be transparent are repeatedly pointed by mouse or tablet on screen to set parameters for soft key.

A preferred embodiment of the present invention will be described in conjunction with the attached drawings.

FIG. 1 is a schematic illustration of color distribution in RGB three-dimensional space and field of key value;

FIG. 2 shows two hexoctahedrons defined in RGB three-dimensional space;

FIG. 3 schematically illustrates the entire image processing system including the system of the present invention;

FIG. 4 is a schematic illustration of arrangement of key value in triangular pyramid;

FIG. 5 is a graph showing function of key value and distance from background representative color;

FIG. 6 is a table showing details of an identification function parameter register;

FIG. 7 is a block diagram of the entire system of the present invention;

FIG. 8 is a block diagram of a color data location unit;

FIG. 9 shows a selector model of an identification function parameter register;

FIG. 10 is a block diagram of an alpha value calculation unit;

FIG. 11 is a flow chart for calculating value k through allocation in alpha value calculation unit; and

FIG. 12 is a block diagram of a color conversion unit.

FIGS. 1 to 12 are directed to a preferred embodiment of the present invention.

Inputted data in the present invention are digital data of blue-back material expressed by RGB. Output data are also RGB digital data and are representative of extracted image of foreground where the blue portions of the blue-back material are expressed in black.

Actual flow of image production is given in FIG. 3. First, blue-back material is shot by a camera 3 such as motion picture camera or video camera. In any case, data are converted by an image digitizer 4 such as film scanner or video digitizer into image data array 42 which is a set of numerical data on RGB three primary colors to be recorded on magnetic tape or fixed disk system. Spatial resolution of image and/or quantization bit width for color components may be freely selectable in the present invention.

The image data array 42 is read by a chroma-key processing system 5 according to the present invention and foreground extraction image 43 after processing is outputted as RGB digital data.

On the other hand, another image to be composited is also converted into image data 44 by the same procedure as above and is composited by an image compositing system 6 together with the foreground extraction image 43.

Composited results are recorded on film or video tape in the form of RGB digital image data array 45 by a video unit 7 such as a film recorder or frame memory.

In the chroma-key processing system 5 according to the present invention, the foreground image data array 42 is read first. This image is displayed on a computer display 38 in a user interface 37 as shown in FIG. 7 and parameters for generating key signals are prepared under computer-aided operation, using a position pointer 39 such as a mouse or tablet. This is usually performed once for each cut (a set of continuous frames from start to stop of a camera). Next, the mode is switched to continuous frame processing mode and the foreground image data arrays 42 are read one after another and all the pixels are processed using preset parameters. The processed results are outputted as foreground extraction image 43 and are sent to a subsequent process. The foreground extraction image 43 is of two kinds of data: that is, of the data of the key signals and of the foreground image which has been color-converted.

Definition of hexoctahedron to determine key value

The value k of the key signal is given by a linear equation as described below and the coefficient of the equation differs according to the position of of RGB color components of each foreground image datum in RGB three-dimensional space. As shown in FIG. 4, RGB three-dimensional space is defined by 48 triangular pyramids 46 which have common apices and the respective pyramid segments have different coefficient parameters. The value k defined by the parameters constitutes a scalar field which has a shape of hexoctahedron in RGB three-dimensional space as equipotential surface.

Forty-eight triangular pyramids are defined as follows: First, one color is determined as most typical background color and its RGB data are given. The color is called point of representative background color C.sub.o. In order to determine this color, normally sampling is performed several times from the background color portion on screen as RGB data, using a position pointer such as a mouse or tablet; and an average value of sampled results is used. From a point in RGB three-dimensional space representing this color C.sub.o, 26 straight lines are extended. Directional vectors of these straight lines are shown in Table 1. These are 6 lines in positive and negative directions along R, G and B axes, 12 lines of 45.degree. direction in 4 quadrants on 3 planes respectively including R and G axes, G and B axes and B and R axes (hereinafter referred to as RG, GB and BR planes, respectively) such as straight lines equally dividing an angle ROG on RG plane and 8 lines coordinate of which the absolute values of 3 components are equal (i.e., 8 lines having the same absolute coordinate-values for 3 components) when the point of C.sub.o is taken as original point in 8 spaces defined by RG, GB and BR planes. These 26 straight lines are given by the following equation:

where v.sub.n is a unit directional vector of a straight line indexed by n (Table 1). This vector is invariable.

Triangular pyramid 46 is formed by 3 adjacent straight lines among these 26 straight lines. Indices for 48 triangular pyramids 46 and indices for 3 straight lines constituting each triangular pyramid are shown in Table 2. These triangular pyramid spaces are part of RGB three-dimensional space cut off by 9 planes which pass through the point of C.sub.o. These 9 planes are 3 planes respectively parallel to RG, GB and BR planes, 2 planes including G axis and angularly displaced from RG plane respectively by 45.degree. and -45.degree., 2 planes including B axis and angularly displaced from GB plane respectively by 45.degree. and -45.degree. and 2 planes including R axis and angularly displaced from BR plane respectively by 45.degree. and -45.degree..

In a triangular pyramid 46, the value k of key signal is defined by two planes not crossing each other, i.e., by two triangles (FIG. 4). To make scalar field C.sup.o continuous, adjacent triangles of triangular pyramids 46 have common apices so that the two hexoctahedrons 40 and 41 determine key value k of any color in RGB three-dimensional space. Forty-eight triangles, each of which is defined by taking a point on each of the 26 straight lines and connecting points of 3 straight lines constituting each triangular pyramid 46, make up a hexoctahedron (forty-eight-faced polyhedron) 40 or 41. Scalar field is determined by arranging the two hexoctahedrons 40 and 41 which are smaller and larger and do not cross with each other.

Each hexoctahedron 40 or 41 is defined by 29 parameters, i.e., 26 Euclidean distances in RGB three-dimensional space from the point of the background representative color C.sub.o to each vertex and 3 components of the background representative color C.sub.o. Since the background representative colors of the smaller and larger hexoctahedrons 40 and 41 are the same, after all the hexoctahedrons 40 and 41 are defined by 55 adjustable parameters.

These data are set by user-interface computer program and are stored on a main memory.

Qualitatively, of these two hexoctahedrons 40 and 41, the pixels 1 of the color expressed by RGB data in a background region 47 which is inner of the smaller hexoctahedron 40 are regarded to have key value by 0% for the reason that these are completely in the background. The pixels 2 of the color expressed by RGB data in a fourground region 48 which is the outer of the large hexoctahedron 41 are regarded to have key value by 100% for the reason that these are completely in the foreground. A region between the two hexoctahedrons 40 and 41 are processed as soft key region, i.e. neither background nor foreground.

Alpha value calculation processing is as follows: Of two planes 50 and 51 in the triangular pyramid 46 space, the one closer to the background representative color C.sub.o is the plane of the smaller hexoctahedron 40. When the color datum of a foreground pixel is closer to the background representative color C.sub.o than this plane 50, key the value k at the pixel is 0%. If it is outside the other plane 51, key the value is 100%. If it is between the two planes, the closer it is to the inner plane 50, the lower key the value k it has. The closer it is to the outer plane 51, the higher key the value k is. Such key values k are calculated as function of distance from the background representative color C.sub.o.

It is supposed that the foreground pixel data to be processed is C.sub.r and that points where straight line connecting C.sub.r with C.sub.o crosses the inner and outer planes 50 and 51 are C.sub.1 and C.sub.2, respectively. If it is supposed that a distance from C.sub.o to C.sub.r, C.sub.1 and C.sub.2 are l.sub.r, l.sub.1 or l.sub.2, respectively, the value k is given by ##EQU2## FIG. 5 is a graphic representation of this function.

The distance in color space is calculated as follows: The indices of 3 straight lines constituting a triangular pyramid 46 are read from a look-up table (FIG. 6) and positions of apices of the two hexoctahedrons 40 and 41 on each of the straight lines are taken up as distances from C.sub.o from main memory. If subscript , is used as index for the straight line, apices A.sub.1 and B.sub.1 of inner and outer triangles, respectively, on each straight line are calculated as:

Equations for the inner and outer planes are:

Coefficients of these equations can be calculated using coordinates since each of the planes passes through three apices given by A.sub.i or B.sub.i.

If it is supposed that components of the foreground pixel data C.sub.r and of the background representative color C.sub.o are (r.sub.r, g.sub.r, b.sub.r) and (r.sub.o, g.sub.o, b.sub.o), respectively, straight line connecting these points are given by the following equation: ##EQU3## Simultaneous equations of the plane equation with the straight line equations are solved as: ##EQU4## Obtained here are parameters of length. The parameters t.sub.in and t.sub.out are lengths between the points C.sub.2 and C.sub.o and between the points C.sub.1 and C.sub.o, respectively, when length between the points C.sub.r and C.sub.o is 1 or unit.

Using the parameters tin and tout, the equation of the value k expressed by l.sub.r, l.sub.1 and l.sub.2 is calculated as: ##EQU5## The equations to obtain tin and tout are calculated for all pixels of the foreground. Development of the denominators of the equations results in: ##EQU6##

The numerator and three terms of the denominator, which do not depend upon C.sub.r and are constant in the triangular pyramid 46, can be calculated in advance. Thus, before going into the stage of processing RGB signals, the coefficients of the equations for the respective planes 50 and 51 of the hexoctahedrons 40 and 41 are obtained and these terms are calculated as identification function parameters DIN.sub.n and DOUT.sub.n (numerator) and EIN.sub.n and EOUT.sub.n (sum of three terms of denominator), i.e.

These are stored to an identification function parameter register 8 (FIG. 6) together with Cr as well as lout, mout, nout, lin, min and nin.

Processing of RGB Signals for foreground image

For the image to be processed, all pixel data 42 constituting foreground in RGB digital data are continuously inputted into the chroma-key processing system 5. The chroma-key processing system 5 performs processings independently for each pixel.

Internal structure of the chroma-key processing system 5 is as shown in FIG. 7. RGB digital data for one pixel obtained from an input unit 52 are sent to a color data location unit 10 (for identifying a belonging triangular pyramid), an alpha value calculation unit 11 and a color conversion unit 12.

First, processing is performed at the color data location unit 10 as shown in FIG. 8. The background representative color C.sub.o is present in the register 8.

RGB digital data of the foreground pixel 2 from the input unit 52 is sent to subtracters 13, 14 and 15 for each component and together with the data of the background representative color C.sub.o of the register 8. The data obtained from the subtracters 13, 14 and 15 are three-dimensional relative coordinates of the foreground pixel 2 in relation to the background representative color C.sub.o. Since 48 triangular pyramid segments are spaces obtained through cutting by 9 planes, a belonging triangular pyramid 46 can be identified by wholly investigating to which half-space the foreground pixel data belong with respect to each plane.

The belonging half-space to the planes parallel to RG, GB and BR planes can be determined by checking the sign of the component of relative coordinates. To the planes tilted by 45.degree., it can be determined by checking magnitude relation of the component or magnitude relation of the component with replaced sign. From three relative coordinates of RGB, two are picked up and processed through the subtracters 16, 18 and 20 and adders 17, 19 and 21 and a resultant sign is checked. Since a triangular pyramid 46 to which the foreground pixel 2 belongs is known beforehand from a combination of 9 signs, a look-up table 22 with corresponding triangular pyramid indices to nine-bit address is available (Table 3). Each of 9 sign testers 53 to 61 outputs "HIGH" and "LOW" when positive and negative, respectively, so that the address is supplied to the look-up table 22 as 9-bit numerical value. As the result, index of the belonging triangular pyramid is obtained as are output of the color data location unit 10 and is given to the parameter selector 9 which is downstream of the register 8.

When triangular pyramid indices 0 to 47 are given from the color data location unit 10 as shown in FIG. 9, the parameter selector 9 sends identification function parameters DIN.sub.n, DOUT.sub.n, EIN.sub.n, EOUT.sub.n, l.sub.out, m.sub.out, n.sub.out, l.sub.in, m.sub.in and n.sub.in to the alpha value calculation unit 11.

In the unit 11, the above-mentioned k value equation is calculated (FIG. 10). RGB signal of foreground pixel 2 given from the input unit 52 is sent to multipliers 23, 24 and 25 together with a coefficient supplied from the register 8. The sum of the result, EIN.sub.n and EOUT.sub.n is obtained by multipliers 26 and 26' and is sent to dividers 27 and 28 together with DIN.sub.n and DOUT.sub.n. Output results tin and tout from the dividers 27 and. 28 obtained by two sets of identification function parameters for the inner and outer planes 50 and 51 are checked by a comparator 29 as to whether they are larger or smaller than 1. The results are allocated and are outputted as key value k after clipping processing. A flow chart for allocation is given in FIG. 11.

Color conversion unit

In the image compositing system 6 (FIG. 3) downstream of the chroma-key processing system 5, composite processing of foreground with another background is performed by the following composite equation: ##EQU7## where C.sub.dst, is color data of image after composite, C.sub.front is color data of an object (foreground) and C.sub.back is color data of background which is prepared independently of the foreground. The value k is obtained by the alpha value calculation unit 11.

To obtain C.sub.dst which is the data of the composited image, it is necessary to give .alpha.C.sub.front and this value is measured by the color conversion unit 12. If the blue-back foreground material image is calculated by the above composite equation, C.sub.dst in the equation is the input color data C.sub.r in the processing obtained as the foreground material, C.sub.front is the color of the foreground portion in the input image and C.sub.back is the background representative color C.sub.o in the input image. In this case, .alpha.C.sub.front can be calculated using the equation: ##EQU8## FIG. 12 shows internal processing of the color conversion unit 12. The value k obtained in the above is subtracted from 1 by an inverter 30 and is given to multipliers 31, 32 and 33 together with the components of the background representative color C.sub.o. RGB data thus obtained are given to subtracters 34, 35 and 36 together with RGB data of the foreground pixels and results are outputted from an output unit 62.

Key value parameter input

To set the parameters necessary for calculation of key value k, the following procedure is taken: First, the foreground material image is displayed on a computer display 38 (FIG. 7). Next, on this screen, the portions which can be considered to be the background are sampled by a position pointer 39 such as a mouse or tablet. The sampling is effected by, for example, specifying a rectangular area to take up RGB data within this area or continuously sampling positions where the cursor passes through. An average value of the RGB data thus sampled is used as the background representative color C.sub.o. A smaller hexoctahedron 40 is prepared which contains all sampled data in it.

The hexoctahedron 40 (FIG. 2) is determined as follows: The following procedure is repeated for all sampled RGB data. Using the color data location unit 10 (FIG. 7), it is checked as to which of triangular pyramids 46 constituting the hexoctahedron 40 the data are in. If the data are in the triangular pyramid 46 within the smaller hexoctahedron 40, it is advanced to the next data processing. If it is outside, a plane 50 (FIG. 4) is obtained by numerical calculation (gradient method) where the sum of the distances (segments) between the crossing points of each axis of triangular pyramids 46 with the plane passing through the data point and the background representative color C.sub.o becomes minimal and this is regarded as the plane 50 of the inner hexoctahedron 40. If each segment is shorter than the length of the segment of the plane which has been present up to that moment, the previous segment is used. This prevents the data already classified as being inside the smaller hexoctahedron 40 from being newly classified to outside.

By the above procedure, parameters are set for the hexoctahedron 40 and, actually, foreground extraction and test composite are accomplished. As the result, if the foreground portion completely remains on screen, the same shape determination method is repeated by the above sampling procedure until there will be no more complete background portion.

Next, the larger hexoctahedron 41 is defined. First, a considerably large value as 26 segments of the outer hexoctahedron 41 is provisionally inputted. For this, a predetermined value is substituted or a user sets an adequate value manually. Since the outer hexoctahedron 41 is considerably large, the portion inherently to be completely in the foreground is also included in a dissolve region. By test composite, an image is obtained in which the foreground portion is discolored and is semitransparent. By the above sampling procedure, the portion which should be classified to the foreground is sampled. As a result, the larger hexoctahedron 41 is prepared in which all sampled data are outside of it.

This shape determination method is different from that of the smaller hexoctahedron 40 and is as follows: For all RGB data sampled, the following procedure is repeated. Using the color data location unit 10, it is checked as to which of the triangular pyramids 46 constituting the hexoctahedron 41 the data are in. If the data are outside the plane of the larger hexoctahedron 41 in the triangular pyramid 46 at present, it is advanced to the next data processing. If the data are inside, the plane 51 is determined such that the distances (segments) between the crossing points of each axis of triangular pyramid 46 with the plane 51 passing through the data point and the background representative color C.sub.o are proportional to sine the of the angle between the straight line connecting the data point with the background representative color C.sub.o and each axis. If each segment is longer than the length of the segment of the plane 51 which has been present up to that moment, the same calculation is performed with the plane using the previous section. This prevents the data which is already classified as being outside the larger hexoctahedron 41 from being are newly classified to inside.

It is to be understood that the present invention is not limited to the above-mentioned embodiment and that various modifications may be made without departing from the true spirit of the present invention.

According to the present invention, it is possible to composite contour, blurred edge, out-of-focused edge, semitransparent object, object shadow, extremely complicated object such as hair blown by wind, net, cloud, flame, etc. of foreground in natural manner, which cannot be effected by the conventional chroma-key methods.

Setting of key parameters including soft key parameters is facilitated by pointing a complete background portion or a complete foreground portion, using a position pointer such as tablet or mouse.