第五章 形狀分析與描述

第五章形狀分析與描述第1頁，課件共33頁，創(chuàng)作于2023年2月

輪廓表示的評價標準：簡單：輪廓應該是一種簡潔的表示。精確：輪廓應能精確地逼近圖象特征。有效：輪廓應適合于后處理階段的計算。

決定輪廓表示精確性的主要因素有以下三個方面： （1）用于輪廓建模的曲線形式； （2）曲線擬合算法的性能； （3）邊緣位置估計的精度。 輪廓的最簡單表示形式是邊緣有序表。這種表示的精度就是邊緣估計的精度，但其表示的緊湊性是最差的，后處理也不方便，因此不是一種高效的圖象分析方法。 用適當?shù)那€模型來擬合邊緣會提高精確度，因為曲線模型擬合邊緣時往往具有均值化效應，因此可以減少邊緣位置誤差。曲線模型也會提高輪廓表示的經(jīng)濟性，為后處理提供了一種更簡單、更緊湊的表示。第2頁，課件共33頁，創(chuàng)作于2023年2月 已知一組控制點，曲線擬合常采用內(nèi)插曲線或逼近曲線來實現(xiàn)。

內(nèi)插：指使得擬合曲線通過所有的控制點。

逼近：指使擬合曲線非常接近這些控制點，而無需一定通過這些控制點。 平面曲線函數(shù)可表示為三種形式： （1）顯式； （2）隱式：； （3）參數(shù)式：，其中u是某一參數(shù)； 函數(shù)的顯式表示很少用在計算機視覺中，主要原因是平面上的曲線可能卷曲，致使一個x值可能對應曲線上多個y值。第3頁，課件共33頁，創(chuàng)作于2023年2月5.1數(shù)字曲線及其表示 下面討論一組計算曲線幾何元素的算法，包括輪廓長度、正切方向、曲率等。由于相鄰象素間的量化增量是45o，因此，精確計算斜率和曲率是很困難的。 估計正切方向的基本思路是使用邊緣表中非鄰接的邊緣點，這就允許存在一個較大可能的正切方向集合。 設是邊緣表中第i個邊緣坐標。K斜率是在邊緣表中相距K個邊緣點的兩個邊緣點之間的方向矢量。進一步又分為左K斜率和右K斜率。 K曲率是左、右K斜率之差。 假定邊緣表中有n個邊緣。則數(shù)字曲線的長度S及輪廓端點之間的距離D可表示為：第4頁，課件共33頁，創(chuàng)作于2023年2月一、鏈碼 鏈碼是沿著輪廓記錄邊緣表的一種表示方法。分為4方向鏈碼和8方向鏈碼。如用8鄰點鏈碼表示一條曲線，即從邊緣表中的第一個邊緣點開始，沿著輪廓按逆時針方向行走，行走方向用8個鏈碼中一個表示。

第5頁，課件共33頁，創(chuàng)作于2023年2月 下圖所示曲線的鏈碼是：602222202101344444454577012

其差分鏈碼是：22000062771210000017120111第6頁，課件共33頁，創(chuàng)作于2023年2月 將上頁圖中曲線旋轉90o后如上圖。 曲線的鏈碼是：024444424323566666676711234 其差分鏈碼不變。二、斜率表示法第7頁，課件共33頁，創(chuàng)作于2023年2月5.2曲線擬合 常用的曲線模型有：直線段、圓錐曲線和三次樣條曲線。一般，擬合之前應考慮如下兩個問題： （1）用什么方法進行邊緣點曲線模型擬合？ （2）如何測量擬合的逼近程度？ 現(xiàn)假設邊緣位置足夠精確，不會對擬合結果產(chǎn)生影響。以下討論用曲線模型擬合邊緣點的方法。 設di是邊緣點到一條擬合曲線的距離（含正負號），在曲線同一側時具有相同的符號。以下是一些常用的用于衡量曲線擬合效果的方法。 （1）最大絕對誤差（MAE） （2）均方差（MSE） （3）規(guī)范化最大誤差 （4）誤差符號變化次數(shù) （5）曲線長度與端點距離之比第8頁，課件共33頁，創(chuàng)作于2023年2月

一、多直線段 多直線段是指端點連接端點的直線段序列，直線段序列的連接點稱為頂點。多線段算法的輸入值是邊緣點有序表 擬合邊緣表并把第一個邊緣點和最后一個邊緣點 連接起來的直線段公式如下：

上式可改寫成： 其中： 而是邊緣點和之間的距離。 任給一點，設，則r的符號可用來計算符號變化次數(shù)。點與擬合直線段的距離為： 規(guī)范化最大誤差為：第9頁，課件共33頁，創(chuàng)作于2023年2月

