關于特征表示與描述第1頁，講稿共73頁，2023年5月2日，星期三第三節特征表示與描述3.3.1特征表示與描述的基本概念3.3.2表示法設計3.3.3邊界描述子3.3.4關系描述子第2頁，講稿共73頁，2023年5月2日，星期三3.3.1特征表示與描述的基本概念特征表示與描述的定義： 把圖像分割后，為了進一步的處理，分割后的圖像一般要進行形式化的表達和描述解決形式化表達問題一般有兩種選擇：1）根據區域的外部特征來進行形式化表示2）根據區域的內部特征（比較區域內部的象素值）來來進行形式化表示第3頁，講稿共73頁，2023年5月2日，星期三3.3.1特征表示與描述的基本概念外部特征來進行形式化表示舉例：

第4頁，講稿共73頁，2023年5月2日，星期三表達方式選擇

要使數據變得更有利于下一步的計算工作。下一步工作是基于所選的表達方式描述這個區域，一般情況下：1）如果關注的焦點是形狀特性，選擇外部表示方式2）如果關注的焦點是反射率特性，如顏色、紋理時，選擇內部表示方式3）所選表示方式，應該對尺寸、變換、旋轉等變量盡可能的不敏感第5頁，講稿共73頁，2023年5月2日，星期三表示法設計鏈碼多邊形逼近外形特征邊界分段區域骨架第6頁，講稿共73頁，2023年5月2日，星期三表示法設計鏈碼定義：1）鏈碼是一種邊界的編碼表示法。

2）用邊界的方向作為編碼依據。為簡化邊界的描述。一般描述的是邊界點集。0123014672354-鏈碼8-鏈碼第7頁，講稿共73頁，2023年5月2日，星期三鏈碼舉例：4-鏈碼：000033333322222211110011第8頁，講稿共73頁，2023年5月2日，星期三鏈碼算法：給每一個線段邊界一個方向編碼。有4-鏈碼和8-鏈碼兩種編碼方法。從起點開始，沿邊界編碼，至起點被重新碰到，結束一個對象的編碼。第9頁，講稿共73頁，2023年5月2日，星期三鏈碼問題1：1）鏈碼相當長。2）噪音會產生不必要的鏈碼。改進1：1）加大網格空間。2）依據原始邊界與結果的接近程度，來確定新點的位置。第10頁，講稿共73頁，2023年5月2日，星期三鏈碼舉例：4-鏈碼：003332221101第11頁，講稿共73頁，2023年5月2日，星期三鏈碼問題2：1）由于起點的不同，造成編碼的不同2）由于角度的不同，造成編碼的不同改進2：1）從固定位置作為起點(最左最上)開始編碼2）通過使用鏈碼的首差代替碼子本身的方式第12頁，講稿共73頁，2023年5月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=0第13頁，講稿共73頁，2023年5月2日，星期三

鏈碼應用背景：如果邊界的本身對于旋轉和比例修改來說是無變化的，使用鏈碼才是正確的。一般來說這是不可能的，實際應用時還需要改進。用鏈碼后，對象只要用1)起點坐標，2)周長（邊界點數）3)鏈碼，4)對象編號，就可以描述。鏈碼一般用于一幅圖像中有多個對象的情況，對單個對象不適用。第14頁，講稿共73頁，2023年5月2日，星期三多邊形逼近基本思想：用最少的多邊形線段，獲取邊界形狀的本質。尋找最小基本多邊形的方法一般有兩種：

1）點合成法

2）邊分裂法第15頁，講稿共73頁，2023年5月2日，星期三多邊形逼近點合成算法思想舉例：RR<T第16頁，講稿共73頁，2023年5月2日，星期三

多邊形逼近點合成算法：1）沿著邊界選兩個相鄰的點對，計算首尾連接直線段與原始折線段的誤差R。2）如果誤差R小于預先設置的閾值T。去掉中間點，選新點對與下一相鄰點對，重復1）；否則，存儲線段的參數，置誤差為0，選被存儲線段的終點為起點，重復1）2）。3）當程序的第一個起點被遇到，程序結束。RR<T第17頁，講稿共73頁，2023年5月2日，星期三多邊形逼近點合成算法的問題：

