Insertion and extraction of a message in an image

• US 7,330,560 B2
• Filed: 06/16/2003
• Issued: 02/12/2008
• Est. Priority Date: 06/19/2002
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Donescu, Ioana
• Primary Examiner(s): Werner; Brian
• Assistant Examiner(s): MACKOWEY, ANTHONY M
• Application Number:
  US10/461,416
• Publication Number:
  US 20040146178A1
• Time in Patent Office: 1,702 Days
• Field of Search: 382/100, 713/176, 358/3.28
• US Class Current: 382/100
• CPC Class Codes: G06T 1/0064 Geometric transfor invariant watermarking, e.g. affine transform invariant
• CPC Class Codes: G06T 2201/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: H04N 1/32149 Methods relating to embedding, encoding, decoding, detection or retrieval operations
• CPC Class Codes: H04N 1/32187 with selective or adaptive application of the additional information, e.g. in selected frequency coefficients
• CPC Class Codes: H04N 1/32229 with selective or adaptive application of the additional information, e.g. in selected regions of the image H04N1/32213 takes precedence
• CPC Class Codes: H04N 19/467 characterised by the embedded information being invisible, e.g. watermarking

Abstract

The invention concerns a method of inserting a message in an image, characterized in that it comprises the steps of:

• • selecting a set of points in the image as a function of predetermined criteria, so as to form a coordinate system in the image,
  • calculating (S21) an affine transformation between a predetermined coordinate system and the coordinate system formed in the image,
  • generating (S24) a pseudo-random sequence for each symbol of the message to be inserted, in the predetermined coordinate system,
  • projecting (E25) each pseudo-random sequence into the coordinate system formed in the image, by affine transformation,
  • inserting (S27) each symbol of the message to be inserted, as a function of its respective projected pseudo-random sequence.

Claims

1. A method of inserting a multiple bit message in an image, characterized in that it comprises the steps of:

selecting a predetermined number of points in the image as a function of predetermined criteria, so as to form a coordinate system in the image,

calculating an affine transformation between a predetermined coordinate system and the coordinate system formed in the image,

generating a pseudo-random sequence for each symbol of the multiple bit message to be inserted, in the predetermined coordinate system,

projecting each pseudo-random sequence into the coordinate system formed in the image, by affine transformation, and

inserting each symbol of the multiple bit message to be inserted, as a function of its respective projected pseudo-random sequence;

wherein said selecting comprises

detecting a first set of interest points, the first set comprising a first number of points, the interest points being ordered,

selecting the points of the coordinate system formed in the image, among the points of interest, the coordinate system comprising a second number of points less than or equal to the first number of points,

verifying that the points of the coordinate system formed in the image are the first interest points in the order, and if the response is negative,

modifying the image around the points of the coordinate system formed in the image, such that an additional detection of a second set of interest points, the second set comprising the second number of points, provides the points of the coordinate system formed in the image.

2. A method of insertion according to claim 1, characterized in that it further comprises the steps of:

detecting a third set of interest points in the image in which the message has been inserted, the third set comprising the same number of points as the coordinate system formed in the image,

comparing the interest points of the third set with the points of the coordinate system formed in the image, and, if there is no identity between the interest points of the third set and the points of the coordinate system formed in the image,

modifying the image in which the message has been inserted, in order for there to be identity between the interest points of the third set and the points of the coordinate system formed in the image.

3. A method of insertion according to claim 2, characterized in that it further comprises the step of:

applying a distortion to the image in which the message has been inserted, prior to the detection of a third set of interest points.

4. A method of insertion according to claim 1, characterized in that the modification of the image is a low-pass filtering operation around the interest points which are not in the coordinate system formed in the image.

5. A method of insertion according to claim 1, characterized in that the modification of the image is a high-pass filtering operation around the points of the coordinate system formed in the image.

6. A method of insertion according to claim 1, characterized in that that generating a pseudo-random sequence comprises generating a pseudo-random sample for each point of the image, the sample being determined as a function of the coordinates of the point in the predetermined coordinate system.

7. A method of insertion according to claim 1, characterized in that that generating a pseudo-random sequence comprises generating a series of pseudo-random numbers and associating these numbers with the points of the image in a spiral scanning path starting with the origin of the predetermined coordinate system.

8. A method of insertion according to claim 1, characterized in that the insertion of a given symbol is carried out by the addition of the projected pseudo-random sequence corresponding to said given symbol, the pseudo-random sequence having been modulated by the symbol, and in that the insertion is carried out over the entire image except in the neighborhood of the points of the coordinate system formed in the image.

9. A method of extraction of a message inserted in an image by the method according to claim 1, characterized in that it comprises the steps of:

selecting a set of points in the image as a function of predetermined criteria, so as to form a coordinate system in the image,

calculating an affine transformation between the coordinate system formed in the image and a predetermined coordinate system,

generating a pseudo-random sequence for each symbol of the message to be extracted, in the predetermined coordinate system,

