# Patent

## Title
Watermark extractor enhancements based on payload ranking

## Abstract

Methods, devices, systems and computer program products improve the detection of watermarks that are embedded in a host content by providing information indicative of a ranking of watermark payloads to watermark extractors. A watermark extractor device obtains information indicative of a ranking of a plurality of watermark payload values, where such information designates each watermark payload value within a first subset of the plurality of watermark payload values as having an associated rank value. Based at least in-part on the information indicative of the ranking, the watermark extractor device is configured to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset. The watermark extractor then extracts a payload value, designated as belonging to the first subset, from one or more watermarks embedded in the host content.

## Background
FIELD OF INVENTION
The present application generally relates to the field of content management. More particularly, the disclosed embodiments relate to improving extraction of watermarks that are embedded in host contents.
BACKGROUND
This section is intended to provide a background or context to the disclosed embodiments that are 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. Therefore, 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 in this section.
Watermarks are substantially imperceptible signals embedded into a host content. The host content may be any one of audio, still image, video or any other content that may be stored on a physical medium or transmitted or broadcast from one point to another. Watermarks are designed to carry auxiliary information without substantially affecting fidelity of the host content, or without interfering with normal usage of the host content. For this reason, watermarks are sometimes used to carry out covert communications, where the emphasis is on hiding the very presence of the hidden signals. Other widespread applications of watermarks include prevention of unauthorized usage (e.g., duplication, playing and dissemination) of copyrighted multi-media content, automatic content recognition (ACR), proof of ownership, authentication, tampering detection, content integrity verification, broadcast monitoring, transaction tracking, audience measurement, triggering of secondary activities such as interacting with software programs or hardware components, communicating auxiliary information about the content such as caption text, full title and artist name, or instructions on how to purchase the content, and the like. The above list of applications is not intended to be exhaustive, as many other present and future systems can benefit from co-channel transmission of main and auxiliary information.
Watermark system design involves balancing a number of different requirements, such as imperceptibility, robustness, security, false positive rate, processing load, payload size, etc. In some applications of watermarks, such as copy management applications, the watermarks that are embedded in a host content must often be extracted in consumer products (e.g., media players, copiers, etc.) that access and use the content. As a result of limited computational resources (e.g., memory, real estate on silicon, processing cycles, etc.) available to watermark extractors within such devices, these applications often create challenges in meeting all of the above noted requirements of the watermarking system since an improvement in one requirement often comes at the expense of another requirement. For example, the robustness of watermark extraction (i.e., a measure of how well an extractor can extract embedded watermarks in the presence of noise and other impairments in the host content and/or watermarking channel) can often be improved by increasing the number of extraction attempts at, for example, small offsets from a particular location of interest of the host content. An increase in the number of extraction attempts, however, increases both the processing load on the extractor and the probability of false watermark extractions. As another example, an increase in payload size typically comes at the expense of reduced robustness and/or increased false positive rate.
In should be noted that in the present application, the term “watermark extraction” is used to describe the operations that result in the extraction of a watermark payload, i.e. the bits or symbols of the message carried by the watermark, which is different from removal or erasure of watermarks from the host content. Alternatively, watermark extraction can be called watermark detection, but sometimes watermark detection is used to indicate the detection of the presence of a watermark within a host content without actually extracting the payload carried by that watermark.
SUMMARY
The disclosed embodiments relate to systems, devices, methods and computer program products that improve the detection of watermarks by providing information indicative of a ranking of watermark payloads to watermark extractors.
One aspect of the disclosed embodiments relates to a method that includes receiving a host content at a watermark extractor device and obtaining, at the watermark extractor device, information indicative of a ranking of a plurality of watermark payload values. Such information designates each watermark payload value within a first subset of the plurality of watermark payload values as having an associated rank value. The method further includes based at least in-part on the information indicative of the ranking, configuring the watermark extractor device to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset, and extracting a payload value from one or more watermarks embedded in the host content. The extracted payload value is one of the payload values designated as belonging to the first subset.
In one exemplary embodiment, prioritizing resource allocation enables extraction of at least one payload value within the first subset with a higher robustness level compared to extraction of any payload value that is not in the first subset. In another exemplary embodiment, prioritizing resource allocation enables extraction of each of the payload values within the first subset with a higher robustness level compared to extraction of each of the payload values within the first subset without the additionally allocated resources. In yet another exemplary embodiment, the ranking comprises a listing of watermark payload values in a particular order of importance. In still another embodiment, the designation as belonging to the first subset is based at least in-part on having a higher likelihood of being extracted compared to watermark payload values that are not in the first subset. The likelihood of being extracted for at least one of the watermark payload values within the first subset is, for example, determine based upon a likelihood of being extracted by other watermark extractor devices.
According to another exemplary embodiment, the designation as belonging to the first subset is based at least in-part on one or more characteristics of the host content. The one or more characteristics can, for example, comprise one or both of: an age or popularity of the host content. In one exemplary embodiment, the designation as belonging to the first subset is based at least in-part on an extent of economic loss associated with unauthorized dissemination of the host content. In still another exemplary embodiment, the designation as belonging to the first subset is based at least in-part on statistics collected regarding one or both of: the host content, or one or more watermark payload values.
In one exemplary embodiment, the designation as belonging to the first subset is based at least in-part on one or more of: a viewing history of a user of the extractor device, a location of a user of the extractor device, a preference of a user of the extractor device, a demographic information of a user of the extractor device, or a behavioral information of a user of the extractor device. In another exemplary embodiment, a count of watermark payload values in the first subset is determined based on a dynamic threshold value that is changeable, thereby allowing designation of a different number of watermark payload values as belonging to the first subset. In yet another exemplary embodiment, the above noted method further includes updating the first subset to include at least one watermark payload value that is different from the watermark payload values before the updating.
In still another exemplary embodiment, configuring the watermark extractor device to prioritize resource allocation includes one or more of: prioritizing usage of a memory resource, prioritizing usage of processing operations, enabling usage of additional watermark payload templates, or enabling usage of additional error correction code templates. In one exemplary embodiment, configuring the watermark extractor device to prioritize resource allocation enables extraction of at least one watermark payload value that is designated as belonging to the first subset with an increased robustness level and with an increased probability of false watermark extractions compared to a watermark payload value that is not designated as belonging to the first subset. In one exemplary embodiment, an expected probability of false watermark extractions for all watermark payload values is not increased. In another exemplary embodiment, the above noted method further comprises allocating additional watermark templates associated with the watermark payload values in the first subset to produce an expanded set of watermark templates, where extracting the payload value comprises comparing a candidate watermark payload value obtained from the host content to all templates in the expanded set of watermark templates to obtain a match to within a predefined error tolerance. In one variation, at least a subset of the expanded set of watermark templates is stored as a look up table (LUT) within the extractor device prior to initiating extraction of the payload value. In another variation, at least a subset of the expanded set of watermark templates is generated on-the-fly, subsequent to initiating extraction of the payload value.
According to one exemplary embodiment, configuring the watermark extractor device to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset comprises configuring the watermark extractor device to conduct a search for payload values that are designated as belonging to the first subset using template matching operations, where the watermark extractor is configured to conduct a search for payload values that are not designated as belonging to the first subset using non-template-matching error correction code decoding operations. For example, configuring the watermark extractor device to conduct a search for payload values that are designated as belonging to the first subset using template matching operations can include constructing an error correction code watermark payload template for each of the payload values in the first subset.
In another exemplary embodiment, extracting the watermark payload value comprises comparing a candidate watermark payload value obtained from the host content to a plurality of constructed error correction code watermark payload templates corresponding to each of the watermark payload values in the first subset, producing a plurality of error counts, each error count representing a count of mismatched symbols between the candidate watermark payload value and a corresponding constructed error correction code watermark payload template, and identifying, as the extracted watermark payload value, a watermark payload value that corresponds to the smallest error count.
In yet another exemplary embodiment, the above noted method further includes configuring the watermark extractor device to allocate fewer resources for extraction of watermark payload values that are not designated as belonging to the first subset compared to the watermark payload values that are designated as belonging to the first subset. In one exemplary embodiment, the allocated sources for extraction of all payload values is not increased. In another exemplary embodiment, the information indicative of the ranking is obtained from a database located remotely from the extractor device. In still another exemplary embodiment, each of the watermarked payload values is ranked in an order of importance, and configuring the watermark extractor device to prioritize resource allocation comprises allocating more resources for extraction of a payload value that is ranked as being more important within the first subset compared to a payload values that is ranked as being less important within the first subset.
Another aspect of the disclosed embodiments relates to a device that includes a processor, and a memory comprising processor executable code. The processor executable code, when executed by the processor, configures the device to receive a host content, and obtain information indicative of a ranking of a plurality of watermark payload values, where the information designates each watermark payload value within a first subset of the plurality of watermark payload values as having an associated rank value. The processor executable code, when executed by the processor, also configures the device to, based at least in-part on the information indicative of the ranking, configure the device to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset. The processor executable code, when executed by the processor, further configures the device to extract a payload value from one or more watermarks embedded in the host content, where the extracted payload value is one of the payload values designated as belonging to the first subset.
In one exemplary embodiment, the processor executable code, when executed by the processor, further configures the device to receive new information indicative of the ranking, and modify the first subset in accordance with the new information. In another exemplary embodiment, the processor executable code, when executed by the processor, configures the device to modify the first subset by at least one of: adding a payload value to the first subset that was not previously in the first subset, o removing an existing payload value from the first subset. In still another exemplary embodiment, the processor executable code, when executed by the processor, configures the device to allocate the additional resources including one or more of: prioritizing usage of an additional memory resource, prioritizing usage of additional processing operations, allocating additional watermark payload templates, or allocating additional error correction code templates.
In another exemplary embodiment, the processor executable code, when executed by the processor, further configures the device to allocate additional watermark templates associated with the watermark payload values in the first subset to produce an expanded set of watermark templates. Further, the processor executable code, when executed by the processor, configures the device to extract the payload value by at least in-part comparing a candidate watermark payload value obtained from the host content to all templates in the expanded set of watermark templates to obtain a match to within a predefined error tolerance.
In still another exemplary embodiment, the processor executable code, when executed by the processor, configures the device to conduct a search for payload values that are designated as belonging to the first subset using template matching operations, where the watermark extractor is configured to conduct a search for payload values that are not designated as belonging to the first subset using non-template-matching error correction code decoding operations. In another exemplary embodiment, the processor executable code, when executed by the processor, configures the device to construct an error correction code watermark payload template for each of the payload values in the first subset.
In one exemplary embodiment, the processor executable code, when executed by the processor, configures the device to compare a candidate watermark payload value obtained from the host content to a plurality of constructed error correction code watermark payload templates corresponding to each of the watermark payload values in the first subset, produce a plurality of error counts, each error count representing a count of mismatched symbols between the candidate watermark payload value and a corresponding constructed error correction code watermark payload template, and identify, as the extracted watermark payload value, a watermark payload value that corresponds to the smallest error count. In still another exemplary embodiment, the processor executable code, when executed by the processor, further configures the device to allocate fewer resources for extraction of watermark payload values that are not designated as belonging to the first subset compared to the watermark payload values that are designated as belonging to the first subset.
In another exemplary embodiment a system is provided that includes the above noted device. Such a system further includes a management center comprising a database, where the management center is configured to provide the information indicative of the ranking from the database to the extractor device. Such a system can also include a plurality of additional devices, each of the plurality of additional devices comprising a corresponding watermark extractor device, where the management center is configured to communicate bi-directionally with each of the plurality of additional devices and with the device.
Another aspect of the disclosed embodiments relates to a computer program product, embodied on one or more non-transitory computer readable media. The computer program product includes program code for receiving a host content at a watermark extractor device, and program code for obtaining, at the watermark extractor device, information indicative of a ranking of a plurality of watermark payload values, where the information designates each watermark payload value within a first subset of the plurality of watermark payload values as having an associated rank value. The computer program product also includes program code for, based at least in-part on the information indicative of the ranking, configuring the watermark extractor device to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset, and program code for extracting a payload value from one or more watermarks embedded in the host content, wherein the extracted payload value is one of the payload values designated as having belonging to the first subset.
Another aspect of the disclosed embodiments relates to a device that includes a receiver configured to receive a host content, and a processor implemented at least in-part in hardware and configured to obtain information indicative of a ranking of a plurality of watermark payload values. Such information designates each watermark payload value within a first subset of the plurality of watermark payload values as having an associated value. The processor is further configured to, based at least in-part on the information indicative of the ranking, configure a watermark extractor component to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset. The watermark extractor is also configured to extract at least one payload value designated as belonging to the first subset from one or more watermarks that are embedded in the host content.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates a system within which improved watermark extraction using payload ranking can be effectuated in accordance with an exemplary embodiment.
FIG. 2 illustrates a set of operations that can be carried out to improve watermark extraction operations in accordance with an exemplary embodiment.
FIG. 3 illustrates a device that can benefit from, and implement, improved watermark extraction based on watermark payload ranking in accordance with an exemplary embodiment.
FIG. 4 illustrates a block diagram of a device within which various disclosed embodiments may be implemented.



