特征表示與描述

特征表示與描述第一頁，共七十頁，編輯于2023年，星期日第三節(jié)特征表示與描述3.3.1特征表示與描述的基本概念3.3.2表示法設(shè)計3.3.3邊界描述子3.3.4關(guān)系描述子第二頁，共七十頁，編輯于2023年，星期日3.3.1特征表示與描述的基本概念特征表示與描述的定義： 把圖像分割后，為了進一步的處理，分割后的圖像一般要進行形式化的表達和描述解決形式化表達問題一般有兩種選擇：1）根據(jù)區(qū)域的外部特征來進行形式化表示2）根據(jù)區(qū)域的內(nèi)部特征（比較區(qū)域內(nèi)部的象素值）來來進行形式化表示第三頁，共七十頁，編輯于2023年，星期日3.3.1特征表示與描述的基本概念外部特征來進行形式化表示舉例：

第四頁，共七十頁，編輯于2023年，星期日表達方式選擇

要使數(shù)據(jù)變得更有利于下一步的計算工作。下一步工作是基于所選的表達方式描述這個區(qū)域，一般情況下：1）如果關(guān)注的焦點是形狀特性，選擇外部表示方式2）如果關(guān)注的焦點是反射率特性，如顏色、紋理時，選擇內(nèi)部表示方式3）所選表示方式，應(yīng)該對尺寸、變換、旋轉(zhuǎn)等變量盡可能的不敏感第五頁，共七十頁，編輯于2023年，星期日表示法設(shè)計鏈碼多邊形逼近外形特征邊界分段區(qū)域骨架第六頁，共七十頁，編輯于2023年，星期日表示法設(shè)計鏈碼定義：1）鏈碼是一種邊界的編碼表示法。

2）用邊界的方向作為編碼依據(jù)。為簡化邊界的描述。一般描述的是邊界點集。0123014672354-鏈碼8-鏈碼第七頁，共七十頁，編輯于2023年，星期日鏈碼舉例：4-鏈碼：000033333322222211110011第八頁，共七十頁，編輯于2023年，星期日鏈碼算法：給每一個線段邊界一個方向編碼。有4-鏈碼和8-鏈碼兩種編碼方法。從起點開始，沿邊界編碼，至起點被重新碰到，結(jié)束一個對象的編碼。第九頁，共七十頁，編輯于2023年，星期日鏈碼問題1：1）鏈碼相當(dāng)長。2）噪音會產(chǎn)生不必要的鏈碼。改進1：1）加大網(wǎng)格空間。2）依據(jù)原始邊界與結(jié)果的接近程度，來確定新點的位置。第十頁，共七十頁，編輯于2023年，星期日鏈碼舉例：4-鏈碼：003332221101第十一頁，共七十頁，編輯于2023年，星期日鏈碼問題2：1）由于起點的不同，造成編碼的不同2）由于角度的不同，造成編碼的不同改進2：1）從固定位置作為起點(最左最上)開始編碼2）通過使用鏈碼的首差代替碼子本身的方式第十二頁，共七十頁，編輯于2023年，星期日鏈碼循環(huán)首差鏈碼：用相鄰鏈碼的差代替鏈碼例如：4-鏈碼10103322循環(huán)首差為： 33133030循環(huán)首差：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第十三頁，共七十頁，編輯于2023年，星期日

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

1）點合成法

2）邊分裂法第十五頁，共七十頁，編輯于2023年，星期日多邊形逼近點合成算法思想舉例：RR<T第十六頁，共七十頁，編輯于2023年，星期日

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

頂點一般不對應(yīng)于邊界的拐點（如拐角）。因為新的線段直到超過誤差的閾值才開始。分裂法可用于緩解這個問題!第十八頁，共七十頁，編輯于2023年，星期日多邊形逼近邊分裂算法思想舉例：

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

