《機(jī)器人智能算法導(dǎo)論》

配套課件課程目標(biāo)能力目標(biāo)：能夠運(yùn)用梯度算子實現(xiàn)圖像邊緣提取并優(yōu)化機(jī)器人任務(wù)中的計算效率能設(shè)計基于Canny算子的多步驟邊緣檢測流程并分析其抗噪性能能結(jié)合RANSAC算法解決機(jī)器人視覺中的模型擬合問題（如直線檢測）知識目標(biāo)：掌握圖像梯度的數(shù)學(xué)定義及其在離散圖像中的差分近似方法理解Sobel、Prewitt、Canny等邊緣檢測算子的原理及應(yīng)用場景掌握RANSAC算法的迭代機(jī)制與參數(shù)計算邏輯，理解其對噪聲的魯棒性原理本講綱要邊緣檢測邊緣和語義上下文建模的語義分割直線檢測數(shù)據(jù)分析與處理|邊緣檢測什么是邊緣檢測將2D圖像轉(zhuǎn)換為一個曲線集合為什么需要邊緣檢測提取場景的顯著性特征比像素更緊湊，邊緣計算表面的不連續(xù)深度的不連續(xù)表面顏色的不連續(xù)照明的不連續(xù)數(shù)據(jù)分析與處理|邊緣檢測邊緣的類型階躍邊緣屋脊邊緣直線邊緣數(shù)據(jù)分析與處理|邊緣檢測真正的邊緣含噪聲的與離散的!理想的邊緣檢測產(chǎn)生邊緣幅度產(chǎn)生邊緣方向好檢測率和好的定位數(shù)據(jù)分析與處理|邊緣檢測梯度梯度方程:梯度方向:邊緣的強(qiáng)度梯度描述了圖像亮度強(qiáng)度變化最快的方向數(shù)據(jù)分析與處理|邊緣檢測離散圖像邊緣檢測子有限差分近似法:卷積掩模：數(shù)據(jù)分析與處理|邊緣檢測離散圖像邊緣檢測子

二階偏導(dǎo)數(shù)：

拉普拉斯算子:卷積掩模：or(更準(zhǔn)確)數(shù)據(jù)分析與處理|邊緣檢測離散圖像邊緣檢測子存在更好的梯度近似方法以下是常用的Sobel算子-101-202-101121000-1-2-1數(shù)據(jù)分析與處理|邊緣檢測離散圖像邊緣檢測子-101-101-101111000-1-11梯度定義:Roberts(2x2):Sobel(3x3):Sobel(5x5):-1-2021-2-3032-3-5053-2-3032-1-2021123212353200000-2-3-5-3-2-1-2-3-2-101-10100-1定位準(zhǔn)確對噪聲敏感檢測能力差定位差對噪聲不敏感檢測能力強(qiáng)數(shù)據(jù)分析與處理|邊緣檢測離散圖像邊緣檢測子Canny邊緣檢測器數(shù)據(jù)分析與處理|直線檢測什么是直線檢測輸入激光點云、圖像的邊緣圖等結(jié)構(gòu)簡單的、點集合數(shù)據(jù)輸出所有可能直線及其參數(shù)值位于直線上的點所屬的直線原圖邊緣圖檢測的直線數(shù)據(jù)分析與處理|直線檢測為什么要進(jìn)行直線檢測激光點云、邊緣圖蘊(yùn)含了場景的局部特征，邊緣圖可以認(rèn)為是邊緣像素點的集合，他們蘊(yùn)含了場景的幾何信息將局部點信息進(jìn)行進(jìn)一步抽象，形成直線，有利于高層語義理解和穩(wěn)定的地標(biāo)提取原圖邊緣圖檢測的直線數(shù)據(jù)分析與處理|直線檢測直線檢測的三個主要問題問題1：點云或邊緣圖等點集合中包含了多少條直線？問題2：點集合中的任意一個點屬于哪條直線？問題3：已知一個點集屬于一條直線，如何估計這條直線的參數(shù)值？常用的直線檢測算法分裂融合算法(Split-and-merge)線性回歸算法(Linearregression)隨機(jī)采樣一致算法(RANdomSAmpleConsensus,RANSAC)霍夫變換(Hough-Transform)數(shù)據(jù)分析與處理|直線檢測分裂-融合算法是一種迭代算法，其通過擬合和拆分的方式實現(xiàn)線段的檢測能同時解決問題1、問題2和問題3核心算法設(shè)S為點集合，dts為分裂閾值，dtm為融合閾值分裂步驟按著某種規(guī)則構(gòu)造一條直線；計算S中所有點到直線的距離，并找出距離最遠(yuǎn)的點p和最遠(yuǎn)距離d；如果d>dts，

