FIELD OF THE INVENTION The present invention relates to computer based image processing and in particular to an interactive editing system that generates free-form curves from key frames for a sequence of static images.

BACKGROUND OF THE INVENTION The composition of images using digital techniques has recently grown in popularity for providing special effects in movies, television programs, multimedia presentations, and in a variety of other applications.

One of the tasks of such a system is so-called"image segmentation"which is the singling out of one part of the sequence of images for special treatment. Image segmentation is used in movies, for example, when it is desired to combine objects from different image sequences, such as in the movie Forest Gump where the lead character meets President Kennedy. Image segmentation can also be used to indicate that part of an image should be treated differently from other parts. For example, a transparent window in an otherwise opaque wall should typically be treated differently for shading purposes. The goal of image segmentation is to combine objects or regions from various still photographs or movie frames to ultimately create a scene which is believable and convincing.

Typically, a segment is identified in each of a certain number of frames in which it appears (called "key frames").

It is common, for example, to make use of the concept of key-frameable curves. In this instance, a user specifies a mathematical expression for a curve in one image of a sequence of images called a key frame.

In another curve in some downstream image, a second curve is also specified. The system then proceeds to create curves for the intervening images such as by mathematical interpolation between the two curves.

Various techniques are then used to identify the segment in the frames which occur between the key frames.

For example, the most commonly used techniques require the user to identify the boundaries of a segment by manually placing seed points and redefining the entire boundary in each key frame. This tends to be a tedious and inaccurate process. The system then automatically fills in the intermediate frames, causing the segment to morph from one position to the next.

Manual segmentation in general is tedious and time consuming, lacks precision, and is impractical when applied to long image sequences. Furthermore, due to the wide variety of image types, most automatic segmentation techniques are inaccurate and require significant user input to control the process.

Other boundary definition methods use contours, splines, or so-called"snakes"to automatically improve a manually entered rough approximation. For example, after an initial rough boundary approximation, such processes mathematically adjust the boundary points in

an attempt to minimize an error function. Other classes of image segmentation techniques typically require a boundary template in the form of a manually entered rough approximation or figure of merit. The template is then used to impose directional sampling and/or searching constraints. Boundary extraction using graph searching techniques is therefore not interactive beyond the template specification, and loses the benefits of further human guidance and expertise.

SUMMARY OF THE INVENTION The present invention is a technique for specifying key frames with free-form hand drawn curves that is not restricted by mathematical formulations.

The user is first enabled to draw any arbitrary or free-form shape in a first key frame. The user then edits the appearance of the free-form shape overlaid in a subsequent key frame. The process leaves unmodified the part of the free-form shape that the user did not edit. The system then makes use of the edit information in order to automatically generate a representation of the shapes for the intermediate frames using the edit information. For example, the system may mathematically interpolate between the initial free-form shape and the edited form. The interpolation information is then used to render a representation of the image segment for frames which occur between the two key frames.

Unlike other algorithms, the technique does not constrain the shapes to be particular types of predefined shapes such as Bezier curves, splines, or

other curves defined by seed points. Rather, the technique works on for any arbitrary shape that can be sketched.

Furthermore, the technique allows the image segment to change from frame to frame in a way that appears more natural to the viewer then the output of most currently available systems that make use of automation of some type.

BRIEF DESCRIPTION OF THE DRAWINGS The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

Fig. 1 is a diagram of a computer based video graphics system that operates on a sequence of images to define image segments according to the invention.

Fig. 2 is a more detailed view of a screen presented to the user of the system shown in Fig. 1.

Fig. 3 illustrates how a curve can be generated for an intermediate key frame according to the invention.

Figs. 4A through 4C depict a sequence of exemplary images in which the technique is applied.

Figs. 5A through 5C further illustrate a technique for interpolation.

DETAILED DESCRIPTION OF THE INVENTION Turning attention now more particularly to the drawings, Fig. 1 is a block diagram of the components of a digital image processing system 10 in which key- frameable free-form curves are developed according to the invention. The system 10 includes a computer workstation 20, a computer monitor 21, and input devices such as a keyboard 22, mouse or stylus 23. The workstation 20 also includes input/output interface 24, storage 25 such as a disk 26, and random access memory 27, as well as one or more processors 28. The workstation 20 may, for example, be a graphics workstation such as the 02/Octane sold by Silicon Graphics, Inc., a windows NT-type workstation, or other suitable computers. The monitor 21, keyboard 22, and input device 23 are used indirect with various software elements of the system that exists within the workstation 20 cause software programs to be run and data to be stored as more particularly described below.

The system 10 also includes hardware elements typical of an image processing system such as video monitor 30, audio monitor 31, hardware accelerator 32, and other user input devices 33. Also included are image capture devices such as a video cassette recorder (VCR), video tape recorder (VTR), and/or digital disc recorder 34 (DDR), cameras 35 and/or film scanner/telecine 36. Sensors 38 might also provide information about the scene and emit capture devices.

The present invention may be used in particular for developing an edited sequence of images. It should be understood, however, that are other applications for systems which permit the user to (a) create a curve in

one image, (b) then create a curve in some other downstream image and (c) ask the system to automatically create curves for any intervening images.

