Adaptive Coding Method for Interlaced Scan Digital Video Sequences

This invention relates to efficient information coding of interlaced scan digital video sequences for digital storage media or transmission media.

Standardization efforts of digital coding methods for video signals are actively progressing nowadays. Such standardization efforts include the studies of digital coding of various video signal formats at different bit-rates. In terms of scanning techniques which define how the video sequence is captured by recording devices and refreshed on display devices, video sequences can be classified into two types: progressive scan video sequences, and interlaced scan video sequences. In a progressive scan video sequence, a frame in the sequence is captured and refreshed sequentially line by line from top to bottom of the frame. An interlaced scan video sequence frame consists of two fields, the even field made up of the even lines of the frame and the odd field made up of the odd lines of the frame. Capturing and refreshing are performed first on the even field, sequentially from top to bottom of the field, and followed by the odd field in the same manner. Since a large number of present sources use the interlaced scan format (e.g. NTSC, PAL), a number of research efforts had been directed to efficient coding of the interlaced scan video sequence.

The prior research results can be classified into three categories: frame coding processes, field coding processes, and interpolated field coding processes. In a frame coding process, (For example in Kazuto Kamikura and Taikun Li, "Consideration of Bit Allocation and Distribution of Moving Image Coding for Storage Media", DAPA Meeting Report, Fourth Telematic Symposium, Tokyo, February 1991) a video sequence is basically coded frame by frame where the even and odd fields are combined in the interlaced manner (the frames are treated as if they were progressive). Each frame in a frame coding process can be partitioned into blocks of pixel data which are then processed by a block coding method such as Discrete Cosine Transform (DCT) Coding with or without Motion Compensation (MC) as described in MPEG Video Simulation Model Three, International Organization for Standardization, Coded Representation of Picture and Audio Information, 1990, ISO-IEC/JTC1/SC2/WG8 MPEG90/041. If a frame is coded independent of other frames in the sequence and without different treatments to the even field and the odd field, the process is called an intra-frame coding process; if the frame is coded with motion compensation using other frame(s) in the sequence, the process is called an inter-frame coding process. In summary, the frame coding process is a process whereby the video sequence is coded with just an intra-frame coding process, or a combination of intra-frame and inter-frame coding processes.

In a field coding process, a video sequence is first split into two sequences, the even field sequence and the odd field sequence, where each of the even field and odd field sequences is subjected to the same coding process. (See, for example, the paper by Ichiro Andoh, Y. Yamada et al., "Some Considerations and Experiments of Interlaced Moving Image Coding", DAPA Meeting Report, Fourth Telematic Symposium, Tokyo, February 1991.) Motion compensation or motion interpolation in a field coding process can be performed independently on each of the even field sequence and odd field sequence, or inter-dependently on the two sequences as illustrated by the paper by Ichiro Andoh et al. The field coding process, hence, is just an intra-field coding process or a combination of intra-field and inter-field coding processes.

As for the interpolated field coding process, only one of the field sequence is coded, and the other field sequence is reproduced by a prediction or interpolation process on the coded field sequence. Examples of this coding process are described in the paper by Feng-Ming Wang and Dimitris Anastassiou, "High-Quality Coding of the Even Fields Based on the Odd Fields of the Interlaced Video Sequences," IEEE Transection on Circuits and Systems, January 1991, and the MPEG Video Simulation Model Three, International Organization for Standardization, Coded Representation of Picture and Audio Information, 1990, ISO-IEC/JTC1/SC2/WG8 MPEG90/041.

