1、章毓晉清華大學(xué)電子工程系 100084 北京圖象工程第2頁第12講第第1212章章 外形分析外形分析 12.1關(guān)于外形的討論12.2平面外形的分類12.3外形特性的描畫12.4基于技術(shù)的描畫12.5拓?fù)錁?gòu)造的描畫12.6分形維數(shù)第3頁第12講12.1 關(guān)于外形的討論關(guān)于外形的討論1.什么是外形什么是外形許多人都知道，但沒人能全面定義的許多人都知道，但沒人能全面定義的概念概念讀書辨字時，主要是外形信息在起作讀書辨字時，主要是外形信息在起作用用但用言語來解釋外形是比較難的但用言語來解釋外形是比較難的 幾個看起來簡單，但很難回答的問題幾個看起來簡單，但很難回答的問題 (1)什么是外形？什么是外形？(

2、2)什么是客觀世界中一個物體的外什么是客觀世界中一個物體的外形？形？(3)什么是圖象中一個區(qū)域的外形？什么是圖象中一個區(qū)域的外形？第4頁第12講1.什么是外形什么是外形字典中關(guān)于外形的幾個定義：字典中關(guān)于外形的幾個定義： (1)外形是由輪廓或外形所確定的外外形是由輪廓或外形所確定的外觀觀(2)外形是具有形體或圖案的東西外形是具有形體或圖案的東西(3)外形是伴隨方式的外形是伴隨方式的(4)外形是實踐物體或幾何圖案的一外形是實踐物體或幾何圖案的一個性個性質(zhì)，該性質(zhì)依賴于組成該物體或質(zhì)，該性質(zhì)依賴于組成該物體或圖案圖案的輪廓或外表的一切點間的相對的輪廓或外表的一切點間的相對位置位置12.1 關(guān)于外形

3、的討論關(guān)于外形的討論第5頁第12講1.什么是外形什么是外形外形的定義：外形的定義： 一個目的的外形就是該目的邊境上一個目的的外形就是該目的邊境上一切點一切點組成的方式組成的方式 外形可定義為外形可定義為“連通的點集合連通的點集合普通思索外形時，均思索普通思索外形時，均思索“單個且單個且“完好完好的目的。的目的。“單個和單個和“完好均完好均可用連通的數(shù)可用連通的數(shù) 學(xué)概念來描畫學(xué)概念來描畫12.1 關(guān)于外形的討論關(guān)于外形的討論第6頁第12講2.外形研討的任務(wù)內(nèi)容外形研討的任務(wù)內(nèi)容(1)預(yù)處置預(yù)處置采集圖象，存儲圖象，消除噪聲，采集圖象，存儲圖象，消除噪聲，分割目的分割目的(2)外形表達(dá)和描畫外形

4、表達(dá)和描畫(3)外形分類外形分類對給定外形的目確實定它能否屬于對給定外形的目確實定它能否屬于某個預(yù)先定義某個預(yù)先定義 的類別有監(jiān)視分類的類別有監(jiān)視分類 對預(yù)先沒有分類的外形如何定義或?qū)︻A(yù)先沒有分類的外形如何定義或辨識其中的類辨識其中的類 別無監(jiān)視分類或聚類別無監(jiān)視分類或聚類 12.1 關(guān)于外形的討論關(guān)于外形的討論第7頁第12講3.外形分析的方法外形分析的方法 描畫常采用的三類方法描畫常采用的三類方法 特征的方法，外形變換的方法，基特征的方法，外形變換的方法，基于關(guān)系的方法于關(guān)系的方法描畫符描畫符一個外形性質(zhì)可用基于不同的實際一個外形性質(zhì)可用基于不同的實際技術(shù)的技術(shù)的描畫符來描畫描畫符來描畫借助

5、同一種實際技術(shù)也可以獲得不借助同一種實際技術(shù)也可以獲得不同的描同的描述符以描寫目的外形的不同性述符以描寫目的外形的不同性質(zhì)質(zhì) 12.1 關(guān)于外形的討論關(guān)于外形的討論第8頁第12講12.2 平面外形的分類平面外形的分類各階導(dǎo)數(shù)均存在 沒有自交叉 第9頁第12講12.2 平面外形的分類平面外形的分類(1)粗和細(xì)外形粗和細(xì)外形粗外形指包括內(nèi)部的區(qū)域粗外形指包括內(nèi)部的區(qū)域細(xì)外形指沒有充溢的區(qū)域細(xì)外形指沒有充溢的區(qū)域2-D目的的外形目的的外形silhouette W第10頁第12講12.2 平面外形的分類平面外形的分類(2)參數(shù)曲線參數(shù)曲線點在點在2-D空間空間挪動得到的軌跡挪動得到的軌跡位置矢量的集合

