魏 巍，段曉東，劉勇奎，郭 晨

(1.大連民族大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，遼寧 大連 116600； 2.大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026； 3.大連民族大學(xué) 大連市民族文化數(shù)字技術(shù)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116600)

一種新壓縮頂點(diǎn)鏈碼

魏 巍1,2,3，段曉東1,3*，劉勇奎1，郭 晨2

(1.大連民族大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，遼寧 大連 116600； 2.大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026； 3.大連民族大學(xué) 大連市民族文化數(shù)字技術(shù)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116600)

(*通信作者電子郵箱duanxd@dlnu.edu.cn)

鏈碼是一種以較少的數(shù)據(jù)存儲表示線條、曲線和區(qū)域邊界的編碼技術(shù)。為進(jìn)一步提高鏈碼的壓縮效率，提出了一種新的壓縮頂點(diǎn)鏈碼：改進(jìn)的正交3方向頂點(diǎn)鏈碼(IO3DVCC)。IO3DVCC將頂點(diǎn)鏈碼(VCC)的統(tǒng)計特征與正交3方向鏈碼(3OT)的方向特征相結(jié)合，共設(shè)5個碼值。碼值1將VCC中的1、3組合和3、1組合歸并表示，碼值2與VCC的對應(yīng)碼值表達(dá)相同，碼值3與3OT中的碼值2表達(dá)相同，碼值4和碼值5分別對應(yīng)2個連續(xù)的新鏈碼碼值1和8個連續(xù)的VCC碼值2。新鏈碼基于Huffman編碼，為不定長編碼。針對100幅圖像的輪廓邊界，統(tǒng)計并計算了IO3DVCC與改進(jìn)的相對8方向Freeman鏈碼(ERD8FCC)、基于算數(shù)編碼的變長相對四方向Freeman鏈碼(AVRF4)、基于算數(shù)編碼的正交3方向鏈碼(Arith_3OT)、壓縮VCC(CVCC)和改進(jìn)的CVCC(ICVCC)6種鏈碼各碼值出現(xiàn)的概率、平均碼值表達(dá)能力、平均碼長和鏈碼效率。實(shí)驗(yàn)結(jié)果表明，IO3DVCC效率最高。針對隨機(jī)選擇的20幅輪廓邊界圖像，統(tǒng)計并計算了IO3DVCC、Arith_3OT和ICVCC3種鏈碼表達(dá)的總碼數(shù)、二進(jìn)制總位數(shù)，以及相對于8方向Freeman鏈碼的壓縮比率。實(shí)驗(yàn)結(jié)果表明，IO3DVCC的壓縮效果最好。

鏈碼；Huffman編碼；圖像邊界；鏈碼效率；壓縮

0 引言

鏈碼是一種表示線條、曲線和圖像邊界區(qū)域的常用編碼技術(shù)，它由一系列固定方向和長度的小直線段組成。在表示圖像邊界輪廓時，按照定義好的編碼規(guī)則對輪廓上的像素點(diǎn)進(jìn)行表達(dá)和存儲。由于鏈碼編碼簡單，操作方便，因此在圖像識別等領(lǐng)域應(yīng)用廣泛。

最直觀的鏈碼是Freeman[1]在1961年提出的8方向Freeman鏈碼(8-Direction Freeman Chain Code, 8DFCC)和4方向Freeman鏈碼(4-Direction Freeman Chain Code, 4DFCC)。8DFCC基于邊界像素8連通的原理，碼值由Σ(F8)={σ|0,1,2,3,4,5,6,7}組成，其中每一碼值σ∈Σ表示與X軸正向呈45°×σ角，如圖1所示。4DFCC基于邊界像素4連通原理，碼值由Σ(F4)={σ|0,1,2,3}組成，其中每一碼值σ∈Σ表示與X軸正向呈90°×σ角，如圖2所示。Freeman鏈碼以圖像邊界輪廓的方向?yàn)橐罁?jù)，因此8DFCC和4DFCC均具有明顯的方向性。

圖1 8DFCC示例

圖2 4DFCC示例

