Method and apparatus for performing an automated inverse telecine process

[0002] The present invention relates generally to video processing systems. More specifically, the present invention includes a method and apparatus for processing a video sequence that automatically reconstructs the original frames from the output of a preceding telecine process.

[0003] The film used to record and project motion pictures is divided into a sequence of individual images known as frames. Video tape is encoded using a similar sequence of frames. As a result, it might appear that converting between film and video tape would be a simple process of transferring frames from the source media to equivalent frames within the destination media. Unfortunately, film and video tape are recorded using different frame rates. For film, the rate is typically twenty-four frames for each second. Video tape encoded using the NTSC standard uses a rate of approximately thirty frames per second. Video tape encoded using the PAL standard uses a rate of approximately twenty-five frames per second.

[0004] The different frame rates used by film and video complicates the conversion between the two types of media. Specifically, when converting from film to video tape, each second of film must be expanded from twenty-four to thirty frames. Effectively, an extra, or composite video frame must be made up or fabricated for each four frames of film. When converting from video tape to film, each second of video tape must be reduced from thirty to twenty-four frames. This means that one frame out of every five frames of video tape must be discarded.

[0005] The process of converting from film to video is known as telecine. Typical telecine processes create composite frames using an interlacing method. The interlacing method takes advantage of the fact that video frames are divided into an odd field and an even field. The even field includes all of the even lines within the video frame. The odd field includes all of the odd lines within the frame. An extra, or composite frame is created by combining the odd field from one frame with the even field from an adjacent second frame. The composite frame is is intended to approximate a midway point between frames and is inserted between the first and second frames.

[0006] The frames added by the telecine process make recordings made on film viewable in video formats. There are many cases, however, where it is desirable to remove the frames added during the telecine process. One of these cases At arises when video data needs to be compressed. Compression is used where it is necessary to reduce the number of bits used to digitally encode video data. Compression increases the capacity of storage devices, such as optical disks. Compression also increases the performance of video transmissions, such as satellite or Internet transmissions. Unfortunately, the composite frames produced by the telecine process tend to disrupt the compression process. This occurs because the output frame rate is higher (resulting in a greater amount of data), and because composite frames tend to be different than both their preceding and following frames. These differences introduce additional discontinuities in the sequence of frames. Video compression methods, such as MPEG, are most effective when applied to relatively continuous frame sequences. These compression methods exhibit lower efficiencies when they are applied to sequences of frames that have been processed through the telecine process.

[0007] The traditional method for removing composite frames requires an operator to manually detect the first composite frame by searching through the sequence of frames encoded on a video tape. The composite frame is then discarded. Each following fifth frame may then be discarded as well. In practice, this method suffers from at least two deficiencies. The first is the requirement that an operator manually scan through frames looking for the initial composite frame. The second, and potentially more serious, deficiency arises when composite frames are to be removed from a video tape that has been edited after the telecine process. In these cases, frames within the video tape may have been removed or added. This means that composite frames may occur at rather random intervals and not every fifth frame. The result is that the process of manually selecting the initial composite frame may have to be repeated. If a video tape includes a large number of edits, the manual selection process may become extremely time consuming or impractical.

[0008] As a result, it is clear that there is a need for a process that automatically removes the composite frames generated by the telecine process. This is especially important where the composite frames cannot be assumed to occur on a strictly periodic basis, as the case of an edited video tape.

[0009] An embodiment of the present invention provides a method and apparatus for performing an inverse telecine process. The inverse telecine process automatically detects and replaces composite frames created during a preceding telecine process. For the method of the present invention, a computer system reads each of the frames in a source video sequence. The computer system uses the frames to create an output video sequence.

[0010] During this process, the computer system analyzes the pixels included in each frame read from the source video sequence. If the pixels included in the even field of a frame correspond to the adjacent pixels included in the odd field, the computer system concludes that the frame is original. An original frame includes pixels from only one image. Original frames are added, without modification, to the destination video sequence.

[0011] If the pixels included in the even field of a frame do not correspond to their adjacent pixels included in the odd field, the computer system concludes that the frame is composite. A composite frame includes pixels from two distinct images and is created during a telecine process. When a composite frame is detected, the computer system attempts to reconstruct the composite frame to form an original frame.

