1. Apparatus for fast motion estimation for video pre-processing, comprising: (A) structure for selecting a second-order distortion criterion for identifying a best reference image portion for comparison with a current image portion, said second-order distortion criterion being a Lagrange-optimized combination of a mean squared error criterion with an entropy criterion; and (B) structure for using said second-order distortion criterion to select an initial reference image portion as an initial starting point for a motion estimation search, said initial starting position being chosen based on at least one motion vector from a neighboring image portion.