Method for eliminating temporal and spacial distortion from interlaced video signals

A method and apparatus for the elimination of temporal and spacial distortions from interlaced video signals, particularly those that occur in signals associated with affine transformations. This elimination is particularly of value for signals that have been magnified so as to prevent the visual appearance of reverse movement of moving images. The removal of these distortions is achieved by sequentially inputting the images fields into three field buffers, updating the data in a rotary manner. This data is withdrawn from any two of the field buffers, while the third field buffer is being updated, and averaging the data from the two. When such averaged data is displayed, there is no apparent reverse direction motion to the image. The method and apparatus are applied to a system wherein there is affine transformation to achieve selected pan, tilt, rotation and magnification of images during the correction of distorted images received from a wide angle lens.

TECHNICAL FIELD 
The present invention relates to a method and apparatus, together with 
algorithms, for substantially eliminating predetermined temporal and 
spacial distortion from real-time interlaced video signals, and, more 
particularly, to the elimination of these distortions from video signals 
associated with affine transformations in performing pan, tilt, rotation 
and magnification, of video signals generated from images, for example, 
perceived from wide-angle lenses. Further, the invention relates to the 
elimination of visual evidence of the temporal shift caused by single line 
changes from the input image to the output image that are inherent in 
dynamic images that have undergone digital magnification. 
BACKGROUND ART 
During certain processing of interlaced video signals, and particularly 
those that have been digitized, there is apparent visual evidence of 
temporal shift upon a display of an image created by those video signals. 
Portions of certain types of images, for example, visually appear to be 
moving backward, with this effect being particularly observed when the 
images are magnified. When the interlaced video image is enlarged, an odd 
(or even) number of line shifts may occur in the picture elements 
(pixels). Even though conventional interlaced images refresh their display 
every field, for example, at sixty times a second, the temporal reversal 
of output relative to input may be perceptible to a viewer. 
One such area in which this temporal (and spatial) shift become apparent is 
in the systems described in commonly-owned U.S. Pat. Nos. 5,185,667 issued 
Feb. 9, 1993, 5,313,306 issued May 17, 1994 and 5,359,363 issued Oct. 25, 
1994. The contents of these patents are incorporated herein by reference 
as to their entire contents. 
In the technology described in these patents, video signals are 
electronically processed for their transformation according to pan and 
tilt orientation, rotation and magnification so as to view any selected 
portion of a total video image under selected conditions. Such 
transformation is generally referred to in the art as "affine 
transformation." The affine transformation causes single line shifts in 
the vertical position of pixels which, in an interlaced image, result in a 
temporal reversal of the display of the transformed dynamic image. Such 
reversal is disconcerting to some users of the technology of the cited 
patents. 
in order to minimize these effects, these patents teach using magnification 
on specific fixed increments. In one, wherein the magnification (really 
minification) is 1/2.times., every other line is discarded which results 
in a reduction of input image frequency, called fields, from sixty fields 
per second to thirty fields per second. This removes the time reversal, 
but at the same time leads to a reduction in the apparent update rate of 
moving objects in the input image. 
Also, it is common to use a 2.times. magnification, that is, doubling the 
magnification by doubling the input lines vertically and the number of 
pixels horizontally. This, however, does not provide an improvement in the 
reversal problem, and further provides images of objects that appear to 
have "fingers" or extensions that do not 0have the proper time 
relationship. 
In addition, it is conventional to utilize filters for deinterlacing. 
However, this has not been applied to the capture, transformation, 
magnification, rotation and reconstitution of interlaced images for both 
input and output. 
Accordingly, it is an object of the present invention to provide a method 
for eliminating the temporal shifts that occur during affine 
transformation of interlaced video images. 
Another object of the present invention is to provide apparatus to carry 
out the present method for eliminating the temporal shifts. 
A further object of the present invention is to provide a method for 
eliminating distortion caused by temporal shifts that occur during 
transformation of interlaced video images for the purpose of selecting pan 
and tilt orientation, rotation and magnification of at least a selected 
portion of the interlaced video images. 
It is also an object of the present invention to provide modified apparatus 
for transforming interlaced video images according to pan and tilt 
orientation, rotation and/or magnification whereby temporal and spacial 
shifts that occur during such transformation are eliminated thereby making 
an output image more satisfactory to a viewer of these output images. 
These and other objects of the present invention will become apparent upon 
a consideration of the drawings set forth below, together with a complete 
description thereof. 
DISCLOSURE OF THE INVENTION 
In accordance with one aspect of the present invention, temporal and 
spatial distortion present in digitized interlaced video signals is 
removed by inputting the digitized signals sequentially into three or more 
field buffers in a rotating manner continuously overwriting data in the 
"oldest" buffer, that is, the buffer containing the oldest stored data. 
The stored data in the buffers is simultaneously withdrawn, again in 
sequence, from the two buffers containing the earliest stored data while 
the next or oldest buffer is being overwritten with new input. In 
particular, referring briefly to FIG. 2B, the output is generated by 
selecting successively two vertically adjacent pixels from two temporally 
adjacent fields (one pixel from each field buffer) and averaging their 
respective values, the mathematical average value being the single output 
pixel. For example, the first pixel of the first line (odd lines) will be 
averaged with the first pixel (which is vertically adjacent thereto) from 
the second line (even lines) to form the first output pixel, and so on. 
Upon averaging the pixel data from the two field buffers, successively 
outputting pixels from the lines of the present and immediately preceding 
field, for example from upper left of a display to lower right, the output 
signal produced is substantially absent of temporal and spatial distortion 
when displayed and viewed on a television receiver. 
This method for distortion elimination, and the apparatus for accomplishing 
the method, is particularly applied to systems wherein affine 
transformations are performed to obtain pan and tilt orientation, rotation 
and magnification, from digitized interlaced video signals so as to 
visually observe selected portions of images as obtained from a wide angle 
lens.

