A method for processing i-blocks used with motion compensated temporal filtering

A method for processing I-blocks in motion compensated temporal filtering {A method for processing i-blocks used with motion compensated temporal filtering}

[Related application]

This application claims priority to US Provisional Application No. 60/477,183, filed on June 10, 2003, the entire contents of which are incorporated herein by reference.

The present invention relates generally to a method and system for processing video frames, a computer-readable recording medium recording a computer program, and a computer system, and more particularly, to be used in Motion Compensated Temporal Filtering (MCTF). A method, system, computer program product and computer system for processing I-blocks.

A conventional method of performing Motion Compensated Temporal Filtering (MCTF) on pixels in successive video frames is to cover and uncover spatial regions as frames progress over time. ) causes a poor match between pixels in successive frames. This poor match can be caused by the occlusion effect when objects pass in front of different objects over time. A poor match can also be caused by other effects, such as an image field of a view that expands or contracts. The resulting poor match results in artifacts in low frame-rate video output from MCTF as well as low coding efficiency.

Accordingly, there is a need for a method of handling poor match in Motion Compensated Temporal Filtering (MCTF) of pixels within successive video frames more efficiently and/or more accurately than the prior art.

The present invention provides a method for processing video frames,

each pair of frames consists of a frame A and a frame B, each frame A and B comprising blocks of pixels, the frame A preceding the frame B in time, providing a pair of consecutive video frames step;

determining a connected state that is a connected state or an unconnected state of each pixel of the frame B with respect to the pixels of the frame A;

classifying each block of the frame B as either unconnected or single connected;

after the classification, reclassifying the single connected blocks of the frame B that satisfy the reclassification criterion as unconcatenated;

after the reclassification, categorizing each unconnected block of the frame B into a P-block or an I-block;

after dividing the category, calculating the values of the pixels of each I-block of the frame B by spatial interpolation based on the values of the available nearest neighbor pixels associated with each I-block; and

after the calculation, generating a residual error block for each I-block of the frame B.

A pair of consecutive video frames, each pair of frames consisting of a frame A and a frame B, each comprising blocks of pixels, the frame A preceding the frame B in time. In a system for processing them,

means for determining a connected state that is a connected or unconnected state of each pixel of the frame B associated with the pixels of the frame A;

means for classifying each block of the frame B as either unconcatenated or single concatenated;

means for reclassifying single connected blocks of frame B that satisfy a reclassification criterion as unconcatenated;

means for categorizing each unconnected block of frame B into a P-block or an I-block;

means for calculating the values of the pixels of each I-block of frame B by spatial interpolation based on values of available nearest neighbor pixels associated with each I-block; and

and means for generating a residual error block for each I-block of frame B.

The present invention provides a computer-readable recording medium recording a computer program having a computer-readable embodied program code, wherein the computer-readable program code comprises an algorithm suitable for executing a method of processing video frames. provided, the method comprising:

each pair of frames consists of a frame A and a frame B, each frame A and B comprising blocks of pixels, the frame A preceding the frame B in time, providing a pair of consecutive video frames step;

determining a connected state that is a connected state or an unconnected state of each pixel of the frame B with respect to the pixels of the frame A;

classifying each block of the frame B as either unconnected or single connected;

after the classification, reclassifying the single connected blocks of the frame B that satisfy the reclassification criterion as unconcatenated;

after the reclassification, categorizing each unconnected block of the frame B into a P-block or an I-block;

after dividing the category, calculating the values of the pixels of each I-block of the frame B by spatial interpolation based on the values of the available nearest neighbor pixels associated with each I-block; and

after the calculation, generating a residual error block for each I-block of the frame B.

The present invention provides a computer system comprising a processing unit, a computer readable memory unit coupled to the processing unit, wherein the memory unit comprises instructions for executing a method of processing video frames when executed by the processing unit, the method comprising: silver,

each pair of frames consists of a frame A and a frame B, each frame A and B comprising blocks of pixels, the frame A preceding the frame B in time, providing a pair of consecutive video frames step;

determining a connected state that is a connected state or an unconnected state of each pixel of the frame B with respect to the pixels of the frame A;

classifying each block of the frame B as either unconnected or single connected;

after the classification, reclassifying the single connected blocks of the frame B that satisfy the reclassification criterion as unconcatenated;

after the reclassification, categorizing each unconnected block of the frame B into a P-block or an I-block;

after dividing the category, calculating the values of the pixels of each I-block of the frame B by spatial interpolation based on the values of the available nearest neighbor pixels associated with each I-block; and

after the calculation, generating a residual error block for each I-block of the frame B.

The present invention provides an excellent method for dealing with occlusion of objects in motion compensated temporal filtering (MCTF) of pixels of successive video frames, the method according to the invention being more efficient and/or compared to methods existing in the prior art. or accurate.

In the following, the introduction; Motion Compensated Temporal Filtering (MCTF); processing of I-blocks; and a computer system divided into four parts, the present invention will be described in detail.

<u>Introduction</u>

Video compression schemes are redundant from the input video signal by encoding the frames of the input video signal with compressed information representing approximate images constituted by the frames of the input video signal prior to transmission of the input video signal. ) to remove the information. Sending the compressed information to the destination, the video signal is reconstructed by decoding an approximate image from the compressed information. In temporal redundancy, pixel values are not independent but are correlated with their neighbors over successive frames of the input video signal.

In the hybrid coding scheme of the Motion Picture Expert Group (MPEG), temporal redundancy may be removed by Motion-Compensated Prediction (MCP). A video signal is often divided into a series of groups of pictures (GOP), each GOP starting with an intra coded frame (I), forward predictive coded frames (P) and bidirectional predicted frames. It is followed by the arrangement in (B). Both the P-frames and B-frames are inter frames. A target macroblock in a P-frame can be predicted from a past reference frame (forward prediction). Bidirectional prediction, also called motion compensation (MC) interpolation, is one of the important features of MPEG video. Bidirectional predictive coded B-frames use two reference frames, one in the past and one in the future. A target macroblock in a B-frame is predicted from a past reference frame (forward prediction), predicted from a future reference frame (reverse prediction), or an average of two prediction macroblocks predicted from each of the past and future reference frames, respectively. It can be predicted by (interpolation). A target macroblock of either a P-frame or a B-frame may be intra-coded as an I-block or a P-block as defined below.

Taking into account the luminance and/or chrominance values of pixels in both the current input frame and the reference frame, and based on the contents of each of the previous or following reference frames, forward or backward prediction is performed on the data in the current input frame (i.e. picture). to encode Accordingly, the reference frame used for predictive encoding is either the previous reference frame or the following reference frame. For pixels of a given input block in the current input frame (for example, pixels in a 16×16 array), predictive coding is a motion-compensated prediction ( MCP) to determine whether there is a 16x16 pixel array with at least a predetermined minimum degree of correlation with the input block in the reference frame. If an array having the predetermined minimum degree of correlation exists, the magnitude and direction of displacement between the 16×16 pixel array of the reference frame and the input block found is a motion vector (MV) having horizontal and vertical components. ) is obtained in the form The difference between the pixel values (eg, luminance value, chrominance value, etc.) of the input block and the corresponding pixel in the 16×16 pixel array of the found reference frame is motion compensation prediction error values. As mentioned above, prediction from a previous reference frame is referred to as forward prediction, and prediction from a subsequent reference frame is referred to as backward prediction. If the relevant 16×16 block in the reference frame is not found within the search range, the input block is intra-coded within the input frame and is referred to as an I-block. In bi-directional prediction, the values of the input block may be predicted based on two 16×16 blocks present in each of the previous and next reference frames. The above description of the 16×16 pixel block is merely exemplary, and the idea according to the present invention may be applied to pixel blocks having various other pixel array sizes.