projecting each pseudo-random sequence into the coordinate system formed in the image, by reverse affine transformation,

extracting each symbol of the message, as a function of its respective projected pseudo-random sequence.

10. An extraction method according to claim 9, characterized in that the extraction comprises calculating a detection value for each symbol to be extracted and comparing the detection value with a predetermined threshold.

11. An extraction method according to claim 10, characterized in that the extraction comprises a plurality of detection tests and the taking into account of the best test, for each symbol to extract.

12. A computer-readable medium embodying a computer program, the computer program comprising computer executable instructions for implementing the method according to claim 1.

13. A device for the insertion of a multiple bit message in an image, characterized in that it comprises:

means for selecting a predetermined number of points in the image as a function of predetermined criteria, so as to form a coordinate system in the image,

means for calculating an affine transformation between a predetermined coordinate system and the coordinate system formed in the image,

means for generating a pseudo-random sequence for each symbol of the multiple bit message to be inserted, in the predetermined coordinate system,

means for projecting each pseudo-random sequence in the coordinate system formed in the image, by affine transformation, and

means for inserting each symbol of the multiple bit message to be inserted, as a function of its respective projected pseudo-random sequence;

said means for selecting comprising

means for detecting a first set of interest points, the first set comprising a first number of points, the interest points being ordered,

means for selecting the points of the coordinate system formed in the image, among the points of interest, the coordinate system comprising a second number of points less than or equal to the first number of points,

means for verifying that the points of the coordinate system formed in the image are the first interest points in the order, and

means for modifying the image around the points of the coordinate system formed in the image if the verification is negative, such that an additional detection of a second set of interest points, the second set comprising the second number of points, provides the points of the coordinate system formed in the image.

14. An insertion device according to claim 13, characterized in that it further comprises:

means for detecting a third set of interest points in the image in which the message has been inserted, the third set comprising the same number of points as the coordinate system formed in the image,

means for comparing the interest points of the third set with the points of the coordinate system formed in the image, and, if identity does not exist between the interest points of the third set and the points of the coordinate system formed in the image,

means for modifying the image in which the message has been inserted, in order for there to be identity between the interest points of the third set and the points of the coordinate system formed in the image.

15. An insertion device according to claim 14, characterized in that it further comprises means for applying a distortion to the image in which the message has been inserted, prior to the detection of a third set of interest points.

16. An insertion device according to claim 13, characterized in that the means for modification the image are adapted to apply a low-pass filtering operation around the interest points which are not in the coordinate system formed in the image.

17. A device for insertion according to claim 13, characterized in that the means for modifying the image are adapted to apply a high-pass filtering operation around the points of the coordinate system formed in the image.

18. An insertion device according to claim 13, characterized in that that the means for generating a pseudo-random sequence are adapted to generate a pseudo-random sample for each point of the image, the sample being determined as a function of the coordinates of the point in the predetermined coordinate system.

19. An insertion device according to claim 13, characterized in that that the means for generating a pseudo-random sequence are adapted to generate a series of pseudo-random numbers and to associate these numbers with the point of the image in a spiral scanning path starting with the origin of the predetermined coordinate system.

20. An insertion device according to claim 13, characterized in that the means for inserting a given symbol are adapted to carry out the addition of the projected pseudo-random sequence corresponding to said given symbol, the pseudo-random sequence having been modulated by the symbol, and in that the means for insertion are adapted to carry out this insertion over the entire image except in the neighborhood of the points of the coordinate system formed in the image.

21. A device for extracting a message inserted in an image by the device according to claim 13, characterized in that it comprises:

means for selecting a set of points in the image as a function of predetermined criteria, so as to form a coordinate system in the image,

means for calculating an affine transformation between the coordinate system formed in the image and a predetermined coordinate system,

means for generating a pseudo-random sequence for each symbol of the message to be extracted, in the predetermined coordinate system,

means for projecting each pseudo-random sequence in the coordinate system formed in the image, by reverse affine transformation,

means for extracting each symbol of the message, as a function of its respective projected pseudo-random sequence.

22. An extraction device according to claim 21, characterized in that the means for extraction comprise means for calculating a detection value for each symbol to be extracted and means for comparing the detection value with a predetermined threshold.

23. An extraction device according to claim 22, characterized in that the means for extraction are adapted to implement a plurality of detection tests and to take into account the best test, for each symbol to extract.

24. An insertion device according to claim 21, characterized in that the means for selecting, calculating, generating, projecting and extracting are incorporated in:

a microprocessor,

a read only memory, comprising a program for processing the data, and

a random access memory comprising registers adapted to record variables modified during the execution of said program.

25. An insertion device according to claim 13, characterized in that the means for selecting, calculating, generating, projecting and inserting are incorporated in:

a microprocessor,

a read only memory, comprising a program for processing the data, and

a random access memory comprising registers adapted to record variables modified during the execution of said program.