1、數(shù)字圖像處理,北京大學(xué)計算機(jī)研究所 陳曉鷗,第三節(jié) 表示與描述,3.3.1 表示與描述的基本概念 3.3.2 表示法設(shè)計 3.3.3 邊界描述子 3.3.4 關(guān)系描述子,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表示與描述的基本概念,基本概念 選擇表達(dá)方式，要本著使數(shù)據(jù)變得更有利于下一步的計算工作。下一步工作是基于所選的表達(dá)方式描述這個區(qū)域，一般情況下

2、： 1）如果關(guān)注的焦點(diǎn)是形狀特性，選擇外部表示方式 2）如果關(guān)注的焦點(diǎn)是反射率特性，如顏色、文理時，選擇內(nèi)部表示方式。 3）所選表示方式，應(yīng)該對尺寸、變換、旋轉(zhuǎn)等變量盡可能的不敏感,3.3.2 表示與描述:表示法設(shè)計,表示法設(shè)計 鏈碼 多邊形逼近 外形特征 邊界分段 區(qū)域骨架,3.3.2 表示與描述:表示法設(shè)計,鏈碼 定義：1）鏈碼是一種邊界的編碼表示法。 2）用邊界的方向作為編碼依據(jù)。為簡化邊界的描述。一般描述的是邊界點(diǎn)集。,0,1,2,3,0,1,4,6,7,2,3,5,4-鏈碼,8-鏈碼,3.3.2 表示與描述:表示法設(shè)計,鏈碼 算法： 給每一個線段一個方向編碼。 有4-鏈碼和8-鏈碼兩

3、種編碼方法。 從起點(diǎn)開始，沿邊界編碼，至起點(diǎn)被重新碰到，結(jié)束一個對象的編碼。,3.3.2 表示與描述:表示法設(shè)計,鏈碼舉例：,4-鏈碼：000033333322222211110011,3.3.2 表示與描述:表示法設(shè)計,鏈碼 問題1： 1）鏈碼相當(dāng)長。 2）噪音會產(chǎn)生不必要的鏈碼。 改進(jìn)1： 1）加大網(wǎng)格空間。 2）依據(jù)原始邊界與結(jié)果的接近程度，來確定新點(diǎn)的位置。,3.3.2 表示與描述:表示法設(shè)計,鏈碼舉例：,4-鏈碼：003332221101,3.3.2 表示與描述:表示法設(shè)計,鏈碼 問題2： 1）由于起點(diǎn)的不同，造成編碼的不同 2）由于角度的不同，造成編碼的不同 改進(jìn)2： 1）從固定位

4、置作為起點(diǎn)(最左最上)開始編碼 2）通過使用鏈碼的首差代替碼子本身的方式,3.3.2 表示與描述:表示法設(shè)計,鏈碼 循環(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 = 12 - 3 = -1(3) 0 - 1 = -1(3)2 - 2 = 0,3.3.2 表示與描述:表示法設(shè)計,鏈碼 應(yīng)用背景： 如果邊界的本身對于旋轉(zhuǎn)和比例修改來說是無變化的，使用鏈碼才是正確的。一般來說這是不可能的，實(shí)際應(yīng)用時還需要改進(jìn)。 用鏈碼后，對象只要

5、用1)起點(diǎn)坐標(biāo)，2)周長（邊界點(diǎn)數(shù)）3)鏈碼，4)對象編號，就可以描述。 鏈碼一般用于一幅圖像中有多個對象的情況，對單個對象不適用。,3.3.2 表示與描述:表示法設(shè)計,多邊形逼近 基本思想：用最少的多邊形線段，獲取邊界形狀的本質(zhì)。 尋找最小基本多邊形的方法一般有兩種：點(diǎn)合成法和邊分裂法,3.3.2 表示與描述:表示法設(shè)計,多邊形逼近 點(diǎn)合成算法思想舉例：,3.3.2 表示與描述:表示法設(shè)計,多邊形逼近 合成點(diǎn)算法： 1）沿著邊界選兩個相鄰的點(diǎn)對，計算首尾連接直線段與原始折線段的誤差。 2）如果誤差小于預(yù)先設(shè)置的閾值。去掉中間點(diǎn)，選新點(diǎn)對與下一相鄰點(diǎn)對，重復(fù)1）；否則，存儲線段的參數(shù)，置誤差為

