Image encoding method, image encoding apparatus, and image encoding program

The present invention relates to an apparatus, method, and program for encoding a moving image or a still image based on a technique such as MPEG.

In recent years, video coding has been widely applied to satellite broadcasting, storage media, and the like. MPEG2 Video is widely used as a compression method, and the standard is described in Non-Patent Document 3. MPEG2 is a compression technology that uses motion compensation and DCT (discrete cosine transform).

An MPEG2 coding apparatus will be briefly described based on Non-Patent Document 1. FIG. 3 shows the basic configuration of the encoder, which is based on the figure on p.71 of Non-Patent Document 1. The coding process will be described with reference to FIG.

If the video input is an analog input, it is digitized by the A / D converter 50. If the input resolution and the coding resolution are different, the format conversion unit 51 converts the spatial resolution.

There are three types of picture, I, P, and B. Since the B picture is encoded after the later I and P pictures are encoded in the input order (display order), the screen rearrangement unit 52 rearranges the screen and converts it into the frame order in the coding order. ..

Coding is performed for each screen in macroblock (16 pixels × 16 pixels) units. The macroblock coding order is left-to-right and top-to-bottom on the screen. In I-pictures, all macroblocks are intra-coded (no reference to other pictures). In P-pictures and B-pictures, macroblocks are intra-coded or inter-coded (see other pictures). In the inter-coding, the motion vector detected by the motion vector detection unit 60 is used, and the motion compensation mode selection unit 61 predicts from other pictures and encodes the difference from the predicted value. Figure 3 shows the case of inter-coding (in the case of intra-coding, motion compensation is not performed).

The processing for each macroblock (MB) will be described. In the case of an intra, DCT is performed by the DCT unit 53 on four blocks (8 × 8) of brightness and two blocks (8 × 8) of color difference. In the case of intercoding, motion compensation prediction is performed based on the motion vector, and DCT is performed on four luminance blocks and two color difference blocks, which are differences from the predicted values.

As a result of DCT, the DCT coefficient is output. The DCT coefficient is quantized by the quantization unit 54, and is output by variable length coding (VLC) by the variable length coding unit 55. If the output bit rate is constrained, the rate control unit 57 controls the rate and reflects it in the quantization step.

The quantized data is locally decoded. The DCT coefficient after quantization is dequantized by the inverse quantization unit 58, inverse DCT is performed by the inverse DCT unit 59, motion compensated (in the case of intercoding), and temporarily stored in the video memory 62. The locally decoded image stored in the video memory is used as a reference frame for encoding P-pictures and B-pictures.

An MPEG2 decoding device will be briefly described based on Non-Patent Document 1. FIG. 4 shows the basic configuration of the decoder, and is based on the figure on p.71 of Non-Patent Document 1. The decoding process will be described with reference to FIG.

The input data is variable-length decoded by the variable-length decoding unit 71, and the quantized DCT coefficient and the motion vector and other information are separated. The quantized DCT coefficient is inversely quantized by the inverse quantization unit 72, and is inverse DCT by the inverse DCT unit 73 to obtain image data. In the case of the inter-coded macroblock, the motion-compensated image data is further added by the motion compensation unit 77 using the motion vector.

In decoding, the processing order of macroblocks is the same as in coding, from left to right and from top to bottom. After decoding one frame, the I picture and P picture are temporarily saved in the video memory 78 for use as a reference frame when decoding other frames. The B picture decoded later may come first in the display order. In this case, the screen rearranging unit 74 rearranges the output order of the frames using the images stored in the memory.

In hardware encoding and decoding, the above-mentioned macroblock processing may be performed by a pipeline method. Pipelining processing for macroblocks will be described based on Non-Patent Document 2. FIG. 5 is a conceptual diagram of macroblock pipeline processing created based on p.126 of Non-Patent Document 2. Since the encoder of Non-Patent Document 2 has a configuration using two DSPs, transfer processing between DSPs (stage 3) is included, but if it is composed of one DSP, transfer processing is unnecessary. Is.

The macroblock pipeline processing will be described with reference to FIG. Figure 5 (a) shows the processing contents of each stage performed for the macroblock. The stage indicates the timing of processing, and the processing of one stage is not necessarily performed by one circuit unit.

Processing from stage 0 to stage 6 is performed for one macroblock. Data is entered in stage 0. In stage 1, frame / field DCT selection and motion compensation mode selection are performed. DCT will take place in Stage 2. In stage 3, the transfer takes place between the two DSPs. In stage 4, quantization and dequantization are performed. In stage 5, variable length coding and inverse DCT are performed. Frame reconstruction is performed in stage 6.

The macroblock pipeline processing will be described over time with reference to Fig. 5 (b). MB0 enters stage 0. MB0 finishes the process of stage 0 and enters stage 1, and at the same time, a new MB1 enters stage 0. MB0 enters stage 2, at the same time MB1 enters stage 1, and a new MB2 enters stage 0. In this way, seven stages from stage 0 to stage 6 operate in parallel. Seven stages of processing are required for each macroblock, but since seven stages operate in parallel, the processing of one macroblock is completed every time of one stage. By making the macroblock processing into a pipeline, it is possible to process at a speed up to 7 times faster than when the macroblock is not made into a pipeline. The effect of pipeline processing is great in speeding up the encoding of MEPG.

The pipeline processing of the encoder has been described based on FIG. 5, but similarly in decoding, it is possible to perform pipeline processing by dividing the macroblock processing into appropriate stages and operating each stage in parallel. .. Even in decoding, the speed can be increased by performing pipeline processing.<nplcit num="1"><text>Television Society ed., "MPEG" Ohmsha, 2001, p.69-71.</text></nplcit><nplcit num="2"><text>Gion, 6 others "DSP for real-time MPEG2 codec (VDSP2)" National Technical Report, 1994, Vol.40, No.6, p.122-128.</text></nplcit><nplcit num="3"><text>ISO / IEC 13818-2, Information technology --Generic coding of moving pictures and associated audio information: Video.</text></nplcit><nplcit num="4"><text>ITU-T H.264, Advanced video coding for generic audiovisual services.</text></nplcit><nplcit num="5"><text>ITU-T T.81, Information technology --Digital compression and coding of continuous-tone still images --Requirements and guidelines.</text></nplcit><nplcit num="6"><text>Joint Video Team (JVT) software, http://iphome.hhi.de/suehring/tml/index.htm</text></nplcit><nplcit num="7"><text>Yu-Wen Huang, Tu-Chih Wang, Bing-Yu Hsieh and Liang-Gee Chen, "Hardware architecture design for variable block size motion estimation in MPEG-4 AVC / JVT / ITU-T H.264", IEEE Int Symp Circuits Syst, 2003 Vol 2, p.796-799, 2003.</text></nplcit><nplcit num="8"><text>Gary J. Sullivan and Thomas Wiegand, "Rate-Distortion Optimization for Video Compression", IEEE Signal Processing Magazine, Nov 1998, p.74-90, 1998.</text></nplcit>

<p> As described above, the conventional encoder in which the basic configuration of the MPEG encoder is implemented by macroblock pipeline processing can process encoding including prediction between frames at high speed.</p><p> However, the conventional coding apparatus has a problem that pipeline processing is difficult in coding including in-frame prediction. This is because, in the case of inter-frame prediction, the encoding and local decoding of the reference frame have already been completed, but in the case of intra-frame prediction, the processing of the referenced area may be in the middle of the macroblock pipeline. Because there is.</p><p> For example, when the left macroblock in the same frame is used for intra-prediction (described later) in macroblock coding, the prediction of the macroblock to be encoded is performed until the encoding of the left macroblock and local decoding are completed. I can't do it. Therefore, it is difficult to implement the macroblock pipeline processing because the processing of each stage cannot be operated in parallel as in the conventional example.</p><p> The intra-prediction will be described in detail below. There is H.264 as a coding method using intra prediction. The H.264 standard is described in Non-Patent Document 4. H.264 uses techniques such as interframe prediction, intra prediction, integer conversion, entropy coding, and deblocking filter, and intra prediction related to the present invention will be described based on Non-Patent Document 4. H.264 coding is performed in macroblock units as in MPEG2.</p><p> The intra-prediction of H.264 will be explained. Intra-prediction is a technique for predicting by referring to already decoded pixels in the same frame and reducing the amount of code by encoding the difference between the input image and the predicted value. The area referenced in the intra-prediction must be encoded and locally decoded prior to the area to be encoded.</p><p> There are two types of H.264 intra-prediction, 16x16 and 4x4. Figure 10 shows H.264 macroblocks (16x16) and blocks (4x4). A 4x4 block is a 16x16 macroblock divided into 16 equal parts.</p><p> The intra 16 × 16 prediction will be described with reference to FIG. Hereinafter, the luminance will be described, but the same applies to the color difference. The current macroblock encoded by macroblock A. The 33 pixels indicated by (black circles) are used as reference pixels for the intra 16 × 16 prediction of macroblock A. If the macroblock A is located at the periphery of the screen and there is no reference pixel, 128 is used as the reference pixel value (the pixel value is 8 bits).</p><p> Predict 256 pixels of macroblock A using 33 reference pixels. The intra 16x16 prediction method has four modes, called vertical, horizontal, DC, and plane. The details of the prediction method are omitted because they have nothing to do with the essence of the present invention.</p><p> Importantly, when encoding macroblock A, the referenced pixels must be available. For that purpose, it is necessary to complete the encoding and local decoding of the left macroblock B including the reference pixel used for encoding the macroblock A, the upper macroblock C, and the upper left macroblock D. The encoding of macroblock A can be started only after the encoding of macroblocks B, C, and D is completed.</p><p> FIG. 9A shows the coding order of macroblocks by a conventional encoder. In a conventional encoder, it is the macroblock B on the left that encodes immediately before the macroblock A. The encoder cannot make an intra 16 × 16 prediction for macroblock A until the processing of macroblock B is completed. Therefore, it is necessary to sequentially perform macroblock processing, and there is a problem that pipeline processing is difficult.</p><p> For the sake of simplicity, a case where macroblock processing is performed in two stages, stage 0 and stage 1, will be described. Here, stage 0 performs processing including mode selection of intra prediction, and stage 1 performs encoding and local decoding using the result of stage 0. Currently, the encoding and local decoding results of the left macroblock are used for intra-prediction of the macroblock. Since stage 0 of the macroblock cannot be started at present until stage 1 of the macroblock on the left is completed, each stage cannot be operated in parallel. Figure 9 (b) shows the processing of each stage of the macroblock.</p><p> The intra 4 × 4 prediction will be described with reference to FIG. The current macroblock encoded by macroblock A. Block a is a 4x4 block encoded. The 13 pixels indicated by (black circles) are used as reference pixels in the intra 4 × 4 prediction of block a. There are 9 types of intra 4x4 prediction methods, called vertical, horizontal, DC, diagonal down left, diagonal down right, vertical right, horizontal down, vertical left, and horizontal up. The details of the prediction method are omitted because they have nothing to do with the essence of the present invention.</p><p> Since the pixels of macroblock B, macroblock C, and macroblock D are referred to in the intra 4 × 4 prediction of block a, the processing of macroblocks B, C, and D is completed prior to the encoding of macroblock A. There is a need. Further, considering the case where the block a is at the position b, since the block b refers to the pixel of the macroblock E, it is necessary that the processing of the macroblock E is completed prior to the encoding of the macroblock A. After all, the encoding and local decoding of macroblocks B, C, D, and E must be completed prior to the encoding of macroblock A.</p><p> As in the case of the intra 16 × 16 prediction, in the intra 4 × 4 prediction, the encoding of the macro block A can be started only after the encoding of the macro blocks B, C, D, and E is completed. Therefore, it is necessary to sequentially perform macroblock processing, and there is a problem that pipeline processing is difficult.</p><p> Depending on the coding standard, there is a coding method in which the motion vector is determined from the motion vector of the surrounding macroblock without coding the motion vector in the coding of the macroblock. Such a macroblock encoding method is called "spatial direct mode" in H.264.</p><p> The spatial direct mode of H.264 will be described based on Non-Patent Document 4. In H.264, blocks in B pictures can be encoded in spatial direct mode. FIG. 8 is an explanatory diagram of the spatial direct mode. Block A is a block to be encoded in the spatial direct mode. Block A is 16x16 or 8x8. The block B is a block containing a pixel located to the left of the upper left pixel of the block A. Block C is a block containing a pixel located above the upper left pixel of block A. The block D is a block containing a pixel located at the upper right of the pixel at the upper right of the block A. Blocks A, B, C and D are in the same frame.</p><p> The motion vector is not coded for block A, which is coded in the spatial direct mode. At the time of decoding, the motion vector of block A is determined by the median (median) of the motion vectors of blocks B, C, and D. By not coding the motion vector of block A, the amount of code can be reduced.</p><p> When coding a block in the spatial direct mode, the motion vectors of the left, top, and top right blocks of the coded block in the same frame are used. Therefore, if there is a block to be encoded in the spatial direct mode in the macroblock, it is necessary to complete the encoding of the left, top, and upper right macroblocks before currently encoding the macroblock.</p><p> In the coding using the spatial direct mode, as in the case of intra prediction, the encoding of the current macroblock can be started only after the encoding of the macroblocks on the left, top, and upper right of the current macroblock is completed. Can not. Therefore, it is necessary to sequentially perform macroblock processing, and there is a problem that pipeline processing is difficult.</p><p> An object of the present invention is to provide an image coding apparatus capable of pipeline processing of macroblocks even if the coding method is such that intra-prediction is performed. Another object of the present invention is to provide an image coding apparatus capable of pipeline processing of macroblocks even in a coding method using spatial direct.</p><p> Another object of the present invention is to provide an image coding apparatus capable of pipeline processing of motion vector search and encoding in a coding method using PMV (predicted motion vector). Another object of the present invention is to provide an image coding apparatus capable of performing motion vector search for a plurality of macroblocks in parallel in a coding method using PMV.</p>

<p> In order to solve the above-mentioned conventional problems, the image coding apparatus of the present invention is characterized in that a means for selecting a macroblock coding order is added to the conventional encoder described in the background art, and an intra prediction is performed. Alternatively, even when the spatial direct mode is used, macroblock pipeline processing can be performed.</p><p> The means for selecting the coding order of the macroblock of the present invention is characterized in that the coding of the macroblock of the next line is started before the coding of the macroblock for one horizontal line is completed. Further, as a means for selecting the order, the order number of the encoding of the macroblock currently used for the intra-prediction of the macroblock or the spatial direct mode prediction of the current macroblock is 2 than the order number of the current macroblock. It is characterized by being larger than or larger (one or more macroblocks exist in between).</p>

<p> According to the image coding apparatus of the present invention, macroblock pipeline processing becomes possible in the coding method using intra-prediction, and the processing speed can be increased.</p><p> Further, according to the image coding apparatus of the present invention, it is possible to perform pipeline processing of macroblocks in coding using spatial direct, and it is possible to increase the processing speed.</p><p> Further, according to the image coding apparatus of the present invention, it is possible to pipeline the motion vector search and encoding in the coding method using PMV (predicted motion vector), and it is possible to increase the processing speed.</p><p> Further, according to the image coding apparatus of the present invention, in the coding method using PMV, motion vector search for a plurality of macroblocks can be performed in parallel, and the processing speed can be increased.</p>

Hereinafter, embodiments of the present invention will be described with reference to the drawings.

(Embodiment 1) FIG. 1 is a basic configuration of an image coding apparatus according to the present invention. The difference from the conventional device configuration is that the macroblock order selection unit 13 has been added. An object of the present embodiment is to facilitate the pipeline processing of the macroblock in the case of the coding method using the intra 16 × 16 prediction of H.264. As mentioned above, in the intra 16 × 16 prediction, the three macro blocks on the left, top, and upper left of the macro block are currently used for prediction. For simplicity, let's assume that the entire picture is a single slice (possible with the H.264 standard). In H.264, instead of DCT, an integer conversion that approximates DCT by integer arithmetic is used, but since it has nothing to do with the essence of the present invention, it will be referred to as DCT in the following description.

The operation will be described with reference to FIG. The macroblock order selection unit 13 selects the macroblock to be encoded next. The motion vector detection and intra-prediction unit 17 detects the motion vector in the inter-prediction mode and selects the intra-prediction mode for the selected macroblock. The motion compensation mode selection unit 18 selects a coding mode such as intra-prediction, inter-prediction, and skip for the selected macroblock. The DCT unit 14 performs DCT on the residual of the intra-prediction or the residual of the inter-prediction of the selected macroblock. The quantization unit 15 quantizes the DCT coefficient. The entropy encoding unit 21 entropy-encodes the DCT coefficient. Entropy coding includes variable length coding and arithmetic coding according to the H.264 standard. The dequantization unit 19 dequantizes the quantized DCT coefficient. The inverse DCT section 20 performs inverse DCT on the inverse quantized DCT coefficient.

FIG. 13 is a flowchart of a method in which the macroblock order selection unit 13 in the present embodiment selects the macroblock (MB) to be encoded next. The operation of the macroblock order selection unit will be described with reference to FIG. Let the coordinates of the current macroblock be (i, j), and find the coordinates (v, h) of the macroblock to be encoded next. The first coordinate indicates the vertical position and increases downward. The second coordinate indicates the horizontal position and increases to the right. MB (i, j) represents a macroblock of coordinates (i, j).

