Method and system for data hiding and authentication via halftoning and coordinate projection

• US 20020171853A1
• Filed: 05/03/2001
• Published: 11/21/2002
• Est. Priority Date: 05/03/2001
• Status: Active Grant

• Current Assignee: X Corp. (f/k/a Twitter, Inc.) (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Wu, Chai Wah
• Granted Patent: US 7,006,254 B2
• Time in Patent Office: Days
• US Class Current: 358/1.9
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G07F 7/08 by coded identity card or credit card or other personal identification means without personal verification means G07F7/02
• CPC Class Codes: G07F 7/12 Card verification
• CPC Class Codes: H04N 1/32203 Spatial or amplitude domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32208 involving changing the magnitude of selected pixels, e.g. overlay of information or super-imposition H04N1/32219, H04N1/32224 take precedence
• CPC Class Codes: H04N 1/32256 in halftone data
• 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 method (and system) of embedding data into an image, includes producing an extended image using a halftoning algorithm on a collection of images, and projecting the extended image onto its first coordinates.

Claims

1. A method of embedding data into an image, comprising:

producing an extended image using a halftoning algorithm on a collection of images; and

projecting said extended image onto its first coordinates.

2. The method of claim 1, wherein auxiliary data is embedded into said image imperceptibly, such that data is embedded into said image, and uses halftoning to ensure that a resultant image looks substantially similar to the original image.

3. The method of claim 1, wherein a space of said extended image comprises a Cartesian product of several image spaces.

4. The method of claim 1, wherein said image is represented as matrices of vectors, such that said image M is represented by a n by m matrix M(i,j) of d-dimensional vectors, each pixel M(i,j) of said image is a d-dimensional vector, where d denotes a dimension of a color space.

5. The method of claim 4, wherein each d-dimensional vector is in the set {0,1, . . . , 255}^d.

6. The method of claim 1, wherein said image comprises a source image M₀, said method further comprising embedding auxiliary images M₁, . . . M_k, into M₀ imperceptibly.

7. The method of claim 6, wherein said embedding comprises:

selecting a set C of extended colors, wherein each member of the set C is a (k+1)-tuple of d-dimensional vectors, and wherein for a member D of the set C, each of the k+1 d-dimensional vectors of D is termed a “

coordinate”

of D where for D=(c₁, c₂, . . . , c_k+1) where each c₁ is a d-dimensional vector, the first, second, . . . , (k+1)-th coordinates of D are c₁, c₂, . . . c_k+1, respectively.

8. The method of claim 7, wherein the set C is chosen such that for each j in the set {0,1, . . . , 255}^d, there exists at most one member of C such that the first coordinate is j.

9. The method of claim 8, wherein the set C is of the same size as {0,1, . . . , 255}^d, such that for each j in the set {0,1, . . . , 255}^d, there exists exactly one member of C such that the first coordinate is j and the projection of C into its first coordinate results in a bijection.

10. The method of claim 9, further comprising:

for each pixel location (i,j), selecting said extended output image ExOut as a matrix of elements of C; and

generating an embedded source image M₀′

by taking a first coordinate of the entries of ExOut.

11. The method of claim 10, further comprising:

extracting the embedded images from M₀′

.

12. The method of claim 11, wherein said extracting comprises:

for each of the pixels M′

(i,j) of M₀′

, finding the element c(i,j) in the set C such that M′

(i,j) is the first coordinate; and

generating reconstructed embedded images M₁′

, M₂′

, . . . M_k′

by setting M_u′

(i,j) equal to the (u+1)-th coordinate of c(i,j) u=1, . . . , k,

wherein the embedded images M₀′

, M₁′

, M₂′

, . . . M_k′

form the coordinates of the extended output image ExOut.

13. The method of claim 12, further comprising:

ensuring that the images M₀′

, M₁′

, M₂′

, . . . M_k′

resemble M₀, M₁, M₂, . . . M_k

14. The method of claim 13, wherein an entire image is selectively embedded into the source image, and the embedded image is used for identifying a tampering of said source image.

15. The method of claim 13, wherein an entire image is selectively embedded into the source image, and the embedded image is used for localizing a tampering of said source image.

16. The method of claim 13, wherein an entire image is selectively embedded into the source image, and the embedded image is used for reversing tampering of said source image.

17. The method of claim 13, wherein an entire image is selectively embedded into the source image, and the embedded image is used for authentication of said source image.

18. The method of claim 1, wherein separate error diffusion algorithms are applied jointly to the embedded images and the source image, such that a choice of output colors is optimized.

19. The method of claim 7, wherein the set C is selectively chosen to be any set of the form (a,f(a)) such that the function f is chosen depending on an application of said method.

20. A method of authenticating an image, comprising:

producing an extended image using a halftoning algorithm on a collection of images;

projecting said extended image onto its first coordinates; and

authenticating said source image by extracting an embedded image from said projection to compare said embedded image to said source image.

21. The method of claim 20, wherein, for each member of a set of extended colors C, an output pixel is set to said member at a particular location (i,j) of the extended image to determine whether error is minimized by selecting such a particular output.

22. The method of claim 21, wherein an auxiliary image M₁ is generated from the source image M₀ by a permutation of the pixels M₁(P(i,j))=M₀(i,j), where P is a permutation of the pixel locations (i,j).

23. The method of claim 22, wherein, in the halftoning algorithm, an inverse permutation is applied to restore a spatial relationship before calculating the error function such that a function to minimize is:

v₀∥

L(ExOut₀−

M₀)∥

²+v₁∥

L(PExOut₁−

M₀)∥

²

where PExOut₁ is the image defined by;

PExOut₁(i,j)=ExOut₁(P(i,j));

24. The method of claim 23, where the parameters v₀ and v₁ are set equal to 1.

25. The method of claim 23, further comprising:

for each pixel, and for each member d of an extended color set C;

computing an error v(d) at a particular pixel (i,j) by setting the (i,j)-th pixel of the extended output ExOut equal to d;

determining the member d of an extended color set C which minimizes v(d);

setting the (i,j)-th pixel of the extended output ExOut equal to said minimizing d;

repeating the above process if the maximum number of iterations is not reached and the extended output ExOut has changed between the last two consecutive iterations; and

otherwise terminating said process.

26. The method of claim 25, wherein, at each iteration, the pixels are traversed in a particular order and for each location (i,j), the pixel ExOut (i,j) is chosen from the set C, such that

v₀∥

L(ExOut₀−

M₀)∥

²+v₁∥

L(PExOut₁−

M₀)∥

²

is minimized,

wherein a plurality of iterations are made until a local minimum is reached or the maximum number of iterations is reached.

27. The method of claim 26, wherein localized changes to the source image result in changes to the embedded images which are spread throughout the image.

28. The method of claim 26, wherein a reconstructed embedded image is compared with the source image to check whether significant changes have occurred.

29. The method of claim 26, wherein a reconstructed embedded image is compared with the source image to localize where such changes or corruptions have occurred.

30. The method of claim 20, further comprising:

repairing the source image which has been changed by using the embedded image.

31. The method of claim 30, wherein said repairing comprises:

setting the embedded image M₁ to be the same as the original source image but after having been permuted by re-shuffling of the pixels thereof;

extracting the embedded image image M₁′

from the modified M₀′

; and

applying an inverse permutation to M₁′

to obtain a reconstructed image.

32. The method of claim 31, further comprising:

low pass filtering a difference between the image M₀′ and

the image M₁′

after the inverse permutation, and finding the pixels with predetermined large norms, such that an estimate of where the modification occurs is produced,

wherein the estimate is used to determine where the embedded image should be repaired such that if a pixel is modified in the source image, then said pixel after permutation is not recovered in the embedded image PM₁′

, but is interpolated from other pixels which are determined not to have been modified.

33. The method of claim 32, further comprising:

processing said estimate with a morphological image processing operation.

34. The method of claim 20, further comprising:

detecting whether the image has been tampered with.

35. The method of claim 34, further comprising:

repairing portions of the image which have been detected as being tampered with.

36. The method of claim 20, wherein said image has a hologram property such that for an image having modified and unmodified portions of an original of the image, an unmodified portion of an original of the image is used to reconstruct the image.

37. The method of claim 20, further comprising:

in an image having a portion with one of modified and defective pixels, taking a portion of said image which has not been modified and reconstructing the entire image.

38. The method of claim 34, further comprising:

self-repairing said image with a portion of an original of said image.

39. The method of claim 20, further comprising:

localizing any tampering of said image; and

detecting said tampering.

40. A method of processing an image, comprising:

scrambling a source image to create a scrambled version of the source image;

embedding the scrambled version of the source image into the source image;

extracting the scrambled version of the image; and

unscrambling the extracted scrambled image to produce an extracted unscrambled image.

41. The method of claim 40, further comprising:

comparing the extracted unscrambled image to said embedded image, thereby to localize any tampering with the image.

42. The method of claim 41, further comprising:

repairing a tampered-with portion of the image.

43. A method for embedding data into an image, comprising:

calculating errors corresponding to a halftone extraction algorithm applied to a plurality of images, to select an extended image such that a sum of the errors is minimized; and

projecting said extended image onto its first coordinates.

44. A system for embedding data into an image, comprising:

an error calculator for calculating errors corresponding to a halftone extraction algorithm applied to a plurality of images, to select an extended image such that a sum of the errors is minimized; and

a projection unit for projecting said extended image onto its first coordinates.

45. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for embedding data into an image, said method comprising:

producing an extended image using a halftoning algorithm on a collection of images; and

projecting said extended image onto its first coordinates.