WO2008035394A1 - Electronic watermark embedding device - Google Patents

Abstract

Information embedded in a document image is converted to a watermark symbol sequence expressed by a dot pattern, each watermark symbol is embedded in a subject embedding region, and embedding advisability is judged by checking whether it is detected. As a result, the watermark symbol is embedded in a region where embedding is possible. Further, the watermark symbol sequence is divided into a plurality of blocks, which are embedded in a document image as a plurality of watermark packets.

Description

 Specification

 Digital watermark embedding device

 Technical field

 The present invention relates to an electronic watermark embedding apparatus that embeds information in document data in a form that is difficult for human eyes to understand.

 Background art

 [0002] In recent years, the digitization of information stored in the company has progressed, and it is expected that the storage by paper documents will decrease in the future. However, since paper documents are not lost, the current situation is that paper and electronic documents are inevitably mixed. In addition, there is concern about the leakage or leakage of personal information such as customer data handled by corporations and public institutions, and the introduction of a more strict management system is required. In fact, there is data that about half of information leaks occur on printed materials, and measures to prevent information leaks from printed materials are important.

 [0003] One of the security technologies for dealing with such a situation is digital watermarking. Digital watermarking is a technology that embeds information such as the copyright holder name and copy history in data such as images, documents, and audio. By embedding important data handled within the company and products provided outside the company, it is possible to prevent information leakage, copy protection, original guarantee, etc.

[0004] The document data is printed and becomes a paper document. The paper document is read by a scanner and analyzed by software, so that embedded transparency information can be detected. By embedding the printer's name, ID, printing date, etc. in the printed material using this technology, even if the printed material is taken outside the company, a copy of the printed material or a part of the paper is collected in some form. If so, you can check who printed by detecting the information. In other words, it is expected to be applied as a technology for tracking information leakage sources for printed materials.

[0005] As described above, research on digital watermarking for digitized data is vigorous, and various types of electronic permeability have been commercialized. However, it is difficult to extract embedded information from binary document data, especially paper media that has been printed once. Electronic transparency, known as tint pattern transparency, is a technology that embeds information by adding a tint block pattern to the background of a document and changing its pattern slightly. It is said that the following is important as the performance that the ground pattern watermark should satisfy when using the ground pattern transparency for security purposes.

 (1) Copy resistance

 Even after copying several generations of a document with a tint block, it is necessary to accurately extract the embedded transparency information. This is because when an information leaker sells information to a business operator, etc., a copy is often given.

 (2) Amount of embedded information

 It is necessary to embed a sufficient amount of information. In other words, it is necessary to embed sufficient information for identifying the criminal, such as the name, ID, and date of printing.

 (3) Cutting resistance

 It is necessary to be able to detect the permeability information even with a part of the document. There are various forms to be cut out, and it is necessary to achieve a mechanism that can detect watermark information no matter where the document is cut.

 [0006] In the method of Patent Document 1 below, as shown in FIG. 1, a transparent image is created by repeatedly inserting symbols representing the transparent information by raster scanning, and then the document is converted into an image. A watermarked document image is generated by overlaying the transparent image on the converted image.

 In this example, a person's name is used as embedded information, and its binary representation “1, 0, 1, 1, 1, 0, 0, 1, is transparent and is used as information 103 as a document image 104. The watermark symbols 101 and 102 constituting the watermark information 103 represent the codes “0” and “1”, respectively.The nine symbols of the watermark information 103 are represented by “A, B, C, D, E”. , F, G, H, I ", for example, these symbols can be repeatedly inserted as shown in FIG.

At the time of extracting a watermark symbol, as shown in FIG. 3, the embedded information is restored by extracting the symbol of each of the repeatedly inserted transparent information power and taking the majority of the extracted symbols. [0009] For example, in the case of symbol strings 301, 302, 303, and 304 extracted from four watermark information, the symbols "C", "H", "E", and "D" are erroneously extracted, respectively. However, the correct symbol string 305 is obtained by taking the majority vote.

 [0010] However, in such a method, when a character image or figure that covers and hides a transparent symbol is included in the document image, the transparent symbol is accurately extracted and the watermark information is restored. Difficult to do. For example, in the document image shown in FIG. 4, since the characters overlap the transparency information 103 in the second and third lines of the document image 401, the transparency symbol cannot be extracted.

 [0011] In addition, because of simple embedding by raster scanning, it is difficult to detect permeability information from an arbitrary cut image of a document image. For example, in the document image 501 shown in FIG. 5, all symbols are included in the correct order in the symbol sequence 504 extracted from the horizontal cut image 502. It is possible to detect 103. The symbol sequence 505 extracted from the vertically cut image 503 does not include the symbol “G”, and the other symbols are also correct! /, Arranged in order! /, Na! /, Therefore, it is difficult to detect the information 103 from the cut image 503 with transparency.

 [0012] Therefore, in the method of Patent Document 2, as shown in FIG. 6, the symbol is embedded with transparency while avoiding the character area of the printed matter. When detecting the transparent information, the watermark symbol is extracted while discriminating the character area and the watermark symbol area, and a majority decision is performed on the extracted symbol strings 601 and 602, whereby the correct symbol string 603 is obtained. .

 However, in this method, it is assumed that the character area and the symbol area are accurately discriminated at the time of detection. If this determination fails, as shown in FIG. 7, characters are included in the extraction result, and for example, symbol strings 701 and 702 are extracted. In this case, the symbol string 701 contains three characters! /, So the symbols “G”, “H”, and “I” that were originally included in the symbol string 701 are the next symbols. Moved to the beginning of column 702.

[0014] Therefore, when taking the majority of two symbol sequences, the beginning (A) and the beginning (A) of the watermark information 103, the second (B) and the second (B), ..., the sixth Like (F) and 6th (F), correct! / ヽ symbols cannot be compared with each other, and the watermark detection performance is significantly degraded. Such deterioration is called the majority phase shift for convenience. For example, copy over several generations If it is done for the first time, it will be difficult to accurately separate the character area and the transparency symbol area where the deterioration of the printed matter will be severe.

 [0015] Whether or not a character is included in the region in which the symbol is embedded is determined by the ratio of black pixels included in the region having the same area as the symbol. In general, it is considered that as the ratio of black pixels is larger, the permeability overlaps with the black pixels and the detection performance deteriorates. Therefore, if the percentage of black pixels is less than 50%, it is determined that characters are not included (watermarks are detected), and conversely if it is 50% or more, characters are included (transmittance is detected). It is not).

 For example, whether or not a watermark symbol can be embedded in the areas A to D in FIG. 8 is determined using the black pixel rate R as follows.

 Area A: R = 14Z81 <50% → can be embedded

 Area B: R = 14Z81 50% → embeddable

 Area C: R = 4lZ81> 50% → cannot be embedded

 Area D: R = 4lZ81> 50% → Cannot be embedded

 However, there is a fact that the probability that the permeability is actually detected and the permeability is erroneously detected at the time of detection is not always proportional to the proportion of black pixels.

 In the example of Patent Document 2, as shown in FIG. 9, a watermark detection is performed by associating a code of “0” or “1” with the wave directions of watermark symbols 901 and 902. For example, “0” is associated with the watermark symbol 901 with the wave direction rising to the left, and “1” is associated with the watermark symbol 902 with the wave rising to the right. When such a watermark symbol overlaps with a character area, if the black pixel ratio R of the area is less than 50%, it is determined that a watermark is detected, and if it is 50% or more, the watermark is detected. It is determined that it is not detected.

 When the watermark symbol of FIG. 9 is embedded in the areas A to D of FIG. 8, the result is as shown in FIG. However, watermark symbols 901 are embedded in areas A and C, and watermark symbols 902 are embedded in areas B and D. The numbers in parentheses in each area represent the code corresponding to the embedded watermark symbol.

