工業(yè)機(jī)器視覺課程9輪廓表示

第7章

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

輪廓表示的評(píng)價(jià)標(biāo)準(zhǔn)：

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

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

有效：輪廓應(yīng)適合于后續(xù)應(yīng)用階段的計(jì)算．精確表示輪廓的影響因素：用于輪廓建模的曲線形式；曲線擬合算法的性能；邊緣位置估計(jì)的精確度。定義：邊緣表是邊緣點(diǎn)或邊緣段的有序集合,輪廓的最簡單表示形式。輪廓是邊緣表或用于表示邊緣表的曲線。邊界是包圍一個(gè)區(qū)域的封閉輪廓。輪廓曲線擬合通常采用內(nèi)插曲線或逼近曲線來實(shí)現(xiàn)．已知一組稱為控制點(diǎn)的坐標(biāo)點(diǎn)，內(nèi)插是指一條曲線擬合這組控制點(diǎn)，使得曲線通過所有的控制點(diǎn)；逼近是指一條曲線擬合這組這組控制點(diǎn)，使得這條曲線非常接近這些控制點(diǎn)而無需一定通過這些點(diǎn)．

設(shè)Pi=(xi,yi)是邊緣表中第i個(gè)邊緣坐標(biāo)．(1)k斜率是在邊緣表相距k個(gè)邊緣點(diǎn)的兩個(gè)邊緣點(diǎn)之間的（角）方向向量．(2)左k斜率是Pi指向Pi–k的方向，(3)右k斜率是Pi指向Pi+k方向．(4)k曲率是左右k斜率之差值。7.1數(shù)字曲線及其表示(6)輪廓端點(diǎn)之間的距離為(5)數(shù)字曲線的長度可以近似為像素之間的線段和：數(shù)字曲線表示1－鏈碼定義：

鏈碼是沿著輪廓記錄邊緣表的一種表示方法．鏈碼規(guī)定了邊緣表中每一個(gè)邊緣點(diǎn)的輪廓方向，其中方向被量化為四個(gè)或八個(gè)方向中的一個(gè)．曲線的鏈碼是：6022222021013444444454577012其差分鏈碼是：220000627712100000017120111鏈碼的特殊性質(zhì):一個(gè)物體很容易實(shí)現(xiàn)45

角旋轉(zhuǎn)．如果一個(gè)物體旋轉(zhuǎn)Nx45°，可由原鏈碼值加上N后再模8得到．N逆時(shí)針為正，順時(shí)針為負(fù)。鏈碼的微分，也稱差分碼，由原碼的一階差分求得．鏈碼差分是關(guān)于旋轉(zhuǎn)不變的邊界描述方法．鏈碼的問題：表示某一點(diǎn)正切方向的集合是有限的（４－鄰接鏈碼有4個(gè)，8－鄰接鏈碼有8個(gè)）。用任意的正切方向來表示輪廓可以克服鏈碼的只能用有限個(gè)正切方向來表示輪廓的局限性．假定從邊緣表開始，計(jì)算正切

和弧長s，畫出正切同弧長的關(guān)系圖，稱作s圖．?dāng)?shù)字曲線表示2－K斜率一個(gè)輪廓及其s圖．對(duì)于封閉輪廓，s圖是一個(gè)周期曲線．三種常用的曲線模型擬合邊緣點(diǎn)的方法：(1)直線段(LineSegment)(2)圓錐曲線段(ConicSection)(3)三次樣條曲線段(CubicSpline)．用曲線模型擬合邊緣點(diǎn)應(yīng)考慮如下兩個(gè)問題：(1)用什么方法進(jìn)行邊緣點(diǎn)的曲線模型擬合？(2)如何測量擬合的逼近程度？7.2曲線擬合設(shè)di是擬合曲線和候選點(diǎn)之間的誤差．最大絕對(duì)誤差(MaximumAbsoluteError,MAE):

測量最壞情況下邊緣點(diǎn)偏離曲線的距離，均方差(MeanSquaredError,MSE):

給出邊緣點(diǎn)偏離擬合曲線的總的測度，常用的誤差測量方法規(guī)范化最大誤差(NormalizedMaximumError,NME):

最大絕對(duì)誤差與曲線長度S之比，誤差符號(hào)變化數(shù):

