本專題目的：了解最小二乘、RANSAC、霍夫變換這3個算法的基本原理，能夠做到脫口而出，并從零編程實現。

目錄

1 前言

2 最小二乘

2.1 基本原理

2.2 求解方法

3 RANSAC 算法

3.1 基本原理

4 霍夫變換

4.1 基本原理——檢測直線

4.1.1?極坐標系

4.1.2 找到參數空間中交點密集位置的方法

4.1.3 一些效果圖

4.2 基本原理——檢測圓

4.3 霍夫變換的其他應用

5 總結

---

1 前言

上一專題知道了如何提取圖像中邊緣像素，本專題我們看看如何從邊緣圖中，通過‘擬合’技術，來進一步提取一些我們需要的幾何形狀邊緣，如直線、圓、或者其他形狀。

當然，從圖像中找到我們想要的一些幾何特征，存在一些難點：

1. 噪聲：圖像以及預處理會存在各種噪聲，影響擬合。
2. 外點（無關點）：如果我們要找一輛車上的幾何形狀，那么圖像中車之外的像素點都是無關像素，但它們會影響我們程序自動化尋找。
3. 遮擋：目標圖形部分被遮擋，使幾何形狀間斷。

（備注：機器學習中也有算法可以完成此事，而且效果更好、更魯棒，所以本專題不做太深入細究，且一些傳統視覺算法的延伸優化問題也不介紹了）

2 最小二乘

2.1 基本原理

最小二乘法（least square method)是一種常用的數學優化方法，所謂二乘就是平方的意思。這平方一詞指的是在擬合一個函數的時候，通過最小化誤差的平方來確定最佳的匹配函數，所以最小二乘指的就是擬合的誤差平方達到最小。

假設這種線性關系為：f(x) = ax+b

總誤差的平方為：

在誤差式子中，不同的 a,b 會導致不同的 E，根據多元微分的知識，當它們的偏微分等于0時，E 可取最小值。

上述方程組為線性方程組，求解上述方程組，得出 a,b 的值后，我們就能找到一條‘最佳’擬合線。（備注：其實這種距離判定方法并不是最優的，具體可見北郵魯鵬的《計算機視覺》中一些最小二乘的改進方法）

2.2 求解方法

主要利用線性代數相關技巧：

本小節主要參考：http://mangoroom.cn/opencv/least-square-method-line-fit.html

3 RANSAC 算法

一眼就能明白，最小二乘擬合方法有太多局限性。效果受噪音數據、圖像遮擋等很大影響。

• 普通最小二乘法是保守派：在現有數據下，如何實現最優。是從一個整體誤差最小的角度去考慮，盡量誰也不得罪。
• RANSAC是改革派：首先假設數據具有某種特性（目的），為了達到目的，適當割舍一些現有的數據。

3.1 基本原理

RANSAC簡化版的思路就是：

第1步：隨機選擇幾個樣本點（如估計一條直線方程需要兩個點，其他模型可能不一樣）

第2步：擬合出一個模型（即把這個直線方程定下來）

第3步：設置一個門限

第4步：記下門限內囊括的“內點”的數量，重復1~4步，迭代N次

第5步：最后選用那個“內點”最多的擬合模型。

RANSAC算法一個很重要參數是：迭代次數。這個參數有種方法可以估算大概是要多少。

具體原理和過程參考：

• RANSAC算法詳解(附Python擬合直線模型代碼) - 知乎
• RANSAC算法理解_robinhjwy的博客-CSDN博客

真實應用時，其實需要針對特定問題和情況做更多改進，比如RANSAC最終得到最好的一根線，其實再用最小二乘去擬合這根線周圍的點，得到的新直線會更好。

4 霍夫變換

RANSAC不好解決圖像中存在大量線的情況。

• 霍夫變換，可以用來檢測圖像中任意多個直線、圓、橢圓等幾何體。它最初被設計成用來檢測能夠精確地解析定義的形狀（即可以用數學公式精確定義的幾何體）。后來廣義霍夫變換（1972）不要求給出幾何體的解析式。
• 它通過將圖像坐標空間變換到參數空間，來實現直線與曲線的擬合。

4.1 基本原理——檢測直線

理解第1點：圖像中的一條直線在參數空間（霍夫空間）是一個點：

原因：只要確定了m和b值，那么也就在 x,y 空間確定了一條直線。

理解第2點：圖像中，經過某點的無數條直線，在參數空間里可以用一條直線表示。（或者也可以說，圖像空間中一個點，在參數空間中是一條直線）

原因：圖像中經過某點的直線公式為 y0 = x0*m+b，而這個公式在參數空間就是一條直線。

理解第3點：參數空間中兩條線的交點，代表圖像空間中兩個點的直線。

原因：參數空間中兩條線交點位置的參數，可以在圖像空間確定一條直線，而這條這些必定經過參數空間那兩條直線所對應圖像空間中那兩個點。

理解第4點：將圖像空間中所有點在參數空間用直線描述，然后將參數空間網格化，統計參數空間每個網格內的直線交點個數（也就是投票），交點數越多的，表示這個網格所對應的參數在圖像空間所形成的直線更有可能是圖像邊緣所形成的直線。

以下是圖片中得票率（交點數）最高的20條直線:

理解上面4點，基本也就理解霍夫變換找直線的方法了，其實找圓也類似，只是直線參數空間變成圓方程參數空間。

當然，實際找直線時，并不是用 y = mx + b方程。原因是：

