# US 2002/0172395 A1 · Systems and methods for embedding data by dimensional compression and expansion

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

- Number: US 2002/0172395 A1
- Document ID: US20020172395A1
- Status: Published application
- Kind: A1
- Application number: 10/104,017
- Filed: 2002-03-25
- Published: 2002-11-21
- Earliest claimed: 2001-03-23
- Assignees: Fuji Xerox Co., Ltd.
- Inventors: Jonathan T. Foote; John E. Adcock
- Web page: https://patentgrep.com/patent/US20020172395A1

## CPC

- G06T 1/0085: {Time domain based watermarking, e.g. watermarks spread over several images}
- G06T 1/0057: {Compression invariant watermarking}
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

The systems and methods of this invention watermark an original data file using dimensional compression and expansion. The original data file extends along a given dimension and has portions that extend along that given dimension. The information is embedded into the data file by selectively dimensionally compressing or expanding a size of each of some or all of the portions along the given dimension, which can be space or time. The portions of the data file are selectively dimensionally expanded or compressed according to a given encoding scheme. This encoding scheme can use the kind of modification, the relationships between the type of modification between adjacent portions, or the duration or degree of compression or expansion to store a portion of the embedded information. The portions of the embedded information can be individual bits of binary or trinary information, or can be a portion of analog information.

## Claims

### Claim 1

A method for embedding a first set of data into a second set of data, the second set of data having at least one dimension along which the data of the second set extends, the method comprising:
dividing the second set of data into a plurality of portions, each of the plurality of portions having an extent along at least a first one of the at least one dimension;
generating a pattern of compression and expansion regions that encode the first set of data; and
selectively dimensionally compressing and expanding the extents of at least some of the portions of the second set of data along at least the first dimension according to the pattern of compression and expansion regions to embed the first set of data into the second set of data.

### Claim 2 (depends on 1)

The method of claim 1, further comprising, prior to selectively dimensionally compressing and expanding the extends of at least some of the portions of the second set of data:
analyzing the second set of data to determine a predicted tempo for each of the plurality of portions; and
modifying, for each of the plurality of portions of the second set of data, an actual tempo for that portion so that the actual tempo for that portion matches the predicted tempo for that portion.

### Claim 3 (depends on 2)

The method of claim 2, wherein analyzing the second set of data to determine the predicted tempo for each of the plurality of portions comprises determining the predicted tempo based on a predetermined function for the tempo.

### Claim 4 (depends on 3)

The method of claim 3, wherein the predetermined function for the tempo is a constant tempo.

### Claim 5 (depends on 3)

The method of claim 3, wherein the predetermined function is at least one of a periodic function and a predictable function.

### Claim 6 (depends on 1)

The method of claim 1, wherein the first set of data is a watermark.

### Claim 7 (depends on 6)

The method of claim 6, wherein the watermark identifies at least one of a source, a time of creation, a location of creation, an identification value, an identification name, a creator name and an owner name.

### Claim 8 (depends on 1)

The method of claim 1, wherein the second set of data is at least one of audio data and video data and the first dimension is time.

### Claim 9 (depends on 1)

The method of claim 1, wherein:
the second set of data is at least one of still image data and video data;
the at least one dimension is at least a first spatial dimension;
dividing the second set of data into a plurality of portions comprises dividing the second set of data into a plurality of portions that extend along the first spatial dimension; and
selectively dimensionally compressing and expanding the extents of at least some of the portions of the second set of data along at least the first dimension comprises selectively dimensionally compressing and expanding the extents of at least some of the portions of the second set of data along the first spatial dimension.

### Claim 10 (depends on 1)

The method of claim 1, wherein:
the second set of data is at least one of still image data and video data;
the at least one dimension comprises a first spatial dimension and a second spatial dimension;
dividing the second set of data into a plurality of portions comprises dividing the second set of data into a plurality of portions that extend along an axis that has components along each of the first spatial dimension and the second spatial dimension; and
selectively dimensionally compressing and expanding the extents of at least some of the portions of the second set of data along at least the first dimension comprises selectively dimensionally compressing and expanding the extents of at least some of the portions of the second set of data along the axis.

### Claim 11

A system that embeds a first set of data into a second set of data, the second set of data having at least one dimension along which the data of the second set extends, the second set of data having a plurality of portions, each of the plurality of portions having an extent along at least a first one of the at least one dimension, the system comprising:
a tempo map generating circuit or routine that generates a pattern of compression and expansion regions that encode the first set of data; and
a watermarking circuit or routine that selectively dimensionally compresses and expands the extents of at least some of the portions of the second set of data along at least the first dimension according to the pattern of compression and expansion regions to embed the first set of data into the second set of data.

### Claim 12 (depends on 11)

