Sensor calibration, matrix and Newton…

In my previous post about AMHR filter I told you that the filter was taking care of the sensors error by being robust to linearity and bias error of our LSM9DS1 chip. Indeed, the Madgwick’s filter is robust against them, but minoring theses error can still be usefull because it will take less time at startup to converge to the correct orientation and it will help getting a more accurate estimation of the speed and the position of the robot.

Good news is that it is possible to perform a calibration to lower the error as some of them are due to factory issued and will be constant for a given chip. Bad news is that it is not possible to completely remove them because some part are temperature dependant and will be drifting over time.

Calibration involve running a certain number of measurements based on known conditions and based on the measurements, compute a correctionto be applied on sensor output. This will present the method I used to perform the accelerometer calibration but it can be used also for the magnetometer.

With a perfect accelerometer in a perfect robot mechanic standing on a perfect floor, the read out of the accelerometer should be \begin{bmatrix}x\ y\ z\\    \end{bmatrix} = \begin{bmatrix}0\ 0\ 1\end{bmatrix}

Of course in a real world, the sensor is not perfect and for each axis, it shows a linearity and a bias error.

\begin{bmatrix}    (X\times err_{x} + bias_{x})\ (Y \times err_{y} + bias_{y}) \ (Z \times err_{z} + bias_{z})\\    \end{bmatrix} = \begin{bmatrix}    0\ 0\ 1    \end{bmatrix}

where X , Y , and Z are the measurement done on the according axes, err_{x,y,z} is the scalling error and bias_{x,y,z} is the offset error.

Our goal will be to determine the 6 unknown from the previous equation.

Let’s imagine that we have a perfect rig available so we can position our robot in six perfectly known positions.  We can choose theses position so the gravity vector is aligned with each axis in both direction. During the calibration we just measure the output of the sensor for each orientation and we just have to solve this equation system:

\begin{pmatrix}    (X_{1}\times err_{x}+bias_{x}) & (Y_{1}\times err_{y}+bias_{y}) & (Z_{1}\times err_{z}+bias_{z})\\  (X_{2}\times err_{x}+bias_{x}) & (Y_{2}\times err_{y}+bias_{y}) & (Z_{2}\times err_{z}+bias_{z})\\  (X_{3}\times err_{x}+bias_{x}) & (Y_{3}\times err_{y}+bias_{y}) & (Z_{3}\times err_{z}+bias_{z})\\  (X_{4}\times err_{x}+bias_{x}) & (Y_{4}\times err_{y}+bias_{y}) & (Z_{4}\times err_{z}+bias_{z})\\  (X_{5}\times err_{x}+bias_{x}) & (Y_{5}\times err_{y}+bias_{y}) & (Z_{5}\times err_{z}+bias_{z})\\  (X_{6}\times err_{x}+bias_{x}) & (Y_{6}\times err_{y}+bias_{y}) & (Z_{6}\times err_{z}+bias_{z})\\    \end{pmatrix} = \begin{pmatrix}    0 & 0 &1 \\    0 & 0 &-1\\    0 & 1 & 0\\    0 & -1 &0\\    1 & 0 & 0\\    -1 & 0 & 0\\    \end{pmatrix}

Unfortunatly, I don’t have any calibrated rig available to do the measurement so it will make our life harder as we don’t known the direction of the gravity vector. However, whatever it’s direction, we still know that it’s norm is equal to 1g. So we can pose if the robot is standing still:

\sqrt{(X \times err_{x} + bias_{x})^{2} + (Y \times err_{y} + bias_{y})^{2} + (Z \times err_{z} + bias_{z})^{2}}=1

Which can be simplified as:

(X \times err_{x} + bias_{x})^{2} + (Y \times err_{y} + bias_{y})^{2} + (Z \times err_{z} + bias_{z})^{2} - 1 = 0

So to acheive our calibration process, we just have to find the roots of the following equation system:

\begin{pmatrix}    (X_{1} \times err_{x} + bias_{x})^{2} + (Y_{1} \times err_{y} + bias_{y})^{2} + (Z_{1} \times err_{z} + bias_{z})^{2}\\  (X_{2} \times err_{x} + bias_{x})^{2} + (Y_{2} \times err_{y} + bias_{y})^{2} + (Z_{2} \times err_{z} + bias_{z})^{2}\\  (X_{3} \times err_{x} + bias_{x})^{2} + (Y_{3} \times err_{y} + bias_{y})^{2} + (Z_{3} \times err_{z} + bias_{z})^{2}\\  (X_{4} \times err_{x} + bias_{x})^{2} + (Y_{4} \times err_{y} + bias_{y})^{2} + (Z_{4} \times err_{z} + bias_{z})^{2}\\  (X_{5} \times err_{x} + bias_{x})^{2} + (Y_{5} \times err_{y} + bias_{y})^{2} + (Z_{5} \times err_{z} + bias_{z})^{2}\\  (X_{6} \times err_{x} + bias_{x})^{2} + (Y_{6} \times err_{y} + bias_{y})^{2} + (Z_{6} \times err_{z} + bias_{z})^{2}\\    \end{pmatrix} = \begin{pmatrix}  1 \\  1 \\  1 \\  1 \\  1 \\  1 \\  \end{pmatrix}

