Image analysis – Applications
Reexamination Certificate
2000-07-13
2004-03-02
Johns, Andrew W. (Department: 2621)
Image analysis
Applications
C358S003280
Reexamination Certificate
active
06700992
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to embedding messages in a halftoned digital image with an error diffuison technique.
BACKGROUND OF THE INVENTION
Digital halftoning is a technique employing digital image processing to produce a halftoned input digital image from an input digital image. An input digital image normally consists of pixels of discrete values typically ranging from 0 to 255. To reproduce this image on an output device capable of printing dots of one gray level (e.g. black), it is necessary to convert the input digital image to a halftoned digital image using some form of halftoning techniques. Halftoning methods rely on the fact that an observer's eye will spatially average over some local area of the halftoned digital image so that intermediate gray levels can be created by turning some of the pixels “on” and some of the pixels “off” in some small region of the halftoned digital image. The fraction of the pixels that are turned on will determine the apparent gray level. Common prior art methods of digital halftoning include error diffusion and dithering (see R. Ulichney, “Digital Halftoning,” MIT Press, Cambridge, Mass., 1987).
Error diffusion is an adaptive algorithm that produces patterns with different spatial frequency content depending on the input digital image value.
FIG. 1
shows a prior art block diagram depicting a basic error diffusion technique. This technique is disclosed in more detail in “An Adaptive Algorithm for Spatial Greyscale,”
Proceedings of the Society for Information Display
, volume 17, pp. 75, 1976 by R. W. Floyd and L. Steinberg. For purpose of illustration it will be assumed that the pixels of the input digital image span the range from 0 to 255. As shown in
FIG. 1
, the pixels of an input digital image are thresholded in block
10
to produce thresholded pixels. The block
10
provides a signal having a 0 for any pixel of the input digital image below the threshold, and a 255 for any pixel of the input digital image above the threshold. A difference signal generator
12
receives the signal representing the pixel of the input digital image from block
10
and also from the output of an adder
16
, which will be discussed later. The difference signal generator
12
produces a difference signal representing the error introduced by the thresholding process. The difference signal is multiplied by a series of error feedback weights in a error feedback
14
, and is provided to the adder
16
which adds the weighted difference signal to the nearby pixels that have yet to be processed. This insures that the arithmetic mean of the pixels of the halftone digital image is preserved over a local image region.
FIG. 2
illustrates how a typical error can affect neighboring pixels in a halftoned digital image. The halftoned digital image from error diffusion is generally considered to be of high quality, since most of the halftone noise is distributed in a high spatial frequency band where human visual sensitivity is relatively low.
An artifact that is typically associated with error diffusion halftoning technique is known as “worms.” Worms are formed when the black or white pixels of a halftoned digital image appear to string together in an area that should be otherwise uniform. Uniform image regions of certain gray levels, i.e., highlight regions, are especially susceptible to “worm” artifacts.
One much desired requirement for the usage of digital images is the detection of the unauthorized use of copyrighted or personal images. For example, the professional photographers are greatly concerned about the illegitimate use of their copyrighted images in the recent years. As the use of Internet and digital imaging devices become more popular, this concern is increasingly shared by common consumers. One example of the methods developed for this purpose is disclosed in commonly assigned U.S. Pat. No. 5,822,660.
SUMMARY OF THE INVENTION
An object of the present invention is to efficiently halftone digital images while embedding messages in such halftoned digital images at the same time.
This object is achieved by a method of producing a halftoned digital image having an embedded message, comprising the steps of:
a) using a digital message and at least one digital carrier image to produce a scrambled message image; and
b) halftoning the digital image employing an error diffusion process where noise is added to the digital image, the noise including the scrambled message image.
This object is further achieved by a method for embedding a message in a halftoned digital image, comprising the steps of:
a) receiving an input digital image having a plurality of pixels;
b) providing a digital message image having pixels representing the message to be embedded;
c) providing a digital carrier image which has a random distribution of pixel values;
d) using the digital message image and the digital carrier image to produce a scrambled message image; and
e) halftoning the input digital image employing an error diffusion process where noise is added to the input digital image, the noise includes the scrambled message image, whereby the scrambled message image is embedded in the halftoned digital image.
ADVANTAGES
An advantage of the present invention is that the efficiency of halftoning an input digital images and embedding information in the halftoned digital image is improved. Information can be embedded in the halftoned digital image and “worm” artifacts can be minimized in the halftoned digital image at the same time.
The halftoned digital images can be printed or displayed. A feature of embedding messages in the printed or displayed images is that the messages can subsequently be extracted later for proofing the authentication of the image or for detecting the unauthorized use of the image.
REFERENCES:
patent: 5396559 (1995-03-01), McGrew
patent: 5790703 (1998-08-01), Wang
patent: 5822660 (1998-10-01), Wen
patent: 5859920 (1999-01-01), Daly et al.
patent: 5875249 (1999-02-01), Mintzer et al.
patent: 5946414 (1999-08-01), Cass et al.
patent: 5949055 (1999-09-01), Fleet et al.
patent: 6044156 (2000-03-01), Honsinger et al.
patent: 6092732 (2000-07-01), Curry
patent: 6094483 (2000-07-01), Fridrich et al.
patent: 6556688 (2003-04-01), Ratnaker
patent: 2001/0054150 (2001-12-01), Levy
“Digital Signal Processing” by Alan V. Oppenheim and Ronald W. Schafer, Prentice-Hall, Inc. 1975, pp. 101-115.
“An Adaptive Algorithm for Spatial Greyscale” by R. W. Floyd and L. Steinberg, Proceedings of the Society for Information Display, vol. 17, p. 75, 1976.
Honsinger Chris W.
Yu Qing
Eastman Kodak Company
Johns Andrew W.
Nakhjavan Shervin
Watkins Peyton C.
LandOfFree
Adaptive message embedding error diffusion method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive message embedding error diffusion method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive message embedding error diffusion method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3272580