The system of claim 11, further comprising:
a tempo predicting circuit or routine that analyzes the second set of data and that determines a predicted tempo for each of the plurality of portions; and
a tempo altering circuit or routine that modifies, for each of the plurality of portions of the second set of data, an actual tempo for that portion so that the actual tempo for that portion matches the predicted tempo for that portion.

### Claim 13 (depends on 12)

The system of claim 12, wherein the tempo predicting circuit or routine determines the predicted tempo for each of the plurality of portions based on a predetermined function for the tempo.

### Claim 14 (depends on 13)

The system of claim 13, wherein the predetermined function for the tempo is a constant tempo.

### Claim 15 (depends on 13)

The system of claim 13, wherein the predetermined function is at least one of a periodic function and a predictable function.

### Claim 16 (depends on 11)

The system of claim 11, wherein the first set of data is a watermark.

### Claim 17 (depends on 16)

The system of claim 16, wherein the watermark identifies at least one of a source, a time of creation, a location of creation, an identification value, an identification name, a creator name and an owner name.

### Claim 18 (depends on 11)

The system of claim 11, wherein the second set of data is at least one of audio data and video data and the first dimension is time.

### Claim 19 (depends on 11)

The system of claim 11, wherein:
the second set of data is at least one of still image data and video data;
the at least one dimension is at least a first spatial dimension;
the second set of data is divided into a plurality of portions that extend along the first spatial dimension; and
the watermarking circuit or routine selectively dimensionally compresses and expands the extents of at least some of the portions of the second set of data along the first spatial dimension.

### Claim 20 (depends on 11)

The system of claim 11, wherein:
the second set of data is at least one of still image data and video data;
the at least one dimension comprises a first spatial dimension and a second spatial dimension;
the second set of data is divided into a plurality of portions that extend along an axis that has components along each of the first spatial dimension and the second spatial dimension; and
the watermarking circuit or routine selectively dimensionally compresses and expands the extents of at least some of the portions of the second set of data along the axis.

### Claim 21

A method for extracting a first set of data from a second set of data into which the first set of data has been embedded, the second set of data having at least one dimension along which the data of the second set extends and having a plurality of portions, each of the plurality of portions having an extent along at least a first one of the at least one dimension, the method comprising:
comparing the second set of data in which the first set of data has been embedded to a reference copy of the second set of data that does not contain the first set of data;
generating a pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions that encodes the first set of data based on the comparison; and
converting the pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions into the first set of data.

### Claim 22 (depends on 21)

The method of claim 21, wherein comparing the second set of data in which the first set of data has been embedded to the reference copy of the second set of data that does not contain the first set of data comprises:
generating a first set of representational data from the second set of data in which the first set of data has been embedded;
generating a second set of representational data from the second set of data that does not contain the first set of data; and
comparing the first set of representational data to the second set of representational data.

### Claim 23 (depends on 22)

The method of claim 22, wherein the first and second sets of representational data are first and second spectrograms.

### Claim 24 (depends on 21)

The method of claim 21, wherein the first set of data is a watermark.

### Claim 25 (depends on 24)

The method of claim 24, wherein the watermark identifies at least one of a source, a time of creation, a location of creation, an identification value, an identification name, a creator name and an owner name.

### Claim 26 (depends on 21)

The method of claim 21, wherein the second set of data is at least one of audio data and video data and the first dimension is time.

### Claim 27 (depends on 21)

The method of claim 21, wherein:
the second set of data is at least one of still image data and video data; and
the at least one dimension is at least a first spatial dimension.

### Claim 28 (depends on 21)

The method of claim 21, wherein:
the second set of data is at least one of still image data and video data;
the at least one dimension comprises a first spatial dimension and a second spatial dimension;
the second set of data comprises a plurality of portions that extend along an axis that has components along each of the first spatial dimension and the second spatial dimension; and
comparing the second set of data in which the first set of data has been embedded to a reference copy of the second set of data that does not contain the first set of data comprises comparing the econd set of data in which the first set of data has been embedded to a reference copy of the second set of data that does not contain the first set of data along the axis.

### Claim 29 (depends on 21)

The method of claim 21, wherein converting the pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions into the first set of data comprises comparing at least a portion of the pattern to at least one template.

### Claim 30 (depends on 29)

The method of claim 29, wherein the at least one template is at least one predetermined template.

### Claim 31 (depends on 29)

The method of claim 29, further comprising estimating the at least one template.

### Claim 32 (depends on 21)

The method of claim 21, wherein converting the pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions into the first set of data comprises comparing each portion of the pattern to at least one threshold.

### Claim 33 (depends on 32)

The method of claim 32, wherein the at least one threshold is at least one predetermined threshold.

### Claim 34 (depends on 32)

The method of claim 32, further comprising estimating the at least one threshold.

### Claim 35

