Mobile robot location determination employing error-correcting distributed landmarks

Claim 3

The method as set forth in claim 1, further comprising the steps of: emitting, from each of the first plurality of rectangular cells, one of two different characteristic responses to radiation from at least one landmark displaying the pseudo-random-checkerboard pattern; and generating, in response to each of the two different characteristic responses, the signal.

Claim 4

The method as set forth in claim 2, further comprising the steps of: converting the signal into a base-digital image depicting a plurality of overlapping rectangular blocks, the base-digital-image having a plurality of adjacent picture elements corresponding to a second plurality of adjacent rectangular cells, each of the plurality of adjacent picture elements corresponding to one of two substantially contrasting colors; storing a representation and a location of each of the plurality of overlapping rectangular blocks of each pseudo-random-checkerboard pattern in a symbolic map; analyzing the base-digital image and the symbolic map; and calculating the position and the orientation of the autonomous vehicle.

Claim 5

The method as set forth in claim 3, further comprising the steps of: creating, in response to the base-digital image, a base-digital array having a plurality of base-digital-array elements, each of the plurality of base-digital-array elements having a first binary value, wherein the base-digital array further comprises a plurality of second binary values, each corresponding to a predetermined number of the plurality of adjacent picture elements of the base-digital image; selecting each first binary value by associating a predetermined number of the plurality of second binary values with each of the base-digital-array elements; detecting a plurality of grid edges and a plurality of grid lines, the plurality of grid edges formed by analyzing each first binary value, and the plurality of grid lines formed by the plurality of grid edges; estimating a first principal direction of the plurality of grid lines, a second principal direction of the plurality of grid lines, a first grid density of the plurality of grid lines, a second grid density of the plurality of grid lines, a first grid phase comprising a first distance, along the first principal direction, from a first image center to a grid line nearest the first image center, and a second grid phase comprising a second distance, along the second principal direction, from the first image center to a grid line nearest the first image center; decoding the first binary value of each of the plurality of base-digital-array elements into a decoded-bit array having a plurality of decoded-bit-array elements, each of the decoded-bit-array elements having a third binary value and corresponding to the plurality of base-digital array elements corresponding to one of the second plurality of adjacent rectangular cells; searching, using the symbolic map, for a representation and a location corresponding to the plurality of overlapping rectangular blocks; determining a geometric transformation for mapping the plurality of decoded-bit array elements to the plurality of overlapping rectangular blocks; and estimating, using the geometric transformation, the position and the orientation of the autonomous vehicle.

Claim 6

The method as set forth in claim 4, further comprising the steps of: assigning an edge intensity and an edge direction to each of the plurality of base-digital-array elements, with at least one edge intensity exceeding a first predetermined value; estimating a first coarse principal direction and a second coarse principal direction of the plurality of grid lines; and specifying a first precise principal direction and a second precise principal direction of the plurality of grid lines.

Claim 7

The method as set forth in claim 5, further comprising the steps of: counting, for each of the plurality of edge directions, the base-digital array elements having that edge direction and having an edge intensity exceeding a second predetermined value; forming a first histogram of a plurality of edge directions by associating, with each of the plurality of edge directions, the count of the base-digital-array elements having that edge direction and having an edge intensity exceeding the second predetermined value; smoothing the first histogram into a smoothed histogram having a plurality of smoothed-edge intensities, by taking a cyclic running average, over a first predetermined number of edge directions, of the count in the first histogram of base-digital-array elements associated with each of the first predetermined number of edge directions; choosing a first coarse-principal-direction of the plurality of grid lines, by selecting an edge direction of the smoothed histogram corresponding to a greatest value of the plurality of smoothed-edge-intensities; and choosing a second coarse-principal-direction of the plurality of grid lines, by selecting an edge direction of the smoothed histogram corresponding to a greatest value of the plurality of smoothed-edge-intensities corresponding to a second predetermined number of edge directions located a third predetermined number of edge directions away from the first coarse-principal-direction.

Claim 10

The apparatus as set forth in claim 7, further comprising: at least one landmark having the pseudo-random-checkerboard pattern with a plurality of rectangular cells, each of the plurality of rectangular calls emitting one of two different characteristic responses to radiation; and wherein the camera means responds to each of the two different characteristic responses.

Claim 11

The apparatus as set forth in claim 8, wherein each of the plurality of rectangular cells substantially uniformly displays one of two substantially contrasting colors.

Claim 12

The apparatus as set forth in claim 9, with approximately one-half of the first plurality of adjacent rectangular cells displaying a first color.

Claim 13

