The basic idea of Hough transform is to map a candidate object of interest in the original coordinate system of the image to a point in another coordinate system (may be the same as the image system). The result of this mapping is that the problem of finding the most likely objects in the image system becomes the problem of finding areas of densest points in the other coordinate system, which is often an easier problem. The most likely objects can then be reconstructed by carrying out the reverse mapping.
Finding lines¶
All candidate lines passing through $(x,y)$ in the image system are mapped to the set of points $(d,\theta)$ in the Hough space that satisfy the following equation:
import numpy as np
from matplotlib import pyplot as plt
import cv2
def hough_lines_acc(edge_image):
theta = []
rho = []
min_rho = -edge_image.shape[1]
max_rho = int(np.ceil(np.sqrt(np.sum(np.square(edge_image.shape)))))
for angle in range(0,180):
theta.append(float(angle)/180*np.pi)
for distance in range(min_rho, max_rho+1):
rho.append(distance)
hough = np.zeros((len(rho), len(theta)))
for y in range(edge_image.shape[0]):
for x in range(edge_image.shape[1]):
if edge_image[y,x] > 0:
for i in range(len(theta)):
angle = theta[i]
distance = int(y * np.sin(angle) + x * np.cos(angle))
hough[distance-min_rho, i] += 1
return hough, rho, theta
def hough_peaks(H, peak_num):
indices = H.ravel().argsort()[-peak_num:]
indices = (np.unravel_index(i, H.shape) for i in indices)
return [i for i in indices]
def hough_lines_draw(image, peaks, rho, theta):
for peak in peaks:
distance = rho[peak[0]]
angle = theta[peak[1]]
if not np.isclose(angle, np.pi/2):
y_1 = 0
x_1 = int((distance - y_1 * np.sin(angle))/np.cos(angle))
y_2 = image.shape[0]
x_2 = int((distance - y_2 * np.sin(angle))/np.cos(angle))
cv2.line(image, (x_1, y_1), (x_2, y_2), 250, 3)
else:
cv2.line(image, (0, distance), (image.shape[1], distance), 250, 3)
return image
plt.figure(figsize = (12, 8))
image = cv2.imread('pens_n_coins.png')
gray = cv2.cvtColor(image, cv2.COLOR_RGB2GRAY)
canny = cv2.Canny(cv2.GaussianBlur(gray, (11,11), 4), 3, 40)
hough_space, rho, theta = hough_lines_acc(canny)
plt.subplot(131), plt.imshow(canny, cmap='gray')
plt.subplot(132), plt.imshow(hough_space, cmap='gray', aspect=0.1)
peaks = hough_peaks(hough_space, 4)
hough_lines = hough_lines_draw(image, peaks, rho, theta)
plt.subplot(133), plt.imshow(hough_lines, cmap='gray')
plt.show()
Finding circles¶
All candidate circles of radius $r$ passing through a point $(x,y)$ in the image system are mapped to all points of distance $r$ from $(x,y)$.
$$\begin{equation} \begin{split} x_c & = x + r \cos(\theta) \\ y_c & = y + r \sin(\theta) \end{split} \end{equation}$$import numpy as np
from matplotlib import pyplot as plt
import cv2
def hough_circles_acc(edge_image, radius):
hough = np.zeros(edge_image.shape)
for y in range(edge_image.shape[0]):
for x in range(edge_image.shape[1]):
if edge_image[y,x] > 0:
for theta in range(0,360):
theta = float(theta)/180.*np.pi
vote_x = int(x + radius * np.cos(theta))
vote_y = int(y + radius * np.sin(theta))
if 0 <= vote_y < edge_image.shape[0]:
if 0 <= vote_x < edge_image.shape[1]:
hough[vote_y, vote_x] += 1
return hough
def hough_peaks(H, peak_num):
indices = H.ravel().argsort()[-peak_num:]
indices = (np.unravel_index(i, H.shape) for i in indices)
return [i[::-1] for i in indices]
def find_circles(image, radius_range):
plt.figure(figsize = (12, 8))
gray = cv2.cvtColor(image, cv2.COLOR_RGB2GRAY)
canny = cv2.Canny(cv2.GaussianBlur(gray, (11,11), 4), 3, 40)
plt.subplot(121), plt.imshow(canny, cmap='gray')
for radius in range(radius_range[0], radius_range[1]+1):
hough_space = hough_circles_acc(canny, radius)
centers = hough_peaks(hough_space, 4)
for center in centers:
cv2.circle(image, center, radius, [255, 0, 0], 3)
plt.subplot(122), plt.imshow(image, cmap='gray')
image = cv2.imread('pens_n_coins.png')
find_circles(image, [20,30])
plt.show()
