[Python] Hough Transform algorithm for pattern recognition of straigth lines form points

Hello everyone, I'm currently working on different algorithms which could give me the patterns of straight lines within groups of aligned cells.

Let me explain:

Suppouse we have a XY plane which is 200(x) per 30(y).

I'm given a bunch of points which mark the center of the cells (in xy coordinates) and my mission is to obtain patterns of points which form a straight line through that cells.

Points placed in xy plane

Patterns must be a group of 8 points: [[point1],[point2],[point3],...[point8]] or a group of 4 if there is no group to pair with.

Patterns of possible straight lines through the points

Straight lines can only have from -50º to 50º of gradient.

For example:

Hit's Y coordinates:

[0.65, 0.65, 0.65, 0.65, 0.65, 1.9500000000000002, 1.9500000000000002, 1.9500000000000002, 1.9500000000000002, 3.25, 3.25, 3.25, 3.25, 3.25, 4.550000000000001, 4.550000000000001, 4.550000000000001, 4.550000000000001]


Hit's X coordinates:

[77.7, 107.1, 191.1, 195.3, 123.9, 79.80000000000001, 109.2, 193.2, 126.00000000000001, 77.7, 111.3, 195.3, 123.9, 128.1, 79.80000000000001, 109.2, 197.4, 126.00000000000001]


Points would be [77.7,0.65],[107.1,0.65]... etc

So my first thought was to implement some kind of Hough Transform which would give me back an accumulator with the rho and theta values of the points with more " votes ".

This is the code:

puntos_y=[0.65, 0.65, 0.65, 0.65, 0.65, 1.9500000000000002, 1.9500000000000002, 1.9500000000000002, 1.9500000000000002, 3.25, 3.25, 3.25, 3.25, 3.25, 4.550000000000001, 4.550000000000001, 4.550000000000001, 4.550000000000001]
puntos_x=[77.7, 107.1, 191.1, 195.3, 123.9, 79.80000000000001, 109.2, 193.2, 126.00000000000001, 77.7, 111.3, 195.3, 123.9, 128.1, 79.80000000000001, 109.2, 197.4, 126.00000000000001]

#ANGLE VALUES (50º MAX )
thetas = np.deg2rad(np.arange(-50,50))
#PLANE WIDTH,HEIGHT XY
width, height = 200,30
#DIAG FOR ACCUMULATOR
diag_len = float(np.ceil(np.sqrt(width * width + height * height))) # max_dist
#LINSPACE DE RHOS
rhos = np.linspace(-diag_len, diag_len, int(2*diag_len))

# STORE SOME VALUES
cos_t = np.cos(thetas)
sin_t = np.sin(thetas)
num_thetas = len(thetas)
num_rhos = len(rhos)

# ACcumulador (ARRAY THETA VS RHO)
accumulator = np.zeros((int(2*diag_len), num_thetas))

#POINTS
y_idxs, x_idxs = puntos_y, puntos_x

# ACCUMULATOR VOTES
for i in range(len(x_idxs)):
x = x_idxs
y = y_idxs

for t_idx in range(num_thetas):
# START CALCULATING RHO VALUES. DIAG_LEN FOR POSITIVE INDEX
rho = round(x * cos_t[t_idx] + y * sin_t[t_idx] + diag_len )
accumulator[int(rho), int(t_idx)] += 1





def votos_max(accumulator, thetas, rhos):
#FINDS MAX VOTES IN ACCUMULATOR
idx = np.argmax(accumulator)
rho = rhos[int(idx / accumulator.shape[1])]
theta = thetas[idx % accumulator.shape[1]]

return idx, theta, rho

#FINDS GRADIENT FOR A THETA
def sacar_pendiente(theta):
return np.cos(theta) / np.sin(theta)

#FINDS Y WHEN X=0
def sacar_n(theta, rho):
return rho / np.sin(theta)


This code gives me an accumulator array with the senoids for each point in the list. Where this points intersect is where the gradient of the straight lines is the same for each group of points.

Hough accumulator of points

THE PROBLEM IS: As you can see, points do not make an exact straight line. They are arranged in the xy plane almost aligned but not exactly, that is why you can see in the accumulator various highly voted points instead of only one per 2 groups of points.

So I can imagine the pattern when i see it graphicaly like this:

Patterns recognized

I would love to find some way of improving this accumulator, maybe some way of changing the threshold so in the accumulator each group of points is seen as a BIG POINT ( i dont know if I'm explaining this very well) is like when you were a kid and made the points bigger so the line could fit.

Some way of reducing the preccision of the straight line to the point of the program considering each group of 4 points like they are totally aligned, which will of course derive in having only one "most voted" (RHO,THETA) point in the accumulator array, which then i would be able to extract its coordinates and create the pattern easily.

Is there any way of improving this? Maybe I should try other type of algorithm as pattern recognitor for points and straight lines?

PD: Sorry if I'm not explaining myself correctly.

Continue reading...