Real time video image processing system

• US 5,384,912 A
• Filed: 05/29/1992
• Issued: 01/24/1995
• Est. Priority Date: 10/30/1987
• Status: Expired due to Fees

• Current Assignee: New Microtime Incorporated
• Original Assignee: New Microtime Incorporated
• Inventors: Mayer, Steven T., Schlag, John F., Collier, Ronda L., Stewart, Bradley G., Hersh, Clifford, Pon, Raymond, Jensen, Sven, Collins, Kevin M., Knittel, Brian C., Burns, Chris R., Clarke, Charles P., Wade, Andrew E., Lay, Robert L., Stead, Lawrence, Leyland, Robert, Card, Robert A., Crane, Stephen E., Ogrinc, Michael A.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US07/892,607
• Time in Patent Office: 970 Days
• Field of Search: 382/46, 340/731, 340/747, 340/750, 395/162, 395/163, 395/164, 395/165, 395/166, 345/136, 345/137, 345/138, 364/728.01, 364/728.02
• US Class Current: 345/501
• CPC Class Codes: G06F 17/175 of multidimensional data
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 3/00 Geometric image transformations in the plane of the image
• CPC Class Codes: H04N 5/2628 Alteration of picture size, shape, position or orientation, e.g. zooming, rotation, rolling, perspective, translation
• CPC Class Codes: H04N 7/002 Special television systems not provided for by H04N7/007 - H04N7/18 still pictures via a television channel H04N1/00098
• CPC Class Codes: H04N 9/74 for obtaining special effects H04N9/65 - H04N9/73 take precedence

Abstract

A video digital signal processing and display system that allows real time processing of video images with extensive filtering and inter-pixel interpolation. The system includes a front end user and program interface supported by a personal computer, and also includes a microprocessor for controlling the system and specialized video circuitry including an image translator.

The image translator performs image translation, perspective projection, scaling, rotation, border insertion, and formation of composite images. The image translator interacts with the other specialized video circuitry which includes a frame constructor, a keyer and crosspoint switches, and a frame store constructor.

Claims

1. In a video system that displays a video image by means of a substantially rectangular array of picture elements or pixels, each pixel having an associated pixel value pv that contributes to the video image, with each row in the array containing about the same number of pixels and each column in the array containing about the same number of pixels, where the length of the array is N•

N₁ pixels and the height of the array is N•

N₂ pixels and N, N₁ and N₂ are all integers, a method for interpolation of the pixel value of a fictitious pixel whose position lies between and does not coincide with any of the pixels that comprises the video image array, the method comprising the steps of;

choosing an array of N×

N pixels from the video image array, with the boundaries of this chosen array being parallel to the boundaries of the video image array and with the fictitious pixel lying near the center of this chosen array; and

providing a filter including an array of, N2 averaging coefficients (C(m,n)), where m, n=0, 1, . . . , N-1 and the sum ##EQU36## and forming a weighted sum of pixel values ##EQU37## where the sequence {pv(m,n)}_m,n-0^N-1 includes all pixel values in the chosen N×

N array of pixels, with each such pixel value in the chosen array appearing as one member pv(m,n) of this sequence;

wherein said step of providing an array of said averaging coefficients and forming a weighted sum of said coefficients comprises the steps of;

dividing said video image array of pixels into a sequence of Fundamental Blocks of, N² pixels each, with each pixel belonging to only one such Fundamental Block and with the boundaries of each Fundamental Block being parallel to the boundaries of said video image array;

assigning to each pixel in said video image array the rectangular coordinates (m,n), where m=0,1,2, . . . , N•

N₁ -1 and n=0,1,2, . . . , N•

N₂ -1, , with the pixel in the upper left corner of said video image array being assigned the coordinates (0,0), and a pixel in said array that lies m consecutive pixels to the right from the left boundary of said video image array and lies n consecutive pixels down from the top boundary of said video image array being assigned the coordinates (m,n);

providing an array of N² memories, numbered r=0,1,2, . . . , N² -1, with each such memory including a designated rectangular array of length N₁ and height N₂ of memory addresses having rectangular coordinates (p,q) beginning with (0,0) in the upper left corner of such array and proceeding in a manner substantially identical to that of the rectangular coordinate system for said video image array;

providing a mapping T(m,n) to store the pixel value pv(m,n) in said video image array with video image array pixel coordinates (m,n) in the memory address ##EQU38## in the designated rectangular array of memory number r=m-m_n +N(n-n_N),where ##EQU39## for m=0,1,2, . . . , N₁ •

N-1 and n=0,1,2 . . . , N₂ •

N-1;

