Source: http://www.google.com/patents/US7065226?dq=6,044,471
Timestamp: 2013-12-06 00:37:39
Document Index: 166595852

Matched Legal Cases: ['Application No. 11', 'art 110', 'art 111', 'art 101', 'art 112', 'art 101', 'art 111', 'art 113', 'art 114', 'art 104', 'art 112', 'art 111', 'art 114', 'art 103', 'art 102', 'art 101', 'art 111', 'art 112', 'art 104', 'art 114', 'art 114', 'art 103', 'art 112', 'art 104', 'art 113', 'art 113', 'art 101', 'art 310', 'art 311', 'art 301', 'art 312', 'art 313', 'art 312', 'art 114', 'art 303', 'art 311', 'art 303', 'art 303', 'art 304', 'art 311', 'art 312', 'art 312', 'art 305', 'art 311', 'art 304', 'art 302', 'art 301', 'art 311', 'art 304', 'art 312', 'art 305', 'art 304', 'art 304', 'art 305', 'art 304', 'art 304', 'art 313', 'art 313', 'art 301', 'Application No. 10']

Patent US7065226 - Method for embedding information and extracting the same - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Advanced Patent Search | Sign inAdvanced Patent SearchPatentsA method of embedding digital watermark information b1�bn (2≦n) in image data. The image data is divided into a plurality of areas S each consisting of M�N (1≦M, N) pixels. A plurality of areas G each consisting of P�Q (1≦P, Q) of the areas S are defined. Each of the areas S constituting each...http://www.google.com/patents/US7065226?utm_source=gb-gplus-sharePatent US7065226 - Method for embedding information and extracting the samePublication numberUS7065226 B1Publication typeGrantApplication numberUS 09/583,952Publication dateJun 20, 2006Filing dateMay 31, 2000Priority dateJun 1, 1999Fee statusPaidPublication number09583952, 583952, US 7065226 B1, US 7065226B1, US-B1-7065226, US7065226 B1, US7065226B1InventorsKousuke Anzai, Isao Echizen, Hiroshi Yoshiura, Shinobu EikawaOriginal AssigneeHitachi, Ltd.Patent Citations (6), Non-Patent Citations (4), Referenced by (10), Classifications (11), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetMethod for embedding information and extracting the sameUS 7065226 B1Abstract A method of embedding digital watermark information b1�bn (2≦n) in image data. The image data is divided into a plurality of areas S each consisting of M�N (1≦M, N) pixels. A plurality of areas G each consisting of P�Q (1≦P, Q) of the areas S are defined. Each of the areas S constituting each area G is allocated to some one of: areas T1�Tn in which said digital watermark information b1�bn is respectively embedded and areas H1�Hm (1≦m) in which information is not embedded. One or more areas T and one or more areas H are located in a predetermined arrangement in each area G. And, the plurality of areas G are located in a predetermined rule.
1. A method of embedding digital watermark information b1�bn (2≦n) in image data, comprising the steps of:
allocating each of the areas S constituting said area G to some one of: areas T1�Tn whose pixel values are changed, areas J1�Jk (1≦k) in which information p1�pk (1≦k) specifying an embedding format for embedding said digital watermark information b1�bn in said areas T1�Tn, and areas H1�Hm (1≦m) whose pixel values are not changed;
corresponding each of said T1�Tn, whose pixel values are changed, to each of said digital watermark information b1�bn and changing the pixel value of each area T according to a bit value;
locating areas T1�Tn, areas J1�Jk and areas H1�Hm in a predetermined same arrangement in said area G; and
said digital watermark information b1�bn is embedded by increasing or decreasing pixel data values in the corresponding areas T1�Tn according to a bit value (0, 1) of each bit of the digital watermark information b1�bn; and
said information p1�pk specifying said embedding format is embedded such that said information indicates a pattern of respective increasing/decreasing directions in the area T1�Tn for a bit value of the digital watermark information, in each area G to which the area J1�Jk embedded with said information p1�pk belong.
2. A method of extracting digital watermark information, for extracting the digital watermark information b1�bn (2≦n), a bit value of the digital watermark information being 0 or 1, from image data in which said digital watermark information is embedded, comprising steps of:
dividing the image data into a plurality of areas S each consisting of M�N (1≦M, N) pixels; detecting areas H1�Hm (1≦m) in which any of bit information 0 and 1 is not embedded, from said plurality of areas S;
recognizing a plurality of areas G each consisting of P�Q (1≦P, Q) of the areas S, said plurality of areas G being located on said image data, and said recognition being carried out by comparing locations of said detected areas H1�Hm on said image data and locations of predetermined areas H1�Hm in the areas S;
in each of the plurality of areas G recognized, extracting information p1�pk (1≦k) from areas J1�Jk in which said information p1�pk (1≦k) in which said information p1�pk (1≦k) should be embedded, said information p1�pk specifying an embedding format for embedding said digital watermark information b1�bn respectively in said areas T1�Tn;
recognizing the embedding format of the digital watermark information b1�bn in the areas T1�Tn in the areas G in question; and
extracting the digital watermark information b1�bn from the areas T1�Tn, according to the recognized embedding format,
for each of the plurality of groups G recognized, the information p1�pk embedded in the areas J1�Jk is extracted to recognize a pattern of increasing/decreasing directions of pixel data values for a bit value of the digital watermark information, in the area G in question; and
each bit value of the digital watermark information b1�bn embedded in the areas T1�Tn is detected according to the recognized pattern of increasing/decreasing directions.
3. A program product for making a computer execute a method of embedding digital watermark information b1�bn (2≦n) in image data, comprising:
codes for allocating each of the areas S constituting said area G to some one of: areas T1�Tn whose pixel values are changed, areas J1�Jk (1≦k) in which information p1�pk (1≦k) specifying an embedding format for embedding said digital watermark information b1�bn, a bit value of the digital watermark information being 0 or 1, in said areas T1�Tn, and areas H1�Hm (1≦m) whose pixel values are not changed;
codes for corresponding each of said T1�Tn whose pixel values are changed, to each of said digital watermark information b1�bn and changing the pixel value of each area T according to a bit value;
codes for locating one or more areas T1�Tn, and areas J1�Jk in a predetermined same arrangement in said area G;
codes for embedding said digital watermark information b1�bn by increasing or decreasing pixel data values in the corresponding areas T1�Tn according to a bit value (0, 1) of each bit of the digital watermark information b1�bn;
codes for embedding said information p1�pk specifying said embedding format such that said information indicates a pattern of respective increasing/decreasing directions in the areas T1�Tn for a bit value of the digital watermark information, in each area G to which the areas J1�Jk embedded with said information p1�pk belong; and
4. A program product for making a computer execute a method of extracting digital watermark information b1�bn (2≦n), a bit value of the digital watermark information being 0 or 1, from image data in which said digital watermark information is embedded, comprising:
codes for detecting areas H1�Hm (1≦m) in which any of bit information 0 and 1 is not embedded, from said plurality of areas S codes for recognizing a plurality of areas G each consisting of P�Q (1≦P, Q) of the areas S, said plurality of areas G being located on said image data, and said recognition being carried out by comparing locations of said detected areas H1�Hm on said image data and locations of predetermined areas H1�Hm in the areas S;
codes for extracting, in each of the plurality of areas G recognized, information p1�pk (1≦k) from areas J1�Jk in which said information p1�pk (1≦k) should be embedded, said information p1�pk specifying an embedding format for embedding said digital watermark information b1�bn respectively in said areas T1�Tn;
codes for recognizing the embedding format of the digital watermark information b1�bn in the areas T1�Tn in the area G in question;
codes for extracting the digital watermark information b1�bn from the areas T1�Tn according to the recognized embedding format;
codes for extracting, for each of the plurality of groups G recognized, the information p1�pk embedded in the areas J1�Jk to recognize a pattern of increasing/decreasing directions of pixel data values for a bit value of the digital watermark information, in the area G in question, and to detect each bit value of the digital watermark information b1�bn embedded in the areas T1�Tn according to the recognized pattern of increasing/decreasing directions; and
5. An apparatus for embedding digital watermark information b1�bn (2≦n) in image data, comprising:
a processing part for allocating each of the areas S constituting said area G to some one of: areas T1�Tn whose pixel values are changed, areas J1�Jk (1≦k) in which information p1�pk (1≦k) specifying an embedding format for embedding said digital watermark information b1�bn in said areas T1�Tn, and areas H1�Hm (1≦m) whose pixel values are not changed;
a processing part for corresponding each of said T1�Tn whose pixel values are changed, to each of said digital watermark information b1�bn and changing the pixel value of each area T according to a bit value;
a processing part for locating one or more areas T1�Tn, one or more areas J1�Jk and one or more areas H1�Hm in a predetermined same arrangement in said area G;
a processing part for embedding said digital watermark information b1�bn by increasing or decreasing pixel data values in the corresponding areas T1�Tn according to a bit value (0, 1) of each bit of the digital watermark information b1�bn; and
a processing part for embedding said information p1�pk specifying said embedding format such that said information indicates a pattern of respective increasing/decreasing directions in the area T1�Tn for a bit value of the digital watermark information, in each area G to which the areas J1�Jk embedded with said information p1�pk belong.
6. An apparatus for extracting digital watermark information b1�bn (2≦n), a bit value of the digital watermark information being 0 or 1, from image data in which said digital watermark information is embedded, comprising:
a processing part for detecting areas H1�Hm (1≦m) in which any of bit information 0 and 1 is not embedded, from said plurality of areas S;
a processing part for recognizing a plurality of areas G each consisting of P�Q (1≦P, Q) of the areas S, said plurality of areas G being located repeatedly over entire said image data, and said recognition being carried out by comparing locations of said detected areas H1�Hm on said image data and locations of predetermined areas H1�Hm in the areas S; a processing part for extracting, in each of the plurality of areas G recognized, information p1�pk (1≦k) from areas J1�Jk in which said information p1�pk (1≦k) should be embedded, said information p1�pk specifying an embedding format for embedding said digital watermark information b1�bn respectively in said areas T1�Tn;
a processing part for recognizing the embedding format of the digital watermark information b1�bn in the areas T1�Tn in the area G in question;
a processing part for extracting the digital watermark information b1�bn from the areas T1�Tn, according to the recognized embedding format; and
a processing part for extracting, for each of the plurality of groups G recognized, the information p1�pk embedded in the areas J1�Jk, to recognize a pattern of increasing/decreasing directions of pixel data values for a bit value of the digital watermark information, in the area G in question, and to detect each bit value of the digital watermark information b1�bn embedded in the areas T1�Tn, according to the recognized pattern of increasing/decreasing directions.
CROSS-REFERENCES TO RELATED APPLICATIONS This application claims priority from Japanese Patent Application No. 11-153672 filed on Jun. 1, 1999 and No. 11-75007 filed on Mar. 19, 1999, the entire contents of which are incorporated herein by reference for all purposes. This application relates to the U.S. patent application Ser. No. 09/388,447, filed on Sep. 2, 1999, which claims priority from Japanese Patent Applications No. 10-343119 filed on Dec. 2, 1998, No. 11-075006 filed on Mar. 19, 1999, and No. 11-153385 filed on Jun. 1, 1999.
BACKGROUND OF THE INVENTION The present invention relates to a technique of digital watermarking of digital data, in particular, multimedia data such as image data.
SUMMARY OF THE INVENTION According to the present invention, even if image data having digital watermark information has been subjected to the above-mentioned image processing, it is possible to specify positions in which the digital watermark information is embedded, in the image data in question.
The present invention provides a method of embedding digital watermark information, in which image data is divided into a plurality of areas S each consisting of M�N (1≦M, N) pixels, and each bit of digital watermark information b1�bn (2≦n) is embedded in at least one of the mentioned plurality of areas S, wherein:
the mentioned digital watermark information b1�bn is embedded in the image data such that:
a plurality of groups, each having a predetermined array consisting of areas T1�Tn in which the mentioned digital watermark information b1�bn is respectively embedded and areas H1�Hm (1≦m) in which information is not embedded, are located according to a predetermined rule; and
each of the mentioned areas S is allocated to some one of the mentioned areas T1�Tn and H1�Hm.
According to the above-described mode of the invention, the groups G each having the predetermined array consisting of the areas T1�Tn in which the digital watermark information b1�bn is respectively embedded and the areas H1�Hm (1≦m) in which information is not embedded, are located according to a predetermined rule, in such a manner that each of the areas S obtained by dividing the image data is necessarily allocated some one of the mentioned areas T1�Tn and H1�Hm.
Thus, even when image shift (i.e., processing of changing the origin in the X-Y coordinates for specifying a location of each pixel constituting the image data in question) is carried out on the image data in which the digital watermark information b1�bn is embedded in such a manner, and accordingly, the locations of the areas T1�Tn in which the digital watermark information is embedded are changed in the X-Y coordinates, it is possible to recognize each of the groups located on the image data by detecting the areas H1�Hm in which information is not embedded, in the areas S, and based on the values of X-Y coordinates of the detected areas H1�Hm on the image data. In each group, the areas T1�Tn in which digital watermark information b1�bn is respectively embedded and the areas H1�Hm in which the digital watermark information is not embedded are located in the predetermined arrangement. As a result, for each group, it is possible to specify the areas T1�Tn in which the digital watermark information b1�bn is respectively embedded.
Further, the present invention provides a method of embedding digital watermark information, in which image data is divided into a plurality of areas S each consisting of M�N (1≦M, N) pixels, and each bit of digital watermark information b1�bn (2≦n) is embedded in at least one of the mentioned areas S, wherein:
a plurality of groups, each having a predetermined array consisting of areas T1�Tn in which the mentioned digital watermark information b1�bn is respectively embedded, areas J1�Jk (1≦k) in which information p1�pk specifying an embedding format for embedding the digital watermark information b1�bn in said areas T1�Tn, and areas H1�Hm (1≦m) in which information is not embedded, are located according to a predetermined rule; and
each of the mentioned areas S is allocated to some one of the mentioned areas T1�Tn, J1�Jk, and H1�Hm; in embedding the mentioned digital watermark information b1�bn and the mentioned information p1�pk specifying the mentioned embedding format, in the image data.
According to the above-described mode of the present invention, the groups, each having the predetermined array consisting of the areas T1�Tn in which the digital watermark information b1�bn is respectively embedded, the areas J1�Jk in which the information p1�pk specifying the embedding format for the mentioned digital watermark information b1�bn in the mentioned areas T1�Tn is embedded, and the areas H1�Hm in which information is not embedded, are located according to the predetermined rule such that each of the areas S obtained by dividing the image data is necessarily allocated to some one of the mentioned areas T1�Tn, J1�Jk, and H1�Hm.
Thus, even when image shift is carried out on the image data in which the digital watermark information b1�bn is embedded in such a way, and accordingly, X-Y coordinate locations of the areas T1�Tn in which the digital watermark information b1�bn is embedded are changed, it is possible to recognize each of the groups located on the image data by dividing the image data on which this image shift has been carried out into a plurality of areas S and by detecting the areas H1�Hm in which information is not embedded from the areas S, and based on the X-Y coordinates values of the detected areas H1�Hm on the image data.
Further, in the present mode, for each group, the information p1�pk specifying the embedding format for the digital watermark information b1�bn in the areas T1�Tn is embedded in the areas J1�Jk. Accordingly, even when an embedding format for the digital watermark information b1�bn is changed for each group, it is possible to extract the digital watermark information b1�bn from the image data.
FIGS. 13A and 13B are flowcharts for explaining a difference in processing burdens between the case (FIG. 13A) in which the method of repeating the same transformation processing as the left-right reversal, scaling processing, and rotation processing that might have been carried out on image data until the digital watermark information b1�bn is extracted from the image data is applied to the transformation by image shift processing and the case (FIG. 13B) in which the mentioned method is combined with the extract method of the present embodiment;
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 17 is a view for explaining a method of embedding and extracting information in and from image data by a digital watermarking technique.
As shown in the figure, in information embedding processing, with respect to each bit bi (0≦i≦n) out of bits b1�bn constituting information that is desired to be embedded, brightness of each of pixels positioned in predetermined areas Q1�Qm in the image data is changed to increase by U when the bit in question is 1, and to decrease by U when it is 0. By carrying out this processing for every bit b1�bn while changing positions of the areas in which the bit in question is embedded, digital watermark information is embedded in the image data.
In processing of extracting the above-mentioned embedded digital watermark information, with respect to a bit bi (0≦i≦n) out of the bits b1�bn constituting the embedded information, an average brightness F of pixel data is obtained for each of the above-mentioned predetermined areas Q1�Qm of the image data, so as to obtain the sum total ΣF of these averages. Further, an average brightness R of pixel data is obtained for respective peripheral areas adjacent to the above-mentioned predetermined areas Q1�Qm, so as to obtain the sum total ΣR (Reference Value) of these averages. When ΣF−ΣR≧Th (where, Th differs depending on required error rates, and here it is assumed that Th=��U�m (m: the number of the areas Q in which bi is embedded)), then it is judged that bi=1. When, ΣF−ΣR≦−Th, then it is judged that bi=0. And, when −Th<ΣF−ΣR<Th, then it is judged that information is not embedded in the above-mentioned predetermined areas Q1�Qm. This processing is carried out for every bit b1�bn, so as to extract the digital watermark embedded in the image data.
Digital watermarking technique is described in detail in Proceedings of the 56th National Convention of IPSJ 1998, pages 3-37�3-38.
In FIG. 17, it is assumed that the origin O of the X-Y coordinates for specifying a position of each pixel constituting image data is set at the upper left vertex of the image data in question. Here, as shown in FIG. 18, when an upper portion of image data in which digital watermark information is embedded is cut, then, respective embedded positions in the X-Y coordinates of the bits b1�bn constituting the digital watermark information are changed.
The storage part 110 comprises: an image hold part 111 that holds image data inputted through the input-output part 101; a watermark information hold part 112 that holds digital watermark information b1�bn (2≦n) to be embedded in the image data inputted through the input-output part 101 and held in the image hold part 111; a watermarked image hold part 113 that holds image data in which the digital watermark information b1�bn is embedded; and a group array/location rule storage part 114 that stores a rule of embedding the digital watermark information b1�bn in the image data.
The information embedding part 104 embeds the digital watermark information b1�bn, which is held in the watermark information hold part 112, in the image data held in the image hold part 111, according to the group array/location rule stored in the group array/location rule storage part 114.
In detail, the digital watermark information b1�bn and information p that specifies embedding format are embedded in the image data as follows. Namely, groups G, each of which has a predetermined array, are located on the image data so as to cover all the image data. The mentioned array consists of: areas T1�Tn in which the digital watermark information b1�bn is respectively embedded; an area J in which the information p that specifies embedding format of the digital watermark information b1�bn in the areas T1�Tn is embedded; and an area H in which information is not embedded. And, a plurality of areas S obtained by division of the image data by the block dividing part 103 are each allocated to some one of the areas T1�Tn, J, and H, without fail.
Here, embedding of the digital watermark information b1�bn and the information p in the image data is carried out by increasing or decreasing brightness of the image data in the corresponding area by U, according to a value (0, 1) of a bit of the information, similarly to the conventional technique. However, in the present embodiment, as a pixel data brightness increasing/decreasing direction pattern depending on a bit value of information to be embedded, two kinds of patterns are prepared in order that extraction of information embedded in a certain area S of each group G is not affected by information embedded in the areas S located on the four sides of the area S in question. The information p is used for specifying this brightness increasing/decreasing direction pattern.
Here, the pixel data brightness increasing/decreasing direction pattern applied to each group G is set as follows. Namely, for example, in the case that the groups G each consisting of 3�3 (nine in total) areas S1�S9 are located to cover all the image data as shown in FIG. 3, there are prepared a first pattern in which pixel data brightness increasing/decreasing directions for a bit value are same for all the areas S1�S9 within a group G, and a second pattern in which pixel data brightness increasing/decreasing directions are opposite between vertically- or laterally-adjacent areas S, as shown in FIG. 4. Then, as shown in FIG. 5, the patterns are set on the image data so that mutually different brightness increasing/decreasing direction patterns are applied to vertically- or laterally-adjacent groups G.
Further, allocation of the areas T1�Tn, J, and H to the areas S within a group G is carried out so as to satisfy the following conditions.
The areas T1�Tn in which the digital watermark information b1�bn is embedded are necessarily allocated to the other areas S1�S9 than the areas to which the areas J and H have been allocated. In that case, it is desirable to note the following, in order that an error is not caused in the below-described detection of the area H in which information is not embedded.
In the example shown in FIGS. 4 and 5, when the areas T1�Tn, J, and H are allocated to the areas S1�S9 within a group G, for example, as shown in FIG. 6, the above-described conditions are satisfied.
FIG. 8 is a flowchart for explaining operation of the digital watermark information embedding apparatus 1 shown in FIG. 1. This flow is started when the control part 102 cooperates with the input-output part 101 to make image data and digital watermark information b1�bn held in the image hold part 111 and the watermark information hold part 112, respectively.
Next, as previously described referring to FIGS. 2�5, the information embedding part 104 establishes a brightness increasing/decreasing direction pattern (first pattern or second pattern) applied to each group G, according to the rule stored in the group array/location rule storage part 114 (Step S1002). Then, as previously described referring to FIG. 6, groups G are located one after another to cover all the image data, according to the rule stored in the group array/location rule storage part 114. Each of the groups G has a predetermined array consisting of the areas T1�Tn in which the digital watermark information b1�bn is embedded respectively, the area J in which the information p specifying brightness increasing/decreasing direction patterns is embedded; and the area H in which information is not embedded. And, the areas T1�Tn, J, and H are allocated to a plurality of areas S obtained by division of the image data by the block dividing part 103 such that each area S is necessarily allocated with some one of the areas T1�Tn, J, and H (Step S1003).
Next, when the processes of the above-described Steps S1004 and S1005 are carried out for all the digital watermark information b1�bn held in the watermark information hold part 112 (Step S1006), then the information embedding part 104 embeds the information p identifying the brightness increasing/decreasing direction pattern (first or second pattern) established in Step S1003 (Step S1007). Here, as described above, with respect to the embedding of the information p in the area J, the pixel data brightness increasing/decreasing direction for a bit value is same for all the brightness increasing/decreasing direction patterns.
When embedding of the information p in the area J of each group G is finished, namely, when embedding of the digital watermark information b1�bn and the information p, which specifies the embedding format of the digital watermark information for each group G, in the image data are finished, then the watermarked image hold part 113 is made to hold the processed image data, to finish the present flow. The image data held in this image hold part 113 is outputted as the watermarked image data through the input-output part 101, as the need arises.
The storage part 310 comprises: an image hold part 311 for holding image data in which digital watermark information b1�bn is embedded and which is inputted through the input-output part 301; a group array/location rule storage part 312 for storing a rule of extracting the digital watermark information b1�bn from the image data; and a watermark information hold part 313 for holding the digital watermark information b1�bn extracted from the image data. Here, the rule stored in the group array/location rule storage part 312 is same as the rule stored in the group array/location rule storage part 114 of the digital watermark information embedding apparatus 1 shown in FIG. 1.
The block dividing part 303 divides image data embedded with the digital watermark information b1�bn, which is held in the image hold part 311, into a plurality of areas S each consisting of M�N (1≦M, N) pixels in the same manner as the block dividing part 303 of the digital watermark information embedding apparatus 1 shown in FIG. 1. Here, the size (M�N) of the area S is set as the area S established in the block dividing part 303 of the digital watermark information embedding apparatus 1 shown in FIG. 1.
The group recognizing part 304 recognizes respective locations of a plurality of groups G located on the image data embedded with the digital watermark information b1�bn, which is held in the image hold part 311, according to the rule stored in the group array/location rule storage part 312. In detail, this is carried out in the following manner.
In detail, for example, the case that the temporary groups G′ each having the same size and shape as the group G consisting of 3�3 (nine in total) areas S1�S9 as shown in FIG. 3 are located to cover all the image data may be considered. In that case, with respect to the area Si (1≦i≦9), a brightness average F for pixel data within the area Si in question is obtained for each temporary group G′, and the total sum ΣF of these averages is obtained. Further, a brightness average R for pixel data in the adjacent areas located on the four sides of the area Si in question is obtained, and the total sum ΣR of these averages is obtained. Then, if the condition |ΣF−ΣR|≦Th (where Th differs depending on required error rates, and, for example, it is assumed that Th=��U�m (m: the number of the temporary groups G′ located on the image data)) is satisfied, it is judged that some information is embedded in the area Si in question. On the other hand, if the condition |ΣF−ΣR|<Th is satisfied, it is judged that information is not embedded in the area Si in question. This process is carried out for all the areas S1�S9 so as to detect the area in which information is not embedded.
Next, when the areas H in which information is not embedded are detected as described above, then a plurality of groups G, which are located on the image data and each have a predetermined array specified by the rule stored in the group array/location rule storage part 312, are recognized based on the locations of the areas H on the image data. That array consists of: the areas T1�Tn in which digital watermark information b1�bn is embedded respectively; the area J in which the information p specifying the image data brightness increasing/decreasing direction pattern is embedded; and the area H in which information is not embedded.
Now, for example as shown in FIG. 6, it is assumed that digital watermark information b1�b7 is embedded in image data such that groups G are located one after another so as to cover all the image data, each group G consisting of the areas T1�T7 in which digital watermark information b1�b7 is embedded respectively, the area J in which information p is embedded, and the area H in which information is not embedded, with those areas being allocated to 3�3 (nine in total) areas S in a predetermined array. Then, a case of an image shift caused by cutting this image data by upper one pixel line is considered.
In this case, the temporary groups G′ are allocated as shown in FIG. 10. In the present embodiment, when digital watermark information is embedded in the image data, the groups G are located one after another on the image data so as to cover all the image data, each group G consisting of the areas T1�T7 in which the digital watermark information b1�b7 is embedded respectively, the area J in which the information p is embedded, and the area H in which digital watermark information is not embedded, these areas being allocated to 3�3 (nine in total) areas S according to the predetermined array. Accordingly, each of the temporary groups G′ inevitably includes the area H in which information is not embedded.
The information extracting part 305 extracts the digital watermark information b1�bn from the image data embedded with the digital watermark information b1�bn, which is held in the image hold part 311, based on the respective locations of the groups G recognized by the group recognizing part 304.
The above process is carried out for all the areas T1�Tn so as to extract the digital watermark information b1�bn from the image data.
FIG. 12 is a flowchart for explaining operation of the digital watermark information extracting apparatus 3 shown in FIG. 9. This flow is started when the control part 302 cooperates with the input-output part 301 to make image data embedded with the digital watermark information b1�bn held in the image hold part 311.
Then, as previously described referring to FIG. 11, based on the locations of the detected areas H on the image data, the group recognizing part 304 recognizes a plurality of groups G that are located on the image data and each have the predetermined array specified by the rule stored in the group array/location rule storage part 312 (Step S3004). That array consists of: the areas T1�Tn in which digital watermark information b1�bn is embedded respectively; the area J in which the information p specifying the image data brightness increasing/decreasing direction pattern is embedded; and the area H in which information is not embedded.
Next, the information extracting part 305 notes an area Ti out of the areas T1�Tn in each group G recognized by the group recognizing part 304 (Step S3006).
Next, when the processes of Steps S3007�S3009 have been finished for all the groups G recognized by the group recognizing part 304 with respect to the area Ti noted in Step S3006 (Step S3010), then, the information extracting part 305 obtains the total sum Z of the differences obtained for all the groups G in Step S3009 with respect to the area Ti, and compares this total sum Z of these differences with the predetermined threshold W (which is set to (a threshold Th set slightly lower than U used for embedding the information)�(the number of the groups recognized by the group recognizing part 304)) (Step S3011). When the total sum Z is more than or equal to the threshold +W, then it is judged that the digital watermark information bi embedded in the area Ti of each group G is 1 (Step S3012). When the total sum Z is less than or equal to a threshold −W, then it is judged that the bit value of the digital watermark information bi is 0 (Step S3013). Here, when the total sum Z is less than the threshold +W and more than the threshold −W, then it means that the digital watermark information bi that should have been embedded in the area Ti is not embedded. In that case, it is possible that processing (for example, rotation processing or scaling processing) other than image shift has been carried out on the image data in which digital watermark information b1�bn has been embedded by the digital watermark information embedding apparatus 1 of the present embodiment. Accordingly, after carrying out error processing (Step S3014), the present flow is ended.
When the processes of Steps S3006�S3011 are finished for all the areas T1�Tn in which the digital watermark information is embedded (Step S3015), the information extracting part 304 makes the information hold part 313 hold the bit values of the digital watermark information b1�bn, and the present flow is ended. The information b1�bn held in this watermark information hold part 313 is outputted as the digital watermark information through the input-output part 301 as the need arises.
According to the present embodiment, groups G each having a predetermined array consisting of areas T1�Tn in which digital watermark information b1�bn is respectively embedded, an area J in which information p specifying an embedding format is embedded, and an area H in which information is not embedded, are located one after another to cover all the image data, and a plurality of areas S obtained by division of the image data are each allocated to some one of the areas T1�Tn, J, and H, so that the digital watermark information b1�bn and the information p are embedded in the image data.
Accordingly, even when image shifting processing is carried out on image data in which digital watermark information b1�bn is embedded as described above, and, as a result, X-Y coordinate locations of the area T1�Tn in which the digital watermark information b1�bn is embedded are changed, it is possible to recognize each of the groups G located on the image data in question, as follows. Namely, by dividing the image data, on which the image shifting processing has been carried out, into a plurality of areas S, and by detecting the areas H, in which information is not embedded, out of these areas S, it is possible to recognize each of the groups G located on the image data in question, based on the X-Y coordinates of the detected areas H in the image data.
Particularly, in the present embodiment, temporary groups G′ (each having the same shape and size as the group G used in embedding the digital watermark information) are located on the image data (in which the digital watermark information b1�bn has been embedded) according to the location rule employed for those groups G in embedding the digital watermark information. Next, by examining the areas S for each of the groups G′ located one after another on the image data as described, the area H in which information is not embedded is detected. Then, each of the groups G located on the image data in question is recognized based on the X-Y coordinate value of the detected area H in the image data, and thereby, the areas T1�Tn in which the digital watermark information b1�bn has been embedded are detected on the image data.
Namely, according to the present embodiment, in specifying the detected positions of the areas T1�Tn on the image data in which the digital watermark information b1�bn is embedded, it is sufficient to calculate a difference |ΣF−ΣR|, a number of times corresponding to the number of the areas S contained in each temporary group G′ so as to examine if information is embedded or not. As a result, determination of the detected locations of the areas T1�Tn on the image data in which the digital watermark information b1�bn is embedded can be carried out at high speed. This effect is particularly remarkable in the case that, when processing (for example, rotation processing and scaling processing) other than image shift is carried out on the image data in which digital watermark information b1�bn has been embedded, the digital watermark extracting apparatus is so constructed that it can specify the detected locations of the areas T1�Tn on the image data taking such processing into consideration.
The present inventors already invented and filed an application for a patent (Japanese Patent Application No. 10-343119, U.S. Ser. No. 09/388,447 filed on Sep. 2, 1999) on a method of extracting digital watermark information b1�bn from the image data that has been subjected to reversible geometric transformation (transformation for which the original image data before the transformation can be recovered) after the digital watermark information b1�bn was embedded. This method is carried out by repeating a process of investigating embedded locations in the X-Y coordinates (determined in advance with a person who embeds the information in the image data) in the image data for each of the digital watermark information b1�bn while carrying out the same transformation processing on the image data as the left-right reversal, scaling processing, and rotation processing that might have been carried out on the image data in question, until the corresponding digital watermark information b1�bn is detected from all the embedded locations.
This method can be applied to the image shift processing. Namely, by repeating a process of changing the origin of the image data in the X-Y coordinates while carrying out the process in combination with the above-mentioned transformation processing, it is also possible to extract the digital watermark information b1�bn from the image data on which the reversible geometric transformation and image shift processing have been carried out after embedding of the digital watermark information b1�bn. However, in that case, the number of times of search for specifying the detected location of each of the digital watermark information b1�bn increases extremely and a burden on the processing increases rapidly.
FIGS. 13A and 13B show flowcharts for explaining the difference in processing burdens between the cases of FIGS. 13A and 13B. In the case of FIG. 13A, the method of repeating the same transformation processing as the left-right reversal, scaling processing, and rotation processing that might have been carried out on the image data until the digital watermark information b1�bn is extracted is applied to the transformation by image shift processing. In the case of FIG. 13B, the mentioned method is combined with the extract method of the present embodiment.
In FIG. 13A, when rotating processing (S5002) on the image data is carried out up to 360 degrees, increasing by 1 degree, and scaling processing (S5003) is carried out in the range of the magnification ratio of 0.5�2.0 at intervals of 0.1, then the number of search for extracting the digital watermark information b1�bn required for combination of left-right reversal (S5001), rotating processing (S5002), and scaling processing (S5003) becomes 2 (for left-right reversal)�360 (for rotation processing)�21 (for scaling processing)=15,120, at most. When, image shift processing (S5004) is carried out in addition, the number of search increases rapidly. Namely, the number of pixels constituting the image data is enormous, and the location of the origin O in the X-Y coordinates required for specifying each pixel data is not always located on the image data (for example, as shown in FIG. 18, it is possible that, when a part of the image data is cut, the origin O in the original data before the cut is located in the cut part). As a result the number of search for the location of the origin O in the X-Y coordinates becomes enormous. The above-mentioned number of search 15,120 is multiplied by this number, and thus the number of times for carrying out the routine (S5006�S5009) of the flow becomes enormous.
As described above, the present embodiment is particularly effective for the case that, when geometric transformation processing other than image shift is carried out on image data in which digital watermark information b1�bn is embedded, the digital watermark extracting apparatus is constructed such that detected location of the areas T1�Tn on the image data can be specified taking such processing into consideration.
Further, in the present embodiment, as the brightness increasing/decreasing direction patterns applied to each group G in embedding digital watermark information in image data, the case in which the two patterns as shown in FIG. 4 are employed has been described. However, three or more patterns may be used. In that case, information p1�pk (k depends on the number of the patterns) specifying those three or more patters may be allocated in the areas of each group G. Further, any combination of patterns may be employed as long as the difference between the total sum ΣF of the pixel data brightness averages F with respect to the area H in which information is not embedded for every groups G and the total sum ΣR of the pixel data brightness average R with respect to the adjacent areas located on the four sides of the area in question for every group G is not affected by increase or decrease of brightness owing to the information embedded in these adjacent areas. Further, when the area H in which information is not embedded can be detected in some way without being affected by information embedded in those adjacent areas located on the four sides of the area H in question, then one kind of pattern may be used. In that case, the area J in which the information p is embedded becomes unnecessary. Further, in that case, extraction of digital watermark information from image data is carried out as follows. Namely, for example, with respect to an area Ti (1≦i≦n) adjacent to the area H in which information is not embedded, a difference F−R between an average brightness F for pixel data in the area in question and an average brightness R for pixel data in the area H in which information is not embedded is obtained for each group G. Then, the total sum Σ(F−R) of the obtained differences F−R is compared with a threshold, in order to judge the bit value of the information embedded in the mentioned area Ti. Next, with respect to an area Tj (1≦j≦, j≠i) adjacent to the area Ti whose bit value of the embedded information has been judged, a difference F−R′ between an average brightness F for pixel data in the area Tj in question and a value R′ obtained by subtracting the brightness increase or decrease according to the bit value of the information embedded in the area Ti from the average brightness R for the pixel data in the area Ti is obtained for each group G. Then, the total sum Σ(F−R′) of the obtained differences F−R′ is compared with a threshold in order to judge the bit value of the information embedded in the mentioned area Tj. When the digital watermark information b1�bn is extracted from the image data by carrying out this process for all the areas T1�Tn in which the digital watermark information b1�bn is embedded, then the bit value of the information embedded in the area Ti can be judged with accuracy without being affected by the information embedded in the areas adjacent to the area Ti.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5721788 *Jul 31, 1992Feb 24, 1998Corbis CorporationMethod and system for digital image signaturesUS6072888 *May 24, 1999Jun 6, 2000Digimarc CorporationMethod for image encodingUS6285774 *Jun 8, 1998Sep 4, 2001Digital Video Express, L.P.System and methodology for tracing to a source of unauthorized copying of prerecorded proprietary material, such as moviesUS6341350 *Sep 1, 1998Jan 22, 2002Sony CorporationDevice and method for processing image data, transmitting medium, and recording mediumUS6510233 *May 3, 1999Jan 21, 2003Nec CorporationElectronic watermark insertion deviceJPH07290767A Title not available* Cited by examinerNon-Patent CitationsReference1"Data Hiding Based on Neighbor Statistics", Seiji Kobayashi, et al, Proceedings of the 56<SUP>th </SUP>Nation Convention of Information Processing Society of Japan, 3-37 to 3-38.2 *Jana, Robust MPEG Video Watermarking Technologies, ACM Multimedia'98, UK, ACM 1-58113-036-8/98/0008.3 *Michell, Multimedia Data-Embedding and Watermarking Technologies, Proceeding of the I.E.E.E., vol. 86, No. 6, Jun. 1988.4 *Rakesh Dugad et al. "A New Wavelet-Based Schem for Watermarking Images". I.E.E.E. Image Processing, 1998. vol. 2, pp. 419-423.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS7330561 *Nov 19, 2003Feb 12, 2008Eastman Kodak CompanyOptimal templates for image data embeddingUS7408680 *Sep 20, 2002Aug 5, 2008Canon Kabushiki KaishaImage processing apparatus and methodUS7508944 *Jun 2, 2000Mar 24, 2009Digimarc CorporationUsing classification techniques in digital watermarkingUS7720250 *May 23, 2006May 18, 2010George Mason UniversityMethod and apparatus for watermarking stream dataUS7756289 *Mar 22, 2006Jul 13, 2010Ancestry.Com Operations Inc.Image watermarking systems and methodsUS7958365Mar 20, 2009Jun 7, 2011Digimarc CorporationUsing classification techniques in digital watermarkingUS8270033 *Feb 20, 2008Sep 18, 2012Konica Minolta Business Technologies, Inc.Generating embed-image by dividing embed-information into blocks and generating an information pattern and positioning patternUS8363890 *Sep 30, 2010Jan 29, 2013Fuji Xerox Co., Ltd.Image processing apparatus, image processing method and non-transitory computer-readable mediumUS20110206233 *Sep 30, 2010Aug 25, 2011Fuji Xerox Co., Ltd.Image processing apparatus, image processing method and non-transitory computer-readable mediumWO2008002103A1 *Jun 29, 2007Jan 3, 2008Han Kil PyoWatermarking method, watermark checking method, watermarking device, and watermark checking device* Cited by examinerClassifications U.S. Classification382/100, 382/232International ClassificationG06T1/00, G06F12/14, G06F21/24, G06K9/00, G06K9/36, H04N1/387Cooperative ClassificationG06T2201/0061, G06T1/0064, G06T2201/0051Legal EventsDateCodeEventDescriptionNov 16, 2009FPAYFee paymentYear of fee payment: 4May 31, 2000ASAssignmentOwner name: HITACHI, LTD, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:ANZAI, KOUSUKE;ECHIZEN, ISAO;EIKAWA, SHINOBU;AND OTHERS;REEL/FRAME:010838/0937;SIGNING DATES FROM 20000421 TO 20000509RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google