In the present invention, an unconnected block in the current input frame is classified as either an I-block or a P-block. An I-block is an input block in the current input frame that does not have sufficient correlation (eg, some degree of minimal correlation) with pixels of the corresponding block in the reference frame used for forward or backward prediction with respect to the frame. Defined. Due to the lack of sufficient correlation, I-blocks are encoded as a whole within a given frame independently of the reference frame. P-blocks are generated by forward prediction from a reference frame on the premise that a reference frame precedes a given frame; by backward prediction under the assumption that a reference frame follows a predetermined frame; or by bi-prediction using both previous and next reference frames.

An example of an I-block is a block of newly exposed pixels in the current input frame that does not have a corresponding pixel in the previous frame. Other examples of I-blocks include motion blocks that do not match well, particularly pixels that are partially covered or partially closed in the current input frame. Here, motion blocks that do not match well do not have sufficient correlation with the corresponding block pixels of the reference frame. The present invention provides a method for determining and encoding I-blocks.

<u>Justice</u>

Terms used in describing the present invention are defined as follows.

A "video coding system" is a system for encoding video data.

A "video coder" is an algorithm that reduces the number of bits required to store a video clip by removing redundancy and introducing controlled distortion.

A "subband/wavelet coder" is a video coder that uses a subband/wavelet transform in the redundancy reduction process.

A "temporal correlation" is a correlation between pixels of adjacent or adjacent frames.

"Spatial correlation" is a correlation between pixels within the same frame.

"Motion prediction" is the prediction of a motion or displacement vector that locates a matching block in another frame.

"Motion compensation (MC)" is the process of actually aligning a block in the current frame with a matching block in another frame.

"Motion Compensated Time Filtering (MCTF)" is a process of filtering an arrangement of blocks or pixels along a time axis (ie, a motion trajectory) in a manner described with reference to FIG. 2 to be described later.

A "low time frame" is a frame containing a low spatial frequency common to a pair (or larger set) of frames.

A "high time frame" is a frame containing a high spatial frequency constituting the MC difference in a pair (or larger set) of frames.

"Temporal redundancy" refers to the dependence between pixels of adjacent or adjacent frames.

"Block matching" is a method of predicting the movement of a block of pixels from one frame to an adjacent or adjacent frame.

"Variable size block matching" is block matching motion prediction that uses variable size blocks to better represent the motion field. The block size may, inter alia, range from 4x4 to 64x64.

A "global motion vector" is a motion vector used for an entire frame whose associated block size is equal to the frame size.

A "local motion vector field" is an arrangement of motion vectors generated by the use of blocks smaller than the entire frame.

"Motion Compensated Prediction (MCP)" is a data reduction technique that warps a previously transmitted frame before using motion vectors for prediction of the current frame, and quantizes and transmits only the resulting prediction error.

"Displaced frame difference (DFD)" is an error generated by motion compensation prediction.

A "hybrid coder" is a video coder that uses MC prediction within a feedback loop to compress data temporally and then a spatial transform coder to code the resulting prediction error.

<u>Motion Compensated Temporal Filtering:</u><u>MCTF</u><u>)</u>

Scalable video coding is an area being investigated within the Motion Picture Experts Group (MPEG) of the International Organization for Standardization (ISO). The purpose of MPEG is to establish an international standard for the transmission and storage of combined audio and video signals. A key factor for this is to compress the audiovisual signal due to its large size when uncompressed. The scalable video coder provides an embedded bitstream that includes a full range of bitrates, lower resolutions and lower frame rates, in addition to the full frame rate and full resolution input to the scalable coder. Due to the embedding, the lower bit rate result is embedded in each of the streams with the higher bit rate.

1 shows a video coding system 50 according to preferred embodiments of the present invention. The input video 51 is received by the MCTF processing unit 52 and includes a group of pictures (GOP) equal to 16 input frames. Each frame has pixels, and each pixel has a pixel value for the pixel characteristics of luminance and chrominance. For each block data processed by the MCTF processing unit 52, the MCTF processing unit 52 requires motion information in the form of a motion vector. Accordingly, the input video 51 data is transmitted from the MCTF processing unit 52 to the MCTF processing unit 52, which determines motion vectors and transmits the determined motion vectors to the MCTF processing unit 52 for performing motion compensation time filtering. is sent to In addition, the motion information is coded in the motion field coding processing unit 57 and then transmitted to the packetizing unit 55 .

The MCTF processing unit 52 converts one low-time frame and a plurality of high-time frames having converted pixel values, derived from input frames of the input video 51 , as described in the description of FIG. 2 , which will be described later. Produces output frames containing The generated output frames are spatially analyzed using a subband wavelet coder, that is, discrete wavelet transform, and then processed by the spatial analysis unit 53 . By using the MCTF processing unit 52 , the video coding system 50 does not suffer from the drift problem seen in hybrid coders with a feedback loop.

The spatial analysis unit 53 decomposes the generated output frames (ie, one low time frame and a plurality of high time frames) into one low frequency band and bands having an increasing scale of increasingly higher frequencies. . Accordingly, the spatial analysis unit 53 performs spatial pixel transformation for deriving spatial subbands in a manner similar to the pixel transformation performed by the MCTF processing unit 52 in the time domain. The output of the spatial analyzer 53 is uncompressed floating point data, and a large number of subbands may be mostly composed of values near zero.

In the space generated by the spatial analysis unit 53, these spatial subbands are EZBC (Embedded Zero), which is one of the subband/wavelet coder series using temporal correlation that is not completely embedded in quality/bit rate, spatial resolution, and frame rate. Block Coder) 54 . The EZBC 54 algorithm provides basic scalability characteristics by individually coding each spatial resolution and high temporal subband. The EZBC 54 includes a compression block that quantizes subband coefficients and assigns bits to the quantized subband coefficients. The quantization transforms the floating-point output of the spatial analysis unit 53 into a binary bit representation, and then discards the relatively insignificant bits by truncating the binary bit representation to such a degree that only negligible distortion occurs. . The EZBC 54 is an adaptive arithmetic coder that converts a fixed bit string into a variable length string and as a result realizes further compression. Accordingly, the EZBC 54 is a variable length coder called a quantizer and conditional adaptive arithmetic coder. The quantizer, on the other hand, discards bits, and the variable length coder compresses the output from the quantizer without loss. The bitstream generated by the EZBC 54 is interleaved and transmitted to the packetizer 55 .

