Gesture recognition for device unlocking

Systems and methods provide a security function for a device or applications running on a device. A lock tap sequence is entered by a user when the device is to be locked. When the user desires to unlock the device, the user enters a unlock tap sequence. If the lock tap sequence matches the unlock tap sequence, the device is unlocked.

FIELD

The disclosure relates generally to systems and methods for device security, and more particularly, to using gesture recognition to unlock a device.

BACKGROUND

Over time, smartphones have become more capable and their use has increased. With the increasing use of smartphones for everyday tasks also comes the increasing risk of losing sensitive data. One way to protect against such loss is the use of a lock screen to secure a smartphone. A lock screen can be built into the phone (i.e., a “default” lock screen) or it can be a separate application that may be obtained from third parties. While lock screens can provide some security, many users are not satisfied with currently available lock screens. They either provide too little security or require too much effort to be unlocked. Additionally, conventional lock screens that are based on gesture recognition typically suffer from the weakness that if the gesture data is collected from a wet surface or using greasy fingers, the lock screen becomes unusable.

DETAILED DESCRIPTION

In the following detailed description of example embodiments, reference is made to the accompanying drawings that form a part hereof, and in which is shown by way of illustration specific example embodiments in which the inventive subject matter may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the inventive subject matter, and it is to be understood that other embodiments may be utilized and that logical, mechanical, electrical and other changes may be made without departing from the scope of the inventive subject matter.

The description of the various embodiments is to be construed as examples only and does not describe every possible instance of the inventive subject matter. Numerous alternatives could be implemented, using combinations of current or future technologies, which would still fall within the scope of the claims. The following detailed description is, therefore, not to be taken in a limiting sense, and the scope of the inventive subject matter is defined only by the appended claims.

Described herein are systems and methods for using tap sequences to unlock a device. While the example features of the disclosure are discussed in the context of smart phones, the systems and methods of the disclosure can be adapted to other devices such as portable music players, tablet computers, or any other device with a touch input device such as a touchscreen interface. A device user may use a favorite song or melody as a tap sequence. It is typically very easy for the user to tap to the rhythm of that melody. For example, people often tap to the rhythm of a song when they hear the song or when they “sing it in their head”. In the embodiments described below, a user can tap on the touchscreen to unlock the device. As mentioned before, users are typically very consistent in keeping the rhythm, they can repeat the tap sequence easily. On the other hand, a stranger has difficulty repeating the sequence. A stranger will usually have no idea what song the user is thinking about. Even if the stranger could spot the sequence, which might be quite difficult, he would not be able to repeat it with the same precision as the user can be. As a result, a stranger can be denied access to the device.

FIG. 1is a block diagram of an operating environment100according to embodiments of the invention. In some embodiments, operating environment100includes a device102having a software environment104. Device102can be any type of device having a touchscreen120. For example device102can be a smartphone, a tablet computer, a media player (e.g., MP3 player) etc. In addition to display capabilities, touchscreen120receives touch input. The data associated with the touch input can include x and y coordinates, pressure and timestamp. In some aspects of the disclosure, x and y coordinates of the touch data are not used, because they are easily influenced by common situations like greasy or shaking hands. Users can typically repeat a gesture (e.g., a tap)—in terms of time and speed very well (even though the coordinates of the touch events may differ significantly). Thus, in some embodiments, the time information received from the touchscreen input is used for determining whether to unlock the device. Touchscreen120is one example of a touch input device. Other touch input devices now known or developed in the future may be used to receive touch input.

Software environment104comprises a set of software that operates on device102, and includes operating system106and lock screen application108. Operating system106controls execution of applications running on device102, manages the resources of device102, and provides interfaces between the applications running on device102and hardware components of device102(e.g., touchscreen120). In some embodiments, operating system106is the Android™ operating system. However, the embodiments are not limited to any particular operating system, and in alternative embodiments, the operating system106can be the iOS® operating system or a version of the Microsoft® Windows® family of operating systems.

