Decoding method

Technical Field

The present invention relates to a a decoding method of performing decompression and decoding of compressed moving picture data by motion compensated prediction.

Background Art

A prior art document by <nplcit id="ncit0001" npl-type="s"><text>Takahiro Fukuhara, et al.: "Very low Bit-Rate Video Coding with Block Partitioning and Adaptive Selection of Two Time-Differential Frame Memories"; IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, Vol. 7 No. 1; February 1997</text></nplcit> discloses motion compensated prediction by block partitioning prediction and utilizing two time differential reference frames <patcit id="pcit0001" dnum="US5825423A"><text>US5825423</text></patcit> addresses the problem of representing different motions existing in one block and discloses estimating motion vectors by using a set of moving object patterns.

The image coding and decoding method based on the H.26L coding method is known as a case example of the conventional video coding methods, which is described in International Standardization Working Document ITU-T SG16 VCEG-M81, "H.26L Test Model Long Term Number 7 (TML-7)" draft0 (http://standard.pictel.com/ftp/video-site/0104_Aus/VCEG-M81d0.doc).

In this H.26L video coding, many motion division patterns shown in <figref idref="f0004">Fig. 4A to Fig. 4G</figref> are prepared as inter prediction modes so as to enable elaborate motion compensation. This ingenuity presents such effect that it is feasible to efficiently capture motions in a case where fine motions occur inside macroblocks, and to increase prediction efficiency.

However, the method of preparing the many motion division patterns as inter prediction modes has the problem that more motion vector information needs to be transmitted with increase in the number of motion divisions, so as to result in increase of the overhead. <figref idref="f0005">Fig. 5</figref> shows the volume of transmitted information necessary for each of the modes of <figref idref="f0004">Fig. 4A to Fig. 4G</figref>. In this <figref idref="f0005">Fig. 5</figref> "mode bit" represents a code length of a variable length code for expressing each prediction mode, "minimum motion vector bit" represents the minimum information amount that can be taken as the amount of information about motion vectors to be transmitted in each macroblock unit, and "minimum requisite bit count" represents the sum of the mode bit and the minimum motion vector bit. The motion vector bit is the total bit count of two values in the horizontal and vertical directions, and the case yielding the minimum is one wherein the motion vector agrees with a motion vector predicted value in both the horizontal and vertical directions (a predicted value of a motion vector is calculated from near motion vectors according to a predetermined rule and the difference between the motion vector value and the motion vector predicted value is coded). However, that is normally a rare case, and it is necessary to transmit more information than the bit count. It is seen from this <figref idref="f0005">Fig. 5</figref> that the overhead becomes very large in Mode 4 or 5 or higher.

On the other hand, in the case of ordinary images, it is believed that there exist cases wherein sufficient motion compensation can be achieved by a comprehensive way of capturing the motions by division into two segments or so, without elaborate motion detection based on segmentalization of each macroblock region into four or more segments. However, the fixed motion assignment in the 16x8 and 8x16 pixel units prepared in the H.26L coding method had the problem that it was not possible to accurately express motion divisions inside each macroblock, which was the reason why the seven inter prediction modes of <figref idref="f0004">Fig. 4A to Fig. 4G</figref> were prepared.

The present invention has been accomplished in order to solve the above problem and an object of the present invention is to provide a decoding method and a decoding program enabling coding or decoding of motion information in a picture with the overhead being small.

Disclosure of the Invention

In order to achieve the above object, a decoding method of performing decompression and decoding of compressed moving picture data by motion compensated prediction is provided in accordance with claim 1.

The above object and other features and advantages of the present invention will become apparent to those skilled in the art by referring to the following detailed description with reference to the accompanying drawings.

Brief Description of the Drawings

<ul id="ul0001" list-style="none" compact="compact"><li><figref idref="f0001">Fig. 1</figref> is a configuration diagram of a coding apparatus.</li><li><figref idref="f0002">Fig. 2</figref> is a configuration diagram of a decoding apparatus.</li><li><figref idref="f0003">Fig. 3A</figref> is a diagram showing the contents of a previous frame used in the description of motion compensated inter prediction.</li><li><figref idref="f0003">Fig. 3B</figref> is a diagram showing the contents of a present frame used in the description of motion compensated inter prediction.</li><li><figref idref="f0004">Fig. 4A</figref> is a diagram showing Mode 1 among the inter prediction modes in H.26L.</li><li><figref idref="f0004">Fig. 4B</figref> is a diagram showing Mode 2 among the inter prediction modes in H.26L.</li><li><figref idref="f0004">Fig. 4C</figref> is a diagram showing Mode 3 among the inter prediction modes in H.26L.</li><li><figref idref="f0004">Fig. 4D</figref> is a diagram showing Mode 4 among the inter prediction modes in H.26L.</li><li><figref idref="f0004">Fig. 4E</figref> is a diagram showing Mode 5 among the inter prediction modes in H.26L.</li><li><figref idref="f0004">Fig. 4F</figref> is a diagram showing Mode 6 among the inter prediction modes in H.26L.</li><li><figref idref="f0004">Fig. 4G</figref> is a diagram showing Mode 7 among the inter prediction modes in H.26L.</li><li><figref idref="f0005">Fig. 5</figref> is a table showing the minimum transmitted information amount necessary for each Mode of the inter prediction modes.</li><li><figref idref="f0006">Fig. 6A</figref> is a diagram showing a first group of fixed division patterns in an embodiment of the invention.</li><li><figref idref="f0006">Fig. 6B</figref> is a diagram showing a second group of fixed division patterns in an embodiment of the invention.</li><li><figref idref="f0006">Fig. 6C</figref> is a diagram showing a third group of fixed division patterns in an embodiment of the invention.</li><li><figref idref="f0006">Fig. 6D</figref> is a diagram showing a fourth group of fixed division patterns in an embodiment of the invention.</li><li><figref idref="f0007">Fig. 7A</figref> is a diagram showing a case where a present macroblock is Mode 1 and the left, upper, and right upper macroblocks thereof are Modes 0, 1, and 8, respectively.</li><li><figref idref="f0007">Fig. 7B</figref> is a diagram showing a case where the upper macroblock uses a reference frame different from that of the present macroblock.</li><li><figref idref="f0008">Fig. 8A</figref> is a diagram for explaining the flow of motion vector predicted value determining processing in a case of Mode 0.</li><li><figref idref="f0008">Fig. 8B</figref> is a diagram for explaining the flow of motion vector predicted value determining processing in a case of Mode 1.</li><li><figref idref="f0008">Fig. 8C</figref> is a diagram for explaining the flow of motion vector predicted value determining processing in a case of Mode 7.</li><li><figref idref="f0009">Fig. 9</figref> is a table showing an example of upper priorities and left priorities defined for each of the prediction modes in consideration of continuity of motion from neighboring macroblocks.</li><li><figref idref="f0010">Fig. 10A</figref> is a diagram showing predicted values of motion vectors fixedly given to each prediction mode in the first group of fixed division patterns.</li><li><figref idref="f0010">Fig. 10B</figref> is a diagram showing predicted values of motion vectors fixedly given to each prediction mode in the second group of fixed division patterns.</li><li><figref idref="f0010">Fig. 10C</figref> is a diagram showing predicted values of motion vectors fixedly given to each prediction mode in the third group of fixed division patterns.</li><li><figref idref="f0010">Fig. 10D</figref> is a diagram showing predicted values of motion vectors fixedly given to each prediction mode in the fourth group of fixed division patterns.</li><li><figref idref="f0011">Fig. 11A</figref> is a diagram showing a syntax of macroblock data of a compressed stream in H.26L.</li><li><figref idref="f0011">Fig. 11B</figref> is a diagram showing a syntax of macroblock data of a compressed stream in the first embodiment.</li><li><figref idref="f0012">Fig. 12</figref> is a flowchart showing the processing contents of the decoding apparatus in the first embodiment.</li><li><figref idref="f0013">Fig. 13A</figref> is a diagram showing a first definition example of a prediction mode expressed as 4×4 binary map information for designating an arbitrary assignment situation.</li><li><figref idref="f0013">Fig. 13B</figref> is a diagram showing a second definition example of a prediction mode expressed as 4×4 binary map information for designating an arbitrary assignment situation.</li><li><figref idref="f0013">Fig. 13C</figref> is a diagram showing a third definition example of a prediction mode expressed as 4×4 binary map information for designating an arbitrary assignment situation.</li><li><figref idref="f0014">Fig. 14</figref> is a diagram showing a procedure of motion vector detection in the second embodiment.</li><li><figref idref="f0015">Fig. 15</figref> is a diagram showing another procedure of motion vector detection.</li><li><figref idref="f0016">Fig. 16A</figref> is a diagram for explaining an example where the degree of continuity of motion from macroblock A is high, among the coding methods of prediction mode information in the second embodiment.</li><li><figref idref="f0016">Fig. 16B</figref> is a diagram for explaining an example where the degree of continuity of motion from macroblock B is high, among the coding methods of prediction mode information in the second embodiment.</li><li><figref idref="f0017">Fig. 17</figref> is a flowchart showing the contents of the coding processing in the second embodiment.</li><li><figref idref="f0018">Fig. 18A</figref> is a table showing an example of code length CB(4).</li><li><figref idref="f0018">Fig. 18B</figref> is a table showing an example of code length CB(3).</li><li><figref idref="f0018">Fig. 18C</figref> is a table showing an example of code length CB(2).</li><li><figref idref="f0019">Fig. 19A</figref> is a diagram showing a syntax of macroblock data of a compressed stream in H.26L.</li><li><figref idref="f0019">Fig. 19B</figref> is a diagram showing a simplest syntax example of macroblock data of a compressed stream in the second embodiment.</li><li><figref idref="f0019">Fig. 19C</figref> is a diagram showing another syntax example of macroblock data of a compressed stream in the second embodiment.</li><li><figref idref="f0020">Fig. 20</figref> is a flowchart showing the processing contents of the decoding apparatus in the second embodiment.</li><li><figref idref="f0021">Fig. 21</figref> is a flowchart showing the processing contents of the coding apparatus in the third embodiment.</li><li><figref idref="f0022">Fig. 22</figref> is a diagram to explain the processing contents of the coding apparatus in the third embodiment.</li><li><figref idref="f0023">Fig. 23A</figref> is a diagram showing an example of zigzag scan of a scan table.</li><li><figref idref="f0023">Fig. 23B</figref> is a diagram showing an example of horizontal scan of a scan table.</li><li><figref idref="f0023">Fig. 23C</figref> is a diagram showing an example of Hilbert scan of a scan table.</li><li><figref idref="f0024">Fig. 24A</figref> is a diagram showing a definition example of a prediction mode wherein discrimination of intra/inter is made along a diagonal direction and two motion vectors are used in an inter predicted segment in the fourth embodiment.</li><li><figref idref="f0024">Fig. 24B</figref> is a diagram showing a definition example of a prediction mode in which a macroblock is divided into upper and lower segments, the upper segment being predicted by intra prediction while the lower segment by inter prediction, in the fourth embodiment.</li><li><figref idref="f0025">Fig. 25A</figref> is a diagram showing a plane of intra/inter classification.</li><li><figref idref="f0025">Fig. 25B</figref> is a diagram showing planes of intra prediction methods.</li><li><figref idref="f0025">Fig. 25C</figref> is a diagram showing a plane of motion vector assignment.</li><li><figref idref="f0026">Fig. 26A</figref> is a diagram showing a plane of intra/inter classification.</li><li><figref idref="f0026">Fig. 26B</figref> is a diagram showing planes of intra prediction methods where only sub-blocks corresponding to intra or inter prediction are converted into bit plane data.</li><li><figref idref="f0026">Fig. 26C</figref> is a diagram showing a plane of motion vector assignment where only sub-blocks corresponding to intra or inter prediction are converted into bit plane data.</li><li><figref idref="f0027">Fig. 27</figref> is a diagram showing an example in which the case of <figref idref="f0024">Fig. 24A</figref> is converted by the coding method 2 in the fourth embodiment.</li><li><figref idref="f0028">Fig. 28</figref> is a diagram showing a syntax of macroblock data of a compressed stream corresponding to the coding method 1 in the fourth embodiment.</li><li><figref idref="f0029">Fig. 29</figref> is a diagram showing a syntax of macroblock data of a compressed stream corresponding to the coding method 2 in the fourth embodiment.</li><li><figref idref="f0030">Fig. 30</figref> is a diagram showing a syntax of macroblock data of a compressed stream corresponding to the coding method 3 in the fourth embodiment.</li><li><figref idref="f0031">Fig. 31</figref> is a diagram showing a syntax of macroblock data of a compressed stream corresponding to the coding method 4 in the fourth embodiment.</li><li><figref idref="f0032">Fig. 32A</figref> is a diagram showing a definition example of a prediction mode set using the minimum number of prediction modes.</li><li><figref idref="f0032">Fig. 32B</figref> is a diagram showing a definition example of a prediction mode set using the smaller number of motion vectors presented in the first embodiment.</li><li><figref idref="f0032">Fig. 32C</figref> is a diagram showing a definition example of a prediction mode set using many divisions and many motion vectors.</li><li><figref idref="f0033">Fig. 33A</figref> is a table showing a code configuration of reference frame information in H.26L.</li><li><figref idref="f0033">Fig. 33B</figref> is a table showing an example of codes assigned to combinations of reference frame information.</li><li><figref idref="f0033">Fig. 33C</figref> is a diagram showing a syntax of macroblock data corresponding to <figref idref="f0033">Fig. 33B</figref>.</li><li><figref idref="f0034">Fig. 34A</figref> is a table showing codes switched according to the predicted value in the case where a value before a change or a predicted value was 0.</li><li><figref idref="f0034">Fig. 34B</figref> is a table showing codes switched according to the predicted value in the case where the predicted value was 4.</li><li><figref idref="f0035">Fig. 35A</figref> is a diagram showing a division example of a macroblock for explaining promotion of efficiency in coding of orthogonal transform coefficient data.</li><li><figref idref="f0035">Fig. 35B</figref> is a diagram showing an example of transmitting the presence or absence of a significant coefficient in each 8x8 block unit.</li><li><figref idref="f0035">Fig. 35C</figref> is a diagram showing an example of transmitting the presence or absence of a significant coefficient in each segmental region.</li><li><figref idref="f0036">Fig. 36A</figref> is a diagram for explaining the motion vector detection processing in the case where adaptation is carried out for a motion vector search range in the fifth embodiment.</li><li><figref idref="f0036">Fig. 36B</figref> is a diagram for explaining the motion vector detection processing in the case where adaptation is not carried out for the motion vector search range in the fifth embodiment.</li><li><figref idref="f0037">Fig. 37A</figref> is a diagram for explaining a motion vector prediction rule about the first group of fixed division patterns in the fifth embodiment.</li><li><figref idref="f0037">Fig. 37B</figref> is a diagram for explaining a motion vector prediction rule about the second group of fixed division patterns in the fifth embodiment.</li><li><figref idref="f0037">Fig. 37C</figref> is a diagram for explaining a motion vector prediction rule about the third group of fixed division patterns in the fifth embodiment.</li><li><figref idref="f0037">Fig. 37D</figref> is a diagram for explaining a motion vector prediction rule about the fourth group of fixed division patterns in the fifth embodiment.</li><li><figref idref="f0038">Fig. 38</figref> is a flowchart showing the motion vector detection processing in the fifth embodiment.</li><li><figref idref="f0039">Fig. 39</figref> is a diagram showing an example of bidirectional prediction in the sixth embodiment.</li><li><figref idref="f0040">Fig. 40A</figref> is a diagram showing a syntax upon bidirectional motion compensated prediction in H.26L.</li><li><figref idref="f0040">Fig. 40B</figref> is a diagram showing a syntax of macroblock data of a compressed stream in the sixth embodiment.</li><li><figref idref="f0041">Fig. 41</figref> is a code table of macroblock type information in the sixth embodiment.</li><li><figref idref="f0042">Fig. 42</figref> is a code table of reference frame information in the sixth embodiment.</li><li><figref idref="f0043">Fig. 43</figref> is a flowchart showing the basic operation of the coding apparatus.</li><li><figref idref="f0044">Fig. 44</figref> is a flowchart showing the basic operation of the decoding apparatus.</li></ul>

Best Mode for Carrying out the Invention

Various embodiments of the present invention will be described below in order.

First, the first embodiment of the present invention will describe the video coding apparatus configured to implement coding in macroblock units, particularly, the video coding apparatus and decoding apparatus configured to perform the motion compensated prediction while assigning up to two motion vectors to sub-blocks obtained by dividing a macroblock in 4×4 pixel units.

The configurations and operations of the image coding and decoding apparatus based on the H.26L coding method to which the present invention is applied will be described below.

<figref idref="f0001">Fig. 1</figref> shows the configuration of the coding apparatus and <figref idref="f0002">Fig. 2</figref> the configuration of the decoding apparatus. In the coding apparatus of <figref idref="f0001">Fig. 1</figref>, information compression of video signal is implemented by reducing the redundancy present in the temporal direction by motion compensated inter prediction and further reducing the redundancy remaining in the spatial direction by orthogonal transform. <figref idref="f0003">Figs. 3A and 3B</figref> provide illustrations to explain the motion compensated inter prediction and <figref idref="f0004">Fig. 4A to Fig. 4G</figref> the scheme of the block matching processing. <figref idref="f0043">Fig. 43</figref> is a flowchart showing the basic operation of the coding apparatus and <figref idref="f0044">Fig. 44</figref> a flowchart showing the basic operation of the decoding apparatus.

The operations of the coding and decoding apparatus shown in <figref idref="f0001">Fig. 1</figref> and <figref idref="f0002">Fig. 2</figref> will be described below with reference to these drawings.

An input video signal 1 in <figref idref="f0001">Fig. 1</figref> is a time sequence of frame images, and in the description hereinafter it will represent a signal of a frame image unit. A frame image as a coding object is represented by a present frame 30B in <figref idref="f0003">Fig. 3B</figref>. The present frame 30B is divided into fixed square regions of 16 pixels × 16 lines (called macroblocks), and the following coding processing is carried out in each unit of a square region.

Each macroblock of the present frame 30B is first fed to motion detector 2, which performs determination of prediction mode 3 and detection of motion vectors 4 the number of which corresponds to the prediction mode determined. In the H.26L coding method, the prediction modes 3 prepared include an intra prediction mode of performing spatial prediction using coded neighboring pixels on the same space and a plurality of inter prediction modes of performing motion compensated prediction using a temporally different coded frame image (e.g., a previous frame 30A in <figref idref="f0003">Fig. 3A</figref>), and the coding scheme is arranged to switch between these modes in macroblock units according to local properties of the video signal so as to be able to perform efficient information compression.

Namely, in the flowchart of <figref idref="f0043">Fig. 43</figref>, the input video signal 1 is fed into the coding apparatus (S01), motion detection (S02) and motion compensation (S03) are then carried out, and spatial prediction (S04) described hereinafter is carried out by the spatial predictor 9.

The motion compensated prediction is a technique of searching a decoded image of the previous frame 30A for a signal pattern (predicted value) similar to an input image of the present frame 30B within a predetermined search range 32, detecting a spatial displacement amount in the form of a motion vector (e.g., detecting a spatial displacement amount of wheel 31 as a motion vector 33), and transmitting a predictive residual signal and the motion vector as coding information, as shown in <figref idref="f0003">Fig. 3A and Fig. 3B</figref>. H.26L provides the seven types of inter prediction modes as shown in <figref idref="f0004">Figs. 4A to 4G</figref>. More precisely, H.26L also provides a prediction mode of copying pixels (skip mode) at identical locations of the previous frame as they are, which is useful in the case of still images, but it will be omitted herein for convenience' sake of description. The motion vector is detected in a 16x16 pixel unit in Mode 1 of <figref idref="f0004">Fig. 4A</figref>, in each 8x16 pixel unit in Mode 2 of <figref idref="f0004">Fig. 4B</figref>, in each 16×8 pixel unit in Mode 3 of <figref idref="f0004">Fig. 4C</figref>, in each 8x8 pixel unit in Mode 4 of <figref idref="f0004">Fig. 4D</figref>, in each 4×8 pixel unit in Mode 5 of <figref idref="f0004">Fig. 4E</figref>, in each 8×4 pixel unit in Mode 6 of <figref idref="f0004">Fig. 4F</figref>, and in each 4×4 pixel unit in Mode 7 of <figref idref="f0004">Fig. 4G</figref>. These seven types of prediction modes enable segmentization of motion detection units inside the macroblock and are intended for accurately capturing various motions that can exist in the macroblock.

The motion detector 2 evaluates each macroblock as to all the inter prediction modes of <figref idref="f0004">Figs. 4A to 4G</figref> and selects a mode judged as one to present the highest coding efficiency. The coding efficiency is also evaluated similarly as to the intra prediction mode, and the intra prediction mode is selected if it provides the higher efficiency than the inter prediction modes. When an inter prediction mode is selected, it results in detecting and transmitting a motion vector or motion vectors 4 by the number defined in the prediction mode 3 selected (up to sixteen motion vectors per macroblock). No motion vector 4 is transmitted when the intra prediction mode is chosen.

When an inter prediction mode is chosen, the determined prediction mode 3 and motion vectors 4 are sent to motion compensator 5, which extracts a motion compensated predictive image 8 of each macroblock with reference to a coded image signal 7 of a previous frame in frame memory 6 with use of the motion vectors 4.

When the intra prediction mode is chosen, the spatial predictor 9 generates a predicted value 10 with reference to the neighboring coded image signal 7. A finally used, predicted value 11 is selected out of the motion compensated predictive image 8 and the predicted value 10 on the basis of the prediction mode 3, at switch 12.

A predictive residual signal 13 is generated as a signal indicating a difference between the foregoing predicted value 11 and input video signal 1 (S05 in <figref idref="f0043">Fig. 43</figref>), and the predictive residual signal 13 is fed to orthogonal transformer 14 to be transformed into orthogonal transform coefficients 15 by orthogonal transform (S06). The orthogonal transform coefficients 15 are fed to quantizer 16 to be converted into quantized orthogonal transform coefficients 17 by quantization (S07), and the quantized orthogonal transform coefficients 17 are fed to variable length encoder 23. Entropy coding is carried out herein to multiplex coded data on a compressed stream 24 (S08).

Although omitted from <figref idref="f0043">Fig. 43</figref>, the quantized orthogonal transform coefficients 17 are locally decoded via dequantizer 18 and inverse orthogonal transformer 19 on the other hand and the resultant is added to the predicted value 11 to yield a locally decoded image 20. The locally decoded image 20 is fed to loop filter 21 for removing degradation of block distortion and others on the boundary of the orthogonal transform block, and the loop filter 21 filters the boundary pixels to obtain a filtered, locally decoded image 22, which is put into the frame memory 6. The image data stored in the frame memory 6 is used as reference data 7 for the motion compensated prediction of subsequent frames.

The prediction mode 3 is also subjected to the entropy coding in each macroblock unit in the variable length encoder 23 and the resultant is multiplexed on the compressed stream 24 (S08). The compressed stream 24 yielded in this way is outputted (S09).

The operation of the decoding apparatus will be described next on the basis of <figref idref="f0002">Fig. 2</figref> and <figref idref="f0044">Fig. 44</figref>. In the decoding apparatus, the compressed stream 24 as coded data is first received (S21 in <figref idref="f0044">Fig. 44</figref>), variable length decoder 25 then detects a synchronization word indicating the head of each frame, and thereafter the prediction mode 3, motion vector(s) 4, and quantized orthogonal transform coefficients 17 are decoded in each macroblock unit (S22).

When the prediction mode 3 is an inter prediction mode (in the case of the affirmative judgment in S23), each motion vector 4 is fed to motion compensator 5 and the motion compensator 5 extracts an image portion having moved by the motion vector 4, as a motion compensated predictive image 8 from frame memory 26 (which is used in similar fashion to the frame memory 6) (S24), as in the case of the operation of the coding apparatus. On the other hand, when the prediction mode 3 is the intra prediction mode (in the case of the negative judgment in S23), the spatial predictor 9 generates the predicted value 10 with reference to the neighboring coded image signal 7 (S25).

In tandem with S23 to S25, dequantizer 18 dequantizes the predictive residual signal (S26) and inverse orthogonal transformer 19 performs inverse orthogonal transform (S27) in order, thereby generating a decoded value of the predictive residual signal.

On the other hand, a final predicted value 11 is determined according to the prediction mode 3 at switch 12, and it is added to the above decoded value of the predictive residual signal thus generated to yield a decoded image 20 (S28). It is further fed through loop filter 21 to obtain a final, decoded, reproduced image 22 (S29), and the reproduced image is outputted in predetermined display timing to a display device (S30) to reproduce the picture. The decoded, reproduced image 22 is also put into the frame memory 26 at the same time in order to be used in the motion compensation of subsequent frames. Here the image data 20, 22 takes the same values as the data of the same numbers in the coding apparatus.

The description will transfer to the detailed description of the present embodiment, and it is noted that the present embodiment is characterized by the definitions of the prediction modes 3 (particularly, the inter prediction modes) and motion vectors 4 included in the compressed stream 24 and the operations of the motion detector 2 and the motion compensator 5 in the aforementioned coding apparatus and decoding apparatus shown in <figref idref="f0001">Fig. 1</figref> and <figref idref="f0002">Fig. 2</figref>. For this reason, the description hereinafter will be given with focus on the operation of the motion detector 2 and the definitions of the prediction modes 3 and motion vectors 4 about the coding apparatus and with focus on the procedure of decoding the video signal from the prediction modes 3 and motion vectors 4 about the decoding apparatus.

① Definitions of fixed motion vector assignment patterns

The motion detector 2 evaluates each macroblock as to all the prediction modes prepared and detects a mode with the highest coding efficiency and a corresponding motion vector or motion vectors. In the H.26L coding method of the conventional example, the patterns shown in <figref idref="f0004">Figs. 4</figref> are investigated as the inter prediction modes, whereas the present embodiment employs a configuration wherein the fixed division patterns shown in <figref idref="f0006">Figs. 6A to 6D</figref> are prepared as inter prediction modes and a mode with the best coding efficiency is chosen among these, as a method of assigning up to two motion vectors in 4x4 block (sub-block) units. The reason why the patterns of <figref idref="f0006">Figs. 6A to 6D</figref> are used as the fixed division patterns is that it is expected that these patterns are of the highest usage frequency as a division rule, for dividing the interior of the macroblock into two segments. For example, a pattern in which vectors are assigned to a central region and a peripheral region is a case including an extremely local motion within 16 pixels × 16 lines, and such a case rarely occurs in images. On the other hand, the division patterns prepared in <figref idref="f0006">Figs. 6A to 6D</figref> indicate patterns in which a typical motion in the horizontal, vertical, or oblique direction is continuous to the outside of the macroblock, and it is expected that they have high usage frequency. In <figref idref="f0006">Figs. 6B to 6D</figref> among these, white regions and gray regions represent discrimination of motion vector assignment and permit the interior of the macroblock to be motion-divided in these patterns and to be subjected to the motion compensated prediction based thereon.

In Mode 0 of <figref idref="f0006">Fig. 6A</figref>, the macroblock (16×16 pixel) region is predicted by one motion vector. This is exactly the same definition as Mode 1 of the inter prediction modes in the H.26L coding method. In Modes 1 and 2 of <figref idref="f0006">Fig. 6B</figref>, the macroblock is divided into two regions of 16×8 pixels or 8×16 pixels, and these are also equivalent to Modes 2 and 3 in <figref idref="f0004">Figs. 4B and 4C</figref>. On the other hand, Mode 3 and the subsequent modes of <figref idref="f0006">Figs. 6C and 6D</figref> are mode definitions specific to the present embodiment, and Modes 3 to 6 of <figref idref="f0006">Fig. 6C</figref> permit uneven division of the macroblock in the horizontal and vertical directions. The uneven horizontal and vertical division is highly useful, particularly, at portions where a new image pattern gradually appears as at the screen edge. Furthermore, Mode 7 and the subsequent modes of <figref idref="f0006">Fig. 6D</figref> permit division of the interior of the macroblock in the oblique direction. The oblique division is highly useful in capturing discontinuity of motion along a boundary portion of an object or in predicting a new image pattern appearing from a screen corner. As described above, only two motion vectors are assigned in all the modes except for Mode 0 of <figref idref="f0006">Fig. 6A</figref>, and the preparation of the various motion division patterns enables motions in the macroblock that can not be captured by only even division like Modes 1 and 2 of <figref idref="f0006">Fig. 6B</figref>, to be accurately captured by the small number of motion vectors.

The grouping of Modes 0-14 of <figref idref="f0006">Figs. 6A to 6D</figref> into four groups (group G1 of <figref idref="f0006">Fig. 6A</figref>, group G2 of <figref idref="f0006">Fig. 6B</figref>, group G3 of <figref idref="f0006">Fig. 6C</figref>, and group G4 of <figref idref="f0006">Fig. 6D</figref>) indicates the difference in the amount of codes in transmission of each prediction mode. Since the present embodiment has the number of modes being twice the number of the H.26L prediction mode information of <figref idref="f0004">Figs. 4A to 4G</figref>, variable length coding by variable code length assignment is performed according to the number of divisions, the division direction, or the area ratio of divided regions in each mode, in order to implement efficient coding of the overhead. From the viewpoint of the number of divisions, the shortest code is first assigned to Mode 0 with the smallest number of motion vector and with the small overhead among all the modes. In general, video signals have very high temporal correlation, and thus the need for division of the interior of the macroblock according to motion is lower than in the case of the motion compensation (Motion Compensation: MC) in each macroblock unit. Concerning the bisected patterns, it is considered that the frequency of horizontal and vertical division patterns is higher than that of oblique division patterns, from the property of video signals. Furthermore, the code lengths of the even division are set shorter from the viewpoint that it is easy to reduce the average predictive residual power by MC in even block size and in units of the same area of the two segments. On the other hand, the uneven division is considered to suit uses where a new image pattern appears, particularly, at the screen edge and where a better prediction is made for an image pattern portion already existing in the frame. It is considered that the oblique division is suitable for uses where a motion that cannot be captured by only horizontal and vertical motions is captured on a contour of a moving object in an image and that the frequency of occurrence thereof is generally lower than those of the other modes.

However, this variable length coding method is nonunique, and, for performing the variable length coding of a prediction mode of a certain macroblock, it is also possible to employ a method of performing the code length assignment in consideration of situations (contexts) of prediction modes in the neighborhood thereof. For example, in the case of coding of a prediction mode of a certain macroblock, supposing the left macroblock is Mode 0 and the left upper macroblock is Mode 9, it can be contemplated that motion division inheriting the pattern of Mode 9 tends to appear in the present macroblock. Namely, it is conceivable in this case to employ such an ingenuity as to change a code table according to parameters of prediction mode situations (contexts) of neighboring macroblocks like the left, upper, and right upper macroblocks, e.g., as to shorten the code length of Mode 9. By defining versatile contexts independent of types of images, it becomes feasible to implement effective code assignment. At the same time, the finding of such contexts also offers the prospect of redundancy reducing effect based on employment of arithmetic coding instead of the fixed code assignment and based on the coding with switching between probability tables of the arithmetic coding dependent upon the contexts.

The variable length coding tables for the prediction mode coding may be switched one from another according to the contents of motion of image. For example, a frame including an image of extremely quick motion or a scene change is considered to have many irregular patterns such as the oblique division and the uneven division like Modes 3 to 14 in <figref idref="f0006">Figs. 6C and 6D</figref>, while such prediction modes are considered to rarely occur in quiet images. Namely, it is conceivably natural that the rate of effective prediction modes should considerably vary in units of frames or sequences. In order to make a distinction, it can be contemplated, for example, that part of header information at the head of a frame or a frame group is multiplexed with flag information for determining a variable length coding table for the prediction mode coding used in that frame or for determining a context definition used therein. The distribution of prediction mode values is also considered to depend upon the coding compression rate, and it is thus possible to employ a configuration wherein a plurality of variable length coding tables of prediction mode values are prepared and are used as switched one from another according to the initial values of quantization parameters in each frame unit.

Since the prediction modes that can appear can be limited to some extent by setting the contexts of the prediction modes according to the local property of the video signal as described above, it is feasible to keep low the overhead resulting from the coding of the prediction mode information even in the case where much more prediction modes than those shown in <figref idref="f0006">Figs. 6C and 6D</figref> are prepared. For example, it is possible to use a configuration in which the prediction mode variations of <figref idref="f0006">Figs. 6C and 6D</figref> are added to the variations of <figref idref="f0004">Figs. 4A to 4G</figref>. However, the variable length coding based on the contexts has the problem that if the compressed data of the neighboring regions is not correctly decoded because of transmission errors or the like, the present prediction mode information cannot be independently correctly decoded. In order to avoid this problem, it is possible, for example, to employ a configuration wherein the interior of the frame image is divided into units of finer independent coding image regions (slices) as used in the MPEG-2 video coding scheme and use of a context across slices is avoided at boundaries of the slices. This method slightly lowers the coding efficiency at the boundaries of the slices, but can improve the resistance to errors, as a trade-off thereof.

Furthermore, a number of prediction mode information may be arranged so as to switch according to coding conditions. In the case of the conventional prediction coding methods based on motion compensation as in the older standard coding schemes (MPEG-1, MPEG-2, etc.) than H.26L described in the conventional example, each macroblock was assigned one motion vector and the amount of codes was adjusted by the accuracy of DCT coefficients being the result of residual coding. The recent coding schemes (H.263 and MPEG-4) were, however, provided with the prediction modes in which the interior of one macroblock was divided into multiple blocks, and the amount of codes has been adjusted by a balance of the amount of codes for prediction to the DCT coefficients. In the H.26L scheme thereafter, more prediction modes were prepared, and there is an increasing tendency that the code amount is adjusted by the accuracy of motion compensation according to the number of motion vectors used. In H.26L, the code amount is adjusted by elaboration of motion compensation with use of the modes permitting utilization of the greater number of motion vectors out of the modes of <figref idref="f0004">Figs. 4A to 4G</figref>, in the high rate range. In the low rate range, however, since the adjustment of the code amount is achieved by the number of motion vectors, there will conceivably arise a problem that the modes to be selected out of the modes of <figref idref="f0004">Figs. 4A to 4G</figref> are limited to one or two (Modes 1 to 3) per macroblock in most cases and increase of the coding efficiency cannot be expected by the elaboration of motion compensation.

From the viewpoint of optimization of code amount to error (Rate-Distortion), optimal motion compensation models should differ depending upon given coding speeds (code rates). Namely, a motion compensation model used at low rates should be different from that used at high rates. It is thus necessary to adopt an approach of elaborating the motion compensation in a sense of conservation of waveform by many modes and many motion vectors at high coding rates and performing the motion compensation with better efficiency by the limited number of motion vectors at low coding rates. This approach of switching between the motion compensation models according to the rates has never been adopted in the coding standards heretofore.

Now, let us consider a motion compensation model in which a single motion is present in one macroblock or in which no single motion is present but a boundary between objects of different motions is present (i.e., the number of motion vectors per macroblock is limited to 2), as shown in <figref idref="f0006">Figs. 6A to 6D</figref>, at low rates. As cases in which the number of motion vectors per macroblock is limited to 2, the division of the macroblock into two segments is expanded from the simple horizontal and vertical division to horizontal, vertical, oblique, and phase-added division, thereby preparing for the cases wherein a border between objects of different motions exists in one macroblock. On the other hand, the motion compensation model to permit the greater number of motion vectors as shown in <figref idref="f0004">Figs. 4A to 4G</figref> is also permitted at high rates. Namely, a useful scheme is one that permits switching between such motion compensation models according to video coding conditions. For example, identification information for dynamic change of the motion compensation model used (i.e., the definition of the set of prediction modes) is arranged to be multiplexed on part of the header information at the head of a frame or a frame group, in each unit thereof (for example, it is equivalent to a sequence or a GOP in the MPEG-2 video coding system, or a video object layer, a video object plane, or the like in the MPEG-4 video coding system).

Such change of the motion compensation model can improve convenience in implementation as a scalable configuration and in use of coded data. For example, let us define three sets of prediction modes as shown in <figref idref="f0032">Figs. 32A to 32C</figref>. In <figref idref="f0032">Fig. 32A</figref> minimal prediction modes are used, and in <figref idref="f0032">Fig. 32B</figref> the prediction modes using the small number of motion vectors, presented in the present embodiment, are used in addition thereto. In <figref idref="f0032">Fig. 32C</figref>, the set further includes the prediction modes using many divisions and many motion vectors.

By defining such sets, it is feasible to switch between the motion compensation models according to coding conditions in the following manner: the prediction mode set of <figref idref="f0032">Fig. 32A</figref> is used where the top priority is given to reduction of calculated amount load; the prediction mode set of <figref idref="f0032">Fig. 32C</figref> is used where the pursuit of more elaborate motion compensation with many modes and many motion vectors is required at high coding rates; the prediction mode set of <figref idref="f0032">Fig. 32B</figref> is used where there are no such special requirements. In the architecture of <figref idref="f0032">Figs. 32A to 32C</figref>, each set of prediction modes is a sub-set of a set including the greater number of prediction modes. For example, the prediction mode set of <figref idref="f0032">Fig. 32B</figref> is a sub-set of the set of <figref idref="f0032">Fig. 32C</figref>. Accordingly, coded data encoded based on each prediction mode set can be made decodable in implementation based on a higher set.

It can also contemplated that such change of the motion compensation model is defined as a profile in the video coding system and motion compensation models available to respective uses are prescribed based thereon. The profile is a scheme of striking a balance between implementation-calculated amount load and coding efficiency by defining sub-sets of coding functions essential to respective uses, in a coding system in which a number of coding functions are prescribed. Each of the sets of prediction modes shown in <figref idref="f0032">Figs. 32A to 32C</figref> can be handled as a prediction mode set utilized in an individual profile and a scalable profile structure can be made in such a manner each profile is defined as a sub-set of a higher profile.

At this time, it is convenient in terms of implementation of an encoder and decoder to handle the units of change of motion compensation model and residual coding independently of each other. In the H.26L case, the residual coding is carried out in 4×4 pixel units, and thus the division models of macroblocks also consist of 4x4 pixel unit blocks. This permits the change of motion compensation model to be handled as reassignment of attribution of residual coding blocks to respective motion vectors, so as to achieve significant effect in terms of implementation efficiency.

② Predictive coding of motion vector information

In general, the overhead ratio of the motion vector information becomes higher at low bit rates, and it is thus necessary to efficiently encode the detected motion vector information. Normally, motions are quite unlikely to become random in magnitude and direction in units of macroblocks, and in that sense, motion vectors usually take close values to those in neighboring macroblocks. From this point of view, a predicted value of a motion vector is determined from neighboring motion vectors and its predictive residual data is coded. The motion vector coding method in the present embodiment will be described below.

The H.26L coding system is provided with a scheme of storing a plurality of past coded frame images as reference images in the frame memory 6 and performing the motion compensated prediction based on one of those designated. This allows us to expect effective prediction, particularly, in the case of images in which a moving region is present in front of the still background and in which the background appears and disappears depending upon the motion of the moving region. The present embodiment can also make use of this scheme in the motion detector 2 and can be configured in such a manner that, where two motion vectors are present in a macroblock, the reference frames thereof can be changed individually.

Although the interior of the macroblock was motion-divided in the inter prediction modes of the H.26L video coding system, the motion vectors had to be obtained from the same reference frame because of the great number of motion vectors. In contrast, the present embodiment permits assignment of reference frame switchover information to each motion vector by the decrease of the overhead without using the large number of motion vectors, thereby further increasing the efficiency of motion compensated prediction. In this case, the reference frame switchover information often takes values similar to those in the same macroblock or in adjacent macroblocks or sub-blocks. The amount of codes necessary for the reference frame switchover information can be reduced by utilizing that fact to estimate the switchover information or encode it all together.

It is a matter of course that the reference frame switchover information itself has to be transmitted as additional information and, in the case of a simple image without need for such switchover, the system may be arranged so as to be able to select a rule of using the same reference frame in each macroblock. In this case, it is conceivable, for example, to multiplex flag information for identifying whether the reference frame change in the macroblock is permitted, in each frame or frame group unit. This allows the decoding apparatus to operate so as to decode only one reference frame switchover information per macroblock, where the reference frame is unchanged within each macroblock.

On the other hand, in the case where the change of reference frame is permitted in units of motion detection, there arises a problem that if different reference frames are used between adjacent motion detection units the correlation becomes lower between their motion vectors. Namely, the accuracy of prediction of motion vectors becomes degraded in that case.

For example, <figref idref="f0007">Fig. 7A</figref> shows a case in which the present macroblock is Mode 1 and the left, upper, and right upper macroblocks are Modes 0, 1, and 8, respectively. In this case, it is anticipated from the contexts of the neighboring prediction modes, i.e., the continuity of motion division that the motion vector of the left segment will have high correlation with the both left and upper macroblocks and that the motion vector of the right segment will have high correlation with the both upper and right upper macroblocks, as indicated by arrows in the same figure. Namely, it is considered that if the same reference frame is referred to by the present, left, upper, and right upper macroblocks in <figref idref="f0007">Fig. 7A</figref>, the prediction can be achieved with accuracy by use of any predicted value. However, for example, in the case where the two motion vectors of the upper macroblock use the reference frame different from that for the motion vectors of the present macroblock and where the left macroblock refers to the same reference frame as that of the present macroblock, it is expected that the motion vector of the left macroblock should ensure higher prediction accuracy.

On the other hand, in <figref idref="f0007">Fig. 7B</figref>, supposing that the upper macroblock uses the reference frame different from that of the present macroblock, there is no continuity of motion from the upper macroblock and it cannot be settled whether either of the motion vectors of the left macroblock should be used for the prediction, from the context. Therefore, continuity of motion cannot be expected and thus high prediction accuracy can no longer be expected.

In order to solve this problem, the present embodiment adopts a method of assigning priorities to respective prediction candidates on the basis of the contexts of neighboring prediction modes and adaptively determining the motion vector predicted values. Since the neighboring prediction mode information and reference frame switchover information itself uses the already decoded information, there is no need for providing special additional information for this motion vector predicted value determining process. The flow of specific motion vector predicted value determining processing will be described below. <ol id="ol0001" compact="compact" ol-style=""><li>1) For each segment, neighboring motion vectors as candidates for predicted value are determined. <figref idref="f0008">Fig. 8A to Fig. 8C</figref> show examples of Modes 0, 1, and 7. In Mode 0 of <figref idref="f0008">Fig. 8A</figref> there is only one motion vector and thus the motion vectors at the block locations shaded by hatching are selected as candidates. In Mode 1 of <figref idref="f0008">Fig. 8B</figref> there exist motion vectors for a white region and a gray region (a region hatched in the macroblock of <figref idref="f0008">Fig. 8B</figref>), respectively, and thus candidates for the predicted value are settled so that the motion vectors at the locations of the blocks shaded by hatching are used for the motion vector of the white region and so that the motion vectors at the locations of the blocks shaded by horizontal stripes are used for the motion vector of the gray region. In <figref idref="f0008">Fig. 8B</figref> of this Mode 1, a shaded block of hatching overlaps a shaded block of horizontal stripes in the central region above the macroblock. In Mode 7 of <figref idref="f0008">Fig. 8C</figref>, a white region has little continuity of motion from the upper region and thus only the motion vector at the location of the left shaded block of hatching is selected as a candidate for the predicted value. For the gray region, the motion vectors at the locations of the shaded blocks of horizontal stripes are selected as candidates for the predicted value. These prediction candidate locations are preliminarily determined for each of the modes and are shared between the coding apparatus and the decoding apparatus.</li><li>2) Macroblocks with predicted values using the same reference frame are specified out of the macroblocks including the predicted value candidates. Determination on whether the neighboring macroblocks use the same reference frame can be implemented by retaining the already decoded information of the neighboring macroblocks.</li><li>3) Among the macroblocks specified in 2), the macroblock and the motion vector with the highest prediction usage priority are specified based on the prediction mode information, and the motion vector is adopted as a predicted value. The prediction usage priorities are fixedly defined for each of the prediction modes in consideration of the continuity of motion from the neighboring blocks, as shown in <figref idref="f0009">Fig. 9</figref>, and are shared between the coding apparatus and the decoding apparatus. In <figref idref="f0009">Fig. 9</figref>, for example, in the case of Mode 5 as an example, where the prediction mode of the macroblock as a present object for prediction of motion vector is Mode 5, the priorities about the continuity of motion for the macroblock above it are defined in the order of 0, 6, 2, 8, 9, 12, and 13 of the mode values named from the highest. The priorities for the left macroblock are also defined in the order of 5, 0, 2, 8, and 12 of the mode values named from the highest. The priorities are also similarly defined for the right upper macroblock. For example, if the upper and left macroblocks have the same priority rank, either one of them will be assertively determined as a predicted value. Namely, in this example, where the prediction mode of the macroblock itself is Mode 5 and where the motion vector of the gray region is predicted, supposing that the motion vectors at the locations of the upper and left prediction candidates use the same reference frame, that the right upper macroblock uses a different reference frame, and that Mode 13 appears in the upper macroblock and Mode 5 in the left macroblock, the motion vector of the left block is selected as the predicted value with the highest priority.</li><li>4) If there is only one prediction candidate location as in the case of the white region of Mode 7 in <figref idref="f0008">Fig. 8C</figref> and if it uses the same reference frame, the motion vector therein is used as a predicted value as it is. If it uses a different reference frame the predicted value is determined using a plurality of predicted value candidates at predetermined locations (for example, using median prediction).</li><li>5) If continuity of motion cannot be expected from any neighboring macroblock, in spite of the presence of a plurality of predicted value candidate locations (i.e., in the case of the prediction modes being not included in the priority order of <figref idref="f0009">Fig. 9</figref>), the predicted value is determined using all the predicted value candidates (e.g., median prediction).</li><li>6) If all the motion vectors of the predicted value candidates use reference frames different from that of the motion vector to be predicted, the predicted value is determined using all the predicted value candidates (e.g., median prediction).</li></ol>

