Encoded video data representing partial video images is decoded from a first video stream such as a HEVC bitstream. The first video stream comprises video images divided into a spatial array of independently decodable slices. The first video stream comprises network abstraction layer units that each contain video content data for a respective one of the slices preceded by a header that comprises parameters relating to the respective one of the slices in relation to the first video stream. Previously prepared information such as meta data about positions of parameters in the network abstraction layer units or a plurality of different versions of the network abstraction layer units for different partial image sizes (different picture sizes) is used. The meta data may be used for partially rewriting the network abstraction layer units for a subarray of slices, the network abstraction layer units being rewritten at a location selected on the basis of meta data, to make the network abstraction layer units consistent with a second video stream of encoded video data only for the sub-array of slices. Versions of the network abstraction layer units may be selected for the sub-array of slices, from the plurality of different versions. Subsequently, the partial video images are generated by decoding the encoded video data from the rewritten network abstraction layer units.