CN101827264A - Hierarchical self-adaptive video frame sampling method - Google Patents

Abstract

The invention discloses a hierarchical self-adaptive video frame sampling method. When in video shoot, the video cannot carry out frame sampling by using a fixed interval due to non-uniform camera motion. The method comprises the following steps of: establishing a mathematic model on the relation between an inter-frame overlap rate and a frame interval; estimating the overlap rate between two video frames through the image registration technology; self-adaptively regulating the interval of the sampling by using the mathematic model; only extracting less parts of video frame to be detected; and updating the mathematic model according to the detection result. The model can track the change of the camera motion to determine the position of the sampling frame and reduce the number of detecting frames without detecting frame by frame. When the expected overlap rate is smaller, the overlap rate can be reduced layer by layer by adopting a method of hierarchical sampling-reduction. The method greatly reduces the calculation consumption of the sampling and reserves all scene information in the video.

Description

The video frame sampling method of hierarchical self-adaptive

Technical field

The present invention relates to Digital Image Processing and computer vision field, particularly relate to and to carry out in the down-sampled application frame of video.

Background technology

Along with the development of hardware device, the same easy acquisition of video with image.The information that continuous video comprises is more, and the selectivity of picture frame is also more.But in much to video data, the Duplication of the identical content of adjacent video frames has very high redundancy up to 90%.If each frame data is all handled, can significantly increase the amount of calculation of handling, reduce treatment effeciency.For example in the image splicing, 3 D scene rebuilding during virtual reality etc. are used, only needs to guarantee that the Duplication between adjacent image is just passable about 50%, and Duplication is too high can to reduce last realization effect sometimes on the contrary.

In order to reduce the video data redundancy, the down-sampled step of frame of video is inevitable.Because in capture video, the motion of camera is irregular, the camera that has is to have machine control to carry out uniform motion, and the camera that has then is motion random in user's hand, can say without any rule.In this case, satisfy the scope of application need by Duplication with the down-sampled rear video frame that can't guarantee to sample of fixing sampling interval.How efficient accurately realization the down-sampled of frame of video is problem demanding prompt solution.

Now, the down-sampled method of Chang Yong frame of video mainly contains:

1) video is decomposed into the image of a frame one frame, artificial then samples to image sequence.

Though this method reliability is higher, needs man-machine interactively, the frame per second of supposing video was 30 frame/seconds, and the video of a few minutes just has thousands of frame of video so, and the time cost that screens cost with artificial method is too high.

2) calculating Duplication by the method that detects frame by frame samples.

This method fully automatically detects video sequence frame by frame, extracts the frame of video that meets the demands.The method of calculating the interframe Duplication can be with calculating global vector, methods such as image registration.But owing to detect frame by frame, amount of calculation is still very high.

Through the overtesting discovery, a lot of in fact frame of video need not detect fully, directly skip to get final product.But how to select those bigger frame of video of possibility just to become a subject matter of research.

Summary of the invention

The problem to be solved in the present invention is exactly how to reduce unnecessary frame to detect, and only detects the higher candidate frame of those possibilities, thereby reduces the amount of calculation of sampling, does not influence the effect of sampling simultaneously again.

This paper has proposed the method that new hierarchical self-adaptive extracts key frame.By " prediction-check-correction " model, the motion of dynamic tracking camera, the adjacent video frames Duplication of bringing according to camera motion change to be extracted some frames adaptively and detects, and determines whether it is key frame, and need not to compare frame by frame, reduced computation complexity.In order to prevent in the camera motion sudden change, to lose some main information frames, we carry out the sampling of layering: we conservatively extract key frame with big Duplication when ground floor extracts, then these key frames are done the extraction of the second layer, further reduced redundant.Certainly, if camera motion is comparatively steady, only the sampling with ground floor can be drawn into the key frame that satisfies the Duplication scope fully.Test shows that this method has kept main information frame, has reduced simultaneously and has calculated redundancy, has improved efficient.

Usually when taking the video data of splicing, in order to guarantee to splice success and splicing effect, translation (translation), yawing (pan) and pitching (tilt) motion are mainly carried out in the motion of camera, avoid camera lens to stretch as far as possible and rotatablely move.So the motion of camera can be thought mainly by the linear superposition of translation, yawing and three kinds of forms of motion of pitching.

Define two width of cloth image I ₀, I ₁Between Duplication R be the ratio of overlapping region and image area (two image sizes are identical in the video), promptly

$R=\frac{\mathrm{Co}\_\mathrm{area}}{\mathrm{area}\left(I_0\right)}=\frac{\mathrm{area}\left(I_0\right)\∩\mathrm{area}\left(I_1\right)}{\mathrm{area}\left(I_0\right)}---\left(1\right)$

Discuss in the motion process of camera below, the Duplication of two two field pictures is situation over time.

