Real-time key frame effects using tracking information

[0002] Video commonly is processed to create special effects by tracking an object in the video. For example, the video may be processed using the information about the tracked object to remove movement of the object (an effect called stabilization). An object also may be added to the video that has a position or movement related to the tracked object (an effect called compositing). An object that has a relationship with the tracked object also may be removed from the video (such as an effect called wire removal).

[0003] Video may be stabilized before compositing, wire removal or other effects are performed where the movement of objects in the video may impact the quality of the effect. The movement of the objects may be reintroduced into the video after the effect is performed by inverting the stabilization effect.

[0004] Creating an effect using tracking and stabilization involves multiple operations to be performed on each image to produce the effect. These operations generally prevent such effects from being rendered in real time. The inability to view the effect in real time increases the cost incurred for each change made to the effect, which in turn limits the creativity of the editor.

[0005] Real time effects are provided by using tracking information to define values for parameters of an effect. The tracking information also may be combined with parameters for various effects that operate on the position, rotation, scale, skew and perspective of objects in an image. The values defined for the parameters of an effect may be represented in a transformation matrix used in a real time digital video effects processor.

[0006] Accordingly, in one aspect, effects may be generated in real time by key frames on video data comprising a sequence of images using tracking information. For each image that is not a key frame, one or more values for parameters are interpolated for the effect using the one or more values that are specified at the key frames. The tracking information is combined with the one or more interpolated values and the effect is performed on each image in the sequence of images in real time using the combined tracking information and one or more interpolated values.

[0007] In the drawings,

[0008] FIG. 1 is a block diagram of an example real time tracking and effects generator;

[0009] FIG. 2 illustrates tracking a moving image for position;

[0010] FIG. 3 illustrates inserting a foreground object into a moving image using a position effect;

[0011] FIG. 4 illustrates tracking a moving image for scale;

[0012] FIG. 5 illustrates inserting a foreground object into a moving image using a scale effect;

[0013] FIG. 6 illustrates tracking a moving image for rotation;

[0014] FIG. 7 illustrates inserting a foreground object into a moving image using a rotation effect; and

[0015] FIG. 8 is an architecture diagram of the tracking level functionality.

[0016] Tracking involves analysis of movement of an object from one image to another in a sequence of images. An object's orientation in an image may be defined by one or more points. The transformation of the object over a sequence of images is recorded as a sequence of these one or more points. This sequence of one or more points is called tracking data or tracking information. Tracking data can be used for a variety of effects including object following, replacement of an object, stabilization, or other operations on objects in an image.

[0017] Effects defined using tracking data may be performed in real-time on a sequence of images. Real-time processing of an effect involves calculating values for parameters of the effect for each image and applying the effect to each image in time to display each image at its desired output rate without precomputing all of the images before initiating display of the sequence. One mechanism for real-time addition of digital video effects can be found in U.S. Pat. No. 5,654,737 (Der et al), in which real-time digital video effects are created using a media pipeline that provides two channels of input sequences of digital still images to a digital video effect processor. Because this system operates using a media pipeline which provides sequences of digital still images, rather than a video signal, display and generation of effects can be stopped at any time. Thus, an editor can stop and view an arbitrary pixel in the created effect. Also, an editor can step forward or backward, frame by frame, through the effect, by virtue of the pipelined nature of the system.

[0018] FIG. 1 is a dataflow diagram illustrating how tracking data may be used to perform effects in real-time. Video data 102 and initial tracking point(s) 104, which may be specified by, for example, an editor, are analyzed by a tracking engine 106 to yield the tracking data 108. The tracking system 106 may be implemented using any conventional or commercially available tracking engine.

[0019] An editor also may define an effect 112 to be performed on the video image. An effects interface 110 enables an editor to select an effect from numerous available effects and to specify values for parameters of the selected effect. The effects that may be defined using effects interface 110 include any operations that perform a spatial transformation on an object or an image or both. Examples of such effects include but are not limited to compositing, paint effects, color manipulations, picture-in-picture or key framed effects, pan and scan operations and the like.

[0020] Values for parameters of the effect 112 are combined with the tracking data 108 and video data 102 by a real-time effects generator 114. The real-time effects generator 114 then generates and displays the video data 116 with the effects in real-time. For example, tracking data may be used to define a picture-in-picture/3D warp effect. The 3D warp effect allows the use of multiple tracking points to cause a superimposed object or picture to appear as if it were part of the original scene.

