COMPRESSED VIDEO

Cross Reference

This patent application claims the benefit of and priority to U.S. Provisional Patent Application No. 61/189,551, filed August 20, 2008, and titled "CHANGEABLE BLOCK SELECTION". The provisional application is expressly incorporated herein by reference in its entirety for all purposes.

Field of the Invention The present invention relates to embedding watermarks in CABAC (Context- based Adaptive Binary Arithmetic Coding) video streams.

Background of the Invention

Today, the demand for digital watermarking as an antipiracy technology is strong. To make it more difficult for pirates to circumvent watermarks it is important for many potential watermarks to be proposed and used. However, it is important for watermarks to not interfere with the intended viewing experience for the intended audience. As such, a need exists for more efficient watermarking techniques. As such, a goal of this invention is to generate a list of possible changes generally associated with watermarking that are CABAC (Context-based Adaptive Binary Arithmetic Coding)/AVC (Advanced Video

Coding) compliant, and yet do not create visible artifacts, thereby ultimately providing an efficacious method for embedding watermarks in a CABAC video stream.

Summary of the Invention

A method comprises accessing potential changes that can be changeable syntax elements in a coded data stream, which can be a coded video stream; determining detectability and/or visibility of the changes to an observer, prior to applying the changes; determining recoverability of the changes for a watermarking detector, prior to applying the changes; determining embedibility of the changes for the coding means which can include compliance with standards or various rules or constraint, prior to applying the changes; and generating a list of changes meeting threshold criteria for detectability and recoverability, . The method can comprise determining a feature vector for the changeable syntax elements, wherein the feature vector is a function of the detectability, recoverability, and embedibility, a limit can be set for the feature vector, and only changes meeting the limit for the feature vector are added to the list. The method can further comprise establishing balance criterion between said detectability, recoverability, and embedibility and adding only the changes meeting the balance criterion. The method can also include accessingthe video data that is divided into blocks and characterizing at least one block by at least one of the following: luminance, before and after applying changes, mean square error between the video before and after applying changes, block pixel variance, before and after applying changes, or blockiness. The method can further include combinations in which propagation maps for the changes prior to applying the changes are made and the propagation maps are used for the selection of the changes to add to the list. The selection criterion can include size of the propagation map; maximum luminance change of all blocks in the propagation map; maximum mean square error of all blocks in the propagation map; and number of blocks in the propagation path that satisfy detectability criteria.

An additional method comprises accessing changes which can be watermarks in a list for coded data, the changes having an syntax element, an original value and an candidate alternative value; determining for a subset a group of compliant changes from the changes, the complaint changes being compliant with a coding protocol such as a CABAC encoding protocol; and selecting for the subset only compliant changes that result in the subset having only one candidate alternative value for each syntax elements and result in only compliant changes also meeting at least one performance criterion. The method can include determining fidelity, recoverability, or robustness of the watermarks and removing or preventing watermarks from being in the subset based on the fidelity, recoverability, or robustness, wherein fidelity, recoverability, and robustness are performance criteria. The method can include determining at least two performance values for the watermarks, determining some collective metric of the at least two performance values, and removing or preventing watermarks from being in the subset based on the some collective metric. Another method comprises accessing, generating, or compiling changes or watermarks in a list for coded data, the changes having an syntax element, an original value and an candidate alternative value; determining for a subset a group of compliant changes from the changes, the complaint changes being compliant with a coding protocol; and selecting for the subset only compliant changes having at least one performance criterion other than the coding protocol. The coded data can be in a transport stream and changes can be removed or prevented from being in the subset when the changes have syntax elements that cross a transport stream packet boundary. Further steps can include generating a propagation map for the changes prior to applying the changes; and removing or preventing changes from being in the subset that have any block that falls in the propagation path of a previously selected change. The method can further include determining fidelity, recoverability, or robustness of the changes and removing or preventing changes from being in the subset based on the fidelity, recoverability, or robustness, wherein fidelity, recoverability, and robustness are performance criteria.

An apparatus comprises a means for accessing or generating changes such as watermarks in a list for coded data such as video stream, the changes having a syntax element, an original value and a candidate alternative value; a means for determining for a subset a group of compliant changes from the changes, the complaint changes being compliant with a coding protocol; and a means for selecting for the subset only compliant changes that result in the subset having one or more candidate alternative value for each syntax elements and result in only compliant changes also meeting at least one performance criterion. The coding protocol can be a CABAC encoding protocol. The apparatus can further comprise a means for determining fidelity, recoverability, or robustness of the watermarks and a means for removing or preventing watermarks from being in the subset based on the fidelity, recoverability, or robustness, wherein fidelity, recoverability, and robustness are performance criteria. Additionally, the apparatus can comprise a means for determining at least two performance values for the watermarks, a means for determining some collective metric of the at least two performance values, and a means for removing or preventing watermarks from being in the subset based on the some collective metric. Brief Description of the Drawings

