JP7207627B2 - High-tolerance digital watermarking method - Google Patents

Description

The present invention is an electronic watermarking method for embedding watermark information such as copyright information in digital image data. It relates to the watermarking method.

In today's digital information society, information can be easily duplicated and information can be shared by many people, and society has developed greatly. However, this convenience has also caused incidents such as copyright infringement due to the illegal duplication and distribution of other people's works. In the case of images, the high image quality of digital cameras and printers in recent years has made it possible to easily obtain exact reproductions of original images. It is a result of encouraging vicious criminal acts called acts.

In such a situation, invisible digital watermark technology embeds other information, such as author information, in image information to protect copyright or warn against illegal duplication. has developed. For example, for the purpose of copyright protection, this digital watermarking technology not only embeds the copyright owner, URL, contact information, terms of use, etc. , and in case of unauthorized use, it is possible to trace it. In this way, electronic watermarks are beginning to be widely used as security measures such as copyright management/protection and unauthorized copying monitoring.

The electronic watermark as a security measure must be robust and highly durable so that it cannot be lost or removed easily. This is because if the watermark information can be removed or erased by editing the image or by a simple operation, it can be used illegally and escaped from tracking and surveillance.

Typically, to enhance robustness, a digital watermark needs to be embedded deep into the image data. Therefore, the embedding strength (gain) is increased for embedding. This increases damage to the original image, resulting in deterioration of image quality. In other words, image quality and durability are in a trade-off relationship, and it is usually difficult to satisfy both.

As a digital watermarking method that satisfies image quality and durability at the same time, we have proposed a method of embedding a green noise pattern in image data (hereinafter referred to as a green noise diffusion method), which is shown in Patent Documents 1 to 6 and Non-Patent Documents 1 to 2. rice field. The green noise pattern has its spectrum confined to a specific band fmax to fmin, and its main frequency can be set to a frequency band that is difficult to recognize by human visual characteristics. For this reason, when used for digital watermarking, when the embedded image is observed at a distance of clear vision, the dot pattern exhibits low responsiveness and artifacts are difficult to recognize. In addition, since it has high response sensitivity in writing and reading with printers and scanners, embedded information can be retained even after printing. In order to increase reliability, even if the embedding strength (gain) is increased, artifacts are less visible and high image quality is maintained.

Like the spread spectrum method, the green noise diffusion method is robust against editing and processing, but it must also be robust against removal of watermark information for unauthorized use by a third party. A third party analyzes, estimates, and attacks the embedding algorithm using various methods, various images, and various information (hereafter referred to as collusion attacks), thereby removing the watermark information from the embedded image and returning it to the original image. , makes unauthorized use possible. Algorithmic open watermarking makes it easy to reverse analyze the signal processing by knowing the algorithm and is therefore vulnerable to attacks. Embedding parameters are usually held in the form of a "key". This key usually uses various parameters such as position information of pixels to be embedded, strength (gain information), random number sequence, hash function password, etc. Without the key information, the watermark cannot be removed. A collusion attack involves guessing this key information.

In the form of steganography, secret information is secretly embedded in the image so that the watermark cannot be extracted without a key. For this reason, the algorithm is private. However, in the digital watermarking method for copyright protection, it is necessary for any user to be able to know the presence or absence of copyright information and conditions, etc., and it is necessary for anyone to be able to easily extract watermarks. . In addition, in order to spread widely, it is necessary to standardize it as a unified method in the industry, and it is desirable that the algorithm can be published.

At this time, in order to ensure security even if the algorithm is made public, an asymmetric digital watermarking method is generally considered desirable. This is because the symmetric type extracts watermarks in the reverse order of embedding, so the location and method of embedding can easily be discovered and attacked.
The green noise diffusion method is an asymmetric type in which the embedding is performed in real space and the extraction is performed in spectral space, and because the green noise pattern is a pattern in which random dots are diffused, it is generally difficult to completely remove it in the same way as spread spectrum. . Even if the algorithm is made public, the various embedded parameters are passed to the recipient as confidential information in the form of a "private key." Confidentiality is aggregated into this key, security is guaranteed, and normally watermark removal cannot be performed without this key.

Furthermore, since parameters such as an embedding pattern are changed for each image, the key information is different for each image. Therefore, even if the key is lost or stolen, the key cannot be used to manipulate other images to remove the watermark.