The coding of the motion vectors is implemented by variable length coding of predictive residual data using the predicted values obtained as a consequence of the above processing.

The predicted values of motion vectors may also be fixedly given as shown in <figref idref="f0010">Figs. 10A to 10D</figref>. In these figures, white arrows indicate directions of prediction for the motion vectors of the white regions, and black arrows directions of prediction for the motion vectors of the black regions. In the case of Mode 4 of <figref idref="f0010">Fig. 10C</figref> as an example, for the prediction of the motion vector of the white region in Mode 4, the predicted value is determined using the motion vector of the sub-block located to the left of the third sub-block from the top in the white region. This rule fails to give sufficient consideration to the continuity of motion from the neighborhood, but has the merit of relieving instrumental implementation associated with the motion vector prediction processing because of the fixed assignment of the prediction locations. In <figref idref="f0010">Figs. 10A to 10D</figref>, if a block intended to be used for the predicted value uses a different reference frame, it is desirable to switch to the technique of median prediction or the like, assuming that the continuity of motion is lost.

③ Compressed stream syntax

The syntax of macroblock data of the compressed stream 24 outputted from the coding apparatus of the present embodiment is presented in <figref idref="f0011">Fig. 11B</figref> in comparison with the H.26L current syntax of <figref idref="f0011">Fig. 11A</figref>.

