A method of selecting motion vectors in a video compression encoder, comprising: receiving a target image, a reference image, a target bit rate and a bit rate variance (610; 115, 125, 130); determining a collection of candidate motion vectors by dividing the target image into blocks by using a library of shape definitions, each shape definition defining tiling of a target image into a collection of blocks of pixels with each block being represented by a motion vector for compensating its pixels; selecting an output collection of motion vectors based on the collection of candidate motion vectors; and forming a compensated image using the output collection of motion vectors to generate a compensated target image by mapping target blocks of the target image to reference blocks in the reference image according to each motion vector of the output collection of motion vectors and copying the pixel values of the reference blocks to the target blocks; wherein the selecting the output collection of motion vectors comprises identifying each of the reference blocks in the reference image corresponding to the target blocks in the target image using each of the candidate motion vectors; for each of the candidate motion vectors calculating an amount of image distortion between the target image and the compensated target image generated from the identified reference blocks and target blocks; and adding one or more of the candidate motion vectors to the output collection of motion vectors in accordance with a rate-distortion criterion to cause the largest decrease in image distortion, or removing one or more of the motion vectors from the output collection of motion vectors to cause the smallest increase in image distortion until a stopping criterion is reached, and the adding or removing the one or more candidate motion vectors including if a resulting bit rate of the compensated target image is less than the target bit rate, adding one or more of the candidate motion vectors from the collection of candidate motion vectors to the output collection of motion vectors until the bit rate is greater than or equal to the target bit rate plus the bit rate variance; if the resulting bit rate of the compensated target image is greater than the target bit rate, removing one or more of the motion vectors from the output collection of motion vectors until the resulting bit rate is less than or equal to the target bit rate minus the bit rate variance. receiving a target image, a reference image, a target bit rate and a bit rate variance (610; 115, 125, 130); determining a collection of candidate motion vectors by dividing the target image into blocks by using a library of shape definitions, each shape definition defining tiling of a target image into a collection of blocks of pixels with each block being represented by a motion vector for compensating its pixels; selecting an output collection of motion vectors based on the collection of candidate motion vectors; and forming a compensated image using the output collection of motion vectors to generate a compensated target image by mapping target blocks of the target image to reference blocks in the reference image according to each motion vector of the output collection of motion vectors and copying the pixel values of the reference blocks to the target blocks; wherein the selecting the output collection of motion vectors comprises identifying each of the reference blocks in the reference image corresponding to the target blocks in the target image using each of the candidate motion vectors; for each of the candidate motion vectors calculating an amount of image distortion between the target image and the compensated target image generated from the identified reference blocks and target blocks; and adding one or more of the candidate motion vectors to the output collection of motion vectors in accordance with a rate-distortion criterion to cause the largest decrease in image distortion, or removing one or more of the motion vectors from the output collection of motion vectors to cause the smallest increase in image distortion until a stopping criterion is reached, and the adding or removing the one or more candidate motion vectors including if a resulting bit rate of the compensated target image is less than the target bit rate, adding one or more of the candidate motion vectors from the collection of candidate motion vectors to the output collection of motion vectors until the bit rate is greater than or equal to the target bit rate plus the bit rate variance; if the resulting bit rate of the compensated target image is greater than the target bit rate, removing one or more of the motion vectors from the output collection of motion vectors until the resulting bit rate is less than or equal to the target bit rate minus the bit rate variance.