1999年，Bribiesca[2]提出了目前使用非常廣泛的頂點(diǎn)鏈碼(VertexChainCode,VCC)。與Freeman鏈碼不同，VCC是通過標(biāo)記圖像邊界輪廓像素的頂點(diǎn)數(shù)目表示的。VCC的碼值由Σ(VCC)={σ|1,2,3}組成，碼值1表示單獨(dú)的像素頂點(diǎn)，通常在邊界像素處出現(xiàn)；碼值2表示連續(xù)的兩個像素頂點(diǎn)，用來表示連續(xù)的像素；碼值3表示將有3個像素頂點(diǎn)聚集在一起，常在邊界像素方向改變處出現(xiàn)，如圖3所示。

圖3 VCC示例

正交3方向鏈碼(OrThogonal3-directionchaincode, 3OT)[3]的碼值由Σ(3OT)={σ|0,1,2}組成。其中：碼值0表示后繼鏈碼與前續(xù)鏈碼碼值方向相同；碼值1表示鏈碼前進(jìn)方向發(fā)生改變，同時與其前續(xù)相鄰的鏈碼碼值改變的變化方向不同；碼值2表示鏈碼前進(jìn)方向發(fā)生改變，但與其前續(xù)相鄰的鏈碼碼值改變的變化方向相同。如圖4所示。

圖4 3OT示例

由圖1、圖2和圖4可以看出，8DFCC、4DFCC和3OT鏈碼在表示圖像邊界輪廓時具有明顯的方向性，而由圖3可以發(fā)現(xiàn)VCC是通過統(tǒng)計頂點(diǎn)的個數(shù)來組成鏈碼的。這些鏈碼對圖像輪廓的幾何形狀均有很好的表示，但在存儲時，往往受限于碼值長度，導(dǎo)致鏈碼存儲占據(jù)較大的空間。因此，在后續(xù)研究中提出了對這些鏈碼的改進(jìn)方案。每種新提出的鏈碼均會在一定程度上提高碼值平均表達(dá)能力，降低鏈碼平均長度，提高鏈碼整體壓縮效率。本文將VCC的統(tǒng)計特征與正交3方向鏈碼的方向特征相結(jié)合，針對VCC提出了一種新的壓縮鏈碼。進(jìn)一步，對所提的新鏈碼進(jìn)行改進(jìn)，大幅提高了鏈碼的壓縮效率。

1 鏈碼的改進(jìn)

1.1 改進(jìn)的Freeman鏈碼

2001年，劉勇奎[4]基于8DFCC提出了角度差Freeman鏈碼(AngleDifferencesFreemanChainCode,ADFCC)。ADFCC的碼值由Σ(ADFCC)={σ|0,1,2,3,4,5,6,7}組成，分別表示碼值的角度差為0°、±45°、±90°、±135°和 180°。ADFCC應(yīng)用Huffman編碼，對圖像中的數(shù)字曲線和邊界輪廓進(jìn)行了統(tǒng)計，對邊界中最常出現(xiàn)的像素相鄰情況分配較少的二進(jìn)制位表示，從而相對8DFCC壓縮比率有很大提高。

2007年，Zahir等[5]基于8DFCC和ADFCC，提出了改進(jìn)的相對8方向Freeman鏈碼(EnhancedRelative8-DirectionFreemanChainCode,ERD8FCC)。ERD8FCC的碼值由Σ(ERD8FCC)={σ|F,FL,L,BL,B,BR,R,FR,X,Y}組成，其中每一碼值均表示當(dāng)前像素相對于其前續(xù)像素的位置關(guān)系：F表示當(dāng)前像素位于前續(xù)像素的前方(Front)，F(xiàn)L表示左前方(FrontLeft)，L表示左方(Left)，BL表示左后方(BackLeft)，B表示后方(Back)，BR表示右后方(BackRight)，R表示右方(Right)，F(xiàn)R表示右前方(FrontRight)，X表示連續(xù)的10個F，Y表示連續(xù)的5個F。同ADFCC類似，ERD8FCC也通過Huffman編碼得到不等長的碼值表達(dá)，相比于ADFCC，對圖像中連續(xù)的碼值合并為一個新的碼值。在圖像出現(xiàn)連續(xù)F碼值較多的情況下，能很好地降低F碼值出現(xiàn)的概率，同時增加X、Y碼值出現(xiàn)的概率。由于X、Y碼值的二進(jìn)制長度小于對應(yīng)連續(xù)F碼值所需的二進(jìn)制長度，因此能夠減少了鏈碼二進(jìn)制總長度，提高壓縮效果。