The apparatus as set forth in claim 10, wherein: each landmark having a pseudo-random-checkerboard pattern displays a first plurality of overlapping rectangular blocks formed from the plurality of rectangular cells, each of the first plurality of overlapping rectangular blocks having: a location in the predetermined space; a first side; a second side; a first predetermined number of the plurality of rectangular cells on the first side; a second predetermined number of the plurality of rectangular cells on the second side; and a plurality of rotations; each of the plurality of rotations of each of the first plurality of overlapping rectangular blocks displays a first arrangement of adjacent rectangular cells different from an arrangement of rectangular cells displayed by each other rotation of the same overlapping rectangular block of the first plurality of overlapping rectangular blocks, different from an arrangement of rectangular cells displayed by each of a plurality of rotations of each other overlapping rectangular block in the first plurality of overlapping rectangular block, and different from an arrangement of rectangular cells displayed by each of a plurality of rotations of each of a plurality of rectangular blocks displayed by each other pseudo-random-checkerboard pattern displayed by each other landmark in a second predetermined space; and wherein the signal depicts a second plurality of overlapping rectangular blocks, corresponding to the first plurality of overlapping rectangular blocks of one pseudo-random-checkerboard pattern, wherein each of the second plurality of overlapping rectangular blocks has a second plurality of rectangular cells.

Claim 14

The apparatus as set forth in claim 11, wherein the locating means further comprises: a frame grabber for converting the signal into a base-digital image depicting the second plurality of overlapping rectangular blocks, the base-digital image having a first plurality of adjacent picture elements, each of the plurality of adjacent picture elements corresponding to one of the two substantially contrasting colors; symbolic-map means for storing symbolic-map information, including a representation and a location of each of the first plurality of overlapping rectangular blocks of each pseudo-random-checkerboard pattern; and digital-computer means for analyzing the base-digital image and the symbolic-map information and for calculating the position and the orientation of the autonomous vehicle.

Claim 15

The apparatus as set forth in claim 12, wherein the digital-computer means further comprises: binarization means, responsive to the base-digital image, for creating a base-digital array having a plurality of base-digital-array elements, each of the plurality of base-digital-array elements having a first binary value; image-processing means, responsive to the binarization means, for detecting a plurality of grid edges and a plurality of grid lines, the plurality of grid edges formed by analyzing each first binary value, and the plurality of grid lines formed by the plurality of grid edges; parametric means, responsive to the binarization means and to the image-processing means, for estimating a first principal direction of the plurality of grid lines, a second principal direction of the plurality of grid lines, a first grid density of the plurality of grid lines, a second grid density of the plurality of grid lines, a first grid phase comprising a first distance, along the first principal direction, from a first image center to a grid line nearest the first image center, and a second grid phase comprising a second distance, along the second principal direction, from the first image center to a grid line nearest the first image center; decoding means, responsive to the binarization means and to the parametric means, for decoding the first binary value of each of the plurality of base-digital-array elements into a decoded-bit array having a plurality of decoded-bit-array elements, each of the decoded-bit-array elements corresponding to one of the second plurality of rectangular cells and having a second binary value; searching means, responsive to the decoded-bit array and to the symbolic-map information, for searching for a representation and a location corresponding to the second plurality of overlapping rectangular blocks; geometric means, for determining a geometric transformation for mapping the plurality of decoded-bit-array elements to the second plurality of overlapping rectangular blocks; and positioning means, responsive to the geometric transformation, for estimating the position and the orientation of the autonomous vehicle.

Claim 16

The apparatus as set forth in claim 13, wherein the parametric means further comprises: edge-detecting means for detecting an edge intensity and an edge direction for each of the plurality of base-digital-array elements; at least one edge-picture-element comprising one of the plurality of base-digital-array elements having an edge intensity greater than a predetermined value and having the edge direction detected for that base-digital-array element; coarse-principal-directing means, responsive to the edge-detecting means, for estimating a first coarse-principal-direction and a second coarse-principal-direction of the plurality of grid lines; and precise-principal-directing means, responsive to the coarse-principal-directing means, for estimating a precise estimate of the first principal direction of the plurality of grid lines and a precise estimate of the second principal direction of the plurality of grid lines.

Claim 17

The apparatus as set forth in claim 14, wherein the edge-detecting means further comprises a Sobel edge operator.

Claim 18

The apparatus as set forth in claim 14, wherein the coarse-principal-directing means further comprises: means for forming a first histogram of a plurality of edge directions by associating, with each of the plurality of edge directions, a count of the edge-picture elements having that edge direction; means for smoothing the first histogram into a smoothed histogram having a plurality of smoothed values, by taking a cyclic running average, over a first predetermined number of edge directions, of the count in the first histogram associated with each of the plurality of edge directions of the first histogram; first means for choosing a first coarse-principal direction of the plurality of grid lines, by selecting the edge direction of the smoothed histogram corresponding to a greatest smoothed value of the smoothed histogram; and second means for choosing a second coarse-principal direction of the plurality of grid lines, by selecting the edge direction of the smoothed histogram corresponding to a greatest smoothed value of the smoothed histogram corresponding to a second predetermined number of edge directions located a third predetermined number of edge directions away from the first coarse-principal-edge-direction.