Check if a macroblock exists at the coordinates (i + 1, j-1) (step S10), and if so, make that macroblock the next macroblock (step S11). If the macroblock does not exist at the coordinates (i + 1, j-1), perform the following (1) to (3).

(1) Let v be the smallest first coordinate in which an unencoded macroblock exists (step S12).

(2) Let h be the second coordinate of the leftmost macroblock among the unencoded macroblocks whose first coordinate is v (step S13).

(3) Let the macroblock of coordinates (v, h) be the next macroblock (step S14).

If there is no unencoded macroblock in (1) above, it is terminated.

Fig. 6 (a) is an example of ordering macroblocks by the method of Fig. 13. The squares indicate the macroblocks, and the numbers inside the squares indicate the order of the macroblocks. The figure shows the case where the frame size is 8 horizontal macroblocks and 4 vertical macroblocks, but the same applies to other frame sizes.

FIG. 6B is a conceptual diagram of pipeline processing when macroblocks are encoded in the order of the present embodiment. For the sake of simplicity, a case where the macroblock processing is divided into stage 0 and stage 1 and two-stage pipeline processing is performed will be described. It is assumed that stage 0 performs processing including mode selection of intra 16 × 16 prediction, and stage 1 performs encoding and local decoding using the result of stage 0. As an example, the case of encoding MB4 will be described. Since MB4 intra 16x16 prediction refers to MB0, MB1 and MB2, it is necessary to complete the encoding and local decoding of these three macroblocks before encoding MB4. As shown in Fig. 6 (b), since MB3 is encoded before MB4, the processing of MB0, MB1 and MB2 is completed at the start of MB4 encoding. Therefore, the stage 0 of MB4 can be started immediately after the completion of stage 0 of MB3. In this way, pipeline processing becomes possible.

The macroblocks encoded by the apparatus of this embodiment may be output in the order of encoding, or may be rearranged and output in the normal raster order so as to meet the H.264 standard after the encoding of the entire frame is completed. good. It is also possible to have identification information in the encoding order or raster order in the output stream so that either one can be selected. When the macroblocks are output in the order of encoding, the stream output from the encoding device should include information indicating the position of the macroblocks in the frame. When outputting macroblocks in raster order, include information indicating the encoding order of macroblocks.

The position of the macroblock can be indicated by adding the information corresponding to the coordinates (i, j) in the frame to the macroblock, but other methods, for example, the position of the macroblock can be derived. It is also possible by adding information that can be done. Another method is to add an identifier in the picture header indicating how to order the macroblocks of the entire picture. Alternatively, it may be a method of adding an identifier of the method of ordering the macroblocks in the slice in the slice header. Alternatively, it may be a method of adding an identifier of the method of ordering the macroblocks of the pictures in the sequence to the sequence header.

In the present embodiment, the order of encoding the macroblocks is selected by the method shown in FIG. 13, but the difference between the order numbers of the macroblocks and the three macroblocks on the left, top, and upper left is 2 or more. As long as the ordering is as such, other selection methods can be similarly implemented.

Although the present embodiment has described the two-stage pipe run processing, it is also possible to perform the pipe run processing of three or more stages. For example, in Fig. 6 (a), since the difference in sequence number between the left, top, and upper left macroblocks is 3 or more after MB6, three-stage pipeline processing is possible. Similarly, after MB10, the difference in sequence number from the left, top, and top left macroblocks is 4 or more, so 4-stage pipeline processing is possible. However, the number of stages that can be pipe run processed is small at the upper left and lower right edges of the frame.

In the above description, the entire picture is regarded as one slice, but even if the entire picture is divided into a plurality of slices, the same can be done by encoding each slice by ordering the macroblocks according to the present embodiment. It is feasible.

Although the frame picture has been described in the above description, the field picture can be similarly implemented. In the case of a field picture, it is divided into fields and then divided into macro blocks, and the processing for the macro blocks (encoding in the case of an encoder and decoding in the case of a decoder) is performed in the order described above.

The present invention may be implemented by a computer and a program, and the program may be recorded on a recording medium. This also applies to other embodiments of the present invention.

(Embodiment 2) The basic configuration of the image coding apparatus in the present embodiment is the same as that in the first embodiment. The operation of the macroblock order selection unit 13 is different from that of the first embodiment. An object of the present embodiment is to enable macroblock pipeline processing even with a coding method including 4 × 4 intra-prediction of H.264. As mentioned above, in the intra 4x4 prediction, the four macro blocks on the left, top, upper left, and upper right of the macro block are currently used for prediction.

FIG. 14 is a flowchart of a method in which the macroblock order selection unit of the present embodiment selects the macroblock to be encoded next. The operation will be described with reference to FIG. The current position of the macroblock is the coordinates (i, j). The first coordinate indicates a vertical position and increases downward. The second coordinate indicates the horizontal position and increases to the right. Check if a macroblock with coordinates (i + 1, j-2) exists (step S20), and if so, use that MB (i + 1, j-2) as the next macroblock (step S21). .. If the macroblock of coordinates (i + 1, j-2) does not exist, execute the following (1) to (3).

(1) Let v be the smallest first coordinate in which there is an unencoded macroblock (step S22).

(2) Let h be the second coordinate of the leftmost macroblock among the uncoded macroblocks whose first coordinate is v (step S23).

(3) Let the macroblock of coordinates (v, h) be the macroblock to be encoded next (step S24).

If there is no unencoded macroblock in (1) above, it is terminated.

FIG. 7 (a) shows the coding order of the macroblocks selected by the method of FIG. Figure 7 (b) shows the macroblock pipeline processing. For the sake of simplicity, the figure shows the case of processing with a two-stage pipe run. It is assumed that stage 0 performs processing including mode selection of intra 4 × 4 prediction, and stage 1 performs encoding and local decoding using the result of stage 0.

As an example, the case of encoding MB5 will be described. In the MB5 intra 4x4 prediction, 4 macroblocks of MB0, MB1, MB2, and MB3 are used for the prediction. By the start of MB5 encoding, the encoding and local decoding of these four macroblocks used for prediction must be completed. According to the macroblock order selection of the present embodiment, the difference between the order of MB5 and these four macroblocks is 2 or more, so that the processing of these four macroblocks is performed at the time of starting the encoding of MB5. Completed. Therefore, stage 0 of MB5 can be started immediately after the completion of stage 0 of MB4. As a result, as shown in Fig. 7 (b), two-stage pipeline processing becomes possible.

Although the present embodiment has described the two-stage pipe run processing, it is also possible to perform the pipe run processing of three or more stages. For example, in Fig. 7 (a), after MB9, the difference in sequence number between the current macroblock and the four macroblocks on the left, top, upper left, and upper right referenced by the current macroblock is 3 or more, so a three-stage pipeline run. Processing is possible. Similarly, since MB16 and later, the difference in sequence number between the macroblock and the macroblocks on the left, top, upper left, and upper right is 4 or more, so 4-stage pipeline processing is possible. However, the number of stages that can be pipe run processed is small at the upper left and lower right edges of the frame.

In this embodiment, the order in which the macroblocks are encoded is selected by the method shown in FIG. 14, but the difference between the order numbers of the current macroblock and the four macroblocks on the left, top, upper left, and upper right is 2 or more. As long as the ordering is such that, other selection methods can be implemented in the same manner.

In the first embodiment, the condition for the two-stage pipeline processing of the coding including the intra 16 × 16 prediction is that the difference between the sequence numbers of the current macroblock and the three macroblocks on the left, top, and upper left is 2 or more. Is to be. In the second embodiment, the condition for the two-stage pipeline processing of the coding including the intra 4 × 4 prediction is that the difference between the sequence numbers of the current macroblock and the four macroblocks on the left, top, upper left, and upper right is 2 That is all. Since the condition of the first embodiment is satisfied if the condition of the second embodiment is satisfied, the coding device of the second embodiment can perform macroblock pipeline processing even for the intra 16 × 16 prediction. As for the pipeline processing of three or more stages, if the condition of the second embodiment is satisfied, the condition of the first embodiment is satisfied, so that the same can be performed.

The macroblocks encoded by the apparatus of this embodiment may be output in the order of encoding, or may be rearranged and output in the normal raster order after the encoding of the entire frame is completed. It is also possible to have identification information in the encoding order or raster order in the output stream so that either one can be selected.

It is also possible to divide the macroblock into two horizontal columns and set the encoding order as shown in FIG. 18A. By adopting such an order, when the macroblocks are sorted and output in raster order after the encoding is completed, the amount of intermediate data from the completion of the macroblock encoding to the output can be reduced. Further, the same can be performed by setting the encoding order of the macroblocks as shown in FIG. 18 (b). In the order shown in Fig. 18 (a), MB14, MB15, and MB17 cannot be pipelined because the difference in order number from the left macroblock is 1. By using the order shown in Fig. 18 (b), it is possible to perform pipeline processing for these macroblocks as well.