The invention will now be described by way of example with reference to accompanying drawings. Figure 1 illustrates an overview of the process of selecting changeable syntax elements.

Figure 2 provides an illustration of a propagation map.

Figure 3 illustrates a block diagram for the selection process for each candidate alternative value of a changeable syntax element. Figure 4 is a flowchart that illustrates an actual implementation for the final selection step.

Description of The Invention

Embodiments of the invention will now be described generally within the context of CABAC encoded H.264/AVC video streams. However, the embodiments can have broader applications.

The changes can be watermarks and these changes can be applied by embedding changing data bytes in a CABAC coded video stream. The method involves identifying changeable syntax elements in a H.264 coded video stream which can be modified into a candidate list of changes for watermark embedding. A subset of the changeable syntax elements list is used for watermark embedding. The embodiments can include implementations of steps that address at least the problem of selecting which elements of the list that will be in the subset used for watermarking.

Herein will be described a method for modifying a CABAC-encoded H.264/ A VC stream and a method for generating a list of CABAC/AVC compliant changes. Each entry in the resulting list identifies a specific syntax element, its original value, and a candidate alternative value. A syntax element that appears in this list is considered a changeable syntax element and can appear in the list more than once, each time with a different candidate alternative value. Embodiments can also include the feature of a subset of the entries in this list being selected and used for watermarking. One choice of subset is to select one and only one candidate alternative value for each changeable syntax element. Another choice of subset is to select more than one candidate alternative values for each changeable syntax element, where each selection may represent different information to embed in the watermark. However, the list can contain changes that, although CABAC and AVC compliant, will not serve the goals of the particular application.

Furthermore, the current disclosure describes at least one implementation that selects a subset of entries in the list when the application is watermarking. The selection step is performed to find the best subset in a given set of watermarking goals that include high fidelity, high robustness, and high capacity. Herein, the selection process or step is referred to as Changeable Block Selection (CBS).

Turning to watermarking algorithms, it is important to point out several of their properties. One property is the visual impact of the watermark embedding, i.e. fidelity. For many watermarking applications, the visual impact should be as small as possible. Another property is the effectiveness of the watermark after embedding. This describes likelihood that a watermark detector will be able to recover a watermark immediately after embedding. For most applications, a very high effectiveness is required. If the watermarked content is to be subject to attacks between the time of embedding and detection, many watermarking applications require that the watermark data still be recoverable after such attacks. This leads to a third property, which is robustness. Finally, a watermarking algorithm can be characterized by the amount of data that can be embedded. This property is called the capacity.

Performance of these four properties is often traded one for another depending on the application. In embodiments of the invention, the trading or balancing of features can be thought of in two steps as illustrated in Figure 1. After identifying the possible changeable syntax elements 105, the first step is the generation of a feature vector 110 for each changeable syntax element in an input list. An analysis is performed to estimate the fidelity, effectiveness, and robustness associated with each entry in the input list. The second step is to select a subset 115 of the changes for output. The subset selection is based on the desired balance between fidelity, effectiveness, robustness, and capacity, and yields 120 the selected changeable syntax elements.

Each changeable syntax element in the list includes a set of candidate alternative values. The syntax element value can be changed to any value in the set without interfering with the AVC/CAB AC compliance of the bitstream. Replacing the value of the syntax element to a candidate alternative value will change the reconstructed pixel values in the block in which the syntax element resides. Therefore, for each candidate alternative value, several block features are evaluated. Some examples of block features include: • average luminance, before embedding and after;

• mean square error between original and watermarked blocks;

• block pixel variance, before embedding and after; and

• blockiness of a block relative to its neighborhood.

The substitution of a candidate alternative value of a changeable syntax element will change the imagery data at the target block (T) where the syntax element resides. Because a whole set of inter-dependency is present in the coded video stream, blocks other than T may also be affected by the substitution. In other words, a modification introduced into block T can propagate to other blocks in the decoded sequence. In order to truly access the impact of a candidate change on the fidelity, robustness, effectiveness, and capacity, a good selection process considers the pixel value changes due to propagation as well as the direct changes to block T. The building of a propagation map that indicates all of the blocks affected by a single change to block, T, can be extremely helpful and even paramount in determining the suitability of substitutions.

