Here'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> * sample smoothing proof-of-concept<br> */<br>#include <stddef.h><br>
#include <stdlib.h><br>#include <stdio.h><br>#include <assert.h><br><br>#define W 5 /* smoothing window */<br><br>struct smooth {<br> int data[W]; /* data samples */<br>
int sort[W]; /* sorted data */<br> int pos; /* circular data buffer position */<br> int avg; /* 2x moving average */<br>};<br><br>void<br>init_smooth(struct smooth* p)<br>
{<br> int i;<br> <br> for (i = 0; i < W; ++i) {<br> p->data[i] = 0;<br> p->sort[i] = 0;<br> }<br> p->pos = 0;<br> p->avg = 0;<br>}<br><br>#define get_smooth(p) (((p)->avg) >> 1)<br>
#define get_median(p) ((p)->sort[W/2])<br><br>void<br>put_smooth(struct smooth* p, int value)<br>{<br> p->data[p->pos] = value;<br> if (p->pos <= 0) {<br> p->pos = W;<br> }<br> --p->pos;<br>
}<br><br>void<br>sort_smooth(struct smooth* p)<br>{<br> int i;<br> int j;<br> int k;<br> int n;<br> <br> i = p->pos;<br> for (k = 0; k < W; ++k) {<br> /* get sample from ring buffer */<br>
if (i <= 0) {<br> i = W;<br> }<br> --i;<br> n = p->data[i];<br> /* insert into sorted list */<br> for (j = 0; j < k; ++j) {<br> if (p->sort[j] >= n) {<br>
int m = k;<br> while (j < m) {<br> p->sort[m] = p->sort[m - 1];<br> m -= 1;<br> }<br> break;<br> }<br>
}<br> p->sort[j] = n;<br> }<br> /* done sorting, pick median & add to average */<br> p->avg = get_median(p) + get_smooth(p);<br>}<br><br>void<br>dump_smooth(struct smooth* p)<br>{<br> int i;<br>
<br> printf("data=[");<br> i = p->pos;<br> while(1) {<br> ++i;<br> if (i >= W) {<br> i = 0;<br> }<br> printf("%d", p->data[i]);<br> if (i == p->pos) {<br>
printf("] ");<br> break;<br> }<br> printf(",");<br> }<br> printf("sort=[");<br> for (i = 0; i < W; ++i) {<br> printf("%s%d", (i ? "," : ""), p->sort[i]);<br>
}<br> printf("] ");<br> printf("median=%d smooth=%d ", get_median(p), get_smooth(p));<br> printf("avg(x2)=%d\n", p->avg);<br>}<br><br>/**<br>SAMPLE DATA<br><br>1213744740.484058: 511 589 1<br>
1213744740.489078: 513 588 1<br>1213744740.494059: 511 588 1<br>1213744740.499058: 509 588 1<br>1213744740.504078: 485 591 1 <===<br>1213744740.509058: 509 591 1<br>
1213744740.514079: 506 586 1<br>1213744740.519078: 511 589 1<br>1213744740.524078: 507 587 1<br>1213744740.529079: 511 586 1<br>1213744740.534059: 511 590 1<br>1213744740.539058: 509 590 1<br>
1213744740.544078: 420 589 1 <===<br>1213744740.549079: 509 591 1<br>1213744740.554078: 501 589 1<br>1213744740.559078: 511 588 1<br>1213744740.564079: 490 589 1 <===<br>
1213744740.569058: 511 589 1<br>1213744740.574078: 512 588 1<br>1213744740.579078: 511 589 1<br>1213744740.584078: 513 588 1<br>1213744740.589078: 512 583 1<br>1213744740.594079: 510 589 1<br>
1213744740.599098: 514 589 1<br>1213744740.604078: 510 588 1<br>1213744740.609058: 509 588 1<br>1213744740.614058: 514 588 1<br>1213744740.619078: 511 589 1<br>1213744740.624059: 517 589 1<br>
1213744740.629057: 505 589 1<br>1213744740.634058: 511 589 1<br>1213744740.639089: 523 589 1 <===<br>1213744740.644116: 508 590 1<br>**/<br><br>static int sample_data[] = {<br>
100,<br> 101,<br> 102,<br> 103,<br> 104,<br> 105,<br> 511, /* start */<br> 513,<br> 511,<br> 509,<br> 485, /* <=== */<br> 509,<br> 506,<br> 511,<br> 507,<br> 511,<br> 511,<br>
509,<br> 420, /* <=== */<br> 509,<br> 501,<br> 511,<br> 490, /* <=== */<br> 511,<br> 512,<br> 511,<br> 513,<br> 512,<br> 510,<br> 514,<br> 510,<br> 509,<br> 514,<br> 511,<br>
517,<br> 505,<br> 511,<br> 523, /* <=== */<br> 508<br>};<br><br>void<br>test_smoothing()<br>{<br> int i;<br> int n;<br> struct smooth s;<br> struct smooth* p = &s;<br><br> assert(p != NULL);<br>
init_smooth(p);<br> assert(get_smooth(p) == 0);<br> dump_smooth(p);<br><br> n = sizeof(sample_data) / sizeof(int);<br> for (i = 0; i < n; ++i) {<br> put_smooth(p, sample_data[i]);<br> sort_smooth(p);<br>
dump_smooth(p);<br> }<br>}<br><br>int<br>main(int argc, char** argv)<br>{<br> test_smoothing();<br> 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 <<a href="mailto:andy@openmoko.com">andy@openmoko.com</a>> 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>
|> Somebody in the thread at some point said:<br>
|> | On 18.06.2008 22:46, Dale Schumacher wrote:<br>
|> |> The averaging scheme seems overly complicated. Using a "median"<br>
|> instead of<br>
|> |> a "mean" (average) would automatically reject outliers and would also<br>
|> track<br>
|> |> the mid-point of a moving signal. There should also be less math<br>
|> involved<br>
|> |> since you would only be sorting 2 sets of 32 values.<br>
|><br>
|> | Exactly what I suggested as well. I don't understand why people<br>
|> | absolutely want to use averages and throw away outliers based on<br>
average<br>
|> | calculations. Maybe because the concept of "mean" is easier to grasp<br>
|> | than the concept of "median". A median solves all these problems of<br>
data<br>
|> | having outliers with less math and better accuracy.<br>
|><br>
|> It's not a bad idea at all. You're quite right it "automatically<br>
|> rejects outliers". But, it's going to get a bit slow as the number of<br>
|> 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'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. Oldstyle averaging has good performance for "averaging<br>
noise", 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. I<br>
don'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>
|> but if someone wants to send patches I'll be happy to be wrong.<br>
|<br>
| As I indicated before, I won'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'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>