The same can be achieved by dividing the macroblock into three horizontal columns and encoding in the order shown in FIG. By adopting such an order, it is possible to perform three-stage pipeline processing of macroblocks, and when the macroblocks are sorted and output in raster order after encoding, after the macroblocks have been encoded. The amount of intermediate data until output can be reduced.

It should be noted that the same can be performed regardless of whether the picture structure is a frame or a field. In the case of a field picture, the macroblock is encoded for each field in the above order.

(Embodiment 3) FIG. 2 is a basic configuration diagram of a decoding device according to the third embodiment of the present invention. The difference from the conventional device configuration is that the macroblock order selection unit 39 exists. An object of the present embodiment is to facilitate decoding of a stream encoded by a coding method including an intra 16 × 16 prediction by a macroblock pipeline process.

The operation will be described with reference to FIG. The macroblock order selection unit 39 receives the position information of the macroblock from the variable length decoding unit 31. The macroblock order selection unit 39 selects the macroblock to be decoded next based on the macroblock order selection method described later. The motion compensation unit 37 performs motion compensation for the selected macroblock, and the video memory unit 38 stores the selected macroblock at a corresponding position in the frame.

The macroblock position information is information indicating the position of the macroblock to be decoded within the frame. Specifically, the coordinates in the picture for each macroblock, the information indicating the order of the macroblocks in the picture included in the picture header, or the information indicating the order of the macroblocks in the slice included in the slice header, or Information indicating the order of macroblocks of pictures in the sequence included in the sequence header. The information indicating the order of macroblocks included in the picture header, slice header, and sequence header is an identifier that defines the order of macroblocks, or a correspondence table of coordinates and coding order for macroblocks in a picture. Even if the storage order of the macroblocks in the stream is not the raster order as shown in FIG. 9A, the position of the macroblocks in the frame can be known from the identifier or the correspondence table.

Hereinafter, a case of decoding a stream encoded by an encoding method including intra-prediction will be described.

The storage order in the macroblock stream and the macroblock decoding order may or may not match. As an example of matching cases, the order in the stream and the decoding order may both be the order shown in FIG. 6 (a), or the order in the stream and the decoding order may both be the order shown in FIG. 7 (a). As an example of different cases, when the order in the stream is Fig. 9 (a) and the decoding order is Fig. 6 (a), or when the order in the stream is Fig. 9 (a) and the decoding order is Fig. 7 (a). There is. If the appearance order and the decoding order of the macroblock in the stream are different, the decoding order of the macroblock is selected by the method described later.

If the coded stream contains coordinates for each macroblock, the macroblock order selection unit determines the position in the frame from the coordinates. If the picture header, slice header, or sequence header of the coded stream contains an identifier indicating the order of the macroblock, the position of the macroblock within the frame is determined according to the procedure indicated by the identifier.

For example, when the storage order of the macroblock indicated by the identifier is the procedure of the flowchart of FIG. 13, the position of the macroblock in the frame is determined based on the procedure of FIG. In this case, the storage order of the macroblocks in the stream is as shown in Fig. 6 (a). In this way, the decoded macroblock can be placed at the correct position in the frame.

The macroblock order selection unit 39 in the present embodiment selects the decoding order of the macroblocks according to the flowchart of FIG. The storage order of macroblocks in the stream may be the order shown in FIG. 6 (a), or may be another order, for example, the order shown in FIG. 9 (a). If the storage order and decoding order of the macroblock in the stream are the same, the macroblocks are decoded in the order of variable length decoding. If the storage order and decoding order in the macroblock stream are different, the macroblock data is temporarily saved after variable-length decoding, and the order selection unit selects the order of the macroblocks to be decoded.

Since the decoding of the intra 16x16 prediction currently refers to the three macroblocks on the left, top, and upper left of the macroblock, the decoding of these three macroblocks is currently completed before decoding the macroblock. There is a need. The decoding order of the macroblocks selected by the procedure of FIG. 13 is the order shown in FIG. 6 (a). In the decoding device of the present embodiment, the difference between the decoding order of the current macroblock and the three macroblocks on the left, top, and upper left of the current macroblock is 2 or more (excluding the upper left end and the lower right end).

A pipeline process for decoding a macroblock by the decoding device of the present embodiment will be described. For the sake of simplicity, it is assumed that the pipeline has two stages, stage 0 and stage 1, and the processing time of each stage is the same. It is assumed that stage 0 performs processing including decoding of the intra 16 × 16 prediction, and stage 1 performs the remaining processing. As an example, MB4 decoding will be described. Suppose MB4 was encoded using the intra 16x16 prediction. Since MB4 decoding refers to MB0, MB1 and MB2, it is necessary to complete the decoding of these three macroblocks before decoding MB4. Since the processing of stage 1 of MB2 is completed before MB4 enters stage 0 of the pipeline, stage 0 of MB4 can be started immediately after the completion of stage 0 of MB3.

Although the present embodiment has described the decoding of the stream encoded by the encoding device of the first embodiment, the case of decoding the stream encoded by the encoding device of the second embodiment also describes the macroblock. By setting the decoding order to Fig. 7 (a), it is possible to perform pipeline processing in the same manner.

In this embodiment, the case where the macroblock processing pipeline has two stages has been described, but the same can be applied to the case where the pipeline has three or more stages. Since MB6 or later, the difference between the sequence number of the current macroblock and the sequence number of the three macroblocks (currently the left, top, and upper left macroblocks of the macroblock) referenced by the intra 16x16 is 3 or more, so 3 Stage pipe run processing is possible. Since MB10 or later, the difference in sequence number between the macroblock and the three macroblocks to be referenced is 4 or more, so 4-stage pipeline processing is possible.

Although the present embodiment has described the case where the coding order of the macroblocks is shown in FIG. 6 (a), it can also be carried out in the order shown in FIG. 7 (a). The order of FIG. 7 (a) can be obtained by the procedure shown in the flowchart of FIG. In the case of the order shown in Fig. 7 (a), the difference between the order numbers of the current macroblock and the four macroblocks on the left, top, upper left, and upper right of the current macroblock is 2 or more. It is possible to decode macroblocks by two-stage pipeline processing for both intra 4x4 predictions. In this case as well, pipe run processing of three or more stages is possible as described above.

The macroblocks encoded by the apparatus of this embodiment may be output in the order of encoding, or may be rearranged and output in the normal raster order after the encoding of the entire frame is completed. It is also possible to have identification information in the encoding order or raster order in the output stream so that either one can be selected.

(Embodiment 4) An object of the present embodiment is to enable macroblock pipeline processing even in a coding method including prediction of H.264 spatial direct mode in an encoder. The spatial direct mode is described in Non-Patent Document 4. The basic configuration of the image coding apparatus in the present embodiment is the same as that in the first embodiment. The operation of the macroblock order selection unit 13 is different from that of the first embodiment. The encoding order of the macroblocks in the present embodiment is the same as that in the second embodiment.

The encoding order of macroblocks in this embodiment is shown in FIG. 7 (a). The macroblock ordering shown in FIG. 7A can be obtained by the method shown in the flowchart of FIG.

As shown in FIG. 8, when macroblock A is currently encoded in the spatial direct mode, the motion vectors of macroblocks B, C, and D or the motion vectors of the small blocks contained in those macroblocks are used. Therefore, it is necessary to complete the encoding of the three macroblocks on the left, top, and upper right before currently encoding the macroblock.

For the sake of simplicity, the case of encoding with a two-stage pipeline will be described. According to the macroblock order of Fig. 7 (a), the difference in encoding order number between the current macroblock and the three macroblocks on the left, top, and upper right of the current macroblock is 2 or more, so Fig. 7 (b) ), Two-stage pipe run processing is possible.

(Embodiment 5) FIG. 15 is a basic configuration diagram of a still image coding device according to the fifth embodiment of the present invention. The still image coding method used in this embodiment is a modification of the JPEG baseline profile of Non-Patent Document 5. Specifically, it is encoded in macroblock units and encoded by 8 × 8 size DCT, quantization, zigzag scan of conversion coefficient, and variable length coding, but the following two points are different from JPEG.

(1) In macroblock coding, the current macroblock is predicted from the surrounding macroblocks using the same prediction as the H.264 intra-prediction, and the prediction residual is encoded.

(2) The coding order of macroblocks shall be the order shown in Fig. 6 (a) or Fig. 7 (a).

