Steganographic system, method, program and storage medium therefor

[0002] The present application is related to patent application Ser. No. 09/274,103 entitled “Digital Watermark Image Processing Method” filed by J. Taguchi et al on Mar. 23, 1999.

[0003] The present invention relates to steganographic system, method, program and storage medium therefor and more particularly, to steganographic system, method, program and storage medium therefore which are useful for the case in which digital contents such as images are distributed and circulated through an internet.

[0004] Recently, with development of internet, digital contents such as images have been sold and circulated frequently. Under the circumstances, for the sake of protecting copyright of digital contents especially represented by images, a contrivance has been offered, according to which writer information or consumer's information is embedded in an original image by utilizing a steganographic technology for visible watermark or invisible watermark to ensure that the writer of the original image or the consumer can be identified even when the image is spread illegally.

[0005] The conventional method for invisible steganography has been mainly classified into a method of embedding a watermark in a space dependent physical quantity or a parameter optically representing a pixel and a method of embedding a watermark in a frequency-domain dependent quantity. The frequency-domain dependent quantity can be obtained by converting the space dependent physical quantity into a frequency through the use of, for example, wavelet transform. Embedding of the watermark in the physical quantity or the frequency dependent quantity can be implemented by adding designated watermark information added with redundancy to a value of physical quantity or a value of frequency dependent quantity on a pixel, that is, correcting the value of physical quantity or the value of frequency dependent quantity and embedding resulting information in the image. The watermark embedded as a fluctuation in the frequency-domain dependent quantity can be subjected to inverse transform so that the original physical quantity may be recovered.

[0006] In the method of embedding a watermark in a space dependent physical quantity, it is general to define brightness or color information assigned to each pixel of an image as a physical quantity and embed a watermark in the physical quantity.

[0007] U.S. Pat. No. 5,721,788 entitled “Method and System for Digital Image Signature” discloses a method, according to which watermarks are embedded in a pixel at which a physical quantity such as brightness or color information becomes the maximal or minimal and in its neighboring position and when the watermarks are to be extracted, the pixel at which the physical quantity is the maximal or minimal is determined from an image embedded with the watermarks to identity the watermark embedded positions and the watermark information is read out in accordance with the identified watermark embedded positions. The above method utilizes such a nature that at a location where the physical quantity, for example, brightness on the pixel of the image changes greatly, even when the physical quantity on the pixel is changed to some extent, eyes of human are insensitive to the change. In this method, however, when the number of pixels at which the physical quantity becomes the maximal or minimal is restricted, the amount of embedded watermark information is small. Besides, if a watermark is embedded at a location where the change in brightness is small, then picture quality will sometimes be degraded. In addition, this conventional method faces difficulties in embedding a watermark at a portion where the physical quantity changes steeply.

[0008] H. Yoshiura et al., “Steganography and its Applications”, Hitachi Review Vol. 80, No. 7, pp. 511 to 516, published in 1998 by Hitachi Review-sha discloses a method for preventing degradation of picture quality as far as possible by embedding a watermark at an optimal location in consideration of characteristics of an original image. This conventional method takes into consideration such a nature that human eyes are insensitive to a change of physical quantity at a portion where the physical quantity changes steeply but are sensitive to a change of outline. In order to conserve the outline, an optimal portion where a physical quantity changes steeply and so a change of the physical quantity is not discernible by human eyes is extracted and watermark information is embedded at the extracted portion. Through this, the watermark can be embedded at the optimal position in consideration of characteristics of an original image without degrading picture quality. This conventional method, however, requires the original image for the sake of identifying the watermark embedded position and when extracting the watermark, it needs to identify the watermark embedded position by comparing the original image with an image embedded with the watermark (a watermark embedded image) and by preparing a differential image. When the original image is necessary, a large volume memory device needs to be provided to fully take custody of the original image. In addition, since selling via internet is generally not proceeded with by an owner of the original image but is generally carried out by an agency, the agency encounters the difficulty of taking custody of the original image for the purpose of extracting the watermark.

[0009] An object of the present invention is to provide steganographic system, method, program and storage medium therefor which can optimize the position where a watermark is embedded for the sake of minimizing deterioration of image and which can dispense with an original image during extraction of the watermark.

[0010] Another object of the invention is to provide a steganographic technique which can reduce the amount of information in the custody to a fraction or several tenths of that in the case of the method which conserves the original image.

[0011] Still another object of the invention is to provide a steganographic technique which can permit even a selling agency of image to hold information for watermark extraction, thereby largely contributing to actual business activity of circulating and selling digital contents via internet.

[0012] According to the present invention, there is provided an information processing system comprising an information management table for storing watermark position information embedded in an image to be embedded with a watermark in correspondence to the image, and a controller for controlling at least one of watermark embedding position and extraction positions in the image on the basis of the position information in the informa- tion management table. The controller can determine the embedding position by avoiding pixel positions corresponding to the maximal and minimal values of a physical quantity owned by a pixel of the image.

[0013] According to another aspect of the present invention, a steganographic system for embedding a watermark in an input image comprises watermark embedding position determining means for determining a watermark embedding position complying with the input image, watermark embedding means for receiving embedding position information from the watermark embedding position determining means to embed the watermark in the input image, and management means for managing the embedding position information.

[0014] The management means manages the embedding position information by making the correspondence of a watermark embedded image corresponding to the input image with the embedding position information.

[0015] A steganographic system for embedding a watermark in an input image comprises watermark embedding position determining means for determining a watermark embedding position complying with the input image, watermark embedding intensity determining means for determining a watermark embedding intensity complying with the input image, watermark embedding means for receiving embedding position information from the watermark embedding position determining means and embedding intensity information from the watermark embedding intensity determining means to embed the watermark in the input image, and management means for managing the correspondence relation between a watermark embedded image corresponding to the input image and the embedding position information.

