Abstract: In video transcoding, the compressed video is often converted to lower resolution in order to reduce 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 downscaling, for example, converting CIF video to sub-QCIF video or QCIF to sub-QCIF. In this paper, we propose a video transcoding method that can estimate the motion vectors for arbitrary size downscaled video. It can provide video quality comparable to full search motion estimation but with very low computational complexity.