Abstract:
The disclosure describes an overall system/method for developing a “speak and touch auto correction interface” referred to as STACI which is far more superior to existing user interfaces including the widely adopted qwerty. Using STACI a user speaks and types a word at the same time. The redundant information from the two modes, namely speech and the letters typed, enables the user to sloppily and partially type the words. The result is a very fast and accurate enhanced keyboard interface enabling document production on computing devices like phones and tablets.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This patent application is a continuation-in-part of U.S. application Ser. No. 12/578,355, filed Oct. 13, 2009, which claims priority to U.S. Provisional Patent Application No. 61,196,037, filed Oct. 14, 2008, and which is a continuation-in-part of U.S. application Ser. No. 11/948,757, filed Nov. 30, 2007, which claims priority to U.S. Provisional Patent Application No. 60/872,467, filed Nov. 30, 2006, and to U.S. Provisional Patent Application No. 60/999,593, filed Oct. 19, 2007, which are incorporated herein by reference in their entirety. 
     
    
     FIELD OF THE INVENTION 
       [0002]    The invention relates to user interfaces for entering text into devices using a combination of text prediction and speech recognition. 
       BACKGROUND 
       [0003]    The problem of entering text into computing devices (e.g., cellular phones, tablets, laptops, smart watches, smart glasses, and the like) is of specific importance in many fundamental applications including, but not limited to, document production (e.g., composing an email, writing a report or a note), text-messaging (e.g., SMS, MMS, IM, chats), and wireless internet browsing. 
         [0004]    Current solutions that address the above mentioned problem may be broadly classified into two types: (a) text prediction and (b) speech to text. The solutions utilizing text prediction come in two different flavors. In one, word choices are predicted and displayed as soon as the user types the partial letters of the desired word; the first choice is normally the letters typed and is followed by several other choices for the user to select either by touching the choice displayed (on a touch device) or by pressing the space bar. An example of this form of text prediction is the well-known xt9® software, sold by Nuance Communications, Inc. of Burlington, Mass., that comes pre-built in several of current day phones. In the xt9® software, a user types the letters “aqe” and notices that the word “awesome” is listed as a choice within a list of 3 or more word choices. In the second form of text prediction, referred to as auto correction, a user simply types out the entire word and the auto correction based solution displays choices that it thinks are correct; the desired choice may be automatically inserted by touching it or using the space-bar. For example on some popular smart phones, a user types “aqesome” and sees the corrected word “awesome” being inserted upon pressing the space-bar. Although the basic concept of text prediction involves predicting words using partially or completely typed ambiguous letters, several enhancements exist based on using varied keyboard designs, using gesture based typing (e.g., swype), using handwriting recognition, and so on. 
         [0005]    One of the primary drawbacks with text prediction is the seemingly awkward user interface; a user needs to type a couple of letters, then lift their head, scroll their eyes, or in some manner change their focus in order to check if the desired word is accurately displayed, before moving to the next word. Although the number of keys pressed is significantly reduced, the requirement to lift their head, scroll their eyes or otherwise change focus disturbs the user&#39;s flow in text composition, thus resulting in a fairly sub-optimal user experience. The problem could be solved if text prediction could be accurate enough to display only one word choice with nearly 100% accuracy. Unfortunately, even with the most sophisticated statistical n-gram models, it is almost impossible to accurately predict a word from the myriad of choices using only word statistics and context. 
         [0006]    Text entry using speech-to-text is a whole different alternative wherein a user presses a “speak” button and speaks a phrase. The computing device then converts the user&#39;s speech to text and displays the transcription for further action by the user. There has been limited adoption of speech-to-text because of the technology&#39;s inherent lack of robustness and accuracy; primarily due to problems associated with large vocabulary sizes, varied accents, varied pronunciations, mismatched language models, background noise, channel noise, and the like. 
         [0007]    Additionally, the user interface associated with speech-to-text is seemingly different from the widely adopted keyboard interface. Specifically, to use speech-to-text, a user has to think of a whole phrase in mind, then press a “speak” button, and subsequently speak it out loud in one go. This is well suited when a user is trying to access information via the internet, such as when using Siri® voice recognition software in the iPhone® mobile digital device manufactured by Apple Inc. Unfortunately this interface is not natural when it comes to composing long text documents. As a result, the market lacks mainstream adoption of speech-to-text except in hands-busy situations like driving a car or when used as an accessible technology by the handicapped and disabled. 
         [0008]    Multimodal solutions which combine speech and typing have been proposed several times in literature. The inventors have determined that all the above described approaches, even though they have significant merits, they have failed to render the widely adopted “qwerty keyboard” obsolete. In fact, the qwerty keyboard continues to dominate as the most preferred input method. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0009]    The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same become better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein: 
           [0010]      FIG. 1  illustrates one embodiment of the speak and touch auto correction interface (STACI) process proposed in this patent application; 
           [0011]      FIG. 2  illustrates one embodiment of a method for dynamically reducing the active dictionary, which forms a part of the STACI process; 
           [0012]      FIG. 3  illustrates one embodiment of a method for implementing a multimodal n-gram language model, used by the STACI process; 
           [0013]      FIG. 4  illustrates one embodiment of a multimodal confidence model, also used as a part of the STACI process; and 
           [0014]      FIG. 5  is a block diagram representing a computing device in the form of mobile device with which embodiments of the present speak and touch auto correction interface process may be implemented. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0015]    The following disclosure describes an auto correction interface that combines a user&#39;s speech and the user&#39;s touch in a multimodal fashion. The invention may be viewed from two different angles: (a) a speech recognition system whose accuracy is significantly increased by providing additional knowledge of the word to recognize in the form of the word&#39;s initial letters and (b) an auto correction system whose accuracy is significantly improved by providing additional knowledge of the word to correct in the form of the acoustics of the word spoken by the user. Specifically in this invention, a user speaks and types a word substantially at the same time. There is no restriction to the ordering of the spoken word and the letters typed; a user may first speak and then type the word or may speak while typing the word or may speak after typing the word; although it is most efficient and fast when a user speaks and types at the same time. On receiving the letters from the user, the system determines a set of letters based upon an ambiguity map. Using the set of letters as a filter and further aided by additional constraints including a multimodal language model, the system dynamically narrows the speech recognition search. When the user hits the space-bar key indicating end of word, the process uses the most recently reduced search to perform speech recognition and computes a best hypothesized word along with its NBest choice alternatives. The multimodal language model is used to post process the list of words to yield the best word, which is presented to the application; a confidence model&#39;s score may also accompany the word in the application to indicate its confidence to the user. 
         [0016]    An embodiment of the “speak and touch auto correction interface” referred to as STACI is described. Next, three sub-components of STACI, namely the method to dynamically reduce the search, the multimodal language model, and the multimodal confidence model are described. 
         [0017]      FIG. 1  is a conceptual overview of a process  100  of the STACI system. For ease of understanding the overview is presented in the form of software designed using object oriented methodologies such as threads. However, one will appreciate that the threads may be thought of as modules too. In  FIG. 1 , three threads are illustrated in the system: 1) a key-input thread  102  for a keyboard interface for inputting letters; 2) an audio input thread  104  for a microphone interface for collecting audio buffers; and 3) a multimodal recognition thread  106  for implementing a multimodal speech recognition logic of STACI. The way the overall interface works in one embodiment is as follows. When a user presses keys on a keyboard, the corresponding letters or symbols or control signals are collected by the key-input thread  102  into a letter queue  108 . In parallel, the user could also speak a word; the microphone is open all the time and the audio-input thread  104  is collecting audio buffers into an audio queue  110 . The multimodal recognition thread  106  is continuously running in a synchronized fashion as shown in  FIG. 1  (as shown with reference to an arrow that connects block  112  back to block  106 ) to check for the letters in the letter queue  108  and the audio buffers in the audio queue  110 . 
         [0018]    The multimodal recognition thread  106  first checks if there is any letter that has not yet been processed from the letter queue  108 . If there is no letter, i.e block  160  is reached, then it takes the audio buffer present in the audio queue  110  and passes it to the process and detect audio module  112 . If in the recognition thread  106 , the take and analyze key presses module  120  finds a new letter which corresponds to an alphabet set, i.e., block  150 , it dynamically reduces the speech recognition active vocabulary using a method described in  FIG. 2 . On the other hand if the letter corresponds to a symbol (i.e., block  122 ), the system activates a symbol vocabulary in the recognition module  132 . Finally, if the process  100  determines that the letter is an end of word indicator  124  (e.g., a space-bar), then the thread  106  carries out the following steps: (a) continues to collect any remaining audio buffers; (b) gets an utterance detected segment from an utterance detector module  130  which in turn gets this by processing the output of process and detect module  112 ; (c) performs speech recognition on the utterance detected in block  132  (d) finds the best word along with the NBest choices and the acoustic scores which is also part of the speech recognition process of block  132 , (e) applies the multimodal language model  134  to find the final word and scores, (f) computes a recognition confidence score at block  136 , (g) presents the final word along with the scores and confidence to the user interface at block  138 , and (h) finally resets, at block  140 , the audio queue, the letter queue, the recognition searches and other necessary modules. 
         [0019]    In the above STACI process, if the ser has typed no letters at all indicated end of word (e.g. user presses space, says awesome, then presses space again without typing any letters) then the process backs off to using the base vocabulary of  FIG. 2  module  204 ; which may be reduced using the multimodal language model (module  250  of  FIG. 2 ) and zero or more applicable constraints (module  240  of  FIG. 2 ); the speech recognition is then performed just like described before. Further on, if the user does not indicate an end of word, then the utterance detector module  112  may be used to signal the end of word automatically; rest of the process remaining the same. Those skilled in art will appreciate that several different architectures, both software and hardware, may be employed to alternatively implement the concept underlying STACI. 
         [0020]    The STACI process  100  can be easily extended to handle gesture based typing. This is described next. There are two ways of implementing this extension. One straightforward way is the following. As the user swipes or traces the letters of a word, the corresponding letters and their ambiguous parts are put by the key-input thread  102  into the letter queue  108 . As before, in parallel, the user may also speak a word and have the speech collected into the audio queue  110 . As before, the multimodal recognition thread  106  is continuously running in a synchronized fashion, checking for the letters in the letter queue  108  and audio buffers in the audio queue  110 . The remaining process remains the same as described above. 
         [0021]    Another approach to extend the STACI process  100  for gesture based typing is the following. The letter queue  108  waits till the user lifts their finger indicating the end of swiping. For example, to enter the word “demonstration” the user swipes over the letters d e m s (introducing ambiguity due to swiping and also due to sloppy swiping) while speaking “demonstration” and lifting finger. Upon lifting their finger, the key-input thread  102  puts the letters with the ambiguous counterparts into the letter queue  108 . The STACI process  100  then processes these letters in  150  to dynamically reduce the speech recognition vocabulary in  152  and directly calls the “Get Utt Detect”  130  followed by the recognition module  132 . Thus, the entire procedure is very similar except for (a) multiple letters are collected when user lifts finger and (b) end of word indicator is not the space-bar but the action by user of “lifting finger”. 
         [0022]    An example that compares STACI to other input methods is now presented for further ease of understanding. Consider the user is attempting to type the word “awesome”. The following are ways to enter the word using the different input methods: (a) STACI: while typing a q e the use says “awesome” and hits space (b) STACI with gesture typing: while swiping a-&gt;q-&gt;e the user says “awesome” and stops swiping (c) QWERTY keyboard with auto correction: user types a q e some and hits space (d) Text prediction: user types a q e then lifts head to select awesome (if present) from choices displayed and then finalizes it by touching same or hitting space. 
         [0023]      FIG. 2  describes a method  200  to dynamically reduce the recognition vocabulary. The method  200  includes a base dictionary object  204 , which may be accomplished by loading a base vocabulary when the application starts for the first time, such as by reading from a file (or any other memory location). The base vocabulary and/or the base dictionary object  204  includes a list of words along with their pronunciations, statistical language model counts, and user adapted language model counts. Further, the base vocabulary and/or the base dictionary object  204  is sorted based on the words language model counts; in the event that words have the same count then metrics including length of pronunciation, length of word, the number of times the word appears as an n-gram etc are used to continue sorting. 
         [0024]    During processing, when a letter is received from the letter queue that corresponds to an alphabet, then the base dictionary object  204  is used to create the  1 -letter dictionary object  206 . Specifically, this is achieved by applying the letter and its ambiguity filter of block  202  to the words. As an example, if the letter typed is “A” then the letter filter is “A” and the ambiguity filter may be “QWASZX” which are the letter keys surrounding the letter key A on a qwerty keyboard; filter implies selecting only those words that begin with the letter filter or the ambiguity filter. When the second letter of the word is received, then the 1-letter dictionary object  206  is used to create the 2-letter dictionary object  208 . This process is repeated until the end of word signal or the space-bar is received in which case everything is reset to simply retain the base dictionary object state  204 . In each stage, the objects are further used to create the actual active grammars (e.g.,  210 ,  220 ,  230 ) and the language model hashmaps (e.g.,  212 ,  222 ,  232 ), using a series of constraints  240  such as length of word, length of pronunciation of the word, length of the audio corresponding to the detected utterance, and max # words. The grammars i.e.  210 ,  220 ,  230  are used by the speech recognition module of  FIG. 1  block  132  to carry out recognition and the language model hashmaps i.e.  212 ,  222 ,  232  are used by the multimodal language module to apply n-gram statistics before finding the best word choice. The entire process beginning from creation of the 1-letter object  206  is repeated as the user types letters corresponding to the next word. It will be appreciated by those skilled in art that grammars may be replaced by statistical networks, pre-compiled grammars, modifications to the search algorithm in a speech recognition decoder. Similarly language model hashmaps may be replaced by other mechanisms to look up language statistics. 
         [0025]      FIG. 3  describes a multimodal language model  300 . Observe that instead of the standard n-gram language model used in speech recognition wherein the probability of words are computed given the previous spoken words, the proposed invention computes the probability of words given the previously finalized word by the user. The advantage of doing so is that the system knows with certainty the previous words. As an example, lets us say a user is intending to type the phrase, “this is demonstration of multimodal language model”. Using conventional speech to text, the user can speak the whole phrase at once. Let&#39;s assume the conventional speech to text system recognizes “This is demonstration of” correctly but fails to recognize “multimodal” and recognizes “multiple mode” instead. This error will now propagate to the recognition of the word “language model” because its using “multiple mode” as the previous words when in reality “multimodal” is the previous word. The proposed invention does not exhibit this problem because its interface is based on a word-by-word interaction where each word is indicated as the final word using an end of word signal such as a space-bar. It can be seen from  FIG. 3  that the previously finalized words  302  along with the letters entered  304  are used to compute statistical n-grams in  306 . For example, if the user has typed “This de” then “This” is part of  302  and the letters “de” are part of  304  and they are used to compute bigram scores or load pre-computed bigram scores of all words starting with “de” that have “This” as the precursor word in their bigram pair. The ngram score is then added to the word&#39;s unigram and other counts like the user counts or topic counts to compute a total LM score in  308 . Finally, this is combined with the acoustic scores in  320  (which are outputted by the recognition module of  FIG. 1  block  132 ) to yield a total score  310 . 
         [0026]      FIG. 4  describes a multimodal confidence model process  400  used in the proposed invention. Observe that the overall confidence score is computed by combining traditional confidence metrics known in speech recognition (difference between NBest scores, number of active hmm nodes, acoustic features like formant location, average frequency, signal to noise ratio etc) with multimodal features including (a) a metric that determines the closeness between acoustic only recognition and text only prediction for e.g. whether the same words were recognized by speech recognition and text prediction (b) the user language model score (c) the time between key presses and so on. As shown in  FIG. 4 , the best hypothesis along with its score from  402 , the nbest choices along with their scores and their difference scores and the total number from  404 , and acoustic features like utterance length and formant frequency locations and formant amplitudes etc from  406  are coupled by block  420  with multimodal features in  408  including whether text prediction and acoustic hypothesis are the same and user count for words and time elapsed between keys during typing the word and whether breath or other sounds detected during audio utterance detection of  FIG. 1  block  114 . Block  420  computes a final confidence score by sorting the scores for all hypothesis and presents it along with its corresponding best hypothesis to the user interface or application. 
         [0027]    Certain of the components described above may be implemented using general computing devices or mobile computing devices. To avoid confusion, the following discussion provides an overview of one implementation of such a general computing device that may be used to embody one or more components of the system described above. 
         [0028]      FIG. 5  is a functional block diagram of a sample mobile device  501  that may be configured for use in certain implementations of the disclosed embodiments or other embodiments. The mobile device  501  may be any handheld computing device and not just a cellular phone. For instance, the mobile device  501  could also be a mobile messaging device, a personal digital assistant, a portable music player, a global positioning satellite (GPS) device, or the like. Although described here in the context of a handheld mobile phone, it should be appreciated that implementations of the invention could have equal applicability in other areas, such as conventional wired telephone systems and the like. 
         [0029]    In this example, the mobile device  501  includes a processor unit  504 , a memory  506 , a storage medium  513 , an audio unit  531 , an input mechanism  532 , and a display  530 . The processor unit  504  advantageously includes a microprocessor or a special-purpose processor such as a digital signal processor (DSP), but may in the alternative be any conventional form of processor, controller, microcontroller, state machine, or the like. 
         [0030]    The processor unit  504  is coupled to the memory  506 , which is advantageously implemented as RAM memory holding software instructions that are executed by the processor unit  504 . In this embodiment, the software instructions (e.g., computer-readable instructions) stored in the memory  506  include a display manager  911 , a runtime environment or operating system  510 , and one or more other applications or modules  512 . For example, modules  512  may include a key-input module, a multimodal recognition module, an audio input module, and the like. The memory  506  may be on-board RAM, or the processor unit  504  and the memory  506  could collectively reside in an ASIC. In an alternate embodiment, the memory  906  could be composed of firmware or flash memory. 
         [0031]    The storage medium  513  may be implemented as any nonvolatile memory, such as ROM memory, flash memory, or a magnetic disk drive, just to name a few. The storage medium  513  could also be implemented as a combination of those or other technologies, such as a magnetic disk drive with cache (RAM) memory, or the like. In this particular embodiment, the storage medium  513  is used to store data during periods when the mobile device  501  is powered off or without power. The storage medium  513  could be used to store contact information, images, call announcements such as ringtones, and the like. 
         [0032]    The mobile device  501  also includes a communications module  521  that enables bi-directional communication between the mobile device  501  and one or more other computing devices. The communications module  521  may include components to enable RF or other wireless communications, such as a cellular telephone network, Bluetooth connection, wireless local area network, or perhaps a wireless wide area network. Alternatively, the communications module  521  may include components to enable land line or hard wired network communications, such as an Ethernet connection, RJ-11 connection, universal serial bus connection, IEEE 1394 (Firewire) connection, or the like. These are intended as non-exhaustive lists and many other alternatives are possible. 
         [0033]    The audio unit  531  is a component of the mobile device  501  that is configured to convert signals between analog and digital format. The audio unit  531  is used by the mobile device  501  to output sound using a speaker  532  and to receive input signals from a microphone  533 . The speaker  532  could also be used to announce incoming calls. 
         [0034]    A display  530  is used to output data or information in a graphical form. The display could be any form of display technology, such as LCD, LED, OLED, or the like. The input mechanism  532  may be any keypad-style input mechanism. Alternatively, the input mechanism  532  could be incorporated with the display  530 , such as the case with a touch-sensitive display device. Other alternatives too numerous to mention are also possible. 
         [0035]    Those skilled in the art will appreciate that the proposed invention may be applied to any application requiring text-input, including (but not limited to) mobile text-messaging (SMS, MMS, Email, Instant Messaging), mobile search, mobile music download, mobile calendar/task entry, mobile navigation, and similar applications on other machines like the Personal Digital Assistants, PCs, Laptops, Automobile-Telematics systems, Accessible Technology systems etc. Additionally, several implementations of the system including a client-only, a server-only, and client-server architecture may be employed for realizing the system.