數字圖像處理北京大學計算機研究所陳曉鷗數字圖像處理北京大學計算機研究所陳曉鷗第三節表示與描述3.3.1表示與描述的基本概念3.3.2表示法設計3.3.3邊界描述子3.3.4關系描述子第三節表示與描述3.3.1表示與描述的基本概念3.3.1表示與描述的基本概念基本概念在用前一章的方法，把圖像分割后，為了進一步的處理，分割后的圖像一般要進行形式化的表達和描述解決形式化表達問題一般有兩種選擇：1）根據區域的外部特征來進行形式化表示2）根據區域的內部特征（比較區域內部的象素值）來來進行形式化表示3.3.1表示與描述的基本概念基本概念3.3.1表示與描述的基本概念基本概念選擇表達方式，要本著使數據變得更有利于下一步的計算工作。下一步工作是基于所選的表達方式描述這個區域，一般情況下：1）如果關注的焦點是形狀特性，選擇外部表示方式2）如果關注的焦點是反射率特性，如顏色、文理時，選擇內部表示方式。3）所選表示方式，應該對尺寸、變換、旋轉等變量盡可能的不敏感3.3.1表示與描述的基本概念基本概念3.3.2表示與描述:表示法設計表示法設計鏈碼多邊形逼近外形特征邊界分段區域骨架3.3.2表示與描述:表示法設計表示法設計3.3.2表示與描述:表示法設計鏈碼定義：1）鏈碼是一種邊界的編碼表示法。

2）用邊界的方向作為編碼依據。為簡化邊界的描述。一般描述的是邊界點集。0123014672354-鏈碼8-鏈碼3.3.2表示與描述:表示法設計鏈碼012301467233.3.2表示與描述:表示法設計鏈碼算法：給每一個線段一個方向編碼。有4-鏈碼和8-鏈碼兩種編碼方法。從起點開始，沿邊界編碼，至起點被重新碰到，結束一個對象的編碼。3.3.2表示與描述:表示法設計鏈碼3.3.2表示與描述:表示法設計鏈碼舉例：4-鏈碼：0000333333222222111100113.3.2表示與描述:表示法設計鏈碼舉例：4-鏈碼：0003.3.2表示與描述:表示法設計鏈碼問題1：1）鏈碼相當長。2）噪音會產生不必要的鏈碼。改進1：1）加大網格空間。2）依據原始邊界與結果的接近程度，來確定新點的位置。3.3.2表示與描述:表示法設計鏈碼3.3.2表示與描述:表示法設計鏈碼舉例：4-鏈碼：0033322211013.3.2表示與描述:表示法設計鏈碼舉例：4-鏈碼：0033.3.2表示與描述:表示法設計鏈碼問題2：1）由于起點的不同，造成編碼的不同2）由于角度的不同，造成編碼的不同改進2：1）從固定位置作為起點(最左最上)開始編碼2）通過使用鏈碼的首差代替碼子本身的方式3.3.2表示與描述:表示法設計鏈碼3.3.2表示與描述:表示法設計鏈碼循環首差鏈碼：用相鄰鏈碼的差代替鏈碼例如：4-鏈碼10103322循環首差為：33133030循環首差：1-2=-1(3) 3-0=3

0-1=-1(3) 3-3=0 1-0=1 2-3=-1(3) 0-1=-1(3) 2-2=03.3.2表示與描述:表示法設計鏈碼3.3.2表示與描述:表示法設計鏈碼應用背景：如果邊界的本身對于旋轉和比例修改來說是無變化的，使用鏈碼才是正確的。一般來說這是不可能的，實際應用時還需要改進。用鏈碼后，對象只要用1)起點坐標，2)周長（邊界點數）3)鏈碼，4)對象編號，就可以描述。鏈碼一般用于一幅圖像中有多個對象的情況，對單個對象不適用。3.3.2表示與描述:表示法設計鏈碼3.3.2表示與描述:表示法設計多邊形逼近基本思想：用最少的多邊形線段，獲取邊界形狀的本質。尋找最小基本多邊形的方法一般有兩種：點合成法和邊分裂法3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計多邊形逼近點合成算法思想舉例：3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計多邊形逼近合成點算法：1）沿著邊界選兩個相鄰的點對，計算首尾連接直線段與原始折線段的誤差。2）如果誤差小于預先設置的閾值。去掉中間點，選新點對與下一相鄰點對，重復1）；否則，存儲線段的參數，置誤差為0，選被存儲線段的終點為起點，重復1）2）。3）當程序的第一個起點被遇到，程序結束。3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計多邊形逼近合成點算法的問題：

