圖像表示與描述課件

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

2）用邊界的方向作為編碼依據(jù)。為簡(jiǎn)化邊界的描述。一般描述的是邊界點(diǎn)集。0123014672354-鏈碼8-鏈碼3.3.2表示與描述:表示法設(shè)計(jì)鏈碼012301467233.3.2表示與描述:表示法設(shè)計(jì)鏈碼算法：給每一個(gè)線段一個(gè)方向編碼。有4-鏈碼和8-鏈碼兩種編碼方法。從起點(diǎn)開始，沿邊界編碼，至起點(diǎn)被重新碰到，結(jié)束一個(gè)對(duì)象的編碼。3.3.2表示與描述:表示法設(shè)計(jì)鏈碼3.3.2表示與描述:表示法設(shè)計(jì)鏈碼舉例：4-鏈碼：0000333333222222111100113.3.2表示與描述:表示法設(shè)計(jì)鏈碼舉例：4-鏈碼：0003.3.2表示與描述:表示法設(shè)計(jì)鏈碼問題1：1）鏈碼相當(dāng)長(zhǎng)。2）噪音會(huì)產(chǎn)生不必要的鏈碼。改進(jìn)1：1）加大網(wǎng)格空間。2）依據(jù)原始邊界與結(jié)果的接近程度，來確定新點(diǎn)的位置。3.3.2表示與描述:表示法設(shè)計(jì)鏈碼3.3.2表示與描述:表示法設(shè)計(jì)鏈碼舉例：4-鏈碼：0033322211013.3.2表示與描述:表示法設(shè)計(jì)鏈碼舉例：4-鏈碼：0033.3.2表示與描述:表示法設(shè)計(jì)鏈碼問題2：1）由于起點(diǎn)的不同，造成編碼的不同2）由于角度的不同，造成編碼的不同改進(jìn)2：1）從固定位置作為起點(diǎn)(最左最上)開始編碼2）通過使用鏈碼的首差代替碼子本身的方式3.3.2表示與描述:表示法設(shè)計(jì)鏈碼3.3.2表示與描述:表示法設(shè)計(jì)鏈碼循環(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=03.3.2表示與描述:表示法設(shè)計(jì)鏈碼3.3.2表示與描述:表示法設(shè)計(jì)鏈碼應(yīng)用背景：如果邊界的本身對(duì)于旋轉(zhuǎn)和比例修改來說是無變化的，使用鏈碼才是正確的。一般來說這是不可能的，實(shí)際應(yīng)用時(shí)還需要改進(jìn)。用鏈碼后，對(duì)象只要用1)起點(diǎn)坐標(biāo)，2)周長(zhǎng)（邊界點(diǎn)數(shù)）3)鏈碼，4)對(duì)象編號(hào)，就可以描述。鏈碼一般用于一幅圖像中有多個(gè)對(duì)象的情況，對(duì)單個(gè)對(duì)象不適用。3.3.2表示與描述:表示法設(shè)計(jì)鏈碼3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近基本思想：用最少的多邊形線段，獲取邊界形狀的本質(zhì)。尋找最小基本多邊形的方法一般有兩種：點(diǎn)合成法和邊分裂法3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近點(diǎn)合成算法思想舉例：3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近合成點(diǎn)算法：1）沿著邊界選兩個(gè)相鄰的點(diǎn)對(duì)，計(jì)算首尾連接直線段與原始折線段的誤差。2）如果誤差小于預(yù)先設(shè)置的閾值。去掉中間點(diǎn)，選新點(diǎn)對(duì)與下一相鄰點(diǎn)對(duì)，重復(fù)1）；否則，存儲(chǔ)線段的參數(shù)，置誤差為0，選被存儲(chǔ)線段的終點(diǎn)為起點(diǎn)，重復(fù)1）2）。3）當(dāng)程序的第一個(gè)起點(diǎn)被遇到，程序結(jié)束。3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近合成點(diǎn)算法的問題：

頂點(diǎn)一般不對(duì)應(yīng)于邊界的拐點(diǎn)（如拐角）。因?yàn)樾碌木€段直到超過誤差的閾值才開始。下面講到的分裂法可用于緩解這個(gè)問題3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近邊分裂算法思想舉例：

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

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

