圖像分析與識(shí)別_課件_6

1、123前一章著重于介紹圖像分割的方法和怎樣構(gòu)造均勻的圖像區(qū)域及其邊界。圖像區(qū)域的識(shí)別是理解圖像數(shù)據(jù)的重要步驟，它需要的是一種準(zhǔn)確的適合于分類器的區(qū)域描述。 4這種描述應(yīng)該生成表現(xiàn)區(qū)域?qū)傩裕ɡ?，形狀）的?shù)字特征向量或非數(shù)字的句法描述詞語(yǔ)。區(qū)域描述是第3章中介紹的4層中的第3層，意味著這種描述已經(jīng)包含了某種抽象。 51.第一層是最底層的表示，稱為圖標(biāo)圖像，由含有原始數(shù)據(jù)的圖像組成，原始數(shù)據(jù)也就是像素亮度數(shù)據(jù)的整數(shù)矩陣，往往需要進(jìn)行預(yù)處理；2.第二層的表示是分割圖像，圖像被分割為可能屬于同一物體的區(qū)域；63.第三層是幾何表示，保存2D和3D形狀知識(shí)；4.第四層的圖像數(shù)據(jù)表示是關(guān)系模型。關(guān)系模型使我

2、們能更有效地、并且在更高的抽象層次上處理數(shù)據(jù)。7在以下幾節(jié)中，我們將把討論限制在二維形狀特征，并且假設(shè)物體的描述來(lái)自圖像的分割結(jié)果。定義物體的形狀其實(shí)是非常困難的。 形狀通常以言辭來(lái)表述或以圖形來(lái)描繪。8在計(jì)算機(jī)時(shí)代，有必要對(duì)即便是非常復(fù)雜的形狀進(jìn)行精確的描述，盡管存在著許多實(shí)際的形狀描述方法，但并沒(méi)有被認(rèn)可的統(tǒng)一的形狀描述的方法學(xué)。甚至我們都不知道形狀中什么是重要的。9盡管如此，也有可能找到大多數(shù)形狀描述方法的共同特點(diǎn)。這些特點(diǎn)可以從不同的角度來(lái)刻畫： 1.輸入的表示形式：物體的描述可以是基于邊界的，或者是基于整個(gè)區(qū)域的更復(fù)雜的知識(shí)的。 102.物體重建的能力：即是否可以從描述來(lái)重建物體的形

3、狀。3.非完整形狀的識(shí)別能力：即如果物體被遮擋而只有部分形狀信息可以得到的話，根據(jù)該描述，物體的形狀可以被識(shí)別到什么程度。 114.局部/全局描述的特征：q全局描述子只能在整個(gè)物體的數(shù)據(jù)可以用來(lái)分析時(shí)才可使用；q局部描述子使用物體的部分信息來(lái)描述物體的局部特征，這樣局部描述子可用來(lái)描述遮擋物體。 125.數(shù)學(xué)的和啟發(fā)式的方法：q一個(gè)典型的數(shù)學(xué)方法是基于傅立葉變換的形狀描述；q一個(gè)具有代表性的啟發(fā)式方法可以是細(xì)長(zhǎng)形。 6.統(tǒng)計(jì)的或句法的物體描述。137.描述所具有的對(duì)平移、旋轉(zhuǎn)、尺度變換的魯棒性。8.形狀描述在不同分辨率下的屬性。 14如果要描述形狀，那么需要考慮尺度（分辨率）問(wèn)題，因?yàn)樾螤羁赡?/p>

4、會(huì)隨著圖像分辨率的變化而發(fā)生很大的變化。在高分辨率下輪廓的檢測(cè)可能會(huì)受到噪聲的影響，而在低分辨率下小的細(xì)節(jié)又可能會(huì)丟失。 15a)原 始 圖 像 6 4 0 像 素480像素b)a的輪廓c)原 始 圖 像 1 6 0 像 素120像素d)c的輪廓e)原始圖像64像素48像素f)e的輪廓 16在多數(shù)情況下，描繪形狀屬性的類別很重要，形狀類別應(yīng)該充分表現(xiàn)屬于同一類別的物體的一般形狀。很明顯，形狀類別應(yīng)該強(qiáng)調(diào)類間的不同點(diǎn)，而類內(nèi)形狀變化的影響不會(huì)在類的描述中有所反映。171.盡管我們?cè)谔幚矶S形狀及其描述，但物體是三維的。如果從不同角度觀看，會(huì)形成非常不同的二維透視投影。q理想的情況應(yīng)該是一個(gè)具有克

5、服這些變化的通用的形狀描述能力既設(shè)計(jì)具有透視投影不變性的描述子。 182.物體遮擋是形狀識(shí)別中的另外一個(gè)困難問(wèn)題。q在這里形狀描述子的選擇必須是基于其描述局部物體特征的能力。19本章介紹描述子的分類是根據(jù)它們是否基于邊界信息或者基于物體區(qū)域的信息。這種形狀描述方法的分類對(duì)應(yīng)于以前描述的基于邊界的和基于區(qū)域的分割方法。2021對(duì)于區(qū)域描述，區(qū)域標(biāo)識(shí)是必需的。區(qū)域標(biāo)識(shí)是給每個(gè)區(qū)域（或邊界）標(biāo)志一個(gè)唯一的數(shù)字，這樣的標(biāo)識(shí)稱為標(biāo)注（labeling）或著色（coloring），或稱為連通分量標(biāo)注。而最大的整數(shù)標(biāo)號(hào)通常也就給出了圖像中區(qū)域的數(shù)目。 22假設(shè)分割后的圖像R由m個(gè)不相交的區(qū)域Ri組成。圖像R