頂點一般不對應于邊界的拐點（如拐角）。因為新的線段直到超過誤差的閾值才開始。分裂法可用于緩解這個問題!第18頁，講稿共73頁，2023年5月2日，星期三多邊形逼近邊分裂算法思想舉例：

第19頁，講稿共73頁，2023年5月2日，星期三多邊形逼近分裂邊算法：（1）連接邊界線段的兩個端點（如果是封閉邊界，連接最遠點）；（2）如果最大正交距離大于閾值，將邊界分為兩段，最大值點定位一個頂點。重復（1）；（3）如果沒有超過閾值的正交距離，結束。第20頁，講稿共73頁，2023年5月2日，星期三外形特征基本思想：外形特征是一種用一維函數表達邊界的方法。基本思想是把邊界的表示降到一維函數第21頁，講稿共73頁，2023年5月2日，星期三外形特征函數定義——質心角函數：邊上的點到質心的距離r，作為夾角的的函數r()Arr()2A第22頁，講稿共73頁，2023年5月2日，星期三外形特征舉例：Arr()2A第23頁，講稿共73頁，2023年5月2日，星期三外形特征問題：函數過分依賴于旋轉和比例的變化改進：對于旋轉——兩種改進：a.選擇離質心最遠的點作為起點b.選擇從質心到主軸最遠的點作為起點對于比例變換：對函數進行正則化，使函數值總是分布在相同的值域里，比如說[0，1]第24頁，講稿共73頁，2023年5月2日，星期三邊界分段基本概念：一個任意集合S（區域）的凸起外緣H是：包含S的最小凸起的集合H-S的差的集合被稱為集合S的凸起補集DSSDS+D=H第25頁，講稿共73頁，2023年5月2日，星期三邊界分段分段算法：給進入和離開凸起補集D的變換點打標記來劃分邊界段。優點：不依賴于方向和比例的變化S第26頁，講稿共73頁，2023年5月2日，星期三邊界分段問題：噪音的影響，導致出現零碎的劃分。解決的方法：先平滑邊界，或用多邊形逼近邊界，然后再分段第27頁，講稿共73頁，2023年5月2日，星期三

區域骨架基本思想表示一個平面區域結構形狀的重要方法是把它削減成圖形。這種削減可以通過細化（也稱為抽骨架）算法，獲取區域的骨架來實現Blum的中軸變換方法（MAT）設:R是一個區域，B為R的邊界點，對于R中的點p，找p在B上“最近”的鄰居。如果p有多于一個的鄰居，稱它屬于R的中軸（骨架）第28頁，講稿共73頁，2023年5月2日，星期三pRB

Blum的中軸變換方法（MAT）設:R是一個區域

B為R的邊界點對于R中的點p，找p在B上“最近”的鄰居。如果p有多于一個的鄰居，稱它屬于R的中軸（骨架）第29頁，講稿共73頁，2023年5月2日，星期三區域骨架問題：計算量大第30頁，講稿共73頁，2023年5月2日，星期三

區域骨架算法改進在保證產生正確的骨架的同時，改進算法的效率。比較典型的是一類細化算法，它們不斷刪去邊緣，但保證刪除滿足：（1）不移去端點（2）不破壞連通性（3）不引起區域的過度腐蝕第31頁，講稿共73頁，2023年5月2日，星期三

區域骨架:一種細化二值區域的算法假設區域內的點值為1，背景值為0這個方法由對給定區域的邊界點連續進行兩個基本操作構成這里邊界點是指任何值為1且至少有一個8鄰域上的點為0的象素第32頁，講稿共73頁，2023年5月2日，星期三對于滿足以下四個條件的邊界點打標記準備刪除：(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）p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5區域骨架基本操作1第33頁，講稿共73頁，2023年5月2日，星期三舉例: N(p1)=4

S(p1)=3 p2*p4*p6=0 p4*p6*p8=0第2個條件沒滿足不打標記00p1110101p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5

區域骨架所有條件都滿足，才打刪除標記。刪除并不立即進行，而是等到對所有邊界點都打完標記后，再把作了標記的點一起刪除第34頁，講稿共73頁，2023年5月2日，星期三

區域骨架基本操作2條件(a)、(b)與操作1相同條件(c)、(d)改為：c’)