The RUN information (RUN) in these figures is coded data to indicate the number of macroblocks judged as the aforementioned skip mode; supposing that the blocks from the nth macroblock to the (n+5)th macroblock are a skip and the (n+6)th macroblock is not a skip, coded data of run information = 5 is given to the head of the (n+6)th macroblock data. The macroblock type information (MB_Type) indicates the prediction mode 3 in <figref idref="f0001">Fig. 1</figref>.

The seven types shown in <figref idref="f0004">Figs. 4A to 4G</figref> are discriminated herein as inter prediction modes. The intra prediction mode information (Intra_pred_mode) in <figref idref="f0011">Fig. 11A</figref> is information used for discriminating a plurality of spatial prediction methods from each other in the intra prediction mode, and is omitted if the inter prediction mode is chosen (arrow P1 in <figref idref="f0011">Fig. 11A</figref>). The reference frame information (Ref_frame) is data to designate a number of a reference frame indicated by the motion vector when the inter prediction mode is chosen, and is omitted when only one immediately preceding frame is used as a reference frame (arrow P2). The motion vector difference (MVD) is a difference of the motion vector from the predicted value and the horizontal and vertical components thereof are multiplexed in the order named. Since the maximum number of motion vectors is sixteen in H.26L as shown in <figref idref="f0004">Fig. 4G</figref>, data of up to sixteen motion vector differences is multiplexed (i.e., arrow Q1 represents up to sixteen loops). The number of motion vector differences is determined by the macroblock type information. It is omitted when the intra prediction mode is chosen (arrow P3). Subsequent to the above data, the orthogonal transform coefficient data (Texture Coding Syntax) of the predictive residual signal is multiplexed.

