Patent Description:
Techniques exist for automatically beautifying handwritten content. Many of these techniques operate by attempting to match the user's handwriting with canonical characters or shapes, and then replacing the user's handwriting with these characters or shapes. For example, one such technique can use handwriting recognition to interpret characters and words that a user has written, and then replace those characters and words with their typed formal counterparts. While useful, these techniques have various shortcomings. For example, the techniques are capable of only recognizing certain handwritten content, not content having any arbitrary form. Further, these techniques may only recognize characters and shapes that are sufficiently similar to their expected canonical counterparts. <NPL>, describes digital painters commonly use a tablet and stylus to drive software like Adobe Photoshop. A high quality stylus with <NUM> degrees of freedom (DOFs: 2D position. pressure, 2D tilt, and 1D rotation) coupled to a virtual brush simulation engine allows skilled users to produce expressive strokes in their own style. Such devices are difficult for novices to control and many people draw with less expensive (lower DOF) input devices. This paper presents a data-driven approach for synthesizing the 6D hand gesture data for users of low quality input devices. Offline, we collect a library of strokes with 6D data created by trained artists. Online, given a query stroke as a series of 2D positions, we synthesize the 4D hand pose data at each sample based on samples from the library that locally match the query. This framework optionally can also modify the stroke trajectory to mulch characteristic shapes in the style of the library. Our algorithm outputs a 6D trajectory that can be fed into any virtual brush stroke engine to make expressive strokes for novices or users of limited hardware.

A stroke processing system (SPS) is described herein which processes handwritten content based on previous instances of the handwritten content. For example, in one approach, the SPS operates by receiving input strokes as the user writes on a writing surface of an input device. The SPS formulates a succession of tokens based on the input stroke samples. Each new token corresponds to a series of stroke samples. For each new token, the SPS then examines a collection of previous tokens to determine if there is at least one previous token that is similar to the new token. If so, the SPS performs an action based on the previous token(s).

In one action, the SPS modifies the new token based on the previous token(s), to thereby improve the appearance of the new token. For example, the SPS can average stroke samples in the new token with correlated stroke samples in the previous token(s). In doing so, the SPS treats the previous tokens as evidence pertaining to the shape of the new token that the user intended to draw.

In another action, the SPS provides a search result based on the previous token(s). For example, the SPS can identify occurrences of the previous token(s) in a document containing handwriting.

In another action, the SPS performs an auto-completion operation based on the previous token(s). Here, the SPS predicts a token that is determined to likely follow the new token, and notifies the user of the predicted token.

The SPS offers various benefits. Without limitation, the SPS can process handwriting that has any arbitrary form without the use of complex recognition algorithms. Further, in the beautification application, the SPS can modify a user's handwriting in a manner that preserves the general appearance of the user's handwriting style.

The above approach can be manifested in various types of systems, components, methods, computer readable storage media, data structures, articles of manufacture, and so on.

This Summary is provided to introduce a selection of concepts in a simplified form; these concepts are further described below in the Detailed Description.

The same numbers are used throughout the disclosure and figures to reference like components and features. Series <NUM> numbers refer to features originally found in <FIG>, series <NUM> numbers refer to features originally found in <FIG>, series <NUM> numbers refer to features originally found in <FIG>, and so on.

This disclosure is organized as follows. Section A presents an overview of a stroke processing system (SPS) that processes a current token (representing handwriting) based on previous tokens. The SPS includes a token formulation module, a similarity assessment module, a token refinement module, and optional other application modules. Section B provides further details regarding the token formation module. Section C provides further details regarding the similarity assessment module. Section D provides further details regarding the token refinement module. Section E provides further details regarding other application modules, such as search functionality and auto-completion functionality. And Section F describes illustrative computing functionality that can be used to implement any aspect of the features described in preceding sections.

As a preliminary matter, some of the figures describe concepts in the context of one or more structural components, variously referred to as functionality, modules, features, elements, etc. The various components shown in the figures can be implemented in any manner by any physical and tangible mechanisms, for instance, by software running on computer equipment, hardware (e.g., chip-implemented logic functionality), etc., and/or any combination thereof. In one case, the illustrated separation of various components in the figures into distinct units may reflect the use of corresponding distinct physical and tangible components in an actual implementation. Alternatively, or in addition, any single component illustrated in the figures may be implemented by plural actual physical components. Alternatively, or in addition, the depiction of any two or more separate components in the figures may reflect different functions performed by a single actual physical component. <FIG>, to be described in turn, provides additional details regarding one illustrative physical implementation of the functions shown in the figures.

Other figures describe the concepts in flowchart form. In this form, certain operations are described as constituting distinct blocks performed in a certain order. Such implementations are illustrative and non-limiting. Certain blocks described herein can be grouped together and performed in a single operation, certain blocks can be broken apart into plural component blocks, and certain blocks can be performed in an order that differs from that which is illustrated herein (including a parallel manner of performing the blocks). The blocks shown in the flowcharts can be implemented in any manner by any physical and tangible mechanisms, for instance, by software running on computer equipment, hardware (e.g., chip-implemented logic functionality), etc., and/or any combination thereof.

As to terminology, the phrase "configured to" encompasses any way that any kind of physical and tangible functionality can be constructed to perform an identified operation. The functionality can be configured to perform an operation using, for instance, software running on computer equipment, hardware (e.g., chip-implemented logic functionality), etc., and/or any combination thereof.

The term "logic" encompasses any physical and tangible functionality for performing a task. For instance, each operation illustrated in the flowcharts corresponds to a logic component for performing that operation. An operation can be performed using, for instance, software running on computer equipment, hardware (e.g., chip-implemented logic functionality), etc., and/or any combination thereof. When implemented by computing equipment a logic component represents an electrical component that is a physical part of the computing system, however implemented.

The following explanation may identify one or more features as "optional. " This type of statement is not to be interpreted as an exhaustive indication of features that may be considered optional; that is, other features can be considered as optional, although not expressly identified in the text. Finally, the terms "exemplary" or "illustrative" refer to one implementation among potentially many implementations.

<FIG> shows an illustrative stroke processing system (SPS) <NUM> for processing handwriting. From a high-level perspective, the SPS <NUM> attempts to find previous instances of handwriting that match a current instance of handwriting. The SPS then performs one or more actions based on the previous instances of handwriting. In one application, the SPS modifies the current instance of handwriting based on the previous instances of handwriting, such that the current instance more closely resembles the previous instances of handwriting.

A user inputs the handwriting using any input device <NUM>. The SPS <NUM> processes the handwriting and produces output information, which it presents on an output device. In some cases, the input device <NUM> is the same mechanism as the output device. For example, the input device <NUM> may correspond to a computer device of any type having a touch-sensitive display surface. For instance, the computer device may correspond to a personal computer, a lap-top computer, a tablet-type computer, a smartphone, and so on. The user may create marks on the touch-sensitive display surface using a stylus, finger, or other writing implement. In these cases, the SPS <NUM> may also present output information on the same touch-sensitive display surface. For example, the SPS <NUM> may present a beautified version of the input handwriting on the same touch-sensitive display surface that is used to enter the input handwriting.

In another case, the input device <NUM> and the output device may correspond to separate mechanisms. For example, the input device <NUM> may correspond to a digitizing pad (also referred to as a graphics tablet). The output device may correspond to a display device that is separate from the digitizing pad. A user may use any writing implement to make marks on the digitizing pad, while observing the resultant handwriting that is presented on the display device.

The SPS <NUM> itself can be implemented in any manner. For example, the SPS <NUM> can correspond to module within the input device <NUM>, implemented using software, hardware, etc., or any combination thereof. In another case, the SPS <NUM> can be implemented by a computer device that is separate from the input device <NUM>. Section F provides further details regarding various physical implementations of the SPS <NUM>.

