# Patent

## Title
Method and system enabling users to interact, via mutually coupled

## Abstract

Method for the interactive real time processing and displaying of camera shots or computer generated video image sequences that include moving objects of variable speed for generating improved computer games. A bank of original sequences of individually selectable images is generated. Each sequence is shot by a camera and contains moving objects and converted to a digital form. A range of possible modified object speeds are selected for each computer game. A set of transformations, from each frame of the original sequence, to its next frame, is calculated in advance for all frames, and stored in a memory, together with the original digital sequence, as a data-base file. Any desired manipulation of the image of a frame on the stored transformation is calculated in real-time, as a function of the desired speed provided by a player and a new virtual frame, which is an intermediate frame of frames from the original sequence is generated in real-time, according to the calculation results. The new generated frame is displayed means, and any other required intermediate frame is generated and displayed, in real-time, optionally together with selected frames from the original sequence.

## Background
The present invention relates to the field of image processing. More particularly, the invention relates to a method for processing camera shot films and for generating therefrom improved computer games which include variable speed, selected by the player.

Computer games are widespread nowadays. They typically employ animation or Computer Generated Images (CGI) techniques, in which images are generated according to algorithms that are relatively simple to formulate, with respect to their mathematical aspects. This relative simplicity, enables CGI based computer games to have high level of interaction. On the other hand, CGI graphic quality is substantially degraded concerning the experience felt by the player, comparing to video graphic quality.

Although video stream graphic techniques have superior quality, they lack interaction. Their graphic representation must track the video camera path, each time the game is played, turning the game into a non-attractive one. In addition, the mathematical representation of a video stream is very complicated and thus, practical almost impossible.

The technology employed in the art for video image processing suffers from several drawbacks, the most important of which being: 1) that there is only a limited feeling of reality, since scenes are pre-determined, constrained to the path, plot and events that were shot and recorded by the video camera; 2) data rates required for display of video streams are very high (in a typical .beta. video stream, 25 frames are displayed at each second, each frame is represented by 0.8 Mbyte, resulting in data rate of 20 Mbyte/Sec); 3) those scenes that appear near an interactive event give the feeling of discontinuity; 4) the range of intermediate speed values is limited. Thus, there are speed values that can not be reached using prior art methods; and 5) more importantly, interactive processing of video streams can not be carried out by conventional Personal Computers (PCs), to give satisfactory results.

Interaction of games may be improved substantially by manipulating the speed of video streams related to the game. One known method is based on changes in the frame display rate of the stream, by dropping frames from the original sequence (usually used for acceleration) or by inserting new frames which may be duplicates of some original frames. This method is widely used for converting video films from PAL (European standard for color TV) to NTSC (American standard for color TV) format, and vice versa. However, since the human eye is sensitive to irregular motion, poor results were achieved using this method concerning the feeling of continuity. In addition, speed values are pre-determined and can not be changed in real time.

U.S. Pat. No. 4,668,986 to Furukawa discloses a method for motion-adaptive interpolation of video signals. A number of motion vectors are computed for each moving object, generating a new representative motion vector.

U.S. Pat. No. 5,557,684 to Wang et. al describes a system for compressing image data for transmission by encoding the data into multiple layers. The system stores images as a series of layers determining the boundaries of regions of coherent motion over the frame, together with associated motion parameters. These motion parameters are coefficients of motion equations that describe the transformations between successive frames by formulating a motion model for each region within a frame. Each image is segmented into regions of coherent motion and defines associated layers of intensity, motion parameters, and depth.

U.S. Pat. No. 5,565,920 to Jungwoo et al. describes a method for video data compression using adaptive motion interpolation. Temporal segmentation is used to dynamically adapt motion interpolation structures for video compression.

Notwithstanding the very high commercial importance of sophisticated computer games, and the many efforts put into the manufacturing of games in the computer industry, the art has so far not successfully addressed the severe problem of producing interactive computer video games, based on real life images. It is an object of the invention to provide a method for manufacturing interactive computer games of improved quality, using real life shots.