DETAILED DESCRIPTION OF CERTAIN EMBODIMENTS
In the following description, fir 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 those skilled in the art that the present invention may be practiced in other embodiments that depart from these details and descriptions.
Additionally, in the subject description, 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, use of the word exemplary is intended to present concepts in a concrete manner.
As noted earlier, watermarks can be used in many different applications such as copy control, forensic marking, or automatic content recognition (ACR). In many of those applications, not all embedded watermark payloads are equally important or equally likely to be encountered by a particular extractor. For example, in ACR applications, where particular types of content, or particular content repositories and websites are examined, a watermark extractor may be provided with some prior knowledge as to which watermark payload values are likely to be presented to it. Such an advanced knowledge of watermark payload values can, for example, be acquired by the watermark extractor using a database that maintains information regarding watermark extractions occurring in other (e.g., similar) extractors. The extractor can then use such information to preferentially allocate more or less resources to extract certain watermark payloads. That is, allocation of resources are prioritized such that more resources are allocated for the extraction of watermark payload values that are designated as having a high rank. Non-limiting examples of such additional resources include additional memory resources, additional processing operations (e.g., computations cycles), additional watermark payload templates and additional error correction code templates. Further details of watermark and error correction code templates are provided in the sections that follow. In some embodiments, the allocation of total resources for the extraction of all watermark payloads remains unchanged (or is not increased) since an increase in allocation of resources for higher ranked payload values can be offset by a reduced allocation of resources for lower ranked payload values. Further, since, in some embodiments, the extraction of higher ranked payloads is more likely, the resources for extraction of lower ranked payloads may not get utilized.
In some embodiments, the designation of payload values as having a high rank value is based at least in-part on an extent of economic loss associated with unauthorized dissemination of the host content. For example, in a copy control watermarking system, a content that includes a “no home use” message as part of its embedded watermark payload often corresponds to a content that is only authorized for presentation in movie theatres. As such, any subsequent encounters with such a movie (e.g., at a file sharing website) should be treated as a movie piracy scenario, which can result in a significant economic loss to the movie studios, movie theatres, actors, and other personnel and entities that are involved in the production and distribution of the movie. In this case, proper extraction of a “no home use” watermark payload is treated as more important than extraction of, for example, a “no Internet redistribution” payload (which could represent unauthorized dissemination of a content that is intended to be only released on DVD).
In some exemplary embodiments, the designation of payload values as having a high rank value is based at least in-part on a contractual agreement that requires a watermark system designer or a system operator to treat particular watermark payloads with higher priority than other payloads.
In some embodiments, an extractor is configured to adjust its operations to conduct watermark extraction based on a received payload ranking information. For example, in one embodiment, an extractor first attempts to extract only those payloads that are most likely to be embedded in the content, and only upon a determination that those payloads cannot be reliably extracted, the extractor conducts further operations to extract less likely payloads. In such a configuration, the processing load is often reduced, since the extractor is more likely to conclude its operations when a likely payload is successfully extracted rather than expending resources in a systematic search of the payload space that includes unlikely watermark payload candidates.
In many applications, a watermarking system is designed based on a predefined maximum false positive rate. If all payloads are treated equally by the extractor, then each candidate watermark payload makes an equal contribution to the overall false positive rate of the watermarking system. On the other hand, when the payloads are ranked in a given priority order, in accordance with the disclosed embodiments, a watermark extractor can be configured to allocate a larger fraction of the overall false positive rate budget to the higher ranked payloads as compared to the lower ranked payloads. This way, the extractor becomes capable of extracting higher ranked codes with a higher robustness and/or at a higher confidence level. In such embodiments, the overall expected false positive rate associated with the extraction of all watermark payload values can remain unchanged (or is not increased) since, through proper allocation of extraction operations and resources, a potentially higher false positive rate for some payload values is offset by a tower false positive rate for other payload values.
Another aspect of the disclosed embodiments related to improving the robustness of watermark extractions for high ranking payloads. In particular, watermark extraction robustness in the presence of various signal distortions can be improved with incorporating additional processing steps in the watermark extraction process. For example, an extractor may attempt to invert (e.g., undo) various potential distortions that are likely to contaminate a particular host content, and then attempt to extract watermarks from both the received host content and the inverted host content. Alternatively, distorted watermark templates (e.g., representations of a watermark payload when the host content is subject to the corresponding distortions) can be provided to the extractor so as to allow the extractor to compare a candidate watermark payload that is extracted from the received content to the distorted watermark templates in search of a match. In both of the above extraction techniques, the chances of extracting a watermark improve by increasing the number of watermark extraction or template matching attempts. Such expanded extraction operations not only allow the search of a larger portion of the watermark extraction space, but they can be designed to enable a search of the extraction space with a finer search granularity. The drawback, however, is an increase in both the processing load and the probability of false watermark extractions.
The techniques of the disclosed embodiments allow an extractor to allocate a larger portion of the false positive rate budget and computational resources to the extraction of higher-ranking payloads, thus allowing more extraction attempts to be directed towards such higher ranking payloads while allocating fewer computational resources (e.g., extraction attempts) to the lower-ranking payloads. As a result, in systems that operate in accordance with such exemplary embodiments of the present application, the total number of processing operations and the probability of false watermark extractions can remain substantially the same as systems where such payload ranking techniques are not utilized. Yet, watermarks that are considered to be more important are extracted with an improved extraction robustness.
By the way of example, and not by limitation, the following provides an illustration of watermark extractor enhancements based on payload ranking for an ACR system. In ACR systems, the embedded watermarks can be used to identify the host content (e.g., a movie, a TV show, a song, an image, etc.). In such systems, watermarks can be used to additionally identify a content distribution channel, such as a theatre where the movie is shown or a broadcast station from which the content is being broadcast. Furthermore, watermarks can be used to identify one or more segments of the content by, for example, incorporating a field (e.g., a counter) into the watermark payload that is sequentially incremented (e.g., once per minute) for the duration of the content. In order to carry all of the above information, the watermark payload needs to be relatively large, e.g. between 20 and 100 bits. Such payload bits are typically linked to the content metadata through a database. For example, each field within the watermark payload can be used as a pointer (or a serial number) that identifies a database entry for the corresponding field.
In an ACR system, payload ranking can be implemented based on a number of different criteria. In one example embodiment, the payloads are ranked based on their likelihood of having been extracted by a similar and/or a same type of device. For example, a list of all extracted watermarks can be constructed for software extractors running on operating system A (i.e., device type A), software extractors running on operating system B (i.e., device type B), hardware extractors running on standalone media handling devices such as DVD players (i.e., device type C), hardware extractors running on integrated media handling devices such as media players incorporated in television sets (i.e., device D), etc. For each type of device, the extracted payload values are counted, and sorted to generate a listing (for each device type) that identifies the most frequently extracted payload as the top ranked payload, followed by the second most frequently extracted payload as the second highest ranked payload, and so on.
Alternatively, payload ranking can be implemented based on one or more characteristics of the host content. In some exemplary embodiments, the ranking is determined based on the age and/or popularity of the host content. For example, higher payload rankings can be assigned to currently broadcast content and lower rankings to older content. In one exemplary embodiment, the assignment of payload rankings is carried out at a database which includes, or can obtain, information regarding the age (e.g., whether the content is being currently broadcast) and/or popularity (e.g., if the content is on a top-50 list or has exceeded certain viewership). Such a database also includes, or can obtain, the payload values that have been embedded in such current or popular content, allowing it to generate a payload ranking list based on the age or popularity criteria, and communicate the ranking to one or more extractors. Additional non-limiting examples of payload ranking criteria includes assigning higher ranks to premium content, pay-per-view content, content belonging to customers with special privileges, etc.
Another aspect of the disclosed embodiments relates to providing a payload ranking technique that is based on the use of error correction codes. Since watermarks can be distorted due to various intentional or unintentional processing operations (e.g., as part of content post-processing, transmission and/or storage), watermark payloads are typically encoded using channel coding techniques that allow correction of error-contaminated symbols. Some examples of well-known error correction/error detection codes include Reed-Solomon codes, BCH codes, LDPC codes, CRCs, etc. An error correction code selected for a watermarking system allows a particular number of symbol errors (e.g., bit errors) to be detected and/or corrected depending on the particular parameters of the error correction code. This error correction/detection capability is obtained by adding parity (or redundancy symbols to each block of data e.g., to each watermark payload) that is to be protected, where a larger number of errors can be corrected resulting in a better watermark resilience to signal distortions) at the expense of an increased payload size. It should be noted that typical forward error correction codes treat all payload values equally during the decoding process.
In some exemplary embodiments, payload ranking is used to modify error correction code decoding operations to improve the detection of embedded watermarks with high ranking payloads. In one exemplary embodiment, a set of watermark templates is provided only for the higher ranking payloads. That is, the appropriate parity symbols (generated based on the particular error correction algorithm of the watermarking system) are appended to each of the higher ranking payloads to form “constructed error correction code (or error detection code) packet, templates” (hereinafter a “constructed ECC templates”). A candidate watermark packet that is extracted from a received content is then compared against all such constructed. ECC templates to determine if a match within a predefined error tolerance is found. Upon a determination that such a match is found, the corresponding payload value is declared as the extracted payload value.
In some exemplary embodiments, the constructed ECC templates are stored in a look-up-table (LUT). Alternatively, or additionally, ECC packet templates can be generated on-the-fly after the initiation of watermark extraction operations (e.g., upon acquisition of a watermark packet candidate).
In some exemplary embodiments related to the ECC constructed templates, such templates are only generated for higher ranking payloads and all other payloads are decoded using conventional (i.e., non-template matching) error correction code decoding techniques. For example, upon a determination that no higher ranking code is extracted, the extractor can make a decision as to whether or not to pursue the detection of lower ranking payloads based on conventional techniques. In these embodiments, the extraction robustness of higher ranking payloads is improved since template matching (e.g., based on LUT decoding or on-the-fly generation of templates) typically allows a higher number of errors to be corrected, while maintaining a substantially similar (e.g., within the same order of magnitude) false positive extraction rate, compared to non-template matching techniques. However, depending on the type of error correction code algorithm and the size of error correction code space, LUT decoding results in consumption of additional memory, while computing the templates on-the-fly increases the processing load of the watermark extractor. Thus, in some implementations, the additional robustness for higher ranking payloads is achieved at the expense of consumption of additional resources. It should be noted that on-the-fly generation of watermark templates typically involves generation of the watermark templates based on an algorithm during the watermark extraction process (e.g., after the extraction process is initiated). Thus, on-the-fly watermark generation means that watermark templates are created as needed and then are erased from memory, which is repeated whenever a new need for watermark templates arises, i.e. many times during an extractor run. In contrast, creating templates as, for example, part of extractor initialization process would only require storing the watermark templates in a LUT, which requires memory resources but not much processing, since the templates are created only once per run.
In a first exemplary embodiment where LUT decoding is carried out, the LUT is created by a database and communicated to the extractors. In a second exemplary embodiment, the higher ranking payloads are selected by the database and communicated to the extractor, but generation of the LUT comprising watermark templates for such higher ranking watermark payloads are conducted at the extractor. In the first exemplary embodiment, through the use of some communication bandwidth between the database and the extractors, processing load of the extractors is reduced, whereas in the second embodiment the opposite holds true. The above two exemplary embodiments (and combinations thereof) illustrate how communication bandwidth between the database and the extractors can be traded off for processing load at the extractor. Such tradeoff considerations can be utilized to implement the disclosed embodiments on a case-by-case basis. For instance, in scenarios where communication bandwidth is at a premium, the second exemplary embodiment may be implemented.
In some exemplary embodiments related to the ECC constructed templates, such templates are generated for all payloads, but the higher ranking payloads are treated preferentially. For example, additional variations of ECC construed templates are generated for only the higher ranking payloads while one (or a limited number) of such templates are generated for the remaining payloads. This way, an expanded search of the extraction payload space (i.e., search of a larger portion of the extraction space and/or search a particular portion of the watermark extraction space with finer granularity) is conducted for only the higher ranking payloads. The generation of ECC constructed templates for all payload values can be particularly useful (or efficient) when the watermark payload size is small, and/or when only a limited number of watermark payloads have been implemented.
In some exemplary embodiments, the list of high ranking payloads is dynamically adjusted. For example, the payload values can change over time as certain payloads gain further importance while other payloads lose their importance. Similarly, the count of high ranking payload values can dynamically change as the list of important payloads shrinks or expands to include fewer or additional payload values. In embodiments that template matching is utilized, a list of watermark templates as well as the associated error thresholds, can be updated dynamically to reflect changes in the ranking of the payloads. These changes can be implemented at the extractor device pursuant to communications with a database that decides which payloads should get preferential treatment during a given period of time and/or which extractors should such information be conveyed to. In deciding which payloads to be treated preferentially, additional considerations can be used, such as viewing history of a particular user, user's location obtained through, for example, its IP address, user provided data regarding the user's preferences, a demographic information of a user of the extractor device, a behavioral information of a user of the extractor device, etc.
FIG. 1 illustrates a system within which improved watermark extraction using payload ranking can be effectuated in accordance with an exemplary embodiment. In FIG. 1, the management center 102 is directly or indirectly in communication with a variety of devices 104 to 112 through one or more communication links 118. In some examples, the communication links are secure links and may be bi-directional. A variety of device authentication and handshaking protocols may be used to establish a secure link between the management center 102 and devices 104 to 112. Such devices can include, for example, media players 104, personal computers 106, smart phones 108, game consoles 110, televisions 112, and other devices that include a media handling device with an associated watermark extractor. The management center 102 includes, or is in communication with, a database 114, which stores information related to payload rankings, watermark and error correction code templates, statistics regarding watermark payloads including the frequency of extraction of particular watermark payloads on particular devices, statistics regarding various host content including their age and popularity, and other information. The management center 102 can also be in communication with other entities and devices (not shown), such as certificate authorities and authorization authorities, or may be part of a larger system of content management and distribution network. The management center 102 also includes one or more processors (not shown) with computational capabilities to process the information received and/or stored at the management center 102, to select various watermark payloads, to compute various thresholds, watermarks and error correction code templates and other parameters or values, at least some of which can be subsequently communicated to one or more of the devices 104 through 112. Although FIG. 1 illustrates a single management center 102, it is understood that the functionality of the management center 102 can be implemented as a distributed system comprising a plurality of connected devices and entities.
FIG. 2 illustrates a set of operations that can be carried out to improve watermark extraction operations in accordance with an exemplary embodiment. At 202, a host content is received at an extractor device. Such an extractor device may be a component within a larger device or system, such as a smartphone, a DVD player, a television set and the like. At 204, information indicative of a ranking of a plurality of watermark payload values is obtained. Such information designates a first subset of the plurality of watermark payload values as having an associated rank value. The associated rank value, for example, indicates a ranking tier the corresponding payload that is higher than other watermark payload values not in the first subset. At 206, based, at least in part, on the information indicative of the ranking, the watermark extractor device is configured to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset. At 208, a payload value is extracted from one or more watermarks embedded in the host content. Such an extracted payload value is one of the payload values designated as belonging to the first subset.
FIG. 3 illustrates a device 300 that can benefit from, and implement, improved watermark extraction based on watermark payload ranking in accordance with an exemplary embodiment. The device 300 in FIG. 3 includes a watermark extractor 302 that is configured to extract one or more watermark payloads from the watermarks that are embedded in a host content. For example, the watermark extractor 302 can be configured to perform template matching, error correction code decoding, correlation computations, filtering and other operations that are needed to extract the watermark payloads. The communication components 310 in FIG. 3 are configured to enable communication between the device 300 (and its components) and other entities outside of the device 300, and as such, they can include, or be in communication with, the appropriate transmitter and receiver circuitry (e.g., antenna, analog and digital components, etc.) that are needed to carry out wired or wireless transmission of signals. The buffer 308 in FIG. 3 is used for temporary storage of information and intermediate data and parameters during the extraction of watermarks. For example, the buffer 308 can include a look-up-table with watermark templates that are generated either by Management Center 102 in FIG. 1 or by the extractor itself based on the payload ranking information obtained from the Management Center 102. The device 300 in FIG. 3 can also include at least one processor 304 (e.g. a microprocessor) and a memory 306 comprising processor executable code. Such a processor executable code can configure the device to perform various operations, to allocate resources for extraction of payloads with varying degrees of importance. The processor 304 can be also used to, for example, coordinate the operations of other components within the device 300, to initiate transfer of information and data from/to the device 300, and perform other computations. The memory 306 can include additional data and information that may be needed to carry out the watermark extraction operations.
The disclosed embodiments can be implemented using hardware devices that comprise particular physical components. For example, the devices of the present application can be implemented as an application specific integrated circuit (ASIC), as part of a field programmable gate array (FPGA), and/or using digital and analog components and circuitry.
Certain aspects of the disclosed embodiments can be implemented as a device that includes a processor and a memory comprising processor executable code. The processor executable code, when executed by the processor, configures the device to perform any one of and/or all operations that are described in the present application. For example, FIG. 4 illustrates a block diagram of a device 400 within which various disclosed embodiments may be implemented. The device 400 comprises at least one processor 404 (e.g., a microprocessor) and/or controller, at least one memory 402 unit that is in communication with the processor 404, and at least one communication unit 404 that enables the exchange of data and information, directly or indirectly, through the communication link 408 with other entities, devices, databases and networks. The communication unit 406 may provide wired and/or wireless communication capabilities in accordance with one or more communication protocols, and therefore it may comprise the proper transmitter/receiver, antennas, circuitry and ports, as well as the encoding/decoding capabilities that may be necessary for proper transmission and/or reception of data and other information. The exemplary device 400 of FIG. 4 may be integrated as part of any of the devices that are shown in FIG. 1, such as part of a device at the management center 102, and any of the devices 104 to 112.
Various embodiments described herein are described in the general context of methods or processes, which may be implemented in one embodiment by a computer program product, embodied in a computer-readable medium, including computer-executable instructions, such as program code, executed by computers in networked environments. A computer-readable medium may include removable and non-removable storage devices including, but not limited to, Read Only Memory (ROM), Random Access Memory (RAM), compact discs (CDs), digital versatile discs (DVD), Blu-ray Discs, etc. Therefore, the computer-readable media described in the present application include 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 processes.
For example, one aspect of the disclosed embodiments relates to a computer program product that is embodied on a non-transitory computer readable medium. The computer program product includes program code for carrying out any one or and/or all of the operations of the disclosed embodiments.
The foregoing description of 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 present 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

