文章信息
- 魏小峰, 苗双喜, 濮国梁, 陈波, 程承旗
- WEI Xiaofeng, MIAO Shuangxi, PU Guoliang, CHEN Bo, CHENG Chengqi
- 应用于六边形网格的链码方法
- Chain Code Methods for Hexagonal Grids
- 武汉大学学报·信息科学版, 2019, 44(11): 1700-1707
- Geomatics and Information Science of Wuhan University, 2019, 44(11): 1700-1707
- http://dx.doi.org/10.13203/j.whugis20180018
-
文章历史
收稿日期: 2018-05-17
2. 96633部队, 北京, 100096
2. Troops 96633, Beijing 100096, China
链码是对目标离散边界的一种编码表示方法,通过记录边界上起始点之后各点的偏移方向来进行边界表达。目前,链码已被广泛应用于计算机视觉[1-2]、模式识别[3-4]、数字图像处理[5-6]以及地理信息系统[7]等各个领域。
最简单的链码就是跟踪目标边界并给每两个相邻像素的连线一个方向值,这便是四方向和八方向Freeman链码的基本思想[8]。四方向Freeman链码需要4个码值进行表达,可记为
由于四方向链码(F4)需要用折线代替斜线,表达同一边界的编码长度往往大于八方向链码(F8), 因此,Freeman八方向链码具有更好的实用性。此后,相继出现了多种新的链码及优化方法。如文献[9]提出依次记录在区域边界外轮廓线上的网格顶点数,从而得到一种新的链码——顶点链(vertex chain code,VCC)[9]。对于四边形网格,顶点链只需要1、2、3三个数字即可完成边界描述,分别对应边界网格的凸角转向、水平或垂直方向前进以及凹角转向,如图 2所示。类似地,VCC可表示为
文献[10-11]提出了直角三方向链码(orthogonal three-direction chain code, 3OT),它是将3个相对变化的直角方向作为码值对边界进行表达。3OT的码值有0、1、2,分别表示无方向变化、方向向前改变和向后回转,即
文献[12]提出了无符号曼哈顿链码(unsigned Manhattan chain code,UMCC)[12]。该链码只使用“0”和“1”两个码值记录边界网格中心连线沿x方向和y方向的前进,并利用3组“00”开头的标识码分别表示两个方向上的单调性变化情况。
以上列举的各种链码方法绝大部分是针对常见的正方形栅格,而对连续图像的离散化还可以按照三角形或六边形进行采样[13]。这3种模式均有固定的规格并能够无缝地覆盖2D平面。与四边形网格相比,六边形没有连通悖论,只有六连通一种情况,而且是等距方向最多的图形,采样密度也更高。六边形网格由于这些优势,近年来得到越来越多的重视和研究。
目前,唯一能直接用于六边形网格边界表达的链码方法为顶点链码。该链码只需要“1”和“2”两个码值即可完成对六边形网格的边界表达,如图 4所示。
研究发现,其他的四边形网格的链码方法可以根据其编码的基本原理进行扩展和改进,得到特性各异的六边形网格链码。本文主要研究如何将已有的链码方法(F8、3OT和UMCC)扩展应用于六边形网格的目标边界表达,并提出了一种基于边数的新的链码方法,对各种六边形网格链码的几何特性进行分析,通过实验比较这些链码的表达效率和压缩性能,得到定量结论。
1 六边形网格链码 1.1 六方向Freeman链码根据连通性不同,四边形Freeman链码分为4方向和8方向两种。而六边形网格的连通性唯一,且只存在边相邻,因此六边形网格的Freeman链码为六方向链码,6个方向分别由6个不同的码表示。仿照F4和F8的定义,沿逆时针方向,分别将相邻边界网格中心连线与x方向夹角为30°、90°、150°、210°和270°方向赋值0、1、2、3、4、5,如图 5所示。将六边形网格的六方向Freeman链码记为F6,则有
与四边形网格的F4和F8链码类似,F6记录的是由前一边界网格中心指向当前网格中心的绝对方向。正常情况下,每个边界网格唯一对应一个码,且每个码需要3 bit存储空间。图 6给出了用F6对六边形网格平面上某目标边界的编码结果。
1.2 左右二方向链码直角三方向链码的基本思想是将目标轮廓的前进方向分为3个相对变化的直角方向并分别表达;而六边形网格边界上轮廓的前进方向可以简化为两种:相对当前方向偏左60°(逆时针60°)或偏右60°(顺时针60°),如图 7所示。当方向偏左时,图中的斜线网格为外部网格,否则为边界网格,而经过任一六边形网格顶点的边界外轮廓线方向均只存在这两种情况。
多边形网格间的邻接关系决定了其可能的轮廓前进方向。四边形网格上每个顶点由4个四边形的90°角共有,因此经过该点的轮廓前进方向共有3种:向前(0°)、向左(逆时针90°)或向右(顺时针90°);而相比之下六边形网格上每个顶点由3个六边形的120°角共有,前进方向只有两种:偏左(逆时针60°)或偏右(顺时针60°)。因此,基于3OT相对变化方向的思想,六边形网格边界可由轮廓前进的两个相对偏转方向决定,记偏左为“1”,偏右为“2”,则外轮廓线上的方向可唯一确定。将该方法命名为左右二方向链码(left right 2-direction chain code, 2LR),以此对同样的目标边界进行编码,得到的结果如图 8所示。
不难发现,采用本文定义的码值进行边界表达,每个顶点处的链码值即为共顶点的边界网格数,即2LR的结果与VCC相同。两者均由边界网格顶点上的某种特性出发,虽然基本思想不同,但最终得到了相同的结果。因此,应用于六边形网格边界的2LR的几何特性与表达效率等均与VCC相同。
由于只需要两个码进行表达,因此每个码仅需要1 bit存储空间,左右二方向链码可由
对于四边形网格边界,无符号曼哈顿链码UMCC分别记录相邻网格中心连线沿边界前进时在x和y两个方向上的单调性变化,共分为4种情况:(1)单调性不变;(2)两个方向单调性均改变;(3)仅x方向单调性改变;(4)仅y方向单调性改变。UMCC将“00”作为识别码,表示该处的单调性发生变化;识别码之后由“11”“10”和“01”作为区分码,分别表示(2)、(3)、(4)3种情况。
而对于六边形网格边界,单调性变化情况有所改变。以图 9为例,深色网格为当前边界网格,虚线箭头指向可能的下一边界网格中心,斜线网格为前一边界网格,且假定目前x和y方向均为单调递增。结合F6链码,同样可将单调性变化情况分为4种:(1)F6=0, 1时,单调性不变,其中前者x、y均增加,后者x不变,y增加;(2)F6=2时,x方向单调性改变,y增加;(3)F6=3时,两个方向单调性均改变;(4)F6=4, 5时,y方向单调性改变,x不变或增加。
首先,在不考虑单调性变化的情况下,可分别用“1”和“0”表达x或y方向上相比前一网格是否有位移。位移码可直接作为单调性不变的边界网格码值。
其次,用“00”标识单调性发生变化的情况,将其称为标识码。如果在某一方向上发生变化,则用“1”表示,否则用“0”表示,表征单调性改变的码可称为区分码。因此,单调性仅x方向变化、仅y方向变化以及两个方向均变化可分别由“10”“01”和“11”表达。
由于仅y方向单调性变化时会有两种情况,因此需要再通过x方向上的位移码进一步区分,即用“1”和“0”分别表示此时x方向上是否有位移。
注意到指示单调性变化的区分码还有组合“00”尚未使用,可将其用于表达单调性变化与之前相同的情况。
因此,由一个边界网格到另一个的变化状态由3部分组成,分别是标识码、区分码与位移码,且可为空,每个边界网格的编码基本结构为“标识码x方向+标识码y方向+区分码x方向+区分码y方向+位移码”。
根据以上讨论可以得到基于单调性变化标识的六边形网格链码方法,码值具体分配情况如表 1所示,其中最后一列为对应的F6编码。为与UMCC进行区分,根据其基本原理,将该链码方法称为单调性标识链码(monotonicity identify chain code,MICC),记为
单调性 | 方向 | 标识码 | 区分码 | 位移码 | F6 |
x, y均不变 | x方向 | 0/1 | 0/1 | ||
y方向 | 1 | ||||
仅x变化 | x方向 | 0 | 1 | 2 | |
y方向 | 0 | 0 | |||
仅y变化 | x方向 | 0 | 0 | 0/1 | 4/5 |
y方向 | 0 | 1 | |||
x, y均变化 | x方向 | 0 | 1 | 3 | |
y方向 | 0 | 1 | |||
变化与之前相同 | x方向 | 0 | 0 | ||
y方向 | 0 | 0 |
分别用“↑”和“↓”表示单调递增和单调递减,则沿逆时针方向目标区域边界的单调性变化如图 10所示,每个边界网格上两个箭头方向依次指示了该网格在x方向和y方向上的单调性,其中单调性发生变化的网格由深色表示。
对照表 1和图 10,可以得到MICC对基于六边形网格的目标区域边界表达结果,如图 11所示。其中,每一边界网格内上下分别为x方向和y方向上的编码结果。可以发现,利用MICC表达单调性没有变化的边界网格需要2 bit,否则需要4~5 bit。单调性变化越少,则整体编码长度越短。
1.4 边链码除以上方法之外,还可以通过统计目标外轮廓线上的各边界网格的边数实现目标边界表达。将这种基于边数统计的链码方法称为边链码(edge chain code,ECC)。六边形网格上边界网格可能边数为1~5,如图 12所示。在确定六边形网格每个边界网格在外轮廓上的边数后,下一边界网格的相对位置也唯一确定。因此,只需要依次记录每个边界网格的边数即可完成对整个目标边界的表达。
适用于六边形网格的边链码可由1、2、3、4、5五个码值表达,码值与边数一一对应,此时每个边界网格需占用3 bit。其中,码值“5”对应于边界上的突出点或线段的端点,如图 6中最右端的边界点。这在实际情况中出现的频率非常小,可考虑将其替换为其他不会出现的码值组合,以提高压缩率。如组合“444”,按照边链码的定义,只可能用于表达图 13 (a)这唯一一种情况,因此满足替换条件。将“444”用于表达边数为5的特殊情况,如图 13(b)所示。替换之后,六边形网格的边链码可表达为
图 14展示了六边形网格边链码的编码结果。
2 链码几何特性分析应用于四边形网格的链码的几何特性已有系统总结[12],在此基础上,本文分别对提出的4种六边形网格链码特性进行分析与比较。
2.1 F6特性分析F6的几何特性主要体现在可检测直线段并能够区分其方向,归一化后的编码结果与起始点选择无关。具体分析如下:
1) F6链码的不同码值代表边界网格中心连线的不同方向,因此同一码值序列即表达边界网格在该方向上的直线段。其中,“11…1”和“44…4”表示垂直方向的直线段,而其他相同码值序列则分别表示与垂直方向夹角为30°或60°的直线段。
2) 将链码看作一个自然数,则将其中各个码值按某一个方向循环使其构成的自然数值最小,这个过程就是归一化。如图 6中F6归一化后结果为0001011101032121132322233433355055444 4544。
由于F6链码表达边界中心连线的绝对方向,因此编码结果会因旋转和翻转操作而发生变化,即不具备旋转或翻转不变性。
2.2 2LR/VCC特性分析由于2LR和VCC编码结果相同,因此其几何特性也完全相同,主要包括可检测直线段、旋转不变性、翻转不变性以及方便计算曼哈顿距离下的轮廓周长。具体分析如下:
1) 在2LR中,序列“1212…12”表示直线段,但与F6不同的是,无法从编码判断直线段的具体方向。
2) 2LR同样能够通过归一化保证链码结果与起始点无关。
3) 由于2LR是由外轮廓的前进相对方向决定的,因此编码结果不受旋转或翻转操作的影响。
4) 用曼哈顿距离表示的轮廓周长即边界网格在外轮廓线上的边数之和,这也与其顶点数相同。因此2LR的总码数即为轮廓周长。
2.3 MICC特性分析MICC的编码较为特殊,基本特性包括可检测不同方向的直线段,具有旋转和翻转不变性等。除此之外,由于MICC的基本原理是标识边界上的单调性变化,因此其独特特性在于检测轮廓上的单调区间。
首先,垂直方向上的直线段单调性不变,只有y变化,编码为“0101…01”,而倾斜方向上的直线段x和y均会变化,在编码形式上体现为序列“1111…11”;然后,旋转和翻转等操作不会改变轮廓上的单调性变化,因此MICC具有旋转和翻转不变性;最后,轮廓上的单调区间可通过标识码与区分码进行判断。
2.4 ECC特性分析ECC的特性与2LR/VCC相似,具有可检测直线段、归一化后与起始点选择无关、旋转及翻转不变性以及方便计算轮廓周长等。
其中,序列“22…2”表示边界上的直线段;外轮廓上的边数不受旋转或翻转影响;轮廓周长的计算与2LR相似但有区别,根据边链码定义,目标轮廓的周长可以通过将ECC各码值相加来得到。
总的来说,六边形网格链码方法的几何特性由各链码基本原理决定,如三种基于边界网格外轮廓顶点或边的链码方法2LR、VCC与ECC的几何特性相似,而且六边形新链码的特性与对应的原始链码方法基本一致。
3 链码表达效率与压缩性能比较除了链码的几何特性之外,对链码的研究还通常关注其表达效率及压缩性能[14]。目前已出现多种针对四边形网格链码的压缩优化方法[15-17]。
表达效率可以通过表达每个边界网格所需的平均码数Sg反映,而压缩率同样可反映为记录每个边界网格位置所需的平均位数Bg。下面分别从这两个方面对提出的六边形网格链码方法进行比较分析。
3.1 表达效率比较表 2展示了利用F6、2LR/VCC、MICC和ECC4种方法对图 6中目标边界进行编码的结果。其中,编码统一从图 6中深色边界网格开始,沿逆时针方向进行。
链码 | 编码结果 |
F6 | 13232223343335505544445440001011101032121 |
2LR/VCC | 2111221122121211212112211212112121122122121212112212111212121122112121221121111122211221 |
MICC | 01001010000000000001111000011011101010100110010100001101010101110101000011110111010101110111010100101011101 |
ECC | 4131223231323231212223123223132213144411312 |
通过表 2可直观发现不同链码之间表达效率的差异。F6和ECC在正常情况下平均每个码均对应一个边界网格,即Sg=1;其次是2LR/VCC,由于每个边界网格上的顶点数可能为1~5个,因此其表达效率会低于F6和ECC,具体取决于轮廓形状;而MICC只能由二进制表达,总码数也最长,在单调性无变化情况下,Sg=2,单调性改变时Sg=4,整体的平均码数大于2。
为量化分析链码的表达效率和压缩性能,选取12个不同形状的物体(骆驼、鹿、虎、狗、蝴蝶、鸟、螃蟹、树、飞机、笔、人物、地图)进行实验。将这些物体的形状用六边形网格进行离散,并分别统计利用F6、2LR、MICC和ECC 4种方法所得到的链码总码数、均值及平均码数Sg,实验结果如表 3所示。
物体 | F6 | 2LR/VCC | MICC | ECC |
骆驼 | 1 258 | 2 534 | 2 990 | 1 272 |
鹿 | 1 058 | 2 122 | 2 441 | 1 058 |
虎 | 977 | 1 960 | 2 364 | 977 |
狗 | 2 891 | 5 788 | 6 814 | 2 891 |
蝴蝶 | 1 906 | 3 826 | 4 144 | 1 910 |
鸟 | 1 864 | 3 740 | 4 630 | 1 872 |
螃蟹 | 3 839 | 7 681 | 9 556 | 3 839 |
树 | 3 106 | 6 263 | 8 031 | 3 144 |
飞机 | 1 287 | 2 577 | 3 360 | 1 287 |
笔 | 1 802 | 3 610 | 3 995 | 1 802 |
人物 | 1 702 | 3 415 | 3 764 | 1 706 |
地图 | 2 265 | 4 556 | 5 405 | 2 285 |
均值 | 2 455 | 4 929 | 5 909 | 2 467 |
Sg | 1 | 2.0077 | 2.4069 | 1.0049 |
实验结果进一步验证了之前对各链码表达效率的分析。其中,部分实验中ECC码数略高于F6,这是由ECC中“444”替换“5”所产生的,总体上两者表达效率最高;2LR及VCC平均需要2个码来表达一个边界网格;虽然MICC与2LR/VCC均由二进制表达,但前者的表达效率显然更低,平均码数Sg=2.4。
3.2 压缩性能比较根据链码的定义,容易得到各链码的总长度(比特数)与码数的关系。其中,F6链码一共6个码值,每个码值需要3 bit存储空间;2LR、VCC和MICC均只有2个码值,每个码值仅需要1 bit空间,即码数与位数相同;经过码值替换的ECC只有4个码值,每个码值刚好需要2 bit空间。根据这一换算关系,可以由表 3得到以位数为单位的不同链码总长度,并统计得到存储每个边界网格信息所需的平均位数Bg,如表 4所示。
物体 | F6 | 2LR/VCC | MICC | ECC |
骆驼 | 3 774 | 2 534 | 2 990 | 2 544 |
鹿 | 3 174 | 2 122 | 2 441 | 2 116 |
虎 | 2 931 | 1 960 | 2 364 | 1 954 |
狗 | 8 673 | 5 788 | 6 814 | 5 782 |
蝴蝶 | 5 718 | 3 826 | 4 144 | 3 820 |
鸟 | 5 592 | 3 740 | 4 630 | 3 744 |
螃蟹 | 11 517 | 7 681 | 9 556 | 7 678 |
树 | 9 318 | 6 263 | 8 031 | 6 288 |
飞机 | 3 861 | 2 577 | 3 360 | 2 574 |
笔 | 5 406 | 3 610 | 3 995 | 3 604 |
人物 | 5 106 | 3 415 | 3 764 | 3 412 |
地图 | 6 795 | 4 556 | 5 405 | 4 570 |
均值 | 7 366 | 4 929 | 5 909 | 4 934 |
Bg | 3 | 2.0077 | 2.4069 | 2.0098 |
从表 4可以发现,基于边界网格外轮廓顶点或边信息的2LR、VCC和ECC 3种链码方法的位数非常接近,整体长度最短,平均位数Bg=2;其次为MICC,平均每个边界网格需要2.4 bit空间;F6链码位数为码数的3倍,总长度最长。以F6链码位数为基准,可计算其他链码相比于F6的压缩率,其中2LR、VCC和ECC的压缩率均为67%,MICC的压缩率约为80%。
通过以上的分析可以发现,ECC的表达效率与压缩性能均接近最优,Sg与F6相比、Bg与2LR相比均相差不超过5%,综合而言是较好的六边形网格链码方法。
4 结语本文将3种典型的四边形网格链码方法扩展应用于六边形网格边界表达,同时提出一种基于边数的新链码方法。其中,基于绝对方向数的F6链码表达效率最高,但压缩率低,且不具有旋转和翻转不变性;2LR记录边界各顶点处相对偏转方向,其编码结果、几何特性、压缩率等均与VCC相同;基于单调性变化标识的MICC在六边形网格上不再具有压缩率高的优势;ECC方法将外轮廓上各边界网格的边数作为码值,并将特殊情况的码值进行替换,从而提高压缩率,其几何特性与2LR相似。
总体而言,这4种方法均能实现六边形网格的边界表达,其中边链码在表达效率和压缩性能两方面均接近最优,在实际应用中可根据需要进行选择。
[1] |
Jain J, Sahoo S K, Prasanna M, et al. Modified Chain Code Histogram Feature for Handwritten Character Recognition[J]. Lecture Notes of the Institute for Computer Sciences, 2012, 84(1): 611-619. |
[2] |
Rachmawati E, Supriana I, Khodra M L. Bag-of-Shapes Descriptor Using Shape Association Based on Freeman Chain Code[J]. Journal of Theoretical and Applied Information Technology, 2017, 95(5): 1142-1153. |
[3] |
Lee D, Kim S J. Modified Chain-Code-Based Object Recognition[J]. Electronics Letters, 2015, 51(24): 1996-1997. DOI:10.1049/el.2015.1019 |
[4] |
Zhao Like, Song Weidong, Wang Jingxue. Straight Line Extraction Algorithm of Freeman Chain Code Priority[J]. Geomatics and Information Science of Wuhan University, 2014, 39(1): 42-46. (赵丽科, 宋伟东, 王竞雪. Freeman链码优先级直线提取算法研究[J]. 武汉大学学报·信息科学版, 2014, 39(1): 42-46. ) |
[5] |
Madenda S, Wibowo E P. Object Feature Extraction of Songket Image Using Chain Code Algorithm[J]. International Journal on Advanced Science, Engineering and Information Technology, 2017, 7(1): 235-241. DOI:10.18517/ijaseit.7.1.1479 |
[6] |
Tawfiq A, Asadi A, Fanar A J. Removing Spatial Redundancy from Image by Using Variable Vertex Chain Code[J]. European Academic Research, 2014, 2(1): 179-192. |
[7] |
Ren M, Karimi H A. A Chain-Code-Based Map Matching Algorithm for Wheelchair Navigation[J]. Transactions in GIS, 2009, 13(2): 197-214. DOI:10.1111/j.1467-9671.2009.01147.x |
[8] |
Freeman H. On the Encoding of Arbitrary Geometric Configurations[J]. IRE Transactions on Electronic Computers, 1961, 10(2): 260-268. |
[9] |
Bribiesca E. A New Chain Code[J]. Pattern Recognition, 1999, 32(27): 235-251. |
[10] |
Cruz S H, Dagnino R M R. Compressing Bi-level Images by Means of a 3-bit Chain Code[J]. SPIE Optical Eng, 2005, 44(9): 1-8. |
[11] |
Sánchez-Cruz H, Bribiesca E, Rodríguez-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 |
[12] |
Žalik B, Domen M, Liu Y K, et al. Unsigned Manhattan Chain Code[J]. Journal of Visual Communication and Image Representation, 2016, 38: 186-194. DOI:10.1016/j.jvcir.2016.03.001 |
[13] |
Machand-Maillet S, Sharaiha Y M. Binary Digital Image Processing:A Discrete Approach[M]. Netherlands: Academic Press, 1999.
|
[14] |
Sdnchez-Cruz H, Bribiesca E, Rodriguez M A. Efficiency of Chain Codes to Represent Binary Objects[J]. Pattern Recognition, 2007, 40(6): 1660-1674. DOI:10.1016/j.patcog.2006.10.013 |
[15] |
Liu Y K, Zalik B. An Efficient Chain Code with Huffman Coding[J]. Pattern Recognition, 2005, 38(4): 553-557. DOI:10.1016/j.patcog.2004.08.017 |
[16] |
Sánchez-Cruz H. Proposing a New Code by Considering Pieces of Discrete Straight Lines in Contour Shapes[J]. Journal of Visual Communication and Image Representation, 2010, 21(4): 311-324. DOI:10.1016/j.jvcir.2010.02.002 |
[17] |
Yu Guofang, Wang Li. Research on Compression-type Vertex Chain Code[J]. Journal of Image and Graphics, 2010, 15(10): 1465-1470. (于国防, 王莉. 压缩型顶点链码的研究[J]. 中国图象图形学报, 2010, 15(10): 1465-1470. ) |