A computing device comprising: a hardware pipelined video encoder for encoding image frames, each comprising a set of macro-blocks, and configured to: select a plurality of candidate predicted motion vectors associated with a macro-block of an image frame of video data to be encoded, wherein the plurality of candidate predicted motion vectors are selected from different, previously-encoded macro-blocks; perform a plurality of motion searches in an image region surrounding each candidate predicted motion vector to produce a plurality of resulting motion vectors, each resulting motion vector having an initial cost score determined using a corresponding candidate predicted motion vector in a cost score calculation wherein the cost score is calculated from the or each candidate predicted motion vector and a rate-distortion function, after an actual predicted motion vector, which was previously unavailable when the plurality of candidate predicted motion vectors were selected for the plurality of motion searches, becomes available due to completion of encoding of a macro-block that includes the actual predicted motion vector, re-scoring the cost score of each resulting motion vector of the plurality of resulting motion vectors, to determine an updated cost score for each resulting motion vector by using the actual predicted motion vector in place of the corresponding predicted motion vector in the cost score calculation, wherein in the updated cost calculation just the rate is recomputed, and encode the video data using a motion vector selected from the plurality of resulting motion vectors based on the motion vector having a lowest updated cost score of the plurality of resulting motion vectors. select a plurality of candidate predicted motion vectors associated with a macro-block of an image frame of video data to be encoded, wherein the plurality of candidate predicted motion vectors are selected from different, previously-encoded macro-blocks; perform a plurality of motion searches in an image region surrounding each candidate predicted motion vector to produce a plurality of resulting motion vectors, each resulting motion vector having an initial cost score determined using a corresponding candidate predicted motion vector in a cost score calculation wherein the cost score is calculated from the or each candidate predicted motion vector and a rate-distortion function, after an actual predicted motion vector, which was previously unavailable when the plurality of candidate predicted motion vectors were selected for the plurality of motion searches, becomes available due to completion of encoding of a macro-block that includes the actual predicted motion vector, re-scoring the cost score of each resulting motion vector of the plurality of resulting motion vectors, to determine an updated cost score for each resulting motion vector by using the actual predicted motion vector in place of the corresponding predicted motion vector in the cost score calculation, wherein in the updated cost calculation just the rate is recomputed, and encode the video data using a motion vector selected from the plurality of resulting motion vectors based on the motion vector having a lowest updated cost score of the plurality of resulting motion vectors.