[0016] A steganographic system for embedding a watermark in an image comprises watermark embedding position determining means for determining a watermark embedding position complying with the image and a threshold function concerning the embedding position, watermark embedding means for receiving embedding position information from the watermark embedding position determining means to embed the watermark in the image, and means for managing the embedding position information and the threshold function.

[0017] A steganographic system for embedding a watermark in an image comprises watermark embedding position determining means for determining a watermark embedding position complying with the image and a physical quantity concerning the embedding position, watermark embedding means for receiving embedding position information from the watermark embedding position determining means to embed the watermark in the image, and means for managing the embedding position information and the physical quantity.

[0018] A steganographic system for extracting a watermark of a watermark embedded image comprises management means for managing the watermark embedded image and embedding position information by making correspondence therebetween, and extraction means for receiving the watermark embedding position information from the management means to extract the watermark from the watermark embedded image.

[0019] A steganographic method for embedding a watermark in an input image comprising the steps of analyzing the input image, embedding the watermark in the input image in accordance with a result of analysis, and managing information for identifying an embedding position.

[0020] A steganographic method for embedding a watermark in an input image comprises the steps of determining a watermark embedding position complying with the input image, receiving information of the embedding position to embed the watermark in the input image, and managing the embedding position information.

[0021] A steganographic method for extracting a watermark of a watermark embedded image comprises the steps of managing the watermark embedded image and watermark embedding position information by making correspondence therebetween, and receiving the managed watermark embedding position information to extract the watermark from the watermark embedded image.

[0022] There is also provided a storage medium for storing a program realizing the function implemented by the aforementioned systems and methods.

[0023] FIG. 1 is a diagram showing an embodiment of a watermark embedding arrangement in a steganographic system according to the invention.

[0024] FIG. 2 is a diagram showing a contrivance for protecting a copyright by identifying an unauthorized person when a watermark embedded image is spread illegally.

[0025] FIG. 3 mates with FIG. 1 to show an embodiment of watermark extraction in the steganographic system according to the invention.

[0026] FIG. 4 shows details of an embedding position determining process.

[0027] FIG. 5 is a diagram showing a specified embodiment of calculation of the rate of change of a physical quantity in respect of each pixel.

[0028] FIG. 6 is a diagram showing the construction of a watermark embedding processing unit.

[0029] FIG. 7 shows details of watermark information conversion.

[0030] FIG. 8 shows details of watermark embedded image preparation.

[0031] FIG. 9 is a flow chart showing an embodiment of embedding position extraction process.

[0032] FIG. 10 shows details of a watermark extraction process.

[0033] FIG. 11 is a flow chart showing another embodiment of embedding position extraction process.

[0034] FIG. 12 is a flow chart showing still another embodiment of embedding position extraction process.

[0035] FIG. 13 shows an example of correspondence management.

[0036] FIG. 14 shows another example of correspondence management.

[0037] FIG. 15 shows still another example of correspondence management.

[0038] FIG. 16 is a diagram showing the construction of a correspondence managing unit.

[0039] FIG. 17 shows details of a characteristic extraction process.

[0040] FIG. 18 is a diagram showing the construction of a characteristic quantity database.

[0041] FIG. 19 shows details of a characteristic quantity retrieval process.

[0042] FIG. 20 is a flow chart showing calculation of characteristic vector of an image.

[0043] FIG. 21 is a flow chart showing a matching process of a neighborhood vector from the characteristic quantity database.

[0044] The present invention pertains to a method of extracting a watermark, without resort to an original image, from an image which is minimized in deterioration due to watermark embedding by using watermark embedding position information alone, a set of position information, threshold function concerning a watermark embedding position and physical quantity or a set of position information, threshold function concerning a watermark embedding position, physical quantity and initial physical quantity so as to embed a space dependent physical quantity, as a watermark, in the image.

[0045] Referring to FIG. 1, there is illustrated an embodiment of a watermark embedding arrangement in a steganographic system according to the invention. The watermark embedding arrangement 101 comprises a watermark embedding input unit 102, an embedding position determining unit 103, a watermark embedding processing unit 104, a correspondence managing unit 105, and a watermark embedding output unit 106. The watermark embedding input unit 102 receives inputs of original image and watermark information and digitizes and holds the information. The embedding position determining processing unit 103 determines a position in a watermark embedded image from the digital original image and watermark information fetched by the input unit as well as a parameter inputted by a user and adapted to designate whether the picture quality preference or the durability preference prevails. The watermark embedding processing unit 104 receives the digital position information and watermark information to calculate information such as brightness or color necessary for preparation of the watermark embedded image. The position information will be used to identify the watermark embedding position in place of the original image during watermark extraction to be described later. The correspondence managing unit 105 manages the correspondence of the original image with information concerning the watermark embedded position and will be used to identify the position information during extraction of the watermark from the water mark embedded image to be described later. The watermark embedding output unit 106 delivers the watermark embedded image.

[0046] Referring to FIG. 2, there is illustrated, in flow chart form, a contrivance for copyright protection which identifies an unauthorized person in case a watermark embedded image is copied illegally. In addition to the watermark embedding arrangement 101, a watermark extraction arrangement 201 is shown. The watermark embedding arrangement 101 receives an input of original image 202 and delivers a watermark embedded image 203. The watermark embedded image is distributed via a circulation route such as internet so as to be utilized. According to a way to utilize, the image is subjected to an image process such as enlargement/reduction or change of the tone of color. In step 204, a watermark is illegally removed through an image process. In step 205, the image subject to the image process is illegally copied. The watermark extraction arrangement 201 receives the image 206 suspected to be an illegal copy so as to extract watermark information 207. In step 208, by detecting the watermark information in the form of a legal consumer's ID of the image precedently embedded in the watermark embedding arrangement 101, the unauthorized or illegal person is identified.

