人工智能物體形狀的分析與識別

人工智能物體形狀的分析與識別教學(xué)內(nèi)容：多面體化為對非多面體景物的描述問題，并以這些描述為基礎(chǔ)，對物體形狀進(jìn)行分析與識別。教學(xué)重點(diǎn)：討論非多面物體的分析，并特別集中于形狀分析。教學(xué)難點(diǎn)：松弛標(biāo)示法、多層匹配法。教學(xué)方法：課堂講解教學(xué)要求：了解物體形狀分析與識別的基本概念1復(fù)雜形狀物體的表示一個(gè)好的形狀表示能夠由物體的部分視圖來識別物體，而且物體形狀的小變化只引起形狀描述的小變化。物體各部分的連接表示應(yīng)當(dāng)是很方便的，它能夠比較兩個(gè)物體的差別和相似性，而不僅是進(jìn)行簡單的分類。如果把復(fù)雜物體表示為被分割的比較簡單的部分以及這些部分間的相互關(guān)系，那么上述要求就比較容易得到滿足。對形狀的識別是由兩個(gè)相關(guān)描述的匹配獲得的。一個(gè)物體的部分視圖所產(chǎn)生的描述圖是完整的物體描述子圖，并能適當(dāng)匹配過程的需要。1、曲線形狀的描述與量度曲線描述對于一些特別物體(如字母符號)和三維景物(如某地區(qū)照片上的道路)分析是很重要的。此外，三維物體的形狀描述也往往被簡化為“輪廓”線條結(jié)構(gòu)。（1）曲線的存儲方法。依次采用曲線上各點(diǎn)的坐標(biāo)序列來表示線條是最容易的描述方法。如果只要存儲曲線的起點(diǎn)坐標(biāo)和依次各點(diǎn)的坐標(biāo)增量，那么就能夠顯著節(jié)省計(jì)算機(jī)內(nèi)存。（2）曲線的近似描述。曲線的緊密和結(jié)構(gòu)描述可以采用近似方法。一種方法是把曲線展開為正交級數(shù)；另一種是把曲線分段為一些比較簡單的曲線。線性分割分段近似是最常見的，而樣條函數(shù)（對多項(xiàng)式分段，在各連接點(diǎn)規(guī)定連續(xù)條件）具有普遍意義。（3）曲線形狀分析量度法。把一些與某曲線的分析近似法有關(guān)的系數(shù)用來表示該曲線形狀的特征。不同形狀的曲線具有不同的系數(shù)。不過，隨著比例尺、旋轉(zhuǎn)和遮斷情況的不同，這些系數(shù)可能變化很大。因此，這種分析量度法只適用于曲線數(shù)目較少及預(yù)期變化較小的情況。2、面積形狀的描述與量度采用圖形內(nèi)部不在邊界上的點(diǎn)來描述圖形，比較健全，因?yàn)楸容^小的面積變化能引起大得多的邊界變化。（1）簡單形狀的量度。由平面圖形的面積和周邊來粗略量度其形狀［面積×(周長)2］是個(gè)與圖形尺寸、位置和方向無關(guān)的量度不變式。把一個(gè)圖形的最小約束矩形定義為一個(gè)完全包圍該圖形的矩形，而且此矩形不會被任何其它的這類矩形所包圍，見圖10.10。一種改進(jìn)的對圖形形狀的近似量度是由它的凸緣進(jìn)行的。把凸緣定義為包圍已知圖形的最小凸出圖形。原圖形則由凸緣形狀及圖中凹面或凹陷的數(shù)目和形狀來描述，見圖10.11。圖10.10最小約束矩形圖10.11圖形的凸緣與凹陷（2）面積分析量度法。如同曲線描述一樣，借助于某些基本函數(shù)(如二維傅里葉級數(shù))對圖形展開或近似而得到的系數(shù)，可用于對圖形形狀進(jìn)行分析量度。對于一些基本函數(shù)，有可能組合這些系數(shù)以獲得一個(gè)對比例尺、位置和方向的不變式。2三維物體的形狀描述三維物體的形狀可由物體的外表面或這些外表面所包絡(luò)的容體來描述（可把洞孔描述為負(fù)容積）。三維物體描述特別困難之處在于，三維表面或容積需要二維圖象來推斷，尤其是對不可見表面的推斷。下面我們將著重分析由二維圖象進(jìn)行容積描述問題。1、物體形狀的廣義錐體表示可用廣義柱體(有時(shí)稱為廣義錐體)來表示物體的形狀。由于單一的廣義錐體能夠描述任意容積，因此，復(fù)雜的形狀能夠自然地分割為若干個(gè)比較簡單的廣義錐體來描述。圖10.13所示的螺絲起子可由4個(gè)廣義錐體來描述。其中，一個(gè)對應(yīng)于螺絲刀片，為一變化的矩形截面；另一個(gè)對應(yīng)于螺絲刀桿，具有圓截面；還有2個(gè)廣義錐體在手把上。簡化廣義錐體的準(zhǔn)則應(yīng)是其橫截面的形狀、尺寸或軸線方向不發(fā)生陡削變化。圖10.13螺絲起子的廣義錐體表示2、廣義錐體描述的計(jì)算廣義錐體表示不是變換表示，對于同一輸入可能有許多可供選擇的描述。需要從中選擇一種或多種最好的描述。（1）擬合表面數(shù)據(jù)。已知可見表面的三維位置以及對軸線和橫截面形狀的約束，就能擬合出最佳廣義錐體。對于已知形狀的橫截面，可能求得一個(gè)簡單的迭代解答?？紤]一個(gè)正圓柱體。起初，該圓柱體的軸線方向和橫截面都是未知的。任選一個(gè)方向之后，就能夠?qū)梢姳砻鏀M合出橢圓橫斷面。通過這些橫截面矩心的某軸線，并不需要與該軸線垂直。接著，能夠作出垂直于該軸的橫截面。重復(fù)此過程，直至只觀察到很小的橫截面變化為止。對于正圓柱體和正圓錐體，這個(gè)過程收斂得很快。對于任意形狀的物體，其收斂情況是不確定的，這時(shí)，要采用這種擬合技術(shù)，需要假設(shè)橫截面由橢圓所近似。（2）采用物體邊界。二維錐面能夠由物體的邊界來計(jì)算。如果二維輪廓是三維物體的投影，那么被計(jì)算的錐面就是所求的三維錐體的投影。3物體形狀識別方法物體或者由幾個(gè)物體組成的構(gòu)件，可由比較它們的描述及存儲在計(jì)算機(jī)內(nèi)的模型描述來識別。這些模型可能由下列方法獲?。捍鎯︻A(yù)先遇到的物體的機(jī)器描述，直接學(xué)習(xí)視圖數(shù)據(jù)序列，或者只是由操作人員提供。如果物體的描述是一張?zhí)匦郧鍐?，即特性矢量，那么能夠采用一般的?shù)學(xué)模式識別技術(shù)來識別。對于結(jié)構(gòu)性描述，需要采用比較復(fù)雜的匹配技術(shù)。此外，不要求用大量的內(nèi)存把一個(gè)描述與每一個(gè)存儲模型進(jìn)行匹配試驗(yàn)，沒有完全匹配而要選擇一個(gè)合適的子集，就需要進(jìn)行檢索。1、圖匹配法(Graphmatching)結(jié)構(gòu)性描述可視為圖或網(wǎng)絡(luò)。我們對評價(jià)兩幅圖的相似性感興趣。下面介紹一些有關(guān)相似性的量度。令某幅圖G：〈N，P，R〉定義為由結(jié)點(diǎn)集合N(表示物體的部件)、這些結(jié)合特性的集合P以及結(jié)點(diǎn)(節(jié)點(diǎn))間關(guān)系的集合R組成的。已知兩幅圖G：〈N，P，R〉和G′：〈N′，P′，R′〉，如果當(dāng)且僅當(dāng)P(n)與P′(n)對某一給定的相似性量度相似(即節(jié)點(diǎn)n的特性與節(jié)點(diǎn)n′的特性相似)時(shí)，就說形成一對配對(assignment)(n,n′)。如果有兩對配對(n1，n1′)和(n2，n2′)，對于R中的r和R′中的r′的所有關(guān)系使得r(n1，n1′)=r′（n2，n2′）成立，那么就說這兩對配對是兼容的。其中，我們假設(shè)關(guān)系是二元的。如果兩幅圖G和G′的節(jié)點(diǎn)具有一對一的配對，使得所有配對相互兼容，那么就稱這兩幅圖是同構(gòu)的(isomorphic)。其中，如果(n,n′)為一配對，那么仍然要求P(n)=P′(n′)。如果G的子圖與G′的子圖同構(gòu)，那么就稱圖G與G′為亞同構(gòu)的(subisomorphic)。2、松弛標(biāo)示法(Relaxationlabeling)把標(biāo)示問題定義為一個(gè)標(biāo)示集合與一個(gè)節(jié)點(diǎn)(或單元)集合的配對，使得標(biāo)示配對與給定約束相一致。這種標(biāo)示法有許多應(yīng)用，而且包含了圖匹配問題。這時(shí)，標(biāo)示是其它圖的節(jié)點(diǎn)。令N為被標(biāo)示節(jié)點(diǎn)的集合，L為可標(biāo)示的集合。對于每個(gè)ni，想要指定一個(gè)標(biāo)示集合Li，使得Li為L的一個(gè)子集，而且這些標(biāo)示與給定約束相容。對于不含糊的情況，每個(gè)集合Li只包含一個(gè)元。最簡單的約束是一元的，限制標(biāo)示只可能賦予某個(gè)確定的節(jié)點(diǎn)，而不考慮網(wǎng)絡(luò)中的其它節(jié)點(diǎn)。二元約束規(guī)定一對節(jié)點(diǎn)的標(biāo)示之間的關(guān)系。對于節(jié)點(diǎn)ni的一個(gè)標(biāo)示集合Li，可能與節(jié)點(diǎn)nj的一個(gè)標(biāo)示集合Lj相容，如果Li的每個(gè)標(biāo)示至少與Lj的一個(gè)標(biāo)示相容的話。這種相容性稱為弧相容性(arcconsistency)。一般說來，約束是n元的，而且弧相容性可能并不導(dǎo)致全局相容性(globalconsistency)。圖10.44給出一個(gè)例子，其一元約束為：要對每個(gè)節(jié)點(diǎn)標(biāo)示為紅色或綠色，而且要求相鄰點(diǎn)為不同的顏色。每當(dāng)對一個(gè)節(jié)點(diǎn)指定紅色或綠色之后，我們能夠?qū)ζ湎噜徆?jié)點(diǎn)指定一個(gè)相容的標(biāo)示，但是不能使這3個(gè)節(jié)點(diǎn)同時(shí)滿足全局約束。一個(gè)更大的約束是路徑相容性(pathconsistency)。兩個(gè)節(jié)點(diǎn)ni和nj(其標(biāo)示為1k和1l)是路徑一致的，如果網(wǎng)絡(luò)內(nèi)存在一條從ni至nj的路徑，對于此路徑上的每個(gè)節(jié)點(diǎn)不存在標(biāo)示集合，而對于兩端點(diǎn)同時(shí)與標(biāo)示1k和1l相一致(用二元法)。圖10.14的網(wǎng)絡(luò)不是距徑相容的。只考慮弧相容性，因?yàn)樗鼘p少可供選擇的方案往往是有用的。圖10.14弧一致但全局不一致的標(biāo)示3、多層匹配法(Multilevelmatching)圖匹配和景物松馳標(biāo)示技術(shù)是普遍的。不過，它們不能提供對相似和差異的滿意描述。采用數(shù)字權(quán)，結(jié)合非相關(guān)特性(如顏色和尺寸等)可能沒有多大意義。一個(gè)可供替代的方案是多層匹配法。對兩種描述進(jìn)行多層匹配的結(jié)果本身就是一種有關(guān)它們相似和差異的描述。如果由兩個(gè)模型匹配求出同樣的差異，那么可能需要對景物重新進(jìn)行檢查，以找出更精細(xì)的細(xì)節(jié)。已有一些采用這種方法來識別物體的例子。在某些情況下，兩個(gè)模型可能具有類似的連通性。這時(shí)，可由各個(gè)單獨(dú)部件