A method for extracting a first set of data from a second set of data into which the first set of data has been embedded, the second set of data having at least one dimension along which the data of the second set extends and having a plurality of portions, each of the plurality of portions having an extent along at least a first one of the at least one dimension, the method comprising:
determining, for each portion of the second set of data, a predicted tempo for that portion;
determining, for each portion of the second set of data, an actual tempo;
comparing, for each portion, the predicted tempo to the actual tempo for that portion;
generating a pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions that encodes the first set of data based on the comparisons for the plurality of portions; and
converting the pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions into the first set of data.

### Claim 36 (depends on 35)

The method of claim 35, wherein determining, for each portion of the second set of data, the predicted tempo for that portion comprises analyzing the second set of data to based on a predetermined function.

### Claim 37 (depends on 36)

The method of claim 36, wherein the predetermined function is a constant tempo.

### Claim 38 (depends on 36)

The method of claim 36, wherein the predetermined function is at least one of a periodic function and a predictable function.

### Claim 39

A system that extracts a first set of data from a second set of data into which the first set of data has been embedded, the second set of data having at least one dimension along which the data of the second set extends and having a plurality of portions, each of the plurality of portions having an extent along at least a first one of the at least one dimension, the system comprising:
a comparison circuit or routine that compares the second set of data in which the first set of data has been embedded to a reference copy of the second set of data that does not contain the first set of data;
a tempo generating circtuit or routine that determines a pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions that encodes the first set of data based on the comparison; and
a watermark decoding circuit or routine that converts the pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions into the first set of data.

### Claim 40 (depends on 39)

The system of claim 39, wherein the comparison circuit or routine compares the second set of data in which the first set of data has been embedded to the reference copy of the second set of data that does not contain the first set of data by:
generating a first set of representational data from the second set of data in which the first set of data has been embedded;
generating a second set of representational data from the second set of data that does not contain the first set of data; and
comparing the first set of representational data to the second set of representational data.

### Claim 41 (depends on 40)

The system of claim 40, wherein the first and second sets of representational data are first and second spectrograms.

### Claim 42 (depends on 39)

The system of claim 39, wherein the first set of data is a watermark.

### Claim 43 (depends on 42)

The system of claim 42, wherein the watermark identifies at least one of a source, a time of creation, a location of creation, an identification value, an identification name, a creator name and an owner name.

### Claim 44 (depends on 39)

The system of claim 39, wherein the second set of data is at least one of audio data and video data and the first dimension is time.

### Claim 45 (depends on 39)

The system of claim 39, wherein:
the second set of data is at least one of still image data and video data; and
the at least one dimension is at least a first spatial dimension.

### Claim 46 (depends on 39)

The system of claim 39, wherein:
the second set of data is at least one of still image data and video data;
the at least one dimension comprises a first spatial dimension and a second spatial dimension;
the second set of data comprises a plurality of portions that extend along an axis that has components along each of the first spatial dimension and the second spatial dimension; and
the comparison circuit or routine compares the second set of data in which the first set of data has been embedded to a reference copy of the second set of data that does not contain the first set of data along the axis.

### Claim 47 (depends on 39)

The system of claim 39, wherein the watermark decoding circuit or routine converts the pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions into the first set of data by comparing at least a portion of the pattern to at least one template.

### Claim 48 (depends on 47)

The system of claim 47, wherein the at least one template is at least one predetermined template.

### Claim 49 (depends on 47)

The system of claim 47, further comprising estimating the at least one template.

### Claim 50 (depends on 39)

The system of claim 39, wherein the watermark decoding circuit or routine converts the pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions into the first set of data by comparing each portion of the pattern to at least one threshold.

### Claim 51 (depends on 50)

The system of claim 50, wherein the at least one threshold is at least one predetermined threshold.

### Claim 52 (depends on 50)

The system of claim 50, further comprising estimating the at least one threshold.

### Claim 53

A system for extracting a first set of data from a second set of data into which the first set of data has been embedded, the second set of data having at least one dimension along which the data of the second set extends and having a plurality of portions, each of the plurality of portions having an extent along at least a first one of the at least one dimension, the system comprising:
a tempo predicting circuit or routine that determines, for each portion of the second set of data, a predicted tempo for that portion;
a tempo determining circuit or routine that determines, for each portion of the second set of data, an actual tempo;
a comparison circuit or routine that compares the predicted tempo to the actual tempo for that portion;
a tempo generating circtuit or routine that determines a pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions that encodes the first set of data based on the comparisons for the plurality of portions; and
a watermark decoding circuit or routine that converts the pattern of dimensionally compressed and dimensionally expanded ones of the plurality portions into the first set of data.

### Claim 54 (depends on 53)

The system of claim 53, wherein determining, for each portion of the second set of data, the predicted tempo for that portion comprises analyzing the second set of data to based on a predetermined function.

### Claim 55 (depends on 54)

The system of claim 54,wherein the predetermined function is a constant tempo.

### Claim 56 (depends on 54)

The system of claim 54,wherein the predetermined function is at least one of a periodic function and a predictable function.
