There are provided encoding and decoding methods, and corresponding systems which are beneficial in connection to performing a search among regions of interest, ROIs, in encoded video data. In the encoded video data, there are independently decodable ROIs. These ROIs and the encoded video frames in which they are present are identified in metadata which is searched responsive to a search query. The encoded video data further embeds information which associates the ROIs with sets of coding units, CUs, that spatially overlap with the ROIs. In connection to independently decoding the ROIs found in the search, the embedded information is used to identify the sets of CUs to decode.