Python圖像處理之Hough變換檢測直線

更新時間：2023年07月27日 16:16:55 作者：菜菜的小粉豬

霍夫變換是一種特征檢測(feature?extraction)，被廣泛應用在圖像分析，本文將利用Hough變換實現(xiàn)直線檢測，感興趣的小伙伴可以了解一下

一、前言

霍夫變換是一種特征檢測(feature extraction)，被廣泛應用在圖像分析（image analysis）、計算機視覺(computer vision)以及數(shù)位影像處理(digital image processing)。由RichardDuda和PeterHart在公元1972年發(fā)明，并稱之為廣義霍夫變換(generalizedHoughtransform)，廣義霍夫變換和更早前1962年的PaulHough的專利有關(guān)。經(jīng)典的霍夫變換是偵測圖片中的直線，之后，霍夫變換不僅能識別直線，也能夠識別任何形狀，常見的有圓形、橢圓形。1981年，因為DanaH.Ballard的一篇期刊論文"Generalizing the Hough transform to detect arbitrary shapes"，讓霍夫變換開始流行于計算機視覺界。霍夫變換是用來辨別找出物件中的特征，例如：線條。他的算法流程大致如下，給定一個物件、要辨別的形狀的種類，算法會在參數(shù)空間(parameter space)中執(zhí)行投票來決定物體的形狀，而這是由累加空間(accumulator space)里的局部最大值(local maximum)來決定。

二、Hough 變換

一條直線可由兩個點A=(x1?,y1?)和B=(x2?,y2?)確定(笛卡爾坐標)

另一方面，y=kx+b也可以寫成關(guān)于（k,q）的函數(shù)表達式（霍夫空間）：

空間變換過程如下圖：

變換后的空間成為霍夫空間。即：笛卡爾坐標系中一條直線，對應霍夫空間的一個點。

反過來同樣成立（霍夫空間的一條直線，對應笛卡爾坐標系的一個點）：

笛卡爾坐標系中兩個點對應霍夫空間兩條線：

如果笛卡爾坐標系三個點共線，對應的霍夫空間的三條線相交于一點

霍夫變換的后處理的基本方式：選擇由盡可能多直線匯成的點。但是，按照直角坐標系表示的話會出現(xiàn)下圖的情況：當圖像空間中點共的線垂直于x軸時，斜率無限大，在霍夫空間無法找到交點。因而，人們最終引入了極坐標的表示法。

極坐標下的霍夫直線檢測原理與直角坐標系下完全一致，唯一需要重新推導的是與霍夫空間的極坐標參數(shù)函數(shù)：

化簡便可得到:

r=xcosθ+ysinθ

如果對于一個給定點(x0?,y0?)，意味著每一對(r,θ)代表一條通過點(xθ?,yθ?)的直線。我們在極坐標對極徑極角平面繪出所有通過它的直線, 將得到一條正弦曲線. 例如, 對于給定點(x0?=8和y0?=6) 我們可以繪出下圖 (在平面):

極坐標與笛卡爾坐標的轉(zhuǎn)換公式，從極坐標轉(zhuǎn)換(r,θ)在笛卡爾坐標系(x,y):

從笛卡兒坐標轉(zhuǎn)換 (x,y) 到極坐標(r,θ):

在極坐標系下，其實是一樣的：極坐標的點→霍夫空間的直線，只不過霍夫空間不再是[k,q]的參數(shù)，而是(r,θ)。

三、直線檢測

通過上面的介紹可知，畫出x−y坐標空間中的點在參數(shù)空間中對應的曲線，然后計算參數(shù)空間中曲線的交點，就能求得待求的參數(shù)。但還有一個問題，當參數(shù)空間中的曲線存在多個交點時，如何挑選出最有可能的解呢？

具體計算時，可將參數(shù)空間劃分為所謂的累加單元A(θ,ρ)。如圖下圖所示，對于x−y平面的每一個非背景點(xk?,yk?),令 θ等于每個可取的細分值，根據(jù)θ=−xk?θ+yk?計算出對應的ρ值，每計算出一組 A(θ,ρ)，則令A(θ,ρ)=A(θ,ρ)+1。計算所有結(jié)果后，找到A(θ,ρ)的峰值對應的θ和ρ，即可檢測直線。(θmin?,θmax?)和(ρmin?,ρmax?)是期望的參數(shù)范圍：0°≤θ≤180°和−D≤θ≤D, D是圖像對角線的長度。 θ和ρ的細分數(shù)量決定了檢測結(jié)果的精度。

投票過程可以觀看下面的GIF,

左邊上青色的點代表圖像上的像素點，黃色的代表對各個點不同角度搜索。右半邊是投票盤，顏色越淺代表票數(shù)越多。

四、代碼實現(xiàn)

1.hough檢測

