Theoretically, it is impossible to detect zero velocity instants by relying only on the accelerometers and gyroscopes. Even if we had perfect inertial sensors, which are completely noise free, and used the magnitude of the gravity and Earth rotation rate as our decision thresholds, our detection algorithm would not be able to differentiate a constant motion from a zero-velocity.

However, because of its importance especially for human motion tracking algorithms, we have to improvise some kind of a zero-motion detection method. As long as these algorithms do not generate too much false positives (zero-motion detection during a motion), we can still use them to diminish the accumulated velocity errors and, to a certain extent, to stabilize the roll/pitch errors.

In addition to this false-positive problem, zero-motion detectors also impose a big burden on the processing side. As I have described in my previous blog entries, we do not need inertial sensors to have very high data rates. As long as they provide angle and velocity increments, we can read their outputs at a very low rate without causing any algorithmic error. However, this is not the case for zero motion detectors at all. Zero-motion detectors need as many samples as possible to reduce their false positive probabilities. That is the reason why we need MEMS sensor producers to embed such decision algorithms into their sensors so that we don’t have to deal with all the problems associated with the high data rates.

Unfortunately, realizing this approach is not as easy as it may seem. First of all, what is a zero motion detection algorithm? Does anyone has ever answer this question? Or, does anyone have ever been able to come up with an optimal detector? The answer is unfortunately no. As a matter of fact the answer will always be “no”, because theoretically it is impossible to find one. All we can do is to adapt some ad-hoc method and hope for the best. In this case, what kind of algorithm can we expect from MEMS producers to embed in their system? Can such a thing be possible by any means?

Recently, I have been working on this issue. I tried to invent a method to be embedded in MEMS sensors such that it can be used for both ordinary and advanced users to detect zero motion instants. Ordinary users only need auto-decision result (regardless of its false positive rate), whereas an advanced user would possibly require all the raw sensor data to generate its own decision. A practical algorithm should also be capable of helping the user in between these groups by providing only the sufficient amount of useful data required for a meaningful decision.

At first I tried to formulate zero motion detection problem in terms of H-infinity settings. For a robust detection algorithm, we have to assume that nature always try to deceive us as much as possible. Therefore, I hoped I could come up with a meaningful 2-people zero-sum game definition and then robustly estimate the worst case motion. However, as in the case of my previous PhD topic, I totally failed. (I had studied the application of H-infinity theory to the navigation systems for 2 years before switching to my last PhD topic of redundant sensors and finally being able to graduate.)

Meanwhile, I realized one important fact about the motion: an acceptable motion definition certainly requires a scale to be associated to the data. Both a spike and almost a constant value in the sensor outputs may denote (hint) a motion. A spike cannot be detected if the data is analyzed at higher levels (averaged signals), whereas a small (almost) constant level output will be burried into additive sensor white noise if the analysis is performed at a very low level (row signal level).

As a result, I abandoned h-infinity concept and turned my attention into multi-resolution signal techniques. At the end, I came up with reasonable (non-orthogonal) signal bases each of which represent the change in different scales within a given data window. Together with these bases I also needed to derive some kind of threshold for the decision algorithm. I did not have to think about this part at all because I already knew that Allan variance coefficients is nothing but the Haar wavelet variance of the stationary signal. Therefore, previously computed Allan variance coefficients contain all the threshold values that I needed. Combining all these pieces of findings together, I finalized my zero-motion detector for low cost MEMS units. Given a data window, my detector first computes the signal coefficients for each basis function and then compares these coefficients with the threshold values to determine whether a motion exists or not.
In the following video, you can see the result of my zero motion detector. I wrote a simple application to broadcast the inertial sensor data of my “wannabe death” htc phone. I also coded simple python scripts to process these data in real time with my zero motion detector on the PC side. At the end, I output the result of the detector using a simple 2-color GUI. The red rectangle means a zero-motion detection instant and the green rectangle represents motion.

As you can see from the above video, my motion detection algorithm is at least capable of reasonably detecting motion/no motion instants. Although this video does not contain an example, my algorithm unavoidably suffers from false positives too. However, as the video proves, it can be still be considered sufficient for simple human motion tracking applications.
The most important feature of my algorithm is not its zero motion detection capability. The power of this algorithm comes from the fact that it relies on multi-resolution signal analysis. Therefore, it can serve for any user group equally well. If such an algorithm is embedded in an inertial sensor, the user can easily determine the amount of useful decision data to be delivered from the sensor. For instance, an average user can request the sensor to send only the biggest 5 coefficients, whereas an advanced user can request all the coefficients to reconstruct the original signal. In the above video, the decision is based on only the biggest coefficient which is all an ordinary user would probably care about.

