Thread Subject: How to detect turning points in curves...

How to detect turning points in curves

Hi all,

If you take a look at the following plot,

http://img63.imageshack.us/img63/5050/gggyt1.jpg

You will agree with me that there are two turning points.

But is there a systematic way to let computer detect the turning points
automatically and programmatically?

Please be advised that the second turn isn't neccessarily turning down, it
can also possibly go up...

And in real-world applications, the turn can be more smooth and round, but
still, naked eyes should be able to find the turning points easily.

My program has to do a classification:

All the good curves should first go down, and then either make no turns; or
make a turn, and stay vertically flat and slightly up, going from the left
to the right.

There should be no second turn (up or down). If there is the second turn,
then that's the bad curves.

My program needs to decern the good curves from bad curves.

I cranked a few algorithms but they don't work well. Are there systematic
methods of handling this?

Thanks a lot!

Linus Utopia:
<SNIP direction of turning of subsequent vecs...

a hint:

     help cross;

us

Hi all,

Please be advised that my curves are not continuous -- they are discrete
data points. When I plotted them in Matlab, they are connected and looked
like a continous curve. So I am not sure if the second "finite difference"
will help..., and accurately...

> How to detect turning points in curves
>
> Hi all,
>
> If you take a look at the following plot,
>
> http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> You will agree with me that there are two turning points.
>
> But is there a systematic way to let computer detect the turning points
> automatically and programmatically?
>
> Please be advised that the second turn isn't neccessarily turning down, it
> can also possibly go up...
>
> And in real-world applications, the turn can be more smooth and round, but
> still, naked eyes should be able to find the turning points easily.
>
> My program has to do a classification:
>
> All the good curves should first go down, and then either make no turns;
> or make a turn, and stay vertically flat and slightly up, going from the
> left to the right.
>
> There should be no second turn (up or down). If there is the second turn,
> then that's the bad curves.
>
> My program needs to decern the good curves from bad curves.
>
> I cranked a few algorithms but they don't work well. Are there systematic
> methods of handling this?
>
> Thanks a lot!
>
>
>
>
>
>

On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> How to detect turning points in curves
>
> Hi all,
>
> If you take a look at the following plot,
>
> http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> You will agree with me that there are two turning points.
>
> But is there a systematic way to let computer detect the turning points
> automatically and programmatically?
>
> Please be advised that the second turn isn't neccessarily turning down, it
> can also possibly go up...
>
> And in real-world applications, the turn can be more smooth and round, but
> still, naked eyes should be able to find the turning points easily.
>
> My program has to do a classification:
>
> All the good curves should first go down, and then either make no turns; or
> make a turn, and stay vertically flat and slightly up, going from the left
> to the right.
>
> There should be no second turn (up or down). If there is the second turn,
> then that's the bad curves.
>
> My program needs to decern the good curves from bad curves.
>
> I cranked a few algorithms but they don't work well. Are there systematic
> methods of handling this?
>
> Thanks a lot!

My browser wouldn't show your image, but here's a
thought. If your points are sampled at equal intervals,
you can do a Fourier transform, use the analytic expression
of the derivative term by term and the Fourier coefficients
to calculate the derivative of the Fourier representation
of your "function", and find the zeros of the derivative
and take those as the turning points. FWIW.

<AWinestein@gmail.com> wrote in message
news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
> On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>> How to detect turning points in curves
>>
>> Hi all,
>>
>> If you take a look at the following plot,
>>
>> http://img63.imageshack.us/img63/5050/gggyt1.jpg
>>
>> You will agree with me that there are two turning points.
>>
>> But is there a systematic way to let computer detect the turning points
>> automatically and programmatically?
>>
>> Please be advised that the second turn isn't neccessarily turning down,
>> it
>> can also possibly go up...
>>
>> And in real-world applications, the turn can be more smooth and round,
>> but
>> still, naked eyes should be able to find the turning points easily.
>>
>> My program has to do a classification:
>>
>> All the good curves should first go down, and then either make no turns;
>> or
>> make a turn, and stay vertically flat and slightly up, going from the
>> left
>> to the right.
>>
>> There should be no second turn (up or down). If there is the second turn,
>> then that's the bad curves.
>>
>> My program needs to decern the good curves from bad curves.
>>
>> I cranked a few algorithms but they don't work well. Are there systematic
>> methods of handling this?
>>
>> Thanks a lot!
>
> My browser wouldn't show your image, but here's a
> thought. If your points are sampled at equal intervals,
> you can do a Fourier transform, use the analytic expression
> of the derivative term by term and the Fourier coefficients
> to calculate the derivative of the Fourier representation
> of your "function", and find the zeros of the derivative
> and take those as the turning points. FWIW.
>

How? Could you please elaborate?

In article <f76ko9$ilr$1@news.Stanford.EDU>,
 "Linus Utopia" <linus_utopia@gmail.com> wrote:

> Hi all,
>
> Please be advised that my curves are not continuous -- they are discrete
> data points. When I plotted them in Matlab, they are connected and looked
> like a continous curve. So I am not sure if the second "finite difference"
> will help..., and accurately...
>

My first thought would be to polynomial interpolation of 3-5 points at a
time, then use the second derivative of that polynomial.

I can't say anything about how efficient that would be, or how accurate,
though.

Peter Claussen


> > How to detect turning points in curves
> >
> > Hi all,
> >
> > If you take a look at the following plot,
> >
> > http://img63.imageshack.us/img63/5050/gggyt1.jpg
> >
> > You will agree with me that there are two turning points.
> >
> > But is there a systematic way to let computer detect the turning points
> > automatically and programmatically?
> >
> > Please be advised that the second turn isn't neccessarily turning down, it
> > can also possibly go up...
> >
> > And in real-world applications, the turn can be more smooth and round, but
> > still, naked eyes should be able to find the turning points easily.
> >
> > My program has to do a classification:
> >
> > All the good curves should first go down, and then either make no turns;
> > or make a turn, and stay vertically flat and slightly up, going from the
> > left to the right.
> >
> > There should be no second turn (up or down). If there is the second turn,
> > then that's the bad curves.
> >
> > My program needs to decern the good curves from bad curves.
> >
> > I cranked a few algorithms but they don't work well. Are there systematic
> > methods of handling this?
> >
> > Thanks a lot!
> >
> >
> >
> >
> >
> >

"us" <us@neurol.unizh.ch> wrote in message
news:ef5d53f.0@webcrossing.raydaftYaTP...
> Linus Utopia:
> <SNIP direction of turning of subsequent vecs...
>
> a hint:
>
> help cross;
>
> us

I admit -- I was unable to figure out how will "cross" help me? Are you
suggesting a hack?

On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> <AWinest...@gmail.com> wrote in message
>
> news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>
>
>
>
>
> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> >> How to detect turning points in curves
>
> >> Hi all,
>
> >> If you take a look at the following plot,
>
> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> >> You will agree with me that there are two turning points.
>
> >> But is there a systematic way to let computer detect the turning points
> >> automatically and programmatically?
>
> >> Please be advised that the second turn isn't neccessarily turning down,
> >> it
> >> can also possibly go up...
>
> >> And in real-world applications, the turn can be more smooth and round,
> >> but
> >> still, naked eyes should be able to find the turning points easily.
>
> >> My program has to do a classification:
>
> >> All the good curves should first go down, and then either make no turns;
> >> or
> >> make a turn, and stay vertically flat and slightly up, going from the
> >> left
> >> to the right.
>
> >> There should be no second turn (up or down). If there is the second turn,
> >> then that's the bad curves.
>
> >> My program needs to decern the good curves from bad curves.
>
> >> I cranked a few algorithms but they don't work well. Are there systematic
> >> methods of handling this?
>
> >> Thanks a lot!
>
> > My browser wouldn't show your image, but here's a
> > thought. If your points are sampled at equal intervals,
> > you can do a Fourier transform, use the analytic expression
> > of the derivative term by term and the Fourier coefficients
> > to calculate the derivative of the Fourier representation
> > of your "function", and find the zeros of the derivative
> > and take those as the turning points. FWIW.
>
> How? Could you please elaborate?- Hide quoted text -
>
> - Show quoted text -