def lines_detector_hough(img,ThetaDim=None, DistStep=None, threshold=None, halfThetaWindowSize=2,
                         halfDistWindowSize=None):
    '''
    :param img: 經(jīng)過邊緣檢測得到的二值圖
    :param ThetaDim: hough空間中theta軸的刻度數(shù)量(將[0,pi)均分為多少份),反應theta軸的粒度,越大粒度越細
    :param DistStep: hough空間中dist軸的劃分粒度,即dist軸的最小單位長度
    :param threshold: 投票表決認定存在直線的起始閾值
    :return: 返回檢測出的所有直線的參數(shù)(theta,dist)和對應的索引值,
    '''
    row,col= edge.shape
    if ThetaDim == None:
        ThetaDim = 90
    if DistStep == None:
        DistStep = 1
    # 計算距離分段數(shù)量
    MaxDist = np.sqrt(row ** 2 + col ** 2)
    DistDim = int(np.ceil(MaxDist / DistStep))
    if halfDistWindowSize == None:
        halfDistWindowSize = int(DistDim /50)
    # 建立投票
    accumulator = np.zeros((ThetaDim, DistDim))  # theta的范圍是[0,pi). 在這里將[0,pi)進行了線性映射.類似的,也對Dist軸進行了線性映射
    #
    sinTheta = [np.sin(t * np.pi / ThetaDim) for t in range(ThetaDim)]
    cosTheta = [np.cos(t * np.pi / ThetaDim) for t in range(ThetaDim)]
    #計算距離（rho）
    for i in range(row):
        for j in range(col):
            if not edge[i, j] == 0:
                for k in range(ThetaDim):
                    accumulator[k][int(round((i * cosTheta[k] + j * sinTheta[k]) * DistDim / MaxDist))] += 1
    M = accumulator.max()
#---------------------------------------
    #非極大抑制
    if threshold == None:
        threshold = int(M * 1.369/ 10)
    result = np.array(np.where(accumulator > threshold))  # 閾值化
    #獲得對應的索引值
    temp = [[], []]
    for i in range(result.shape[1]):
        eight_neiborhood = accumulator[
                           max(0, result[0, i] - halfThetaWindowSize + 1):min(result[0, i] + halfThetaWindowSize,
                                                                              accumulator.shape[0]),
                           max(0, result[1, i] - halfDistWindowSize + 1):min(result[1, i] + halfDistWindowSize,
                                                                             accumulator.shape[1])]
        if (accumulator[result[0, i], result[1, i]] >= eight_neiborhood).all():
            temp[0].append(result[0, i])
            temp[1].append(result[1, i])
    #記錄原圖所檢測的坐標點（x,y）
    result_temp= np.array(temp)
#-------------------------------------------------------------
    result = result_temp.astype(np.float64)
    result[0] = result[0] * np.pi / ThetaDim
    result[1] = result[1] * MaxDist / DistDim
    return result,result_temp

2.畫直線代碼

def drawLines(lines, edge, color=(255, 0, 0), err=3):
    '''
    :param lines: 檢測后的直線參數(shù)
    :param edge: 原圖
    :param color: 直線的顏色
    :param err:檢測的可接受的誤差值
    :return: 無
    '''
    if len(edge.shape) == 2:
        result = np.dstack((edge, edge, edge))
    else:
        result = edge
    Cos = np.cos(lines[0])
    Sin = np.sin(lines[0])
    for i in range(edge.shape[0]):
        for j in range(edge.shape[1]):
            e = np.abs(lines[1] - i * Cos - j * Sin)
            if (e < err).any():
                result[i, j] = color
    plt.imshow(result, cmap='gray')
    plt.axis('off')
    plt.show()

3.畫hough空間代碼

def data_img(data):
    '''
    :param data: 直線上含有的點（x,y）
    :return: 輸出hough空間圖像
    '''
    fig = plt.figure()  # 新建畫布
    ax = axisartist.Subplot(fig, 111)  # 使用axisartist.Subplot方法創(chuàng)建一個繪圖區(qū)對象ax
    fig.add_axes(ax)
    ax.axis[:].set_visible(False)  # 隱藏原來的實線矩形
    ax.axis["x"] = ax.new_floating_axis(0, 0, axis_direction="bottom")  # 添加x軸
    ax.axis["y"] = ax.new_floating_axis(1, 0, axis_direction="bottom")  # 添加y軸
    ax.axis["x"].set_axisline_style("->", size=1.0)  # 給x坐標軸加箭頭
    ax.axis["y"].set_axisline_style("->", size=1.0)  # 給y坐標軸加箭頭
    t = np.arange(-np.pi / 2, np.pi / 2, 0.1)
    ax.annotate(text='x', xy=(2 * math.pi, 0), xytext=(2 * math.pi, 0.1))  # 標注x軸
    ax.annotate(text='y', xy=(0, 1.0), xytext=(-0.5, 1.0))  # 標注y軸
    for i in range(data.shape[1]):
        rho = data[0][i] * np.cos(t) + data[1][i] * np.sin(t)
        plt.plot(t, rho)
    plt.show()