115
`United States Patent
`5,949,055
`[45] Date of Patent:
`Sep. 7, 1999
`Fleet et al.
`
`[11] Patent Number:
`
`US005949055A
`
`[54] AUTOMATIC GEOMETRIC IMAGE
`TRANSFORMATIONS USING EMBEDDED
`SIGNALS
`
`[75]
`
`Inventors: David J. Fleet, Kingston, Canada;
`David J. Heeger, Palo Alto, Calif.;
`Todd A. Cass, San Francisco, Calif.;
`David L. Hecht, Palo Alto, Calif.
`
`[73] Assignee: Xerox Corporation, Stamford, Conn.
`
`[21] Appl. No.: 08/956,839
`
`[22]
`
`Filed:
`
`Oct. 23, 1997
`
`Tint, C0Soecccssnneeceesteeecenneeennneses G06K 7/12
`[SL]
`[52] US. Cle sessessvseisevees 235/469; 235/454; 235/462.41;
`235/494; 382/165
`[58] Field of Search oo... eee 235/469, 462.01,
`235/462.04, 462.07, 462.1, 462.125, 462.127,
`462.41, 454, 470, 487, 494; 382/164, 165,
`309
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4,120,045
`4,964,066
`5,091,966
`5,199,081
`5,278,400
`5,315,098
`5,416,308
`5,629,990
`5,646,388
`
`10/1978 Moellgaard et al... 235/470 X
`10/1990 Yamaneetal. oe 235/454 X
`2/1992 Bloomberg et al.
`oe 382/21
`
`3/1993 Saito et al. 0.0...
`235/380 X
`
`1/1994 Appel......
`w. 235/494
`
`w. 235/494
`5/1994 Tow ....
`
`5/1995 Hood etal.
`.
`«» 235/454
`
`5/1997 Tsuji et al.
`235/454 X
`7/1997 D’Entremontet al... 235/380
`
`FOREIGN PATENT DOCUMENTS
`
`WO 95/14289
`
`5/1995 WIPO.
`
`OTHER PUBLICATIONS
`
`Brassil et al., “Electronic Marking and Identification Tech-
`niques to Discourage Document Copying” in JEEE Journal
`on Selected Areas in Communications, vol. 12, No. 8, Oct.
`1995, pp. 1495-1504.
`
`Cox, Kilian, Leighton and Shamoon,“Secure Spread Spec-
`trum Watermarking for Multimedia,” NEC Research Insti-
`tute Technical Report No. 95-10, 1995. month missing.
`A. Poirson and B. Wandell, “The appearance of colored
`patterns: pattern—color separability”, Journal of the Optical
`Society ofAmerica A, 10:2458—2471, 1993. month missing.
`A. Poirson and B. Wandell, “Pattern—color separable path-
`ways predict sensitivity to single colored patterns”, Vision
`Research, 36:515-526, 1996. month missing.
`X. Zhang and B. Wandell, “A spatial extension of CIELAB
`for digital color image reproduction”, Proceedings of the
`Society of Information Display 96 Digest, pp. 731-734, San
`Diego, 1996. month missing.
`
`Primary Examiner—Michacl G. Lee
`[57]
`ABSTRACT
`
`An acquired (e.g., scanned) image contains an imperceptible
`periodic signal component (e.g., a sinusoid), decoding of
`which can be used to automatically determine a linear
`geometric relationship between the acquired image and the
`original image in which the signal was embedded, without
`having the original image available during the decoding
`process. This known geometric relationship allowsfor linear
`geometric properties of the acquired image, such as align-
`ment and scaling, to be automatically matched with those of
`the original
`image so that
`the acquired image may be
`automatically oriented and scaled to the size of the original
`image. The embedded periodic signals produce a distinct
`pattern of local peak power concentrations in a spatial
`frequency amplitude spectrum of the acquired image. Using
`geometric constraint information about the embeddedsig-
`nals when the signals were originally embedded in the
`image, the locations and spatial frequencies of the signals
`are decoded from the image, providing a linear mapping
`between the peak power concentrations of the acquired and
`original image spatial frequency amplitude spectra. This
`linear mapping can be used to compute the linear geometric
`relationship between the two images.
`In an illustrated
`embodiment, the acquired imagecontainsa set of sinusoidal
`signals that act as a grid. Decoding of the sinusoids does not
`require the original image, only information about the pre-
`determined geometric relationship of the embedded sinuso-
`ids.
`
`18 Claims, 11 Drawing Sheets
`
`188
`
`Signal
`
`Source
`
` Attenvation Image
`
`Production Instructions
`Perceptual Difference
`Measurement
`Instructions
`Decoding instructions
`
`‘Geometric
`Transformation
`Instructions
`
`Program Memory
`System Software,
`Firmware
`‘Attenuation Image
`Production Subroutine
`ColorDifference
`Measurement Subroutine
`Signal Embedding
`Routine
`
`
`
`
`
`
`
`
`Data Memory
`
`Original Image
`
`Data Structure
`
`
`Signal Component
`
`Tnage Data Structure
`Opponent-color image
`Tepresentations
`AE(&y)Color Differences
`
`
`Data Structure
`
`
`Modified Color Image
`Data Structure
`Miscellaneous
`Data
`
`
`
`
`
`
`Sony Exhibit 1047
`Sony Exhibit 1047
`Sony v. MZ Audio
`Sony v. MZ Audio
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`Sheet 1 of 11
`
`5,949,055
`
`210 fo200
`
`
`Add Signal, S'(x,y),
`to Original Color
`
`
`Image, I (x,y)
`
`
`to Produce Modified
`
`
`Color Image, I’(x,y)
`
`
`
`
`
`
`
`
`
`Measure Perceptual
`Differences between
`I (x,y) and Ixy)
`Using Human Perception
`Model; Produce AE(x,y)
`of Perceptual Differences
`
`
`
`
`
`
`
`240
`
`270
`
`
`
`
`
`
`Measured Perceptual
`
`Differences in AE(x,y)
`
`
`Produce new S'*!(x,y) from
`S' (x,y) having
`
`modified signals
`
`in image areas having
`erceptual differences
`
`poeeP
`290
`
`
`Modified Color Image
`with embedded signals
`
`FIG.
`
`|
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`Sheet 2 of 11
`
`5,949,055
`
`
`
`04
`
`jj
`
`I
`
`raveteratetecere’
`RCD
`
`6555oeaCoe
`
`SS
`
`PRRORS
`Watatetatetetetetete:
`PPR
`
`SSSASe
`
`RS
`CeSC5e
`
`SSRIS
`
`retaraeterererererererers
`SSC
`
`O55552
`
`665552oeeoC
`
`
`6,9,6.0.%.%.©.0.6%,
`
`RGSa
`
`SSCS
`B50
`
`EKKOKKKON
`
`BSS508oS
`catatatatererece’
`SS
`
`SSS
`
`BOOQIOY?
`
`FIG. 3
`
`“a
`
`334
`
`340
`
`©.
`
`teteraa”
`
`SKe
`0+.0.09%6.0.9@
`
`©“9>
`
`POO
`
`OT
`
`PRAIA
`
`PY
`
`XAG
`
`eS
`
`OOO
`
`’
`I(x,y)+8'(x,y)
`
`338
`
`FIG. 4
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`Sheet 3 of 11
`
`5,949,055
`
`358
`AEy)
`<thrsh
`
`AE(x,y)
`
`FIG.
`
`5
`
`%
`44 FLL Aa
`&25
`a a a a a
`PLS LSP PLD oS
`ye
`
`\5555082
`~RRS
`
`ZBRR
`
`©SRRKN
`
`SOONG
`SERIES
`B55e5
`AAaaO00,0.@.S552525
`
`eSCHGSORI
`
`ISLS
`
`RKC
`ROHS
`RSLS
`
`%RORIIII)SICHX1.55505
`
`BoM09
`SORRECO
`
`25525529Y5052505oe)e552$6
`
`S(x,y)
`
`FIG. 6
`
`AECx,y)
`<thrsh
`
`356
`
`364
`
`
`
`POIIAI
`
`BASLE05SCSSSSI
`SIC
`vecacenecececarececeedsts
`SSRN
`B5505052525
`arararenecerere,
`SCORHES
`
`SSRSCSCSateres5SSR
`
`SDSKKIIISmretateretatererereree,
`ROKR
`
`CRC82
`RORCRINKK
`DOSSID
`regetetatetetare,
`
`SPIROORIRICY
`RSCIIIS
`RRRKHSRS
`RISO
`SCRND
`statatatatetyteletets
`RAM
`OSORIO
`SOKICICI
`REGS
`oesectntsteestatgesteecey
`
`
`
`55052
`
`Se
`
`BX
`PSS
`
`a 7
`
`PSPS
`
`OSBSR
`S555
`IOQVODOD
`
`Soo Pe LPO
`LSPS A SPL LASS
`SLPS PLE LAE LAP PE LSA SAS ALA SPAS
`SLA LP LAASPFLE POL EOL LA ALE SALA GL
`SL FS PFPA LOS LALA LS
`4
`C44 PLA LE LFA LA
`o %
`LoL FF LLL LL AAS
`S BSS
`<7
`SLA L PLL LLL LLL SAS
`SSFP CFOS SSP LL LE FLSA AS
`SOL PLE LOLA LP LP LS
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`Sheet 4 of 11
`
`5,949,055
`
`404
`
`Original Image
`
`xO400
`
`406
`
`
`
`Convert Original
`
`Image to Opponent-
`
`Colors Representation
`
`
`
`402
`
`412
`
`Opponent-Color
`Image Representation
`
`410
`
`409
`
`450
`
`424
`
`Final Modified Color
`Image with Embedded
`Sinusoidal Signals
`
`430
`
`Sinusoidal Signals
`
`
`
`Add Sinusoids
`to YB band
`
`
`44td
`
`of Original Image
`Interim Modified
`Image with Sinusoids
`
`
`Convert Original,
`Interim Images
`
`to LMS
`
`representations
`
`LMSRepresentations of
`Original, Interim Images
`
`
`S-CIELAB
`
`
`Measure of Per-
`
`
` 416
`
`ceptual Differences
`AE (x,y) mage
`ofPerceptual
`
`Differences
`
`
`Perceptual
`NO
`Differences in AE(x,y)
`> threshold?
`416
`
`
`
`
`
`AE (x,y) Image
`ofPerceptual
`Differences
`420
`
`
`
`Produce
`Attenuation
`
`
`Image
`
`
`418
`
`
`Attenuation Image
`
`Multiply Attenuation
`Image with
`Sinusoidal Signals
`
`FIG. 7
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`Sheet 5 of 11
`
`5,949,055
`
`Original
`Color Image
`
`404
`
`414
`nan
`Interim Modified Color
`Image with Sinusoids
`454
`
`450
`
`e
`
`460
`
`
`
`Produce BW, RG, YB
`Opponent-Color
`
`Separations
`
`456
`
`
`
`Apply Spatial
`(Lowpass) Filters to
`
`
`Opponent Color
`Separations
`
`458
`
`
`Convert to CIE
`Tristimulus XYZ
`
`
`Representation
`
`
`
`
`
`
`Convert to CIELAB;
`Compute AE( x,y)
`between Original,
`Modified Images
`
`
`
`
`> threshold?
`
`
`
`
`Perceptual
`YES
`Differences in AE(x,y)
`
`
`
`Return AE(x,y)
`NO
`to Operation 420,
`FIG 7
`
`424
`
`_
`Final Modified Color
`Image with Embedded
`Sinusoidal Signals
`
`FIG. 8
`
`AE(x,y)From Box 450, FIG. 7
`ye
`
`426
`
`
`Multiply blurred a(x,y)
`
`
`
`Convert AEF (x,y) into
`image of attenuation
`
`image a(x,y) of
`
`
`
`
`factors with S(x,y) to
`attenuation factors
`produce S**(x,y)
`
`
`
`430
`
`
`
`Return S*\(x,y) to
`Operation 406, FIG. 7
`
`Blur a(x,y) with
`lowpass filter
`
`FIG. 9
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`Sheet 6 of 11
`
`5,949,055
`
`482
`
`
`
`
`
`480wo
`
`
`ROS0%,
`SoeSXRESoyS¢%
`III IDON XK
`RRRRRR
`RX
`ORRROOKSEYEX
`
`
`SOOOSS
`ORKCOOKen
`ROR
`
`
`SOROS
`
`
`OS CNOYLEM,;CMMson
`
`
`RRRSRae
`
`
`
`
`
`
`SORSOR xx
`AS,
`
`
`
`
`
`
`
`
`
`
`SOS
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`Sheet 7 of 11
`
`5,949,055
`
`500one
`
`
`
`
`
`Modified
`Image
`
`501
`
`Image
`
`Produce
`Visual
`Rendering
`
`
`
` Acquire
`Digital
`Representation
`
`
`
`
`Acquired eM
`
`
`
`
`
`Geometric Constraints
`ofEmbedded Signals
`
`508
`
`558
`
`
`
`520
`Decode frequencies
`(and phases)
`
`of embeddedsignals
`
`
`Linear Mapping ofLocations of
`Local Peak Power Concentrations
`Between Acquired and Modified Images
`
`
`
`Compute geometric
`960
`
`relationships between
`
`
`acquired, modified
`
`
`images
`
`
`
`Transform geometric
`566
`attributes of acquired
`
`
`image to match
`
`
`geometric attributes of
`modified image
`
`
`570
`
`Geometrically modified
`Acquired Image
`
`FIG. 13
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`Sheet 8 of 11
`
`5,949,055
`
`504
`
`Acquired
`Image
`
`920en
`
`522
`
`
`
`Convert acquired
`image into opponent-color
`
`
`representations
`
`YB band ofacquired image
`
`
`
`
`Compute amplitude
`spectrum of the YB
`color band
`
`
`
`
`Peak enchancement and
`constrast normalization
`
`
`
`
`Determineall local peak
`powerconcentrations in
`YB band of acquired image
`as candidate frequencies
`
`
`
`
`524
`
`525
`
`526
`
`Candidatefrequencies
`
`
`
`Discardall sets of n
`
`
`candidates that violate
`geometric constraints
`
`928
`
`Remaining candidatefrequencies
`
`Geometric
`Constraints
`
`508
`
`
`
`Find best linear mapping
`
`
`
`between locations ofa set
`
`
`of n acquired image local
`peaks andthenvoriginal
`imagelocal peaks
`
`
`
`530
`
`558
`
`Linear Mapping ofLocations of
`Local Peak Power Concentrations
`Between Acquired and Modified Images
`
`FIG. 14
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`Sheet 9 of 11
`
`5,949,055
`
`FIG. 16
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`5,949,055
`
`Sheet 10 of 11
`
`yo
`
`FIG. 18
`
`

`

