System and method for entering text in a virtual environment

[0002] This application makes reference to, incorporates the same herein, and claims all benefits accruing under 35 U.S.C. §119 from an provisional application entitled SYSTEM AND METHOD FOR ENTERING TEXT IN A VIRTUAL WORLD earlier filed in the U.S. Patent Office on Jul. 31, 1998, and there duly assigned Serial No. 60/094,910.

[0003] 1. Field of the Invention

[0004] The present invention relates generally to data input in a virtual environment and, more particularly, to inputting words and sentences by means of sensory gloves.

[0005] 2. Description of the Related Art

[0006] A virtual environment is one where the user is placed entirely inside a computer-generated world. This is typically done by means of various types of communication gear attached or strapped to the user's body—for example, goggles to create a visual tableau, earphones to provide an audible counterpart, and other instruments that generate sensory input for the user. In order to immerse the user in a virtual world, this gear serves two functions: one is to provide sensory input to the user, the other is to provide the virtual world system with information about the user. For instance, headgear will tell the system the direction of the user's view and sensory gloves will tell the relative locations of the hands and fingers of the user.

[0007] In the virtual environment, traditional means of inputting data to the system are neither available nor practical. Because a keyboard cannot be easily attached to the human body, the user usually has to leave the virtual environment in order to enter text data. This inability to enter key data such as text in a virtual environment will become more problematic over time, as the potential of virtual world representations of complex file systems, flowcharts, architectural drawings, and event simulations are realized.

[0008] Therefore, other means of text input need to be created for virtual environments. While there are many possible solutions to this problem, including speech recognition, some type of hand or finger manipulation seems to be the most intuitive way to enter text.

[0009] Sensory gloves have been considered as appropriate instruments of such text entry. Grimes, U.S. Pat. No. 4,414,537, discloses a glove with sensors positioned to detect joint angles and positions of each finger and further discloses using such a glove to replace a keyboard. However, Grimes' user must learn a new set of static gestures to specify letters. Although Grimes discloses entering data into a virtual world system using sensory gloves, the user must learn new skills that are not intuitive or obvious.

[0010] Zimmerman et al., U.S. Pat. No. 4,988,981, discloses sensory gloves that could be used to manipulate objects in a virtual world, such as moving a cursor or performing operations based on gesture and position of the user's hands. The virtual object to be manipulated in Zimmerman et al. could be a representation of an input device such as a keyboard.

[0011] There are severe limitations on the prior art use of sensory gloves for key input. A first problem involves the ability to recognize when a simulated finger press is being made. Sensory gloves are typically used to recognize only coarse hand gestures, such as select, grasp, and drop, not the fine gestures needed to differentiate individual finger movements. When fingers are used to represent individual keys, low-cost low-resolution sensory gloves present several problems. Correlated finger movements called sympathetic finger movements, which occur when one finger is pressed down to input a key and the neighboring finger moves a certain distance along with it, create confusing data. For example, FIG. 2A illustrates what happens as a person simulates a press of the pinkie finger. As the pinkie finger presses down (indicated by the peak labeled A), the ring finger (line B) parallels the movement. If the ring finger has a lower threshold (value at which the system determines there has been a simulated press) than the pinkie, the system may determine that the ring finger was the one being pressed.

[0012] The phenomenon of finger amplitude variation is also a problem. Two different users may use differing amounts of movement to indicate a finger press. In addition, over time a single user varies the amount of movement to indicate a press. For example, FIG. 2B shows the same intended pinkie press as FIG. 2A, but made ten minutes later. Although the user started by using a right-hand index finger press value of 130 in FIG. 2A, the user is only using a value of 55 when making the same finger press in FIG. 2B.

[0013] Lastly, the measurement of finger movements is inherently noisy, which causes false peaks. More exactly, sympathetic finger motions, minor motions caused by shaking hands, and glove output noise produce jagged curves in the finger motion data, as shown in FIG. 2C. These jagged curves can lead the system to both missing presses and recognizing unintended ones.

[0014] A second problem is caused by the fact we are limited to ten fingers, but we use a 26-letter alphabet with punctuation symbols. If every finger of the sensory gloves is used to represent an individual key, it would not be possible to represent an entire alphanumeric keyboard by single key entry. It would be possible to use combinations of individual keystrokes to represent each alphanumeric character, but such a procedure would be burdensome.

