工學(xué)mv-chp07輪廓表示

第7章

輪廓表示1.輪廓：把邊緣連接起來就成為輪廓(contour)．輪廓可以是斷開的，也可以是封閉的.輪廓可以用邊緣有序表或曲線來表示。曲線通常稱為輪廓的數(shù)學(xué)模型．曲線表示包括線段、二次曲線、三次樣條曲線等．

2.輪廓表示的評價標(biāo)準(zhǔn)：

效率：輪廓應(yīng)該是一種簡單和緊湊的表示．

精確：輪廓應(yīng)能精確地逼近圖像特征．

有效：輪廓應(yīng)適合于后續(xù)應(yīng)用階段的計算．3.精確表示輪廓的影響因素：用于輪廓建模的曲線形式；曲線擬合算法的性能；邊緣位置估計的精確度。4.輪廓曲線擬合通常采用內(nèi)插曲線或逼近曲線來實現(xiàn)．一組稱為控制點的坐標(biāo)點，內(nèi)插是指一條曲線擬合這組控制點，使得曲線通過所有的控制點；逼近是指一條曲線擬合這組這組控制點，使得這條曲線非常接近這些控制點而無需一定通過這些點．5.定義：邊緣表是邊緣點或邊緣段的有序集合,輪廓的最簡單表示形式。輪廓是邊緣表或用于表示邊緣表的曲線。邊界是包圍一個區(qū)域的封閉輪廓。6.設(shè)Pi=(xi,yi)是邊緣表中第i個邊緣坐標(biāo)．(1)k斜率是在邊緣表相距k個邊緣點的兩個邊緣點之間的〔角〕方向向量．(2)左k斜率是Pi指向Pi–k的方向，(3)右k斜率是Pi指向Pi+k方向．(4)k曲率是左右k斜率之差值。7.1數(shù)字曲線及其表示7.(6)輪廓端點之間的距離為(5)數(shù)字曲線的長度可以近似為像素之間的線段和：8.數(shù)字曲線表示1－鏈碼

鏈碼：是沿著輪廓記錄邊緣表的一種表示方法．鏈碼規(guī)定了邊緣表中每一個邊緣點的輪廓方向，其中方向被量化為四個或八個方向中的一個．9.曲線的鏈碼是：6022222021013444444454577012其差分鏈碼是：22000062771210000001712021110.曲線的鏈碼是：024444424323566666676711234其差分鏈碼是：2200006277121000001713011111.鏈碼的特殊性質(zhì):一個物體很容易實現(xiàn)45角旋轉(zhuǎn)．如果一個物體旋轉(zhuǎn)Nx45°，可由原鏈碼值加上N后再模8得到．N逆時針為正，順時針為負(fù)。鏈碼的微分，也稱差分碼，由原碼的一階差分求得．鏈碼差分是關(guān)于旋轉(zhuǎn)不變的邊界描述方法．鏈碼的問題：表示某一點正切方向的集合是有限的〔４－鄰接鏈碼有4個，8－鄰接鏈碼有8個〕。12.用任意的正切方向來表示輪廓可以克服鏈碼的只能用有限個正切方向來表示輪廓的局限性．假定從邊緣表開始，計算正切

和弧長的投影s，畫出正切同弧長的投影的關(guān)系圖，稱作

s圖．?dāng)?shù)字曲線表示2－K斜率13.一個輪廓及其

s圖．對于封閉輪廓，

s圖是一個周期曲線．輪廓

s14.三種常用的曲線模型擬合邊緣點的方法：

(1)直線段(LineSegment)(2)圓錐曲線段(ConicSection)(3)三次樣條曲線段(CubicSpline)．用曲線模型擬合邊緣點應(yīng)考慮如下兩個問題：

(1)用什么算法進(jìn)行邊緣點的曲線模型擬合？