2013年，李靈華等[6]基于4DFCC提出了基于算數(shù)編碼的變長相對四方向Freeman鏈碼(ArithmeticencodingVariable-lengthRelative4-directionFreemanchaincode,AVRF4)。AVRF4的碼值由Σ(AVRF4)={σ|0,1,2,3,4}組成，相比4DFCC新增了碼值4。AVRF4變4DFCC的絕對方向?yàn)橄鄬Ψ较?，碼值0表示后續(xù)像素與當(dāng)前像素方向相同，碼值1表示后續(xù)像素相對當(dāng)前像素方向向左改變，碼值2表示方向向后改變，碼值3表示向右改變，碼值4表示8個連續(xù)的碼值0組合。

1.2 改進(jìn)的3OT鏈碼

2009年，Sánchez-Cruz等[7]基于3OT鏈碼提出了基于算數(shù)編碼的正交3方向鏈碼(Arithmeticcodingappliedto3OTchaincode,Arith_3OT)。Arith_3OT的碼值由Σ(Arith_3OT)={σ|0,1,2,3,4,5}組成，碼值0、1、2與3OT的相同，新增的碼值3、4、5是基于碼值方向的統(tǒng)計，碼值3與碼值4分別表示5個連續(xù)的碼值0和1，碼值5表示連續(xù)的3OT碼值0110組合。

1.3 改進(jìn)的VCC鏈碼

2007年，Liu等[8]對VCC進(jìn)行改進(jìn)，提出了壓縮VCC(CompressedVCC,CVCC)。CVCC的碼值由Σ(CVCC)={σ|1,2,3,4,5}組成，基于Huffman編碼對VCC定義了碼值進(jìn)行了新增和改進(jìn)，其中碼值1對應(yīng)VCC的碼值2，碼值2對應(yīng)VCC的碼值1、3組合，碼值3對應(yīng)3、1組合，碼值4和5分別對應(yīng)VCC的碼值1和3。實(shí)驗(yàn)表明，CVCC的壓縮比率和鏈碼效率遠(yuǎn)遠(yuǎn)高于VCC。

2014年，魏巍等[9]對壓縮鏈碼CVCC進(jìn)一步改進(jìn)，得到了改進(jìn)的CVCC(ImprovedCVCC,ICVCC)。ICVCC的碼值由Σ(ICVCC)={σ|1,2,3,4,5,6}組成，鏈碼在CVCC的基礎(chǔ)上，新增了一個碼值6用來表示CVCC中連續(xù)的9個碼值2的組合。ICVCC與CVCC的對應(yīng)關(guān)系如表1所示。實(shí)驗(yàn)表明，其鏈碼效率和壓縮比率要高于壓縮的VCC的。

表1 ICVCC與VCC的對應(yīng)關(guān)系

除了對常用鏈碼進(jìn)行改進(jìn)，研究者嘗試應(yīng)用多種方式提高鏈碼的壓縮效率。2015年，?alik等[10]提出一種新的無損壓縮鏈碼方法：基于游程編碼、動態(tài)窗口等壓縮方式對鏈碼二進(jìn)制進(jìn)行壓縮。2016年，?alik等[11]又提出采用基于Move-To-Front變換(Move-To-FrontTransformation,MTFT)和Burrows-Wheeler變換(Burrows-WheelerTransform,BWT)等字符變換技術(shù)，結(jié)合游程編碼方法對鏈碼進(jìn)行壓縮，取得了較好的壓縮效果。

2 新壓縮VCC

2.1 正交3方向VCC

正交3方向鏈碼及其改進(jìn)鏈碼的共同特點(diǎn)是具有明確的方向性。VCC及其優(yōu)化鏈碼雖沒有明顯的方向性，但通過逐一統(tǒng)計邊界像素的頂點(diǎn)個數(shù)完成編碼過程。本文將3OT鏈碼的方向特征與VCC的像素統(tǒng)計特征相結(jié)合，提出了一種新的鏈碼：正交3方向VCC(Orthogonal3-DirectionVCC,O3DVCC)。

