第8章 形狀描述

1、- -第8章形狀描述8.1 概述圖像分析和圖像合成中的一個(gè)重要的問(wèn)題就是形狀描述。用圖像分析技術(shù)獲得的形狀描述可以用于目標(biāo)識(shí)別。在圖形學(xué)中，通過(guò)目標(biāo)建模獲得的二維和三維形狀描述，可以用于數(shù)字圖像合成。下面討論幾種二維形狀描述方法，以及這些方法在圖像分析，計(jì)算機(jī)視覺(jué)和模式識(shí)別中的應(yīng)用。二維形狀可以用兩種不同的方式來(lái)描述。第一種方式是用目標(biāo)的邊界和邊界的特征來(lái)描述目標(biāo)形狀，如邊界長(zhǎng)度、曲率等。這種方法與邊緣和直線檢測(cè)有直接關(guān)系，得到的描述結(jié)果稱(chēng)為外部描述。外部形狀描述簡(jiǎn)潔，因而應(yīng)用廣泛。第二種方法是用目標(biāo)在圖像內(nèi)所覆蓋的區(qū)域描述形狀。這種方法來(lái)自區(qū)域分割，其描述結(jié)果稱(chēng)為內(nèi)部描述。一些圖像分割技術(shù)本

2、身就包含了目標(biāo)描述技術(shù)，如區(qū)域分裂法的四叉樹(shù)。一般地說(shuō)，形狀描述手段應(yīng)當(dāng)具有下面的性質(zhì)：1 單一性：對(duì)每個(gè)目標(biāo)具有一個(gè)專(zhuān)一的描述。2 完備性：可以描述所有的目標(biāo)。3 幾何變換不變性：幾何變換，如平移、旋轉(zhuǎn)、縮放和鏡像之后描述不變。4 靈敏性：能容易地反映相似目標(biāo)的差異。5 概括性：能從細(xì)節(jié)中抽取概括形狀的根本特征。8.2 鏈碼假設(shè)二值圖像中某一目標(biāo)的邊界用值為1的像素構(gòu)成的連通路徑包括四連通徑和八連通路徑來(lái)表示。這里路徑可以看成是由連接兩個(gè)相鄰像素線段組成，如圖8.1所示。每一條線段都有一個(gè)方向，當(dāng)沿著邊界順時(shí)針遍歷目標(biāo)邊界時(shí)，邊界鏈上的方向可以按照?qǐng)D8.2的方式編碼。這樣，邊界上相連線段的方

3、向碼便構(gòu)成一個(gè)鏈碼。如圖8.1所示的從路徑左上角開(kāi)場(chǎng)的四連通路徑鏈碼為011?？梢钥闯?，鏈碼的形式與起點(diǎn)的設(shè)置有關(guān)。因?yàn)槁窂绞情]合的，所以，由于起點(diǎn)設(shè)定不同而得到的不同鏈碼仍然表示同一形狀。為了滿(mǎn)足目標(biāo)識(shí)別時(shí)單一性的要求，可以循環(huán)移動(dòng)鏈碼，使由鏈碼構(gòu)成的整數(shù)數(shù)值最小，取這個(gè)最小整數(shù)為確定的鏈碼。用鏈碼表示邊界的優(yōu)點(diǎn)是具有平移不變性；縮放不變性，可以通過(guò)改變采樣?xùn)鸥竦拇笮?lái)實(shí)現(xiàn)；旋轉(zhuǎn)不變性可以用差分鏈碼來(lái)實(shí)現(xiàn)。設(shè)x1x2xN為鏈碼，d1d2dN為差分鏈碼，差分鏈碼di，可按下式計(jì)算：di= (8-1)其中差分diff(x,xi-1)是通過(guò)計(jì)算鏈碼xi相對(duì)于它的前點(diǎn)xi-1逆時(shí)針?lè)较蛐D(zhuǎn)90

