Real time digital video animation using compressed pixel mappings

• US 5,119,442 A
• Filed: 12/19/1990
• Issued: 06/02/1992
• Est. Priority Date: 12/19/1990
• Status: Expired due to Term

• Current Assignee: Pinnacle Systems Incorporated (Avid Technology Incorporated)
• Original Assignee: Pinnacle Systems Incorporated (Avid Technology Incorporated)
• Inventors: Brown, William B.
• Primary Examiner(s): Razavi, Michael
• Assistant Examiner(s): CAMMARATA, MICHAEL
• Application Number:
  US07/630,069
• Time in Patent Office: 531 Days
• Field of Search: 382/44, 382/47, 382/41, 382/56, 340/723, 340/725, 340/731, 340/791
• US Class Current: 382/235
• CPC Class Codes: G06T 13/80 2D [Two Dimensional] animation, e.g. using sprites
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00

Abstract

Method and apparatus for construction and use in real time of a sequence of pixel-to-pixel mappings that define a video image transformation of a sequence of video images in digital animation video image processing and display. A sequence of compressed mappings that approximate the required sequence of pixel-to-pixel mappings is constructred off-line, and this sequence of compressed mappings is stored for subsequent use and is designated by a selected indicium. When that sequence of pixel-to-pixel mappings is to be applied to a chosen set of video image fields, the sequence of compressed pixel mappings is called up by use of the indicium, the compressed mappings are decompressed, and the sequence of decompressed mappings is applied to the chosen set of video image fields in real time.

Claims

1. A method for animating a sequence of video image fields in real time, the method comprising the steps of:

performing a selected video transformation as a sequence of ordered mappings, where each of the sequence of video mappings is generated and performed off-line and is represented as a pixel-to-pixel mapping;

for each pixel-to-pixel mapping of a field, applying a compression mapping to that mapping to produce a compressed pixel mapping that approximates the original mapping;

storing the compressed pixel mappings as an ordered sequence of such mappings and providing this sequence with an indicium that corresponds to and indicates the selected video transformation, where each such indicium corresponds and indicates a unique video transformation;

whereby selection of a video transformation is implemented after selection of the corresponding indicium and application of the corresponding sequence of compressed pixel mappings to a presently received sequence of video fields presented in real time.

2. The method of claim 1, further comprising the steps of:

selecting an indicium corresponding to a video transformation sequence as a sequence of video image fields is received;

applying the sequence of compressed pixel mappings to the sequence of video image fields received; and

displaying the results of applying this sequence of mappings to this sequence of image fields as a sequence of video images in real time.

3. The method of claim 2, further comprising the step of:

providing a specification of at least one of the video image characteristics of high-light, color intensity and color for said video images; and

modifying this specified video image characteristic after said video transformation is constructed and before said video transformation is applied to said sequence of video image fields.

4. The method of claim 1, further comprising the step of choosing said compressed pixel mappings so that, at any pixel address, each of said compression mappings has an error that is no larger than a predetermined error.

5. The method of claim 1, wherein the step of choosing said compression mapping comprises the steps of:

providing a sequence of two-coordinate data addresses (v,w)=(v_m,w_m) (m=1,2, . . . , M) for said pixel-to-pixel mapping T, where v_m represents the x-address of a pixel destination address under said mapping, with vm <

vm+1 for all m, and where w_m is a descriptive coordinate of a source pixel corresponding to the destination pixel address;

providing a sequence of two-coordinate.. data.., addresses (v_cm,w_cm) (m=1,2, . . . , M) for said compressed pixel mapping, where v_cm =v_m represents the -x.-address of a pixel destination address under said compressed pixel mapping and w_cm is a- Descriptive Coordinate of a source pixel corresponding to the destination pixel address;

forming a graph of v_m versus w_m for the coordinate pairs (v_m,w_m) (m=1,2, . . . , M);

for each coordinate v=v_m (m=1,2, . . . , M), prodding an error interval defined by w_m -ε

_m ≦

w≦

w_m +ε

_m, where ε

_m is a predetermined positive number;

for each coordinate v=v_j (j=1,2, . . . , M) on this graph, defining ##EQU4## defining k1 as the largest integer in the range 1<

k<

M for which;

space="preserve" listing-type="equation">S.sub.2,k ≦

S.sub.2,k for k=2,3, . . . , k1,

and constructing a first line segment L1 on the graph defined by w_c (v)=S₁ (v-v₁)+w₁ to approximately represent resent the coordinate pairs (v_j,w_j) (j=1,2, . . . , k₁) on the graph, where S₁ is a line slope that lies in the range S₁,k1 ≦

S₁ ≦

