CN107077609B - Non-parametric model for detecting spatially distinct temporal patterns - Google Patents

Abstract

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 different data points representing a spatio-temporal pattern. The received training trajectory defines an area that is divided into one or more observed clusters and a non-observed complementary cluster. A spatio-temporal pattern model is generated to include both observed clusters and non-observed complementary clusters.

Description

A nonparametric model for detecting spatially distinct temporal patterns

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims US Provisional Patent Application No. 62/, filed on November 6, 2014 and entitled "NONPARAMETRIC MODEL FOR DETECTIONOF SPATIALLY DIVERSE TEMPORAL PATTERNS" 076,319, the disclosures of which are expressly incorporated herein by reference in their entirety.

Background technique

technical field

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

background

Mobile devices, such as cellular telephones or personal digital assistants (PDAs), have several functions, each of which can be activated by a user selecting a unique key sequence or using an on-screen menu. Given the limited number of controls that can be provided on a mobile device, accessing all of the features can become increasingly complex as the mobile device provides an increased feature set.

More recently, some mobile devices have been designed to include the ability to receive user input by recognizing user-controlled gestures. Some devices may receive user-controlled gestures through a touch screen interface, while other devices may be configured to receive user-controlled gestures by acquiring images and implementing computer vision approaches to track user input. An important aspect of gesture recognition is the ability to recognize known patterns in the resulting trajectory data. However, the method or performance of gestures or gestures to make input gestures typically varies from user to user, or even for each gesture by the same user. For example, slight differences may exist in how different users gesture certain characters (eg, the number "2"). Because of these differences, identifying patterns in trajectory data remains a significant challenge.

Overview

In one aspect of the present disclosure, a computer-implemented method of generating a spatiotemporal pattern model for spatiotemporal pattern recognition is presented. The method includes receiving a plurality of training trajectories. Each of the training trajectories includes a number of distinct data points representing spatiotemporal patterns. The received training trajectory defines a region. The method also includes dividing the region into a plurality of observed clusters and a non-observed complementary cluster. The method further includes generating a spatiotemporal pattern model to include each observed cluster and the non-observed complementary cluster.

In another aspect of the present disclosure, an apparatus for generating a spatiotemporal pattern model for spatiotemporal pattern recognition is presented. The apparatus includes a memory and at least one processor coupled to the memory. The processor(s) are configured to receive training trajectories. Each of the training trajectories includes different data points representing spatiotemporal patterns. The received training trajectory defines a region. The processor(s) are further configured to divide the area into observed clusters and a non-observed complementary cluster. The processor(s) further includes generating a spatiotemporal pattern model to include each observed cluster and the non-observed complementary cluster.

In yet another aspect of the present disclosure, an apparatus for generating a spatiotemporal pattern model for spatiotemporal pattern recognition is presented. The apparatus includes means for receiving a training trajectory. Each of the training trajectories includes different data points representing spatiotemporal patterns. The received training trajectory defines a region. The apparatus also includes means for dividing the area into observed clusters and a non-observed complementary cluster. The apparatus further includes means for generating a spatiotemporal pattern model to include each observed cluster and the non-observed complementary cluster.

According to yet another 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 spatiotemporal pattern model for spatiotemporal pattern recognition. The program code is executed by the processor and includes program code for receiving training trajectories. Each of the training trajectories includes different data points representing spatiotemporal patterns. The received training trajectory defines a region. The program code also includes program code for dividing the region into observed clusters and a non-observed complementary cluster. The program code further includes program code for generating a spatiotemporal pattern model to include each observed cluster and the non-observed complementary cluster.

Additional features and advantages of the present disclosure will be described below. It should be appreciated by those skilled in the art that this disclosure may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of this disclosure. Those skilled in the art should also realize that such equivalent constructions do not depart from the teachings of the present disclosure as set forth in the appended claims. The novel features believed to be characteristic of the present disclosure, both in their organization and method of operation, together with further objects and advantages, will be better understood when the following description is considered in conjunction with the accompanying drawings. It is to be clearly understood, however, that each drawing is provided for illustrative and descriptive purposes only and is not intended as a definition of the limitations of the present disclosure.

Brief Description of Drawings

The features, nature and advantages of the present disclosure will become more apparent when the detailed description set forth below is read in conjunction with the accompanying drawings, in which like reference numerals have been designated accordingly.

1A and 1B illustrate the front and back of the mobile platform, respectively.

2 illustrates the mobile platform receiving alphanumeric user input.

3 illustrates an example implementation of designing a neural network using a system on a chip (SOC), including a general purpose processor, in accordance with certain aspects of the present disclosure.

4 illustrates an example implementation of a system in accordance with aspects of the present disclosure.

5 is a diagram illustrating a divided spatial region according to a Dirichlet process in accordance with aspects of the present disclosure.

6 is a diagram illustrating a divided spatial region according to a Pitman-Yor process in accordance with aspects of the present disclosure.

7A is a diagram illustrating a set of training trajectories for the alphanumeric character "2" presented upside down.

7B is a graph of the Gaussian process covariance of the training trajectory of FIG. 7A.

7C is a graph illustrating another Gaussian process covariance for the training trajectory of FIG. 7A with an increased length-scale compared to the length-scale used for FIG. 7B.

Figure 7D is a three-dimensional (3D) representation of the Gaussian process covariance of Figure 7C.

8A-C are diagrams illustrating divided spatial regions according to a Pitman-Yor process applied to the training trajectory of FIG. 7A in accordance with aspects of the present disclosure.

9 is a graphical illustration of a method for identifying spatiotemporal patterns.

10 is a functional block diagram illustrating a mobile platform capable of receiving user input via a front-facing camera.

11 is a flowchart illustrating a method for generating a spatiotemporal pattern model for spatiotemporal pattern recognition in accordance with aspects of the present disclosure.

12 is a flowchart illustrating a process for generating a spatiotemporal pattern model in accordance with aspects of the present disclosure.

13 is a flowchart illustrating a method for spatiotemporal pattern recognition in accordance with aspects of the present disclosure.

Detailed Description

The detailed description set forth below in connection with the appended drawings is intended as a description of various configurations, and is not intended to represent the only configurations in which the concepts described herein can be practiced. The detailed description includes specific details in order to provide a thorough understanding of various concepts. However, it will be apparent to those skilled in the art that these concepts may be practiced without these specific details. In some instances, well-known structures and components are shown in block diagram form in order to avoid obscuring such concepts.

Based on the present teachings, those skilled in the art should appreciate that the scope of the disclosure is intended to cover any aspect of the disclosure, whether implemented independently or in combination with any other aspect of the disclosure. For example, an apparatus may be implemented or a method of practice may be implemented using any number of the set forth aspects. In addition, the scope of the present disclosure is intended to cover such apparatus or methods that are practiced using other structure, functionality, or structure and functionality in addition to or other than the various aspects of the present disclosure set forth. It should be understood that any aspect of the disclosure disclosed may be embodied by one or more elements of a claim.