O3DVCC共3個碼值：碼值1表示當(dāng)前鏈碼與之前最近發(fā)生方向改變的碼值對應(yīng)的方向不同；碼值2同VCC的碼值2，表示方向沒有改變；碼值3表示當(dāng)前鏈碼與之前最近發(fā)生方向改變的碼值對應(yīng)的方向相同。O3DVCC需要一個參考方向，通常將遍歷的第1個像素方向定義為參考方向，后續(xù)碼值均相對于前續(xù)的碼值進(jìn)行定義。圖5給出了用O3DVCC表示圖像邊界的示意，其中位于像素格子內(nèi)的鏈碼表示是VCC，位于像素格子外圍帶方向箭頭的表示為O3DVCC。

O3DVCC將鏈碼的方向特征與統(tǒng)計特征進(jìn)行了融合，其中方向特征是相對的，統(tǒng)計特征是絕對的。由圖5不難發(fā)現(xiàn)，應(yīng)用VCC表示的鏈碼為1313131時，對應(yīng)的O3DVCC鏈碼表示為1111111；應(yīng)用VCC表示的鏈碼為3131時，對應(yīng)的O3DVCC鏈碼也表示為1111；VCC中的碼值2與O3DVCC中的碼值2保持一致。可以看出，O3DVCC將VCC中的碼值1、3組合和3、1組合統(tǒng)一歸并為帶有方向性質(zhì)的碼值1。這為進(jìn)一步壓縮O3DVCC鏈碼奠定了基礎(chǔ)。

圖5 O3DVCC示例

若以VCC為基準(zhǔn)鏈碼，其轉(zhuǎn)換為O3DVCC的算法如下：

/*數(shù)組V[]存放VCC碼值*/ /*數(shù)組N[]存放O3DVCC碼值*/Vertex2New(V[]) { /*reference_section為參考段碼值*/reference_section=0; /*i為O3DVCC碼長*/i=1;WhileV[i]NotNullDo{If(V[i] == 2‖reference_section==0)Then{N[i]==V[i];If(V[i]～=2)Thenreference_section=V[i];

}

Else

{If(reference_section==V[i] )ThenN[i]=3;

ElseN[i]=1;reference_section=V[i];

}

i=i+1;

}

}

同理，O3DVCC也可以轉(zhuǎn)換為VCC，其算法如下：

/*數(shù)組V[]存放VCC碼值*/ /*數(shù)組O[]存放O3DVCC碼值*/O2Vertex(O[]) {i=1;reference_section=0; /*reference_section為參考段碼值*/WhileO[i]NotNullDo{If(O[i] == 2‖reference_section== 0)Then{V[i]==O[i];

If(V[i]～=2)Thenreference_section=V[i];

}

Else

{If(reference_section+V[i]== 4 )Then{N[i]=1;reference_section=1;}

Else{N[i]=3;reference_section=3;}

}

i=i+1;

}

}

本文應(yīng)用O3DVCC對100幅圖像進(jìn)行了概率統(tǒng)計，并基于Huffman編碼計算了O3DVCC每一碼值的二進(jìn)制編碼，如表2所示。

根據(jù)表2，可知碼值1和碼值2的概率較為近似，遠(yuǎn)遠(yuǎn)超過了碼值3出現(xiàn)的概率。這意味著圖像輪廓中出現(xiàn)相對方向不同向變化的概率和方向不發(fā)生變化的概率要遠(yuǎn)大于出現(xiàn)相對方向同向變化的概率?；谠摻y(tǒng)計，可以對O3DVCC鏈碼進(jìn)一步改進(jìn)。

表2 O3DVCC碼值概率與二進(jìn)制編碼

2.2 改進(jìn)的O3DVCC

由于O3DVCC中碼值1和碼值2占有很大比例，因此對存在連續(xù)的碼值1和連續(xù)的碼值2進(jìn)行改進(jìn)，必定能夠提高鏈碼的壓縮效率。在O3DVCC的基礎(chǔ)上，新增了2個碼值，分別表示M個碼值1和N個碼值2，定義該鏈碼為改進(jìn)的O3DVCC(ImprovedO3DVCC,IO3DVCC)。對100幅圖像的邊界輪廓進(jìn)行了統(tǒng)計，并基于Huffman編碼為M=2，3，…，10且N=2，3，…，10共81種組合中每一組合的鏈碼進(jìn)行了二進(jìn)制碼值編碼，同時計算了每一組合的鏈碼平均表達(dá)能力，鏈碼平均碼長和鏈碼的效率，如表3所示。

