Abstract:
Described is a unified digital ink recognizer that recognizes various different types of digital ink data, such as handwritten character data and custom data, e.g., sketched shapes, handwritten gestures, and/or drawn pictures, without further participation by a user such as recognition mode selection or parameter input. For a custom item, the output may be a Unicode value from a private use area of Unicode. Building the unified digital ink recognizer may include defining the data set to be recognized, extracting features of training samples corresponding to the dataset items to build a recognizer model, evaluating the recognizer model using testing data, and modifying the recognizer model using tuning data. The extracted features may be processed into feature data for a multi-dimensional nearest neighbor recognizer approach; the extracted features for the samples of each class is calculated and combined into the feature set for this class in the resulting recognizer model.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    The present application is related to the following copending U.S. patent applications, assigned to the assignee of the present application, filed concurrently herewith and hereby incorporated by reference: “Digital Ink-Based Search,” U.S. patent application Ser. No. ______ (attorney docket no. 319643.01), and “Integrated Platform for User Input of Digital Ink,” U.S. patent application Ser. No. ______ (attorney docket no. 319644.01). 
     
    
     BACKGROUND 
       [0002]    Digital ink can be used to represent many kinds of user input, such as handwritten characters, sketches, drawings, gestures, and so forth. Although it is easy for humans to distinguish the meanings of different kinds of digital ink input, it is difficult for a computer system to distinguish among them. 
         [0003]    As a result, computer systems operate in separate modes with respect to digital ink processing, whereby in general, existing digital ink recognition technologies mainly focus on one kind of digital ink information at a time. For example, when in a character recognition mode, handwriting character recognition technologies can only recognize digital ink as characters, even when the digital ink does is not intended to represent a character. 
         [0004]    In many situations, users want to input different kinds of information when inputting digital ink to computer programs. However, existing digital ink recognition technologies are unable to differentiate such input, without specifically telling the program what the user intends to enter, that is, by manually changing input modes. 
       SUMMARY 
       [0005]    This Summary is provided to introduce a selection of representative concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used in any way that would limit the scope of the claimed subject matter. 
         [0006]    Briefly, various aspects of the subject matter described herein are directed towards a technology by which a unified digital ink recognizer that recognizes two or more different types of digital ink data is built. Such different types may include, for example, handwritten characters, sketched shapes, handwritten gestures, and/or drawn pictures. Upon receiving an input item, the recognizer outputs a value associated with one of the types of digital ink data. For a custom item of a defined dataset of items that the recognizer can recognize, the output may be a Unicode value from a private use area of Unicode. 
         [0007]    In one aspect, building the unified digital ink recognizer may include using features of training samples corresponding to the dataset items to train a recognizer model. Building may further include evaluating the recognizer model using digital ink testing data, and modifying the recognizer model using digital ink tuning data. In one implementation, the features are extracted and processed (e.g., reduced) into data for a multi-dimensional nearest neighbor recognizer approach. Each set of data for a sample are classified into a recognizer model in association with a value (e.g., a Unicode value) representative of that set of feature-based data. Once built, when an input item is to be processed, the recognizer extracts and/or otherwise processes features of the input item to determine which data in the model the input item&#39;s data best matches, to output the matched data&#39;s associated recognition value. 
         [0008]    In one aspect, a feature extraction mechanism featurizes digital ink data corresponding to training samples that represent at least two different types of digital ink data. A builder mechanism builds a recognizer model by persisting data representative of the features of each class of training sample in association with a recognition value of that class of training sample. An evaluation mechanism evaluates the recognition model using digital ink data testing samples, and an error analysis mechanism tunes the recognition model (e.g., based on the evaluation of the evaluation mechanism) using digital ink data tuning samples. 
         [0009]    Other advantages may become apparent from the following detailed description when taken in conjunction with the drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0010]    The present invention is illustrated by way of example and not limited in the accompanying figures in which like reference numerals indicate similar elements and in which: 
           [0011]      FIG. 1  is a block diagram representative of example components used to build a unified digital ink recognizer. 
           [0012]      FIG. 2  is a block diagram representative of example components within a set of one or more core algorithms that may be used in building a unified digital ink recognizer. 
           [0013]      FIG. 3A  is a visual representation of a core algorithm that recognizes a new item via nearness to a class within a recognition model built during training. 
           [0014]      FIG. 3B  is a block diagram representing recognition of a new item. 
           [0015]      FIG. 4  is a flow diagram representing example steps that may be taken when building a unified digital ink recognizer. 
           [0016]      FIGS. 5-25  are representations of some example figures that may be recognized from a sketch via a unified digital ink recognizer. 
           [0017]      FIG. 26  shows an illustrative example of a general-purpose network computing environment into which various aspects of the present invention may be incorporated. 
       
    
    
     DETAILED DESCRIPTION 
       [0018]    Various aspects of the technology described herein are generally directed towards a unified digital ink recognition system that uniformly recognizes at least two different types of digital ink input. For example, once a unified digital ink recognizer is trained with the proper dataset, whether a user handwrites a character, sketches a shape, inputs a gesture, or draws a picture, the unified digital ink recognition technology correctly interprets the digital ink of the user input as what the user intended, at least to a high degree of accuracy. 
         [0019]    In one implementation, there is described an example development process by a unified digital ink recognizer is built. One such example recognizer is able to recognize Chinese characters and some shapes (such as graphs, a triangle, a rectangle, a circle and the like). However, it is understood that this is only one example, as the technology described herein is not limited to any type of development process, nor to any particular type of algorithm, digital ink recognition or the like. Indeed, the described recognizer is extensible to recognizer many types of digital ink input. 
         [0020]    As such, the present invention is not limited to any particular embodiments, aspects, concepts, structures, functionalities or examples described herein. Rather, any of the embodiments, aspects, concepts, structures, functionalities or examples described herein are non-limiting, and the present invention may be used various ways that provide benefits and advantages in computing, telephony and/or testing in general. 
         [0021]    As described below with reference to  FIGS. 1-4 , a unified digital ink recognizer  102  is built. As part of the building process, a dataset of items that are to be recognized by the recognizer  102  is defined. For example, one such dataset comprises a set of Chinese characters and shapes, and contains 9,119 Chinese characters, corresponding to the Unicode range from 0x4e00 to 0x9FA5 (seldom used characters are removed), along with twenty-one shapes, corresponding to  FIGS. 5-25 , respectively. Note that the shapes may have additional accompanying information (not shown in  FIGS. 5-25 ), such as axes labels, numeric unit labels accompanying the tick marks on the graph shapes, formulas (e.g., x=y for  FIG. 5 ) and so forth. 
         [0022]    For the shape set, the private use area of Unicode that can be customized, ranging from Unicode 0xF000 to 0xF0FF, is used. In this example, for each of the twenty-one shapes in the dataset, one Unicode value is used as the label to identify that shape, e.g., from 0xF000 to 0xF014 corresponding to  FIGS. 5-25 . For building a unified digital ink recognizer, any item to be recognized can be assigned with a Unicode value as its label from the private use area of Unicode, although an item with an already-assigned Unicode values (e.g., a character) can use that value. 
         [0023]    To build the unified digital ink recognizer  102 , a learning based pattern recognition approach is used, as generally represented by the example components shown in  FIG. 1 . In general, this approach builds a classifier according to the features of different classes of items to be recognized. Via feature extraction, the features of each class of items are extracted from a collection of samples for that class. 
         [0024]    With the classifier, given a new item to be recognized, the features of the item are matched with the feature of an existing class, which means the new item is recognized as belonging to that class. 
         [0025]    One aspect of building a digital ink recognizer  102  with this approach is data collection of digital ink samples for each item in the defined dataset to be recognized by the digital ink recognizer  102 . In the implementation represented in  FIG. 1 , the digital ink samples  102  are divided into three different datasets, comprising a training set  106 , a testing set  110  and a tuning set  108 . The training set  106  is used for building a recognizer model  112 , the testing set  110  for testing the recognizer model  112 , and the tuning set  108  for tuning the recognizer model  112  to improve its accuracy. In one example implementation, for building the recognizer model  112 , five-hundred digital ink samples of handwriting were collected for each Chinese character in the training set, and one-hundred digital ink sketch samples were collected for each shape in the training set. 
         [0026]    Based on the digital ink samples  104 , a first mechanism (process step)  114  develops and/or selects a set of one or more core algorithms  116  for use in extracting the features of the training set  106  to build the digital ink recognizer model  112  according to the extracted features. The developed core algorithms are performed on the training set  106  to build the digital ink recognizer model  112 . 
         [0027]    More particularly, a recognition algorithm is used to build the recognizer model (classifier)  112  for the items to be recognized. As represented in  FIG. 2  via blocks  202  and  204 , for each selected training sample  206  of a set of training samples  106 , the core algorithm  116  includes a feature extraction mechanism  208  that extracts a set of features  210 . Further processing  212  may be performed on the feature set  210 , such as feature selection (e.g., for nearest neighbor recognition, described below with reference to  FIG. 3 ) into selected feature set  214 . The feature set  214  is then combined with other such feature data for this sample&#39;s class to build (block  216 ) the recognizer model  112 , by adjusting the combined feature data of the class to which this sample belongs based on the feature set  214 . 
         [0028]    As is known, there are many existing and possible recognition algorithms which may be used to build a recognition system, including nearest neighbor classification (sometimes referred to as k-nearest neighbor, or KNN), Gaussian Mixture Model (GMM), Hidden Markov Model (HMM), and so forth. In one implementation of the unified digital ink recognition system, nearest neighbor classification is used to recognize digital ink. 
         [0029]    A primary concept in nearest neighbor classification is to use one point in multi-dimensional space to represent each class of samples, such as classes A-C as generally represented in  FIG. 3A . In such an example, the class data is thus a set of coordinates in multiple (two or more) dimensional space. 
         [0030]    After the recognizer model  112  is built, when a new item “New Item” is to be recognized, that item is also represented by a point in this space. As represented in  FIG. 3B , a search algorithm  330  performs computations (e.g., searches for a nearest neighbor) to find the nearest point relative to this new item&#39;s point, and recognizes this item as belonging to the class that is represented by the found search result, whereby the recognition result  332  (e.g., a Unicode value) is output. In the example of  FIG. 3A , (in which only three classes are shown, and in only two dimensions for purposes of simplicity), it is readily apparent that the new item is nearest to the Class B, and thus would be recognized as whatever Unicode value corresponded to the Class B. 
         [0031]    Returning to  FIG. 1 , the accuracy and efficiency of the unified digital ink recognizer model  112  may be evaluated via an evaluation mechanism  118  that operates using the testing set  116  of digital ink samples. Further, according to the evaluation results  119 , some error analysis may be performed (block  120 ), by which the unified recognizer model  112  may be improved with the tuning set of digital ink samples  108 . As represented via decision diamond  122 , the process may be performed over and over to optimize the accuracy and efficiency of the unified recognizer model  112 , until, for example, the evaluation results indicate an acceptable recognizer. 
         [0032]    When complete, a unified digital ink recognizer  102  is provided, comprising the core algorithm or algorithms and the recognizer model  112 . In one implementation, the unified digital ink recognizer can recognize digital ink of handwriting (e.g., Chinese characters) and sketching shapes (including sketched graphs). As a result, whether the user inputs a Chinese character by handwriting or inputs a shape by sketching, the unified digital ink recognizer correctly interprets the digital ink of the user&#39;s input as a character or as a shape. 
         [0033]      FIG. 4  summarizes how the unified digital ink recognition technology is built so as to uniformly recognize different kinds of information represented by digital ink, beginning at step  402  which represents defining the dataset of items to be recognized, and collecting the digital ink samples for those items. Step  404  represents dividing the digital ink samples into the training set, testing set and tuning set. Note that the samples may be divided randomly, or based on some other criteria, such as to put similar looking items in the tuning set. Step  406  represents selecting the core algorithms, e.g., determining which features to extract, and for nearest neighbor classification, which should be selected from those features, how much weight to give each feature, and so forth. 
         [0034]    Step  408  represents using a feature extraction algorithm to extract the features from each selected item in the training set, with step  410  representing the feature selection algorithm, and step  412  representing the building of the recognizer model, e.g., processing the feature data of each selected item as needed to adjusting the feature data for the class [the class is identified by the Unicode value, the selected item is belonging to the class] in the recognizer model (such as representing multi-dimensional coordinates). 
         [0035]    Step  414  represents the evaluation of the accuracy and/or efficiency using the testing set of digital ink samples. Based on an error analysis at step  416  as to how accurate and/or efficient the model is, samples from the tuning set may be applied at step  416  in an attempt to better optimize the recognizer. Step  418  represents repeating any or all of steps  406 ,  408 , 410 ,  412 ,  414  and  416  for further optimization. Note that the evaluation at step  414  may be used to determine whether further optimization is necessary. Further, note that a model that is less accurate and/or efficient than another model may be discarded until the best model of those evaluated is determined. 
       Exemplary Operating Environment 
       [0036]      FIG. 26  illustrates an example of a suitable computing system environment  2600  on which the unified digital ink recognizer of  FIG. 1  may be implemented. The computing system environment  2600  is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment  2600  be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment  2600 . 
         [0037]    The invention is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to: personal computers, server computers, hand-held or laptop devices, tablet devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like. 
         [0038]    The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, and so forth, which perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in local and/or remote computer storage media including memory storage devices. 
         [0039]    With reference to  FIG. 26 , an exemplary system for implementing various aspects of the invention may include a general purpose computing device in the form of a computer  2610 . Components of the computer  2610  may include, but are not limited to, a processing unit  2620 , a system memory  2630 , and a system bus  2621  that couples various system components including the system memory to the processing unit  2620 . The system bus  2621  may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus. 
         [0040]    The computer  2610  typically includes a variety of computer-readable media. Computer-readable media can be any available media that can be accessed by the computer  2610  and includes both volatile and nonvolatile media, and removable and non-removable media. By way of example, and not limitation, computer-readable media may comprise computer storage media and communication media. Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can accessed by the computer  2610 . Communication media typically embodies computer-readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of the any of the above should also be included within the scope of computer-readable media. 
         [0041]    The system memory  2630  includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM)  2631  and random access memory (RAM)  2632 . A basic input/output system  2633  (BIOS), containing the basic routines that help to transfer information between elements within computer  2610 , such as during start-up, is typically stored in ROM  2631 . RAM  2632  typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit  2620 . By way of example, and not limitation,  FIG. 26  illustrates operating system  2634 , application programs  2635 , other program modules  2636  and program data  2637 . 
         [0042]    The computer  2610  may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only,  FIG. 26  illustrates a hard disk drive  2641  that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive  2651  that reads from or writes to a removable, nonvolatile magnetic disk  2652 , and an optical disk drive  2655  that reads from or writes to a removable, nonvolatile optical disk  2656  such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive  2641  is typically connected to the system bus  2621  through a non-removable memory interface such as interface  2640 , and magnetic disk drive  2651  and optical disk drive  2655  are typically connected to the system bus  2621  by a removable memory interface, such as interface  2650 . 
         [0043]    The drives and their associated computer storage media, described above and illustrated in  FIG. 26 , provide storage of computer-readable instructions, data structures, program modules and other data for the computer  2610 . In  FIG. 26 , for example, hard disk drive  2641  is illustrated as storing operating system  2644 , application programs  2645 , other program modules  2646  and program data  2647 . Note that these components can either be the same as or different from operating system  2634 , application programs  2635 , other program modules  2636 , and program data  2637 . Operating system  2644 , application programs  2645 , other program modules  2646 , and program data  2647  are given different numbers herein to illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer  2610  through input devices such as a tablet, or electronic digitizer,  2664 , a microphone  2663 , a keyboard  2662  and pointing device  2661 , commonly referred to as mouse, trackball or touch pad. Other input devices not shown in  FIG. 26  may include a joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit  2620  through a user input interface  2660  that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor  2691  or other type of display device is also connected to the system bus  2621  via an interface, such as a video interface  2690 . The monitor  2691  may also be integrated with a touch-screen panel or the like. Note that the monitor and/or touch screen panel can be physically coupled to a housing in which the computing device  2610  is incorporated, such as in a tablet-type personal computer. In addition, computers such as the computing device  2610  may also include other peripheral output devices such as speakers  2695  and printer  2696 , which may be connected through an output peripheral interface  2694  or the like. 
         [0044]    The computer  2610  may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer  2680 . The remote computer  2680  may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer  2610 , although only a memory storage device  2681  has been illustrated in  FIG. 26 . The logical connections depicted in  FIG. 26  include one or more local area networks (LAN)  2671  and one or more wide area networks (WAN)  2673 , but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet. 
         [0045]    When used in a LAN networking environment, the computer  2610  is connected to the LAN  2671  through a network interface or adapter  2670 . When used in a WAN networking environment, the computer  2610  typically includes a modem  2672  or other means for establishing communications over the WAN  2673 , such as the Internet. The modem  2672 , which may be internal or external, may be connected to the system bus  2621  via the user input interface  2660  or other appropriate mechanism. A wireless networking component  2674  such as comprising an interface and antenna may be coupled through a suitable device such as an access point or peer computer to a WAN or LAN. In a networked environment, program modules depicted relative to the computer  2610 , or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation,  FIG. 26  illustrates remote application programs  2685  as residing on memory device  2681 . It may be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used. 
         [0046]    An auxiliary subsystem  2699  (e.g., for auxiliary display of content) may be connected via the user interface  2660  to allow data such as program content, system status and event notifications to be provided to the user, even if the main portions of the computer system are in a low power state. The auxiliary subsystem  2699  may be connected to the modem  2672  and/or network interface  2670  to allow communication between these systems while the main processing unit  2620  is in a low power state. 
       CONCLUSION 
       [0047]    While the invention is susceptible to various modifications and alternative constructions, certain illustrated embodiments thereof are shown in the drawings and have been described above in detail. It should be understood, however, that there is no intention to limit the invention to the specific forms disclosed, but on the contrary, the intention is to cover all modifications, alternative constructions, and equivalents falling within the spirit and scope of the invention.