The operation of the still image coding device according to the present embodiment will be described with reference to FIG. Selects the macroblock to be encoded by the macroblock order selection unit 86. The order of macroblocks can be selected by the method shown in FIG. 13 or FIG. The prediction unit 80 creates a prediction image for the selected macroblock using the locally decoded image of the macroblock around the current macroblock stored in the frame memory 87. The residual calculation unit 81 calculates the residual of the prediction. The DCT section 82 performs DCT on the residual. The quantization unit 83 quantizes the DCT coefficient. The zigzag scan unit 84 performs a zigzag scan of the DCT coefficient. The variable-length coding unit 85 encodes the DCT coefficient in a variable-length code and adds information on how the current macroblock is predicted from the surrounding macroblocks. The dequantization unit 89 dequantizes the quantized DCT coefficient. The inverse DCT section 88 inversely DCTs the inverse quantized DCT coefficient. The macroblock is reconstructed from the information used for prediction and the result of the inverse DCT, and saved in the frame memory 87. The macroblock saved in the frame memory is used for the prediction of the subsequent macroblock.

There are two ways to predict the current macroblock from the locally decoded image of the surrounding macroblock.

(1) Currently, three macroblocks on the left, top, and upper left of the macroblock are used.

(2) Currently, four macroblocks are used: left, top, top left, and top right of the macroblock.

Here, in the case of (1), it is assumed that the coding order of the macroblock is shown in FIG. 6 (a). In the case of (2), the coding order of macroblocks shall be shown in Fig. 7 (a).

By coding by the above method, since intra-prediction can be used for macroblock coding, there is an advantage that the amount of code can be made smaller than that of JPEG. Moreover, since the macroblocks are encoded in the order of FIG. 6 (a) or FIG. 7 (a), it is possible to pipeline the macroblocks as shown in FIG. 6 (b) or FIG. 7 (b). ..

Although the still image coding device has been described in the above description, the still image decoding device that decodes the data encoded by the still image coding device of the present embodiment also has macros in the same order as the coding device. By decoding the block, pipeline processing in macroblock units becomes possible.

Note that Fig. 6 (b) and Fig. 7 (b) show the case of two-stage pipeline processing, but when the difference between the sequence numbers of the macroblocks referenced in encoding and decoding and the current macroblocks is 3 or more. Can perform pipeline processing of 3 or more stages in encoding and decoding.

(Embodiment 6) FIG. 16 is a basic configuration diagram of a macroblock order rearranging device for a coding device according to the sixth embodiment of the present invention. The purpose of this device is to rearrange the macroblocks when the coding order of the macroblocks and the output order of the macroblocks to the stream are different. The encoded macroblock is output after the order is rearranged by this device.

The operation of the macroblock sorting device will be described with reference to FIG. As an example, the case where the coding order of the macroblock is FIG. 7 (a) and the storage order of the macroblock is FIG. 9 (a) will be described.

The coded macroblock area stores the coded macroblock (MB). The code amount of a macroblock is not always constant and may differ depending on the macroblock. The pointer table has the addresses of macroblocks stored in the encoding order. The order conversion table has two entries, the first entry is the macroblock transmission order and the second entry is the macroblock coding order. The coded macroblock is not transmitted until the coding of the macroblock of one picture is completed, but is stored in the coded macroblock area, and its address is stored in the entry of the pointer table.

After the coding of the macroblock of one picture is completed, the macroblocks are sorted in the transmission order and output. First, it outputs the macroblock pointed to by the pointer corresponding to the value of the second entry where the value of the first entry in the order conversion table is 0. Next, the macro block pointed to by the pointer corresponding to the value of the second entry whose value of the first entry is 1 is output. The same applies after that. By such a procedure, in the example of the figure, the macroblocks pointed to by 0, 1, 2, 4, 6, 9, 12, 16, 3, 5, 7, 10, and 13 of the pointer table are output in this order.

The macroblock order rearranging device of the present embodiment can be used in combination with the image coding device of the first embodiment or the second embodiment. The macroblocks encoded by the coding device of the first embodiment or the second embodiment are rearranged by the device of the present embodiment. Since the coding order of macroblocks is as shown in Fig. 7 (a), pipeline processing in macroblock units is possible. Moreover, since the transmission order of the macroblock is as shown in FIG. 9A, it is possible to generate a stream conforming to the H.264 standard. That is, it enables an image coding device that generates a stream conforming to the H.264 standard by pipeline processing of macroblocks.

In the present embodiment, the case where the coding order of the macroblock is FIG. 7 (a) and the output order is FIG. 9 (a) has been described, but the encoding order or the output order of the macroblock is the present embodiment. Even if it is different from the form, it can be implemented in the same manner by changing the order conversion table.

The macroblock stored in the coded macroblock area may be a macroblock after entropy coding or a macroblock before entropy coding. When the macroblock before being entropy-encoded is stored, the macroblock is reordered and then entropy-encoded and output.

(Embodiment 7) FIG. 17 is a basic configuration diagram of a macroblock order rearranging apparatus for a decoding apparatus according to the seventh embodiment of the present invention. The purpose of this device is to rearrange the macroblocks when the storage order of the macroblocks in the coded stream and the decoding order of the macroblocks are different. After the input macroblock is entropy-decoded, the decoding order is selected by the present device and the macroblock is decoded.

The operation of the macroblock order rearranging apparatus according to the present embodiment will be described with reference to FIG. As an example, a case where the input order of the macroblock is as shown in FIG. 9 (a) and the decoding order of the macroblock is as shown in FIG. 7 (a) will be described.

A macroblock (MB) waiting to be decrypted is stored in the macroblock area waiting to be decrypted. The code amount of a macroblock is not always constant and may differ depending on the macroblock. The pointer table has the address where the entropy-decoded macroblocks are stored in the input order of the macroblocks. The order conversion table has two entries, the first entry is the macroblock decryption order and the second entry is the macroblock input order.

The input and entropy-decoded macroblock is stored in the macroblock area waiting for decoding. The address of the macroblock waiting to be decrypted in the input order is stored in the pointer table. After inputting all the macroblocks in one picture is completed, the macroblocks are selected and decoded according to the decoding order.

First, decrypt the macroblock pointed to by the pointer corresponding to the value of the second entry where the value of the first entry in the order conversion table is 0. Next, the macroblock pointed to by the pointer corresponding to the value of the second entry whose value of the first entry is 1 is decoded. The same applies after that. In the case of the figure, the macroblocks pointed to by 0, 1, 2, 8, 3, 9, 4, 10, 16, 5, 11, 17, and 6 of the pointer table are decoded in this order by such a procedure.

The macroblock order rearranging device of the present embodiment can be used in combination with the image decoding device of the third embodiment. After rearranging the order by the apparatus of the present embodiment, decoding is performed by the decoding apparatus of the third embodiment. By doing so, the input order of the macroblock becomes as shown in FIG. 9 (a), and it is possible to conform to the H.264 standard. Further, the decoding order of the macroblock is as shown in FIG. 7A, and it is possible to enable the pipeline processing for decoding the macroblock. That is, it enables an image decoding device that decodes a stream conforming to the H.264 standard by pipeline processing.

In the present embodiment, the case where the input order of the macroblock is FIG. 9 (a) and the decoding order is FIG. 7 (a) has been described, but the order conversion table is changed even in the case of other orders. By doing so, it can be carried out in the same manner.

(Embodiment 8) The H.264 standard includes a macroblock coding method called MBAFF (macroblock adaptive frame field). In this embodiment, a coding device that processes a coding method using MBAFF by a pipeline method will be described. MBAFF is described in Non-Patent Document 4. When encoding with MBAFF, you can pair the upper and lower two macroblocks and select frame or field for each macroblock pair. If the macrobook pair is a frame, encode the two macroblocks together as a frame. If the macroblock pair is a field, encode the two macroblocks together as a field. The macroblock pair encodes the upper macroblock and then the lower macroblock in that order.

FIG. 21 (a) shows the coding order of macroblocks in the case of MBAFF in the conventional method. Intra 16x16 prediction, intra 4x4 prediction, and spatial direct mode can also be used in MBAFF. In these modes, the left, top, top left, and top right macroblock pairs of the macroblock pair that currently contains the macroblock (currently called the macroblock pair) are encoded, and the result of local decoding is used to currently encode the macroblock. Encode the pair. Therefore, it is necessary to complete the encoding and local decoding of the left, top, top left, and top right macroblock pairs before starting the encoding of the macroblock pair. Taking the case where one macroblock is encoded in two stages as an example, the processing timing of each stage of the macroblock is as shown in Fig. 21 (b), and it is difficult to perform pipeline processing. ..

FIG. 20A shows the processing order of macroblocks in this embodiment. Since the macroblock pair of MB6 and MB7 does not refer to the macroblock pair of MB4 and MB5, the macroblock pair of MB6 and MB7 encodes the macroblock pair of MB4 and MB5 without waiting for the completion of local decoding. You can start. Therefore, MB6 and MB7 macroblock pairs can be encoded by pipeline processing with MB4 and MB5 macroblock pairs. Similarly, MB8 and MB9 macroblock pairs can be encoded by pipeline processing with MB6 and MB7 macroblock pairs. The same applies to subsequent macroblock pairs.