[0047] FIG. 3 mates with FIG. 1 in an embodiment of the construction of the steganographic system according to the invention, showing the construction of a watermark extraction arrangement 201. As shown, the watermark extraction arrangement 201 comprises a watermark extraction input unit 301, an embedding position extraction processing unit 302, a watermark extraction processing unit 303, a watermark extraction output unit 304 and the correspondence managing unit 105. The watermark extraction input unit 301 receives inputs of watermark embedded image and position information and digitizes and holds them. The digital image and information are held in the unit 301. The embedding position extraction processing unit 302 transfers the inputted embedding position information to the watermark extraction processing unit 303. In this phase, position information corresponding to the watermark embedded image is identified by the correspondence managing unit 105. The watermark extraction processing unit 303 receives the embedding position information from the embedding position extraction processing unit 302 and calculates watermark information. The watermark extraction output unit 304 delivers the thus obtained watermark information.

[0048] Referring now to FIG. 4, details of a process in the embedding position determining processing unit 103 will be described. In order to determine a watermark embedding position, rates of change of physical quantities of individual pixels in an original image are first determined in step 401. Where the number of pixels in the original image is N, N rates of change of physical quantities are determined when the whole of image is treated as an embedding target. But when a watermark is embedded in only a part of the image, change rates for pixels included in the part are determined. The rate of change of physical quantity indicates the degree of change in physical quantity near a pixel. An embodiment of determination of the rate of change of physical quantity will be described later with reference to FIG. 5.

[0049] It is determined in step 402 in accordance with a parameter inputted by a user whether the picture quality preference or intensity preference prevails during embedding of watermark. When determining whether a watermark is embedded in individual pixels of the image, the system determines a search region range including one watermark as a comparison range used for comparing rates of change of physical quantities of the individual pixels.

[0050] The picture quality preference implies that deterioration in the picture quality is suppressed to such an extent that even when a watermark embedded image is directly compared with the original image, human eyes can hardly discern the difference. To this end, the watermark is embedded sequentially in order of steepness of the physical quantity change rate, starting with a portion of the original image where the physical quantity change rate is the steepest and so, the comparison range of physical quantity change rates of pixels which is necessary to determine the order of pixels to be embedded with watermark is required to cover the whole region.

[0051] In the picture quality preference, pixels to be embedded with watermark are sometimes concentrated to one portion. Accordingly, in the case of intensity preference, with the aim of dispersing pixels embedded with watermark over the whole of image as far as possible, physical quantity change rates in one localized range are compared with those in another localized range. In this case, watermark embedding is carried out in respect of the individual localized ranges. An image expected either to cope with an image process such as partial cut-out for illegally accessing a part of the image or to be durable against the above process needs to undergo the intensity preference. In the case of picture quality preference, the search region range covers the overall area including all pixels of the original image. In the case of intensity preference, the overall area is divided into n partial ranges which are used as search region ranges, where n is integer larger than 1 and determined by the degree of the intensity preference. For the overall area, n=1 stands. The search region range will be used in step 403 to be described below.

[0052] Let a rule indicating whether a pixel is embedded with a watermark be defined in the step 403. In each of the n divided partial ranges, the degree of change or the rate of change of physical quantity for one pixel is compared with that for another pixel and pixels which can be confined within X/n bytes are sequentially picked up in order of magnitude of the change degree or change rate, that is, in order of steepness of the change of physical quantity, where X represents the number of bytes for all pixels to be embedded with watermark. Usually, the rule depends on the algorithm of watermark, the degree of deterioration in picture quality desired in watermark embedding and the intensity. Further, as will be described later with reference to FIG. 7, the rule is also restricted by the amount of information to be embedded and the manner of determination of parity bits. It is now assumed that “1” is assigned to a picked-up pixel. This assignment is indicated by S(x)=1, where x denotes a pixel. A pixel which fails to be picked up is indicated by S(x)=0. Through this, rule S(x) for an image concerned is defined. The rule S(x) is a mapping for indicating whether a pixel is embedded with a watermark. This mapping is implemented from all of the pixels to a set {0,1}.

[0053] By using the mapping S(x), whole pixels embedded with watermark and whole pixels not embedded with watermark will be defined. Assuming that the whole of pixels of the original image is G, a set A indicated by equation (1) expresses the whole pixels embedded with watermark.

[0054] A={xεG:S(x)=1}  (1)

[0055] Besides, a set A′ indicated by equation (2) expresses the whole pixels not embedded with watermark.

[0056] A′={xεG:S(x)=0}  (2)

[0057] In step 404, the watermark embedding position is delivered to a file. The watermark embedding position is indicated by S given by equation (3), where S(i) corresponds to an i-th pixel in the original image.

[0058] S={S(1)S(2) . . . S(N)}  (3)

[0059] The position information S is delivered to the file.

[0060] Referring to FIG. 5, there is illustrated a specified embodiment of calculation of the rate of change of physical quantity in respect of each pixel. When pixels on the left side of, on the right side of, above and below a pixel x are represented by a, b, c and d and f(x) represents a physical quantity of the pixel x, the degree of change of physical quantity is given by expression (4).

[0061] |f(a)−f(x)|+|f(b)−f(x)|+|f(c)−f(x)|+|f(d)−f(x)|  (4)

[0062] Referring to FIG. 6, details of the watermark embedding processing unit 104 will be described. The watermark embedding processing unit 104 comprises a watermark information conversion unit 601 and a watermark embedded image preparation unit 602. The watermark embedding processing unit 104 receives inputs of watermark information and position information S. The watermark information conversion unit 601 receives an input of the watermark information and when embedding the information in the original image, converts the information into an expanded form considering redundancy. The watermark embedding image preparation unit 602 receives the converted watermark information to correct the physical quantity on the pixel and returns a value of corrected physical quantity to the original image.

