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

<p><img src="https://i.sstatic.net/dJdFk.jpg" alt="knotted USB cable"></p>

<p>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? </p>

<p>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. </p>

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

<p>$$ (-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) $$</p>

<p>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. </p>

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

<p>Apologies in advance if I am using inappropriate tags. </p>

CC BY-SA 3.0
2014-10-26T06:41:02.983Z
"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: http://en.wikipedia.org/wiki/Unknotting_problem
Tyson Williams
CC BY-SA 3.0
2014-10-26T06:48:22.617Z
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
CC BY-SA 3.0
2014-10-26T13:15:03.200Z
Ic. That should be doable.
Tyson Williams
CC BY-SA 3.0
2014-10-26T13:36:09.560Z
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
CC BY-SA 3.0
2014-10-26T14:50:34.320Z
@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
<cv.computer-vision><image-processing>
Algorithm to go from a picture (or pictures) of a string in space, to a piecewise-linear representation of the curve
Ryan Budney
# Algorithm to go from a picture (or pictures) of a string in space, to a piecewise-linear representation of the curve

(Asked by: username_0 on 2014-10-26)

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

![knotted USB cable](https://i.sstatic.net/dJdFk.jpg)

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.

**Tags:** cv.computer-vision, image-processing
> **Comments:**
> **username_1**: "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: http://en.wikipedia.org/wiki/Unknotting_problem  
> **username_0**: 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.  
> **username_1**: Ic. That should be doable.  
> **username_2**: 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.)  
> **username_0**: @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.  

---

## 0 answers