An example propagation map or path 200 is illustrated in Figure 2, wherein 7 by 6 matrix 205 of blocks of video are presented. Herein, the terms propagation map and propagation path are used interchangeably. In this example, a change is made directly to block T 210. Depending on the prediction mode of the neighboring blocks, this change can propagate to the right, down, down and to the right, and/or down and to the left. In this illustration, assume that the change has propagated to the right to block A 215. The change in block A can also propagate. In this illustration assume that this change propagates to blocks B 220 and C 225. Each of these changes can further propagate to other blocks having reference sign 230. The propagation map 200 indicates all of the blocks that will be affected by the initial change to block T. These blocks are the directly changed T block 200, the first order indirectly changed block A 215, the second order indirectly changes blocks B 220 and C 225, and the further affected blocks 230. The other blocks 235 in this example are unaffected.

When a change affects blocks other than the target block, the features considered should assess the impact in all affected blocks, not just the target block. Thus, a propagation map is generated and used to show the entire impact of the change as opposed to just considering the target block. Some examples of block features include: • the size of the propagation map;

• the maximum luminance change of all blocks in the propagation path;

• the maximum mean square error of all blocks in the propagation path; and

• the number of blocks in the propagation path that satisfy both a detectability test and a fidelity test. To understand why usage of propagation maps is important, the consideration of a propagation map fidelity test in the selection steps can show which changes are acceptable if all the blocks in the propagation path pass a block-based fidelity test. In other words, a change will be unacceptable if it results in a visible artifact anywhere in its propagation path. In general, a key feature of the invention is selection of a subset of the candidate alternatives. The selection process is based on the evaluation of a set of features as described above. The general process 305 is a tool that evaluates each candidate alternative in light of the feature values and the application requirements to do the subset selection. Three application properties of the watermark are considered in the selection process. These three are detectability, fidelity, and robustness. For a change to be acceptable, it generally must satisfy application requirements in each of these properties.

Figure 3 illustrates a block diagram for the selection process 305 for each candidate alternative value of a changeable syntax element where each block acts as a filter, passing only those candidate alternatives that pass a test based on the corresponding requirements. As mentioned above, after identifying the possible changeable syntax elements, the first step is the generation of a feature vector 310 for each changeable syntax element in an input list. Note that the only candidate alternatives that are evaluated by the block labeled "Final Selection" 330 are those that have passed the tests of the Fidelity Selection 315, Detectability Selection 320, and Robustness Selection 325. These three tests can be performed in any order.

The tests of Figure 3 can be applied to each change, one at a time, or can be applied to a list of candidate alternatives. For example, a global threshold could be applied to each change individually, or the selection process can be configured to select the group of changes that has best performance. The former approach would not guarantee how many changes pass through the filters while the latter approach would not guarantee a minimum performance. The requirements of the application will indicate which of these two approaches are most appropriate. Note also that different approaches can be applied to each of the filters in Figure 3. hi the preferred embodiment, initial, fidelity, robustness, and detectability filtering are applied to each alternative individually, while the final selection acts on a list of changes that have passed the first three filters.

Fidelity selection can be based on a simple thresholding test applied to one or more of the generated features. Candidate elements that pass the threshold tests are deemed to have sufficiently high fidelity. Those that fail one or more of the thresholding tests are assumed to introduce visible artifacts too severe for the application. These candidates are removed from the list of potential changes. hi at least one embodiment, the feature vector includes the worst case, of all the blocks in the propagation path, of the sum (over all pixels in the block) of absolute luminance change that results from the change. This feature is compared to a luminance threshold. Any candidate which results in a block anywhere in its propagation path that has a sum of absolute luminance change greater than the threshold will be removed from the list.

At least one embodiment of the feature vector also includes the worst case, of all the blocks in the propagation path, of a blockiness measure indicating the amount of blockiness introduced by the change. This feature is compared to a blockiness threshold. Any candidate which results in a block anywhere in its propagation path that has a blockiness score greater than the blockiness threshold will be removed from the list.