[0015] One solution to this problem is to use an overloaded keyboard, whereby each key, or finger, would represent several different alphanumeric characters. Such a keyboard layout is shown in FIG. 1, where multiple letters are mapped to certain fingers. The left-hand ring finger, for example, could represent “s”, “v”, and “x”, the right-hand index finger could represent “j”, “u,” “y”, “h” and “n”, and so on for each finger. This presents a new difficulty: how will the virtual system be able to tell which alphanumeric character was intended, out of the multiple characters that one key input represents?

[0016] This character ambiguity can be resolved by exploiting the statistical and grammatical constraints of language in order to reconstruct the text. This process of disambiguation uses probabilistic analysis and a dictionary. There have been various approaches to this overloaded keyboard problem in the field of text entry. One method decodes the text word-by-word using a weighted tree structure called a “Probabilistic History Tree” (See, Litvak and Shamir, Efficient algorithms for constructing and employing variable-length Markov models of language,Technical Report, Dept. of Computer Science, Tel-Aviv University, Israel, 1996). Another method, which has also been applied to handwriting recognition, decodes the text sentence-by-sentence using a hash table (See, H. Rau and S. Skiena, Dialing for documents: An experiment in information theory,Journal of Visual Languages and Computing, pages 79-95, 1996). But all of these methods were directed towards the overloaded alphabetic keyboard of a telephone keypad.

[0017] Therefore, a need exists for a method and system that can reconstruct text from ambiguous characters, as well as reliably recognize the fine movements that represent presses using low-cost, low-resolution sensory gloves.

[0018] It is therefore an object of the present invention to provide a system and method of recognizing fine finger movements, such as key entry on a virtual keyboard, using low-cost, low-resolution sensory gloves. In particular, the system and method solves the problem of sympathetic finger movements by examining the relative motions of neighboring fingers. The system and method also solves the problem of finger amplitude variation by performing an initial calibration, providing the user with visual and aural feedback, and using dynamic thresholds to evaluate the finger movements. Lastly, the system and method eliminates the inherent noise in the finger movement data by using a low-pass Gaussian filter.

[0019] It is another object of the present invention to provide a system and method of resolving ambiguous characters entered on an overloaded keyboard. This ambiguous character resolution, or reconstruction, is performed by recognizing blank characters, thus separating out words as key sequences; matching each key sequence with one or more words in a dictionary; constructing or partially matching the words with no dictionary match; generating all possible partial sentences from the possible words; and then determining the most likely partial sentence by assigning probabilities to each possible partial sentence.

[0020] The present invention builds on the idea that sensory gloves can be used to create a virtual keyboard, where finger movements can be translated into key entry by a virtual world system. In the exemplary embodiment, the user does not actually see a simulated keyboard in the video goggles, but is shown which fingers represent which letters and when the system recognizes a finger press as text input. In the following text, the term “press” is used to describe a finger motion that is mimicking a finger press on a keyboard, and is intended by the user to indicate that the key represented by that finger has been pressed. The terms “keyboard layout” refers to how the alphanumeric characters are assigned to each finger and “keyboard” to the system by which the sensory gloves are manipulated to represent alphanumeric characters.

[0021] FIG. 1 is an example of a keyboard layout on the fingers of a pair of sensory gloves;

[0022] FIGS. 2A, 2B, 2C, and 2D are graphs of glove output over time;

[0023] FIG. 3 is an overall flowchart of the finger press recognition portion of the text entry process in accordance with the present invention;

[0024] FIG. 4 is a detailed sub-flowchart of the INITIALIZE DICTIONARY step 100 from FIG. 3;

[0025] FIG. 5 is a detailed sub-flowchart of the INITIALIZE GLOVE step 200 from FIG. 3;

[0026] FIG. 6 is a detailed sub-flowchart of the CALIBRATION STAGE step 300 from FIG. 3;

[0027] FIG. 7 is an overall flowchart of the reconstruction engine portion of the text entry process in accordance with the present invention;

[0028] FIG. 8 is a detailed sub-flowchart of the RECONSTRUCT PARTIAL SENTENCE step 1300 from FIG. 7; and

[0029] FIG. 9 is a chart illustrating an example of how a word might be reconstructed in accordance with the present invention.

[0030] The present invention allows low-cost, low-resolution sensory gloves to be used in the system and method. In the preferred embodiment, the 5^thGlove manufactured by the General Reality Company is used. In these gloves, each finger has only one sensor giving its angular position, consisting of a fully enclosed fiber optic bend sensor. Each finger is sampled at a rate of 200 Hz, producing an 8-bit sample that describes one of 256 possible positions per finger.

