
One of the most important pieces of information for a robot is its position in the environment. In order for an autonomous robot to perform its tasks, its position and orientation must be known. For an mobile robots its position can be classified in two categories: relative positioning and absolute positioning. A relative positioning system is one which uses sensors on the robot's wheels or other navigation systems to calculate the position without taking a fixed consideration. An absolute positioning system is one which uses fixed a reference for position determination, such as the Global Positioning Systems (GPS). One of the most fundamental techniques to position determination is the use of encoders on the wheels, which is called Odometry. Odometry is very important to have precise estimates on the wheel's velocity and orientation and combined with other sensors it makes a reliable way to position estimate \cite{Andov}.

\section{History of Odometry}

Since the early times men found the need to measure distance and velocity. An odometer is the device that measures the distance travelled by a vehicle and it can be electronic, mechanical or the combination of two.

Possibly the first odometer was described by Vitruvius around 27 and 23 BC. The odometer of Vitruvius was based on wheels of 1.2 m diameter turning 400 times, that making one Roman mile, about 1400 m. At each revolution a pin on the axle hit a 400 tooth gear making one revolution per mile. This gear engaged another device that dropped pebbles into a box and thus the distance travelled would be calculated by counting the pebbles. It is unclear if the instrument was ever built at the time. Leonardo da Vinci also drawn an odometer (Figure \ref{f:odometer}) based on the plans \cite{Vitruvius}.
%
\begin{figure}[htbp]
\centering
%
\includegraphics[width=5cm]{./Imagens/odometer_vinci.jpg}
%
\caption{Odometer drawn by Leonardo da Vinci.}
\label{f:odometer}
\end{figure}
%

Blaise Pascal and Wilhrlm Schickard, both, made the invention of the mechanical calculator in the early of the 17th century. Pascal's invention, called Pascaline (Figure \ref{f:pascaline}), was made in 1642. Thought it was not a odometer, the Pascaline used gears to calculate measurements. Each gear contained ten teeth, the first gear moved the next gear one position at each complete revolution, this is the principle used in the modern odometers \cite{pascaline}.

%
\begin{figure}[htbp]
\centering
%
\includegraphics[width=5cm]{./Imagens/pascaline.jpg}
%
\caption[Pascaline, Pascal's calculator]{Pascaline, Pascal's calculator \cite{pascaline}.}
\label{f:pascaline}
\end{figure}
%

In 1698 Thomas Savery, an English military engineer and inventor, developed odometers to measure the distance travelled by ships. In 1775 Benjamin Franklin, a statesman, writer and inventor, built a odometer to measure the mileage of postal routes to analyse the best routes for delivering the mail. In 1847 William Clayton, Orson Pratt, Appleton Milo Harmon, invented the Roadometer that recorded the distance travelled by wagons. The Roadometer was a pascaline inspired device that used gears to measure the distance travelled (Figure \ref{f:roadometer}) \cite{mendonutah}. 
%
\begin{figure}[htbp]
\centering
%
\includegraphics[width=5cm]{./Imagens/roadometer.jpg}
%
\caption[Roadometer, first used in May, 1847.]{Roadometer, first used in May, 1847 \cite{mendonutah}.}
\label{f:roadometer}
\end{figure}
%

Arthur P. and Charles H. Warner produced a device to measure speed of industrial equipment which used a magnet in a rotating shaft to induce a magnetic pull to a metal disk. This device became the first automobile speedometer in 1912 and became standard equipment on most American-made cars \cite{jsonline}.

\section{Odometry}

Odometry is the method that uses data from moving sensors to estimate the change in position over time. Odometry is used to estimate, and not determine, the position of a vehicle relative to a starting location. This method is sensitive to errors due to the integration of velocity measurements over time to give position estimates. A robot can have, for example, rotary encoders on its wheels or on its legged joints and use the data from this sensors to measure how much the wheels have rotated, and knowing the circumference of the wheel it can calculate the distance travelled. 

Odometry mostly uses encoders to measure wheel rotation and/or steering orientation, resolvers also can be used but encoders are usually the first choice. Odometry has the advantage that it can be self-contained, and it is always capable of providing  an estimate of position of a vehicle. The disadvantage of odometry is that it must integrate displacement measurements to give position estimates, this causes this method to be sensitive to errors. The position error grows over time and an independent reference should be used periodically to reduce the error \cite{Cox}.

