Patent Description:
Digital signatures provide a layer of validation and security to digital messages that are transmitted through a non-secure channel. By means of the digital signature, the authenticity or integrity of a message can be validated, and non-repudiation can be ensured. With regard to video coding particularly, there are safe and highly efficient methods for digitally signing a prediction-coded video sequence, which have been described in the prior art. See for example the earlier patent applications <CIT> (<CIT>) and <CIT> (<CIT>) by the present inventors. See also <CIT>, which proposes a cryptographic video verification technique that is specifically adapted for prediction-coded video data with a group-of-pictures structure.

A video sequence may need to be edited after it has been signed. In addition to visual improvements, the edits could aim to ensure privacy protection by cropping, masking, blurring or similar image processing that renders visual features less recognizable. With most available methods, this will require re-encoding and re-signing the edited frames in their entirety. The re-encoding and re-signing should preferably be extended into a number of neighboring frames too, even though the neighboring frames are not directly affected by the edits, so as not to disturb any prediction-coding dependencies (inter-frame/intra-frame references) that may exist. These steps may consume significant computational resources and could lead to delays that are awkward for the user.

<CIT> discloses a method of performing region-of-interest editing of a video stream in the compressed domain. The compressed video stream includes a compressed video stream frame, which represents a video stream frame having an unwanted portion and a region-of-interest portion. According to the method, the compressed video stream frame is edited to modify said unwanted portion and obtain a compressed video stream frame comprising said region-of-interest portion while maintaining an original structure of said video stream. To achieve this, said editing comprises skipping macroblocks located above, below and to the right of said region-of-interest portion for predictive coded (P) frames and bi-directionally predictive-coded (B) frames. The video stream under consideration in <CIT> is not a signed video stream.

One objective of the present disclosure is to make available a method of editing a signed video bitstream obtained by prediction coding of a video sequence that largely avoids the need to re-sign the bitstream outside the portions affected by the editing, as is the case with some available methods. A particular objective is to make available such a video editing method that preserves the signatures of all macroblocks except for the edited ones and any further macroblocks that refer to these, whether directly or indirectly. A further objective is to enable the video editing without any significant detriment to the data security of the original signed video bitstream. A further objective is to provide a method of validating a signed video bitstream obtained by prediction coding of a video sequence. It is a still further objective to provide devices and computer programs for these purposes.

At least some of these objectives are achieved by the invention as defined by the independent claims. The dependent claims relate to advantageous embodiments of the invention.