The SPS <NUM> includes (or can be conceptualized as including) different sub-modules which perform different functions. For instance, a token formation module (TFM) <NUM> receives input stroke samples that make up handwriting produced by the user. The TFM <NUM> can then optionally resample the input stroke samples to produce resampled stroke samples. The TFM <NUM> can then define, as the user produces handwriting, a succession of tokens based on the resampled stroke samples. A token corresponds to a series of n consecutive (temporally adjacent) stroke samples. Without limitation, for example, a token may correspond to <NUM> resampled stroke samples that collectively describe a few handwritten characters. A "new token," as the term is used herein, refers to a most recent token that is defined by the TFM <NUM>. Section B provides further illustrative details regarding the operation of the TFM <NUM>.

A data store <NUM> stores a plurality of previous tokens. Each previous token corresponds to a token that was previously defined by the TFM <NUM> (with respect to the new token that is the most recent token defined by the TFM <NUM>). As will be set forth in greater detail below, the data store <NUM> maintains the previous tokens as a plurality of clusters. Each cluster includes a set of similar previous tokens. Two tokens are similar when they possess similar stroke samples, and thus, on a whole, likely pertain to the same semantic content (e.g., the same characters, pictures, etc.). Each cluster is associated with a cluster representative which is a cluster mean. As will be described below, a cluster mean of a cluster corresponds to a token that represents the average of the tokens in the cluster.

A similarity assessment module (SAM) <NUM> examines the previous tokens in the data store <NUM> to determine whether there are previous tokens that are similar to the new token. The SAM <NUM> performs this task by determining whether there are any cluster representatives (i.e. cluster means) which are similar to the new token.

Although not shown in <FIG>, the SPS <NUM> can also include a cluster management module. The cluster management module adds the new token to the cluster which is most similar to the new token. If there is no cluster that is suitably similar to the new token, then the cluster management module can create a new cluster. The new cluster will initially contain only one member, corresponding to the new token. Section C provides further illustrative details regarding the operation of the SAM <NUM> and the cluster management module.

A token refinement module (TRM) <NUM> modifies the appearance of the new token based on the similar previous tokens (if any) which have been identified by the SAM <NUM>. The TRM <NUM> performs this task by first aligning the samples in the previous token(s) with the samples in the new token. This produces correlated samples. The TRM <NUM> then averages the correlated samples together. Less formally stated, the TRM <NUM> produces a modified new token that is blend of the original new token and the previous token(s). Hence, the TRM <NUM> implicitly treats the previous similar tokens as evidence of the characters and/or shapes that the user intended to create with respect to the new token. Section D provides further illustrative details regarding the operation of the TRM <NUM>.

<FIG> also indicates that the SPS <NUM> can provide optional other applications <NUM>, that is, instead of, or in addition to, the TRM <NUM>. For example, without limitation, the SPS <NUM> can include search functionality and auto-completion functionality. Section E provides further illustrative details regarding these two applications.

<FIG> shows a procedure <NUM> that provides an overview of one manner of operation of the SPS <NUM> of <FIG>. In block <NUM>, the SPS <NUM> receives input stroke samples. In block <NUM>, the SPS <NUM> forms a new token based on the input stroke samples (after optionally performing a resampling operation). In block <NUM>, the SPS <NUM> examines a collection of previous tokens to determine at least one previous token (if any) that is similar to the new token. In block <NUM>, the SPS <NUM> performs one or more actions based on the results of block <NUM>. For example, the SPS <NUM> can perform a token refinement operation in which the new token is beautified based on the previous tokens. Or the SPS <NUM> can perform a search operation, an auto-complete operation, etc. In block <NUM>, the SPS <NUM> provides output information which conveys a result of the processing performed in block <NUM>.

<FIG> provide examples of the use of the SPS <NUM> to beautify handwriting. Each figure includes two columns. The first column (labeled "pre-refinement") includes a series of original instances of handwriting created by a user, prior to the application of refinement. The second column (labeled "post-refinement") includes a series of beautified instances of handwriting produced by the SPS <NUM>. That is, each instance of beautified handwriting in the second column is a beautified counterpart of an adjacent original instance of handwriting in the first column.

First consider the case of <FIG>. Here, the pre-refinement column includes a series of instances of the same phrase, "Pencil + Paper," produced by the user in top to bottom order. That is, the topmost instance of "Pencil + Paper" represents the first instance of the phrase produced by the user, while the bottommost instance of "Paper + Paper" represents the last instance of this phrase produced by the user. The post-refinement column shows a series of counterpart phrases produced by the SPS <NUM>, following application of refinement.

Note that, as the user repeats the phrase "Pencil + Paper," the SPS <NUM> accumulates a knowledge base from which it can assess the typical manner in which this phrase is written by the user. The SPS <NUM> can leverage this knowledge by correcting the appearance of new instances of the phrase "Pencil + Paper" produced by the user, such that they more closely conform to previous instances of that phrase. For example, note that the fourth instance of the original phrase has two anomalies (<NUM>, <NUM>) (assessed relative to the previous instances). For the anomaly <NUM>, the curved line segment of the character "P" of "Pencil" has a tail that overshoots the vertical straight line segment of the character "P". For the anomaly <NUM>, the straight line segment of the "P" in "Paper" flares out to produce a loop. The SPS <NUM> produces corrections <NUM>'and <NUM>' based on previous instances of "Paper + Pencil" which do not contain these anomalies. For example, in correction <NUM>', the SPS <NUM> removes the tail which overshoots the straight line segment. In correction <NUM>', the SPS <NUM> collapses the loop associated with anomaly <NUM>.

The SPS <NUM> can display the beautified instances in relation to the original instances in any manner. In one case, the SPS <NUM> can overwrite the original instances with their beautified counterparts, once the beautified counterparts are calculated. For example, the SPS <NUM> can replace the original instances of the phrase "Pencil + Paper" with the beautified counterparts of these phrases, once they are calculated. The SPS <NUM> can also use various temporal blending strategies to achieve this effect, such as by gradually morphing the original instances into the beautified instances as the user writes. The user may perceive this effect as a refinement window which trails his or her handwriting, in which the user's original handwriting is gradually morphed into the beautified handwriting.

The SPS <NUM> can also adjust the position of the beautified instances so that they line up with the preceding writing, to thereby prevent the beautified writing from drifting away from the preceding writing. The SPS <NUM> can perform this task by computing an average position of the original instances, and an average position of the beautified instances. The SPS <NUM> can then shift the beautified instances by the difference between the two averages.

In another implementation, the SPS <NUM> can write the beautified instances on the output device without removing the original instances, such as by displaying the beautified instances beneath the original instances, or to the right of the original instances (as shown in <FIG>), or to the left of the original instances, or in a selectable pop-up window, or in any other relation with respect to the original instances. Still other presentation strategies are possible. The SPS <NUM> can also give the user an "undo" option, which allows the user to remove the effects of beautification.

Further note that, in the above examples, the SPS <NUM> operates on a moving window of immediately-preceding new handwriting based on a more encompassing corpus of past handwriting. The SPS <NUM> does not operate to correct instances of past handwriting which occur prior to that window. This means that, after the window moves on, the handwriting that appears in "back" of the window becomes fixed (meaning that it is no longer subject to beautification). But it is also possible to modify handwriting in back of this window. For example, in another implementation, the user may instruct the SPS <NUM> to make a global correction of handwriting in a document that is already produced based on the complete corpus of previous handwriting expressed in the document and elsewhere.

