李靈華，劉勇奎

（大連民族學(xué)院 計算機(jī)科學(xué)與工程學(xué)院，遼寧 大連116600）

0 引 言

鏈碼由于其使用簡單方便，占用存儲空間少而被廣泛應(yīng)用于圖像處理、模式識別、形狀分析等各領(lǐng)域。隨著圖形圖像處理各領(lǐng)域?qū)︽湸a越來越多的應(yīng)用，鏈碼技術(shù)也得到了快速的發(fā)展，許多不同的鏈碼新方法被提了出來。根據(jù)在描述的過程中對形狀信息的丟失與否，鏈碼可分為有損壓縮、準(zhǔn)無損壓縮和無損壓縮。本文選取典型的無損壓縮鏈碼方法，進(jìn)行深入的分析和比較，并通過實驗給出對各鏈碼方法的評價，針對各鏈碼技術(shù)的特點，剖析了其形成的原因。

1 無損鏈碼技術(shù)研究

可以從兩個方面來討論鏈碼技術(shù)，分別是：基于像素的鏈碼技術(shù)和基于邊界的鏈碼技術(shù)。對于基于像素的鏈碼技術(shù)，本文主要介紹典型的Freeman鏈碼技術(shù)；對于基于邊界的鏈碼技術(shù)，本文主要介紹頂點鏈碼技術(shù)。

1.1 Freeman鏈碼

一些典型的Freeman鏈碼包括：8方向Freeman、4方向Freeman鏈碼、角度差Freeman鏈碼、直角變化3方向Freeman鏈碼、改進(jìn)的相對8方向Freeman鏈碼、以及應(yīng)用計算編碼的直角變化3方向Freeman鏈碼，等等。

1.1.1 8方向Freeman鏈碼和4方向Freeman鏈碼

1961年，F(xiàn)reeman提出的8方向Freeman鏈碼D8FCC（8－direction Freeman chain code）是所有鏈碼技術(shù)研究的基礎(chǔ)。另一種較為常用的是4方向Freeman鏈碼D4FCC（4－direction Freeman chain code）。

D8FCC和D4FCC的鏈碼編碼簡單，但二者都不獨立于旋轉(zhuǎn)操作，即在旋轉(zhuǎn)操作下鏈碼改變。

1.1.2 角度差 Freeman鏈碼

2005年，劉勇奎等提出角度差Freeman鏈碼ADFCC（angle differences Freeman chain code）［1］。在 ADFCC 中，第一個碼值仍然采用D8FCC鏈碼，其余每個碼值則采用它與其前一個碼值的相對角度差進(jìn)行編碼。ADFCC基于最常用的D8FCC和霍夫曼 （Huffman）編碼思想，編碼時考慮到各碼值出現(xiàn)的不同概率。

ADFCC的碼值有8個，即ADFCC∈ ｛C0，C1，C2，C3，C4，C5，C6，C7｝。D8FCC、D4FCC和 ADFCC編碼實驗結(jié)果表明ADFCC的總碼長與D8FCC相同，為最短碼長。并且，ADFCC的平均碼長最短，存儲所需二進(jìn)制位數(shù)最少，相對比率最小。同時，ADFCC獨立于旋轉(zhuǎn)操作，即在旋轉(zhuǎn)操作下鏈碼不變。

1.1.3 直角變化3方向Freeman鏈碼

2005年，H.Sánchez－Cruz等人提出了直角3方向Freeman 鏈 碼 3OT （orthogonal three－direction Freeman chain code）［2］。3OT中有3個碼：0、1、2，其基于3種相對變化的直角方向。碼0表示沒有方向變化，即沿著前一個碼前進(jìn)的方向 “直行”；碼1表示參照之前行走的方向的變化趨勢是 “向前行進(jìn)”；碼2表示參照之前行走的方向的變化趨勢是 “向后回轉(zhuǎn)”。為了將碼值0、1、2進(jìn)行數(shù)字化表示，采用Huffman編碼方法編碼為二進(jìn)制碼。