表3 IO3DVCC不同M、N組合對應(yīng)的效率統(tǒng)計

由表3可知，當(dāng)M=2、N=8時鏈碼的效率是最高的，為0.932 3。因此，定義IO3DVCC為5個碼值，前3個碼值與O3DVCC一致，碼值4定義為連續(xù)2個碼值1，碼值5定義為連續(xù)8個碼值2。表4給出了IO3DVCC與O3DVCC的對應(yīng)關(guān)系以及其在100幅測試圖像中出現(xiàn)的概率和具體的二進(jìn)制編碼。

再次，形成新市場。一方面，要通過促進(jìn)傳統(tǒng)五大需求“吃穿住行用”升級，來形成新市場；另一方面，要通過培育新五大需求“學(xué)樂康安美”（學(xué)習(xí)需求、快樂需求、健康需求、安全需求、美麗需求），來形成新市場。

表4 IO3DVCC與O3DVCC的對應(yīng)關(guān)系

3 新壓縮VCC與其他鏈碼的比較分析

3.1 鏈碼評價的方法

評價鏈碼的主要指標(biāo)是鏈碼效率[12]，其公式可表示為：

e=c/l

(1)

其中：e表示鏈碼的效率；c代表碼值平均表達(dá)能力；l代表平均碼長。

碼值的表達(dá)能力指碼值所能表示的區(qū)域邊界(或數(shù)字曲線)的像素長度的平均值，如圖6所示。

圖6 碼值表達(dá)能力

8DFCC鏈碼中碼值0、2、4、6的表達(dá)能力為1個像素長度；碼值1、3、5、7的表達(dá)能力為2個像素長度。4DFCC和VCC的所有碼值表達(dá)能力均為1個像素長度。

鏈碼的平均表達(dá)能力可表示為：

(2)

其中：ci為鏈碼中某一碼值的表達(dá)能力；pi為該碼值出現(xiàn)的概率。

鏈碼的平均碼值長度，對于定長鏈碼，其鏈碼平均碼長即為表達(dá)每位鏈碼所需的bit。如，8DFCC鏈碼由8個碼值，每個碼值用固定的3個bit進(jìn)行表示，因此其平均碼長為3bit/碼。

(3)

其中：li為鏈碼中某一碼值表達(dá)所占的bit數(shù)；pi為該碼值出現(xiàn)的概率。

3.2 實(shí)驗(yàn)比較與分析

通常，改進(jìn)鏈碼的壓縮效果要好于被改的鏈碼。為了驗(yàn)證IO3DVCC的有效性，本文基于100幅圖像將IO3DVCC的平均表達(dá)能力c，平均鏈碼長度l和鏈碼效率e，與改進(jìn)的8方向Freeman鏈碼ERD8FCC和改進(jìn)的4方向鏈碼AVRF4，改進(jìn)的3OT鏈碼Arith_3OT，以及改進(jìn)的VCC鏈碼CVCC和ICVCC進(jìn)行了比較，并給出了這些鏈碼的碼值出現(xiàn)概率和二進(jìn)制編碼表示，如表5所示。

表5 不同鏈碼的性能對比

由表5可以發(fā)現(xiàn):6種鏈碼中平均表達(dá)能力最強(qiáng)的是Arith_3OT鏈碼，為1.991 5像素長度;其次是ERD8FCC，為1.750 9像素長度;第三是ICVCC鏈碼，為1.543 6像素長度;第四是本文提出的IO3DVCC鏈碼，為1.537 6像素長度;CVCC與AVRF4的平均表達(dá)能力分別為1.308 0像素長度和1.144 8像素長度。

6種鏈碼中，CVCC的平均鏈碼長度最短，為1.567 2/碼，其次是IO3DVCC，為1.649 3/碼，第三是ICVCC為1.780 7/碼，后續(xù)依次是AVRF4為1.923 4/碼，ERD8FCC為2.108 0/碼，Arith_3OT為2.266 5/碼。

在這些鏈碼比較中，效率最高的是本文提出的IO3DVCC，為0.932 3；其次是Arith_3OT，為0.878 7；第三是ICVCC；CVCC和ERD8FCC較為接近，分別是0.834 6和0.830 6；AVRF4最少，為0.595 2。

