United States Patent (19)
`Levi et al.
`
`54) DEAD RECKONING NAVIGATIONAL
`SYSTEMUSING ACCELEROMETERTO
`MEASURE FOOT IMPACTS
`
`(75) Inventors: Robert W. Levi, Anaheim, Thomas
`Judd, Fountain Valley, both of Calif.
`73 Assignee: Point Research Corporation, Santa
`Ana, Calif.
`
`(21) Appl. No.: 405,087
`22 Filed:
`Mar 16, 1995
`6
`I51)
`int. Cl. ..................................................... GO1C 22/00
`(52
`364/450; 364/443; 364/460
`58 Field of Search ..................................... 364449,450,
`364/452, 460, 454,443; 235/105; 340/944;
`73/490
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`23.5/105
`1/1972 Dahlquist et al
`3,635,399
`35,010 3/1674 Adicca. 340,323
`3,901,086 8/1975 Griffiths et al. .......................... 73/.490
`4,053,755 10/1977 Sherrill ...............
`. 364,561
`4,149,417 4/1979 Griffiths et al. .......................... 73/490
`4,409,992 O/1983 Sidorenko et al. ..................... 128/782
`
`||||III|IIII
`US005583776A
`11) Patent Number:
`5,583,776
`(45) Date of Patent:
`Dec. 10, 1996
`
`4,991,126 2/1991 Reiter ...................................... 364/561
`5,117,301
`5/1992 Tsumura....
`359,154
`5,117,444 5/1992 Sutton et al. ..
`... 377/242
`5,367,458 11/1994 Roberts et al.
`364/42402
`5,485,402
`1/1996 Smith et al. ............................ 354/566
`OTHER PUBLICATIONS
`Meijer, et al., Methods to Assess Physical Activity with
`Special Reference to Motion Sensors and Accelerometers,
`IEEE Transactions on Biomedical Engineering, Mar. 1991,
`vol. 38, No. 3, pp. 221–229.
`"American Practical Navigator', originally by N. Bowditch,
`LL.D., 1966-Corrected Print, published by the U.S. Navy
`Hydrographic Office.
`Primary Examiner Michael Zanelli
`Attorney, Agent, or Firm-Price, Gess & Ubell
`57)
`ABSTRACT
`A microcomputer-assisted position finding system that inte
`grates GPS data, dead reckoning sensors, and digital maps
`into a low-cost, self-contained navigation instrument is
`disclosed. A built-in radio frequency transponder allows
`individual positions to be monitored by a central coordinat
`ing facility, Unique dead reckoning sensors and features are
`disclosed for ground speed/distance measurement and com
`puter-aided position fixes.
`
`15 Claims, 8 Drawing Sheets
`
`
`
`
`
`NITALIZE SLIDING WINDOW,
`NORTH AND EAST ACCUMULATORS
`AND TOTAL DISANCE
`
`GE NEXT SAMPLE
`
`SHIFT OUT OLD SAMPLE
`PUT NEW SAMPLENTO
`SLONG WINDOW
`
`PERIODeMIN.
`p
`
`Y
`
`SAVE NEW PEAK ME
`
`ADD SEPSIZE TO OAL DISTANCE
`ADDCOS (HEADING) STEPSIZE TONORTH ACCUMULATOR
`ADD SN (HEADING) "STEPSIZE TO EASAOCUMULATOR
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IPR2020-01192
`Apple EX1006 Page 1
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 1 of 8
`
`5,583,776
`
`3.O
`
`2. 5
`
`
`
`2. O
`
`TTL-E.
`-K1
`
`O
`
`O
`
`2O
`
`4.O
`3.O
`SPEED (MPH)
`FIG.
`
`5.O
`
`6.O
`
`7O
`
`8O
`
`
`
`ACCELERATION
`Ol8lg
`
`TIME
`
`FIG. 2
`
`IPR2020-01192
`Apple EX1006 Page 2
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 2 of 8
`
`5,583,776
`
`
`
`
`
`O
`
`C
`as
`SS
`O
`O
`
`3.
`
`N)
`d CO
`L
`
`CN
`D -
`Sco
`a
`is a
`O. :
`És o S C
`25
`n
`Xs
`
`S
`
`E
`3
`9 x
`l
`
`C
`&
`
`2 >
`
`IPR2020-01192
`Apple EX1006 Page 3
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 3 of 8
`
`5,583,776
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`INITIALIZE SLIDING WINDOW,
`NORTH AND EAST ACCUMULATORS
`AND TOTAL DISTANCE
`
`GET NEXT SAMPLE
`
`SHIFT OUT OLD SAMPLE
`PUT NEW SAMPLE INTO
`SLONG WINDOW
`
`PERIODMIN.
`p
`
`Y
`
`SAVE NEW PEAK TME
`
`ADD STEPSIZE TO TOTAL DISTANCE
`ADDCOS (HEADING) "STEPSIZE TO NORTH ACCUMULATOR
`ADD SIN (HEADING) "STEPSIZE TO EASTAOCUMULATOR
`
`FIG. 4
`
`IPR2020-01192
`Apple EX1006 Page 4
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 4 of 8
`
`5,583,776
`
`
`
`STEP SIZE
`
`SO
`
`S = SO + m * (f-fO)
`
`fC)
`
`STEPS PER SECOND
`
`FIG. 5
`
`IPR2020-01192
`Apple EX1006 Page 5
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 5 of 8
`
`5,583,776
`
`
`
`
`
`NITIALIZE FFT REAL 8
`MAGINARY ARRAYS
`
`6O.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`GET NEXT SAMPLE
`
`
`
`ENOUGH
`SAMPLES FOR
`NEXT FFT
`p
`Y
`
`CALCULATE FFT
`
`FIND PEAK FREQUENCY, f
`
`FREQUENCY
`RANGE OK
`
`CALCULATE NEW STEPSIZE
`S = SO+ m * (f-fC))
`
`CALCULATE:
`TOTAL DISTANCE
`NORTH DSPLACEMENT
`EAST DISPLACEMENT
`
`F.G. 6
`
`IPR2020-01192
`Apple EX1006 Page 6
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 6 of 8
`
`5,583,776
`
`
`
`
`
`
`
`
`
`NITALIZE STEPSIZE
`FROM DEFAULTS
`
`7O
`
`GET NEXT
`STEP PERIOD
`
`SMOOTH STEP
`PERIOD
`
`7O2
`
`7O3
`
`
`
`
`
`
`
`CALCULATE STEP
`FREQUENCY
`
`CALCULATE NEW
`STEPSIZE
`
`7O5
`
`FIG. 7
`
`IPR2020-01192
`Apple EX1006 Page 7
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 7 of 8
`
`5,583,776
`
`START
`
`SELECT FIRST LANDMARK
`MARK ON MAP
`
`AM AT LANDMARK AND
`PRESS TRIGGER
`
`8O
`
`8O2
`
`LOP SHOWN ON MAP
`
`3
`8O
`
`8O7
`
`USE ALTIMETER
`INFO TO DETERMINE
`POSITION ALONG LOP
`
`
`
`
`
`
`
`SELECT NEXT ANDMARK-8O4
`
`(DONE)
`
`AMAND PRESS TRIGGER - 8O5
`
`LOP SHOWN ON MAP
`
`8O6
`
`
`
`
`
`KEEP LATEST LOP
`ON MAP ERASE
`ANY OTHERS
`
`
`
`
`
`
`
`POSITION
`AT INTERSECTIO
`9F LOP2
`
`8.
`
`
`
`CALCULATION POSITION
`AS INTERSECTION OF LOP
`
`
`
`CURSOR SELECTS
`POSITION ON MAP
`
`IPR2020-01192
`Apple EX1006 Page 8
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 8 of 8
`
`5,583,776
`
`ENTER BEGINNG
`MAP POSITION
`
`90
`
`WALK TOWARDS
`DESTINATION
`(USE CURRENTSTEPSIZING
`AND COMPASS OFFSET )
`
`902
`
`ENTER ENDING
`MAP POSITION
`
`
`
`CALCULATE MAP DISPLACEMENT
`AND OR DISPLACEMENT
`
`
`
`
`
`CALCULATE NEW
`STEPSIZE
`
`
`
`CALCULATE NEW
`COMPASS OFFSET
`
`907
`
`FIG. 9
`
`IPR2020-01192
`Apple EX1006 Page 9
`
`

`

`5,583,776
`
`1.
`DEAD RECKONING NAVIGATIONAL
`SYSTEM USING ACCELEROMETERTO
`MEASURE FOOT IMPACTS
`
`BACKGROUND OF THE INVENTION
`
`5
`
`10
`
`15
`
`20
`
`1. Field of the Invention
`The present invention relates generally to navigational
`systems and, in particular, to electronic, portable naviga
`tional systems that use radionavigational data and dead
`reckoning for foot navigation.
`2. Description of Related Art
`The term "dead reckoning' (DR) refers to a position
`solution that is obtained by measuring or deducing displace
`ments from a known starting point in accordance with
`motion of the user. Two types of DR are known: inertial
`navigation and compass/speedometer.
`Inertial Navigation Systems (INS) use data from three
`orthogonal accelerometers. Double integration calculates
`position from acceleration as the user moves. Three gyros
`are also required to measure the attitude of the accelerom
`eters and remove the effects of gravity. Results of the
`integration are added to the starting position to obtain
`current location. The need for six accurate and stable sensors
`makes the cost of INS high.
`INS position errors increase with the square of time due
`to the double integration. These errors could easily be a large
`fraction of a foot traveler's ground speed. A typical INS
`system has a drift rate on the order of 0.8 miles per hour
`(mph). Although this error could easily exceed the rate of
`travel for a person walking on foot, it may be negligible for
`a jet aircraft. Future developments in inertial sensors may
`lower costs, but improvements in accuracy are less predict
`able. For these reasons, inertial navigation may not be a
`35
`viable option for low-cost foot traveler navigation.
`Regarding compass/speedometer DR systems, a compass
`and a speed/distance sensor is a direct means to determine
`location, and has been automated with microcomputers in
`vehicular applications. Simple and low-cost DR systems for
`land navigation have often been built using only a compass
`and a ground speed sensor for measurements.
`Generally, these systems have been designed for automo
`biles or trucks, with the speed sensor output being derived
`from rotation of the road wheels. Strap-down inertial navi
`gation systems have become popular due to the numerical
`processing capability of microprocessors and are lower cost
`and power than stable platform inertial systems.
`A considerable amount of work has been done related to
`the integration of a Global Positioning System (GPS) and
`INS. The importance of supplementing the GPS position
`solution with an integrated GPS/DR system is evidenced by
`the considerable work that has been done in this area. Work
`has not been done specifically for foot traveler, hiker, or
`pedestrian use in this area.
`
`25
`
`30
`
`45
`
`50
`
`55
`
`SUMMARY OF THE INVENTION
`GPS data can be either unreliable or unavailable due to
`antenna shading, jamming, or interference. The present
`invention discloses incorporation of DR functions with GPS
`position information, thus providing the individual foot
`traveler with an autonomous navigation capability. The
`present invention discloses a microcomputer-assisted posi
`tion finding system that integrates GPS data, DR sensors,
`and digital maps into a low-cost, self-contained navigation
`instrument. A built-in radio frequency transponder allows
`
`60
`
`65
`
`2
`individual positions to be monitored by a central coordinat
`ing facility. Unique DR sensors and features are disclosed
`for ground speed/distance measurement and computer-aided
`position fixes.
`The navigation system of the present invention combines
`a digital electronic compass with both a silicon pedometer
`and a barometric altimeter to generate a low-cost, comput
`erized DR system. These sensors are used in a complemen
`tary configuration with GPS and digital electronic maps.
`Compared with a stand-alone GPS receiver, the integrated
`GPS-DR navigation system of the present invention pro
`vides advantages during GPS outages. In these outages, DR
`continuously tracks the user's position without references to
`external aids or signals.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The objects and features of the present invention, which
`are believed to be novel, are set forth with particularity in the
`appended claims. The present invention, both as to its
`organization and manner of operation, together with further
`objects and advantages, may best be understood by reference
`to the following description, taken in connection with the
`accompanying drawings.
`FIG. 1 illustrates a pedometer calibration curve of speed
`versus fundamental frequency for two different users;
`FIG. 2 illustrates raw data from a silicon accelerometer
`plotted on a time axis;
`FIG. 3 illustrates a frequency domain representation of
`the silicon accelerometer raw data of FIG. 2;
`FIG. 4 illustrates a flow chart for peak detection according
`to the presently preferred embodiment;
`FIG. 5 illustrates the relationship between frequency of a
`user's steps and step size; .
`FIG. 6 illustrates the frequency measurement algorithm of
`the presently preferred embodiment;
`FIG. 7 illustrates the dynamic step size algorithm of the
`presently preferred embodiment;
`FIG. 8 illustrates a flow chart for the dead reckoning
`position fix algorithm of the presently preferred embodi
`ment; and
`FIG. 9 illustrates the calibration algorithm of the presently
`preferred embodiment.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`The following description is provided to enable any
`person skilled in the art to make and use the invention and
`sets forth the best modes contemplated by the inventors of
`carrying out their invention. Various modifications, how
`ever, will remain readily apparent to those skilled in the art,
`since the generic principles of the present invention have
`been defined herein specifically.
`The present invention analyzes the frequency of a user's
`footsteps to aid in the detection of future footsteps, and
`further to aid in determining the size of footsteps taken by
`the user. The present invention also incorporates several
`directional calibrating and position-fixing algorithms which
`are used in combination with digital maps.
`A. Use of Frequency to Detect Steps and Determine Step
`Size
`The present invention for a ground speed/distance sensor
`is an improvement over a common hiker's pedometer.
`Existing electronic pedometer designs use a spring-loaded
`
`IPR2020-01192
`Apple EX1006 Page 10
`
`

`

`3
`mechanical pendulum to sense walking motions of the user.
`The pendulum operates a simple switch so that the up-down
`motion of the pendulum may be counted by the unit's
`electronics. A scale factor that is proportional to the user's
`stride length is applied to the count. The assumption is that
`each count represents one step, however due to the pendu
`lum dynamics extra bounces can occur. Sensitivity and
`bouncing depends on the spring rate and the pendulous
`mass. Multiplying step counts by the scale factor yields a
`measure of distance. Prior-art pedometers require manual
`calibration, are unreliable, and cannot be interfaced to a
`computer.
`The present invention uses an accelerometer to provide
`acceleration data indicative of footsteps. The basic sensor
`for the navigation pedometer of the presently preferred
`embodiment comprises a silicon accelerometer. The accel
`erometer may be mounted or attached at any convenient
`point on the user's body, as long as it can sense the harmonic
`motions and impact accelerations that result from walking or
`running. Other footstep sensors may be used, such as force
`sensors embedded in the user's shoe. Shoe sensors, however,
`may be impractical, since they require special shoe modi
`fications and possibly wires up the leg of the user. Silicon
`accelerometers have recently become available at low cost
`from several vendors. The device is "micromachined' from
`solid silicon using much the same techniques as used for
`integrated circuit manufacture.
`The sensing element of the presently preferred embodi
`ment comprises a mass suspended on a flexure. When the
`mass is subjected to an acceleration force (for example,
`during a footstep), the resulting motion can be detected by
`an electrical resistance change in the flexure or by motion
`measurement of the mass. The resonant frequency of the
`accelerometer is much higher than ordinary electromechani
`cal pedometers. Similar sensors are used for crash detection
`in automotive air bag systems. The sensed footsteps are
`converted to distance and velocity.
`Lab experiments were conducted using the accelerometer
`footstep sensor of the present invention on a treadmill. FIG.
`1 shows the acceleration data resulting from walking at a
`speed of 3.3 mph on the treadmill. This data indicates that
`simple pulse counting is unreliable for counting the accel
`eration peaks that correspond to footsteps. The character of
`the data changes substantially as speed changes. Simple
`pulse counting is the method used by existing pedometers.
`The present invention combats problems associated with
`simple pulse counting by extracting the fundamental fre
`quency of a hiker's footsteps, using digital signal processing
`techniques. More complex peak counting algorithms are
`also feasible.
`AFast FourierTransform (FFT) spectrum analyzer is used
`in conjunction with treadmill testing to gather fundamental
`frequency data from 1 to 7 mph, for example. Thus, a
`fundamental frequency is determined for each speed of a
`hiker, by collecting acceleration peaks corresponding to the
`user's footsteps at that speed, taking an FFT of the data, and
`recording the fundamental frequency for the hiker at that
`speed.
`A typical spectrum is shown in FIG. 2. This spectrum
`corresponds to a hiker's acceleration peaks at 3.3 mph. FIG.
`2 shows that the fundamental frequency is about 1.8 Hz for
`the hiker's speed of 3.3 mph. The present invention thus
`collects fundamental frequencies for a user at various
`speeds. From this data, Applicants have discovered that the
`fundamental frequency is indeed proportional to a user's
`speed.
`FIG. 3 shows a calibration curve resulting from a plot of
`the fundamental frequencies derived via FFT and the tread
`
`4
`mill speed. The linearity of the results is a good indication
`that this method works without a large amount of complex
`mathematical manipulations. Two curves are shown in FIG.
`3. One of the curves is for a person with a relatively short
`stride, and the other curve is for a person with alonger stride.
`As expected, the person with the shorter stride must "walk
`faster,' which results in higher fundamental frequencies for
`the same speed for that person with the shorter stride. This
`corresponds to step size increasing with increasing speed.
`The tapering off at the higher speeds indicates that step size
`is increasing.
`In a fielded system, automatic calibration using GPS
`velocity can be used with a military GPS or Differential GPS
`receiver to obtain a calibration curve fit to the user's stride
`and terrain traveled. With a civilian GPS receiver and
`selective availability velocity accuracies of about 1 m/s are
`not good enough for velocity calibration.
`Walking thus produces a periodic variation in vertical
`acceleration, which is measured on the user's body and
`indicated by the accelerometer. Peaks in the acceleration
`correspond to individual steps. The fundamental period of
`the data is the step frequency for that speed. Hence, two
`independent methods may be used by the present invention
`to determine displacement: one based on the detection of
`single steps, and another based on the determination of the
`frequency content of the signal from a number of steps.
`These two methods may be used separately or in combina
`tion.
`1. Peak Detection Algorithm
`Peak or step detection allows determination of distance
`directly by a scale factor. A sliding window of the data is
`maintained with an odd number of samples. Using an odd
`number of samples ensures that there is always a central
`sample. The central sample in the window, is tested. Refer to
`FIG. 4.
`Step 401: First, the sliding window is set to zero, as are
`North and East distance accumulators, and the total
`distance traveled.
`Step 402: The next accelerometer sample is taken.
`Step 403: The samples in the sliding window are shifted,
`the oldest falls off the far end, the new sample is placed
`in the near end.
`Step 404: The middle sample is compared to all the others.
`If it is greater than the rest, then there is a potential step
`or peak in the data. If not, another sample is taken.
`Step 405: The magnitude of the peak must be above a
`minimum threshold to prevent false detection on small
`fluctuations that could not have been caused by foot
`falls. If the magnitude of the peak is below the thresh
`old, another sample is taken.
`Step 406: The time since the last peak must be greater than
`some minimum period. If it is expected that steps will
`occur no more often than three times per second, for
`example, then peaks that are closer in time than /3-sec
`ond are not allowed. If the period is too small, another
`sample is taken.
`Step 407: A peak exists. The time is marked so it may be
`used for comparison in Step 6 the next time around.
`Step 408: Total distance traveled is
`New distance=old distance+step size
`
`The north and east accumulators are modified as fol
`lows:
`
`New North=Old North+step size * cosine (heading)
`
`5,583,776
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`45
`
`50
`
`55
`
`60
`
`65
`
`IPR2020-01192
`Apple EX1006 Page 11
`
`

`

`10
`
`15
`
`20
`
`30
`
`35
`
`S
`New East=Old East-step size * sine (heading)
`The average or steady-state value of the data is subtracted
`from the accelerometer samples to remove gravity effects.
`The resulting dynamic component of the data contains the
`useful peak information. The dynamic data is filtered to
`attenuate accelerations that are outside the known frequency
`band of human movement. Measurements have shown that
`the fundamental frequencies for normal human walking and
`running are below 10 Hz. A peak is noted if the data sample
`is the largest value in a set of samples that include times
`before and after the peak sample. It also must be larger than
`a minimum threshold value, and must not occur within a set
`time period, measured from the previously detected peak.
`The user's stride length is added incrementally to the
`accumulated distance every time a peak is detected. North
`and East components of the stride are calculated using data
`from the direction sensor. The component displacements are
`added to separate North and East accumulators, and are used
`to calculate the total displacement from the starting point.
`2. Frequency Measurement Algorithm
`Frequency measurement is performed in the presently
`preferred embodiment primarily to obtain step size. Step
`size is related to frequency as shown in FIG. 5. Frequency
`detection relies on a Fast Fourier Transform (FFT) to
`estimate the frequency content of the signal, and an FFT
`25
`requires that a fixed number of samples be stored prior to
`analysis. An FFT cannot be performed on a single sample.
`To keep the update rate reasonable, a sliding window of
`samples is used, and the FFT is recalculated after a percent
`age of fresh samples have been added. Refer to flow chart
`FIG. 6.
`Step 601: First, initialize the real and imaginary arrays to
`Zero.
`Step 602: Get the next sample and place it in the real
`array.
`Step 603: If there are sufficient samples to perform the
`FFT then go on; otherwise go get the next sample.
`There may be a 512-point FFT, but recalculation every
`128 samples may be advantageous. So if only 128
`Samples are new, go on.
`Step 604: Calculate the FFT.
`Step 605: The magnitude of each frequency bin is calcu
`lated, and the largest of these is identified as the step
`frequency.
`Step 606: As in the peak detection algorithm, minimum
`limits are put on the strength of the signal, so that
`calculations on noise are not performed. If a minimum
`threshold on the signal is not met, then do not proceed
`to update the accumulators; rather, return to get more
`data.
`Step 607: The range of acceptable frequencies is also
`limited. If they are outside normal walking frequencies
`(0.5 to 3.0 Hz) then proceed with the calculation but do
`not update the step size.
`Step 608: If the frequency range check is passed, then the
`step size is readjusted according to the newly-calcu
`lated frequency:
`
`40
`
`45
`
`50
`
`55
`
`Step 609: Calculation of Total Displacement and the
`North and East components is similar to that in the Peak
`Detection Algorithm, except now it is being done on
`multiple steps over a fixed time period. The individual
`components are scaled by the time period and the step
`frequency. For example:
`
`60
`
`65
`
`5,583,776
`
`6
`North change=step size cos (heading) *fftPeriod * f.
`
`The fiftperiod is the time it took to collect just the new
`points, not the whole ensemble. Using the example
`above, it would be 128 sample points, not 512.
`3. Dynamic Step Size Algorithm
`As a user walks faster, both the step size and the fre
`quency of steps increases. This can be simply modeled as a
`linear fit to observed data at different walking speeds.
`Looking at the calibration data shown in FIG. 5, as the
`number of steps increases from 1.7 to 2.1 steps per second,
`for example, the step size increases from 0.72 meters (2.36
`feet) to 0.90 meters (2.95 feet). In this example, the fre
`quencies span rates from a stroll to a fast walk. The step size
`varies by more than 20% under these conditions.
`Since step size directly affects the estimated DR distance,
`the presently preferred embodiment adjusts step size accord
`ing to the step frequency. A dynamic scaling algorithm to
`improve the accuracy of distance measurements of a human
`footstep sensor by adjusting the scale factor as a function of
`step frequency is thus harnessed by the present invention.
`Refer to flow chart FIG. 7.
`Step 701: The step size may be initialized from default
`values stored in a configuration file. The configuration
`is particular to the individual person using the system
`and is generated during the calibration process. Three
`constants are saved: S0, fo, and m. S0 is the default step
`size, fo is the frequency at which there is no correction
`to S0, and m is the slope of the calibration curve.
`Step 702: The time of each step is noted as the pedometer
`collects data. The step period is calculated as the time
`between two successive steps.
`Step 703: The step period is smoothed over a suitable time
`period. An average of the last five to ten steps is
`suitable.
`Step 704: The step frequency is the reciprocal of the
`averaged step period:
`f-1/(step period)
`
`Step 705: The new step size is calculated by:
`
`S=S0+m * (ff0)
`B. Directional Correcting and Position Fixing Algorithms
`Incorporating Digitized Maps
`DR errors depend on a number of factors, including the
`speed of travel and the time between position fixes. If GPS
`is used to update DR positions, the error depends on the
`duration of the GPS outage. Vehicular DR systems have
`achieved errors of 2% to 5% of distance traveled. According
`to the present invention, calculations were performed to
`determine errors as a percent of distance traveled using
`known error sources. An azimuth error of 1 degree due to the
`electronic compass will produce a position error of about 2%
`of distance traveled. In vehicular DR systems, the compass
`has been shown to be the predominant source of error.
`Hardware testing by the Applicants with actual hiking
`sensors showed position errors on the order of 1-2% of the
`distance traveled.
`In view of the above problems recognized by the present
`invention, calibration algorithms for the compass and speed/
`distance sensor are incorporated for successful implemen
`tation of the DR system. The present invention utilizes novel
`algorithms for accurately aligning the compass direction
`readout with the direction of travel of the user.
`According to the present invention, combining position
`ing functions with digital electronic maps frees the user from
`
`IPR2020-01192
`Apple EX1006 Page 12
`
`

`

`5,583,776
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`7
`the tedious and error-prone process of transferring coordi
`nates from a digital GPS position display to a paper map.
`Additional benefits are realized by combining manual azi
`muths obtained from sightings with digital map data. The
`present invention's use of digital maps thus allows for
`accurate calibration of the DR navigation system.
`To take advantage of the positioning capabilities of DR
`and GPS, navigation features are included in the present
`invention. These features are intended to help the user find
`his destination, identify landmarks, travel a defined route,
`and fix his position. Area navigation functions require cal
`culation for determining such parameters as required course,
`speed, and distance, time, or velocity. These calculations are
`based on plane or spherical trigonometry. A capability for
`defining waypoints and routes comprised of connected way
`points is provided. Coordinate transformations between
`Latitude/Longitude and Universal Transverse Mercator
`(UTM) are also included.
`Algorithms for exploiting the built-in digital compass and
`map of the presently preferred embodiment are included.
`Computer-aided manual fixes are automatically calculated
`and plotted on the map when compass azimuths on two
`known landmarks are available. Another technique known
`as a running-fix allows position determination by azimuths
`on a single known landmark. By taking successive azimuths
`on the same feature, but separated in time and distance, one
`of the azimuths can be advanced or retarded to coincide in
`time with the other bearing, thus providing data for a
`position fix.
`The user's keypad and graphical display of the presently
`preferred embodiment is contained in a hand-held enclosure.
`Placing the compass in the hand-held enclosure allows
`manual sightings. for bearings and manual fixes. A holster
`attached to the user's belt and placed near the hip holds the
`hand-held enclosure while the user is traveling. The hip
`holster location also provides an ideal mounting point for the
`pedometer. The keypad layout and the associated software
`allows the user to exercise the various functions. Features
`are accessed via menu-driven mode selections. The user can
`Select the desired primary function or mode by pressing a
`key on the keypad. In the presently preferred embodiment,
`mode keys group the major functions as follows:
`
`35
`
`40
`
`POS
`
`GPS
`
`DR
`
`MAP
`
`NAW
`
`WPT
`
`COM
`
`TIM
`
`ALR
`
`Show current position on map. Indicator shows whether
`the position is derived from GPS or DR.
`Directly access the GPS receiver functions and data
`output. Controls for 2D/3D mode, signal/noise mask,
`DOP switching levels. Display of receiver status
`and almanac data.
`Access position solution from DR system. Graphical
`compass output display, Pedometer speed readout and
`distance since last fix. Altimeter readout. Manual and
`automatic calibration modes.
`Display map data independent of current position.
`Show user defined features. Pan, zoom functions.
`Area navigation, range and bearing to features.
`Control display of track and route.
`Create and modify waypoints, routes and user
`defined features.
`Control the digital data link and transmit user's position.
`Review incoming and outgoing messages.
`Send predefined messages.
`Timer functions such as elapsed time, estimated
`time of arrival.
`Alarm functions to activate an alert when approaching a
`destination or preset time.
`
`45
`
`50
`
`55
`
`60
`
`The DR software module of the present invention per
`forms dead reckoning (DR) navigation by sampling vector
`Velocities for incremental course changes. Calculations can
`be performed continuously whenever there is a detected
`
`65
`
`8
`velocity. The DR software accesses the compass, altimeter,
`pedometer frequency, and calibration table data to obtain
`velocity magnitude and 3-D direction. The DR software
`normally uses GPS to obtain starting positions when GPS is
`valid, but also accepts manual position fixes by map selec
`tion or text entry. When GPS is not valid, DR uses the last
`fix, whether GPS or manual, for a start point. DR navigation
`is automatically used by the navigation module when GPS
`is unavailable. The map and navigation modules are used to
`Select a manual fix location from the map, or to manually
`switch between DR and GPS navigation.
`The navigation software module performs area navigation
`functions, and determines relative positions between loca
`tions. Calculations for required course, speed, time, and
`distance required are based on plane or spherical geometry.
`Terrain and other features selected by the user are treated as
`inputs to the navigation module. The navigation module may
`perform switching between DR and GPS navigation auto
`matically, as conditions dictate.
`In the presently preferred embodiment, GPS and DR
`sources are selected with a switch scheme depending on
`whether GPS is available. When GPS fixes are available, the
`DR system is continuously updated using the GPS fix. The
`output composite position/velocity track is displayed on the
`map.
`Current course and speed calculation is continuously
`displayed on the map, along with a position track. The user
`can enter or select locations for area navigation. The user can
`determine course and range between two locations, using
`trigonometry algorithms. Horizontal, vertical, and slant
`range are found with trigonometry. The user can select a
`destination such as a feature or waypoint to obtain naviga
`tion information. The starting location can be current posi
`tion or some other user-defined position. Time and velocity
`may be calculated from the given positions or course and
`range, Such as required velocity or estimated-time-of-ar
`rival.
`The simplest method for a manual fix is to enter a known
`current location. The user may also take bearings with the
`hand-held-enclosure compass/trigger switch and automati
`cally triangulate to establish a position fix and DR starting
`location.
`1. DR Position Fix Algorithm
`Since DR calculates an incremental change in position
`from a known starting point, subsequent positioning
`depends on accurately identifying the starting position.
`Periodic reinitialization of DR position is thus performed in
`the presently preferred embodiment, to thereby avoid accu
`mulation of errors. These methods are independent from
`radionavigation aids such as GPS. Refer to flow chart FIG.
`8.
`Step 801: The user visually identifies the first landmark
`desired for use in the manual fix. He or she then moves
`the electronic cursor on the digital map and marks it as
`his first point of reference.
`Step 802: The user aims the hand-held enclosure contain
`ing the electronic compass and a sighting post at the
`landmark and presses a trigger switch to indicate to the
`Computer to save that compass bearing and to associate
`it with the identified landmark.
`Step 803: A Line of Position (LOP) appears on the map
`that indicates the bearing direction line from the user's
`position t