p2*p4*p8=0d’)

p2*p6*p8=0p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5第35頁，講稿共73頁，2023年5月2日，星期三

區域骨架細化算法細化算法的一輪操作包括：按操作1，給邊界點打標記——刪除點按操作2，給邊界點打標記——刪除點這個基本過程反復進行，直至沒有點可以刪除為止。此時算法終止。第36頁，講稿共73頁，2023年5月2日，星期三區域骨架例:

第37頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子邊界描述子簡單描述子形狀數傅立葉描述子矩量第38頁，講稿共73頁，2023年5月2日，星期三

簡單描述子邊界的周長：

是最簡單的描述符之一。沿輪廓線計算象素的個數，給出了一個長度的近似估計邊界的直徑：邊界B的直徑是：

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

D是歐氏距離或幾何距離，pi,pj是邊界上的點。直徑的長度和直徑的兩個端點連線（這條線被稱為邊界的主軸）的方向，是關于邊界的有用的描述符。第39頁，講稿共73頁，2023年5月2日，星期三簡單描述子邊界的直徑舉例第40頁，講稿共73頁，2023年5月2日，星期三

曲率被描述為斜率的變化率。近似：用相鄰邊界線段（描述為直線）的斜率差作為在邊界線交點處的曲率描述子。

交點a處的曲率為

dk=k1–k2

其中k1、k2為相鄰線段的斜率ak1k2簡單描述子邊界的曲率：第41頁，講稿共73頁，2023年5月2日，星期三

邊界的凸線段點： 當頂點p上的斜率是非負時，稱其為凸線段上的點P1P2簡單描述子

邊界的凹線段點： 當頂點p上的斜率為負時，稱其為凹線段上的點第42頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子形狀數——鏈碼的實用化形狀數定義：最小循環首差鏈碼。循環首差鏈碼：用相鄰鏈碼的差代替鏈碼例如：4-鏈碼10103322

循環首差為：33133030循環首差:1-2=-1(3) 0-1=-1(3) 1-0=1 0-1=-1(3) 3-0=3 3-3=0 2-3=-1(3) 2-2=0第43頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子形狀數形狀數定義：例如：4-鏈碼：10103322

循環首差：33133|030

形狀數：03033133形狀數序號n的定義： 形狀數中阿拉伯數字的個數。上例序數為8

對于封閉邊界序號一定是偶數。如order4、6、8。第44頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子形狀數序號為4、6、8的形狀數舉例：

序號4鏈碼：0321首差：3333形狀：3333序號6鏈碼：003221首差：303303形狀：033033序號8鏈碼：00032221首差：30033003形狀：00330033第45頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子形狀數序號為6的形狀數舉例：

序號6鏈碼：033211首差：330330形狀：033033序號6鏈碼：003221首差：303303形狀：033033形狀數與方向無關第46頁，講稿共73頁，2023年5月2日，星期三形狀數序號為8的形狀數舉例：

序號8鏈碼：03032211首差：33133030形狀：03033133序號8鏈碼：00332211首差：30303030形狀：03030303序號8鏈碼：00323211首差：30331330形狀：03033133第47頁，講稿共73頁，2023年5月2日，星期三形狀數問題： 雖然鏈碼的首差是不依賴于旋轉的，但一般情況下邊界的編碼依賴于網格的方向。改進： 規整化網格方向，具體方法如下：第48頁，講稿共73頁，2023年5月2日，星期三

形狀數幾個基本概念：邊界最大軸a:是連接距離最遠的兩個點的線段邊界最小軸b:與最大軸垂直，且其長度確定的包圍盒剛好包圍邊界。邊界離心率c：最大軸長度與最小軸長度的比