With this final invention of mine, I am one step closer to my ultimate smart front-end design for MEMS inertial sensors. I know one day I will be able to convince some MEMS producers to listen to my genuine ideas.

Those of you who have some experience on the INSs may find this a little bit disturbing. Basically, both “C” and the “a” changes in an update interval. Therefore, such a first order approximation should not be theoretically valid.

Basically you are right. A decent INS implementation must consider this effect. In general, such integral compensations are performed as a part of the coning and sculling algorithms (which are now part of the toolkit). Although these algorithms are meant to remove the algorithmic bias effects generated by the so-called coning and sculling motions, the intra-minor steps of these algorithms also take care of the integral compensation terms. After compensated by these algorithms, the IMU outputs can be directly used in the INS without requiring any special integration considerations in the strapdown implementation.

The beautiful part of this approach is that the IMU and the INS algorithms can be distinctively separated. The coning and sculling algorithms are black-box type algorithms for IMU sections (or boards). They operate only on the sensor outputs in a user defined interval and provide compensated outputs which are later processed by the strapdown algorithms like the ones in the toolkit. That is why, despite the simple integration approximation, the strapdown implementations in the toolkit are theoretically correct.

Most MEMS producers are not aware of this very simple fact. They only provide inertial measurements (i.e. acceleration and rotation rate) at the highest possible sensor rate and force to INS designers to read all the data separately. But INS designers don’t need such high rates. Even the missiles cruising in the subsonic region executes the INS algoithms at 100-200Hz rates. Only the compensated senor outputs at a moderate rate is sufficient for most commercial applications. As explained above, thanks to the IMU compensation algorithms, no integral error is induced in the strapdown algorithms even with the fairly slow updates rates.

It will take probably 10 more years for MEMS producers to think of providing low-rate compensated sensor outputs rather than very high rate raw measurements. They are really too stupid to understand even the simplest things about inertial navigation. Meanwhile, it is us (the INS designers) who is going to suffer from their stupidity.

As an example consider the inertial sensors in the smart phones. If you want to design a navigation system based on these sensors you have to make the OS (i.e android) read data at least 200Hz. Just trying to read data at such high rates costs tremendous processing power for nothing. Furhtermore, at such high rates synchronization becomes impossible. (As a matter of fact the time tags in the sensor data for the android is completely useless either.) It will be more than sufficient to read inertial sensor outputs at rates lower than 25Hz (even much lower for most human tracking applications) if the sensors provide compensated outputs. Also in this case, the unknown time jitter problem would also be less severe (or perhaps completely removed).

I am really disgusted by the overall ignorance in the inertial sensor industry. They don’t know and they don’t try to learn.

Here is a video showing a sample output with some real data:

In this video, the embedded navigation code processed the sensor data at 100HZ. The Kalman filter covariance update was also set to 100Hz. The GPS outputs at 1HZ and some occasional heading information was processed by the 21 state Kalman filter to stabilize the INS outputs during the navigation.

As can be seen from the left-upper corner (the time tag information), the real duration of the sensor data used in this video was only 320 seconds. However, it took 15 minutes for the phone to process the data (this can be verified from the phone’s clock seen on the upper-right corner).

One reason for this huge execution duration was the screen capture application that was run together with the navigation code. When I ran the navigation code by itself without any screen capture the total execution duration dropped to 440 seconds which was again 120s longer than the real navigation duration.

In my desktop PC, it takes less than 10 seconds for the same navigation code to process the entire data. It is clear from these time results that the processors in the smartphones, which do not have a math-coprocessor, are not fast enough for real time navigation with the single speed INS implementations.

This simple experiment shows that a gps/ins system for the smartphones must have 3-speed structure with the following components:

1. High speed INS update (for inertial sensors)
2. Low speed INS update (for navigation frame updates)
3. Low speed KF covariance updates.

Furthermore, it would be quite wise if  “item 3″ is implemented as an additional thread.  However, in this case the asynchronous KF updates should be well synchronized with the covariance update thread in order to prevent disastrous mistakes.