S₁,k1 ;

defining w'"'"'_k1 =S₁ (v_k1 -v₁)+w₁, defining k2 as the largest integer in the range k1<

k≦

M for which

space="preserve" listing-type="equation">S.sub.k1,k ≧

S.sub.k1,k for k=k1+1, k1+2, . . . , K2,

and constructing a line segment L2 on the graph defined by w_c (v)=S₂ (v-v_k1)+w'"'"'_k1 to approximately represent the coordinate pairs (v_j,w_j) (j=k1, l1+1, . . . , k2) on the graph, where S₂ is a line slope that lies in the range S_k1,k2 ≦

S₂ ≦

S_k1,k2 ;

for each integer kn (n=2,3, . . . ) defined iteratively as below, defining a line segment Ln by w'"'"'_kn =S_n (v_kn -v_k(n-1))+w'"'"'_k(n-1), defining k(n+1) as the largest integer in the range kn<

k≦

M for which

space="preserve" listing-type="equation">S.sub.kn,k ≧

S.sub.kn,k for k=kn, kn+1, kn+2, . . . , k(n+1),

and constructing a line segment L(n+1) on the graph defined by w_c (v)=S_n+1 (v-v_kn)+w'"'"'_kn to approximately represent the coordinate pairs (v_j,w_j) (j=k_n, kn+1, . . . , k(n+1)) on the graph, where S_n+1 is a line slope that lies in the range S_kn,k(n+1) ≦

S_n+1 ≦

k_n,k(n+1) ; and

defining w_cm =w_c (v=v_m ) for m=1,2, . . . , M and defining said mapping T by the relation T(v_m,w_m)=(v_cm,w_cm)(m=1,2, . . . ,M).

6. The method of claim 5, further comprising the step of choosing at least two of said error bounds ε

_j to be equal.

7. The method of claim 5, further comprising the steps of:

expressing each of said parameters S₁ and w₁ that define said first line segment L1 binary form as a p-bit number (p=12-14 ), with 10 bits of this number representing the whole number w-address and p-10 bits of this number representing the fractional w-address of this number for the parameter S₁ or w₁ ; and

expressing each of said parameters S_n and w'"'"'_kn that define said nth line segment Ln(n≧

2) in the form

space="preserve" listing-type="equation">S.sub.n =S.sub.n-1 +Δ

S.sub.n,

space="preserve" listing-type="equation">w'"'"'.sub.kn =w'"'"'.sub.k(n-1)+Δ

w'"'"'.sub.kn,

where Δ

S_n and Δ

w'"'"'_kn are each expressed as a q-bit number (q=12-14 ), with 5 bits of this number representing the whole number w-address and 7-9 bits of this number representing the fractional w-address of this number for the parameter Δ

S_n or Δ

w'"'"'_kn.

8. The method of claim 7, further comprising the steps of:

expressing said parameter Δ

S_n (n=2) in binary form as first and second associated numbers, with the first number having 16 bits, if Δ

S_n <

1, with 9 of the bits representing the fractional part of said parameter Δ

S_n, with a tenth bit being zero and the remaining 6 bits of this first number representing the run length RL of said line segment Ln, expressed as an integer in binary form, if RL≦

64;

with the second number having six bits representing an excess run length RL-64 of said line segment Ln, if the run length of said line segment Ln satisfies the conditions 65<

RL<

128; and

representing the excess run length RL-64 of said line segment Ln if the run length of said line segment Ln satisfies the conditions 129≦

RL≦

1024.

9. The method of claim 7, further comprising the steps of:

expressing said parameter Δ

w'"'"'_kn (n=2) in binary form as first and second associated numbers, with the first number having 16 bits, if Δ

w'"'"'_kn <

1, with 9 of the bits representing the fractional part of said parameter Δ

,w'"'"'_kn, with a tenth bit being zero and the remaining 6 bits of this first number representing the run length RL of said line segment Ln, expressed as an integer in binary form, if RL≦

64;

with the second number having six bits representing an excess run length RL-64 of said line segment Ln, if the run length of said line segment Ln satisfies the conditions 65≦

RL≦

128; and

with the second number having ten bits representing the excess run length RL-64 of said line segment Ln if the run length of said line segment Ln satisfies the conditions 129≦

RL≦

1024.

10. The method of claim 1, wherein said step of applying said compression mapping to said pixel-to-pixel mapping T comprises application of a linear predictor line-by-line to said pixel-to-pixel mapping T to a video image field to be transformed.

11. The method of claim 10, wherein said step of applying a compression mapping further comprises choice of a maximum error associated with said linear predictor that is no larger than a predetermined fraction f of the nearest neighbor distance between pixels.