1. A method, comprising:
receiving a host content at a watermark extractor device;
obtaining, at the watermark extractor device, information indicative of a ranking of a plurality of watermark payload values, the information designating each watermark payload value within a first subset of the plurality of watermark payload values as having an associated rank value;
based at least in-part on the information indicative of the ranking, configuring the watermark extractor device to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset; and
extracting a payload value from one or more watermarks embedded in the host content,
wherein extracting the payload value comprises:
comparing a candidate watermark payload value obtained from the host content to a plurality of constructed error correction code watermark payload templates corresponding to each of the watermark payload values in the first subset,
producing a plurality of error counts, each error count representing a count of mismatched symbols between the candidate watermark payload value and a corresponding constructed error correction code watermark payload template, and
identifying, as the extracted watermark payload value, a watermark payload value that corresponds to the smallest error count, and

wherein the extracted payload value is one of the payload values designated as belonging to the first subset.

2. The method of claim 1, wherein configuring the watermark extractor device to prioritize resource allocation enables extraction of at least one payload value within the first subset with a higher robustness level compared to extraction of any payload value that is not in the first subset.

3. The method of claim 1, wherein configuring the watermark extractor device to prioritize resource allocation enables extraction of each of the payload values within the first subset with a higher robustness level compared to extraction of each of the payload values within the first subset without the additionally allocated resources.

