Method and apparatus for coordination of motion determination over multiple frames

• US 6,157,677 A
• Filed: 11/21/1997
• Issued: 12/05/2000
• Est. Priority Date: 03/22/1995
• Status: Expired due to Fees

• Current Assignee: IDT Intenational Digital Technologies Deutschland GmbH
• Original Assignee: IDT Intenational Digital Technologies Deutschland GmbH
• Inventors: Reberg, Jan Otto, Martens, Harald Aagaard
• Primary Examiner(s): Le, Vu
• Application Number:
  US08/930,340
• Time in Patent Office: 1,110 Days
• Field of Search: 375/240.16, 348/407.1, 348/413.1, 348/416.1, 348/699, 348/700, 382/236, 382/238, 382/239, 381/111, 358/261.2
• US Class Current: 375/240.16
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06T 7/262 using transform domain methods, e.g. Fourier domain methods
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based

Abstract

The present invention concerns improved motion estimation in signal records. A method for estimating motion between one reference image and each frame in a sequence of frames, each frame consisting of a plurality of samples of an input signal comprises the steps of: transforming the estimated motion fields into a motion matrix, wherein each row corresponds to one frame, and each row contains each component of motion vector for each element of the reference image; performing a Principal Component Analysis of the motion matrix, thereby obtaining a motion score matrix consisting of a plurality of column vectors called motion score vectors and a motion loading matrix consisting of a plurality of row vectors called motion loading vectors, such that each motion score vector corresponds to one element for each frame, such that each element of each motion loading vector corresponds to one element of the reference image, such that one column of said motion score matrix and one motion loading vector together constitute a factor, and such that the number of factors is lower than or equal to the number of said frames; wherein the results from the Principal Component Analysis on the motion matrix are used to influence further estimation of motion from the reference image to one or more of the frames.

Claims

1. A method for estimating motion between one reference image and one or more frames in a sequence of two or more frames, each frame consisting of a plurality of pixels of an input image, comprising the steps of:

estimating motion from the reference image to two or more of the frames to produce motion fields;

transforming the motion fields into a motion matrix, where each row of the motion matrix corresponds to one motion field and each row of the motion matrix contains a vertical and a horizontal component of a motion vector pertaining to each pixel of the reference image; and

performing Principal Component Analysis on the motion matrix to produce a factorization of the motion matrix into the product of a motion score matrix and a motion loading matrix, the motion score matrix comprising a plurality of motion score vectors arranged as column vectors, the motion loading matrix comprising a plurality of motion loading vectors arranged as row vectors, the factorization forming a bilinear model in which one column of said motion score matrix and one corresponding row of said motion loading matrix together comprise a factor of the bilinear model, the number of factors being lower than or equal to the number of said frames;

wherein results from the Principal Component Analysis on the motion matrix are used to influence further estimation of motion from the reference image to one or more of the frames.

2. The method according to claim 1, comprising the steps of:

(1) estimating a particular motion field for each frame from the reference image to the respective frame

(2) transforming the estimated motion field for each frame into a motion matrix;

(3) performing Principle Component Analysis on the motion matrix associated with each frame;

(4) for each frame, multiplying the entries of the motion score matrix corresponding to the frame by the corresponding motion loading vectors to produce a motion hypothesis for each frame;

(5) for each frame, estimating a motion field from the reference image to said frame, using the motion hypothesis as side information; and

(6) outputting the motion fields estimated in step (5), the output motion fields representing the motion between said reference image and each respective frame in the sequence of frames.

3. The method according to claim 2, wherein steps (2) to (5) are repeated for a plurality of passes through said sequence of frames.

4. The method according to claim 3, wherein said motion estimation is performed with reference to a smoothness parameter which is a decreasing function of pass number, a smoother motion field being produced for a higher value of said smoothness parameter.

5. The method according to claim 3, wherein said motion hypothesis is formed with reference to a hypothesis impact parameter which is an increasing function of pass number, a larger hypothesis impact parameter producing a motion hypothesis which has a greater impact on said motion estimation.

6. The method according to claim 2, further comprising the steps of:

(5b) re-estimating the bilinear model based on the motion field found in step (5);

(5c) multiplying the motion score matrix for the given frame by the motion loading vectors from the re-estimated bilinear model to produce a second motion hypothesis; and

(5d) estimating a particular motion field from the reference image to the frame, using said second motion hypothesis as side information,

