圖像分析及識別_課件_6

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

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

3、能力：即如果物體被遮擋而只有部分形狀信息可以得到的話，根據(jù)該描述，物體的形狀可以被識別到什么程度。 11局部/全局描述的特征：q全局描述子只能在整個物體的數(shù)據(jù)可以用來分析時才可使用；q局部描述子使用物體的部分信息來描述物體的局部特征，這樣局部描述子可用來描述遮擋物體。 12數(shù)學(xué)的和啟發(fā)式的方法：q一個典型的數(shù)學(xué)方法是基于傅立葉變換的形狀描述；q一個具有代表性的啟發(fā)式方法可以是細(xì)長形。 統(tǒng)計的或句法的物體描述。13描述所具有的對平移、旋轉(zhuǎn)、尺度變換的魯棒性。形狀描述在不同分辨率下的屬性。 14如果要描述形狀，那么需要考慮尺度（分辨率）問題，因為形狀可能會隨著圖像分辨率的變化而發(fā)生很大的變化。在高

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

5、體遮擋是形狀識別中的另外一個困難問題。q在這里形狀描述子的選擇必須是基于其描述局部物體特征的能力。19本章介紹描述子的分類是根據(jù)它們是否基于邊界信息或者基于物體區(qū)域的信息。這種形狀描述方法的分類對應(yīng)于以前描述的基于邊界的和基于區(qū)域的分割方法。2021對于區(qū)域描述，區(qū)域標(biāo)識是必需的。區(qū)域標(biāo)識是給每個區(qū)域（或邊界）標(biāo)志一個唯一的數(shù)字，這樣的標(biāo)識稱為標(biāo)注（labeling）或著色（coloring），或稱為連通分量標(biāo)注。而最大的整數(shù)標(biāo)號通常也就給出了圖像中區(qū)域的數(shù)目。 22假設(shè)分割后的圖像R由m個不相交的區(qū)域Ri組成。圖像R常常由若干物體和一個背景組成。其中RC是集合的補(bǔ)，Rb為背景，其它區(qū)域是物體

6、。imbiiCbRR, 123標(biāo)注算法的輸入通常是二值圖像或多亮度級別的圖像。多亮度級圖像常常用于表示標(biāo)注的結(jié)果，背景用零值表示，區(qū)域用它們的非零標(biāo)號表示。 下面是一個標(biāo)注分割后圖像的算法。24算法：4-鄰域和8-鄰域區(qū)域標(biāo)識第一遍掃描：一行一行地搜索整個圖像R，對每個非零像素R(i,j)賦一個非零的值v。根據(jù)鄰域像素的標(biāo)號來選擇v值，其中鄰域的性質(zhì)由下圖定義。（不考慮在圖像R外面的“鄰域”）。25 區(qū)域標(biāo)識的掩模： (a) 在4-連通下 (b) 在8-連通下 (c) 標(biāo)號沖突26q如果所有的鄰域都是背景像素（其像素值為零），則R(i,j)被賦予一個新的（到目前為止）沒使用過的標(biāo)號。q如果僅僅

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

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

9、信息。處理過程產(chǎn)生了一個數(shù)字序列。為了利用鏈碼的位置不變性，忽略其包含位置信息的第一個元素。這樣的鏈碼定義就是Freeman碼。384向鏈碼8向鏈碼39一個模4或模8的差分碼，稱為鏈碼的導(dǎo)數(shù)，它表示區(qū)域邊界元素的相對方向的另一個數(shù)字序列，以逆時針計數(shù)的90或45的倍數(shù)來度量。鏈碼對噪聲非常敏感，而且如果要用于識別，尺度和旋轉(zhuǎ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，141疊加在數(shù)字化邊界上的重取樣網(wǎng)格重取樣的結(jié)果4向鏈碼8向鏈碼42以下的描述子大部分基于被描述區(qū)域的幾何屬性。由于數(shù)字圖像的離散特點(diǎn)，它們

10、都對圖像的分辨率敏感。 43邊界長度：邊界長度是基本的區(qū)域?qū)傩?，可以簡單地從鏈碼表示中得到。垂直的和水平的步幅為單位長度，在8-連通下的對角步幅的長度為 。這可以說明在4-連通下邊界會更長些，其中對角步幅包含兩個直角步，總長度為2。244邊界長度隨著圖像光柵分辨率的增加而增加。區(qū)域面積不受更高分辨率的影響而收斂于某個限度值。數(shù)字化邊界可以用多邊形進(jìn)行任意精確性的近似。45被單元包圍的對象邊界最小周長多邊形(a)(b)46曲率：在連續(xù)的情況下，曲率被定義為斜率的變化率。在離散空間，曲率的描述必須稍做修改以克服因曲線不具有平滑性所造成的困難。47曲率標(biāo)量描述子（也稱為邊界平直度）是邊界像素的總數(shù)目

