As it seems you have the time-parametrized dynamics on the plane. See it as path given by some dynamical system whose solution is the pair {y=y(t); x=x(t)} and NOT as a function Y=Y(X).

Try to fit/smooth separately X(T) and Y(T), be aware that the discrete parametrization for both functions should be linearly depended to not introduces more complexities (I just use the fixed width steps of higher precision) and plot it parametrically

http://www.mathworks.it/it/help/matlab/ref/plot.html

http://msg.byu.edu/matlab/node21.html

In this case you obtain a smooth path on the plane that can be nicely studied for stationary point, inflections, maxima and minima.

EDIT 1

T is not necessarily time, it is used to call "time" that is the common to all functions independent parameter. In your case it could be the index (i). You have a set of point on the plane (X_i, Y_i), try to plot (i, X_i) and (i, Y_i) as a function of (i) and work with these functions directly. Smooth them, make an analysis of periodicity etc.

EDIT 2

Question: Tobias could you share the full data set of the boundary of the cell, I'd play with it in my spare time, of course if it is public? As I see, it could be related to so called "Jordan curve" and algorithms around it.

For me it looks like time series data, becouse you have reapeated value of data...

For starters, a series of points is non-continuous by definition. Tell us more about your task so we can help you.

What are your X and Y variables?

Is your data really of the type y=f(x)? If so, the overhangs represent some significant error.

Or is it (x,y)=f(t)? If so, the overhangs are not an issue at all.

Either way, you need to decide what type of curve you want to fit to your data. Why don't you just keep the spline function you have already fitted to it?

MatLab

yy = spline(x,Y,xx) uses a cubic spline interpolation to find yy, the values of the underlying function Y at the values of the interpolant xx

yi = pchip(x,y,xi) returns vector yi containing elements corresponding to the elements of xi and determined by piecewise cubic interpolation within vectors x and y

Optimization Toolbox software extends the capability of the MATLAB numeric computing environment.

But I think the problem is that the data is not sorted.

As it seems you have the time-parametrized dynamics on the plane. See it as path given by some dynamical system whose solution is the pair {y=y(t); x=x(t)} and NOT as a function Y=Y(X).

Try to fit/smooth separately X(T) and Y(T), be aware that the discrete parametrization for both functions should be linearly depended to not introduces more complexities (I just use the fixed width steps of higher precision) and plot it parametrically

http://www.mathworks.it/it/help/matlab/ref/plot.html

http://msg.byu.edu/matlab/node21.html

In this case you obtain a smooth path on the plane that can be nicely studied for stationary point, inflections, maxima and minima.

EDIT 1

T is not necessarily time, it is used to call "time" that is the common to all functions independent parameter. In your case it could be the index (i). You have a set of point on the plane (X_i, Y_i), try to plot (i, X_i) and (i, Y_i) as a function of (i) and work with these functions directly. Smooth them, make an analysis of periodicity etc.

EDIT 2

Question: Tobias could you share the full data set of the boundary of the cell, I'd play with it in my spare time, of course if it is public? As I see, it could be related to so called "Jordan curve" and algorithms around it.

Is it really like THAT?

I mean, in some points the curve goes back in x, so that a simple, univocal f(t) will not do the job.

But what about looking if the missing parts have some periodicity? You could then sample periodically using a few existing points, then all possibilities are open.

I hate to get into the weeds here, but 1) what is your hypothesis, 2) what did you measure and graph, and 3) how does it relate to your hypothesis? Only then can I give advice. One of our engineers had an office that was too hot, so he got a thermo-sensor and took the temperature of his office every 10 minutes. The sawtooth graph that showed the temperature spiking over 80 Fahrenheit in the afternoon several times was enough to convince management there was a heating problem. How you make your "picture" depends on the problem you are facing.

MATLAB - cftool

and in 'type of fit', choose - 'sum of sine functions'. Then play with it for different number of sums and terms.

i am sure you'll get what you want. gud luck

I would use a simple greedy algorithm which removes the most "noisy" points one by one.

That is

1) you start with all points

2) evaluate the points by assigning them "noise" values (define by yourself)

3) remove the point with the most "noise" value

4) repeat step 2 & 3 until either a wanted number of points is reached, or the total noise is acceptable.

So, by trying different "noise" functions and algorithm settings you can "your" wanted result.

@ Leszek Luchowski

"Either way, you need to decide what type of curve you want to fit to your data. Why don't you just keep the spline function you have already fitted to it? "

Thank you for the answer! Unfortunatelly the spline function give me funny jups at the first part of the curve. This is not reliable enough. At other parts it worked well to straighten out the overhangs. But I would rather not straighten it out, only if neccessary.

"Or is it (x,y)=f(t)? If so, the overhangs are not an issue at all."

I don't understand. The most important thing for me is knowing the shape and being able to seperate the individual bumps. How could I do that in an 2D plane? How do you define maxima, minima etc?

Fitting splines to image data reminds me of "snakes: active contour models". You can also search for spline fitting algorithms (the articles of de Boor, and Dierckx book)