It is an object of the invention to provide such interactive games in which the speed of displayed video streams is manipulated interactively to run slower and faster.

It is an object of the present invention to provide a method for real time computation and generation of virtual frames displayed as image sequences, which overcomes the drawbacks of the prior art.

It is another purpose of the invention to provide computer games utilizing pre-shot image sequences, which permit to effect smooth speed changes without the need for large databases of pre-stored images.

It is another object of the present invention to provide a method for carrying out and for storing most of the required intensive processing, in advance, while the display of any desired speed is carried out, in real time, using a fast, simple computation.

Other purposes and advantages of the invention will appear as the description proceeds.

The invention is directed to a method for the interactive real time processing and displaying of camera shots or computer generated video image sequences that include moving objects of variable speed, particularly for generating improved computer games, comprising the steps of: individually selectable images, said bank of images being shot by a movie or the like camera, and containing at least one object moving at least at one speed; for objects moving in said sequence; frame of said original sequence of step b) above to its next frame; transformations of step (c) above as a data-base file in suitable memory means; frame, or of the part thereof, on the stored transformation of step (e) above, as a function of the desired speed provided by a player; frame of at least two frames from the original sequence of step (b)above, according to the results of the calculations of step (f) above; frame, optionally together with selected frames from the original sequence.

By "object" it is meant to indicate a group of pixels which are part of the image and differs from other parts by a defined classification (e.g., color motion or arbitrary criteria). Group of objects may also be defined as an object. Depth layers with significant differences of distance from camera may be defined as objects (e.g., far background).

By "moving object" it is meant to indicate an object which appears differently in two (or more) adjacent frames, like as a result of camera movements, or even without changing its relative position, e.g., an object that only changes its color.

By "speed" it is meant to indicate the rate of changes of an object characteristics from one frame to another frame, e.g., changes in its relative position with respect to other objects, shape, colors, camera movements etc. Thus, speed may be varied even without any physical displacement of the object itself.

The original sequence of images can be either filmed with a camera, which may be a movie camera, a video camera, or any other suitable type of camera, or can be computer generated. Furthermore, the original sequence of images can be a combination of computer generated and film camera shot frames, transformed to digital form.

As will be apparent to the skilled person from the description to follow, according to a preferred embodiment of the invention the original sequence is used as the reference sequence.

The object speed changes and their resolution can be derived from a variety of events, for instance, from a previous occurrence during the game. According to a preferred embodiment of the invention, however, values for such changes, as well as their rates are provided interactively by the player and input thereby. This can be done, i.e., through the movement of a joystick, or by selecting a suitable button, or by directly inputting a value.

As will be apparent to the skilled person, the displaying of the images, their creation and interpolation, and the storage of the information used to generate them, all require computational power and memory means. These can be provided by any suitable computing means, such as commercially available computers, e.g., a Personal Computer (PC), or may be carried out by a specially designed computer, as is often done with arcade games.

As stated, each sequence may contain one or more objects that may move independently one of the other. According to a preferred embodiment of the invention, the speed of each one of a plurality of independently moving objects is controlled independently.

According to a preferred embodiment of the invention, more than one sequence are speed processed and displayed simultaneously. According to another preferred embodiments of the invention, different sequences originate from different scenes and/or are of different lengths.

Any change in speed can be effected, according to the invention. Thus, the speed can be reduced or accelerated, or the movement can be stopped, or the direction of movement can be inverted. Furthermore, movement can be either horizontal, or vertical, or composite.

According to a preferred embodiment of the invention, additional sequences are computer generated virtual object sequences. Several types of transformations can be used. Illustrative and non-limitative examples of such transformations include shift transformations, rigid transformations, projective transformations, object oriented pixel dependent transformations, area oriented pixel dependent transformations, and transformations carried out as a result of camera movements.

The above and other characteristics and advantages of the invention will be better understood through the following illustrative and non-imitative detailed description of preferred embodiments thereof, with reference to the appended drawings, wherein:

FIGS. 1A to 1D schematically illustrate the relative locations in a scene with a moving object while being shot by a camera;

