-
Notifications
You must be signed in to change notification settings - Fork 0
/
Hough.py
270 lines (216 loc) · 10.3 KB
/
Hough.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
import numpy as np
import cv2 as cv
import math
from PIL import Image
import matplotlib.pyplot as plt
# from libs import helper
from collections import defaultdict
def hough_peaks(H, peaks, neighborhood_size=3):
"""Calculate the indices of the peaks.
Args:
H: the accumulator
peaks: number of line peaks.
neighborhood_size (int, optional): the size of the region to detect 1 line within. Defaults to 3.
Returns:
indices (np.ndarray): the indices of the peaks.
H: accumulator that holds only the line points.
"""
indices = []
H1 = np.copy(H)
# loop through number of peaks to identify
for i in range(peaks):
idx = np.argmax(H1) # find argmax in flattened array
H1_idx = np.unravel_index(idx, H1.shape) # remap to shape of H to be 2d array
indices.append(H1_idx)
idx_y, idx_x = H1_idx # separate x, y indices from argmax(H)
# if idx_x is too close to the edges choose appropriate values
if (idx_x - (neighborhood_size / 2)) < 0:
min_x = 0
else:
min_x = idx_x - (neighborhood_size / 2)
if (idx_x + (neighborhood_size / 2) + 1) > H.shape[1]:
max_x = H.shape[1]
else:
max_x = idx_x + (neighborhood_size / 2) + 1
# if idx_y is too close to the edges choose appropriate values
if (idx_y - (neighborhood_size / 2)) < 0:
min_y = 0
else:
min_y = idx_y - (neighborhood_size / 2)
if (idx_y + (neighborhood_size / 2) + 1) > H.shape[0]:
max_y = H.shape[0]
else:
max_y = idx_y + (neighborhood_size / 2) + 1
# bound each index by the neighborhood size and set all values to 0
for x in range(int(min_x), int(max_x)):
for y in range(int(min_y), int(max_y)):
# remove neighborhoods in H1
H1[y, x] = 0
# highlight peaks in original H
if x == min_x or x == (max_x - 1):
H[y, x] = 255
if y == min_y or y == (max_y - 1):
H[y, x] = 255
# return the indices and the original Hough space with selected points
return indices, H
def hough_lines_draw(color,img, indices, rhos, thetas):
"""Draw lines according to specific rho and theta
Args:
img (np.ndarray): image to draw on
indices: indices of the peaks points
rhos: norm distances of each line from origin
thetas: the angles between the norms and the horizontal x axis
"""
for i in range(len(indices)):
# get lines from rhos and thetas
rho = rhos[indices[i][0]]
theta = thetas[indices[i][1]]
a = np.cos(theta)
b = np.sin(theta)
x0 = a * rho
y0 = b * rho
# these are then scaled so that the lines go off the edges of the image
y1 = int(y0 + 1000 * (a))
x1 = int(x0 + 1000 * (-b))
y2 = int(y0 - 1000 * (a))
x2 = int(x0 - 1000 * (-b))
if color =='Red':
cv.line(img, (x1, y1), (x2, y2), (255, 0, 0), 2)
elif color =='Blue':
cv.line(img, (x1, y1), (x2, y2), (0,0,205), 2)
elif color == 'Green':
cv.line(img, (x1, y1), (x2, y2), (50,205,50), 2)
def line_detection(image: np.ndarray,T_low,T_upper):
"""Fucntion that detects lines in hough domain
Args:
image (np.ndarray())
Returns:
accumulator: hough domain curves
rhos: norm distances of each line from origin
thetas: the angles between the norms and the horizontal x axis
"""
grayImg = cv.cvtColor(image, cv.COLOR_BGR2GRAY)
blurImg = cv.GaussianBlur(grayImg, (5,5), 1.5)
edgeImg = cv.Canny(blurImg, T_low, T_upper)
height, width = edgeImg.shape
maxDist = int(np.around(np.sqrt(height**2 + width**2)))
thetas = np.deg2rad(np.arange(-90, 90))
rhos = np.linspace(-maxDist, maxDist, 2*maxDist)
accumulator = np.zeros((2 * maxDist, len(thetas)))
for y in range(height):
for x in range(width):
if edgeImg[y,x] > 0:
for k in range(len(thetas)):
r = x * np.cos(thetas[k]) + y * np.sin(thetas[k])
accumulator[int(r) + maxDist, k] += 1
return accumulator, thetas, rhos
def hough_lines(T_low,T_high,neighborhood_size,color,source: np.ndarray,peaks):
"""detect lines and draw them on the image
Args:
source (np.ndarray): image
peaks (int, optional): number of line peaks. Defaults to 10.
Returns:
image: image with detected lines
"""
src = np.copy(source)
H, thetas, rhos = line_detection(src,T_low,T_high)
indicies, H = hough_peaks(H, peaks, neighborhood_size)
hough_lines_draw(color,src, indicies, rhos, thetas)
plt.imshow(src)
plt.axis("off")
plt.savefig("images/output/hough_line.jpeg")
return src
def houghCircles(circle_color,img_path:str, r_min:int = 20, r_max:int = 100, delta_r:int = 1, num_thetas:int = 100, bin_threshold:float = 0.4, min_edge_threshold:int = 100, max_edge_threshold:int = 200, pixel_threshold:int = 20, post_process:bool = True):
"""Function that detects circles in haugh domain.
Args:
img_path: image path.
r_min: minimum detected circles radius.
r_max maximum detected circles radius.
delta_r: the step to arrange the radius values.
nun_thetas: the step to arrange the thetas values.
bin_threshold: the threshold that decide whether takes a bin or not.
min_edge_threshold: canny edge detection min threshold constant.
max_edge_threshold: canny edge detection max threshold constant.
pixel_threshold: filltering the duplicate drwan circles pixel threshold
Returns:
output_img: (np.ndarray): the output image where circles are drwan at the edges of circles shapes.
"""
input_img = cv.imread(img_path)
#Edge detection on the input image
edge_image = cv.cvtColor(input_img, cv.COLOR_BGR2GRAY)
#ret, edge_image = cv.threshold(edge_image, 120, 255, cv2.THRESH_BINARY_INV)
edge_image = cv.Canny(edge_image, min_edge_threshold, max_edge_threshold)
if edge_image is None:
print ("Error in input image!")
return
#image size
img_height, img_width = edge_image.shape[:2]
# R and Theta ranges
dtheta = int(360 / num_thetas)
## Thetas is bins created from 0 to 360 degree with increment of the dtheta
thetas = np.arange(0, 360, step=dtheta)
## Radius ranges from r_min to r_max
rs = np.arange(r_min, r_max, step=delta_r)
circle_candidates = condidateCircles(thetas, rs, num_thetas)
accumulator = calculateAccumlator(img_height, img_width, edge_image, circle_candidates)
# Output image with detected lines drawn
output_img = input_img.copy()
# Output list of detected circles. A single circle would be a tuple of (x,y,r,threshold)
out_circles = []
# Sort the accumulator based on the votes for the candidate circles
for candidate_circle, votes in sorted(accumulator.items(), key=lambda i: -i[1]):
x, y, r = candidate_circle
current_vote_percentage = votes / num_thetas
if current_vote_percentage >= bin_threshold:
# Shortlist the circle for final result
out_circles.append((x, y, r, current_vote_percentage))
# Post process the results, can add more post processing later.
if post_process :
out_circles = postProcces(out_circles, pixel_threshold)
# Draw shortlisted circles on the output image
for x, y, r, v in out_circles:
if circle_color =='Red':
output_img = cv.circle(output_img, (x,y), r, (255,0,0), 2)
elif circle_color =='Blue':
output_img = cv.circle(output_img, (x,y), r, (0,0,205), 2)
elif circle_color == 'Green':
output_img = cv.circle(output_img, (x,y), r, (50,205,50), 2)
return output_img
def calculateAccumlator(img_height, img_width, edge_image, circle_candidates):
# Hough Accumulator, we are using defaultdic instead of standard dict as this will initialize for key which is not
# aready present in the dictionary instead of throwing exception.
accumulator = defaultdict(int)
for y in range(img_height):
for x in range(img_width):
if edge_image[y][x] != 0: #white pixel
# Found an edge pixel so now find and vote for circle from the candidate circles passing through this pixel.
for r, rcos_t, rsin_t in circle_candidates:
x_center = x - rcos_t
y_center = y - rsin_t
accumulator[(x_center, y_center, r)] += 1 #vote for current candidate
return accumulator
def condidateCircles(thetas, rs, num_thetas):
# Evaluate and keep ready the candidate circles dx and dy for different delta radius
# based on the the parametric equation of circle.
# x = x_center + r * cos(t) and y = y_center + r * sin(t),
# where (x_center,y_center) is Center of candidate circle with radius r. t in range of [0,2PI)
# Calculate Cos(theta) and Sin(theta) it will be required later
cos_thetas = np.cos(np.deg2rad(thetas))
sin_thetas = np.sin(np.deg2rad(thetas))
circle_candidates = []
for r in rs:
for t in range(num_thetas):
#instead of using pre-calculated cos and sin theta values you can calculate here itself by following
#circle_candidates.append((r, int(r*cos(2*pi*t/num_thetas)), int(r*sin(2*pi*t/num_thetas))))
#but its better to pre-calculate and use it here.
circle_candidates.append((r, int(r * cos_thetas[t]), int(r * sin_thetas[t])))
return circle_candidates
def postProcces(out_circles, pixel_threshold):
postprocess_circles = []
for x, y, r, v in out_circles:
# Exclude circles that are too close of each other
# all((x - xc) ** 2 + (y - yc) ** 2 > rc ** 2 for xc, yc, rc, v in postprocess_circles)
# Remove nearby duplicate circles based on pixel_threshold
if all(abs(x - xc) > pixel_threshold or abs(y - yc) > pixel_threshold or abs(r - rc) > pixel_threshold for xc, yc, rc, v in postprocess_circles):
postprocess_circles.append((x, y, r, v))
return postprocess_circles