Method and apparatus for variable accuracy inter-picture timing specification for digital video encoding

(74) Agent

<td> (54)</td><td>Designation</td><td>COMPUTER-READY STORAGE MEDIUM AND APPARATUS FOR CODING A MULTIPLE VIDEO IMAGE USING A SERIAL VALUE</td>

<td> (56)</td><td>cited publications</td><td>EP 1 014 729</td>

<td> (57)</td><td>Summary</td><td></td>

A method of decoding video images is provided, the method comprising receiving a plurality of encoded video images and an integer value which is a value of an exponent of a power of two, said exponent of decoding a sequence value representing a display position for a specific video image in a sequence of video images, and decoding that particular video image using the sequence value. Also provided is a decoder, comprising means for receiving a plurality of encoded video images and an integer value that is a value of one exponent of power of two, said exponent for decoding a sequence value representing a display position for a particular video image in a sequence of video images, and means for decoding the particular video image using the sequence value.

<img file="NO342829B1_D0001.tif" />

Technical area

The present invention relates to multimedia compression systems. In particular, the present invention provides methods and systems for specifying intermediate image timing with variable accuracy.

Known technique

Digitally based electronic media formats are definitely in the process of replacing analog electronic media formats to a large extent. Digital CDs have long replaced analog vinyl records. Analog magnetic cartridges are becoming rare. Second and third generation digital audio systems, such as mini-discs and MP3 (MPEG audio layer 3) are now taking market share from the first generation audio format to the CD.

Video media has been slower to move to digital storage and transfer formats than audio. This has largely been due to the massive amount of digital information required to accurately represent video in digital form. The massive amounts of digital information needed to accurately represent video require very high capacity digital storage systems and high bandwidth transmission systems.

However, video is now moving quickly into digital storage and transfer formats. Faster computer processors, high density storage systems and new efficient compression and coding algorithms have finally led to digital video becoming available at consumer prices. DVD (Digital Versatile Disc), a digital video system, has been one of the fastest selling consumer electronics products in many years. DVDs have rapidly displaced video cassette recorders (VCRs) as the chosen pre-recorded video playback system due to their high video quality, very high audio quality, convenience and other features. The outdated analogue NTSC (National Television Standards Committee) video transmission system is now being replaced with the digital ATSC (Advanced Television Standards Committee) video transmission system.

European Patent Application EP 1014729 A2, entitled "Apparatus and method for time stamping using time base and time increment resolution", describes a system and method for encoding a coded representation of the presentation page for an audiovisual sequence with a dynamic time base resolution range. The method provides instances of audiovisual sequences by temporal sampling and determining a local time base for instances of the sequences to be encoded into compressed data.

Computer systems have used various digital video coding formats for a number of years. Among the best digital video compression and coding systems used by computer systems have been the digital video systems supported by the Motion Pictures Expert Group, commonly known by the acronym MPEG. The three most well-known and most widely used digital video formats from MPEG are simply known as MPEG-1,