[0031] A computer system is used to create the virtual environment. In the preferred embodiment, a Pentium Pro™ PC with 512 MB of memory is used. In addition, some manner of visualizing a virtual environment is required, such as goggles. The preferred method provides a display window which shows the positions of all the fingers, indicating by both color and orientation which finger has been pressed, as well as a text window showing what words the system has reconstructed from the finger presses. In the following description, the system and method is broken down into two sections, Finger Press Recognition and Reconstruction Engine. After those sections, an example is given.

[0032] A. Finger Press Recognition

[0033] As shown in FIG. 3, the text entry procedure starts with initializing the dictionary at step 100. In the preferred embodiment, the dictionary was built from the UNIX word list, enhanced by other common words. The dictionary, which should contain at least the commonly used words, has a frequency count associated with each word. The dictionary is designed as a balance between including as many words as possible, which may result in frequent collisions between word possibilities, and only including the most common words, which may result in unrecognized words.

[0034] Initializing step 100 is further described in detail in FIG. 4, where a word is selected from the dictionary (step 110), and then that word is converted into its key digit equivalent (step 120). For example, the word “cat” might become “228,” if the letters “c” and “a” were both overloaded on the finger labeled key 2, and the letter “t” was on the finger labeled key 8. Then, at step 130, the digitized key word is stored in data lookup structure such as a trie (a digital search tree). The preferred embodiment uses a trie, a digital search tree, rather than other structures such as a hash table as the main dictionary data structure. By doing a depth-first traversal of the appropriate portion of the trie data structure, all dictionary strings that partially match a query string can be efficiently retrieved. Hash tables, which are used in the prior art, cannot efficiently support such queries without hashing multiple copies of each string, which requires a prohibitive amount of space. Further, there is data that suggests the trie structures can be built roughly four times faster than an analogous hash table (Francine Evans, Efficient Interaction Techniques in Virtual Environments,Dissertation, Dept. of Computer Science, State University of New York at Stony Brook, 1998).

[0035] After storing that word in the data structure, the process loops back to select another word. This process continues until all the words have been placed in the data structure.

[0036] Once the dictionary has been initialized, the gloves are initialized at step 200 in FIG. 3. As shown in FIG. 5, this initialization starts by setting the threshold value of each finger to zero (step 210). At step 220 in FIG. 5, the ports of the computer are opened so the computer can read the data from the sensory gloves. Finally, at step 230, the specified keyboard is mapped to the fingers. In the preferred embodiment of the invention, the user specifies his or her own keyboard layout. Although the user is forced to overload some fingers with multiple symbols, the user may decide to load the same symbol on multiple fingers, such as a space on both thumbs. There are many possible ways of choosing the keyboard layout. The results of experiment suggest that at least 6 keys or fingers be used to map the entire alphabet (Francine Evans, Efficient Interaction Techniques in Virtual Environments,Dissertation, Dept. of Computer Science, State University of New York at Stony Brook, 1998). Consecutive letters may be placed on successive keys or fingers, in the same manner as telephone keypads, which have three letters per numeral. With the idea that reconstructing text is the end result of this system, a keyboard could be laid out so that each individual finger is pressed with the same frequency. The principles of information theory suggest that such an equal frequency layout should lead to greater reconstruction accuracy. The keyboard could also mimic the traditional QWERTY layout of most keyboards or use ergonomic principles to create a minimum-motion keyboard.

[0037] After the gloves are initialized, they are calibrated (step 300 in FIG. 3). The process of calibration helps to eliminate the problems associated with finger amplitude variation. As shown in FIG. 6, the calibration starts with the computer requesting the user to enter some text (step 310). While the user is entering the text, the computer is monitoring all of the fingers through its ports, and performing a checking loop on each one. In that loop, the computer first stores the current finger value (step 320) and then it compares the stored value with the threshold value of that finger (step 330). If the stored value is greater than the threshold value, the computer adds the threshold value to the stored value, divides that sum by two, and stores the result as the new threshold value (step 340). After step 340 or, if the stored value was less than the threshold value in step 330, the computer checks to see if the calibration time period has elapsed (step 350). If it has, that ends the calibration sequence. If not, the computer goes through the checking loop on the next finger.

[0038] After the calibration sequence, the computer is ready to take text entry from the user. In step 400, the computer monitors the sensory gloves by checking the data from the ports connected to each finger. In the preferred embodiment, this data is pre-processed by a Gaussian low-pass filter in order to remove noise. Noise, such as sympathetic finger motions, minor motions caused by shaking hands, and glove output noise, produce jagged curves in the finger motion data, as shown in FIG. 2C. In the prior art, jagged curves can lead to missing presses and recognizing unintended ones. As shown in FIG. 2D, the addition of a low-pass filter eliminates the jagged variations caused by noise, thereby alleviating the problem.