那么從p點分裂，并在分裂的子點集中繼續(xù)執(zhí)行分裂步驟；融合步驟如果兩條連續(xù)的線段足夠共線(需要設(shè)定準(zhǔn)則)，那么按著既定規(guī)則構(gòu)造一條共享直線；如果屬于兩條線段的點到共享直線最遠(yuǎn)的距離小于dtm，那么利用共享直線代替原來的兩條連續(xù)直線，實現(xiàn)融合數(shù)據(jù)分析與處理|直線檢測分裂-融合算法是一種迭代算法，其通過擬合和拆分的方式實現(xiàn)線段的檢測能同時解決問題1、問題2和問題3核心算法設(shè)S為點集合，dts為分裂閾值，dtm為融合閾值分裂步驟按著某種規(guī)則構(gòu)造一條直線；計算S中所有點到直線的距離，并找出距離最遠(yuǎn)的點p和最遠(yuǎn)距離d；如果d>dts，

那么從p點分裂，并在分裂的子點集中繼續(xù)執(zhí)行分裂步驟；融合步驟如果兩條連續(xù)的線段足夠共線(需要設(shè)定準(zhǔn)則)，那么按著既定規(guī)則構(gòu)造一條共享直線；如果屬于兩條線段的點到共享直線最遠(yuǎn)的距離小于dtm，那么利用共享直線代替原來的兩條連續(xù)直線，實現(xiàn)融合數(shù)據(jù)分析與處理|直線檢測分裂-融合算法基于兩端點直線擬合的分裂-融合算法利用點云或邊緣圖的兩端的點來構(gòu)造一條直線。數(shù)據(jù)分析與處理|直線檢測分裂-融合算法基于兩端點直線擬合的分裂-融合算法利用點云或邊緣圖的兩端的點來構(gòu)造一條直線。分割數(shù)據(jù)分析與處理|直線檢測分裂-融合算法基于兩端點直線擬合的分裂-融合算法利用點云或邊緣圖的兩端的點來構(gòu)造一條直線。分割分割分割數(shù)據(jù)分析與處理|直線檢測分裂-融合算法基于兩端點直線擬合的分裂-融合算法利用點云或邊緣圖的兩端的點來構(gòu)造一條直線。不再分割分割分割分割數(shù)據(jù)分析與處理|直線檢測分裂-融合算法基于兩端點直線擬合的分裂-融合算法利用點云或邊緣圖兩端的點來構(gòu)造一條直線。合并不再分割分割分割分割數(shù)據(jù)分析與處理|直線檢測線性回歸算法是一種基于滑動窗口的直線檢測算法；首先為每一個窗口內(nèi)的點擬合一條直線；其次，將有重合點的直線進(jìn)行合并；能同時解決問題1、問題2和問題3。核心算法設(shè)S為點集合，Nf為窗口大小(覆蓋點的個數(shù))窗口滑動步驟為每一個窗口擬合一條直線；融合步驟如果兩條直線有重疊，那么屬于兩條直線的點進(jìn)行合并，并利用合并的點集重新擬合一條直線。Nf=