In this case, at the time of watermark detection, the wave direction as indicated by the arrow is detected. In other words, among the areas A and B that are determined to be embeddable by the black pixel ratio R, “0” is embedded. From the region A, the direction of the wave indicating “1” is detected, and from the region B in which “1” is embedded, the direction of the wave indicating “0” is detected. Therefore, in practice, the watermark symbol 901 indicating “0” cannot be embedded in the area A, and the watermark symbol 902 indicating “1” cannot be embedded in the area B.

 [0020] On the other hand, in regions C and D that are determined to be non-embedded, the direction of the detected wave is the same as that of the embedded permeable symbol, so the embedded permeable The phenomenon that it can be detected occurs. The following is a summary of the embedding possibility when the symbols 901 and 902 are actually embedded through the respective areas. Area A: "0" → cannot be embedded, "1" → can be embedded

 Area B: "0" → embeddable, "1" → not embedding

 Area C: "0" → embeddable, "1" → not embedding

 Area D: "0" → cannot be embedded, "1" → can be embedded

 Thus, even if the black pixel rate is less than 50%, embedding may not be possible. Conversely, embedding may be possible even if the black pixel ratio is 50% or more. The determination of whether or not to embed a watermark based on the black pixel rate includes the above contradictory problems, and there is a problem in the stability of watermark detection.

 [0021] The problems of the prior art described above are summarized as follows.

 (1) The watermark detection capability decreases when the dot pattern of the transparent symbol overlaps the character image, figure, photo, or other area of the document image.

 (2) When embedding the transparency symbol simply avoiding the area of characters, diagrams, photographs, etc., it is necessary to accurately classify the transparency symbol and the character area etc. Arise. For this reason, the watermark detection capability is significantly reduced.

 (3) As a means to avoid areas such as characters, diagrams, and photographs, if threshold processing is performed by calculating the black pixel ratio, even if the watermark symbol can be embedded, it may be determined that embedding is impossible. Conversely, even in an area that cannot be embedded, it may be determined that embedding is possible, causing the same problem as in (2) above.

(4) It is desirable that the embedded information can be accurately restored by cutting out any region of the document image in which the transparent symbol is embedded. In other words, it is necessary to uniformly embed transparent blueprints in the document image. [0022] Patent Document 3 below relates to an information embedding method and an information extraction method capable of combining a plurality of partial images in an accurate arrangement, and Non-Patent Document 1 is an erosion that is a kind of morphological transformation. (Erosion) and dilation. Patent Document 1: Japanese Patent Laid-Open No. 2006-101161

 Patent Document 2: Japanese Patent Laid-Open No. 2003-209676

 Patent Document 3: Japanese Patent Laid-Open No. 2005-333359

 Non-Patent Document 1: Hidefumi Obata, "Morphology", Corona, p. 72-77, November 1996 Disclosure of Invention

 [0023] An object of the present invention is to provide a copy-forgery-inhibited pattern that has copy resistance and cut-out resistance and can be stably detected when a watermark is applied to an electronic document including areas such as characters, diagrams, and photographs. Information is embedded.

 [0024] In the first aspect of the present invention, the digital watermark embedding device includes a document image input unit, a watermark conversion unit, a permeability embedding area determination unit, and a permeability embedding unit, and uses a dot pattern. Information is embedded in the background area of the document image.

 The document image input unit inputs a document image, and the transparency conversion unit assigns a plurality of transparent symbols each represented by a different dot pattern to the embedded information, and transmits the information. Force Converts to a sequence of symbols. The watermark embedding area determination unit embeds a watermark symbol in an area in the document image, checks whether or not the embedded watermark symbol is detected, and if the watermark symbol is detected, the area is determined. Judgment is made that embedding is possible, and if the symbol is not detected due to transparency, the area is judged not to be embedding.

 [0026] The watermark embedding unit passes the position information of the embedding target region in the document image and the information of the transparent symbol, in which the column power of the watermark symbol is also selected, to the watermark embedding availability determining unit, and receives the determination result. . Then, the selected transparent symbol is embedded in the embedding target area determined to be embeddable to generate a watermarked document image.

[0027] The information to be embedded is transparently converted into a symbol column by the transparency converting unit, and the watermark symbol is embedded in the document image by the watermark embedding unit. At this time, the permeable embedding unit determines whether each permeable symbol can be embedded in the region to be embedded. The watermark embedding / non-embedding area determining unit tests whether or not the force is detected by trying to embed the transparent symbol in the area.

 [0028] When a transparent symbol is detected, a determination result indicating whether embedding is possible is transmitted to the embedding unit, and a watermark symbol is embedded in the area. On the other hand, when a watermark symbol is not detected, a determination result indicating that embedding is not possible is notified, and a symbol expressed by a dot pattern different from the transparent symbol or a randomly selected transparent symbol is displayed. Embedded in that area.

 [0029] In this way, by performing a test of whether or not detectability is possible when embedding a transparent symbol, even a document containing a large number of characters, drawings, photographs, etc. can be reliably detected. Information can be embedded. Therefore, embedded information can be detected stably even after several generations of copies of a printed document.

 [0030] In the second aspect of the present invention, the digital watermark embedding device includes a document image input unit, a watermark conversion unit, a watermark packetizer unit, and a watermark embedding unit, and uses a dot pattern as a document image. Embed information in the background area.

 [0031] The document image input unit inputs a document image, and the transparency conversion unit assigns a plurality of transparent symbols each represented by a different dot pattern to the embedded information, and transmits the information. And convert it to a sequence of symbols. The watermark packet part divides the transparent symbol row into a plurality of transparent blocks, and at the beginning of each transparent block, a head symbol indicating the head, and the order of the watermark blocks in the plurality of watermark blocks. A watermark packet is generated by adding one or more symbols indicating. The transparent embedding unit embeds a plurality of watermark packets in which a plurality of watermark blocking forces are also generated in a document image.

 [0032] The information to be embedded is transparently converted into a symbol string by the permeability converter, and the watermark symbol is divided into a plurality of transparent blocks by the watermark packet part. A plurality of watermark packets including different transparent blocks are generated. The watermark embedding unit embeds these watermark packets in the document image.

[0033] As described above, the information is divided into a plurality of parts and embedded in the document image, and information indicating the order is added to each part. , If all parts are included, the original information can be restored. Brief Description of Drawings

 FIG. 1 is a diagram showing a conventional watermarked document image.

 FIG. 2 is a diagram showing a transparent symbol inserted repeatedly.

 FIG. 3 is a diagram showing the majority processing of a transparent symbol.

圆 4] Permeability This is a figure showing the characters superimposed on the information.

[5] It is a diagram showing an image in which the document power is also cut off.

[6] This is a diagram showing the case where the majority vote is successful.

[7] This is a diagram showing a case where the majority vote fails.

 FIG. 8 is a diagram showing regions with different black pixel ratios.

 FIG. 9 is a diagram showing the wave direction of a watermark symbol.

 FIG. 10 is a diagram showing embedding possibility determination based on a black pixel rate.

[11] FIG. 11 shows a first document image.

 FIG. 12 is a diagram showing a permeable symbol having a hole.

 FIG. 13 is a diagram showing a result of embedding a first watermark symbol.

 FIG. 14 is a diagram showing a result of embedding a second watermark symbol.

 FIG. 15 is a diagram showing a method of generating a watermark packet.

 FIG. 16 is a diagram showing a method for arranging a watermark packet.

 FIG. 17 is a configuration diagram of a first electronic permeability embedding device.

 FIG. 18 is a flowchart of watermark conversion processing.

 FIG. 19 is a diagram showing a permeability conversion process.

 FIG. 20 is a flowchart of watermark packetization processing.

 FIG. 21 is a flowchart of a permeability and embeddability determination process.

 FIG. 22 is a diagram showing a hole and a structural element of a transparent symbol.

 FIG. 23 is a diagram showing a case where a watermark symbol can be embedded.

 FIG. 24 is a diagram showing a case where a watermark symbol cannot be embedded.

 FIG. 25 is a flowchart of a first watermark embedding process.