11、（長度）和邊界方向有顯著變化的邊界像素的數(shù)目的比率。方向改變的數(shù)目越少，邊界越平直。48對它的估算算法是基于檢測存在于從待估計的邊界像素出發(fā)到在任兩個方向上各b個邊界像素位置處的兩條線段間的角度的方法。這個角度不必以數(shù)字形式表示。參數(shù)b決定了對邊界方向局部變化的敏感度。49曲率50彎曲能量：邊界（曲線）的彎曲能量（BE）可以理解為把一個桿彎曲成所要求的形狀所需的能量，可以計算為邊界曲率c(k)的平方和除以邊界長度L。LkkcLBE12)(151為了表示邊界，可以使用Freeman鏈碼或它的平滑形式，參見下圖。彎曲能量沒有形狀重建能力。52鏈碼 0，0，2，0，1，0，7，6，0，0；曲率 0，

12、2，-2，1，-1，-1，-1，2，0；平方和給出了彎曲能量；平滑型53簽名：區(qū)域的簽名可以由法線輪廓距離的序列得到。對每一個邊界元素，法線輪廓距離為路徑長度的函數(shù)。對每一個邊界點(diǎn)A，到對面邊界點(diǎn)B的最近距離的道路為垂直于點(diǎn)A邊界切線的方向，參見下圖。對面不是一個對稱關(guān)系。54簽名對噪聲敏感，因而使用平滑后的簽名或平滑后的輪廓的簽名來降低對噪聲的敏感性。簽名可以用于對有重疊的物體的識別，或每當(dāng)只有部分輪廓可以獲得的情況下的識別。55(a) 構(gòu)造 (b) 圓和三角形的簽名 56弦的分布：連接區(qū)域邊界上任兩點(diǎn)的直線就是弦，而在輪廓上所有弦的長度和角度的分布可以用于形狀描述。 57弦的分布58假設(shè)C

13、是復(fù)平面上的封閉曲線（邊界）。以逆時針方向沿著這個曲線保持恒定速度移動，得到一個復(fù)函數(shù)Z(t)，這里t是時間變量。速度應(yīng)該選擇為使得環(huán)繞邊界一周的時間為2；然后沿曲線做多次遍歷得到一個周期為2的周期函數(shù)。這就允許了z(t)的傅立葉表示。 59系數(shù)Tn稱為曲線C的傅立葉描述子。相對于時間t，考慮曲線距離s會更有用，其中L是曲線長度。 nneTtzint)(Lst260傅立葉描述子Tn由下式給出。描述子受曲線形狀及曲線初始點(diǎn)的影響。 dseszLTLnnsLi0)2()(161對于數(shù)字圖像數(shù)據(jù)，邊界坐標(biāo)是離散的而函數(shù)z(t)不是連續(xù)的。假定z(k)是z(s)的離散型，其中為了得到不變的采樣間隔使用

14、4-連通；傅立葉描述子Tn可以從z(k)的離散傅立葉變換中計算出來：nTDFTkZ)(62一個封閉邊界可以表示為切線間的角度相對于其在邊界上的點(diǎn)之間的距離的函數(shù)。令k為在第k個邊界點(diǎn)測量的角度，令lk為起始邊界點(diǎn)和第k個邊界點(diǎn)的距離。一個周期函數(shù)可以被定義為：63描述子集合則為：kkkula)(Llukk220)(21dueuaSinun64(a) 描述符Tn (b) 描述符 Sn65傅立葉描述子的優(yōu)點(diǎn)是僅使用少數(shù)低階系數(shù)就得到了高質(zhì)量的邊界形狀表示。我們可以比較使用描述子Sn和Tn的結(jié)果：由于切線角度的變化相對比較顯著，描述子Sn有更多的高頻成分出現(xiàn)在邊界函數(shù)中，結(jié)果使它們不如描述子Tn那樣

15、快地衰減。66另外，由于常常導(dǎo)致不封閉的邊界，Sn描述子不適合于邊界重建。描述子Tn的值對于更高的頻率會非?？斓厮p，而它們的重建常常會產(chǎn)生封閉的邊界。Sn描述子不能用于正方形和正三角形等情況。67傅立葉描述子也可以用于計算區(qū)域面積、質(zhì)心的定位以及二次矩。傅立葉描述子是一種通用的技術(shù)，但是在描述局部信息時存在問題。傳統(tǒng)的傅立葉描述子不能用于遮擋物體的識別。68邊界（以及曲線）描述的另一種選擇是使用具有特定屬性的片段來表示邊界。如果對于所有的片段其類型都是已知的，則邊界可以描述為片段類型的一個鏈，碼字由代表類型的字母組成。這種描述適合于句法識別。69多邊形表示通過一個多邊形來近似區(qū)域，區(qū)域由它的

16、頂點(diǎn)來表示。多邊形表示可以作為對邊界的一個簡單分割的結(jié)果。邊界可以用各種精度來近似，如果需要一個更精確的描述，就可能需要使用更多的線段。70任意兩個邊界點(diǎn)x1和x2定義了一條線段，點(diǎn)x1、x2和x3的序列表示了一個線段鏈從點(diǎn)x1到點(diǎn)x2，從x2到x3。如果x1=x3，則為一個封閉的邊界。 71有很多類型的線片段的邊界表示。問題在于邊界頂點(diǎn)位置的確定，一個解決方法是使用分裂歸并算法。歸并的步驟為檢查邊界點(diǎn)的集合，只要滿足了一個片段的平直性標(biāo)準(zhǔn)，就把它們加到這個片段中。72如果失去了片段的平直性，最后連接的點(diǎn)就被標(biāo)記為頂點(diǎn)，并開始構(gòu)建一個新的片段。通過使用曲率（邊界平直率）標(biāo)準(zhǔn)，當(dāng)邊界點(diǎn)在邊界方向

17、上有顯著變化時，就可以檢測到邊界頂點(diǎn)。當(dāng)邊界擁有直的邊界片段時，這個方法很有效。73把邊界分割成更小片段的分裂方法有時會有幫助。如果使用了分裂方法，片段通常被分成兩段更小的新片段直到新的片段達(dá)到最后的要求。 74一個分裂的簡單過程從一條曲線的終點(diǎn)x1和x2開始，兩終點(diǎn)被一條線段連接起來。下一個步驟是在所有的曲線點(diǎn)中找到距離線段最遠(yuǎn)的曲線點(diǎn)x3。75如果被確定的點(diǎn)在預(yù)設(shè)的它和線段間的距離范圍內(nèi)，片段x1-x2就是最后的片段，而所有的曲線頂點(diǎn)都找到了，頂點(diǎn)x1和x2就是曲線的多邊形表示。否則點(diǎn)x3作為新的頂點(diǎn)，并且將這個過程在兩個結(jié)果片斷x1-x3和x3-x2上遞歸地調(diào)用。 76 遞歸的邊界分裂7

18、7把邊界分割成常數(shù)曲率的片段是邊界表示的另一個可能性。邊界也可以被分割成能用多項式來表示的片段，通常是二階的，例如圓形的、橢圓形的或拋物線形的線段。78對于句法形狀識別過程，片段被作為基元看待。一個典型的例子是染色體的句法描述和識別，其中邊界片段被分類為較大曲率的凸片段、較大曲率的凹片段、直線片段，等等。79 邊界片段鏈形式的染色體結(jié)構(gòu)描述碼字：d, b, a, b, c, b, a, b, d, b, a, b, c, b, a, b80我們已經(jīng)提到過形狀描述子對尺度（圖像分辨率）的敏感性是大多數(shù)描述子的一個不受歡迎的的特征。換句話說，形狀描述隨著尺度的變化而變化，在不同分辨率下會得到不同的

19、結(jié)果。 81如果曲線要被分成片段，這個問題仍然很突出。曲線的一些分割點(diǎn)在某一分辨率下存在。在其它分辨率下會消失因而沒有任何直接的對應(yīng)。 82考慮到這個問題，曲線分割的一個保證分割點(diǎn)位置連續(xù)變化的尺度空間方法就是一個顯著的成就。這個方法中，新的分割點(diǎn)只能在更高分辨率下出現(xiàn)，且已經(jīng)存在的分割點(diǎn)不會消失。 83這種技術(shù)是基于把單獨(dú)的高斯平滑核在一定的尺度范圍內(nèi)應(yīng)用于一維信號（例如，曲率函數(shù)），并將其結(jié)果微分兩次。通過檢測二階導(dǎo)數(shù)的過零點(diǎn)來確定曲率的峰值，過零點(diǎn)的位置給出了曲線分割點(diǎn)的位置。84在不同分辨率（不同的高斯核尺寸）下獲得分割點(diǎn)的不同位置。高斯核的一個重要性質(zhì)是分割點(diǎn)的位置隨著分辨率的變化而

20、連續(xù)變化，這可以從曲線的尺度空間圖像中看出。85曲線的細(xì)微細(xì)節(jié)在高斯平滑核尺寸的增大下成對地消失，并且總是兩個分割點(diǎn)合并起來而形成一個封閉的輪廓。說明了在粗分辨率下存在的任意分割點(diǎn)一定也在細(xì)的分辨率下存在。86此外，分割點(diǎn)的位置在最精細(xì)的分辨率下是最精確的。而且可以對它的位置通過使用尺度空間圖像從粗分辨率到細(xì)分辨率進(jìn)行跟蹤。 87一個多尺度的曲線描述可以通過區(qū)間樹表示出來。每一對過零點(diǎn)的位置被表示成一個矩形，它的位置對應(yīng)于分割點(diǎn)在曲線上的位置，它的高度表示分割點(diǎn)可以被檢測到的最低分辨率。88區(qū)間樹可以用于不同尺度下的曲線分解，同時保持了使用較高分辨率做片段描述的可能性。89(a) 作為尺度函數(shù)

21、的曲線分割點(diǎn)的數(shù)目和位置的變化(b) 曲線表示的區(qū)間樹形式 90在圖形學(xué)中，使用分段多項式插值來得到平滑曲線的這種曲線表示方法是十分普遍的。B樣條是分段多項式曲線，其形狀與它的控制多邊形緊密相關(guān)曲線的多邊形表示由一個頂點(diǎn)的鏈給出。 91三次B樣條是最常見的，因為這是包含曲率變化的最低階次。樣條有非常好的表示特性并且容易計算：第一，它們的形狀改變要小于其控制多邊形，并且它們不會像很多其它表示那樣在采樣點(diǎn)間振蕩。 92此外，對于n次B樣條，樣條曲線總是位于n+1個頂點(diǎn)的多邊形內(nèi)。第二，插值在特性上是局部的。如果一個控制多邊形的頂點(diǎn)改變了它的位置，所造成的樣條曲線的變化僅僅在那個頂點(diǎn)的一個小的鄰域內(nèi)

22、發(fā)生。 93第三，把由樣條表示的區(qū)域邊界與圖像數(shù)據(jù)相匹配的方法是基于對原始圖像數(shù)據(jù)的直接搜索。 94(a, b, c) n次B樣條的n+1個頂點(diǎn)的多邊形(d) 3次樣條95令xi，i=l, , n為B樣條插值曲線的點(diǎn)，稱此插值曲線為x(s)。參數(shù)s在點(diǎn)xi間線性變化，即xi=x(i)。三次B樣條曲線的每一個部分都是三次多項式，這意味著它以及它的一階和二階導(dǎo)數(shù)都是連續(xù)的。B樣條由下式給出：9610)()(niiisBvsx其中vi為表示樣條曲線的系數(shù)，Bi(s)是基函數(shù)，其形狀由樣條的階次給出。97系數(shù)vi具有的信息對偶于樣條曲線點(diǎn)的信息vi的值可以從xi中得出，反之亦然。系數(shù)vi代表了控制多邊

23、形的頂點(diǎn)，而且如果有n個點(diǎn)xi，則必須有n+2個點(diǎn)vi。兩個端點(diǎn)v0和vn+1由邊界條件確定。 98樣條生成的曲線通常是令人滿意的。它們提供了一個好的曲線近似，在圖像分析的曲線表示問題中也很容易使用。樣條對于尺度的變化非常敏感。99還有很多可以用來描述二維曲線和輪廓的其它方法和途徑。 Hough變換擁有極好的形狀描述能力。使用統(tǒng)計矩的基于區(qū)域的形狀描述。對形狀的分形的研究方法，在圖像形狀的描述中正在受到越來越多的關(guān)注。 100數(shù)學(xué)形態(tài)學(xué)可以用于形狀描述，特別是在與區(qū)域骨架重建相關(guān)的方面上。神經(jīng)網(wǎng)絡(luò)可以直接用于識別以原始邊界表示的形狀。用無噪聲的參考形狀的輪廓序列來訓(xùn)練，且為了提高魯棒性在訓(xùn)練的

24、后期階段使用帶有噪聲的數(shù)據(jù)。101形狀不變量是當(dāng)前機(jī)器視覺領(lǐng)域的一個非?；钴S的研究方向。 即便在機(jī)器視覺中形狀不變性是一個新的方法，但不變量理論并不是新的，它的很多原理早在19世紀(jì)就出現(xiàn)了。102正如多次所提到那樣，物體描述對于物體識別來說是必要的。不幸的是，目前所討論過的所有形狀描述子都依賴于視點(diǎn)，這意味著由于物體或觀察者的位置變化，使得識別物體常常是不可能的。103相同的矩形截面在圖像平面中被表示為不同的多邊形 104形狀描述不變性的作用是顯然的。形狀不變量表示了一種幾何結(jié)構(gòu)的屬性，它在一個適當(dāng)?shù)淖儞Q類下保持不變。機(jī)器視覺特別關(guān)心透視變換類。 105共線性是透視不變性圖像特征的最簡單的例子