As an example of pipeline processing, a case where processing of one macroblock is performed in two stages will be described. Assume that the processing times of the two stages are equal. FIG. 20B is a diagram illustrating the timing of pipeline processing in the present embodiment. When the stage 0 of MB4 is finished, the stage 1 of MB4 is started, and the stage 0 of MB6 is started at the same time. When the stage 0 of MB6 is finished, the stage 1 of MB6 is started, and the stage 0 of MB5 is started at the same time. When the stage 0 of MB5 is finished, the stage 1 of MB5 is started, and the stage 0 of MB7 is started at the same time. When the stage 0 of MB7 is finished, the stage 1 of MB7 is started, and the stage 0 of MB8 is started at the same time. After that, pipeline processing can be performed in the same manner.

The same can be applied to pipeline processing of three or more stages. The MB14 and MB15 macroblock pairs do not use the local decoding results of the MB12 and MB13 macroblock pairs. Also, the MB16 and MB17 macroblock pairs do not use the local decoding results of the MB12 and MB13 macroblock pairs and the MB14 and MB15 macroblock pairs. Therefore, three macroblock pairs, MB12, MB13 macroblock pair, MB14, MB15 macroblock pair, and MB16, MB17 macroblock pair, can be encoded in parallel. Therefore, the macroblock pairs of MB12 and MB13 and thereafter can be encoded by a three-stage pipeline process. Similarly, it is possible to perform pipeline processing of four or more stages for an image having a frame size larger than that shown in FIG. 20 (a).

(Embodiment 9) In the present embodiment, a coding device that processes motion vector search and encoding by a pipeline method will be described. The overall configuration is the same as in Figure 1.

The H.264 standard allows macroblocks to be encoded using motion compensation. Motion compensation can be performed in macroblock units, or motion compensation can be performed in blocks obtained by dividing macroblocks. Figure 22 shows the motion compensation block. The block size for motion compensation can be selected from 16x16, 16x8, 8x16, and 8x8. In the case of 8x8, it can be further divided into 8x8, 8x4, 4x8, and 4x4. You can have a motion vector for each divided block.

In the H.264 standard, when encoding a motion vector, the difference between the motion vector and the predicted value of the motion vector (called PMV) is encoded instead of encoding the motion vector value itself. The difference between the motion vector and PMV is encoded for each horizontal and vertical component. According to the standard, the predicted value (PMV) of the motion vector is currently obtained from the motion vector of the macroblock on the left, top, and upper right of the macroblock. Assuming that MB9 is currently a macroblock in Fig. 23 (a), the predicted value (PMV) of the motion vector of MB9 is used using the motion vectors of three macroblocks, MB8 (left), MB1 (top), and MB2 (upper right). Ask for. The procedure for obtaining PMV from the motion vector of the surrounding macroblock is complicated, but since it has nothing to do with the essence of the present invention, the explanation of the procedure is omitted.

In the process of standardizing H.264, encoders and decoders called Joint Model (hereinafter referred to as JM) described in Non-Patent Document 6 were created. JM uses a method called rate / distortion optimization in order to reduce the distortion due to coding and reduce the amount of coding (the method of rate / distortion optimization is also described in Non-Patent Document 8). A method of motion estimation (ME) in JM encoding will be described based on Non-Patent Document 6. After finding the motion vector by the motion vector search, the motion vector is used for encoding. In the motion vector search, the motion vector is selected so that the prediction error between the original image and the predicted image is reduced and at the same time the sign amount of the motion vector is reduced.

In JM, the motion vector that minimizes J calculated by the following formula is selected.

J = SAD + λR where SAD (sum of absolute difference) is the sum of the absolute values of the predicted residuals, λ is a constant called the Lagrange parameter, and R is the sign amount of the motion vector. Instead of SAD, SATD, which is the sum of the absolute values after the Hadamard transform on the residuals, may be used. In the JM encoder, in order to reduce the code amount of the motion vector, PMV is calculated based on the standard procedure, and a motion vector is selected so that the difference between the motion vector and PMV becomes small at the same time as the prediction error of the image becomes small (motion). The vector search method is not specified in the H.264 standard, but is left to the encoder. The procedure for obtaining PMV is specified in the H.264 standard.)

The JM encoder is implemented by software, but when it is implemented by hardware, pipeline processing becomes an issue. This will be described below. If JM motion vector search is to be implemented in hardware as it is, PMV must be obtained according to the standard procedure. Since the motion vectors of the macroblocks on the left, top, and top right of the macroblock are currently used when calculating the PMV, the encoding of these three macroblocks is currently completed before starting the motion vector search for the macroblock. There is a need. The macroblock on the left has a particularly large effect. Since the motion vector search for the macroblock on the left can only be started after the motion vector search and encoding are completed, it is difficult to pipeline the motion vector search and the subsequent encoding process. is there.

Non-Patent Document 7 addresses this issue as follows. As shown in Fig. 23 (b), in the calculation of PMV of the current macroblock, the motion vector of the upper left macroblock is used instead of the motion vector of the left macroblock. Assuming that the vector obtained in this way is PMV', the method of Non-Patent Document 7 currently selects a motion vector so as to reduce the difference between the motion vector of the macroblock and PMV'. In this way, it is possible to pipeline the motion vector search and encoding, but another problem arises. In the motion vector search, the motion vector is selected so as to reduce the difference between the motion vector and PMV', but in the encoding, the difference between the motion vector and PMV is encoded. Since PMV and PMV'are different, even if the difference between the motion vector and PMV'is small, the difference between the motion vector and PMV may be large. Therefore, there arises a problem that the code amount of the motion vector becomes large after encoding.

In the method of this embodiment, macroblocks are processed in the order shown in FIG. 24 (a). By processing in such an order, it becomes possible to perform pipeline processing for motion vector search and subsequent encoding processing as shown in FIG. 24 (b). In the example shown in the figure, the macroblock processing is processed by a two-stage pipeline of motion vector search and subsequent encoding processing. As an example, the case where the macroblock is currently MB5 will be described with reference to FIG. 24 (b). Since the motion vectors of MB1, MB2, and MB3 are used to obtain the PMV used for the motion vector search of MB5, it is necessary that the processing of these three macroblocks is completed. Since the MB3 encoding stage ends when the MB4 motion vector search stage ends, the MB5 motion vector search stage can be started immediately after the MB4 motion vector search stage ends.

Note that Fig. 24 shows the case where macroblock processing is performed by two-stage pipeline processing of motion vector search and subsequent encoding, but macroblock processing should be subdivided and processed by a pipeline with three or more stages. Is also possible. By processing the macroblocks in the order shown in Fig. 24 (a), it is possible to perform three-stage pipeline processing after MB6. After MB12, 4-stage pipeline processing is possible. For images with a large frame size, pipeline processing with 5 or more stages can be performed in the same way.

The processing order of the macroblocks shown in FIG. 24A can be selected by the procedure shown in the flowchart of FIG. Alternatively, it can be selected by using the correspondence table between the macroblock address and the processing order.

The feature of this embodiment is that one or more macroblocks are inserted in the processing order between the macroblocks and the macroblocks on the left, top, and upper right. (In other words, the difference between the sequence numbers of the current macroblock and the macroblocks on the left, top, and top right is 2 or more.) If this condition is satisfied, the processing is different from that in Fig. 24 (a). Even in order, it is similarly possible to pipeline the motion vector search and subsequent encoding. The same applies to pipeline processing with three or more stages.

(Embodiment 10) In the present embodiment, a coding device that performs motion vector search for a plurality of macroblocks in parallel and further processes motion vector search and encoding by a pipeline method will be described. The overall configuration is the same as in Figure 1.

The H.264 standard does not encode the motion vector itself, but encodes the difference between the motion vector and the predicted value of the motion vector. As described in the ninth embodiment, in the motion vector search, it is necessary to obtain the PMV which is the predicted value of the motion vector from the motion vector of the macroblocks on the left, upper, and upper right of the macroblock at present. Therefore, if there are currently macroblocks to the left, top, and top right of the macroblock, the encoding of those macroblocks must be completed before the motion vector search of the macroblock can be started (currently the macroblock). If there are no macroblocks on the left, top, or top right, their encoding does not need to be complete.)

FIG. 25 (a) shows the processing order of macroblocks according to the present embodiment. FIG. 25 (b) is a diagram illustrating the operation of an encoding device provided with two ME units 0 and 1 for performing motion vector search and two encoding units 0 and 1 for encoding. The operation will be described with the passage of time based on the figure.

Time 0: Starts motion vector search for MB0.

Time 1: MB0 motion vector search is completed and MB0 encoding is started.

Time 2: Since the encoding of MB0 is completed, it is possible to start the motion vector search of MB1 (because the encoding result of MB0 is used to obtain the PMV for MB1). Start MB1 motion vector search.

Time 3: MB1 motion vector search is completed and MB1 encoding is started.