FIGS. 2A to 2B schematically illustrate a an original sequence and a processed sequence containing low speed moving object;

FIG. 3 illustrates a transformation process simulating movement of the camera from right to left; and

FIGS. 4A to 4B show two different intermediate frames generated from two adjacent real life shot frames.

In order to create an interactive continuous realistic computer game, it is needed to provide means for controlling the speed of moving objects. A scene with a moving object can be displayed to the player by a sequence of images. Each image shows a different location of the moving object with respect to the background of the scene. The said images, when displayed consecutively, give the observer the feeling of movement at a given speed. Changing speed is being achieved by changing several parameters, as will be explained below.

For a better understanding of speed effects seen by a player, there is a need first to define some parameters which directly affect the object speed while displaying a scene. FIG. 1A illustrates a scene which takes place along a road segment of length.times.[m]. A moving object which in this case is a car 1, is being shot by a camera 4, which operates with a shooting rate of N.sub.0 [frames/Sec]. For simplicity, it is assumed that camera 4 is located at a fixed position during all the shot. Moreover, it is assumed that car 1 moves from left to right at a fixed velocity V.sub.0. The car enters the scene at point 1, passes in front of tree 2 and then tree 3, and disappears at point 2. In this case the total scene time will be T.sub.0 [Sec] where:

Since the shooting rate is N.sub.0, the total number of frames for the scene will be S.sub.0, where S.sub.0 =N.sub.0 *T.sub.0. This means that this scene can be displayed by a sequence length of S.sub.0 frames (or images).

FIGS. 1B, 1C and 1D show 3 frames which are a part of the sequence S.sub.0. It can be seen that in FIG. 1B the car 1 has almost reached tree 2, in FIG. 1C it is between tree 2 and tree 3 and in FIG. 1D it is right in front of tree 3. If those three frames are displayed consequently, the observer will see the car moving from left to right. If all S.sub.0 frames will be displayed to the observer in exactly the same rate N.sub.0, then the observer will see the car moving at exactly the same speed V.sub.0 at which the car moved when the original sequence was shot.

On the other hand, if the observer wishes to see exactly the same scene with car 1 moving at a speed other than V.sub.0, then it is clear that if he wishes to accelerate, then the scene should be displayed faster, viz. during a time shorter than T.sub.0. If he wishes to reduce the speed, then the display time should be larger than N.sub.0.

Another effect to be taken into account when changing the speed of an object, is the resolution of the displayed scene. Looking at FIG. 2A which illustrates this problem, an original sequence of frames is seen, taken by a camera with rate N.sub.0 =1 [frame/Sec] during a scene with a car moving at speed V.sub.0.=1 [m/Sec] and traveling a distance of x=8 [m]. The total scene time is T.sub.0 =8 [Sec], and the total number of frames is S.sub.0 =8, indicated as A1 to A8 in the figure. As it can be seen, each frame, starting from left to right, contains different information about the relative location of the car in the scene showing its movement from left to right in increments.

According to what was discussed above, if the original shot included 8 frames, then if they are displayed during 8 seconds, the observer will see the car moving at a speed of 1 [m/Sec] from left to right.

Now, if the observer wishes to watch the same scene with the car moving slower e.g., to reduce the speed to 0.27*V.sub.0, then the scene should be displayed during 29.6 seconds (=8/0.27). In this case, if the same display rate of 1 [frame/Sec] is kept, then in order to keep the same quality of the original scene 30 frames must be displayed, otherwise unwanted "stops" in the car movement will appear. Thus, in this case it is needed to generate a new set of 30 (=the first integer number that>29.6) intermediate frames. Each frame from the said new set displays a non-existing (in the original sequence) relative position of the moving object (a car in this example). Looking at the original sequence frames of FIG. 2A from left to right, each frame represents a shift of distance .DELTA. of the car position, relative to its previous frame.