[0012] To reconstruct composite frames into original frames, the computer system compares the pixels included in the composite frame to the pixels included in the frame that precedes the composite frame in the source video sequence. If the pixels included in the even field of the composite frame correspond to their adjacent pixels included in the odd field of the preceding frame, the computer system reconstructs an original frame using the even field of the composite frame and the odd field of the preceding frame. If the pixels included in the odd field of the composite frame correspond to their adjacent pixels included in the even field of the preceding frame, the computer system reconstructs an original frame using the odd field of the composite frame and the even field of the preceding frame. The computer system adds reconstructed frames to the destination video sequence.

[0013] The computer system creates interpolated frames for composite frames that cannot be reconstructed. The computer system creates interpolated frames by applying an interpolation function to the pixels included in the composite frames. The computer system adds interpolated frame to the destination video sequence only if they cannot be discarded without compromising the synchronization between the source and destination video sequences.

[0014] The method of the present invention performs the inverse telecine process using only a single pass and is self-adapting to a variety of different input and output frame rates. The automatic detection of composite frames means that the method is self-synchronizing and automatically adapts to discontinuities introduced during the editing process.

[0015] Advantages of the invention will be set forth, in part, in the description that follows and, in part, will be understood by those skilled in the art from the description herein. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.

[0016] The accompanying drawings, that are incorporated in and constitute a part of this specification, illustrate several embodiments of the invention and, together with the description, serve to explain the principles of the invention.

[0017] FIG. 1 is a block diagram of a host computer system shown as an exemplary environment for an embodiment of the present invention.

[0018] FIG. 2 is a block diagram of an inverse telecine process in accordance with an embodiment of the present invention.

[0019] FIG. 3 is a flow chart showing the steps associated with an inverse telecine process as used by an embodiment of the present invention.

[0020] FIG. 4ais a block diagram of a first original video frame as exemplary input for an embodiment of the present invention.

[0021] FIG. 4bis a block diagram of a second original video frame as exemplary input for an embodiment of the present invention.

[0022] FIG. 4cis a block diagram of a composite video frame as exemplary input for an embodiment of the present invention.

[0023] FIG. 5 is a flow chart showing the steps associated with a frame selection method telecine process as used by an embodiment of the present invention.

[0024] FIG. 6 is a detail showing a group of pixels in a video frame.

[0025] Reference will now be made in detail to preferred embodiments of the invention, examples of which are illustrated in the accompanying drawings. Wherever convenient, the same reference numbers will be used throughout the drawings to refer to the same or like parts.

[0026] Environment

[0027] In FIG. 1, a computer system 100 is shown as a representative environment for the present invention. Structurally, computer system 100 includes a processor, or processors 102, and a memory 104. An input device 106 and an output device 108 are connected to processor 102 and memory 104. Input device 106 and output device 108 represent a wide range of varying I/O devices such as disk drives, keyboards, modems, network adapters, printers and displays. Each node 102 may also includes a disk drive 110 of any suitable disk drive type (equivalently, disk drive 110 may be any non-volatile mass storage system such as “flash” memory).

[0028] Inverse Telecine Process

[0029] An embodiment of the present invention includes a method and apparatus for performing an inverse telecine process. The inverse telecine process automatically detects and replaces or discards composite frames created during a preceding telecine process. As shown in FIG. 2, a representative telecine process 202 accepts a source video sequence 204 as input and creates a destination video sequence 206 as output. Source video sequence 204 and destination video sequence 206 are video data encoded as sequences of individual frames. For the purposes of the present invention, source video sequence 206 may be encoded using any suitable video format, such as QUICKTIME, AVI, DV or MPEG, or. This means that source video sequence 206 may be taken from a wide range of different sources, including computer networks, video tapes and optical disks. Destination video sequence 206 may be created using any suitable video format (i.e., QUICKTIME, AVI, DV or MPEG). This allows destination video sequence 206 to be created for a range of different destinations including, once again, computer networks, video tapes and optical disks. For some embodiments, different video formats will be used for source video sequence 204 and destination video sequence 206.

[0030] In FIG. 3, a representative implementation of inverse telecine process 202 is shown as method 300. Method 300 includes a series of steps performed by computer system 100 during transformation of source video sequence 204 to destination video sequence 206. Method 300 begins with initialization step 302. In step 302, computer system 100 performs any sub-steps that are required prior to execution of the main steps of method 300. In particular, computer system 100 initializes a source timer and a destination timer. Computer system 100 uses the source timer to track the number of seconds of source video sequence 204 that have been consumed. Computer system 100 uses the destination timer to track the number of seconds of destination video sequence 206 that have been produced. In step 302, computer system 100 initializes both of these timers to zero.