The word "exemplary" is used herein to mean "serving as an example, instance, or illustration." Any aspect described herein as "exemplary" is not necessarily to be construed as preferred or advantageous over other aspects.

Although certain aspects are described herein, numerous variations and permutations of these aspects fall within the scope of this disclosure. While some benefits and advantages of preferred aspects have been mentioned, the scope of the present disclosure is not intended to be limited to particular benefits, uses, or objectives. Rather, aspects of the present disclosure are intended to be broadly applicable to different technologies, system configurations, networks, and protocols, some of which are illustrated by way of example in the accompanying drawings and the following description of preferred aspects. The detailed description and drawings merely illustrate rather than limit the disclosure, the scope of which is defined by the appended claims and their equivalents.

Aspects of the present disclosure relate to generating models for spatiotemporal pattern recognition. That is, when a temporal pattern within a continuously observed multidimensional variable is detected, it is desirable to know whether and by how much the variable deviates from the evaluated pattern. Temporal patterns may include alphanumeric characters, objects, speech, gestures, stock market activity, weather patterns, and other temporal or spatiotemporal patterns. The amount of variance can be considered before accepting or rejecting a temporal pattern. In other words, spatial differences in temporal patterns may be significant enough that otherwise acceptable patterns are rejected, or vice versa. Accordingly, aspects of the present disclosure provide control over the amount of acceptable variance through the modeling process.

According to aspects of the present disclosure, non-parametric models may be used to detect 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 can be modeled by a Pitman-Yor process applying a covariance regression process (eg, Gaussian process covariance regression) on the second parameter. Given the sequence of components of the mixture model, a Hidden Markov Model can be applied to model the temporal dynamics of each manifold. This allows evaluating a given manifold and rejecting arbitrary sequences, which is important in applications where patterns are to be found within a continuous sequence of observations (eg, temporal patterns within a continuous hand movement).

Temporal manifolds are used in many applications, including hand tracking, gesture recognition, and human action recognition. Conventional Hidden Markov Models (HMMs) have been used to detect temporal events in many applications including speech and gesture recognition. Different versions of HMMs exist, including HMMs with discrete and continuous density emissions used in applications where observations occur in spatial diversity.

Spatial data plays an important role for many applications, such as the identification of trajectories for flow detection and gesture recognition. Some conventional methods for modeling spatial data include K-means and Gaussian Mixture Models (GMM), in which data points are grouped together to define a set of clusters, each cluster representing a symbol in the alphabet. In a vocabulary of words (eg, English words, spoken words, trajectories, or gestures), various sequences of symbols from the alphabet can create meaningfully distinct words (manifolds, gestures, etc.).

One problem with detecting spatiotemporal patterns involves rejecting movements that do not resemble any member of the vocabulary of the learned pattern. This is especially 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, where all parts of the movement should be completed to be considered one of the learned models in the vocabulary. This means for example that if the trained pattern or movement appears to be a circle in space, a partially circle-like curve (eg, 60% of a circle) is not acceptable and rejected. This is especially important when detecting patterns within continuous movements, since arbitrary movements occur frequently and many of them may be partially similar to some of the trained patterns.

Accordingly, aspects of the present disclosure provide non-parametric models for localizing patterns and rejecting observations and movements of trajectories that do not resemble any patterns in the vocabulary. The temporal dynamics of the modes can be modeled with a Hidden Markov Model and their spatial variation with a Dirichlet Process Mixture (DPM) model with Gaussian emission. Mixtures of Gaussians allow an infinite set of observations suitable for spatially different modes. DPM can be used to cluster observations. This mixed component label can in turn be used in the HMM for modeling the temporal dynamics of each mode.

Furthermore, the configuration herein is used to detect or reject a sequence. Therefore, a clear and strong separation gap between acceptance and rejection zones is desirable. For example, it is desirable that data from the acceptable zone yield a large likelihood that is significantly greater than that produced by the data from the rejection zone. For example, if the likelihood of acceptance is -100 and above and the likelihood of rejection is -300 and below, there is enough separation to avoid confusion. However, if the likelihood of acceptance is -100 and above and the likelihood of rejection is -115 and below, the gap is so small that some acceptable inputs may cause a likelihood slightly less than -115 and thus be rejected.

Since clear and strong separation gaps are desirable, this model can be configured without the use of continuous density emission HMMs (CDHMMs). In CDHMM, the probability of emission is represented by a mixture of a probability density function (such as a Gaussian) and a vector of mixing coefficients. Therefore, observations far from the density center will yield small likelihoods, which cause a loss in the likelihood of the HMM. The CDHMM makes a smooth movement from the acceptance to the rejection area, making the separation between the acceptance area and the rejection area ambiguous and unclear. Instead, according to aspects of the present disclosure, the gap between the acceptance and rejection regions can be magnified by considering observations from complementary clusters that make the HMM yield very small likelihoods. Sequences that do not have data points from complementary clusters have greater likelihood.

1A and 1B illustrate the front and back, respectively, of mobile platform 100 configured to receive user input via front-facing camera 110 . Mobile platform 100 is illustrated as including front-facing display 102 , speaker 104 , and microphone 106 . The mobile platform 100 further includes a rear-facing camera 108 and a front-facing camera 110 for capturing images of the environment. Mobile platform 100 may further include a sensor system including sensors such as proximity sensors, accelerometers, gyroscopes, proximity sensors, touch sensors/touchscreens, etc., which may be used to assist in determining the position and/or relative motion of mobile platform 100 or Touch where your finger is on the screen.

As used herein, mobile platform refers to any portable electronic device, such as 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 communications and/or navigation signals (such as navigation positioning signals). The mobile platform may include a device that communicates with a Personal Navigation Device (PND), such as via a short-range wireless, infrared, wired connection, or other connection, regardless of whether satellite signal reception, assistance data reception, and/or location-related processing occurs on the device or on PND. In some aspects, the mobile platform may also include electronic devices, including wireless communication devices, computers, laptops, tablets, head-mounted devices, wearable computers, and the like, that are capable of being optically captured via a front-facing camera or touch sensor. Or track user-guided objects by touch for recognizing user input.

2 illustrates a top view of an exemplary mobile platform 100 receiving alphanumeric user input via a camera (eg, see front-facing camera 110 of FIG. 1A). The mobile platform 100 uses its camera to capture a sequence of images of the object guided by the user. In this configuration, the object that the user guides is the fingertip 204 of the user 202 . However, in other aspects, the user-directed object may include a writing instrument, such as the user's entire finger, a stylus, a pen, a pencil, a brush, or other writing instrument.