頂點一般不對應于邊界的拐點（如拐角）。因為新的線段直到超過誤差的閾值才開始。下面講到的分裂法可用于緩解這個問題3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計多邊形逼近邊分裂算法思想舉例：

3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計多邊形逼近分裂邊算法：（1）連接邊界線段的兩個端點（如果是封閉邊界，連接最遠點）；（2）如果最大正交距離大于閾值，將邊界分為兩段，最大值點定位一個頂點。重復（1）；（3）如果沒有超過閾值的正交距離，結束。3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計外形特征基本思想：外形特征是一種用一維函數表達邊界的方法。基本思想是把邊界的表示降到一維函數3.3.2表示與描述:表示法設計外形特征3.3.2表示與描述:表示法設計外形特征函數定義——質心角函數：邊上的點到質心的距離r，作為夾角的的函數。Arr()2A3.3.2表示與描述:表示法設計外形特征Arr()23.3.2表示與描述:表示法設計外形特征舉例：Arr()2A3.3.2表示與描述:表示法設計外形特征Arr()23.3.2表示與描述:表示法設計外形特征問題：函數過分依賴于旋轉和比例的變化改進：對于旋轉——兩種改進：a.選擇離質心最遠的點作為起點b.選擇從質心到主軸最遠的點作為起點對于比例變換：對函數進行正則化，使函數值總是分布在相同的值域里，比如說[0，1]3.3.2表示與描述:表示法設計外形特征3.3.2表示與描述:表示法設計邊界分段基本概念：一個任意集合S（區域）的凸起外緣H是：包含S的最小凸起的集合H-S的差的集合被稱為集合S的凸起補集DSSDS+D=H3.3.2表示與描述:表示法設計邊界分段SSDS+D3.3.2表示與描述:表示法設計邊界分段分段算法：給進入和離開凸起補集的變換點打標記來劃分邊界段。優點：不依賴于方向和比例的變化S3.3.2表示與描述:表示法設計邊界分段S3.3.2表示與描述:表示法設計邊界分段問題：噪音的影響，導致出現零碎的劃分。解決的方法：先平滑邊界，或用多邊形逼近邊界，然后再分段3.3.2表示與描述:表示法設計邊界分段3.3.2表示與描述:表示法設計區域骨架基本思想表示一個平面區域結構形狀的重要方法是把它削減成圖形。這種削減可以通過細化（也稱為抽骨架）算法，獲取區域的骨架來實現Blum的中軸變換方法（MAT）設:R是一個區域，B為R的邊界點，對于R中的點p，找p在B上“最近”的鄰居。如果p有多于一個的鄰居，稱它屬于R的中軸（骨架）3.3.2表示與描述:表示法設計區域骨架3.3.2表示與描述:表示法設計區域骨架基本思想問題：計算量大pRB3.3.2表示與描述:表示法設計區域骨架pRB3.3.2表示與描述:表示法設計區域骨架算法改進思想在保證產生正確的骨架的同時，改進算法的效率。比較典型的是一類細化算法，它們不斷刪去邊緣，但保證刪除滿足：（1）不移去端點（2）不破壞連通性（3）不引起區域的過度腐蝕3.3.2表示與描述:表示法設計區域骨架3.3.2表示與描述:表示法設計區域骨架一種細化二值區域的算法假設區域內的點值為1，背景值為0這個方法由對給定區域的邊界點連續進行兩個基本操作構成這里邊界點是指任何值為1且至少有一個8鄰域上的點為0的象素3.3.2表示與描述:表示法設計區域骨架3.3.2表示與描述:表示法設計區域骨架基本操作1對于滿足以下四個條件的邊界點打標記準備刪除：(a)2N(p1)6其中N(p1)是點p1的鄰域中1的個數，即： N(p1)=p2+p3+…+p9(b) S(p1)=1

其中S(p1)是按p2,p3,…,p9順序，0-1轉換的個數(c) p2*p4*p6=0（p2、p4、p6至少有一個0）(d) p4*p6*p8=0（p4、p6、p8至少有一個0）p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p53.3.2表示與描述:表示法設計區域骨架p9p2p1p8p3.3.2表示與描述:表示法設計區域骨架所有條件都滿足，才打刪除標記。刪除并不立即進行，而是等到對所有邊界點都打完標記后，再把作了標記的點一起刪除。舉例: N(p1)=4 S(p1)=3 p2*p4*p6=0 p4*p6*p8=0第2個條件沒滿足不打標記00p1110101p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p53.3.2表示與描述:表示法設計區域骨架00p1110103.3.2表示與描述:表示法設計區域骨架基本操作2條件(a)、(b)與操作1相同條件(c)、(d)改為：c’)

p2*p4*p8=0d’)

