Polygonizing a pixelated 2D curve

I have a bunch of pixelated binary curves (that is, the pixel is 1 if the curve runs over it and 0 otherwise), and I'm looking for an algorithm that can return a polygonal chain that approximates the curve well. The pixelated curves are usually only a pixel thin, and they are completely connected. I've looked over some literature for this, but my main problem seems to be that I don'开发者_运维问答t even know where the endpoints of my curves are.

Does anyone know of any algorithms that can do this in a reasonable amount of time? If it makes a difference, I'll be implementing this in MATLAB.

---

You might try looking at the Active Contours algorithm (or Snakes, if you prefer). http://en.wikipedia.org/wiki/Active_contour_model

It will try to find a locally optimal polygon, based on a score image. It will automatically deal with line segment length as the curve turns. Since you already have a binary image with your curves, that part should work well. It is not exactly suited to your problem, as it is usually designed to work with closed contours. However, I think it might work anyway (simply closing the polygon between the ends of the curves) or could be adapted. If your curves are very close together, it will probably not work as it seeks out local minimums and will easily get stuck.

It is not that fast, and requires decent initialization. If they are always completely connected, you might be better off stepping through them yourself, but that would probably mean starting from scratch.

You could start with an available toolbox (there are plenty of others): http://www.mathworks.com/matlabcentral/fileexchange/11643-active-contour-toolbox