<FIG> shows another example in which the SPS <NUM> refines original instances of handwriting to produce beautified instances of handwriting. Here, the user successively writes the word "stylus," as indicated in the pre-refinement column (where only the last four entries are shown). The SPS <NUM> modifies these original instances into beautified instances of the word "stylus," as indicated in the post-refinement column (where, again, only the last four entries are shown). For example, consider an anomaly <NUM> in an original instance of the word "stylus," corresponding to the case in which a user produces the distended segment of the letter "y" as a single line. Assume that this is an anomaly insofar as the user typically writes this segment as a loop, not as a single line; note, however, that this is not evident from the limited number of samples shown in <FIG>. In response to this finding, the SPS <NUM> can replace the anomaly <NUM> with its correction <NUM>'.

<FIG> correspond to the case in which the handwriting corresponds to alphanumeric characters. But, more generally, the SPS <NUM> performs analysis in a manner which is agnostic to the nature of the user's handwriting. In other words, the SPS <NUM> can beautify any marks that resemble previous-input marks. Those marks can correspond to repetitive symbols in any language, repetitive pictures, or repetitive makings having no meaning whatsoever.

For instance, <FIG> shows an example in which a user produces a series of crude pictures of a vehicle, as shown in the pre-refinement column. Once the SPS <NUM> accumulates previous tokens associated with this picture, the SPS <NUM> can produce beautified counterpart instances of the pictures, as shown in the post-refinement column. For example, note that one such original instance includes an anomaly <NUM> in which a tire overlaps the body of the vehicle to a greater extent compared to previous pictures of the vehicle. The SPS <NUM> produces a correction <NUM>' which reduces the extent of this anomaly. Note that the SPS <NUM> does not entirely correct the anomaly, in that the tire still overlaps the body of the vehicle to some extent. This is because the anomaly <NUM> in the original picture was large enough so that it could not be completely "corrected" by the previous instances of the picture. This, in turn, stems from the fact that the beautified drawing represents an average of the original instance of the picture (which contains the anomaly) and the previous instances of the pictures (which omit the anomaly to varying extents).

As a general characteristic, note that the SPS <NUM> operates by correcting the user's handwriting based on previous instances of the same user's handwriting. Thus, the corrections that the SPS <NUM> makes generally conform to the writing style of the user, rather than some canonical template defining what constitutes a "correct" form of a character or geometrical shape. For example, if the user repetitively forms a character in an idiosyncratic way, then the SPS will not regard this character as anomalous, and thus will not correct it. In one implementation, the data store <NUM> can store the user's previous tokens over the course of any number of prior sessions, corresponding to any length of time (e.g., days, months, years, etc.), and any number of documents produced by the user. The SPS <NUM> can also optionally weight each token based on its time of creation, giving more weight to more recent tokens.

In another implementation, the SPS <NUM> can rely on a data store that contains tokens produced by plural users. Such a data store may be regarded as a user-agnostic token collection. In another implementation, the SPS <NUM> can rely on the user-agnostic token collection only to the extent that it has not yet accumulated sufficient knowledge of a particular user's handwriting style. For example, the SPS <NUM> can use the user-agnostic token collection almost exclusively when an individual user first begins to use the SPS <NUM>. The SPS <NUM> can thereafter reduce its reliance on the user-agnostic token collection in proportion to the current size of the user's personal token collection.

In another implementation, the SPS <NUM> can store multiple versions of user-agnostic token collections, each corresponding to a particular writing style. The SPS <NUM> can classify the user based on his or her writing style, and then use whatever user-agnostic token collection is appropriate for that style. Still other implementations are possible.

However, to simplify and facilitate explanation, the remainder of this description will assume that the data store <NUM> stores a collection of previous tokens produced by the handwriting of a particular user, for use in beautifying the handwriting of that user.

<FIG> shows one implementation of the TFM <NUM>. The TFM <NUM> includes an optional resampling module <NUM> and a token creation module <NUM>. The token resampling module <NUM> receives original stroke samples that have been created using any sampling technique. Each original stroke sample is denoted herein as φo. The token resampling module <NUM> then generates another representation of the handwriting, yielding resampled stroke samples. Each resampled stroke sample is denoted herein as φr. The token creation module <NUM> produces a series of tokens <NUM> over the course of time based on the resampled stroke samples. Each token is denoted herein as Φ.

More specifically, in one case, the resampling module <NUM> can produce a resampled version of the handwriting in which the rate at which samples are produced directly varies with the curvature of the handwriting. This means that the resampling module <NUM> can represent a relatively straight line segment with fewer sample points compared to a curved line segment.

In one implementation, the token creation module <NUM> produces a new token (Φ) each time the resampling module <NUM> provides a new stroke sample (φr). For example, assume that the token creation module <NUM> defines a new token as a succession of n samples, that is, <MAT>, where, in one case, n = <NUM>. When the token creation module <NUM> receives the next stroke sample (φr), it creates a new token having n samples. The new token is the same as the immediately previous token, except that it is shifted by one sample position relative to the previous token. In other words, if n = <NUM>, the new token shares <NUM> samples in common with the previous token. <FIG> pictorially illustrates the above-described overlapping nature of the tokens <NUM>.

The token size is selected to accommodate the formation of meaningful clusters. If the token size is too large, such that it encompasses an entire word (e.g., the word "mountain"), then the SPS <NUM> will not be able to quickly form a cluster for this token, since a user can be expected to infrequently write this word. And if the token size is too small (such that it encompasses just a single character), then the token will not capture contextual information that reflects how it is combined with other tokens. For example, the way that a user writes the character "a" will differ depending on the characters which precede and follow the character "a. " Choosing the token size large enough to encompass a few characters (e.g., <NUM>-<NUM> characters) provides a satisfactory solution in many implementations. For example, while the word "mountain" occurs infrequently, the character combination "oun" occurs quite often. More generally, the token creation module <NUM> can be configured to produce tokens of any size, depending on any environment-specific factor(s).

<FIG> shows a procedure <NUM> which represents one manner of operation of the resampling module <NUM>. This procedure <NUM> is described by way of illustration, not limitation; other implementations can adopt other resampling strategies. In this case, it is assume that both the original and resampled stroke samples are represented in polar coordinates. That is, each sample is defined by three values (r, θ, p), where r is a magnitude value which indicates a length of a line segment, θ is an angle value which indicates an orientation of the line segment with respect to some global reference frame, and p is the pressure of the stylus (or other writing implement) on the surface of the input device <NUM>. A pressure of zero indicates that the stylus is not in contact with the writing surface of the input device <NUM>.

By way of overview, the resampling module <NUM> assigns original stroke samples to "buckets," where each bucket corresponds to a particular resampled stroke sample. More specifically, the resampling module <NUM> operates to add original stroke samples to a bucket until a curvature-based value associated with the bucket exceeds some threshold. When this happens, the resampling module <NUM> will advance to the next bucket in the sequence of buckets. In this manner, the resampling module <NUM> will "fill" more buckets for curved lines, compared to straight lines.

More specifically, in block <NUM>, the resampling module <NUM> receives a new original stroke sample φo. In block <NUM>, the resampling module <NUM> determines whether the new original stroke sample φo, relative to the preceding original stroke sample, indicates that a user has placed the stylus onto the writing surface of the input device <NUM>, or removed the stylus from the writing surface. If so, then, in block <NUM>, the resampling module <NUM> produces a new resampled stroke sample φr. The resampling module <NUM> also "fixes" the previous resampled stroke sample (if any) that it was previously creating; this means that the resampling module <NUM> will stop adding original stroke samples to that previous "bucket.

In block <NUM>, assume that the new original stroke sample corresponds to a mark that a user has produced on the writing surface. Expressed in polar coordinates, assume that the mark has a length rk, an orientation θk, and a pressure pk. The resampling module <NUM> increments a variable value zk based on a change in orientation (ϑk) of the current original stroke sample relative to the previous original stroke sample. That is, zk is some function of ϑk, where ϑk = Δθ (k - <NUM>, k), where Δθ(a, b) = min (|θa - θb |, <NUM>π - |θa - θb|).

