Abstract:
This patent document relates generally to steganography and digital watermarking. One claim recites, a method of encoding auxiliary information in an image or video. The method includes: determining a watermark tweak for an attribute of an image or video sample to encode auxiliary information in the image or video; and altering color values of the image or video sample to effect the watermark tweak, said altering alters color values based at least in part on both: i) visibility of color value alterations, and ii) anticipated watermark detection. Of course, other claims are provided too.

Description:
RELATED PATENT DATA 
       [0001]    This application is a continuation of Ser. No. 13/971,607, filed Aug. 20, 2013 (U.S. Pat. No. 8,744,120) which is a division of U.S. patent application Ser. No. 12/708,278, filed Feb. 18, 2010 (U.S. Pat. No. 8,515,120), which is a continuation of U.S. patent application Ser. No. 11/143,088, filed Jun. 1, 2005 (U.S. Pat. No. 7,668,334), which claims the benefit of U.S. Provisional Patent Application Nos.: 60/585,490, filed Jul. 2, 2004; 60/620,093, filed Oct. 18, 2004; and 60/642,915, filed Jan. 10, 2005. 
         [0002]    The present application is also related to U.S. Pat. Nos. 6,700,995; 6,590,996 and 6,307,949. 
         [0003]    Each of the U.S. patent documents mentioned in this application is hereby incorporated by reference. 
     
    
     TECHNICAL FIELD 
       [0004]    The present invention relates generally to digital watermarking. In particular, the present invention relates to modifying imagery to better receive digital watermarking. 
       BACKGROUND AND SUMMARY OF THE INVENTION 
       [0005]    Not all images are suitable to receive digital watermarking. Some images are too light (e.g., “washed out”) or have a large percentage of pixels that include high saturation. Other images may be too dark to effectively receive digital watermarking. The present invention provides methods and apparatus to modify an image to better receive digital watermarking. The methods and apparatus can be integrated into image workflows and only modify those images that may be sub par in terms of their ability to receive and hide digital watermarking. One example workflow is image capture for identification documents (e.g., at DMV station or passport application process). Another example is a photography studio during its print (or proofs) process. Of course, these are but a few of the many environments in which our inventive techniques will benefit. 
         [0006]    Digital watermarking technology, a form of steganography, encompasses a great variety of techniques by which plural bits of digital data are hidden in some other object, preferably without leaving human-apparent evidence of alteration. 
         [0007]    Digital watermarking may be used to modify media content to embed a machine-readable code into the media content. The media may be modified such that the embedded code is imperceptible or nearly imperceptible to the user, yet may be detected through an automated detection process. 
         [0008]    There are many processes by which media can be processed to encode a digital watermark. In physical objects, the data may be encoded in the form of surface texturing or printing. Such marking can be detected from optical scan data, e.g., from a scanner or web cam. In electronic objects (e.g., digital audio or imagery—including video), the data may be encoded as slight variations in sample values. Or, if the object is represented in a so-called orthogonal domain (also termed “non-perceptual,” e.g., MPEG, DCT, wavelet, etc.), the data may be encoded as slight variations in quantization values or levels. The assignee&#39;s U.S. Pat. Nos. 6,122,403 and 6,614,914 are illustrative of certain watermarking technologies. Still further techniques are known to those of ordinary skill in the watermarking art. 
         [0009]    Digital watermarking systems typically have two primary components: an embedding component that embeds a watermark in the media content, and a reading component that detects and reads the embedded watermark. The embedding component embeds a watermark pattern by altering data samples of the media content. The reading component analyzes content to detect whether a watermark pattern is present. In applications where the watermark encodes information, the reading component extracts this information from the detected watermark. 
         [0010]    One problem that arises in many watermarking applications is that of object corruption. If the object is reproduced, or distorted, in some manner such that the content presented for watermark decoding is not identical to the object as originally watermarked, then the decoding process may be unable to recognize and decode the watermark. To deal with such problems, the watermark can convey a reference signal or “orientation component.” The orientation component is of such a character as to permit its detection even in the presence of relatively severe distortion. Once found, the attributes of the distorted reference signal can be used to quantify the content&#39;s distortion. Watermark decoding can then proceed—informed by information about the particular distortion present. 
         [0011]    The Assignee&#39;s U.S. Pat. Nos. 6,614,914 and 6,408,082 detail orientation components, and processing methods, that permit such watermark decoding even in the presence of distortion. In some image watermarking embodiments, an orientation component comprises a constellation of quasi-impulse functions in the Fourier magnitude domain, each with pseudorandom phase. To detect and quantify the distortion, the watermark decoder converts the watermarked image to the Fourier magnitude domain and then performs a log polar resampling of the Fourier magnitude image. A generalized matched filter correlates a known orientation signal with the re-sampled watermarked signal to find the rotation and scale parameters providing the highest correlation. The watermark decoder performs additional correlation operations between the phase information of the known orientation signal and the watermarked signal to determine translation parameters, which identify the origin of the watermark message signal. Having determined the rotation, scale and translation of the watermark signal, the reader then adjusts the image data to compensate for this distortion, and extracts the watermark message signal. 
         [0012]    One aspect of the present invention is a method to condition an image prior to receiving steganographic encoding. The process includes receiving an image and subjecting the image to an approximation of an expected workflow process. The subjected image is evaluated to determine whether the image includes characteristics that are conducive to receive steganographic encoding in view of the expected workflow process. If the digital image is not conducive, the image is modified. 
         [0013]    Another aspect of the present invention is a method to analyze a digital image to determine whether the digital image will be a suitable host to receive digital watermarking. The method includes processing a digital image in accordance with an approximation of an expected workflow process, and analyzing the processed digital image to determine whether the digital image forms a suitable host to receive digital watermarking. If the digital image is not suitable, the digital image is modified to better receive digital watermark in anticipation of the expected workflow process. 
         [0014]    Additional features, aspects and advantages of the present invention will become even more apparent with reference to the following detailed description and accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0015]      FIG. 1A  illustrates an example image workflow. 
           [0016]      FIG. 1B  illustrates image analysis and modification for the workflow of  FIG. 1A . 
           [0017]      FIG. 2  illustrates a response curve for an expected image capture device and printer. 
           [0018]      FIG. 3A  illustrates an image including areas susceptible to washing out with workflow processing;  FIG. 3B  illustrates a corresponding luminosity histogram; and  FIG. 3C  illustrates the  FIG. 3A  image after processing according to the  FIG. 2  curve. 
           [0019]      FIG. 4  illustrates tone correction for washed-out images. 
           [0020]      FIG. 5A  illustrates the  FIG. 3A  image after applying the tone correction of  FIG. 4 ;  FIG. 5B  illustrates a corresponding luminosity histogram; and  FIG. 5C  illustrates the  FIG. 5A  image after processing according to the  FIG. 2  curve. 
           [0021]      FIG. 6A  illustrates an image including relatively darker image regions;  FIG. 6B  illustrates a corresponding luminosity histogram; and  FIG. 6C  illustrates the  FIG. 6A  image after processing according to the  FIG. 2  curve. 
           [0022]      FIG. 7  illustrates tone correction for images including dark or shadow regions. 
           [0023]      FIG. 8  illustrates an image including both washed-out regions and relatively darker image regions. 
           [0024]      FIG. 9  illustrates tone correction for an image including both washed-out regions and darker image regions. 
           [0025]      FIG. 10  is a flow diagram for image analysis. 
           [0026]      FIG. 11  illustrates a cumulative histogram of good (or acceptable) images;  FIG. 12  illustrates a cumulative histogram of washed-out images; and  FIG. 13  illustrates a cumulative histogram of images including relatively darker regions. 
           [0027]      FIGS. 14A and 14B  illustrate an image include a relatively high level of noise, and  FIG. 14C  illustrates a corresponding histogram. 
           [0028]      FIGS. 15A and 15B  illustrate corresponding images—after smoothing of the  FIGS. 14A and 14B  images—including a relatively lower level of noise, and  FIG. 15C  illustrates a corresponding histogram. 
           [0029]      FIG. 16  illustrates an imaging system characteristic response curve. 
           [0030]      FIG. 17  illustrates an image analysis algorithm flow diagram. 
           [0031]      FIG. 18  illustrates an image with significant highlight content and a corresponding histogram. The histogram plots image grayscale values against percentages of pixels in the image. 
           [0032]      FIG. 19  illustrates a tone correction calculated for an image (Appendix A,  FIG. 3 ) with significant highlight content. 
           [0033]      FIG. 20  illustrates an image with significant highlight content and its histogram after tone correction of  FIG. 19 . The histogram shows how pixels values have moved relative to the histogram in  FIG. 18 . 
           [0034]      FIG. 21  illustrates an error rate for a watermark including  96  payload bits. 
           [0035]      FIG. 22  illustrates SNR distributions of two datasets. 
           [0036]      FIG. 23  is a diagram showing human contrast sensitivity at various watermark embedding spatial frequencies. ( FIG. 23  corresponds to FIG. 1 in priority application No. 60/620,093, filed Oct. 18, 2004.) 
           [0037]      FIG. 24  is a diagram illustrating detection rates for various watermark detection weightings for RGB channels. ( FIG. 24  corresponds to FIG. 2 in priority application No. 60/620,093, filed Oct. 18, 2004.) 
       
    
    
     DETAILED DESCRIPTION 
       [0038]      FIG. 1A  illustrates a conventional image workflow. A digital image  10  is received. For example, the image is captured by a digital camera, converted to a digital image from conventional film, or obtained via an optical scanning device. The digital image  10  is printed by printer  12  onto a substrate  14 . For example, if digital image  10  includes a photograph, it may be printed onto an identification document, such as a passport, driver&#39;s license or other photo ID. Printed substrate  14  is expected to be eventually captured by an image capture device  16  (e.g., an optical sensor, scanner, digital camera, cell phone camera, etc.). The image capture device  16  produces a digital representation  18  of substrate  14 , including a representation of digital image  10  printed thereon. 
         [0039]    We can make predictions of resulting image quality based on components (e.g., printer  12  and capture device  16 ) in a workflow. Moreover, we can make predictions of a workflow system to even more successfully embed and read digital watermarks. 
         [0040]    In an ideal image workflow system all components of a digital watermark embedder and reader systems are preferably modeled as approximately linear, and all watermarked images read in a similar manner (e.g., assuming equal watermark embedding strength). 
         [0041]    In practice, however, a linear model fails due to non-linearity introduced in capture and print devices. Non-linearity of a capture and print device can be compensated for by characterizing the devices and compensating for their response (see, e.g., Assignee&#39;s U.S. Pat. No. 6,700,995 and U.S. patent application Ser. No. 10/954,632, filed Sep. 29, 2004, issued as U.S. Pat. No. 7,443,537, which are herein incorporated by reference.). 
         [0042]    But in many cases the watermark capture and/or print device are outside the control of a watermarking application. 
         [0043]    In these cases a captured image is preferably analyzed for its ability to carry and conceal a watermark, taking into account an anticipated response of an output printer and capture device. 
         [0044]    If a predetermined proportion of image pixels are of a level (e.g., color or grayscale level) that will not be correctly measured or represented by the output device/capture device then image correction or modification is applied. The correction preferably minimizes a visual impact attributable to watermarking, but still allows an embedded watermark to read by ensuring that about 50-85% of the pixels in the image are in an approximately linear section of a print device. (We most prefer that at least 70% of the pixels fall within the approximately linear section of the print device.). 
         [0045]    With reference to  FIG. 1B , we insert image analysis  20  and image modification  22  modules into the workflow of  FIG. 1A . Image analysis  20  determines whether the digital image  10 , if subjected to an anticipated print process (e.g., process  12 ) and eventual image capture (e.g., process  16 ), will provide a suitable environment for digital watermarking. If the digital image is acceptable, flow continues to a digital watermark embedder  11 , where the digital image is embedded with one or more digital watermarks. Otherwise the digital image is modified  22  to provide more favorable image characteristics. A modified digital image is provided to the digital watermark embedder  11 . The embedded image is printed. (While the analysis  20  and modification  22  can be manually preformed, e.g., via photo editing software like Adobe&#39;s PhotoShop, we prefer an automated the process. For example, the analysis  20  and modification  22  can be dedicated software modules and incorporated into an SDK or application program.). 
         [0046]      FIG. 2  illustrates a printer/scanner curve, which models anticipated characteristics of (and/or corruption introduced by) printer  12  and scanner  16 . We use the printer/scanner curve to estimate how a particular digital image will respond when subjected to the printer  12  and eventual scanning  16 . As discussed in Appendix A, a response curve can be generated by printing a range of test patterns on the printer  12  and scanning in the printed test patterns via scanner  16 . The scanned in test patterns are analyzed to model the workflow process (e.g., printer  12  and scanner  16 ). Results of this process are represented in the response curve  FIG. 2  (e.g., in terms of luminance, or defining a range of pixel values that fall within a linear region). In other implementations we represent the workflow response as a data file or equations, etc. 
         [0047]    To illustrate further consider the image shown in  FIG. 3A . After passing through (or analysis relative to) the printer/scanner response curve ( FIG. 2 ), a resulting image will appear washed-out or faded as shown in  FIG. 3C . A luminosity histogram corresponding to  FIG. 3A  is shown in  FIG. 3B . The percentage of pixels in the range from low_lum to high_lum (e.g., defined by the range shown between dashed lines in  FIG. 2 ) is only about 16% in this case. The large number of pixels in the highlight or high luminance areas creates an image which appears washed-out. This image will have a hard time effectively hosting digital watermarking, once it passes through the expected print/scan process, since a high number of its pixels correspond to a non-linear portion of the printer curve ( FIG. 3B ). To compensate for these anticipated problems, tone correction is applied to bring a predetermined number of image pixels into the linear region of the printer/scanner (e.g., between the dashed lines shown in  FIG. 2 ). While we prefer to bring at least 70% of the pixels within this linear region, we can accept a range having a lower boundary of approximately 50% of pixels within the linear region. 
         [0048]    We correct the tone of the image shown in  FIG. 3A  according to a curve shown in  FIG. 4 . The dashed line in  FIG. 4  represents preferred image tone, while the solid line represents the actual image tone. The  FIG. 3A  image is tone corrected, e.g., pixel values are reduced. This process moves the solid line more toward the dashed line in  FIG. 4 . This tone correction process brings a predetermined number of pixels (e.g., 70%) into the desired linear range. For example, a predetermined number of pixels now fall between the dashed lines of  FIG. 2 . The tone correction is preferably applied to the red, green and blue channels (or CYMK channels, etc.). Tone correction can be automated using conventional software such as Adobe&#39;s PhotoShop. Of course, software modules (e.g., C++) can be written to accomplish the same task. 
         [0049]    A resulting image—after tone correction—is shown in  FIG. 5A . We pass the modified  FIG. 5A  image through (or analyze relative to) the printer/scanner response curve ( FIG. 2 ) to determine whether the modified image ( FIG. 5A ) will provide a sufficient watermark hosting environment when subjected to printer  12  and scanner  16 . A resulting image—after passing through the response curve—is shown in  FIG. 5C . The  FIG. 5A  image is deemed to have acceptable characteristics. ( FIG. 5A  luminosity features are shown in  FIG. 5B . A comparison between  FIG. 5B  and  FIG. 3B  helps to illustrate that the overall highlight pixels in  FIG. 5A  have been reduced compared to  FIG. 3A ). We determine that the  FIG. 5C  image is better able to host a watermark—in comparison to FIG.  3 C—and is also more visually pleasing. 
         [0050]    Correction can improve images with larger shadow regions also. The image represented in  FIG. 6A  is passed through (or analyzed relative to) the printer/scanner response curve ( FIG. 2 ), which results in the  FIG. 6C  image. ( FIG. 6A  luminosity is shown in  FIG. 6B .). We determine that we need to move pixels from the low luminance (or shadow region) into a more linear region of the printer/scanner. For this case, a shadow tone correction is performed as shown in  FIG. 7 . The solid line representing image pixels values are changed to move the pixel values toward the dashed line. 
         [0051]    The above two situations (washed out and darker regions) are sometimes found in the same image. For example, consider  FIG. 8 , which includes a combination of darker and lighter areas. Again the  FIG. 2  printer/scanner curve is used for evaluation, and again we determine that correction is needed. This time we apply tone correction shown in  FIG. 9 . This correction moves pixel value from both highlights and shadows toward the preferred dashed line. 
         [0052]      FIG. 10  illustrates a process to help determine whether correction is needed for a particular image. This process can be automated using software and/or hardware. An image is analyzed to determine pixel values. The process determines whether a predetermined number of pixel values fall within a shadow region (e.g., as illustrated, &lt;=15%). The shadow region is preferably identified by a value of low luminance (e.g., see  FIG. 2 ) relative to an expected workflow process. This is the lower level at which the system exhibits non-linear behavior. If not within this limit, shadow tone correction is applied. In a first and preferred implementation, all image pixels are tone corrected. In a second implementation only a subset of image pixels are tone corrected. For example, only those pixels having predetermined pixel value (here, at this stage, a low pixel value) are adjusted. Similarly, it is determined whether a predetermined number of pixels fall within predetermined midtone ranges (e.g., as illustrated, &gt;=70%). These ranges are preferably determined by reference to the response curve of  FIG. 2  (e.g., the area falling within the two dashed lines.) If not, highlight tone correction is applied. As discussed above, we prefer that all image pixels are tone corrected. 
         [0053]    A predetermined number of pixels can be determined according to a number of factors, e.g., visibility constraints, watermark detection rates needed, aesthetic considerations, etc. If modification is preformed, the process can be repeated to ensure desired image characteristics. (Image modification is preferably automatically applied prior to watermark embedding, which results in more consistent watermark detection for otherwise poor images.) 
         [0054]    Returning to  FIG. 1B , an acceptable image  10 —an image including a predetermined number of pixels falling within a reasonable tonal range relative to an expected response of a workflow—passes unchanged to the printer  12 . 
         [0055]    In order to further illustrate the differences between histograms of good ( FIG. 11 ), washed out ( FIG. 12 ) and dark ( FIG. 13 ) tonal range images, cumulative histograms are plotted for a range of these images with error bars to show spread of data. A cumulative histogram is an accumulated sum of a number of pixels in each luminance bin. Ten luminance bins from black to white are on the x axis, with the cumulative percentage of the pixels in the image on the y axis. For example, in  FIG. 13 , between 80% and 100% luminance, &lt;=15% of the pixels are preferred to be in that region. In fact about 70% of the pixels are in that region (1.0-0.3) so a tone correction ( FIG. 7 ) is performed to change the number of pixels in the highlight region to be &lt;=15%. While we have made image changes based on luminance or tonality considerations, we can also apply our techniques to other image criteria. For example, if an image is too busy or noisy (or, alternatively, not busy or noisy enough)—relative to the business or noisiness of a typical image—we can modify the image to better receive digital watermarking in anticipation for the expected printer and scanner (or in anticipation for expected signal processing, like filtering, etc.).  FIGS. 14A and 14B  illustrate a noisy image, which is smoothed ( FIG. 15A and 15B ) prior to watermark embedding and printing. (The term “smoothed” implies a filtering process, like a Gaussian or Weiner filter, or wavelet based filter.). Corresponding histograms are shown in  FIGS. 14C  (noisy image) and  15 C (smoothed image) respectively. 
         [0056]    Another image analysis identifies compression artifacts that are anticipated to be introduced in a later workflow process. We correct an image to compensate for such anticipated artifacts, prior to watermark embedding. 
         [0057]    Another implementation of our invention allows a user to identify an expected workflow process. A library of response curves is queried to identify a corresponding response curve for the identified workflow process. A received digital image is analyzed relative to the corresponding response curve. 
       Conclusion 
       [0058]    The foregoing are just exemplary implementations of the present invention. It will be recognized that there are a great number of variations on these basic themes. The foregoing illustrates but a few applications of the detailed technology. There are many others. 
         [0059]    The section headings in this application are provided merely for the reader&#39;s convenience, and provide no substantive limitations. Of course, the disclosure under one section heading may be readily combined with the disclosure under another section heading. 
         [0060]    To provide a comprehensive disclosure without unduly lengthening this specification, each of the above-mentioned patent documents are hereby incorporated by reference. The particular combinations of elements and features in the above-detailed embodiments are exemplary only; the interchanging and substitution of these teachings with other teachings in this application and the incorporated-by-reference patent documents are expressly contemplated. 
         [0061]    Additional digital watermarking methods and systems are disclosed in Appendix A, which is hereby incorporated by reference. Appendix A provides even further discussion of the methods, systems and apparatus discussed in the body of this application. 
         [0062]    Many of the above-described methods and related functionality can be facilitated with computer executable software stored on computer readable media, such as electronic memory circuits, RAM, ROM, EPROM, flash memory, magnetic media, optical media, magnetic-optical media, memory sticks, hard disks, removable media, etc., etc. Such software may be stored and/or executed on a general-purpose computer, or on a server for distributed use. Also, instead of software, a hardware implementation, or a software-hardware implementation can be used. 
         [0063]    In view of the wide variety of embodiments to which the principles and features discussed above can be applied, it should be apparent that the detailed embodiments are illustrative only and should not be taken as limiting the scope of the invention.