Lock screen application108can be an application running on device102that provides a security function for device102. Lock screen application108can prevent access to applications and services provided on device102by unauthorized users. In some embodiments, lock screen application108includes a tap learning unit110and a tap recognition unit112. In order to unlock the device102, a user provides a sequence of taps on touchscreen120, where the sequence of taps has a rhythm that can be recognized by tap recognition unit112as matching a rhythm of a previously entered sequence of taps that was used to lock the device. As an example, a user may tap a rhythm that is based on a melody running in the user's mind.

In some embodiments, in order to lock device102, the user invokes the lock screen application108. Tap learning unit110receives tap sequence data from touchscreen120(e.g., via APIs or other touchscreen interfaces provided by operating system106). Data derived from the tap sequences may be stored as tap learning data114.

After entry of the tap sequences, lock screen application108can lock the screen and require a user to repeat the tap sequence via tap recognition unit112in order for the screen to be unlocked making device102available for use.

The domain of protection provided by lock screen application108may vary in different embodiments. In some embodiments, lock screen application108may protect all of the applications and services on device102from unauthorized use. In alternative embodiments, lock screen application108may protect a designated application or set of applications from unauthorized use.

Although described as an application, the functionality of lock screen application108may be integrated into operating system106or within another application. For example, the systems and methods described herein may be provided as part of an application, where, in order to use the application, the user must successfully enter a tap sequence that matches an earlier entered tap sequence.

FIG. 2is a flowchart200describing a method for unlocking a device according to embodiments. The method may, in some embodiments, constitute computer programs made up of computer-executable instructions. Describing the method by reference to a flowchart enables one skilled in the art to develop such programs including such instructions to carry out the method on suitable processors (the processor or processors of the computer executing the instructions from computer-readable media). The method illustrated inFIG. 2is inclusive of acts that may be taken by an operating environment100executing an example embodiment of the invention.

The operations begin at block202with learning a lock tap sequence. A user can provide a lock tap sequence on the touchscreen of a device, where the lock tap sequence corresponds to a rhythm. As noted above, the user may tap a rhythm for a melody that is running through the user's mind. In some embodiments, to reduce the chances of false positives or false negatives, tap learning unit110may request that the user repeat entry of the lock tap sequence multiple times. In some embodiments, the user can be asked to enter the same lock tap sequence ten times. When the requested number of lock tap sequences have been entered, the device can be locked.

Later, when a user desires to unlock the device, at block204a user interface is invoked that requests that the user enter an unlock tap sequence on the touchscreen of the device.

At block206, the unlock tap sequence entered at block204is compared with the lock tap sequence used to lock the device.

At decision block208, the system determines if the unlock tap sequence matches the lock tap sequence. If the unlock tap sequence matches the learned lock tap sequence, then at block210the device is unlocked. If the unlock tap sequence does not match the learned lock tap sequence, then the method returns to block204where the user may be given another opportunity to enter the correct tap sequence.

Tap sequences may be analyzed using any type of algorithm that is suitable for measuring similarity between temporal sequences. Some aspects of the disclosure involve utilize hidden Markov models for tap sequence learning and tap sequence evaluation. While hidden Markov models are used in some embodiments, other algorithms such as Dynamic Time Warping (DTW) may be used in alternative embodiments. An introduction into hidden Markov models and variations used in aspects of the disclosure will now be provided.

Hidden Markov Models

A Hidden Markov model (HMM) is a statistical model used for modeling Markov processes with hidden states. Compared to a Markov model, in which the state at a given time is known, in HMM measurements are observed that have a certain relation to the real states (that are hidden from the observer).

