System and associated method for transcoding discrete cosine transform coded signals

[0001] The invention relates to a method for translating or “transcoding” between formats of compressed digital signals that have been encoded using a discrete cosine transform (DCT) operation. More particularly, the invention relates to a method of transcoding between a DV compressed signal and an MPEG compressed signal without performing an inverse discrete cosine transform (IDCT) operation.

[0002] The Moving Picture Experts Group (MPEG) video compression standard is one of the most popular formats in digital video production for compressing or encoding a video signal. The MPEG-2 standard was initially proposed and developed as an open standard by the international standard organization (ISO), its main strength is its flexibility and compression efficiency. The MPEG-2 standard is well suited for data transmission and storage. This standard was designed to allow video signals in many different formats to be compressed. It was also designed for broadcasting applications with a point to multi-point model in mind. As such, the MPEG-2 encoding-decoding process is highly asymmetric, the MPEG-2 encoder, for example, being far more complex than its corresponding decoder.

[0003] The MPEG-2 video compression method is also lossy, that is to say, significant information is lost when the signal is compressed. The standard is designed, however, to take advantage of the human visual system in order to hide these losses. Nonetheless, significant degradation of the video image occurs if a compressed signal is expanded, re-compressed and expanded again.

[0004] Consequently, MPEG based compression is not well suited for production and/or editing applications. In a production/editing environment there would be as many encoding steps as decoding steps, and the processing involved for simple tasks (e.g. frame-level editing) would be unwieldy as a complex encoding process would be required after each edit.

[0005] Because of these features of MPEG, a second standard Digital Video(DV) was developed as a proposed SMPTE standard. This standard includes Digital Video at 50 Mb/s (DV50) and Digital Video at 25 Mb/s (DV25). The DV standard is typically utilized to compress data for production/editing applications. The compression methods defined by the DV standard were designed with a studio production scenario in mind, so encoder and decoder are of roughly similar complexity. The DV standard uses fixed size frames and does not place as much emphasis on compression efficiency as does MPEG-2.

[0006] More detailed features of the DV standard are briefly reviewed hereafter for the purpose of facilitating the teachings of the present invention.

[0007] Digital video DV50 has a constant bit-rate of 50 Mb/s, and a compression ratio of about 3.3:1. The chrominance format is 4:2:2, and the compression method is based on the DCT operation. All the frames of a DV50 signal are compressed independently from each other (i.e., intra-coded) into a fixed size payload. Both NTSC and PAL formats are supported by the DV50 standard.

[0008] FIGS. 1 and 1A illustrate an exemplary DV coding process, generally designated 1. Note that the DV standard only uses intra-frame coding, taking advantage of spatial redundancy in the image by transforming blocks of image pixels into the spatial frequency domain through the use of the DCT. The DV standard does not use any temporal prediction. In this regard, it is similar to the MPEG-2 standard constrained to encode only Intra-frame or I pictures.

[0009] The DV encoding process at the block level, however, encodes parts of frames that exhibit relatively large amounts of intra-frame motion differently than parts that do not exhibit this type of motion. Portions of frames that have significant motion between their fields are encoded as two 4×8 blocks, one from each field (248 blocks) while portions of frames that do not significant exhibit inter-field motion are encoded as 8×8 blocks (88 blocks). The relationship between the field encoded 248 blocks and the frame encoded 88 blocks is described below with reference to FIG. 2. In order to detect blocks that need to be encoded as 248 blocks, the DV coding process includes a intra-frame motion detector 2. This detector controls the DCT stage 4, weighting stage 6, and scan stage 12.

[0010] In operation, the intra-frame motion detector 2 monitors the fields of interlaced frames to detect rapid motion between the two fields that constitute the frame. A block of image pixels from the frame is applied to a discrete cosine transform (DCT) process 4 which converts the pixels to DCT coefficients. The weighting block 6 applies weighting factors to the DCT coefficients as a part of the quantization process, as described below. The weighted coefficients are applied in parallel to a quantization process 8 and to a quantization table selection block 10. Based on the values of the coefficients, the quantization table selection block 10 selects a quantization table to be used by the quantization process 8. The identity of this table is encoded into the bit-stream. Using this table, the process 8 quantizes the weighted coefficients provided by the weighting process 6 and applies the result to the scan stage 12. The scan stage 12 scans the coefficients to determine their run-amplitude combinations. Finally, the blocks of run-length coded coefficients are applied to a variable-length coder VLC) 14 in which they are encoded according to a predetermined variable length, or entropy, code to produce the output bit-stream

[0011] The decoding process consists of a VLC decoder 16 that reverses the process performed by the VLC coder 14, a run-length decoder 20 that reverses the run-length scan performed by the scanner 12, and an inverse quantizer 22 that reverses the quantization operation performed by the quantizer 8. In order to dequantize the coefficients, the decoder identifies the quantization table that was used by the quantizer 8 and selects this table in the quantization table selection process 18. After the DV data has been dequantized, the weighting applied by the process 6 is reversed in the inverse weighting process 24 to reproduce the DCT coefficients generated by process 4 and these coefficients are applied to an inverse discrete cosine transform (IDCT) process 26. The decoder shown in FIG. 1B detects whether a block is encoded as an 88 block or as a 248 block and changes the operation of the inverse scan process 20, inverse weighting process 24 and IDCT process 26 accordingly. The quantization and inverse quantization operations are described in more detail below with reference to Tables 1, 2 and 3.

[0012] As set forth above, although the DV standard does not employ any inter-frame motion compensation scheme per se, it does have a facility for handling fast motion. If there is fast motion in the content, there may be perceptible differences between the two fields of an interlaced frame and thus, “intra-frame motion.” In such a case, there may be only slight correlation between the two fields in the frame, so a frame-based compression method, such as an 88 DCT, may produce unsatisfactory results. When inter-field or intra-frame motion is detected by intra-frame detector 2, a different DCT mode called “248-DCT” is used to improve the coding efficiency. In this way, 248 DCT mode is used adaptively to suppress any degradation of picture quality in video images having fast motion content.

