United States Patent [19]
`Levi et al.
`
`lllllllllllllllllIlllllllllllllllllllllllllllllllllllllllIlllllllllllllllll
`USOO5583776A
`[11] Patent Number:
`5,583,776
`[45] Date of Patent:
`Dec. 10, 1996
`
`[54] DEAD RECKONING NAVIGATIONAL
`
`4,991,126
`
`2/1991 Reiter .................................... .. 364/561
`
`
`
`SYSTEM USING ACCELEROMETER TO MEASURE FOOT INIPACTS
`
`[75] Inventors; Robert W_ Levi, Anaheim; Thomas
`Judd, Fountain Valley, both of Calif.
`
`[73] Assignee: Point Research Corporation, Santa
`Ana’ Calif
`
`[21] Appl' No'z 405’087
`[22] Filed:
`Mar. 16, 1995
`
`6
`[51] Int. Cl. ................................................... .. G01C 22/00
`[52]
`364/450; 364/443; 364/460
`[58] Field of Search ................................... .. 364/449, 450,
`364/452, 460, 454, 443; 235/105; 340/944;
`73/490
`
`_
`[56]
`
`References Cited
`
`‘
`
`-
`
`U-S- PATENT DOCUMENTS
`1/1972 Dahlquist et a1. .................... .. 235/105
`3,635,399
`3/1974 Adler et aL
`340/323
`3,797,010
`3/1975 Grmiths et a1_
`____ " 73/490
`3,901,036
`4,053,755 10/1977 Sherrill ............. ..
`. 364/561
`4,149,417
`4/1979 Gri?iths et a1.
`..... .. 73/490
`4,409,992 10/ 1983 Sidorenko et a1. ................... .. 128/782
`
`5/1992 Tsumura 5/1992 Sutton et a1. ..
`5,117,301 5,117,444
`
`
`5,367,458 11/1994 Roberts et al.
`5,485,402
`1/1996 Smith et a1. .......................... .. 354/566
`OTHER PUBLICATIONS
`
`Meijer, et 21., 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 US Navy
`Hydrographic O?ice.
`Primary Examiner—l\'/Iichael IZanelli
`“may, Agent’ 0’ Fm’H’me’ Ge“ & Ubcn
`[57]
`ABSTRACT
`A microcomputer-assisted position ?nding 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 p°siti°ns ‘0 be monitored by a Central mmdinat'
`ing facility. Unique dead reckoning sensors and features are
`disclosed for ground speed/distance measurement and com
`puter-aided position ?xes.
`
`15 Claims, 8 Drawing Sheets
`
`@
`
`INITIALIZE SLIDING WINDOW, ,
`40],,- NORTH AND EAST ACCUMULATORS
`AND TOTAL DISTANCE
`
`402
`
`403\ SHIFT OUT OLD SAMPLE
`PUT NEW SAMPLE INTO
`SLIDING WINDOW
`
`ADD STEPSIZE TO TOTAL DISTANCE
`ADDCOS(HEADING) 'STEPSIZE TO MJRTHACCUMULATOR
`ADD SIN (HEADING) ‘STEPSIZE T0 EASTAQIUMULATOR
`
`TomTom Exhibit 1003, Page 1 of 15
`
`

`

`US. Patent
`
`Dec. 10, 1996
`
`Sheet 1 of 8
`
`5,583,776
`
`3.0
`
`2.5
`
`/--—0
`
`.
`
`.
`
`/
`
`,
`
`/
`/ LONG
`SHORT % "
`STRIDE
`STRIDE
`\ /
`/
`//
`
`.
`
`I
`
`n:
`
`-
`
`'5
`2
`*5‘
`S '5
`L.
`a‘
`5
`2
`§ 3 0.5
`
`l-
`
`l0
`
`I
`
`L1.
`
`0
`0
`
`1.0
`
`20
`
`5.0
`
`.
`
`6.0
`
`20
`
`8.0
`
`4.0
`3.0
`SPEED (MPH)
`FIG. I
`
`llllllllllllllllllllllllllllllll
`I
`ACCELERATION
`:
`
`l'*———l SEC —>|
`l|1|||||||11l||1|11||1|||1|||||l
`
`TIME
`
`FIG. 2
`
`TomTom Exhibit 1003, Page 2 of 15
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 2 0f 8
`
`5,583,776
`
`ta:
`
`25x6
`
`NI
`
`m 9....
`
`03:
`
`wSE
`
`Emm x 9E
`
`TomTom Exhibit 1003, Page 3 of 15
`
`