Looking at FIG. 2B, it can be seen that since the car speed was cut to 0.27*V.sub.0, a new desired sequence B1 to B30 was generated. Indicating each frame by its relative displacement of the moving object (a car in this case), each frame can be generated according to the following process (in terms of the distance shift .DELTA.:

It is clear that all the frames B1 . . . B30 are newly generated and none of them is identical to a frame from the original sequence. Furthermore, if frames from the original sequence are duplicated and displayed in order to have the impression of reduced speed, the car may be seen moving with "jump" rather than performing a continuous and smooth ride, resulting in a bad quality film.

Of course, varying the car speed V.sub.0 by other factors will require different combinations of frames and further processing than was shown in FIG. 2 above. FIG. 2 showed only part of the effects that can be achieved by image processing.

The invention uses one original sequence taken by a camera or generated by a computer, displaying a moving object moving in a given speed or displaying relative shift in objects position according to horizontal and/or vertical movements of the camera.

Since one goal of the invention is to minimize the amount of real-time processing needed to obtain satisfactory results, when complex transformations are required, the invention is based on a method of using a pre-programmed data-base together with said original sequence. One important advantage of using one original sequence and a data base is the ability to generate and display any desired frame in real time. Using the method of the invention further eliminates the need for a very large and memory-consuming bank of images.

An apparatus, for generating a speed controlled, smooth, realistic sequence in real time according to one embodiment of the invention performs the following steps: original sequence comprises N frames, and i (i=1,2, . . . , N) represents the index of an original frame, then each transformation T.sub.i.fwdarw..sub.i+1 is being calculated; digitized original sequence in a data-base file. This original sequence will be used later to generate, together with calculated transformation from the data-base, any frame or sequence of frames that will be able to display an object moving in speed equal to or different from its speed in the original sequence; representing a required frame that does not exist in the data-base file. By using the term "manipulation" it is meant to describe a new transformation which is a relatively simple modification of one of the existing transformations stored in the data-base. If x represents a desired non-integer index of an intermediate frame F.sub.x, and n represents the closest integer value of x, then for x>n the desired manipulation is carried out as follows:

x<n the inverse manipulation is carried out:

By using the term "closest integer value" of x it is meant that

By using the term "transformation", it is meant to describe two kinds of transformations. The first one is called "Global Transformation", T(x,y) when the same transforming process is being applied on a whole frame.

However, in some cases a transformation is applied only on one or more objects of the frame. Thus, if there are m objects to be transformed in a frame, the second transformation is a actually a set of transformations called "Object Dependent Transformation" T=T.sub.j (x,y) where j=0,1, . . . , m. Moreover, several kinds of transformations may be operated: simple shifting, projective transformation, different transformation for different areas, etc.

In some cases, better and smooth results will be achieved using complex transformations during the game display. In other cases, the same results may be achieved by relatively simple transformations.

Transformations are related to their relative quality. Since a digital image (frame) is constructed from a matrix of pixels, a transformation Tn.sub.n.fwdarw.from one frame to the next frame not necessarily requires implementation on each pixel of the frame. In some cases, implementation of the transformation is carried out partially, according to the required quality. A transformation T.sub.n.fwdarw..sub.n+1 may be implemented on frame n so as to obtain frame n+1 to look substantially the same as the original frame n+1 to the eye of a moderate observer. This may simplify the required processing and still achieve satisfactory results.

According to another preferred embodiment of the present invention an apparatus provides multiple video sequences that are speed controlled independently, forming a scene. Each video sequence may be of different length, and may include only part of the displayed scene. The apparatus performs the following steps: each frame to its next, in the same way as described in step f) above; of said multiple sequences, together with the digitized original multiple sequences in a data-base file; between different sequences. This range may be frame dependent and/or scene dependent. For instance, if two different sequences include connected moving objects or connected static objects, both sequences should be displayed in the same speed. In another case, one sequence may include a far background view, wile another sequence includes a rigid moving object, a car for example. It is possible to run the car and the far background view in different speeds. On the other hand, instead of the car the other sequence may include a flexible moving object, a walking person for example. In this case, the two different sequences may be displayed in only slightly different speeds; sequences, any manipulation of its original frames, representing a required frame that does not exist in the data-base file in the same process described in step f) above; in a pre-determined order, forming a complete scene;

