Motion vector estimation, motion picture encoding and storage

A method of estimating a motion vector for a given block of pixels in a frame of a digitised motion picture sequence, which estimated motion vector is to be encoded in a data stream encoding the motion picture sequence, the method comprising the steps of:

• generating a set of candidate motion vectors for evaluation;
• determining a quality of prediction value for each of the candidate motion vectors;
• selecting candidate motion vectors having a quality of prediction value within a pre-determined threshold of a highest quality of prediction value for the candidate motion vectors;
• determining an encoding length for each of the selected candidate motion vectors, the encoding length being dependent on the value of the selected candidate motion vector;
• and
• selecting as the estimated motion vector for the given block of pixels the selected candidate motion vector having a shortest encoding length.

An apparatus for estimating motion vectors for pixel blocks in a frame of a digitized motion picture sequence, said apparatus comprising in combination:

• a) means for dividing the pixel blocks into at least two separate ordered subsets of pixel blocks;
• b) means for selecting for each given pixel block in the frame, at least one pixel block which is a neighbor of the given pixel block in space and/or in time, wherein any selected pixel block which is a neighbor of the given pixel block in space is selected only from pixel blocks that precede the given pixel block in the same ordered subset as the given pixel block;
• and
• c) means for performing, for each given pixel block in the frame, a vector search around at least one starting motion vector for the given pixel block to determine an estimated motion vector for the given pixel block, the at least one starting motion vector being derived from at least one previously estimated motion vector of said at least one selected block which is a neighbor of the given pixel block, wherein the vector searches for pixel blocks in each of the subsets is performed in parallel.