形狀分析方法綜述

摘要:形狀分析是圖像分析領域研究的重點內容之一。回顧了近幾十年來形狀分析領域的發展狀況，從基于區域和基于邊界的角度對當前的各種形狀分析方法進行分類，討論了各種典型的形狀描述算法思想，并列舉了在這些算法思想基礎上發展而來的各種形狀描述方法的改進及延伸。總結了各種算法的優缺點，并對該領域的研究發展進行了展望和探討。

關鍵詞:形狀分析;形狀描述;矩;傅立葉描述子;鏈碼

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2009)32-9047-03

A Survey on Shape Analysis Methods

YOU Hong-xia

(Nantong Textile Vocational Technology College， Nantong 226007， China)

Abstract: Shape analysis is an important part of image analysis field. The development of shape analysis methods in recent years was reviewed in this paper. The methods of shape analysis were classified and some typical algorithms in this field were discussed as well as their advantages and disadvantages. At last， the tendency of this direction was also discussed.

Key words: shape analysis; shape depict; moment; Fourier descriptors; chain code

形狀是物體的重要特征之一，形狀分析是圖像分析領域的重點研究內容之一。盡管形狀的識別對于人類視覺系統來說是件非常容易的事情，但是對于計算機視覺系統來說，卻是個非常大的挑戰。在工程、生物、天文地理、醫學、考古等眾多領域都有對物體形狀分析和識別的需求，因此人們早就開始研究用計算機來進行物體形狀分析和識別。

形狀分析是從圖像中提取形狀的特征信息，存儲于特定的數據結構中，并用于比較、識別、分類、檢索等操作的過程。它是一個涉及到多個學科分支的問題，需要綜合運用圖像處理，模式識別，人工智能等領域中的知識和方法。

近幾十年來人們已經提出了很多形狀分析的方法，這些方法呈現多樣化的特點，其中的一些方法也趨于成熟，應用領域不斷地延伸。但目前普遍認為比較滿意的使用方法還比較有限，通用性都或多或少地受到了一定地限制，很難說哪一種方法更加適合人們的需要。下面對各種典型形狀分析方法進行綜述，并分析各種方法的優缺點。

1 形狀分析方法的分類

形狀分析的主要步驟包括了形狀特征提取，形狀特征描述和形狀分類識別三個部分，本文主要討論形狀特征描述方法部分，這也是形狀分析的主要步驟。圖像形狀的描述方法可以分為基于內部參數(區域)和基于外部參數(邊界)的兩大類。基于區域的形狀描述方法主要有:矩方法、形態學方法、骨架法、形狀分解法、凸包法等;基于邊界的形狀描述方法主要有:鏈碼、多邊形逼近法、邊界分解法、傅立葉描述子、形狀簽名法、隨機過程法等。下面對一些典型的形狀描述方法進行分類介紹。

1.1 基于區域的形狀分析方法

1.1.1 不變矩方法

1962年Hu[1]提出了圖像識別的不變矩理論，為圖像識別建立了一種統計特征提取方法。區域的矩方法把一個歸一化的灰度圖像函數理解為一個2維隨機變量的概率密度，這個隨機變量的屬性用統計特征，即矩來描述。在二維笛卡爾空間中，密度函數f(x，y)的p+q階矩定義為:

低階矩p+q≤2代表分布函數的幾何特征，三階矩和高階矩p+q≥3表示函數在x軸y軸上的投影特性。Hu等人根據不變幾何理論，利用低階矩和三階矩的廣義線性組合而計算得的7個不變矩，公式如下:

不變矩是圖像的一種統計特征，可以用它來對形狀特征進行描述，它滿足平移、旋轉和尺度不變性，在圖像分析領域得到了廣泛應用。在Hu之后，又有多位研究人員對圖像分析的矩方法進行了改進，使該方法的應用得到了延伸和完善。

1.1.2 正交矩方法

1980年Teague等人提出了正交矩理論，之后Legendr多項式、Zernike多項式等陸續應用于矩分析法中。其中Zernike矩方法[2]對于形狀區域描述具有相對更好的綜合性能。Zernike矩形式為:

其中:

由于Zernike優良和穩定的性能，MPEG-7標準已經將基于Zernike矩思想的方法采納作為標準的形狀區域描述子[3]。除此以外，近年來仍不斷有基于矩的形狀分析新方法被提出。總體而言，正交矩的方法冗余少，還原原形狀精確，數學形式簡潔，整體性能穩定，是較為理想的形狀描述方法之一。缺點在于各個矩分量往往很難與形狀的具體視覺特征相關聯，此外，噪音干擾對高階矩的結果影響相對較大。