The packetizer 55 combines the bits of the streams generated by the EZBC 54 with the bits of the motion vectors (necessary for later decoding) transmitted from the motion field coding unit 57, and generates a desired size. Breaks down combinations of bits into packets (eg, Internet packets of 500 kilobytes or less). The packetizer 55 then sends the packet to a destination (eg, a predetermined storage area for storing encoded video information) through a communication channel.

FIG. 2 illustrates an MCTF processing process implemented by the MCTF processing unit 52 of FIG. 1 for a GOP having a size of 16 frames according to preferred embodiments of the present invention. In Fig. 2, 5 levels in the MCTF process of continuous filtering are shown, ie, levels 5, 4, 3, 2 and 1 with 16, 8, 4, 2 and 1 frames, respectively. Thus, each level N (N=1,2,3,4,5) equals 2<sp>N-1</sp> contains frames. Level 5 includes 16 input frames of the input video 51 of FIG. 1 , that is, input frames F1, F2, ..., F16 arranged in an increasing order from left to right. MC temporal filtering is performed on the frame pairs to generate low-time (tL) and high-time (tH) sub-band frames of the next lower time scale or frame rate. In Fig. 2, solid lines indicate low-time frames, and dotted lines indicate high-time frames. At each time scale, the curve points to the corresponding motion vectors.

In Figure 2, MC temporal filtering is performed 4 times resulting in 5 time scales or frame rates, i.e. the original frame rate and four lower frame rates. The generated frame rates are full rate, 1/2 full rate, 1/4 full rate, 1/8 full rate and 1/16 full rate at levels 5, 4, 3, 2 and 1 respectively. Thus, if the input frame rate is 32 frames per second (fps), then the lowest resulting frame rate at level 1 is 2 fps. In FIG. 2, the optimal frame rate is indicated by (1), and the next higher frame rate is indicated by (2) and the like.

In the motion prediction from level 5 to level 4 and related temporal filtering, the motion prediction unit 56 of FIG. 1 includes F1 to F2, F3 to F4, F5 to F6, F7 to F8, F9 to F10, F11 to F12, Motion predictions from F13 to F14 and F15 to F16 are performed to determine motion vectors M1, M2, M3, M4, M5, M6, M7 and M8, respectively. The MCTF processing unit 52 of FIG. 1 performs temporal filtering on frames F1 and F2 to generate a low-time frame L1 and a high-time frame H1; performing temporal filtering on frames F3 and F4 to generate low-time frame L2 and high-time frame H2; performing temporal filtering on frames F5 and F6 to generate low-time frame L3 and high-time frame H3; performing temporal filtering on frames F7 and F8 to generate low-time frame L4 and high-time frame H4; performing temporal filtering on frames F9 and F10 to generate low-time frame L5 and high-time frame H5; performing temporal filtering on frames F11 and F12 to generate low-time frame L6 and high-time frame H6; performing temporal filtering on frames F13 and F14 to generate low-time frame L7 and high-time frame H7; and temporal filtering on frames F15 and F16 to generate low-time frames L8 and high-time frames H9. In general, V the corresponding pixel values in the child frames<sb>A</sb> and V<sb>B</sb>In the special case where Haar filters are used for temporal filtering, corresponding pixel values in low-time and high-time frames are respectively V<sb>A</sb>+V<sb>B</sb><sb></sb>and V<sb>A</sb>-V<sb>B</sb>proportional to Accordingly, the pixel values of the low-time frames are comparable to the average of the corresponding pixel values in the child frames. Conversely, the pixel values of the high-time frames are proportional to the difference between the corresponding pixel values in the child frames. Thus, if the pixel values in the child frames are close to each other, the pixels in the high-time frame have low energy (ie, a large number of values are near zero), which can result in greater compression.

In motion prediction from level 4 to level 3 and related temporal filtering, the motion prediction unit 56 of FIG. 1 performs motion prediction from L1 to L2, L3 to L4, L5 to L6, and L7 to L8, respectively. Determine the associated motion vectors M9, M10, M11 and M12. The MCTF processing unit 52 of FIG. 1 performs temporal filtering on frames L1 and L2 to generate a low-time frame L9 and a high-time frame H9; performing temporal filtering on frames L3 and L4 to generate low-time frame L10 and high-time frame H10; performing temporal filtering on frames L5 and L6 to generate low-time frame L11 and high-time frame H11; and temporal filtering on the frames L7 and L8 to generate a low-time frame L12 and a high-time frame H12.

In the motion prediction from level 3 to level 2 and related temporal filtering, the motion prediction unit 56 of FIG. 1 performs motion prediction from L9 to L10 and L11 to L12 to determine related motion vectors M13 and M14, respectively. . The MCTF processing unit 52 of FIG. 1 performs temporal filtering on frames L9 and L10 to generate a low-time frame L13 and a high-time frame H13; and performing temporal filtering on the frames L11 and L12 to generate a low-time frame L14 and a high-time frame H14.

In the motion prediction from level 2 to level 1 and related temporal filtering, the motion prediction unit 56 of FIG. 1 performs motion prediction from L13 to L14 to determine related motion vectors M15. The MCTF processing unit 52 of FIG. 1 generates a low-time frame L15 and a high-time frame H15 by performing temporal filtering on the frames L13 and L14.

As a result of performing the MCTF of FIG. 2 , 16 frames composed of the low-time frame L15 and the high-time frames H1, H2, ..., H15 at these exemplary five levels are output from the MCTF processing unit 52 as shown in FIG. 1 is transmitted to the spatial analysis unit 53 . As described above, since the high-time frames H1, H2, ..., H15 contain a large number of values near zero, the high-time frames H1, H2, ..., H15 are highly compressed. This is possible.

Given the frames of L15, H1, H2, ..., H15, the frames of levels 2, 3, 4 and 5 sequentially reverse the process of generating frames of L15, H1, H2, ..., H15. It can be regenerated by For example, frames L15 and H15 of level 1 are mathematically combined to recreate L13 and L14 of level 2, for example. Similarly, L13 and H13 of level 2 are mathematically combined to regenerate L9 and L10 frames of level 3, and L14 and H14 of level 2 are mathematically combined to recreate L11 and L12 of level 3 . This process may be sequentially continued until the frames of F1, F2, ..., F16 of level 1 are regenerated. Since the compression performed by the EZBC 54 of FIG. 1 is lossy, the regenerated frames of levels 2-5 will be approximately, but not exact, identical to the original frames of levels 2-5 before being temporally filtered. .

<u>Processing of I-blocks</u>

As described above with respect to FIG. 2 , since MCTF decomposition is similarly applied to a plurality of frame pairs, a pair of consecutive frames representative of one level of FIG. 2 (eg, a frame of level 4) Let's focus on L1 and L2). Two representative frames of this pair of consecutive frames are denoted frames A and B, and forward prediction is performed from frame A to frame B, so that frame A precedes frame B in time. Newly exposed pixels in frame B do not have corresponding pixels in frame A. Similarly, pixels that were not visible in pixel A have no corresponding pixels in pixel B. The present invention uses I-blocks to locally process poorly matched motion blocks resulting from newly exposed pixels in frame B. For I-blocks identified according to the present invention, as described below, MC temporal filtering is omitted and spatial interpolation is used instead of determining the pixel values in the I-block. The resulting spatial interpolation error block for the I-block (also referred to as the "residual error block of the interpolated I-block") is then overlaid (ie, inserted) into the corresponding block of the associated MCTF high time frame.

