一種新壓縮頂點鏈碼

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

(1.大連民族大學 計算機科學與工程學院，遼寧 大連 116600； 2.大連海事大學 信息科學技術學院，遼寧 大連 116026； 3.大連民族大學 大連市民族文化數字技術重點實驗室，遼寧 大連 116600)

一種新壓縮頂點鏈碼

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

(1.大連民族大學 計算機科學與工程學院，遼寧 大連 116600； 2.大連海事大學 信息科學技術學院，遼寧 大連 116026； 3.大連民族大學 大連市民族文化數字技術重點實驗室，遼寧 大連 116600)

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

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

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

0 引言

鏈碼是一種表示線條、曲線和圖像邊界區域的常用編碼技術，它由一系列固定方向和長度的小直線段組成。在表示圖像邊界輪廓時，按照定義好的編碼規則對輪廓上的像素點進行表達和存儲。由于鏈碼編碼簡單，操作方便，因此在圖像識別等領域應用廣泛。

最直觀的鏈碼是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鏈碼以圖像邊界輪廓的方向為依據，因此8DFCC和4DFCC均具有明顯的方向性。

圖1 8DFCC示例

圖2 4DFCC示例

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

圖3 VCC示例

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

圖4 3OT示例

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

1 鏈碼的改進

1.1 改進的Freeman鏈碼

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

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

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

1.2 改進的3OT鏈碼

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

1.3 改進的VCC鏈碼

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

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

表1 ICVCC與VCC的對應關系

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

2 新壓縮VCC

2.1 正交3方向VCC

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

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

O3DVCC將鏈碼的方向特征與統計特征進行了融合，其中方向特征是相對的，統計特征是絕對的。由圖5不難發現，應用VCC表示的鏈碼為1313131時，對應的O3DVCC鏈碼表示為1111111；應用VCC表示的鏈碼為3131時，對應的O3DVCC鏈碼也表示為1111；VCC中的碼值2與O3DVCC中的碼值2保持一致?？梢钥闯?，O3DVCC將VCC中的碼值1、3組合和3、1組合統一歸并為帶有方向性質的碼值1。這為進一步壓縮O3DVCC鏈碼奠定了基礎。

圖5 O3DVCC示例

若以VCC為基準鏈碼，其轉換為O3DVCC的算法如下：

/*數組V[]存放VCC碼值*/ /*數組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也可以轉換為VCC，其算法如下：

/*數組V[]存放VCC碼值*/ /*數組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;

}

}

本文應用O3DVCC對100幅圖像進行了概率統計，并基于Huffman編碼計算了O3DVCC每一碼值的二進制編碼，如表2所示。

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

表2 O3DVCC碼值概率與二進制編碼

2.2 改進的O3DVCC

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

表3 IO3DVCC不同M、N組合對應的效率統計

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

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

表4 IO3DVCC與O3DVCC的對應關系

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

3.1 鏈碼評價的方法

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

e=c/l

(1)

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

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

圖6 碼值表達能力

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

鏈碼的平均表達能力可表示為：

(2)

其中：ci為鏈碼中某一碼值的表達能力；pi為該碼值出現的概率。

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

(3)

其中：li為鏈碼中某一碼值表達所占的bit數；pi為該碼值出現的概率。

3.2 實驗比較與分析

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

表5 不同鏈碼的性能對比

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

6種鏈碼中，CVCC的平均鏈碼長度最短，為1.567 2/碼，其次是IO3DVCC，為1.649 3/碼，第三是ICVCC為1.780 7/碼，后續依次是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的平均表達能力和鏈碼長度對比其他鏈碼雖然并非最優，但均排在前列。Arith_3OT的平均表達能力最強，但其平均鏈碼長度過長，排在6種鏈碼的最后，因而其效率并非最高。ICVCC鏈碼的平均表達能力和鏈碼長度排名均靠前，因此其效率較高。CVCC的平均鏈碼長度較短，雖然其平均表達能力不高，但其效率較高。

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

圖7 圖像輪廓邊界

圖像尺寸總像素數圖像尺寸總像素數寶寶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

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

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

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

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

4 結語

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

)

[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].計算機學報,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].計算機工程與設計,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].計算機應用,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].計算機學報,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。

國家自然科學基金資助項目(61672132,51579024)；遼寧省教育廳科學研究項目(L2014546)；遼寧省科技計劃項目(2013405003)；中央高?；究蒲袠I務費專項資金資助項目(DC201502030408，DC201501025)。

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

1001- 9081(2017)06- 1747- 06

10.11772/j.issn.1001- 9081.2017.06.1747

TP391.9

A