Detecting start and end point of line in image (numpy array)

Question

I have an image like the following:

What I would like is to get the coordinates of the start and end point of each segment. Actually what I thought was to consider the fact that each extreme point should have just one point belonging to the segment in its neighborhood, while all other point should have at least 2. Unfortunately the line does not have thickness equal to one pixel so this reasoning does not hold.

Answer 1

Here's a fairly simple way to do it:

• load the image and discard the superfluous alpha channel
• skeletonise
• filter looking for 3x3 neighbourhoods that have the central pixel set and just one other

---

#!/usr/bin/env python3

import numpy as np
from PIL import Image
from scipy.ndimage import generic_filter
from skimage.morphology import medial_axis

# Line ends filter
def lineEnds(P):
    """Central pixel and just one other must be set to be a line end"""
    return 255 * ((P[4]==255) and np.sum(P)==510)

# Open image and make into Numpy array
im = Image.open('lines.png').convert('L')
im = np.array(im)

# Skeletonize
skel = (medial_axis(im)*255).astype(np.uint8)

# Find line ends
result = generic_filter(skel, lineEnds, (3, 3))

# Save result
Image.fromarray(result).save('result.png')

---

Note that you can obtain exactly the same result, for far less effort, with ImageMagick from the command-line like this:

convert lines.png -alpha off -morphology HMT LineEnds result.png

Or, if you want them as numbers rather than an image:

convert result.png txt: | grep "gray(255)"

Sample Output

134,78: (65535)  #FFFFFF  gray(255)    <--- line end at coordinates 134,78
106,106: (65535)  #FFFFFF  gray(255)   <--- line end at coordinates 106,106
116,139: (65535)  #FFFFFF  gray(255)   <--- line end at coordinates 116,139
196,140: (65535)  #FFFFFF  gray(255)   <--- line end at coordinates 196,140

---

Another way of doing it is to use scipy.ndimage.morphology.binary_hit_or_miss and set up your "Hits" as the white pixels in the below image and your "Misses" as the black pixels:

The diagram is from Anthony Thyssen's excellent material here.

---

In a similar vein to the above, you could equally use the "Hits" and "Misses" kernels above with OpenCV as described here:

morphologyEx(input_image, output_image, MORPH_HITMISS, kernel);

I suspect this would be the fastest method.

---

Keywords: Python, image, image processing, line ends, line-ends, morphology, Hit or Miss, HMT, ImageMagick, filter.

Answer 2

The method you mentioned should work well, you just need to do a morphological operation before to reduce the width of the lines to one pixel. You can use scikit-image for that:

from skimage.morphology import medial_axis
import cv2

# read the lines image
img = cv2.imread('/tmp/tPVCc.png', 0)

# get the skeleton
skel = medial_axis(img)

# skel is a boolean matrix, multiply by 255 to get a black and white image
cv2.imwrite('/tmp/res.png', skel*255)

See this page on the skeletonization methods in skimage.

Answer 3

I would tackle this with watershed-style algorithm. I described method below, however it is created to deal only with single (multisegment) line, so you would need to split your image into images of separate lines.

Toy example:

0000000
0111110
0111110
0110000
0110000
0000000

Where 0 denotes black and 1 denotes white.

Now my implemention of solution:

import numpy as np
img = np.array([[0,0,0,0,0,0,0],
[0,255,255,255,255,255,0],
[0,255,255,255,255,255,0],
[0,255,255,0,0,0,0],
[0,0,0,0,0,0,0]],dtype='uint8')

def flood(arr,value):
    flooded = arr.copy()
    for y in range(1,arr.shape[0]-1):
        for x in range(1,arr.shape[1]-1):
            if arr[y][x]==255:
                if arr[y-1][x]==value:
                    flooded[y][x] = value
                elif arr[y+1][x]==value:
                    flooded[y][x] = value
                elif arr[y][x-1]==value:
                    flooded[y][x] = value
                elif arr[y][x+1]==value:
                    flooded[y][x] = value
    return flooded

ends = np.zeros(img.shape,dtype='uint64')

for y in range(1,img.shape[0]-1):
    for x in range(1,img.shape[1]-1):
        if img[y][x]==255:
            temp = img.copy()
            temp[y][x] = 127
            count = 0
            while 255 in temp:
                temp = flood(temp,127)
                count += 1
            ends[y][x] = count

print(ends)

Output:

[[0 0 0 0 0 0 0]
 [0 5 4 4 5 6 0]
 [0 5 4 3 4 5 0]
 [0 6 5 0 0 0 0]
 [0 0 0 0 0 0 0]]

Now ends are denoted by positions of maximal values in above array (6 in this case).

Explanation: I am examing all white pixels as possible ends. For each such pixel I am "flooding" image - I place special value (127 - different than 0 and different than 255) and then propogate it - in every step all 255 which are neighbors (in von Neumann's sense) of special value become special values themselves. I am counting steps required to remove all 255. Because if you start (constant velocity) flooding from end it would take more time than if you have source in any other location, then maximal times of flooding are ends of your line.

I must admit that I did not tested this deeply, so I can't guarantee correct working in special case, like for example in case of self-intersecting line. I am also aware of roughness of my solution especially in area of detecting neighbors and propagation of special values, so feel free to improve it. I assumed that all border pixels are black (no line is touching "frame" of your image).