Patent Publication Number: US-6711303-B1

Title: Method and computer program for detecting rotation and magnification of images

Description:
FIELD OF THE INVENTION 
     The invention relates generally to the field of image processing, and in particular to methods for detecting when an image has been rotated or resized (magnified). 
     BACKGROUND OF THE INVENTION 
     U.S. Pat. No. 5,835,639 issued Nov. 10, 1998 to Honsinger et al., entitled “Method For Detecting Rotation And Magnification In Images” describes a method for embedding two identical carriers in an image in order to track rotation and magnification changes. The method is based on the fact that the autocorrelation of the image will contain the cross-correlation of the two carriers and the cross-correlation will exhibit two delta functions whose distance apart will be proportional to magnification and whose angle will be maintained under no rotation or will be rotated in the same amount as the rotation of the original image. Thus, by identifying the location (separation and rotation) of the two delta functions one can determine the amount of rotation and magnification that an image has undergone. In images that contain a large amount of pronounced linear and angular features, these features tend to cause the autocorrelation of the image to exhibit a number of features that mask the delta functions, thereby making the detection of the delta functions difficult. 
     There is a need therefore for an improved method of detecting angular rotation and magnification of the type disclosed in the above referenced patent that avoids this problem. 
     SUMMARY OF THE INVENTION 
     The present invention is directed to overcoming one or more of the problems set forth above. Briefly summarized, according to one aspect of the present invention an improved method and computer program product for detecting an amount of rotation or magnification in a modified image, of the type including the steps of: 
     a) embedding a marker image having a pair of identical features separated by a distance d and oriented at an angle α in an original image to produce a marked image, the marked image having been rotated and/or magnified to produce the modified image; 
     b) performing an autocorrelation on the modified image to produce a pair of autocorrelation peaks corresponding to the location of the features of the marker image in the modified image; and 
     c) comparing the separation d and orientation α of the autocorrelation peaks with the separation d and orientation α of the features in the marker image to determine the amount of rotation and magnification in the modified image, wherein the improvement comprises the step of: 
     d) preprocessing the modified image to have a constant standard deviation over all local regions in the image. 
     The present invention has the advantage of being able to more easily detect the autocorrelation peaks in an image having large amounts of linear and angular detail. 
     These and other aspects, objects, features and advantages of the present invention will be more clearly understood and appreciated from a review of the following detailed description of the preferred embodiments and appended claims, and by reference to the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic diagram showing the prior art method of adding of a marker image to an original image; 
     FIG. 2 is a flow chart illustrating one prior art method of generating a marker image; 
     FIG. 3 is a schematic diagram showing a prior art rotation and magnification of the marked image to produce a modified image; 
     FIG. 4 is a schematic diagram illustrating the prior art method of recovery of the separation and orientation of the features in a marker image in the modified image; 
     FIG. 5 is a flow chart showing the determination of the rotation and magnification of the modified image and the recovery of the original image size and orientation according to the present invention; 
     FIG. 6 is a flow chart showing the steps employed in preprocessing the image according to the present invention; and 
     FIGS. 7 and 8 are diagrams useful in describing a preferred filter for filtering the autocorrelation according to a preferred method of practicing the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Referring to FIGS. 1 and 2, a digital image  10  is prepared by adding  12  a marker image  11  having a pair of identical features  14  and  16  to produce a combined image  18 . The identical features  14  and  16  in the marker image  11  are oriented a distance “d” from each other and at an angle “α” with respect to the vertical in image  10 . Referring to FIG. 2, prior to adding the marker image  11  to the image  10 , the features  14  and  16  in the marker image  11  are convolved  20  with a carrier image  22  and magnified (or minified) such that their amplitude is low relative to the amplitude of the original image so that the marker image is not visible in the combined image  18 . In one example, the marker image features  14  and  16  are delta functions (one pixel at maximum amplitude) convolved with a random carrier signal  22  having a uniform frequency amplitude and random phase. In an alternative example, the marker image may contain information such as digital code (such as  0 &#39;s and  1 &#39;s ordered in such a way as to effect a message) or text image such as a copyright notice. 
     The identical digital code or text images are convolved with the carrier signal  22  as described above and then added to the image  10 . Referring to FIG. 3, the angular orientation and/or magnification of the combined image  18  is changed, for example in an optical or digital printing or copy process to produce a modified combined image  24 . 
     Referring to FIGS. 4 and 5, to determine if and how much the modified combined image  24  has been rotated and magnified, the modified combined image  24  is first preprocessed  25  to have a desired constant local standard deviation. Referring to FIG. 6, this may be achieved by specifying a desired standard deviation σ D  that is chosen to be relatively low, but not too low (preferably 0.1 to 0.3) and a surrounding area A (preferably over 3×3 to 5×5 pixel regions) for the normalization to be performed  38 . For each pixel within the modified image, a local standard deviation σ A  is calculated  40 . The local standard deviation is tested  42  and if the calculated standard deviation is less than the desired standard deviation σ D , it is replaced  44  with a random number generated from a process  46  having the same standard deviation as the desired standard deviation. The pixel value is then multiplied  48  by the ratio of the desired standard deviation and the local standard deviation to form a modified pixel value. Finally, all of the pixel values in the modified image are replaced  50  with the modified pixel values. The resulting image will have the desired constant local standard deviation σ D . Since the preprocessed image has a constant local standard deviation, the effect on the autocorellation due to the high contrast of the edges and angular features of the image is substantially reduced. 
     Next, the preprocessed image is autocorrelated  26 . The autocorrelation will result in two autocorrelation peaks  28  and  30  corresponding to the centers of the features in the marker image  11 . Preferably the autocorrelation is performed in the frequency domain using Fourier transform techniques. The autocorrelation is simply the inverse Fourier transform of the magnitude of the forward Fourier transform. The two autocorrelation peaks may, optionally, be further emphasized during the processes of autocorrelation in the frequency domain by weighting the Fourier transform coefficients by the frequency domain representation of a Wiener filter  32  that emphasizes isolated peaks and suppresses smooth regions. An example of a Wiener filter useful for this purpose is illustrated in FIGS. 7 and 8. FIG. 7 is a two dimensional frequency plot having frequency axes f x  and f y  from zero to the Nyquist frequency N x , N y . The filter has the effect of setting to zero the Fourier transform coefficients for frequencies in a region  52  having a radius R centered about zero frequency. For regions outside this radius, the weighting function is a monotonically increasing function as shown by line  54  in FIG.  8 . The Wiener filter can be expressed as follows: 
     For 
     
       
         ( f   x   2   +f   y   2 ) 0.5   &gt;Rw ( f   x   ,f   y )= a ( f   x   2   +f   y   2 ) β   (1) 
       
     
     and for 
     
       
         ( f   x   2   +f   y   2 ) 0.5   ≦Rw ( f   x   ,f   y )=0 
       
     
     where α is an arbitrary constant and β ranges from 0.50 to 1.00 in a preferred embodiment. Optionally, a linear ramp may be applied to smooth the transition region at the radius R. 
     The autocorrelation peak positions  28  and  30  of the modified image may be measured  34  to obtain the modified distance “d′” and the modified angle “α′” measured with respect to the vertical. If it is of interest to measure rotations greater than 180 degrees, the amplitude of the autocorrelation peaks should be measured. The modified distance “d′” and the modified angle “α′” may be used to calculate  36  the magnification and rotation that the image has undergone by use of the following formulae: 
     
       
         Magnification  M=d′/d ×100 percent.  (2) 
       
     
     If the autocorrelation peak of the upper left hand corner is stronger than the lower right: 
     
       
         Rotation angle Ω=α′−α  (3) 
       
     
     If the autocorrelation peak of the lower right hand corner is stronger than the upper left: 
     
       
         Rotation angle Ω=α′−α+180 degrees  (4) 
       
     
     The present invention is preferably practiced in an image processing system including a source of digital images, such as a scanner, a computer programmed to process digital images, and an output device such as a thermal or inkjet printer. The method of the present invention may be sold as a computer program product including a computer readable storage medium bearing computer code for implementing the steps of the invention. Computer readable storage medium may include, for example: magnetic storage media such as a magnetic disc (e.g. a floppy disc) or magnetic tape; optical storage media such as optical disc or optical tape; bar code; solid state electronic storage devices such as random access memory (RAM)or read only memory (ROM); or any other physical device or medium employed to store a computer program. 
     Appendix A contains a computer program written in the C++ language for extracting an embedded message from a digital image according to the present invention. 
     The invention has been described with reference to a preferred embodiment. However, it will be appreciated that variations and modifications can be effected by a person of ordinary skill in the art without departing from the scope of the invention. 
     PARTS LIST 
       10  digital image 
       11  marker image 
       12  adding step 
       14  identical feature 
       16  identical feature 
       18  combined image 
       20  convolution step 
       22  carrier image 
       24  modified combined image 
       25  preprocessing step 
       26  autocorrelation step 
       28  autocorrelation peak 
       30  autocorrelation peak 
       32  Wiener filter step 
       34  measure autocorrelation peak position step 
       36  calculate angle step 
       38  specifying step 
       40  calculating step 
       42  testing step 
       44  replacing step 
       46  random number generating process 
       48  multiplication step 
       50  replace pixels step