Nonparametric model for detection of spatially diverse temporal patterns

A computer-implemented method of generating a spatio-temporal pattern model for spatio-temporal pattern recognition includes receiving one or more training trajectories. Each of the training trajectories includes diverse data points that represent a spatio-temporal pattern. The received training trajectories define an area that is partitioned into one or more observed clusters, and a unpopulated complementary cluster. The spatio-temporal pattern model is generated so as to include both of the observed clusters and the unpopulated complementary cluster.

BACKGROUND

Technical Field

Certain aspects of the present disclosure generally relate to machine learning and, more particularly, to improving systems and methods of detecting spatially diverse temporal patterns.

Background

Mobile devices, such as cell phones or personal digital assistants (PDAs), have several functions, each of which may be activated through the user selection of a unique sequence of keys or using on-screen menus. As mobile devices offer increased feature sets, accessing all of the features may become increasingly complex given a limited number of controls capable of being provided on a mobile device.

Recently, some mobile devices have been designed to include the ability to receive user input through recognition of user-controlled gestures. Some devices may receive user-controlled gestures by way of a touch-screen interface, while other devices may be configured to receive user-controlled gestures by acquiring images and implementing a computer-vision approach to tracking user input. One important aspect of gesture recognition is the ability to recognize a known pattern in the resultant trajectory data. However, the appearance of or the method in which the input gesture is drawn or motioned often varies from user to user, or even varies each time it is drawn by the same user. For example, slight variations may exist in how different users draw a particular character (e.g., number “2”). Recognizing a pattern in the trajectory data remains a significant challenge due to these variations.

SUMMARY

In an aspect of the present disclosure, a computer-implemented method of generating a spatio-temporal pattern model for spatio-temporal pattern recognition is presented. The method includes receiving a plurality of training trajectories. Each of training trajectory including a plurality of diverse data points representative of a spatio-temporal pattern. The received training trajectories define an area. The method also includes partitioning the area into a plurality of observed clusters and a non-observed complementary cluster. The method further includes generating the spatio-temporal pattern model to include the observed clusters and the non-observed complementary cluster.

In another aspect of the present disclosure, an apparatus for generating a spatio-temporal pattern model for spatio-temporal pattern recognition is presented. The apparatus includes a memory and at least one processor coupled to the memory. The processor(s) is(are) configured to receive training trajectories. Each of the training trajectories includes diverse data points representative of a spatio-temporal pattern. The received training trajectories define an area. The processor(s) is(are) also configured to partition the area into observed clusters and a non-observed complementary cluster. The processor(s) is(are) further configured to generate the spatio-temporal pattern model to include the observed clusters and the non-observed complementary cluster.

In yet another aspect of the present disclosure, an apparatus for generating a spatio-temporal pattern model for spatio-temporal pattern recognition is presented. The apparatus includes means for receiving training trajectories. Each of the training trajectories includes diverse data points representative of a spatio-temporal pattern. The received training trajectories define an area. The apparatus also includes means for partitioning the area into observed clusters and a non-observed complementary cluster. The apparatus further includes means for generating the spatio-temporal pattern model to include the observed clusters and the non-observed complementary cluster.

In a further aspect of the present disclosure, a non-transitory computer readable medium is presented. The non-transitory computer readable medium has encoded thereon program code for generating a spatio-temporal pattern model for spatio-temporal pattern recognition. The program code is executed by a processor and includes program code to receive training trajectories. Each of the training trajectories includes diverse data points representative of a spatio-temporal pattern. The received training trajectories define an area. The program code also includes program code to partition the area into observed clusters and a non-observed complementary cluster. The program code further includes program code to generate the spatio-temporal pattern model to include the observed clusters and the non-observed complementary cluster.

DETAILED DESCRIPTION

Aspects of the present disclosure are directed to generating a model for spatio-temporal pattern recognition. That is, when detecting a temporal pattern within a continuously observed multi-dimensional variable, it is desirable to know where the variable deviates from the pattern under evaluation and how much it deviates. The temporal pattern may comprise an alphanumeric character, an object, speech, a gesture, stock market activity, meteorological patterns, and other temporal or spatio-temporal patterns. The variation amount may be considered before accepting or rejecting a temporal pattern. In other words, spatial diversity in temporal patterns may be significant enough to make an otherwise acceptable pattern rejected, or vice versa. Accordingly, aspects of the present disclosure provide for control over the amount of acceptable variation through the modeling process.

