CN101877790B - Panoramic video coding-oriented quick global motion estimation method - Google Patents

Abstract

The invention discloses a panoramic video coding-oriented quick global motion estimation method. The method comprises two steps of: 1, using a brightness residual threshold value model, which is based on the combination of statistic characteristics and mean of threshold values, to approximately divide a local motion area and a global motion area, and obtaining an approximate set of a global motion estimation area; and 2, adopting the motion vector residual grading threshold value technology to gradually detail the set of global motion pixels in a minimum iterative process of the energy residual function and finally separating the complete global motion area so as to achieve an aim of quick motion estimation. The method has the advantages of taking both accuracy and robustness of the global motion estimation into consideration, greatly saving cost of calculating the motion estimation under the condition of ensuring the quality of the re-constructed image does not decline, but is improved a little bit, and having effects of low algorithm complexity and accurate estimation of motion parameters on the global motion estimation of the panoramic video sequence.

Description

A kind of quick global motion estimation method towards panorama video code

Technical field

The present invention relates to a kind of image video encoding compression technology, specifically a kind of quick global motion estimation method towards panorama video code.

Background technology

Panoramic video is widely used in the application such as sports cast, three-dimensional movie, multipart video-meeting.One width of cloth panoramic picture is to do rotation or convergent-divergent motion by the flake video camera of six or octahedral around fixing axle; The same time domain of scene around the video camera is taken the photo of different azimuth; Technological seamless spliced these photos with " stitchings ", again according to cylinder or the sphere mapping algorithm is mapped to cylinder figure or spherical diagram forms.Therefore, the resolution of panoramic picture is in general than higher, and the motion details is abundanter.And because panoramic video be in order to let the user have reality scene to experience, the camera motion of general virtual support reappears, and therefore, global motion and the local motion characteristic of interlocking is more obvious.Moreover cylinder and sphere mapping algorithm can cause the object of which movement distortion, make the difficulty of estimation strengthen.But simultaneously; We can find from the analysis of two dimensional surface coordinate mapping cylinder areal coordinate and spherical coordinate; The motion deformation of panoramic picture object on cylinder or sphere mainly shows as the deformation that motion is cut in video camera rotation, convergent-divergent, mistake; Therefore, we can use global motion model to come panoramic video is carried out the overall motion estimation compensation.

But research in the past shows that overall motion estimation exists the big problem of amount of calculation.The overall motion estimation key is the estimation to global motion model parameters.In theory, for a definite global motion parameter model, like affine six movement parameter models, only the motion vector of 3 background pixel points of need can be tried to achieve the value of six kinematic parameters.But general motion vector method can only obtain the limited motion vector of precision; If only estimate global motion model parameters with seldom several pixel motion vector; The precision as a result that obtains is very low, therefore needs more pixel motion vector to participate in global motion model parameters and estimates to improve accuracy.Like this, parameter Estimation has just become a problem of separating the inconsistent equation group, and available least square method is found the solution, like Gauss's Newton iteration method.Through the several iterative computation group of solving an equation, to the last the global motion model parameters value converges on a comparatively stable value.But this iterative process is the highest part of computation complexity in the overall motion estimation, especially when the global motion model of need handling comparatively complicated, under the more situation of iterations.

Moreover; Most video scene all includes global motion and local motion; If let all pixel motion vector all participate in overall motion estimation; Pixel and the bigger pixel of estimation of motion vectors error of then making local motion can produce very big interference to overall motion estimation, make motion model parameters estimate just to be converged on a stationary value many times by iteration.Not only reduce the precision of overall motion estimation, and made computational complexity raise greatly.