[0031] In step 304, computer system 100 determines if the input of the inverse telecine process is falling behind the output of the inverse telecine process. To make this determination, computer system 100 compares the start time of the next frame to be processed in source video sequence 204 (i.e., the source timer) to the start time of the next frame to be added to output video sequence 206 (i.e., the destination timer). During the first execution of step 304, both of these timers are zero and execution of method 300 automatically continues at step 312. In subsequent executions, computer system 100 moves to step 306 if the destination timer leads the source timer by a frame or more. In the alternative (i.e., if the destination timer does not lead the source timer by a frame or more), computer system 100 moves to step 312.

[0032] In the case where the input is falling behind the output, execution of method 300 continues at step 306. In step 306, computer system 100 skips over one of the frames included in source video sequence 204. The skipped frame is discarded and is not transferred to destination video sequence 206. The value of the source timer is incremented by computer system 100 by an amount that is equal to the duration of the skipped frame. This allows computer system 100 to advance through source video sequence 204 to increase the synchronization between the source timer and the destination timer.

[0033] Following execution of step 306, computer system 100 continues execution of method 300 at step 308. In step 308, computer system 100 determines if there are any unprocessed frames remaining in source video sequence 204. In the negative case (where all frames have already been processed), computer system 100 ends method 300 at step 310. Where there are remaining frames left to be processed, computer system 100 continues method 300 with another iteration of step 304.

[0034] In the case where the input of the inverse telecine process is not falling behind the output of the telecine process, computer system 100 continues execution of method 300 at step 312. In step 312, computer system 100 retrieves a frame from source video sequence 204. The frame retrieved during step 312 is one of two different types: original or composite. Original and composite frames are better understood by reference to FIGS. 4athrough 4c.In FIG. 4a,a representative frame is shown and generally designated 400a.Frame 400aincludes a series of 486 lines. Each line has 420 pixels. The lines within each frame are divided into an even frame and an odd frame. The even frame includes each even numbered line (i.e., lines 0, 2, 4, etc.) The odd frame includes each odd numbered line (i.e., lines 1, 3, 5, etc.).

[0035] A frame is original if the odd and even fields both contain pixel data from a single image. For the purposes of this description, it is assumed that FIG. 4ais original and includes a single image of a solid rectangle. Frame 400bof FIG. 4bincludes the same image of a rectangle. In the case of frame 400b,however, the image of the rectangle has been shifted two pixels to the right. The shifted, solid rectangle is the only image included in frame 400b.For this reason, frame 400bis also an original frame.

[0036] A frame is composite if its odd and even fields contain pixel data from distinct images. This is the case for frame 400cof FIG. 4c.The even field of frame 400ccontains the same pixel data as the even field of 400a.The odd field of frame 400ccontains the same pixel data as the odd field of 400b.For this reason, frame 400ccontains pixels data from two distinct images, the solid rectangle of frame 400aand the shifted, solid rectangle of FIG. 4b.Composite frames result when video sequence are transformed by a telecine process. Frame 400cis an intermediate frame that was inserted between frames 400aand frame 400bto adapt source video sequence 204 from a format having fewer frames per second (such as film) to a format having more frames per second (such as video). The telecine process creates frame 400cusing the even field of frame 400aand the odd field of frame 400b.Since frames 400aand 400binclude different images, frame 400ccontains pixels data from two distinct images.

[0037] As mentioned, computer system 100 retrieves an original or a composite frame from source video sequence 204 during step 312. When practical, the frame retrieved in step 312 is original. In all other cases, the retrieved frame is composite. An embodiment of the method used by computer system 100 to get a next frame from source video sequence 204 is designated 500 in FIG. 5. Method 500 may be invoked as a subroutine or procedure. Alternately, method 500 may be included as inline code within method 300.

[0038] Method 500 begins, symbolically, with placeholder 502. During each invocation of method 500, computer system 100 reads a new frame from source video sequence 204. This frame is referred to as the current frame. Before updating the current frame, computer system 100 saves the old value (i.e., the frame read in the preceding invocation of method 500). The saved frame is referred to as the previous frame. In FIG. 5, the process of saving the current frame as the previous frame and reading a new frame to be the current frame are shown as steps 504 and 506, respectively. Both the previous frame and the current frame are stored in memory buffers or otherwise positioned to allow the pixels within the frames to be accessed. During step 506, computer system 100 increments the value of the source timer by an amount that is equal to the duration of the frame read from source video sequence 206.

