# Patent

## Title
Electronic watermark embedding apparatus and method and electronic watermark detecting apparatus and method

## Abstract

An electronic watermark embedding apparatus includes means for storing a pixel matrix G with n rows and m columns of an input image, means for acquiring singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr of the pixel matrix G, means for creating a watermark information matrix W with r rows and r columns having a non-0 value as at least one nondiagonal element as electronic watermark information, creating a diagonal matrix S having singular values s1 to sr as diagonal elements, and creating a matrix Sw on the basis of Sw=S+aW (a≠0). The apparatus also includes means for multiplying the matrix Sw by a matrix U having the acquired left singular vectors u1 to ur as columns from the left and multiplying the transposed matrix of a matrix V having the acquired right singular vectors v1 to vr as columns from the right to create a pixel matrix Gw with n rows and m columns, and outputting it as an electronic-watermark-embedded image of the input image.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
The present application is a U.S. national stage application claiming the benefit of International Application No. PCT/JP2007/068355, filed on Sep. 21, 2007, the entire contents of which is incorporated herein by reference in its entirety.
TECHNICAL FIELD
The present invention relates to a technology that embeds an electronic watermark to an image, for example, and a technology that detects an electronic watermark contained in an image, for example.
BACKGROUND ART
Hitherto, various electronic watermark schemes have been proposed and been developed. It is difficult to remove an electronic watermark from an image unless the key information for extracting it is available. Therefore, it is being widely used for the purpose of copyright protection, such as the prevention of tampering and illegal copy of images.
For example, Non-Patent Document 1 proposes an electronic watermark method using singular value decomposition (SVD).
More specifically, in order to embed an electronic watermark, singular value decomposition is performed on an original image A to acquire a singular value S and singular vectors U and V. Next, an electronic watermark W is embedded to the singular value S to create (S+αW). This further undergoes singular value decomposition to acquire a singular value Sw and singular vectors Uw and Vw. Then, the singular value Sw is multiplied by the singular vectors U and VT, which are acquired by the first singular value decomposition, from both sides to create an electronic-watermark-embedded image Aw(=USwVT).
In order to detect an electronic watermark, singular value decomposition is performed on an examination target image Aw* to acquire the singular value Sw*. Next, the singular value Sw* is calculated by the singular vectors Uw* and Vw*T from both sides to calculate D*(=Uw*Sw*Vw*T). Then, W*=(D*−S)/α acquired by performing expression transformation on D*=(S+αW*) is used to detect an electronic watermark W*.
[Non-Patent Document 1] Ruizhen Liu et al, “An SVD-Based Watermarking Scheme for Protecting Rightful Ownership”, IEEE Transactions on Multimedia, March in 2002, Vol. 4, No. 1, pp. 121-128
[Non-Patent Document 2] Xiao-Ping Zhang, “Comments on “An SVD-Based Watermarking Scheme for Protecting Rightful Ownership”, IEEE Transactions on Multimedia, April in 2005, Vol. 7, No. 2, pp. 593-594
DISCLOSURE OF INVENTION
Problems to be Solved by the Invention
However, the scheme described in Non-Patent Document 1 does not clarify the mathematical meaning of the application of the singular vectors U and V by the first singular value decomposition to Sw acquired by the second singular value decomposition, and, as a result, how the acquired watermark-embedded image Aw relates to the original image A is not clear.
Regarding the scheme, the problem has been pointed out that an electronic watermark dependent on the singular vectors Uw* and Vw* to be used for the detection is detected regardless of both examination target image Aw* and actually embedded electronic watermark W (Non-Patent Document 2).
Accordingly, it is an object of the present invention to provide an inventive electronic watermark scheme that solves the problems.
Means for Solving the Problems
An electronic watermark embedding apparatus of the present invention includes input image storage means for storing a pixel matrix G with n rows and m columns (2≦n and m) of an input image, singular value decomposition means for acquiring singular values s1 to sr (s1>s2> . . . >sr), left singular vectors u1 to ur and right singular vectors v1 to vr of the pixel matrix G read from the input image storage means, means for creating a watermark information matrix W with r rows and r columns having a non-0 value at least one nondiagonal element as electronic watermark information, watermark information embedding means for creating a diagonal matrix S having singular values s1 to sr as diagonal elements, and creating a matrix Sw on the basis of Sw=S+aW (a≠0), means for outputting the acquired singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr as electronic watermark key information, and means for multiplying the created matrix Sw by a matrix U having the acquired left singular vectors u1 to ur as columns from the left and multiplying the transposed matrix of a matrix V having the acquired right singular vectors v1 to vr as columns from the right to create a pixel matrix Gw with n rows and m columns, and outputting it as an electronic-watermark-embedded image of the input image.
Preferably, the electronic watermark embedding apparatus further includes original image storage means for storing an original image which is to be the target for embedding an electronic watermark, means for cutting out a partial image of n×m pixels from the original image means and storing a pixel matrix of the partial image in the input image storage means as the pixel matrix G with n rows and m columns of the input image, and means for replacing the partial image in the original image by the electronic-watermark-embedded image of the input image to create an electronic-watermark-embedded image of the original image and outputting it.
Preferably, the watermark information embedding means creates the watermark information matrix W such that the rank of the matrix Sw can be lower than r.
An electronic watermark detecting apparatus of the invention includes examination target image storage mean for storing a pixel matrix Gk with n rows and m columns of an examination target image, key information storage means for storing singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr of the pixel matrix G with n rows and m columns of an input image as electronic watermark key information, means for multiplying the pixel matrix Gk read from the examination target image storage means by the transposed matrix of a matrix U having the left singular vectors u1 to ur as columns from the left and a matrix V having the right singular vectors v1 to vr as columns from the right to create matrix Sk with r rows and r columns, and means for creating a diagonal matrix S* having the singular values s1 to sr as diagonal elements, creating matrix W* with r rows and r columns on the basis of W*=(Sk−S*)/a, and outputting them as the detected electronic watermark.
An electronic watermark embedding method of the invention includes the step of reading a pixel matrix G from input image storage means storing the pixel matrix G with n rows and m columns (2≦n and m) of an input image, a singular value decomposition step of acquiring the singular values s1 to sr (s1>s2> . . . >sr), left singular vectors u1 to ur and right singular vectors v1 to vr of the read pixel matrix G, the step of creating a watermark information matrix W with r rows and r columns having a non-0 value as at least one nondiagonal element as electronic watermark information, the Watermark information embedding step of creating a diagonal matrix S having singular values s1 to sr as diagonal elements and creating a matrix Sw on the basis of Sw=S+aW (a≠0), the step of outputting the acquired singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr as electronic watermark key information, the step of multiplying the created matrix Sw by a matrix U having the acquired left singular vectors u1 to ur as columns from the left and the transposed matrix of a matrix V having the acquired right singular vectors v1 to vr as columns from the right to create a pixel matrix Gw with n rows and m columns and outputting them as an electronic-watermark-embedded image of the input image.
An electronic watermark detecting method of the invention includes the steps of reading a pixel matrix Gk from examination target image storage means for storing the pixel matrix Gk with n rows and m columns of an examination target image, reading singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr from key information storage means storing singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr of pixel matrix Gk with n rows and m columns of the input image as electronic watermark key information, multiplying the read pixel matrix Gk by the transposed matrix of the matrix U having the read left singular vectors u1 to ur as columns from the left and the matrix V having the read right singular vectors v1 to vr as columns from the right to create a matrix Sk with r rows and r columns, and creating a diagonal matrix S* having the read singular values s1 to sr as diagonal elements, creating a matrix W* with r rows and r columns on the basis of W*=(Sk−S*)/a and outputting it as the detected electronic watermark.
The electronic watermark embedding method and electronic watermark detecting method of the present invention may be executed by a CPU in a computer. The computer programs for the CPU may be installed or loaded to a computer through a medium such as a CD-ROM, a magnetic disk and a semiconductor memory or over a communication network, for example.
ADVANTAGES
As described above, according to the present invention, the number of times of singular value decomposition to be performed on an input image is equal to the number of times of the computing based on singular vectors to be performed for acquiring an electronic-watermark-embedded image. Therefore, there are no mathematically unclear points, unlike conventional schemes.
The singular vectors to be used for the embedding and detection are singular vectors of an input image and do not include information on an electronic watermark. This can prevent the problem that unintended information on an electronic watermark may mix thereinto due to computing using singular vectors.


