# US 6,731,775 B1 · Data embedding and extraction techniques for documents

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,731,775 B1
- Document ID: US6731775B1
- Status: Granted
- Kind: B1
- Application number: 09/659,479
- Filed: 2000-09-11
- Granted: 2004-05-04
- Earliest claimed: 1998-08-18
- Assignees: Seiko Epson Corporation
- Inventors: Hakan Ancin
- Web page: https://patentgrep.com/patent/US6731775B1

## CPC

- H04N 1/32144: {embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp}
- H04N 2201/0091: Digital copier; digital 'photocopier' (H04N2201/0093 and H04N2201/0094 take precedence)
- H04N 2201/3235: Checking or certification of the authentication information, e.g. by comparison with data stored independently
- H04N 2201/3236: Details of authentication information generation
- H04N 2201/327: which are undetectable to the naked eye, e.g. embedded codes
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 3)

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

### Claim 5 (depends on 3)

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

### Claim 6 (depends on 2)

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

### Claim 7 (depends on 6)

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

### Claim 8 (depends on 2)

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.

### Claim 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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 9)

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

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 9)

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.

### Claim 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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 15)

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.

### Claim 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.

### Claim 19 (depends on 18)

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.

### Claim 20 (depends on 18)

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

### Claim 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.

### Claim 22 (depends on 21)

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

### Claim 23 (depends on 22)

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.

### Claim 24 (depends on 23)

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

### Claim 25 (depends on 23)

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

### Claim 26 (depends on 22)

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

### Claim 27 (depends on 26)

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

### Claim 28 (depends on 22)

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.

### Claim 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.

### Claim 30 (depends on 29)

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.

### Claim 31 (depends on 29)

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.

### Claim 32 (depends on 31)

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.

### Claim 33 (depends on 32)

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.

### Claim 34 (depends on 29)

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.

### Claim 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.

### Claim 36 (depends on 35)

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.

### Claim 37 (depends on 35)

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.

### Claim 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.

### Claim 39 (depends on 38)

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.

### Claim 40 (depends on 38)

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.