[0021] Key frames are used to define values for parameters for operations on a sequence of images. Key frames specify values for initial, optionally selected intermediate and final images, leaving values for other images to be defined by interpolation. For example, the user selects a first frame and sets an initial value for each of one or more parameters. The user then selects a second frame and sets terminal values for the one or more parameters. Values for other frames are obtained by interpolating between the first frame and each subsequent key frame. This process of key framing may be used for a variety of desired effects. For example, a user may desire an object to change color from green to blue, or to increase in size from a first frame to a second frame. The user also may use key framing to composite a foreground image onto a background image. The user selects the starting point of the foreground image in the first frame and the ending point of the foreground image in the second frame. The intermediate frames are then interpolated so that the foreground image appears at the appropriate location on the background during the intermediate frames.

[0022] Tracking data may be combined with key frame data to perform, optionally in real time, effects in which an object follows a desired motion. A user sets an initial key frame to set the starting position of an object and then selects tracking data to move the object according to a tracked path of movement. This combination of key framing and tracking is done without having to match points of the foreground image to the background. The use of key frames and real-time tracking effects allows the tracking data points to be at any location on the moving image, not just at the corners of the object to be inserted. The key frame data defines an initial relationship between the foreground image and the background image, then the tracking data or transformation matrix is used to determine how the foreground image moves in relation to the background image in subsequent frames.

[0023] The number of tracking points used to insert a foreground object into a moving background depends on the complexity of the movement. If the movement only occurs in the horizontal and vertical plane without any rotation or scale a single tracking point may be used to follow the position of the background.

[0024] FIG. 2 shows a sequence of images of a truck 200 driving in the horizontal plane. Only one point 202 is used to track the truck's position. At the first image in the sequence, shown in FIG. 2A, the horizontal and vertical coordinates of the tracking point are stored as the reference point (RefPoint.h, RefPoint.v). For each subsequent field, shown in FIGS. 4B-4C, the coordinates of the tracking point are stored (pt.h, pt.v). This tracking data is obtained by the tracking engine. The tracking data is then used by the digital effects generator according to the effect desired.

[0025] To superimpose a foreground object (shown in FIG. 3A as a sign) onto the background the initial, optional intermediate and end values for the position of the foreground with respect to the background are first set at the key frames, as shown in FIG. 3B for a first key frame. Then the tracking data is applied to the foreground object so that the coordinates (x, y) of the foreground image are altered at each field according to the equation:

[0026] X=pt.h−RefPoint.h

[0027] Y=pt.v−RefPoint.v

[0028] This operation will result in the foreground object moving with the truck, as shown in FIGS. 3C-3D. If the desired effect was a stabilization of the truck rather than the compositing of an object, every image in the sequence would be altered according to the inverse of the truck's movement:

[0029] X=RefPoint.h−pt.h

[0030] Y=RefPoint.v−pt.v

[0031] To insert a foreground object into a moving background where scale is altered, as shown in FIG. 4 with the truck 400 driving away, two tracking points are used. The two points may be chosen anywhere in the moving background, but for better results should be far enough apart so they can adequately represent the change in scale. The initial coordinates of these points 402, 404 are stored as reference points (RefPoint1.h, RefPoint1.v, RefPoint2.h, RefPoint2.v). For each subsequent field, shown in FIGS. 6B-6C, the coordinates of these tracking points are stored (pt1.h, pt1.v, pt2.h, pt2.v). RefPoint1 and pt1 define a vector for how the first tracking point has changed from the initial field to the current field, and similarly for the second point with RefPoint2 and pt2. The motion of the first point is removed from second point to isolate the change in scale:

[0032] pt2.h=pt2.h+RefPoint1.h−pt1.h

[0033] pt2.v=pt2.v+RefPoint1.v−pt1.v

[0034] pt1.h=RefPoint1.h

[0035] pt1.v=RefPoint1.v.

[0036] To further isolate the change in scale between the tracking points any rotation effects between the points must be removed. The rotation is removed by adjusting the tracking data to compensate for any rotation, using the following equations:

[0037] angle1=arc tan gent((RefPoint2.v−RefPoint1.v)/(Refpoint2.h−RefPoint1.h))

[0038] angle2=arc tan gent((pt2.v−pt1.v)/(pt2.h−pt1.h))

[0039] if (angle1 is not equal to angle2)

[0040] r=square root((pt2.h−pt1.h)*(pt2.h−pt1.h)+(pt2.v−pt1.v)*(pt2.v−pt1.v))

[0041] pt2.h=pt1.h+r*cos(angle1)