The present invention discloses a video compression method comprising a spatiotemporal or space-time transformation using motion compensated blocks in pairs of input frames, such as a representative pair with input frames A and B. These blocks have various sizes and are selected to match the local motion vector field, so that small blocks exist in fields with high spatial gradients and large blocks exist in flatter regions with small spatial gradients. . The block based on this motion field is used to control the spatiotemporal transformation in order to perform a filter along the coarse motion path. The result of this transformation is compressed for transmission or storage.

Some blocks may not be connected to their neighbors in the next frame (in time) because of areas covered or exposed in the frame due to, for example, ball-like motion passing in front of a static background object. Such regions (ie, I-blocks) should not participate in MC temporal filtering, as MC temporal filtering may introduce artifacts in low frame rate video. These I-blocks need to be compressed along with other blocks (ie, P-blocks) of the high time frame. P-blocks can be used to spatially predict unconnected I-blocks through spatial interpolation. These I-blocks are therefore suitable for targeting non-hybrid MCTFs.

3 is a flow chart illustrating steps 31-38 of using I-blocks in MCTF high time frames, in accordance with preferred embodiments of the present invention.

In step 31, forward prediction is performed from frame A to frame B using two consecutive frames A and B in one MCTF filtering level. For example, frames A and B may represent frames F1 and F2 in level 5 of FIG. 2 or frames L1 and L2 of level 4 of FIG. 2 .

In steps 32 and 33, a connection state of the pixels of each of frames A and B is determined. Each pixel in frames A and B will be classified as having a connected state of either "connected" or "unconnected" as follows. Fig. 4 shows A1, A2, ..., A12 pixels of frame A and B1, B2, ..., B12 pixels of frame B. Pixels A1, A2, A3 and A4 are in block 1 of A of the frame. Pixels A5, A6, A7 and A8 are in block 2 of A of the frame. Pixels A9, A10, A11 and A12 are in block 3 of A of the frame. Pixels B1, B2, B3 and B4 are in block 1 of B of the frame. Pixels B5, B6, B7 and B8 are in block 2 of B of the frame. Pixels B9, B10, B11 and B12 are in block 3 of B of the frame. Pixels in frame A are used as references for pixels in frame B in connection with forward motion prediction from frame A to frame B. Note that the blocks of frames A and B are 4x4 pixel blocks, and FIG. 4 only shows one column of each of the four column blocks. In Fig. 4, one pixel P of frame B<sb>B</sb>One pixel P of frame A pointed by the arrow from<sb>A</sb>is the pixel P<sb>B</sb>is used as a reference for For example, pixel A1 of frame A is used as a reference for pixel B1 of frame B.

In step 32, a pixel in frame A is classified as unconnected if it is not used as a reference by any pixel in frame B. Accordingly, pixels A7 and A8 are unconnected. A pixel in frame A is concatenated if used as a reference by a pixel in frame B. Accordingly, pixels A1-A6 and A9-A12 are connected. However, each of pixels A3 and A4 requires special handling because it is being used as a reference by one or more pixels of frame B. For example, pixel A3 is being used as a reference by pixels B3 and B5 of frame B, and the present invention is to keep pixel A1 as a reference to either pixel B3 or pixel B5, but not to both pixels B3 and B5. Minimum mean-squared displaced frame difference (as defined below)<shadow>DFD</shadow>)) using an algorithm based on calculations. Note that pixel A3 resides inside block 1 of frame A and pixel B3 resides inside block 1 of frame B, the above algorithm calculates the square-mean DFD between block 1 of frame A and block 1 of frame B. Calculate DFD11, which is Note that pixel A3 is inside block 1 of frame A and pixel B5 is inside block 2 of frame B. to calculate If DFD11 is less than DFD12, pixel A3 is kept as a reference for pixel B3, and is dropped as reference for pixel B5. If DFD12 is less than DFD11, pixel A3 is kept as a reference for pixel B5, and is dropped as reference for pixel B3. If DFD11 and DFD12 are the same, various tie-breakers can be used. One example of such a tiebreaker is the "scan order" in which pixel A3 continues as a reference for whichever pixel B3 or B5 first uses pixel A3 as reference. An example of a second tiebreaker is to select a random number R from a uniform distribution between 0 and 1, and keep the pixel A3 as a reference to the pixel B3 if the R is less than 0.5; or to keep the pixel A3 as a reference of the pixel B5 if the R is greater than or equal to 0.5. In the example of Fig. 4, DFD11 is smaller than DFD12, so that pixel A3 is kept as reference for pixel B3 and dropped as reference for pixel B5. Similarly, each of pixels B4 and B6 uses pixel A4 as a reference, and the aforementioned DFD-based algorithm indicates that the pixel A4 is not for both of the pixels B4 or B6, but as a reference for either of the pixels B4 or B6. can be used to maintain In the example of FIG. 4 , pixel A4 is retained as reference to pixel B4 and dropped as reference to pixel B6 based on the DFD-based algorithm described above.

In step 33, a DFD-based algorithm is applied to resolve the case where a pixel in frame A is used as a reference by more than one pixel in frame B, then a pixel in frame B that does not use a reference pixel in frame A is concatenated displayed as not For example, after applying the DFD-based algorithm as described above, pixels A3 and A4 are dropped as references to pixels B5 and B6, respectively. Accordingly, pixels B5 and B6 are unconnected. The pixels of different frame B are connected. Accordingly, pixels B1-B4 and B7-B12 are connected. If the aforementioned DFD-based algorithm has been executed (ie when the connection states of the pixels of frame A have been determined), then pixel A3 from pixel B5 in FIG. Note that the arrow pointing to and the arrow pointing from pixel B6 to pixel A4 become meaningless. Although step 33 is performed after step 32 in FIG. 4 , step 33 may be generally performed before step 32 . The above-described DFD-based algorithm for resolving the case where a pixel in frame A is used as a reference in more than one pixel in frame B may be performed before, during, or after steps 32 and 33 are performed. . As another example, if step 33 is performed prior to step 32, the DFD-based algorithm described above may be performed before step 33, between steps 33 and 32, or after step 32.

What is actually needed as a result of performing steps 32 and 33 is the connected state (ie, connected or unconnected) of each pixel of frame B relative to frame A. Accordingly, step 32 can be omitted in general. This is because the connection state of each pixel of the frame B requires information on the reference pixels of the frame A for each pixel of the frame B, not information on the connection state of each pixel of the frame A.

The square-mean DFD between one block of frame A and one block of frame B is defined as follows. Let n be the number of pixels in each of the blocks. V<sb>A1</sb>, V<sb>A2</sb>, ... V<sb>An</sb>is called the value (eg, luminance or chrominance) of the pixels of the block of frame A. V<sb>B1</sb>, V<sb>B2</sb>, ... V<sb>Bn</sb>is called the value of the corresponding pixels of the block of frame B. The square-mean DFD between the block of frame A and the block of frame B is expressed by Equation 1 below.