FIG. 26 is a diagram showing a first state of the permeability embedding process. FIG. 27 is a diagram showing a second state of the permeability embedding process.

 FIG. 28 is a diagram showing a third state of the permeability embedding process.

 FIG. 29 is a diagram showing a fourth state of the permeability embedding process.

 FIG. 30 is a diagram showing a fifth state of the permeability embedding process.

 FIG. 31 is a diagram showing a background pattern of a watermark symbol.

 FIG. 32 is a diagram showing a blank area in a tint block pattern.

[33] It is a diagram showing a structural element.

 FIG. 34 is a diagram showing the progress of erosion processing.

 FIG. 35 is a diagram showing a result of erosion processing.

 FIG. 36 is a diagram showing block division as a result of erosion processing.

FIG. 37 is a block diagram of a second electronically permeable embedding device.

 FIG. 38 is a flowchart (part 1) of category extraction processing.

 FIG. 39 is a second flowchart of category extraction processing.

 FIG. 40 is a flowchart (part 3) of the category extraction process.

 FIG. 41 is a flowchart (part 4) of category extraction processing.

 FIG. 42 shows a second document image.

 FIG. 43 is a diagram showing a label image.

 FIG. 44 is a diagram showing a watermark packet.

 FIG. 45 is a diagram showing a first test arrangement.

 FIG. 46 is a diagram showing a first AND operation.

 FIG. 47 is a diagram showing a second AND operation.

 FIG. 48 is a diagram showing a first update result of a label image.

 FIG. 49 is a diagram showing a second test arrangement.

 FIG. 50 is a diagram showing a third AND operation.

 FIG. 51 is a diagram showing a fourth AND operation.

 FIG. 52 is a diagram showing a second update result of the label image.

 FIG. 53 is a diagram showing a third test arrangement.

FIG. 54 is a diagram showing a fifth AND operation. FIG. 55 is a diagram showing a sixth AND operation.

 FIG. 56 is a view showing document images classified into categories.

 FIG. 57 shows a watermark packet before inversion.

 FIG. 58 shows an inverted watermark packet.

 FIG. 59 is a diagram showing embedding a reverse watermark packet.

 FIG. 60 is a flowchart of a second watermark embedding process.

 FIG. 61 is a diagram showing an embedding process using a label image and a permeability generation image.

 FIG. 62 is a block diagram of a digital watermark detection apparatus.

 FIG. 63 is a flowchart of head symbol search processing.

 FIG. 64 is a diagram showing an erosion process for three symbols.

 FIG. 65 is a flowchart of packet cut-out processing.

 FIG. 66 is a flowchart of watermark restoration processing.

 FIG. 67 shows a watermark restoration process.

 FIG. 68 is a block diagram of an information processing apparatus.

 FIG. 69 is a diagram showing a program and data providing method.

 BEST MODE FOR CARRYING OUT THE INVENTION

Hereinafter, the best mode for carrying out the present invention will be described in detail with reference to the drawings.

 In the embodiment of the present invention, whether or not the watermark can be embedded is determined based on the threshold value of the black pixel ratio. Instead, it is tested whether or not the transparency information is actually embedded and can be detected, and only the area where the permeability information can be reliably detected. Embed information with transparency. As a result, even when the transparent area is overlapped with the area such as the symbol and the character, the transparent watermark can be detected stably.

As an example, a case will be described in which watermark symbols 1201 and 1202 as shown in FIG. 12 are embedded in a sentence image as shown in FIG. In the watermark symbol in Fig. 12, the symbol is distinguished by the center position and shape of the blank area (hole) opened in the watermark symbol. The permeable symbols 1201 and 1202 represent the signs “0” and “1”, respectively.

FIG. 13 and FIG. 14 show the watermark symbols 1201 and 12 respectively on the sentence image of FIG. The result of embedding 02 is shown. In this case, whether or not the watermark can be detected depends on whether or not the holes of the watermark symbols 1201 and 1202 are closed by characters. In the example of FIG. 13, the watermark symbol 1201 can be embedded only in the region A, and in the example of FIG. 14, the watermark symbol 1202 can be embedded only in the regions C and D.

[0038] Permeability The embedding / non-embedding test determines whether or not a hole in a symbol is filled with characters or the like by using only a document image without actually performing processing for embedding the permeability and detecting it. It can be replaced by a simple test. As a result, the amount of computation required for the test can be reduced by IJ.

 Further, as shown in FIG. 15, the permeability information is divided into a plurality of portions and packetized, and then embedded in the document image. First, information to be embedded is transparent using a transparent symbol 1501 having a hole in the upper right portion and representing the sign “0” and a watermark symbol 1502 having a hole in the lower left portion and representing the sign “1”. Converted to fraud information 1503

 [0040] Next, the transparency level f blue information 1503 force is divided into three watermark blocks 1504 to 1506 each consisting of three watermark symbols. Then, at the head of each watermark block, a symbol 1510 indicating the head and identification information (packet ID) 1511 indicating the numbered block of the divided information are added. Is done. As a result, the first to third force blocks 1504 to 1506 are generated, and force nogets 150 7 to 1509 are generated.

 [0041] As shown in FIG. 16, the packetized information is randomly placed on the document image 1601 according to the order determined by the random numbers, so that the information is uniformly transmitted to any region of the document image 1601. It is embedded and the permeability information can be detected by cutting out any part. Therefore, it is possible to detect the transparency information not only from the cropped image in the horizontal direction but also from the cropped image in the vertical direction.

 [0042] In addition, by adopting a unique dot pattern as the symbol 1510 indicating the head of the watermark packet, it is possible to accurately determine the transparent information and the character area, etc., and the phase shift is determined by majority decision at the time of detection. It is possible to stably detect information that does not occur.

[0043] The watermark packet can be embedded even in an area where characters, drawings, photographs, etc. exist. May be embedded.

 It is also effective to embed a transparency management packet 1512 representing the management information of the watermark packet in the document image 1601 in addition to the watermark packet. The transparent management packet 1512 includes a symbol 1513 indicating the head, identification information (packet ID) 15 14 indicating the transparent management packet, the size 1515 of one watermark block, and the number of watermark information divisions (number of blocks). Including 1516.

 By embedding such a permeability management packet 1512, it is possible to change the embedding method such as the number of divisions and block size of the permeability information for each document. At the time of detection, the embedded watermark information can be restored by decoding this packet and combining multiple watermark packets.

FIG. 17 shows a configuration example of an electronically permeable embedding device using such a watermark packet. This electronic permeability embedding device includes a document image input unit 1701, a watermark conversion unit 1702, a watermark packet unit 1703, a permeability and embedding area determination unit 1704, and a transparency embedding unit 1705. Below, operation | movement of each part is demonstrated concretely.

 [1] Document image input section

 The document image input unit 1701 inputs a document image obtained by converting a document such as a specification of a patent application into a bitmap or the like, for example. In the Windows (registered trademark) operating system, data such as MS Office and PowerPoint (registered trademark) is converted to print data called EMF (Enhanced Metafile Format) format when printing a document. Therefore, it is possible to input a document image obtained by converting the EMF format into an image.

 [2] Watermark converter