According to still another preferred embodiment of the present invention an apparatus provides a video sequence several objects are speed controlled independently. The apparatus performs the following steps: containing one object, comprising the following steps:

An object stream contains information only about one object. The remaining part of the original sequence which does not contain any object is defined and handled also as an object stream.

If multiple manipulations are required to display one frame, they should be carried out starting from the most distant object. In a case when pixels of two objects should appear in the same location on the frame, the closest object will overlie the far one. By using the term "pixel" it is meant to represent the smallest unit of a video display which may be coded to an electrical signal for transmission.

In a case when a pixel or an array of pixels has no defined source in the transformation, a "hole" may appear in the frame. For example, in case when a global transformation from one frame to its next is a simple shift by 10 pixels to the left, and it is required to generate the 0.4 portion of the frame, a shift of 4 pixels to the left should be accomplished. Thus, a strip of 4 columns on the right side will remain with no source information.

Another case, when a relative movement between two objects in a frame may also result as a hole in a desired intermediate frame, is illustrated in the following example:

A frame having two objects in two different depth layers, for instance, a house and a chain of mountains in the horizon. A simulation of camera movement to the left requires translation of the house of 15 pixels to the right, with no translation of the far background (mountains in the horizon). Generating 0.7 portion of the frame requires a shift of 4.5 [=(1-0.7)*15] pixels to the left, leaving a strip of 4.5 pixels with no source information.

To overcome these problems it is required to reach the missing information from n which is defined now as the 2.sup.nd closest integer value of x. this means looking after the missing source information at the next frame By using the term "2.sup.nd closest integer value" of x it is meant that 0.5<.vertline.n-x.vertline..ltoreq.1. Similar to step e) above, if x represents a desired non-integer index of an intermediate frame F.sub.x, and n represents the 2.sup.nd closest integer value of x, then for x>n the desired manipulation is carried out as follows:

For x<n the inverse manipulation is carried out:

In some cases the missing source information exists at the m.sup.th frame. In this case .vertline.m-x.vertline.>1 and n is defined as the "integer value" of x (e.g., the integer value of 2.99 is 2). Different from step e) above, if x represents a desired non-integer index of an intermediate frame F.sub.x, and n represents the integer value of x, then for x>m the desired manipulation is carried out as follows: ##EQU1##

For x<m and n=(integer value of x)+1, the inverse manipulation is carried out: ##EQU2##

As an illustrative example, if x=1.1 and the source information of an object exists in frame 25, the frame transformation from 1 to 25 should be: 1.fwdarw.2.fwdarw.3.fwdarw.. . . .fwdarw.25 since there is no direct transformation 1.fwdarw.25.

FIG. 3 illustrates an apparatus for generating any desired intermediate frame from an original sequence of five frames describing a camera movement from right to the left. Similar transformations and processing is being used for speed change.

Four global transformations are needed to move from frame 1 to frame 5: T.sub.1.fwdarw. .sub.2 {character pullout} shift by 5 pixels to the right T.sub.2.fwdarw. .sub.3 {character pullout} shift by 8 pixels to the right T.sub.3.fwdarw. .sub.4 {character pullout} shift by 6 pixels to the right T.sub.4.fwdarw. .sub.5 {character pullout} shift by 5 pixels to the right

If the original sequence was shot at a speed of V.sub.0 and a new speed of 0.8*V.sub.0 is desired, 6 frames should be generated from the sequence F.sub.1 . . . F.sub.5 as follows: Frame No.     Source        Manipulation F.sub.1       F.sub.1       none F.sub.1.8     F.sub.2       (2-1.8)*5 = 1 pixel left F.sub.2.6     F.sub.3       (3-2.6)*8 = 3.2 pixels left F.sub.3.4     F.sub.3       (3.4-3)*6 = 2.4 pixels right F.sub.4.2     F.sub.4       (4.2-4)*5 = 1 pixel right F.sub.1       F.sub.1       none

