Apparatus and method of adaptively coding/decoding interlaced shaped material

[0002] 1. Field of the Invention

[0003] The present invention relates to coding/decoding of an interlaced video, and more particularly to an apparatus and method of adaptively coding/decoding interlaced shape information, for coding and decoding shape information in units of frame type or field type based upon characteristics of the shape information when coding interlaced video, thereby having a high compression ratio.

[0004] 2. Description of Related Art

[0005] For the future video/audio technology and system, development is in progress to make it realize to support novel video/audio applications which existing known standards (e.g., H.263 and H.261 by ITU-T and MPEG1 and MPEG-2 by ISO/IEC) cannot support. An object-based interactive functionality and an object-based manipulation are representative examples of new functionality. To offer novel and various functionality, transmission of shape information is required. The shape information is for dividing a picture into an object region and a non-object region (background). This shape information allows for transmitter and receiver to perform signal processing focusing on the object region instead of the whole picture and offers the novel functionalities. Binary shape information has a form of a binary mask where pixels have different values according to whether the pixel is for the object or non-object. For example, the values of pixels for the object and non-object(background) are 0 and 1, respectively. It should be noted that these values are not limited to a specific value. A video coding method using such shape information is called object-based video coding.

[0006] The shape information has a great amount of data, so it is deemed to be important how to effectively compress the shape information. This aims at improvement of efficiency in compression coding of the shape information.

[0007] FIG. 1 is a block diagram of a general object-based video coder.

[0008] Signals of a picture consists of shape information and texture information and two types of information are respectively inputted to a shape coding unit 11 and motion estimation unit 12

[0009] The shape coding unit 11 performs loss coding or lossless coding with respect to the shape information in each picture. Reconstructed shape information is inputted to both motion compensation unit 13 and texture coding unit 17. Both motion compensation unit 13 and texture coding unit 17 operate based upon an object. A shape bitstream, which is the other output of the shape coding unit 11, is inputted to a multiplexer 18.

[0010] The motion estimation unit 12 estimates motion information of current picture's texture information using input texture information of the current picture and texture information of a previous picture which is stored in a previous reconstructed frame memory 14. Estimated motion information is inputted to the motion compensation unit 13 while a motion information is encoded and its bitstream is inputted to the multiplexer 18. The motion compensation unit 13 performs motion compensated prediction using the motion information obtained through the motion estimation unit 12 and the previous reconstructed picture in the previous reconstructed frame memory 14.

[0011] The texture coding unit 17 encodes a prediction error which is a difference between an input texture information and motion compensated texture information, and is obtained at a subtracter 15. A texture bitstream which is produced through the coding is inputted to the multiplexer 18 and an error signal of reconstructed texture information is inputted to an adder 16. The previous reconstructed frame memory 14 stores a previous reconstructed picture signal produced by the adder 16 which adds the error signal to a motion compensated prediction signal

[0012] Digital video may be classified into progressive video and interlaced video according to frame constructing methods. For the progressive video, a frame is constructed in such a manner that lines subsequently progresses from the top to the bottom. For the interlaced video, a frame is constructed in such a manner that two fields are separately constructed and then lines of two fields are interlaced for constructing a frame. A height (the number of lines) of a field is a half of the height of a frame. This is illustrated in FIG. 2. FIG. 2ashows a frame in the progressive video and FIG. 2bshows two fields—a top field and a bottom field—and a frame in the interlaced video. In FIG. 2, the lines of the top and bottom fields are denoted as solid arrows and dashed arrows, respectively, and the lines of each field are interlaced (the solid arrows are interlaced with the dashed arrows) to construct an interlaced frame.

[0013] When the top and bottom fields are constructed, as shown in FIG. 2b, there is a time lag between the two fields and the top field precedes the bottom field. In other cases, the bottom field may precede the top field. Because of the time lag between the top field and the bottom field, signal characteristics of two adjacent lines in the interlaced frame can be different. Particularly in case of a picture having a lot of motion, this feature is prominent. When applying video coding tools developed in accordance with properties of the progressive video, such as motion estimation, motion compensation, and discrete cosine transform (DCT), coding efficiency may be reduced in the case of interlaced video coding. Technology such as field-based motion estimation and compensation and adaptive frame/field DCF has been developed to prevent this problem. Such technology is disclosed in the standard MPEG-2 and has been frequently applied to actual application products such as digital TV. However, the technologies for coding/decoding the interlaced shape information has not been presented as yet because the adoption of the shape information was investigated most recently. Therefore, this technology has a very important role in the (future) multimedia applications including interlaced video coding.

[0014] FIGS. 3aand 3bshow interlaced shape information where an object has no motion or a little motion between two fields. As shown in FIG. 3a, correlation between lines in a frame is higher compared with that in each field, so it is better to code the shape information in the unit of frames in this case.

[0015] FIGS. 4aand 4bshow interlaced shape information where an object has much motion between two fields. As shown in FIG. 4bwhere the lines are grouped into each field, variation between neighboring lines in each field is little and correlation between lines is high in the same field. However, as shown in FIG. 4a, considering in units of a frame type, the variation between neighboring lines is larger and the correlation between lines is lower. Therefore, coding efficiency is reduced when coding the shape information in the unit of frames. To overcome this problem, the present invention provides a method of coding the shape information having a lot of motion in units of a field type.

[0016] Furthermore, it is best to adaptively select one of a field type coding and frame type coding rather than to use only one type coding with respect to the interlace shape information.

[0017] Accordingly, the present invention is directed to apparatus and method for adaptively coding/decoding interlaced shape information that substantially obviates one or more of the limitations and disadvantages of the related art.

[0018] An objective of the present invention is to provide apparatus and method of adaptively coding/decoding interlaced shape information, for detecting correlation between lines in a frame and correlation between lines in a field and coding the shape information in units of a frame type or a field type according to the correlation when coding an interlaced video.

[0019] The present invention offers a method of adaptively selecting either a frame coding mode or a field coding mode. During a process of coding shape information, motion estimation and motion compensation for the shape information is performed in accordance with characteristics of the shape information. Errors between pixels in each field and between pixels in a frame are calculated and coding is performed in favor of the less error. When the error in the frame is larger than the error in two separate fields, the shape information is coded from the field. When the error in each field is larger than the error in the frame, the shape information is coded from the frame. To improve efficiency in interlace shape information coding, motion estimation and compensation for the shape information is adaptively subjected to a frame or field coding process.