In addition, countermeasures against the above-mentioned collusion attacks are necessary. In a collusion attack, the key information is determined by taking the difference from the original image without a key, decoding the embedding parameters and patterns from images with many flat parts, and embedding features and image correlations from multiple images. . Therefore, countermeasures against such attacks are required. Such collusion attacks from third parties are becoming possible to estimate key information by learning various patterns using machine learning using recent AI technology. In particular, in the block-type digital watermarking method, since watermark information is embedded in each block, as many pieces of learning data as the number of blocks are prepared from one image, embedding parameters can be easily estimated.

For this reason, Patent Document 5 proposes a method of increasing the number of green noise patterns to be embedded by using inverted patterns, and inserting the selection of a plurality of patterns into key information as a random number sequence for bit information (0, 1) to be embedded. bottom. The multiple patterns consisted of the spatially inverted pattern of the original pattern and the inverted pattern of the luminance data (negative/positive pattern), and eight inverted patterns were generated for one green noise pattern. As a result, the number and types of patterns are increased, the risk of the same pattern appearing repeatedly is reduced, and safety is improved.

However, with only the inverted pattern, there is no pattern phase (spatial position information shift amount) and the phase is always the same, so it is possible to identify the pattern from a lot of pattern embedding information, and it is still completely safe. Absent.

JP 2018-182471 JP 2018-201134 JP 2018-207247 Patent application 2017-117460 Patent application 2018-216362 Patent application 2019-000178

N.Kawamura;”Digital Halftoning by Clustered Dither Screen Masks Representing Green-noise Characteristics”, Proceeding of the 1st ICAI 2015, T109-3, pp.708-711 (2015). N.Kawamura;”Digital Halftoning by Stochastic Dither Screen Mask Representing Green to Blue Noise Characteristics”, Trans. on IEVC, Vol.5, No.1, pp.34-41 (2017).

Therefore, it is a challenge to obtain a digital watermarking method that maintains high image quality and resistance to editing and processing, and is sufficiently robust against collusion attacks. That is, in the algorithm public type digital watermarking method, it is a problem to obtain a digital watermarking method that exhibits strong resistance such that a third party cannot determine the embedding pattern by analyzing the embedding pattern without a key.

In order to solve the above problems, the present invention provides a digital watermarking method in which an image is divided into blocks and watermark information is embedded in each block. embedded by shifting or varying the phase of

That is, in the digital watermarking method in which image data I(x,y) is divided into R×R blocks and different patterns corresponding to watermark information bits are embedded in each block, the embedding patterns are a plurality of different basic patterns exhibiting green noise characteristics. The pattern Pi(x,y) is shifted by x0 in the x direction and y0 in the y direction using a different phase shift amount (x0,y0) (where 0≤x0,y0<R) for each block. , P'i(x,y) = Pi((x+x0) mod R, (y+y0) mod R) (where P'i(x,y) is the shifted pattern and mod R is (R modulo R), and the watermark embedding is W(x,y)=I(x,y)+gain・P 'i(x, y) (here, gain is the embedding strength) The phase shift amount (x0, y0) is generated by a random number generator and obtained from the phase shift list L(n) (n is the block number ), and the basic pattern Pi(x,y), the embedding strength (gain), and the phase shift list L(n) are stored as keys. The embedded bit information is extracted from the shape of the Fourier spectrum pattern of each block. The same extraction software can be used regardless of the phase shift amount. ,y) is removed by the operation I(x,y)=W(x,y)-gain・P'i(x,y) using the key to return to the original image and new information It is characterized by being embeddable .

Such a phase-shifted pattern P'i(x,y) is based on the basic pattern Pi(x,y) of R×R, by (x0,y0) (where 0≦x0,y0<R) Although the amount of shift (x0, y0) is different for each block, the shape of the Fourier spectrum pattern of the watermark-embedded block shows the same spectrum shape regardless of the amount of phase shift. Extraction of watermark information does not require a change in the extraction software accompanying a change in this phase shift amount, and the watermark is removed using this key only when removing the watermark. By doing so, it is possible to make it difficult to estimate patterns from collusion attacks.

The embedding pattern Pi(x,y) is a green noise pattern generated from different initial values for each image, and the shift list L( n ) is composed of different shift sequences for each image, and Unable to remove watermarks on other images with a key.

According to the present invention, it is possible to obtain a secure digital watermark that has high resistance to editing processing and resistance to collusion attacks from a third party, is robust, and cannot be removed without a key.