Mobile platform 100 captures a series or sequence of images and, in response thereto, tracks the object (eg, fingertip 204 ) that the user guides as user 202 moves fingertip 204 around on surface 200 . In one configuration, surface 200 is a flat surface and is separate from and external to mobile platform 100 . For example, surface 200 may be a table top or countertop. In another configuration, the user 202 may simply move the fingertip 204 in the field of view of the mobile platform 100 without touching a surface (eg, an open space) to be tracked by the mobile platform 100 . In this configuration, the input sequence may, for example, track the movement of the user's fingertip 204 with respect to the surface of the display 102 . In yet another configuration, surface 200 may be a touch screen, such as touch-sensitive display 102, where input is indicated based on contact with the surface of the display. In this configuration, the input sequence may, for example, track the contact of the user's fingertip 204 along and/or with the surface of the display 102 .

The tracking data of the object guided by the user by the mobile platform 100 may be analyzed by the mobile platform 100 to generate trajectory data. In one example, the trajectory data is a collection of temporally ordered and spatially distinct data points. The mobile platform 100 may analyze all or part of the trajectory data to identify various types of user input. For example, the trajectory data may indicate user input such as alphanumeric characters (eg, letters, numbers, and symbols), gestures, and/or mouse/touch control input. In the example of FIG. 2 , user 202 is shown completing one or more strokes of an alphanumeric character 206 (eg, the number "2") by guiding fingertip 204 across surface 200 . By capturing a series of images or recording movement across the touch-sensitive display 102 as the user 202 draws the virtual number "2", the mobile platform 100 can track the fingertip 204 and then analyze the trajectory data to recognize the character input.

3 illustrates an example implementation of the aforementioned generation of spatiotemporal pattern models for spatiotemporal pattern recognition using a system-on-chip (SOC) 300, which may include a general-purpose processor (CPU) or a multi-core general-purpose processor ( CPU) 302. Variables (eg, neural signals and synaptic weights), system parameters associated with a computing device (eg, a neural network with weights), delays, frequency bin information, and task information can be stored in conjunction with the neural processing unit (NPU). ) 308, in the memory block associated with the CPU 302, in the memory block associated with the graphics processing unit (GPU) 104, in the memory block associated with the digital signal processor (DSP) 306, In dedicated memory block 318, or may be distributed across multiple blocks. Instructions executed at general-purpose processor 302 may be loaded from program memory associated with CPU 302 or may be loaded from special-purpose memory block 318 .

SOC 300 may also include additional processing blocks customized for specific functions (such as GPU 304, DSP 306, connectivity block 310 (which may include fourth generation long term evolution (4G LTE) connectivity, unlicensed Wi-Fi connectivity, USB connectivity, Bluetooth connectivity, etc.)) and, for example, a multimedia processor 312 that can detect and recognize gestures. In one implementation, the NPU is implemented in a CPU, DSP, and/or GPU. The SOC 300 may also include a sensor processor 314, an image signal processor (ISP), and/or a navigation 320 (which may include a global positioning system).

The SOC 300 may be based on the ARM instruction set. In one aspect of the present disclosure, the instructions loaded into general-purpose processor 302 may include code for receiving training trajectories. Each of the training trajectories includes different data points representing spatiotemporal patterns and the received training trajectories define a region. The instructions loaded into the general purpose processor 302 may also include code for dividing the region into observed clusters and a non-observed complementary cluster. Furthermore, the instructions loaded into the general purpose processor 302 may include code for generating a spatiotemporal pattern model to include each observed cluster and the non-observed complementary cluster.

4 illustrates an example implementation of a system 400 in accordance with certain aspects of the present disclosure. As illustrated in FIG. 4, system 400 may have multiple local processing units 402 that may perform various operations of the methods described herein. Each local processing unit 402 may include a local state memory 404 and a local parameter memory 406 that may store parameters of the machine learning model. Additionally, the local processing unit 402 may have a local (eg, neuron) model program (LMP) memory 408 for storing local model programs, a local learning program (LLP) memory 410 for storing local learning programs, and a local connection memory 412. Furthermore, as illustrated in FIG. 4 , each local processing unit 402 may interface with a configuration processor unit 414 for providing configuration for the local memories of that local processing unit, and to provide communication between the local processing units 402 The routing connection processing unit 416 of the routing is docked.

FIG. 5 is a diagram illustrating a divided spatial region 502 according to a Dirichlet process. As shown in FIG. 5, the spatial area 502 has been divided into eight areas A1-A8.