If the original sequence was shot at a speed of V.sub.0 and a new speed of 1.3*V.sub.0 is desired, 4 frames should be generated from the sequence F.sub.1 . . . F.sub.5 as follows: Frame No.     Source        Manipulation F.sub.1       F.sub.1       none F.sub.2.3     F.sub.2       (2.3-2)*8 = 2.4 pixels right F.sub.3.6     F.sub.4       (4-3.6)*6 = 2.4 pixels left F.sub.4.9     F.sub.5       (5-4.9)*5 = 2.4 pixels left

FIG. 4A and FIG. 4B show two intermediate frames, 1.33 and 1.66, respectively, generated from two adjacent original real life frames. Looking first at FIG. 5A, two real life shot frames, (loaded shelves in a department store) frame 1 and frame 2 are presented, together with an intermediate frame 1.33. Frame 2 represents a movement of the camera from right to left relative to frame 1. If X.sub.i and Y.sub.i represents the horizontal and vertical displacements (relative to the origin) of a pixel in frame i, respectively, then the transformation T.sub.1.fwdarw..sub.2 from frame 1 to frame 2 is given by:

X.sub.1 =X.sub.2 *1.02264+Y.sub.2 *0.0058839-10.2872

or alternatively:

Manipulating the transformation T.sub.1.fwdarw..sub.2, a desired intermediate frame 1.33 is obtained and given by the transformation:

FIG. 4B shows the same real life shot frame 1 and frame 2, together with another desired intermediate frame 1.66.

Similarly, manipulating the transformation T.sub.1.fwdarw..sub.2, intermediate frame 1.66 is obtained and given by the transformation:

Of course, the above examples and description has been provided only for the purpose of illustrations, and are not intended to limit the invention in any way. As will be appreciated by the skilled person, the invention can be carried out in a great variety of ways, employing more than one technique from those described above, generating the original sequence by a computer or by any other photographing means, applying the same or similar method of the invention to generate on-line and real time scenes which may include more than one moving object moving in any direction, all without exceeding the scope of the invention.

## Claims

1. A method for the interactive real time processing and displaying of camera shots or computer generated video image sequences that include moving objects of variable speed, particularly for generating improved computer games, comprising the steps of: individually selectable images, said bank of images being shot by a movie or the like camera, and containing at least one object moving at least at one speed; for objects moving in said sequence; frame of said original sequence of step (b) above to its next frame; transformations of step (c) above as a data-base file in suitable memory means; frame, or of the part thereof, on the stored transformation of step (e) above, as a function of the desired speed provided by a player; frame of at least two frames from the original sequence of step (b) above, according to the results of the calculations of step (f) above; frame, optionally together with selected frames from the original sequence.

2. A method according to claim 1, wherein the original sequence of images is computer generated.

3. A method according to claim 1, wherein the original sequence of images is a combination of computer generated and film camera shot frames transformed to digital form.

4. A method according to claim 3, wherein the movie camera is a video camera.

5. A method according to claim 1, wherein the object speed changes and the rate of change is provided interactively by the player and input thereby.

6. A method according to claim 1, wherein the image processing and the calculations are carried out on a Personal Computer (PC).

7. A method according to claim 1, wherein the speed of each one of a plurality of independently moving objects is controlled independently.

8. A method according to claim 1, wherein more than one sequence are speed processed and displayed simultaneously.

9. A method according to claim 8, wherein different sequences originate from different scenes and/or are of different lengths.

10. A method according to claim 1, wherein the speed is reduced or accelerated, or movement is stopped, or the direction of movement is inverted.

11. A method according to claim 1 wherein additional sequences are computer generated virtual object sequences.

12. A method according to claim 1, wherein the transformations are shift transformations.

13. A method according to claim 1, wherein the transformations are rigid transformations.

14. A method according to claim 1, wherein the transformations are projective transformations.

15. A method according to claim 1, wherein the transformations are object oriented pixel dependent transformations.

16. A method according to claim 1, wherein the transformations are area oriented pixel dependent transformations.

17. A method according to claim 12, wherein the transformations are carried out as a result of camera movements.