US 6,289,049 B1Grant
Method for coding motion vector in moving picture
Issue Date:2001-09-11
•14 Claims
•9 Drawing Sheets
Abstract
A method for coding a motion vector in a moving picture reduces overall bit rates in a process of moving picture coding includes searching a motion vector prediction candidate for a first block among a plurality of blocks in a macroblock, searching a plurality of motion vector prediction candidates for each of additional blocks in the plurality of blocks in succession upon completion of the search for the plurality of motion vector prediction candidates for the first block. A motion vector median prediction value for the first block is compared to a motion vector bound. If the motion vector median prediction value is determined to lie within a motion vector bound, a predicted value for coding the first block is determined to be the motion vector median prediction value. If it is determined that the motion vector median prediction value does not lie within the motion vector bound, a vector value that lies within the bound of a motion vector prediction candidate among the plurality of motion vector prediction candidate or the motion vector median prediction value is determined to be the predicted value for coding the first block. The steps of comparing a motion vector median prediction value to the motion vector bound and determining a predicted value is repeated for each of the additional blocks in the plurality of blocks in the macroblock.
Metadata
Assignee
- LG Electronics Inc.
Inventors
- Hyun Mun Kim
- Jong Beom Ra
- Sung Deuk Kim
- Young Su Lee
Application Information
Application Number:US 09/065,575
Filing Date:1998-04-24
Priority Date:1997-07-30
Art Unit:7
Classifications
IPC:
H04N 732
Field of Search:
375240375240013752401237524016375240173752401337524014375240153752402434838413483901348400134840113484021348409134841513484161348699348700382232382236382238
Patent Drawings (9 sheets)
Description
Background of the Invention
[0002] 1. Field of the Invention
[0003] The present invention relates to vector coding, and more particularly, to a method for coding a motion vector in a moving picture.
[0004] 2. Background of the Related Art
[0005] An outline of an emerging Moving Picture Expert Group (MPEG) standardization MPEG-4 will now be described. The MPEG-4 pursues a technique different from the techniques of MPEG-1 and MPEG-2 previously used to cope with the current trend in which boundaries of techniques of communication, computer and broadcasting are removed and transformed into multimedia. That is, the object of MPEG-4 is a comprehensive technique that embraces each field of the above techniques and their independent technical innovations independently as well as the exploration of fields to which the new comprehensive technique is applicable. The directions that MPEG-4 pursues at large is a technique that allows an Audio and Video (AV) coding at an extra low bit rate.
[0006] To realize the technique that allows an AV coding at an extra low bit rate, the following techniques are suggested. First, a new coding technique in which the MPEG-1 and MPEG-2 DCT transform technique is not used, for example, the Wavelet coding system that has less distortion at block boundaries and a high coding efficiency. Second, a technique that conducts motion compensation in a manner other than the MPEG-1 and MPEG-2 block based motion compensation, which conducts the motion compensation by a macro block unit. Third, a region based coding technique inclusive of the contour coding technique and the object oriented coding technique. Fourth, a Fractal coding technique that can make a compression ratio over 1/1000.
[0007] Further, there are 8 new techniques that are not yet realized but are trying to be fully realized in MPEG-4. The eight new techniques include improvement of a coding efficiency, scaleability matching to a content, content handling and bit stream editing, improvement of tolerance for error, access to a multimedia data base, coding of a plurality of synchronous data, hybrid coding of natural data and synthesized data, and improvement of a random accessibility at an extra low bit rate.
[0008] A related art method for coding a motion vector will be explained with reference to FIGS. 1-3. FIG. 1 shows a motion vector bound of 8×8 motion vectors at an 8×8 mode macroblock. FIGS. 2a-2dillustrate definitions of candidate predictors for motion vectors in 8×8 mode macroblock. FIG. 3 illustrates an example of the case when a predicted motion vector median value lies outside of a bound.
[0009] In the emerging MPEG-4 standard, the 8×8 block search operation for integer pixel motion estimation is conducted within ±2 pixel search window centered on a 16×16 motion vector. Therefore, if a particular macroblock is searched in the 8×8 mode, all the motion vectors for 4 blocks in the macroblock will lie within a bound. The matrix shown in FIG. 1 shows the bound within which the 4 block motion vectors in the macroblock searched in the 8×8 mode can exist. This bound for the 4 motion vectors serves to improve a coding efficiency of motion vectors. Each of the motion vectors representing the 4 blocks in the bound is estimated as median values of neighboring three motion vector candidates, and the x and y components of the difference between the true and the estimated motion vectors, MVDXand MVDY, are variable-length coded, which is expressed as the following.
[0010] Px=Median(MV1x, MV2x, MV3x),
[0011] Py=Median(MV1y, MV2y, MV3y),
[0012] and
[0013] MVDx=MVx−Px, MVDy=MVy−Py.
[0014] FIGS. 2a-2dillustrate motion vector candidates in a 8×8 mode according to an algorithm for estimation of a motion vector in MPEG-4. However, the motion vector estimation bound shown in FIG. 1 can not support an MPEG-4 Verification Model (VM) for the following reasons.
[0015] Referring to FIGS. 2a-2d, when the motion vector prediction candidates in the 8×8 mode macroblock are reviewed, cases exist when the motion vector prediction candidates of which median values are used for estimation of motion vectors lie outside of the bound of motion vectors in a 8×8 mode. Only the case of MV2 of block 2 is outside the bound of motion vectors in a 8×8 mode if the case of block 1 is excluded. As shown in FIG. 2b, only one of the three motion vector prediction candidates lies within the 8×8 mode macroblock. In this case, an absolute value of the MVD2 obtained from the predicted value of the median values may lie outside of a bound of 5.0. As shown in FIG. 3, when an MV of block 2 is denoted as MVCurrentBlock(a motion vector for respective block), an MV1 of block 2 is denoted as MvinsideMBprediction(a motion vector estimation within the bound), and a Median(MV1, MV2, MV3) of block 2 is denoted as MVMedianPrediction, there is a case when the MVMedianPredictionlies on a point outside of the bound.
[0016] Therefore, the related art method for coding a motion vector has various disadvantages. The related art method for coding a motion vector in a moving picture has a problem of bit loss when an estimated value from medians lies outside of a bound.
Summary of the Invention
[0017] An object of the present invention is to provide a method for coding a motion vector in a moving picture that substantially obviates one or more of the problems due to limitations and disadvantages of the related art.
[0018] Another object of the present invention is to provide a method for coding a vector that prevents an increase in bit rate when a predicted vector lies outside a bound.
[0019] A further object of the present invention is to provide a method for coding a moving vector in a motion picture that reduces the bit rate.
[0020] A still further object of the present invention is to provide a method for coding a moving vector that reduces bit loss.
[0021] To achieve these and other advantages in whole or in parts and in accordance with the purpose of the present invention, as embodied and broadly described, a method for coding a motion vector in a moving picture includes searching a first, a second and a third motion vector prediction candidates for a block 1 among 4 8×8 blocks in a macroblock when a search mode for the macroblock is selected to be an 8×8 mode, searching a first, a second and a third motion vector prediction candidates MV1, MV2 and MV3 for each of block 1, block 2, block 3 and block 4 in succession, comparing a notion vector median prediction value MVMedianPredictionfor the block 1 to a motion vector bound, determining the motion vector median prediction value as a predicted value for coding the block 1 if the motion vector median prediction value lies within the bound, determining a vector value that lies within the bound of a motion vector prediction candidate among the first, the second and the third motion vector prediction candidates or a motion vector median prediction value as a predicted value PMV for coding the block 1 if the motion vector median prediction value does not lie within the bound, and repeating the step of comparing a motion vector median prediction value to a motion vector bound and determining a predicted value for the entire 8×8 blocks in the macroblock.
[0022] To further achieve these and other advantages in whole or in parts and in accordance with the purpose of the present invention, as embodied and broadly described, a method for coding a motion vector includes selecting a motion vector median prediction value for a current block of the plurality of blocks in a macroblock to be a predicted value if the motion vector median prediction value lies within a bound, selecting one of a vector value of a motion vector prediction candidate that lies within the motion vector from the plurality of motion vector prediction candidates for the current block and the motion vector median prediction value to be the predicted value and performing the selecting steps for said each of the plurality of blocks.
[0023] Additional advantages, objects, and features of the invention will be set forth in part in the description which follows and in part will become apparent to those having ordinary skill in the art upon examination of the following or may be learned from practice of the invention. The objects and advantages of the invention may be realized and attained as particularly pointed out in the appended claims.
Brief Description of the Drawings
[0024] The invention will be described in detail with reference to the following drawings in which like reference numerals refer to like elements wherein:
[0025] FIG. 1 is a diagram that illustrates a matrix showing a motion vector bound of 8×8 motion vectors at an 8×8 mode macroblock;
[0026] FIGS. 2a-2dare diagrams that illustrate definitions of candidate predictors for motion vectors in 8×8 mode macroblock;
[0027] FIG. 3 is a diagram that illustrates a predicted median value of a motion vector;
[0028] FIG. 4 is a flow chart that illustrates coding a motion vector according to a preferred embodiment of the present invention; and
[0029] FIG. 5a-5dare diagrams that illustrate tables of bit rate changes using the motion vector coding according to a preferred embodiment of the present invention.
Detailed Description of Preferred Embodiments
[0030] A preferred embodiment of a method for coding motion vectors according to the present invention will now be described. When an estimation based on median values lies outside of a bound, an expected bit amount produced when an MVMedianPredictionor MVInsideMBPredictionis used as a predictor can be determined as follows:
[0031] Expected bit amount (E(R(MVCurrentBlock−MVMedianPrediction))=(R(0.5)+R(1.0)+R(1.5)+R(2.0)+R(2.5)+R(3.0)+, . . . ,+R(10.5))/21=
[0032] (3+4+5+7+3*10+11*11)/21=194/21=9.238(when f_code=1), (2*4+2*5+2*6+2*8+6*9+6*11+12)/21=178/21=8.476(when f_code=2),
[0033] (4*5+4*6+4*7+4*9+5*10)/21=154/21=7.333(when f_code=3).
[0034] Expected bit amount E(R(MVCurrent Block−MVInsideMBPrediction))=(R(0)+2*(R(0.5)+R(1.0)+R(1.5)+, - - - ,+R(5.0)))/21=
[0035] (1+2*(3+4+5+7+3*8+3*10))/21=147/21=7(when f_code=1), (1+2*(2*4+2*5+2*6+2*8+2*9))/21=129/21=6.143(when f_code=2), (1+2*(4*5+4*6+2*7))/21=117/21=5.571(when f_code=3).
[0036] In the above calculations, R(MVD) is an amount of bit produced of MVD and an MVCurrentBlockis assumed to have a uniform probability distribution within the bound. In view of probability, there is about an increase of two bits in each component for every f_code when MVMedianPredictionlies outside of the vector bound.
[0037] The method for coding a motion vector according to the preferred embodiment of the present invention prevents the increase of bits when MVMedianPredictionlies outside of the vector bound. When MVMedianPrediction, which is used as a median predictor lies outside of the vector bound, MVInsideMBPredictionis selectively used. That is, the portions selected for motion vector prediction (PMV) for a case outside of the bound (e.g. the block 2 shown in FIG. 2b) are preferably changed as follows:
[0038] PMV=Median(MV1, MV2, MV3), if(ABS(PMV−MV1)>THR), PMV=MV1,
[0039] where THR denotes an actual motion vector bound in an 8×8 mode and maximum value of THR is preferably 5.0.
[0040] A case of the motion vector prediction candidate lying outside of the bound is most probably the case of the second 8×8 block (e.g., block 2 shown in FIG. 2b) in the current MPEG-4 standard. Therefore, in the preferred embodiment of a method for coding motion vectors, comparing THR to ABS(PMV−MV1) is preferably used only the case of block 2.
[0041] FIG. 4 illustrates a flow chart showing an exemplary process steps for coding a motion vector in accordance with the preferred embodiment of the present invention. Referring to FIG. 4, a process starts and continues to step 401S. In step 401S, an 8×8 mode is selected as a search mode of a macroblock for coding a motion vector. From step 401S, control continues to step 402S.
[0042] In step 402S, a block (e.g., initial block 1) of the 4 8×8 blocks in the macroblock is searched for a motion vector prediction candidate. From step 402S, control continues to step 403S. In step 403S, completion of the search of the first, second and third motion vector prediction candidates for the current block (e.g., block 1) is determined. If the determination in step 403S is negative, control returns to step 402S. If it is determined in step 403S that the search of the first, second and third motion vector prediction candidates for the current block is finished, control continues to step 404S.
[0043] In step 404S, completion of the search of all blocks (e.g., the four 8×8 blocks) for a respective motion vector prediction candidate is determined. If it is determined in step 404S that the search for motion vector candidates for the 4 8×8 blocks is complete, control continues to step 405S. However, if the determination in step 404S is negative, a current block being searched is incremented by 1 (e.g., from block 1 to block 2) and control returns to step 402S. Thus, the searches of the 8×8 block 1, block 2, block 3, and block 4 for the first, second and third motion vector prediction candidates MV1, MV2 and MV3 for each of the blocks are conducted in succession.
[0044] In step 405S, the motion vector median prediction value MVMedianPredictionfor an 8×8 block (e,.g., the first block) is compared to the motion vector bound. From step 405S, control continues to step 406S. In step 406S, whether the motion vector median prediction value MVMedianPredictionis within the motion vector bound is determined. If the determination in step 406S is affirmative, control continues to step 407S. In step 407S, the motion vector median prediction value MVMedianPredictionis determined to be a prediction value for coding the corresponding (e.g., block 1) 8×8 block. If the determinination in step 406S is negative (not within the bound), control continues to step 408S.
[0045] In step 408S, an absolute value of the motion vector median value minus the vector value of the prediction candidate is compared to a preset threshold value THR. As a result of the comparison, if found the preset threshold value THR is smaller, of the first, second and third motion vector prediction candidates, the vector value of the prediction candidates that lies within the bound is taken as a prediction value for coding the corresponding 8×8 block. If the preset threshold value THR is larger, a motion vector median prediction value is taken as a prediction value for coding the corresponding 8×8 block. In other words, if the determination in step 408S is negative, control continues to step 407S. If the determination in step 408S is affirmative, control continues to step 409S. In step 409S, a vector value of a prediction candidate lying within the bound among the first, second and third motion vector prediction candidates is determined as a predicted value for coding a current 8×8 block.
[0046] From steps 407S and 409S, control continues to step 410S. In step 410S, a determination is made whether predicted values for all 8×8 blocks in the macroblock are complete. If the determination in step 410S is negative, the current block is incremented and control returns to step 405S. If the determination in step 410S is affirmative, the process ends. Thus, the steps (e.g., steps 405S-409S) in which a motion vector median prediction value is determined within a bound and a preset threshold value THR is compared to determine a prediction value is repeated for all blocks (e.g., sub-blocks or 8×8 blocks) in the macroblock in question. Upon determination of a prediction value, a differential of the prediction values for the entire motion vectors are coded.
[0047] As described above, the preferred method for coding a motion vector in a moving picture of the present invention prevents an increase of a bit amount when an MVMedianPredictionlies outside of a motion vector bound when an 8×8 mode is selected. In other words, the increase of bit amount in coding is prevented by using MVInsideMBPredictionwhen the MVMedianPrediction, which is used as a median predictor, is outside of a preset threshold value THR.
[0048] The preferred embodiment of a method for motion vector coding described with respect to FIG. 4 uses a 16×16 macroblock and a 8×8 search mode. However, the present invention is not intended to be limited to this. Alternative sized macroblocks and various search modes can also be used.
[0049] An exemplary apparatus using a motion vector coding technique according to a preferred embodiment of the present invention will now be described. FIGS. 5a-5dillustrates a number of bits in an actual motion vector coding using the preferred embodiment of a method for motion vector coding under the following conditions. First, a quantization parameter QP is fixed for each sequence, and a motion vector of a skipped macroblock is not included in the determination. Second, a sequence resolution format in an advanced prediction mode is a Quarter Common Intermediate Format (QCIF)(176×144) with a frame rate of 10 Hz (300 frames). Third, an f_code=1(range of MV search: −16.0˜+15.5), and the No shape coding (rectangular) is used as a coding technique.
[0050] The tables in FIGS. 5aand 5brespectively illustrate results when a block (MVD2) has a motion prediction value lying outside of a bound according to the prediction value determination of the preferred embodiment of the present invention. FIG. 5ashows a case of QP=10 and FIG. 5bshows a case of QP=20. The tables in FIGS. 5cand 5drespectively illustrate results when the entire motion vectors are coded. FIG. 5cshows a case of QP=10 and FIG. 5dshows a case of QP=20. Thus, as shown in FIGS. 5a-5d, the preferred embodiment of a method of a motion vector coding is more efficient (e.g. an increase of number of bits is prevented) than an MPEG-4 video VM 5.0, enough to apply to VM 6.0.
[0051] The method for coding a motion vector in moving picture of the present invention has an advantage of reducing a required number of bits to code the motion vector by preventing an increase of a number of bits by using, for example, an MVInsideMBPredictionas a prediction value when an MVMedianPredictionused, for example, as a median predictor lies outside of a preset bound.
[0052] The foregoing embodiments are merely exemplary and are not to be construed as limiting the present invention. The present teaching can be readily applied to other types of apparatuses. The description of the present invention is intended to be illustrative, and not to limit the scope of the claims. Many alternatives, modifications, and variations will be apparent to those skilled in the art.
Claims
What is claimed is:
1. A method for coding a motion vector in a moving picture, the method comprising:
searching a plurality of motion vector prediction candidates for a first block among a plurality of blocks in a macroblock;
searching a plurality of motion vector prediction candidates for each of additional blocks of the plurality of blocks;
comparing a motion vector median prediction value for the first block to a motion vector bound, and wherein a motion vector predicted value for coding the first block is determined to be the motion vector median prediction value when the motion vector median prediction value lies within the motion vector bound, wherein the motion vector predicted value for coding the first block is determined to be at least one of a vector value that lies within the motion vector bound of a motion vector prediction candidate among the plurality of motion vector prediction candidates and the motion vector median prediction value when the motion vector prediction candidates are outside the motion vector bound, and wherein when the motion vector median prediction value is outside the motion vector bound for a current block, the comparing comprises,
comparing an absolute value of the motion vector prediction median value minus a vector value of a prediction candidate lying within the motion vector bound to a prescribed threshold value,
determining the vector value of the motion vector prediction candidate among the plurality of motion vector prediction candidates within the motion vector bound to be the motion vector predicted value for coding the current block when the prescribed threshold value is smaller, and
determining the motion vector median prediction value to be the motion vector predicted value when the prescribed threshold value is larger; and,
repeating the step of comparing a motion vector median prediction value for the additional blocks in the plurality of blocks.
2. The method of claim 1, wherein the motion vector bound has a maximum value of 5.0.
3. The method of claim 1, wherein the prescribed threshold value is smaller for a second searched block in the macroblock according to prescribed motion vector prediction candidates.
4. The method of claim 1, wherein the prescribed threshold value is smaller for a second block in the macroblock according to a motion vector prediction candidate standard search.
5. The method of claim 1, wherein a search mode for the macroblock is 8×8, and wherein the plurality of blocks is 4 8×8 blocks in the macroblock.
6. A method for coding a motion vector, comprising:
selecting a motion vector median prediction value for a current block of a plurality of blocks in a macroblock to be a predicted value if the motion vector median prediction value lies within a bound;
selecting one of a vector value of a motion vector prediction candidate that lies within the bound from a plurality of motion vector prediction candidates for the current block and the motion vector median prediction value to be the predicted value, wherein when the motion vector median prediction value is outside the bound, the step of selecting comprises,
comparing an absolute value of a motion vector median prediction value minus a vector value of a prediction candidate lying within the bound to a prescribed threshold value, and
determining the motion vector median prediction value to be the predicted value when the prescribed threshold value is larger; and
performing the selecting steps for each of the plurality of blocks in the macroblock.
7. The method of claim 6, wherein when the motion vector median prediction value is outside the bound, the selecting one comprises:
determining the vector value of the motion vector prediction candidate within the bound from the plurality of motion vector prediction candidates to be the predicted value when the prescribed threshold value is smaller.
8. The method of claim 6, wherein the prescribed threshold value has a maximum value of 5.0.
9. The method of claim 6, wherein the prescribed threshold value is smaller for a second searched block in the macroblock according to prescribed motion vector prediction candidates for the current block.
10. The method of claim 6, further comprising:
successively searching for the plurality of motion vector prediction candidates for said each of the plurality of blocks in the macroblock; and
determining the motion vector median prediction value for said each of the plurality of blocks based on the corresponding plurality of motion vector prediction candidates.
11. The method claim 6, wherein the searching step searches in an 8×8 search mode.
12. The method of claim 6, further comprising coding said each of the plurality of blocks based on the predicted value, wherein a coding bit rate is reduced.
13. The method of claim 6, wherein the macroblock is 16×16, each of 4 blocks in the plurality of blocks is 8×8, and wherein the plurality of motion vector prediction candidates is 3.
14. The method of claim 6, wherein the predicted value is a motion vector predicted value for coding the current block.
Patent Citations (8)
Non-Patent Literature (6)
- Avideh Zakhor, “Iterative Procedures for Reduction of Blocking Effects In Transform Image Coding”, IEEE Transactions On Circuits and Systems For Video Technology, vol. 2, No. 1, pp. 91-95 (Mar. 1992).Applicant
- Yongyi Yang et al., “Regularized Reconstructions to Reduce Blocking Artifacts of Block Discrete Cosine Transform Compressed Images”, IEEE Transactions On Circuits and Systems For Video Technology, vol. 3, No. 6, pp. 421-432 (Dec. 1993).Applicant
- Gary J. Sullivan et al., “Motion Compensation for Video Compression Using Control Grid Interpolation”, IEEE International Conference, pp. 2713-2716 (1991).Applicant
- G. de Haan et al., “IC For Motion-Compensation 100Hz TV With Natural-Motion Movie-Mode”, IEEE Transactions On Consumer Electronics, vol. 42, pp. 165-174 (Feb. 1996).Applicant
- Taner Özcelik et al., “Image and Video Compression Algorithms Based on Recovery Techniques Using Mean Field Annealing”, Proceedings of the IEEE, vol. 83, No. 2, pp. 304-316, Feb. 1995.Applicant
- Yasuyuki Nakajima et al., “A PEL Adaptive Reduction of Coding Artifacts for MPEG Video Signals”, pp. 928-932, IEEE, 1994.Applicant