4、76;或45°角度的次數(shù)得到的。因?yàn)檫吔缡欠忾]的，所以把最后一個(gè)像素xN看作第一個(gè)像素x1的前點(diǎn)。差分鏈碼代表方向差分，因而具有旋轉(zhuǎn)不變性，即旋轉(zhuǎn)/2角度的整數(shù)倍時(shí)具有旋轉(zhuǎn)不變性。在直角坐標(biāo)柵格中旋轉(zhuǎn)任意角度，會(huì)改變邊界的形狀，因此也改變了差分鏈碼。圖8.1 邊界的鏈碼表示圖8.2 邊緣鏈碼方向?qū)τ谒倪B通鏈碼，每個(gè)元素只需要2位存儲(chǔ)空間，而存儲(chǔ)邊界像素坐標(biāo)那么需要2字節(jié)空間，所以鏈碼可以做為邊緣描述的一種很好的壓縮方法。鏈碼還可以用于計(jì)算邊界的一些特征。因?yàn)樵谒倪B通路徑中，每節(jié)鏈碼線段的長(zhǎng)度為1，所以邊界的周長(zhǎng)P等于四鏈通碼的總長(zhǎng)度N。在八連通鏈碼中，偶數(shù)鏈碼的長(zhǎng)度為1，奇數(shù)鏈碼的長(zhǎng)

5、度為，其邊界的周長(zhǎng)為： P= 8-2其中ni= 8-3目標(biāo)的寬度和高度h同樣可以用鏈碼計(jì)算。在四連通鏈碼中，鏈碼為0(或者2)的線段相加為目標(biāo)的寬度,鏈碼為1或者3的線段相加為目標(biāo)的高度。因此可以得到求寬、高的公式：=(8-4)h=(8-5)其中i= 8-6hi= 8-7同理，對(duì)于八連通鏈碼：0,1,7或者3,4,5對(duì)寬度的奉獻(xiàn)都是1；1，2，3或者5，6，7對(duì)高度的奉獻(xiàn)都是1。所以目標(biāo)的寬度和高度為：i= 8-8hi= 8-9利用鏈碼還可以完成很多與目標(biāo)形狀有關(guān)的計(jì)算用甲蟲(chóng)算法很容易跟蹤二值目標(biāo)的邊界。這種算法用于四連通鄰域。甲蟲(chóng)從一個(gè)邊界點(diǎn)出發(fā)，如果當(dāng)前點(diǎn)值為1，就向左前進(jìn)一個(gè)像素；如果當(dāng)

6、前點(diǎn)的值為0，就向右轉(zhuǎn)并前進(jìn)一個(gè)像素；當(dāng)甲蟲(chóng)轉(zhuǎn)回起點(diǎn)時(shí)，算法終止。這個(gè)過(guò)程的圖示見(jiàn)圖8.3。在邊界跟蹤過(guò)程中出現(xiàn)了一些小循環(huán)，這些小循環(huán)可以在優(yōu)化處理中除去。圖8.3二值目標(biāo)邊界跟蹤的甲蟲(chóng)算法8.3 多邊形近似在一些應(yīng)用中，數(shù)字圖像邊界提供的信息具有一定的冗余度，這時(shí)可以考慮用近似方法描述邊界。最常用的方法是逐段線性近似，即多邊形近似方法。這種方法用一個(gè)與原邊界曲線相近的多邊形來(lái)表示邊界。為了獲得滿(mǎn)意的近似效果，可采用某種誤差指標(biāo)來(lái)衡量多邊形與原曲線的近似程度。假設(shè)從A點(diǎn)到B點(diǎn)的數(shù)字曲線用直線AB來(lái)近似，如圖8.4所示。令x1,x2，xN為數(shù)字曲線上像素的坐標(biāo)，x1di, i = 2,，N1,