Also, the original image can be restored with a key. This saves the purchaser of the image the trouble of having the original image delivered directly from the distributor, and since the original image is not distributed, there is no need to worry about leaks or theft, and it is safe in terms of security. highly sexual. Furthermore, the purchaser can use the key to embed the copyright information as the second author in the edited image.

Such a key only needs the basic pattern Pi(x, y), gain (embedding strength) and phase shift list L(n), which makes it possible to reduce the size of the key and facilitate handling.

Also, the basic pattern Pi(x, y) included in the key uses a different green noise pattern for each image, and even if the key is lost or stolen, this key cannot be used to remove watermarks from other images. Therefore, the safety is extremely high.

Security of the embedded image is ensured by the shift pattern against a collusion attack in which the embedding pattern is estimated from the embedding image. For this reason, even if the algorithm is made public, the embedding pattern cannot be estimated from the algorithm, which does not encourage attacks.

1 is a diagram of a watermark embedding and extraction apparatus of the present invention; A diagram showing the distribution of watermarked images over the Internet, A diagram showing the flow of embedding dot pattern generation, A diagram showing the rotation direction and embedded bits of the spectrum of the dot pattern, Diagram showing the shape of the filter when generating a dot pattern for embedding A diagram showing the generated dot pattern and its spectrum and embedded information, Diagram showing the process flow of watermark embedding, Figure showing the processing flow of watermark extraction, A diagram showing the processing flow of pattern identification, A diagram showing a mask pattern, Figures showing phase shift patterns, A diagram showing a phase shift pattern by random number generation, FIG. 10 is a diagram showing a basic pattern, a phase shift pattern and their spectra, (a) for R=64 and (b) for R=32. (a) is the original image, (b) is the embedded image, and (c) is the spectrum of the embedded image.

FIG. 1 is a configuration diagram of a digital watermarking system for information embedding and extraction according to the present invention. In the copyright holder's computer 3, copyrighted image data is stored in a data memory 7 such as a hard disk. The image data is image-processed by the image processing program in the program memory 6 using the CPU 11, ROM 4, RAM 5, etc., and is displayed on the monitor 8. FIG. A scanner 1 and a printer 2 are connected to the computer 3 , and the processed image can be output from the printer and the image can be read from the scanner 1 . Such image processing increases the computational load when handling images of a large size, so there are cases where parallel processing is performed and a processing board such as a GPU is included for speeding up.

In order to embed the copyright information in the image, character information such as the author's name, date, URL, etc. is input from the keyboard 9, and at least 16 characters are required to be embedded. This requires 16 bytes (128 bits) to be embedded with ASCII code characters.

FIG. 2 shows one operation mode, showing a processing procedure for internet distribution. The image embedded with the watermark information is distributed or exhibited via the Internet 12 from the computer or server of the distributor or copyright holder 16 (13). The prospective purchaser 17 who sees it informs the distributor of his purchase desire (14). After a predetermined procedure, the distributor distributes the private key for watermark embedding and removal (15). Based on the contract with the distributor, the purchaser can remove the electronic watermark embedded in the sent image and edit the image.

The purchaser can embed information such as his/her own work information and URL as a secondary author in the edited image data using this secret key. Images embedded with such watermark information are released to the public, circulated on the market, and used in various ways.

A third party who sees the image can confirm that the image has the copyright by using watermark extraction software. The watermark extracting software is not confidential and can be freely downloaded from, for example, the homepages of distributors and copyright holders and made widely available for anyone to use. Third parties can know the owner of the image, copyright information, contact information, etc. by this, so it can also prevent unauthorized use and warn.

On the other hand, copyright holders and secondary copyright holders can track and monitor image data as copyrighted works by using the watermark. If a third party uses the image illegally, the copyright holder or secondary copyright holder will read the watermark information from the image using monitoring software, confirm that it is their own work, and that the third party will use it without permission. If so, it can be detected.

A key corresponds to each embedded image on a one-to-one basis. For this reason, the copyright holder uses a different key for each image to prevent abuse. This key cannot be used to remove watermarks on other images. Even if the key is lost or the key is obtained through a collusion attack by a third party, the damage will be limited to one image, and the watermark cannot be removed from the other images. At this time, the watermark reading software can be used in common even if the keys are different. Also. Since keys can be issued almost infinitely, the probability of having the same key is extremely low.