6、0，選被存儲線段的終點(diǎn)為起點(diǎn)，重復(fù)1）2）。 3）當(dāng)程序的第一個起點(diǎn)被遇到，程序結(jié)束。,3.3.2 表示與描述:表示法設(shè)計,多邊形逼近 合成點(diǎn)算法的問題： 頂點(diǎn)一般不對應(yīng)于邊界的拐點(diǎn)（如拐角）。因?yàn)樾碌木€段直到超過誤差的閾值才開始。 下面講到的分裂法可用于緩解這個問題,3.3.2 表示與描述:表示法設(shè)計,多邊形逼近 邊分裂算法思想舉例：,3.3.2 表示與描述:表示法設(shè)計,多邊形逼近 分裂邊算法： （1）連接邊界線段的兩個端點(diǎn)（如果是封閉邊界，連接最遠(yuǎn)點(diǎn)）； （2）如果最大正交距離大于閾值，將邊界分為兩段，最大值點(diǎn)定位一個頂點(diǎn)。重復(fù)（1）； （3）如果沒有超過閾值的正交距離，結(jié)束。,3.3.2

7、 表示與描述:表示法設(shè)計,外形特征 基本思想： 外形特征是一種用一維函數(shù)表達(dá)邊界的方法?；舅枷胧前堰吔绲谋硎窘档揭痪S函數(shù),3.3.2 表示與描述:表示法設(shè)計,外形特征 函數(shù)定義質(zhì)心角函數(shù)：邊上的點(diǎn)到質(zhì)心的距離r，作為夾角的的函數(shù)。,A,r,r(),2,A,3.3.2 表示與描述:表示法設(shè)計,外形特征 舉例：,A,r,r(),2,A,3.3.2 表示與描述:表示法設(shè)計,外形特征 問題：函數(shù)過分依賴于旋轉(zhuǎn)和比例的變化 改進(jìn)： 對于旋轉(zhuǎn)兩種改進(jìn)： a.選擇離質(zhì)心最遠(yuǎn)的點(diǎn)作為起點(diǎn) b.選擇從質(zhì)心到主軸最遠(yuǎn)的點(diǎn)作為起點(diǎn) 對于比例變換： 對函數(shù)進(jìn)行正則化，使函數(shù)值總是分布在相同的值域里，比如說0，1,3

8、.3.2 表示與描述:表示法設(shè)計,邊界分段 基本概念： 一個任意集合S（區(qū)域）的凸起外緣H是：包含S的最小凸起的集合 H-S的差的集合被稱為集合S的凸起補(bǔ)集D,S,S,D,S + D = H,3.3.2 表示與描述:表示法設(shè)計,邊界分段 分段算法： 給進(jìn)入和離開凸起補(bǔ)集的變換點(diǎn)打標(biāo)記來劃分邊界段。 優(yōu)點(diǎn)：不依賴于方向和比例的變化,S,3.3.2 表示與描述:表示法設(shè)計,邊界分段 問題： 噪音的影響，導(dǎo)致出現(xiàn)零碎的劃分。 解決的方法： 先平滑邊界，或用多邊形逼近邊界，然后再分段,3.3.2 表示與描述:表示法設(shè)計,區(qū)域骨架 基本思想 表示一個平面區(qū)域結(jié)構(gòu)形狀的重要方法是把它削減成圖形。這種削減可

