Abstract:
Performing dead reckoning navigation for persons on foot with improved accuracy. Accelerometers in a navigation device are used to deduce when abnormal steps are being taken and modify navigation calculations accordingly. Running and walking sideways or backwards are among the situations which can be detected and compensated. One embodiment of the invention is a pedometer which is attached to the user&#39;s waist or torso. Various correlations are used to distinguish between running versus walking, forward steps versus backward steps, left turn versus right turn, and the slope of the terrain being traveled. Various algorithms are used to distinguish between such motions and accurately track the distance and direction traveled.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS  
       [0001]    This non-provisional United States (U.S.) patent application claims the benefit of U.S. Provisional Application No. 60/399,912 filed on Jul. 31, 2002 by inventors Robert W. Levi and Robert R. Marshall, titled “Navigation Device for Personnel on Foot.” 
     
    
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT  
       [0002] This invention was originated as part of a Federally sponsored Small Business Innovation Research (SBIR) project, contract number DAMD17-99-C-9028. The contractor is Point Research Corporation, 17150 Newhope Street, Suite 709, Fountain Valley, Calif. 92708. Patent rights for this invention are subject to the Federal Acquisition Regulations (FAR) paragraph 52.227-20—Rights in Data—SBIR Program, and DFARS 252.227-7018 Rights in Noncommercial Technical Data and Computer Software—Small Business Innovation Research (SBIR). 
     
    
     
       FIELD  
         [0003]    Various embodiments of the invention pertain to navigation systems. More particularly, at least one embodiment of the invention relates to a device, system, and method for dead reckoning navigation for a person on foot.  
         DESCRIPTION OF RELATED ART  
         [0004]    A pedometer is a device for counting footsteps and has been in use for some time to assist in determining distance traveled by persons on foot. The usefulness of a pedometer depends on knowing the length of each footstep, or the “stride”, and the assumption that the direction of travel is straight ahead. A person&#39;s walk or stride typically varies in response to a number of circumstances, including, but not limited to, walking sideways or backwards, and going uphill or downhill. Stride changes even more drastically if a person runs instead of walks.  
           [0005]    If a pedometer is used in conjunction with a device to determine direction of travel, such as a magnetic compass, navigation by dead reckoning is possible. For example, the system described in U.S. Pat. No. 5,583,776 uses stride data from a pedometer combined with compass data. However, that device does not compensate for non-forward walking motions.  
           [0006]    Dead reckoning permits knowing the user&#39;s location with respect to some known reference, such as his starting point. When determining position of the user by dead reckoning techniques, unusual walking motions introduce errors if a person steps sideways or backwards as, for example, a soldier may need to do to evade an enemy or obstacle. In these cases, the direction of travel may differ from the direction the user is facing, which is the direction that would be reported by a compass attached to the person&#39;s torso.  
           [0007]    Thus, prior art dead reckoning systems typically fail to accurately account for non-forward walking motions and changes in stride length.  
           [0008]    U.S. Pat. Nos. 6,305,221 and 6,301,964 describe dead reckoning navigations systems and methods in which accelerometers are mounted on the user&#39;s foot or leg. It is theoretically possible to measure a user&#39;s motion directly by double integration of acceleration with time, but currently available accelerometers severely limit the accuracy of this method when the accelerometers are mounted on or near a user&#39;s waist. Where the information to be integrated is much smaller than gravity, typical accelerometer components are distorted by gait rotations and other sources of noise. This is the reason prior art dead reckoning navigation systems specify mounting the accelerometers on a user&#39;s foot or extremities, where the acceleration magnitudes are greater.  
           [0009]    However, mounting the accelerometers around a user&#39;s foot or extremities, and the need to communicate results from the accelerometers by wire or radio transmission methods, is subject to other sources of error, is less convenient, potentially more expensive and sometimes impractical.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0010]    [0010]FIG. 1 is a block diagram illustrating a dead reckoning navigation device according to an embodiment of the invention.  
         [0011]    [0011]FIG. 2 is a flow diagram illustrating a method for determining the occurrence of sideways or transverse steps according to one aspect of an embodiment of the invention.  
         [0012]    [0012]FIG. 3 is a flow diagram illustrating a method for determining the direction of a transverse or sideways step according to one embodiment of the invention.  
         [0013]    [0013]FIG. 4 is a block diagram illustrating a method for utilizing the correlation between the square of the forward acceleration and the product of forward and vertical accelerations to deduce forward versus backward motion.  
         [0014]    [0014]FIGS. 5 and 6 are graphs illustrating accelerations and deduced directions according to one implementation of the invention.  
         [0015]    [0015]FIG. 7 is a flow diagram illustrating a method for invention distinguishes between running or jogging versus walking according to one aspect an embodiment of the invention.  
         [0016]    [0016]FIGS. 8 and 9 are trajectory graphs illustrating the difference in navigation with and without a running compensation algorithm.  
     
    
     DETAILED DESCRIPTION  
       [0017]    In the following description numerous specific details are set forth in order to provide a thorough understanding of the invention. However, one skilled in the art would recognize that the invention may be practiced without these specific details. In other instances, well known methods, procedures, and/or components have not been described in detail so as not to unnecessarily obscure aspects of the invention.  
         [0018]    A first aspect of an embodiment of the invention improves the accuracy and usefulness of dead reckoning navigation for a person on foot by exploiting additional information from accelerometers provided for leveling and step determination. The additional information permits deducing a variety of walking motions and adjusting dead reckoning navigation calculations to improve the accuracy of the navigation.  
         [0019]    A second aspect of an embodiment of the invention also anticipates using altitude data from a barometric altimeter as part of the calculations to estimate variations in stride when walking uphill, downhill or on stairs.  
         [0020]    One implementation of the invention provides an electronic dead reckoning device that can be mounted on the user&#39;s waist. The electronic dead reckoning device contains sensors for measuring the direction that the user is facing, in addition to sensors for measuring acceleration in three orthogonal axes. Since the earth&#39;s magnetic field is not generally horizontal, but the direction of magnetic north is the component of that field in the horizontal plane, accelerometers, which also respond to gravity, are included to determine and/or correct for tilting.  
         [0021]    The same accelerometers can also serve to implement the navigation functions of a pedometer. Generally, data available from the accelerometers is used by a novel algorithm to deduce non-forward walking and improve the accuracy of personal dead reckoning positioning by estimating changes in the length and/or relative direction of the user&#39;s stride.  
         [0022]    [0022]FIG. 1 is a block diagram illustrating a dead reckoning navigation device  100  according to an embodiment of the invention. Three accelerometers are employed, with sensitive axes oriented horizontally in the direction of normal walking (forward)  102 , horizontally perpendicular to the forward direction (transverse)  104 , and vertically  106 , respectively. Each accelerometer produces an electrical signal proportional to the acceleration being experienced along its axis. The accelerometers  102 ,  104 , and  106  are communicatively coupled to a processing unit  108  that has timing capabilities which can be used to measure elapsed time intervals. In one implementation of the invention, a barometric altimeter  110  permits measuring changes in elevation during relatively brief intervals.  
         [0023]    According to one implementation of the invention, the navigation device  100  is design to mount the accelerometers on, around, or near the user&#39;s trunk or waist and above the legs.  
         [0024]    A nominal or average stride length that represents the user&#39;s stride under normal walking conditions is determined for the particular user by means not a part of this invention and supplied to the processing unit  108 . There are two stride parameters referenced in this invention. The nominal or average stride and a modified stride used to calculate distance traveled for a particular step. According to one aspect of the invention, ratios are applied by the processing unit to adjust stride length on a step-by-step basis. That is, the processing unit deduces the type of step that has been taken by a user and applies a scaling multiplier to estimate the correct distance traveled.  
         [0025]    According to an embodiment of the invention, the grade or slope of the terrain being walked on can be determined by dividing the change in elevation, as measured by the barometric altimeter  110 , by the number of steps to accomplish the elevation change multiplied by the nominal stride. This calculation may be used to select a ratio by which to, for example, reduce the nominal stride for dead reckoning calculations when walking uphill or increase the nominal stride when walking downhill.  
         [0026]    According to an embodiment of the invention, accelerometer signals are subjected to high-pass filtering to remove frequencies which do not contain useful information and might interfere with processing, and also low-pass filtering to remove the constant portion of the acceleration of gravity. Although the acceleration of gravity is constant, its component parallel to a particular accelerometer axis may be changed by rotations during walking. These changes are not filtered out. These two filtering processes are equivalent to a band-pass filter which is relatively wide. That is, the ratio of upper cutoff frequency to lower cutoff frequency is large. For the remainder of this description of the invention, “accelerometer signal” shall refer to a signal filtered as described herein. However, unfiltered signals may also be use without deviating from the invention.  
         [0027]    The filtered signal from the vertical accelerometer  106  is processed to identify the instance of a footstep. One method for doing this is to recognize a maximum (peak) acceleration by the fact that accelerations decline afterwards. Another method is to respond to a “zero-crossing,” a moment when the direction of acceleration reverses. Because the signal from the vertical accelerometer is subject to bandpass filtering, and the DC component has been removed, there is always at least one zero-crossing per step. Since there can be multiple peaks as well as zero crossings per step, some form of reset mechanism is needed to assure that only the first event is recognized. In identifying peaks, a zero crossing can be required before another peak is recognized. Similarly another peak may be required to enable recognizing another zero crossing. It is not necessary that this detection occur at some specific point during the sequence of a step, but it may occur at the same point during each step so that the interval between two successive steps is a useful measure of the time required to complete the step.  
         [0028]    [0028]FIG. 2 is a flow diagram illustrating a method for determining the occurrence of sideways steps according to one embodiment of the invention. A sideways step can be deduced through an analysis of the forward acceleration  102  and transverse acceleration  104 . The forward axis accelerometer  102  and transverse axis accelerometer  104  are monitored  202 , for example, by the processing unit  108 . Each acceleration signal is squared  204  to produce a variance which is then passed through a low-pass filter  206 . During the step, the two filtered variances are compared  208 . If the transverse variance exceeds a threshold determined by applying an empirically-determined scale factor to the forward variance, a sideways step is deduced. Otherwise, a forward step is assumed  214 .  
         [0029]    [0029]FIG. 3 is a flow diagram illustrating a method for determining the direction of a transverse or sideways step according to one embodiment of the invention. The transverse accelerometer signal is continuously monitored  302  to track whether if is increasing more often than decreasing, or vice versa  304 . When walking sideways toward the right, a person&#39;s acceleration is rightward for a longer portion of the step than it is leftward. The leftward acceleration may have a greater magnitude, but it occurs during a shorter proportion of the step. Correspondingly, leftward acceleration dominates when moving leftward. Consequently, the transverse accelerometer signal is continuously monitored  302  to track whether it is increasing more often than decreasing or vice versa  304 . In one implementation, this is done by creating a signal which has a positive but constant value when the acceleration is increasing, and a constant negative value of the same magnitude when decreasing. After suitable low-pass filtering, this signal can be used to determine whether the motion was in the direction of positive acceleration (as determined by the properties of the accelerometer) or the other direction. Note that this determination of sideways motion may be done as described in the preceding paragraph.  
         [0030]    At the moment of step detection deduce whether there was a sideways step  306 ,  308 . If no sideways step is detected, then do nothing  310 . Otherwise, if a sideways step is detected, the filtered signal may be used to determine whether the step is rightward or leftward  312 .  
         [0031]    If a sideways step is deduced, the direction of travel for dead reckoning calculations is rotated one-quarter turn in the appropriate direction, i.e., ninety (90) degrees,  314  and the nominal stride length is reduced by an empirically-determined ratio  316 .  
         [0032]    [0032]FIG. 4 is a block diagram illustrating a method for utilizing the correlation between the square of the forward acceleration and the product of forward and vertical accelerations to deduce forward versus backward motion. A significant correlation has been observed between the square of the forward acceleration (variance) and the product of forward and vertical accelerations (covariance) when a user is walking forward. This correlation is much weaker when walking backwards and is the basis for deducing backwards walking. This correlation may be employed by monitoring the forward and vertical accelerations to obtain instantaneous values for each signal  402 . A forward variance is calculated by taking the square of the forward acceleration signal  404 . A covariance is calculated by taking the product of the forward acceleration and vertical acceleration signals  406 . The instantaneous arithmetic difference between forward variance and forward-vertical covariance is then calculated  408 . In one implementation, the result of this calculation (variance minus covariance) may be subjected to low-pass filtering as described for variances above. If at the moment of step detection the resultant signal is smaller than a threshold  410 , implying little correlation, the step may be deduced to be backwards  414 . Otherwise, a forward step may be deduced  412 .  
         [0033]    According to one implementation of the invention, a step is deduced to be backward only if it is not first determined to be sideways, and the correlation described in the preceding paragraph is smaller than a threshold. If a backward step is deduced  410 ,  414 , the direction for dead reckoning calculations is reversed  416 , and the nominal stride length is reduced by an empirically-determined ratio  418 .  
         [0034]    [0034]FIGS. 5 and 6 are graphs illustrating accelerations and deduced directions from an actual test according to one implementation of the invention. FIG. 5 illustrates the recognition of sideways walking and, additionally, whether it is toward the left or right. FIG. 6 pertains to recognizing backward walking. Both figures are from the same data, which is a recording walking forward (seconds 0 through 10, approximately), then sideways toward the right (seconds 10 through 20), then backwards (seconds 20 through 28) then sideways toward the left (seconds 28 through the end).  
         [0035]    Three accelerometers were used to collect data. The signals from each of the three accelerometers is subjected to bandpass filtering to remove the DC component and extraneous peaks. After filtering, the signals from each of the two horizontal accelerometers are squared, to create the forward and rightward variances. These variance signals are then subjected to additional low-pass filtering. Additionally, the bandpass-filtered output of the transverse accelerometer is converted to one of two levels, a constant positive value if the acceleration had increased since the previous sampling, or a negative value of the same magnitude if the acceleration had decreased. This modified signal is then subjected to low-pass filtering. This method may be implemented by counting, separately, the number of samples during which the acceleration increases, and the number of samples during which it decreases, since the previous step.  
         [0036]    In FIG. 5, the difference between the low-pass filtered forward variance and the corresponding sideways variance is illustrated as the area between forward variance trace  500 , and the quantized and filtered sideways (rightward/leftward acceleration) trace  502 . Each dot represents the moment that a step (Forward, Rightward, Backward, and Leftward) is determined as described elsewhere. In addition, each dot indicates the direction (Forward, Rightward, Backward, and Leftward) of that step as determined by the methods described here. The amount by which sideways (rightward and/or leftward) variance (trace  502 ) exceeds the forward/backward variance (trace  500 ) when walking sideways is illustrated by the difference between trace  502  and trace  500 . When walking sideways, and only when walking sideways, the quantized and filtered sideways acceleration can be used to determine whether the step is towards the left or the right, as is apparent from trace  502  with the acceleration below the zero line for rightward movement and above the zero line for leftward movement.  
         [0037]    In one implementation, an additional signal is generated from the bandpass-filtered accelerations. The signals from the forward/backward and vertical accelerometers are added and then multiplied by the forward/backward acceleration. This is then subjected to low-pass filtering. FIG. 6 illustrates this filtered signal as trace  602 . This filtered signal  602  is then used to distinguish between forward walking and backward walking but only when it is determined that the subject is not walking sideways. The difference between sideways and forward/backward variances is also shown in this figure as trace  600 . When this difference is large, as it is when walking sideways, the signal shown in trace  602  is ignored.  
         [0038]    There are four distinct periods of stepping, and they are, in order, forward, rightward, backward, and leftward. As seen in the FIGS. 5 and 6, three of the fifty-four steps (at around the 2, 3, and 18 second marks) are classified as erroneous, and it is significant that these errors occur at the beginning or end of a series of steps.  
         [0039]    Mounting offset of the compass on the user&#39;s body would interfere with the processing since, when there is a significant offset, the accelerometer configured to be forward does not actually face forward, and the same is true of that configured to be rightward. If the device is mounted on the user such that it does not face perfectly forward as intended, this offset will distort the accelerations experienced by the forward/backward and transverse accelerometers, and this can invalidate the methods of the invention. It is necessary to determine and correct for such an offset. The offset if left uncompensated would compromise the generality of the advanced pedometry algorithms. Even fairly small body offsets can disrupt the validity of the various algorithms enough to increase erroneous identifications.  
         [0040]    By applying a coordinate transformation, the forward and rightward acceleration signals are rotated exactly by the current body offset. This produces the best results possible provided that the value for body offset is correct.  
         [0041]    [0041]FIG. 7 is a flow diagram illustrating a method for invention distinguishes between running or jogging versus walking according to one aspect an embodiment of the invention. Running or jogging may be deduced by estimating the amount of energy expended by the user to make the step. This may be accomplished by noting the “spread” of vertical acceleration, defined as the arithmetic difference between the maximum and minimum instantaneous vertical acceleration values, since the last step was identified  702 . At the moment of detection of a step, this spread is divided by the time elapsed since the previous step was identified  704 . If this quotient is greater than an empirically determined threshold  706 , the nominal stride is increased proportionally for purposes of dead reckoning calculations  708 . Otherwise do nothing  710 .  
         [0042]    In one implementation, whenever a sideways or backward step is detected, the dead reckoning update is done with a reduced stride as well as a rotated heading.  
         [0043]    The maximum and minimum of the band-pass-filtered vertical acceleration is maintained on a step-to-step basis. At the moment a step is detected, the difference between the maximum and minimum accelerations since the previous step is divided by the elapsed time since that step.  
         [0044]    The result is a “step energy estimate” which, if it exceeds a certain threshold, is used to increase the length of the stride for that step. This increase is proportional to the amount by which the energy estimate exceeds the threshold and is limited to doubling the stride at another, higher, predetermined value. The threshold distinguishes between walking and running. The difference between the doubling point and the threshold controls the amount of stride extension. Doubling the stride length has been determined to be adequate to describe a running stride for a person. In other implementations, other multiplier factors may be used without departing from the invention.  
         [0045]    [0045]FIGS. 8 and 9 are trajectory graphs illustrating the difference in navigation with and without a running compensation algorithm. FIGS. 8 and 9 show dead reckoning tracks with (FIG. 9) and without (FIG. 8) the running compensation algorithm of a test in which the subject walked north for one hundred (100) meters, then ran back to the starting point. The figures actually show the data for a single trial in which both sets of data, with and without a running compensation algorithm, were calculated and recorded simultaneously. The subject took one hundred twenty-nine (129) steps walking northward but needed only sixty-eight (68) steps to run back. As shown in FIG. 8, the pedometer without running compensation had a greater error in tracking the position of the user during the running phase. Thus, the increased accuracy of using a running compensation algorithm can be verified.  
         [0046]    While certain exemplary embodiments have been described and shown in the accompanying drawings, it is to be understood that such embodiments are merely illustrative of and not restrictive on the broad invention, and that this invention not be limited to the specific constructions and arrangements shown and described, since various other modifications are possible. Those skilled, in the art will appreciate that various adaptations and modifications of the just described preferred embodiment can be configured without departing from the scope and spirit of the invention. Additionally, it is possible to implement embodiments of the invention or some of their features in hardware, programmable devices, firmware, software or a combination thereof. The invention or parts of the invention may also be embodied in a processor-readable storage medium or machine-readable medium such as a magnetic (e.g., hard drive, floppy drive), optical (e.g., compact disk, digital versatile disk, etc), or semiconductor storage medium (volatile and non-volatile). Therefore, it is to be understood that, within the scope of the appended claims, the invention may be practiced other than as specifically described herein.