CN100359952C

CN100359952C - motion prediction method in video coding

Info

Publication number: CN100359952C
Application number: CNB2004100545423A
Authority: CN
Inventors: 张誉钟; 郭沛昀
Original assignee: MediaTek Inc
Current assignee: MediaTek Inc
Priority date: 2004-07-23
Filing date: 2004-07-23
Publication date: 2008-01-02
Anticipated expiration: 2024-07-23
Also published as: CN1725862A

Abstract

A motion prediction method in video coding is used to generate motion vectors required for encoding original blocks. The method comprises the following steps: (a0) generating a center point; (a) generating a main search window with 7 × 7 points with a step size of 3 by taking the center point as a center, calculating a plurality of block difference measurement values corresponding to a plurality of check points in the main search window respectively, and setting the check point corresponding to the smallest check point as a candidate check point; (a1) judging whether the candidate check point is a central point, if so, executing the step (c), otherwise, executing the step (b); (b) setting the candidate check point as a central point, and executing the step (a); and (c) generating an auxiliary search window with 3 multiplied by 3 points and the step size of 1 by taking the candidate check point as a central point, and calculating a plurality of block difference measurement values corresponding to the check points in the auxiliary search window, wherein the check point with the minimum block difference measurement value is the obtained optimal point, and the motion vector is obtained by subtracting the coordinate of the optimal point and the coordinate of the central point.

Description

Motion forecast method in the video coding

Technical field

The present invention relates to a kind of motion forecast method, and be particularly related to the motion forecast method in a kind of video coding.

Background technology

In the technology of motion compensated video coding, when to present picture frame (current frame) when encoding, can more present picture frame be encoded by producing a motion vector (motion vector) afterwards from previous picture frame (previous frame).And this motion vector is to produce via motion prediction (motion estimation) method.General motion forecast method is to predict unit with the piece (macroblock) in each picture frame as minimum, and the size of each piece for example is 16 * 16 pixels.

Please refer to Fig. 1, it shows the schematic diagram of conventional motion compensation video coding.In the time will encoding to the piece in the present picture frame 102 104, must be earlier from previous picture frame 106, find in the search window (search window) 110 by motion forecast method, mate (match) and the minimum piece 108 of otherness (distortion) most.Then, the coordinate figure of computing block 108 in picture frame 106 and the difference of the coordinate figure of piece 104 in picture frame 102 can obtain motion vector 112.Then, encoded in the difference place of the view data of the view data of piece 104 and piece 108.So, with directly with piece 104 Methods for Coding of picture frame 102 than, the data volume when using motion compensated video to encode the image data transmission that can significantly reduce picture frame 102, the image of picture frame 102 can be compressed effectively.

The algorithm of the existing two kinds of motion predictions of tradition proposes.First kind is T.Koga, K.Iinuma, A.Hirano, Y.Iijima and T.Ishiguro are at Proc.NTC81, New Orleans, LA, three steps that proposed in Nov.1981 " Motion-Compensated Interframe Coding for Video Conferencing " are searched (Three-step Search, TSS) algorithm, another kind is that Lai-Man Po and Wing-Chung Ma are at IEEE Transactions on Circuits and Systems for VideoTechnology, vol.6, no.3, four steps that proposed in June 1996 " A Novel Four Step SearchAlgorithm For Fast Block Motion Estimation " are searched (Four-Step Search, FSS) algorithm.

Please refer to Fig. 2, it shows the schematic diagram of three traditional step search algorithms.Three step search algorithms have the seek actions in three steps altogether, and the step size in per step (step size) SS is 4,2 and 1 length in pixels in regular turn.Its step is as follows.At first, get a search window (search window) 204.Search window 204 is for square, and is to have 9 points on each length of side, and the size of search window 204 is to be 9 * 9 points.Except from 9 points of each length of side, three points getting equidistant intervals are as outside the checkpoint, and the central point of more getting search window 204 is checkpoint 202 (1).The length of side of search window 204 is 8 length in pixels, and the distance between each checkpoint and the most contiguous checkpoint is 4 length in pixels, so the step of search window 204 size SS is 4 length in pixels.Then, (Block Distortion Measure BDM), and finds out the pairing checkpoint of smallest blocks difference measured value, for example is checkpoint 202 (2) to obtain the pairing discrepancy measure in each checkpoint.Then, taking out with checkpoint 202 (2) is the center, and length is 9 checkpoints on the search window 206 of 4 length in pixels, and finds out the pairing checkpoint of smallest blocks difference measured value, for example is checkpoint 202 (3).At last, taking out with checkpoint 202 (3) be the center, and length is 9 checkpoints on the search window 208 of 2 length in pixels, and calculates in these 9 checkpoints, and the piece discrepancy measure is the checkpoint of minimum, for example is checkpoint 202 (4).So, can obtain the value of motion vector 210 by checkpoint 202 (4) and 202 (1).