BEST MODES FOR CARRYING OUT THE INVENTION
With reference to drawings, configurations and operations of embodiments of the present invention will be described below.
First Embodiment
FIG. 1 is a block diagram showing the configuration of an electronic watermark embedding apparatus according to a first embodiment of the present invention.
As shown in FIG. 1(A), an electronic watermark embedding apparatus 1 includes hardware equivalent to hardware of a normal computer apparatus, such as a CPU, a ROM, a RAM, an HDD, a user interface and a communication interface. The electronic watermark embedding apparatus 1 may physically be either specialized system or generic information processing apparatus. For example, in an information processing apparatus having a general configuration, the electronic watermark embedding apparatus 1 may be implemented by starting software defining processing in the electronic watermark embedding method according to the present invention.
As shown in FIG. 1(B), the electronic watermark embedding apparatus 1 functionally includes input image storage means 10 for storing a pixel matrix G with n rows and m columns (2≦n and m) of an input image, singular value decomposition means 11 for acquiring singular values s1 to sr (s1>s2> . . . >sr), left singular vectors u1 to ur and right singular vectors v1 to vr of the pixel matrix G read from the input image storage means 10, watermark information embedding means 12 for creating a watermark information matrix W with r rows and r columns having a non-0 value at least one nondiagonal element as electronic watermark information, creating a diagonal matrix S having singular values s1 to sr as diagonal elements, and creating a matrix Sw on the basis of Sw=S+aW (a≠0), key information output means 13 for outputting the acquired singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr as electronic watermark key information, and means 14 for multiplying the created matrix Sw by a matrix U having the acquired left singular vectors u1 to ur as columns from the left and multiplying the transposed matrix of a matrix V having the acquired right singular vectors v1 to vr as columns from the right to create a pixel matrix Gw with n rows and m columns, and outputting it as an electronic-watermark-embedded image of the input image.
These means may be implemented as function means by executing, by a CPU, programs stored in a RAM and/or a ROM in the electronic watermark embedding apparatus 1 and/or an external storage medium, for example.
With reference to the flowchart in FIG. 2, operations by the electronic watermark embedding apparatus 1 will be described below. Notably, the steps (including partial steps with no reference numerals given) can be performed in any order or in parallel unless the processing details contradict each other. The electronic watermark embedding apparatus 1 acquires in advance a pixel matrix G with n rows and m columns (2≦n and m) of an input image Ito be processed from an external apparatus (including a server, a memory device, an imaging device and a scanner device) and stores it in the input image storage means 10.
The singular value decomposition means 11 reads a pixel matrix G of an input image I from the input image storage means 10 (S100). FIG. 3(A) shows an example of the pixel matrix G when n=m=4.
Next, the singular value decomposition means 11 acquires the singular values s1 to sr (s1>s2> . . . >sr), left singular vectors u1 to ur, and right singular vectors v1 to vr of the pixel matrix G (That is, performing singular value decomposition on the pixel matrix G), and stores them in a memory such as a RAM (S101). Notably, the singular value Sk corresponds to the left singular vector uk and right singular vector vk.
The method for acquiring singular values and singular vectors may be any of conventional various sequential calculation algorithms (such as QR algorithm). Those algorithms are well known by those skilled in the art, and the programs for implementing the algorithms are easily available. Therefore, the details will not be described herein.
FIGS. 3(B), 3(C) and 3(D) show the singular value s1 to s4, left singular vectors u1 to u4 and right singular vectors v1 to v4 acquired for the pixel matrix G shown in FIG. 3(A).
Next, the watermark information embedding means 12 creates a watermark information matrix W with r rows and r columns having a non-0 value at least as one nondiagonal element as electronic watermark information, creates a diagonal matrix S having the acquired singular values s1 to sr as diagonal elements, creates a matrix Sw on the basis of Sw=S+aW (a≠0) and stores them in a memory such as a RAM (S102). In the expression, a is a parameter for adjusting the electronic watermark strength and may be defined, as a=1, for example, in accordance with the design.
Here, the position or specific value of the nondiagonal element having a non-0 value of the watermark information matrix W may be determined by using a random number, for example. Alternatively, it may be determined such that the watermark information matrix W itself can be a meaningful image. On the other hand, each of the diagonal elements of the watermark information matrix W has a tradeoff in which as the value increases, the degree of image deformation increases due to the embedded watermark information while, as the value decreases, the watermark information may easily disappear due to some processing on the image. Accordingly, when the singular values of an image exist in the range from 0.1 to several tens of thousands, it is preferable that the diagonal element value of the watermark information matrix W is approximately 200.
Furthermore, the watermark information matrix W may be created such that the rank of the matrix Sw can be lower than r. For example, the acquired singular values s1 to sr may be used as the nondiagonal element value of the watermark information matrix W to cause the two or more rows or columns of the matrix Sw to be linearly dependent.
FIG. 4(A) shows an example of the watermark information matrix W created by using S shown in FIG. 3(B) such that the rank of the matrix Sw can be lower than r. FIG. 4(B) shows the matrix Sw created by using S shown in FIG. 3(B) and W shown in FIG. 4(A) and in the case where a=1.
Next, the electronic-watermark-embedded image output means 14 multiplies the created matrix Sw by the matrix U having the acquired left singular vectors u1 to ur as columns from the left and the transposed matrix of the matrix V having the acquired right singular vectors v1 to vr as columns from the right to create a pixel matrix Gw with n rows and m columns thereby and stores it in a memory such as a RAM (S103).
Notably, the computing for creating the pixel matrix Gw by step S103 may be expressed by:

Gw=USwVT 

FIG. 4(C) shows the pixel matrix Gw created when step S103 by using the left singular vectors u1 to u4, and right singular vectors v1 to v4 shown in FIGS. 3(C) and 3(D) is performed on the Sw shown in FIG. 4(B).
Next, the key information output means 13 outputs the acquired singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr as electronic watermark key information (S104).
Next, the electronic-watermark-embedded image output means 14 outputs the created pixel matrix Gw as electronic-watermark embedded image 4 of the input image I (S105).
The outputting in step S104 or S105 may include recording in a RAM of the electronic watermark embedding apparatus 1 or an external memory, for example, and transmitting to other devices.
In this way, in the electronic watermark embedding apparatus 1 of this embodiment, singular value decomposition is performed on the pixel matrix G of the input image Ito acquire singular values and singular vectors, and electronic watermark information W is embedded to the diagonal matrix S having the acquired singular values as diagonal elements to create the matrix Sw. Then, the created matrix Sw is multiplied by the acquired singular vectors from both sides to create the electronic-watermark-embedded image Iw of the input image I.
With the configuration of this embodiment, both of the number of times of singular value decomposition to be performed on the pixel matrix G of the input image I and the number of times of computing based on singular vectors to be performed for acquiring the electronic-watermark-embedded image Iw are one and are matched. Therefore, there are no mathematically unclear points, unlike conventional schemes.
The singular vectors to be used for embedding are singular vectors of the input image and do not include information on the electronic watermark. This can prevent the problem that unintended information of the electronic watermark may mix into the electronic-watermark-embedded image due to the computing based on singular vectors.
Second Embodiment
FIG. 5 is a block diagram showing the configuration of an electronic watermark detecting apparatus according to a second embodiment of the present invention.
As shown in FIG. 5(A), an electronic watermark detecting apparatus 2 includes hardware equivalent to hardware of a normal computer apparatus, such as a CPU, a ROM, a RAM, an HDD, a user interface and a communication interface. The electronic watermark detecting apparatus 2 may physically be either specialized system or generic information processing apparatus. For example, in an information processing apparatus having a general configuration, the electronic watermark detecting apparatus 2 may be implemented by starting software defining processing in an electronic watermark detecting method according to the present invention.
As shown in FIG. 5(B), the electronic watermark detecting apparatus 2 functionally includes examination target image storage mean 20 for storing a pixel matrix Gk with n rows and m columns of an examination target image Ik, key information storage means 21 for storing singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr of a pixel matrix G with n rows and m columns of an input image I as electronic watermark key information, singular vector applying means 22 for multiplying the pixel matrix Gk read from the examination target image storage means 20 by the transposed matrix of a matrix U having the left singular vectors u1 to ur as columns from the left and a matrix V having the right singular vectors v1 to vr as columns from the right to create matrix Sk with r rows and r columns, and electronic watermark detecting means 23 for creating a diagonal matrix S* having the singular values s1 to sr as diagonal elements, creating matrix W* with r rows and r columns on the basis of W*=(Sk−S*)/a, and outputting the created matrix W* as the detected electronic watermark.
These means may be implemented as function means by executing, by a CPU, programs stored in a RAM and/or a ROM in the electronic watermark detecting apparatus 2 and/or an external storage medium, for example.
With reference to the flowchart in FIG. 6, operations by the electronic watermark detecting apparatus 2 will be described below. Notably, the steps (including partial steps with no reference numerals given) can be performed in any order or in parallel unless the processing details contradict each other.
The singular vector applying means 22 reads pixel matrix Gk of examination target image Ik from examination target image storage means 20 (S200). The examination target image storage means 20 prestores the pixel matrix Gk with n rows and m columns (2≦n and m) of the examination target image Ik.
Next, the singular vector applying means 22 reads the singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr of the pixel matrix G with n rows and m columns of the input image I from the key information storage means 21 as electronic watermark key information (S201).
Here, it is assumed that, in advance, the electronic watermark detecting apparatus 2 acquires the singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr of the pixel matrix G output by the key information output means 13 in the electronic watermark embedding apparatus 1 and stores them in the key information storage means 21. The acquisition of the data may include acquiring them from the electronic watermark embedding apparatus 1 through communication over a network and reading in the electronic watermark detecting apparatus 2 the data from a portable memory storing them in the electronic watermark embedding apparatus 1.
Alternatively, in the electronic watermark detecting apparatus 2, the pixel matrix G of the input image I may be directly stored, and singular value decomposition is performed on the pixel matrix G to acquire the singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr, which may be stored in the key information storage means 21 then.
Next, the singular vector applying means 22 multiplies the read pixel matrix Gk by the transposed matrix of the matrix U having the left singular vectors u1 to ur as columns from the left and the matrix V having the right singular vectors v1 to vr as columns from the right to create the matrix Sk with r rows and r columns, which are then stored in a memory such as a RAM (S202).
Notably, the computing for creating the matrix Sk in step S202 can be expressed as:

