A video coding method progressively refines a predicted motion vector to obtain an estimated motion vector. Subsequent steps are omitted if the estimated motion vector matches a current macroblock. Variable matching thresholds can permit dynamic adjustment of image quality and computational cost to optimize encoding performance for available computational resources. The method permits control of desired encoding speed and bit rate by adjusting encoding parameters. Video coders according to the invention may comprise a motion estimator, transform computer and coder each of which operates according to one or more parameters. A speed rate control and/or a bit rate control may adjust the parameters to maintain a desired encoding speed and output bit rate. A coder according to the invention may be implemented in software running on a general purpose computer. The method may be used in block-based video encoders including MPEG-2 and H.263 encoders.