Claim 19

The apparatus as set forth in claim 14, wherein the precise-principal-directing means further comprises: means, responsive to the coarse-principal-directing means, for forming a first binary-edge image having a first plurality of binary-edge-image elements and a first spectrum; means, responsive to the coarse-principal-directing means, for forming a second binary-edge image having a second plurality of binary-edge-image elements and a second spectrum; and spectrum-maximizing means, responsive to the first spectrum and to the second spectrum, for determining a first maximum of the first spectrum, for associating the precise estimate of the first principal direction of the plurality of grid lines with the first maximum, for determining a second maximum of the second spectrum, and for associating the precise estimate of the second principal direction with the second maximum.

Claim 20

The apparatus as set forth in claim 17, wherein the spectrum-maximizing means further comprises: grid-forming means for forming a grid of a specified number of candidate-principal directions around a selected coarse-principal direction, the grid having a grid spacing of a predetermined size; means for associating, with each binary edge element less than a specified distance from a second image center, a third binary value calculated according to a specified method; means for forming an edge-direction histogram, having a plurality of components representing a predetermined number of the plurality of edge directions, for associating with each component one of the predetermined number of the plurality of edge directions and the number of binary-edge elements having that edge direction; means for dividing the plurality of components of the edge-direction histogram into a first half and a second half, each of the first half of the plurality of components corresponding to one of the second half of the plurality of components; Fourier transform means for forming: a first discrete Fourier transform of the first half of the plurality of components, the first discrete Fourier transform having a first plurality of component values, each of the first plurality of component values associated with one of the first half of the plurality of components and having an absolute magnitude; and a second discrete Fourier transform of the second half of the plurality of components, the second discrete Fourier transform having a second plurality of component values, each of the second plurality of component values associated with one of the second half of the plurality of components and having an absolute magnitude; squaring means for calculating the square of the absolute magnitude each of the first plurality of component values and the square of the absolute magnitude of each of the second plurality of component values; spectrum vectoring means for forming a spectrum vector having a plurality of spectrum-vector components, each spectrum-vector component corresponding to one of the first plurality of component values and to one of the second plurality of component values and associated with the sum of the square of the absolute magnitude of the corresponding component value of first plurality of component values; and the square of the absolute magnitude of the corresponding component value of the second plurality of component values; further estimating means, responsive to the first spectrum vector, for specifying a precise estimate of the principal direction.

Claim 21

The apparatus as set forth in claim 14, wherein the searching means further comprises: means for selecting, for each arrangement of rectangular cells displayed by each rotation of each of the second plurality of overlapping rectangular blocks, a representation stored in the symbolic map information matching that arrangement of rectangular cells; means for deducing, from each matching arrangement of rectangular cells, a likely position and a likely orientation in the first predetermined space for the second plurality of rectangular cells; means for selecting, from the likely position and the likely orientation for each matching arrangement of rectangular cells, a most likely position and a most likely orientation in the first predetermined space for the second plurality of rectangular cells.

Claim 22

The apparatus as set forth in claim 14, wherein the precise-principal-directing means further comprises ambiguity-resolving means for selecting the most likely position of the autonomous vehicle and the most likely orientation of the autonomous vehicle when the digital-computer means calculates a plurality of likely positions of the autonomous vehicle.

Claim 23

The apparatus as set forth in claim 20, wherein the ambiguity-resolving means comprises: timekeeping means for determining a time elapsed between producing the plurality of likely positions and the plurality of likely orientations of the autonomous vehicle and estimating at least one second position and at least one second orientation of the autonomous vehicle; measuring means for estimating a maximum distance travelled by the autonomous vehicle during the time elapsed; eliminating means, responsive to the timekeeping means and to the measuring means, for selecting the position and orientation of the autonomous vehicle.

Claim 24

The apparatus as set forth in claim 12, wherein: the frame grabber converts the signal into a pre-processed digital image having a plurality of adjacent pre-processed-digital-image elements; the number of the first plurality of adjacent picture elements of the base-digital image is a predetermined fraction of the number of adjacent pre-processed-digital-image elements; and pre-processing means associates a binary value with each of the first plurality of adjacent picture elements of the base-digital image by averaging, over a predetermined number of the adjacent pre-processed-digital-image elements corresponding to that adjacent picture element of the base-digital image, a suitable attribute of each of the predetermined number of the pre-processed-digital-image elements corresponding to that adjacent picture element of the base-digital image.