3OT的碼值有3個，即3OT∈ ｛0，1，2｝，其平均碼長為1.51位／碼，3OT 獨立于旋轉(zhuǎn)操作［2］。在文獻(xiàn) ［2］中，作者還給出了基于35幅圖像的D8FCC、D4FCC、ADFCC及3OT編碼實驗結(jié)果對比，實驗結(jié)果表明在參與比較的所有鏈碼中，D8FCC和ADFCC的總碼長最短，且D8FCC的效率最低，ADFCC的效率最高。

1.1.4 改進(jìn)的相對8方向Freeman鏈碼

2007年，S.Zahir等人基于8方向Freeman鏈碼和角度差Freeman鏈碼提出了改進(jìn)的相對8方向Freeman鏈碼ERD8FCC （enhanced relative 8－direction Freeman chain code）［3］。

ERD8FCC在D8FCC的基礎(chǔ)上，變絕對的8方向運動為相對的8方向變化，同時引入了 （n10，5）規(guī)則以提高壓縮率，同時也采用Huffman編碼方法實現(xiàn)不等長編碼。

ERD8FCC的碼值共有10個，分別是F（前方）、FR（右前方）、FL （左前方）、R （右方）、L （左方）、BR （右后方）、BL（左后方）、B （后方）、Y （5個連續(xù)的前方）以及X （10個連續(xù)的前方）。

由于文獻(xiàn) ［3］中并未給出每個碼值的Huffman編碼的二進(jìn)制位碼形式，因此，在后面的實驗比較中，我們將基于10幅實驗圖像的統(tǒng)計給出Huffman編碼結(jié)果。

ERD8FCC的碼值有10個，即ERD8FCC∈ ｛F，F(xiàn)R，F(xiàn)L，R，L，BR，BL，B，Y，X｝，ERD8FCC獨立于旋轉(zhuǎn)操作。在文獻(xiàn) ［3］中，ERD8FCC被用于形狀及二值圖像的壓縮與復(fù)原中，該文作者對46幅二值圖像的D8FCC、D4FCC、ADFCC及ERD8FCC編碼實驗結(jié)果對比，實驗結(jié)果表明在參與比較的所有鏈碼中，ERD8FCC效率最高［3］。

1.1.5 應(yīng)用計算編碼的直角變化3方向Freeman鏈碼

2009年，H.Sánchez－Cruz等人在3OT的基礎(chǔ)上加入了計算編碼，提出了基于計算編碼的直角變化3方向Freeman鏈 碼 Arith＿3OT （arithmetic coding applied to 3OT chain code）［4］。除了3OT中的3個碼值0、1、2外，Arith＿3OT中增加了3個碼值3、4、5。碼值0、1、2所表示的含義與3OT中的定義相同。碼值3表示每5個連續(xù)的符號0的情況，碼值4表示每5個連續(xù)的符號1的情況，碼值5表示符號組合0110的情況。

由于文獻(xiàn) ［4］中同樣并未給出每個碼值的Huffman編碼的二進(jìn)制位碼形式，因此，在后面的實驗比較中，我們也將基于10幅實驗圖像的統(tǒng)計給出Arith＿3OT的Huffman編碼結(jié)果。

Arith＿3OT的碼值有6個，即Arith＿3OT∈ ｛0，1，2，3，4，5｝，Arith＿3OT獨立于旋轉(zhuǎn)操作。在文獻(xiàn) ［4］中，Arith＿3OT被應(yīng)用于二值圖像的輪廓形狀編碼中，該文作者對16幅二值圖像的ADFCC及Arith＿3OT編碼實驗結(jié)果對比，實驗結(jié)果表明Arith＿3OT的效率最高［4］。

1.2 頂點鏈碼

一些典型的頂點鏈碼包括：原始頂點鏈碼、擴(kuò)展頂點鏈碼、變長頂點鏈碼，變長壓縮頂點鏈碼、動態(tài)頂點鏈碼、以及等長壓縮頂點鏈碼，等等。

1.2.1 原始頂點鏈碼

1999年，E.Bribiesca首先介紹了頂點鏈碼的概念，此為原始頂點鏈碼VCC（vertex chain code）。頂點鏈碼是基于形狀邊界的頂點像素的數(shù)目進(jìn)行編碼的。