25、。在任意的透視變換下任何直線都被投影為直線。類似地，透視不變性形狀描述的基本思想是找到這樣的形狀特征，它不受物體和圖像平面間的變換的影響。 106一種標(biāo)準(zhǔn)的透視不變性描述技術(shù)是：假設(shè)知道物體的姿態(tài)（位置和方向），把它變換到特定的坐標(biāo)系統(tǒng)中，然后在這個坐標(biāo)系統(tǒng)中測量形狀特征，形成一個不變的描述。然而對每一個物體和每一幅圖，都必須假設(shè)知道姿態(tài)，這使得該方法困難而不可靠。 107不變量理論的應(yīng)用提供了另一個途徑，其中不變量描述子可以直接從圖像數(shù)據(jù)中計算出來而不需要專門的坐標(biāo)系統(tǒng)。 現(xiàn)在將給出幾個不變量的例子。108首先給出交比的定義。交比是代表了透視線的一個經(jīng)典的不變量。就像前面提到的，一條直線總是

26、投影為一條直線。109任意四個共線點(diǎn)A, B, C, D可以用交比不變量描述為： 其中(A-C)表示點(diǎn)A和點(diǎn)C間的距離。交比依賴于被標(biāo)注的四個共線點(diǎn)的順序。CBDADBCAI110交比：四個共線點(diǎn)形成一個透視不變數(shù) 111 一個四條共面共點(diǎn)的直線（交于同一點(diǎn)）的系統(tǒng)對偶于一個四個共線點(diǎn)的系統(tǒng)并且交比是它的不變量。 112一個五條共面直線的系統(tǒng)產(chǎn)生兩個不變量。5314215214311MMMMI 5214325324312MMMMI 113其中Mijk=(1i, lj, lk)。li=(li1, li2, li3)T是一條直線li1x+li2y+li3=0的表示，其中i1, 5，并且|M|是矩陣