Not sure- perhaps RBF use and reduction of Lambdas. Or RBF approximation. Vaclav

I am not suggesting a method to exactly solve your problem but essentially doing some loud thinking. I hope this helps you. Basically what is the process which is generating the data points? in ideal form and then with noise? what assumptions can be made about the noise? The physical laws of the process which generates the points should certainly suggest what can be a good way to fit nice functions. The idea of fitting polynomial functions f(x,y) can also be extended to fitting rational functions f(x,y)/g(x,y). Moreover the models of fractals and map iterates show that even a very simple rational map when iterated can produce very complex patters. If any of these dont help I dont know whether you can use muti-dimensional analogs of predictive coding to represent the data. In this method you have formulate a model of a systems whose response to random noise is best fit for the data.

You could also try penalized B-splines. These are probably available in your software package.

I have actually published an article on that kind of problem. What helped us in this situation was splines with an optimization procedure to position the nodes.

Schleicher, J. & Biloti, R., A frequency criterion for optimal node selection in smoothing with cubic splines. Geophysical Prospecting, v. 56, p. 229-237, 2008.

This is a really interesting problem. There are a lot of ways you could analyze the data, the first and easiest for a single image would be to do your measurements by hand. However if you have a lot of these images and want to objectively measure the periodicity etc., you will have to handle the "non-functionality" of your image. It looks like you are trying to pose y as a function of x; however, it doesn't meet the function requirement that each input evaluates to only one output (the vertical line test). Thus standard curve fitting tools don't apply directly. So to handle this you could break the image into smaller images and rotate the subimages to best meet the input-output requirement, and then do a smaller curve fitting on each of the sub images.

For the criteria you are looking for I would consider using either the wavelet transform of short time Fourier transform.

Alternatively, if you can pose another dimension on the data such as length, you could then pose the data as a function of length and you could possibly analyze the x and y dimensions separately.

My bio points to several papers that deal with shape preserving curve fitting. Look them over and let me know if anything appears to be relevant.

In the help of Matlab you are going to find how to approach a polynomial function to a data.The fit depends of the grade that you place for the polynomial function.http://www.mathworks.com.au/help/matlab/ref/polyfit.html

Interesting question

It make me think to issues in fractal analysis (how much does a curve fill a plane). You could look for indices of fractal dimension and probably find some of interest. You can make a first trial with the (free) ImageJ software (in ImageJ see Analyse->Tools->option ->fractal Box).

Also, it is tempting to consider the figure that you would obtain if you put disks (of a given diameter d ) centered on each of the points of your original data. And progressively change diameter d. For some values of the diameter you would fill all the area enclosed by bumps and this diameter would represent a measure of the distance between bumps. Also you could fine some value of the diameter that represents the amplitude of the bumps.

You should try to assess a measure of self-similarity before choosing a technique

Tobias,

I looked at the picture and I have the following questions:

1) I am seeing blue lines completing the shape. Wouldn't the omission of that cell membrane surface (i am assuming it is something along those lines) impact your analysis?

2)Have you taken into account that previous to edge detection there is usually a smoothing process which might erase possible information(for example, possible receptor sites)?

You probably have taken these into account, but just making sure.

I could offer suggestions but they would probably not serve you any good unless as Monika mentioned, we know the Hypothesis and what you are trying to achieve.

Try maybe http://zunzun.com/

In any case it is a great sofwtare useful for everyone !

Tobias, I would follow Igor Moiseev's advice. I understand that your set of points in reality is a "continuous" set, just a pixelized image, in other words a discretized curve. What if you rotate this picture? What happens to minima and maxima then? This is not a malicious question, its purpose is to show the problems with clear understanding what are your "bumps". Having a parametrized description of your object, exactly like Igor suggests, makes possible to calculate curvature of your line. Or, maybe even better, you can think of consecutive points on this line as of trajectory of, say, a bacteria following it. In Igor's picture it is straightforward to calculate the velocity and/or acceleration of the said bacteria (both as vectors, assuming |v| = const). I would identify then the points on a line characterized by acceleration being perpendicular to the given trajectory ("turning points") with what you call extrema or bumps.

You can use Genetic Algorithms and Artificial Neural Networks

Why not try the frequency domain? You could get a measure of the fundamental frequency and its spectrum even with discontinuities in behaviour.

@ Tobias Wenzel:

First of all, please help us all help you by telling us what your "x" and "y" are and how they are measured. We're all trying to guess what exactly you are doing.

TW: @ Leszek Luchowski

TW: "Or is it (x,y)=f(t)? If so, the overhangs are not an issue at all."

TW: I don't understand. The most important thing for me is knowing the shape and being TW: able to seperate the individual bumps. How could I do that in an 2D plane? How do TW: you define maxima, minima etc? "

As Joanna Wachnicka pointed out, your curve is a "non-function" - it does not look like a proper case of y=f(x), even though you are trying to present it that way. It looks more like x=f(t) and y=g(t), with f being close to a linear function - but not actually linear, or even monotonous. That would explain your overhangs.