在頂點鏈碼中，任意形狀的邊界或輪廓是由規(guī)律排列的單元組成的。因此，頂點鏈碼描述的是封閉的邊界。最小的封閉邊界只包含一個像素。VCC中的每個碼的碼值表示該頂點是幾個邊界像素的頂點，對應(yīng)用3個碼值0、1、2分別表示該頂點是0、1、2這3個邊界像素的頂點。

VCC的碼值有3個，即VCC∈ ｛1，2，3｝，其平均碼長為2位／碼。VCC獨立于旋轉(zhuǎn)操作。

在文獻(xiàn) ［5］中，VCC被用于表示圖像區(qū)域，在文獻(xiàn)［6］和文獻(xiàn) ［7］中，頂點鏈碼被用于曲線長度估計，在文獻(xiàn) ［8］中，其被用于提取目標(biāo)圖像的最小外接矩形。

1.2.2 擴(kuò)展頂點鏈碼

2007年，文獻(xiàn) ［9］基于原始頂點鏈碼提出了一種改進(jìn)的頂點鏈碼，稱為擴(kuò)展頂點鏈碼E＿VCC（extended vertex chain code）。

VCC是等長編碼，碼長為二位二進(jìn)制數(shù)，用來表示碼值1、2和3。但是，二位二進(jìn)制數(shù)是可以對四個碼值進(jìn)行編碼表示的。E＿VCC在不增加碼長的情況下，增加一個碼值0，用來表示在圖像邊界上最經(jīng)常出現(xiàn)的角點相鄰的情況，即碼值1和3組合的情況。

E＿VCC比VCC所用的數(shù)據(jù)少。E＿VCC的碼值有4個，即VCC∈ ｛0，1，2，3｝，其平均碼長為2位／碼。E＿VCC獨立于旋轉(zhuǎn)操作［9］。

1.2.3 變長頂點鏈碼

在文獻(xiàn) ［9］中，作者還基于原始頂點鏈碼提出了第二種改進(jìn)的頂點鏈碼，稱為變長頂點鏈碼V＿VCC（variablelength vertex chain code）。

V＿VCC仍采用VCC的3個碼值1、2和3。所不同的是，V＿VCC考慮到這三種碼值的出現(xiàn)概率。統(tǒng)計結(jié)果表明，碼值2的出現(xiàn)概率遠(yuǎn)大于另兩個碼值。因此，V＿VCC用1位二進(jìn)制位0編碼碼值2，碼值1和碼值3則分別用2位二進(jìn)制位10和11進(jìn)行編碼。

V＿VCC的功能與VCC相同，但其長度要遠(yuǎn)遠(yuǎn)小于VC的長度。V＿VCC的碼值有3個，即VCC∈ ｛1，2，3｝，其平均碼長為1.49位／碼，V＿VCC獨立于旋轉(zhuǎn)操作［9］。

1.2.4 變長壓縮頂點鏈碼

文獻(xiàn) ［9］中，作者還基于原始頂點鏈碼及Huffman編碼思想提出了第三種改進(jìn)的頂點鏈碼，稱為變長壓縮頂點鏈 碼 VC ＿VCC （variable－length compressed vertex chain code）。

VC＿VCC考慮到各碼值的出現(xiàn)概率，將E＿VCC與V＿VCC相結(jié)合而成。它包括5個碼值，分別是碼值1、碼值2、碼值3、碼值4和碼值5。新增加的兩個碼值分別用于表示兩種組合情況，即 “1和3組合”和 “3和1組合”。5個碼值按出現(xiàn)概率采用Huffman編碼為二進(jìn)制碼。

當(dāng)輪廓邊界越長時，采用VC＿VCC的節(jié)省數(shù)據(jù)位數(shù)的優(yōu)勢越明顯。VC＿VCC的碼值有5個，即VC＿VCC∈｛c1，c2，c3，c4，c5｝，其平均碼長為1.62位／碼，VC＿VCC獨立于旋轉(zhuǎn)操作［9］。

