HK1197126A1 - Watermark extraction based on tentative watermarks - Google Patents

Description

Watermark extraction based on tentative watermarks

Related application

This application claims priority from united states patent applications No. 13/288,937, No. 13/288,945, No. 13/288,952, and No. 13/288,958, all filed on 3/11/2011. The entire contents of the aforementioned patent application are incorporated by reference as part of the disclosure of the present application.

Technical Field

The present application relates generally to the field of content management. More particularly, disclosed embodiments relate to the embedding and extraction of watermarks from media content.

Background

This section is intended to provide a background or context to the disclosed embodiments as recited in the claims. The description herein may include concepts that could be pursued, but are not necessarily ones that have been previously conceived or pursued. Thus, unless otherwise indicated herein, what is described in this section is not prior art to the description and claims in this application and is not admitted to be prior art by inclusion of this section.

The watermark is essentially an imperceptible signal embedded in the host content. The host content may be any of the following: audio, still images, video, or any other content that may be stored on physical media or transmitted or broadcast from one point to another. The watermark is designed to carry the auxiliary information without substantially affecting the fidelity of the host content or interfering with the normal use of the host content. For this reason, covert communications are sometimes performed using watermarks, with emphasis placed on hiding the presence of a concealed signal. In addition, other broad applications of watermarks include: preventing unauthorized use (e.g., copying, playing, and propagating) of copyrighted multimedia content, proof of ownership, authentication, tamper detection, content integrity verification, broadcast monitoring, transaction tracking, audience measurement, triggering secondary activities (e.g., interacting with software programs or hardware components), delivering ancillary information about the content (e.g., title text, full title, and artist name or instructions on how to purchase the content), and so forth. The above list of applications is not intended to be exhaustive, as many other current and future systems may benefit from co-channel transmission of primary and secondary information.

Designing a watermarking system requires achieving a proper balance between transparency (imperceptibility) of the embedded watermark, robustness of the embedded watermark (i.e., the ability of the watermark to withstand intentional and unintentional signal distortions), and the security requirements of the system (i.e., the extent to which the embedded watermark can escape detection, deletion, and/or manipulation by unauthorized parties). This balancing action must be performed while limiting the average number and/or maximum number of processing operations (i.e., processing loads) and memory usage below a particular level typically imposed for actual software and/or hardware implementations of the watermark embedder and/or watermark extractor.

Disclosure of Invention

This section is intended to provide a summary of certain exemplary embodiments and is not intended to limit the scope of embodiments disclosed in the present application.

One aspect of the disclosed embodiments relates to a method comprising: receiving a watermark frame comprising a synchronization portion and a packet portion, the watermark frame having been obtained from content in which a watermark is embedded; comparing the received synchronization portion to one or more pre-distorted synchronization templates; and evaluating the received watermark frame based on at least one result of the comparison.

In one example embodiment, the one or more pre-distorted synchronization templates are generated, at least in part, by: generating a plurality of pilot content; embedding the plurality of pilot content with a watermark comprising a synchronization portion; distorting the plurality of embedded pilot contents with one or more distortions; and obtaining candidate predistortion synchronization templates from the plurality of distorted pilot content. In one example variation, generating the one or more synchronization templates further includes receiving a subset of the plurality of embedded pilot content after transmission over a transmission medium, wherein the transmission medium introduces one or more distortions into the subset of the plurality of embedded pilot content. Further, generating the one or more synchronization templates further comprises: comparing a synchronization portion of the received subset of the plurality of pilot content to each of the candidate pre-distorted synchronization templates, and selecting one or more candidate pre-distorted synchronization templates that match the synchronization portion of the plurality of pilot content of the received subset within a predefined tolerance.

In one example embodiment, the comparing generates an error count for each of the one or more pre-distorted synchronization templates that indicates a number of mismatched symbols between the received synchronization portion of the watermark frame and each of the one or more pre-distorted synchronization templates. In another exemplary embodiment, the comparing generates a correlation value for each of the one or more pre-distorted synchronization templates that indicates how well the synchronization portion of the watermark frame matches each of the one or more pre-distorted synchronization templates.

According to a further embodiment, the above-mentioned method further comprises: after the comparing, identifying a pre-distorted synchronization template that best matches the received synchronization portion of the watermark frame, and selecting one or more distortion types and distortion amounts associated with the identified pre-distorted synchronization template to represent the distortion present in the content. In one embodiment, the above-mentioned method further comprises organizing the candidate predistortion synchronization templates in a pre-sorted order for each type of distortion and/or distortion combination. In this embodiment, the pre-sort order ranks a first candidate pre-distorted synchronization template having a higher likelihood of representing real-world content distortion higher than a second candidate pre-distorted synchronization template having a lower likelihood of representing real-world content distortion.

In yet another embodiment, the one or more pre-distorted synchronization templates correspond to a particular search granularity within the distortion space. In a variation on the above embodiment, the number of the one or more pre-distorted synchronization templates is selected to reduce one or both of: false watermark detection probability and/or computational resources required to evaluate the received watermark frame.

According to a further embodiment, the evaluation generates an indication of the presence of one of: tentative watermarks representing candidate watermarks having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection; or conclusive watermark, which represents a watermark that is detected with an associated probability of false watermark detection that is less than or equal to the desired probability of false watermark detection. In another embodiment, the evaluation identifies one or more distortion types and amounts of distortion present in the content.

In another embodiment, the content includes at least first and second watermark messages, and the first watermark message has a smaller payload than the second watermark message. In this embodiment, evaluating the received watermark frame results in detecting the first watermark message as a tentative watermark, and extracting the second watermark message using a content distortion estimate obtained for the tentative watermark.

Another aspect of the disclosed embodiments relates to a device comprising a receiver configured to receive a watermark frame comprising a synchronization portion and a packet portion, the watermark frame having been obtained from content embedded with a watermark. The apparatus also includes: a comparator configured to compare the received synchronization portion to one or more pre-distorted synchronization templates; and an evaluator configured to evaluate the received watermark frame based on at least a result of the comparator.

Another embodiment relates to a device, comprising: a watermark embedder configured to embed a plurality of pilot content with a watermark comprising a synchronization portion; a distortion processing component configured to distort the plurality of embedded pilot contents with one or more distortions; and a watermark extractor configured to generate a candidate pre-distorted synchronization template from the plurality of distorted pilot content. In one embodiment, the apparatus further comprises: a receiver configured to receive a subset of the plurality of embedded pilot contents after transmission over a transmission medium, wherein the transmission medium introduces one or more distortions into the subset of the plurality of embedded pilot contents; and a template matching component configured to compare a synchronization portion of the received subset of the plurality of pilot content to each of the candidate pre-distorted synchronization templates, and select one or more candidate pre-distorted synchronization templates that match the synchronization portion of the received subset of the plurality of pilot content within a predefined tolerance.

Another aspect of the disclosed embodiments relates to a device comprising a processor and a memory, the memory comprising processor executable code. The processor executable code, when executed by the processor, configures the device to receive a watermark frame comprising a synchronization portion and a packet portion, the watermark frame having been obtained from content embedded with a watermark; comparing the received synchronization portion to one or more pre-distorted synchronization templates; and evaluating the received watermark frame based on at least one result of the comparison.

Another aspect of the disclosed embodiments relates to a computer program product, embodied on a non-transitory computer-readable medium, comprising program code for receiving a watermark frame comprising a synchronization portion and a packet portion, the watermark frame having been obtained from content embedded with a watermark. The computer program product also includes program code for comparing the received synchronization portion to one or more pre-distorted synchronization templates and program code for evaluating the received watermark frame based on at least a result of the comparison.

Another aspect of the disclosed embodiments relates to a method that includes extracting a plurality of tentative watermarks from embedded host content, wherein each tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. The method further comprises: obtaining estimated distortion information associated with one or more distortions present in the embedded host content using at least two of the extracted tentative watermarks; and obtaining one or more pre-distorted watermark templates based on the estimated distortion information. The method further includes re-evaluating at least one of the extracted tentative watermarks using the one or more pre-distorted watermark templates.

In one embodiment, the re-evaluation results in detection of a watermark having an improved probability of false watermark detection compared to the probability of false watermark detection associated with each of the extracted tentative watermarks. In another embodiment, the re-evaluation results in detection of a conclusive watermark with an associated probability of false watermark detection that is less than or equal to the desired probability of false watermark detection. In yet another embodiment, each of the pre-distorted watermark templates represents a particular type and a particular amount of at least one type of distortion that may contaminate the embedded host content. According to a further embodiment, the re-evaluation results in an improved estimation of distortion present in the embedded host content.

In one embodiment, the method mentioned above further includes determining whether the estimated distortion information corresponds to an amount of distortion that exceeds a particular distortion threshold before obtaining one or more pre-distorted watermark templates. In this embodiment, the one or more pre-distorted watermark templates are obtained only if the estimated distortion information corresponds to an amount of distortion that does not exceed the particular distortion threshold.

In another embodiment, the estimated distortion information is obtained using two or more synchronized portions of the at least two extracted tentative watermarks. In this embodiment, the estimated distortion information is obtained by comparing a spacing between the at least two of the extracted tentative watermarks to a nominal spacing of watermarks associated with undistorted content. In yet another embodiment, the extracting of each of the tentative watermarks includes detecting a synchronization portion of the tentative watermark that triggers extraction of a packet portion of the tentative watermark.

Another aspect of the disclosed embodiments relates to a device comprising an extractor configured to extract a plurality of tentative watermarks from embedded host content, wherein each tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. This device also includes a distortion estimator configured to obtain estimated distortion information associated with one or more distortions present in the embedded host content using at least two of the extracted tentative watermarks and to obtain one or more pre-distorted watermark templates. This device further includes an evaluator configured to re-evaluate at least one of the extracted tentative watermarks using the one or more pre-distorted watermark templates.

Another aspect of the disclosed embodiments relates to a device comprising a processor and a memory, the memory including processor executable code. The processor executable code, when executed by the processor, configures the device to extract a plurality of tentative watermarks from embedded host content, wherein each tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. The processor executable code, when executed by the processor, also configures the device to obtain estimated distortion information associated with one or more distortions present in the embedded host content using at least two of the extracted tentative watermarks; and obtaining one or more pre-distorted watermark templates based on the estimated distortion information. The processor executable code, when executed by the processor, further configures the device to re-evaluate at least one of the extracted tentative watermarks using the one or more pre-distorted watermark templates.

Another aspect of the disclosed embodiments relates to a computer program product, embodied on a non-transitory computer-readable medium, comprising program code for extracting a plurality of tentative watermarks from embedded host content, wherein each tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. The computer program product also includes program code for obtaining estimated distortion information associated with one or more distortions present in the embedded host content using at least two of the extracted tentative watermarks, and program code for obtaining one or more pre-distorted watermark templates based on the estimated distortion information. The computer program product further includes program code for re-evaluating at least one of the extracted tentative watermarks using the one or more pre-distorted watermark templates.

Another aspect of the disclosed embodiments relates to a method comprising extracting a tentative watermark from embedded host content, wherein the tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. The method further comprises: obtaining estimated distortion information indicative of a coarse value of a particular distortion or combination of distortions present in the embedded host content using the extracted tentative watermark; and selecting one or more supplemental pre-distorted watermark templates corresponding to one or more distortion values in the vicinity of the coarse value. This method further includes reevaluating the extracted tentative watermark using the selected one or more supplemental pre-distorted watermark templates.

In one embodiment, obtaining the estimated distortion information comprises: selecting, at a coarse granularity, a plurality of coarse pre-distortion watermark templates corresponding to a range of distortion values for a particular distortion or combination of distortions; comparing the extracted tentative watermark to each of the plurality of coarse pre-distorted watermark templates; and obtaining the estimated distortion information by identifying a first coarse pre-distorted watermark template that best matches the extracted tentative watermark. In a variation on this embodiment, the plurality of coarse pre-distorted watermark templates are randomly selected from among a larger set of pre-distorted watermark templates. In another variation on this embodiment, the plurality of coarse pre-distorted watermark templates corresponding to one or more types of distortion that may be present in the embedded host content are selected.

According to a further embodiment, the one or more supplemental pre-distorted watermark templates are selected to enable searching of a distortion space around the coarse values with fine granularity. In yet another embodiment, the re-evaluation results in an improved estimate of distortion present in the embedded host content. In one variation, the improved estimate is utilized to extract additional watermarks from the embedded host content. In one embodiment, the re-evaluation results in detection of a watermark having an improved probability of false watermark detection compared to a probability of false watermark detection associated with the extracted tentative watermark. In another embodiment, the re-evaluation results in detection of a conclusive watermark with an associated probability of false watermark detection that is less than or equal to the desired probability of false watermark detection.

In another embodiment, the reevaluation comprises: comparing the one or more supplemental pre-distorted watermark templates to the extracted tentative watermark; generating an error count associated with each comparison, wherein the error count represents how well the corresponding supplemental pre-distorted watermark template matches the extracted tentative watermark; and selecting the supplemental pre-distorted watermark template that corresponds to the smallest generated error count. In another embodiment, the one or more supplemental pre-distorted watermark templates are selected one at a time in an iterative manner.

Another aspect of the disclosed embodiments relates to a device comprising an extractor configured to extract a tentative watermark from embedded host content, wherein the tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. This device further includes a distortion estimator configured to obtain estimated distortion information indicative of a coarse value of a particular distortion or combination of distortions present in the embedded host content using the extracted tentative watermark, and to select one or more supplemental pre-distortion watermark templates corresponding to one or more distortion values in the vicinity of the coarse value. This device additionally includes an evaluator configured to reevaluate the extracted tentative watermark using the selected one or more supplemental pre-distorted watermark templates.

According to another aspect of the disclosed embodiments, there is provided a device comprising a processor and a memory, the memory comprising processor executable code. The processor executable code, when executed by the processor, configures the device to extract a tentative watermark from embedded host content, wherein the tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. The processor executable code, when executed by the processor, also configures the device to obtain estimated distortion information indicative of a coarse value of a particular distortion or combination of distortions present in the embedded host content using the extracted tentative watermark, and select one or more supplemental pre-distortion watermark templates corresponding to one or more distortion values in the vicinity of the coarse value. The processor executable code, when executed by the processor, further configures the device to re-evaluate the extracted tentative watermark using the selected one or more supplemental pre-distorted watermark templates.

