Re: How to Determine Stable Y-Values... or Detect an Edge..?

You can apply a low-pass filter to the data first, in order to remove the "noise".

Probably, there is already some module on CPAN that does it (look for Fourier transform or series). Otherwise, programming it from scratch should not be too difficult once you understand the maths behind ;-)

Once you have your data cleaned, looking for stability intervals would just be a matter of defining how to measure stability. For instance, you can set a maximum Y delta and search for intervals where delta_X > min_delta_X and delta_Y < max_delta_Y

In any case, make your data samples available to us so we can also play with them!

Comment on Re: How to Determine Stable Y-Values... or Detect an Edge..?

Replies are listed 'Best First'.
Re^2: How to Determine Stable Y-Values... or Detect an Edge..? by tilly (Archbishop) on Aug 19, 2009 at 16:23 UTC
I like the idea of a low pass filter, though that is not sufficient to solve this problem. But with a data set of this kind, a Fourier transform is a particularly poor choice. The reason is that the Fourier transform tries to approximate the data as a set of sine waves. Therefore if you have a jump anywhere in the data, then applying a Fourier transform, removing high order terms, and transforming back will leave you with severe visible "ringing" over the whole data set, which will obscure what he's looking for. That's why I naturally jumped to wavelets, which localize the higher order terms so that removing noise in one part of the picture doesn't create it elsewhere. They do that by combining low-pass and high-pass filters to separate data into localized high frequency pieces, and spread out low frequency pieces. The easiest kind of wavelet to use is the Haar wavelet, which is likely also most appropriate for this case. The Haar wavelet is just a bunch of square waves. If the number of points is a power of 2, then you'd calculate the Haar wavelet as follows. Take each pair of points. Calculate their average and their difference from the average. The differences are the highest frequency wavelets, so save them. You have half as many averages as you have points. Repeat the calculation on the averages to get the next smaller wavelets. Then the next smaller wavelets, etc. Finally you'll be left with an overall average. This procedure works, and will work well with data sets with large piecewise horizontal chunks. However as described it will not find boundaries well that are not conveniently on a power of 2. Nor will it work well if the width of the images is not a power of 2. Wavelet packet algorithms generalize this procedure by dynamically altering the details of wavelet shape to come up with a solution that optimizes some global goal. For instance you could vary the boundary of the square waves to concentrate as much energy as possible into the smallest number of waves possible. If you do that then the boundaries of the largest few wavelets will naturally fall on the intervals that they're trying to find, and the intervals will be recognizable by the interior pieces being very small. I remember that much of what they do, but I don't remember how to dynamically calculate wavelet packets. :-(	[reply]

Replies are listed 'Best First'.

Re^2: How to Determine Stable Y-Values... or Detect an Edge..?
by tilly (Archbishop) on Aug 19, 2009 at 16:23 UTC

That's why I naturally jumped to wavelets, which localize the higher order terms so that removing noise in one part of the picture doesn't create it elsewhere. They do that by combining low-pass and high-pass filters to separate data into localized high frequency pieces, and spread out low frequency pieces.

The easiest kind of wavelet to use is the Haar wavelet, which is likely also most appropriate for this case. The Haar wavelet is just a bunch of square waves. If the number of points is a power of 2, then you'd calculate the Haar wavelet as follows. Take each pair of points. Calculate their average and their difference from the average. The differences are the highest frequency wavelets, so save them. You have half as many averages as you have points. Repeat the calculation on the averages to get the next smaller wavelets. Then the next smaller wavelets, etc. Finally you'll be left with an overall average.

This procedure works, and will work well with data sets with large piecewise horizontal chunks. However as described it will not find boundaries well that are not conveniently on a power of 2. Nor will it work well if the width of the images is not a power of 2.

Wavelet packet algorithms generalize this procedure by dynamically altering the details of wavelet shape to come up with a solution that optimizes some global goal. For instance you could vary the boundary of the square waves to concentrate as much energy as possible into the smallest number of waves possible. If you do that then the boundaries of the largest few wavelets will naturally fall on the intervals that they're trying to find, and the intervals will be recognizable by the interior pieces being very small.

I remember that much of what they do, but I don't remember how to dynamically calculate wavelet packets. :-(

[reply]