The transparency conversion unit 1702 digitally watermarks confidential information embedded in the document image. The secret information to be embedded is converted into a code string having N types of code powers, and by assigning a power symbol corresponding to each code, the power information is generated. In the following explanation, for simplicity, N = 2 force N can be any integer greater than or equal to 2. In the case of N = 2, the secret information is expressed in binary numbers of “0” or “1”, and is generally expressed in N-digit numbers. FIG. 18 is a flowchart of such a watermark conversion process. First, as shown in FIG. 19, watermark conversion section 1702 inputs watermark symbols 1501 and 1502 representing codes “0” and “1” and leading symbol 1901 representing the beginning (step 1801). Next, the secret information is converted into a code string such as “1, 0, 1, 1, 1, 0, 0, 1, 1”, and each code is replaced with a corresponding watermark symbol image. Information 1503 is generated (step 1802).

 [3] Watermark packetizer

 FIG. 20 is a flowchart of the packet key process performed by the watermark packet key unit 1703. The watermark packet unit 1703 first divides the transparency information 1503 into, for example, three blocks (3 bits), and generates the transparency blocks 1504 to 1506 (step 2001).

 [0048] Next, an image of the leading symbol 1901 is attached to each watermark block, the 2-bit packet ID is replaced with the watermark symbol image, and the leading symbol 1901 and the watermark block are inserted. (Step 2002). In this way, the permeable forces 1507, 1508, and 1509 forces S are generated, including the socket IDs 1511, 1911, and 1912, respectively.

 Next, a watermark management packet 1512 as shown in FIG. 15 is generated (step 2003).

 In the watermark management packet 1512, 3 (binary representation: 11) is set as the block size 1515, and 3 (binary representation: 11) is set as the division number 1516. Therefore, it is shown that the original watermark information 1503 is divided into three watermark packets, and each watermark packet includes a transparent block having a length of 3 symbols.

 [4] Watermark embedding area determination unit

 As shown in FIGS. 10, 13, and 14, the transparent and embeddable / unembedable area determination unit 1704 determines whether or not it can be accurately detected at the time of detection when a transparent image is embedded in a document image. Judging.

 FIG. 21 is a flowchart of such an embeddability determination process. In this process, for example, as shown in FIG. 22, a symbol area having a size of m pixels × n pixels is divided into four, and a watermark symbol 1501 or 1502 is embedded depending on the position of the hole in the divided area. Conversely, when detecting watermark information, the position of the hole is detected, and the value of the embedded watermark symbol is determined based on the position information.

[0051] The transparent and embeddable area determination unit 1704 first determines the position in which the symbol is actually embedded. Try embedding a symbol in the box (step 2101). At this time, the logical product (AND) operation of the document image and the embedded symbol image is performed by setting the value of the black pixel in the document image and the symbol image to “0” and the value of the white pixel to “1”.

 For example, as shown in FIG. 23, considering a case where a watermark symbol 1501 is embedded at a symbol embedding position Q of a document image 2301, an image 2301 is obtained as a result of an AND operation. Similarly, when the watermark symbol 1502 is embedded at the symbol embedding position Q, an image 2401 is obtained by AND operation as shown in FIG.

 Next, an erosion process, which is a type of morphological transformation, is performed on the obtained image (step 2102). At this time, the value of each pixel is converted using a graphic 2201 called a structural element as shown in FIG. 22, and the position of the hole of the symbol that is actually embedded is detected.

 In the erosion process, the symbol embedding position Q force is also applied to the image obtained by the AND operation within the range of the area of the watermark symbol image. Then, while moving the structural element 2201 within the range of the symbol image, a blank area in which the entire structural element 2201 completely enters is detected. In the blank area into which the structural element 2201 enters, the locus drawn by the center of the structural element 2201 becomes white, and the other pixels are painted black. Such calculation processing is called erosion calculation in morphology mathematics, and is described in, for example, Non-Patent Document 1 described above.

 When the erosion process using the structural element 2201 is performed on the image 2301 in FIG. 23, an image 2302 force is obtained, and when the same erosion process is performed on the image 2401 in FIG. 24, the image 2402 is obtained. can get.

 [0056] Next, the value of the embedded transparent symbol is identified from the position coordinates of the blank area in the image obtained by the erosion process (step 2103), and the embedded value is detected. Compare the values (step 2104). If they match, it is determined that embedding is possible (step 2105), and if they do not match, it is determined that embedding is impossible (step 2106).

In the image 2302 of FIG. 23, since the blank area 2303 exists in the upper right part of the symbol image, the value of the symbol is identified as “0”. Since this value matches the value of the embedded watermark symbol 1501, it is determined that embedding is possible. On the other hand, in the image 2402 in FIG. 24, since there is no blank area in the range of the symbol image, it is determined that the symbol value is neither “0” nor “1”. In this case, since the value of the symbol does not match the value of the embedded watermark symbol 1502, it is determined that embedding is impossible.

 Note that, in step 2102 of FIG. 21, instead of erosion processing, the image obtained by the AND operation may be simply scanned to check for the presence of a blank area composed of white pixels.

 [5] Watermark embedding part

 FIG. 25 is a flowchart of the embedding process performed by the watermark embedding unit 1705. The transparent embedding unit 1705 first randomly selects one of the plurality of transparent packets generated by the watermark packet unit 1703 (step 2501). Here, the intermediate force and the like in FIG. 19, the force column 1507 to 1509, f row; t is the force force 1507 force S} g scale.

 Next, paying attention to the position where the information is to be embedded in the document image, it is checked whether or not the leading symbol can be embedded at that position (step 2502). Specifically, the head symbol 1901 and the symbol embedding position information are passed to the watermark embedding availability determination unit 1704 to request the embedding permission and receive the determination result.

 For example, when information on symbol embedding position Q as shown in FIG. 26 is received, watermark embedding availability determining unit 1704 actually embeds the first symbol 1901 by the process of FIG. It is determined whether or not it is possible to embed.

 Next, the determination result received from the watermark embedding availability determining unit 1704 is checked (step 2503). If the determination result is embeddable, the leading symbol 1901 is embedded at the symbol embedding position Q as shown in FIG. 26 (step 2505).

 Next, the symbol embedding position Q is moved to the right by one symbol, and it is checked whether or not the next symbol of the selected watermark packet can be embedded (step 2506). At this time, the permeable symphonor 1501 following the leading symphonor 1901 of the permeable pad 1507 and the updated information power of the symbol embedding position Q are transmitted to the embeddability determination unit 1704.

Next, the determination result received from the watermark embedding availability determining unit 1704 is checked. (Step 2507). If the determination result can be embedded, a watermark symbol 1501 is embedded at the symbol embedding position Q as shown in FIG. 27 (step 2508).

 Next, it is checked whether or not the entire watermark packet has been embedded (step 2509). If unprocessed symbols remain, the processing from step 2506 is repeated. When the embedding of one watermark packet is completed, the processing after step 2501 is repeated.

 If it is not possible to embed a watermark symbol in the middle of one watermark packet as shown in FIG. 28, a determination result indicating that embedding cannot be performed is received in step 2507. Therefore, the embedding of the watermark packet is stopped, and the processing after step 2501 is repeated. As a result, the processing is resumed from the position where the watermark could not be embedded, and whether or not the newly selected watermark packet can be embedded is checked.

 In step 2503, even if the determination result of the leading symbol 1901 cannot be embedded, the leading symbol 1901 is forcibly inserted at the position Q as shown in FIG. 29 (step 2504). Then, after returning to step 2501 and selecting a new watermark packet, an attempt is made to insert the first symbol again. Therefore, as shown in FIG. 30, a plurality of head symbols 1901 may be embedded continuously.

 [0068] By repeating the above process, a part or all of the watermark packet is embedded in the area where the transparent symbol can be detected, and the area where the transparent symbol cannot be detected is embedded at the head. Only symbols are embedded. Therefore, if the watermark symbol embedded in the range from the first symbol to the next first symbol is extracted, the information of the watermark packet can be detected.

 [0069] In step 2504, instead of the first symbol 1901, either one of the watermark symbols 1501 and 1502 may be randomly selected and embedded, or a symbol having a dot pattern different from these symbols may be embedded. Good.

 Here, with reference to FIGS. 31 to 36, the watermark symbol identifying method by the erosion process of FIG. 21 will be described more specifically.