[0020] To achieve these objectives and advantages, the present invention determines whether to code shape information of a binary alpha block (BAB) from a frame or from a field based upon the amount of motion. The amount of motion is estimated with respect to the BAB. A type of the BAB is determined according to the estimated amount of motion. When the BAB falls under a type which does not need coding data for indicating the type is coded and transmitted. When the BAB falls under a type which needs coding, it is determined whether to code the BAB from a frame or from a field according to the estimated amount of motion. Differences between pixel pairs in line pairs each comprising an odd and an adjacent even line are calculated and summed up to compute an error of the frame. Differences between pixel pairs in consecutive odd line pairs and differences between pixel pairs in consecutive even line pairs are calculated and summed up to compute an error of individual fields. The two calculated errors of the frame and the separate fields are compared to determine whether to code the shape information from the frame or from the separate fields. When coding the information from the frame, the frame is divided into macroblocks and the coding is performed with respect to each macroblock for transmission. When coding the information from the separate fields, the odd and even fields, each is divided into macroblocks and the coding is performed with respect to each macroblock for transmission.

[0021] Additional features and advantages of the invention will be set forth in the description which follows, and in part will be apparent from the description, or may be learned by practice of the invention. The objectives and other advantages of the invention will be realized and attained by the structure as illustrated in the written description and claims hereof, as well as the appended drawings.

[0022] It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are intended to provide further explanation of the invention as claimed.

[0023] The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate embodiments of the invention and together with the description serve to explain the principles of the invention.

[0024] In the drawings:

[0025] FIG. 1 is a block diagram of a general object-based video coder;

[0026] FIGS. 2aand 2bare diagrams for showing progressive scanning and interlaced scanning;

[0027] FIGS. 3aand 3bshow a 16×16 shape information without motion or with little motion and its fields;

[0028] FIGS. 4aand 4bshow a 16×16 shape information with much motion and its fields;

[0029] FIG. 5 is a block diagram of an interlaced coding apparatus according to one embodiment of the present invention;

[0030] FIGS. 6aand 6bshow a notation of pixels of shape information forming a block of 16×16;

[0031] FIG. 7 is a block diagram of a coding mode determining unit according to one embodiment of the present invention;

[0032] FIG. 8 is a block diagram of a coding mode determining unit according to another embodiment of the present invention;

[0033] FIGS. 9aand 9bare block diagrams of a frame type coding unit and a field type coding unit according to the present invention;

[0034] FIGS. 10aand 10bshow an INTRA template and an INTER template which are used in context based arithmetic encoding (CAE);

[0035] FIG. 11 is a flow chart how interlaced shape information is adaptively coded according to the present invention;

[0036] FIG. 12 is a block diagram of a shape information decoding apparatus according to the present invention;

[0037] FIG. 13 is a detailed block diagram of a frame type decoding unit and a field type decoding unit according to the present invention;

[0038] FIG. 14 is a block diagram of a coding apparatus for interlaced shape information according to another embodiment of the present invention;

[0039] FIG. 15 is a flow chart of a coding method considering a conversion ratio (CR) according to one embodiment of the present invention;

[0040] FIG. 16 is a flow chart showing how a CR is determined;

[0041] FIG. 17 is a flow chart showing how to determine each CR and perform coding with respect to a top and a bottom fields in a binary alpha block;

[0042] FIG. 18 is a flow chart showing a method of determining a CR after deciding CAE_type; and

[0043] FIG. 19 is a block diagram of a coding apparatus having a field CR determining unit according to the present invention.

[0044] Reference will now be made in detail to the preferred embodiments of the present invention, examples of which are illustrated in the accompanying drawings.

[0045] With reference to the accompanying drawings, the present invention will now be described in detail. Generally, when coding shape information of a whole picture, a whole picture is divided into macroblocks of a predetermined size and the shape information is coded by each macroblock. A coding unit of the shape information is named a binary alpha block (BAB) hereinafter. The size of the BAB is not limited in this invention but, generally, corresponds to 16 pixels×16 lines.

[0046] FIG. 5 is a block diagram of interlaced coding apparatus according to one embodiment of the present invention. A BAB division unit 51 divides input binary shape information into BAB units of a predetermined size (e.g., 16×16). A coding type mode determining unit 52 checks correlation with respect to the input BAB and determines whether to code in units of a frame type or a field type. A switching unit 53 switches the BAB received from the BAB division unit 51 according to a coding type mode signal SCM produced by the coding type mode determining unit 52. When the coding type mode signal SCM is a frame mode, the switching unit 53 switches the input BAB to a frame type coding unit 56. Alternatively, when the coding type mode signal SCM is a field mode, the switching unit 53 switches the input BAB to a field type coding unit 57. The SCM signal is encoded and its bitstream is sent to a multiplexer for transmitting to a decoder. A motion estimation unit 54 estimates motion information with respect to the input BAB from the BAB division unit 51 and a previous shape information frame. A motion compensation unit 55 compensates the current BAB using the motion information inputted from the motion estimation unit 54 and the previous shape information frame. The frame type coding unit 56 receives the BAB inputted from the BAB division unit 51 and a motion compensated BAB inputted from the motion compensation unit 55 and encodes the shape information in units of a frame type, and reconstructs it and outputs its reconstructed BAB. The field type coding unit 57 receives the BAB inputted from the BAB division unit 51 and a motion compensated BAB inputted from the motion compensation unit 55 and encodes the shape information in units of a field type, and reconstructs it and outputs its reconstructed BAB. A shape reconstructing unit 60 reconstructs the shape information frame from the reconstructed BAB received from the frame type coding unit 56 and the field type coding unit 57. A previous shape memory unit 59 receives a reconstructed shape information from the shape reconstructing unit 60 and stores it. This reconstructed shape information is used as a previous shape information at encoding the next shape information. An overhead coding unit 58 encodes overhead information such as motion information received from the motion estimation unit 54 and the information (e.g., conversion ratio, scan type, BAB_type, and so on) necessary for reconstructing shape information at a decoder which is received from the frame type coding unit 56 and field type coding unit 57. A multiplexer 61 multiplexes the coded data received from the frame type coding unit 56 and field type coding unit 57, the coded overhead information received from the overhead coding unit 59 and the coded SCM signal.