分析原因，IO3DVCC的平均表達(dá)能力和鏈碼長度對比其他鏈碼雖然并非最優(yōu)，但均排在前列。Arith_3OT的平均表達(dá)能力最強(qiáng)，但其平均鏈碼長度過長，排在6種鏈碼的最后，因而其效率并非最高。ICVCC鏈碼的平均表達(dá)能力和鏈碼長度排名均靠前，因此其效率較高。CVCC的平均鏈碼長度較短，雖然其平均表達(dá)能力不高，但其效率較高。

進(jìn)一步檢驗(yàn)IO3DVCC的壓縮效果，從100幅圖像樣本中隨機(jī)抽取20幅，將IO3DVCC與上述鏈碼效率較高的Arith_3OT和ICVCC以8DFCC為基準(zhǔn)進(jìn)行比較。所選的20幅圖像輪廓邊界如圖7所示。各圖像的尺寸如表6所示。針對這20幅圖像，分別統(tǒng)計這四種鏈碼相對每幅圖像輪廓的總碼數(shù)和所占二進(jìn)制總數(shù)，以及相對于8DFCC的壓縮比率，如表7所示。

圖7 圖像輪廓邊界

圖像尺寸總像素數(shù)圖像尺寸總像素數(shù)寶寶193×17533775路由器300×30090000豹子350×27495900驢147×17024990貝殼211×15031650螃蟹350×23180850茶杯153×15022950酒瓶251×21152961房子662×514340268小轎車375×24993375楓葉343×300102900雨傘422×300126600海賊王200×15030000烏龜454×300136200汽車447×300134100椅子436×330143880警帽221×22048620蘋果220×22048400老鼠275×36199275板凳278×22061160

鏈碼存儲的空間大小與碼值數(shù)和鏈碼的碼值長度相關(guān)。相同碼值數(shù)，碼值長度多的鏈碼勢必要比碼值長度少的更占用空間。表7中，Arith_3OT、ICVCC和IO3DVCC的碼值數(shù)相比8DFCC均有壓縮，其中Arith_3OT的總碼數(shù)最少，其次是ICVCC，而IO3DVCC相對較多。然而，由于Arith_3OT的鏈碼長度均多于ICVCC和IO3DVCC，因此其所占存儲空間并非最少。IO3DVCC的碼值總數(shù)與ICVCC較為接近，但由于其鏈碼長度少于ICVCC和Arith_3OT，因此所占存儲空間最少。

表7 各鏈碼相對圖像輪廓鏈碼的總碼數(shù)與二進(jìn)制總位數(shù)，以及相對于8DFCC的壓縮比率

從鏈碼效率角度分析，鏈碼效率越高，單位像素長度對應(yīng)的碼值表達(dá)能力越強(qiáng)，相對于同一種鏈碼的壓縮比率越高，壓縮效果越明顯。由表7可知，在Arith_3OT、ICVCC和IO3DVCC鏈碼相對于8DFCC的壓縮比率比較中，IO3DVCC的壓縮比率是最明顯的，其次是Arith_3OT，最后是ICVCC，這與表5給出的鏈碼效率是完全一致的。

進(jìn)一步分析，鏈碼IO3DVCC、Arith_3OT、ICVCC均是變長編碼，且都采用了Huffman編碼方式。Arith_3OT將連續(xù)碼值合并生成新碼值，其碼值3、4均是對連續(xù)相同3OT碼值表示，碼值5則是對0110特定的組合進(jìn)行表示，結(jié)果Arith_3OT鏈碼的壓縮效果明顯優(yōu)于3OT。IO3DVCC的碼值4表達(dá)的是連續(xù)2個O3DVCC碼值1，O3DVCC的碼值1又將CVCC的碼值2和碼值3進(jìn)行了歸并表示，其分別對應(yīng)VCC的碼值1、3和3、1組合。IO3DVCC的碼值5表達(dá)的是連續(xù)的8個碼值2，而碼值2又與O3DVCC的碼值2和VCC的碼值2是相同的，這同ICVCC鏈碼的碼值6表示連續(xù)的9個VCC碼值2相似。由此不難發(fā)現(xiàn)，IO3DVCC相對于ICVCC對CVCC進(jìn)一步優(yōu)化。ICVCC重點(diǎn)對CVCC中連續(xù)的碼值2定義了一個新的碼值，IO3DVCC不僅對CVCC連續(xù)的碼值2進(jìn)行了新的定義，還對CVCC的碼值2和碼值3進(jìn)行了歸并表示，因此IO3DVCC的壓縮效果必定優(yōu)于ICVCC和CVCC。這類通過概率統(tǒng)計出連續(xù)相同碼值出現(xiàn)的概率，進(jìn)而通過定義新碼值對這些連續(xù)相同碼值進(jìn)行表示的方法，從本質(zhì)上均是對各自原始鏈碼的優(yōu)化，因此其效率必定高于所對應(yīng)的原始鏈碼。

