United States Patent
`
`(12)
`(10) Patent No.:
`US 7,289,643 B2
`
`Brunk et a1.
`(45) Date of Patent:
`Oct. 30, 2007
`
`US007289643B2
`
`(54) METHOD, APPARATUS AND PROGRAMS
`FOR GENERATING AND UTILIZING
`CONTENT SIGNATURES
`
`(75)
`
`Inventors: Hugh L. Brunk, Portland, OR (US);
`Kenneth L Le
`Stevenson WA (US)
`'
`’
`Vy’
`.
`(73) A551gnee: Digimarc Corporation, Beaverton, OR
`(US)
`.
`'
`.
`.
`Subject to any d1scla1mer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 860 days.
`
`.
`( * ) Not1ce:
`
`4,284,846 A
`4,432,096 A
`4,450,531 A
`4,495,526 A
`
`4’499’601 A
`4,511,917 A
`4,547,804 A
`4,677,466 A
`4,682,370 A
`4,697,209 A
`4,739,398 A
`4,776,017 A
`4,807,031 A
`
`8/1981 Marley
`2/ 1984 Bunge
`5/1984 Kenyon et al.
`1/1985 Baranoff—Rossine
`
`2/1985 Matthews
`4/1985 Kohler et al.
`10/1985 Greenberg
`6/1987 L It, J.
`t
`l.
`7/1987 hiattherw: a
`9/1987 Kiewit et al.
`4/1988 Thomas
`10/1988 Fujimoto
`2/1989 Broughton et a1.
`.
`(Continued)
`
`(21) Appl' No“ 10/027,783
`
`(22)
`
`Filed:
`
`Dec. 19, 2001
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`161512
`
`11/1985
`
`(65)
`
`Prior Publication Data
`
`US 2002/0126872 A1
`
`Sep. 12, 2002
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`Related US. Application Data
`
`US. Appl. No. 60/257,822, filed Dec. 21, 2000, Aggson et al.
`
`(60) Provisional application No. 60/263,490, filed on Jan.
`22, 2001, prov151onal apphcatlon No. 60/257,822,
`filed on Dec. 21’ 2000‘
`
`(Continued)
`Primary ExamineriMattheW C. Bella
`Assistant ExamineriShefali Patel
`
`(51)
`
`Int- Cl-
`G06K 9/00
`
`(2006.01)
`
`(57)
`
`ABSTRACT
`
`...................................................... 382/100
`(52) US. Cl.
`(58) Field Of Classification Search ................ 380/239,
`.
`. 380/277; 382/100: 293,301.; 713/176
`See app11cat1on file for complete Search hIStOYY
`References Cited
`US. PATENT DOCUMENTS
`
`(56)
`
`3,810,156 A
`3,919,479 A
`4,071,698 A
`4,230,990 A
`
`5/1974 Goldman
`11/1975 Moon et 31.
`1/1978 Barger, Jr. et 31.
`10/1980 Lert, Jr. et 31.
`
`The present invention relates to deriving and utilizing con-
`tent signatures. A content signature is a representation of a
`content item, which is derived from the content item itself.
`According to the invention, a method of generating a content
`signature for a signal is provided. The method includes the
`steps of:
`i) dividing the signal
`into at least one set; 11)
`transforming the set
`into a frequency-based domain;
`iii)
`determining features of the transformed set; and iv) group-
`ing the features so as to form a content signature of the set.
`
`28 Claims, 5 Drawing Sheets
`
`
`
`
`
`Media Signal
`
`Correct for
`
`
`Distortion in
`Media Signal
`
`
`
`Corrected Media
`
`Signal
`
`
`
`
`Corrected Media
`
`Signal
`
`
`Calculate
`
`Fingerprint
`
`
`
`
`
`Fingerprint
`
`Metadata
`
`Metadata Database
`
`GOOG-1006-Page 1 of 18
`
`GOOG-1006-Page 1 of 18
`
`