6、常常由若干物體和一個(gè)背景組成。其中RC是集合的補(bǔ)，Rb為背景，其它區(qū)域是物體。imbiiCbRR, 123標(biāo)注算法的輸入通常是二值圖像或多亮度級(jí)別的圖像。多亮度級(jí)圖像常常用于表示標(biāo)注的結(jié)果，背景用零值表示，區(qū)域用它們的非零標(biāo)號(hào)表示。 下面是一個(gè)標(biāo)注分割后圖像的算法。24算法：4-鄰域和8-鄰域區(qū)域標(biāo)識(shí)1.第一遍掃描：一行一行地搜索整個(gè)圖像R，對(duì)每個(gè)非零像素R(i,j)賦一個(gè)非零的值v。根據(jù)鄰域像素的標(biāo)號(hào)來(lái)選擇v值，其中鄰域的性質(zhì)由下圖定義。（不考慮在圖像R外面的“鄰域”）。25 區(qū)域標(biāo)識(shí)的掩模： (a) 在4-連通下 (b) 在8-連通下 (c) 標(biāo)號(hào)沖突26q如果所有的鄰域都是背景像素（其像

7、素值為零），則R(i,j)被賦予一個(gè)新的（到目前為止）沒(méi)使用過(guò)的標(biāo)號(hào)。q如果僅僅只有一個(gè)鄰域像素有非零標(biāo)號(hào)，那么就把這個(gè)標(biāo)號(hào)賦予像素R(i,j)。27q如果鄰域中有不止一個(gè)非零像素，則把這些像素中的任意一個(gè)的標(biāo)號(hào)賦予要標(biāo)注的像素。q如果鄰域的標(biāo)號(hào)有不同的（標(biāo)號(hào)沖突）。則將標(biāo)號(hào)對(duì)作為等價(jià)對(duì)保存起來(lái)。等價(jià)對(duì)被保存在單獨(dú)的數(shù)據(jù)結(jié)構(gòu)中等價(jià)表。282.第二遍掃描：所有的區(qū)域像素在第一遍掃描時(shí)被標(biāo)注了，但是一些區(qū)域存在具有不同標(biāo)號(hào)的像素（由于標(biāo)號(hào)沖突）。再一遍掃描圖像，使用等價(jià)表的信息重新標(biāo)注像素（例如，用等價(jià)類中的最小值）。 29q標(biāo)號(hào)沖突經(jīng)常發(fā)生發(fā)生這種現(xiàn)象的圖像形狀的例子包括U形物體、E的鏡像形物體

8、，等等。q等價(jià)表是一個(gè)出現(xiàn)在圖像中的所有標(biāo)號(hào)對(duì)的列表；所有的等價(jià)標(biāo)號(hào)在第二步中被用一個(gè)唯一的標(biāo)號(hào)代替。30q算法在4-連通和8-連通下基本相同，不同點(diǎn)僅在鄰域掩模的形狀上。q為了便于在第二遍掃描中對(duì)區(qū)域進(jìn)行簡(jiǎn)單計(jì)數(shù)，給區(qū)域賦予遞增的標(biāo)號(hào)是有用的。 31(a)32(b) 經(jīng)過(guò)步驟(b)后的等價(jià)表：2-5，5-6，2-433(c)3435區(qū)域邊界必須以某種數(shù)學(xué)形式來(lái)表示：1.直角坐標(biāo)最常見。2.極坐標(biāo)，在極坐標(biāo)下，邊界元素以角度和距離r的數(shù)對(duì)來(lái)表示。3.切線坐標(biāo)，作為路徑長(zhǎng)度n的函數(shù)，它對(duì)曲線上點(diǎn)的切線方向(xn)進(jìn)行編碼。36(a) 直角坐標(biāo)； (b) 極坐標(biāo)； (c) 切線坐標(biāo)37鏈碼通過(guò)帶有

9、給定方向的單位長(zhǎng)度的線段序列來(lái)描述物體。為了可以重建區(qū)域，該序列的第一個(gè)元素必須帶有其位置的信息。處理過(guò)程產(chǎn)生了一個(gè)數(shù)字序列。為了利用鏈碼的位置不變性，忽略其包含位置信息的第一個(gè)元素。這樣的鏈碼定義就是Freeman碼。384向鏈碼8向鏈碼39一個(gè)模4或模8的差分碼，稱為鏈碼的導(dǎo)數(shù)，它表示區(qū)域邊界元素的相對(duì)方向的另一個(gè)數(shù)字序列，以逆時(shí)針計(jì)數(shù)的90或45的倍數(shù)來(lái)度量。鏈碼對(duì)噪聲非常敏感，而且如果要用于識(shí)別，尺度和旋轉(zhuǎn)的任意變化都可能會(huì)引起問(wèn)題。40鏈碼：3，0，0，3，0，1，1，2，1，2，3，2導(dǎo)數(shù)：1，0，3，1，1，0，1，3，1，1，3，141a)疊加在數(shù)字化邊界上的重取樣網(wǎng)格b)重取

10、樣的結(jié)果c)4向鏈碼d)8向鏈碼42以下的描述子大部分基于被描述區(qū)域的幾何屬性。由于數(shù)字圖像的離散特點(diǎn)，它們都對(duì)圖像的分辨率敏感。 431.邊界長(zhǎng)度：邊界長(zhǎng)度是基本的區(qū)域?qū)傩裕梢院?jiǎn)單地從鏈碼表示中得到。垂直的和水平的步幅為單位長(zhǎng)度，在8-連通下的對(duì)角步幅的長(zhǎng)度為 。這可以說(shuō)明在4-連通下邊界會(huì)更長(zhǎng)些，其中對(duì)角步幅包含兩個(gè)直角步，總長(zhǎng)度為2。244邊界長(zhǎng)度隨著圖像光柵分辨率的增加而增加。區(qū)域面積不受更高分辨率的影響而收斂于某個(gè)限度值。數(shù)字化邊界可以用多邊形進(jìn)行任意精確性的近似。45a)被單元包圍的對(duì)象邊界b)最小周長(zhǎng)多邊形(a)(b)462.曲率：在連續(xù)的情況下，曲率被定義為斜率的變化率。在離