[0013] The quantization operation according to the DV standard is a multi-step C2 operation. After the coefficients have been processed through the discrete cosine transform, the DCT coefficients are scaled in weighting stage 6 (shown in FIG. 1). Weighting stage 6 utilizes a weighting matrix, that is chosen based on the DCT mode (88 DCT or 248 DCT).

[0014] Specifically, instead of giving the quantization step size explicitly for each coefficient, each DCT block is divided into 4 areas according to a predetermined pattern (shown in FIG. 3). This pattern is different for the 88-DCT and the 248-DCT. The quantization step size is the same in each defined area. Table 1 shows the quantization step size for each area, for different classes and quantization table numbers. For example, for a coefficient in area “2”, if the class number is “1” and quantization table number is “10”, the quantization step size is determined as follows. In Table 1, quantization number “10” is located in the column corresponding to class “1” and the row in which “10” resides is denoted as “row X”. Next the column corresponding to area “2” is identified and denoted as “column Y”. The quantization step size (in this case “2”) to be used for the coefficient is found at the junction of row X and column Y.

[0015]

	TABLE 1
	Class Number	Area Number
	0	1	2	3	0	1	2	3
Quantization	15				1	1	1	1
Number	14				1	1	1	1
	13				1	1	1	1
	12	15			1	1	1	1
	11	14			1	1	1	1
	10	13		15	1	1	1	1
	9	12	15	14	1	1	1	1
	8	11	14	13	1	1	1	2
	7	10	13	12	1	1	2	2
	6	9	12	11	1	1	2	2
	5	8	11	10	1	2	2	4
	4	7	10	9	1	2	2	4
	3	6	9	8	2	2	4	4
	2	5	8	7	2	2	4	4
	1	4	7	6	2	4	4	8
	0	3	6	5	2	4	4	8
		2	5	4	4	4	8	8
		1	4	3	4	4	8	8
		0	3	2	4	8	8	16
			2	1	4	8	8	16
			1	0	8	8	16	16
			0		8	8	16	16

[0016] A minor variation is applied to class 3 in the process described above. If a Class Number of 3 is chosen for a DCT block, then an extra right shifting by 1 bit-position is performed for each coefficient after the weighting step. The reason for this shift is in the VLC coding stage following the quantization stage, no AC coefficient greater than 255 or less than −255 is allowed and the quantization process for class 3 must ensure that the quantized AC coefficients will fall into that scope. For those DCT blocks that can not meet the VLC coding requirement with other class numbers, class 3 is the only choice.

[0017] Within a DCT block, the coefficient scan order is the same as in MPEG-2 for 88 DCT blocks but follows a different scan order for 248 DCT blocks. How the class number and quantization number chosen are matters of encoder design choice. But the DV standard gives some guidelines for class selection, which are shown in Tables 2 and 3.

[0018]

TABLE 2
Class Number Selection and Quantization Noises
		Maximum Absolute Value of AC
Class Number	Quantization Noise	Coefficient
0	Visible	Less than or equal to 255
1	Lower than class 0
2	Lower than class 1
3	Lower than class 2
	—	Greater than 255

[0019]

TABLE 3
An Example of the Classification for Reference
	Maximum Absolute Value of AC Coefficient
	0 to 11	12 to 23	24 to 35	>35
	Y	0	1	2	3
	Cr	1	2	3	3
	Cb	2	3	3	3

[0020] A macroblock in DV consists of 4 DCT blocks, including 2 luminance (Y) blocks, and two chrominance blocks (Cr and Cb), as shown in FIG. 4. Macroblocks are further organized into superblocks, each of which consists of 27 macroblocks as shown in FIG. 4A. FIG. 4A also shows the way in which the superblocks are formatted into image frames. The image frame shown in FIG. 4A is encoded by pseudo-randomly selecting five macroblocks, from five superblocks and grouping the selected macroblocks into a video segment. This pseudo-random selection is also known as shuffling. The blocks are shuffled to minimize distortion in the final image caused by burst errors in the data stream.

[0021] Each video segment is then compressed into 77×5 bytes, which is exactly the payload of five DIF (Digital Interface) packets. If a video segment is denoted as Seg(i,k), then the order of compressed segments in a frame is: Seg(0,0), Seg(0,1) . . . Seg(0,26), Seg(1,0) . . . Seg(n−1,26).

[0022] The process of encoding an I-frame according to the MPEG-2 standard is similar in some ways and different in some ways from the process used according to the DV standard. In MPEG-2, 8 by 8 blocks of image pixels are processed using a discrete cosine transform (DCT) operation to produce 8 by 8 blocks of DCT coefficients. The coefficients are quantized, zigzag scanned, run-length coded and variable length coded to produce the output bit-stream. The blocks of DCT coefficients are arranged in macroblocks, each macroblock including eight 8 by 8 blocks. The macroblocks, in turn, are arranged in slices, where multiple slices constitute a picture. There are two variables in the quantization of a block of DCT coefficients, the quantization matrix and the quantizer scale value. The quantization matrix is transmitted with the bit-stream and may change for each picture. The quantization matrix defines the relative quantization resolution among the DC and lower spatial-frequency coefficients versus the higher spatial-frequency components of the DCT coefficients.

[0023] The quantizer scale value may be specified both in the slice header and in the macroblock header and, so, may change on a macroblock by macroblock basis. The quantizer scale value is a multiplier that multiplies the values in the quantization matrix. A larger value for the quantizer scale translates to a coarser quantization. The MPEG-2 encoder adjusts the quantizer scale value dynamically to adjust the data rate of the bit-stream. If this instantaneous data rate increases above a first threshold value, the encoder increases the quantizer scale value to more coarsely quantize the DCT coefficients and, so, reduce the data rate. It the data rate decreases below a second threshold value, the quantizer decreases the quantizer scale value to more finely quantize the DCT coefficients.