According to aspects of the present disclosure, undesirable observations and sequences may be rejected. In some aspects, a Dirichlet process mixture model can be applied over an infinite space of observations to define acceptance and rejection regions. The Dirichlet process can be used to define partitions of the observed space by θ and α as positive real numbers such that for any finitely measurable partition A ₁ ,A ₂ ,…,AK on θ, A _{1 ∪A 2} ∪ ... _∪AK = θ, and G is a random probability measure on θ (G(A ₁ ), G(A ₂ ), ..., G(A _K )) ~ Dirichlet(αH(A ₁ ), αH(A ₂ ),…,αH(A _K )). According to this definition, the observed space (eg, a region of space) can be divided into regions, such as shown in FIG. 5 . If G is distributed according to a Dirichlet process (DP) (eg, G∼DP(α,H), then the stroke from G is θ _i , where θ _i |G∼G, i=1,2,...,N, And the posterior of the Dirichlet process is given as:

By marginalizing G, the predicted distribution is given by:

where |Θ| is the current number of partitions, Nk is the number of observations at partition _k , N is the total number of observations, δ(θ, _θk ) is the increment function (eg, the Kronecker increment function), and α is symmetric Parameters of the Dirichlet distribution.

被指派给任何当前填充(非空)分区或集群k。另选地，新观察能以概率

被指派给新未填充(空)分区。因而，如果α与当前分区处的观察的数目相比很小，则更可能的是新观察被指派给当前分区之一(而非新分区)。According to Equation 2, the new observation will be

is assigned to any currently populated (non-empty) partition or cluster k. Alternatively, new observations can be probabilistically

is assigned to a new unpopulated (empty) partition. Thus, if a is small compared to the number of observations at the current partition, it is more likely that the new observation is assigned to one of the current partitions (rather than the new partition).

Applying a stochastic process (for example, a Pitman-Yor process), the predicted probability distribution can be given by:

where d is a parameter that controls the area of each zone or cluster.

In Equation 3, the parameter d may, for example, be defined such that 0≦d<1 and α>−d. In this example, the parameter d may control the number of regions or clusters with one or very few observations (trajectories). That is, the larger the value of d, the more regions or clusters with a smaller number of observations (trajectories). In addition, the larger d, the smaller the number of regions or clusters with a large number of observations, and the larger the number of observations (trajectories) per region.

In one exemplary aspect, spatially distributed data points may be modeled by Gaussian clusters. Stochastic processes such as the Pitman-Yor process can be used to limit the extent of Gaussian clusters. A cluster of training data points for a word in the vocabulary can be clustered with a Gaussian mixture model. The Pitman-Yor Process (PYP) can be used to group the space into a limited number of clusters or regions. In this way, the observed space can be divided into a limited number of regions or clusters, some of which have training data points assigned to it, with the potential or ability to grow more clusters. Considering an infinite set of clusters with no assigned data points collectively as a single cluster, the Pitman Yor process can be used to group the space into the following set:

是经训练高斯分区(例如，区或集群)。in

are trained Gaussian partitions (eg, regions or clusters).

6 is a diagram illustrating a divided spatial region 602 according to a stochastic process, such as a Pitman-Yor process. Referring to Figure 6, the spatial region 602 has been divided into _four observed regions A1, A2, A3 and A4 and _one non _- observed _{complementary region Acomplement .} Although four observed zones are shown in FIG. 6, this is for ease of explanation only and the present disclosure is not so limited. As shown herein, any number of zones may be used to divide the viewing space. In one configuration, the complement region A _complement generally represents all unobserved partitions that can be initiated by the PYP of Equation 4.

When data point i+1 is quite unlikely to be generated by one of the trained components, the PYP of Equation 4 can be used to limit the extent of each Gaussian cluster and evaluate the creation of new clusters. The location of the new cluster initiated by the Pitman-Yor process can thus be any location. In some aspects, the underlying distribution of Equation 4 may be of the Gaussian family because the mixture model is Gaussian.

Both the mean and covariance of the Gaussian in the mixture model can be unknown and sampled from a conjugate prior. Since the covariance matrix is positive definite (the transpose is positive for each non-zero column vector), its conjugate prior has the inverse Wishart distribution Λ~IW(v,Δ) for the fixed mean case, which is the multi-dimensional analog of the inverse gamma-normal conjugate prior of single-dimensional Gaussian sampling. In some aspects, the multidimensional mean and covariance matrices are indeterminate. Therefore, the correct prior for this situation is the normal inverse Wishart distribution, whose density is expressed as: Λ ~ W(v, Δ) and

自由度的Student-t分布来分布。因而，预测似然性随后可由均值为

且协方差为

的正态分布来近似地给出。where v represents the degrees of freedom and is generally chosen to be larger than the dimensionality of the data, Δ is the pseudo-covariance matrix with v as the size of its dataset, and k is the size of the pseudo-data set with a prior of expected mean v. The predicted likelihood of observation x ^* can be calculated according to having

Degree of freedom Student-t distribution to distribute. Thus, the predicted likelihood can then be calculated from the mean as

and the covariance is

to approximate the normal distribution of .

Accordingly, using the Pitman-Yor process and having a determined correct distribution for the conjugate prior of the underlying normal distribution, the distribution can be sampled for inference. In one exemplary aspect, the Gibbs sampler process may be used for training and for inference from PYP. The PYP likelihood models the emission of a hidden Markov model, where the partition labels of each cluster are considered observations. The PYP likelihood of an observation data point that does not belong to any partition with an assigned data point allows the observation to be extended to an infinite set of partitions without any observations, which may be referred to as complementary partitions or regions (eg, A _complement ) . Thus, observations that are unlikely to come from an occupied partition can be given the label of a supplementary partition. The HMM was thus modified to accommodate these observations. Since there are no instances of such observations during the clustering of the vocabulary and in the training of the HMM, complementary partitions (eg, _Acomplement ) are added to the observations of each HMM's table (this ensures that the emission matrix remains random). For example, if B _w is the emission matrix of the HMM for word w, then the probability of an observation from the supplementary partition is then given by:

是状态为s的观察O_k针对单词w的经调整发射概率。

表示来自补充分区的所有观察，且|K_w|表示对于单词w而言混合模型中被占据分区的数目。虽然单词间分区交叠是可能的，但对于观察序列分开地推断每一单词的PYP，并且因此每一单词的PYP的分区是根据训练数据针对该单词的观察的最高值表示。因此，每一分区处的数据点的空间变化由该单词的相关联的训练数据来表示。in

is the adjusted emission probability of the observation _Ok with state s for word w.

represents all observations from complementary partitions, and |Kw| represents the number of occupied partitions in the mixture model for word _w . While inter-word partition overlap is possible, the PYP for each word is inferred separately for a sequence of observations, and thus the partition of the PYP for each word is the highest value representation of the observations for that word from the training data. Thus, the spatial variation of data points at each partition is represented by the associated training data for that word.

将新成员吸引到已占据或填充的集群或区。因此，在关于新观察进行推断时，新分区被发起并被这一观察占据的似然性可能非常低。换言之，Dirichlet过程往往产生许多大分区。然而，从已占据分区集合排除数据点是合乎需要的，如果它更可能来自补充分区的话。此外，因为数据可在各区域处不同，使用相同的限制因子来限制混合的所有分量可能是不合理的。因此，代替等同地限制各混合分量，在一些方面，Pitman-Yor过程的第二参数(例如，参数d)可根据数据来被设置并允许分量协方差控制每一分量的范围。In some aspects, the Dirichlet process can be probabilistic

Attract new members to occupied or populated clusters or zones. Therefore, when inferring about a new observation, the likelihood that a new partition was initiated and occupied by this observation may be very low. In other words, the Dirichlet process tends 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 come from a supplementary partition. Furthermore, since the data may differ at regions, it may not be reasonable to limit all components of the mix using the same limit factor. Thus, instead of constraining each mixed component equally, in some aspects, a second parameter of the Pitman-Yor process (eg, parameter d) may be set according to the data and allow the component covariances to control the extent of each component.

Due to the spatial nature of the data points, a spatial model can be used to provide a second parameter of the PYP (eg, parameter d). To this end, a model in which the spatial variation of the data is modeled by nonparametric covariance regression can be employed. Consider the conditional distribution of multi-dimensional Gaussian variables, given a set of Gaussian variables with the same dimension, 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) are given by gives:

To avoid the computational burden of regression on high-dimensional data, in some aspects, the mean and covariance of the data can be modeled by functions sampled from some prior distribution. Thus, a Gaussian model can be created for the data in a potentially infinite dimensional Gaussian space (eg, μ(x ₁ ),...,μ(x _n )～N((m(x ₁ ),...,m(x _n ),K( x ₁ ,...,x _n ))), which is a Gaussian Process (GP). It is reasonable to think of the data as stationary, since the pattern is independent of the location of the observations. Therefore, a fixed covariance function (such as a squared exponent) can be used :

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)+σ ² I)-1K(x ^* ,X) (10)

In some configurations, there may not be any output associated with treating the data as data points representing a Gaussian process. Therefore, in this case, the expectation of the GP of the data point x ^* is meaningless. However, covariance regression can be governed by the expectation of inverting the term (K(X,X)+σ ² I). However, it can be computed reasonably fast because the term is independent of the observation x ^* and can be stored. As such, the process of covariance regression can also be fast.

In some aspects, the hyperparameters (τ and /) of the covariance function of Equation 9 can be set such that the regression is useful for a Pitman-Yor process. Because there is no output for the data point, given the data X and the hyperparameters of the Gaussian process, the marginal likelihood of the output cannot be maximized. Thus, in some aspects heuristics may also be used.