(2)如何測量擬合的逼近程度？7.2曲線擬合15.設(shè)di是擬合曲線和候選點之間的誤差．〔1〕最大絕對誤差(MaximumAbsoluteError,MAE):測量最壞情況下邊緣點偏離曲線的距離。〔2〕均方差(MeanSquaredError,MSE):給出邊緣點偏離擬合曲線的總的測度。常用的誤差測量方法16.〔3〕標(biāo)準(zhǔn)化最大誤差(NormalizedMaximumError,NME):最大絕對誤差與曲線長度S之比。17.〔5〕誤差符號變化數(shù):用來表示輪廓邊緣模型的曲線適合程度的測度．〔4〕曲線長度與端點距離之比:曲線復(fù)雜程度的測度。18.多直線段是指端點連結(jié)端點的直線段序列，直線段序列的連接點稱為頂點．最大標(biāo)準(zhǔn)誤差常常作為線段擬合邊緣列表好壞的量度.7.2.1多直線段表示19.自頂而下的分裂算法(top-downsplitting)：將整條曲線作為初始曲線，通過反復(fù)增加頂點數(shù)來進(jìn)行直線段擬合曲線．方法1:直線段分裂方法20.線段合并(merging)是指用一條直線段盡量多地擬合邊緣表中的邊緣點．當(dāng)邊緣點離直線段太遠(yuǎn)而無法用該直線段擬合時，那么開始新的直線段擬合．合并方法也稱為自底而上(bottom-upmerging)的多線段擬合方法．方法2:直線段合并方法21.確定邊緣點離直線段的距離有許多種方法．一種方法是使用序貫最小二乘法，完成直線段到邊緣點的最小二乘法擬合，并在每次處理新的邊緣點時遞增地更新線段參數(shù)．?dāng)M合算法將計算直線段模型和邊緣點之間的偏查平方．當(dāng)偏差超過某一閾值時，引進(jìn)一個頂點，并將上一個線段的端點作為新的起點開始新的直線段擬合．

22.誤差帶算法是另一種確定頂點位置的方法，主要工作是計算兩條平行且離中心線距離為ε的直線段．ε值表示離中心直線的絕對偏離值．只要新的邊緣在誤差帶內(nèi)，就可以用當(dāng)前擬合直線表示該邊緣．當(dāng)新的邊緣增加到線段內(nèi)時，線段的參數(shù)要重新計算．逼近直線段不必與誤差帶邊保持平行．位于線段端點的頂點是下一線段的起點．23.自頂而下的迭代分解方法和自底而上的合并方法組合起來，形成合并和分裂算法．單獨使用分裂或合并算法時，成功率往往不是很高，改進(jìn)的方法是交叉使用分裂和合并算法．分解過程以后，如果新的線段以很小的標(biāo)準(zhǔn)誤差擬合邊緣，那么允許用單一直線段代替鄰接線段．請注意，由于多直線段總是比單直線段的擬合誤差小，因此很有必要使用標(biāo)準(zhǔn)化誤差．在線段合并后，新的線段可能在不同點處分裂．這樣，分裂和合并交替作用直到?jīng)]有線段被合并和分裂為止．方法3:分裂和合并24.(a)原始邊緣點集(b)自底而上的邊緣合并方法產(chǎn)生的壞角點估計(c)漏掉的真實角點位置由分裂和合并過程來修補25.算法7.1一種有效的多線段擬合算法從邊緣表中的前k個邊緣構(gòu)成的子表開始；用直線段擬合子表中第一和最后一個邊緣之間的邊緣點；如果某點的標(biāo)準(zhǔn)化最大誤差太大，那么將子表縮到最大誤差對應(yīng)的邊緣點處，回到步驟；這樣一直進(jìn)行下去，就可以得到第一條擬合直線段，這實際上是分裂算法．置當(dāng)前新線段為舊線段，向前移動邊緣窗口使得k個邊緣在子表中，返回步驟。用分裂算法求取第二條擬合直線段．比較當(dāng)前直線段和原直線段的方向，如果它們具有相似方向，那么將這兩條直線段合并,這是合并算法；26.有三種類型的錐形曲線：雙曲線，拋物線和橢圓，其中圓是橢圓的一種特殊情況．在幾何上，錐形曲線定義為錐體與平面的相交曲線.7.2.2錐形曲線(二次曲線)圓錐曲線表示如下：27.用直線段擬合一個圓弧可能需要許多個直線段才能滿足擬合誤差．如果將這些直線段用一個圓弧段來擬合，那么僅需要一條圓弧段即可．因此可見，圓弧段擬合比直線段能擬合得更緊湊。圓弧段擬合是在多邊形的頂點上進(jìn)行的。〔1〕圓弧段28.1.將頂點窗口初始化為僅包含前兩個直線段的三個頂點;2.計算兩個直線段對應(yīng)的輪廓長度與兩個端點之間距離的比值．如果這一比值很大，那么保存第一個直線段不動，將窗口向前移動一個頂點，然后重復(fù)這一步;3.用一個圓來擬合這三個頂點;4.計算標(biāo)準(zhǔn)化最大誤差和符號變化數(shù);5.假設(shè)標(biāo)準(zhǔn)化最大誤差太大或符號數(shù)太小，那么保存第一個直線段不動，將窗口向前移動一個頂點，返回步驟2;6.如果圓弧段擬合成功，那么盡力讓該圓弧段合并下一個直線段．重復(fù)這一過程，直到?jīng)]有直線段被合并為止;7.圓弧段擬合結(jié)束后，移動頂點窗口到下一個多直線段頂點，返回步驟2．算法7．2用圓弧段代替直線段算法29.圓錐曲線可以擬合輪廓多直線段上的三個頂點．將圓錐曲線段連接在一起的點稱為結(jié)點．圓錐樣條曲線是圓錐曲線的一個序列，它們的端點和端點連接在一起，在結(jié)點處具有相等的正切，以便使兩個鄰接曲線段之間平滑過渡．(2)圓錐曲線30.圓錐樣條中的每一個圓錐曲線由兩個端點、兩個正切和第三點確定．結(jié)點位于多線段頂點之間：第三點定義為：31.7.3樣條曲線