[0024] Because both MPEG-2 and DV provide characteristic advantages, it is conceivable that both standards will co-exist in the long term and complement each other in the studio environment. As can be appreciated from the above description, the DV and MPEG-2 standards were independently developed with no consideration as to their interoperability. Presently, there exist proprietary hardware systems for transcoding between the two formats. Yet, these systems are expensive and complex as they fully decode signals from one standard to the pixel level and then re-encode the data in the other standard.

[0025] Accordingly, there is a need for a simplified transcoding method for efficiently remedying this interoperability problem in real time.

[0026] The present invention is embodied in a method of transcoding between first and second standards that employ a discrete cosine transform (DCT) operation to compress video data. The method decodes a first signal that has been compressed according to a first standard to the level of the DCT coefficients and then re-encodes the coefficients to produce a compressed signal according to the second standard.

[0027] According to one aspect of the invention, the first standard encodes video frames differently when there is significant motion between the fields that constitute a frame than when there is no such motion. According to one embodiment of the invention, encoded frames of the first signal which have intra-frame motion are converted into a coding format used for frames that do not exhibit intra-frame motion before being converted to the second standard.

[0028] According to another aspect of the invention, the first standard is DV and frames in the DV encoded signal that have been encoded as 248 blocks are translated to 88 blocks after the DV signal is partially decoded.

[0029] According to another aspect of the invention, the method decodes the first signal into a stream of DCT blocks in which the coefficients are quantized according to the first standard. Quantized DCT coefficients in the first standard are converted to Quantized DCT coefficients in the second standard without being dequantized and then formatted into a compressed signal according to the second standard.

[0030] According to yet another aspect of the invention, the first standard is the DV standard and the second standard is the MPEG-2 standard. To partially decode the DV signal, the variable length coding (VLC) of the coefficients is reversed to obtain a sequence of blocks of quantized DCT coefficients. The quantized DCT coefficients in the DV standard are converted into quantized MPEG-2 macroblocks of coefficients without affecting the run-length coding of the coefficients. The quantized MPEG coefficients are then formatted into an MPEG-2 sequence of video frames and variable-length coded according to the MPEG-2 standard.

[0031] According to another aspect of the invention, the first standard is the DV standard and the second standard is the MPEG-2 standard. The DV standard encodes the image data into fixed-size blocks, macroblocks and segments. The macroblocks and segments include respective overflow data representing coefficients in individual blocks that do not fit within the fixed-size blocks. To reduce the data rate of the MPEG signal, the overflow data first in the segments and then in the macroblocks is selectively ignored. That is to say, the coefficient values corresponding to this overflow data may be set to zero.

[0032] According to yet another aspect of the invention, the first standard is the MPEG-2 standard and the second standard is the DV standard.

[0033] According to another aspect of the invention, MPEG-2 blocks are converted to DV frame-mode blocks and the DV frame mode blocks are analyzed to determine if they are to be converted to DV field-mode blocks. Responsive to the analysis, selected ones of the DV frame mode blocks are converted to DV field mode blocks.

[0034] According to yet another aspect of the invention, the analysis to determine whether a frame mode DV block is to be converted to a field mode DV block compares one coefficient of the frame mode DV block to a predetermined threshold value.

[0048] Certain terminology is used herein for convenience only and is not to be taken as a limitation on the present invention. The terms “intra-coded” and “intra-frame coded” are defined as referring to a coding scheme that does not employ temporal prediction in encoding a signal (i.e., all of the video frames are compressed independently of each other). In the drawings, the same reference numerals are used for designating the same elements throughout the several Figures.

[0049] The present invention concerns a transcoding system that translates between coding formats based primarily on the same linear orthogonal transform known as the Discrete Cosine Transform (DCT). The transcoder in accordance with C the present invention utilizes this commonality by recovering and re-quantizing these common DCT coefficients for transcoding into a desired format. In this way, it is not necessary to completely decode the signal to recover the original pixel data.)

[0050] Exemplary video formats supported by the transcoder of the present invention are Digital Video (DV) and MPEG-2 4:2:2 Profiled@ Main Level (4:2:2@ML) with I-frames only. Details of the DV may be found in a proposed SMPTE standard entitled “Data Structure for DV Based Audio, Data and Compressed Video, 25 Mb/s and 50 Mb/s,” 4^th draft. Details on the MPEG-2 standards can be found in an ISO standard entitled “ISO/IEC 13818-2 Information Technology-Generic Coding of Moving Pictures and Associated Audio Information:Video.”

[0051] As described above, intra-coded DV is a digital video recording standard mainly designed for field news acquisition and postproduction for television broadcast. MPEG-2 is a very flexible and “generic” video format that is designed for distributing compressed video data to consumers. To ensure that the implementation is efficient and that the editing features are supported, the exemplary embodiments use only I-frame based coding in the MPEG format.

[0052] Three different chrominance formats are supported by MPEG-2, the 4:2:0, 4:2:2 and 4:4:4 formats. The most commonly used MPEG-2 format is called Main Profile@Main Level, which is targeted for video in the CCIR-601 Resolution, in the 4:2:0 format. To meet the needs of the professional studio and post-production environment with interoperability, however, a new profile—4:2:2 Profile@Main Level—has been defined. Unlike other profiles defined in MPEG, this format is a non-scalable profile and does not have a hierarchical relationship with other profiles. The 4:2:2 Profile@Main level professional extension is used in the exemplary embodiment of the invention to match the chrominance format and bit-rate of signals encoded according to the DV standard.

[0053] A macroblock in MPEG-2 consists of 4 Y-blocks and 2 Cb and 2 Cr blocks as illustrated in FIG. 5. The MPEG-2 standard was developed primarily for dealing with interlaced video. The pixels in pictures of interlaced video are sampled at alternate vertical positions in the image plane. The purpose of interlaced video is to trade-off vertical resolution for increased temporal resolution under a given total data rate constraint. As a result, both spatial and temporal correlation between the pixels in adjacent lines of interlaced frames is reduced, which causes a decrease in coding efficiency.