文獻(xiàn) ［10］在VC＿VCC的基礎(chǔ)上提出了分段編碼的思想，從而得到更高的數(shù)據(jù)壓縮率。

1.2.5 動態(tài)頂點鏈碼

2010年，于國防等人基于原始頂點鏈碼提出了一種改進(jìn)的頂點鏈碼，稱為動態(tài)頂點鏈碼D＿VCC（dynamic vertex chain code）［11］。

D＿VCC的思想是改變VCC中各碼值直觀表示頂點像素的數(shù)目的含義，對鏈碼組成元素重新分配碼值。即以十進(jìn)制數(shù)值0（或9）表示原碼值1，以十進(jìn)制數(shù)值9（或0）表示原碼值3，而以十進(jìn)制數(shù)值18動態(tài)且直觀地表示原碼值2及碼值2連續(xù)出現(xiàn)的個數(shù)。

從文獻(xiàn) ［11］的描述中可以看出，D＿VCC碼值有10個，即D＿VCC∈ ｛0，1，2，3，4，5，6，7，8，9｝，平均碼長則為4位／碼，其在減少鏈碼總碼數(shù)的同時卻增加了碼值的二進(jìn)制位數(shù)。D＿VCC主要追求的是在總碼數(shù)方面的高壓縮率而未考慮鏈碼占用的存儲空間 （總二進(jìn)制位數(shù)）的大小。

1.2.6 等長壓縮頂點鏈碼

文獻(xiàn) ［11］中，作者還基于上述的VCC和E＿VCC提出了一種新的壓縮頂點鏈碼，稱為等長壓縮頂點鏈碼EC＿VCC （equivalent－length compressed vertex chain code）。

EC＿VCC改變以往鏈碼以位 （bit）為最小單位的存儲方式，而采用以字節(jié) （byte）為最小單位的存儲方式。EC＿VCC的基本思想是將一個字節(jié) （8位二進(jìn)制數(shù)）拆分為高2位和低6位兩部分。高2位的編碼用于表示EC＿VCC的碼值，第6位的編碼用于表示高2位指定的碼值連續(xù)出現(xiàn)的個數(shù)。2位二進(jìn)制編碼最多可表示4種碼值，6位二進(jìn)制編碼最多可表示碼值連續(xù)出現(xiàn)的個數(shù)是64個。如果碼值連續(xù)出現(xiàn)的個數(shù)超過64個，則開始一個新的字節(jié)編碼。

EC＿VCC同樣追求的是在總碼數(shù)方面的高壓縮率而未考慮鏈碼占用的存儲空間 （總二進(jìn)制位數(shù)）的大小。EC＿VCC采用等長編碼，其碼值最多可有256個，碼長為8位／碼。文獻(xiàn) ［11］對3幅圖像的D8FCC、D4FCC、VCC、VC＿VCC、D＿VCC以及EC＿VCC編碼實驗結(jié)果進(jìn)行對比，實驗結(jié)果表明在參與比較的所有鏈碼中，VC＿VCC具有穩(wěn)定高效的編碼壓縮比，而D＿VCC和EC＿VCC的壓縮比隨圖像形狀的變化而變化，圖像中包含的連續(xù)同向走線越多，壓縮比就越高［11］。

2 比較與評價

2.1 鏈碼的評價方法

文獻(xiàn) ［9］中給出了評價鏈碼效率的公式如下

式中：E——鏈碼的效率，C——碼值平 均表達(dá)能力，L——平均碼長。也就是說，一種鏈碼的效率與其碼值平均表達(dá)能力成正比，與其平均碼長成反比，其含義是每個二進(jìn)制位平均所表示的邊界的長度。

鏈碼的碼值平均表達(dá)能力C指的是該鏈碼的各碼值所能表示的區(qū)域邊界 （或數(shù)字曲線）的長度的平均值，以像素單位作為計量單位。例如，當(dāng)一個碼值表示的是邊相鄰像素間的接續(xù)關(guān)系時，如D8FCC的碼值0、2、4和6，則C為1；當(dāng)它表示的是角點相鄰像素間的接續(xù)關(guān)系時，如D8FCC的碼值1、3、5和7，則C為2。

