Insertion and extraction of a message in an image

• US 20040146178A1
• Filed: 06/16/2003
• Published: 07/29/2004
• Est. Priority Date: 06/19/2002
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Donescu, Ioana
• Granted Patent: US 7,330,560 B2
• Time in Patent Office: Days
• 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 message in an image, characterized in that it comprises the steps of:

selecting (S1) 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.

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

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

selecting (S11) 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 (S14) that the points of the coordinate system formed in the image are the first interest points, and if the response is negative,

modifying (S14) 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.

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

detecting (S31) 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 (S32) 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 (S33) 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.

4. A method of insertion according to claim 2 or 3, 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 2 or 3, 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 3, characterized in that it further comprises the step of:

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

7. A method of insertion according to any one of claims 1 to 6, characterized in that that generating (S24) 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.

8. A method of insertion according to any one of claims 1 to 6, characterized in that that generating (S24) 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.

9. A method of insertion according to any one of claims 1 to 8, 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.

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

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

calculating (S101, S201) an affine transformation between the coordinate system formed in the image and a predetermined coordinate system,

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

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

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

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

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

27. An apparatus (10) for processing a digital image, characterized in that it comprises means adapted to implement the method according to any one of claims 1 to 12.

29. Storage medium storing a program for implementing the method according to any one of claims 1 to 12.

31. Storage medium according to claim 29 or 30, characterized in that said storage medium is a floppy disk or a CD-ROM.

32. Computer program on a storage medium and comprising computer executable instructions for implementing the method according to any one of claims 1 to 12.

13. A device for the insertion of a message in an image, 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 (R) in the image,

means for calculating an affine transformation (A) 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 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,

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

14. An insertion device according to claim 13, characterized in that the means for selection comprise:

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, and if the response is negative,

means for 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.

15. An insertion device according to claim 13 or 14, 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.

16. An insertion device according to claim 14 or 15, 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 14 or 15, 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 15, 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.

19. An insertion device according to any one of claims 13 to 18, 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.

20. An insertion device according to any one of claims 13 to 18, 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 points of the image in a spiral scanning path starting with the origin of the predetermined coordinate system.

21. An insertion device according to any one of claims 13 to 20, 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.

22. A device for extracting a message inserted in an image by the device according to any one of claims 13 to 21, 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 systemin 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.

23. An extraction device according to claim 22, characterized in that he 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.

24. An extraction device according to claim 23, 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.

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

a microprocessor (100),

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

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

26. An insertion device according to any one of claims 22 to 24, characterized in that the means for selecting, calculating, generating, projecting and extracting are incorporated in:

a microprocessor (100),

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

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

28. An apparatus (10) for processing a digital image, characterized in that it comprises the device according to any one of claims 13 to 26.

30. Storage medium according to claim 29, characterized in that said storage medium is detachably mountable on a device according to any one of claims 13 to 26.