Convert to rectangular average that and convert back to polar. Not as hard as it sounds. I did it years ago on an AVR. In asm
Mark Rages <spam_OUTmarkragesTakeThisOuTgmail.com> wrote:
>Suppose I have some measurements of an angle as integer degrees in the
>range [0, 359].
>
>I would like to find an average of these measurements as an estimate
>of the true angle.
>
>A simple numerical average doesn't work: Suppose the measurements are
>0, 1, 359. Then a simple average is 120, but the number I'm looking
>for is zero.
>
>Is there a standard algorithm to do what I want?
>
>Regards,
>Mark
>markrages@gmail
>
Bonus points, when you convert back to polar, the length vector is proportional to bearing quality.
Mark Rages <.....markragesKILLspam@spam@gmail.com> wrote:
>Suppose I have some measurements of an angle as integer degrees in the
>range [0, 359].
>
>I would like to find an average of these measurements as an estimate
>of the true angle.
>
>A simple numerical average doesn't work: Suppose the measurements are
>0, 1, 359. Then a simple average is 120, but the number I'm looking
>for is zero.
>
>Is there a standard algorithm to do what I want?
>
>Regards,
>Mark
>markrages@gmail
>
> Convert to rectangular average that and convert back to polar. Not as hard as it sounds. I did it years ago on an AVR. In asm
>
> Mark Rages <.....markragesKILLspam.....gmail.com> wrote:
>
>>Suppose I have some measurements of an angle as integer degrees in the
>>range [0, 359].
>>
>>I would like to find an average of these measurements as an estimate
>>of the true angle.
>>
>>A simple numerical average doesn't work: Suppose the measurements are
>>0, 1, 359. Then a simple average is 120, but the number I'm looking
>>for is zero.
>>
>>Is there a standard algorithm to do what I want?
>>
>>Regards,
>>Mark
>>markrages@gmail
A few years ago, I ran into the same thing for digital compass filtering. Wasn't really important so I did not implement it., but I came up with an idea that should've worked...
Pick an offset based on the first sample. If that first sample is between 270 (positive through 360) and up to 90, then use 180 for the offset.
Then add that offset to all samples and modulo 360, average, then subtract that offset. So your samples of 359,0,1 would be ((359+180) modulo 360), (0+180), (1 + 180) = 179, 180, 181 . Average = 180, then subtract the offset of 180 for a net result of 0.
For another example of 305, 309, 304, it would be ( ((305 + 180) modulo 360) + ((309 + 180) modulo 360) + ((304 + 180) modulo 180) ) / 3 - 180 = (125 + 129 + 124) / 3 -180 = 378 / 3 -180 = 126 - 180 = -54 (or 306 deg average).
> Suppose I have some measurements of an angle as integer degrees in the
> range [0, 359].
>
> I would like to find an average of these measurements as an estimate
> of the true angle.
>
> A simple numerical average doesn't work: Suppose the measurements are
> 0, 1, 359. Then a simple average is 120, but the number I'm looking
> for is zero.
>
> Is there a standard algorithm to do what I want?
>
> Regards,
> Mark
If (highest reading - lowest reading) > 180 // Wrap occurred
for each reading, if reading > 180, reading = reading - 360 // Convert to negative value
Average = sum of readings / number of readings
Examples:
358, 359, 1, 2
Highest - lowest (359-1) is > 180, so convert readings by subtracting 360 from each one over 180. Results are -2, -1, 1, 2, average is 0.
178, 179, 181, 182
Highest - lowest (182-178) is < 180, so don't convert readings. Results are 178, 179, 181, 182, average is 180.
Refer to the thread "Phase Averaging?" from June of last year.
> Suppose I have some measurements of an angle as integer degrees in the
> range [0, 359].
>
> I would like to find an average of these measurements as an estimate
> of the true angle.
>
> A simple numerical average doesn't work: Suppose the measurements are
> 0, 1, 359. Then a simple average is 120, but the number I'm looking
> for is zero.
>
> Is there a standard algorithm to do what I want?
>
> Regards,
> Mark
> markrages@gmail
Works for 16 bit calculations, but I wanted to stay in 8 bit for speed. I did simplify and assume that a circle has 255 dilberts which are a bit more than a degree.
PICdude <EraseMEpicdude3spam_OUTTakeThisOuTnarwani.org> wrote:
>A few years ago, I ran into the same thing for digital compass
>filtering. Wasn't really important so I did not implement it., but I
>came up with an idea that should've worked...
>
>Pick an offset based on the first sample. If that first sample is
>between 270 (positive through 360) and up to 90, then use 180 for the
>offset.
>
>Then add that offset to all samples and modulo 360, average, then
>subtract that offset. So your samples of 359,0,1 would be ((359+180)
>modulo 360), (0+180), (1 + 180) = 179, 180, 181 . Average = 180, then
>subtract the offset of 180 for a net result of 0.
>
>For another example of 305, 309, 304, it would be ( ((305 + 180) modulo
>360) + ((309 + 180) modulo 360) + ((304 + 180) modulo 180) ) / 3 - 180 =
>(125 + 129 + 124) / 3 -180 = 378 / 3 -180 = 126 - 180 = -54 (or 306 deg
>average).
>
>I haven't tested it exhaustively though.
>
>Cheers,
>-Neil.
>
>
>On 3/20/2012 10:34 PM, Mark Rages wrote:
>> Suppose I have some measurements of an angle as integer degrees in the
>> range [0, 359].
>>
>> I would like to find an average of these measurements as an estimate
>> of the true angle.
>>
>> A simple numerical average doesn't work: Suppose the measurements are
>> 0, 1, 359. Then a simple average is 120, but the number I'm looking
>> for is zero.
>>
>> Is there a standard algorithm to do what I want?
>>
>> Regards,
>> Mark
>> markrages@gmail
>
> are 0, 1, 359. Then a simple average is 120, but the number I'm
> looking for is zero
You'll have to treat a range as negative. Look at the circle as left
and right semi-circles
For example, if the values were all between 0 and 180 then the
result will be "positive", ie the average will be Eastward. If one is
over 180 then that is going to skew the average Westward. And
similarly if all the values but one were between 180 and 360
Consider the way values are handled in a micro. 127 is the most
positive, 128 is the most negative. For values that represent degrees,
0 is the least positive, 179 is the most positive, 180 is the most
negative, 359 is the least negative. In this case wrt North, or 0
degrees, which is where the circle starts and ends
So, 0, 1, 359 becomes 0, 1 and -1. The -1 is derived from 359
by (360 - value) if (value > 179) and designating it negative
Example ; 0, 137, 245 becomes 0, 137, -115, and the average
is +22, which is East of North
That just seems to move the problem point.
Take 178, 179, 181 and 182.
Becomes 178, 179, -179, -178, average is 0.
Or am I misunderstanding the algorithm?
>> are 0, 1, 359. Then a simple average is 120, but the number I'm
>> looking for is zero
>>
>
> You'll have to treat a range as negative. Look at the circle as left
> and right semi-circles
>
> For example, if the values were all between 0 and 180 then the
> result will be "positive", ie the average will be Eastward. If one is
> over 180 then that is going to skew the average Westward. And
> similarly if all the values but one were between 180 and 360
>
> Consider the way values are handled in a micro. 127 is the most
> positive, 128 is the most negative. For values that represent degrees,
> 0 is the least positive, 179 is the most positive, 180 is the most
> negative, 359 is the least negative. In this case wrt North, or 0
> degrees, which is where the circle starts and ends
>
> So, 0, 1, 359 becomes 0, 1 and -1. The -1 is derived from 359
> by (360 - value) if (value > 179) and designating it negative
>
> Example ; 0, 137, 245 becomes 0, 137, -115, and the average
> is +22, which is East of North
>
> Joe
On Tue, Mar 20, 2012 at 10:14 PM, Sean Breheny <shb7spam_OUTcornell.edu> wrote:
> You could also do your sum modulo 360: 0+1+359=360 360 mod 360=0
>
> You would divide by N (number of samples) after performing the modulo sum..
>
> Sean
>
No, modulo isn't enough. Try it on two samples: 0, 359.
On Tue, Mar 20, 2012 at 10:54 PM, Dave <@spam@microbrixKILLspamgmail.com> wrote:
> Works for 16 bit calculations, but I wanted to stay in 8 bit for speed.
> I did simplify and assume that a circle has 255 dilberts which are a bit more than a degree.
>
Actually, I'm doing this. Wikipedia says the unit is a brad, for
binary radian. I'm using 16-bit brads, so a circle is divided into
65536 divisions.
When I posed the problem, I used 360 so that the answers would have to
show modulo operations explicitly.
On Tue, Mar 20, 2012 at 9:50 PM, Dave <KILLspammicrobrixKILLspamgmail.com> wrote:
> Convert to rectangular average that and convert back to polar. Not as hard as it sounds. I did it years ago on an AVR. In asm
>
> That just seems to move the problem point.
> Take 178, 179, 181 and 182.
> Becomes 178, 179, -179, -178, average is 0.
> Or am I misunderstanding the algorithm?
>> So, 0, 1, 359 becomes 0, 1 and -1. The -1 is derived from 359
>> by (360 - value) if (value > 179) and designating it negative
No, you're quite right. With what I proposed there will be two
0 results. One will be correct (0 = 360) but the other is opposite
polarity (0 = 180)
If the original values were used - 178, 179, 181 and 182 - the
correct result of 180 would be obtained
So what step have I omitted ? Another test for overall magnitude,
something like that
On 21/3/2012 4:34 AM, Mark Rages wrote:
> Suppose I have some measurements of an angle as integer degrees in the
> range [0, 359].
>
> I would like to find an average of these measurements as an estimate
> of the true angle.
>
> A simple numerical average doesn't work: Suppose the measurements are
> 0, 1, 359. Then a simple average is 120, but the number I'm looking
> for is zero.
>
> Is there a standard algorithm to do what I want?
IMHO your angles should all be in a narrow range, otherwise averaging makes no sense.
I would do this:
- count the number of values in each quadrant.
- If there are values in all 4 quadrants, reject the measurements.
- rotate the samples such that there are no measurements in Q4 (270..359)
- average
- rotate back
> I would do this:
> - count the number of values in each quadrant.
> - If there are values in all 4 quadrants, reject the measurements.
> - rotate the samples such that there are no measurements in Q4 (270..359)
> - average
> - rotate back
Drat, that is not enough for some funny cases. The measurements must be restricted to two adjacent quadrants for this to work.
If the number is greater than 180, subtract from 360, then average. Or something starting with that. It's too early in the morning yet to follow this through. Maybe rotate180 degrees.
On 3/20/2012 11:34 PM, Mark Rages wrote:
> Suppose I have some measurements of an angle as integer degrees in the
> range [0, 359].
>
> I would like to find an average of these measurements as an estimate
> of the true angle.
>
> A simple numerical average doesn't work: Suppose the measurements are
> 0, 1, 359. Then a simple average is 120, but the number I'm looking
> for is zero.
>
> Is there a standard algorithm to do what I want?
>
> Regards,
> Mark
> markrages@gmail
>
> IMHO your angles should all be in a narrow range, otherwise averaging
> makes no sense.
That's exactly the example he gave, and exactly the problem I was solving.
I was taking readings from a Doppler DF unit at 7200 readings/sec,
which are normally relative to the vehicle, 0 degrees being "dead
ahead" so this problem is pretty common. A string of readings
dithering around 0, if averaged improperly, 1,359,1,359, gives you the
wrong answer of 180.
Converting to rectangular makes averaging dead easy, and going back to
polar is a bit less easy, requiring a square root, but it's workable.
If you consider all the incoming polar bearings to have a length of
"1", then the result after averaging has some length less than "1"
proportional to the quality of the bearing. A narrow wedge gives
values near 1, and a wide one gives rather less.
I can probably dig up the code, but I haven't looked at it since about '96-ish
For that particular project I had eight MAX3100 SPI uarts (I'd use
AVRs today) at 9600 bidirectional, plus the onboard uart at 115200,
plus the bearing math, and display all running at full speed on an 8
MHz 8515, which would be a pretty low end chip today. The SPI uarts
were multiplexed over the onboard uart, talking to and from a PC app
with a pair of virtual channels for bearing data and commands back to
the system.
Since the max theoretical resolution of such systems is about 5
degrees, using 0-255 as my "Dilberts" of angle resulted in
calculations that were adequately accurate, and keeping 8 bit math
kept things fast.
On 21-Mar-12 04:34, Mark Rages wrote:
> Suppose I have some measurements of an angle as integer degrees in the
> range [0, 359].
>
> I would like to find an average of these measurements as an estimate
> of the true angle.
>
> A simple numerical average doesn't work: Suppose the measurements are
> 0, 1, 359. Then a simple average is 120, but the number I'm looking
> for is zero.
>
> Is there a standard algorithm to do what I want?
On Wed, Mar 21, 2012 at 9:47 AM, Djula Djarmati <RemoveMEpiclistTakeThisOuTsbb.rs> wrote:
> On 21-Mar-12 04:34, Mark Rages wrote:
>> Suppose I have some measurements of an angle as integer degrees in the
>> range [0, 359].
>>
>> I would like to find an average of these measurements as an estimate
>> of the true angle.
>>
>> A simple numerical average doesn't work: Suppose the measurements are
>> 0, 1, 359. Then a simple average is 120, but the number I'm looking
>> for is zero.
>>
>> Is there a standard algorithm to do what I want?
>
> Yes, of course there is:
> http://abelian.org/vlf/bearings.html
>
> Djula
>
> -----Original Message-----
> From: spamBeGonepiclist-bouncesspamBeGonemit.edu [TakeThisOuTpiclist-bouncesEraseMEspam_OUTmit.edu] On Behalf
> Of David VanHorn
> Sent: 21 March 2012 14:34
> To: Microcontroller discussion list - Public.
> Subject: Re: [EE] Numerical averaging of angles
>
> > IMHO your angles should all be in a narrow range, otherwise averaging
> > makes no sense.
>
>
> That's exactly the example he gave, and exactly the problem I was solving..
If all your samples cover a range of less than two quadrants then I don't think there is a problem with simply averaging the angles? If the samples cross the 0/360 degree problem area then just rotate 90 degrees before averaging and then rotate back afterwards.
Admittedly this would be a little more tricky if you are averaging samples as you receive them rather than from a buffer, but I think it could still be done e.g. by checking the quadrant each value lies within as it's received. As long as you remain within one quadrant then simply accumulate the samples. If you receive a sample in another quadrant, then check if the two quadrants are the problematic ones - if so then offset your accumulated value by (90*nsamples) and set a flag to ensure further samples received are also offset. If you detect samples in a third quadrant then it's probably time to give up and flag an error.
After all samples are processed divide the accumulated values by the number of samples and check the flag to see if the average needs rotating back by 90 degrees.
This seems to work in my head and in a quick test in Excel, what did I miss?
Mike
=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================
>On Wed, Mar 21, 2012 at 9:47 AM, Djula Djarmati <piclistEraseME.....sbb.rs> wrote:
>> On 21-Mar-12 04:34, Mark Rages wrote:
>>> Suppose I have some measurements of an angle as integer degrees in the
>>> range [0, 359].
>>>
>>> I would like to find an average of these measurements as an estimate
>>> of the true angle.
>>>
>>> A simple numerical average doesn't work: Â Suppose the measurements are
>>> 0, 1, 359. Â Then a simple average is 120, but the number I'm looking
>>> for is zero.
>>>
>>> Is there a standard algorithm to do what I want?
>>
>> Yes, of course there is:
>> http://abelian.org/vlf/bearings.html
>>
>> Djula
>>
>
>Bingo!
>
>Thanks much Djula.
>
>Regards,
>Mark
>markrages@gmail
>
> If all your samples cover a range of less than two quadrants then I don't think there is a problem with simply averaging the angles? If the samples cross the 0/360 degree problem area then just rotate 90 degrees before averaging and then rotate back afterwards.
I don't know what his app is, but in mine there was NO way I could
guarantee that.
It's very common to have wild bearings even 180 degrees out in a
doppler DF system. Reflections and RF paths vary widely especially
when mobile, and perversely you usually get better overall bearing
quality when moving.
If it works for him, it works.. It wouldn't have worked for me. I
chewed on that one for a while before deciding to bite the bullet and
do it the formal way.
> On Tue, Mar 20, 2012 at 10:14 PM, Sean Breheny <RemoveMEshb7EraseMEEraseMEcornell.edu> wrote:
>> You could also do your sum modulo 360: 0+1+359=360 360 mod 360=0
>>
>> You would divide by N (number of samples) after performing the modulo sum.
>>
>> Sean
>>
>
> No, modulo isn't enough. Try it on two samples: 0, 359.
>
> --
> Regards,
> Mark
> markrages@gmail
>
gmail.com> wrote:
