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&#39;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&#39;s usual path passes over a marker, that path can be used without change for acquiring navigation corrections.

Description:
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&#39;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, p 1 , p 2 , etc., whereas the pattern reference point C 0 =&lt;X 0 , Y 0 &gt; on pattern axis  3  is upper case. For descriptions of specific notations, see T ABLE  1: L IST OF  S YMBOLS  U SED . Terms specific to this invention are italicized when defined, and shown in T ABLE  2: L IST OF  T ERMS . 
     For the part of the path shown, the motion starts at point p 1 , then goes through points p 2 , p 3 , p 4 , and p 5 , to p 6 . The part of the path between p 2  and p 5  is a straight line aligned with unit direction-of-motion vector v. The point p 2  is the reference point for distance s (i.e., s=0 at p 2 ) on the straight segment of the sensor&#39;s path. 
     Simple-pattern marker  1  (see  FIG. 1 ) is a circular disk of radius R 0  centered at C 0 . Its optical density varies in the direction of unit orientation vector I 0 , but is independent of position in the direction of unit vector J 0  orthogonal to I 0 . The counterclockwise angles in radians from the x-axis to I 0  and J 0  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 I 0 . The distance between adjacent density peaks measured in the direction of I 0  is the wavelength Λ 0 . The function is independent of position in the direction of J 0 . 
     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 J 0 , and periodic in the direction of I 0 ; and equals F inside disk  1 . The maxima of F +  are on certain lines parallel to J 0 . 
     Points p 3  and p 4  are the points at which path  2  intersects the boundary of  1 . Line  3  is the pattern axis; it passes through C 0  and is parallel to the orientation vector I 0 . The counterclockwise angle in radians between I 0  and v is θ 0  satisfying 0≦θ 0 &lt;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 =R 0 /6, and Ω 0 =12π/R 0 . 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&#39;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(ω 0   s+ψ   0 )+ b,   (2)
 