11、散空間，曲率的描述必須稍做修改以克服因曲線不具有平滑性所造成的困難。47曲率標(biāo)量描述子（也稱為邊界平直度）是邊界像素的總數(shù)目（長(zhǎng)度）和邊界方向有顯著變化的邊界像素的數(shù)目的比率。方向改變的數(shù)目越少，邊界越平直。48對(duì)它的估算算法是基于檢測(cè)存在于從待估計(jì)的邊界像素出發(fā)到在任兩個(gè)方向上各b個(gè)邊界像素位置處的兩條線段間的角度的方法。這個(gè)角度不必以數(shù)字形式表示。參數(shù)b決定了對(duì)邊界方向局部變化的敏感度。49曲率503.彎曲能量：邊界（曲線）的彎曲能量（BE）可以理解為把一個(gè)桿彎曲成所要求的形狀所需的能量，可以計(jì)算為邊界曲率c(k)的平方和除以邊界長(zhǎng)度L。LkkcLBE12)(151為了表示邊界，可以使用F

12、reeman鏈碼或它的平滑形式，參見下圖。彎曲能量沒(méi)有形狀重建能力。52a)鏈碼 0，0，2，0，1，0，7，6，0，0；b)曲率 0，2，-2，1，-1，-1，-1，2，0；c)平方和給出了彎曲能量；d)平滑型534.簽名：區(qū)域的簽名可以由法線輪廓距離的序列得到。對(duì)每一個(gè)邊界元素，法線輪廓距離為路徑長(zhǎng)度的函數(shù)。對(duì)每一個(gè)邊界點(diǎn)A，到對(duì)面邊界點(diǎn)B的最近距離的道路為垂直于點(diǎn)A邊界切線的方向，參見下圖。對(duì)面不是一個(gè)對(duì)稱關(guān)系。54簽名對(duì)噪聲敏感，因而使用平滑后的簽名或平滑后的輪廓的簽名來(lái)降低對(duì)噪聲的敏感性。簽名可以用于對(duì)有重疊的物體的識(shí)別，或每當(dāng)只有部分輪廓可以獲得的情況下的識(shí)別。55(a) 構(gòu)造 (

13、b) 圓和三角形的簽名 565.弦的分布：連接區(qū)域邊界上任兩點(diǎn)的直線就是弦，而在輪廓上所有弦的長(zhǎng)度和角度的分布可以用于形狀描述。 57弦的分布58假設(shè)C是復(fù)平面上的封閉曲線（邊界）。以逆時(shí)針?lè)较蜓刂@個(gè)曲線保持恒定速度移動(dòng)，得到一個(gè)復(fù)函數(shù)Z(t)，這里t是時(shí)間變量。速度應(yīng)該選擇為使得環(huán)繞邊界一周的時(shí)間為2；然后沿曲線做多次遍歷得到一個(gè)周期為2的周期函數(shù)。這就允許了z(t)的傅立葉表示。 59系數(shù)Tn稱為曲線C的傅立葉描述子。相對(duì)于時(shí)間t，考慮曲線距離s會(huì)更有用，其中L是曲線長(zhǎng)度。 nneTtzint)(Lst260傅立葉描述子Tn由下式給出。描述子受曲線形狀及曲線初始點(diǎn)的影響。 dseszLT

14、LnnsLi0)2()(161對(duì)于數(shù)字圖像數(shù)據(jù)，邊界坐標(biāo)是離散的而函數(shù)z(t)不是連續(xù)的。假定z(k)是z(s)的離散型，其中為了得到不變的采樣間隔使用4-連通；傅立葉描述子Tn可以從z(k)的離散傅立葉變換中計(jì)算出來(lái)：nTDFTkZ)(62一個(gè)封閉邊界可以表示為切線間的角度相對(duì)于其在邊界上的點(diǎn)之間的距離的函數(shù)。令k為在第k個(gè)邊界點(diǎn)測(cè)量的角度，令lk為起始邊界點(diǎn)和第k個(gè)邊界點(diǎn)的距離。一個(gè)周期函數(shù)可以被定義為：63描述子集合則為：kkkula)(Llukk220)(21dueuaSinun64(a) 描述符Tn (b) 描述符 Sn65傅立葉描述子的優(yōu)點(diǎn)是僅使用少數(shù)低階系數(shù)就得到了高質(zhì)量的邊界形

15、狀表示。我們可以比較使用描述子Sn和Tn的結(jié)果：由于切線角度的變化相對(duì)比較顯著，描述子Sn有更多的高頻成分出現(xiàn)在邊界函數(shù)中，結(jié)果使它們不如描述子Tn那樣快地衰減。66另外，由于常常導(dǎo)致不封閉的邊界，Sn描述子不適合于邊界重建。描述子Tn的值對(duì)于更高的頻率會(huì)非?？斓厮p，而它們的重建常常會(huì)產(chǎn)生封閉的邊界。Sn描述子不能用于正方形和正三角形等情況。67傅立葉描述子也可以用于計(jì)算區(qū)域面積、質(zhì)心的定位以及二次矩。傅立葉描述子是一種通用的技術(shù)，但是在描述局部信息時(shí)存在問(wèn)題。傳統(tǒng)的傅立葉描述子不能用于遮擋物體的識(shí)別。68邊界（以及曲線）描述的另一種選擇是使用具有特定屬性的片段來(lái)表示邊界。如果對(duì)于所有的片段

16、其類型都是已知的，則邊界可以描述為片段類型的一個(gè)鏈，碼字由代表類型的字母組成。這種描述適合于句法識(shí)別。69多邊形表示通過(guò)一個(gè)多邊形來(lái)近似區(qū)域，區(qū)域由它的頂點(diǎn)來(lái)表示。多邊形表示可以作為對(duì)邊界的一個(gè)簡(jiǎn)單分割的結(jié)果。邊界可以用各種精度來(lái)近似，如果需要一個(gè)更精確的描述，就可能需要使用更多的線段。70任意兩個(gè)邊界點(diǎn)x1和x2定義了一條線段，點(diǎn)x1、x2和x3的序列表示了一個(gè)線段鏈從點(diǎn)x1到點(diǎn)x2，從x2到x3。如果x1=x3，則為一個(gè)封閉的邊界。 71有很多類型的線片段的邊界表示。問(wèn)題在于邊界頂點(diǎn)位置的確定，一個(gè)解決方法是使用分裂歸并算法。歸并的步驟為檢查邊界點(diǎn)的集合，只要滿足了一個(gè)片段的平直性標(biāo)準(zhǔn)，就

17、把它們加到這個(gè)片段中。72如果失去了片段的平直性，最后連接的點(diǎn)就被標(biāo)記為頂點(diǎn)，并開始構(gòu)建一個(gè)新的片段。通過(guò)使用曲率（邊界平直率）標(biāo)準(zhǔn)，當(dāng)邊界點(diǎn)在邊界方向上有顯著變化時(shí)，就可以檢測(cè)到邊界頂點(diǎn)。當(dāng)邊界擁有直的邊界片段時(shí)，這個(gè)方法很有效。73把邊界分割成更小片段的分裂方法有時(shí)會(huì)有幫助。如果使用了分裂方法，片段通常被分成兩段更小的新片段直到新的片段達(dá)到最后的要求。 74一個(gè)分裂的簡(jiǎn)單過(guò)程從一條曲線的終點(diǎn)x1和x2開始，兩終點(diǎn)被一條線段連接起來(lái)。下一個(gè)步驟是在所有的曲線點(diǎn)中找到距離線段最遠(yuǎn)的曲線點(diǎn)x3。75如果被確定的點(diǎn)在預(yù)設(shè)的它和線段間的距離范圍內(nèi)，片段x1-x2就是最后的片段，而所有的曲線頂點(diǎn)都找到

18、了，頂點(diǎn)x1和x2就是曲線的多邊形表示。否則點(diǎn)x3作為新的頂點(diǎn)，并且將這個(gè)過(guò)程在兩個(gè)結(jié)果片斷x1-x3和x3-x2上遞歸地調(diào)用。 76 遞歸的邊界分裂77把邊界分割成常數(shù)曲率的片段是邊界表示的另一個(gè)可能性。邊界也可以被分割成能用多項(xiàng)式來(lái)表示的片段，通常是二階的，例如圓形的、橢圓形的或拋物線形的線段。78對(duì)于句法形狀識(shí)別過(guò)程，片段被作為基元看待。一個(gè)典型的例子是染色體的句法描述和識(shí)別，其中邊界片段被分類為較大曲率的凸片段、較大曲率的凹片段、直線片段，等等。79 邊界片段鏈形式的染色體結(jié)構(gòu)描述碼字：d, b, a, b, c, b, a, b, d, b, a, b, c, b, a, b80我們

19、已經(jīng)提到過(guò)形狀描述子對(duì)尺度（圖像分辨率）的敏感性是大多數(shù)描述子的一個(gè)不受歡迎的的特征。換句話說(shuō)，形狀描述隨著尺度的變化而變化，在不同分辨率下會(huì)得到不同的結(jié)果。 81如果曲線要被分成片段，這個(gè)問(wèn)題仍然很突出。曲線的一些分割點(diǎn)在某一分辨率下存在。在其它分辨率下會(huì)消失因而沒(méi)有任何直接的對(duì)應(yīng)。 82考慮到這個(gè)問(wèn)題，曲線分割的一個(gè)保證分割點(diǎn)位置連續(xù)變化的尺度空間方法就是一個(gè)顯著的成就。這個(gè)方法中，新的分割點(diǎn)只能在更高分辨率下出現(xiàn)，且已經(jīng)存在的分割點(diǎn)不會(huì)消失。 83這種技術(shù)是基于把單獨(dú)的高斯平滑核在一定的尺度范圍內(nèi)應(yīng)用于一維信號(hào)（例如，曲率函數(shù)），并將其結(jié)果微分兩次。通過(guò)檢測(cè)二階導(dǎo)數(shù)的過(guò)零點(diǎn)來(lái)確定曲率的峰

20、值，過(guò)零點(diǎn)的位置給出了曲線分割點(diǎn)的位置。84在不同分辨率（不同的高斯核尺寸）下獲得分割點(diǎn)的不同位置。高斯核的一個(gè)重要性質(zhì)是分割點(diǎn)的位置隨著分辨率的變化而連續(xù)變化，這可以從曲線的尺度空間圖像中看出。85曲線的細(xì)微細(xì)節(jié)在高斯平滑核尺寸的增大下成對(duì)地消失，并且總是兩個(gè)分割點(diǎn)合并起來(lái)而形成一個(gè)封閉的輪廓。說(shuō)明了在粗分辨率下存在的任意分割點(diǎn)一定也在細(xì)的分辨率下存在。86此外，分割點(diǎn)的位置在最精細(xì)的分辨率下是最精確的。而且可以對(duì)它的位置通過(guò)使用尺度空間圖像從粗分辨率到細(xì)分辨率進(jìn)行跟蹤。 87一個(gè)多尺度的曲線描述可以通過(guò)區(qū)間樹表示出來(lái)。每一對(duì)過(guò)零點(diǎn)的位置被表示成一個(gè)矩形，它的位置對(duì)應(yīng)于分割點(diǎn)在曲線上的位置，

21、它的高度表示分割點(diǎn)可以被檢測(cè)到的最低分辨率。88區(qū)間樹可以用于不同尺度下的曲線分解，同時(shí)保持了使用較高分辨率做片段描述的可能性。89(a) 作為尺度函數(shù)的曲線分割點(diǎn)的數(shù)目和位置的變化(b) 曲線表示的區(qū)間樹形式 90在圖形學(xué)中，使用分段多項(xiàng)式插值來(lái)得到平滑曲線的這種曲線表示方法是十分普遍的。B樣條是分段多項(xiàng)式曲線，其形狀與它的控制多邊形緊密相關(guān)曲線的多邊形表示由一個(gè)頂點(diǎn)的鏈給出。 91三次B樣條是最常見的，因?yàn)檫@是包含曲率變化的最低階次。樣條有非常好的表示特性并且容易計(jì)算：第一，它們的形狀改變要小于其控制多邊形，并且它們不會(huì)像很多其它表示那樣在采樣點(diǎn)間振蕩。 92此外，對(duì)于n次B樣條，樣條曲線

