Watermarks for customer identification
First Claim
1. A digital watermarking method, comprising the steps of:
- forming a first collection of masks;
forming a second collection of masks, each mask in said second collection being different from said masks in said first collection;
assigning to each of a plurality of customers Ci a plurality of pairs of masks (M(K(I,j,
1)), M(K(I,j,
2))), each pair of masks assigned per customer corresponding to a different one of a plurality of digital images Ij offered for use by a vendor, the first mask M(K(I,j,
1) in each pair being derived from said first collection and the second mask M(K(I,j,
2) in each pair being derived from said second collection;
accepting a request to use one of said digital images from one of said customers; and
encoding into said digital image requested for use by said one of said customers the pair of masks assigned to said one of said customers in said assigning step which corresponds to the requested digital image, wherein said pair of masks are used to perform a recognition among said plurality of customers so that at most the number of comparative computations is no more than two times the square root of a number of said plurality of customers.
1 Assignment
0 Petitions
Accused Products
Abstract
A digital watermarking method encodes different pairs of watermarks into each of a plurality of images offered for use by a vendor. The watermarks in each pair are derived from two separate collections of watermarks and sufficiently different so as to prevent false positives. Because each pair of watermarks is assigned to a different customer relative to a particular image, unauthorized use of a digital image sold to a customer may be determined by locating the associated pair of watermarks assigned to the customer in the image. Collusion detection is also realized by forming each pair of masks from sub-collections of masks which are detectable in an image formed by combining the same images sold to one or more customers.
78 Citations
20 Claims
-
1. A digital watermarking method, comprising the steps of:
-
forming a first collection of masks;
forming a second collection of masks, each mask in said second collection being different from said masks in said first collection;
assigning to each of a plurality of customers Ci a plurality of pairs of masks (M(K(I,j,
1)), M(K(I,j,
2))), each pair of masks assigned per customer corresponding to a different one of a plurality of digital images Ij offered for use by a vendor, the first mask M(K(I,j,
1) in each pair being derived from said first collection and the second mask M(K(I,j,
2) in each pair being derived from said second collection;
accepting a request to use one of said digital images from one of said customers; and
encoding into said digital image requested for use by said one of said customers the pair of masks assigned to said one of said customers in said assigning step which corresponds to the requested digital image, wherein said pair of masks are used to perform a recognition among said plurality of customers so that at most the number of comparative computations is no more than two times the square root of a number of said plurality of customers. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
obtaining a digital image suspected of being an unauthorized version of the requested digital image;
comparing the masks in said first collection to said suspected digital image on a mask-by-mask basis;
identifying a mask in said first collection which is found in the suspected mask;
comparing the masks in said second collection to said suspected digital image on a mask-by-mask basis;
identifying a mask in said second collection which is found in the suspected mask;
forming the mask identified in said first collection and the mask identified in the second collection into a pair of identified masks;
determining which of said plurality of customers was assigned to said pair of identified masks for the requested digital image; and
identifying the customer assigned to said pair of identified masks for the requested digital image as one responsible for the unauthorized version of the requested digital image.
-
-
3. The method of claim 1, wherein said steps of forming said first collection and said second collection include:
-
a) defining at least one initial mask in a temporary collection;
b) generating a tentative mask as a possible mask to be added to said temporary collection;
c) comparing the tentative mask to the masks already in said temporary collection;
d) rejecting the tentative mask if a predetermined correspondence exists between the tentative mask and any of the masks in said temporary collection;
e) adding the tentative mask to said temporary collection if said predetermined correspondence does not exist;
f) repeating steps b)-e) until a desired number of masks are included in said temporary collection; and
g) dividing the desired number of masks in said temporary collection into two groups corresponding, respectively, to said first collection and said second collection.
-
-
4. The method of claim 3, wherein said predetermined correspondence equals a relationship wherein less than one third of values in the tentative mask are different from values in any of the masks in said temporary collection.
-
5. The method of claim 3, wherein step b) includes:
-
randomly generating an array of zeros and ones; and
generating said tentative mask from said array.
-
-
6. The method of claim 3, wherein said first collection and said second collection contain a same number of masks.
-
7. The method of claim 2, wherein said first collection of masks and said second collection of masks are disjoint collections having a same number (Elem) of masks, and wherein at most 2×
- (Elem) comparisons are performed in order to determine which of said plurality of customers was assigned to said pair of identified masks for the requested digital image.
-
8. The method of claim 7, wherein said comparison comprises a step of detecting whether a watermark generated from a mask is embedded in said digital image.
-
9. A digital watermarking method, comprising the steps of:
-
forming a first collection of masks;
forming a second collection of masks, each mask in said second collection being different from said masks in said first collection; and
encoding a pair of masks into a digital image to form an authorized digital image, a first mask of said pair derived from said first collection and a second mask of said pair derived from a second collection, wherein said pair of masks are used to perform a recognition among said plurality of customers that at most the number of comparative computations is no more than two times the square root of a number of said plurality of customers. - View Dependent Claims (10, 11, 12)
associating said first mask and said second mask with one of a plurality of customers for said digital image;
obtaining a digital image suspected of being an unauthorized version of said authorized digital image;
locating said first mask and said second mask in said unauthorized digital image; and
identifying the customer assigned to said first mask and said second mask as one who distributed the unauthorized version of said authorized digital image.
-
-
11. The method of claim 9, wherein said steps of forming said first collection and said second collection include:
-
a) defining at least one initial mask in a temporary collection;
b) generating a tentative mask as a possible mask to be added to said temporary collection;
c) comparing the tentative mask to the masks already in said temporary collection;
d) rejecting the tentative mask if a predetermined correspondence exists between the tentative mask and any of the masks in said temporary collection;
e) adding the tentative mask to said temporary collection if said predetermined correspondence does not exist;
f) repeating steps b)-e) until a desired number of masks are included in said temporary collection; and
g) dividing the desired number of masks in said temporary collection into two groups corresponding, respectively, to said first collection and said second collection.
-
-
12. The method of claim 11, wherein said predetermined correspondence equals a relationship wherein less than one third of values in the tentative mask are different from values in any of the masks in said temporary collection.
-
13. A method for detecting when unauthorized digital images have been formed as a result of collusion between customers of a digital image vendor, comprising the steps of:
-
forming a first collection of masks, said first collection including a sub-collection of a first type and a sub-collection of a second type;
forming a second collection of masks, said second collection including a sub-collection of a first type and a sub-collection of a second type, each mask in said second collection being different from said masks in said first collection;
assigning to each of a plurality of customers Ci a plurality of pairs of masks (M(K(I,j,
1)), M(K(I,j,
2))), each pair of masks assigned per customer corresponding to a different one of a plurality of digital images Ij offered for use by a vendor, the first mask M(K(I,j,
1) in each pair being derived from said first collection and the second mask M(K(I,j,
2) in each pair being derived from said second collection, the first mask and the second mask in each pair either both being of said first type or both being of said second type, wherein said pair of masks will be used to perform a recognition among said plurality of customers so that at most the number of comparative computations is no more than two times the square root of a number of said plurality of customers;
accepting a request to use one of said digital images from one of said customers; and
encoding into said digital image requested for use by said one of said customers the pair of masks assigned to said one of said customers in said assigning step which corresponds to the requested digital image. - View Dependent Claims (14, 15)
a) defining at least one initial mask in a temporary collection;
b) choosing a plurality of patterns for said digital images, each of said patterns be chosen for a subset of pixels in a respective one of said digital images;
c) generating a first tentative mask as a possible mask to be added to said temporary collection;
d) modifying said first tentative mask to carry one of said patterns Pat(j) for a subset Sj of pixels (h,v) within digital image Ij e) generating a second tentative mask, said second tentative mask being same as said first tentative mask except that said second tentative mask carries a pattern which is an inversion Pat'"'"'(j) of the pattern Pat(j) carried by the first tentative mask;
f) comparing the first tentative mask and the second tentative mask to the masks already in said temporary collection;
g) rejecting the first tentative mask and the second tentative mask if a predetermined correspondence exists between at least one of the first tentative mask and the second tentative mask and any of the masks in said temporary collection;
h) adding the first tentative mask and the second tentative mask to said temporary collection if said predetermined correspondence does not exist between both the first tentative mask and the second tentative mask and any of the masks in said temporary collection;
f) repeating steps c)-h) until a desired number of masks are included in said temporary collection; and
g) dividing the desired number of masks in said temporary collection into two groups corresponding, respectively, to said first collection and said second collection, wherein the sub-collection of said first type in said first collection and said second collection includes masks which carry patterns Pat(j) and the sub-collection of the second type includes masks which carry patterns Pat′
(j).
-
-
15. The method of claim 14, further comprising the steps of:
-
constructing one of the following symbolic sequences s1(j,Ci) for each of said plurality of customers;
s1(j, Ci)=0 if Ci has not bought image Ij, s1(j, Ci)=1 if Image Ij sold to Ci has watermarks of type A, and s1(j, Ci)=2 if Image Ij sold to Ci has watermarks of type B;
computing an output Sj for all possible pairs of said plurality of customers based on the symbolic sequences assigned to said customers in said constructing step;
obtaining a digital image suspected of being an unauthorized version of the requested digital image;
comparing the output Sj for all of said possible pairs of customers as determined in said computing step to said suspected digital image; and
identifying which two of said customers colluded to produce said unauthorized version of the requested digital image based on an outcome of said comparing step.
-
-
16. A method for detecting when unauthorized digital images have been formed as a result of collusion between customers of a digital image vendor, comprising the steps of:
-
forming a pair of masks where each mask (M) is a two-dimensional concatenation of two smaller masks, a second one of said smaller masks (Ms′
) being an inversion of a first one of said smaller masks (Ms), said first mask corresponding to a first letter of an alphabet and said second mask corresponding to a second letter of said alphabet, with said pair of masks (M) being a pair of code words written in said first and second letters;
assigning said pair of masks (M) to a customer Ci;
accepting a request from said customer Ci to use one of said digital images, encoding said pair of masks (M) into said digital image;
obtaining a digital image suspected of being an unauthorized version of said authorized digital image;
locating said pair of code words corresponding to said pair of masks (M) in said unauthorized digital image; and
identifying the customer assigned to said pair of masks having said pair of code words as one who distributed the unauthorized version of said authorized digital image.
-
-
17. A watermark detection method, comprising the steps of:
-
forming n collections of pairs of watermarks;
forming a set of n pairs of watermarks W(I) for a customer, said n pairs of watermarks in said set being chosen one from each said n collections of pairs of watermarks, respectively;
encoding a different one of said pair of watermarks from said set of pairs into a respective plurality of images;
authorizing said customer to use said plurality of images;
obtaining a group of images suspected of being unauthorized versions of said plurality of images;
analyzing watermarks in a predetermined number of said unauthorized versions of said plurality of images; and
identifying said group of images as being derived from said customer when, in said analyzing step, watermarks in said predetermined number of said unauthorized versions of said images are determined to belong to said customer.
-
-
18. A method for detecting when unauthorized digital images have been formed as a result of collusion between customers of a digital image vendor, comprising the steps of:
-
forming n collections of pairs of watermarks, where n is less than a number of customers of said vendor;
randomly choosing pairs of watermarks from said n collections of pairs of watermarks;
encoding said randomly chosen pairs of watermarks into respective ones of a plurality of images;
authorizing at least two customers to use said plurality of images, at least a portion of said images used by said two customers being encoded with a common pair of watermark;
obtaining a group of images suspected of being unauthorized versions of said plurality of images;
analyzing said group of images to determine which images in said group have said common pair of watermarks; and
identifying said two customers as ones who colluded to produce said unauthorized versions of said plurality of digital images as a result of said common pair of watermarks being found in said group of images.
-
-
19. A computer program product for use with a computer, comprising:
-
a computer readable medium with a computer program recorded thereon, the program including;
first code means for causing the computer to form a first collection of masks;
second code means for causing the computer to form a second collection of masks, each mask in said second collection being different from said masks in said second collection;
third code means for causing the computer to assign to each of a plurality of customers Ci a plurality of pairs of masks (M(K(I,j,
1)), M(K(I,j,
2))), each pair of masks assigned per customer corresponding to a different one of a plurality of digital images Ij offered for use by a vendor, the first mask M(K(I,j,
1) in each pair being derived from said first collection and the second mask M(K(I,j,
2) in each pair being derived from said second collection; and
fourth code means for causing the computer to encode into a digital image requested for use by said one of said customers the pair of masks assigned to said one of said customers by said third code means which corresponds to the requested digital image, wherein said pair of masks are used to perform a recognition among said plurality of customers so that at most the number of comparative computations is no more than two times the square root of a number of said plurality of customers. - View Dependent Claims (20)
fifth code means for causing the computer to compare the masks in said first collection to a suspected digital image on a mask-by-mask basis;
sixth code means for causing the computer to identify a mask in said first collection which is found in the suspected mask;
seventh code means for causing the computer to compare the masks in said second collection to said suspected digital image on a mask-by-mask basis;
eighth code means for causing the computer to identify a mask in said second collection which is found in the suspected mask;
ninth code means for causing the computer to form the mask identified in said first collection and the mask identified in the second collection into a pair of identified masks;
tenth code means for causing the computer to determine which of said plurality of customers was assigned to said pair of identified masks for the requested digital image; and
eleventh code means for causing the computer to identify the customer assigned to said pair of identified masks for the requested digital image as one responsible for the unauthorized version of the requested digital image.
-
Specification