27、M的行列式。如果生成矩陣Mijk的三條直線是共點(diǎn)的，則矩陣變?yōu)槠娈惖亩蛔兞烤蜎]有定義。 114一個五個共面點(diǎn)的系統(tǒng)對偶于一個五條直線的系統(tǒng)，并且可以生成同樣的的兩個不變量。這兩個獨(dú)立作用的不變量也可由兩組共面共點(diǎn)的四條直線的兩個交比來產(chǎn)生，參見下圖。115注意即使產(chǎn)生了除了下圖中給出的組合之外，也僅有兩個已介紹的獨(dú)立作用的不變量存在。116 (a) 共面點(diǎn)(b) 五點(diǎn)形成一個四條共點(diǎn)直線的系統(tǒng)(c) 相同的五點(diǎn)形成另一個四條共點(diǎn)直線的系統(tǒng) 117 一條平面二次曲線可以由一個方程表示： 對于X=(x, y, 1)T, 則二次曲線也可由矩陣C來定義，022feydxcybxyaxfedecbdb

28、aC222222118以及對任意的由矩陣C表示的二次曲線，以及兩條不切于二次曲線的共面直線，可以定義一個不變量: 0CXXT2121112211lCllCllClITTT119對于一條二次曲線和兩個共面點(diǎn)，可以形成同樣的不變量。 對于兩條由它們的歸一化矩陣C1和C2 (|Ci|=1)表示的二次曲線，可以確定兩個不變量。 2111CCTraceI1122CCTraceI120矩陣的跡（Trace）是主對角線元素的和。 對于非歸一化的二次曲線，所關(guān)聯(lián)的二次型的不變量為：31212111CCCCTraceI31121122CCCCTraceI121以及二次曲線的兩個真正的不變量為：212112211