rotating in a first direction by one address unit each of the designated memory arrays number r=S₁ +k₁ •

N (K₁ =0, 1, . . . , N-1;

s₁ =0, 1, . . . , p'"'"'-1), where p'"'"'=m'"'"'-m_N, then rotating in a second direction by one address unit each of the designated memory arrays number 1;

s₂ =0,1, . . . , n-1), where q'"'"'=n'"'"'-n_N and where (m'"'"',n'"'"') are the coordinates of the pixel in a corner of said chosen array that is centered on said fictitious pixel position wherein said rotating changes the pixel value stored in each memory;

applying the map T^-1 (r;

p,q) to the contents at coordinates (p,q) of a subset of the designated rectangular arrays of the memories r=0,1,2, . . . , N² -1 resulting from the immediately preceding rotation step to produce an N×

N array of pixel values pv'"'"'(m,n) corresponding to said video image array coordinates ##EQU40## where m=m'"'"'_N, m'"'"'_N +1, . . . , m'"'"'_N -1 and n=n'"'"'_N +n'"'"'_N +1, . . . , n'"'"'_N N-1;

providing a sequence of N² permutations P_t (t=0,1,2, . . . , N² -1) on a N×

N array of entries where permutation number t=k₃ •

N (k₃ =0,1,2, . . . , N-1) is a one-place rotation in the second direction of the rows of the array K₃ times with end-around carry and permutation number t=k₃ •

N+s (s=1,2, . . . , N-1) is the permutation number r=k₃ •

N followed by an s-place rotation in the first direction of the columns of the N×

N array with end-around carry;

forming the permuted array P_t -1C(m,n)=Q(m,n) of coefficients where t=m'"'"'-m'"'"'_N •

(n'"'"'-n'"'"'_N) and {C(m,n)} is said array of averaging coefficients;

forming the sum ##EQU41## as the interpolated pixel value; and

displaying in place of a portion of the original video image the interpolated pixel value for a plurality of pixels.

2. In a video system with a video image defined by an array comprising lines of pixel values associated with picture elements or pixels, with array position coordinates (X_m, Y_n) (m=0,1,2, . . . , M'"'"';

n=0,1,2, . . . , N'"'"'), where each video image is formed by the combination of two fields with each field containing a subset of lines of pixels and the two lines of pixels comprising the array of pixels, where each line of pixels of one field is positioned between and adjacent to two lines of pixels of a second field, where a first field of pixel values is displayed on a video screen during time intervals t₀, t₂, t₄ and a second field of pixel values is displayed at time intervals t₁, t₃, t₅ and where t₅ precedes t₄ which precedes t₃ which precedes t₂ which precedes t₁ which precedes t₀ and where a pixel value of a pixel on line number k at horizontal position j with array position (x_j, y_k) has an associated pixel value pv(x_j,y_k ;

t) that is displayed during time interval t, a method of constructing a synthetic pixel value of a non-existent pixel at position (x_j,y_k) in a line of the second field that takes account of relative motion or change in time manifested by pixel values adjacent to array position (x_j,y_k), the method comprising the steps of;

determining the rapidity of change with time of each of the pixel values at each pixel position (x_j,y_k-1) and (x_j, y_k+1) between the time interval t₀ [(t₀, t₁)={t/t₀ <

t<

t₁ }] and the time interval t₂ and at each pixel position (x_j-1, y_K) between time intervals t₁ and t₃ ;

