Zero motion detection for low cost MEMS units is an extremely important topic that has not received enough attention in the navigation community. For most low-cost inertial navigation applications, the only aiding source that can be used to limit the velocity errors (and thus reduce the position error divergence rate) is the zero-velocity updates. Despite its significance, there is only a couple of papers that deal with the detection of the zero-motion instants and, unfortunately, some of these papers are written by self-deceptive ignorants. (After this blog entry, I am planning to write another entry just to expose one such example.)
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.