A detailed description will be given below along with examples.
Here, the generation of the dot pattern showing the green noise characteristics used in the present invention will be explained with reference to FIG.
Assume that the matrix size is R pixels × R pixels (R=2^m where ^ is a power), and 1-pixel size black dots are embedded in it. Let the area ratio of black dots be g (0 ≤ g ≤ 1: g = 1 is all black, g = 0 is all white). Assuming that the dot pattern at the point (x, y) is p(x, y), the dot pattern showing the green noise characteristics of g=1/2 is obtained as follows.
(Step 1) First, a pseudo-random number generator generates random dots p(x,y) (20). At this time, the initial state can be changed by changing the SEED value of the pseudo-random number generator.
(Step 2) A two-dimensional Fourier transform is performed on p(x,y) to obtain a spectrum P(u,v) (21). Here, (x, y) represent spatial coordinates, and (u, v) represent spatial frequency coordinates. For g=0.5, generate (R^2)/2 random dots (initial state is white noise) and let p(x,y).
(Step 3) Multiply P(u,v) by filter D(u,v) to obtain new P'(u,v) (22). i.e.
P'(u,v)=P(u,v)・D(u,v)
(Step 4) Perform an inverse Fourier transform on P'(u, v) to obtain a multivalued point profile p'(x, y) (23).
(Step 5) Find the error function e(x, y)=p'(x, y)-p(x, y) (24), and invert white and black by the same number in descending order of error at each pixel position (25 ).
(Step 6) The operations from Step 2 to Step 5 are repeated until the error is within the allowable amount, and finally a dot pattern of g=1/2 is obtained.

Here, the setting of the pattern of the filter D(u,v) will be explained. Now let D(u,v) be a circular ring pattern with its maximum radial frequency fmax and minimum radial frequency fmin. The frequency f0 due to the average dot spacing at g=1/2 is
f0＝√g・fn＝√(1/2)・fn
and fmax and fmin are based on f0,
a ≡ (fmax - f0)/fn
b ≡ (fmin - f0)/fn
Define the parameters (a,b) as Here, fn indicates the Nyquist frequency. By changing (a, b), it is possible to obtain dot patterns with different cluster sizes according to visual characteristics.

Watermark embedding is performed using a quaternary pattern. For this purpose, four types of patterns corresponding to embedded 2 bits (00, 01, 10, 11) are required. Therefore, the pattern of the filter D(u,v) is an elliptical ring pattern, and four patterns are rotated by 45 degrees. FIG. 4 schematically shows a filter pattern, where the minimum value of the minor axis of the elliptical ring is fmin, the maximum value is fmax, and the minimum value of the major axis is β·fmin, and the maximum value is β·fmax. Here, β represents magnification. Filter pattern corresponding to 2-bit (00) upright, (01) rotated by 45°, bit (10) rotated by 90°, and (11) rotated by 135° shall correspond to each other. The four watermark patterns thus obtained shall be denoted as Pi(x,y) (i=0,...,3).

FIG. 5 shows the shapes of such four filters (Filter 0, Filter 1, Filter 2, Filter 3). In the figure, black areas represent 0 and white areas represent 1. FIG. 6 shows the pattern and spectrum created through the above steps using this filter D(u,v). Each pattern has a size of R×R, pattern 0 corresponds to 2-bit embedded information (00), pattern 1 corresponds to (01), pattern 2 corresponds to (10), and pattern 3 corresponds to (11).

Next, a method of embedding a watermark in image data will be described. Watermark information is embedded in blue (B) data of color image data consisting of red (R), green (G), and blue (B), or it becomes luminance and color difference signals (Y, Cb, Cr). It is conceivable to convert it into a signal and embed it in luminance (Y) data. When watermark information is handled only in electronic data, embedding it in blue (B) is ideal because it is the least visually recognizable. When considering applications such as reading printed images or monitor images with a camera or scanner, it is difficult to accurately separate blue (B) data (yellow when printing), so luminance (Y) data should be used. is good.

Next, a processing procedure will be described along the flow of FIG. First, the embedded information is converted into a bit string and set to wm (20). For example, if the information to be embedded is "0123456789abcdef" and the ASCII 16 characters are expanded into a bit string, it becomes a 128-bit string wm="0011000000110001...". Let wm(i) be the i-th bit from the first bit.

Next, the image data is divided into blocks of R pixels×R pixels (21). It should be the same size as the dot pattern size. A block size of 64 pixels x 64 pixels enables highly accurate extraction, but if a large amount of information is to be embedded, a block size of 32 pixels x 32 pixels enables embedding of four times as much information.

