115
`United States Patent
`6,141,441
`[11] Patent Number:
`[45] Date of Patent:
`Oct. 31, 2000
`Casset al.
`
`US006141441A
`
`[54] DECODING DATA FROM PATTERNED
`COLOR MODULATED IMAGE REGIONSIN
`A COLOR IMAGE
`
`[75]
`
`Inventors: Todd A. Cass, San Francisco, Calif.;
`Xin Tong, Jacksonville, Fla.
`
`[73] Assignee: Xerox Corporation, Stamford, Conn.
`
`[21] Appl. No.: 09/162,257
`
`[22]
`
`Filed:
`
`Sep. 28, 1998
`
`Tite C0 one cece eccesnneeeseenteeeccnneeennneses G06K 9/00
`PSL]
`[52] U.S. CM. oes 382/166; 382/232; 235/494
`[58] Field of Search wees 382/166, 167,
`382/232, 183, 233; 235/469, 494
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`4/1984 Sanford ..cccscccssesseeees 235/465
`4,443,694
`6/1993 Hecht..
`w. 235/494
`5,221,833
`9/1993 Zhang .
`.. 235/454
`5,245,165
`1/1994 Appel ..
`w. 235/494
`5,278,400
`5/1994 Tow ....
`w.. 235/494
`5,315,098
`11/1994 Shamir....
`... 235/469
`5,369,261
`
`.
`4/1997 Chou et al.
`235/462
`5,619,026
`11/1997 Cass etal. ......
`.. 382/100
`5,684,885
`
`6/2000 Kaufman et al. oe 235/494
`6,070,805
`FOREIGN PATENT DOCUMENTS
`
`63-254586
`WO 95/14289
`
`Japan .
`10/1988
`5/1995 WIPO.
`
`OTHER PUBLICATIONS
`
`I. J.; Kilian, J; Leighton, T.; Shamoon, T. Secure
`Cox,
`Spread Spectrum Watermarking for Multimedia. NEC
`Research Institute, Technical Repot 95-10, pp. 1-33.
`Antognini, T.; Antognini, W. A Vlexibly Configurable 2D
`Bar Code. pp. 1-26. http://www.paperdisk.com/ibippa-
`pr.htm.
`Aurora bar code technolgics ltd. Two-Dimensional Bar
`Codes. The Biggest Advance in Bar Code Technology in
`Recent Years. Code Facts. pp. 1-2. http://www.dimension-
`—x.com/cf—2d.htm.
`
`Johnston, R.B.; Yap, A. K. C. ‘lwo Dimensional Bar Code as
`a Medium for Electronic Data Interchange. Two Dimen-
`sional Bar Code. pp. 1-10. http://www.bs.monash.edu.au/
`staff/johno/BARCOPAW.html.
`Nelson, B. Secret Codes? Automatic ILD. News . pp. 1-2.
`hitp://Awww.auloidnews.com/technologies/concepts/secre-
`t.htm.
`
`The ‘Big 3’ Dominate 2D Symboloty Use. Automatic LD.
`News. pp. 1-2. http:/$www.autoidnews.com/technologies/
`concepts/big3.htm.
`
`Primary Examiner—Amelia Au
`Assistant Examiner—Jingge Wu
`
`[57]
`
`ABSTRACT
`
`A technique for decoding message data that has been
`encoded into a printed color image locates small
`image
`regions called signal cells that carry the encoded message.
`Each signal cell is composed of a spatial pattern of colored
`subregions that collectively have an overall average color.
`The colors of the subregions are defined as changes
`(modulations) to the average color in one or more directions
`in a multi-dimensional color spacc. The decoding technique
`uses a set of valid signal blocks, each of which is a unique
`pattern of color modulated subregions. There is a valid
`signal block for each valid message value defined in the
`coding scheme. The decoding operation first locates the
`positions of the signal cells in the acquired image and then
`subtracts the local average color of each signal cell from the
`cell to produce a received signal block. Then the decoding
`operation determines which valid signal block each received
`signal block is by comparing each valid signal block to a
`received signal block. One implementation of the decoding
`technique decodessignal cells that have been arrangedin the
`acquired image in a 2D array by synchronizing an imaginary
`grid-like structure with the most likely position of all of the
`signal cells. In one embodiment, a color space direction is
`selected for the color modulations that results in the differ-
`
`ently colored subregionsof a signal cell being substantially
`imperceptible to a human viewer, thus making the pattern
`that carries the message substantially imperceptible in an
`encoded image.
`
`13 Claims, 22 Drawing Sheets
`
`‘Test each max correlation image
`location on a grid spaced by
`
`ignal cell size for a hypothetical
`id
`phase h:
`i
`correlation
`m5
`compute a test value from all
`
`locations
`Repeat test 860forhypothetical
`fstid phases having an offset
`at each pointin a Kx Kregion
`
`in the max correlation image
`
`
`Select signa! grid phase
`associated with test values thal
`satisfy expected testcriterion
`
`Signalgridphaseshif, signalcell locations
`
`Sony Exhibit 1050
`Sony Exhibit 1050
`Sony v. MZ Audio
`Sony v. MZ Audio
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 1 of 22
`
`6,141,441
`
`
`
`
`
`Modulate
`
`Message
`colors in
`£
`arranged
`
`
`Signal Blocks
`
`according to
`
`respective colors
`
`
`80
`Image, E,
`wi ed
`encode
`message
`
`
`
`mM— kK —— —— K —>>
`
`33
`
`
`
`
`32 be a
`
`
`
`
`
`
`
`
`m = “QO”?
`
`m = “1”
`
`signal block has mean color 0
`
`signal block has mean color 0
`
`FIG. 2
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 2 of 22
`
`6,141,441
`
`Receive message,
`m; arrange in 2D
`array having size
`nsions of
`dime
`carrier image
`I
`
`210
`
`200
`
`>
`
`Define at least two K x K
`signal blocks, each having an
`overal 0 mean color difference
`and each composed of color
`difference quantities expressed
`as a color space direction,6 ;
`arrange color difference
`quantities in each signal block
`in a spatial pattern unique
`to all other signal blocks
`
`For each messagedata item in
`m, select the signal block
`representing its value to encode
`3
`spatially arrange
`message m
`1 blocks in same order
`signa
`as message data items are
`arranged in 2D array to
`produce message image, M@
`
`Message image, M@
`
`FIG. 3
`
`_©=°oS
`
`oO
`
`oS
`
`~
`
`_
`
`555050)
`
`CToreeA?coneceeIRRR
`
`ROEOIC)states:
`reretete!Wetetete!RSC56055.
`
`
`BeeKSsees
`OOOOLOCKo1BlBSe
`OO)OeCOOSe
`VeeaeOFaaFatSOPROM00Se0aratarel
`tekOTOOOO
`Wetetere
`
`Message Array
`
`00)
`
`50250899RgC52
`
`Message Image, M
`
`FIG. 4
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 3 of 22
`
`6,141,441
`
`300LO
`Message image, M
`
`31
`(from FIG 3, block 280)
`
`For eachsignal
`block in M, determinecolor
`
`
` Combine message image M
`space direction 6 , for color, ¢,
`
`additively to I: Pair animage
`in the paired im:
`ni,
`such thatmeanpixel color
`signal bloLin Movsaage
`region in carrier imageIwith a
`
`
`and sub-block color.
`c:L438, are imperveeptible
`
`to human viewer
`
`80
`Imagewith encoded message, Ip
`
`FIG. 5
`
`HYE—2(lim
`
`
`MM te |aa
`
`Carrier Image, I’
`
`46
`
`FIG. 6
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 4 of 22
`
`6,141,441
`
`
`
`NoooKSCoR25Sele
`
`KXIOC
`A*SSBC
`QlKKK?SO55509
`
`4
`
`
`
`
`
`
`
`ll
`
`
`
`
`
`
`49
`
`
`a
`
`>CCCEECCHay
`
`FIG. 7
`
`44
`
`FIG. 8
`
`TENS
`feYce;
`
`eed
`
`mean (perceived) color c,
`
`85
`
`Li
`
`NoNEONOre
`
`_ENSNa
`=
`
`FIG. 9
`
`mean (perceived) color c,
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 5 of 22
`
`6,141,441
`
` FIG. 10
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 6 of 22
`
`6,141,441
`
`signal block has mean color
`!
`
`E
`
`>
`
`0
`
`signal block has mean color
`aa
`iM3
`
`0
`
`=
`
`Li:
`K color cells
`
`FIG. 13
`
`21
`
`001010011
`
`| Lo
`
`~)rs
`
`
`
`
`

`

`U.S. Patent
`
`6,141,441
`
`Oct. 31, 2000
`
`Sheet 7 of 22
`
`
`
` s,=[-1 +1]}' <5,
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 8 of 22
`
`6,141,441
`
`+— kK ——>
`
`48
`
`Kk
`
`‘LI
`
`614 42)
`614
`
`or
`
`FIG. 18
`
`
`
`
`s,=[-1 +1]'<—~>5,
`
`
`
`612
`
`614
`
`Do
`
`P;
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 9 of 22
`
`6,141,441
`
`NCNULi
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 10 of 22
`
`6,141,441
`
`653 va650
`
`+8
`
`654 a652
`
`662
`
`+6
`
` |
`
`m= “Q”
`
`}
`
`I
`
`m= 64479
`
`I
`
`signal block has mean color @
`
`signal block has mean color 0
`
`FIG. 27
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 11 of 22
`
`6,141,441
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 12 of 22
`
`6,141,441
`
`<—> 55
`
`659
`
`Ss
`
`t 1] 1 [ 2
`
`Hie
`
`Hh
`
`FIG. 33
`
`FIG
`
`. 34
`
`2|e
`
`
`
`
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 13 of 22
`
`6,141,441
`
`
`
`
`
`Sy =[+1 +1 +1 +1] <> = CDF +CVGT+OGr+ ong;
`s,=[+1 +1 41 -I]' <> P= GDB+GDG,+4GDG2+ CDE;
`
`
`s)=[+l +1 -1 +1}
`Sig [-1 +1 -1 +1]
`
`
`s,=[+1 +1 -1 -I]
`
`
`
`
` e
`
`
`S;4=[-1 -1 -1 +1]!
`85=[-1 -1 -1
`-1]'
`
` +1 -1]!
`
`
`FIG. 36
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 14 of 22
`
`6,141,441
`
`FIG. 37
`
`FIG. 38
`
`
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 15 of 22
`
`6,141,441
`
`
`
`
`
`
`
`
`FIG. 39
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 16 of 22
`
`6,141,441
`
`signal block has mean color 0
`
`m
`
`signal block has mean color0
`
`“1”
`
`FIG. 40
`
`
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 17 of 22
`
`6,141,441
`
`
`
`Message Data
`Item Value
`
`Input Reference
`Color, ¢
`
`Lo400
`
`410
`
`
`
`
`Compute
`Selects. b.
`color space
`modulation
`
`
`
`directionand
`pattern to
`
`
`
`represent
`amplitude
`
`
`
`value
`of color change
`
`
`Signal block
`amplitude,
`modulation patterns
`color space direction
`
`.
`(ergnlationpattems)
`ke—-—--=~—pass.
`
`430
`
`Signal block
`modulation
`patterns
`
`
`
`
`
`Combineto
`
`
`produce signal block:
`5¢6- modulation pattern
`Add Reference Color:
`ctée Se modulation pattern
`
`
`
`Output signal block
`
`FIG. 42
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 18 of 22
`
`6,141,441
`
`From digital image capture device
`
`Yo
`
`ee yom
`Acquired Color Image,I,
`
`Alignment and synchron-
`ization of signal grid;
`Removeaverage color
`
`820
`
`890
`
`decode message
`
`Correlation between signal set
`and signalcells;
`
`fn“A
`
`Recovered Message, M
`
`FIG. 43
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 19 of 22
`
`6,141,441
`
`RRR
`
`
`
`
`FIG. 44
`
`FIG. 45
`
`