[0039] When monitoring, the computer first checks if any of the finger presses has passed their individual threshold values in step 410. If not, the computer then checks to see if there was a light press in step 420. As discussed above, light presses may occur as the user tires over time and uses less finger movement to indicate a press. The computer checks by taking all current finger values and comparing each one to their threshold value minus a constant value. This constant can be specified beforehand. If the current value of one or more fingers is greater than or equal to the threshold value minus the constant value, there has been a light press. If the current value is not greater than or equal to the threshold value minus the constant, the computer loops back to step 400.

[0040] The finger with the light press is recalibrated in step 430. If more than one finger has a light press, the system chooses the finger with the value closest to the threshold and sends it to the recalibration step 430.

[0041] The recalibration step 430 consists of replacing the threshold value with the threshold value minus the constant. This makes the thresholds dynamic, successfully alleviating the finger amplitude problem when a user tires over time. In addition, since the new threshold value is the old threshold value minus the constant, the system can recalibrate incrementally rather than with abrupt changes in threshold values.

[0042] Once the threshold is recalibrated, the computer returns the appropriate finger ID or key (e.g., 1=left-hand pinkie, 2=left-hand ring finger, and so on) to the reconstruction engine and generates audio/visual feedback to inform the user that a finger press has been entered (step 500). This feedback is helpful in alleviating the finger amplitude problem, because the user will recognize whether the system has registered a finger press. Preferably, the feedback is a soft beep combined with changes in the visual diagram of both hands that is displayed in the user's goggles. In the preferred embodiment, the finger in the diagram representing the one that is pressed changes color and moves to simulate the pressing movement.

[0043] Referring back to step 410, if one of the finger values passes the threshold value, the computer determines at step 440 whether only one finger passed its threshold value. If only one finger did, the computer passes the finger ID or key to the reconstruction engine and generates a beep in step 500. If more than one finger has passed the threshold value, the computer determines which current finger value is closest to its threshold at step 450. This step eliminates the sympathetic finger movement problem by analyzing all the fingers in relation to their thresholds before determining which finger press was intended.

[0044] The finger ID or key determined in step 450 is passed on to the reconstruction engine and the system generates a beep in step 500. The details of the reconstruction engine will be described below.

[0045] B. Reconstruction Engine

[0046] From step 500 in FIG. 3, the procedure continues at step 1000 in FIG. 7. At step 1000, the computer checks if the finger pressed was the <period> (the left thumb in FIG. 1 and finger ID or key 4). If the <period> was pressed, the computer discards the past finger IDs or keys at step 1050. This effectively erases the sentence from memory so that the system is ready to start a new sentence. After the finger IDs are discarded, the computer returns to monitor for the next finger press (step 400 in FIG. 3).

[0047] If the <period> was not pressed in step 1000, the computer then checks if a <backspace> was entered at step 1100. The <backspace> can be represented by more than one finger press—for instance, an embodiment may use two consecutive left thumb presses to be a <backspace>. This requires adding an extra loop that checks for two consecutive left thumb presses. If a <backspace> was entered, the computer deletes the last finger ID or key from memory (step 1150). After step 1150, the computer reconstructs the partial sentence in step 1300. If the press was not a <backspace> in step 100, the computer saves the finger ID and adds it to however much of the sentence exists at this time (step 1200). At this point, the computer reconstructs the partial sentence at step 1300.

[0048] After the partial sentence reconstruction (which will be described below) at step 1300, the computer displays the sentence at step 1400, and returns to step 400 in FIG. 3 in order to monitor for more finger presses.

[0049] The partial sentence reconstruction at step 1300 is broken down in FIG. 8. First, the system recognizes spaces, and partitions the sentence into words at step 1305. As an example, the input at this point might be “585_—341_—69” (the underscores represent spaces), so the computer would break this down into “585”, “341”, and “69”. Then, at step 1310, the computer takes the first word (“585”) and searches the dictionary data structure for that sequence. For “585,” the dictionary might contain “RAT”, “TAT,” “TAR,” “RAG,” “FAT,” “FAR,” “FAG,” “VAT,” “TAG,” “TAB,” “BAR,” “BAG,” “GAG,” “GAB,” and “BAT.” If an entry is found in the dictionary, the different word options are saved in step 1350.