BEST MODE FOR CARRYING OUT THE INVENTION 
In order to better explain the matter of temporal shift that occurs in the 
processing of interlaced video signals, reference is made to the four 
drawings of FIGS. 1A through 1E. FIG. 1A, for example, depicts an image of 
a straight line moving in the direction indicated. The video image of this 
line on a screen at a given time would be as indicated in FIG. 1B. Since 
video images are commonly interlaced, at a given time later (e.g., 1/60 
sec later) the video image would appear as in FIG. 1C. However, since the 
two images are interlaced in video systems of interest, they result in a 
pattern as depicted in FIG. 1D. When magnified, the result is as in FIG. 
1E. Since the image continues to be an ongoing depiction on the video 
screen, the image can appear to a viewer as moving in a reverse direction. 
When magnified, this visual distortion caused by temporal shift is very 
evident and therefore undesirable. 
A basic circuit for substantially removing the spatial and temporal 
distortion is shown at 10 in FIG. 2A and a method therefor is 
diagrammatically illustrated in FIG. 2B. Any selected system 12 is 
utilized to capture an image. This can be a video camera, for example. The 
input can be, however, from a video tape machine or from digital video 
information stored on computer storage media. A number of standard formats 
can be used from analog NTSC to to SECAM to High Definition TV (Grand 
Alliance standard or Japanese MUSE), or totally digital formats. 
In the process of the image capture the video signals are interlaced. 
Referring briefly to FIG. 2C, this means that a current field of a 
plurality of horizontal lines is interlaced with the immediately previous 
field, ie. every other line containing pixels of the same field shown as 
X's for the current field or O's for the immediately previous field. The 
output signal therefrom is digitized, as with the element 14. The 
digitized signals are fed to an input bank sequencer 16 whereby they are 
sequentially inputted into three or more identical field buffers 18, 20, 
and 22 in a rotating manner, overwriting the data in the oldest buffer. 
Although technology for a sequencer and field buffers will be known by 
persons skilled in the art, these typically can be created using known 
FPGA technology, for example, Xilinx XC4005 or XC 3164 or equivalent 
devices. 
An output bank sequencer 24 (typically also an FPGA type device of the 
types already mentioned) is connected to the output of the three field 
buffers. This output sequencer withdraws data from any two of the field 
buffers in a random access fashion while the third or oldest buffer is 
being loaded with new data. In particular, as will be described further in 
connection with FIG. 2C, vertically adjacent picture elements are regarded 
and their data values retrieved. This data withdrawn from the two field 
buffers (temporally adjacent fields) is averaged in the vertical averager 
26 (typically an FPGA device such as a Xilinx XC3120). The resultant 
averaged signal is then fed into any desired display system indicated at 
28. This results in a single field delay in the reporting out of data for 
the previously transformed field, but any temporal or spatial distortion 
resulting from, for example, a diagonal line moving across a screen as per 
FIGS. 1A to 1E is eliminated. Due to this triple field buffer system, and 
the averaging of two signals, the output display image is substantially 
devoid of the spatial and temporal shift distortion that would otherwise 
be observed. 
The equations for averaging the picture elements can be derived from the 
characteristic equation for the general vertical filter: 
EQU P.sub.out =P.sub.(x, y+n) C.sub.n 
where 
P.sub.0 =input pixel 
t=Range of pixels used on either side of center pixel 
C.sub.n =an array of coefficients used for each pixel 
P.sub.out =f (P.sub.(x,Y)) where x is fixed and y is variable, that is, in 
one embodiment, 
P.sub.out =1/2 P.sub.(x,y) +1/2 P.sub.(x,y+1) 
and, consequently, the values of vertically adjacent pixels are averaged 
from temporally adjacent fields. 
The averaging of the signals can be explained using the equation: 
EQU P.sub.out(u,v) =P.sub.in(x,y) +P.sub.in(x,y+1) !/2 
where, 
P.sub.out(u,v) =Output pixel value for a pixel on line v at horizontal 
position u; 
P.sub.in(x,y) =Input pixel value f or a pixel on line y at horizontal 
position x; and 
P.sub.in(x,y+1) =input pixel value for a pixel on line y+1 at horizontal 
position x. 
Referring to FIG. 2B, successive vertical pairs of pixels comprise a pixel 
from field 1 and a pixel from field 2, field 1 and field 2, being 
temporally adjacent, which are averaged together to provide an output for 
field 1. Continuing, field 2 pixels are averaged with field 3, fields 2 
and 3 being temporally adjacent in an interlaced image, field 3 with field 
4 and so on. The interlacing of lines as per FIGS. 1A-1E which resulted in 
the distortion shown there is eliminated by this averaging. 
Referring to FIG. 2C, there is shown a diagram for showing the averaging of 
vertically adjacent pixels from temporally adjacent field. There may be a 
plurality of choices for successive vertical pairs of pixels, one from 
each of a current and immediately previous field. Starting, for example, 
with pixel pair 201, this pixel pair represents a directly addressed pixel 
pair comprising one each of data values for a horizontal row of a current 
field and a horizontal row from an immediately previous field. They are 
vertically adjacent; that is, they appear in the same vertical column of 
an interlaced display, if displayed. 
Now the next successive vertical pair may comprise pair 202, it may 
comprise 203, it may even comprise, according to the present invention, a 
virtual pixel pair between pair 201 and 202. The point being that many 
degrees of magnification are possible in the present invention. This 
magnification may be achieved in this line averaging process as 
distinguished from magnification which may occur during affine 
transformation. Greater resolution is achieved by picking successive pairs 
which are closer together; lesser magnification is achieved by skipping 
every one, two or more pixel pairs of vertically adjacent pixels. 
Looking at the example of picking a high magnification pixel pair between 
201 and 202, this may be achieved by averaging values for pixel pairs 201 
and 202 together. Thus, the successive vertical pixel pairs are taken at 
half pixel width increments. 
Vertically, the same is true. Pixel pair 204 achieves a greater resolution 
or degree of magnification than pixel pair 205. Similarly, a weighted 
pixel pair is possible as between pixel pair 201 and 204 to improve 
magnification. 
One of ordinary skill in the art will readily appreciate that aspect ratios 
may be varied to output true or intentionally distorted images, as, for 
example, to output widescreen movies on narrow screen televisions. The 
addressing of different widths and heights of available corrected (affine 
transformed) pixels is achieved, for example, to obtain 4.times.3 aspect 
ratios from 5.times.3 aspect ratios. Alternatively, 5.times.3 aspect 
ratios may be read out as 4.times.3 for example for displaying widescreen 
movies on television raster displays. 
The visual results of the use of three or more buffers, and the sequential 
averaging of two outputs of the field buffers, is illustrated in the 
drawings in FIGS. 3A through 3F. As before, this shows the results of a 
moving diagonal line image of FIG. 3A. FIGS. 3B, 3C and 3D are the video 
images interlaced (fields) at three different times each field being 
1/60th of a second apart as would be the case with conventional National 
Television Standards Committee format. These fields would be sequentially 
input to the three field buffers. FIG. 3E depicts the results of the 
sequential averaging of data in the last two buffers to receive data, 
while the third buffer is receiving data. This, when magnified as 
illustrated in FIG. 3F, provides an image that a person would perceive as 
moving in the same direction as the original line image (FIG. 3A). Thus, 
the distortion has been eliminated. 
The incorporation of the three or more field buffers and signal averaging 
into an omnidirectional viewing system is illustrated at 30 in FIG. 4. 
Certain portions of the circuit will be recognized as being those utilized 
in the circuits of the afore-cited patents for obtaining a corrected view 
of selected portions of an image derived using a wide angle lens. Such a 
system permits electronic pan and tilt orientation, rotation and 
magnification of these selected portions. The algorithm equations for 
achieving the necessary transformations are set forth in those patents as 
well as hereinafter. 
In this embodiment 30 of the present invention, an image is viewed by a 
wide angle lens 32, this being for examples a fish-eye lens. The image 
(which is distorted in a predetermined manner by the lens or imaging 
system) is received by a camera unit 34 with its output signal then being 
fed into an image capture unit 12' which includes a digitizer portion. 
These digitized signals are then the input to the circuit 10 described 
with respect to FIG. 2A. 
As with the omnidirectional viewing application described in the cited 
patents, control of the system comes from a microcomputer and control 
interfaces unit 36. Thus, control can be given through any selected remote 
controller 38 (as by an operator) or a preselected computer controller 40. 
Through input as to the desired pan, tilt, rotation and magnification 
values, and through the algorithm equations cited in the patents, the 
aforementioned output bank sequencer 24, under control by an image address 
unit 42, successively withdraws the stored data from two of the three 
image field buffers 18, 20, and 22. This is indicated by solid lines from 
field buffers 20 and 22. The broken line from field buffer 18 indicates 
that this will be sequentially connected in proper time sequence according 
to control from the sequencer 24. The withdrawn data comprises vertically 
adjacent pixel values from temporally adjacent fields. The data values are 
averaged in the averager 26, fed to a display driver 28 which, as depicted 
herein, has a display driver 44 and display monitor 46. 
The specific orthogonal set of transform algorithms used to correct and 
process any portions of an image are defined by the following two 
equations, as set forth in the cited patents: 
##EQU1## 
where: A=(cos .phi.cos .differential.-sin .phi.sin .differential.cos 
.beta.) 
B=(sin .phi.cos .differential.+cos .phi.sin .differential.cos .beta.) 
C=(cos .phi.sin .differential.+sin .phi.cos .differential.cos .beta.) 
D=(sin .phi.sin .differential.-cos .phi.cos .differential.cos .beta.) 
and where: 
R=radius of the image circle 
.beta.=zenith angle 
.delta.=Azimuth angle in image plane 
.phi.=Object plane rotation angle 
m=Magnification 
u,v=object plane coordinates 
x,y=image plane coordinates 
Also, it will be understood by one of ordinary skill in the art that the 
above equations may be substituted by their simplified polynomial 
approximations in certain applications and the application still obtain 
satisfactory results thereby. For examples in virtual reality computer 
game applications, simplified equations based upon fourth or fifth order 
polynomial approximations may prove economically viable and practical. 
Thus, it will be understood that the system 30 illustrated in FIG. 4 
operates in substantially the same manner as the systems disclosed in the 
above-cited patents commonly owned by the Assignee. The difference is in 
the use of the three or more buffers to receive the image data in rotary 
sequence, with this image data being withdrawn simultaneously from two 
buffers for averaging while the third or oldest buffer is being loaded or 
overwritten with new data. Withdrawal is controlled to obtain the data 
used for the necessary transform to achieve corrected images. This 
withdrawn information (data) is averaged prior to display to overcome the 
temporal and spacial distortion that leads to an apparent reversal of 
motion in displayed images. 
One implementation of the above-described method and apparatus is in the 
form of an application specific integrated circuit, functionally shown in 
schematic form in FIG. 5. Referring to FIG. 5 there is shown a functional 
block diagram of a distortion correction engine according to the present 
invention, hereinafter referred to as a video dewarping engine (VDE). As 
shown, the VDE is divided into three main sections, a video input section 
510, a video processing section 520 and a random access memory multiplexer 
section, RAM Mux 530. 
Referring first to the video input section 510 there is shown video data 
from an external imaging system (off chip), camera, recorder or the like 
input to a data register driven by clock drivers, clocked by a pixel clock 
and a clock reference from a clock and control circuit (not shown). There 
may be multiple such inputs in accordance with the present invention The 
input video data is stored in buffer RAM banks A, B or C for processing as 
described above. Two field memories are utilized for data storage for 
averaging and the third bank for overwriting with new field data. A 
non-linear scan of pixel data from an array of CMOS active pixel sensors 
or, alternatively CID or CCD arrays (not shown in FIG. 5) accessed through 
RAM Mux 530 is described in copending, concurrently filed application Ser. 
No., incorporated herein by reference. The ASIC depicted in FIG. 5 accepts 
video data input by whatever means, corrects any predetermined distortion 
introduced by the imaging system, corrects any temporal or spatial 
distortion by line averaging as described in the present application, and 
outputs corrected data in a predetermined format. 
In the video input section 510, the clock drivers provide clock drive for 
address and timing generator 515 for RAM Mux 530 and directly to RAM Mux 
530. Address and timing generator 515 also generates timing and addresses 
for dewarping logic 522. For example, 9-bit resolution video data is input 
to memory from data registers thereafter via RAM Mux 530. Moreover, the 
address and timing generator 515 is controlled by control inputs, for 
example, for selecting an image portion for output as per remote control 
38 or computer control 40 (of FIG. 4) here shown as camera sync, camera 
control and host control leads or data buses. As taught in U.S. Pat. No. 
5,185,767, the control input should, at least, provide a viewing angle 
having zenith and azimuth angle components from a central line-of-sight. 
Other control input data includes rotation, a distortion inherently 
correctable in accordance with that described system. As described herein, 
magnification can be provided in accordance with FIG. 2B during the 
addressing and scanning process. Thus, without any need for mechanical 
movement, a camera is panned, tilted rotated, zoomed or the like in 
accordance with the present invention. 
Referring now to the video output or processing section 520, the selected 
video data is accessed from RAM banks A,B, or C via RAM Mux 530 and 
operated upon via de-warping logic 522 as required The dewarping logic 
522, in turn, is controlled via horizontal and vertical counters and 
timers and parameter selection and general control sections respectively. 
The manipulated data is output to vertical line averaging circuitry 525 
and forwarded to post-processing circuits. Vertical line averaging 525 is 
performed as described above. Thereafter, the processed video data is 
output to formatter circuitry 537. There the data may be selectively, 
overlaid for example, for captioning or teletext messaging or the like and 
output in a preselected desired format. 
The video processing section 520 receives control input as to which of a 
plurality of formats in which the output may be provided, for example, 
from NTSC, , SECAM, HDTV, etc. Moreover, video processing section 520 
receives pixel clock and a clock reference in the same manner from a clock 
and control circuit on board the ASIC (not shown). 
From the foregoing, it will be understood by persons skilled in the art 
that a method and apparatus have been described for eliminating (removing) 
temporal and spatial effects that occur in transforming interlaced video 
images. This eliminates the bothersome apparent reverse movement of 
images, particularly when magnified. 
Although certain commercial components are indicated for providing a 
complete description of the present invention, these are solely for 
illustration and not for limitation. Rather, the invention is to be 
limited only by the appended claims.