YI URAA
`
`US005583776A
`
`United States Patent 15
`5,583,776
`Dec. 10, 1996
`[45] Date of Patent:
`Leviet al.
`
`[11] Patent Number:
`
`[54]
`
`[75]
`
`[73]
`
`[21]
`
`[22]
`
`[51]
`[52]
`[58]
`
`[56]
`
`DEAD RECKONING NAVIGATIONAL
`SYSTEM USING ACCELEROMETER TO
`MEASURE FOOT IMPACTS
`
`Inventors: Robert W. Levi, Anaheim; Thomas
`Judd, Fountain Valley, both of Calif.
`
`Assignee: Point Research Corporation, Santa
`Ana, Calif.
`
`Appl. No.: 405,087
`
`Filed:
`
`Mar. 16, 1995
`
`ws G01C 22/00
`Tint. C19 oiecccccesccsscsssessessssssecnsssssensees
`
`US. Cl. cece
`
`364/450, 364/443; 364/460
`Field of Search... csssssssssssssesesseenss 364/449, 450,
`364/452, 460, 454, 443; 235/105; 340/944;
`73/490
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`1/1972 Dahlquist et al. 2...eee 235/105
`3,635,399
`w. 340/323
`
`3/1974 Adler et al.
`..
`3,797,010
`— 73/490
`8/1975 Griffiths et al.
`3,901,086
`.
`
`a 364/561
`4,053,755 10/1977 Sherrill ...........
`wae 73/490
`
`4,149,417
`4/1979 Griffiths et al.
`.
`4,409,992 10/1983 Sidorenko et al.
`..... esses 128/782
`
`4,991,126
`5,117,301
`§,117,444
`5,367,458
`5,485,402
`
`we 364/561
`2/1991 Reiter......
`ve 359/154
`5/1992 Tsumura......
`5/1992 Sutton et al.
`eee
`seseesseeee 377/24.2
`
`11/1994 Roberts et al.
`.
`.. 364/424.02
`...ccccseaseseseenesee 354/566
`1/1996 Smith et al.
`OTHER PUBLICATIONS
`
`Meijer, ct 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—Michae] 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
`
`GET NEXT SAMPLE
`
`
`
`INITIALIZE SLIDING WINDOW,
`NORTH AND EAST ACCUMULATORS
`
`
`AND TOTAL DISTANCE
`
`
`SHIFT OUT OLD SAMPLE
`
`PUT NEW SAMPLEINTO
`SLIDING WINDOW
`
`
`
`SAVE NEW PEAK TIME
`
`
`ADD STEPSIZE TO TOTAL DISTANCE
`
`
`ADD COS (HEADING) “STEPSIZE TO NORTHACCUMULATOR)
`
`ADD SIN (HEADING) *STEPSIZE TO EASTACCUMULATOR
`
`
`
`
`Google Exhibit 1053
`Google Exhibit 1053
`Google v. Mullen
`Google v. Mullen
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 1 of 8
`
`5,583,776
`
`25
`
`2.0
`
`
`
`
`
`FUNDAMENTALFREQUENCY(Hz)
`
`3.0
`P|te
`
`
`|te
`
`
`wee||
`
`
`
`wTTT|
`Piet
` 0.5
`
`0
`
`4.0
`3.0
`SPEED (MPH)
`
`5.0
`
`| 6.0
`
`7.0
`
`80
`
`FIG. |
`
`ACCELERATION
`
`O.18Ig
`
`TIME
`
`FIG. 2
`
`

`

`US. Patent
`
`Dec. 10, 1996
`
`Sheet 2 of 8
`
`5,583,776
`
`FIG.3 “I
`
`>L
`
`o
`no
`POG
`- Oo
`BNO ~ 2
`Hi Om
`‘“
`x<
`Ya
`
`~]
`
`Hz
`
`E
`a
`Oo x
`x
`Le
`
`itis
`=
`or >
`
`

`