In accordance with aspects of the present disclosure, a nonparametric model may be used for detection of learned temporal manifolds with spatial diversity. In some aspects, the model may be based on a stochastic process such as a two-parameter Dirichlet process known as a Pitman-Yor process. For example, spatial diversity may be modeled by the Pitman-Yor process with a covariance regression process (e.g., a Gaussian process covariance regression) imposed on the second parameter. Hidden Markov models may be applied to model the temporal dynamics of the manifolds given the sequences of components of a mixture model. This allows evaluation of a given manifold and rejection of arbitrary sequences which is of significant importance in applications where patterns are to be discovered within continuous sequences of observation (e.g., temporal patterns within continuous hand movements).

Temporal manifolds are used in many applications including hand tracking, gesture recognition, and human action recognition. Conventional hidden Markov models (HMM) have been used in detecting temporal events in many applications including speech and gesture recognition. There have been different versions of HMM including the HMMs with discrete and continuous density emissions used in applications where observations occur with spatial diversity.

Spatial data play an important role for many applications, such as recognition of trajectories for flow detection and gesture recognition. Some conventional methods used for modelling spatial data include K-means and Gaussian mixture models (GMMs), in which data points are grouped together to define a set of clusters each representing a symbol in an alphabet. In a vocabulary of words (e.g., English words, spoken words, trajectories, or gestures), individual sequences of symbols from an alphabet may create meaningfully different words (manifolds, gestures, etc.)

One problem with detection of spatio-temporal patterns relates to the rejection of movements that are not similar to any member of a vocabulary of learned patterns. This is particularly important in speech and gesture recognition. For applications such as gesture and action recognition, a gesture/action is defined as a movement within a multidimensional space in which all parts of the movement should be completed in order to be considered as one of the learned models in the vocabulary. This means that, for example, if a trained pattern or movement appears as a circle in space, a curve that is partially similar to a circle (e.g., 60% of a circle) is not acceptable and is rejected. In detection of patterns within a continuous movement, this is particularly important because arbitrary movements happen frequently and many of them may be partially similar to some of the trained patterns.

Accordingly, aspects of the present disclosure provide a nonparametric model for localizing patterns and rejecting observations and movements of a trajectory that are not similar to any pattern in a vocabulary. The temporal dynamics of the patterns may be modeled with Hidden Markov Models and their spatial variations with a Dirichlet process mixture (DPM) model with Gaussian emissions. The mixture of Gaussians allows for an infinite set of observations suitable for spatially diverse patterns. The DPM may be used for clustering observations. Component labels of the mixture may in turn be used in the HMMs for modeling the temporal dynamics of each pattern.

Furthermore, configurations herein are used for detecting or rejecting a sequence. Therefore, a clear and strong separation gap between accept and reject regions is desirable. For example, it is desirable for the data from the acceptable region to produce a large likelihood that is significantly larger than the likelihood produced by the data from reject regions. For instance, if the likelihood for accept is −100 and larger and the likelihood for reject is −300 and smaller, then there is enough separation to avoid confusion. However, if the likelihood for accept is −100 and larger, and the likelihood for reject is −115 and smaller, the gap is small such that some acceptable inputs may cause the likelihood to be a little smaller than −115 and therefore be rejected.

Because a clear and strong separation gap is desirable, the model may be configured without the use of a continuous density emissions HMM (CDHMM). In a CDHMM, probabilities of emissions are presented by a mixture of probability density functions such as Gaussians and a vector of mixture coefficients. Therefore, an observation far from the center of a density will produce a small likelihood, which causes penalties in the HMMs likelihood. The CDHMM makes a smooth movement from the accept to the reject region causing the separation between the accept region and the reject region to be vague and unclear. Conversely, in accordance with aspects of the present disclosure, the gap between the accept region and the reject region may be enlarged by considering the observations from the complementary cluster that cause the HMMs to produce very small likelihoods. The sequences that do not have data points from the complementary cluster have larger likelihoods.

FIGS. 1A and 1Billustrate a front side and a back side, respectively, of a mobile platform100that is configured to receive user input via a front-facing camera110. The mobile platform100is illustrated as including a front-facing display102, speakers104, and a microphone106. The mobile platform100further includes a rear-facing camera108and front-facing camera110for capturing images of an environment. The mobile platform100may further include a sensor system that includes sensors such as a proximity sensor, an accelerometer, a gyroscope, proximity sensor, a touch sensor/screen or the like, which may be used to assist in determining the position and/or relative motion of the mobile platform100or the position of a touching finger on the screen.