4. The method of claim 1, wherein the ranking comprises a listing of watermark payload values in a particular order of importance.

5. The method of claim 1, wherein the designation as belonging to the first subset is based at least in-part on having a higher likelihood of being extracted compared to watermark payload values that are not in the first subset.

6. The method of claim 5, wherein the likelihood of being extracted for at least one of the watermark payload values within the first subset is determined based upon a likelihood of being extracted by other watermark extractor devices.

7. The method of claim 1, wherein the designation as belonging to the first subset is based at least in-part on one or more characteristics of the host content.

8. The method of claim 7, wherein the one or more characteristics comprise one or both of: an age or popularity of the host content.

9. The method of claim 1, wherein the designation as belonging to the first subset is based at least in-part on an extent of economic loss associated with unauthorized dissemination of the host content.

10. The method of claim 1, wherein the designation as belonging to the first subset is based at least in-part on statistics collected regarding one or both of:
the host content, or
one or more watermark payload values.

11. The method of claim 1, wherein the designation as belonging to the first subset is based at least in-part on one or more of:
a viewing history of a user of the extractor device,
a location of a user of the extractor device,
a preference of a user of the extractor device,
a demographic information of a user of the extractor device, or
a behavioral information of a user of the extractor device.

12. The method of claim 1, wherein a count of watermark payload values in the first subset is determined based on a dynamic threshold value that is changeable, thereby allowing designation of a different number of watermark payload values as belonging to the first subset.