22、總是位于n+1個(gè)頂點(diǎn)的多邊形內(nèi)。第二，插值在特性上是局部的。如果一個(gè)控制多邊形的頂點(diǎn)改變了它的位置，所造成的樣條曲線的變化僅僅在那個(gè)頂點(diǎn)的一個(gè)小的鄰域內(nèi)發(fā)生。 93第三，把由樣條表示的區(qū)域邊界與圖像數(shù)據(jù)相匹配的方法是基于對(duì)原始圖像數(shù)據(jù)的直接搜索。 94(a, b, c) n次B樣條的n+1個(gè)頂點(diǎn)的多邊形(d) 3次樣條95令xi，i=l, , n為B樣條插值曲線的點(diǎn)，稱此插值曲線為x(s)。參數(shù)s在點(diǎn)xi間線性變化，即xi=x(i)。三次B樣條曲線的每一個(gè)部分都是三次多項(xiàng)式，這意味著它以及它的一階和二階導(dǎo)數(shù)都是連續(xù)的。B樣條由下式給出：9610)()(niiisBvsx其中vi為表示樣條曲線的

23、系數(shù)，Bi(s)是基函數(shù)，其形狀由樣條的階次給出。97系數(shù)vi具有的信息對(duì)偶于樣條曲線點(diǎn)的信息vi的值可以從xi中得出，反之亦然。系數(shù)vi代表了控制多邊形的頂點(diǎn)，而且如果有n個(gè)點(diǎn)xi，則必須有n+2個(gè)點(diǎn)vi。兩個(gè)端點(diǎn)v0和vn+1由邊界條件確定。 98樣條生成的曲線通常是令人滿意的。它們提供了一個(gè)好的曲線近似，在圖像分析的曲線表示問(wèn)題中也很容易使用。樣條對(duì)于尺度的變化非常敏感。99還有很多可以用來(lái)描述二維曲線和輪廓的其它方法和途徑。 Hough變換擁有極好的形狀描述能力。使用統(tǒng)計(jì)矩的基于區(qū)域的形狀描述。對(duì)形狀的分形的研究方法，在圖像形狀的描述中正在受到越來(lái)越多的關(guān)注。 100數(shù)學(xué)形態(tài)學(xué)可以用于

24、形狀描述，特別是在與區(qū)域骨架重建相關(guān)的方面上。神經(jīng)網(wǎng)絡(luò)可以直接用于識(shí)別以原始邊界表示的形狀。用無(wú)噪聲的參考形狀的輪廓序列來(lái)訓(xùn)練，且為了提高魯棒性在訓(xùn)練的后期階段使用帶有噪聲的數(shù)據(jù)。101形狀不變量是當(dāng)前機(jī)器視覺領(lǐng)域的一個(gè)非常活躍的研究方向。 即便在機(jī)器視覺中形狀不變性是一個(gè)新的方法，但不變量理論并不是新的，它的很多原理早在19世紀(jì)就出現(xiàn)了。102正如多次所提到那樣，物體描述對(duì)于物體識(shí)別來(lái)說(shuō)是必要的。不幸的是，目前所討論過(guò)的所有形狀描述子都依賴于視點(diǎn)，這意味著由于物體或觀察者的位置變化，使得識(shí)別物體常常是不可能的。103相同的矩形截面在圖像平面中被表示為不同的多邊形 104形狀描述不變性的作用是

25、顯然的。形狀不變量表示了一種幾何結(jié)構(gòu)的屬性，它在一個(gè)適當(dāng)?shù)淖儞Q類下保持不變。機(jī)器視覺特別關(guān)心透視變換類。 105共線性是透視不變性圖像特征的最簡(jiǎn)單的例子。在任意的透視變換下任何直線都被投影為直線。類似地，透視不變性形狀描述的基本思想是找到這樣的形狀特征，它不受物體和圖像平面間的變換的影響。 106一種標(biāo)準(zhǔn)的透視不變性描述技術(shù)是：假設(shè)知道物體的姿態(tài)（位置和方向），把它變換到特定的坐標(biāo)系統(tǒng)中，然后在這個(gè)坐標(biāo)系統(tǒng)中測(cè)量形狀特征，形成一個(gè)不變的描述。然而對(duì)每一個(gè)物體和每一幅圖，都必須假設(shè)知道姿態(tài)，這使得該方法困難而不可靠。 107不變量理論的應(yīng)用提供了另一個(gè)途徑，其中不變量描述子可以直接從圖像數(shù)據(jù)中計(jì)