Optical encoders are the most common sensors used in odometry. The main components of the optical encoder's is a disc made of glass or plastic with transparent and opaque areas, a light source and photo detector array that reads the pulses generated by the optical pattern from the disc's position. Increasing the number of pulses increases the resolution. These type of devices are relatively inexpensive and well suited for velocity feedback low to high speed systems. Some encoders have two channels displaced one from the other and by determining which one is the leading channel it is possible to calculate the direction of rotation. The addition of a channel also has the benefit of increasing the resolution (Figure \ref{f:encoder}). There are some downsides associated to this sensors, in the event of a power interruption all relative position information is lost, this sensors are also more sensitive to damage by external agents \cite{whereami}.
%
\begin{figure}[htbp]
\centering
%
\includegraphics[width=10cm]{./Imagens/encoder.jpg}
%
\caption[The phase relationship between channel A and B can be used to determine the direction of rotation. With the unique states S1 to S4 it is possible to increase the resolution with a multiplication factor of 4.]{The phase relationship between channel A and B can be used to determine the direction of rotation. With the unique states S1 to S4 it is possible to increase the resolution with a multiplication factor of 4 \cite{sensorsmobile}.}
\label{f:encoder}
\end{figure}
%


Another type of optical encoder which can be used to measure wheel's orientation is the absolute encoder. The application of this type of sensor is mostly associated to slower rotational applications where the loss of the position information cannot be tolerated. Absolute encoders produce a unique digital code for each distinct angle of the shaft (Figure \ref{f:absencoder}). Each track of the disk codes a bit, increasing the number of tracks increases the resolution and also increases the diameter of the disk and consequently the decrease in shock and vibration tolerance. Absolute encoders are best suited for slow rotating systems such as direction angle. The main downside of this type of sensor is the increasing fragility and cost as the resolution increases \cite{whereami}.
%
\begin{figure}[htbp]
\centering
%
\includegraphics[width=10cm]{./Imagens/absencoder.jpg}
%
\caption[The line of light passes through the coded pattern of the rotor and that corresponds to a unique code that specifies the absolute angular position.]{The line of light passes through the coded pattern of the rotor and that corresponds to a unique code that specifies the absolute angular position \cite{agent}.}
\label{f:absencoder}
\end{figure}
%


Encoders are the most commonly used sensors to odometry purposes. They provide a straightforward encoding scheme and digital output, this results in a low-cost reliable package with good noise immunity \cite{whereami}.

Encoders like the ones used on the ATLASCAR are inexpensive and higher resolution encoders are highly available and still at a low cost. 1024 pulse encoders are very common and installed on the car would provide a speed measurement at every 1.7 millimetres, which is a very high resolution. This method still has the disadvantage of having an error accumulation that grows over time. Wheel's geometry changes are the most common source of error due to fluctuation of tire pressure, tire diameter, slippage of the wheels and tire tread wear.

Most of the modern cars, the ones with ABS systems, use a speed sensor based on inductive principles. Coupled to the wheel's axle there is a spur gear and next to it there is an inductive sensor that generates a pulse every time a tooth passes (Figure \ref{f:abs}). This kind of sensors is very robust, they do not need contact between the moving parts and the sensor is immune to water and dust. Although, they have some disadvantages, measurements may be affected by magnetic fields, also they do not provide accurate measurements for low speed movements \cite{abs}.
%
\begin{figure}[htbp]
\centering
%
\includegraphics[width=7cm]{./Imagens/abs.png}
%
\caption{ABS inductive velocity sensor.}
\label{f:abs}
\end{figure}
%

\section{Inertial Navigation}

This method measures rate of rotation and acceleration with gyroscopes and/or accelerometers. The measurements of a gyroscope must be integrated once to get angular displacement and accelerometer data must be integrated twice to obtain linear displacement. This sensors have the advantage that they are self-contained and they the measurements are independent of the wheel's geometry changes and wheel's slippage. On the other hand this type of inertial devices have a natural drift which is a source of error, this drift accumulates over time causing a deviation on the measurements. This data then needs to be integrated to obtain velocity and position and the error grows without bounds. For this reason, inertial sensors are unsuitable for accurate positioning over an extended period of time \cite{whereami}.

Along with odometry, gyroscopes are the most used sensors for determining the orientation of a mobile robot. Gyroscopes can be classified in several categories, the most common types of gyroscopes are mechanical, optical and piezoelectric vibrating gyroscopes.