13. The method of claim 1, further comprising updating the first subset to include at least one watermark payload value that is different from the watermark payload values before the updating.

14. The method of claim 1, wherein configuring the watermark extractor device to prioritize resource allocation includes one or more of:
prioritizing usage of a memory resource,
prioritizing usage of processing operations,
allocating additional watermark payload templates, or
allocating additional error correction code templates.

15. The method of claim 1, wherein configuring the watermark extractor device to prioritize resource allocation enables extraction of at least one watermark payload value that is designated as belonging to the first subset with an increased robustness level and with an increased probability of false watermark extractions compared to a watermark payload value that is not designated as belonging to the first subset.

16. The method of claim 15, wherein an expected probability of false watermark extractions for all watermark payload values is not increased.

17. The method of claim 1, further comprising allocating additional watermark templates associated with the watermark payload values in the first subset to produce an expanded set of watermark templates, wherein
extracting the payload value comprises comparing the candidate watermark payload value obtained from the host content to all templates in the expanded set of watermark templates to obtain a match to within a predefined error tolerance.

18. The method of claim 17, wherein at least a subset of the expanded set of watermark templates is stored as a look up table (LUT) within the extractor device prior to initiating extraction of the payload value.

19. The method of claim 17, wherein at least a subset of the expanded set of watermark templates is generated on-the-fly, subsequent to initiating extraction of the payload value.

