`United States Patent No. 7,868,912
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`
`BEFORE THE PATE NT 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 & IPR2019-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. IPR20 19-00235 and IPR20 19-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, I7arabow, 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 oflibrary science practices, as well as my knowledge of the practices at
`
`the Massachusetts Institute of Technology ("MIT") Libraries.
`
`4.
`
`I earned a Master's ofijbrary 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
`
`ofFinnegan since 2013, and from 2005-2013, I worked in the Library Department
`
`ofFish & Richardson P.C.
`
`2
`
`
`
`Case Nos. IPR20 19-0023 5 and IPR20 19-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 ofthe 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 IPR20 19-
`
`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 Cis a true and correct copy of the MARC record
`
`of the MIT Libraries for its copy of Kellogg.
`
`9.
`
`Attached as r;:xhibit D (Exhibit 1005 to the Petition in IPR20 19-
`
`00235) is a true and accurate copy of B. Flinchbaugh et al., "Autonomous Video
`
`Surveillance," SPIE Proceedings, 25th AIPR Workshop: Emerging Applications of
`
`Computer Vision, Feb. 26, 1997, Vol. 2962, p. 144-151 ("Flinchbaugh"), obtained
`
`from the MIT Libraries.
`
`10. Attached as Exhibit Eisa true and correct copy ofthe MARC record
`
`of the Library of Congress for its copy of the SPIE 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 is a true and correct copy of the MARC record
`
`of the MIT Libraries for its copy of the SPIE Proceedings publication that includes
`
`Flinchbaugh.
`
`12. Attached as Exhibit G (Exhibit 1004 in each Petition in IPR20 19-
`
`00235 and IPR20 19-00236) is a true and correct copy of. Brill et al., "Event
`
`Recognition and Reliability Improvements for the Autonomous Video Surveillance
`
`System," Proceedings ofthe 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.
`
`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.
`
`4
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`16.
`
`Each field in a MARC record provides information about the
`
`cataloged item. MARC uses a simple three-digit numeric code (from 00 1-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.
`
`Kellogg
`
`19. As indicated in Exhibit A (Exhibit 1003 to the Petition in IPR20 19-
`
`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.
`
`5
`
`
`
`Case Nos. IPR20 19-00235 and IPR20 19-00236
`United States Patent No. 7,868,912
`
`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 refened 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
`
`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' cunent and prior practices, Kellogg would have been
`
`6
`
`
`
`Case Nos. IPR20 19-00235 and IPR20 19-00236
`United States Patent No. 7,868,912
`
`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
`
`Bibliography, Flinchbaugh cites to Kellogg (reference [4] on p. 151 ). As
`
`addressed below, Flinchbaugh was published in SPIE Volume 2962, which
`
`corresponds to the Proceedings from the 25th Annual AIPR Workshop on
`
`Emerging Applications of Computer Vision. The Workshop was held October 16-
`
`18, 1996, 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 Non circulating Collection 1,
`
`7
`
`
`
`Case Nos. IPR20 19-00235 and IPR20 19-00236
`United States Patent No. 7,868,912
`
`Noncirculating Collection 3, and in microfiche form in the Barker Jjbrary, 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 IPR20 19-00235) was published in the Proceedings of the 25th AIPR Workshop:
`
`Emerging Applications of Computer Vision, SPIE Vol. 2962. The Workshop was
`
`held in Washington, D.C. during October 16-18, 1996, and the Proceedings was
`
`published by SPIE (The International Society for Optical Engineering). Ex. D at 1.
`
`In view of the above and the following, Flinchbaugh was published and accessible
`
`to the public before October 1999.
`
`28.
`
`Page 2 of Exhibit D shows a copyright date of 1997. The edition of
`
`the SPIE Proceedings that was published with Flinchbaugh is Volume 2962, and it
`
`was "Printed in the United States of America." Ex. D at 2.
`
`29. Although the copyright date of Flinchbaugh is listed as 1997, it
`
`appears that Flinchbaugh was actually published before that, in 1996. First, as
`
`noted above, the Workshop was held in Washington, D.C. during October 16-18,
`
`1996. Second, a copy of Flinchbaugh was received and cataloged by the Library
`
`of Congress in November 1996. See Ex. E at 1. Exhibit E is the MARC record for
`
`8
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`the SPIE Proceedings, including Flinchbaugh, that was obtained from the Library
`
`of Congress. As shown in field 008 near the top of page 2 of Exhibit E,
`
`Flinchbaugh was cataloged by the library on November 21, 1996. Based on
`
`standard library practices, this reference would have been shelved shortly after it
`
`was cataloged (i.e., within a few days or weeks). Collectively, Exhibits D and E
`
`show that Flinchbaugh was published and accessible to the public years before
`
`October 1999.
`
`30.
`
`Further evidence of the publication and public availability of
`
`Flinchbaugh can be found in Exhibit F, which is the MARC record for the SPIE
`
`Proceedings, including Flinchbaugh, that was obtained from the MIT Libraries.
`
`As shown in field 008 on page 1 of Exhibit F, Flinchbaugh was cataloged by the
`
`library on March 10, 1997. Based on standard library practices and my
`
`understanding of the practices of the MIT Libraries, this reference would have
`
`been shelved shortly after it was cataloged (i.e., within a few days or weeks) and
`
`accessible to the public before October 1999.
`
`31.
`
`For the avoidance of any doubt, I note that on April 8, 2011, online
`
`access to Flinchbaugh was provided to certain MIT-associated individuals, as
`
`indicated by the fields 008 and 8528 and the URL entry at the top of page 2 of
`
`Exhibit F. Also, on June 23, 2001, the SPIE Proceedings, including Flinchbaugh,
`
`was archived at the MIT Library Storage Annex ("LSA"), as indicated by the
`
`9
`
`
`
`Case Nos. IPR2019-00235 and IPR2019-00236
`United States Patent No. 7,868,912
`
`second 008 field and subsequent 8520 entry on page 2 of Exhibit F. 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
`
`IPR20 19-0023 5 and IPR20 19-0023 6) 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
`
`FOR PUBLIC RELEASE" with "DISTRIBUTION UNLIMITED." Ex. Gat 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 ofExhibit 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.
`
`10
`
`
`
`Case Nos . .IPR20 19-00235 and IPR20 19-00236
`United States Patent No. 7,868,912
`
`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 ncar the top of page 2 of Exhibit I 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.
`
`3 5.
`
`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
`
`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
`
`prim· to October 1999.
`
`I declare under penalty of perjury that the foregoing is true and correct.
`
`Executed on November 9, 2018 in Washington, D.C.
`
`Emily R. Florio
`
`11
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`EXHIBIT A
`EXHIBIT A
`
`
`Axis Exhibit 1007, Page 12 of 154
`
`
`
`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
`Author ................ D~~~~~~~~~ ~f· El~~~;i~·~. E~~i~~;Jn~ ~~~;---flci~~~~
`/ } /
`j
`ril
`, 1993
`Signature redacted
`
`.
`
`Certified by .................................. -.-.r• ... ·v •.••• ·- .................. .
`Alex P. Pentland
`Associate Professor of Media Arts and Sciences
`. Thesis Supervi§or
`Signature redacted
`Certified by ...................................... ·r · · · · · · · ... ,. · ·~· · · · · · · · · ..... , -· r
`Bruce E. Flinchbaugh
`Manager of Image Understandin~ra~h a~ruments
`. >-:? /J
`/"/ / // / ~s/supervisor
`
`Signature redacted
`Accepted by ........... ~; . . 1 ;/· .) .. 07 .. ·r· ·v .. . 6~~~];~n·L.· ~i~~ri~
`
`Ch7on, ~rtmental Committee on Graduate Students
`MASSACHUSETIS INSTITUTE
`OF TFr.HNOLOGY
`rJUL 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 Understanding Environments .
`2.2.5 PROBE ....
`2.2.6 Spatial Indices
`
`2.3 Tern poral 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
`
`9
`
`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
`
`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 Tern poral 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
`
`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 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(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, 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
`
`
`
`data model and concurrent access, along 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
`
`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(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 Database with GEometric Reasoning) "whiteboard" database 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 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(cid:173)
`
`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(cid:173)
`
`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(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 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(cid:173)
`
`resentation to meet the needs of a wide variety of computer vision applications. An
`
`IUE spatial object is defined by a set of points; this point set can be concrete (a list
`
`of all the points) or abstract (an equation defining the points in the object). IUE
`
`spatial objects are manipulated through set operations- complex objects can be con(cid:173)
`
`structed through conjunction and disjunction of point sets. In addition to its point
`
`set, each spatial object also defines a bounding box, a centroid, and other attributes
`
`for different, and perhaps more efficient, methods of spatial manipulation. The IUE
`
`specification only briefly discusses data transfer and does not provide database sup(cid:173)
`
`port for storage and retrieval of spatial information.
`
`2.2.5 PROBE
`
`The PROBE database [15], developed at the Computer Corporation of America,
`
`extends an object-orien