Time 4: Now that the MB1 encoding is complete, it is possible to start the MB2 motion vector search. Start MB2 motion vector search. Since the encoding of MB0 and MB1 is completed, it is possible to start the motion vector search of MB3. Start MB3 motion vector search.

Time 5: MB2 motion vector search is completed and MB2 encoding is started. MB3 motion vector search is completed and MB3 encoding is started.

Time 6: Start MB4 motion vector search. Start MB5 motion vector search.

Time 7: Start encoding MB4. Start encoding MB5.

Time 8: Start MB6 motion vector search. Start MB7 motion vector search.

Time 9: Since the encoding of MB3 and MB5 is completed, it is possible to start the motion vector search of MB8 (because the encoding result of MB3 and MB5 is used to obtain the PMV for MB8). Start MB8 motion vector search. Start encoding MB6. Start encoding MB7.

Time 10: Since the encoding of MB4, MB6, MB7 is completed, it is possible to start the motion vector search of MB10 (because the encoding result of MB4, MB6, MB7 is used to obtain the PMV for MB10. ). Start MB10 motion vector search. Since the encoding of MB6 is completed, it is possible to start the motion vector search of MB9. Start MB9 motion vector search. Start encoding MB8.

Time 11: Since the encoding of MB5, MB7 and MB8 is completed, it is possible to start the motion vector search of MB11. Start motion vector search for MB11. Start encoding MB10. Start encoding MB9.

Time 12: Now that the MB9 encoding is complete, it is possible to start the MB12 motion vector search. Start MB12 motion vector search. Since the encoding of MB6, MB9, and MB10 has been completed, it is possible to start the motion vector search of MB13. Start the motion vector search of MB13. Start encoding MB11.

Time 13: Since the encoding of MB7, MB10 and MB11 is completed, it is possible to start the motion vector search of MB14. Start the motion vector search of MB14. Since the encoding of MB8 and MB11 is completed, it is possible to start the motion vector search of MB15. Start MB15 motion vector search. Start encoding MB12. Start encoding MB13.

Time 14: Since the MB12 encoding is complete, it is possible to start the MB16 motion vector search. Start MB16 motion vector search. Since the encoding of MB9, MB12, and MB13 has been completed, it is possible to start the motion vector search of MB17. Start motion vector search for MB17. Start encoding MB14. Start encoding MB15.

As can be seen from the above explanation, after time 4, motion vector search for two macroblocks or encoding for two macroblocks can be executed in parallel. In addition, after time 13, both the motion vector search for two macroblocks and the encoding for two macroblocks can be executed in parallel. After time 13, two ME units and two encoding units can be operated continuously without creating free time.

The parallel processing for a device having two ME units and two encoding units has been described above, but parallel processing for three or more macroblocks can also be performed in the same manner. As an example, parallel processing for three macroblocks will be described. It is assumed that the coding device has three ME units and three encoding units. In Fig. 25, MB4 is referred to when calculating PMV for MB6. MB2, MB4, and MB5 are referenced when calculating the PMV for MB7. MB3 and MB5 are referenced when calculating the PMV for MB8. When the encoding of MB4 and MB5 is completed, the encoding of the macro block to be referred to when calculating the PMV for MB6, MB7, and MB8 is completed. Therefore, when the encoding of MB4 and MB5 is completed, the motion vector search for MB6, MB7, and MB8 can be started at the same time. In this way, after MB6, motion vector search for 3 macroblocks or encoding for 3 macroblocks can be performed in parallel. If the frame size is large, both motion vector search for 3 macroblocks and encoding for 3 macroblocks can be performed in parallel as the process progresses. It should be noted that parallel processing for four or more macroblocks can be performed in the same manner.

(Embodiment 11) The image coding apparatus according to the present embodiment includes two ME units that perform a motion vector search and one encoding unit that performs encoding processing after the motion vector search. FIG. 26 is an explanatory diagram of the present embodiment. Since the motion vector search requires a large amount of calculation as compared with encoding, the present embodiment includes more ME units than the number of encoding units.

The image coding apparatus according to this embodiment processes macroblocks in the order shown in FIG. 26 (a). Based on FIG. 26 (b), the operation of this embodiment will be described over time. It is assumed that the motion vector search takes twice as long as the encoding.

Time 0: Starts motion vector search for MB0.

Time 2: MB0 motion vector search is completed and MB0 encoding is started.

Time 3: Now that the MB0 encoding is complete, it is possible to start the MB1 motion vector search. Start MB1 motion vector search.

Time 5: MB1 motion vector search is completed and MB1 encoding is started.

Time 6: Now that the MB1 encoding is complete, it is possible to start the MB2 motion vector search. Start MB2 motion vector search. Since the encoding of MB0 and MB1 is completed, it is possible to start the motion vector search of MB3. Start MB3 motion vector search.

Time 8: MB2 motion vector search completes and MB2 encoding begins.

Time 9: Now that the MB2 encoding is complete, it is possible to start the MB4 motion vector search. Start MB4 motion vector search. Since the motion vector search of MB3 is completed, start encoding MB3.

Time 10: Now that the MB1, MB2, and MB3 encodings are complete, it is possible to start the MB5 motion vector search. Start MB5 motion vector search.

Time 11: MB4 motion vector search completes and MB4 encoding begins.

Time 12: Now that the MB4 encoding is complete, it is possible to start the MB6 motion vector search. Start MB6 motion vector search. Now that the MB5 motion vector search is complete, start encoding the MB5.

Time 13: Now that the MB2, MB4, and MB5 encodings are complete, it is possible to start the MB7 motion vector search. Start MB7 motion vector search.

Time 14: Since the encoding of MB3 and MB5 is completed, it is possible to start the motion vector search of MB8. Start MB8 motion vector search. Now that the motion vector search for MB6 is complete, start encoding MB6.

Time 15: Now that the MB6 encoding is complete, it is possible to start the MB9 motion vector search. Start MB9 motion vector search. MB7 motion vector search is completed and MB7 encoding is started.

Time 16: Now that the encoding of MB4, MB6 and MB7 is completed, it is possible to start the motion vector search of MB10. Start MB10 motion vector search. MB8 motion vector search is completed and MB8 encoding is started.

As can be seen from the above explanation, after time 14, it is possible to operate two ME units and one encoding unit continuously without creating free time. It is possible to perform motion vector search for two macroblocks in parallel, and further perform motion vector search and encoding processing in parallel.

It is also possible to implement the encoding process other than the motion vector search by the personal computer so that the expansion board of the personal computer performs the motion vector search with a large amount of calculation. When implemented in this way, ME units 0 and 1 correspond to the expansion board of the personal computer, the encoding unit corresponds to the personal computer, and the personal computer executes overall control. One expansion board may be used as one ME unit, or one expansion board may have the functions of a plurality of ME units. The operation of the ME unit and the encoding unit is the same as that of the present embodiment.

(Embodiment 12) The image coding apparatus according to the present embodiment includes three ME units that perform a motion vector search and one encoding unit that performs encoding processing after the motion vector search. FIG. 27 is an explanatory diagram of the present embodiment.

If there are macroblocks on the left, top, and upper right of the current macroblock, the motion vectors of these macroblocks are used to find the PMV for the current macroblock, so before starting the motion vector search for the current macroblock. These macroblocks need to be encoded. The image coding apparatus according to this embodiment processes macroblocks in the order shown in FIG. 27 (a). Based on FIG. 27 (b), the operation of this embodiment will be described over time. It is assumed that the motion vector search takes three times as long as the encoding.

Time 0: Starts motion vector search for MB0.

Time 3: MB0 motion vector search is completed and MB0 encoding is started.

Time 4: MB0 encoding is complete and MB1 motion vector search can be started. Start MB1 motion vector search.

Time 7: MB1 motion vector search completes and MB1 encoding begins.

Time 8: Now that the MB1 encoding is complete, it is possible to start the MB2 motion vector search. Start MB2 motion vector search. Since the encoding of MB0 and MB1 is completed, it is possible to start the motion vector search of MB3. Start MB3 motion vector search.

Time 11: MB2 motion vector search completes and MB2 encoding begins.

Time 12: Now that the MB2 encoding is complete, it is possible to start the MB4 motion vector search. Start MB4 motion vector search. Since the motion vector search of MB3 is completed, start encoding MB3.

Time 13: Since the encoding of MB1, MB2 and MB3 is completed, it is possible to start the motion vector search of MB5. Start MB5 motion vector search.

Time 15: MB4 motion vector search completes and MB4 encoding begins.

Time 16: Now that the MB4 encoding is complete, it is possible to start the MB6 motion vector search. Start MB6 motion vector search. MB5 motion vector search is completed and MB5 encoding is started.