On the other hand, in the syntax of the present embodiment shown in <figref idref="f0011">Fig. 11B</figref>, the macroblock type information is used to identify the fourteen types of inter prediction modes shown in <figref idref="f0006">Figs. 6A to 6D</figref> (while the intra prediction mode is assumed to be the same as in H.26L). Since one reference frame information is made correspondent to one motion vector, the reference frame information and the motion vector difference are always multiplexed as a set. The number of sets of reference frame information and motion vector difference is determined by the macroblock type information. The maximum number is 2 (i.e., arrow Q2 in <figref idref="f0011">Fig. 11B</figref> indicates up to two loops). When the inter prediction mode is chosen, the intra prediction mode information is omitted as indicated by arrow P4, and when the intra prediction mode is chosen, the reference frame information and motion vector difference are omitted as indicated by arrow P5.

Since the reference frame information often takes values similar to those of the reference frame information in the same macroblock or in neighboring macroblocks or sub-blocks, coding may be implemented by making use of it. For example, by assigning one code to a combination of two reference frame information values in the same macroblock and making codes on the basis of probabilities of occurrence of combination patterns, it is feasible to reduce the amount of codes for frequently appearing combinations.

<figref idref="f0033">Fig. 33A</figref> shows a code configuration of the reference frame information in H.26L, and <figref idref="f0033">Fig. 33B</figref> shows an example of codes assigned to combinations of reference frame information. For example, if the reference frame information is often 0 in the both blocks within the same macroblock, the code configuration of <figref idref="f0033">Fig. 33A</figref> requires two bits for the two reference frame information values, whereas the code configuration of <figref idref="f0033">Fig. 33B</figref> requires only one bit for coding of the reference frame information, so as to be able to reduce the amount of codes. In this case, different from the syntax of <figref idref="f0011">Fig. 11B</figref>, only one code about the reference frame information is multiplexed per macroblock without being paired with the motion vector difference, as shown in <figref idref="f0033">Fig. 33C</figref>. Arrows P26, P27 in <figref idref="f0033">Fig. 33C</figref> indicate jumping with omission of corresponding processing, and arrow Q11 indicates up to two loops.

It is also possible to perform the prediction based on the reference frame information in adjacent macroblocks or sub-blocks and switch the codes. For example, just as in the case of the aforementioned prediction of motion vector, the prediction locations may be fixedly assigned as in <figref idref="f0010">Figs. 10A to 10D</figref> and the reference frame information associated with the prediction locations is used as predicted values. Since there are also cases with no reference frame information associated, as in the case where no fixed prediction location is assigned as in Mode 0, in the case where the intra prediction mode is adopted at the prediction location, etc., a default predicted value is used in such cases. Codes are arranged based on probabilities of occurrence of reference frame information values in acquisition of the predicted value, and codes are switched according to the predicted value.

For example, let us suppose that the codes of <figref idref="f0034">Fig. 34A</figref> are used as codes before change or when the predicted value is 0, and that the codes configured as shown in <figref idref="f0034">Fig. 34B</figref> are used as codes when the predicted value is 4 as an example. In the case where the reference frame information often takes the same value as the predicted value and where if the predicted value is 4, the probability of the reference frame information becoming 4 is higher than the probability of the reference frame information becoming 2, the code amount of the reference frame information can be reduced by using the codes of <figref idref="f0034">Fig. 34B</figref>, instead of using the codes of <figref idref="f0034">Fig. 34A</figref> as they are. In this case, the reference frame information is always multiplexed as a set with the motion vector difference in the same manner as in <figref idref="f0011">Fig. 11B</figref>.

Although not illustrated, the orthogonal transform coefficient data contains significant coefficient presence identification information (CBP: abbreviation of Coded Block Pattern) indicating whether data to be coded exists in 8x8 block units in the macroblock, and use of this data permits omission of transmission of the entire information in each 8×8 block without any significant coefficient, thereby achieving efficient coding of orthogonal transform coefficient data. <figref idref="f0035">Figs. 35A to 35C</figref> show examples thereof. Let us suppose that a macroblock is divided and coded as shown in <figref idref="f0035">Fig. 35A</figref> and that each sub-block (4x4 block) indicated as a white block has no significant coefficient. In this case, the presence or absence of significant coefficient is coded and transmitted in units of 8×8 blocks, as shown in <figref idref="f0035">Fig. 35B</figref>, to preliminarily indicate the presence or absence of orthogonal transform coefficient data in each 4×4 block included in 8×8 blocks, whereby the code amount can be reduced by omission of transmission of information in each 4×4 block.

With use of the prediction modes in the present embodiment, in cases where a pattern using two motion vectors is chosen, it is expected that the coefficient data to be coded is reduced for the predictive residual signal located at the division boundary, because of the increase of the prediction efficiency by the division. Particularly, in the case of the uneven division and oblique division in and after Mode 3, a division boundary can exist inside an 8×8 block, and it is considered that this portion has a high probability that there exists no coefficient data to be coded. Therefore, depending upon the circumstances, it is possible to employ a configuration to change variable length coding tables of significant coefficient presence identification information or probability tables of arithmetic coding according to the prediction modes. This enables implementation of efficient coding of significant coefficient presence identification information according to the prediction modes.

With use of the prediction modes according to the present embodiment, it is also conceivable that a macroblock is divided into a portion without change and a portion with great change and the presence or absence of significant coefficient data becomes constant in each segmental region. In this case, if the significant coefficient presence identification information is configured and coded so as to indicate the presence or absence of significant coefficient data in each segmental region, instead of designating the presence or absence of significant coefficient data in each 8×8 block as used in H.26L, the code amount necessary for the significant coefficient presence identification information can also be reduced. <figref idref="f0035">Fig. 35C</figref> shows an example of that case. When the presence or absence of significant coefficient data is transmitted in 8x8 block units as shown in <figref idref="f0035">Fig. 35B</figref>, the number of patterns thereof becomes large; whereas, in the case where the presence or absence of significant coefficient data is sent in units of the segmental regions as shown in <figref idref="f0035">Fig. 35C</figref>, the number of patterns can be made smaller whereby the code amount necessary for the significant coefficient presence identification information can be reduced.

The decoding processing procedure in the decoding apparatus will be described below. <figref idref="f0012">Fig. 12</figref> shows the processing flow of the decoding apparatus.

The variable length decoder 25 first detects the synchronization word indicating the head of a picture (i.e., decoded data of each frame of an image) (S101) to decode the picture header (S102). The picture header contains the picture type information to identify whether the picture is an intra coded picture (which is a picture all macroblocks of which are coded by intra prediction and which will be called an I picture) or a picture using inter prediction (which will be called a P picture), and values including the quantization parameters of orthogonal transform coefficient data and others. Subsequently, the flow proceeds to decoding of individual macroblock data formed in the syntax of <figref idref="f0011">Fig. 11B</figref>. The run information is first decoded in the macroblock layer (S103). The definition of data of the run information is as described previously, and skip macroblocks occur by the number of the run information. For each of the skip macroblocks, data of the 16×16 pixel region at the same location on the predetermined reference frame stored in the frame memory 26 is acquired as decoded image data as it is (S104 and S105). The process of acquiring the decoded image is conducted by giving the motion vector of zero and the predetermined reference frame number to the motion compensator 5. When the run information indicates the last macroblock of the picture (S106), the variable length decoding of that picture is terminated at that point, the loop filter 21 performs the block distortion removing process (S118), and then the flow transfers to the variable length decoding processing of the next picture.

