Patent Description:
Work of the presently named inventor(s), to the extent it is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.

Many runners desire to monitor speed or pace in order to assess performance, determine whether personal goals are being met and, ultimately, improve running performance. To this end, many runners carry smartphones and/or smart watches that include Global Navigation Satellite System (GNSS) receivers. GNSS may include one or more of the Global Positioning System (GPS) of the United States of America, GLONASS of Russia, BeiDou of China, Galileo of Europe, QZSS of Japan, and/or IRNSS of India. Speed estimates are derived from GNSS locations, or from the Doppler shifts of GNSS signals. Unfortunately, GNSS-based speed measurements tend to be noisy and therefore inaccurate. Noise/inaccuracy is caused by factors such as blockage of GNSS signals (e.g., when running inside a building or under a bridge), multipath reflection of GNSS signals (e.g., when running in a downtown area of a city), and arm swing (e.g., if the device is handheld or worn on the wrist or upper arm). These factors can easily cause an instantaneous, GNSS-based speed measurement to be up to <NUM>% lower than, or <NUM>% higher than, the user's true speed at any given moment. To reduce the level of noise, some devices apply heavy smoothing/averaging to the GNSS speed measurements. While this may reduce the magnitude of speed measurement errors when the user's pace is fairly constant, the technique is insufficiently responsive to large and sudden changes in speed, such as when a user runs intervals, or briefly stops at a crosswalk, etc..

In one example embodiment, a method for accurately estimating gait characteristics of a user is implemented in a computing device. The method includes monitoring a first plurality of parameters indicative of movement of the user. Monitoring the first plurality of parameters includes monitoring (i) a first GNSS-derived speed of the user and (ii) a step count of the user. The method also includes processing values of the monitored first plurality of parameters to determine values of a second plurality of parameters indicative of movement of the user. Processing values of the monitored first plurality of parameters includes applying, as inputs to an estimator (e.g., a Kalman filter) having the second plurality of parameters as estimator states, one or both of (i) values of at least one of the monitored first plurality of parameters, and (ii) values of at least one parameter derived from one or more of the monitored first plurality of parameters and predicting, at each of a plurality of time intervals, that values of the estimator states are unchanged from respective values of the estimator states at a most recent time interval, wherein the estimator is a Kalman filter, a non-linear estimator or a particle filter. At least two parameters of the second plurality of parameters are collectively indicative of a mapping between step frequency of the user and step length of the user, wherein the mapping includes (i) a slope of a line representing the mapping between step frequency of the user and step length of the user, and (ii) an intercept of the line representing the mapping between step frequency of the user and step length of the user. The method also includes causing a graphical user interface of the computing device or another computing device to display values of one or both of (i) at least one of the second plurality of parameters, and (ii) at least one parameter derived from one or more of the second plurality of parameters.

In another example embodiment, a non-transitory, computer-readable medium stores instructions that, when executed by one or more processors of a computing device, cause the computing device to monitor a first plurality of parameters indicative of movement of a user. The first plurality of parameters includes (i) a first GNSS-derived speed of the user and (ii) a step count of the user. The instructions also cause the computing device to process values of the monitored first plurality of parameters to determine values of a second plurality of parameters indicative of movement of the user. Processing values of the monitored first plurality of parameters includes applying, as inputs to an estimator (e.g., a Kalman filter) having the second plurality of parameters as estimator states, one or both of (i) values of at least one of the monitored first plurality of parameters, and (ii) values of at least one parameter derived from one or more of the monitored first plurality of parameters and predicting, at each of a plurality of time intervals, that values of the estimator states are unchanged from respective values of the estimator states at a most recent time interval, wherein the estimator is a Kalman filter, a non-linear estimator or a particle filter. At least two parameters of the second plurality of parameters are collectively indicative of a mapping between step frequency of the user and step length of the user, wherein the mapping includes (i) a slope of a line representing the mapping between step frequency of the user and step length of the user, and (ii) an intercept of the line representing the mapping between step frequency of the user and step length of the user. The instructions also cause the computing device to display on a graphical user interface of the computing device, or cause a graphical user interface of another computing device to display, values of one or both of (i) at least one of the second plurality of parameters, and (ii) at least one parameter derived from one or more of the second plurality of parameters.

In another example embodiment, a mobile computing device includes a display screen, one or more processors, and a memory. The memory stores instructions that, when executed by the one or more processors, cause the mobile computing device to monitor a first plurality of parameters indicative of movement of a user of the mobile computing device. The first plurality of parameters includes (i) a first GNSS-derived speed of the user and (ii) a step count of the user. The instructions also cause the mobile computing device to process values of the monitored first plurality of parameters to determine values of a second plurality of parameters indicative of movement of the user. Processing values of the monitored first plurality of parameters includes applying, as inputs to an estimator (e.g., a Kalman filter) having the second plurality of parameters as estimator states, one or both of (i) values of at least one of the monitored first plurality of parameters, and (ii) values of at least one parameter derived from one or more of the monitored first plurality of parameters and predicting, at each of a plurality of time intervals, that values of the estimator states are unchanged from respective values of the estimator states at a most recent time interval, wherein the estimator is a Kalman filter, a non-linear estimator or a particle filter. At least two parameters of the second plurality of parameters are collectively indicative of a mapping between step frequency of the user and step length of the user, wherein the mapping includes (i) a slope of a line representing the mapping between step frequency of the user and step length of the user, and (ii) an intercept of the line representing the mapping between step frequency of the user and step length of the user. The instructions also cause the mobile computing device to display, on a graphical user interface presented on the display screen, values of one or both of (i) at least one of the second plurality of parameters, and (ii) at least one parameter derived from one or more of the second plurality of parameters.

<CIT> discloses a displacement of a pedestrian that is determined from his non vertical accelerations by detecting a step frequency and a displacement step.

<CIT> discloses a pedestrian pace estimation with pace change detection by combining GNSS data with a pedometer.

<CIT> discloses a Land Surveyor System carried by a surveyor moving from a first known position at the start of a survey interval to a second known position at the end of the survey interval has an aided inertial navigation system that provides a continuing sequence of time-indexed present position values.

<CIT> discloses an inertial system hybridised with a GPS receiver, wherein said hybridisation is carried out by Kalman filtering.

To estimate a user's speed with a reduced level of noise/error, while also maintaining a high level of responsiveness to large and sudden changes in the user's speed, a custom estimator, such as a Kalman filter, is utilized. As inputs, the estimator utilizes a number of different types of observations/measurements, including one or more GNSS-derived speeds of the user and a step count of the user. In one implementation, for example, the Kalman filter utilizes a first observed speed that is derived from GNSS locations of the user, a second observed speed that is derived from Doppler shifts of the GNSS signals, and an observed step count of the user.

Due to the inherent properties of optimal estimators, such as Kalman filters, the estimation error for each of the estimator states (i.e., the estimates provided/output by the estimator) may be minimized. Much of the following description corresponds to an implementation in which a Kalman filter is used as the estimator. However, those skilled in the art will recognize that alternative optimal estimators, such as non-linear estimators, particle filters, etc., may also be used.