In mathematical morphology, when obtaining the Minkowski sum or Minkowski difference between set X and set Y, set Y when set X is the figure to be processed is called a structural element. Structural elements can be handled as matrices and functions. In this embodiment, structural elements are used as matrices. deal with. Visually, a structural element can be expressed as a small region having a predetermined shape

[0071] Erosion is the arrangement of structural elements around the pixel of interest in the image to determine the luminance of the pixels within the range corresponding to the definition area of the structural element, and the luminance of the pixel of interest is the minimum value of those luminances. This is a replacement operation.

 [0072] The four copy-forgery-inhibited pattern patterns 3101 to 3104 shown in FIG. 31 represent different watermark symbols. In these tint block patterns, as shown in FIG. 32, a plurality of dots are arranged so that blank areas having different features are formed for each pattern. Here, the characteristics of the blank area mean the number, area, shape, average value of pixels, etc. of the blank area. By performing erosion processing on each pattern pattern, it is possible to detect blank areas inside the no pattern.

 It should be noted that in order to make the density of the entire document image uniform and to discriminate the tint block pattern with human eyes, it is desirable that the number of dots constituting each tint block pattern be the same. When extracting a blank area surrounded by a circle as shown in FIG. 32 from the four tint block patterns of 31, erosion processing is performed using a diamond-shaped structural element 3301 as shown in FIG. For example, when the erosion process is performed on the tint block pattern 3101, as shown in FIG. 34, a conversion result 3501 including the blank area at the upper left shown in FIG. 32 is obtained.

 In this processing, with the center of the structural element 3301 as a reference position, the structural element 3301 is arranged so as to be transparent and overlapped with the pixel of interest in the symbol image. Then, the luminance of the pixels within the definition area of the structural element is obtained, and the luminance of the pixel of interest is replaced with the minimum value of those luminances. The conversion result 3501 is obtained by repeating such replacement while raster scanning the entire image by the structural element 3301.

 Similarly, conversion results 3502, 3503, and 3504 forces as shown in FIG. 35 are obtained from the tint block patterns 3102, 3103, and 3104, respectively.

From these conversion results, it can be seen that by using the structural element 3301, blank areas of a background pattern of less than a certain size in the background pattern 3101 to 3104 are painted black, and only blank areas of a certain size or more can be detected. In the conversion result of the image obtained in this way, the symbol The symbol value is identified based on the position information of the blank area within the image.

 [0076] Specifically, the symbol area is divided into a plurality of blocks, and the symbols are identified based on the number of blank areas included in each block. In the case of the conversion result shown in FIG. 35, as shown in FIG. 36, the symbol area is divided into 2 × 2 blocks, and the symbol is also identified by the position power of the block in which the blank area exists.

 By the way, according to the morphological transformation, it is also possible to extract a black region having a low luminance instead of the blank region of the tint block pattern. When the tint block pattern has a black area having a different characteristic for each pattern, the embedded information can be detected by extracting the black area inside the pattern.

 When a black area is detected from these tint block patterns, a dilation is used instead of erosion. Dilation is an operation in which structural elements are placed around the pixel of interest in the image, the luminance of pixels within the range corresponding to the definition area of the structural element is obtained, and the luminance of the pixel of interest is replaced with the maximum value of those luminances. It is.

 Next, an embodiment will be described in which an area in a document image is classified into a plurality of categories and the information embedding method is changed for each category to change the information embedding method. By adopting the embedding method according to the area, the permeability information can be embedded efficiently. In addition, more stable watermark detection is possible when detecting watermark information, and the amount of calculation is reduced.

 FIG. 37 shows an example of the configuration of an electronic permeability embedding device using such a category classification. This electronic transparency embedding device includes a document image input unit 3701, a watermark conversion unit 3702, a watermark packet input unit 3703, a transparent and embedding area determination unit 3704, a watermark category extraction unit 3705, and a transparent embedding unit 3706. .

 Among these, the operations of the document image input unit 3701, the watermark conversion unit 3702, the watermark packet unit 3703, and the transparency embedding / non-permission area determination unit 3704 are the same as those of the document image input unit 1701 and the watermark conversion unit 1702 in FIG. The operations of the watermark packet unit 1703 and the watermark embedding availability determination unit 1704 are the same. Hereinafter, the operations of the watermark category extraction unit 3705 and the permeability embedding unit 3706 will be specifically described.