Time 17: Now that the MB2, MB4, and MB5 encodings are complete, it is possible to start the MB7 motion vector search. Start MB7 motion vector search. Now that the MB3 and MB5 encodings are complete, it is possible to start the MB8 motion vector search. Start MB8 motion vector search.

Time 19: MB6 motion vector search completes and MB6 encoding begins.

Time 20: MB6 encoding is complete and MB9 motion vector search can be started. Start MB9 motion vector search. MB7 motion vector search is completed and MB7 encoding is started.

Time 21: Now that the encoding of MB4, MB6 and MB7 is completed, it is possible to start the motion vector search of MB10. Start MB10 motion vector search. Since the motion vector search of MB8 is completed, start encoding MB8.

Time 22: Now that the encoding of MB5, MB7 and MB8 is complete, it is possible to start the motion vector search of MB11. Start motion vector search for MB11.

Time 23: MB9 motion vector search completes and MB9 encoding begins.

Time 24: Now that the MB9 encoding is complete, it is possible to start the MB12 motion vector search. Start MB12 motion vector search. MB10 motion vector search is completed and MB10 encoding is started.

Time 25: MB11 motion vector search completes and MB11 encoding begins.

Time 26: Now that the encoding of MB7, MB10 and MB11 is complete, it is possible to start the motion vector search of MB14. Start the motion vector search of MB14.

Time 27: Since the encoding of MB8 and MB11 is completed, it is possible to start the motion vector search of MB15. Start MB15 motion vector search. MB12 motion vector search is completed and MB12 encoding is started.

Time 28: Now that the MB12 encoding is complete, it is possible to start the MB16 motion vector search. Start MB16 motion vector search. The motion vector search of MB13 is completed, and the encoding of MB13 is started.

Time 29: Now that the encoding of MB9, MB12 and MB13 is complete, it is possible to start the motion vector search of MB17. Start motion vector search for MB17. The motion vector search of MB14 is completed, and the encoding of MB14 is started.

Time 30: Now that the encoding of MB10, MB13 and MB14 is complete, it is possible to start the motion vector search of MB18. Start MB18 motion vector search. MB15 motion vector search is completed and MB15 encoding is started.

Time 31: Now that the encoding of MB11, MB14 and MB15 is complete, it is possible to start the motion vector search of MB19. Start the motion vector search of MB19. MB16 motion vector search is completed and MB16 encoding is started.

Time 32: Now that the MB16 encoding is complete, it is possible to start the MB20 motion vector search. Start MB20 motion vector search. The motion vector search of MB17 is completed, and the encoding of MB17 is started.

As can be seen from the above explanation and FIG. 27 (b), it is possible to operate the three ME units and the encoding unit continuously without creating free time after the time 27. It is possible to execute motion vector search for three macroblocks in parallel, and further execute motion vector search and encoding in parallel (the number that can be parallelized is small in the upper left and lower right regions of the frame). ..

In this embodiment, the case where the number of ME units is three has been described, but the case where the number of ME units is four or more can be similarly implemented. The frame size shall be large enough. If there are 4 ME units and the processing time of the ME unit for one macroblock is 4 times the processing time of the encoding unit, 4 ME units and 1 encoding unit are continuously connected without creating free time. Can be operated. The same applies when the number of ME units is larger.

It is also possible to implement the encoding process other than the motion vector search by the personal computer so that the expansion board of the personal computer performs the motion vector search with a large amount of calculation. When implemented in this way, ME units 0, 1 and 2 correspond to the expansion board of the personal computer, the encoding unit corresponds to the personal computer, and the personal computer controls the whole. One expansion board may be used as one ME unit, or one expansion board may have the functions of a plurality of ME units. An image coding device using a personal computer equipped with four or more ME units can be similarly implemented.

When the motion vector search function is implemented as an expansion board of a personal computer, it can be similarly implemented even if the motion vector search for a plurality of macroblocks is performed with one call from the personal computer. By doing so, the number of times the expansion board is called from the personal computer is reduced, and the overhead of calling the expansion board can be reduced.

In the present embodiment, since the motion vectors of the left, upper, and upper right macroblocks are used to obtain the PMV for the current macroblock, the processing of these macroblocks is completed before the processing of the current macroblock is started. I needed to be there. However, the reason is not limited to seeking PMV. If the processing of the macroblock currently depends on the processing result of the macroblock on the left, top, and upper right, the method of the present invention can be applied. In the present embodiment, the reason why the macroblock currently depends on the left, upper, and upper right macroblocks is to obtain PMV, but the same applies not only to obtain PMV but also to depend on other reasons. It is possible to carry out. It should be noted that the macroblock currently dependent on the macroblock is not limited to the left, upper, and upper right macroblocks, and the same implementation can be performed even if the macroblock currently dependent on the macroblock is in other cases. For example, even if the macroblock currently depends on the left, top, and upper left macroblocks, it can be implemented in the same manner. Even if the macroblock currently depends on the macroblocks on the left, upper left, top, and upper right, it can be implemented in the same way.

The image coding device according to the present invention has a feature that it can perform pipeline processing in macroblock units, and is useful as an image coding device in applications such as digital broadcasting, video conferencing, and storage media.

<figref num="1">Basic configuration diagram of the coding device according to the first embodiment of the present invention</figref><figref num="2">Basic configuration diagram of the decoding device according to the third embodiment of the present invention</figref><figref num="3">Basic configuration diagram of a conventional MPEG2 coding device</figref><figref num="4">Basic configuration diagram of a conventional MPEG2 decoding device</figref><figref num="5">(a) Diagram showing the processing contents of each stage in macroblock pipeline processing (b) Diagram showing macroblock pipeline processing</figref><figref num="6">The figure which shows the coding order of a macroblock in Embodiment 1 of this invention.</figref><figref num="7">The figure which shows the coding order of a macroblock in Embodiment 2 of this invention.</figref><figref num="8">Explanatory drawing of spatial direct mode</figref><figref num="9">The figure which shows the coding order of a macroblock in a conventional method</figref><figref num="10">Explanatory drawing of division of coded macroblock</figref><figref num="11">Explanatory drawing of intra 16 × 16 forecast</figref><figref num="12">Explanatory drawing of intra 4x4 forecast</figref><figref num="13">Flowchart of macroblock order selection method according to Embodiment 1 of the present invention</figref><figref num="14">Flowchart of macroblock order selection method according to Embodiment 2 of the present invention</figref><figref num="15">Basic configuration diagram of the still image coding device according to the fifth embodiment of the present invention</figref><figref num="16">Basic configuration diagram of the macroblock order rearranging device according to the sixth embodiment of the present invention.</figref><figref num="17">Basic configuration diagram of the macroblock order rearranging device according to the seventh embodiment of the present invention.</figref><figref num="18">Diagram showing the processing order of macroblocks</figref><figref num="19">Diagram showing the processing order of macroblocks</figref><figref num="20">The figure which shows the processing order of MBAFF in Embodiment 8 of this invention.</figref><figref num="21">The figure which shows the coding order of MBAFF in the conventional method</figref><figref num="22">Explanatory drawing of motion compensation block</figref><figref num="23">Diagram showing macroblocks used to derive PMV</figref><figref num="24">The figure which shows the processing order of the macroblock in Embodiment 9 of this invention.</figref><figref num="25">The figure which shows the processing order of the macroblock in Embodiment 10 of this invention.</figref><figref num="26">The figure which shows the processing order of the macroblock in Embodiment 11 of this invention.</figref><figref num="27">The figure which shows the processing order of the macroblock in Embodiment 12 of this invention.</figref>

Code description

10 A / D transform section 11 Format transform section 12 Screen sort section 13 Macroblock order selection section 14 DCT section 15 Quantization section 16 Rate control section 17 Motion vector detection, intra prediction section 18 Motion compensation mode selection section 19 Inverse quantization Part 20 Inverse DCT part 21 Entropy coding part 22 Buffer 23 Video memory 30 Buffer 31 Variable length decoding part 32 Inverse quantization part 33 Inverse DCT part 34 Screen sorting part 35 Format conversion part 36 D / A conversion part 37 Motion compensation Part 38 Video memory 39 Macroblock order selection part 50 A / D conversion part 51 Format conversion part 52 Screen sorting part 53 DCT part 54 Quantization part 55 Variable length coding part 56 Buffer 57 Rate control part 58 Inverse quantization part 59 Inverse DCT part 60 Motion vector detection part 61 Motion compensation mode selection part 62 Video memory 70 Buffer 71 Variable length decoding part 72 Inverse quantization part 73 Inverse DCT part 74 Screen sorting part 75 Format conversion part 76 D / A conversion part 77 Motion compensation unit 78 Video memory 80 Prediction unit 81 Residual calculation unit 82 DCT unit 83 Quantization unit 84 Zigzag scan unit 85 Variable length coding unit 86 Macroblock order selection unit 87 Frame memory 88 Inverse DCT unit 89 Inverse quantization unit