The embedding work is done in block units. As embedding in the n-th block (23), first, start from n=1 (22). Consecutive 2 bits are extracted from the head of the embedded watermark information, and this is defined as b=(wm(i), wm(i+1)).

The pattern to be embedded is selected (24) according to the value of b. If b=(00), embed using pattern 0 (25a). Similarly, when b=(01), pattern 1 is used for embedding (25b). If b=(10), pattern 2 is used for embedding (25c). If b=(11), pattern 3 is used for embedding (25d).

Such embedding of watermark information is performed in a real space (pixel space). Now, if the image data is I(x,y), the embedding strength is gain, and the watermark embedded image data is W(x,y),
W(x,y)=I(x,y)+gain・Pi(x,y) (i=0,1,2,3)-----(1)
however,
Pi(x,y) is pattern 0 when b=(00)
When b=(01) Pi(x,y) is pattern 1
When b=(10) Pi(x,y) is pattern 2
When b=(11) Pi(x,y) is pattern 3
becomes. Pi is a binary value of (1,0), but it is set to (1/2,-1/2) to preserve the average luminance. As a result of embedding, the pixel data may exceed the dynamic range and overflow or underflow may occur. Therefore, the image I'(x,y) is sometimes subjected to the following linear transformation of the image data in advance.
I'(x,y)=(1-gain)・I(x,y)+gain/2-----(2)
This process is essential for completely removing watermark information, which will be described later, but may be omitted if the removal is unnecessary or if the frequency of overflow or underflow is low.
It is determined whether all blocks are finished (26), and if not finished, the next block is moved to (27).

All embedding bit strings wm(i) are embedded as described above. If the number of embedding blocks is larger than the number of embedding bits, the reliability can be increased by repeatedly embedding. In this case, a delimiter marker indicating the beginning of the string is required.
In the embedded image, Pi(x,y) is a random dot, so block boundaries are not conspicuous. The dot pattern, which exhibits green noise characteristics, is also used as an FM screen in printing. Dispersive dots are excellent in uniformity, so they are visually uniform and do not give the impression of graininess.

Next, extraction of watermark information will be described along the processing flow of FIG. The extraction work is performed in units of blocks by dividing into R×R blocks (30) as in the case of embedding. Starting from n=1 (31), we extract from the nth block. An R×R image is extracted from the n-th block, FFT (Fast Fourier Transform) is performed, and the image is converted into spectral information Wn (32). Subsequently, normalization by histogram equalization is performed (33). This is because the luminance differs for each block, so that the contrast is improved to improve the identification accuracy, and the degree of reliability, which will be described later, is equally evaluated for each block. Subsequently, the pattern is identified as described later (40), and 2-bit data of embedded information is extracted from the identification pattern (34). It is judged whether or not all the blocks have ended (35), and if not, n is set to n+1 (36), and the next block is started. When finished, all bits are taken out to restore the original character information (37).

FIG. 9 shows the processing flow of pattern identification processing (40). Spectral information Wn in the block is matched with a prepared mask pattern to obtain its output Qi (41). As shown in Fig. 10, the mask pattern is the same as the filter pattern, and four masks, mask 0 (M0), mask 1 (M1), mask 2 (M2), and mask 3 (M3), rotated by 45° are prepared. there is
Returning to FIG. 9, with Mi as the i-th mask, the output Qi of matching with Wn is
Qi=(1/Zi)ΣMi・Wn (i=0,1,2,3) --------(3)
However, Zi = ΣMi
(42). However, Σ is performed for each pixel in the block (corresponding to spatial frequency in this case). As a result, outputs (Q0, Q1, Q2, Q3) corresponding to each mask are obtained. Letting the largest of these four outputs be Qmax,
When Qmax = Q0, b = 00
When Qmax = Q1, b = 01
When Qmax = Q2, b = 10
When Qmax = Q3, b = 11
2-bit watermark information b is obtained (43 and 44a, 44b, 44c, 44d).

Next, if the next largest output after Qmax is Qnext, the reliability rel is
rel=Qmax-Qnext ------------(4)
is represented by That is, when Qnext is a value very close to Qmax, the probability of misjudgment is high, and the greater the difference between Qmax and Qnext, the higher the reliability. This difference can be used as an indicator of reliability.
As described above, the 2-bit embedded information b and the reliability rel are obtained.