29、1CCCCTraceCCTraceI1222111122CCCCTraceCCTraceI122兩條平面二次曲線唯一地確定了四個相交點(diǎn)，而任意選擇一個非相交點(diǎn)和四個相交點(diǎn)都可成一個五點(diǎn)系統(tǒng)。因此，對于這一對二次曲線，像五點(diǎn)系統(tǒng)一樣，存在兩個不變量。123很多人造物體由圓和直線組成，這些不變量可用于它們的描述。然而，如果物體具有不能用代數(shù)曲線表示的輪廓，情況就非常困難了。 124在機(jī)器觀覺應(yīng)用中，設(shè)計新的不變量是不變量理論的一個重要部分。最簡單的方法是組合基本的不變量，從這些組合中形成新的不變量。下圖給出了一個這樣的物體識別的例子。 125 從一個任意視點(diǎn)拍攝的重疊物體的原始圖像基于直線和二次曲

30、線不變量的物體識別126127我們可以使用邊界信息來描述區(qū)域，也可以從區(qū)域自身來描述形狀。 由啟發(fā)式方法表示的一大類形狀描述技術(shù)，在簡單形狀的描述中可產(chǎn)生能夠接受的結(jié)果。例如，區(qū)域的面積、矩形度、細(xì)長度、方向、緊致度等等。128但是它們不能用于區(qū)域重建且對于較復(fù)雜的形狀也不起作用。對于更復(fù)雜的區(qū)域的描述，必須基于其它的把區(qū)域分解成更小和更簡單的子區(qū)域的方法，然后這些子區(qū)域可以分別地用啟發(fā)式方法來描述。 129物體用平面圖來表示，其節(jié)點(diǎn)代表由區(qū)域分解產(chǎn)生的子區(qū)域，而區(qū)域形狀由圖的屬性來描述。有兩種一般的途徑來得到子區(qū)域的圖：130第一種是區(qū)域細(xì)化，它導(dǎo)致可以用圖來描述區(qū)域骨架。第二種可選的方法從