13. The method of claim 10, further comprising the step of choosing at least two of said error bounds ε

_j to be equal.

14. The method of claim 10, further comprising the steps of:

expressing each of said parameters S₁ and w₁ that define said first line segment L1 binary form as a p-bit number (p=12-14 ), with 10 bits of this number representing the whole number w-address and p-10 bits of this number representing the fractional w-address of this number for the parameter S₁ or w₁ ; and

expressing each of said parameters S_n and w'"'"'_kn that define said kth line segment Ln (n=2) in the form

space="preserve" listing-type="equation">S.sub.n =s.sub.n-1 +Δ

S.sub.n,

space="preserve" listing-type="equation">w'"'"'.sub.kn =w'"'"'.sub.k(n-1)+Δ

w'"'"'.sub.kn,

where Δ

S_n and Δ

w'"'"'_kn are each expressed as a q-bit number (q=12-14), with 5 bits of this number representing the whole number w-address and 7-9 bits of this number representing the fractional w-address of this number for the parameter Δ

S_n or Δ

w'"'"'_kn.

15. The method of claim 14, further comprising the steps of:

expressing said parameter Δ

S_n (n=2) in binary form as first and second associated numbers, with the first number having 16 bits, if Δ

S_n <

1, with 9 of the bits representing the fractional part of said parameter Δ

S_n, with a tenth bit being zero and the remaining 6 bits of this first number representing the run length RL of said line segment Ln, expressed as an integer in binary form, if RL≦

65;

with the second number having six bits representing an excess run length RL-64 of said line segment Ln, if the run length of said line segment Ln satisfies the conditions 65≦

RL≦

128; and

with the second number having ten bits representing the excess run length RL-64 of said line segment Ln if the run length of said line segment Ln satisfies the conditions 129≦

RL≦

1024.

16. The method of claim 14, further comprising the steps of:

expressing said parameter Δ

w'"'"'_kn (n=2) in binary form as first and second associated numbers, with the first number having 16 bits, if Δ

w'"'"'_kn <

1, with 9 of the bits representing the fractional part of said parameter Δ

w'"'"'_kn, with a tenth bit being zero and the remaining 6 bits of this first number representing the run length RL of said line segment Ln, expressed as an integer in binary form, if RL≦

64;

with the second number having six bits representing an excess run length RL-64 of said line segment Ln, if the run length of said line segment Ln satisfies the conditions 65≦

RL≦

128; and

with the second number having ten bits representing the excess run length RL-64 of said line segment Ln if the run length of said line segment Ln satisfies the conditions 129≦

RL≦

1024.

12. A method of compression of data address information, where the information is available in the form of a collection of triples (u,v,w)=(u_m, v_m, w_m) (m=1,2, . . . , M), where w_m is a real number representing a descriptive coordinate of the source address of a pixel and v_m and u_m are real numbers representing the x-coordinate and y-coordinate, respectively, of the destination pixel address corresponding to that source address pixel under a predetermined pixel-to-pixel transformation T on a screen, the method comprising the steps of:

forming a graph of v_m versus w_m for the coordinate pairs (v_m,w_m) for m=1,2, . . . , M with v_m <

v_m+1 for all m;

for each coordinate v=v_m (m=1,2, . . . , M) on this graph, providing an error interval defined by w_m -ε

_m ≦

w ≦

w_m +ε

_m where ε

_m is a predetermined positive number;

for each coordinate v=v_j (j=1,2, . . . , M) on this graph, defining ##EQU5## defining k1 as the largest integer in the range 1<

k≦

M for which

space="preserve" listing-type="equation">S.sub.2,k ≦

S.sub.2,k for k=2,3, . . . k1,

and construction a first line segment L1 on the graph defined by w_c (v)=S_l (v-v_l)+w_l to approximately represent the coordinate pairs (v_j,w_j) (j=1,2, . . . , k_l) on the graph, where S_l is a line slope that lies in the range S₁,k1 ≦

S₁ ≦

S₁,k1 ;

defining w'"'"'_k1 =S_l (v_kl -v_l)+w₁, defining k2 as the largest integer in the range k1<

k≦

M for which

space="preserve" listing-type="equation">S.sub.k1,k ≧

S.sub.k1,1 for k=k1+1, k1+2, . . . , k2,

and constructing a line segment L2 defined by w_c (v)=S₂ (v-v_k1)+w'"'"'_k1 to approximately represent the coordinate pairs (v_j, w_j) (j=k1, k1+1, . . . , k2) on the graph, where S₂ is a line slope that lies in the range S_k1,k2 ≦

S₂ ≦

S_k1,k2 ; and

