System and method for hashing digital images

• US 6,671,407 B1
• Filed: 10/19/1999
• Issued: 12/30/2003
• Est. Priority Date: 10/19/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Koon, Say-Ming William, Venkatesan, Ramarathnam
• Primary Examiner(s): Do, Anh Hong
• Application Number:
  US09/421,986
• Time in Patent Office: 1,533 Days
• Field of Search: 382/232, 382/248, 382/251, 382/239, 382/224, 710/73, 711/164, 707/6, 345/582, 345/427, 345/606
• US Class Current: 382/232
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0052 Embedding of the watermark in the frequency domain
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking

Abstract

A system has an image store, a digital hashing unit, and a watermark encoder. A digital image hashing unit computes a hash value representative of a digital image in such a manner that visually similar images hash to the same hash value and visually distinct images hash to different values. The hash value is stored in an image hash table and is associated via the table with the original image. This image hash table can be used to index the image storage. A watermark encoder computes a watermark based on the hash value and a secret. Using both values renders the watermark resistant to BORE (Break Once, Run Everywhere) attacks because even if the global watermark secret is discovered, an attacker still needs the hash value of each image to successfully attack the image. The system can be configured to police the Internet to detect pirated copies. The system randomly collects images from remote Web sites and hashes the images using the same hashing function. The system then compares the image hashes to hashes of the original images. If the hashes match, the collected image is suspected as being a copy of the original.

Claims

1. A computer-implemented method for hashing an image, comprising:

transforming the image into an image transform;

randomly dividing the image transform into multiple tiles, each tile containing pixel data for multiple pixels;

averaging, for each of the tiles, the pixel data to produce corresponding tile averages;

generating, based in part on the tile averages, an exponential distribution having multiple distinct quantization levels;

randomly rounding each of the tile averages to one of the quantization levels to produce rounded values; and

hashing a composite of the rounded values.

2. A computer-implemented method as recited in claim 1, wherein the transforming is performed according to a transformation function selected from a group of functions comprising Fourier transform, a wavelet transform, and a DCT transform.

3. A computer-implemented method as recited in claim 1, wherein the transforming comprises decomposing the Image into multiple wavelet subbands.

4. A computer-implemented method as recited in claim 1, wherein the dividing comprises forming non-overlapping rectangular tiles.

5. A computer-implemented method as recited in claim 1, wherein the dividing comprises forming overlapping rectangular tiles.

6. A computer-implemented method as recited in claim 1, wherein the averaging comprises computing a variance of the pixel data in cases where the tile average is approximately zero.

7. A computer-implemented method as recited in claim 1, wherein the rounding comprises rounding toward a closer one of the quantization levels, but at a randomness that suggests an equal probability of rounding toward a farther one of the quantization levels.

8. A computer-implemented method as recited in claim 1, wherein the hashing comprises processing the rounded values to produce an intermediate hash value such that for visually distinct images, the intermediate hash values differ approximately 60% of the time and for visually similar images, the intermediate hash values agree in all but approximately 20% of the time.

9. A computer-implemented method as recited in claim 1, wherein the hashing comprises processing the rounded values using a Reed-Muller error correction code decoder.

10. A computer-implemented method as recited in claim 1, wherein the hashing comprises processing the rounded values using a Reed-Muller error correction code decoder with an exponential pseudo-random norm.

11. A computer-implemented method as recited in claim 1, wherein the hashing produces an intermediate hash value, further comprising reducing a size of the intermediate hash value via an error correction process.

12. A computer-implemented hashing method, comprising:

computing a hash value representative of a digital Image such that visually distinct images result in hash values that are approximately independent of one another and visually similar images result in identical hash values;

storing the hash value in relationship with the digital image;

watermarking the digital Image using, In part, the hash value to produce a watermarked image;

subsequently distributing the watermarked image over a network;

collecting an image from a remote site on the network;

computing a hash value of the image collected from the remote site;

comparing the hash value of the collected image with the stored hash value; and

identifying the collected image as a pirated version of the digital image if the hash values match.

13. A digital image hash system, comprising:

means for transforming an image into an image transform;

means for randomly dividing the image transform into multiple files, each tile containing pixel data for multiple pixels;

means for averaging, for each of the tiles, the pixel data to produce corresponding tile averages;

means for generating, based in part on the tile averages, an exponential distribution having multiple distinct quantization levels;

means for randomly rounding each of the tile averages to one of the quantization levels to produce rounded values; and

means for hashing a composite of the rounded values.

14. A computer-readable medium comprising computer-executable instructions, which when executed on a processor, direct a computer to:

transform an image into an image transform;

divide the image transform into multiple tiles, each tile containing pixel data for multiple pixels;

average, for each of the tiles, the pixel data to produce corresponding tile averages;

generate, based in part on the tile averages, an exponential distribution having multiple distinct quantization levels;

randomly round each of the tile averages to one of the quantization levels to produce rounded values; and

hash a composite of the rounded values.

15. A computer-readable medium as recited in claim 14, further comprising computer-executable instructions, which when executed on a processor, direct a computer to transform an image into an image transform by decomposing the image into multiple wavelet subbands.

16. A computer-readable medium as recited in claim 14, further comprising computer-executable instructions, which when executed on a processor, direct a computer to divide the image transform into multiple non-overlapping rectangular tiles.

17. A computer-readable medium as recited in claim 14, further comprising computer-executable instructions, which when executed on a processor, direct a computer to divide the image transform into multiple overlapping rectangular tiles.

18. A computer-readable medium as recited in claim 14, further comprising computer-executable instructions, which when executed on a processor, direct a computer to average, for each of the tiles, the pixel data to produce corresponding tile averages, wherein the averaging comprises computing a variance of the pixel data in cases where the tile average is approximately zero.

19. A computer-readable medium as recited in claim 14, further comprising computer-executable instructions, which when executed on a processor, direct a computer to randomly round each of the tile averages, wherein the rounding comprises rounding toward a closer one of the quantization levels, but at a randomness that suggests an equal probability of rounding toward a farther one of the quantization levels.