<maths num="1"><df><img file="KR100782829B1_D0001.tif" /></df></maths>

The above-described DFD-based algorithm is also applicable to motion vectors with sub-pixel accuracy related to the connection between sub-pixels, as used in high-performance video coders. A subpixel is a location between adjacent pixels. The interpolated subpixels are used to calculate the DFD. Therefore, no other changes are required to the DFD algorithm, except to use a predefined form of spatial interpolation when the reference pixel is not an integer. For example, a separable 9-tap FIR interpolation filter may be used for this purpose.

After steps 32 and 33 of Figure 4 are performed, all pixels in frame A and frame B are classified as "unconnected" or "connected". Because the DFD-based algorithm described above removes multiple connections from two or more pixels of frame B to one reference pixel of frame A, each "connected" pixel in frame A is correctly connected to one pixel in frame B. and vice versa.

Step 34 classifies the blocks of frame B as "uni-connected" or "unconnected" according to preferred embodiments of the present invention. If at least a fraction F of the pixels within a block of a frame are unconnected, then the block is a "unconnected" block; Otherwise, the block is a "single-connected" block. Since I-blocks require separate processing time, the fraction F has a value that reflects the tradeoff between image quality and processing time. The fraction F has in particular a value of at least 0.50 (eg within the range 0.50 to 0.60, 0.50 to 0.75, 0.60 to 0.80, 0.50 to 1.00, 0.30 to 1.00, 0.50 to less than 1). By examining the reference pixels of frame A to which pixels in the single connected block of frame B are connected, the matched block of frame A (referred to as "single connected block of frame A") for each single connected block of frame B can be determined. . The resulting single connected blocks of frames A and B constitute a set of matched pairs of single connected blocks, where each matched pair consists of the single connected blocks of frame B and the matched single connected block of frame A. A matched pair of single-connected blocks is denoted as the first and second single-connected blocks in frame A and frame B, respectively.

In step 35, according to preferred embodiments of the present invention, the first and second single connected blocks of the matched pair of single connected blocks are reclassified as unconnected if the following reclassification criteria are satisfied. V<sb>1</sb> and V<sb>2</sb>is called the pixel variance of the first and second single connected blocks, respectively. The pixel variance in a block is the square-mean deviation between the pixel values in that block and the average pixel value of that block. V<sb>MIN</sb>v<sb>1</sb> and V<sb>2</sb>denoted as the minimum value of Then, the square-mean DFD between the first and second blocks is fV<sb>MIN</sb>(where f is a real number between 0 and 1), the first and second single connected blocks are reclassified as unconnected blocks. For example, f can range from 0.4 to 0.6, 0.5 to 0.7, 0.4 to 0.75, 0.5 to 0.9, 0.4 to 1.00, and the like, among others. After step 35 is performed, classifying each block of frame B as "unconnected" or "connected" is complete.

In step 36, each unconnected block of frame B is categorized into a P-block or an I-block, according to preferred embodiments of the present invention. As described below, an I-block has an initial pixel value replaced by spatially interpolated values extracted from adjacent pixels outside the I-block. The difference between the initial pixel value of the I-block pixel and the spatially interpolated pixel value is the residual error of the interpolated I-block pixel. A block of residual error in all pixels within an I-block is called a residual error block of or associated with an I-block.

To determine whether an unconnected block is an I-block or a P-block, an interpolated I-block is formed, its residual error block is computed, and the sum of residual errors in the residual error block (S<sb>RES</sb>) is also calculated. S<sb>RES</sb>is also called "residual interpolation error". Residual errors are errors in the pixels of the residual error block. Also, forward and backward movements are performed on unconnected blocks. The sums of the absolute DFD values of the forward and backward motion compensation prediction errors are calculated. The minimum value (S) of the sums of the DFD absolute values of the forward and backward motion compensation prediction errors<sb>MC-MIN</sb>) is determined. S<sb>MC</sb><sb>-MIN</sb>is also called the "minimum motion compensation error" of unconnected blocks. The unconnected block is S<sb>RES</sb>go S<sb>MC</sb><sb>-MIN</sb>If it is not less than, it is classified as a P-block.

In step 37, according to preferred embodiments of the present invention, the I-blocks determined in step 36 are processed by spatial interpolation from the available adjacent pixels, and a residual error block associated with the interpolated I-block is generated. . Blocks in one frame may have a fixed size or a variable size. As will be described later, FIGS. 5-7 and 9 are for interpolation with a fixed block size, and FIG. 8 for interpolation with a variable block size, according to preferred embodiments of the present invention.

In step 38, the residual error block associated with the interpolated I-block is analyzed for compression of the relevant high-time frame by the EZBC 54 after the spatial analysis unit 53 of FIG. 2 is performed. It is overlaid on (i.e. located within) the relevant high-time frames related to frame pairs A and B. 7C, which will be described later, shows that the residual error block has a plurality of values near zero, and thus is suitable for efficient compression.

5 shows a frame comprising I-blocks, P-blocks, and single connected blocks. The I-blocks contain blocks 1-3, and the P-blocks and single connected blocks contain the remaining blocks comprising blocks 4-10. Each I-block has four possible contiguous blocks: an upper block, a lower block, a left block and a right block. In the interpolation algorithm used here, the blocks of a frame are processed according to the scan order, and only "available" blocks (i.e. previously processed I-blocks with pixel values, P-blocks with original data) , and/or single connected blocks) may be used for spatial interpolation. For example, using the left-to-right and top-to-bottom scan order for block 1 in FIG. 5, only adjacent blocks 4-5 are spatial interpolation of block 1 because neither block 2 nor block 3 are available. can be used for However, for block 2, after block 1 is interpolated, there are 4 adjacent blocks available for spatial interpolation of block 2, namely blocks 1 and 6-8. Similarly, after block 1 is interpolated, there are 4 adjacent blocks available for spatial interpolation of block 3, namely blocks 1 and 8-10.

Spatial interpolation is performed according to raster scanning rules, such as the left-to-right and top-to-bottom scanning rules described above. There are other interpolation functions based on the available adjacent blocks and their location. Fig. 6 shows the following notation: "u" for upper neighboring pixels, "lw" for lower neighboring pixels, "lf" for left neighboring pixels, and "r" for right neighboring pixels. , "in" represents interpolated pixel values in the I-block. Interpolation may be linear or non-linear, and a variety of different interpolation schemes may be used.

7A-7C (collectively referred to as "FIG. 7") illustrate a case where only one adjacent block is available. Assume that the 4x4 pixel size I block 40 of Fig. 7a is defined by column segments 41-44, and that in the adjacent upper block above block 40, column segment 45 is the only available neighbor. Exemplary pixel values shown for I-block 40 in FIG. 7A are initial values before spatial interpolation. The pixel values of the column segment 45 are used for spatial interpolation. For this case, the C-code of Table 1 may be used to perform spatial interpolation.

<tables id="1"><table><tgroup cols="1" xmlns="http://www.oasis-open.org/tables/exchange/1.0"><colspec align="left" colname="col1" colnum="1" colwidth="3150" /><tbody><row><entry align="left" colname="col1">for (i=0; i&lt;4; i++) for (j=0; j&lt;4; j++) in[i*4+j] = u[j];</entry></row></tbody></tgroup></table></tables>

