Method and system for digital image signatures.

The present invention relates to a method of encoding a signature into a digital image and auditing the digital image to determine if it is derived from the encoded image.

Various images are generally distributed to a large number of users in traditional printed matter and photographic media. For example, printed matter, photographs and film clips relating to the general public may be distributed in media. Owners may want to audit the use of those images in printed matter and electronic media, and therefore analyze printed matter, film and digital images and either obtain them directly from the owner or derive from those images. We need a way to determine if this is the case. For example, the owner of the statue may want to restrict access or use of the statue. In order to monitor and enforce such restrictions, it is useful to have a method of verifying that the image is a copy or derivative of the image of the owner. This method of proof must be accurate and unobstructive. In addition, the method must be capable of detecting unauthorized copies that have been resized, rotated, cut, or otherwise slightly modified.

<p> In the field of computers, digital signatures are applied to digital data other than images to identify the source of the data. These known digital signatures have not been applied to digital image data for various reasons. One reason for this is that if the data to which these known digital symbols are applied is changed, these digital symbols will be lost. Digital images are often modified due to the formation of unintended "noise" by the mechanical playback equipment used each time they are printed, scanned, copied, or photographed. In addition, it is often desired to intentionally resize, rotate, cut, or otherwise resize the image. Therefore, existing digital signatures are unacceptable for use in digital images.</p>

<p> The present invention is a method and system for embedding an image symbol in a visible image, and in the preferred embodiments described herein, a method and system that can be applied to both digital display and other media such as printed matter and film. provide. The sign identifies the source or ownership of the statue, and also distinguishes separate copies of the single statue. In a preferred embodiment, these signatures survive image conversions such as resizing and print-to-film conversions, and thus the subsequent use of digital images, including prints and other forms of derivative images. It provides a way to track.</p><p> In the preferred embodiment described below, a plurality of sign points arranged in the original image having pixels with pixel values are selected. The pixel value of the sign point is adjusted by the amount that can be detected by the digital scanner. The adjusted sign points form a digital sign that is stored to identify the image derived from that image in the future.</p><p> In a preferred embodiment of the invention described below, the signature is embedded in the original image by positioning candidate points such that the pixel values are relatively extreme. The symbol points are selected from the candidate points, and the data bits are encoded by adjusting the pixel values at and around each point at each symbol point. It is preferable that the signature is redundantly embedded in the image, and the signature can be identified by using any of the redundant displays. The signature is stored for later use in identifying the image.</p><p> According to a preferred embodiment, identifying the image involves ensuring that the image is normalized, i.e., of the same size, rotation and brightness level as the original image. If not pre-normalized, the image is normalized by aligning and adjusting the luminance values of the subset of pixels in the image to match the corresponding subset in the original image. The normalized image is then subtracted from the original image and the result is compared to the stored digital signature. In another embodiment, the normalized image is directly compared to the marked image.</p>

The present invention relates to a method and system for embedding a signature in an original image to form the signatured image. A preferred embodiment comprises selecting a large number of candidate points in the original image and selecting a large number of sign points from among these candidate points. These sign points are slightly modified to form the sign. The sign points are stored for later use to audit the image and determine if the image is derived from the marked image.

The sign is encoded in the visible domain of the image and therefore becomes part of the image and cannot be detected or removed by known knowledge of the sign. The important point is that the changes represented by the signature are too small for the human eye to see, but are easily and consistently recognizable by a normal digital image scanner, and then the signature is extracted by a software algorithm. It is possible to decipher and collate.

Unlike known signing methods used for non-image data, this signing survives significant image transformations that retain the visible image but can completely alter the digital data. Certain transformations allowed include resizing the image to a larger or smaller size, rotating the image, adjusting the color, brightness and / or contrast uniformly, and making limited cuts. .. What is important is that the signature survives the process of printing the image on paper or film and rescanning it into digital form.

The computer system 10 shown in FIG. 1 is used to carry out the present invention. The computer system 10 includes a computer 12 having ordinary complementary memory and logic circuits, a display monitor 14, a keyboard 16, a mouse 18, or other indicating device. The computer system also includes a digital scanner 20 used to form a digital image that represents an original image such as a photograph or picture. Typically, pictorial delicate images are converted to prints or films before being scanned into digital form. In one embodiment, the printer 22 is connected to the computer 12 to print a digital image output from the processor. Further, the digital image can also be output in a data format to a storage medium 23 such as a floppy disk for later display at a remote location. Any digital display device such as a regular computer printer, XY plotter or display screen may be used.