Unfortunalty, that’s not so easy to solve because this equation system is not linear (some square unknown appear in the calculation).

That’s where Newton and his buddy Raphson come to save the day as they developped an algorithm which is going to be a great help in our case. The Newton Raphson method is a method to find an approximation of the root of a function by iteration.

The idea, is simple. Start with a value of your function  that you know is close to the solution. Calculate the derivate of the function for this point (which is the tangent line at this point) and determine when this tangent equals 0.  Then use this value as the new starting value and repeat the operation until you reach the needed precision.

NewtonIteration Ani

In other word for a single equation: x_{n+1} = x_{n}  - \frac{f(x_n)}{f'(x_n)}

This method can be extended to solve system of non linear equation but it gets a little bit more complex. In that case instead of dividing by f'(x) it can be shown that F(x) can be  left multiply by the inverse of its jacobian matrix.

X_{n+1} = X_{n} - J_{F}^{-1}(X_n) \times F(X_n)

A jacobian matrix is a matrix containing the first order partial derivates for each of our function.

J\begin{pmatrix}    f_0(x_0 \; x_1 \cdots x_j) \\    f_1(x_0 \; x_1 \cdots x_j) \\    \vdots \\    f_i(x_0 \; x_1 \cdots x_j) \\    \end{pmatrix}    =    \begin{pmatrix}    \frac{\partial f_0}{\partial x_0} & \frac{\partial f_0}{\partial x_1} & \cdots & \frac{\partial f_0}{\partial x_j} \\    \frac{\partial f_1}{\partial x_0} & \frac{\partial f_1}{\partial x_1} & \cdots & \frac{\partial f_1}{\partial x_j} \\    \vdots & \vdots & \ddots & \vdots\\    \frac{\partial f_i}{\partial x_0} & \frac{\partial f_i}{\partial x_1} & \cdots & \frac{\partial f_i}{\partial x_j} \\    \end{pmatrix}

So we only have to perform the partial derivate of  (X \times err_{x} + bias_{x})^{2} + (Y \times err_{y} + bias_{y})^{2} + (Z \times err_{z} + bias_{z})^{2} -1 = 0

On err _{x}, err _{y}, err _{z}, bias_{x}, bias_{y}, and bias_{z}.

The process of calculating a partial derivate is easy. Derivate according to one unknown and treat the other as constant. For example if we want to calculate the partial derivate of f_0 on err_{x}  we get:
\frac{\partial f_0}{\partial err_x} = (X_{1} \times err_{x} + bias_{x})^{2} + (Y_{1} \times err_{y} + bias_{y})^{2} + (Z_{1} \times err_{z} + bias_{z})^{2} - 1) . \partial err_x

\frac{\partial f_0}{\partial err_x} = ((X_{1} \times err_{x} + bias_{x})^{2} + C) .\partial err_x

\frac{\partial f_0}{\partial err_x} = ((X_{1} \times err_{x} + bias_{x})^{2} ) .\partial err_x

\frac{\partial f_0}{\partial err_x} =  2 (X_{1}^{2} \times err_{x} + X_{1} \times err_x)

The same way we can show that
\frac{\partial f_0}{\partial bias_x} = 2 (X_{1} * err_{x} + bias {x})

We can extrapolate our jacobian matrix for our functions:

J_F = \begin{pmatrix}    2 (X_{1}^{2} \times err_{x} + X_{1} \times bias_{x}) & 2 (Y_{1}^{2} \times err_{y} + Y_{1} \times bias_{y}) &  2 (Z_{1}^{2} \times err_{z} + Z_{1} \times bias_{z}) & (X_{1} * err_{x} + bias {x}) & (Y_{1} * err_{y} + bias {y}) & (Z_{1} * err_{z} + bias {z}) \\    2 (X_{2}^{2} \times err_{x} + X_{2} \times bias_{x}) & 2 (Y_{2}^{2} \times err_{y} + Y_{2} \times bias_{y}) &  2 (Z_{2}^{2} \times err_{z} + Z_{2} \times bias_{z}) & (X_{2} * err_{x} + bias {x}) & (Y_{2} * err_{y} + bias {y}) & (Z_{2} * err_{z} + bias {z}) \\    2 (X_{3}^{2} \times err_{x} + X_{3} \times bias_{x}) & 2 (Y_{3}^{2} \times err_{y} + Y_{3} \times bias_{y}) &  2 (Z_{3}^{2} \times err_{z} + Z_{3} \times bias_{z}) & (X_{3} * err_{x} + bias {x}) & (Y_{3} * err_{y} + bias {y}) & (Z_{3} * err_{z} + bias {z}) \\    2 (X_{4}^{2} \times err_{x} + X_{4} \times bias_{x}) & 2 (Y_{4}^{2} \times err_{y} + Y_{4} \times bias_{y}) &  2 (Z_{4}^{2} \times err_{z} + Z_{4} \times bias_{z}) & (X_{4} * err_{x} + bias {x}) & (Y_{4} * err_{y} + bias {y}) & (Z_{4} * err_{z} + bias {z}) \\    2 (X_{5}^{2} \times err_{x} + X_{5} \times bias_{x}) & 2 (Y_{5}^{2} \times err_{y} + Y_{5} \times bias_{y}) &  2 (Z_{5}^{2} \times err_{z} + Z_{5} \times bias_{z}) & (X_{5} * err_{x} + bias {x}) & (Y_{5} * err_{y} + bias {y}) & (Z_{5} * err_{z} + bias {z}) \\    2 (X_{6}^{2} \times err_{x} + X_{6} \times bias_{x}) & 2 (Y_{6}^{2} \times err_{y} + Y_{6} \times bias_{y}) &  2 (Z_{6}^{2} \times err_{z} + Z_{6} \times bias_{z}) & (X_{6} * err_{x} + bias {x}) & (Y_{6} * err_{y} + bias {y}) & (Z_{6} * err_{z} + bias {z}) \\    \end{pmatrix}

That’s a big matrix, but at the end, it is only the two same easy computation repeated each 3 times.

However we are not done yet, as Newton algorithm asks us to invert this matrix but it can be very time consuming to do so. So we can change this:
X_{n+1} = X_{n} - J_{F}^{-1}(X_n) \times F(X_n)
to look like this:
J_F(X_n)(X_{n+1} - X_n) = -F(X_n)
And solve this equation system with (X_{n+1} - X_n) as the unknown.

This time this system is linear and you may have notice that it is in the form of B = A . X which is “easy” to solve using a LU decomposition.

Fortunatly for us, we won’t have to do it ourself (that’s way too many math already! ) as a nice library called Eigen is offering to do the job for us. This library is completly template based so we just have to include the header in our code and solving this equation is as simple as:

MatrixXd Xd = jacobian.lu().solve(-F);

And we are done ! We just have to repeat the process until we reach the precision we want.

So finally how is the code looking ? very simple compared to the rest of this article 🙂

double CSensorCalibration::partialDerivateOffset (double val, double offset, double scale)
{
	double ret =  2.0 * (val * scale + offset);
	return ret;
}

double CSensorCalibration::partialDerivateScale (double val, double offset, double scale)
{
	double ret =  2.0 * (val * val * scale + val * offset);
	return ret;
}

MatrixXd CSensorCalibration::solve (MatrixXd & Meas)
{
	MatrixXd jacobian(6,6);
	MatrixXd X(6,1);
	MatrixXd F(6,1);
	int32_t iter;
        
	//Init solution
	X << 0.0, 0.0, 0.0, 1.0, 1.0, 1.0;

	for (iter = 0; iter < MAX_ITERATION; iter++)
	{
		//Calculate jacobian matrix   
		for (int i = 0; i < 6; i++)
		{
			for (int k = 0; k < 3; k++)
			{
				jacobian(i,k) = partialDerivateOffset(Meas(i,k),X(k,0),X(3+k,0));
				jacobian(i,3+k) = partialDerivateScale(Meas(i,k),X(k,0),X(3+k,0));
			}
		}
		//Compute "result" matrix.
		for (int i = 0; i < 6; i++)
		{
			F(i,0) = pow(Meas(i,0)*X(3,0) + X(0,0), 2) + pow(Meas(i,1)*X(4,0) + X(1,0), 2) + pow(Meas(i,2)*X(5,0) + X(2,0), 2) - 1;
		}

		//Check if we reached our precision requierement.
                if (abs(F.sum()) <= LIMIT_CONV_FUNCT)
		{
			break;
		}

		//Solve J_F(x_n)(x_{n+1} - x_n) = -F(x_n)
		MatrixXd Xd = jacobian.lu().solve(-F);

		//Check if we reached our precision requierement.
		if (abs(Xd.sum()) <= LIMIT_CONV_ROOT)
		{
			break;
		}

		//Update our result as the equation is giving us the (x_{n+1} - x_n).
		X = X + Xd;
	}
	return X;

}

LSM9DS1, Madgwick’s AHR filter and robot orientation