The states of the custom Kalman filter include characteristics of a gait model of the user, and possibly also one or more other characteristics relating to user movement (e.g., the user's speed). In some implementations, the gait model constitutes or includes a relation between the user's step frequency (cadence) and the user's step length. In one implementation, for example, the custom Kalman filter produces estimates of (<NUM>) the slope of a line representing cadence versus step length of the user, and (<NUM>) the x- or y- intercept of the line representing cadence versus step length of the user. For most individuals, step length varies considerably as a function of cadence. Moreover, step length and its relation to cadence typically change throughout the course of a run or walk based on various factors, such as the user's level of fatigue, and whether the user is running/walking on flat ground, or up or down a hill. By estimating parameters indicative of the relation between step length and cadence (e.g., in real-time), the custom Kalman filter may closely track such changes throughout the course of a run and/or walk. In some implementations, a user may be provided with this information on a display, and use the information to modify his or her gait and improve future performance.

A single user's gait characteristics (e.g., step length versus given cadence) can also vary greatly depending on whether the user is walking or running. To account for this difference, in some implementations, some or all of the Kalman filter states/estimates may be specific to a "walking" gait model of the user or a "running" gait model of the user, with the appropriate gait model being selected based on one or more factors (e.g., a current cadence indicating that the user is likely walking, or an accelerometer detecting impacts that are more consistent with running, etc.). Moreover, in some implementations, a process noise covariance of the custom Kalman filter can be dynamically adjusted based on one or more factors (e.g., whether the step count indicates the user has stopped, and/or whether at least some threshold level of speed change is measured, etc.). Dynamically changing the process noise covariance may generally serve to reduce the noisiness/error of the Kalman filter estimates when the user's pace is fairly constant, without overly degrading the responsiveness of the estimates to large and sudden changes in the user's speed. Other potential features and benefits of the invention are discussed below.

<FIG> is a block diagram of an example system <NUM> in which techniques for real-time estimation of a user's speed and gait characteristics may be implemented. The example system <NUM> includes a computing device <NUM> and three movement detection units <NUM>, <NUM>, <NUM>. In some implementations, computing device <NUM> is a mobile computing device that a user wears or carries while walking or running. For example, computing device <NUM> may be a smartphone (e.g., held in the user's hand, or carried in an arm band or belt, etc.), or a wearable computing device such as a smart watch, smart glasses, or smart clothing. The computing device <NUM> may be a general-purpose computing device, or a dedicated device (e.g., a device dedicated entirely to fitness tracking). In other implementations, computing device <NUM> is a stationary or semi-stationary computing device, such as a desktop or laptop computer or a server. Examples of each of these alternative implementations will be discussed in more detail below.

In the example embodiment of <FIG>, computing device <NUM> includes a processor <NUM>, a memory <NUM>, and a user interface <NUM>. The processor <NUM> may be a single processor (e.g., a central processing unit (CPU)), or may include a set of processors (e.g., one or more CPUs and a graphics processing unit (GPU)). Memory <NUM> is a computer-readable, non-transitory storage unit or device, or collection of units/devices, that may include persistent (e.g., hard disk) and/or non-persistent memory components. Memory <NUM> stores instructions that are executable on processor <NUM> to perform various operations, including the instructions of various software applications, and the data generated and/or used by such applications. In the example implementation of <FIG>, memory <NUM> stores at least an activity tracking application <NUM>. Generally, and as discussed in more detail below, activity tracking application <NUM> is executed by processor <NUM> to track a user's running and/or walking performance based on measurements/observations provided by movement detection units <NUM>, <NUM>, <NUM>.

User interface <NUM> includes hardware, firmware and/or software configured to enable a user to interact with (i.e., both provide inputs to and perceive outputs of) computing device <NUM>. For example, user interface <NUM> may include a touchscreen with both display and manual input capabilities. User interface <NUM> may also, or instead, include other types of components, such as a keyboard and monitor (with associated processing components) that provide input/output capabilities to the user.

Each of movement detection units <NUM>, <NUM>, <NUM> is worn and/or carried by the user, and observes (e.g., detects or senses) movements of the user and generates parameters indicative of that movement. In one implementation, for example, movement detection unit <NUM> uses GNSS signals to determine locations of the user, and to generate user speed values based on changes in those locations over time, movement detection unit <NUM> uses Doppler shifts in GNSS signals to generate other, independent user speed values, and movement detection unit <NUM> detects user steps and provides a step count of the user.

Each of movement detection units <NUM>, <NUM>, <NUM> may include hardware components and/or software components, and may be external to computing device <NUM> or integrated within computing device <NUM>. External movement detection units may communicate with computing device <NUM> via a wired or wireless (e.g., Bluetooth, WiFi, etc.) network interface of computing device <NUM> (not shown in <FIG>). In implementations where computing device <NUM> is a smartphone or smart watch and movement detection unit <NUM> is a step counter, for example, movement detection unit <NUM> may be a foot-mounted accessory device that communicates with computing device <NUM> via Bluetooth, or an accelerometer component with computing device <NUM>. Generally, movement detection units <NUM>, <NUM>, <NUM> may be implemented on any device worn or carried by the user in any location (e.g., hand, wrist, arm, waist-band, etc.). In one implementation, for example, an accelerometer and/or step counter are implemented on a device worn by the user on his or her wrist, arm, waist-band, or any other suitable location.

While three distinct movement detection units are shown in <FIG>, other implementations may include more (e.g., four, five, etc.) or fewer (two) such units, and/or two or more of the movement detection units may be included in a single device or component. In one implementation where movement detection unit <NUM> provides a speed derived from GNSS locations and movement detection unit <NUM> provides a speed derived from GNSS Doppler shifts, for example, both movement detection unit <NUM> and movement detection unit <NUM> are included in a single GNSS-capable device external to computing device <NUM>, or in a single GNSS component of computing device <NUM> (e.g., if computing device <NUM> is a smartphone or smart watch).

As noted above, computing device <NUM> may be a stationary or semi-stationary computing device, such as a desktop computer, laptop computer, or server. For example, computing device <NUM> may be a server that is remote from the user and movement detection units <NUM>, <NUM>, <NUM>. In such an embodiment, each of movement detection units <NUM>, <NUM>, <NUM> may include a network interface that communicates with a network interface of computing device <NUM> via a wireless (or partially wireless) network not shown in <FIG> (provided that the user has expressly agreed to share his or her data). As just one specific example, the network may include a cellular network, the Internet, and a server-side LAN. Alternatively, some or all of movement detection units <NUM>, <NUM>, <NUM> may communicate (e.g., via wired connections and/or Bluetooth) with a mobile computing device not shown in <FIG>, and that mobile computing device may communicate with the remote computing device <NUM> via the network to relay the measurements/observations to computing device <NUM> (provided that the user has expressly agreed to share his or her data).

When executed by processor <NUM>, activity tracking application <NUM> monitors the observations/measurements generated by movement detection units <NUM>, <NUM>, <NUM>, and applies those observations/ measurements (and/or values derived therefrom) as inputs to a Kalman filter <NUM>. As noted above, other implementations may use a different type of estimator instead of a Kalman filter. The states of the Kalman filter <NUM> include an estimated speed <NUM> of the user and an estimated gait model <NUM> of the user. In other implementations, the estimated speed <NUM> is not included as a state of the Kalman filter <NUM>. The estimated gait model <NUM> may include multiple parameters relating to the user's gait. In one implementation, for example, the estimated gait model <NUM> includes two parameters that are jointly indicative of the user's cadence as a function of the user's step length (e.g., slope and x- or y- intercept of a line that models the relation between cadence and step length). Example gait models are discussed further below in connection with <FIG>.

Activity tracking unit <NUM> may pre-process one, some, or all of the observations/measurements from movement detection units <NUM>, <NUM>, <NUM> prior to applying those observations/measurements as inputs to the Kalman filter <NUM>. Moreover, activity tracking unit <NUM> may dynamically adjust one or more parameters of the Kalman filter <NUM> itself (e.g., process noise covariance) during the course of a run and/or walk. Operation of the Kalman filter <NUM>, along with some specific examples of pre-processing and dynamic parameter adjustment, are discussed in more detail below in connection with a specific implementation shown in <FIG>.

In some implementations, the estimates (updated states) produced by the Kalman filter <NUM> and/or values derived therefrom (e.g., values of the estimated speed <NUM>, step length versus time, one or more plots of the estimated gait model <NUM>, etc.) are displayed to the user. Some or all of the information may be displayed in real-time as the user is running and/or walking (e.g., via user interface <NUM>, if computing device <NUM> is a smartphone or wearable computing device). Alternatively, or in addition, some or all of the information may be displayed to the user after the run/walk is completed. For example, some or all the information may be displayed to the user when he or she later uses a web browser application of computing device <NUM> or another computing device (or activity tracking application <NUM>, or another activity tracking application not shown in <FIG>) to access a server that collects the estimates/states from computing device <NUM> (if the user has expressly agreed to share his or her data) and packages that data for display. Some example user displays are discussed below in connection with <FIG>.