An example of the output of the scanner 20 to the computer 12 is the digital image 24 shown in FIG. More specifically, the scanner outputs data representing the digital image, and the computer displays the digital image 24 on the display monitor 14. The term "digital image" as used herein refers to digital data representing a digital image, a digital image displayed on a monitor or other display screen, and a digital image printed by a printer 22 or a remote printer.

The digital image 24 is drawn with a large number of pixels 24 having different pixel values. In the grayscale image 24, the pixel value is a luminance value representing a luminance level that changes from black to white. In a color image, a pixel has a color value and a luminance value, both of which are pixel values. The color value can include the value of any component in the display of color by vector. FIG. 3 shows a digital image 24A in the form of an array of pixels 26. Each pixel is combined with one or more pixel values, which are the luminance values from 0 to 15 in the example shown in FIG.

The digital image 24 shown in FIG. 2 contains thousands of pixels. The digital image 24A shown in Figure 3 contains 225 pixels. The present invention is preferably used for images with millions of pixels. Therefore, of course, the usefulness of the present invention will be briefly described here.

According to a preferred embodiment of the present invention, a large number of candidate points are positioned within the original image. A sign point is selected from these candidate points and changed to form a sign. A sign is a pattern of any number of sign points. In a preferred embodiment, the signature is a binary number 16-bit to 32-bit in length. The sign points can be anywhere in the image, but are preferably chosen to be as inconspicuous as possible. The number of sign points is preferably much larger than the number of bites of the sign. This makes it possible to redundantly encode the signature in the image. When using 6-32 bit signatures, 50-200 signature points are preferred in order to obtain a large number of signatures for the image.

In a preferred embodiment of the invention, candidate points are positioned by finding relative maximums and minimums (referred to as overall extremes) in the image. These extremes locally represent extreme brightness or color. Figure 4 shows what the relatively extremes mean. FIG. 4 is a graph showing the pixel values of the small part of the digital image. The vertical axis of this graph represents the pixel values, while the horizontal axis represents the pixel positions along a single line of the digital image. The small variation in pixel value shown in 32 represents a digital image portion where the brightness or color changes slightly between pixels. The relative maximum value of 34 represents the pixel with the highest pixel value for a given area of the image. Similarly, the relative minimum value of 36 represents the pixel with the lowest pixel value for a given area of the image.

Relatively extreme values are the preferred sign points for two main reasons. First of all, they are easily searched by a simple and well-known process. And second, they allow the sign points to be encoded less noticeably.

One of the easiest ways to determine relatively extreme values is to use the "mean difference" technique. This technique uses a predetermined neighborhood around each pixel 26, with small neighbors 28 and large neighbors 30 shown in Figures 2 and 3. In the examples shown here, these neighborhoods are square for simplicity, but in preferred embodiments circular neighborhoods are used. This technique determines the difference between the average pixel value of a small neighborhood and the average pixel value of a large neighborhood. When this difference is large relative to the difference for the surrounding pixels, the first pixel value is the relative maximum or minimum.

Using the image of FIG. 3 as an example, the average difference with respect to pixel 26A is determined as follows. Adding the pixel values in the small neighborhood 28A of 3x3 pixels gives 69, which is divided by 9 pixels to average 7.67. Adding the pixel values within the large neighborhood 30A of 5x5 pixels gives 219, which is divided by 25 pixels to give an average of 8.76, so the difference between the means is -1.09. Similarly, the average of the small neighbor 28G is 10.0 and the average of the large neighbor 30G is 9.8, so the difference between the averages of the pixels 26G is 0.2. The same calculation for pixels 26B to 26F results in the following table.<u style="single">26A 26B 26C 26D 26E 26F 26G</u>Small neighborhood 7.67 10.56 12.89 14.11 13.11 11.56 10.0 Large neighborhood 8.76 10.56 12.0 12.52 12.52 11.36 9.8 Average difference -1.09 0.0 0.89 1.59 0.59 0.2 0.2 According to pixels 26A-26G, pixel 26D has a relative maximum, the mean difference of 1.59 being greater than the mean difference of the other pixels examined in that row. To determine if pixel 26D is not just a small variation, but a relative maximum, its average difference must be compared to the average difference with respect to the pixels surrounding it in a large area.