2.2 鏈碼的比較

我們分別從兩個方面對文中提到的鏈碼方法進(jìn)行比較：實驗結(jié)果和理論分析。

2.2.1 實驗結(jié)果比較

我們選取實際圖像中10個景物的輪廓進(jìn)行實驗，如圖1所示。輪廓圖像的尺寸列于表1中。

圖1 實驗圖像

針對圖1中10幅實驗圖像的輪廓，我們分別采用文中提到的6種Freeman鏈碼及6種頂點鏈碼進(jìn)行編碼，分別統(tǒng)計每幅圖像輪廓鏈碼的總長度，即鏈碼的總碼數(shù)如表2所示。

表1 實驗圖像尺寸列表

表2 實驗圖像采用不同鏈碼方法得到的鏈碼總長度 （鏈碼總碼數(shù)）

表3 不同鏈碼的碼值數(shù)及每位編碼需要的二進(jìn)制位數(shù) （位／碼）

文中提到的6種Freeman鏈碼及6種頂點鏈碼的碼值數(shù)及每碼編碼需要的二進(jìn)制位數(shù) （位／碼）列于表3中。

在12種鏈碼中，有6種鏈碼采用不等長編碼。其中ADFCC、3OT、V＿VCC和VC＿VCC鏈碼的每個碼值對應(yīng)的二進(jìn)制編碼分別見文獻(xiàn) ［1］、文獻(xiàn) ［2］以及文獻(xiàn) ［9］，ERD8FCC和Arith＿3OT鏈碼的每個碼值對應(yīng)的二進(jìn)制編碼我們通過對表2中10幅實驗圖像的ERD8FCC和Arith＿3OT各碼值出現(xiàn)的概率分別進(jìn)行統(tǒng)計，并進(jìn)行Huffman編碼，得到的編碼結(jié)果分別見表4和表5。

表4 ERD8FCC各碼值的出現(xiàn)概率及二進(jìn)制編碼

表5 Arith＿3OT各碼值的出現(xiàn)概率及二進(jìn)制編碼

這樣，我們通過計算得到文中提到的6種Freeman鏈碼及6種頂點鏈碼對10幅實驗圖像分別進(jìn)行編碼所占用的存儲空間大小，用所需二進(jìn)制總位數(shù)進(jìn)行衡量，見表6。

通過對表2中得到的針對10幅實驗圖像的12種鏈碼的總碼數(shù)和表6中的二進(jìn)制總位數(shù)的計算，得到12種鏈碼的平均碼長列于表7中。

表6 實驗圖像采用不同鏈碼方法編碼所占存儲空間大小 （二進(jìn)制總位數(shù)）

表7 文中提及的12種鏈碼的平均碼長 （位／碼）

分析文中提到的12種鏈碼，對于D4FCC、3OT、VCC、V＿VCC這4種鏈碼，由于每個碼值表示的都為邊相鄰像素間的接續(xù)關(guān)系，每個碼值的表達(dá)能力都為1，因此，碼值的平均表達(dá)能力為1。

對于D8FCC、ADFCC、E＿VCC、VC＿VCC這4種鏈碼，分別有表示邊相鄰像素和角點相鄰像素間的接續(xù)關(guān)系的碼值，D8FCC和ADFCC中的兩種情況的碼值出現(xiàn)概率是相同的。基于上述10幅實驗圖像，分別統(tǒng)計碼值表達(dá)能力為1和2的碼值出現(xiàn)概率，從而計算出該4種鏈碼的碼值平均表達(dá)能力。

對于ERD8FCC、Arith＿3OT、D＿VCC、EC＿VCC這4種鏈碼，分別有表示邊相鄰像素和角點相鄰像素間的接續(xù)關(guān)系的碼值，同時，因為鏈碼中采用了計算編碼，所以，有些碼值描述的是多個像素。如ERD8FCC中的碼值Y的表達(dá)能力為5，碼值X的表達(dá)能力為10；Arith＿3OT中的碼值3和4的表達(dá)能力為5，碼值5的表達(dá)能力為4；D＿VCC中碼值28的表達(dá)能力分別為28；EC＿VCC中碼值的表達(dá)能力最多可達(dá)到64?；谏鲜?0幅實驗圖像，分別統(tǒng)計4種鏈碼中不同碼值表達(dá)能力的碼值的出現(xiàn)概率，從而計算出該4種鏈碼的碼值平均表達(dá)能力。