For example, to make the parameter d in Equation 3 obey the constraint 0≤d<1, the magnitude τ of the covariance function may be set to a value less than 1 but close to 1 (eg, τ=0.99). This may actually be insufficient to ensure that the covariance of the regression is less than 1 everywhere. Alternatively, in some aspects, the magnitude τ may be set to a smaller value. The value of the regression can also be scaled down equally for all data points.

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

The covariance regression function in Equation 10 can be interpreted as the conditional likelihood of a mixture of basis functions, each centered on a data point from a given dataset X. The variance of each basis function is then controlled by the length scale parameter /. To properly set l so that the mixture of basis functions does not overfit or underfit the data, in some aspects the length scale parameter l can be set equal to the average minimum distance between observations multiplied by a coefficient , for example given by:

对于全部

其中系数η可被用来调整(例如，扩张或缩减)集群的面积。

for all

where the coefficient n can be used to adjust (eg, expand or shrink) the area of the cluster.

The regression process produces values between 0 and 1 (excluding 1). The covariance of the regression will be very small for points close to or within a given dataset X, and it will be large for points far from items in that dataset.

7A-7D illustrate examples of covariance regression of trajectories with different values of n. 7A is a diagram illustrating a set 702 of training trajectories (eg, 704A-C) for the alphanumeric character "2" presented upside down. The training trajectories can be normalized to provide training patterns that can be used for identification. Figure 7B is a plot of Gaussian process covariance for the training trajectory of Figure 7A. 7C is a graph illustrating another Gaussian process covariance for the training trajectory of FIG. 7A with an increased length-scale (eg, l=0.0244) compared to the length-scale used for FIG. 7B (eg, l=0.0244). 0.0488). Figure 7D is a three-dimensional (3D) representation of the Gaussian process covariance of Figure 7C.

正的)且集合X上的混合覆盖的越平滑。实际上，混合覆盖的边缘也由超参数l控制。参考图7B，在数字“2”的轨迹的开始处，该模型具有其间有间隙的两个脱节分支708和710。另外，在图7B，示出了分开的样本之间的空区域712。然而，具有高斯基础分布的Dirichlet过程可被用来预测并计入将来变化。在一些方面，第二参数(参数d)可被设置成样本的GP协方差乘以可调整系数。这可向PYP提供极好提示以包括并预见变化，同时每一分布的范围被控制。如上所示，式3中的小参数d可造成给定数据点被指派给已占据分量(例如，区或集群)的较高概率。相反地，较高d可使得该过程允许生成新分量，如果该数据点不可能足够由已占据分量之一生成的话。因此，在一些方面，给定数据点x^*处的GP协方差可被用作Pitman-Yor过程的d。如此，如果x^*足够远离已占据分量，则该过程可以指派从基础分布h(θ)采样的新分量。From Figures 7B and 7C showing the results for the value of 1-cov(x*|X) for a given set X, it can be determined that the larger the n coefficient, the larger the l (because it is

positive) and the smoother the blend coverage on the set X. In fact, the edges of the blend coverage are also controlled by the hyperparameter l. Referring to Figure 7B, at the beginning of the trajectory for number "2", the model has two disjointed branches 708 and 710 with a gap therebetween. Additionally, in Figure 7B, empty regions 712 between the separated samples are shown. However, a Dirichlet process with a Gaussian basis distribution can be used to predict and account for future changes. In some aspects, the second parameter (parameter d) may be set to the GP covariance of the samples multiplied by an adjustable coefficient. This can provide an excellent hint to the PYP to include and anticipate changes, while the extent of each distribution is controlled. As shown above, a small parameter d in Equation 3 may result in a higher probability of a given data point being assigned to an occupied component (eg, a region or cluster). Conversely, a higher d may allow the process to allow new components to be generated if the data point is unlikely to be sufficiently generated by one of the occupied components. Thus, in some aspects, the GP covariance at a given data point x ^* can be used as d for the Pitman-Yor process. As such, if x ^* is sufficiently far away from the occupied components, the process can assign new components sampled from the underlying distribution h(θ).

8A-8C illustrate an example of a Pitman-Yor process applied to a trained model based on the trajectory of FIG. 7A. 8A is a diagram illustrating a divided spatial region according to a Pitman-Yor process applied to a trained model based on the trajectory of FIG. 7A (where parameter d is set to 0). Referring to Figure 8B, a Dirichlet process is applied based on the set of training trajectories of Figure 7A to generate a clustered space. Clusters A1-A7 are shown along with the A _complement . Figure 8C is a diagram illustrating the partitioning according to the Pitman-Yor process applied to the trained model based on the trajectory of Figure 7A, where the parameter d is set based on the Gaussian process covariance (eg, the GP covariance has length-scale l=0.0244) Illustration of the space area. As shown in Figure 8B, the area of regions A1-A7 is broad, so that the pattern is still detectable but can lead to false positives. 8C is a diagram illustrating a divided spatial region according to a Pitman-Yor process applied to a trained model based on the training trajectory of FIG. 7A (where parameter d is multiplied by a coefficient greater than 1 (d>1.0)). As shown in Figure 8A, the regions defining the clusters of the pattern are so broad that the number 2 is no longer discernible.

Figure 9 is a graphical representation of a model for spatiotemporal pattern recognition. In the model of Figure 9, a Dirichlet Process Mixture Model (DPM) is shown along with parameters a, d and the underlying distribution H. A Hidden Markov Model receives a sequence of observations from the DPM, which is a sequence of component labels extracted by the DPM.

In some aspects, the correctness of the identified patterns can be verified. Verifying the correctness of an identified pattern in a given sequence of data points includes verifying that all regions of the pattern are correctly satisfied. For validation, most partitions in the trained model are satisfied throughout a given trajectory. That is, a pattern is satisfied if it has data points along trajectories assigned by PYP to clusters of a given pattern. In some aspects, the HMM may further identify that the sequence of trajectories satisfying each partition is in the correct order.

Because the PYP assigns a given sequence of data points to clusters, the number of data points assigned to each cluster can be unambiguous. Furthermore, it is known exactly how many data points the PYP gives to the new clusters, meaning they belong to complementary partitions that collectively represent areas not covered by the trained clusters. A counting scheme is used to ensure that each partition receives some minimum number of allocated data points, and that the allocated points of complementary partitions are below the allowable minimum, the number of partitions satisfying these criteria is considered correct for a given sequence to satisfy the metric for all regions of the trained model.

10 is a functional block diagram illustrating a mobile platform 1000 configured to recognize temporal patterns. Mobile platform 1000 is one possible implementation of mobile platform 100 of FIGS. 1A and 1B . Mobile platform 1000 includes camera 1002 and user interface 1006 . User interface 1006 includes display 1026, which may be configured to display preview images captured by camera 1002 as well as alphanumeric characters, as described above. User interface 1006 may also include a keypad 1028 through which a user may enter information into mobile platform 1000 . If desired, the keypad 1028 can be eliminated by utilizing the camera 1002, as described above. Additionally, to provide a user with a variety of ways to provide a spatiotemporal pattern, for example, in some aspects mobile platform 1000 may include a touch sensor for receiving touch gesture input via display 1026 . The user interface 1006 may also include a microphone 1030 and a speaker 1032 (eg, if the mobile platform is a cellular telephone).

