Data hiding and extraction methods

Details Data hiding and extraction methods Data hiding and extraction methods

2000-01-10

2003-01-28

Mancuso, Joseph (Department: 2623)

Image analysis

Applications

C348S460000, C725S022000

Reexamination Certificate

active

06512835

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to a data hiding method for hiding message data in media data and a data extraction method for extracting the hidden data.
2. Prior Art
Due to the development of multimedia-oriented society, a large amount of digitalized image and sound information is distributed over Internet or as recording media such as CD-ROMs, DVD-ROMs (or DVD-RAMs), or DVCs. Since anyone can simply make a complete copy of such digitalized information which is unlikely to be degraded, its unfair use is a problem. To prevent a third person from unfairly copying media data such as image or sound data, attention is being paid to a hiding technology that hides in original media data, information such as the sign of the author. If digitalized image data is illegally copied, the sign hidden in the copy can be checked to identify its source in order to determine whether it has been illegally made. Such a technology is called “data hiding”.
FIG. 1
is a half tone image comprising digitalized data shown on a display. Photo description (messages) such as a “nurse”, a “river”, a “kindergarten pupil”, and a “bird” is hidden in the media data, that is, the digitalized image in FIG.
1
(
a
), as shown in FIG.
1
(
b
). Media data can be obtained by dividing an image from a photograph into small points and determining the numerical values of the brightness and color of each point. In this case, the original numerical values of the image are intentionally somewhat changed. Very small changes in the numerical values do not substantially disturb the image and are not perceived by users. This nature can be used to hide completely different information (message data) in the original image. Message data hidden in the image may include any information and may be, for example, a lattice pattern, a rule-like figure, or the sign of the producer of the image. Message data hidden in media data can be extracted by processing with a special program. Thus, based on the extracted message data, it can be determined whether the original media data has been modified.
Each of the messages shown in FIG.
1
(
b
) is hidden near a meaningful region on the image. For example, the message “bird” is hidden near the region in which the bird in the image is present, and acts as a caption. To hide a message such as information on the owner in the image, the message is preferably distributed over the image. This is because the message, which is locally hidden, may degrade the quality of that region when its amount is large. In addition, if part of the image is cut off, it is likely to be able to extract the message if it is distributed over the image. Thus, how to determine where each message piece is hidden is important. The positions are determined on the bases of a state sequence S. That is, each element of the state sequence is associated with each message and the message is hidden at the corresponding position determined on the basis of the element.
According to conventional data hiding methods, the state sequence S has been determined by a random number sequence.
FIG. 2
schematically shows a layout of message data distributed on an image according to conventional methods. The image shown in FIG.
1
(
a
) is divided into I image regions, each of which is numbered from 0 to 9. Then, message data is expressed as a message array (m), and an array element is described as an array value m[n] (0≦n≦9). Each array value is associated with divided message data. Each message is hidden at the position in the image specified on the basis of the element in the state sequence S. The following equations determine a position p
0
at which
0
th message m[
0
] is hidden.
State value
S
0
=initial value (constant)
Position
p
0
=S
0
mod I
  [Equation 1]
The above equations indicate that after a constant has been given as the initial value of the state value S
0
, the remainder of I (the number of image regions) relative to the state value S
0
is P
0
. The value of the position P
0
is any integral value between 0 and (I−1). By associating the integral values with the order of the image regions, the message m[
0
] is hidden in the i-th image region. The locations P
n
of the first and subsequent messages m[n] on the basis of the following equation.
S
n
=Rnd
(
S
n−1
)
P
n
=S
n
mod I
  [Equation 2]
These equations indicate that the preceding state value S
n−1
is used as the seed of a random number to generate a pseudo random number array, which is used as the next state value S
n
. The remainder of I relative to the state value S
n
is the position P
n
. The message m[n] is hidden in the image region corresponding to this value.
The hidden message can be read only by users who know the state value S
0
(initial value). If the message is extracted, all the state values (S
1
, . . . , S
9
) following the state value S
0
are calculated on the basis of the initial value. The positions corresponding to the state values are identified and the messages hidden at these positions are extracted.
As is seen in
FIG. 2
, since the state value S
n
used to determine the position on the image of the n-th message m[n] depends only on the state value S
n−1
the state value S
n
can be determined when the state value S
n−1
is determined. Likewise, the state value S
n−1
depends only on the state value S
n−2
. By recursively repeating this procedure, all the elements (S
0
, S
1
, S
2
. . . , S
9
) in the state sequence S can be determined. Thus, all the elements in the state sequence S depend only on the constant initially given as the initial value. Consequently, once the initial value has been identified, the state sequence S can be determined to identify all the positions of the messages distributed over the image and to extract their hidden contents.
If the initial value has been published or known to a third person despite efforts to make it secret, the third person can use the value to identify the positions of messages easily and erase the message data or write a different message data over the first data. It has been difficult for conventional methods to effectively prevent a third person from erasing the original sign to make the source unknown or writing a different sign over the original sign to act as if he or she was the author.
It is therefore an object of this invention to propose a new method for distributing and hiding message data in media data. It is another object of this invention to provide a data hiding method that prevents a third person from modifying message data.
SUMMARY OF THE INVENTION
To achieve the above objects, the present invention relates to a data hiding method of dispersively hiding the array elements of a message array in a media array based on a state value S specifying a particular array element in the media array if the media data is expressed as the media array while message data is expressed as the message array. Specifically, one aspect of the present invention comprises the steps of:
(a) determining the j-th (j≧0) state value Sj;
(b) determining (j+1)-th state value S
j+1
based on the j-th state value, the array element of the media array indicated by the j-th state value, and the array element of the message array; and
(c) hiding data with respect to the array element of the media array indicated by the (j+1)-th state value S
j+1
.
If the message array has J array elements, the above steps (a) to (c) are recursively repeated until the J array elements have been hidden. If j=0, the initial state value S
0
is determined on the basis of the data in the array elements of the message array. Specifically, an initial function for determining the initial state value S
0
is provided, and a value based on the data in all the elements of the message array (for example, the exclusive OR of the data) is input to this initial function.
In step (b), the (j+

Affiliated with

Also associated with

Rating

Data hiding and extraction methods does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data hiding and extraction methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data hiding and extraction methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3048168