用來表示輪廓邊緣模型的曲線適合程度的測度．符號(hào)變化是一種評(píng)價(jià)擬合好壞的很有用的參數(shù)．比如，用直線段逼近邊緣表，并檢測符號(hào)變化數(shù)．如果符號(hào)變化一次，則說明邊緣點(diǎn)可以由直線段來逼近；符號(hào)變化兩次，說明邊緣可以由二次曲線逼近；符號(hào)變化三次，說明邊緣模型是三次曲線，依此類推．如果符號(hào)變化數(shù)量很大，則意味著曲線復(fù)雜度增加一點(diǎn)將不能顯著地改善擬合效果．一種好的擬合所對(duì)應(yīng)的符號(hào)變化具有隨機(jī)模式．相同符號(hào)連續(xù)出現(xiàn)多次說明存在擬合系統(tǒng)誤差，這種誤差可能是由于錯(cuò)誤的曲線模型引起的．

曲線長度與端點(diǎn)距離之比:

曲線復(fù)雜程度的測度．多直線段是指端點(diǎn)連結(jié)端點(diǎn)的直線段序列，直線段序列的連接點(diǎn)稱為頂點(diǎn)．最大規(guī)范誤差常常作為線段擬合邊緣列表好壞的量度.7.2.1多直線段表示自頂而下的分裂算法(top-downsplitting)：將整條曲線作為初始曲線，通過反復(fù)增加頂點(diǎn)數(shù)來進(jìn)行直線段擬合曲線．方法1:直線段分裂方法線段合并(merging)是指用一條直線段盡量多地?cái)M合邊緣表中的邊緣點(diǎn)．當(dāng)邊緣點(diǎn)離直線段太遠(yuǎn)而無法用該直線段擬合時(shí)，則開始新的直線段擬合．合并方法也稱為自底而上(bottom-upmerging)的多線段擬合方法．方法2:直線段合并方法確定邊緣點(diǎn)離直線段的距離有許多種方法．一種方法是使用序貫最小二乘法，完成直線段到邊緣點(diǎn)的最小二乘法擬合，并在每次處理新的邊緣點(diǎn)時(shí)遞增地更新線段參數(shù)．?dāng)M合算法將計(jì)算直線段模型和邊緣點(diǎn)之間的偏查平方．當(dāng)偏差超過某一閾值時(shí)，引進(jìn)一個(gè)頂點(diǎn)，并將上一個(gè)線段的端點(diǎn)作為新的起點(diǎn)開始新的直線段擬合．誤差帶算法是另一種確定頂點(diǎn)位置的方法，主要工作是計(jì)算兩條平行且離中心線距離為ε的直線段．ε值表示離中心直線的絕對(duì)偏離值．只要新的邊緣在誤差帶內(nèi)，就可以用當(dāng)前擬合直線表示該邊緣．當(dāng)新的邊緣增加到線段內(nèi)時(shí)，線段的參數(shù)要重新計(jì)算．逼近直線段不必與誤差帶邊保持平行．位于線段端點(diǎn)的頂點(diǎn)是下一線段的起點(diǎn)．

自頂而下的迭代分解方法和自底而上的合并方法組合起來，形成合并和分裂算法．單獨(dú)使用分裂或合并算法時(shí)，成功率往往不是很高，改進(jìn)的方法是交叉使用分裂和合并算法．分解過程以后，如果新的線段以很小的規(guī)范誤差擬合邊緣，則允許用單一直線段代替鄰接線段．請注意，由于多直線段總是比單直線段的擬合誤差小，因此很有必要使用規(guī)范化誤差．在線段合并后，新的線段可能在不同點(diǎn)處分裂．這樣，分裂和合并交替作用直到?jīng)]有線段被合并和分裂為止．

方法3:分裂和合并(a)原始邊緣點(diǎn)集．(b)自底而上的邊緣合并方法產(chǎn)生的壞角點(diǎn)估計(jì)．(c)漏掉的真實(shí)角點(diǎn)位置由分裂和合并過程來修補(bǔ)算法7.1一種有效的多線段擬合算法

從邊緣表中的前k個(gè)邊緣構(gòu)成的子表開始；