Mobile platform 1000 includes a tracking unit 1018 configured to perform object-guided tracking. In one example, the tracking unit 1018 is configured to track the movement of an object (eg, a fingertip, stylus, writing instrument, or other object), as discussed above, to generate trajectory data.

Mobile platform 1000 also includes a control unit 1004 that is connected to and in communication with camera 1002 and user interface 1006 along with other components such as tracking unit 1018 and gesture recognition unit 1022. Gesture recognition unit 1022 accepts and processes trajectory data received from tracking unit 1018 to recognize user input as symbols and/or gestures. Control unit 1004 may be provided by processor 1008 and associated memory 1014 , hardware 1010 , software 1016 and firmware 1012 .

If desired, the control unit 1004 may also include a graphics engine 1024, which may be, for example, a game engine for rendering the desired AR data in the display 1026. For clarity, tracking component 1018 and gesture recognition component 1022 are illustrated separately and separate from processor 1008 , but may be a single unit and/or implemented in processor 1008 based on instructions in software 1016 running in processor 1008 middle. Processor 1008 and one or more of tracking unit 1018, gesture recognition unit 1022, and graphics engine 1024 may, but need not, include one or more microprocessors, embedded processors, controllers, application specific integrated circuits (ASICs) , Advanced Digital Signal Processing (ADSP) and more. The term processor describes the functions implemented by the system rather than specific hardware. Furthermore, as used herein, the term "memory" refers to any type of computer storage medium, including long-term, short-term, or other memory associated with mobile platform 1000, and is not limited to any particular type or number of memory The type of medium on which the memory, or memory, is stored.

In one configuration, the machine learning model is configured to receive training trajectories. The model is also configured to divide the region into observed clusters and a non-observed complementary cluster. The model is further configured to generate a spatiotemporal pattern model to include each observed cluster and the non-observed complementary cluster. The model includes receiving means, dividing means, and/or generating means. In one aspect, the receiving means, partitioning means, and/or generating means may be the general-purpose processor 302, program memory associated with the general-purpose processor 302, memory blocks 318, local processing unit 402, and /or routing connection processing unit 316 . In another configuration, the receiving means, the dividing means and/or the generating means may be implemented via the processor 1008 , hardware 1010 , firmware 1012 and/or software 1016 . In another configuration, the aforementioned means may be any module or any apparatus configured to perform the functions recited by the aforementioned means.

The processes described herein can be implemented by various means depending on the application. For example, these processes may be implemented in hardware 1010, firmware 1012, software 1016, or any combination thereof. For hardware implementation, these processing units can be implemented in one or more Application Specific Integrated Circuits (ASICs), Digital Signal Processors (DSPs), Digital Signal Processing Devices (DSPDs), Programmable Logic Devices (PLDs), Field Programmable Gate Arrays ( FPGA), processor, controller, microcontroller, microprocessor, electronic device, other electronic unit designed to perform the functions described herein, or a combination thereof.

According to certain aspects of the present disclosure, each local processing unit 402 may be configured to determine parameters of the model based on one or more desired functional characteristics of the model, and as the determined parameters are further adapted, tuned, and updated to The one or more functional characteristics are developed towards the desired functional characteristics.

11 is a diagram illustrating a method 1100 for generating a spatiotemporal pattern model for spatiotemporal pattern recognition in accordance with aspects of the present disclosure. At block 1102, the process receives a training trajectory. Each of the training trajectories may include different data points representing spatiotemporal patterns. The spatiotemporal pattern may, for example, include camera input or input gestures representing at least one of alphanumeric characters, symbols, mouse/touch controls. The received training trajectory defines a region.

At block 1104, the process divides the region into observed clusters and a non-observed complementary cluster. Additionally, at block 1106, the process generates a spatiotemporal pattern model to include each observed cluster and the non-observed complementary cluster.

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

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

Additionally, the process can modify the HMM's observation table to include non-observed complementary clusters. In still other aspects, the process may identify the received trajectory as a spatiotemporal match when the likelihood of the hidden Markov model is above a predetermined threshold.

12 is a flowchart illustrating an exemplary process 1200 for generating a model for spatiotemporal pattern recognition in accordance with aspects of the present disclosure. At block 1202, the process receives a training trajectory (eg, training trajectories 704A-C of Figure 7A). Each of the training trajectories includes spatially distinct data points representing the input pose. At block 1204, a Gaussian process (eg, FIG. 7C) is then applied to the training trajectory and at optional process block 1206, the Gaussian process is used to determine stochastic process parameters (eg, parameter d of the Pitman-Yor process). As mentioned above, process block 1206 is optional and may be omitted when training the model. Thus, in one example, Gaussian process covariance regression is used only for identification and not for training. A stochastic process (eg, a Pitman-Yor process) is then applied in process block 1208 to divide the spatial region of the trajectory into observed regions and a non-observed complementary region. The extent (eg, size) of each of the observed regions may be based on the stochastic process parameters described above. At block 1210, the process generates a model for spatiotemporal pattern recognition that uses each observed region and the non-observed complementary region to determine pattern matches.

13 is a flow diagram illustrating a process 1300 of spatiotemporal pattern recognition. At block 1302, the process receives a trace. The received trajectory may include data points. Each data point of the trajectory may be related to input gestures, stock market related data, speech, weather data, or other spatiotemporal data.

At block 1304, the process evaluates the received trajectories to determine into which clusters (eg, observed and complementary clusters) each data point of the received trajectories falls into the trained spatiotemporal pattern model. The process assigns a marker when a data point falls into an observed cluster. A data point may not be acceptable when it is in a complementary cluster. However, some differences may be tolerated according to aspects of the present disclosure.

At block 1306, the process finds data points in each cluster and complementary clusters. The assigned label for each cluster including the complementary cluster may be provided to the corresponding hidden Markov model to determine the likelihood. By considering complementary clusters of data points, the likelihood produced by the HMM can be reduced.

Each HMM may output a likelihood value that may be compared to a threshold at block 1308 . If the output is above the threshold, the received trajectory may be identified as a spatiotemporal match at block 1310 . Otherwise, at block 1312, the received trajectory is not considered a match.

In some aspects, the order of observations may also be evaluated. That is, in some aspects, the HMM can be trained with the correct order of observations and can be used to evaluate spatiotemporal patterns. For example, if the HMM was trained using the correct order for drawing the number 2, if the number 2 was drawn in reverse order, the likelihood generated by the HMM may be very small and thus may indicate that the input is not a match.

