`Cox
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 8,205,237 B2
`*Jun. 19, 2012
`
`US008205237B2
`
`(54) IDENTIFYING WORKS, USINGA
`SUB-LINEAR TIME SEARCH, SUCH As AN
`APPROXIMATE NEAREST NEIGHBOR
`SEARCH, FOR INITIATING A WORK-BASED
`ACTION, SUCH AS AN ACTION ON THE
`INTERNET
`
`(76) Inventor: Ingemar J. Cox, London (GB)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(1)) by 594 days.
`
`This patent is subject to a terminal dis
`claimem
`
`_
`1
`(21) App 'NO" 11/977’202
`
`Oct- 23,
`
`(65)
`
`Prior Publication Data
`Us Zoos/006003 6 A1 M a r‘ 6, 2008
`
`Related U‘s‘ Apphcatlon Data
`(63) Continuation of application No. 11/445,928, ?led on
`Jun. 2, 2006, Which is a continuation-in-part of
`application No. 09/950,972, ?led on Sep. 13, 2001,
`noW Pat. No. 7,058,223.
`
`(60) Provisional application NO- 60/232,618, ?led On SeP-
`14, 2000-
`
`(51)
`
`/1 73
`
`201 1 01
`(
`'
`)
`(52) U..S.Cl. ...... .... ...... ... .................................... .. 725/110
`(58) Field 0f1 'CIQ'SSI??CIQtE‘OII Searclh ........
`...... .. None
`See app lcanon e or Comp ete Seam lstory'
`References Cited
`
`(56)
`
`US. PATENT DOCUMENTS
`3,919,479 A 11/1975 Moon et a1.
`4,230,990 A 10/1980 Lert, Jr. et a1.
`4,450,531 A
`5/1984 Kenyon et a1.
`4,495,526 A
`1/1985 Baranoff-Rossine
`
`2/1985 Matthews
`4,499,601 A
`3‘
`2 13;
`E0111? er a1~
`4,634,966 A
`M987 Nfjgtlajirget 31
`436393779 A
`1/1987 Greenberg
`'
`4,677,455 A
`6/1987 Okajima
`4,677,466 A
`6/1987 Lert, Jr. et al.
`4,682,370 A
`7/1987 Matthews
`4,697,209 A
`9/1987 Klewlt
`4,739,398 A
`4/1988 Thomas et al.
`i
`322g
`
`’
`
`’
`
`_
`(Commued)
`
`OTHER PUBLICATIONS
`
`Peter N. Yianilos, Excluded Middle Vantage Point Forest for Nearest
`Neighbor Search, Aug. 1, 1999, pp. 1-12.*
`
`(Continued)
`
`Primary Examiner * Brian Pendleton
`Assistant Examiner * Cai Chen
`(74) Attorney, Agent, or Firm * Amster, Rothstein &
`Ebenstein LLP
`
`(57)
`
`ABSTRACT
`
`Amedia Work may be associated With an action by (a) extract
`ing features from the media Work, (b) determining an identi
`?cation of the media Work, based on the features extracted,
`using a sub-linear time search, such as an approximate nearest
`neighbor search for example, and (c) determining an action
`basedontheidenti?cationOfthemediaworkdeterminedThe
`media Work may be an audio Work The features extracted
`from the Work may include (A) a frequency decomposition of
`a signal of the audio Work, (B) information samples of the
`audio Work, (C) average intensities of sampled WindoWs of
`the audio Work, and/or (D) information from frequencies of
`the audio Work.
`
`40 Claims, 10 Drawing Sheets
`
`WORK an
`
`WORK an
`
`FEATURE
`snowman
`OPERATIONS
`
`FEATURES) (venom w ‘rm
`
`138
`
`AC‘HON
`wmmou
`OPERATIONS)
`
`no
`
`Google Ex. 1001
`
`
`
`>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
`
`US. PATENT DOCUMENTS
`6/1989
`4,843,526
`Price, 111
`Kenyon et al.
`6/1989
`4,843,562
`SchulZe
`4/1990
`4,918,730
`Kenyon
`5/1993
`5,210,820
`2/1994
`5,283,819
`Glick et al.
`5,437,050
`7/1995
`Lamb et al.
`5,481,294
`1/1996
`Thomas et al.
`O’Hagan et al.
`5,581,658
`12/1996
`5,594,934
`1/1997
`Lu et al.
`Dougherty
`5,629,739
`5/1997
`Goldberg et al.
`5,692,213
`11/1997
`5,701,452
`Siefert
`12/1997
`Sasayama
`5,701,542
`12/1997
`5,724,605
`Wissner
`3/1998
`5,745,900
`4/1998
`Burrows
`5,798,785
`8/1998
`Hendricks et al.
`5,850,490
`Johnson
`12/1998
`5,918,223
`6/1999
`Blum et al.
`5,953,415
`Nielsen
`9/1999
`Zdepski et al.
`6,006,256
`12/1999
`6,011,758
`1/2000
`Dockes et al.
`Chowdhury et al.
`6,026,439
`2/2000
`6,044,402
`3/2000
`Jacobson et al.
`6,052,693
`4/2000
`Smith et al.
`6,061,056
`5/2000
`Menard et al. .............. .. 715/704
`Logan et al.
`6,088,455
`7/2000
`6,088,707
`7/2000
`Bates et al.
`6,118,450
`9/2000
`Proehl et al.
`6,119,124
`9/2000
`Broder et al.
`6,169,986
`1/2001
`Bowman et al.
`Wang et al.
`6,173,406
`1/2001
`6,240,409
`Aiken
`5/2001
`Hempleman et al.
`6,243,725
`6/2001
`Palage et al.
`6,247,133
`6/2001
`6,253,193
`6/2001
`Ginter et al.
`6,263,348
`7/2001
`Kathrow et al.
`6,330,593
`12/2001
`Roberts et al.
`6,345,256
`2/2002
`Milsted et al.
`6,349,296
`Broder
`2/2002
`6,360,215
`3/2002
`Judd et al.
`6,363,377
`3/2002
`Kravets et al.
`Hejna, Jr.
`6,374,225
`4/2002
`Fujiwara et al.
`6,381,601
`4/2002
`6,385,596
`5/2002
`Wiser et al.
`6,408,128
`Abecassis
`6/2002
`6,418,421
`7/2002
`Hurtado et al.
`Kortge
`6,446,068
`9/2002
`Kumagai
`6,449,226
`9/2002
`6,452,874
`9/2002
`Otsuka et al.
`6,477,704
`Cremia
`11/2002
`6,496,802
`12/2002
`Van Zoest et al.
`Levy
`6,505,160
`1/2003
`6,550,001
`4/2003
`Corwin et al.
`6,550,011
`4/2003
`Sims, III
`6,577,746
`6/2003
`Evans et al.
`Klug
`6,591,245
`7/2003
`Hejna, Jr.
`6,598,228
`7/2003
`6,609,105
`8/2003
`Van Zoest et al.
`6,654,757
`11/2003
`Stern
`6,665,661
`12/2003
`Crow et al.
`6,675,174
`1/2004
`Bolle et al.
`6,834,308
`12/2004
`IkeZoye et al. .............. .. 709/231
`6,873,982
`3/2005
`Bates et al.
`6,931,451
`Logan et al.
`8/2005
`6,941,275
`SwiercZek
`9/2005
`6,978,419
`KantrowitZ
`12/2005
`6,978,461
`Shapiro et al.
`12/2005
`6,990,453
`Wang et al.
`1/2006
`7,013,301
`3/2006
`Holm et al.
`7,058,223
`6/2006
`Cox
`7,106,904
`Shima
`9/2006
`7,155,449
`Pingel et al.
`12/2006
`7,158,929
`1/2007
`Wouters et al.
`7,168,083
`1/2007
`Kalker et al.
`7,302,574
`11/2007
`Conwell et al.
`7,366,718
`Pugh et al.
`4/2008
`7,421,723
`9/2008
`Harkness et al.
`7,477,739
`1/2009
`Haitsma et al.
`
`US 8,205,237 B2
`Page 2
`
`4/2009 Kalker et al.
`7,523,312 B2
`9/2009 Wheeler et al.
`7,587,728 B2
`1/2010 Ramaswamy
`7,647,604 B2
`1/2010 Lee
`7,650,616 B2
`7/2010 Harkness et al.
`7,757,248 B2
`2001/0001160 A1* 5/2001 Shoff et al. ................... .. 725/51
`2001/0003818 A1
`6/2001 Pingel et al.
`2002/0023020 A1
`2/2002 Kenyon et al.
`2002/0032698 A1
`3/2002 Cox
`2002/0120925 A1
`8/2002 Logan
`2002/0156760 A1 10/2002 Lawrence et al.
`2003/0106017 A1
`6/2003 Kanchirayappa et al.
`2003/0146940 A1
`8/2003 Ellis
`2004/0199387 A1* 10/2004 Wang et al. ................. .. 704/243
`2005/0160363 A1
`7/2005 Bhogal et al.
`2006/0101069 A1
`5/2006 Bell et al.
`2006/ 0206462 A1
`9/2006 Barber
`2007/0041667 A1
`2/2007 Cox
`2007/0083510 A1
`4/2007 McArdle
`2007/0118375 A1
`5/2007 Kenyon et al.
`2008/0091684 A1
`4/2008 Ellis et al.
`2008/0250241 A1 10/2008 Ginter et al.
`
`OTHER PUBLICATIONS
`
`Peter N. Yianlos, Excluded Middle Vantage Point Forest for Nearest
`Neighbor Search, Aug. 1, 1999, pp. 1-12.*
`P.N.Yianilos, “Locally Lifting the Curse of Dimensionality for Near
`est Neighbor Search” SODA 2000, pp. 361-370.
`Baum, L., et al., “A Maximation Technique Occurring in the Statis
`tical Analysis of Probabilistic Functions of Markov Chains”, The
`Annals ofMathematicalStatistics, vol. 41,No. 1,pp. 164-171 (1970).
`Dempster, A. P., et al., “Maximum Likelihood from Incomplete Data
`via the $EM$ Algorithm”, Journal of the Royal Statistical Society,
`Series B (Methodological), vol. 39, Issue 1, pp. 1-38 (1977).
`Reynolds, D., et al., “Robust Text-Independent Speaker Identi?ca
`tion Using Gaussian Mixture Speaker Models”, IEEE Transactions
`on Speech andAudio Processing, vol. 3, No. 1, pp. 72-83 (Jan. 1995).
`Nievergelt, J. et al., “The Grid File: An Adaptable, Symmetric
`Multikey File Structure,” ACM Transactions on Database Systems,
`vol. 9, No. 1, pp. 38-71 (Mar. 1984).
`HeintZe, N, “Scalable Document Fingerprinting,” Proc. USENIX
`Workshop on Electronic Commerce (1996).
`Wold, E, et al., “Content-Based Classi?cation, Search, and Retrieval
`ofAudio,” IEEE Multimedia, vol. 3, Issue 3, pp. 27-63 (1996).
`Bhanu, B., et al., “Learning Feature Relevance and Similarity Metrics
`in Image Databases”, Proceedings of the IEEE Workshop on Con
`tent-Based Access of Image and Video Libraries, pp. 14-19 (1998).
`Del Bimbo, A., et al., “Using Weighted Spatial Relationships in
`Retrieval by Visual Contents”, Image Description and Retrieval, pp.
`161-192 (1998).
`Indyk, P., and Motwani, R., “Approximate Nearest Neighbors:
`Towards Removing the Curse of Dimensionality,” Proceeding of the
`Thirtieth Annual ACM Symposium on Theory of Computing, pp.
`604-613 (1998).
`La Cascia, M., et al., “Combining Textual and Visual Cues for Con
`tent-based Image Retrieval on the World Wide Web”, Proceedings of
`the IEEE Workshop on Content-Based Access of Image and Video
`Libraries, pp. 24-29 (1998).
`Yoshitaka, A., et al., “A Survey on Content-Based Retrieval for Mul
`timedia Databases”, IEEE Transactions on Knowledge and Data
`Engineering, vol. 11, No. 1, pp. 81-93 (Jan/Feb. 1999).
`Lawrence, S., et al., “Digital Libraries and Automonous Citation
`Indexing,” IEEE Computer, pp, 67-71 (Jun. 1999).
`Kimura, A, et al., “Very Quick Audio Searching: Introducing Global
`Pruning to the Time-Series Active Search,” IEEE Conf on Acoustics,
`Speech and Signal Processing, (ICASSP ’01), vol. 3, pp, 1429- 1432
`(2001).
`Chavez, E., et al., “Searching in Metric Spaces”, ACM Computing
`Surveys, vol. 33, No. 3, pp. 273-321 (Sep. 2001).
`Haitsma, J ., et al., “Robust Audio Hashing for Content Identi?cation,
`Int” Workshop on Content Based Multimedia Indexing, Brescia, Italy
`(Sep. 19-21, 2001).
`
`Google Ex. 1001
`
`
`
`US 8,205,237 B2
`Page 3
`
`Haitsma, J ., and Walker, T, “A Highly Robust Audio Fingerprinting
`System,” Journal ofNew Music Research, 1744-5027, vol. 32, Issue
`2, pp. 211-221 (2003).
`Schleimer, Saul, et al., “Winnowing: Local Algorithms for Document
`Fingerprinting ACM SIGMOD” (Jun. 9-12, 2003).
`“Searching Near-Replicas of Images via Clustering” Edward Chang,
`Chen Li, James Wang, Peter Mork, Gio Wiederhold Proc. SPIE
`Symposium of Voice, Video, and Data Communications, 1999.
`“RIME: A Replicated Image Detector for the World-Wide Web”
`EdwardY. Chang, James Ze Wang, Chen Li, and Gio Wiederhold,
`SPIE 1998.
`“Safeguarding and charging for information on the internet,” H.
`Garcia-Molina, S. Ketchpel, and N. Shivakumar, Proceedings of
`ICDE , 1998.
`“Detection mechanisms for digital documents,” S. Brin and H.
`Garcia-Molina, Proceedings of ACM SIG-MOD , May 1995.
`“The x-tree: An index structure for high-dimensional data,” S.
`Berchtold, Proceedings of the 22nd VLDB , Aug. 1996.
`“The sr-tree: An index structure for high-dimensional nearest neigh
`bor queries,” N. Katayama and S. Satoh, Proceedings of ACM
`SIGMOD , May 1997.
`“The k-d-b-tree: A search structure for large multidimensional
`dynamic indexes,” J. T. Robinson, Proceedings of ACM SIGMOD ,
`Apr. 1981.
`“Query by image and video content: The QBIC system,” M. Flickner,
`H. Sawhney, W. Niblack, J. Ashley, Q. Huang, and et al, IEEE
`Computer 28(9), pp. 23{32, 1995.
`“Visual information retrieval,” A. Gupta and R. Jain, Communica
`tions ofthe ACM 40(5), pp. 69-79, 1997.
`“Visualseek: A fully automated content-based image query system,”
`J. R. Smith and S.-F. Chang, ACM Multimedia Conference , 1996.
`“Similarity indexing: Algorithms and performance,” D. A. White and
`R. Jain, Proc. SPIE vol. 2670, San Diego, 1996.
`“The r*-tree: an ef?cient and robust access method, for points and
`rectangles,” N. Beckmann, H.-P. Kriegel, R. Schneider, and B.
`Seeger, Proceedings ofACM Sigmod , May 1990.
`“R-trees: a dynamic index structure for spatial searching,” A. Gutt
`man, Proceedings ofACM Sigmod , Jun. 1984.
`“Similarity indexing with the ss-tree,” D. A. White and R. Jain,
`Proceedings ofthe 12th ICDE , Feb. 1996.
`“The tv-tree: an index structure for high-dimensional data,” K.-L.
`Lin, H. V. Jagadish, and C. Faloutsos, VLDB Journal 3 (4), 1994.
`“M-tree: An ef?cient access method for similarity search in metric
`spaces,” P. Ciaccia, M. Patella, and P ZeZula, Proceedings of the 23rd
`VLDB , Aug. 1997.
`“Nearest neighbor queries,” N. Roussopoulos, S. Kelley, and F.
`Vincent, Proceedings ofACM Sigmod , May 1995.
`“An extensible hashing index for high-dimensional similarity
`search,” C. Li, E. Chang, and J. Z. Wang, Stanford Technical
`Report , Aug. 1998.
`“Two algorithms for nearest-neighbor search in high dimensions” J.
`M. Kleinberg, Proc 29th STOC, 1997.
`“A Density-Based Algorithm for Discovering Clusters in Large Spa
`tial Databases with Noise” Martin Ester, Hans-Peter Kriegel, Jorg
`Sander, Xiaowei Xu Proceedings of 2nd International Conference on
`Knowledge Discovery and Data Mining (KDD-96), 1996.
`“Adaptive Color Image Embeddings for Database Navigation”Yossi
`Rubner, Carlo Tomasi and Leonidas J. Guibas, Proceedings of the
`1998 IEEE Asian Conference on Computer Vision.
`A Quantitative Analysis and Performance Study for Similarity
`Search Methods in High-Dimensional Spaces R. Weber, H-J Schek,
`S. Blott Proc., 24th VLDB Conf. 1998.
`Bouktache, D, “A fast algorithm for the nearest neighbor classi?er”,
`IEEE Transactions on Pattern Analysis and Machine Intelligence,
`Mar. 1997, pp. 277-282.
`Nene et al., “A simple algorithm for nearest neighbor search in high
`dimensions”, IEEE Transactions on Pattern Analysis and Machine
`Intelligence; Sep. 1997, pp. 989-1003.
`Arya et al. “Approximate nearest neighbor queries in ?xed dimen
`sions”, Proceedings of the 4th annual ACM-SIAM Symposium on
`Discrete algorithms, 1993; pp. 271-280.
`
`K. Fukunaga and P M. Narendra. A branch and bound algorithm for
`computing k-nearest
`neighbors. IEEE Trans.
`Comput.,
`C-24:750{753, Jul. 1975.
`CD. Feustel and L. G. Shapiro. The nearest neighbor problem in an
`abstract metric space. Pattern Recognition Letters, pp. 125 { 128, Dec.
`1982.
`Dennis Shasha and Tsong-Li Wang. New techniques for best-match
`retrieval. ACM Transactions on Information Systems, 8(2): 140{ 158,
`Apr. 1990.
`J. Uhlmann. Satisfying general proximity/ similarity queries with
`metric trees. Information Processing Letters, 40 (4): 175{9, Nov.
`1991.
`Sergey Brin, “Near Neighbor Search in Large Metric Spaces”, Pro
`ceedings of the 21st VLDB Conference, Zurich, Switzerland, Sep.
`1995.
`D. P. Huttenlocher, et al. Comparing images using the hausdorff
`distance. IEEE Transactions on Pattern Analysis and Machine Intel
`ligence, 15(3):850{63, Sep. 1993.
`Seidl et al. “Optimal multi-step k-nearest neighbor search”, Proceed
`ings of ACM SIGMOD international conference on Managemet of
`data, 1998, pp. 154-165.
`W.A. Burkhard and RM. Keller. Some Approaches to Best-Match
`File Searching. Communications of the ACM. vol. 16, No. 4, Apr.
`1973.
`KushilevitZ et al. “Ef?cient search for approximate nearest neighbor
`in high dimensional spaces”, Proceedings of the 30th annual ACM
`Symposium on Theory of computing, 1998, pp. 614-623.* ;annual
`ACM Symposium on Theory of computing, 1998, pp. 614-623.
`Yianilos, P, “Data structures and algorithms for nearest neighbor
`search in general metric spaces”, Proceedings of the ACM-SIAM
`Symposium on Discrete algorithms, 1993, pp. 311-321.
`ArdiZZone, Edoardo et al., “Motion and Color-Based Video Indexing
`and Retrieval,” Universita di palermo, Departimento di Ingegneria
`Elettrica, pp. 135-139, Viale delle ScienZe, Palermo, Italy, IEEE
`1996.
`Deng, Yining et al., “Content-based Search of Video Using Color,
`Texture, and Motion,” Dept. of Electrical and Computer Engineering,
`University of California, Santa Barbara, CA, pp. 534-537, IEEE
`1997.
`Fang, Min et al., “Computing Iceberg Queries Ef?ciently,” Dept. of
`Computer Science, Stanford, CA, Paper No. 234, pp. 1-25.
`Flickner, Myron et al., “Query by Image and Video Content: The
`QBIC System,” IBM Almaden Research Center, Sep. 1995, pp.
`23-32, IEEE 1995.
`Gargi, U et al., “Performance Characterization and Comparison of
`Video Indexing Algorithms,” Dept. of Computer Science and Engi
`neering, The Pennsylvania State University, University Park, PA.
`Gionis, Aristides et al., “Similarity Search in High Demensions via
`Hashing,” Dept. of Computer Science, Stanford University, Stanford,
`CA, pp. 518-529, Proceeding the 25th VLDB Conference,
`Edinburgh, Scotland, 1999.
`Indyk, Piotr et al., “Approximate Nearest Neighbors: Towards
`Removing the Curse of Dimensionality” (preliminary version) Dept.
`of Computer Science, Stanford University, Stanford, CA, pp. 1-13 &
`i-vii, Jul. 21, 1999.
`Iyengar, Giridharan et al., “Models for automatic classi?cation of
`video sequences,” MIT Media Laboratory, Cambridge, MA.
`Jain, Anil K., et al., “Image Retrieval using Color and Shape,” Dept.
`of Computer Science, Michigan State University, Eas Lansing, MI,
`pp. 1-24, May 15, 1995.
`Ogle, Virginia E., et al., “Chabot: Retrieval from a Relational Data
`base of Images,” University of California at Berkeley, Computer pp.
`40-48, IEEE 1995.
`Pentland, A. et al., “Photobook: Content-Based Manipulation of
`Image Databases,” Perceptual Computing Section, The Media Labo
`ratory, Massachusetts Institute of Tech., International Jorunal of
`ComputerVision 18(3), pp. 233-254 (1996), 1996 KluwerAcademic
`Publishers. Manuf. in The Netherlands.
`Shivakumar, Narayanan et al., “SCAM: A Copy Detection Mecha
`nism for Digital Documents,” Dept. of Computer Science, Stanford
`University, Stanford, CA, pp. 1-13.
`
`Google Ex. 1001
`
`
`
`US 8,205,237 B2
`Page 4
`
`Shivakumar, Narayanan et al., “Building a Scalable and Accurate
`Copy Detection Mechanism,” Dept. of Computer Science, Stanford
`University, Stanford, CA.
`Srihari, Rohiini K., “Automatic Indexing and Content-Based
`Retrieval of Captioned Images,” State University of NeWYork, Buf
`falo, Theme Feature, pp. 49-56, Sep. 1995, IEEE 1995.
`Swain, Michael and Ballard, Dana H., “Color Indexing,” Interna
`tional Journal ofComputerVision 7:1, p. 11-32 (1991), 1991 Kluwer
`Academic Publishers. Manuf. in The Netherlands.
`Wactlar, Howard D. et al., “Intelligence Access to Digital Video:
`Informedia Project,” Carnegie Mellon University, Digital Library
`
`Initiative: Carnegie Mellon University, Computer, pp. 46-52, IEEE
`1996.
`Yeo, Boon-Lock et al., “Rapid Scene Analysis on Compressed
`Video,” IEEE Transactions on Circuits and Systems for Video Tech
`nology, vol. 5, No. 6, pp. 533-544, Dec. 1995, Dept. of Electrical
`Engineering, Princeton University, Princeton, NJ, IEEE Log No.
`9415901.
`Indyk, Piotr et al., “Finding pirated video sequences on the Internet,”
`Dept. of Computer Science, Stanford University, Palo Alto, CA,
`Paper No. 199.
`
`* cited by examiner
`
`Google Ex. 1001
`
`
`
`US. Patent
`
`Jun. 19, 2012
`
`Sheet 1 0110
`
`US 8,205,237 B2
`
`WORK @t1
`
`WORK @t2
`
`FEATURE
`EXTRACTION
`OPERATIONS
`
`FEATURE TO
`WORK ID
`TAGGING
`OPERATION(S
`
`124
`
`FEATURE
`(VECTOR) EXTRACTION
`OPERAT|ON(S)
`
`140
`
`DATABASE
`GENERATION
`OPERAT|ON(S)
`
`150
`
`FEATURE
`(VECTOR) LOOKUP
`OPERAT|ON(S)
`
`160
`
`WORK-ASSOCIATED
`INFORMATION LOOKUP
`OPERATION(S)
`
`FEATURE(S) (VECTOR) WORK ID @112
`
`DATABASE
`GENERATION
`OPERAT|ON(S)
`
`WID-ACTION
`INFORMATION
`
`WORK ID ASSOCIATED INFORMATION (e,g., ACTION) ‘J\ E
`
`ACTION
`INITIATION
`OPERATION(S)
`
`170
`
`100
`FIGURE 1
`
`Google Ex. 1001
`
`
`
`US. Patent
`
`Jun. 19, 2012
`
`Sheet 2 0f 10
`
`US 8,205,237 B2
`
`SATELLITE CABLE
`OR TERRESTRIAL
`TV BROADCAST
`
`USER COMPUTER,
`SET-TOP-BOX OR
`EQUIVALENT
`
`110a
`
`WID
`DATABASE
`
`T T )T A U IA
`
`
`EIIN EO/\ D IO
`
`ANumw Wow N NWW
`
`
`
`RDOATO ROW EDP ET“ 0
`NCAA TRA IAMAK wAIHR 2
`
`P )
`
`DATABASE
`
`vS
`
`FIGURE 2
`
`
`
`
`
`
`
`
`
`HP FCP %mL 0
`
`120a/138a
`
`' DATABASE
`GENERATION
`OPERATIONS
`
`E % mm M D
`
`WIDAT
`DATABASE
`
`Google Ex. 1001
`
`
`
`US. Patent
`
`Jun. 19, 2012
`
`Sheet 3 0f 10
`
`US 8,205,237 B2
`
`SATELLITE, CABLE |— _ _ _ — _ _ _ _|
`
`320 _
`
`OR TERRESTRIAL
`TVBROADCAST
`
`USER COMPUTER,
`SET-TOP-BOX OR
`EQUIVALENT
`
`FEATURE
`(VECTOR)
`EXTRACTION
`OPERATION(S
`
`FEATURE
`(VECTOR) LOOKUP
`OPERATION(S)
`
`110b
`
`WI D
`DATABASE
`
`ACTION
`INITIATION
`OPERATION(S)
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`MONITORINFCENER
`
`DATABASE
`GENERATION
`OPERATION(S)
`
`WORK-ASSOCIATED
`INFORMATION LOOKUP
`OPERAT|ON(S)
`
`16Gb
`
`1 1 Oh’
`
`I
`I
`
`WID
`DATABASE
`
`WIDAT
`DATABASE
`
`FIGURE 3
`
`340
`
`Google Ex. 1001
`
`
`
`US. Patent
`
`Jun. 19, 2012
`
`Sheet 4 0f 10
`
`US 8,205,237 B2
`
`SATELLITE, CABLE
`OR TERRESTRIAL
`TV BROADCAST
`
`420
`
`'- —— —_ _ _ _ _ _ — ‘I
`
`I
`
`USER COMPUTER
`SET-TOP-BOX OR
`EQUIVALENT
`
`1700
`
`1400
`
`INITIATION
`OPERATION(S)
`
`FEATURE
`(VECTOR)
`EXTRACTION
`
`|
`|
`|
`|
`l
`
`|
`|
`|
`
`FEATURE
`(VECTOR) LOOKUP
`OPERATION(S)
`
`WORK-ASSOCIATED
`INFORMATION LOOKUP
`OPERATION(S)
`
`DATABASE
`GENERATION
`OPERATION(S)
`
`110C
`
`WID
`DATABASE
`
`Wl DAT
`DATABASE
`
`130C
`
`MONITORING CENTER
`
`FIGURE 4
`
`Google Ex. 1001
`
`
`
`US. Patent
`
`Jun. 19, 2012
`
`Sheet 5 0f 10
`
`US 8,205,237 B2
`
`WORK
`WORK (WITH
`EXTRA-WORK ,q
`INFOMRATION)
`
`FEATURE
`(VECTOR) EXTRACTION
`OPERATION(S)
`
`REAL-TIME (CENTRALIZED) MONITORING
`
`EXTRA-WORK
`INFORMATION
`
`FEATURE (VECTOR) LOOKUP
`
`OPERATION(S)
`
`INFORMATION
`I594
`RELATEDTOWORK 596‘
`EXTRA-WORK WORK
`INFORMATION
`ID
`
`‘7
`
`I
`
`‘
`
`114d 116d
`
`" FEATuRE(s) WORK‘
`(VECTQR)
`|D
`_
`.
`
`\’\
`M
`
`EXTRA-WORK INFORMATION
`AGGREGATION OPERAT|ON(S)
`
`DATABASE
`GENERATION
`OPERATION(S
`
`580
`
`2
`5 o
`
`510
`
`LOOKUP
`OPERATION(S)
`
`QWID
`INFORMATION
`------ " m ?x‘ ‘‘‘‘ __
`
`EXTRA-WORK
`.
`INFORMATION (VECTOR) WORK "3 w
`
`WORK-ASSOCIATED
`INFORMATION LOOKUP
`0PERAT|ON(S)
`
`DATABASE
`GENERATION
`OPERAT|ON(S)
`
`WIDAT
`INFORMATION
`
`ASSOCIATED INFORMATION (e.g., ACTION) I Q
`
`Lg
`
`570
`
`EJ‘
`FIGURES
`
`Google Ex. 1001
`
`
`
`US. Patent
`
`Jun. 19, 2012
`
`Sheet 6 0f 10
`
`US 8,205,237 B2
`
`SATELLITE, CABLE
`OR TERRESTRIAL
`TV BROADCAST
`
`|
`
`620
`
`F
`
`-
`
`USER COMPUTER
`SET-TOP-BOX OR
`EQUIVALENT
`
`.
`
`Q12
`
`I‘
`
`540a
`l
`EXTRA-WORK INFORMATION
`AGGREGATION OPERATION(S)
`
`570a
`
`INITIATION
`OPERATION(S)
`
`I
`I
`I
`I
`I
`I
`I
`
`I
`I
`I
`
`WORK-ASSOCIATED
`INFORMATION LOOKUP
`OPERATION(S)
`
`WID
`DATABASE
`
`1 1o
`e
`
`QWI D
`DATABASE
`
`5208/5383
`
`DATABASE
`GENERATION
`OPERATION(S
`
`DATABASE
`
`MONITORING AND QUERY RESOLUTION CENTER
`
`64;
`
`FIGURE 6
`
`Google Ex. 1001
`
`
`
`US. Patent
`
`Jun. 19, 2012
`
`Sheet 7 0f 10
`
`US 8,205,237 B2
`
`720
`
`SATELLITE, CABLE
`OR TERRESTRIAL
`TV BROADCAST
`
`I_L.ISER COMPUTER, SET-TOP-BOX OR EQUIVALEN
`
`EXTRA-WORK INFORMATION
`AGGREGATION OPERATION(S)
`
`ACTION
`INITIATION
`OPERAT|ON(S)
`
`v
`
`. P
`
`_ . §
`
`O D
`
`P A
`
`_ W_.Nr D%P 0
`
`F UO E Y_
`OM D% E
`PN R
`K“ S R
`0 WA U
`.LE QT Q
`
`O | 0 %
`
`ARA T RRO TER U 0 O A N E L
`
`AmAR AAD O E B T l KMP
`
`— ONm NS .E
`
`
`.7 EK DB R
`\. DU MA
`.. TO\SI IM E
`
`
`
`S O T E o /N.\ C
`
`CLN D N_
`
`T
`
`74Ob\,\l
`l
`|_
`
`l
`|
`OPTIONAL
`I
`PRIVATE
`I NETWORK
`
`|
`l
`|
`
`WID
`DATABASE
`
`DATABASE
`GENERATION
`OPERATION(S
`
`IJQJOEG @TER
`_‘ _l
`F|GURE7
`
`740a
`
`Google Ex. 1001
`
`
`
`US. Patent
`
`Jun. 19, 2012
`
`Sheet 8 0f 10
`
`US 8,205,237 B2
`
`SATELLITE, CABLE
`OR TERRESTRIAL
`TV BROADCAST
`
`a
`
`:
`
`860
`
`SATELLITE TV BROADCAST
`
`MONITORING I
`
`CENTER
`
`840a
`
`810
`
`\,\
`
`HOME VIEWERS
`
`830 J
`
`812
`
`84Gb
`
`DATABASE
`CENTER
`
`850 \q E-COMMERCE
`OR OTHER WEB
`S|TE
`
`00
`
`FIGURE 8
`
`Google Ex. 1001
`
`
`
`US. Patent
`
`Jun. 19, 2012
`
`Sheet 9 0f 10
`
`US 8,205,237 B2
`
`m wmDOE
`
`mwomr H: vEO>>
`
`
`
`woum USE. A
`
`
`
`mwmmp. un: vEO>>
`
`36 M22.
`
`
`
`Emit-2mm: vEO>>
`
`Google Ex. 1001
`
`
`
`US. Patent
`
`Jun. 19, 2012
`
`Sheet 10 0f 10
`
`US 8,205,237 B2
`
`UNIQUE ID: 15642
`
`\1\ 1010
`
`PRODUCT: COCA COLA
`
`\I\ 1020
`
`CATEGORY: SODA
`
`\.r\ 1030
`
`MANUFACTURER: COCA COLA
`
`\I\ 1040
`
`URL http://www.cocacola.com
`
`\J\ 1050
`
`OTHER DATA
`
`\r\ 1060
`
`100
`
`FIGURE 10
`
`Google Ex. 1001
`
`
`
`US 8,205,237 B2
`
`1
`IDENTIFYING WORKS, USING A
`SUB-LINEAR TIME SEARCH, SUCH AS AN
`APPROXIMATE NEAREST NEIGHBOR
`SEARCH, FOR INITIATING A WORK-BASED
`ACTION, SUCH AS AN ACTION ON THE
`INTERNET
`
`§0. RELATED APPLICATIONS
`
`The present application is a continuation of US. patent
`application Ser. No. 11/445,928 (incorporated herein by ref
`erence), titled “USING FEATURES EXTRACTED FROM
`AN AUDIO AND/ OR VIDEO WORK TO OBTAIN INFOR
`MATION ABOUT THE WORK,” ?led on Jun. 2, 2006, and
`listing Ingemar J. Cox as the inventor, Which is a continua
`tion-in-part of US. patent application Ser. No. 09/950,972
`(incorporated herein by reference, issued as US. Pat. No.
`7,058,223 on Jun. 6, 2006), titled “IDENTIFYING WORKS
`FOR INITIATING A WORK-BASED ACTION, SUCH AS
`AN ACTION ON THE INTERNET,” ?led on Sep. 13, 2001,
`now US. Pat. No. 7,058,223 and listing Ingemar J. Cox as the
`inventor, Which application claims bene?t to the ?ling date of
`provisional patent application Ser. No. 60/232,618 (incorpo
`rated herein by reference), titled “Identifying and linking
`television, audio, print and other media to the Internet”, ?led
`on Sep. 14, 2000 and listing Ingemar J. Cox as the inventor.
`
`20
`
`25
`
`§1. BACKGROUND OF THE INVENTION
`
`§1.1 Field of the Invention
`The present invention concerns linking traditional media to
`neW interactive media, such as that provided over the Internet
`for example. In particular, the present invention concerns
`identifying a Work (e.g., content or an advertisement deliv
`ered via print media, or via a radio or television broadcast)
`Without the need to modify the Work.
`§1.2 Related Art
`§1.2.1 Opportunities Arising from Linking Works Deliv
`ered V121 Some Traditional Media Channel or Conduit to a
`More Interactive System
`The rapid adoption of the Internet and associated World
`Wide Web has recently spurred interest in linking Works,
`delivered via traditional media channels or conduits, to a
`more interactive system, such as the Internet for example.
`Basically, such linking can be used to (a) promote commerce,
`such as e-commerce, and/ or (b) enhance interest in the Work
`itself by facilitating audience interaction or participation.
`Commerce opportunities include, for example, facilitating
`the placement of direct orders for products, providing product
`coupons, providing further information related to a product,
`product placement, etc.
`In the context of e-commerce, vieWers could request dis
`count vouchers or coupons for vieWed products that are
`redeemable at the point of purchase. E-commerce applica
`tions also extend beyond advertisements. It is noW common
`for television shoWs to include product placements. For
`example, an actor might drink a Coke rather than a Pepsi
`brand of soda, actors and actresses might Wear designer
`labeled clothing such as Calvin Klein, etc. Viewers may Wish
`to purchase similar clothing but may not necessarily be able to
`identify the designer or the particular style directly from the
`shoW. HoWever, With an interactive capability, vieWers Would
`be able to discover this and other information by going to an
`associated Web site. The link to this Web site can be auto
`matically enabled using the invention described herein.
`In the context of facilitating audience interaction or par
`ticipation, there is much interest in the convergence of tele
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`vision and computers. Convergence encompasses a very Wide
`range of capabilities. Although a signi?cant effort is being
`directed to video-on-demand applications, in Which there is a
`unique video stream for each user of the service, as Well as to
`transmitting video signals over the Internet, there is also
`interest in enhancing the television vieWing experience. To
`this end, there have been a number of experiments With inter
`active television in Which vieWers can participate in a live
`broadcast. There are a variety of Ways in Which vieWers can
`participate. For example, during game shoWs, users can
`ansWer the questions and their scores can be tabulated. In
`recent reality-based programming such as the ABC television
`game shoW, “Big Brother”, vieWers can vote on contestants
`Who must leave the shoW, and be eliminated from the com
`petition.
`§1.2.2 Embedding Work Identifying Code or Signals
`Within Works
`Known techniques of linking Works delivered via tradi
`tional media channels to a more interactive system typically
`require some type of code, used to identify the Work, to be
`inserted into the Work before it is delivered via such tradi
`tional media channels. Some examples of such inserted code
`include (i) signals inserted into the vertical blanking interval
`(“VBI”) lines of a (e.g., NTSC) television signal, (ii) Water
`marks embedded into images, (iii) bar codes imposed on
`images, and (iv) tones embedded into music.
`The common technical theme of these proposed imple
`mentations is the insertion of visible or invisible signals into
`the media that can be decoded by a computer. These signals
`can contain a variety of information. In its most direct form,
`the signal may directly encode the URL of the associated Web
`site. However, since the alphanumeric string has variable
`length and is not a particularly ef?cient coding, it is more
`common to encode a unique ID. The computer then accesses
`a database, Which is usually proprietary, and matches the ID
`With the associated Web address. This database can be con
`sidered a form of domain name server, similar to those
`already deployed for netWork addresses. HoWever, in this
`case, the domain name server is proprietary and the addresses
`are unique ID’s.
`There are tWo principal advantages to encoding a propri
`etary identi?er into content. First, as previously mentioned, it
`is a more e?icient use of the available bandWidth and second,
`by directing all tra?ic to a single Web site that contains the
`database, a company can maintain control over the technol
`ogy and gather useful statistics that may then be sold to
`advertisers and publishers.
`As an example of inserting signals into the vertical blank
`ing interval lines of a television signal, RespondTV of San
`Francisco, Calif. embeds identi?cation information into the
`vertical blanking interval of the television signal. The VBI is
`part of the analog video broadcast that is not visible to tele
`vision vieWers. For digital television, it may be possible to
`encode the information in, for example, the motion picture
`experts group (“MPEG”) header. In the USA, the vertical
`blanking interval is currently used to transmit close-caption
`ing information as Well as other information, While in the UK,
`the VBI is used to transmit teletext information. Although the
`close captioning information is guaranteed to be transmitted
`into the home in America, unfortunately, other information is
`not. This is because oWnership of the vertical blanking inter
`val is disputed by content oWners, broadcasters and local
`television operators.
`As an example of embedding Watermarks into images,
`Digimarc of Tualatin, Oreg. embeds Watermarks in print
`media. Invisible Watermarks are neWer than VBI insertion,
`and have the advantage of being independent of the method of
`
`Google Ex. 1001
`
`
`
`US 8,205,237 B2
`
`3
`broadcast. Thus, once the information is embedded, it should
`remain readable Whether the video is transmitted in NTSC,
`PAL or SECAM analog formats or neWer digital formats. It
`should be more reliable than using the vertical blanking inter
`val in television applications. Unfortunately, hoWever, Water
`marks still require modi?cation of the broadcast signal Which
`is problematic for a number of economic, logistical, legal
`(permission to alter the content is needed) and quality control
`(the content may be degraded by the addition of a Watermark)
`reasons.
`As an example of imposing bar codes on images, print
`advertisers are currently testing a technology that alloWs an
`advertisement to be shoWn to a camera, scanner or bar code
`reader that is connected to a personal computer (“PC”). The
`captured image is then analyZed to determine an associated
`Web site that the PC’s broWser then accesses. For example,
`GoCode of Draper, Utah embeds small tWo-dimensional bar
`codes for print advertisements. The latter signal is read by
`inexpensive barcode readers that can be connected to a PC.
`AirClic of Blue Bell, Pa. provides a combination of barcode
`and Wireless communication to enable Wireless shopping
`through print media. A so-called “CueCat” reads bar codes
`printed in conjunction With advertisements and articles in
`Forbes magaZine. Similar capabilities are being tested for
`television and audio media.
`Machine-readable bar codes are one example of a visible
`signal. The advantage of this technology is that it is very
`mature. HoWever, the fact that the signal is visible is often
`considered a disadvantage since it may detract from the aes
`thetic of the Work delivered via a traditional media channel or
`conduit.
`As an example of embedding tones into music, Digital
`Convergence of Dallas, Tex. proposes to embed identi?cation
`codes into audible music tones broadcast With television sig
`nals.
`All the foregoing techniques of inserting code into a Work
`can be categorized as active techniques in that they must alter
`the existing signal, Whether it is music, print, television or
`other media, such that an identi?cation code is also present.
`There are several disadvantages that active systems share.
`First, there are aesthetic or ?delity issues associated With bar
`codes, audible tones and