This work addresses the optimization of TV-resolution MPEG-2 video streams to be transmitted over lossy packet networks. This paper introduces a new scene-complexity adaptive mechanism, namely the Adaptive MPEG-2 Information Structuring (AMIS) mechanism. AMIS adaptively modulates the number of resynchronization points (i.e the slice headers and intra-coded macroblocks) in order to maximize the perceived video quality assuming it is aware of the packet loss probability and the error concealment technique implemented in the decoder. The perceived video quality depends both on the encoding quality and the degradation due to data loss. Therefore, AMIS constantly determines the best compromise between the rate allocated to pure video information and the rate aiming at reducing the sensitivity to packet loss. Results show that the proposed algorithm behaves much better than the traditional MPEG-2 encoding scheme in terms of perceived video quality under the same traffic constraints.