# Patent

## Title
Floor patterns for navigation corrections

## Abstract

For a vehicle using dead reckoning or some other type of navigation which accumulates error as the vehicle moves, this invention provides a simple, single-sensor, low-cost, highly-accurate system for correcting navigation errors. The system uses a marker structure with optical density which is formed from one or more periodic patterns. The vehicle's navigation computer records the density, measured by the sensor, as the sensor moves on a line over a marker at a known location, then it processes the recorded density function to get the correct navigation parameters. If the vehicle's usual path passes over a marker, that path can be used without change for acquiring navigation corrections.

## Background
CROSS-REFERENCE TO RELATED APPLICATIONS
This patent claims the benefit of U.S. provisional patent No. 62/108,004 filed on Jan. 26, 2015, which is herein incorporated by reference.










U.S. PAT. DOCUMENTS



















4,541,049
September 1985
Ahlbom
Method for updating in a wheeled 
364/424.02





vehicle steered by dead reckoning



4,847,773
July 1989
van Helsdingen
System for navigating a free 
364/443





ranging vehide



5,111,401
May 1992
Everett
Navigational control system for 
364/424.02





an autonomous vehicle











OTHER PUBLICATIONS
Odin, a robot for odometry, http://philohome.com/odin/odin.htm
Bong-Su Cho, Woo-sung Moon, Woo-Jin Seo and Kwang-Ryul Baek,

    
    
        “A dead reckoning localization system for mobile robots using inertial sensors and wheel revolution encoding,” Journal of Mechanical Science and Technology 25 (11) (2011) 2907 2917, Springer
    
    


STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not applicable
REFERENCE TO A SEQUENCE LISTING, A TABLE, OR A COMPUTER PROGRAM LISTING COMPACT DISC APPENDIX
Not applicable
STATEMENT REGARDING PRIOR DISCLOSURE BY THE INVENTOR
There have been no prior disclosures by the inventor.
BACKGROUND OF THE INVENTION
Field of the Invention
This invention relates generally to methods for correcting dead-reckoning navigation errors in vehicles which can move past an area having a patterned position marker. In particular, the area can be on a horizontal floor, such as a warehouse floor or a table top; or it can be on a wall, a ceiling, or some other surface. The present invention describes a class of patterns to be used for markers, and methods that an autonomous robot or other vehicle can use to analyze the patterns for determining coordinates to be used for navigational corrections.
The purpose of this invention is providing a simple, single-sensor, low-cost, highly-accurate system for correcting navigation errors as a vehicle moves without changing direction along a dynamically variable path which crosses one or more two-dimensional patterned markers.
The Prior Art
Mobile robots commonly use odometry for position estimation. From wheel rotation measurements a robot can estimate its direction and travel distance along its path, and use those estimates to approximate its position. It is well known that this dead-reckoning navigation suffers from accumulation of errors, so the use of dead-reckoning for extended travel needs a method for correcting the estimated position. Many methods are known.
For example, a U.S. Pat. No. 4,541,049 by S. H. N. Ahlbom, et al. derives corrections using signals from a vehicle-mounted set of optical sensors arranged in a line as the vehicle crosses known-position lines on the floor. The present invention is simpler in that it uses a single optical sensor.
The robot known as “Odin” (reference: “Odin, a robot for odometry”) uses a related method: the robot optically senses one leg of a known-position L-shaped pattern as it moves into the angle between the two legs, then it turns to cross and sense the other leg; it uses the positions sensed to determine its location. The present invention does not need to make large path direction changes to get the data necessary for navigation corrections.
U.S. Pat. No. 4,847,773 by C. C. van Helsdingen, et al. describes a grid of “passive” markers over which a sensor-equipped vehicle moves, but it does not describe markers with patterns similar to those of the present invention.
U.S. Pat. No. 5,111,401 by H. R. Everett, et al teaches the use of a stripe with position markers at various points; the robot moves until it encounters the stripe, then follows the stripe until it encounters a position marker, which it uses to establish its location by referring to predetermined coordinates of the position markers. The position markers are wider places on the stripe. The patent mentions that the “simplistic marker pattern” can be replaced with a more complex pattern providing unique identification of the marker, but it does not provide a detailed description of any such complex pattern. The present invention does not need stripe following, and it has complete descriptions of position markers.
BRIEF SUMMARY OF THE INVENTION
Overview
The key concept for this invention is the fact that Fourier analysis can reveal features of an object that is the superposition of periodic structures. The prototype for the patterned position marker is a finite, two-dimensional region, such as a circular disk, for which the optical density varies with position in a particular way. It will be apparent to persons familiar with the appropriate art that optical density is not the only characteristic which is appropriate, but using it here simplifies the description. Generally, the optical density will vary periodically in various directions; more precise descriptions of this are given below. For simplicity, in the following the term marker will mean “patterned position marker.”
A vehicle using this invention carries a sensor which measures an average optical density in a small region. The exact nature of the averaging is not important, and the size of the region is not important as long as it is small compared with the sizes of features of the marker pattern, but large enough to reduce signal noise to an acceptable level. As the vehicle moves the sensor reports the measured density to the navigation computer (henceforth, computer) of the vehicle. The computer stores a portion of the measured density as a function f(s) of distance s along the sensor's path, and uses that function to determine corrections of navigation errors. In the following, this function f is called the path-density function, and the term sensor refers to the density sensor just described.
Using Simple Patterns
Some Definitions
FIG. 1 shows a simple-pattern marker 1 with part of the path 2 of the sensor as the vehicle moves past the marker, the dashed parts indicating that the path is incomplete.
Capital letters are used for quantities related to markers, and lower case letters are used for quantities related to the sensor path. Boldface sans-serif letters are used for vectors and points. Thus, points on sensor path 2 are lower-case letters p, p1, p2, etc., whereas the pattern reference point C0=<X0, Y0> on pattern axis 3 is upper case. For descriptions of specific notations, see TABLE 1: LIST OF SYMBOLS USED. Terms specific to this invention are italicized when defined, and shown in TABLE 2: LIST OF TERMS.
For the part of the path shown, the motion starts at point p1, then goes through points p2, p3, p4, and p5, to p6. The part of the path between p2 and p5 is a straight line aligned with unit direction-of-motion vector v. The point p2 is the reference point for distance s (i.e., s=0 at p2) on the straight segment of the sensor's path.
Simple-pattern marker 1 (see FIG. 1) is a circular disk of radius R0 centered at C0. Its optical density varies in the direction of unit orientation vector I0, but is independent of position in the direction of unit vector J0 orthogonal to I0. The counterclockwise angles in radians from the x-axis to I0 and J0 are α0 and α0+π/2, respectively.
Within the marker, the optical density is given by the marker-density function F, which will appear as F(x, y) when it is necessary to show the x and y coordinates. At times it will be convenient to use the notation F(p), where p is the point with coordinates x and y. For a simple-pattern marker, F is a sinusoidal function of position in the direction of I0. The distance between adjacent density peaks measured in the direction of I0 is the wavelength Λ0. The function is independent of position in the direction of J0.
The function F has not been defined outside the circular disk of the marker, but the discussion which follows is simplified if F is extended to the entire x,y-plane. Therefore, let F+ denote the function which, throughout the x,y-plane, is constant on lines parallel to J0, and periodic in the direction of I0; and equals F inside disk 1. The maxima of F+ are on certain lines parallel to J0.
Points p3 and p4 are the points at which path 2 intersects the boundary of 1. Line 3 is the pattern axis; it passes through C0 and is parallel to the orientation vector I0. The counterclockwise angle in radians between I0 and v is θ0 satisfying 0≦θ0<2π.
As the sensor moves along the straight-line path across the marker it will report a density which is sinusoidal with wavelength λ0. If cos(θ0)≠0, λ0 satisfies |cos(θ0)|λ0=Λ0. The following discussion uses angular frequencies ω0=2π/λ0 and Ω0=2π/Λ0. Thus