Sk=UTGkV

Next, the electronic watermark detecting means 23 creates a diagonal matrix S* having the singular values s1 to sr as diagonal elements, creates a matrix W* with r rows and r columns on the basis of W*=(Sk−S*)/a and outputs the matrix W* as the detected electronic watermark (S203).
The outputting may include recording in a RAM in the electronic watermark detecting apparatus 2 or an external memory, for example, displaying it to a user through a user interface and transmitting it to other apparatus.
In this way, in the electronic watermark detecting apparatus 2 of this embodiment, the computing based on the singular vectors of the pixel matrix G of the input image is performed on the pixel matrix Gk of the examination target image Ik to create the matrix Sk, and, on the basis of the created matrix Sk and the diagonal matrix S having the singular values of the pixel matrix G as diagonal elements, the electronic watermark W* is detected.
With the configuration of this embodiment, the singular vectors to be used in order to detect an electronic watermark are the singular vectors of the input image, which do not include the information on the electronic watermark. Therefore, this can prevent the problem that unintended information of an electronic watermark may mix into the detected electronic watermark due to the computing based on singular vectors.
Furthermore, as described on the first embodiment, when the watermark information matrix W is created such that the rank of the matrix Sw can be lower than r and the pixel matrix Gw is created, the following effects can be acquired in the electronic watermark detecting apparatus of the second embodiment.
In the electronic watermark detecting apparatus, when the rank of the pixel matrix Gk is r, appropriate r×r regular matrices TU and TV (=TU−1) as illustrated in FIGS. 8(A) and 8(B) may be selected. Thus, a false W, which is different from the embedded one, can be calculated, and the false W may be claimed as the watermark embedded by a user by the following method including the steps of:
1) performing SVD expansion to acquire Sk=ukTGkvk;
2) using regular matrices TU and TV to acquire U*=(TUUkT)−1, V*T=(vkTV)−1, Sk*=TUSkTV where Gk=U*Sk*V*T is satisfied;
3) decomposing the Sk* to a diagonal matrix Sk and a nondiagonal matrix W′ where, when the TU and TV shown in FIGS. 8(A) and 8(B) are used, the Sk* may be decomposed to a diagonal matrix Sk and a nondiagonal matrix W′ as shown in FIG. 8(C), for example; and
4) claiming the W′ acquired by the decomposition as the watermark information embedded by the user and claiming that the diagonal matrix Sk is the singular value matrix of the original image and the columns of the U* and V* are singular vectors of the original image.
On the other hand, when the watermark information matrix W is created such that the rank of the matrix Sw can be lower than r and the pixel matrix Gw is created, the rank of the pixel matrix Gw is lower than r (the pixel matrix Gw lacks information, compared with the pixel matrix G). In other words, the processing for creating the pixel matrix Gw is one-way processing.
Therefore, when the false W is acquired by the method for the pixel matrix Gw (or Gk), the rank of the Sk acquired by 1) is lower than r, the numbers of linear dependent columns of the Uk and Vk are lower than r. In this case, even with the use of any regular matrices TU and TV, the numbers of linear dependent columns of the U* and V* acquired by 2) are lower than r. Therefore, when the rank r of the original image I is publicly known, the claim based on the method can be rejected by comparing the publicly known rank r, the rank of the Sk claimed on the basis of the method and the numbers of linear dependent columns of the U* and V*.
Variation Example
The present invention is applicable by being changed in various manners, without limiting to the embodiments.
For example, in the first embodiment, a partial image cut out from an original image Io in which an electronic watermark is to be embedded may be the input image I.
More specifically, as shown in FIG. 7, the original image storage means 15 for storing an original image Io in which an electronic watermark is to be embedded, cut out means 16 for cutting out a partial image of n×m pixels from an original image Io, storing the pixel matrix of the partial image as a pixel matrix G with n rows and m columns of an input image I in the input image storage means 10, and electronic-watermark-embedded original image output means 17 for replacing the partial image in the original image Io by the electronic-watermark-embedded image Iw of the input image I output by the electronic-watermark-embedded image output means 15 to create and output an electronic-watermark-embedded image of the original image Io may further be provided. In this case, the cut out means 16 and electronic-watermark-embedded original image output means 17 may be configured in the same manner as a cutout function module and synthesis function (insertion function) module included in a normal image editing apparatus.
With the configuration, an electronic watermark based on the present invention can be embedded at an arbitrary position on an original image I.
Furthermore, for example, having described according to the second embodiment that the matrix W* is output as the detected electronic watermark, in addition to or instead of that, the presence of an electronic watermark may be determined and the determination result may be output.
More specifically, the electronic watermark detecting apparatus 2 may acquire the watermark information matrix W embedded when the electronic-watermark-embedded image Iw, is created, like the electronic watermark key information from the electronic watermark embedding apparatus 1 and store it in a RAM, for example. Then, the correlation value between the watermark information matrix W and the matrix W* may be calculated. If the correlation value is equal to or higher than a predetermined value, it is determined that the examination target image Ik contains an electronic watermark.
Notably, the present invention is also applicable to data (such as audio data) excluding image data. In order to apply it to data excluding image data, the data may be transformed to two-dimensional array data with n rows and m columns under a predetermined rule (for example, if the data is one-dimensional data, a certain series of n data is handled as the first row, the next series of n data as the second row and so on to form a two-dimensional array with n rows and m columns). Then, the two-dimensional array data may be regarded as the pixel matrix G with n rows and m columns of the input image I. In other words, the “image” in the present invention is the concept including not only general image data of a still picture or a frame image within a moving picture but also image data obtained as a result of the transformation of voice data and so on to a two-dimensional array.
BRIEF DESCRIPTION OF DRAWINGS
FIG. 1 is a block diagram showing the hardware configuration and function configuration of an electronic watermark embedding apparatus 1 according to a first embodiment.
FIG. 2 is a flowchart for describing operations by the electronic watermark embedding apparatus 1.
FIG. 3 is a diagram illustrating the process for embedding an electronic watermark with reference to an example.
FIG. 4 is a diagram illustrating the process for embedding an electronic watermark with reference to an example.
FIG. 5 is a block diagram showing the hardware configuration and function configuration of an electronic watermark detecting apparatus 2 of a second embodiment.
FIG. 6 is a flowchart for describing operations by the electronic watermark detecting apparatus 2 of the second embodiment.
FIG. 7 is a block diagram showing the function configuration of the electronic watermark embedding apparatus 1 of a variation example.
FIG. 8 is a diagram showing examples of regular matrices TU and TV.
REFERENCE NUMERALS


    
    
        1 electronic watermark embedding apparatus
        2 electronic watermark detecting apparatus
        10 input image storage means
        11 singular value decomposition means
        12 watermark information embedding means
        13 key information output means
        14 electronic-watermark-embedded image output means
        15 original image storage means
        16 cut out means
        17 electronic-watermark-embedded original image output means
        20 examination target image storage means
        21 key information storage means
        22 singular vector applying means
        23 electronic watermark embedding apparatus

