System and method for superimposed handwriting recognition technology

CROSS REFERENCE TO RELATED APPLICATIONS

0001This application claims priority to <patcit id="pcit0001" dnum="US24560114" dnum-type="L"><text>U.S. Patent Application No. 14/245,601, filed April 4, 2014</text></patcit>.

TECHNICAL FIELD

0002The present invention relates generally to the field of computing device interfaces capable of recognizing user input handwriting of various characters.

BACKGROUND

0003Computing devices continue to become more ubiquitous to daily life. They take the form of computer desktops, laptops, tablet PCs, e-book readers, mobile phones, smartphones, wearable computers, global positioning system (GPS) units, enterprise digital assistants (EDAs), personal digital assistants (PDAs), game consoles, and the like. Further, computing devices are being incorporated into cars, trucks, farm equipment, manufacturing equipment, building environment control (e.g., lighting, HVAC), and home and commercial appliances.

0004Computing devices generally consist of at least one processing element, such as a central processing unit (CPU), some form of memory, and input and output devices. The variety of computing devices and their subsequent uses necessitate a variety of input devices. One such input device is a touch sensitive surface such as a touch screen or touch pad wherein user input is received through contact between the user's finger or an instrument such as a pen or stylus and the touch sensitive surface. Another input device is an input surface that senses gestures made by a user above the input surface. Either of these methods of input can be used generally for drawing or inputting text. When a user input is text, the computing device must interpret the user's handwriting using an on-line handwriting recognition system or method.

0005Generally, on-line handwriting recognition systems or methods monitor the initiation of a stroke, such as when the user contacts a touch sensitive surface (pen-down); the termination of a stroke, such as when the user stops contacting a touch sensitive surface (pen-up); and any movements (gestures or strokes) the user makes with his or her finger or pen between the initiation and termination of the stroke.

0006On-line handwriting recognition systems or methods usually consist of a preprocessing stage, a segmentation stage, a recognition stage, and an interpretation stage. Generally, the preprocessing stage includes discarding irrelevant input data and normalizing, sampling, and removing noise from relevant data. The segmentation stage specifies the different ways to break down the input data into individual characters and words. The recognition generally includes a feature extraction stage, which characterizes the different input segments, and a classification stage which associates the segments with possible character candidates. Finally, the interpretation stage generally includes identifying the characters and/or words associated with the character candidates. In practice, on-line handwriting recognition systems or methods may include these stages along with additional stages. Further, on-line handwriting recognition systems or methods may not clearly delineate each stage.