用直線段擬合子表中第一和最后一個(gè)邊緣之間的邊緣點(diǎn)；

如果某點(diǎn)的規(guī)范化最大誤差太大，則將子表縮到最大誤差對(duì)應(yīng)的邊緣點(diǎn)處，回到步驟

；這樣一直進(jìn)行下去，就可以得到第一條擬合直線段，這實(shí)際上是分裂算法．

置當(dāng)前新線段為舊線段，向前移動(dòng)邊緣窗口使得k個(gè)邊緣在子表中，返回步驟

。用分裂算法求取第二條擬合直線段．

比較當(dāng)前直線段和原直線段的方向，如果它們具有相似方向，則將這兩條直線段合并,這是合并算法；有三種類型的錐形曲線：雙曲線，拋物線和橢圓，其中圓是橢圓的一種特殊情況．在幾何上，錐形曲線定義為錐體與平面的相交曲線.7.2.2錐形曲線(二次曲線)圓錐曲線表示如下：用直線段擬合一個(gè)圓弧可能需要許多個(gè)直線段才能滿足擬合誤差．如果將這些直線段用一個(gè)圓弧段來擬合，則僅需要一條圓弧段即可．因此可見，圓弧段擬合比直線段能擬合得更緊湊。圓弧段擬合是在多邊形的頂點(diǎn)上進(jìn)行的。(1)圓弧段1.將頂點(diǎn)窗口初始化為僅包含前兩個(gè)直線段的三個(gè)頂點(diǎn);2.計(jì)算兩個(gè)直線段對(duì)應(yīng)的輪廓長度與兩個(gè)端點(diǎn)之間距離的比值．如果這一比值很大，則保留第一個(gè)直線段不動(dòng)，將窗口向前移動(dòng)一個(gè)頂點(diǎn)，然后重復(fù)這一步;3.用一個(gè)圓來擬合這三個(gè)頂點(diǎn);4.計(jì)算規(guī)范化最大誤差和符號(hào)變化數(shù);5.若規(guī)范化最大誤差太大或符號(hào)數(shù)太小，則保留第一個(gè)直線段不動(dòng)，將窗口向前移動(dòng)一個(gè)頂點(diǎn)，返回步驟2;6.如果圓弧段擬合成功，則盡力讓該圓弧段合并下一個(gè)直線段．重復(fù)這一過程，直到?jīng)]有直線段被合并為止;7.圓弧段擬合結(jié)束后，移動(dòng)頂點(diǎn)窗口到下一個(gè)多直線段頂點(diǎn)，返回步驟2．算法7．2用圓弧段代替直線段算法圓錐曲線可以擬合輪廓多直線段上的三個(gè)頂點(diǎn)．將圓錐曲線段連接在一起的點(diǎn)稱為結(jié)點(diǎn)．圓錐樣條曲線是圓錐曲線的一個(gè)序列，它們的端點(diǎn)和端點(diǎn)連接在一起，在結(jié)點(diǎn)處具有相等的正切，以便使兩個(gè)鄰接曲線段之間平滑過渡．(2)圓錐曲線圓錐樣條中的每一個(gè)圓錐曲線由兩個(gè)端點(diǎn)、兩個(gè)正切和第三點(diǎn)確定．結(jié)點(diǎn)位于多線段頂點(diǎn)之間：第三點(diǎn)定義為：7．3樣條曲線