`

`US. Patent
`
`Dec. 10, 1996
`
`Sheet 3 of 8
`
`5,583,776
`
`I START I
`
`I
`
`INITIALIZE SLIDING WINDOW,
`4Q|__,_ NORTH AND EAST ACCUMULATORS
`AND TOTAL DISTANCE
`I
`GET NEXT SAMPLE
`
`II
`403\ SHIFT OUT OLD SAMPLE
`TPUT NEW SAMPLE INTO
`SLIDING WINDOW
`
`MIDDLE SAMPL
`> ALL OTHERS
`
`PERIOD>MIN.
`I?
`
`SAVE NEW PEAK TIME
`I
`408 w
`ADD STEPSIZE TO TOTAL DISTANCE
`ADD COS(HEADING) *STEPSIZE TO I\DRTH ACCUMULATOR
`ADD SIN (HEADING) ‘STEPSIZE TO EASTACIIUMULATOR
`
`FIG. 4
`
`TomTom Exhibit 1003, Page 4 of 15
`
`

`

`US. Patent
`
`Dec. 10, 1996
`
`Sheet 4 of 8
`
`5,583,776
`
`-O.9
`
`'
`
`0
`
`SLOP= m
`
`STEP SIZE
`
`80
`
`_O.72
`
`'
`
`S:
`
`m
`
`f0
`
`STEPS PER SECOND
`
`FIG. 5
`
`TomTom Exhibit 1003, Page 5 of 15
`
`

`

`US. Patent
`
`Dec. 10, 1996
`
`Sheet 5 of 8
`
`5,583,776
`
`( START )
`
`I
`INITIALIZE FFT REAL a
`IMAGINARY ARRAYS H6O’
`
`‘ GET NEXT SAMPLE #602
`
`603
`
`ENOUGH
`SAMPLES FOR
`NEXT) FFT
`
`CALCULATE FF T
`
`1
`
`FIND PEAK FREQUENCY, f V605
`
`FIG.6
`
`FREQUENCY
`RANGE OK
`
`608
`
`CALCULATE NEW STEPSIZE
`S = SO+ m *(f-fO)
`
`T
`
`CALCU LATE:
`soi
`TOTAL DISTANCE
`NORTH DISPLACEMENT ‘*
`EAST DISPLACEMENT
`
`TomTom Exhibit 1003, Page 6 of 15
`
`

`

`US. Patent
`
`Dec. 10, 1996
`
`Sheet 6 of 8
`
`5,583,776
`
`INITIALIZE STEPSIZE
`FROM DEFAULTS
`
`TOI
`
`GET NEXT
`_""' STEP PERIOD
`
`702
`
`SMOOTH STEP
`PERIOD
`
`703
`
`CALCULATE STEP
`FREQUENCY
`
`704
`
`CALCULATE NEW
`STEPS IZE
`
`705
`
`FIG. 7
`
`TomTom Exhibit 1003, Page 7 of 15
`
`

`

`US. Patent
`
`Dec. 10, 1996
`
`Sheet 7
`
`5,583,776
`
`@
`
`SELECT FIRST LANDMARK
`MARK ON MAP
`
`I
`AIM AT LANDMARK AND
`PRESS TRIGGER
`
`I
`LOP SHOWN ON MAP ~803
`
`80?
`
`SINGLE
`LOP?
`
`USE ALTIMETER
`INFO TO DETERMINE
`POSITION ALONG LOP
`
`SELECT NEXT LANDMARK '- 804
`
`I
`AIM AND PRESS TRICK-BER " 805
`
`I
`LOP SHOWN ON MAP
`
`~ 806
`
`KEEP LATEST LOP
`ON MAP ERASE
`' ANY OTHERS
`
`I
`
`809
`
`AT INTE RSECTIO
`
`N
`
`I
`CANCEL
`
`CALCULATION POSITION
`AS INTERSECTION OF LOP
`
`CURSOR SELECTS
`POSITION ON MAP
`
`FIG.8
`
`‘
`
`,
`
`DONE
`
`TomTom Exhibit 1003, Page 8 of 15
`
`

`

`US. Patent
`
`Dec. 10, 1996
`
`Sheet 8 of s
`
`I
`
`5,583,776
`
`( START )
`
`ENTER BEGINING __/-9OI
`MAP POSITION
`
`T
`WALK TOWAR DS
`DESTI NA‘HON
`(USE CURRENTSTEPSIZING “"902
`AND COMPASS OFFSET )
`
`ENTER ENDING
`MAP POSITION
`
`V
`
`CALCULATE MAP DISPLACEMENT
`AND DR DISPLACEMENT
`--904
`
`CALCULATE NEW
`STEPSIZE
`
`f 906
`
`CALCULATE N E W
`COMPASS OFFSET r907
`
`TomTom Exhibit 1003, Page 9 of 15
`
`

`