3數(shù)據(jù)分析與處理|直線檢測線性回歸算法是一種基于滑動窗口的直線檢測算法；首先為每一個窗口內(nèi)的點擬合一條直線；其次，將有重合點的直線進(jìn)行合并；能同時解決問題1、問題2和問題3。核心算法設(shè)S為點集合，Nf為窗口大小(覆蓋點的個數(shù))窗口滑動步驟為每一個窗口擬合一條直線；融合步驟如果兩條直線有重疊，那么屬于兩條直線的點進(jìn)行合并，并利用合并的點集重新擬合一條直線。Nf=

3數(shù)據(jù)分析與處理|直線檢測隨機(jī)采樣一致算法(RANdomSAmpleConsensus,RANSAC)是一種非確定性的迭代算法，每次迭代都隨機(jī)選擇點集的一個子集來為全部點集擬合一條直線隨著迭代次數(shù)的增加，選擇到一個沒有outliers子集的概率將會增加因為RANSAC可以有效避免outlier對擬合的負(fù)面影響，所以其是一個很魯棒的方法RANSAC可以應(yīng)用于任何需要選擇Inliers點估計預(yù)設(shè)模型參數(shù)的場合，比如局部特征匹配、相機(jī)標(biāo)定、平面提取、直線提前等因為是一種非確定性的迭代算法，所以每次運(yùn)行產(chǎn)生的結(jié)果可能不一致對于直線檢測應(yīng)用，其單獨使用能解決問題3，也可以和其它算法結(jié)合，解決問題1和問題2?數(shù)據(jù)分析與處理|直線檢測設(shè)S為點集合，M為參數(shù)待估計的預(yù)設(shè)模型，e為預(yù)設(shè)的檢驗條件。迭代步驟步驟1：隨機(jī)選擇一個最小樣本子集合；步驟2：估計預(yù)設(shè)模型M的參數(shù)；步驟3：利用e判斷其它樣本是否是內(nèi)點，并統(tǒng)計個數(shù)重復(fù)上述步驟K次，選出內(nèi)點數(shù)最多的模型利用內(nèi)點最多模型的內(nèi)點重新估計模型參數(shù)利用e進(jìn)一步尋找新的內(nèi)點利用新的內(nèi)點更新模型參數(shù)RANSAC核心算法RANSAC核心功能是從樣本集合擬合出產(chǎn)生樣本集合的預(yù)設(shè)模型。RANSAC的核心思想是，隨機(jī)從樣本集合中選擇一個能擬合出預(yù)設(shè)模型參數(shù)的最小樣本子集合，利用這個子集合估計出預(yù)設(shè)模型參數(shù)，再根據(jù)預(yù)設(shè)的檢驗準(zhǔn)測判斷其它樣本是否符合此模型（判斷是否是內(nèi)點），并統(tǒng)計符合的樣本個數(shù)。經(jīng)過多次迭代，將內(nèi)點最多的模型最為最終模型。數(shù)據(jù)分析與處理|直線檢測隨機(jī)采樣一致算法(RANdomSAmpleConsensus,RANSAC)步驟1：隨機(jī)采樣兩個點(子集合)數(shù)據(jù)分析與處理|直線檢測隨機(jī)采樣一致算法(RANdomSAmpleConsensus,RANSAC)步驟1：隨機(jī)采樣兩個點(子集合)步驟2：利用這兩個點構(gòu)建一條直線，估計直線的參數(shù)數(shù)據(jù)分析與處理|直線檢測隨機(jī)采樣一致算法(RANdomSAmpleConsensus,RANSAC)步驟1：隨機(jī)采樣兩個點(子集合)步驟2：利用這兩個點構(gòu)建一條直線，估計直線的參數(shù)步驟3：計算所有其它點到直線的距離(誤差)數(shù)據(jù)分析與處理|直線檢測隨機(jī)采樣一致算法(RANdomSAmpleConsensus,RANSAC)步驟1：隨機(jī)采樣兩個點(子集合)步驟2：利用這兩個點構(gòu)建一條直線，估計直線的參數(shù)步驟3：計算所有其它點到直線的距離(誤差)步驟4：選擇到直線距離小于預(yù)設(shè)誤差(e)的點，統(tǒng)計點的個數(shù)數(shù)據(jù)分析與處理|直線檢測隨機(jī)采樣一致算法(RANdomSAmpleConsensus,RANSAC)步驟1：隨機(jī)采樣兩個點(子集合)步驟2：利用這兩個點構(gòu)建一條直線，估計直線的參數(shù)步驟3：計算所有其它點到直線的距離(誤差)步驟4：選擇到直線距離小于預(yù)設(shè)誤差(e)的點，統(tǒng)計點的個數(shù)重復(fù)步驟1-4，直到達(dá)到預(yù)設(shè)的迭代次數(shù)數(shù)據(jù)分析與處理|直線檢測隨機(jī)采樣一致算法(RANdomSAmpleConsensus,RANSAC)步驟1：隨機(jī)采樣兩個點(子集合)步驟2：利用這兩個點構(gòu)建一條直線，估計直線的參數(shù)步驟3：計算所有其它點到直線的距離(誤差)步驟4：選擇到直線距離小于預(yù)設(shè)誤差(e)的點，統(tǒng)計點的個數(shù)重復(fù)步驟1-4，直到達(dá)到預(yù)設(shè)的迭代次數(shù)數(shù)據(jù)分析與處理|直線檢測隨機(jī)采樣一致算法(RANdomSAmpleConsensus,RANSAC)步驟1：隨機(jī)采樣兩個點(子集合)步驟2：利用這兩個點構(gòu)建一條直線，估計直線的參數(shù)步驟3：計算所有其它點到直線的距離(誤差)步驟4：選擇到直線距離小于預(yù)設(shè)誤差(e)的點，統(tǒng)計點的個數(shù)重復(fù)步驟1-4，直到達(dá)到預(yù)設(shè)的迭代次數(shù)K將包含Inliers個數(shù)最多的直線作為最終直線數(shù)據(jù)分析與處理|直線檢測如何為RANSAC選擇一個合適的迭代次數(shù)K？理想情況下，可以Check所有可能成對組合理想情況下，如何點集合中點的個數(shù)為N，需要Check的對的個數(shù)為N(N-1)/2，即K=N(N-1)/2。如果N的數(shù)量很大，那么需要Check的對的數(shù)量就會很龐大。事實上，如果已知內(nèi)點個數(shù)占總點數(shù)的粗略比例，那么可以以概率的方式解決這個問題。設(shè)N為集合點的個數(shù)；w為內(nèi)點和N的比例，

