四近邻图像的链码转换算法

四近邻图像的链码转换算法

1实验结果的提出数字图像处理是计算机科学的一个重要理论领域。计算机图形软件的一项关键技术。这与其他学科密切相关。计算机处理的图像包括灰色图像、彩色图像和两个值图像。其中两个值图像相对简单且重要。H.Freeman创造了二值图像的链码表示方法.链码的优点是十分明显的,它把二维图像的存储和处理变为一维链上的问题.对于大尺度的图像,链码可以大幅度地节省存储空间并提高处理速度.在Freeman之后已提出了多种链码方案.Bribiesca则对顶点链码做了系统的研究并做了推广.既然不同的链码表示的是同一个目标图像,它们之间是等价的,则应该可以相互转换.如果掌握了各种链之间的转换关系,那么从数字图像获得一种链码,也就能得到其他的链码.另外,图像的每一种链码都有它自己的优点和应用背景.例如,由Freeman链码可以便捷地计算图像的一阶矩、二阶矩等,从顶点链码可以获得图像区域的边界周长、图像的面积、图像区域密集度和体态比,利用顶点链码可以自动探测扫描文件的倾斜角度.于是有了链码之间的转换关系,链码获得的每一个有用结果都可以直接共享.因此有必要仔细分析和研究链码之间的关系.就作者所知,石秀和施泽生的论文实现了从Freeman链码到顶点链码的转化,首先提出并研究图像编码之间转化的这一具有实际意义的问题.从Freeman链码到顶点链码的转化固然必要,借此可以利用顶点链码的各种优良性质.不过Freeman链码也有许多好的性质,例如Freeman链码上可以直接利用GREGORYY.TANG的离散格林定理,高效地计算图形的矩.从理论的完整性的角度考虑,也有必要建立从顶点链码到Freeman链码的变换.另外,如同下文将具体解释的,Freeman定义的链码和E.Bribiesca介绍的链码之间是有区别的,我们权且把它称为边界链码.本文将较系统研究矩形点阵中链码间的相互转化.我们找到了顶点链码与边界链码之间的相互转换和Freeman链码与顶点链码之间的相互转换算法,因此可以在这些链码之间自由变换.最后给出了用边界标定自动机从图像获得顶点链码,通过前面提到的各种链码之间的转换,即可以得到各种链码,并给出了实验结果.2边界链码的标记在介绍正方形点阵上的链码前,我们先要明确边界像素的概念.和背景以八邻接意义上相邻的像素是四连通区域的边界像素.如图1所示(见下页),用0,1,2,3四个代码表示四个方向.从图像边界上的任一像素点开始,沿某一方向(本文中皆采用顺时针方向)依次连接边界像素,并用码记录链的行走方向,直到回到起始点为止,就构成了图像的Freeman链码.因此,图像Freeman链码可以表示为{(x0F,y0F)a0a1a2…al-1},(x0F,y0F)为图像边界上的起始像素点坐标,ai∈{0,1,2,3}是图像的四方位代码,l为链的长.如图2所示的图像,从点Q出发的Freeman链码表示为{(x0F,y0F)12212010101330001303232232}.(x0F,y0F)是起始点Q的坐标.Bribiesca采用边界像素的外边界来表记图形,并对链码做了系统的研究.从边界像素的某一顶点出发,沿着图像边界像素的边按一定的方向行走一周,记录边上的行走方向,构成一个有序链,加上起始点坐标,图像的边界也被唯一地确定下来.Bribiesca把这种标记图形的新的链码,也称作Freeman链码.其实两种链码的差别是十分明显的,有必要做出区分.因此我们把Bribiesca提出的这种链码称作边界链码.边界链码的表示为{(x0,y0)b0b1b2…bm-1},其中(x0,y0)是边界链码的起始点坐标,bi∈{0,1,2,3}.如图2,图像的边界链码表示为{(x0,y0)12212101010133001030332322322}.(x0,y0)为图像边界起始点P的坐标.论文中考虑的就是这种链.因此给出的是一种从边界链码到顶点链码的方法.Bribiesca还提出了用边界像素的顶点来标记图像的方法.对于正四边形点阵上的图像,可以有三种不同性质的顶点,如图3所示,分别用代码1,2,3来标记.沿着图像边界像素的顶点行走一周,依次记录图像边界像素顶点的代码,就得到顶点链码,图像的边界也被唯一地确定下来.图像顶点链码的表示为:{(x0,y0)/→c/c0c1⋯cn-1},其中(x0,y0)是顶点链码的起始点,→c为初始行走方向,ci∈{1,2,3}.如图4所示的图像的顶点链码表示为:{(x0,y0)/1/132131131313112323113121312312}.(x0,y0)是图像边界像素的顶点P的坐标,初始行走方向为1.3实现核心链码和边界链码之间的相互转换本节我们考虑链码之间的相互转换.我们首先实现顶点链码和边界链码之间的相互转换,然后研究顶点链码和Freeman链码之间的相互转换.这样就可以在这三种链码之间自由变换.3.1边界链码-点对点链码的转化假设图像的边界链码为{(x0,y0)b0b1b2…bl-1},当bi=bi-1时,其经过的顶点的代码是2,当边界链码的变化为,0→3,3→2,2→1,1→0则经过的顶点的代码为1,当边界链码的变化为3→0,2→3,1→2,0→1,则经过的顶点的代码为3.我们定义边界链码-顶点链码的转化函数C(bi-1,bi),其函数关系见表1.设顶点链码的起始点坐标为(x0,y0),初始方向为b0,由上面定义的转化函数,我们可以得到图像的顶点链码为{(x0,y0)/→c/c0c1⋯cl-1},其中→c=b0‚ci=C(bi-1,bi)‚i=0,⋯,l-1,当i=0时,bi-1=bl-1.3.2分配规则设图像边界的顶点链码为{(x0,y0)/→c/c0c1⋯cl-1}.假设b0=→c,沿着边界行走时,当经过像素的顶点的链码为1或3时,链改变方向,当经过像素顶点的链码为2时,链不改变方向.当经过的顶点链码为1时,链方向的变化规则为1→0,0→3,3→2,2→1;当经过的顶点链码为3时,链方向的变化规则为0→1,3→0,2→3,1→2.根据以上的分析,我们得到从顶点链码到边界链码的转换规则:b0=→c;当ci=2时,bi=bi-1;当ci=1时,bi=(bi-1+3)mod4;当ci=3时,bi=(bi-1+1)mod4;这里mod是模运算.由上面的转换规则,取边界链码起始点的坐标为(x0,y0),就获得图像的边界链码为{(x0,y0)b0b1b2…bl-1}.3.3b从结合点链码到也码到顶链码设图像的Freeman链码为{(x0F,y0F)a0a1a2…al-1}.因为顶点链码与Freeman链码行走的轨迹不同,所以Freeman链码的代码数与顶点链码的代码数不相同.使代码数发生变化的边界图形有三种,这些子链在顶点链码中的表示分别为12a1(a≥1),32b3(b≥0)和11,其中2a表示连续a个编码2.将图像中出现这几种子链的部分提取出来,如图6所示.当子链为12a1或11时,如图5(a)和(b),Freeman链码比顶点链码少1个编码2,当子链为32b3时,如图5(c),Freeman链码比顶点链码多1个编码2.下面分三步实现从Freeman链码到顶点链码的转换.第1步,确定顶点链码的起始点坐标和初始行走方向.假设顶点链码的初始行走方向为→c=a0,起始点坐标为(x0,y0).起始点坐标可由以下公式计算:当a0=0时,x0=x0F-0.5,y0=y0F-0.5;当a0=1时,x0=x0F-0.5,y0=y0F+0.5;当a0=2时,x0=x0F+0.5,y0=y0F+0.5;当a0=3时,x0=x0F+0.5,y0=y0F-0.5.第2步,引进伪顶点链码和伪顶点链码转化函数D(ai-1,ai),把四方向Freeman链码转化为伪顶点链码.D(ai-1,ai)的映射关系见表2.设得到的伪顶点链码序列为e0e1e2…en-1,其中ei=D(ai-1,ai)∈{1,2,3,4}.第3步,把第2步得到的伪顶点链码转换为顶点链码.扫描伪顶点链码,对12a1(a≥0)、32b3(b≥1)这两种子链做如下的替换:12a1⇒12a+1142a1⇒4a+1112a4⇒12a+14032b3⇒32b-13然后再把代码4替换为11.加上第1步得到的起始点坐标和初始行走方向,就得到了图像的顶点链码.3.4新链码的生成设图像的顶点链码为{(x0,y0)/→c/c0c2⋯cn-1},设Freeman链码的起始点坐标为(x0F,y0F).算法也有分三步.第1步,(x0F,y0F)的值由以下的公式计算:当→c=0时,x0F=x0+0.5,y0F=y0+0.5;当→c=1时,x0F=x0+0.5,y0F=y0-0.5;当→c=2时,x0F=x0-0.5,y0F=y0-0.5;当→c=3时,x0F=x0-0.5,y0F=y0+0.5.第2步,扫描顶点链码,先用代码0标记11子链,对12a1(a≥1)、32b3(b≥0)这两种子链做如下的替换:12a1⇒12a-1102a1⇒02a-1112a0⇒12a-1032b3⇒32b+13假设经替换后的新链码序列为e0e1e2…es,为新链码定义初始方向为→e如下:当e0≠0或e0=0且c0=cs-1=1时,e→=c→;当e0=0且c0=c1=1时,e→=(c→+3)mod4;第3步,对第2步得到的代码e0e1e2…es作替换处理,规则如下:d0=e→;当ei=2时,di=di-1;当ei=1时,di=(di-1+3)mod4;当ei=3时,di=(di-1+1)mod4;当ei=0时,di→d¯i-1.其中b¯是与b反方向链的代码,如0¯=2.这样我们就得到了图像的Freeman链码:{(x0F,y0F)d0d1d2…dt}4三种链码首先利用文献中定义的边界标定自动机获得图像的顶点链码.然后再由本文提供的转换算法,就获得了图像的边界链码和Freeman链码.如图6所示.我们通过边界标定自动机和转换算法获得图像L的三种链码分别为:顶点链码:边界链码:Freeman链码:5图像边缘链码和边界链码之间的转换图像的Freeman链码和顶