p2*p6*p8=0p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p53.3.2表示與描述:表示法設計區域骨架p9p2p1p8p3.3.2表示與描述:表示法設計區域骨架細化算法細化算法的一輪操作包括：按操作1，給邊界點打標記——刪除點按操作2，給邊界點打標記——刪除點這個基本過程反復進行，直至沒有點可以刪除為止。此時算法終止。3.3.2表示與描述:表示法設計區域骨架3.3.2表示與描述:表示法設計區域骨架算法分析：1）條件a)的分析：當輪廓點p1的8鄰域上有1個或7個值為1的點時，不滿足條件a。 有1個點說明：p1是骨架上的終點，顯然不能刪除有7個點說明：如果刪除p1會引起區域的腐蝕2）條件b)的分析：當p1在寬度為1的筆劃上時，不滿足條件b。因而該條件保證了骨架的連續性。3.3.2表示與描述:表示法設計區域骨架3.3.2表示與描述:表示法設計區域骨架算法分析：

（3）當(p4=0orp6=0)or(p2=0andp8=0)時，條件c,d同時滿足。滿足這個條件的點可能是右邊、下邊、左上角的邊界點。任何一種情況下，p1都不是骨架的一部分，應被刪除。當(p4=0andp6=0)or(p2=0orp8=0)時，條件c’,d’同時滿足。滿足這個條件的點可能是左邊、上邊、右下角的邊界點，應被刪除。p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p53.3.2表示與描述:表示法設計區域骨架p9p2p1p8p3.3.2表示與描述:表示法設計區域骨架例:

3.3.2表示與描述:表示法設計區域骨架3.3.3表示與描述：邊界描述子邊界描述子簡單描述子形狀數傅立葉描述子矩量3.3.3表示與描述：邊界描述子邊界描述子3.3.3表示與描述：邊界描述子簡單描述子邊界的周長：是最簡單的描述符之一。沿輪廓線計算象素的個數，給出了一個長度的近似估計邊界的直徑：邊界B的直徑是：

Diam(B)=max[D(pi,pj)]

D是歐氏距離或幾何距離，pi,pj是邊界上的點。直徑的長度和直徑的兩個端點連線（這條線被稱為邊界的主軸）的方向，是關于邊界的有用的描述符。3.3.3表示與描述：邊界描述子簡單描述子3.3.3表示與描述：邊界描述子簡單描述子邊界的直徑舉例3.3.3表示與描述：邊界描述子簡單描述子3.3.3表示與描述：邊界描述子簡單描述子邊界的曲率： 曲率被描述為斜率的變化率。近似：用相鄰邊界線段（描述為直線）的斜率差作為在邊界線交點處的曲率描述子。

交點a處的曲率為

dk=k1–k2

其中k1、k2為相鄰線段的斜率ak1k23.3.3表示與描述：邊界描述子簡單描述子ak1k23.3.3表示與描述：邊界描述子簡單描述子邊界的凸線段點： 當頂點p上的斜率是非負時，稱其為凸線段上的點邊界的凹線段點： 當頂點p上的斜率為負時，稱其為凹線段上的點3.3.3表示與描述：邊界描述子簡單描述子3.3.3表示與描述：邊界描述子簡單描述子邊界的凸線段點P1：邊界的凹線段點P2：P1P23.3.3表示與描述：邊界描述子簡單描述子P1P23.3.3表示與描述：邊界描述子形狀數形狀數定義：最小循環首差鏈碼。循環首差鏈碼：用相鄰鏈碼的差代替鏈碼例如：4-鏈碼10103322循環首差為：33133030循環首差:1-2=-1(3) 3-0=3 0-1=-1(3) 3-3=0 1-0=1 2-3=-1(3) 0-1=-1(3) 2-2=03.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數形狀數定義：例如：4-鏈碼：10103322

循環首差：33133|030

形狀數：03033133形狀數序號n的定義： 形狀數中阿拉伯數字的個數，對于封閉邊界序號是偶數。如order4、6、8。3.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數形狀數例如：

序號4鏈碼：0321首差：3333形狀：3333序號6鏈碼：003221首差：303303形狀：033033序號8鏈碼：00032221首差：30033003形狀：003300333.3.3表示與描述：邊界描述子形狀數序號4鏈碼：03213.3.3表示與描述：邊界描述子形狀數形狀數例如：

序號6鏈碼：033211首差：330330形狀：033033序號6鏈碼：003221首差：303303形狀：0330333.3.3表示與描述：邊界描述子形狀數序號6鏈碼：03323.3.3表示與描述：邊界描述子形狀數問題： 雖然鏈碼的首差是不依賴于旋轉的，但一般情況下邊界的編碼依賴于網格的方向。改進： 規整化網格方向，具體方法如下：3.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數幾個基本概念：邊界最大軸a:是連接距離最遠的兩個點的線段邊界最小軸b:與最大軸垂直，且其長度確定的包圍盒剛好包圍邊界。邊界離心率c：最大軸長度與最小軸長度的比