obtaining the pixel value pv(x_j+1, y_k ;

t) for t in the interval (t_t '"'"', t₂ '"'"')={t₁ <

t<

t₂ '"'"'};

introducing a parameter β

(0≲

β

≲

1) that is either continuous or has at least three distinct values β

=0, β

=1, and β

_i (0<

β

i<

1);

setting β

=0 if substantially no change with time is perceived in any of the pixel values at positions (x_j, y_y-1), (x_j, y_k+1), (x_j-1, y_k, and (x_j, y_k), setting β

=1 if rapid change with time is perceived at any of those pixel positions, and setting β

equal to an intermediate value β

_i if the change with time perceived at least one of these pixel positions is non-zero but the change with time perceived at each of these pixel positions is less than rapid;

forming the sum ##EQU42## as the synthetic pixel value; and

displaying the synthetic value for a pixel position in place of at least one pixel of the video image.

3. In a video system having substantially periodic horizontal blanking intervals, a method for rapid copying of pixel values from the video lines that comprise the video image to a set of M memories for subsequent display or storage, the method comprising the steps of:

providing a sequence of M fast-acting first-in-first-out registers, with each register having about the same number of pixel data storage positions where L is at least equal to the number of pixels that comprise a horizontal line of the video image divided by the value of M;

as each item of pixel data arrives at the video display system writing the data onto one of the registers in a predetermined pattern at the entry end of that register;

during a horizontal blanking interval of the video system, writing the pixel value appearing at the exit end of register number n to the corresponding memory number n for registers n=0,1,2, . . . , M.

4. In a video system with a video image defined by a two-dimensional array, with array positions (x_m, y_n), of picture elements or pixels and with each pixel having an associated pixel value pv that contributes to formation of the video image, a method of forming a desired signal value S of pixel values for up to a predetermined number M of pixels adjacent to a given target pixel, with weight coefficients that change from one target pixel to another target pixel and may change from one time interval Δ

t₁ to another time interval Δ

t₂, where the lengths of the time intervals Δ

t₁ and Δ

t₂ are each of the order of 74 nanoseconds, the method consisting of;

providing a filter including a predetermined number K of arrays (k=1,2, . . . , K) of weight coefficients C(J,k)_j-1^j.sbsp. stored in a random access memory system, with the weight coefficients being jk real numbers that satisfy the normalization constraint ##EQU43## providing coefficient choice means whereby an array C(j,k)_j-1^j.sbsp.k of weight coefficients may be chosen to form the weighted sum of j_k pixel values pv(x_m,y_n) of pixels with positions (x_m,y_n) adjacent to or in a predetermined neighborhood N(x_T,y_T) Of the position (x_T,y_T) of the target pixel;

providing coefficient change means whereby an array of weight coefficients can be changed in a time interval Δ

t that is substantially no greater than 74 nanoseconds

forming the desired signal value sum ##EQU44## and displaying the desired signal value in place of at least one of the predetermined number M of pixels in the video image.

5. A method of interpolating pixel signals in a video system for displaying a video image means of an array of picture elements each having an associate pixel signal, comprising the steps of:

choosing a portion of pixels from the array;

providing a plurality of sets of low pass filters, there being one filter in each set for each pixel of the portion;

providing a multiplexer for matching each of the filters to an associated pixel signal in the portion; and

forming an interpolated pixel signal as a function of the stored pixel signals of the portion by passing the portion of pixel signals through the matched filters.

6. The method of claim 5, further comprising the step of performing the step of providing a multiplexer on a first integrated circuit chip and performing the step of forming an interpolated pixel signal on a second integrated circuit chip.

7. In a video signal having a video image defined by an array of picture elements each having a pixel value, a method of displaying a pixel that takes into account motion manifested by pixel positions comprising the steps of:

determining the rapidity of change with time of the pixel positions at each of a plurality of picture elements over a particular time interval;

introducing three output signals associated respectively with no change, rapid change, and intermediate change in the particular time interval of pixel positions, the third signal being a function of the rapidity of change in the step of determining;

forming a synthetic value for each pixel position, the synthetic value being a function of the particular time interval, the output signal, and the pixel positioning in the particular time interval; and

displaying the synthetic value for each pixel position in place of the original pixel.

8. In a system for filtering a digital video signal including pixels dv(x_j), a method of forming a desired signal S of values for up to a predetermined number M of pixels adjacent to a given pixel, with weight coefficients that change from one pixel to another pixel and may change from a first time interval to a second time interval, where the length of both time intervals is equal to a cycle time of the video system, the method comprising the steps of:

providing a predetermined number K of digital filter arrays (k=1,2, . . . , K) of weight coefficients {C(j,k)}j-1 stored in a memory system;

providing a coefficient choice whereby an array {C(j,k)}_j-1^m of weight coefficients are chosen to form the

weighted sum of M pixel values dv(x_m) of pixels with positions (x_m) adjacent to or in a predetermined neighborhood of the position (x_T) of a particular pixel;

changing coefficients whereby an array of weight coefficients can be changed in a time interval that is substantially no greater than the first time interval;

forming the desired signal value sum ##EQU45## for the number K;

displaying the desired signal value in place of at least one of the M pixel values in the video signals; and

wherein the step of changing coefficients is performed by one integrated circuit chip.

9. A method of filtering a digital video signal defined by a plurality of pixels each having an associated pixel value, comprising the steps of:

providing a predetermined number of arrays of digital filters in a plurality of storage locations;

selecting one of the arrays at repeated time intervals of no greater than 74 nanoseconds;

for each pixel in the digital video signal, applying the selected array to the pixel; and

displaying the filtered video signals in place of a portion of the digital video signal.

10. The method of claim 9, further comprising the step of providing the plurality of storage locations in random access memory.