Suppose the width of the frame of video that camera is taken and highly be respectively W, H.The very short time period (0, T) in, camera is key frame F in 0 position constantly _k, be frame F in the position of moment t _tThen along with the motion of camera, frame of video F _tWith key frame F _kThe variation of overlapping region as follows:

When camera is done translational motion, short time period (0, can think uniform motion in T), speed is v, the angle of the direction of motion and horizontal plane is

As shown in Figure 1.

Frame F _kAnd F _tBetween the overlapping region area be

The value of t is very little, vt＜＜W, vt＜＜H, so formula (2) can be approximated to be:

Be spaced apart under the situation of fixed value Δ T key frame F at every frame shooting time _kThe n frame F of back _KnWith F _kBetween Duplication be:

Short time period (0, T) in,

Think constant with v.So as can be seen, frame F from formula (4) _KnWith key frame F _kDuplication R along with frame period n evenly reduces, promptly R is the linear function of n.

When camera when fixing point is done yawing (pan) and pitching (tilt) motion, interframe Duplication situation of change in time should be identical, just one is in the horizontal direction, one in vertical direction.Here we discuss camera yawing motion (pan).

The very short time period (0, think that camera is with the angular velocity omega uniform rotation in T).0 to moment t, camera is from frame F from constantly _kMove to frame F _t, scanned angle is ω t.The camera perspective of picture traverse W correspondence is θ, as shown in Figure 2.When ω t hour, frame F _kWith frame F _tBetween the overlapping region area be

$\mathrm{Co}\_\mathrm{area}\left(t\right)\≈H*(W-\frac{W/2}{\sin (\mathrm{\θ}/2)}*\mathrm{\ωt})=H*W-H*\frac{W}{2\sin (\mathrm{\θ}/2)}*\mathrm{\ωt}---\left(5\right)$

Be spaced apart under the situation of fixed value Δ T key frame F at every frame shooting time _kThe n frame F of back _KnWith F _kBetween Duplication be:

$R=\mathrm{Co}\_\mathrm{area}(n*\mathrm{\ΔT})/\mathrm{area}\left(I_0\right)=1-\frac{\mathrm{\ω}*n*\mathrm{\ΔT}}{2\sin (\mathrm{\θ}/2)}---\left(6\right)$

Short time period (0, T) in, ω thinks constant, the θ of each camera correspondence also is a fixed value.So as can be seen, frame F from formula (6) _KnWith key frame F _kDuplication R along with frame period n evenly reduces, promptly R is the linear function of n.

According to the discussion of front, when camera was in certain single forms of motion in translation, yawing and three kinds of motions of pitching respectively, in the very short time period, Duplication R can be similar to the linear function of regarding frame period n as.In the camera motion based on the linear superposition of these three kinds of forms of motion, Duplication R still can be approximated to be the linear function of frame period n so.

We can infer the pairing frame period n of the frame that satisfies certain Duplication R according to the linear relationship of R and n.If known up-to-date key frame F _k, itself and last key frame F _K-1Duplication and frame period be respectively R _kAnd N _k, then with F _kDuplication be expectation Duplication R _sFrame F _K+1With F _kFrame period N _K+1Can estimate with the linear relationship of R and n:

Frame period 0 N _kN _K+1

Duplication 1 R _kR _K+1

$\frac{N_k-0}{R_k-1}=\frac{N_{k+1}-0}{R_{k+1}-1}\}$

R _k+1＝R _s

N is arranged _K+1=N _k* (1-R _s)/(1-R _k) (7)

The N that calculates _K+1Differing is decided to be integer, and we get N _K+1Integer part [N _K+1] as the frame period of wait to sample frame and current key frame.

Because camera is not uniform motion completely in short time period, so predicted value and actual value are not on all four, according to [N _K+1] the key frame F that gets of frame period _K+1With F _kDuplication R _K+1Generally be not to equal to expect Duplication R _sSo work as R _K+1At certain interval (R _Tl, R _Th) in, we just think F _K+1Estimation be correct.

Each candidate frame F _nHave three parameters, with the Duplication R of last key frame _n, mate the M that counts _nWith frame period N _nKey frame constraints has: the upper and lower bound of Duplication is respectively R _ThAnd R _Tl, the lower bound that coupling is counted is M _Tl, the upper bound of frame period is N _ThHave only three parameters of candidate frame all to satisfy under the situation of its constraints, this frame is just thought effective key frame, otherwise abandons this frame, chooses candidate frame again according to correction model.

Because the frame per second of capture video is different with the movement velocity of camera, largest frames is N at interval _ThDetermine it is the comparison difficulty, our initialization N here _Th=N _S=scale*FPS (scale＜1, FPS is a video frame rate).In the process of sampling, suppose that the average in sampling interval is N so far _Mean, largest frames this moment N at interval so _ThBe 1.5*N _MeanAnd N _SThe smaller value of the two,