With objects in the interlaced scan video sequence maintained stationary, correlation between adjacent pixels on every line and adjacent lines is high which allows popular image compression methods such as the conventional Discrete Cosine Transform Coding method, to achieve high compression ratio in a frame coding process (taking advantage of the high correlation between the lines) as compared of the high correlation between the lines) as compared to the field or interpolated field coding process. Inter-frame motion compensation can also be performed in this case with better efficiency. However, if objects in the sequence start to move, the correlation between the fields will drop, and hence the efficiency of the DCT method, for example, will be better if a field coding process is used. Furthermore, when motion compensation is involved in this situation, a inter-field coding process which performs the motion compensation individually on each fields has the advantage of better estimating the motion of the objects in the sequence. It can be seem that in general, the frame coding, field coding, and interpolated field coding process are sub-optimal in terms of efficiency given the fact that movement of objects in a sequence can be very dynamic. The improvement of efficiency of video coding systems is especially important in high bit-rate reduction coding systems.

In order to take advantage of frame (intra/inter) coding and field (intra/inter) coding processes, a method can be deviced to adaptively examine each region of the frame to decide which of the frame and field coding processes to use. In such a way, stationary regions in the frame are coded using a frame coding process efficiently making use of the high spatial correlations in the frame; and regions in the frame corresponding to the moving objects in the sequence are coded using field coding process since better correlation can be found within each fields in these regions.

This method can be done by partitioning each frame of an input interlaced scan video signal into smaller blocks of pixel data; determining a difference of pixel values between two fields within each of said blocks; subjecting a given block to a frame coding process if the difference between the two fields within the block is determined to be low; and otherwise subjecting the block to a field coding process.

By the above-described method, blocks with motion between the fields or less correlated fields can be separated from blocks that are highly spatially correlated between the fields, and field coding process or frame coding process can be optimally applied to achieve the best results in the two kinds of blocks mentioned. Such a case in the frame coding process, the block can be intra-frame coded using conventional block coding techniques such as the DCT method or inter-frame coded using block coding techniques with inter-frame motion compensation. As in the case of field coding process, the two fields in the block can be separated into sub-blocks and intra-field coded using conventional block coding method, or inter-field coded with inter-field motion compensation.

FIG. 1 is a block diagram of the interlaced scan video coding method in connection with one embodiment of the present invention;

FIG. 2 is a block diagram of the frame coding process and the field coding process illustrating part of the embodiment of the present invention;

FIG. 3 is a block diagram of the inter-frame motion compensation process illustrating part of the embodiment of the present invention;

FIG. 4 is a block diagram of the inter-field motion compensation process illustrating part of the embodiment of the present invention;

FIG. 5 is an explanatory drawing of an example arrangement and relationship of the I-picture, the P-picture, and the B-picture;

FIG. 6A is an explanatory drawing illustrating an example effect of the frame restructuring process;

FIG. 6B is an explanatory drawing illustrating an example intra-frame sub-sampling process for the chrominance data;

FIG. 7A is an explanatory drawing illustrating an example effect of the field restructuring process;

FIG. 7B is an explanatory drawing illustrating an example intra-field sub-sampling process for the chrominance data;

FIG. 8 is a block diagram of the block coding process in connection with part of one embodiment of the present invention;

FIG. 9 is a block diagram of the block decoding process in one embodiment of the present invention.

According to the prior art in motion, compensation (e.g. the MPEG Video Simulation Model Three, International Organization for Standardization, Coded Representation of Picture and Audio Information, 1990, ISO-IEC/JTC1/SC2/WG8 MPEG90/041), the frames, which can also be referred as pictures, in an interlaced scan video sequence can be classified in three ways: (1) intra-coded frames (or I-frames) wherein each frame is coded using information only from itself; (2) predictive-coded frames (or P-frames) wherein each frame is coded using motion compensated prediction from a past I or P-frame; and (3) bidirectionally predictive-coded frames (or B-frames)--wherein each frame is coded using motion compensated prediction from a past and/or future I or P-frame. An example arrangement of the three types of frames in a sequence is shown in FIG. 5. The number of P-frames in between the I-frames and the number of B-frames in between the I or P-frames are not necessarily 4 and 2 respectively. Other suitable numbers may be used in coding a sequence; for examples, there can be no B-frame or no B and P-frames at all.

