實(shí)戰(zhàn)：基于霍夫變換進(jìn)行線檢測(cè)
點(diǎn)擊上方“小白學(xué)視覺(jué)”，選擇加"星標(biāo)"或“置頂”
重磅干貨，第一時(shí)間送達(dá)
霍夫變換算法線檢測(cè)
最近，我們發(fā)現(xiàn)自己不得不在應(yīng)用程序中加入文檔掃描功能。在做了一些研究之后，我們偶然發(fā)現(xiàn)了一篇熊英寫(xiě)的文章，他是Dropbox機(jī)器學(xué)習(xí)團(tuán)隊(duì)的成員。該文章介紹了如何Dropbox的的機(jī)器學(xué)習(xí)團(tuán)隊(duì)通過(guò)強(qiáng)調(diào)他們通過(guò)去的步驟，并在每個(gè)步驟使用的算法來(lái)實(shí)現(xiàn)他們的文檔掃描儀。通過(guò)那篇文章，我們了解了一種稱(chēng)為霍夫變換的方法， 以及如何將其用于檢測(cè)圖像中的線條。因此，在本文中，我們想解釋Hough變換算法，并提供該算法在Python中的“從頭開(kāi)始”的實(shí)現(xiàn)。
Hough變換是Paul VC Hough專(zhuān)利的一種算法，最初是為了識(shí)別照片中的復(fù)雜線條而發(fā)明的（Hough，1962）。自從創(chuàng)建以來(lái)，該算法已進(jìn)行了修改和增強(qiáng)，使其能夠識(shí)別其他形狀，例如特定類(lèi)型的圓形和四邊形。為了了解霍夫變換算法的工作原理，重要的是要了解四個(gè)概念：邊緣圖像，霍夫空間以及邊緣點(diǎn)到霍夫空間的映射，表示線的替代方法以及如何檢測(cè)線。
邊緣圖像
坎尼邊緣檢測(cè)算法
邊緣圖像是邊緣檢測(cè)算法的輸出。邊緣檢測(cè)算法通過(guò)確定圖像的亮度/強(qiáng)度急劇變化的位置來(lái)檢測(cè)圖像中的邊緣（“邊緣檢測(cè)-使用Python進(jìn)行圖像處理”，2020年）。邊緣檢測(cè)算法的示例包括：Canny，Sobel，Laplacian等。對(duì)邊緣圖像進(jìn)行二值化是很常見(jià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?）可以有無(wú)數(shù)的線通過(guò)。因此，邊緣點(diǎn)在Hough空間中以b =ax?+y?的形式生成一條線（Leavers，1992）。在霍夫變換算法中，霍夫空間用于確定邊緣圖像中是否存在線條。
表示線的另一種方法
用y = ax + b形式的直線 和帶有斜率和截距的霍夫空間代表著一種缺陷。在這種形式下，該算法將無(wú)法檢測(cè)垂直線，因?yàn)樾甭蔭對(duì)于垂直線是不確定的/無(wú)窮大（Leavers，1992）。編程，這意味著，一個(gè)計(jì)算機(jī)將需要的存儲(chǔ)器的無(wú)限量來(lái)表示的所有可能的值一個(gè)。為避免此問(wèn)題，一條直線由一條稱(chēng)為法線的線表示，該線穿過(guò)原點(diǎn)并垂直于該直線。法線的形式為ρ = x cos（ θ ）+ y sin（ θ ），其中ρ 是法線的長(zhǎng)度，θ是法線與x軸之間的角度。
使用此方法，不再用坡度a和截距b表示霍夫空間，而是用ρ和θ表示，其中水平軸表示θ值，垂直軸表示ρ值。邊緣點(diǎn)到霍夫空間的映射以類(lèi)似的方式工作，除了邊緣點(diǎn)（x，y）現(xiàn)在在霍夫空間中生成余弦曲線，而不是直線（Leavers，1992）。線的這種正常表示消除了在處理垂直線時(shí)出現(xiàn)的a的無(wú)限值的問(wèn)題。
線檢測(cè)
如前所述，邊緣點(diǎn)在霍夫空間中產(chǎn)生余弦曲線。由此，如果我們將邊緣圖像中的所有邊緣點(diǎn)映射到霍夫空間上，它將生成許多余弦曲線。如果兩個(gè)邊緣點(diǎn)位于同一條線上，則它們對(duì)應(yīng)的余弦曲線將在特定的（ρ，θ）對(duì)上彼此相交。因此，霍夫變換算法通過(guò)找到交叉點(diǎn)數(shù)量大于某個(gè)閾值的（ρ，θ）對(duì)來(lái)檢測(cè)線。值得注意的是，如果不對(duì)霍夫空間進(jìn)行鄰域抑制等預(yù)處理以去除邊緣圖像中的相似線條，這種閾值化方法可能不會(huì)總是產(chǎn)生最佳結(jié)果。
確定ρ和θ的范圍。通常，θ的范圍是[0，180]度，而ρ是[ -d，d ]，其中d是邊緣圖像對(duì)角線的長(zhǎng)度。量化ρ和θ的范圍很重要，這意味著應(yīng)該有數(shù)量有限的可能值。
創(chuàng)建一個(gè)稱(chēng)為累加器的二維數(shù)組，該數(shù)組表示維度為（num_rhos，num_thetas）的霍夫空間，并將其所有值初始化為零。
對(duì)原始圖像執(zhí)行邊緣檢測(cè)?？梢允褂媚銈冞x擇的任何邊緣檢測(cè)算法來(lái)完成。
對(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)
綜上所述，本文以最簡(jiǎn)單的形式展示了Hough變換算法，該算法可以擴(kuò)展到檢測(cè)直線以外。多年來(lái)，對(duì)該算法進(jìn)行了許多改進(jìn)，使其可以檢測(cè)其他形狀，例如圓形，三角形甚至特定形狀的四邊形。這導(dǎo)致了許多有用的現(xiàn)實(shí)世界應(yīng)用，從文檔掃描到自動(dòng)駕駛汽車(chē)的車(chē)道檢測(cè)。
推薦一波我好朋友的公眾號(hào)：
交流群
歡迎加入公眾號(hào)讀者群一起和同行交流，目前有SLAM、三維視覺(jué)、傳感器、自動(dòng)駕駛、計(jì)算攝影、檢測(cè)、分割、識(shí)別、醫(yī)學(xué)影像、GAN、算法競(jìng)賽等微信群（以后會(huì)逐漸細(xì)分），請(qǐng)掃描下面微信號(hào)加群，備注：”昵稱(chēng)+學(xué)校/公司+研究方向“，例如：”張三 + 上海交大 + 視覺(jué)SLAM“。請(qǐng)按照格式備注，否則不予通過(guò)。添加成功后會(huì)根據(jù)研究方向邀請(qǐng)進(jìn)入相關(guān)微信群。請(qǐng)勿在群內(nèi)發(fā)送廣告，否則會(huì)請(qǐng)出群，謝謝理解~