[0042] pt2v.=pt1.v+r*sin(angle1).

[0043] To scale an X coordinate, the following are used to compute the scale factor:

[0044] delta1=RefPoint2.h−RefPoint1.h

[0045] delta2=pt2.h−pt1.h.

[0046] To scale a Y coordinate, the following are used to compute the scale factor:

[0047] delta1=RefPoint2.v−RefPoint1.v

[0048] delta2=pt2.v−pt1.v.

[0049] To superimpose a foreground object into a background with scale the initial, optional intermediate and end values for the position of the foreground with respect to the background are first set at the key frames, as shown in FIG. 5B for a first key frame. Given the key framed or interpolated values for the object, the scale factors are applied to the object then the object is inserted into the image. The scale factors used to scale an object are calculated with the following equation:

[0050] scale factor=delta2/delta1.

[0051] This operation results in the foreground object moving with the truck, as shown in FIGS. 5C-5D. If the purpose of the tracking was not to superimpose a foreground object, but to scale the background and keep the moving object the same size, the individual images of the sequence would be scaled according to the scale factor:

[0052] scale factor=delta1/delta2.

[0053] To insert a foreground object into a moving background where the background is rotated, as shown in FIG. 6, two tracking points may be used. The two points may be chosen anywhere in the moving background, but for best results should be far enough apart so they can adequately represent the rotation. The initial coordinates of these points 602, 604 are stored as reference points (RefPoint1.h, RefPoint1.v, RefPoint2.h, RefPoint2.v). For each subsequent field, shown in FIGS. 6B-6C, the coordinates of these tracking points are stored (pt1.h, pt1.v, pt2.h, pt2.v). The rotation effect for each image is determined using the following equations:

[0054] angle2=arc tan gent((pt2.v−pt1.v)/(pt2.h−pt1.h))

[0055] angle1=arc tan mgent((RefPoint2.v−RefPoint1.v)/(RefPoint2.h−RefPoint1.h))

[0056] angle2=angle2−angle1.

[0057] To superimpose a foreground object into a background with rotation the initial, optional intermediate and end values for the position of the foreground with respect to the background are first set at the key frames, as shown in FIG. 7B for a first key frame. Then rotation is applied to the object in each image using the following rotation angle computed for that image:

[0058] rotation angle=angle2.

[0059] This operation results in the foreground object rotating with the truck, as shown in FIGS. 7C-7D. If the purpose of the tracking was not to superimpose a foreground object, but to rotate the background and keep the moving object still, each image in the sequence would be subject to the following rotation:

[0060] rotation angle−angle2.

[0061] When tracking data is taken from a sequence of images in an interlaced media, undesired motion may appear in the tracking data due to the apparent movement of a point between the two fields that make up one image. To compensate for this apparent movement all tracking data taken from the second field of an interlaced image is shifted by half a line. In particular, for NTSC images the second field is shifted up half a line. For PAL images the second field is shifted down half a line.

[0062] The editor can create effects using the tracking data by either using the tracking data of the points to create position, rotation or scale effects or may use the tracking data combined into a transformation matrix. If isolated effects such as rotation or scale are desired, tracking points may be associated directly with those parameters. If matching the background movement as accurately as possible is desired, a transformation matrix may provide better results.

[0063] A transformation matrix is capable of using the tracking data of several points to create more detailed tracking effects. The matrix uses the tracking data to more accurately duplicate the motion of a tracked image, depending on the number of tracking points used. If one tracking point is used the matrix can be used to perform position transformations. If two tracking points are used the matrix can be used to perform position, scale and rotation transformations. If three tracking points are used the matrix can be used to perform position, scale, rotation and skew transformations. If four tracking points are used the matrix will perform position, scale, rotation, skew and perspective transformations. The inverse of the transformation matrix can be used for stabilization effects. Some digital video effects (DVE) processors use such a transformation matrix to define an effect to be performed on an image and can be used to perform effects in real time as described in U.S. Pat. No. 5,654,737. For each image a transformation matrix is loaded into the DVE processor.

[0064] The 3×3 transformation matrix M is created which represents the motion determined by the tracking data. The use of one to four tracking points is allowed. First the tracking data for the current field is obtained (pt1, pt2, pt3, pt4). The tracking data at the reference point is obtained (RefPoint1, RefPoint2, RefPoint3, RefPoint4). Based on the number of tracking points being used, a transformation matrix is determined by the motion of the tracking data from the reference point to the current field. The number of tracking points determine the coefficients of the transformation matrix M $M=\left|\begin{array}{ccc}A& D& G\\ B& E& H\\ C& F& I\end{array}\right|$