`5,583,776
`
`1
`DEAD RECKONING NAVIGATIONAL
`SYSTEM USING ACCELEROMETER TO
`MEASURE FOOT IMPACTS
`
`BACKGROUND OF THE INVENTION
`
`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 ?xes.
`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 con?guration 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 ?ow 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; 7
`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 ?ow chart for the dead'reckoning
`position ?x 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 modi?cations, how
`ever, will remain readily apparent to those skilled in the art,
`since the generic principles of the present invention have
`been de?ned herein speci?cally.
`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-?xing 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
`
`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
`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 speci?cally for foot traveler, hiker, or
`pedestrian use in this area.
`
`25
`
`35
`
`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 ?nding 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
`
`65
`
`TomTom Exhibit 1003, Page 10 of 15
`
`

`

`5,583,776
`
`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
`?cations 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 ?exure. 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 ?exure 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 Fourier Transform (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 FFF 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 FFI‘ and the tread
`
`l0
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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 a longer 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 ?elded system, automatic calibration using GPS
`velocity can be used with a rrrilitary GPS or Differential GPS
`receiver to obtain a calibration curve ?t 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 deternrination of the
`frequency content of the signal from a number of steps.
`These two methods may be used separately or in combina
`tron.
`l. Peak Detection Algorithm
`Peak or step detection allows deterrrrination 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 rrriddle 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
`?uctuations 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 1/3-sec
`end are not allowed. If the period is too small, another
`sarrrple 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=0ld distance+step size
`
`The north and east accumulators are modi?ed as fol
`lows:
`
`New N0rth=0ld N0r1h+step size * cosine (heading)
`
`TomTom Exhibit 1003, Page 11 of 15
`
`

`

`5
`New East=0ld East+step size * sine (heading)
`
`6
`North change=step size* cos (heading) * fftPeriod * f.
`
`5,583,776
`
`The average or steady-state value of the data is subtracted
`from the accelerometer samples to remove gravity e?ects.
`The resulting dynamic component of the data contains the
`useful peak information. The dynamic data is ?ltered 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
`requires that a ?xed 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 FFl‘ is recalculated after a percent
`age of fresh samples have been added. Refer to ?ow chart
`FIG. 6.
`Step 601: First, initialize the real and imaginary arrays to
`
`1O
`
`15
`
`20
`
`The fftPeriod 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 ?t 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 ?ow chart FIG. 7.
`Step 701: The step size may be initialized from default
`values stored in a con?guration ?le. The con?guration
`is particular to the individual person using the system
`and is generated during the calibration process. Three
`constants are saved: S0, f0, and in. S0 is the default step
`size, f0 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 ?ve to ten steps is
`suitable.
`'
`
`Step 704: The step frequency is the reciprocal of the
`averaged step period:
`
`f=l/(step period)
`
`Step 705: The new step size is calculated by:
`
`S=S0+m * (f-jO)
`
`25
`
`30
`
`35
`
`zero.
`
`_
`
`Step 602: Get the next sample and place it in the real
`array.
`Step 603: If there are suf?cient samples to perform the
`FFT then go on; otherwise go get the next sample.
`There may be a 5l2-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 identi?ed 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:
`
`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 ?xed time period. The individual
`components are scaled by the time period and the step
`frequency. For example:
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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 ?xes. 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 l—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
`
`TomTom Exhibit 1003, Page 12 of 15
`
`

`

`5,583,776
`
`7
`the tedious and error-prone process of transferring coordi
`nates from a digital GPS position display to a paper map.
`Additional bene?ts 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 ?nd
`his destination, identify landmarks, travel a de?ned route,
`and ?x 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
`de?ning 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 ?xes are automatically calculated
`and plotted on the map when compass azimuths on two
`known landmarks are available. Another technique known
`as a running-?x 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 ?x.
`The user’s keypad and graphical display of the presently
`preferred embodiment is contained in a handheld enclosure.
`Placing the compass in the hand-held enclosure allows
`manual sightings. for bearings and manual ?xes. 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:
`
`20
`
`25
`
`35
`
`POS
`
`GPS
`
`DR
`
`MAP
`
`N AV
`
`WPT
`
`COM
`
`TIM
`
`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 ?x. Altimeter readout. Manual and
`automatic calibration modes.
`Display map data independent of current position.
`Show user de?ned features. Pan, zoom functions.
`Area navigation, range and bearing to features.
`Control display of track and route.
`Create and modify waypoints, routes and user
`de?ned features.
`Control the digital data link and transmit user's position.
`Review incoming and outgoing messages.
`Send prede?ned 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 ?xes by map selec
`tion or text entry. When GPS is not valid, DR uses the last
`?x, 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 ?x 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 ?xes are available, the
`DR system is continuously updated using the GPS ?x. 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-de?ned 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 ?x 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 ?x 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 ?ow chart FIG.
`8.
`'
`Step 801: The user visually identi?es the ?rst landmark
`desired for use in the manual ?x. He or she then moves
`the electronic cursor on the digital map and marks it as
`his ?rst 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 identi?ed landmark.
`Step 803: A Line of Position (LOP) appears on the