In the discussion below, a notation will be used that is provided in Lawrence R. Rabiner, “A tutorial on hidden markov models and selected applications in speech recognition,”Proceedings of the IEEE, Vol. 77, No. 2, February 1989, which is hereby incorporated by reference. Using this notation:S={s1, . . . , sN}—set of N hidden statesV={v1, . . . , vM}—set of M possible observationsQ=q1q2. . . qT—considered state sequenceO=o1o2. . . oT—observed sequencet=1, 2, . . . , T—time indexes associated with state and observation sequencesaijεAN×N−p(qt=sj|qt−1=si), transition probability from state sito sjbi(vj)εBN×M−p(ot=vj|qt=si), probability of observing symbol vj, given being in state si

πi—probability of being in state siat time t=1

In aspects of the disclosure, a hidden state and an observation are a duration between two consecutive touch events relative to the total length of the sequence (details of which are provided below with respect toFIG. 3). A melody in a user's head can be considered a sequence of hidden states and nobody except the user knows it. Touchscreen taps based on that melody can be considered observations.

When using hidden Markov models, three issues that can be resolved are:1. Determine appropriate state representation and the number of states.2. Given observed sequence O=o1o2. . . oTand a model defined by parameters λ=(A, B, π), determine the probability p(O|λ) of that sequence.3. Learn optimal set of parameters λ=(A, B, π),

While the state-related settings are typically problem-specific and usually subject to experiments, the other two issues −λ optimization and computing p(O|λ)—can be solved using Expectation-Maximization and Forward-Backward algorithms.

Consider an observation of a sequence O=o1o2. . . oTof length T and, given λ=(A, B, π), p(O|λ), the probability of observing that sequence is determined. A brute-force solution would be to compute it for all possible underlying state sequences Q (of length T) and then sum the results.

Consider a fixed sequence of states Q=q1q2. . . qTof length T. Then the probability of observing O given Q and λ is
p(O|Q,λ)=bq1(o1)·bq2(o2) . . .bqT(oT)  (equation 1)
Also, the probability of state sequence Q actually happening can be computed:
p(Q|λ)=πq1·aq1q2·aq2q3. . . aqT−1qT(equation 2)
The joint probability of O and Q (i.e., the probability that Q occurs and it is observed O) is the product of the equations (1) and (2). To compute the probability p(O|λ), a sum over all possible sequences Q can be performed, yielding the equation:
p(O|λ)=ΣQp(O|Q,λ)·p(Q|λ)  (equation 3)

This solution with time complexity 2T·NTmay be unfeasible in some environments, thus some embodiments use a more sophisticated method described below.

Forward Process

A variable can be defined:
αt(i)=p(o1o2. . . ot,qt=si|λ)  (equation 4)
that represents the probability of observing subsequence o1o2. . . oTand being in state siat time t. It can be computed recursively. First an initialization can be performed:
α1(i)=πi·bi(o1) 1≦i≦N(equation 5)

Then the following recursion can be repeated until α is computed for all times and states:
αt1(j)=[Σi=1Nαt(i)·aij]·bj(ot+1) 1≦j≦N(equation 6)

The state sjat time t+1 can be arrived through N possible states si, 1≦i≦N. Since αt(i) is the probability observing subsequence o1o2. . . otand being in state siat time t, then the product αt(i)aijis the probability of observing subsequence o1o2. . . otand being in state sjat time t+1, passing through state siat time t. When this product is summed over all possible states si, 1≦i≦N, the probability of being in state sjat time t+1 is obtained considering observations up until time t. Then, by simply multiplying it by observation probability bj(ot+1), the αt+1(j) can be determined.

Backward Process

The backward process is similar. A variable can be defined:
βt(i)=p(ot+1ot+2. . . oT|qt=si,λ)  (equation 7)
that represents the probability of observing subsequence ot+1ot+2. . . oTwhen it is known that state siexists at time t.

The following values can be set before starting the recursion (the probability of observing empty sequence is always 1):
βT(i)=1 1≦i≦N(equation 8)

Then the values of β are recursively computed for all times and states:
βt(i)=Σj=1N(aij−bj(ot+1)·βt+1(j) 1≦t≦T−1, 1≦i≦N)  (equation 9)

Obtaining the Observed Sequence Probability