[0063] Referring to FIG. 7, a process in the watermark information conversion unit 601 will be described. As an example, the watermark information to be embedded is a sequence of numerals or symbols such as “2936104. Here, a numeral sequence is considered to be included in a symbol sequence.

[0064] In step 701, individual symbols (here numerals) in a symbol sequence indicative of the watermark information are indicated by binary expression. In the case of a system which uses 10 numerals 0 to 9 and 52 capital and small alphabetical letters in total, 6 bits suffice to identify 62 letters. When a larger number of symbols are desired to be identified, the number of bits may be increased. Then, the symbols are expressed herein by 6 bits in binary expression as indicated in expression (5). $\begin{array}{cc}\begin{array}{cccccccc}2& \to & “0& 0& 0& 0& 1& 0”\\ 9& \to & “0& 0& 1& 0& 0& 0”\\ & & ⋮& & & & & \\ 4& \to & “0& 0& 0& 1& 0& 0”\end{array}\}& \left(5\right)\end{array}$

[0065] In step 702, these binary sequences are aligned to form one binary sequence which is represented by b. The binary sequence b is expressed by equation (6).

[0066] b=“000010” “001001” . . . 000100”  (6)

[0067] In step 703, the binary sequence prepared in the step 702 is expanded as follows. Let the number of pixels embedded with watermark be #(A) and the number of columns (the number of bits) of the binary sequence b be #(b). Then, the number #(A) is given by equation (7).

[0068] #(A)={The number of pixels for which S(x)=1 stands}  (7)

[0069] Besides, expression (8) generally stands.

[0070] #(b)<<(A)  (8)

[0071] where << indicates that the number of figures on the right side is larger than that on the left side.

[0072] An expanded binary sequence to be actually embedded in the original image is prepared in the step 703. Firstly, the binary sequence b is added with a parity bit sequence. Any one of known various methods may be employed to prepare the parity bit sequence and to determine the number of bits. For example, the binary sequence b is divided into two columns and parities are prepared by the total of rows and columns and are defined as a parity bit sequence. Where the thus prepared parity bit sequence is p, a binary sequence indicated by a set A″ is prepared pursuant to equation (9).

[0073] A={b, p, b, p, . . . , b, p}  (9)

[0074] This binary sequence corresponds to the expanded binary sequence representing the watermark information actually embedded in the original image. As indicated in equation (10), the number #(A) of pixels to be embedded with watermark must equal the number #(A) of columns (the number of bits) of the expanded binary sequence. The number of embedding bytes X is determined similarly.

[0075] #(A)=#(A) . . . (10)

[0076] The byte number X is related to the bit number #(A″) pursuant to equation (11).