4 結(jié)語

本文將VCC的統(tǒng)計特征和正交3方向鏈碼的方向特征進(jìn)行融合，提出了一種改進(jìn)的O3DVCC?；?00幅圖像樣本，統(tǒng)計了IO3DVCC、ERD8FCC、AVRF4、Arith_3OT、CVCC和ICVCC等鏈碼各碼值出現(xiàn)的概率，給出了碼值的二進(jìn)制編碼表示，計算了碼值平均表達(dá)能力、平均長度和鏈碼效率，結(jié)果顯示IO3DVCC鏈碼的效率最高。在后續(xù)的實(shí)驗(yàn)驗(yàn)證中，統(tǒng)計了鏈碼效率計算排名靠前的I3ODVCC、Arith_3OT和ICVCC在表達(dá)20幅隨機(jī)圖像樣本中的碼值總數(shù)、二進(jìn)制總位數(shù)和相對于8DFCC的壓縮比率，結(jié)果表明，IO3DVCC壓縮效果最好。本文方法存在的不足是編碼與解碼方式較為復(fù)雜，時間消耗較大，因此，下一步的研究工作是對鏈碼進(jìn)一步改進(jìn)，降低時間復(fù)雜度。

)

[1]FREEMANH.Ontheencodingofarbitrarygeometricconfigurations[J].IRETransactionsonElectronicComputers, 1961,EC-10(2): 260-268.

[2]BRIBIESCAE.Anewchaincode[J].PatternRecognition, 1999, 32(2): 235-251.

[3]SANCHEZ-CRUZH,BRIBIESCAE,RODRIGUEZ-DAGNINORM.Efficiencyofchaincodestorepresentbinaryobjects[J].PatternRecognition, 2007, 40(6): 1660-1674.

[4] 劉勇奎.Freeman鏈碼壓縮算法的研究[J].計算機(jī)學(xué)報,2001,24(12):1294-1298.(LIUYK.ResearchonthecompressionalgorithmforFreemanchaincode[J].ChineseJournalofComputers, 2001, 24(12): 1294-1298.)[5] ZAHIR S, DHOU K. A new chain coding based method for binary image compression and reconstruction [EB/OL]. [2016- 10- 20]. http://www.eurasip.org/Proceedings/Ext/PCS2007/defevent/papers/cr1221.pdf.

[6] 李靈華,劉勇奎.Freeman 四方向鏈碼壓縮率提高的方法研究[J].計算機(jī)工程與設(shè)計,2013,34(3):1132-1136.( LI L H, LIU Y K. Study on methods for improving compressibility of 4-direction Freeman chain code [J]. Computer Engineering and Design, 2013, 34(3): 1132-1136.)

[7] SANCHEZ-CRUZ H, RODRIGUEZ-DIAZ M A. Coding long contour shapes of binary objects [C]// Proceedings of the 2009 14th Iberoamerican Conference on Pattern Recognition, Image Analysis, Computer Vision, and Applications, LNCS 5856. Berlin: Springer, 2009: 45-52.

[8] LIU Y K, WEI W, WANG P J, et al. Compressed vertex chain codes [J]. Pattern Recognition, 2007, 40(11): 2908-2913.

[9] 魏巍,劉勇奎,段曉東,等.基于Huffman編碼的改進(jìn)壓縮鏈碼[J].計算機(jī)應(yīng)用,2014,34(12):3565-3569.( WEI W, LIU Y K, DUAN X D, et al. Improved compression vertex chain code based on Huffman coding [J]. Journal of Computer Applications, 2014, 34(12): 3565-3569.)

[10] ?ALIK B, MONGUS D, LUKACN. A universal chain code compression method [J]. Journal of Visual Communication & Image Representation, 2015, 29(C): 8-15.