FIG. 1 is a block diagram of an interlaced scan video signal coding apparatus using the method according to one embodiment of the present invention. An input frame 1 of a sequence is first partitioned into blocks of pixel data by the block partition process 2, and each of the blocks is subjected to an inter-field difference detection process 3 that examines the differences between the pixel data from the two fields within the block. One example of the inter-field difference detection process would be to calculate the meansquare error between the even and the odd line pairs of the block luminance area, and compare the calculated result to the meansquare error calculated between the consecutive odd line pairs and the consecutive even line pairs of the same area intra-field difference detection process; if the ratio of the square error between the even and odd line pairs over the square error between the consecutive odd line pairs and even line pairs is greater than a pre-defined threshold value, the block 4 will be coded by a field coding process 5; otherwise the said block will be coded by a frame coding process 6. The ratio of the two calculated square errors can also be compared to a multiple of thresholds depending on the block activity to achieve better detection. An example inter-field difference detection process implemented as a `C` program procedure for a block size of 16.times.16 pixels can be given by:

The block size, the threshold values of 12, 18, 30, and the activity values of 8000, 100000 of the above `C` program example can also be adjusted or expanded to other suitable values if needed. The result 7 of the inter-field difference detection process is coded as side information.

An example embodiment of an apparatus performing the frame coding process 6 and the field coding process 5 is illustrated in FIG. 2. In the frame coding process, the input block is subjected to an intra-frame coding process which comprises the frame restructuring process 21, the block coding process 22, and the block decoding process 23 if the input frame is an I-frame, or subjected to an inter-frame coding process which comprises the inter-frame motion compensation process 20, the frame restructuring process 21, the block coding process 22, and the block decoding process 23 if the input frame is not an I-frame. Similarly, in the field coding process 5, the input block is subjected to an intra-field coding process which comprises the field restructuring process 25, the block coding process 22, and the block decoding process 23 if the input frame is an I-frame, or else subjected to an inter-field coding process which comprises of the inter-field motion compensation process 26, the field restructuring process 25, the block coding process 22, and the block decoding process 23. The frame(s) memory 28 stores reconstructed frames from the results of the block decoding process 23, and it will be used by the inter-frame or inter-field motion compensation process (20, 26) of the input blocks from the frame to be coded.

FIG. 3 is the apparatus block diagram of one embodiment of the inter-frame motion compensation process. Depending on the input frame type, the input block 27 to the inter-frame motion compensation process can be subjected to one of the motion compensation process; the inter-frame motion prediction process if the input frame is a P-frame, or the inter-frame motion interpolation process if the input frame is a B-frame. In the inter-frame motion prediction process, the input block is subjected to an inter-frame forward motion vector detection process 41 to estimate a forward motion vector 44. Conventional block matching techniques may be used in detecting the motion vector. Forward motion prediction process 42 is then performed, which basically obtains a forward motion displaced block from the previously coded frame using the detected forward motion vector. Finally, the result of the forward motion prediction process 42 is compared to the input block 27 in the motion compensation mode selection process 43 to decide which one of the two blocks should be coded since motion compensation may not always be successful, especially in regions with very fast changes in the video sequence. If the input block is decided to be coded, the actual value of the input block will be coded; else, the difference of the input block and the forward motion displaced block, i.e. the forward motion compensated block, will be coded. An example procedure in C Language of the motion compensation mode selection process is:

The inter-frame motion interpolation process comprises the processes of inter-frame forward motion vector detection 41, inter-frame backward motion vector detection 46, forward motion prediction 42, forward/backward motion interpolation 47, backward motion prediction 48, and the motion interpolation mode selection 49. With reference to the past and future I or P-frame (coded or not coded frames may be used), the inter-frame forward and backward motion vector detection processes estimate a forward motion vector and a backward motion vector by using conventional block matching techniques. With the two estimated motion vectors, the forward motion displaced block and the backward motion displaced block are found by forward and backward motion prediction processes (42 & 48) in the same way mentioned before. The forward/backward motion interpolation process 47 calculates the forward/backward motion interpolated block by averaging the forward and the backward motion displaced block. Weighting or no weighting based on the frame distances may be used when averaging the forward and backward motion displaced blocks. The above three mentioned motion displaced and interpolated blocks are compared together with the input block 27 at the motion interpolation mode selection process 49 to determine which block is to be coded. One method of determining which block is to be coded is by comparing the mean square errors described in the MPEG Video Simulation Model Three, International Organization for Standardization, Coded Representation of Picture and Audio Information, 1990, ISO-IEC/JTC1/SC2/WG8 MPEG90/041. If the determined block is not the input block, the difference of the determined block and the input block will be coded.

Data of the two fields in the input block 29 (see FIG. 2) to the field coding process 5 is generally uncorrelated or contains motion as selected by the inter-field difference detection process 3; therefore, an inter-field motion compensation process 26 which performs independently motion compensation on the data from the two fields is selected. The example embodiment of the inter-field motion compensation process shown in FIG. 4 is, however, very similar to the inter-frame motion compensation process (FIG. 3) except for the motion vector detection processes and the construction of the motion displaced block. In the inter-field forward/backward motion vector detection process 61 and 62, one motion vector will be estimated for each of the field in the input block 30, and in the forward and backward directions; hence, the forward motion vector 1 and 2, and backward motion vector 1 and 2 are to be estimated. Based on the estimated motion vector 1 and 2, two motion displaced fields of the block are obtained from previous coded pictures to form the motion displaced block and also the motion interpolated block in processes 63, 64, 65. The mode selection processes 43 and 49 are the same processes used in the inter-frame motion compensation process 20. Regarding the coding of the forward motion vector 1 and 2, or backward motion vector 1 and 2, as the difference in motion in the two fields within the input block and between previous neighboring coded block is not expected to be high, an efficient way of coding is to delta code the motion vector (forward and/or backward) or one field with reference to the previous coded block, and the delta difference of the motion of the two fields within the input block.

The input block 4 or the output of the inter-frame motion compensation process is subjected to the frame restructuring process (numeral 21 of FIG. 2) where it is spatially partitioned into smaller sub-blocks suitable for a block coding process for example based on the DCT (Discrete Cosine Transformation) method. FIG. 6A is an example of a 16.times.16 block of luminance data (Y) partitioned in such a way into 4 smaller 8.times.8 sub-blocks. The interlaced fields in the frame restructuring process are not separated in order to allow the block coding process to take advantage of the correlation between the fields. The frame restructuring process can further comprise an intra-frame sub-sampling process which reduces the resolution of the chrominance information (Cr/Cb). Referring to FIG. 6B, an example of an 8.times.16 chrominance block (co-sited with a 16.times.16 luminance block in a 4:2:2 source) is intra-frame sub-sampled to an 8.times.8 chrominance sub-block by averaging each even and odd line pair of the chrominance block. Such sub-sampling of the chrominance signal is done to reduce the amount of information needs to be coded without generating visible differences.

The field restructuring process (numeral 25 of FIG. 2) accepts the result from the inter-field motion compensation process (numeral 26 of FIG. 2) or the input block 4. The process partitions the luminance data (Y) of an input into smaller sub-blocks with the two fields separated. FIG. 7A shows the such a process of partitioning of a 16.times.16 input luminance block into four 8.times.8 sub-blocks, two of which contain the even field data and the other two contain the odd field data. This is done so that the block coding process (numeral 22 of FIG. 2) would take advantage of the higher correlation within the field in each sub-block. The field restructuring process may further comprise an intra-field sub-sampling process which reduces the resolution of the chrominance information (Cr/Cb) in each field. Referring to FIG. 7B, an example of an 8.times.16 chrominance block is intra-field sub-sampled to an 8.times.8 chrominance sub-block by separately averaging every two consecutive lines in each field. The averaged lines may be rearranged such that the two fields are separated in the output sub-block. The averaged lines may also be arranged in the interlaced way in the output sub-block, but the resultant coding efficiency was found not to be as good as the previous mentioned way.