12種鏈碼的碼值數(shù)、碼值、碼值表達(dá)能力、不同表達(dá)能力碼值出現(xiàn)的概率、以及平均表達(dá)能力的計算結(jié)果列于表8中。

考慮到EC＿VCC鏈碼的碼值較多，并且對應(yīng)的每個碼的碼值表達(dá)能力各不相同，因此，表8中沒有分別列出EC＿VCC的所有碼值、各個碼值的表達(dá)能力以及出現(xiàn)的概率統(tǒng)計，在出現(xiàn)概率統(tǒng)計一欄中給出的數(shù)字1.000指的是將所有碼值放在一起。最后給出了平均表達(dá)能力的計算結(jié)果值，這一結(jié)果同樣是基于10幅實驗圖像，采用與其他鏈碼相同的統(tǒng)計方法獲得，只不過這個計算量要比其他的大很多。

表8 文中12種鏈碼的碼值數(shù)、碼值、碼值表達(dá)能力、出現(xiàn)概率及平均表達(dá)能力

綜合上述分析及得到的數(shù)據(jù)，我們通過計算得到12種鏈碼效率的相關(guān)結(jié)果，見表9。

2.2.2 理論分析比較

由表2可以看出，12種鏈碼中鏈碼總長度最短的是EC＿VCC，為14241個碼，接下來的是Arith＿3OT，為16828個碼，以及ERD8FCC，為17701個碼。12種鏈碼中鏈碼總長度最長的是VCC和V＿VCC，都為29600個碼，接下來的是D4FCC和3OT，都為29560個碼，其他鏈碼的鏈碼總長度處于中等。

表9 文中提及的12種鏈碼的效率

可見，EC＿VCC實現(xiàn)了其所追求的目標(biāo)，即鏈碼總長度最短。其采用的方法是變按位為最小存儲單位為按字節(jié)為最小存儲單位，并采用等長編碼及行程編碼，該方法對于目標(biāo)的實現(xiàn)是有效的。同時，由表3可見，EC＿VCC使用的碼值最多，而VCC和V＿VCC使用的碼值最少。因此，要想縮短鏈碼總長度，就要增加鏈碼的碼值數(shù)。

由表6可以看出，12種鏈碼中鏈碼編碼所占存儲空間最小的是VC＿VCC，為38000位二進(jìn)制碼，接下來的是Arith＿3OT，為38293位二進(jìn)制碼，以及ERD8FCC，為39121位二進(jìn)制碼。12種鏈碼中鏈碼編碼所占存儲空間最大的是EC＿VCC，為113928位二進(jìn)制碼，接下來的是D＿VCC，為89240位二進(jìn)制碼，其他鏈碼編碼所占存儲空間處于中等。

分析這一結(jié)果形成的原因，VC＿VCC、Arith＿3OT和ERD8FCC都采用變長編碼，編碼時考慮碼值出現(xiàn)的概率，應(yīng)用了Huffman編碼思想。所占存儲空間最小的VC＿VCC還采用的組合編碼的碼值，這也是進(jìn)一步減少鏈碼編碼存儲空間的有效措施。反之，所占存儲空間最大的EC＿VCC和次大的D＿VCC都采用等長編碼，編碼時未考慮碼值出現(xiàn)的概率。

由表7可以看出，12種鏈碼中平均碼長最短的是3OT，為1.50位／碼，接下來的是V＿VCC，為1.55位／碼，以及VC＿VCC，為1.71位／碼。12種鏈碼中平均碼長最長的是EC＿VCC，為8位／碼，接下來的是D＿VCC，為4位／碼，其他鏈碼平均碼長處于中等。

