A video transcoding method is provided for transcoding a first signal stream compressed by a first coding scheme to a second signal stream compressed by a second coding scheme. The method employs an adaptive frame rate and a joint temporal-spatial rate control technique, such that the overall quality of compressed MPEG video can be significantly enhanced when the transcoding is controlled in the joint temporal (picture or frame rate) and spatial (quantization) domains. One embodiment considers transcoding from high bit rate video with larger image size (e.g. 4CIF/4SIF, CIF) coded by one coding technique, e.g., MPEG-2 to a lower bit rate video with smaller image size (e.g. CIF, QCIF) coded by the same or another coding technique, e.g., MPEG-4.