26、算出來(lái)而不需要專門的坐標(biāo)系統(tǒng)。 現(xiàn)在將給出幾個(gè)不變量的例子。108首先給出交比的定義。交比是代表了透視線的一個(gè)經(jīng)典的不變量。就像前面提到的，一條直線總是投影為一條直線。109任意四個(gè)共線點(diǎn)A, B, C, D可以用交比不變量描述為： 其中(A-C)表示點(diǎn)A和點(diǎn)C間的距離。交比依賴于被標(biāo)注的四個(gè)共線點(diǎn)的順序。CBDADBCAI110交比：四個(gè)共線點(diǎn)形成一個(gè)透視不變數(shù) 111 一個(gè)四條共面共點(diǎn)的直線（交于同一點(diǎn)）的系統(tǒng)對(duì)偶于一個(gè)四個(gè)共線點(diǎn)的系統(tǒng)并且交比是它的不變量。 112一個(gè)五條共面直線的系統(tǒng)產(chǎn)生兩個(gè)不變量。5314215214311MMMMI 5214325324312MMMMI 113其中M

27、ijk=(1i, lj, lk)。li=(li1, li2, li3)T是一條直線li1x+li2y+li3=0的表示，其中i1, 5，并且|M|是矩陣M的行列式。如果生成矩陣Mijk的三條直線是共點(diǎn)的，則矩陣變?yōu)槠娈惖亩蛔兞烤蜎](méi)有定義。 114一個(gè)五個(gè)共面點(diǎn)的系統(tǒng)對(duì)偶于一個(gè)五條直線的系統(tǒng)，并且可以生成同樣的的兩個(gè)不變量。這兩個(gè)獨(dú)立作用的不變量也可由兩組共面共點(diǎn)的四條直線的兩個(gè)交比來(lái)產(chǎn)生，參見下圖。115注意即使產(chǎn)生了除了下圖中給出的組合之外，也僅有兩個(gè)已介紹的獨(dú)立作用的不變量存在。116 (a) 共面點(diǎn)(b) 五點(diǎn)形成一個(gè)四條共點(diǎn)直線的系統(tǒng)(c) 相同的五點(diǎn)形成另一個(gè)四條共點(diǎn)直線的系統(tǒng) 1