Watermark removal is possible by subtracting the embedding. That is, from formula (1),
I(x,y)=W(x,y)-gain・Pi(x,y) (i=0,1,2,3) -------------(5)
By subtracting the embedding pattern from the watermark-embedded image by multiplying the gain, it is possible to completely restore the original image. However, if linear dynamic range correction is performed to avoid overflow or underflow during embedding, inverse correction must be performed.
Although watermark removal is possible as described above, an embedding pattern (pattern 0, pattern 1, pattern 2, pattern 3) and gain are required.

For example, if the block size is 64×64, the capacity of the private key is 16 Kbits (2 Kbytes) for 4 patterns from pattern 0 to pattern 3, plus the capacity of gain and embedded information. In the case of 32x32, four patterns from pattern 0 to pattern 3 are 4K bits (512 bytes). Since gain is usually 100 bytes or less, the embedded pattern information occupies most of the key capacity.

The smaller the capacity of the key, the easier it is to handle. To reduce the key size, pattern 2 and pattern 3 can be generated from pattern 0 and pattern 1, respectively. That is, pattern 2 is obtained by rotating pattern 0 by 90°, and pattern 3 is obtained by rotating pattern 1 by 90°. Since the rotation of the dot pattern is the same as the rotation of the spectrum, there is no change in other processing.

For loss or theft of a key, using a different dot pattern for each image makes it impossible to remove the watermark of another image with the same key. These are obtained by changing the seed value of the initial random number when generating the green noise pattern. The spectral distribution is the same, the extraction software is common, but the dot profile is different. In the case of R = 64, there are 4096 C 2048 different patterns per dot pattern, and when using multiple dot patterns, the product is the product, so the probability of having the same pattern is extremely low. high. Here, C represents a combination. The copyright holder provides each purchaser with a dot pattern obtained from different random numbers as a secret key. Since this key is different for each purchaser, it is not possible to remove the watermark from another purchaser's image.

Next, the phase shift pattern method will be described.
Since Pi(x,y) is a green noise pattern, it has no boundaries. For this reason, the phase-shifted pattern is also inconspicuous. Therefore, a pattern Pi'(x,y) is generated by shifting the phase of this pattern.
Let P'i(x,y) be obtained by shifting the phase of the R×R basic pattern Pi(x,y) by x0 in the x direction and by y0 in the y direction. However, the shift amount is assumed to be 0≤x0,y0<R. P'i(x,y) is represented by the following formula.
P'i(x,y)=Pi((x+x0) mod R, (y+y0) mod R) ----------(6)
where mod R represents the remainder modulo R. In other words, when the values of x+x0 and y+y0 exceed R, it returns to the beginning and a phase-shifted pattern is obtained.

With the phase-shifted embedding pattern P'i(x,y), the embedding is done as follows, as in the case without phase shift.
W(x,y)=I(x,y)+gain・P'i(x,y) -------(7)
where P'i(x,y) is given by equation (6)

Fig. 11 shows the phase-shifted embedding pattern P'i(x,y). Based on the pattern of (x0.y0)=(0,0), R/4,R This is the pattern when phase-shifted by /2. When R = 32, the shift amount s has 16 patterns in all combinations, of which (0, 0), (8, 8), (16, 16), (24, 24), (0, 24 ), (0,16), (16,8), and (24,0). During actual operation, the shift amount s is determined by a random number generator so that the shift amount is unknown. Fig. 12 shows random integer values from 0 to (W-1) generated. Shift amount s has 1024 patterns, of which (22,25), (23,17), (6, 17), (28,13), (30,8), (9,14), (19,14), (30,0) 8 patterns from s0 to s7 are shown.

All these patterns exhibit the same spectral characteristics. FIG. 13 shows patterns with and without phase shift and their spectral distributions. As an example, shift values (x0, y0)=(R/2, R/2) are shown for (32, 32) for R=64 and (16, 16) for R=32. The shift does not reveal the boundary of the pattern, and its spectral shape does not change. Since watermark extraction does not depend on the amount of phase shift, the extraction software does not need to be changed or modified.