• 圖像中垂直的直線，斜率無窮大，在參數空間中此交點位置會離原點無窮遠。這導致沒法計算了。

4.1.1?極坐標系

圖像坐標是笛卡爾坐標系，我們把參數空間用極坐標中參數表示就能解決上述問題。

如下圖，xy坐標系中任意一個點，可以用θ和ρ參數來表示：

要意識到兩點：

• θ值僅在180個單位長度內就能完整的與圖像空間中所有點進行對應。
• ρ值其實也是有限大的，因為圖像尺寸是長寬的，也即xy長度有限，那么根據極坐標轉換公式，ρ也不會無限大。

把θ和ρ作為參數，則圖像空間中一個點，在參數空間中就變為一條正弦曲線，如下圖：

上圖，我們的θ在0~180直接，也可以畫在-90~90之間。

4.1.2 找到參數空間中交點密集位置的方法

首先我們網格化參數空間，只要統計出每個網格內有多少根線經過，就也算出了該網格所對應的參數值在邊緣圖像空間中形成的直線，是會經過多少個邊緣像素點。

我們用一個二維矩陣 H 來代表參數空間：

具體算法過程如下：

• 將二維數組（作為累加器） H(θ, ρ) 初始化為0
• For 圖像空間每個像素點（x, y）
  • For θ 0到180
    • 計算ρ值:（ρ = x*cosθ + y*cosθ）
    • 投票+1（因為此θ和ρ點有條線經過）：H(θ, ρ)? = H(θ, ρ) + 1
  • End
• End
• 尋找H矩陣中，元素值的局部波峰位置，這些位置所對應θ和ρ值，就對應圖像中各邊緣形成的直線。

注意：

• 由于圖像中的直線往往具有一定的像素寬度，這會導致 H 矩陣的局部會有連續幾個高投票值位置，因此每找到一個當前最大的峰值點后，需要將該點及其附近點清零，以防算法檢測出多條極其鄰近的“假”直線。
• 具體使用時，還是要應對噪聲問題，也可以借助圖像中梯度方向來減少遍歷次數等等，具體要用時還是要更深入研究。

4.1.3 一些效果圖

散點線：

有噪聲的情況：

兩根粗直線：

上圖左邊是一個邊緣圖像，每個像素點通過極坐標映射到霍夫空間后，會有2個密集交匯區，而且這個高亮區寬度還是比較大的（代表邊緣圖像中大量平行且臨近的直線）。

正方形和圓：

上圖正方形霍夫空間會有4個交匯點，而圓沒有任何密集交匯區（上圖亮度只是可視化方式不一樣）。

幾何圖形在一起情況：

電路板：

網格線：

4.2 基本原理——檢測圓

根據下面的圖，理解如下幾點：

1. 圖像中一個圓，可以用三個參數表示：圓心坐標(x, y)和半徑 r ，所以，圖像中一個圓，可以用三維參數空間中一個點來表示。
2. 圖像中一個點，它如果在圖像中的某個圓上，那它和圓心所成的方向，是該點圖像梯度的方向！（圖像梯度的原理和計算方法見專題2）。這一點很重要，這是理解后續的基礎，也是該建模方法可窮舉投票的理由。（當然，殘缺了一點的圓，這些殘缺像素位置梯度可能為0或其他，但并不影響后續投票算法）
3. 基于已知的某點圖像梯度方向，經過圖像中某一個點的所有可能的圓，可以在x,y,r三維空間中用兩根直線表示。（如果不考慮該點梯度方向，則笛卡爾坐標系中某一個點，其所有可能的圓，在參數空間中可以用一個立體圓錐曲面表示！）
4. 對于圖像中某個像素點 (x，y) ，當給定r半徑值后，僅有兩個可能的圓心位置（這兩個潛在可能的圓心位置相對這個像素點互為鏡像位置），這兩個圓心的位置可以通過x，y，r，以及圖像梯度角度值計算出來。

理解上述4點后，遍歷圖像中每個像素點，再遍歷r長度的可能范圍，通過投票來找，找到參數空間中密度高亮區，這些位置的參數就鎖定了圖像中一些圓。算法如下：

• For 圖像中每一個邊緣像素點
  • For r in range( len(最大半徑) )（注意：r是可窮舉的，因為圖像中最大的完整圓，其半徑最大為圖像高或寬的一半）
    • 計算圓心坐標（a, b）
    • H(a, b, r) = H(a, b, r)? + 1
  • End
• End
• 找出H(a, b, r) 中局部最大點。

4.3 霍夫變換的其他應用

除了檢測出直線、圓等幾何體，此算法進一步還能做一些其他事，因為最近幾年沒什么進展了，就不細研究了。

案例：通過檢測一些大物體的局部組件相對大物體的位置關系，通過方向投票機制，去鎖定圖像中某大物體的中心位置。

5 總結

本專題介紹了圖像擬合的一些經典計算機視覺方法，雖然這些方法在深度學習時代競爭力已不大，但是其經久考驗的算法思想還是很值得學習的。通過本專題整理，收獲主要如下：

1. 霍夫變換思想，真的讓我震驚了，感覺可以和DL技術相結合。
2. 投票機制。
3. 圖像噪聲對各種算法的影響，以及應對措施，這方面非常麻煩，效果也要特定問題特定分析，讓我更加感受到深度學習技術的潛在威力。

總結

以上是生活随笔為你收集整理的CS131专题-4：拟合（最小二乘、RANSAC、霍夫变换）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。