[1] Watermark category extraction unit The watermark category extraction unit 3705 classifies the area in which the symbol can be embedded by category while referring to the document image. Each area is classified into the following four categories, for example.

 Category 1: Area where all types of watermark packets can be inserted

 Category 2: Area where one type of watermark packet can be completely inserted

 Category 3: Area where a part of one kind of watermark packet can be inserted

 Category 4: Areas that do not fall under the above category

 As the category 3 area, at least the area where the header symbol which is the head symbol of the watermark packet and the packet HD force can be inserted is extracted. In addition to the header part, the area where one or more symbols in the watermark block can be embedded is also classified as Category 3.

 FIG. 38 to FIG. 41 are flowcharts of category extraction processing performed by the watermark category extraction unit 3705. In this process, the document image is divided into regions according to the categories, and a label image indicating the category of each region is generated.

 As shown in FIG. 42, the watermark category extraction unit 3705 first sets the size of the document image to k pixels XI pixels and the size of the watermark symbol to m pixels Xn pixels as shown in FIG. 43 ( A storage area for a label image having a size of (k Zm) pixel X (lZn) pixel is prepared. Then, the size of the watermark symbol is set to 1 block, and the document image is divided into (k / m) X (lZn) blocks (step 3801). The label value indicating the category is written into this label image.

 Next, the document image is raster-scanned for each obtained block, and it is checked whether or not the symbol is embeddable by transmitting through each block (step 3802). Specifically, the determination symbol and embedding target block information are passed to the watermark embedding availability determination unit 3704 to request the determination of embedding and receive the determination result. As the determination symbol, for example, a symbol having, as a blank area, a logical sum (OR) of blank areas of the head symbol and all types of watermark symbols is used.

Next, the determination result received from the watermark embedding availability determining unit 3704 is checked (step 3803). If the judgment result is embeddable, the label image shown in Fig. 43 The label value “0” is written to the pixel to be printed (step 3806), and if embedding is impossible, the label value “1” is written (step 3804).

Next, it is checked whether or not all blocks have been scanned (step 3805). If there is an unprocessed block, the processing from step 3802 is repeated. Thus, for example, Figure 4

A label image as shown in Fig. 3 is obtained.

Next, the processing shifts to the processing in FIG. 39, and the category 1 region is extracted. Here, as shown in FIG. 44, it is assumed that P types of watermark packets each having S symbol powers are embedded in the document image. Of the S symbols, the first H symbols correspond to the header. In this example, P = 3, S = 6, H = 3.

Further, as shown in FIG. 45, an inspection array having a size of P pixel X S pixel is prepared. "1" is written in each element of this verification array. Of the areas where the label value is “0” in the label image, the area is determined as the area of category 1 where the test arrangement fits perfectly.

 The watermark category extraction unit 3705 first raster-scans the label image, and performs an AND operation on the inspection array and the label image starting from the pixel of interest (step 3901). Then, in the obtained image, it is checked whether or not the label value “1” exists within the range of the inspection array (step 3902). If “1” exists in the range of the inspection array, the position of the pixel of interest is shifted to the adjacent pixel (step 3906), and the processing after step 3901 is repeated.

 In step 3902, if “1” does not exist within the range of the check array, all label values within the range of the check array are rewritten to “2” (step 3903). Then, the position of the pixel of interest is moved by S pixels corresponding to the horizontal width of the inspection array (step 3904). Thus, the next inspection is performed starting from the point moved by S pixels.

 Next, it is checked whether or not all the pixels have been scanned (step 3905). If there is an unprocessed pixel, the processing from step 3901 is repeated.

 For example, as shown in FIG. 46, when the ND calculation is performed with the pixel 4601 at the upper left of the label image as the target pixel, the calculation result includes the label value “1”, so the position of the target pixel is adjacent to the right Shift to the next pixel.

[0092] Then, as shown in FIG. 47, the pixel 4701 in the 3rd row and the 1st column of the label image is set as the target pixel A. When the ND operation is performed, the label value “1” is not included in the operation result, so the label value in the inspection array range is rewritten to “2”. As a result, the position of the target pixel moves to the pixel 4702 separated by S pixels to the right.

In this way, the label image is updated, and a result as shown in FIG. 48 is obtained. In FIG. 48, the area power field in which the label value “2” is written is the field of power category 1 that can embed all P watermark packets.

 Next, the process proceeds to the processing of FIG. 40, and the category 2 region is extracted. Here, the updated label image and a test array of S pixel X 1 pixel size as shown in FIG. 49 are used. In each element of this check array, a brilliant “1” is written. Of the areas where the label value is "0" in the label image, the area force is determined to be the area of category 2 where the test arrangement fits completely.

 The watermark category extraction unit 3705 first raster-scans the label image and checks the label value of the pixel of interest (step 4001). If the label value is “2”, the position of the pixel of interest is shifted by S pixels (step 4007), and the processing after step 4001 is repeated.

 [0096] If the label value force is not '2', the NAND operation is performed on the label image and the test array from the target pixel (step 4002), and the label value "1" exists within the test array range. (Step 4003) If “1” exists in the range of the inspection array, the position of the target pixel is shifted to the next pixel (Step 4008), and the processing after Step 4001 is repeated. .

 [0097] In step 4003, if "1" does not exist within the inspection array range, all label values within the inspection array range are rewritten to "3" (step 4004), and the position of the pixel of interest is set to S. Move the pixel part (step 4005).

Next, it is checked whether or not all the pixels have been scanned (step 4006). If there is an unprocessed pixel, the processing from step 4001 is repeated.

 For example, as shown in FIG. 50, the upper left pixel 5001 of the label image is used as the target pixel.

When D calculation is performed, the label value “1” is included in the calculation result, so the position of the pixel of interest shifts to the pixel on the right.

[0099] After that, as shown in FIG. 51, the pixel 5101 in the 6th row and the 1st column of the label image is set as the target pixel A. When the ND operation is performed, the label value “1” is not included in the operation result, so the label value in the inspection array range is rewritten to “3”. As a result, the position of the pixel of interest moves to the pixel 5102 separated by S pixels to the right.

[0100] In this way, the label image is updated, and a result as shown in FIG. 52 is obtained. In FIG. 52, the area power in which the label value “3” is written is the area of category 1 in which one watermark packet can be embedded.

 Next, the processing shifts to the processing in FIG. 41, and the category 3 region is extracted. Here, the updated label image and a test array having a size of H pixel X 1 pixel as shown in FIG. 53 are used. In each element of this check array, a brilliant “1” is written. Of the areas where the label value is “0” in the label image, the area is determined as the area of category 3 where the test arrangement fits completely.

 [0102] The watermark category extraction unit 3705 first raster-scans the label image to check the label value of the pixel of interest (step 4101). If the label value is '2' or '3', the position of the pixel of interest is shifted by H pixels (step 4107) and the processing from step 4101 is repeated.

[0103] If the label value is not "2" or "3", an AND operation is performed on the label image and the test array starting from the target pixel (step 4102), and the label value "1" is within the range of the test array. It is checked whether or not it exists (step 4103). If “1” exists within the range of the inspection array, the position of the pixel of interest is shifted to the adjacent pixel (step 4108), and the processing after step 4101 is repeated.

 In step 4103, if “1” does not exist within the range of the inspection array, all the continuous label values “0” after the pixel of interest are rewritten to “4” (step 4104). As a result, the label value in the region from H pixel to (S-1) pixel is rewritten. Then, the position of the pixel of interest is moved by the width of the rewritten area (step 4105).

 Next, it is checked whether or not all pixels have been scanned (step 4106). If there are unprocessed pixels, the processing from step 4101 is repeated.

For example, as shown in FIG. 54, when the ND calculation is performed with the pixel 5401 at the upper left of the label image as the target pixel, the calculation result includes the label value “1”. Shift to the next pixel to the right.

 Thereafter, as shown in FIG. 55, when the AND calculation is performed using the pixel 5501 in the first row and the fifth column of the label image as the pixel of interest, the calculation result does not include the label value “1”. The label value of the area from pixel 550 1 to 4 pixels is rewritten to "4". As a result, the position of the target pixel moves to a pixel 5502 that is separated by four pixels.

 In this way, the label image is updated, and the area force in which the label value “4” is written becomes at least a category 3 area in which the header portion of the watermark packet can be embedded. In the updated label image, the area where the label value “0” or “1” remains is the category 4 area.

 [0108] By performing the above processing, the document image is classified into categories 1 to 4.

 FIG. 56 shows a document image area classified by the watermark category extraction unit 3705. In this document image, an area of one or more lines indicated by pattern 5601 corresponds to category 1, an area of one line indicated by pattern 5602 corresponds to category 2, and an area indicated by pattern 5603 corresponds to category 3. Corresponding to The character area and the remaining blank area correspond to Category 4.

 [2] Watermark embedding part

 The transparency embedding unit 3706 embeds the following symbols in each area according to the label image generated by the watermark category extraction unit 3705.

 (1) Category 1 area

 All types of watermark packets are arranged according to random numbers or the like.

 (2) Category 2 area

 One watermark packet is selected by a random number or the like, and the selected watermark packet is embedded.

(3) Category 3 area

One watermark packet is selected by random numbers, etc., and the maximum number of symbols that can be embedded is embedded from the beginning of the selected watermark packet. At this time, the embedding order of symbols other than the leading symbol is reversed with a predetermined probability, and the leading symbol is replaced with another tint block pattern to indicate that the symbol has been reversed. For example, in the case of a watermark packet as shown in FIG. 57, as shown in FIG. "E, F, G" is inverted and changed to "G, F, E, D, C, B, A".

 [0110] When all the watermark packets are embedded without being inverted, as shown in the document image 5901 in Fig. 59, among the embedded watermark packet symbols, "E", "F", and "G" in the latter half are Mostly it is not embedded in the document image 5901. On the other hand, for example, by embedding the inverted watermark packet in FIG. 58 with a probability of 1Z2, the first half and the second half of the watermark packet are distributed in a well-balanced manner as in the document image 5902.

 (4) Category 4 area

 Since the watermark block that is the body of the watermark packet cannot be embedded, either the power to embed the leading symbol or the watermark symbol is selected at random and embedded. Or you may embed symbols with a different dot pattern from these symbols.

 FIG. 60 is a flowchart of the embedding process performed by the watermark embedding unit 3706. In this processing, as shown in FIG. 61, a transparency generating image 6102 having the same size as the document image is prepared, and a symbol is embedded in the watermark generating image 6102 while referring to the label image 6101. To go.

 The transparent embedding unit 3706 first raster-scans the label image and checks the label value of the pixel of interest in the label image (steps 6001 to 6004).

 If the label value is "0" or "1", the transparency is applied to the corresponding block in the generation image 6102.

The first symbol is embedded (step 6007).

[0113] If the label value power is '2', all types of watermark packets can be inserted, and therefore P types of watermark packets are embedded side by side in the corresponding region of the watermark generation image 6102 (step 6008).

If the label value is “3”, one watermark packet is selected by a random number, and the watermark packet is embedded in the corresponding area of the watermark generation image 6102 (step 6009). If the label value is “4”, one watermark packet is selected by a random number, and the order of the symbols of the watermark packet is reversed with a probability of 1Z2 (step 6010). And watermark The watermark packet symbol is embedded only in the corresponding area of the generation image 6102 (step 6011).

Next, it is checked whether or not all the pixels have been scanned (step 6005). If there are unprocessed pixels, the processing from step 6001 is repeated. When scanning of all pixels is completed, an image 6103 in which symbols are embedded in the entire watermark generation image 6102 is obtained.

[0116] After that, the document image and the obtained image for generating transparency are overlapped to generate a watermarked document image (step 6006). However, if the pixel values are different, the pixel value of the document image is given priority.

Next, the configuration and operation of a digital watermark detection apparatus that detects information embedded by the electronic permeability embedding apparatus of FIG. 17 or FIG. 37 will be described.

 FIG. 62 shows a configuration example of the digital watermark detection apparatus. This digital watermark detection device

, Watermarked document image input unit 6201, head symbol search unit 6202, watermark restoration unit 620

3 and a packet cutout unit 6204 are provided. In the following, the operation of each part will be described specifically.

 [1] Watermarked document image input section

 A watermarked document image input unit 6201 inputs a document image in which a watermark packet is embedded.

 [2] Lead symbol search part

 The leading symbol search unit 6202 detects the position of the watermark packet by searching for the leading symbol embedded in the document image.

FIG. 63 is a flowchart of the search process performed by the head symbol search unit 6202. First, symbol search unit 6202 performs raster erosion on the document image, performs erosion processing on the range of the symbol image including the pixel of interest, and detects the position of the symbol hole (step 6301). .

As shown in FIG. 64, if the first symbol 1901 is included in the target region, an image 6401 having a hole at the center is obtained by erosion processing using the structural element 2201. Next, the position of the detected hole is checked (step 6302). If there is a hole in the center of the symbol, the symbol is regarded as the first symbol 1901 and the position of the target pixel is determined. It is passed to the packet cutout unit 6204 as the head symbol position (step 6305).

[0120] Upon receiving a packet cut-out completion notification from the packet cut-out unit 6204, it is checked whether or not the power of all pixels has been crushed (step 6303). Shift to a pixel that is one size away (one symbol) (step 6306

), Repeat the process after step 6301.

[0121] If there is no hole at the center of the symbol in step 6302, the processing from step 6303 is performed. When the scanning of all pixels is finished, the watermark restoration unit 6 indicates that the search is finished.

203 is notified (step 6304).

 [3] Packet clipping unit

 The packet cutout unit 6204 extracts watermark packet information based on the start symbol position received from the start symbol search unit 6202.

FIG. 65 is a flowchart of the clipping process performed by the packet clipping unit 6204. The packet cutout unit 6204 first shifts the position of the target pixel indicated by the head symbol position by one symbol, and performs an erosion process on the range of the symbol image including the target pixel (step 6501). As a result, the erosion process for the next symbol after the first symbol is performed.

As shown in FIG. 64, if watermark symbol 1501 is included in the target area, an image 6402 having a hole in the upper right part is obtained by erosion processing using structural element 2201, and watermark symbol 1502 Is included, an image 6403 with a hole in the lower left is obtained.

Next, the value of the embedded transparent symbol is identified from the position of the hole in the obtained image (steps 6502 and 6503). If there is a hole in the upper right part of the symbol, the symbol is regarded as a watermark symbol 1501, and a code "0" is written at an address corresponding to the symbol position in the memory (step 6504). On the other hand, if there is a hole in the lower left part of the symbol, the symbol is regarded as a watermark symbol 1502, and a code "1" is written at the corresponding address in the memory (step 6505). Then, the position of the target pixel is shifted by one symbol, and the processing from step 6501 is repeated.

[0125] In steps 6502 and 6503, either in the upper right or lower left of the symbol If there is no hole, that is, if there is a hole in another position, such as the first symbol 1901, or if there is no hole in the symbol, error information is recorded at the corresponding address in the memory ( Step 6506). Then, it notifies the head symbol search unit 6202 that the packet cut-out has been completed (step 6507).

In this way, the maximum (S-1) values are detected from the portion between the two leading symbols in the document image.

 [4] Watermark restoration part

 When the watermark restoration unit 6203 is notified of the end of the search from the head symbol search unit 6202, the watermark restoration unit 6203 refers to the memory in which the symbol identification result is recorded and restores the embedded information.

 FIG. 66 is a flowchart of the restoration process performed by the watermark restoration unit 6203. The watermark restoration unit 6203 first takes a majority vote for each packet ID and restores P type watermark packets (step 6601).

 [0128] At this time, the packet cut-out result that also has a value less than (S-1) is used in the majority decision as part of the watermark packet. However, if the packet ID is not completely restored, the packet is excluded from the majority vote.

 [0129] Next, transparent blocks are cut out from the restored P watermark packets (step 6602), combined in the order specified by the packet ID, and watermark information is restored (step 6603). ). Then, the transparent blue information is converted into a code string (step 6604), and the embedded secret information is restored (step 6605).

 For example, as shown in FIG. 67, when three kinds of transparent packets 1507 to 1509 are restored by majority, watermark blocks 1504 to 1506 are cut out from these watermark packets. Then, by combining these permeable blocks, the permeable information 1503 is assembled and converted into a code string "1, 0, 1, 1, 1, 0, 0, 1, 1". In this way, secret information indicating the person's name is restored.