Pixel in the local motion zone, we are called exterior point, the global motion pixel, we are called interior point.The emphasis of the quick global motion estimation method that we will study effectively splits the local motion zone from the view picture image exactly, makes the global motion zone comprise interior point as much as possible and the least possible exterior point.Key and the difficult point of distinguishing exterior point and interior point are confirming of threshold value T.In some document; T is set to a fixing value (being referred to as the fixed threshold method); But often be difficult to find a suitable fixed threshold T to be competent at: if T is too little in whole iterative process; Iterative process converges on the part that needs the local motion zone probably at the very start, when especially the local motion zone accounts for the large percentage of whole scene; When iteration finished if T is too big, the global motion pixel is misjudged some was the local motion point, thereby influences the accuracy of parameter Estimation greatly.Some document is mentioned with percentage threshold r% and is replaced threshold value T (being referred to as the fixed percentage threshold method), even the exterior point set is the set of the bigger r% pixel of residual values.But the scale that accounts for whole scene owing to global motion zone in the different video is all inequality, and therefore this method or the global motion that can only obtain part are regional, or in interior some set, can comprise a lot of exterior points.There is the scholar to propose a kind of improved method: to make the average (be referred to as residual error average threshold method) of threshold value T for the residual error of all pixels; But the residual error averaging method might not be portrayed the difference of global motion zone and local moving region well, and experimental result also is illustrated in this in some cases method possibly make interior some set converge on the local motion zone.

Above-mentioned these inner regions confirm that method is difficult to take into account the accuracy and the robustness of parameter Estimation, and often need to select a desirable threshold value in advance to different video scenes, and adaptability is relatively poor.

Summary of the invention

The purpose of this invention is to provide a kind of global motion estimating method of cutting apart global motion zone and local moving region fast towards panorama video code.

The technical scheme that the present invention solves the problems of the technologies described above is:

A kind of quick global motion estimation method towards panorama video code, this method were divided into for two steps to carry out: the first step, carry out the brightness residual threshold method; It further may further comprise the steps:

1-1 is divided into the piece of non-overlapping copies to entire image, and block size is 16 * 16, to the estimation of taking exercises of each piece, obtains the motion vector (Δ x, Δ y) of each piece with block matching algorithm;

1-2 uses the motion vector (Δ x, Δ y) that obtains among the step 1-1 to the compensation of taking exercises of each piece of present frame, obtains the predicted value I of each pixel of present frame _k

1-3, the gradient mean S of all pixels in the calculating current block, wherein,

And the gradient mean S ' of all pixels in the corresponding blocks in reference frame,

Compare the size of S and S ' residual absolute value, also be | S-S ' | account form is formula (1), promptly $G_B=\underset{i=1}{\overset{m}{\mathrm{\Σ}}}\underset{j=1}{\overset{n}{\mathrm{\Σ}}}|S_{i,j}-S_{i,j}^{\′}|/m\×n,$ M * n is a block size;

1-4, calculated threshold C _g, threshold value C _gConfirm according to formula (2), promptly

In the formula, N is the number that image is divided into the piece of non-overlapping copies, G _iBe brightness residual according to i piece in the image of formula (1) calculating, Represent the brightness residual average of present frame; If the brightness residual G of current block _BLess than C _g, then current block is judged as the local motion region unit, from the global motion set of macroblocks, rejects away;

Second step, carry out motion vector residual error classification thresholds method, specifically comprise:

2-1 uses block matching algorithm to estimate the local motion displacement of each piece of present frame, obtains the local motion vector (Δ x, Δ y) of each piece;

2-2; Estimate motion model parameters: the size of choosing the image upper left corner, the upper right corner, three 48 * 48 image-regions in the lower left corner is the initialization input value of the motion vector of 16 * 16 central block as Gauss's Newton iteration estimation model parametric procedure first time; Through Gauss's Newton iterative calculation, draw initialized several motion model parameters values;

2-3, the global motion vector of each piece in the computed image (Δ x ', Δ y '): in the image; The motion of the piece of background area belongs to global motion, and the motion of the piece of foreground area belongs to local motion, through in the motion model parameters value substitution Gauss again Newton iteration that obtains in the last step; (x, value y) calculate the global motion vector of each piece respectively based on the coordinate of each piece central pixel point; For the local motion piece, this motion vector is pseudo-global motion vector;