31、區(qū)域分解成子區(qū)域開始，然后子區(qū)域由節(jié)點(diǎn)來表示，節(jié)點(diǎn)的弧表示了子區(qū)域的相鄰關(guān)系。通常規(guī)定子區(qū)域是凸的。131區(qū)域的圖表示有很多優(yōu)點(diǎn)所產(chǎn)生的圖具有以下特點(diǎn)： q它是平移和旋轉(zhuǎn)的不變量，位置和旋轉(zhuǎn)可以被包括在圖的定義中。q它對形狀的微小改變不敏感。q相對區(qū)域的尺寸是很好的不變量。132q它生成的是可理解的表示。q它很容易被用來獲得圖的具有一定信息的特征。q它適合于句法識別。133另一方面，這種形式的形狀表示可能是很難得到的，而且分類器的學(xué)習(xí)階段也不是容易的。然而，如果我們貼近計算機(jī)視覺的現(xiàn)實(shí)的話，為了理解復(fù)雜圖像，別無選擇。134存在許多簡單的啟發(fā)式形狀描述子，它與統(tǒng)計特征描述有關(guān)。這些方法是基本的

32、，它們用在復(fù)雜區(qū)域的子區(qū)域的描述中，而且也可用于定義圖節(jié)點(diǎn)的分類。135 最簡單的且最自然的區(qū)域?qū)傩允撬拿娣e，由區(qū)域包含的像素個數(shù)給出。 如果圖像被表示為一個矩形光柵，那么區(qū)域像素的簡單計數(shù)就會提供其面積。136 歐拉數(shù)描述了物體的一個簡單的拓?fù)洳蛔兊膶傩?。它基于物體的連通部分的數(shù)目S以及物體中孔的數(shù)目N（一個物體可以包含不止一個區(qū)域，否則連通部分的數(shù)目等于1）。于是有：=S-N 137定義水平的和垂直的區(qū)域投影ph(i)和pv(j)為：根據(jù)投影的區(qū)域描述通常和二值圖像處理相關(guān)。投影可以被當(dāng)作定義相關(guān)區(qū)域描述子的一個基礎(chǔ)。ivjhjifjpjifip),()(),()(138垂直投影寬度水平

33、投影高度139 最簡單的離心率特征是最長弦A和垂直于A的最長弦B的長度比（一個物體的主次軸的比）。另一個近似的離心率的度量是基于主區(qū)域慣量軸的比。 140 細(xì)長度是區(qū)域外接矩形的長寬比。這是一個包圍形狀的最小面積的矩形，它是通過以離散步幅旋轉(zhuǎn)直到達(dá)到最小值來確定的。這個準(zhǔn)則在彎曲的區(qū)域下達(dá)不到（參見圖b），對于這種區(qū)域的細(xì)長度的估計必須基于最大區(qū)域厚度。141(a) 外接矩形給出了可接受的結(jié)果(b) 外接矩形不能表示細(xì)長度142 令Fk為區(qū)域面積和外接矩形面積的比，矩形具有方向k。矩形的方向像前面一樣以離散步幅旋轉(zhuǎn)，矩形度度量為這個比率Fk的最大矩形值：)(maxkkF矩形度143方向僅需旋轉(zhuǎn)

34、一個象限。矩形度設(shè)定的數(shù)值在區(qū)間(0，1中，1代表一個完美的矩形區(qū)域。 144 方向是僅在細(xì)長區(qū)域下有意義的屬性。如果區(qū)域是細(xì)長的，方向就是最小外接矩形的最長邊的方向。 145 緊致度是獨(dú)立于線性變換的一個通用的形狀描述特征，由下式給出：在歐氏空間里最緊致的區(qū)域是圓。 arealengthborderregion2)_(緊致度146(a) 緊致的 (b) 非緊致的147區(qū)域的矩表示把一個歸一化的灰度級圖像函數(shù)理解為一個2維隨機(jī)變量的概率密度。隨機(jī)變量的屬性用統(tǒng)計特征矩來描述。 通過假設(shè)非零的像素值表示區(qū)域，矩可以用于二值或灰度級的區(qū)域描述。 148(p+q)階矩依賴于尺度、平移、旋轉(zhuǎn)、甚至灰度

35、級上的變換，由下式給出：在數(shù)字圖像中，我們計算求和式： dxdyyxfyxmqppq),( ijqppqjifjim),(149其中x, y, i, j是區(qū)域點(diǎn)的坐標(biāo)。如果使用中心矩，可以獲得平移不變性。在數(shù)字圖像中： dxdyyxfyyxxqcpcpq),()()( ijqcpcpqjifyjxi),()()(150其中Xc和Yc是區(qū)域重心（質(zhì)心）的坐標(biāo)，它可以由下面的關(guān)系來得到：00010010mmYcmmXc151一個區(qū)域R是凸的，當(dāng)且僅當(dāng)對于任意兩點(diǎn)x1, x2R，由它的端點(diǎn)x1和x2定義的整個直線段x1x2在區(qū)域R的內(nèi)部。區(qū)域的凸包是滿足條件RH的最小凸區(qū)域H，參見下圖。 15215

36、3凸包在數(shù)字?jǐn)?shù)據(jù)中具有一些特殊性質(zhì)。例如，凹的部分在數(shù)字?jǐn)?shù)據(jù)中由于旋轉(zhuǎn)會出現(xiàn)或消失，因此凸包在數(shù)字空間中不是旋轉(zhuǎn)不變量。凸包可以用來描述區(qū)域形狀屬性而且可以用于建立區(qū)域凹狀的樹型結(jié)構(gòu)。 154離散凸包的構(gòu)建算法 找到具有最小行坐標(biāo)的區(qū)域R的所有像素，在它們中間，找到具有最小列坐標(biāo)的像素P1。賦值Rk=P1，v=(0, -1)，向量v表示凸包的前一直線段的方向。 155以逆時針方向搜索區(qū)域邊界并且對每一個位于點(diǎn)P1后（在邊界搜索方向上見上圖）的邊界點(diǎn)Pn計算方向角n。方向角n是向量PkPn的角度。滿足條件q=minnn的點(diǎn)Pq是區(qū)域凸包的一個元素（頂點(diǎn)）。156賦值v=PkPq, Pk=Pq。重

37、復(fù)執(zhí)行步驟2和3直到Pk=P1。 157令待檢測凸包的多邊形為簡單多邊形P=v1, v2, , vn。并且令頂點(diǎn)以這個順序來處理。序列P中的前三個頂點(diǎn)A, B, C形成一個三角形（如果不共線），而這個三角形表示了這前三個點(diǎn)的凸包（見圖a）。Melkman的凸包檢測算法158然后在序列中測試下一個頂點(diǎn)D是否位于當(dāng)前凸包的內(nèi)部或外部。如果D位于內(nèi)部，則當(dāng)前的凸包不改變（見圖b）。如果D位于當(dāng)前凸包的外部，它就必須成為一個新的凸包頂點(diǎn)（見圖c）。159而基于當(dāng)前的凸包形狀，或者沒有、或者一個或幾個頂點(diǎn)必須從當(dāng)前的凸包中去掉（見圖c和d）。對序列P中所有剩下的頂點(diǎn)重復(fù)這個過程。160前三個頂點(diǎn)A, B

38、, C形成一個三角形；如果下一個頂點(diǎn)D位于當(dāng)前凸包ABC的內(nèi)部， 則當(dāng)前凸包不變；如果下一個頂點(diǎn)D位于當(dāng)前凸包的外部，則它成為當(dāng)前新的凸包ABCDA的一個新頂點(diǎn)；在這種情況下，必須從當(dāng)前的凸包中支掉頂點(diǎn)B而新的凸包為ADCA。161 被處理的區(qū)域-多邊形ABCDEA輸入和處理頂點(diǎn)D頂點(diǎn)D成為當(dāng)前凸包ADC的一個新頂點(diǎn)輸入和處理頂點(diǎn)E，E沒有成為當(dāng)前凸包的一個新的頂點(diǎn)結(jié)果凸包DCAD162區(qū)域圖是基于區(qū)域骨架的，第一步是骨架構(gòu)建。數(shù)學(xué)形態(tài)學(xué)是一個可用來獲得區(qū)域骨架的有力工具。大多數(shù)的細(xì)化過程重復(fù)地去除邊界元素直至找到最大厚度為1或2的像素集合。 163構(gòu)建骨架有四種基本的途徑：q細(xì)化迭代地去除區(qū)

