`FOR THE DISTRICT OF MASSACHUSETTS
`
`CANON, INC., CANON U.S.A., INC.
`AND AXIS COMM. AB,
`Plaintiffs,
`
`v.
`
`A VIGILON FORTRESS
`CORPORATION,
`Defendant.
`
`Civil Action No. 1 :19-MC~91401-NMG(cid:173)
`JCB
`
`DECLARATION OF KATHERINE ZIMMERMAN
`
`I, Katherine Zimmerman state and declare as follows:
`
`1. I am a Scholarly Communications and Licensing Librarian at the Massachusetts
`
`Institute of Technology ("MIT") Libraries, 105 Broadway, Building NE36, Suite
`
`6101, Cambridge, Massachusetts 02142.
`
`2. I am over 18 years of age and am competent to make this Declaration. I make this
`
`Declaration based on my own personal knowledge, based on my knowledge and
`
`review of the business records and practices of the MIT Libraries, based _on
`
`conversations with other library staff, and based on the notes and records of
`
`Marilyn Mcsweeney who prepared Declarations until her retirement in 2016.
`
`3. I have been employed at MIT since 2016.
`
`4. Through the actions described in paragraph 2, I have become knowledgeable
`
`about the MIT Libraries' normal business practices with respect to how MIT
`
`receives, catalogs, indexes, shelves, and makes available to the public student
`
`theses.
`
`855802.vl
`
`Canon Ex. 1054 Page 1 of 104
`
`
`
`5. Attached as Exhibit A to this Declaration is a true and accurate copy of the
`
`catalog record in standard format from the MIT Libraries' online catalog system
`
`(known as the Barton Catalog) for the thesis . titled "Visual Memory" by
`
`Christopher James Kellogg (the "Kellogg Thesis"). This is a record that MIT
`
`maintains in the ordinary course of its regular activities.
`
`6. Attached as Exhibit B to this Declaration is a true and accurate copy of the
`
`catalog record in MARC tags format from the Barton Catalog for the Kellogg
`
`Thesis. This is a record that MIT maintains in the ordinary course of its regular
`
`activities.
`
`7. Attached as Exhibit C to this Declaration is a true and accurate copy of the
`
`Kellogg Thesis. The Kellogg Thesis, which is 92 pages in length, is available in
`
`its entirety from the MIT Libraries. It can also be viewed at the following URL:
`
`http ://hdl.handle.net/1721.1/108869. The Kellogg Thesis is a record that MIT
`
`maintains in the ordinary course of its regular activities.
`
`8. The cover page of the original printed copy of the Kellogg Thesis has an MIT
`
`Libraries date stamp of "JUL 091993" indicating that the MIT Libraries received
`
`this thesis on July 9, 1993.
`
`9. Once a thesis has been received by the MIT Libraries, the original print copy is
`
`sent to the Archives of the MIT Libraries, at which point any member of the
`
`public may, if they know of the existence of the specific thesis by name, request
`
`to view a copy of it.
`
`10. The Kellogg Thesis has a cat~loging date of September 28, 1993 (shown as
`
`930928 in line number 008 of Exhibit B), indicating it was entered into OCLC,
`
`855802.vl
`
`2
`
`Canon Ex. 1054 Page 2 of 104
`
`
`
`the national bibliographic utility in which MIT does its cataloging, on September
`
`28, 1993.
`
`11. One to three business days after a thesis receives a cataloging date in the MIT
`
`Libraries, a record of its existence will appear in the list of results of a relevant
`
`search of the MIT Libraries' collections via the Barton Catalog.
`
`12. The Barton Catalog is available online to any user of the World Wide Web. Prior
`
`to the creation of the Web, access to the records in the Barton Catalog was limited
`
`to people who were on the MIT campus or otherwise had access to the OCLC
`
`database.
`
`13. Based on the practices in place at the time, the Kellogg Thesis would have
`
`appeared in a relevant Barton Catalog search conducted one to three business days
`
`after September 28, 1993.
`
`14. From June 1987 through June 1995, the Barton Catalog allowed for keyword-in(cid:173)
`
`title searching only. From June 1995 until July 2001, the Barton Catalog allowed
`
`for keyword searching for words in the thesis title and thesis notes (thesis notes
`
`consist of University, Department, and Program names). From July 2001 to the
`
`present, the Barton Catalog has allowed keyword searching for a number of fields,
`
`including author, title, thesis supervisor, degree, and department. Exact author and
`
`title searching has always been available.
`
`15. After a thesis receives a cataloging date in the MIT Libraries, any member of the
`
`public may request and purchase a copy of it from MIT.
`
`16. After being cataloged in OCLC, a thesis undergoes a process of being labeled and
`
`moved to a shelf of the MIT Libraries. This process typically takes two to four
`
`855802.vl
`
`3
`
`Canon Ex. 1054 Page 3 of 104
`
`
`
`weeks. According to MIT's nomial business practice at the time, the Kellogg
`
`Thesis would have been displayed on a shelf of the MIT Libraries no later than
`
`December 28, 1993.
`
`1 7. Once shelved in the MIT Libraries, a thesis can be borrowed by a member of the
`
`MIT community, and a copy can be purchased by any member of the public.
`
`18. On May 11, 2017 the entire Kellogg Thesis was made available for viewing on
`
`MIT's online database known as DSpace.
`
`19. To the best of my knowledge and that of current MIT employees, unless stated
`
`otherwise, the above statements are descriptions of normal business practices at
`
`the MIT Libraries from at least 1993 and through the present.
`
`I declare under penalty of perjury that the foregoing is true and correct. Executed on
`
`October __Juz_, 2019, at Cambridge, Massachusetts.
`
`855802.vl
`
`4
`
`Canon Ex. 1054 Page 4 of 104
`
`
`
`
`
`EXHIBIT A
`EXHIBIT A
`
`Canon Ex. 1054 Page 5 of 104
`
`Canon Ex. 1054 Page 5 of 104
`
`
`
`MIT Libraries' catalog - Barton - Full Catalog - Full Record
`
`http://library.mit.edu/F/8UYH8LSKVQFL4E66H3ML3283NA8FL82L...
`
`Search Full Catalog:
` • Basic
` • Advanced
`
`Search only for:
` • Conferences
` • E-resources
`
` • Journals
` • MIT Theses
`
`• Reserves
`• more...
`
`• Your Account
`• Help with Your Account
`
`• Your Bookshelf
`• Previous Searches
`
`MIT Libraries
`
`Other Catalogs
`
`Help
`
`Full Record
`
`Permalink for this record: http://library.mit.edu/item/000656176
`
`Results List | Add to Bookshelf | Save/Email
`
`Choose
`format:
`
`Standard | Citation |
`
`MARC
`tags
`
`Record 1 out
`of 1
`
`Author Kellogg, Christopher James.
`Title Visual memory / by Christopher James Kellogg.
`Online Access
` Click button for available online volumes
`Shelf Access Find it in the library/Request item
`Shelf Location Institute Archives - Noncirculating Collection 1 | Thesis E.E. 1993 M.S.
`Shelf Location Institute Archives - Noncirculating Collection 3 | Thesis E.E. 1993 M.S.
`Shelf Location Barker Library - Microforms | Thesis E.E. 1993 M.S.
`
`Published ©1993.
`Description 92 leaves : illustrations ; 29 cm
`Format Book
`Thesis Note M.S., Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1993.
`Thesis Supervisor Supervised by Alex P. Pentland.
`Bibliography Includes bibliographical references (leaves 90-92).
`Abstract Visual memory supports computer vision applications by efficiently storing and retrieving spatiotemporal
`information. It is a unique combination of databases, spatial representation and indexing, and temporal
`representation and indexing. This thesis designs a visual memory architecture that meets the requirements
`of a number of computer vision applications. It also presents an implementation of part of this design in
`support of a scene monitoring prototype.
`Other Author Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.
`Local System Number 000656176
`
`Basic Search of Full Catalog
`Search type:
`
`Search for:
`
`1 of 2
`
`10/8/2019, 11:46 AM
`
`Canon Ex. 1054 Page 6 of 104
`
`
`
`MIT Libraries' catalog - Barton - Full Catalog - Full Record
`
`http://library.mit.edu/F/8UYH8LSKVQFL4E66H3ML3283NA8FL82L...
`
`Barton Questions: Ask Us! | Contact Us
`Massachusetts Institute of Technology
`77 Massachusetts Avenue, Cambridge, MA 02139-4307 USA
`
`© 2003 Massachusetts Institute of Technology
`
`2 of 2
`
`10/8/2019, 11:46 AM
`
`Canon Ex. 1054 Page 7 of 104
`
`
`
`
`
`EXHIBIT B
`EXHIBIT B
`
`Canon Ex. 1054 Page 8 of 104
`
`Canon Ex. 1054 Page 8 of 104
`
`
`
`MIT Libraries' catalog - Barton - Full Catalog - Full Record
`
`http://library.mit.edu/F/8UYH8LSKVQFL4E66H3ML3283NA8FL82L...
`
`Search Full Catalog:
` • Basic
` • Advanced
`
`Search only for:
` • Conferences
` • E-resources
`
` • Journals
` • MIT Theses
`
`• Reserves
`• more...
`
`• Your Account
`• Help with Your Account
`
`• Your Bookshelf
`• Previous Searches
`
`MIT Libraries
`
`Other Catalogs
`
`Help
`
`Full Record
`
`Permalink for this record: http://library.mit.edu/item/000656176
`
`Results List | Add to Bookshelf | Save/Email
`
`Choose
`format:
`
`Standard | Citation |
`
`MARC
`tags
`
`Record 1 out
`of 1
`FMT
`BK
`LDR
` ctm 2200277Ka 4500
`005
`20180227072504.0
`008
`930928s1993 xx a bm 000 0 eng d
`035
`|a (OCoLC)28904769
`040
`|a MYG |b eng |c MYG |d OCLCQ |d MYG
`1001 |a Kellogg, Christopher James.
`24510 |a Visual memory / |c by Christopher James Kellogg.
`260
`|c ©1993.
`300
`|a 92 leaves : |b illustrations ; |c 29 cm
`336
`|a text |b txt |2 rdacontent
`337
`|a unmediated |b n |2 rdamedia
`338
`|a volume |b nc |2 rdacarrier
`502
`|b M.S. |c Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science |d 1993
`504
`|a Includes bibliographical references (leaves 90-92).
`|a Visual memory supports computer vision applications by efficiently storing and retrieving spatiotemporal information.
`It is a unique combination of databases, spatial representation and indexing, and temporal representation and indexing.
`This thesis designs a visual memory architecture that meets the requirements of a number of computer vision
`applications. It also presents an implementation of part of this design in support of a scene monitoring prototype.
`59900 |a Supervised by Alex P. Pentland.
`7102 |a Massachusetts Institute of Technology. |b Department of Electrical Engineering and Computer Science.
`85641 |u http://hdl.handle.net/1721.1/108869
`CAT
`|a CONV |b 00 |c 20010620 |l MIT01 |h 1525
`CAT
`|a lti0904 |b 00 |c 20090523 |l MIT01 |h 2117
`CAT
`|a dspace |b 00 |c 20170621 |l MIT01 |h 1432
`CAT
`|a RCHALL |b 00 |c 20180226 |l MIT01 |h 1543
`CAT
`|a loader |b 00 |c 20180227 |l MIT01 |h 0725
`CAT
`|a lti_week |b 00 |c 20180302 |l MIT01 |h 1920
`049
`|a MYGG
`|a rch180226 |b mod |c recat |e thesis |j t |k m |l blank |m K |o a |p MYG |q vt |r a |s 1 |w i |x 1 |y ~ |z ~ |i rch |d
`180226
`949 1 |1 Internet Access |a N |b NET |h **See URL(s) |o 8 |x 02
`994
`|a C0 |b MYG
`910
`|a jlh
`PST8 |0 Z30 |1 000656176000020 |b ARC |c NOLN1 |o BOOK |d 02 |y 00000 |f N |r MIT60-000584976 |n 8 |h Thesis E.E.
`1993 M.S. |k THESIS |a MCM |3 Book |4 Institute Archives |5 Noncirculating Collection 1 |6 Room Use Only |p Avail
`
`5203
`
`910
`
`1 of 3
`
`10/8/2019, 11:46 AM
`
`Canon Ex. 1054 Page 9 of 104
`
`
`
`MIT Libraries' catalog - Barton - Full Catalog - Full Record
`
`http://library.mit.edu/F/8UYH8LSKVQFL4E66H3ML3283NA8FL82L...
`
`PST8 |0 Z30 |1 000656176000010 |b ARC |c NOLN3 |o BOOK |d 02 |y 00000 |f N |r MIT60-000579310 |n 8 |h Thesis E.E.
`1993 M.S. |k THESIS |a MCM |3 Book |4 Institute Archives |5 Noncirculating Collection 3 |6 Room Use Only
`PST8 |0 Z30 |1 000656176000030 |b ENG |c MFORM |o BOOK |d 12 |y 00000 |f N |r MIT60-000584981 |n 8 |h Thesis E.E.
`1993 M.S. |k THESIS |a MCM |3 Book |4 Barker Library |5 Microforms |6 Thesis Loan
`LDR
` nx 22 zn 4500
`008
`0106230u 0 4 uu 1
`004
`000656176
`8528 |a MCM |b ARC |c NOLN3 |h Thesis E.E. 1993 M.S. |k THESIS |z
`LDR
` nx 22 zn 4500
`008
`0106230u 0 4 uu 1
`004
`000656176
`8528 |a MCM |b ARC |c NOLN1 |h Thesis E.E. 1993 M.S. |k THESIS |z
`LDR
` nx 22 zn 4500
`008
`0106230u 0 4 uu 1
`004
`000656176
`8528 |a MCM |b ENG |c MFORM |h Thesis E.E. 1993 M.S. |k THESIS |z
`LDR
` nx a22 1i 4500
`008
`1802272u 8 4001uueng0000000
`004
`000656176
`8528 |b NET |z Internet Access |h **See URL(s)
`001
`000656176
`SFX41 |s 0-0-0-6-5-6-1-7-6 |l MIT01 |9 001 |z button~~~ |p Avail |f 001 |a Click button for available online volumes
`URL
`|u http://hdl.handle.net/1721.1/108869 |9 001
`U564 |u http://hdl.handle.net/1721.1/108869 |9 001
`LU564 |u http://hdl.handle.net/1721.1/108869 |f 001
`SYS
`000656176
`
`Basic Search of Full Catalog
`Search type:
`
`Search for:
`
`Barton Questions: Ask Us! | Contact Us
`Massachusetts Institute of Technology
`77 Massachusetts Avenue, Cambridge, MA 02139-4307 USA
`
`© 2003 Massachusetts Institute of Technology
`
`2 of 3
`
`10/8/2019, 11:46 AM
`
`Canon Ex. 1054 Page 10 of 104
`
`
`
`MIT Libraries' catalog - Barton - Full Catalog - Full Record
`
`http://library.mit.edu/F/8UYH8LSKVQFL4E66H3ML3283NA8FL82L...
`
`3 of 3
`
`10/8/2019, 11:46 AM
`
`Canon Ex. 1054 Page 11 of 104
`
`
`
`
`
`
`EXHIBIT C
`EXHIBIT C
`
`Canon Ex. 1054 Page 12 of 104
`
`Canon Ex. 1054 Page 12 of 104
`
`
`
`
`
`Visual Memory
`
`by
`Christopher James Kellogg
`
`Submitted to the Department of Electrical Engineering and Computer Science
`in partial fulfillment of the requirements for the degrees of
`
`Bachelor of Science
`and
`Master of Science in Computer Science
`
`at the
`
`MASSACHUSETTS INSTITUTE OF TECHNOLOGY
`
`May 1993
`
`(©) Christopher James Kellogg, MCMXCIII. All rights reserved.
`
`The author hereby grants to MIT permission to reproduce andto distribute copies
`of this thesis document in whole or in part, and to grant others the right to do so.
`
`
`Department of Electrical Engineering gg
`
`til
`247 1993
`
`
`Certified by ......... cc cee cee cect een e enn SEF
`Alex P. Pentland
`Associate Professor of Media Arts and Sciences
`
`cee ee eh
`
`oe ne wee eee eco ees eee
`
`Te ce elf
`
`Thesis Wyor
`
`CA.Certified by....0...cececececececencetceeeeeetenetpectentee4.hk
`—ae oatZ
`Lf.
`
`Chaiyyation,
`fo é Ly - /
`Accepted by...........Kot...wae.fsAe . LoyWaoaeeaeessuneuaatl—
`
`MASSACHUSETTS INSTITUTE
`OF TECHNOLOGY
`
`Canon Ex28aPage 13 of 104
`
`LIBRARIES
`ARCHIVES
`
`§
`
`
`
`4
`
`Campbell L. Searle
`/
`~
`‘artmental Committee on Graduate Students
`
`Canon Ex. 1054 Page 13 of 104
`
`
`
`Visual Memory
`
`by
`
`Christopher James Kellogg
`
`Submitted to the Department of Electrical Engineering and Computer Science
`on April 21, 1993, in partial fulfillment of the
`requirements for the degrees of
`Bachelor of Science
`and
`Master of Science in Computer Science
`
`Abstract
`
`Visual memory supports computer vision applications by efficiently storing and re-
`trieving spatiotemporal information. It is a unique combination of databases, spatial
`representation and indexing, and temporal representation and indexing. This the-
`sis designs a visual memory architecture that meets the requirements of a number
`of computer vision applications.
`It also presents an implementation of part of this
`design in support of a scene monitoring prototype.
`
`Thesis Supervisor: Alex P. Pentland
`Title: Associate Professor of Media Arts and Sciences
`
`Thesis Supervisor: Bruce E. Flinchbaugh
`Title: Manager of Image Understanding Branch at Texas Instruments
`
`Canon Ex. 1054 Page 14 of 104
`
`Canon Ex. 1054 Page 14 of 104
`
`
`
`Acknowledgements
`
`My primary thanks goes to my two thesis supervisors, Bruce Flinchbaugh at Texas
`
`Instruments and Sandy Pentland at MIT. Bruce pointed me to the visual memory
`
`project that he was starting and guided my research at Texas Instruments. Sandy
`
`provided useful feedback throughout the research stage. They were both very helpful
`
`in critiquing the thesis document.
`
`I’d also like to thank the other people at Texas Instruments who helped me with
`
`this project. Steve Ford and Tom Bannon were especially helpful in developing the
`
`visual memory design. In addition, I don’t think I would have survived the bugs in
`
`PC++ without Steve’s expertise. Tom Bannon and Tom O’Donnell provided a nice
`
`tracking system with which to test the visual memory prototype.
`
`Finally, I’d like to thank my family, Fred, Jeannette, and Mark Kellogg, myfiancée
`
`Christine Bailey, and my brothers at Phi Kappa Sigma for their support throughout
`
`my MIT career.
`
`Canon Ex. 1054 Page 15 of 104
`
`Canon Ex. 1054 Page 15 of 104
`
`
`
`9 9
`
`10
`
`11
`
`11
`
`11
`
`12
`
`13
`
`13
`
`13
`
`Contents
`
`1
`
`Introduction
`
`1.1 Needs for Visual Memory. .
`
`. . . .
`
`.
`
`. . .
`
`. . .
`
`. .
`
`. .
`
`. .
`
`. . .
`
`.
`
`1.2 G oals .
`
`.
`
`. .
`
`. .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. .
`
`. . . .
`
`. .
`
`. .
`
`2 Background
`
`2.1 Database Research
`
`. .
`
`. . .
`
`. . . .
`
`. . .
`
`2.1.1 DARPA Open OODB
`
`. . .
`
`. . .
`
`2.1.2 POSTGRES . .
`
`. . .
`
`. .
`
`. .
`
`. . . .
`
`2.2 Spatial Research
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`2.2.1 CODGER
`
`. . . .
`
`. . .
`
`. . .
`
`. . .
`
`. .
`
`. . .
`
`2.2.2 Core Knowledge System
`
`2.2.3
`
`ISR .
`
`. .
`
`. . . .
`
`.
`
`. . .
`
`. . .
`
`. . . .
`
`2.2.4
`
`Image Understanding Environments
`
`2.2.5 PROBE
`
`. . . . .
`
`. . .
`
`.
`
`. .
`
`. . . .
`
`2.2.6 Spatial Indices
`
`.
`
`. . .
`
`. . .
`
`. . . .
`
`2.3 Temporal Research
`
`. . .
`
`. . .
`
`.
`
`. .
`
`. . . .
`
`2.3.1 TQuel
`
`.
`
`.
`
`. . . .
`
`. . .
`
`. . .
`
`. . . .
`
`2.3.2 Temporal Sequences
`
`.
`
`. . .
`
`. . . .
`
`2.3.3 Temporal Sets . .
`
`2.3.4 Relative Time . .
`
`.
`
`.
`
`. .
`
`. . .
`
`. . .
`
`. . .
`
`. . .
`
`. .
`
`2.3.5 Temporal Indices
`
`4
`
`14
`
`14
`
`14
`
`15
`
`15
`
`15
`
`16
`
`16
`
`17
`
`17
`
`Canon Ex. 1054 Page 16 of 104
`
`.
`.
`.
`.
`.
`.
`.
`.
`
`
`3 Design
`
`3.1 Requirements and Considerations
`. .
`
`3.1.1 Database Considerations
`
`.
`
`. . . .
`
`. . . .
`
`3.1.2 Spatial and Temporal Considerations
`. . . . .
`
`3.1.3 Performance Considerations
`
`3.2 Design Overview
`3.3 Spatial Representations .
`
`. . .
`
`.
`
`. . . .
`
`. . . .
`
`3.3.1 Core Spatial Classes
`
`. .
`
`. .
`
`. .
`
`. .
`
`3.3.2 Relative Spatial Specification
`
`. . . .
`
`. . . .
`
`. . . .
`
`. . .
`
`3.3.3 Uncertain Spatial Specification
`
`. . .
`
`3.4 Temporal Representations
`
`. . .
`
`. .
`
`. . . .
`
`3.4.1 Core Temporal Classes
`
`.
`
`. .
`
`. . . .
`
`3.4.2 Relative Temporal Specification
`
`. . .
`
`3.4.3 Uncertain Temporal Specification
`
`. .
`
`3.5 Spatiotemporal Representations
`
`. .
`
`. . . .
`
`3.6 Object Storage
`
`3.6.1
`
`Identity
`
`. .
`
`. .
`
`.
`
`. . .
`
`. . .
`
`. . .
`
`. .
`
`3.6.2 Storage Mechanism . .
`
`3.6.3 Time . . . .
`
`.
`
`. . .
`
`.
`
`3.7 Queries .
`3.7.1 Query Mechanism. . .
`
`.
`
`.
`
`. . . .
`
`. . . .
`
`.
`
`3.7.2 Spatial Queries
`
`. .
`
`3.7.3 Temporal Queries .
`
`.
`
`.
`
`3.7.4 Spatiotemporal Queries
`
`3.8
`
`Indices .
`
`. . .
`
`. . . .
`
`. . .
`
`.
`
`3.8.1 Mechanism
`
`.
`
`. . .
`
`3.8.2 Spatial Indices
`
`. .
`
`. .
`
`. .
`
`3.8.3 Temporal Indices
`
`.
`
`3.8.4 Spatiotemporal Indices
`
`.
`
`.
`
`5
`
`66
`
`Canon Ex. 1054 Page 17 of 104
`
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`.
`
`
`4 Implementation
`
`4.1 Database...... .......
`
`................
`
`.......
`
`4.2 Spatiotemporal Representations
`
`. .
`
`. . . .
`
`. .
`
`.
`
`. . . .
`
`. . .
`
`. . .
`
`4.3
`
`Indices . . .
`
`. .
`
`.
`
`. . .
`
`. . . .
`
`. . .
`
`. . . .
`
`.
`
`. .
`
`. . .
`
`. . .
`
`. . . .
`
`. .
`
`. .
`
`4.3.1 Mechanism
`
`. .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . .
`
`. . . .
`
`. .
`
`4.3.2 Spatial Indices
`
`. . . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . .
`
`. .
`
`. .
`
`. .
`
`. .
`
`68
`
`68
`
`71
`
`71
`
`71
`
`72
`
`4.3.3 Temporal Indices
`4.4 Q ueries. . .
`Input .
`.
`. .
`
`4.5
`
`. .
`
`.
`
`. . . .
`
`. . .
`
`.
`
`. . .
`
`. . . .
`
`. . . .
`
`. .
`
`. .
`
`. . . . .
`
`.
`
`.
`
`. . . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`. .
`
`. .
`
`. .
`
`. .
`
`. .
`
`75
`
`77
`
`77
`
`78
`
`81
`
`82
`
`83
`
`88
`
`4.6 Graphical Query Interface
`
`. .
`
`. . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . .
`
`. .
`
`.
`
`5 Performance
`
`5.1 Spatiotemporal Object Storage and Retrieval . . .
`
`. . .
`
`. . .
`
`. . .
`
`5.2
`
`Index Comparison. . .
`
`. . . . .
`
`. .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`6 Conclusion
`
`6
`
`Canon Ex. 1054 Page 18 of 104
`
`
`
`A
`
`List of Figures
`
`. .
`
`. . . .
`
`. . .
`
`. . .
`
`. . . . .
`
`. . .
`
`.. .... ... 25
`
`. . . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . . . .
`
`. .
`
`. .
`
`. .
`
`. . . . . .
`
`. . .
`
`. ..
`
`. ..... 26
`
`. . . . .
`
`. . . . . . . . . . .
`
`.
`
`. . . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . .
`
`.
`
`.
`
`. .
`
`. .
`
`. . . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . . .
`
`. .
`
`. .
`
`. .
`
`...
`
`.. ... .. . 33
`
`. . .
`
`. . . . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . . .
`
`27
`
`28
`
`30
`
`32
`
`32
`
`34
`
`35
`
`38
`
`38
`
`3-1 Spatial objects
`3-2 Discrete point set .
`3-3 Abstract point set .
`3-4 Coordinate systems . .
`. . . .
`. . . .
`. . .
`3-5 Relative spatial objects . . . .
`3-6 Breaking a relative spatial specification, part 1 . .
`. .
`3-7 Breaking a relative spatial specification, part 2 .
`. . .
`. . . . . .
`. .
`. . .
`3-8 Uncertain edges . . . .
`. . .
`.
`3-9 Uncertain location
`3-10 Conflicting information . .
`. . . .
`3-11 Temporal element .
`3-12 Overlapping temporal elements
`3-13 Temporal resolution in favor of version A . . .
`. . .
`3-14 Temporal resolution in favor of version B . .
`. . . . .
`3-15 Relative temporal specification . . .
`3-16 Probabilistic temporal interval . . .
`3-17 Overlapping probabilistic temporal intervals
`. . .
`3-18 Probabilistic conjunction by minimization
`3-19 Probabilistic disjunction by maximization
`3-20 Discrete spatiotemporal information . . . .
`. . . . .
`3-21 Interpolated spatiotemporal state
`. . . . .
`. . .
`. .
`3-22 Point set trajectory . .
`
`. .
`
`. .
`
`. . . .
`
`. . .
`
`. . .
`
`. . .
`
`. . .
`
`. . . . .
`
`. . .
`
`. . .
`
`. .
`
`. .
`
`. . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. .
`
`. . . .
`
`. . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . . .
`
`.
`
`.
`
`.
`
`. . .
`
`. . .
`
`. .
`
`. . . .
`
`. .
`
`. .
`
`. .
`
`. .
`
`. .
`
`. . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. . .
`
`. . . .
`
`39
`
`39
`
`40
`
`42
`
`43
`
`43
`
`44
`
`46
`
`46
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . . ....
`
`47
`
`3-23 Coordinate system trajectory
`
`.
`
`. . . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . .
`
`48
`
`7
`
`Canon Ex. 1054 Page 19 of 104
`
`
`
`-1
`
`3-24 Spatial queries . . .
`
`. .
`
`. . . . .
`
`. .
`
`. . . .
`
`. . . . .
`
`. .
`
`. . . .
`
`. .
`
`. .
`
`55
`
`3-25 Temporal queries
`
`.
`
`.
`
`. .
`
`. ..
`
`............ ..... ..... 58
`
`3-26 States of a spatiotemporal object
`
`.
`
`3-27 Joint spatial and temporal queries .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`..
`
`. . . . . . . . . . . .
`
`.
`
`61
`
`.
`
`.
`
`.
`
`.
`
`.
`
`60
`
`3-28 Spatiotemporal queries
`
`.
`
`.
`
`..
`
`. . . . .. . . . . . . . . . . . . . . . . 62
`
`4-1 Scene monitoring prototype
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`4-2 Fixed grid spatial index
`
`. . . .
`
`. . . .
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`.
`
`..
`
`69
`
`. .
`
`. . . .
`
`. .
`
`. . . .
`
`. ... 73
`
`4-3 Segmented space for bucket PR quadtree
`
`. .
`
`. . . .
`
`. .
`
`. . . .
`
`. . .
`
`.
`
`4-4 Data structure for bucket PR quadtree
`
`. . . .
`
`. . .
`
`. . .
`
`. . .
`
`. . . .
`
`4-5 Temporal segment tree
`
`. .
`
`. . .
`
`. . ..
`
`.................
`
`76
`
`4-6 Temporal B+ tree . .
`
`.
`
`.
`
`. . ... ........ ........... 76
`
`4-7 Graphical query interface viewing region
`
`. . .
`
`. . .
`
`. . .
`
`. . .
`
`. . . .
`
`4-8 Specification of query times and classes .
`
`. . ..
`
`. .
`
`. . .
`
`. . . .
`
`. . .
`
`4-9 Graphical query results .
`
`.
`
`. . . .
`
`. . . .
`
`. . .
`
`. ..
`
`......... . 80
`
`5-1 Spatiotemporal update performance . . . .
`
`5-2 Spatial update performance
`
`. . .
`
`. . . . .
`
`. .
`
`. .
`
`. . .
`
`. . . .
`
`. . .
`
`. . .
`
`. . . .
`
`. . .
`
`.
`
`. . .
`
`. .
`
`5-3 Temporal update performance
`
`. . .
`
`. . . .
`
`. . .
`
`. . ..
`
`. ... ... .
`
`85
`
`5-4 Spatial query performance
`
`. .
`
`. . .
`
`. . . .
`
`. . .
`
`. . . .
`
`. .. ..... 86
`
`74
`
`74
`
`78
`
`79
`
`82
`
`84
`
`5-5 Temporal query performance .
`
`. . .
`
`. . . . .
`
`. . .
`
`. . .
`
`. . .
`
`. . .
`
`. .
`
`87
`
`8
`
`Canon Ex. 1054 Page 20 of 104
`
`
`
`Chapter 1
`
`Introduction
`
`Visual memory supports computer vision applications by efficiently storing and re-
`trieving spatiotemporal information. It is a unique combination of databases, spatial
`representation and indexing, and temporal representation and indexing. Visual mem-
`ory provides representational flexibility and high-performance information access to
`meet the requirements of a variety of computer vision applications.
`
`1.1 Needs for Visual Memory
`
`Applications use spatiotemporal data in many different ways and place many different
`demands on a visual memory. Studying possible uses helps to clarify the concept of
`a visual memory and to identify the functionality it provides.
`Visual memory could serve as the repository for static information, such as ob-
`ject descriptions, maps, and environment models, that applications reference during
`execution. For example, a vehicle navigator could store maps and images to help it
`later recognize its location. A large amount of such information could be established
`prior to application execution, and the visual memory would subsequently provide an
`application with efficient access to desired pieces of information.
`An application could store dynamic information in the visual memory. For ex-
`ample, a vehicle navigator's input systems could maintain in the visual memory a
`description of the vehicle's local environment, updating it as the vehicle moved. The
`
`9
`
`Canon Ex. 1054 Page 21 of 104
`
`
`
`A
`
`visual memory could provide the navigator's planning processes with information
`
`about the vehicle's latest state and could analyze its progress to help determine a
`
`course of action. The high performance of the visual memory allows it to handle the
`
`frequent updates and queries needed by such dynamic, real-time systems.
`
`Visual memory could manipulate spatiotemporal information about objects and
`
`collections of objects too large to fit into volatile memory. For example, a computer-
`
`aided design and modeling system could use the visual memory in building up a large
`
`design layout and simulating its execution over time; a photo interpretation system
`
`could similarly construct in the visual memory a complex representation of a scene.
`
`The visual memory would retrieve into main memory only a manageable part of a
`
`large representation at a time.
`
`Visual memory could act as the interface between inputs and applications in a
`computer vision system. For example, computer vision algorithms for a security
`
`system could analyze data provided by various cameras and store information in the
`
`visual memory. Applications could then retrieve this data to track objects, watch for
`
`suspicious events, and respond to user queries. The visual memory would coordinate
`
`the information from its inputs and eliminate the need for full connectivity between
`
`inputs and applications.
`
`Finally, visual memory could serve as a means for data transfer. A computer
`
`vision application could store spatiotemporal information in the visual memory for
`
`other applications to retrieve at any time in the future. To run comparative studies,
`
`different algorithms could use common data stored in the visual memory.
`
`1.2 Goals
`
`This thesis explores visual memory design and implementation. The primary goal
`
`of the thesis is to design a visual memory architecture that meets the requirements
`
`of various computer vision applications. A secondary goal is to implement a visual
`
`memory prototype to support a real-time scene monitoring prototype.
`
`10
`
`Canon Ex. 1054 Page 22 of 104
`
`
`
`Chapter 2
`
`Background
`
`Visual memory builds on research in database design, spatial representation and
`indexing, and temporal representation and indexing. While there has been significant
`research in each of these areas, no previous project has combined them in this manner.
`The visual memory design uses knowledge gained from research projects in all these
`areas. This chapter summarizes and discusses some especially relevant projects.
`
`2.1 Database Research
`
`Visual memory must address concerns that a great deal of database research has
`already investigated. It must provide everything from information storage techniques
`to concurrency control for multiple inputs and outputs. Visual memory should build
`on the results of research into these topics. Presented here are two databases that
`address a number of the issues important to visual memory and that could be the
`
`basis for a visual memory system.
`
`2.1.1 DARPA Open OODB
`
`The DARPA Open Object-Oriented Database (Open OODB) project at Texas In-
`struments outlines an extensible architecture that allows "... tailoring database func-
`tionality for particular applications in the framework of an incrementally improvable
`
`system .... "
`
`[25] The architecture meets functional requirements such as an object
`
`11
`
`Canon Ex. 1054 Page 23 of 104
`
`
`
`data model and concurrent access, along with "meta requirements" including open-
`ness and reusability. The open architecture lets separate modules handle extensions
`to the basic storage mechanism. These extensions cover standard database issues
`such as transactions, versions, and queries.
`The Open OODB architecture is very suitable for visual memory. The object-
`oriented model can flexibly and intuitively represent the information used by computer
`vision applications. Following the Open OODB architecture, visual memory could
`avoid confronting standard database issues by letting other modules support those
`features. Instead, visual memory would consist only of those extensions necessary to
`support efficient manipulation of spatiotemporal information. If new features were
`needed, extra modules could easily be added to the architecture.
`
`2.1.2 POSTGRES
`
`The POSTGRES database [23] expands the relational database model to meet the
`needs of complex applications. Because it builds on traditional relational databases, it
`provides a number of standard features, such as transactions, a query language, and
`
`recovery processing.
`
`In addition, it allows applications to specify new data types,
`
`operators, and access methods. POSTGRES supports active databases and rules,
`letting applications set up daemons in the database that react to changes in the data.
`A versioning mechanism keeps track of old data and works with the query language
`to let applications retrieve this information. Finally, the POSTGRES storage server
`can "vacuum" old data onto archival media.
`POSTGRES supplies many features useful to a visual memory, such as transac-
`tions, queries, and application-defined access methods. However, the relational model
`might not be sufficiently expressive to meet the representational needs of complex
`computer vision applications. In addition, the POSTGRES design does not support
`application-specific extensions to the database, so it would be hard for the visual
`
`memory to expand to meet future requirements.
`
`12
`
`Canon Ex. 1054 Page 24 of 104
`
`
`
`-1
`
`2.2 Spatial Research
`
`There are many ways to describe spatial objects and to handle their storage and
`
`retrieval. Visual memory must consider how well different spatial models meet the
`
`representational needs of computer vision applications and how efficiently information
`
`in these models can be stored and retrieved.
`
`2.2.1 CODGER
`
`Researchers at Carnegie Mellon University developed the CODGER (COmmunica-
`
`tions Database with GEometric Reasoning) "whiteboard" database and communica-
`
`tion system to support the autonomous NAVLAB vehicle [20]. CODGER stores data
`
`to be communicated among the various modules that control vehicle navigation. It
`
`represents this information as tokens consisting of attributes and values.
`
`CODGER uses a fairly simple spatial model. Token attributes represent basic
`
`spatial information such as position and object extent. The tokens support some
`
`standard geometric operations like area calculation. A query mechanism can answer
`
`some spatial queries like the proximity query "Return the tokens with location within
`
`5 units of (45,32)." CODGER does not provide an indexing mechanism, and spatial
`
`operations and queries are performed in memory.
`
`2.2.2 Core Knowledge System
`
`The Core Knowledge System (CKS) [24], developed at SRI International, stores in-
`
`formation for a robot. Like CODGER, it encodes this information as attribute-value
`
`tokens. CKS introduces special support for the uncertainty that results from incon-
`
`sistent or incomplete information provided to the database.
`
`Its query mechanism
`
`includes keywords such as apparently and possibly to discern multiple opinions. Since
`
`spatial information is often imprecise, this support for uncertainty would be very use-
`
`ful in a visual memory context. However, CKS does not provide any special spatial
`
`operations or query constructs.
`
`13
`
`Canon Ex. 1054 Page 25 of 104
`
`
`
`2.2.3
`
`ISR
`
`The ISR project at the University of Massachusetts at Amherst [3] defines a spatial
`
`representation (the Intermediate Symbolic Representation) and a management system
`
`for accessing data represented this way. The intermediate symbolic representation
`
`includes tokens for basic spatial objects such as lines, regions, and sets of parallel
`
`lines, but not for higher-level spatial objects such as people and vehicles. The data
`
`management system manipulates these tokens in an efficient manner. Applications
`
`built with ISR perform classification and in-memory spatial indexing.
`
`2.2.4
`
`Image Understanding Environments
`
`The Image Understanding Environments (IUE) program [16] specifies a spatial rep-
`
`resentation to meet the n