Data embedding and extraction techniques for documents

• US 6,731,775 B1
• Filed: 09/11/2000
• Issued: 05/04/2004
• Est. Priority Date: 08/18/1998
• Status: Expired due to Term

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Ancin, Hakan
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Miller, Ryan J.
• Application Number:
  US09/659,479
• Time in Patent Office: 1,331 Days
• Field of Search: 382/100, 382/232, 382/176, 380/210, 380/287, 380/252, 380/54, 713/176
• US Class Current: 382/100
• CPC Class Codes: H04N 1/32144 embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 2201/0091 Digital copier; digital 'photocopier' H04N2201/0093 and H04N2201/0094 take precedence
• CPC Class Codes: H04N 2201/3235 Checking or certification of the authentication information, e.g. by comparison with data stored independently
• CPC Class Codes: H04N 2201/3236 Details of authentication information generation
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

Improved data embedding and extracting techniques provide a way to embed and extract messages in text sections of documents during copying. Extracted text pixels are grouped together to form text lines of the document. From this formation, a document layout is constructed that is used to embed the message in the text pixels. Each text line is partitioned into blocks, and those of which contain a certain threshold percentage of text pixels are identified as valid. Each valid block is used to embed one bit of information by labeling text pixels of that block with a certain predetermined color. The embedding of bits in valid blocks in a particular text line is done in a column-wise raster order. Only one message character (which may be comprised of multiple bits) is embedded in a particular text line, although that character may be embedded multiple times in the same line if there are enough valid blocks. Extracting a message so embedded involves forming a first representation of the document in which pixels are classified to locate blocks of pixels in which data is embedded, forming a second representation of the document to extract text lines and identify text pixels. These two representations are compared to identify clusters of color-labeled pixels in each text line to determine the location of embedded bits of the message. The clusters in each text line are sorted in accordance with the predetermined embedding order and converted into a sequence of bits which are decoded to determine the message character embedded in each text line.

Claims

1. A method for embedding a message in a text-containing document, comprising the steps of:

obtaining a pixel representation of the document;

identifying text pixels of the document;

determining each text line of the document;

partitioning each determined text line into a plurality of blocks;

identifying each block as valid if that block contains at least a predetermined percentage of text pixels and that block is not an immediate neighbor of a block already identified as valid; and

embedding a binary element in each valid block by labeling text pixels within that block with a first color or a second color to embed the message in the document.

2. The method of claim 1, wherein the step of embedding is carried out text line-by-text line.

3. The method of claim 2, wherein the message comprises at least one character which comprises at least one binary element, and only one character is embedded in each text line.

4. The method of claim 3, wherein a character embedded in a particular text line is repetitively embedded in that text line.

5. The method of claim 3, wherein a character is embedded in more than one text line.

6. The method of claim 2, wherein each valid block of a particular text line has a predetermined embedding order.

7. The method of claim 6, wherein the predetermined order is a column-wise raster order.

8. The method of claim 2, wherein the message comprises at least one character, each of which is comprised of a first binary element sequence, each of the first binary elements being comprised of a second binary element sequence.

9. A method for extracting a message embedded in text of a document, comprising the steps of:

obtaining a pixel representation of the document;

forming a first representation of the document in which pixels are classified to locate blocks of pixels in which data is embedded;

forming a second representation of the document to extract text lines and identify text pixels;

comparing the second representation with the first representation to identify clusters of first and second colored pixels in each text line to determine the location of embedded binary elements of the message;

sorting the identified first and second colored clusters in each text line in accordance with a predetermined embedding order;

converting the sorted first and second colored clusters in each text line into a sequence of binary elements; and

decoding the sequence of binary elements in each text line to determine an embedded character of the message.

10. The method of claim 9, wherein the sequence of binary elements in each text line is comprised of a plurality of subsets of binary elements, each of which is representative of a character of the message, and wherein the step of decoding comprises performing majority voting in each text line to determine the character of the message embedded in that text line.