ω0=|cos(θ0)|Ω0.  (1)

In FIG. 1, there are 12 cycles of the density across the disk, so Λ0=R0/6, and Ω0=12π/R0. Values of Ω0 of about this size will be used in the figures, but practical applications will have much higher values of Ω0.
The density reported by the sensor is a function of x and y, but since it is measured on the sensor's path, the computer stores it as periodic samples of the path-density function f(s). On the part of the path intersecting disk 1

f(s)=a cos(ω0s+ψ0)+b,  (2)

where a, b, and ψ0 are constants with b≧|a| and 0≦ψ0<2π.

The function F(x, y) is anchored to the x, y-axes and C0, but f(s) is not. Instead, v and p2 determine its relationship to F(x, y), hence to the x, y-axes and C0. Therefore, f(s) carries some information about where the path is located. The computer has approximate values {tilde over (p)}2 and {tilde over (θ)}2 for p2, and θ0, respectively. The angle {tilde over (θ)}0 determines a unit vector {tilde over (v)} which is an approximation of v. The goal is to use f(s) to get {tilde over (θ)}0 and δ0, the latter being the component of the displacement δ={tilde over (p)}2−p2 in the direction of I0. The method for this involves mathematical concepts described in the following.
Mathematics for Getting Position and Direction from Phase and Frequency
An expression for F(p) on the path between p2 and p5 will be obtained, then that will be related to f(s).
For a point p (e.g., on the sensor's path), let S(p) denote the signed distance (positive toward I0) from C0 to the orthogonal projection P of p onto line 3. The reader is reminded that since I0 is a unit vector, the dot product (p−C0)−I0 is the (signed) length of the projection of the line segment from C0 to p onto line 3, and δ0=δ·I0, so

P=C0+((p−C0)·I0)I0,

and

S(p)=(p−C0)·I0.  (3)

The value of the function F+(p) at p is determined by S(p). Let φ0 be the phase at C0, so

F+(p)=A cos(Ω0S(p)+φ0)+B,  (4)

where A and B are constants associated with the pattern. Usually, B≧|A| so that F(p) is always nonnegative.

Between p2 and p5 on the sensor's path, p is a function of s given by p(s)=p2+sv, so from equations (2) and (4),

a cos(ω0s+ψ0)+b=f(s)=F+(p(s))=A cos(Ω0S(p(s))+φ0)+B,  (5)

which is true while p(s) is between p3 and p4.

An early part of the computer processing of f is removal of the DC component b by any well-known technique (high-pass filtering, finding the average value b and subtracting it from f, etc.). Thus, in the following, without loss of generality, b, and B will be taken to be zero. Also, it is obvious that the cosine amplitudes must be equal: a=A. Therefore, the cosine factors in equation (5) are equal:

cos(ω0s+ψ0)=cos(Ω0S(p(s))+φ0) for p(s) between p3 and p4.

Since this is true over an extended interval of s, the arguments of the cosines are equal except for an additive multiple of 2π to account for the periodicity of the cosines. Thus, from equation (3),

ω0s+ψ0=Ω0(p(s)−C0)·I0+φ0−m2π,  (6)

where m is an integer. In particular, since p(0)=p2, for s=0 equation (6) is

ψ0=Ω0(p2−C0)·I0+φ0−m2π.  (7)

This can be rearranged and applied to the definition of δ0 to get

δ0=({tilde over (p)}2−p2)·I0=({tilde over (p)}2−C0)·I0+(φ0−ψ0−2πm)/Ω0.  (8)

Therefore, if ψ0 and m can be found, any position can be partially corrected by subtracting δ0I0 from it. In particular, the partially-corrected {tilde over (p)}2 is {tilde over (p)}2−δ0I0.
A single simple-pattern marker does not, by itself, provide enough information to determine m but there is a condition under which m can be computed. Rearrange equation (8) to get (since Ω0=2π/Λ0)




  
    
      
        m
        =
        
          
            
              1
              
                Λ
                0
              
            
            ⁢
            
              
                (
                
                  
                    
                      p
                      ~
                    
                    2
                  
                  -
                  
                    C
                    0
                  
                
                )
              
              ·
              
                I
                0
              
            
          
          +
          
            
              1
              
                2
                ⁢
                π
              
            
            ⁢
            
              (
              
                
                  φ
                  0
                
                -
                
                  ψ
                  0
                
              
              )
            
          
          -
          
            
              
                δ
                0
              
              
                Λ
                0
              
            
            .
          
        
      
    
    
      
        (
        9
        )
      
    
  




If

|δ0|<Λ0/2,  (10)

then m is the nearest integer to the right side of (9) with δ0=0; i.e.,





  
    
      
        m
        =
        
          
            Round
            ⁡
            
              (
              
                
                  
                    1
                    
                      Λ
                      0
                    
                  
                  ⁢
                  
                    
                      (
                      
                        
                          
                            p
                            ~
                          
                          2
                        
                        -
                        
                          C
                          0
                        
                      
                      )
                    
                    ·
                    
                      I
                      0
                    
                  
                
                +
                
                  
                    1
                    
                      2
                      ⁢
                      π
                    
                  
                  ⁢
                  
                    (
                    
                      
                        φ
                        0
                      
                      -
                      
                        ψ
                        0
                      
                    
                    )
                  
                
              
              )
            
          
          .
        
      
    
    
      
        (
        11
        )
      
    
  




The restriction on δ0 is too severe for most applications. Markers comprising superposed patterns, described below, have much weaker restrictions.

The computer will have the following information about the marker: the coordinates X0 and Y0 of the marker reference point C0, the orientation vector I0, the angular frequency Ω0, and the phase φ0 at C0. All of these values, collectively called the marker parameters, are determined at the time of installation of the position marker, then delivered to the computer.
Under condition (10), after ψ0 has been found, the computer can use equation (11) to get m, then use m in equation (8) to get δ0. Then the corrected value of {tilde over (p)}2 is {tilde over (p)}2−δ0I0.
After ω0 has been found, the computer can use it in equation 1 to put restrictions on the approximation {tilde over (θ)}0 to θ0. This does not work well when |d cos({tilde over (θ)}0)/d{tilde over (θ)}0| is close to zero (i.e., when {tilde over (θ)}0 is close to 0 or π).
A given value of ω0 determines several values of {tilde over (θ)}0, however: if {tilde over (θ)}0 is a solution satisfying 0<{tilde over (θ)}0<π, then each of π+{tilde over (θ)}0, π−{tilde over (θ)}0, and 2π−{tilde over (θ)}0 is a solution. Nevertheless, if one of these values is close enough to the current value of θ0 it can be used for the revised value of {tilde over (θ)}0. Usually, this is the case if θ0 and {tilde over (θ)}0 are reasonably close to the same one of π/4, 3π/4, 5π/4, and 7π/4. Therefore, it is best if the path crosses the marker with θ0 close to one of these values.
Getting the Frequency and Phase
The computer uses odometry to measure s and to estimate the sensor's position {tilde over (p)}and direction of motion {tilde over (v)} (at angle {tilde over (θ)}0). When it starts on the straight segment from p2 to p3 it stores {tilde over (p)} as {tilde over (p)}2, an approximation to p2.
After the sensor has passed over the marker, the computer determines ω0 and ψ0 by some means. In principle, the frequency ω0 and phase ψ0 can be determined by finding the midlevel points of f, and doing some simple calculations. This is a poor method because it is relatively sensitive to random errors (e.g., optical noise from dirt or breaks in the density pattern).
Consider, instead, using the Fourier transform {circumflex over (f)}(ω) of the stored path-density function f. Since the complex representation of the cosine is




  
    
      cos
      ⁡
      
        (
        γ
        )
      
    
    =
    
      
        1
        2
      
      ⁢
      
        (
        
          
            e
            jγ
          
          +
          
            e
            
              -
              jγ
            
          
        
        )
      
    
  
  ,




where j is the imaginary unit (j2=−1), f(s) can be written (with b=0; see equation (2))





  
    
      
        
          
            f
            ⁡
            
              (
              s
              )
            
          
          =
          
            
              a
              2
            
            ⁢
            
              (
              
                
                  e
                  
                    j
                    ⁡
                    
                      (
                      
                        
                          
                            ω
                            0
                          
                          ⁢
                          s
                        
                        +
                        
                          ψ
                          0
                        
                      
                      )
                    
                  
                
                +
                
                  e
                  
                    -
                    
                      j
                      ⁡
                      
                        (
                        
                          
                            
                              ω
                              0
                            
                            ⁢
                            s
                          
                          +
                          
                            ψ
                            0
                          
                        
                        )
                      
                    
                  
                
              
              )
            
          
        
        ,
      
    
    
      
        (
        12
        )
      
    
  




so {circumflex over (f)}(ω) is zero except at two points:

{circumflex over (f)}+=caejψ0 at ω=ω0,

and

{circumflex over (f)}−=cae−jψ0 at ω=−ω0,  (13)

where c is a positive constant determined by the form of the Fourier transform used.

Therefore, to get both ω0 and ψ0, the computer can examine the values of {circumflex over (f)}(ω) for ω>0 to find the nonzero value at ω0, then evaluate

ψ0=arc tan(Im({circumflex over (f)}+(ω0))/Re({circumflex over (f)}+(ω0))),  (14)

where Re(•) and Im(•) extract the real and imaginary parts, respectively.

It will be apparent to persons familiar with the appropriate art that since the computer stores discrete samples it should use the Discrete Fourier Transform (DFT) instead of the continuous-domain Fourier transform appearing in the discussion above. Application of the DFT is illustrated in FIGS. 2 and 3, which, for purposes of illustration, show functions with continuous lines instead of discrete points.
FIG. 2 shows path-related functions, and FIG. 3 shows features of corresponding DFTs. The function ω is the window function which multiplies the extended density function f+ to produce the path-density function f that the sensor reports. FIG. 2 shows the wavelength λ0 expressed in terms of the corresponding angular frequency ω0.
The functions {circumflex over (f)}+ and {circumflex over (f)}, which are the DFTs of f+ and f, respectively, are complex functions of ω. For simplicity, FIG. 3 shows |{circumflex over (f)}+| and |{circumflex over (f)}|, the absolute values of these functions. The graphs of the functions and the discussion that follows have been simplified by ignoring the fact that the DFT might not be computed over the entire span from p3 to p4, or over an integral number of cycles of the function f+.
Multiplication of functions implies convolution of their DFTs. In particular, {circumflex over (f)} is the convolution of {circumflex over (f)}+ and {circumflex over (ω)}, the DFT of ω. The latter is a multiple of a sinc function, so |{circumflex over (f)}| is a multiple of the absolute value of a sinc function translated so its center is at ω0, as shown in FIG. 4. The width of the central peak is inversely proportional to the distance between p3 and p4.
The computer can use |{circumflex over (f)}| to determine ω0, either from the position of the peak, or by determining the centroid of the function. The latter should be more accurate if certain precautions are taken, such as using only that part of the function in the central peak. After getting ω0, the computer can determine ψ0 as indicated in equation (14).
Some details that will be apparent to persons familiar with the appropriate art have been omitted. The graphs in FIG. 4 are drawn as if the DC components of f+ and f have been removed.
Since the method for determining the frequency and phase integrates measured values (by summation, through the DFT), the accuracy is better than that of methods that use single point measures. It is also much less sensitive to noise.
Using Multiple Simple Patterns
The method just described fails if the vector v is nearly orthogonal to I0. One way to provide for complete correction is to have the sensor path pass across several markers. This is illustrated in FIG. 4, in which the sensor path 8 passes sequentially across markers 5, 6, and 7 as the sensor moves from p1 to p6. The patterns are rotated from each other, as indicated by the orientation vectors I1, I2, and I3. Each of markers 5 and 7 provide coordinate corrections in the directions of their orientation vectors.
Marker 6 cannot be used for corrections because I2 is nearly orthogonal to the direction of motion. It is easy to see that the corresponding path wavelength λ2 is very large, and that only two full cycles of the density sinusoid are crossed, so the determination of λ2 would not be accurate. Better rotations of the three markers can be found.
A main disadvantage of the arrangement of FIG. 4 is that the sensor path is restricted. As will be shown below, it is possible to construct a single marker by superposing several patterns of the type being used in FIG. 1 and FIG. 4.



BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS
FIG. 1 shows a patterned position marker and the path of the density sensor passing over it.
FIG. 2 displays the path-density function and some related functions.
FIG. 3 displays discrete Fourier transforms (DFTs) of some functions in FIG. 3.
FIG. 4 shows the sensor path crossing three position markers with different orientations.
FIG. 5 has two patterns with different wavelengths, and a marker made by superposing them, with the path of a density sensor passing over the marker.
FIG. 6 shows the path-density function of a sensor passing over a marker comprising two superposed patterns of different wavelengths.
FIG. 7 displays the discrete Fourier transform (DFT) of the path-density function in FIG. 6.
FIG. 8 exhibits the dependency of the frequencies on the direction of motion.
FIG. 9 shows the path-density function of a sensor passing over a marker comprising two superposed patterns of different wavelengths and different orientations.
FIG. 10 displays the DFT of the path-density function in FIG. 9.
FIG. 11 exhibits the dependency of the path-density-function frequencies on the direction of motion for a marker of two patterns with different wavelengths and different orientations.
FIG. 12 displays the geometry of a marker comprising two patterns with different orientations.



DETAILED DESCRIPTION OF THE INVENTION
This description is divided into several sections and it uses technical abbreviations, so the following lists are provided as an aid to the reader. Other than in Table 2, below, the first time an abbreviation is used, it is put in parentheses after its definition.
1. Tables
Table of Contents
1. TABLES 

    
    
        TABLE OF CONTENTS 
        TABLE 1: LIST OF SYMBOLS USED 
        TABLE 2: LIST OF TERMS 
    
    


2. SUPERPOSING ALIGNED PATTERNS 
3. SUPERPOSING UNALIGNED PATTERNS 
4. USING HIGH-CONTRAST MEDIA 
5. OTHER CONSIDERATIONS 







TABLE 1







LIST OF SYMBOLS USED


In this list k is the numerical index of a patterned position marker;


it can be blank; in some cases it can be a pair of indices.








Symbol
Meaning










Mathematical Notation








<x, y>
The point (or vector) with coordinate components x and y; e.g., δ = <δx, δy>.


┌·┐
The ceiling function: ┌r┐ is the smallest integer ≧ r.


Round
Round to the nearest integer, ties rounding down: Round(u) = ┌u − 1⁄2┐.


U · V
For any vectors U and V, the dot product U · V = UxVx + UyVy.


k ∈ { . . . }
k is one of the members of the set { . . . }; e.g., k ∈ {1, 2, 3} means k is 



1,2, or 3







Symbols for the Patent 








αk
The angle between the positive x axis and the pattern orientation vector Ik.


δk
Offset in the direction Ik of the estimated coordinates from the true coordinates.


θk
The counterclockwise angle in radians between Ik and v with 0 ≦ θk < 2π.


{tilde over (θ)}k
The computer's estimate of θk.


λk
Wavelength of the path-density function fk.


Λk
Wavelength of the pattern-density function Fk(x, y).


φk
The phase of Fk+ at Ck: Fk+ (Ck) = A cos(φk) + Bk.


ψk
Phase of fk(s) at s = 0.


ωk
The angular frequency corresponding to λk (thus, ωk = 2π/λk).


Ωk
The angular frequency corresponding to Λk (thus, Ωk = 2π/Λk).


f
The path-density function.


f+
The periodic extension of f to the entire s axis.


{circumflex over (f)}
The discrete Fourier transform (DFT) of f.


s
The distance along the sensor path from p2.


v
The direction-of-motion vector for the density sensor on the segment from 



p2 to p5.


{tilde over (v)}
The computer's estimate of v.


Ck
The pattern reference point <Xk,Yk> of pattern k.


Ik
The orientation vector of pattern k.


Jk
The vector orthogonal to and on the left side of Ik.


Fk
The pattern density function of pattern k.


Fk+
The periodic extension of Fk to the entire x, y-plane.


Rk
Radius of the position marker pattern (when circular).


δ
The displacement vector of p2: δ = {tilde over (p)}2 − p2.


p
A point on the sensor path, especially the sensor location.


{tilde over (p)}
The computer's estimate of p.


p1
Starting point of the sensor path in the figures.


p2
Starting point of the straight path segment crossing a position marker;



used as a reference point for s (s = 0 at p2).


p4
Last point at which the straight path segment meets the position marker;


p5
Ending point of the straight path segment crossing the position marker;


p6
Ending point of the sensor path in the figures.


Pk
The projection of p on pattern axis Ik


{tilde over (p)}2
The computer's approximation of p2.


S(p)
Distance from C0 to P: S(p) = (p − C0) · I0
















TABLE 2







LIST OF TERMS











Meaning, Example, 


Paragraph
Term
Symbol, or Comment












8
marker
patterned position marker


9
sensor
optical density sensor


9
path-density function
f


9
computer
navigation computer


11
pattern reference point
Ck


11
pattern axis
line 3 in FIG. 1; 




lines 33, and 34 in FIG. 12


12
direction-of-motion vector
v


13
orientation vector
Ik


14
pattern-density function
Fk


20
displacement
δ


27
marker parameters
Xk, Yk, Ik, Ωk, and φk


58
underlying navigation
e.g., dead reckoning


60
superposing
F3 = A F1 + B F2 + C









2. Superposing Aligned Patterns
No matter what form of navigation (called underlying navigation in the following), dead-reckoning or some other, is used to estimate the instantaneous position of the vehicle, operation of the vehicle must provide for the sensor to cross a position marker properly. Thus, the line from p2 to p5 must pass reasonably close to the center of the marker; within one-half of the radius of the marker may be sufficient.
As discussed above, for the geometry shown in FIG. 1, avoiding phase ambiguity requires the underlying navigation to insure that the orthogonal projection of {tilde over (p)}2 on line 3 is within Λ0/2 of the corresponding projection of p2; i.e., that |δ|<Λ0/2. This reqirement is too severe in many applications.
The |δ|<Λ0/2 restriction can be relieved if there is a second marker pattern which provides for phase identification over a wider range. This can be done by superposing two or more patterns. The term superposing means combining the patterns by weighted addition of their density functions and adjustment of the DC component to produce the final pattern.
This is illustrated in FIG. 5, in which the pattern density function F3 of marker 11 is the weighted sum of the density functions F1 and F2 of patterns 12 and 13, respectively. Specifically, for FIG. 5

F3(x, y)=A(F1(x, y)+0.75 F2(x, y))+B,  (15)

where A and B are constants. The orientation vectors, Ik for k=1, 2, and 3, are all rotated 15 degrees from the x-axis (so I1=I2=I3). The direction-of-motion vector v is rotated 20 degrees from the orientation vectors, so the two path frequencies are ω1=cos(20°)Ω1 and ω2=cos(20°)Ω2 (see equaion (1)). Points p2, p3, p4, and p5, are the same as in FIG. 1. FIG. 5 shows the wavelengths Λ1, Λ2, and Λ3 corresponding to Ω1, Ω2, and Ω3, respectively; Ω3=(Ω1−Ω2)/2.

The path-density function f of FIG. 5 and the absolute value |{circumflex over (f)}| of its DFT are shown in FIG. 6 and FIG. 7. From the two peaks in FIG. 7 the computer can determine the frequencies ω1 and ω2, and the phases ψ1 and ψ2 of the two components of the path-density function.
This can be generalized to the superposition of L≧2 patterns with angular frequencies Ωl, and orientation vectors Il for l=1, 2, . . . , L. Here it will be assumed that the Il are all equal.
There are L equations, one for each pattern, corresponding to equation (8):

δ1=({tilde over (p)}2−Cl)·Il+(φl−ψl−2πml)/Ωl, for l∈{1,2, . . . , L},  (16)

where 0≦ψl<2π, and ml is an integer (there is only one δ1 because all Il=I1; all Il are shown, however). Combine these as follows. For l∈{1, 2, . . . , L} let nl be an integer. Multiply equation (16) by nlΩl, then add the equations together and rearrange the sum to get





  
    
      
        
          
            δ
            1
          
          =
          
            
              1
              
                
                  ∑
                  
                    l
                    =
                    1
                  
                  L
                
                ⁢
                
                  
                    n
                    l
                  
                  ⁢
                  
                    Ω
                    l
                  
                
              
            
            ⁢
            
              (
              
                
                  
                    ∑
                    
                      l
                      =
                      1
                    
                    L
                  
                  ⁢
                  
                    (
                    
                      
                        n
                        l
                      
                      ⁡
                      
                        (
                        
                          
                            
                              
                                Ω
                                l
                              
                              ⁡
                              
                                (
                                
                                  
                                    
                                      p
                                      ~
                                    
                                    2
                                  
                                  -
                                  
                                    C
                                    l
                                  
                                
                                )
                              
                            
                            ·
                            
                              I
                              l
                            
                          
                          +
                          
                            (
                            
                              
                                φ
                                l
                              
                              -
                              
                                ψ
                                l
                              
                            
                            )
                          
                        
                        )
                      
                    
                    )
                  
                
                -
                
                  2
                  ⁢
                  π
                  ⁢
                  
                    
                      ∑
                      
                        l
                        =
                        1
                      
                      L
                    
                    ⁢
                    
                      
                        n
                        l
                      
                      ⁢
                      
                        m
                        l
                      
                    
                  
                
              
              )
            
          
        
        ,
      
    
    
      
        (
        17
        )
      
    
  




which can be rearranged into





  
    
      
        
          
            ∑
            
              l
              =
              1
            
            L
          
          ⁢
          
            
              n
              l
            
            ⁢
            
              m
              l
            
          
        
        =
        
          
            
              ∑
              
                l
                =
                1
              
              L
            
            ⁢
            
              (
              
                
                  n
                  l
                
                ⁡
                
                  (
                  
                    
                      
                        1
                        
                          Λ
                          l
                        
                      
                      ⁢
                      
                        
                          (
                          
                            
                              
                                p
                                ~
                              
                              2
                            
                            -
                            
                              C
                              l
                            
                          
                          )
                        
                        ·
                        
                          I
                          l
                        
                      
                    
                    +
                    
                      
                        1
                        
                          2
                          ⁢
                          π
                        
                      
                      ⁢
                      
                        (
                        
                          
                            φ
                            l
                          
                          -
                          
                            ψ
                            l
                          
                        
                        )
                      
                    
                  
                  )
                
              
              )
            
          
          -
          
            
              δ
              1
            
            ⁢
            
              
                ∑
                
                  l
                  =
                  1
                
                L
              
              ⁢
              
                
                  
                    n
                    l
                  
                  
                    Λ
                    l
                  
                
                .
              
            
          
        
      
    
    
      
        (
        18
        )
      
    
  




The left side of this is an integer, so if





  
    
      
        
          
          
            δ
            1
          
          
        
        <
        
          
            1
            2
          
          ⁢
          
            
              
              
                
                  ∑
                  
                    l
                    =
                    1
                  
                  L
                
                ⁢
                
                  
                    n
                    l
                  
                  
                    Λ
                    l
                  
                
              
              
            
            
              -
              1
            
          
        
      
    
    
      
        (
        19
        )
      
    
  




then





  
    
      
        
          
            ∑
            
              l
              =
              1
            
            L
          
          ⁢
          
            
              n
              l
            
            ⁢
            
              m
              l
            
          
        
        =
        
          
            Round
            ⁡
            
              (
              
                
                  ∑
                  
                    l
                    =
                    1
                  
                  L
                
                ⁢
                
                  
                    n
                    l
                  
                  ⁡
                  
                    (
                    
                      
                        
                          1
                          
                            Λ
                            l
                          
                        
                        ⁢
                        
                          
                            (
                            
                              
                                
                                  p
                                  ~
                                
                                2
                              
                              -
                              
                                C
                                l
                              
                            
                            )
                          
                          ·
                          
                            I
                            l
                          
                        
                      
                      +
                      
                        
                          1
                          
                            2
                            ⁢
                            π
                          
                        
                        ⁢
                        
                          (
                          
                            
                              φ
                              l
                            
                            -
                            
                              ψ
                              l
                            
                          
                          )
                        
                      
                    
                    )
                  
                
              
              )
            
          
          .
        
      
    
    
      
        (
        20
        )
      
    
  




As before (see the text following equation (11)), after ψl has been found for l∈{1, . . . L}, if condition (19) is satisfied, the computer can get Σl=1L nlml, then δ1, and partially correct {tilde over (p)}2 to {tilde over (p)}2−δ1I0.
Condition (19) is much better than the one (|δ0|<Λ0/2) for a single pattern. For example, with L=2, Λ1=Λ0, and Λ2=Λ1/0.8, the values for FIGS. 5, 6, and 7, with n1=1, if n2=−1, the right hand side of (19) is 2.5 Λ0, which is 5 times larger than the other bound. With other choices of the frequencies it can be much larger.
The text after equation (11) applies mutatis mutandis to ψl, ωl, etc.
FIG. 8 shows how the path frequencies ω1 and ω2 change as the direction-of-motion vector v changes. Since ω1 and ω2 are periodic, the figure shows only one period. Near θ=20° there is enough variation of the path frequencies that equation (1) with ω0 replaced by either ω1 or ω2 can be used for accurate correction of θ0, but that is not true at θ=0° where dω1/dθ=dω2/dθ=0. Another extreme is near θ=±90°, where ω1 and ω2 are so small that there is no useful information about θ0 (as is the case with position marker 6 in FIG. 4). This kind of graph will be seen again in the following.
3. Superposing Unaligned Patterns
Consider a marker which is the same as that of FIG. 5 except that patterns 12 and 13 are rotated so that, say, α1=15° (i.e., 12 is unchanged) and α2=60°. Then the two patterns provide information about coordinate errors in two different directions, so the coordinates can be corrected completely.
FIG. 9 and FIG. 10 show the path-density function f and the absolute value |{circumflex over (f)}| of its DFT, respectively, for this arrangement. The peaks of |{circumflex over (f)}| are somewhat farther apart than those of FIG. 7. FIG. 11 shows how the wavelengths ω1 and ω2 change as the angle-of-motion θ changes.
Consider a marker with L≧2 pattern axes. For each l∈{1, . . . , L}, the displacement vector δ={tilde over (p)}2−p2 has a component δl=δ·Il along Il. Given δl for all l∈1, . . . , L, δ can be found by taking δ=Σl=1L alIl and solving the simultaneous linear equations

δl=δ·Il, for l∈{1, . . . , L}.  (21)

for a1, . . . , aL.

FIG. 12 shows the geometrical relationships for two pattern axes, but omits the marker pattern, which is represented by its boundary circle 31. Line 32 is the sensor path. The pattern axes are line 33 for the axis associated with Il, and line 34 for the axis associated with Ii. The orientation vectors Il and Ii are at angles αl and αi from the positive x-axis, respectively. The angles from Il and Ii to the direction-of-motion vector v are θl and θi, respectively; for purposes of illustration, θi is shown as negative, but all calculations assume that both θl and θi are in [0, 2π).
For FIGS. 9, 10, and 11 the pattern for each of I1 and I2 is sinusoidal with a single frequency. As was noted earlier, this severely restricts the size of the displacement.
Instead, in the following, each pattern axis Il has Kl≧1 associated patterns. For each k∈{1, . . . , Ki} the pattern has refernce point Clk, angular frequency Ωlk, phase ψlk at Clk, and corresponding path frequency ωlk; and for each of these patterns there is an equation like equation (16) for δl=({tilde over (p)}2−p2)·Il, the displacement in the direction of Il. Let Jl be the unit vector orthogonal to Il and pointing to the left of Il. Then there are numbera ali and bli such that Ii=aliIl+bliJl. Note that all=1 and bll=0. FIG. 12 shows vectors Ji and Jl.
There are integers mik such that equation (7) mutatis mutandis becomes

Ωik(p2−Cik)·Ii=−φik+ψik+2πmik for i∈{1,2, . . . , L} and k∈{1,2, . . . , Ki}.  (22)

Since

(p2−Cik)·Ii=(p2−{tilde over (p)}2+{tilde over (p)}2−Cik)·Ii=−δ·(aliIl+bliJl)+({tilde over (p)}2−Cik)·Ii=−aliδl−bliδ·Jl+({tilde over (p)}2−Cik)·Ii

equation (22) can be rewritten as





  
    
      
        
          
            
              δ
              l
            
            ⁢
            
              
                
                  Ω
                  ik
                
                ⁢
                
                  a
                  li
                
              
              
                2
                ⁢
                π
              
            
          
          =
          
            
              
                
                  Ω
                  ik
                
                
                  2
                  ⁢
                  π
                
              
              ⁢
              
                (
                
                  
                    
                      (
                      
                        
                          
                            p
                            ~
                          
                          2
                        
                        -
                        
                          C
                          ik
                        
                      
                      )
                    
                    ·
                    
                      I
                      i
                    
                  
                  -
                  
                    
                      b
                      li
                    
                    ⁢
                    
                      δ
                      ·
                      
                        J
                        l
                      
                    
                  
                
                )
              
            
            +
            
              
                1
                
                  2
                  ⁢
                  π
                
              
              ⁢
              
                (
                
                  
                    φ
                    ik
                  
                  -
                  
                    ψ
                    ik
                  
                
                )
              
            
            -
            
              m
              ik
            
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            
              for
              ⁢
              
                
              
              ⁢
              i
            
            ∈
            
              {
              
                1
                ,
                2
                ,
                ...
                ⁢
                
                  
                
                ,
                L
              
              }
            
          
          ,
          
            k
            ∈
            
              
                {
                
                  1
                  ,
                  2
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  
                    K
                    i
                  
                
                }
              
              .
              l
            
            ∈
            
              {
              
                1
                ,
                2
                ,
                ...
                ⁢
                
                  
                
                ,
                L
              
              }
            
          
        
        ⁢
        
          
        
        ⁢
        
          

        
        ⁢
        
          
        
        ⁢
        
          
            and
            ⁢
            
              
            
            ⁢
            
              a
              li
            
          
          ≠
          0
        
      
    
    
      
        (
        23
        )
      
    
  




(omit any of these equations with ali=0).

Combine all of these equations to get a single equation for δl: choose integers nlik, multiply the equation by them, and sum on i and k to get




  
    
      
        
          
            δ
            l
          
          ⁢
          
            
              ∑
              
                
                  i
                  =
                  1
                
                
                  
                    a
                    li
                  
                  ≠
                  0
                
              
              L
            
            ⁢
            
              
                ∑
                
                  k
                  =
                  1
                
                
                  K
                  i
                
              
              ⁢
              
                
                  
                    n
                    lik
                  
                  ⁢
                  
                    Ω
                    ik
                  
                  ⁢
                  
                    a
                    li
                  
                
                
                  2
                  ⁢
                  π
                
              
            
          
        
        =
        
          
            
              
                ∑
                
                  
                    i
                    =
                    1
                  
                  
                    
                      a
                      li
                    
                    ≠
                    0
                  
                
                L
              
              ⁢
              
                
                  ∑
                  
                    k
                    =
                    1
                  
                  
                    K
                    i
                  
                
                ⁢
                
                  
                    
                      
                        n
                        lik
                      
                      ⁢
                      
                        Ω
                        ik
                      
                    
                    
                      2
                      ⁢
                      π
                    
                  
                  ⁢
                  
                    (
                    
                      
                        
                          (
                          
                            
                              
                                p
                                ~
                              
                              2
                            
                            -
                            
                              C
                              ik
                            
                          
                          )
                        
                        ·
                        
                          I
                          i
                        
                      
                      -
                      
                        
                          b
                          li
                        
                        ⁢
                        
                          δ
                          ·
                          
                            J
                            l
                          
                        
                      
                    
                    )
                  
                
              
            
            +
            
              
                ∑
                
                  
                    i
                    =
                    1
                  
                  
                    
                      a
                      li
                    
                    ≠
                    0
                  
                
                L
              
              ⁢
              
                
                  ∑
                  
                    k
                    =
                    1
                  
                  
                    K
                    i
                  
                
                ⁢
                
                  
                    
                      n
                      lik
                    
                    
                      2
                      ⁢
                      π
                    
                  
                  ⁢
                  
                    (
                    
                      
                        φ
                        ik
                      
                      -
                      
                        ψ
                        ik
                      
                    
                    )
                  
                
              
            
            -
            
              
                ∑
                
                  
                    i
                    =
                    1
                  
                  
                    
                      a
                      li
                    
                    ≠
                    0
                  
                
                L
              
              ⁢
              
                
                  ∑
                  
                    k
                    =
                    1
                  
                  
                    K
                    i
                  
                
                ⁢
                
                  
                    n
                    lik
                  
                  ⁢
                  
                    m
                    ik
                  
                  ⁢
                  
                    
                  
                  ⁢
                  for
                  ⁢
                  
                    
                  
                  ⁢
                  l
                
              
            
          
          ∈
          
            
              {
              
                1
                ,
                2
                ,
                ...
                ⁢
                
                  
                
                ,
                L
              
              }
            
            .
          
        
      
    
    
      
        (
        24
        )
      
    
  




If the last term can be computed, this can be solved for δl. As before, since the last term is an integer, for each l∈{1, 2, . . . , L}





  
    
      
        
          
            
              ∑
              
                
                  i
                  =
                  1
                
                
                  
                    a
                    li
                  
                  ≠
                  0
                
              
              L
            
            ⁢
            
              
                ∑
                
                  k
                  =
                  1
                
                
                  K
                  i
                
              
              ⁢
              
                
                  n
                  lik
                
                ⁢
                
                  m
                  ik
                
              
            
          
          =
          
            
              Roun
              ⁢
              d
            
            ⁢
            
              (
              
                
                  ∑
                  
                    
                      i
                      =
                      1
                    
                    
                      
                        a
                        li
                      
                      ≠
                      0
                    
                  
                  L
                
                ⁢
                
                  
                    ∑
                    
                      k
                      =
                      1
                    
                    
                      K
                      i
                    
                  
                  ⁢
                  
                    
                      
                        
                          n
                          lik
                        
                        ⁢
                        
                          Ω
                          ik
                        
                      
                      
                        2
                        ⁢
                        π
                      
                    
                    ⁢
                    
                      (
                      
                        
                          
                            (
                            
                              
                                
                                  p
                                  ~
                                
                                2
                              
                              -
                              
                                C
                                ik
                              
                            
                            )
                          
                          ·
                          
                            I
                            i
                          
                        
                        +
                        
                          
                            
                              n
                              lik
                            
                            
                              2
                              ⁢
                              π
                            
                          
                          ⁢
                          
                            (
                            
                              
                                φ
                                ik
                              
                              -
                              
                                ψ
                                ik
                              
                            
                            )
                          
                        
                      
                      )
                    
                  
                
              
              )
            
          
        
        ,
      
    
    
      
        (
        25
        )
      
    
  




provided





  
    
      
        
          
          
            
              
                δ
                l
              
              ⁢
              
                
                  ∑
                  
                    
                      i
                      =
                      1
                    
                    
                      
                        a
                        li
                      
                      ≠
                      0
                    
                  
                  L
                
                ⁢
                
                  
                    ∑
                    
                      k
                      =
                      1
                    
                    
                      K
                      i
                    
                  
                  ⁢
                  
                    
                      
                        n
                        lik
                      
                      ⁢
                      
                        Ω
                        ik
                      
                      ⁢
                      
                        a
                        li
                      
                    
                    
                      2
                      ⁢
                      π
                    
                  
                
              
            
            +
            
              
                δ
                ·
                
                  J
                  l
                
              
              ⁢
              
                
                  ∑
                  
                    
                      i
                      =
                      1
                    
                    
                      
                        a
                        li
                      
                      ≠
                      0
                    
                  
                  L
                
                ⁢
                
                  
                    ∑
                    
                      k
                      =
                      1
                    
                    
                      K
                      i
                    
                  
                  ⁢
                  
                    
                      
                        
                          n
                          lik
                        
                        ⁢
                        
                          Ω
                          ik
                        
                      
                      
                        2
                        ⁢
                        π
                      
                    
                    ⁢
                    
                      b
                      li
                    
                  
                
              
            
          
          
        
        <
        
          
            1
            2
          
          .
        
      
    
    
      
        (
        26
        )
      
    
  




It is sufficient to make





  
    
    
      δ
      l
    
    
  
  <
  
    
      π
      2
    
    ⁢
    
      
        
        
          
            ∑
            
              
                i
                =
                1
              
              
                
                  a
                  li
                
                ≠
                0
              
            
            L
          
          ⁢
          
            
              ∑
              
                k
                =
                1
              
              
                K
                i
              
            
            ⁢
            
              
                n
                lik
              
              ⁢
              
                Ω
                ik
              
              ⁢
              
                a
                li
              
            
          
        
        
      
      
        -
        1
      
    
    ⁢
    
      
    
    ⁢
    and
    ⁢
    
      
    
    ⁢
    
      
      δ
      
    
  
  <
  
    
      π
      2
    
    ⁢
    
      
        
          
          
            
              ∑
              
                
                  i
                  =
                  1
                
                
                  
                    a
                    li
                  
                  ≠
                  0
                
              
              L
            
            ⁢
            
              
                ∑
                
                  k
                  =
                  1
                
                
                  K
                  i
                
              
              ⁢
              
                
                  n
                  lik
                
                ⁢
                
                  Ω
                  ik
                
                ⁢
                
                  b
                  li
                
              
            
          
          
        
        
          -
          1
        
      
      .
    
  




In summary, under the assumption in equation (26), for each the computer can use equation (25) to get




  
    
      ∑
      
        i
        =
        1
      
      L
    
    ⁢
    
      
        ∑
        
          k
          =
          1
        
        
          K
          i
        
      
      ⁢
      
        
          n
          lik
        
        ⁢
        
          m
          lk
        
      
    
  
  ,




use that in equation (24) to get δl, use δl in equation (21) to get the vector displacement δ, then subtract δ from {tilde over (p)}2 to get a new estimate of p2.

Usually, the number Σi=1L Ki of patterns is greater than two, and the peaks of the function |{circumflex over (f)}| must be associated with the corresponding pattern. This can be done if the patterns have unique amplitudes so the computer can associate each pattern with the peak of corresponding size.
Markers for particular applications can be designed by varying the number of pattern axes, the number of patterns for each axis, the pattern frequencies, and the directions of the pattern orientation vectors. The integers nlik can be chosen to provide the best range for δ.
4. Using High-Contrast Media
The discussion above assumed that the marker density can take on all possible values over some range. This allowed the marker-density function F to be the sum of several cosine functions. That is not possible for high-contrast media which have only few density values.
Consider a medium that can only be black or white. In this case, patterns can be represented by marker-density functions F, F1, F2, . . . having only the values 0 and 1, say 0 for white, and 1 for black. The function F cannot be formed by weighted addition of the pattern density functions F1, F2, . . . , but it can be formed by multiplying them. Periodic functions of this type can be represented by Fourier series. Multiplication of the functions produece complicated combinations of the sinusoidal components, but analysis of the path-density function can still provide phase and frequency information needed for correction of navigation parameters. For two patterns, if




  
    
      
        
          
            
              F
              k
            
            ⁡
            
              (
              s
              )
            
          
          =
          
            
              1
              2
            
            +
            
              
                ∑
                
                  
                    m
                    =
                    
                      -
                      ∞
                    
                  
                  
                    m
                    ≠
                    0
                  
                
                ∞
              
              ⁢
              
                
                  c
                  km
                
                ⁢
                
                  e
                  
                    
                      jω
                      k
                    
                    ⁢
                    ms
                  
                
              
            
          
        
        ,
      
    
    
      
        (
        27
        )
      
    
  




where ckm is a complex constant, then





  
    
      
        
          
            
              
                F
                1
              
              ⁡
              
                (
                s
                )
              
            
            ⁢
            
              
                F
                2
              
              ⁡
              
                (
                s
                )
              
            
          
          =
          
            
              1
              4
            
            +
            
              
                1
                2
              
              ⁢
              
                (
                
                  
                    
                      c
                      
                        1
                        ,
                        
                          -
                          1
                        
                      
                    
                    ⁢
                    
                      e
                      
                        
                          -
                          
                            jω
                            1
                          
                        
                        ⁢
                        s
                      
                    
                  
                  +
                  
                    
                      c
                      11
                    
                    ⁢
                    
                      e
                      
                        
                          jω
                          1
                        
                        ⁢
                        s
                      
                    
                  
                  +
                  
                    
                      c
                      
                        2
                        ,
                        
                          -
                          1
                        
                      
                    
                    ⁢
                    
                      e
                      
                        
                          -
                          
                            jω
                            s
                          
                        
                        ⁢
                        s
                      
                    
                  
                  +
                  
                    
                      c
                      21
                    
                    ⁢
                    
                      e
                      
                        
                          jω
                          2
                        
                        ⁢
                        s
                      
                    
                  
                
                )
              
            
            +
            
              terms
              ⁢
              
                
              
              ⁢
              with
              ⁢
              
                
              
              ⁢
              higher
              ⁢
              
                
              
              ⁢
              fequencies
            
          
        
        ,
      
    
    
      
        (
        28
        )
      
    
  




so the low frequency terms are separated and can be found using the DFT. This can be extended to more than two patterns. The functions on the left of this equation can be raised to different powers to weight the functions.

5. Other Considerations
Pattern density functions are periodic, but they need not be sinusoidal. Since periodic functions can be represented as a Fourier series like that of equation (27), the technique described for high-contrast media can be adapted for patterns which are not sinusoidal.
It is well known that window functions ω other than the one shown in FIG. 2 can be used to reduce the level of |{circumflex over (f)}| outside the central peaks. While such windows can be used to taper the edge of a marker, it is better and more flexible to have the computer apply windows in the processing of the path-density function f.
Persons knowledgeable of the relevant art will recognize that markers need not be circular disks, so that other regions can be used.
Although it is not clear how one could construct markers for three (or higher) dimensional applications, equations (23) through (26), which were derived for two-dimensional markers, also apply to markers of higher dimensions comprising superposed periodic patterns.

## Claims

1. An automatic system for determining a position and direction-of-motion of a vehicle, which system comprises
set of position markers fixed in known positions,
a density sensor mounted on the vehicle and positioned so it determines density along a line as the vehicle moves,
a computer receiving density values determined by the density sensor, and maintaining an estimate of the position and direction-of-motion of the vehicle, and
a computer control system that directs the computer to perform computations for estimating the position and direction-of-motion of the vehicle from the density values as the sensor passes across any one of the position markers;
each of the position markers comprising one or more density patterns in a finite two-dimensional region;
each of the density patterns filling a two-dimensional region of a position marker;
each of the density patterns having a known orientation vector;
in the two-dimensional region, a density of each density pattern being a known periodic function of position in a direction of its orientation vector, and independent of position in a direction orthogonal to its orientation vector;
at each point of the two-dimensional region the position marker having a density which is a combination of its density-pattern densities at the same point;
the computer storing the density values it receives as a path density function until it determines that it has a quantity of them that is sufficient for performing the computations needed to estimate a current position and direction-of-motion of the vehicle;
the computer then performing mathematical operations necessary to determine frequency, phase, and amplitude values of various sinusoidal components of the path density function;
the computer then using so-determined amplitude value of each sinusoidal component of the path density function to determine which density pattern corresponds to that sinusoidal component;
the computer then performing mathematical operations necessary to use so-determined frequency and phase values of sinusoidal components of the path density function and spatial frequency and phase values of corresponding known density patterns of position markers to determine the vehicle's direction-of-motion and an offset of a current estimate of the vehicle's position from a vehicle's actual position, and then using that offset to correct the current estimate of the vehicle's position.

2. A system as in claim 1 for which a density-determining periodic function of a density pattern is a sinusoid.

3. A system as in claim 1 for which
at each point of the two-dimensional region the position marker has a density which is a constant plus a weighted sum of its density-pattern densities at the same point.

4. A system as in claim 1 for which
the density of each of the density patterns is between zero and one;
and at each point of the two-dimensional region the position marker has a density which is a multiplicative product of the densities of the density patterns at the same point,
with adjustment of a range of densities.

5. A system as in claim 1 for which
a set of position markers are positioned so the density sensor passes over them sequentially.

6. A system as in claim 1 for which
the frequencies, phases, and amplitudes of the sinusoidal components of the computer-stored path-density function are determined by using the Discrete Fourier Transform.