Encoding/decoding moving images with forward and backward keyframes for forward and reverse display

• US 5,267,334 A
• Filed: 01/21/1993
• Issued: 11/30/1993
• Est. Priority Date: 05/24/1991
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Normille, James O., Chu, Ke-Chiang C., Wright, Daniel W., Yeh, Chia L.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Johns, Andrew W.
• Application Number:
  US08/006,686
• Time in Patent Office: 313 Days
• Field of Search: 382/56, 358/133, 358/135, 358/136, 358/105
• US Class Current: 382/236
• CPC Class Codes: H04N 19/107 between spatial and temporal predictive coding, e.g. picture refresh
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/142 Detection of scene cut or scene change
• CPC Class Codes: H04N 19/146 Data rate or code amount at the encoder output
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/179 the unit being a scene or a shot
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/577 Motion compensation with bidirectional frame interpolation, i.e. using B-pictures
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 19/87 involving scene cut or scene change detection in combination with video compression
• CPC Class Codes: H04N 5/147 Scene change detection
• CPC Class Codes: H04N 5/783 Adaptations for reproducing at a rate different from the recording rate
• CPC Class Codes: H04N 5/85 on discs or drums
• CPC Class Codes: H04N 7/54 the signals being synchronous H04N21/23602, H04N21/23614, H04N21/2365, H04N21/2368, H04N21/4341, H04N21/4342, H04N21/4347, H04N21/4348 take precedence
• CPC Class Codes: H04N 9/8042 involving data reduction
• CPC Class Codes: H04N 9/877 by assembling picture element blocks in an intermediate memory

Abstract

A method of removing frame redundancy in a computer system for a sequence of moving images. The method comprises detecting a first scene change in the sequence of moving images and generating a first keyframe containing complete scene information for a first image. The first keyframe is known, in a preferred embodiment, as a "forward-facing" keyframe or intra frame, and it is normally present in CCITT compressed video data. The process then comprises generating at least one intermediate compressed frame, the at least one intermediate compressed frame containing difference information from the first image for at least one image following the first image in time in the sequence of moving images. In a preferred embodiment, this at least one frame is known as an inter frame. Finally, detecting a second scene change in the sequence of moving images and generating a second keyframe containing complete scene information for an image displayed at the time just prior to the second scene change. This is known, in the preferred embodiment, as a "backward-facing" keyframe. The first keyframe and the at least one intermediate compressed frame are linked for forward play, and the second keyframe and the intermediate compressed frames are linked in reverse for reverse play. In a preferred embodiment, the intra frame is used for generation of complete scene information when the images are played in the forward direction. When this sequence is played in reverse, the backward-facing keyframe is used for the generation of complete scene information.

Claims

1. A method of encoding a first sequence of moving images as a second sequence of images in a computer system comprising:

a. detecting a first scene change in the first sequence of moving images and generating a first keyframe containing complete scene information for a first image detected at said first scene change in the first sequence of moving images for play of the second sequence of images in the forward direction;

b. generating at least one intermediate frame for the second sequence of images following said first keyframe, the at least one intermediate frame containing difference information from the first image for at least one image following the first image in time in the first sequence of moving images; and

c. detecting a second scene change in the first sequence of moving images and generating a second keyframe following said at least one intermediate frame in the second sequence of images, said second keyframe containing complete scene information prior to the second scene change in the first sequence of moving images for play of the second sequence of images in reverse.

2. The method of claim 1 further comprising linking the first keyframe and the at least one intermediate compressed frame in the forward direction for forward play, and linking the second keyframe and the at least one intermediate compressed frame in reverse for reverse play.

3. A method of encoding a sequence of images in a computer system comprising:

a. for playing said sequence of images in a forward direction, linking a first frame to a second frame, said first frame preceding said second frame temporally, the second frame containing complete image information for a first scene, and linking the second frame to a third frame, the third frame comprising image difference information from the second frame and following said second frame temporally in said sequence of images when said sequence of images is played in the forward direction; and

b. for playing said sequence of images in a reverse direction, linking the third frame to a forth frame, the fourth frame containing complete image information for a second scene preceding said second frame and following said first frame temporally in said sequence of images, and linking the fourth frame to the first frame, the first frame comprising image difference information from the fourth frame in said sequence of images when said sequence of images is played in said reverse direction.

4. An improved method of displaying an encoded sequence of images in a display system, the encoded sequence of images comprising a first frame, second frame, third frame and fourth frame, the second frame containing complete scene information for said encoded sequence of images, the third frame containing difference information from the second image and following the second image temporally when said encoded sequence of images is displayed in a forward direction, the fourth frame containing complete scene information, preceding said second frame and following said first frame temporally in said sequence of images, said first frame containing difference information from the fourth frame, the method comprising:

a. displaying the sequence of images in said forward direction by first displaying the first frame, second skipping the fourth frame, third displaying the second frame, and forth generating a first sum image of the second frame and the third frame and displaying the first sum image; and

b. displaying the sequence of images in a reverse direction by first displaying the third frame, second skipping the second frame, third displaying the fourth frame, fourth generating a second sum image of the fourth frame and the first frame and displaying the second sum image.

5. A sequence of encoded images for representing a sequence of unencoded images, said sequence of encoded images which may be displayed in a forward direction and in a reverse direction, said sequence of encoded images comprising:

a. a first intra frame, said first intra frame establishing complete scene information for a first scene change of said unencoded sequence of images, said intra frame being first in said encoded sequence of images;

b. at least one inter frame, said at least one inter frame comprising difference information from said first intra frame for at least one second image in said unencoded sequence of images and following said first intraframe in said encoded sequence of images; and

c. a second intra frame, said second intraframe comprising complete scene information for a frame prior to a second scene change of said unencoded sequence of images, said second intra frame following said at least one inter frame in said encoded sequence of images temporally, said first intra frame being displayed first during said forward display of said encoded sequence of images, followed by said at least one inter frame, and said second intra frame being displayed during said reverse display of said encoded sequence of images, said at least one inter frame following said second intra frame temporally during said reverse display of said encoded sequence of images.

6. The sequence of images of claim 5 which is encoded according to the CCITT standard H.261 (International Consulative Committee on Telephony and Telegraphy).

7. The encoded sequence of images of claim 5 further comprising:

a. a third intra frame, the third intra frame establishing complete scene information for said second scene change of said unencoded sequence of images, said third intra frame following said at least one inter frame temporally in said encoded sequence of images during said forward display of said encoded sequence of images; and

b. at least one second inter frame, said at least one second inter frame comprising difference information of frames following said second scene change in said unencoded sequence of images from said third intra frame and following said third intraframe temporally in said encoded sequence of images.

8. The encoded sequence of images of claim 5 wherein said unencoded sequence of images is encoded to generate said encoded sequence of images using temporal prediction, block-based transformation, quantization, and variable length coding.

9. The sequence of images of claim 5 wherein for forward display of said encoded sequence of images, said first intra frame is linked with said at least one interframe in said encoded sequence of images, and said at least one interframe is linked to a next encoded sequence of images for display in the forward direction after display of said second intra frame, and for reverse display of said encoded sequence of images, said second intra frame is linked with said at least one inter frame, and said at least inter frames is linked with a previous sequence of encoded images prior to said first intra frame.

10. An apparatus for decoding an encoded sequence of images comprising:

a. a means for providing forward display of said encoded sequence of images, comprising means for decoding a forward keyframe in said encoded sequence of images which comprises complete scene information for the beginning of the encoded sequence of images, and which further comprises a means for decoding at least one intermediate frame comprising scene difference information from said forward keyframe when displaying said encoded sequence of images in a forward direction; and

b. a means for providing reverse display of said encoded sequence of images, comprising means for decoding a reverse keyframe which comprises complete scene information for the end of said encoded sequence of images, and which further comprises a means for decoding said at least one intermediate frame while displaying said encoded sequence of images in a reverse direction.

11. The apparatus of claim 10 further comprising playback control means for activating said means for providing forward display of said encoded sequence of images, and said means for providing reverse display of said encoded sequence of images.

12. The apparatus of claim 10 further comprising variable length decoding means for decoding said forward keyframe and said reverse keyframe in said encoded sequence of images.

13. The apparatus of claim 10 further comprising means for combining said at least one interframe with either said forward keyframe or said reverse keyframe in said encoded sequence of images.

14. The apparatus of claim 10 further comprising means for detecting said forward keyframe and said reverse keyframe in said encoded sequence of images.

15. The apparatus of claim 10 wherein the sequence of images is encoded according to the CCITT standard H.261 (International Consultative Committee on Telephony and Telegraphy).

16. An apparatus for encoding a first sequence of unencoded images as a sequence of encoded images which may be displayed in a forward direction and a reverse direction comprising:

a. scene change detection means for determining when the difference between a frame and preceding frames of said unencoded sequence of images has exceeded a predetermined threshold;

b. forward keyframe creation means for creating a forward keyframe in said sequence of encoded images when a first scene change at a first frame has been detected in said unencoded sequence of images, said forward keyframe comprising complete scene information for said first frame of said unencoded sequence of images;

c. difference frame creation means for creating at least one difference frame following said forward keyframe in said encoded sequence of images from at least one second frame in said unencoded sequence of images following said first frame, said at least one difference frame comprising difference information between the forward keyframe and said at least one second frame in said unencoded sequence of images following said first frame;

d. reverse keyframe creation means for creating a reverse keyframe in said encoded sequence of images when a second scene change has been detected at a third frame in said unencoded sequence of images, said reverse keyframe comprising complete scene information for a fourth frame in said unencoded sequence of images, said fourth frame immediately preceding said third frame in said unencoded sequence of images; and

e. linking means for linking said forward keyframe with said at least one difference frame in said encoded sequence of images for display of said encoded sequence of images in a forward direction, and further for linking said reverse keyframe with said at least one difference frame in said encoded sequence of images for display of said encoded sequence of images in a reverse direction.

17. The apparatus of claim 16 wherein the scene change detection means comprises chrominance and luminance difference energy determination means.

18. The apparatus of claim 16 wherein the scene change detection means comprises luminance difference energy determination means.

19. The apparatus of claim 16 wherein the scene change detection means comprises chrominance difference energy determination means.

20. The apparatus of claim 16 wherein the sequence of images is encoded according to the CCITT standard H.261 (International Consultative Committee on Telephony and Telegraphy).