Fig. 14 shows a diagram when embedded in an image. Image 1 is a 256×256 LENNA image embedded with gain=0.1875 for each 32×32 block, and a 4-level green noise pattern is embedded using a random number phase shift pattern. There are 64 blocks in total, padded with 16 characters (ASCII). In the same figure, (b) is an embedded image, and (c) is a spectral image in which the 16 embedded characters can be correctly extracted. Image 2 is embedded in a uniform image with a luminance value of 192, and is intentionally embedded with a large value of gain=0.5 to emphasize the pattern so that the embedded pattern can be identified. As can be seen from these figures, the pattern boundaries are inconspicuous. This is because the green noise pattern is a random pattern and has no boundaries. Therefore, no matter how the values of x0 and y0 are changed, the boundary is not conspicuous.

Since R phase shifts are possible in both the x and y directions in increments of one pixel, a total of R^2 phase shifts is possible. If the block size is 32x32, 1024 patterns are possible. For 64x64
4096 patterns are possible. However, since fine shift amounts are vulnerable to attacks, it is preferable to reduce the number of states and configure a large shift amount.

The phase shift amount (x0, y0) of this P'i(x, y) is changed for each block and stored as a phase shift list L(n) (where n is the block number) and stored in the key. Removal of the embedded watermark is from the embedding pattern P'i(x,y), the embedding strength gain, and the phase shift list L(n),
I(x,y)=W(x,y)-gain・P'i(x,y) --------(8)
can be removed as In order to completely return to the original image, it is necessary to perform an integer-type operation in consideration of rounding errors. Since the embedding pattern P'i(x,y) is obtained from the basic pattern Pi(x,y) and the phase shift amount as shown in Equation (6), the keys are the basic pattern Pi(x,y) and the embedding strength store gain, and phase shift list L(n).

Next, the effect of phase shift will be described. In a collusion attack from a third party, it is conceivable to estimate an embedding pattern by synthesizing images for each block. That is, from a set of N embedding patterns corresponding to embedding information, embedding image patterns Ci(x,y) are collected for each block corresponding to Pi(x,y). Next, when the embedding pattern Ci(x,y) is added and the average value is calculated, if the phase shift is not performed,
Ci(x,y)=(1/N)ΣWi(x,y)
= (1/N)ΣIi(x,y)+gain・(1/N)ΣPi(x,y) ----(8)
becomes. where N is the number of blocks corresponding to Pi(x,y), ΣWi(x,y) is the addition of watermarked image data, and ΣIi(x,y) is the addition of block-divided image data. indicates If N is infinite here,
(1/N)ΣIi(x,y)→const (DC component of image) ------(9)
(1/N)ΣPi(x,y) →Pi(x,y) -----(10)
and therefore Ci(x,y) is
Ci(x,y)=gain・Pi(x,y)＋const-----(11)
As a result, Pi(x,y) is extracted.
On the other hand, in the phase-shifted embedded image, the phase of P'i(x,y) changes randomly, so
(1/N)ΣP'i(x,y) → const -------(12)
As a result, the embedded pattern Pi(x,y) cannot be extracted.

N must be large for Equation (12) to hold. Now, assuming that the image size is W×H, the number of R×R blocks is [W/R]×[H/R]. Here, [・] represents rounding down to the nearest decimal place. Assuming that this is embedded with an embedding pattern Pi(x,y), the maximum number of one embedding pattern Pi(x,y) is [W/R]×[H/R]. For example, if an image of 256×256 pixels is embedded in blocks of size 32×32, Pi(x,y) can appear up to 64 times at maximum. If Pi(x,y) has 4 values, there are 4 patterns, so the average number of appearances is 16. Therefore, if there are 64 or more phase shift patterns P'i(x,y) per pattern, the probability of the same pattern appearing in the image is extremely low.

To accommodate various image sizes, 256 phase shift patterns are prepared for one embedding pattern. That is, 256 patterns are generated by giving x0 and y0 a phase shift amount of W/16, 2W/16, 3W/16, …, 15W/16 respectively, numbered from 0 to 255, and put in the phase shift list Make a list in embedding order. An image of 512×512 size has 256 blocks when divided into 32×32 blocks, and the capacity of the phase shift list can be 256 bytes. Data in this phase shift list are used repeatedly for larger images.

With a block size of 32×32, the key size is 1024 bits (128 bytes) for patterns 0 and 1, 256 bytes for the phase shift list, and several bytes for the gain, for a total of about 520 bytes. Embedded character information can be obtained at the time of extraction, so it does not need to be included in the key. The phase shift list L can be made even smaller by reducing the number of patterns. Furthermore, if a fixed random number sequence is used, the phase list may not be required. In this case, it is sufficient to specify only the head position of the fixed random number, so a few bytes will suffice.