The various operations of the methods described above may be performed by any suitable apparatus capable of performing the corresponding functions. These means may include various hardware and/or software component(s) and/or module(s) including, but not limited to, circuits, application specific integrated circuits (ASICs), or processors. In general, where there are operations illustrated in the figures, those operations may have corresponding counterpart means-plus-function components with similar numbering.

As used herein, the term "determining" encompasses a wide variety of actions. For example, "determining" may include calculating, calculating, processing, deriving, studying, looking up (eg, in a table, database, or other data structure), probing, and the like. Additionally, "determining" may include receiving (eg, receiving information), accessing (eg, accessing data in memory), and the like. Also, "determining" may include resolving, selecting, selecting, establishing, and the like.

As used herein, a phrase referring to "at least one of" a list of items refers to any combination of those items, including individual members. As an example, "at least one of a, b, or c" is intended to encompass: a, b, c, a-b, a-c, b-c, and a-b-c.

The various illustrative logical blocks, modules, and circuits described in connection with this disclosure may be used with general purpose processors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays designed to perform the functions described herein signal (FPGA) or other programmable logic device (PLD), discrete gate or transistor logic, discrete hardware components, or any combination thereof. A general-purpose processor may be a microprocessor, but in the alternative, the processor may be any commercially available processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, such as a combination of a DSP and a microprocessor, multiple microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The steps of a method or algorithm described in connection with this disclosure may be implemented directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in any form of storage medium known in the art. Some examples of storage media that can be used include random access memory (RAM), read only memory (ROM), flash memory, erasable programmable read only memory (EPROM), electrically erasable programmable read only memory (EEPROM) , registers, hard disks, removable disks, CD-ROMs, etc. A software module may include a single instruction, or many instructions, and may be distributed over several different code segments, among different programs, and across multiple storage media. A storage medium may be coupled to the processor such that the processor can read and write information from/to the storage medium. In the alternative, the storage medium may be integrated into the processor.

The methods disclosed herein include one or more steps or actions for achieving the described methods. The method steps and/or actions may be interchanged with each other without departing from the scope of the claims. In other words, unless a specific order of steps or actions is specified, the order and/or use of specific steps and/or actions may be modified without departing from the scope of the claims.

The functions described can be implemented in hardware, software, firmware, or any combination thereof. If implemented in hardware, an example hardware configuration may include a processing system in the device. The processing system can be implemented with a bus architecture. Depending on the specific application and overall design constraints of the processing system, the bus may include any number of interconnecting buses and bridges. A bus may link together various circuits including a processor, a machine-readable medium, and a bus interface. A bus interface may be used to connect, among other things, a network adapter or the like to the processing system via the bus. Network adapters can be used to implement signal processing functions. For certain aspects, a user interface (eg, keypad, display, mouse, joystick, etc.) may also be connected to the bus. The bus may also link various other circuits, such as timing sources, peripherals, voltage regulators, power management circuits, and the like, which are well known in the art and will not be described further.

The processor may be responsible for managing the bus and general processing, including executing software stored on a machine-readable medium. A processor may be implemented with one or more general and/or special purpose processors. Examples include microprocessors, microcontrollers, DSP processors, and other circuitry capable of executing software. Software should be construed broadly to mean instructions, data, or any combination thereof, whether referred to as software, firmware, middleware, microcode, hardware description language, or otherwise. As examples, machine-readable media may include random access memory (RAM), flash memory, read only memory (ROM), programmable read only memory (PROM), erasable programmable read only memory (EPROM), electrically erasable programmable read only memory (EEPROM), registers, magnetic disk, optical disk, hard drive, or any other suitable storage medium, or any combination thereof. The machine-readable medium may be embodied in a computer program product. The computer program product may include packaging material.

In a hardware implementation, the machine-readable medium may be a separate part of the processing system from the processor. However, as those skilled in the art will readily appreciate, the machine-readable medium or any portion thereof may be external to the processing system. As examples, a machine-readable medium may include a transmission line, a carrier wave modulated by data, and/or a computer product separate from the device, all of which can be accessed by a processor through a bus interface. Alternatively or additionally, the machine-readable medium or any portion thereof may be integrated into the processor, such as may be the case with a cache and/or a general purpose register file. Although the various components discussed may be described as having particular locations, such as local components, they may also be configured in various ways, such as certain components being configured as part of a distributed computing system.

The processing system may be configured as a general-purpose processing system having one or more microprocessors providing processor functionality, and external memory providing at least a portion of a machine-readable medium, all connected via an external bus architecture. Other support circuitry is linked together. Alternatively, the processing system may include one or more neuron morphological processors for implementing the neuron models and nervous system models described herein. As another alternative, the processing system may be implemented as an application specific integrated circuit (ASIC) with a processor, bus interface, user interface, support circuitry, and at least a portion of a machine-readable medium integrated in a single chip, or The present disclosure may be implemented using one or more field programmable gate arrays (FPGAs), programmable logic devices (PLDs), controllers, state machines, gated logic, discrete hardware components, or any other suitable circuitry, or capable of implementing the present disclosure. implemented in any combination of the various functional circuits described in this article. Depending on the specific application and the overall design constraints imposed on the overall system, those skilled in the art will recognize how best to implement the functionality described with respect to the processing system.

The machine-readable medium may include several software modules. These software modules include instructions that, when executed by a processor, cause the processing system to perform various functions. These software modules may include a transmitting module and a receiving module. Each software module may reside in a single storage device or be distributed across multiple storage devices. As an example, a software module may be loaded into RAM from a hard drive when a trigger event occurs. During the execution of a software module, the processor may load some instructions into the cache to increase access speed. One or more cache lines may then be loaded into the general register file for execution by the processor. When referring to the functionality of a software module as described below, it will be understood that such functionality is implemented by the processor when the processor executes instructions from the software module. Furthermore, it should be appreciated that aspects of the present disclosure result in improvements in the functioning of processors, computers, machines, or other systems that implement such aspects.

碟，其中盘(disk)常常磁性地再现数据，而碟(disc)用激光来光学地再现数据。因此，在一些方面，计算机可读介质可包括非瞬态计算机可读介质(例如，有形介质)。另外，对于其他方面，计算机可读介质可包括瞬态计算机可读介质(例如，信号)。上述的组合应当也被包括在计算机可读介质的范围内。If implemented in software, the functions may be stored on or transmitted over as one or more instructions or code on a computer-readable medium. Computer-readable media includes both computer storage media and communication media including any medium that facilitates transfer of a computer program from one place to another. A storage medium can be any available medium that can be accessed by a computer. By way of example and not limitation, such computer-readable media may include RAM, ROM, EEPROM, CD-ROM, or other optical disk storage, magnetic disk storage, or other magnetic storage devices, or as desired in the form of carrying or storing instructions or data structures. Program code and any other medium that can be accessed by a computer. Also, any connection is properly termed a computer-readable medium. For example, if the software is transmitted from a web site, server, or other remote source using coaxial cable, fiber optic cable, twisted pair, digital subscriber line (DSL), or wireless technologies such as infrared (IR), radio, and microwave Then, the coaxial cable, fiber optic cable, twisted pair, DSL or wireless technology (such as infrared, radio, and microwave) is included in the definition of medium. Disk and disc as used herein includes compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk, and

