本文將簡單介紹 Hough Transform 偵測直線的基本原理，並使用 OpenCV 套件進行直線的偵測。

Hough Transform 原理:
在理解 Hough Transform 前，我們必須了解該轉換會用到的兩件事，分別為 "直線的 Hesse normal form" 和 "給定非原點的一點，收集所有通過該點的直線的 Hesse normal form 表示式的集合會是三角函數"，底下為這兩件事情的推論。

• "直線的 Hesse normal form":

Note: 過原點的直線滿足 "0 = xcos(theta)+ysin(theta)"，eg: 假設上圖該直線的 theta = 45 度，將此直線往原點方向平行移動 (r 趨近最後抵達原點 o, theta 固定不變)，抵達原點時即可得到直線 y= -x。

• Fact: "給定非原點的一點，收集所有通過該點的直線的 Hesse normal form 表示式的集合會是三角函數":

• Observation:

根據上面的 Fact，我們可以得知給定任意非原點的兩點時，Fact 中和該兩點有關的三角函數的交點代表著一條通過這兩點的直線。

在理解了 Hough Transform 會用到的數學原理後，接下來就讓我們進入正題吧，但在進入正題前你可能會有下面的疑問?!(沒有也沒關係XD)

首先我們注意一下我們的目標是偵測影像中的 "直線"，但上面的數學原理都是在跟我說某點如果有直線經過該點時會發生什麼事，是"建立在直線經過某點的情況下"的推論，但今天給定影像中的一點，我根本不知道該點有沒有直線經過啊，如果該點真的有直線經過的話，將這樣性質的點收集起來，或許有機會可以求得我們要的直線，可是問題是我們根本不知道給定的點有沒有線段通過，因此這樣要在影像中尋找直線，猶如在大海撈針，我們該怎麼偵測我們關心的"線段"呢?

➡️

Note: 我們要找的直線，往往其實藏在邊緣(Edge)裡!!!

所以若我們能偵測出邊緣(輪廓)，不就代表說那些邊緣(輪廓)上的點就是我直線線段的"候選人(Candidate)"了嗎?😝

透過這樣的想法，我們可以將這個大海撈針的問題簡化成去判斷邊緣上的點是否有機率就是直線線段上的某點，若是的話，我們就找到我們關心的直線了! 這也是為什麼我們會看到 Hough Transform (通常)會要求 Binary-Format 的圖片，因為如果你的輪廓上的點的像素是 255，不是輪廓上的點像素是 0，等於是告訴該演算法說哪些像素是候選人，是可能會有直線通過的點!

而實務上，我們會習慣用 Canny edge detector 去做 edge detection，因為 Canny 後得到的圖片就是 Binary-Format 的邊緣輪廓圖片，所以可以很方便，無縫接軌地當作 Hough Transform 的 Input!

• Voting in r-theta grids:

好了，既然我們已經知道那些點是"候選人(Candidate)"，那接下來我們又該怎麼找出這些候選人，或是說，找出我們關心的線段呢? 根據上面的 Fact，我們知道通過這些候選人的所有線段集合在 r-theta 平面上會是三角函數，既然如此，我就把這些點相關的三角函數畫出來，這樣再根據上面 fact 之後的 Observation，我們就可以知道越多條三角函數通過的交點其實可能代表著我們關心的直線。

而實際上三角函點上的有無限多個，我們不可能將所有的點畫出來去看交集，於是我們會採用投票的機制，去近似那些多條三角函數相交的點，底下將簡單介紹此投票機制的步驟。

1. 將 r-theta 平面分成細小的 grids，例如 theta 的範圍(0-180度)可以從分成180份，r 的範圍可以選擇 0 到對角線的長度去做細分，如下圖所示。

2. 取得 grids 後，從候選人中挑出一點，我們可以知道它的 x,y 座標，接著依序依步驟1的 theta 的那些分割點，依序帶入直線的 Hesse normal form 求得相對應的 r，例如我將 theta 分割成 180等份，我就將該候選點的x,y座標，依需用 theta=0，theta=1度,..., theta=179度帶入去求得我的r，接著再去看那些取樣的樣本點落在哪幾格 grids，每個樣本點落在哪個 grid，相當於該 grid 獲得一票，如下方示意圖。