wherein the motion field estimated in step (5d) represents the motion between the reference image and the frames.

7. The method according to claim 2, wherein during the Principal Component Analysis of step (3) and the formation of the motion hypotheses in step (4) uncertainity estimates for the motion hypothesis are generated and subsequently used to control the degree of impact of the motion hypothesis as side information in the motion estimation in step (5).

8. The method of claim 2, wherein the collection of motion score vectors and motion loading vectors estimated in step (3) represents the motion fields.

9. The method according to claim 1, the method comprising the steps of:

(1) estimating motion from the reference image to the first of said frames;

(2) forming the motion matrix from the estimated motion between the reference image and the first of said frames;

(3) performing Principal Component Analysis of the formed motion matrix;

(4) for a next one of said frames, predicting a value for the motion score vectors using extrapolation from previous entries of the motion score matrix and multiplying the predicted entries of motion score vectors with the motion loading vectors to produce a motion hypothesis for each frame;

(5) for said next frame, estimating a particular motion field from the reference image to the frame, using the motion hypothesis as side information; and

(6) repeating steps (2) to (5) for respective subsequent next frames until no more frames remain in the sequence,

wherein the motion fields estimated in step (5) represent the motion between the reference image and the frames.

10. The method according to claim 1, comprising the steps of:

(1) estimating motion from the reference image to the first frame in said sequence;

(2) forming a motion row vector containing each component of the motion vector for each element of the reference image and with one row for each frame;

(3) updating the bilinear model based on the appended new motion row vector;

(4) for a next of said frames, predicting a value for the motion score matrix using extrapolation from previous entries of the motion score matrix and multiplying the predicted entries of the motion score matrix by the motion loading vectors to produce a motion hypothesis for each frame;

(5) for the next frame, estimating a motion field from the reference image to the frame, using the motion hypothesis as side information; and

(6) repeating steps (2) to (5) for respective subsequent next frames until the last frame in said sequence has been processed;

wherein the motion field estimated in step (5) represents the motion between the reference image and the frames.

11. The method of claim 10, wherein steps (2) to (6) are repeated for a plurality of passes through said sequence.

12. The method of claim 11, wherein steps (2) to (5d) are repeated for a plurality of passes through said sequence.

13. The method of claim 1, further comprising the step of using an intermediate bilinear model of the motion matrix as side information for motion analysis in higher spatial resolution, the intermediate bilinear model having motion loading vectors of reduced spatial resolution relative to the motion loading vectors of the bilinear model.

14. The method according to claim 13, wherein a degree of use of said bilinear model is indicated by a pyramid impact parameter that is a decreasing function of pass number, a large value for said pyramid impact parameter resulting in a strong influence of said side information.

15. The method according to claim 1, wherein a segment field is used to select a part of said reference image and motion estimation is performed only for the selected part of said reference image.

16. The method of estimating motion according to claim 1, wherein the reference image is part of the sequence of frames, and further comprising the step of:

segmenting said reference image based on the estimated motion to produce a plurality of segment fields.

17. The method of claim 16, further comprising the steps of:

estimating motion for each segment field; and

repeating the segmenting and estimating motion for the segment field steps for a plurality of passes, the collection of estimated motion fields in the last of said passes representing segmentwise motion.

18. The method according to claim 17, wherein segmenting of said reference image is performed according to a segment detail parameter which is an increasing function of pass number, a higher value of said segment detail parameter producing a more detailed segmenting.

19. The method of claim 1, further comprising the step of performing an Optimal Scaling on the bilinear model.

20. The method of claim 1, wherein the step of performing Principal Component Analysis includes reweighting.

21. The method of claim 1, wherein the step of performing Principal Component Analysis includes the step of handling missing values in the input data which correspond to areas in said reference frame where said motion estimation was not successful for the corresponding given frame.

22. The method of claim 1, further comprising the step of preprocessing the frames to normalize intensity and position of the frames.

23. The method of claim 1, wherein said motion matrix is augmented with score matrices taken from bilinear models of supplementary data matrices for the same frames used to generate the motion matrix, said supplementary data matrices containing data from one of (a) motions for other holons, (b) intensity changes, (c) motions estimated in an earlier stage, and (d) motions estimated at another spatial resolution.

24. The method of claim 1, wherein the step of performing Principal Component Analysis comprises smoothing said motion loading vectors.

25. The method of claim 1, wherein the step of performing Principal Component Analysis comprises smoothing said motion score vectors.

