第五章 形狀分析與描述

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

輪廓表示的評(píng)價(jià)標(biāo)準(zhǔn)：簡單：輪廓應(yīng)該是一種簡潔的表示。精確：輪廓應(yīng)能精確地逼近圖象特征。有效：輪廓應(yīng)適合于后處理階段的計(jì)算。

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

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

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

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

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

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

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

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

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

樣條：富有彈性的細(xì)長條。

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

幾何等效：是指它們連接相同的點(diǎn)集（即在空間上對(duì)應(yīng)著相同的形狀）。

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

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

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

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

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

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

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