Image analysis – Applications
Reexamination Certificate
1999-12-01
2003-12-16
Boudreau, Leo (Department: 2621)
Image analysis
Applications
Reexamination Certificate
active
06665418
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of image processing, and in particular to embedding and extracting hidden messages in digital image data. This field is also referred to as data hiding, information hiding, watermarking and also steganography.
BACKGROUND OF THE INVENTION
U.S. Pat. No. 5,850,481, issued Dec. 15, 1998 to Rhoads, entitled “Steganographic System” discloses a method of embedding hidden messages in source data that can be described by the equation:
I
′
(
x
,
y
)
=
I
(
x
,
y
)
+
∑
i
=
1
n
b
i
·
R
i
(
x
,
y
)
,
(
1
)
where I′(x,y) is the source data containing the hidden message,
I(x, y) is the source data,
b
i
is the i
th
bit of the n-bit hidden message, and
R
i
(x, y) are random arrays of numbers having the property that
R
i
(
x
,
y
)
·
R
j
(
x
,
y
)
=
{
1
where
i
=
j
0
where
i
≠
j
,
A simplified schematic block diagram illustrating this method is shown in FIG.
2
. First an n-bit message is provided (
10
), then n random independent arrays R
i
(x,y) are generated (
12
). By independent is meant that the arrays are orthogonal in the sense of equation (1). Each of the random independent arrays R
i
(x,y) is then multiplied by the value of a corresponding bit in the n-bit message to produce n products(
14
). The n products are then added to produce a sum (
16
), and finally the sum is added to the original image data (
18
) to produce a modified image having an embedded message.
Each individual bit b
i
of the embedded message is recovered from the modified image data I′(x,y) by taking the dot product of the modified image data and the corresponding random independent array R
i
(x,y). The values of the recovered bits are assigned based on the amplitude of the dot product.
A problem with this method is that a separate random array of numbers R
i
(x,y) must be generated for each bit of the hidden message. One method disclosed for generating n random arrays is to scan a pure black image n times on a scanner where the gain has been turned up. For large hidden messages, this process becomes unduly burdensome, and if any systematic disturbances occur in the system, the resulting noise patterns will not be orthogonal. To locate the boundaries of the embedded message, embedded calibration signals are employed. These calibration signals use up bandwidth that could be used for the message.
There is a need therefore for an improved process for generating the random arrays employed in the hidden message embedding process.
SUMMARY OF THE INVENTION
The need is met according to the present invention by generating the random number arrays as follows.
R
i
(
x,y
)=
C
(
x−&agr;
i
,y−&bgr;
i
),
where C(x,y) is a random array of numbers, and (&agr;
i
,&bgr;
i
) are cyclical shifts having the property that (&agr;
i
,&bgr;
i
)≠(&agr;
j
,&bgr;
j
) for i≠j. Statistical theory can be used to show that a cyclically shifted version of a random array is orthogonal to the original random array and to other cyclically shifted versions of the random array.
This approach has the advantage that after generating one random number array C(x,y), the remainder may be easily generated simply by cyclically shifting the array by offsets (&agr;
i
,&bgr;
i
). It has the additional advantage that it makes the computation simpler at the decoder. Instead of using n (typically 32, 64, . . . , 128 etc.) independent random number arrays, the method can now use one random number array. This complexity reduction is immensely beneficial to system developers attempting to improve algorithm speed. The invention may be applied to embedded systems in cameras, scanners or other systems where memory and processor performance are important.
In a preferred embodiment, the random array C(x,y) possesses a substantially flat Fourier amplitude spectrum and random phase.
In a further preferred embodiment, the cyclical shifts applied to the random array C(x,y) are represented by a shift template having a highly peaked autocorrelation. This embodiment has the additional advantages that the message can be recovered from the image without the need for embedded calibration signals, and the same method can be used to recover messages embedded by the technique disclosed by Rhoads in U.S. Pat. No. 5,850,481, or by the technique disclosed in U.S. patent application Ser. No. 08/848,112, filed Apr. 28, 1997 and allowed Sep. 23, 1999, entitled “Method For Generating An Improved Carrier For Use In An Image Data Embedding Application,” by Honsinger et al. Thus messages embedded using two different proprietary embedding techniques can be recovered with the message extraction method of the present invention. This will be useful for example in image scanners that are likely to encounter embedded messages of different origin.
REFERENCES:
patent: 3697881 (1972-10-01), Nakagome et al.
patent: 4059805 (1977-11-01), de Laage de Meux et al.
patent: 5636279 (1997-06-01), Katta et al.
patent: 5850481 (1998-12-01), Rhoads
patent: 5859920 (1999-01-01), Daly et al.
patent: 6154571 (2000-11-01), Cox et al.
patent: 6157612 (2000-12-01), Weerackody et al.
patent: 9-191395 (1997-07-01), None
Boudreau Leo
Eastman Kodak Company
Lu Tom Y.
Watkins Peyton C.
LandOfFree
Linear projective data embedding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Linear projective data embedding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear projective data embedding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136649