9、以通過細(xì)化（也稱為抽骨架）算法，獲取區(qū)域的骨架來實(shí)現(xiàn) Blum的中軸變換方法（MAT） 設(shè):R是一個區(qū)域，B為R的邊界點(diǎn)，對于R中的點(diǎn)p，找p在B上“最近”的鄰居。如果p有多于一個的鄰居，稱它屬于R的中軸（骨架）,3.3.2 表示與描述:表示法設(shè)計,區(qū)域骨架 基本思想 問題：計算量大,p,R,B,3.3.2 表示與描述:表示法設(shè)計,區(qū)域骨架 算法改進(jìn)思想 在保證產(chǎn)生正確的骨架的同時，改進(jìn)算法的效率。比較典型的是一類細(xì)化算法，它們不斷刪去邊緣，但保證刪除滿足： （1）不移去端點(diǎn) （2）不破壞連通性 （3）不引起區(qū)域的過度腐蝕,3.3.2 表示與描述:表示法設(shè)計,區(qū)域骨架 一種細(xì)化二值區(qū)域的算法

10、假設(shè)區(qū)域內(nèi)的點(diǎn)值為1，背景值為0 這個方法由對給定區(qū)域的邊界點(diǎn)連續(xù)進(jìn)行兩個基本操作構(gòu)成 這里邊界點(diǎn)是指任何值為1且至少有一個8鄰域上的點(diǎn)為0的象素,3.3.2 表示與描述:表示法設(shè)計,區(qū)域骨架 基本操作1 對于滿足以下四個條件的邊界點(diǎn)打標(biāo)記準(zhǔn)備刪除： (a) 2N(p1)6 其中N(p1)是點(diǎn)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）,

11、p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,3.3.2 表示與描述:表示法設(shè)計,區(qū)域骨架 所有條件都滿足，才打刪除標(biāo)記。刪除并不立即進(jìn)行，而是等到對所有邊界點(diǎn)都打完標(biāo)記后，再把作了標(biāo)記的點(diǎn)一起刪除。 舉例: N(p1) = 4 S(p1) = 3 p2*p4*p6 = 0 p4*p6*p8 = 0 第2個條件沒滿足不打標(biāo)記,0,0,p1,1,1,0,1,0,1,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,3.3.2

12、 表示與描述:表示法設(shè)計,區(qū)域骨架 基本操作2 條件(a)、(b)與操作1相同 條件(c)、(d)改為： c) p2* p4* p8= 0 d) p2* p6* p8= 0,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,3.3.2 表示與描述:表示法設(shè)計,區(qū)域骨架 細(xì)化算法 細(xì)化算法的一輪操作包括： 按操作1，給邊界點(diǎn)打標(biāo)記刪除點(diǎn) 按操作2，給邊界點(diǎn)打標(biāo)記刪除點(diǎn) 這個基本過程反復(fù)進(jìn)行，直至沒有點(diǎn)可以刪除為止。此時算法終止。,3.3.2 表示與描述:表示法設(shè)計,區(qū)域骨架 算法分析： 1）條件a)的分析：當(dāng)輪廓點(diǎn)p1的8鄰域上有1個或7

13、個值為1的點(diǎn)時，不滿足條件a。 有1個點(diǎn)說明：p1是骨架上的終點(diǎn)，顯然不能刪除 有7個點(diǎn)說明：如果刪除p1會引起區(qū)域的腐蝕 2）條件b)的分析：當(dāng)p1在寬度為1的筆劃上時，不滿足條件b。因而該條件保證了骨架的連續(xù)性。,3.3.2 表示與描述:表示法設(shè)計,區(qū)域骨架 算法分析： （3）當(dāng)(p4=0 or p6=0)or(p2=0 and p8=0)時，條件c,d同時滿足。滿足這個條件的點(diǎn)可能是右邊、下邊、左上角的邊界點(diǎn)。任何一種情況下，p1都不是骨架的一部分，應(yīng)被刪除。 當(dāng)(p4=0 and p6=0)or(p2=0 or p8=0)時，條件c,d同時滿足。滿足這個條件的點(diǎn)可能是左邊、上邊、右下角

