第六章 圖像表示與描述

第6章表示與描述圖像描述實(shí)例：指紋圖像描述（a）Gabor濾波器；（b）小波變換；（c）細(xì)節(jié)點(diǎn)（分叉點(diǎn)、端點(diǎn)）主要內(nèi)容6.1表示方法6.2邊界描繪子6.3區(qū)域描繪子6.4運(yùn)用主分量進(jìn)行描述（自學(xué)）6.1表示方法1鏈碼

（1）概念鏈碼是對(duì)邊界點(diǎn)的一種編碼表示方法，其基本思想是利用一系列具有特定長度和方向的相連的直線段來表示目標(biāo)的邊界。

舉例：若設(shè)起始點(diǎn)O的坐標(biāo)為（5，5），則分別用如下4方向和8方向鏈碼按逆時(shí)針順序表示區(qū)域邊界：4方向鏈碼：（5，5）111232323000；8方向鏈碼：（5，5）2224556000。

（2）鏈碼表示的特點(diǎn)A、只有邊界的起點(diǎn)需用絕對(duì)坐標(biāo)表示，其余點(diǎn)都可只用接續(xù)方向來代表偏移量；

B、與用坐標(biāo)值相比，鏈碼表達(dá)可大大減少邊界表示所需的數(shù)據(jù)量。

（3）存在的問題直接對(duì)分割所得的目標(biāo)邊界編碼，有可能出現(xiàn)如下問題：A、產(chǎn)生的碼串通常很長；

B、噪聲等干擾會(huì)導(dǎo)致小的邊界變化而使鏈碼發(fā)生與目標(biāo)整體形狀無關(guān)的較大變動(dòng)。（4）改進(jìn)措施對(duì)原邊界以較大的網(wǎng)格重新采樣，并把與原邊界點(diǎn)最接近的大網(wǎng)格點(diǎn)定為新的邊界點(diǎn)?？偨Y(jié)重采樣的規(guī)則。（5）鏈碼的起點(diǎn)歸一化

A、問題的引出

鏈碼起點(diǎn)的選擇常是很關(guān)鍵的。對(duì)同一個(gè)邊界，如用不同的邊界點(diǎn)作為鏈碼起點(diǎn)，得到的鏈碼是不同的。

B、歸一化給定1個(gè)從任意點(diǎn)開始而產(chǎn)生的鏈碼，可把它看作1個(gè)由各方向數(shù)構(gòu)成的自然數(shù)。將這些方向數(shù)依1個(gè)方向循環(huán)以使它們所構(gòu)成的自然數(shù)的值最小。我們將這樣轉(zhuǎn)換后所對(duì)應(yīng)的鏈碼起點(diǎn)作為這個(gè)邊界的歸一化鏈碼的起點(diǎn)。

另一起點(diǎn)：33221010（6）鏈碼的旋轉(zhuǎn)歸一化A、問題用鏈碼表示給定目標(biāo)的邊界時(shí)，如果目標(biāo)旋轉(zhuǎn)，則鏈碼會(huì)發(fā)生變化。B、解決方法利用鏈碼的一階差分來重新構(gòu)造1個(gè)序列(1個(gè)表示原鏈碼各段之間方向變化的新序列)。這相當(dāng)于把鏈碼進(jìn)行旋轉(zhuǎn)歸一化。原碼旋轉(zhuǎn)90度碼鏈碼10103322212100334方向差分：3313303033133030

練習(xí)：分別寫出下面目標(biāo)的4連接和8連接鏈碼、最小值鏈碼和差分鏈碼。分別以（1，2）、（0，2）點(diǎn)為起點(diǎn)，順時(shí)針進(jìn)行。2多邊形近似（1）問題的引出實(shí)際應(yīng)用中的數(shù)字邊界常由于噪聲、采樣等的影響而有許多較小的不規(guī)則處，這些不規(guī)則處常對(duì)鏈碼和邊界段表達(dá)產(chǎn)生較明顯的干擾影響。（2）多邊形方法的基本思想多邊形是一系列線段的封閉集合，它可用來逼近大多數(shù)使用的曲線到任意的精度。在實(shí)際中多邊形表達(dá)的目的是要用盡量少的線段來代表邊界并保持邊界的基本形狀，從而用較簡單的形式來表達(dá)和描述邊界。（3）基于收縮的最小周長多邊形法將邊界看成是有彈性的線，將組成邊界的像素系列的內(nèi)外邊各看成一堵墻，如將線拉緊則可到最小周長多邊形。（4）聚合技術(shù)