26. The method of claim 1, wherein there is one motion matrix for each spatial dimension in said reference image, and each said component of each said motion vector is placed in the motion matrix that corresponds to said spatial dimension.

27. The method of claim 1, further comprising the step of approximating a specific frame from the reference image by moving the reference image according to estimated motion.

28. The method of claim 1, comprising the steps of:

selecting a specific frame;

estimating motion from the reference frame to the specific frame; and

regressing the motion found in the estimating step on the motion loading vectors to produce entries for the motion score matrix corresponding to the selected specific frame.

29. The method according to claim 1, further comprising the steps of:

(1) selecting a specific frame;

(2) initializing a set of motion score vectors to start values, the number of said motion score vectors being equal to the number of said motion loading vectors;

(3) for each of a plurality of trial score combinations, computing a motion field by multiplying said trial combination of motion score vectors by said motion loading vector, moving a second image according to said motion field to produce a reconstruction, computing a fidelity measurement according to the difference between said reconstruction and a first image, each trial score combination being computed as a perturbation of said motion scores;

(4) computing new motion scores dependent on said trial combination of motion score vectors and said fidelity measurement; and

(5) repeating steps (3) and (4);

wherein said motion load vectors and said motion score vectors computed by the last repetition of step (4) represent motion to be approximated for the selected specific frame.

30. The method according to claim 1, wherein an intensity score matrix comprises a plurality of intensity score vectors arranged in columns and an intensity loading matrix comprises intensity loading vectors arranged in rows, each intensity score vector element corresponding to one frame, each element of each intensity loading vector corresponding to one element of the reference image, one column of said intensity score matrix and one intensity loading vector together constitute a factor, the number of factors being less than or equal to the number of said frames, the sum of factors describing intensity changes in said reference image,

the step of estimating motion comprising the substep of adjusting at least one of the reference image and a specific frame according to the intensity loading vectors.

31. The method according to claim 30, further comprising the steps of:

(1) predicting intensity score entries of the intensity score vectors for said specific frame by one of interpolating and extrapolating from entries of the intensity score vectors from related frames;

(2) computing an intensity-corrected reference image from the product of intensity scores predicted in step (1) and the intensity loading vectors, plus said reference image; and

(3) estimating motion from said intensity-corrected reference image to said specific frame, the estimated motion representing motion relative to said reference image for said specific frame.

32. The method of claim 1, further comprising the steps of:

(1) computing an intensity-corrected reference image as the product of the intensity change score vector entries for a specific frame and the intensity change loading vectors, plus said reference image;

(2) estimating motion from said intensity-corrected reference image to said specific frame;

(3) projecting the motion estimated in step (2) on said motion loading vectors to produce motion scores for said specific frame;

(4) computing a motion field by multiplying the motion score vector entries produced in step (3) by the motion loading vectors;

(5) moving said specific frame backwards according to the motion field computed in step (4) to produce a motion compensated image;

(6) calculating an intensity difference between the motion compensated image produced in step (5) and said reference image;

(7) projecting the difference calculated in step (6) on the intensity change loading vectors to produce intensity change score vector entries for said specific frame; and

(8) repeating steps (1)-(7) one or more times;

wherein the specific frame is described relative to the reference image according to intensity change loading vectors, motion loading vectors, and initial intensity change score vector entries for the specific frame.

33. The method of claim 1, further comprising the steps of:

(1) initializing an intensity change model comprising intensity change score vectors and intensity change loading vectors to empty;

(2) initializing a motion model comprising motion score vectors and motion loading vectors to empty;

(3) choosing an unprocessed frame;

(4) if a non-empty intensity change model is available, predicting intensity change score vector entries for the unprocessed frame by one of interpolating and extrapolating to related frames, computing an intensity correction by multiplying the predicted intensity change score vector entries for said unprocessed frame by the intensity change loading vectors, computing an intensity-corrected reference image by adding said intensity correction to said reference image,

otherwise setting the intensity-corrected reference image to be equal to said reference image;

(5) estimating motion from said intensity-corrected reference image to said unprocessed frame;

(6) updating said motion model according to the motion estimated in step (5);

(7) computing a motion compensation field by multiplying motion score vector entries for said unprocessed frame by said motion loading vectors;

(8) moving said unprocessed frame backwards according to the motion compensation field, thereby producing a motion-compensated image;

(9) calculating the difference between said motion-compensated image and said reference image;