Another aspect of the disclosed embodiments relates to a computer program product, embodied on a non-transitory computer-readable medium, comprising program code for extracting a tentative watermark from embedded host content, wherein the tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. The computer program product also includes program code for obtaining estimated distortion information indicating a coarse value of a particular distortion or combination of distortions present in the embedded host content using the extracted tentative watermark, and program code for selecting one or more supplemental pre-distorted watermark templates corresponding to one or more distortion values that are near the coarse value. The computer program product further includes program code for re-evaluating the extracted tentative watermark using the selected one or more supplemental pre-distorted watermark templates.

Another aspect of the disclosed embodiments relates to a method comprising extracting a tentative watermark from embedded host content, wherein the tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. The method also includes forming one or more extrapolated watermarks by obtaining symbols of potential watermark frames positioned within the embedded host content at predefined locations relative to the extracted tentative watermark, and determining whether the extrapolated watermarks satisfy a desired false watermark detection probability when evaluated jointly with the detected tentative watermark. In one embodiment, the symbols of the potential watermark frame are located within the embedded host content at predefined temporal and/or spatial locations relative to the extracted tentative watermark.

In another embodiment, determining whether the extrapolated watermark satisfies a desired false watermark detection probability comprises: the method may include determining a number of erroneous symbols in one or more of the extrapolated watermarks, assigning weights to the one or more of the extrapolated watermarks based at least in part on the determined number of erroneous symbols, and determining whether the weighted extrapolated watermark, when combined with the detected tentative watermark, satisfies the desired false watermark detection probability. In this embodiment, the number of erroneous symbols in each extrapolated watermark may be determined by one or more of: a comparison of the extrapolated watermark symbols with the symbols of the extracted tentative watermark, an error correction code decoding of the extrapolated watermark symbols, and/or a comparison of the extrapolated watermark with one or more pre-distorted watermark templates.

In one embodiment, forming each of the extrapolated watermarks comprises: obtaining a number of erroneous symbols in one or more segments, assigning a weight to each of the one or more segments based at least in part on the number of erroneous symbols in each of the one or more segments, combining the assigned weights associated with the one or more segments to generate one or more weighted extrapolated watermark segments, and determining whether the weighted extrapolated watermark segments, when combined with the detected tentative watermark, satisfy the desired false watermark detection probability. In this embodiment, obtaining the number of erroneous symbols in each of the one or more segments includes: comparing the symbols of the potential watermark frame in each of the one or more segments to one or more pre-distorted watermark templates; and generating a count for each of the one or more segments, the count representing a number of mismatched symbols between the symbols of the potential watermark frame and the one or more pre-distorted watermark templates in the one or more segments. Further, in a variation on this embodiment, the number of segments within the extrapolated watermark is determined based on one or more of: a range of the extracted tentative watermark, an amount of distortion present in the embedded host content, and/or a type of distortion present in the embedded host content. Additionally, in a variation on this embodiment, the weight of a particular segment is assigned based at least in part on an expected weight of an unhydromarked segment that is equal in length to the particular segment. According to a further embodiment, the range of each segment is determined based at least in part on one or more of: an amount of distortion expected to be present in the embedded host content and a type of distortion expected to be present in the embedded host content. In another embodiment, the determination as to whether the weighted extrapolated watermark segments, when combined with the detected tentative watermark, satisfy the desired probability of false watermark detection is performed for the one or more segments that collectively span a smaller range than the tentative watermark.

According to a further embodiment, the desired false watermark detection probability corresponds to detection of a conclusive watermark. In yet another embodiment, the above-mentioned method further comprises reporting an estimate of the amount and type of distortion or combination of distortions present in the embedded host content.

Another aspect of the disclosed embodiments relates to a device comprising an extractor configured to extract a tentative watermark from embedded host content, wherein the tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. The apparatus also includes: a watermark extrapolator configured to form one or more extrapolated watermarks by obtaining symbols of potential watermark frames positioned within the embedded host content at predefined locations relative to the extracted tentative watermark; and an evaluator configured to determine whether the extrapolated watermark satisfies a desired false watermark detection probability when evaluated jointly with the detected tentative watermark.

Another aspect of the disclosed embodiments relates to a device comprising a processor and a memory comprising processor executable code. The processor executable code, when executed by the processor, configures the device to extract a tentative watermark from embedded host content, wherein the tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. The processor executable code, when executed by the processor, also configures the device to form one or more extrapolated watermarks by obtaining symbols of potential watermark frames positioned within the embedded host content at predefined locations relative to the extracted tentative watermark, and determine whether the extrapolated watermarks satisfy a desired false watermark detection probability when evaluated jointly with the detected tentative watermark.

Another aspect of the disclosed embodiments relates to a computer program product, embodied on a non-transitory computer-readable medium, comprising program code for extracting a tentative watermark from embedded host content, wherein the tentative watermark represents a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection. The computer program product also includes program code for forming one or more extrapolated watermarks by obtaining symbols of potential watermark frames positioned within the embedded host content at predefined locations relative to the extracted tentative watermark, and program code for determining whether the extrapolated watermarks satisfy a desired probability of false watermark detection when evaluated jointly with the detected tentative watermark.

Another aspect of the disclosed embodiments relates to a method comprising: extracting potential watermark frames from content embedded with one or more watermarks, wherein each embedded watermark comprises a plurality of symbols forming a watermark frame; dividing the watermark frame into a plurality of segments, wherein each of the plurality of segments comprises two of more watermark symbols; assigning a weight to each segment; combining the assigned weights associated with two or more segments to generate one or more weighted partial or full watermark frames; and determining whether the one or more weighted full or partial watermark frames satisfy a desired false watermark detection probability.

In one embodiment, the range of each segment is selected according to the type of error present in the content. In another embodiment, the weight of a particular segment is assigned based at least in part on an expected weight of unhydroprinted segments equal in length to the particular segment.

Another aspect of the disclosed embodiments relates to a device comprising an extractor configured to extract potential watermark frames from content embedded with one or more watermarks, wherein each embedded watermark comprises a plurality of symbols forming a watermark frame. The device also includes an evaluator configured to divide the watermark frame into a plurality of segments, wherein each of the plurality of segments includes two of more watermark symbols; assigning a weight to each segment; combining the assigned weights associated with two or more segments to generate one or more weighted partial or full watermark frames; and determining whether the one or more weighted full or partial watermark frames satisfy a desired false watermark detection probability.

Another aspect of the disclosed embodiments relates to a device comprising a processor and a memory comprising processor executable code. The processor executable code, when executed by the processor, configures the device to extract potential watermark frames from content embedded with one or more watermarks, wherein each embedded watermark comprises a plurality of symbols forming a watermark frame; dividing the watermark frame into a plurality of segments, wherein each of the plurality of segments comprises two of more watermark symbols; assigning a weight to each segment; combining the assigned weights associated with two or more segments to generate one or more weighted partial or full watermark frames; and determining whether the one or more weighted full or partial watermark frames satisfy the desired false watermark detection probability.

Another aspect of the disclosed embodiments relates to a computer program product, embodied on a non-transitory computer-readable medium, comprising: program code for extracting potential watermark frames from content embedded with one or more watermarks, wherein each embedded watermark comprises a plurality of symbols forming a watermark frame; program code for dividing the watermark frame into a plurality of segments, wherein each of the plurality of segments comprises two of more watermark symbols; program code for assigning a weight to each segment; program code for combining the assigned weights associated with two or more segments to generate one or more weighted partial or full watermark frames; and program code for determining whether the one or more weighted full or partial watermark frames satisfy a desired false watermark detection probability.

Drawings

Fig. 1 is a block diagram of a watermarking system that can accommodate the disclosed embodiments.

Fig. 2 is a block diagram of a watermark extractor device that may accommodate the disclosed embodiments.

Fig. 3A shows an example watermark frame with Synchronization (SYNCH) and PACKET portions.

Fig. 3B illustrates an exemplary PACKET assembly attempt after successful and unsuccessful assembly of the SYNCH portion of the watermark frame.

Fig. 3C illustrates a PACKET assembly operation using a pre-distorted SYNCH template, according to an exemplary embodiment.

Fig. 4 shows a predistortion SYNCH template in accordance with an exemplary embodiment.

FIG. 5 illustrates a set of operations performed in accordance with an exemplary embodiment.

FIG. 6 is a block diagram of certain components that may be used to perform some or all of the operations of FIG. 5, according to an exemplary embodiment.

Fig. 7 illustrates a set of operations that may be performed to generate a set of pre-distorted watermark templates, according to an exemplary embodiment.

FIG. 8 is a block diagram of certain components that may be used to perform some or all of the operations of FIG. 7.

Fig. 9 illustrates a set of operations that may be performed to facilitate extraction of an embedded watermark, according to an exemplary embodiment.

Fig. 10 illustrates a set of operations that may be performed to extract an embedded watermark from distorted content, according to an exemplary embodiment.

Fig. 11A shows an example watermark frame with Synchronization (SYNCH) and PACKET portions.

Fig. 11B illustrates an example PACKET assembly attempt after successful and unsuccessful assembly of the SYNCH portion of the watermark frame.

Fig. 11C illustrates a PACKET assembly operation after detecting a tentative watermark according to an exemplary embodiment.

Fig. 11D illustrates a PACKET assembly operation after detection of a tentative watermark and using watermark segmentation, according to an exemplary embodiment.

Fig. 12 illustrates an exemplary graph of false watermark detection probability versus watermark weight threshold comparing independent watermark search to sparse granularity search and fine granularity search, according to an exemplary embodiment.

Fig. 13 illustrates a set of operations 1300 that may be performed to extrapolate watermarks on a segment-by-segment basis, according to an exemplary embodiment.

Fig. 14 is a block diagram of particular components that may be used to perform some or all of the operations of fig. 13 and/or 18, according to an exemplary embodiment.

FIG. 15 shows a graph of expected weights for unhydroprinted segments, according to an example embodiment.

FIG. 16 illustrates a simplified diagram of a device within which various disclosed embodiments may be implemented.

Fig. 17 illustrates SYNCH assembly and predistortion SYNCH template operations according to an exemplary embodiment.

Fig. 18 illustrates a set of operations that may be performed to extrapolate a watermark, according to an exemplary embodiment.

Detailed Description

In the following description, for purposes of explanation and not limitation, details and descriptions are set forth in order to provide a thorough understanding of the disclosed embodiments. However, it will be apparent to one skilled in the art that the present invention may be practiced in other embodiments that depart from these details and descriptions.

Additionally, in the description of the present invention, the word "exemplary" is used to mean serving as an example, instance, or illustration. Any embodiment or design described herein as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments or designs. Rather, the word exemplary is intended to be used to present concepts in a concrete fashion.

Various watermark embedding techniques may be used to embed watermarks into host content by: for example, the least significant bits of the host signal are manipulated in the time or frequency domain, the watermark is inserted with an independent carrier signal using spread spectrum, phase, amplitude, or frequency modulation techniques, and the watermark is inserted using a host dependent carrier signal (e.g., feature modulation and informed embedding techniques). Most embedding techniques utilize psychovisual or psychoacoustic (or both) analysis of the host content to determine the optimal location and amplitude of the inserted watermark. This analysis typically identifies the extent to which the host signal can hide or mask the embedded watermark as perceived by humans.

Various storage and/or transmission channels are typically used to store and/or transmit embedded host content to another location. These channels are characterized by inherent noise and distortion, such as errors due to scratches and fingerprints contaminating the data on the optical media, noise in the wireless broadcast of audio-visual content, packet drops in the flow of multimedia content via the internet or from a media server, and so forth. Additional impairments that can affect the fidelity of the embedded watermark may result from various signal processing operations (e.g., lossy compression, scaling, rotation, analog-to-digital conversion, etc.) that are typically performed on multimedia content. In most digital watermarking applications, the embedded watermark must be able to maintain its integrity under such noise and distortion conditions.

Security of embedded watermarks is another aspect of watermarking systems. In certain applications (e.g., proof of ownership, source verification, piracy tracking, access control to copyrighted content), embedded watermarks must resist intentional manipulations directed to detecting the presence of watermarks, deciphering the data carried by those watermarks, modifying or inserting illegal values (counterfeiting), and/or removing the embedded watermarks.

Another consideration in designing watermarking systems is watermark payload capacity. This requirement depends on the particular application of the watermarking system. Typical applications range from the need to detect the presence of a watermark only (i.e. a single state watermark is required) to side information requiring tens of bits per second. In the latter case, embedded bits may be used to carry identification and timing information, such as a serial number and timestamp, metadata (metadata), such as title, artist name, purchase information, and the like.

Another factor in designing an actual watermarking system is the computational cost of the embedding and/or extraction unit. This factor becomes increasingly important for consumer electronic devices or software utilization that must be implemented with limited silicon area or computing requirements. This factor may be closely related to the intended use of the watermarking system. For example, watermarks used for forensic tracking of pirated channels (such as those that embed different codes in each copy of content distributed over the internet) require simple embedder and can tolerate complex and high-cost forensic extractors. On the other hand, copy control systems designed to prevent unauthorized access to multimedia content in consumer electronic devices, for example, can tolerate sophisticated embedder but require simple and efficient extractors.

Yet another important factor in designing a watermarking system is the false watermark detection probability. False watermarks may result when a watermark is detected from unmarked content, or may result from detecting a watermark value that is different from the originally embedded watermark value. The desired level of false watermark detection may also vary depending on the intended application of the watermarking system. For example, in copy control applications, the false detection probability must be very low (e.g., about 10)^-12) Because performing a limiting action (e.g., stopping playback of the content) due to false watermark detection of legally purchased content tends to frustrate users and has a negative impact on device manufacturers and/or content providers. On the other hand, the number of times a future song has been broadcast is tracked, for exampleA relatively high false detection rate (e.g., about 10) may be tolerated for broadcast monitoring applications that generate royalties or leaderboards^-6) Since the presence of several false detections may have little effect on the final result of the count.

Another important factor affecting the overall performance of a watermarking system is the choice of the particular technique used for watermark embedding and extraction. Making an optimal compromise between the above mentioned requirements is a very challenging task in view of the specific application at hand.

The disclosed embodiments significantly improve the embedding and extraction of watermarks while balancing various system requirements, including watermark transparency, robustness, false positive detection, security, payload capacity, and processing load. In some embodiments, watermark extraction is based on tentative watermark detection as an intermediate step towards conclusive watermark extraction.