p2*p4*p8=0d’)

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

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

3.3.2表示與描述:表示法設(shè)計(jì)區(qū)域骨架3.3.3表示與描述：邊界描述子邊界描述子簡(jiǎn)單描述子形狀數(shù)傅立葉描述子矩量3.3.3表示與描述：邊界描述子邊界描述子3.3.3表示與描述：邊界描述子簡(jiǎn)單描述子邊界的周長(zhǎng)：是最簡(jiǎn)單的描述符之一。沿輪廓線計(jì)算象素的個(gè)數(shù)，給出了一個(gè)長(zhǎng)度的近似估計(jì)邊界的直徑：邊界B的直徑是：

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

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

交點(diǎn)a處的曲率為

dk=k1–k2

其中k1、k2為相鄰線段的斜率ak1k23.3.3表示與描述：邊界描述子簡(jiǎn)單描述子ak1k23.3.3表示與描述：邊界描述子簡(jiǎn)單描述子邊界的凸線段點(diǎn)： 當(dāng)頂點(diǎn)p上的斜率是非負(fù)時(shí)，稱其為凸線段上的點(diǎn)邊界的凹線段點(diǎn)： 當(dāng)頂點(diǎn)p上的斜率為負(fù)時(shí)，稱其為凹線段上的點(diǎn)3.3.3表示與描述：邊界描述子簡(jiǎn)單描述子3.3.3表示與描述：邊界描述子簡(jiǎn)單描述子邊界的凸線段點(diǎn)P1：邊界的凹線段點(diǎn)P2：P1P23.3.3表示與描述：邊界描述子簡(jiǎn)單描述子P1P23.3.3表示與描述：邊界描述子形狀數(shù)形狀數(shù)定義：最小循環(huán)首差鏈碼。循環(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=03.3.3表示與描述：邊界描述子形狀數(shù)3.3.3表示與描述：邊界描述子形狀數(shù)形狀數(shù)定義：例如：4-鏈碼：10103322

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

形狀數(shù)：03033133形狀數(shù)序號(hào)n的定義： 形狀數(shù)中阿拉伯?dāng)?shù)字的個(gè)數(shù)，對(duì)于封閉邊界序號(hào)是偶數(shù)。如order4、6、8。3.3.3表示與描述：邊界描述子形狀數(shù)3.3.3表示與描述：邊界描述子形狀數(shù)形狀數(shù)例如：

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

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

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

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

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）選取整數(shù)MN-1，進(jìn)行逆傅立葉變換（重構(gòu)）

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

u=0

這時(shí)，對(duì)應(yīng)于邊界的點(diǎn)數(shù)沒有改變，但在重構(gòu)每一個(gè)點(diǎn)所需要的計(jì)算項(xiàng)大大減少了。如果邊界點(diǎn)數(shù)很大，M一般選為2的指數(shù)次方的整數(shù)。3.3.3表示與描述：邊界描述子傅立葉描述子3.3.3表示與描述：邊界描述子傅立葉描述符2）M的選取與描述符的關(guān)系

在上述方法中，相當(dāng)于對(duì)于u>M-1的部分舍去不予計(jì)算。由于傅立葉變換中高頻部分對(duì)應(yīng)于圖像的細(xì)節(jié)描述，因此M取得越小，細(xì)節(jié)部分丟失得越多。3.3.3表示與描述：邊界描述子傅立葉描述符3.3.3表示與描述：邊界描述子傅立葉描述符3）優(yōu)點(diǎn)1）使用復(fù)數(shù)作為描述符，對(duì)于旋轉(zhuǎn)、平移、放縮等操作和起始點(diǎn)的選取不十分敏感。2）以上幾何變換均可以通過對(duì)描述子函數(shù)作簡(jiǎn)單變換來獲得。3.3.3表示與描述：邊界描述子傅立葉描述符3.3.3表示與描述：邊界描述子矩量基本思想：將描述形狀的任務(wù)減少至描述一個(gè)一維函數(shù)，邊界段和特征的形狀可以用矩量來量化地描述矩量的定義：把邊界當(dāng)作直方圖函數(shù)：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(fēng)是邊界上點(diǎn)的數(shù)目,n(r)是邊界的矩量3.3.3表示與描述：邊界描述子矩量3.3.3表示與描述：邊界描述子矩量矩量的優(yōu)點(diǎn)：實(shí)現(xiàn)是直接的附帶了一種關(guān)于邊界形狀的“物理”解釋對(duì)于旋轉(zhuǎn)的不敏感性為了使大小比例不敏感，可以通過伸縮r的范圍來將大小正則化。

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