In block <NUM>, the resampling module <NUM> determines whether the value of zk exceeds some threshold. For example, assume that the resampling module <NUM> creates a bucket for values of zk from <NUM> up to <NUM>, and another bucket for values of zk from <NUM> up to <NUM>, and so on. In this case, in block <NUM>, the resampling module <NUM> can determine whether the value of zk has moved into the next integer bucket.

If the threshold has not been exceeded, the resampling module <NUM> can add the new original stroke sample to the existing resampled stroke sample being created in the current "bucket. " Assume that the accumulated line segment in the current bucket has a magnitude value rl, an orientation θl, and a pressure pl. The resampling module can update the new Cartesian endpoints (x, y) of the resampled stroke sample as x = rk cos(θk) + rlcos (θl) and y = rksin(θk) + rlsin (θl). The resampling module <NUM> can update the new pressure of the accumulated resampled stroke sample as pl = (rk * pk + rl * pl)/(rk + rl). The updated magnitude of the resampled stroke sample (after adding the new sample) corresponds to rl = ∥x, y∥. The updated orientation of the resampled stroke sample corresponds to θl = arctan (y, x).

In block <NUM>, alternatively assume that adding the current original stroke sample to the current bucket causes the value of zk to exceed the threshold. In response, the resampling module <NUM> creates a new bucket (corresponding to a new resampled stroke sample) and adds the original stroke sample as a first entry to the new bucket. At this point, the previous bucket (corresponding to the previous resamples stroke sample) becomes fixed, and the resampling module <NUM> adds future received original stroke samples to the new bucket.

Any function f(ϑk) can be used to compute zk. Without limitation, in one example, the resampling module <NUM> uses the following equation to compute zk: <MAT>.

Using this equation, the resampling module <NUM> produces a new value zk by adding the smaller of <NUM> and αβlϑk to the previous value of zk (i.e., zk-<NUM>). The value of <NUM> ensures that the resampling module <NUM> increases the value of zk by no more than <NUM>, which prevents the procedure <NUM> from skipping over a bucket, and which correspondingly prevents the token that is created from having entries with zero-length magnitudes. The parameter α controls the density of sampling. Without limitation, α can be set as <NUM>/π, which will roughly produce <NUM> samples for a drawn circle. The parameter βl prevents errors that would otherwise be caused by the discretization of the stylus position, that is, by reducing the values of z when the stroke magnitude rl is currently small, where rl corresponds to the length of the line segment to which rk is being added. Without limitation, in one case, the resampling module <NUM> can compute the parameter βl as max <MAT>.

<FIG> shows an example which clarifies the operation of the procedure <NUM> of <FIG>. The figure shows original handwriting <NUM> that is composed of a plurality of original stroke samples. Each original stroke sample is demarcated by a beginning sample point and an ending sample point (where each sample point is denoted in <FIG> as a black dot). The beginning sample point is the same as the ending sample point of the preceding sample (if any). The resampling module <NUM> converts the original handwriting <NUM> into resampled handwriting <NUM>. The resampled handwriting <NUM> is likewise composed of a plurality of resampled stroke samples, each of which is denoted by a beginning sample point and ending sample point.

Based on the procedure <NUM>, the resampling module <NUM> performs resampling based on the degree of curvature in the original handwriting <NUM>. More specifically, the resampling module <NUM> advances to a new bucket when the value zk exceeds a threshold, such as when the value zk exceeds an integer value associated with a current bucket. For example, the resampling module <NUM> adds an original stroke sample <NUM> to the first bucket <NUM> without exceeding the threshold of the first bucket (which, in this case, is <NUM>). The resampling module <NUM> then adds another original stroke sample <NUM> to the first bucket <NUM>, again without exceeding the threshold. But then assume that the resampling module <NUM> discovers that, by adding another stroke sample <NUM> to the first bucket <NUM>, it will exceed the threshold. In response, the resampling module <NUM> adds the stroke sample <NUM> as a first entry of the second bucket <NUM>. This procedure continues in the above-described manner, processing the original stroke samples in piecemeal fashion as the user produces the original handwriting <NUM>.

Upon reaching the straight line portion <NUM> of the original handwriting <NUM>, the resampling module <NUM> will discover that it can fit a relatively large number of original stroke samples into a single bucket. As a result, the resampled handwriting <NUM> can devote a single resampled stroke sample <NUM> to the straight line portion <NUM> of the original handwriting <NUM>.

Next assume that, at juncture <NUM> in the original handwriting, the user lifts the stylus off of the writing surface of the input device <NUM>. Then assume that, at juncture <NUM>, the user again applies the stylus to the writing surface. The resampling module <NUM> initiates the creation of a new resampled stroke sample for both of these events, as indicated by the resampled stroke samples <NUM> and <NUM> which appear in the resampled handwriting <NUM>. Further note that the resampling module <NUM> does not increment any bucket when a user's stylus is not in contact with the writing surface.

The resampling module <NUM> can use curvature-based resampling to efficiently represent handwriting. For example, the resampled handwriting <NUM> includes fewer strokes samples compared to the original handwriting <NUM>. By comparison, consider a constant-distance sampling technique, in which the resampling module <NUM> would create a new stroke sample for every fixed distance d traversed by the original handwriting <NUM>. Had the resampling module <NUM> used this technique, it would have created more resampled stroke samples compared to the above-described curvature-based resampling technique (depending, that is, on the value of d).

<FIG> conveys another advantage of the use of curvature-based resampling. Here, the TFM <NUM> produces resampled stroke samples to express a first token <NUM> and a second token <NUM>. The tokens (<NUM>, <NUM>) represent different instances of the characters "abc. " That is, while the tokens (<NUM>, <NUM>) express the same characters from a high-level semantic standpoint, the characters also vary from each other in various ways from a graphical standpoint. The TFM <NUM> can more effectively capture the similarity between the two tokens (<NUM>, <NUM>) using curvature-based resampling compared to, for instance, constant-distance resampling. This makes it more likely that stroke samples in the first token <NUM> will match up with stroke samples in the second token <NUM> (e.g., such that xth stroke sample in the first token <NUM> will match up with the xth stroke sample in the second token <NUM>).

Moreover, to further reduce the difference between the tokens (<NUM>, <NUM>), the TFM <NUM> can normalize their stroke magnitudes. This reduces the variation in scale between the tokens (<NUM>, <NUM>), e.g., such that a large version of the characters "abc" can be effectively compared with a smaller version of the characters "abc. " That is, the TFM <NUM> produces a normalized magnitude value, <MAT>, for each sample in a token using rk/ηk, where ηk may be computed as a Gaussian weighted running average of the stroke magnitudes in the token. In the following description, the magnitudes rk may be normalized in above-described manner, although not explicitly stated.

The similarity between the tokens (<NUM>, <NUM>) is further evident by comparing their descriptors (<NUM>, <NUM>). In general, a descriptor refers to a way of describing a token. In the case of <FIG>, the SPS <NUM> represents each token as two histograms, such as, for the first token <NUM>, a first histogram <NUM> and a second histogram <NUM>. Both histograms (<NUM>, <NUM>) express the samples of the first token <NUM> along their horizontal axes, that is, from a first sample φi to a last sample φi+n. The vertical dimension of the first histogram <NUM> expresses the orientation (θ) of each sample. The density of each data point in the first histogram <NUM> expresses the magnitude value (r) of a sample. Here, dark points correspond to relatively high r magnitudes. The density of each data point in the second histogram <NUM> expresses a pressure value (p). Here, dark points correspond to relative low pressures; for example, the darkest points indicate that the user has lifted the stylus off of the writing surface of the input device <NUM>. (Note that <FIG> depicts only a few shades of density in the histograms to facilitate illustration, although, in actual practice, a histogram may express additional density gradations. ) The second descriptor <NUM> is also composed of two histograms (<NUM>, <NUM>) that express the same information as the histograms (<NUM>, <NUM>) described above.