If you are looking for maxima (of y, presumably), you can find them by ignoring x completely and just analyzing y=g(t), if you have access to it. If you don't have the actual values of t to go with your samples, you can still parametrize your curve as x=f(u), y=g(u), u being a purely virtual parameter (possibly position measured along the curve) and not real time. Then, again, look for the maxima of g.

Forcing the approximating curve to be a function in the sense of y=f(x) may badly distort the process you are studying, because you will be suppressing a possibly important aspect of it.

Thank you for the added clarifications. As it's the shape of a cell, there is no reason why it should follow the principle of y=f(x), i.e. "no overhang". Parametrizing the curve as x=f(u) and y=g(u), with u=(position along the curve), seems to be a good option (note that I am not saying "the best").

Before you can measure the "heights" and "widths" of each bump, you need to think carefully about defining them.

In your picture, it seems obvious to measure the "height" vertically, i.e. in the "y" dimension, starting from some imaginary baseline passing more or less horizontally through the bottoms of the "valleys" (for lack of a better word) between the bumps. I suppose this baseline will actually be the outline of the cell without the "bumps". However, the general outline of a whole cell must, by definition, be a closed curve. What is the scale? Are the bumps so small, compared to the whole cell, that you can treat the cell locally as being flat - just like we don't think about the curvature of the Earth when we measure the height of a tree?

As for the width of the bumps - some of them seem to have a "neck" and a "head" - a narrower part closer to the base, topped by a broader part. For those, the width of the "head" is _relatively_ easy to define. However, others look more like Gaussian curves, and their broadest part will be at the base. It is not obvious at what height you want to measure their width, and the choice of that height will very strongly influence your result. Remember that the "width" of an actual Gaussian, at height zero, is infinite.

"Halfwidth" point locations can be easily detected as those where the vector product of acceleration and the line changes sign (i.e. its z-component changes sign).

To me it looks like you shouldn't get hung up on finding a fancy fitting method. The salient features are the length and width and these can be determined by eye with a ruler. Just get the average length and width. Assuming these are microvilli you may find this interesting:

http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2747329/

The authors developed a model of microvilli extension during leukocyte rolling on endothelium.

Please find the files attached that I announced in the 2nd edit to my question. Thank you for beeing interested!

The attachements are:

-> An X,Y array containing the non-scaled example data points I used.

... and the second attachment:

-> A colored version of the graph in my question to demonstrate the cell-cut and a free-hand red line showing that the small defects in the path are not biologically relevant because they were introduced by the edge detection and microscopy artefacts.

Sorry, I misunderstood the problem in the first place.

Lowpass filtering the y(t) data (I chose t=1:1221 in ms) at omega=0.2 Hz yields the attached graph. Red crosses are original data points, blue line is smoothed curve. Is this more or less what you had in mind?

(Of course, the ends are distorted because FFT assumes periodic data. Adding a few extra data points that simulate that property will improve the result. The same trick can also be used to improve the interpolated curve in the gaps.)

Hi, to fit a curve to non continuously data points I use Principal Componen Analysis. Here is a tutorial for 3D data, I guess it can be used for 2D? not sure, but anyway... hope it helps somehow

Have you considered using a piecewise cubic Hermite interpolating polynomial (PCHIP)? There is a built-in MATLAB function that I have used with success many times for problems involving curve-fitting of points that represent functions that are discontinuous or that have discontinuities in their derivatives. It is very easy to try if you have MATLAB.

Could you just publish your set of points, i.e., values?

Tobias,

Indeed, your data are not well sorted. Therefore they are not suitable for path-tracking approach suggested above. Did you look closer at your data? Here is a small part, shown as points and line segments connecting allegedly "consecutive" points.

Indeed, also for the lowpass I applied, I had to sort the data first. Fortunately, a simple sorting by distance proved sufficient, with the exception of one single data point that I then corrected by hand.

Hey Tobi,

I did a similar thing like Jörg Schleicher. But instead of simply cutting off the high frequencies in the FFT, I convolve the (sorted) data with a filter function.

So the steps I did (in Python) are:

1) sort data by distance

2) convolve x(t) and y(t) separately with window function (I used a Hann function)

3) find local extrema

It should be quite easy to find the local extrema. You probably find solutions in the web. As you use MATLAB you could use this script for example: http://www.billauer.co.il/peakdet.html

If you have further questions, just ask me in real life ;-)

If you are doing 2D, I like 'gridfit' by John D'Errico, it is on the Mathworks site. It allows you to surface plot a nice fit for regular and irregular (x,y) points. Think of a rubber sheet over your data where you control the elasticity.

Hi Tobias,

if I am not mistaken, you could get a good representation just using some modifications of spline algorithms, e.g. using Matlab: http://www.mathworks.it/it/help/curvefit/spapi.html

Did you try it?

Have tou tried an approximate function with nonlinear least squares. Can do that easily with excel solver.