28、17 一條平面二次曲線可以由一個(gè)方程表示： 對(duì)于X=(x, y, 1)T, 則二次曲線也可由矩陣C來(lái)定義，022feydxcybxyaxfedecbdbaC222222118以及對(duì)任意的由矩陣C表示的二次曲線，以及兩條不切于二次曲線的共面直線，可以定義一個(gè)不變量: 0CXXT2121112211lCllCllClITTT119對(duì)于一條二次曲線和兩個(gè)共面點(diǎn)，可以形成同樣的不變量。 對(duì)于兩條由它們的歸一化矩陣C1和C2 (|Ci|=1)表示的二次曲線，可以確定兩個(gè)不變量。 2111CCTraceI1122CCTraceI120矩陣的跡（Trace）是主對(duì)角線元素的和。 對(duì)于非歸一化的二次曲線，所關(guān)

29、聯(lián)的二次型的不變量為：31212111CCCCTraceI31121122CCCCTraceI121以及二次曲線的兩個(gè)真正的不變量為：2121122111CCCCTraceCCTraceI1222111122CCCCTraceCCTraceI122兩條平面二次曲線唯一地確定了四個(gè)相交點(diǎn)，而任意選擇一個(gè)非相交點(diǎn)和四個(gè)相交點(diǎn)都可成一個(gè)五點(diǎn)系統(tǒng)。因此，對(duì)于這一對(duì)二次曲線，像五點(diǎn)系統(tǒng)一樣，存在兩個(gè)不變量。123很多人造物體由圓和直線組成，這些不變量可用于它們的描述。然而，如果物體具有不能用代數(shù)曲線表示的輪廓，情況就非常困難了。 124在機(jī)器觀覺應(yīng)用中，設(shè)計(jì)新的不變量是不變量理論的一個(gè)重要部分。最簡(jiǎn)單的

30、方法是組合基本的不變量，從這些組合中形成新的不變量。下圖給出了一個(gè)這樣的物體識(shí)別的例子。 125 (a)從一個(gè)任意視點(diǎn)拍攝的重疊物體的原始圖像(b)基于直線和二次曲線不變量的物體識(shí)別126127我們可以使用邊界信息來(lái)描述區(qū)域，也可以從區(qū)域自身來(lái)描述形狀。 由啟發(fā)式方法表示的一大類形狀描述技術(shù)，在簡(jiǎn)單形狀的描述中可產(chǎn)生能夠接受的結(jié)果。例如，區(qū)域的面積、矩形度、細(xì)長(zhǎng)度、方向、緊致度等等。128但是它們不能用于區(qū)域重建且對(duì)于較復(fù)雜的形狀也不起作用。對(duì)于更復(fù)雜的區(qū)域的描述，必須基于其它的把區(qū)域分解成更小和更簡(jiǎn)單的子區(qū)域的方法，然后這些子區(qū)域可以分別地用啟發(fā)式方法來(lái)描述。 129物體用平面圖來(lái)表示，其節(jié)

31、點(diǎn)代表由區(qū)域分解產(chǎn)生的子區(qū)域，而區(qū)域形狀由圖的屬性來(lái)描述。有兩種一般的途徑來(lái)得到子區(qū)域的圖：1301.第一種是區(qū)域細(xì)化，它導(dǎo)致可以用圖來(lái)描述區(qū)域骨架。2.第二種可選的方法從區(qū)域分解成子區(qū)域開始，然后子區(qū)域由節(jié)點(diǎn)來(lái)表示，節(jié)點(diǎn)的弧表示了子區(qū)域的相鄰關(guān)系。通常規(guī)定子區(qū)域是凸的。131區(qū)域的圖表示有很多優(yōu)點(diǎn)所產(chǎn)生的圖具有以下特點(diǎn)： q它是平移和旋轉(zhuǎn)的不變量，位置和旋轉(zhuǎn)可以被包括在圖的定義中。q它對(duì)形狀的微小改變不敏感。q相對(duì)區(qū)域的尺寸是很好的不變量。132q它生成的是可理解的表示。q它很容易被用來(lái)獲得圖的具有一定信息的特征。q它適合于句法識(shí)別。133另一方面，這種形式的形狀表示可能是很難得到的，而且分

32、類器的學(xué)習(xí)階段也不是容易的。然而，如果我們貼近計(jì)算機(jī)視覺的現(xiàn)實(shí)的話，為了理解復(fù)雜圖像，別無(wú)選擇。134存在許多簡(jiǎn)單的啟發(fā)式形狀描述子，它與統(tǒng)計(jì)特征描述有關(guān)。這些方法是基本的，它們用在復(fù)雜區(qū)域的子區(qū)域的描述中，而且也可用于定義圖節(jié)點(diǎn)的分類。135 最簡(jiǎn)單的且最自然的區(qū)域?qū)傩允撬拿娣e，由區(qū)域包含的像素個(gè)數(shù)給出。 如果圖像被表示為一個(gè)矩形光柵，那么區(qū)域像素的簡(jiǎn)單計(jì)數(shù)就會(huì)提供其面積。136 歐拉數(shù)描述了物體的一個(gè)簡(jiǎn)單的拓?fù)洳蛔兊膶傩?。它基于物體的連通部分的數(shù)目S以及物體中孔的數(shù)目N（一個(gè)物體可以包含不止一個(gè)區(qū)域，否則連通部分的數(shù)目等于1）。于是有：=S-N 137定義水平的和垂直的區(qū)域投影ph(i)