7B shows the resultant interpolated values of the I-block 40 according to the execution result of the C-code of Table 1 above. FIG. 7C shows a residual error block determined by subtracting the interpolated pixel values of FIG. 7B from the initial pixel value of FIG. 7A. The residual error block shown in FIG. 7C is overlaid (ie, positioned) within the high-time frames associated with frame pairs A and B being analyzed for compression of the relevant high-time frame by the EZBC 54 of FIG. . 7A-7C have described an embodiment in which only the upper adjacent pixels are available for interpolation, but using the above-described upper adjacent pixels even when only the left, right or bottom adjacent pixels are available for interpolation. It can be similarly inferred from, or through appropriate coordinate rotation.

Tables 2 and 3 show the interpolation algorithm when two adjacent blocks are available. Table 2 shows the interpolated pixel values of in[0]...in[15] in a 4×4 I-block using the available adjacent pixels in the top and left positions according to the representation shown in FIG. 6 ( FIG. 6 ). The formulas for calculating the reference) are specified. Table 3 shows the C for calculating the interpolated pixel values of in[0]...in[15] in a 4×4 I-block using the available adjacent pixels in the upper and lower positions according to the representation shown in FIG. 6 . - The code is embodied.

<tables id="2"><table><tgroup cols="1" xmlns="http://www.oasis-open.org/tables/exchange/1.0"><colspec align="left" colname="col1" colnum="1" colwidth="11700" /><tbody><row><entry align="left" colname="col1">in[0]=(lf[0]+u[0])/2; in[1]=u[1]; in[2]=u[2]; in[3]=u[3]; in[4]=lf[1]; in[5]=(in[4]+in[1])/2; in[6]=in[2]; in[7]=in[3]; in[8]=lf[2]; in[9]=in[8]; in[10]=(in[9]+in[6])/2; in[11]=in[7]; in[12]=lf[3]; in[13]=in[12]; in[14]=in[13]; in[15]=(in[11]+in[14])/2</entry></row></tbody></tgroup></table></tables>

<tables id="3"><table><tgroup cols="1" xmlns="http://www.oasis-open.org/tables/exchange/1.0"><colspec align="left" colname="col1" colnum="1" colwidth="5063" /><tbody><row><entry align="left" colname="col1">for (i=0; i&lt;4; i++) { in[i]=u[i]; in[12+i]=lw[i]; in[4+i] = in[8+i] = (u[i]+lw[i])/2; }</entry></row></tbody></tgroup></table></tables>

Other embodiments where two adjacent blocks are available are derived similarly to the "up and left" or "up and down" adjacent cases described above with respect to Tables 2 and 3, respectively, or via appropriate coordinate rotation. can be induced.

Table 4 shows the interpolation algorithm when three adjacent blocks are available. Table 4 shows the interpolated pixel values ( 6) embodied the C-code for calculating.

<tables id="4"><table><tgroup cols="1" xmlns="http://www.oasis-open.org/tables/exchange/1.0"><colspec align="left" colname="col1" colnum="1" colwidth="11700" /><tbody><row><entry align="left" colname="col1">in[0]=(lf[0]+u[0])/2; in[1]=u[1]; in[2]=u[2]; in[3]=(u[3]+r[0])/2; in[4]=lf[1]; in[5]=(in[4]+in[1])/2; in[7]=r[1]; in[6]=(in[2]+in[7])/2; in[8]=lf[2]; in[9]=in[8]; in[11]=r[2]; in[10]=in[11]; in[12]=lf[3]; in[13]=in[12]; in[15]=r[3]; in[14]=in[15];</entry></row></tbody></tgroup></table></tables>

Other embodiments where three adjacent blocks are available may be derived similarly to the case of adjacent "up, left and right" above with respect to Table 4 above, respectively, or may be derived through appropriate coordinate rotation.

Table 5 shows the interpolation algorithm when four adjacent blocks are available. Table 5 shows the interpolated pixel values of in[0]...in[15] in a 4×4 I-block using the available adjacent pixels in the top, bottom, left and right positions according to the representation shown in FIG. 6 . The C-code for calculating the values (see FIG. 6) is specified.

<tables id="5"><table><tgroup cols="1" xmlns="http://www.oasis-open.org/tables/exchange/1.0"><colspec align="left" colname="col1" colnum="1" colwidth="11700" /><tbody><row><entry align="left" colname="col1">in[0]=(lf[0]+u[0])/2; in[1]=u[1]; in[2]=u[2]; in[3]=(u[3]+r[0])/2; in[4]=lf[1]; in[5]=(in[4]+in[1])/2; in[7]=r[1]; in[6]=(in[2]+in[7])/2; in[12]=(lf[3]+lw[0])/2; in[13]=lw[1]; in[14]=lw[2]; in[15]=(lw[3]+r[3])/2; in[8]=lf[2]; in[9]=(in[8]+in[13])/2; in[11]=r[2]; in[10]=(in[14]+in[11])/2</entry></row></tbody></tgroup></table></tables>

8 shows the case of a variable block size resulting from 5-level hierarchical variable size block matching in which the block size ranges from 4x4 to 64x64. In the example of Figure 8, I-blocks 11 and 12 are shown. Block 11 has a size of 8x8 pixels and block 12 has a size of 4x4 pixels. If the I-blocks 11 and 12 are processed by the left-to-right and top-to-bottom scanning order described above (ie block 11 is interpolated before block 12 is interpolated), block 12 ) will not be available for interpolation of block 11 . To simplify interpolation, block 11 is treated as four separate 4x4 I-blocks for interpolation purposes, so that spatial interpolation can be implemented as a fixed-block interpolation.

9A-9F (collectively referred to as "FIG. 9") illustrate a directional spatial interpolation scheme for determining pixel values of I-blocks according to a preferred embodiment of the present invention. 9A-9F show a 4x4 I-block 61 within a portion of a frame 60 . Part of the frame 60 comprises pixels P11 ... P99. I-block 61 includes pixels P22, P23, P24, P25, P32, P33, P35, P42, P43, P44, P45, P52, P53, P54 and P55. 9A-9F , all pixels that are not within the I-block 61 are neighbors of the pixels of the I-block 61 . The interpolation of the pixels of the I-block 61 is along one of the parallel lines having a fixed angle θ with the X axis, namely line 66 , as shown in FIG. 9A . Each of the figures in FIGS. 9B-9F shows embodiments with different θ values. For example, the θ value is predicted, and for convenience of explanation, it is assumed that each pixel is a square. Thus, θ=45° by line 66 diagonally passing through the opposite vertices of pixels P25, P34, P43 and P52 in FIG. 9A. Of course, if the pixels have a rectangular or non-rectangular shape, θ by line 66 in FIG. 9A will be different from 45 degrees. Note that here, θ and θ+180 represent the same set of parallel lines. Interpolation along each of these lines uses the pixel values of the nearest available neighbors on that line, where the available neighbors are neighbors with previously established pixel values. The directional interpolation scheme assumes that for each line of parallel lines at least one neighbor is always available.