（1）多直線段分裂 自頂向下的分裂算法是將整條曲線作為初始曲線，通過反復增加頂點來用直線段擬合曲線。直到所有的直線段對應的規(guī)范化最大誤差均小于某一閾值為止。該過程也稱為迭代分解。第10頁，課件共33頁，創(chuàng)作于2023年2月 （2）線段合并 線段合并是指用一直線段盡量多地擬合邊緣表中的邊緣點。當邊緣點離直線太遠而無法用該直線段擬合時，則開始新的直線段擬合。（自底而上合并的多線段擬合方法）第11頁，課件共33頁，創(chuàng)作于2023年2月 （3）分裂與合并 將多直線分裂與線段合并方法組合起來，形成合并與分裂算法。第12頁，課件共33頁，創(chuàng)作于2023年2月二、二次曲線 二次曲線的一般表示如下： 二次曲線也稱為圓錐曲線，包括：圓、橢圓、拋物線、雙曲線。

（1）圓弧段 （2）圓錐曲線第13頁，課件共33頁，創(chuàng)作于2023年2月5.3樣條曲線

樣條：富有彈性的細長條。

樣條曲線：將樣條上的若干點固定，沿樣條畫出的光滑曲線。 在數(shù)學意義上，樣條曲線是用分段多項式表示的一個函數(shù)，在其連接點處具有連續(xù)的一階和二階導數(shù)。 樣條曲線有很多應用。在數(shù)學分析中，當沒有合適的函數(shù)模型時，可選用樣條函數(shù)擬合數(shù)據(jù)點；在計算機圖形學和計算機輔助設計中，樣條函數(shù)用來表示自由曲線；在計算機視覺中，若沒有表示曲線的合適模型時，樣條函數(shù)可以提供曲線的通用表示形式。 需指出，幾何等效和參數(shù)等效是兩個不同的概念。

幾何等效：是指它們連接相同的點集（即在空間上對應著相同的形狀）。

參數(shù)等效：是指兩條曲線的方程相同。 顯然，參數(shù)等效比幾何等效更穩(wěn)定。兩條曲線可以是幾何上等效但可具有不同的參數(shù)表示式，這是計算機視覺中的一個重要概念。 在計算機視覺的形狀表示和物體識別中，常?；趲缀蔚刃?。第14頁，課件共33頁，創(chuàng)作于2023年2月一、三次樣條曲線 樣條函數(shù)最常見的形式是三次樣條函數(shù)，它是分段三次多項式的一個序列。直線段、二次曲線序列都是樣條函數(shù)的特例。三次樣條函數(shù)可以用很少的幾個樣條段表示很復雜的曲線。已廣泛用于圖形學及輪廓表示。 三次樣條具有足夠的自由度來逼近邊緣段位置和方向。大多數(shù)邊緣檢測算子同時提供邊緣方向和位置估計。在直線段、二次曲線擬合中，僅使用了邊緣的位置信息。下面介紹一種在三次樣條曲線擬合中如何使用有邊緣檢測器產(chǎn)生的方向信息的例子。 平面三次曲線方程如下： 或： 參數(shù)u取值范圍在0和1之間。三次曲線起始點為，終點為。三次樣條是由 構成的一個序列。這一序列定義在連續(xù)區(qū)間[0，1]，[1，2]，…，第15頁，課件共33頁，創(chuàng)作于2023年2月 [n-1，n]上，并將端點連接起來使得在端點處。樣條中每一個三次曲線段稱為樣條段，連接樣條段兩端的端點稱為結點。設第i個結點連接第i-1樣條段和第i樣條段，該結點表示為 或。 與前述曲線擬合算法相同，把邊緣點序列分成一個個子序列，每一子序列的第一個和最后一個邊緣點為樣條曲線的結點，然后再用樣條段擬合這些結點。由三次曲線方程可知，樣條中每一個三次曲線段都需要確定四個二維矢量共計8個參數(shù)，其中，曲線段的兩個端點提供4個約束，結點處的一階連續(xù)性提供2個約束，結點處的二階連續(xù)性提供兩個約束，結點處的方向信息僅提供1個約束（由于結點由兩個樣條段共享），這樣產(chǎn)生的方程數(shù)量為9個，多于三次樣條段所需的8個參數(shù)。第16頁，課件共33頁，創(chuàng)作于2023年2月

在結點處光滑連接樣條段是非常重要的。在計算機圖形學中，光滑連接是通過增加二階連續(xù)性來實現(xiàn)。由上述分析知，二階連續(xù)性提供2個約束，從而對樣條段產(chǎn)生過約束。為避免過約束，同時又要使結點處光滑，可以采用結點處二階不連續(xù)性的極小化條件，也即將結點處的曲率差值極小化作為一個約束代替二階連續(xù)性提供的兩個約束。（推導略） 同前面介紹的多線段、二次曲線擬合算法一樣，結點必須從邊緣表中選出。調(diào)節(jié)結點的位置和數(shù)量可以改善三次樣條對整個邊緣點集的擬合效果。 三次樣條擬合算法僅需要求解一個小的線性系統(tǒng)就可得到正切值的符號和量值，因此該算法十分有效。另外，也可以使用交互式圖形界面，在其上可方便地調(diào)節(jié)三次樣條曲線。

第17頁，課件共33頁，創(chuàng)作于2023年2月二、B樣條曲線

B樣條曲線是由結點引導的逐段多項式曲線，是一種平滑和內(nèi)插技術。第18頁，課件共33頁，創(chuàng)作于2023年2月5.4Hough變換

