Motion compensated digital video signal processing

[0002] RELATED APPLICATION/PATENTS

[0003] In an earlier filed U.S. Application Ser. No. 08,800,880, entitled “Adaptive Video Coding Method,” filed in the name of Huifang Sun and Anthony Vetro, now U.S. Pat. No. 5,790,196, a system was disclosed for coding video signals for storage and/or transmission using joint rate control for multiple video objects based on a quadratic rate distortion model.

[0004] In a second application, Ser. No. 08/896,861, entitled “Improved Adaptive Video Coding Method,” Sun and Vetro described an improved method of target distribution and introduction of a tool to take into account object shape in the rate control process. The disclosures of these previously-filed applications are incorporated by reference in the present application, particularly insofar as they describe the general configurations of encoding and decoding, including motion estimation and motion compensation functions in such systems.

[0005] For an overall understanding of general techniques involved in encoding and decoding video image information, reference should be made to the “MPEG-4 Video Verification Model Version 5.0”, prepared for the International Organization for Standardization by the Ad hoc group on MPEG-4 video VM editing, paper Number MPEG 96/N1469, November 1996, the contents of which are herein incorporated by reference.

[0006] This invention relates to encoding and decoding of complex video image information including motion components which may be encountered, for example, in multimedia applications, such as video-conferencing, video-phone, and video games. In order to be able to transfer complex video information from one machine to another, it is often desirable or even necessary to employ video compression techniques. One significant approach to achieving a high compression ratio is to remove the temporal and spatial redundancy which is present in a video sequence. To remove spatial redundancy, an image can be divided into disjoint blocks of equal size. These blocks are then subjected to a transformation (e.g., Discrete Cosine Transformation or DCT), which decorrelates the data so that it is represented as discrete frequency components. With this representation, the block energy is more compact, hence the coding of each block can be more efficient. Furthermore, to achieve the actual compression, two-dimensional block elements are quantized. At this point, known run-length and Huffman coding schemes can be applied to convert the quantized data into a bit-stream. If the above process is applied to one block independent of any other block, the block is said to be intra-coded. On the other hand, if the block uses information from another block at a different time, then the block is said to be inter-coded. Inter-coding techniques are used to remove temporal redundancy. The basic approach is that a residual block (or error block) is determined based on the difference between the current block and a block in a reference picture. A vector between these two blocks is then determined and is designated as a motion vector. To keep the energy in the residual block as small as possible, block-matching algorithms (BMAs) are used to determine the block in the reference picture with the greatest correlation to the current block. With the reference block locally available, the current block is reconstructed using the motion vector and the residual block.

[0007] For the most part, video coding schemes encode each motion vector differentially with respect to its neighbors. The present inventors have observed that a piecewise continuous motion field can reduce the bit rate in this case. Hence, a rate-optimized motion estimation algorithm has been developed. The unique features of this proposal come from two elements: (1) the number of bits used for encoding motion vectors is incorporated into the minimization criterion, and (2) rather than counting the actual number of bits for motion vectors, the number of motion vector bits is estimated using the residues of the neighboring blocks. With these techniques, the bit-rate is lower than in prior encoders using full-search motion-estimation algorithms. In addition, the computational complexity is much lower than in a method in which rate-distortion is optimized. The resulting motion field is a true motion field, hence the subjective image quality is improved as well.

[0008] If we disregard for a moment the advantages that are achieved in terms of coding quality and bit rate savings, and only concentrate on the improvements in subjective image quality, it can be demonstrated that the resulting true motion field can be used at the decoder, as well, in a variety of other ways. More specifically, it has been found that the true motion field can be used to reconstruct missing data, where the data may be a missing frame and/or a missing field. In terms of applications, this translates into frame-rate up-conversion, error concealment and interlaced-to-progressive scan rate conversion capabilities, making use of the true motion information at the decoder end of the system.

[0009] Frame-Rate Up-Conversion. The use of frame-rate up-conversion has drawn considerable attention in recent years. To accomplish acceptable coding results at very low bit-rates, most encoders reduce the temporal resolution, i.e., instead of targeting the full frame rate of 30 frames/sec (fps), the frame rate may be reduced to 10 fps, which would mean that 2 out of every 3 frames are never even considered by the encoder. However, to display the full frame rate at the decoder, a recovery mechanism is needed. The simplest mechanism is to repeat each frame until a new one is received. The problem with that interpolation scheme is that the image sequence will appear very discontinuous or jerky, especially in areas where large or complex motion occurs. Another simple mechanism is linear-interpolation between coded frames. The problem with this mechanism is that the image sequence will appear blurry in areas of motion, resulting in what is referred to as ghost artifacts.

[0010] From the above, it appears that motion is the major obstacle to image recovery in this manner. This fact has been observed by a number of prior researchers and it has been shown that motion-compensated interpolation can provide better results. In one approach, up-sampling results are presented using decoded frames at low bit-rates. However, the receiver must perform a separate motion estimation just for the interpolation. In a second approach, an algorithm that considers multiple motion is proposed. However, this method assumes that a uniform translational motion exists between two successive frames. In still a third approach, a motion-compensated interpolation scheme is performed, based on an object-based interpretation of the video. The main advantage of the latter scheme is that the decoded motion and segmentation information is used without refinement. This may be attributed to the fact that the object-based representation is true in the “real” world. However, a proprietary codec used in that approach is not readily available to all users.

