Automatic detection and retrieval of embedded invisible digital watermarks from halftone images

• US 6,263,086 B1
• Filed: 04/15/1998
• Issued: 07/17/2001
• Est. Priority Date: 04/15/1998
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Wang, Shen-ge
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): MILLER, MARTIN E
• Application Number:
  US09/060,469
• Time in Patent Office: 1,189 Days
• Field of Search: 382/100, 382/232, 382/278, 382/295, 380/54, 380/210
• US Class Current: 382/100
• CPC Class Codes: G06T 1/005 Robust watermarking, e.g. average attack or collusion attack resistant
• CPC Class Codes: G06T 2201/0061 Embedding of the watermark in each block of the image, e.g. segmented watermarking
• CPC Class Codes: G06T 2201/0065 Extraction of an embedded watermark; Reliable detection
• CPC Class Codes: H04N 1/32149 Methods relating to embedding, encoding, decoding, detection or retrieval operations
• CPC Class Codes: H04N 1/32256 in halftone data
• CPC Class Codes: H04N 2201/3205 of identification information, e.g. name or ID code H04N2201/3209 takes precedence
• CPC Class Codes: H04N 2201/3211 of a company logo or the like
• CPC Class Codes: H04N 2201/3226 of identification information or the like, e.g. ID code, index, title, part of an image, reduced-size image
• CPC Class Codes: H04N 2201/3233 of authentication information, e.g. digital signature, watermark
• CPC Class Codes: H04N 2201/327 which are undetectable to the naked eye, e.g. embedded codes

Abstract

A system for automatic detection and retrieval of embedded invisible digital watermarks retrieves digital watermarks from halftone images. Specifically, by supplying an image to the system, through a process of autocorrelation and shifting, the embedded invisible watermark becomes visible. The process includes scarning or supplying an image to the system, calculating the global autocorrelation of the image, selecting a moving window size, conducting a piecewise localized autocorrelation for each window-sized portion of the image, retrieving the embedded, initially invisible, watermarks, normalizing the resultant image for visualization and displaying the resultant image with the now visible retrieved embedded digital watermarks.

Claims

1. A method for recovering an embedded invisible digital watermark from an image, comprising:

determining a global autocorrelation of the image;

selecting a window having a determined size;

selecting a current portion of the image corresponding to the size of the window;

determining a piecewise localized autocorrelation of the image for the current portion;

generating a shifted image for the current portion;

retrieving the embedded watermarks for the current portion;

repeating the portion selecting, determining, generating and retrieving steps for a new current portion until the entire image has been analyzed; and

generating a new image containing the retrieved watermarks.

2. The method of claim 1, wherein determining the global autocorrelation comprises:

searching the image for autocorrelation peaks;

determining if the image is a halftone; and

estimating a size and orientation of the halftone.

3. The method of claim 1, wherein selecting the window comprises determining the window size, the determined window size being large enough to ensure a portion of two adjacent correlated halftone patterns is contained within the window.

4. The method of claim 1, wherein selecting the portion of the image corresponding to the size of the window comprises cropping the image at the current position to the size of the window.

5. The method of claim 1, wherein determining the piecewise localized autocorrelation for the current portion comprises:

determining a mean of the current portion;

subtracting the mean from the current portion;

determining a local autocorrelation of the current portion;

locating a local peak of the current portion near a point estimated by the global autocorrelation; and

determining a maximal autocorrelation position for the current portion.

6. The method of claim 5, wherein determining the maximal correlation comprises using either the global autocorrelation or a parabolic interpolation to estimate the local peak for the current portion.

7. The method of claim 6, wherein the parabolic interpolation comprises:

8. The method of claim 1, wherein generating the shifted image comprises:

9. The method of claim 1, further comprising inputting the image.

26. The method of claim 1, further including generating the image from which the watermark is to be recovered using an input interface and an image input device and generating the new image using an image output interface and an image output device.

27. The method of claim 26, wherein the step of generating the image includes using one of a digitizer, a scanner, a digital photocopier, a digital camera, or a video camera.

28. The method of claim 26, wherein the step of generating the new image includes using one of a printer, a monitor, a plotter, a digitally photocopier or video projector.

29. The method of claim 26, wherein using an image input image output device or an input/output interface includes using one of a server of a local network, a node of a local area network, a node of a wide area network, a node of an intranet, a node of the Internet, and a node of a distributed network.