2-4, the calculating kinematical vector residual error: for same, the motion vector (Δ x ', Δ y ') of this piece that draws among the motion vector (Δ x, Δ y) of this piece that draws step 2-1 and the step 2-3 is made variance;

2-5; Percentage threshold is set gets rid of the local motion piece: adopt the percentage threshold P of hierarchical subtractive clustering to come progressively meticulous global motion zone; The motion vector threshold residual value T that a hierarchical subtractive clustering is set simultaneously judges whether this iteration can finish, and in first time iterative process, the initial value that P is set is 50; It is 0.04 that T is set simultaneously, and computing formula does $\sqrt{{(\mathrm{\Δ\; x}-{\mathrm{\Δ\; x}}^{\′})}^2+{(\mathrm{\Δ\; y}-{\mathrm{\Δ\; y}}^{\′})}^2}>T;$

Be labeled as the local motion piece to the piece of the P percentage that is no more than image block number summation at most that satisfies the following formula condition, the remaining global motion piece that is labeled as is as the set of blocks of overall motion estimation iterative computation next time; If the motion vector residual error of all pieces does not satisfy the following formula condition in this overall motion estimation set of blocks; Then finish this iteration; Generate final motion model parameters, simultaneously can be partitioned into the local motion zone according to the local motion set of blocks of each iteration institute mark; The rule of successively decreasing of P and T: before getting into the iterative computation of a new round, P is updated to 1/4th of P at every turn, T is updated to T=T-0.01; After Gauss's Newton iteration finishes for the first time, with obtaining a new cover motion model parameters value, the input value of this cover motion model parameters value as next round Gauss Newton iteration;

2-6, repeating step 2-3 to 2-5 equals 4 less than T or iterations up to the motion vector residual error of all pieces, then the finishing iteration process.

Description of drawings

Fig. 1 is the quick global motion estimation algorithm flow chart of the present invention towards panorama video code.

Embodiment

Below in conjunction with embodiment the present invention is further described:

Practical implementation of the present invention is carried out in two steps:

1. the first step is carried out the brightness residual threshold method.

When the utilization recurrent least square method was estimated global motion, the initialization input value was the motion vector that each macro block obtains after estimating through block matching motion in the image.The motion vector that is in the macro block in local motion zone does not belong to the set of point in the global motion; It is the exterior point that the global motion parameter Estimation is caused interference; Will consume a large amount of operation time. therefore; If when using block matching algorithm to carry out estimation, just can carry out anticipation to the attribute of macro block estimation, find in advance may disturb the macro block of overall motion estimation and reject, will inevitably reduce the amount of calculation of overall motion estimation greatly.

Analysis to video image can find that the texture in global motion zone is than horn of plenty; And local motion generally is positioned at texture gray scale unanimity or the extremely level and smooth zone of gray scale.This is that comparatively speaking, the brightness residual between primitive frame and the reference frame corresponding blocks also seldom because the movable information that the local motion zone is comprised is fewer.Therefore; The monochrome information of the present invention after through the macro block motion compensation comes each macro block is carried out preanalysis; To judge whether this macro block belongs to the local motion macro block, if then before carrying out overall motion estimation, from the global motion set of macroblocks, reject away this macro block; To save the computing cost of overall motion estimation, improve the precision of overall motion estimation.

This algorithm is divided into following four steps:

1) be divided into entire image the piece of non-overlapping copies, block size is 16 * 16, to the estimation of taking exercises of each piece, obtains the motion vector (Δ x, Δ y) of each piece with block matching algorithm.In theory, block size is more little, and motion estimation result is accurate more, an opposite extreme situations, and when block size is a pixel, then motion estimation result is the most accurate.But so, the complexity of estimation will raise greatly, need the motion vector bit number of coding transmission also more.16 * 16 of this algorithm use are taken into account and are considered computation complexity and estimation accuracy.Simultaneously, estimate that what we adopted is that three step search quick motions are estimated, further reduces the complexity of estimation for block matching motion.The motion vector (Δ x, Δ y) of each piece that obtains through block matching algorithm needs preserve, imports as the initialization of the second link motion vector residual error classification thresholds method of execution.

