We present and compare methods for choosing motion vectors for
motion-compensated video coding. Our primary focus is on videophone and
videoconferencing applications, where very low bit rates are necessary,
where motion is usually limited, and where frames must be coded in the
order they are generated. We provide evidence, using established
benchmark videos typical of these applications, that choosing motion
vectors explicitly to minimize rate, subject to implicit constraints on
distortion, yields better rate-distortion tradeoffs than minimizing
notions of prediction error. Minimizing a linear combination of rate
and distortion results in further rate-distortion improvements. Using a
heuristic function of the prediction error and the motion vector
codelength results in compression performance comparable to the more
computationally intensive coders while running much faster. We
incorporate these ideas into coders that operate within the
standard.