`

`Oct. 31, 2000
`
`Sheet 20 of 22
`
`Compute a correlation image
`indicating the correlation of
`each unique signal block with
`each acquired image location
`
`U.S. Patent 852
`
`854
`
`860
`
`864
`
`868
`
`Create a max correlation image
`indicating the maximum value
`of all correlation imagesat
`every location in the acquired
`image
`
`Test each max correlation image
`location on a grid spaced by
`signalcell size for a hypothetical
`signal grid phase having a given
`offset from an initial max
`correlation image location;
`compute a test value from all
`locations
`
`Repeattest 860 for hypothetical
`grid phases having an offset
`at each point in a K x K region
`in the max correlation image
`
`Select signal grid phase
`associated with test values that
`satisfy expected test criterion
`
`6,141,441
`
`Lo
`
`842
`
`Signal gridphaseshift, signal cell locations
`
`FIG. 46
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 21 of 22
`
`6,141,441
`
`100
`
`>
`
`Signal
`Source
`
`158
`
`156
`
`
`
`Input
`Circuitry
`
`140
`
`Processor ~<
`
`150
`
`Storage Medium
`
`Access Device
`
`160
`
`162
`
`170
`
`
`164 i duction Instructions
`166 i
`
`
`Instructions
`168 i
`
`
`Message Image Pro-
`
`Encoded Image Pro-
`duction Instructions
`
`Decoding
`
`Color Modulation
`Instructions
`
`
`
`
`
`
`
`
`
`Program Memory
`
`
`192
`
`Firmware
`.
`Define Signal Blocks
`Signal Block Selection,
`Arrangement Subroutine
`
`Color Modulation
`
`Message Image
`Production Routine
`
`240
`
`|
`
`280
`320
`
`Encoded Image
`Production Routine
`Signal Grid Synchroniza
`
`
`850
`
`
`0
`
`
`
`
`
`114
`
`
`tion Subroutine
`
`Decoding Routine
`
`Data Memory
`
`Original Image
`Data Structure
`
`Message Image
`Data Structure
`
`Signal Block
`Data Structures
`
`Input Message
`Data Structure
`
`Encoded Color Image
`Data Structure
`Upsampled Carrier Image
`Data Structure
`
`Basis Function Data
`
`Signal Cell Location Data
`Recovered Message
`
`Data Structure
`
`116
`
`842
`
`U
`
`898
`122
`
`FIG. 47
`
`

`