2) use last one to go on foot motion vector (Δ x, Δ y) that block matching algorithm obtains, obtain the predicted value I of each pixel of present frame the compensation of taking exercises of each piece of present frame _kBecause (Δ x, Δ y) representative is because the caused by movement interframe of object local motion displacement MV own ₁, do after the inter motion compensation, then can passing threshold current frame pixel (i, brightness I j) _kWith in the next frame ((i, j)+MV ₁) brightness of position pixel

Difference judge that (i j) is global motion area pixel or local motion area pixel to current frame pixel.

3) the gradient mean S of all pixels in the calculating current block; Wherein, The gradient mean S ' of all pixels in

and the corresponding blocks in reference frame; Wherein, compares the size of S and S ' residual absolute value, also is | S-S ' |.Be shown below:

$G_B=\underset{i=1}{\overset{m}{\mathrm{\Σ}}}\underset{j=1}{\overset{n}{\mathrm{\Σ}}}|S_{i,j}-S_{i,j}^{\′}|/m\×n---\left(1\right)$

In formula, m * n is a block size.

4) calculated threshold C _gThreshold value C _gConfirm according to following formula:

$C_g=k\·\frac{1}{N}\underset{i=1}{\overset{N}{\mathrm{\Σ}}}{G}_i---\left(2\right)$

In the formula, N is the number that image is divided into the piece of non-overlapping copies, G _iBe the brightness residual (calculating) of i piece in the image according to formula 1,

Represent the brightness residual average of present frame.If the brightness residual G of current block _BLess than C _g, then current block is judged as the local motion region unit, from the global motion set of macroblocks, rejects away.Consider threshold value critical point C _gValue excessively will cause global motion parameter Estimation failure, we confirm that the value of k in the formula 2 is: under low code check situation, like the video sequence of encode CIF, QCIF form, k=1.1; Under high code check situation, like coding 4CIF, high definition, panoramic video sequence, k=1.2 also promptly is shown below:

C _g=1.1G _Av, under the low code check situation

(3)

C _g=1.2G _Av, under the high code check situation

2. in second step, carry out motion vector residual error classification thresholds method.

Motion vector residual error ratio juris mainly is based on the difference of global motion vector and local motion vector, is the key point of this method to the tolerance of this difference.The present invention adopts a kind of classification thresholds method to realize the accurate division of this tolerance.The main thought of this algorithm is: in the starting stage of iteration, remove the exterior point of the overwhelming majority earlier with a big percentage threshold.Because at the beginning; The ratio that the exterior point that differs greatly with interior point accounts in image is maximum (local motion zone particularly; Often comparatively significantly kinetic property difference is arranged) with the global motion zone; Adopt the big percentage threshold can to remove the big exterior point of these othernesses rapidly, in case got rid of the interference of the bigger exterior point of otherness earlier, then whole iterative process restrains sooner; After the iteration, obtained a rough overall motion estimation result for the first time, the pending exterior point that be left in the image this time is and the interior some pixel that difference is less; The ratio that in image, accounts for is little; In ensuing iteration several times, we can classification reduce the value of percentage threshold, get rid of the little exterior point of these othernesses gradually; The accurately set of point in the refinement, some set in all excluding exterior point as much as possible.The specific algorithm step is following:

1) use block matching algorithm to estimate the local motion displacement of each piece of present frame.This step is carried out in the threshold method of a last link-based on brightness residual.

2) estimate motion model parameters.Consider that the global motion zone generally concentrates on image background regions; Edge of image part just; We choose the motion vector of central block (block size is 16 * 16) of the image upper left corner, the upper right corner, three 48 * 48 image-regions in the lower left corner as the initialization input value of Gauss's Newton iteration estimation model parametric procedure first time; Through Gauss's Newton iterative calculation, can draw initialized several motion model parameters values.

