第8章 形狀描述

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

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

3、向碼便構成一個鏈碼。如圖8.1所示的從路徑左上角開場的四連通路徑鏈碼為011?？梢钥闯?，鏈碼的形式與起點的設置有關。因為路徑是閉合的，所以，由于起點設定不同而得到的不同鏈碼仍然表示同一形狀。為了滿足目標識別時單一性的要求，可以循環(huán)移動鏈碼，使由鏈碼構成的整數數值最小，取這個最小整數為確定的鏈碼。用鏈碼表示邊界的優(yōu)點是具有平移不變性；縮放不變性，可以通過改變采樣柵格的大小來實現；旋轉不變性可以用差分鏈碼來實現。設x1x2xN為鏈碼，d1d2dN為差分鏈碼，差分鏈碼di，可按下式計算：di= (8-1)其中差分diff(x,xi-1)是通過計算鏈碼xi相對于它的前點xi-1逆時針方向旋轉90

4、76;或45°角度的次數得到的。因為邊界是封閉的，所以把最后一個像素xN看作第一個像素x1的前點。差分鏈碼代表方向差分，因而具有旋轉不變性，即旋轉/2角度的整數倍時具有旋轉不變性。在直角坐標柵格中旋轉任意角度，會改變邊界的形狀，因此也改變了差分鏈碼。圖8.1 邊界的鏈碼表示圖8.2 邊緣鏈碼方向對于四連通鏈碼，每個元素只需要2位存儲空間，而存儲邊界像素坐標那么需要2字節(jié)空間，所以鏈碼可以做為邊緣描述的一種很好的壓縮方法。鏈碼還可以用于計算邊界的一些特征。因為在四連通路徑中，每節(jié)鏈碼線段的長度為1，所以邊界的周長P等于四鏈通碼的總長度N。在八連通鏈碼中，偶數鏈碼的長度為1，奇數鏈碼的長

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

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

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

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

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

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

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

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

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

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

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

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