[0039] In step 508, computer system 100 computes three values based on the pixels included in the current frame and the pixels included in the previous frame. The first of these values measures the similarity between pixels included in the even field of the current frame and adjacent pixels included in the odd field of the current frame. For the sake of convenience this value is referred to in this document as: ΔC_EC_O. The second value calculated in step 508 measures the similarity between pixels included in the even field of the current frame and adjacent pixels included in the odd field of the previous frame. For the sake of convenience this value is referred to in this document as: ΔC_EP_O. The final value calculated in step 508 measures the similarity between pixels included in the odd field of the current frame and adjacent pixels included in the even field of the previous frame. For the sake of convenience this value is referred to in this document as: ΔC_OP_E.

[0040] To compute ΔC_EC_Ocomputer system 100 selects a predetermined percentage of the pixels of the even field of the current frame. For each selected pixel, computer system 100 calculates a value that represents the degree of similarity between the selected pixel and nearby pixels within the odd field of the current frame. For one embodiment of the present invention, computer system 100 makes this calculation by comparing each selected pixel with four pixels that are vertically aligned with the selected pixel. This is shown more clearly in FIG. 6 where the selected pixel is shown at location x, y. Computer system 100 compares this selected pixel with its two vertically aligned and adjacent neighbors. These pixels are located at x, y+1 and x, y−1. Both of these pixels are included within the odd field of the current frame (since the selected pixel is included within the even frame). Computer system 100 also compares the selected pixel with the two pixels that are vertically aligned and separated by one pixel from selected pixel. These pixels are located at x, y+2 and x, y−2. Both of these pixels are included within the even field of the current frame (since the selected pixel is included within the even frame).

[0041] Computer system 100 compares each selected pixel to the pixels above and below the selected pixel using an equation of the form:

[0042] difference (x,y)=rgb_diff ((x,y),(x,y+1))+rgb_diff ((x,y),(x,y−1))−rgb_diff ((x,y),(x,y+2))−rgb_diff ((x,y),(x,y−2))

[0043] where rgb_diff (a,b) computes the difference between two pixels and b. Preferably, but not necessarily, rgb_diff (a,b) computes the difference between pixels a and b using the following equation:

[0044] $\mathrm{rgb\_diff}\left(a,b\right)=\sqrt{{\left(\mathrm{red}\left(a\right)-\mathrm{red}\left(b\right)\right)}^2+{\left(\mathrm{green}\left(a\right)-\mathrm{green}\left(b\right)\right)}^2+{\left(\mathrm{blue}\left(a\right)-\mathrm{blue}\left(b\right)\right)}^2}$

[0045] rgb_diff (a,b) returns small values when pixels a and b are similar and reaches zero when pixels a and b are equivalent. As a result, the function difference (x,y) tends to be negative when evaluated within original frames that include a single image. This follows because pixels within these frames tend to be more similar to nearby pixels and less similar to pixels father away. This causes the first two components of difference (x,y) (i.e., rgb_diff ((x,y),(x,y+1)) and rgb_diff ((x,y),(x,y−1))) to contribute a relatively small positive value while the second two components (i.e., rgb_diff ((x,y),(x,y+2)) and rgb_diff ((x,y),(x,y−2))) contribute larger negative values. This situation is reversed for composite frames that include two images. In these cases, pixels tend to be more similar to pixels within the same field. This means that pixels are more likely to resemble pixels two pixels away (vertically) than they are to immediately adjacent pixels. This means that the first two components of difference (x,y)contribute larger values than the second two components making the overall value of difference positive.

[0046] To compute ΔC_EC_Ocomputer system 100 computes difference (x,y) for each selected pixel in the current frame. ΔC_EC_Ois the sum of each computed value of difference (x,y). Negative values for ΔC_EC_Oindicate that pixels within the current frame tend to be similar to their nearby pixels. This is expected for original frames that contain only a single image. Positive values for ΔC_EC_Oindicate that pixels within the current frame tend to be different than their adjacent pixels but similar to pixels in the same field. This is expected for composite frames that contain two images.

[0047] Computer system 100 computes values for ΔC_EP_Oand ΔC_OP_Eusing the same method used to compute ΔC_EC_O. Before computing these values, however, computer system constructs two frames. The first constructed frame includes the even field from the current frame and the odd field from the previous frame. This frame is referred to as C_EP_O. The second constructed frame includes the odd field from the current frame and the even field from the previous frame. This frame is referred to as C_OP_E. Computer system 100 repeats the method used to calculate ΔC_EC_Ousing the first constructed frame (C_EP_O) to calculate ΔC_EP_O. Computer system 100 then repeats the method used to calculate ΔC_EC_Ousing the second constructed frame (C_OP_E) to calculate ΔC_OP_E.