c=a/b基本矩形:包圍邊界的矩形。3.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數基本概念舉例邊界最大軸a邊界最小軸b基本矩形3.3.3表示與描述：邊界描述子形狀數邊界最大軸a邊界最小3.3.3表示與描述：邊界描述子形狀數規整化網格方向算法的思想： 大多數情況下，將鏈碼網格與基本矩形對齊，即可得到一個唯一的形狀數。對一個給定的形狀序號，處理步驟如下：（1）我們找出一個序號為n的矩形，它的離心率最接近于給定形狀的基本矩形的離心率。3.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數（2）然后再用這個矩形構造網格。例如:如果n=12，所有序號為12的矩形（即周長為12）為2*4，3*3，1*5。如果2*4矩形的離心率最接近于給定邊界的基本矩形的離心率，我們建立一個2*4的網格。（3）再得到鏈碼。（4）最后，再得到循環首差。（5）首差中的最小循環數即為形狀數。3.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數規整化網格方向算法舉例：鏈碼：000033222121首差：300030300313形狀：00030300313301233.3.3表示與描述：邊界描述子形狀數鏈碼：00003323.3.3表示與描述：邊界描述子傅立葉描述子1）基本思想：（1）對于XY平面上的每個邊界點，將其坐標用復數表示為：

s(k)=x(k)+jy(k) k=0,1,…,N-1y0y1x0x1jyxx(k)=xky(k)=yk3.3.3表示與描述：邊界描述子傅立葉描述子y0y1x0x3.3.3表示與描述：邊界描述子傅立葉描述子1）基本思想：（2）進行離散傅立葉變換

N-1a(u)=1/N∑s(k)exp(-j2uk/N)u=0,1,…,N-1

u=0

N-1s(k)=∑a(u)exp(j2uk/N) k=0,1,…,N-1

u=0a(u)被稱為邊界的傅立葉描述子3.3.3表示與描述：邊界描述子傅立葉描述子3.3.3表示與描述：邊界描述子傅立葉描述子1）基本思想：（3）選取整數MN-1，進行逆傅立葉變換（重構）

M-1s’(k)=∑a(u)exp(j2uk/N) k=0,1,…,N-1

u=0

這時，對應于邊界的點數沒有改變，但在重構每一個點所需要的計算項大大減少了。如果邊界點數很大，M一般選為2的指數次方的整數。3.3.3表示與描述：邊界描述子傅立葉描述子3.3.3表示與描述：邊界描述子傅立葉描述符2）M的選取與描述符的關系

在上述方法中，相當于對于u>M-1的部分舍去不予計算。由于傅立葉變換中高頻部分對應于圖像的細節描述，因此M取得越小，細節部分丟失得越多。3.3.3表示與描述：邊界描述子傅立葉描述符3.3.3表示與描述：邊界描述子傅立葉描述符3）優點1）使用復數作為描述符，對于旋轉、平移、放縮等操作和起始點的選取不十分敏感。2）以上幾何變換均可以通過對描述子函數作簡單變換來獲得。3.3.3表示與描述：邊界描述子傅立葉描述符3.3.3表示與描述：邊界描述子矩量基本思想：將描述形狀的任務減少至描述一個一維函數，邊界段和特征的形狀可以用矩量來量化地描述矩量的定義：把邊界當作直方圖函數：g(r)rg(r)3.3.3表示與描述：邊界描述子矩量rg(r)3.3.3表示與描述：邊界描述子矩量矩量的定義：

L

n(r)=∑(ri-m)ng(ri)

i=1L其中

m=∑rig(ri)

i=1這里L是邊界上點的數目,n(r)是邊界的矩量3.3.3表示與描述：邊界描述子矩量3.3.3表示與描述：邊界描述子矩量矩量的優點：實現是直接的附帶了一種關于邊界形狀的“物理”解釋對于旋轉的不敏感性為了使大小比例不敏感，可以通過伸縮r的范圍來將大小正則化。

