A method of transcoding from H.263 coded video frames to H.261 coded video frames, the method comprising for each INTER coded macro block (MB) of each frame, determining whether a component of the motion vector (MV) of the MB has a half pixel value, if yes, carrying out a MV search using the current H.263 decoded MB and a previous decoded frame to determine a new MV, the MV search being restricted to the vicinity of the H.263 coded MV, and coding the MB into an H.261 format using the new MV.