20. The method of claim 1, wherein configuring the watermark extractor device to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset comprises:
configuring the watermark extractor device to conduct a search for payload values that are not designated as belonging to the first subset using non-template-matching error correction code decoding operations.

21. The method of claim 1, further comprising configuring the watermark extractor device to allocate fewer resources for extraction of watermark payload values that are not designated as belonging to the first subset compared to the watermark payload values that are designated as belonging to the first subset.

22. The method of claim 21, wherein allocated resources for extraction of all payload values is not increased.

23. The method of claim 1, wherein the information indicative of the ranking is obtained from a database located remotely from the extractor device.

24. The method of claim 1, wherein: each of the watermarked payload values is ranked in an order of importance; and configuring the watermark extractor device to prioritize resource allocation comprises allocating more resources for extraction of a payload value that is ranked as being more important within the first subset compared to a payload value that is ranked as being less important within the first subset.

25. The method of claim 1, wherein the watermark payload value that corresponds to the smallest error count is identified as the extracted watermark payload value upon a determination that the smallest error count is below a predefined error tolerance value.

26. 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:
receive a host content;
obtain information indicative of a ranking of a plurality of watermark payload values, the information designating each watermark payload value within a first subset of the plurality of watermark payload values as having an associated rank value;
based at least in-part on the information indicative of the ranking, configure the device to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset; and
extract a payload value from one or more watermarks embedded in the host content, wherein extraction of the payload value comprises:
comparison of a candidate watermark payload value obtained from the host content to a plurality of constructed error correction code watermark payload templates corresponding to each of the watermark payload values in the first subset,
production of a plurality of error counts, each error count representing count of mismatched symbols between the candidate watermark payload value and a corresponding constructed error correction code watermark payload template, and
identification, as the extracted watermark payload value, a watermark payload value that corresponds to the smallest error count, and
wherein the extracted payload value is one of the payload values designated as belonging to the first subset.

