Abstract:
A method and system designed to augment, rather than replace, the work habits of its users. These work habits include practices such as drawing on Post-it™ notes using a symbolic language. The system observes and understands the language used on the Post-it notes and the system assigns meaning simultaneously to objects in both the physical and virtual worlds. Since the data is preserved in physical form, the physical documents serve as a back-up in the case of electronic system failure. With the present invention users can rollout a primary paper document such as a map, register it, and place secondary physical documents on the map. The secondary physical documents can be moved from one place to another on the primary document. Once an object is augmented, users can modify the meaning represented by it, ask questions about that representation, view it in virtual reality, or give directions to it, all with speech and gestures.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     Priority is claimed for the following applications: 
     1) Co-pending application serial number 60/188,524 filed 3/10/00. 
     2) Co-pending application serial Number 60/188,553 filed 3/10/00. 
    
    
     STATEMENT CONCERNING FEDERALLY SPONSORED RESEARCH 
     The development of this invention was in part supported by government contracts administered by the Information Systems Office of DARPA under contract number N66001-99-D-8503, and also in part by ONR grants: N00014-95-1-1164, N00014-99-1-0377, and N00014-99-1-0380. 
    
    
     COMPUTER PROGRAM LISTING APPENDIX AND TO OTHER APPENDICES 
     Appendix A is “Computer Program Listing Appendix” on a CD (Compact Disk). containing the following 17 text files consisting of 18427730 bytes. 
     
       
         
               
               
               
               
             
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 File Name 
                 File Size 
                 Creation Date 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 aaaAgents.uue 
                 200782 
                 03/01/2001 
               
               
                   
                 aaaLib.uue 
                 188119 
                 03/01/2001 
               
               
                   
                 blank_bmp.uue 
                 135554 
                 03/05/2001 
               
               
                   
                 blank_map.uue 
                 56 
                 03/05/2001 
               
               
                   
                 bridge.uue 
                 1930063 
                 03/05/2001 
               
               
                   
                 coord_rdr.uue 
                 44300 
                 03/05/2001 
               
               
                   
                 EggTimer.uue 
                 45179 
                 03/05/2001 
               
               
                   
                 GateKeeper.uue 
                 94929 
                 03/01/2001 
               
               
                   
                 Gesture.uue 
                 10643440 
                 03/01/2001 
               
               
                   
                 mm_ogi_nl.uue 
                 2031646 
                 03/05/2001 
               
               
                   
                 multiparse.uue 
                 1980857 
                 03/05/2001 
               
               
                   
                 QuickSet.uue 
                 784537 
                 03/01/2001 
               
               
                   
                 rasa_simple.uue 
                 26288 
                 03/01/2001 
               
               
                   
                 Speech.uue 
                 191979 
                 03/01/2001 
               
               
                   
                 startup.uue 
                 500 
                 03/05/2001 
               
               
                   
                 TermEx.uue 
                 39179 
                 03/01/2001 
               
               
                   
                 tts.uue 
                 90322 
                 03/05/2001 
               
               
                   
                   
               
             
          
         
       
     
     Appendix B is a copy of forty two page co-pending application No. 60/188,524 filed Mar. 10, 2000. 
     Appendix C is a copy of twelve page co-pending application No. 60/188,553 filed Mar. 10, 2000. 
     Appendix D is a copy of a seven page document entitled “Unification-based Multi-modal Parsing” by Michael Johnson 
     Appendix E is a copy of a seven page document entitled “Creating Tangible Interfaces by Augmenting Physical Objects with multi-modal Language” by David McGee and Philip Cohen. 
     Appendix F is a copy of a nine page document entitled “Something from Nothing: Augmenting a paper-based work practice via multimodal interaction” by David R. McGee, Philip R. Cohen and Lizhong Wu. 
     All of the above listed appendices A to F are hereby incorporated herein in their entirety by reference. 
     FIELD OF THE INVENTION 
     The present invention relates to computer systems and more particularly to a method and system which provides for interaction between a user and a computer system. 
     BACKGROUND OF THE INVENTION 
     The prior art provides a number of methods for computationally augmenting natural, non-digital settings. The term augmenting is herein used to mean extending a physical artifact so that it represents or denotes something more or something new, and thereby gains computation meaning and behavior. 
     A paper, by Underkoffler, J. and Ishii, H., Urp: “A luminous-tangible Workbench for Urban Planning and Design”, published in the  Proceedings of the ACM Conference on Human Factors in Computing Systems  (CHI &#39;99), May 1999, ACM 
     Press, 386-393 describes a system called “Urp” that planners use to build models, rulers, clocks, and other physical objects. Objects are tagged by patterns of colored dots, and if a pattern is recognized, a vision system sends Urp the associated object&#39;s location. With Urp, augmented objects “behave” as you would expect them to: rulers measure distances, clocks mark time, and so on. The object&#39;s physical characteristics and the environment it inhabits govern these expectations 
     A paper by Wellner, P.,“Interacting with paper on the DigitalDesk” published in the Communications of the ACM, 1993. 36(7): 87-96 describes a system that augments office work by introducing paper into a workstation environment. Through computer vision, users can point at numbers on a real piece of paper, in response to which the system performs optical character recognition and pastes the recognized number into the system&#39;s calculator. Similarly, regions of real paper, like a sketch on a napkin, can be cut and pasted into a painting program. 
     A paper by Ishii, H. and Ullmer, B., “Tangible bits: towards seamless interfaces between people, bits and atoms”, published in the  Proceedings of the ACM Conference on Human Factors in Computing Systems  (CHI &#39;97), March 1997, ACM Press, 234-241 describes a system with a shared whiteboard, uses barcode-tagged cards to hold digital ink. However, the ink can only be retrieved when scanned by a barcode reader connected to a desktop computer. 
     A paper by Coen, M. H., “Design principles for intelligent environments” published in the  Proceedings of the Conference on Artificial Intelligence  (AAAI &#39;98), July 1998, American Association for Artificial Intelligence, 547-554 describes a system that uses Post-it Notes to activate behaviors in the room. Different colored Post-it Notes are used so that they can be easily distinguished from each other and from the supporting table by a vision system. Ink on each note is used only to remind the user of the action to expect, not as input to the system. 
     A system call “Passage ” is described in a paper by Streitz, N. A., Geibler, J., and Holmer, T., “Roomware for cooperative buildings: integrated design of architectural spaces and information spaces” published in the  Proceedings of the First International Workshop on Cooperative Buildings: Integrating Information, Organization, and Architecture  (CoBuild &#39;98), February 1998, Springer-Verlag, 4-21 and a technique termed RFID (radio frequency identifier) is described in a paper by Want, R., Fishkin, K. P., Gujar, A., and Harrison, B. L., Bridging physical and virtual worlds with electronic tags, in the  Proceedings of the ACM Conference on Human Factors in Computing Systems  (CHI &#39;99), May 1999, ACM Press, 370-377. These systems interpret the human act of augmenting paper in order to create a digital representation and provide some flexibility in changing that data. Within the Passage concept, meaning can be linked graphically to a physical object whenever that object is placed on a “bridge.” In the initial prototype, the bridge is a scale and recognizes objects based on their weight. With the RFID system, tags are hidden in books, documents, watches, etc. As with Passage, associational augmentations can be formed when the tags are first detected. These systems do not yet support a pre-existing work practice, nor can users learn what information is associated with an object unless the users and the object are adjacent to a bridge or detector. More generally, associational augmentation methods like these and others, such as the use of colored dots, glyphs, or bar codes, fail to present the linked digital information to the user without the assistance of technology. 
     A paper by Moran, T. P., Saund, E., Melle, W. V., Bryll, R., Gujar, A. U., Fishkin, K. P., and Harrison, B. L., “The ins and outs of collaborative walls: Demonstrating the Collaborage concept”, published in the  Proceedings of the ACM Conference on Human Factors in Computing Systems  (CHI &#39;99), May 15-20, 1999, ACM Press, CHI&#39;99 Extended Abstracts, 192-193T herein called the Collaborage concept. The Collaborage concept characterizes augmented systems consisting of a board and various tagged physical information items. Several such prototypes have been built. One of these prototypes is an In/Out board system with glyph-tagged magnetized photos that can be slid from the Out column to the In column and vice-versa. Within seconds, a vision system recognizes the change in location of the glyph and an In/Out web page is updated to reflect the change in status. If the system were to fail, individuals could still check the physical In/Out board, move their picture from one column to the other, add hand-written annotations, and walk away with up-to-date information. Because objects are augmented using glyphs rather than a natural language, users cannot easily add new digital information to the board. For example, a new employee cannot use any magnet and photograph and expect it to work in the Collaborage system. 
     SUMMARY OF THE PRESENT INVENTION 
     The present invention provides a method and system designed to augment, rather than replace, the work habits of its users. These work habits include practices such as drawing on secondary physical documents (e.g. Post-it™ notes) using a symbolic language and placing these secondary physical documents on a primary physical document such as a map. With the present invention the system observes and understands the language used on the primary and secondary physical documents and the system assigns meaning simultaneously to objects in both the physical and virtual worlds. Since the data is preserved in physical form, the physical documents serve as a back-up in the case of electronic system failure. With the present invention users can utilize a paper primary physical document such as a map, register it, and augment the primary physical document by placing secondary physical documents on the primary physical document. The secondary physical documents can be moved from one place to another on the primary document. Once an object is augmented, users can modify the meaning represented by it, ask questions about that representation, view it in virtual reality, or give directions to it, all with speech and gestures. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is an overall diagram of the system. 
     FIG. 2 is a block flow diagram showing how a document is registered. 
     FIG. 3 is an example of the steps performed by the system. 
     FIG. 4 is a more detailed flow diagram of the operations performed by the system. 
     FIGS. 5,  6  and  7  show how data feature structure and multi-modal grammar rules. 
     FIG. 8 is a program flow diagram. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 is an overall diagram of a first embodiment of the present invention. The system combines the advantages of a paper system and the advantages of an electronic computer system. These advantages are achieved without adding substantially to the task. The user continues to employ familiar tools and procedures. The physical artifacts normally employed by the user become a computational interface. 
     The human operator  100  and various input and output components of the system are positioned near a large touch board  104 . A primary physical document, that is, a map  103  is positioned on the touch board  104 . The human operator  100  communicates with the system via a number of input-output devices that are connected to a computer  112 . 
     The input-output devices that are connected to computer  112  include a microphone  101 , a speaker  102 , a keyboard  106 , a digital ink tablet  108 , and a projector  110 . The touch board  104  also provides input to computer. The digital ink tablet  108  is operated by a computer  108 A which communicates with computer  112 . The digital ink tablet  108  may be the commercially available tablet marketed under the trademark “Crosspad Ipenpro” marketed by Cross Computing Inc. The touch board  104  may be the commercially available touch board marketed under the trademark “SMART Board”. 
     The system provides the human operator  100  with multi-modal interaction with the computer system. The human operator  100  can issue instructions and provide information via microphone  101  and keyboard  106 . The operator can receive information via the audio speaker  102 . A projector  110  projects images on the map  103  that are visible to the operator. As will be explained in detail later, the digital ink tablet  108  and the touch board  104  also serve as devices through which the operator communicates with the computer system. The line  131  in FIG. 1 indicates that the operator writes on Post-it notes and physically places them on touch board  104 . The map  103  is hereinafter referred to as the primary physical document. The Post-it notes are hereinafter referred to as the secondary physical document. The computer  112  includes a number of computer programs designated  112   a ,  112   b ,  112   c , and  112   x . The functions which are performed by these computers programs are hereinafter described. 
     The first preferred embodiment of the invention is directed to a system which could for example be used in a military command post. The central feature in a typical military command post is a map. Typically when unit positions are reported over the radio, an officer draws a symbol depicting the unit&#39;s strength, composition, and other relevant features on an adhesive note such as the widely used “Post™” notes. The Post-it note is next placed at the appropriate location on the map. It is the job of users in each command post to keep all of the information on the map as accurate and as complete as possible, so that their superiors can make critical decisions efficiently and quickly. 
     Typically units are identified on the Post-it notes and on the map by special unit symbols. There is a standard format for the pictograms that comprise the unit symbols. The unit symbols are part of a composable language that is used by many military organizations. The location of the Post-it notes on the map represent a unit&#39;s position in the real world 
     Often there are from several dozen to several hundred Post-it notes arrayed on a typical command post map. In addition to the information represented by the Post-it notes on the map, auxiliary information is often available on nearby charts. In a typical command post, anyone can observe the map and thereby have a clear picture of the current state of affairs. 
     The present invention augments the functions performed in a typical command post without requiring the operator to drastically change the normal mode of operating the command post. The system captures the relevant information in electronic form so that it can be preserved, electronically analyzed and transmitted to remote locations. Furthermore, the relevant information is preserved in hard copy form so that in the event of electronic failure, the command post can continue to function. 
     The first step which must be performed with the present invention is to orient map  102  relative to touch board  104 . The orientation process is shown in block diagram form in FIG.  2 . As indicated by blocks  201  and  202 , the map is placed on the touch board  104 . Next the operator touches a location on the map, and speaks the coordinates of the position that was touched. As indicated by block  208 , the touch board  104  indicated to the system the position that was touched and the system registers that location on the board as having the coordinates that were spoken. The process is then repeated for a second point on the map as indicated by blocks  210  to  214 . Once the coordinates of two positions have been registered the system can correlate any other positions on touch board  104  with any coordinates on map  103 . 
     FIG. 3 illustrates a simple but illustrative set of steps performed by the system. As indicated by block  301 , the process illustrated in FIG. 3 begins when the operator writes or draws on a post-it note. The writing takes place while the post-it note is on digital ink tablet  108 , thus the writing is electronically captured and recognized. Next the operator physically moves the post it note and places it on touch board  104  (represented by line  131  in FIG.  1 ). The touch screen  104  detects when the operator presses the post-it note onto the board  104 . As indicated by block  307 , the system would then verbally request that the operator provide certain information about the unit represented by the post-it note that was placed on the map. The operator speaks the requested information and it is recognized by the system as indicated by block  309 . The system then creates an electronic image of the information and projects it onto board  104  via projector  110 . 
     At this point in the process, there is a posit-it note on board  104  which indicates certain information. This information is stored in computer  112  and the stored information is displayed on board  104  at the same location as the post-it note so that the electronic information can be verified. 
     FIG. 4 is a more detailed program flow diagram showing the operations performed. Blocks  401 ,  411 ,  421  and  431  illustrate the operator providing input to the system. The user can also type information into keyboard  106 . Block  448  indicates that the system provides output by projecting images onto board  104  via projector  110 . Block  442  indicates that the information acquired by the system can be transferred to another remotely located command post. The dark lines on blocks  401 ,  421  and  431  indicate that these are physical documents that retain information in the event of electronic system failure. The electronic information or data is stored in a data base  441 . 
     As an example of the operations performed by the system, block  401  indicates that the operator draws a symbol on a Post-it note. The drawing is done with the Post-it note on digital ink tablet  108  which electronically captures the material that is written. The symbol is recognized using the approach described in patent application No. 60/188,524 which is entitled “A robust Approach to Gestural and Multi-modal Recognition” which is hereby incorporated by reference. 
     Next, as indicated by block  404 , the meaning of the symbol is determined. For example, the user might draw a symbol for a “Recon Company”. This is a standard symbol which the system would recognize. This system has the attributes of name, size, etc. The system would ask the operator to input these via the microphone. As indicated by blocks  412  and  414 , the words are recognized. Recognition can be done by commercially available programs such as the “IBM VoiceType Application Factory” or by “Dragon Systems Naturally Speaking”. 
     As indicated by block  446 , the inputs from all the modalities are combined to determine if the input represents a new object, or a modification of an existing object. The input can also merely be a query about an existing object. 
     The data structure is shown in FIGS. 5,  6  and  7 . This data structure is described in the attached document entitled “Creating Tangible Interfaces by Augmenting Physical Objects with Multi-modal Language”. 
     FIG. 8 is a program flow diagram of the programs in computer  112  which implement this invention. A copy of the program is provided on a compact Disk which is appended hereto as Appendix A. FIG. 8 also shows some of the physical units. The touch board  104  which includes the map  103  is shown in FIG. 8 in more detail that in FIG.  1 . As indicated by block  802 , symbols are drawn on Post-it notes which are on digital ink tablet  108 . A symbol recognizer program  803  recognizes this symbol. The technology used by the symbol recognizer  803  is given in Appendix B. 
     Information spoken into microphone  101  is recognized by speech recognizer program  804  (this program performs step  412  shown in FIG.  4 ). Such programs are commercially available from companies including IBM and Dragon Systems Inc. The spoken information is parsed into grammar as shown in FIGS. 5,  6 , and  7  by Natural Language parser  826  (this is step  414  in FIG.  4 ). Gestures are parsed by Gesture parsing program  814  (this is what performs  404  and  424  in FIG.  4 ). The input information from the various input modalities is integrated by program  815  (this performs step  446  in FIG.  4 ). Information about the objects is stored in data base  813  and provides data to external systems  811  as desired (see steps  441  and  442  in FIG.  4 ). 
     The steps implemented by Multimodal integrator  815  are described in The attached paper entitled “Unification-based Multimodal Parsing”. (see also co-pending application No. 60/188,524 which is appended). 
     A program used to implement the preferred embodiment of the present invention is attached as an appendix on a CD. The attached CD includes the following files (all of which are incorporated herein by reference). 
     aaaAgents.uue—ASCII form of aaaAgents.jar: Java byte code for the AAA facilitator agent which enables the agents to communicate. 
     aaaLib.uue—ASCII form of aaaLib.jar: Java byte code for the agent communication part of the AAA facilitator and GateKeeper. 
     blank_bmp.uue—ASCII form of blank.bmp: A dummy blank map picture used by QuickSet as a map backdrop. 
     blank_map.uue—ASCII form of blank.map: A short text file describing a blank map for QuickSet. 
     bridge.uue—ASCII form of bridge.exe: A Prolog agent in x86 executable form which receives commands in Prolog feature-structure form and interprets them to transmit the commands further in Prolog standard functor form. 
     coord_rdr.uue—ASCII form of COORD.RDR: A text file from the US Government which describes the transformation of Universal Transverse Mercator map coordinates as used by the military into latitude-longitude coordinates. 
     EggTimer.uue—ASCII form of EggTimer.exe: A simple agent (x86 executable) which helps control timing for the multiparse agent. 
     GateKeeper.uue—ASCII form of GateKeeper.jar: Java byte code for the GateKeeper agent which acts as a storehouse for entities which may appear on the map, representing units, lines, points and such, and also executes commands related to such entities. 
     Gesture.uue—ASCII form of Gesture.exe: An agent (x86 executable) which receives messages consisting of a set of points representing a gesture on a map, and issues messages which represent the possible interpretations of these points as gestures. 
     mm_ogi_nl.uue—ASCII form of mm_ogi_nl.exe: A Prolog agent in x86 executable form which receives messages consisting of text interpretations of speech, and issues messages in Prolog feature-structure form for possible commands resulting from this speech text. 
     multiparse.uue—ASCII for multiparse.exe: A Prolog agent in x86 executable form which receives messages consisting of possible commands from of speech and also messages consisting of gestures, interprets the gestures as possible commands, and combines the possible speech and gesture commands according to certain rules into a combined unimodal or multimodal command made up of one or more feature structures. 
     QuickSet.uue—ASCII form of QuickSet.exe: An agent (x86 executable) which displays a map, the objects on the map, and allows the user to enter commands with speech and gesture. 
     rasa_simple.uue—ASCII form of rasa_simple.grm: A grammar file compatible with Microsoft Speech API 4.0 (SAPI 4), which instructs a SAPI-compliant speech recognition engine on how to interpret an audio stream as a series of words which represent commands compatible with the system of agents. 
     Speech.uue—ASCII form of Speech.exe: An agent (x86 executable) which employs a SAPI-4 or IBM VoiceType speech recognition engine to interpret the user&#39;s spoken input as text for possible commands. 
     startup.uue—ASCII form of startup.bat: A DOS-type batch file (text) as an example of how the agents may be started so as to work together. 
     TermEx.uue—ASCII form of TermEx.jar: Java byte code supporting the GateKeeper, helping it to store objects and execute operations on them, by assisting in the conversion of objects from Prolog agent messages to native Java format. 
     tts.uue—ASCII form of TTS.exe: An agent (x86 executable) which receives text messages and employs SAPI text-to-speech to produce audible speech audio output so as to as help inform the user of certain events. 
     Various alternative embodiments of the invention are also possible without departing from the spirit and scope of the invention. The present invention can be used with other types of technologies. For example the invention can be used with the technologies shown in U.S. Pat. No. 5,862,271 (the contents of which are incorporated herein by reference) and on the web site: http://www.anoto.com/. The referenced web site describes a special type of pre-printed paper as follows: 
     “On this paper is printed the Anoto™ pattern, consisting of very small dots slightly displaced from a grid structure. A minute section of the pattern will give you your exact location on the full pattern. As you write or draw on the paper with your Anoto pen, the pen creates a digital trace of whatever you do. This information is stored in the pen until you tick the appropriate check-box. The information is then forwarded from your Anoto pen directly to your nearby personal computer, or by a Bluetooth™ device—such as a Bluetooth enabled mobile phone—to any computer, mobile phone or information bank in the world via the Internet. 
     Anoto functionality allows you to send whatever you write or draw directly to your nearby personal computer, or via the Internet to any computer, mobile phone or information bank in the world.” 
     In one alternative embodiment of the present invention the above described paper is used instead of the touch board  104  and/or the digital ink tablet  108 . In such an embodiment, the information written on the paper and/or the Post-it note is automatically captured. Hence a physical and machine record are simultaneously produced. 
     In the military command post environment described above, the tactical situation as recorded on the paper can be automatically captured, analyzed and electronically relayed to other command centers. In the event of a power failure, the physical paper forms an appropriate back up record. In the first embodiment described herein the primary physical document is map  103  and the secondary physical documents are Post-it notes. It should be understood that various and sundry other types of primary physical documents may be employed with the invention. Likewise a wide variety of types of secondary physical documents could be used. The secondary physical documents could for example be written material on the heads of push pins. 
     In yet other alternate embodiments, one or more machine vision systems is used in place of one or both the touch board  104  and the ink tablet  108 . For example, in one alternate embodiment, the primary physical document (e.g. map  103 ) is placed on a non-electronic board. When the secondary documents are placed on the non-electronic board, a machine vision system is used to detect the location where the secondary documents are placed and to detect any drawings that are made on the primary physical document. The same (or a different) machine vision system can be used to determine what is written on the secondary physical documents in place of ink tablet  108 . Thus, either one or both the touch board  104  and/or the ink table  108  can be replaced by a machine vision system. 
     While the invention has been described with respect to various embodiments thereof, it should be appreciated that various changes in form and detail can be made without departing from the spirit and scope of the present invention.