In a first aspect of the present disclosure, there is provided a method of editing a signed video bitstream, which has been obtained by prediction coding of a video sequence. The signed video bitstream shall include data units and associated signature units. Each data unit represents (i.e., encodes) at most one macroblock in a video frame of the prediction-coded video sequence. Each signature unit includes a digital signature of a bitstring derived from a plurality of fingerprints of exactly one associated data unit each. The signature unit may optionally include the bitstring to which the digital signature pertains. For a signed video bitstream with these characteristics, the method comprises the following steps: receiving a request to substitute a region of at least one video frame (e.g., substitute a privacy mask for the region's pixel values, in one or multiple video frames); determining a first set of macroblocks, in which said region is contained, and a second set of macroblocks referring directly or indirectly to macroblocks in the first set; adding an archive object to the signed video bitstream, the archive object including fingerprints of a first and a second set of data units, which respectively represent the determined first and second set of macroblocks; editing the first set of data units in accordance with the request to substitute; and re-encoding the second set of data units. The signature unit may optionally include the derived bitstring to which the digital signature pertains ('document approach').

Because each data unit represents at most one macroblock, it follows that the data units and macroblocks are in a one-to-one relationship, or some macroblocks are represented by - and can be reconstructed from - two or more data units. No data unit represents multiple macroblocks (nor portions of multiple macroblocks), and thus the direct effect of editing some macroblocks is confined to the edited macroblocks' data unit or data units (first set). Since furthermore each fingerprint is a fingerprint of exactly one associated data unit, the need for re-signing data units after the editing is kept in bounds. More precisely, the method according to the first aspect preserves any prediction-coding dependencies that connect pairs or groups of macroblocks, namely, by determining and re-encoding a set (second set) of data units representing macroblocks referring directly or indirectly to the edited macroblock(s). If the re-encoding is restricted to this second set of data units, the method will utilize available computational efforts efficiently. This allows the method to be executed with satisfactory performance on ordinary processing equipment.

The method according to the first aspect involves a further advantage on the recipient side. Thanks to the archive object, from which the fingerprints of the first and second sets of data units can be retrieved, a recipient will be able to validate all data units of the signed video bitstream that have not been affected by the editing. This allows a significant part of the existing signatures to be preserved; the video editing method according to the first aspect can be said to be minimally destructive in this regard. The validation at the recipient side will be explained in detail within the second aspect of the present disclosure.

In some embodiments, the archive object further includes positions of the first and second sets of macroblocks. A position may refer to the macroblock's position in a frame, e.g., in frame coordinates. If a static macroblock partitioning is used, the position of a macroblock can be expressed as a macroblock sequence number or another identifier. This provides one way of aiding a recipient of the edited video bitstream to determine whether a particular macroblock has been changed, and thus to select the proper way of obtaining a fingerprint of the data unit that represents said macroblock.

Some embodiments provide an advantageous procedure for editing the first set of data units. More precisely, such editing may include decoding the data unit into a reconstructed macroblock; providing an edited macroblock by performing the requested substitution on the reconstructed macroblock; and providing an edited data unit by encoding the edited macroblock. If the region to be substituted covers the entire reconstructed macroblock, the edited data unit may in particular be provided by encoding a subset of the region, e.g., an intersection of the macroblock and the region.

Within such embodiments, it is optional to encode the macroblock resulting after the substitution as an intra-coded macroblock (I-block), whereby an independently decodable data unit is obtained. This accounts for the fact that the substitution may introduce a sudden temporal change in the video sequence; this tends to lessen the time continuity of the video sequence, so that most known prediction coding techniques will perform less well.

Still within the above-outlined procedure for editing the first set of data units, it is possible to use the reconstructed macroblock to decode a data unit in the second set. The decoding is predictive since the second set of data units represent the second set of macroblocks, which refer directly or indirectly to the first set of macroblocks. The output of decoding said data unit in the second set will be used in the re-encoding step.

In different embodiments, the re-encoding of the second set of data units can be performed by prediction coding with reference to the edited first set of data units or it can be performed by non-predictive coding. The choice of one of these two options may correspond to striking a desired balance between quality and bitrate. Further still, the second set of data units may be re-encoded using reduced data compression. In lossy video coding formats, the data compression is achieved by discarding some of the information in the video sequence, such as by quantization of pixel values. The degree of quantization may for example correspond to a value of a quantization parameter (QP) representing the fineness of the quantized pixel values. The degree of quantization may further depend on the entries in the definition of a scaling matrix. Assuming the video sequence is encoded at a predetermined regular data compression level, it is foreseen to encode the second set of macroblocks at a data compression level that is reduced relative to the regular data compression. The use of the reduced data compression level will imply that a lesser amount of information in the macroblocks is discarded in the encoding step, e.g., by mapping the macroblock's pixel values to a relatively finer set of quantized pixel values. In other words, the macroblocks in the second set are encoded at a relatively higher bitrate than they would be if the regular data compression level was used, and it can be played back with less residual errors. The additional memory or bandwidth cost is likely to be acceptable, all the more so in use cases where edits usually occur infrequently and/or in isolated portions of the video sequence.

In some embodiments, the data security of the edited signed video bitstream is improved by providing, in the bitstream, one or more signature units associated with the edited first set of data units and/or the re-encoded second set of data units. This avoids a scenario of unauthorized modification of the edited first set of data units and the re-encoded second set of data units. The one or more signature units may be new signature units added to the bitstream or edited versions of signature units that were included in the signed video bitstream prior to the editing.

According to a generalization of the first aspect, there is provided a video editing method performed on a signed video sequence which includes data units and associated signature units. Each data unit represents at most N macroblocks in a video frame of the prediction-coded video sequence. Here, N is a small integer number, such as <NUM>, <NUM>, <NUM>, <NUM>, <NUM> or at most <NUM>. Each signature unit includes a digital signature of a bitstring derived from a plurality of fingerprints of exactly one associated data unit each and optionally the bitstring. The video editing method includes: receiving a request to substitute a region of at least one video frame; determining a first set of macroblocks, in which said region is contained, and a second set of macroblocks referring directly or indirectly to macroblocks in the first set; adding an archive object to the signed video bitstream, the archive object including fingerprints of a first and a second set of data units, which respectively represent the determined first and second set of macroblocks; editing the first set of data units in accordance with the request to substitute; and re-encoding the second set of data units.

Because, according to this generalization, each data unit represents at most N macroblocks, the direct effect of editing one macroblock is confined to the edited macroblock's at most N data units. Since furthermore each fingerprint is a fingerprint of exactly one associated data unit, the need for re-signing data units after the editing is kept in bounds. In particular, the archive object will hold at most N times as many fingerprints as the cardinality of the first and second sets of macroblocks, so that the video editing method will have feasible complexity.

In a second aspect of the present disclosure, there is provided a method of validating a signed video bitstream obtained by prediction coding of a video sequence. It is understood that the signed video bitstream includes data units, signature units each associated with some of the data units, and an archive object. Each data unit represents at most one macroblock in a frame of the prediction-coded video sequence. Each signature unit includes a digital signature of a bitstring and optionally the bitstring itself. Finally, the archive object includes at least one archived fingerprint of a data unit. The method of validating the signed video bitstream comprises: obtaining a fingerprint of each data unit associated with a signature unit, by either computing a fingerprint of the data unit, or retrieving an archived fingerprint from the archive object; deriving a bitstring from the obtained fingerprints; and validating the data units associated with the signature unit using the digital signature in the signature unit. The final validation step may include verifying the derived bitstring using the digital signature. Alternatively ('document approach'), the validation step includes verifying a bitstring in the signature unit using the digital signature, and comparing the derived bitstring and the verified bitstring.

The archive object may have been added by performing the editing method according to the first aspect, but the method according to the second aspect can be performed without reliable knowledge of such prior processing. Accordingly, the method according to the second aspect achieves a validation of the authenticity of the video sequence in that it verifies that the digital signatures (and any bitstrings) carried in the signature units are indeed consistent with the fingerprints of the associated data units. Hence, the data units cannot have been modified either.

The method according to the second aspect includes two options for obtaining the fingerprints of the data units, by direct computation or retrieval from the archive object. This supports the minimally destructive handling of the existing fingerprints during the editing phase (first aspect). The fact that each data unit represents at most one macroblock tends to limit the number of fingerprints that need to be archived for a given substitution request, which therefore limits the size of the archive object.

In some embodiments, the archive object further indicates the positions of the macroblocks that are represented by data units to which the archived fingerprints pertain. Put differently, an archived fingerprint is a fingerprint of a data unit, and the data unit represents (encodes) a macroblock, the position of which is indicated in the archive object. During the execution of the method according to the second aspect, to obtain the fingerprints of a data unit, it is determined, based on the positions indicated by the archive object, whether to compute the fingerprint or retrieve the fingerprint from the archive object.

A third aspect of the present disclosure relates to devices arranged to perform the method of the first aspect and/or the second aspect. These devices may be embedded in a system with a different main purpose (e.g., video recording, video content management, video playback) or they may be dedicated to said editing and validation, respectively. The devices within the third aspect of the disclosure generally share the effects and advantages of the first and second aspect, and they can be embodied with an equivalent degree of technical variation.

The invention further relates to a computer program containing instructions for causing a computer to carry out the above methods. The computer program may be stored or distributed on a data carrier. As used herein, a "data carrier" may be a transitory data carrier, such as modulated electromagnetic or optical waves, or a non-transitory data carrier. Non-transitory data carriers include volatile and non-volatile memories, such as permanent and non-permanent storage media of magnetic, optical or solid-state type. Still within the scope of "data carrier", such memories may be fixedly mounted or portable.

In a further aspect of the present disclosure, there is provided a signed video bitstream which includes data units and associated signature units. Each data unit represents at most N macroblocks in a video frame of the prediction-coded video sequence. Here, N is a small integer number, such as <NUM>, <NUM>, <NUM>, <NUM>, <NUM> or at most <NUM>. Each signature unit includes a digital signature of a bitstring derived from a plurality of fingerprints of exactly one associated data unit each and optionally the bitstring itself. The signed video bitstream is suitable for editing since the direct effect of editing one macroblock is confined to the at most N data units of the edited macroblock, and since each fingerprint is a fingerprint of exactly one associated data unit. This restricts the propagation of the editing to a limited number of data units, so that fewer data units need to be re-signed after the editing.

It should be noted that as used in this disclosure, a "macroblock" may advantageously be an encoding macroblock. However, the invention is applicable also to video that is not prediction encoded and in a more generalized case, a macroblock can therefore be any contiguous group of pixels. As the signing of the video is done on decoded frames, the grouping of pixels need not be limited to any encoding group partitioning.

The steps of any method disclosed herein do not have to be performed in the exact order described, unless explicitly stated.

The aspects of the present disclosure will now be described more fully hereinafter with reference to the accompanying drawings, on which certain embodiments of the invention are shown. These aspects may, however, be embodied in many different forms and should not be construed as limiting; rather, these embodiments are provided by way of example so that this disclosure will be thorough and complete, and to fully convey the scope of all aspects of the invention to those skilled in the art.

In the terminology of the present disclosure, a "video bitstream" includes any substantially linear data structure, which may be similar to a sequence of bit values. A video bitstream can be carried by a transitory medium (e.g., modulated electromagnetic or optical waves), as in some streaming use cases, or the video bitstream can be stored on a non-transitory medium, such as a volatile or non-volatile memory.

The video bitstream represents a video sequence, which may be understood to be a sequence of video frames to be played back sequentially with nominal time intervals. Each video frame may be partitioned into macroblocks. In the present disclosure, further, a "macroblock" can be a transform block or a prediction block, or a block with both of these uses, in a frame of the video sequence. The usage of "frame" and "macroblock" herein is intended to be consistent with an H. 26x video coding standard or similar specifications. A "macroblock" can furthermore be a coding block. As noted above, although the term macroblock is used, the grouping of pixels need not be limited to any partitioning used for encoding; rather, a macroblock may be any groups of neighboring pixels. When applied in the case of prediction-based encoding, it may be advantageous to use the same partitioning as used for the encoding.

<FIG> illustrate an example partition of a video frame <NUM> into a <NUM> × <NUM> uniform arrangement of macroblocks <NUM>. It may be noted that this is a simplification for illustration purposes. In practice, a video frame <NUM> is generally partitioned into much larger numbers of macroblocks; for example, a macroblock could be <NUM> × <NUM> pixels, <NUM> × <NUM> pixels or <NUM> × <NUM> pixels. Curled arrows are consistently used herein to indicate an intra-frame or inter-frame reference to be used in prediction coding. Without departing from the scope of the present disclosure, the partition into macroblocks seen in <FIG> can be varied significantly, to include non-square arrangements and/or arrangements of macroblocks <NUM> that are not homothetic to the video frame <NUM> and/or mixed arrangements of different macroblocks <NUM> that have different sizes or shapes. It is appreciated that some video coding formats support dynamic macroblock partitioning, i.e., the partition may be different for different video frames in a sequence. This is true, for example, of H.

In <FIG>, the pattern of intra-frame references is restricted to a single row of macroblocks <NUM>. Indeed, each macroblock <NUM> refers to the macroblock to its immediate left (if it exists in the frame <NUM>) in the sense that it is represented by a data unit that expresses the image data in the macroblock predictively, that is, the image data in this macroblock is expressed relative to the image data in the macroblock to the left. Conceptually, and somewhat simplified, the data unit expresses the macroblock <NUM> in terms of the change or movement relative to the left macroblock. Another possible understanding is that the data unit represents a correction of a predefined prediction operation that derives the macroblock <NUM> from the left macroblock. In an alternative within the scope of the present disclosure, a macroblock <NUM> may refer to another macroblock <NUM> to its right, or above or below it.

In <FIG>, the pattern of intra-frame references is denser. Here, each macroblock <NUM> refers to the macroblock to its immediate left (if it exists in the frame <NUM>) and to the macroblock immediately above it (if it exists in the frame <NUM>). Accordingly, the macroblock <NUM> is represented by a data unit that expresses the image data in the macroblock predictively, e.g., in terms of a difference , or in terms of a correction of a prediction of this image data based on a predefined interpolation operation (or some other predefined combination) acting on the image data in the left and upper macroblocks. The interpolation may include postconditioning operations such as smoothing. A further alternative, still within the scope of the present disclosure, is to use intra-frame references with directions opposite to that shown in <FIG>, i.e., starting in the lowest row.

An image/video format with a predefined pattern of intra-frame references can be associated with a specified scan order, which represents a feasible sequence for decoding the macroblocks. In <FIG>, the macroblock scan order is non-unique, namely, since each row can be decoded independently. For the pattern according to <FIG>, the macroblocks can be decoded either row-wise from above or column-wise from the left; a video format with this reference pattern may specify a column-wise or row-wise scan order, so that any reconstruction errors can be anticipated on the encoder side, which benefits coding efficiency. Further, there exist video formats with arbitrary macroblock ordering or so-called slicing.

<FIG> shows a video sequence V including a sequence of frames <NUM>. There are independently decodable frames (I-frame) and predictive frames in the video sequence V, including unidirectionally predictive frames (P-frame) and bidirectionally predictive frames (B-frame). Recommendation ITU-T H. <NUM> (<NUM>/<NUM>) "Advanced video coding for generic audiovisual services", International Telecommunication Union, specifies a video coding standard in which both forward-predicted and bidirectionally predicted frames are used. As seen in <FIG>, the independently decodable frames do not refer to any other frame. The unidirectionally predictive frames (P-frames) in <FIG> are forward-predicted in that they refer directly to at least one other preceding or immediately preceding frame. The bidirectionally predictive frames (B-frames) can additionally refer directly to a subsequent or immediately subsequent frame in the video sequence V. A first frame refers indirectly to a second frame if the video sequence includes a third frame (or subsequence of frames) to which the first frame refers directly and which, in turn, refers directly to the second frame. In predictive video coding, a group of pictures (GoP) is defined as a subsequence of video frames that do not refer to any video frame outside the subsequence; it can be decoded without reference to any other I-, P- or B-frames. The video frames in <FIG> form a GoP. The GoPs in <FIG> are minimal since they cannot be subdivided into further GoPs.

In simpler implementations, a video sequence V may consist of independently decodable frames (I) and unidirectionally predictive frames (P) only. Such a video sequence may have the following appearance: IPPIPPPPIPPPIPPP, where each P-frame refers to the immediately preceding I- or P-frame. The following GoPs can be discerned in this example: IPP, IPPPP, IPPP, IPPP.

There are several options for coordinating inter-frame and intra-frame prediction coding. For example, if a static (fixed) macroblock partition is used in all video frames, the inter-frame references like those exemplified may be defined at the level of one macroblock position (e.g., upper left macroblock in <FIG>) at a time. Some video formats allow dynamic macroblock partitions, e.g., a macroblock can be predicted either from the corresponding pixels in a preceding video frame or from spatially shifted pixels in the preceding frame. Alternatively, the inter-frame references are defined for entire video frames. An I-frame consists of I-blocks only, whereas a P-frame may consist of only P-blocks or a mixture of I-blocks and P-blocks.

Turning to <FIG>, attention will now be directed to the video bitstream that encodes the video sequences under consideration. The subfigures 3A, 3B, 3C and 3D illustrate different correspondence patterns between data units <NUM> and the macroblocks <NUM> that they represent (encode). For purposes of the present disclosure, a data unit may have any suitable format and structure; no assumption is being made other than that the data unit can be separated (or extracted) from the video bitstream, e.g. to allow for processing, without any need to decode that data unit or any surrounding data units. A signed video bitstream further includes, in addition to the data units, signature units that are separable from the signed video bitstream in a same or similar manner. Details about signature units will be presented below with reference to <FIG>.

Under one option, as illustrated in <FIG>, the data units <NUM> are in a one-to-one correspondence (dashed lines) to the macroblocks <NUM>. This correspondence pattern allows each macroblock <NUM> to be always reconstructed from one data unit <NUM>. Further, no other data unit <NUM> than the corresponding data unit <NUM> needs to be modified if a macroblock <NUM> is edited (although, certainly, modifications to signature units, metadata and the like may be necessary).

Alternatively, as illustrated in <FIG>, each macroblock <NUM> is encoded by multiple data units <NUM>. Still each data unit <NUM> represents at most one macroblock <NUM>. Therefore, if each macroblock <NUM> is encoded by at most M data units <NUM>, then it follows that any macroblock <NUM> can be reconstructed from at most M data units <NUM>. An edit made to a macroblock <NUM> has a direct effect on at most M data units <NUM>. It is assumed that M is a small integer number, such as <NUM>, <NUM>, <NUM>, <NUM>, <NUM> or at most <NUM>.

Under a further option, as illustrated in <FIG>, each data unit <NUM> encodes multiple macroblocks <NUM>. This means that the effects of an edit made to a macroblock <NUM> are not limited to the macroblock <NUM> itself, but it may become necessary to re-encode and/or re-sign a data unit <NUM> that the edited macroblock <NUM> shares with a further macroblock <NUM>. Because it may be computationally wasteful to perform the re-signing on an unnecessarily large data set, this correspondence pattern is not applied in the best-performing embodiment in the present disclosure though quite possible to implement. The total added computational effort may be kept limited if a data unit <NUM> is allowed to be shared by at most a predefined number N of macroblocks <NUM>. Again, N may be specified to be a small integer number, such as <NUM>, <NUM>, <NUM>, <NUM>, <NUM> or at most <NUM>.

Combinations of the patterns seen in <FIG> are possible within the scope of the present disclosure. As a result, the techniques proposed herein can be applied to video bitstream where the ratio of macroblocks <NUM> to data units <NUM> may be <NUM>:<NUM>, <NUM>:<NUM>, <NUM>:<NUM>, <NUM>:<NUM>, <NUM>:<NUM>, <NUM>:<NUM> or <NUM>:<NUM>.

Under a still further option, as illustrated in <FIG>, each data unit <NUM> is allowed to represent any number of macroblocks <NUM> in the video sequence, and each macroblock <NUM> may be encoded by any number of data units <NUM>. This correspondence pattern, as suggested by the dashed lines, could at worst imply that even a limited edit operation on a macroblock <NUM> will necessitate complete re-encoding and re-signing of the video sequence. The techniques disclosed herein are not to be practiced on video sequences with the structure shown in <FIG>.

<FIG> illustrates an editing operation to be described below.

<FIG> depicts a section of a video sequence V including a succession of macroblocks <NUM> belonging to one or more video frames. For example, the macroblocks <NUM> may occupy a fixed position (e.g., upper left macroblock in <FIG>) in consecutive video frames. The macroblocks <NUM> are assumed to have been predictively coded in accordance with the references indicated by curly arrows. The video sequence V is encoded as a signed video bitstream B which includes data units <NUM> and signature units <NUM>. For purposes of illustration, not limitation, <FIG> shows the data units <NUM> such that they encode the video macroblocks <NUM> in accordance with a correspondence pattern that may be described as a hybrid of the patterns shown in <FIG> and allowing a regular or irregular alternation between these (e.g., based on macroblock size, wherein a larger macroblock <NUM> corresponds to multiple data units <NUM>, while a smaller or more compressed macroblock <NUM> corresponds to a single data unit <NUM>). Nonetheless, each data unit <NUM> represents at most one macroblock <NUM>. The data units <NUM> may be in accordance with a proprietary or standardized video coding format, such as ITU-T H. <NUM> or AV1. The bitstream B may further include, without departing from the scope of the present disclosure, additional types of units (e.g., dedicated metadata units).

Each of the signature units <NUM> can be associated with a plurality of data units <NUM>. In <FIG>, it is understood that the data units <NUM> between two consecutive signature units <NUM> are associated with the later signature unit <NUM>; this is not an essential feature of the invention, and other conventions are possible without departing from the scope of this disclosure. A signature unit <NUM> could be associated with a set of data units <NUM> that are all contained in one GoP, but other association patterns - like the one seen in <FIG> - are possible as well. Further, the set of data units <NUM> to be associated with one signature unit <NUM> is preferably selected in view of an applicable macroblock scan order. For instance, the set of data units <NUM> associated with a signature unit <NUM> could represent a number of macroblocks that are to be sequentially scanned during decoding, whereby the number of macroblocks that need to be revisited if a signature unit <NUM> fails to validate is minimized.

The signature unit <NUM> includes at least one bitstring (e.g., H<NUM>) and a digital signature of the bitstring (e.g., s(H<NUM>)). The presence of the bitstring is optional, as suggested by the use of dashed line. In the case where a signature unit <NUM> includes multiple bitstrings, the signature unit <NUM> may have one digital signature for all of these bitstrings, or multiple digital signatures for single bitstrings each or for subgroups of bitstrings each. The bitstring from which the digital signature is formed may be a combination of fingerprints of the associated data units <NUM> or it may be a fingerprint of said combination of fingerprints of the associated data units <NUM>. The combination of the fingerprints (or 'document') may be a list or other concatenation of string representations of the fingerprints. In the ITU-T H. <NUM> and H. <NUM> formats, the signature unit may be included as a Supplemental Enhancement Information (SEI) message in the video bitstream. In the AV1 standard, the signature may be included in a Metadata Open Bitstream Unit (OBU).

Each of the fingerprints may be a hash or a salted hash. A salted hash may be a hash of a combination of the data unit (or a portion of the data unit) and a cryptographic salt; the presence of the salt may stop an unauthorized party who has access to multiple hashes from guessing what hash function is being used. Potentially useful cryptographic salts include a value of an active internal counter, a random number, and a time and place of signing. The hashes may be generated by a hash function (or one-way function) h, which is a cryptographic function that provides a safety level considered adequate in view of the sensitivity of the video data to be signed and/or in view of the value that would be at stake if the video data was manipulated by an unauthorized party. Three examples are SHA-<NUM>, SHA3-<NUM> and RSA-<NUM>. The hash function shall be predefined (e.g., it shall be reproducible) so that the fingerprints can be regenerated when the recipient is going to verify the fingerprints. In the example of <FIG>, the bitstrings are given by <MAT> and <MAT> where h<NUM>, h<NUM>,. are hashes of the data units and [·] denotes concatenation. Example salted hashes can be defined as <MAT> or <MAT> where σ is the cryptographic salt. In the first example, the hash function h has a parametric dependence on the second argument, to which the salt σ has been assigned.

In some embodiments, each of the fingerprints h<NUM>, h<NUM>,. is computed from the data unit <NUM> directly, e.g., from coded transform coefficients or other video data therein. The fingerprint may be computed from the entire data unit or from a subset thereof that has been extracted according to a pre-agreed rule. In other embodiments, the fingerprints h<NUM>, h<NUM>,. are computed from a reconstructed macroblock obtained by decoding the data unit <NUM>, e.g., pixel values or other plaintext data. In still other embodiments, the fingerprints h<NUM>, h<NUM>,. are computed neither on plaintext level or bitstream level, but instead from intermediate reconstruction data derived from the data unit. More precisely, if an encoder is used that comprises a frequency-domain transformation (e.g., DCT, DST, DFT, wavelet transform) followed by a coding process (e.g., entropy, Huffman, Lempel-Ziv, run-length, binary or non-binary arithmetic coding, such as context-adaptive variable-length coding, CAVLC, context-adaptive binary arithmetic coding, CABAC), the transform coefficients will normally be available as intermediate reconstruction data at the decoder side. The transform coefficients can be restored from the coded representation. If the encoder further includes a quantization process immediately downstream of the transformation, the quantized transform coefficients will be available at the decoder side. In more complex codecs, with a greater number of sequential processing stages, there may be further types of intermediate reconstruction data, and these may be used for the fingerprint computation. It is particularly convenient to use a type of intermediate reconstruction data which, like the quantized transform coefficients, appears identically in the encoding process. Common to all the embodiments reviewed in this paragraph, a fingerprint pertains to exactly one data unit <NUM> associated with the signature unit <NUM>.

Optionally, to discover unauthorized removal or insertion of data units, the fingerprints can be linked together sequentially. This is to say, each fingerprint has a dependence on the next or previous fingerprint, e.g., the input to the hash includes the hash of the next or previous fingerprint. The linking can for example be realized as follows: h<NUM> = h(X<NUM>), h<NUM> = h([h<NUM>, X<NUM>]), h<NUM> = h([h<NUM>, X<NUM>]) etc., where X<NUM>, X<NUM>, X<NUM> denote data from a first, second and third one of the data units <NUM>.

Still with reference to the signature units <NUM> in <FIG>, to generate the digital signature s(H<NUM>), a cryptographic element (not shown) with a pre-stored private key may be utilized. The recipient of the signed video bitstream may be supposed to hold a public key belonging to the same key pair (see also <FIG>), which enables the recipient to verify that the signature produced by the cryptographic element is authentic but not generate new signatures. The public key could also be included as metadata in the signed video bitstream, in which case it is not necessary to store it at the recipient side.

With reference to <FIG>, there will now be described a method <NUM> of editing a signed video bitstream B obtained by prediction coding of a video sequence V. It is assumed that the non-optional steps of the method <NUM> are performed after the original signing of the video bitstream. For example, if the signed video bitstream is originally generated at a recording device, the editing method <NUM> may be performed in a video management system (VMS). Another example use case is where the signed video bitstream is generated at a device, is stored in memory and is then revisited for editing using the same device. The editing may take place at a later point in time, e.g., after a need to perform privacy masking has become known.

Although, as noted, the device performing the editing method <NUM> may be an application or system dedicated for a particular purpose, it may have the basic functional structure shown in <FIG>. As illustrated, device <NUM> includes processing circuitry <NUM>, memory <NUM> and an external interface <NUM>. The memory <NUM> may be suitable for storing a computer program <NUM> with instructions implementing the editing method <NUM>. The external interface <NUM> may be a communication interface allowing the device <NUM> to communicate with an analogous device (not shown) held by a recipient and/or a video content author (e.g., a recording device), or it may allow read and write operations in an external memory <NUM> suitable for storing video bitstreams.

<FIG> illustrates the case where a bitstream is transferred among multiple devices. It is noted that the device performing the editing method <NUM> may be connected to the recipient device over a local-area network (connection lines in lower half of <FIG>) or over a wide-area network <NUM>. Attacks on the bitstream B can occur on either type of network, which justifies the signing.

Returning to <FIG>, one embodiment of the method <NUM> begins with a step <NUM> of receiving a request to substitute a region of at least one video frame <NUM> in a video sequence V. The request may be received via a human-machine interface from a human operator or in an automated way, e.g., in a message from a control application executing on the same device <NUM> or remotely. The region to be substituted may be a set of substitute pixel values, such as a privacy mask, which is to replace analogously located pixels in the video sequence V.

For the avoidance of doubt, it is noted that the video sequence V to be edited is encoded by prediction coding as a signed video bitstream B, which includes, data units <NUM> and associated signature units <NUM>, wherein each data unit represents at most one macroblock <NUM> in a video frame <NUM> of the prediction-coded video sequence V, and wherein each signature unit includes a digital signature of a bitstring derived from a plurality of fingerprints of exactly one associated data unit each. Such a bitstream format has been exemplified with reference to <FIG>.

In a next step <NUM> of the method <NUM>, a first set of macroblocks, in which said region is contained, and a second set of macroblocks referring directly or indirectly to macroblocks in the first set are determined. Recalling that bidirectionally predictive frames (B-frames) can be defined in some video coding formats, it is appreciated that the second set of macroblocks can be located before or after the first set of macroblocks, or occupy both of these locations. It is understood that the first and second sets are defined to be disjoint. For example, it may be stipulated that a macroblock belongs to the second set only if it does not belong to the first set, i.e., only if this macroblock is not needed in order to form a set of macroblocks that contains the region to be substituted. It follows that the second set of macroblocks is normally empty if the first set of macroblocks extends up to the boundary of a GoP. It is appreciated, further, that the second set of macroblocks may contain macroblocks in more than one P-frame or more than two B-frames since, depending on the video encoder initially used, additional frames may use the substituted region as reference.

If the region to be substituted is limited to a single video frame, the first set of macroblocks can be determined with reference only to the macroblock partition of the frame. More precisely, the first set is all macroblocks with which the region overlaps (that is, the macroblocks with which the region has a non-empty intersection in pixel space). If the region extends to multiple frames, this operation is repeated for each frame. In the special case where the region repeats identically in all of the video frames and additionally the macroblock partition is constant across all said frames, the first set of macroblocks is a copy of those determined (by the overlap criterion) for the initial frame for each of the following frames. The second set of macroblocks can be determined on the basis of the first set and the pattern of intra-frame and inter-frame references in the signed prediction-coded video sequence. Because such references by definition do not extend past GoP boundaries, the search for macroblocks to be included in the second set can be restricted to that GoP or those GoPs to which the first set of macroblocks belong.

A possible outcome of step <NUM> is illustrated in <FIG>, where each column represents one video frame of a video sequence V and each row represents one macroblock at a particular position in the frame (e.g., upper left macroblock). In <FIG>, further, references between macroblocks have been indicated as curled arrows, and a boundary between two consecutive GoPs, GoP1 and GoP2, has been shown as a dashed vertical line. It is noted that the inter-frame references are defined at the level of one macroblock positions in <FIG>. Further, the diagonally hashed macroblocks are those directly affected by the request to substitute the region; they are all located in the <NUM>st frame and form the first set <NUM> of macroblocks. The macroblocks with dotted shading are all macroblocks that refer directly (<NUM>nd frame) or indirectly (<NUM>rd frame) to the macroblocks in the first set, and they are identified as the second set <NUM> of macroblocks. In line with expectation, the second set of macroblocks does not extend past the GoP boundary.

It is noted that the composition of the first and second sets of macroblocks seen in <FIG> could be altered if an intra-frame reference is introduced but not necessarily. For example, if the macroblock position corresponding to the first row refers to the macroblock position corresponding to the second row, the first and second sets of macroblocks <NUM>, <NUM> would remain unchanged.

A next step <NUM> of the method <NUM> will be illustrated with respect to <FIG>, which shows the video sequence V and the signed video bitstream B after the substitution of the region has been carried out. In <FIG>, diagonal hashing is used for the first set of macroblocks <NUM>, <NUM>, and dotted shading is used for the macroblocks <NUM>, <NUM> in the second set of macroblocks.

In step <NUM>, an archive object <NUM> is added to the signed video bitstream B. The archive object <NUM> includes fingerprints of a first and a second set of data units, namely, the data units which respectively represent the first and second set of macroblocks determined in step <NUM>. It is preferable though not strictly necessary that the fingerprints are individual fingerprints pertaining to exactly one data unit each. In implementations where the fingerprints are computed from macroblocks reconstructed from the data units, which is one of the options mentioned above, and the re-encoding is expected to faithfully preserve these macroblocks, then the fingerprints of the second set of data units need not be included in the archive object <NUM>. At the level of the signed video bitstream B, the archive object <NUM> has a similar format as the data units <NUM> and signature units <NUM>, in that the archive object <NUM> can be separated from the video bitstream without decoding.

In <FIG>, the first set of data units corresponds to the third, fourth and fifth data units <NUM>, and the second set of data units corresponds to the sixth and seventh data units <NUM>. Accordingly, the (two) archive objects <NUM> added to the signed video bitstream B in step <NUM> will together store fingerprints h<NUM>, h<NUM>, h<NUM>, h<NUM>, h<NUM>. Optionally, each archive object <NUM> may include a digital signature of these fingerprints, or a digital signature of a combination of these fingerprints in this archive object <NUM>, or it may include a digital signature of a fingerprint of said combination. Further optionally, the archive objects <NUM> may as well include positions of the first and second sets of macroblocks, the signatures of which have been archived. A position may refer to the macroblock's position in a frame, e.g., in frame coordinates, and this in turn corresponds to a position in the bitstring. If a static macroblock partition is used, the position of a macroblock <NUM> can be expressed as a macroblock sequence number or another identifier. For example, the bitstring may be formed by concatenating the fingerprints in the same order as the macroblock sequence in a frame.

The execution flow of the editing method <NUM> then proceeds to step <NUM>, where the first set of data units are edited in accordance with the request to substitute the region. In other words, step <NUM> leaves the signed video bitstream B with some data units replaced or modified.

In some embodiments, step <NUM> may include decoding <NUM> the data unit into a reconstructed macroblock; providing <NUM> an edited macroblock by performing the requested substitution on the reconstructed macroblock; and providing <NUM> an edited data unit by encoding the edited macroblock.

Optionally, the macroblock resulting after the substitution <NUM> (e.g., macroblocks <NUM> and <NUM> in <FIG>) may be encoded as an independently decodable data unit. The independently decodable data unit may correspond to an I-frame in the H. <NUM> or H. <NUM> coding specifications, an encoded macroblock that does not refer to another macroblock, or data units equivalent to these. This is in line with the realization that the substitution introduces a sudden temporal change in the video sequence, which could lessen performance of the prediction coding.

In a next step <NUM> of the method <NUM>, the second set of data units is re-encoded. A generally desirable aim is for the re-encoded second set of data units to decode into macroblocks resembling as closely as possible the (original) second set of macroblocks. With reference to the decoder application, the aim is for the re-encoded second set of data units to produce a near-identical reference buffer content and/or a near-identical decoder state. However, while the macroblocks in the second set (e.g., macroblocks <NUM> and <NUM> in <FIG>) shall be unchanged, they contain references to the macroblocks in the first set, which generally become unusable when the first set of macroblocks change. Because of the sudden temporal change introduced by the editing, the first set of macroblocks ceases to provide a promising basis for predicting the second set of macroblocks. The re-encoding <NUM> may be facilitated by the optional substep <NUM>, which outputs a reconstructed macroblock, based on which the second set of macroblocks can be reconstructed, namely, by decoding the second set of data units.

The second set of macroblocks may advantageously be re-encoded <NUM> using reduced data compression. This is to be understood against the background that the video sequence V is encoded at a predetermined regular level data compression. More precisely, it is foreseen that the second set of macroblocks are encoded at a reduced level of data compression in comparison with the regular data compression.

To encode the second set of macroblocks in step <NUM>, the main options are non-predictive coding and predictive coding. If non-predictive coding is used, the second set of macroblocks are encoded in independently decodable form, as intra-coded blocks, also referred to as I-blocks. The coded second set of macroblocks will thus be represented by independently decodable data units. Under this option, it is furthermore possible to use non-lossy coding for the second set of macroblocks; for example, the second set of macroblocks may be represented by unencoded, 'raw' blocks, such as a plain list of the original values for each position in the macroblock in appropriate color space.

Under the second option, predictive coding, step <NUM> may be executed by re-encoding the second set of data units using prediction coding with reference to the edited first set of data units. More precisely, applying step <NUM> to a data unit may include: obtaining <NUM> a macroblock reconstructed from a further data unit, to which said data unit refers directly; decoding <NUM> said data unit using the reconstructed macroblock; obtaining <NUM> a reconstructed edited version of the macroblock; and providing <NUM> an edited data unit by re-encoding said data unit by prediction coding with reference to the reconstructed edited version of the macroblock. Substep <NUM> may include decoding the further data unit (see step <NUM>), and the further data unit can belong to the first or second set of data units. In substep <NUM>, the reconstructed edited version of the macroblock may correspond to the image data produced in substep <NUM> above, that is, by performing the requested substitution on the reconstructed macroblock. Substep <NUM> may include expressing the macroblock in the second set (i.e., the macroblock which is being processed) in terms of a difference or correction relative to the reconstructed edited version of the macroblock (which originated from said further data unit). As mentioned, this option is mainly useful if the edits performed in the first set of macroblocks are relatively limited, or else the prediction coding might not perform satisfactorily.

In an optional final step <NUM> of the method <NUM>, one or more signature units <NUM> associated with the edited first set of data units and the re-encoded second set of data units are provided in the signed video bitstream B. The signature units <NUM> provided in step <NUM> may have the same structure as the signature units <NUM> described above. Accordingly, the signature unit <NUM> may include a bitstring derived from fingerprints of one edited data unit each and a digital signature of this bitstring, or the signature unit <NUM> may include the digital signature only. A signature unit <NUM> provided in step <NUM> may be a newly generated signature unit, as suggested in <FIG>. Alternatively, the signature unit <NUM> is provided by editing an existing signature unit, notably by extending it with a further digital signature.

As already mentioned, steps of any method disclosed herein do not have to be performed in the exact order described, unless explicitly stated. This is illustrated notably by the editing method <NUM>, wherein it is clearly possible to perform step <NUM> before, between or after the subsequence of steps <NUM> and <NUM>, as desired.

In some embodiments, the method <NUM> further includes an initial step <NUM> of providing at least one signature unit <NUM>. It is understood that, in use cases believed to be of primary interest, step <NUM> is performed by a different entity than steps <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and <NUM> of the method <NUM>, and/or step <NUM> is performed at an earlier point in time. Either way, step <NUM> is separated from the subsequent steps <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and <NUM> by a relatively unsecure data transfer and/or a storage period that justifies signing to ensure the desired level of data security.

The optional step <NUM> may comprise the substeps of computing <NUM> a plurality of fingerprints of respective data units associated with the signature unit; deriving <NUM> a bitstring from the plurality of fingerprints; and obtaining <NUM> a digital signature of the bitstring, wherein the bitstring is a combination of said plurality of fingerprints or a fingerprint of said combination. Suitable implementations of the fingerprint computation <NUM>, the bitstring derivation <NUM> and the digital signing <NUM> have been discussed in detail above. In particular, the bitstring to which the digital signature in the signature unit <NUM> pertains may be a combination of fingerprints of the associated data units <NUM>, or it may be a fingerprint of said combination of fingerprints of the associated data units <NUM>. The combination (or 'document') may be a list or another concatenation of respective string representations of the fingerprints.

Having thus completed the description of the editing method <NUM>, attention is now directed to the recipient side. More precisely, with reference to the flowchart in <FIG>, a method <NUM> of validating a signed video bitstream B will be described. It is again assumed that the signed video bitstream B has been obtained by prediction coding of a video sequence V and, optionally, by subsequent editing operations. It is not essential that the signed video bitstream B has been processed according to the editing method <NUM>. It is moreover assumed that the signed video bitstream includes data units <NUM>, associated signature units <NUM> and an archive object <NUM>. Here, each data unit <NUM> represents at most one macroblock <NUM> in a frame <NUM> of the prediction-coded video sequence V, each signature unit <NUM> includes a digital signature (e.g., s(H<NUM>), s(H<NUM>)) of a bitstring (e.g., H<NUM>, H<NUM>) and optionally the bitstring itself, and the archive object <NUM> includes at least one fingerprint, which may be an archived fingerprint of a data unit that is now absent from the bitstream B and/or has undergone editing. It is irrelevant for the validation method <NUM>, and usually not possible to determine at the recipient side, whether a particular signature unit <NUM> was added in connection with editing (e.g., by the editing method <NUM>) or it was part of the original, not-edited bitstream B.

In an optional first step <NUM> of the method <NUM>, which is only carried out in some embodiments ('document approach'), the bitstring H<NUM> in one signature unit <NUM> is validated using the digital signature s(H<NUM>), so as to verify that the fingerprints contained therein are authentic, in a per se known manner. As illustrated in <FIG>, the validation may be performed using a cryptographic element <NUM>, which is located in the recipient device <NUM> and in which a public key is deposited. This can be described as an asymmetric signature setup, where signing and verification are distinct cryptographic operations corresponding to private/public keys. Other combinations of symmetric and/or asymmetric verification operations are possible without departing from the scope of the present disclosure. If the outcome V<NUM> of the bitstring validation is negative (reject), the execution of the method <NUM> ends. If instead the outcome V1 is positive (approve), the execution of the method <NUM> proceeds to the second step <NUM>.

In a second step <NUM>, a fingerprint h<NUM>, h<NUM>,. of each data unit <NUM> associated with the signature unit <NUM> is obtained. An independent decision <NUM> on how to obtain the fingerprint can be made for each data unit. More precisely, either the fingerprint is computed <NUM> from the data unit, or the fingerprint is retrieved <NUM> from an archive object <NUM> in the bitstream. As explained above, the fingerprint can be computed from (a subset of) this data unit <NUM> directly, e.g., from transform coefficients or other video data therein, for from a reconstructed macroblock obtained by decoding the data unit <NUM>. It is seen in <FIG>, that the fingerprints h<NUM>, h<NUM> are computed from the data units <NUM>, whereas the remaining fingerprints h<NUM>, h<NUM>, h<NUM>, h<NUM> are retrieved from the archive object <NUM>. Accordingly, it is only fingerprints h<NUM>, h<NUM> that can cause the validation in the forthcoming fourth step <NUM> to fail, in which case the failure suggests that an unauthorized manipulation of the bitstream B has taken place.

In a third step <NUM>, a bitstring H<NUM> is derived from the fingerprints thus obtained. This may be done according to a pre-agreed rule, e.g., by a procedure analogous to those described within step <NUM>. It is recalled that the bitstring may be a combination of the obtained fingerprints or it may be a fingerprint of said combination of fingerprints.

Finally, in a fourth step <NUM>, the data units associated with the signature unit <NUM> under consideration are validated using the digital signature in the signature unit <NUM>. For the avoidance of doubt, it is noted that the validation in step <NUM> of the data units is indirect, without any processing that acts on the data units themselves.

In embodiments where the signature units <NUM> do not contain the bitstring H<NUM>, step <NUM> is executed by verifying the derived bitstring H<NUM> using the digital signature s(H<NUM>). For example, the derived bitstring H<NUM> can be verified using a public key belonging to the same key pair as the private key which was used to generate the digital signature s(H<NUM>). In <FIG>, this is illustrated by feeding the derived bitstring H<NUM> and digital signature s(H<NUM>) to a cryptographic entity <NUM> where the public key is stored, which outputs a binary result W1 representing the outcome of the verification.

Alternatively, in embodiments where the signature units <NUM> do contain the bitstring H<NUM> ('document approach'), said bitstring H<NUM> has been verified initially in step <NUM>, and the verified bitstring H<NUM> is then compared, in step <NUM>, with the derived bitstring H<NUM>. The comparison may be a bitwise equality check, as suggested by the functional block <NUM> in <FIG>, which yields a true- or false-valued output V2. If the result V2 of the comparison is true, then it may be concluded that the signed video bitstream <NUM> is authentic as far as this signature unit <NUM> is concerned.

The execution of the method <NUM> may then include repeating relevant ones of the above-described steps <NUM>, <NUM>, <NUM> for any further signature units <NUM> in the signed video bitstream <NUM>. If the outcome is positive for all signature units <NUM>, it is concluded that the signed video bitstream <NUM> is valid, and it may be consumed or processed further. In the opposite case, the signed video bitstream <NUM> shall be considered unauthentic, and it may be quarantined from any further use or processing.

It is noted that the validation of the data units in the first set is based on a different trust relationship than the validation of the data units in the second set. The data units in the first set are validated by trusting the entity that created the digital signature s(H<NUM>), that is, the holder of the private key if asymmetric key cryptography is used. The data units in the second set are validated by trusting the entity which edited the signed bitstream B and created the archive objects.

In some embodiments of the validation method <NUM>, the decision in substep <NUM> is guided by positions indicated in the archive object <NUM>. These positions are positions of the macroblocks <NUM> which are represented by the data units <NUM> to which the archived fingerprints relate. Having access to these macroblock positions allows the recipient to perform a reliable completeness check, based on an assumption along the following lines: any macroblock <NUM> in a video frame <NUM> which cannot be reconstructed from the data units <NUM> in the signed video bitstream B is encoded by another data unit whose fingerprint can necessarily be retrieved from an archive object <NUM>. If the archive object <NUM> does not indicate the positions of these macroblocks, the recipient may for example insert the missing fingerprints - those that are not computable from the data units <NUM> in the signed video bitstream B - by a trial and error approach. The trial and error approach may include executing steps <NUM> and <NUM> for each of the possible ways of inserting the archived fingerprints from the archive object <NUM> (each such way of inserting can be imagined to be a permutation of the positions of the missing macroblocks), and to conclude that the signed video bitstream B is unauthentic only if all of these executions fail.

Claim 1:
A method (<NUM>) of editing a signed video bitstream (B) obtained by prediction coding of a video sequence (V),
the signed video bitstream including data units (<NUM>) and associated signature units (<NUM>), wherein each data unit represents at most one macroblock (<NUM>) in a video frame (<NUM>) of the prediction-coded video sequence, and wherein each signature unit includes a digital signature (s(H<NUM>), s(H<NUM>)) of a bitstring (H<NUM>, H<NUM>) derived from a plurality of fingerprints (h<NUM>, h<NUM>, ...) of exactly one associated data unit each,
the method comprising:
receiving (<NUM>) a request to substitute a region of at least one video frame;
determining (<NUM>) a first set of macroblocks (<NUM>), in which said region is contained, and a second set of macroblocks (<NUM>) referring directly or indirectly to macroblocks in the first set;
adding (<NUM>) an archive object (<NUM>) to the signed video bitstream, the archive object including fingerprints of a first and a second set of data units, which respectively represent the determined first and second set of macroblocks, wherein the archive object includes positions of the first and second sets of macroblocks;
editing (<NUM>) the first set of data units in accordance with the request to substitute the region of the at least one video frame, wherein the editing of the first set of data units comprises:
decoding (<NUM>) the data unit into a reconstructed macroblock,
providing (<NUM>) an edited macroblock by performing the requested substitution on the reconstructed macroblock, and
providing (<NUM>) an edited data unit by encoding the edited macroblock; and
re-encoding (<NUM>) the second set of data units.