11. The method of claim 9, wherein the step of forming the first representation comprises filtering and sharpening the pixel representation of the document.

12. The method of claim 11, wherein each pixel of the pixel representation of the document comprises multiple color components to define corresponding multiple color planes, and wherein the filtering is applied on each color plane.

13. The method of claim 12, wherein the step of forming the first representation comprises classifying each of the pixels of the document as a first colored pixel, a second colored pixel, or neither.

14. The method of claim 9, wherein the step of forming the second representation comprises thresholding the pixel representation of the document to identify text pixels.

15. An apparatus for embedding a message in a text-containing document, the apparatus comprising:

a scanner that outputs a pixel representation of the document;

a text pixel identifying circuit, in communication with the scanner;

a text line determining circuit, in communication with the text pixel identifying circuit;

a block partitioning circuit in communication with the text pixel identifying circuit and the text line determining circuit;

a valid block identifying circuit, in communication with the text pixel identifying circuit and the block partitioning circuit, the valid block identifying circuit being configured to identify each block as valid if that block contains at least a predetermined percentage of text pixels and that block is not an immediate neighbor of a block already identified as valid; and

a binary element embedding circuit in communication with the text pixel identifying circuit and the valid block identifying circuit.

16. The apparatus of claim 15, wherein the text pixel identifying circuit, the text line determining circuit, the block partitioning circuit, the valid block identifying circuit, and the binary element embedding circuit are embodied as a single integrated circuit.

17. The apparatus of claim 15, wherein the text pixel identifying circuit, the text line determining circuit, the block partitioning circuit, the valid block identifying circuit, and the binary element embedding circuit are physically distinct circuits.

18. An apparatus for extracting a message embedded in text of a document, the apparatus comprising:

a scanner that outputs a pixel representation of the document;

a first circuit, in communication with the scanner, that forms a first representation of the document in which pixels are classified to locate blocks of pixels in which data is embedded;

a second circuit, in communication with the first circuit, that forms a second representation of the document to extract text lines and identify text pixels;

a comparator circuit, in communication with the first and second circuits, that compares the second representation with the first representation to identify clusters of first and second colored pixels in each text line to determine the location of embedded binary elements of the message; and

an extracting circuit, in communication with the comparator circuit that

sorts the identified first and second colored clusters in each text line in accordance with a predetermined embedding order,

converts the sorted first and second colored clusters in each text line into a sequence of binary elements, and

decodes the sequence of binary elements in each text line to determine an embedded character of the message.

19. The apparatus of claim 18, wherein the first circuit, the second circuit, the comparator circuit, and the extracting circuit are embodied as a single integrated circuit.

20. The apparatus of claim 18, wherein the first circuit, the second circuit, the comparator circuit, and the extracting circuit are physically distinct circuits.

21. A machine-readable medium embodying a program of instructions for causing a machine to perform a method of embedding a message in a text-containing document, the program of instructions comprising instructions for:

obtaining a pixel representation of the document;

identifying text pixels of the document;

determining each text line of the document;

partitioning each determined text line into a plurality of blocks;

identifying each block as valid if that block contains at least a predetermined percentage of text pixels and that block is not an immediate neighbor of a block already identified as valid; and

embedding a binary element in each valid block by labeling text pixels within that block with a first color or a second color to embed the message in the document.

22. The machine-readable medium of claim 21, wherein the step of embedding is carried out text line-by-text line.

23. The machine-readable medium of claim 22, wherein the message comprises at least one character which comprises at least one binary element, and only one character is embedded in each text line.

24. The machine-readable medium of claim 23, wherein a character embedded in a particular text line is repetitively embedded in that text line.

25. The machine-readable medium of claim 23, wherein a character is embedded in more than one text line.

26. The machine-readable medium of claim 22, wherein each valid block of a particular text line has a predetermined embedding order.

