A method for decoding video data in connection to performing a search in the video data, comprising: receiving encoded video data which includes encoded video frames in which there are independently decodable regions of interest, wherein an independently decodable region of interest in a video frame is decodable by only using or referring to encoded video data in coding units of the encoded video frame that spatially overlap with the region of interest, receiving, as a data entity which is separate from the encoded video data, metadata comprising data units which each includes an identifier of an encoded video frame, an identifier of each region of interest in the encoded video frame, and an identification of which regions of interest in the encoded video frame that are independently decodable, wherein the encoded video data embeds information which associates the identifier of each region of interest being identified as independently decodable in the metadata with a set of coding units that spatially overlap with the region of interest, receiving a search query relating to a search among regions of interest in the encoded video data, in response to receiving the search query, searching in the metadata to find and provide identifiers of one or more regions of interest which are identified as independently decodable and the encoded video frames in which they are present, for each found region which is present in an encoded video frame: identifying a set of coding units being associated with the identifier of the region of interest by using the information embedded in the encoded video data, and decoding the identified set of coding units of the encoded video frame independently of video data in other video frames and independently of video data in coding units outside of the set of coding units in the encoded video frame to produce decoded video data corresponding to the region of interest. receiving encoded video data which includes encoded video frames in which there are independently decodable regions of interest, wherein an independently decodable region of interest in a video frame is decodable by only using or referring to encoded video data in coding units of the encoded video frame that spatially overlap with the region of interest, receiving, as a data entity which is separate from the encoded video data, metadata comprising data units which each includes an identifier of an encoded video frame, an identifier of each region of interest in the encoded video frame, and an identification of which regions of interest in the encoded video frame that are independently decodable, wherein the encoded video data embeds information which associates the identifier of each region of interest being identified as independently decodable in the metadata with a set of coding units that spatially overlap with the region of interest, receiving a search query relating to a search among regions of interest in the encoded video data, in response to receiving the search query, searching in the metadata to find and provide identifiers of one or more regions of interest which are identified as independently decodable and the encoded video frames in which they are present, for each found region which is present in an encoded video frame: identifying a set of coding units being associated with the identifier of the region of interest by using the information embedded in the encoded video data, and decoding the identified set of coding units of the encoded video frame independently of video data in other video frames and independently of video data in coding units outside of the set of coding units in the encoded video frame to produce decoded video data corresponding to the region of interest. identifying a set of coding units being associated with the identifier of the region of interest by using the information embedded in the encoded video data, and decoding the identified set of coding units of the encoded video frame independently of video data in other video frames and independently of video data in coding units outside of the set of coding units in the encoded video frame to produce decoded video data corresponding to the region of interest.