早期繪圖員在制圖時(shí)，使用一種富有彈性的細(xì)長條，稱為樣條。用壓鐵將樣條固定在若干樣點(diǎn)上，然后沿樣條可以畫出很光滑的曲線，人們將該曲線稱為樣條曲線．從數(shù)學(xué)上講，樣條曲線是用分段多項(xiàng)式表示的一個(gè)函數(shù)，在其連接點(diǎn)處具有連續(xù)的一階和二階導(dǎo)數(shù)．樣條曲線有著許多應(yīng)用．在數(shù)據(jù)分析中，當(dāng)沒有合適的函數(shù)模型時(shí)，可以選用樣條函數(shù)擬合數(shù)據(jù)點(diǎn)．在計(jì)算機(jī)圖形和計(jì)算機(jī)輔助設(shè)計(jì)中，樣條函數(shù)用來表示自由曲線．在機(jī)器視覺中，若沒有表示曲線的合適模型時(shí)，樣條函數(shù)可以提供曲線的通用表示形式．幾何等效和參數(shù)等效是兩個(gè)不同的概念．兩條曲線在幾何上等效，是指它們連接相同的點(diǎn)集，即它們在空間上對(duì)應(yīng)著相同的形狀（或點(diǎn)集）．如果兩條曲線的方程一樣，則兩條曲線在參數(shù)上等效．顯然，參數(shù)等效性比幾何等效性更穩(wěn)定．兩條曲線可以是幾何上等效但可以具有不同的參數(shù)表示式，這是機(jī)器視覺中曲線擬合的一個(gè)重要概念．比如，機(jī)器視覺系統(tǒng)可以產(chǎn)生基于三次樣條曲線的表示，其在幾何上非常接近于物體輪廓的真實(shí)表示，但在參數(shù)意義上，表示可能完全不同．在物體識(shí)別應(yīng)用方面和工業(yè)零件圖像與其模型匹配應(yīng)用中，通過比較三次樣條曲線的參數(shù)形式實(shí)現(xiàn)匹配幾乎是不可能的，在這種情況下，比較必須基于幾何等效性．比分段線性插值更光滑

xyxi-1xiab在數(shù)學(xué)上，光滑程度的定量描述是：函數(shù)(曲線)的k階導(dǎo)數(shù)存在且連續(xù)，則稱該曲線具有k階光滑性。光滑性的階次越高，則越光滑。是否存在較低次的分段多項(xiàng)式達(dá)到較高階光滑性的方法？三次樣條插值就是一個(gè)很好的例子。三次樣條插值第一型邊界條件:三彎矩方程和三轉(zhuǎn)角方程三次樣條是三次曲線的一個(gè)序列樣條中的每一個(gè)三次曲線稱為樣條段連結(jié)樣條段的邊緣點(diǎn)稱為結(jié)點(diǎn)．7.3.1三次樣條曲線三次樣條具有足夠的自由度來逼近邊緣段位置和方向．我們知道，大多數(shù)邊緣檢測算法同時(shí)提供邊緣方向（梯度角）和邊緣位置估計(jì)．在直線段、圓弧段和圓錐曲線的擬合中，僅僅使用了邊緣的位置信息．

7.3.2B樣條曲線式中B0,B1,B2,B3為參數(shù)的三次多項(xiàng)式．如何確定上式四個(gè)多項(xiàng)式所對(duì)應(yīng)的16個(gè)參數(shù)?B樣條曲線是由結(jié)點(diǎn)引導(dǎo)的逐段多項(xiàng)式曲線，是一種平滑和內(nèi)插技術(shù)．B樣條與上述三次樣條曲線不同，它不必通過結(jié)點(diǎn)，我們將這種結(jié)點(diǎn)稱為引導(dǎo)結(jié)點(diǎn)．已知引導(dǎo)結(jié)點(diǎn)序列為P0,P1,…,Pn，則三次B－樣條多項(xiàng)式為：7.3.2B樣條曲線相鄰曲線段Pi(t),Pi+1(t)端點(diǎn)以及一階二階導(dǎo)數(shù)必須連續(xù)的條件提供15個(gè)等式:五個(gè)等式五個(gè)等式B樣條曲線示意圖（a）直線(b)二次B樣條曲線（c）三次B樣條曲線通常，m次的樣條包含在由m+1控制點(diǎn)確定的多邊形內(nèi)。7．4曲線回歸逼近直線段、圓弧段、圓錐曲線和三次樣條擬合邊緣點(diǎn)的方法屬于一般回歸問題，主要用于端點(diǎn)之間的曲線擬合．這些算法都假定邊緣的位置可以精確計(jì)算，甚至可能使用子像素計(jì)算方法．這種回歸算法沒有使用端點(diǎn)之間的邊緣點(diǎn)信息，因此曲線的擬合精度主要取決于端點(diǎn)的位置精度．本節(jié)討論的曲線最佳逼近方法將使用所有邊緣點(diǎn)信息．一般曲線擬合問題是一個(gè)曲線的回歸問題,曲線用p個(gè)參數(shù)的隱函數(shù)表示：在無噪聲情況下，通過p次觀測產(chǎn)生的p個(gè)方程來求解p個(gè)未知曲線參數(shù)．不幸的是在大多數(shù)場合，由于噪聲的原因，這一直接方法不是很有效．實(shí)際的應(yīng)用常常需要使用邊緣表中所有信息來獲取這些參數(shù)的最佳估計(jì)．曲線預(yù)估問題就是指這種曲線模型擬合一個(gè)邊緣點(diǎn)集為觀測值例子：（直線）全回歸方法(最小二乘法)對(duì)數(shù)據(jù)點(diǎn)與回歸模型之間垂直距離平方和進(jìn)行極小化.最小二次回歸方法在計(jì)算機(jī)視覺中主要用于曲線擬合．當(dāng)誤差服從正態(tài)分布時(shí)，最小二次方法是最合適的擬合方法．對(duì)于正態(tài)分布的點(diǎn)集，最小二乘法可以得到最佳估計(jì)，但對(duì)于不服從正態(tài)分布的局外點(diǎn)很敏感。魯棒回歸法設(shè)Z是n個(gè)數(shù)據(jù)點(diǎn)的集合，將Z集合中任意m個(gè)點(diǎn)的坐標(biāo)設(shè)置成任意值（局外點(diǎn)），構(gòu)成一個(gè)含有m個(gè)任意點(diǎn)的集合Z’．已知回歸預(yù)估器:由局外點(diǎn)引起的偏差：設(shè)置潰點(diǎn)的基本思想是定量分析局外點(diǎn)的數(shù)量在數(shù)據(jù)點(diǎn)數(shù)量n中所占比例增加時(shí)對(duì)ε

