In video transcoding, the compressed video is often converted to a lower resolution in order to reduce the bit rate. One way to achieve this is to first decompress the compressed video, down-sample each frame, and then re-compress the down-scaled frame sequences. This method can obtain high-quality compressed video bit-streams; however, it involves motion vector estimation that is computationally complex. Recently, some transcoding techniques have been proposed to compute the motion vectors for a compressed video with lower resolution using the motion vectors directly from the original compressed video. These techniques, however, cannot be used in arbitrary-size video down-scaling, e.g for converting CIF (Common Intermediate Format) video to sub-QCIF (Quarter CIF) video or QCIF to sub-QCIF. In this paper, we propose a video transcoding method that can estimate the motion vectors for arbitrary-size down-scaled video. It can provide video quality that is comparable to full-search motion estimation but with very low computational complexity.