for each integer kn (n=2,3, . . . ) defined iteratively as below, defining a line segment Ln by w'"'"'_kn =S_n (v_kn -v_k(n-1)+w'"'"'_k(n-1), defining k(n+1) as the largest integer in the range kn<

k≦

M for which

space="preserve" listing-type="equation">S.sub.kn,k ≦

S.sub.kn,k for k=kn, kn+1, kn+2, . . . , k(n+1),

and constructing a line segment L(n+1) on the graph defined by w_c (v)=S_n+1 (v-v_kn)+w'"'"'_kn to approximately represent the coordinate pairs (v_j,w_j) (j=kn, kn+1),

defining w_cm =w_c (v=v_m) for m=1,2. . . ,M and defining said mapping T by the relation T(v_m,w_m)=(v_cm,w_cm)(m=1,2. . . ,M).

17. A method of representing a video image edge that defines a boundary between a first image and a second, different image, where an image is represented by a rectangular array of pixels, each pixel having two dimensional coordinates (x_m,y_n) representing the pixel'"'"'s position on a display screen and having a pixel value pv(x_m,y_n) associated with the pixel positioned at (x_m,y_n), the method comprising the steps of:

if the edge separates the pixel having coordinates (x_m,y_n) from at least one of the pixels having coordinates (x_m+m, Y_n) and (x_m, Y_n+n) providing predetermined non-negative coefficients c₀, c₁ and c₂ and forming an interpolated pixel value pv(x_m,y_n)_int defined by the relations

space="preserve" listing-type="equation">pv(x.sub.m,y.sub.n).sub.int =c.sub.0 pv(x.sub.m+m,Y.sub.n)+c.sub.1 pv(x.sub.m,y.sub.n)+c.sub.2 pv(x.sub.m,Y hd n+n),

space="preserve" listing-type="equation">c.sub.0 +c.sub.1 +c.sub.2 =1; and

replacing the pixel value pv(x_m,y_n) by pv(x_m,y_n)_int, and forming and displaying on a video screen the first and second images with the pixel value pv(x_m,y_n)_int being substituted.

18. Apparatus for reconstruction from a compressed pixel mapping, of an approximation to an original pixel-to-pixel mapping that existed before compression, where the original mapping maps a first ordered sequence of pixel data addresses into a second sequence of data addresses so that the second sequence corresponds to and provides approximations for precise data addresses in the first sequence, and the original mapping is approximated by an approximation mapping that is a collection of linear mappings of consecutive groups of two or more pixel data addresses into a third sequence of data addresses, the apparatus comprising:

a first information source to receive, for each data address, a first information field containing the precise data address for each pixel in the domain of the approximation mapping, to issue the precise data address as an output signal, to issue first and second control output signals indicating whether the precise data address or an approximate data address is to be used for that data address, and to receive a clock pulse at a clock input terminal;

a second information source to receive, for each data address, a second information field indicating the correction required, if any, for a line segment parameter so that the data address belongs to the line segment with corrected line segment parameter, and to issue this information as an output signal corresponding to that data address, and to receive a clock pulse at a clock input terminal;

a first multiplexer having first, second, and third input terminals; and

first and second control input terminals; and

an output terminal;

to receive the output signal of the first information source at its'"'"' first input terminal;

to receive the first and second control output signals at its'"'"' first and second control terminals; and

to issue as an output signal the signal received at the first input terminal, at the second input terminal, or at the third input terminal according to the values of the first and second control signals received;

a first data address register having an input terminal, a clock input terminal, and an output terminal, to receive and temporarily hold a first data address from the first multiplexer and to issue this data address as an output signal when the clock input terminal receives a clock pulse;

a second multiplexer having first and second input terminals, a control input terminal)and an output terminal, to receive the output signals from the first information source and from the first data address register at its'"'"' first and second input terminals, respectively, to receive the first control signal from the first information source at its control input terminal, and to issue as an output signal the signal received at its'"'"' first input terminal or at its'"'"' second input terminal according to the value of the first control signal received;

a second data address register having an input terminal, a clock input terminal, and an output terminal;

to receive and temporarily hold a second data address that is the output signal from the second multiplexer and to issue this address as an output signal when the clock input terminal receives a clock pulse;

signal summation means having first and second input terminals to receive the output signals of the second information source and the first data address register thereat and to form and issue the sum of these two input signals as an output signal;

predictor means having first and second input terminals, for receiving as input signals the first and second data address register output signals and for forming and issuing, as an output signal, a weighted sum of these two input signals as a prediction of the next consecutive data address based upon the first and second data addresses received, where the output signals of the signal summation means and the predictor means are received as input signals at the second and third input terminals of the first multiplexer;