[0011] The method proposed in the present case is applicable to most video coding standards in that it does not require any proprietary information to be transmitted and it does not require an extra motion estimation computation. The present motion-compensated interpolation scheme utilizes the decoded motion information which is used for inter-coding. Since the current true motion estimation process provides a more accurate representation of the motion within a scene, it becomes possible to more readily reconstruct information at the decoder which needs to be recovered before display. Besides quality, the major advantage of this method over other motion compensated interpolation methods is that significantly less computation is required on the decoder side.

[0012] Error Concealment. True motion vector information can also be employed to provide improved error concealment. In particular, post-processing operations at the decoder can be employed to recover damaged or lost video areas based on characteristics of images and video signals.

[0013] Interlaced-to-Progressive Scan Conversion. In addition to the above motion-compensated interpolation method, a related method for performing interlaced-to-progressive scan conversion also becomes available. In this scenario, rather than recovering an entire frame, an entire field is recovered. This type of conversion is necessary for cases in which a progressive display is intended to display compressed inter-frame, and motion-compensated inter-frame.

[0014] Intraframe methods. Simple intraframe techniques interpolate a missing line on the basis of two scanned lines which occur immediately before and after the missing line. One simple example is the “line averaging” which replaces a missing line by averaging the two lines adjacent to it. Some other improved intraframe methods which use more complicated filters or edge information have been proposed by M. H. Lee et al. (See “A New Algorithm for Interlaced to Progressive Scan Conversion Based on Directional Correlations and its IC Design,” IEEE Transactions on Consumer Electronics, Vol. 40, No. 2, pp. 119-129, May 1994). However, such intraframe techniques cannot predict information which is lost from the current field, but which appears in neighboring fields.

[0015] Interframe techniques take into account the pixels in the previous frame in the interpolation procedure. One simple and widely-adopted method is the field staying scheme which lets I(m,2n+((t−1) mod 2),t)=I(m,2n+((t−1) mod2), t−1). Non-motion-compensated approaches, which apply linear or nonlinear filters, are fine for stationary objects, but they result in severe artifacts for moving objects.

[0016] For moving objects, it has been found that motion compensation should be used in order to achieve higher quality. Some motion compensated de-interlacing techniques have been proposed. For example, it has been shown that motion compensated de-interlacing methods are better than the intraframe methods and non-motion-compensated interframe methods (see Lee et al., “Video Format Conversions between HDTV Systems,” IEEE Transactions on Consumer Electronics, Vol. 39, No. 3, pp. 219-224, August. 1993).

[0017] The system disclosed by the present inventors utilizes an accurate motion estimation/compensation algorithm so it is classified as a motion-compensated interframe method. The interlaced-to-progressive scan conversion procedure contains two parts: (1) a motion-based compensation, and (2) a generalized sampling theorem. The motion-based compensation essentially determines a set of samples at a time 2t, given samples at 2t−1 and 2t+1. In general, these determined sets of samples will not lie on the image grid at time 2t, since the motion vector between 2t−1 and 2t+1 is arbitrary. Therefore, a generalized sampling theorem is used to compute the missing samples at the grid points given the motion compensated samples and the samples which already exist. Formally, this can be expressed as: first, find {I(m+Δ_x,2n+Δ_y,2t)} given {I(m,2n−1,2t−1)} and {I(m,2n+1,2t+1)}, then find {I(m,2n+1,2t)} given {I(m,2n,2t)} and {I(m+Δ_x,2n+Δ_y,2t)}.

[0018] While the invention will be described hereinafter in terms of a preferred embodiment and one or more preferred applications, it will be understood by persons skilled in this art that various modifications may be made without departing from the actual scope of this invention, which is described hereinafter with reference to the drawing.

[0019] In accordance with a further aspect of the present invention, a method of image data interpolation comprises decoding true motion vector data associated with blocks of digitally encoded image information, with the true motion vector data being dependent in part on neighboring image block proximity weighting factors. The method further comprises interpolating from the supplied picture information, image sequence signal data corresponding to intermediate image time intervals absent from the supplied picture information, the absent image time intervals corresponding to intermediate image information occurring during the intermediate image time intervals in sequence between supplied image time intervals associated with the supplied picture information. The interpolation comprises the steps of constructing image pixels for image blocks in each intermediate image time interval, based upon corresponding pixels in corresponding blocks in the supplied picture information which occur immediately before and after the intermediate image time interval, by distributing to constructed image pixels a fractional portion of image intensity difference information between the corresponding pixels occurring before and after the intermediate time to produce averaged intensity pixels for the intermediate image time interval. Thereafter, each constructed image pixel in each intermediate time interval is associated with a corresponding true motion vector equal in magnitude to a fractional part of the true motion vector information associated with the block in which the corresponding pixel is located in a reference supplied time interval, the fractional part being determined according to the number of intermediate image time intervals inserted between supplied time intervals. Each constructed, averaged intensity pixel is then associated with a spatial location in the intermediate image time interval according to the fractional part of the corresponding decoded true motion vector.

[0020] In the drawing,

[0021] FIG. 1 is a block diagram of a portion of an encoder adapted for use in connection with the present invention;

[0022] FIG. 2 is a block diagram of a portion of an encoder of the same general type as is illustrated in the above-mentioned first Sun and Vetro application;