Each sub-block produced by the frame or field restructuring process is subjected to a block coding process (numeral 22 of FIG. 2) for data compaction by exploring correlations in the sub-block. An embodiment of the block coding apparatus is shown in FIG. 8 which comprises the means for discrete cosine transforming (DCT) 80 of the sub-block into DCT coefficients; quantizing 81 the DCT coefficients based on a rate-controller 84 that monitors the amount of output information 85; zig-zag scanning 82 the quantized DCT coefficients; variable length coding (VLC) 83 the result of the zig-zag scanning and all necessary side information describing the sub-block to produce the encoded information 85 for digital storage media or transmission media. An example implementation of the block coding process illustrated in FIG. 8 can be found in detail in the MPEG Video Simulation Model Three, International Organization for Standardization, Coded Representation of Picture and Audio Information, 1990, ISO-IEC/JTC1/SC2/WG8 MPEG90/041.

The block decoding process (numeral 23 of FIG. 2) decodes the output of the block coding process (numeral 22 of FIG. 2), and reconstructs the frames. The frames reconstructed by the block decoding process are placed in the frame memory (numeral 28 of FIG. 2) for use by the inter-frame/inter-field motion compensation processes (numeral 20 & 26 of FIG. 2). The block decoding process is also used to decode the encoded information from digital storage media or transmission media that is created by the block encoding process and/or the motion compensation process. FIG. 9 is an embodiment of the block decoding apparatus, corresponding to the block coding process described in FIG. 8, which comprises means for demultiplexing/VLC decoding 90 the encoded information to reproduce the zig-zag scanned sub-block and the included side information; inverse zig-zag scanning 91 followed by inverse quantizing 92 of the said sub-block to reproduce the DCT coefficients; inverse DCT 93 of said coefficients; subjecting the result of the inverse DCT to an inverse of the inter-frame or inter-field motion compensation process (FIGS. 3 & 4) 94 & 95 according to the coded picture type (I, P or B-frame) and the coded result of the inter-field difference detection process (numeral 3 of FIG. 1) to reproduce the reconstructed sub-block 96; reversing of the frame/field restructuring process 97 & 98 according to the coded result of the inter-field difference detection process to reproduce the reconstructed block 100 which can then be placed into the frame memory 101 for the inverse motion compensation process 94 or 95 or for display onto a monitor screen. The demultiplexer/VLC decoder and the inverse zig-zag scanner may be omitted if the block decoding process is to be used in conjunction with the block encoding process in the video signal encoder as the input to the inverse quantizer and other side information may be obtained from the corresponding processes in the block coding process directly.

As described above, the input frame is partitioned into smaller blocks of pixel data where the two fields in each block is examined for correlation. If the difference between the two fields in the block is low (or the correlation is high), the block will be coded with a frame coding process that assumes all lines in the block are progressive scanned, and therefore, with efficient inter-frame motion compensation process and chrominance data intra-frame sub-sampling process designed. On the other hand, if the difference between the two fields in the block is high (or the correlation is low), the block will be coded with a field coding process where more emphasis is made on exploring correlation within each field (intra-field) and correlation of each field and its neighboring fields (inter-field); furthermore, intra-field sub-sampling of the chrominance data is better performed in such blocks. In general video sequences, the level of correlation within each picture frame differs between regions that contain stationary scene or objects and regions that contain moving scene or objects; therefore, the present invention provides an effect of more efficient or adaptive coding the two types of regions with methods that are more optimal to each the of regions. In a fixed bit-rate video coding system, the present invention provides an effect of better reconstructed picture quality.