图像拼接的并行实现方法

255××理论计算机科学电子笔记46（2001）网址：http://www.elsevier.nl/locate/entcs/volume46.html14页关于图象P. Helen Chandra1，K. G. Subramanian2和D. G. 托马斯数学系，马德拉斯基督教学院，Tambaram，钦奈（原马德拉斯）600 059，印度D. L. Vanb河内数学研究所，P.O.Box 631 BoHo，10000 Hanoi，Vietnam摘要介绍了图像拼接的概念，并提出了图像拼接的并行实现方法这是在DNA计算背景下广泛研究的字符串拼接操作的扩展各种性质的图像拼接检查。1介绍七十年代引入的L -系统用于模拟生物发展，它开创了并行重写字符串的应用，并以重大发展丰富了形式语言理论和生命科学[4，7]。剪接系统是Head [2]最近基于生物学考虑引入的另一个模型。这些系统旨在模拟DNA分子的某些重组行为，并且是当前感兴趣和研究的[3]。另一方面，在生成和识别被视为数字化数组的图像或图片的句法方法中，已经提出并研究了几种二维文法[6]。将L-系统类型重写推广到数组，文[8]提出了一个生成模型.在[1]中，已经将局部和可识别的字符串语言的概念优雅地推广到最近，Krithivasan等人[5]将拼接的概念扩展到阵列并定义了阵列拼接系统。本文介绍了一种对矩形阵列图像进行拼接操作的新方法。拼接规则，涉及2 1或1 2多米诺骨牌被认为是。两个数组是列拼接或行拼接，通过使用并行多米诺拼接规则。 由此产生的模型称为H阵列1电子邮件地址：chandrajac@yahoo.com2电子邮件地址：kgsmcc@kmronline.com2001年由ElsevierScienceB出版。 诉 在CCBY-NC-ND许可下开放访问。CHANDRA，SUBRAMANIAN，THOMAS和 VAN256×拼接系统是一种操作简单的图形语言生成机制。考虑了几何运算和语言理论运算下的一些闭包结果。本文的研究可能有助于更好地分析图像的结构2基本定义设字母表为有限字母表。Σ∗ is the set of all words over Σ includingtheempty wordλ.一个图像或一张图片在屏幕上是一个矩形阵列的元素。所有图像的集合用表示。 尺寸为m的图像或图片 n是以下形式的数组a11a 12a 13···a1na 21a 22a 23···a2n··················am1 am2 am3 ···amn或简称为[a ij] m×n。图语言或二维语言是图语言的子集。设A=a11···a1p···am1··· amp得双曲正切值.b11···b1q···bn1··· bnqA和B的列连接AΦB仅在m=n并由下式给出AΦB =a11···a1pb11···b1q············am1··· amp bn1··· bnq类似地，A和B的行级联AΘB仅在以下情况下定义：CHANDRA，SUBRAMANIAN，THOMAS和 VAN257≤≤p=q，由下式给出：AΘB =a11··· a1p······am1···ampb11···b1q······bn1··· bnq如果L1、L2是字母表上的两种图像语言，则L1和L2的列连接L1ΦL2定义为：L1 Φ L2={A Φ B|A∈L1，B∈ L2}.L1和L2的行级联L1θL2定义为：L1 Θ L2={A Θ B|A∈L1，B∈ L2}.我们回顾了局部和可识别的图像语言的概念[1]。给定一个大小为（m，n）的图像A，我们用Bh，k（A）表示，对于hm，kn，集合A的大小为（h，k）的所有块（或子图片）。我们把一个大小为（2，2）的正方形图片称为瓦片。设Γ是一个有限的字母表。二维语言L<$r <$<$r是局部的，如果存在字母表r <${#}上的有限瓦片集θ，使得L={A∈r <$r <$}|B2，2（A）<$θ}其中A是一个大小为（m+2， n+2）的图象，它是用一个特殊的有限性mbol#∈/Γ包围A而得到的。例2.1由所有大小的数组A（图1a）组成的描述1Js的标记L（将0Js解释为空白）（图1b）的图片语言M是本地语言。1 0 0 0 0 011 0 0 0 0 011 0 0 0 0 011 0 0 0 0 011 1 1 1 1 11 1 1 1 1 1图1a. 描述记号L图1b.令牌L（共1个CHANDRA，SUBRAMANIAN，THOMAS和 VAN258→⊆联系我们--的对应集合#11##1， 0#，# #，# #，1 0， 00电话：+86-10 -8888888传真：+86-10-88888888θ= #1， 0#，# #，1#，1 0， 001 0 0 02011年11月11日，平铺系统（TS）是一个4元组T =（TS）。r，θ，π），其中，r和r是两个有限字母表，θ是字母表r上的瓦片的有限集合，和π：Γ π是一个投影。平铺系统T在字母表上定义语言L如下：L=π（LJ）其中LJ=L（θ）是局部语言在对应于瓦片集合θ的Γ上。 我们写L = L（T）。 我们说一个语言L可被镶嵌系统识别（或镶嵌可识别），如果存在镶嵌系统T =（，Γ，θ，π）使得L = L（T）。我们表示由L（TS）的家庭的所有二维语言可识别的平铺系统。 换句话说，L∈L（TS），如果它是某个局部语言的投影。在文献[1]中已经研究了使用语法生成图片的不同系统我们在这里回顾模型，包括两套重写规则：水平和垂直的规则，分别。这些模型首先使用水平规则生成（水平）字符串σ;然后生成 通过应用平行垂直规则从顶行σ开始的矩形图片。这些语法实际上形式化了二维语言的并行生成。二维右线性文法（2RLG）由7元组定义G=（Vh，Vv，I，，S，Rh，Rv），其中Vh是水平变量的有限集合;Vv是垂直变量的有限集合; IVv是中间变量的有限集合;是终端变量的有限集合;S∈Vh是起始符号;Rh是形式为S1→AS2或S1→A的水平规则的有限集合，其中S1，S2∈Vh，A∈I;Rv是形式为W→aWJ或W→a的垂直规则的有限集合其中W，WJ∈V v，a∈ V。实施例2.2设G=（Vh，Vv，Rh，Rv）是一个文法，其中：Vh={S，T};Vv={A，B，C，D};I={A，B};={ 0， 1};Rh={S→AT;T→BS;T→B};R v={A → 1 C; C → 0 A; C → 0; B → 0 D; D → 1 B; D → 1。}在第一阶段，G生成字符串语言H（G）= AB+。在第二阶段，从被认为是图像的顶行的H（G）的串CHANDRA，SUBRAMANIAN，THOMAS和 VAN259L通过应用R v中的垂直规则，我们得到由G生成的图像语言L的数组，它是偶数边长的“棋盘”图像的集合;即，以下形式的图片：所代表1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 11代表黑色，0代表白色。我们用（2RLG）表示由二维右线性文法生成的图像语言族.文[5]中介绍的数组拼接系统是Head [2]最初考虑的弦上拼接系统的推广我们参考[5]了解阵列拼接系统的详细信息。我们非正式地描述这个想法。在[5]中考虑了四种类型的拼接。这里的想法是，拼接中涉及的阵列X和Y被适当地“分割”成子阵列，“交叉”，即X和Y的子阵列需要相同以进行拼接。‘Type-3H阵列拼接系统我们现在介绍H阵列剪接系统的主要概念。定义3.1设V是一个字母表。 #、$是两个特殊的符号，在诉V上的多米诺骨牌的形式是或 ab，a，b∈ V。V上的多米诺列拼接规则的形式为r=α1#α2$α3#α4其中，每个αi=对于a，b∈V或 αi=其中，λ是空字。一B一BλλCHANDRA，SUBRAMANIAN，THOMAS和 VAN260bi+1，kbi，kai+1，j+1ai，j+1ai+1，jai，j|···≤≤V上的多米诺骨牌拼接规则的形式为r=β1#β2$β3#β4其中，每个βi=对于a，b∈V或βi=λ λ。给定两个大小分别为m×p和m×q的数组X和Ya11 ···al，j a1，j+1 ···a1pX=a 21···a 2，ja 2，j+1···a 2p······am1 ···am，j am，j+1 ···一个mpB11 ···b 1，k b1、k+1 ···b1qY=b 21···b 2，kb 2，k+1···b 2q······bm1 ···bm，kbm，k+1 ···bmq我们写（X，Y）ΦZ如果存在列拼接规则r1，r2，r3，，rm−1并不是所有的都不同，ri=#$#对于所有i，（1≤i≤m− 1）和对于某些j，k（1≤j≤p）和（1≤k≤q），a11 ···ai，j b1、k+1 ···b1qZ=a 21···a 2，jb 2，k+1···b 2q······am1···am，jbm，k +1···bmq特别地，如果任何符号a ij是λ，则对于所有i，（1 ≤ i ≤ m），aij=λ。 对于ai，j+1，bi，k，bi，k+1（1我m）。 我们知道Z是由X和Ya Bbi+1，k+1bi，k+1CHANDRA，SUBRAMANIAN，THOMAS和 VAN261通过多米诺柱平行拼接得到的。我们可以类似地定义两个数组U和V的行拼接操作，CHANDRA，SUBRAMANIAN，THOMAS和 VAN262bk，j+1bk，jai+1，j+1ai+1，jai，j+1ai，j|···⊆使用行拼接规则来调整p×n和q×n的大小以产生阵列W。a11a 12a 1n·········U=ai，1ai，2 ···ai，nai+1，1ai+1，2···ai+1，n·········ap1ap 2apnb11b12b1n·········V=bk，1bk，2 ···bk，nbk+1，1bk+1，2···bk+1，n·········bq1bq 2bqn我们写（U，V） 如果存在行拼接规则r1，r2，r3，rn-1，则ΘW不全是不同的，使得ri=#$#对于所有j，（1≤j≤n− 1）和对于某些i，k（1≤i≤p）和（1≤k≤q），a11a 12a 1n·········W=ai，1ai，2 ···ai，nbk+1，1bk+1，2···bk+1，n·········bq1bq 2bqn我们现在说W是通过多米诺骨牌行并行拼接从U和V定义3.2我们定义了一个H阵列方案和一个H阵列拼接系统。一个H数组方案是一个三元组Γ =（V，Rc，RR），其中V是一个字母表，Rc=多米诺列拼接规则的有限集合，RR=多米诺行拼接规则的有限集合对于给定的H数组方案Γ =（V，Rc，Rr）和语言L V，我们定义了Z∈V|（X，Y）| ΦZ或（X，Y）| ΘZ对于某个X，Y∈L，Γ（L）=πpi∈Rc且qj ∈Rr（1≤i≤m −1），（1≤j≤n −1）换句话说，Γ（L）由使用阵列列或行拼接规则通过列或行拼接L的任何两个阵列迭代地定义bk+1，j+1bk+1，jCHANDRA，SUBRAMANIAN，THOMAS和 VAN263B aB aλ λλ λb a，baλΓ0（L）=LΓi+1（L）=Γi（L）Γ（Γi（L）），i≥0r（L）=i≥0Γ i（L）.H阵列拼接系统定义为S =（Γ，I），其中Γ =（V，Rc，RR），I是V的有限子集。S的语言定义为L（S）= Γ（I），我们称之为拼接数组语言，并表示此类语言FHA的。我们用一个例子来说明。例3.3设V={a，b}a bI=B aa λ λbRc=p1：#bλbλp2：# $a λ$#λ aλa#λbRr=、q1：a b#λ λ$λ λ#、问2：# $#在使用p2并行进行列拼接时， a b产量- 是 的.ΣΦΣΣ学士 λλ。a Bb a. λ，λ。B a|a b a bb a b a我们已经显示了空列λ以指示拼接完成了同样，使用q1，q2并行拼接行，a B a Bλ λ λ λab abΘb a ba b ab a b|babaλ，b a b aa b a bb a b aL是由所有边长相等的“棋盘”组成的语言a b a b b ba b b a b bb a b b b ab b b a b bb a b b b ab b b定理3.4局部数组语言的类FHA和拼接数组语言的类FHA不可比但不相交。a BCHANDRA，SUBRAMANIAN，THOMAS和 VAN26401 1λ λ0 01 1λ λa aλ λλ λ× ≥≥- -证据由描述1的标记L的所有m n个数组（m 2，n 2）组成的图像语言M在图中。M的一个成员如图1a所示。现在我们给出一个H阵列拼接系统S =（V，Rc，Rr，I）来描述M.设V={0，1}Rc=p1：#p2：#$#$#Rr=、问题1： #$#、问2：#$#和I=1 01 1已知在V=a上具有3列的所有图像（图2）的图像语言L不处于正态。但它是通过H阵列拼接系统获得的，I = aa aRr=#$#且Rc= 1。正方形图像的图片语言，其中对角线位置带有符号1，但其余位置带有符号0（图3）是在[1]中。但它不是在FHA中，因为从行和列拼接的定义中可以清楚地看到，不能生成只有正方形大小的图片a a a1 0 0 0a a a0 1 0 0a a a0 0 1 0a a a0 0 0 1图2图3✷注3.5类FHA与L（TS）相交，因为类FHA与L（TS）相交。定理3.6类FHA与L（2RLG）相交证据结果表明，边长相等的“棋盘”图形语言是由FHA生成的，并且是由a2个激光陀螺[1]。✷1 00 0a a01001λλλλ11110100CHANDRA，SUBRAMANIAN，THOMAS和 VAN265λ$λλ$λλ λλ λ. XXXXXXXX.XXXX≤ ≤ ≤≤XX定理3.7类FHA与[5]的空上下文拼接数组语言类相交。证据 令网格表示大小<为m，n>的图像G，其中m，n是奇正整数m，n≥3，G由下式给出：如果i是奇数或j是奇数，G[i，j] =0Y否则其中1im，1Jn. G被称为定义在上的大小为的网格。 网格表示上所有网格的集合。GRIDS X的成员<。”如图所示。四、我的天啊 X .X . 我的天啊X . X . 我的天啊 X . X . 10Xx X x x x x X图4. 网格已知网格是空上下文拼接数组语言[5]，我们给出了一个H数组拼接系统S =（V，Rc，Rr，I），生成了它.令V ={X，. {\fn黑体\fs22\bord1\shad0\3aHBE\4aH00\fscx67\fscy66\2cHFFFFFF\3cH808080}XXI=网格= X。 XRC=p1：#p2：#XX X#联系我们Rr=、问题1：#$#、问题2：#$##注3.8我们现在考虑两个字符串的行列组合，X.XX.XXXCHANDRA，SUBRAMANIAN，THOMAS和 VAN2661$1λ λ1x1λ λλ λλ λλ λλ λ一个2B2C1D1B2一个2D1C1B1的1B2一个2D1C1B1的1X2X1X2X1语言[1]。设V是一个有限字母表，S1和S2<$V <$是V上的两种字符串语言。 S1和 S2的行列组合是一种图像语言L=S1<$S2<$V <$$>，使得图像p∈V<$<$属于L当且仅当对应于p的行和列的字符串属于S1和S2分别本文给出了FHA中的一种行列组合图形语言L的一个例子这里L由V={ 0， 1}上的所有图像组成，其第一列和最后一列仅由1事实上，L=（{1}S1{ 1}）<$V<$其中S1<$V<$。100x11mm设V={ 0， 1}I={0，1}1x21其中x i= 0或1（i = 1，2）。Rc=p1：#、#和Rr=q1：#$#问题二：问三：#$#、#$#现在我们来看看某些闭包的结果：定理3.9类FHA在基底和右腿上的反射以及旋转90 °、180 °和270 °下是封闭的。证据 我们首先证明了FHA在反射下是闭的。设S=（Γ，I），其中Γ =（V，Rc，Rc），I是V的有限子集，V是一个拼接系统，Rc中的规则如下p=#$#在Rr中，q=#$#描述一种图像语言L.由L阵列在基底上的反射图像组成的图像语言可以通过由以下形式#$#111x1X11X11C2D2的1B1D2C2D2C2X2X1X2X1CHANDRA，SUBRAMANIAN，THOMAS和 VAN267D1C1B2一个2一个2B2C1D1C1D1一个2B2C1D1一个2B2一个2B2C1D1D1C1B2一个2一个2B2C1D1D1C1B2一个2D1C1B2一个2对应于p和形式#$#对应于q。类似地，右腿上的L阵列的反射可以通过具有修改规则的H#$#和#$#分别对应于p和q。接下来我们证明FHA在90 °、180 °和270 °旋转下是闭的。我们只提到Rc和Rr的修正规则#$#和旋转90度;#$##$#和旋转180度;#$##$#和#$#旋转270度。✷定理3.10类FHA在并和连接下不是闭的。证据设L1是一种语言，由3行任意列的数组组成，左边框由a组成L1的成员如图所示。五、B1的1D2C2C2D2的1B1的1B1C2D2的1B1C2D2C2D2的1B1B1的1D2C2C2D2的1B1B1的1D2C2B1的1D2C2CHANDRA，SUBRAMANIAN，THOMAS和 VAN268∪∪组织：体操队形x x xx x b五、类似地，让L2是另一种数组语言，就像L1一样，但是左边界由C组成，右边是D。很明显，L1L2的成员将分别只有a和b的左边界和右边界生成L1L2所需的任何列拼接规则都必须增加x的内部列但在列拼接上，两个初始数组的形式a x Ba x b， ax bc x dc x dc x d的H阵列拼接系统将产生具有左右边界的阵列，aJs和dJs或cJs和bJs。这些不是L1和L2的元素.同样，两个初始数组的列拼接形式如下：a x b c x da x b c x da x b c x d可能产生L1 Φ L2的H阵列拼接系统将产生不在L1 Φ L2中的阵列。类似的参数也适用于行连接。结论本文试图以一种简单而有效的方式将拼接操作推广到矩形阵列图像。虽然这个新系统与[5]的数组拼接系统相交，但它仍然可以找到这个类的确切位置。确认作者K.G. Subramanian和D.G.托马斯要感谢河内数学研究所，越南延长支持他们访问研究所在10月至11月，1999.作者感谢D.L.Van教授的合作。CHANDRA，SUBRAMANIAN，THOMAS和 VAN269−−引用[1] Giammarresi ， D. 和 A.Restivo ， Two-dimensional Languages ， InHand- Book of Formal Languages ， eds.G.Rozenberg 和 A.Salomaa ，Springer Verlag3（1997），215-265.[2] 海德，T.，形式语言理论与DNA：特定重组行为的生成能力分析。数学Biology，49（1987），735-759.[3] 海德，T.， 嗯P. Pixton，语言理论和分子遗传学：DNA扩增所建议的生成机 制 ， 形式语言手册，编辑。G. Rozenberg和A. Salomaa，SpringerVerlag2（1997），295-358.[4] Herman，G. T.和G. Rozenberg，[5] Krithivasan ， K. ， 诉 T. Chakaravarthy 和 R.Rama， Array SplicingSystems ， InComputingwithBio-molecules ： TheoryandExperiments，ed.Gh. Pennaun，SpringerVerlag（1998）.[6] Rosenfeld，A.和R.图片语言-调查，语言设计。1（1993年）。[7] 罗森伯格湾和A.Salomaa，L系统的数学理论，学术出版社，纽约（1980）。[8] 西罗莫尼河和G.Siromoney，Extended Controlled TableLArrays，Information and Control35（1977），119 - 138.