A、算法步驟：1）沿著邊界選兩個(gè)相鄰的點(diǎn)對(duì)，計(jì)算首尾連接直線段與原始折線段的誤差R。2）如果誤差R小于預(yù)先設(shè)置的閾值T。去掉中間點(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é)束。RR<TB、聚合算法存在的問題：

頂點(diǎn)一般不對(duì)應(yīng)于邊界的拐點(diǎn)（如拐角）。因?yàn)樾碌木€段直到超過誤差的閾值才開始。（4）拆分技術(shù)

算法步驟：1）連接邊界線段的兩個(gè)端點(diǎn)（如果是封閉邊界，連接最遠(yuǎn)點(diǎn)）；2）如果最大正交距離大于閾值，將邊界分為兩段，最大值點(diǎn)定位一個(gè)頂點(diǎn)。重復(fù)1）；3）如果沒有超過閾值的正交距離，結(jié)束。3標(biāo)記

（1）基本思想標(biāo)記是邊界的1-D泛函表達(dá)，其基本思想是把2-D的邊界用1-D的較易描述的函數(shù)形式來表達(dá)。（2）最簡單的標(biāo)記方法先對(duì)給定的物體求出質(zhì)心，然后把邊界點(diǎn)與質(zhì)心的距離作為角度的函數(shù)就得到一種標(biāo)記。（3）存在問題函數(shù)過分依賴于旋轉(zhuǎn)和比例的變化。（4）改進(jìn)措施-----旋轉(zhuǎn)不變A、選擇離質(zhì)心最遠(yuǎn)的點(diǎn)作為起點(diǎn)；B、選擇從質(zhì)心到本征軸最遠(yuǎn)的點(diǎn)作為起點(diǎn)；C、使用差分鏈碼的方法。（5）改進(jìn)措施-----比例不變對(duì)函數(shù)進(jìn)行正則化，使函數(shù)值總是分布在相同的值域里，比如說[0，1]。A、利用長短軸進(jìn)行正則化；B、利用所有邊界樣本進(jìn)行正則化。4邊界分段（1）基本概念A(yù)、一個(gè)任意集合S（區(qū)域）的凸起外緣H是：包含S的最小凸起的集合。B、H-S的差的集合被稱為集合S的凸起補(bǔ)集D。SSDS+D=H（2）分段算法：給進(jìn)入和離開凸起補(bǔ)集D的變換點(diǎn)打標(biāo)記來劃分邊界段。（3）優(yōu)點(diǎn)：不依賴于方向和比例的變化S（4）存在問題噪音的影響，導(dǎo)致出現(xiàn)零碎的劃分。（5）改進(jìn)措施先平滑邊界，或用多邊形逼近邊界，然后再分段。4骨架（1）基本思想表示一個(gè)平面區(qū)域結(jié)構(gòu)形狀的一種重要方法是把它削減成圖形。這種削減可以通過細(xì)化（也稱為抽骨架）算法，獲取區(qū)域的骨架來實(shí)現(xiàn)。（2）Blum的中軸變換方法（MAT）設(shè)：R是一個(gè)區(qū)域，B為R的邊界點(diǎn)，對(duì)于R中的點(diǎn)p，找p在B上“最近”的鄰居。如果p有多于一個(gè)的鄰居，稱它屬于R的中軸（骨架）pRB（3）存在問題：計(jì)算量大（4）算法改進(jìn)思想在保證產(chǎn)生正確的骨架的同時(shí)，改進(jìn)算法的效率。比較典型的是一類細(xì)化算法，它們不斷刪去邊緣，但保證刪除滿足：A、不移去端點(diǎn)B、不破壞連通性C、不引起區(qū)域的過度腐蝕（5）一種細(xì)化二值區(qū)域的算法假設(shè)區(qū)域內(nèi)的點(diǎn)值為1，背景值為0。由兩個(gè)基本操作組成。A、基本操作1對(duì)于滿足以下四個(gè)條件的邊界點(diǎn)打標(biāo)記準(zhǔn)備刪除：(a)2

N(p1)

6