[0077] X*(The number of bits per byte=#(A)  (11)

[0078] Referring now to FIG. 8, a process in the watermark embedded image preparation unit 602 will be described. The watermark embedded image preparation unit 602 receives the expanded binary sequence A and the position information S. Here, the expanded binary sequence A prepared in the step 703 is used.

[0079] In step 801, the expanded binary sequence A is inputted and the correspondence of an i-th position from the head in the expanded binary sequence with a corresponding value {0, 1} of A is made, thus making the correspondence of the expanded binary sequence with the image position. When the latter correspondence is indicated by I, this correspondence I is given by equation (12).

[0080] I(x)=i: order of pixels xsatisfying xεA  (12)

[0081] The physical quantity f(x) is corrected to a corrected physical quantity F(x) which is defined by equation (13). In step 802, a corrected physical quantity F(x) to be embedded in the original image is determined in correspondence to the expanded binary sequence A. The F(x) is defined by equation (13). $\begin{array}{cc}\begin{array}{c}F\left(x\right)=f\left(x\right)\left(\mathrm{when}x\in A^{\prime }\mathrm{or}S\left(x\right)=0\right)\\ =\left[f\left(x\right)/2\right]*2+1(\mathrm{when}x\in A\mathrm{or}A\left(I\left(x\right)\right)=1\\ =\left[f\left(x\right)/2\right]*2(\mathrm{when}x\in A\mathrm{or}A\left(I\left(x\right)\right)=0\end{array}\}& \left(13\right)\end{array}$

[0082] For a pixel x, the corrected physical quantity F(x) is embedded in place of the physical quantity f(x) in the original image. Thus, for a pixel not embedded with watermark, the same physical quantity as that in the original image is retained. But F(x) at a site where the watermark is embedded branches to two, so that the pixel embedded with watermark is sequenced in accordance with the correspondence I and the physical quantity is rounded to odd number or even number in accordance with a value of {0, 1} determined by the correspondence I. This operation is not limitative and may be implemented in a different way. Here, the corrected physical quantity is so changed as to be odd number when corresponding to “1” and even number when corresponding to “0”. This premises the fact that even when the physical quantity of the pixel is increased or decreased by about “1”, such a change is generally indiscernible by human eyes and it does not matter to change the original image to such an extent.

[0083] In step 803, a watermark embedded image having, as pixel value, the corrected physical quantity F(x) for the pixel x is prepared.

[0084] Referring to FIG. 9, there is illustrated a flow chart of a process carried out in the embedding position extraction processing unit 302. In this process, an inverse operation to the operation in the watermark embedded image preparation unit 602 is carried out. Generally, the pixel position is indicated by I and the position of a pixel embedded with watermark is indicated by i. Then, in step 901, the positions I and i are initialized so as to be set to “0”. In step 902, the pixel position is counted up pursuant to equation (14).

[0085] I=I+1  (14)

[0086] In step 903, it is checked whether processing of the final pixel has ended. When ended, the binary sequence A representing embedded watermark information is completed (step 909). If processing of the final pixel has not ended, the program proceeds to step 904.

[0087] In the step 904, it is calculated from the position information S whether the I-th pixel x is a watermark embedded pixel or not. When the result of calculation is given by S(x), equation (15) stands.

[0088] S(x)=S(I)  (15)

[0089] In step 905, S(x) is checked for its value and if the value equals “1”, indicating that the I-th pixel is at the watermark embedding position, the program proceeds to step 906. If not so, the pixel process concerned skips to return to the step 902.

[0090] In step 906, the watermark embedded pixel position i is counted up as shown in equation (16).

[0091] i=i+1  (16)

[0092] In step 907, the physical quantity F(x) for the pixel x is obtained from the watermark embedded image.

[0093] In step 908, the binary sequence A representing the embedded watermark information is determined pursuant to equation (17).

[0094] A(i)=mod(F(x), 2)  (17)

[0095] where, in general, mod(a, b) indicates a residue when numeral a is divided by numeral b. When the physical quantity F(x) of the pixel x is even, A(i) is set with “0” and when odd, A(i) is set with “1”. This is an inverse operation to the step 802 in FIG. 8. By repeating this operation for all pixels, the binary sequence A can be recovered.

[0096] Referring to FIG. 10, a process in the watermark extraction processing unit 303 will be described. In this unit, an inverse operation to the operation in the watermark information conversion unit 601 is carried out.

[0097] In step 1001, the binary sequence A is decomposed to obtain a binary sequence of watermark information and a parity bit sequence as shown in equation (18). $\begin{array}{cc}\begin{array}{c}A=\left\{\mathrm{b1},\mathrm{p1},\mathrm{b2},\mathrm{p2},\dots ,\mathrm{bm},\mathrm{pm}\right\}\\ \#\left(\mathrm{bi}\right)=\#\left(b\right),\#.\left(\mathrm{pi}\right)=\#\left(p\right)\end{array}\}& \left(18\right)\end{array}$

[0098] where b is the binary sequence prepared from the watermark information during watermark embedding and p is the parity check bit sequence during watermark embedding.

[0099] The column number of each of the sequences b and p is the same as that determined in the steps 702 and 703.

[0100] In step 1002, by using parity bit sequence pi for bi and pi, error correction of bi is recovered. This operation is carried out for i=1 . . . m.

[0101] In step 1003, b is restored by using the principle of decision of majority. The restored b is also designated by b. In respect of individual bit columns of each bi, larger one of the numbers of “0” and “1” is chosen to prepare corresponding individual bit columns of b. As will be seen from the above, odd number is selected as the number m of bi and pi. In this manner, an eventual binary sequence b is completed. This sequence is divided by the number of bits of symbol as shown in equation (19).

[0102] b=“000010” “001001 . . . 000100”  (19)

[0103] From the divided bit sequence, a symbol sequence is recovered as indicated by expression (20). $\begin{array}{cc}\begin{array}{cccccccc}“0& 0& 0& 0& 1& 0”& \to & 2\\ “0& 0& 1& 0& 0& 0”& \to & 9\\ & & ⋮& & & & & \\ “0& 0& 0& 1& 0& 0”& \to & 4\end{array}\}& \left(20\right)\end{array}$

[0104] In this manner, the eventual extracted watermark information “2936104” can be obtained.

[0105] Another embodiment of watermark embedding in the steganographic system according to the present invention will be described. In the present embodiment, in place of the position information described in connection with FIG. 1, a set of position information, threshold function and physical quantity is used. In the case of the present embodiment, the embedding position determining processing unit 103 shown in FIG. 1 calculates a set of position information, threshold function and physical quantity from an original image and watermark information. Only portions of the threshold function and physical quantity corresponding to the watermark embedding position are calculated. The watermark embedding processing unit 104 receives inputs of digitized position information, threshold function, physical quantity and watermark information and calculates information such as brightness necessary for preparing a watermark embedded image. The position information, threshold function and physical quantity are used in place of the original image during watermark extraction to be described later to identify the watermark embedding position. The correspondence managing unit 105 manages the correspondence of the original image with the position information, threshold function and physical quantity and is used to identify the position information, threshold function and physical quantity during extraction of a watermark from the watermark embedded image to be described later.

[0106] In an invisible watermark, information is embedded by changing the physical quantity to such an extent that the change cannot be detected by human eyes. The permissible range in which the change is indiscernible by human eyes is defined as the threshold function. Generally, a watermark embedded at a site in the image where the change of physical quantity is steep is hardly detected by human eyes and for such a site, the permissible range is widened and the value of the threshold function becomes large. Various methods for determination of the threshold function have been known. For example, in a method used for medical treatment image, steepness of the physical quantity change is calculated to determine an optimum permissible range through the technique of human engineering. According to the method, one permissible range is determined in respect of individual images to provide a threshold function.

[0107] Another embodiment of watermark extraction in the steganographic system according to the present invention will be described. In the present embodiment, a set of position information, threshold function and physical quantity is used in place of the position information explained in connection with FIG. 3. The watermark extraction input unit 301 as shown in FIG. 3 receives inputs of watermark embedded image, position information, threshold function and physical quantity and digitizes and retains them. The embedding position extraction processing unit 302 transfers, to the watermark extraction processing unit 303, embedding information extracted from the aforementioned inputs. At that time, the correspondence managing unit 105 identifies the position information, threshold function and physical quantity corresponding to the watermark embedded image. The watermark extraction processing unit 303 receives the embedding position information extracted from the embedding position extraction processing unit 302 to calculate watermark information. Only portions of the threshold function and physical quantity corresponding to the watermark embedding position are calculated.

[0108] As an example, the watermark embedding processing unit 104 shown in FIG. 6 uses a set of position information, threshold function and physical quantity in place of the position information as will be described below. The watermark embedding processing unit 104 receives inputs of watermark information, position information S, threshold function and physical quantity. The watermark information conversion unit 601 receives the watermark information, converts the watermark information into a format which is used when the watermark information is actually embedded in an original image, and transfers the converted information to the watermark embedded image preparation unit 602. Only portions of the threshold function and physical quantity corresponding to the watermark embedding position are inputted.

[0109] As an example, the watermark embedded image preparation unit 602 shown in FIG. 8 uses a set of position information, threshold function and physical quantity in place of the position information as will be described below. The watermark embedded image preparation unit 602 receives inputs of binary sequence A and position information, threshold function and physical quantity. Only portions of the threshold function and physical quantity corresponding to the watermark embedding position are inputted. The binary sequence A prepared in the step 703 of FIG. 7 is used herein.

[0110] In the step 802, a corrected physical quantity to be embedded in the original image is determined. The corrected physical quantity F(x) is defined by equation (21). $\begin{array}{cc}\begin{array}{c}\begin{array}{c}F\left(x\right)=f\left(x\right)\left(\mathrm{when}x\in A^{\prime }i.e.S\left(x\right)=0\right)\\ =f_S\left(x\right)(\mathrm{when}x\in A\mathrm{and}A\left(I\left(x\right)=1\right)\\ =f\left(x\right)\left(\mathrm{when}x\in A\mathrm{and}A\left(I\left(x\right)\right)=0\right)\end{array}\\ \mathrm{where}{f}_S\mathrm{is}a\mathrm{function}\mathrm{satisfying}\mathrm{the}\\ \mathrm{following}\mathrm{relation}\text{:}\\ f\left(x\right)-h_S\left(x\right)<f_S\left(x\right)\leqq f\left(x\right)-h·h_S\left(x\right)\\ \mathrm{or}\\ f\left(x\right)+h·h_S\left(x\right)\leqq f_S\left(x\right)<f\left(x\right)+h_S\left(x\right)\\ \mathrm{where}0<h<1.\end{array}\}& \left(21\right)\end{array}$

[0111] In place of the physical quantity f(x) for the pixel x in the original image, the corrected physical quantity F(x) is embedded. Thus, for a pixel not embedded with watermark, the same physical quantity as that in the original image is retained. Corrected physical quantity F(x) at a site where the watermark is embedded branches to two, so that pixels to be embedded with watermark is sequenced in accordance with the correspondence I and the following is taken in accordance with a value of {0, 1} determined by the correspondence I. In the case of “0”, the corrected physical quantity is the same as the physical quantity in the original image. In the case of “1”, by using a parameter h which is defined as 0<h<1, function f_Sis defined which is distant from the physical quantity of the original image by not less than h times the threshold function h_Sand by less than one times the threshold function and the original physical quantity is replaced with f_S. This premises the fact that even when the physical quantity for the pixel is increased or decreased by a value which is less than the threshold function, the increase or decrease is indiscernible by human eyes and it does not matter to apply the change to such an extent to the original image.

[0112] Referring to FIG. 11, there is illustrated a flow chart of a process in the embedding position extraction unit 302 when a set of position information, threshold function and physical quantity is used in place of the position information shown in FIG. 9. The operation in this process is inverse to the operation in the watermark embedded image preparation unit 602 explained in connection with FIG. 8 in which the position information, threshold function and physical quantity are used in place of the position information. Steps 901 to 907 are the same as those in FIG. 9.

[0113] In step 1101, a binary sequence A representing embedded watermark information is determined pursuant to equation (22). $\begin{array}{cc}\begin{array}{c}A\left(i\right)=1\left(\mathrm{when}\left|F\left(x\right)-f_A\left(x\right)\right|\geqq h·h_S\left(x\right)\right)\\ =0\left(\mathrm{when}\left|F\left(x\right)-f_A\left(x\right)\right|<h·h_S\left(x\right)\right)\end{array}\}& \left(22\right)\end{array}$