The mechanical gyroscope is a rotation sensor based on the inertial properties of a rapidly spinning rotor, this technology is known since the early 1800s. This gyroscope is composed by a rotating mass mounted on a support with three moving axes (Figure \ref{f:mecgyro}). The mass is rotating at a constant velocity and when the support is inclined causes gyroscopic pressetion, which is a rotation of the support to compensate the inclination. A modern mechanical gyroscope provides a voltage or frequency output signal proportional to the turning rate. High precision mechanical gyroscopes are expensive, also they are big on size and heavy. For this reasons mechanical gyroscopes have a limited application in mobile robotics \cite{whereami}.
%
\begin{figure}[htbp]
\centering
%
\includegraphics[width=10cm]{./Imagens/mecgyro.jpg}
%
\caption[Typical mechanical gyroscope configuration.]{Typical mechanical gyroscope configuration \cite{whereami}.}
\label{f:mecgyro}
\end{figure}
%

Piezoelectric vibrating gyroscopes use Coriolis forces to measure rate of rotation. In a typical configuration three piezoelectric transducers are mounted on the sides of a triangular prism. If one of the transducers is at a constant resonance frequency the vibrations will be transmitted at equal intensity to the others transducers. If a rotation is applied to the system the other two transducers will measure vibrations with a difference. This voltage difference is proportional to the rate of rotation \cite{whereami}. Inexpensive vibrating structure gyroscopes using MEMS technology, a technology for microelectronics, have become widely available. These are packaged into integrated circuits providing analog or digital outputs or sometimes both. Some units integrate gyroscopes for multiple axes in a single part. Some units even incorporate multiple-axis gyroscopes and accelerometers to provide a six degrees of freedom output. These units are called Inertial measurement units, or IMUs (Figure \ref{f:imu}). This type of sensor is the most used in consumer electronics like smart-phones due to their small size and low energy consumption. They are also used in the automotive and industrial robotic field. Some units became so inexpensive that they are also used by hobbyists \cite{MEMS}.
%
\begin{figure}[htbp]
\centering
%
\subfloat[]{\includegraphics[width=4cm]{./Imagens/imu.jpg}}
\quad
\subfloat[]{\includegraphics[width=4cm]{./Imagens/imu2.jpg}}
%
\caption[POLOLU - MinIMU9DOF, an inertial measurement unit (IMU) that has a 3-axis gyro, a 3-axis accelerometer and a 3-axis magnetometer.]{POLOLU - MinIMU9DOF, an inertial measurement unit (IMU) that has a 3-axis gyro, a 3-axis accelerometer and a 3-axis magnetometer \cite{pololu}.}
\label{f:imu}
\end{figure}
%

The other type of gyroscope is the optical gyroscope. Optical gyroscopes are build with no moving parts, being a maintenance free device. Its design is based on two fibber optics coils with the same length on which two laser beams with opposite directions travel. If a rotation is applied the duration of the travel by each laser beam will be different, this is known as the Sagnac effect. Recently optical gyroscopes have become available at competitive prices being the choice for applications with high precision needs \cite{whereami}.

\section{Visual Odometry}

Visual odometry is a technique that estimate robot location using visual information (images); the position is defined as the incremental estimation of robot motion from image sequences using an on-board camera. Visual odometry is a method highly used on off-road robots like space robotic exploration missions. The motion of the robot is estimated with calculation of the pixel displacement between two consecutive frames, this is called optical flow \cite{Mars}.

The optical flow is mostly calculated based on features that stand out in the image, this method doesn't work well on smooth or texture-less surfaces like concrete and asphalt roads. The other method, with better results, is template matching. This method use a small area of a image and tries to find it in the next frame, if found, it is possible to calculate the optical flow \cite{IMUodometry}.

There are two main different approaches in hardware, the first uses a camera looking forward and the velocity is calculated based on the movement of the surroundings. This method is very sensitive to lighting changes and a high quality image is needed. The other method uses a camera looking directly at the ground, this is the principle used in most optical mice. This method needs simpler computation and hardware and lighting conditions can be handled better \cite{Kalman}.

The literature suggests visual odometry as a better odometry system in terms of precision and error accumulation. Navid Nourani-Vatani et al \cite{IMUodometry, carodometry}, obtained good results using a common webcam at 20 fps and a image resolution of 640 x 480 pixels; they used template matching with a searching area of 320 x 320 pixels. The acquisition speed was set to 20 fps due to the high processing time, 42 ms/frame, this is a clear limitation. Also due to the low frame rate, the velocity of the vehicle was limited to 1.5 m/s, which is very low. Nevertheless, this method showed better results than common wheel's odometry. This method is illustrated in Figure \ref{f:visual_example}; the image displacements are translated to vehicle displacement to estimate its position and trajectory.