3.3.3表示與描述：邊界描述子矩量3.3.3表示與描述：關系描述子關系描述子基本思想階梯關系編碼骨架關系編碼方向關系編碼內角關系編碼樹結構關系編碼3.3.3表示與描述：關系描述子關系描述子3.3.3表示與描述：關系描述子基本思想：通過挖掘各個成分之間的結構關系來描述邊界圖像中各個部分間的結構關系是二維的，而串是一維的，期望找到一種方法把二維關系轉化為一維的串主導思想是考慮物體各個部分的連接線段3.3.3表示與描述：關系描述子基本思想：3.3.4表示與描述：關系描述子階梯關系編碼對于如下階梯形邊界，定義兩個基本元素a,babaaabbb3.3.4表示與描述：關系描述子階梯關系編碼abaaabb3.3.4表示與描述：關系描述子階梯結構關系定義如下產生規則：

(1)S->aA (2)A->bS (3)A->b

其中S、A是變量舉例：(1,3)(1,2,1,3)(1,2,12,1,3)aaabbbaabbab3.3.4表示與描述：關系描述子階梯結構關系(1,3)(13.3.4表示與描述：關系描述子骨架關系編碼用有向線段來描述一個圖像的各個部分（例如同構區域），這個線段是通過頭尾連接等方法得到的。線段之間的不同運算代表了區域的不同組合。當圖像的連通性可以通過首尾相接或其它連續的方式描述的時候，最適于使用這種串來描述。3.3.4表示與描述：關系描述子骨架關系編碼3.3.4表示與描述：關系描述子骨架關系編碼a+ba-ba×ba*baaaabbbb編碼3.3.4表示與描述：關系描述子骨架關系編碼a+ba3.3.4表示與描述：關系描述子方向關系編碼跟蹤對象的邊界，將跟蹤得到的線段按照方向或長度來編碼a1a2a5a7a8a3a4a6a1a8a7a6a5a4a3a23.3.4表示與描述：關系描述子方向關系編碼a1a2a5a3.3.4表示與描述：關系描述子內角關系編碼根據角度范圍不同，編碼為8個符號即:a1:0-45;a2:45-90;a3:90-135;…;

a8:315-360舉例：a3a3a3a3a3a3a3a3a2a2a3a33.3.4表示與描述：關系描述子內角關系編碼a3a3a3a3.3.4表示與描述：關系描述子樹結構關系樹結構中每個結點的意義和結點之間的關系最為重要舉例：abcd$abcdefef$3.3.4表示與描述：關系描述子樹結構關系abcd$abc請提問請提問數字圖像處理北京大學計算機研究所陳曉鷗數字圖像處理北京大學計算機研究所陳曉鷗第三節表示與描述3.3.1表示與描述的基本概念3.3.2表示法設計3.3.3邊界描述子3.3.4關系描述子第三節表示與描述3.3.1表示與描述的基本概念3.3.1表示與描述的基本概念基本概念在用前一章的方法，把圖像分割后，為了進一步的處理，分割后的圖像一般要進行形式化的表達和描述解決形式化表達問題一般有兩種選擇：1）根據區域的外部特征來進行形式化表示2）根據區域的內部特征（比較區域內部的象素值）來來進行形式化表示3.3.1表示與描述的基本概念基本概念3.3.1表示與描述的基本概念基本概念選擇表達方式，要本著使數據變得更有利于下一步的計算工作。下一步工作是基于所選的表達方式描述這個區域，一般情況下：1）如果關注的焦點是形狀特性，選擇外部表示方式2）如果關注的焦點是反射率特性，如顏色、文理時，選擇內部表示方式。3）所選表示方式，應該對尺寸、變換、旋轉等變量盡可能的不敏感3.3.1表示與描述的基本概念基本概念3.3.2表示與描述:表示法設計表示法設計鏈碼多邊形逼近外形特征邊界分段區域骨架3.3.2表示與描述:表示法設計表示法設計3.3.2表示與描述:表示法設計鏈碼定義：1）鏈碼是一種邊界的編碼表示法。

2）用邊界的方向作為編碼依據。為簡化邊界的描述。一般描述的是邊界點集。0123014672354-鏈碼8-鏈碼3.3.2表示與描述:表示法設計鏈碼012301467233.3.2表示與描述:表示法設計鏈碼算法：給每一個線段一個方向編碼。有4-鏈碼和8-鏈碼兩種編碼方法。從起點開始，沿邊界編碼，至起點被重新碰到，結束一個對象的編碼。3.3.2表示與描述:表示法設計鏈碼3.3.2表示與描述:表示法設計鏈碼舉例：4-鏈碼：0000333333222222111100113.3.2表示與描述:表示法設計鏈碼舉例：4-鏈碼：0003.3.2表示與描述:表示法設計鏈碼問題1：1）鏈碼相當長。2）噪音會產生不必要的鏈碼。改進1：1）加大網格空間。2）依據原始邊界與結果的接近程度，來確定新點的位置。3.3.2表示與描述:表示法設計鏈碼3.3.2表示與描述:表示法設計鏈碼舉例：4-鏈碼：0033322211013.3.2表示與描述:表示法設計鏈碼舉例：4-鏈碼：0033.3.2表示與描述:表示法設計鏈碼問題2：1）由于起點的不同，造成編碼的不同2）由于角度的不同，造成編碼的不同改進2：1）從固定位置作為起點(最左最上)開始編碼2）通過使用鏈碼的首差代替碼子本身的方式3.3.2表示與描述:表示法設計鏈碼3.3.2表示與描述:表示法設計鏈碼循環首差鏈碼：用相鄰鏈碼的差代替鏈碼例如：4-鏈碼10103322循環首差為：33133030循環首差：1-2=-1(3) 3-0=3

0-1=-1(3) 3-3=0 1-0=1 2-3=-1(3) 0-1=-1(3) 2-2=03.3.2表示與描述:表示法設計鏈碼3.3.2表示與描述:表示法設計鏈碼應用背景：如果邊界的本身對于旋轉和比例修改來說是無變化的，使用鏈碼才是正確的。一般來說這是不可能的，實際應用時還需要改進。用鏈碼后，對象只要用1)起點坐標，2)周長（邊界點數）3)鏈碼，4)對象編號，就可以描述。鏈碼一般用于一幅圖像中有多個對象的情況，對單個對象不適用。3.3.2表示與描述:表示法設計鏈碼3.3.2表示與描述:表示法設計多邊形逼近基本思想：用最少的多邊形線段，獲取邊界形狀的本質。尋找最小基本多邊形的方法一般有兩種：點合成法和邊分裂法3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計多邊形逼近點合成算法思想舉例：3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計多邊形逼近合成點算法：1）沿著邊界選兩個相鄰的點對，計算首尾連接直線段與原始折線段的誤差。2）如果誤差小于預先設置的閾值。去掉中間點，選新點對與下一相鄰點對，重復1）；否則，存儲線段的參數，置誤差為0，選被存儲線段的終點為起點，重復1）2）。3）當程序的第一個起點被遇到，程序結束。3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計多邊形逼近合成點算法的問題：

