2. 大连海事大学 信息科学技术学院, 辽宁 大连 116026;
3. 大连民族大学 大连市民族文化数字技术重点实验室, 辽宁 大连 116600
2. College of Information Science and Technology, Dalian Maritime University, Dalian Liaoning 116026, China;
3. Dalian Key Lab of Digital Technology for National Culture, Dalian Minzu University, Dalian Liaoning 116600, China
链码是一种表示线条、曲线和图像边界区域的常用编码技术，它由一系列固定方向和长度的小直线段组成。在表示图像边界轮廓时，按照定义好的编码规则对轮廓上的像素点进行表达和存储。由于链码编码简单，操作方便，因此在图像识别等领域应用广泛。
最直观的链码是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示例 Figure 1 Example of 8DFCC |
|
图 2 4DFCC示例 Figure 2 Example of 4DFCC |
1999年，Bribiesca[2]提出了目前使用非常广泛的顶点链码(Vertex Chain Code, VCC)。与Freeman链码不同，VCC是通过标记图像边界轮廓像素的顶点数目表示的。VCC的码值由Σ(VCC)={σ|1, 2, 3}组成，码值1表示单独的像素顶点，通常在边界像素处出现；码值2表示连续的两个像素顶点，用来表示连续的像素；码值3表示将有3个像素顶点聚集在一起，常在边界像素方向改变处出现，如图 3所示。
|
图 3 VCC示例 Figure 3 Example of VCC |
正交3方向链码(OrThogonal 3-direction chain code, 3OT)[3]的码值由Σ(3OT)={σ|0, 1, 2}组成。其中：码值0表示后继链码与前续链码码值方向相同；码值1表示链码前进方向发生改变，同时与其前续相邻的链码码值改变的变化方向不同；码值2表示链码前进方向发生改变，但与其前续相邻的链码码值改变的变化方向相同。如图 4所示。
|
图 4 3OT示例 Figure 4 Example of 3OT |
由图 1、图 2和图 4可以看出，8DFCC、4DFCC和3OT链码在表示图像边界轮廓时具有明显的方向性，而由图 3可以发现VCC是通过统计顶点的个数来组成链码的。这些链码对图像轮廓的几何形状均有很好的表示，但在存储时，往往受限于码值长度，导致链码存储占据较大的空间。因此，在后续研究中提出了对这些链码的改进方案。每种新提出的链码均会在一定程度上提高码值平均表达能力，降低链码平均长度，提高链码整体压缩效率。本文将VCC的统计特征与正交3方向链码的方向特征相结合，针对VCC提出了一种新的压缩链码。进一步，对所提的新链码进行改进，大幅提高了链码的压缩效率。
1 链码的改进 1.1 改进的Freeman链码2001年，刘勇奎[4]基于8DFCC提出了角度差Freeman链码(Angle Differences Freeman Chain Code, 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链码(Enhanced Relative 8-Direction Freeman Chain Code, ERD8FCC)。ERD8FCC的码值由Σ(ERD8FCC)={σ|F, FL, L, BL, B, BR, R, FR, X, Y}组成，其中每一码值均表示当前像素相对于其前续像素的位置关系：F表示当前像素位于前续像素的前方(Front)，FL表示左前方(Front Left)，L表示左方(Left)，BL表示左后方(Back Left)，B表示后方(Back)，BR表示右后方(Back Right)，R表示右方(Right)，FR表示右前方(Front Right)，X表示连续的10个F，Y表示连续的5个F。同ADFCC类似，ERD8FCC也通过Huffman编码得到不等长的码值表达，相比于ADFCC，对图像中连续的码值合并为一个新的码值。在图像出现连续F码值较多的情况下，能很好地降低F码值出现的概率，同时增加X、Y码值出现的概率。由于X、Y码值的二进制长度小于对应连续F码值所需的二进制长度，因此能够减少了链码二进制总长度，提高压缩效果。
2013年，李灵华等[6]基于4DFCC提出了基于算数编码的变长相对四方向Freeman链码(Arithmetic encoding Variable-length Relative 4-direction Freeman chain code, 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方向链码(Arithmetic coding applied to 3OT chain code, 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 (Compressed VCC, 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 (Improved CVCC, ICVCC)。ICVCC的码值由Σ(ICVCC)={σ|1, 2, 3, 4, 5, 6}组成，链码在CVCC的基础上，新增了一个码值6用来表示CVCC中连续的9个码值2的组合。ICVCC与CVCC的对应关系如表 1所示。实验表明，其链码效率和压缩比率要高于压缩的VCC的。
|
表 1 ICVCC与VCC的对应关系 Table 1 Corresponding relationship of ICVCC and VCC |
除了对常用链码进行改进，研究者尝试应用多种方式提高链码的压缩效率。2015年，Žalik等[10]提出一种新的无损压缩链码方法：基于游程编码、动态窗口等压缩方式对链码二进制进行压缩。2016年，Žalik等[11]又提出采用基于Move-To-Front变换(Move-To-Front Transformation, MTFT)和Burrows-Wheeler变换(Burrows-Wheeler Transform, BWT)等字符变换技术，结合游程编码方法对链码进行压缩，取得了较好的压缩效果。
2 新压缩VCC 2.1 正交3方向VCC正交3方向链码及其改进链码的共同特点是具有明确的方向性。VCC及其优化链码虽没有明显的方向性，但通过逐一统计边界像素的顶点个数完成编码过程。本文将3OT链码的方向特征与VCC的像素统计特征相结合，提出了一种新的链码：正交3方向VCC (Orthogonal 3-Direction VCC, O3DVCC)。
O3DVCC共3个码值：码值1表示当前链码与之前最近发生方向改变的码值对应的方向不同；码值2同VCC的码值2，表示方向没有改变；码值3表示当前链码与之前最近发生方向改变的码值对应的方向相同。O3DVCC需要一个参考方向，通常将遍历的第1个像素方向定义为参考方向，后续码值均相对于前续的码值进行定义。图 5给出了用O3DVCC表示图像边界的示意，其中位于像素格子内的链码表示是VCC，位于像素格子外围带方向箭头的表示为O3DVCC。
|
图 5 O3DVCC示例 Figure 5 Example of O3DVCC |
O3DVCC将链码的方向特征与统计特征进行了融合，其中方向特征是相对的，统计特征是绝对的。由图 5不难发现，应用VCC表示的链码为1313131时，对应的O3DVCC链码表示为1111111；应用VCC表示的链码为3131时，对应的O3DVCC链码也表示为1111；VCC中的码值2与O3DVCC中的码值2保持一致。可以看出，O3DVCC将VCC中的码值1、3组合和3、1组合统一归并为带有方向性质的码值1。这为进一步压缩O3DVCC链码奠定了基础。
若以VCC为基准链码，其转换为O3DVCC的算法如下：
/*数组V[]存放VCC码值*/
/*数组N[]存放O3DVCC码值*/
Vertex2New (V[])
{
/*reference_section为参考段码值*/
reference_section=0;
/*i为O3DVCC码长*/
i=1;
While V[i] Not Null Do
{
If (V[i] == 2‖reference_section ==0)
Then
{
N[i]== V[i];
If (V[i]~=2)
Then
reference_section=V[i];
}
Else
{
If (reference_section == V[i])
Then
N[i]=3;
Else N[i]=1;
reference_section=V[i];
}
i=i+1;
}
}
同理，O3DVCC也可以转换为VCC，其算法如下：
/*数组V[]存放VCC码值*/
/*数组O[]存放O3DVCC码值*/
O2Vertex (O[])
{
i=1;
reference_section=0;
/* reference_section为参考段码值*/
While O[i] Not Null Do
{
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 O3DVCC码值概率与二进制编码 Table 2 O3DVCC code probability and binary code |
根据表 2，可知码值1和码值2的概率较为近似，远远超过了码值3出现的概率。这意味着图像轮廓中出现相对方向不同向变化的概率和方向不发生变化的概率要远大于出现相对方向同向变化的概率。基于该统计，可以对O3DVCC链码进一步改进。
2.2 改进的O3DVCC由于O3DVCC中码值1和码值2占有很大比例，因此对存在连续的码值1和连续的码值2进行改进，必定能够提高链码的压缩效率。在O3DVCC的基础上，新增了2个码值，分别表示M个码值1和N个码值2，定义该链码为改进的O3DVCC (Improved O3DVCC, IO3DVCC)。对100幅图像的边
界轮廓进行了统计，并基于Huffman编码为M=2，3，…，10且N=2，3，…，10共81种组合中每一组合的链码进行了二进制码值编码，同时计算了每一组合的链码平均表达能力，链码平均码长和链码的效率，如表 3所示。
|
|
表 3 IO3DVCC不同M、N组合对应的效率统计 Table 3 Efficiency statistics of different M and N combinations of IO3DVCC |
由表 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的对应关系 Table 4 Corresponding relationship of IO3DVCC and O3DVCC |
评价链码的主要指标是链码效率[12]，其公式可表示为：
| $e = c/l$ | (1) |
其中：e表示链码的效率；c代表码值平均表达能力；l代表平均码长。
码值的表达能力指码值所能表示的区域边界(或数字曲线)的像素长度的平均值，如图 6所示。
|
图 6 码值表达能力 Figure 6 Expression ability of code value |
8DFCC链码中码值0、2、4、6的表达能力为1个像素长度；码值1、3、5、7的表达能力为2个像素长度。4DFCC和VCC的所有码值表达能力均为1个像素长度。
链码的平均表达能力可表示为：
| $c = \sum\limits_{i = 1}^n {{c_i}} *{p_i}$ | (2) |
其中：ci为链码中某一码值的表达能力；pi为该码值出现的概率。
链码的平均码值长度，对于定长链码，其链码平均码长即为表达每位链码所需的bit。如，8DFCC链码由8个码值，每个码值用固定的3个bit进行表示，因此其平均码长为3 bit/码。
对于不定长链码，其链码平均码长可表示为：
| $l = \sum\limits_{i = 1}^n {{l_i}} *{p_i}$ | (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 不同链码的性能对比 Table 5 Performance comparison of different chain codes |
由表 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 图像轮廓边界 Figure 7 Image contour boundary |
|
|
表 6 图像尺寸及像素统计 Table 6 Image size and pixel statistics |
|
|
表 7 各链码相对图像轮廓链码的总码数与二进制总位数，以及相对于8DFCC的压缩比率 Table 7 Total code number and binary bit number of different chain codes with respect to image contour boundary chain code and their compression ratios with respect to 8DFCC |
链码存储的空间大小与码值数和链码的码值长度相关。相同码值数，码值长度多的链码势必要比码值长度少的更占用空间。表 7中，Arith_3OT、ICVCC和IO3DVCC的码值数相比8DFCC均有压缩，其中Arith_3OT的总码数最少，其次是ICVCC，而IO3DVCC相对较多。然而，由于Arith_3OT的链码长度均多于ICVCC和IO3DVCC，因此其所占存储空间并非最少。IO3DVCC的码值总数与ICVCC较为接近，但由于其链码长度少于ICVCC和Arith_3OT，因此所占存储空间最少。
从链码效率角度分析，链码效率越高，单位像素长度对应的码值表达能力越强，相对于同一种链码的压缩比率越高，压缩效果越明显。由表 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。基于100幅图像样本，统计了IO3DVCC、ERD8FCC、AVRF4、Arith_3OT、CVCC和ICVCC等链码各码值出现的概率，给出了码值的二进制编码表示，计算了码值平均表达能力、平均长度和链码效率，结果显示IO3DVCC链码的效率最高。在后续的实验验证中，统计了链码效率计算排名靠前的I3ODVCC、Arith_3OT和ICVCC在表达20幅随机图像样本中的码值总数、二进制总位数和相对于8DFCC的压缩比率，结果表明，IO3DVCC压缩效果最好。本文方法存在的不足是编码与解码方式较为复杂，时间消耗较大，因此，下一步的研究工作是对链码进一步改进，降低时间复杂度。
| [1] | FREEMAN H. On the encoding of arbitrary geometric configurations[J]. IRE Transactions on Electronic Computers, 1961, EC-10(2): 260-268. doi: 10.1109/TEC.1961.5219197 |
| [2] | BRIBIESCA E. A new chain code[J]. Pattern Recognition, 1999, 32(2): 235-251. doi: 10.1016/S0031-3203(98)00132-0 |
| [3] | SANCHEZ-CRUZ H, BRIBIESCA E, RODRIGUEZ-DAGNINO R M. Efficiency of chain codes to represent binary objects[J]. Pattern Recognition, 2007, 40(6): 1660-1674. doi: 10.1016/j.patcog.2006.10.013 |
| [4] | 刘勇奎. Freeman链码压缩算法的研究[J]. 计算机学报, 2001, 24(12): 1294-1298. ( LIU Y K. Research on the compression algorithm for Freeman chain code[J]. Chinese Journal of Computers, 2001, 24(12): 1294-1298. doi: 10.3321/j.issn:0254-4164.2001.12.009 ) |
| [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. doi: 10.1016/j.patcog.2007.03.001 |
| [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. ) |