(10) updating said intensity model according to the difference calculated in step (9);

(11) repeating steps (3)-(10) for each frame in said sequence;

wherein the motion score vectors and motion loading vectors resulting from the last repetition of step (6) and the intensity change score vectors and intensity change loading vectors resulting from the last repetition of step (10) together represent the motion and intensity changes for the reference image relative to each frame in the sequence.

34. The method of claim 33, wherein the step of intensity modeling includes calculating uncertainties, adjusting said intensity corrections according to said uncertainties by at least one of smoothing, multiplying by, or subtracting from said intensity correction in accordance with said uncertainties.

35. The method of claim 33, wherein said intensity corrections are adjusted according to an intensity relaxation parameter which is a decreasing function of repetitions, a small intensity relaxation parameter resulting in a small intensity correction.

36. The method of claim 33, wherein the motion modeling includes the steps of calculating uncertainties and smoothing said motion compensation field according to said uncertainties.

37. The method of claim 33, wherein the motion is smoothed according to a motion relaxation parameter which is a decreasing function of repetitions, a small motion relaxation parameter resulting in little smoothing.

38. The method of claim 37, wherein steps (3)-(11) are repeated for several passes.

39. The method to claim 38, wherein after the step of moving backwards, a Multiplicative Signal Correction is performed.

40. The method according to claim 1, further comprising the steps of:

(1) initializing an intensity change model consisting of intensity change score vectors and intensity change loading vectors to empty;

(2) initializing a motion model consisting of motion score vectors and motion loading vectors to empty;

(3) choosing an unprocessed frame;

(4) if a non-empty motion model is available, predicting motion score vector entries by one of interpolating and extrapolating to related frames, computing a motion compensation field by multiplying the predicted motion score vector entries by the motion loading vectors, moving said unprocessed frame backwards using the motion compensation field thus producing a motion-compensated image,

otherwise setting the motion-compensated image to be equal to said unprocessed frame;

(5) calculating a difference between said motion-compensated image and said reference image;

(6) updating said intensity model according to the difference calculated in step (5);

(7) computing an intensity correction by multiplying the intensity change score vector entries updated in step (6) corresponding to said frame by the intensity change loading vectors updated in step (6);

(8) adding said intensity correction to said reference image to produce an intensity-corrected image;

(9) estimating motion from said intensity-corrected image to said unprocessed frame;

(10) updating the motion model with the motion estimated in step (9);

(11) repeating steps (3)-(10);

wherein the motion score vectors and motion loading vectors resulting from the last repetition of step (10) and the intensity score vectors and intensity loading vectors resulting from the last repetition of step (6) together represent the motion and intensity changes for the reference image relative to each frame in the sequence.

41. The method according to claim 1, wherein said intensity model is initialized according to a set of chosen intensity patterns.

42. An apparatus for estimating motion between one reference image and one or more frames in a sequence of two or more frames, each frame consisting of a plurality of pixels of an input image, said apparatus comprising:

means for estimating motion from the reference image to two or more of the frames to produce motion fields;

means for transforming the motion fields into a motion matrix, where each row of the motion matrix corresponds to one motion field and each row of the motion matrix contains a vertical and a horizontal component of a motion vector pertaining to each pixel of the reference image; and

means for performing Principal Component Analysis on the motion matrix to produce a factorization of the motion matrix into the product of a motion score matrix and a motion loading matrix, the motion score matrix comprising a plurality of motion score vectors arranged as column vectors, the motion loading matrix comprising a plurality of motion loading vectors arranged as row vectors, the factorization forming a bilinear model in which one column of said motion score matrix and one corresponding row of said motion loading matrix together comprise a factor of the bilinear model, the number of factors being lower than or equal to the number of said frames;

wherein results from the Principal Component Analysis on the motion matrix are used to influence further estimation of motion from the reference image to one or more of the frames.

43. A data structure stored in a computer readable medium and suitable for representing motion between one reference image and each frame in a sequence of frames, said frames consisting of a plurality of data samples arranged in a spatial pattern, said data structure comprising:

(1) a plurality of motion patterns represented as loading vectors, each element of each loading vector corresponding to one element of said reference image; and

(2) a plurality of motion score vectors, each motion score vector corresponding to one of said frames, each motion score vector consisting of the same number of elements as the number of loading vectors, each motion score element of each motion score vector representing how much the corresponding loading vector should contribute to the total motion for said one frame.