[0023] FIG. 3 is a block diagram of a portion of a video decoder adapted for use in connection with the present invention;

[0024] FIG. 4 is an illustration which is helpful in understanding terminology used in connection with the frame-rate up-conversion process, using transmitted motion information in accordance with one aspect of the present invention;

[0025] FIG. 5 is schematic illustration of certain aspects of motion interpolation as employed in a motion based de-interlacing process according the another aspect of the invention;

[0026] FIG. 6 is a schematic illustration of certain aspects of the use of a generalized sampling theorem in connection with motion-based de-interlacing according to the present invention;

[0027] FIG. 7 is a schematic illustration which is helpful in understanding a technique for accomplishing interlaced to progressive scan conversion in a system employing the present invention; and

[0028] FIG. 8 is a pictorial representation helpful in understanding principals of block motion compensation.

[0029] In the video encoder shown in block diagram form in FIG. 1, a digital video signal representing a sequence of images 20, comprising spatially arranged video blocks 20A, 20B, 20C, etc., each made up of individual image pixels (or pels)—see FIG. 7—is supplied as a signal input to the video encoder. The video image information is supplied in a conventional sequence of luminance and chrominance information.

[0030] In accordance with the present invention, as will be described more fully below, the incoming digital video signal is supplied to a true motion estimation processor 22 to determine true motion vectors TMV representative of the “best match” between, for example, a block of the current frame and a “corresponding” block of a previous frame as illustrated in FIG. 8. The processor 22 provides an appropriate motion compensated prediction for the video signal. “Difference image” information is then subjected to a Discrete Cosine Transformation (DCT) 24 and the transformed information is subjected to quantization (Q) 26, each of which operations is conventional. Quantized transform coefficients and quantizer indicator information are supplied to a variable length coding (VLC) encoder such as the general arrangement shown in FIG. 2. The quantized transform coefficients are subjected to Inverse Quantization (IQ) 28 and then to Inverse Discrete Cosine Transformation (IDCT) 30. The resulting information is coupled to a frame memory 32 to provide a delay. Image information from a current image and a frame delayed image from frame memory 32 are compared and processed, as will be explained below, to produce true motion vector information for application in accordance with the present invention at the decoder of a system (see FIG. 3). An encoder arrangement of the general type shown in FIG. 2, but not specifically directed to providing true motion vectors, is described in greater detail in the above-identified patent of Sun and Vetro, the disclosure of which is incorporated herein by reference.

[0031] Algorithms for computing motion flow can be divided into two categories; those for removing temporal redundancy and those for tracking physical motion.

[0032] The first set of motion estimation algorithms is aimed at removing temporal redundancy in the video compression process. In motion pictures, similar scenes exist in a frame and a corresponding previous frame. In order to minimize the amount of information to be transmitted, the MPEG video coding standards code the displaced difference block instead of the original block. For example, assume a block in a current frame is similar to a displaced block in a previous frame. (See for example, FIG. 5 showing two odd fields and an intermediate even field in an interlaced system, with the “similar” block shown by the dashed line outline). A motion prediction vector together with a residue (difference) is coded. Since an achieved compression ratio will depend on removal of redundancy, the displacement vector corresponding to minimal displaced frame difference (DFD) is often used in prior systems.

[0033] A second type of motion estimation algorithm aims at accurately tracking the physical motion of features in video sequences. A video sequence arises from putting a three dimensional (3D) real world onto a series of 2D images. When objects in the 3D real world move, the brightness (pixel intensity) of the 2D images changes correspondingly. The 2D projection of the movement of a point in the 3D real world will be referred to herein as the “true motion.” Computer vision, whose goal is to identify the unknown environment via the moving camera, is one of the many potential applications of true motion information.

[0034] Many existing motion estimation algorithms attempt to optimize the search for a suitable or best motion vector in the rate-distortion sense. Often, a complex scheme results and the motion vectors do not correspond to the true physical motion within the scene.

[0035] In most video compression algorithms, there is a tradeoff among picture quality, compression ratio and computational cost. Generally speaking, the lower the compression ratio, the better the picture quality.

[0036] In high quality video compression (e.g. video broadcasting), quantization scales are usually low. Therefore, the number of bits available for an inter frame residual block B_iresis dominant with regard to the total bit rate B_total. Until recently, it was generally believed that use of a smaller displaced frame difference (DFD or mean residue) would result in fewer bits to code the residual block, and thus a smaller total bit rate. Hence, the minimal DFD criterion is still widely used in BMAs (block matching algorithms) and, the motion vector for any particular block is the displacement vector which carries the minimal DFD. That is: $\begin{array}{cc}\mathrm{motion}\mathrm{vector}=\arg \underset{\stackrel{\rightharpoondown }{v}}{\min }\left\{\mathrm{DFD}\left(\stackrel{\rightharpoondown }{v}\right)\right\}& \left(1\right)\end{array}$

[0037] However, it has been observed that full-search BMAs are computationally too costly for a practical real-time application, usually do not produce the true motion field, which could produce better subjective picture quality, and generally cannot produce the optimal bit rate for very low bit rate video coding standards.

