Path: news.mathworks.com!newsfeed-00.mathworks.com!newscon02.news.prodigy.net!prodigy.net!news.glorb.com!postnews.google.com!n2g2000hse.googlegroups.com!not-for-mail
From:  AWinestein@gmail.com
Newsgroups: comp.soft-sys.matlab,sci.math,sci.stat.math,sci.stat.consult,sci.stat.edu
Subject: Re: How to detect turning points in curves...
Date: Thu, 12 Jul 2007 20:43:59 -0700
Organization: http://groups.google.com
Lines: 80
Message-ID: <1184298239.408921.284810@n2g2000hse.googlegroups.com>
References: <f76kg0$ic0$1@news.Stanford.EDU>
NNTP-Posting-Host: 64.24.177.172
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
X-Trace: posting.google.com 1184298239 13721 127.0.0.1 (13 Jul 2007 03:43:59 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Fri, 13 Jul 2007 03:43:59 +0000 (UTC)
In-Reply-To: <f76pbs$mef$1@news.Stanford.EDU>
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; .NET CLR 1.1.4322),gzip(gfe),gzip(gfe)
Complaints-To: groups-abuse@google.com
Injection-Info: n2g2000hse.googlegroups.com; posting-host=64.24.177.172;
Xref: news.mathworks.com comp.soft-sys.matlab:418866 sci.math:1030752 sci.stat.math:78238 sci.stat.consult:58910 sci.stat.edu:48357



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.