6、位置矢量的集合參數(shù)為參數(shù)為t 時的點速度時的點速度 XY0p t + dt()p t ( )dp)()(d)()d(limd)()d(limd)()d(limdd)(0d0d0dtytxttyttyttxttxtttttttttpppp第11頁第12講12.2 平面外形的分類平面外形的分類(3)規(guī)那么曲線規(guī)那么曲線假設(shè)一條參數(shù)曲線的速度永遠(yuǎn)不為假設(shè)一條參數(shù)曲線的速度永遠(yuǎn)不為零，那么零，那么 稱該曲線為規(guī)那么曲線稱該曲線為規(guī)那么曲線規(guī)那么曲線速度的一個重要性質(zhì)：規(guī)那么曲線速度的一個重要性質(zhì)：各點的速度矢量都與曲線在該點相各點的速度矢量都與曲線在該點相切切 歸一化以使沿曲線的切向矢量為單歸一化以使

7、沿曲線的切向矢量為單位大小位大小1)()()()(ttttpp第12頁第12講12.3 外形特性的描畫外形特性的描畫 外形和尺寸外形和尺寸任何目的均可用它的外形和尺寸來任何目的均可用它的外形和尺寸來描畫？描畫？外形性質(zhì)與尺寸性質(zhì)不相關(guān)？外形性質(zhì)與尺寸性質(zhì)不相關(guān)？描畫微構(gòu)造的外形參數(shù)應(yīng)具有一些描畫微構(gòu)造的外形參數(shù)應(yīng)具有一些共性共性 12.3.1外形緊湊性描畫外形緊湊性描畫12.3.2外形復(fù)雜性描畫外形復(fù)雜性描畫第13頁第12講12.3.1 外形緊湊性描畫 對應(yīng)目的的幾何參數(shù)，所以均與尺度有關(guān) 1. 外觀比外觀比aspect ratio常用來描畫塑性形變后目的的外形細(xì)長程度可借助目的圍盒定義L和W

8、分別是目的圍盒的長和寬 WLR 第14頁第12講12.3.1 外形緊湊性描畫 2、外形因子基于周長和面積F 的值當(dāng)區(qū)域為圓時到達(dá)最小1沒有量綱，所以對尺度變化不敏感 問題：外形不同，外形因子能夠一樣ABF42 pppppppppppppppppppp第15頁第12講12.3.1 外形緊湊性描畫 3、偏心率利用整個區(qū)域的一切象素描畫了區(qū)域的緊湊性伸長情況由慣量推出 轉(zhuǎn)動慣量 慣性積qpXY2iiymA2iixmBiiiyxmC第16頁第12講12.3.1 外形緊湊性描畫 3、偏心率半軸長E = p / q E 的值當(dāng)區(qū)域為圓時到達(dá)最小1qpXY 4)()( 222CBABAp 4)()( 222

9、CBABAq第17頁第12講12.3.1 外形緊湊性描畫 4、球狀性本來指3-D目的的外表積和體積的比值 基于區(qū)域的內(nèi)切圓和外接圓圓心為重心區(qū)域為圓時 S 值到達(dá)最大1rirc重心cirrS 第18頁第12講12.3.1 外形緊湊性描畫 5、圓形性利用一切輪廓點區(qū)域趨向圓時 C 值趨于無窮RRC10) ),(,( 1KkkkRyxyxK102 ) ),(,( 1KkRkkRyxyxK重心第19頁第12講12.3.1 外形緊湊性描畫 區(qū)域描畫符例如幾個典型的簡單物體第20頁第12講12.3.1 外形緊湊性描畫 幾個描畫符的比較幾個描畫符的比較外觀比：外觀比：比較容易計算比較容易計算但不適宜用來描

10、畫非規(guī)那么性但不適宜用來描畫非規(guī)那么性外形因子：外形因子：對非規(guī)那么性比較敏感對非規(guī)那么性比較敏感 對外形伸長度方面不如外觀比對外形伸長度方面不如外觀比敏感敏感 球狀性：球狀性：對伸長度和不規(guī)那么性都比較對伸長度和不規(guī)那么性都比較敏感敏感第21頁第12講12.3.2 外形復(fù)雜性描畫 (1)細(xì)度比例thinness ratio：外形因子的倒數(shù)，即4p(A/B2)(2)面積周長比：A/B(3)矩形度rectangularity：定義為A/AMER，其中AMER代表圍盒面積。(4)與邊境的平均間隔mean distance to the boundary：定義為A /(5)輪廓溫度temperatu

11、re：由熱力學(xué)原理得來，定義為其中H為目的凸包的周長。2R)/()2(log2HBBT第22頁第12講12.3.2 外形復(fù)雜性描畫 飽和度飽和度在一定意義下反映了目的的緊湊 性緊致性它思索的是目的在其圍盒中的充溢程度詳細(xì)可用屬于目的的像素數(shù)與整個圍盒所包含的像素數(shù)之比來計算 第23頁第12講12.4 基于技術(shù)的描畫基于技術(shù)的描畫 相關(guān)的描畫符由一種表達(dá)技術(shù)衍生出來的描畫符由根本描畫符推導(dǎo)出來的描畫符 12.4.1基于多邊形表達(dá)的外形描畫12.4.2基于曲率的外形描畫 第24頁第12講12.4.1 基于多邊形表達(dá)的外形描畫 1.直接計算的特征直接計算的特征可直接從多邊形表達(dá)輪廓算出的特征可直接從

12、多邊形表達(dá)輪廓算出的特征：(1)角點或頂點的個數(shù)角點或頂點的個數(shù)(2)角度和邊的統(tǒng)計量，如均值，中值，角度和邊的統(tǒng)計量，如均值，中值，方差方差(3)最長邊和最短邊的長度，它們的長度最長邊和最短邊的長度，它們的長度比和它比和它們間的角度們間的角度(4)最大內(nèi)角與一切內(nèi)角和的比值最大內(nèi)角與一切內(nèi)角和的比值(5)各個內(nèi)角的絕對差的均值各個內(nèi)角的絕對差的均值第25頁第12講12.4.1 基于多邊形表達(dá)的外形描畫 2.外形數(shù)的比較外形數(shù)的比較兩個外形兩個外形 A 和和 B 之間的類似度之間的類似度 k 是是這兩個外形數(shù)之間的最大公共外形數(shù)這兩個外形數(shù)之間的最大公共外形數(shù)假設(shè)假設(shè) S4(A) = S4(B

13、)，S6(A) = S6(B)，Sk(A) = Sk(B)，Sk+2(A) Sk+2(B)，那么，那么 A 和和 B 的類似度就是的類似度就是 k 兩個外形間的間隔：它們類似度的兩個外形間的間隔：它們類似度的倒數(shù)：倒數(shù)： kBAD/1) ,( 第26頁第12講12.4.1 基于多邊形表達(dá)的外形描畫 3.區(qū)域的標(biāo)志區(qū)域的標(biāo)志對區(qū)域中一切象素沿不同方向進(jìn)展投對區(qū)域中一切象素沿不同方向進(jìn)展投影影點陣表達(dá)的字母多邊形逼近后的結(jié)點陣表達(dá)的字母多邊形逼近后的結(jié)果果 垂直投影：垂直投影： 得到一樣的結(jié)果得到一樣的結(jié)果 程度投影：程度投影： 得到不同的結(jié)果得到不同的結(jié)果 第27頁第12講12.4.2 基于曲率

14、的外形描畫 1.曲率與幾何特征曲率與幾何特征曲率曲率幾何特征幾何特征連續(xù)零曲率直線段連續(xù)非零曲率圓弧段局部最大曲率絕對值（一般）角點局部最大曲率正值凸角點局部最大曲率負(fù)值凹角點曲率過零點拐點大曲率平均絕對值或平方值形狀復(fù)雜性，與彎曲能有關(guān)第28頁第12講12.4.2 基于曲率的外形描畫 2.離散曲率離散曲率給定一個離散點集合給定一個離散點集合 P=pii=0, , n，它定義了一條數(shù)字曲線，在點，它定義了一條數(shù)字曲線，在點 piP處的處的 k-階曲率階曲率 r k(pi) =1|cos |，其中，其中 = angle(pik, pi, pi+k)是兩個線段是兩個線段pi k, pi和和pi,

15、pi+k之間的夾角，而之間的夾角，而k i, , n i。 p0q10pp17p=7p13p103ikik第29頁第12講12.4.2 基于曲率的外形描畫 2.離散曲率離散曲率第30頁第12講12.4.2 基于曲率的外形描畫 3.離散曲率的計算離散曲率的計算(1)先對先對x(t)和和y(t)進(jìn)展插值再求導(dǎo)數(shù)進(jìn)展插值再求導(dǎo)數(shù)用有限差分的方法用有限差分的方法 ) 1( )( )() 1( )( )() 1()()( ) 1()()( nynynynxnxnxnynynynxnxnx2/322)( )( )( )()()( )(tytxtytxtytxtk第31頁第12講12.4.2 基于曲率的外形

16、描畫 3.離散曲率的計算離散曲率的計算(2)根據(jù)矢量間的夾角來定義等價的曲率根據(jù)矢量間的夾角來定義等價的曲率測度測度)()( , )()()()()( , )()()(inynyinxnxninynyinxnxniivu)( )()()()(nvnunvnunriiiii第32頁第12講12.4.2 基于曲率的外形描畫 4.基于曲率的描畫符基于曲率的描畫符(1)曲率的統(tǒng)計值：平均值，方差，曲率的統(tǒng)計值：平均值，方差，熵熵 (2)曲率最大、最小點，拐點曲率最大、最小點，拐點(3)彎曲能彎曲能將給定曲線彎曲成所需外形而需將給定曲線彎曲成所需外形而需求的能量求的能量設(shè)曲線長度為設(shè)曲線長度為L，在其上

17、一點，在其上一點k的的曲率為曲率為k(t) LttkBE12)(第33頁第12講12.5 拓?fù)錁?gòu)造描畫拓?fù)錁?gòu)造描畫 交叉數(shù)交叉數(shù)crossing number思索象素思索象素 p 的的8個鄰域象素個鄰域象素 qi (i = 0, , 7) S4(p)：在：在p的的8-鄰域中鄰域中4-連通組元的數(shù)目連通組元的數(shù)目 銜接數(shù)銜接數(shù)connectivity numberC8(p)：在：在p的的8-鄰域中鄰域中8-連通組元的數(shù)目連通組元的數(shù)目70170421)(iiiiiqqqpS3022122264208)()(iiiiiqqqqqqqqpC第34頁第12講12.5 拓?fù)錁?gòu)造描畫拓?fù)錁?gòu)造描畫 區(qū)分4-