3) global motion vector of each piece (Δ x ', Δ y ') in the computed image.In the image; The piece motion of background area belongs to global motion; And the piece of foreground area motion belongs to local motion, but we still can be through in the motion model parameters value substitution Gauss again Newton iteration that obtains in the last step, according to the coordinate (x of each piece central pixel point; Y) value calculates respectively " global motion vector " of each piece.For the local motion piece, this motion vector is pseudo-global motion vector.

4) calculating kinematical vector residual error.For same, the motion vector (Δ x ', Δ y ') of this piece that draws in the motion vector (Δ x, Δ y) of this piece that draws step (1) and the step (3) is made variance, shown in formula 4.The purpose of calculating kinematical vector residual error is for the actual motion vector of judging this block of pixels and the difference of global motion vector, if the motion vector residual error is bigger, explain that this piece probably is the local motion piece, otherwise this piece probably is the global motion piece.

5) percentage threshold is set and gets rid of the local motion piece.We adopt the percentage threshold P of a hierarchical subtractive clustering to come progressively meticulous global motion zone, and the motion vector threshold residual value T that a hierarchical subtractive clustering is set simultaneously judges whether this iteration can finish.In first time iterative process, the initial value that we are provided with P is 50.It is 0.04 that T is set simultaneously, that is:

$\sqrt{{(\mathrm{\Δx}-{\mathrm{\Δx}}^{\′})}^2+{(\mathrm{\Δy}-{\mathrm{\Δy}}^{\′})}^2}>T---\left(4\right)$

Be labeled as the local motion piece to the piece of the P percentage that is no more than image block number summation at most that satisfies the following formula condition, the remaining global motion piece that is labeled as is as the set of blocks of overall motion estimation iterative computation next time.If the motion vector residual error of all pieces does not satisfy the following formula condition in this overall motion estimation set of blocks; Then finish this iteration; Generate final motion model parameters, simultaneously can be partitioned into the local motion zone according to the local motion set of blocks of each iteration institute mark.The rule of successively decreasing of P and T: before at every turn getting into the iterative computation of a new round, P is updated to 1/4th (P=P/4) of P, promptly for the second time in the iterative process; P is made as 12.5, and in the iterative process, P is made as 3.125 for the third time ... This is because of the increase along with iterations; Interior some set more and more tends towards stability; The exterior point that is comprised is fewer and feweri, so the P value needs linear decrease, in order to avoid iteration convergence is in the part of interior some set.Simultaneously T is updated to T=T-0.01, because after each iteration end, the motion vector residual error of remaining piece is littler, wherein some is the local motion piece littler with the global motion attribute difference for this, need differentiate them with a littler T.When the iteration result tends to stable, can reach the quickening iteration convergence simultaneously with the T that successively decreases, lower computation complexity and guarantee the progressively meticulous purpose of overall motion estimation result.After Gauss's Newton iteration finishes for the first time, with obtaining a new cover motion model parameters value.The input value of this cover motion model parameters value as next round Gauss Newton iteration.

6) repeating step 3), 4), 5), all equal 4 up to the motion vector residual error of all pieces, then the finishing iteration process less than T or iterations.Experiment showed, that working as iterations surpasses 4 times, the accuracy increase of separating of model parameter is extremely limited; That is to say; 4th, the result of the 5th, the 6th iteration is very approximate, even is as good as, model parameter separate a limit that has reached this classification thresholds iterative method accuracy.

It should be noted last that above embodiment is only unrestricted in order to technical scheme of the present invention to be described.Although the present invention is specified with reference to embodiment; Those of ordinary skill in the art is to be understood that; Technical scheme of the present invention is made amendment or is equal to replacement, do not break away from the spirit and the scope of technical scheme of the present invention, it all should be encompassed in the claim of the present invention.

Claims (1)

1. quick global motion estimation method towards panorama video code is characterized in that: this method was divided into for two steps and carries out:

1 first step is carried out the brightness residual threshold method; It further may further comprise the steps:

1-1 is divided into the piece of non-overlapping copies to entire image, and block size is 16 * 16, to the estimation of taking exercises of each piece, obtains the motion vector (Δ x, Δ y) of each piece with block matching algorithm;