As used herein, a mobile platform refers to any portable electronic device such as a cellular or other wireless communication device, personal communication system (PCS) device, personal navigation device (PND), personal information manager (PIM), personal digital assistant (PDA), or other suitable mobile device. The mobile platform may be configured to receive wireless communication and/or navigation signals, such as navigation positioning signals. The mobile platform may comprise devices which communicate with a personal navigation device (PND), such as by short-range wireless, infrared, wireline connection, or other connection, regardless of whether satellite signal reception, assistance data reception, and/or position-related processing occurs at the device or at the PND. In some aspects, the mobile platform may also comprise electronic devices, including wireless communication devices, computers, laptops, tablet computers, head-mounted devices, wearable computers, and the like, which are capable of optically or by touch tracking a user-guided object via a front-facing camera or a touch sensor for recognizing user input.

FIG. 2illustrates a top view of an exemplary mobile platform100receiving alphanumeric user input via a camera (e.g., see front-facing camera110ofFIG. 1A). The mobile platform100captures a sequence of images with its camera of a user-guided object. In this configuration, the user-guided object is a fingertip204of a user202. However, in other aspects the user-guided object may include a writing implement such as a user's entire finger, a stylus, a pen, a pencil, a brush, or other writing implements.

The mobile platform100captures the series or sequence of images and in response thereto, tracks the user-guided object (e.g., fingertip204) as the user202moves the fingertip204about the surface200. In one configuration, the surface200is a planar surface and is separate and external to the mobile platform100. For example, the surface200may be a table top or desk top. In another configuration, the user202may simply move the fingertip204in view of the mobile platform100but without contacting the surface (e.g., open space) for tracking by the mobile platform100. In this configuration, a sequence of inputs may, for instance, track movement of the user fingertip204about a surface of the display102. In yet another configuration, the surface200may be a touch screen, such as a touch sensitive display102, in which an input is indicated based on a contacts with a surface of the display. In this configuration, a sequence of inputs may, for example, track contacts of the user fingertip204along and/or with a surface of the display102.

The tracking data of the user-guided object by the mobile platform100may be analyzed by the mobile platform100in order to generate trajectory data. In one example, trajectory data is a set of temporally-ordered and spatially diverse data points. The mobile platform100may analyze all or a portion of the trajectory data in order to recognize various types of user input. For example, the trajectory data may indicate user input such as alphanumeric characters (e.g., letters, numbers, and symbols), gestures, and/or mouse/touch control input. In the example ofFIG. 2, the user202is shown completing one or more strokes of an alphanumeric character206(e.g., number “2”) by guiding the fingertip204across the surface200. By capturing a series of images or recording movement across the touch display102, as the user202draws the virtual number “2”, the mobile platform100can track the fingertip204and then analyze the trajectory data to recognize the character input.

FIG. 3illustrates an example implementation of the aforementioned generating a spatio-temporal pattern model for spatio-temporal pattern recognition using a system-on-a-chip (SOC)300, which may include a general-purpose processor (CPU) or multi-core general-purpose processors (CPUs)302in accordance with certain aspects of the present disclosure. Variables (e.g., neural signals and synaptic weights), system parameters associated with a computational device (e.g., neural network with weights), delays, frequency bin information, and task information may be stored in a memory block associated with a neural processing unit (NPU)308, in a memory block associated with a CPU302, in a memory block associated with a graphics processing unit (GPU)104, in a memory block associated with a digital signal processor (DSP)306, in a dedicated memory block318, or may be distributed across multiple blocks. Instructions executed at the general-purpose processor302may be loaded from a program memory associated with the CPU302or may be loaded from a dedicated memory block318.

The SOC300may also include additional processing blocks tailored to specific functions, such as a GPU304, a DSP306, a connectivity block310, which may include fourth generation long term evolution (4G LTE) connectivity, unlicensed Wi-Fi connectivity, USB connectivity, Bluetooth connectivity, and the like, and a multimedia processor312that may, for example, detect and recognize gestures. In one implementation, the NPU is implemented in the CPU, DSP, and/or GPU. The SOC300may also include a sensor processor314, image signal processors (ISPs), and/or navigation320, which may include a global positioning system.

The SOC300may be based on an ARM instruction set. In an aspect of the present disclosure, the instructions loaded into the general-purpose processor302may comprise code for receiving training trajectories. Each of the training trajectories includes diverse data points representative of a spatio-temporal pattern and the received training trajectories define an area. The instructions loaded into the general-purpose processor302may also comprise code for partitioning the area into observed clusters and a non-observed complementary cluster. Further, the instructions loaded into the general-purpose processor302may comprise code for generating the spatio-temporal pattern model to include the observed clusters and the non-observed complementary cluster.