0007On-line handwriting recognition systems or methods can be single-stroke or multi-stroke. Single stroke recognition uses single-stroke shorthand for each character of an alphabet (e.g., Palm, Inc.'s Graffiti). These systems or methods have less input errors but require users to memorize new stroke patterns for a whole alphabet. Multi-stroke recognition can recognize natural handwriting and is often necessary when using on-line handwriting recognition systems with languages that include characters that are not easily reduced to single strokes, such as Japanese or Chinese characters.

0008The type of computing device can also determine the type of handwriting recognition system or method utilized. For instance, if the input surface is large enough (such as a tablet), the user can input text or data anywhere on or above the input surface, as if the user was writing on a piece of paper. As devices become smaller, different systems or methods, such as multi-box or single-box, have been developed. Multi-box systems or methods divide the input surface into multiple areas, such as three boxes, where a user inputs each character in each box, one after another. These are advantageous because character segmentation becomes minimal or unnecessary. They also allow for multi-stroke characters, which can be analyzed with isolated-character recognition techniques.

0009For even smaller devices, the input surface may not be large enough for multiple boxes, so the surface is essentially a single-box writing interface. In this instance, only one character can be written at a time. Although single-box interfaces lend themselves to single-stroke recognition systems, certain languages, such as Japanese or Chinese, have multi-stroke characters that do not easily reduce to single-stroke shorthand. Further, most natural handwriting contains multi-stroke characters, regardless of the language.

0010Single-box interfaces using multi-stroke systems or methods create additional problems including determining the beginning and end of characters and clearly displaying the images of the input characters. One way to determine the beginning and end of characters requires the user to explicitly pause between each character. However, this is not optimal because it slows down the user from inputting data. In a single box system or method, where a user is able to input characters continuously and without a pause, input characters would be overlaid or superimposed on each other. This is referred to as superimposed handwriting, overlaid handwriting, or "on-top-writing."

0011The present on-line superimposed handwriting recognition system and method provides improved results for user input handwriting recognition by performing segmentation, recognition, and interpretation concurrently, rather than sequentially. The present system and method performs these processes at the same level rather than applying a hierarchy to the steps. By having segmentation, recognition, and interpretation occur collaboratively, the present system provides the user with the best possible character, word, and sentence candidates based on the user input. The document "<nplcit id="ncit0001" npl-type="s"><text>On-line Chinese Character Recognition System for Overlapping Samples" by Xiang Wan et al., 2011 International Conference on Document Analysis and Recognition, 1 September 2011, pages 799-803</text></nplcit> discloses a method for on-line handwriting Chinese Character recognition for overlapping samples, according to which samples are evaluated on a stroke level and on a character level based on a character pair search model. The document "<nplcit id="ncit0002" npl-type="s"><text>On-line Overlaid-Handwriting Recognition Based on Substroke HMMs" by H. Shimodaira et al., 7th International Conference on Document Analysis and Recognition, 3 August 2003, pages 1043 - 1047</text></nplcit>, discloses a handwriting recognition interface for wearable computing where users write characters continuously without pauses on a small single writing box. Since characters are written on the same writing area, they are overlaid with each other. Therefore the task is regarded as a special case of the continuous character recognition problem. To tackle the problem, substroke based hidden Markov models (HMMs) and a stochastic bigram language model are employed.

SUMMARY

0012The examples of the present invention that are described herein below provide methods, systems, and software for use in on-line superimposed handwriting recognition. These permit a user to enter characters into a computing device using his or her natural handwriting without any explicit separation between characters. The present handwriting recognition system and method includes a computing device connected to an input device in the form of an input surface. A user is able to provide input by applying pressure to or gesturing above the input surface using either his or her finger or an instrument such as a stylus or pen. The present system and method monitors the input strokes. After preprocessing the input strokes, the segmentation expert, recognition expert, and language expert simultaneously analyze the input data. These three experts work collaboratively through dynamic programming to process input strokes and generate candidates at the character, word, and sentence level.

0013An object of the disclosed system and method is to provide an on-line handwriting recognition system and method that can interpret a user's natural handwriting style. This can be done by providing a system and method whereby the segmentation expert, which creates a segmentation graph based on the user input and input from the recognition expert and language expert; recognition expert, which associates a list of character candidates with recognition scores of each node of the segmentation graph; and language expert, which generates linguistic meaning of the different paths in the segmentation graph, all work collaboratively through dynamic programming.

0014Another object of the disclosed system and method is to provide an on-line handwriting recognition system and method that can recognize superimposed handwriting, where characters are written one over another without any explicit separation between consecutive letters. This can be done by providing a system and method whereby the segmentation expert, recognition expert, and language expert work collaboratively through dynamic programming to provide the most likely candidates for character, word, and sentence inputs.

0015Yet another object of the disclosed system and method is to provide an on-line handwriting recognition system and method that can recognize multiple-stroke characters. This can be done by providing a system and method whereby the segmentation expert creates a segmentation graph that is based on the user input and the dynamic programming that involves the recognition and language experts analyzing the segmentation graph.

0016Another object of the disclosed system and method is to provide an on-line handwriting recognition system and method that can recognize cursive writing where attached characters are written one over the other. This is done by providing a system and method whereby the segmentation expert detects particular points defining locations for breaking a stroke into its constituting segments.

0017A further object of the disclosed system and method is to provide an on-line handwriting recognition system and method that provides word boundaries based on either a specific input stroke or by automatically detecting word boundaries. This is done by providing a system and method whereby the present system including the segmentation expert, recognition expert, and language expert all expect a specific input stroke to break up input characters into words; or the three experts automatically add word breaks by analyzing all the input characters holistically.

0018The achievement of the above objects in accordance with the invention is set out in the independent claims. Further developments of the invention are the subject matter of the dependent claims. The present system and method will be more fully understood from the following detailed description of the examples thereof, taken together with the drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

0019<ul id="ul0001" list-style="none"><li><figref idref="f0001">FIG. 1</figref> shows a block diagram of a computing device in accordance with an example of the present system.</li><li><figref idref="f0002">FIG. 2</figref> shows a block diagram of a system for on-line handwriting recognition in accordance with an example of the present system.</li><li><figref idref="f0003">FIG. 3A</figref> shows a pictorial illustration of a possible user input in accordance with an example of the present system.</li><li><figref idref="f0003">FIG. 3B</figref> shows a schematic pictorial of a segmentation graph in accordance with an example of the present system.</li><li><figref idref="f0004">FIG. 4</figref> shows a schematic pictorial of a possible user input of cursive user input in accordance with an example of the present system.</li><li><figref idref="f0004">FIG. 5</figref> shows schematic pictorial illustration of the segmentation of a cursive user input in accordance with an example of the present system.</li><li><figref idref="f0005">FIG. 6</figref> shows a schematic pictorial illustration of the recognition expert in accordance with an example of the present system.</li><li><figref idref="f0006">FIG. 7</figref> shows a schematic pictorial illustration of a linguistic automaton in accordance with an example of the present system.</li></ul>

DETAILED DESCRIPTION

0020In the following detailed description, numerous specific details are set forth by way of examples in order to provide a thorough understanding of the relevant teachings. However, it should be apparent to those skilled in the art that the present teachings may be practiced without such details. In other instances, well known methods, procedures, components, and/or circuitry have been described at a relatively high-level, without detail, in order to avoid unnecessarily obscuring aspects of the present teachings.

0021The various technologies described herein generally relate to on-line handwriting recognition and more specifically to systems and methods for superimposed handwriting recognition on various computing devices. The system and method described herein may be used to recognize a user's natural handwriting input through the concurrent processes of segmentation, recognition, and interpretation to provide the best possible character, word, and sentence candidates.

0022<figref idref="f0001">FIG. 1</figref> shows a block diagram of a computing device 100. This computing device can be a computer desktop, laptop, tablet PC, e-book reader, mobile phone, smartphone, wearable computer, digital watch, global positioning system (GPS) unit, enterprise digital assistant (EDA), personal digital assistant (PDA), or game console. The device 100 includes at least one processing element, some form of memory and input and/or output (I/O) devices. The components communicate with each other through input and output means, such as connectors, lines, buses, cables, buffers, electromagnetic links, networks, modems, transducers, IR ports, antennas, or other means as known to those of ordinary skill in the art.

0023The device 100 includes at least one input surface 104. The input surface 104 may employ technology such as resistive, surface acoustic wave, capacitive, infrared grid, infrared acrylic projection, optical imaging, dispersive signal technology, acoustic pulse recognition, or any other appropriate technology as known to those of ordinary skill in the art. The input surface 104 may be bounded by a permanent or video-generated border that clearly identifies its boundaries.

0024In addition to the input surface 104, the device 100 may include one or more additional I/O devices (or peripherals) that are communicatively coupled via a local interface. The local interface may have additional elements to enable communications, such as controllers, buffers (caches), drivers, repeaters, and receivers, which are omitted for simplicity but known to those of skill in the art. Further, the local interface may include address, control, and/or data connections to enable appropriate communications among the other computer components.

0025One such I/O device may be at least one display 102 for outputting data from the computing device such as images, text, and video. The display 102 may use LCD, plasma, CRT, or any other appropriate technology as known to those of ordinary skill in the art. At least some of display 102 could be co-located with the input surface 104. Other additional I/O devices may include input devices such as a keyboard, mouse, scanner, microphone, touchpads, bar code readers, laser readers, radio-frequency device readers, or any other appropriate technology as known to those of ordinary skill in the art. Furthermore, the I/O devices may also include output devices such as a printer, bar code printers, or any other appropriate technology as known to those of ordinary skill in the art. Finally, the I/O devices may further include devices that communicate both inputs and outputs such as a modulator/demodulator (modem; for accessing another device, system, or network), a radio frequency (RF) or other transceiver, a telephonic interface, a bridge, a router, or any other appropriate technology as known to those of ordinary skill in the art.

0026The device 100 also includes a processor 106, which is a hardware device for executing software, particularly software stored in the memory 108. The processor can be any custom made or commercially available general purpose processor, a central processing unit (CPU), a semiconductor based microprocessor (in the form of a microchip or chipset), a macroprocessor, microcontroller, digital signal processor (DSP), application specific integrated circuit (ASIC), field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, state machine, or any combination thereof designed for executing software instructions known to those of ordinary skill in the art. Examples of suitable commercially available microprocessors are as follows: a PA-RISC series microprocessor from Hewlett-Packard Company, an 80x86 or Pentium series microprocessor from Intel Corporation, a PowerPC microprocessor from IBM, a Sparc microprocessor from Sun Microsystems, Inc., a 68xxx series microprocessor from Motorola Corporation, DSP microprocessors, or ARM microprocessors.

0027The memory 108 can include any one or a combination of volatile memory elements (e.g., random access memory (RAM, such as DRAM, SRAM, SDRAM, etc.)) and nonvolatile memory elements (e.g., ROM, EPROM, flash PROM, EEPROM, hard drive, magnetic or optical tape, memory registers, CD-ROM, WORM, DVD, redundant array of inexpensive disks ("RAID"), another direct access storage device ("DASD"), etc.). Moreover, memory 108 may incorporate electronic, magnetic, optical, and/or other types of storage media. The memory 108 can have a distributed architecture where various components are situated remote from one another but can also be accessed by the processor 106. The memory 108 is coupled to a processor 106, so the processor 106 can read information from and write information to the memory 108. In the alternative, the memory 108 may be integral to the processor 106. In another example, the processor 106 and the memory 108 may both reside in a single ASIC or other integrated circuit.

0028The software in memory 108 includes the on-line handwriting computer program, which may include one or more separate programs, each of which comprises an ordered listing of executable instructions for implementing logical functions. The operating system 110 controls the execution of the on-line handwriting computer program. The operating system 110 may be a proprietary operating system or a commercially available operating system, such as PALM^®, WINDOWSO, MAC and IPHONE OS^®, LINUX, ANDROID, etc. It is understood that other operating systems may also be utilized without departing from the scope of the system and method disclosed herein.

0029The memory 108 may include other application programs 112 related to handwriting recognition as described herein, totally different functions, or both. The applications 112 include programs provided with the device 100 upon manufacture and may further include programs downloaded into the device 100 after manufacture. Some examples include a text editor, telephone dialer, contacts directory, instant messaging facility, email program, word processing program, web browser, camera, etc.

0030The on-line handwriting recognition computer program with support and compliance capabilities may be a source program, executable program (object code), script, or any other entity comprising a set of instructions to be performed. When a source program, the program needs to be translated via a compiler, assembler, interpreter, or the like, which may or may not be included within the memory, so as to operate properly in connection with the operating system. Furthermore, the on-line handwriting recognition computer program with support and compliance capabilities can be written as (a) an object oriented programming language, which has classes of data and methods, or (b) a procedure programming language, which has routines, subroutines, and/or functions, for example but not limited to, C, C++, Pascal, Basic, Fortran, Cobol, Perl, Java, and Ada.

0031The system is initiated when processor 106 detects a user entered stroke via the input surface 104. The user may enter a stroke with a finger or some instrument such as a pen or stylus. A stroke is characterized by at least the stroke initiation location, the stroke termination location, and the path upon which the user connects the stroke initiation and termination locations. Because different users may naturally write the same letter with slight variations, the present system accommodates a variety of ways in which each letter may be entered.

0032<figref idref="f0002">FIG. 2</figref> is a schematic pictorial of a system for on-line handwriting recognition in accordance with an example of the present system. Once initiated with at least one input stroke, the system preprocesses 114 the strokes. Preprocessing 114 can include normalizing the path connecting the stroke initiation and termination locations by applying size normalization and/or methods such as B-spline approximation to smooth the input. The input stroke is then passed to three experts (segmentation expert 116, recognition expert 118, and language expert 120) that collaborate through dynamic programming to generate output candidates 124 at the character, word, and sentence level.

0033The segmentation expert 116 defines the different ways to segment the input strokes into words and individual character hypotheses. To form the character hypotheses, the segmentation expert 116 groups consecutive strokes of the original input. This results in a segmentation graph where each node corresponds to at least one character hypothesis and where adjacency constraints between characters are handled by the node connections. Nodes are considered adjacent if the corresponding hypotheses have no common stroke but whose strokes are consecutive in the original input. <figref idref="f0003">FIG. 3A</figref> shows a possible user input of the word BEAN in accordance with an example of the present system. Specifically, the figure displays an example of superimposed writing with multi-stroke characters. <figref idref="f0003">FIG. 3B</figref> shows a possible segmentation graph of the input of <figref idref="f0003">FIG. 3A</figref> created in accordance with an example of the present system.

0034Superimposed handwriting recognition systems and methods must also determine where one word ends and another begins. The present system and method is capable of multiple embodiments to retrieve word boundaries. In one embodiment, a user is required to insert a specific gesture after each word. In this embodiment, the specific gesture is output as a space character. This embodiment brings more robustness to the segmentation process since it reduces the different ways to segment the input strokes into words and individual character hypotheses. However, this embodiment forces the user to add a specific gesture indicating the end of each word, which might be missed by some users.

0035An alternative embodiment does not require a specific gesture separating words. Instead, the on-line handwriting recognition computer program automatically detects word boundaries with the help of the recognition expert 118 and/or language expert 120, which will be described in detail below. For instance, the language expert 120 uses linguistic information 130 to retrieve the word boundaries based on, among other things, lexical knowledge and techniques modeling the likelihood of a sequence of consecutive words in a given language, such as N-grams models, syntactic parsing, semantic analysis, etc.

0036For example, a user may enter the character sequence "whattimeisit?" with superimposed writing in an embodiment based on linguistic information 130 extracted from the English language. This alternative embodiment would output the word segmentation "what time is it?" making a global meaning to the input strokes and retrieving the word boundaries based on the linguistic information 130. This embodiment has the advantage of allowing the user to input a sequence of words without inserting a specific gesture between each word.

0037In another embodiment, the two previous methods can be combined. In that case, the user can insert a specific gesture after each word for getting more robustness to detect word boundaries. But whenever the user neglects to insert a gesture, the handwriting recognition system is able to detect word boundaries with the help of the recognition expert 118 and/or language expert 120.

0038In one example, the segmentation expert is not limited to handprint writing input where each individual character is separated from its neighbor characters with a pen-up, as seen in <figref idref="f0003">FIGS. 3A and 3B</figref>. The segmentation expert 116 of the present system is also able to process cursive writing where attached characters are written one over the other. <figref idref="f0004">FIG. 4</figref> illustrates a cursive user input of words "be" and "an." When interpreting cursive user input, the segmentation expert 116 segments each stroke based on a detection of particular points defining locations for breaking a stroke into its constituting segments. <figref idref="f0004">FIG. 5</figref> illustrates an example of a cursive "an" being broken up into its constituting segments. The particular points for breaking a stroke into its constituting segments may be defined by crossing points, a change in the slope of stroke path, etc. These constituting segments are used to construct the segmentation graph.

0039The recognition expert 118 associates a list of character candidates with probabilities or recognition scores for each node of the segmentation graph. These probabilities or recognition scores are based on the language recognition information 122. The language recognition information defines all the different characters and symbols of the alphabet underlying to the specified language. This information is language dependent and comprises general differences in alphabets as well as the ability to recognize various individual styles of writing the alphabets. For instance, the way an individual writes a "7" can be quite different depending on whether that individual is from the USA, France, or even Korea. Continuing the example given in <figref idref="f0003">FIGS. 3A and 3B</figref>, <figref idref="f0005">FIG. 6</figref> illustrates an embodiment of the recognition expert 118 that includes two stages. The first stage of the recognition expert 118, feature extraction 126, is based on a combination of dynamic and static features. For instance, the dynamic features can be extracted from the trajectory of the input stroke and are based on information such as position, direction, and curvature of the input stroke. Static features can be extracted from a bitmap representation of the input stroke and can be based on projections and histograms.

0040The second stage of the recognition expert 118 of the present embodiment is classification of the features extracted by a pattern classifier such as Neural Networks 128. In the present embodiment, the Neural Networks can be simple multilayer perceptrons. The Neural Networks can also include an extra class enabling the Neural Network to reject node hypotheses corresponding to badly segmented characters. The recognition expert 118 outputs a list of character candidates with probabilities or recognition scores for each node of the segmentation graph. An alternative embodiment might make use of another kind of Neural Network such as Deep Neural Network, Convolutional Neural Network, or Recurrent Neural Network. More generally, any kind of pattern classifier could be used to address this recognition task (e.g., Support Vector Machine, Hidden Markov Model).

0041The language expert 120 generates linguistic meaning for the different paths in the segmentation graph. It checks the candidates suggested by the other experts according to the linguistic information 130 available. This linguistic information 130 can include a lexicon, regular expressions, etc. The language expert 120 aims at finding the best recognition path. In one embodiment, the language expert 120 does this by exploring a language model such as final state automaton (determinist FSA) representing the content of linguistic information 130. <figref idref="f0006">FIG. 7</figref>, building on examples in <figref idref="f0003">FIGS. 3A, 3B</figref>, and <figref idref="f0005">6</figref>, shows a linguistic automaton with a lexicon that only contains the words BEAN, BY, CAR, CAT, and COW. Further, <figref idref="f0006">FIG. 7</figref> represents an embodiment of the language expert that expects the user to insert a dash 132 to define a word boundary.

0042In addition to the lexicon constraint, the language expert 120 may use statistical information modeling for how frequent a word or a given sequence of words appears in the specified language or is used by a specific user. For instance, a word tri-gram language model may be used to evaluate the linguistic likelihood of the interpretation of a given path of the segmentation graph.

0043The segmentation expert 116, recognition expert 118, and language expert 120 work collaboratively through dynamic programming to process input strokes and generate output candidates 124 at the character, word, and sentence level. The dynamic programming is based on a beam search technique that searches for the best path both in the segmentation graph and the linguistic model, wherein the best path is the path corresponding to the lowest cost. The lowest cost path is defined as the sum of: <ul id="ul0002" list-style="bullet" compact="compact"><li>Costs of all the character candidates encountered in the corresponding path into the segmentation graph. These costs can be estimated from the probabilities or recognition scores of each node belonging to this path in the segmentation graph. In one embodiment, the costs are estimated from the Neural Network probabilities by applying a -log non-linear function.</li><li>Costs of all words encountered in the corresponding path of the linguistic model. Those costs can be estimated from the N-gram probabilities from the language expert 120. In one embodiment, the costs are estimated from the N-gram probabilities from the language expert 120 by applying a -log non-linear function.</li></ul>

0044For overall training of the present on-line handwriting recognition computer program, a global discriminant training scheme at the text level with automatic learning of all parameters of the classifiers (e.g., Neural Network) 128 and any meta-parameters of the system may be used, although other training systems and methods may be used. Through the present on-line superimposed handwriting recognition system and method, the best results for user input handwriting recognition are provided by performing segmentation, recognition, and interpretation concurrently, rather than sequentially or in a hierarchal nature.

0045While the foregoing has described what is considered to be the best mode and/or other examples, it is understood that various modifications may be made, as long as they fall within the scope of the invention as defined by the appended claims, and that the subject matter disclosed herein may be implemented in various forms and examples, and that they may be applied in numerous other applications, combinations, and environments, only some of which have been described herein.