Patent EP0535746A2 successfully refreshed from Google Patents.
EP0535746A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Motion vector estimation, motion picture encoding and storage
Assignee: Philips Electronics UK Ltd
•
Filing: 1992-09-29
•
Granted: —
•
Expires: 2012-09-29
Abstract
Abstract In the encoding of a frame (P3) in a digitised motion picture sequence, the frame is divided into blocks (A) of pixels and a motion vector (VA) found to predicts the contents of each block A from a block (A') in a previous frame (IO). Rather than evaluate many thousands of candidate vectors to find the best motion vector (VA), relatively few candidate vectors are evaluated, based on starting vector which is the estimated motion vector for a neighbouring block (LB(A)) in the same frame. To allow parallel processing of several pixel blocks, all the blocks of one row in the current frame are assigned to one processor (DSP), and a starting vector is obtained from a block (LB(A)) previously processed by the same processor. Further starting vectors are obtained if desired from neighbouring blocks (UR(B),DR(B)) in neighbouring frames of the sequence. The candidate vectors based on a starting vector may be very few in number, or may fill an area a few percent of the full search area. The method may favour candidate vectors which are more economical to encode.
Inventors
- 👤 Derek Andrew
- 👤 Octavius John Morris
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-09 14:13
CPC Classifications
H; H04; H04N; H04N5/00; H04N5/14; H04N5/144; H04N5/145; G; G06; G06T; G06T7/00; G06T7/20; G06T7/223; G06T7/238; H04N19/00; H04N19/42; H04N19/43; H04N19/436; H04N19/50; H04N19/503; H04N19/51; H04N19/56; H04N19/567
Claims Analysis
Total Claims: 17
Claim 1
Independent Claim
167 words
A method of estimating motion vectors for blocks of pixels in a frame of a digitised motion picture sequence, the method comprising, for each given block of pixels performing a vector search based around at least one starting vector derived from a previously estimated vector for a pixel block which is a neighbour in space and/or time of the given pixel block, characterised in that the estimation of motion vectors for each frame is performed in parallel for at least two ordered subsets of the pixel blocks of the frame, the division and ordering of pixel blocks into the subsets and the selection of the neighbouring pixel block(s) being performed such that, where a neighbouring block whose estimated vector is to be used to predict that of the given block is selected from the same frame as the given block, the said neighbouring block is one of the same subset as the given block and is ordered in the subset so as to precede the given block.
Claim 2
Dependent Claim
68 words
A method as claimed in Claim 1 wherein each subset comprises a row of pixel blocks, the processor estimating motion vectors for the pixel blocks of the row in a predetermined sequence, the motion vector for each given block (disregarding the first block in each row) being predicted by the processor from the motion vector estimated for a block which precedes the given block in the said sequence.
Claim 3
Dependent Claim
44 words
A method as claimed in Claim 1 or 2 wherein for each given pixel block at least one further prediction of the motion vector is based on a motion vector estimated for a pixel block in a neighbouring frame in the motion picture sequence.
Claim 4
Dependent Claim
51 words
A method as claimed in Claim 3 wherein for each given pixel block in a row (disregarding the first block in each row) predictions are based upon the previously estimated motion vectors of the said preceding block in the same row and a plurality of blocks in the said neighbouring frame.
Claim 5
Independent Claim
88 words
A method as claimed in any of Claims 1 to 4 wherein the predictions for each given pixel block (disregarding the first block in each subset) are based on motion vectors estimated previously for: - the said preceding block in the same subset as the given block; and - two blocks in a neighbouring frame occupying spatial positions relative to the given block so as to define with the said preceding block in the same subset as the given block a triangular distribution generally surrounding the given block.
Claim 6
Independent Claim
48 words
A method as claimed in any preceding claim wherein on the basis of the at least one starting vector, matching between the given block and a block in a previous frame is measured for an array of from 5 to 10 candidate vectors distributed around the starting vector.
Claim 7
Independent Claim
57 words
A method as claimed in any of Claims 1 to 5 wherein on the basis of the at least one starting vector matching between the given block and a block in a previous frame is measured sequentially for an ordered series of candidate vectors surrounding the starting vector and with generally increasing distance from the starting vector.
Claim 8
Dependent Claim
28 words
A method as claimed in Claim 7 wherein the evaluation of candidate vectors is terminated if a vector is found giving a matching better than a predetermined threshold.
Claim 9
Independent Claim
62 words
A method of estimating a motion vector for a given block of pixels in a frame of a digitised motion picture sequence by performing an evaluation of a plurality of candidate vectors based around a starting vector, characterised in that the candidate vectors surround the starting vector and are evaluated in an ordered series of generally increasing distance from the starting vector.
Claim 10
Dependent Claim
28 words
A method as claimed in Claim 9 wherein the evaluation of candidate vectors is terminated if a vector is found giving a matching better than a predetermined threshold.
Claim 11
Independent Claim
55 words
A method as claimed in any of Claims 1 to 10 wherein the selection of each estimated vector depends not only on the measured prediction quality (matching) of each candidate vector, but also on the relative economy with which the candidate vector can be encoded in a resultant data stream encoding the motion picture sequence.
Claim 12
Dependent Claim
34 words
A method as claimed in Claim 10 wherein the zero vector is most economically encoded and wherein a candidate vector which is zero will be favoured in the selection of each estimated motion vectors.
Claim 13
Independent Claim
206 words
A method of estimating a motion vector for a given block of pixels in a frame of a digitised motion picture sequence, which estimated vector is to be encoded in a data stream encoding the motion picture sequence, the method comprising: - generating a set of candidate vectors for evaluation; - evaluating the quality of prediction provided by each of the candidate vectors; and - comparing the results of said evaluations to select one of the candidate vectors as the estimated vector for encoding in a stream of data encoding the motion picture sequence, wherein the amount of data required to encode the estimated motion vector is dependent on the value of the estimated motion vector and wherein the selection of the estimated vector from among the candidate vectors depends not only on the quality of prediction provided by each candidate, but also on the amount of data required to encode each candidate in the data stream, such that the candidate vector selected is not the one providing the highest quality of prediction, if it is determined that another one of the candidate vectors can been coded in less data while providing a prediction quality which is within a pre-determined threshold of the highest prediction quality.
Claim 14
Independent Claim
31 words
A method as claimed in any preceding claim wherein the motion vectors and prediction error information are encoded in accordance with the MPEG standard as defined by the International Standards Organisation.
Claim 15
Independent Claim
86 words
An apparatus for encoding a digitised motion picture sequence comprising: - means for dividing at least one given frame of the sequence into a plurality of blocks of pixels; - means for estimating by the method of any preceding claim a motion vector predicting each block of pixels in the given frame from a block in a neighbouring frame and encoding said motion vector; and - means for generating and encoding prediction error information to for use with the motion vectors in reconstructing the encoded image.
Claim 16
Dependent Claim
46 words
A method of storing a digitised motion picture sequence on a record carrier, comprising: - using an apparatus as claimed in Claim 15 to encode the motion picture sequence; and - storing the resultant encoded motion vector information and prediction error information on the record carrier.
Claim 17
Dependent Claim
21 words
A record carrier wherein a motion picture sequence has been stored in accordance with a method as claimed in Claim 16.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.