A third possible fidelity test is based on the size of the propagation map. Here it is assumed that larger propagation maps are more likely to introduce visible artifacts. The size of the propagation map need not be listed as a feature since it is easily obtained directly from the data structure that contains the propagation map. Any candidate that has a propagation map which is larger than a threshold will be removed from the list. hi at least one embodiment, the recovery or robustness is based on the change in luminance in the block where the syntax element change is made. In other embodiments, the recovery can be based on the change in luminance in one or more blocks in the propagation path.

Thus, a simple measure of robustness is the amount of luminance change introduced by the candidate change, hi this simple model, one assumes that candidate changes that result in higher luminance changes will be more robust. hi at least one embodiment, the feature vector includes the luminance change that will result from the candidate change. This value is compared to a robustness threshold. Any candidate for which the change in luminance is below the robustness threshold will be removed from the list. When recovery is based on the entire propagation path, the size of the propagation map can be used to estimate the robustness of a change. Here it is assumed that larger propagation maps are more likely to survive processing of the marked video. Any candidate that has a propagation map which is smaller than a threshold will be removed from the list. The final selection can be based on a number of different application requirements. One example of an application requirement is that, in a transport stream, the change must fully reside within a single transport stream packet. Any candidate change that would result in the modification of a syntax element that crosses transport stream packet boundaries will be removed from the list. In at least one embodiment, the final selection process examines all of the candidate changes that have passed all of the previous tests in a slice. For a given syntax element, there may be a number of possible alternative values that satisfy the other tests, but only one can be selected for the final output. This choice may be based on the same fidelity and robustness features in the feature vector (e.g., selecting the value with the highest fidelity). This part of the selection could also be done in either of the other two selection processes.

In at least one embodiment, no change is made to any block that falls in the propagation path of a previously selected change. This rule is implemented in the final selection process, but could also be implemented elsewhere.

In at least one embodiment, no change is made if its propagation map would intersect with that of a previously selected change. This rule is implemented in the final selection process, but could also be implemented elsewhere.

The final selection is illustrated in Figure 4. Here, step 405 begins with loading data for a current slice into memory, which is followed by accessing each of the changeable macroblocks in step 410 and determining macroblock by macroblock if the current macroblock satisfies defined constraints defined by an application, a standard, a particular encoder, a visibility threshold, a bit length requirement, a payload requirement or the like in decision step 415. If not, the next macroblock in the slice is processed in step 410, and if the macroblock satisfies the defined constraints, then one proceeds to decision step 420. In step 420, if the current macroblock is in the propagation path of the previously selected output, then the next macroblock in the slice is processed in step 410, and if the current macroblock is not in the propagation path of the previously selected output, then one proceeds to decision step 430, wherein the best alternative entry for the current macroblock is selected. In step 430, one advances to next step 435 if there are not further macroblocks in the slice, and if there are more macroblocks in the slice, then the next macroblock in the slice is processed in step 410. When there are not more macroblocks to process, in step 435, the final selection is written to the data output. If there are more slices in the video frame to evaluate, then one accesses the next slice in step 405, and if there are not further slices 440, then the final selection is complete in step 445. Several of the implementations and features described in this application may be used in the context of the H.264/MPEG-4 AVC (AVC) standard. However, these implementations and features may be used in the context of another Standard, which can be existing or future, or in a context that does not involve a Standard. Thus, provided herein is one or more implementations having particular features and aspects. However, features and aspects of described implementations may also be adapted for other implementations .

The implementations described herein may be implemented in, for example, a method or process, an apparatus, a software program, a datastream, or a signal. Even if only discussed in the context of a single form of implementation such as being discussed only as a method, the implementation or features discussed may also be implemented in other forms such as an apparatus or program. An apparatus may be implemented in appropriate hardware, software, and firmware. The methods may be implemented in an apparatus such as a computer or other processing device. Additionally, the methods may be implemented by instructions being performed by a processing device or other apparatus, and such instructions may be stored on a computer readable medium such as a CD, or other computer readable storage device, or an integrated circuit. Further, a computer readable medium may store the data values produced by an implementation.

As should be evident to one of skill in the art, implementations may also produce a signal formatted to carry information that can be stored or transmitted. The information can include instructions for performing a method, or data produced by one of the described implementations. For example, a signal may be formatted to carry a watermarked stream, an unwatermarked stream, a fidelity measure, or other watermarking information.

Additionally, many implementations may be implemented in one or more of an encoder, a decoder, a post-processor processing output from a decoder, or a pre-processor providing input to an encoder. Further, other implementations are contemplated by this disclosure. For example, additional implementations may be created by combining, deleting, modifying, or supplementing various features of the disclosed implementations.