After α and β are computed, they can be used to compute the probability p(O|λ). From the definitions above, it can be seen that
p(O|qt=si,λ)=αt(i)·βt(i)  (equation 10)
meaning that the probability of seeing the sequence o1o2. . . oTgiven state siat time t is the product of αt(i) and β=(i). The overall sequence probability can be obtained by summing that equation over all possible states si, 1≦i≦N for arbitrary time t.
p(O|λ)=Σi=1Nαt(i)·βt(i)  (equation 11)
Since the time t can be chosen, this can be used to further reduce the time complexity by half. Instead of running the whole Forward-Backward algorithm, the fact that βT(i)=1 for every i can be used. Therefore, if t=T is chosen, the backward process can be disregarded and the sequence probability can be computed by running only the forward part of the algorithm:
p(O|λ)=Σi=1NαT(i)  (equation 12)
The time complexity of Forward-Backward algorithm is TN2, which is better than the brute-force solution. Moreover, the variables α and β are acquired, which can be useful in an Expectation-Maximization algorithm.

The Expectation Maximization (EM) algorithm (known as the Baum-Welch algorithm when referring to HMMs) can be used for λ=(A, B, π) optimization. A training sequence O=o1o2 . . . oT is given, from which the best possible set of parameters λ, maximizing p(O|λ) can be inferred.

The algorithm includes two stages—E-stage (expectation) and M-stage (maximization). In the E-stage, auxiliary variables can be computed using the results of Forward-Backward algorithm. These auxiliary variables can then used in the M-stage for updating the set of parameters λ. This whole process is repeated until the local maxima is reached or some other stopping criterion fulfilled.

The EM algorithm only reaches local maxima. One way to deal with this issue is to perform k-fold crossvalidation with random initial values. Alternatively, estimating initial values based on performed experiments or some reasoning can be used in some embodiments to achieve better results (as described below with reference to block306ofFIG. 3).

Expectation Stage

Two auxiliary variables, state variable and joint variable, are now introduced that can be later used for updating λ.

State variable γt(i)=p(qt=si|O, λ) is the probability of being in state siat time t given observed sequence O. This can be computed using the results from the Forward-Backward algorithm.

Another variable introduced is joint variable ξt(i, j). This denotes the probability of being in state siat time t and in state sjat time t+1.
ξt(i,j)=p(qt=si,qt+1=sj|O,λ)  (equation 14)

This can be computed, again using α and β from the Forward-Backward algorithm.FIG. 8is a conceptual diagram illustrating joint variable ξt(i, j).

The probability of being in state siat time t, given observations o1o2. . . otis stored in αt(i). The probability of observing ot+1ot+2. . . oTgiven state sjat time t+1 is stored in βt+1(j). This can be added with the transition probability from state sito sj, aij, and the observation probability of the symbol ot+1 given state sj, bj(ot+1).

Maximization Stage

The auxiliary variables described above can be used to compute a newλfrom λ. The new sequence likelihood will be at least as high as the current sequence likelihood:
p(O|λ)≧p(O|λ)  (equation 16)

The update equations can be derived by solving optimization problem of maximizing p(O|λ) given following constraints:

∑j=1N⁢aij=1⁢⁢1≤i≤N(equation⁢⁢17)∑k=1M⁢bj⁡(k)=1⁢⁢1≤j≤N(equation⁢⁢18)∑i=1N⁢π⁢⁢i=1⁢⁢1≤i≤N(equation⁢⁢19)
That is, rows of A and B sum up to one and initial probabilities π sum up to one, so they actually represent valid probability distributions.

A technique that can be used for this optimization problem is known as Lagrange multipliers. Details of the derivation can be found at “Stephen Tu, Derivation of Baum-Welch Algorithm for Hidden Markov Models” available at the URL people.csail.mit.edu/stephentu/writeups/hmm-baum-welch-derivation.pdf which is hereby incorporated by reference herein for all purposes. The following update formulas are obtained:

a_ij=∑t=1T-1⁢ξ⁢⁢t⁡(i,j)∑t=1T-1⁢γ⁢⁢t⁡(i)(equation⁢⁢20)b_j⁡(vk)=∑t=1T⁢γ⁢⁢t⁡(j)·d⁡(ot,vk)∑t=1T-1⁢γ⁢⁢t⁡(j)(equation⁢⁢21)π_⁢⁢i=γ⁢⁢t⁡(i)(equation⁢⁢22)
where d is referred to as an indicator function defined as d(ot,vk)=1 iff ot=vkand d(ot,vk)=0 iff ofvk. These formulas work can also be derived by counting event occurrences:

Generally, the algorithm will converge at increasingly slower rate as it approaches the local maxima (as described below with reference to block308ofFIG. 3). Therefore, a stopping criterion can be used to break the iterations when an acceptable result is achieved. One example of such a stopping criterion is a condition that if two consecutive likelihoods p(O|λiter), p(O|λiter+1) differ by less than a chosen tolerance ε, the algorithm is terminated.

Additional Modifications

In some embodiments, the algorithms introduced above are modified to accommodate aspects of the operating environment.

First, the symbols observed above can be discrete values. However, in a touchscreen environment, continuous measurements are observed (e.g., a tap does not last 1 or 2 seconds, but rather 1.452 s). One possible implementation can be to round the measurements and optionally to increase the state count N. Further, in view of using the EM algorithm, model bj(vk) can be modeled as a Gaussian distribution rather than a N×M matrix and then optimize its parameters with the EM algorithm.

Second, the number of training sequences can be limited to only one. Having a single training sequence is undesirable, because it can cause overfitting. Therefore, in some embodiments, multiple training sequences are used for λ optimization.

Continuous Observation Probabilities

In the discussion above, bj(vk)=p(ot=vk|qt=sj) has been considered. Instead, vkcan be considered a continuous measurement rather than a discrete value. As a result, the observation probability can be redefined as following:
bj(vk)=N(vk,μj,σj2)  (equation 26)
where N( ) is the probability density function of the normal distribution and μj and σj2are the mean and variance related to state sj.

The learning process described above for the discrete version can be updated for continuous measurements. The updated formula for variable μ is given by:

μj=∑t=1T⁢γ⁢⁢t⁡(j)·ot∑t=1T-1⁢γ⁢⁢t⁡(j)⁢⁢1≤j≤N(equation⁢⁢27)
The mean μjfor state sjis thus a mean of observations weighted by their probabilities of being in state sjat time t.

A formula for updating σ2 is given by:

μj=∑t=1T⁢γ⁢⁢t⁡(j)·(ot-μ⁢⁢j)·(ot-μ⁢⁢j)′∑t=1T⁢γ⁢⁢t⁡(j)⁢⁢1≤j≤N(equation⁢⁢28)
This is very similar to standard formula for variance computation, however here the additions have different weights, again based on the probability γt(j).

Multiple Training Sequences

The discussion above has considered one training sequence. While that may be acceptable in some cases, to prevent overfitting, all the provided training sequences are used in some embodiments. Equations 24 and 25 can be used to explain the modifications.

As can be seen, the set of parameters λ is a result of counting the observation and transition frequencies. The algorithm can be modified to work with multiple sequences. The formal derivation of these equations can be found in “Xiaolin Li; M. Parizeau; Rejean Plamondon, “Training Hidden Markov Models with Multiple Observations—a Combinatorial Method,”IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 22, Issue 4, April 2000, which is hereby incorporated by reference herein for all purposes.

A set of K training sequences can be defined as O={O(1), O(2), . . . , O(K)}, where each sequence O(k)=O1(k)O2(k). . . OT(k)consists of T observations. Similarly, the superscripts can be used for γt(i)(k), ξt(i, j)(k)to refer to the variables computed over the particular sequence.

Then the transition probabilities become