With an ordinary coded macroblock, the flow proceeds to step S107 to decode the macroblock type information. This settles the prediction mode 3. If the prediction mode 3 is the intra prediction mode (in the case of the affirmative judgment in S108), the intra prediction mode information is decoded (S109). Precisely, H.26L involves two types of intra prediction modes: an intra 4×4 mode of performing the intra prediction in sub-block (4x4 block) units and an intra 16x16 mode of performing the intra prediction in 16x16 pixel units, among which only the intra 4x4 mode requires the intra prediction mode information. After the intra prediction mode information is settled, the spatial predictor 9 generates intra prediction values from neighboring image data (S110).

On the other hand, if the prediction mode 3 is an inter prediction mode (in the case of the negative judgment in S108), it must be a value indicating one of the modes shown in <figref idref="f0006">Figs. 6</figref>. Accordingly, how many sets of reference frame information and motion vector difference should be decoded is settled at this point (i.e., one set in Mode 0 and two sets in the other modes). Each set of reference frame information and motion vector difference is decoded according to this information. However, since whether the reference frame information is multiplexed is integrated into the aforementioned picture type information, it is necessary to make a decision on whether the reference frame information is present, based on the value of the picture type (Sill).

Although not illustrated in the figure, where the reference frame information was coded by making use of the values of reference frame information in the same macroblock or in adjacent macroblocks or sub-blocks as described previously, the reference frame information is decoded on the basis of the combinational information of the reference frame information according to those, or after switchover of codes according to the predicted value.

With the reference frame information, the value thereof is first decoded and then the motion vector difference is decoded (S112 and S113); without the reference frame information, only the motion vector difference is decoded (S113). The predicted value of each motion vector is determined based on the reference frame information, motion vector difference, prediction mode indicated by the macroblock type information, and neighboring prediction mode information, and based on the same predicted value candidate locations and prediction usage priorities as in the coding apparatus, shown in <figref idref="f0008">Figs. 8A to 8C</figref> and <figref idref="f0009">Fig. 9</figref>, to decode each motion vector information corresponding to every sub-block in the macroblock. This motion vector information 4 is fed to the motion compensator 5, and the motion compensator 5 generates a motion compensated prediction value for every individual sub-block, based on the designated reference frame information and motion vector (S114).

After completion of the above processing, the variable length decoder 25 decodes the orthogonal transform coefficient data 17 of the predictive residual signal of the macroblock (S115), and the dequantizer 18 and inverse orthogonal transformer 19 decode the predictive residual signal (S116). Finally, the predicted value obtained in S110 or S114 is added thereto to acquire a decoded image of the macroblock (S117). Thereafter, the flow transfers to the decoding processing of the next macroblock.

The coding apparatus and decoding apparatus described above made it feasible to accurately capture various motions in the macroblock, within a small overhead and to implement efficient video transmission, recording, and playback. Since in the present embodiment the interior of the macroblock is motion-divided in various shapes to increase the prediction efficiency and each region as a motion compensated prediction target is comprised of a combination of sub-blocks, no division boundary of prediction exists inside the sub-blocks on the occasion of performing the predictive residual signal coding in sub-block units as in the H.26L video coding system, thus presenting the advantage of producing no discontinuous wave. This presents the advantage that in application of DCT to the predictive residual signal coding, occurrence of excess high-frequency coefficients can be avoided, and in application of vector quantization, efficient coding can also be implemented in that peculiar signal waveforms are reduced, so as to allow expression with only general-purpose waveforms specified by a code book.

The second embodiment will be described below. The present embodiment will describe the video coding apparatus configured to perform coding in macroblock units, particularly, the video coding apparatus and decoding apparatus configured to use up to two motion vectors per macroblock and to perform the motion compensated prediction while assigning the two motion vectors, in units of sub-blocks obtained by dividing a macroblock into 4×4 pixel units. The first embodiment described that the motion vectors were assigned in units of sub-blocks according to the fixed patterns, whereas the present embodiment will describe the coding apparatus and decoding apparatus configured to permit arbitrary designation of motion vector assignment to each sub-block.

The present embodiment can be described with the same members and operations except for differences in the definitions of the prediction mode 3 (particularly, the inter prediction modes) and the motion vector 4 in the compressed stream 24, and the operations of the motion detector 2 and motion compensator 5, as in the coding apparatus and decoding apparatus shown in <figref idref="f0001">Fig. 1</figref> and <figref idref="f0002">Fig. 2</figref> in the conventional example. The description below will be given with focus on the operation of the motion detector 2 and the definitions of the prediction mode 3 and motion vector 4 about the coding apparatus and with focus on the procedure of decoding the video signal from the prediction mode 3 and motion vector 4 about the decoding apparatus.

First, the processing of the coding apparatus and the configuration of the compressed stream transmitted to the decoding apparatus will be described with focus on the configuration of the prediction mode 3 and the detection procedure of motion vector 4 in connection therewith in the present embodiment. The prediction mode 3 in the present embodiment is defined as information extended so as to enable designation of an arbitrary assignment situation in addition to the aforementioned fixed motion vector assignment of <figref idref="f0006">Figs. 6A to 6D</figref>, as shown in <figref idref="f0013">Figs. 13A to 13C</figref>. Namely, supposing IDs of two motion vectors are 0 and 1, the prediction mode can be expressed as binary map information of 4×4 as shown in <figref idref="f0013">Figs. 13A to 13C</figref>. Here the arrangement of IDs has the meaning as a transmission order in the compressed stream, for example.

The following will describe a method of determining the motion vectors 4 assignable as shown in <figref idref="f0013">Figs. 13A to 13C</figref> (which is executed in the motion detector 2) and a coding method of prediction mode 3 based on the expression of <figref idref="f0013">Figs. 13A to 13C</figref>. The first embodiment was configured simply to evaluate the plurality of patterns of the fixed motion vector assignment and fixedly execute the detection of motion vector in each of regions, whereas in the present embodiment the motion vector detection has to be carried out in consideration of optimization of motion vector assignment.

<figref idref="f0014">Fig. 14</figref> shows a procedure of an example of the detection. First, S201 is to carry out the motion vector detection in a unit of 16×16 pixels. This can be much the same motion vector detection as in the case of Mode 1 of <figref idref="f0004">Fig. 4A</figref> or Mode 0 of <figref idref="f0006">Fig. 6A</figref>. The resultant motion vector is referred to as a first motion vector V1. Then, using the predicted value obtained as a consequence, a predictive evaluation value (SAD: Sum of Absolute Difference herein) is calculated for each 4×4 sub-block, and a sub-block with the predictive evaluation value over a predetermined value is extracted as an exceptional sub-block region (S202). This results in obtaining a motion vector assignment map 40 in which hatched portions indicate exceptional sub-block regions. The exceptional sub-block regions represent regions that cannot be satisfactorily predicted by the first motion vector V1, and by specifying the exceptional sub-block regions, it becomes feasible to implement motion vector assignment based on prediction efficiency. Then the motion vector detection is carried out for an object of only the exceptional sub-block regions, to detect a second motion vector V2 (S203).

In the above processing procedure, the detection process may also be configured to be performed in consideration of not only the predictive evaluation values but also the motion vector value and the code amount of motion vector assignment information (i.e., the prediction mode 3 of <figref idref="f0001">Fig. 1</figref>) determined in the exceptional sub-block regions. The first and second motion vectors may also be detected with reference to their respective reference frames different from each other, as in the first embodiment.

<figref idref="f0015">Fig. 15</figref> shows a procedure of another detection example. In this example, a motion vector is first detected in every sub-block unit to acquire sixteen vectors (S204). Then the sixteen vectors are clustered into two vectors V1, V2 so as to be optimal in terms of the code amount and prediction efficiency of the entire macroblock (S205). Particularly, if the vector assignment is done in consideration of the code amount of prediction mode 3, it becomes feasible to detect such motion vectors as to achieve an optimal rate distortion balance in coding of the macroblock. The motion detector 2 determines the prediction mode 3 and motion vectors 4 on the basis of the method as described above.

A coding method of information of the prediction mode 3 will be described below using <figref idref="f0016">Figs. 16A and 16B</figref>. The procedure of coding is presented in the flowchart of <figref idref="f0017">Fig. 17</figref>. Let us suppose that the macroblock C in <figref idref="f0016">Figs. 16A and 16B</figref> is a macroblock as an object of coding, the macroblock A a macroblock located immediately above C, and the macroblock B a macroblock located to the left of C. Each macroblock is divided into 4×4 sub-block units and states of motion vector assignment (prediction mode 3 in <figref idref="f0001">Fig. 1</figref>) are indicated by the difference of white and gray. The coding is conducted in such a manner that change points of motion vector assignment in the sub-blocks are coded on the basis of the situations of the prediction modes in the macroblocks A and B. First, which should be inherited between the situations of the prediction modes, A or B, (prediction priority context) is determined from the prediction mode situations of the macroblocks A and B (S206 in <figref idref="f0017">Fig. 17</figref>). In addition, a line counter L is reset to zero. It is obvious in <figref idref="f0016">Fig. 16A</figref> that the continuity of motion is higher from the macroblock A, and thus changes of motion vector assignment in the vertical direction as indicated by an arrow shall be defined as objects of detection. Hereinafter, this will be called a vertical prediction priority context. Conversely, in the case where the continuity of motion is judged higher from the macroblock B, as shown in <figref idref="f0016">Fig. 16B</figref>, changes of motion vector assignment in the horizontal direction shall be defined as objects of detection. Hereinafter, this will be called a horizontal prediction priority context. In <figref idref="f0016">Figs. 16A and 16B</figref>, change points are indicated by bold lines in the cases where the macroblock C is assumed to be coded by the respective prediction priority contexts. The description below will be given concerning the case example of <figref idref="f0016">Fig. 16A</figref>.

For processing of line L, first settled are a remaining run count r, a run start point a0, and a run end point a1 (S207). The run end point a1 represents a location of a sub-block assigned a motion vector different from that assigned to the nearest sub-block in the macroblock designated by the prediction priority context (the macroblock A in the case of <figref idref="f0016">Fig. 16A</figref>).

However, it is practically less common to continuously detect the same motion vector across the macroblocks A and C, and it is thus necessary to adopt some means, for example, a method of starting the processing on the assumption that the motion vector assignment situation (0 or 1) of the nearest sub-block in the macroblock designated by the prediction priority context is the same as the assignment situation at the initial run start point a0 of the macroblock as an object of coding.

Another potential method is a method of applying the prediction priority context as closed within the macroblock C. Specifically, among the sixteen sub-blocks, the value of 0 or 1 is left as it is, for the left upper corner sub-block, a change point from a left adjacent sub-block is defined as 1 for the four sub-blocks in the uppermost line, and a change point from an immediately above sub-block is always defined as 1 for the four sub-blocks in the leftmost line. In addition to the determination above, change points of the remaining sub-blocks are determined on the basis of the prediction priority context.

It is seen that r=4 and a0=0 at the head of line L and in the example of <figref idref="f0016">Fig. 16A</figref> a1 is 3 in L=0. From this, the number of sub-blocks continuously assigned the same motion vector in the line L is given by R=a1-a0. This value is subjected to variable length coding using a code length CB(r) determined by the remaining run cont r (S208). Examples of the code length CB(r) are presented in <figref idref="f0018">Fig. 18A to Fig. 18C</figref>. Since situations of occurrence of remaining R are restricted depending upon progress of operation in coding of R, the coding efficiency can be increased by switching between the code lengths according to the remaining run count r in this way. For example, in the case of L=0 in <figref idref="f0016">Fig. 16A</figref>, r=4 and R=3 are first obtained, and thus R=3 is coded using CB(4) (code 1 is assigned and the code length is 3 bits). Then the remaining run count r is updated according to r=r-R and the run start point a0 is transferred to a1 (S209). This results in obtaining r=1, and the remaining run count of 1 means that the motion vector assignment in the line L is all settled at that point. Therefore, there is no need for transmission of a code in particular. This is the reason why CB(1) is not defined. Accordingly, in the case of r ≤ 1, L is counted up and the processing is transferred to the next line (S210 and S212). If r &gt; 1 on the other hand, a new change point is detected (S211) and the above processing is repeated. In the final line L=3 of the macroblock C shown in <figref idref="f0016">Fig. 16A</figref>, the initial sub-block suddenly becomes the run end point and the code of "initial reversal 0" of CB(4) is encoded. Thereafter, the processing is advanced with the remaining run information count r=3. The coding processing is terminated when the time count L reaches 4.

As described above, in the case of <figref idref="f0016">Fig. 16A</figref>, <figref idref="f0003">3</figref> bits are necessary for L=0, 4 bits for L=1, and 6 bits for L=2, 3 and by further adding the code length of the prediction priority context (three bits in either of the horizontal and vertical cases herein) thereto, the coding of the prediction mode 3 is done by 18 bits. In the case of <figref idref="f0016">Fig. 16B</figref>, the coding can be done with four bits each for L=0, 1 and 1 bit each for L=2, 3, and with addition of the context, the prediction mode can be coded by 13 bits. Since the binary information itself can be expressed by 16 bits, a case of expression over 16 bits can be arranged to be coded by a 16-bit fixed length code with some device such as an escape code or the like. Furthermore, it is also possible to employ a configuration wherein patterns expected to have high frequencies of occurrence as division patterns (the cases as shown in <figref idref="f0006">Figs. 6B to 6D</figref>) like the case of <figref idref="f0016">Fig. 16A</figref> are preliminarily assigned fixed short codes and wherein the codes by the above coding are used for expressing arbitrary division patterns other than those. The above coding processing procedure makes it feasible to efficiently code and transmit the information of the prediction mode 3 of <figref idref="f0001">Fig. 1</figref> indicating the arbitrary motion vector assignment situation in sub-block units.

In light of the above description, syntaxes of macroblock data of the compressed stream 24 outputted from the coding apparatus of the present embodiment are presented in <figref idref="f0019">Figs. 19B, 19C</figref> in comparison with the H.26L syntax (<figref idref="f0019">Fig. 19A). Fig. 19B</figref> shows the simplest syntax example of the present embodiment, in which the macroblock type information contains only discrimination of either intra prediction or inter prediction and in which as to the inter prediction the shortest code is assigned to the case of the 16×16 pixel unit motion compensation while the information of the prediction priority context is assigned the next shortest code. The prediction priority context information means that the mode is the inter prediction mode by an arbitrary division pattern.