More generally, the histograms in <FIG> use a temporal representation to describe the tokens (<NUM>, <NUM>). This is, each token is created in piecemeal fashion, sample by sample, as the user writes on the writing surface of the input device <NUM>. This means that the horizontal axis of each histogram is a proxy for a succession of instances of time.

Overall, observe that the first descriptor <NUM> resembles the second descriptor <NUM>. This is due, in part, to the use of curvature-based resampling to represent the handwriting. For instance, consider the alternative case in which the resampling module <NUM> uses constant-distance resampling to produce descriptors for the two instances of the characters "abc" shown in <FIG>. The descriptors (not shown) for these tokens would not exhibit the same degree of correlation as is depicted in <FIG>.

With that said, the TFM <NUM> can also be implemented using other types of resampling strategies besides curvature-based sampling, including constant-distance sampling strategies. Further, in those cases in which curvature-sampling is used, the resampling module <NUM> can use other techniques for defining the samples, besides the procedure <NUM> shown in <FIG>.

<FIG> shows one implementation of the similarity assessment module (SAM) <NUM>. As noted in Section A, the SAM <NUM> determines the similarity between a new token and previous tokens. A new token corresponds to a most recent token that has been defined by the TFM <NUM>, while a previous token corresponds to a token that has been previously defined by the TFM <NUM>. The data store <NUM> stores the previous tokens.

In general, the SAM <NUM> can compare the new token with a previous token by forming a descriptor of the new token and another descriptor of the previous token. The SAM <NUM> can then use any technique to compare the two descriptors. If the difference between the two descriptors is below a prescribed threshold, then the SAM <NUM> concludes that the new token is similar to the previous token.

A cluster management module <NUM> forms clusters <NUM> of tokens. Each cluster includes a set of tokens that have been previously assessed as being similar to each other. Each cluster also includes a cluster representative, such as a cluster mean Ψ. The cluster mean Ψ represents the average of the tokens within the cluster. The SAM <NUM> operates by comparing the new token with each of the cluster representatives, instead of the individual previous tokens.

The cluster management module <NUM> can also add the new token to whatever cluster that it most closely matches. The cluster management module <NUM> can perform this task by updating the cluster mean to take into consideration the contribution of the new token, e.g., by averaging the cluster mean with the new token to produce a new cluster mean. Alternatively, if there is no sufficiently similar existing cluster, the cluster management module <NUM> can create a new cluster. Initially, the new cluster includes a single member, corresponding to the new token.

The SAM <NUM> can adopt any approach to determine the similarity between two tokens (e.g., between a new token and a token mean). In one approach, the SAM <NUM> includes a coarse similarity determination module <NUM> and a fine similarity determination module <NUM>. The coarse similarity determination module <NUM> uses temporal analysis to make a first-level assessment of the similarity between two tokens. This temporal analysis yields a set of candidate tokens, e.g., corresponding to a candidate set of cluster means which match the new token (if any). The fine similarity determination module <NUM> uses spatial analysis to verify whether each of the candidate tokens is indeed a suitable match for the new token.

<FIG> shows a procedure <NUM> which summarizes the operation of the SAM <NUM>. In block <NUM>, the SAM <NUM> determines the coarse similarity between the new token and each of the previous tokens (or the cluster means), to produce a set of candidate tokens. In block <NUM>, the SAM <NUM> uses spatial analysis to verify whether each candidate token is indeed a suitable match for the new token. The individual sub-steps in blocks <NUM> and <NUM> will be described at a later juncture in this section.

In one implementation, the SPS <NUM> can perform the operations in blocks <NUM> and <NUM> for all similarity comparisons that it performs, including case A in which the SPS <NUM> uses similarity analysis to find the closest-matching cluster for the purpose for updating the clusters, and case B in which the SPS <NUM> uses similarity analysis to find a set of similar clusters for the purposes of beautifying a new token. In another implementation, for case A, the SPS <NUM> can perform block <NUM>, but not block <NUM>.

<FIG> shows a procedure <NUM> which summarizes the operation of the cluster management module <NUM>. In block <NUM>, the cluster management module <NUM> receives a new token. In block <NUM>, the cluster management module <NUM> relies on the SAM <NUM> to determine the similarity between the new token and the cluster representatives (e.g., the cluster means). In block <NUM>, the cluster management module <NUM> determines whether there are any clusters which match the new token within a predetermined threshold τ (using the analysis in just block <NUM>, or the two-stage analysis of blocks <NUM> and <NUM>). If there is at least one such cluster, in block <NUM>, the cluster management module <NUM> can use the TRM <NUM> to merge the new token into the closest-matching cluster (in a manner described below). In another implementation, not shown, the cluster management module <NUM> can potentially add the token to two or more clusters that satisfy the above similarity threshold.

Alternatively, in block <NUM>, assume that the cluster management module <NUM> determines that no cluster is suitably similar to the new token. In that case, the cluster management module <NUM> creates a new cluster to represent the new token. That new cluster initially includes one member, corresponding to the new token.

Block <NUM> in <FIG>, together with the example of <FIG>, illustrate one technique for performing coarse-level temporal analysis on each pair of tokens to be compared. The SAM <NUM> begins by expressing each token using a single descriptor <NUM>. That descriptor <NUM> corresponds to the type of histogram <NUM> shown in <FIG>; that is, the descriptor <NUM> describes orientation (θ) and magnitude (r) values as a function of samples (φ). In step (<NUM>) of block <NUM>, the SAM <NUM> breaks the single descriptor <NUM> into two separate descriptors (<NUM>, <NUM>). A first descriptor <NUM> describes the stroke samples for the times when the stylus is in contact with the display surface. The second descriptor <NUM> describes strokes samples for the times when the stylus is not in contact with the display surface.

In step (<NUM>), the SAM <NUM> blurs both descriptors (<NUM>, <NUM>) in the temporal dimension, e.g., by modifying the values in the descriptors (<NUM>, <NUM>) using a Gaussian function. This yields blurred descriptors (<NUM>, <NUM>). In step (<NUM>), the SAM <NUM> takes the logarithm of the magnitudes in the blurred descriptors (<NUM>, <NUM>). This operation is performed because small stroke samples may be as visually salient as large stroke samples; this operation helps equalizes changes across scale. In step (<NUM>), the SAM <NUM> weights the results of step (<NUM>) by a temporally centered Gaussian. The resultant processed pen-down and pen-up descriptors may then be combined to form a single vector.

The SAM <NUM> performs the above described operations on each token to be compared. More specifically, consider the case in which a new token is being compared with a cluster mean. The SAM <NUM> performs the above-described processing on the new token and, separately, on the cluster mean. This ultimately yields two vectors for comparison. In step (<NUM>), the SAM <NUM> then uses any comparison technique to compare the two vectors, such as by computing the L2 distance between the vectors. By performing this same procedure for each pairing of the new token and a cluster mean, the SAM <NUM> can identify the set of clusters which are within a prescribed threshold distance of the new token (if any). This yields zero, one, or more candidate tokens for verification in block <NUM> of the procedure <NUM>.

Block <NUM> in <FIG>, together with the example of <FIG>, illustrate one technique for performing fine-level spatial analysis on each candidate token to be compared with the new token. In step (<NUM>), the SAM <NUM> begins by forming a low-resolution descriptor of each token to be compared, such as the low-resolution descriptor <NUM> shown in <FIG>. In other words, the SAM <NUM> provides a spatial rendering of the token, duplicating its appearance as drawn by the user. In step (<NUM>), the SAM <NUM> weights the intensity of the rendered strokes by their respective temporal distances to the center of the token. In other words, when drawing the token, the user produces strokes in a certain temporal order; the SAM <NUM> weights the strokes that were made at the beginning and end of the process the least, and the strokes that occur in the middle of the process the most. In step (<NUM>), the SAM <NUM> spatially blurs the results of step (<NUM>) by a few pixels, e.g., to produce the blurred descriptor <NUM>. In step (<NUM>), the SAM <NUM> centers the token content in the blurred descriptor produced in step (<NUM>), e.g., so that the middle of the token is placed in the middle of the descriptor.