a_ij=∑k=1K⁢∑t=1T-1⁢ξt⁡(i,j)(k)∑k=1K⁢∑t=1T-1⁢γ⁢⁢t⁡(i)(k)⁢⁢1≤i≤N,1≤j≤N(equation⁢⁢29)
and the initial probabilities π can be computed as:

π_i=∑k=1K⁢γ1⁡(i)(k)∑k=1K⁢∑j=1N⁢γ⁢⁢t⁡(i)(k)K⁢⁢1≤i≤N⁢(equation⁢⁢30)
These are basically the same equations as equations 23 and 25, only this time they are summed over all the training sequences O. The denominator in equation 30 is used to ensure thatπsums up to one.

Finally, the observation probability can be adjusted. Even though continuous observation probabilities are used, the update step includes summing over K training sequences:

FIG. 3is a flowchart300describing a method for learning a tap sequence. The method begins at block302by collecting a data sequence. In some embodiments, the data sequence can be a series of taps that represent a lock tap sequence. The series of taps can represent a melody that is chosen by a user. The user can tap a touchscreen in accordance with the melody. In some embodiments, the user can be asked to provide multiple sequences of taps for the same portion of the melody. For example, a user may be asked to provide ten sequences of taps for the same portion of the melody. Those of skill in the art having the benefit of the disclosure will appreciate that a user can be asked to provide more or fewer sequences, depending on the desired learning accuracy and tolerance for false negatives or false positives.

FIG. 4illustrates an example user interface400for receiving sequences of taps from a user. The user can be prompted to touch the touchscreen to start a new sequence. The user may tap the melody anywhere within area402of user interface400. As the user taps the touchscreen, data representing the taps is collected. A restart button404can be included that provides a means for a user to restart a particular sequence from the beginning A counter406can be included that shows how many sequences have been received so far.

Returning toFIG. 3, at block304, the data collected at block302is measured. For example, assume that at block302, a data sequence D=d1d2dT+1is collected where a new data point diis added whenever a touch event is registered (a finger is lifted up or touches the screen). In some embodiments, the value dtis the number of milliseconds that elapsed from the first touch event. Then value dtdoes not only depend on dt−1, but can also depend on all previous values d1. . . dt−1. That contradicts the Markov property, which says that the value dtonly depends on the previous value, dt−1. Therefore in such embodiments, the sequence D cannot be used as the observation sequence O. Thus in some embodiments, the first derivative of the acquired data sequence D is used. The derivative is defined as follows:
ot=dt+1−dt(equation 33)
which means that the durations between two consecutive touch events can be used. Sequence o1. . . oTcan then be used as the observation sequence O.

Then in some embodiments, the durations are normalized, so they sum up to 1. This means that the total length of the sequence does not matter, only the rhythm is considered. Then the measurement can be interpreted as a duration between two consecutive touch events relative to the length of the whole tap sequence.

FIG. 5includes graphs illustrating normalization of data used in embodiments. Graph500illustrates ten sequences prior to normalization. As can be seen in graph500, total lengths of the sequences representing the same melody can differ by up to 1 second. The difference in duration can have different causes. For example, in stressed situations, a user may tap the sequence faster than when the user is relaxed. However, the user can still keep the rhythm as illustrated in graph502. Graph502illustrates the data from graph500after the data has been normalized as described above.

Returning toFIG. 3, at block306, an HMM model is initialized. The hidden states, just like observations, represent the duration between two consecutive tap events relative to the total length of the sequence. State si, 1≦i≦N represents the duration of length i/N.

In some embodiments, N=30 states are used. Other embodiments can use a different number of states. The choice of the number of states to use involves a tradeoff between execution speed and the number of false negatives or false positives. A lower number of states can produce a lower number of false negatives, but also a higher number of false positives. Increasing the number of states can result in fewer false positives and false negatives, but with the algorithm's time complexity of TKN2, where T is the length of the tap sequence, K number of sequences used for learning and N number of states, it can be impractical to use too many states. It has been determined that in some embodiments, a value of N=30 states provides low error rate while maintaining reasonable execution speed.