a delay register having an input terminal, a clock input terminal, and an output terminal to receive the first multiplexer output signal at its input terminal and to issue the signal received as an output signal, when the clock input terminal receives a clock pulse thereat; and

a clock pulse source to provide a sequence of periodic clock pulses for the clock input terminals of the first and second information sources, the first and second data address register), and the delay register;

whereby the output signal of the third multiplexer reproduces the pixel mapping that approximates the original pixel-to-pixel mapping.

19. Apparatus for forming and issuing pixel value signals that determine a video image, defined by a rectangular array of pixels, to be displayed on a video screen, beginning with a compressed mapping of the pixels, the apparatus comprising:

first and second field buffers for receiving, storing, and issuing as output signals pixel values that determine image intensity or image high-light for first and second interlaced fields of pixels representing a video image under a compression mapping of the pixels;

third and fourth field buffers for receiving, storing, and issuing as output signals pixel values that determine image surface characteristics for the first and second interlaced fields of pixels;

fifth and sixth field buffers for receiving, storing, and issuing as output signals pixel values that determine the pixel source x-address of the video image for the first and second interlaced fields of pixels;

seventh and eighth field buffers for receiving, storing, and issuing as output signals pixel values that determine the pixel source y-address of the video image for the first and second interlaced fields of pixels;

first decompression means, for receiving the first and second field buffer output signals and applying a decompression mapping to these signals to produce decompressed first and second fields of pixel values representing decompressed video image intensity or video image high-light pixel values, and for issuing the decompressed first and second fields as output signals;

second decompression means, for receiving the third and fourth field buffer output signals and applying a decompression mapping to these signals to produce decompressed third and fourth fields of pixel values representing decompressed video image surface characteristics pixel values, and for issuing the decompressed third and fourth fields as output signals;

third decompression means, for receiving the fifth and sixth buffer output signals and applying a decompression mapping to these signals to produce decompressed fifth and sixth fields of pixel values representing decompressed video image pixel destination x-addresses, and for issuing the decompressed fifth and sixth fields as output signals;

fourth decompression means, for receiving the seventh and eighth buffer output signals and applying a decompression mapping to these signals to produce decompressed fifth and sixth fields of pixel values representing decompressed video image pixel destination y-addresses, and for issuing the decompressed seventh and eighth fields as output signals;

high-light/color determination means, for receiving the output signals from the first and second decompression means, for forming and issuing a first high-light/color module output signal representing high-light or intensity of a pixel, and for forming and issuing a second high-light/color module output signal representing the B-Y color component of a pixel;

address/color means, for receiving the second, third and fourth decompression means output signals, for forming and issuing a first output signal representing the Y and R-Y color components of a pixel and for forming and issuing a second output signal representing the x-address and y-address of a pixel;

a background color register, having an input terminal to receive a background color control signal that determines a background color, if any, for a pixel and having an output terminal that issues an output signal representing the background color choice for that pixel;

a first multiplexer;

having three input terminals, a control input terminal and an output terminal, that receives the background color register output signal at a first terminal;

that receives the Y, R-Y, and B-Y color component signals at a second input terminal;

that receives a supplemental pixel color signal at a third input terminal; and

that issues the signal received at the first, second or third input terminal as an output signal at the output terminal;

depending on the control signal received at the control input terminal;

color palette means, having an input terminal, a control input terminal, and an output terminal;

for receiving the first multiplexer output signal at the input terminal;

for receiving a color control signal at the input control terminal; and

for forming and issuing a palette color output signal that determines the basic color for a pixel;

blend color means, having a first input terminal for receiving a blend color command signal, having a second input terminal for receiving a pixel specification signal that identifies the pixel for which the blend color command signal is received, and having an output terminal for issuing the blend color command signal, and a signal identifying the pixel to which the blend color command signal corresponds, as output signals;

a second multiplexer, having two input terminals, a control input terminal, and an output terminal;

to receive the first multiplexer ;

output signal and the color palette means of the first and second input terminals, respectively, to receive a control signal at the control input terminal; and

to issue at the output terminal the signal received at the first input terminal or at the second input terminal, depending upon the control signal received; and

intensity/high-light color mixer means, having four input terminals, a control input terminal, and an output terminal;

for receiving the second multiplexer output signal, the blend color means output signal, the high-light/color means output signal, and the second decompression means output signal at the first, second, third, and fourth input terminals, respectively, for receiving at the control input terminal a control signal indicating the pixel whose pixel value is determined by the first, second, third, and fourth input signals;

for forming and issuing at the output terminal a pixel value signal for which color, high-light, and intensity are determined.