The SAM <NUM> performs the above-described process for each pair of tokens to be compared for verification. For example, the SAM <NUM> can perform the above-described process on a new token and a particular cluster mean that was identified by the coarse-level analysis performed in block <NUM>. This yields two descriptors for the two respective tokens being compared. In step (<NUM>), the SAM <NUM> then computes the distance between each pair of descriptors using any technique, such as by forming the L2 distance. More specifically, the SAM <NUM> can form the difference between each position in a first descriptor with each corresponding position in a second descriptor, yielding, as a whole, a plurality of differences. The similarity assessment module sums these differences to generate a final distance measure q. In step (<NUM>), the SAM <NUM> can form a final confidence score λ using a normal distribution on the distance measure q, e.g., using the equation λ = exp (-q/<NUM>σ<NUM>).

The SAM <NUM> performs the fine-grained spatial analysis (in block <NUM>) described above because the coarse-grained temporal analysis (in block <NUM>) may not always be sufficient to identify similar tokens. The example of <FIG> demonstrates this point. As shown there, a double-"e" token <NUM> and an "a"-character token <NUM> yield the respective temporal descriptors (<NUM>, <NUM>). By comparison, two double-"e" tokens (<NUM>, <NUM>) yield the respective temporal descriptors (<NUM>, <NUM>). An observer can see that the double-"e" token <NUM> is not a good match with the "a"-character token <NUM>. Yet the distinction between descriptors <NUM> and <NUM> is not much greater than the distinction between the descriptors <NUM> and <NUM>. In other words, the temporal analysis fails to clearly reveal the difference between the double-"e" token <NUM> and the "a"-character token <NUM>. To address this shortcoming, the SAM <NUM> performs the above-described spatial comparison between descriptors. There is, in fact, a salient difference between the spatial descriptor <NUM> (corresponding to the double-"e" token <NUM>) and the spatial descriptor <NUM> (corresponding to the "a"-character token <NUM>), relative to the difference between spatial descriptors <NUM> and <NUM> (corresponding to two double-"e" tokens, <NUM> and <NUM>).

As described above, the SAM <NUM> can compare each new token with respect to each individual previous token. Or to be more efficient, the SAM <NUM> can compare each new token with each cluster mean. But comparison using cluster means may itself represent a resource-intensive computation. To address this issue, the remainder of this section describes one technique for further expediting the search to find similar previous tokens.

First consider the example of <FIG>. This figure shows a current token (Φcurrent), which represents the most recent token that has been processed by the SPS <NUM>. This current token is preceded by a previous token (Φprevious). As described above, the current token has <NUM> samples in common with the previous token, corresponding to portion <NUM>. That is, the new token adds one sample <NUM> that is not present in the previous token, and omits one token <NUM> that is present in the previous token. Further assume that the SAM <NUM> has already determined that the previous token is most similar to a particular cluster mean, Ψclosest. If there is no good match between Φprevious and an existing cluster mean, then Φprevious is assigned to a new cluster with Ψclosest = Φprevious.

The SAM <NUM> can pre-compute the clusters which are similar to Ψclosest. Assume, for example, that the cluster management module <NUM> is forced to define a new cluster for <Pprevíous because there is no existing cluster which is sufficiently similar to Φprevious. After creating the new cluster, the SAM <NUM> compares the portion <NUM> with other existing cluster means, with the omission of the terminal sample in these other cluster means, e.g., corresponding to sample <NUM>. Assume, for example, that the SAM <NUM> determines that the portion <NUM> is similar to cluster means Ψa, Ψb, and Ψc, when the terminal sample is removed from these cluster means. The SAM <NUM> then stores this association, e.g., in a lookup table or the like. That is, the association links Ψclosest with cluster means Ψa, Ψb, and Ψc. Then, when it comes time to compute the similarity between the current cluster and the cluster means (Φcurrent), the SAM <NUM> can compare the current token with the related cluster means Ψa, Ψb, and Ψc, rather than the entire set of cluster means (which may be a large number). The comparison is made by considering the full version of each of these related cluster means, e.g., by now including the terminal sample of these cluster means in the comparison.

<FIG> shows a procedure <NUM> for establishing the relationship between a token and a related set of clusters, e.g., in the above case, by establishing the relationship between the portion <NUM> and its set of related cluster means (Ψa, Ψb, Ψc). The procedure <NUM> is performed by the cluster management module <NUM> using the SAM <NUM>. In block <NUM>, the cluster management module <NUM> receives a new token (Φcurrent). In block <NUM>, the cluster management module <NUM> determines whether the new token is sufficiently similar to one of the existing clusters. If so, in block <NUM>, the cluster management module <NUM> merges the new token with the cluster mean of the closest-matching cluster. Since this cluster already exists, it is not necessary to compute the set of other clusters which are related to this closest-matching cluster; that is, the assumption is that the cluster management module <NUM> has already determined the related set for this closest-matching cluster, e.g., when it was initially created.

Alternatively, in block <NUM>, assume that the new token does not match any existing clusters. In response, the cluster management module <NUM> creates a new cluster associated with the new token. In block <NUM>, the cluster management module <NUM> then attempts to find the set of other clusters which are related to the new token (where the comparison is, more precisely stated, between the portion <NUM> and the version of each cluster mean that omits the terminal sample of the cluster mean). In one approach, the cluster management module <NUM> can perform this task by comparing the new token with each existing individual cluster mean. In another approach, the cluster management module <NUM> can perform this task by randomly sampling a prescribed number γ of cluster means. Assume that, in this random search, the cluster management module <NUM> discovers a cluster mean t which is related to the new token. The lookup table will reveal that cluster t, in turn, is related to a predetermined set of clusters (e.g., clusters f, g, h, etc.). Based on this knowledge, the cluster management module <NUM> then determines the similarity between the new token and each of the discovered related tokens, e.g., by comparing the new token with cluster mean f, cluster mean g, cluster mean h, and so on. In block <NUM>, the cluster management module <NUM> stores the relationships established in block <NUM>, e.g., by storing an index which links the new cluster that has been created (to hold the new token) with the discovered set of related cluster means. The procedure <NUM>, considered as a whole, establishes a cross-linked collection of clusters, where the lookup table links ever cluster with a related set of clusters (if any).

<FIG> shows a procedure <NUM> for applying the relationships learned via the procedure <NUM> of <FIG>. In block <NUM>, the SAM <NUM> receives a new token (Φcurrent) which follows a previous token (Φprevious). In block <NUM>, the SAM <NUM> identifies the cluster mean (Ψprevious) which matches the previous token. (Note that the SAM <NUM> has determined this cluster mean in a previous step, when the previous token constituted the current token. ) In block <NUM>, the SAM <NUM> identifies a set of related cluster means that have been predetermined to be similar to Ψprevious. In block <NUM>, the SAM <NUM> compares the new token with each of the cluster means in the set of identified cluster means.

<FIG> shows one implementation of the token refinement module (TRM) <NUM> of <FIG>. The TRM <NUM> receives the new token and each of the similar tokens identified by the SAM <NUM>. Consider the simplified case in which just two tokens are to be merged. An alignment determination module <NUM> aligns the samples of the first token with the corresponding tokens of the second sample. This produces correlated tokens. A token blending module <NUM> then blends the correlated tokens with each other.