（N(p1)=p2+p3+…+p9，是點(diǎn)p1鄰域中1的個(gè)數(shù)）(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）p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5所有條件都滿足，才打刪除標(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)記00p1110101p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5B、基本操作2條件(a)、(b)與操作1相同，條件(c)、(d)改為：c’)p2*p4*p8=0d’)p2*p6*p8=0p9p2p1p8p3p4p7p6p5p9p2p1p8p3p4p7p6p5隨堂練習(xí)：（骨架抽?。?.2邊界描繪子1一些簡單的描繪子

（1）邊界的長度A、定義：區(qū)域的邊界長度。

B、計(jì)算方法1)周長用邊界所占面積表示，也即邊界點(diǎn)數(shù)之和，每個(gè)點(diǎn)占面積為1的一個(gè)小方塊。2)當(dāng)把像素看作一個(gè)個(gè)點(diǎn)時(shí)，則周長用鏈碼表示。此時(shí)，當(dāng)鏈碼值為奇數(shù)時(shí)，其長度記作 ；當(dāng)鏈碼值為偶數(shù)時(shí)，其長度記作1。即周長p表示為隨堂練習(xí)：（周長計(jì)算）（2）邊界的直徑Diam(B)=max[D(pi,pj)]（3）邊界線的離心率：長軸和短軸的比率。A、邊界最大軸a：是連接距離最遠(yuǎn)的兩個(gè)點(diǎn)的線段。B、邊界最小軸b：與最大軸垂直，且其長度確定的包圍盒剛好包圍邊界。C、基本矩形:包圍邊界的矩形。邊界最大軸a邊界最小軸b基本矩形（4）曲率

定義為斜率的改變率，描述了邊界上各點(diǎn)沿邊界方向的變化量。用相鄰邊界線段（描述為直線）的斜率差作為在邊界線交點(diǎn)處的曲率描述子。

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

dk=k1–k2

在一個(gè)邊界點(diǎn)的曲率的符號(hào)描述了邊界在該點(diǎn)的凹凸性。如果曲率大于零，則曲線凹向朝著該點(diǎn)法線的正向。如果曲率小于零，則曲線凹向朝著該點(diǎn)法線的負(fù)方向。P1P22形狀數(shù)（1）定義：形狀數(shù)是鏈碼的最小值的差分碼。例如：基于4—方向的鏈碼為:10103322,差分碼為：33133030,形狀數(shù)為：03033133。（2）形狀數(shù)的階(order)形狀數(shù)序列的長度(即碼的個(gè)數(shù))。對(duì)閉合曲線，階總是偶數(shù)。對(duì)凸形區(qū)域，階對(duì)應(yīng)邊界外包矩形的周長。

序號(hào)為4、6、8的形狀數(shù)舉例：

序號(hào)4鏈碼：0321首差：3333形狀：3333序號(hào)6鏈碼：003221首差：303303形狀：033033序號(hào)8鏈碼：00032221首差：30033003形狀：00330033序號(hào)為6的形狀數(shù)舉例：

序號(hào)6鏈碼：033211首差：330330形狀：033033序號(hào)6鏈碼：003221首差：303303形狀：033033形狀數(shù)與方向無關(guān)序號(hào)為8的形狀數(shù)舉例：

序號(hào)8鏈碼：03032211首差：33133030形狀：03033133序號(hào)8鏈碼：00332211首差：30303030形狀：03030303序號(hào)8鏈碼：00323211首差：30331330形狀：03033133（3）存在問題 雖然鏈碼的首差是不依賴于旋轉(zhuǎn)的，但一般情況下邊界的編碼依賴于網(wǎng)格的方向。（4）改進(jìn)措施（規(guī)整化網(wǎng)格方向） 大多數(shù)情況下，將鏈碼網(wǎng)格與基本矩形對(duì)齊，即可得到一個(gè)唯一的形狀數(shù)。規(guī)整化網(wǎng)格方向的一種算法如下：A、首先確定形狀數(shù)的序號(hào)n；B、在序號(hào)為n的矩形形狀數(shù)中，找出一個(gè)與給定形狀的基本矩形的離心率最接近的形狀數(shù)的矩形。C、然后再用這個(gè)矩形與基本矩形對(duì)齊，構(gòu)造網(wǎng)格。D、用獲得鏈碼的方法得到鏈碼；E、再得到循環(huán)首差；F、首差中的最小循環(huán)數(shù)即為形狀數(shù)。例如:如果n=12，所有序號(hào)為12的矩形（即周長為12）為2*4，3*3，1*5。如果2*4矩形的離心率最接近于給定邊界的基本矩形的離心率，我們建立一個(gè)2*4的網(wǎng)格。鏈碼：000033222121首差：300030300313形狀：00030300313301233傅里葉描繪子（1）基本方法：A、將XY平面中的曲線段轉(zhuǎn)化為復(fù)平面上的1個(gè)序列，從而用復(fù)數(shù)的形式來表示給定邊界上每個(gè)點(diǎn)（x,y）。對(duì)1個(gè)由N個(gè)點(diǎn)組成的封閉邊界，從任一點(diǎn)開始繞邊界1周就得到1個(gè)復(fù)數(shù)序列：