As explained above, image segmentation is often used to single out one part of a sequence of images for special treatment. The special treatment may include replacing part of the image with some other image (for example, a sequence of images captured with a video camera may need to have a portion therein replaced with a synthetically generated image) where that part of the image may need to be treated differently from other parts of an image during subsequent processing. For example, a transparent window in an otherwise opaque wall might need to be treated differently for the purposes of generating proper lighting, shadowing, and reflection affects.

As shown in Fig. 2, the user is presented with a display such as through a window on the computer screen on the monitor 21 in which the sequence of images 40 may be viewed. The user typically has available a set of VCR-like controls 42 that permit playing, fast forwarding, rewinding and stopping the sequence as desired. The system 10 also provides the user with a set of editing tools 44 common in graphics editing such as pick tools, shape drawing tools, line sketching tools, and the like. In the particular example shown, the user is working with a sequence of images that depict a locomotive train that is moving towards the camera.

Fig. 3 shows a sequence of steps that are performed in part by the user interacting with the display shown in Fig. 2 and in part by the system 10

automatically performing certain steps. The sequence of steps : allows the user to draw any arbitrary shape in a first key frame ; * allows the user to edit its appearance in a second key frame ; and * automatically, using the edit information, provide corresponding shapes for the frames occurring between the two key frames.

The result is that the user may make use of key- framing techniques using only free-form hand drawn curves as a tool for identifying non-regularly shaped areas in image for further processing, such as through image segmentation.

Now more particularly, from an idle state 100, in a first state 102, the system 10 displays the first key frame, which is frame number"n"in this instance.

In a next state 104, the user defines a first free-form curve such as by using the available drawing tools 44. This free-form curve is then stored as, for example, a series of x, y coordinate points by the system in its memory 27.

As shown in Fig. 4A, the user is presented with the view of frame number n and they may choose to define a first free-form curve 50 that comprises a portion of the edge of the locomotive 48. In this instance, as shown in Fig. 5A, the free-form curve 50 is defined as a set of three points 52-1, 52-2, 52-3.

In the next state 106, the user moves to a different frame such as frame n+m. In the next state 108, the system causes the first free-form curve to be overlaid upon the view of frame n+m. The dashed lines

in Fig. 4C indicate the originally overlaid first curve 50 while the user is viewing frame n+m.

In state 110, the user defines an edited free-form curve while viewing frame n+m. The end result is not only a view of the edited curve 54, but also information that was used to transform the first curve 50 into the edited curve 54.

In the next state 112, as the user wishes to review intermediate frames located between frame n and frame n+m, the process for generating additional shapes proceeds.

More particularly as shown in states 114 through 118, in a first state 114, points on the first curve 50 and the edited curve 54 are first identified. The edited curve 54 may have, for example, been defined by four points 56-1, 56-2, 56-3, 56-4. The original curve 50 thus may appear as the dotted lines in Fig. 4C.

However, by using a stylus 23 or mouse, the user redefines a portion of the edited curve at 54, such as by picking end points of a section and then dragging or "rubber banding"the section to a different location By using the information indicating how the user edited the curve 50, the system 10 then knows the areas of the two curves that are related to one another. In this instance, an interpolation process is used to change the section of the curve only where it has been edited, leaving the curve alone where it has not.

Thus, for example, a first portion I of the curve is not changed ; however, a second portion II of the curve which was edited will be used in the interpolation process.

In the first state 114, a parameterization process is used to generate a parameter for each point for each edited curve in each key frame. For example, this process may begin by starting at a beginning point such as point 52-1 for edited segment 50, and performing a normalized distance calculation to a value of 1. In this instance, the second point 522 lies half-way along the segment 50 and is therefore given a parameter of 0. 5. The third point 52-3 lies at the end of the segment 50 and is given a parameter of 1. 0. The parameters may be determined, for example, by taking a cumulative distance of the point along the segment 50 from the beginning to the end.

A similar process takes place for the edited segment 54 as shown in Fig. 5C. In particular, the edited segment 54 also has a point 56-1 with a parameter of 0. 0 and also a point 56-4 with a parameter of 1. 0. However, the edited segment 54 has points 56-2 and 56-3 that lie a distance of 0. 33 and 0. 66 respectively. These parameters are thus similarly determined for the edited segment 54.

In the next state 116, which is a normalization state, points are added to both the first segment 50 and edited segment 54 so that the number of points on each segment is the same. Thus, for example, a point 52-4 and 52-5 are added to the first segment 50 located at a corresponding parameter distance location 0. 33 and 0. 66. Likewise, a fifth point, 56-5, is added to the edited segment 54 at x, y location corresponding to a parameter of 0. 5.

The final step 118 is to perform a linear interpolation assuming an x, y location for each point.

For example, the linear interpolation may take the mathematical form of : x,=x,+J[x-x,] m+l Yn+iYn----LYn+m*Yn-i m+l The result is an interpolated segment 60 such as shown in Fig. 5B having a number of points 62-1 through 62-5.

Thus, when the user"rewinds"his view of the sequence of images to a frame n+i, a view of the free form segment 60 for the intermediate images is easily calculated and presented to the user as shown in Fig.

4C.

It should be understood that the user can make any number of edits to the original free-form curve, with the only constraint that the user cannot introduce a completely new free-form curve in the second key frame n+m.

It should also be understood that techniques other than strict mathematical interpolation may be used to derive the intermediate curves.

While this invention has been particularly shown and described with references to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.