In three step search algorithms, need 25 pairing 25 pieces in checkpoint are fixed the action of 25 times piece coupling altogether, that is fix and to calculate 25 times piece discrepancy measure.The checkpoint the position that might occur be that the Search Area 200 that defines 200, three step an of Search Area (Search Range) search algorithm is (7.

Wherein, each checkpoint is a piece that corresponds to respectively in the previous picture frame, and the point of diverse location is the piece that corresponds to diverse location.For instance, please refer to Fig. 3 A and 3B, it shows checkpoint 202 (1) and 202 (2) pairing 302 (1) and 302 (2) respectively.Because checkpoint 202 (1) to the right upwards respectively after four pixels of translation, can be obtained checkpoint 202 (2), so, the regional extent of piece 302 (1) to the right upwards respectively after four pixels of translation, can be obtained the regional extent of piece 302 (2).With checkpoint 202 (2) is example, the account form of piece discrepancy measure be for, image data value with all pixels of piece 302 (2), image data value with all pixels of the piece of the central point that corresponds to Search Area 200 in the present image, after subtracting each other accordingly and taking absolute value, its summation is the piece discrepancy measure of checkpoint 202 (2).

Please refer to Fig. 4, it shows the schematic diagram of four traditional step search algorithms.Four step search algorithms have the seek actions in four steps altogether, and the step size SS in per step is 2,2,2 and 1 length in pixels in regular turn.Its step is as follows.At first, be the center with the central point of Search Area 400, get 9 checkpoints 402, the distance between each checkpoint 402 and the most contiguous checkpoint 402 is 2 length in pixels, checkpoint 402 (1) is to be positioned at central point.Then, obtaining the 402 pairing discrepancy measure in each checkpoint, and find out the pairing checkpoint of smallest blocks difference measured value, for example is checkpoint 402 (2).Then, repeat above-mentioned steps twice, to obtain checkpoint 402 (3) and 402 (4) respectively.At last, obtain in 8 checkpoints adjacent with checkpoint 402 (4), the piece discrepancy measure is minimum checkpoint again.The checkpoint of piece discrepancy measure minimum is the optimum of being tried to achieve, and the coordinate of optimum and the coordinate of central point subtract each other and be motion vector.The Search Area of four step search algorithms also is (7.

Four step search algorithms are to have the function that finishes (Early Termination) ahead of time.That is to say, in the seek actions in first three step,, then enter the seek actions in the 4th step ahead of time, to finish the calculating of four step search algorithms ahead of time if the pairing checkpoint of smallest blocks difference measured value is to be positioned at central point.Therefore, in four steps the number of times of required piece coupling of carrying out be 17 (=9+8) inferior to 27 (=9+5+5+8) inferior.On average, four step search algorithms are weak point than three step search algorithms required computing time.

It is the characteristic that distributes for central tendency (Center-Biased) that the design of four step search algorithms mainly is based on motion vector, and four step search algorithms are efficient than three step search algorithms when handling the image of microinching (Slow Motion).So-called central tendency distributes and is meant, the image in the real life is to be slowly smooth-going variation.Therefore, in general, near the central point of search window, find the piece discrepancy measure very high for the chance of minimum checkpoint.But four step search algorithms are to the image (Fast MotionPictures) of rapid movement when encoding, and (Peak Signal-to-Noise Ratio PSNR) has the decline of certain degree to the error ratio of representative image quality.Its main cause is, the step size of the seek actions in first three step of four step search algorithms all is fixed as 2, and search window is 5 * 5, and the search window of the seek actions in the 4th step is 3 * 3.Therefore, when the image rapid movement, the step size is 2 slightly to seem big inadequately, and can't catch up with the speed of image motion.And, the words that have the characteristic of local minimum (Local Minimum) when the piece discrepancy measure of certain checkpoint of search window, even just the number of times in increase step extends to n step search (n＞4) with the search of four steps, Search Area is increased substantially and effectively.Wherein, the situation that local minimum produces is, in nine checkpoints of being searched, when the pairing discrepancy measure in the checkpoint that is positioned at central point for hour, the condition that finishes (Early Termination) will be set up ahead of time, and directly carries out final step (Final Step).That is to say that four step search algorithms may be judged a minimum value in the local zonule by accident, and it is considered as is global minimum (Global Minimum) in the whole Search Area.So, will make the image quality of the compressed image after encoding reduce.

Therefore, how to improve the image quality of compressed image, especially the image quality after the image compression of rapid movement is one of industry problem of endeavouring to study.

Summary of the invention

In view of this, purpose of the present invention is exactly the motion forecast method in a kind of video coding is provided, and can improve the image quality after the image compression of image quality, especially rapid movement of compressed image effectively.The present invention more can reach required search time is lacked than other traditional algorithm, and makes also little than other the traditional algorithm purpose of film distortion rate after the compression.

According to purpose of the present invention, motion forecast method in a kind of video coding is proposed, when to the original block (macroblock) of present picture frame (frame) when encoding, this method is most to mate a purpose piece of (match) with original block in order to hunt out in the previous picture frame.This method is the relative position according to purpose piece and original block, produces the original block required motion vector of encoding.The purpose piece is that (I, J) (I, one of J), I, J are integer to pairing a plurality of B for a plurality of somes CP that comprised in the Search Area (search region).Motion forecast method of the present invention comprises the following steps: that (a) makes parameter K=0, L=0, P=1; (b) setting a P main search window, is to have a plurality of checkpoints on P main search window, comprises a CP (M, N), M=K+i, N=L+j, i, j=-3,0,3, and a plurality of discrepancy measure (blockdistortion measure) BDM (M of these corresponding pieces is distinguished in these checkpoints of calculating P search window, N), define reckling in these piece discrepancy measure and be BDM (K+s, L+t), s, t are integer; (c) judge whether P equals a main predetermined step number, if, execution in step (f) then, if not, execution in step (c1) then; (c1) judge whether s=t=0, if, execution in step (f) then, if not, execution in step (d) then; (d) K is added s, L is added t, P is added 1, execution in step (b); And (f) set one and assist search window, on auxiliary search window is to have a plurality of checkpoints, comprises a CP (M ', N '), M '=K+u, N '=L+v, u, v=-1,0,1, and these checkpoints of calculating auxiliary search window distinguish a plurality of discrepancy measure BDM (M ', N ') of these pieces of correspondence, and selecting pairing of reckling in these piece discrepancy measure is the purpose piece.

According to another object of the present invention, the motion forecast method in a kind of video coding is proposed.When to the original block (macroblock) of present picture frame (frame) when encoding, this method is in order to produce the original block required motion vector of encoding.Motion forecast method of the present invention comprises the following steps: that (a0) produces a central point; (a) carry out the seek actions that step size (Step Size) is 3 the first step, wherein, with the central point is the center, generation one has the first main search window of 7 * 7 points, and calculate a plurality of checkpoint in the first main search window and distinguish a plurality of corresponding discrepancy measure, and the pairing checkpoint of the reckling of these piece discrepancy measure is made as a candidate checkpoint; (a1) judge whether the candidate checkpoint is the central point of the first main search window, if, execution in step (d) then, if not, execution in step (b) then; (b) the candidate checkpoint is set at central point, execution step size is 3 one second seek actions that goes on foot, wherein, with the central point is the center, generation one has the second main search window of 7 * 7 points, and a plurality of corresponding discrepancy measure are distinguished in a plurality of checkpoint of calculating in the second main search window, and the pairing checkpoint of reckling of these piece discrepancy measure in the seek actions in second step is made as the candidate checkpoint; (b1) judge whether the candidate checkpoint is the central point of the second main search window, if, execution in step (d) then, if not, execution in step (c) then; (c) execution step size is 3 one the 3rd seek actions that goes on foot, wherein, with the candidate checkpoint is central point, generation has one the 3rd main search window of 7 * 7 points, and a plurality of corresponding discrepancy measure are distinguished in a plurality of checkpoint of calculating in the 3rd main search window, and the pairing checkpoint of reckling of these piece discrepancy measure in the seek actions in the 3rd step is made as this candidate checkpoint; And (d) carry out the seek actions that the step size is a final step of 1, wherein, with the candidate checkpoint is central point, generation has an auxiliary search window of 3 * 3 points, and a plurality of corresponding discrepancy measure are distinguished in a plurality of checkpoint of calculating in the auxiliary search window, and the pairing checkpoint of reckling of these piece discrepancy measure in the seek actions of final step is made as the candidate checkpoint, and the coordinate of candidate checkpoint and the coordinate of central point subtract each other and are motion vector.

For above-mentioned purpose of the present invention, feature and advantage can be become apparent, a preferred embodiment cited below particularly, and conjunction with figs. are described in detail below.

Description of drawings

Fig. 1 shows the schematic diagram of conventional motion compensation video coding.

Fig. 2 shows the traditional search of three steps (Three-Step Search, TSS) schematic diagram of algorithm.

3A and 3B figure shows checkpoint 202 (1) and 202 (2) pairing 302 (1) and 302 (2) respectively.

Fig. 4 shows the traditional search of four steps (Four-Step Search, FSS) schematic diagram of algorithm.

Fig. 5 shows the flow chart according to the motion forecast method in a kind of video coding of a preferred embodiment of the present invention.

Fig. 6 A shows one first example of the motion forecast method in the video coding of using present embodiment.

Fig. 6 B shows one second example of the motion forecast method in the video coding of using present embodiment.

Fig. 7 shows another example of four step of tradition search algorithm.

Fig. 8 shows another example of the motion forecast method in the video coding of present embodiment.

Fig. 9 shows the schematic diagram of 4-4-2-1 algorithm.

Figure 10 shows four step search algorithms, three step search algorithms, 4-4-2-1 algorithm, reaches every comparison sheet of the motion forecast method of present embodiment.

Figure 11 A-11E divides the representative image that shows Salesman, Hall_mointor, Foreman, Carphone and Stefan test film in addition.

Figure 12 A-12C be listed in respectively low under the Senior Three kind bit rate (bit-rate), four step search algorithms, three step search algorithms, 4-4-2-1 algorithm, and the comparison of the mean value of the piece discrepancy measure of the motion forecast method of present embodiment.

Figure 13 A-13C be listed in respectively low under the Senior Three kind bit rate, four step search algorithms, three step search algorithms, 4-4-2-1 algorithm, and the comparison of the average step number of the motion forecast method of present embodiment.

Figure 14 A-14C be listed in respectively low under the Senior Three kind bit rate, four step search algorithms, three step search algorithms, 4-4-2-1 algorithm, and the comparison of the average block matching times of the motion forecast method of present embodiment.

Figure 15 A-15E shows branch when testing with Salesman, Hall_mointor, Foreman, Carphone and Stefan test film in addition, the bit rate of the motion forecast method of four step search algorithms and present embodiment and the relation curve of error ratio.

The reference numeral explanation

102,106: picture frame

104,108,302: piece

110,204,206,208: search window

112,210: motion vector

202,402, CP: checkpoint

200,400,600: Search Area

502-512: process step

604: main search window

606: auxiliary search window

Embodiment

Motion forecast method in the video coding of the present invention can effectively improve the error ratio of compression rapid movement image.The present invention is when the image (Fast Motion Pictures) of compression rapid movement, and error ratio of the present invention can improve 0.2-0.4dB approximately than four step search algorithms.When the slow or static image of compression movement, the present invention still can reach and the close image quality of four step search algorithms.In addition, average calculating operation speed of the present invention is also fast than four step search algorithms and three step search algorithms.

Please refer to Fig. 5, it shows the flow chart according to the motion forecast method in a kind of video coding of a preferred embodiment of the present invention.When the original block of present picture frame was encoded, the method for present embodiment was in order to hunt out the purpose piece that mates most with original block in the previous picture frame.The method of present embodiment is the relative position according to purpose piece and original block, produces the original block required motion vector of encoding.The purpose piece is that (I, J) (I, one of J), I, J are integer to pairing a plurality of B for a plurality of somes CP that comprised in the Search Area.The motion forecast method of present embodiment mainly comprises step 502 to 512, and division is as follows now.

At first, execution in step 502 makes window center point abscissa parameter K=0, and step number P=1 is carried out in window center point ordinate parameter L=0.Then, execution in step 504 is set a P main search window.On the main search window of P is to have a plurality of checkpoints, comprise a CP (M, N), M=K+i, N=L+j, i, j=-3,0,3.In this step, and these checkpoints of calculating P search window distinguish a plurality of corresponding a plurality of discrepancy measure BDM (M, N).The reckling that defines in these piece discrepancy measure is that (K+s, L+t), s, t are integer to BDM.

Then, enter step 506, judge whether P equals a main predetermined step number; If then execution in step 512, if not, then execution in step 508.In step 508, judge whether s=0 and t=0, if then execution in step 512, if not, then execution in step 510.In step 510, K is added s, L is added t, P is added 1, and execution in step 504.

In step 512, set an auxiliary search window.On auxiliary search window is to have a plurality of checkpoints, comprises a CP (M ', N '), M '=K+u, N '=L+v, u, v=-1,0,1.In this step, and a plurality of discrepancy measure BDM (M ', N ') of these pieces of correspondence are distinguished in these checkpoints of calculating auxiliary search window.Pairing of the reckling that defines in these piece discrepancy measure is the purpose piece.

Wherein, the central point CP (0,0) of Search Area corresponds in the previous picture frame and the piece B original block same position (0,0).In step 504, the method of calculating these piece discrepancy measure is, earlier with the view data of all pixels of the piece in the pairing previous picture frame in checkpoint, after subtracting each other accordingly with the view data of all pixels of original block and taking absolute value, calculate its summation again.This summation is the piece discrepancy measure of checkpoint.Above-mentioned main predetermined step number is for more than or equal to 1 positive integer, and preferably, this mainly predetermined step number is to equal 3.

Now lift an example so that it to be described.Please refer to Fig. 6 A, it shows one first example of the motion forecast method in the video coding of using present embodiment.In this first example, setting main predetermined step number is to equal 3, and always searching step number is 4.Search Area 600 is to be ± 10, its comprise 11 * 11 some CP (I, J) ,-10＜=I＜=10 ,-10＜=J＜=10.The step size SS of the seek actions in three steps of the first step to the is 3, and the seek actions in three steps of the first step to the is to correspond to the 1st, the 2nd and the 3rd main search window 604 (1), 604 (2) and 604 (3) with 7 * 7 points respectively.Each main search window is to have 9 checkpoints, and the distance between the checkpoint is 3 length in pixels.And in the end the step size SS of the seek actions in a step is 1, and the seek actions of final step is to correspond to an auxiliary search window 606 (1) with 3 * 3 points.Auxiliary search window 606 (1) also has 9 checkpoints, and the distance between the checkpoint is 1 length in pixels.

At first, execution in step 502 makes K=0, L=0, P=1, and execution in step 504.On the 1st main search window 604 (1) is to have 9 checkpoints, comprises a CP (0,0), CP (0,3), CP (0 ,-3), CP (3,0), CP (3,3), CP (3 ,-3), CP (3,0), CP (3,3) and CP (3 ,-3).If pairing discrepancy measure BDM of checkpoint CP (3,3) (3,3) be minimum, make BDM (3,3)=BDM that (K+s L+t), and is made as a candidate checkpoint with checkpoint CP (3,3).Because K=L=0 is so can obtain s=3, t=3.Since P=1＜3, s=3, and t=3 so follow execution in step 510, adds 3 with K, L is added 3, and P is added 1.

At this moment, K=L=3, P=2.Then, repeating step 504 corresponds to the 2nd 9 checkpoints on the main search window 604 (2) with calculating, comprise a CP (3,3), CP (3,6), CP (3,0), CP (0,3), CP (0,6), CP (0,0), CP (6,3), CP (6,6) 9 piece discrepancy measure and CP (6,0).The 2nd main search window 604 (2) is with candidate checkpoint at this moment, that is is that checkpoint CP (3,3) is a central point.If pairing discrepancy measure BDM of checkpoint CP (6,6) (6,6) is minimum, make BDM (6,6)=BDM that (K+s L+t), and is made as the candidate checkpoint with checkpoint CP (6,6) again.Because K=L=3 is so can obtain s=3, t=3.Similarly, since P=2＜3, s=3, and t=3 so follow execution in step 510, adds 3 with K, L is added 3, and P is added 1.

At this moment, K=L=6, P=3.Then, repeated execution of steps 504 calculates 9 piece discrepancy measure that correspond to the 3rd 9 checkpoints on the main search window 604 (3).The 3rd main search window 604 (3) is with candidate checkpoint at this moment, that is is that checkpoint CP (6,6) is a central point.If pairing discrepancy measure BDM of checkpoint CP (9,9) (9,9) is minimum, then make BDM (9,9)=BDM that (K+s L+t), and is made as the candidate checkpoint with checkpoint CP (9,9) again.Because K=L=6 is so can obtain s=3, t=3.Afterwards, follow execution in step 506.Because P=3 is so then enter step 512.

In step 512, on auxiliary search window 606 (1), be to have 9 checkpoints, comprise a CP (9,9), CP (9,10), CP (9,8), CP (8,9), CP (8,10), CP (8,8), CP (10,9), CP (10,10) and CP (10,8).Auxiliary search window 606 (1) is the candidate checkpoint with this moment, that is is that checkpoint CP (9,9) is a central point.In this step, be to correspond to 9 piece discrepancy measure in 9 checkpoints, wherein, selecting pairing minimum of piece discrepancy measure is the purpose piece, in the hope of motion vector.Motion vector also is pairing point of the different measured value of minimal block difference and the formed vector of initial point.

Present embodiment has more the function that finishes (Early Termination) ahead of time.In the seek actions in first three step,, then enter the seek actions of final step ahead of time if the pairing checkpoint of smallest blocks difference measured value is to be positioned at central point.Please refer to Fig. 6 B, it shows one second example of the motion forecast method in the video coding of using present embodiment.When execution in step 504, calculating corresponds to after 9 piece discrepancy measure of the 2nd 9 checkpoints on the main search window 604 (2), if checkpoint CP (3,3) pairing discrepancy measure BDM (3,3) is minimum, then makes BDM (3,3)=and BDM (K+s, L+t).Because K=L=3 is so can obtain s=0, t=0.At this moment, when then carrying out 506 and 508, because s=t=0, the candidate checkpoint of this moment is the central point for the 2nd main search window 604 (2), so direct execution in step 512 directly enters the seek actions of final step.

That is to say, except the seek actions of final step, when the seek actions in per step finishes, be minimum words if be positioned at the piece discrepancy measure of checkpoint of the central point of search window, promptly take place to finish ahead of time, become 1 and go on foot big young pathbreaker by 3, and directly enter the seek actions of final step.If one of them pairing discrepancy measure of remaining 8 checkpoint beyond the central point of search window is minimum words, then the central point of search window of seek actions with next step moves to this checkpoint, and carry out next step seek actions, the rest may be inferred.

Certainly, what need illustrate is that the present invention also can be designed as does not have the function that finishes (EarlyTermination) ahead of time, thus, the present invention will become a method for searching with four search step, and wherein the step size of these four search step is respectively 3,3,3,1, and in first three search step, its search window has 7 * 7 points, and in the 4th search step, its search window has 3 * 3 points.

The motion of supposing the image in the real life can be found out by Fig. 6 A that for continuously the search window between the seek actions in adjacent two steps of present embodiment is ingenious joining.In the seek actions in per step, be continuously in the process of search window motion, and seamless existence.This represents that point can not omitted.The Search Area of this method is ± 10, and than four step search algorithms and three step search algorithms be that ± 7 Search Area is height.Therefore, present embodiment can forereach the image of (Catch) rapid movement, improves the probability that finds better motion vector, and then improves the quality of image compression.Counting of the need search of present embodiment is 17 to 27.

The foregoing description is to be 4 with step number, and going on foot big or small SS is that 3,3,3 and 1 length in pixels are that example is done explanation in regular turn, and right the present invention is not limited thereto.The present invention more can be according to the complexity of search area and calculating, and step number is adjusted into any integer greater than 1, very has elasticity.

Now further present embodiment and traditional four step search algorithms are compared as follows.Please refer to Fig. 7, it shows another example of four step of tradition search algorithm.Have a few though the search areas of traditional four step search algorithms can contain the institute of its Search Area, truly have the shortcoming of search area overlapping.For instance, suppose in the Search Area of seek actions in the 3rd step that the piece discrepancy measure is that minimum pairing checkpoint is point 402 (4), then the central point of next step seek actions will move to a little 402 (4).So, in the seek actions in the 4th step institute's point to be searched for around the point of putting 402 (4).And if in the seek actions in the 3rd step, piece discrepancy measure to be minimum pairing checkpoint be point 402 (3), then the central point of next step seek actions will move to a little 402 (3).So, in the seek actions in the 4th step institute's point to be searched for around the point of putting 402 (3), that is the point at triangle place as shown in Figure 7.As seen from Figure 7, be the search window of central point and be that the search window of central point is to have part to overlap to put 402 (4), that is be to put 402 (5) to put 402 (3).

Please refer to Fig. 8, it shows another example of the motion forecast method in the video coding of present embodiment.Suppose that in the seek actions in the 3rd step the piece discrepancy measure is that minimum pairing checkpoint is that then the central point of next step seek actions will move to a CP (9,9) or CP (6,6) when putting CP (9,9) or CP (6,6).So, institute's point to be searched is to be around the point of some CP (9,9) or around the point of CP (6,6) in the seek actions in the 4th step.As shown in Figure 8, do not repeat, make be the search window at center and be the part that the search window at center does not have overlapping with a CP (6,6) with a CP (9,9) around the point of some CP (9,9) and a point around some CP (6,6), and the continuous seamless crack.Hence one can see that, and the motion forecast method in the video coding of present embodiment can strengthen search area really, and can not omit any point in the Search Area.

In addition, if in order to increase Search Area, and be that the seek actions of the simple first step with four traditional step search algorithms repeat twice, also can't reach effect of the present invention.Now this kind algorithm is referred to as the 4-4-2-1 algorithm.Please refer to Fig. 9, it shows the schematic diagram of 4-4-2-1 algorithm.In the 4-4-2-1 algorithm, the first step and the step size of seek actions in second step are that the step size of the seek actions in 4, the three steps is 2, and the step size of the seek actions of final step is 1, its Search Area can be expanded to ± and 11.Though the scope of the Search Area of 4-4-2-1 algorithm is very big, yet the 4-4-2-1 algorithm does not have the characteristic that finishes ahead of time, and must carry out the piece coupling 34 times.Therefore, the 4-4-2-1 algorithm is the longest in the method for 4-4-2-1 algorithm, four step search algorithms and present embodiment required operation time.Very and, because the search window excessive (9 * 9) of the seek actions in the first step and second step, the situation of this kind checkpoint arrangement mode (Pattern) too sparse (sparse) is on the contrary easily with the wrong direction of search path guiding, and the phenomenon that the pairing discrepancy measure in easier generation checkpoint is local minimum, therefore, its image compression effect is poor than four step search algorithms on the contrary.Hence one can see that, and the operation time of the motion forecast method of use present embodiment is shorter than 4-4-2-1 algorithm, and the image quality of the compressed image of the motion forecast method of present embodiment is also good than 4-4-2-1 algorithm.

Now with four step search algorithms, three step search algorithms, 4-4-2-1 algorithms, and every comparison sheet of the motion forecast method of present embodiment list among Figure 10.

For present embodiment usefulness is assessed, the applicant used 5 test films (testsequence) come to four step search algorithms, three step search algorithms, 4-4-2-1 algorithm, and the motion forecast method of present embodiment test.5 above-mentioned test films comprise Salesman, Hall_mointor, Foreman, Carphone and Stefan test film, and its representative image is respectively shown in 10A-10E figure.Wherein, Salesman and Hall_mointor film are the films that belongs to static, and the image motion speed of Foreman and Carphone film is slightly fast, and the Stefan film then belongs to the film of image rapid movement.

Now with following four foundations as comparison:

(1) mean value of piece discrepancy measure

That is be when doing the piece coupling, the mean value of the smallest blocks difference measured value that is found. at every turnThis is representing the quality of the motion vector that algorithm finds, and mean value is the smaller the better.Please refer to Figure 12 A-12C, its be listed in respectively low under the Senior Three kind bit rate (bit-rate), four step search algorithms, three step search algorithms, 4-4-2-1 algorithm, and the comparison of the mean value of the piece discrepancy measure of the motion forecast method of present embodiment.By Figure 12 A-12C as can be known, when the method for present embodiment is applied to the image of microinching, the mean value of its piece discrepancy measure is suitable with other algorithm, and right when being applied to the image of rapid movement, the mean value of the piece discrepancy measure of present embodiment is littler than other algorithm.So as can be known, when the method for present embodiment was applied to the image of rapid movement, the quality of resulting motion vector had apparent improvement.

(2) average step number

That is be after finishing the seek actions of final step, needed average step number, its value of being is between 2-4.Average step number be in order to assessment with hardware realize four step search algorithms, three step search algorithms, 4-4-2-1 algorithm, and during the motion forecast method of present embodiment, needed search time, the value of average step number is the smaller the better.Please refer to Figure 13 A-13C, its be listed in respectively low under the Senior Three kind bit rate, four step search algorithms, three step search algorithms, 4-4-2-1 algorithm, and the comparison of the average step number of the motion forecast method of present embodiment.By Figure 13 A-13C as can be known, the average step number of the method for present embodiment is to be less than other three kinds of algorithms.

(3) average block matching times

That is be after finishing the seek actions of final step, needed average block matching times.The action that the block discrepancy measure of a checkpoint is calculated in block coupling system expression each time.The value of average block matching times is that this value is the smaller the better in order to the search time of assessment with above-mentioned each algorithm of hardware realization.Please refer to Figure 14 A-14C, its be listed in respectively low under the Senior Three kind bit rate, four step search algorithms, three step search algorithms, 4-4-2-1 algorithm, and the comparison of the average block matching times of the motion forecast method of present embodiment.By Figure 14 A-14C as can be known, present embodiment and four step search algorithms need 17 times to 27 times piece coupling, the number of times of the piece coupling that three step search algorithms need be fixed as 25 (=9+8+8) inferior, the number of times of the piece coupling that the 4-4-2-1 algorithm needs then be fixed as 33 (=9+8+8+8) inferior.

(4) error ratio (PSNR)

That is be under identical bits speed, the error ratio of the image that compressed and original image.The numerical value of error ratio is high more, and the film distortion rate after the expression compression is more little.Please refer to Figure 15 A-15E, it shows when testing with Salesman, Hall_mointor, Foreman, Carphone and Stefan test film respectively, the bit rate of the motion forecast method of four step search algorithms and present embodiment and the relation curve of error ratio.In Figure 15 A-15E, " Improved FSS " curve is the relation curve for present embodiment.As can be seen from Figure, when the method for using present embodiment was compressed the image of rapid movement, the error ratio of the method for present embodiment was to be better than four step search algorithms.

Of the present invention except the seek actions of final step, the number of times of the seek actions in former steps of the main search window of 7 * 7 points of use can be the n step, and n is the positive integer more than or equal to 1.Motion forecast method of the present invention can be used in the encoding process of the picture signal that a mobile phone will transmit or receive.The present invention can improve the image quality after the image compression of image quality, especially rapid movement of compressed image effectively.Search time required for the present invention lacks than other traditional algorithm, and uses the film distortion rate after the compression of the present invention also little than other traditional algorithm.

In sum; though the present invention discloses as above with a preferred embodiment; right its is not in order to limit the present invention; anyly have the knack of this skill person; without departing from the spirit and scope of the present invention; when can being used for a variety of modifications and variations, so protection scope of the present invention is as the criterion when looking accompanying the claim person of defining.

Claims

1. A motion prediction method in video coding, when encoding an original block of a current picture frame, the method is used to search for a target block that best matches the original block in a previous picture frame, the The method is to generate a motion vector required for coding the original block according to the relative position between the target block and the original block, the target block is defined by a plurality of points CP(I, J) included in a search area One of corresponding multiple blocks B (I, J), I, J are integers, and the motion prediction method includes:

(a) make parameter K=0, L=0, P=1, wherein K is the window center point abscissa parameter, L is the window center point ordinate parameter, and P is the number of execution steps;

(b) Set a Pth main search window, on which there are multiple checkpoints, including point CP(M, N), M=K+i, N=L+j, i, j=-3, 0, 3, and calculate the multiple block difference measurement values BDM(M, N) of these blocks respectively corresponding to these checkpoints of the P search window, define these block difference measurement values The minimum of is BDM(K+s, L+t), s, t are integers;

(c) judging whether P is equal to a main predetermined number of steps, if so, then execute step (f), if not, then execute step (c1);

(c1) judge whether s=t=0, if so, then execute step (f), if not, then execute step (d);

(d) Add s to K, add t to L, add 1 to P, and perform step (b); and

(f) Setting an auxiliary search window, on which there are multiple checkpoints, including point CP(M', N'), M'=K+u, N'=L+v, u, v=-1, 0, 1, and calculate multiple block difference measurement values BDM(M', N') of these blocks respectively corresponding to these checkpoints of the auxiliary search window, and select the smallest of these block difference measurement values The corresponding block is the target block.

2. The motion prediction method as claimed in claim 1, wherein the center point CP(0,0) of the search area corresponds to the block B(0,0) in the same position as the original block in the previous picture frame ).

3. The motion prediction method according to claim 1, wherein the method for calculating the block difference measurement value comprises: combining the image data of all pixels of the block in the previous picture frame corresponding to the checkpoint with the After the image data of all pixels of the original block are correspondingly subtracted and taken as absolute values, the sum is the block difference measurement value of the checkpoint.

4. The motion prediction method as claimed in claim 1, wherein the main predetermined step number is an integer greater than or equal to 1.

5. The motion prediction method as claimed in claim 1, wherein the main predetermined number of steps is equal to 3, -10<=I<=10, -10<=J<=10.

6. The motion prediction method as claimed in claim 1, wherein the motion prediction method is used in encoding processing of an image signal to be transmitted or received by a mobile phone.

7. A motion prediction method in video coding, when an original block of a current picture frame is encoded, the method is used to generate a motion vector required for encoding the original block, the motion prediction method includes :

(a0) generate a center point;

(a) Perform a first-step search action with a step size of 3, wherein a main search window with 7x7 points is generated centered on the center point, and checkpoints in the main search window are calculated a plurality of block difference measurement values corresponding to them, and setting the checkpoint corresponding to the smallest of these block difference measurement values as a candidate checkpoint;

(a1) judging whether the candidate checkpoint set in step (a) is the center point of the first main search window, if yes, execute step (c), if not, execute step (b);

(b) Executing a second search operation with a step size of 3, wherein a second main search window with 7x7 points is generated with the candidate checkpoint set in step (a) as the center point , and calculate a plurality of block difference measurements corresponding to a plurality of checkpoints in the second main search window, and the checkpoint corresponding to the smallest of these block difference measurements in the second step of the search action Set as the candidate checkpoint; (b1) judge whether the candidate checkpoint set in step (b) is the center point of the second main search window, if yes, execute step (c), if not, then Execute step (b2);

(b2) Execute a third search action with a step size of 3, wherein a third main search window with 7x7 points is generated with the candidate checkpoint set in step (b) as the center point, And calculate a plurality of block difference measurement values corresponding to the plurality of checkpoints in the third main search window, and set the checkpoint corresponding to the smallest of these block difference measurement values in the third step of the search action to as the candidate checkpoint; and

(c) Execute a final search action with a step size of 1, wherein an auxiliary search window with 3x3 points is generated with the candidate checkpoint set in step (b2) as the center point, and calculates Multiple block difference measurement values corresponding to multiple checkpoints in the auxiliary search window, and the checkpoint corresponding to the smallest of these block difference measurement values in the last search action is set as the candidate checkpoint , to obtain the motion vector according to the set candidate checkpoint and the center point generated in the step (a0).

8. The motion prediction method according to claim 7, wherein the method for calculating the block difference measurement value comprises: comparing the image data of all pixels of the block in the previous picture frame corresponding to the checkpoint with the original After the image data of all the pixels of the block are correspondingly subtracted and taken the absolute value, the sum is the block difference measurement value of the checkpoint.

9. The motion prediction method according to claim 7, wherein said motion prediction method is used in an encoding process of an image signal to be transmitted or received by a mobile phone.

10. A motion prediction method in video coding. When encoding an original block of a current picture frame, the method is used to search for a target block that best matches the original block in a previous picture frame. The method generates a motion vector required for coding the original block according to the relative position between the target block and the original block, and the target block is one corresponding to multiple points CP(I, J) included in the search area One of the blocks B (I, J), where I and J are integers, and the motion prediction method includes:

(b) Set a Pth main search window on which there are multiple checkpoints, including point CP(M, N), M=K+1, N=L+j, i , j=-3, 0, 3, and calculate the multiple block difference measurement values of these blocks respectively corresponding to these checkpoints of the P search window, and define the minimum among these block difference measurement values as BDM(K +s, L+t), said s and t are integers;

(c) judge whether P is equal to a main step number, if so, then execute step (f), if not, then execute step (d);

(d) adding s to K, t to L, and 1 to P, and performing step (b); and

(f) Set an auxiliary search window on which there are multiple checkpoints, including point CP(M', N'), M'=K+u, N'=L+v, u, v =-1, 0, 1, and calculate the multiple block difference measurement values BDM(M', N') of these blocks respectively corresponding to these checkpoints of the auxiliary search window, and select the smallest of these block difference measurement values The corresponding block is the target block.

11. The motion prediction method as claimed in claim 10, wherein the center point CP(0,0) of the search area is the block B(0,0) corresponding to the same position as the original block in the previous picture frame ).

12. The motion prediction method according to claim 10, wherein the method for calculating the block difference measurement value comprises: comparing the image data of all pixels of the block in the previous picture frame corresponding to the checkpoint with the original After the image data of all the pixels of the block are correspondingly subtracted and taken the absolute value, the sum is the block difference measurement value of the checkpoint.

13. The motion prediction method as claimed in claim 10, wherein the motion prediction method is used in encoding processing of an image signal to be transmitted or received by a mobile phone.