Method and apparatus for site selection for data embedding

• US 6,813,367 B1
• Filed: 09/11/2000
• Issued: 11/02/2004
• Est. Priority Date: 09/11/2000
• Status: Active Grant

• Current Assignee: Seiko Epson Corporation (Seiko Group)
• Original Assignee: Seiko Epson Corporation (Seiko Group)
• Inventors: Bhattacharjya, Anoop
• Primary Examiner(s): MARIAM, DANIEL G
• Application Number:
  US09/659,197
• Time in Patent Office: 1,513 Days
• Field of Search: 382/100, 382/165, 382/176, 382/181, 382/190, 382/202, 382/257, 382/260, 382/321, 380/201, 380/202, 380/203, 358/3.28, 713/165, 713/170, 713/176, 713/178
• 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/0051 Embedding of the watermark in the spatial domain
• CPC Class Codes: G06T 2201/0062 Embedding of the watermark in text images, e.g. watermarking text documents using letter skew, letter distance or row distance
• CPC Class Codes: G06V 30/224 of printed characters having additional code marks or containing code marks
• CPC Class Codes: H04N 1/32144 embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 1/32203 Spatial or amplitude domain methods H04N1/32309 takes precedence
• CPC Class Codes: H04N 1/32309 in colour image data

Abstract

A differential color or luminance signal is used to embed a binary message in selected stroke segments in the text of a document and for extracting a message so embedded. The bits representing the message are embedded in the stroke segments by modifying a color or luminance value of pixels in one region of a selected stroke with respect to such a value of pixels in a second region of that stroke. To determine whether a bit is embedded in a stroke segment, a value representative of the luminance or color of pixels in the one region is compared with a value representative of the luminance or color of pixels in the second region. The presence or absence of a bit is determined by whether the difference between the two values is greater than a minimum predetermined threshold.

Claims

1. A method for embedding a message in a text-containing document, comprising the steps of:

obtaining a pixel representation of the document;

identifying text pixels of the document;

identifying stroke segments in the text pixels of the document; and

embedding information in at least one identified stroke segment by changing a characteristic value of pixels in a first region of that stroke segment with respect to the characteristic value of pixels in a second region of that stroke segment, wherein the first and second regions are non overlapping.

2. The method of claim 1, wherein the characteristic value is a color or luminance value.

3. The method of claim 1, wherein the step of identifying stroke segments is carried out by filtering text pixels using a morphological filter having a structuring element defining minimum stroke segment dimensions.

4. The method of claim 3, wherein the stroke segments are substantially vertical.

5. The method of claim 1, wherein the first and second regions in each identified stroke segment are disjoint and located in interior regions of that stroke segment.

6. The method of claim 1, wherein the step of embedding information comprises embedding a single bit of information in that stroke segment by changing the characteristic value of pixels in one or the other of the first or second regions but not both.

7. A method for extracting a message embedded in stroke segments in text of a document, comprising the steps of:

obtaining a pixel representation of the document;

identifying text pixels of the document;

identifying the stroke segments in the text pixels of the document; and

measuring a value representative of a characteristic of pixels in a first region of each identified stroke segment with respect to such a value representative of the characteristic of pixels in a second region of that stroke segment to determine the presence or absence of a bit embedded in that stroke segment, wherein the first and second regions are non overlapping.

8. The method of claim 7, wherein the characteristic is color or luminance.

9. The method of claim 7, and the representative value is an average.

10. The method of claim 7, wherein the step of identifying stroke segments is carried out by filtering text pixels using a morphological filter having a structuring element defining minimum stroke segment dimensions.

11. The method of claim 10, wherein the stroke segments are substantially vertical.

12. The method of claim 7, wherein the first and second regions in each identified stroke segment are disjoint and located in interior regions of that stroke segment.

13. The method of claim 7, wherein the measuring step comprises, for each identified stroke

summing the characteristic values of pixels along each of pixel line within the first region to generate a first set of summed values,

summing the characteristic values of pixels along each pixel line within the second region to generate a second set of summed values,

computing the average of the first set of summed values,

computing the average of the second set of summed values, and

comparing the average of the first set with the average of the second set to determine the presence or absence of a bit embedded in that stroke segment.