[0131] As shown in Fig. 59, when the normal watermark packet and the inverted watermark packet are used together, the leading symbol search unit 6202 forces both in the step 6302 of Fig. 63 depending on the position of the hole of the leading symbol. And the discrimination result is notified to the packet cutout unit 6204. The packet cutout unit 6204 excludes the first symbol in the case of a reverse watermark packet. The order of (S-l) identification values is reversed and recorded in the memory. This makes it possible to take a majority vote by combining a normal watermark packet and a reverse watermark packet.

 The digital watermark embedding device shown in FIGS. 17 and 37 and the digital watermark detection device shown in FIG. 62 are configured using an information processing device (computer) as shown in FIG. 68, for example. 68 includes a CPU (central processing unit) 6801, a memory 6802, an input device 6803, an output device 6804, an external storage device 6805, a medium drive device 6806, and a network connection device 6807, which are noses. 6808 are connected to each other.

 [0133] The memory 6802 includes, for example, a ROM (read only memory), a RAM (random access memory), and the like, and stores programs and data used for processing. The CPU 6801 performs the above-described processing by executing a program using the memory 6802.

 In this case, the document image input unit 1701, the watermark conversion unit 1702, the watermark packetization unit 1703, the watermark embedding availability determination unit 1704, and the watermark embedding unit 1705 in FIG. 17, the document image input unit 3701 in FIG. Watermark conversion unit 3702, watermark packet input unit 3703, watermark embedding possibility determination unit 3704, watermark category extraction unit 3705, watermark embedding unit 3706, watermarked document image input unit 6201, head symbol search unit 6202, watermark restoration Unit 6203 and packet cutout unit 6204 correspond to programs stored in memory 6802.

 [0135] The input device 6803 is, for example, a keyboard, a pointing device, and the like, and is used for inputting instructions and information from the operator. The output device 6804 is, for example, a display, a printer, a speaker, and the like, and is used to output an inquiry to the operator and a processing result.

 [0136] The external storage device 6805 is, for example, a magnetic disk device, an optical disk device, a magneto-optical disk device, a tape device, or the like. The information processing apparatus stores programs and data in the external storage device 6805, and loads them into the memory 6802 and uses them as necessary.

