A compressed data stream modifier 270 is disclosed. The stream modifier modifies an input data stream that may comprise audio and video data streams conforming to any one of the well-known video compression standards, for example, MPEG or AVC. The input stream is first de-multiplexed to obtain a single video elementary stream. The video elementary stream is then decoded by means of a variable-length decoder and provided to the data stream modifier. A decoding complexity of each frame is estimated by an estimator 210 and provided to a controller 250. The controller selects a number of regions from each frame based on some psycho-visual criteria, such that a method of modification of these regions can bring the decoding complexity within an available capacity at a decoder. An efficient means of adapting a decoding complexity to an available capacity is thus obtained.