Initial parameter estimates can also be determined for the HMM. As mentioned above, good initialization can provide better results for the EM algorithm. In some embodiments, observed sequences can be used to set up the transition matrix A, observation vectors μ and σ2and the initial probabilities π.

The transition matrix A can be initialized as an empty matrix of size N×N. Then the algorithm iterates through all pairs of observations in all sequences ot(k)ot+1(k)for 1≦t≦T−1 and 1≦k≦K. The closest state representations of these observations, si, sjrespectively, are found: si=round(N*ot(k)) and similarly for sj. The state transition from sito sjis then entered into the matrix A: Aij+=1.

Because these are estimates, some tolerance ε can be introduced. This tolerance says that the underlying state qt(k)of the observation ot(k)isn't necessarily qt(k)=si(the closest state). The underlying state qt(k)can rather be qt(k)=si, where i−ε≦1≦i+ε and ε is the chosen tolerance. In some embodiments, ε=3 when N=30 states are being used. A lower tolerance can mean that the learning would be too limited by the initial estimates, a higher tolerance can make the initial estimates unnecessary.

To implement this tolerance into the transition probabilities estimates, the matrix A can be smoothed by a Gaussian filter. The width of this filter is given by the chosen tolerance. Variance used for this filter is set as σ2=1. If the variance of the Gaussian filter is too high, the algorithm converges slowly, but if it is too low, the learning is limited by the initial estimates just like if the tolerance ε was too low. In MATLAB notation, the Gaussian filter can be created as flit=fspecial(‘gaussian’, 2*ε+1, 1).

iN
will most likely be observed. Therefore, μi=i for 1≦i≦N. Tolerance is then implemented into the observation probabilities using the observation variances (σ12, . . . , σN2).

Observation variances (σ12, . . . , σN2) can be initially set to a constant value just like the variance of the Gaussian filter. However, if (σ12, . . . , σN2) are set with respect to the given observations, it can lead to faster convergence of the algorithm.

Consider ρ=max(var(ot(k))). Then the initial observation variance can be set as the tεT kεK maximal variance among the observed sequences for all states:
σi2=ρ, 1≦i≦N.

Initial probabilities

πi=1N,1≤i≤N
can be set to a constant value. This initial setting typically has no effect on the results or convergence speed, the algorithm will adjust these accordingly after the first iteration.

At block308, HMM parameters can be optimized. After obtaining the initial estimates, the EM algorithm described above is iteratively executed to tune the parameters and to maximize p(O|λ).

Depending on the amount of time it takes for each iteration to complete, it can be desirable to limit the number of iterations in order to reduce the execution time, while still aiming for the best possible precision. In some embodiments, a stopping criterion is used. As long as the algorithm converges steeply, the algorithm is allowed to continue to run. If the convergence becomes too slow, the algorithm is terminated. Consider Pi=p(O|λi) in iteration i. In some embodiments, if Pi-4/Pi>0.1, the algorithm is terminated. That is, if the likelihood p(O|λ) has not improved at least ten times during the last four iterations, the convergence is considered to be too slow.

At block310, a threshold is selected. Because only sequences from the genuine user are available, and not from an unauthorized user, it can be useful to perform a cross-validation. In some embodiments, eight sequences are chosen at random and used for HMM training, and then the remaining two sequences are evaluated. This process is repeated ten times, resulting in twenty different likelihoods. The two lowest likelihoods are filtered out (presumed to be outliers), and the threshold is then selected as the value of the lowest remaining likelihood divided by ten. Those of skill in the art having the benefit of the disclosure will appreciate that other combinations of sequences can be used for cross-validation. Further alternative mechanisms for determining the threshold can be used.

FIG. 6is a flowchart600illustrating further details of a method for unlocking a device. At block602data for an unlock tap sequence is collected. The user can provide the unlock tap sequence in a user interface similar to that illustrated inFIG. 4. In some embodiments, the user interface does not include any indicators that would help an unauthorized user to spot the sequence.