[0114] where f_Arepresents a physical quantity at a portion corresponding to the watermark embedding position. When the physical quantity F(x) of the pixel x is distant from the original physical quantity by only less than h times the threshold function, “0” is set to A(i) but when distant by not less than h times the threshold function, “1” is set to A(i). By repeating this operation for all pixels, the binary sequence A can be restored (step 909).

[0115] Still another embodiment of watermark embedding in the steganographic system according to the invention will be described below. In the present embodiment, in place of the position information explained in connection with FIG. 1, a set of position information, threshold function, physical quantity and initial circumference quantity is used. In the case of the present embodiment, the embedding position determining processing unit 103 as shown in FIG. 1 calculates, from an original image and watermark information, the position information, threshold function, physical quantity and initial circumference quantity. Only portions of the threshold function, physical quantity and initial circumference quantity corresponding to the watermark embedding position are calculated. The watermark embedding processing unit 104 receives inputs of digitized position information, threshold function, physical quantity, initial circumference quantity and watermark information to calculate information such as brightness necessary to prepare a watermark embedded image. The position information, threshold function, physical quantity and initial circumference quantity are used in place of the original image to identify the watermark embedding position during watermark extraction to be described later. The correspondence managing unit 105 manages the correspondence of the original image with the position information, threshold function, physical quantity and initial circumference quantity and is used to identify the position information, threshold function, physical quantity and initial circumference quantity during extraction of a watermark from the watermark embedded image to be described later.

[0116] The circumference quantity is a mean value of physical quantities at pixels adjoining each pixel. Where pixels x₁, . . . , x_1kadjoin a pixel x, circumferenc quantity F_Sof physical quantity F is calculated pursuant to equation (23).

[0117] F_S(x)=(F(x₁)+ . . . F(x_k))/k  (23)

[0118] It is assumed that initial circumference quantity F_SOis a circumference quantity calculated in association with the original image pursuant to equation (23).