Hough變換(HT)是一種用于區(qū)域邊界形狀描述的方法，經(jīng)典HT常常被用于直線段、圓和橢圓的檢測。HT是于1962年由P.V.C.Hough提出的，后經(jīng)不斷改進。廣義HT可推廣至檢測任意形狀。無論是HT還是廣義HT其基本思想是將圖象空間變換到參數(shù)空間，用大多數(shù)邊界點滿足的某種參數(shù)形式來描述圖象中的曲線（邊界）。由于HT是根據(jù)局部度量來計算全面描述參數(shù)，因此對區(qū)域邊界被噪聲干擾或被其它目標遮蓋而引起邊界發(fā)生某些間斷的情況，它具有很好的容錯性和魯棒性。第19頁，課件共33頁，創(chuàng)作于2023年2月一、Hough變換的原理 Hough（HT）變換是一種用于區(qū)域邊界形狀描述的重要方法。采用Hough變換檢測任意曲線的原理如下： 假設 為需檢測曲線的參數(shù)方程。式中為形狀參數(shù)，x，y為空間域的圖象點坐標。 對于圖象空間的任一點，利用上式可將其變換為參數(shù)空間中的一條曲線。假定空間域中位于同一曲線上的n個點，對這n個點逐一進行上述變換，則在參數(shù)空間中對應地得到n條曲線，由上式知，這n條曲線必定經(jīng)過同一點 ，找到參數(shù)空間的這個點就決定了空間域中的曲線l。 傳統(tǒng)的Hough變換將空間域中的每一個輪廓點代入上式，其計算結果對參數(shù)空間中的量化點進行投票，若票數(shù)超過某一門限值，則認為有足夠多的圖象點位于該參數(shù)點所決定的曲線上。即需要逐點投票、記錄，故耗時長，占用存儲量也大。為克服這一缺點，人們在應用中提出了許多改進算法。第20頁，課件共33頁，創(chuàng)作于2023年2月二、線段檢測

直線的方程為： 如下圖，按上述思想，一種檢測直線的簡單方法為：首先把參數(shù)平面離散化，并建立一個參數(shù)矩陣。對于圖象空間的每一個邊緣點，建立方程，并對離散化后的每個a值，計算出相應的b值，然后，將參數(shù)矩陣的元素的值加1：第21頁，課件共33頁，創(chuàng)作于2023年2月 即 重復這一過程，直到掃描完所有的邊界點。在過程結束后，參數(shù)矩陣元素的值表示圖象空間中滿足方程的邊界點的個數(shù)，如果其大于某一閾值，就表示檢測到了相應的直線。這種在參數(shù)空間進行“投票”的方法體現(xiàn)了Hough變換抗干擾的魯棒性。 上述參數(shù)方程不適合處理垂直直線，因為此時直線的a值趨于無窮大。為此，需引進直線的極坐標形式：

第22頁，課件共33頁，創(chuàng)作于2023年2月空間與空間的變換yx第23頁，課件共33頁，創(chuàng)作于2023年2月 此時的參數(shù)空間為。其檢測步驟如下： （1）適當量化參數(shù)空間； （2）累加器清零； （3）對每一投票，相應累加器加1； （4）對投票結果進行閾值化處理。 由上述分析可知，若對參數(shù)空間量化過細，則計算量增大；反之，若量化過粗，則參數(shù)空間的集聚效果差，檢測精度降低。因此，在應用Hough變換時，應根據(jù)實際選取合適的量化值。 如果圖象空間各點的梯度方向已知，在尋求直線邊緣時，可在邊緣點梯度方向的一定范圍內(nèi)對精細量化，其它角則粗量化，這樣可提高檢測直線方向角的精度，又不致增加計算量。第24頁，課件共33頁，創(chuàng)作于2023年2月例：第25頁，課件共33頁，創(chuàng)作于2023年2月三、圓檢測 對于圓，其參數(shù)方程為： 其參數(shù)空間為，增加到三維。第26頁，課件共33頁，創(chuàng)作于2023年2月 其算法步驟如下（從灰度圖象出發(fā)）： （1）應用邊緣檢測算子提取圖象邊緣，并按一定的閾值對其進行二值化處理，生成邊緣圖象； （2）圓的參數(shù)方程可改寫為： 將角度值按參數(shù)空間的大小離散化，并求出相應的值存入數(shù)據(jù)表中； （3）對邊緣圖象中的所有點，當r的取值在變化時，求出值，并將對應的累加器陣列中的單元加1； （4）對累加陣進行處理，當時，其參數(shù)對應為圖象空間的圓形邊界。 顯然，上述圓的Hough變換的計算量是非常大的。為降低計算復雜性，有許多改進算法，如增加邊緣方向信息等。第27頁，課件共33頁，創(chuàng)作于2023年2月四、橢圓檢測 參數(shù)空間變?yōu)?維：五、廣義Hough變換與任意形狀檢測第28頁，課件共33頁，創(chuàng)作于2023年2月第29頁，課件共33頁，創(chuàng)作于2023年2月第30頁，課件共33頁，創(chuàng)作于2023年2月5.5傅立葉描述子