14、的邊界點(diǎn)，應(yīng)被刪除。,p9,p2,p1,p8,p3,p4,p7,p6,p5,p9,p2,p1,p8,p3,p4,p7,p6,p5,3.3.2 表示與描述:表示法設(shè)計,區(qū)域骨架 例:,3.3.3 表示與描述：邊界描述子,邊界描述子 簡單描述子 形狀數(shù) 傅立葉描述子 矩量,3.3.3 表示與描述：邊界描述子,簡單描述子 邊界的周長： 是最簡單的描述符之一。沿輪廓線計算象素的個數(shù)，給出了一個長度的近似估計 邊界的直徑：邊界B的直徑是： Diam(B) = maxD(pi, pj) D是歐氏距離或幾何距離，pi, pj是邊界上的點(diǎn)。直徑的長度和直徑的兩個端點(diǎn)連線（這條線被稱為邊界的主軸）的方向，是關(guān)于

15、邊界的有用的描述符。,3.3.3 表示與描述：邊界描述子,簡單描述子 邊界的直徑舉例,3.3.3 表示與描述：邊界描述子,簡單描述子 邊界的曲率： 曲率被描述為斜率的變化率。近似：用相鄰邊界線段（描述為直線）的斜率差作為在邊界線交點(diǎn)處的曲率描述子。 交點(diǎn)a處的曲率為 dk = k1 k2 其中k1、k2 為相鄰線段的斜率,a,k1,k2,3.3.3 表示與描述：邊界描述子,簡單描述子 邊界的凸線段點(diǎn)： 當(dāng)頂點(diǎn)p上的斜率是非負(fù)時，稱其為凸線段上的點(diǎn) 邊界的凹線段點(diǎn)： 當(dāng)頂點(diǎn)p上的斜率為負(fù)時，稱其為凹線段上的點(diǎn),3.3.3 表示與描述：邊界描述子,簡單描述子 邊界的凸線段點(diǎn)P1： 邊界的凹線段點(diǎn)P

16、2：,P1,P2,3.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 = 12 - 3 = -1(3) 0 - 1 = -1(3)2 - 2 = 0,3.3.3 表示與描述：邊界描述子,形狀數(shù) 形狀數(shù)定義： 例如： 4-鏈碼 ：10103322 循環(huán)首差 ：33133|030 形狀數(shù) ：03033133 形狀數(shù)序號n的定義： 形狀數(shù)中阿拉伯?dāng)?shù)字的個數(shù)，對于

17、封閉邊界序號是偶數(shù)。如order4、6、8。,3.3.3 表示與描述：邊界描述子,形狀數(shù) 形狀數(shù)例如：,序號4,鏈碼：0321 首差：3333 形狀：3333,序號6,鏈碼：003221 首差：303303 形狀：033033,序號8,鏈碼：00032221 首差：30033003 形狀：00330033,3.3.3 表示與描述：邊界描述子,形狀數(shù) 形狀數(shù)例如：,序號6,鏈碼：033211 首差：330330 形狀：033033,序號6,鏈碼：003221 首差：303303 形狀：033033,3.3.3 表示與描述：邊界描述子,形狀數(shù) 問題： 雖然鏈碼的首差是不依賴于旋轉(zhuǎn)的，但一般情況下邊

18、界的編碼依賴于網(wǎng)格的方向。 改進(jìn)： 規(guī)整化網(wǎng)格方向，具體方法如下：,3.3.3 表示與描述：邊界描述子,形狀數(shù) 幾個基本概念： 邊界最大軸a:是連接距離最遠(yuǎn)的兩個點(diǎn)的線段 邊界最小軸b:與最大軸垂直，且其長度確定的包圍盒剛好包圍邊界。 邊界離心率c：最大軸長度與最小軸長度的比 c = a / b 基本矩形: 包圍邊界的矩形。,3.3.3 表示與描述：邊界描述子,形狀數(shù) 基本概念舉例,邊界最大軸a,邊界最小軸b,基本矩形,3.3.3 表示與描述：邊界描述子,形狀數(shù) 規(guī)整化網(wǎng)格方向算法的思想： 大多數(shù)情況下，將鏈碼網(wǎng)格與基本矩形對齊，即可得到一個唯一的形狀數(shù)。 對一個給定的形狀序號，處理步驟如下：

