Forums

algorithms for location versus for frequency?

Started by Ron N. February 27, 2006
Jerry Avins wrote:
> Ron N. wrote: > > Jerry Avins wrote: > >>I don't know about best, but time measurements are good. You might even > >>count zero crossings. That will establish the duration within a cycle. > > > > I assume you meant to say measure zero crossings, not just to > > count them. But I suppose one could count the zero crossings, > > and assume that when the number becomes very different from two > > per period that the signal has disappeared, and any zero crossings > > remaining are likely from noise or interference. This method > > seems very different from trying to estimate the amplitude > > and/or threshold of a filtered waveform. I'll give it a try. > > No, I meant count. After the signal is filtered well enough so that an > octave above it is well attenuated and there's not much noise below it, > there'll be only one zero crossing per cycle. The signal being buried in > noise means it's hard to know that it's there. If you can't tell with > reasonable certainty whether it's there or not, deciding when it starts > and stops is a fool's errand.
This sounds circular. One has to know when a signals ends before one knows that isn't there. If a circuit keeps counting zero crossings too long, it may start counting small zero crossings due to random noise after the signals trailing edge. How to know if one has gotten past the trailing edge so that one knows one should stop counting puts us back to the original question of how to estimate a signals time envelope position and duration. I was thinking of looking at the spacing of the zero crossings to help validate that they weren't just due to any noise that might have leaked past the filter either before or after the signal of interest. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Ron N. wrote:
> Jerry Avins wrote: > >>Ron N. wrote: >> >>>Jerry Avins wrote: >>> >>>>I don't know about best, but time measurements are good. You might even >>>>count zero crossings. That will establish the duration within a cycle. >>> >>>I assume you meant to say measure zero crossings, not just to >>>count them. But I suppose one could count the zero crossings, >>>and assume that when the number becomes very different from two >>>per period that the signal has disappeared, and any zero crossings >>>remaining are likely from noise or interference. This method >>>seems very different from trying to estimate the amplitude >>>and/or threshold of a filtered waveform. I'll give it a try. >> >>No, I meant count. After the signal is filtered well enough so that an >>octave above it is well attenuated and there's not much noise below it, >>there'll be only one zero crossing per cycle. The signal being buried in >>noise means it's hard to know that it's there. If you can't tell with >>reasonable certainty whether it's there or not, deciding when it starts >>and stops is a fool's errand. > > > This sounds circular. One has to know when a signals ends > before one knows that isn't there. If a circuit keeps counting > zero crossings too long, it may start counting small zero crossings > due to random noise after the signals trailing edge. How to know > if one has gotten past the trailing edge so that one knows one > should stop counting puts us back to the original question of > how to estimate a signals time envelope position and duration. > > I was thinking of looking at the spacing of the zero crossings to > help validate that they weren't just due to any noise that might > have leaked past the filter either before or after the signal of > interest.
You can discriminate between a substantial signal and background noise with appropriate hysteresis. The bandpass filter ahead of the zero-crossing comparator with hysteresis ought to provide that substantial signal. Use an FFT to determine the filters location if you will. The whole operation can be done in the computer with two passes over the file that is the recording of the unfiltered waveform. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Thomas Magma wrote:
> > A filter does not produce time information. It produces yet another > > waveform with somewhat less interference. So even if I use a filter > > (which I am) I am still left with the original problem. How does one > > extract the signal envelope duration with accuracy? > > Like it has already been suggested to you, I think a sliding Goertzel would > be a good way to start. Sure a sliding window will always have a low pass > response, but the rise and fall time of this type of algorithm remains > constant, resulting in a fairly accurate measure of your "signal envelope" > duration.
A sliding Goertzel algorithm would still produce a low-pass response waveform with known rise and fall times (sliding window width plus the signal rise time), not a duration. That still leaves the problem of finding an accurately fixed point in time (either the center or the start) on each of the rising or falling portions of the low-pass amplitude envelope from the sliding Goertzel results. Perhaps running linear regressions for the length of the expected rise time, and then picking the start point of the fixed-length line with the maximum slope? Or perhaps looking for bi-modal humps in the amplitude envelope distribution statistics, and then using a threshold halfway in between the centroids of the two modal humps with a percentage of hysteresis? The FFT bin amplitude doesn't help too much for setting a threshold unless one knows the duty cycle of the signal in the FFT window, which requires knowing the duration of the signal(s), which happens to be the unknown in my problem statements. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Ron N. wrote:
> Rune Allnor wrote: > > If you are really interested in this sort of stuff, try van Trees' > > "detection Estimation and Modulation Theory", vols 1-4. > > This is exactly the type of thing I've noted before, mentioning > books instead of algorithms. In comp.dsp, the ratio of discussing > algorithms versus books is far higher for questions about frequency > measurement. Why this difference? Is frequency measurement > somehow easier to explain?
Yes. With frequency estimation, there are fewer algorithms and methods to deal with, and the principles are basic and easy to explain. In time domain, all sorts of peculiarities and idiosyncraticies of measurement, equipment and purpose come into play.
> > > For instance, what means could be used to measure the precise > > > duration (within rise time uncertainty) of a DTMF tone, Morse > > > code dit, or saxaphone note from a buffer of sound samples? > > > > For the first two cases, a naive attempt would be to design > > some filter that is centered around the transmitted frequencies > > of the various tones, and use some sort of energy detector > > at the output. > > This solution seems to produce far less resolution and more > error than frequency measurements of the same signals by > methods which have been extensively discussed in the group. > What do the non-naive attempts look like?
I don't know. The question that must be answered prior to this, is "what resolution is *needed*?" Only then can one start criticising the different methods. One usually choose the cheapest/simplest method that solves the problem to within spec.
> > The latter case is a completely different problem. Does the > > signal contain sound only from the saxophone, or are other > > instruments involved? If there is only one instrument available, > > do you need to determine if it is a saxophone or, say, a trumpet > > or a clarinet? > > That is a different question. My question is more about if one did > already have some means (say a priori information) to detect that > there was some saxophone note present, sufficient to measure the > note's frequency content in the signal, how would the methods > for an accurate measurement of the notes duration differ from > those for the measurement of its frequency.
The time duration ought to be measured in time domain, and frequency in frequency domain. Rune
">> Like it has already been suggested to you, I think a sliding Goertzel 
would
>> be a good way to start. Sure a sliding window will always have a low pass >> response, but the rise and fall time of this type of algorithm remains >> constant, resulting in a fairly accurate measure of your "signal >> envelope" >> duration. > > A sliding Goertzel algorithm would still produce a low-pass > response waveform with known rise and fall times (sliding > window width plus the signal rise time), not a duration. That > still leaves the problem of finding an accurately fixed point > in time (either the center or the start) on each of the rising > or falling portions of the low-pass amplitude envelope from the > sliding Goertzel results. Perhaps running linear regressions > for the length of the expected rise time, and then picking the > start point of the fixed-length line with the maximum slope? > Or perhaps looking for bi-modal humps in the amplitude > envelope distribution statistics, and then using a threshold > halfway in between the centroids of the two modal humps with > a percentage of hysteresis? > > The FFT bin amplitude doesn't help too much for setting a > threshold unless one knows the duty cycle of the signal in the > FFT window, which requires knowing the duration of the signal(s), > which happens to be the unknown in my problem statements. > > > IMHO. YMMV. > -- > rhn A.T nicholson d.0.t C-o-M >
Hi Ron, Is this just a thought experiment or is this a real problem your trying to solve? If it is the latter, could you say what this signal is composed of and what resolution and accuracies you are trying to achieve. Thomas
Thomas Magma wrote:
> ">> Like it has already been suggested to you, I think a sliding Goertzel > would > >> be a good way to start. Sure a sliding window will always have a low pass > >> response, but the rise and fall time of this type of algorithm remains > >> constant, resulting in a fairly accurate measure of your "signal > >> envelope" > >> duration. > > > > A sliding Goertzel algorithm would still produce a low-pass > > response waveform with known rise and fall times (sliding > > window width plus the signal rise time), not a duration. That > > still leaves the problem of finding an accurately fixed point > > in time (either the center or the start) on each of the rising > > or falling portions of the low-pass amplitude envelope from the > > sliding Goertzel results. Perhaps running linear regressions > > for the length of the expected rise time, and then picking the > > start point of the fixed-length line with the maximum slope? > > Or perhaps looking for bi-modal humps in the amplitude > > envelope distribution statistics, and then using a threshold > > halfway in between the centroids of the two modal humps with > > a percentage of hysteresis? > > > > The FFT bin amplitude doesn't help too much for setting a > > threshold unless one knows the duty cycle of the signal in the > > FFT window, which requires knowing the duration of the signal(s), > > which happens to be the unknown in my problem statements. > > > > > > IMHO. YMMV. > > -- > > rhn A.T nicholson d.0.t C-o-M > > > > Hi Ron, > > Is this just a thought experiment or is this a real problem your trying to > solve? If it is the latter, could you say what this signal is composed of > and what resolution and accuracies you are trying to achieve. > > Thomas
It's a thought experiment. But like many thought experiments, it has a basis in some problems to which I wish I had a solution many years ago. The first problem was when I was using a hand key in amateur radio. I was wondering how to collect statistics on the quality of my keying (easy), and the keying of my on-the-air contacts. IIRC, 1% accuracy requires measuring a dit time to within 1 cycle at some realistic WPM and BFO frequency. I actually ran a switched capacitor audio filter into a level detector (diode, cap, comparitor); but the narrow band filter had such slow rise times, and the correct thresholds were so variable (I had AGC before the audio filter, not after, which was part of the problem), that it seemed like I was getting more like 50% errors in the duration measurements. Second problem was a friend who was learning to play the flute, but had rhythm problems. I was wondering if there was some way to determine, via digitized audio, how far away from some reference beat she was starting each note... maybe to show some indicator of whether she was early, late, held C# notes too long, etc. 'course, this was back in the days when hobby computers ran maybe 5 kiloflops, with MACs not much faster. Nowadays, you can get megaflops and even more MACs out of user written software running on your cellphone, so I thought I revisit this class of time domain problems. The third problem is from this newsgroup. How to validate whether a DTMF signal is within time spec, accurately. IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
A bit more Google-driven literature research has turned up several
papers on FFT algorithms called "time frequency reassignment" for
estimation of not only frequency, but also location of a frequency
burst
within an STFT window (ref: Auger & Flandrin, 1995 IEEE paper) .

Has anyone tried these methods?

Thanks.

Ron N. wrote:
> I suppose all characterization of signals inside some buffer > of samples is a form of statistical signal processing. > > When asking about the frequency of some signal in comp.dsp, > all sorts of algorithms are mentioned, forms of autocorrelation > (or squared difference, etc.), or fft/dft usage (windowed, zero > padded, phase differentiated, etc.). Also, there seem to be lots > of textbooks on these forms of analysis in the local libraries. > Very little mention of statistical techniques from old radar/sonar > textbooks. > > However when asking about how to find the location of a signal > (start/stop/center position), I often get pointers to some signal > processing textbooks (of which I haven't found any in the local > library yet). > > Why this difference? Is location analysis less tractable, less > interesting, or less explainable in comp.dsp algorithms, than > is frequency? > > For instance, what means could be used to measure the precise > duration (within rise time uncertainty) of a DTMF tone, Morse > code dit, or saxaphone note from a buffer of sound samples?
IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M