[0038] In most video coding standards, motion vectors are differentially encoded, therefore it is not always true that a smaller DFD will result in a reduced bit rate. The reason is that the total number of bits, which includes the number of bits for interframe residues, also includes the number of bits for coding motion vectors. Conventional BMAs treat the motion estimation problem as an optimization problem on DFD only, hence they suffer from the high price of the differential coding of motion vectors with large differences. The smaller the difference, the less bits that are required. A rate-optimized motion estimation algorithm such as is shown below, should account for the total number of bits: $\begin{array}{cc}\begin{array}{c}{\left\{v_i\right\}}_{i=1}^n=\arg \underset{\left\{\stackrel{\rightharpoondown }{v_1}\right\}}{\min }\{\mathrm{bits}\left({\mathrm{DFD}}_1\left(\stackrel{\rightharpoondown }{v_1}\right),Q_1\right)+\mathrm{bits}\left(\Delta {\stackrel{\rightharpoondown }{v}}_1\right)+\\ \mathrm{bits}\left({\mathrm{DFD}}_2\left({\stackrel{\rightharpoondown }{v}}_2\right),Q_2\right)+\mathrm{bits}\left(\Delta {\stackrel{\rightharpoondown }{v}}_2\right)+\dots +\\ \mathrm{bits}\left({\mathrm{DFD}}_n\left({\stackrel{\rightharpoondown }{v}}_n\right),Q_n\right)+\mathrm{bits}\left(\Delta {\stackrel{\rightharpoondown }{v}}_n\right)\}\end{array}& \left(2\right)\end{array}$

[0039] where {right arrow over (v)}_iis the motion vector of block i, Δ{right arrow over (v)}_i={right arrow over (v)}_i−{right arrow over (v)}_i−1, DFD_i({right arrow over (v)}_i) represents the DFD of block i, and bits(DFD_i({right arrow over (v)}_i),Q_i) is the number of bits required for this frame difference.

[0040] Spatial Correlation Technique.

[0041] It has been found that the true motion field may be considered piecewise continuous in the spatial domain. Therefore, the motion vectors can be more dependably estimated if the global motion trend of an entire neighborhood is considered, as opposed to that of one feature block itself. This approach enhances the chance that a singular and erroneous motion vector may be corrected by its surrounding motion vectors. For example, assume that there is an object moving in a certain direction and a tracker fails to track its central block due to noise, but successfully tracks its surrounding blocks. When a smoothness constraint is applied over the neighborhood, the true motion of the central block can be recovered.

[0042] Spatial/Temporal Correlation Technique.

[0043] The true motion field may also be considered to be piecewise continuous in the temporal domain. That is, assuming that the motion of each block is much smaller than the size of the block, then the motion field is piecewise continuous in the temporal domain. Therefore, motion fields may not only be considered to be piecewise continuous in the spatial domain (2D) but also piecewise continuous in the temporal domain (1D). The initial search area for matching thus can be reduced by exploiting correlations of motion vectors between spatial and temporal adjacent blocks.

[0044] A piecewise continuous motion field is advantageous in reducing the bit rate for differentially encoded motion vectors. Hence, a “true” motion tracker based on a neighborhood relaxation approach offers an effective approach for rate-optimized motion estimation. In the context of neighborhood relaxation, Eq. (2) can be written as: $\begin{array}{cc}\begin{array}{c}\mathrm{motion}\mathrm{of}{B}_i\approx \arg \underset{\stackrel{\rightharpoondown }{v}}{\min }\left\{\frac{{\stackrel{.}{\alpha }}_1}{Q_i}{\mathrm{DFD}}_i\left(\stackrel{\rightharpoondown }{v}\right)+{\stackrel{.}{\alpha }}_2\Vert \Delta \stackrel{\rightharpoondown }{v}\Vert \right\}\\ \approx \arg \min \left\{{\mathrm{DFD}}_i\left(\stackrel{\rightharpoondown }{v}\right)+\beta \Vert \Delta \stackrel{\rightharpoondown }{v}\Vert \right\}.\end{array}\mathrm{where}\beta ={\stackrel{.}{\alpha }}_2{Q}_i/{\stackrel{.}{\alpha }}_1& \left(3\right)\end{array}$

[0045] The coefficients α₁and α₂are selected to provide a desired approximation for the influence of neighboring blocks on the motion vector.

[0046] Assume that B_jis a neighbor of B_i, {right arrow over (v)}_jis the optimal motion vector, and that DFD_j({right arrow over (v)}) increases as {right arrow over (v)} deviates from {right arrow over (v)}*_jaccording to $\begin{array}{cc}{\mathrm{DFD}}_j\left(\stackrel{\rightharpoondown }{v}\right)\approx {\mathrm{DFD}}_j\left({\stackrel{\rightharpoondown }{v}}_j^{*}\right)+{\rm Y}\left|\right|\stackrel{\rightharpoondown }{v}-{\stackrel{\rightharpoondown }{v}}_j^{*}\left|\right|,& \left(4\right)\\ \mathrm{or},& \\ \left|\right|\stackrel{\rightharpoondown }{\Delta v}\left|\right|=\left|\right|\stackrel{\rightharpoondown }{v}-{\stackrel{\rightharpoondown }{v}}_j^{*}\left|\right|\approx {{\rm Y}}^{-1}\left({\mathrm{DFD}}_j\left(\stackrel{\rightharpoondown }{v}\right)-{\mathrm{DFD}}_j\left({\stackrel{\rightharpoondown }{v}}_j^{*}\right)\right).& \left(5\right)\end{array}$

[0047] Substituting Eq. (5) into Eq. (3), $\begin{array}{cc}\begin{array}{c}\mathrm{motion}\mathrm{of}{B}_i\approx \arg \underset{\stackrel{\rightharpoondown }{v}}{\min }\{{\mathrm{DFD}}_i\left(\stackrel{\rightharpoondown }{v}\right)+\\ \mu \sum _{B_j\in N\left(B_i\right)}({\mathrm{DFD}}_j\left(\stackrel{\rightharpoondown }{v}\right)-\left({\mathrm{DFD}}_j\left({\stackrel{\rightharpoondown }{v}}_j^{*}\right)\right)\},\end{array}& \left(6\right)\end{array}$

[0048] where N(B_i) means the neighboring blocks of B_i. (μ=β/γ=α₂Q Ĺ/γα₁) Here we can use an idea commonly adopted in relaxation methods, i.e., we can let {right arrow over (v)}_j* (and DFD_j({right arrow over (v)}_j)*) remain constant during the block Ĺ updating of the neighborhood relaxation. Therefore, they can be dropped from Eq. (7), resulting in $\begin{array}{cc}\mathrm{motion}\mathrm{of}{B}_i=\arg \underset{\stackrel{\rightharpoondown }{v}}{\min }\{{\mathrm{DFD}}_i\left(\stackrel{\rightharpoondown }{v}\right)+\mu \sum _{B_j\in N\left(B_i\right)}({\mathrm{DFD}}_j\left(\stackrel{\rightharpoondown }{v}\right)\}& \left(8\right)\end{array}$

[0049] If a particular motion vector results in the DFDs of the center block and its neighbors dropping, then it is selected to be the motion vector for that block for the encoder. That is, when two motion vectors produce similar DFDs, the one that is much closer to the neighbors, motion will be selected. The motion field produced by this method will be smoother than that of Eq. (1).

[0050] The above approach will be inadequate for non-translational motion, such as object rotation, zooming, and approaching. For example, assume an object is rotating counterclockwise. Because Eq. (8) assumes the neighboring blocks will move with the same translational motion, it may not adequately model the rotational motion. Since the neighboring blocks may not have uniform motion vectors, a further relaxation on the neighboring motion vectors is introduced; that is $\begin{array}{cc}\begin{array}{c}\mathrm{motion}\mathrm{of}{B}_i=\arg \min \{\mathrm{DFD}\left(B_i,\stackrel{\rightharpoondown }{v}\right)+\\ \sum _{B_j\in N\left(B_i\right)}({\mu }_{i,j}\times \mathrm{DFD}\left(B_j,\stackrel{\rightharpoondown }{v}+\stackrel{\rightharpoondown }{\delta }\right)\}\end{array}& \left(9\right)\end{array}$

[0051] where a small δ is incorporated to allow local variations of motion vectors among neighboring blocks due to the non-translational motions, and μ_i,jis the weighting factor for different neighboring blocks. The shorter the distance between B_iand B_j, the larger will be μ_i,j. Also, the larger the Q_i, the larger the μ_i,j. In particular, we use the 4 nearest neighbors with higher weighting for DFD's closer to the center. The inclusion of the δ^→ vector allows reasonable tracking of more complex motion such as rotation, zooming, shearing, and the like. Neighborhood relaxation will consider the global trend in object motion as well as provide some flexibility to accommodate non-translational motion. Local variations δ among neighboring blocks of Eq. (9), are included in order to accommodate those other (i.e., non-translational) affine motions such as (a) rotation, and (b) zooming/approaching.

[0052] Referring to FIG. 3, at the decoding end of the system, a received signal bitstream is provided to a Variable Length (VLC) Decoder 38 and the output of Decoder 38 is coupled to an Inverse Quantizer (IQ) 40. The True Motion Vector (TMV) information provided by the encoder (FIG. 1) in accordance with the present invention is extracted and is supplied to motion compensation predictor 42. The main signal output of VLD 38/IQ 40 is subjected to Inverse Discrete Cosine Transformation (IDCT) 44 and is combined at adder 46 with an output from motion compensation block 42. The combined output from adder 46 is supplied to a frame memory 48, the output of which is supplied to remaining post processing stages of the information processing receiver for post-processing to produce a desired image on a display. The True Motion Vector information available at the decoder is also supplied to the post-processing stage 50 to accomplish, for example, a desired frame rate up-conversion or interlaced to progressive scan as explained below.

[0053] Frame-Rate Up-Conversion

[0054] Referring to the schematic diagram of FIG. 4 of the drawing, if image block B_imoves v_ifrom frame F_t−1to frame F_t+, then it is likely that block B_imoves v_i/2 from frame F_t−1to frame F_ti.e., as depicted in FIG. 4. The basic technique of motion-based frame-rate up-conversion is to interpolate frame F_tbased on frame F_t−1, frame F_t+1, and block motion vectors {v_i} can be stated as follows: $\begin{array}{cc}\tilde{I}\left(\overrightarrow{p}-\frac{{\overrightarrow{v}}_i}{2},t\right)=\frac{1}{2}\left\{I\left(\overrightarrow{p}-{\overrightarrow{v}}_i,t-1\right)+I\left(\overrightarrow{p},t+1\right)\right\}\forall \overrightarrow{p}\in B_i& \left(10\right)\end{array}$

[0055] where {right arrow over (p)}=[x,y]⁹indicates the pixel location, I(p,{right arrow over (t)}) means the intensity of the pixel [x,y] at time t, and Ĩ({right arrow over (p)},t)

[0056] means the reconstructed intensity of the pixel [x,y] at time t and v_iis the motion vector of block B_i.

[0057] Note that the more accurate the motion estimation, v_i/2, the smaller the reconstruction error, Σ∥I(p,t)−I(p,t)∥, and the higher the quality of the motion based interpolation. Therefore, one possible technique of frame-rate up-conversion using transmitted motion is to encode F_t−1, F_t+1, . . . with {2v_i} where v_iis the motion vector of B_ifrom F_tto F_t+1. The reconstruction error will be minimized, but the rate-distortion curves may not be optimized.

[0058] We can show that Eq. (9) captures the true movement of the block in the scene more accurately than Eq. (1) does. Hence, it is most likely that v_i/2 using Eq. (9) is more accurate than v_i/2 using Eq. (1).

[0059] When a block B_iis coded as the INTRA block (no motion compensation), it usually implies an uncovered region (see FIG. 4). Hence,

[0060] Ĩ(p,t)=Ĩ(p,t+1)∀p ∈B_i  (11)

[0061] When I(p,t) has never been assigned to any value by Eq. (10) and Eq. (11), it usually implies an occluded region. As a result,

[0062] Ĩ(p,t) Ĩ(p,t−1)  (12)

[0063] For the more general problem of interpolating from F_t+nour method can be summarized as follows: $\begin{array}{c}\tilde{I}\left(\overrightarrow{p},t\right)=\sum _{\left\{B_i\right\}}w\left(\overrightarrow{p},{\overrightarrow{p}}_i+\frac{n{\overrightarrow{v}}_i}{m+n}\right)(I\left(\overrightarrow{p}-\frac{m{\overrightarrow{v}}_i}{m+n},t-m\right)+\\ \left(I\left(\overrightarrow{p}+\frac{n{\overrightarrow{v}}_i}{m+n},t+n\right)\right)\end{array}$ $W\left(\overrightarrow{p},t\right)=\sum _{\left\{B_i\right\}}2w\left(\overrightarrow{p},{\overrightarrow{p}}_i+\frac{n{\overrightarrow{v}}_i}{m+n}\right)$ $\tilde{I}\left(\overrightarrow{p},t\right)=\{\frac{I\left(\overrightarrow{p},t\right)/W\left(\overrightarrow{p},t\right)\mathrm{if}W\left(\overrightarrow{p},t\right)\ne 0}{I\left(\overrightarrow{p},t-1\right)\mathrm{if}W\left(\overrightarrow{p},t\right)=0}$

[0064] where {right arrow over (v)}_iis the movement of B_ifrom frame F_t−mto frame F_t+n, {right arrow over (P)} is the coordinate of Bi, and w(*,*) is the window function. v₁=0 when B_iis INTRA-coded, w(*,*) equals zero when {right arrow over (p)} is outside the B_i. In order to reduce the block artifacts, the weighting value of w(*,*) could be similar to the coefficients defined for overlapped block motion compensation (OBMC).

[0065] As stated above, the present arrangement is particularly suited for use in connection with interlaced-to-progressive scan conversion (see FIGS. 6 and 7). The first step is to perform true motion-based compensation at the video decoder (See FIG. 3) and obtain a missing set of samples on the 2t plane, and the second step is to use these samples and the samples which exist for the preceding field to determine the samples for the missing field (See FIG. 6). Some issues regarding motion-based compensation are discussed first. Then, our use of the generalized sampling theorem is explained. Finally, a variety of different scenarios are considered so that the two steps can be put together to achieve a practical scan conversion scheme that yields a high quality output.

[0066] Prior methods are known which utilize a 3D recursive-search block matcher to estimate motion up to ¼ to ½ pixel accuracy. The present method provides even higher accuracy using its generalized sampling theorem. The high precision TMT vertically integrates two parts: (1) a matching-based TMT as the base, and (2) a gradient-based motion vector refinement. Gradient-based approaches are accurate at finding motion vectors less one pixel resolution.

[0067] Most previous methods use causal information (never use the next fields). They perform motion estimation based on the current field information. On the other hand, the present method uses non-causal information. The motion estimation is performed making use of the previous field and the next field. By assuming that the motion of a block is almost linear over a very small period of time, we can linearly interpolate the motion vectors related to the current field. In addition, because the information from previous and next fields is available, the non-grid pixels of the current field are bi-directionally interpolated for higher precision. Furthermore, previous or next odd fields are used for the motion estimation of the current odd field (See FIG. 7). Previous or next even fields are used for the motion estimation of the current even field. Odd fields are not used for even field motion estimation or vice versa. Thus, only similarly (odd or even) numbered fields are compared. Most pixels in the odd field will stay in the odd field (e.g., non-motion background, horizontal panning regions). Therefore, using previous or next odd fields for the motion estimation of the current odd field is adequate. Only when there is an odd-pixel vertical movement will a pixel in the odd field move to the even field. However, when there is an odd-pixel vertical movement, the lost information in the current odd field is also lost in the previous even field. In that case it is unnecessary to track the motion.

[0068] The present method adaptively combines line averaging and motion compensated deinterlacing techniques. Based on the position of the motion compensated, sampled point, different weightings are assigned to it. When the motion compensated, sampled point has the same position as a missed pixel (e.g. non-motion region), it has the highest reliability. On the other hand, when the motion compensated, sampled point has the same position as the existing pixel, it has the lowest reliability. In addition, the reliability of the motion vector also influences the reliability of the motion compensated, sampled point.

[0069] The first step of the deinterlacing approach is to perform motion-based compensation and obtain a missing set of samples on the 2t (even field) plane, as shown in FIG. 5. There are many approaches to obtain a missing set of samples {I(m+Δ_x,2n+Δ_y, 2t)} on the 2t plane, such as:

[0070] 1. we can find I(m+v_x, 2n+1+v_y, 2t)=I(m, 2n+1,2t+1)=I(m+2v_x, 2n+1+2v_y, 2t−1) from the motion estimation between the preceding odd field (2t−1) and the following odd field (2t+1);

[0071] 2. we can find I(m+v_x, 2n+v_y, 2t)=I(m, 2n,2t+2) from the motion estimation between even field (2t) and even field (2t+2);

[0072] 3. we can find I(m+v_x, 2n+v_y, 2t)=I(m, 2n,2t−2) from the motion estimation between the even field (2t) and the preceding even field (2t−2).

[0073] Since Δ_xand Δ_yrequire high accuracy, the true motion tracking for this application requires higher accuracy and precision than the true motion tracking for compression purposes. Our high-precision true motion tracker vertically integrates two parts: (1) a matching-based true motion tracker as the base, and (2) a gradient-based motion vector refinement. Our matching-based true motion tracker which uses a neighborhood relaxation formulation is very dependable. However, the true motion tracker can only find full-pel motion vectors. That is, the precision of the estimated motion vectors cannot be smaller than an integer. On the other hand, the precision of the motion vectors estimated by gradient-based techniques can be very small. Therefore, gradient-based techniques should be exploited in high-precision motion estimation.

[0074] Once a new set of motion compensated samples has been found on the 2t plane, we must then use those samples to determine a set of samples which lie on the sampling grid for the missing field, as shown in FIG. 6. Even though this sampling and reconstruction problem is two-dimensional, it is assumed that the signal is separable. Therefore, if {I(m, 2n, 2t), I (m+Δ_x, 2n+Δ_y, 2t)} are given, it actually takes two steps to find {I(m,2n+1, 2t)}. That is,

[0075] For Horizontal Interpolation: Given {I(m+Δ_x,2n+Δ_y,2t)} find {I(m,2n+Δ_y,2t}: Because there are enough horizontal samples at the Nyquist rate, $\begin{array}{cc}\{I\left(x,2y+{\Delta }_y,2t\right)=\sum _{m}I\left(m+{\Delta }_x,2y+{\Delta }_y,2t\right)\mathrm{sinc}\left(x-m-{\Delta }_x\right)& \left(13\right)\end{array}$

[0076] For Vertical Interpolation: Given {I(m,2n,2t),I(m,2n+Δ_y,2t)}find{I(m,2n+1,2t)}: Since 0<Δ_y<2, the generalized sampling theorem is used as:

[0077] I⁽¹⁾(x,2y+1,2t)=I^(l−1)(x,2y+1,2t)+

[0078] $\begin{array}{cc}\left\{I\left(x,2y+{\Delta }_y,2t\right)-\sum _{n}I\left(x,2n,2t\right)\mathrm{sinc}\left(2y+{\Delta }_y-2n\right)-\sum _n{I}^{\left(l-1\right)}\left(x,2n+1,2t\right)\mathrm{sinc}\left(2y+{\Delta }_y-2n-1\right)\right\}\frac{1}{\mathrm{sinc}({\Delta }_y-1}& \left(14\right)\end{array}$

[0079] The above method works well. However, there are two special cases which require further attention.

[0080] 1. Object Occlusion and Reappearance: As mentioned before, whenever there is object occlusion and reappearance, this makes the motion estimation and the motion-based frame-rate up-conversion more difficult. In this motion-compensated deinterlacing problem, the motion vectors at the object occlusion and reappearance region are ignored and use the intra-field information (e.g. line-averaging techniques) are used.

[0081] 2. Field Motion Singularity: Where an object is moving upward/downward at (2n+1) pixels per field. (Δ_y=0), multiple fields do not provide more information than that from a single field. Therefore, the intra-field information (e.g. line-averaging techniques) should be used.

[0082] The present method can be summarized as follows: $\begin{array}{c}\Delta \left(i,2j+1\right)=\sum _x\sum _y\sum _{\left\{\mathrm{Bi}\right\}}w\left(x,y,B_i\right)\delta \left(i,x+v_{\mathrm{xi}}\right)\delta \left(2j+1,y+v_{\mathrm{yi}}\right)\\ \{(I\left(x+2v_{\mathrm{xi}},y+2v_{\mathrm{yi}},2t-1\right)+\\ I\left(x+2v_{\mathrm{xi}},y+2v_{\mathrm{yi}},2t+1\right)/2-\\ \sum _m\sum _{n}I\left(m,2n,2t\right)\mathrm{sinc}\left(x+v_{\mathrm{xi}}-m\right)\\ \mathrm{sinc}\left(y+v_{\mathrm{yi}}-2n\right)-\sum _m\sum _n{\tilde{I}}^{\left(l\right)}\left(m,2n+1,2t\right)\\ \mathrm{sinc}\left(x+v_{\mathrm{xi}}-m\right)\mathrm{sinc}\left(y+v_{\mathrm{yi}}-2n-1\right)\}\end{array}$ $\begin{array}{cc}\begin{array}{c}W\left(i,2j+1\right)=\sum _x\sum _y\sum _{\left\{\mathrm{Bi}\right\}}w\left(x,y,B_i\right)\delta \left(i,x+v_{\mathrm{xi}}\right)\\ \delta \left(2j+1,y+v_{\mathrm{yi}}\right)\mathrm{sinc}\left(x+v_{\mathrm{xi}}-i\right)\\ \mathrm{sinc}\left(y+v_{\mathrm{yi}}-2j-1\right)\end{array}\begin{array}{c}{I}^{\left(l+1\right)}\left(i,2j+1,2t\right)=I^{\left(l\right)}\left(i,2j+1,2t\right)+\\ \{\begin{array}{cc}\Delta \left(i,2j+1\right)/W\left(i,2j+1\right)& \mathrm{if}W\left(i,2j+1\right)\ne 0\\ 0& \mathrm{if}W\left(i,2j+1\right)=0\end{array}\end{array}& \left(15\right)\end{array}$

[0083] where 2{right arrow over (v)}_iis the movement of B_ifrom field f_2t−1to field f_2t+1, δ (a,b)=1 when |a−b|<1 and δ (a,b)=0 otherwise,

[0084] w(z,900 ) is the window function, and I⁽⁰⁾(i,2j+1, 2t) is from the line averaging using the field f₂t. That is, $I^{\left(0\right)}\left(i,2j+1,2t\right)=\sum _{n}I\left(i,2n,2t\right)\mathrm{sinc}\left(\frac{2n-2j-1}{2}\right)$

[0085] w(x,y,B_i)=0 whenever (x,y)^Tis outside the B_i. In order to reduce the block artifacts, the weighting value of w(z,900 )could be similar to the coefficients defined for overlapped block motion compensation (OBMC).

[0086] Generalized Sampling Theorem

[0087] In the interlaced-to-progressive scan conversion method, a generalized sampling theorem is used. The Sampling Theorem itself is well-known as the following. If f(t) is a 1-D function having a Fourier transform F(ω) such that F(ω)=0 for |ω|≧ω₀=π/T_s(a band-limited signal), and is sampled at the points t_n=nT_s(Nyquist rate), then f(t) can be reconstructed exactly from its samples {f(nT_s)} as follows: $f\left(t\right)=\sum _{n=-\infty }^{\infty }f\left({\mathrm{nT}}_s\right)\frac{\sin \left[{\omega }_0\left(t-{\mathrm{nT}}_s\right)\right]}{\left[{\omega }_0\left(t-{\mathrm{nTx}}_s\right)\right]}=\sum _{n=\infty }^{\infty }f\left({\mathrm{nT}}_s\right)\mathrm{sinc}\left(\frac{t-{\mathrm{nT}}_s}{T_s}\right)$ $\mathrm{where}\mathrm{sinc}\left(0\right)=1\mathrm{and}\mathrm{sinc}\left(x\right)=\left(\pi x\right)/\pi x\mathrm{whenever}x\ne 0.$

[0088] Since the original sampling theorem debut, it has been generalized into various extensions. One Generalized Sampling Theorem is the following. If f(t) is band-limited to ω₀=π/T_s, and is sampled at ½ the Nyquist rate but, in each sampling interval, not one but two samples are used (bunched samples), then f(t) can be reconstructed exactly from its samples {f(2nT_s+ΔT_k)/0<ΔT_s,<2T_x, k=1,2}.

[0089] True Motion Information for Error Concealment

[0090] True motion vectors can also be used for better error concealment. Error concealment is intended to recover the loss due to channel noise (e.g., bit-errors in noisy channels, cell-loss in ATM networks) by utilizing available picture information. The error concealment techniques can be categorized into two it classes, according to the roles that the encoder and decoder play in the underlying approaches. Forward error concealment includes methods that add redundancy at the source (encoder) end to enhance error resilience of the coded bit streams. For example, I-picture motion vectors were introduced in MPEG-2 to improve error concealment. However, syntax changes are required. Error concealment by post-processing refers to operations at the decoder to recover damaged picture areas, based on characteristics of image and video signals.

[0091] The present method is a post-processing error concealment method that uses motion-based temporal interpolation for damaged image regions. This method uses true motion estimation at the encoder. In this work, the syntax is not changed and thus no additional bits are required. Using the true motion vectors for video coding can even optimize the bit rate for residual and motion information. Using true motion vectors for coding offers significant improvement in motion-compensated frame-rate up-conversion over the minimal-residue BMA. The more accurate the motion estimation, the better the performance of frame-rate up-conversion. Because the error concealment problem is similar to the frame-rate up-conversion problem when the error is the whole frame, one can also interpolate the damaged image regions more readily making use of the true motion vectors as described above.

[0092] While the foregoing invention has been described in terms of one or more preferred embodiments, it will be apparent to persons skilled in this art that various modifications may be made without departing from the scope of the invention, which is set forth in the following claims.