[0054] Without special treatment for interlaced video, two adjacent fields can be combined into one frame picture and coded as a progressive frame. Alternatively, one each of the two field pictures may be encoded as if it were a progressive frame. Special coding modes are designed in MPEG-2 to improve the coding efficiency for interlaced video. These include Field Prediction, Field DCT and Alternate Scan (a modification of the zigzag scan order). The transcoder of the present invention does not take advantage of these options. That is, the exemplary transcoder only implements frame-mode operations in MPEG-2 when transcoding DV video to MPEG-2. Conversely, when transcoding from MPEG-2 to DV, the exemplary transcoder processes only frame-mode encoded MPEG-2 images. Thus, as described below, the partial DV decoder used in the exemplary embodiment of the invention translates any 248 DCT blocks into corresponding 88 DCT blocks. The partial DV encoder described below examines each 88 DCT block provided by the partial MPEG-2 decoder and translates appropriate blocks to 248 DCT blocks for the DV signal.

[0055] As described above, quantization process in MPEG-2 differs considerably from the DV standard. Under the MPEG-2 standard, the quantization steps for all DCT coefficients constitute an 88 matrix denoted as quantization step matrix. It is computed as follows:
QS=QW×Q_—Scale/16
where QS=Quantization Step Matrix (8×8); QW=Quanization Weighting Matrix(8×8) and Q_Scale=Quantization Scale (an integer). QW can change on a picture-by-picture basis while Q_Scale can change on a macroblock-by-macroblock basis. As set forth above, QW is changed to take advantage of the frame content while Q_Scale is changed dynamically to increase or reduce the data rate of the compressed video signal. In 4:2:2 or 4:4:4 video streams, the QWs for luminance and chrominance blocks are different so there are four QWs all together.

[0056] (1) In DV, for each DCT block, a fixed number of bytes are assigned to the DCT encoded data. One macroblock consists of 4 DCT blocks, two luminance component blocks and two chrominance component blocks (one Cr and one Cb). A fixed number of bytes are also assigned to each macroblock (slightly more than the sum of the bytes assigned to its individual four DCT blocks). Every five macroblocks selected according to the predefined shuffling algorithm constitute a video segment, and a fixed number of bytes are assigned to each segment. If some DCT blocks need more storage space than that assigned to them, there are two steps to distribute “overflow” data bits:

• • [0057] a) Concatenate the overflowed bits of the DCT blocks within the same macroblock and distribute the bits to the unused space of the other DCT blocks in the same macroblock.
  • [0058] b) If, after step (a), there are still overflow bits for some macroblocks in a segment, then concatenate those overflow bits and distribute them to unused space of the DCT blocks in the same segment.

[0059] Because a fixed number of bytes is assigned to each block, the DC coefficient and the lower-spatial frequency coefficients are always stored in the area allocated to the block. Only the highest spatial frequency components are concatenated into the overflow data. Consequently, if an image is decoded without recovering the overflow data, only information related to these coefficients is lost. This scheme minimizes apparent distortion because the human eye is less sensitive to errors in the high spatial frequency components than to errors in the DC component or in the lower spatial frequency components.

[0060] Because the overflow data stays within the segment, each segment is completely independent from other segments. From the description above it follows that during the encoding of a DCT block and a macroblock, the unused bits should be preserved for future use by other DCT blocks in the same macroblock or the same segment.

[0061] Note that MPEG-2 needs no such facility for ‘overflow’, because, it does not have fixed size frames. Each MPEG-2 DCT block can be as big or small as necessary. This is also a tradeoff between compression efficiency and the convenience of fixed size frames.

[0062] (2) As described above, DV adopts a DCT mode called 248 DCT to encode frames that exhibit intra-frame motion. MPEG-2 also supports a frame DCT and a field DCT mode. For simplicity, however, the transcoder of the present invention does not use the field DCT mode of MPEG-2. In the transcoder of the present invention, all MPEG-2 DCT blocks use the 88 DCT mode. Therefore, a conversion to the 88 DCT mode is performed in the exemplary embodiment of the invention when a 248-DCT block is encountered in the DV bit-stream. The process for converting from 248 DCT blocks to 88 DCT blocks is described below in section III.

[0063] (3) Even for the 88 DCT mode in DV, which has exactly the same coefficient order as the frame DCT in MPEG-2, it is not possible to directly use the quantized DCT coefficients in the DV, due to the difference in the quantization processes between the two standards. The MPEG-2 quantization-weighting matrix is chosen on a picture-by-picture basis and a quantization scale is chosen on a macroblock-by-macroblock basis. The DV quantization method, described above is more complex. Accordingly, it is impossible to simply choose an appropriate MPEG-2 weighting matrix that would allow the direct reuse of the quantized DV DCT coefficients by simply adjusting the weighting scale for each macroblock. Even if the weighting matrices in DV did have a simple scaling relationship with that in MPEG-2, it would still not be possible to reuse the DV coefficients directly in MPEG-2. The weighting scale in MPEG-2 is chosen at the level of one macroblock (8 DCT blocks) whereas the corresponding quantization decisions (class number and quantization table number) are made at the level of each DCT block in DV. Accordingly, in the exemplary embodiments of the invention, the DCT coefficients are requantized.

[0064] Complete dequantization and requantization is not necessary, however. If an MPEG-2 weighting matrix is specified to match the 88 area numbers, shown in FIG. 3 with quantization steps taken from the first row of the DV quantization table, (Table 1, the finest quantization step), then the DCT coefficients can be reused simply by doing some bit shifting on the original quantized DV DCT coefficients. This is possible because the quantization steps in DV are always powers of 2 times the finest quantization steps. In addition, because both MPEG-2 and DV use the same zigzag scan order for 88 DCT and because MPEG-2 and DV both use run-length coding, the run-lengths can be reused. In those cases when a quantization step size other than the finest step size for DV is used within the MPEG stream, some non-zero DCT coefficients of DV may become zero in MPEG. In this instance, some extra processing may be used to combine two or more run-lengths into one.

[0065] FIG. 6 illustrates a general block diagram of a software transcoder in accordance with the present invention. The transcoder includes a decoder module 30 and an encoder module 40. The de coder module 30 takes frames of DV data as input data and produces raw DCT coefficients as output data. The encoder module 40 requantizes the DV DCT coefficients to MPEG-2 DCT coefficients and encodes the coefficients as MPEG-2 data. While the transcoder is described herein as software based, hardware adaptation of the same is within the skill of those in the art. The transcoder employs the following simplified procedure:

• • [0066] Decode the (run-length, quantized-DCT) combinations in DV to obtain at least partially dequantized, run-length coded coefficients
  • [0067] Requantize the dequantized-DCT coefficients
  • [0068] Format the DCT coefficients into sequences of image frames
  • [0069] Encode the re-quantized-DCT coefficients with the MPEG-2 VLC table into an MPEG-2 bit-stream.

[0070] The run-length computation in MPEG-2 can be omitted, at least for 88 DV blocks, by reusing the run-length values from the DV blocks. As described below, these values can be reused if the MPEG quantization matrix is defined to correspond to the first row of the DV quantization table. With an MPEG-2 weighting matrix corresponding to the coarser quantization steps in DV and some minor modifications on the process described above, the bit-rate and quality of the output MPEG-2 stream can be adjusted. In the exemplary embodiment of the invention, partial dequantization and requantization is used only when converting 88 format blocks in DV to MPEG transcoding. As described below in section III, 248 DCT blocks are fully dequantized and requantized as a part of the conversion process.

I. Transcoding from DV to MPEG-2 4:2:2 (I-Frames only)

[0071] Based on the discussion above, two algorithmic simplifications are incorporated in the transcoder of the present invention. First, due to the essential equivalence between the DCTs in the two standards, the step of doing an inverse DCT (IDCT) can be avoided. In other words, the DCT coefficients may be reused without converting data to the pixel level. This eliminates the computation intensive steps of doing an IDCT and then a second DCT. As the DCT with rounding is one source of losses in the encoding process, the exemplary transcoding process is less lossy than a process that fully decodes the DV data into pixels and then encodes the pixels as MPEG-2 images. Second, as noted above, inverse quantization and re-quantization are not always necessary. For 88 DCT blocks, the quantized DCT coefficients may be used directly.

[0072] The method of transcoding from DV to MPEG-2 can be divided into two general phases shown in FIG. 7: (A) partial decoding and (B) partial encoding. Briefly, In step 71 of FIG. 7, the compressed DCT blocks are extracted from the DV segments. At step 72, the DCT coefficients are variable-length decoded and dequantized at step 73. At step 74, any 248 DCT blocks are converted into 88 DCT blocks and at step 75, the decoded and dequantized DV DCT blocks are regrouped into DCT blocks and macroblocks for the MPEG signal. At steps 76 and 77, the regrouped coefficients are quantized and at step 78, the quantized coefficients are variable-length coded to produce the output bit-stream. At step 79, the data rate of the MPEG bitstream is monitored to generate a data rate control signal. This signal is applied to steps 72, 76 and 77. In step 72, the signal controls how the DV overflow data is decoded from the DV blocks and, thus, how this data is used to generate MPEG blocks. In steps 76 and 77, the signal controls the MPEG quantization scale factor that is used for respective macroblocks of the MPEG signal.

[0073] The smallest unit where there is a logical correspondence between the DV and MPEG data is one frame. In DV each frame is encoded independently of others. Only the I-frame mode in the MPEG-2 format, is used to simplify implementation and to retain the editing capabilities of DV. The basic transcoding process, therefore, consists of decoding each DV frame partially, i.e. down to DCT coefficients, and then re-encoding the frames into MPEG-2 I-frames.

Partial decoding generally includes:

• [0074] (1) Collecting overflow data.
• [0075] (2) VLC decoding of the DV stream.
• [0076] (3) Converting 248 DCT blocks in DV into 88 DCT blocks.

[0077] In partial decoding, instead of reconstructing the pixels of the video frame, corresponding DCT coefficients are extracted in step 71 and VLC run lengths are extracted in step 72. In the encoding phase steps 73-78, the extracted DCT coefficients are re-encoded into the MPEG-2 format described in greater detail below with reference to FIG. 9.

[0078] In FIG. 8, the partial decoding process is shown more specifically as a hierarchical flow diagram. In a flow diagram of this type, some blocks are indented with respect to other blocks. The top-most block represents the entire operation. Sub-blocks that are indented from this block represent steps that are performed to complete the operation. Each of these sub-blocks, in turn may have further indented sub-blocks representing steps that are performed to complete the sub-block operation.

[0079] At step 801 of the hierarchical flow diagram shown in FIG. 9, a series of video frames, encoded as DIF packets, is received and separated into segments and decoded. Step 801 repeats for each video frame until the end of the video sequence is detected at step 802. The segments, in turn, are decoded at step 803. Each segment includes five macroblocks. Accordingly, at step 804, the individual macroblocks of the segments are decoded. At this step, any overflow bits that are distributed among the blocks of the macroblock and among the macroblocks of the segment are retrieved and stored separately. At step 805, macroblock decoding process determines the quantization step sizes that are used for each block. In step 806-813, the individual blocks of DCT coefficients are processed. At steps 806-810 the variable-length DCT coefficients are extracted from the blocks and the DCT mode of the block, 88 of 248, is identified. Also at steps 806-810, the overflow bits are processed to recover the corresponding coefficient values and these values are restored to their respective blocks. At steps 811, 812 and 813, the extracted coefficients are variable-length decoded and at least partially dequantized, as described above. If a block is in 248 mode then, at step 814, it is converted to an 88 block, as described below in section III. When a block is converted from a 248 mode block to an 88 mode block, the 248 block is fully dequantized. The result of the process shown in FIG. 8 is a stream of DCT coefficients that are at least partially dequantized. These coefficients, however, if they are derived from 88 DV blocks, are still run-length coded and in the zigzag scan order used for the 88 block format.