33、和pv(j)為：根據(jù)投影的區(qū)域描述通常和二值圖像處理相關(guān)。投影可以被當(dāng)作定義相關(guān)區(qū)域描述子的一個(gè)基礎(chǔ)。ivjhjifjpjifip),()(),()(138垂直投影寬度水平投影高度139 最簡(jiǎn)單的離心率特征是最長(zhǎng)弦A和垂直于A的最長(zhǎng)弦B的長(zhǎng)度比（一個(gè)物體的主次軸的比）。另一個(gè)近似的離心率的度量是基于主區(qū)域慣量軸的比。 140 細(xì)長(zhǎng)度是區(qū)域外接矩形的長(zhǎng)寬比。這是一個(gè)包圍形狀的最小面積的矩形，它是通過(guò)以離散步幅旋轉(zhuǎn)直到達(dá)到最小值來(lái)確定的。這個(gè)準(zhǔn)則在彎曲的區(qū)域下達(dá)不到（參見圖b），對(duì)于這種區(qū)域的細(xì)長(zhǎng)度的估計(jì)必須基于最大區(qū)域厚度。141(a) 外接矩形給出了可接受的結(jié)果(b) 外接矩形不能表示細(xì)長(zhǎng)度1

34、42 令Fk為區(qū)域面積和外接矩形面積的比，矩形具有方向k。矩形的方向像前面一樣以離散步幅旋轉(zhuǎn)，矩形度度量為這個(gè)比率Fk的最大矩形值：)(maxkkF矩形度143方向僅需旋轉(zhuǎn)一個(gè)象限。矩形度設(shè)定的數(shù)值在區(qū)間(0，1中，1代表一個(gè)完美的矩形區(qū)域。 144 方向是僅在細(xì)長(zhǎng)區(qū)域下有意義的屬性。如果區(qū)域是細(xì)長(zhǎng)的，方向就是最小外接矩形的最長(zhǎng)邊的方向。 145 緊致度是獨(dú)立于線性變換的一個(gè)通用的形狀描述特征，由下式給出：在歐氏空間里最緊致的區(qū)域是圓。 arealengthborderregion2)_(緊致度146(a) 緊致的 (b) 非緊致的147區(qū)域的矩表示把一個(gè)歸一化的灰度級(jí)圖像函數(shù)理解為一個(gè)2維隨

35、機(jī)變量的概率密度。隨機(jī)變量的屬性用統(tǒng)計(jì)特征矩來(lái)描述。 通過(guò)假設(shè)非零的像素值表示區(qū)域，矩可以用于二值或灰度級(jí)的區(qū)域描述。 148(p+q)階矩依賴于尺度、平移、旋轉(zhuǎn)、甚至灰度級(jí)上的變換，由下式給出：在數(shù)字圖像中，我們計(jì)算求和式： dxdyyxfyxmqppq),( ijqppqjifjim),(149其中x, y, i, j是區(qū)域點(diǎn)的坐標(biāo)。如果使用中心矩，可以獲得平移不變性。在數(shù)字圖像中： dxdyyxfyyxxqcpcpq),()()( ijqcpcpqjifyjxi),()()(150其中Xc和Yc是區(qū)域重心（質(zhì)心）的坐標(biāo)，它可以由下面的關(guān)系來(lái)得到：00010010mmYcmmXc151一個(gè)

36、區(qū)域R是凸的，當(dāng)且僅當(dāng)對(duì)于任意兩點(diǎn)x1, x2R，由它的端點(diǎn)x1和x2定義的整個(gè)直線段x1x2在區(qū)域R的內(nèi)部。區(qū)域的凸包是滿足條件RH的最小凸區(qū)域H，參見下圖。 152153凸包在數(shù)字?jǐn)?shù)據(jù)中具有一些特殊性質(zhì)。例如，凹的部分在數(shù)字?jǐn)?shù)據(jù)中由于旋轉(zhuǎn)會(huì)出現(xiàn)或消失，因此凸包在數(shù)字空間中不是旋轉(zhuǎn)不變量。凸包可以用來(lái)描述區(qū)域形狀屬性而且可以用于建立區(qū)域凹狀的樹型結(jié)構(gòu)。 154離散凸包的構(gòu)建算法 1.找到具有最小行坐標(biāo)的區(qū)域R的所有像素，在它們中間，找到具有最小列坐標(biāo)的像素P1。賦值Rk=P1，v=(0, -1)，向量v表示凸包的前一直線段的方向。 1552.以逆時(shí)針?lè)较蛩阉鲄^(qū)域邊界并且對(duì)每一個(gè)位于點(diǎn)P1后（

37、在邊界搜索方向上見上圖）的邊界點(diǎn)Pn計(jì)算方向角n。方向角n是向量PkPn的角度。滿足條件q=minnn的點(diǎn)Pq是區(qū)域凸包的一個(gè)元素（頂點(diǎn)）。1563.賦值v=PkPq, Pk=Pq。4.重復(fù)執(zhí)行步驟2和3直到Pk=P1。 1571.令待檢測(cè)凸包的多邊形為簡(jiǎn)單多邊形P=v1, v2, , vn。并且令頂點(diǎn)以這個(gè)順序來(lái)處理。2.序列P中的前三個(gè)頂點(diǎn)A, B, C形成一個(gè)三角形（如果不共線），而這個(gè)三角形表示了這前三個(gè)點(diǎn)的凸包（見圖a）。Melkman的凸包檢測(cè)算法1583.然后在序列中測(cè)試下一個(gè)頂點(diǎn)D是否位于當(dāng)前凸包的內(nèi)部或外部。4.如果D位于內(nèi)部，則當(dāng)前的凸包不改變（見圖b）。5.如果D位于當(dāng)前