\begin{figure}[htbp]
\centering
%
\includegraphics[width=10cm]{./Imagens/visual_example.png}
%
\caption[Simplified model of a vehicle with Ackermann-like steering model. The pixel displacement, $\Delta U$ and $\Delta V$, translates to vehicle displacement $\Delta x$ and $\Delta \theta$, which are defined with respect to the center of motion corresponding to the midpoint of the rear axle.]{Simplified model of a vehicle with Ackermann-like steering model. The pixel displacement, $\Delta U$ and $\Delta V$, translates to vehicle displacement $\Delta x$ and $\Delta \theta$, which are defined with respect to the center of motion corresponding to the midpoint of the rear axle \cite{IMUodometry}.}
\label{f:visual_example}
\end{figure}


The velocity allowed by the measuring unit is are mostly influenced by the sampling rate and the size of the image. If the velocity is higher than the limit, there will be no overlap of the frames and there will be no similarity between the successive images; this will cause the impossibility of the estimation of velocity \cite{Kalman}. So, for car-like velocities it is necessary a very high sampling rate camera, this brings difficulties as the computational power needs to be considerable. Viktor K\'{a}lm\'{a}n \cite{Kalman} suggests the use of line scan cameras to achieve high velocities and resolution, using less computational resources than a common matrix camera. In his work he made simulations and came to the conclusion that it is possible to measure movements of vehicles up to the range of 100m/s with high accuracy.

Visual odometry has clear advantages over the common wheel's odometry. It is possible to measure velocity independent of the variations in tire pressure, tire diameter, uneven terrain and tire slip. It is possible to obtain a compact and easy to install module. However, there are several drawbacks, the lighting is an important factor (and it isn't always possible to control), also the sensors are high price and sophisticated.

\section{Commercial Solutions}

Every car on the roads have a odometer on the dashboard that shows the instantaneous velocity, although most of them have a odometer actuated mechanically so that there is no electrical signal that can be measured.

There are already some companies that sell devices capable of measuring wheel's speed and orientation. Most of this devices are used by automotive manufacturers to test the dynamics and durability of their products. 

The company Kistler Automotive sells various sensors that can be used to measure velocity and direction of a car, they provide one product that measures wheel's rotation and others that are optical and measure velocity and orientation without contact. The WPT Sensors is a sensor that is universally adaptable for acquisition of vehicle wheel speed (Figure \ref{f:wpt}). This sensor consists of an optical incremental encoder and has 1000 pulses in its standard configuration. Its applications are wheel slip measurement, acceleration and braking tests, ABS testing. \cite{Kistler}

%
\begin{figure}[htbp]
\centering
\includegraphics[width=5cm]{./Imagens/WPT.png}
\caption[WPT sensors from Kistler Automotive.]{WPT sensors from Kistler Automotive \cite{Kistler}.}
\label{f:wpt}
\end{figure}
%

Kistler has another kind of solution based on optical sensors, the 2-Axis Non Contact Optical Velocity and Slip Angle Sensors. These sensors provide slip-free measurement of distance, velocity and slip-angle which is the angle between a rolling wheel's actual direction of travel and the direction towards which it is pointing (Figure \ref{f:kistler}).

%
\begin{figure}[htbp]
\centering
%
\subfloat{\includegraphics[width=5cm]{./Imagens/kcd_LFII-P-Sensor-mounted.jpg}}
\subfloat{\includegraphics[width=5cm]{./Imagens/S350-sensorhead+electronics2.jpg}}
%
\caption[2-Axis Non Contact Optical Velocity and Slip Angle Sensors.]{2-Axis Non Contact Optical Velocity and Slip Angle Sensors \cite{Kistler2}.}
\label{f:kistler}
\end{figure}
%

%
\begin{figure}[htbp]
\centering
%
\includegraphics[width=5cm]{./Imagens/briaskThumb_POS_LV.jpg}
%
\caption{POS LV}
\label{f:poslv}
\end{figure}
%

Applanix provides a solution based on GPS and inertial sensors, the POS LV (Figure \ref{f:poslv}). POS LV is a position and orientation system, utilizing integrated inertial technology to generate stable, reliable and repeatable positioning solutions for land-based vehicle applications.The product generates a true representation of vehicle motion in all three axes, works in areas of intermittent, or no GPS reception, computes wheel rotation information to aid vehicle positioning, embedded GPS receivers provide heading aiding to supplement the inertial data. \cite{Applanix}