This is a brief summary. Hopefully it doesn't insult your
intelligence and isn't too sketchy.

Under certain conditions on F,
F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
            b1 sin(kx) + b2 sin(2kx) + ...
Using a discrete Fourier Transform (preferably using the Fast
Fourier Transform algorithm if you have very many data points),
you can calculate a discrete set of a's and b's the cause F to
agree with your function at the x values for which you have F
values. Then F' is given by
F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
         kb1 cos(kx) + 2kb2 cos(2kx) + ...
Set F'(x) = 0 and solve for x's that satisfy this equation.
These should approximate the turning point.

I don't know if it will work for your application, or how
practrical it will be.

<AWinestein@gmail.com> wrote in message
news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
> On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>> <AWinest...@gmail.com> wrote in message
>>
>> news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>>
>>
>>
>>
>>
>> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>> >> How to detect turning points in curves
>>
>> >> Hi all,
>>
>> >> If you take a look at the following plot,
>>
>> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>>
>> >> You will agree with me that there are two turning points.
>>
>> >> But is there a systematic way to let computer detect the turning
>> >> points
>> >> automatically and programmatically?
>>
>> >> Please be advised that the second turn isn't neccessarily turning
>> >> down,
>> >> it
>> >> can also possibly go up...
>>
>> >> And in real-world applications, the turn can be more smooth and round,
>> >> but
>> >> still, naked eyes should be able to find the turning points easily.
>>
>> >> My program has to do a classification:
>>
>> >> All the good curves should first go down, and then either make no
>> >> turns;
>> >> or
>> >> make a turn, and stay vertically flat and slightly up, going from the
>> >> left
>> >> to the right.
>>
>> >> There should be no second turn (up or down). If there is the second
>> >> turn,
>> >> then that's the bad curves.
>>
>> >> My program needs to decern the good curves from bad curves.
>>
>> >> I cranked a few algorithms but they don't work well. Are there
>> >> systematic
>> >> methods of handling this?
>>
>> >> Thanks a lot!
>>
>> > My browser wouldn't show your image, but here's a
>> > thought. If your points are sampled at equal intervals,
>> > you can do a Fourier transform, use the analytic expression
>> > of the derivative term by term and the Fourier coefficients
>> > to calculate the derivative of the Fourier representation
>> > of your "function", and find the zeros of the derivative
>> > and take those as the turning points. FWIW.
>>
>> How? Could you please elaborate?- Hide quoted text -
>>
>> - Show quoted text -
>
> This is a brief summary. Hopefully it doesn't insult your
> intelligence and isn't too sketchy.
>
> Under certain conditions on F,
> F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
> b1 sin(kx) + b2 sin(2kx) + ...
> Using a discrete Fourier Transform (preferably using the Fast
> Fourier Transform algorithm if you have very many data points),
> you can calculate a discrete set of a's and b's the cause F to
> agree with your function at the x values for which you have F
> values. Then F' is given by
> F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
> kb1 cos(kx) + 2kb2 cos(2kx) + ...
> Set F'(x) = 0 and solve for x's that satisfy this equation.
> These should approximate the turning point.
>
> I don't know if it will work for your application, or how
> practrical it will be.
>

Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT) and
specifically used for detecting "changes" like this.

"Jon Slaughter" <Jon_Slaughter@Hotmail.com> wrote in message
news:MfHli.6345$rL1.6014@newssvr19.news.prodigy.net...
>
> <AWinestein@gmail.com> wrote in message
> news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
>> On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>>> <AWinest...@gmail.com> wrote in message
>>>
>>> news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>>>
>>>
>>>
>>>
>>>
>>> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>>> >> How to detect turning points in curves
>>>
>>> >> Hi all,
>>>
>>> >> If you take a look at the following plot,
>>>
>>> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>>>
>>> >> You will agree with me that there are two turning points.
>>>
>>> >> But is there a systematic way to let computer detect the turning
>>> >> points
>>> >> automatically and programmatically?
>>>
>>> >> Please be advised that the second turn isn't neccessarily turning
>>> >> down,
>>> >> it
>>> >> can also possibly go up...
>>>
>>> >> And in real-world applications, the turn can be more smooth and
>>> >> round,
>>> >> but
>>> >> still, naked eyes should be able to find the turning points easily.
>>>
>>> >> My program has to do a classification:
>>>
>>> >> All the good curves should first go down, and then either make no
>>> >> turns;
>>> >> or
>>> >> make a turn, and stay vertically flat and slightly up, going from the
>>> >> left
>>> >> to the right.
>>>
>>> >> There should be no second turn (up or down). If there is the second
>>> >> turn,
>>> >> then that's the bad curves.
>>>
>>> >> My program needs to decern the good curves from bad curves.
>>>
>>> >> I cranked a few algorithms but they don't work well. Are there
>>> >> systematic
>>> >> methods of handling this?
>>>
>>> >> Thanks a lot!
>>>
>>> > My browser wouldn't show your image, but here's a
>>> > thought. If your points are sampled at equal intervals,
>>> > you can do a Fourier transform, use the analytic expression
>>> > of the derivative term by term and the Fourier coefficients
>>> > to calculate the derivative of the Fourier representation
>>> > of your "function", and find the zeros of the derivative
>>> > and take those as the turning points. FWIW.
>>>
>>> How? Could you please elaborate?- Hide quoted text -
>>>
>>> - Show quoted text -
>>
>> This is a brief summary. Hopefully it doesn't insult your
>> intelligence and isn't too sketchy.
>>
>> Under certain conditions on F,
>> F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
>> b1 sin(kx) + b2 sin(2kx) + ...
>> Using a discrete Fourier Transform (preferably using the Fast
>> Fourier Transform algorithm if you have very many data points),
>> you can calculate a discrete set of a's and b's the cause F to
>> agree with your function at the x values for which you have F
>> values. Then F' is given by
>> F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
>> kb1 cos(kx) + 2kb2 cos(2kx) + ...
>> Set F'(x) = 0 and solve for x's that satisfy this equation.
>> These should approximate the turning point.
>>
>> I don't know if it will work for your application, or how
>> practrical it will be.
>>
>
> Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT)
> and specifically used for detecting "changes" like this.
>
>
>

I admit that I've never heard about that... how to do that? Could you please
elaborate?

Thanks!