Assuming that the image size is W.times.H, the embedded information amount V is four values, so V=2.times.[W/R].times.[H/R] bits. For example, if a 540×530 image is embedded in R=64 blocks, V=128 bits and 16 characters can be embedded in ASCII character code. 64 characters can be embedded if it is embedded in a 32×32 block. When used for copyright protection purposes, at least 16 characters or more are required. Therefore, when embedding in a block size of 64 x 64, the image size is 512 x 512 or more, and when embedding in a block of 32 x 32, it is 256 x 256. Image size or larger is required.

As described above, in this method, by giving a phase shift to the embedding pattern, a digital watermark that is strong against collusion attacks from third parties is obtained. This technique becomes even more robust when used in combination with the reversal pattern introduced in Patent Document 5.
In addition, since the green noise diffusion method is inherently highly resistant to various types of editing and processing, it can be said that this method is strong against all kinds of attacks because it is also resistant to collusion attacks by this method.

The digital watermarking method of the present invention has been described above, but since this method embeds a dot pattern that exhibits green noise characteristics that are difficult to see, there is little visual deterioration in image quality and it is resistant to attacks such as image editing and processing. Tolerant. The reason is that this method is a spread spectrum watermarking method. While white noise is superimposed in normal spectrum spreading, green noise is superimposed in the present invention, so that it can be easily separated from the spectrum of the image.

In addition, by using the phase shift pattern, the embedded dots are spatially diffused, making it extremely difficult to decipher the pattern and exhibiting strong resistance to collusion attacks. Therefore, it is highly resistant to all kinds of attacks and has high security. Due to such features, in the form of use for copyright protection, robust watermark embedding is possible, and illegal use, copying, falsification, etc. can be detected in various environments.

Since the watermark is embedded in the real space in units of blocks, there is no restriction on the size of the image such as a large size image, and processing can be performed at a high speed equivalent to that of the dither method. For this reason, real-time embedding of moving images is also possible, enabling the use of drive recorders and surveillance cameras.

In addition, since this method is completely reversible, it can also be used for tampering detection. That is, the hash value of the image data is embedded in the watermark as signature information. When tampering detection is performed, after removing the watermark with the key and completely restoring the original image, the hash value of the image is obtained, and if both match, it is proved that there has been no tampering.
This tampering detection method is limited to a completely reversible electronic watermark technology. This is because the Hash value changes when the image data changes as a result of embedding. Decryption of the key by a collusion attack overturns such a system from the ground up, and this method is also effective in preventing it.

1 is scanner, 2 is printer, 3 is computer system, 4 is ROM, 5 is RAM, 6 is program memory, 7 is data memory, 8 is monitor, 9 is keyboard, 10 is communication function, 11 is CPU, 12 is Internet, 13 image data distribution, 14 purchase request notification, 15 secret key delivery, 16 copyright holder's computer, and 17 purchaser's computer.

Claims (1)

In a digital watermarking method in which image data I(x,y) is divided into R×R blocks and different patterns corresponding to watermark information bits are embedded in each block,
The embedding pattern uses multiple different basic patterns Pi(x,y) that exhibit green noise characteristics, and different phase shift amounts (x0,y0) (where 0≤x0,y0<R) for each block. is shifted by x0 in the y direction and y0 in the y direction,
P'i(x,y) = Pi((x+x0) mod R, (y+y0) mod R)
(where P'i(x,y) is the pattern after shift, mod R is the remainder modulo R)
is obtained by the following arithmetic expression,
Watermark embedding uses such a pattern P'i(x,y) as follows:
W(x,y)=I(x,y)+ gain・P'i(x,y) (where gain is embedding strength)
and
The phase shift amount (x0, y0) is generated by a random number generator and stored in a phase shift list L(n) (n is a block number),
Store the basic pattern Pi(x,y), the embedding strength (gain) and the phase shift list L(n) as keys,
Extraction of watermark information involves dividing the watermarked image data into blocks and extracting the embedded bit information from the shape of the Fourier spectrum pattern of the block. The same extraction software can be used regardless of the amount of phase shift. Yes ,
To remove the watermark, the watermarked image W(x,y) is processed using the key
I(x,y)=W(x,y)-gain・P'i(x,y)
A reversible electronic watermarking method that can restore the original image by removing it by the following calculation and embed new information .

Images