`U.S. Patent
`
`Sep. 7, 1999
`
`Sheet 11 of 11
`
`5,949,055
`
`100“
`
`110
`
` Program Memory
`System Software,
`Firmware
`
`Attenuation Image
`Production Subroutine
`
`Color Difference
`Measurement Subroutine
`
`Signal Embedding
`Routine
`
`
`
`
`
`
`
`Signal
`Source
`
`Input
`Circuitry
`
`158
`
`156
`
`140
`
`<—_—_——
`
`Storage Medium
`Access Device
`
`150
`
`160
`
`170
`
`Attenuation Image
`Production Instructions
`
`
`
`
`
`
`Perceptual Difference
`Measurement
`Instructions
`
`Decoding Instructions
`Geometric
`
`Transformation
`
`Instructions
`
`
`
`
`Data Memory
`
`
`
`
`
`
`
`
`
`
`
`Original Image
`Data Structure
`
`Signal Component
`Image Data Structure
`Opponent-color image
`representations
`AE(x,y) Color Differences
`Data Structure
`
`Modified Color Image
`Data Structure
`
`Miscellaneous
`Data
`
`162
`
`: 164
`
`166
`168
`
`
`
`FIG. 19
`
`

`

`5,949,055
`
`1
`AUTOMATIC GEOMETRIC IMAGE
`TRANSFORMATIONS USING EMBEDDED
`SIGNALS
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`The present invention is related to the subject matter of a
`concurrently-filed, copending patent application assigned to
`the same assignee as the present application, having an
`application Ser. No. 08/956,638 and entitled “Method For
`Embedding Signals In A Color Image.”
`
`BACKGROUND OF THE INVENTION
`
`The present invention relates generally to a processor-
`based technique in the field of information decoding, and,
`more particularly, to a process for decoding signals embed-
`ded in an acquired image version of an original image.
`Information about geometric properties of the original image
`can be determined from the embedded signals in the
`acquired image thus allowing geometric transformations of
`the acquired imagein order to match geometric properties of
`the original image, without use of the original image in the
`decoding or transformation processes.
`Encoding information in image form to permit its subse-
`quent electronic decoding is a well-known information
`processing technique. For example, bar codes explicitly
`carry encoded information in black and white image form,
`and are typically used in applications where the obvious and
`perceptible presence of the encoded information is intended
`and is not a disadvantage.
`Data glyph technology is a category of embedded
`encoded information that is particularly advantageous for
`use in image applications that require the embeddeddata to
`be robust for decoding purposes yet inconspicuous, or even
`surreptitious, in the resulting image. Data glyph technology
`encodesdigital information in the form of binary 1’s and 0’s
`which are then rendered in the form of distinguishable
`shaped marks such as very small linear marks. Generally,
`each small mark represents a digit of binary data; whether
`the particular digit is a digital 1 or 0 depends on the linear
`orientation of the particular mark. For example,
`in one
`embodiment, marks which are oriented from top left
`to
`bottom right may represent a 0, while marks oriented from
`bottom left to top right may represent a 1. The individual
`marks are of such a size relative to the maximum resolution
`of a black and white printing device as to produce an overall
`visual effect
`to a casual observer of a uniformly gray
`halftone area when a large number of such marks are printed
`together in a black and white image on paper; when incor-
`porated in an image border or graphic, this uniformly gray
`halftone area does not explicitly suggest that embedded data
`is present in the document. A viewer of the image could
`perhaps detect by very close scrutiny that the small dots
`forming the gray halftone area are a series of small marks
`which together bear binary information. The uniformly gray
`halftone area may already be an element of the image,or it
`may be added to the image in the form of a border, a logo,
`or some other image element suitable to the nature of the
`document. For example, U.S. Pat. No. 5,315,098, entitled
`“Methods and Means for Embedding Machine Readable
`Digital Data in Halftone Images,” discloses techniques for
`encoding digital data in the angular orientation of circularly
`asymmetric halftone dot patterns that are written into the
`halftone cells of digital halftone images.
`Research and developmentefforts have also been directed
`to techniques for inserting, or embedding, encoded infor-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`mation in black and white images in a mannerthat hides the
`embedded information in objects or elements in the image,
`without adding additional elements or objects, while not
`causing any degradation or distortion. These techniques may
`be collectively and generally called document or image
`marking. U.S. Pat. No. 5,278,400, assigned to the assignee
`of the present invention and entitled “Multiple Threshold
`Encoding of Machine Readable Code,” discloses a method
`and apparatus for applying coded data to a substrate and
`decoding the data where the data are encoded in uniformly
`sized groups ofpixels, called cells. Each cell is encoded by
`distinctively marking a certain number of the pixels to
`represent the code, without regard to the position in the cell
`of a marked pixel. For example, a cell comprised of six
`pixels each of which may be marked in black or white
`provides for seven possible black-white combinationsof the
`pixels in the cell; a series of three cells provides for 7°
`possible coded combinations, more than enough to encode
`the 256 character ASCII character set with only 18 pixels.
`The characteristics of the marking of each cell are preferably
`the same to facilitate robustness for decoding purposes.
`Another type of image or document marking is known as
`digital watermarking. A successful digital watermarking
`technique simultaneously achieves two purposes: first, the
`technique must produce an embedded signal that is imper-
`ceptible to a human viewer so as not
`to diminish the
`commercial quality and value of the image being water-
`marked. At the same time, the embedded signal must be
`resistant
`to tampering; removal of the embedded signal
`defeats the identification purpose of watermarking, and so a
`successful watermarking technique is typically designed so
`that attempts to remove the embedded signal cause degra-
`dation of the image sufficient to render it commercially less
`valuable or worthless.
`
`text document
`Digital watermarking techniques for
`images may differ from those for use in graphic or scenic
`images. In text document
`images, document marking is
`typically achieved by altering the text formatting in a
`document, or by altering certain characteristics of textual
`elements (e.g., characters), in a mannerthat is both reliably
`able to be decoded and that is largely indiscernible to a
`reader. In graphic or scenic images, document marking may
`be achieved by adding a deterministic signal with a well-
`defined pattern and sequence in areas of the image that are
`determined to be insignificant or inconspicuous, such as by
`toggling the least significantbit.
`Brassil et al., in “Electronic Marking and Identification
`Techniques to Discourage Document Copying” in IEEE
`Journal on Selected Areas in Communications, Vol. 12, No.
`8, October 1995, pp. 1495-1504, disclose three techniques
`for embedding a unique codeword in a text document image
`that enables identification of the sanctioned recipient of the
`document while being largely indiscernible to document
`readers, for the purpose of discouraging unauthorized text
`document distribution. The image coding schemes were
`designed to result in a substantial loss of document presen-
`tation quality if successfully removed. The techniques dis-
`closed include line shift coding, word shift coding and
`feature coding. Use of these techniques in the resulting
`image is typically not noticeable to a viewer of the image,
`and text in the image is not substantively altered.
`PCTInternational Application WO 95/14289 discloses a
`signal encoding technique in which an identification code
`signal is impressed on a carrier to be identified (such as an
`electronic data signal or a physical medium) in a mannerthat
`permits the identification signal later to be discerned and the
`carrier thereby identified. The method and apparatus are
`
`

`

`5,949,055
`
`3
`characterized by robustness despite degradation of the
`encoded carrier, and by holographic permeation of the
`identification signal throughout the carrier. The embedding
`of an imperceptible identification code throughout a source
`signal is achieved by modulating the source signal with a
`small noise signal
`in a coded fashion; bits of a binary
`identification code are referenced, one at a time, to control
`modulation of the source signal with the noise signal. A
`preferred embodimentis disclosed which uses identification
`signals that are global (holographic) and which mimic
`natural noise sources, thereby allowing the maximization of
`identification signal energy.
`In a disclosed preferred
`embodiment, an N-bit identification word is embedded in an
`original image by generating N independent random encod-
`ing images for each bit of the N-bit identification word,
`applying a mid-spatial-frequency filter to each independent
`random encoding image to remove the lower and higher
`frequencies, and adding all of the filtered random images
`together that have a “1” in their corresponding bit value of
`the N-bit identification word;
`the resulting image is the
`composite embedded signal. As disclosed at pg. 11 of the
`application, the composite embedded signal is added to the
`original image using a formula (Equations 2 and 3) based on
`the square root of the innate brightness value of a pixel.
`Varying certain empirical parameters in the formula allows
`for visual experimentation in adding the composite identi-
`fication signal to the original image to achieve a resulting
`marked image, which includes the composite identification
`signal as added noise, that is acceptably close to the original
`image in an aesthetic sense. The disclosure notes that the use
`of a noise, or random, source for the identification signal is
`optional, and that a variety of other signal sources can be
`used, depending on application-dependent constraints (e.g.,
`the threshold at which the encoded identification signal
`becomes perceptible.) In many instances, the level of the
`embeddedidentification signal is low enough that the iden-
`tification signal need not have a random aspect; it is imper-
`ceptible regardless of its nature. It is further pointed out,
`however, that a pseudo random source is usually desired
`because it is more likely to provide an identification signal
`that is both detectable and imperceptible in a given context.
`Cox, Kilian, Leighton and Shamoon, in NEC Research
`Institute Technical Report No. 95-10 entitled “Secure Spread
`Spectrum Watermarking for Multimedia,” disclose a fre-
`quency domain digital watermarking technique for use in
`audio, image, video and multimedia data which views the
`frequency domain of the data (image or sound) signal to be
`watermarked as
`a communication channel, and
`correspondingly, views the watermark as a signal that is
`transmitted through it. Attacks and unintentional signal
`distortions are thus treated as noise to which the immersed
`signal must be immune. To avoid perceptual degradation of
`the signal, Cox et. al propose to insert the watermark into the
`spectral components of the data using techniques analogous
`to spread spectrum communications, hiding a narrow band
`signal in a wideband channelthatis the data. Their technique
`proposesto spread the watermark over very manyfrequency
`bins so that the energy in any one bin is very small and
`certainly undetectable, on the premise that a watermark that
`is well placed in the frequency domain of an image or of a
`sound track will be practically impossible to see or hear if
`the energy in the watermark is sufficiently small in any
`single frequency coefficient. At the same time, they propose
`that the watermark be placed in perceptually significant
`components of a signalif it is to be robust to commonsignal
`distortions and malicious attack, on the premise that signifi-
`cant tampering with these perceptually significant frequen-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`cies will destroy the fidelity of the original signal well before
`the watermark.In particular with respect to watermarking an
`NxN black and white image, the technique first computes
`the NxN DCT of the image to be watermarked,;
`then a
`perceptual mask is computed that highlights the perceptually
`significant regions in the spectrum that can support the
`watermark without affecting perceptual fidelity. Each coef-
`ficient in the frequency domain has a perceptual capacity
`defined as a quantity of additional information that can be
`added without any (or with minimal) impact to the percep-
`tual fidelity of the data. The watermark is placed into the n
`highest magnitude coefficients of the transform matrix
`excluding the DC component. For most images, these coef-
`ficients will be the ones corresponding to the low frequen-
`cies. In a disclosed example, the 1000 largest coefficients of
`the DCT (excluding the DC term) were used. The precise
`magnitude of the added watermark signal is controlled by
`one or more scaling parameters that appear to be empirically
`determined. Coxet. al note that to determine the perceptual
`capacity of each frequency, one can use models for the
`appropriate perceptual system or simple experimentation,
`and that further refinement of the method would identify the
`perceptually significant components based on an analysis of
`the image and the human perceptual system. Coxet. al also
`provide what appears to be a detailed survey of previous
`work in digital watermarking.
`Manyof the existing techniques for embedding informa-
`tion in images appear to operate in the black and white
`image domain, and so do not explicitly address how to
`embed a signal in a color image that is imperceptible to a
`human viewer and that does not distort the quality of the
`image. Digital watermarking techniques, even those that
`may apply to color images, are typically designed to be
`irreversible; they produce a tamper-proof embedded signal
`which cannot be removed without distorting the information
`in the image; the watermarked image must remain water-
`marked for all subsequent uses. Moreover, the detection of
`an embedded identification signal in a watermarked image
`typically requires the use of the original image, which is
`typically maintained in a secure location for such future use
`as needed. While these characteristics of digital watermark-
`ing are useful features for image authentication and identi-
`fication purposes,
`they may be limitations for other pur-
`poses. There are a variety of other image processing
`applications, especially in the burgeoning field of color
`image processing, that could make use of a technique for
`modifying a color image to have an imperceptible signal
`added thereto, where the modified color image doesnot have
`all of the aforementioned limitations of a watermarked
`image. The present invention addresses this need.
`SUMMARY OF THE INVENTION
`
`The steadily rising use of color images in all types of
`commercial and aesthetic applications suggests that many of
`the techniques that have been developed for embedding
`information in black and white images need to be extended
`to the color domain. The present invention is premised on
`the observation that modifying a color image by adding
`signals that do not unacceptably distort or degrade the image
`to a humanviewer presents a human perception problem that
`is different from that associated with black and white
`images. The mere extension of existing techniques in the
`black and white image domain using empirical or heuristic
`approachesto determine whether an added signal is humanly
`perceptible is inadequate to embedsignals in color images
`that do not unacceptably distort or degrade the image.
`Moreover, image artifacts that appear in a color image as a
`
`

`

`5,949,055
`
`5
`result of adding a signal using an inadequate method are
`likely to be attributed to the hardware device that produced
`the image; if the quality of the color image is aesthetically
`unacceptable, the hardware device or the application that
`produced these artifacts will simply not be used.
`A technique for embedding data in images is premised on
`the discovery that adding signals to a color image that do not
`unacceptably distort or degrade the image can only be
`predictably and reliably accomplished by using a sophisti-
`cated model of human perception that is able to quantita-
`tively determine the magnitude of the perceptual differences
`between an original image and a version of the image with
`the embedded signals. The technique uses a quantitative
`model of human perception to attenuate the power
`(amplitude)of the added signal in local regions of the color
`image where the model indicates that the perceptual differ-
`ence between an original color and the modified color
`produced with the added signalis too high, toward the goal
`of producing a version of an original color image having an
`added signal that is substantially imperceptible to human
`viewers of the image. The quantitative model of human
`perception controls the perceptibility of the embedded signal
`by ensuring that it is below a perceptual threshold.
`The technique of an illustrated embodimentaddsa pattern
`of periodic signals to a color image, and in particular, adds
`a pattern of amplitude-modulated sinusoidal signals to the
`color image. A comparing operation automatically deter-
`mines local areas in the modified color image where the
`amplitude of the embedded information is too high, and is
`thus perceptible. The perceptible signals are then iteratively
`attenuated in those identified local areas of the modified
`image. In one aspect of the illustrated embodiment,
`the
`sinusoidal signals are added to the yellow-blue opponent-
`color band of the color image, at spatial frequencies where
`most color images have relatively little power, and where
`humans have the least sensitivity. The added amplitude-
`modulated sinusoidal signals can be decoded (located in a
`modified image) because they form a specific pattern of peak
`power concentrations in the frequency domain. The manner
`of adding the signals results in particular geometric rela-
`tionships occurring between the spatial frequencies that are
`unlikely to occur by chance in natural or computer-
`generated synthetic images. The embedding technique takes
`advantage of human perception: the spatial frequencies of
`the embeddedsinusoidal signals are well within the range of
`frequencies to which humansare normally quite sensitive in
`the luminance (black-white) vision band, but this sensitivity
`does not extend to the color vision bands. Thus, while
`sinusoidal signals at relative high spatial frequencies are
`added to the modified color image in the embodimentof the
`invention described below, signals can be added at lower
`spatial frequencies if a particular application, a specific
`decoding domain, or a specific device requires it.
`An image with the embedded sinusoidal signal may be
`useful in a variety of applications according to the present
`invention. A set of sinusoids forms a grid when embedded in
`an original
`image. After the decoding operation of the
`present invention has extracted the spatial frequencies of the
`embedded sinusoids, a mapping is computed between the
`acquired (e.g., scanned) modified image and the sinusoidal
`grid image that was embedded in the original image. This
`mapping then allows geometric transformations to be per-
`formed on the acquired image to match the geometric
`properties of the acquired image to the geometric properties
`of the original image. For example, the acquired image can
`be automatically aligned and scaled to that of the original
`image, if the acquired image has becomerotated, skewed,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`reduced or enlarged during previous manipulations. Thus,
`images containing the added sinusoidal signals do not have
`to be perfectly aligned when scanned, nor manually scaled
`or rotated after scanning. In addition, the sinusoidal grid can
`function as a reference point with respect to which other
`embedded information can be located with precision.
`Moreover, a combination of embedded sinusoidal signals
`can be chosen such that the total embedded signal has a
`period greater than or equal to the imagefield so that, during
`a decoding operation, each position in the acquired image is
`uniquely associated with a unique position in the embedded
`signal image.
`A significant advantage of the technique of the signal
`decoding processis that the process of locating the sinusoi-
`dal signal image that is embedded in an acquired image(i.e.,
`the decoding process) does not require use of the original,
`unmodified image. This characteristic provides anyone with
`the ability to use the embedded information.
`Therefore, in accordance with one aspect of the present
`invention,
`there is provided a method for operating a
`machine to automatically transform geometric properties of
`an acquired image version of an original image to match
`geometric properties of the original
`image. The method
`comprises obtaining an acquired imagedata structure defin-
`ing an acquired image; the acquired image is a version of an
`original
`image and additionally has embedded signals
`therein not included in the original image. The embedded
`signals have predetermined geometric relationships with
`respect to each other. The processor further obtains geomet-
`ric constraint data indicating expected geometric relation-
`ships about the embedded signals in the acquired image.
`Then, the geometric relationships of the embeddedsignals in
`the acquired image are determined. The processor then
`computes geometric differences between the acquired image
`and the original image using the geometric relationships of
`the embedded signals in the acquired image and using the
`geometric constraint data indicating the expected geometric
`relationships of the embedded signals. Using these geomet-
`ric differences, geometric properties of the acquired image
`are transformed to match the geometric properties of the
`original image.
`In accordance with still another aspect of the invention, a
`method for operating a processor-controlled machine is
`provided for decoding a set of n periodic signals embedded
`in an image. The method comprises obtaining an image data
`structure defining an image including a set of n periodic
`signals embedded therein. The set of n periodic signals have
`geometric relationships with respect
`to each other. The
`method further includes obtaining geometric constraint data
`indicating expected geometric relationships aboutthe set of
`n periodic signals. Then, a plurality of local peak power
`concentrations in the two-dimensional