頂點一般不對應于邊界的拐點（如拐角）。因為新的線段直到超過誤差的閾值才開始。下面講到的分裂法可用于緩解這個問題3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計多邊形逼近邊分裂算法思想舉例：

3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計多邊形逼近分裂邊算法：（1）連接邊界線段的兩個端點（如果是封閉邊界，連接最遠點）；（2）如果最大正交距離大于閾值，將邊界分為兩段，最大值點定位一個頂點。重復（1）；（3）如果沒有超過閾值的正交距離，結束。3.3.2表示與描述:表示法設計多邊形逼近3.3.2表示與描述:表示法設計外形特征基本思想：外形特征是一種用一維函數表達邊界的方法?；舅枷胧前堰吔绲谋硎窘档揭痪S函數3.3.2表示與描述:表示法設計外形特征3.3.2表示與描述:表示法設計外形特征函數定義——質心角函數：邊上的點到質心的距離r，作為夾角的的函數。Arr()2A3.3.2表示與描述:表示法設計外形特征Arr()23.3.2表示與描述:表示法設計外形特征舉例：Arr()2A3.3.2表示與描述:表示法設計外形特征Arr()23.3.2表示與描述:表示法設計外形特征問題：函數過分依賴于旋轉和比例的變化改進：對于旋轉——兩種改進：a.選擇離質心最遠的點作為起點b.選擇從質心到主軸最遠的點作為起點對于比例變換：對函數進行正則化，使函數值總是分布在相同的值域里，比如說[0，1]3.3.2表示與描述:表示法設計外形特征3.3.2表示與描述:表示法設計邊界分段基本概念：一個任意集合S（區域）的凸起外緣H是：包含S的最小凸起的集合H-S的差的集合被稱為集合S的凸起補集DSSDS+D=H3.3.2表示與描述:表示法設計邊界分段SSDS+D3.3.2表示與描述:表示法設計邊界分段分段算法：給進入和離開凸起補集的變換點打標記來劃分邊界段。優點：不依賴于方向和比例的變化S3.3.2表示與描述:表示法設計邊界分段S3.3.2表示與描述:表示法設計邊界分段問題：噪音的影響，導致出現零碎的劃分。解決的方法：先平滑邊界，或用多邊形逼近邊界，然后再分段3.3.2表示與描述:表示法設計邊界分段3.3.2表示與描述:表示法設計區域骨架基本思想表示一個平面區域結構形狀的重要方法是把它削減成圖形。這種削減可以通過細化（也稱為抽骨架）算法，獲取區域的骨架來實現Blum的中軸變換方法（MAT）設:R是一個區域，B為R的邊界點，對于R中的點p，找p在B上“最近”的鄰居。如果p有多于一個的鄰居，稱它屬于R的中軸（骨架）3.3.2表示與描述:表示法設計區域骨架3.3.2表示與描述:表示法設計區域骨架基本思想問題：計算量大pRB3.3.2表示與描述:表示法設計區域骨架pRB3.3.2表示與描述:表示法設計區域骨架算法改進思想在保證產生正確的骨架的同時，改進算法的效率。比較典型的是一類細化算法，它們不斷刪去邊緣，但保證刪除滿足：（1）不移去端點（2）不破壞連通性（3）不引起區域的過度腐蝕3.3.2表示與描述:表示法設計區域骨架3.3.2表示與描述:表示法設計區域骨架一種細化二值區域的算法假設區域內的點值為1，背景值為0這個方法由對給定區域的邊界點連續進行兩個基本操作構成這里邊界點是指任何值為1且至少有一個8鄰域上的點為0的象素3.3.2表示與描述:表示法設計區域骨架3.3.2表示與描述:表示法設計區域骨架基本操作1對于滿足以下四個條件的邊界點打標記準備刪除：(a)2N(p1)6其中N(p1)是點p1的鄰域中1的個數，即： N(p1)=p2+p3+…+p9(b) S(p1)=1

