How to join segments in Python?

Question

This question concerns the union of segments.

I have an array (a) composed of 10* 4 elements (which are the extremities of lines: (x1,y1,x2,y2)). If I draw these 10 segments (see image), there are actually 2 lines only (cause some lines are on top of each others or have a small length).

a = np.array([[40,33,54,4],[40,34,54,5], [41,34,55,5], [43,34,57,7], [18,85,34,52], [15,83,30,51], [16,84,33,52], [42,34,56,5], [16,83,32,51]])

To process this, I was thinking of taking the x1 and x2 positions of each line and then define segments. Similarly to what has been proposed, one could proceed as follows (finding unions of line segments on a number line).

For the first line (x1=40, x2=54), I could create a vector having 0 and 1 only, which would read: 00000.......0000001111....111100. That is 40 zeros, then 15 ones, and then 2 zeros. The length would be 57 as this is the largest x2 value.

I could proceeed like this for all lines.

Assuming three lines:

00011100000000

00000000001111

00111111000000

The result would be

00111111001111

And then I would know that there are two lines of length 6 (starting at 2) and 4 (starting at 10).

Is there an efficient to that in python ?

To create the array of 0 and 1 and I was doing :

import numpy as np

def array_zero_ones(x1, x2, xmax):
    # convert a segment into 0 and Ones
    arr = np.zeros(x1,dtype=np.bool)
    arr1 = np.ones((x2-x1+1),dtype=np.bool)
    arr2= np.zeros((xmax-x2),dtype=np.bool)
    arrall= np.concatenate([arr,arr1,arr2])
    return arrall


a = np.array([[3,33,6,4],[4,40,7,70], [9,98,11,111]])
max=np.max(a[:,2])

sum_array_all = np.zeros(max+1,dtype=np.bool)

for i in range(len(a)):
        sum_array_all =  sum_array_all + array_zero_ones(a[i,0],a[i,2],max)

print(sum_array_all)

#still need to find all non 1 values in this array

Not sure it is efficient.... Best,

W

Answer 1

Found the solution. Not sure it is very efficient but it works.

def return_segments_along_x_axis(arr):
    # array should be as [[13,33,14,4],[3,33,6,4],[4,40,7,70], [9,98,11,111],[14,98,16,111]]
    # I calculate the max of x2 for all those lines
    max=np.max(arr[:,2])
    # Array init
    sum_array_all = np.zeros(max+1,dtype=np.bool)
    # For the projection along the x axis, I assign TRUE if there is a segment at a given pixel
    # And then sum over all lines.
    # If I have those lines (along the x axis)
    #    ---    
    #      ----    
    #             ---
    # Then the value would be
    #    ------   ---
    for i in range(len(arr)):
        sum_array_all =  sum_array_all + array_zero_ones(a[i,0],a[i,2],max)
    # I then find the indexes of the True Values 
    array_ind_TRUE_index = np.where(np.r_[False, sum_array_all[1:] > sum_array_all[:-1]])[0]
    # Now I retrieve the length of the segment 
    # Init arrays
    arr_Length_TRUE = np.empty(shape=[0, 1])
    arr_lines_along_given_axis = np.empty(shape=[0, 2])
    # Loop
    for i in range(len(array_ind_TRUE_index)):
        temp_array_1 =sum_array_all[array_ind_TRUE_index[i]:]
        val_temp = (temp_array_1 !=True).argmax(axis=0)
        if val_temp == 0:
            val_temp = len(temp_array_1)
        arr_Length_TRUE =   np.append(arr_Length_TRUE,val_temp)
    #For a given direction, this gives (along the x axis), the x1 values and lengths of the segments
    arr_lines_along_given_axis = [[array_ind_TRUE_index[i], arr_Length_TRUE [i]] for i, i in zip(range(0,len(array_ind_TRUE_index)), range(0,len(array_ind_TRUE_index)))]
    return(arr_lines_along_given_axis)

Answer 2

You could use RANSAC to estimate straight line and get it from there. RANSAC is very simple and robust method, though non-deterministic. Unless your images are prone to noise, it should work fine for your case. There's example here. There's also great visual and intuitive explanationon wiki.