由表8可以看出，12種鏈碼中碼值平均表達(dá)能力最強(qiáng)的是EC＿VCC，為2.08像素單位，接下來的是ERD8FCC，為1.79像素單位，以及Arith＿3OT，為1.78像素單位。12種鏈碼中平均表達(dá)能力最弱的是VCC和E＿VCC，都為1.23像素單位，接下來的是V＿VCC和VC＿VCC，都為1.34像素單位，其他鏈碼碼值平均表達(dá)能力處于中等。

由表9可以看出，12種鏈碼中效率最高的是ERD8FCC，為0.81，接下來的是ADFCC，為0.79，Arith＿3OT和VC＿VCC的效率都為0.78，此4種鏈碼的效率較為相當(dāng)。12種鏈碼中效率最低的是EC＿VCC，僅為0.26，接下來的是D＿VCC，為0.35，其他效率處于中等。

可見，雖然EC＿VCC的鏈碼表達(dá)能力最強(qiáng)，但其平均碼長最長，因此，其效率反而最低。ERD8FCC的鏈碼表達(dá)能力較強(qiáng)，其平均碼長為中等，其效率卻為最高。VC＿VCC的鏈碼表達(dá)能力較弱，其平均碼長較短，其效率卻為較高?？梢?，鏈碼效率受平均碼長影響的程度要大于受鏈碼表達(dá)能力影響的程度。因此，要提高鏈碼的效率，可考慮提高鏈碼的表達(dá)能力，但不能以犧牲鏈碼平均碼長為代價。

進(jìn)一步分析這一結(jié)果形成的原因，效率高的4種鏈碼均采用了Huffman不等長編碼，因而形成了最佳編碼。效率最高的ERD8FCC鏈碼不僅采用Huffman編碼，還采用了計算編碼，雖然在ADFCC的基礎(chǔ)上增加了2個碼值，但仍得到了最高的鏈碼效率。而效率低的2種鏈碼EC＿VCC和D＿VCC都采用等長編碼，并且在編碼的過程中都有冗余。如D＿VCC用4位二進(jìn)制位編碼10個碼值，冗余了6個編碼；EC＿VCC則分別采用64個碼值編碼頂點鏈碼的碼值1（二進(jìn)制編碼01b5b4b3b2b1b0）和碼值3（二進(jìn)制編碼11b5b4b3b2b1b0），而很顯然，碼值1和碼值3最多只能連續(xù)出現(xiàn)2個，因此，各自最多需要的碼值是2個，由此產(chǎn)生了2個62個碼 （即124個碼）的冗余。這樣導(dǎo)致了鏈碼EC＿VCC和D＿VCC的低效率。

鏈碼所占存儲空間的大小表明了鏈碼的壓縮率，存儲空間越小，其壓縮率越高。從上述比較結(jié)果可見，壓縮率高的VC＿VCC、Arith＿3OT以及ERD8FCC的效率也高，而壓縮率低的EC＿VCC和D＿VCC的效率也低。這也說明了鏈碼的效率是鏈碼壓縮率的有力體現(xiàn)。

3 鏈碼技術(shù)展望

從文中前面部分的敘述可以看出，鏈碼技術(shù)在圖像處理以及模式識別領(lǐng)域得到了快速的發(fā)展，出現(xiàn)了許多鏈碼的應(yīng)用及新方法。然而，鏈碼技術(shù)的發(fā)展最多的都是基于Freeman鏈碼以及頂點鏈碼方法。為了提高鏈碼的壓縮率，可以考慮采取不等長編碼、計算編碼、組合碼值編碼等措施，將不同鏈碼技術(shù)采用的方法結(jié)合應(yīng)用到現(xiàn)有的某一鏈碼中，從而形成新的鏈碼方法。

上述介紹的鏈碼方法都是應(yīng)用到二維坐標(biāo)系統(tǒng)描述的圖像中，從而將其轉(zhuǎn)化為一維的形式。新的發(fā)展趨勢則是研究將三維坐標(biāo)系統(tǒng)描述的圖像轉(zhuǎn)化為一維形式的鏈碼技術(shù)。另一方面，目前的鏈碼技術(shù)都是用于描述簡單圖像，進(jìn)一步的發(fā)展可以考慮如何將鏈碼技術(shù)應(yīng)用于復(fù)雜圖像的描述的新方法。

