![](templates/subSilver/images/CCSLogo.jpg) |
![CCS C Software and Maintenance Offers](templates/subSilver/images/forumAd6.jpg) |
View previous topic :: View next topic |
Author |
Message |
avatarengineer
Joined: 13 May 2013 Posts: 51 Location: Arizona
|
Qsort alternative |
Posted: Mon Feb 29, 2016 3:19 pm |
|
|
I often need to sort analog samplings for use in a median filter.
The "qsort" command has me worried,
I'm not fond of pointers and I rarely need to sort characters.
The following code snippet is what I like to use for sorting a stream
of data from the ADC (usually 10bits types or more).
A further routine (not shown) takes the inner 3 or more values and gets an average (mean).
This eliminates hi and lo values that might be considered noise.
Doing this on each analog sample, loading the array and shifting out
the oldest value allows a rolling mean to be calculated.
Often used is a "bubblesort", however that seems much slower than
the "Shell-Metzner" method (as used by the CCS qsort).
Any comments from the forum? let me know if I'm smokin' dope.
Code: |
// in the header
#DEFINE sortsize 10
int16 sortarray[sortsize];
typedef int16 sorttype; // allows simple change of type for different array types
// called routine
void shellsort() {
int8 i,j,k,m;
int1 done;
sorttype x;
j=sortsize/2;
while( j > 0 ) {
for(i=0; i<(sortsize-j); ++i) {
k=i;
do {
done=1;
m=j+k;
if (sortarray[i]>sortarray[m]) {
x=sortarray[i];
sortarray[i]=sortarray[m];
sortarray[m]=x;
if(j <= k) { k -= j; done = 0; }
}
} while(!done);
}
j/=2;
}
}
|
![Rolling Eyes](images/smiles/icon_rolleyes.gif) |
|
![](templates/subSilver/images/spacer.gif) |
Ttelmah
Joined: 11 Mar 2010 Posts: 19369
|
|
Posted: Mon Feb 29, 2016 3:24 pm |
|
|
There is a fundamental flaw in what you are doing. With an array size of 10, you have the three values you take, plus an _odd_ number of other values. Your array size must be _odd_ for the central value, and the value each side, to be used for a median filter....
Have you searched the forum?. PCM_programmer, many years ago, posted a generic median filter (based on taking the central value from a sorted array), that would be quite easy to modify to use three values. |
|
![](templates/subSilver/images/spacer.gif) |
jeremiah
Joined: 20 Jul 2010 Posts: 1328
|
|
Posted: Mon Feb 29, 2016 4:17 pm |
|
|
Just for portability OCD I would change:
Code: |
int16 sortarray[sortsize];
typedef int16 sorttype; // allows simple change of type for different array types
|
to
Code: |
typedef int16 sorttype; // allows simple change of type for different array types
sorttype sortarray[sortsize];
|
Also note that your method still relies on pointers (arrays are pointers as implemented in C), so keep that in mind if you are concerned about them.
As far as the sorting algorithms go, I prefer an insertion sort algorithm for ADC values because you can use the time between ADC readings to do the data moving instead of trying to do all of it at the end. As long as the data sets are not huge, it is really efficient. That said, you should also consider choosing a sorting algorithm based on how the data statistically trends if you can take the time to sample and record lots of data. |
|
![](templates/subSilver/images/spacer.gif) |
temtronic
Joined: 01 Jul 2010 Posts: 9174 Location: Greensville,Ontario
|
|
Posted: Mon Feb 29, 2016 4:36 pm |
|
|
Also consider the source. Getting reliable, consistant, accurate 10,12 16 bit data from an analog source needs a LOT of careful design/build techniques.
No 'fancy' algorithm can compensate for faulty data. Simple test, read and display the data over several hours. If the sensor source is stable the displayed data should be +-1 bit. If not, you'll have to track down the interference and eliminate it.
Jay |
|
![](templates/subSilver/images/spacer.gif) |
PCM programmer
Joined: 06 Sep 2003 Posts: 21708
|
|
![](templates/subSilver/images/spacer.gif) |
avatarengineer
Joined: 13 May 2013 Posts: 51 Location: Arizona
|
Median filtering and Qsort alternate |
Posted: Tue Mar 01, 2016 2:32 pm |
|
|
@Ttelmah; Using odd or even array size is not a requirement for median filtering, just an old convention as to my understanding.
Whether average values are centered in an array is not germane once it's sorted as the point in time is lost and overall delay is constant regardless of offset. Typically, I'll have an array of 100 items and track the average of only a few centered with an offset that is biased for fewer or larger outliers at the high or low side depending on the trajectory.
Otherwise, I was looking for help on the code.
This is a new routine (with minimal pointers) I just tried
and with any array size 9, 11, 23, 45... I require to run this twice before a full sort occurs.
Something in the While loops is not right and I've become blind to it.
![Confused](images/smiles/icon_confused.gif) |
|
![](templates/subSilver/images/spacer.gif) |
avatarengineer
Joined: 13 May 2013 Posts: 51 Location: Arizona
|
FYI |
Posted: Tue Mar 01, 2016 2:37 pm |
|
|
The actual version is 32bit signed values for use with a LTC ADC 29bits.
But keep to the simple version for conversation.
...and OCD is OK. |
|
![](templates/subSilver/images/spacer.gif) |
PCM programmer
Joined: 06 Sep 2003 Posts: 21708
|
|
Posted: Tue Mar 01, 2016 6:24 pm |
|
|
Quote: | Otherwise, I was looking for help on the code. |
I assume you mean the Shell sort code in your first post. Why not use
Shell sort routines available on the internet ? Instead of writing your own. |
|
![](templates/subSilver/images/spacer.gif) |
Ttelmah
Joined: 11 Mar 2010 Posts: 19369
|
Re: Median filtering and Qsort alternate |
Posted: Wed Mar 02, 2016 2:08 am |
|
|
avatarengineer wrote: | @Ttelmah; Using odd or even array size is not a requirement for median filtering, just an old convention as to my understanding.
Whether average values are centered in an array is not germane once it's sorted as the point in time is lost and overall delay is constant regardless of offset. Typically, I'll have an array of 100 items and track the average of only a few centered with an offset that is biased for fewer or larger outliers at the high or low side depending on the trajectory.
Otherwise, I was looking for help on the code.
This is a new routine (with minimal pointers) I just tried
and with any array size 9, 11, 23, 45... I require to run this twice before a full sort occurs.
Something in the While loops is not right and I've become blind to it.
![Confused](images/smiles/icon_confused.gif) |
The size of the array, changes 'where' the median actually is.
If you have an even sized array, then the median will actually be half way between the centre two numbers. So you could work by taking these and just averaging these two values.
However you talked about taking a three number average, and show a ten number array. Problem is that there isn't a 'centre three' set of numbers in a ten number array. Think about it:
0
1
2
3
4
5
6
7
8
9
If you pick 3,4,5 you have three elements above, and four below. If you pick 4,5,6, you have four above and three below.
The 'rule' is that on a sorted array with an odd number of elements, you can use the central element, or an average of the central three, five, seven etc., elements. For a similar array with an even number of elements, you need to use the central 2, 4, 6, 8 etc. elements.
As a further comment, why sort?.
Ignore the median filter, and use the Olympic average instead.
For a 12bit ADC.
Start with three values. Max=0, Min=4096, sum=0.
Read a number of samples.
For each reading, if val>Max then Max=val
If val<Min then Min=val
sum+=val
Then sum-=Min
sum-=Max
avg=sum/(num_samples-2)
This gives you the average of the samples taken, _ignoring the maximum and minimum readings_.
Quick to calculate - just two comparisons and one addition for each sample. Choose a number of samples like 6, and the final division will be binary (/4).
Quick, rejects 'spike' noise well, and is small/simple to code.
This is what is used for the judges scores in things like Olympic ski-jumping, to prevent any single 'ill-informed', or 'biased' judge from being able to significantly influence the result. |
|
![](templates/subSilver/images/spacer.gif) |
RF_Developer
Joined: 07 Feb 2011 Posts: 839
|
|
Posted: Wed Mar 02, 2016 3:38 am |
|
|
I think that to a great extent this is a case of making a mountain out of a molehill. Sorting ten integers is, in computing terms, regarded as a trivial case. There's not a lot of point worrying much, if at all, about efficiency and speed of processing. The overhead involved with more complex, but algorithmically more efficient searches can easily be greater than any gains.
The more complex methods begin to give real gains only with significantly more data points, and more complex data such as records rather than single, simple data points. Imagine the work required to sort a telephone directory, which has telephone number, name and address, by number rather than by name.
Pointers are a very effective programming technique, and make complex data structures, and easily traversilble and sortable structures, possible. There's nothing inherently wrong or frightening about them. But in C especially, they do need careful progamming and testing. Such care and careful testing should, of course, be done for all programming tasks.
The use of pointers for sortable lists really scores when the pointer is significantly smaller and easier to manipulate than the data itself. Simple int8 data is smaller and simpler to move around that those pesky pointers, so making pointer-based data structures of int8s inefficient: its far easier and quicker to move the data than to change the pointers. Think, though, about that telephone book data. There's much more data in a record - number, maybe ten or more digits, name, could be twenty or more characters, address, say another forty - than a single sixteen or thirty two bit pointer. So for telephone data sorting, pointers are a no brainer.
Pointer based sorts are also good for data you already have in a data structure. If you are collecting data sample by sample as you go along, as with an ADC, a simple linear buffer is often all you need, and anything more is overkill and more importantly, overhead.
I do some so-called "olympic" averaging on some ADC data. It's not especially good with pure randomly noisy data, but it is very good with data corrupted by spikes, such as ADC readings of voltages from a SMPS. For that I take 2n + 2 samples, e.g. 10, 18, etc. - a straight binary multiple of samples is actually more awkward - adding them and recording the highest and lowest as I sample. When I have the required number of samples I subtract the lowest and highest and divide by 2n, which is a simple divide by a binary multiple, or for integers, a shift which the CCS compiler optimises for you. On PICs it would work for many more samples, even with 12 bit ADC data, which I often use; accumulating the sum in an unsigned int16. I only convert to engineering units, which may involve float arithmethic, but I'll do in integers if I can, once I have a value I need to save or present to a user. Even then I'll nearly alwas store that internally in integer form, for example voltages in millivolts or tens of millvolts.
EDIT: Sorry, I see that Ttelmah is proposing the same form of processing. I just described it in words. |
|
![](templates/subSilver/images/spacer.gif) |
Ttelmah
Joined: 11 Mar 2010 Posts: 19369
|
|
Posted: Wed Mar 02, 2016 4:00 am |
|
|
Yes, and we both get to the same final conclusion:
"Quick, rejects 'spike' noise well, and is small/simple to code."
It is a very good approach for anything involving spike noise.
It also though illustrates the importance of 'know your noise'.
Choosing the wrong filter can/will involve unnecessary processing, and may gain you nothing. For instance, if the noise is synchronous to your sampling, or involves longer bursts, 'things change'. |
|
![](templates/subSilver/images/spacer.gif) |
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|