Be N _Th=min (1.5*N _Mean, N _S) (8)

Correction model decides the strategy of choosing of candidate frame next time according to the check situation of this candidate frame.If this candidate frame satisfies key frame constraint, as new key frame, and utilize formula (7) to calculate next sampling interval this frame.Otherwise, abandon this frame, extract candidate frame again:, extract new candidate frame according to formula (7) the new sampling interval of prediction if Duplication surpasses the upper limit; If Duplication is low excessively, then rollback upgrades candidate frame with littler interval.

Algorithm begin to need two initial key frame, first frame of video is as first initial key frame, choosing of another initial key frame will be to the key frame prediction generating influence of back.Motion instability when camera begins to take most is if adopt the frame of certain fixed intervals bigger as the methodical error of second key frame.We detect frame by frame to the frame of the first frame back, and first frame of video that meets the key frame constraint as second initial key frame, has been avoided the irregular influence of camera initial motion, obtain well initial Duplication.

Self adaptation key frame sampling algorithm concrete steps based on camera motion are as follows:

1) first frame of selecting video is as key frame.

2) find second key frame by the method that detects frame by frame, write down its corresponding frame period N ₂, Duplication R ₂

3) establishing current up-to-date key frame is F _k, corresponding Duplication and frame period are respectively R _k, N _kAccording to the next candidate frame frame C of formula (7) prediction _K+1Corresponding frame period N _K+1

4) upgrade sampling interval upper bound N according to formula (8) _Th, if N _K+1＞N _Th, get N _K+1=N _Th

5) calculate C _K+1With F _kBetween Duplication R _K+1Number of features M with coupling _K+1

6) if Duplication R _Th＞R _K+1＞R _TlAnd M _K+1＞M _Tl, with candidate frame C _K+1As new key frame F _K+1

Otherwise, abandon candidate frame C _K+1, choose candidate frame again.If R _K+1＞R _Th, illustrate that the too small overlapping region that causes of sampling interval is too big, need the increase sampling interval further to go redundancy, choose and F _kInterframe is divided into N _h=N _K+1* (1-R _s)/(1-R _K+1) frame as new candidate frame C _K+1, if R _K+1＜R _TlPerhaps M _K+1＜M _Tl, illustrate that the sampling interval excessively causes overlapping region or characteristic point very little, need reduce the sampling interval, this registration results is unreliable so can not be used for next time and estimate, directly selects and F _kBe spaced apart N _l=max ([N _K+1/ 2] frame, 1) is as new candidate frame C _K+1

7) repeating step 4-6 is up to finding the new key frame F that satisfies condition _K+1

8) repeating step 3-7 finishes until video.

When the movement velocity of camera was undergone mutation, the sampling of jump might the useful frame of lost part.For example scan when an end then flyback takes place at camera, then can take place at this moment to change some frames constantly in the camera motion direction can be missed along with frame period increases and situation that Duplication also increases, corresponding scene information is lost.In order to guarantee to be drawn into all main information frames, we adopt the hierarchical key frame sampling, in the ground floor sampling, bigger Duplication (such as 80%) are set, and the limited samples interval upper limit is (as N _Th=0.25*FPS, FPS are frame per second).Carry out once down-sampled again to these accurate key frames then.This moment, number of frames was less, can adopt the method that compares Duplication frame by frame to sample.Adopt the notion of information dropout rate in [9], for one group of successive frame F (m), F (m+1) ... F (m+L) extracts F (m), and F (m+L) two frames as the information dropout rate Lost_ratio of key frame correspondence are:

$\mathrm{Lost}\_\mathrm{ratio}=\frac{\mathrm{Area}(F\left(m\right)\∪F(m+1)\∪...\∪F(m+L))-\mathrm{Area}(F\left(m\right)\∪F(m+L))}{\mathrm{Area}\left(F\left(m\right)\right)}$

The information dropout rate is the parameter that the expression local message is lost, and too much for fear of the information dropout of last spliced panoramic figure, the upper limit of Lost_ratio is generally got P _Lost=10%.

Then frame F (m) is if key frame must satisfy:

Lost_ratio＜P _lost (9)

With first frame in the frame sequence that for the first time sampling is obtained as initial key frame, subsequent frame is done detection frame by frame, when certain frame F (m+1) does not satisfy inequality (9), just get F (m+1) front one frame F (m) as up-to-date key frame, restart to detect frame by frame for up-to-date key frame with F (m) then.

Description of drawings

Two interframe overlapping region schematic diagrames when Fig. 1 is the camera translational motion

Overlapping region schematic diagram when Fig. 2 is the motion of camera yawing

Fig. 3 is a hierarchical self-adaptive frame of video frame sampling flow chart of the present invention

Embodiment

Be that the specific embodiment of the present invention is described in further detail below.Following examples are used to illustrate the present invention, but are not used for limiting the scope of the invention.

Hierarchical self-adaptive extracts key frame and mainly comprises following step (as shown in Figure 3):

(1) characteristic point of up-to-date key frame of extraction and candidate frame.

(2) registration candidate frame and up-to-date key frame calculate two frame Duplication.

(3) whether the check candidate frame satisfies the key frame requirement, if candidate frame satisfies standard, then with this frame as up-to-date key frame, otherwise lose this candidate frame

(4) revise forecast model according to the difference of predicted value and actual value, choose candidate frame again.

(5) finish up to video multiple step (1)-(4).

(6) if desired, key frame is carried out double sampling, further go redundancy.

(7) the final sampling results of output

The above only is a preferred implementation of the present invention; should be pointed out that for those skilled in the art, under the prerequisite that does not break away from the technology of the present invention principle; can also make some improvements and modifications, these improvements and modifications also should be considered as protection scope of the present invention.

Claims (4)

1. based on the frame of video methods of sampling of image registration, it is characterized in that, may further comprise the steps:

A, utilize the method for image registration to calculate Duplication between two width of cloth frame of video

B, utilize the Mathematical Modeling of interframe Duplication and frame period to predict the frame period of satisfied certain Duplication

C, the parameter that obtains according to this sampling are upgraded Mathematical Modeling

D, according to the sampling interval next time of the calculated with mathematical model after upgrading.

2. the video methods of sampling described in claim 1 is characterized in that, the Mathematical Modeling of interframe Duplication and frame period is as follows:

Suppose to determine that the frame of video that is extracted is called key frame, the frame of video that waits to detect is called candidate frame.

Camera is in translation (translation) respectively, and during certain single forms of motion in the yawing (pan) and (tilt) the three kinds of motions of diving, in the very short time period, Duplication R is the linear function of frame period n.In the camera motion based on the linear superposition of these three kinds of forms of motion, Duplication R still can be approximated to be the linear function (in the very short time period) of frame period n so.

We can infer the frame period n of the frame correspondence that satisfies certain Duplication R according to the linear relationship of R and n.If known up-to-date key frame F _k, itself and last key frame F _K-1Duplication and frame period be respectively R _kAnd N _k, then with F _kDuplication be expectation Duplication R _sFrame F _K+1With F _kFrame period N _K+1Can estimate with following formula:

Frame period 0 N _kN _K+1

Duplication 1 R _kR _K+1

$\left.\begin{array}{c}\frac{N_k-0}{R_k-1}=\frac{N_{k+1}-0}{R_{k+1}-1}\\ R_{k+1}=R_s\end{array}\right\}$

That is: N _K+1=N _k* (1-R _s)/(1-R _k).

3. the video methods of sampling described in claim 1 is characterized in that, it is as follows that the parameter that obtains according to this sampling is upgraded mathematical model method:

Each candidate frame F _nHave two parameters, with the Duplication R of last key frame _nWith frame period N _nKey frame constraints has: the upper and lower bound of Duplication is respectively R _ThAnd R _Tl, the upper bound of frame period is N _Th=scale*FPS (scale＜1, FPS is a video frame rate).Have only two parameters of candidate frame all to satisfy under the situation of its constraints, this frame is just thought effective key frame, otherwise abandons this frame, chooses candidate frame again according to correction model.

If Duplication R _Th＞R _K+1＞R _TlAnd M _K+1＞M _Tl, with candidate frame C _K+1As new key frame F _K+1, and calculate prediction correction factor r _K+1=(1-R _s)/(1-R _K+1).Otherwise, abandon candidate frame C _K+1, choose candidate frame again.If R _K+1＞R _Th, illustrate that the too small overlapping region that causes of sampling interval is too big, need the increase sampling interval further to go redundancy, choose and F _kInterframe is divided into N _h=N _K+1* (1-R _s)/(1-R _K+1) frame as new candidate frame C _K+1, if R _K+1＜R _TlIllustrate that the sampling interval excessively causes overlapping region or characteristic point very little, need reduce the sampling interval, this registration results is unreliable so can not be used for estimation next time, illustrate that the sampling interval excessively causes overlapping region or characteristic point very little, need reduce the sampling interval, this registration results is unreliable so can not be used for estimation next time, directly selects and F _kBe spaced apart N _l=max ([N _K+1/ 2] frame, 1) is as new candidate frame C _K+1

4. based on the frame of video methods of sampling of image registration, it is characterized in that: the piecewise linear model of interframe Duplication and frame period is only more accurate when Duplication is less than certain limit, the Duplication that requires when sampling is less, can adopt the stratified sampling method progressively to reduce Duplication.

Images