[0080] As described above, coefficients in 248 DV blocks are fully dequantized during the transcoding process. Coefficients in 88 format DV blocks may also be fully dequantized. In either of these operations the DV coefficients are fully is dequantized using an approximation of the dequantization operation. Essentially, the quantization process involves multiplying each DCT coefficient by a (floating point) weighting factor, and then scaling it by the corresponding quantization-step. Because all the quantization steps are powers of 2, the division can be simply carried out by means of bit shifting. A rounding process is incorporated to achieve smaller quantization errors. The processes of quantizing with rounding and dequantizing are shown in equations (2).
Quantization: QDCT=(DCTCoeff*WFactor+Sign(DCTCoeff)*Quanstep)/Quanstep, where Sign(x)={1 if x>0; 0 if x=0; −1 if x<0}
Dequantization: DCTCoeff=QDCT/WFactor*Quanstep,  (2)
where QDCT is the quantized DCT coefficient, Wfactor is the weighting factor and Quanstep is the quantization step.
Thus a floating-point division operation is performed as part of the dequantization operation. The implementation of the exemplary embodiment of the invention approximates the operations of equation (2) by equation (3).
DCTCoeff=((QDCT*IntFactor)*Quanstep)>>15;  (3)
where IntFactor=└32768/WFactor┘ and “>>15” means to shift to less significant bit positions by 15 bits.

[0081] Although this exemplary embodiment of the invention fully de-quantizes the coefficients using an approximation to the full dequantization algorithm, it is contemplated that the coefficients may be only partially dequantized as described above.

[0082] Preferably, a simple, optimal procedure to implement the VLC decoding is provided in step 13. Ideally this would achieve the YLC lookup in as little as 2 CPU cycles. A pre-stored lookup table is used to achieve a tradeoff between memory and efficiency. Since the length of the VLC code-word is not known in advance but only that it has a maximum length of 16 bits, the loon up table returns the correct code-word for any arbitrary input stream; in this exemplary embodiment of the invention, a table of size 216 is used. Using this table, the VLC decoding becomes a simple table lookup operation, which may be simplified further using a native hardware implementation on PENTIUM® CPUs manufactured by Intel Corporation.

II. MPEG Bit-Rate Control Via DV Decoding Level

[0083] The exemplary decoder described above processes the overflow bits both from the segments and from the individual macroblocks. It is contemplated, however, that to control the bit-rate of the encoded MPEG-2 signal, the partial decoding process may ignore the overflow bits that are associated with the segments or with both the segments and the macroblocks. In ignoring the overflow bits, the exemplary process selectively sets the coefficient values corresponding to the overflow bits to zero. In order to understand how the overflow bits are processed during conversion, it is helpful to understand how the overflow bits are generated during the initial encoding operation. The method of distributing the overflow blocks among the macroblocks and among the segments is described below.

[0084] There are three levels of bit rate distribution in a DV segment:

• • [0085] 1) The bits for each DCT block are distributed into the assigned space for the block (1^st level).
  • [0086] 2) The overflow bits of the DCT blocks are concatenated within the same macroblock and distributed to the unused space of the other DCT blocks of the macroblock. (2^nd level)
  • [0087] 3) If after the second level there are still overflow bits for some macroblocks in a segment, then these bits are concatenated and distributed to unused space of the DCT blocks of the same segment. (3^d level)

[0088] Because the blocks are run-length coded and variable length coded, each coefficient in each block is specified. The blocks of the segment are encoded in a predetermined order, storing the coefficients that do not fit into the data space allocated for a particular block into a list. If, after encoding a macroblock, coefficients for that macroblock are in the overflow list, the encoding method first tries to place these coefficients into available space in any of the blocks of the same macroblock in a predetermined order. If space can not be found, these coefficients are then stored in the overflow list for the segment. After the segment has been encoded, these coefficients are stored into available locations in the remaining macroblocks in a predetermined order.

[0089] The overflow bits can be recovered by reversing the process. As each block is decoded, any extra data in the block is identified as overflow data. When a decoded block does not include all of its coefficients, the process first looks to extra data in the same macroblock to recover the coefficients. Any overflow data remaining after the macroblock has been completely decoded is segment overflow data. Once all of the macroblocks in the segment have been processed in this manner, the process then decodes the remaining missing coefficients from the segment overflow data.

[0090] Thus, in transcoding the DV stream into the MPEG stream the bit rate of the MPEG stream can be controlled both by adjusting the quantization scale and by selecting which overflow bits are decoded. Three options are available, corresponding to the three levels of handling overflow bits.

[0091] 1) Decode only the bits in the assigned space for each DCT block. This method produces the lowest bit rate and the lowest data quality.

[0092] 2) in addition to (a), decode the overflow bits within each macroblock, namely the bits distributed in the 2^nd level. This will yield a higher data quality and bit-rate in the MPEG steam.

[0093] 3) Decode all the DV bits in the blocks and all of the overflow bits.

[0094] This method produces the highest quality and highest bit rate.

III. 248 to 88 DCT Conversion

[0095] FIG. 2 illustrates the relationship between a block of pixels (Block ‘P’) and to a block (Block ‘C’) of 248-DCT coefficients. Alternate rows of pixels are regrouped into two sub-blocks, P₁ and P₂, the blocks P₁ and P₂ are subject to a 4×8 DCT to provide blocks of coefficients, C₁ and C₂. These two blocks are then recombined to give the final block of 248-DCT coefficients. Mathematically, the operation of converting from a block of 248 format DCT coefficients to a block of 88 DCT coefficients is derived as follows:

• [0096] 1) Obtain C₁ and C₂ from block C using equations (4): $\begin{array}{cc}{C}_1=\frac{C_T+C_B}{2a}+H;C_2=\frac{C_T-C_B}{2a}+H& \left(4\right)\end{array}$
  where $a=\frac{1024}{2*724}$
  is a scaling factor and H is a constant matrix, which compensates forte fixed DC offset, CT is the matrix of coefficients from the top block and CB is the matrix of coefficients from the bottom part of the shown in FIG. 2.
• [0097] 2) Compute P₁ and P₂ by doing inverse 4×8 DCT according to equation (5):
  P₁=T₄^TC₁T₈;P₂=T₄^TC₂T₈  (5)
  • [0098] where T₄ and T₈ are the 4-point and 8-point DCT transformation matrices respectively.
