Parallel three-dimensional recursive search (3DRS) meandering algorithm

A motion estimation unit for performing motion estimation on video data comprising a plurality of frames, the motion estimation unit comprising:

• a memory that stores a plurality of frames of the video data;
• and
• a plurality of processors, wherein, in processing a current row in a current frame of the plurality of frames, a first processor of the plurality of processors:
• reads the current frame from the memory, the current frame comprising a plurality of rows;
• and
• selects a motion vector for each respective block of pixels in the current row of the current frame, wherein the first processor, for each respective block:
• selects a candidate vector for at least one block directly surrounding the respective block based on a determination of whether the directly surrounding block has been processed for the current frame,
• calculates, for each candidate vector, a difference value indicating an accuracy of motion estimation when the candidate vector is used to represent motion of the respective block, and
• selects, as the motion vector, the candidate vector with a lowest difference value, wherein a second processor of the plurality of processors simultaneously processes a subsequent row in a direction opposite to processing by the first processor.

A machine-readable medium encoded with processor-executable instructions for performing motion estimation on video data comprising a plurality of frames, the machine-readable medium comprising:

• instructions for reading, by a motion estimation unit, a current frame of the plurality of frames from a memory, the current frame comprising a plurality of rows;
• instructions for selecting a motion vector, with a first processor, for each respective block of pixels in a current row of the current frame, wherein the instructions for selecting the motion vector comprise, for each respective block:
• instructions for selecting a candidate vector for at least one block directly surrounding the respective block based on a determination of whether the directly surrounding block has been processed for the current frame,
• instructions for calculating, for each candidate vector, a difference value indicating an accuracy of motion estimation when the candidate vector is used to represent motion of the respective block, and
• instructions for selecting, as the motion vector, the candidate vector with a lowest difference value;
• and
• instructions for simultaneously processing, with a second processor, at least one subsequent row by repeating the step of selecting a motion vector for each block of pixels in the at least one subsequent row, wherein processing of the at least one subsequent row with the second processor occurs in an opposite direction to processing of at least one block of the current row with the first processor.