14. An apparatus for embedding a message in a text-containing document, the apparatus comprising:

a scanner that outputs a pixel representation of the document;

a text pixel identifying circuit in communication with the scanner;

a stroke segment identifying circuit, in communication with the text pixel identifying circuit; and

an embedding circuit, in communication with the stroke segment identifying circuit, that embeds information in each identified stroke segment by changing a characteristic value of pixels in a first region of that stroke segment with respect to the characteristic value of pixels in a second region of that stroke segment, wherein the first and second regions are non overlapping.

15. The apparatus of claim 14, wherein the characteristic value is a color or luminance value.

16. The apparatus of claim 14, wherein the stroke segment identifying circuit comprises a morphological filter having a structuring element defining minimum stroke segment dimensions to identify stroke segments in text pixels.

17. The apparatus of claim 16, wherein the stroke segments are substantially vertical.

18. The apparatus of claim 14, wherein the first and second regions in each identified stroke segment are disjoint and located in interior regions of that stroke segment.

19. The apparatus of claim 14, wherein the embedding circuit embeds information in each identified stroke segment by embedding a single bit of information in that stroke segment by changing the characteristic value of pixels in one or the other of the first or second regions but not both.

20. The apparatus of claim 14, wherein the text pixel identifying circuit, the stroke segment identifying circuit, and the embedding circuit are embodied as a single integrated circuit.

21. An apparatus for extracting a message embedded in stroke segments in text of a document, the apparatus comprising:

a scanner that outputs a pixel representation of the document;

a text pixel identifying circuit in communication with the scanner;

a stroke segment identifying circuit, in communication with the text pixel identifying circuit; and

an extracting circuit, in communication with the stroke segment identifying circuit, that measures a value representative of a characteristic of pixels in a first region of that stroke segment with respect to such a value representative of the characteristic of pixels in a second region of that stroke segment to determine the presence or absence of a bit embedded in that stroke segment, wherein the first and second regions are non overlapping.

22. The apparatus of claim 21, wherein the characteristic is color or luminance.

23. The apparatus of claim 21, and the representative value is an average.

24. The apparatus of claim 21, wherein the stroke segment identifying circuit comprises a morphological filter having a structuring element defining minimum stroke segment dimensions to identify stroke segments in text pixels.

25. The apparatus of claim 24, wherein the stroke segments are substantially vertical.

26. The apparatus of claim 21, wherein the first and second regions in each identified stroke segment are disjoint and located in interior regions of that stroke segment.

27. The apparatus of claim 21, wherein the extracting circuit comprises

a summing circuit that sums the characteristic values of pixels along each pixel line within the first region to generate a first set of summed values, and that sums the characteristic values of pixels along each pixel line within the second region to generate a second set of summed values,

an averaging circuit that computes the average of the first set of summed values, and that computes the average of the second set of summed values, and

a comparator that compares the average of the first set with the average of the second set to determine the presence or absence of a bit embedded in that stroke segment.

28. The apparatus of claim 21, wherein the text pixel identifying circuit, the stroke segment identifying circuit, and the extracting circuit are embodied as a single integrated circuit.

29. A machine-readable medium embodying a program of instructions for causing a machine to perform a method of embedding a message in a text-containing document, the program of instructions comprising instructions for:

obtaining a pixel representation of the document;

identifying text pixels of the document;

identifying stroke segments in the text pixels of the document; and

embedding information in at least one identified stroke segment by changing a characteristic value of pixels in a first region of that stroke segment with respect to the characteristic value of pixels in a second region of that stroke segment, wherein the first and second regions are non overlapping.

30. The machine-readable medium of claim 29, wherein the characteristic value is a color or luminance value.

31. The machine-readable medium of claim 29, wherein the step of identifying stroke segments is carried out by filtering text pixels using a morphological filter having a structuring element defining minimum stroke segment dimensions.

32. The machine-readable medium of claim 31, wherein the stroke segments are substantially vertical.

33. The machine-readable medium of claim 29, wherein the first and second regions in each identified stroke segment are disjoint and located in interior regions of that stroke segment.