(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表示與描述：關(guān)系描述子階梯結(jié)構(gòu)關(guān)系(1,3)(13.3.4表示與描述：關(guān)系描述子骨架關(guān)系編碼用有向線段來描述一個(gè)圖像的各個(gè)部分（例如同構(gòu)區(qū)域），這個(gè)線段是通過頭尾連接等方法得到的。線段之間的不同運(yùn)算代表了區(qū)域的不同組合。當(dāng)圖像的連通性可以通過首尾相接或其它連續(xù)的方式描述的時(shí)候，最適于使用這種串來描述。3.3.4表示與描述：關(guān)系描述子骨架關(guān)系編碼3.3.4表示與描述：關(guān)系描述子骨架關(guān)系編碼a+ba-ba×ba*baaaabbbb編碼3.3.4表示與描述：關(guān)系描述子骨架關(guān)系編碼a+ba3.3.4表示與描述：關(guān)系描述子方向關(guān)系編碼跟蹤對(duì)象的邊界，將跟蹤得到的線段按照方向或長(zhǎng)度來編碼a1a2a5a7a8a3a4a6a1a8a7a6a5a4a3a23.3.4表示與描述：關(guān)系描述子方向關(guān)系編碼a1a2a5a3.3.4表示與描述：關(guān)系描述子內(nèi)角關(guān)系編碼根據(jù)角度范圍不同，編碼為8個(gè)符號(hào)即:a1:0-45;a2:45-90;a3:90-135;…;

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

2）用邊界的方向作為編碼依據(jù)。為簡(jiǎn)化邊界的描述。一般描述的是邊界點(diǎn)集。0123014672354-鏈碼8-鏈碼3.3.2表示與描述:表示法設(shè)計(jì)鏈碼012301467233.3.2表示與描述:表示法設(shè)計(jì)鏈碼算法：給每一個(gè)線段一個(gè)方向編碼。有4-鏈碼和8-鏈碼兩種編碼方法。從起點(diǎn)開始，沿邊界編碼，至起點(diǎn)被重新碰到，結(jié)束一個(gè)對(duì)象的編碼。3.3.2表示與描述:表示法設(shè)計(jì)鏈碼3.3.2表示與描述:表示法設(shè)計(jì)鏈碼舉例：4-鏈碼：0000333333222222111100113.3.2表示與描述:表示法設(shè)計(jì)鏈碼舉例：4-鏈碼：0003.3.2表示與描述:表示法設(shè)計(jì)鏈碼問題1：1）鏈碼相當(dāng)長(zhǎng)。2）噪音會(huì)產(chǎn)生不必要的鏈碼。改進(jìn)1：1）加大網(wǎng)格空間。2）依據(jù)原始邊界與結(jié)果的接近程度，來確定新點(diǎn)的位置。3.3.2表示與描述:表示法設(shè)計(jì)鏈碼3.3.2表示與描述:表示法設(shè)計(jì)鏈碼舉例：4-鏈碼：0033322211013.3.2表示與描述:表示法設(shè)計(jì)鏈碼舉例：4-鏈碼：0033.3.2表示與描述:表示法設(shè)計(jì)鏈碼問題2：1）由于起點(diǎn)的不同，造成編碼的不同2）由于角度的不同，造成編碼的不同改進(jìn)2：1）從固定位置作為起點(diǎn)(最左最上)開始編碼2）通過使用鏈碼的首差代替碼子本身的方式3.3.2表示與描述:表示法設(shè)計(jì)鏈碼3.3.2表示與描述:表示法設(shè)計(jì)鏈碼循環(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=03.3.2表示與描述:表示法設(shè)計(jì)鏈碼3.3.2表示與描述:表示法設(shè)計(jì)鏈碼應(yīng)用背景：如果邊界的本身對(duì)于旋轉(zhuǎn)和比例修改來說是無變化的，使用鏈碼才是正確的。一般來說這是不可能的，實(shí)際應(yīng)用時(shí)還需要改進(jìn)。用鏈碼后，對(duì)象只要用1)起點(diǎn)坐標(biāo)，2)周長(zhǎng)（邊界點(diǎn)數(shù)）3)鏈碼，4)對(duì)象編號(hào)，就可以描述。鏈碼一般用于一幅圖像中有多個(gè)對(duì)象的情況，對(duì)單個(gè)對(duì)象不適用。3.3.2表示與描述:表示法設(shè)計(jì)鏈碼3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近基本思想：用最少的多邊形線段，獲取邊界形狀的本質(zhì)。尋找最小基本多邊形的方法一般有兩種：點(diǎn)合成法和邊分裂法3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近點(diǎn)合成算法思想舉例：3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近合成點(diǎn)算法：1）沿著邊界選兩個(gè)相鄰的點(diǎn)對(duì)，計(jì)算首尾連接直線段與原始折線段的誤差。2）如果誤差小于預(yù)先設(shè)置的閾值。去掉中間點(diǎn)，選新點(diǎn)對(duì)與下一相鄰點(diǎn)對(duì)，重復(fù)1）；否則，存儲(chǔ)線段的參數(shù)，置誤差為0，選被存儲(chǔ)線段的終點(diǎn)為起點(diǎn)，重復(fù)1）2）。3）當(dāng)程序的第一個(gè)起點(diǎn)被遇到，程序結(jié)束。3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近合成點(diǎn)算法的問題：