On Jul 13, 7:42 am, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote in message
>
> news:MfHli.6345$rL1.6014@newssvr19.news.prodigy.net...
>
>
>
>
>
>
>
> > <AWinest...@gmail.com> wrote in message
> >news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
> >> On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> >>> <AWinest...@gmail.com> wrote in message
>
> >>>news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>
> >>> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> >>> >> How to detect turning points in curves
>
> >>> >> Hi all,
>
> >>> >> If you take a look at the following plot,
>
> >>> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> >>> >> You will agree with me that there are two turning points.
>
> >>> >> But is there a systematic way to let computer detect the turning
> >>> >> points
> >>> >> automatically and programmatically?
>
> >>> >> Please be advised that the second turn isn't neccessarily turning
> >>> >> down,
> >>> >> it
> >>> >> can also possibly go up...
>
> >>> >> And in real-world applications, the turn can be more smooth and
> >>> >> round,
> >>> >> but
> >>> >> still, naked eyes should be able to find the turning points easily.
>
> >>> >> My program has to do a classification:
>
> >>> >> All the good curves should first go down, and then either make no
> >>> >> turns;
> >>> >> or
> >>> >> make a turn, and stay vertically flat and slightly up, going from the
> >>> >> left
> >>> >> to the right.
>
> >>> >> There should be no second turn (up or down). If there is the second
> >>> >> turn,
> >>> >> then that's the bad curves.
>
> >>> >> My program needs to decern the good curves from bad curves.
>
> >>> >> I cranked a few algorithms but they don't work well. Are there
> >>> >> systematic
> >>> >> methods of handling this?
>
> >>> >> Thanks a lot!
>
> >>> > My browser wouldn't show your image, but here's a
> >>> > thought. If your points are sampled at equal intervals,
> >>> > you can do a Fourier transform, use the analytic expression
> >>> > of the derivative term by term and the Fourier coefficients
> >>> > to calculate the derivative of the Fourier representation
> >>> > of your "function", and find the zeros of the derivative
> >>> > and take those as the turning points. FWIW.
>
> >>> How? Could you please elaborate?- Hide quoted text -
>
> >>> - Show quoted text -
>
> >> This is a brief summary. Hopefully it doesn't insult your
> >> intelligence and isn't too sketchy.
>
> >> Under certain conditions on F,
> >> F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
> >> b1 sin(kx) + b2 sin(2kx) + ...
> >> Using a discrete Fourier Transform (preferably using the Fast
> >> Fourier Transform algorithm if you have very many data points),
> >> you can calculate a discrete set of a's and b's the cause F to
> >> agree with your function at the x values for which you have F
> >> values. Then F' is given by
> >> F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
> >> kb1 cos(kx) + 2kb2 cos(2kx) + ...
> >> Set F'(x) = 0 and solve for x's that satisfy this equation.
> >> These should approximate the turning point.
>
> >> I don't know if it will work for your application, or how
> >> practrical it will be.
>
> > Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT)
> > and specifically used for detecting "changes" like this.
>
> I admit that I've never heard about that... how to do that? Could you please
> elaborate?
>
> Thanks!- Hide quoted text -
>
> - Show quoted text -

Detecting "turning points" requires a model. Intervention Detection
methods compute the probability of observing what you observed "BEFORE
YOU OBSERVED IT" ... Thus if that probability ( for the last observed
poinr ) is small ...say less than some critical value ..one can
conclude (ceterus paribus) that an anomaly has been observed.

Going forward ...

1. download and install the freeware time series analysis and
forecasting ackage called FREEFORE from http://www.autobox.com/freef.exe

2. provide it with a history set of values (recordings) and examine
whether or not the LAST POINT is found to be anomolous.

3. step though time 1 period by period and continue the evaluation of
whether FREEFORE reports that an INTERVENTION has occurred at the most
recent point.

hth

dave reilly
automatic forecasting systems
http://www.autobox.com
215-675-0652

On Jul 13, 5:05 am, "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote:
> <AWinest...@gmail.com> wrote in message
>
> news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
>
>
>
>
>
> > On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> >> <AWinest...@gmail.com> wrote in message
>
> >>news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>
> >> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> >> >> How to detect turning points in curves
>
> >> >> Hi all,
>
> >> >> If you take a look at the following plot,
>
> >> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> >> >> You will agree with me that there are two turning points.
>
> >> >> But is there a systematic way to let computer detect the turning
> >> >> points
> >> >> automatically and programmatically?
>
> >> >> Please be advised that the second turn isn't neccessarily turning
> >> >> down,
> >> >> it
> >> >> can also possibly go up...
>
> >> >> And in real-world applications, the turn can be more smooth and round,
> >> >> but
> >> >> still, naked eyes should be able to find the turning points easily.
>
> >> >> My program has to do a classification:
>
> >> >> All the good curves should first go down, and then either make no
> >> >> turns;
> >> >> or
> >> >> make a turn, and stay vertically flat and slightly up, going from the
> >> >> left
> >> >> to the right.
>
> >> >> There should be no second turn (up or down). If there is the second
> >> >> turn,
> >> >> then that's the bad curves.
>
> >> >> My program needs to decern the good curves from bad curves.
>
> >> >> I cranked a few algorithms but they don't work well. Are there
> >> >> systematic
> >> >> methods of handling this?
>
> >> >> Thanks a lot!
>
> >> > My browser wouldn't show your image, but here's a
> >> > thought. If your points are sampled at equal intervals,
> >> > you can do a Fourier transform, use the analytic expression
> >> > of the derivative term by term and the Fourier coefficients
> >> > to calculate the derivative of the Fourier representation
> >> > of your "function", and find the zeros of the derivative
> >> > and take those as the turning points. FWIW.
>
> >> How? Could you please elaborate?- Hide quoted text -
>
> >> - Show quoted text -
>
> > This is a brief summary. Hopefully it doesn't insult your
> > intelligence and isn't too sketchy.
>
> > Under certain conditions on F,
> > F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
> > b1 sin(kx) + b2 sin(2kx) + ...
> > Using a discrete Fourier Transform (preferably using the Fast
> > Fourier Transform algorithm if you have very many data points),
> > you can calculate a discrete set of a's and b's the cause F to
> > agree with your function at the x values for which you have F
> > values. Then F' is given by
> > F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
> > kb1 cos(kx) + 2kb2 cos(2kx) + ...
> > Set F'(x) = 0 and solve for x's that satisfy this equation.
> > These should approximate the turning point.
>
> > I don't know if it will work for your application, or how
> > practrical it will be.
>
> Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT) and
> specifically used for detecting "changes" like this.- Hide quoted text -
>
> - Show quoted text -

Yes, wavelets are good. Kind of depends on whether there are
any reasons to prefer more global or local function behavior
to influence one's calculation of local turning points. There
didn't appear to be any given in the OP's post, so wavelets
might well be better there.

Linus Utopia:
<SNIP cross-talk...

> Are you suggesting a hack...

not really

% create some data
% ...a skeleton
     y=[5,3,2,0,0,0,0,0,0,0,-1,-3,-5,-5,-6].';
     x=(1:numel(y)).';
% ...slightly enhanced
     xs=(x(1):.2:x(end)).';
     ys=interp1(x,y,xs,'spline');
% the engine
% ...macro of a poor man's 2d cross product
     cp=@(u,v)u(:,1).*v(:,2)-u(:,2).*v(:,1);
     dx=diff(xs);
     dy=diff(ys);
     dd=[dx,dy];
     r=cp(dd(1:end-1,:),dd(2:end,:));
% the result on display
% - note: some vals are scaled for clarity
     lh=zeros(3,1);
     lh(1)=line(xs,ys,...
           'markerfacecolor',[0,0,1],...
           'color',[0,0,1]);
     lh(2)=line(xs(2:end-1),500*r,...
           'markerfacecolor',[1,0,0],...
           'color',[1,0,0]);
     lh(3)=line(xs(2:end),10*dy,...
           'markerfacecolor',[0,1,0],...
           'color',[0,1,0]);
     set(lh,'marker','o',...
            'markersize',4);
     line(x([1,end]),[0,0],-[1,1],...
         'color',.85*[1,1,1]);
     legend(lh,'data','cross','diff');

now, look at the <red> cross-product...
- how does it change with respect to the <blue> data
- how easy would it be to check whether all are >=0
- how does it compare with the diff

just a thought
us