FIG. 4illustrates an example implementation of a system400in accordance with certain aspects of the present disclosure. As illustrated inFIG. 4, the system400may have multiple local processing units402that may perform various operations of methods described herein. Each local processing unit402may comprise a local state memory404and a local parameter memory406that may store parameters of a machine learning model. In addition, the local processing unit402may have a local (e.g., neuron) model program (LMP) memory408for storing a local model program, a local learning program (LLP) memory410for storing a local learning program, and a local connection memory412. Furthermore, as illustrated inFIG. 4, each local processing unit402may interface with a configuration processor unit414for providing configurations for local memories of the local processing unit, and with a routing connection processing unit416that provides routing between the local processing units402.

FIG. 5is a diagram illustrating a partitioned spatial area502according to a Dirichlet process. As shown inFIG. 5, the spatial area502has been partitioned into eight regions A1-A8.

In accordance with aspects of the present disclosure, undesirable observations and sequences may be rejected. In some aspects, a Dirichlet process mixture model may be imposed on an infinite space of observations to define accept regions and reject regions. The Dirichlet process may be used to define partitions of the space of observations by θ and α to be a positive real number so that for any finite measurable partition A1, A2, . . . , AKon θ, A1∪A2∪ . . . ∪AK=θ, and G is a random probability measure over θ, (G(A1), G(A2), . . . , G(AK)˜Dirichlet(αH(A1), αH(A2), . . . , αH(AK)). According to this definition, the space of observations (e.g., spatial area) may be partitioned into a number or regions as shown, for example, inFIG. 5. If G is distributed according to a Dirichlet process (DP) (e.g., G˜DP(α, H), a draw from G is θiwhere θi|G˜G for i=1, 2, . . . , N and the posterior of the Dirichlet process is given by:

By marginalizing G, the prediction distribution is given by:

p⁡(θi+1=θ|θ1,θ2,…⁢,θi,α,H)=αα+N⁢h⁡(θ)+1α+N⁢∑k=1K⁢⁢Nk⁢δ⁡(θ,θk)(2)
where |Θ| is the current number of partitions, Nkis the number of observations at partition k, N is the total number of observations, δ(θ,θk) is a delta function (e.g., Kronecker delta function), and α is a parameter of the symmetric Dirichlet distribution.

According to Equation 2, a new observation will be assigned to any currently populated (non-empty) partitions or clusters k with probability

Nkα+N.
Alternatively, a new observation may be assigned to a new unpopulated (empty) partition with probability

αα+N.
Thus, if α is small compared to the number of observation at the current partitions, it will be more likely that a new observation is assigned to one of the current partitions (and not a new partition).

Applying a stochastic process (e.g., Pitman-Y or process), the prediction probability distribution may be given by:

In one exemplary aspect, spatially distributed data points may be modeled by Gaussian clusters. A stochastic process such as the Pitman-Y or process may be used to limit the range of the Gaussian clusters. A group of training data points for a word in a vocabulary may be clustered with a Gaussian mixture model. The Pitman-Y or process (PYP) may be used to cluster the space into a finite number of clusters or regions. As such, the space of observation may be partitioned into a limited number of regions or clusters with some clusters having training data points assigned thereto with the potential or capability to grow more clusters. Considering an infinite set of clusters with no assigned data points as a single cluster collectively, the Pitman Y or process may be used to cluster the space into the following set:

p⁡(θi+1=θ|θ_1,θ_2,…⁢,θ_1,α,H,d)=α+Θ_⁢dα+N⁢h⁡(θ)+1α+N⁢∑k=1K⁢⁢(Nk-d)⁢δ⁡(θ,θ_k)(4)
whereθks are the trained Gaussian partitions (e.g., regions or clusters).

FIG. 6is a diagram illustrating a partitioned spatial area602according to a stochastic process such as the Pitman-Y or process. Referring toFIG. 6, the spatial area602has been partitioned into four observed regions A1, A2, A3, and A4and one non-observed complementary region Acomplement. Although four observed regions are shown inFIG. 6, this is merely for ease of explanation and the present disclosure is not so limited. As indicated herein, any number of regions may be used to partition the space of observation. In one configuration, the complementary region Acomplementcollectively represents all unobserved partitions that can be initiated by the PYP of Equation 4.

The PYP of Equation 4 may be used to limit the range of each Gaussian cluster and evaluate creation of a new cluster when the data point i+1 is considerably unlikely to be generated by one of the trained components. The position of a new cluster initiated by the Pitman-Y or process can therefore be anywhere. In some aspects, the base distribution for the PYP of Equation 4 may be of a Gaussian family because the mixture model is Gaussian.

The mean and covariance of the Gaussians in the mixture model may both be unknown and sampled from conjugate priors. Because the covariance matrix is positive definite (transpose is positive for every non-zero column vector), its conjugate prior for the case that mean is fixed has an inverse-Wishart distribution Λ˜IW(v, Δ), which is a multidimensional analog of the inverse-Gamma-Normal conjugate prior for single-dimension Gaussian sampling. In some aspect, the multidimensional mean and the covariance matrix are uncertain. Therefore, a proper prior for this case is a Normal-inverse-Wishart distribution with density expressed as:

Accordingly, using the Pitman-Y or process and having determined proper distributions for the conjugate prior for the base normal distribution, the distribution may be sampled for inference. In one exemplary aspect, a Gibbs sampler process may be used for training and for inference from the PYP. The PYP likelihood models the emissions of hidden Markov models where the partition labels of each cluster is considered as the observations. The PYP likelihood for observing data points not belonging to any of the partitions with assigned data points allows for extending the observation into an infinite set of partitions without any observation, which may be referred to as a complement partition or region (e.g., Acomplement). Therefore, the observations unlikely from the occupied partitions may be given the label of the complement partition. The HMM is thus modified to accommodate these observations. Because there has been no instance of such observations in the clustering process and training of the HMMs in a vocabulary, the complement partition (e.g., Acomplement) is added to each HMM's table of observations with a very small probability collectively subtracted from other observations (this makes sure that the emission matrix remains stochastic). For example, if Bwis the matrix of emissions for the HMM of word w, the probability of an observation from the complement partition is then given by:
{circumflex over (b)}s,w(ok)=bs,w(ok)−ε;k=1, . . . ,Kw; 0<ε<<1bs,w(oKw+1)=|Kw|·ε  (6)
where {circumflex over (b)}s,w(ok) is the adjusted emission probability of observation Okat state s for the word w. Okw+1 represents all of the observations from the complement partition, and |Kw| denotes the number of occupied partitions in the mixture model for the word w. Although inter-word partition overlap is possible, the PYP of each word is inferred separately for a sequence of observations and therefore, the partitions of each word's PYP are the highest value representation of the observations for that word according to the training data. Therefore, the spatial variations of the data points at each partition are represented by the associated training data of that word.

In some aspects, the Dirichlet process may attract new members to already occupied or populated clusters or regions with probability

Nkα+N.
Therefore, when inferring regarding a new observation, it may be that the likelihood that a new partition is initiated and occupied with this observation may be very low. In other words, the Dirichlet process may tend to produce many large partitions. However, it is desirable to exclude a data point from the set of occupied partitions if it is more likely to be from the complement partition. Further, because the data may differ at various areas, it may be unreasonable to limit all the components of the mixture with the same limiting factor. Therefore, instead of limiting the mixture components equally, in some aspects, the second parameter of the Pitman-Y or process (e.g., parameter d) may be set according to data and allow the components covariance to control the range of each component.

Due to the spatial nature of the data points, a spatial model may be used to provide the second parameter of the PYP (e.g., parameter d). For this, a model for which the spatial variation of the data is modeled by nonparametric covariance regression may be employed. Considering the conditional distribution of a multidimensional Gaussian variable given a set of Gaussian variables with the same dimensionality, if x* is a d-dimensional variable and X represents a set of Gaussian variables, the mean and covariance of the conditional distribution p(x*|X) is given by:
μx*|X=μx*+Σx*XΣXX−1(x*−μX(7)
Σx*|X=Σx*x*−Σx*XTΣXX−1Σx*X(8)

To avoid the computational burden of a high-dimensional data regression, in some aspects, the mean and covariance of the data may be modelled by functions sampled from some prior distributions. Thus, a Gaussian model may be created for the data in a potentially infinite-dimensional Gaussian space (e.g., μ(x1), . . . , μ(xn)˜N ((m(x1), . . . , m(xn), K(x1, . . . , xn))), which is a Gaussian process (GP). Considering data to be stationary is reasonable because the patterns are independent of a location of observations. Therefore, a stationary covariance function such as the squared exponential may be used:

k⁡(x,x*)=τ2⁢e-x-x*2l2(9)
where τ is the magnitude and l is the smoothness of the covariance function. In some aspects, only the covariance of the conditional distribution for a given data point may be considered:
cov(x*|X)=K(x*,x*)−K(x*,X)T(K(X,X)+σ2I)−1K(x*,X)  (10)

In some configurations, there may not be any outputs associated with the data points considering the data to represent a Gaussian process. Therefore, in this case, the expectation of the GP for the data point x* has no meaning. However, the covariance regression may be dominated by the desire to invert the term (K(X,X)+σ2I). But, it can be computed rationally fast because the term is independent of the observation x* and can be stored. As such, the process of covariance regression may also be fast.

In some aspects, the hyper parameters (τ and l) of the covariance function of Equation 9 may be set such that the regression is useful for the Pitman-Y or process. Because there is no output for the data points, the marginal likelihood of the outputs cannot be maximized given the data X and the hyper parameters of the Gaussian process. Therefore, in some aspects, heuristics may also be used.

For example, to abide with the constraint 0≦d<1 for parameter d in Equation 3, the magnitude τ of the covariance function may be set to a value smaller than but close to 1 (e.g., τ=0.99). This may in fact not be enough to make sure the regressed covariance is smaller than 1 everywhere. Alternatively, in some aspects, the magnitude τ may be set to a smaller value. The regressed values may also be scaled down equally for all the data points.

On the other hand, the smoothness parameter l (also referred to herein as the length-scale) may be set to an appropriate value representing how smoothly the data changes.

The covariance regression function in Equation 10 can be interpreted as a conditional likelihood of a mixture of basis functions each centered at a data point from the given data set X. The variance of each basis function may then be controlled by the length-scale parameter l. In order to set l appropriately, such that the mixture of the basis functions do not over-fit or under-fit the data, in some aspects, the length-scale parameter l may be set to be equal to the average minimum distance between the observations multiplied by a coefficient as given, for example, by:
l=ηΔ,Δ=mean(Δ1, . . . , ΔN), for all Δn=min(|xi−xj|2), ∀i≠j(11)
where the coefficient η may be used to adjust (e.g., expand or reduce) the area of the clusters.

The regression process produces values between 0 and 1 (not including 1). For the points close to or in the given data set X, the regressed covariance is very small and for the points away from the items in the data set, it will be large.

FIGS. 7A-7Dillustrate examples of covariance regression for a trajectory with different values for η.FIG. 7Ais a diagram illustrating a set702of training trajectories (e.g.,704A-C) for the alphanumeric character “2,” presented upside down. The training trajectories may be normalized to provide a training pattern that may be used for recognition.FIG. 7Bis a plot illustrating a Gaussian process covariance of the training trajectories ofFIG. 7A.FIG. 7Cis a diagram illustrating another Gaussian process covariance of the training trajectories ofFIG. 7A, with an increased length-scale (e.g., l=0.0488) as compared to that used forFIG. 7B(e.g., l=0.0244).FIG. 7Dis a three-dimensional (3D) representation of the Gaussian process covariance ofFIG. 7C.

FromFIGS. 7B and 7Cshowing the result for the value of 1−cov(x*|X) for the given set X, it may be determined that the larger the η coefficient, the larger the1(becauseΔis positive) and the smoother the mixture blanket on the set X In fact the edges of the mixture blanket are also controlled by the hyper parameter l. Referring toFIG. 7B, at the beginning of trajectories of digit “2,” the model has two disjoint branches708and710with a gap in between. Additionally, inFIG. 7Ban empty area712between separate samples is shown. However, the Dirichlet process with the Gaussian base distribution may be used to anticipate and account for future variations. In some aspects, the second parameter (parameter d) may be set to the GP covariance of the samples multiplied by an adjustable coefficient. This may provide an excellent hint for the PYP to include and foresee variations while the range of each distribution is controlled. As indicated above, a small parameter d, in Equation 3 may result in a higher probability that a given data point is assigned to an already occupied component (e.g., region or cluster). Inversely, a higher d may cause the process to allow for a new component to be generated if the data point is unlikely enough to be generated by one of the occupied components. Therefore, the GP covariance at a given point x* may, in some aspects, be used as d for the Pitman-Yor process. As such, the process may assign a new component sampled from the base distribution h(θ) if x* is far enough away from the occupied components.

FIGS. 8A-8Cshow examples of the Pitman-Yor process applied to the trained model based on the trajectories ofFIG. 7A.FIG. 8Ais a diagram illustrating a partitioned spatial area according to a Pitman-Y or process applied to the trained model based on the trajectories ofFIG. 7Awith the parameter d set to zero. Referring toFIG. 8B, a Dirichlet process is applied to produce clustered space based on a set of training trajectories ofFIG. 7A. Clusters A1-A7are shown along with Acomplement.FIG. 8Cis a diagram illustrating a partitioned spatial area according to a Pitman-Yor process applied to the trained model based on the trajectories ofFIG. 7Awith the parameter d set based on a Gaussian process covariance (e.g., GP covariance with length-scale l=0.0244). As shown inFIG. 8B, the areas for regions A1-A7are relaxed such that the pattern is still detectable but may result in false positives.FIG. 8Cis a diagram illustrating a partitioned spatial area according to a Pitman-Yor process applied to the trained model based on the training trajectories ofFIG. 7Awith the parameter d multiplied with a coefficient greater than one (d>1.0). As shown inFIG. 8Athe areas defining the clusters of the pattern are very relaxed such that the digit2is no longer discernable.

FIG. 9is a graphical representation of a model of spatio-temporal pattern recognition. In the model ofFIG. 9, a Dirichlet Process mixture model (DPM) is shown with parameters α, d, and a base distribution H. The hidden Markov model receives the sequence of observations from the DPM which is the sequence of component labels extracted by the DPM.

In some aspects, the correctness of the recognized pattern may be verified. Verifying the correctness of a recognized pattern in a given sequence of data points includes verifying that all the areas of the pattern are met properly. To be verified most of the partitions in the trained model are met throughout the given trajectory. That is, a pattern is met if it has data points along the trajectory assigned by the PYP to the clusters of a given pattern. In some aspects, the HMM may further identify that the sequence of trajectories meeting the partitions is in the correct order.

Because PYP assigns the data points of a given sequence to the clusters, the number of data points assigned to each cluster may be clear. Furthermore, it is known exactly how many data points are given new clusters by PYP meaning they belong to the complement partition collectively representing the areas not covered by the trained clusters. Using a counting scheme for making sure that each partition receives a certain minimum number of allocated data points and the complement partition's allocated points are below a tolerable minimum, the number of partitions meeting these criteria is considered as a measure to whether the given sequence properly meet all areas of the trained model properly.

FIG. 10is a functional block diagram illustrating a mobile platform1000configured for recognizing temporal patterns. The mobile platform1000is one possible implementation of the mobile platform100ofFIGS. 1A and 1B. The mobile platform1000includes a camera1002as well as a user interface1006. The user interface1006includes a display1026, which may be configured for displaying preview images captured by the camera1002, as well as alphanumeric characters, as described above. The user interface1006may also include a keypad1028through which the user can input information to the mobile platform1000. If desired, the keypad1028may be obviated by utilizing a camera1002as described above. In addition, in order to provide the user with multiple ways to provide a spatio-temporal pattern, for example, in some aspects, the mobile platform1000may include a touch sensor to receive touch gesture input via the display1026. The user interface1006may also include a microphone1030and a speaker1032(e.g., if the mobile platform is a cellular telephone).

The mobile platform1000includes a tracking unit1018that is configured to perform object-guided tracking. In one example, the tracking unit1018is configured to track movement of an object (e.g., fingertip, stylus, writing instrument or other object), as discussed above in order to generate trajectory data.

The mobile platform1000also includes a control unit1004that is connected to and communicates with the camera1002and user interface1006, along with other features, such as the tracking unit1018and the gesture recognition unit1022. The gesture recognition unit1022accepts and processes trajectory data received from the tracking unit1018in order to recognize user input as symbols and/or gestures. The control unit1004may be provided by a processor1008and associated memory1014, hardware1010, software1016, and firmware1012.

The control unit1004may further include a graphics engine1024, which may be, e.g., a gaming engine, to render desired data in the display1026, if desired. The tracking unit1018and gesture recognition unit1022are illustrated separately and separate from the processor1008for clarity, but may be a single unit and/or implemented in the processor1008based on instructions in the software1016which is run in the processor1008. The processor1008, as well as one or more of the tracking unit1018, gesture recognition unit1022, and graphics engine1024can, but need not necessarily include, one or more microprocessors, embedded processors, controllers, application specific integrated circuits (ASICs), advanced digital signal processors (ADSPs), and the like. The term processor describes the functions implemented by the system rather than specific hardware. Moreover, as used herein the term “memory” refers to any type of computer storage medium, including long term, short term, or other memory associated with the mobile platform1000, and is not to be limited to any particular type of memory or number of memories, or type of media upon which memory is stored.

In one configuration, a machine learning model is configured for receiving training trajectories. The model is also configured for partitioning the area into observed clusters and a non-observed complementary cluster. The model is further configured for generating a spatio-temporal pattern model to include the observed clusters and the non-observed complementary cluster. The model includes a receiving means, partitioning means, and/or generating means. In one aspect, the receiving means, partitioning means, and/or generating means may be the general-purpose processor302, program memory associated with the general-purpose processor302, memory block318, local processing units402, and or the routing connection processing units316configured to perform the functions recited. In another configuration, the receiving means, partitioning means, and/or generating means may be implemented via processor1008, hardware1010, firmware1012, and/or software1016. In another configuration, the aforementioned means may be any module or any apparatus configured to perform the functions recited by the aforementioned means.

According to certain aspects of the present disclosure, each local processing unit402may be configured to determine parameters of the model based upon desired one or more functional features of the model, and develop the one or more functional features towards the desired functional features as the determined parameters are further adapted, tuned and updated.

FIG. 11illustrates a method1100for generating a spatio-temporal pattern model for spatio-temporal pattern recognition in accordance with aspects of the present disclosure. In block1102, the process receives training trajectories. Each of the training trajectories may include diverse data points representative of a spatio-temporal pattern. The spatio-temporal pattern may, for example, comprise a camera input or an input gesture representative of at least one of an alphanumeric character, a symbol, a mouse/touch control. The received training trajectories define an area.

In block1104, the process partitions the area into observed clusters and a non-observed complementary cluster. Furthermore, in block1106, the process generates the spatio-temporal pattern model to include the observed clusters and the non-observed complementary cluster.

The area may be partitioned by applying a stochastic process such as a two parameter Pitman-Y or process, for example. In some aspects, a covariance regression, such as a Gaussian process covariance regression may be performed for two or more of the data points included in the training trajectories and may in turn be used to determine the one or more stochastic process parameters.

The stochastic process may be used to determine which cluster, including the non-observed complementary cluster, corresponds to each data point of a given trajectory. A range of each of the observed clusters may also be determined based on one or more stochastic process parameters. Additionally, the spatio-temporal pattern model may, in some aspects, be generated by creating a hidden Markov model (HMM) based on the stochastic process.

Furthermore, the process may modify an observation table of the HMM to include the non-observed complementary cluster. In still further aspects, the process may recognize a received trajectory as a spatio-temporal match when a likelihood of the hidden Markov model is above a predetermined threshold.

FIG. 12is a flow diagram illustrating an exemplary process1200for generating a model for spatio-temporal pattern recognition, in accordance with aspects of the present disclosure. In block1202, the process receives training trajectories (e.g., training trajectories704A-C ofFIG. 7A). Each of the training trajectories includes a spatially diverse data point representative of an input gesture. In block1204, a Gaussian process (e.g.,FIG. 7C) is then applied to the training trajectories and in optional process block1206, the Gaussian process is used to determine a stochastic process parameter (e.g., parameter d of the Pitman-Y or process). As mentioned, process block1206is optional and may be omitted when training the model. Thus, in one example, the Gaussian process covariance regression is only used for recognition and not for training The stochastic process (e.g., Pitman-Y or process) is then applied in process block1208to partition a spatial area of the trajectories into observed regions and a non-observed complementary region. The range (e.g., size) of each of the observed regions may be based on the aforementioned stochastic process parameter. In block1210the process generates the model for spatio-temporal pattern recognition, which uses the observed regions and the non-observed complementary region to determine a pattern match.

FIG. 13is a flow diagram illustrating a process1300of spatio temporal pattern recognition. In block1302, the process receives a trajectory. The received trajectory may comprise data points. The data points of the trajectory may be related to an input gesture, stock market related data, speech, weather data or other spatio temporal data.

In block1304, the process evaluates the received trajectory to determine which cluster (e.g., the observed cluster and the complement cluster) of a trained spatio-temporal pattern model, the data points of the received trajectory fall within. When a data point falls within an observed cluster, the process assigns a label. When the data point is within the complement cluster, the data point may not be acceptable. However, in accordance with aspects of the present disclosure, some variance may be tolerated.

In block1306, the process finds the data points in each cluster and the complement cluster. Assigned labels for each cluster including the complement cluster may be supplied to a corresponding hidden Markov model to determine a likelihood. By considering the data points of the complement cluster, the likelihood produced by an HMM may be reduced.

Each HMM may output a likelihood value that may be compared to a threshold at block1308. If the outputs are above a threshold, the received trajectory may be recognized as a spatio temporal match in block1310. Otherwise, the received trajectory is not deemed a match, in block1312.

In some aspects, the order of observation may also be evaluated. That is, in some aspects, the HMM may be trained with the correct order of observation and may be used to evaluate the spatio-temporal pattern. For example, if an HMM is trained with a correct order for drawing the digit2, if a digit2is drawn in a reverse order, the likelihood generated by the HMM may be very small and thus, may indicate that the input is not a match.