1-2 uses the motion vector (Δ x, Δ y) that obtains among the step 1-1 to the compensation of taking exercises of each piece of present frame, obtains the predicted value I of each pixel of present frame _k

1-3, the gradient mean S of all pixels in the calculating current block, wherein,

And the gradient mean S ' of all pixels in the corresponding blocks in reference frame,

Compare the size of S and S ' residual absolute value, also be | S-S ' |, account form is formula (1), promptly $G_B=\underset{i=1}{\overset{m}{\mathrm{\Σ}}}\underset{j=1}{\overset{n}{\mathrm{\Σ}}}|S_{i,j}-S_{i,j}^{\′}|/m\×n,$ M * n is a block size;

1-4, calculated threshold C _g, threshold value C _gConfirm according to formula (2), promptly

In the formula, N is the number that image is divided into the piece of non-overlapping copies, G _iBe brightness residual according to i piece in the image of formula (1) calculating,

Represent the brightness residual average of present frame; If the brightness residual G of current block _BLess than C _g, then current block is judged as the local motion region unit, from the global motion set of macroblocks, rejects away;

Second step, carry out motion vector residual error classification thresholds method, specifically comprise:

2-1 uses block matching algorithm to estimate the local motion displacement of each piece of present frame, obtains the local motion vector (Δ x, Δ y) of each piece;

2-2; Estimate motion model parameters: the size of choosing the image upper left corner, the upper right corner, three 48 * 48 image-regions in the lower left corner is the initialization input value of the motion vector of 16 * 16 central block as Gauss's Newton iteration estimation model parametric procedure first time; Through Gauss's Newton iterative calculation, draw initialized several motion model parameters values;

2-3, the global motion vector of each piece in the computed image (Δ x ', Δ y '): in the image; The motion of the piece of background area belongs to global motion, and the motion of the piece of foreground area belongs to local motion, through in the motion model parameters value substitution Gauss again Newton iteration that obtains in the last step; (x, value y) calculate the global motion vector of each piece respectively based on the coordinate of each piece central pixel point; For the local motion piece, this motion vector is pseudo-global motion vector;

2-4, the calculating kinematical vector residual error: for same, the motion vector (Δ x ', Δ y ') of this piece that draws among the motion vector (Δ x, Δ y) of this piece that draws step 2-1 and the step 2-3 is made variance;

2-5; Percentage threshold is set gets rid of the local motion piece: adopt the percentage threshold P of hierarchical subtractive clustering to come progressively meticulous global motion zone; The motion vector threshold residual value T that a hierarchical subtractive clustering is set simultaneously judges whether this iteration can finish, and in first time iterative process, the initial value that P is set is 50; It is 0.04 that T is set simultaneously, and computing formula does $\sqrt{{(\mathrm{\Δ\; x}-{\mathrm{\Δ\; x}}^{\′})}^2+{(\mathrm{\Δ\; y}-{\mathrm{\Δ\; y}}^{\′})}^2}>T;$

Be labeled as the local motion piece to the piece of the P percentage that is no more than image block number summation at most that satisfies the following formula condition, the remaining global motion piece that is labeled as is as the set of blocks of overall motion estimation iterative computation next time; If the motion vector residual error of all pieces does not satisfy the following formula condition in this overall motion estimation set of blocks; Then finish this iteration; Generate final motion model parameters, simultaneously can be partitioned into the local motion zone according to the local motion set of blocks of each iteration institute mark; The rule of successively decreasing of P and T: before getting into the iterative computation of a new round, P is updated to 1/4th of P at every turn, T is updated to T=T-0.01; After Gauss's Newton iteration finishes for the first time, with obtaining a new cover motion model parameters value, the input value of this cover motion model parameters value as next round Gauss Newton iteration;

2-6, repeating step 2-3 to 2-5 equals 4 less than T or iterations up to the motion vector residual error of all pieces, then the finishing iteration process.

Images