On Jul 14, 1:02 am, AWinest...@gmail.com wrote:
> On Jul 13, 5:05 am, "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote:
>
>
>
>
>
> > <AWinest...@gmail.com> wrote in message
>
> >news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
>
> > > On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> > >> <AWinest...@gmail.com> wrote in message
>
> > >>news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>
> > >> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> > >> >> How to detect turning points in curves
>
> > >> >> Hi all,
>
> > >> >> If you take a look at the following plot,
>
> > >> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> > >> >> You will agree with me that there are two turning points.
>
> > >> >> But is there a systematic way to let computer detect the turning
> > >> >> points
> > >> >> automatically and programmatically?
>
> > >> >> Please be advised that the second turn isn't neccessarily turning
> > >> >> down,
> > >> >> it
> > >> >> can also possibly go up...
>
> > >> >> And in real-world applications, the turn can be more smooth and round,
> > >> >> but
> > >> >> still, naked eyes should be able to find the turning points easily.
>
> > >> >> My program has to do a classification:
>
> > >> >> All the good curves should first go down, and then either make no
> > >> >> turns;
> > >> >> or
> > >> >> make a turn, and stay vertically flat and slightly up, going from the
> > >> >> left
> > >> >> to the right.
>
> > >> >> There should be no second turn (up or down). If there is the second
> > >> >> turn,
> > >> >> then that's the bad curves.
>
> > >> >> My program needs to decern the good curves from bad curves.
>
> > >> >> I cranked a few algorithms but they don't work well. Are there
> > >> >> systematic
> > >> >> methods of handling this?
>
> > >> >> Thanks a lot!
>
> > >> > My browser wouldn't show your image, but here's a
> > >> > thought. If your points are sampled at equal intervals,
> > >> > you can do a Fourier transform, use the analytic expression
> > >> > of the derivative term by term and the Fourier coefficients
> > >> > to calculate the derivative of the Fourier representation
> > >> > of your "function", and find the zeros of the derivative
> > >> > and take those as the turning points. FWIW.
>
> > >> How? Could you please elaborate?- Hide quoted text -
>
> > >> - Show quoted text -
>
> > > This is a brief summary. Hopefully it doesn't insult your
> > > intelligence and isn't too sketchy.
>
> > > Under certain conditions on F,
> > > F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
> > > b1 sin(kx) + b2 sin(2kx) + ...
> > > Using a discrete Fourier Transform (preferably using the Fast
> > > Fourier Transform algorithm if you have very many data points),
> > > you can calculate a discrete set of a's and b's the cause F to
> > > agree with your function at the x values for which you have F
> > > values. Then F' is given by
> > > F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
> > > kb1 cos(kx) + 2kb2 cos(2kx) + ...
> > > Set F'(x) = 0 and solve for x's that satisfy this equation.
> > > These should approximate the turning point.
>
> > > I don't know if it will work for your application, or how
> > > practrical it will be.
>
> > Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT) and
> > specifically used for detecting "changes" like this.- Hide quoted text -
>
> > - Show quoted text -
>
> Yes, wavelets are good. Kind of depends on whether there are
> any reasons to prefer more global or local function behavior
> to influence one's calculation of local turning points. There
> didn't appear to be any given in the OP's post, so wavelets
> might well be better there.- Hide quoted text -
>
> - Show quoted text -

Well, I'd like to know in what way "wavelets are good" for this
problem?
I use wavelets all the time, but I see no way of applying them in this
case.
The OP has a signal that looks like half of a swastika, with two
vertical arms joined by a horizontal arm.
Orthogonal wavelet decomposition does not like such signals and makes
a pig's ear of the job because of end effects. For wavelet
decomposition, the ends should be at the same level (ideally, zero),
and the signal needs to be padded at either end with at least N/4
zeroes.
Seems to me that wavelets are BAD for this problem.

"us" <us@neurol.unizh.ch> wrote in message
news:ef5d53f.12@webcrossing.raydaftYaTP...
> Linus Utopia:
> <SNIP cross-talk...
>
>> Are you suggesting a hack...
>
> not really
>
> % create some data
> % ...a skeleton
> y=[5,3,2,0,0,0,0,0,0,0,-1,-3,-5,-5,-6].';
> x=(1:numel(y)).';
> % ...slightly enhanced
> xs=(x(1):.2:x(end)).';
> ys=interp1(x,y,xs,'spline');
> % the engine
> % ...macro of a poor man's 2d cross product
> cp=@(u,v)u(:,1).*v(:,2)-u(:,2).*v(:,1);
> dx=diff(xs);
> dy=diff(ys);
> dd=[dx,dy];
> r=cp(dd(1:end-1,:),dd(2:end,:));
> % the result on display
> % - note: some vals are scaled for clarity
> lh=zeros(3,1);
> lh(1)=line(xs,ys,...
> 'markerfacecolor',[0,0,1],...
> 'color',[0,0,1]);
> lh(2)=line(xs(2:end-1),500*r,...
> 'markerfacecolor',[1,0,0],...
> 'color',[1,0,0]);
> lh(3)=line(xs(2:end),10*dy,...
> 'markerfacecolor',[0,1,0],...
> 'color',[0,1,0]);
> set(lh,'marker','o',...
> 'markersize',4);
> line(x([1,end]),[0,0],-[1,1],...
> 'color',.85*[1,1,1]);
> legend(lh,'data','cross','diff');
>
> now, look at the <red> cross-product...
> - how does it change with respect to the <blue> data
> - how easy would it be to check whether all are >=0
> - how does it compare with the diff
>
> just a thought
> us

Wow. Very cool! The positive and negative peaks of the <red> cross-product
curve shows the turning points of the <blue> data very clearly, even for
very slight transitions in the data. I also like your "macro" definition of
cp. I didn't know this usage in Matlab... Thank you! But I still have
questions:

1. This didn't solve the problem -- how do you detect the positive and
negative peaks in <red> cross-product curve then?

2. How reliable is this method?

<dave@autobox.com> wrote in message
news:1184329839.101091.223770@n2g2000hse.googlegroups.com...
> On Jul 13, 7:42 am, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>> "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote in message
>>
>> news:MfHli.6345$rL1.6014@newssvr19.news.prodigy.net...
>>
>>
>>
>>
>>
>>
>>
>> > <AWinest...@gmail.com> wrote in message
>> >news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
>> >> On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>> >>> <AWinest...@gmail.com> wrote in message
>>
>> >>>news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>>
>> >>> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>> >>> >> How to detect turning points in curves
>>
>> >>> >> Hi all,
>>
>> >>> >> If you take a look at the following plot,
>>
>> >>> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>>
>> >>> >> You will agree with me that there are two turning points.
>>
>> >>> >> But is there a systematic way to let computer detect the turning
>> >>> >> points
>> >>> >> automatically and programmatically?
>>
>> >>> >> Please be advised that the second turn isn't neccessarily turning
>> >>> >> down,
>> >>> >> it
>> >>> >> can also possibly go up...
>>
>> >>> >> And in real-world applications, the turn can be more smooth and
>> >>> >> round,
>> >>> >> but
>> >>> >> still, naked eyes should be able to find the turning points
>> >>> >> easily.
>>
>> >>> >> My program has to do a classification:
>>
>> >>> >> All the good curves should first go down, and then either make no
>> >>> >> turns;
>> >>> >> or
>> >>> >> make a turn, and stay vertically flat and slightly up, going from
>> >>> >> the
>> >>> >> left
>> >>> >> to the right.
>>
>> >>> >> There should be no second turn (up or down). If there is the
>> >>> >> second
>> >>> >> turn,
>> >>> >> then that's the bad curves.
>>
>> >>> >> My program needs to decern the good curves from bad curves.
>>
>> >>> >> I cranked a few algorithms but they don't work well. Are there
>> >>> >> systematic
>> >>> >> methods of handling this?
>>
>> >>> >> Thanks a lot!
>>
>> >>> > My browser wouldn't show your image, but here's a
>> >>> > thought. If your points are sampled at equal intervals,
>> >>> > you can do a Fourier transform, use the analytic expression
>> >>> > of the derivative term by term and the Fourier coefficients
>> >>> > to calculate the derivative of the Fourier representation
>> >>> > of your "function", and find the zeros of the derivative
>> >>> > and take those as the turning points. FWIW.
>>
>> >>> How? Could you please elaborate?- Hide quoted text -
>>
>> >>> - Show quoted text -
>>
>> >> This is a brief summary. Hopefully it doesn't insult your
>> >> intelligence and isn't too sketchy.
>>
>> >> Under certain conditions on F,
>> >> F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
>> >> b1 sin(kx) + b2 sin(2kx) + ...
>> >> Using a discrete Fourier Transform (preferably using the Fast
>> >> Fourier Transform algorithm if you have very many data points),
>> >> you can calculate a discrete set of a's and b's the cause F to
>> >> agree with your function at the x values for which you have F
>> >> values. Then F' is given by
>> >> F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
>> >> kb1 cos(kx) + 2kb2 cos(2kx) + ...
>> >> Set F'(x) = 0 and solve for x's that satisfy this equation.
>> >> These should approximate the turning point.
>>
>> >> I don't know if it will work for your application, or how
>> >> practrical it will be.
>>
>> > Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT)
>> > and specifically used for detecting "changes" like this.
>>
>> I admit that I've never heard about that... how to do that? Could you
>> please
>> elaborate?
>>
>> Thanks!- Hide quoted text -
>>
>> - Show quoted text -
>
> Detecting "turning points" requires a model. Intervention Detection
> methods compute the probability of observing what you observed "BEFORE
> YOU OBSERVED IT" ... Thus if that probability ( for the last observed
> poinr ) is small ...say less than some critical value ..one can
> conclude (ceterus paribus) that an anomaly has been observed.
>
> Going forward ...
>
> 1. download and install the freeware time series analysis and
> forecasting ackage called FREEFORE from http://www.autobox.com/freef.exe
>
> 2. provide it with a history set of values (recordings) and examine
> whether or not the LAST POINT is found to be anomolous.
>
> 3. step though time 1 period by period and continue the evaluation of
> whether FREEFORE reports that an INTERVENTION has occurred at the most
> recent point.
>
> hth
>
> dave reilly
> automatic forecasting systems
> http://www.autobox.com
> 215-675-0652
>
>
>
>