27. The device of claim 26, wherein configuring the watermark extractor device to prioritize resource allocation enables extraction of at least one payload value within the first subset with a higher robustness level compared to extraction of any payload value that is not in the first subset.

28. The device of claim 26, wherein configuring the watermark extractor device to prioritize resource allocation enables extraction of each of the payload values within the first subset with a higher robustness level compared to extraction of each of the payload values within the first subset without the additionally allocated resources.

29. The device of claim 26, wherein the ranking comprises a listing of watermark payload values in a particular order of importance.

30. The device of claim 26, wherein the designation as belonging to the first subset is based at least in-part on having a higher a likelihood of being extracted compared to watermark payload values that are not in the first subset.

31. The device of claim 30, wherein the likelihood of being extracted for at least one of the watermark payload values within the first subset is determined based upon a likelihood of being extracted by other devices.

32. The device of claim 26, wherein the designation as belonging to the first subset is based at least in-part on one or more characteristics of the host content.

33. The device of claim 32, wherein the one or more characteristics comprise one or both of: an age or popularity of the host content.

34. The device of claim 26, wherein the designation as belonging to the first subset is based at least in-part on an extent of economic loss associated with unauthorized dissemination of the host content.

35. The device of claim 26, wherein the designation as belonging to the first subset is based at least in-part on statistics collected regarding one or both of:
the host content, or
one or more watermark payload values.

36. The device of claim 26, wherein the designation as belonging to the first subset is based at least in-part on one or more of:
a viewing history of a user of the device,
a location of a user of the device,
a preference of a user of the device,
a demographic information of a user of the extractor device, or
a behavioral information of a user of the extractor device.