In general, the intra prediction appears at lower frequency of occurrence than the inter prediction, and is thus assigned a longer code than that of the prediction priority context information. For example, on the basis of the H.26L variable length code definition, code "1" (1 bit) is assigned to the 16×16 pixel unit motion compensation mode and code "001" or "011" (3 bits) to the prediction priority context information. When the intra prediction mode is chosen, the intra prediction mode information is decoded as in H.26L (in the case of the inter prediction mode, the intra prediction mode information is omitted as indicated by arrow P9). The motion vector assignment information in sub-block units as coded by the above coding method is multiplexed at the next location. This may be a 16-bit fixed length code. In the case of the intra prediction mode, this information is omitted to skip the corresponding processing as indicated by arrow P10. The information thereafter is as described in the first embodiment.

<figref idref="f0019">Fig. 19C</figref> shows another syntax configuration, in which, instead of expressing the prediction priority context by the macroblock type information, the code "001" or "011" (3 bits) is used as identification information to identify whether the mode information of inter predication by an arbitrary division pattern is sent by variable length or by fixed length (16 bits). When it indicates the variable length, the motion vector assignment information (Pattern_info) is multiplexed subsequent to the prediction priority context (pred_ctx). When the fixed length is indicated on the other hand, the motion vector assignment information is multiplexed with a 16-bit fixed length code. In <figref idref="f0019">Fig. 19B</figref>, it is also possible to define the macroblock type information so as to express the information indicating the specific division patterns with high frequencies of occurrence as shown in <figref idref="f0006">Figs. 6B to 6D</figref> and the escape code indicating the other patterns. In this case, the motion vector assignment information shall contain the value of the prediction priority context. This permits the division patterns with high occurrence frequencies to be coded more efficiently, without need for additional information for the motion vector assignment. In <figref idref="f0019">Figs. 19A to 19C</figref>, arrows P6 to P15 indicate omission of pertinent information, an arrow Q3 up to sixteen loops, and arrows Q4 and Q5 up to two loops.

<figref idref="f0020">Fig. 20</figref> shows the operation flow of the decoding apparatus. The decoding apparatus in the present embodiment operates in the same manner as the decoding apparatus of the first embodiment, except for the difference in the decoding procedure of the prediction mode information 3, and thus only the decoding processing part of the prediction mode information 3 will be described below.

In <figref idref="f0020">Fig. 20</figref>, S101 to S118 are the same processing steps as those in the decoding apparatus of the first embodiment shown in <figref idref="f0012">Fig. 12</figref>. When S108 in <figref idref="f0020">Fig. 20</figref> ends up indicating the inter prediction mode, the flow proceeds to S215 to decode the motion vector assignment information in <figref idref="f0019">Fig. 19B</figref>. On this occasion, since the prediction priority context information has already been obtained from the macroblock type information, this step is arranged to perform the decoding processing using CB(r) on the basis of the prediction priority context information decoded in the process of S214. Since this can be carried out by common variable length decoding processing, the detailed description thereof is omitted herein. After the motion vector assignment is settled for all the sixteen sub-blocks, the process of S215 is terminated and the flow transfers to the decoding process of the reference frame information and the motion vector difference. The processing hereinafter is carried out as described in the first embodiment.

The decoding processing based on the syntax of <figref idref="f0019">Fig. 19C</figref> can also be explained with <figref idref="f0020">Fig. 20</figref>. In this case, step S214 is configured to determine whether the motion vector assignment information is a variable length code or a fixed length code, instead of the prediction priority context information. On the basis of this information, step S215 is arranged to execute the decoding of the motion vector assignment information based on the syntax of <figref idref="f0019">Fig. 19C</figref>. In the case of the variable length code, the decoding processing of the prediction priority context information is first carried out. Furthermore, where the macroblock type information contains the identification information indicating one of some division patterns with high occurrence frequencies (e.g., Modes 1 to 14 in <figref idref="f0006">Figs. 6B to 6D</figref>), the division pattern is settled in the step of S214, and thus the flow can be configured to skip the step of S215 except when the escape code indicating an arbitrary division pattern is detected.

The coding apparatus and decoding apparatus described above make it feasible to capture various motions in the macroblock by the arbitrary division in sub-block units and to implement efficient video transmission, recording, and playback with a small overhead.

The third embodiment will be described below. The present embodiment will describe another coding method of the prediction mode 3 of <figref idref="f0001">Fig. 1</figref> to indicate the arbitrary division pattern in the second embodiment. <figref idref="f0021">Fig. 21</figref> shows the processing flow of the coding method in conjunction with the specific example used in <figref idref="f0016">Fig. 16A</figref>, and <figref idref="f0022">Figs. 22</figref> are illustrations to explain the processing. First, S301 in <figref idref="f0021">Fig. 21</figref> is to determine the prediction priority context as in the second embodiment. When the vertical prediction priority context is selected herein, change points are detected as locations of change where the motion vector assignment changes with respect to the lowermost sub-block line of macroblock A (S302). For example, in the case of macroblocks A, C of <figref idref="f0022">Fig. 22A</figref>, bold portions are detected as change points. This results in generating a binary map of <figref idref="f0022">Fig. 22B</figref> with each changing point assigned 1 and with each unchanging point assigned 0. This map is scanned with a predetermined scan table (e.g., a scan table of <figref idref="f0022">Fig. 22C</figref>) to generate zero runs (S303).

For example, since the vertical prediction priority context is adopted herein, the binary map of <figref idref="f0022">Fig. 22B</figref> is scanned using the scan table for vertical scan of <figref idref="f0022">Fig. 22C</figref>. As a consequence, a set of zero runs {3, 1, 3, 5) is generated. This information is subjected to variable length coding (S304 to S307), thereby effecting coding of the prediction mode 3. When no change point is found in the middle of the scan (in the case of the affirmative judgment in S305), the zero run information thereafter is replaced by only one end code (EOB) (S306).

When a change point is present to the point of the end of the scan on the other hand, the code of the last zero run can be settled by making use of the fact that the total number of zero runs and change points should be 16, and the coding with the end code is not performed (S306 is skipped after the affirmative judgment in S307).

The scan table may be replaced, for example, by zigzag scan of <figref idref="f0023">Fig. 23A</figref>, horizontal scan of <figref idref="f0023">Fig. 23B</figref>, or Hilbert scan of <figref idref="f0023">Fig. 23C</figref> or can be any other table. The scan may be changed based on the prediction priority context (e.g., the horizontal scan is used when the horizontal prediction priority context is selected), or a specific general scan rule may be fixedly used. A dedicated flag for switching between scan tables may be coded as part of the information of the prediction mode 3. In this case, the coding apparatus can selectively use a scan table with the best coding efficiency out of a plurality of scan methods.

The syntax of the prediction mode 3 obtained by the above-stated coding method can be implemented by replacing the motion vector assignment information shown in <figref idref="f0019">Figs. 19B and 19C</figref> with the coding method of the second embodiment. Concerning the configuration of the decoding apparatus, the step of S215 in <figref idref="f0020">Fig. 20</figref> corresponds to the process of decoding the code encoded by the coding method described in the present embodiment to settle the prediction mode 3.

The present embodiment described the case example using the prediction priority context information, but it is also possible to employ a configuration in which the change points are detected according to a certain fixed rule, independent of the prediction priority context, so as to obviate the need for coding the information of the prediction priority context. In this configuration the scan table may be a fixed one or a flag may be provided to switch to an efficient table.

The coding apparatus and decoding apparatus described above make it feasible to capture various motions in the macroblock by arbitrary division in sub-block units and to implement efficient video transmission, recording, and playback with a small overhead.

The fourth embodiment will be described below. The present embodiment will describe the coding apparatus and decoding apparatus in which the prediction mode 3 of <figref idref="f0001">Fig. 1</figref> is configured to allow change of motion vector assignment in sub-block units and provide the distinction of intra/inter prediction. Since this configuration allows intra or inter (one of plural motion vectors) to be selected and coded in each sub-block, efficient coding adapted to the property of actual images can be performed, as compared with the mode switching in macroblock units.

First, the definition of the prediction mode 3 of <figref idref="f0001">Fig. 1</figref> in the present embodiment will be described using the examples of <figref idref="f0024">Figs. 24A and 24B</figref>. In the H.26L coding system, two types of intra prediction are prepared: the intra 4×4 mode (INTRA_4×4) of performing the spatial prediction with switching among a plurality of prediction methods identified by the intra prediction mode information in 4×4 sub-block units; and the intra 16×16 mode (INTRA_16×16) of performing the spatial prediction with switching among a plurality of prediction methods in macroblock units.

A total of six types (1-6) of spatial prediction methods are defined for the intra prediction mode information, and these are allowed to be designated in sub-block units. Then this is extended to be integrated with the motion vector assignment information as prediction modes of 4×4 sub-blocks. Namely, supposing two motion vectors can be used, IDs of prediction methods thereof are defined by 7 and 8. <figref idref="f0024">Figs. 24A and 24B</figref> show examples in which the prediction methods 1 to 8 are assigned to the sub-blocks on the basis of this definition. In <figref idref="f0024">Fig. 24A</figref> the distinction of intra/inter is made along the diagonal direction and two motion vectors are used in inter prediction.

<figref idref="f0024">Fig. 24B</figref> is an example in which the macroblock is divided into upper and lower segments and in which the prediction is performed by intra prediction for the upper segment and by inter prediction for the lower segment. In this example only one motion vector is used for the inter prediction. In the description hereinafter, this prediction assignment information of many values will be called many-valued prediction identification map information.

Since the discrimination between the intra 16×16 mode and the 16×16 pixel unit motion compensation mode (hereinafter, an inter 16×16 mode) does not require the prediction assignment information of 4×4 sub-block unit, it can be implemented by only identification based on the macroblock type information. Namely, the macroblock type information is classified under three types of the intra 16×16 mode, the inter 16×16 mode, and sub-block unit arbitrary prediction assignment. Then, in the case of the mode of sub-block unit arbitrary prediction assignment, the prediction methods for all the sub-blocks are settled by coding the above many-valued prediction identification map information.

In this example, the motion detector 2 of the coding apparatus can select a mode with the best coding efficiency by evaluating possibilities of all the intra 16x16 mode, inter 16x16 mode, and sub-block unit arbitrary prediction assignment. Of course, the apparatus may be configured to perform coding with some fixed combinations of modes. A variety of techniques can be considered for the optimal detection of sub-block unit prediction, and, for example, by extending the method shown in <figref idref="f0014">Fig. 14</figref> in the second embodiment, the map information can be settled, for example, by a method of applying the intra prediction to each sub-block with a prediction evaluation value greater than that of intra prediction out of the exceptional sub-block regions.

The following will describe coding methods of the many-valued prediction identification map information shown in <figref idref="f0024">Figs. 24A and 24B</figref>. This map information can be coded by much the same coding method as that of the motion vector assignment information described in the second embodiment and the third embodiment. The difference is that, while the information of the object of coding was the binary map in the second embodiment and the third embodiment, the object of coding in the present embodiment is a gray scale map.

(1) Coding method 1

For implementation by the method of the second embodiment, individual mode information is expanded into bit planes. For example, the bit planes can be classified into a plane indicating either intra or inter, planes indicating use or nonuse of the individual intra prediction methods (a total of six planes), and a plane for assignment of motion vector. Each of these planes can be coded by the method described in the second embodiment. For example, if the many-valued prediction identification map information of <figref idref="f0024">Fig. 24A</figref> is decomposed into the bit planes according to the above rule, the result will be as shown in <figref idref="f0025">Figs. 25A to 25C</figref>. Here the intra/inter classification plane of <figref idref="f0025">Fig. 25A</figref> and the motion vector assignment plane of <figref idref="f0025">Fig. 25C</figref> both are constructed using the prediction priority context, while the planes of the intra prediction methods are constructed as bit planes based on only the presence or absence of the prediction methods.

The information of the prediction mode 3 in the present embodiment can be expressed by coding the binary maps of the total of eight planes shown in <figref idref="f0025">Figs. 25A to 25C</figref>, according to a predetermined order by the method of the second embodiment. It is also possible to adopt a configuration wherein discrimination of intra/inter is first transmitted and wherein as to the six planes of <figref idref="f0025">Fig. 25B</figref> concerning the intra prediction methods and the plane of motion vector assignment of <figref idref="f0025">Fig. 25C</figref>, only the sub-blocks corresponding to intra and inter, respectively, are used as bit plane data, as shown in <figref idref="f0026">Figs. 26B and 26C</figref> (i.e., the gray portions in <figref idref="f0026">Figs. 26B and 26C</figref> are excluded from the object of coding). This makes it feasible to efficiently reduce the amount of information to be coded. The above plane information may be arranged to be coded by the coding method of the third embodiment.

(2) Coding method 2

Another potential coding method as a modification of the third embodiment is a method of setting each unchanging point of a prediction method to 0 and expressing a continuous unchanging zone of the same prediction method by a run. When this method is applied to the case of <figref idref="f0024">Fig. 24A</figref>, it is transformed into data as shown in <figref idref="f0027">Fig. 27</figref> (where each change point is detected by the horizontal prediction priority context). This information is coded in sets of zero runs and IDs of the prediction methods of change points. In this example, using the horizontal scan of <figref idref="f0023">Fig. 23B</figref>, the information can be expanded into sets of {(5, 7), (0, 1), (2, 7), (3, 8), (1, 7)}. These sets are assigned respective variable length codes to be coded. The scan table may be arranged so that a flag is prepared therefor and so that an efficient table is used by switching among tables.

In this case, it is also possible to adopt a configuration wherein the changes by the values of 7 and 8 indicating the inter prediction are assumed not to be changes of the prediction method and are regarded as unchanging points and wherein the plane of motion vector assignment information is separately coded.

(3) Coding method 3

Furthermore, the coding method may be configured to expand so as to add the flag of inter prediction to the intra prediction mode information in the H.26L coding system of the conventional example and transmit only the inter prediction portions in the form of the motion vector assignment plane.

(4) Coding method 4