c=a/b基本矩形:包圍邊界的矩形。第49頁，講稿共73頁，2023年5月2日，星期三形狀數基本概念舉例邊界最大軸a邊界最小軸b基本矩形第50頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子形狀數規整化網格方向算法的思想： 大多數情況下，將鏈碼網格與基本矩形對齊，即可得到一個唯一的形狀數。 規整化網格方向的一種算法如下：（1）首先確定形狀數的序號n；（2）在序號為n的矩形形狀數中，找出一個與給定形狀的基本矩形的離心率最接近的形狀數第51頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子形狀數（3）然后再用這個矩形與基本矩形對齊，構造網格。（4）用獲得鏈碼的方法得到鏈碼；（5）再得到循環首差；（6）首差中的最小循環數即為形狀數。例如:如果n=12，所有序號為12的矩形（即周長為12）為2*4，3*3，1*5。如果2*4矩形的離心率最接近于給定邊界的基本矩形的離心率，我們建立一個2*4的網格。第52頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子形狀數規整化網格方向算法舉例：鏈碼：000033222121首差：300030300313形狀：0003030031330123第53頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子傅立葉描述子1）基本思想：（1）對于XY平面上的每個邊界點，將其坐標用復數表示為：

s(k)=x(k)+jy(k) k=0,1,…,N-1y0y1x0x1jyxx(k)=xky(k)=yk第54頁，講稿共73頁，2023年5月2日，星期三3.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=0系數a(u)被稱為邊界的傅立葉描述子第55頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子傅立葉描述子1）基本思想：（3）選取整數MN-1，進行逆傅立葉變換（重構）

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

u=0

這時，對應于邊界的點數沒有改變，但在重構每一個點所需要的計算項大大減少了。如果邊界點數很大，M一般選為2的指數次方的整數。第56頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子傅立葉描述符2）M的選取與描述符的關系

在上述方法中，相當于對于u>M-1的部分舍去不予計算。由于傅立葉變換中高頻部分對應于圖像的細節描述，因此M取得越小，細節部分丟失得越多。M=4M=61M=62N=64第57頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子傅立葉描述符3）使用價值1）較少的傅立葉描述子（如4個），就可以獲取邊界本質的整體輪廓2）這些帶有邊界信息的描述子，可以用來區分明顯不同的邊界第58頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子傅立葉描述符4）優點1）使用復數作為描述符，對于旋轉、平移、放縮等操作和起始點的選取不十分敏感。2）幾何變換的描述子可通過對函數作簡單變換來獲得幾何變換傅立葉描述子原形a(u)旋轉a(u)=a(u)ej平移a(u)=a(u)+xy(u)放縮a(u)=a(u)起點a(u)=a(u)e-j2k0u/N第59頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子矩量基本思想：將描述形狀的任務減少至描述一個一維函數，邊界段和特征的形狀可以用矩量來量化地描述矩量的定義：把邊界當作直方圖函數：g(r)rg(r)第60頁，講稿共73頁，2023年5月2日，星期三3.3.3特征表示與描述：邊界描述子矩量矩量的定義：

L

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

i=1L其中

m=∑rig(ri)

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

第62頁，講稿共73頁，2023年5月2日，星期三3.3.4特征表示與描述：關系描述子關系描述子基本思想階梯關系編碼骨架關系編碼方向關系編碼內角關系編碼樹結構關系編碼第63頁，講稿共73頁，2023年5月2日，星期三3.3.4特征表示與描述：關系描述子基本思想：通過挖掘各個成分之間的結構關系來描述邊界圖像中各個部分間的結構關系是二維的，而串是一維的，期望找到一種方法把二維關系轉化為一維的串主導思想是考慮物體各個部分的連接線段第64頁，講稿共73頁，2023年5月2日，星期三3.3.4特征表示與描述：關系描述子階梯關系編碼對于如下階梯形邊界，定義兩個基本元素a,babaaabbb第65頁，講稿共73頁，2023年5月2日，星期三3.3.4特征表示與描述：關系描述子階梯結構關系定義如下產生規則：

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

其中S、A是變