[0065] Given the initial and current position of a single point, a translation between them can be uniquely determined. This case is the same as the object replacement discussed above. The transformation here becomes $\begin{array}{ccc}A=1& D=0& G=0\\ B=0& E=1& H=0\\ C=X& F=Y& I=1\end{array}$

[0066] Given the initial position in a first image and current position in a subsequent image, defined using two points, a linear transformation between them can be uniquely determined. It is assumed here that the motion is that of a rigid body undergoing planar motion; i.e. no skew, only rotation, translation and scale. A translation of two points is accomplished in the following manner:

[0067] The distance between RefPoint1 and RefPoint2 is set as d, and the distance between pt1 and pt2 is set as r. A third reference point, RefPoint3, is added at a distance of d from RefPoint2, in a direction perpendicular to the vector from RefPoint1 to RefPoint2. A third current point, pt3, is added at a distance r from pt2, in a direction erpendicular to the vector from pt1 to pt2. Then the problem is treated as a three point ranslation as discussed below.

[0068] Given the initial position in a first image and current position in a subsequent image, defined using three points, an affine transformation between them can be uniquely determined. The transformation matrix is determined by solving the following set of simultaneous equations: $\begin{array}{cc}\mathrm{RefPoint1}.h*A+\mathrm{RefPoint1}.v*B+C& =\mathrm{pt}1.h\\ \mathrm{RefPoint2}.h*A+\mathrm{RefPoint2}.v*B+C& =\mathrm{pt}2.h\\ \mathrm{RefPoint3}.h*A+\mathrm{RefPoint3}.v*B+C& =\mathrm{pt}3.h\\ \mathrm{RefPoint1}.h*D+\mathrm{RefPoint1}.v*E+F& =\mathrm{pt}1.v\\ \mathrm{RefPoint2}.h*D+\mathrm{RefPoint2}.v*E+F& =\mathrm{pt}2.v\\ \mathrm{RefPoint3}.h*D+\mathrm{RefPoint3}.v*E+F& =\mathrm{pt}3.v\\ \mathrm{And}G=H=0,I=1& \end{array}$

[0069] Given the initial and current positions for four points, a projective transformation between them can be uniquely determined. Finding such a transformation which maps from one quadrilateral to another is straight forward; see for example the description in Fundamentals of Texture Mapping and Image Warping,Paul Heckbert, Master's thesis, UCB/CSD 89/516, CS Division, U.C. Berkeley, June 1989, hereby incorporated by reference.

[0070] FIG. 8 shows an example architecture of how tracking information may be handled. Tracking information is grouped according to an individual tracker. Tracking information includes tracked data points, confidence value, tracker type, location and sizes of search and pattern rectangles, ranges tracked and untracked, and other information associated with trackers. Access to the groups of tracking information is controlled by tracker data slots 810. The tracker data slots 810 map between the tracker number of user interface 800 and the respective slot number of the tracker. Trackers are instantiated by the tracker registry 802 at the request of the tracker data slots 810. The tracker data slots object 810 is responsible for managing the tracking engines 812 and the tracking data they produce.

[0071] The tracker registry 802 isolates the user interface 800 from interacting directly with the tracking engine 812. The tracker registry 802 keeps a list of, and allows for the use of different tracking engines 812. Tracked parameter slots 808 controls access to the tracked parameter groups. Each tracked parameter group manages the information associated with a single effect parameter that is utilizing tracking, such as which effect the parameter represents and whether the use of tracking information is currently enabled. The tracked parameter group also contains other information such as references to the contributing tracker, the rules for combining the tracked data points into one parameter point, and other information. The tracked parameter slots 808 map between the tracked parameter group number of the user interface 800 and the respective slot number of the parameter group. Through the tracked parameter slots object 808 the effects 806 can determine which of its parameters are currently using tracking and what their tracked parameter values are.

[0072] The tracking interface 804 provides facilities for creating trackers, mapping trackers to effect parameters, performing tracking, etc. The tracking interface 804 creates objects which group the tracked parameter slots and tracker data slots that are associated with a particular effect. The tracking interface 804 generally passes requests to it on to the tracked parameter slots object 808 or the tracker data slots object 810.

[0073] Having now described an embodiment of the invention, it should be apparent that the foregoing is merely illustrative and not limiting, having been presented by way of example only. Numerous modifications and other embodiments are contemplated as falling within the scope of the invention.