擬合（最小二乘法和RANSAC）魯鵬北京郵電大學(xué)擬合我們已經(jīng)學(xué)習(xí)了如何檢測(cè)邊緣，現(xiàn)在要解決什么問題呢？我們希望用一個(gè)簡(jiǎn)單的模型對(duì)多種特征進(jìn)行分組，從而形成一個(gè)更高層次、更緊湊的圖像特征表示。9300HarrisCornersPkwy,夏洛特,NC2025/10/20北京郵電大學(xué)1來源：S.Lazebnik來源：K.Grauman擬合選擇一個(gè)參數(shù)化模型來表示一組特征簡(jiǎn)單模型：直線簡(jiǎn)單模型：圓復(fù)雜模型：汽車2025/10/20北京郵電大學(xué)2擬合：要解決的問題要檢測(cè)的特征區(qū)域存在噪聲無(wú)關(guān)數(shù)據(jù)：雜點(diǎn)（外點(diǎn)）、多條直線缺失數(shù)據(jù)：遮擋案例研究：直線檢測(cè)2025/10/20北京郵電大學(xué)3來源：S.Lazebnik擬合：概述如果我們知道哪些點(diǎn)屬于直線，那么我們?nèi)绾握业健白罴选敝本€參數(shù)？最小二乘法如果有外點(diǎn)怎么辦？Robustfitting，RANSAC如果有很多直線怎么辦？投票方式：RANSAC、Houghtransform如果我們不確定這是一條直線怎么辦？模型選擇2025/10/20北京郵電大學(xué)4來源：S.Lazebnik最小二乘法直線擬合數(shù)據(jù)：(x1

,y1)

,…,(xn,yn)直線方程：yi=mxi

+b找到(m,b)來最小化正規(guī)方程：XB=Y的最小二乘解(xi,yi)y=mx+b來源：S.Lazebnik“垂直”最小二乘法的問題非旋轉(zhuǎn)不變的無(wú)法描述垂直線2025/10/20北京郵電大學(xué)6來源：S.Lazebniky=mx+b數(shù)據(jù)：

(

x1

,y1),…,(xn,yn)直線方程：yi=mxi

+b找到(m,b)來最小化全最小二乘法點(diǎn)(xi,yi)與直線之間的距離

ax+by=d(a2+b2=1):

|axi+byi–d|(xi,yi)單位法向量：N=(a,b)來源：S.Lazebnikax+by=d全最小二乘法點(diǎn)(xi,yi)與直線之間的距離

ax+by=d(a2+b2=1):

|axi+byi–d|

找到(a,b,d)以最小化垂直距離的平方和(xi,yi)ax+by=d單位法向量：N=(a,b)來源：S.Lazebnik全最小二乘法點(diǎn)(xi,yi)與直線之間的距離

ax+by=d(a2+b2=1):|axi+byi–d|

找到(a,b,d)以最小化垂直距離平方和(xi,yi)ax+by=d（UTU)N=0的解，滿足||N||2=1：解為UTU的最小特征值對(duì)應(yīng)的特征向量（齊次線性系統(tǒng)的最小二乘解

UN=0)來源：S.Lazebnik單位法向量：N=(a,b)全最小二乘法二階矩矩陣來源：S.Lazebnik全最小二乘法N=(a,b)二階矩矩陣來源：S.Lazebnik

最小二乘用作極大似然估計(jì)(x,y)(u,v)ε生成模型：對(duì)共線的點(diǎn)獨(dú)立采樣，并在垂直于線的方向上引入高斯噪聲線上的點(diǎn)噪聲：采樣自零均值標(biāo)準(zhǔn)差為σ的高斯分布法線

方向2025/10/20北京郵電大學(xué)12來源：S.Lazebnikax+by=d最小二乘用作極大似然估計(jì)當(dāng)給定線的參數(shù)(a,b,d)時(shí)，點(diǎn)的出現(xiàn)概率可表示為：對(duì)數(shù)似然：(x,y)(u,v)ε2025/10/20北京郵電大學(xué)13來源：S.Lazebnikax+by=d生成模型：對(duì)共線的點(diǎn)獨(dú)立采樣，并在垂直于線的方向上引入高斯噪聲最小二乘法：對(duì)噪聲的魯棒性最小二乘法擬合紅色的點(diǎn)：2025/10/20北京郵電大學(xué)14來源：S.Lazebnik最小二乘法：對(duì)噪聲的魯棒性存在一個(gè)外點(diǎn)時(shí)的最小二乘法擬合：?jiǎn)栴}：平方誤差嚴(yán)重懲罰外點(diǎn)2025/10/20北京郵電大學(xué)15來源：S.Lazebnik魯棒估計(jì)