37. The device of claim 26, wherein the processor executable code, when executed by the processor, further configures the device to:
receive new information indicative of the ranking; and
modify the first subset in accordance with the new information.

38. The device of claim 26, wherein the processor executable code, when executed by the processor, configures the device to modify the first subset by at least one of:
adding a payload value to the first subset that was not previously in the first subset, or
removing an existing payload value from the first subset.

39. The device of claim 26, the processor executable code, when executed by the processor, configures the device to prioritize resource allocation by including one or more of:
prioritizing usage of a memory resource,
prioritizing usage of processing operations,
allocating additional watermark payload templates, or
allocating additional error correction code templates.

40. The device of claim 26, wherein configuring the device to prioritize resource allocation enables extraction of at least one watermark payload value that is designated as belonging to the first subset with an increased robustness level and with an increased probability of false watermark extractions compared to a watermark payload value that is not designated as belonging to the first subset.

41. The device of claim 40, wherein an expected probability of false watermark extractions for all watermark payload values remains unchanged.

42. The device of claim 26, wherein:
the processor executable code, when executed by the processor, further configures the device to allocate additional watermark templates associated with the watermark payload values in the first subset to produce an expanded set of watermark templates; and
the processor executable code, when executed by the processor, configures the device to extract the payload value by at least in-part comparing the candidate watermark payload value obtained from the host content to all templates in the expanded set of watermark templates to obtain a match to within a predefined error tolerance.

43. The device of claim 42, wherein the processor executable code, when executed by the processor, further configures the device to store at least a subset of the expanded set of watermark templates as a look up table (LUT) within the device prior to initiating extraction of the payload value.

44. The device of claim 42, wherein the processor executable code, when executed by the processor, further configures the device to generate at least a subset of the expanded set of watermark templates on-the-fly, subsequent to initiating extraction of the payload value.

45. The device of claim 26, the processor executable code, when executed by the processor, configures the device to conduct a search for payload values that are not designated as belonging to the first subset using non-template-matching error correction code decoding operations.

46. The device of claim 26, wherein the processor executable code, when executed by the processor, further configures the device to allocate fewer resources for extraction of watermark payload values that are not designated as belonging to the first subset compared to the watermark payload values that are designated as belonging to the first subset.

47. The device of claim 46, wherein allocated resources for extraction of all payload values is not increased.

48. The device of claim 26, wherein: each of the watermarked payload values is ranked in an order of importance; and the processor executable code, when executed by the processor, configures the device to prioritize resource allocation by allocating more resources for extraction of a payload value that is ranked as being more important within the first subset compared to a payload value that is ranked as being less important within the first subset.

49. A system comprising the device of claim 26, and further comprising a management center comprising a database, wherein the management center is configured to provide the information indicative of the ranking from the database to the extractor device.

50. The system of claim 48, further comprising a plurality of additional devices, each of the plurality of additional devices comprising a corresponding watermark extractor device, wherein the management center is configured to communicate bi-directionally with each of the plurality of additional devices and with the device.

51. The device of claim 26, wherein the watermark payload value that corresponds to the smallest error count is identified as the extracted watermark payload value upon a determination that the smallest error count is below a predefined error tolerance value.

52. A computer program product, embodied on one or more non-transitory computer readable media, comprising:
program code for receiving a host content at a watermark extractor device;
program code for obtaining, at the watermark extractor device, information indicative of a ranking of a plurality of watermark payload values, the information designating each watermark payload value within a first subset of the plurality of watermark payload values as having an associated rank value;
program code for, based at least in-part on the information indicative of the ranking,
configuring the watermark extractor device to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset; and
program code for extracting a payload value from one or more watermarks embedded in the host content,
wherein extracting the payload value comprises:
comparing a candidate watermark payload value obtained from the host content to a plurality of constructed error correction code watermark payload templates corresponding to each of the watermark payload values in the first subset,
producing a plurality of error counts, each error count representing a count of mismatched symbols between the candidate watermark payload value and a corresponding constructed error correction code watermark payload template, and
identifying, as the extracted watermark payload value, a watermark payload value that corresponds to the smallest error count, and

wherein the extracted payload value is one of the payload values designated as belonging to the first subset.

53. The A computer program product of claim 52, wherein the watermark payload value that corresponds to the smallest error count is identified as the extracted watermark payload value upon a determination that the smallest error count is below a predefined error tolerance value.

54. A device, comprising:
a receiver configured to receive a host content;
a processor implemented at least in-part in hardware and configured to obtain information indicative of a ranking of a plurality of watermark payload values, the information designating each watermark payload value within a first subset of the plurality of watermark payload values as having an associated value;
the processor further configured to, based at least in-part on the information indicative of the ranking, configure a watermark extractor component to prioritize resource allocation for extraction of payload values that are designated as belonging to the first subset over payload values that are not designated as belonging to the first subset, wherein:
the watermark extractor is configured to extract at least one payload value designated as belonging to the first subset from one or more watermarks embedded in the host content, wherein extraction of the payload value comprises:
comparison of a candidate watermark payload value obtained from the host content to a plurality of constructed error correction code watermark payload templates corresponding to each of the watermark payload values in the first subset,
production of a plurality of error counts, each error count representing a count of mismatched symbols between the candidate watermark payload value and a corresponding constructed error correction code watermark payload template, and
identification, as the extracted watermark payload value, a watermark payload value that corresponds to the smallest error count.

55. The device of claim 54, wherein the watermark payload value that corresponds to the smallest error count is identified as the extracted watermark payload value upon a determination that the smallest error count is below a predefined error tolerance value.