表示從集合隨機(jī)選到一個內(nèi)點的概率；p表示從集合隨機(jī)選取的最小樣本子集全是內(nèi)點的概率；對于直線檢測應(yīng)用，最小樣本子集的樣本個數(shù)是2。w

2表示從集合隨機(jī)選取的最小樣本子集全是內(nèi)點的概率，即p=w

2；1-w

2表示從集合隨機(jī)選取的最小樣本子集至少一個不是內(nèi)點的概率。如果迭代K次，那么選不到一個全是內(nèi)點的最小樣本子集的概率是(1-w2)k即1-q=(1-w2)k。q表示迭代K次后選到一個全是內(nèi)點的最小樣本子集的概率數(shù)據(jù)分析與處理|直線檢測如何為RANSAC選擇一個合適的迭代次數(shù)K？將上述公式兩邊去對數(shù)可得

log(1

q)

k

log(1

w2

)可以看出，如果我們粗略知道內(nèi)點在全部集合樣本的比例，那么只要我們設(shè)定一個想要的概率p，可以計算出需要多少次迭代，就可以以概率p獲得一個全是內(nèi)點的最小樣本集合

。舉例說明如果我們想以q=99%的概率，獲得一個包含兩個內(nèi)點的子集合，并且已知w=50%，那么可以算出，經(jīng)過K=16次迭代，就可以滿足。這遠(yuǎn)小于所有可能的對組合。數(shù)據(jù)分析與處理|直線檢測霍夫變換算法(HoughTransform)是一種特征提前算法，其通過將原空間的點變換到參數(shù)空間來通過投票來確定原空間點的形狀。能同時解決問題1、問題2和問題3為什么使用霍夫變換算法(HoughTransform)對于圖像邊緣圖和點云數(shù)據(jù)，由于邊緣檢測器和激光雷達(dá)的不完美性，導(dǎo)致有些邊緣像素點或點云點缺失，或偏離了實際的邊界，所以無法直觀的檢測出高層的直線、圓或橢圓的合集。另外，即使數(shù)據(jù)完美，人一眼就可以看出哪寫點屬于哪個直線或哪個圓，但機(jī)器并不知。需要獲得直線或圓的參數(shù)來確定直線或圓的位置。數(shù)據(jù)分析與處理|直線檢測霍夫變換霍夫變換就試圖將原空間的邊緣點或點云點映射到預(yù)定義形狀的參數(shù)空間。比如，預(yù)定義形狀是直線，那么原空間任意一點P映射到直線的參數(shù)空間，就是一條直線或曲線;參數(shù)空間的直線或曲線上任意一點就是原空間一個直線的參數(shù)。這條曲線表示所有通過原空間點P的直線。數(shù)據(jù)分析與處理|直線檢測霍夫變換如果利用斜率和截距來表示直線，在圖像空間或點云空間的一條直線對應(yīng)霍夫空間的一個點。m0b0圖像空間參數(shù)空間(霍夫空間)數(shù)據(jù)分析與處理|直線檢測霍夫變換如果利用斜率和截距來表示直線，圖像空間或點云空間的一個點對應(yīng)霍夫空間的一條直線。圖像空間參數(shù)空間(霍夫空間)數(shù)據(jù)分析與處理|直線檢測霍夫變換圖像空間兩個點(x0,y0)和(x1,y1)對應(yīng)霍夫空間中的兩條直線。因為兩個點相連就在圖像空間構(gòu)成一條直線，所以這條直線對應(yīng)霍夫變換的一個點。我們的目標(biāo)就是確定這個點的坐標(biāo)。因為(x0,y0)和(x1,y1)在圖像空間共線，所以這兩點在霍夫空間對應(yīng)的直線必然相交，交點就是的共線的斜率和截距。b*