1.1.3 骨架算法

骨架法最早由Blum[4]提出，也稱中軸變換法。利用骨架表示原始圖像，可以在保持圖像重要拓撲特征的前提下，減少圖像中的冗余信息。骨架的形成可以用下面的例子來解釋:在圖像的內部填滿可燃物質，在t=0時刻，從形狀邊界的各點同時點火，火焰以相同的速度向形狀中心蔓延，在某點上兩股不同方向的火勢將會相遇，在相遇點處火焰將會熄滅，火焰熄滅處所有點的集合就構成了骨架。如果x為骨架上的點，t為火焰從點燃到x點處熄滅所經歷的時間，則可以構造一個t與x之間的關系函數，稱為熄滅函數，通過骨架和熄滅函數可重建圖像。用骨架法得到的骨架來描述對象形狀，比較直觀，但是也有一定的缺陷:該方法對噪聲比較敏感，邊界上小的擾動會引起骨架結構的較大變化。為解決噪聲問題，Blum和Nagel又提出了一種改進的中軸變換法，增強了算法的抗噪聲能力。

1.1.4 數學形態學方法

數學形態學是一類常用的圖像處理方法，可作為工具從圖像中提取對于表達和描述區域形狀有用的圖像分量，如邊界、骨架等。在圖像處理中最有效的兩種形態學基本操作是腐蝕和膨脹。大多數其它更復雜的操作都由這兩種派生而來。另外形態學開操作和閉操作也是具有十分強大的功能。

基于形態學原理的形狀描述方法很多，P.Maragos等人提出了模式譜的概念。Loui等人使用基于形態學協方差的方法，取得了具有旋轉和平移不變性的形狀描述方法。S.Loncaric提出了一種稱為形態學簽名變換的方法使用多尺度的形態學處理方式，將多尺度圖像處理技術和形態學方法的優點相結合，將復雜的形狀分解為一系列的簡單簽名圖像。

1.2 基于邊界的形狀分析方法

1.2.1 鏈碼方法

鏈碼可以用來描述物體的邊界線條，鏈碼方法就是跟蹤一條曲線或一個二維形狀邊界，將其路徑矢量化成標準方向的線段再進行編碼的方法，最早由Freeman[5]提出，典型的鏈碼有四方向鏈碼和八方向鏈碼。在八方向鏈碼中，鏈碼沿著數字曲線或邊界像素以八鄰接的方式移動并進行編碼，最終形成一個由起始點的坐標和一個方向編碼序列表示的鏈碼。鏈碼能夠以較少的數據來存儲較多的信息，因此得到了廣泛的應用。

鏈碼方法中，鏈碼起始點坐標的確定是一個比較復雜的計算過程。對于同一個邊界采用不同的邊界點作為鏈碼的起點，將得到不同的鏈碼。另外，噪聲的干擾會導致邊界變化，從而使鏈碼發生變化。研究者們陸續針對此問題對鏈碼方法做了各種改進。彭鐵根[6]等人將鏈碼轉化為頻域表示，并結合目標邊界曲線特征，較好地解決了鏈碼起始坐標的計算問題和噪聲干擾問題。

1.2.2 傅立葉描述子

傅立葉描述子是物體形狀邊界的傅立葉變換系數，它是物體邊界信號頻域分析的結果。傅立葉描述子方法的基本思想是:假定物體的形狀是一條封閉的曲線，沿邊界曲線上的一個點開始跟蹤邊界，把邊界上各點的位置坐標(x，y)看成是一個復數x+iy，從而得到一個復數序列，這個復數序列的離散傅立葉變換就是描述該物體形狀的傅里葉描述符。在一般情況下，傅立葉描述符的高頻成分反映邊界的不規則性細節，低頻成分反映整體形狀。傅立葉描述子方法具有易于計算、容易歸一化、匹配簡單、易獲得全局和局部特征等許多優點。對傅里葉描述符作歸一化運算，可以使它同物體所在圖像中的位置、大小和方向無關。通過實驗比較各種典型形狀識別方法的能力，表明基于物體輪廓坐標序列的傅立葉描述子具有極佳的形狀識別能力。

1.2.3 形狀簽名法

