FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10; rule 13)
Title: “SYSTEM AND METHOD FOR SEARCHING
HANDWRITTEN TEXTS”
NAME OF THE APPLICANT AND ADDRESS: INDIAN INSTITUTE OF SCIENCE,
Bangalore 560 012, Karnataka, India.
NATIONALITY: Indian
Attorney’s Docket No.: MBHB Case No. 09-461
The following specification particularly describes the nature of this invention and the manner in
which it is to be performed.
Attorney’s Docket No.: MBHB Case No. 09-461
2
BACKGROUND
[0001] In the last decade, there has been a tremendous increase in the popularity and
widespread use of mobile devices. Although mobile devices and PDAs support touch
sensitive screens that are naturally suited for handwritten input, keypads continue to be
the primary input interface. Current handwriting recognition technologies are not yet
reliable enough for most users. Text recognition is particularly lacking for written
languages with complex character sets.
[0002] More recently, the use of digital ink, which is the storing of raw handwritten data
directly without performing text recognition, has been gaining in popularity. Use of
digital ink opens the possibility of forgoing the need for text recognition altogether and
simply operating and accessing stored handwritten notes in their raw format. The
usability of handwritten digital ink documents written in can be greatly increased if
previously handwritten documents can be searched.
SUMMARY
[0003] In one embodiment, a method for searching handwritten notes comprises storing a
handwritten note in a bivariate time format; receiving a handwritten query note in the
bivariate time format; generating finite sequences based on pair hidden Markov models
using a portion of the handwritten note and a portion of the handwritten query note;
providing a joint probability distribution based on the finite sequences; calculating a
similarity score based on the joint probability distribution; and comparing the similarity
score against a criterion.
[0004] In another embodiment, the method further comprises wherein the similarity score
is based on the highest probability value in the joint probability distribution.
[0005] In another embodiment, the method further comprises wherein a highest
probability value in the joint probability distribution is acquired using a Viterbi
algorithm.
Attorney’s Docket No.: MBHB Case No. 09-461
3
[0006] In one embodiment, a method for searching handwritten notes comprises storing
an array of handwritten notes in a bivariate time format; receiving a handwritten query
note in the bivariate time format; calculating a similarity score for each handwritten note
in the array of handwritten notes by generating finite sequences based on pair hidden
Markov models using a portion of each handwritten note in the array and a portion of the
query note, and acquiring a highest probability value from a joint probability distribution
of the finite sequences; comparing each similarity score against a criterion; and
generating an array of similar handwritten notes comprising handwritten notes with
corresponding similarity scores that meet the criteria.
[0007] In another embodiment, the method further comprises wherein acquiring highest
probability values from a joint probability distribution of the finite sequences is achieved
using a Viterbi algorithm.
[0008] In another embodiment, the method further comprises segmenting the handwritten
notes based on a distance threshold.
[0009] In another embodiment, the method further comprises rescaling the handwritten
notes and the handwritten query note to having matching heights before calculating a
similarity score.
[0010] In another embodiment, the method further comprises wherein calculating a
similarity score accounts for variations in the start points and positions of the handwritten
notes and the handwritten query note.
[0011] In one embodiment, an apparatus for searching handwritten notes comprises a
stored array of handwritten notes in a bivariate time format; an interface for receiving a
handwritten query note in the bivariate time format; and a processor for calculating an
array of similarity scores, and outputting an array of similar handwritten notes, wherein
each similarity score in the array of similarity scores corresponds to a handwritten note in
Attorney’s Docket No.: MBHB Case No. 09-461
4
the stored array of handwritten notes, wherein each similarity score is calculated by
generating finite sequences based on pair hidden Markov models using a portion of the
corresponding handwritten note in the array and a portion of the query note, and
acquiring a highest probability value from a joint probability distribution of the finite
sequences, and wherein the array of similar handwritten notes comprises handwritten
notes with corresponding similarity scores that meet a criterion.
[0012] In one embodiment, the apparatus further comprises wherein the highest
probability value from the joint probability distribution of the finite sequences is acquired
using a Viterbi algorithm.
[0013] The foregoing summary is illustrative only and is not intended to be in any way
limiting. In addition to the illustrative aspects, embodiments, and features described
above, further aspects, embodiments, and features will become apparent by reference to
the drawings and the following detailed description.
BRIEF DESCRIPTION OF THE FIGURES
[0014] The embodiments will be further elucidated by means of the following description
and the appended drawings.
[0015] Figure 1 is a block diagram of a device for searching handwritten notes.
[0016] Figure 2 is a flow diagram showing steps for handwritten notes searching that
may be executed by the processor in Figure 1.
[0017] Figure 3a is an example of PFD and PDTW calculations based on a first possible
alignment between a curve P and a subcurve of curve Q.
[0018] Figure 3b is an example of PFD and PDTW calculations based on a second
possible alignment between a curve P and a subcurve of curve Q.
[0019] Figure 3c is an example of PFD and PDTW calculations based on a third possible
alignment between a curve P and a subcurve of curve Q.
[0020] Figure 3d is an example of PFD and PDTW calculations based on a fourth
possible alignment between a curve P and a subcurve of curve Q.
Attorney’s Docket No.: MBHB Case No. 09-461
5
[0021] Figure 4a is an example of shift-affected PFD and PDTW calculations based on a
first possible alignment between a curve P and a subcurve of curve Q.
[0022] Figure 4b is an example of shift-affected PFD and PDTW calculations based on a
second possible alignment between a curve P and a subcurve of curve Q.
[0023] Figure 5a is an example of a possible displacement shifted version of the curve P,
denoted P’.
[0024] Figure 5b is an example of shift-invariant PFD and PDTW calculations based on a
possible alignment between a curve P and a subcurve of curve Q, denoted as P”.
[0025] Figure 6a is an example of alternative shift-invariant PFD and PDTW calculations
based on a first possible alignment between a curve P and a subcurve of curve Q.
[0026] Figure 6b is an example of alternative shift-invariant PFD and PDTW calculations
based on a first possible alignment between a curve P and a subcurve of curve Q.
[0027] Figure 7 is a pair hidden Markov model for providing a joint probability
distribution over alignments between a pair of finite length polygonal curves P and Q.
[0028] Figure 8 is a block diagram illustrating an example computing device arranged for
handwritten notes searches.
DETAILED DESCRIPTION
[0029] In the following detailed description, reference is made to the accompanying
drawings, which form a part hereof. In the drawings, similar symbols typically identify
similar components, unless context dictates otherwise. The illustrative embodiments
described in the detailed description, drawings, and claims are not meant to be limiting.
Other embodiments may be utilized, and other changes may be made, without departing
from the spirit or scope of the subject matter presented here. It will be readily understood
that the aspects of the present disclosure, as generally described herein, and illustrated in
the Figures, can be arranged, substituted, combined, and designed in a wide variety of
different configurations, all of which are explicitly contemplated and make part of this
disclosure.
[0030] The present application is directed to a system and method for searching
Attorney’s Docket No.: MBHB Case No. 09-461
6
handwritten notes, with the capability of searching for notes written in any language,
drawings, and other free-form symbols. Accordingly, the term handwritten note(s) in the
following description may refer to any written language, drawings or various free-form
symbols.
[0031] Figure 1 is a block diagram of a device 100 for searching handwritten notes,
including a processor 102, a query note 104, a set of stored handwritten notes 106, and a
set of matching handwritten notes 108. The set of stored handwritten notes 106 is an
array of handwritten notes inputted by a user previously. The query note 104 is
handwritten by the user when the user wishes to search for handwritten notes similar to
the query note 104 among the set of stored handwritten notes 106. The processor 102
receives the query note 104 from the user, searches among the set of stored handwritten
notes 105, and outputs the set of matching handwritten notes 108, which is an array that
contains handwritten notes from the set of stored handwritten notes 106 considered
similar to the query note 104, based on algorithms executed by the processor 102.
[0032] In an embodiment of the present application, the notes in the set of stored
handwritten notes 106 are stored in a bivariate time format. Similarly, the query note 104
is also received in a bivariate time format. Algorithms executed by the processor 102
may accordingly determine whether the query note 104 and a handwritten note from the
set of stored handwritten notes 106 are similar using the bivariate time information of the
notes as inputs.
[0033] Data in bivariate time format may include two variables and a time value. The
two variables can be standard x and y Cartesian coordinates, or magnitude and angle
values. The time value can alternatively be any set of values that define the order or
sequence of the two variables.
[0034] Figure 2 is a flow diagram 200 showing the steps of a handwritten notes searching
device, including a Receive Handwritten Query Note step 202, a Preprocess Handwritten
Notes step 204, a Calculate Similarity Score Step 206, a Compare Similarity Score step
Attorney’s Docket No.: MBHB Case No. 09-461
7
208, and an Output Similar Handwritten Notes step 210.
[0035] The Receive Handwritten Query Note step 202 is analogous to the processor 102
receiving the query note 104 as shown in the block diagram of Figure 1, involving the
device receiving a handwritten note that the user wishes to search for. The handwritten
query note can be received from the user drawing on a pad using a stylus, wherein the
pad can be a generic touch pad or a touch screen interface. The handwritten query note
can also be received through various computer pointing devices. In an embodiment of
the present application, the handwritten query note itself is received in a bivariate time
format.
[0036] The Preprocess Handwritten Notes step 204 involves the segmenting and/or
parsing of handwritten notes which are to be searched to match the query note. Because
the handwritten notes may have been received as a series of symbols (sentences),
segmenting the handwritten notes to be searched into individual segments (words) allows
searching of the individual segments.
[0037] To segment the series of symbols, an algorithm can be employed to identify
indices of the bivariate time series where the split distance is greater than a particular
threshold. The split distance ds, of a time series at an index i, is defined as:
j i
j
j i
s j d x x
> ≤
= min( )− max( )
where xj is the x-coordinate corresponding to index j of the time series.
[0038] The Preprocess Handwritten Notes step 204 may also involve normalizing the
coordinates and rescaling of the handwritten notes. Normalizing the coordinates may be
necessary due to variations in starting positions between handwritten notes and the query
note, as well as among the handwritten notes. This may be achieved by defining a
starting coordinate and a handwritten note baseline based on the average coordinate
values of a handwritten note. Similarly, rescaling of the handwritten notes may be
necessary due to variations in sizes in the handwritten notes. This may be achieved by
Attorney’s Docket No.: MBHB Case No. 09-461
8
rescaling all handwritten notes to a constant height. These preprocessing steps as well as
other operations may be utilized to improve handwritten note searching.
[0039] The Calculate Similarity Score step 206 involves providing a quantitative
comparison between the query note and each of the preprocessed handwritten notes. In
an embodiment of the present application, similarity scores can be calculated based on
the bivariate time series information of the query note and the handwritten notes. There
are a number of ways for calculating similarity scores. A few examples of these
methods, as well as examples of similarity score calculations and related quantitative
comparisons are further herein below with respect to Figures 3-7.
[0040] The Compare Similarity Score step 208 compares the respective similarity scores
between the query note and each of the preprocessed handwritten notes against a criterion
to determine which of the preprocessed handwritten notes may be what the user is
looking for. How the criterion is set may depend on how the similarity scores are
calculated. For example, if the similarity score is calculated based on how similar two
curves are, then the criterion may be set as a minimum similarity value such that only the
preprocessed handwritten notes with a similarity score above a certain value is added to
an output array. For example, if the similarity score is based on a similarity percentage,
then an example criterion may be that only the preprocessed handwritten notes with
similarity score above 80% are added to the output array.
[0041] On the other hand, if the similarity score is calculated based on how different two
curves are, then the criterion may be set as a maximum similarity value such that only the
preprocessed handwritten notes with a similarity score below a certain value is added to
the output array. For example, if the similarity score is based on a scalar difference
between two polygonal curves, then an example criterion may be that only the
preprocessed handwritten notes with similarity score below 15 units are added to the
output array.
[0042] The criterion may also be set as threshold based on a similarity ranking. In this
Attorney’s Docket No.: MBHB Case No. 09-461
9
case, the preprocessed handwritten notes may be ranked according to their similarity
scores and only the preprocessed handwritten notes with similarity scores within a certain
ranking are added to the output array. For example, an example criterion may be that
only the top 50 most similar preprocessed handwritten notes are added to the output array
regardless of their similarity scores.
[0043] Further, a criterion based on the combination of similarity score as well as ranking
may be implemented, such that only the handwritten notes within a certain ranking that
also have similarity scores above or below a certain value are added to the output array.
For example, the top 50 most similar preprocessed handwritten notes are added to the
output array if their similarity score is also below 15 units.
[0044] The Output Similar Handwritten Notes step 210 outputs the handwritten notes
that have been determined to be similar to the query word based on the criterion. The
similar handwritten notes may be presented to the user either as they are found in the
form of an instantly updated display of the updated array as new similar notes are found,
or as a complete array once all the hand written notes have been searched and have been
compared against a criterion.
[0045] As mentioned earlier, there are a number of ways for calculating similarity scores.
Two methods for calculating the similarity scores are presented below – the Fréchet
distance method, and the pair hidden Markov model (PHMM).
[0046] The Fréchet distance between two curves is the longest distance between a point
from one curve and a point on the other curve with the same corresponding time value.
Given that D1, D2, D3,…, Dm denote the Euclidean distances between the corresponding
points of two curves each having m points, the Fréchet distance can be represented by
max(D1, D2, D3,…, Dm). For the application of handwritten notes searching, a partial
Fréchet distance (PFD) calculation focusing on the matching of a curve to a subcurve
may be implemented. The following examples of partial Fréchet distance calculations
are compared against calculations based on partial dynamic time warping (PDTW), a
Attorney’s Docket No.: MBHB Case No. 09-461
10
distance measure concept used for sequential pattern matching. The PDTW distance can
be represented as (D1
2 + D2
2 + D3
2 +… + Dm
2)1/2. Shift-invariant versions of PFD and
PDTW calculations are also presented.
[0047] Figures 3a-3d illustrates an example of finding the best alignment between a
curve Q and a curve P using both PFD and PDTW calculations. Curve P 302 includes
points p1, p2 and p3, while Curve Q 304 includes points q1, q2, q3, q4, q5 and q6. Dash
lines represent the curve P, solid lines represent the curve Q, and dotted lines represent
the distance values between a point in curve P and a corresponding point in curve Q
depending on the alignment. All possible monotonic alignments between the curve P and
subcurves of curve Q are considered. For each alignment, the distances PFD(Q, P) and
PDTW(Q,P) are calculated, and the subcurve of curve Q that results in the shortest
alignment distance is considered to be the closest alignment match to the curve P. The
shortest alignment distance can then be considered as a representative quantitative
comparison or similarity score between the curve Q and the curve P.
[0048] Figure 3a is an example of PFD and PDTW calculations based on a first possible
alignment between a curve P and a subcurve of curve Q. In this example, the curve P is
aligned to a subcurve of curve Q consisting of just the single point q1. The distances
between the points p1, p2, p3 in curve P and the point q1 in the subcurve of curve Q are
0.2, 2.136 and 1.5 respectively. Accordingly, PFD(Q, P) = max(0.2, 2.136, 1.5) = 2.136,
and PDTW(Q, P) = (0.22 + 2.1362 + 1.52) 1/2 = 2.6177.
[0049] Figure 3b is an example of PFD and PDTW calculations based on a second
possible alignment between a curve P and a subcurve of curve Q. In this example, the
curve P is aligned to a subcurve of curve Q consisting of the points q1 and q2, having
aligned matched pair of points (p1, q1), (p2, q1) and (p3, q2). Their respective distances
are 0.2, 2.136 and 2.062 respectively. Accordingly, PDF(Q,P) = max(0.2, 2.136, 2.062)
= 2.136, and PDTW(Q,P) = (0.22 + 2.1362 + 2.0622) 1/2 = 2.975.
[0050] Figure 3c is an example of PFD and PDTW calculations based on a third possible
Attorney’s Docket No.: MBHB Case No. 09-461
11
alignment between a curve P and a subcurve of curve Q. In this example, the curve P is
aligned to a subcurve of curve Q consisting of the points q1, q2 and q3, having aligned
matched pair of points (p1, q1), (p2, q2) and (p3, q3). Their respective distances are 0.2,
0.25 and 0.5 respectively. Accordingly, PDF(Q,P) = max(0.2, 0.25, 0.5) = 0.5, and
PDTW(Q,P) = (0.22 + 0.252 + 0.52) 1/2 = 0.5937.
[0051] Figure 3d is an example of PFD and PDTW calculations based on a fourth
possible alignment between a curve P and a subcurve of curve Q. In this example, the
curve P is aligned to a subcurve of curve Q consisting of the points q2, q3 and q4, having
aligned matched pair of points (p1, q2), (p2, q3) and (p3, q4). Their respective distances
are 2.059, 2.358 and 1.414 respectively. Accordingly, PDF(Q,P) = max(2.059, 2.358,
1.414) = 2.358, and PDTW(Q,P) = (2.0592 + 2.3582 + 1.4142) 1/2 = 3.435.
[0052] In addition to the alignments discussed in Figures 3a-d, the PFD and PDTW
calculations for all other possible monotonic alignments between P and subcurves of the
curve Q are performed and considered. The resulting shortest alignment distance, which
is to be considered as a representative quantitative comparison or similarity score
between the curve Q and the curve P is represented by min(2.136, 2.136, 0.5, 2.358, …) =
0.5 for PFD, and min(2.6177, 2.975, 0.5937, 3.435, …) = 0.5937 for PDTW. As such, it
has been shown that the alignment shown in Figure 3c of subcurve points q1, q2, and q3
provided the shortest alignment distances for both PFD and PDTW, and is therefore the
closest match to the curve P.
[0053] Figures 4a and 4b illustrate an example situation in which shifts and/or
translations of handwritten notes affect the results of the search, as mentioned briefly
above. As shown in Figure 4b, it can be seen that the subcurve of the curve Q that best
matches the curve P consist of the points q5, q6 and q7. However, both PFD and PDTW
calculations return that the subcurve of Q consisting of the points q1, q2, q3 and q4 is the
best match as illustrated in Figure 4a. To overcome a situation such as depicted in
Figures 4a-4b, PFD and PDTW calculations can be performed for all possible monotonic
alignments between all possible subcurves of the curve Q and all possible displacement
Attorney’s Docket No.: MBHB Case No. 09-461
12
shifted versions of the curve P. In other words, the curve P can be shifted horizontally
and/or vertically across an incremented range, and PDF and PDTW calculations are made
at each incremented shift. The minimum values from all the outputs of these calculations
can then be used as the representative quantitative comparison or similarity score
between the curve Q and the curve P.
[0054] In one embodiment, the increment for each shift is the horizontal or vertical
distance between a point and its successive point in the curve. For example, Figure 5a
shows a horizontal displacement shifted version of the curve P, denoted as P’. P’ is
shifted horizontally along the x-axis such that the point p1 has the same x-axis value as
the point q2, which is the successive point of q1 in the curve Q. In this case, the
increment for the shift is given as
xshift = xq2 – xq1 = xq2 – xp1.
Accordingly,
xp1’ = xp1 + xshift,
xp2’ = xp2 + xshift,…, and
xpm’ = xpm + xshift.
Since there is no vertical shift in this example, yp1’ = yp1. In the case that there is a
vertical shift along the y-axis, similar calculations can be done to generate different
monotonic alignments between the curves. In another embodiment, the increment for
each shift can be any constant or dynamically computed value appropriate for the
application and computing ability of the device.
[0055] Figure 5b shows a displacement shifted version of the curve P, denoted as P”. P”
is shifted along the x-axis such that the point p1” has the same x-axis value as the point
q5. Performing PFD and PDTW calculations for all possible monotonic alignments
between all possible subcurves of the curve Q and all possible displacement shifted
versions of the curve P returns the subcurve of the curve Q consisting of points q5, q6
and q7 to be the best match for the curve P.
[0056] Another shift-invariant solution to the issue of shifts and/or translations of
Attorney’s Docket No.: MBHB Case No. 09-461
13
handwritten notes is to use height and angle variables. The height variable y denotes the
height of each sample point of the curve and the angle variable θ denotes the
counterclockwise angle between the x-axis and the slope of the tangent to the curve at a
given sample point. Given a curve P = (p1, p2,…, pm) in the x-y coordinate system,
where pi = (xi, yi), the equivalent curve Py,θ = (p1’, p2’,…, p’m ) can be obtained using the
following computations:
y’i = yi – ymin
wherein ymin is the y-coordinate of the bottommost point of the curve P, and
θi = tan-1((yi+1 - yi)/(xi+1 - xi))
for i = 1, 2, …, m-1. Since there is no succeeding point pm+1 for the terminal point pm, θm
is defined to be 0. Accordingly, the PFDy,θ between the two curves P and Q is defined as
PFDy,θ(P, Q) = PFD(P’, Q’). In other words, instead of using the x-y coordinate system
values, the curves P and Q are converted to equivalent curves P’ and Q’ in the y-θ system
before PFD calculations between P’ and Q’. The y-θ variant of PDTW is analogously
defined as PDTWy,θ(P, Q) = PDTW(P’, Q’).
[0057] Figures 6a and 6b illustrate the distances between matched pair of points of the
curve P’ 306 and subcurves of the curve Q’ 308 corresponding to the curve P and
subcurves of the curve Q, respectively from Figures 3a to 3d. Figure 6a shows the
alignment between the curve P’ and the subcurve of the curve Q’ consisting of the points
q1’, q2’ and q3’, analogous to the curve P and subcurve of the curve Q in Figure 3c. In
this case, q1’ actually coincides with q3’. Figure 6b shows the alignment between the
curve P’ and the subcurve of the curve Q’ consisting of the points q4’, q5’ and q6’.
Based on calculations, the alignment with the subcurve of the curve Q consisting of the
points q1’, q2’ and q3’ gives the minimum alignment distance for both PFD y,θ and
PDTW y,θ calculations. Hence the subcurve of the curve Q’ consisting of the points q1’,
q2’ and q3’ is the closest match to P’. Since the subcurve of the curve Q’ with points q1’,
q2’ and q3’ is the y-θ system equivalent of subcurve of the curve Q with points q1, q2
and q3 as shown in Figure 3c, it has been shown that the results of the shift-invariant
PFDy,θ and PDTWy,θ calculations is consistent with the standard. PFD and PDTW
Attorney’s Docket No.: MBHB Case No. 09-461
14
calculations.
[0058] In addition to the PFD calculations presented in the present application and the
currently used PDTW calculations, the concept of pair hidden Markov models (PHMM)
can also be implemented for searching handwritten notes by providing joint probability
distributions over two polygonal curves. PHMM models a system of two sequences,
each with hidden states, and generates a conditional probability distribution of the hidden
states based on the visible states. In other words, a PHMM can determine the probability
that the curve P matches approximately with a particular subcurve of the curve Q via a
particular curve alignment. As such, using PHMM for partial searching of handwritten
notes has the advantage of being able to account for random variations in a user’s
handwriting and drawings.
[0059] Figure 7 shows a PHMM 700 that can provide a joint probability distribution over
alignments between a pair of finite length polygonal curves P and Q. The PHMM 700
comprises states S, M, I, E, P, P’, P” and Q, beginning in the state S, and ending in the
state E. The state M corresponds to when the bivariate time data points on both the curve
P and the curve Q are advancing along the curve. The state Q corresponds to when the
bivariate time data point on the curve Q is advancing, but the bivariate time data point on
the curve P is stationary. Analogously, the state P corresponds to when the bivariate time
data point on the curve P is advancing, but the bivariate time data point on the curve Q is
stationary. The states Q’ and Q” respectively generate the initial and terminating portions
of Q that are not aligned with P. The values α, β, η, μ and τ represent the transition
probabilities.
[0060] Given the probability distribution provided by the PHMM 700 shown in Figure 7,
the Viterbi algorithm can be used to derive the most probable alignment between the
curve Q and the curve P, based on an alignment score. To demonstrate this method, the
same curve Q and curve P from Figures 3a to 3d are transformed into the height y and
angle θ system, as previously shown in Figure 6a and 6b, respectively. Again, Figure 6a
corresponds to the alignment shown in Figure 3c, and Figure 6b shows the alignment
Attorney’s Docket No.: MBHB Case No. 09-461
15
between the curve P’ and the subcurve of the curve Q’ consisting of the points q4’, q5’
and q6’.
[0061] In the alignment shown in Figure 3c and represented in Figure 6a, curve P is
aligned to a subcurve of curve Q consisting of the points q1’, q2’ and q3’, having aligned
matched pair of points (p1’, q1’), (p2’, q2’) and (p3’, q3’). As such, the points q4’, q5’
and q6’ are unaligned. The corresponding sequence of state transitions, based on the
PHMM 700 is as follows: S → M → M → M → Q” → Q” → Q” → I → E. Defining
g(pi’, qj’) as the emissions probability of an alignment (pi’, qj’), the alignment score can
be given as:
(1-α) • g(p1’, q1’) • μ • g(p2’, q2’) • μ • g(p3’, q3’) • (1-3μ) • β • τ • τ • (1-τ),
which can simplified as:
(1-α) • μ2 • (1-3μ) • β • τ2 • (1- τ) • g(p1’, q1’) • g(p2’, q2’) • g(p3’, q3’).
In one embodiment, the emissions probability can be defined as:
g(pi’, qj’) = γ • e-γ • D(p
i
’, q
j
’)
where D(pi’, qj’) can be the Euclidean distance between the points pi’ and qj’.
Accordingly, the above equation becomes:
(1-α) • μ2 • (1-3μ) • β • τ2 • (1- τ) • γ3 • e-γ • (D(p
1
’, q
1
’) + D(p
2
’, q
2
’) + D(p
3
’, q
3
’)).
[0062] In the alignment represented in Figure 6b, curve P is aligned to a subcurve of
curve Q consisting of the points q4’, q5’ and q6’, having aligned matched pair of points
(p1’, q4’), (p2’, q4’) and (p3’, q6’). The corresponding sequence of state transitions,
based on the PHMM 700 is as follows: S → Q’ → Q’ → Q’ → M → M → M → I → E.
The alignment score is accordingly:
α • η • η • (1- η) • g(p1’,q4’) • μ • g(p2’, p5’) • μ • g(q3’, p6’) • (1-3μ) • (1-β)
= α • η2 • (1- η) • μ2 • (1-3μ) • (1-β) • γ3 • e-γ • (D(p
1
’, q
4
’) + D(p
2
’, q
5
’) + D(p
3
’, q
6
’))
[0063] The values for transition probabilities in a PHMM system, such as α, β, γ, η, τ and
μ of the PHMM 700 shown in Figure 7, can be chosen heuristically based on
experiments. Example values may be: α = β = η = τ = 0.5, μ=0.25, γ=1. Using these
Attorney’s Docket No.: MBHB Case No. 09-461
16
transition probabilities, the alignment score of the alignment represented in Figure 6a
becomes:
(0.5) • (0.0625) • (0.25) • (0.5) • (0.25) • (0.5) • e-(D(p
1
’, q
1
’) + D(p
2
’, q
2
’) + D(p
3
’, q
3
’))
= 0.00048828125 • e-(D(p
1
’, q
1
’) + D(p
2
’, q
2
’) + D(p
3
’, q
3
’))
Similarly, the alignment score of the alignment represented in Figure 6b becomes:
(0.5) • (0.25) • (0.5) • (0.0625) • (0.25) • (0.5) • e-(D(p
1
’, q
4
’) + D(p
2
’, q
5
’) + D(p
3
’, q
6
’))
= 0.00048828125 • e-(D(p
1
’, q
4
’) + D(p
2
’, q
5
’) + D(p
3
’, q
6
’)).
[0064] Further, by substituting the values of distances D(p1’, q1’), D(p2’, q2’) and
D(p3’, q3’), the alignment score of the alignment represented in Figure 6a becomes:
0.00048828125 e-(0.224 + 0.1 + 1)
= 0.00048828125 • 0.2661
= 0.0001299165
Similarly, by substituting the values of the distances D(p1’, q4’), D(p2’, q5’) and D(p3’,
q6’), the alignment score of the alignment represented in Figure 6a becomes:
0.00048828125 e-(1.36 + 1.118 + 0)
= 0.00048828125 • 0.08391
= 0.0000409721
Based on theses alignment scores, the alignment represented in Figure 6a appears to be a
better alignment than the alignment represented in Figure 6b. Calculations similar to
what has been show for the alignments represented in Figures 6a and 6b can be
performed for other alignments as well to find the best alignment between curve P and
the subcurve of the curve Q.
[0065] Analogous to the PFD and PDTW methods of finding the shortest distance of all
the possible alignments and using that particular distance as the representative quantitative
comparison of the query note and handwritten note, the probability associated with the
most probably alignment based on a PHMM model can be used as the representative
quantitative comparison and applied against a specific criterion.
[0066] Figure 8 is a block diagram illustrating an example computing device 800 that is
Attorney’s Docket No.: MBHB Case No. 09-461
17
arranged for searching handwritten notes. In a very basic configuration 801, computing
device 800 typically includes one or more processors 810 and system memory 820. A
memory bus 830 can be used for communicating between the processor 810 and the
system memory 820.
[0067] Depending on the desired configuration, processor 810 can be of any type
including but not limited to a microprocessor (μP), a microcontroller (μC), a digital signal
processor (DSP), or any combination thereof. Processor 810 can include one more levels
of caching, such as a level one cache 811 and a level two cache 812, a processor core 813,
and registers 814. The processor core 813 can include an arithmetic logic unit (ALU), a
floating point unit (FPU), a digital signal processing core (DSP Core), or any combination
thereof. A memory controller 815 can also be used with the processor 810, or in some
implementations the memory controller 815 can be an internal part of the processor 810.
[0068] Depending on the desired configuration, the system memory 820 can be of any
type including but not limited to volatile memory (such as RAM), non-volatile memory
(such as ROM, flash memory, etc.) or any combination thereof. System memory 820
typically includes an operating system 821, one or more applications 822, and program
data 824. Application 822 includes distance or probability calculation algorithm 823 that
is arranged to determine a quantitative comparison between a query note and a previously
handwritten note. Program Data 824 includes multipath routing data 825 that is useful for
calculating distances or probabilities, as will be further described below. In some example
embodiments, application 822 can be arranged to operate with program data 824 on an
operating system 821 such that previously handwritten notes can be searched according to
a user input query note. This described basic configuration is illustrated in Figure 8 by
those components within dashed line 801.
[0069] Computing device 800 can have additional features or functionality, and additional
interfaces to facilitate communications between the basic configuration 801 and any
required devices and interfaces. For example, a bus/interface controller 840 can be used to
facilitate communications between the basic configuration 801 and one or more data
Attorney’s Docket No.: MBHB Case No. 09-461
18
storage devices 850 via a storage interface bus 841. The data storage devices 850 can be
removable storage devices 851, non-removable storage devices 852, or a combination
thereof. Examples of removable storage and non-removable storage devices include
magnetic disk devices such as flexible disk drives and hard-disk drives (HDD), optical
disk drives such as compact disk (CD) drives or digital versatile disk (DVD) drives, solid
state drives (SSD), and tape drives to name a few. Example computer storage media can
include 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.
[0070] System memory 820, removable storage 851 and non-removable storage 852 are
all examples of computer storage media. Computer storage media includes, but is not
limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CDROM,
digital versatile disks (DVD) or other optical 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 be accessed by computing
device 800. Any such computer storage media can be part of device 800.
[0071] Computing device 800 can also include an interface bus 842 for facilitating
communication from various interface devices (e.g., output interfaces, peripheral
interfaces, and communication interfaces) to the basic configuration 801 via the
bus/interface controller 840. Example output interfaces 860 include a graphics processing
unit 861 and an audio processing unit 862, which can be configured to communicate to
various external devices such as a display or speakers via one or more A/V ports 863.
Example peripheral interfaces 860 include a serial interface controller 871 or a parallel
interface controller 872, which can be configured to communicate with external devices
such as input devices (e.g., keyboard, mouse, pen, voice input device, touch input device,
etc.) or other peripheral devices (e.g., printer, scanner, etc.) via one or more I/O ports 873.
An example communication interface 880 includes a network controller 881, which can be
arranged to facilitate communications with one or more other computing devices 890 over
a network communication via one or more communication ports 882. The
Attorney’s Docket No.: MBHB Case No. 09-461
19
Communication connection is one example of a communication media. Communication
media may typically be embodied by 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. A “modulated data
signal” can be 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 can include wired media such as a wired network or direct-wired
connection, and wireless media such as acoustic, radio frequency (RF), infrared (IR) and
other wireless media. The term computer readable media as used herein can include both
storage media and communication media.
[0072] Computing device 800 can be implemented as a portion of a small-form factor
portable (or mobile) electronic device such as a cell phone, a personal data assistant
(PDA), a personal media player device, a wireless web-watch device, a personal headset
device, an application specific device, or a hybrid device that include any of the above
functions. Computing device 800 can also be implemented as a personal computer
including both laptop computer and non-laptop computer configurations.
[0073] While various aspects and embodiments have been disclosed herein, other aspects
and embodiments will be apparent to those skilled in the art. The various aspects and
embodiments disclosed herein are for purposes of illustration and are not intended to be
limiting, with the true scope and spirit being indicated by the following claims.
[0074] The present disclosure is not to be limited in terms of the particular embodiments
described in this application, which are intended as illustrations of various aspects. Many
modifications and variations can be made without departing from its spirit and scope, as
will be apparent to those skilled in the art. Functionally equivalent methods and
apparatuses within the scope of the disclosure, in addition to those enumerated herein, will
be apparent to those skilled in the art from the foregoing descriptions. Such modifications
and variations are intended to fall within the scope of the appended claims. The present
disclosure is to be limited only by the terms of the appended claims, along with the full
Attorney’s Docket No.: MBHB Case No. 09-461
20
scope of equivalents to which such claims are entitled. It is to be understood that this
disclosure is not limited to particular methods, reagents, compounds compositions or
biological systems, which can, of course, vary. It is also to be understood that the
terminology used herein is for the purpose of describing particular embodiments only, and
is not intended to be limiting.
[0075] With respect to the use of substantially any plural and/or singular terms herein,
those having skill in the art can translate from the plural to the singular and/or from the
singular to the plural as is appropriate to the context and/or application. The various
singular/plural permutations may be expressly set forth herein for sake of clarity.
[0076] It will be understood by those within the art that, in general, terms used herein, and
especially in the appended claims (e.g., bodies of the appended claims) are generally
intended as “open” terms (e.g., the term “including” should be interpreted as “including
but not limited to,” the term “having” should be interpreted as “having at least,” the term
“includes” should be interpreted as “includes but is not limited to,” etc.). It will be further
understood by those within the art that if a specific number of an introduced claim
recitation is intended, such an intent will be explicitly recited in the claim, and in the
absence of such recitation no such intent is present. For example, as an aid to
understanding, the following appended claims may contain usage of the introductory
phrases "at least one" and "one or more" to introduce claim recitations. However, the use
of such phrases should not be construed to imply that the introduction of a claim recitation
by the indefinite articles "a" or "an" limits any particular claim containing such introduced
claim recitation to embodiments containing only one such recitation, even when the same
claim includes the introductory phrases "one or more" or "at least one" and indefinite
articles such as "a" or "an" (e.g., “a” and/or “an” should be interpreted to mean “at least
one” or “one or more”); the same holds true for the use of definite articles used to
introduce claim recitations. In addition, even if a specific number of an introduced claim
recitation is explicitly recited, those skilled in the art will recognize that such recitation
should be interpreted to mean at least the recited number (e.g., the bare recitation of "two
recitations," without other modifiers, means at least two recitations, or two or more
Attorney’s Docket No.: MBHB Case No. 09-461
21
recitations). Furthermore, in those instances where a convention analogous to “at least
one of A, B, and C, etc.” is used, in general such a construction is intended in the sense
one having skill in the art would understand the convention (e.g., “ a system having at
least one of A, B, and C” would include but not be limited to systems that have A alone, B
alone, C alone, A and B together, A and C together, B and C together, and/or A, B, and C
together, etc.). In those instances where a convention analogous to “at least one of A, B,
or C, etc.” is used, in general such a construction is intended in the sense one having skill
in the art would understand the convention (e.g., “ a system having at least one of A, B, or
C” would include but not be limited to systems that have A alone, B alone, C alone, A and
B together, A and C together, B and C together, and/or A, B, and C together, etc.). It will
be further understood by those within the art that virtually any disjunctive word and/or
phrase presenting two or more alternative terms, whether in the description, claims, or
drawings, should be understood to contemplate the possibilities of including one of the
terms, either of the terms, or both terms. For example, the phrase “A or B” will be
understood to include the possibilities of “A” or “B” or “A and B.”
[0077] In addition, where features or aspects of the disclosure are described in terms of
Markush groups, those skilled in the art will recognize that the disclosure is also thereby
described in terms of any individual member or subgroup of members of the Markush
group.
[0078] As will be understood by one skilled in the art, for any and all purposes, such as in
terms of providing a written description, all ranges disclosed herein also encompass any
and all possible subranges and combinations of subranges thereof. Any listed range can
be easily recognized as sufficiently describing and enabling the same range being broken
down into at least equal halves, thirds, quarters, fifths, tenths, etc. As a non-limiting
example, each range discussed herein can be readily broken down into a lower third,
middle third and upper third, etc. As will also be understood by one skilled in the art all
language such as “up to,” “at least,” “greater than,” “less than,” and the like include the
number recited and refer to ranges which can be subsequently broken down into subranges
as discussed above. Finally, as will be understood by one skilled in the art, a range
Attorney’s Docket No.: MBHB Case No. 09-461
22
includes each individual member. Thus, for example, a group having 1-3 cells refers to
groups having 1, 2, or 3 cells. Similarly, a group having 1-5 cells refers to groups having
1, 2, 3, 4, or 5 cells, and so forth.”
[0079] While various aspects and embodiments have been disclosed herein, other aspects
and embodiments will be apparent to those skilled in the art. The various aspects and
embodiments disclosed herein are for purposes of illustration and are not intended to be
limiting, with the true scope and spirit being indicated by the following claims.
Attorney’s Docket No.: MBHB Case No. 09-461
23
We claim:
1. A method for searching handwritten notes comprising:
storing a handwritten note in a bivariate time format;
receiving a handwritten query note in the bivariate time format;
generating finite sequences based on pair hidden Markov models using a
portion of the handwritten note and a portion of the handwritten query note;
providing a joint probability distribution based on the finite sequences;
calculating a similarity score based on the joint probability distribution; and
comparing the similarity score against a criterion.
2. The method of claim 1, wherein the similarity score is based on the highest
probability value in the joint probability distribution.
3. The method of claim 2, wherein a highest probability value in the joint probability
distribution is acquired using a Viterbi algorithm.
4. A method for searching handwritten notes comprising:
storing an array of handwritten notes in a bivariate time format;
receiving a handwritten query note in the bivariate time format;
calculating a similarity score for each handwritten note in the array of
handwritten notes by generating finite sequences based on pair hidden Markov
models using a portion of each handwritten note in the array and a portion of the
query note, and acquiring a highest probability value from a joint probability
distribution of the finite sequences;
comparing each similarity score against a criterion; and
generating an array of similar handwritten notes comprising handwritten notes
with corresponding similarity scores that meet the criteria.
5. The method of claim 4, wherein acquiring highest probability values from a joint
probability distribution of the finite sequences is achieved using a Viterbi
algorithm.
Attorney’s Docket No.: MBHB Case No. 09-461
24
6. The method of claim 4 further comprising segmenting the handwritten notes
based on a distance threshold.
7. The method of claim 4 further comprising rescaling the handwritten notes and the
handwritten query note to having matching heights before calculating a similarity
score.
8. The method of claim 4 wherein calculating a similarity score accounts for
variations in the start points and positions of the handwritten notes and the
handwritten query note.
9. An apparatus for searching handwritten notes comprising:
a stored array of handwritten notes in a bivariate time format;
an interface for receiving a handwritten query note in the bivariate time
format; and
a processor for calculating an array of similarity scores, and outputting an
array of similar handwritten notes, wherein each similarity score in the array of
similarity scores corresponds to a handwritten note in the stored array of
handwritten notes, wherein each similarity score is calculated by generating finite
sequences based on pair hidden Markov models using a portion of the
corresponding handwritten note in the array and a portion of the query note, and
acquiring a highest probability value from a joint probability distribution of the
finite sequences, and wherein the array of similar handwritten notes comprises
handwritten notes with corresponding similarity scores that meet a criterion.
Attorney’s Docket No.: MBHB Case No. 09-461
25
10. The apparatus of claim 9, wherein the highest probability value from the joint
probability distribution of the finite sequences is acquired using a Viterbi
algorithm.

Dated this 17th day of August, 2009,
Naveen. C
IN/PA 1419
Of K & S Partners
Agent for the Applicant