[0119] Still another embodiment of watermark extraction in the steganographic system according to the invention will be described. In the present embodiment, in place of the position information explained in connection with FIG. 3, a set of position information, threshold function, physical quantity and initial circumference quantity is used. In the case of the present embodiment, the watermark extraction input unit 301 as shown in FIG. 3 receives inputs of watermark embedded image, position information, threshold function, physical quantity and initial circumference quantity and digitizes and retains them. The embedding position extraction processing unit 302 transfers, to the watermark extraction processing unit 303, embedding position information extracted from the aforementioned inputs. At that time, the correspondence managing unit 105 identifies the position information, threshold function, physical quantity and initial circumference quantity corresponding to the watermark embedded image. The watermark extraction processing unit 303 receives the embedding position information extracted from the embedding position extraction processing unit 302 to calculate watermark information. Only portions of the threshold function, physical quantity and initial circumference quantity corresponding to the watermark embedding position are calculated.

[0120] An example will be described in which a set of position information, threshold function, physical quantity and initial circumference quantity are used in place of the position information of the watermark embedding processing unit 104 of FIG. 6. The watermark embedding processing unit 104 receives inputs of watermark information, position information S, threshold function, physical quantity and initial circumference quantity. The watermark information conversion unit 601 receives the watermark information, converts the watermark information into a format used when the watermark information is actually embedded in the original image and transfers the converted watermark information to the watermark embedded image preparation unit 602. Only portions of the threshold function, physical quantity and initial circumference quantity corresponding to the watermark embedding position are inputted.

[0121] An example will be described in which a set of position information, threshold function, physical quantity and initial circumference quantity is used in place of the position information in the watermark embedded image preparation unit 602 of FIG. 8. The watermark embedded image preparation unit 602 receives inputs of a binary sequence A and the position information, threshold function, physical quantity and initial circumference quantity. Only portions of the threshold function, physical quantity and initial circumference quantity corresponding to the watermark embedding position are inputted. The binary sequence A prepared in the step 703 of FIG. 7 is used.

[0122] In the step 802, a corrected physical quantity to be embedded in an original image is determined. The corrected physical quantity F(x) is defined by the equation (21). In place of the physical quantity f(x) for the pixel x in the original image, the corrected physical quantity F(x) is embedded. Thus, for a pixel not embedded with watermark, the same physical quantity as that in the original image is retained. Corrected physical quantity F(x) at a site where the watermark is embedded branches to two, so that pixels to be embedded with watermark is sequenced in accordance with the correspondence I and the following is taken in accordance with a value of {0, 1} determined by the correspondence I. In the case of “0”, the corrected physical quantity is the same as the physical quantity in the original image. In the case of “1”, by using a parameter h which is defined as 0<h<1, function f_Sis defined which is distant from the physical quantity of the original image by not less than h times the threshold function h_Sand by less than one times (or by a fraction of) the threshold function and the original physical quantity is replaced with f_S. This premises the fact that even when the physical quantity for the pixel is increased or decreased by a value which is less than the threshold function, the increase or decrease is indiscernible by human eyes and it does not matter to apply the change to such an extent to the original image.

[0123] Referring to FIG. 12, there is illustrated a flow chart of a process in the embedding position extraction processing unit 302 when a set of position information, threshold function, physical quantity and initial circumference quantity is used in place of the position information shown in FIG. 9. The operation in this process is inverse to the operation in the watermark embedded image preparation unit 602 explained in connection with FIG. 8 in which the position information, threshold function, physical quantity and initial circumference quantity are used in place of the position information. Steps 901 to 906 are the same as those in FIG. 9.

[0124] In step 1201, a physical quantity F(x) for a pixel x is obtained from a watermark embedded image. A circumference quantity F_Sis obtained form the watermark embedded image pursuant to the equation (23).

[0125] In step 1202, a binary sequence A representing embedded watermark information is determined pursuant to equation (24). $\begin{array}{cc}\begin{array}{c}A\left(i\right)=1\left(\mathrm{when}\left|F\left(x\right)-\left(F_S\left(x\right)-F_{\mathrm{SO}}\left(x\right)\right)-f_A\left(x\right)\right|\geqq h·h_S\left(x\right)\right)\\ =0\left(\mathrm{when}\left|F\left(x\right)-\left(F_S\left(x\right)-F_{\mathrm{SO}}\left(x\right)\right)-f_A\left(x\right)\right|<h·h_S\left(x\right)\right)\end{array}\}& \left(24\right)\end{array}$

[0126] where f_Arepresents the physical quantity at a site corresponding to the watermark embedding position. F_SOrepresents an initial circumference quantity concerning the inputted watermark embedding position. Difference F_S−F_SObetween the circumference quantity F_Sand the initial circumference quantity F_SOrepresents correction when the watermark embedded image undergoes a change in physical quantity. When the physical quantity F(x) for the pixel x after the correction is distant from the original physical quantity by only less than h times the threshold function, “0” is set to A(i) but when distant by not less than h times the threshold function, “1” is set to A(i). By repeating this operation for all pixels, the binary sequence A can be restored (step 909).

[0127] An example of the correspondence management in the unit 105 of FIG. 1 is shown in FIG. 13. Watermark embedded image file name 1301 and position information field 1302 are managed in table form. When a watermark embedded image is acquired, corresponding watermark embedding position information can be obtained from this table by way of the file name.

[0128] Another example of the correspondence management in the unit 105 of FIG. 1 is shown in FIG. 14. Watermark embedded image file name 1401 and field 1402 of position information, threshold function at a watermark embedded position and physical quantity are managed in a table form. When a watermark embedded image is acquired, the position information, threshold function at a watermark embedded position and physical quantity can be obtained from this table by way of the file name.