其中S(p1)是按p2,p3,…,p9順序，0-1轉換的個數(c) p2*p4*p6=0（p2、p4、p6至少有一個0）(d) p4*p6*p8=0（p4、p6、p8至少有一個0）p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p53.3.2表示與描述:表示法設計區域骨架p9p2p1p8p3.3.2表示與描述:表示法設計區域骨架所有條件都滿足，才打刪除標記。刪除并不立即進行，而是等到對所有邊界點都打完標記后，再把作了標記的點一起刪除。舉例: N(p1)=4 S(p1)=3 p2*p4*p6=0 p4*p6*p8=0第2個條件沒滿足不打標記00p1110101p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p53.3.2表示與描述:表示法設計區域骨架00p1110103.3.2表示與描述:表示法設計區域骨架基本操作2條件(a)、(b)與操作1相同條件(c)、(d)改為：c’)

p2*p4*p8=0d’)

p2*p6*p8=0p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p53.3.2表示與描述:表示法設計區域骨架p9p2p1p8p3.3.2表示與描述:表示法設計區域骨架細化算法細化算法的一輪操作包括：按操作1，給邊界點打標記——刪除點按操作2，給邊界點打標記——刪除點這個基本過程反復進行，直至沒有點可以刪除為止。此時算法終止。3.3.2表示與描述:表示法設計區域骨架3.3.2表示與描述:表示法設計區域骨架算法分析：1）條件a)的分析：當輪廓點p1的8鄰域上有1個或7個值為1的點時，不滿足條件a。 有1個點說明：p1是骨架上的終點，顯然不能刪除有7個點說明：如果刪除p1會引起區域的腐蝕2）條件b)的分析：當p1在寬度為1的筆劃上時，不滿足條件b。因而該條件保證了骨架的連續性。3.3.2表示與描述:表示法設計區域骨架3.3.2表示與描述:表示法設計區域骨架算法分析：

（3）當(p4=0orp6=0)or(p2=0andp8=0)時，條件c,d同時滿足。滿足這個條件的點可能是右邊、下邊、左上角的邊界點。任何一種情況下，p1都不是骨架的一部分，應被刪除。當(p4=0andp6=0)or(p2=0orp8=0)時，條件c’,d’同時滿足。滿足這個條件的點可能是左邊、上邊、右下角的邊界點，應被刪除。p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p53.3.2表示與描述:表示法設計區域骨架p9p2p1p8p3.3.2表示與描述:表示法設計區域骨架例:

3.3.2表示與描述:表示法設計區域骨架3.3.3表示與描述：邊界描述子邊界描述子簡單描述子形狀數傅立葉描述子矩量3.3.3表示與描述：邊界描述子邊界描述子3.3.3表示與描述：邊界描述子簡單描述子邊界的周長：是最簡單的描述符之一。沿輪廓線計算象素的個數，給出了一個長度的近似估計邊界的直徑：邊界B的直徑是：

Diam(B)=max[D(pi,pj)]

D是歐氏距離或幾何距離，pi,pj是邊界上的點。直徑的長度和直徑的兩個端點連線（這條線被稱為邊界的主軸）的方向，是關于邊界的有用的描述符。3.3.3表示與描述：邊界描述子簡單描述子3.3.3表示與描述：邊界描述子簡單描述子邊界的直徑舉例3.3.3表示與描述：邊界描述子簡單描述子3.3.3表示與描述：邊界描述子簡單描述子邊界的曲率： 曲率被描述為斜率的變化率。近似：用相鄰邊界線段（描述為直線）的斜率差作為在邊界線交點處的曲率描述子。