s(k)=x(k)+jy(k)

y0y1xx(k)=xky(k)=ykB、進(jìn)行離散傅立葉變換

N-1a(u)=1/N∑s(k)exp(-j2

uk/N)u=0,1,…,N-1

u=0

N-1s(k)=∑a(u)exp(j2

uk/N) k=0,1,…,N-1

u=0系數(shù)a(u)被稱為邊界的傅立葉描述子C、選取整數(shù)M

N-1，進(jìn)行逆傅立葉變換（重構(gòu)）

M-1s’(k)=∑a(u)exp(j2

uk/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ù)。（2）M的選取與描述符的關(guān)系在上述方法中，相當(dāng)于對(duì)于u>M-1的部分舍去不予計(jì)算。由于傅立葉變換中高頻部分對(duì)應(yīng)于圖像的細(xì)節(jié)描述，因此M取得越小，細(xì)節(jié)部分丟失得越多。M=4M=61M=62N=64思考題：如何進(jìn)行空間曲線平滑？（3）使用價(jià)值A(chǔ)、較少的傅立葉描述子（如4個(gè)），就可以獲取邊界本質(zhì)的整體輪廓；B、這些帶有邊界信息的描述子，可以用來區(qū)分明顯不同的邊界。（4）優(yōu)點(diǎn)A、使用復(fù)數(shù)作為描述符，對(duì)于旋轉(zhuǎn)、平移、放縮等操作和起始點(diǎn)的選取不十分敏感。B、幾何變換的描述子可通過對(duì)函數(shù)作簡單變換來獲得。幾何變換傅立葉描述子原形a(u)旋轉(zhuǎn)a(u)=a(u)ej

平移a(u)=a(u)+

xy(u)放縮a(u)=

a(u)起點(diǎn)a(u)=a(u)e-j2k0u/N4統(tǒng)計(jì)矩（1）基本思想：將描述形狀的任務(wù)減少至描述一個(gè)一維函數(shù)，邊界段和特征的形狀可以用矩量來量化地描述。（2）統(tǒng)計(jì)矩的定義A、把邊界當(dāng)作直方圖函數(shù)：g(r)

B、定義：

K-1

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

i=0K-1

其中m=∑rig(ri)

i=1這里L(fēng)是邊界上點(diǎn)的數(shù)目,

n(r)是邊界的矩量（3）矩量的優(yōu)點(diǎn)A、實(shí)現(xiàn)是直接的；B、附帶了一種關(guān)于邊界形狀的“物理”解釋C、對(duì)于旋轉(zhuǎn)的不敏感性D、為了使大小比例不敏感，可以通過伸縮r的范圍來將大小正則化。

6.3區(qū)域描繪子1一些簡單的描繪子

（1）區(qū)域面積：區(qū)域中像素的數(shù)目。

（2）區(qū)域周長：區(qū)域邊界的長度。

（3）致密度：(周長)2/面積。

（4）其他簡單描繪子如最大值、最小值、中值、均值、重心、方差等。實(shí)例：利用面積描繪子從圖像中提取信息2拓?fù)涿枥L子

（1）拓?fù)湫再|(zhì)研究一種圖像在沒有撕裂和連接的情況下（橡皮伸展變形），不受任何變形影響的性質(zhì)。（2）孔洞數(shù)H、連通分量的數(shù)目C、歐拉數(shù)EE=C-H（3）拓?fù)渚W(wǎng)絡(luò)與歐拉數(shù)的關(guān)系