4
$\begingroup$

Let's say you have pixel bitmaps that look something like this: example snake

From this I can easily extract a contour, which will be a concave polygon defined by a set of 2D points. The question is what is the fastest algorithm to pick, from the set of polygon points, the ones that are closest to the natural "endings" of the contour (i.e. the two tips at the end of the U in this case) - so there are $2$ points in the output.

Somehow it looks like it should be related to curvature, although the algorithm should support a large variety of possible shapes, including S, W and other largely curved shapes so I'm hesitant to set any kind of threshold on curvature.

I've tried convex hull methods as well as a couple of variations of the rotating calipers method but still I've found nothing that will convince me that I can reliably and quickly identify the endings/tips of any curved thin line. It's always impressive how humans can pick up on these natural features so fast!

Improve this question
$\endgroup$
2
  • $\begingroup$ Maybe it was not clear from the question, but I do have the concave hull of the data, which is represented as a 2D polygon that traces the black region. However, what I need is from that concave hull extract only two points: the "natural endings" of the shape (i.e. those that humans point out as natural, such as the tips of C, S, W and other curved shapes). I'm trying to define formally what is special about these points, and struggling... $\endgroup$
    – glopes
    Jun 28, 2016 at 5:20
  • $\begingroup$ The expected output is always 2 points, the two endings of the curve. For the case of W, it would also be 2. It is a challenging case because of the curvature in the extra bends. $\endgroup$
    – glopes
    Jun 28, 2016 at 5:49

3 Answers 3

Reset to default
2
$\begingroup$

Run Flood Fill from any point and the farthest points in the both directions are your result. If you find that the distance in one of the directions is zero it means that it was one of them.

Exploiting the very same idea, if you try finding pixels with the least number of surrounding pixels and apply limited BFS Flood Fill to find out where it can go - at the endpoints there is only one way out. Also going by curvature and then applying the same idea would tell apart the extra bends from results.

Improve this answer
$\endgroup$
1
$\begingroup$

Compute the topological skeleton of the black pixels. This will form a curved line one pixel wide (i.e., it will be isomorphic to a line). Use the two endpoints of this line as your answer. You can find the endpoints by using depth-first search, or (for a more robust solution) by computing the tangent line at each point $p$ and checking for a neighbor connected to $p$ near both sides of the tangent line.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I had actually tried this solution before but found it not very robust... the problem is that the topological skeleton algorithm itself is not perfect (as you can even see from the Wikipedia example) which then forces you to deal with thresholds that can vary for different inputs (W vs C vs U). $\endgroup$
    – glopes
    Jun 29, 2016 at 1:42
  • 1
    $\begingroup$ @glopes, OK, that's good to know! For future reference: when asking a question, we'd prefer that you tell us in the question what approaches you've already tried or rejected (so we don't suggest something you have already tried). Does the line have a fairly constant width? (I'm guessing not, but just checking.) $\endgroup$
    – D.W. ♦
    Jun 29, 2016 at 3:35
  • $\begingroup$ Not really... yeah, I tried to list all of the methods I've tried, but forgot to include the topological skeleton. It didn't work good enough to get stuck in my mind I guess. I tried throwing a bunch of things at this problem and nothing really robust enough... kind of drives you crazy how easy we humans solve this! $\endgroup$
    – glopes
    Jun 29, 2016 at 4:58
1
$\begingroup$

Build a graph, with one vertex per black pixel, and an edge between two pixels if they are adjacent. Compute all-pairs shortest-path distances $d(x,y)$. For each vertex $x$, compute

$$f(x) = \max \{d(x,y) : y \in V\}.$$

Find the vertex (pixel) $x$ with the maximum score for $f(x)$. This will be one endpoint of the shape. Find the other vertex $y$ that maximizes $d(x,y)$. This will be the other endpoint of the shape.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is this formally equivalent to @Evil's answer below? It looks like flood fill might be the equivalent of traversing this graph. Basically I'm wondering if both methods have the same time complexity. $\endgroup$
    – glopes
    Jun 29, 2016 at 6:21
  • $\begingroup$ @glopes, I don't know. It's not equivalent in general for arbitrary shapes, though it might be equivalent for shapes that are a thin line with no "junctions" (I'm not 100% sure). $\endgroup$
    – D.W. ♦
    Jun 29, 2016 at 6:41
  • $\begingroup$ Yes, this is equivalent. Exactly for all inputs. 4-connected floodfill will run differently (it will not follow 1px diagonals) but 8-connected is perfectly the same (with difference in description @D.W. made it formal). And possibly in runtime - in my crude method measure distance while traversing, with floodfill to convert pixels to graph - it is faster. $\endgroup$
    – Evil
    Jul 3, 2016 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.