The following transformations may be used to facilitate an understanding of concepts related to the disclosed embodiments. However, it should be understood that other numbers and representations may be used to represent watermarking systems that may accommodate embodiments of the present application. The watermark system may be composed of the tuples { O, W, K, E_K，D_K，C_TDescription, where O is a set of all original host content (i.e., one or more host content without embedded watermarks), W is a set of all watermarks, K is a set of all steganographic keys, E_KFor the embedding operation, D_KIs an extraction operation and C_TIs a comparison operation. Embedding operation E_KAnd an extraction operation D_KWhich can be expressed by equations (1) and (2), respectively.

E_K：O×W×K→O_w (1)。

D_K：O_w×K→W′ (2)。

In equations (1) and (2), O_wEmbedding content for the set and W' is embedding content O from the set_wThe extracted set of candidate watermarks. Comparison operation C represented by equation (3)_TThe extracted watermark W' is compared to the set of all watermarks W.

C_T：<W′，W>→{0，1} (3)。

It should be noted that in some embodiments, the comparison may not be performed for all watermarks, but for a subset of all watermarks. For example, such a subset may include watermarks having a particular range of values, watermarks used to embed particular types of content, and the like. Upon obtaining a successful match between W' and W, the compare operation generates a first value (e.g., "1"), and upon an unsuccessful match, the compare operation generates a second value (e.g., "0").

Fig. 1 shows a simplified block diagram of a watermarking system 100 according to an exemplary embodiment. Original host content 102, c_oAnd watermark 110W is the input to watermark embedder 104. The watermark 110 is generated by a watermark design module 108 that uses the embedded steganographic key 106, K and the original host content 102. The generated watermark 110 is embedded into the host content 102 to produce embedded host content 112, c_w. By embedding operation E_KThe generation of embedded host content 112 may be represented by equation (4) below.

c_w＝E_k(c_o，W) (4)。

The embedded host content 112 is stored and/or transmitted using one or more transmission/storage media 114. The transmission/storage medium 114 may be a unidirectional or bidirectional transmission medium. In embodiments utilizing a bi-directional transmission channel, information from the watermark extractor may flow back to the embedded components of the watermarking system 100. Such feedback may include, but is not limited to, transmission of identification, authentication and/or authorization information, indications regarding success or failure of watermark extraction operations, reports of various statistics related to extractor operations, and the like.

Referring back to fig. 1, the content transmitted through the transmission/storage medium 114 may include distortion due to the inherent transmission/storage medium 114 and/or as a result of an intentional attack on the embedded host content 112. This modified embedded host content 116, c'_wIs an input to the watermark extractor 118The watermark extractor 118 uses the extracted steganographic key 120, K and (possibly) the original host content 102 to generate one or more candidate watermarks 122, W'. By extracting operation D_KThe generation of candidate watermark 122 performed may be represented by equation (5) below.

W′＝D_K(c′_w，c_o) (5)。

Note that many watermark detectors do not require the original host content 102 to extract the embedded watermark, and thus, in those scenarios (commonly referred to as blind detection), in equation (5), the extraction operation D_KThe dependency on the original host content 102 may decrease. It should further be noted that in some embodiments, embedding the steganographic key 106 is the same as extracting the steganographic key 120. However, in other embodiments, embedding the steganographic key 106 is different than extracting the steganographic key 120.

Candidate watermark 122 is generally different from watermark 110 selected for embedding due to possible content manipulation or due to imperfect embedding procedure steps. The candidate watermark 122 and one or more possible watermarks 126, W are compared by a comparator 124_iA comparison is made. The comparator generates a watermark detector output 128 that indicates whether a match between the candidate watermark 122 and one of the possible watermarks 126 was generated. For example, the watermark detector output 128 may be generated according to equation (3). The watermark detector output 128 may further include an indication of the value, status, and/or pattern of the detected watermark. It should be noted that the comparator 124 of fig. 1 merely illustrates an exemplary mechanism for evaluating whether the candidate watermark W' does indeed represent a true watermark in the content. Other exemplary techniques for evaluating the presence and/or value of a watermark include, but are not limited to, using error detection and/or error correction codes. For example, an Error Correction Code (ECC) encoded candidate watermark W' may be decoded to determine whether error-free watermark packets may be recovered and/or to obtain the number of errors contaminating a particular watermark packet.

Considering the probability P of false watermark extraction_fProducing a watermark detector output 128. False watermark detection can occur in two different ways. First, aim atA watermark extraction system exists for a small but finite probability of falsely detecting watermarks in unwatermarked content (sometimes also referred to as false positive detection). For example, Secure Digital Music Initiative (SDMI) and DVD Audio requirements specify less than 10^-12False positive watermark detection probability of/15 second detection interval. This means that the average time between false positive watermark detections must be continuously monitored 476 decades for unwatermarked content. A second type of false detection occurs when watermarked content is examined and a watermark value is detected that is different from the original embedded watermark value. This type of false detection (often referred to as false detection) can produce undesirable results. For example, false detection can potentially result in the detection of a "no playback allowed" watermark rather than a "no copy allowed" watermark, and thus, cause playback of legally purchased content to stop. For a properly designed watermarking system, the false detection rate should be roughly the same order of magnitude as the false positive detection rate described above.

In some systems, a threshold value T is used to determine the output of the comparison operation represented by equation (3). That is, the comparator output can be expressed by the following equation (6).

In equation (6), m is the comparison result (and/or correlation value) such that the probability of false watermark detection P increases with m_fMonotonically decreases.

The comparator operation and the calculation of the false watermark detection probability depend on the chosen watermark algorithm. For example, many spread spectrum based watermarking algorithms use a correlation metric between W' and W as the comparison metric m. In particular, a correlation coefficient m between the candidate watermark W' and the pseudo-random pattern W used when embedding the watermark is estimated. Next, if the estimated correlation coefficient m is greater than a certain threshold T, successful watermark extraction is reported. In the case of unmarked content, the correlation coefficients operating between the extracted false watermark pattern and the long pseudorandom pattern generally follow a normal distribution, which means that the false watermark detection probability P can be operated on using well-known error functions_f. As the correlation coefficient m increases, the probability of false watermark detection P_fMonotonically decreases. Thus, the thresholds T and P_fWith a one-to-one mapping.

Alternatively, the candidate watermark may also be extracted as a bit string, and then the number of bit errors e may be calculated using an error detection/correction code or a direct pattern that matches the bit pattern of the potential watermark. Then, the probability of false watermark detection P can be calculated using binomial distribution_f. For example, if the watermark is N bits long and the number of bit errors is less than or equal to e, then the false detection probability may be calculated using equation (7).

False watermark detection probability P if the watermark consists of N-64 bits and the detector only finds an e-5 bit error_fLess than 10^-12. This P is_fThe conditions are typically sufficient for conclusive watermark extraction and, for example, full copyright enforcement. False watermark detection probability P obtained according to equation (7)_fMonotonically decreases as the number of matched bits m (i.e., N-e) increases.

The comparison operation described above produces only two results. In the first result, the watermark is extracted and reported, for example, to enforce copyright rules. This result is sometimes referred to as detecting a strong watermark. In the second result, no watermark is found and no other action is started. In addition to the conclusive watermark detection and the no watermark detection mentioned previously, a third result of the comparison procedure step specifying the detection of a "tentative" watermark may be established. For example, the third result may specify a extraction scenario in which the comparison results in a value (e.g., number of bits with errors e) that is greater than or equal to threshold T but less than another threshold T for strong watermark detection. The three outputs of the comparison operation can be represented by equation (8) below.

Consider again the case where the watermark consists of a bit string and the comparator output count consists of the number of bit errors. In the above example, finding up to 5 errors in a 64-bit long string may be sufficient for conclusive watermark extraction. However, if the detector finds a 20-bit error, the false watermark detection probability is less than 0.2%, which makes the presence of the watermark possible but insufficient to determine its use outside the extractor. Thus, any error count that exceeds 5 (i.e., T-6) but is less than 21 (i.e., T-21) may be used to signal tentative watermark detection. If the error count is greater than or equal to 21 errors, the false watermark detection probability is greater than 0.2%, and thus, the watermark may be ignored.

Fig. 2 shows a simplified block diagram of a watermark extractor device 200 that may accommodate the disclosed embodiments. The watermark extractor device 200 may be a stand-alone device or may be incorporated as a component of a larger content handling device, such as a content playback device, a content relay device, a content recording device, a set-top box, and so forth. Incoming modified embedded content 202 is received at receiver 204. The receiver 204 is depicted in fig. 2 as a separate component within the watermark extractor device 200. However, it should be understood that receiver 204 may be a component within a different subsystem of a larger media handling device or may be incorporated as part of another component within watermark extractor device 200. Since the modified embedded content 202 may be in various formats and may include a number of audio, video, multimedia, or data signals, it may be necessary for the receiver 204 to appropriately condition the modified embedded content 202 into an appropriate form that can be recognized by other components of the watermark extractor device 200. The conditioning may include signal processing operations such as demodulation, decompression, deinterleaving, decryption, descrambling, resampling, a/D conversion, reformatting, filtering, and so forth.

The steganographic key selection component 208 then selects at least one steganographic key from the set of steganographic keys used by the watermark extraction engine 206 to extract the embedded watermark. In some embodiments, the steganographic key is stored in the steganographic key storage component 210. The watermark extraction result 216 is generated by the watermark extraction engine 206. The watermark extraction result 216 may indicate the presence and/or value of the recovered watermark as well as an indication of the authenticity of the recovered watermark and other information. The watermark extraction results 216 may be reported at predetermined time intervals (e.g., to a particular user or device). In some embodiments, distortion estimation component 212 generates an estimate of the type and amount of one or more distortions that may be present in the received content. The estimated distortion information may be used by the watermark extraction engine 206 to facilitate detection of embedded watermarks in the presence of content distortion. The estimated distortion information may also be passed to an evaluator component 214, the evaluator component 214 facilitating detection of the embedded watermark by evaluating watermark frames processed by the watermark extraction engine 206. In some embodiments, the evaluator component 214 can perform operations such as: assigning weights to the extracted potential watermarks or watermark segments; combining the assigned weights; evaluating whether the extracted watermark or accumulated watermark segments satisfy a desired false watermark detection probability, and so on. In some embodiments, the watermark extraction result 216 may be output by the evaluator component 214 instead of the watermark extraction engine 206. The distortion estimation component 212, the evaluator component 214, and the watermark extraction engine 206 may be in communication with a storage 218 (e.g., a database) containing pre-distorted watermark templates and other information. The pre-distorted watermark template will be discussed in detail in the following sections. The storage 218 may be the same or a different physical storage unit than the steganographic key storage component 210. It should be noted that to facilitate an understanding of the underlying concepts, fig. 2 illustrates separate components within the watermark extractor device 200. However, it should be understood that in some implementations, two or more of the depicted components may be combined together. For example, in some implementations, one or more of the distortion estimation component 212, the evaluator component 214, and the storage 218 may be incorporated as part of the watermark extraction engine 206.

In some applications, if the watermark extraction result 216 indicates that at least one conclusive watermark is detected, other mandatory actions may be performed outside the watermark extractor device 200 (e.g., stop content playback, stop content recording, display an alert message, etc.). If watermark extraction result 216 indicates that at least one tentative watermark is detected, the use of the extracted tentative watermark may be limited to initiating various adjustments to the detector operation within watermark extractor device 200, for example. As mentioned earlier, tentative watermarks may be detected based on a threshold that depends on tentative watermark usage and a desired trade-off between processing load and robustness gain.

Many intentional attacks on digital watermarks or even conventional content processing operations result in watermark distortion that changes the watermark location, size, orientation, and other parameters. For example, recording a movie displayed on a screen may result in picture rotation, cropping in the temporal or spatial domain, picture stretching, angle modification, and so forth. Similarly, audio watermarks may be subject to time shifting (e.g., due to audio clipping or concatenation with other audio), time scaling, pitch shifting, judder, and judder, among others. Most of the distortions can be compensated for by detecting content distortions and inverting them before watermark extraction. Alternatively, in some embodiments, the effect of such distortion may be mitigated, in whole or in part, by adjusting watermark search program steps to correlate the extracted candidate watermarks with the pre-distorted watermark template.

Distortion detection and compensation may be manual or automatic, and it may be accomplished with or without the original content at the detector. Clearly, the most desirable approach is to provide automatic distortion detection without using the original content in order to simplify the watermark detection procedure steps. Typically, this can be achieved by introducing a synchronization (or registration) watermark.

Fig. 3A shows an example watermark frame of length L including a synchronization portion (SYNCH) and a PACKET Portion (PACKET). In the exemplary diagram of fig. 3A, for simplicity, a one-dimensional view of a watermark frame (e.g., corresponding to audio content) is depicted. However, it should be understood that similar principles may be applied to watermarks having two or more dimensions (e.g., watermarks embedded in images, video sequences, etc.). The synchronization and packet portions of the watermark frame may each comprise a plurality of symbols (i.e., binary or non-binary symbols). In some embodiments, the synchronized portion of the watermark frame may be a particular pattern or sequence embedded in the host content. As such, the synchronization portion of the watermark frame is sometimes referred to as a synchronization watermark, a synchronization pattern, a synchronization mark, a synchronization sequence, or the like. One of the functions of the synchronization portion is to help locate watermark frames within the host content. For example, the watermark extractor may search the content (e.g., process samples of the content) for a known synchronization pattern that marks the beginning of the watermark frame. Upon successful detection of the synchronization portion, the watermark extractor may then attempt to recover the watermark packet symbols following the synchronization portion. In some embodiments, the detection of the synchronization pattern signals the start of the watermark frame at a coarse granularity, which may further trigger additional processing at a fine granularity to increase the reliability of the watermark detection. In some systems, a watermark frame may contain two or more synchronization portions for establishing the location of the watermark frame and/or signaling the start, end, and/or other sections of the watermark frame, for example, at different levels of granularity.

In an exemplary fetch operation workflow, after successful assembly and detection of the SYNCH, a PACKET is assembled. However, it may be difficult or impossible to detect the SYNCH when there is a significant amount of distortion in the content. Fig. 3B shows that PACKET #1 is assembled after successful detection of the SYNCH portion marking the beginning of PACKET # 1. However, PACKETs #2 and #3 are not assembled due to distortion of the SYNCH portion that precedes each of PACKETs #2 and # 3. To further illustrate the extraction of watermarks, consider an application in which audio content is embedded with a watermark and then linearly compressed in time (e.g., shifted up with an associated tone) due to intentional or unintentional content processing operations. Depending on the particular watermark embedding technique, the SYNCH portion of the embedded watermark frame may be able to tolerate a certain amount of time scaling before its detection fails. In some scenarios where the content has been subject to linear time scaling, if the amount of time scaling can be estimated, immunity to time scaling can be improved by scaling the content in the opposite direction before attempting to extract the SYNCH pattern. In this way, the audio time scaling compression is inverted (i.e., compensated) and watermark detection becomes feasible for a larger range of compression impairments.

In another embodiment, instead of modifying the time-scaled (or otherwise compromised) content, one or more pre-distorted synchronization templates (e.g., time-compressed synchronization templates) are generated and used to detect the embedded synchronization patterns without changing the content itself. As mentioned earlier, the SYNCH pattern is used to establish the location of the watermark frame. The SYNCH template is a predefined SYNCH pattern formed to facilitate detection of a SYNCH pattern embedded in the content. According to some embodiments, the SYNCH detection procedure step includes processing the received content to obtain a candidate SYNCH pattern and then comparing the candidate SYNCH pattern to one or more SYNCH templates, which may include a plurality of pre-distorted SYNCH templates. The analysis and demonstration results indicate that generating a set of pre-distorted SYNCH templates provides watermark detection reliability as much as scaling the content, but at a lower processing cost.

To facilitate an understanding of the disclosed embodiments, it is beneficial to consider an example in which the SYNCH pattern comprises a 50-bit sequence embedded in sequential sections of audio content using a particular embedding algorithm. Assume further that each bit of the SYNCH pattern crosses 1 second of the host audio content. For audio content having 44,100 samples per second, each bit of the SYNCH pattern is embedded over 44,100 samples of the content. One method of detecting a SYNCH pattern from received content is (1) collecting 44,100 samples of received content, (2) processing the samples to extract a candidate bit value, (3) repeating steps (1) and (2)49 times to form a 50-bit candidate SYNCH pattern, and (4) comparing the candidate SYNCH pattern to one or more SYNCH templates to determine whether the candidate SYNCH pattern does correspond to a true SYNCH pattern with a particular level of confidence.

Since the location of the SYNCH pattern within the content is not known, it may be desirable to repeat steps (1) through (4) in a sliding window fashion, where in each iteration of steps (1) through (4), the processed samples of the received audio content overlap with the previous iteration. In an extreme case, steps (1) to (4)44,100 may be repeated to generate a pool of 44,100 candidate SYNCH patterns with one sample search granularity. However, in most practical applications, this extreme approach is computationally infeasible and is also unnecessary for detecting embedded SYNCH patterns with reasonable reliability. Therefore, steps (1) to (4) are typically repeated several times for each watermark bit duration. This is sometimes referred to as searching the content at X sub-bit granularity, where X represents the number of times steps (1) through (4), or at least steps (1) and (2), are repeated for each bit duration. In some embodiments, the detection procedure step may begin at a coarse sub-bit granularity (e.g., 3 sub-bits) and repeat or restart the search at a higher sub-bit granularity once the potential SYNCH pattern is detected.

In the absence of content distortion, the SYNCH detection process mentioned above may be performed by assembling candidate SYNCH pattern bit values that are spaced apart from each other by a nominal distance. FIG. 17 is a simplified diagram of a SYNCH assembly and/or template generation that may be performed in accordance with an exemplary embodiment. As mentioned earlier, the sub-bit pool represents candidate bit values generated at sub-bit granularity. The nominal template selection operation in the exemplary diagram of fig. 17 includes selecting each fifth sub-bit (or more generally, sub-bits separated by d 0). In the example above, where the SYNCH pattern is a 50-bit sequence, 50 such sub-bits are selected to form a candidate SYNCH pattern. The candidate SYNCH pattern is then compared to a nominal (or undistorted) SYNCH template to determine how well it matches (e.g., how many non-matching bits are detected).

In the presence of distortion (e.g., time scaling distortion), a candidate SYNCH pattern may be formed by selecting sub-bits at a different pitch than the nominal pitch. Referring to fig. 17, a sub-bit may be selected at a distance d1 for a first type of distortion (e.g., time expansion) and a distance d2 for a second type of distortion (e.g., time contraction). In some scenarios, candidate SYNCH patterns obtained based on different sub-bit spacings are compared to a nominal SYNCH template to evaluate how well they match.

In some embodiments, instead of matching the candidate SYNCH pattern to the nominal SYNCH template, the candidate SYNCH pattern is compared to one or more pre-distorted SYNCH templates, which may be different from the nominal SYNCH template. Such a predistortion SYNCH template may be obtained by: embedding a content (or various contents) with a SYNCH pattern, subjecting the content to various distortions, and extracting the SYNCH pattern from the distorted content at nominal and/or modified sub-bit spacing. For example, referring to fig. 17, a predistortion template #1 of length N (e.g., N-50) may be obtained by selecting N sub-bits at a d1 pitch, while a predistortion template #2 of length N may be obtained by selecting N sub-bits at a d2 pitch. Selecting a pre-distortion template based on different sub-bit spacings is most effective for scaling type distortion. For some distortions (e.g., sound propagation, intensity/amplitude modulation, camcorder capture, etc.), a pre-distortion template may be obtained by selecting sub-bits at the nominal spacing d 0.

In general, many dimensions of the distortion space may be developed using a predistortion SYNCH template. Fig. 4 shows an example in which an original (or nominal) SYNCH template 402 (i.e., a SYNCH template in the absence of content distortion) is passed through various potential distortions a-K404, 406, 408, 410 to produce a set of pre-distorted SYNCH templates a-K414, 416, 418, 420. Fig. 4 also depicts an undistorted SYNCH template 412 that may be stored with the predistortion SYNCH templates a-K414, 416, 418, 420. Pre-distortion of the template may be applied to modify the content, including linear or non-linear scaling (warping) and rotation, in one or more dimensions in the frequency/time/spatial/amplitude domain. A non-exhaustive list of distortions that may affect a watermark inserted into an image includes image rotation, stretching in the vertical or horizontal dimension, dynamic range compression of the luminance signal, color balance, and the like. A non-exhaustive list of impairments that may affect a watermark inserted into audio content includes linear time scaling, pitch-invariant time scaling, time-invariant pitch scaling, dynamic range compression, equalization, and resampling.

It should be noted that the above discussion regarding SYNCH patterns can be readily extended to include watermark packets. Furthermore, the disclosed principles may be extended to include syncs or PACKETs embedded in two or more dimensions in the spatial, time and/or frequency domains. Such syncs or PACKETs may be represented by binary or non-binary symbols, and their detection may be based on binary or non-binary symbols and/or parameters. For example, the SYNCH portion of the embedded watermark may be generally described as a predefined signal pattern that may be extracted using a correlation procedure step.

Fig. 3C illustrates a similar PACKET assembly operation for the same PACKET as shown in fig. 3B, but the operation in fig. 3C utilizes a pre-distorted SYNCH template to enable successful detection of an embedded SYNCH in the presence of content distortion. The amount of processing and the probability of false watermark detection depend on the number K of pre-distorted templates used to detect the embedded synchronization pattern. The number of pre-distortion templates, K, depends on the extent and granularity of the distortion that needs to be accommodated and the watermarking sensitivity to the particular distortion. For example, spread spectrum based watermarking techniques are generally more sensitive to time scaling distortion than replica modulation based techniques. Thus, spread spectrum based techniques require more pre-distortion templates to effectively detect watermarks in the presence of time scaling distortion when compared to replica modulation techniques.

Consider the scenario where an audio watermark is distorted using a time-invariant pitch scaling (TIPS) modification. Further assume that the pre-distorted watermark template only accounts for the following TIPS modification values: 3%, 6% and 9%. In this case, the watermark extractor may only reliably detect and report watermarks from content that has been distorted by approximately 3%, 6%, or 9% TIPS damage (plus or minus tolerance values) as tentative or conclusive. In this example scenario, when the audio watermark is distorted at any other TIPS ratio (e.g., 4.5%), there is a possibility that the conclusive watermark is not detected. Clearly, the choice of the number of pre-distortion templates depends significantly on the desired reliability of SYNCH detection. As the granularity of the predistortion template increases, the chances of detecting a reliable SYNCH (e.g., with a low bit error count or high correlation coefficient value) also increases, but the processing load also increases. It is therefore important to provide a trade-off between the number of pre-distorted synchronization templates and the probability of false watermark detection.

In some embodiments, the granularity of the pre-distorted synchronous templates (and thus, the number of pre-distorted templates) within a particular distortion range is selected such that at least a single tentative watermark is detected in the distorted content. For example, the number and spacing of the pre-distorted synchronization templates is chosen in such a way that even if the distortion is intermediate between two pre-distorted templates (as in the example above), there is a good chance of detecting a SYNCH pattern followed by a tentative watermark.

Once a tentative watermark is found, the extractor can start a more elaborate search of the distortion space. FIG. 5 illustrates a set of operations 500 performed in accordance with an example embodiment. At 502, a watermark frame is received. The received frame may include a Synchronization (SYNCH) and watermark PACKET (PACKET). At 504, the received SYNCH is compared to a plurality of pre-distorted SYNCH templates. At 506, it is determined whether the SYNCH has been successfully detected, and if so (i.e., "yes" at 506), the group operation 500 continues to assemble a PACKET at 508. On the other hand, if the determination at 506 does not indicate a successful SYNCH detection (i.e., "no" at 506), then the group operation 500 continues at 520 with the PACKET being discarded.

Referring back to fig. 5, at 508, the PACKET assembly may include various operations, such as de-interleaving, descrambling, and other PACKET formation operations. At 510, the number of errors in the assembled PACKET is determined. For example, the operations at 510 may include decoding using an error correction/detection code, template matching, and so on. At 512, it is determined whether the number of errors in the assembled PACKET is less than a first threshold associated with detection of a strong (i.e., conclusive) watermark, and if so (i.e., "yes" at 512), then a conclusive watermark is declared detected at 514. If the determination at 512 indicates an error value greater than the first threshold (i.e., "no" at 512), then the set of operations 500 continues at 516, where it is determined whether the number of errors in the assembled PACKET is less than a second threshold associated with detection of the tentative watermark. If the determination at 516 is "yes," then the set of operations 500 continues at 518, where the tentative watermark is declared detected. On the other hand, if the indication at 516 is "no," then the set operation 500 continues at 520 and the PACKET is discarded.

FIG. 6 is a simplified diagram illustrating components 600 that may be used to perform some or all of the operations described in FIG. 5. The watermark frame receiver 602 is configured to receive a watermark frame that includes the SYNCH and PACKET portions of the watermark frame. The comparator 604(a) is configured to receive the SYNCH and compare it to one or more of a pre-distorted synchronization template and an undistorted SYNCH template. The result of the comparison may be used by the distortion estimator 604(b) to obtain an estimate of one or more distortions present in the content. For example, the distortion estimator may identify a predistortion synchronization template that produces a best match with the received SYNCH, and select one or more distortion types and/or distortion amounts associated with the identified predistortion SYNCH template to represent distortion present in the content. In some embodiments, the comparator 604(a) and the distortion estimator 604(b) are combined into a single component (e.g., the comparator 604 (a)).

The templates may be stored in the storage 606 component. The PACKET assembly component 608 is configured to receive at least a PACKET and an indication of success or failure of the comparator 604(a) to obtain a match between the received SYNCH and one or more of a pre-distorted synchronization template or an undistorted SYNCH template. Upon detecting a successful SYNCH, PACKET assembly component 608 assembles a PACKET of watermark frames, which is used by PACKET error determination component 610 to generate an error count. The generated error count is used by an evaluator 612, which includes a decision logic component, to determine whether the error count is confined within or above or below a particular packet error range. For example, the evaluator 612 may determine whether a conclusive or tentative watermark is detected (and provide an output indicative thereof). The evaluator 612 may also generate an indication that a SYNCH match failed to be detected due to the comparator 604(a) and/or the distortion estimator 604(b) or that a PACKET was dropped when no tentative or conclusive watermark was detected. The output of the evaluator 612 may be used to trigger additional operations, such as triggering an extended packet search when a tentative watermark is detected. The output of evaluator 612 may include additional information such as watermark values (i.e., detected watermark status, watermark pattern, etc.), indications of levels of confidence in such watermark detection (e.g., packet error count, synchronization error count, etc.), the amount and type of one or more distortions present in the content, and so forth.

The multi-step approach described in connection with fig. 5 and 6 enables an efficient balancing of the overall processing load and associated false positive watermark detection probability in the watermark extractor, and further improves the overall robustness and security of the watermark extraction.

In some embodiments, a two-step search of the distortion space may be implemented in such a way that a match between the pre-distorted SYNCH template and the detected candidate SYNCH pattern immediately triggers an extension extractor operation, such as extending the location and granularity of the search for synchronization patterns and/or watermark packets. However, this immediate extension of the extractor operation may not yield the optimal tradeoff in terms of processing load and probability of false positive watermark detection. For example, assume that it is desirable to improve conclusive watermark extraction performance over a-20% to + 20% Pitch Invariant Time Scaling (PITS) distortion range. The search granularity must be carefully selected in order to properly populate the predistortion SYNCH template database 606. If a fine search granularity is selected (e.g., with 1% PITS spacing), a large number of predistortion templates (e.g., 40 predistortion SYNCH templates and one undistorted SYNCH template) may have to be utilized in order to reliably detect SYNCH patterns. In this scenario, the large number of pre-distorted SYNCH templates may negatively impact processing load and false watermark detection probability. Furthermore, if the pre-distortion template match has a high false SYNCH detection probability, each SYNCH detection may trigger an extended extractor operation, which will increase the processing load and false watermark detection probability. On the other hand, if a coarse search granularity is chosen (e.g., with 5% PITS spacing), there is a possibility that the embedded SYNCH and corresponding watermark PACKET are not detected. Furthermore, if the pre-distortion template matches with too low a false SYNCH detection probability, many watermarks in the distorted content may not be detected. However, this drawback can be compensated for by increasing the number of pre-distortion templates at the expense of additional processing load. Thus, a limited number of pre-distorted synchronization templates are generated and utilized in a watermark extractor in such a way that it is advantageous to improve the balance of true watermark detection, processing load and false watermark detection probability.

Fig. 7 illustrates a set of operations 700 that may be performed to generate a set of pre-distorted watermark templates, according to an exemplary embodiment. It should be noted that in describing the set of operations 700 in fig. 7, reference is made to a pre-distorted watermark template. However, it should be understood that such templates may be generated for one or both of the synchronization pattern and the known watermark packet pattern. For example, a watermark with a two-bit payload may signal the presence of only one of four different states. In such a system, a unique symbol pattern may be associated with each of the watermark states, and for each unique symbol pattern, the set of operations 700 described in connection with fig. 7 may be performed.

Referring to fig. 7, at 702, one or more pilot signals are generated. These signals may correspond to particular functions, such as pulses, sinusoidal functions, square waves, plane images, edge images, and so forth. It should be noted that the term "signal" is used to convey a particular type of content that may be transmitted, received, and stored in digital or analog form. Such signals may be subject to signal processing operations such as modulation/demodulation, a/D and D/a conversion, compression, resampling, and the like. The pilot signal generated (or otherwise obtained) at 702, once embedded with the synchronization pattern and/or watermark packet and distorted (or transmitted over a noisy channel) may provide insight as to the characteristics of the distorted and transmitted channel and how such distortion and/or transmission affects the embedded watermark. In an alternative embodiment, instead of pilot signals, typical content (e.g., a concatenation of different types of movies) is generated or obtained in addition or alternatively at 702.

At 704, the pilot signal is embedded with a watermark. At 704, the embedded pilot signal undergoes one or more distortions. These distortions may include, but are not limited to, various time scaling distortions, a/D and D/a distortions, clipping, rotation, scaling, spatial and/or temporal shifts, and so forth. At 706, the distortion may be applied to the host pilot signal using one or more distortion parameters that may span a particular range. For example, LTS distortion may be applied according to a Linear Time Scaling (LTS) percentage parameter ranging between-10% to + 10% in 1% increments. At 708, a watermark is extracted from the distorted pilot signal. At 710, for each successful watermark extraction, a pre-distortion candidate watermark template is generated that corresponds to a particular distortion with particular distortion parameters. At 712, a set of distorted watermarks is received from the field. In one example, the set of distorted watermarks at 712 is generated by extracting a watermark from the host pilot signal after watermark embedding at 704 after the host pilot signal has undergone real-world transmission through a noisy channel. For example, a host pilot signal containing an embedded watermark may be played back at a movie theater, captured using a camcorder, and input to a watermark extractor to obtain a distorted watermark.

At 714, the received distorted watermark is compared to the candidate pre-distorted watermark templates. This comparison may reveal which of the candidate pre-distorted watermark templates is the best match or correlation. At 716, the relevant pre-distorted watermark templates are sorted (e.g., in order of relevance or best match) and stored in a database. In some embodiments, the database may include the pre-distorted watermark templates that generate a subset of tentative watermarks or strong watermarks. Note that the pre-distorted template database may be updated and/or supplemented with new templates when new distorted watermarks from fields are obtained.

As described in the exemplary diagram of fig. 7, the procedure steps of the experimental selection of the pre-distorted watermark template may be repeated for each distortion within a particular range and for combinations of distortions. In some embodiments, to limit the number of distortions performed on the pilot signal to within practical limits, critical distortion vectors are first identified (e.g., distortions due to time/space/frequency scaling attacks within a particular range, camcorder capture, low bitrate perceptual compression, etc.). Next, a pre-distorted watermark template of the critical distortion vector and a combination thereof are determined. All other distortion vectors (e.g., non-critical distortion vectors) may be tested against the predistortion template for critical distortion vectors to determine if additional predistortion watermark templates are needed.

Fig. 8 is a simplified diagram of components that may be used to perform some or all of the operations 700 of fig. 7. The embedding device 802 is used to embed pilot signals that are subsequently subjected to various distortions using a distortion processing component 804. The distortion-embedded pilot signal produced by the distortion processing component 804 is input to an extractor component 806, where a pre-distorted watermark template is produced that corresponds to a particular distortion with particular distortion parameters. In fig. 8, these watermark templates are denoted as "WM template 1", "WM template 2", and the like. Fig. 8 also depicts modified embedded pilot content obtained from the fields input to the extractor component 808. In some embodiments, extractor component 806 and extractor component 808 are the same physical device. In other embodiments (e.g., embodiments in which decentralized processing is used), the extractor component 806 and the extractor component 808 may be different physical entities that may be located at different physical locations.

Fig. 8 further illustrates a template matching and classification component 810 that compares and matches the distorted watermark from the field to the pre-distorted candidate watermark template generated by extractor component 806. The results of the various distorted matching and classification operations are stored in database 812.

In some embodiments, to reduce processing load and false watermark detection probability, the extractor may skip one or more of the pre-distorted watermark templates at any candidate watermark location. In the following sections, this method is sometimes referred to as sparse search within the distortion space. One disadvantage of skipping a subset of pre-distorted watermarks is that the extractor may lose the opportunity for watermark extraction. However, if the number of occasions is sufficiently large, the overall impact of missed occasions may be negligible. Furthermore, in some embodiments, if the extractor finds a tentative watermark at another stage of the watermark extraction procedure step (e.g., at a different extraction occasion), the extractor may be configured to develop some of the missed occasions, for example, based on tentative watermark extrapolation discussed below. In one variation, only missed occasions with a high probability of successful watermark detection are accessed, not all missed occasions. This is achieved by revisiting those occasions that only match the distortion parameters associated with the detected tentative watermark(s).

In designing a sparse search within the distortion space, the disclosed embodiments may utilize the following two features. First, a subset of the pre-distorted watermark templates is randomly (or pseudo-randomly) selected. If this decision is deterministic, the attacker can find the deterministic pattern experimentally or through reverse engineering, and then adjust the distortion pattern to match the skipped search space to escape watermark detection.

Secondly, it is advantageous if the extractor knows the possibility of a certain distortion being present. For example, if a watermark conveys a "theater show" status in audiovisual content, a typical piracy scenario involves recording the content. For this attack scenario, an appropriate type of pre-distortion template (e.g., a template corresponding to clipping, stretching, rotation, etc.) is selected with a higher probability than other pre-distortion templates (e.g., time/frequency scaling, etc.). Similarly, if the watermark conveys a "trusted source" status indicating that the content is in a digitally encrypted format, then the perceptual transcoding becomes a possible attack and the pre-distortion template associated with the perceptual compression is selected with a high probability. In general, the probability of a pre-distortion template selection is proportional to the probability of a particular distortion present in the content, so long as this probability can be estimated.

In some embodiments, the distortion operation is performed based on two or more distinct watermarks. The two or more distinct watermarks may include a SYNCH pattern alone, a tentative watermark alone, or a combination of SYNCH and tentative watermarks. When those watermarks have a predefined correlation at the embedder and the relationship is known to the extractor, any deviation from this relationship can be used to calculate the nature and amount of distortion. For example, if two synchronization patterns in an image are embedded along a horizontal line and they are detected such that the line connecting them is at an angle to the horizontal line, it may be assumed that the image is rotated by the detected angle. Similarly, if the audio watermark is embedded periodically with a period P and the extractor finds audio watermarks spaced apart with P ', it may be assumed that the content is time scaled by a factor P'/P.

Distortion operations based on individual SYNCH patterns may have particular advantages, such as reduced processing load. However, using a tentative watermark rather than a SYNCH pattern may provide superior performance because tentative watermarks typically have a lower probability of false detection and better position resolution. As mentioned earlier, the detection of the SYNCH pattern is typically characterized by a higher probability of false detection when compared to the detection of the watermark packet. This is done to balance the processing load of the extraction procedure steps with the robustness requirements. Thus, a distortion operation based on the separately embedded SYNCH pattern may produce an incorrect or unreliable distortion estimate. However, if a tentative watermark is detected, it provides additional confidence in the presence and location of the detected watermark.

Once the amount of distortion is calculated based on two or more watermarks, the next step is to evaluate whether the distortion is realistic. For example, it is safe to assume that image rotation during video recording will be no greater than 20 degrees (relative to a vertical or horizontal baseline) or that temporal compression of the audio track will be no greater than 50%. Any amount of distortion greater than those predefined limits may render the image or audio imperceptible, and thus, distortion calculations that produce values beyond those limits may be attributed to false watermark detection.

When a realistic amount of distortion is detected, additional pre-distorted watermark templates corresponding to distortion in the computationally distorted neighborhood may then be selected and/or generated and used for other watermark searches. The pre-distorted watermark template may correspond to a SYNCH portion of a watermark frame, a PACKET portion of a watermark frame, a combined SYNCH and PACKET portion of a watermark frame, or a SYNCH or small portion of a PACKET portion of a watermark frame. Additional pre-distorted watermark templates may be repeatedly correlated with the extracted watermark in order to increase the reliability of watermark detection and the reliability of distortion operations. For example, watermark extraction with a new watermark template may produce a watermark with fewer errors or higher correlation values (and thus higher reliability) than previously detected tentative watermarks. The amount of estimated distortion may then be re-computed using the watermark detected to have higher reliability. In some real-time applications (e.g., when watermark extraction occurs during real-time playback of content), repeated searches of the same segment of content may be difficult to perform. Thus, in some embodiments, the additional pre-distorted watermark template is only used for subsequent content segments.

Fig. 9 illustrates a set of operations 900 that may be performed to facilitate a search for distortion, according to an example embodiment. At 902, a tentative watermark is extracted. At 904, an amount of distortion is estimated based on the detection of the two or more tentative watermarks. For example, as mentioned earlier, the spacing between two detected watermarks may be used to estimate the amount of linear time scaling in the audio content. At 906, it is determined whether the estimated amount of distortion is below a particular threshold. Operations at 906 provide a mechanism to determine whether the estimated distortion is realistic. If the estimated distortion is above the threshold, then the distortion estimate is discarded at 912. At this point, the set of operations 900 returns to 902 to wait until another set of viable tentative watermarks becomes available for the distortion estimation at repeat 904, or to generate another distortion estimate using another set of tentative watermarks that are already available.

If the distortion estimate is below the threshold (i.e., "yes" at 906), then an additional pre-distorted watermark template is selected and/or generated at 908. The "generation" of the pre-distorted watermark template at 908 may be accomplished using an algorithm and associated parameters that allow for the generation of a new pre-distorted watermark template. Alternatively or additionally, an appropriate pre-distorted watermark template may be selected from a database. At 910, an additional pre-distorted watermark template is used to detect a watermark with higher reliability and/or to improve the estimation of content distortion.

In distorted content, the tentative watermark carries uncertainty about its exact location and parameters. Therefore, the distortion operation is also approximate. As mentioned in connection with fig. 9, an additional pre-distorted watermark template may be selected at 908 to improve watermark detection and/or distortion estimation. In some embodiments, additional pre-distorted watermark templates are selected in a manner to enable more efficient and reliable watermark detection and/or distortion estimation. In particular, when generating a pre-distorted watermark template, a plurality of watermarked content is distorted in a predefined manner, a tentative watermark is detected, distortion is estimated based on the detected tentative watermark, and statistics of errors associated with the computed distortion are collected. When an additional pre-distorted watermark template is selected/generated at the watermark extractor (e.g., operation 908 in fig. 9), such additional pre-distorted watermark template is selected/generated based not only on the estimated distortion (e.g., obtained from operation 904) but also on the distortion that is within the expected error. Thus, for each estimated amount of distortion, a plurality of pre-distorted watermark templates may be selected, all of which are in the vicinity of the estimated distortion. In this way, the chance of extracting a watermark with high reliability is significantly improved without significantly increasing the number of template matching attempts.

In some embodiments, the estimation of the distortion is performed using a single tentative watermark. As mentioned earlier, to reduce the processing load of the extractor and the false watermark detection probability, only a subset of the pre-distorted watermark templates may be used for the initial search for embedded watermarks. This subset of templates enables a coarse search of the distortion space. When a single tentative watermark is detected using coarse graining of the distortion space, there is a good chance that a more reliable watermark can be found if the distortion space is searched at a finer granularity around the distortion parameters that trigger detection of the tentative watermark.

Fig. 10 illustrates a set of operations 1000 that may be performed to extract an embedded watermark from distorted content, according to an exemplary embodiment. At 1002, a watermark frame is received, and at 1004, a multi-step search for a tentative watermark is conducted. In one example, the operations at 1002 and 1004 are performed using the set of operations described in conjunction with FIG. 5. At 1006, it is determined whether a tentative watermark is detected. If a tentative watermark is not detected, the operations 1000 continue at 1018 where the system waits for the next tentative watermark. If the determination at 1006 indicates that a tentative watermark is detected, then the operations 1000 continue at 1008 where distortion information is estimated. For example, the estimation of the distortion information may include determining an amount of a particular distortion (or combination of distortions) present in the received content. In one embodiment, this estimation may be performed by: assembling one or more SYNCH portions of the watermark frame (or otherwise obtaining an assembled SYNCH portion); and compare it to one or more pre-distortion SYNCH templates corresponding to various amounts of a particular distortion (or combination of distortions). As mentioned earlier, in some embodiments, the estimation of the amount of distortion and/or the detection of the tentative watermark is performed from a coarse search of the distortion space. Watermark detection generated from this coarse search provides estimated distortion information indicative of a coarse value of a particular distortion or combination of distortions present in the embedded host content.

At 1010, an additional (or supplemental) pre-distorted watermark template is selected and/or generated for a finer search of the distortion space. The further selected/generated template corresponds to the distortion values in the neighborhood of the (coarse) distortion value obtained at 1008. Consider a TIPS modification example of audio content where an initial set of pre-distorted watermark templates allows for a coarse or sparse search of the time scale space at 3%, 6% and 9% values. If the audio content is distorted by 3.5% during a coarse search of the distortion space in this example, a pre-distorted watermark template associated with a 3% TIPS can be used to obtain the best SYNCH compilation followed by a successful tentative watermark packet compilation. For this example, selecting an additional distorted watermark template (i.e., operation at 1010) may include selecting or generating a pre-distorted watermark template in the neighborhood of 3% TIPS distortion (e.g., 2.5% to 3.5% stepped by 0.1%).

At 1012, the number of packet errors associated with the tentative watermark is reevaluated using the newly selected/generated pre-distorted watermark template. In one embodiment, the candidate recovered PACKET is compared to some or all of the additional pre-distorted watermark templates to generate an associated error count. As such, the new set of pre-distorted PACKET templates may be used for repeated searches of the same segment of content in which the tentative watermark was detected or for searches in subsequent segments of content.

At 1014, the pack or pack template that yields the smallest number of errors is selected. The selected packet/packet template corresponds to an amount of distortion that more accurately represents the amount of true distortion present in the received content. Thus, in some scenarios, the re-evaluated packet error may indicate the presence (and more accurate location) of an embedded watermark with higher reliability. For example, the operation at 1014 may result in the detection of a strong or conclusive watermark. At 1016, distortion information for assembling future packets and/or synchronization patterns is updated based on the packet/template that produced the best error value at 1014.

It should be noted that while the operations at 1014 are described as selecting the package/template that produces the least number of errors, the operations at 1012 and 1014 should also produce selections corresponding to a low probability of false positive detection. In an alternative embodiment, an iterative process is used to achieve extraction of the watermark and estimation of the distortion. In this embodiment, the supplemental pre-distorted watermark templates in the neighborhood of the previously estimated distortion are selected/generated one at a time. For example, the first supplemental pre-distorted watermark template may correspond to slightly less content distortion than the pre-distorted watermark template used for tentative watermark detection at 1004. If the first supplemental pre-distorted watermark template yields fewer bit errors or a higher correlation with the candidate watermark, then the second supplemental pre-distorted watermark template is selected to correspond to a content distortion that is smaller than the first supplemental pre-distorted watermark template. On the other hand, if the first supplemental pre-distorted watermark template results in a larger number of bit errors or a reduced correlation value, then the second supplemental pre-distorted watermark template is selected to correspond to a content distortion that is greater than the distortion associated with the pre-distorted watermark template for tentative watermark detection at 1004. The iterations may continue until one of the pre-distorted watermark templates provides the best watermark detection and the best estimate of the content distortion. In some examples, numerical methods (e.g., dichotomy or newton's method) may be used to facilitate convergence of the iterations. The iterative process described above obtains the most reliable estimate of the detected watermark more efficiently and with a lower probability of false detection than multiple searches at fine granularity.

In some embodiments, upon detection of a tentative watermark, extrapolation techniques are used to improve the reliability of watermark detection. In distorted content, individual watermarks may be damaged to the extent that conclusive watermark detection is possible despite the efforts of distortion operations and compensation described above. In these cases, the extractor may continue the search for subsequent watermarks in the content in the vicinity of the detected tentative watermark. However, if one or more additional tentative watermarks are found in subsequent searches, a joint "weight" of two or more watermarks may be operated on and used to further re-evaluate the watermark presence.

In some embodiments, alternative methods of predicting the location, symbol pattern and watermark parameters of neighboring watermarks depending on the watermark embedding pattern may be employed. In general, repeated embedding of the same watermark throughout the content is contemplated, but more complex embedding patterns are also possible and, in some cases, advantageous. For example, in some scenarios, neighboring watermarks may differ from one another in a known manner (e.g., when the embedded watermark includes a counter that is incremented with the embedding of each additional watermark packet, or when payloads of neighboring watermark packets are scrambled with different scrambling keys). In scenarios where the embedding pattern of subsequent and/or previous watermarks is known, the detection of tentative watermarks may be extrapolated to evaluate the presence and value of other embedded watermarks in a predetermined location within the content. In some embodiments, the detected tentative watermark is used to predict the presence of other watermark patterns within the content. This prediction is then tested (e.g., using hypothesis testing statistical methods), which may result in rejection or confirmation of the feasibility of watermark detection.

Fig. 11A shows an example sequence of watermark frames with SYNCH and PACKET portions similar to those presented in fig. 3A. After successful assembly and detection of the SYNCH, a PACKET is assembled. When a significant amount of distortion is applied to the content, it may be difficult or impossible to detect the SYNCH portion of the watermark frame. Fig. 11B shows that PACKET #1 is assembled after the previous SYNCH is successfully assembled. However, PACKET #2 and #3 were not assembled due to severe distortion of the corresponding SYNCH portions of watermark frames #2 and # 3. Fig. 11C shows an example in which, after the tentative watermark is detected, extrapolation of the tentative watermark is performed across watermark frames #2 and #3 (expected to include PACKET #2 and # 3). In a typical extrapolation scenario, some of the symbols of the extrapolated watermark are expected to match associated symbols in the unextended (i.e., tentative) watermark. Upon assembling the symbols of the extrapolated watermark, symbol errors are counted, false watermark detection probabilities are estimated, and weights are assigned to the extrapolated watermark. The assigned weights may be accumulated to jointly evaluate the presence and value of the watermark.

The extrapolation techniques of the disclosed embodiments include features that can improve the likelihood of detecting an embedded watermark while maintaining the probability of false watermark detection within desirable limits. In particular, in some embodiments, when extrapolating to search for additional watermarks, there is no need to find additional SYNCH patterns in order to assemble the next watermark packet symbols. In distorted content, many SYNCH patterns may be corrupted and unrecognizable. However, the extrapolation technique of the present application enables the assembly and use of packet symbols even though the SYNCH portion of the watermark frame is not detected for all potential watermark frames.

Furthermore, in some of the extrapolation techniques of the disclosed embodiments, the number of extraction attempts to detect the extrapolated watermark may be as low as 1. Thus, the weights assigned to the extrapolated watermark symbols need not be adjusted to maintain the desired false detection probability. However, in a particular embodiment, to account for the uncertainty associated with the distortion estimate and the true position of the tentative watermark, a watermark extrapolation attempt may be performed using several start offsets and several distortion estimates. This approach facilitates achieving the best tradeoff between robustness and false detection probability. Even in this scenario, the number of attempts is still significantly lower than in systems where independent detection based on embedded watermarks triggers weight accumulation. In this independent detection of embedded watermarks, the detection of each watermark (e.g., each tentative watermark) requires the detection of an associated SYNCH portion, as illustrated in fig. 3B and 11B.

Fig. 12 shows an exemplary graph of false watermark detection probability versus watermark weight threshold. The exemplary graph in fig. 12 corresponds to experimental results obtained for a watermark frame having a binary symbol with a 32-bit SYNCH portion and a 64-bit PACKET portion embedded in the audio content. Curve 1220 corresponds to a sparse granularity search of the distortion space and curve 1240 corresponds to a fine granularity search obtained using the watermark extrapolation technique of the disclosed embodiments. Fig. 12 also shows a third curve 1260 of false watermark detection probabilities corresponding to extractors that operate independent recovery based on watermarks to achieve weight accumulation. Note that for about 5 x 10^-9The watermark weight threshold using the disclosed tentative watermark extrapolation techniques (both sparse and fine searches) is less than the threshold used in the independent weight accumulation technique. As such, the disclosed extrapolation technique based on extrapolation of previously detected tentative watermarks yields similar or better false positive performance at lower computational processing loads than a weight accumulation technique based on independent detection of embedded watermarks. Also, detection based on extrapolation of previously detected tentative watermarks requires a lower watermark detection threshold for detection of the tentative watermark, as opposed to detection of a conclusive watermark. These features greatly improve the robustness performance of the watermark extractor.

Fig. 18 illustrates a set of operations 1800 that may be performed to extrapolate watermarks, according to an exemplary embodiment. At 1802, a tentative watermark is extracted. For example, the operations at 1802 may include at least some of the operations discussed in connection with fig. 5, 9, and 10. At 1804, one or more extrapolated watermarks are formed. Such packet formation may be accomplished, for example, by obtaining symbols of potential watermark frames positioned at predefined locations within the embedded host content relative to the extracted tentative watermark. At 1806, the extrapolated watermark is co-evaluated with the extracted tentative watermark. At 1808, it is determined whether the joint evaluation of the watermarks results in meeting the desired false watermark detection probability. For example, such a desired false watermark detection probability may correspond to a detection probability associated with a conclusive watermark.

The amount of watermark extrapolation performed in accordance with the disclosed embodiments depends on the nature of the distortion and the accuracy of the distortion estimate. For example, in the case of audio watermarks that are distorted due to acoustic propagation of host content, time scaling distortion is typically negligible when background noise and reverberation appear to be the primary sources of distortion. In this environment, a successful extrapolation across several watermark lengths is possible, assuming that the watermark is embedded periodically. On the other hand, if the content is subject to time scaling attacks, the accuracy associated with estimating time scaling distortion may be limited, and thus, only a small number of watermark extrapolations in each temporal direction may be feasible.

In some cases, the distortion varies in time or space due to content changes or intentional attacks. For example, audio tape players are known to produce judder or judder artifacts due to variations in the speed of the motor of the tape player. Thus, the resulting time scaling factor varies over time based on changes in motor speed. An attacker may employ similar techniques in order to disturb a proper estimation and compensation of time scaling distortion in the watermarked content. However, a distortion that warns of too fast and/or too large a temporal variation often produces objectionable perceptual artifacts and reduces the feasibility of the attack. Thus, it may be beneficial to develop more effective countermeasures against misses that increase the robustness of watermark extraction in the presence of time varying distortions that vary slowly over the watermark duration.

Experiments conducted by the inventors indicate that when distortion varies slowly over the length of the watermark, tentative watermark detection is typically achieved with a pre-distorted SYNCH template that is approximately appropriate somewhere within the distortion variation range. However, over the duration of the watermark PACKET, which is typically larger than the SYNCH portion, the distortion may fluctuate to values outside the detection range of the pre-distorted watermark template. This means that the pre-distorted packet template can only match the actual distortion of a limited section of the watermark frame, thereby resulting in a significant symbol error rate.

According to some embodiments, in cases where the embedded watermark symbol pattern is known in advance (e.g. by a previously detected tentative watermark payload, by considering only a limited set of payloads, etc.), the entire watermark interval is divided into segments and a watermark extraction attempt is made for each segment. This operation may be better understood with reference to FIG. 11D. Note that the horizontal scales in fig. 11D may be different from those in fig. 11A to 11C. Starting with a distortion estimate obtained from SYNCH detection and/or tentative watermark detection of PACKET #1, extraction of the first watermark segment SEG1 is attempted using one or more of the pre-distorted watermark templates corresponding to the estimated distortion value. In some embodiments, SEG1 contains all or a portion of SYNCH expected to follow PACKET # 1. For example, if the watermark frame consists of a 20-bit SYNCH and a 100-bit PACKET, in one example, each segment may include 20 bits (i.e., 6 segments/frame). In another example, each segment may include 30 bits (i.e., 4 segments/frame). In yet another example, each segment may include 10 bits (i.e., 12 segments/frame). In yet another example, the SYNCH portion may be skipped and only segment matching of the PACKET portion of the watermark frame may be performed. The above examples are not intended to provide an exhaustive list of different segment sizes and segment configurations, but are provided to illustrate that different segment sizes and configurations may be selected based on the needs and capabilities of the watermark detection system and the target application.

In some embodiments, the number of segments is selected based on the range (e.g., duration, spatial range, etc.) of the extracted tentative watermark. For example, a watermark with a smaller payload may be segmented into fewer segments than a watermark with a larger payload. Other factors that determine the number of segments are the amount of distortion present (or expected to be present) in the embedded host content and/or the type of distortion present (or expected to be present) in the embedded host content. The selection of the number of segments may be dynamically changed based on, for example, the amount and type of distortion, or may be made statically or semi-statically, with the number of segments being fixed. Further, the length of each segment may be selected based on the amount and/or type of distortion expected in the content.

Referring back to fig. 11D, in some embodiments, the predistortion watermark template closest to the estimated distortion value is used for SEG1 and extrapolated detection of one or more predistortion watermark templates corresponding to distortions in the vicinity of the estimated distortion value. Whichever matching attempt produces the best result, its associated distortion level is used as the starting distortion estimate for the next segment SEG 2. The above mentioned operations continue for the other segments SEG2, …, SEG K of the extrapolated watermark. In this way, slowly varying distortions can be efficiently tracked and mitigated by utilizing an appropriate pre-distorted watermark template.

Fig. 13 illustrates a set of operations 1300 that may be performed to extrapolate watermarks on a segment-by-segment basis, according to an exemplary embodiment. At 1302, a watermark frame is received, and at 1304, a multi-step search for a tentative watermark is conducted. In one example, the operations at 1302 and 1304 are performed using the set of operations described in conjunction with FIG. 5. At 1306, it is determined whether a tentative watermark is detected. If no tentative watermark is detected, the set of operations 1300 continues at 1320, where the system waits for the next frame and then repeats the operations performed at 1302-1306. If the determination at 1306 indicates that a tentative watermark is detected (i.e., "yes" at 1306), then the set of operations 1300 continues at 1308, where distortion information is estimated. For example, the estimation of the distortion information may include determining an amount and type of distortion (or combination of distortions) present in the received content. In one embodiment, this estimation may be performed by: assembling the SYNCH portion of the watermark frame (or obtaining the assembled SYNCH portion); and compare it to one or more pre-distortion SYNCH templates corresponding to various amounts of a particular distortion(s). As mentioned earlier, the estimation of the amount of distortion and/or the detection of tentative watermarks is typically performed on the basis of a coarse search of the distortion space.

At 1310, the granularity of the search is determined. The granularity of the search (e.g., the number of pre-distortion packets and their spacing in the distortion space) may be initially selected based on a particular default value, may be adjusted for initial segment evaluation based on estimated distortion information, and/or may be based on error minimization criteria on a segment-by-segment basis. The criteria may be selected based on desired false watermark detection probability, robustness, and computational complexity. In some embodiments, the criterion is adapted in response to observed or expected distortion. Based on the error minimization criteria, the pre-distorted watermark templates at the segmentation level (which may reside locally at the watermark extractor or remotely at the database) are rearranged and reclassified to comply with the error minimization criteria. Furthermore, the selection rules for selecting the pre-distorted watermark template may be updated to enable the watermark extrapolator to select a set of optimal pre-distorted watermark segment templates. In some embodiments, the error minimization criteria further triggers the selection of a new steganographic key that can be used to extract subsequent watermarks. Steganographic key selection may be done in a manner to optimize at least one of robustness, security, and computational efficiency of extraction of watermarks embedded in host content. In addition, the selection of one or more steganographic keys may be adapted to anticipate transformation of the host content. For example, the transformation may alter the appearance of at least one watermark embedded with a first embedded steganographic key such that the at least one embedded watermark appears to be embedded with a second embedded steganographic key.

Referring back to fig. 13, at 1312, watermark extrapolation for the segment under consideration is performed. In some embodiments, the operations at 1312 include comparing the symbols of the segment under consideration with one or more pre-distorted watermark templates at the segment level. For example, this comparison may be performed using a bitwise exclusive or (XOR) operation between the segment bits and the bits of the pre-distorted watermark template. Based on the granularity of the search and the estimated distortion information, one or more extrapolation attempts may be made, for example, to generate one or more error values. The operations at 1312 further include selecting the best match result (e.g., the result that yields the least number of errors). At 1314, it is optionally determined whether all segments have been processed. This determination may be made by comparing the number of segments that have been processed so far to the number of segments expected to include watermark packets based on factors including the length of the detected tentative watermark packet, the amount and type of distortion present, and so on. In some embodiments, not all segments need to be processed. As such, subsequent operations (i.e., operations at 1316 and 1318) may be performed upon extrapolation of one or more segments that collectively span a smaller range (e.g., duration, spatial range, etc.) than the tentative watermark. In these embodiments, the operations at 1314 may include a determination as to whether a predetermined number of segments in the range of 1 to k have been processed. In some embodiments, k is the number of segments expected to include one watermark packet. In other embodiments, k is the number of segments expected to include more than one watermark packet. In embodiments where the processed segments collectively span a smaller range than the tentative watermark, if the operation at 1318 fails to produce the desired result, the additional extrapolated segments may be processed and evaluated.

Referring back to FIG. 13 and assuming the operations at 1314 are performed, if the determination at 1314 indicates that additional segments must be processed (i.e., "No" at 1314), then the set of operations 1300 returns to 1308 and a new estimate of distortion information is obtained based on the results of the extrapolation of the previous segment. For example, at 1308, an estimate of the distortion space may be refined (e.g., based on the pre-distorted watermark template that produced the best match result at 1312).

If the determination at 1314 indicates that all segments have been processed ("yes" at 1314), then the set of operations 1300 continues at 1316, where each segment is assigned a weight. In one example, the weights are assigned according to equations (9) and (10) provided in the following sections. At 1318, the presence and value of the watermark is evaluated based on a joint evaluation of the one or more segments. For example, the weights assigned at 1316 may be added together and compared to a weight threshold representing detection of a watermark having a particular level of reliability. It should be noted that the set of operations 1300 depicted in fig. 13 may be performed in a different sequential order. For example, assigning weights to each segment may be performed simultaneously or immediately after performing watermark extrapolation for that segment. It should further be noted that the above-described procedural steps of distortion tracking also increase the false watermark detection probability. Therefore, care must be taken to ensure that the false conclusive watermark detection probability remains within predefined limits.

FIG. 14 is a simplified diagram of particular components that may be used to perform some or all of the operations of FIG. 13 and/or FIG. 18, according to a disclosed embodiment. The components shown in fig. 14 may reside, at least partially, in a content handling device that may play, record, copy, transfer, or otherwise access content, for example. Content receiver component 1402 is configured to receive modified embedded content. The modified embedded content may, for example, be content that contains an embedded watermark and has been subject to intentional or unintentional distortion. The received modified embedded content is provided in an appropriate format to a multi-step search component 1404, the multi-step search component 1404 configured to generate one or more tentative watermarks and segments to be subject to extrapolation. The multi-step search component 1404 can utilize the steganographic key supplied by the steganographic key selection component 1410. The steganographic keys may be stored on a steganographic key storage component 1408. Watermark extrapolator component 1406 is configured to perform watermark extrapolation for an entire watermark frame or on a segment-by-segment basis. In some embodiments, the template selection component 1418 is configured to receive/retrieve the pre-distorted watermark template, either entirely or on a segment-by-segment basis. For example, template selection component 1418 may retrieve one or more pre-distorted watermark templates from database 1416 and make them available to watermark extrapolator component 1406.

Referring back to fig. 14, the error minimization criteria determination component 1412 is configured to receive the results generated by the watermark extrapolator component 1406. The error minimization criteria determining component 1412 may be further configured to receive additional input from a user or an entity within a larger system or device that allows the error minimization criteria determining component 1412 to determine a desired search granularity. The error minimization criteria determination component 1412 is further configured to communicate with the steganographic key selection component 1410, the template selection component 1418, and the template rearrangement component 1414 to, for example, communicate new search granularity, update template selection rules, and the like. The template rearranging component 1414 is configured to rearrange the pre-distorted watermark template based on information provided by the error minimization criteria determining component 1412. The template rearrangement component 1414 may retrieve the pre-distorted watermark template from the database 1416 and store the pre-distorted watermark template to the database 1416. Evaluator component 1420 may perform various watermark evaluation operations, such as assigning weights to the extrapolated watermark or watermarks, comparing the extrapolated watermark or segments thereof to a pre-distortion template, determining whether a joint evaluation of the extrapolated watermark or watermark segments meets a desired false watermark detection probability, reporting an amount and type of distortion present in the host content, and so forth. In some embodiments, evaluator component 1420 is incorporated into watermark extrapolator component 1406.

According to some embodiments, watermark extraction is facilitated depending on the nature of errors that may contaminate or distort the content. In particular, content processing and/or intentional content attacks may inject random or burst errors into watermarks embedded in the content. For example, burst errors in video images captured by a camcorder can result from sudden camcorder movements, and burst errors in captured audio can result, for example, from unwanted sounds in the background, such as a human coughing sound. According to some embodiments, in the presence of burst errors, the performance of a watermark extraction system may be enhanced if the false watermark detection probability is estimated for a watermark segment rather than for the entire watermark. In one example embodiment, to achieve this enhancement in watermark extraction and reduce processing load, instead of computing weights for the entire watermark itself, the entire watermark is computed and the weights of the individual segments are accumulated.

The following exemplary embodiment illustrates how the weights of individual watermark segments are estimated. Assume that the watermark segment is represented by a string of n bits and the extractor finds that a particular segment contains e bit errors. For example, the number of errors e may be determined by comparing bits comprising a segment to a template representing actual bits in the watermark segment. The weight W (n, e) associated with this segment may be represented by equation (9) below.

In equation (9), w_u(n) represents the expected weight of the unhydroprinted segment of length n, which can be expressed according to equation (10) below.

FIG. 15 shows an exemplary plot of expected weights for unhydroprinted segments generated based on equation (10) as a function of segment length n in bits. To illustrate the utilization of equations (9) and (10) and the graph in fig. 15, consider a 64-bit candidate watermark PACKET in which 20 bits have errors. The weight associated with this packet is 2.3462 according to equation (9). However, if the watermark is divided into two 32-bit segments and if the error burst happens to result in 16-bit errors in the first segment and 4-bit errors in the second segment, the accumulated weight for both segments is 4.52. Thus, by examining the two segments separately and then combining the results, the presence of a watermark with a higher degree of confidence can be established. In some embodiments, the segment length (or more generally, the range of segments as applicable to multi-dimensional watermarks) is selected in a manner to facilitate (or optimize) the detection of watermarks in different distortion environments. For example, if the embedded content is transmitted over a communication channel that is likely to generate burst errors (or that is subject to a particular type of distortion), then a segment length within a particular range may be selected (e.g., 4 ≦ n ≦ 10). In other examples, the potential watermark may be evaluated in an iterative manner using some or all of the possible segment lengths (e.g., 2 ≦ n ≦ (watermark frame length/2)) in order to select the segment length that yields the highest accumulated weight.

In many cases, multiple watermarks, each carrying a different payload, are embedded into the same content. For example, content may simultaneously carry watermark messages intended for copy control, content identification, identification of content owner, identification of distributor and/or recipient, providing synchronous operation with external applications, and so forth. In these cases, different watermarks may have different performance requirements with respect to payload size, robustness, security, false detection probability, processing load, and other requirements. In these systems, each watermark message may typically be embedded and extracted independently.

When multiple watermark messages are embedded in content, the extraction of the watermark messages may be greatly enhanced by extracting one or both of the embedded watermark messages in a coordinated manner. In particular, in some embodiments, the distortion estimation performed for the first watermark message may be reused to facilitate extraction of a second watermark message having different performance requirements than the first watermark message. In general, watermark messages having a lower payload size (e.g., copy control watermarks) may be used more efficiently to estimate content distortion than watermark messages having a larger payload size (e.g., content identification watermarks and/or forensic watermarks used to distinguish different copies of content). For example, having a watermark message with a smaller payload may enable the use of more powerful error correction capabilities. Furthermore, watermark messages with smaller footprints may be less susceptible to temporally/spatially varying distortion and may be embedded in larger numbers, thereby improving the robustness of watermark extraction. In addition, having a small payload may enable the use of more efficient search algorithms based on template matching as opposed to error correction decoding processes. Thus, in some embodiments, distortion estimation is performed based on watermark messages having smaller payload sizes, and the result is used to make a target extraction attempt for watermark messages having larger payload sizes.

According to some embodiments, when there are multiple watermark messages in the content, the extraction of the embedded watermark is further improved by initiating the extraction of the watermark with a larger payload (and less robustness) only when a tentative watermark with a smaller payload is detected. In this way, significant computational savings may be achieved due to the prevention of invalid searches for larger payload watermarks in unwritten content. Furthermore, even in marked content, multiple searches for larger payload watermarks in distortion space are eliminated. Having to do fewer searches also reduces the probability of false watermark detection associated with larger payload watermarks. Experiments conducted by the inventors have revealed that correlating the search for larger payload watermark messages with the detection of conclusive lower payload watermark messages yields negligible improvements in watermark extraction efficiency and false positive rate in some scenarios, but may significantly reduce the robustness of the larger payload watermark messages. That is, the extraction of the larger payload watermark message is triggered less frequently and thus sufficient opportunity for detection of the larger payload watermark is wasted. Thus, as mentioned earlier, detection based on a tentative smaller payload watermark message triggers a larger payload watermark message to improve the efficiency and processing load of the extraction operation, while providing reasonably robust detection results of the larger payload watermark message.

It should be understood that the various embodiments of the invention may be implemented individually or collectively in a device made up of various hardware and/or software modules and components. In describing the disclosed embodiments, separate components have sometimes been illustrated as being configured to perform one or more operations. However, it should be understood that two or more of such components may be combined together and/or that each component may include sub-components not depicted. Further, the operations described in the various figures of the present application are presented in a particular sequential order in order to facilitate an understanding of the underlying concepts. However, it should be understood that such operations may be performed in a different sequential order, and further, that additional or fewer steps may be used to perform the various disclosed operations.

In some examples, the devices described in this application may include a processor, a memory unit, an interface communicatively connected to each other, and may range from desktop and/or laptop computers to consumer electronic devices (e.g., media players, mobile devices, etc.). For example, FIG. 16 illustrates a block diagram of a device 1600 within which various disclosed embodiments may be implemented. Device 1600 includes at least one processor 1602 and/or controller, at least one memory 1604 unit in communication with processor 1602, and at least one communication unit 1606 to enable exchange of data and information with other entities, devices, databases, and networks, either directly or indirectly through communication link 1608. Communication unit 1606 may provide wired and/or wireless communication capabilities in accordance with one or more communication protocols, and thus, may include appropriate transmitter/receiver antennas, circuitry, and ports, as well as necessary encoding/decoding capabilities that may enable appropriate transmission and/or reception of data and other information. The exemplary device 1600 depicted in fig. 16 may be integrated as part of a content handling device, watermark embedding and/or extraction device.

Various embodiments described herein are described in the general context of methods or program steps that may be implemented in one embodiment by a computer program product embodied in a computer-readable medium that includes computer-executable instructions, such as program code, executed by computers in networked environments. Computer-readable media can include removable and non-removable storage devices, including, but not limited to, read-only memory (ROM), random-access memory (RAM), Compact Discs (CD), Digital Versatile Discs (DVD), Blu-ray discs, and the like. Thus, the computer-readable media described in this application includes non-transitory storage media. Generally, program modules may include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Computer-executable instructions, associated data structures, and program modules represent examples of program code for executing steps of the methods disclosed herein. The particular sequence of such executable instructions or associated data structures represents examples of corresponding acts for implementing the functions described in such steps or program steps. Content embedded with watermarks according to disclosed embodiments may be stored on a storage medium. In some embodiments, such stored content including one or more imperceptible embedded watermarks, when accessed by a content handling device (e.g., a software or hardware media player) configured with a watermark extractor, may trigger watermark extraction procedure steps, associated signal processing operations, and subsequent operations by the watermark extractor and/or content handling device disclosed in the present application.

The foregoing description of the embodiments has been presented for purposes of illustration and description. The foregoing description is not intended to be exhaustive or to limit embodiments of the invention to the precise form disclosed, and modifications and variations are possible in light of the above teachings or may be acquired from practice of various embodiments. The embodiments discussed herein were chosen and described in order to explain the principles and the nature of various embodiments and their practical application to enable one skilled in the art to utilize the present invention in various embodiments and with various modifications as are suited to the particular use contemplated. The features of the embodiments described herein may be combined in all possible combinations of methods, apparatus, modules, systems, and computer program products.

Claims (51)

1. A method, comprising:

receiving a watermark frame comprising a synchronization portion and a packet portion, the watermark frame having been obtained from content in which a watermark is embedded;

comparing the received synchronization portion to one or more pre-distorted synchronization templates; and

evaluating the received watermark frame based on at least one result of the comparison.

2. The method of claim 1, wherein the one or more pre-distorted synchronization templates are generated, at least in part, by:

generating a plurality of pilot content;

embedding the plurality of pilot content with a watermark comprising a synchronization portion;

distorting the plurality of embedded pilot contents with one or more distortions; and

candidate pre-distorted synchronization templates are obtained from the plurality of distorted pilot contents.

3. The method of claim 2, further comprising:

receiving a subset of the plurality of embedded pilot contents after transmission over a transmission medium, wherein the transmission medium introduces one or more distortions into the subset of the plurality of embedded pilot contents;

comparing a synchronization portion of the received subset of the plurality of pilot content to each of the candidate pre-distorted synchronization templates; and

selecting one or more candidate pre-distorted synchronization templates that match the synchronization portion of the plurality of pilot content of the received subset within a predefined tolerance.

4. The method of claim 1, wherein the comparison results in one or both of:

an error count for each of the one or more pre-distorted synchronization templates indicating a number of mismatched symbols between the received synchronization portion of the watermark frame and each of the one or more pre-distorted synchronization templates; and

a correlation value for each of the one or more pre-distorted synchronization templates that indicates how well the synchronization portion of the watermark frame matches each of the one or more pre-distorted synchronization templates.

5. The method of claim 1, further comprising:

after the comparing, identifying a pre-distorted synchronization template that best matches the received synchronization portion of the watermark frame; and

one or more distortion types and distortion amounts associated with the identified predistortion synchronization template are selected to represent the distortion present in the content.

6. The method of claim 1, further comprising:

the candidate predistortion synchronization templates are organized in a pre-sort order for each type of distortion and/or distortion combination, wherein the pre-sort order ranks a first candidate predistortion synchronization template having a higher likelihood of representing real content distortion higher than a second candidate predistortion synchronization template having a lower likelihood of representing real content distortion.

7. The method of claim 1, wherein the evaluation produces an indication of the presence of one of:

tentative watermarks representing candidate watermarks having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection,

conclusive watermarks, representing watermarks detected with an associated probability of false watermark detection less than or equal to a desired probability of false watermark detection,

one or more distortion types and amounts of distortion present in the content.

8. The method of claim 1, wherein:

the content comprises at least first and second watermark messages;

the first watermark message has a smaller payload than the second watermark message;

evaluating the received watermark frame resulting in detecting the first watermark message as a tentative watermark; and is

Extracting the second watermark message using a content distortion estimate obtained for the tentative watermark.

9. The method of claim 1, further comprising:

extracting a tentative watermark from host content, the tentative watermark representing a candidate watermark having an associated false watermark detection probability that exceeds a desired false watermark detection probability;

forming one or more extrapolated watermarks by obtaining symbols of potential watermark frames positioned within the content at predefined locations relative to the extracted tentative watermark; and

determining whether the extrapolated watermark satisfies a desired false watermark detection probability when evaluated jointly with the detected tentative watermark.

10. The method of claim 9, wherein the symbols of the potential watermark frame are positioned within the content at predefined temporal and/or spatial locations relative to the extracted tentative watermark.

11. The method of claim 9, wherein the determining comprises:

determining a number of erroneous symbols in one or more of the extrapolated watermarks;

assigning weights to the one or more of the extrapolated watermarks based at least in part on the determined number of erroneous symbols; and

determining whether the weighted extrapolated watermark, when combined with the detected tentative watermark, satisfies the desired false watermark detection probability.

12. The method of claim 11, wherein the number of erroneous symbols in each extrapolated watermark is determined by one or more of:

a comparison of the extrapolated watermark symbols with the symbols of the extracted tentative watermark;

performing error correction code decoding of the extrapolated watermark symbols; and

a comparison of the extrapolated watermark to one or more pre-distorted watermark templates.

13. The method of claim 9, wherein:

forming the extrapolated watermark comprises obtaining symbols of the potential watermark frame on a segment-by-segment basis, wherein each segment comprises two of more watermark symbols; and is

The determining includes:

obtaining a number of erroneous symbols in one or more segments;

assigning a weight to each of the one or more segments based at least in part on the number of erroneous symbols in each of the one or more segments;

combining the assigned weights associated with the one or more segments to generate one or more weighted extrapolated watermark segments; and

determining whether the weighted extrapolated watermark segment, when combined with the detected tentative watermark, satisfies the desired false watermark detection probability.

14. The method of claim 13, wherein obtaining the number of erroneous symbols in each of the one or more segments comprises:

comparing the symbols of the potential watermark frame in each of the one or more segments to one or more pre-distorted watermark templates; and

generating a count for each of the one or more segments, the count representing a number of mismatched symbols between the symbols of the potential watermark frame and the one or more pre-distorted watermark templates in the one or more segments.

15. The method of claim 13, wherein a number of segments within the extrapolated watermark is determined based on one or more of:

a range of the extracted tentative watermark;

an amount of distortion present in the content; and

the type of distortion present in the content.

16. The method of claim 13, wherein the weight of a particular segment is assigned based at least in part on an expected weight of unhydromarked segments equal in length to the particular segment.

17. The method of claim 9, wherein the desired false watermark detection probability corresponds to detection of a conclusive watermark.

18. The method of claim 9, further comprising reporting an estimate of an amount and type of distortion or combination of distortions present in the embedded host content.

19. The method of claim 13, wherein a range for each segment is determined based at least in part on one or more of:

an amount of distortion expected to be present in the content; and

the type of distortion expected to be present in the content.

20. The method of claim 1, further comprising

Extracting a plurality of tentative watermarks from the content, each tentative watermark representing a candidate watermark having an associated false watermark detection probability that exceeds a desired false watermark detection probability;

obtaining estimated distortion information associated with one or more distortions present in the embedded host content using at least two of the extracted tentative watermarks;

obtaining one or more pre-distorted watermark templates based on the estimated distortion information; and

re-evaluating at least one of the extracted tentative watermarks using the one or more pre-distorted watermark templates.

21. The method of claim 20, wherein the re-evaluation results in one or more of:

detecting a watermark having an improved probability of false watermark detection compared to a probability of false watermark detection associated with each of the extracted tentative watermarks;

detecting a conclusive watermark having an associated probability of false watermark detection that is less than or equal to the desired probability of false watermark detection; and

an improved estimate of distortion present in the embedded host content.

22. The method of claim 21, wherein the estimated distortion information is obtained using two or more synchronized portions of the at least two extracted tentative watermarks.

23. The method of claim 1, further comprising:

extracting a tentative watermark from the content, the tentative watermark representing a candidate watermark having an associated false watermark detection probability that exceeds a desired false watermark detection probability;

obtaining estimated distortion information indicative of a coarse value of a particular distortion or combination of distortions present in the embedded host content using the extracted tentative watermark;

selecting one or more supplemental pre-distortion watermark templates corresponding to one or more distortion values in the vicinity of the coarse value; and

reevaluating the extracted tentative watermark using the selected one or more supplemental pre-distorted watermark templates.

24. The method of claim 23, wherein obtaining the estimated distortion information comprises:

selecting, at a coarse granularity, a plurality of coarse pre-distortion watermark templates corresponding to a range of distortion values for a particular distortion or combination of distortions;

comparing the extracted tentative watermark to each of the plurality of coarse pre-distorted watermark templates; and

the estimated distortion information is obtained by identifying a first coarse pre-distorted watermark template that best matches the extracted tentative watermark.

25. The method of claim 23, wherein the re-evaluation results in detection of a conclusive watermark with an associated probability of false watermark detection that is less than or equal to a desired probability of false watermark detection.

26. The method of claim 23, wherein the reevaluation comprises:

comparing the one or more supplemental pre-distorted watermark templates to the extracted tentative watermark;

generating an error count associated with each comparison that represents how well the corresponding supplemental pre-distorted watermark template matches the extracted tentative watermark; and

selecting the supplemental pre-distorted watermark template that corresponds to the smallest generated error count.

27. An apparatus, comprising:

a receiver configured to receive a watermark frame comprising a synchronization portion and a packet portion, the watermark frame having been obtained from content embedded with a watermark;

a comparator configured to compare the received synchronization portion to one or more pre-distorted synchronization templates; and

an evaluator configured to evaluate the received watermark frame based on at least a result of the comparator.

28. The device of claim 27, wherein the comparator is configured to generate one or both of:

an error count for each of the one or more pre-distorted synchronization templates indicating a number of mismatched symbols between the received synchronization portion of the watermark frame and each of the one or more pre-distorted synchronization templates; and

a correlation value for each of the one or more pre-distorted synchronization templates that indicates how well the synchronization portion of the watermark frame matches each of the one or more pre-distorted synchronization templates.

29. The device of claim 27, wherein the comparator is configured to:

identifying a pre-distorted synchronization template that best matches the received synchronization portion of the watermark frame; and

one or more distortion types and distortion amounts associated with the identified predistortion synchronization template are selected to represent the distortion present in the content.

30. The device of claim 27, wherein the evaluator is configured to generate an indication of the presence of one or more of:

tentative watermarks representing candidate watermarks having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection,

conclusive watermarks representing watermarks detected with an associated probability of false watermark detection less than or equal to a desired probability of false watermark detection, and

one or more distortion types and amounts of distortion present in the content.

31. The apparatus of claim 27, wherein:

the content comprises at least first and second watermark messages;

the first watermark message has a smaller payload than the second watermark message; and is

The evaluator is configured to generate an indication of detection of the first watermark message as a tentative watermark and a content distortion estimate, wherein the second watermark message is extracted using the content distortion estimate.

32. The device of claim 27, further comprising

An extractor configured to extract a tentative watermark from the content, the tentative watermark representing a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection; and

a watermark extrapolator configured to form one or more extrapolated watermarks by obtaining symbols of potential watermark frames positioned within the content at predefined locations relative to the extracted tentative watermark; wherein

The evaluator is further configured to determine whether the extrapolated watermark satisfies a desired false watermark detection probability when evaluated jointly with the detected tentative watermark.

33. The device of claim 32, wherein the watermark extrapolator is configured to obtain the symbols of the potential watermark frame from locations within the content at predefined temporal and/or spatial locations relative to the extracted tentative watermark.

34. The device of claim 32, wherein the evaluator is configured to:

determining a number of erroneous symbols in one or more of the extrapolated watermarks;

assigning weights to the one or more of the extrapolated watermarks based at least in part on the determined number of erroneous symbols; and

determining whether the weighted extrapolated watermark, when combined with the detected tentative watermark, satisfies the desired false watermark detection probability.

35. The device of claim 34, wherein the number of erroneous symbols in each extrapolated watermark is determined by one or more of:

a comparison of the extrapolated watermark symbols with the symbols of the extracted tentative watermark;

performing error correction code decoding of the extrapolated watermark symbols; and

a comparison of the extrapolated watermark to one or more pre-distorted watermark templates.

36. The apparatus of claim 32, wherein:

the watermark extrapolator is configured to form the extrapolated watermark by obtaining symbols of the potential watermark frame at least in part on a segment-by-segment basis, wherein each segment includes two of more watermark symbols; and is

The evaluator is configured to:

obtaining a number of erroneous symbols in one or more segments;

assigning a weight to each of the one or more segments based at least in part on the number of erroneous symbols in each of the one or more segments;

combining the assigned weights associated with the one or more segments to generate one or more weighted extrapolated watermark segments; and

determining whether the weighted extrapolated watermark segment, when combined with the detected tentative watermark, satisfies the desired false watermark detection probability.

37. The device of claim 36, wherein the evaluator is configured to obtain the number of erroneous symbols in each of the one or more segments at least in part by:

comparing the symbols of the potential watermark frame in each of the one or more segments to one or more pre-distorted watermark templates; and

generating a count for each of the one or more segments, the count representing a number of mismatched symbols between the symbols of the potential watermark frame and the one or more pre-distorted watermark templates in the one or more segments.

38. The device of claim 32, wherein the evaluator is configured to assign a particular segment the weight based at least in part on an expected weight of an un-watermarked segment equal in length to the particular segment.

39. The device of claim 32, wherein the evaluator is configured to report an estimate of an amount and type of distortion or combination of distortions present in the content.

40. The device of claim 27, further comprising

An extractor configured to extract a plurality of tentative watermarks from the content, each tentative watermark representing a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection; and

a distortion estimator configured to obtain estimated distortion information associated with one or more distortions present in the embedded host content using at least two of the extracted tentative watermarks and obtain one or more pre-distorted watermark templates; wherein

An evaluator is configured to re-evaluate at least one of the extracted tentative watermarks using the one or more pre-distorted watermark templates.

41. The device of claim 40, wherein the distortion estimator is configured to determine whether the estimated distortion information corresponds to an amount of distortion that exceeds a particular distortion threshold, and to obtain the one or more pre-distorted watermark templates only if the estimated distortion information corresponds to an amount of distortion that does not exceed the particular distortion threshold.

42. The device of claim 40, wherein the distortion estimator is configured to obtain the estimated distortion information using two or more synchronized portions of the at least two extracted tentative watermarks.

43. The device of claim 27, further comprising

An extractor configured to extract a tentative watermark from the content, the tentative watermark representing a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection;

a distortion estimator configured to obtain estimated distortion information indicative of a coarse value of a particular distortion or combination of distortions present in the content using the extracted tentative watermark, and to select one or more supplemental pre-distortion watermark templates corresponding to one or more distortion values in the vicinity of the coarse value; wherein

The evaluator is further configured to reevaluate the extracted tentative watermark using the selected one or more supplemental pre-distorted watermark templates.

44. The device of claim 43, wherein the distortion estimator is configured to:

selecting, at a coarse granularity, a plurality of coarse pre-distortion watermark templates corresponding to a range of distortion values for a particular distortion or combination of distortions;

comparing the extracted tentative watermark to each of the plurality of coarse pre-distorted watermark templates; and

the estimated distortion information is obtained by identifying a first coarse pre-distorted watermark template that best matches the extracted tentative watermark.

45. The device of claim 43, wherein the evaluator is configured to:

comparing the one or more supplemental pre-distorted watermark templates to the extracted tentative watermark;

generating an error count associated with each comparison that represents how well the corresponding supplemental pre-distorted watermark template matches the extracted tentative watermark; and

selecting the supplemental pre-distorted watermark template that corresponds to the smallest generated error count.

46. A computer program product, embodied on a non-transitory computer-readable medium, comprising:

program code for receiving a watermark frame comprising a synchronization portion and a packet portion, the watermark frame having been obtained from content in which a watermark is embedded;

program code for comparing the received synchronization portion to one or more pre-distorted synchronization templates; and

program code for evaluating the received watermark frame based on at least a result of the comparison.

47. The computer program product of claim 46, further comprising:

program code to extract a tentative watermark from the content, the tentative watermark representing a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection;

program code for forming one or more extrapolated watermarks by obtaining symbols of potential watermark frames positioned within the content at predefined locations relative to the extracted tentative watermark; and

program code for determining whether the extrapolated watermark satisfies a desired false watermark detection probability when evaluated jointly with the detected tentative watermark.

48. The computer program product of claim 46, further comprising:

program code for extracting a plurality of tentative watermarks from the content, each tentative watermark representing a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection;

program code for obtaining estimated distortion information associated with one or more distortions present in embedded host content using at least two of the extracted tentative watermarks;

program code to obtain one or more pre-distorted watermark templates based on the estimated distortion information; and

program code for re-evaluating at least one of the extracted tentative watermarks using the one or more pre-distorted watermark templates.

49. The computer program product of claim 46, further comprising:

program code to extract a tentative watermark from the content, the tentative watermark representing a candidate watermark having an associated probability of false watermark detection that exceeds a desired probability of false watermark detection;

program code for obtaining estimated distortion information indicative of a coarse value of a particular distortion or combination of distortions present in the embedded host content using the extracted tentative watermark;

program code for selecting one or more supplemental pre-distorted watermark templates corresponding to one or more distortion values in the vicinity of the coarse value; and

program code for re-evaluating the extracted tentative watermark using the selected one or more supplemental pre-distorted watermark templates.

50. An apparatus, comprising:

a watermark embedder configured to embed a plurality of pilot content with a watermark comprising a synchronization portion;

a distortion processing component configured to distort the plurality of embedded pilot contents with one or more distortions; and

a watermark extractor configured to generate a candidate pre-distorted synchronization template from the plurality of distorted pilot content.

51. The device of claim 50, further comprising:

a receiver configured to receive a subset of the plurality of embedded pilot contents after transmission over a transmission medium, wherein the transmission medium introduces one or more distortions into the subset of the plurality of embedded pilot contents; and

a template matching component configured to compare a synchronization portion of the received subset of the plurality of pilot content to each of the candidate pre-distorted synchronization templates and select one or more candidate pre-distorted synchronization templates that match the synchronization portion of the received subset of the plurality of pilot content within a predefined tolerance.