3. 依序對其他候選人做一樣的事情，最後去統計 grids 得到的所有票數，票數越高的 grid，代表說可能越多條三角函數會在此 grid 有交點，此時我們可以在每個票數高的 grid 中去選一點來代表我的直線，如下圖所示。而從下圖我們也可以推測，如果"直線真的存在"，則我的 grids 若是取得越小(diameter越小)，則票數越高的Grids中選出來的黃色代表點就越有可能靠近我的真實交點(淡藍色的點)，也就是說黃點所代表的直線越有可能接近淡藍色的點所代表的直線，也就是我們所關心的直線。(Note:但我們也不難想像grids 切得越細，則計算量越大，需要儲存的訊息也越多)

簡單起見，使用 Accumulator 實作 Voting 的部份筆者就不在此介紹了，有興趣的讀者可以自行 Google, 接下來讓我們直接套用 OpenCV 幫我們實作好的 HoughLines 方法來偵測直線吧!

程式碼(Python):

import cv2
import numpy as np
import matplotlib.pyplot as plt

your_pic = '../images/yourpic.jpg' # 圖片位址

your_pic_img = cv2.imread(your_pic) 
your_pic_img_copy = your_pic_img.copy()

# 將讀取的圖片轉成灰階
gray_img = cv2.cvtColor(your_pic_img, cv2.COLOR_BGR2GRAY)
# 透過 Canny Detector 偵測邊緣
edges = cv2.Canny(gray_img, 50,150,apertureSize = 3)
# 調用 OpenCV　的　 HoughLines　方法偵測 theta 範圍在[ min_theta, max_theta]內，voter 投票數超過100票的直線， theta 的參數代表將其 theta 分割成360份，rho 等於 200 代表將向素以200單位距離為一分割長度。
lines = cv2.HoughLines(edges, rho = 200, theta= np.pi/360, threshold= 100, min_theta = np.pi/3 , max_theta = np.pi/2 )

＃將直線畫出來
for line in lines:
    rho,theta = line[0]
    a = np.cos(theta)
    b = np.sin(theta)
    x0 = a*rho
    y0 = b*rho
    x1 = int(x0 + 1000*(-b))
    y1 = int(y0 + 1000*(a))
    x2 = int(x0 - 1000*(-b))
    y2 = int(y0 - 1000*(a))

    cv2.line(your_pic_img,(x1,y1),(x2,y2),(0,255,255),20)

pic_titles = ['origin','after canny','after hough']
bgr_images= [your_pic_img_copy, edges, your_pic_img]
rgb_images = [cv2.cvtColor(img, cv2.COLOR_BGR2RGB) for img in bgr_images]

for i in range(len(pic_titles)):

    plt.subplot(1, len(pic_titles) ,i+1), plt.imshow(rgb_images[i])
    plt.title(pic_titles[i])
    plt.xticks([]),plt.yticks([]) 

plt.show()

Result:

Note:

• 官方theta 的角度定義(不太一樣):
  
  可以注意到官方 theta 的角度和我們一般所熟悉的 theta 角度定義不太一樣，這應該是因為它把[0,0] index 的Pixel 當作原點比較方便的關係。

• 帶入不同參數畫出的線:底下為一些不同參數帶入的結果，讀者有興趣可以自己帶入各種不同的參數玩玩看，從中我們也可以發現 Hough Transform 得到的線段集合跟參數選取有關，不全然真的就是我們關心的直線，但 Hough Transform 仍然不失為偵測直線的一個好方法!

1. lines = cv2.HoughLines(edges,rho = 200, theta= np.pi/360, threshold= 100, min_theta = 0 , max_theta = np.pi/2 )
   
2. lines = cv2.HoughLines(edges,rho = 200, theta= np.pi/360, threshold= 100, min_theta = 0 , max_theta = np.pi/2 )
   
3. lines = cv2.HoughLines(edges,rho = 200, theta= np.pi/180, threshold= 10000)
   
4. lines = cv2.HoughLines(edges, rho = 1, theta= np.pi/360, threshold= 100, min_theta = np.pi/3 , max_theta = np.pi/2 )
   

• 沒有找到線的時候 hough.line 會回傳 'None':
  
  HoughLines 方法再調用時，會因為參數的選取導致直線可能找不到，此時沒有找到直線的話會回傳 None，因此使用時須注意一下是否要做 try-catch 等例外處理。

以上就是筆者對 Hough Transform 的直線偵測相關理解，希望對讀者有所幫助，謝謝~