18、連通組元 F 中的各個象素 p： (1)假設(shè) S4(p) = 0，那么 p 是一個孤立點即F = p(2)假設(shè) S4(p) = 1，那么 p 或者是一個邊境點或者是一個內(nèi)部點(3)假設(shè) S4(p) = 2，那么 p 對堅持F的4-連通是必不可少的一個點(4)假設(shè) S4(p) = 3，那么 p 是一個分叉點(5)假設(shè) S4(p) = 4，那么 p 是一個交叉點第35頁第12講12.5 拓?fù)錁?gòu)造描畫拓?fù)錁?gòu)造描畫 連通區(qū)域圖 拓?fù)錁?gòu)造圖 圖中的孔數(shù) H = 1 + |A| |V| V代表圖構(gòu)造中的結(jié)點集合A代表圖構(gòu)造中的結(jié)點銜接弧集合 10123411122222222222222211112103

19、411第36頁第12講12.6 分形維數(shù)分形維數(shù) 1.兩種維數(shù)定義兩種維數(shù)定義(1)拓?fù)渚S數(shù)拓?fù)渚S數(shù)topological dimension點在集合中位置的自在度的數(shù)目，記點在集合中位置的自在度的數(shù)目，記為為dT 點的點的dT是是0，曲線的，曲線的dT是是1，平面，平面的的dT是是2(2)Hausdorff 維數(shù)自類似維數(shù)維數(shù)自類似維數(shù)它被記為它被記為d，是實數(shù)，是實數(shù)在歐氏空間的集合中，總有在歐氏空間的集合中，總有d dT 不等式成立的為分形集合，不等式成立的為分形集合，d為分形為分形維數(shù)維數(shù)第37頁第12講12.6 分形維數(shù)分形維數(shù) 2.盒計數(shù)方法盒計數(shù)方法將圖象分成尺寸為將圖象分成尺寸為 L L的盒的盒對含有感興趣目的的盒進(jìn)展計數(shù)，記對含有感興趣目的的盒進(jìn)展計數(shù)，記為為N(L) 經(jīng)過改動經(jīng)過改動L，得到，得到logN(L)對對log(L)的的曲線曲線 分形維數(shù)是分形維數(shù)是曲