Image analysis – Applications
Reexamination Certificate
2000-12-08
2004-02-10
Ahmed, Samir (Department: 2621)
Image analysis
Applications
C382S252000, C283S094000, C358S003030, C358S003280
Reexamination Certificate
active
06690811
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to methods and apparatus for producing a halftone image including embedded data, such as data indicating the origin of the image. In particular the data is embedded such that it can be revealed by comparison of the halftone image with a second halftone image.
BACKGROUND OF THE INVENTION
Nowadays, digital images can be distributed easily through the Internet and the Web. As a side effect, the problems of copyright infringement and authentication are growing rapidly with the ease of distribution. One possible solution is to hide within the images “watermarking” data such as identity of the company which produced the image, the owner of the image, its creation date and time, for copyright protection and authentication purposes. The embedded watermarking data should not be visible.
Halftoning is a method widely used to transform multi-tone images (typically “grey-scale” images with 256 levels at each pixel, although in this document the term multi-tone is used to imply merely that there are at least 3 levels, or more preferably at least 10 levels) into a “halftone” image having only two tone colors (i.e. 2 levels) at each pixel. Such methods are used widely, for example in computer printers and for publishing newspapers, magazines and books. From a distance, halftoned images resemble images with multi-tones. The two most commonly used halftoning techniques are known as “ordered dithering” (see B. E. Bayers, “An optimum method for two level rendition of continuous tone pictures”, Proc. of IEEE Int. Communication Conf., pp2611-2615, 1973) and “error diffusion” (R. W. Floyd, L. Steinberg, “An adaptive algorithm for spatial greyscale”, Proc. SID, pp 75-77, 1976). Typically, the second of the two techniques produces half-tone images of higher quality.
Ordered dithering is a computationally simple and effective halftoning method. It employs a “screen” having at each pixel a pseudo-random value, and sets the tone of the halftone value at each pixel according to whether the grey-tone value at that pixel is higher or lower than the pseudo-random value. With ordered dithering, the average local intensity within a screen region of the generated halftone image corresponds approximately to that of the original grey-tone image. Unfortunately, the technique introduces a high level of undesirable noise and gives low image quality.
Error diffusion is a more advanced technique usually used in certain printers. It is more complicated than ordered dithering, but it can generate halftone images with higher visual quality. It is a single pass algorithm (i.e. pixels are processed in a single sweep across the image. For example, the method may process the rows one-by-one from top to bottom of the image, and, for each row, process the pixels one-by-one along the row, e.g. left to right; clearly these orders may be varied, e.g. by processing successive columns rather than rows). In error diffusion, the halftoning output is obtained by comparing the grey-tone value of each given pixel with a fixed threshold, and generating a halftone value according to the result of the comparison. The halftoning error generated in this way (for example, in the case of a pixel having a grey-tone value below the threshold, the halftoning error for that pixel is the grey-tone value itself) is fed forward to its adjacent neighbors, specifically to pixels which are later in the single pass across the image performed by the algorithm. For those adjacent pixels the halftone values are calculated by comparing the threshold with a sum of the grey-tone values for those pixels plus a fraction of the error value fed forward. In other words, each image pixel effectively has an adaptive threshold. The error feedback helps to make the local average intensity of the halftone image approximately equal to the original multi-tone image (neglecting any trivial constant factor arising because from the definition of the two possible halftone values (e.g. either 0 or 255 whereas the multi-tone values are in the range 0 to 255)). An essential component of error diffusion is its error feedback kernel, which determines the proportion of the error fed from a given pixel to each of its adjacent pixels. Different kernels can have quite different behaviour. Two commonly used error feedback kernels are the Jarvis kernel and the Steinberg kernel shown in Tables 1 and 2 respectively.
The Jarvis kernel has a large support and tends to give halftone images with high contrast and coarse texture. The Steinberg kernel has smaller support and gives halftone images with fine texture and good contrast. In each case, each element of tables 1 and 2 refers to a respective pixel. The element with an entry marked “x” refers to the pixel currently being processed. Each numerical entry shows the weighting on the pixel presently being processed from the error caused by halftoning in the pixel with the numerical entry.
TABLE 1
The Jarvis kernel
1
3
5
3
1
3
5
7
5
3
5
7
X
TABLE 2
The Steinberg kernel
1
3
5
7
X
There have been quite a number of watermarking methods designed for natural grey scale images. However, few, if any, of the algorithms can be applied to halftone images. This is because halftone images have only 2 tones and have a large amount of high frequency noise resulting in little intensity redundancy. Few image processing operations can be performed on halftone images without creating serious perceptual artifacts.
The present inventors have recently proposed a technique in which data is hidden in a half-tone image at individual data storage pixels chosen using a pseudo-random number generator. At each data storage pixel, the halftone value is fixed at a value determined by the data to be hidden.
In a first case, the data is hidden within an existing halftone image. Hiding the data requires reversing the tone value at about half of the data storage pixels. For such pixels, the tone value of one of the adjacent pixels is also reversed—to maintain the local average intensity.
In a second case, the data is hidden while the half-tone image is generated from a grey-scale image by error diffusion. In the case of the data storage pixels, the halftone value is determined by the data to be hidden. The error caused by doing this (i.e. the difference between the grey-tone value of the original image for that pixel and the halftone value determined by the data to be hidden) is fed to adjacent pixels, as in error diffusion. However, this error may be fed not only to pixels which are ahead in the sweep across the image, but also to pixels which are earlier in the single pass across the image (i.e. the kernel is “non-causal”).
In both of these cases, the hidden data is regenerated by using the same pseudo-random algorithm to determine the data storage pixels. This algorithm is very effective in hiding a large amount of data with very low degradation of the half-tone image (e.g. 4096 bits of hidden data in a 512×512 image).
In certain applications, however, it is preferable for the data to be hidden so that it can be extracted more rapidly from the half-tone image. For example, it would be useful if the data could be extracted from a digitised half-tone image by a method which does not require knowledge or use of a pseudo-random algorithm. In some applications it would be advantageous if the method can be performed directly on a printed image without the need for scanning it.
U.S. Pat. Nos. 5,709,703, 5,734,752, 5,488,664, 5,315,098 and 5,296,559 all relate to methods of generating a halftone image including hidden data by ordered dithering. Generally speaking, they transform a multi-tone image into two halftone images by ordered dithering using respective screens. A first screen is composed of random grey-tone values at each pixel. A second screen is composed of random grey-tone values correlated with the first screen in some portions, and grey-tone values uncorrelated with the first screen in other portions. When the two halftone images are superimposed, the portions in which the two screens are correlated have a dif
Au Oscar Chi-Lim
Fu Ming Sun
Ahmed Samir
Bhatnagar Anand
Burns Doane Swecker & Mathis L.L.P.
The Hong Kong University of Science and Technology
LandOfFree
Methods and apparatus for hiding data in halftone images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for hiding data in halftone images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for hiding data in halftone images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3350304