[0137] The medium driving device 6806 drives the portable recording medium 6809 and accesses the recorded contents. The portable recording medium 6809 is an arbitrary computer-readable recording medium such as a memory card, a flexible disk, an optical disk, and a magneto-optical disk. The operator A program and data are stored in the portable recording medium 6809, and are loaded into the memory 6802 and used as necessary.

 [0138] The network connection device 6807 is connected to a communication network such as a LAN (local area network) and performs data conversion accompanying communication. Further, the information processing apparatus receives programs and data as needed via the external apparatus power network connection apparatus 6807 and loads them into the memory 6802 for use.

 FIG. 69 shows a method for providing a program and data to the information processing apparatus of FIG. Programs and data stored in the portable recording medium 6809 and the database 6911 of the server 6901 are loaded into the memory 6802 of the information processing apparatus 6902. The server 6901 generates a carrier signal for carrying the program and data, and transmits the carrier signal to the information processing device 6902 via an arbitrary transmission medium on the communication network. The CPU 6801 executes the program using the data and performs the above-described processing.

 Industrial applicability

[0140] According to the present invention, it is possible to embed a copy-forgery-inhibited pattern watermark even in a document including a large number of characters, figures, photographs, and the like. In addition, even if a printed document with embedded transparency is copied for several generations, or even a printed matter that does not have the paper remaining force, the watermark with embedded force can be detected stably.

Claims

The scope of the claims  [1] A computer program for embedding information in a background area of a document image using a dot pattern,  A plurality of watermark symbols expressed by different dot patterns are assigned to the embedded information, and the embedded information is converted into a watermark symbol sequence,  Embedding a watermark symbol selected from the column of transparency symbols in an embedding target area in the document image and checking whether the embedded watermark symbol is detected;  When the embedded watermark symbol is detected, it is determined that the embedding target area can be embedded, and when the embedded transparency symbol is not detected, it is determined that the embedding target area cannot be embedded,  A watermarked document image is generated by embedding the selected watermark symbol in an embedding target area determined to be embedding.  A program for causing a computer to execute processing.  [2] In the embedding target area determined as non-embeddable, a symbol represented by a dot pattern different from the plurality of transparent symbols, or a transparent card selected at random from the plurality of watermark symbols. 2. The program according to claim 1, which causes the computer to execute a process of embedding a fraud symbol.  [3] When the selected permeability symbol is embedded in the embedding target area, it is checked whether or not the position of the blank area included in the embedded permeability symbol is detected. 3. The program according to claim 1, wherein the computer is caused to execute a process of checking whether or not an embedded transparency symbol is detected. [4] The watermark symbol sequence is divided into a plurality of watermark blocks, and a head symbol indicating the head and the order of each transparent block in the plurality of transparent blocks are indicated at the beginning of each watermark block. A watermark packet is generated by adding one or more symbols, and the symbol selected from the watermark packet is embedded in the embedding target area determined to be embedding, and generated from the plurality of watermark blocks. Before multiple watermark packets The program according to claim 1 or 2, wherein the computer is caused to execute processing for embedding in a document image.  [5] Classifying a plurality of embedding target areas determined to be embedding into a plurality of categories, and embedding a symbol selected from the watermark packet in the embedding target area by a different embedding method for each category, 5. The program according to claim 4, characterized in that the program is executed.  [6] Cause the computer to execute a process of embedding the plurality of watermark packets in an area composed of a plurality of embedding target areas classified into a category indicating that all of the plurality of watermark packets can be inserted. The program according to claim 5, wherein:  [7] Processing to embed one watermark packet selected from the plurality of watermark packets in an area composed of a plurality of embedding target areas classified into a category indicating that one watermark packet can be inserted 6. The program according to claim 5, wherein the program is executed by the computer.  [8] A part of one watermark packet selected from the plurality of watermark packets in an area composed of a plurality of embedding target areas classified into a category indicating that a part of one watermark packet can be inserted. 6. The program according to claim 5, wherein the computer is caused to execute a process of embedding.  [9] A process of reversing the order of symbols included in the selected one watermark packet with a predetermined probability and embedding a part of the obtained watermark packet in an area having the plurality of embedding target area powers, The program according to claim 8, wherein the program is executed by the computer. [10] The plurality of categories one includes a first category indicating that all of the plurality of watermark packets can be inserted, and a second force category indicating that one watermark packet can be inserted, and A third category indicating that a part of one watermark packet can be inserted, and a fourth category other than the first, second, and third categories. Processing to embed a symbol represented by a dot pattern different from the plurality of watermark symbols or a watermark symbol randomly selected from the plurality of watermark symbols into the embedding target area classified into the four categories The above 6. The program according to claim 5, wherein the program is executed by a computer. [11] A transparency management packet including a plurality of symbols indicating the number of the plurality of watermark blocks and the size of each watermark block is generated, and the watermark management packet is selected from the watermark management packets determined to be embedded. 5. The program according to claim 4, wherein the computer is caused to execute a process of embedding a symbol that has been processed.  [12] A computer program for embedding information in a background area of a document image using a dot pattern,  A plurality of watermark symbols expressed by different dot patterns are assigned to the embedded information, and the embedded information is converted into a watermark symbol sequence,  The watermark symbol sequence is divided into a plurality of watermark blocks, and at the beginning of each watermark block, a leading symbol indicating the head and one or more indicating the order of each transparent block in the plurality of transparent blocks To generate a watermark packet,  Embeds multiple watermark packets with multiple transparency and block power in the document image to generate a watermarked document image  A program for causing a computer to execute processing. [13] A transparency management packet including a plurality of symbols indicating the number of the plurality of watermark blocks and the size of each watermark block is generated, and is selected from the watermark management packet as an embedding target area determined to be embeddable. 13. The program according to claim 12, which causes the computer to execute a process of embedding a symbol that has been processed. [14] A digital watermark embedding device that embeds information in a background area of a document image using a dot pattern,  A document image input unit for inputting the document image;  A watermark converting unit that assigns a plurality of watermark symbols each represented by a different dot pattern to the embedded information, and converts the embedded information into a watermark symbol sequence; A watermark symbol is embedded in an area in the document image, and it is checked whether or not the embedded watermark symbol is detected. If the transparent symbol is detected, it is determined that the area can be embedded. If the transparent symbol is not detected, the region is embedded A watermark embedding availability determining unit that determines that it is impossible;  The position information of the embedding target area in the document image and the information of the transparency symbol selected from the watermark symbol column are passed to the watermark embedding possibility determination section, the determination result is received, and it is determined that embedding is possible An electronic transparency embedding device comprising: a transparency embedding unit that embeds the selected transparency symbol in an embedding target region to generate a watermarked document image.  [15] The watermark embedding unit may embed a symbol represented by a dot pattern different from the plurality of transparent symbols in the embedding target area determined to be non-embeddable, or the medium power of the plurality of watermark symbols. 15. The digital watermark embedding apparatus according to claim 14, wherein the selected watermark symbol is embedded in.  [16] The watermark embedding possibility determination unit determines whether or not the position of the blank area included in the embedded watermark symbol is detected when the selected transparent symbol is embedded in the embedding target area. 16. The digital watermark embedding apparatus according to claim 14, wherein it is checked whether or not the embedded transparency symbol is detected by checking.  [17] The watermark symbol sequence is divided into a plurality of watermark blocks, and a head symbol indicating the head and the order of each transparent block in the plurality of transparent blocks are indicated at the beginning of each watermark block. A watermark packetizing unit that adds one or more symbols to generate a watermark packet is further included, and the transparency embedding unit adds the watermark packet to the embedding target area determined to be embedding from the watermark packet. 16. The digital watermark embedding apparatus according to claim 14 or 15, wherein a plurality of watermark packets in which the plurality of permeability block forces are also embedded are embedded in the document image by embedding the selected symbol.  [18] The method further comprises a watermark category extraction unit that classifies a plurality of embedding target areas determined to be embedding into a plurality of categories, and the watermark embedding unit is selected from the watermark packet by an embedding method different for each category. 18. The electronic permeability embedding apparatus according to claim 17, wherein the embedded symbol is embedded in the embedding target area.