10. A recovery system that retrieves embedded invisible digital watermarks from an image comprising:

input means for inputting the image;

global autocorrelation means for determining a global autocorrelation for the image;

piecewise autocorrelation means for determining a piecewise autocorrelation for each of a plurality of portions of the image;

shifting means for generating a shifted version for each of the plurality of portions of the image based on the piecewise local autocorrelation;

new image generation means for generating, based on the plurality of portions of the corresponding shifted versions, a new image containing retrieved watermarks; and

output means for displaying the new image containing the retrieved watermark.

11. The system of claim 10, wherein the global autocorrelation means further comprises:

searching means for searching the image for peaks;

determining means for determining if the image is a halftone; and

estimating means for estimating a size and orientation of the halftone.

12. The system of claim 10, wherein the piecewise autocorrelation means further comprises:

positioning means for moving a window across the image;

selecting means for cropping the image based on a position of the window to form the plurality of portions;

determining means for determining, for each portion, a mean of that portion;

subtracting means for subtracting, for each portion, the determined mean for that portion from that portion;

determining means for determining, for each portion, a localized autocorrelation for that portion; and

searching means for searching for, for each portion, an autocorrelation peak near a point estimated by the global autocorrelation for that portion.

13. The system of claim 12, further comprising decision means for deciding, for each portion, whether to use the global autocorrelation or a parabolic interpolation to estimate a localized autocorrelation peak.

14. The method of claim 13, wherein the parabolic interpolation comprises:

15. The method of claim 10, wherein generating the shifted image comprises:

30. The system of claim 10, further comprising

an input/output interface means;

an image input means; and

an image output means.

31. The system of claim 30, wherein the image input means is one of a digitizing means, a scanning means, a digital photocopying means, a digital camera means, or a video camera means.

32. The system of claim 30, wherein the image output means is one of a printing means, a monitoring means, a plotting means, a digital photocopying means, or a video projecting means.

33. The system of claim 30, wherein each of the image input means and the image output means is one of a server for a local area network, a node of a local area network, a node of a wide area network, a node of an intranet, a node of the Internet, and a node of a distributed network.

16. A system that extracts a digital watermark from an image based on a global and piecewise autocorrelation comprising a controller, a memory and an autocorrelator, wherein the autocorrelator comprises:

an global autocorrelator that determines a global autocorrelation of the image;

a moving window selector that selects a moving window;

a piecewise autocorrelator that determines a piecewise local autocorrelation of the image for each of a plurality of portions of the image;

a shifted image generator that generates a shifted version for each portion based on the corresponding piecewise autocorrelation;

a watermark retriever that retrieves a watermark for each portion based on that portion and the corresponding shifted image; and

an image visualizer that generates, based on the retrieved watermarks, a new image containing the retrieved visible watermarks.

17. The system of claim 16, wherein the global autocorrelator comprises:

a peak determiner that searches the image for peaks;

a halftone determiner that determines if the image is a halftone; and

a halftone estimator that estimates a size and orientation of the halftone.

18. The system of claim 17, wherein the autocorrelator comprises:

a moving window positioner that searches the image for peaks;

an image cropper that crops the image, based on the position of the moving window, to form the plurality of portions;

a mean determiner that determines, for each portion, a mean of that portion;

a mean subtractor that subtracts, for each portion, the mean for that portion from that portion;

a local autocorrelation determiner that determines, for each portion, a local autocorrelation for that portion; and

a correlation determiner that determines, for each portion, a maximal autocorrelation position of that portion.

19. The system of claim 18, wherein the correlation determiner determines the maximal correlation using either the global autocorrelation or a parabolic interpolation to estimate a localized autocorrelation peak.

20. The method of claim 19, wherein the parabolic interpolation comprises:

21. The method of claim 16, wherein generating the shifted image comprises:

22. The system of claim 16, further comprising:

an input/output interface;

an image input device; and

an image output device.

23. The system of claim 22, wherein the image input device is one of a digitizer, a scanner, a digital photocopier, a digital camera, or a video camera.

24. The system of claim 22, wherein the image output device is one of a printer, a monitor, a plotter, a digital photocopier, or video projector.

25. The system of claim 22, wherein each of the image input device and the image output device is one of a server of a local area network, a node of a local area network, a node of a wide area network, a node of an intranet, a node of the Internet, and a node of a distributed network.