• [0099] 3) Compute P, by shuffling the rows of P₁ and P₂ according to equation (6):
  P=A₁P₁+A₂P₂  (6)
  • [0100] where A₁ and A₂ are the matrices that represent a shuffling operation, for example. $A_1=[\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 0& 0\end{array}]A_2=[\begin{array}{cccc}0& 0& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 1\end{array}]$
• [0101] 4) Finally, perform regular DCT on the pixel block P to get the 88-DCT block, C′ according to equation (7):
  C^T=T₈PT₈^T  (7)
  The following summarizes the above steps. $\hspace{1em}\begin{array}{cc}\begin{array}{c}{C}^T=T_8{\mathrm{PT}}_8^T\\ =T_8\left(A_1{P}_1+A_2{P}_2\right)T_8^T\\ =T_8\left(A_1{T}_4^T{C}_1{T}_8+A_2{T}_4^T{C}_2{T}_8\right)T_8^T\\ =\left(\frac{F_1+F_2}{2a}\right)C_T+\left(\frac{F_1-F_2}{2a}\right)C_B+\left(F_1+F_2\right)H\\ =\mathrm{FC}+K\end{array}& \left(8\right)\end{array}$
  where $F_1=T_8{A}_1{T}_4^T;F_2=T_8{A}_2{T}_4^T$ $F=\left(\frac{F_1+F_2}{2a}\frac{F_1-F_2}{2a}\right)$ $C=\left(\begin{array}{c}{C}_T\\ C_8\end{array}\right)$ $K=\left(F_1+F_2\right)H$

[0102] In the last step above, C_T and C_B are combined into a single matrix C; F and K are constant matrices derived from F₁, F₂ and H as shown.

[0103] As shown in Equation (8), this operation of converting from a block of coefficients C₂₄₈ in 248 format to a block of coefficients C₈₈ in 88 format can be mathematically reduced to equation (9):
C₈₈=FC₂₄₈+K  (9)

[0104] First the matrix F is pre-computed and then approximated by an integer array to an accuracy of about 4 decimal digits. This matrix is very sparse, i.e., only a small fraction of its coefficients are non-zero. Also, the matrix K has only the DC coefficient non-zero. Therefore, the operation described by equation (9) can be reduced to a hard-coded multiplication by the non-zero coefficients of the F matrix, and addition of the DC coefficient of the K matrix.

IV. Conversion of the Decoded DV Coefficients to MPEG-2 4:2:2 Profile@Main Level

[0105] FIG. 9 is a hierarchical flow diagram that shows details of the MPEG-2 encoding process. This module produces an MPEG-2 video stream from a block of dequantized (or at least partially dequantized) DCT coefficients.

[0106] In step 901 the data stream is identified with an MPEG-2 sequence header and then, at step 902, each image frame is identified by an MPEG picture header. The process of encoding a video frame includes steps 902-914, as described below. The encoding of video frames continues until, at step 903, no more video frames are to be encoded.

[0107] In step 904 the DCT blocks that resulted from partially decoding the DV signal are arranged to form slices of MPEG macroblocks, each with a slice header. In the exemplary embodiment, all frames are encoded as MPEG-2 intra-frame coded data (I-frames). Accordingly, at step 905, the frame is marked as being an I frame. In steps 906-914, the individual macroblocks are encoded using the blocks that were decoded from the DV signal. In steps 907 and 908, the macroblock header is inserted into the bit stream including a first data value indicating that the macroblock is a frame encoded 4:2:2 macroblock and a second data value indicating an appropriate quantization scale value for the macroblock.

[0108] At steps 909-914, the DV blocks are encoded and requantized. At step 910, the DC coefficient is encoded. At step 911, the AC coefficients are quantized according to the quantization table and at steps 912-914 the AC coefficients are variable-length coded. The encoding of an individual block continues until, at step 914, 64 coefficients have been encoded. When this occurs, control transfers to step 909 to encode the next block. When eight blocks have been encoded at step 909, control transfers to step 906 to encode the next macroblock. When a number of macroblocks corresponding to image pixels that extend across the video frame (a slice) have been encoded, control transfers to step 904 to encode the next slice.

[0109] In step 912 the DCT coefficients decoded from the DV stream are requantized as DCT coefficients according to the MPEG-2 standard. If the block being encoded was a 248 DV block that was converted to an 88 block, the coefficients are fully dequantized. If, however, the block was originally an 88 block in the DV signal, the coefficients at step 911 may be quantized. DV coefficients.

[0110] At step 911, the fully dequantized coefficients (rawCoeff) are quantized in accordance with the MPEG standard into quantized coefficients (QuanDCT) using the MPEG quantization matrix (Qmatrix) and quantization scale values (Qscale) as defined by equation (10):
Qstep=Qmatrix[i][i]×Qscale
QuanDCT=(16*rawCoeff+Sign(rawCoeff)*Qstep/2)/Qstep  (10)
V. Partial Dequantization and Requantization

[0111] As set forth above, rather than fully dequantizing the DV coefficients and then requantizing the MPEG-2 coefficients, the quantized DV coefficients for blocks that we re originally in 88 format may be converted into quantized MPEG-2 coefficients by a simple bit-shifting operations. In this conversion process, the MPEG-2 weighting matrix is selected to correspond to the 88 DCT block number matrix, shown in FIG. 3, with the quantization steps determined from the first row of the DV quantization table (i.e. the finest step size). The quantized DV coefficients may be converted to quantized MPEG-2 coefficients by a simple bit-shift operation on each coefficient. This is possible because the quantization steps in the DV standard are always a power of two times the finest quantization steps.

VI. DCT Mode Selection in DCT Domain (MPEG-2 4:2:2 (I-Frames only to DV))

[0112] Transcoding MPEG-2 to DV follows from symmetry but is briefly described below with reference to FIG. 10. In the exemplary embodiment of the invention, the input MPEG data is limited to be intra-frame (I-Frame) coded and having a 4:2:2 chrominance format.

