# Algorithm to go from a picture (or pictures) of a string in space, to a piecewise-linear representation of the curve

Say you have a knotted-up string or, as in this case, USB cable:

I am wondering to what extent there are algorithms that could turn a picture like this (or a succession of pictures of the same object) into a proper 3d mathematical representation of the object?

For example, I would be happy with a 1-dimensional polygon in $\mathbb R^3$ that describes the rough shape of a cable, given in a picture like the above. It would be useful if the algorithm could tell the difference between an "open" knot and a closed knot -- meaning the knot is a (possibly tangled) loop, vs just some length of string with free ends.

In the case of the above picture, I would be happy with output a list like:

$$(-2,0,0) \to (1,0.2,0) \to (1,-1,1) \to (-1,-1,-1) \to (-1,0.2,-1) \to (-1,0.2,1) \to (1,0,-0.2) \to (2,0,0)$$

from the algorithm. Roughly the $(x,y,z)$ coordinate corresponds to the picture with the x-axis horizontal, the y-axis vertical, and the z-axis would be into the table.

Are there any algorithms out there that are (?close?) to capable of such a task?

Apologies in advance if I am using inappropriate tags.

• "It would be useful if the algorithm could tell the difference between an "open" knot and a closed knot -- meaning the knot is a (possibly tangled) loop, vs just some length of string with free ends." That is asking for too much: en.wikipedia.org/wiki/Unknotting_problem – Tyson Williams Oct 26 '14 at 6:41
• Hmm, somehow there has been a misunderstanding. I'm not asking this algorithm to say anything about the unknotting problem. There are good algorithms for that problem already implemented nowadays. The Haken algorithm being one. My laptop has a nice implementation of it via the software Regina. In the above sentence you quote, I'm only asking for this algorithm to tell if the string has a start and an end, or if it is one continuous loop. Said another way, is it an embedded interval, or an embedded circle. – Ryan Budney Oct 26 '14 at 6:48
• Ic. That should be doable. – Tyson Williams Oct 26 '14 at 13:15
• If you are guaranteed to be given a raster image of either a loop or a simple curve and want to tell which, then trying to reconstruct the three-dimensional location of the whole curve sounds like an overkill to me. It is probably much easier to detect just the ends of the curve. (Disclaimer: I know nothing about image processing.) – Tsuyoshi Ito Oct 26 '14 at 13:36
• @Tsuyoshi: I suspect this is somewhere close to or a little beyond the state of the art in image processing nowadays. I'm asking the question to find out precisely where it sits. Thanks for the input. – Ryan Budney Oct 26 '14 at 14:50