I have to do that in Matlab and within my own program. Thanks

<AWinestein@gmail.com> wrote in message
news:1184331729.785200.153510@n60g2000hse.googlegroups.com...
> On Jul 13, 5:05 am, "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote:
>> <AWinest...@gmail.com> wrote in message
>>
>> news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
>>
>>
>>
>>
>>
>> > On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>> >> <AWinest...@gmail.com> wrote in message
>>
>> >>news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>>
>> >> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>> >> >> How to detect turning points in curves
>>
>> >> >> Hi all,
>>
>> >> >> If you take a look at the following plot,
>>
>> >> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>>
>> >> >> You will agree with me that there are two turning points.
>>
>> >> >> But is there a systematic way to let computer detect the turning
>> >> >> points
>> >> >> automatically and programmatically?
>>
>> >> >> Please be advised that the second turn isn't neccessarily turning
>> >> >> down,
>> >> >> it
>> >> >> can also possibly go up...
>>
>> >> >> And in real-world applications, the turn can be more smooth and
>> >> >> round,
>> >> >> but
>> >> >> still, naked eyes should be able to find the turning points easily.
>>
>> >> >> My program has to do a classification:
>>
>> >> >> All the good curves should first go down, and then either make no
>> >> >> turns;
>> >> >> or
>> >> >> make a turn, and stay vertically flat and slightly up, going from
>> >> >> the
>> >> >> left
>> >> >> to the right.
>>
>> >> >> There should be no second turn (up or down). If there is the second
>> >> >> turn,
>> >> >> then that's the bad curves.
>>
>> >> >> My program needs to decern the good curves from bad curves.
>>
>> >> >> I cranked a few algorithms but they don't work well. Are there
>> >> >> systematic
>> >> >> methods of handling this?
>>
>> >> >> Thanks a lot!
>>
>> >> > My browser wouldn't show your image, but here's a
>> >> > thought. If your points are sampled at equal intervals,
>> >> > you can do a Fourier transform, use the analytic expression
>> >> > of the derivative term by term and the Fourier coefficients
>> >> > to calculate the derivative of the Fourier representation
>> >> > of your "function", and find the zeros of the derivative
>> >> > and take those as the turning points. FWIW.
>>
>> >> How? Could you please elaborate?- Hide quoted text -
>>
>> >> - Show quoted text -
>>
>> > This is a brief summary. Hopefully it doesn't insult your
>> > intelligence and isn't too sketchy.
>>
>> > Under certain conditions on F,
>> > F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
>> > b1 sin(kx) + b2 sin(2kx) + ...
>> > Using a discrete Fourier Transform (preferably using the Fast
>> > Fourier Transform algorithm if you have very many data points),
>> > you can calculate a discrete set of a's and b's the cause F to
>> > agree with your function at the x values for which you have F
>> > values. Then F' is given by
>> > F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
>> > kb1 cos(kx) + 2kb2 cos(2kx) + ...
>> > Set F'(x) = 0 and solve for x's that satisfy this equation.
>> > These should approximate the turning point.
>>
>> > I don't know if it will work for your application, or how
>> > practrical it will be.
>>
>> Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT)
>> and
>> specifically used for detecting "changes" like this.- Hide quoted text -
>>
>> - Show quoted text -
>
> Yes, wavelets are good. Kind of depends on whether there are
> any reasons to prefer more global or local function behavior
> to influence one's calculation of local turning points. There
> didn't appear to be any given in the OP's post, so wavelets
> might well be better there.
>

But how to do wavelet? I have no idea at all.

On Jul 13, 5:22 pm, NZTideMan <mul...@gmail.com> wrote:
> On Jul 14, 1:02 am, AWinest...@gmail.com wrote:
>
>
>
>
>
> > On Jul 13, 5:05 am, "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote:
>
> > > <AWinest...@gmail.com> wrote in message
>
> > >news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
>
> > > > On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> > > >> <AWinest...@gmail.com> wrote in message
>
> > > >>news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>
> > > >> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> > > >> >> How to detect turning points in curves
>
> > > >> >> Hi all,
>
> > > >> >> If you take a look at the following plot,
>
> > > >> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> > > >> >> You will agree with me that there are two turning points.
>
> > > >> >> But is there a systematic way to let computer detect the turning
> > > >> >> points
> > > >> >> automatically and programmatically?
>
> > > >> >> Please be advised that the second turn isn't neccessarily turning
> > > >> >> down,
> > > >> >> it
> > > >> >> can also possibly go up...
>
> > > >> >> And in real-world applications, the turn can be more smooth and round,
> > > >> >> but
> > > >> >> still, naked eyes should be able to find the turning points easily.
>
> > > >> >> My program has to do a classification:
>
> > > >> >> All the good curves should first go down, and then either make no
> > > >> >> turns;
> > > >> >> or
> > > >> >> make a turn, and stay vertically flat and slightly up, going from the
> > > >> >> left
> > > >> >> to the right.
>
> > > >> >> There should be no second turn (up or down). If there is the second
> > > >> >> turn,
> > > >> >> then that's the bad curves.
>
> > > >> >> My program needs to decern the good curves from bad curves.
>
> > > >> >> I cranked a few algorithms but they don't work well. Are there
> > > >> >> systematic
> > > >> >> methods of handling this?
>
> > > >> >> Thanks a lot!
>
> > > >> > My browser wouldn't show your image, but here's a
> > > >> > thought. If your points are sampled at equal intervals,
> > > >> > you can do a Fourier transform, use the analytic expression
> > > >> > of the derivative term by term and the Fourier coefficients
> > > >> > to calculate the derivative of the Fourier representation
> > > >> > of your "function", and find the zeros of the derivative
> > > >> > and take those as the turning points. FWIW.
>
> > > >> How? Could you please elaborate?- Hide quoted text -
>
> > > >> - Show quoted text -
>
> > > > This is a brief summary. Hopefully it doesn't insult your
> > > > intelligence and isn't too sketchy.
>
> > > > Under certain conditions on F,
> > > > F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
> > > > b1 sin(kx) + b2 sin(2kx) + ...
> > > > Using a discrete Fourier Transform (preferably using the Fast
> > > > Fourier Transform algorithm if you have very many data points),
> > > > you can calculate a discrete set of a's and b's the cause F to
> > > > agree with your function at the x values for which you have F
> > > > values. Then F' is given by
> > > > F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
> > > > kb1 cos(kx) + 2kb2 cos(2kx) + ...
> > > > Set F'(x) = 0 and solve for x's that satisfy this equation.
> > > > These should approximate the turning point.
>
> > > > I don't know if it will work for your application, or how
> > > > practrical it will be.
>
> > > Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT) and
> > > specifically used for detecting "changes" like this.- Hide quoted text -
>
> > > - Show quoted text -
>
> > Yes, wavelets are good. Kind of depends on whether there are
> > any reasons to prefer more global or local function behavior
> > to influence one's calculation of local turning points. There
> > didn't appear to be any given in the OP's post, so wavelets
> > might well be better there.- Hide quoted text -
>
> > - Show quoted text -
>
> Well, I'd like to know in what way "wavelets are good"