魯棒函數(shù)ρ對(duì)于較小殘差u表現(xiàn)為平方距離，但對(duì)于較大的u值飽和2025/10/20北京郵電大學(xué)16來源：S.Lazebnik選擇尺度：恰到好處外點(diǎn)的影響被最小化來源：S.Lazebnik每個(gè)點(diǎn)的誤差值幾乎相同，擬合得很差選擇尺度：太小來源：S.Lazebnik選擇尺度：太大結(jié)果與最小二乘法非常相似來源：S.Lazebnik魯棒估計(jì)：細(xì)節(jié)魯棒擬合是一個(gè)非線性優(yōu)化問題，必須迭代求解最小二乘解可用于初始化自適應(yīng)尺度選擇：大約1.5倍平均殘差（F&P，第15.5.1節(jié)）2025/10/20北京郵電大學(xué)20來源：S.LazebnikRANSAC魯棒擬合可以處理少量外點(diǎn)-如果我們有很多外點(diǎn)怎么辦？隨機(jī)采樣一致性(RANSAC)：

在存在外點(diǎn)的情況下進(jìn)行模型擬合的非常通用的框架概述隨機(jī)均勻地選擇一小部分樣本點(diǎn)，作為一個(gè)子集根據(jù)該子集擬合模型找到所有與該模型“接近”的剩余點(diǎn)，并將其余點(diǎn)作為外點(diǎn)丟棄多次執(zhí)行此操作并選擇最佳模型2025/10/20北京郵電大學(xué)21來源：S.LazebnikM.A.Fischler,R.C.Bolles.RandomSampleConsensus:AParadigmforModelFittingwithApplicationstoImageAnalysisandAutomatedCartography.Comm.oftheACM,Vol24,pp381-395,1981.

RANSAC用于直線擬合的示例來源：R.Raguram2025/10/20北京郵電大學(xué)22RANSAC用于直線擬合的示例最小二乘擬合來源：R.Raguram2025/10/20北京郵電大學(xué)23RANSAC用于直線擬合的示例隨機(jī)選擇點(diǎn)的最小子集資料來源：R.Raguram2025/10/20北京郵電大學(xué)24RANSAC用于直線擬合的示例隨機(jī)選擇點(diǎn)的最小子集假設(shè)一個(gè)模型來源：R.Raguram2025/10/20北京郵電大學(xué)25RANSAC用于直線擬合的示例隨機(jī)選擇點(diǎn)的最小子集假設(shè)一個(gè)模型計(jì)算誤差函數(shù)來源：R.Raguram2025/10/20北京郵電大學(xué)26RANSAC用于直線擬合的示例隨機(jī)選擇點(diǎn)的最小子集假設(shè)一個(gè)模型計(jì)算誤差函數(shù)選擇符合模型點(diǎn)來源：R.Raguram2025/10/20北京郵電大學(xué)27RANSAC用于直線擬合的示例隨機(jī)選擇點(diǎn)的最小子集假設(shè)一個(gè)模型計(jì)算誤差函數(shù)選擇與模型一致的點(diǎn)重復(fù)假設(shè)和驗(yàn)證循環(huán)來源：R.Raguram2025/10/20北京郵電大學(xué)28RANSAC用于直線擬合的示例隨機(jī)選擇點(diǎn)的最小子集假設(shè)一個(gè)模型計(jì)算誤差函數(shù)選擇與模型一致的點(diǎn)重復(fù)假設(shè)和驗(yàn)證循環(huán)來源：R.Raguram2025/10/20北京郵電大學(xué)29RANSAC用于直線擬合的示例隨機(jī)選擇點(diǎn)的最小子集假設(shè)一個(gè)模型計(jì)算誤差函數(shù)選擇與模型一致的點(diǎn)重復(fù)假設(shè)和驗(yàn)證循環(huán)未受污染的樣本來源：R.Raguram2025/10/20北京郵電大學(xué)30隨機(jī)選擇點(diǎn)的最小子集假設(shè)一個(gè)模型計(jì)算誤差函數(shù)選擇與模型一致的點(diǎn)重復(fù)假設(shè)和驗(yàn)證循環(huán)來源：R.RaguramRANSAC用于直線擬合的示例RANSAC用于直線擬合重復(fù)N次：隨機(jī)均勻抽取s個(gè)點(diǎn)對(duì)這些點(diǎn)進(jìn)行線擬合在剩余點(diǎn)中查找該線的內(nèi)點(diǎn)（即與該線的距離小于t的點(diǎn)）如果有d個(gè)或更多內(nèi)點(diǎn)，則接受該線并使用所有內(nèi)點(diǎn)重新擬合2025/10/20北京郵電大學(xué)32來源：S.Lazebnik來源：M.Pollfeys選擇參數(shù)

2025/10/20北京郵電大學(xué)33選擇參數(shù)來源：M.Pollfeys2025/10/20北京郵電大學(xué)34外點(diǎn)的比例

es5%10%20%25%30%40%50%22356711173347911193543591317347254612172657146647162437972937482033541635888592644782721177

選擇參數(shù)來源：M.Pollfeys2025/10/20北京郵電大學(xué)35

選擇參數(shù)來源：M.Pollfeys2025/10/20北京郵電大學(xué)