`

`US 7,289,643 B2
`
`Page 2
`
`US. PATENT DOCUMENTS
`
`4,843,562 A
`4,858,000 A
`4,945,412 A
`4,972,471 A
`4,994,831 A
`5,019,899 A
`5,031,228 A
`5,276,629 A
`5,303,393 A
`5,319,735 A
`5,400,261 A
`5,436,653 A
`5,437,050 A
`5,481,294 A
`5,486,686 A
`5,504,518 A
`5,539,635 A
`5,564,073 A
`5,572,246 A
`5,572,653 A
`5,574,519 A
`5,574,962 A
`5,577,249 A
`5,577,266 A
`5,579,124 A
`5,581,658 A
`5,581,800 A
`5,584,070 A
`5,612,729 A
`5,613,004 A
`5,621,454 A
`5,640,193 A
`5646997 A
`5,652,626 A
`5,659,726 A
`5,661,787 A
`5,663,766 A
`5671267 A
`5,687,236 A
`5,708,478 A
`5,710,834 A
`5,721,788 A
`5,737,025 A
`5,740,244 A
`5,751,854 A
`5,761,606 A
`5,765,152 A
`5,765,176 A
`5,774,452 A
`5,778,192 A
`5,781,914 A
`5,799,092 A
`5,832,119 A
`5,835,639 A
`5,841,978 A
`5,842,162 A
`5,859,920 A
`5,862,260 A
`5,889,868 A
`5,892,900 A
`5,893,095 A
`5,901,224 A
`5902353 A
`5903,892 A
`5,905,248 A
`5,905,800 A
`5,918,223 A
`5,930,369 A *
`5,932,863 A
`5,938,727 A
`5,943,422 A
`
`6/1989 Kenyon etal.
`8/1989 Lu
`7/1990 Kramer
`ll/l990 Gross
`2/1991 Marandi
`5/1991 Boles et a1.
`7/1991 Lu
`1/1994 Reynolds
`4/1994 Noreen eta1.
`6/1994 Preuss et a1.
`3/1995 Reynolds
`7/1995 Ellis et al.
`7/1995 Lamb etal
`1/1996 Thomas et al.
`1/1996 Zdybel, Jr, et al.
`4/1996 Ellis eta1.
`7/1996 Larson, Jrl
`10/1996 Tnknhisa
`11/1996 Ellis et a1.
`11/1996 DeTemple et al.
`11/1996 Manico eta1.
`11/1996 Fardeau etal.
`ll/l996 Califano
`ll/l996 Tnknhisa etal
`11/1996 Aijala et 31.
`12/1996 O’Hagan et al.
`12/1996 Fardeau etal.
`12/1996 Harris elnl
`3/1997 Ellis et al.
`3/1997 Coopennan etal
`4/1997 Ellis etal
`6/1997 Wellner
`7/1997 Barton
`7/1997 Kawakami et al.
`8/1997 Sandford, 11 et 31.
`8/1997 Pocock
`9/1997 Sizer, 11
`9/1997 August et al
`11/1997 Moskowitz
`1/1998 Tognazzini
`1/1998 Rhoads
`2/1998 Powell etal
`4/1998 Doughenyetal
`4/1998 Indeck
`5/1998 Saitoh etal-
`6/1998 Wolzien
`6/1998 Erickson
`6/1998 Bloomberg
`6/1998 Wolosewicz
`7/1998 Shuster et al.
`7/1998 Stork et al.
`8/1998 Kristol etal
`11/1998 Rhoads
`11/1998 Honsingeretal.
`11/1998 Rhoads
`ll/l998 Fineberg
`1/1999 Daly etal-
`1/1999 Rhoads
`3/1999 Moskowitz eta1.
`4/1999 Ginter et a1.
`4/1999 Jain etal
`5/1999 Hecht
`5/1999 Reber et al~
`5/1999 Hoflen etal
`5/1999 Russell et al.
`5/1999 Moskowitz eta1.
`6/1999 Blum 6t 31.
`7/1999 Cox eta1. ..................... 380/54
`8/1999 Rathus
`8/1999 Ikeda
`8/1999 Van Wie et a1.
`
`5,949,055 A
`5,978,791 A
`5,982,956 A
`5,983,176 A
`5,986,651 A
`5,986,692 A
`5,991,500 A
`5,991,737 A
`5,995,105 A
`6,028,960 A
`6,031,914 A
`6.081.629 A
`6,081,827 A
`6,081,830 A
`6,084,528 A
`6,088,455 A
`6,121,530 A
`6,122,403 A
`6,138,151 A
`6,157,721 A
`6,164,534 A
`6,169,541 B1
`6,181,817 B1
`6,185,316 B1
`6,199,048 B1
`6,201,879 B1
`6,219,787 B1
`6,282,362 B1
`6,286,036 B1
`6,304,523 B1
`6,311,214 B1
`6,314,192 B1
`6,314,457 B1
`6,317,881 B1
`6,321,992 B1
`6,324,573 B1
`6,345,104 B1
`6,386,453 B1
`6,389,055 B1
`6,401,206 B1
`6,408,331 B1
`6,411,392 B1
`6,411,725 B1
`6,415,280 B1
`6,425,081 B1*
`6,433,946 B2
`6,434,561 B1
`6,439,465 B1
`6,466,670 B1
`6,496,802 B1
`6,505,160 B1
`6,522,769 B1
`6,523,175 B1
`6,526,449 B1
`6,542,927 B2
`6,542,933 B1
`6,553,129 B1
`6,574,594 B2
`6,577,746 B1
`6,611,524 B2*
`6,611,607 B1
`6,614,914 B1
`6,658,568 B1
`6,674,876 B1
`6,674,993 B1
`6,681,028 B2
`6,748,360 B2
`6,748,533 B1
`6,768,980 B1
`6,771,885 B1
`6,772,124 B2
`6,785,421 B1*
`6,807,534 B1
`
`9/1999 Fleet et a1.
`11/1999 Farber et a1.
`11/1999 Lahmi
`11/1999 Hofl‘ert et a1.
`11/1999 Reberetal.
`11/1999 Logan et a1.
`11/1999 Kanota et a1.
`11/1999 Chen
`11/1999 Reberet 31.
`2/2000 Graf et a1.
`2/2000 Tewfik et 31,
`6/2000 Browning
`6/2000 Reberetal.
`6/2000 Schindler
`7/2000 Beach et a1.
`7/2000 Logan et 31,
`9/2000 Sonoda
`9/2000 Rhoads
`10/2000 Reberetal.
`12/2000 Shear et a1.
`12/2000 Rathus et a1.
`1/2001 Smith
`1/2001 Zabih
`2/2001 Buffam
`3/2001 Hudetz et a1.
`3/2001 Bender et a1.
`4/2001 Brewer
`8/2001 Murphy et al.
`9/2001 Rhoads
`10/2001 Jones et a1.
`10/2001 Rhoads
`11/2001 Chen et a1.
`11/2001 Schena et a1.
`11/2001 Shah-Nazarolf etal.
`11/2001 Knowles et a1.
`11/2001 Rhoads
`2/2002 Rhoads
`5/2002 Russell et a1.
`5/2002 August et a1.
`6/2002 Khan et a1.
`6/2002 Rhoads
`6/2002 Bender et a1.
`6/2002 Rhoads
`7/2002 Farber et a1.
`7/2002 Iwamura ..................... 713/176
`8/2002 Ogino
`8/2002 Durst, J1: et a1.
`8/2002 Bloomberg
`10/2002 Tsuria et a1.
`12/2002 van Zoest et a1.
`1/2003 Levy
`2/2003 Rhoads et al.
`2/2003 Chan
`2/2003 Philyaw et a1.
`4/2003 Rhoads
`4/2003 Durst, Jr. et a1.
`4/2003 Rhoads
`6/2003 Pitman et a1.
`6/2003 Evans et a1.
`8/2003 Devanagondi et a1.
`8/2003 Davis et 31,
`9/2003 Rhoads
`12/2003 Ginter et a1.
`1/2004 Hannigan et a1.
`1/2004 Tarbounech
`1/2004 Rodriguez eta1.
`6/2004 Pitman et al.
`6/2004 Wu
`7/2004 Meyer eta1.
`8/2004 Agnihotri
`8/2004 Hohherg et a1.
`8/2004 Gindele et a1.
`10/2004 Erickson
`
`............. 382/217
`
`370/3955
`
`GOOG-lOOB-Page 2 of 18
`
`GOOG-1006-Page 2 of 18
`
`