19、 （1）我們找出一個序號為n的矩形，它的離心率最接近于給定形狀的基本矩形的離心率。,3.3.3 表示與描述：邊界描述子,形狀數(shù) （2）然后再用這個矩形構(gòu)造網(wǎng)格。 例如: 如果n=12，所有序號為12的矩形（即周長為12）為2*4，3*3，1*5。如果2*4矩形的離心率最接近于給定邊界的基本矩形的離心率，我們建立一個2*4的網(wǎng)格。 （3）再得到鏈碼。 （4）最后，再得到循環(huán)首差。 （5）首差中的最小循環(huán)數(shù)即為形狀數(shù)。,3.3.3 表示與描述：邊界描述子,形狀數(shù) 規(guī)整化網(wǎng)格方向算法舉例：,鏈碼：000033222121 首差：300030300313 形狀：000303003133,0,1,2,3

20、,3.3.3 表示與描述：邊界描述子,傅立葉描述子 1）基本思想： （1）對于XY平面上的每個邊界點(diǎn)，將其坐標(biāo)用復(fù)數(shù)表示為： s(k) = x(k) + jy(k) k=0,1,N-1,y0,y1,x0,x1,jy,x,x(k) = xk y(k) = yk,3.3.3 表示與描述：邊界描述子,傅立葉描述子 1）基本思想： （2）進(jìn)行離散傅立葉變換 N-1 a(u) =1/N s(k)exp(-j2uk/N) u=0,1,N-1 u=0 N-1 s(k) = a(u)exp(j2uk/N) k=0,1,N-1 u=0 a(u)被稱為邊界的傅立葉描述子,3.3.3 表示與描述：邊界描述子,傅立葉

21、描述子 1）基本思想： （3）選取整數(shù) MN-1，進(jìn)行逆傅立葉變換（重構(gòu)） M-1 s(k) = a(u)exp(j2uk/N) k=0,1,N-1 u=0 這時，對應(yīng)于邊界的點(diǎn)數(shù)沒有改變，但在重構(gòu)每一個點(diǎn)所需要的計算項(xiàng)大大減少了。如果邊界點(diǎn)數(shù)很大，M一般選為2的指數(shù)次方的整數(shù)。,3.3.3 表示與描述：邊界描述子,傅立葉描述符 2）M的選取與描述符的關(guān)系 在上述方法中，相當(dāng)于對于u M-1的部分舍去不予計算。由于傅立葉變換中高頻部分對應(yīng)于圖像的細(xì)節(jié)描述，因此M取得越小，細(xì)節(jié)部分丟失得越多。,3.3.3 表示與描述：邊界描述子,傅立葉描述符 3）優(yōu)點(diǎn) 1）使用復(fù)數(shù)作為描述符，對于旋轉(zhuǎn)、平移、放

22、縮等操作和起始點(diǎn)的選取不十分敏感。 2）以上幾何變換均可以通過對描述子函數(shù)作簡單變換來獲得。,3.3.3 表示與描述：邊界描述子,矩量 基本思想： 將描述形狀的任務(wù)減少至描述一個一維函數(shù)，邊界段和特征的形狀可以用矩量來量化地描述 矩量的定義： 把邊界當(dāng)作直方圖函數(shù)：g(r),r,g(r),3.3.3 表示與描述：邊界描述子,矩量 矩量的定義： L n(r) = (ri- m)ng(ri) i=1 L 其中 m = rig(ri) i=1 這里L(fēng)是邊界上點(diǎn)的數(shù)目, n(r)是邊界的矩量,3.3.3 表示與描述：邊界描述子,矩量 矩量的優(yōu)點(diǎn)： 實(shí)現(xiàn)是直接的 附帶了一種關(guān)于邊界形狀的“物理”解釋 對于旋轉(zhuǎn)的不敏感性 為了使大小比例不敏感，可以通過伸縮r的范圍來將大小正則化。,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)系描述子,基本思想： 通過挖掘各個成分之間的結(jié)構(gòu)關(guān)系來描