27. The machine-readable medium of claim 26, wherein the predetermined order is a column-wise raster order.

28. The machine-readable medium of claim 22, wherein the message comprises at least one character, each of which is comprised of a first binary element sequence, each of the first binary elements being comprised of a second binary element sequence.

29. A machine-readable medium embodying a program of instructions for causing a machine to perform a method of extracting a message embedded in text of document, the program of instructions comprising instructions for:

obtaining a pixel representation of the document;

forming a first representation of the document in which pixels are classified to locate blocks of pixels in which data is embedded;

forming a second representation of the document to extract text lines and identify text pixels;

comparing the second representation with the first representation to identify clusters of first and second colored pixels in each text line to determine the location of embedded binary elements of the message;

sorting the identified first and second colored clusters in each text line in accordance with a predetermined embedding order;

converting the sorted first and second colored clusters in each text line into a sequence of binary elements; and

decoding the sequence of binary elements in each text line to determine an embedded character of the message.

30. The machine-readable medium of claim 29, wherein the sequence of binary elements in each text line is comprised of a plurality of subsets of binary elements, each of which is representative of a character of the message, and wherein the step of decoding comprises performing majority voting in each text line to determine the character of the message embedded in that text line.

31. The machine-readable medium of claim 29, wherein the step of forming the first representation comprises filtering and sharpening the pixel representation of the document.

32. The machine-readable medium of claim 31, wherein each pixel of the pixel representation of the document comprises multiple color components to define corresponding multiple color planes, and wherein the filtering is applied on each color plane.

33. The machine-readable medium of claim 32, wherein the step of forming the first representation comprises classifying each of the pixels of the document as a first colored pixel, a second colored pixel, or neither.

34. The machine-readable medium of claim 29, wherein the step of forming the second representation comprises thresholding the pixel representation of the document to identify text pixels.

35. An apparatus for embedding a message in a text-containing document, the apparatus comprising:

means for outputting a pixel representation of the document;

means, in communication with the outputting means, for identifying text pixels of the document;

means, in communication with the identifying means, for determining each text line of the document;

means, in communication with the identifying means and the determining means, for partitioning each determined text line into a plurality of blocks;

means, in communication with the identifying means and the partitioning means, for classifying each block as valid if that block contains at least a predetermined percentage of text pixels and if that block is not an immediate neighbor of a block already identified as valid; and

means, in communication with the identifying means and the classifying means, for embedding a binary element in each valid block by labeling text pixels within that valid block with a first color or a second color to embed the message in the document.

36. The apparatus of claim 35, wherein the identifying means, the determining means, the partitioning means, the classifying means, and the embedding means are embodied as a single integrated circuit.

37. The apparatus of claim 35, wherein the identifying means, the determining means, the partitioning means, the classifying means, and the embedding means are physically distinct circuits.

38. An apparatus for extracting a message embedded in text of a document, the apparatus comprising:

means for outputting a pixel representation of the document;

means, in communication with the scanner, for forming a first representation of the document in which pixels are classified to locate blocks of pixels in which data is embedded;

means, in communication with the first representation forming means, for forming a second representation of the document to extract text lines and identify text pixels;

means, in communication with the first and second representation forming means, for comparing the second representation with the first representation to identify clusters of first and second colored pixels in each text line to determine the location of embedded binary elements of the message; and

extracting means, in communication with the comparing means, for

sorting the identified first and second colored clusters in each text line in accordance with a predetermined embedding order,

converting the sorted first and second colored clusters in each text line into a sequence of binary elements, and

decoding the sequence of binary elements in each text line to determine an embedded character of the message.

39. The apparatus of claim 38, wherein the first representation forming means, the second representation forming means, the comparing means, and the extracting means are embodied as a single integrated circuit.

40. The apparatus of claim 38, wherein the first representation forming means, the second representation forming means, the comparing means, and the extracting means are embodied as a single integrated circuit.