`

`US 7,289,643 B2
`
`Page 3
`
`6,834,308 B1
`6,850,252 B1
`6,856,977 B1
`6,870,547 B1*
`6,931,451 B1
`6,941,275 B1
`6,968,337 B2
`6,973,669 B2
`6,987,862 B2
`6,990,453 B2
`7,010,144 B1
`7.047.413 B2
`7,050,603 B2
`7,058,697 B2
`7,116,781 B2
`7,127,744 B2
`2001/0007130 A1
`2001/0011233 A1
`2001/0019611 A1
`2001/0026618 A1
`2001/0026629 A1
`2001/0031066 A1
`2001/0044824 A1
`2001/0055391 A1
`2002/0012444 A1*
`2002/0021805 A1
`2002/0021822 A1
`2002/0023020 A1
`2002/0023148 A1
`2002/0023218 A1
`2002/0028000 A1
`2002/0032698 A1
`2002/0032864 A1
`2002/0037083 A1
`2002/0040433 A1
`2002/0044659 A1
`2002/0048224 A1
`2002/0052885 A1
`2002/0059208 A1
`2002/0059580 A1
`2002/0068987 A1
`2002/0069107 A1
`2002/0069370 A1
`2002/0072982 A1
`
`5335/3333: :1
`2002/0082731 A1
`2002/0083123 A1
`
`2002/0087885 A1
`2002/0088336 A1
`2002/0099555 A1
`2002/0102966 A1
`2002/0118864 A1
`2002/0126872 A1
`2002/0133499 A1
`2002/0138744 A1
`2002/0150165 A1
`2002/0152388 A1
`2002/0153661 A1
`2002/0161741 A1
`2002/0168082 A1
`2002/0174431 A1
`2002/0178410 A1
`2002/0184505 A1
`2003/0018709 A1
`2003/0028796 A1
`2003/0033321 A1
`2003/0037010 A1
`2003/0051252 A1
`2003/0101162 A1
`2003/0120679 A1
`2003/0135623 A1
`2003/0167173 A1
`
`.............. 345/619
`
`......... 382/100
`
`12/2004 Ikezoye etal.
`2/2005 Hotberg
`2/2005 Adelsbach
`3/2005 Crosby etal.
`8/2005 Logan etal.
`9/2005 Swierczek
`11/2005 Wold
`12/2005 Daniels
`1/2006 Rhoads
`1/2006 Wang
`3/2006 Davis etal.
`5/2006 Yacobietal.
`5/2006 Rhoadsetal.
`6/2006 Rhoads
`10/2006 Rhoads
`10/2006 Levy
`7/2001 Takaragi
`8/2001 Narayanaswami
`9/2001 Hilton
`10/2001 Van Wie et al.
`10/2001 Oki
`10/2001 Meyer et al.
`11/2001 Hunter et al.
`12/2001 Jacobs
`1/2002 Nishikawa et al.
`2/2002 Schumann et al.
`2/2002 Maeno
`2/2002 Kenyon et al.
`2/2002 Ritz et al.
`2/2002 Lawandy et al.
`3/2002 Conwelletal.
`3/2002 Cox
`3/2002 Rhoads
`3/2002 Weare etal.
`4/2002 Kondo
`4/2002 Ohta
`4/2002 Dygert
`5/2002 Levy
`5/2002 Abe
`5/2002 Kalker
`6/2002 Hars
`6/2002 Werner
`6/2002 Mack
`6/2002 Van de Sluis
`
`$88; Elan de 81““
`chena et al.
`.
`6/2002 Pltman et 31'
`6/2002 Freedman etal.
`
`7/2002 Peled
`7/2002 Stahl
`7/2002 Pitrnan et 31.
`8/2002 Lev et al.
`8/2002 Kondo et al.
`9/2002 Brunk
`9/2002 Ward et al.
`9/2002 Schleicher et 31.
`10/2002 Huizer
`10/2002 Linnartz et 31.
`10/2002 Brooks et 31.
`10/2002 Wang et al.
`11/2002 Razdan
`11/2002 Bowman et 31,
`11/2002 Haitsma et 31,
`12/2002 Mihcak et al.
`1/2003 Schrempp et a1.
`2/2003 Roberts et al.
`2/2003 Schrempp et al.
`2/2003 Schmelzer et a1.
`3/2003 Miyaoku
`5/2003 Thompson et a1.
`6/2003 Kriechbaum et a1.
`7/2003 Schrempp et a1.
`9/2003 Levy et a1.
`
`2003/0174861 A1
`2003/0197054 A1
`2004/0049540 A1
`2004/0145661 A1
`2004/0163106 A1
`2004/0169892 A1
`2004/0201676 A1
`2004/0223626 A1
`2005/0043018 A1
`2005/0044189 A1
`2005/0058319 A1
`2005/0108242 A1
`2005/0144455 A1
`2005/0229107 A1
`2005/0267817 A1
`
`9/2003 Levy etal.
`10/2003 Eunson
`3/2004 Wood
`7/2004 Murakami et a1.
`8/2004 Schrempp etal.
`9/2004 Yoda
`10/2004 Needham
`11/2004 Honsingeretal.
`2/2005 Kawamoto
`2/2005 Ikezoye etal.
`3/2005 Rhoads etal.
`5/2005 Kalkeretal.
`6/2005 Haitsma
`10/2005 Hull et al.
`12/2005 Barton etal.
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`JP
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`WO
`
`0493091
`493091
`0953938
`953938 A2
`0967803
`1173001
`1199878
`11265396
`W098/03923
`W099/35809
`WOW/58940
`wool/15021
`W001/20483
`W001/20609
`W001/62004
`0172030
`W001/71517
`W00172030
`0175794
`W001/75629
`WOW/11123
`W00219589
`WOW/27600
`02082271
`
`7/1992
`7/1992
`“/1999
`“/1999
`””999
`“2002
`“002
`9/1999
`“1998
`7/1999
`10/2000
`”001
`”001
`”001
`”001
`”001
`”001
`”001
`10/2001
`10/2001
`”002
`”002
`“002
`10/2002
`
`OTHER PUBLICATIONS
`
`U.S.App1.No. 60/263,490, filed Jan. 22, 2001, Brunk et al.
`U.S. Appl. No. 60/232,618, filed Sep. 14, 2000, Cox.
`Gh'
`t
`l
`b Hummin ' Musical Information Retrieval In
`lase.a’Query y
`g'
`.
`.
`An Audio Database. In ACM Mult1med1a, pp. 231-236, Nov., 1995.
`K
`t 31 M 1 d R tr.
`31
`.thH
`.
`P
`d.
`f
`ageyme
`’
`f” y e “W W‘
`ummmg’ ”we mg”
`Int. Computer Mus1c Conference (ICMC), 1993.
`Muscle F1sh press release, Muscle F1sh’s Audlo Search Technology
`to be Encapsulated 1nto Inforle-Data-blade Module, Jul. 10, 1996.
`Wold et al, Content-Based Classificatlon, Search, and Retrleval of
`Audio, IEEE Mult1med1a Magazme, Fall, 1996.
`US. Appl. No. (50/175,159, filed Jan. 7, 2000, Derose et a1.
`U.S. Appl. No. 60/178,028, filed Jan. 26, 2000, Meyer et a1.
`PCT/USOl/50238 Notification of Transmittal of the International
`Search Report or the Declaration and International Search Report
`dated May 31, 2002
`PCT/USOl/50238 Written Opinion dated Feb. 13, 2003.
`Lin, et al., “Generating Robust Digital Signature for Image/Video
`Authentication,” Proc. Multimedia and Security workshop at ACM
`Multimedia ’98, Sep. 1, 1998, pp. 49—54.
`Cox et al., “Secure Spread Spectrum Watermarking for Images,
`Audio and Video,” 1996 IEEE, pp. 243-246.
`Kawaguchi
`et
`al.,
`“Principles
`and Applications of BPCS-
`Steganography,” Proc. SPIE vol. 3528: Multimedia Systems and
`Applications, Nov. 2-4, 1998, pp. 464-473.
`Koch et
`al.,
`“Copyright Protection for multimedia Data,”
`Fraunhofer Institute for Computer Graphics, Dec. 16, 1994, 15
`pages. “Access Control and COpyright Protection for Images,
`WorkPackage 8: Watermarking,” Jun. 30, 1995, 46 pages.
`
`GOOG-1006—Page 3 of 18
`
`GOOG-1006-Page 3 of 18
`
`

`

`US 7,289,643 B2
`Page 4
`
`Komatsu et a1., “Authentication System Using Concealed Image in
`Telematics,” Memoirs of the School of Science & Engineering,
`Waseda Univ., No. 52, 1988, pp. 45-60.
`Matsui et a1., “Video-Steganography: How to Secretly Embed a
`Signature in a Picture,” IMA Intellectual Property Project Proceed-
`ings. Jan. 1994, vol. 1, Issue 1, pp. 187-205.
`O’Ruanaidh, “Rotation, Scale and Translation Invariant Digital
`Image Watermarking,” Signal Processing, pp. 2-15, May 1, 1998.
`O’Runanaidh, “Rotation, Scale and Translation Invariant Digital
`Image Watermarking,” 1997 IEEE, pp. 536-539.
`Sheng, “Experiments on Pattern Recognition Using Invariant
`Fourier-Mellin Descriptors.” Journal of Optical Society ofAmerica.
`vol. 3, No. 6, pp. 771-776, 1986.
`
`Szepanski, “A Signal Theoretic Method For Creating Forgery-Proof
`Documents For Automatic Verification”, 1979 Carnahan Confer-
`ence on Crime Countermeasures, University of Kentucky, Lexing-
`ton, Kentucky, May 16-18, 1979.
`Tanaka, “Embedding the Attribute Information Into a Dithered
`Image,” Systems and Computers in Japan, vol. 21, No. 7, 1990, pp.
`43-50.
`Tanaka et a1., Embedding Secret Information Into a Dithered
`Multi-Level Image, 1990 IEEE, pp. 216-220.
`van Schyndel et al., “A Digital Watermark,” IEEE International
`Conference on Image Processing, Nov. 13, 1994 pp. 86-90.
`
`* cited by examiner
`
`GOOG-1006—Page 4 of 18
`
`GOOG-1006-Page 4 of 18
`
`

`

`U.S. Patent
`
`Oct. 30, 2007
`
`Sheet 1 of 5
`
`US 7,289,643 132
`
`Fig. 1
`
`Fig. 2
`
`20
`
`22
`
`24
`
` Stream of
`
`Signature (or
`
`Set) values
`
`
`of signatures in
`
`Database
`
`
`
`Look up
`associated
`
`Apply Viterbi
`decoding to
`resolve stream
`
`
`
`
`
`
`
`behavior or info
`
`30
`
`32
`
`34
`
`
`
`Return behavior
`
`or info
`
`Input Signal
`Segments
`(image blocks,
`video frames,
`
`audio segments)
`
`Transform
`
`segments
`(optional, freq or
`time freq map)
`
`Calculate
`
`perceptually
`relevant features
`
`(edges, peaks)
`
`Set of
`
`Perceptually
`Relevant
`
`features per
`segment
`
`
`
`Store linked list / 28
`
`of signatures in
`a segment
`sequence
`
`GOOG-1006—Page 5 of 18
`
`GOOG-1006-Page 5 of 18
`
`

`

`U.S. Patent
`
`Oct. 30, 2007
`
`Sheet 2 of 5
`
`US 7,289,643 B2
`
`Fig- 3
`
`Fig. 4
`
`,v/
`
`40
`
`
`
`_
`Slgnature
`1
`
`
`
`Transform
`
`
`fl (compression,
`44
`D/A,conversion,
`
`42
`
`
`
`48
`
`Signature
`2
`
`46
`
`Input Signal
`Sets (image
`blocks,
`video frames,
`
`audio segments)
`
`Calculate list of
`Signatures
`
`Signatures
`
`Perform
`
`matching of
`Calculated list
`with database of
`
`GOOG-1006—Page 6 of 18
`
`GOOG-1006-Page 6 of 18
`
`

`

`U.S. Patent
`
`Oct. 30, 2007
`
`Sheet 3 of 5
`
`US 7,289,643 B2
`
`Fig. 5
`
`Input (or Transition)
`
`State 00
`
`State 01
`
`State 1 1
`
`State 10
`
`GOOG-1006—Page 7 of 18
`
`GOOG-1006-Page 7 of 18
`
`

`

`U.S. Patent
`
`Oct. 30, 2007
`
`Sheet 4 of 5
`
`US 7,289,643 B2
`
`Fig. 6
`
`
`
`Compute
`Signature via
`Trellis Coded
`
`Quantization
`
`
`
`
`
`
`
`
`
`
`Store Signature
`in
`
`Database
`
`
`
`60
`
`62
`
`Database
`
`
`Look—up
`
`
`64
`
`GOOG-‘IOOB-Page 8 of 18
`
`GOOG-1006-Page 8 of 18
`
`

`

`U.S. Patent
`
`Oct. 30, 2007
`
`Sheet 5 of 5
`
`US 7,289,643 B2
`
`Media Signal
`
`Corrected Media
`
`Signal
`
`
`
`
`
`Correct for
`
`
`
`Media Signal
`
`
`
`Distortion in
`
`Corrected Media
`Signal
`
`
`
`
`Fig. 7
`
`Calculate
`
`Fingerprint
`
`
`
`
`Fingerprint
`
`Metadata
`
`Metadata Database
`
`Fig. 8
`
`GOOG-iOOB-Page 9 of 18
`
`GOOG-1006-Page 9 of 18
`
`

`

`US 7,289,643 B2
`
`1
`METHOD, APPARATUS AND PROGRAMS
`FOR GENERATING AND UTILIZING
`CONTENT SIGNATURES
`
`RELATED APPLICATION DATE
`
`The present application claims the benefit of U.S. Provi-
`sional Application Nos. 60/257,822, filed Dec. 21, 2000, and
`60/263,490,
`filed Jan. 22, 2001. These applications are
`herein incorporated by reference.
`The subject matter of the present application is related to
`that disclosed in U.S. Pat. No. 5,862,260, and in the fol-
`lowing U.S. patent applications: Ser. No. 09/503,881 (now
`U.S. Pat. No. 6,614,914), filed Feb. 14, 2000; Ser. No.
`09/563,664 (now U.S. Pat. No. 6,505,160), filed May 2,
`2000; Ser. No. 09/620,019, filed Jul. 20, 2000; and Ser. No.
`09/661,900 (now U.S. Pat. No. 6,674,876), filed Sep. 14,
`2000. Each of these patent documents is herein incorporated
`by reference.
`
`TECHNICAL FIELD
`
`The present invention relates generally to deriving iden-
`tifying information from data. More particularly, the present
`invention relates to content signatures derived from data,
`and to applications utilizing such content signatures.
`
`BACKGROUND AND SUMMARY
`
`Advances in software, computers and networking systems
`have created many new and useful ways to distribute, utilize
`and access content items (e.g., audio, visual, and/or video
`signals). Content items are more accessible than ever before.
`As a result, however, content owners and users have an
`increasing need to identify,
`track, manage, handle,
`link
`content or actions to, and/or protect their content items.
`These types of needs may be satisfied, as disclosed in this
`application, by generating a signature of a content item (e.g.,
`a “content signature”). A content signature represents a
`corresponding content item. Preferably, a content signature
`is derived (e.g., calculated, determined, identified, created,
`etc.) as a function of the content item itself. The content
`signature can be derived through a manipulation (e.g., a
`transformation, mathematical representation, hash, etc.) of
`the content data. The resulting content signature may be
`utilized to identify, track, manage, handle, protect the con-
`tent, link to additional information and/or associated behav-
`ior, and etc. Content signatures are also known as “robust
`hashes” and “fingerprints,” and are used interchangeably
`throughout this disclosure.
`Content signatures can be stored and used for identifica-
`tion of the content item. A content item is identified when a
`
`derived signature matches a predetermined content signa-
`ture. A signature may be stored locally, or may be remotely
`stored. A content signature may even be utilized to index (or
`otherwise be linked to data in) a related database. In this
`manner, a content signature is utilized to access additional
`data, such as a content ID, licensing or registration infor-
`mation, other metadata, a desired action or behavior, and
`validating data. Other advantages of a content signature may
`include identifying attributes associated with the content
`item, linking to other data, enabling actions or specifying
`behavior (copy, transfer, share, view, etc.), protecting the
`data, etc.
`A content signature also may be stored or otherwise
`attached with the content item itself, such as in a header (or
`footer) or frame headers of the content item. Evidence of
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`content tampering can be identified with an attached signa-
`ture. Such identification is made through re-deriving a
`content signature using the same technique as was used to
`derive the content signature stored in the header. The newly
`derived signature is compared with the stored signature. If
`the two signatures fail to match (or otherwise coincide), the
`content item can be deemed altered or otherwise tampered
`with. This functionality provides an enhanced security and
`verification tool.
`
`A content signature may be used in connection with
`digital watermarking. Digital watermarking is a process for
`modifying physical or electronic media (e. g., data) to embed
`a machine-readable code into the media. 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. Most commonly, digital
`watermarking is applied to media signals such as images,
`audio signals, and video signals. However, it may also be
`applied to other types of media objects, including documents
`(e.g., through line, word or character shifting), software,
`multi-dimensional graphics models, and surface textures of
`objects.
`Digital watermarking systems typically have two primary
`components: an encoder that embeds the watermark in a host
`media signal, and a decoder that detects and reads the
`embedded watermark from a signal suspected of containing
`a watermark (a suspect signal). The encoder embeds a
`watennark by altering the host media signal. And the
`decoder analyzes a suspect signal
`to detect whether a
`watermark is present. In applications where the watermark
`encodes information, the reader extracts this information
`from the detected watermark.
`
`Several particular watermarking techniques have been
`developed. The reader is presumed to be familiar with the
`literature in this field. Particular techniques for embedding
`and detecting imperceptible watermarks in media signals are
`detailed in the assignee’s co-pending patent application Ser.
`No. 09/503,881 (now U.S. Pat. No. 6,614,914) and in U.S.
`Pat. No. 5,862,260, which are referenced above.
`the digital
`According to one aspect of our invention,
`watermark may be used in conjunction with a content
`signature. The watermark can provide additional informa-
`tion, such as distributor and receiver information for track-
`ing the content. The watermark data may contain a content
`signature and can be compared to the content signature at a
`later time to determine if the content
`is authentic. As
`
`discussed above regarding a frame header, a content signa-
`ture can be compared to digital watermark data, and if the
`content signature and digital watermark data match (or
`otherwise coincide) the content is determined to be authen-
`tic. If different, however, the content is considered modified.
`According to another aspect of the present invention, a
`digital watermark may be used to scale the content before
`deriving a content signature of the content. Content signa-
`tures are sensitive to scaling (e.g., magnification, scaling,
`rotation, distortion, etc.). A watermark can include a cali-
`bration and/or synchronization signal to realign the content
`to a base state. Or a technique can be used to determine a
`calibration and/or synchronization based upon the water—
`mark data during the watermark detection process. This
`calibration signal (or technique) can be used to scale the
`content so it matches the scale of the content when the
`
`content signature was registered in a database or first deter-
`mined, thus reducing errors in content signature extraction.
`These and other features and advantages will become
`apparent with reference to the following detailed description
`and accompanying drawings.
`
`GOOG-1006-Page 10 of 18
`
`GOOG-1006-Page 10 of 18
`
`

`

`US 7,289,643 B2
`
`3
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a flow diagram of a content signature generating
`method.
`FIG. 2 is a flow diagram of a content signature decoding
`method.
`
`FIG. 3 is a diagram illustrating generation of a plurality of
`signatures to form a list of signatures.
`FIG. 4 is a flow diagram illustrating a method to resolve
`a content ID of an unknown content item.
`
`FIG. 5 illustrates an example of a trellis diagram.
`FIG. 6 is a flow diagram illustrating a method of applying
`Trellis Coded Quantization to generate a signature.
`FIG. 7 is a diagram illustrating correcting distortion in a
`media signal (e.g., the media signal representing an image,
`audio or Video).
`FIG. 8 is a diagram illustrating the use of a fingerprint,
`derived from a corrected media signal, to obtain metadata
`associated with the media signal.
`
`DETAILED DESCRIPTION
`
`The following sections describe methods, apparatus, and/
`or programs for generating, identifying, handling, linking
`and utilizing content signatures. The terms “content signa-
`ture,” “fingerprint,” “hash,” and “signature” are used inter-
`changeably and broadly herein. For example, a signature
`may include a unique identifier (or a fingerprint) or other
`unique representation that is derived from a content item.
`Alternatively, there may be a plurality of unique signatures
`derived from the same content item. A signature may also
`correspond to a type of content (e.g., a signature identifying
`related content items). Consider an audio signal. An audio
`signal may be divided into segments (or sets), and each
`segment may include a signature. Also, changes in percep-
`tually relevant features between sequential (or alternating)
`segments may also be used as a signature. A corresponding
`database may be structured to index a signature (or related
`data) via transitions of data segments based upon the per-
`ceptual features of the content.
`As noted above, a content signature is preferably derived
`as a function of the content item itself. In this case, a
`signature of a content item is computed based on a specified
`signature algorithm. The signature may include a number
`derived from a signal (e.g., a content item) that serves as a
`statistically unique identifier of that signal. This means that
`there is a high probability that the signature was derived
`from the digital signal in question. One possible signature
`algorithm is a hash (e.g., an algorithm that converts a signal
`into a lower number of bits). The hash algorithm may be
`applied to a selected portion of a signal (e.g., the first 10
`seconds, a video frame or a image block, etc.) to create a
`signal. The hash may be applied to discrete samples in this
`portion, or to attributes that are less sensitive to typical audio
`processing. Examples of less sensitive attributes include
`most significant bits of audio samples or a low pass filtered
`version of the portion. Examples of hashing algorithms
`include MD5, MD2, SHA, and SHAl.
`A more dynamic signature deriving process is discussed
`with respect to FIG. 1. With reference to FIG. 1, an input
`signal is segmented in step 20. The signal may be an audio,
`video, or image signal, and may be divided into sets such as
`segments, frames, or blocks, respectively. Optionally, the
`sets may be further reduced into respective sub-sets. In step
`22, the segmented signal is transformed into a frequency
`domain (e.g., a Fourier transform domain), or time-fre-
`quency domain. Applicable transformation techniques and
`
`5
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`related frequency-based analysis are discussed in Assignee’s
`Ser. No. 09/661,900 patent application (now US. Pat. No.
`6,674,876), referenced above. Of course other frequency
`transformation techniques may be used.
`transformed set’s relevant features (e.g., perceptual rel-
`evant features represented via edges; magnitude peaks,
`frequency characteristics, etc.) are identified per set in step
`24. For example, a set’s perceptual features, such as an
`object’s edges in a frame or a transition of such edges
`between frames, are identified, analyzed or calculated. In the
`case of a video signal, perceptual edges may be identified,
`analyzed, and/or broken into a defining map (e.g., a repre-
`sentation of the edge,
`the edge location relevant to the
`segment’s orientation, and/or the edge in relation to other
`perceptual edges.). In another example, frequency charac-
`teristics such as magnitude peaks having a predetermined
`magnitude, or a relatively significant magnitude, are used for
`such identifying markers. These identifying markers can be
`used to form the relevant signature.
`Edges can also be used to calculate an object’s center of
`mass, and the center of mass may be used as identifying
`information (e.g., signature components) for an object. For
`example, after thresholding edges of an object (e.g., identi-
`fying the edges), a centering algorithm may be used to locate
`an object’s center of mass. A distance (e.g., up, down, right,
`left, etc.) may be calculated from the center of mass to each
`edge, or to a subset of edges, and such dimensions may be
`used as a signature for the object or for the frame. As an
`alternative, the largest object (or set of objects) may be
`selected for such center of mass analysis.
`In another embodiment, a generalized Hough transform is
`used to convert content
`items such as video and audio
`
`signals into a signature. A continuous sequence of the
`signatures is generated via such a transform. The signature
`sequence can then be stored for future reference. The
`identification of the signature is through the transformation
`of the sequence of signatures. Trellis decoding and Viterbi
`decoding can be used in the database resolution of the
`signature.
`In step 26, the set’s relevant features (e.g., perceptual
`features, edges, largest magnitude peaks, center of mass,
`etc.) are grouped or otherwise identified, e.g., thorough a
`hash, mathematical relationship, orientation, positioning, or
`mapping to form a representation for the set. This represen-
`tation is preferably used as a content signature for the set.
`This content signature may be used as a unique identifier for
`the set, an identifier for a subset of the content item, or as a
`signature for the entire content item. Of course, a signature
`need not be derived for every set (e.g., segment, frame, or
`block) of a content item. Instead, a signature may be derived
`for alternating sets or for every nth set, where n is an integer
`of one or more.
`
`As shown in step 28, resulting signatures are stored. In
`one example, a set of signatures, which represents a
`sequence of segments, frames or blocks,
`is linked (and
`stored)
`together. For example,
`signatures
`representing
`sequential or alternating segments in an audio signal may be
`linked (and stored) together. This linking is advantageous
`when identifying a content item from a partial stream of
`signatures, or when the signatures representing the begin-
`ning of a content item are unknown or otherwise unavailable
`(e.g., when only the middle 20 seconds of an audio file are
`available). When perceptually relevant features are used to
`determine signatures, a linked list of such signatures may
`correspond to transitions in the perceptually relevant data
`between frames (e.g., in video). A hash may also be option-
`ally used to represent such a linked list of signatures.
`
`GOOG-1006-Page 11 of 18
`
`GOOG-1006-Page 11 of 18
`
`