34. The machine-readable medium of claim 29, wherein the step of embedding information comprises embedding a single bit of information in that stroke segment by changing the characteristic value of pixels in one or the other of the first or second regions but not both.

35. A machine-readable medium embodying a program of instructions for causing a machine to perform a method of extracting a message embedded in stroke segments in text of document, the program of instructions comprising instructions for:

obtaining a pixel representation of the document;

identifying text pixels of the document;

identifying the stroke segments in the text pixels of the document; and

measuring a value representative of a characteristic of pixels in a first region of each identified stroke segment with respect to such a value representative of the characteristic of pixels in a second region of that stroke segment to determine the presence or absence of a bit embedded in that stroke segment, wherein the first and second regions are non overlapping.

36. The machine-readable medium of claim 35, wherein the characteristic is color or luminance.

37. The machine-readable medium of claim 35, and the representative value is an average.

38. The machine-readable medium of claim 35, wherein the step of identifying stroke segments is carried out by filtering text pixels using a morphological filter having a structuring element defining minimum stroke segment dimensions.

39. The machine-readable medium of claim 38, wherein the stroke segments are substantially vertical.

40. The machine-readable medium of claim 35, wherein the first and second regions in each identified stroke segment are disjoint and located in interior regions of that stroke segment.

41. The machine-readable medium of claim 35, wherein the measuring step comprises, for each identified stroke

summing the characteristic values of pixels along each of pixel line within the first region to generate a first set of summed values,

summing the characteristic values of pixels along each pixel line within the second region to generate a second set of summed values,

computing the average of the first set of summed values,

computing the average of the second set of summed values, and comparing the average of the first set with the average of the second

set to determine the presence or absence of a bit embedded in that stroke segment.

42. An apparatus for embedding a message in a text-containing document, the apparatus comprising:

means for outputting a pixel representation of the document;

means for identifying text pixels in the pixel representation of the document;

means for identifying stroke segments in the text pixels of the document; and

means for embedding information in each identified stroke segment by changing a characteristic value of pixels in a first region of that stroke segment with respect to the characteristic value of pixels in a second region of that stroke segment, wherein the first and second regions are non overlapping.

43. The apparatus of claim 42, wherein the characteristic value is a color or luminance value.

44. The apparatus of claim 42, wherein the stroke segments identifying means comprises a morphological filter having a structuring element defining minimum stroke segment dimensions to identify stroke segments in text pixels.

45. The apparatus of claim 44, wherein the stroke segments are substantially vertical.

46. The apparatus of claim 42, wherein the first and second regions in each identified stroke segment are disjoint and located in interior regions of that stroke segment.

47. The apparatus of claim 42, wherein the information embedding means embeds information in each identified stroke segment by embedding a single bit of information in that stroke segment by changing the characteristic value of pixels in one or the other of the first or second regions but not both.

48. An apparatus for extracting a message embedded in stroke segments in text of a document, the apparatus comprising:

means for outputting a pixel representation of the document;

means for identifying text pixels in the pixel representation of the document;

means for identifying the stroke segments in the text pixels of the document; and

means for measuring a value representative of a characteristic of pixels in a first region of that stroke segment with respect to such a value representative of the characteristic of pixels in a second region of that stroke segment to determine the presence or absence of a bit embedded in that stroke segment, wherein the first and second regions are non overlapping.

49. The apparatus of claim 48, wherein the characteristic is color or luminance.

50. The apparatus of claim 48, and the representative value is an average.

51. The apparatus of claim 48, wherein the stroke segments identifying means comprises a morphological filter having a structuring element defining minimum stroke segment dimensions to identify stroke segments in text pixels.

52. The apparatus of claim 51, wherein the stroke segments are substantially vertical.

53. The apparatus of claim 48, wherein the first and second regions in each identified stroke segment are disjoint and located in interior regions of that stroke segment.

54. The apparatus of claim 48, wherein the measuring means comprises

means for summing the characteristic values of pixels along each pixel line within the first region to generate a first set of summed values, and for summing the characteristic values of pixels along each pixel line within the second region to generate a second set of summed values,

means for computing the average of the first set of summed values, and for computing the average of the second set of summed values, and

means for comparing the average of the first set with the average of the second set to determine the presence or absence of a bit embedded in that stroke segment.