My statement "wavelets are good" was without reference to this
problem. I just like wavelets. Don't you?

> for this
> problem?

Note I did say "might" be better than a Fourier expansion for
this problem. More on this point below.

> I use wavelets all the time, but I see no way of applying them in this
> case.
> The OP has a signal that looks like half of a swastika, with two
> vertical arms joined by a horizontal arm.

Apparently you didn't read the whole thread closely, because
I mentioned in my first post that my browser wouldn't show
the OP's graphic, so I could hardly have known that. Fourier
expansion would not be my first thought for the function
you've described.

> Orthogonal wavelet decomposition does not like such signals and makes
> a pig's ear of the job because of end effects.

Although you use wavelets all the time, perhaps you are not
familiar with all types. Haar functions, the first known
wavelets and now decades old (I've been using them over 25
years, and the subject was old when I first come across it),
"like" such signals just fine. Of course, Haar functions are
usually the first wavelets mentioned in the texts I read, so
I'd be surprised if you have not encountered them. However,
in this case the whole derivative approach may be a
nonstarter anyway.

> For wavelet
> decomposition, the ends should be at the same level (ideally, zero),
> and the signal needs to be padded at either end with at least N/4
> zeroes.

Not with Haar functions. One needs to pad to 2^N points to
use the fast transform. I usually use the mean of the data,
but that might vary depending on the application.

> Seems to me that wavelets are BAD for this problem.

They may be, but your arguments have not shown that conclusively.
For free on Usenet the OP gets ideas off the top of my head and
gets what he pays for. :-)

Also you might read more closely and it would be polite of you to
post with a little circumspection.

- Hide quoted text -
>
> - Show quoted text -

On Jul 13, 9:18 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> <AWinest...@gmail.com> wrote in message
>
> news:1184331729.785200.153510@n60g2000hse.googlegroups.com...
>
>
>
>
>
> > On Jul 13, 5:05 am, "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote:
> >> <AWinest...@gmail.com> wrote in message
>
> >>news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
>
> >> > On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> >> >> <AWinest...@gmail.com> wrote in message
>
> >> >>news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>
> >> >> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> >> >> >> How to detect turning points in curves
>
> >> >> >> Hi all,
>
> >> >> >> If you take a look at the following plot,
>
> >> >> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> >> >> >> You will agree with me that there are two turning points.
>
> >> >> >> But is there a systematic way to let computer detect the turning
> >> >> >> points
> >> >> >> automatically and programmatically?
>
> >> >> >> Please be advised that the second turn isn't neccessarily turning
> >> >> >> down,
> >> >> >> it
> >> >> >> can also possibly go up...
>
> >> >> >> And in real-world applications, the turn can be more smooth and
> >> >> >> round,
> >> >> >> but
> >> >> >> still, naked eyes should be able to find the turning points easily.
>
> >> >> >> My program has to do a classification:
>
> >> >> >> All the good curves should first go down, and then either make no
> >> >> >> turns;
> >> >> >> or
> >> >> >> make a turn, and stay vertically flat and slightly up, going from
> >> >> >> the
> >> >> >> left
> >> >> >> to the right.
>
> >> >> >> There should be no second turn (up or down). If there is the second
> >> >> >> turn,
> >> >> >> then that's the bad curves.
>
> >> >> >> My program needs to decern the good curves from bad curves.
>
> >> >> >> I cranked a few algorithms but they don't work well. Are there
> >> >> >> systematic
> >> >> >> methods of handling this?
>
> >> >> >> Thanks a lot!
>
> >> >> > My browser wouldn't show your image, but here's a
> >> >> > thought. If your points are sampled at equal intervals,
> >> >> > you can do a Fourier transform, use the analytic expression
> >> >> > of the derivative term by term and the Fourier coefficients
> >> >> > to calculate the derivative of the Fourier representation
> >> >> > of your "function", and find the zeros of the derivative
> >> >> > and take those as the turning points. FWIW.
>
> >> >> How? Could you please elaborate?- Hide quoted text -
>
> >> >> - Show quoted text -
>
> >> > This is a brief summary. Hopefully it doesn't insult your
> >> > intelligence and isn't too sketchy.
>
> >> > Under certain conditions on F,
> >> > F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
> >> > b1 sin(kx) + b2 sin(2kx) + ...
> >> > Using a discrete Fourier Transform (preferably using the Fast
> >> > Fourier Transform algorithm if you have very many data points),
> >> > you can calculate a discrete set of a's and b's the cause F to
> >> > agree with your function at the x values for which you have F
> >> > values. Then F' is given by
> >> > F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
> >> > kb1 cos(kx) + 2kb2 cos(2kx) + ...
> >> > Set F'(x) = 0 and solve for x's that satisfy this equation.
> >> > These should approximate the turning point.
>
> >> > I don't know if it will work for your application, or how
> >> > practrical it will be.
>
> >> Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT)
> >> and
> >> specifically used for detecting "changes" like this.- Hide quoted text -
>
> >> - Show quoted text -
>
> > Yes, wavelets are good. Kind of depends on whether there are
> > any reasons to prefer more global or local function behavior
> > to influence one's calculation of local turning points. There
> > didn't appear to be any given in the OP's post, so wavelets
> > might well be better there.
>
> But how to do wavelet? I have no idea at all.
> - Hide quoted text -
>
> - Show quoted text -

For how your function has now been described, I'd have to
think about the whole problem more, and at the moment I have
my own plate full. If you want to read about a wavelet that
might be applicable try
http://mathworld.wolfram.com/HaarFunction.html .