where a, b, and ψ 0  are constants with b≧|a| and 0≦ψ 0 &lt;2π.
 
     The function F(x, y) is anchored to the x, y-axes and C 0 , but f(s) is not. Instead, v and p 2  determine its relationship to F(x, y), hence to the x, y-axes and C 0 . 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 p 2 , 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 −p 2  in the direction of I 0 . 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 p 2  and p 5  will be obtained, then that will be related to f(s). 
     For a point p (e.g., on the sensor&#39;s path), let S(p) denote the signed distance (positive toward I 0 ) from C 0  to the orthogonal projection P of p onto line  3 . The reader is reminded that since I 0  is a unit vector, the dot product (p−C 0 )−I 0  is the (signed) length of the projection of the line segment from C 0  to p onto line  3 , and δ 0 =δ·I 0 , so
 
 P=C   0 +(( p−C   0 )·I 0 ) I   0 ,
 
and
 
 S ( p )=( p−C   0 )· I   0 .  (3)
 
The value of the function F + (p) at p is determined by S(p). Let φ 0  be the phase at C 0 , so
 
 F   + ( p )= A  cos(Ω 0   S ( 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 p 2  and p 5  on the sensor&#39;s path, p is a function of s given by p(s)=p 2 +sv, so from equations (2) and (4),
 
 a  cos(ω 0   s+ψ   0 )+ b=f ( s )= F   + ( p ( s ))= A  cos(Ω 0   S ( p ( s ))+φ 0 )+ B,   (5)
 
which is true while p(s) is between p 3  and p 4 .
 
     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(ω 0   s+ψ   0 )=cos(Ω 0   S ( p ( s ))+φ 0 ) for  p ( s ) between  p   3  and  p   4 .
 
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),
 
ω 0   s+ψ   0 =Ω 0 ( p ( s )− C   0 )· I   0 +φ 0   −m 2π,  (6)
 
where m is an integer. In particular, since p(0)=p 2 , for s=0 equation (6) is
 
ψ 0 =Ω 0 ( p   2   −C   0 )· I   0 +φ 0   −m 2π.  (7)
 
This can be rearranged and applied to the definition of δ 0  to get
 
δ 0 =( {tilde over (p)}   2   −p   2 )· I   0 =( {tilde over (p)}   2   −C   0 )· I   0 +(φ 0 −ψ 0 −2π m )/Ω 0 .  (8)
 
     Therefore, if ψ 0  and m can be found, any position can be partially corrected by subtracting δ 0 I 0  from it. In particular, the partially-corrected {tilde over (p)} 2  is {tilde over (p)} 2 −δ 0 I 0 . 
     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 |&lt;Λ 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 X 0  and Y 0  of the marker reference point C 0 , the orientation vector I 0 , the angular frequency Ω 0 , and the phase φ 0  at C 0 . 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 −δ 0 I 0 . 
     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&lt;{tilde over (θ)} 0 &lt;π, 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&#39;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 p 2  to p 3  it stores {tilde over (p)} as {tilde over (p)} 2 , an approximation to p 2 . 
     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     ⁢     (       ⅇ   jγ     +     ⅇ     -   jγ         )         ,         
where j is the imaginary unit (j 2 =−1), f(s) can be written (with b=0; see equation (2))
 
                       f   ⁡     (   s   )       =       a   2     ⁢     (       ⅇ     j   ⁡     (         ω   0     ⁢   s     +     ψ   0       )         +     ⅇ     -     j   ⁡     (         ω   0     ⁢   s     +     ψ   0       )             )         ,           (   12   )               
so {circumflex over (f)}(ω) is zero except at two points:
 
 {circumflex over (f)}   +   =cae   jψ     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 ω&gt;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 p 3  to p 4 , 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 p 3  and p 4 . 
     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 I 0 . 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 p 1  to p 6 . The patterns are rotated from each other, as indicated by the orientation vectors I 1 , I 2 , and I 3 . Each of markers  5  and  7  provide coordinate corrections in the directions of their orientation vectors. 
     Marker  6  cannot be used for corrections because I 2  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. T ABLES  
         T ABLE OF  C ONTENTS      T ABLE  1: L IST OF  S YMBOLS  U SED      T ABLE  2: L IST OF TERMS          

     2. S UPERPOSING  A LIGNED  P ATTERNS    
     3. S UPERPOSING  U NALIGNED  P ATTERNS    
     4. U SING  H IGH -C ONTRAST  M EDIA    
     5. O THER  C ONSIDERATIONS    
     
       
         
               
             
               
               
             
               
             
               
               
             
               
             
               
               
             
           
               
                 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 
               
             
          
           
               
                 &lt;x, y&gt; 
                 The point (or vector) with coordinate components x and y; e.g., δ = &lt;δ x , δ y &gt;. 
               
               
                 ┌·┐ 
                 The ceiling function: ┌r┐ is the smallest integer ≧ r. 
               
               
                 Round 
                 Round to the nearest integer, ties rounding down: Round(u) = ┌u − ½┐. 
               
               
                 U · V 
                 For any vectors U and V, the dot product U · V = U x V x  + U y V y . 
               
               
                 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 I k . 
               
               
                 δ k   
                 Offset in the direction I k  of the estimated coordinates from the true coordinates. 
               
               
                 θ k   
                 The counterclockwise angle in radians between I k  and v with 0 ≦ θ k  &lt; 2π. 
               
               
                 {tilde over (θ)} k   
                 The computer&#39;s estimate of θ k . 
               
               
                 λ k   
                 Wavelength of the path-density function f k . 
               
               
                 Λ k   
                 Wavelength of the pattern-density function F k (x, y). 
               
               
                 φ k   
                 The phase of F k   +  at C k : F k   +  (C k ) = A cos(φ k ) + B k . 
               
               
                 ψ k   
                 Phase of f k (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 p 2 . 
               
               
                 v 
                 The direction-of-motion vector for the density sensor on the segment from  
               
               
                   
                 p 2  to p 5 . 
               
               
                 {tilde over (v)} 
                 The computer&#39;s estimate of v. 
               
               
                 C k   
                 The pattern reference point &lt;X k ,Y k &gt; of pattern k. 
               
               
                 I k   
                 The orientation vector of pattern k. 
               
               
                 J k   
                 The vector orthogonal to and on the left side of I k . 
               
               
                 F k   
                 The pattern density function of pattern k. 
               
               
                 F k   +   
                 The periodic extension of F k  to the entire x, y-plane. 
               
               
                 R k   
                 Radius of the position marker pattern (when circular). 
               
               
                 δ 
                 The displacement vector of p 2 : δ = {tilde over (p)} 2  − p 2 . 
               
               
                 p 
                 A point on the sensor path, especially the sensor location. 
               
               
                 {tilde over (p)} 
                 The computer&#39;s estimate of p. 
               
               
                 p 1   
                 Starting point of the sensor path in the figures. 
               
               
                 p 2   
                 Starting point of the straight path segment crossing a position marker; 
               
               
                   
                 used as a reference point for s (s = 0 at p 2 ). 
               
               
                 p 4   
                 Last point at which the straight path segment meets the position marker; 
               
               
                 p 5   
                 Ending point of the straight path segment crossing the position marker; 
               
               
                 p 6   
                 Ending point of the sensor path in the figures. 
               
               
                 P k   
                 The projection of p on pattern axis I k   
               
               
                 {tilde over (p)} 2   
                 The computer&#39;s approximation of p 2 . 
               
               
                 S(p) 
                 Distance from C 0  to P: S(p) = (p − C 0 ) · I 0   
               
               
                   
               
             
          
         
       
     
     
       
         
               
             
               
               
               
             
               
               
               
             
           
               
                 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 
                 C k   
               
               
                 11 
                 pattern axis 
                 line 3 in FIG. 1;  
               
               
                   
                   
                 lines 33, and 34 in FIG. 12 
               
               
                 12 
                 direction-of-motion vector 
                 v 
               
               
                 13 
                 orientation vector 
                 I k   
               
               
                 14 
                 pattern-density function 
                 F k   
               
               
                 20 
                 displacement 
                 δ 
               
               
                 27 
                 marker parameters 
                 X k , Y k , I k , Ω k , and φ k   
               
               
                 58 
                 underlying navigation 
                 e.g., dead reckoning 
               
               
                 60 
                 superposing 
                 F 3  = A F 1  + B F 2  + 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 p 2  to p 5  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 p 2 ; i.e., that |δ|&lt;Λ 0 /2. This reqirement is too severe in many applications. 
     The |δ|&lt;Λ 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 F 3  of marker  11  is the weighted sum of the density functions F 1  and F 2  of patterns  12  and  13 , respectively. Specifically, for  FIG. 5 
 
 F   3 ( x, y )= A ( F   1 ( x, y )+0.75  F   2 ( x, y ))+ B,   (15)
 
where A and B are constants. The orientation vectors, I k  for k=1, 2, and 3, are all rotated 15 degrees from the x-axis (so I 1 =I 2 =I 3 ). 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 p 2 , p 3 , p 4 , and p 5 , 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 I l  for l=1, 2, . . . , L. Here it will be assumed that the I l  are all equal. 
     There are L equations, one for each pattern, corresponding to equation (8):
 
δ 1 =( {tilde over (p)}   2   −C   l )· I   l +(φ l −ψ l −2π m   l )/Ω l , for  l∈{ 1,2, . . . ,  L},   (16)
 
where 0≦ψ l &lt;2π, and m l  is an integer (there is only one δ 1  because all I l =I 1 ; all I l  are shown, however). Combine these as follows. For l∈{1, 2, . . . , L} let n l  be an integer. Multiply equation (16) by n l Ω 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          &lt;       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=1   L  n l m l , then δ 1 , and partially correct {tilde over (p)} 2  to {tilde over (p)} 2 −δ 1 I 0 . 
     Condition (19) is much better than the one (|δ 0 |&lt;Λ 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 n 1 =1, if n 2 =−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 −p 2  has a component δ l =δ·I l  along I l . Given δ l  for all l∈1, . . . , L, δ can be found by taking δ=Σ l=1   L  a l I l  and solving the simultaneous linear equations
 
δ l   =δ·I   l , for  l∈{ 1, . . . ,  L}.   (21)
 
for a 1 , . . . , a L .
 
       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 I l , and line  34  for the axis associated with I i . The orientation vectors I l  and I i  are at angles α l  and α i  from the positive x-axis, respectively. The angles from I l  and I i  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 I 1  and I 2  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 I l  has K l ≧1 associated patterns. For each k∈{1, . . . , K i } the pattern has refernce point C lk , angular frequency Ω lk , phase ψ lk  at C lk , and corresponding path frequency ω lk ; and for each of these patterns there is an equation like equation (16) for δ l =({tilde over (p)} 2 −p 2 )·I l , the displacement in the direction of I l . Let J l  be the unit vector orthogonal to I l  and pointing to the left of I l . Then there are numbera a li  and b li  such that I i =a li I l +b li J l . Note that a ll =1 and b ll =0.  FIG. 12  shows vectors J i  and J l . 
     There are integers m ik  such that equation (7) mutatis mutandis becomes
 
Ω ik ( p   2   −C   ik )· I   i =−φ ik +ψ ik +2π m   ik  for  i∈{ 1,2, . . . ,  L } and  k∈{ 1,2, . . . ,  K   i }.  (22)
 
Since
 
( p   2   −C   ik ) ·I   i =( p   2   −{tilde over (p)}   2   +{tilde over (p)}   2   −C   ik ) ·I   i =−δ·( a   li   I   l   +b   li   J   l )+( {tilde over (p)}   2   −C   ik )· I   i   =−a   li δ l   −b   li   δ·J   l +( {tilde over (p)}   2   −C   ik )· I   i 
 
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 a li =0).
 
     Combine all of these equations to get a single equation for δ l : choose integers n lik , 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                    &lt;       1   2     .             (   26   )               
It is sufficient to make
 
     
       
         
           
             
                
               
                 δ 
                 l 
               
                
             
             &lt; 
             
               
                 π 
                 2 
               
               ⁢ 
               
                 
                    
                   
                     
                       ∑ 
                       
                         
                           i 
                           = 
                           1 
                         
                         
                           
                             a 
                             li 
                           
                           ≠ 
                           0 
                         
                       
                       L 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           k 
                           = 
                           1 
                         
                         
                           K 
                           i 
                         
                       
                       ⁢ 
                       
                         
                           n 
                           lik 
                         
                         ⁢ 
                         
                           Ω 
                           ik 
                         
                         ⁢ 
                         
                           a 
                           li 
                         
                       
                     
                   
                    
                 
                 
                   - 
                   1 
                 
               
               ⁢ 
               
                   
               
               ⁢ 
               and 
               ⁢ 
               
                   
               
               ⁢ 
               
                  
                 δ 
                  
               
             
             &lt; 
             
               
                 π 
                 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 p 2 .
 
     Usually, the number Σ i=1   L  K i  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 n lik  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, F 1 , F 2 , . . . 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 F 1 , F 2 , . . . , 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     ⁢     ⅇ       jω   k     ⁢   ms               ,           (   27   )               
where c km  is a complex constant, then
 
                           F   1     ⁡     (   s   )       ⁢       F   2     ⁡     (   s   )         =       1   4     +       1   2     ⁢     (         c     1   ,     -   1         ⁢     ⅇ       -     jω   1       ⁢   s         +       c   11     ⁢     ⅇ       jω   1     ⁢   s         +       c     2   ,     -   1         ⁢     ⅇ       -     jω   s       ⁢   s         +       c   21     ⁢     ⅇ       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.