4 結(jié)束語

應(yīng)該指出，介紹的12種鏈碼并不是鏈碼方法的全部。介紹了6種基于像素的鏈碼方法和6種基于邊界的鏈碼方法?；谙袼氐逆湸a方法介紹了Freeman鏈碼，基于邊界的鏈碼方法介紹了頂點鏈碼。當(dāng)然，除了這兩類技術(shù)外，還有其他基于像素的鏈碼和基于邊界的鏈碼技術(shù)。

鏈碼之所以成為近年來研究的熱點，主要原因在于其高壓縮率以及節(jié)省存儲空間。文中分別從各鏈碼的產(chǎn)生、實現(xiàn)的主要思想、各鏈碼的主要特性及一些典型的應(yīng)用進(jìn)行了詳細(xì)的論述，并結(jié)合鏈碼的評價方法對各鏈碼進(jìn)行了實驗結(jié)果的比較與理論比較分析，希望本文的研究能為鏈碼的應(yīng)用者與研究者提供便利與參考。進(jìn)一步的研究將著眼于選取和確定新的鏈碼碼值，將Huffman編碼和計算編碼相結(jié)合，探討有利于提高鏈碼效率的新方法，這將是我們下一步研究工作的重點。

：

［1］LIU Y K，Zalik B，WANG P J，et al.Directional difference chain codes with quasi－lossless compression and run－length encoding［J］.Signal Processing：Image Communication，2012，27（9）：973－984.

［2］Sánchez Cruz H，Bribiesca E，Rodríguez Díaz M A.Efficiency of chain codes to represent binary objects［J］.Pattern Recognition，2007，40 （6）：1660－1674.

［3］Zahir S，Dhou K.A new chain coding based method for binary image compression and reconstruction［J］.Picture Coding Symposium，Lisbon，Portugal，2007：1321－1324.

［4］Sánchez Cruz H，Rodríguez Díaz M A.Coding long contour shapes of binary objects［G］.LNCS 5856：Progress in Pattern Recognition，Image Analysis，Computer Vision，and Applications，2009：45－52.

［5］YU Youyang，CHEN Youguang，GU Guoqing.Filling algorithm for vertex chain code image［J］.Computer Engineering，2008，34 （12）：265－267 （in Chinese）. ［于游洋，陳優(yōu)廣，顧國慶.頂點鏈編碼圖像的填充算法 ［J］.計算機(jī)工程，2008，34（12）：265－267.］

［6］Dianat O，Haron H.Algorithm for length estimation based on the vertex chain code ［C］／／Singapore：International Conference on Signal Processing Systems，2009：951－954.

［7］Haron H，Rehman A，Wulandhari L A，et al.Improved vertex chain code based mapping algorithm for curve length estimation［J］.Journal of Computer Science，2011，7 （5）：736－743.

［8］LU Rong，F(xiàn)AN Yong，CHEN Niannian，et al.Fast algorithm for extracting minimum enclosing rectangle of target image［J］.Computer Engineering，2010，36 （21）：178－180 （in Chinese）.［盧蓉，范勇，陳念年，等.一種提取目標(biāo)圖像最小外接矩形的快速算法 ［J］.計算機(jī)工程，2010，36 （21）：178－180.］

［9］LIU Y K，WEI W，WANG P J，et al.Compressed vertex chain codes［J］.Pattern Recognition，2007，40 （11）：2908－2913.

［10］CHEN P Y，CHANG C P.The segmented vertex chain code［J］.Journal of the Chinese Institute of Engineers，2011，34（6）：40－44.

［11］YU Goufang，WANG Li.Research on compression－type vertex chain code［J］.Journal of Image and Graphics，2010，15（10）：1465－1470 （in Chinese）. ［于國防，王莉.壓縮型頂點鏈碼的研究 ［J］.中國圖象圖形學(xué) 報，2010，15 （10）：1465－1470.］