## Claims

1. An electronic watermark embedding apparatus comprising:
input image storage means for storing a pixel matrix G with n rows and m columns (2≦n and m) of an input image;
singular value decomposition means for acquiring singular values s1 to sr (s1>s2> . . . >sr), left singular vectors u1 to ur and right singular vectors v1 to vr of the pixel matrix G read from the input image storage means;
watermark information embedding means for creating a watermark information matrix W with r rows and r columns having a non-0 value as at least one nondiagonal element as electronic watermark information, creating a diagonal matrix S having singular values s1 to sr as diagonal elements, and creating a matrix Sw on the basis of Sw=S+aW (a≠0);
means for outputting the acquired singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr as electronic watermark key information; and
means for multiplying the created matrix Sw by a matrix U having the acquired left singular vectors u1 to ur as columns from the left and multiplying the transposed matrix of a matrix V having the acquired right singular vectors v1 to vr as columns from the right to create a pixel matrix Gw with n rows and m columns, and outputting it as an electronic-watermark-embedded image of the input image.

2. The electronic watermark embedding apparatus according to claim 1, further comprising:
original image storage means for storing an original image which is to be the target for embedding an electronic watermark;
means for cutting out a partial image of n×m pixels from the original image means and storing a pixel matrix of the partial image in the input image storage means as the pixel matrix G with n rows and m columns of the input image; and
means for replacing the partial image in the original image by the electronic-watermark-embedded image of the input image to create an electronic-watermark-embedded image of the original image and outputting it.