`U.S. Patent
`
`Oct. 31, 2000
`
`Sheet 22 of 22
`
`6,141,441
`
`\
`
`
`
`ay
`
`346
`
`VeaCOaciacas
`
`Mee0S00),
`
`RNROROROE
`NowaA
`ROROR
`PKK
`OQ.
`rNJ
`
`KNOS
`
`\F|D
`(|
`ll
`
`4
`
`344
`
`
`
`
`
`aA:
`
`/
`
`VArary‘a
`oYZNOO
`
`
`
`OOOOROROM|
`
` YYNONON\esOO),|\SCNNWW,WW</O\eN
`BOBBLE
`BSOSOSOSONON
`apanSaSa
`
`
`
`348
`
`FIG. 48
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`6,141,441
`
`1
`DECODING DATA FROM PATTERNED
`COLOR MODULATED IMAGE REGIONS IN
`A COLOR IMAGE
`
`CROSS-REFERENCE TO OTHER
`APPLICATIONS
`
`The subject matter disclosed in this application is related
`to subject matter disclosed in a concurrently filed,
`commonly-assigned U.S. patent application Ser. No. 09/162,
`119 by the same inventor entitled “Encoding Data In Color
`Images Using Patterned Color Modulation Image Regions”,
`which is incorporated by reference herein for all that it
`teaches as if set out in full. The subject matter disclosed in
`this application may also be related to subject matter dis-
`closed in U.S. patent application Ser. No. 08/956,326,
`entitled “Determining An Optimal Color Space Direction
`For Selecting Color Modulations”, which is incorporated by
`reference herein for all that it teaches as if set out in full.
`
`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 technique for decoding digital data
`that has been encoded in an acquired color image in image
`regions that have patterns of color modulated subregions
`within them. The data may be encoded so that each image
`region has an overall visual appearance of an average color
`to the human viewer while the multi-colored subregions are
`substantially imperceptible, or not visually objectionable,
`and are simultaneously capable of detection by a digital
`image capture device for decoding purposes. The decoding
`operation does not require the original, unencoded color
`image for decoding.
`Bar codes are a well-known category of document or
`image marking techniquesthat have as their primary goal to
`densely encode digital information in a small image space
`without regard to how visible the encoded information is to
`a human viewer, and with the intent to reliable decode the
`information at a later time. Bar code images are typically
`attached to other objects and carry identifying information.
`U.S. Pat. No. 4,443,694, entitled “Multilevel Bar Code
`Reader” discloses a bar code reader for decoding a bar code
`using at least three levels of darkness. The bar code that
`encodes data consists of a plurality of bars, each of which
`has a particular level of darkness. The sequence of bars
`encodes a particular data string in a printed format. It is
`disclosed that in a particular embodimentof the invention,
`the transition from one darkness level to another second
`darkness level is indicative of the encoding of a predeter-
`mined value of a binary string. Each transition from bar to
`bar is translated into its appropriate dual set of bit strings to
`divulge the final binary string. In this embodimentfive levels
`of darkness are utilized in the bar code, with each level
`having associated with it a certain degree of darkness
`including white, white-gray, gray, gray-black, and black.
`US. Pat. No. 5,619,026, entitled “Grayscale Barcode
`Reading Apparatus System Including Translating Device for
`Translating a Pattern Image into a Sequence of Bar Widths
`and Transition Directions,” discloses a system for verifying
`an object of interest
`that
`includes a grayscale one-
`dimensional bar pattern coupled to the object. The grayscale
`pattern includes vertical stripes of varying brightness and
`width, and is disclosed as being a hidden pattern. It is
`disclosed that the use of grayscale bar codes differs from
`standard practice which uses binary patterns. Decoding
`relies on detecting distinct transitions between gray scales at
`the edges of the bars.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`Two-dimensional (2D) bar codes encode data in both the
`height and width of an encoded bar code image, and so store
`considerably more information than a linear, one-
`dimensional (1D) bar code.
`It
`is estimated that over a
`thousand alphanumeric characters can be placed in a single
`2D bar code symbol the size of a large postage stamp. 2D bar
`codes typically have one of two designs: a stacked, or
`multi-row linear bar code, and a matrix or dot type bar code.
`The matrix type of 2D bar code is usually square and made
`up of a grid of small square cells which can be black or
`white. PDF417 is an example of a stacked 2D bar code.
`PDF417 has a very high data capacity and density: each
`symbol can code up to 2725 bytes of data at a density of
`about 300-500 bytes per square inch. DataMatrix is an
`example of a 2D matrix-type bar code that contains up to
`2,335 characters per symbol. Symbols typically have
`400-500 characters per square inch. Maxicodeis an example
`of a dot-type 2D bar code that uses 888 data-carrying
`circular cells arranged around a bullseye; approximately 100
`alphanumeric characters can be encoded in a square inch.
`Additional information on 2D bar codes may be found, for
`example, in an article by Johnston and Yap entitled “Two
`Dimensional Bar Code as a Medium for Electronic Data
`Interchange,” Monash University (Clayton, Victoria) avail-
`able as of the date offiling at http://www.bs.monash.edu.au/
`staff/johno/BARCOPAW.html.
`In an article entitled “A Flexibly Configurable 2D Bar
`Code”, available as of the date of filing at http://
`www.paperdisk.com/ibippapr.htm, Antognini and Antognini
`disclose a 2D symbol technology called PaperDisk™ that
`represents data by means of what is termed a “spot” or
`“cell”. A spot is a typically rectangular array of dots, or
`printed pixels, laid downbya printer to represent a bit being
`“on”. It is separated from adjoining spots (or places they
`might occupy) by designated vertical and horizontal dis-
`tances. These distances are measured in terms of(typically)
`integral numbers of dots. A cell is a region allocated to a
`given potential spot. Thatis, it includes the spot itself (where
`the bit value calls for a spot) and extends halfway to the
`edges of neighboring potential spots. Clocking features,
`called “markers” are rectangular arrays of dots arranged in
`vertical strips throughout a pattern. All encoded data plus
`landmarks and meta-information about the encoded infor-
`mation are collectively referred to as a data tile. Decoding
`proceeds byfirst finding a landmark, from which a prelimi-
`nary estimate can be made ofthe scale and orientation of the
`features in the image, with the goal of finding the meta-
`information. When the meta-information is found it
`is
`decoded to produce data format parameter values for the
`data portion that follows. FIG. 2 illustrates a full data tile as
`a black and white image of a large number of small,
`rectangular dark marks. It would appear,
`then, from the
`disclosure that the PaperDisk™ technology is intended to
`produce an encoded image in which the encoded data is
`visible to a human viewer.
`
`There are also a collection of document or image marking
`techniquesthat have as their primary goal to embed encoded
`information in an imageso thatit is substantially impercep-
`tible to a human viewer, in a manner that simultaneously
`minimizes image distortion caused by embeddingthe infor-
`mation and permits reliable decoding of the information at
`a later time in the imagelife cycle. These techniques, which
`may be relevant to an embodimentof the present invention,
`often have design goals that can be generally categorized in
`terms of three main factors: how muchdata(i.e., the density)
`is encoded in the image; how robust the encoded data is to
`image manipulation such as printing, scanning, rotation,
`
`

`

`6,141,441
`
`3
`scaling and compression; and how muchperceptible change
`is producedin an original image by adding the encoded data.
`The intended purpose or function of the encoded data in an
`image generally determines which one or combination of the
`three factors is the most important goal of a data encoding
`technique, and necessarily influences the design and tech-
`nical details of the technique used. Anotherfactor that is also
`sometimes taken into consideration when designing an
`image marking technique is whether the image to which data
`is to be encodedis a text, or document, image, or a graphic
`or photographic image.
`A particularly well-known area of image marking is
`knownasdigital watermarking, which is typically applied to
`a graphic or photographic image. A successful digital water-
`marking technique is concerned with the factors of robust-
`ness and minimizing image changes, and so is designed to
`simultaneously 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
`watermarked, while also producing an embeddedsignal that
`is resistant to tampering, since removal of the embedded
`signal defeats the identification purpose of watermarking. 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. Because the factors of minimizing
`image change and encoded data robustness are so crucial to
`successful digital watermarking techniques,
`the goal of
`achieving a high data density rate is typically sacrificed in
`these techniques.
`PCT International 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 manner that
`permits the identification signal later to be discerned and the
`carrier thereby identified. The method and apparatus are
`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. In a
`disclosed preferred embodiment, an N-bit
`identification
`word is embedded in an original image by generating N
`independent random encoding 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. The
`composite embedded signal is then added to the original
`image using a formula (Equations 2 and 3) that is 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.
`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 viewsthe
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`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. In particular with respect to water-
`marking an NxN black and white image, the techniquefirst
`computes the NxN DCTof 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 perceptualfidelity.
`Each coefficient 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
`perceptualfidelity 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. The precise magnitude of the added watermark signal
`is controlled by one or more scaling parameters that appear
`to be empirically determined. Cox et. al note that to deter-
`mine 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 humanperceptual
`system. Coxet. al also provide what appears to be a detailed
`survey of previous work in digital watermarking.
`U.S. Pat. No. 5,369,261, entitled “Multi-color Informa-
`tion Encoding System,” discloses an exceptionally dense
`information encoding system that employs colored areas in
`the forms of bars or checkerboard matrices of colored dot
`regions to encode information, with each colored region
`being variable as to both color and intensity.
`In one
`embodiment, “super-pixel” dots have differently colored
`sub-regions within them, arranged with side-by-side colors,
`or with colored regions stacked one on top of the other, such
`that information from one dot has as manycolorvariables as
`there are stacked layers or mixed colors. For each color there
`are as many as 64 intensities yielding a coding system of
`high information density. For decoding purposes, the various
`colors are read out at one super pixel dot position by
`dividing out reflected or transmitted energy from a dot by
`colorfiltering such that a color and intensity can be detected
`for each color intensity within the super pixel dot. The code
`provided by this invention is substantially invisible to the
`naked eye.
`Data glyph technology is a category of embedded
`encoded information that is particularly advantageous for
`use in image applications that require a high density rate of
`embedded data and require the embedded data to be robust
`for decoding purposes. However, data glyph encoding pro-
`duces perceptible image changes which may be able to be
`minimized so as to be inconspicuous, or even surreptitious,
`in particular types of images. Data glyph technology
`encodesdigital information in the form of binary 1’s and 0’s
`that 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 onthe linear orientation of
`the particular mark. For example, in one embodiment, marks
`that 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 small size
`relative to the maximum resolution of a black and white
`printing device so as to produce an overall visual effect to a
`casual observer of a uniformly gray halftone area when a
`large number of such marksare printed together in a black
`and white image on paper; when incorporated in an image
`
`

`

`6,141,441
`
`5
`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 that together bear
`binary information. The uniformly gray halftone area may
`already be an elementof the image, or it may be addedto the
`image in the form of a border, a logo, or some other image
`element suitable to the nature of the document.
`
`Examples of U.S. Patents on data glyph technology are
`US. Pat. Nos. 5,221,833, 5,245,165, and 5,315,098. U.S.
`Pat. No. 5,221,833, entitled “Methods and Meansfor Reduc-
`ing Error Rates in Reading Self-Clocking Glyph Codes”,
`discloses a method for encoding n-bit long multi-bit digital
`values in a pre-ordered cyclical sequence based on their
`analytically or empirically determined probabilities of being
`confused with each other, such that each glyph is adjacent in
`that sequence to the two glyphs with whichit is more likely
`to be confused during decoding. U.S. Pat. No. 5,245,165,
`entitled “Self-Clocking Glyph Code for Encoding Dual Bit
`Digital Values Robustly”, discloses a method for encoding
`dual bit digital values in the cardinal rotations (0°, 90°, 180°
`and 270°) of a logically ordered sequence of wedge-shaped
`glyphs(essentially right triangles) that are written, printed or
`otherwise recorded on a hardcopy recording medium with a
`predetermined spatial formatting rule. The widths of the
`glyphs vary unidirectionally as a function of their height, so
`they can be decoded reliably, even when they are degraded
`by scan errors, dropped scan lines and/or random noise
`patterns. 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.
`Commonly assigned U.S. Pat. No. 5,684,885, entitled
`“Binary Glyph Codes Based on Color Relationships,”
`(hereafter, the *885 patent’) discloses a technique that may
`be used to encode information in a color image. The
`technique renders binary digital data on a surface, such as a
`sheet of paper, by printing a series of color patches on the
`sheet, with the 1 bits rendered as color patchesofa first color
`and the 0 bits rendered as color patches of the second color.
`The color patches are arranged in a predetermined order
`along an axis on the surface. The second colorrelates to the
`first color by a fixed relationship in color space. In an
`illustrated embodiment, the first and second colors are a
`scalar a distance away from an average color along a vector
`Vo in color space. A relatively large area of intermingled
`color patches for the first color and the second color will
`optically combine to appear, from a distance to be a single
`third color. The color patches can be intermixed with areas
`of a third color, the third color representing an average in
`color space of the first color and the second color. When
`these color patches of two different colors are imperceptible
`to a human,the information they represent becomes invis-
`ibly encoded in the image. In the illustrated embodiments in
`the *521 application,
`it
`is noted that,
`in the choice of
`orientation of the vector v, and the extent of the scalar a that
`are used to determine the two colorsthat are used to produce
`the color patches,it is desirable to balance the accuracy and
`sensitivity of the marking device (e.g., a printer) and the
`digital image capture device (e.g., a scanner) being used
`with the sensitivity of the humaneye. It is desirable to have
`the deviation between the two colors to be maximally
`detectable by a scanner and minimally detectable by the
`human eye. When an average color of the two colors is
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`rendered on the page and is visible to the humaneye, the
`average color should be deemed merely the carrier of
`information, and the color deviations of neighboring color
`patches being a modulation of the carrier.
`the
`that
`The °885 patent further proposes, at col. 5,
`information encoding technique therein be used in conjunc-
`tion with the data glyph technology described above. Each
`individual color patch could be printed in the form of a
`geometric data glyph in which the shapeor linear orientation
`of each glyph determines whether it is assigned a 1 or 0
`value, and the different shading of each glyph, representing
`one of two different colors, determines whether the coloris
`assigned a 1 or O value. The relative colors of neighboring
`glyphs are independent of the orientations of neighboring
`glyphs, and so the geometry-based glyphs can be used to
`render one set of data, while the relative colors of neigh-
`boring glyphs render another set of digital data.
`Some types of 2D bar code technology encode data at a
`high density rate but none are intended to produce encoded
`data that is substantially imperceptible in an encoded image.
`Data glyph technology, which also supports a high data
`density encoding rate,
`is also not designed to produce
`encoded data that
`is substantially imperceptible in an
`encoded image, although data glyphs may happen to be very
`unobtrusive in an encoded image as a result of where they
`are placed. The technology disclosed in the ’885 patent
`requires that
`the differently colored patches produce an
`average colorthat effectively hides them from view; in order
`to decode the message value in a color patch of a first color,
`it is necessary to determine the second color used to encode
`a different data value, and also to determine the average
`color of the image region in which data is encoded in order
`to establish the color space relationship between the two
`colors.
`
`SUMMARYOF THE INVENTION
`
`The decoding technique of the present invention recovers
`messages encoded at a high density rate in an acquired
`image, and in particular from graphic or photographic
`images. The decoding technique has as its premise that
`existing color regions in an encoded image function as the
`carrier of encoded information in the form of color
`differences, or color modulations. The invention makes use
`of a plurality of data structures, referred to herein as “signal
`blocks”, each having a spatial pattern of color modulation
`unique to all other signal blocks and that encodes one ofthe
`possible values of a coding schemethat the information may
`assume. When a color value is addedto a signal block during
`an encoding operation, an encoded