[0050] If there is no dictionary match, the computer checks to see if there are partial matches in step 1320. If one or more partial matches are found, the computer saves these different word options in step 1350. If not, the computer checks to see if there is a prefix/suffix match in step 1330. If there are prefix/suffix matches, the computer saves them all in step 1350. If there are no prefix/suffix matches, the computer constructs one or more words using character probabilities combined with letter transition probabilities in step 1340. Once constructed, these one or more word options are saved in step 1350.

[0051] After step 1350, the computer checks if there are more key sequences to be matched. If there are, the computer starts at 1310 again. If there are no more, the computer has reached the end of the partial sentence and will now analyze it as a whole in order to find the most accurate reconstruction. At step 1370, the computer generates all possible combinations of word options; in other words, every possible sentence.

[0052] In step 1380, the computer uses the Viterbi algorithm to find the probability attached to each possible sentence. Grammatical constraints and word pair frequency are employed within the Viterbi algorithm to find the most likely sentence. These constraints can be formulated in terms of transition probabilities:

[0053] P(Z_i/X_i), the probability that the word Z_iwas intended when the code X_iwas observed.

[0054] P(Z_i/Z_i−1), the transitional probability that the word Z_iis observed when the previous word was Z_i−1.

[0055] A directed graph represents the word lattice that forms a set of sentence candidates. Each of the nodes and edges have costs assigned to them. The node costs are the word probabilities for the observed code, while the edge costs are the transition probabilities between word pairs. Any path between the start and end node represents a possible sentence. The Viterbi algorithm finds the maximum-cost path in the trellis using dynamic programming. To ensure that implausible sentences are rejected, each word in the dictionary is augmented with a tag that indicates the corresponding grammatical category.

[0056] Once probabilities are assigned to every possible sentence, the computer selects the most probable sentence and stores it at step 1390. At this point, the computer returns to step 1400 in FIG. 7 and provides feedback about the reconstructed sentence. In the preferred embodiment, the reconstructed sentence is shown in the user's visual display. But more sophisticated feedback, such as text-to-speech, could be used.

[0057] C. The User's View

[0058] In order to give a clearer idea of what the user sees in the preferred embodiment of the present invention, FIG. 9 gives an example of what a user might see during a series of finger presses. The letters of the alphabet have been mapped consecutively to the fingers, which are numbered 1 through 10. The <space> is mapped to finger 9, and the <period> to finger 10.

[0059] The user starts by pressing the finger labeled 2, which could indicate the letters “e,” “f,” “g,” or “h.” The system runs through steps 400 to 1400 and displays the letter “e.” This means that the system has determined that the most probable letter of the group is “e.” At step 2, the user presses finger 3, which could indicate the letters “i,” “j,” “k,” or “l.” After running through steps 400 through 1400, the system determines the most likely word is “hi” and displays it. As shown in FIG. 9, this process continues as the user presses the fingers labeled 9, 4, 4, and 8. The computer saves the original key sequence (“23944” at step 5) so that each reconstruction iteration will provide the most likely partial sentence. Finally, at step 7, the user presses finger 10, which represents the <period>. This ends the sentence, which the computer has determined is “hi mom,” so the computer erases the key sequence “239448” from the memory (step 1050 in FIG. 7) and saves the sentence “hi mom” for display and/or later storage.

[0060] The reconstruction engine used above can be used for other applications where there are obscured or ambiguous characters. Conventional handwriting recognition systems and Optical Character Recognition (OCR) systems often report obscured characters as “unknown” or they use reconstruction that is limited to dictionary lookups and character trigram frequencies. The present invention's reconstruction engine, which uses context and grammatical constraints, could increase the recognition rates and decrease the error rates of such devices. In addition, any keyboard system that uses overloaded keys would benefit from the character disambiguation the above system provides.

[0061] Text entry for languages with thousands of symbols, such as Chinese, could also be done using this system. The conventional text entry method for Chinese has the user type in the phonetic pronunciation of each character, and then the user selects the appropriate character from a menu based on the phonetic entry. The present invention could perform the selection process automatically.

[0062] Although the above embodiment uses sensory gloves, other devices could be used to monitor finger movement, such as cameras, rings, etc.

[0063] Although the feedback listed above is auditory and visual, the feedback could also be tactile.

[0064] Computer code modules for executing parts of the present invention are provided as appendices.

[0065] Although the preferred embodiments of the present invention have been disclosed for illustrative purposes, those skilled in the art will appreciate that various modifications, additions and substitutions are possible, without departing from the scope and spirit of the invention as disclosed in the accompanying claims.

[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]