[0048] In step 510, computer system 100 compares ΔC_EC_O, ΔC_EP_Oand ΔC_OP_Ewith zero. If each of these values is greater than zero, computer system 100 concludes method 500 at step 512. In step 512 computer system 100 returns the current frame and indicates that the returned frame is a composite frame.

[0049] In the alternative (i.e., where one of ΔC_EC_O, ΔC_EP_Oand ΔC_OP_Eis less than zero) computer system 100 continues method 500 at step 514. In step 514, computer system 100 determines if ΔC_EC_Ois less than ΔC_EP_Oand ΔC_OP_E. If so, computer system 100 concludes method 500 at step 516. In step 516 computer system 100 returns the current frame and indicates that the returned frame is an original frame.

[0050] In the alternative (i.e., where one of ΔC_EP_Oor ΔC_OP_Eis less than ΔC_EC_O) computer system 100 continues method 500 at step 518. In step 518, computer system 100 determines if ΔC_EP_Ois less than ΔC_EC_Oand ΔC_OP_E. If so, computer system 100 concludes method 500 at step 520. In step 520 computer system 100 returns the C_EP_Oframe and indicates that the returned frame is an original frame.

[0051] The final alternative to the series of tests made in steps 510, 514 and 518 is step 522. Computer system 100 reaches step 522 if ΔC_OP_Eis less than ΔC_EC_Oand ΔC_EP_O. In step 522 computer system 100 returns the C_OP_Eframe and indicates that the returned frame is an original frame.

[0052] In cases where method 500 returns an original frame (i.e., steps 516, 520 and 522), the returned frame may include one or both fields from the current frame. Preferably, method 500 is configured so that the identity of these fields are tracked. This allows computer system 100 to determine whether a particular field has been previously used. Computer system 100 uses this information to avoid constructing and returning frame (C_EP_O) or frame (C_OP_E) where these frames would contain previously used frames.

[0053] Following the invocation of method 500, computer system 100 continues method 300 at step 314. In step 314, computer system 100 checks to see if method 500 returned an original or a composite frame. In the former case, computer system continues at step 314 by adding the returned frame to destination video sequence 206. Computer system 100 also increments the destination timer by an amount equal to the duration of the returned frame. Computer system 100 then continues method 300 at step 308 to determine if method 300 should continue to process remaining frames in video sequence 204 or terminate at step 310.

[0054] In the case where computer system 100 determines in step 314 that the frame is a composite frame, computer system 100 continues execution of method 300 at step 318. In step 318, computer system 100 determines if the input of the telecine process has gotten ahead of the output of the inverse telecine process. To make this determination, computer system 100 compares the start time of the returned frame (i.e., the source timer) to the start time of the next frame to be added to output video sequence 206 (i.e., the destination timer). Computer system 100 moves to step 320 if the source timer leads the destination timer by a frame or more. In the alternative (i.e., if the source timer does not lead the destination timer by a frame or more), computer system 100 moves to step 312.

[0055] In the case where input leads output, computer system 100 continues execution of method 300 at step 320. In step 320, computer system 100 uses the returned frame to create an interpolated frame. Each pixel (x, y) in the interpolated frame is computed using a weighted average of the same pixel (x, y) in the returned frame and two immediately adjacent pixels (x, y−1) and (x, y+1). For the purposes of the present invention many different interpolation functions may be used. One function that has been found to be particularly effective is:

[0056] interpolated frame (x, y)=0.25*subject frame (x, y−1)+0.50*subject frame (x, y)+0.25*subject frame (x, y+1)

[0057] Computer system 100 adds the interpolated frame to destination video sequence 206. Computer system 100 increments the destination timer by an amount equal. to the duration of the interpolated frame. Computer system 100 then continues method 300 at step 308 to determine if method 300 should continue to process remaining frames in video sequence 204 or terminate at step 310.

[0058] In the case where the input has not gotten ahead of the output, computer system 100 continues method 300 at 322. This causes the returned frame to be discarded, increasing the synchronization of input and output of the inverse telecine process. In step 322, computer system 100 discards the returned frame. Computer system 100 then continues execution of method 300 at step 324. In step 324, computer system 100 determines if there are any unprocessed frames remaining in source video sequence 204. In the negative case (where all frames have already been processed), computer system 100 ends method 300 at step 310. Where there are remaining frames left to be processed, computer system 100 continues method 300 with another iteration of step 312.

[0059] Other embodiments will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and examples be considered as exemplary only, with a true scope of the invention being indicated by the following claims and equivalents.