早期繪圖員在制圖時，使用一種富有彈性的細(xì)長條，稱為樣條。用壓鐵將樣條固定在假設(shè)干樣點上，然后沿樣條可以畫出很光滑的曲線，人們將該曲線稱為樣條曲線．從數(shù)學(xué)上講，樣條曲線是用分段多項式表示的一個函數(shù)，在其連接點處具有連續(xù)的一階和二階導(dǎo)數(shù)．樣條曲線有著許多應(yīng)用．在數(shù)據(jù)分析中，當(dāng)沒有適宜的函數(shù)模型時，可以選用樣條函數(shù)擬合數(shù)據(jù)點．在計算機圖形和計算機輔助設(shè)計中，樣條函數(shù)用來表示自由曲線．在機器視覺中，假設(shè)沒有表示曲線的適宜模型時，樣條函數(shù)可以提供曲線的通用表示形式．舉MSWORD里的樣條曲線的例子！32.幾何等效和參數(shù)等效的概念:兩條曲線在幾何上等效，是指它們連接相同的點集，即它們在空間上對應(yīng)著相同的形狀〔或點集〕．如果兩條曲線的方程一樣，那么兩條曲線在參數(shù)上等效．33.顯然，參數(shù)等效性比幾何等效性更穩(wěn)定．兩條曲線可以是幾何上等效但可以具有不同的參數(shù)表示式，這是機器視覺中曲線擬合的一個重要概念．比方，機器視覺系統(tǒng)可以產(chǎn)生基于三次樣條曲線的表示，其在幾何上非常接近于物體輪廓的真實表示，但在參數(shù)意義上，表示可能完全不同．在物體識別應(yīng)用方面和工業(yè)零件圖像與其模型匹配應(yīng)用中，通過比較三次樣條曲線的參數(shù)形式實現(xiàn)匹配幾乎是不可能的，在這種情況下，比較必須基于幾何等效性．34.在數(shù)學(xué)上，光滑程度的定量描述是：函數(shù)(曲線)的k階導(dǎo)數(shù)存在且連續(xù)，那么稱該曲線具有k階光滑性。光滑性的階次越高，那么越光滑。是否存在較低次的分段多項式到達(dá)較高階光滑性的方法？三次樣條曲線就是一個很好的例子。7.3.1三次樣條曲線35.三次樣條是三次曲線的一個序列樣條中的每一個三次曲線稱為樣條段連結(jié)樣條段的邊緣點稱為結(jié)點36.三次樣條曲線是一個三次多項式函數(shù)的集合：要確定這個三次樣條曲線，就要確定等4n個參數(shù)。37.邊界條件:以上總共4n個方程！38.7.3.2B樣條曲線式中B0,B1,B2,B3為參數(shù)的三次多項式，如何確定上式四個多項式所對應(yīng)的16個參數(shù)?B樣條曲線是由結(jié)點引導(dǎo)的逐段多項式曲線，是一種平滑和內(nèi)插技術(shù)．B樣條與上述三次樣條曲線不同，它不必通過結(jié)點，我們將這種結(jié)點稱為引導(dǎo)結(jié)點．引導(dǎo)結(jié)點序列為P0,P1,…,Pn，那么三次B樣條多項式為：39.7.3.2B樣條曲線相鄰曲線段Pi(t),Pi+1(t)端點以及一階二階導(dǎo)數(shù)必須連續(xù)的條件提供15個等式:五個等式五個等式40.41.B樣條曲線示意圖〔a〕直線(b)二次B樣條曲線〔c〕三次B樣條曲線通常，m次的樣條包含在由m+1控制點確定的多邊形內(nèi)。42.7.4曲線回歸逼近