<FIG> and <FIG> illustrate two alternative implementations of system <NUM> in which computing device <NUM> is a mobile computing device carried or worn by the user. Referring first to <FIG>, a system <NUM> includes a mobile computing device <NUM>, and a server <NUM> that is remote from mobile computing device <NUM> and communicatively coupled to mobile computing device <NUM> via a network <NUM>. While <FIG> shows mobile computing device <NUM> as a smartphone, in other implementations mobile computing device <NUM> may be a smart watch, or another type of mobile computing device (e.g., smart glasses or smart clothing) worn or carried by a user. Moreover, while <FIG> shows only one mobile computing device <NUM>, it is understood that server <NUM> may also be in communication with numerous other, similar mobile computing devices of other users. Further, while referred to herein as a "server," server <NUM> may, in some implementations, include multiple co-located or remotely distributed computing devices. Network <NUM> may include any suitable combination of one or more wired and/or wireless communication networks, such as one or more local area networks (LANs), metropolitan area networks (MANs), and/or wide area network (WANs). As just one specific example, network <NUM> may include a cellular network, the Internet, and a server-side LAN.

Mobile computing device <NUM> is communicatively coupled to a GNSS unit <NUM> and a step counter unit <NUM>. GNSS unit <NUM> may be integrated within mobile computing device <NUM>, or an external unit that is also worn or carried by the user (e.g., a GNSS unit within a smart watch of the user). In one implementation, GNSS unit <NUM> provides observed values of speeds that are derived from GNSS signals. For example, in an implementation where GNSS unit <NUM> corresponds to movement detection unit <NUM> of <FIG>, GNSS unit <NUM> may calculate speed based on GNSS locations of the user, and provide those speed observations to mobile computing device <NUM>. As another example, in an implementation where GNSS unit <NUM> corresponds to both movement detection unit <NUM> and movement detection unit <NUM> of <FIG>, GNSS unit <NUM> may calculate a first speed based on GNSS locations of the user and a second speed based on Doppler shifts of GNSS signals, and provide both speed observations to mobile computing device <NUM>.