At block604, the data representing the unlock tap sequence is measured. The data can be measured in the same manner as described above in block304(FIG. 3).

At block606, the likelihood of the unlock tap sequence is evaluated. In some embodiments, the likelihood is evaluated as described above under the heading of “Obtaining the Observed Sequence Probability.”

At block608, a check is made to determine if the likelihood of the unlock tap sequence is higher than the previously selected threshold. If so, then at block610the device is unlocked, otherwise the access to the device is denied. The method can return to block602to await entry of a new unlock tap sequence.

FIG. 7is a block diagram of an example embodiment of a computer system700upon which embodiments of the inventive subject matter can execute. The description ofFIG. 7is intended to provide a brief, general description of suitable computer hardware and a suitable computing environment in conjunction with which the invention may be implemented. In some embodiments, the inventive subject matter is described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types.

With reference toFIG. 7, an example embodiment extends to a machine in the example form of a computer system700within which instructions for causing the machine to perform any one or more of the methodologies discussed herein may be executed. In alternative example embodiments, the machine operates as a standalone device or may be connected (e.g., networked) to other machines. In a networked deployment, the machine may operate in the capacity of a server or a client machine in server-client network environment, or as a peer machine in a peer-to-peer (or distributed) network environment. Further, while only a single machine is illustrated, the term “machine” shall also be taken to include any collection of machines that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein.

The example computer system700may include a processor702(e.g., a central processing unit (CPU), a graphics processing unit (GPU) or both), a main memory704and a static memory706, which communicate with each other via a bus708. The computer system700may further include a touchscreen display unit710. In example embodiments, the computer system700also includes a network interface device720.

The persistent storage unit716includes a machine-readable medium722on which is stored one or more sets of instructions724and data structures (e.g., software instructions) embodying or used by any one or more of the methodologies or functions described herein. The instructions724may also reside, completely or at least partially, within the main memory704or within the processor702during execution thereof by the computer system700, the main memory704and the processor702also constituting machine-readable media.

While the machine-readable medium722is shown in an example embodiment to be a single medium, the term “machine-readable medium” may include a single medium or multiple media (e.g., a centralized or distributed database, or associated caches and servers) that store the one or more instructions. The term “machine-readable medium” shall also be taken to include any tangible medium that is capable of storing, encoding, or carrying instructions for execution by the machine and that cause the machine to perform any one or more of the methodologies of embodiments of the present invention, or that is capable of storing, encoding, or carrying data structures used by or associated with such instructions. The term “machine-readable storage medium” shall accordingly be taken to include, but not be limited to, solid-state memories and optical and magnetic media that can store information in a non-transitory manner, i.e., media that is able to store information. Specific examples of machine-readable storage media include non-volatile memory, including by way of example semiconductor memory devices (e.g., Erasable Programmable Read-Only Memory (EPROM), Electrically Erasable Programmable Read-Only Memory (EEPROM), and flash memory devices); magnetic disks such as internal hard disks and removable disks; magneto-optical disks; and CD-ROM and DVD-ROM disks. A machine-readable storage medium does not include signals.

The instructions724may further be transmitted or received over a communications network726using a signal transmission medium via the network interface device720and utilizing any one of a number of well-known transfer protocols (e.g., FTP, HTTP). Examples of communication networks include a local area network (LAN), a wide area network (WAN), the Internet, mobile telephone networks, Plain Old Telephone (POTS) networks, and wireless data networks (e.g., WiFi and WiMax networks). The term “machine-readable signal medium” shall be taken to include any transitory intangible medium that is capable of storing, encoding, or carrying instructions for execution by the machine, and includes digital or analog communications signals or other intangible medium to facilitate communication of such software.

The Abstract is provided to comply with 37 C.F.R. §1.72(b) to allow the reader to quickly ascertain the nature and gist of the technical disclosure. The Abstract is submitted with the understanding that it will not be used to limit the scope of the claims.