MPEG-2 and MPEG-4. Video CDs (VCDs) and early-consumption digital video editing systems use the early MPEG-1 digital video coding format. DVDs and DBS (Dish Network Brand Direct Broadcast Satellite Television Broadcasting System use the higher quality MPEG-2 digital video compression and coding system. The MPEG-4 coding system is quickly adapted by the latest computer-based digital video coders and associated digital video players.

The MPEG-2 and MPEG-4 standards compress a series of video frames or video fields and then encode the compressed frames or fields to a digital bit stream. When a video frame or field is encoded with MPEG-2 and MPEG-4 systems, the video frame or field is divided into a rectangular grid consisting of macro blocks. Each macro block is compressed and coded independently.

When a video frame or field is compressed, the MPEG-4 standard can compress the frame or field one-way predictable frames (P frames) or two-way predicted frames (B frames). Intra-frames encode an independent video frame, completely independent without reference to other video frames. P frames define a video frame with reference to a single previously displayed video frame. B-frames define a video frame with reference to both a video frame shown before the current frame and a video frame to be displayed after the current frame. Because of their respective use of redundant video information, Prams and B-frames generally provide best compression.

Summary of the Invention

A method and apparatus for intermediate image timing specification with variable accuracy for digital video coding are shown. In particular, the present invention provides a system which allows the relative timing of nearby video images to be encoded in a highly efficient manner. In one embodiment, the display time difference is determined between a current video image and a neighboring video image. The display time difference is then encoded into a digital representation of the video image. In a preferred embodiment, the adjacent video image is the most recently transferred stored image.

For coding efficiency, the display time difference can be coded using a variable length coding system or arithmetic coding. In an alternate embodiment, the display time difference is coded as a power of two to reduce the number of bits transmitted.

The invention is set out in the claims.

Other objects, features and advantages of the present invention will become apparent from the accompanying drawings and from the following detailed description.

Description of the drawings

The objects, features and advantages of the present invention will be apparent to those skilled in the art by looking at the following detailed description wherein:

Fig. 1 illustrates a high-level block diagram of a possible embodiment of a digital video coding system.

Fig. 2 illustrates a series of video images in the order in which the images should be displayed where the arrows linking different images indicate the intermediate image dependence formed by using motion compensation.

FIG. 3 illustrates the video images of FIG. 2 listed in a preferred transfer order of images where the arrows link different images indicating intermediate image dependence formed using motion compensation.

Fig. 4 graphically illustrates a series of video images in which the distances between video images referring to each other are chosen to be the powers of two.

Detailed description

A method and system for specifying intermediate image timing with variable accuracy in a multimedia compression and coding system are shown. In the following description, for explanatory purposes, specific terminology will be determined to provide a good understanding of the present invention. However, it will be apparent to one of ordinary skill in the art that these specific details are not required to practice the present invention. Eg. the present invention has been described with reference to the MPEG-4 multimedia compression and coding system. However, the same techniques can easily be used with other types of compression and coding systems.

Overview of multimedia compression and coding

FIG. 1 illustrates a high-level block diagram of a typical digital video encoder 100 of a well-known type. The digital video encoder 100 receives an incoming video stream of video frames 105 to the left of the block diagram. Each video frame is processed by a Discrete Cosine Transformation DCT 110. The frame can be processed independently (an intra-frame) or with reference to information from other frames received from the motion compensation unit (a middle frame). Then, a quantifier (Q) 120 quantifies the information from DCT 110. Finally, the quantified video frame is encoded with an entropy coding unit (H) 180 to produce an encoded bit stream.

The entropy coding unit 180 can use a variable length coding system (VLC).

Since a mid-frame encoded video frame is defined with reference to other nearby video frames, the digital video encoder 100 needs to form a copy of where the decoded each frame will appear in a digital video decoder so that the middle frames can be encoded. Thus, the lower part of the digital video encoder 100 is actually a digital video decoder system. In particular, an inverse quantum exchange unit 130 (Q¹) quantification of the value frame information and an inverse discrete cosine transformation unit 140 (DCT¹) reverses the discrete cosine transformation of the value frame formation. After all DCT purchase rates have been reconstructed from the rDCT, the motion compensation unit uses the information together with the motion vectors to reconstruct the encoded frame which is then used as the reference frame for the motion stream of the next frame.

The decoded value frame can then be used to encode intermediate frames (P frames or B frames) defined relative to the information of the decoded value frame. Specifically, a motion compensation unit 150 (MC) and a motion stressing unit 160 (ME) are used to determine the motion vectors and generate drift-clean values ​​used to encode the intermediate frames.

A speed controller 190 receives information from many different components of a digital value codec 100 and uses the information to allocate a target budget for each video frame. The Speed ​​Controller 190 should allocate the broad budget in a way that generates the highest quality of the digital value stream that is consistent with a specified set of restrictions. In particular, the speed controller 190 attempts to generate the highest possible quality of the compressed value stream without overflow buffers (exceeding the amount of available memory in a decoder by sending more information than can be stored) or underflow buffers (not sending value frames fast enough for a decoder to run out of frame values which should appear).

Overview of multimedia compression and coding

In some video signals, the time between subsequent video frames (frames or fields) is not necessarily constant. (Note: this document turns on the concept of video images to generally refer to value frames or value fields). Eg. some video images may be dropped because the transmission bandwidth is limited. Furthermore, the value stream may also vary due to the camera regularity or special effects such as slow film or fast film. In some streams of streams, the original video source may simply have row-shaped mid-size wires based on design. Eg. synthesized video, such as computer graphics events, may have some form of timing since no arbitrary value formation is formed by an unformed value recording system such as a value camera system. A flexible digital value encoding system should be able to handle range-transform timing.

Many digital word encryption systems split video images into a rectangular grid of macro blocks. Each individual macro block from the video image is independently compressed and coded. In some embodiments, subblocks of macroblocks, known as pruning blocks, are used. Such barriers may have their own motion vectors that can be interpolated. This document does not refer to tri macroblocks although the present invention can be applied in the same way to macroblocks and pixel blocks.

Some video coding standards, such as The ISO MPEG standards or the ITU H.264 standard, use various types of predictable macro blocks to encode video images. In a scenario, the macroblocks can be one of three types:

1. I macro block - an intra (I) macro block uses no information from other video images in its encoding (it is completely self-defined);

2. P macroblock - a one-way predictable macroblock (P) refers to image information from a preceding video image; or

3. B macro block - a two-way predictable (B) macro block uses information from a previous image and a future video image.

If all the macroblocks in a video image are intra-macroblocks, then the video image is an intra-frame. If a video image only includes one-way predictable macro blocks or intra-macro blocks, then the video image is known as a P frame. If the video image contains any two-way predictable macro blocks, then the video image is known as a B-frame. For simplicity, this document will consider the case where all macroblocks in a given image are of the same type.

An example sequence of video images to be encoded can be represented as

I1B2B3B4P5B6B7B8B9P10B11P12B13I14 ... where the letters (I, P or B) represent whether the video image is an I frame, P frame or B frame and the number represents the camera order of the video image in the sequence of video images. The camera order is the order in which a camera captures the video images and in this way is also the order in which the video images should be displayed (display order).

The previous example series of video images is graphically illustrated in FIG. 2. Referring now to FIG. 2, where the arrows indicate that the macroblocks from a stored image (I frame or P frame in this case) are used in the motion compensated prediction of other images.

In the scenario of FIG. 2, no information from other images is used in the encoding of the intra-frame video image Ii. The video image P5 is a P frame that uses video information from the previous video image Ii in its encoding, so that an arrow is drawn from the video image Ii to the video image P5. The video image B2, the video image B3, the video image B4 use all information from both the video image Ii and the video image P5 in their coding so that the arrows are drawn from the video image Ii and the video image P5 to the video image B2, the video image B3 and the video image B4. As mentioned above, the intermediate frame times are generally not the same.

Since the B images use information from future images (images that will be shown later, the transfer order is usually different from the display order. In particular, video images needed to construct other video images should be transferred first.

I1P5B2B3B4P10B6B7B8B9P12B11I14B13 ...

FIG. 3 graphically illustrates the transfer order above of the video images of FIG. 2. Again, the arrows in the figure indicate that macro blocks from a stored video image (I or P in this case) are used in the motion compensated prediction of other video images.

Referring now to FIG. 3, wherein the system first transmits the I frame Ii which does not depend on any other frame. Then, the system transmits the P-frame video image P5 which depends on the video image Ii. Then, the system transmits the B-frame video image B2 to the video image P5, although the video image B2 will be displayed before the video image P5. The reason for this is that when it comes time to decode B2, the decoder will already have received and stored the information in the video images Ii and P5, which is necessary to decode the video image B2. Similarly, video images Ii and P5 are ready to be used to decode the subsequent video image B3 and video image B4. The receiver / decoder sorts the video image sequence for proper display. In this operation, the I and P images are often referred to as stored images.

The encoding of the P-frame images usually utilizes motion compensation, where a motion vector is calculated for each macro block in the image. By using the calculated motion vector, a prediction macroblock (P macroblock) can be formed by translating pixels in the above-mentioned previous image. The difference between the current macro block in the P frame image and the prediction macro block is then coded for transmission.

Each motion vector can also be transmitted via predictive coding. Eg. For example, a motion vector prediction can be formed by using nearby motion vectors. In such a case, the difference between the current motion vector and the motion vector prediction for transmission is encoded.

Each B macro block uses two motion vectors: a first motion vector referring to a previous video image mentioned above and a second motion vector referring to the future video image. From these two motion vectors, two prediction macroblocks are calculated. The two predicted macro blocks are then combined together using a function to form a final predicted macro block. As above, the difference between the current macroblock in the Bram image is encoded and the final predicted macroblock for transmission.

As with P macro blocks, each motion vector (MV ) of a B macro block can be transmitted via predictive coding. In particular, a predicted motion vector is formed by using nearby motion vectors. Then, the difference between the current motion vector and the predicted for transmission is coded.

However, at B macroblocks, there is a possibility of interpolating motion vectors from motion vectors in the nearest stored image macroblock. Such interpolation is performed both in the digital video encoder and in the digital video decoder.

This motion vector interpolarization works particularly well on video images from a video sequence where a camera is slowly panning over a stationary background.

In fact, such a motion vector interpolarization may be sufficient to be used alone. Specifically, this means that no different information needs to be calculated or transmitted for these B macroblock motion vectors encoded using interpolarization.

To further illustrate the scenario above, let's represent the interpolation display time between images i and j as Dij, i.e. if the display times of the images are Ti and Tj respectively, then

Dij = Ti - Tj from which it follows that

Di, k - Dij + Dj.k Di, k = -Dkj

Note that Dij may be negative in some cases.

In this way, if MVs.i is a motion vector for a Ps macro block referring to l1, then the motion vector referred to as l1 and P5 respectively for the corresponding macroblocks in B2, B3 and B4 will be interpolated by

- M ¥ si * S3, s / 2s.i = f4V₅, 3. * D5 / i&gt;_S, L

MV-j j «iv-T / TiA ,:

ms? -, / ru Note that since the ratios between the display times are used for motion vector prediction, absolute display times are not needed. In this way, relative display times can be used for Dij display time values.

This scenario can be generalized, such as e.g. in the H.264 standard. In generalization, a P or B image may use any previous image for its motion vector prediction. In this way, the image B in the above case can use the image 1i and the image B₂ in his prediction. Furthermore, the motion vectors can be extrapolated, not just interpolated. In this way, in this case we will be able to have:

M? j, j -. i * Ds, i / D2 342829

Such a motion vector extrapolation (or interpolation) can also be used in the prediction process for predictive coding of motion vectors.

In any case, in the case of non-uniform intermediate image times, the problem is to transfer the relative display time values ​​of Dij to the receiver, and it is the object of the present invention. In one embodiment of the present invention, for each image after the first image, the display time difference between the current image and the most recently transferred stored image is transmitted. For fault tolerance, the transfer can be repeated several times within the image, e.g. in the so-called slice headers of the MPEG or H.264 standard. If all disk headers are lost, then presumably other images that depend on the lost image for decoding information cannot be decoded.

In this way, in the scenario above, we will transfer the following:

Dys Dys Djy Ehy Ds &amp; s EXs.se Dj.sb Dyic Dym Efo, ε&gt;_;

L&gt; M.S2 Djj ...

For the purpose of motion vector estimation, the accuracy requirements for Dij may vary from image to image. Eg. if there is only a single B-frame image Βό halfway between two P-frames P5 and P7, then it is sufficient to send:

D7.5 = 2 And Then, 7 = -1 where Dij display time values ​​are relative time values. If the video image Βό is only one quarter of the distance between the video image P5 and the video image P7, then the appropriate Dij display time values ​​to be sent are:

D7.5 = 4 and De, 7 = -1

Note that in both of the above examples, the display time between a video image Βό and video image P7 is used as the display unit "unit" and the display time difference between the video image P5 and the video image P7 is four display time "units".

In general, motion vector estimation is less complex if the divisors are the powers of two. This is easily achieved in our embodiment if Dij (the intermediate frame time) between two stored images is chosen to be a power of two as graphically illustrated in FIG. 4. Alternatively, the estimation procedure can be defined to truncate or round all divisors to a power of two.

In the case where an intermediate image time is a power of two, the number of data bits can be reduced only if the integer potential (of two) is transferred instead of the full value to the intermediate image time. Fig. 4 graphically illustrates a case where the distances between the images are chosen to be the powers of two. In such a case, D3, in the display time value of 2, is transferred between the video image Pi and the video image P3 as 1 (page 2¹ = 2) and D7.3 display time value of 4 between video image P7 and video image P3 can be transferred as 2 (since 2² = 4).

In some cases, motion vector interpolation cannot be used. However, it is still necessary to transfer the display order to the video images of the receiver / playback system so that the receiver / playback system will display the video images in the correct order. In this case, simple plotted integer values ​​for Dij will suffice with respect to the current display times. In some applications only the sign is needed.

The intermediate image times Dij can be easily transferred as simple character integer values. However, many methods can be used to encode the Dij values ​​to achieve extra compression. Eg. is a character bit followed by a variable length-coded size relatively easy to implement and provides coding efficiency.

One such variable length coding system that can be used is known as Universal Variable Length Code (UVLC). The UVLC variable length coding system is given by the following password:

= 0 10 = Oil '= 0 0 10 0

<img file="NO342829B1_D0002.tif" />

Another method of encoding the middle frame may be to use arithmetic coding. Usually, arithmetic coding utilizes conditional probabilities to cause a very high compression of data bits.

In this way, the present invention introduces a simple but effective method of encoding and transmitting intermediate image viewing times. The coding of the intermediate image display times can be done very efficiently using variable length coding or arithmetic coding. Furthermore, a desired accuracy can be selected to meet the needs of the video decoder, but no more.

The foregoing has described a system for specifying intermediate image timing with variable accuracy in a multimedia compression and coding system. It is contemplated that changes and modifications may be made by one skilled in the art, on the materials and arrangement of the elements of the present invention without departing from the scope of the invention.

Methods and coding systems as defined in the set of numbered aspects below also form part of the present disclosure. The numbered aspects should not be confused with patent claims.

Aspect 1. Method for specifying digital video information, the method comprising:

determining a first display time difference between a first video image and a neighboring video image; and encoding the first video image and the first display time difference in a first digital video image.

Aspect 2. A method according to aspect 1, the method further comprising:

transmission of the first video image and the first display time difference.

Aspect 3. Method according to aspect 1, wherein the adjacent video image comprises a most recently transferred stored image.

Aspect 4. Method according to aspect 1, wherein the first display time difference is encoded in a disk header.

Aspect 5. A method according to aspect 1, wherein the first display time difference is coded more than once in the first digital video image.

Aspect 6. Method according to aspect 1, wherein the first display time difference comprises a relative time value.

Aspect 7. Method according to aspect 1, wherein the first display time difference is coded as a power of two.

Aspect 8. Method according to aspect 1, wherein the first display time difference is encoded with variable length coding.

Aspect 9. Method according to aspect 1, wherein the first display time difference is encoded with arithmetic coding.

Aspect 10. A method according to aspect 1, wherein the first display time difference comprises a plotted integer.

Aspect 11. Encoding system for encoding digital video information, wherein the digital encoding system comprises:

a first digital video image containing a coding of a first video image; and a first display time difference, wherein the first display time difference specifies a difference between a display time of the first video image and a display time of a nearby video image.

Aspect 12. Encoding system according to aspect 11, wherein the first display time difference is encoded in the first digital video image.

Aspect 13. Encoding system according to claim 11, wherein the adjacent video image comprises the most recently transferred stored image.

Aspect 14. Encoding system according to aspect 11, wherein the first display time difference is encoded in a disk header of the first digital video image.

Aspect 15. Encoding ssy voice according to aspect 11, wherein the first display time difference is coded more than once in the first digital video image.

Aspect 16. Encoding system according to aspect 11, wherein the first display time difference comprises a relative time value.

Aspect 17. Encoding sys voice according to aspect 11, where the first display time difference is coded as a factor of two.

Aspect 18. Encoding system according to aspect 11, wherein the first display time difference is encoded with variable length encoding.

Aspect 19. Encoding sys voice according to aspect 11, wherein the first display time difference is encoded with arithmetic coding.

Aspect 20. Encoding ssy voice according to aspect 1, wherein the first display time difference comprises a plotted integer.

Aspect 21. Computer readable storage medium storing a bit stream, said bit stream comprising:

a plurality of encoded video images; and an integer exponent value of a power of two for encoding a display order value for a particular video image, wherein at least one of the plurality of video images is encoded using the sequence value.

Aspect 22. Computer readable storage medium according to aspect 21, wherein the sequence value is encoded in a disk header in the bitstream.

Aspect 23. Computer-readable storage medium according to aspect 21, wherein the sequence value represents a time difference between the particular video image and a reference image.

Aspect 24. Computer-readable storage medium according to aspect 23, wherein the reference image is an I-video image that does not include unidirectional or bidirectional predicted macro blocks.

Aspect 25. Computer-readable storage medium according to aspect 21, wherein the particular video image is a B-video image comprising at least one bidirectional predicted macro block.

Aspect 26. Computer-readable storage medium according to aspect 21, wherein the sequence value is an integer that is a power of two.

Apparatus for encoding a plurality of video images, the apparatus comprising:

means for specifying a plurality of sequence values, each sequence value representing a display position of a video image in a sequence of video images;

means for encoding a particular sequence value using a value of an exponent 5 of a power of two; and means for encoding a particular video image using the particular sequence value.

Aspect 28. Apparatus according to aspect 27, further comprising means for encoding the particular sequence value in a disk header for the encoded particular video image.

Aspect 29. Apparatus according to aspect 27, wherein the sequence value represents a time difference between the particular video image and a reference image.

Aspect 30. Apparatus according to aspect 29, wherein the reference image is an I-video image that does not include unidirectional or bidirectional predicted macro blocks.

Aspect 31. Apparatus according to aspect 27, wherein the particular video image is a B-video image comprising at least one bidirectional predicted macro block.

Aspect 32. Apparatus according to aspect 27, wherein the sequence value is an integer that is a power of two.