實(shí)戰(zhàn)：基于霍夫變換進(jìn)行線檢測(cè)
點(diǎn)擊上方“AI算法與圖像處理”，選擇加"星標(biāo)"或“置頂”
重磅干貨，第一時(shí)間送達(dá)
霍夫變換算法線檢測(cè)
最近，我們發(fā)現(xiàn)自己不得不在應(yīng)用程序中加入文檔掃描功能。在做了一些研究之后，我們偶然發(fā)現(xiàn)了一篇熊英寫的文章，他是Dropbox機(jī)器學(xué)習(xí)團(tuán)隊(duì)的成員。該文章介紹了如何Dropbox的的機(jī)器學(xué)習(xí)團(tuán)隊(duì)通過強(qiáng)調(diào)他們通過去的步驟，并在每個(gè)步驟使用的算法來實(shí)現(xiàn)他們的文檔掃描儀。通過那篇文章，我們了解了一種稱為霍夫變換的方法， 以及如何將其用于檢測(cè)圖像中的線條。因此，在本文中，我們想解釋Hough變換算法，并提供該算法在Python中的“從頭開始”的實(shí)現(xiàn)。
Hough變換是Paul VC Hough專利的一種算法，最初是為了識(shí)別照片中的復(fù)雜線條而發(fā)明的（Hough，1962）。自從創(chuàng)建以來，該算法已進(jìn)行了修改和增強(qiáng)，使其能夠識(shí)別其他形狀，例如特定類型的圓形和四邊形。為了了解霍夫變換算法的工作原理，重要的是要了解四個(gè)概念：邊緣圖像，霍夫空間以及邊緣點(diǎn)到霍夫空間的映射，表示線的替代方法以及如何檢測(cè)線。
邊緣圖像
坎尼邊緣檢測(cè)算法
邊緣圖像是邊緣檢測(cè)算法的輸出。邊緣檢測(cè)算法通過確定圖像的亮度/強(qiáng)度急劇變化的位置來檢測(cè)圖像中的邊緣（“邊緣檢測(cè)-使用Python進(jìn)行圖像處理”，2020年）。邊緣檢測(cè)算法的示例包括：Canny，Sobel，Laplacian等。對(duì)邊緣圖像進(jìn)行二值化是很常見的，意味著其所有像素值均為1或0。根據(jù)你們的情況，為1或0可以表示邊緣像素。
霍夫空間和邊緣點(diǎn)到霍夫空間的映射
霍夫空間是2D平面，其水平軸表示坡度，而垂直軸表示邊緣圖像上直線的截距。邊緣圖像上的一條線以y = ax + b的形式表示（Hough，1962年）。邊緣圖像上的一條線在霍夫空間上產(chǎn)生一個(gè)點(diǎn)，因?yàn)橐粭l線的特征在于其斜率a和截距b。另一方面，邊緣圖像上的邊緣點(diǎn)（x?，y?）可以有無數(shù)的線通過。因此，邊緣點(diǎn)在Hough空間中以b =ax?+y?的形式生成一條線（Leavers，1992）。在霍夫變換算法中，霍夫空間用于確定邊緣圖像中是否存在線條。
表示線的另一種方法
用y = ax + b形式的直線 和帶有斜率和截距的霍夫空間代表著一種缺陷。在這種形式下，該算法將無法檢測(cè)垂直線，因?yàn)樾甭蔭對(duì)于垂直線是不確定的/無窮大（Leavers，1992）。編程，這意味著，一個(gè)計(jì)算機(jī)將需要的存儲(chǔ)器的無限量來表示的所有可能的值一個(gè)。為避免此問題，一條直線由一條稱為法線的線表示，該線穿過原點(diǎn)并垂直于該直線。法線的形式為ρ = x cos（ θ ）+ y sin（ θ ），其中ρ 是法線的長度，θ是法線與x軸之間的角度。
使用此方法，不再用坡度a和截距b表示霍夫空間，而是用ρ和θ表示，其中水平軸表示θ值，垂直軸表示ρ值。邊緣點(diǎn)到霍夫空間的映射以類似的方式工作，除了邊緣點(diǎn)（x，y）現(xiàn)在在霍夫空間中生成余弦曲線，而不是直線（Leavers，1992）。線的這種正常表示消除了在處理垂直線時(shí)出現(xiàn)的a的無限值的問題。
線檢測(cè)
如前所述，邊緣點(diǎn)在霍夫空間中產(chǎn)生余弦曲線。由此，如果我們將邊緣圖像中的所有邊緣點(diǎn)映射到霍夫空間上，它將生成許多余弦曲線。如果兩個(gè)邊緣點(diǎn)位于同一條線上，則它們對(duì)應(yīng)的余弦曲線將在特定的（ρ，θ）對(duì)上彼此相交。因此，霍夫變換算法通過找到交叉點(diǎn)數(shù)量大于某個(gè)閾值的（ρ，θ）對(duì)來檢測(cè)線。值得注意的是，如果不對(duì)霍夫空間進(jìn)行鄰域抑制等預(yù)處理以去除邊緣圖像中的相似線條，這種閾值化方法可能不會(huì)總是產(chǎn)生最佳結(jié)果。
確定ρ和θ的范圍。通常，θ的范圍是[0，180]度，而ρ是[ -d，d ]，其中d是邊緣圖像對(duì)角線的長度。量化ρ和θ的范圍很重要，這意味著應(yīng)該有數(shù)量有限的可能值。
創(chuàng)建一個(gè)稱為累加器的二維數(shù)組，該數(shù)組表示維度為（num_rhos，num_thetas）的霍夫空間，并將其所有值初始化為零。
對(duì)原始圖像執(zhí)行邊緣檢測(cè)。可以使用你們選擇的任何邊緣檢測(cè)算法來完成。
對(duì)于邊緣圖像上的每個(gè)像素，請(qǐng)檢查該像素是否為邊緣像素。如果是邊緣像素，則循環(huán)遍歷所有可能的θ值，計(jì)算對(duì)應(yīng)的ρ，在累加器中找到θ和ρ索引，并基于這些索引對(duì)遞增累加器。
循環(huán)遍歷累加器中的所有值。如果該值大于某個(gè)閾值，則獲取ρ和θ索引，從索引對(duì)獲取ρ和θ的值，然后可以將其轉(zhuǎ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變換算法，該算法可以擴(kuò)展到檢測(cè)直線以外。多年來，對(duì)該算法進(jìn)行了許多改進(jìn)，使其可以檢測(cè)其他形狀，例如圓形，三角形甚至特定形狀的四邊形。這導(dǎo)致了許多有用的現(xiàn)實(shí)世界應(yīng)用，從文檔掃描到自動(dòng)駕駛汽車的車道檢測(cè)。
個(gè)人微信（如果沒有備注不拉群！） 請(qǐng)注明：地區(qū)+學(xué)校/企業(yè)+研究方向+昵稱
下載1：何愷明頂會(huì)分享
在「AI算法與圖像處理」公眾號(hào)后臺(tái)回復(fù)：何愷明，即可下載。總共有6份PDF，涉及 ResNet、Mask RCNN等經(jīng)典工作的總結(jié)分析
下載2：終身受益的編程指南：Google編程風(fēng)格指南
在「AI算法與圖像處理」公眾號(hào)后臺(tái)回復(fù)：c++，即可下載。歷經(jīng)十年考驗(yàn)，最權(quán)威的編程規(guī)范！
下載3 CVPR2021
在「AI算法與圖像處理」公眾號(hào)后臺(tái)回復(fù)：CVPR，即可下載1467篇CVPR 2020論文 和 CVPR 2021 最新論文
點(diǎn)亮 
，告訴大家你也在看