On Jul 14, 2:02 pm, AWinest...@gmail.com wrote:
> On Jul 13, 5:22 pm, NZTideMan <mul...@gmail.com> wrote:
>
>
>
>
>
> > On Jul 14, 1:02 am, AWinest...@gmail.com wrote:
>
> > > On Jul 13, 5:05 am, "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote:
>
> > > > <AWinest...@gmail.com> wrote in message
>
> > > >news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
>
> > > > > On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> > > > >> <AWinest...@gmail.com> wrote in message
>
> > > > >>news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>
> > > > >> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> > > > >> >> How to detect turning points in curves
>
> > > > >> >> Hi all,
>
> > > > >> >> If you take a look at the following plot,
>
> > > > >> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> > > > >> >> You will agree with me that there are two turning points.
>
> > > > >> >> But is there a systematic way to let computer detect the turning
> > > > >> >> points
> > > > >> >> automatically and programmatically?
>
> > > > >> >> Please be advised that the second turn isn't neccessarily turning
> > > > >> >> down,
> > > > >> >> it
> > > > >> >> can also possibly go up...
>
> > > > >> >> And in real-world applications, the turn can be more smooth and round,
> > > > >> >> but
> > > > >> >> still, naked eyes should be able to find the turning points easily.
>
> > > > >> >> My program has to do a classification:
>
> > > > >> >> All the good curves should first go down, and then either make no
> > > > >> >> turns;
> > > > >> >> or
> > > > >> >> make a turn, and stay vertically flat and slightly up, going from the
> > > > >> >> left
> > > > >> >> to the right.
>
> > > > >> >> There should be no second turn (up or down). If there is the second
> > > > >> >> turn,
> > > > >> >> then that's the bad curves.
>
> > > > >> >> My program needs to decern the good curves from bad curves.
>
> > > > >> >> I cranked a few algorithms but they don't work well. Are there
> > > > >> >> systematic
> > > > >> >> methods of handling this?
>
> > > > >> >> Thanks a lot!
>
> > > > >> > My browser wouldn't show your image, but here's a
> > > > >> > thought. If your points are sampled at equal intervals,
> > > > >> > you can do a Fourier transform, use the analytic expression
> > > > >> > of the derivative term by term and the Fourier coefficients
> > > > >> > to calculate the derivative of the Fourier representation
> > > > >> > of your "function", and find the zeros of the derivative
> > > > >> > and take those as the turning points. FWIW.
>
> > > > >> How? Could you please elaborate?- Hide quoted text -
>
> > > > >> - Show quoted text -
>
> > > > > This is a brief summary. Hopefully it doesn't insult your
> > > > > intelligence and isn't too sketchy.
>
> > > > > Under certain conditions on F,
> > > > > F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
> > > > > b1 sin(kx) + b2 sin(2kx) + ...
> > > > > Using a discrete Fourier Transform (preferably using the Fast
> > > > > Fourier Transform algorithm if you have very many data points),
> > > > > you can calculate a discrete set of a's and b's the cause F to
> > > > > agree with your function at the x values for which you have F
> > > > > values. Then F' is given by
> > > > > F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
> > > > > kb1 cos(kx) + 2kb2 cos(2kx) + ...
> > > > > Set F'(x) = 0 and solve for x's that satisfy this equation.
> > > > > These should approximate the turning point.
>
> > > > > I don't know if it will work for your application, or how
> > > > > practrical it will be.
>
> > > > Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT) and
> > > > specifically used for detecting "changes" like this.- Hide quoted text -
>
> > > > - Show quoted text -
>
> > > Yes, wavelets are good. Kind of depends on whether there are
> > > any reasons to prefer more global or local function behavior
> > > to influence one's calculation of local turning points. There
> > > didn't appear to be any given in the OP's post, so wavelets
> > > might well be better there.- Hide quoted text -
>
> > > - Show quoted text -
>
> > Well, I'd like to know in what way "wavelets are good"
>
> My statement "wavelets are good" was without reference to this
> problem. I just like wavelets. Don't you?
>
> > for this
> > problem?
>
> Note I did say "might" be better than a Fourier expansion for
> this problem. More on this point below.
>
> > I use wavelets all the time, but I see no way of applying them in this
> > case.
> > The OP has a signal that looks like half of a swastika, with two
> > vertical arms joined by a horizontal arm.
>
> Apparently you didn't read the whole thread closely, because
> I mentioned in my first post that my browser wouldn't show
> the OP's graphic, so I could hardly have known that. Fourier
> expansion would not be my first thought for the function
> you've described.
>
> > Orthogonal wavelet decomposition does not like such signals and makes
> > a pig's ear of the job because of end effects.
>
> Although you use wavelets all the time, perhaps you are not
> familiar with all types. Haar functions, the first known
> wavelets and now decades old (I've been using them over 25
> years, and the subject was old when I first come across it),
> "like" such signals just fine. Of course, Haar functions are
> usually the first wavelets mentioned in the texts I read, so
> I'd be surprised if you have not encountered them. However,
> in this case the whole derivative approach may be a
> nonstarter anyway.
>
> > For wavelet
> > decomposition, the ends should be at the same level (ideally, zero),
> > and the signal needs to be padded at either end with at least N/4
> > zeroes.
>
> Not with Haar functions. One needs to pad to 2^N points to
> use the fast transform. I usually use the mean of the data,
> but that might vary depending on the application.
>
> > Seems to me that wavelets are BAD for this problem.
>
> They may be, but your arguments have not shown that conclusively.
> For free on Usenet the OP gets ideas off the top of my head and
> gets what he pays for. :-)
>
> Also you might read more closely and it would be polite of you to
> post with a little circumspection.
>
> - Hide quoted text -
>
>
>
>
>
> > - Show quoted text -- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

The arrogance of the man!!
He gives spurious advice, and when he's picked up on it, he
gratuitously advises more circumspection.
My guess is that he's an academic who's hated by his grad students
because he's always sending them off on wild goose chases. And from
his comments on the use of wavelets, it's clear that he never deals
with real-world data.

Linus Utopia:
<SNIP does not seem to be able to look at things academically...

> But I still have questions:
> 1. This didn't solve the problem -- how do you detect the positive
and negative peaks in <red> cross-product curve then...
> 2. How reliable is this method...

1) according to your OP, it's not a matter of peaks, it's a matter of
     signal stays >=0 | <=0
...though anything else, like peak-detection, is equally trivial as
well...
2) extremely reliable - as a matter of fact, all the way down to FP
reliability...

now, have you shown your intelligence by extracting the very engine
from the snippet into a function, which might(!) take various inputs
of your choice to look at the results... unfortunately, i do not
think so...

note: no one at CSSM is going to solve your particular problem; the
good people, who choose to join your thread, are just giving you
ideas and - at best - possible code skeletons (ie, snippets) of how
you might proceed... and it's left up to you to display your
smartness by integrating them into your own frame of work...

us