7、為從xi(i = 2, N1),點(diǎn)出發(fā)與直線AB(即矢量xN x1)垂直的矢量：xi diTxN x1= 0 (8-10)距離| xi di |表示直線與曲線上的點(diǎn)xi, i = 2,，N1的誤差。近似度標(biāo)準(zhǔn)可以用均方誤差E2或最大誤差Emax表示：E2=(8-11)Emax=| xi di | (8-12)圖8.4 用直線近似曲線的誤差定義用多邊形近似曲線時(shí)，也可以使用同樣的近似標(biāo)準(zhǔn)。為了使多邊形近似到達(dá)最優(yōu)，在選擇多邊形頂點(diǎn)時(shí)應(yīng)使總體誤差最小。利用迭代搜索方法可以解決這個(gè)問(wèn)題，但是計(jì)算復(fù)雜性較高。我們介紹一種分裂和合并算法。這種算法在大多數(shù)情況下的運(yùn)算效率都比較高。該算法將一段曲線遞歸地截

8、斷成小的曲線段，并用直線來(lái)近似它們，直到滿(mǎn)足近似標(biāo)準(zhǔn)為止。均方誤差與最大誤差準(zhǔn)那么在這里都可以使用。近似過(guò)程如圖8.5所示。曲線x1到xN要用多邊形來(lái)近似，假設(shè)使用最大誤差標(biāo)準(zhǔn)，可以看出y2點(diǎn)的誤差最大，于是用直線x1y2和y2，xN來(lái)近似x1xN，重復(fù)這個(gè)過(guò)程，直到所有的線段的Emax小于某一閾值為止。圖8.5 多項(xiàng)式近似的分裂算法近似多邊形的頂點(diǎn)數(shù)目在很大程度上取決于誤差閾值。如果誤差閾值小，那么需要大量的直線段。如果曲線是閉合的，起點(diǎn)x1和終點(diǎn)xN要選擇曲線上相對(duì)兩側(cè)上的點(diǎn)，如圖8.6所示。這兩個(gè)點(diǎn)將曲線分為兩段。算法可對(duì)這兩局局部別進(jìn)展。分裂算法的優(yōu)點(diǎn)是可以找到曲線的轉(zhuǎn)折點(diǎn)，并用這些轉(zhuǎn)

9、折點(diǎn)來(lái)描述曲線。合并算法用相反的方式進(jìn)展多邊形近似。我們從曲線的一點(diǎn)x1出發(fā)，沿順時(shí)針?lè)较蚧蚰鏁r(shí)針?lè)较虮闅v曲線。對(duì)于每一點(diǎn)xi，檢測(cè)x1到xi的誤差，如果超過(guò)某一閾值，就將xi作為多邊形頂點(diǎn)并以xi為起點(diǎn)，重復(fù)上述過(guò)程。如果曲線是閉合的，那么選擇曲線上外凸的轉(zhuǎn)折點(diǎn)作為x1。圖8.6 封閉邊界的多邊形近似分裂方法8.4 紋理描述紋理是圖像的一個(gè)重要特征，在區(qū)域分割中有廣泛的應(yīng)用。盡管如此，關(guān)于圖像的紋理至今尚沒(méi)有一個(gè)統(tǒng)一而明確的定義。通常認(rèn)為紋理是圖像的粗糙、光滑和規(guī)那么的程度。紋理描述技術(shù)可以分成三大類(lèi)：統(tǒng)計(jì)方法、譜方法和構(gòu)造方法。統(tǒng)計(jì)方法描述紋理是根據(jù)區(qū)域的直方圖、直方圖外延和矩，主要用于描

10、述圖像的反差、顆粒度和粗糙度。譜分析技術(shù)，是用區(qū)域自相關(guān)函數(shù)或傅立葉變換域的能量分布來(lái)檢測(cè)紋理的周期。構(gòu)造方法是用模式基元和特定的排列規(guī)那么來(lái)描述紋理。8.4.1基于直方圖的分析最簡(jiǎn)單的紋理描述是基于圖像直方圖pf(f)的。令fk,k=1,2，N為不同的圖像灰度級(jí)。 1.均值：=(8-33)2.方差：2=(9-34)3扭曲度:3=(8-35)假設(shè)某一圖像區(qū)域的直方圖，那么，均值給出了該圖像區(qū)域的平均灰度水平的估計(jì)值；方差2那么說(shuō)明區(qū)域灰度的彌散程度；扭曲度反映直方圖的對(duì)稱(chēng)性，它表示了在平均灰度值兩側(cè)的像素的百分比。這類(lèi)紋理描述方法的最大優(yōu)點(diǎn)是計(jì)算簡(jiǎn)單。8.4.2差分直方圖分析上述紋理描述方法的

11、最大缺點(diǎn)是不能表達(dá)紋理的空間域特征?？臻g信息可以用灰度差分直方圖表達(dá)。d=(d1，d2)為兩個(gè)像素之間的位移矢量，g(d)是位移量為d的灰度差分：g(d)=|f(k,l)f(k+d1, l+d2)| (8-38)我們用pg(g,d)表示位移量為d的灰度差分直方圖。每個(gè)位移值d,都對(duì)應(yīng)一個(gè)直方圖pg(g,d),pg(g,d)反映了圖像灰度的空間組織信息。如果圖像的紋理較粗，那么對(duì)于較小的位移值d,直方圖pg(g,d)集中在g=0附近；如果圖像的紋理較細(xì)，即使對(duì)于剛剛超過(guò)紋理粒度的小位移矢量d，直方圖pg(g,d)也趨于發(fā)散。圖8.7兩幅具有不同紋理的的圖像圖8.8 突出水平方向紋理的差分結(jié)果圖8

12、.9突出垂直方向紋理的差分結(jié)果從灰度差分直方圖中可以獲得幾種紋理描述量：1.均值：d=(8-39)均值較小，說(shuō)明粗糙的紋理具有等于或者大于位移矢量d幅值的粒度。如果位移矢量用極坐標(biāo)表示，即d=(r,)，那么均值能夠給出圖像紋理的方向信息。2.方差和反差：d=(8-40)Cd=(8-41)方差是對(duì)特定位移d的灰度差分彌散程度的度量，確定紋理的方差d通常較小。反差Cd是灰度差分比照度的度量。3.熵：Hd=(8-42)熵反映直方圖Pg(g,d)的一致性，對(duì)于均勻分布的直方圖，熵有最大值。灰度差分直方圖不僅計(jì)算簡(jiǎn)單，而且能夠反映紋理的空間組織情況。 8.4.3 游程長(zhǎng)度分析游程長(zhǎng)度統(tǒng)計(jì)量出是一種提醒紋

13、理空間性質(zhì)的方法。游程長(zhǎng)度是指連續(xù)、共線，并且具有一樣灰度或同一灰度段的像素的數(shù)目。長(zhǎng)度為l個(gè)像素，具有一樣灰度f(wàn),方向?yàn)榻堑氖录?，記為l,f,。游程長(zhǎng)度即反映紋理的粗糙程度，也反映紋理的方向性。具有方向性的紋理在某一角度會(huì)具有較長(zhǎng)的游程。同理，粗糙的紋理趨于具有較長(zhǎng)的游程。令Nl,f,表示大小為N1×N2像素的圖像中游程l,f,的數(shù)目，NR為最大游程長(zhǎng)度，雙重和式TR為游程總數(shù)：TR=(8-43)比值Nl,f,/TR表示灰度游程在方向上的直方圖。根據(jù)灰度游程能得到以下紋理信息：1.短游程優(yōu)勢(shì)：A1=(8-44)A1為圖像中短游程的度量；2.長(zhǎng)游程優(yōu)勢(shì)：A2=(8-45)A2為圖像中

14、長(zhǎng)游程的度量；3.灰度分布：A3=(8-46)表示在方向上灰度為fk的各長(zhǎng)度游程的總數(shù)。顯然，A3是游程灰度分布的一種度量。4.游程長(zhǎng)度分布：A4=(8-47)表示在方向上長(zhǎng)度為l的各灰度游程總數(shù)。顯然，A4是游程長(zhǎng)度分布的一種度量。5.游程百分率：A5=(8-48)8.5 形狀特征在某些應(yīng)用中，幾何形狀特征，如周長(zhǎng)、面積等，為識(shí)別過(guò)程提供了重要的信息。幾何形狀特征可以作為目標(biāo)的一種描述。幾何形狀特征可以用較少的特征矢量表達(dá)，所以能夠?qū)崿F(xiàn)較顯著的數(shù)據(jù)壓縮。前面討論的用邊界鏈碼計(jì)算的目標(biāo)周長(zhǎng)，寬度和高度都可以做為形狀特征。形狀特征可以分成兩大類(lèi)：邊界特征和區(qū)域特征。下面介紹幾種邊界特征和區(qū)域特征

15、，以及它們的計(jì)算方法。1.周長(zhǎng)可以根據(jù)邊緣跟蹤的結(jié)果定義周長(zhǎng)。如果x1,xN是邊緣坐標(biāo)表，那么：T= (8-51)對(duì)于四連通邊界，di=1；對(duì)于八連通邊界di=1或di=。2.角在邊界上線段s曲率幅度值k(s)很大或者為無(wú)窮大的位置稱(chēng)為角。這里，曲率定義為： 8-54是邊界上線段s的切線角度變化，ds是弧微分。根據(jù)8-54式的定義，方向鏈碼的局部曲率kn可近似取為：8-55其中： 8-56公式8-55中引用了前面介紹的鏈碼x1x2xN。鏈碼元素的取值范圍是0，1，m-1。對(duì)于八連通鏈碼m=8。8-55式的分子表示局部方向的切向變化，分母表示點(diǎn)n附近的曲線長(zhǎng)度。標(biāo)準(zhǔn)圓的曲率為1/R，R為半徑。3

16、.彎曲能彎曲能也是與曲率相關(guān)的目標(biāo)邊界特征，其定義為： 8-57T為目標(biāo)邊界周長(zhǎng)。結(jié)合(8-57)式和(8-55)式，可以得出目標(biāo)邊界方向鏈碼x1xn的彎曲能為： 8-58在所有周長(zhǎng)為T(mén)的形狀中，圓的彎曲能最小： 8-60由公式8-58可以看出，彎曲能與周長(zhǎng)有關(guān)，因此，應(yīng)對(duì)彎曲能作歸一化處理，使其取值范圍在0,1之內(nèi)： 8-614.面積目標(biāo)的面積是一個(gè)與區(qū)域有關(guān)的特征，其定義為 (8-62)其中R是目標(biāo)區(qū)域。式8-62中的面積微分單元dxdy代表一個(gè)目標(biāo)像素。因此在數(shù)字圖像中，可以通過(guò)計(jì)算像素的個(gè)數(shù)求面積。連通成分標(biāo)記時(shí)要逐一掃描目標(biāo)像素，所以可以用連通成分標(biāo)記算法來(lái)求面積。5.密質(zhì)度/圓度形狀的復(fù)雜性可以用密質(zhì)度或者圓度來(lái)說(shuō)明。密質(zhì)度/圓度的定義為： (8-64)其中T和A分別是目標(biāo)的周長(zhǎng)和面積。圓的密質(zhì)度最小。所有其它形狀的密質(zhì)度值都大于圓。正方形的密質(zhì)度為：。密質(zhì)度的歸一化形式是： (8-65)圓的歸一化密質(zhì)度等于0，復(fù)雜形狀的歸一化密質(zhì)度趨向于1。6. 直徑目標(biāo)的直徑定義為：