區(qū)域骨架基本思想表示一個平面區(qū)域結(jié)構(gòu)形狀的重要方法是把它削減成圖形。這種削減可以通過細化（也稱為抽骨架）算法，獲取區(qū)域的骨架來實現(xiàn)Blum的中軸變換方法（MAT）設(shè):R是一個區(qū)域，B為R的邊界點，對于R中的點p，找p在B上“最近”的鄰居。如果p有多于一個的鄰居，稱它屬于R的中軸（骨架）第二十八頁，共七十頁，編輯于2023年，星期日pRB

Blum的中軸變換方法（MAT）設(shè):R是一個區(qū)域

B為R的邊界點對于R中的點p，找p在B上“最近”的鄰居。如果p有多于一個的鄰居，稱它屬于R的中軸（骨架）第二十九頁，共七十頁，編輯于2023年，星期日區(qū)域骨架問題：計算量大第三十頁，共七十頁，編輯于2023年，星期日

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

區(qū)域骨架:一種細化二值區(qū)域的算法假設(shè)區(qū)域內(nèi)的點值為1，背景值為0這個方法由對給定區(qū)域的邊界點連續(xù)進行兩個基本操作構(gòu)成這里邊界點是指任何值為1且至少有一個8鄰域上的點為0的象素第三十二頁，共七十頁，編輯于2023年，星期日對于滿足以下四個條件的邊界點打標(biāo)記準(zhǔn)備刪除：(a)2N(p1)6其中N(p1)是點p1的鄰域中1的個數(shù)，即： N(p1)=p2+p3+…+p9(b) S(p1)=1

其中S(p1)是按p2,p3,…,p9順序，0-1轉(zhuǎn)換的個數(shù)(c) p2*p4*p6=0（p2、p4、p6至少有一個0）(d) p4*p6*p8=0（p4、p6、p8至少有一個0）p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5區(qū)域骨架基本操作1第三十三頁，共七十頁，編輯于2023年，星期日舉例: N(p1)=4

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

區(qū)域骨架所有條件都滿足，才打刪除標(biāo)記。刪除并不立即進行，而是等到對所有邊界點都打完標(biāo)記后，再把作了標(biāo)記的點一起刪除第三十四頁，共七十頁，編輯于2023年，星期日

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

p2*p4*p8=0d’)

p2*p6*p8=0p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5第三十五頁，共七十頁，編輯于2023年，星期日

區(qū)域骨架細化算法細化算法的一輪操作包括：按操作1，給邊界點打標(biāo)記——刪除點按操作2，給邊界點打標(biāo)記——刪除點這個基本過程反復(fù)進行，直至沒有點可以刪除為止。此時算法終止。第三十六頁，共七十頁，編輯于2023年，星期日區(qū)域骨架例:

第三十七頁，共七十頁，編輯于2023年，星期日3.3.3特征表示與描述：邊界描述子邊界描述子簡單描述子形狀數(shù)傅立葉描述子矩量第三十八頁，共七十頁，編輯于2023年，星期日

簡單描述子邊界的周長：

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

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

D是歐氏距離或幾何距離，pi,pj是邊界上的點。直徑的長度和直徑的兩個端點連線（這條線被稱為邊界的主軸）的方向，是關(guān)于邊界的有用的描述符。第三十九頁，共七十頁，編輯于2023年，星期日簡單描述子邊界的直徑舉例第四十頁，共七十頁，編輯于2023年，星期日

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

交點a處的曲率為

dk=k1–k2

其中k1、k2為相鄰線段的斜率ak1k2簡單描述子邊界的曲率：第四十一頁，共七十頁，編輯于2023年，星期日

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

邊界的凹線段點： 當(dāng)頂點p上的斜率為負時，稱其為凹線段上的點第四十二頁，共七十頁，編輯于2023年，星期日3.3.3特征表示與描述：邊界描述子形狀數(shù)——鏈碼的實用化形狀數(shù)定義：最小循環(huán)首差鏈碼。循環(huán)首差鏈碼：用相鄰鏈碼的差代替鏈碼例如：4-鏈碼10103322