Intra/inter classification patterns and motion vector assignment patterns are fixedly arranged, for example, as shown in <figref idref="f0006">Figs. 6A to 6D</figref>. Since all the intra/inter division situations and motion vector assignment situations can be identified as fixed pattern IDs between encoder and decoder, the IDs of these patterns are subjected to variable length coding in the order of their frequencies of occurrence. Since it is also considered that the intra/inter division patterns and the motion vector assignment patterns (equivalent to those in the first embodiment) have high correlations with patterns selected in neighboring macroblocks, the coding method may also be arranged in such a manner that a context is defined based on the situations of the neighboring macroblocks, as in the first embodiment, for the intra/inter division patterns as well and that variable length coding tables or probability tables for arithmetic coding are arranged to be switched according to the context.

Syntax examples of the prediction mode 3 coded by the above methods are presented in <figref idref="f0028 f0029 f0030 f0031">Fig. 28 to Fig. 31. Fig. 28 to Fig. 31</figref> correspond to the above coding methods 1 to 4, respectively. In the coding method 1, as shown in <figref idref="f0028">Fig. 28</figref>, the motion vector assignment information is coded on a bit plane basis. The prediction priority context may be defined in the closed form within the same macroblock, as described in the second embodiment, or may be arranged not to be used.

In the coding method 2, as shown in <figref idref="f0029">Fig. 29</figref>, the scan table flag information for identifying the scan table is multiplexed subsequent to the prediction priority context. This is not required in the case where the scan table is determined depending upon the prediction priority context and in the case where the scan table is fixedly determined. Subsequently, sets of zero runs and IDs of prediction methods of change points are transmitted by the number obtained as a result of the scan.

In the coding method 3, as shown in <figref idref="f0030">Fig. 30</figref>, the extended information including the inter prediction flag in addition to the intra prediction mode information implements such expansion as to be able to designate the total of seven types of methods including the six types of intra prediction methods and the inter prediction method, and the syntax is arranged to transmit this expanded information, and the motion vector assignment information for designating the motion vector assignment in the inter prediction case.

In the coding method 4, as shown in <figref idref="f0031">Fig. 31</figref>, the macroblock type information contains the fixed mode assignment patterns including the intra/inter classification pattern and the motion vector assignment pattern, and is expanded as data to uniquely identify each of the very large number of prediction mode values. Then the identification information of the intra prediction mode is separately transmitted for only 4×4 sub-blocks within each region of intra prediction designated by the macroblock type information. As in this syntax, it is also possible, for example, to employ a configuration using the intra prediction mode identification information in sub-block units (intra prediction mode information), used in the intra 4×4 mode of the H.26L coding system, as it is.

In <figref idref="f0028 f0029 f0030 f0031">Figs. 28 to 31</figref>, arrows P16 to P25 represent omission of pertinent information, an arrow Q7 up to sixteen loops, and arrows Q6 and Q8 to Q10 up to two loops.

The decoding apparatus is arranged to receive the syntax in one of the above various configurations, settle the prediction mode assignment in the macroblock according to the procedure reverse to the procedure defined in the associated coding method, and decode the video signal, on the basis of the decoding operation flow of <figref idref="f0012">Fig. 12</figref>, <figref idref="f0020">Fig. 20</figref>, or the like.

The coding apparatus and decoding apparatus described above make it feasible to capture various change states in the macroblock by arbitrary division in sub-block units and to implement efficient video transmission, recording, and playback with a small overhead.

In the present embodiment, the prediction mode definition may be arranged to set the number of motion vectors to three or four and additionally assign the motion vectors respective IDs of prediction methods thereof.

The fifth embodiment will be described below. The present embodiment will describe an example in which another embodiment of the motion vector detecting processing and motion vector prediction method is implemented in the coding apparatus and decoding apparatus of the first embodiment.

When the inter prediction modes of <figref idref="f0006">Figs. 6A to 6D</figref> described in the first embodiment are used, the detection method of motion vector in each mode can be any method as long as it can be interpreted by the predetermined syntax as described in the operation of the decoding apparatus in the first embodiment. However, the present embodiment will describe a motion vector detecting technique of increasing the prediction efficiency without much increase in the load of computational complexity, and the coding apparatus and decoding apparatus employing a motion vector prediction rule associated therewith. In the description below, the motion vector detection processing is carried out in the motion detector 2 of <figref idref="f0001">Fig. 1</figref>, and the motion vector prediction processing is carried out in the variable length encoder 23 (on the coding apparatus side) of <figref idref="f0001">Fig. 1</figref> and in the variable length decoder 25 (on the decoding apparatus side) of <figref idref="f0002">Fig. 2</figref>. In the description hereinafter, the operations will be described according to the flowcharts of these processing.

In the case of the inter prediction mode set in the first embodiment shown in <figref idref="f0006">Figs. 6A to 6D</figref>, one or two motion vectors have to be detected per macroblock. In the low rate coding, the amount of codes that can be used for expression of the orthogonal transform coefficients is decreased with increase in the number of motion vectors, and it is thus desirable to perform the detection of motion vectors in consideration of a trade-off between the cost for the amount of codes for motion vectors and the accuracy of prediction with the detected motion vectors. In the H.26L video coding system as a basis of the first embodiment, MVi(n,j) (n: macroblock location and j: segment number) represents the motion vectors detected in a reference frame RFi (i ≥ 1) temporally previous by i frames, Rp represents the bit amount necessary for coding of the motion vectors MVi(n,j) and the reference frame identification information RFi, and cost Cp is defined by Eq (1) below, using the predictive residual power Dp obtained in that case and constant λ; the motion vectors MVi(n,j) and reference frame RFi (i ≥ 1) to minimize the cost Cp are determined. The constant λ is set so as to increase with decrease in the target coding bit rate, and thus constraints due to the bit amount Rp become severer is low rate coding. <maths id="math0001" num="(1)"><math display="block"><mi>Cp</mi><mo>=</mo><mi>Dp</mi><mo>+</mo><mi mathvariant="normal">λ</mi><mi>Rp</mi></math><img file="EP3399747B1_D0001.tif" /></maths>

Since the predicted value is first determined and the prediction difference is then coded for each motion vector as described in the first embodiment, the bit amount Rp becomes smaller as the motion vector detected approaches the predicted value. For this reason, in the H.26L video coding system, it is recommended that a center point of a motion vector search range be set at the motion vector predicted value and the location of the motion vector search widow be adopted segment by segment. This decreases at least the amount of codes of motion vectors and relaxes the constraints due to the bit amount Rp on the minimization of the cost Cp in the above equation, and the motion vector detection can be performed under advantageous conditions based on the minimization of the predictive residual power Dp. Even with consideration to the continuation of motion from neighboring macroblocks, it is expected that the adaptation of the search window location for the predicted value can also lead to decrease of the predictive residual power Dp. On the other hand, there arises a problem that the adaptation of the search window increases the load of calculation processing of the predictive residual power.

In order to explain this problem, <figref idref="f0036">Fig. 36A</figref> schematically shows a case with the optimization of the motion vector search range and <figref idref="f0036">Fig. 36B</figref> a case without the optimization of the motion vector search range. As shown in <figref idref="f0036">Fig. 36B</figref>, where the search range is set constant independent of segments, it is possible to reduce the number of calculations of the predictive residual power by making use of the fact that shapes of segments are hierarchical.

For example, in <figref idref="f0006">Fig. 6D</figref>, if the calculation of the predictive residual power is carried out for all the motion vector candidates with the search window uniquely determined for the upper segment (white segment) of Mode 13, the predictive residual power calculation does not have to be performed again in Mode 9 as to the three sub-blocks in the upper segment of Mode 13 and the predictive residual power calculation shall be performed for the remaining three sub-blocks. In contrast to it, in <figref idref="f0036">Fig. 36A</figref>, assuming that the motion vector prediction rule of <figref idref="f0010">Fig. 10D</figref> is used, the upper segment of Mode 13 can no longer use the common search location to the same portion of Mode 9, and the result of the predictive residual power calculation thereof cannot be reused.

Therefore, the present embodiment will describe the motion vector detection processing and motion vector prediction rule to improve the prediction accuracy by effecting the adaptation of the search window in each segment while keeping down the computational complexity. The motion vector prediction rule of the present embodiment is fixedly defined as shown in <figref idref="f0037">Figs. 37A to 37D</figref>. This rule includes less variations of prediction locations used than in <figref idref="f0010">Figs. 10A to 10D</figref>, and roughly only four types of motion vector predictions are used.

The first type is a prediction of the upper segment in Mode 0 and Modes 9, 10, 13, and 14 (MV prediction ①), and in this case, it is the median predication using motion vectors at locations of three sub-blocks (4×4 blocks) surrounded with dotted lines.

The second type and the third type are predictions in Modes 1-8, 11, and 12 and, as shown in <figref idref="f0037">Figs. 37B to 37D</figref>, they are defined as predictions using a motion vector of a sub-block at the left or upper fixed location according to a target segment (MV predictions ② and ③, wherein ② is a prediction from the left and ③ a prediction from above) .

The fourth type is a prediction of the lower segment in Modes 9, 10, 13, and 14, and in this case, it is a prediction using a sub-block at a dotted-line location adjacent to the right upper corner sub-block in the macroblock (MV prediction ④).

In the case where a motion vector at a location used for the prediction refers to a reference frame different from that of a motion vector to be predicted at present and in the case where no motion vector is defined because of the intra coding, the median prediction used for Mode 0 and the upper segments in Modes 9, 10, 13, and 14 is applied as it is. <figref idref="f0010">Figs. 10A to 10D</figref> showed the application of the individual prediction rules to the respective modes and respective segments, whereas the application of the prediction rule in the present embodiment concentrates the prediction ways to up to four types. This can largely decrease the number of calculations of the predictive residual power even if the search window adapted to the predicted value is set upon the search for the motion vector.

<figref idref="f0038">Fig. 38</figref> shows a flowchart of the motion vector detection processing carried out in the motion detector 2 of the coding apparatus by making use of the above motion vector prediction rule. The motion vector detection processing making use of the above motion vector prediction rule will be described below with reference to <figref idref="f0038">Fig. 38</figref>.

First, the motion vector predicted value is calculated by MV prediction ① and this is defined as a center location of search window ① (SA1). First detected in this search window ① is a motion vector (and a reference frame) to minimize the cost Cp for Mode 0 (SA2). At this time, for the respective sub-blocks in the macroblock, predictive residual powers (calculated as prediction evaluation values (SAD)) obtained for motion vector candidates in the search window ① all are retained as SAD values ① (SA3). The SAD values ① can be reused on the occasion of determining the motion vectors and reference frames in Modes 9, 10, 13, and 14 using the same MV prediction ① (SA4). Namely, the motion vectors and reference frames to minimize the cost Cp as to Modes 9, 10, 13, and 14 can be determined by selecting them from the values retained as the SAD values ① and adding them, which eliminates the need for executing the calculation of predictive residual power (SAD).

It is then determined in SA5 whether the MV predictions ② and ③ can be used for Modes 1-8, 11, and 12. If as to Modes 1-8, 11, and 12 to use the MV predictions ②, ③, the motion vectors at the prediction locations used in the MV predictions ②, ③ refer to different reference frames or the intra coding is applied, it is determined that the MV predictions ②, ③ cannot be used, and the motion vectors and reference frames are determined using the SAD values ① (SA8). If it is determined in SA5 on the other hand that the MV predictions ②, ③ can be used, the motion vector predicted value obtained using the MV prediction ② or ③ is set as the center location of the search window ②, ③ (SA6), and the motion vector (and the reference frame) to minimize the cost Cp for each of Modes 1-8, 11, and 12 is detected within this search window ②, ③ (SA7). Thereafter, similar processing to SA5-SA8 is carried out in SA9-SA12 for the lower segments of Modes 9, 10, 13, and 14. In the last step SA13, a mode yielding the minimum cost Cp is selected out of all the modes.

The above motion vector detection processing allows the amount of SAD calculation to be further reduced by determining the order of the motion vector calculation according to the sizes of the segments in each of the processes of SA4, 7, 8, 11, and 12. For example, concerning the relation among Modes 9, 10, 13, and 14, there is a relation of Mode 13 ⊂ Mode 9 ⊂ Mode 10 ⊂ Mode 14 about their upper segments. Namely, the result of the SAD calculation for the upper segment of Mode 13 can be applied to the SAD calculation for the upper segment of Mode 9 as it is, which can reduce the number of addition operations as compared with the direct addition from the SAD values ①. The same also applies to Modes 1-8, 11, and 12, and it is therefore feasible to keep down the computational complexity, by implementing the motion detection processing according to the hierarchical property of the modes.

On the other hand, the decoding apparatus can be arranged to have the decoding processing of the motion vector syntax in the variable length decoder 25 to determine the predicted value while adopting the motion vector prediction rule shown in <figref idref="f0037">Figs. 37A to 37D</figref>, instead of the motion vector prediction rule of <figref idref="f0010">Figs. 10A to 10D</figref>, and decode the motion vector.

The sixth embodiment will be described below. The present embodiment will describe coding and decoding methods using the motion vector division patterns in the first embodiment, together with the bidirectional inter prediction using both the forward inter prediction and the backward inter prediction, and permitting one of prediction directions of the bidirectional prediction to be selected for each divisional segment in the macroblock.

Just as in the case of the first embodiment, the present embodiment can be described with the same members and operations as the coding apparatus and decoding apparatus shown in <figref idref="f0001">Figs. 1</figref> and <figref idref="f0002">2</figref> of the conventional example, except for the differences in the syntax about the prediction mode 3 and motion vector 4 included in the compressed stream 24 and in the operations of the motion detector 2 and motion compensator 5. The following will mainly describe the operation of the motion detector 2 and the syntax as well about the coding apparatus, and will mainly describe the procedure of generating the predicted image in the motion compensator 5 about the decoding apparatus.

The motion compensation models, i.e., the definition of the fixed motion vector assignment in the present embodiment is the same as in the first embodiment. Namely, in order to divide a macroblock into two segments, as shown in <figref idref="f0006">Figs. 6A to 6D</figref>, the present embodiment adopts the motion vector assignment expanded to the division ways including the horizontal, vertical, oblique, and phase-added division, different from the simple horizontal division or vertical division.