Extreme values within 10% of the image size on either side should not be used as sign points. This prevents the signing points from being lost due to the provision that cuts the border area of the image. Also, it is preferable to use relatively extreme values that do not appear in a regular pattern but are randomly and widely spaced.

Using the average difference technique or other known techniques, a large number of extreme values can be obtained, the number of which is based on the pixel density and contrast of the image. Of the total number of extreme values found in this way, in the preferred embodiment 50-200 sign points are selected. This is done manually by the user selecting each sign point from the extreme values displayed on the display monitor 14 with a keyboard 16, mouse 18, or other indicator. These extreme values may be displayed as a digital image and each point may be selected using a mouse or other pointing device pointing to a pixel, or these values may be displayed as a list of coordinates. , A keyboard, mouse or other indicator may be used for selection. Alternatively, the computer 12 can be programmed to randomly select the sign points or to select based on a pre-programmed pattern.

At each sign point in the image, 1-bit binary data is encoded by adjusting the pixel value at that point and the pixel values around it. The image is modified to represent binary 0 or 1 by adjusting the pixel value at that sign point to be slightly positive or negative by 2% to 10%. Pixels surrounding each of its symbol points in a grid of about 5x5 to 10x10 are preferably adjusted proportionally to ensure a continuous transition to new values at that symbol point. A large number of bits are encoded at the sign point to form a pattern that is a sign for the image.

In a preferred embodiment, the signature is the pattern of all signature points. When auditing the image, if a statistically significant number of potential sign points in the image match the corresponding sign points in the marked image, the image is marked. It is thought that it was derived from the statue. A statistically significant number is slightly less than 100%, but it is sufficient if the image is reasonably convinced that it is derived from the marked image.

In another embodiment, the signatures are encoded using a redundant pattern, which distributes the signatures within the signature points in a way that can be reliably retrieved using only a subset of the signature points. In one embodiment, only a predetermined number of exact copies of the signature are encoded. Alternatively, other redundant display methods such as error correction codes may be used.

The symbols are stored in a database where they are associated with the original image in order to audit future images and determine if they match the signed image. The symbol can be stored by associating the bit value of each symbol point with the xy coordinate of that symbol point. The sign may be stored separately from or as part of the marked image. At this time, the signed image is distributed in digital form.

As mentioned above, the signed image can be transformed and manipulated to form a derived image. Derived images are derived from images that have been marked by various transformations such as resizing, rotating, adjusting color, brightness and / or contrast, cutting, converting to print or film. Derivation may be done in multiple stages or processes, or the signed image may simply be copied directly.

It is assumed that the derivation of the image that the owner intends to track includes only the intended use that substantially preserves the resolution and general quality of the image. A 90% reduction in size, significant discoloration, or a clear reduction in pixel value destroys the signature, but also reduces the significance and value of the image so that it is unwilling to audit.

To audit the image based on a preferred embodiment, the user identifies the original image that the image appears to be a duplicate. In the case of a print or film image, the image is scanned to form a digital image file. Scanning is not required for digital images. This digital image is normalized to the same size and the same total brightness, contrast and color profile as the unmodified original image using the techniques described below. The image is analyzed by the method described below to extract the signature, if any, and compare it with the signature stored for the image.

This normalization process involves a series of steps to undo the transformations already made on the image and bring it back as close as possible to the resolution and appearance of the original image. It is assumed that the image has been manipulated and transformed as described above. In order to align the image with the original image, in a preferred embodiment, three or more points corresponding to the points in the original image are selected from the image. These three or more points of the image are aligned with the corresponding points of the original image. The points of the image that are not selected are rotated and resized as needed to accept the alignment of the selected points.