FIG. 9B shows directional interpolation for parallel lines 63, 64, ..., 69 when θ=45°. The lines 63,64,...69 are called "direction lines". Since line 63 passes through pixel P22, line 63 has the following neighbors: P13 and P31 neighbors if both P13 and P31 are available; only P13 neighbors if P13 is available but P31 is not; or if P31 is available but P13 is not, it is used to determine the pixel value of pixel P22 based only on interpolation using P31 neighbors. Because line 64 goes through pixels P23 and P32, line 64 is only available if P14 and P41 are available and P14 and P41 neighbors are: P14 is available but P41 is not. P14 neighbor; or if P41 is available but P14 is not, it is used to determine the values of pixels P23 and P32 based on interpolation using only the P41 neighbor. Similarly, interpolation along lines 65, 66, 67, 68 and 69 is (P24, P33, P42), (P25, P34, P43, P52), (P35, P44, P53), (P45, P54) and (P55) are used to determine the pixel values .

Lines 67-69 indicate the possibility that nearest neighbors may be replaced. For example, line 68 has (P36, P27 and P18) and (P63, P72 and P81) neighbors at the opposite boundary of I-block 61 . In determining which of the (P36, P27 and P18) neighbors to use, the directional interpolation uses the pixel P36 if it is available because the pixel P36 is the nearest one of the (P36, P27 and P18) neighbors. If pixel P36 is not available, then directional interpolation uses pixel P27 if it is available because it is the nearest one of neighbors P27 and P18. If pixel P27 is not available, directional interpolation uses the remaining pixel P18 if available. If pixel P27 is not available, directional interpolation does not use any of the pixels P36, P27 and P18. Similarly, directional interpolation selects one of the neighboring pixels P63, P72 and P81 based on the available nearest neighbor criterion. Therefore, as a result of applying the criterion of the nearest neighbor, the directional interpolation along line 68 for determining the pixel values of pixels P45 and P54 is a combination of the following neighbors: P63 only, P72 only, P81 only, P63 and P36, P63 and P27, P63 and P18, P72 and P36, P72 and P27, P72 and P18, P81 and P36, P81 and P27, P81 and P18, P36 only, P27 only, P18 only.

A directional interpolation for linear interpolation along line 68 to determine pixel values of pixels P45 and P54 is shown next, assuming that both neighboring pixels P36 and P63 are available. 9B shows points Q0, Q1, Q2, Q3 and Q4 along line 68. The points Q0, Q1, Q2, Q3 and Q4 are located at the midpoints of the portions of line 68 lying at pixels P27, P36, P45, P54 and P63, respectively. Let D12, D13 and D14 represent the distances between point Q1 and points Q2, Q3, and Q4, respectively. F1214 and F1314 are said to represent D12/D14 and D13/D14, respectively. It is said that V36 and V63 represent pixel values in pixels P36 and P63, respectively. Then, the pixel values in the pixels P45 and P54 are (1-F1214)×V36+F1214×V63 and (1-F1314)×V36+F1314×V63, respectively.

Directional interpolation for linear interpolation along line 68 raises the question of how to perform the interpolation if neighboring pixel P36 is unavailable and neighboring pixel P27 is available. Assuming that V27 represents the pixel value of a pixel P27, V27 will replace V36 at every occurrence of V36 in the interpolation equation. However, the scope of the present invention includes three options for handling distance along line 68 .

The first option is to keep the F1214 and F1314 parameters in the interpolation formula, which is conceptually equivalent to using the point Q1 as a reference in measuring the distance even if pixel P36 is replaced by pixel P27 as the nearest neighbor available. In the first option, the pixel values at pixels P45 and P54 are (1-F1214)×V27+F1214×V63 and (1-F1314)×V27+F1314×V63, respectively.

A second option is to use the distance from point Q0 of line 68 starting at neighboring pixel P27. In the second option, D02, D03 and D04 are said to represent the distances between point Q0 and points Q2, Q3 and Q4, respectively. F0204 and F0304 are said to represent D02/D04 and D03/D04, respectively. Then, the pixel values of the pixels P45 and P54 are (1-F0204) x V27 + F0204 x V63 and (1-F0304) x V27 + F0304 x V63, respectively.

The third option is to use a compromise between the first and second options. Instead of using either (F1214 and F1314) or (F0204 and F0304) in the first and second options, (F1214,F0204)<sb>AVE</sb> and (F1314,F0304)<sb>AVE</sb> parameters are used. where (F1214,F0204)<sb>AVE</sb>is the weighted or unweighted average of F1214 and F0204, (F1314,F0304)<sb>AVE </sb>is the weighted or unweighted average of F1314 and F0304. Then, the pixel values of pixels P45 and P54 are respectively (1-(F1214, F0204)<sb>AVE</sb>)×V27 + (F1214,F0204)<sb>AVE</sb>×V63 and (1-(F1314,F0304)<sb>AVE</sb>)×V27 + (F1314,F0304)<sb>AVE</sb>×V63. If (F1214,F0204)<sb>AVE</sb> and (F1314,F0304)<sb>AVE</sb> If these are weighted averages, then irrespective of the distance of pixels P36 and P27 from points Q2 and Q3 along line 68 , the weighting of the pixels P36 on the image quality of I-block 61 along line 68 and external knowledge about the relative importance of P27.

9C-9F are similar to FIG. 9B except for the θ value. θ=90° of direction lines 71 to 74 in FIG. 9C . The value at pixels P22, P32, P42 and P52 is determined from interpolation along line 71 using a subset of neighboring pixels P12, P62, P72, P82 and P92. The values of pixels P23, P33, P43 and P53 are determined from interpolation along line 72 using a subset of neighboring pixels P13, P63, P73, P83 and P93. The values of pixels P24, P34, P44 and P54 are determined from interpolation along line 73 using a subset of neighboring pixels P14, P64, P74, P84 and P94. The values of pixels P25, P35, P45 and P55 are determined from interpolation along line 74 using a subset of neighboring pixels P15, P65, P75, P85 and P95.

In FIG. 9D , θ=135° of direction lines 81 to 87 . The value of pixel P52 is determined from interpolation along line 81 using a subset of neighboring pixels P41, P63, P74, P85 and P96. The value of pixels P42 and P53 is determined from interpolation along line 82 using a subset of neighboring pixels P31, P64, P75, P86 and P97. The values of pixels P32, P43 and P54 are determined from interpolation along line 83 using a subset of neighboring pixels P21, P65, P76, P87 and P98. The values of pixels P22, P33, P44 and P55 are determined from interpolation along line 84 using a subset of neighboring pixels P11, P66, P77, P88 and P99. The values of pixels P23, P34 and P45 are determined from interpolation along line 85 using a subset of P12, P56, P67, P78 and P89. The values of pixels P24 and P35 are determined from interpolation along line 86 using a subset of neighboring pixels P13, P46, P57, P68 and P79. The value of pixel P25 is determined from interpolation along line 87 using a subset of neighboring pixels P14, P36, P47, P58 and P69.