[0047] Once binary shape information is inputted into this apparatus, the binary shape information is divided into blocks of a predetermined size (e.g., 16×16 or 8×8) at the BAB division unit 51 and sent to both the coding type mode determining unit 52 and the motion estimation unit 54. The coding type mode determining unit 52 calculates correlation of the shape information with respect to a top and a bottom fields forming a BAB. The following expression is used as a reference in deciding the correlation of the shape information contained in both fields. $\begin{array}{cc}\sum _{i=0}^6\sum _{j=0}^{15}\left(\left|P_{\left(2i,j\right)}-P_{\left(2i+1,j\right)}\right|+\left|P_{\left(2i+1,j\right)}-P_{\left(2i+2,j\right)}\right|\right)⟩\sum _{i=0}^6\sum _{j=0}^{15}(\left|P_{\left(2i,j\right)}-P_{\left(2i+2,j\right)}\right|+\left|P_{\left(2i+2,j\right)}-P_{\left(2i+3,j\right)}\right|& \left(1\right)\end{array}$

[0048] wherein “i” is a vertical location in the BAB; j, a horizontal location in the BAB; and P_(i,j), a pixel value at the location, (i,j), in the BAB. When P_(i,j)=0, a pixel at the corresponding location is supposed to be one of pixels representing a background, and, when P_(i,j)=1, a pixel at the corresponding location is supposed to be one of pixels representing an object. This formula is applied to the BAB having the 16×16 size and can be changed properly to be applied to other sizes.

[0049] The left in the formula (1) represents a value obtained by summing up differences between each even line(top field) pixel value and its neighboring odd line(bottom field) pixel value, the pixels being at the same horizontal location. Referring to FIG. 6, differences of P_(0,0)and P_(1,0), P_(1,0)and P_(2,0), . . . , P_(0,1)and P_(1,1), P_(1,1)and P_(2,1), . . . , and P_(14,15)and P_(15,15)are calculated and all summed up. The right in the formula (1) represents a value obtained by summing up differences between values of two pixels at the same horizontal location and respectively in two adjacent even lines and differences between values of two pixels at the same horizontal location and respectively in two adjacent odd lines. Referring to FIG. 6, differences of P_(0,0)and P_(2,0), P_(2,0)and P_(4,0), . . . , P_(1,0)and P_(3,0), P_(3,0)and P_(5,0), and P_{(13, 15)}and P_(15,15)are calculated and all summed up.

[0050] When there is much motion since there is temporal difference between each odd line and each even line, the value of the left in the formula (1) is relatively larger. On the other hand, since the value of the right in the formula (1) is based upon a difference between lines of the same field, that is, difference between an odd line and another odd line and difference between an even line and another even line, there is little temporal difference, so the value is not notably larger even though there is much motion.

[0051] Consequently, when there is much motion, the left value is larger than the right value. On the other hand, when there is little motion, the left value is less than the right value.

[0052] As a result, a coding mode signal for selecting a coding mode having a less error is sent to the switching unit 53. When a coding type mode signal SCM is a frame mode, the switching unit 53 switches the BAB from the BAB division unit 51 to the frame type coding unit 56. On the other hand, when a field mode signal is received, the switching unit 53 reads the BAB from the BAB division unit 51 and sends it to the field type coding unit 57.

[0053] An amount of motion in the BAB may be determined according to a reference expressed as: $\begin{array}{cc}\sum _{i=0}^6\sum _{j=0}^{15}\left(A+B\right)\sum _{i=0}^6\sum _{j=0}^{15}\left(C+D\right)& \left(2\right)\end{array}$

[0054] where if (P_(2i,j)≠P_(2i+1,j)), A=1, otherwise, A=0 . . . (2-1),

[0055] if (P_(2i+1,j)≠P_(2i+2,j)), B=1, otherwise, B=0 . . . (2-2),

[0056] if (P_(2i,j)≠P_{(2i+2 j)}), C=1, otherwise, C=0 . . . (2-3), and

[0057] if (P_(2i+1,j)≠P_(2i+3,j)), D=1, otherwise, D=0 . . . (2-4).

[0058] The formulas (1) and (2) have the same result. This is because each pixel in the BAB has one of only two values such as 0 and 1.

[0059] FIG. 7 is a block diagram of a coding type mode determining unit according to one embodiment of the present invention.

[0060] A BAB memory unit 71 stores an input BAB from the BAB division unit 51. An address generating unit 72 generates an address to make the BAB memory output the BAB in units of a frame to a first shape comparing unit 73aand a second shape comparing unit 73bor the BAB in units of a field to a third shape comparing unit 73cand a fourth shape comparing unit 73d. The first shape comparing unit 73acompares a pair of pixels at the same horizontal location in each odd line and each consecutive even line in the frame BAB. The second shape comparing unit 73bcompares a pair of pixels at the same horizontal location in each even and consecutive odd line in the frame BAB. The third shape comparing unit 73ccompares pixels at the same horizontal location in a pair of consecutive odd lines in the BAB. The fourth shape comparing unit 73dcompares pixels at the same horizontal location in a pair of consecutive even lines in the BAB.

[0061] First to fourth counting units 74ato 74drespectively count outputs of the first to fourth shape comparing units 73ato 73d. A first summing unit 75asums up the outputs of the first and second counting units 74aand 74b. A second summing unit 75bsums up the outputs of the third and fourth counting units 74cand 74d. A frame/field mode selecting and coding unit 76 compares outputs of the first and second summing units 75aand 75bto decide a field or frame mode and produces the SCM signal. And the frame/field mode selecting and coding unit 76 also encode the SCM signal and outputs its bitstream to multiplexer 61.

[0062] A coding type mode signal SCM controls the switching unit 53 depicted in FIG. 5 and a bitstream is inputted to the multiplexer 61 depicted in FIG. 5.

[0063] The first shape comparing unit 73acompares a pixel P_(2,j)in the even lines (top field) with a pixel P_(2i+1,j)at the same horizontal position in the consecutive odd lines (bottom field) in the input BAB stored in the BAB memory 71, wherein “j” is one of the positive numbers from 0 to 15, and “i” is one of the positive numbers from 0 to 6. Specifically, it compares P_(0,0)with P_(1,0), P_(2,0)with P_(3,0), . . . , P_(14,0)with P_(15,0), . . . , and P_(12,15)with P_(13,15). As a result of the comparison, two pixels are not equal, 1 is produced, and two pixels are equal, 0 is produced. The second shape comparing unit 73bcompares a pixel P_(2i+1,j)in each odd line with a pixel P_(2i+2,j)at the same horizontal position in each consecutive even line, wherein “j” is one of the positive numbers from 0 to 15, and “i” is one of the positive numbers from 0 to 6. Specifically, it compares P_(1,0)with P_(2,0), P_(3,0)with P_(4,0), . . . , P_(13,0)with P_(14,0). . . , and P_(13,15)with P_(14,15). As a result of the comparison, when two pixels are not equal, 1 is produced, and when two pixels are equal, 0 is produced. The third shape comparing unit 73ccompares a pixel P_(2i,j)in each even line with a pixel P_(2i+2,j)at the same horizontal position in each consecutive even line, wherein “j” is one of the positive numbers from 0 to 15, and “i” is one of the positive numbers from 0 to 6. Specifically, it compares P_(0,0)with P_(2,0), P_(2,0)with P_(4,0), . . . , P_(12,0)with P_(14,0), . . . , and P_(12,15)with P_(14,15). As a result of the comparison, two pixels are not equal 1 is produced, and two pixels are equal 0 is produced. The fourth shape comparing unit 73dcompares a pixel P_(2i+1,j)in each odd line with a pixel P_(2i+3,j)at the same horizontal position in each consecutive odd line, wherein “j” is one of the positive numbers from 0 to 15, and “i” is one of the positive numbers from 0 to 6. Specifically, it compares P_(1,0)with P_(3,0), P_(3,0)with P_(5,0), . . . , P_(13,0)with P_(15,0), . . . , and P_(13,15)with P_(15,15). As a result of the comparison, two pixels are not equal, “1” is produced, and two pixels are equal, “0” is produced. The ranges of “i” and “1” can be changed in accordance with the size of the BAB. In this embodiment described above, the size of the BAB is 16 pixels×16 lines.

[0064] The four counting units 74ato 74dperform the same operation. Each counting unit is reset whenever a new BAB is inputted thereto and increases by one when “1” is inputted. After such operation is performed with respect to whole ranges of “i” and “j”, results of each counting unit are inputted to the their corresponding summing units 75aand 75b.

[0065] Values of the first and second counting units 74aand 74bare summed up at the first summing unit 75a, and values of the third and fourth counting units 74cand 74dare summed up at the second summing unit 75b. It is be noted that a result of the summing at the first summing unit 75acorresponds to a sum of differences between pixels in a pair of consecutive lines in the input BAB while a result of the summing at the second summing unit 75bcorresponds to a sum of differences between pixels in a pair of consecutive lines within the same field.

[0066] In other words, if correlation between pixels of shape information in a pair of consecutive lines is high, the result of the first summing unit 75ais small, and if correlation between pixels of shape information in a pair of consecutive lines in the same field is high, the result of the second summing unit 75bis small When the result of the first summing unit 75ais large, this means that variation of the shape information between the two fields is large. In this regard, the frame/field mode selecting unit 76 decides a coding mode in favor of high correlation and generates a corresponding coding type mode signal SCM. Namely, when the result value of the first summing unit 75ais small the SCM is set to a frame mode, and when the result value of the second summing unit 75bis small, the SCM is set to a field mode.

[0067] The SCM is the information necessary for decoding the shape information at a decoding unit, so it should be encoded and transmitted to a receiver. The decoder decodes the data representing the coding type mode at a shape information decoder and determines whether the data indicates the frame type mode where a block of the shape information is coded in units of a frame type or the field type mode where a block of the shape information is coded in units of a field type. In the embodiment of the present invention, a bit 0 is produced as the SCM for the frame type mode while a bit 1 is produced as the SCM for the field type mode, but the coding method for the SCM is not limited to the present invention.

[0068] FIG. 8 is a block diagram of a shape coding type mode determining unit according to another embodiment of the present invention. A BAB memory unit 81 stores an input BAB from the BAB division unit 51. An address generating unit 82 generates an address to make the BAB memory unit 81 output the BAB in units of a frame type to a first exclusive OR(EOR) operation unit 84 or the BAB in units of a field type to a second EOR operation unit 85. The first EOR operation unit 84 performs an EOR operation with respect to pairs of pixels at the same horizontal location in consecutive line pairs within the frame BAB (65) stored in the BAB memory unit 81. The second EOR operation unit 85 reads odd line field (66) and even line field (67) from the frame BAB (65) stored in the BAB memory unit 81 and performs an EOR operation with respect to pairs of pixels at the same horizontal location in consecutive line pairs within each field. First and second summing units 86 and 87 respectively sum up outputs of the first and second EOR operation units 84 and 85. The summing units can be replaced with counting units because the first and second EOR operation units 84 and 85 output data “0” or “1”, so that the counting unit can increase a count value by one when the data “1” is inputted thereto. A frame/field mode selecting and coding unit 88 compares the outputs of the first and second summing units 86 and 87 to decide a field or frame type mode and generates a coding type mode signal corresponding to a result of the decision.

[0069] The formula (2) can be simply expressed as the formula (3): $\begin{array}{cc}\sum _{i=0}^6\sum _{j=0}^{15}\left(A+B\right)\underset{i=0}{\overset{6}{⟩\sum }}\sum _{j=0}^{15}\left(C+D\right)& \left(3\right)\end{array}$

[0070] where,

[0071] A=P_(2i,j){circle around (X)}P_(2i+1,j). . . (3-1)

[0072] B=P_(2i+1,j){circle around (X)}P_(2i+2,j). . . (3-2)

[0073] C=P_(2i,j){circle around (X)}P_(2i+2,j). . . (3-3)

[0074] D=P_(2i+1,j){circle around (X)}P_(2i+3,j). . . (3-4)

[0075] A character “{circle around (x)}” shown in the formulas (3-1), (3-2), (3-3), and (3-4) is an operator in an EOR operation and has the following features:

[0076] if(a==b), a{circle around (x)}b=0, otherwise, a{circle around (x)}b=10.

[0077] In other words, if a is equal to b, 0 is produced, otherwise, 1 is produced. Therefore, the formulas (3) and (2) equally operate with respect to the shape information. A configuration of a coding type mode determining unit implemented based upon the formula (3) is illustrated in FIG. 8.

[0078] FIGS. 9aand 9bare block diagrams of a frame type coding unit and a field type coding unit according to the present invention. In this embodiment, a context-based arithmetic encoding (CAE) method is employed, but other encoding methods can be used.

[0079] A frame type coding unit 56 comprises a bordering unit 561 and a frame scan type and CAE unit 562 The bordering unit 561 performs the bordering—described in detail below—of the frame BAB received from the BAB division unit 51 via the switching unit 53. The frame scan type and CAE unit 562 decides a scan type, that is, determines whether to perform the CAE in horizontal or vertical direction with respect to the bordered BAB and performs the CAE.

[0080] Through the CAE, each value of pixels, 0 or 1, is arithmetic-encoded before transmission. As shown in FIGS. 10aand 10b, a context template is made using neighboring pixels for construction of and reference to a probability table. For example, if the neighboring pixels in the context are all “0”, namely, background pixels, there is high probability in that a current pixel to be coded is also “0”, and if the neighboring pixels in the context are all “1”, namely, object pixels, there is high probability in that the current pixel to be coded is “1” rather than “0”. Alternatively, if the neighboring pixels in the context are all “0”, namely, background pixels, there is very low probability that the current pixel to be coded is also “1”. As illustrated, when the current pixel value is arithmetic-encoded, it is adaptively encoded by changing the probability in accordance with values of the neighboring pixels.

[0081] The frame scan type and CAE unit 562 performs the CAE while scanning the frame BAB according to the scan type described below. The BAB outputted from the BAB division unit 51 is inputted to the bordering unit 561 via the switching unit 53. The switching unit 53, as described in advance, switches the BAB to the frame type coding unit 56 or the field type coding unit 57 according to the coding type mode signal received from the coding type mode determining unit 52. The bordering operation is necessary for construction of the context shown in FIGS. 10aand 10bwhen a pixel 101, 102, 103 to be coded is located at the border of the BAB. Specifically, when the pixel 101 in FIG. 10ais at a left border of BAB, pixels C0, C1, C5, C6 and C9 are not present, so these pixels should be brought from an adjacent BAB for using CAE. We call this operation BAB bordering. The BAB bordered at the bordering unit 561 is inputted to the frame scan type and CAE unit 562. The frame scan type and CAE unit 562 performs CAE in both directions—horizontal and vertical directions, and decides the direction which shows better coding efficiency by comparing the amounts of coded bits. We call this direction for CAE a scan type. The decided scan type is coded at the overhead coding unit 58 and transmitted to the decoder. Coded data is inputted into the multiplexer 61 in the form of a bitstream and multiplexed at the multiplexer 61 before being transmitted to the decoder. Reconstructed BAB is also inputted to the shape reconstructing unit 60.

[0082] As shown in FIG. 9b, a field type coding unit 57 comprises a BAB field converting unit 571, a bordering unit 572, and a field scan type and CAE unit 573. The BAB field converting unit 571 converts the frame BAB received from the BAB division unit 51 via the switching unit 53 into field BAB 66 and 67 shown in FIG. 6b. The bordering unit 572 performs the bordering of the field BAB received from the BAB field converting unit 571. The field scan type and CAE unit 573 determines whether to scan the bordered field BAB from the bordering unit 572 in transverse direction or longitudinal direction and performs the CAE. Scan type(s) decided at the field scan type and CAE unit 573 is(are) coded at the overhead coding unit 58 and transmitted to the decoder, and coded data is inputted into the multiplexer 61 and multiplexed at the multiplexer 61 before being transmitted to the decoder. Reconstructed field BAB is inputted to the shape reconstructing unit 60.

[0083] FIG. 11 is a flow chart illustrating how interlaced shape information is adaptively coded according to the present invention. When coding the shape information, shape information of a whole picture is divided into binary alpha blocks (BABs). Therefore, an input in the flow chart shown in FIG. 11 is the BAB and an operation of FIG. 11 is performed as many times as the number of BABs in a whole picture.

[0084] Motion estimation is performed by using shape information of a reference picture with respect to the BAB (S111). One motion information per BAB can be estimated or two motion information can be estimated in units of a field type with respect to the BAB. When one motion information estimation and two motion information estimation are used together, a flag for indicating which motion information estimation is used should be transmitted to a receiving part.

[0085] Subsequently, an overhead of the shape information, BAB_type, is decided (S112). The BAB type can be classified into seven types, such as All_—0, All_—255, MVDs=0&&No_update, MVDs!=0&&No_update, IntraCAE, MVDs=0&&InterCAE, MVDs!=0&&lnterCAE.

[0086] If all pixel values in the BAB is “0” indicating a background, BAB_type=All_—0. If all pixel values in the BAB is “255” indicating an object, BAB_type=All_—255. “MVDs=0&&No_update” indicates that there is no motion information to be transmitted and prediction error information is not transmitted. “MVDs!=0&&No_update” indicates that there is motion information to be transmitted and the prediction error information is not transmitted. “IntraCAE” indicates to perform CAE with respect to the BAB without use of reference shape information of a previous frame. “MVDs=0&&InterCAE” is the case that there is no motion information to be transmitted and the CAE should be performed using the reference shape information. “MVDs!=0&&InterCAE” is the case that there is motion information to be transmitted and the CAE should be performed using the reference shape information.

[0087] It is determined that the BAB falls under a BAB_type, such as All_—0, All_—255, or MVDs=0&&No_update, which does not need further coding steps (S113). For the three cases which does not need the coding, BAB_type is encoded and the pertinent BAB coding procedure is terminated.

[0088] When the BAB falls under a BAB_type other than the above three types, it is determined which of field type shape coding and frame type shape coding is more efficient in terms of coding efficiency (S115). In other words, a shape coding type mode (SCM) is determined. In this invention, the SCM which is applied to a coder using the CAE is represented with CAE_type.

[0089] It is then determined whether a frame CAE mode is selected as CAE_type (S116). When the frame CAE mode is selected, the CAE is performed with respect to each frame BAB (S118). When a field CAE mode is selected, the CAE is performed in the units of field type (S117).

[0090] As illustrated, the coding is performed according to the selected mode and, in addition to the coded data, the flag of one bit, CAE_type, for expressing the field CAE mode or the frame CAE mode is transmitted to the decoder. Alternatively, without using the formula, the CAE is performed in units of a field type and a frame type and then CAE_type can be determined in favor of less number of bits generated.

[0091] FIG. 12 is a block diagram of shape information decoding apparatus according to the present invention.

[0092] A demultiplexer (DEMUX) 91 demultiplexes coding data received via a transmission line. An overhead decoding unit 92 decodes overhead information, such as BAB_type, conversion ratio (CR), and scan type (ST), in demultiplexed data received from the demultiplexer 91. A coding type mode decoding unit 93 decodes coding type mode data received from the demultiplexer 91. A switching unit 94 switches coded shape information received from the demultiplexer 91 according to the coding type mode received from the coding type mode decoding unit 93. A frame type decoding unit 95 decodes the shape information received via the switching unit 94 and motion-compensated, previous shape information in units of a frame type using the overhead information (BAB_type, CR, ST). A field type decoding unit 96 decodes the shape information received via the switching unit 94 and motion-compensated, previous shape information in units of a field type using the overhead information (BAB_type, CR, ST). A previous shape memory unit 97 stores previous shape information received from the shape reconstructing unit 99. A motion compensation unit 98 receives motion information from the overhead decoding unit 92 and the previous shape information from the previous shape memory unit 97 and performs motion compensation with respect to the previous shape information before transmission to the frame type decoding unit 95 and the field type decoding unit 96. A shape reconstructing unit 99 receives the overhead information from the overhead decoding unit 92 and the reconstructed BAB received from the frame type decoding unit 95 and the field type decoding unit 96, and produces reconstructed shape information of a whole picture.

[0093] The overhead decoding unit 92 decodes the overheads which are contained in a bitstream inputted to the demultiplexer 91 via the transmission line and necessary for the shape information decoding and controls the decoding process with decoded overhead information. If a coding apparatus uses the CAE, the overhead information includes BAB_type, CR, ST, and motion information. When BAB_type is All_—0, the pixels of the reconstructed BAB are set to 0 at a decoder. On contrary, when BAB_type is All_—255, the pixels of the reconstructed BAB are set to 1 at a decoder. A shape coding type mode (SCM) is decoded at the coding type mode decoding unit 93 and controls the switching unit 94. If the SCM is the frame mode, the bitstream outputted from the demultiplexer is inputted to and decoded at the frame type decoding unit 95. If the SCM is the field mode, the bitstream outputted from the demultiplexer is inputted to and decoded at the field type decoding unit 96. The motion compensation unit 98 produces a motion compensation BAB from the reference shape information stored in the previous shape memory unit 97 using decoded motion information from the overhead decoding unit 92. The motion compensated BAB is inputted to the frame type decoding unit 95 and the field type decoding unit 96. The frame type decoding unit 95 and the field type decoding unit 96 each decodes the bitstream received via the swithching unit 94 and produces reconstruction BAB, using the overhead from the overhead decoding unit 92 and the motion compensated BAB received from the motion compensation unit 98. The shape reconstructing unit 99 reconstructs the shape information of a whole picture using the reconstructing BAB and the overhead of the overhead decoding unit 92. The reconstructed shape information is stored in the previous shape memory unit 97 and used when the next shape information is decoded.

[0094] As illustrated above, the shape information decoding apparatus has the coding type mode decoding unit 93, which decodes data for expressing the SCM signal, and performs the decoding at the frame type decoding unit 95 or the field type decoding unit 96 according to the decoded SCM signal.

[0095] FIG. 13 is a detailed block diagram of a frame type decoding unit and a field type decoding unit according to the present invention. Demultiplexed coded shape information outputted from the demultiplexer 91 is inputted to the frame type decoding unit 95 via the switching unit 94 when the coding type mode decoding unit 93 produces a frame mode SCM signal The frame type decoding unit 95 comprises a bordering unit 951 and a scan type and CAE decoding unit 952. The bordering unit 951, as previously described, borders pixels at the border of the BAB to construct a context when a pixel to be decoded is at the border of the BAB. The scan type and context-based arithmetic decoding unit 952 performs context-based arithmetic decoding while scanning the frame BAB using a scan type received from the overhead decoding unit 92.

[0096] The field type decoding unit 96 comprises a bordering unit 961, a scan type and context-based arithmetic decoding unit 962, and a BAB converting unit 963. The bordering unit 961 has the same function as the bordering unit 951 other than it performs bordering with respect to the BAB in units of a field type. The scan type and context-based arithmetic decoding unit 962 performs the context-based arithmetic decoding while scanning the field BAB using the scan type received from the overhead decoding unit 92 The BAB converting unit 963 converts the top field BAB and the bottom field BAB received from the scan type and context-based arithmetic decoding unit 962 into a frame BAB.

[0097] Input information of the frame type decoding unit 95 and the field type decoding unit 96 includes the coded bitstream, a motion compensation BAB, and the overhead information received from the overhead decoding unit 92. The frame type decoding unit 95 is first described in detail. The bordering unit 951 receives the motion compensated BAB and the bitstream and performs the bordering of adopting a neighboring pixel's value to construct the CAE template. The motion compensated BAB is transposed according to the scan type information among the input overheads (additional information). The context-based arithmetic decoding is performed on the bitstream received from the demultiplexer 91. By decoding the BAB_type information of the overhead, IntraCAE or InterCAE is obtained. The context-based arithmetic decoding is performed with one of these two methods. During the context-based arithmetic decoding& a context is obtained by using the neighboring pixels and arithmetic decoding is performed with reference to the probability in the obtained context.

[0098] The field type decoding unit 96 performs the same functions as the frame type decoding unit 97 other than that it performs the functions with respect to a field and that it reconstructs the frame BAB with the context-based arithmetic decoded field BAB at the BAB converting unit 963.

[0099] FIG. 14 is a block diagram of a coding apparatus for interlaced shape information according to another embodiment of the present invention.

[0100] Compared with the coding apparatus shown in FIG. 5, a motion estimation unit 54′ has different functions. Other components perform the same functions as those depicted in FIG. 5, so the same reference numbers are given and descriptions about them are omitted here.

[0101] The motion estimation unit 54′ estimates motion using the previous shape information received from the previous shape memory unit 59 and the BAB received from the BAB division unit 51. The motion estimation unit 54′ separately estimates the motion by each field in the BAB when the SCM signal from the coding type mode determining unit 52 is a field mode. Alternatively, when the SCM signal is a frame mode, the motion estimation unit 54′ performs the motion estimation with respect to a frame of the BAB. A result of the motion estimation is sent to the motion compensation unit 56. The motion compensation unit 55 compensates the input BAB using the previous shape information received from the previous shape memory unit 59 according to the motion information received from the motion estimation unit 54′. The motion compensation unit 55 sends motion compensated BAB to both the frame type coding unit 56 and field type coding unit 57. When the frame mode is selected, the BAB is inputted to the frame type coding unit 56 and frame type coding is performed. When the field mode is selected, the BAB is inputted to the field type coding unit 57 and field type coding is performed.

[0102] As disclosed in the description of FIG. 5, motion estimation is not limited to a particular method, but the apparatus depicted in FIG. 14 estimates one piece of frame motion information per BAB when the SCM is the frame type mode and it estimates two pieces of field motion information per BAB when the SCM is the field type mode. The most important feature of the apparatus depicted in FIG. 14 is to control the motion information with the SCM.

[0103] This method has advantages when the motion information of the shape information is very closely related to the SCM. When the correlation between two fields is low, namely, there is much motion of an object between two fields, field-based motion information rather than frame-based motion information usually has an advantage. It would be most advantageous in efficient coding to select a better one of two kinds of motion information as shown in FIG. 5. Alternatively, when controlling the motion information with the SCM as shown in FIG. 14, complexity can be reduced and it is not necessary to transmit a flag for indicating that the motion information is a field type or a frame type.

[0104] When performing field-based motion estimation, restriction can be defined such that estimation and prediction with respect to an even (top) field should be performed against the even field of a reference picture and estimation and prediction for the odd (bottom) field should be performed against the odd field of a reference picture. In other words, the restriction means that the estimation and compensation of each field should use the same field of the reference shape information. In this case, transmission of the flag for indicating which field of the reference picture is used is not needed, thereby improving coding efficiency.

[0105] FIG. 15 is a flow chart of a coding method considering a CR. Compared with FIG. 11, a new step, S115, is added. In this step, a CR is determined and coded for transmission. This step is performed when the BAB_type falls under a case other than All_—0, All_—255, and MVDs==0&& No_update. CR is information indicating degree of compression of the BAB. For example, if CR is ¼, the BAB is compressed to ¼ in both vertical and horizontal direction. Consequently, a size of the BAB is reduced to ⅙. When coding and transmitting the compressed BAB instead of an original size of BAB, the amount of bits generated is reduced although resulting in the lossy coding.

[0106] FIG. 16 is a flow chart showing how a CR is determined.

[0107] A BAB is down-sampled into ⅙ by setting a CR to ¼, in turn, the BAB of a size ⅙ is up-sampled to an original size and this up-sampled original size of BAB is compared with an input BAB to calculate the number of error pixels between the two BABs (S161). The calculated number of error pixels is compared with a predetermined threshold Error_thr (S162). When the number of error pixels is less than or equal to the threshold Error_thr, the CR is determined to be set to ¼ and this data is transmitted to a decoder (S163), before terminating the procedure. When the number of error pixels exceeds the threshold Error_thr, the CR is set to ½, thus down-sampling the BAB to a size ¼, and, in turn, the BAB of the size ¼ is up-sampled to an original size of BAB, so that the BAB is compared with an input BAB to calculate the number of error pixels between the two BABs (S164). The calculated number of error pixels(Error) is compared with the predetermined threshold Error_thr (S165). When the number of error pixels is less than or equal to the threshold Error_thr, the CR is determined to be set to ½ and this data is transmitted to the decoder (S166), before terminating the procedure. Otherwise, the CR is determined to be set to 1 and this data is transmitted to the decoder (S167). There are two methods in structuring an object BAB. As shown in FIG. 6a, while the BAB is maintaining a form of a frame, it is downsampled into 8×8 blocks or 4×4 blocks for the coding. Alternatively, as shown in FIG. 6b, two fields are separately downsampled and rearranged making a new type of BAB. Hereinafter, this BAB rearranged by each field is named a permuted BAB.

[0108] FIG. 17 is a flow chart showing how to determine each CR and perform coding with respect to a top and a bottom fields in a binary alpha block.

[0109] Compared with the method shown in FIG. 11, this method further includes the steps S175 and S176 of independently determining CRs with respect to a top and a bottom fields in a BAB.

[0110] The step S115 in FIG. 15 is divided into the two steps S175 and S176 in FIG. 17. According to the flow chart depicted in FIG. 15, the CR is determined with respect to a frame of the BAB and one CR per BAB is coded for transmission. On the other hand, the BAB is divided into two fields and CRs of each field are independently determined in FIG. 17. The step S175 is for the top field and the step S176 is for the bottom field. The procedure disclosed in FIG. 16 can be employed as a method of obtaining the CR. In this case, two CRs for each field in the BAB should be coded, so an overhead for transmitting the CRs can result in reduction of coding efficiency.

[0111] To prevent this problem the larger CR between two CRs of each field is selected and a selected single CR per BAB is coded and transmitted. For example, when the CR of the top field may be ½ and that of the bottom field may be ¼, the CR of the BAB is determined to be set to a larger value, ½, and then the CR value ½ for the BAB is coded and transmitted. This method is advantageous in that the CR can be determined by each field and an overhead does not occur.

[0112] The methods illustrated in FIGS. 15 and 17 are advantageous in facilitating the loss coding by applying the CR, but they have also a drawback that characteristics of the BAB do not considered in determining and coding the CR. In other words, while the method depicted in FIG. 15 is efficient with respect to the frame type BAB but inefficient with respect to the field type BAB, the method depicted in FIG. 17 is inefficient with respect to the frame type BAB but efficient with respect to the field type BAB. To overcome this problem, a method depicted in FIG. 18 is offered.

[0113] FIG. 18 is a flow chart showing a method of determining a CR after deciding CAE_type. After deciding CAE_type at the step S116, when CAE_type is the frame CAE mode, the CR of the BAB is determined and this data is transmitted to the decoder according to the method shown in FIG. 16 at the step S189. In this case, a single CR is determined. When CAE type is the field CAE mode, each CR is separately determined with respect to the top field BAB and the bottom field BAB and the CR data is transmitted to the decoder through the method shown in FIG. 16 at the respective steps S187 and S188.

[0114] Compared with the methods shown in FIGS. 15 and 17, the method illustrated in FIG. 18 first decides CAE_type and then determines the CR in accordance with CAE_type. In other words, when CAE_type is the frame CAE mode, a frame type CR is determined (S189). When CAE_type is the field CAE mode, a field type CR is determined (S187 and S188). Similarly to S175 and S176 in FIG. 17, a single CR per BAB can be selected and coded before transmission at S187 and S188 in FIG. 18.

[0115] FIG. 19 is a block diagram of a coding apparatus having a field CR determining unit according to the present invention.

[0116] Compared with the apparatus depicted in FIG. 5, the apparatus depicted in FIG. 19 further includes a frame CR determining unit 191 and a field CR determining unit 192. The frame CR determining unit 191 corresponds to an apparatus for performing the step S189 in FIG. 18. The frame CR determining unit 191 determines a CR and converts the input BAB and the motion compensated BAB in accordance with the determined CR. A result BABs of the conversion are inputted to the frame type coding unit 56. The field CR determining unit 192 is for performing the steps S187 and S188 in FIG. 18. The field CR determining unit 192 determines CRs and converts the input BAB and the motion compensated BAB in accordance with the determined CRs. A result BABs of the conversion are inputted to the field type coding unit 57.

[0117] Compared with the apparatus illustrated in FIG. 5, FIGS. 15, 17, and 19 additionally using the CR have been described. As described above, use of the CR enables the loss coding and the coding efficiency can be improved by properly selecting the CR. Besides, there are further methods for additionally improving the coding efficiency.

[0118] Primarily, the CR can be used when deciding All_—0 or All_—255 at a BAB_type determining unit. This method can be applied to the lossy coding. While performing processes shown in the flow chart of FIG. 11, the input BAB which was down-sampled and then up-sampled is compared with a BAB in which all pixels have a value, 0. When the number of error pixels between the two BAB is less than or equal to a predetermined threshold, it is decided that BAB_type is All_—0. Similarly, the input BAB which was down-sampled and then up-sampled is compared with a BAB in which all pixels have a value, 1 (or 255). When the number of error pixels between the two BAB is less than or equal to a predetermined threshold, it is decided that BAB_type is All_—255. Through this method, the number of BABs where BAB_type is All_—0 or All_—255 increases, thereby reducing complexity and the amount of transmission data.

[0119] Another method is implemented by expanding and applying the first method described above to the field type coding. After performing the operations of the first method with respect to the frame type BAB as described before, the same operations are repeated with respect to the field type BAB. Specifically, the operations are applied to each independent field and, when both fields are detected to be All_—0, BAB_type is determined to be All_—0. When both fields are detected to be All_—255, BAB_TYPE is determined to be All_—255. This method is advantageous in processing interlaced shape information. Because, for the interlaced shape information, BAB_type can be All_—0 in a field-based process although BAB_type is not All_—0 in a frame-based process.

[0120] Further another method is to increase the number of No_Update BABs, such as MVDs==0&&No_Update and MVDs!=0&&No_Update, when deciding BAB_type. This method is also applied to the field type BAB. Specifically, No_Update is checked with respect to each field in a BAB. When MVDs==0&&No_Update is concluded with respect to both fields, it is decided that BAB_type is MVDs==0&&No_Update. Alternatively, when MVDs!==0&&No_Update is concluded with respect to both fields, it is decided that BAB_type is MvDs!==0&&No_Update. Since BAB_type can be No_Update in a field-based process although BAB_type is not No_Update in a frame-based process, this method is profitable in the coding.

[0121] Another method is to use the same scan type (ST) for both fields and to transmit a single ST per BAB. According to this method, overhead transmission can be reduced, thereby improving the coding efficiency.

[0122] Still another method is related to a flush bit. A coder using both arithmetic coding and non-arithmetic coding together should transmit a flush bit after finishing the arithmetic coding and before starting the non-arithmetic coding. When applying the field type coding to this coder in the same way as the frame type coding, flush bits should be transmitted twice in the field type coding, compared with in the frame type coding. This reduces the coding efficiency in the field type coding. To overcome this drawback, before the non-arithmetic coding with respect to the top and bottom fields, the arithmetic coding with respect to both fields are consecutively performed. This method allows a flush bit to be transmitted just once in the field type coding mode as in the frame type coding mode.

[0123] As illustrated, the present invention selects one of the frame and field type shape coding modes according to the amounts of motion of the frame based shape information and the field-based shape information to adaptively code the interlaced shape information, thereby improving efficiency in coding the interlaced shape information.

[0124] It will be apparent to those skilled in the art that various modifications and variations can be made in an apparatus and method of adaptively coding/decoding interlaced shape information of the present invention without deviating from the spirit or scope of the invention. Thus, it is intended that the present invention cover the modifications and variations of this invention provided they come within the scope of the appended claims and their equivalents.