Disks, where disks often reproduce data magnetically, while discs reproduce data optically with lasers. Thus, in some aspects computer-readable media may include non-transitory computer-readable media (eg, tangible media). Also, for other aspects, computer-readable media may include transitory computer-readable media (eg, signals). Combinations of the above should also be included within the scope of computer-readable media.

Accordingly, certain aspects may include a computer program product for performing the operations presented herein. For example, such a computer program product may include a computer-readable medium having stored (and/or encoded) thereon instructions executable by one or more processors to perform the operations described herein. For certain aspects, the computer program product may include packaging materials.

Furthermore, it should be appreciated that modules and/or other suitable means for performing the methods and techniques described herein can be downloaded and/or otherwise obtained by user terminals and/or base stations, where applicable. For example, such a device can be coupled to a server to facilitate the transfer of means for performing the methods described herein. Alternatively, the various methods described herein can be provided via a storage device (eg, RAM, ROM, physical storage medium such as a compact disc (CD) or floppy disk, etc.) such that once the storage device is coupled to or provided to User terminal and/or base station, the device can obtain various methods. Furthermore, any other suitable technology suitable for providing the methods and techniques described herein to a device may be utilized.

It is to be understood that the claims are not to be limited to the precise arrangements and components described above. Various changes, substitutions and alterations may be made in the arrangement, operation and details of the methods and apparatus described above without departing from the scope of the claims.

Claims (24)

1. A method of generating a spatio-temporal pattern model for spatio-temporal pattern recognition, the method comprising:

receiving a plurality of training trajectories in a spatial region, each training trajectory comprising a plurality of different data points representing a spatio-temporal pattern;

dividing the spatial region into a plurality of observed clusters and an unfilled complementary cluster, each observed cluster including a set of different data points from the plurality of different data points, and the unfilled complementary cluster being devoid of the plurality of different data points representing a spatio-temporal pattern; and

generating the spatio-temporal pattern model to include the plurality of observed clusters and the unfilled complementary clusters.

2. The method of claim 1, wherein the spatial region is partitioned by applying a stochastic process, and

the range of each of the plurality of observed clusters is determined based on one or more random process parameters.

3. The method of claim 2, wherein the stochastic process is a Dirichlet process mixture model.

4. The method of claim 2, wherein the stochastic process is a two parameter Pitman-Yor process.

5. The method of claim 2, wherein generating the spatio-temporal pattern model comprises creating a hidden markov model based on the stochastic process.

6. The method of claim 5, further comprising modifying an observation table of the hidden Markov model to include the unfilled supplemental clusters.

7. The method of claim 5, further comprising identifying a received trajectory as a spatio-temporal match when a likelihood of the hidden Markov model is above a predetermined threshold.

8. The method of claim 7, further comprising using the stochastic process to determine which cluster, including the unfilled supplemental cluster, corresponds to each data point of the received trajectory.

9. The method of claim 2, further comprising determining a covariance regression of at least two of the plurality of different data points included in the plurality of training trajectories and using the determined covariance regression to determine the one or more stochastic process parameters.

10. The method of claim 9, in which the covariance regression comprises a gaussian process covariance regression.

11. The method of claim 1, wherein the spatiotemporal pattern comprises an input gesture representing at least one of an alphanumeric character, a symbol, or a mouse/touch control.

12. An apparatus for generating a spatio-temporal pattern model for spatio-temporal pattern recognition, the apparatus comprising:

a memory; and

at least one processor coupled to the memory, the at least one processor configured to:

receiving a plurality of training trajectories in a spatial region, each training trajectory comprising a plurality of different data points representing a spatio-temporal pattern;

dividing the spatial region into a plurality of observed clusters and an unfilled complementary cluster, each observed cluster including a set of different data points from the plurality of different data points, and the unfilled complementary cluster being devoid of the plurality of different data representing a spatio-temporal pattern; and

generating the spatio-temporal pattern model to include the plurality of observed clusters and the unfilled complementary clusters.

13. The apparatus of claim 12, in which the at least one processor is further configured to partition the spatial region by applying a stochastic process, and

determining a range for each of the plurality of observed clusters based on one or more stochastic process parameters.

14. The apparatus of claim 13, in which the stochastic process is a Dirichlet process mixture model.

15. The apparatus of claim 13, in which the stochastic process is a two parameter Pitman-Yor process.

16. The apparatus of claim 13, in which the at least one processor is further configured to generate the spatio-temporal pattern model by creating a hidden markov model based on the stochastic process.

17. The apparatus of claim 16, in which the at least one processor is further configured to modify an observation table of the hidden markov model to include the unfilled supplemental clusters.

18. The apparatus of claim 16, in which the at least one processor is further configured to identify a received trajectory as a spatio-temporal match when a likelihood of the hidden markov model is above a predetermined threshold.

19. The apparatus of claim 18, in which the at least one processor is further configured to utilize the stochastic process to determine which cluster, including the unfilled supplemental cluster, corresponds to each data point of a received trajectory.

20. The apparatus of claim 13, in which the at least one processor is further configured to determine a covariance regression for at least two of the plurality of different data points included in the plurality of training trajectories and to use the determined covariance regression to determine the one or more stochastic process parameters.

21. The apparatus of claim 20, in which the covariance regression comprises a gaussian process covariance regression.

22. The apparatus of claim 12, in which the spatiotemporal pattern comprises input gestures representing at least one of alphanumeric characters, symbols, or mouse/touch controls.

23. An apparatus for generating a spatio-temporal pattern model for spatio-temporal pattern recognition, the apparatus comprising:

means for receiving a plurality of training trajectories in a spatial region, each training trajectory comprising a plurality of different data points representing a spatio-temporal pattern;

means for dividing the spatial region into a plurality of observed clusters and an unfilled complementary cluster, each observed cluster comprising a set of different data points from the plurality of different data points, and the unfilled complementary cluster being devoid of the plurality of different data points representing a spatio-temporal pattern; and

means for generating the spatio-temporal pattern model to include the plurality of observed clusters and the unfilled complementary clusters.

24. A non-transitory computer-readable medium having encoded thereon program code for generating a spatio-temporal pattern model for spatio-temporal pattern recognition, the program code being executed by a processor and comprising:

program code for receiving a plurality of training trajectories in a spatial region, each training trajectory comprising a plurality of different data points representing a spatio-temporal pattern;

program code for dividing the spatial region into a plurality of observed clusters and an unfilled supplemental cluster, each observed cluster including a set of different data points from the plurality of different data points, and the unfilled supplemental cluster being devoid of the plurality of different data points representing a spatio-temporal pattern; and

program code to generate the spatio-temporal pattern model to include the plurality of observed clusters and the unfilled supplemental clusters.

Images