頂點(diǎn)一般不對(duì)應(yīng)于邊界的拐點(diǎn)（如拐角）。因?yàn)樾碌木€段直到超過誤差的閾值才開始。下面講到的分裂法可用于緩解這個(gè)問題3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近3.3.2表示與描述:表示法設(shè)計(jì)多邊形逼近邊分裂算法思想舉例：

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

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

p2*p4*p8=0d’)

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

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

3.3.2表示與描述:表示法設(shè)計(jì)區(qū)域骨架3.3.3表示與描述：邊界描述子邊界描述子簡(jiǎn)單描述子形狀數(shù)傅立葉描述子矩量3.3.3表示與描述：邊界描述子邊界描述子3.3.3表示與描述：邊界描述子簡(jiǎn)單描述子邊界的周長(zhǎng)：是最簡(jiǎn)單的描述符之一。沿輪廓線計(jì)算象素的個(gè)數(shù)，給出了一個(gè)長(zhǎng)度的近似估計(jì)邊界的直徑：邊界B的直徑是：

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

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

交點(diǎn)a處的曲率為

dk=k1–k2

其中k1、k2為相鄰線段的斜率ak1k23.3.3表示與描述：邊界描述子簡(jiǎn)單描述子ak1k23.3.3表示與描述：邊界描述子簡(jiǎn)單描述子邊界的凸線段點(diǎn)： 當(dāng)頂點(diǎn)p上的斜率是非負(fù)時(shí)，稱其為凸線段上的點(diǎn)邊界的凹線段點(diǎn)： 當(dāng)頂點(diǎn)p上的斜率為負(fù)時(shí)，稱其為凹線段上的點(diǎn)3.3.3表示與描述：邊界描述子簡(jiǎn)單描述子3.3.3表示與描述：邊界描述子簡(jiǎn)單描述子邊界的凸線段點(diǎn)P1：邊界的凹線段點(diǎn)P2：P1P23.3.3表示與描述：邊界描述子簡(jiǎn)單描述子P1P23.3.3表示與描述：邊界描述子形狀數(shù)形狀數(shù)定義：最小循環(huán)首差鏈碼。循環(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=03.3.3表示與描述：邊界描述子形狀數(shù)3.3.3表示與描述：邊界描述子形狀數(shù)形狀數(shù)定義：例如：4-鏈碼：10103322

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

形狀數(shù)：03033133形狀數(shù)序號(hào)n的定義： 形狀數(shù)中阿拉伯?dāng)?shù)字的個(gè)數(shù)，對(duì)于封閉邊界序號(hào)是偶數(shù)。如order4、6、8。3.3.3表示與描述：邊界描述子形狀數(shù)3.3.3表示與描述：邊界描述子形狀數(shù)形狀數(shù)例如：

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

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

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

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

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）