[0113] FIG. 10 illustrates a general block diagram of a software transcoder in accordance with a further aspect of the present invention. The transcoder takes I-frames of MPEG-2 data as input and produces raw DCT coefficients that are then used to generate the corresponding DV signal: The transcoder re-quantizes the MPEG-2 DCT coefficients to DV DCT coefficients and encodes the coefficients as a DV signal.

[0114] As can be appreciated, in partial decoding, instead of reconstructing the pixels of the video frame, corresponding DCT blocks are extracted in step 101, each macroblock of the slice is decoded to extract DCT blocks. In step 102, the coefficients are processed through a variable length decoder and a run-length decoder. In step 103 the quantization step size used for each of the DCT blocks is determined and the coefficients are dequantized. In steps 104, the blocks of MPEG DCT coefficients are converted into blocks of DV coefficients. At step 105, the converted blocks are regrouped into DV macroblocks. At step 106, the DV macroblocks are quantized and, at step 107, the quantized macroblocks are variable-length coded to produce the DV encoded output signal.

[0115] In the exemplary embodiment of the invention, the MPEG-2 coefficients are completely dequantized at step 103 and the blocks of coefficients are then requantized according to the DV standard at step 106. In addition, because both MPEG-2 and DV use the same zigzag scan order for 88 DCT and the same run-length coding, the run-lengths and the coefficient order can be reused.

[0116] By using only the I-frame mode in the MPEG-2 format, implementation is simplified and the editing facilities remain intact. The basic transcoding process consists of decoding each MPEG-2 frame partially, i.e. down to DCT coefficients, and then re-encoding the coefficients into DV format. Partial decoding generally includes:

• [0117] (1) VLC decoding of the MPEG-2 stream.
• [0118] (2) Dequantize the DCT coefficients
• [0119] (3) Converting MPEG macroblocks into DV macroblocks.

[0120] After dequantizing the MPEG frame-mode DCT blocks, it is desirable to determine whether a particular block should be encoded as a 248 DV block. In the exemplary embodiment of the invention, the each frame-mode MPEG block is analyzed to determine if it exhibits significant intra-frame motion. Because there are two DCT modes in DV encoding, (i.e., 88 frame mode and 248 field mode) a significant improvement in both temporal and spatial resolution may be achieved by recognizing MPEG blocks that combine two fields which exhibit significant intra-frame motion and encoding those blocks as 248 blocks in the DV signal.

[0121] The criteria for determining whether an MPEG-2 block is a candidate for recoding as a DV 248 block is described below. Assume that a pixel DCT block is denoted as P(x,y) (x,y=0,1 . . . 7) where x is the vertical position y is the horizontal position.

[0122] In the pixel domain, the selection of the DCT mode follows from equation (12) $\begin{array}{cc}\mathrm{Sum}=\sum _{y=0}^7\mathrm{abs}\left(\sum _{x=0}^7{\left(-1\right)}^{x}P\left(x,y\right)\right)& \left(12\right)\end{array}$

[0123] If the Sum≧a predetermined threshold, the 248 DCT mode is selected, otherwise the 88 DCT mode is selected.

[0124] When only 88 DCT coefficients are decoded from the MPEG stream, it is undesirable to perform IDCT to recover the pixels and then perform the process described above just to determine whether the block should be coded as a 248 DCT block. Preferably, this analysis and selection should be performed in the DCT domain. For example, a pixel DCT block Q(x,y) is constructed such that:

• • [0125] Q(x,y)=a when x is even
    • [0126] where a=threshold/sum, where the threshold=600 and $a=\frac{600}{32}Q\left(x,y\right)=0$
    • [0127]  when x is odd

[0128] Using this DCT block, Sum==the predetermined threshold defined in the pixel domain above. Next the 88 DCT is performed on Q(x,y) to get a DCT coefficient DQ(m,n)(m.n=0,1, . . . 7). Note that only D(2v+1,0) is not zero (v=0,1,2,3) and DQ(7,0) is significantly greater than its counterparts in those 88 DCT blocks with their mode selected in the pixel domain. Thus, it is reasonable to use the absolute value of DQ(7,0) as an index to make the mode selection decision in the DCT domain.

[0129] Therefore, if the 88 DCT coefficient block is denoted D(m,n) m,n=0,1 . . . 7, the selection process in the DCT domain is:

[0130] If abs(D(7,0))≧DQ(7,0), 248 DCT mode is selected (and the 88 to 248 DCT conversion is performed), otherwise the 88 DCT is selected (i.e., D(m,n) remains intact).

[0131] At step 104, the exemplary process examines each decoded MPEG block to determine whether it should be encoded as an 88 or 248 DV block. The method for converting from 88 coefficient blocks to 248 coefficient blocks follows from the process, described above, that is used to convert the 248 blocks to 88 blocks. Equation (13) that describes the conversion of 88 blocks into 248 blocks can be derived from equation (9),
C₂₄₈=F⁻¹(C₈₈−K) =F⁻¹C₈₈K₈₈  (13)
where K₈₈=F⁻¹K. The inventors have determined that FF^T=1.00021 where I is an 8 by 8 identity matrix. Consequently, F⁻¹≈F^T and the translation from an 88 block to a 248 block may be approximated by equation (14).
C₂₄₈=F^TC₈₈−F^TK  (14)
Thus, the same process that is used to convert the 248 blocks of coefficients into 88 blocks of coefficients may be used to convert 88 blocks of coefficients into 248 blocks of coefficients.

[0132] Although the invention has been described in terms of a transcoding process, it is contemplated that the invention may be implemented as computer software embodied in a computer-readable carrier such as a magnetic disk, optical disk, radio-frequency carrier wave or audio-frequency carrier wave.

[0133] It will be appreciated by those skilled in the art that changes could be made to the embodiments described above without departing from the broad inventive concept thereof. For example, while the present invention utilizes DV and MPEG-2 formats, those skilled in the art recognize that the method described herein is generally applicable to intra-coded or intra-frame formats. It is underestood, therefore, that this invention is not limited to the particular embodiments disclosed, but is intended to cover modifications within the spirit and scope of the present invention.