In the present embodiment, for the segments resulting from the division by the motion vector assignment, a prediction direction can be selected out of those of the bidirectional inter prediction on a segment basis. This presents the following advantage: in the case where a boundary between objects of different motions exists in one macroblock, for the segments permitting various motions in the macroblock to be accurately captured with a small overhead, a prediction direction capable of yielding better coding efficiency can be selected and assigned out of the plurality of prediction directions in the bidirectional prediction on a segment basis, thereby increasing the prediction efficiency.

<figref idref="f0039">Fig. 39</figref> shows an example of the bidirectional prediction in the present embodiment. <figref idref="f0039">Fig. 39</figref> shows a case in which the division of Mode 9 in <figref idref="f0006">Figs. 6</figref> is applied to a macroblock M in a bidirectional prediction frame Bt and in which the forward prediction F1 from a temporally previous reference frame Pt□1 and the backward prediction B1 from a temporally subsequent reference frame Pt+1 are applied to the respective two segments in the macroblock.

For coding the macroblock M, the motion detector 2 in <figref idref="f0001">Fig. 1</figref> first evaluates and detects a prediction mode and motion vector capable of yielding better coding efficiency, as an inter prediction mode, out of the prediction modes shown in <figref idref="f0006">Figs. 6A to 6D</figref>. At this time, the present embodiment is arranged to evaluate and detect a prediction direction capable of yielding better coding efficiency, out of the prediction directions in the bidirectional prediction for each of the two segments in each of the prediction modes. <figref idref="f0039">Fig. 39</figref> shows the case where as a result of the evaluation and detection, Mode 9 is selected as a prediction mode in the macroblock M and the different prediction directions are selected for the respective segments. This selection result is transmitted as information in the compressed stream described below.

<figref idref="f0040">Fig. 40B</figref> shows a syntax of the macroblock data of the compressed stream outputted from the coding apparatus of the present embodiment, in comparison with a syntax (<figref idref="f0040">Fig. 40A</figref>) in the bidirectional motion compensated prediction in H.26L.

In the H.26L syntax shown in <figref idref="f0040">Fig. 40A</figref>, the information of the prediction direction is transmitted one per macroblock in the prediction mode macroblock type information indicating the motion vector division pattern, and is identified together with the prediction mode. A like configuration can also be adopted in the case using the syntax in the bidirectional prediction in the motion compensation models or the fixed motion vector assignment of the present invention, and the information can also be configured and transmitted as prediction mode macroblock type information also including the information about the selection situation of the prediction direction for each segment. However, the present embodiment employs a configuration different from the configuration in H.26L, thereby preventing the variable length coding table of the prediction mode from becoming massive.

<figref idref="f0040">Fig. 40B</figref> shows the syntax in the present embodiment. In this syntax the information of the prediction direction is arranged so that only the identification of the Direct mode as a prediction mode for the skip macroblocks in the bidirectional prediction is transmitted in the macroblock type information and so that the information of the prediction direction in the other modes is transmitted as reference frame information to be identified together with the reference frame number. The present embodiment does not use the block sizes introduced in order to identify the prediction mode in each direction in the bidirectional prediction in H.26L. In <figref idref="f0040">Figs. 40A, 40B</figref> arrows P28 to P36 indicate omission of pertinent processing to jump, and arrows Q12 to Q19 loops.

<figref idref="f0041">Fig. 41</figref> shows a code table of the macroblock type information in the present embodiment. The configuration of this code table may be much the same as the configuration of the macroblock type information used in the first embodiment, except that the Direct mode is placed at the head of the code table. The definitions about the intra 16×16 mode at and after the code number 17 are omitted herein, but these are assumed to be based on the definitions about the intra 16×16 mode in the code table of H.26L. The subsequent syntax shall differ depending upon the contents of the macroblock type information, and in many prediction modes there exist two reference frame information elements, because the reference frame information is present in each segment. However, there is only one reference frame information in Mode 0 being the prediction mode without segment division, and in the intra 4×4 mode there is no reference frame information but there is the intra prediction mode information.

<figref idref="f0042">Fig. 42</figref> shows a code table of the reference frame information in the present embodiment. In the configuration of the reference frame information in H.26L, numbers for identifying the reference frame numbers in the forward prediction are arranged in order, whereas the code table herein is configured to contain the information about the forward direction (Forward), the backward direction (Backward), and the two directions (Bidirectional) to use an average of predicted values in the forward direction and in the backward direction, in addition to the reference frame numbers. In addition, there exists the reference frame information of each segment. Since a reference frame can be selected from a plurality of reference frames in the case of the forward prediction, the table is configured so that codes are arranged in order with change of reference frames in the forward direction for each of the forward prediction and bidirectional prediction. Since the prediction direction is identified by the reference frame information, the subsequent syntax will differ depending upon the contents of the reference frame information: there will exist a forward motion vector difference FW in the case of the forward prediction, a backward motion vector difference BW in the case of the backward prediction, and both the motion vector difference FW and motion vector difference BW in the bidirectional prediction. The number of motion vector differences will differ depending upon the prediction mode identified by the macroblock type information.

The reference frame information code in <figref idref="f0042">Fig. 42</figref> also exists for each segment even in the case where the function of plural reference frames in H.26L is not used, i.e., in the case where there exists only the reference frame number of forward prediction of 1 (one frame back of Forward), and in this case only the prediction direction in the bidirectional prediction is identified from the reference frame information.

On the other hand, the decoding apparatus performs the decoding processing on the basis of these information obtained from the compressed stream, and the processing is much the same as the flow shown in the first embodiment. Therefore, the detailed description thereof is omitted herein. The decoding apparatus of the present embodiment is different from the decoding apparatus of the first embodiment in that the information obtained from the compressed stream contains the information about the selection situation of the prediction direction in the bidirectional prediction differing depending upon segments in the prediction mode and in that in accordance therewith the motion compensator 5 in <figref idref="f0002">Fig. 2</figref> performs the motion compensation and generation of the predicted image by use of the prediction direction in the bidirectional prediction differing segment by segment. This makes it feasible to generate the predicted image obtained by assigning the prediction direction capable of yielding better prediction efficiency to each segment and to obtain a decoded picture with better coding efficiency from the compressed stream.

The present embodiment was adapted to use the motion compensation models as shown in <figref idref="f0006">Figs. 6A to 6D</figref>, but the system may also be adapted to simultaneously use the motion compensation models permitting a number of motion vectors as shown in <figref idref="f0004">Figs. 4A to 4G</figref>, or to use them while being changed over from or to the compensation models of <figref idref="f0006">Figs. 6A to 6D</figref>. In that case, it is also feasible to improve the prediction efficiency in such a way that the change of prediction is allowed for each segmental block, the number of divisions is assumed to become not less than 2, the syntax and coding and decoding methods presented in the present embodiment are also applied in similar fashion, and the prediction direction capable of yielding better coding efficiency is selected and assigned to each block in the macroblock. When the number of divisions becomes greater than 2 in this case, the overhead of the information about the selection situation becomes large in the case where the selection of the prediction direction is performed for each block. For this reason, it is possible to adopt a configuration wherein the selection of the prediction direction is allowed only in the case where the prediction mode with the number of divisions being 2 is used and wherein whether the information about the selection situation in each block is transmitted is switched depending upon the prediction mode used in each individual macroblock.

Since the information about the selection situation of the prediction direction for each segment is transmitted as additional information, in the case of a simple picture without need for such switching, it is possible to employ a configuration wherein a rule of keeping the prediction direction constant within each macroblock can be selected. In this case, for example, it is conceivable to use a method of multiplexing flag information for identifying whether the change of prediction direction in the macroblock is permitted, in units of frames or frame groups. This permits the decoding apparatus to operate on the assumption that there exists only one syntax including the selection situation of the prediction direction, per macroblock if the prediction direction is unchanged in the macroblock.

The present embodiment described the coding and decoding methods of performing the motion compensated prediction by selecting the prediction direction used in the bidirectional inter prediction for each segment in the macroblock, but the same methods can also apply to construction of coding and decoding methods of performing the inter prediction or the intra prediction by selecting the inter prediction or the intra prediction for each segment in the macroblock. When this configuration is adopted, the intra prediction can be selectively assigned to only segments for which effective prediction cannot be achieved by the inter prediction, which can further improve the prediction efficiency.

The coding method and decoding method according to the present embodiment described above make it feasible to accurately capture various motions in the macroblock with a small overhead, to apply the appropriate bidirectional inter prediction or intra prediction to each of segments representing respective different motions, and to implement efficient video transmission, recording, and playback.

Incidentally, in order to achieve the aforementioned object of the present invention, image processing systems according to the present invention can be embodied by employing a variety of configuration forms below.

Namely, an image processing system according to the present invention can be constructed by adopting a configuration wherein in a coding apparatus motion compensated prediction means is configured to select one of a plurality of pattern groups obtained by preliminarily grouping motion vector assignment patterns to second blocks defined in each first block unit and to perform motion compensated prediction while assigning a motion vector to second blocks on the basis of an assignment pattern included in the selected pattern group and assignment information coding means is configured to output information about a motion vector assignment situation coded in each first block unit, as identification information of the motion vector assignment pattern specified out of the selected pattern group; and wherein in a decoding apparatus assignment information decoding means is configured to decode motion vector assignment information, as information to identify a motion vector assignment pattern to second blocks preliminarily determined in each first block unit, to, on the occasion of specifying an assignment pattern from the assignment pattern identification information, decode information to identity a pattern group to which the assignment pattern belongs, and to determine motion vector assignment to the second blocks from the assignment pattern identification information in accordance with a definition of the pattern group specified by the pattern group identification information.

Another image processing system according to the present invention can be constructed by adopting a configuration wherein in a coding apparatus assignment information coding means is configured to determine a predicted value of a motion vector according to a shape of a motion vector assignment pattern for a first block as an object of coding and to code a prediction difference based on the predicted value, as motion vector information; and wherein in a decoding apparatus assignment information decoding means is configured to decode motion vector information obtained by coding a prediction difference based on a predicted value of a motion vector determined according to a shape of a motion vector assignment pattern for a first block as an object of decoding.

Another image processing system according to the present invention can be constructed by adopting a configuration wherein in a coding apparatus assignment information coding means is configured to determine a prediction candidate location of a motion vector according to a shape of a motion vector assignment pattern for a first block as an object of coding to determine as a predicted value one of prediction candidate locations according to a shape of an assignment pattern for a first block located in the vicinity of the first block as the object of coding, and to code a prediction difference of the predicted value as motion vector information; and wherein in a decoding apparatus assignment information decoding means is configured to decode motion vector information obtained by determining one of prediction candidate locations for a motion vector determined according to a shape of a motion vector assignment pattern for a first block as an object of decoding, as a predicted value according to a shape of an assignment pattern for a first block located in the vicinity and coding a prediction difference of the predicted value.

Another image processing system according to the present invention can be constructed by adopting a configuration wherein in a coding apparatus motion compensated prediction means is configured to perform motion compensated prediction while assigning a motion vector to second blocks on the basis of a condition that the maximum number of motion vectors that can be assigned in second block units is 2 and on the basis of one of a plurality of predetermined assignment patterns determined in each first block unit and indicating an assignment state to second blocks included in the first block and assignment information coding means is configured to output information about a motion vector assignment situation determined in each first block unit, as identification information of the assignment pattern; and wherein in a decoding apparatus the maximum number of motion vectors decoded in each first block unit is set to 2 and motion vector assignment information is decoded as information to identify a plurality of predetermined assignment patterns determined in each first block unit and indicating assignment states of motion vectors to second blocks included in the first block.

Another image processing system according to the present invention can be constructed by adopting a configuration wherein a coding apparatus comprises compensated prediction means for performing motion compensated prediction while selecting one reference frame out of a plurality of reference frames retained for the motion compensated prediction, in a unit consisting of one or more second blocks obtained by sub-dividing each of first blocks resulting from division of a frame of a moving picture; and reference frame information coding means for outputting information about a selection situation of a reference frame for one or more second blocks in a multiplexed state on a bitstream; and wherein a decoding apparatus comprises reference frame information decoding means for decoding information about a selection situation of a reference frame used for the motion compensated prediction, assigned in a unit consisting of one or more second blocks obtained by sub-dividing each of first blocks resulting from division of a frame of a moving picture; compensating means for generating a predicted image by performing motion compensation while selecting one reference frame out of a plurality of reference frames retained for the motion compensation, on the basis of the reference frame information.

Another image processing system according to the present invention can be constructed by adopting a configuration wherein a coding apparatus comprises motion compensated prediction means for performing motion compensated prediction while selecting a prediction direction used in bidirectional inter prediction, in a unit consisting of one or more second blocks obtained by sub-dividing each of first blocks resulting from division of a frame of a moving picture; and prediction information coding means for outputting information about a selection situation of the prediction direction for the one or more second blocks in a multiplexed form on a bitstream; and wherein a decoding apparatus comprises prediction information decoding means for decoding information about a selection situation of a prediction direction used in bidirectional inter prediction, assigned in a unit consisting of one or more second blocks obtained by sub-dividing each of first blocks resulting from division of a frame of a moving picture; and motion compensation means for generating a predicted image by performing motion compensation while selecting a prediction direction used in bidirectional interframe motion compensation out of reference frames retained in both a forward direction and a backward direction, based on the prediction information.

Another image processing system according to the present invention can be constructed by adopting a configuration wherein a coding apparatus comprises predicting means for performing inter prediction or intra prediction while selecting an inter prediction mode or an intra prediction mode in a unit consisting of one or more second blocks obtained by sub-dividing each of first blocks resulting from division of a frame of a moving picture; and prediction mode information coding means for outputting information about a selection situation of the inter prediction mode or the intra prediction mode for the one or more second blocks in a multiplexed form on a bitstream; and wherein a decoding apparatus comprises prediction mode information decoding means for decoding information about a selection situation of the inter prediction mode or the intra prediction mode assigned in a unit consisting of one or more second blocks obtained by sub-dividing each of first blocks resulting from division of a frame of a moving picture; and predicted image generating means for generating a predicted image by performing the inter prediction or the intra prediction while selecting the inter prediction mode or the intra prediction mode, based on the prediction information.

Industrial Applicability

As described above, the present invention made it feasible to accurately capture various motions in the first block with a small overhead and to implement efficient video transmission, recording, and playback.