3. The electronic watermark apparatus according to claim 1 wherein the watermark information embedding means creates the watermark information matrix W such that the rank of the matrix Sw can be lower than r.

4. An electronic watermark detecting apparatus comprising:
examination target image storage mean for storing a pixel matrix Gk with n rows and m columns of an examination target image;
key information storage means for storing singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr of a pixel matrix G with n rows and m columns of an input image as electronic watermark key information;
means for multiplying the pixel matrix Gk read from the examination target image storage means by the transposed matrix of a matrix U having the left singular vectors u1 to ur as columns from the left and a matrix V having the right singular vectors v1 to vr as columns from the right to create a matrix Sk with r rows and r columns; and
means for creating a diagonal matrix S* having the singular values s1 to sr as diagonal elements, creating matrix W* with r rows and r columns on the basis of W*=(Sk−S*)/a, and outputting it as the detected electronic watermark.

5. An electronic watermark embedding method comprising:
the step of reading a pixel matrix G with n rows and m columns (2≦n and m) of an input image from input image storage means storing the pixel matrix G;
a singular value decomposition step of acquiring the singular values s1 to sr (s1>s2> . . . >sr), left singular vectors u1 to ur and right singular vectors v1 to vr of the read pixel matrix G;
the step of creating a watermark information matrix W with r rows and r columns having a non-0 value as at least one nondiagonal element as electronic watermark information;
the watermark information embedding step of creating a diagonal matrix S having singular values s1 to sr as diagonal elements and creating a matrix Sw on the basis of Sw=S+aW (a≠0);
the step of outputting the acquired singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr as electronic watermark key information;
the step of multiplying the created matrix Sw by a matrix U having the acquired left singular vectors u1 to ur as columns from the left and the transposed matrix of a matrix V having the acquired right singular vectors v1 to vr as columns from the right to create a pixel matrix Gw with n rows and m columns and outputting it as an electronic-watermark-embedded image of the input image.

6. An electronic watermark detecting method comprising the steps of
reading a pixel matrix Gk with n rows and m columns of an examination target image from examination target image storage means for storing the pixel matrix Gk;
reading singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr from key information storage means storing singular values s1 to sr, left singular vectors u1 to ur and right singular vectors v1 to vr of pixel matrix Gk with n rows and m columns of the input image as electronic watermark key information;
multiplying the read pixel matrix Gk by the transposed matrix of the matrix U having the read left singular vectors u1 to ur as columns from the left and the matrix V having the read right singular vectors v1 to vr as columns from the right to create a matrix Sk with r rows and r columns; and
creating a diagonal matrix S* having the read singular values s1 to sr as diagonal elements, creating a matrix W* with r rows and r columns on the basis of W*=(Sk−S*)/a and outputting them as the detected electronic watermark.

7. A program embodied on a non-transitory computer readable medium causing a computer to execute the electronic watermark embedding method according to claim 5.

8. A program embodied on a non-transitory computer readable medium causing a computer to execute the electronic watermark embedding method according to claim 6.