In one application, the SPS <NUM> calls on the TFM <NUM> to blend a new token with a cluster mean that is determined to most closely match the new token. The SPS <NUM> performs this task when it operates to update its set of clusters stored in the data store <NUM>. In another application, the SPS <NUM> calls on the TRM <NUM> to blend a new token with a set of cluster means that have been determined to match the new token, within some threshold level of similarity. The SPS <NUM> performs this task when it seeks to refine the appearance of the new token based on previous similar tokens.

<FIG> is a procedure <NUM> which summarizes the operation of the TRM <NUM>. In block <NUM>, the TRM <NUM> receives a new token. In block <NUM>, the TRM <NUM> receives one or more similar tokens from the SAM <NUM>. In block <NUM>, the TRM <NUM> aligns each of the previous tokens with the new token (using a technique to be described below). In block <NUM>, the TRM <NUM> can blend the samples of the new token with the correlated samples in the similar previous token(s).

More specifically, the TRM <NUM> can perform the operations of block <NUM> by converting each endpoint that will contribute to the average from polar coordinates to Cartesian coordinates, e.g., using xk = rkcos (θk) and yk = rksin (θk), where (rk, θk) corresponds to one of the samples to be averaged. The TRM <NUM> can then average all the x values (associated with the contributing samples) together to provide an average x for the resultant averaged sample, and similarly for the y values. The TRM <NUM> can then convert the resultant averaged sample points back into polar coordinates. The TRM <NUM> can compute a blended pressure value by averaging the individual p values, where each individual p value is weighted by the magnitude (r) of its corresponding sample. Note that, when performing blending for the purpose of beautifying a new token, the TRM <NUM> can perform additional computations that are not specified in <FIG>, but will be described below.

<FIG> shows determining the correlation between samples in a first token <NUM> and a second token <NUM>. The first token <NUM> is represented by a first descriptor <NUM> which presents orientation (θ) and magnitude (r) values as a function of samples (φ), and a second descriptor <NUM> which presents pressure (p) values as a function of samples (φ). Likewise, the second token <NUM> is described by first and second descriptors (<NUM>, <NUM>). The alignment determination module <NUM> first computes a cost matrix <NUM>. Each cell in the cost matrix is defined by a first index which identifies a sample in the first token <NUM> and a second index which identifies a sample in the second token <NUM>. The cell has a value which describes the difference (ω) between the identified samples in the first and second tokens (<NUM>, <NUM>). In one case, the difference can be computed as: <MAT>.

In this equation, the value Δr corresponds to the absolute difference between the magnitudes of the two tokens, e.g., Δr = |rtoken<NUM> - rtoken<NUM>|. The value Δθ corresponds to the absolute angular distance between the orientation values of the two tokens, e.g., Δθ = |θtoken<NUM> - θtoken2|. The value δp = <NUM> if ptoken1 = <NUM> and ptoken<NUM> = <NUM>, or if ptoken<NUM> > <NUM> and ptoken<NUM> > <NUM>; the value of δp is <NUM> otherwise.

The alignment determination module <NUM> then finds a least cost path <NUM> through the cost matrix <NUM>, from cell c<NUM> to cell cnn. In choosing the path, the alignment determination module <NUM> can choose from among three moves at each step {(<NUM>,<NUM>), (<NUM>,<NUM>), and (<NUM>,<NUM>)}, corresponding to: (a) a move from left to right, →; (b) a move in the upward direction, ↑; and (<NUM>) a diagonal move, ↗. Each move to a destination cell has a particular cost value associated with it, defined by ω + ξ, where small cost values are more preferable than large cost values. The value ω is defined above; in this context, ω measures the similarity between the two tokens that are identified by the indices of the destination cell. The value ξ favors diagonal moves by assigning a value of <NUM> for a diagonal move and a small positive value (e.g., <NUM>) otherwise. The alignment determination module <NUM> can use any technique to compute the path <NUM>, such as, but not limited to, a dynamic programming technique.

The token blending module <NUM> can blend a new token with similar previous tokens (for the purpose of stroke beautification) in the following manner. First consider the observation that any given stroke sample φi in a new token may actually represent a sample in n different tokens, i.e., Φi-n to Φi (that is, presuming that φi is at least one token length "old"). Each of these tokens Φj with j ∈ [i - n, i] has its own set of candidate cluster matches mj with corresponding confidence scores λik, k ∈ mj. The confidence score λjk refers an extent to which a token Φj matches the cluster mean Ψk, which may be computed using a normal distribution on the L2 distance. For the cluster mean Ψk, the sample Φl ∈ Ψk with l = i - j will contribute to the refinement of the stroke sample φi. The weight wijk assigned to the sample φl can be computed using, <MAT>.

In this equation, <IMG> refers to a normal distribution with, for example, a mean of n/<NUM> and standard deviation of σ = n/<NUM>. The use of a Gaussian weighting ensures a smooth transition between the contributions of various tokens in the refinement.

Using the above weights, the token blending module <NUM> can now calculates the x̃i Cartesian value of a refined endpoint as follows: <MAT>.

In this equation, xi refers to an x coordinate value in the new token to be refined, and xl corresponds to a coordinate value in a cluster mean, which contributes to the refinement of the new token. These Cartesians values can be computed from the stored polar coordinates in the manner described above. The value wijk corresponds to the weighting factor that is computed in the manner described above. The value sk reflects the size of the cluster k, e.g., corresponding to the square root of the cluster's size; hence, the above equation assigns a higher weight to larger clusters. The refined value of the Cartesian coordinate ỹi, and the refined value of the pressure p̃i, can be computing using a similar manner to that described above for x̃i. In practice, the token blending module <NUM> may wait until a sample is at least one token length "old" before refining it.

<FIG> shows one implementation of search functionality <NUM>, which represents another application of the SPS <NUM>, instead of, or in addition to, the refinement application. The search functionality <NUM> includes an index management module <NUM> for creating and managing an index. A data sore <NUM> stores the index. More specifically, the index management module <NUM> stores a link between the previously encountered tokens and the respective locations of those tokens within documents. For example, assume that a user has written the word "Sue" several times in the past. The SAM <NUM> may identify one or more clusters which contain tokens associated with this word. The index management module <NUM> also stores information in the index which describes the locations at which the tokens appear within documents that the user has previously created.

A search module <NUM> can provide any search result in response to the user's input tokens. For example, assume that the user again inputs the word "Sue. " The search module <NUM> can, first of all, receive information from the SAM <NUM>, which indicates the token(s) that are associated with the word "Sue. " The search module <NUM> can then interact with the index to determine the respective locations of previous instances of the word "Sue" in the documents that have been previously created by the user. The search module <NUM> may then notify the user of those previous occurrences in any manner, such as by displaying a document <NUM> containing the word Sue <NUM>, and highlighting that word Sue <NUM> in that document <NUM> in any manner.

<FIG> shows one implementation of auto-completion functionality <NUM>, which represents another application of the SPS <NUM>, instead of, or in addition to, the refinement application. The auto-completion functionality <NUM> includes a prediction determination module <NUM> which predicts the likelihood that one token will follow another token. The auto-completion functionality <NUM> can perform this task in any manner, e.g., by counting co-occurrences of tokens within a training corpus, and then training an n-gram model based on those count values. A data store <NUM> can store prediction information which indicates the predictions made by the prediction determination module <NUM>.

An auto-completion module <NUM> performs an auto-completion operation based on the prediction information stored in the data store <NUM>. Assume, for example, that the user inputs the word "Best" <NUM>, with a capital "B. " The SAM <NUM> can interpret this word by matching the tokens associated with this word with previous tokens. The auto-completion module <NUM> receives the matching token information from the SAM <NUM>. In response, it determines, based on the prediction information in the data store <NUM>, the tokens (if any) which are likely to follow the tokens that make up the word "Best. " Assume that the user has written the phrase "Best regards" many times in the past when closing his or her handwritten letters. The auto-completion module <NUM> may therefore identify the tokens that make up the word "Regards" as a likely word to follow the word "Best.