`US. Patent
`
`Dec. 10, 1996
`
`Sheet 3 of 8
`
`5,583,776
`
`INITIALIZE SLIDING WINDOW,
`NORTH AND EAST ACCUMULATORS
`AND TOTAL DISTANCE
`
`
`
`
`
` SHIFT OUT OLD SAMPLE
`
`~PUT NEW SAMPLEINTO
`SLIDING WINDOW
`
`
`
`Y
`
`SAVE NEW PEAK TIME
`
`
`
`
`
`
`
`ADD STEPSIZE TO TOTAL DISTANCE
`
`
`ADD COS (HEADING) *STEPSIZE TO NORTH ACCUMULATOR
`
`
`ADD SIN (HEADING) *STEPSIZE TO EAST ACCUMULATOR
`
`FIG. 4
`
`

`

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

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 5 of 8
`
`5,583,776
`
`
`
`INITIALIZE FFT REAL &
`
`IMAGINARY ARRAYS
`
` 60}
`
`
`
`
`GET NEXT SAMPLE
`
`602
`
`ENOUGH
`
`SAMPLES FOR
`NEXT FFT
`?
`
`603
`
`Y
`
`604
`
`CALCULATE FFT
`
`FIND PEAK FREQUENCY, f
`
`605
`
`606
`
`FIG.6
`
`
`CALCULATE NEW STEPSIZE
`S= SO+m *(f-fO)
`
`
`
`CALCULATE:
`
`
`TOTAL DISTANCE
`
`NORTH DISPLACEMENT
`EAST DISPLACEMENT
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 6 of 8
`
`5,583,776
`
`INITIALIZE STEPSIZE|
`FROM DEFAULTS
`
`70}
`
`102
`
`703
`
`
`104 705
`
`GET NEXT
`STEP PERIOD
`
`
`
` PERIOD
`
`
`SMOOTH STEP
`
`CALCULATE STEP
`FREQUENCY
`
`
`
`CALCULATE NEW
`
`STEPSIZE
`
`FIG. 7
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 7 of 8
`
`5,583,776
`
`START
`
`SELECT FIRST LANDMARK
`MARK ON MAP
`
`AIM AT LANDMARK AND
`PRESS TRIGGER
`
`80!
`
`B02
`
`LOP SHOWN ON MAP
`
`3
`
`80
`
`807
`
`USE ALTIMETER
`INFO TO DETERMINE
`
`POSITION ALONG LOP
`
`
`
`
`
`
`
`AIM AND PRESS TRIGGER[F-~805
`
`LOP SHOWN ON MAP
`
`806
`
`KEEP LATEST LOP
`ON MAP ERASE
`"ANY OTHERS
`
`809
`
`8il
`
`
`
`SELECT NEXT LANDMARK|~ (DONE)804
`
`
`
`
`
`Keawnd>"
`
`Y
`
`CANCEL
`
`CALCULATION POSITION
`AS INTERSECTION OF LOP
`
`CURSOR SELECTS
`POSITION ON MAP
`
`
`
`
`
`

`

`U.S. Patent
`
`Dec. 10, 1996
`
`Sheet 8 of 8 5,583,776
`
`
`
`ENTER BEGINING
`MAP POSITION
`
`90!
`
`WALK TOWARDS
`DESTINATION
`
`(USE CURRENT STEPSIZING
`AND COMPASS OFFSET )
`
`902
`
`CALCULATE NEW
`STEPSIZE
`
`
`
` 907
`
`CALCULATE NEW
`COMPASS OFFSET
`
`FIG. 9
`
`

`

`5,583,776
`
`1
`DEAD RECKONING NAVIGATIONAL
`SYSTEM USING ACCELEROMETER TO
`MEASURE FOOT IMPACTS
`
`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.
`BACKGROUND OF THE INVENTION
`The navigation system of the present invention combines
`a digital electronic compass with bothasilicon pedometer
`1. Field of the Invention
`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 GPSreceiver, 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.
`
`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 theattitude of the accelerom-
`eters and remove the effects of gravity. Results of the
`integration ate added to the starting position to obtain-
`current location. The need for six accurate and stable sensors
`makes the cost of INS high.
`INSposition errors increase with the square of time due
`to the double integration. Theseerrors 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 accuracyare 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 systemsfor
`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 lowercost-
`and powerthan 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 donein this area. Work
`has not been done specifically for foot traveler, hiker, or
`pedestrian use in this area.
`
`SUMMARYOF THE INVENTION
`
`GPSdata 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
`
`25
`
`35
`
`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 pedometercalibration 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 measurementalgorithm 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 ofthe 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
`
`55
`
`60
`
`65
`
`

`

`5,583,776
`
`3
`mechanical pendulum to sense walking motions ofthe 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 embeddedin 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 ofthe 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.
`A Fast Fourier Transform (FFT) spectrum analyzeris 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 ofthe data, and
`recording the fundamental frequency for the hiker at that
`speed.
`A typical spectrum is shown in FIG. 2. This spectrum
`correspondsto a hiker’s acceleration peaks at 3.3 mph. FIG.
`2 showsthat 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 showsa calibration curve resulting from a plot of
`the fundamental frequencies derived via FFT andthe tread-
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`60
`
`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 shownin 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 longerstride.
`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 speedsindicates 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 numberofsteps.
`These two methods maybe 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 windowis 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 oldestfalls off the far end, the new sampleis placed
`in the near end.
`
`Step 404: The middle sample is comparedto all the others.
`If it is greater than therest, 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 thethresh-
`old, another sample is taken.
`Step 406: The time sincethe 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 peaksthat are closer in time than ¥4-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 traveledis
`
`New distance=old distance+step size
`
`The north and cast accumulators are modified as fol-
`lows:
`
`New North=Old North+step size * cosine (heading)
`
`

`

`5
`New East=Old Easttstep 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
`The fftPeriod is the time it took to collect just the new
`from the accelerometer samples to remove gravity effects.
`points, not the whole ensemble. Using the example
`The resulting dynamic component of the data contains the
`above, it would be 128 sample points, not 512.
`useful peak information. The dynamic data is filtered to
`3, Dynamic Step Size Algorithm
`attenuate accelerationsthat are outside the known frequency
`As a user walks faster, both the step size and the fre-
`band of human movement. Measurements have shownthat
`quency ofsteps increases. This can be simply modeled as a
`the fundamental frequencies for normal human walking and
`linear fit
`to observed data at different walking speeds.
`running are below 10 Hz.A peak is noted if the data sample
`Looking at the calibration data shown in FIG. 5, as the
`is the largest value in a set of samples that include times
`numberof steps increases from 1.7 to 2.1 steps per second,
`before and after the peak sample. It also must be larger than
`for example, the step size increases from 0.72 meters (2.36
`a minimum threshold valuc, and must not occur within a set
`feet) to 0.90 meters (2.95 feet). In this example, the fre-
`time period, measured from the previously detected peak.
`quencies span rates fromastroll to a fast walk. The step size
`The user’s stride length is added incrementally to the
`varies by more than 20% under these conditions.
`15
`accumulated distance every time a peak is detected. North
`Since step size directly affects the estimated DR distance,
`and East components of the stride are calculated using data
`the presently preferred embodimentadjusts step size accord-
`from the direction sensor. The componentdisplacements are
`ing to the step frequency. A dynamic scaling algorithm to
`added to separate North and East accumulators, and are used
`improvethe accuracy of distance measurements of a human
`to calculate the total displacement from thestarting point.
`footstep sensor by adjusting the scale factor as a function of
`2. Frequency Measurement Algorithm
`step frequency is thus harnessed by the present invention.
`Refer to flow chart FIG. 7.
`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 fixed number of samples be stored prior to
`analysis. An FFT cannot be performed ona 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.
`
`20
`
`25
`
`30
`
`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: SO, f0, and m. S0 is the default step
`size, f0 is the frequency at which there is no correction
`to SO, 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 overa 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:
`
`fel((step period)
`
`Step 705: The new step size is calculated by:
`
`S=80+m * (f-f0)
`
`B. Directional Correcting and Position Fixing Algorithms
`Incorporating Digitized Maps
`DR errors depend on a numberof 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% ofdistance traveled. According
`to the present invention, calculations were performed to
`determine errors as a percent of distance traveled using
`knownerror sources. An azimuth error of 1 degree due to the
`electronic Compasswill 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. Thepresent 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
`
`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 frequencybin is calcu-
`lated, and the largest of these is identified as the step
`frequency.
`Step 606: As in the peak detection algorithm, minimum
`limits arc 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 checkis passed, then the
`step size is readjusted according to the newly-calcu-
`lated frequency:
`
`S=SO+m*(f-f0)
`
`Step 609: Calculation of Total Displacement and the
`North and East componentsis similar to that in the Peak
`Detection Algorithm, except now it is being done on
`multiple steps overa fixed time period. The individual
`components are scaled by the time period and the step
`frequency. For example:
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`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 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 samefeature, but separated in time and distance, one
`of the azimuths can be advancedor 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 embodimentis 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 pointfor the
`pedometer. The keypad layout and the associated software
`allows the user to exercise the various functions. Features
`are accessed via menu-driven modeselections. 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:
`
`
`POS
`GPS
`
`DR
`
`Show currentposition 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,
`DOPswitching 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 ofcurrent position.
`Show user defined features. Pan, zoom functions.
`Area navigation, range and bearing to features.
`Control display of track androute.
`Create and modify waypoints, routes and user
`defined features.
`Controlthe 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.
`
`
`MAP
`
`NAV
`
`WPT
`
`COM
`
`TIM
`
`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
`
`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 GPSis
`valid, but also accepts manual position fixes by map selec-
`tion or text entry. When GPSis 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 modulesare used to
`select a manual fix location from the map, or to manually
`switch between DR and GPS navigation.
`The navigation software module performsarea 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 userare treated as
`inputs to the navigation module. The navigation module may
`perform switching between DR and GPS navigation auto-
`matically, as conditionsdictate.
`In the presently preferred embodiment, GPS and DR
`sources are selected with a switch scheme depending on
`whether GPSis available. When GPSfixes 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 enteror 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. Thestarting 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 DRstarting
`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. Referto 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 marksit 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 andpresses a trigger switch to indicateto the
`computer to save that compass bearing andto 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 to the designated landmark. The user’s actual
`position lies somewhere alongthe line.
`Step 804: A second landmark is selected and Steps 802
`and 803 are repeated at Steps 805 and 806. The
`intersection of the two LOPsindicates the user’s actual
`position.
`
`10
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`5,583,776
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`9
`Step 807: If the map contains altitude contourlines, the
`altimeter readout may be used to locate the actual
`position alonga single line by noting where the contour
`line crosses the LOP.
`
`Step 808: If more readings are to be taken, the first three
`steps are repeated.
`Step 809: Successive points may be taken, but only the
`two most recent are shown on the digital map.
`Step 810: When done, the user may wish to automatically
`update his position from the intersection of the two
`most recent LOPs. If so, Step 811 is performed auto-
`matically; otherwise he or she may do it manually, or
`quit.
`Step 811: Current position is updated to be the intersec-
`tion of the LOPs.
`
`Step 812: Manual position update is achieved when the
`user movesthe cursor to indicate his present position as
`knownfrom other sources, such as standing at a known
`crossroad or other marker.
`The hand-bearing can also be used to determine a manual
`fix with only one landmark. A “running-fix” or “advanced
`LOP”technique uses two or more hand-bearings to the same
`landmark separated in time. Using DR distance measure-
`ment, the earlier azimuth LOPsar