值的影響程度．當(dāng)增加到一定數(shù)量時(shí)，ε無界，這就是潰點(diǎn)．當(dāng)?shù)陀跐Ⅻc(diǎn)時(shí)，回歸估計(jì)器可以完全拒絕局外點(diǎn)，或使得局外點(diǎn)對(duì)預(yù)估結(jié)果影響很?。?dāng)高于潰點(diǎn)時(shí)，局外點(diǎn)可以驅(qū)使預(yù)估器產(chǎn)生任意的解案，答案將取決于局外點(diǎn)而不是合法數(shù)據(jù)．換句話說，預(yù)估器所提供的結(jié)果是不可預(yù)估的．

潰點(diǎn)定義:潰點(diǎn)定義：潰點(diǎn)是指局外點(diǎn)占整個(gè)數(shù)據(jù)的一個(gè)最小比例值，當(dāng)局外點(diǎn)數(shù)不超過這個(gè)值時(shí)，無論局外點(diǎn)如何不正確，都不會(huì)使預(yù)估算法產(chǎn)生任意的錯(cuò)誤估計(jì).簡單、被證明是解決大量局外點(diǎn)回歸問題的非常有效的方法．容錯(cuò)高達(dá)百分之五十的局外點(diǎn)，也就意味著數(shù)據(jù)點(diǎn)集中，有一半的數(shù)據(jù)可以取任意值而不會(huì)嚴(yán)重地影響回歸結(jié)果．在最小中值二次回歸方法中，模型參數(shù)的估計(jì)由極小化殘差平方的中值求得:最小中值二乘回歸方法假定有n個(gè)數(shù)據(jù)和p個(gè)參數(shù)的線性模型在n各個(gè)數(shù)據(jù)點(diǎn)集中，隨機(jī)地選擇p個(gè)點(diǎn);用模型擬合p個(gè)點(diǎn);計(jì)算殘差平方的中值;擬合過程重復(fù)進(jìn)行直到得到足夠小的殘差平方中值.算法7.3最小中值二乘回歸方法Hough變換是基于表決原理的參數(shù)估計(jì)方法．在圖像處理領(lǐng)域，是一種重要的形狀檢測技術(shù).基本思想：圖像中每一點(diǎn)對(duì)參數(shù)組合進(jìn)行表決，贏得多數(shù)票的參數(shù)組合為勝者（結(jié)果）．7．5Hough變換以檢測直線為例：以(x,y)為自變量，(m,c)為因變量每個(gè)點(diǎn)(x,y)對(duì)應(yīng)于空間(m,c)上的一條直線yxcm直線方程表示存在的問題？極坐