[11] ?ALIK B, MONGUS D, ?ALIK K R, et al. Chain code compression using string transformation techniques [J]. Digital Signal Processing, 2016, 53(C): 1-10.

[12] 劉勇奎,魏巍,郭禾.壓縮鏈碼的研究[J].計算機(jī)學(xué)報,2007,30(2):281-287.(LIU Y K, WEI W, GUO H. Research on compressed chain code [J]. Chinese Journal of Computers, 2007, 30(2): 281-287.)

This work is partially supported by the National Natural Science Foundation of China (61672132, 51579024), the Science Research Project of Liaoning Provincial Department of Education (L2014546), the Liaoning Province Science and Technology Plan (2013405003), the Fundamental Research Funds for the Central Universities (DC201502030408, DC201501025).

WEI Wei, born in 1980, Ph. D., associate professor. His research interests include computer graphics, pattern recognition.

DUAN Xiaodong, born in 1963, Ph. D., professor. His research interests include intelligent computing.

LIU Yongkui, born in 1961, Ph. D., professor. His research interests include computer graphics.

GUO Chen, born in 1956, Ph. D., professor. His research interests include virtual reality.

A new compressed vertex chain code

WEI Wei1,2,3, DUAN Xiaodong1,3*, LIU Yongkui1, GUO Chen2

(1.SchoolofComputerScienceandEngineering,DalianMinzuUniversity,DalianLiaoning116600,China; 2.CollegeofInformationScienceandTechnology,DalianMaritimeUniversity,DalianLiaoning116026,China; 3.DalianKeyLabofDigitalTechnologyforNationalCulture,DalianMinzuUniversity,DalianLiaoning116600,China)

Chain code is one kind of coding technology, which can represent the line, curve and region boundary with small data storage. In order to improve the compression efficiency of chain code, a new compression vertex chain code named Improved Orthogonal 3-Direction Vertex Chain Code (IO3DVCC) was proposed. The statistical characteristic of the Vertex Chain Code (VCC) and the directional characteristic of the OrThogonal 3-direction chain code (3OT) were combined in the proposed new chain code, 5 code values were totally set. The combination of 1, 3 and the combination of 3, 1 in VCC were merged and expressed by code 1. The expression of the code 2 was the same with the corresponding code value of VCC. The expression of code 3 was the same as the code value 2 of 3OT. Code 4 and code 5 corresponded to the two continuous code value 1 of IO3DVCC and eight continuous code values 2 of VCC respectively. Based on Huffman coding, the new chain code was the indefinite length coding. The code value probability, average expression ability, average length and efficiency of IO3DVCC, Enhanced Relative 8-Direction Freeman Chain Code (ERD8FCC), Arithmetic encoding Variable-length Relative 4-direction Freeman chain code (AVRF4), Arithmetic coding applied to 3OT chain code (Arith_3OT), Compressed VCC (CVCC), and Improved CVCC (ICVCC) were calculated aiming at the contour boundary of 100 images. The experimental results show that the efficiency of I3ODVCC is the highest. The total code number, total binary bit number, and compression ratio relative to the 8-Direction Freeman Chain Code (8DFCC) of three kinds of chain codes including IO3DVCC, Arith_3OT, and ICVCC were calculated aiming at the contour boundary of 20 randomly selected images. The experimental results demonstrate that the compression effect of IO3DVCC is the best.

chain code; Huffman coding; image boundary; efficiency of chain code; compression

2016- 12- 07;

2017- 03- 02。

國家自然科學(xué)基金資助項(xiàng)目(61672132,51579024)；遼寧省教育廳科學(xué)研究項(xiàng)目(L2014546)；遼寧省科技計劃項(xiàng)目(2013405003)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(DC201502030408，DC201501025)。

魏巍(1980—)，男，河南安陽人，副教授，博士，主要研究方向：計算機(jī)圖形學(xué)、模式識別； 段曉東(1963—)，男，吉林遼源人，教授，博士，主要研究方向：智能計算； 劉勇奎(1961—)，男，遼寧沈陽人，教授，博士，主要研究方向：計算機(jī)圖形學(xué)； 郭晨(1956—)，男，江蘇如東人，教授，博士，主要研究方向：虛擬現(xiàn)實(shí)。

1001- 9081(2017)06- 1747- 06

10.11772/j.issn.1001- 9081.2017.06.1747

TP391.9

A