`

`US 7,289,643 B2
`
`5
`There are many possible variations for storing a signature
`or a linked list of signatures. The signature may be stored
`along with the content item in a file header (or footer) of the
`segment, or otherwise be associated with the segment. In
`this case, the signature is preferably recoverable as the file
`is transferred, stored, transformed, etc. In another embodi-
`ment, a segment signature is stored in a segment header (or
`footer). The segment header may also be mathematically
`modified (e.g., encrypted with a key, XORed with an ID,
`etc.) for additional security. The stored content signature can
`be modified by the content in that segment, or hash of
`content in that segment, so that it is not recoverable if some
`or all of content is modified, respectively. The mathematical
`modification helps to prevent tampering, and to allow recov-
`ery of the signature in order to make a signature comparison.
`Alternatively, the signatures may be stored in a database
`instead of, or in addition to, being stored with the content
`item. The database may be local, or may be remotely
`accessed through a network such as a LAN, WAN, wireless
`network or intemet. When stored in a database, a signature
`may be linked or associated with additional data. Additional
`data may include identifying information for the content
`(e.g., author,
`title,
`label, serial numbers, etc.), security
`information (e.g., copy control), data specifying actions or
`behavior (e.g., providing a URL, licensing information or
`rights, etc.), context information, metadata, etc.
`To illustrate one example, software executing on a user
`device (e.g., a computer, PVR, MP3 player, radio, etc.)
`computes a content signature for a content item (or segments
`within the content item) that is received or reviewed. The
`software helps to facilitate communication of the content
`signature (or signatures) to a database, where it is used to
`identify the related content item. In response, the database
`returns related information, or performs an action related to
`the signature. Such an action may include linking to another
`computer (e.g., a web site that returns information to the user
`device), transferring security or licensing information, veri-
`fying content and access, etc.
`FIG. 2 is a flow diagram illustrating one possible method
`to identify a content item from a stream of signatures (e.g.,
`a linked set of consecutive derived signatures for an audio
`signal). In step 32, Vlterbi decoding (as discussed further
`below) is appl