In FIG. 9E , θ=0° (or 180°) of direction lines 76 to 79 . The values of pixels P22, P23, P24 and P25 are determined from interpolation along line 76 using a subset of neighboring pixels P21, P26, P27, P28 and P29. The values of pixels P32, P33, P34 and P35 are determined from interpolation along line 77 using a subset of neighboring pixels P31, P36, P37, P38 and P39. The values of pixels P42, P43, P44 and P45 are determined from interpolation along line 78 using a subset of neighboring pixels P41, P46, P47, P48 and P49. The values of pixels P52, P53, P54 and P55 are determined from interpolation along line 79 using a subset of neighboring pixels P51, P56, P57, P58 and P59.

In FIG. 9F , θ=26.56° of direction lines 101-105 (ie, θ is the inverse tangent of 2/4). The values of pixels P22 and P23 are determined from interpolation along line 101 using a subset of neighboring pixels P13 and P14. The values of pixels P32, P33, P24 and P25 are determined from interpolation along line 102 using a subset of neighboring pixels P41 and P16. The values of pixels P42, P43, P34 and P35 are determined from interpolation along line 103 using a subset of neighboring pixels P51, P26, P27, P18 and P19. The values of pixels P52, P53, P44 and P45 are determined from interpolation along line 104 using a subset of neighboring pixels P61, P36, P37, P28 and P29. The values of pixels P54 and P55 are determined from interpolation along line 105 using a subset of neighboring pixels P71, P46, P47, P38 and P39.

9a to 9f show directional spatial interpolation characterized by all pixel values in an I-block determined through spatial interpolation along parallel directional lines. In contrast, Figures 7a-7c and Tables 1-5 show that all pixel values in an I-block are determined by the available nearest-neighbor spatial interpolation without using directional lines passing through the I-block used in the spatial interpolation. It shows the non-directional spatial interpolation characterized by Another spatial interpolation of I-block is hybrid spatial interpolation, which involves a combination of directional spatial interpolation and non-directional spatial interpolation. In hybrid spatial interpolation, at least one directional line is used for spatial interpolation of a portion of an I-block, and some pixel values of the I-block are available nearest neighbors without using a directional line passing through the I-block. It is determined through spatial interpolation. When directional spatial interpolation or hybrid spatial interpolation is used, the selected directional and hybrid mask must be coded and transmitted as side information. A short fixed Huffman code is used for this purpose in an embodiment of the present invention.

10 illustrates hybrid spatial interpolation according to an embodiment of the present invention. 10 shows pixels P25, P34, P43 and P52 (along line 121), pixels P35, P44 and P53 (along line 122), pixels P45 and P54 (along line 123), and pixels P45 and P54 (along line 124). ) direction lines 121-124 used for spatial interpolation to determine the values of pixel P55. However, the values of pixels P22, P23, P24, P32, P33 and P42 are not calculated in non-directional spatial interpolation using the top nearest neighbor pixels P12, P13, P14 and the left nearest neighbor pixels P21, P31 and P41. is determined by

As shown in the spatial interpolation examples described above with respect to FIGS. 6-10 and Tables 1-5 above, the values of the pixels of each I-block within a given frame are the available values associated with each I-block within the given frame. It is computed by spatial interpolation based on the values of the nearest neighboring pixels. A given pixel outside a particular I-block in a given frame is said to be a neighboring pixel associated with the I-block if the given pixel is close enough to an I-block that potentially contributes to the pixel value of the I-block by the spatial interpolation. is called

The discussion of determining pixel values of I-blocks by interpolation described above with reference to FIGS. 6-10 and Table 1-5 has focused on linear interpolation. However, the scope of the present invention includes any non-directional interpolation scheme that takes advantage of the relative importance of various neighboring pixels contributing to a pixel value within an I-block.

11 illustrates a computer system 90 for processing I-blocks used in motion compensated temporal filtering (MCTF) in accordance with embodiments of the present invention. The computer system 90 includes a processing unit 91 , an output device 93 connected to the processing unit 91 , and memory devices 94 and 95 connected to the processing unit 91 , respectively. The input device 92 may be a keyboard, a mouse, or the like. The output device 93 may be a printer, magnetic tape, an internal hard disk or disk array, a removable hard disk, a floppy disk, an information network, or the like. The memory devices 94 and 95 include a hard disk, a floppy disk, a magnetic tape, an optical storage medium such as a compact disc (CD) or a digital video disc (DVD), a dynamic random access memory (DRAM), and a read-only memory (ROM). ), and so on. The memory device 95 includes computer code 97 . The computer code 97 comprises an algorithm for the processing of I-blocks used for motion compensated temporal filtering (MCTF). The processing unit 91 executes the computer code 97 . The memory device 94 contains input data 96 . The input data 96 includes the input required by the computer code 97 . The output device 93 displays the result from the computer code 97 . One or both memory devices 94 and 95 (or one or more additional memory devices not shown in FIG. 11 ) may implement computer readable program code including the computer code 97 and/or Or it may be used as a computer-usable medium (or computer-readable medium or program storage device) having computer-readable program code having other data embodied therein. In general, a computer program product (or alternatively an article or product) of the computer system 90 may include a computer-usable medium (or the program storage device).

Although the computer system 90 is shown as a specific hardware or software configuration in FIG. 11, other types of hardware or software configuration known to those skilled in the art may be used for purposes related to the specific computer system 90 of FIG. have. For example, the memory devices 94 and 95 may be parts of a single memory device rather than individual memory devices.

The embodiments of the present invention described so far are illustrative, and those of ordinary skill in the art to which the present invention pertains can understand that the present invention can be implemented in a modified form without departing from the essential characteristics of the present invention. will be. Therefore, the disclosed embodiments are to be considered in an illustrative rather than a restrictive sense. The scope of the present invention is indicated in the claims rather than the foregoing description, and all differences within the scope equivalent thereto should be construed as being included in the present invention.

1 is a diagram illustrating a video coding system including a Motion Compensated Temporal Filtering (MCTF) processing unit according to preferred embodiments of the present invention.

2 is a diagram illustrating an MCTF process performed by the MCTF processing unit of FIG. 1 according to preferred embodiments of the present invention.

3 is a flowchart illustrating a method of using I-blocks of high time frames generated by the MCTF process of FIG. 2 according to preferred embodiments of the present invention;

Fig. 4 is a diagram illustrating the connection between pixels of successive frames according to preferred embodiments of the present invention.

5 is a diagram illustrating one frame with I-blocks and P-blocks according to preferred embodiments of the present invention.

6 is a diagram illustrating a notation used for spatial interpolation of one I-block according to preferred embodiments of the present invention.

7A to 7C are diagrams illustrating spatial interpolation of an I-block when only one neighboring block is available according to preferred embodiments of the present invention.

8 is a diagram illustrating I-blocks with variable block size in a frame according to preferred embodiments of the present invention.

9A to 9F are diagrams illustrating directional spatial interpolation of an I-block according to preferred embodiments of the present invention.

10 is a diagram illustrating hybrid spatial interpolation of an I-block according to preferred embodiments of the present invention.

11 is a diagram illustrating a computer system for processing I-blocks used in MCTF according to preferred embodiments of the present invention.