直線段、圓弧段、圓錐曲線和三次樣條擬合邊緣點的方法屬于一般回歸問題，主要用于端點之間的曲線擬合．這些算法都假定邊緣的位置可以精確計算，甚至可能使用子像素計算方法．這種回歸算法沒有使用端點之間的邊緣點信息，因此曲線的擬合精度主要取決于端點的位置精度．本節(jié)討論的曲線回歸逼近方法將使用所有邊緣點信息．

43.一般曲線擬合問題是一個曲線的回歸問題,曲線用p個參數(shù)的隱函數(shù)表示：在無噪聲情況下，通過p次觀測產(chǎn)生的p個方程來求解p個未知曲線參數(shù)．不幸的是在大多數(shù)場合，由于噪聲的原因，這一直接方法不是很有效．實際的應(yīng)用常常需要使用邊緣表中所有信息來獲取這些參數(shù)的最正確估計．曲線擬合〔預(yù)估〕問題就是指這種曲線模型擬合一個邊緣點集：44.〔1〕全回歸方法〔最小二乘法〕對數(shù)據(jù)點與回歸模型之間垂直距離平方和進(jìn)行極小化.最小二次回歸方法在計算機視覺中主要用于曲線擬合．當(dāng)誤差服從正態(tài)分布時，最小二次方法是最適宜的擬合方法．45.為觀測值例子：〔直線〕直線的極坐標(biāo)形式：46.對于正態(tài)分布的點集，最小二乘法可以得到最正確估計，但對于不服從正態(tài)分布的局外點很敏感。全回歸方法的缺點47.〔2〕魯棒回歸法設(shè)Z是n個數(shù)據(jù)點的集合，將Z集合中任意m個點的坐標(biāo)設(shè)置成任意值〔局外點〕，構(gòu)成一個含有m個任意點的集合Z’．回歸預(yù)估器:由局外點引起的偏差：48.潰點定義:潰點定義：潰點是指局外點占整個數(shù)據(jù)的一個最大比例值，當(dāng)局外點數(shù)不超過這個值時，無論局外點如何不正確，都不會使預(yù)估算法產(chǎn)生任意的錯誤估計.此處課本有誤！49.設(shè)置潰點的根本思想是定量分析局外點的數(shù)量在數(shù)據(jù)點數(shù)量n中所占比例增加時對ε值的影響程度．當(dāng)增加到一定數(shù)量時，ε無界，這就是潰點．當(dāng)?shù)陀跐Ⅻc時，回歸估計器可以完全拒絕局外點，或使得局外點對預(yù)估結(jié)果影響很?。?dāng)高于潰點時，局外點可以驅(qū)使預(yù)估器產(chǎn)生任意的解案，答案將取決于局外點而不是合法數(shù)據(jù)．換句話說，預(yù)估器所提供的結(jié)果是不可預(yù)估的．50.

最小中值二乘回歸方法被證明是解決大量局外點回歸問題的非常簡單、有效的方法．容錯高達(dá)百分之五十的局外點，也就意味著數(shù)據(jù)點集中，有一半的數(shù)據(jù)可以取任意值而不會嚴(yán)重地影響回歸結(jié)果．在最小中值二次回歸方法中，模型參數(shù)的估計由極小化殘差平方的中值求得:最小中值二乘回歸方法51.假定有n個數(shù)據(jù)和p個參數(shù)的線性模型在n各個數(shù)據(jù)點集中，隨機地選擇p個點;用模型擬合p個點;計算殘差平方的中值;擬合過程重復(fù)進(jìn)行直到得到足夠小的殘差平方中值.算法7.3最小中值二乘回歸方法52.Hough變換是基于表決原理的參數(shù)估計方法．在圖像處理領(lǐng)域，是一種重要的形狀檢測技術(shù).根本思想：圖像中每一點對參數(shù)組合進(jìn)行表決，贏得多數(shù)票的參數(shù)組合為勝者〔結(jié)果〕．7.5Hough[發(fā)音hok]變換53.以檢測直線為例：以(x,y)為自變量，(m,c)為因變量每個點(x,y)對應(yīng)于空間(m,c)上的一條直線yxcm54.直線方程表示存在的問題：垂直時斜率〔m〕趨于無窮大！極坐標(biāo)表示：

空間與空間的變換yx55.圖7.16Hough變換示意圖。左邊:為圖像空間右邊:為Hough變換空間(