For example, FIG. 5 shows the digital image 38, which is smaller than the original image 24 of FIG. To resize the image, the user points to three points, such as the mouth 40B, ears 42B, and eyes 44B, of the image using a mouse 18 or other pointing device. Since it is usually difficult to pinpoint a single pixel, the computer chooses the extreme value closest to the pixel pointed to by the user. The user points to the mouth 40A, ears 42A and eyes 44A of the original image. Computer 12 may size the images as needed to ensure that points 40B, 42B, and 44B are positioned with each other in the same way that points 40A, 42A, and 44A are positioned with each other in the original image. Change and rotate. The remaining pixels are repositioned in proportion to the repositioning of these points 40B, 42B and 44B. By aligning these three points, the entire image is aligned with the original image without having to align each pixel individually.

The next step after the image is aligned is to normalize the brightness, contrast and / or color of the image. This normalization involves adjusting the pixel values of the image to match the value distribution profile of the original image. This is done by a technique similar to that used to align the images. The subset of pixels in the image is adjusted to be equal to the corresponding pixels in the original image. Pixels that are not in this subset are adjusted in proportion to the adjustments made to the pixels in the subset. The image's pixels corresponding to the sign points must not be within a subset of pixels. Otherwise, the signature points of the image will be hidden from detection when adjusted equally to the corresponding pixels of the original image.

In a preferred embodiment, the subset includes the brightest and darkest pixels of the image. These pixels are adjusted to have a brightness value equal to the brightness value of the corresponding pixel in the original image. To ensure that the sign points can be detected, the sign points must not be selected from the brightest and darkest pixels of the original image during the above-mentioned sign embedding process. For example, after selecting a sign point from less than 5% of the brightest and darkest to ensure no overlap, then pixel out of 3% of the brightest and darkest to adjust the subset. Can be used.

The image is preferably compared to the original image after it has been fully normalized. One way to compare these images is to subtract one image from the other. By this deduction, a digital image including the sign points existing in the image is formed. These sign points, if any, are compared to the sign points stored for the marked image. If the sign points do not match, the image is not a derivative of the marked image unless it is substantially modified from the marked image.

In another embodiment, the normalized image is compared directly to the signed image, rather than subtracting it from the original image. This comparison involves subtracting the image from the marked image. If this deduction produces little or no image, then the image is equal to the marked image and is therefore derived from the marked image.

In yet another embodiment, instead of normalizing the entire image, only the portion of the image surrounding each potential sign point has the same general resolution and appearance as the corresponding portion of the original image. Is normalized as. This is done by selecting each potential sign point of the image and selecting the portion around each potential sign point. Normalization of each selected portion is performed according to the same method as described above for normalization of the entire image.

By normalizing each selected part individually, each potential signing point of the image can be directly compared to the corresponding signing point of the marked image. It is preferred that the mean value be calculated for each potential sign point by averaging the pixel values of the potential sign points with the pixel values of a plurality of pixels around the potential sign point. The average value calculated for each sign is directly compared to the corresponding sign point in the marked image.

As described above, the method of normalizing and extracting the signature from the image was related to the luminance value, but the same method can be used for the color value. Instead of or in addition to normalizing by changing the luminance value, the color value of the image can be adjusted equally to the corresponding color value of the original color image. However, it is not necessary to adjust the color values to encode the signatures or extract the signatures from the color image. The color image uses pixels having pixel values including luminance and color values. Digital signatures can encode any pixel value, regardless of whether the pixel value is a luminance value, a color value, or a pixel value in another format. Luminance values are preferred because they can be easily changed without being visible to the human eye.

Although the specific embodiments of the present invention have been described in detail above for the purpose of explanation, it will be clear that various changes can be made without departing from the spirit and scope of the present invention. Therefore, the present invention shall be limited only by the scope of claims.

<figref num="1">It is a figure which shows the computer system used in the preferable embodiment of this invention.</figref><figref num="2">It is a figure which shows the digital image sample in which a preferable example of this invention is used.</figref><figref num="3">It is a figure which shows the digital image in the form of a pixel array which has a pixel value.</figref><figref num="4">It is a graph of the pixel value which shows the relative minimum and maximum pixel value.</figref><figref num="5">It is a figure which shows the digital image compared with the image of FIG. 2 by a preferable embodiment of this invention.</figref>

Code description

10 computer system 12 computers 14 Display monitor 16 keyboard 18 mouse 20 digital scanner 22 printer 23 Storage medium 24 Digital image 26 pixels