[0129] Still another example of the correspondence management in the unit 105 of FIG. 1 is shown in FIG. 15. Watermark embedded image file name 1501 and field 1502 of position information, threshold function at a watermark embedded position, physical quantity and initial circumference quantity are manage in a table form, so that when a watermark embedded image is acquired, the position information, threshold function at a watermark embedded position, physical quantity and initial circumference quantity can be obtained from this table by way of the file name.

[0130] Referring to FIG. 16, another example of construction of the correspondence managing unit 105 of FIG. 1 is shown. Various characteristic quantities are almost the same for the original image and the watermark embedded image. The unit 105 utilizes this point and comprises a characteristic quantity extraction processing unit 1601 and a characteristic quantity retrieval processing unit 1602.

[0131] Operation in the characteristic quantity extraction processing unit 1601 is detailed in FIG. 17. In step 1701, a characteristic quantity vector of a watermark embedded image is calculated from the watermark embedded image. The characteristic quantity is an index for featuring the image and an example of a method of determining the characteristic quantity will be described later.

[0132] In step 1702, the calculated characteristic quantity vector is delivered to a characteristic quantity database.

[0133] Referring to FIG. 18, there is illustrated an example of construction of the characteristic quantity database. Each record 1802 in a characteristic quantity database 1801 includes characteristic quantity eigenvalue/vector group 1803 and watermark embedded image name file 1804. The characteristic quantity eigenvalue/vector group 1803 consists of m eigenvalues and m characteristic vectors corresponding to m characteristic quantities which express the image.

[0134] Referring to FIG. 19, a process in the characteristic quantity retrieval processing unit 1602 will be described. Step 1701 is the same as the step 17 of FIG. 17 and in this step, a characteristic quantity vector of an image is calculated.

[0135] In step 1901, a neighborhood vector having a characteristic quantity vector most approximating the characteristic quantity vector of the watermark embedded image is retrieved from the characteristic quantity database.

[0136] In step 1902, a watermark embedded image file name corresponding to the thus obtained neighborhood vector is obtained.

[0137] Referring to FIG. 20. details of the step 1701 for calculation of characteristic vectors of the image will be described. In step 2001, the area of the image is divided into M sections. The number M is determined in such a manner that when m characteristic quantities are provided, each section is grained to such an extent that each section can be featured by a characteristic quantity. Normally, m is set to be smaller than M. In step 2002, m characteristic quantities are chosen which are represented by vector b_i, where i indicates a section number.

[0138] In step 2003, b_i's are collected to form a B-matrix given by equation (25). The B-matrix is a matrix of (M, m) type and T is a transposed matrix.

[0139] B=[b₁b₂. . . b_M]T  (25)

[0140] In step 2004, in order to avoid the dependency on the manner of section dividing as far as possible, analysis of principal components is carried out through eigenvalue analysis pursuant to equation (26).

[0141] Bx_j=λ_jx_j  (26)

[0142] (j=1, 2, . . . , m)

[0143] where

[0144] λ_j: eigenvalue

[0145] x_j: characteristic vector

[0146] |x_j|=1)

[0147] Eigenvalues, m in number, hardly depend on the manner of section dividing. As the section division becomes thinner, the individual eigenvalues converge to constant values. A physical quantity corresponding to the maximum eigenvalue exhibits most eminently the characteristic of the image. The thus obtained m eigenvalues and characteristic vectors are registered as the characteristic quantity eigenvalue/vector group 1803 in the record 1802, along with the watermark embedded image file name 1804.

[0148] Referring to FIG. 21, a flow chart shows details of matching with the neighborhood vector from the characteristic quantity database. In step 2101, the number of records in the characteristic quantity database is set to N and initial values of record counter I and optimum position counter i are set as indicated in equation (27). Similarity of the characteristic quantity eigenvalue/vector group is represented by norm. As an initial value of norm, a large value of 10¹⁰such as indicated in equation (27) is set.

[0149] Norm=10¹⁰  (27)

[0150] when N: the number of records in characteristic quantity DB

[0151] I=0: record counter

[0152] i=1: optimum position counter

[0153] In step 2102, the record counter I in the characteristic quantity database is updated pursuant to equation (28).

[0154] I=I+1  (28)

[0155] In step 2103, the record counter is checked to determine whether a record to be processed exists in the characteristic quantity database. If the record counter I exceeds the record number N in the characteristic quantity database, it is determined that no record to be processed exists and the program proceeds to step 2107.

[0156] In the presence of a record to be processed, norm representing the degree of approximation of the characteristic quantity eigenvalue/vector group of record I to that of an input image, the norm being designated by norm_I, is calculated pursuant to equation (29).

[0157] Norm_I=|λ_I1−λ_O1|+|λI2−λ_O2|+ . . . +|λ_Im−λ_Om|+∥x_I1−x_O1∥+∥x_I2−x_O2∥+ . . . +∥x_Im−x_Om∥ where ∥x∥=max |x_j| (when x=(x_j))  (29)

[0158] where ∥x∥ represents the length (also one norm) of vector x. The length may be given by a square root of square sum of components but here it is indicated by an absolute value of absolute value maximum component. As indicated by expression (30), the norm is mapping from vector space to non-negative real number and is defined such that norm of the sum does not exceed the sum of norms.

[0159] ∥x∥≦0, ∥x+y∥≧∥x∥+∥y∥  (30)

[0160] In step 2105, the norm is compared with the norm_I. If the norm_Iis smaller than the norm, it is determined that the record I is more approximate to the input characteristic quantity eigenvalue/vector group and its record number is determined to be i and its norm_Iis substituted to norm. Then, the program returns to the step 2102 and proceeds to the next record processing. If not so, the program directly returns to the step 2102 and proceeds to the next record processing.

[0161] By using any one of the correspondence management table of FIGS. 13, 14 and 15, a watermark embedded image file name corresponding to the necessary position information, threshold function, physical quantity and initial circumference quantity can be obtained from the thus determined characteristic quantity eigenvalue/vector group.