38、凸包的外部，它就必須成為一個(gè)新的凸包頂點(diǎn)（見圖c）。1596.而基于當(dāng)前的凸包形狀，或者沒(méi)有、或者一個(gè)或幾個(gè)頂點(diǎn)必須從當(dāng)前的凸包中去掉（見圖c和d）。7.對(duì)序列P中所有剩下的頂點(diǎn)重復(fù)這個(gè)過(guò)程。160a)前三個(gè)頂點(diǎn)A, B, C形成一個(gè)三角形；b)如果下一個(gè)頂點(diǎn)D位于當(dāng)前凸包ABC的內(nèi)部， 則當(dāng)前凸包不變；c)如果下一個(gè)頂點(diǎn)D位于當(dāng)前凸包的外部，則它成為當(dāng)前新的凸包ABCDA的一個(gè)新頂點(diǎn)；d)在這種情況下，必須從當(dāng)前的凸包中支掉頂點(diǎn)B而新的凸包為ADCA。161 a)被處理的區(qū)域-多邊形ABCDEAb)輸入和處理頂點(diǎn)Dc)頂點(diǎn)D成為當(dāng)前凸包ADC的一個(gè)新頂點(diǎn)d)輸入和處理頂點(diǎn)E，E沒(méi)有成為當(dāng)前凸

39、包的一個(gè)新的頂點(diǎn)e)結(jié)果凸包DCAD162區(qū)域圖是基于區(qū)域骨架的，第一步是骨架構(gòu)建。數(shù)學(xué)形態(tài)學(xué)是一個(gè)可用來(lái)獲得區(qū)域骨架的有力工具。大多數(shù)的細(xì)化過(guò)程重復(fù)地去除邊界元素直至找到最大厚度為1或2的像素集合。 163構(gòu)建骨架有四種基本的途徑：q細(xì)化迭代地去除區(qū)域邊界像素；q從邊界開始的波傳播；q在區(qū)域的距離變換圖像中檢測(cè)局部最大值；q分析的方法。164算法：通過(guò)細(xì)化提取骨架 1.令R為區(qū)域像素的集合，Hi(R)為它的內(nèi)部邊界，而HO(R)為它的外部邊界。令S(R)為區(qū)域R中的部分像素的集合，這些像素在8-連通下的所有鄰居或者來(lái)自內(nèi)部邊界Hi(R)或者來(lái)自背景R的余集。賦值Rold=R。1652.構(gòu)建一

40、個(gè)新的區(qū)域Rnew為如下的進(jìn)一步細(xì)化的結(jié)果：3.如果Rnew=Rold，結(jié)束迭代并轉(zhuǎn)步驟4。否則賦值Rold=Rnew，重復(fù)步驟2。 4.Rnew是骨架像素的集合（即區(qū)域R的骨架）。)()()(oldoldooldioldoldnewRRSHRHRRSR166細(xì)化過(guò)程常常使用中軸變換來(lái)構(gòu)建區(qū)域骨架。在中軸的定義下，骨架是滿足以下條件的所有區(qū)域點(diǎn)的集合：它至少與兩個(gè)分開的邊界點(diǎn)具有相同的到區(qū)域邊界的最小距離。由這個(gè)條件產(chǎn)生的骨架的例子參見下圖。 167使用一個(gè)距離變換給每個(gè)區(qū)域像素賦予其到區(qū)域邊界的（最小）距離值，這樣就可以構(gòu)建骨架。可以認(rèn)為骨架是到區(qū)域邊界的距離取得局部最大值的像素的集合。 1

41、68每一個(gè)骨架的元素可以附有它到邊界距離的信息，這提供了一個(gè)重建區(qū)域的方法：以骨架元素為中心點(diǎn)，以所保存的距離值為半徑，所有這樣的圓盤所形成的包絡(luò)曲線就構(gòu)成區(qū)域的邊界。 169區(qū)域骨架：邊界的小變化在骨架上有顯著的影響170 (a) 原始圖像 (b) 區(qū)域骨架（為了顯 示而加粗了）171 (a) 原始圖像 (b) 區(qū)域骨架（為了顯 示而加粗了）172分解方法是基于形狀識(shí)別，是一個(gè)分級(jí)過(guò)程的想法。形狀基元是在較低的級(jí)別上定義的，基元是形成區(qū)域的最簡(jiǎn)單的元素。圖是在較高的級(jí)別上構(gòu)建的節(jié)點(diǎn)由基元產(chǎn)生，弧描述了基元的相互關(guān)系。173分解問(wèn)題的解決包含兩個(gè)主要步驟：q第一步是把區(qū)域分割為簡(jiǎn)單的子區(qū)域（基

42、元）；q第二步是基元的分析?；銐虻暮?jiǎn)單以至于可以使用簡(jiǎn)單的標(biāo)量形狀屬性來(lái)有效地描述。 174分解的一般思想?yún)⒁娤聢D，其中給出了原始區(qū)域、一種可能的分解以及所產(chǎn)生的圖。初等凸子區(qū)域被標(biāo)注為初等子區(qū)域或核。核（在圖中以陰影表示）是屬于幾個(gè)初等凸子區(qū)域的子區(qū)域。175如果子區(qū)域由多邊形來(lái)表示，則圖的節(jié)點(diǎn)具有如下的信息：q節(jié)點(diǎn)類型表示初等子區(qū)域或核。q子區(qū)域頂點(diǎn)的個(gè)數(shù)由節(jié)點(diǎn)表示。q子區(qū)域的面積由節(jié)點(diǎn)表示。q子區(qū)域的主軸方向由節(jié)點(diǎn)表示。q子區(qū)域的重心由節(jié)點(diǎn)表示。176a)區(qū)域b)初等區(qū)域c)初等子區(qū)域以及核d)分解圖177區(qū)域分解為子區(qū)域或圖像分解為區(qū)域后，區(qū)域或圖像就可以表示為區(qū)域鄰近圖。區(qū)域鄰近圖把一個(gè)區(qū)域表示為一個(gè)圖節(jié)點(diǎn)，而鄰近區(qū)域的節(jié)點(diǎn)以邊連接起來(lái)。178179形狀類別的表示被認(rèn)為是形狀描述的具有挑戰(zhàn)性的問(wèn)題。我們期望形狀類別能很好地表示屬于這個(gè)類別的物體的一般形狀，并且能夠突出類別間的形狀差別，而類別內(nèi)允許的形狀變化不應(yīng)該