39、域邊界像素；q從邊界開始的波傳播；q在區(qū)域的距離變換圖像中檢測局部最大值；q分析的方法。164算法：通過細(xì)化提取骨架 令R為區(qū)域像素的集合，Hi(R)為它的內(nèi)部邊界，而HO(R)為它的外部邊界。令S(R)為區(qū)域R中的部分像素的集合，這些像素在8-連通下的所有鄰居或者來自內(nèi)部邊界Hi(R)或者來自背景R的余集。賦值Rold=R。165構(gòu)建一個新的區(qū)域Rnew為如下的進(jìn)一步細(xì)化的結(jié)果：如果Rnew=Rold，結(jié)束迭代并轉(zhuǎn)步驟4。否則賦值Rold=Rnew，重復(fù)步驟2。 Rnew是骨架像素的集合（即區(qū)域R的骨架）。)()()(oldoldooldioldoldnewRRSHRHRRSR166細(xì)化過程

40、常常使用中軸變換來構(gòu)建區(qū)域骨架。在中軸的定義下，骨架是滿足以下條件的所有區(qū)域點(diǎn)的集合：它至少與兩個分開的邊界點(diǎn)具有相同的到區(qū)域邊界的最小距離。由這個條件產(chǎn)生的骨架的例子參見下圖。 167使用一個距離變換給每個區(qū)域像素賦予其到區(qū)域邊界的（最?。┚嚯x值，這樣就可以構(gòu)建骨架?？梢哉J(rèn)為骨架是到區(qū)域邊界的距離取得局部最大值的像素的集合。 168每一個骨架的元素可以附有它到邊界距離的信息，這提供了一個重建區(qū)域的方法：以骨架元素為中心點(diǎn)，以所保存的距離值為半徑，所有這樣的圓盤所形成的包絡(luò)曲線就構(gòu)成區(qū)域的邊界。 169區(qū)域骨架：邊界的小變化在骨架上有顯著的影響170 (a) 原始圖像 (b) 區(qū)域骨架（為了顯

41、 示而加粗了）171 (a) 原始圖像 (b) 區(qū)域骨架（為了顯 示而加粗了）172分解方法是基于形狀識別，是一個分級過程的想法。形狀基元是在較低的級別上定義的，基元是形成區(qū)域的最簡單的元素。圖是在較高的級別上構(gòu)建的節(jié)點(diǎn)由基元產(chǎn)生，弧描述了基元的相互關(guān)系。173分解問題的解決包含兩個主要步驟：q第一步是把區(qū)域分割為簡單的子區(qū)域（基元）；q第二步是基元的分析?；銐虻暮唵我灾劣诳梢允褂煤唵蔚臉?biāo)量形狀屬性來有效地描述。 174分解的一般思想?yún)⒁娤聢D，其中給出了原始區(qū)域、一種可能的分解以及所產(chǎn)生的圖。初等凸子區(qū)域被標(biāo)注為初等子區(qū)域或核。核（在圖中以陰影表示）是屬于幾個初等凸子區(qū)域的子區(qū)域。175如果子區(qū)域由多邊形來表示，則圖的節(jié)點(diǎn)具有如下的信息：q節(jié)點(diǎn)類型表示初等子區(qū)域或核。q子區(qū)域頂點(diǎn)的個數(shù)由節(jié)點(diǎn)表示。q子區(qū)域的面積由節(jié)點(diǎn)表示。q子區(qū)域的主軸方向由節(jié)點(diǎn)表示。q子區(qū)域的重心由節(jié)點(diǎn)表示。176區(qū)域初等區(qū)域初等子區(qū)域以及核分解圖177區(qū)域分解為子區(qū)域或圖像分解為區(qū)域后，區(qū)域或圖像就可以表示為區(qū)域鄰近圖。區(qū)域鄰近圖把一個區(qū)域表示為一個圖節(jié)點(diǎn)，而鄰近區(qū)域的節(jié)點(diǎn)以邊連接起來。178179形狀類別的表示被認(rèn)為是形狀描述的具有挑戰(zhàn)性的問題。我們期望形狀類別能很好地表示屬于這個類別的物體的一般形狀，并且能夠突出類別間的形狀差別，而類別內(nèi)允許的形狀變化不應(yīng)該影響其描述。180有兩種形狀