The auto-completion module <NUM> can then present its findings to the user in any manner, such as by displaying the word "Regards" <NUM> next to the word "Best. " The user can select the word "Regards" to formally add this word to his or her writing, or continue writing to effectively ignore the recommendation of the auto-completion functionality <NUM>.

The search functionality <NUM> and auto-completion functionality <NUM> were described above by way of example, not limitation. Other applications can leverage the above-described features of the SPS <NUM>.

<FIG> shows a procedure <NUM> which provides an overview of the operation of the search functionality <NUM> and auto-completion functionality <NUM>. In block <NUM>, the SPS <NUM> receives a new token. In block <NUM>, the SPS <NUM> identifies previous tokens (if any) which are similar to the new token. In block <NUM>, the SPS <NUM> performs a search operation and/or auto-completion operation based on the similar token(s) identified in block <NUM>.

<FIG> represents a standalone implementation of the SPS <NUM> of <FIG>. That is, in this implementation, local computing equipment <NUM> can implement all aspects of the SPS <NUM>. <FIG> conveys this point by indicating that the local computing equipment <NUM> includes local SPS functionality <NUM>. The local computing equipment <NUM> can be implemented by a personal computer, a computer workstation, a laptop computer, a tablet-type computer, a game console, a set-top box device, a media consumption device, a smartphone, and so on.

<FIG> shows a distributed implementation of the SPS <NUM>, where the SPS functionality is distributed between local computing equipment <NUM> and remote computing equipment <NUM>. That is, the local computing equipment <NUM> may implement local SPS functionality <NUM>, while the remote computing equipment <NUM> may implement remote SPS functionality <NUM>. The local computing equipment <NUM> can be implemented using any technology described above with respect to <FIG>. The remote computing equipment <NUM> can be implemented, for instance, using one or more servers and associated data stores. A communication mechanism <NUM> may connect the local computing equipment <NUM> with the remote computing equipment <NUM>. The communication mechanism <NUM> can be implemented using a local area network, a wide area network (e.g., the Internet), a point-to-point connection, etc., or any combination thereof.

In one scenario, for example, the remote SPS functionality <NUM> can maintain the data store <NUM> which stores the previous tokens. The remote SPS functionality <NUM> can download the previous tokens to the local SPS functionality <NUM> for use by the local SPS functionality <NUM> in analyzing handwriting. In another case, the remote SPS functionality <NUM> can also perform one or more processing functions of the SPS <NUM>, as described above. For example, the local SPS functionality <NUM> can offload its most resource-intensive computations to the remote SPS functionality <NUM>.

<FIG> sets forth illustrative computing functionality <NUM> that can be used to implement any aspect of the functions described above. For example, the type of computing functionality <NUM> shown in <FIG> can be used to implement any aspect of SPS <NUM> of <FIG>, using the functionality of <FIG>, the functionality of <FIG>, or some other functionality. In one case, the computing functionality <NUM> may correspond to any type of computing device that includes one or more processing devices. In all cases, the computing functionality <NUM> represents one or more physical and tangible processing mechanisms.

The computing functionality <NUM> can include volatile and non-volatile memory, such as RAM <NUM> and ROM <NUM>, as well as one or more processing devices <NUM> (e.g., one or more CPUs, and/or one or more GPUs, etc.). The computing functionality <NUM> also optionally includes various media devices <NUM>, such as a hard disk module, an optical disk module, and so forth. The computing functionality <NUM> can perform various operations identified above when the processing device(s) <NUM> executes instructions that are maintained by memory (e.g., RAM <NUM>, ROM <NUM>, or elsewhere).

More generally, instructions and other information can be stored on any computer readable medium <NUM>, including, but not limited to, static memory storage devices, magnetic storage devices, optical storage devices, and so on. The term computer readable medium also encompasses plural storage devices. In many cases, the computer readable medium <NUM> represents some form of physical and tangible entity. The term computer readable medium also encompasses propagated signals, e.g., transmitted or received via physical conduit and/or air or other wireless medium, etc. However, the specific terms "computer readable storage medium" and "computer readable medium device" expressly exclude propagated signals per se, while including all other forms of computer readable media.

The computing functionality <NUM> also includes an input/output module <NUM> for receiving various inputs (via input devices <NUM>), and for providing various outputs (via output devices). Illustrative input devices include a keyboard device, a mouse input device, a touchscreen input device, a digitizing pad, a gesture input device, a voice recognition mechanism, tabletop or wall-projection input mechanisms, and so on. One particular output mechanism may include a presentation device <NUM> and an associated graphical user interface (GUI) <NUM>. The computing functionality <NUM> can also include one or more network interfaces <NUM> for exchanging data with other devices via one or more communication conduits <NUM>. One or more communication buses <NUM> communicatively couple the above-described components together.

The communication conduit(s) <NUM> can be implemented in any manner, e.g., by a local area network, a wide area network (e.g., the Internet), etc., or any combination thereof. The communication conduit(s) <NUM> can include any combination of hardwired links, wireless links, routers, gateway functionality, name servers, etc., governed by any protocol or combination of protocols.

Alternatively, or in addition, any of the functions described in the preceding sections can be performed, at least in part, by one or more hardware logic components. For example, without limitation, the computing functionality can be implemented using one or more of: Field-programmable Gate Arrays (FPGAs); Application-specific Integrated Circuits (ASICs); Application-specific Standard Products (ASSPs); System-on-a-chip systems (SOCs); Complex Programmable Logic Devices (CPLDs), etc..

In closing, functionality described herein can employ various mechanisms to ensure the privacy of user data maintained by the functionality (if any). For example, the functionality can allow a user to expressly opt in to (and then expressly opt out of) the provisions of the functionality. The functionality can also provide suitable security mechanisms to ensure the privacy of the user data (such as data-sanitizing mechanisms, encryption mechanisms, password-protection mechanisms, etc.).

Further, the description may have described various concepts in the context of illustrative challenges or problems. This manner of explanation does not constitute an admission that others have appreciated and/or articulated the challenges or problems in the manner specified herein.

Claim 1:
A stroke processing system (<NUM>) for processing handwriting (<NUM>, <NUM>), implemented by one or more processing devices, and one or more storage devices storing computer readable instructions which, when executed by the one or more processing devices, cause the one or more processing devices to
receive input stroke samples (<NUM>) that represent handwriting (<NUM>, <NUM>) of a user produced using an input device (<NUM>);
store in a data store (<NUM>) a collection of previous tokens obtained by processing previous handwriting instances produced by the user, wherein a token represents a set of temporally adjacent input stroke samples in a handwriting instance, wherein the data store maintains the previous tokens as a plurality of clusters (<NUM>),
each cluster comprising a set of similar previous tokens, wherein each cluster is associated with a cluster representative and wherein the cluster representative represents an average of the tokens within a cluster;
process a new handwriting instance produced by the user to obtain a new token (<NUM>)
representing new temporally adjacent input stroke samples in the new handwriting instance (<NUM>);
generate a first temporal descriptor for each of the cluster representatives, and a second temporal descriptor for the new token;
designate at least one of the cluster representatives as a selected cluster representative responsive to a determination that its first temporal descriptor and the second temporal descriptor are within a prescribed threshold;
modify an appearance of the new handwriting instance produced by the user by modifying coordinates of the new token using coordinates of each of the selected cluster representatives;
wherein the modifying further comprises:
aligning stroke samples associated with each of the selected cluster representatives with stroke samples of the set of the input stroke samples to produce correlated stroke samples;
averaging the correlated stroke samples; and
modifying an appearance of the set of the input stroke samples using the averaged correlated stroke samples.