Post by thread:[EE] Numerical averaging of angles

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 >

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 On Tue, Mar 20, 2012 at 11:50 PM, Dave <microbrixKILLspamgmail.com> wrote: {Quote hidden}> 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). I haven't tested it exhaustively though. Cheers, -Neil. On 3/20/2012 10:34 PM, Mark Rages wrote: {Quote hidden}> 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

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. Kerry Mark Rages wrote: {Quote hidden}> 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: {Quote hidden}>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 Jo

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? Kerry IVP wrote: {Quote hidden}>> 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: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. -- Regards, Mark markrages@gmai

> 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 -- Wouter van Ooijen -- ------------------------------------------- Van Ooijen Technische Informatica: http://www.voti.nl consultancy, development, PICmicro products docent Hogeschool van Utrecht: http://www.voti.nl/hvu C++ on uC blog: http://www.voti.nl/erblog

> 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. -- Wouter van Ooijen -- ------------------------------------------- Van Ooijen Technische Informatica: http://www.voti.nl consultancy, development, PICmicro products docent Hogeschool van Utrecht: http://www.voti.nl/hvu C++ on uC blog: http://www.voti.nl/erblog

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. http://www.teacherschoice.com.au/maths_library/coordinates/polar_-_rectangular_conversion.htm 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. It's all about the art of compromise. :

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 > > Regards, > Mark > markrages@gmai

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 > Bingo! Thanks much Djula. Regards, Mark markrages@gmail

> -----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. =======================================================================

Note the conditions where it breaks down. Pretty common in the application I was working on. YMMV Mark Rages <RemoveMEmarkragesTakeThisOuTgmail.com> wrote: {Quote hidden}>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.

Sorry, you're correct. Some others here have suggested variants of this which work for restricted ranges of angles. On Wed, Mar 21, 2012 at 1:59 AM, Mark Rages <EraseMEmarkragesgmail.com> wrote: {Quote hidden}> 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 > >