形狀簽名本質上是將二維邊界轉換為一個一維的實函數或復數函數，然后對該函數進行一些諸如傅立葉變換、小波變換等的數學變換，從而來描述形狀的方法[3]。具體實現該思想的方法有多種，Zahn等使用切線角弧長比作為一維表示函數。Bennet和McDonald通過連接邊界上的點與質心的半徑，以及初始點的半徑的夾角正切值對弧長的函數來表示二維邊界，但是這種方法對噪聲異常敏感，因為噪聲將直接影響到角度正切值的計算。S.Wang[7]提出使用形狀的質心到邊界上特征點之間的距離作為一維函數的函數值。雖然各種方法實現過程不同，但是其主要思想都是將二維邊界轉換為一維來解決形狀的描述問題。

1.2.4 多邊形逼近法

多邊形逼近法是指用一系列線段的封閉集合來逼近物體的形狀邊界曲線。如果多邊形的線段數與邊界上的點數相等，即每對相鄰點定義多邊形的一個邊，則多邊形可以完全準確的表達邊界。實際應用中多邊形表達的目的就是要用盡量少的線段來代表本邊界并保持邊界的基本形狀。一般以最小多邊形周長、最大內接多邊形面積、最小外界多邊形面積、最小誤差等作為近似準則。常用的多邊形描述方法有:基于收縮的最小周長多邊形法、基于聚合的最小均方差線段逼近法、基于分裂的最小均方誤差線段逼近法。

目前，已有多個基于多邊形逼近法思想的形狀分析方法。T.Pavlids提出了一種分裂-合并的多邊形逼近算法，這是目前最為常見的多邊形逼近法。Bengtsson提出一種層次型多邊形表示方法。Chung[8]等人提出了一種基于神經網絡的形狀多邊形逼近法。多邊形逼近法的抗干擾性能比鏈碼方法好，表達所需的數據量小。其缺點是存在對多邊形近似精度的選擇的問題，精度過高，得到的多邊形會因為邊數過多而顯得復雜;精度過低，抗噪聲能力增強，但是容易丟失邊界的細節信息。

2 各種方法比較

各類形狀分析方法解決問題的出發點都不盡相同，也存在各自的優缺點。基于邊界的方法只利用圖像的邊界信息，提取的有效信息量較小，運算比較便捷，適合處理較為簡單的形狀圖像，但算法自身的抗噪聲能力較弱，當邊界受到噪聲的干擾，將會引起算法較大的誤差。在處理特別復雜的形狀如:形狀本身不連通、有內孔或形狀內部包含復雜而豐富的結構時，就不能取得很好的效果。基于區域信息的方法充分利用形狀從邊緣到內部的所有信息，因此這類方法對形狀的描述能力更具魯棒性，性能比較穩定，但信息量較大，需要的存儲空間相對較大，算法復雜度相對較高。

3 總結

討論了近幾十年來形狀分析領域的一些方法。每種形狀分析方法都各有其優勢和適合使用的場合，但是每一種方法都無法勝任所有情況下對形狀描述的需要。一些形狀描述方法非常適合某一領域內的應用，但是換一應用領域，性能就會變差。因為所處理的圖形對象有著各種不同的特性，不同的領域對形狀描述的特征屬性值的要求也各有差異。對于形狀分析，無論從算法的簡單性、通用性、魯棒性，還是對新方法的多樣性需求上，都對研究人員有著更高的要求，需要今后深入細致地做進一步的探討和研究。

參考文獻:

[1] Hu M K. Visual Pattern recognition by Moment Invariants[J].IRE Transactions Information Theory，1962，8(2):179-187.

[2] A.Khotanzad， Y.H.Hong.Invariant image recognition in zernike moments[J].IEEE Trans on Pattern analysis and machine intelligence，1990，12(5):250-261.

[3] 陳運文.形狀識別與圖像分割方法研究[D].上海:復旦大學，2008.

[4] Blum H. A transformation for extracting new descriptors of shape[M].In Whater-dunn，editor，Models for the perception of speech and Visual forms.MIT Press. 1967:362-380.

[5] Freeman H. On the encoding of arbitrary geometric configuration[J].IEEE Transactions on Electric Computers，1961，10(2):260-268.

[6] 彭鐵根，吳惕華.基于邊界鏈碼的幅度譜圖像識別研究[J].計算機仿真，2004，21(8):149-151.

[7] Wang S， Chen P， Lin W. Invariant pattern recognition by moment Fourier descriptor[J]. Pattern Recognition，1994(27):1735-1742.

[8] Chung P， Tsai C， Chen E. et al. Polygonal approximation using a competitive Hopfield neural network[J].Pattern Recognition，1994(27):1505-1512.