實戰(zhàn)：基于霍夫變換進行線檢測
點擊上方“小白學視覺”，選擇加"星標"或“置頂”
重磅干貨，第一時間送達
霍夫變換算法線檢測
最近，我們發(fā)現(xiàn)自己不得不在應用程序中加入文檔掃描功能。在做了一些研究之后，我們偶然發(fā)現(xiàn)了一篇熊英寫的文章，他是Dropbox機器學習團隊的成員。該文章介紹了如何Dropbox的的機器學習團隊通過強調(diào)他們通過去的步驟，并在每個步驟使用的算法來實現(xiàn)他們的文檔掃描儀。通過那篇文章，我們了解了一種稱為霍夫變換的方法， 以及如何將其用于檢測圖像中的線條。因此，在本文中，我們想解釋Hough變換算法，并提供該算法在Python中的“從頭開始”的實現(xiàn)。
Hough變換是Paul VC Hough專利的一種算法，最初是為了識別照片中的復雜線條而發(fā)明的（Hough，1962）。自從創(chuàng)建以來，該算法已進行了修改和增強，使其能夠識別其他形狀，例如特定類型的圓形和四邊形。為了了解霍夫變換算法的工作原理，重要的是要了解四個概念：邊緣圖像，霍夫空間以及邊緣點到霍夫空間的映射，表示線的替代方法以及如何檢測線。
邊緣圖像
坎尼邊緣檢測算法
邊緣圖像是邊緣檢測算法的輸出。邊緣檢測算法通過確定圖像的亮度/強度急劇變化的位置來檢測圖像中的邊緣（“邊緣檢測-使用Python進行圖像處理”，2020年）。邊緣檢測算法的示例包括：Canny，Sobel，Laplacian等。對邊緣圖像進行二值化是很常見的，意味著其所有像素值均為1或0。根據(jù)你們的情況，為1或0可以表示邊緣像素。
霍夫空間和邊緣點到霍夫空間的映射
霍夫空間是2D平面，其水平軸表示坡度，而垂直軸表示邊緣圖像上直線的截距。邊緣圖像上的一條線以y = ax + b的形式表示（Hough，1962年）。邊緣圖像上的一條線在霍夫空間上產(chǎn)生一個點，因為一條線的特征在于其斜率a和截距b。另一方面，邊緣圖像上的邊緣點（x?，y?）可以有無數(shù)的線通過。因此，邊緣點在Hough空間中以b =ax?+y?的形式生成一條線（Leavers，1992）。在霍夫變換算法中，霍夫空間用于確定邊緣圖像中是否存在線條。
表示線的另一種方法
用y = ax + b形式的直線 和帶有斜率和截距的霍夫空間代表著一種缺陷。在這種形式下，該算法將無法檢測垂直線，因為斜率a對于垂直線是不確定的/無窮大（Leavers，1992）。編程，這意味著，一個計算機將需要的存儲器的無限量來表示的所有可能的值一個。為避免此問題，一條直線由一條稱為法線的線表示，該線穿過原點并垂直于該直線。法線的形式為ρ = x cos（ θ ）+ y sin（ θ ），其中ρ 是法線的長度，θ是法線與x軸之間的角度。
使用此方法，不再用坡度a和截距b表示霍夫空間，而是用ρ和θ表示，其中水平軸表示θ值，垂直軸表示ρ值。邊緣點到霍夫空間的映射以類似的方式工作，除了邊緣點（x，y）現(xiàn)在在霍夫空間中生成余弦曲線，而不是直線（Leavers，1992）。線的這種正常表示消除了在處理垂直線時出現(xiàn)的a的無限值的問題。
線檢測
如前所述，邊緣點在霍夫空間中產(chǎn)生余弦曲線。由此，如果我們將邊緣圖像中的所有邊緣點映射到霍夫空間上，它將生成許多余弦曲線。如果兩個邊緣點位于同一條線上，則它們對應的余弦曲線將在特定的（ρ，θ）對上彼此相交。因此，霍夫變換算法通過找到交叉點數(shù)量大于某個閾值的（ρ，θ）對來檢測線。值得注意的是，如果不對霍夫空間進行鄰域抑制等預處理以去除邊緣圖像中的相似線條，這種閾值化方法可能不會總是產(chǎn)生最佳結果。
確定ρ和θ的范圍。通常，θ的范圍是[0，180]度，而ρ是[ -d，d ]，其中d是邊緣圖像對角線的長度。量化ρ和θ的范圍很重要，這意味著應該有數(shù)量有限的可能值。
創(chuàng)建一個稱為累加器的二維數(shù)組，該數(shù)組表示維度為（num_rhos，num_thetas）的霍夫空間，并將其所有值初始化為零。
對原始圖像執(zhí)行邊緣檢測?？梢允褂媚銈冞x擇的任何邊緣檢測算法來完成。
對于邊緣圖像上的每個像素，請檢查該像素是否為邊緣像素。如果是邊緣像素，則循環(huán)遍歷所有可能的θ值，計算對應的ρ，在累加器中找到θ和ρ索引，并基于這些索引對遞增累加器。
循環(huán)遍歷累加器中的所有值。如果該值大于某個閾值，則獲取ρ和θ索引，從索引對獲取ρ和θ的值，然后可以將其轉換回y = ax + b的形式。
非向量化解決方案
import cv2import numpy as npimport matplotlib.pyplot as pltimport matplotlib.lines as mlinesdef line_detection_non_vectorized(image, edge_image, num_rhos=180, num_thetas=180, t_count=220):edge_width = edge_image.shape[:2]edge_width_half = edge_height / 2, edge_width / 2#d = np.sqrt(np.square(edge_height) + np.square(edge_width))dtheta = 180 / num_thetasdrho = (2 * d) / num_rhos#thetas = np.arange(0, 180, step=dtheta)rhos = np.arange(-d, d, step=drho)#cos_thetas = np.cos(np.deg2rad(thetas))sin_thetas = np.sin(np.deg2rad(thetas))#accumulator = np.zeros((len(rhos), len(rhos)))#figure = plt.figure(figsize=(12, 12))subplot1 = figure.add_subplot(1, 4, 1)subplot1.imshow(image)subplot2 = figure.add_subplot(1, 4, 2)cmap="gray")subplot3 = figure.add_subplot(1, 4, 3)0, 0))subplot4 = figure.add_subplot(1, 4, 4)subplot4.imshow(image)#for y in range(edge_height):for x in range(edge_width):if edge_image[y][x] != 0:edge_point = [y - edge_height_half, x - edge_width_half]xs = [], []for theta_idx in range(len(thetas)):rho = (edge_point[1] * cos_thetas[theta_idx]) + (edge_point[0] * sin_thetas[theta_idx])theta = thetas[theta_idx]rho_idx = np.argmin(np.abs(rhos - rho))+= 1ys.append(rho)xs.append(theta)ys, color="white", alpha=0.05)for y in range(accumulator.shape[0]):for x in range(accumulator.shape[1]):if accumulator[y][x] > t_count:rho = rhos[y]theta = thetas[x]a = np.cos(np.deg2rad(theta))b = np.sin(np.deg2rad(theta))x0 = (a * rho) + edge_width_halfy0 = (b * rho) + edge_height_halfx1 = int(x0 + 1000 * (-b))y1 = int(y0 + 1000 * (a))x2 = int(x0 - 1000 * (-b))y2 = int(y0 - 1000 * (a))[rho], marker='o', color="yellow")x2], [y1, y2]))subplot3.invert_yaxis()subplot3.invert_xaxis()Image")Image")Space")Lines")plt.show()return accumulator, rhos, thetasif __name__ == "__main__":for i in range(3):image = cv2.imread(f"sample-{i+1}.png")edge_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)edge_image = cv2.GaussianBlur(edge_image, (3, 3), 1)edge_image = cv2.Canny(edge_image, 100, 200)edge_image = cv2.dilate(edge_image,(5, 5)),iterations=1)edge_image = cv2.erode(edge_image,(5, 5)),iterations=1)edge_image)
向量化解決方案
import cv2import numpy as npimport matplotlib.pyplot as pltimport matplotlib.lines as mlinesdef line_detection_vectorized(image, edge_image, num_rhos=180, num_thetas=180, t_count=220):edge_width = edge_image.shape[:2]edge_width_half = edge_height / 2, edge_width / 2#d = np.sqrt(np.square(edge_height) + np.square(edge_width))dtheta = 180 / num_thetasdrho = (2 * d) / num_rhos#thetas = np.arange(0, 180, step=dtheta)rhos = np.arange(-d, d, step=drho)#cos_thetas = np.cos(np.deg2rad(thetas))sin_thetas = np.sin(np.deg2rad(thetas))#accumulator = np.zeros((len(rhos), len(rhos)))#figure = plt.figure(figsize=(12, 12))subplot1 = figure.add_subplot(1, 4, 1)subplot1.imshow(image)subplot2 = figure.add_subplot(1, 4, 2)cmap="gray")subplot3 = figure.add_subplot(1, 4, 3)0, 0))subplot4 = figure.add_subplot(1, 4, 4)subplot4.imshow(image)#edge_points = np.argwhere(edge_image != 0)edge_points = edge_points - np.array([[edge_height_half, edge_width_half]])#rho_values = np.matmul(edge_points, np.array([sin_thetas, cos_thetas]))#theta_vals, rho_vals = np.histogram2d(rho_values.shape[0]),rho_values.ravel(),bins=[thetas, rhos])accumulator = np.transpose(accumulator)lines = np.argwhere(accumulator > t_count)theta_idxs = lines[:, 0], lines[:, 1]t = rhos[rho_idxs], thetas[theta_idxs]for ys in rho_values:ys, color="white", alpha=0.05)[r], color="yellow", marker='o')for line in lines:x = linerho = rhos[y]theta = thetas[x]a = np.cos(np.deg2rad(theta))b = np.sin(np.deg2rad(theta))x0 = (a * rho) + edge_width_halfy0 = (b * rho) + edge_height_halfx1 = int(x0 + 1000 * (-b))y1 = int(y0 + 1000 * (a))x2 = int(x0 - 1000 * (-b))y2 = int(y0 - 1000 * (a))[rho], marker='o', color="yellow")x2], [y1, y2]))subplot3.invert_yaxis()subplot3.invert_xaxis()Image")Image")Space")Lines")plt.show()return accumulator, rhos, thetasif __name__ == "__main__":for i in range(3):image = cv2.imread(f"sample-{i+1}.png")edge_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)edge_image = cv2.GaussianBlur(edge_image, (3, 3), 1)edge_image = cv2.Canny(edge_image, 100, 200)edge_image = cv2.dilate(edge_image,(5, 5)),iterations=1)edge_image = cv2.erode(edge_image,(5, 5)),iterations=1)edge_image)
綜上所述，本文以最簡單的形式展示了Hough變換算法，該算法可以擴展到檢測直線以外。多年來，對該算法進行了許多改進，使其可以檢測其他形狀，例如圓形，三角形甚至特定形狀的四邊形。這導致了許多有用的現(xiàn)實世界應用，從文檔掃描到自動駕駛汽車的車道檢測。
推薦一波我好朋友的公眾號：
交流群
歡迎加入公眾號讀者群一起和同行交流，目前有SLAM、三維視覺、傳感器、自動駕駛、計算攝影、檢測、分割、識別、醫(yī)學影像、GAN、算法競賽等微信群（以后會逐漸細分），請掃描下面微信號加群，備注：”昵稱+學校/公司+研究方向“，例如：”張三 + 上海交大 + 視覺SLAM“。請按照格式備注，否則不予通過。添加成功后會根據(jù)研究方向邀請進入相關微信群。請勿在群內(nèi)發(fā)送廣告，否則會請出群，謝謝理解~