On Jul 14, 5:34 pm, NZTideMan <mul...@gmail.com> wrote:
> On Jul 14, 2:02 pm, AWinest...@gmail.com wrote:
>
>
>
>
>
> > On Jul 13, 5:22 pm, NZTideMan <mul...@gmail.com> wrote:
>
> > > On Jul 14, 1:02 am, AWinest...@gmail.com wrote:
>
> > > > On Jul 13, 5:05 am, "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote:
>
> > > > > <AWinest...@gmail.com> wrote in message
>
> > > > >news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
>
> > > > > > On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> > > > > >> <AWinest...@gmail.com> wrote in message
>
> > > > > >>news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>
> > > > > >> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> > > > > >> >> How to detect turning points in curves
>
> > > > > >> >> Hi all,
>
> > > > > >> >> If you take a look at the following plot,
>
> > > > > >> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> > > > > >> >> You will agree with me that there are two turning points.
>
> > > > > >> >> But is there a systematic way to let computer detect the turning
> > > > > >> >> points
> > > > > >> >> automatically and programmatically?
>
> > > > > >> >> Please be advised that the second turn isn't neccessarily turning
> > > > > >> >> down,
> > > > > >> >> it
> > > > > >> >> can also possibly go up...
>
> > > > > >> >> And in real-world applications, the turn can be more smooth and round,
> > > > > >> >> but
> > > > > >> >> still, naked eyes should be able to find the turning points easily.
>
> > > > > >> >> My program has to do a classification:
>
> > > > > >> >> All the good curves should first go down, and then either make no
> > > > > >> >> turns;
> > > > > >> >> or
> > > > > >> >> make a turn, and stay vertically flat and slightly up, going from the
> > > > > >> >> left
> > > > > >> >> to the right.
>
> > > > > >> >> There should be no second turn (up or down). If there is the second
> > > > > >> >> turn,
> > > > > >> >> then that's the bad curves.
>
> > > > > >> >> My program needs to decern the good curves from bad curves.
>
> > > > > >> >> I cranked a few algorithms but they don't work well. Are there
> > > > > >> >> systematic
> > > > > >> >> methods of handling this?
>
> > > > > >> >> Thanks a lot!
>
> > > > > >> > My browser wouldn't show your image, but here's a
> > > > > >> > thought. If your points are sampled at equal intervals,
> > > > > >> > you can do a Fourier transform, use the analytic expression
> > > > > >> > of the derivative term by term and the Fourier coefficients
> > > > > >> > to calculate the derivative of the Fourier representation
> > > > > >> > of your "function", and find the zeros of the derivative
> > > > > >> > and take those as the turning points. FWIW.
>
> > > > > >> How? Could you please elaborate?- Hide quoted text -
>
> > > > > >> - Show quoted text -
>
> > > > > > This is a brief summary. Hopefully it doesn't insult your
> > > > > > intelligence and isn't too sketchy.
>
> > > > > > Under certain conditions on F,
> > > > > > F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
> > > > > > b1 sin(kx) + b2 sin(2kx) + ...
> > > > > > Using a discrete Fourier Transform (preferably using the Fast
> > > > > > Fourier Transform algorithm if you have very many data points),
> > > > > > you can calculate a discrete set of a's and b's the cause F to
> > > > > > agree with your function at the x values for which you have F
> > > > > > values. Then F' is given by
> > > > > > F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
> > > > > > kb1 cos(kx) + 2kb2 cos(2kx) + ...
> > > > > > Set F'(x) = 0 and solve for x's that satisfy this equation.
> > > > > > These should approximate the turning point.
>
> > > > > > I don't know if it will work for your application, or how
> > > > > > practrical it will be.
>
> > > > > Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT) and
> > > > > specifically used for detecting "changes" like this.- Hide quoted text -
>
> > > > > - Show quoted text -
>
> > > > Yes, wavelets are good. Kind of depends on whether there are
> > > > any reasons to prefer more global or local function behavior
> > > > to influence one's calculation of local turning points. There
> > > > didn't appear to be any given in the OP's post, so wavelets
> > > > might well be better there.- Hide quoted text -
>
> > > > - Show quoted text -
>
> > > Well, I'd like to know in what way "wavelets are good"
>
> > My statement "wavelets are good" was without reference to this
> > problem. I just like wavelets. Don't you?
>
> > > for this
> > > problem?
>
> > Note I did say "might" be better than a Fourier expansion for
> > this problem. More on this point below.
>
> > > I use wavelets all the time, but I see no way of applying them in this
> > > case.
> > > The OP has a signal that looks like half of a swastika, with two
> > > vertical arms joined by a horizontal arm.
>
> > Apparently you didn't read the whole thread closely, because
> > I mentioned in my first post that my browser wouldn't show
> > the OP's graphic, so I could hardly have known that. Fourier
> > expansion would not be my first thought for the function
> > you've described.
>
> > > Orthogonal wavelet decomposition does not like such signals and makes
> > > a pig's ear of the job because of end effects.
>
> > Although you use wavelets all the time, perhaps you are not
> > familiar with all types. Haar functions, the first known
> > wavelets and now decades old (I've been using them over 25
> > years, and the subject was old when I first come across it),
> > "like" such signals just fine. Of course, Haar functions are
> > usually the first wavelets mentioned in the texts I read, so
> > I'd be surprised if you have not encountered them. However,
> > in this case the whole derivative approach may be a
> > nonstarter anyway.
>
> > > For wavelet
> > > decomposition, the ends should be at the same level (ideally, zero),
> > > and the signal needs to be padded at either end with at least N/4
> > > zeroes.
>
> > Not with Haar functions. One needs to pad to 2^N points to
> > use the fast transform. I usually use the mean of the data,
> > but that might vary depending on the application.
>
> > > Seems to me that wavelets are BAD for this problem.
>
> > They may be, but your arguments have not shown that conclusively.
> > For free on Usenet the OP gets ideas off the top of my head and
> > gets what he pays for. :-)
>
> > Also you might read more closely and it would be polite of you to
> > post with a little circumspection.
>
> > - Hide quoted text -
>
> > > - Show quoted text -- Hide quoted text -
>
> > - Show quoted text -- Hide quoted text -
>
> > - Show quoted text -
>
> The arrogance of the man!!
> He gives spurious advice,

You gave a spurious analysis of my advice, based on
incorrect and incomplete of knowledge of the subject and
thread. Your comment, "Orthogonal wavelet decomposition
does not like such signals and makes a pig's ear of the
job because of end effects" is simply wrong, unless you
insist that Haar functions are not orthogonal wavelets.
Since all you've offered is an ad hominem attack, I'm
happy to let the readers draw their own conclusions.

> and when he's picked up on it, he
> gratuitously advises more circumspection.

I'm sorry you won't accept good advice.

> My guess is that he's an academic who's hated by his grad students
> because he's always sending them off on wild goose chases.

Hmmm, did you have a bad grad school experience that prompted
that comment? Well, you're wrong anyway.

> And from
> his comments on the use of wavelets, it's clear that he never deals
> with real-world data.

And you're wrong again. Perhaps you should try posting something
sensible and useful, for instance giving the OP some idea of how
you think he might approach his problem. But instead of trying to
be constructive, so far you've chosen just to throw rocks and at
the wrong target at that.

> - Hide quoted text -
>
> - Show quoted text -

In article <1184448854.707139.321250@i13g2000prf.googlegroups.com>,
NZTideMan <mulgor@gmail.com> wrote:
>The arrogance of the man!!
>He gives spurious advice, and when he's picked up on it, he
>gratuitously advises more circumspection.
>My guess is that he's an academic who's hated by his grad students
>because he's always sending them off on wild goose chases. And from
>his comments on the use of wavelets, it's clear that he never deals
>with real-world data.

Please could you (and others) trim posts. I had to scroll down
through many pages of quoted material just to read a paragraph
which adds nothing (imho) to the discussion.

Francis

On Jul 13, 6:26 am, "Linus Utopia" <linus_uto...@gmail.com> wrote:
> How to detect turning points in curves
>
> Hi all,
>
> If you take a look at the following plot,
>
> http://img63.imageshack.us/img63/5050/gggyt1.jpg
>
> You will agree with me that there are two turning points.
>
> But is there a systematic way to let computer detect the turning points
> automatically and programmatically?
>
> Please be advised that the second turn isn't neccessarily turning down, it
> can also possibly go up...
>
> And in real-world applications, the turn can be more smooth and round, but
> still, naked eyes should be able to find the turning points easily.
>
> My program has to do a classification:
>
> All the good curves should first go down, and then either make no turns; or
> make a turn, and stay vertically flat and slightly up, going from the left
> to the right.
>
> There should be no second turn (up or down). If there is the second turn,
> then that's the bad curves.
>
> My program needs to decern the good curves from bad curves.
>
> I cranked a few algorithms but they don't work well. Are there systematic
> methods of handling this?
>
> Thanks a lot!

Just plot y vs X = log x (say to base 10) , instead of y vs directly
to x in order to get a readable graph... it roughly appears to be the
shape of the lower half of a pear, laid flat (symmetric axis parallel
to x-axis ).

If points of inflection at two points are found, ( by computing second
finite differences changing sign on constant step intervals of X ) as
X1 and X2, then their x locations are at 10^X1 and 10^X2 respectively.

There are no good or bad curves. Draw a figure of eight for a general
situation. Changes of second derivative signs signal inflection
points that can be detected in two out of four segments, as roots of
y'' = 0 in such a curve.

HTH