Here&#39;s a proof-of-concept showing a 5-point median feeding a weighted moving average.<br><br>----smoothing.c----<br><font face="courier new,monospace">/*<br>&nbsp;* sample smoothing proof-of-concept<br>&nbsp;*/<br>#include &lt;stddef.h&gt;<br>
#include &lt;stdlib.h&gt;<br>#include &lt;stdio.h&gt;<br>#include &lt;assert.h&gt;<br><br>#define&nbsp;&nbsp;&nbsp; W&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; 5&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; /* smoothing window */<br><br>struct smooth {<br>&nbsp;&nbsp;&nbsp; int&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; data[W];&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; /* data samples */<br>
&nbsp;&nbsp;&nbsp; int&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; sort[W];&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; /* sorted data */<br>&nbsp;&nbsp;&nbsp; int&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; pos;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; /* circular data buffer position */<br>&nbsp;&nbsp;&nbsp; int&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; avg;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; /* 2x moving average */<br>};<br><br>void<br>init_smooth(struct smooth* p)<br>
{<br>&nbsp;&nbsp;&nbsp; int i;<br>&nbsp;&nbsp;&nbsp; <br>&nbsp;&nbsp;&nbsp; for (i = 0; i &lt; W; ++i) {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; p-&gt;data[i] = 0;<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; p-&gt;sort[i] = 0;<br>&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; p-&gt;pos = 0;<br>&nbsp;&nbsp;&nbsp; p-&gt;avg = 0;<br>}<br><br>#define&nbsp;&nbsp;&nbsp; get_smooth(p)&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; (((p)-&gt;avg) &gt;&gt; 1)<br>
#define&nbsp;&nbsp;&nbsp; get_median(p)&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; ((p)-&gt;sort[W/2])<br><br>void<br>put_smooth(struct smooth* p, int value)<br>{<br>&nbsp;&nbsp;&nbsp; p-&gt;data[p-&gt;pos] = value;<br>&nbsp;&nbsp;&nbsp; if (p-&gt;pos &lt;= 0) {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; p-&gt;pos = W;<br>&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; --p-&gt;pos;<br>
}<br><br>void<br>sort_smooth(struct smooth* p)<br>{<br>&nbsp;&nbsp;&nbsp; int i;<br>&nbsp;&nbsp;&nbsp; int j;<br>&nbsp;&nbsp;&nbsp; int k;<br>&nbsp;&nbsp;&nbsp; int n;<br>&nbsp;&nbsp;&nbsp; <br>&nbsp;&nbsp;&nbsp; i = p-&gt;pos;<br>&nbsp;&nbsp;&nbsp; for (k = 0; k &lt; W; ++k) {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; /* get sample from ring buffer */<br>
&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if (i &lt;= 0) {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; i = W;<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; --i;<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; n = p-&gt;data[i];<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; /* insert into sorted list */<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; for (j = 0; j &lt; k; ++j) {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if (p-&gt;sort[j] &gt;= n) {<br>
&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; int m = k;<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; while (j &lt; m) {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; p-&gt;sort[m] = p-&gt;sort[m - 1];<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; m -= 1;<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; break;<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }<br>
&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; p-&gt;sort[j] = n;<br>&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; /* done sorting, pick median &amp; add to average */<br>&nbsp;&nbsp;&nbsp; p-&gt;avg = get_median(p) + get_smooth(p);<br>}<br><br>void<br>dump_smooth(struct smooth* p)<br>{<br>&nbsp;&nbsp;&nbsp; int i;<br>
&nbsp;&nbsp;&nbsp; <br>&nbsp;&nbsp;&nbsp; printf(&quot;data=[&quot;);<br>&nbsp;&nbsp;&nbsp; i = p-&gt;pos;<br>&nbsp;&nbsp;&nbsp; while(1) {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; ++i;<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if (i &gt;= W) {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; i = 0;<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; printf(&quot;%d&quot;, p-&gt;data[i]);<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; if (i == p-&gt;pos) {<br>
&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; printf(&quot;] &quot;);<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; break;<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; printf(&quot;,&quot;);<br>&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; printf(&quot;sort=[&quot;);<br>&nbsp;&nbsp;&nbsp; for (i = 0; i &lt; W; ++i) {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; printf(&quot;%s%d&quot;, (i ? &quot;,&quot; : &quot;&quot;), p-&gt;sort[i]);<br>
&nbsp;&nbsp;&nbsp; }<br>&nbsp;&nbsp;&nbsp; printf(&quot;] &quot;);<br>&nbsp;&nbsp;&nbsp; printf(&quot;median=%d smooth=%d &quot;, get_median(p), get_smooth(p));<br>&nbsp;&nbsp;&nbsp; printf(&quot;avg(x2)=%d\n&quot;, p-&gt;avg);<br>}<br><br>/**<br>SAMPLE DATA<br><br>1213744740.484058:&nbsp;&nbsp;&nbsp; 511&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>
1213744740.489078:&nbsp;&nbsp;&nbsp; 513&nbsp;&nbsp;&nbsp; 588&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.494059:&nbsp;&nbsp;&nbsp; 511&nbsp;&nbsp;&nbsp; 588&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.499058:&nbsp;&nbsp;&nbsp; 509&nbsp;&nbsp;&nbsp; 588&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.504078:&nbsp;&nbsp;&nbsp; 485&nbsp;&nbsp;&nbsp; 591&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1&nbsp; &lt;===<br>1213744740.509058:&nbsp;&nbsp;&nbsp; 509&nbsp;&nbsp;&nbsp; 591&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>
1213744740.514079:&nbsp;&nbsp;&nbsp; 506&nbsp;&nbsp;&nbsp; 586&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.519078:&nbsp;&nbsp;&nbsp; 511&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.524078:&nbsp;&nbsp;&nbsp; 507&nbsp;&nbsp;&nbsp; 587&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.529079:&nbsp;&nbsp;&nbsp; 511&nbsp;&nbsp;&nbsp; 586&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.534059:&nbsp;&nbsp;&nbsp; 511&nbsp;&nbsp;&nbsp; 590&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.539058:&nbsp;&nbsp;&nbsp; 509&nbsp;&nbsp;&nbsp; 590&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>
1213744740.544078:&nbsp;&nbsp;&nbsp; 420&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1&nbsp; &lt;===<br>1213744740.549079:&nbsp;&nbsp;&nbsp; 509&nbsp;&nbsp;&nbsp; 591&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.554078:&nbsp;&nbsp;&nbsp; 501&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.559078:&nbsp;&nbsp;&nbsp; 511&nbsp;&nbsp;&nbsp; 588&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.564079:&nbsp;&nbsp;&nbsp; 490&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1&nbsp; &lt;===<br>
1213744740.569058:&nbsp;&nbsp;&nbsp; 511&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.574078:&nbsp;&nbsp;&nbsp; 512&nbsp;&nbsp;&nbsp; 588&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.579078:&nbsp;&nbsp;&nbsp; 511&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.584078:&nbsp;&nbsp;&nbsp; 513&nbsp;&nbsp;&nbsp; 588&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.589078:&nbsp;&nbsp;&nbsp; 512&nbsp;&nbsp;&nbsp; 583&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.594079:&nbsp;&nbsp;&nbsp; 510&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>
1213744740.599098:&nbsp;&nbsp;&nbsp; 514&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.604078:&nbsp;&nbsp;&nbsp; 510&nbsp;&nbsp;&nbsp; 588&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.609058:&nbsp;&nbsp;&nbsp; 509&nbsp;&nbsp;&nbsp; 588&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.614058:&nbsp;&nbsp;&nbsp; 514&nbsp;&nbsp;&nbsp; 588&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.619078:&nbsp;&nbsp;&nbsp; 511&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.624059:&nbsp;&nbsp;&nbsp; 517&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>
1213744740.629057:&nbsp;&nbsp;&nbsp; 505&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.634058:&nbsp;&nbsp;&nbsp; 511&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>1213744740.639089:&nbsp;&nbsp;&nbsp; 523&nbsp;&nbsp;&nbsp; 589&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1&nbsp; &lt;===<br>1213744740.644116:&nbsp;&nbsp;&nbsp; 508&nbsp;&nbsp;&nbsp; 590&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1<br>**/<br><br>static int sample_data[] = {<br>
&nbsp;&nbsp;&nbsp; 100,<br>&nbsp;&nbsp;&nbsp; 101,<br>&nbsp;&nbsp;&nbsp; 102,<br>&nbsp;&nbsp;&nbsp; 103,<br>&nbsp;&nbsp;&nbsp; 104,<br>&nbsp;&nbsp;&nbsp; 105,<br>&nbsp;&nbsp;&nbsp; 511, /* start */<br>&nbsp;&nbsp;&nbsp; 513,<br>&nbsp;&nbsp;&nbsp; 511,<br>&nbsp;&nbsp;&nbsp; 509,<br>&nbsp;&nbsp;&nbsp; 485, /* &lt;=== */<br>&nbsp;&nbsp;&nbsp; 509,<br>&nbsp;&nbsp;&nbsp; 506,<br>&nbsp;&nbsp;&nbsp; 511,<br>&nbsp;&nbsp;&nbsp; 507,<br>&nbsp;&nbsp;&nbsp; 511,<br>&nbsp;&nbsp;&nbsp; 511,<br>
&nbsp;&nbsp;&nbsp; 509,<br>&nbsp;&nbsp;&nbsp; 420, /* &lt;=== */<br>&nbsp;&nbsp;&nbsp; 509,<br>&nbsp;&nbsp;&nbsp; 501,<br>&nbsp;&nbsp;&nbsp; 511,<br>&nbsp;&nbsp;&nbsp; 490, /* &lt;=== */<br>&nbsp;&nbsp;&nbsp; 511,<br>&nbsp;&nbsp;&nbsp; 512,<br>&nbsp;&nbsp;&nbsp; 511,<br>&nbsp;&nbsp;&nbsp; 513,<br>&nbsp;&nbsp;&nbsp; 512,<br>&nbsp;&nbsp;&nbsp; 510,<br>&nbsp;&nbsp;&nbsp; 514,<br>&nbsp;&nbsp;&nbsp; 510,<br>&nbsp;&nbsp;&nbsp; 509,<br>&nbsp;&nbsp;&nbsp; 514,<br>&nbsp;&nbsp;&nbsp; 511,<br>
&nbsp;&nbsp;&nbsp; 517,<br>&nbsp;&nbsp;&nbsp; 505,<br>&nbsp;&nbsp;&nbsp; 511,<br>&nbsp;&nbsp;&nbsp; 523, /* &lt;=== */<br>&nbsp;&nbsp;&nbsp; 508<br>};<br><br>void<br>test_smoothing()<br>{<br>&nbsp;&nbsp;&nbsp; int i;<br>&nbsp;&nbsp;&nbsp; int n;<br>&nbsp;&nbsp;&nbsp; struct smooth s;<br>&nbsp;&nbsp;&nbsp; struct smooth* p = &amp;s;<br><br>&nbsp;&nbsp;&nbsp; assert(p != NULL);<br>
&nbsp;&nbsp;&nbsp; init_smooth(p);<br>&nbsp;&nbsp;&nbsp; assert(get_smooth(p) == 0);<br>&nbsp;&nbsp;&nbsp; dump_smooth(p);<br><br>&nbsp;&nbsp;&nbsp; n = sizeof(sample_data) / sizeof(int);<br>&nbsp;&nbsp;&nbsp; for (i = 0; i &lt; n; ++i) {<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; put_smooth(p, sample_data[i]);<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; sort_smooth(p);<br>
&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; dump_smooth(p);<br>&nbsp;&nbsp;&nbsp; }<br>}<br><br>int<br>main(int argc, char** argv)<br>{<br>&nbsp;&nbsp;&nbsp; test_smoothing();<br>&nbsp;&nbsp;&nbsp; return (exit(EXIT_SUCCESS), 0);<br>}<br><br><br></font><br><div class="gmail_quote">On Thu, Jun 19, 2008 at 3:13 AM, Andy Green &lt;<a href="mailto:andy@openmoko.com">andy@openmoko.com</a>&gt; wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d">-----BEGIN PGP SIGNED MESSAGE-----<br>
Hash: SHA1<br>
<br></div><div class="Ih2E3d">
Somebody in the thread at some point said:<br>
| On 19.06.2008 01:14, Andy Green wrote:<br>
|&gt; Somebody in the thread at some point said:<br>
|&gt; | On 18.06.2008 22:46, Dale Schumacher wrote:<br>
|&gt; |&gt; The averaging scheme seems overly complicated. &nbsp;Using a &quot;median&quot;<br>
|&gt; instead of<br>
|&gt; |&gt; a &quot;mean&quot; (average) would automatically reject outliers and would also<br>
|&gt; track<br>
|&gt; |&gt; the mid-point of a moving signal. &nbsp;There should also be less math<br>
|&gt; involved<br>
|&gt; |&gt; since you would only be sorting 2 sets of 32 values.<br>
|&gt;<br>
|&gt; | Exactly what I suggested as well. I don&#39;t understand why people<br>
|&gt; | absolutely want to use averages and throw away outliers based on<br>
average<br>
|&gt; | calculations. Maybe because the concept of &quot;mean&quot; is easier to grasp<br>
|&gt; | than the concept of &quot;median&quot;. A median solves all these problems of<br>
data<br>
|&gt; | having outliers with less math and better accuracy.<br>
|&gt;<br>
|&gt; It&#39;s not a bad idea at all. &nbsp;You&#39;re quite right it &quot;automatically<br>
|&gt; rejects outliers&quot;. &nbsp;But, it&#39;s going to get a bit slow as the number of<br>
|&gt; samples held in whatever the sorting structure is increases,<br>
|<br>
| The secret is to keep the number of samples exactly at 5. You remove the<br>
<br></div>
There&#39;s also a question about how noisy one of the axes is, the hardware<br>
may not play ball with this nice idea -- it is a nice idea -- of magic<br>
number 5. &nbsp;Oldstyle averaging has good performance for &quot;averaging<br>
noise&quot;, jitter in the result can still come with this method if generic<br>
noise is present and skews one set of 5 one way, and another the other.<br>
~ Maybe some combination of mean and median gets the best result. &nbsp;I<br>
don&#39;t think what ails the bad axis is quite as simple as perfect results<br>
disturbed occasionally by an excursion, the raw samples seem to be all<br>
over the shop anyway (hidden a bit by mean averaging) and occasionally<br>
really crazy.<div class="Ih2E3d"><br>
<br>
|&gt; but if someone wants to send patches I&#39;ll be happy to be wrong.<br>
|<br>
| As I indicated before, I won&#39;t have time in the next 3 weeks, but if<br>
| there is something to be done afterwards, why not? I lack the hardware<br>
| to test, though, so I can only send untested patches.<br>
<br></div>
I&#39;m going to leave mine in until then, pending any complaints about<br>
performance or a better implementation turning up.<div class="Ih2E3d"><br>
<br>
- -Andy<br>
-----BEGIN PGP SIGNATURE-----<br>
Version: GnuPG v1.4.9 (GNU/Linux)<br>
Comment: Using GnuPG with Fedora - <a href="http://enigmail.mozdev.org" target="_blank">http://enigmail.mozdev.org</a><br>
<br></div>
iEYEARECAAYFAkhaFRkACgkQOjLpvpq7dMrkagCfaxPcDCH2+g26ZElYw3E5yND8<br>
H9wAnRW/eOQE3wQKIGZnlwh+tNZfFEI4<br>
=TYbf<br>
-----END PGP SIGNATURE-----<br>
</blockquote></div><br>