四近鄰圖像的鏈碼轉(zhuǎn)換算法

四近鄰圖像的鏈碼轉(zhuǎn)換算法

1實(shí)驗(yàn)結(jié)果的提出數(shù)字圖像處理是計(jì)算機(jī)科學(xué)的一個(gè)重要理論領(lǐng)域。計(jì)算機(jī)圖形軟件的一項(xiàng)關(guān)鍵技術(shù)。這與其他學(xué)科密切相關(guān)。計(jì)算機(jī)處理的圖像包括灰色圖像、彩色圖像和兩個(gè)值圖像。其中兩個(gè)值圖像相對(duì)簡(jiǎn)單且重要。H.Freeman創(chuàng)造了二值圖像的鏈碼表示方法.鏈碼的優(yōu)點(diǎn)是十分明顯的,它把二維圖像的存儲(chǔ)和處理變?yōu)橐痪S鏈上的問題.對(duì)于大尺度的圖像,鏈碼可以大幅度地節(jié)省存儲(chǔ)空間并提高處理速度.在Freeman之后已提出了多種鏈碼方案.Bribiesca則對(duì)頂點(diǎn)鏈碼做了系統(tǒng)的研究并做了推廣.既然不同的鏈碼表示的是同一個(gè)目標(biāo)圖像,它們之間是等價(jià)的,則應(yīng)該可以相互轉(zhuǎn)換.如果掌握了各種鏈之間的轉(zhuǎn)換關(guān)系,那么從數(shù)字圖像獲得一種鏈碼,也就能得到其他的鏈碼.另外,圖像的每一種鏈碼都有它自己的優(yōu)點(diǎn)和應(yīng)用背景.例如,由Freeman鏈碼可以便捷地計(jì)算圖像的一階矩、二階矩等,從頂點(diǎn)鏈碼可以獲得圖像區(qū)域的邊界周長(zhǎng)、圖像的面積、圖像區(qū)域密集度和體態(tài)比,利用頂點(diǎn)鏈碼可以自動(dòng)探測(cè)掃描文件的傾斜角度.于是有了鏈碼之間的轉(zhuǎn)換關(guān)系,鏈碼獲得的每一個(gè)有用結(jié)果都可以直接共享.因此有必要仔細(xì)分析和研究鏈碼之間的關(guān)系.就作者所知,石秀和施澤生的論文實(shí)現(xiàn)了從Freeman鏈碼到頂點(diǎn)鏈碼的轉(zhuǎn)化,首先提出并研究圖像編碼之間轉(zhuǎn)化的這一具有實(shí)際意義的問題.從Freeman鏈碼到頂點(diǎn)鏈碼的轉(zhuǎn)化固然必要,借此可以利用頂點(diǎn)鏈碼的各種優(yōu)良性質(zhì).不過Freeman鏈碼也有許多好的性質(zhì),例如Freeman鏈碼上可以直接利用GREGORYY.TANG的離散格林定理,高效地計(jì)算圖形的矩.從理論的完整性的角度考慮,也有必要建立從頂點(diǎn)鏈碼到Freeman鏈碼的變換.另外,如同下文將具體解釋的,Freeman定義的鏈碼和E.Bribiesca介紹的鏈碼之間是有區(qū)別的,我們權(quán)且把它稱為邊界鏈碼.本文將較系統(tǒng)研究矩形點(diǎn)陣中鏈碼間的相互轉(zhuǎn)化.我們找到了頂點(diǎn)鏈碼與邊界鏈碼之間的相互轉(zhuǎn)換和Freeman鏈碼與頂點(diǎn)鏈碼之間的相互轉(zhuǎn)換算法,因此可以在這些鏈碼之間自由變換.最后給出了用邊界標(biāo)定自動(dòng)機(jī)從圖像獲得頂點(diǎn)鏈碼,通過前面提到的各種鏈碼之間的轉(zhuǎn)換,即可以得到各種鏈碼,并給出了實(shí)驗(yàn)結(jié)果.2邊界鏈碼的標(biāo)記在介紹正方形點(diǎn)陣上的鏈碼前,我們先要明確邊界像素的概念.和背景以八鄰接意義上相鄰的像素是四連通區(qū)域的邊界像素.如圖1所示(見下頁),用0,1,2,3四個(gè)代碼表示四個(gè)方向.從圖像邊界上的任一像素點(diǎn)開始,沿某一方向(本文中皆采用順時(shí)針方向)依次連接邊界像素,并用碼記錄鏈的行走方向,直到回到起始點(diǎn)為止,就構(gòu)成了圖像的Freeman鏈碼.因此,圖像Freeman鏈碼可以表示為{(x0F,y0F)a0a1a2…al-1},(x0F,y0F)為圖像邊界上的起始像素點(diǎn)坐標(biāo),ai∈{0,1,2,3}是圖像的四方位代碼,l為鏈的長(zhǎng).如圖2所示的圖像,從點(diǎn)Q出發(fā)的Freeman鏈碼表示為{(x0F,y0F)12212010101330001303232232}.(x0F,y0F)是起始點(diǎn)Q的坐標(biāo).Bribiesca采用邊界像素的外邊界來表記圖形,并對(duì)鏈碼做了系統(tǒng)的研究.從邊界像素的某一頂點(diǎn)出發(fā),沿著圖像邊界像素的邊按一定的方向行走一周,記錄邊上的行走方向,構(gòu)成一個(gè)有序鏈,加上起始點(diǎn)坐標(biāo),圖像的邊界也被唯一地確定下來.Bribiesca把這種標(biāo)記圖形的新的鏈碼,也稱作Freeman鏈碼.其實(shí)兩種鏈碼的差別是十分明顯的,有必要做出區(qū)分.因此我們把Bribiesca提出的這種鏈碼稱作邊界鏈碼.邊界鏈碼的表示為{(x0,y0)b0b1b2…bm-1},其中(x0,y0)是邊界鏈碼的起始點(diǎn)坐標(biāo),bi∈{0,1,2,3}.如圖2,圖像的邊界鏈碼表示為{(x0,y0)12212101010133001030332322322}.(x0,y0)為圖像邊界起始點(diǎn)P的坐標(biāo).論文中考慮的就是這種鏈.因此給出的是一種從邊界鏈碼到頂點(diǎn)鏈碼的方法.Bribiesca還提出了用邊界像素的頂點(diǎn)來標(biāo)記圖像的方法.對(duì)于正四邊形點(diǎn)陣上的圖像,可以有三種不同性質(zhì)的頂點(diǎn),如圖3所示,分別用代碼1,2,3來標(biāo)記.沿著圖像邊界像素的頂點(diǎn)行走一周,依次記錄圖像邊界像素頂點(diǎn)的代碼,就得到頂點(diǎn)鏈碼,圖像的邊界也被唯一地確定下來.圖像頂點(diǎn)鏈碼的表示為:{(x0,y0)/→c/c0c1?cn-1},其中(x0,y0)是頂點(diǎn)鏈碼的起始點(diǎn),→c為初始行走方向,ci∈{1,2,3}.如圖4所示的圖像的頂點(diǎn)鏈碼表示為:{(x0,y0)/1/132131131313112323113121312312}.(x0,y0)是圖像邊界像素的頂點(diǎn)P的坐標(biāo),初始行走方向?yàn)?.3實(shí)現(xiàn)核心鏈碼和邊界鏈碼之間的相互轉(zhuǎn)換本節(jié)我們考慮鏈碼之間的相互轉(zhuǎn)換.我們首先實(shí)現(xiàn)頂點(diǎn)鏈碼和邊界鏈碼之間的相互轉(zhuǎn)換,然后研究頂點(diǎn)鏈碼和Freeman鏈碼之間的相互轉(zhuǎn)換.這樣就可以在這三種鏈碼之間自由變換.3.1邊界鏈碼-點(diǎn)對(duì)點(diǎn)鏈碼的轉(zhuǎn)化假設(shè)圖像的邊界鏈碼為{(x0,y0)b0b1b2…bl-1},當(dāng)bi=bi-1時(shí),其經(jīng)過的頂點(diǎn)的代碼是2,當(dāng)邊界鏈碼的變化為,0→3,3→2,2→1,1→0則經(jīng)過的頂點(diǎn)的代碼為1,當(dāng)邊界鏈碼的變化為3→0,2→3,1→2,0→1,則經(jīng)過的頂點(diǎn)的代碼為3.我們定義邊界鏈碼-頂點(diǎn)鏈碼的轉(zhuǎn)化函數(shù)C(bi-1,bi),其函數(shù)關(guān)系見表1.設(shè)頂點(diǎn)鏈碼的起始點(diǎn)坐標(biāo)為(x0,y0),初始方向?yàn)閎0,由上面定義的轉(zhuǎn)化函數(shù),我們可以得到圖像的頂點(diǎn)鏈碼為{(x0,y0)/→c/c0c1?cl-1},其中→c=b0?ci=C(bi-1,bi)?i=0,?,l-1,當(dāng)i=0時(shí),bi-1=bl-1.3.2分配規(guī)則設(shè)圖像邊界的頂點(diǎn)鏈碼為{(x0,y0)/→c/c0c1?cl-1}.假設(shè)b0=→c,沿著邊界行走時(shí),當(dāng)經(jīng)過像素的頂點(diǎn)的鏈碼為1或3時(shí),鏈改變方向,當(dāng)經(jīng)過像素頂點(diǎn)的鏈碼為2時(shí),鏈不改變方向.當(dāng)經(jīng)過的頂點(diǎn)鏈碼為1時(shí),鏈方向的變化規(guī)則為1→0,0→3,3→2,2→1;當(dāng)經(jīng)過的頂點(diǎn)鏈碼為3時(shí),鏈方向的變化規(guī)則為0→1,3→0,2→3,1→2.根據(jù)以上的分析,我們得到從頂點(diǎn)鏈碼到邊界鏈碼的轉(zhuǎn)換規(guī)則:b0=→c;當(dāng)ci=2時(shí),bi=bi-1;當(dāng)ci=1時(shí),bi=(bi-1+3)mod4;當(dāng)ci=3時(shí),bi=(bi-1+1)mod4;這里mod是模運(yùn)算.由上面的轉(zhuǎn)換規(guī)則,取邊界鏈碼起始點(diǎn)的坐標(biāo)為(x0,y0),就獲得圖像的邊界鏈碼為{(x0,y0)b0b1b2…bl-1}.3.3b從結(jié)合點(diǎn)鏈碼到也碼到頂鏈碼設(shè)圖像的Freeman鏈碼為{(x0F,y0F)a0a1a2…al-1}.因?yàn)轫旤c(diǎn)鏈碼與Freeman鏈碼行走的軌跡不同,所以Freeman鏈碼的代碼數(shù)與頂點(diǎn)鏈碼的代碼數(shù)不相同.使代碼數(shù)發(fā)生變化的邊界圖形有三種,這些子鏈在頂點(diǎn)鏈碼中的表示分別為12a1(a≥1),32b3(b≥0)和11,其中2a表示連續(xù)a個(gè)編碼2.將圖像中出現(xiàn)這幾種子鏈的部分提取出來,如圖6所示.當(dāng)子鏈為12a1或11時(shí),如圖5(a)和(b),Freeman鏈碼比頂點(diǎn)鏈碼少1個(gè)編碼2,當(dāng)子鏈為32b3時(shí),如圖5(c),Freeman鏈碼比頂點(diǎn)鏈碼多1個(gè)編碼2.下面分三步實(shí)現(xiàn)從Freeman鏈碼到頂點(diǎn)鏈碼的轉(zhuǎn)換.第1步,確定頂點(diǎn)鏈碼的起始點(diǎn)坐標(biāo)和初始行走方向.假設(shè)頂點(diǎn)鏈碼的初始行走方向?yàn)椤鷆=a0,起始點(diǎn)坐標(biāo)為(x0,y0).起始點(diǎn)坐標(biāo)可由以下公式計(jì)算:當(dāng)a0=0時(shí),x0=x0F-0.5,y0=y0F-0.5;當(dāng)a0=1時(shí),x0=x0F-0.5,y0=y0F+0.5;當(dāng)a0=2時(shí),x0=x0F+0.5,y0=y0F+0.5;當(dāng)a0=3時(shí),x0=x0F+0.5,y0=y0F-0.5.第2步,引進(jìn)偽頂點(diǎn)鏈碼和偽頂點(diǎn)鏈碼轉(zhuǎn)化函數(shù)D(ai-1,ai),把四方向Freeman鏈碼轉(zhuǎn)化為偽頂點(diǎn)鏈碼.D(ai-1,ai)的映射關(guān)系見表2.設(shè)得到的偽頂點(diǎn)鏈碼序列為e0e1e2…en-1,其中ei=D(ai-1,ai)∈{1,2,3,4}.第3步,把第2步得到的偽頂點(diǎn)鏈碼轉(zhuǎn)換為頂點(diǎn)鏈碼.掃描偽頂點(diǎn)鏈碼,對(duì)12a1(a≥0)、32b3(b≥1)這兩種子鏈做如下的替換:12a1?12a+1142a1?4a+1112a4?12a+14032b3?32b-13然后再把代碼4替換為11.加上第1步得到的起始點(diǎn)坐標(biāo)和初始行走方向,就得到了圖像的頂點(diǎn)鏈碼.3.4新鏈碼的生成設(shè)圖像的頂點(diǎn)鏈碼為{(x0,y0)/→c/c0c2?cn-1},設(shè)Freeman鏈碼的起始點(diǎn)坐標(biāo)為(x0F,y0F).算法也有分三步.第1步,(x0F,y0F)的值由以下的公式計(jì)算:當(dāng)→c=0時(shí),x0F=x0+0.5,y0F=y0+0.5;當(dāng)→c=1時(shí),x0F=x0+0.5,y0F=y0-0.5;當(dāng)→c=2時(shí),x0F=x0-0.5,y0F=y0-0.5;當(dāng)→c=3時(shí),x0F=x0-0.5,y0F=y0+0.5.第2步,掃描頂點(diǎn)鏈碼,先用代碼0標(biāo)記11子鏈,對(duì)12a1(a≥1)、32b3(b≥0)這兩種子鏈做如下的替換:12a1?12a-1102a1?02a-1112a0?12a-1032b3?32b+13假設(shè)經(jīng)替換后的新鏈碼序列為e0e1e2…es,為新鏈碼定義初始方向?yàn)椤鷈如下:當(dāng)e0≠0或e0=0且c0=cs-1=1時(shí),e→=c→;當(dāng)e0=0且c0=c1=1時(shí),e→=(c→+3)mod4;第3步,對(duì)第2步得到的代碼e0e1e2…es作替換處理,規(guī)則如下:d0=e→;當(dāng)ei=2時(shí),di=di-1;當(dāng)ei=1時(shí),di=(di-1+3)mod4;當(dāng)ei=3時(shí),di=(di-1+1)mod4;當(dāng)ei=0時(shí),di→dˉi-1.其中bˉ是與b反方向鏈的代碼,如0ˉ=2.這樣我們就得到了圖像的Freeman鏈碼:{(x0F,y0F)d0d1d2…dt}4三種鏈碼首先利用文獻(xiàn)中定義的邊界標(biāo)定自動(dòng)機(jī)獲得圖像的頂點(diǎn)鏈碼.然后再由本文提供的轉(zhuǎn)換算法,就獲得了圖像的邊界鏈碼和Freeman鏈碼.如圖6所示.我們通過邊界標(biāo)定自動(dòng)機(jī)和轉(zhuǎn)換算法獲得圖像L的三種鏈碼分別為:頂點(diǎn)鏈碼:邊界鏈碼:Freeman鏈碼:5圖像邊緣鏈碼和邊界鏈碼之間的轉(zhuǎn)換圖像的Freeman鏈碼和頂