Like GNSS unit <NUM>, step counter unit <NUM> may be integrated within mobile computing device <NUM>, or an external unit that is worn or carried by the user (e.g., a device physically mounted on or otherwise coupled to the user's hip, arm or foot). The step counter unit <NUM> may include an accelerometer, a magnetic pendulum, and/or any other hardware and/or software suitable for detecting steps. In different implementations, step counter unit <NUM> may provide a cumulative step count to mobile computing device <NUM>, or may provide a single count (i.e., a step detection signal) that can be added to a total step count maintained by mobile computing device <NUM>.

Mobile computing device <NUM> includes a processor <NUM>, a memory <NUM>, a user interface <NUM>, and a network interface <NUM>. Processor <NUM>, memory <NUM>, and user interface <NUM>, may be similar to processor <NUM>, memory <NUM>, and user interface <NUM> of <FIG>, for example. Network interface <NUM> includes hardware, firmware and/or software configured to enable mobile communications device <NUM> to exchange electronic data with server <NUM> via network <NUM>. For example, network interface <NUM> may include cellular and/or WiFi transceivers.

Memory <NUM> stores an activity tracking application <NUM>, which implements a custom Kalman filter <NUM> having an estimated speed <NUM> and an estimated gait model <NUM> as filter states. Activity tracking application <NUM> and the Kalman filter <NUM> may be similar to activity tracking application <NUM> and Kalman filter <NUM>, respectively, of <FIG>, for example.

Server <NUM> includes a network interface <NUM>, a memory <NUM>, and a processor <NUM>. Network interface <NUM> includes hardware, firmware and/or software configured to enable server <NUM> to exchange electronic data with mobile computing device <NUM> and other, similar mobile computing devices (not shown in <FIG>) via network <NUM>. For example, network interface <NUM> may include a wired or wireless router and a modem.

Memory <NUM> is a computer-readable, non-transitory storage unit or device, or collection of units/devices, that may include persistent (e.g., hard disk) and/or non-persistent memory components. Memory <NUM> stores the software instructions of an activity tracking manager <NUM>, and processor <NUM> includes one or more processors configured to execute those instructions. In operation, if the user has expressly agreed to share his or her data, activity tracking application <NUM> may cause mobile computing device <NUM> to transmit estimated speeds and gait model parameters to server <NUM> (e.g., in real-time as those parameters are estimated, or during a post-activity session upload process supported by activity tracking application <NUM>, etc.). Activity tracking manager <NUM> may store the received data in a performance database <NUM> (e.g., along with metadata that associates the data with an account of the user of mobile computing device <NUM>). The performance database <NUM> may be stored in memory <NUM> or another suitable memory. When the user accesses his or her account (e.g., via a web browser application, activity tracking application <NUM>, and/or another dedicated application), he or she may view the estimated parameters (e.g., instantaneous speed and step length as a function of time over the course of a run/walk), parameters that are calculated based on the estimated parameters, and/or other parameters (e.g., a cadence versus time that is derived directly from the step count provided by step counter unit <NUM>).

In some implementations, system <NUM> does not include server <NUM>. For example, activity tracking manager <NUM> may be a component of activity tracking application <NUM>, and/or performance database <NUM> may be stored in memory <NUM>. In another alternative implementation, activity tracking application <NUM> is instead stored in memory <NUM> of server <NUM>. For example, GNSS unit <NUM> and step counter unit <NUM> may include respective network interfaces that permit communication with server <NUM> (or may communicate with server <NUM> via mobile computing device <NUM>) and, if the user has expressly agreed to share his or her data, server <NUM> may generate values of the estimated speed <NUM> and estimated gait model <NUM> rather than mobile computing device <NUM>. In such an implementation, server <NUM> may transmit the estimated parameters (and/or values derived therefrom) to mobile computing device <NUM> for display to the user in real time via user interface <NUM>, and/or the user may access server <NUM> (via a web browser application or dedicated application) after a run/walk to view his or her performance.

Referring next to <FIG>, a system <NUM> includes a first mobile computing device <NUM> (e.g., a smartphone), a second wearable computing device <NUM> (e.g., a smart watch), and a server <NUM> that is remote from both mobile computing device <NUM> and mobile computing device <NUM>. Server <NUM> is communicatively coupled to mobile computing device <NUM> via a network <NUM>, which may be similar to network <NUM> of <FIG>. While <FIG> shows mobile computing device <NUM> as a smartphone and mobile computing device <NUM> as a smart watch, in other implementations mobile computing device <NUM> may be a different mobile computing device (e.g., a smart watch) and/or mobile computing device <NUM> may be a different mobile computing device (e.g., smart glasses or other wearable electronics). Moreover, while <FIG> shows only one pair of mobile computing devices <NUM>, <NUM>, which are carried by and/or worn by a single user, it is understood that server <NUM> may also be in communication with numerous other, similar mobile computing devices of numerous other users. Further, while referred to herein as a "server," server <NUM> may, in some implementations, include multiple co-located or remotely distributed computing devices.

Mobile computing device <NUM> includes, or is coupled to, a GNSS unit <NUM> and a step counter <NUM>, which may be similar to the like-named elements of <FIG>, and includes a processor <NUM>, memory <NUM>, user interface <NUM>, and network interface <NUM>, which also may be similar to the like-named elements shown in <FIG>. Moreover, activity tracking application <NUM>, the Kalman filter <NUM>, the estimated speed <NUM>, and the estimated gait model <NUM> may be similar to the like-named elements shown in <FIG>, except as discussed below with respect to operation of the system <NUM>.

Server <NUM> includes a network interface <NUM>, memory <NUM>, and processor <NUM>, which may be similar to the like-named elements in <FIG>. Moreover, memory <NUM> may store an activity tracking manager <NUM>, which may be similar to the like-named element of <FIG>. Performance database <NUM> may be similar to performance database <NUM> of <FIG>, and may or may not be stored in memory <NUM>.

Mobile computing device <NUM> includes a processor <NUM>, a user interface <NUM>, a network interface <NUM>, and a memory <NUM>. The processor <NUM> may be a single processor (e.g., a single CPU), or may include a set of processors (e.g., one or more CPUs and a GPU). User interface <NUM> includes hardware, firmware and/or software configured to enable a user to interact with (i.e., both provide inputs to and perceive outputs of) mobile computing device <NUM>. For example, user interface <NUM> may include a touchscreen with both display and manual input capabilities. User interface <NUM> may also include other components, such as a microphone (with associated processing components) that provides voice control/input capabilities to the user, one or more physical input keys or buttons, and so on.

Network interface <NUM> includes hardware, firmware and/or software configured to enable mobile computing device <NUM> to exchange electronic data with mobile computing device <NUM> via a short range link <NUM>. For example, network interface <NUM> and network interface <NUM> may each include a Bluetooth transceiver. In other implementations, other short range technologies are instead used (e.g., WiFi, RFID, etc.).

Memory <NUM> is a computer-readable, non-transitory storage unit or device, or collection of units/devices, that may include persistent and/or non-persistent memory components. Memory <NUM> stores instructions that are executable by processor <NUM> to perform various operations, including the instructions of various software applications, and the data generated and/or used by such applications. In the example implementation of <FIG>, memory <NUM> stores activity tracking application <NUM>. Activity tracking application <NUM> acts in tandem with activity tracking application <NUM> of mobile computing device <NUM>. For example, as the Kalman filter <NUM> of activity tracking application <NUM> generates values of the estimated speed <NUM> and estimated gait model <NUM>, mobile computing device <NUM> may transmit those values to mobile computing device <NUM> (via short range link <NUM>), and activity tracking application <NUM> may cause user interface <NUM> to display the real-time values to the user as the user runs/walks. In some implementations, activity tracking application <NUM> also, or instead, supports one or more user control functions. For example, activity tracking application <NUM> may cause user interface <NUM> to display an interactive control that, when activated by the user, pauses tracking of the user's run/walk (e.g., by communicating the activation to mobile computing device <NUM> via short range link <NUM>, in response to which activity tracking application <NUM> pauses tracking).

In some implementations, system <NUM> does not include server <NUM>. For example, activity tracking manager <NUM> may be a component of activity tracking application <NUM>, and/or performance database <NUM> may be stored in memory <NUM>. In another alternative implementation, activity tracking application <NUM> is instead stored in memory <NUM> of mobile computing device <NUM> (in place of activity tracking application <NUM>). For example, mobile computing device <NUM> may receive data from GNSS unit <NUM> and step counter unit <NUM>, and transmit that data to mobile computing device <NUM> via short range link <NUM> as the data is received to allow mobile computing device <NUM> to generate real-time gait model parameter, speed, and/or other estimates.

In yet another alternative implementation, activity tracking application <NUM> is instead stored in memory <NUM> of server <NUM>. For example, GNSS unit <NUM> and step counter unit <NUM> may include respective network interfaces that permit communication with server <NUM> (or may communicate with server <NUM> via mobile computing device <NUM>) and, if the user has expressly agreed to share his or her data, server <NUM> may generate values of the estimated speed <NUM> and estimated gait model <NUM> rather than mobile computing device <NUM>. In such an implementation, server <NUM> may transmit the estimated parameters (and/or values derived therefrom) to mobile computing device <NUM> for display to the user in real time via user interface <NUM> and/or user interface <NUM>, and/or the user may access server <NUM> (via a web browser application or dedicated application) after a run/walk to view his or her performance.

As noted above, the estimated gait model (e.g., gait model <NUM> of <FIG>, gait model <NUM> of <FIG>, or gait model <NUM> of <FIG>) may represent various characteristics of a user's gait. Moreover, because the characteristics of a user's gait may change considerably depending on whether the user is running or walking, the activity tracking application (e.g., activity tracking application <NUM> of <FIG>, activity tracking application <NUM> of <FIG>, or activity tracking application <NUM> of <FIG>) may, in some implementations, select a "running" gait model or a "walking" gait model as the model to be updated/estimated by the custom Kalman filter (e.g., Kalman filter <NUM> of <FIG>, Kalman filter <NUM> of <FIG>, or Kalman filter <NUM> of <FIG>) at any given time.

<FIG> depicts an example set <NUM> of gait models for a single user, including a walking gait model <NUM> and a running gait model <NUM>. The walking gait model <NUM> is associated with a first region 262A in which step length increases as cadence increases, a second region 262B in which step length is constant over a range of cadences, and a third region 262C in which step length is constant over another range of cadences. Similarly, the running gait model <NUM> is associated with a first region 264A in which step length increases as cadence increases, a second region 264B in which step length is constant over a range of cadences, and a third region 264C in which step length is constant over another range of cadences. Thus, the example gait models <NUM>, <NUM> both include non-linearities. In other implementations, the gait models <NUM>, <NUM> do not attempt to capture the limits of step length and/or cadence, and are purely linear. In some implementations, the gait models may be quadratic functions or other functions that can be represented by polynomials, exponential functions, logarithmic functions, or combinations thereof.

As seen in <FIG>, both the walking gait model <NUM> and the running gait model <NUM> show that the user's step length generally increases as the user's step frequency (cadence) increases. However, the range of step lengths, the range of cadences, and the slope of the relation between the two, varies significantly between the two models. While the example gait models <NUM>, <NUM> in <FIG> do not overlap along the x-axis, overlap is possible in other implementations and/or scenarios.

In one implementation, the gait model parameters estimated by the custom Kalman filter (e.g., for gait model <NUM> of <FIG>, gait model <NUM> of <FIG>, or gait model <NUM> of <FIG>) include parameters that are jointly indicative of the linear, sloped portion of the gait model (e.g., region 262A or 264A in <FIG>, depending on which gait model is currently in use). For example, the gait model parameters may include, or consist entirely of, the slope and x- or y- intercept of the sloped line portion.

When the activity tracking application determines that the user has changed from running to walking, or vice versa, the old gait model may be stored in cache memory (e.g., within memory <NUM> of <FIG>, memory <NUM> of <FIG>, or memory <NUM> of <FIG>), and the new gait model may be loaded from the cache memory. The manner in which the activity tracking application determines whether the user is running or walking at any given time may vary depending on the implementation. In one implementation, for example, the activity tracking application determines that the user is walking if he or she currently has a cadence, as derived from observed step counts over known time intervals, that is less than a threshold cadence (e.g., below <NUM> steps per second in the scenario of <FIG>), and determines that the user is running if he or she currently has a cadence that is above the threshold cadence. In an alternative implementation, the determination is made based on the magnitude of measurements made by an accelerometer (e.g., a same accelerometer used to measure step count, as discussed above in connection with <FIG>). For example, the activity tracking application may determine that the user is running if acceleration magnitude (or an average magnitude level, etc.) is above a threshold level, and instead determine that the user is walking if acceleration magnitudes (or an average magnitude level, etc.) is below the threshold level. Hysteresis of thresholds (for cadence or acceleration) may be used to prevent rapid bouncing between gait models. Other suitable techniques may also, or instead, be used. For example, the activity tracking application may base the gait model selection on acceleration magnitudes, or patterns in acceleration magnitudes, as well as one or more other factors (e.g., lateral acceleration, vertical acceleration, cadence, etc.). In some implementations, machine learning is used to determine, based on three-dimensional acceleration and/or other measurements, which combinations of measurement values and/or ranges are indicative of walking versus running for a particular user.

In other implementations, the set <NUM> includes only a single gait model that is always employed by the custom Kalman filter, or includes more than two gait models. For example, in addition to gait models <NUM> and <NUM>, a third gait model may be used when the activity tracking application determines that the user is "jogging" (running slowly), or "power walking," etc. Moreover, in some implementations, gait models <NUM>, <NUM> may be differ than those shown in <FIG>. As just one example, gait models <NUM>, <NUM> may still be indicative of step length versus cadence, but may accomplish this by plotting step length versus the inverse of cadence (i.e., step period).

<FIG> is a data flow diagram of an example process <NUM> for real-time estimation of a user's speed and gait characteristics. The process <NUM> may be implemented in whole or in part by activity tracking application <NUM> of <FIG>, activity tracking application <NUM> of <FIG>, or activity tracking application <NUM> of <FIG>, for example. It is understood that the process <NUM> represents just one possible implementation.

The process <NUM> corresponds to the operation of a custom Kalman filter (e.g., Kalman filter <NUM> of <FIG>, Kalman filter <NUM> of <FIG>, or Kalman filter <NUM> of <FIG>), along with associated pre-processing of observation/measurement data, according to one implementation. Before addressing the flow of data shown in <FIG>, the custom Kalman filter (corresponding to the specific implementation of process <NUM>) is described. A system model for the Kalman filter can be expressed as: <MAT> <MAT> <MAT> <MAT> In Equations <NUM> through <NUM>, k represents the time, with each integer increment to k representing a next time interval (e.g., the next half second, the next second, the next two seconds, etc., depending on the implementation). Also in Equations <NUM> through <NUM>, xk is a vector representing the Kalman filter state at time k, Fk is a matrix representing the Kalman filter state transition model at time k, wk is a vector representing the process noise at time k (here, a normal distribution with a mean of zero and a covariance of Qk), zk is a vector representing the observation (input to the Kalman filter) at time k, Hk is a matrix representing the observation model at time k (i.e., the mapping of the measurement/observation to the Kalman filter state), and vk is a vector representing the observation noise at time k (here, a normal distribution with a mean of zero and a covariance of Rk). The "process noise" wk represents parameters that have an effect on the estimates/states but are not directly captured in the system model (in this case, acceleration), and the "observation noise" vk represents noise in the measurements/observations that are input to the Kalman filter.

In the example process <NUM>, the Kalman filter state xk is a vector with three elements: the user's true speed (s), the slope of the user's gait model (m), and the y-intercept of user's gait model (n), where the gait model includes a line representing step length as a function of cadence. In an embodiment where the observation model Hk of Equation <NUM> is not a linear function (e.g., as seen below in Equations <NUM> and <NUM>), the custom Kalman filter is an extended Kalman filter, such that Equation <NUM> is replaced with the following equation: <MAT>.

The Kalman filter of the process <NUM> assumes, for purposes of the prediction, that the user's speed and gait model parameters do not change from one time increment to the next. This assumption results from the fact that the Kalman filter of the process <NUM> does not model acceleration. To reflect this assumption, Fk is a 3x3 identity matrix that is fixed for all values of k.

The Kalman filter operation generally includes two steps/stages per time interval (i.e., per k value): an a priori prediction step, and an a posteriori update step. In the prediction step, the Kalman filter generates a prediction of the next state x and the state covariance P based on the system model at time k-<NUM>, as follows: <MAT> <MAT> The state covariance P can be viewed as a measure of the uncertainty in the prediction of Equation <NUM>. Because Fk is an identity matrix, Equations <NUM> and <NUM> result in the predicted state being the same as the previous state estimate, and the state covariance being the previous state covariance plus the covariance Qk (which captures the extent to which the state might have further changed since the last time interval). In the process <NUM>, the covariance Qk of the process noise wk may be dynamically set to reflect the level of uncertainty that results from acceleration not being modeled by the system, as is discussed further below.

After the prediction step, in the a posteriori update step, the estimations are updated based on the current (time k) observations as follows: <MAT> <MAT> In Equations <NUM> and <NUM>, Kk the Kalman filter gain (a scalar value) at time k, dzk is a vector representing the observation residual at time k, and I is an identity matrix. The Kalman filter gain Kk, the observation residual dzk, and a residual covariance (Sk) that is used to calculate the Kalman filter gain are calculated as follows: <MAT> <MAT> <MAT>.

Thus, the observation residual dzk is the difference between the measurement zk and the expected measurement Hkx̂k|k-<NUM>. By virtue of being a multiplier of dzk in Equation <NUM>, the Kalman filter gain Kk determines the extent to which new measurements (more precisely, differences between new measurements and expected measurements) will affect the current estimate of the state, x̂k|k. The new/current state estimate x̂k|k is the output of the Kalman filter at time k (i.e., in this implementation, the new speed, gait model slope, and gait model intercept). x̂k|k is also stored for use in the prediction step of the next time interval, at which point x̂k|k will be used as the quantity x̂k-<NUM>|k-<NUM> in Equation <NUM>. As seen in Equation <NUM>, the Kalman filter gain Kk also determines the extent to which the state covariance prediction Pk|k-<NUM> and the observation noise covariance Rk will affect the current covariance Pk|k. The new/current covariance Pk|k is also stored for use in the prediction step of the next time interval, at which point Pk|k will be used as the quantity Pk-<NUM>|k-<NUM> in Equation <NUM>.

The example process <NUM> corresponds to an implementation in which three observations/measurements are input to the Kalman filter: a first user speed derived from Doppler shifts of the GNSS signals, a second user speed derived from the GNSS locations, and a user cadence (e.g., as calculated based on a measured step count of the user and a known time interval). As seen in Equation <NUM> above, Hk maps the measurement/observation zk to the Kalman filter state xk. Each of the three different kinds of measurements (Doppler-based speed, location-based speed, step count-based cadence) is associated with its own Hk. If xk is expressed as a column vector [s m n] (k), then: <MAT> <MAT> Thus, Equations <NUM> and <NUM> cause the respective measured/observed speed to be mapped directly to the speed s of state xk.

For the cadence measurement (or, as discussed below, an average cadence determined from the cadence measurement), Hk is more complex. When the calculated step length is in the range of the gait model that has a non-zero slope (e.g., region 262A or 264A of <FIG>), the following equations hold true: <MAT> <MAT> <MAT>.

In this case, the observation function is quadratic: <MAT>.

To simplify the solution of Equation <NUM>, an approximation may be made by taking the gradient of h(s,m,n) at x̂k|k (i.e., a Taylor series around the most recent state estimation): <MAT> <MAT> <MAT> <MAT>.

For Equations <NUM> through <NUM>, g is defined as: <MAT>.

When the calculated step length is instead in a range of the gait model that has zero slope (e.g., in region 262B, 262C, 264B, or 264C of <FIG>), step length is constant (csl) and cadence is: <MAT>.

In this scenario, the Hk(cadence) to map the cadence measurement to speed is simply: <MAT>.

To avoid instability (or cadence being stuck at a constant value) due to g or m approaching zero, both g and/or m may be constrained by lower bound values.

As noted above, in the process <NUM>, the observation noise vk has a normal distribution with a mean of zero and a covariance of Rk. As seen from Equations <NUM> and <NUM>, the covariance Rk is used to calculate the Kalman filter gain Kk. Moreover, as seen from Equations <NUM> and <NUM>, a larger covariance Rk results in a smaller Kalman filter gain Kk. Thus, a noisier observation generally causes the observation to have less effect on the state.

The value of Rk may reflect a different amount of uncertainty for each of the three types of observations in the process <NUM> (i.e., Doppler-based speed, location-based speed, and step count-based cadence). For the Doppler-based speed, the activity tracking application may set Rk(Doppler) to a fixed covariance value (e.g., <NUM><NUM>/s<NUM>) that makes certain assumptions about the level of measurement noise. In other implementations, the source of the Doppler-derived speed (e.g., movement detection unit <NUM> of <FIG>, GNSS unit <NUM> of <FIG>, or GNSS unit <NUM> of <FIG>) may provide Rk(Doppler), either as a fixed or dynamically changing value. In one implementation, Rk(Doppler) may be set equal to (or otherwise derived from) the variance observed in Doppler-derived speed samples over some period of time (e.g., the most recent <NUM> seconds), with the variance being measured and/or calculated by the activity tracking application and/or the source of the Doppler-derived speed.

For the location-based speed, the activity tracking application may calculate Rk(location) based on variances in the location ( <MAT> for a first dimension and <MAT> for a second dimension). For example, for locations l<NUM> and l<NUM>, measured across a time differential dt, the speed may be calculated as <MAT>, and Rk(location) may be approximated as: <MAT>.

In Equation <NUM>, cf<NUM>is a correlation factor, which is indicative of the strength of correlations between the GNSS location measurements l<NUM> and l<NUM> (e.g., where the locations are offset from the true locations in a consistent direction and by a consistent amount). In some implementations, l<NUM> and l<NUM> are not adjacent measurements, but instead are separated by some predetermined amount of time (e.g., <NUM> seconds). This may generally reduce the amount of observation noise corresponding to the location-derived speed measurements. The activity tracking application may set the correlation factor to a fixed value (e.g., <NUM>), or the source of the location-derived speed (e.g., movement detection unit <NUM> of <FIG>, GNSS unit <NUM> of <FIG>, or GNSS unit <NUM> of <FIG>) may provide the correlation factor, either as a fixed or dynamically changing value. Also in Equation <NUM>, uf is a path uncertainty factor, which reflects the fact that it becomes less and less likely that the user took a straight path between two locations as those locations become further apart. The activity tracking application may set or calculate the path uncertainty factor based on the distance between locations, or the source of the location-derived speed (e.g., movement detection unit <NUM> of <FIG>, GNSS unit <NUM> of <FIG>, or GNSS unit <NUM> of <FIG>) may provide the path uncertainty factor as a fixed or dynamically changing value.

For the cadence, the activity tracking application may assume that the step counter (from which cadence is derived) is highly accurate and reliable, with the worst case scenario being that the step counter misses the first and last step of a given time interval. Under this assumption, the activity tracking application may calculate Rk(cadence) as: <MAT>.

In other implementations, the activity tracking application may receive values of Rk(cadence) from the source of the step counter measurements (e.g., movement detection unit <NUM> of <FIG>, step counter unit <NUM> of <FIG>, or step counter unit <NUM> of <FIG>), as a fixed or dynamically changing value.

As was also noted above, in the process <NUM>, the process noise wk has a normal distribution with a mean of zero and a covariance of Qk. Qk reflects the uncertainty of the state estimation, and is used in the custom Kalman filter to control how much the state changes from the previous update. Generally, when Qk is smaller there is greater confidence as to the state estimation, and the state is updated more as a result of a new measurement. Conversely, when Qk is larger there is less confidence as to the state estimation, and the state is updated less as a result of a new measurement. Generally, a smaller Qk helps smooth the noise from the GNSS measurements but makes the state less responsive to actual changes in user speed, while a larger Qk provides less smoothing but makes the state more responsive to actual changes in user speed (i.e., allows the state estimate to converge to a the new speed more quickly).

In the example process <NUM>, the process noise covariance is defined as follows: <MAT> <MAT> <MAT> <MAT>.

One or more of the values accS, accM, and accN may be dynamically set based on various factors. In the example process <NUM>, the value accS has a nominal value, but is set to a higher value if a stop has been detected or if a large and sudden speed change is detected. In one implementation, for example, accS is increased from a nominal value of <NUM>/s<NUM> to a value of <NUM>/s<NUM> if a stop was recently detected (for a predetermined amount of time, e.g., <NUM> seconds, <NUM> seconds, etc.), and is instead increased from the nominal value of <NUM>/s<NUM> to a value of <NUM>/s<NUM> if a large and sudden speed change is detected (e.g., only while the large speed change is occurring, or for some slightly longer period, etc.). In addition, or alternatively, accS may be set to a higher value (e.g., <NUM>/s<NUM>) when a user has just started tracking activity (e.g., upon a "cold start"), and for some predetermined amount of time thereafter (e.g., <NUM> seconds), before decreasing to the nominal value. Techniques for detecting stops and large speed changes are discussed in further detail below with reference to <FIG>.

Also in the example process <NUM>, the value accM has a nominal value, but is set to a new value if the cadence is zero (or, in some implementations, if the cadence is below a low, predetermined threshold). For example, accM may have a nominal value of (<NUM>/<NUM>) during normal operation, but be lowered to zero if the cadence falls below a predetermined threshold. In one implementation, the value accN is a function of accM and/or the cadence. For example, accN may be set equal to the product of accM and the measured (or average cadence).

Referring again now to the data flow diagram shown in <FIG>, it is seen that GNSS data <NUM> and step counter data <NUM> are provided as inputs to the process <NUM>. The GNSS data <NUM> and step counter data <NUM> may include new observations/measurements each time interval (e.g., for each increment in the value of k in the discussion above). In some implementations, the process <NUM> is also designed to handle situations where some or all observations are missing for one or more time intervals, and/or where extra observations are made available. GNSS data <NUM> may be provided by a device or component such as GNSS unit <NUM> of <FIG> or GNSS unit <NUM> of <FIG>, and step counter data <NUM> may be provided by a device or component such as step counter unit <NUM> of <FIG> or step counter unit <NUM> of <FIG>, for example.

GNSS data <NUM> includes data indicative of two independent speed measurements: a first speed derived from Doppler shifts of GNSS signals, and a second speed derived from GNSS location displacements (e.g., distances between successive GNSS locations). Step counter data <NUM> includes data indicative of a number of steps taken by the user (e.g., a cumulative number of steps since a last measurement interval). At a process stage <NUM>, the Doppler-derived speeds of GNSS data <NUM> are converted to a Doppler speed <NUM>, which is added to speeds in a first queue of observation queues <NUM>. At a process stage <NUM>, the location-derived speeds of GNSS data <NUM> are converted to a location displacement speed <NUM>, which is added to speeds in a second queue of observation queues <NUM>. At a process stage <NUM>, the step counter data <NUM> is converted to a cadence <NUM>, which is added to cadences in a third queue of observation queues <NUM>. Observation queues <NUM> generally retain a history of recent speed and cadence information, which can be used to identify times when it is likely that the user has quickly and substantially changed his or her speed (as discussed further below).

In some implementations, GNSS data <NUM> provides raw data (e.g., Doppler shift information and/or locations or location displacements), in which case process stage <NUM> and/or process stage <NUM> may perform the calculations needed to determine speed values. In other implementations, GNSS data <NUM> already includes the Doppler-derived and location-derived speed values. Process stage <NUM> may convert step counter data <NUM> into cadence values by dividing the number of steps in a predetermined time interval by the length of that time interval, for example. In implementations where step counter data <NUM> only includes an indication of each new step without a cumulative count (which can be viewed as "counting" up to one, with the count being reset to zero after each detected step), process stage <NUM> may also determine the cumulative step counts over the predetermined time interval. One, some, or all of process stages <NUM>, <NUM>, <NUM> may also, or instead, convert the received data into a format that is more amenable to later processing in the process <NUM>.

At a process stage <NUM>, the time of a last observed "large" speed change by the user is identified based on the Doppler speeds and/or location displacement speeds in observation queues <NUM>. For example, both a mean and a standard deviation of Doppler speed measurements may be calculated based on the last i time intervals (e.g., the last <NUM> intervals, <NUM> intervals, etc.), and process stage <NUM> may detect when a new Doppler speed measurement (or an average of a certain number of the most recent measurements, etc.) is at least some threshold amount away from the mean (e.g., at least two standard deviations away from the mean, etc.). In some implementations, process stage <NUM> independently identifies the speed changes based on the queued Doppler speeds and the queued location displacement speeds in this manner, and only indicates a "valid" speed change if both sources indicate such a change. In other implementations, process stage <NUM> jointly applies an algorithm to both of these sources of queued data to determine when such a speed change occurs, only looks at one of these source of queued data, and/or additionally bases the determination of the time of the last large speed change on queued cadence data.

At a process stage <NUM>, the time of a last stop by the user is identified based on the cadences in observation queues <NUM>. For example, it may be determined that the user "stopped" only if there are zero steps (or less than a threshold number of steps, etc.) counted in the most recent time interval. In some implementations, other information is also, or instead, used to determine whether the user has stopped. For example, the process stage <NUM> may determine the user has stopped only if the most recent Doppler speed, location displacement speed, and cadences in observation queues <NUM> (or a certain number of the most recent values, etc.) all confirm that the user has stopped. In one implementation where the step counter cannot or does not wake up the activity tracking application (or the portion of the activity tracking application responsible for detecting stops), and where the step counter is only able to provide a report when the step count changes and some other trigger has woken the activity tracking application, stops are detected when both (<NUM>) the step counter has not provided an update for at least some threshold amount of time (e.g., <NUM> seconds) and (<NUM>) at least one of the GNSS Doppler speed and the GNSS location speed is below some threshold level (e.g., <NUM>/s). The latter condition may be useful in preventing "false positives" (i.e., detected stops which did not actually occur), which are generally much more costly than false negatives in terms of estimation error.

At process stage <NUM>, an average cadence is calculated based on cadence values in observation queues <NUM>. In one implementation, the cadence is averaged over a predetermined window of time (e.g., <NUM> seconds), but not extending past the time of the last "large" speed change as detected by process stage <NUM>, and not extending past the time of the last stop as detected by process stage <NUM>. Put differently, the averaging window for the cadence may be set to a nominal time value or number of time intervals, but may be bounded at the upper end by the lesser of (<NUM>) the time since the last large speed change, and (<NUM>) the time since the last stop. This bounded averaging technique may help to prevent a skewed average cadence in the time periods immediately following a stop and/or a large speed change. In other implementations, the time averaging window is bounded in another manner (e.g., only by the time since the last stop), or is simply fixed at the nominal value.

Various parameters of the Kalman filter system model are shown in <FIG> as reference numbers <NUM>, <NUM> or <NUM>. Specifically, model parameter <NUM> represents the Kalman filter state transition model F, model parameters <NUM> represent the observation model H, the observation residual dz, and the observation noise covariance R, and model parameter <NUM> represents the process noise covariance Q. These parameters correspond to the parameters included in Equations <NUM> through <NUM> above (with subscripts k or k-<NUM> in Equations <NUM> through <NUM> to indicate relative time intervals).

As noted above, the state transition model F (model parameter <NUM>) is fixed in the example process <NUM>. The parameters H, dz, and R (model parameters <NUM>), on the other hand, can be affected by new observations/measurements, as is reflected in the above equations and the arrows from Doppler speed <NUM>, location displacement speed <NUM>, and average cadence <NUM> to model parameters <NUM> in <FIG>. As was also noted above, the process noise covariance Q (model parameter <NUM>) may normally be kept at a relatively low nominal value, but may be changed to higher values if a stop was recently detected or a large speed change is observed. In <FIG>, this is reflected by the arrows from process stage <NUM> and process stage <NUM> to model parameter <NUM>. In some implementations, process stage <NUM> can distinguish between two or more levels of "large" speed changes (e.g., one to two standard deviations from the mean corresponding to a first level of speed change, two to three standard deviations from the mean corresponding to a second level of speed change, etc.), and the model parameter <NUM> is set to a respective value based on the identified level of the speed change. The Kalman filter states are estimated at a process stage <NUM>, based on the model parameters <NUM>, <NUM>, and <NUM>, and as reflected in the equations above.

The techniques described herein (e.g., in connection with system <NUM> of <FIG>, system <NUM> of <FIG>, system <NUM> of <FIG>, and/or process <NUM> of <FIG>) may, depending upon the specific implementation, be used to output information such as real-time, instantaneous speed, step length, and/or other information. For example, one or more of the states that are continuously updated by the process <NUM>, and/or by the Kalman filter <NUM> of <FIG>, the Kalman filter <NUM> of <FIG>, or the Kalman filter <NUM> of <FIG>, may be displayed to the user. Additionally, or alternatively, one or more parameters derived from one or more of those states may be displayed in real time. It is understood that, as used herein, the term "instantaneous" may be used to refer to parameters (e.g., speed) that are not precisely instantaneous, but rather involve some relatively small amount of averaging. For example, some averaging may be inherent to the techniques described herein if the GNSS speeds that are input to the Kalman filter are the product of smoothing techniques. Moreover, in some implementations, the techniques described herein themselves add some amount of smoothing or averaging (e.g., in the process <NUM> of <FIG>, due to the averaging of the cadence at process stage <NUM>, and/or if the GNSS speeds in observation queues <NUM> are averaged over a short time window prior to being input to the Kalman filter, etc.).

The real-time speed and/or other parameters may be displayed to the user while he or she is walking/running. For example, the activity tracking application may cause a user interface such as user interface <NUM> of <FIG>, user interface <NUM> of <FIG>, or user interface <NUM> (and/or user interface <NUM>) of <FIG> to display the real-time parameter(s) to the user. In addition, or alternatively, speeds, gait model parameters, and/or other parameters that are continuously updated as Kalman filter states (and/or parameters derived therefrom) may be stored in a memory (e.g., memory <NUM> of <FIG>, memory <NUM> and/or performance database <NUM> of <FIG>, or memory <NUM>, memory <NUM>, and/or performance database <NUM> of <FIG>) for later presentation (e.g., after the run/walk is completed and uploaded to server <NUM> of <FIG> or server <NUM> of <FIG>, if the user has expressly agreed to share his or her data). As one example, if the user has expressly agreed to share his or her data, a server such as server <NUM> of <FIG> or server <NUM> of <FIG> may receive the data from a mobile computing device (e.g., mobile computing device <NUM> of <FIG> or mobile computing device <NUM> of <FIG>) in response to the user selecting an interactive "upload" control provided by an activity tracking application (e.g., activity tracking application <NUM> of <FIG> or activity tracking application <NUM> of <FIG>). Thereafter, the server may process the data into a format suitable for presentation on a graphical user interface (GUI), which the user can access by using a web browser application or a dedicated application at a different computing device (e.g., after entering a login and password).

An example presentation that may be generated, including three displays <NUM>, <NUM>, and <NUM>, is shown in <FIG>. The first display <NUM> plots the user's pace <NUM> (in minutes per mile) versus time over the course of an approximately <NUM> minute run, with breaks/rests around the eighth and thirteenth minutes. The pace <NUM> may be equal to (or derived from, e.g., the inverse of) a speed estimate that is a state of the Kalman filter in the process <NUM> at a number of different times, for example. Also seen in the display <NUM> is a GNSS pace <NUM>, which may be equal to (or derived from) the Doppler-based GNSS speed or the location-based GNSS speed (or an average of the two, etc.), for example. The GNSS pace <NUM> may be omitted, and is shown here primarily to illustrate the potential improvement in noise level that the custom Kalman filter may provide, as well as the potential improvement in responsiveness (e.g., as seen by the steeper negative or positive slope when the user stops or starts).

The second display <NUM> in <FIG> plots both the user's cadence <NUM> (in steps per second) and the user's step length <NUM> (in meters per step) versus time over the course of the run/walk. The cadence <NUM> may be values of the average cadence calculated at process stage <NUM> of the process <NUM> at a number of different times, and the step length <NUM> may be calculated from values of the gait model parameters of the Kalman filter states (e.g., slope and intercept in the process <NUM>) at a number of different times, and from the average cadence at those times, for example.

The third display <NUM> plots the user's gait model. The gait model <NUM> (a single line) may represent at least a portion of the user's average gait model (e.g., the average slope and intercept) over the course of the run/walk, and the numerous gait models <NUM> may represent the instantaneous gait model (or a portion thereof) at each of a number of different times within the run/walk. The gait models <NUM> may be plotted using the values of the slope and intercept states of the Kalman filter (in the process <NUM>), as updated by the Kalman filter at a number of different times, for example. In some implementations where each user is associated with both a walking and a running gait model, the third display <NUM> may correspond to just the walking gait model, and a fourth display may show the user's running gait model (or the third display <NUM> may additionally show the running gait model, or the user may select which gait model is shown, etc.).

The display of accurate, instantaneous gait characteristics such as cadence and step length over time (display <NUM>), and/or the display of a model such as the user's cadence versus the user's step length (display <NUM>), may help the user to modify his or her gait in the future for improved running performance. Conventional approaches do not allow such displays (at least, step length versus time and the gait model versus time) to be presented with a comparable level of accuracy. It is understood that different units and/or inverse metrics may be used, such as minutes/kilometers for speed or pace (e.g., kilometers per hour, kilometers per minute, minutes per kilometer, etc.). Similarly, cadence and step length may be shown using different units and/or inverse metrics (e.g., step period instead of cadence).

An example method <NUM> for accurately estimating gait characteristics of a user, according to one implementation, is shown in <FIG>. The method <NUM> may be implemented as instructions stored on a computer-readable medium and executed by one or more processors of a computing device. With reference to <FIG>, the method <NUM> may be implemented by activity tracking application <NUM>, by activity tracking application <NUM>, or by activity tracking application <NUM>, for example.

At block <NUM>, a first plurality of parameters is monitored over time. Each of the first plurality of parameters is indicative of movement of the user. The first parameters include a first GNSS-derived speed (e.g., a speed determined using GNSS location or GNSS Doppler shift) of the user and a step count of the user. The monitored step count may be a cumulative count, or may simply be an indication of each new step (which can be accumulated later, e.g., at block <NUM>). In some implementations, one or more other parameters may also be monitored. In one implementation, for example, the first parameters include (or consist entirely of) a first speed that is determined using GNSS location, a second speed that is determined using GNSS Doppler shift, and a step count.

The first parameters may be monitored by receiving values of those parameters from external devices and/or from components integrated in the computing device implementing the method <NUM>. In implementations where the computing device is a mobile computing device (e.g., a smartphone or smart watch), for example, block <NUM> may include receiving real-time data generated by one or more devices external to the mobile computing device (e.g., a device mounted on or near the foot), and/or receiving real-time data generated by one or more components of the mobile computing device (e.g., a GNSS unit and/or an accelerometer). As another example, in implementations where the computing device is a server remote from the user and the user has expressly agreed to share his or her data, block <NUM> may include receiving over a network (e.g., network <NUM> of <FIG> or network <NUM> of <FIG>) real-time data generated by one or more mobile computing devices carried by the user (e.g., a smart phone and/or smart watch).

At block <NUM>, values of the monitored first plurality of parameters are processed to determine values of a second plurality of parameters. Each of the second plurality of parameters is also indicative of movement of the user. The processing at block <NUM> includes applying, as inputs to an estimator (e.g., a Kalman filter), values of at least one of the monitored first parameters and/or values of at least one parameter that is derived from one or more of the monitored first parameters. The estimator states include the second parameters whose values are determined at block <NUM>. That is, the values of the second parameters are determined via the estimation/updates provided by the estimator.

In one implementation, the second parameters include at least two parameters that are collectively indicative of a mapping between step frequency (cadence) of the user and step length of the user. For example, the second parameters may include a slope of a line representing the mapping between step frequency and step length of the user, and also an x-or y- intercept of that line. The second parameters may also, or instead, include a speed of the user, and/or one or more other parameters.

In certain implementations where the estimator is a Kalman filter, the processing at block <NUM> is performed partially or wholly in accordance with any one of the implementations of process <NUM> as discussed above in connection with <FIG>. Thus, for example, the processing at block <NUM> may include predicting, at each of a plurality of time intervals, that values of the Kalman filter states are unchanged from respective values of the Kalman filter states at a most recent time interval, and/or dynamically setting values of a process noise covariance (Q) used by the Kalman filter. Moreover, dynamically setting values of the process noise covariance may include increasing the process noise covariance when at least the step count of the user indicates the user has stopped, and/or increasing the process noise covariance when at least the first GNSS-derived speed of the user indicates the user has accelerated or decelerated (and thus, increased/decreased speed) by more than a threshold amount. As another example, the processing at block <NUM> may include determining an average cadence over a window of time intervals, where the upper window length is bounded by the minimum of (<NUM>) a predetermined maximum window length, (<NUM>) a time since the last user stop was detected, and/or (<NUM>) a time since the last "large" user speed change (e.g., of at least some threshold amount) was detected.

At block <NUM>, a GUI (presented by the computing device implementing the method <NUM>, or by another computing device) is caused to display values of at least one of the second parameters and/or at least one parameter that is derived from one or more of the second parameters. The GUI may include a visual representation of the mapping between the user's step frequency and step length, and/or the user's instantaneous speed, for example. Other examples include average speed (as calculated using the current, instantaneous speed), current and/or average step length, and so on. In one implementation where the computing device implementing the method <NUM> is a mobile computing device (e.g., a smartphone or smart watch), for example, block <NUM> may include causing a GUI on a display of the mobile computing device to display the appropriate values. In some implementations where the computing device is instead a server remote from the user, and the user has expressly agreed to share his or her data, block <NUM> may include transmitting, via a wireless network (e.g., network <NUM> of <FIG> or network <NUM> of <FIG>), data indicative of values of the second parameters (and/or data indicative of values of one or more parameters derived from the second parameters) to a mobile computing device of the user (e.g., a smartphone or smart watch) to cause a GUI of the mobile computing device to display the appropriate values.

The ordering of blocks shown in <FIG> does not necessarily mean that the blocks are performed strictly in that order. For example, in a real-time implementation, parameters may continue to be monitored at block <NUM> while earlier values of those parameters are processed at block <NUM> and/or while values are displayed at block <NUM>. Moreover, the method <NUM> may include one or more additional blocks not shown in <FIG>. For example, the method <NUM> may include an additional block, prior to block <NUM>, at which a gait model (corresponding to a current gait type of the user) is selected from among a plurality of gait models (e.g., a running gait model and a walking gait model, as discussed above in connection with <FIG>). In one such implementation, the mapping between step frequency and step length (discussed above in connection with block <NUM>) is specific to the selected gait model. Moreover, values of that mapping, as output by the estimator, may be used to update the selected gait model (e.g., in real-time).

In some implementations, block <NUM> is omitted from the method <NUM>. For example, the method <NUM> may instead include an additional block (not shown in <FIG>) at which the second parameters are processed only for purposes other than display (e.g., to generate automated text-based suggestions to a particular user, or to automatically determine a race seeding for a particular user, etc.).

Although the foregoing text sets forth a detailed description of numerous different aspects and embodiments of the invention, it should be understood that the scope of the patent is defined by the words of the claims set forth at the end of this patent.

The following additional considerations apply to the foregoing discussion.

Unless specifically stated otherwise, discussions in the present disclosure using words such as "processing," "computing," "calculating," "determining," "presenting," "displaying," or the like may refer to actions or processes of a machine (e.g., a computer) that manipulates or transforms data represented as physical (e.g., electronic, magnetic, or optical) quantities within one or more memories (e.g., volatile memory, non-volatile memory, or a combination thereof), registers, or other machine components that receive, store, transmit, or display information.

As used in the present disclosure any reference to "one implementation" or "an implementation" means that a particular element, feature, structure, or characteristic described in connection with the implementation is included in at least one implementation or embodiment. The appearances of the phrase "in one implementation" in various places in the specification are not necessarily all referring to the same implementation.

Claim 1:
A method, implemented in a computing device, for accurately estimating gait characteristics of a user, the method comprising:
monitoring a first plurality of parameters indicative of movement of the user,
wherein monitoring the first plurality of parameters includes monitoring (i) a first GNSS-derived speed of the user and (ii) a step count of the user;
processing values of the monitored first plurality of parameters to determine values of a second plurality of parameters indicative of movement of the user, wherein
processing values of the monitored first plurality of parameters includes applying, as inputs to an estimator having the second plurality of parameters as estimator states, one or both of (i) values of at least one of the monitored first plurality of parameters, and (ii) values of at least one parameter derived from one or more of the monitored first plurality of parameters and predicting, at each of a plurality of time intervals, that values of the estimator states are unchanged from respective values of the estimator states at a most recent time interval, wherein the estimator is a Kalman filter, a non-linear estimator or a particle filter,
and
at least two parameters of the second plurality of parameters are collectively indicative of a mapping between step frequency of the user and step length of the user, wherein the mapping includes (i) a slope of a line representing the mapping between step frequency of the user and step length of the user, and (ii) an intercept of the line representing the mapping between step frequency of the user and step length of the user; and
causing a graphical user interface of the computing device or another computing device to display values of one or both of (i) at least one of the second plurality of parameters, and (ii) at least one parameter derived from one or more of the second plurality of parameters.