循環(huán)首差為：33133030循環(huán)首差: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第四十三頁，共七十頁，編輯于2023年，星期日3.3.3特征表示與描述：邊界描述子形狀數(shù)形狀數(shù)定義：例如：4-鏈碼：10103322

循環(huán)首差：33133|030

形狀數(shù)：03033133形狀數(shù)序號n的定義： 形狀數(shù)中阿拉伯?dāng)?shù)字的個數(shù)。上例序數(shù)為8

對于封閉邊界序號一定是偶數(shù)。如order4、6、8。第四十四頁，共七十頁，編輯于2023年，星期日3.3.3特征表示與描述：邊界描述子形狀數(shù)序號為4、6、8的形狀數(shù)舉例：

序號4鏈碼：0321首差：3333形狀：3333序號6鏈碼：003221首差：303303形狀：033033序號8鏈碼：00032221首差：30033003形狀：00330033第四十五頁，共七十頁，編輯于2023年，星期日3.3.3特征表示與描述：邊界描述子形狀數(shù)序號為6的形狀數(shù)舉例：

序號6鏈碼：033211首差：330330形狀：033033序號6鏈碼：003221首差：303303形狀：033033形狀數(shù)與方向無關(guān)第四十六頁，共七十頁，編輯于2023年，星期日形狀數(shù)序號為8的形狀數(shù)舉例：

序號8鏈碼：03032211首差：33133030形狀：03033133序號8鏈碼：00332211首差：30303030形狀：03030303序號8鏈碼：00323211首差：30331330形狀：03033133第四十七頁，共七十頁，編輯于2023年，星期日形狀數(shù)問題： 雖然鏈碼的首差是不依賴于旋轉(zhuǎn)的，但一般情況下邊界的編碼依賴于網(wǎng)格的方向。改進： 規(guī)整化網(wǎng)格方向，具體方法如下：第四十八頁，共七十頁，編輯于2023年，星期日

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

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

s(k)=x(k)+jy(k) k=0,1,…,N-1y0y1x0x1jyxx(k)=xky(k)=yk第五十四頁，共七十頁，編輯于2023年，星期日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系數(shù)a(u)被稱為邊界的傅立葉描述子第五十五頁，共七十頁，編輯于2023年，星期日3.3.3特征表示與描述：邊界描述子傅立葉描述子1）基本思想：（3）選取整數(shù)MN-1，進行逆傅立葉變換（重構(gòu)）

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

u=0

這時，對應(yīng)于邊界的點數(shù)沒有改變，但在重構(gòu)每一個點所需要的計算項大大減少了。如果邊界點數(shù)很大，M一般選為2的指數(shù)次方的整數(shù)。第五十六頁，共七十頁，編輯于2023年，星期日3.3.3特征表示與描述：邊界描述子傅立葉描述符2）M的選取與描述符的關(guān)系

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

L

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

i=1L其中

m=∑rig(ri)

i=1這里L(fēng)是邊界上點的數(shù)目,n(r)是邊界的矩量第六十一頁，共七十頁，編輯于2023年，星期日3.3.3特征表示與描述：邊界描述子矩量矩量的優(yōu)點：實現(xiàn)是直接的附帶了一種關(guān)于邊界形狀的“物理”解釋對于旋轉(zhuǎn)的不敏感性為了使大小比例不敏感，可以通過伸縮r的范圍來將大小正則化。

第六十二頁，共七十頁，編輯于2023年，星期日3.3.4特征表示與描述：關(guān)系描述子關(guān)系描述子基本思想階梯關(guān)系編碼骨架關(guān)系編碼方向關(guān)系編碼內(nèi)角關(guān)系編碼樹結(jié)構(gòu)關(guān)系編碼第六十三頁，共七