m*圖像空間中的每個點都會在霍夫空間中為某條直線投票|數(shù)據(jù)分析與處理|直線檢測霍夫變換|霍夫變換本質(zhì)上就是圖像空間每一個點對所有可能穿過它的直線進(jìn)行投票。如果一條直線獲得的多個點的投票，那么說明這條直線穿過圖像空間中的多個點，即這幾個點共線，共享這條直線。數(shù)據(jù)分析與處理|直線檢測基于點斜視直線表示的霍夫變換|Image

SpaceParameter

Space步驟1：屬性測量圖像空間參數(shù)空間(霍夫空間)共線的點映射到霍夫空間后，他們對應(yīng)的直線，都會穿過參數(shù)空間的點(m,c)。數(shù)據(jù)分析與處理|直線檢測基于點斜視直線表示的霍夫變換|步驟1：投票計數(shù)量化參數(shù)空間創(chuàng)建累加器數(shù)組設(shè)置對于每個圖像邊緣點對于每個m計算c，基于公式增加計數(shù)在

中尋找局部最大值Parameter

Space1111112111111數(shù)據(jù)分析與處理|直線檢測霍夫變換利用斜率和截距來表示直線存在的問題當(dāng)直線垂直于x軸時，斜率為無限大，是一個無邊界的參數(shù)域，不便于電腦數(shù)值表示和計算。因此，需要尋找一種更方便的直線表達(dá)方法。數(shù)據(jù)分析與處理|直線檢測霍夫變換利用斜率和截距來表示直線存在的問題