`United States Patent No. 7,868,912
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`
`BEFORE THE PA TENT TRIAL AND APPEAL BOARD
`
`Axis Communications AB, Canon Inc., and Canon U.S.A., Inc.,
`
`Petitioner
`
`V.
`
`Avigilon Fortress Corporation,
`
`Patent Owner
`
`Cases: IPR2019-00235 & IPR.2019-00236
`
`U.S. Patent No. 7,868,912
`Issue Date: January 11, 2011
`
`Title: Video Surveillance System Employing Video Primitives
`
`DECLARATION OF EMILY R. FLORIO
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`I, Emily R. Florio, state and declare as follows:
`
`1.
`
`I have prepared this Declaration in connection with the Petitions of
`
`Axis Communications AB, Canon Inc., and Canon U.S.A., Inc. ( collectively
`
`"Petitioner") for two inter partes reviews of U.S. Patent No. 7,868,912 ("the '912
`
`patent"), Case Nos. IPR2019-00235 and IPR2019-00236, which I understand will
`
`be filed concurrently with this Declaration.
`
`2.
`
`I am currently the Director of Research & Information Services at
`
`Finnegan, Henderson, Farabow, Garrett & Dunner LLP, 901 New York Avenue
`
`NW, Washington, DC 20001-4413.
`
`3.
`
`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 of library science practices, as well as my knowledge of the practices at
`
`the Massachusetts Institute of Technology ("MIT") Libraries.
`
`4.
`
`I earned a Master's of Library Science ("MLS") from Simmons
`
`College in 2006, and I have worked as a librarian for over a decade. I have been
`
`employed in the Research & Information Services (formerly Library) Department
`
`of Finnegan since 2013, and from 2005-2013, I worked in the Library Department
`
`of Fish & Richardson P.C.
`
`2
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`5.
`
`I am currently the Vice-President Elect of the American Association
`
`of Law Libraries and the President of the Law Librarians' Society of Washington,
`
`DC, and a member of the International Legal Technology Association.
`
`Attachments
`
`6.
`
`Attached as Exhibit A (Exhibit 1003 to the Petition in IPR2019-
`
`00235) is a true and correct copy of"Visual Memory," May 1993, pp. 1-92, by
`
`Christopher James Kellogg ("Kellogg"), obtained from the MIT Libraries.
`
`7.
`
`Attached as Exhibit B is a true and correct copy of the "Standard"
`
`record from the MIT Libraries' catalog system (known as the Barton Catalog) for
`
`its copy of Kellogg.
`
`8.
`
`Attached as Exhibit C is a true and correct copy of the MARC record
`
`of the MIT Libraries for its copy of Kellogg.
`
`9.
`
`Attached as Exhibit D (Exhibit 1005 to the Petition in IPR2019-
`
`00235) is a true and accurate copy ofB. Flinchbaugh et al., "Autonomous Scene
`
`Monitoring System," Proceedings, 10th Annual Joint Government-Industry
`
`Security Technology Symposium & Exhibition, June 20-23, 1994, pp. 205-209
`
`("Flinchbaugh"), obtained from the British Library.
`
`10. Attached as Exhibit Eis a true and correct copy of the MARC record
`
`of the British Library for its copy of the Proceedings publication that includes
`
`Flinchbaugh.
`
`3
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`11. Attached as Exhibit F are documents further showing the public
`
`availability of Flinchbaugh. Exhibit F-1 is a true and correct copy of U.S. Patent
`
`No. 7,023,469 (the '469 Patent), and the list of references filed by the applicant of
`
`the '469 Patent with its filing on April 15, 1999, obtained from the U.S. Patent and
`
`Trademark Office's PAIR files. Exhibit F-2 is a true and correct copy ofR.
`
`Collins et al., "A System for Video Surveillance and Monitoring," Robotics
`
`Institute, Carnegie Mellon University, Pittsburgh, PA ("Collins") and information
`
`concerning this 1999 publication available at https://www.semanticscholar.org.
`
`12. Attached as Exhibit G (Exhibit 1004 in each Petition in IPR2019-
`
`00235 and IPR2019-00236) is a true and correct copy of Brill et al., "Event
`
`Recognition and Reliability Improvements for the Autonomous Video Surveillance
`
`System," Proceedings of the Image Understanding Workshop, Monterey, CA, Nov.
`
`20-23, 1998, Vol. 1, pp. 267-283 ("Brill"), obtained from the Duderstadt Center,
`
`formerly known as the University of Michigan Media Union (UMMU).
`
`13. Attached as Exhibit H is a true and correct copy of the MARC record
`
`of the University of Virginia Library for its copy of Brill.
`
`14. Attached as Exhibit I is a true and correct copy of the MARC record
`
`of the North Carolina State University library for its copy of Brill.
`
`4
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`The MARC Cataloging System
`
`15. The MAchine-Readable Cataloging ("MARC") system is used by
`
`libraries to catalog materials. The MARC system was developed in the 1960s to
`
`standardize bibliographic records so they could be read by computers and shared
`
`among libraries. By the mid-1970's, MARC had become the international standard
`
`for bibliographic data, and it is still used today.
`
`16. Each field in a MARC record provides information about the
`
`cataloged item. MARC uses a simple three-digit numeric code (from 001-999) to
`
`identify each field in the record.
`
`17.
`
`For example, field 245 lists the title of the work and field 260 lists
`
`publisher information. In addition, field 008 provides the date the item was
`
`cataloged. The first six characters of the field 008 are always in the "YYMMDD"
`
`format.
`
`18.
`
`It is standard library practice that once an item is cataloged using the
`
`MARC system, it is shelved. This process may take a relatively nominal amount
`
`of time (i.e., a few days or weeks). During the time between the cataloging and
`
`shelving of an item, the public may still find the item by searching the catalog and
`
`requesting the item from the library.
`
`5
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`Kellogg
`
`19. As indicated in Exhibit A (Exhibit 1003 to the Petition in IPR2019-
`
`00235), Kellogg has an MIT Libraries date stamp of"JUL 09 1993" on page 1,
`
`indicating that the MIT Libraries received Kellogg on July 9, 1993. Further, as
`
`indicated in Exhibit B, the Standard record of the Barton Catalog confirms that
`
`Kellogg is shelved at the MIT Libraries and was published in 1993. In view of the
`
`above and the following, Kellogg was published and accessible to the public in
`
`1993, years before October 1999.
`
`20. As indicated in Exhibit C, Kellogg has a cataloging date of September
`
`28, 1993 (shown as "930928" in field 008). This confirms that Kellogg was
`
`entered into the OCLC database, in which MIT does its cataloging, on September
`
`28, 1993. This is also consistent with its noted year of publication in the MARC
`
`record (shown as "1993" in field 260). The OCLC database (also referred to as
`
`"WorldCat") is the largest online public access catalog (OP AC) in the world.
`
`21.
`
`Soon after Kellogg received a cataloging date, a record of its existence
`
`would have appeared in and been keyword-searchable through the Barton Catalog
`
`of the MIT Libraries. The Barton Catalog is currently available online to any user
`
`of the World Wide Web. Before it was accessible by Web (i.e., at the time the
`
`Kellogg thesis was received by the MIT Libraries in July 1993), it would have been
`
`6
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`accessible to anyone on the MIT campus and anyone who had access to the OCLC
`
`database.
`
`22. During the time period from September 1993 through October 1999,
`
`the Barton Catalog allowed keyword searching for words in the thesis title, and
`
`Kellogg would have appeared in a relevant Barton Catalog search conducted on or
`
`shortly after September 28, 1993.
`
`23. After being cataloged, a document such as Kellogg will undergo a
`
`process of being labeled and then shelved at the MIT Libraries. Based on my
`
`knowledge of MIT Libraries' current and prior practices, Kellogg would have been
`
`shelved in a relatively nominal amount of time (i.e., a few days or weeks). Thus,
`
`Kellogg was cataloged and shelved at the MIT Libraries at least before the end of
`
`1993.
`
`24. Once shelved, Kellogg can be borrowed by any member of the MIT
`
`community. Furthermore, a copy of Kellogg can be purchased from MIT by any
`
`member of the public. Indeed, the first page of Kellogg confirms that there were
`
`no restrictions placed on its publication, as it states that "[t]he author hereby grants
`
`to MIT permission to reproduce and to distribute copies of this thesis document in
`
`whole or in part, and to grant others the right to do so."
`
`25.
`
`Further evidence of the public availability of Kellogg before October
`
`1999 is provided in Exhibit D, which is a copy of Flinchbaugh. In its
`
`7
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`"References" section, Flinchbaugh cites to Kellogg (reference [1] on p. 209). It
`
`also states that Kellogg is available as a Technical Report, CSL-93-05-20, from
`
`Texas Instruments. As addressed below, Flinchbaugh was published in the
`
`Proceedings from the 10th Annual Joint Government-Industry Security Technology
`
`Symposium and Exhibition. The Symposium was held June 20-23, 1994, and the
`
`Proceedings were published by at least 1997. Thus, Kellogg was at least available
`
`to members of the public in 1997, as shown by its citation in Flinchbaugh.
`
`26.
`
`For the avoidance of any doubt, I note that on June 23, 2001, Kellogg
`
`was also cataloged in the MIT Archive Noncirculating Collection 1,
`
`Noncirculating Collection 3, and in microfiche form in the Barker Library, as
`
`indicated in the three entries for PST8 and in the second, third, and fourth instances
`
`of field 008 on page 1 of Exhibit C. However, none of this alters the fact that
`
`Kellogg was published and accessible to the public in 1993, as indicated above.
`
`Flinchbaugh
`
`27. As indicated in Exhibit D, Flinchbaugh (Exhibit 1005 to the Petition
`
`in IPR2019-00235) was published in the Proceedings of the 10th Annual Joint
`
`Government-Industry Security Technology Symposium and Exhibition. The
`
`Symposium was held in Williamsburg, VA during June 20-23, 1994, and the
`
`Proceedings was published by the American Defense Preparedness Association.
`
`8
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`Ex. D at 1. In view of the above and the following, Flinchbaugh was published and
`
`accessible to the public before October 1999.
`
`28.
`
`First, as noted above, the Symposium was held in Williamsburg, VA
`
`during June 20-23, 1994. Second, a copy of Flinchbaugh was received and
`
`cataloged by the British Library in February 1997. See Ex. E at 1. Exhibit E is the
`
`MARC record for the Proceedings, including Flinchbaugh, that was obtained from
`
`the British Library. As shown in field 008 on page 1 of Exhibit E, Flinchbaugh
`
`was cataloged by the library on February 17, 1997 (shown as 970217 in field 008).
`
`Based on standard library practices, this reference would have been shelved shortly
`
`after it was cataloged (i.e., within a few days or weeks). The above is corroborated
`
`by the dates stamped on the cover of the Proceedings, including the "12 Feb 1997"
`
`date at the top of the page indicating that it was received into the British Library's
`
`"serials file" and the "1 7 Feb 1997" date on the middle-left side of the page
`
`indicating "conference indexed." Ex. D at 1. Field 85241, subfield j of Exhibit E
`
`also has the number 1086.803000, which matches the stamp in the upper right
`
`comer of Flinchbaugh. Collectively, Exhibits D and E show that Flinchbaugh was
`
`published and accessible to the public years before October 1999.
`
`29.
`
`Further evidence of the publication and public availability of
`
`Flinchbaugh can be found in Exhibit F. For example, Exhibit F-1 is a copy of the
`
`'469 Patent, which lists Thomas J. Olson as the inventor and shows that
`
`9
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`Flinchbaugh was cited to the Patent Office. See Ex. F-1 at 1-2. Based on the Patent
`
`Office's prosecution file of the '469 Patent, Flinchbaugh was cited by the applicant
`
`with the filing of the application on April 15, 1999, more than a year before the
`
`earliest possible filing date of the '912 Patent. Ex. F-1 at 20.
`
`30. As further evidence of the publication and public availability of
`
`Flinchbaugh, Exhibit F-2 is a copy of Collins, which is co-authored by one of the
`
`inventors of the '912 Patent, Alan J. Lipton. Ex. F-2 at 1. As part of the
`
`"References" section in Collins, Flinchbaugh is listed and Collins states that
`
`Flinchbaugh was published in "June 1994." Ex. F-2 at 15.
`
`31.
`
`For the avoidance of any doubt, I note that Collins itself was
`
`published in 1999 and is a highly cited paper. For example, as indicated on the
`
`website "www.semanticscholar.org," Collins was published in" 1999" and is a
`
`highly cited paper, having "1,676 citations." See Ex. F-2 at 16. However, none of
`
`this alters the fact that Flinchbaugh was published and accessible to the public
`
`years before October 1999, as indicated above.
`
`Brill
`
`32. As indicated in Exhibit G, Brill (Exhibit 1004 to each Petition in
`
`IPR2019-00235 and IPR2019-00236) is part of the published Proceedings of the
`
`1998 Image Understanding Workshop. The Workshop was held in Monterey,
`
`California during November 20-23, 1998, and the Proceedings were "APPROVED
`
`10
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`FOR PUBLIC RELEASE" with "DISTRIBUTION UNLIMITED." Ex. G at 1. In
`
`view of the above and the following, the Proceedings, including Brill, was
`
`published and accessible to the public before October 1999.
`
`33. Evidence of Brill's publication and availability to the public includes
`
`the hand-written receipt date of"8-13-99" at the top of page 3 of Exhibit G. This
`
`indicates it was received by the UMMU (the University of Michigan Media Union,
`
`now known as the Duderstadt Center) on August 13, 1999. In my experience as a
`
`librarian and knowledge of standard library practices, the hand-written information
`
`at the top of p. 2 of Exhibit G appears to be the catalog record information for
`
`Brill. Based on standard library practices, this reference would have been shelved
`
`shortly after being received and .cataloged by UMMU.
`
`34.
`
`Further evidence of the publication and accessibility of Brill to the
`
`public can be found in Exhibit H, which is the MARC record for the Proceedings,
`
`including Brill, that was obtained from the University of Virginia Library. As
`
`shown in field 008 near the top of page 2 of Exhibit H, Brill was cataloged by the
`
`library on December 15, 1998. Based on standard library practices, this reference
`
`would have been shelved shortly after (i.e., within a few days or weeks) and been
`
`accessible to the public prior to October 1999.
`
`35.
`
`Further evidence of the publication and public availability of Brill can
`
`be found in Exhibit I, which is the MARC record for the Proceedings, including
`
`11
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`Brill, that was obtained from North Carolina State University. As shown in field
`
`008 on page 1 of Exhibit I, Brill was cataloged by the library on December 15,
`
`1998. Based on standard library practices, this reference would have been shelved
`
`shortly after (i.e., within a few days or weeks) and been accessible to the public
`
`prior to October 1999.
`
`I declare under penalty of perjury that the foregoing is true and correct.
`
`Executed on April 1, 2019 in Washington, D.C.
`
`12
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EXHIBIT A
`EXHIBIT A
`
`
`IPR2019-00235
`
`Axis Exhibit 1043, Page 13 of 197
`
`Axis V. AVigilon
`
`
`
`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 and to distribute copies
`of this thesis document in whole or in part, and to grant others the right to do so.
`
`Signature redacted
`Au tho, ................ ji~;.;;~; ~i" Ek;;;;;.i" ~~~;://~;;;;
`Signature redacted
`
`.
`
`Certified by .................................. ...-.rT• .. •v •.••• ••..•....•...........
`Alex P. Pentland
`Associate Professor of Media Arts and Sciences
`_ Thesis Supervi§or
`Signature redacted
`Certified by ...................................... ·r ...... · ... ,- . -~• · ·. ·. · ·. v- · , -· r
`Bruce E. Flinchbaugh
`Manager of Image Understandin~a~h a~rum~nts
`.• -:;..,-= /? d
`/ // /
`,1hes,WSuperv1sor
`
`Signature redacted
`Accepted by ......... -~:;z.ze:~~;~L::.:~n i:i~~~ E::::
`
`MASSACHUSITTS INSTITUTE
`OF TH'.HNOLOGY
`
`'JUL 09 1993
`LIBRARIES
`ARCHIVE=~
`
`
`
`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(cid:173)
`trieving spatiotemporal information. It is a unique combination of databases, spatial
`representation and indexing, and temporal representation and indexing. This the(cid:173)
`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
`
`
`
`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, my fiancee
`
`Christine Bailey, and my brothers at Phi Kappa Sigma for their support throughout
`
`my MIT career.
`
`3
`
`
`
`Contents
`
`1 Introduction
`1.1 Needs for Visual Memory .
`1.2 Goals .. ..........
`
`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 U ndersta.nding 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
`
`g
`
`9
`10
`
`11
`
`11
`
`11
`12
`13
`13
`13
`
`14
`
`14
`14
`15
`15
`
`15
`16
`
`16
`17
`17
`
`
`
`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
`3.6.2 Storage Mechanism
`
`Identity
`
`3.6.3 Time.
`
`3.7 Queries . . . .
`3.7.1 Query Mechanism .
`
`3.8
`
`3.7.2 Spatial Queries
`3.7.3 Temporal Queries
`3.7.4 Spatiotemporal Queries .
`
`Indices . . . . . . .
`3.8.1 Mechanism
`3.8.2 Spatial Indices
`3.8.3 Temporal Indices
`3.8.4 Spatiotemporal Indices
`
`5
`
`18
`
`19
`19
`20
`20
`
`22
`24
`24
`
`29
`31
`
`36
`
`36
`40
`41
`
`45
`50
`50
`51
`
`52
`
`53
`53
`54
`
`57
`59
`64
`
`64
`65
`66
`66
`
`
`
`4 Implementation
`4.1 Database ... ..........
`4.2 Spatiotemporal Representations
`4.3
`
`Indices . . . . . . .
`4.3.1 Mechanism
`4.3.2 Spatial Indices
`4.3.3 Temporal Indices
`4.4 Queries.
`4.5
`Input ..
`4.6 Graphical Query Interface
`
`5 Performance
`5.1 Spatiotemporal Object Storage and Retrieval .
`Index Comparison . ...............
`5.2
`
`6 Conclusion
`
`68
`
`68
`
`71
`
`71
`
`71
`72
`75
`77
`77
`78
`
`81
`
`82
`83
`
`88
`
`6
`
`
`
`List of Figures
`
`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 . . . . . .
`
`3-23 Coordinate system trajectory
`
`7
`
`25
`
`26
`
`27
`
`28
`
`30
`
`32
`
`32
`
`33
`
`34
`
`35
`
`38
`
`38
`
`39
`
`39
`40
`
`42
`
`43
`
`43
`44
`
`46
`46
`
`47
`48
`
`
`
`55
`
`58
`
`60
`
`61
`
`62
`
`69
`
`73
`
`74
`
`74
`
`76
`
`76
`
`78
`
`79
`
`80
`
`82
`
`84
`
`85
`
`86
`
`87
`
`3-24 Spatial queries . .
`
`3-25 Temporal queries
`
`3-26 States of a spatiotemporal object
`
`3-27 Joint spatial and temporal queries .
`
`3-28 Spatiotemporal queries ...
`
`4-1 Scene monitoring prototype
`4-2 Fixed grid spatial index ..
`4-3 Segmented space for bucket PR quadtree
`
`4-4 Data structure for bucket PR quadtree
`
`4-5 Temporal segment tree
`
`4-6 Temporal B+ tree . . .
`
`4-7 Graphical query interface viewing region
`
`4-8 Specification of query times and classes
`
`4-9 Graphical query results . . . . . . . .
`
`5-1 Spatiotemporal update performance .
`
`5-2 Spatial update performance
`
`5-3 Temporal update performance
`
`5-4 Spatial query performance . .
`
`5-5 Temporal query performance .
`
`8
`
`
`
`Chapter 1
`
`Introduction
`
`Visual memory supports computer vision applications by efficiently storing and re(cid:173)
`
`trieving spatiotemporal information. It is a unique combination of databases, spatial
`
`representation and indexing, and temporal representation and indexing. Visual mem(cid:173)
`
`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(cid:173)
`
`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(cid:173)
`
`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
`
`
`
`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 pedormance 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(cid:173)
`
`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
`
`
`
`Chapter 2
`
`Background
`
`Visual memory builds on research in database design, spatial representation and
`
`indexing, a.nd temporal representation and indexing. While there has been significant
`
`research in ea.ch of these areas, no previous project has combined them in this ma.nner.
`
`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 data.base 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 a.re two data.bases that
`
`address a number of the issues important to visual memory a.nd that could he the
`
`basis for a visual memory system.
`
`2.1.1 DARPA Open OODB
`
`The DARPA Open Object-Oriented Data.base (Open OODB) project at Texas In(cid:173)
`
`struments outlines an extensible architecture that allows " ... tailoring data.base func(cid:173)
`
`tionality for particular applications in the framework of an incrementally improvable
`
`system .... " [25] The architecture meets functional requirements such as an object
`
`11
`
`
`
`data model and concurrent access, a.long with "meta requirements" including open(cid:173)
`
`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(cid:173)
`
`oriented model can flexibly and intuitively represent the information used by computer
`
`vision applications. Following the Open OODB architecture, visual memory could
`
`a.void confronting standard da.ta.ba.se issues by letting other modules support those
`
`features. Instead, visual memory would consist only of those extensions necessary to
`
`support efficient manipulation of spa.tiotempora.l 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 data.base 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(cid:173)
`
`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
`
`
`
`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.(cid:173)
`
`tions Data.base with GEometric Reasoning) "whiteboard" data.base and communica(cid:173)
`
`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 a.s 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(cid:173)
`
`formation for a robot. Like CODGER, it encodes this information a.s attribute-value
`
`tokens. CKS introduces special support for the uncertainty that results from incon(cid:173)
`
`sistent or incomplete information provided to the database. Its query mechanism
`
`includes keywords such a.s apparently and possibly to discern multiple opinions. Since
`
`spatial information is often imprecise, this support for uncertainty would be very use(cid:173)
`
`ful in a visual memory context. However, CKS does not provide any special spatial
`
`operations or query constructs.
`
`13
`
`
`
`2.2.3
`
`ISR
`
`The ISR project a.t the University of Ma.ssa.chusetts a.t 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 ha.sic spatial objects such as lines, regions, and sets of para.Ile!
`
`lines, but not for higher-level spatial objects such as people and vehicles. The da.ta.
`
`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 Ima.ge Understanding Environments (IUE) program [16] specifies a spatial rep(cid:173)
`
`resentation to meet the needs of a wide variety of computer vision applications. An
`
`IUE spat