Parity-grid steganographic method and apparatus

• US 6,862,362 B2
• Filed: 11/02/2001
• Issued: 03/01/2005
• Est. Priority Date: 11/02/2001
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gangadhar, Deepak K
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US10/000,212
• Publication Number:
  US 20030086609A1
• Time in Patent Office: 1,215 Days
• Field of Search: 382/100, 382/162, 382/199
• US Class Current: 382/100
• CPC Class Codes: G06T 1/0028 Adaptive watermarking, e.g. Human Visual System [HVS]-based watermarking
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain

Abstract

A method and apparatus for generating a parity grid matrix from an indexed data representation are disclosed. The method includes the steps of calculating a parity value for each of specified rows and columns of the indexed representation, determining a parity restoration value for each of the specified rows and columns that exhibit a non-zero parity value, and adding the parity restoration values to one or more selected elements of the specified rows and columns that exhibit a non-zero parity value. A method and apparatus for embedding and retrieving information in/from data representations such as images, by use of a parity grid matrix, are also disclosed.

Claims

1. A method for generating a parity grid matrix from an indexed representation of an image, said method including the steps of:

calculating a parity value for each of specified rows and columns of said indexed representation;

determining a parity restoration value for each of said specified rows and columns that exhibit a non-zero parity value; and

adding said parity restoration values to one or more selected elements of said specified rows and columns that exhibit a non-zero parity value.

2. A method according to claim 1, wherein said indexed image comprises a data matrix.

3. A method according to claim 1, wherein said specified rows and columns comprise alternate rows and columns of said indexed image.

4. A method according to claim 1, wherein said specified rows and columns comprise every third row and every third column of said indexed image.

5. A method according to claim 1, wherein said step of calculating a parity value for one of said specified rows or columns includes the sub-steps of:

calculating the sum of the elements contained in said selected row or column; and

calculating the modulus of said sum and a selected integer value of parity level.

6. A method according to claim 1, wherein said selected elements are selected by an edge detection process.

7. A method according to claim 6, wherein said edge detection process identifies regions of greatest variation in said image, said variation selected from the group consisting of:

intensity variation;

hue variation; and

saturation variation.

8. A method for detecting alterations to an image, said method including the steps of:

calculating a parity value for each of specified rows and columns of a parity grid encoded representation of said image; and

determining each non-zero occurrence of said parity values, each said non-zero occurrence being indicative of a row or column containing one or more altered elements.

9. A method according to claim 8, wherein the intersection of a row of non-zero parity value and a column of non-zero parity value is indicative of the location of an alteration to said image.

10. A method for embedding information in an image, said method including the steps of:

generating a parity grid matrix from an indexed representation of said image;

selecting elements of said parity grid matrix for alteration; and

altering said selected elements according to a representation of said information.

11. A method according to claim 10, wherein said selected elements are selected by an edge detection process.

12. A method according to claim 11, wherein said edge detection process identifies regions of greatest variation in said image, said variation selected from the group consisting of:

intensity variation;

hue variation; and

saturation variation.

13. A method for retrieving information embedded in an image, said method including the steps of:

calculating a parity value for each of specified rows and columns of a parity grid encoded representation of said image; and

combining each non-zero value of said parity values to reconstruct said embedded information, said information being embedded in said image by alteration of said parity grid encoded representation of said image.

14. A method according to claim 13, wherein said step of calculating a parity value for one of said specified rows or columns includes the sub-steps of:

calculating the sum of the elements contained in said selected row or column; and

calculating the modulus of said sum and a selected integer value of parity level.

15. An apparatus for generating a parity grid matrix from an indexed representation of an image including:

means for calculating a parity value for each of specified rows and columns of said indexed representation;

means for determining a parity restoration value for each of said specified rows and columns that exhibit a non-zero parity value; and

means for adding said parity restoration values to one or more selected elements of said specified rows and columns that exhibit a non-zero parity value.

16. An apparatus according to claim 15, wherein said indexed image comprises a data matrix.

17. An apparatus according to claim 15, wherein said specified rows and columns comprise alternate rows and columns of said indexed image.

18. An apparatus according to claim 15, wherein said specified rows and columns comprise every third row and every third column of said indexed image.

19. An apparatus according to claim 15, wherein said means for calculating a parity value for one of said specified rows or columns includes:

means for calculating the sum of the elements contained in said selected row or column; and

means for calculating the modulus of said sum and a selected integer value of parity level.

20. An apparatus according to claim 15, further including edge detection means for selecting said selected elements.

21. An apparatus according to claim 20, wherein said edge detection means is adapted to identify regions of greatest variation in said image, said variation selected from the group consisting of:

intensity variation;

hue variation; and

saturation variation.

22. An apparatus for detecting alterations to an image including:

means for calculating a parity value for each of specified rows and columns of a parity grid encoded representation of said image; and

means for determining each non-zero occurrence of said parity values, each said non-zero occurrence being indicative of a row or column containing one or more altered elements.

23. An apparatus according to claim 22, wherein the intersection of a row of non-zero parity value and a column of non-zero parity value is indicative of the location of an alteration to said image.

24. An apparatus for embedding information in an image including:

means for generating a parity grid matrix from an indexed representation of said image;

means for selecting elements of said parity grid matrix for alteration; and

means for altering said selected elements according to a representation of said information.

25. An apparatus according to claim 24, wherein said means for selecting said selected elements comprises edge detection means.

26. An apparatus according to claim 25, wherein said edge detection means identifies regions of greatest variation in said image, said variation selected from the group consisting of:

intensity variation;

hue variation; and

saturation variation.

27. An apparatus for retrieving information embedded in an image including:

means for calculating a parity value for each of specified rows and columns of a parity grid encoded representation of said image; and

means for combining each non-zero value of said parity values to reconstruct said embedded information, said information being embedded in said image by alteration of said parity grid encoded representation of said image.

28. An apparatus according to claim 27, wherein said means for calculating a parity value for one of said specified rows or columns includes:

means for calculating the sum of the elements contained in said selected row or column; and

means for calculating the modulus of said sum and a selected integer value of parity level.

29. A computer program product having a computer readable medium having a computer program recorded therein for generating a parity grid matrix from an indexed representation of an image, said computer program product including:

computer program code means for calculating a parity value for each of specified rows and columns of said indexed representation;

computer program code means for determining a parity restoration value for each of said specified rows and columns that exhibit a non-zero parity value; and

computer program code means for adding said parity restoration values to one or more selected elements of said specified rows and columns that exhibit a non-zero parity value.

30. A computer program product according to claim 29, wherein said indexed image comprises a data matrix.

31. A computer program product according to claim 29, wherein said specified rows and columns comprise alternate rows and columns of said indexed image.

32. A computer program product according to claim 29, wherein said specified rows and columns comprise every third row and every third column of said indexed image.

33. A computer program product according to claim 29, wherein said computer program code means for calculating a parity value for one of said specified rows or columns includes:

computer program code means for calculating the sum of the elements contained in said selected row or column; and

computer program code means for calculating the modulus of said sum and a selected integer value of parity level.

34. A computer program product according to claim 29, further including computer program code means for edge detection to select said selected elements.

35. A computer program product according to claim 34, wherein said computer program code means for edge detection is adapted to identify regions of greatest variation in said image, said variation selected from the group consisting of:

intensity variation;

hue variation; and

saturation variation.

36. A computer program product product having a computer readable medium having a computer program recorded therein for detecting alterations to an image, said computer program product including:

computer program code means for calculating a parity value for each of specified rows and columns of a parity grid encoded representation of said image; and

computer program code means for determining each non-zero occurrence of said parity values, each said non-zero occurrence being indicative of a row or column containing one or more altered elements.

37. A computer program product according to claim 36, wherein the intersection of a row of non-zero parity value and a column of non-zero parity value is indicative of the location of an alteration to said image.

38. A computer program product product having a computer readable medium having a computer program recorded therein for embedding information in an image, said computer program product including:

computer program code means for generating a parity grid matrix from an indexed representation of said image;

computer program code means for selecting elements of said parity grid matrix for alteration; and

computer program code means for altering said selected elements according to a representation of said information.

39. A computer program product according to claim 38, wherein said computer program code means for selecting said selected elements comprises computer program code means for edge detection.

40. A computer program product according to claim 39, wherein said computer program code means for edge detection identifies regions of greatest variation in said image, said variation selected from the group consisting of:

intensity variation;

hue variation; and

saturation variation.

41. A computer program product product having a computer readable medium having a computer program recorded therein for retrieving information embedded in an image, said computer program product including:

computer program code means for calculating a parity value for each of specified rows and columns of a parity grid encoded representation of said image; and

computer program code means for combining each non-zero value of said parity values to reconstruct said embedded information, said information being embedded in said image by alteration of said parity grid encoded representation of said image.

42. A computer program product according to claim 41, wherein said computer program code means for calculating a parity value for one of said specified rows or columns includes:

computer program code means for calculating the sum of the elements contained in said selected row or column; and

computer program code means for calculating the modulus of said sum and a selected integer value of parity level.