My original plan was to do several posts about general information and then go deeper into some topics, but as I’m currently working on getting the ST iNEMO LSM9DS1 intertial module to work, I thought that I might as well start this blog on this subject.

One of the thing I would like to achieve with this robot is to get it as close as possible of being capable of navigating and avoiding obstacles autonomously so it can, for example, returns to its starting position by itself.

As it will be used mostly indoor, using a GPS for precise positioning is not possible, so we have to rely on less accurate sensors. A 9DOF inertial module in the form of a LSM9DS1 from ST(datasheet), will be the main sensors to evaluate the robot position. This chip is in reality two components into a single package with a 3D accelerometer / gyroscope on one side, and a 3D magnetometer (compass) on the other side.

This kind of sensors are cheap, and are able to give the acceleration, the angular speed, as well as measuring the magnetic field but they are also not very accurate. For instance, apart from the usual “noise” of the measurement, gyroscope has an output drift which is dependant of the chip temperature and the magnetometer is subject to several measurement impairment due to the presence of other magnetic components (especially in a robot were motors are close !!!).  It is possible to  mitigate some of the errors  by performing a sensor calibration without completely removing them. Also if we want to be able to evaluate the speed and position of the robot based on the accelerometer, we need to remove the acceleration due to the gravity which means we need to be able to evaluate precisly the direction of the gravity in the sensor reference frame.

That’s where the filter proposed by Sebastian Madgwick comes into play (more info).  This filter combines data from the gyroscope, accelerometer and magnetometer to estimate the orientation (in the form a quaternion) of the device according to the earth reference (magnetic north and gravity). This algorithm acheive a good accuracy even if the device is subject to linear accelerations and is robust to sensors bias and drift. It is also open source and  C code is  available!

So, everything perfect, right? Not really and I have been struggling a little bit to get the correct output from the filter. Main reason for that the source code of the filter does not provide any documentation about the convention used for the input values: unit and axis orientation. So I had to dig into Sebastian Madgwick’s paper to find some info.

Units are simples. The filter needs to have the gyroscope data expressed as rad.s-1. For the acceleration and magnetic field, however, you can use any unit you like, because the values are normalized in the filter (only the vector orientation is important).

However, getting a clear answer about the axis orientation was difficult. On some discussion I found that the madgwick filter’s is using a NED  (x pointing north, y pointing east and z pointing down) convention just like in aviation.  This is not completely correct. Madgwick’s filter is indeed using a right handed axis convention but as show in Madgwick paper on page 5, the Z axis is pointing up and not down.

madgwick_axis

This can also be confirmed by the Xsens MTX user Manual  which was used to perform the algorithm evaluation and is using the same convention.

Where it gets a little bit confusing, is that Madgwick is giving the formulae to get the euler angles from the quaternion representation in his paper.

madgwick_euler_angles

Where ψ is yaw, θ is pitch and Φ is roll.

If you use theses equations, the calculated roll, pitch and yaw will be according to the aircraft convention (NED), but for the roll which need to be inverted.

Yaw_Axis_Corrected.svg

Finally, Madgwick is using variables q0, q1, q2 and q3 (or q1, q2, q3 and q4 in his paper) to represent the quaternion. But sometimes you can find quaternion represented as x, y, z and w (as in unity 3D). If for some reason, you want to use the filter output for something else, just be aware that w is equivalent to q0, not q3.

So now that we know what is expected by the filter, what about the output of the LSM9DS1 ? For accelerometer/gyroscope, the datasheet is giving the following:

LSM9DS1_accelgyro_orient

Orientation reference is left handed, so we can’t use the output as it is but swapping from left handed to right handed axis is easy, we just have to swap the X and Y axis for gyro and accelerometer.  Finally we have to align the X axis point to the front of the robot (and Y to be the left side). For Yapibot, I got lucky as the Y axis of the sensor is pointing to the front of the robot so I can just apply:

Yapibot.ax = LSM9DS1.ay
Yapibot.ay = LSM9DS1.ax
Yapibot.az = LSM9DS1.az

And for the gyro:

Yapibot.gx = LSM9DS1.gy
Yapibot.gy = LSM9DS1.gx
Yapibot.gz = LSM9DS1.gz

The same way, we need to adapt the ouput of the magnetometer according to our reference.

LSM9DS1_mag_orient

Be careful here because for some reason, ST did not use the same orientation of the diagram (dot on the chip is up, while for accel/gyro it is on the left) (IT’S A TRAP!). So finally, compared to the accel/gyro, only the X direction is inverted.

Yapibot.mx = LSM9DS1.my
Yapibot.my = -LSM9DS1.mx
Yapibot.mz = LSM9DS1.mz

Using this convention, I have been able to correctly get the orientation of the robot.

20160820_112329