6

I have an image made up of lines; how can I find the endpoints with OpenCV?

The lines are about 20 pixels wide. They turn, branch, and can be at angles (although mostly horizontal and vertical). Note that Hough won't work because my lines aren't straight. (Maybe that makes them contours?)

I looked at this answer but it finds extreme points, not endpoints. I looked at this, but I think goodFeaturesToTrack() will pick up corners too. Maybe use a thinning algorithm, although OpenCV doesn't seem to have one?

The image below shows sample input (blue) and the desired endpoints (magenta).

Lines with endpoints marked

Community
  • 1
  • 1
Ken Shirriff
  • 1,654
  • 16
  • 20

4 Answers4

5

I speak Chinese, while my English is poor.

So I just post my core steps.

A general way to find endpoints of lines is:

  1. Binary the gray image.
  2. Find the skeleton of the binary image.
  3. Do hit-miss operation (all end points) or goodFeaturesToTrack(all corners include endpoints) on the skeleton.

Notice:

You should select a good skeleton method to make sure that the endpoints wouldn't shrink(while my example does shrink).

This is the result.

enter image description here

This is a demo using hit-miss to find special points. enter image description here

Kinght 金
  • 17,681
  • 4
  • 60
  • 74
4

You can create a morphological skeleton (thinning algorithm which you talked about) as described here, my implementation of this is here. Then you can traverse the skeleton(s) and just look for the end of it in every way.

Aleksander Grzyb
  • 749
  • 1
  • 6
  • 18
  • Thank you for the response. I tried the described algorithm and it almost worked, but there are two issues. First, the skeleton has gaps, which will complicate finding the ends. Second, it produces "tentacles" at the corners. I could solve the second problem by using 8-way connectivity (MORPH_RECT instead of MORPH_CROSS), but the gaps get worse. – Ken Shirriff Feb 15 '17 at 01:36
  • 3
    The skeletonization function proposed by Aleksander Grzyb is a very trivial implementation and unfortunately it will have this issue. Try skeletonization using hit or miss transform like in the article I referred or you can use some more sophisticated algorithms (plenty of them are freely avalible as code snippets). By the way, I have a book where the exact problem you have is solved using hit or miss transform. – Max Walczak Feb 15 '17 at 12:26
  • 1
    Idea proposed by @MaxWalczak seems very promising. I will look into to it later today. To get rid off the gaps I think you could use `findContour` as described [here](http://answers.opencv.org/question/53548/gap-filling-contours-lines/) (I didn't check if it works). – Aleksander Grzyb Feb 15 '17 at 16:27
  • I uses Zhang-Suen thinning, which thinned without any problems. It was glacially slow, though, hundreds of times slower than the algorithm @AleksanderGrzyb mentioned. (Probably because it iterates over the image pixels rather than using OpenCV functions.) But it gave me the output I needed and then finding endpoints was straightforward. Zhang-Suen algorithm was at http://stackoverflow.com/questions/8080383/a-fast-thinning-algorithm – Ken Shirriff Feb 15 '17 at 16:57
  • 1
    The Zhang-Suen implementation attached below is very inefficient because of using .at operator which performs quite a lot of checks before returning desired value. Zhang-Suen thinning is a relatively simple and very fast thinning algorithm which can also be paralellized. A much faster implementation of Zhang-Suen would be to use LUT function from OpenCV library. – Max Walczak Feb 16 '17 at 09:24
  • @MaxWalczak you mentioned a book in one of the above comments. Can you please tell the book title? Sounds like an interesting read. Thanks. – Nejc Feb 19 '17 at 12:52
  • @Nejc, the book title is "Hands on Morphological Image Processing" by E. R. Dougherty and R. A. Lotufo. A very similar example to your question is given on page 88. You should be able to find and read it on Google Books. – Max Walczak Feb 20 '17 at 13:45
2

The easiest way for me would be to thin the image to 1px thickness and then use hit and miss transform to detect the endpoints. Unfortunately, none of these functions are implemented in OpenCV. Thinning can also be obtained with hit or miss transform. All you need is thoroughly described in the following link: http://homepages.inf.ed.ac.uk/rbf/HIPR2/thin.htm

Let me know if you have any problems with this, as I have it all implemented. Hit or miss transform might be really old and simple, but it's a very powerful tool.

Max Walczak
  • 433
  • 2
  • 12
  • Any code links for quick try? – Shiv Tavker May 08 '22 at 20:16
  • The kernels are given in the linked page which still works. You can just use these kernels with OpenCV morphology methods as described here: https://docs.opencv.org/4.x/d9/d61/tutorial_py_morphological_ops.html – Max Walczak May 09 '22 at 13:55
1

If your endpoints are always either horizontal or vertical you can also try to convolve the image with a simple kernel - square (side should be equal to your line width) with background (width should be equal to minimal distance between neighboring endpoints). Color (or intensity) of square and background should match those on your images.

In this case endpoints would "match" the kernel along 3 "sides", line segments and corners along "2 sides", other shapes should have a weaker response. By thresholding response appropriately you should be able to get endpoint locations.

This approach should be simpler and faster (if implemented appropriately) than the one you settled on currently, but it may have some quirks depending on the input. Unfortunately, I don't have time to try implementing it.

alexisrozhkov
  • 1,623
  • 12
  • 18