交點a處的曲率為

dk=k1–k2

其中k1、k2為相鄰線段的斜率ak1k23.3.3表示與描述：邊界描述子簡單描述子ak1k23.3.3表示與描述：邊界描述子簡單描述子邊界的凸線段點： 當頂點p上的斜率是非負時，稱其為凸線段上的點邊界的凹線段點： 當頂點p上的斜率為負時，稱其為凹線段上的點3.3.3表示與描述：邊界描述子簡單描述子3.3.3表示與描述：邊界描述子簡單描述子邊界的凸線段點P1：邊界的凹線段點P2：P1P23.3.3表示與描述：邊界描述子簡單描述子P1P23.3.3表示與描述：邊界描述子形狀數形狀數定義：最小循環首差鏈碼。循環首差鏈碼：用相鄰鏈碼的差代替鏈碼例如：4-鏈碼10103322循環首差為：33133030循環首差:1-2=-1(3) 3-0=3 0-1=-1(3) 3-3=0 1-0=1 2-3=-1(3) 0-1=-1(3) 2-2=03.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數形狀數定義：例如：4-鏈碼：10103322

循環首差：33133|030

形狀數：03033133形狀數序號n的定義： 形狀數中阿拉伯數字的個數，對于封閉邊界序號是偶數。如order4、6、8。3.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數形狀數例如：

序號4鏈碼：0321首差：3333形狀：3333序號6鏈碼：003221首差：303303形狀：033033序號8鏈碼：00032221首差：30033003形狀：003300333.3.3表示與描述：邊界描述子形狀數序號4鏈碼：03213.3.3表示與描述：邊界描述子形狀數形狀數例如：

序號6鏈碼：033211首差：330330形狀：033033序號6鏈碼：003221首差：303303形狀：0330333.3.3表示與描述：邊界描述子形狀數序號6鏈碼：03323.3.3表示與描述：邊界描述子形狀數問題： 雖然鏈碼的首差是不依賴于旋轉的，但一般情況下邊界的編碼依賴于網格的方向。改進： 規整化網格方向，具體方法如下：3.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數幾個基本概念：邊界最大軸a:是連接距離最遠的兩個點的線段邊界最小軸b:與最大軸垂直，且其長度確定的包圍盒剛好包圍邊界。邊界離心率c：最大軸長度與最小軸長度的比

c=a/b基本矩形:包圍邊界的矩形。3.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數基本概念舉例邊界最大軸a邊界最小軸b基本矩形3.3.3表示與描述：邊界描述子形狀數邊界最大軸a邊界最小3.3.3表示與描述：邊界描述子形狀數規整化網格方向算法的思想： 大多數情況下，將鏈碼網格與基本矩形對齊，即可得到一個唯一的形狀數。對一個給定的形狀序號，處理步驟如下：（1）我們找出一個序號為n的矩形，它的離心率最接近于給定形狀的基本矩形的離心率。3.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數（2）然后再用這個矩形構造網格。例如:如果n=12，所有序號為12的矩形（即周長為12）為2*4，3*3，1*5。如果2*4矩形的離心率最接近于給定邊界的基本矩形的離心率，我們建立一個2*4的網格。（3）再得到鏈碼。（4）最后，再得到循環首差。（5）首差中的最小循環數即為形狀數。3.3.3表示與描述：邊界描述子形狀數3.3.3表示與描述：邊界描述子形狀數規整化網格方向算法舉例：鏈碼：000033222121首差：300030300313形狀：00030300313301233.3.3表示與描述：邊界描述子形狀數鏈碼：00003323.3.3表示與描述：邊界描述子傅立葉描述子1）基本思想：（1）對于XY平面上的每個邊界點，將其坐標用復數表示為：

s(k)=x(k)+jy(k) k=0,1,…,N-1y0y1x0x1jyxx(k)=xky(k)=yk3.3.3表示與描述：邊界描述子傅立葉描述子y0y1x0x3.3.3表示與描述：邊界描述子傅立葉描述子1）基本思想：（2）進行離散傅立葉變換

N-1a(u)=1/N∑s(k)exp(-j2uk/N)u=0,1,…,N-1

u=0

N-1s(k)=∑a(u)exp(j2uk/N) k=0,1,…,N-1

u=0a(u)被稱為邊界的傅立葉描述子3.3.3表示與描述：邊界描述子傅立葉描述子3.3.3表示與描述：邊界描述子傅立葉描述子1）