基于分布式加权有限自动机的灰度图像函数推理算法

161→理论计算机科学电子笔记46（2001）网址：http://www.elsevier.nl/locate/entcs/volume46.html16页基于分布式加权有限自动机的Y. Sivasubramanyam1、2和Kamala Krithivasan3印度理工学院计算机科学与工程系，马德拉斯印度钦奈摘要加权有限自动机（WFA）定义实函数，特别是灰色调图像的灰度函数。在[7]中给出了将任意函数（灰度图像）转换为可以再生它的WFA的推理算法。 在本页中-我们定义了n-分量合作分布式加权有限自动机（n-WFA）的理论结构，并研究了这种结构在各种接受模式下的能力。给出了n-WFA的推理算法和反推理算法。1介绍加权有限自动机（WFA）在[7]中被引入。他们计算n-变量的实函数[6]，更精确地说，函数[0， 1]nR。对于n= 2，这样的函数可以被解释为图像的灰度函数。WFA的理论研究见[6]。在[7]中，给出了WFA的推理算法，对于以表格（像素）形式给出的函数（图像），找到了具有少量状态的WFA，该状态近似于给定函数。在[8]中给出了一种递归算法，该算法推断出相对较小的WFA，该WFA提供了对任何给定的真实生活图像的良好近似。[9，10]给出了WFA及其在图像压缩中的应用的全面处理分布式计算在这个计算时代扮演着重要的角色。 语法系统理论是分布式计算的语法模型。语法系统是一组根据特定协议协调工作的语法，以生成一种语言。语法系统可以是1.印度科学技术部的财政支持是有利的2 电子邮件地址：siva@cs.iitm.ernet.in3电子邮件：kamala@iitm.ernet.in2001年由ElsevierScienceB出版。 诉 在CCBY-NC-ND许可下开放访问。SIVASUBRAMANYAM和 KRITHIVASAN162××||×在[2]中可以找到对语法系统的全面处理和对这一领域最近发展的综述。顺序文法系统的概念在[1，12]中被推广到自动机在本文中，我们定义了一个新的理论结构，即，合作分布式加权有限自动机与n-组件（n-WFA），这是一个集合的加权有限自动机顺序工作，以接受输入字符串。这里所遵循的协议是合作分布的协议。我们研究的权力，这一结构在各种模式的接受。给出了n-WFA的推理算法和反推理算法，并举例说明了如何用n-WFA表示图像。当使用n-WFA表示图像时，权重矩阵将是稀疏的，因此所需的存储量将很小。这可以提供更好的压缩比。而且，在大多数情况下，推理和反推理算法将更快，因为推理和反推理算法中涉及的矩阵计算比经典情况快得多。在第二节中，我们给出了加权有限自动机的初步定义及其在数字图象中的应用。在第3节中，我们介绍了合作分布式加权有限自动机的构造，并研究了这种构造在各种接受模式下的接受能力在这一节中，我们还讨论了灰度图象的n-WFA表示，并给出了n-WFA的推理算法和反推理算法第四部分是本文的结论2加权有限自动机与灰度图像在本节中，我们给出了本文所需的基本定义定义2.1加权有限自动机M [10]由下式指定：(i) Q是一组有限的状态。(ii) 一组有限的字母表。(iii) Wα：Q×Q −→R，对于所有α∈φ{}，标记为α的边的权重。(iv) I：Q −→（−∞，∞），初始分布。(v) F：Q −→（−∞，∞），最终分布。这里Wα是一个n矩阵，其中n=Q。I被认为是一个1n行向量，F被认为是一个n1列向量。当将WFA表示为图形时，我们遵循类似于FSA的格式。每个状态由图中的一个节点表示。每个状态的初始分布和最终分布被写为状态内部的元组。 画出了一个标记为α的跃迁作为从状态p到q的有向弧，如果Wα（p，q）/= 0。边的权重写在有向弧上的括号记法Iq（Fq）用于表示SIVASUBRAMANYAM和 KRITHIVASAN163−→−→状态q的初始（最终）分布。Wα（p，q）是指从p到q的转移的权重。Wα（p）是指权重矩阵Wα的第p行向量。它以向量形式给出了从状态p开始的所有转换的权重，标记为αWx也指乘积Wα1·Wα2···Wαk，其中x=α1α2···αk。定义2.2如果WFA的基础FSA是确定性的，则称其为确定性的定义2.3WFA M定义一个函数f：f−→R，其中对于所有且x=α1α2···αk，f（x）=I·Wα1·Wα2···Wαk·F其中运算定义2.4长度为k的路径P被定义为一个元组（q0q1···qk，α1α2···αk）其中q i∈ Q，0 ≤ i ≤ k和α i∈ N，1 ≤ i ≤ k，使得α i表示从q i −1移动到q i时遍历的边的标号。定义2.5路径P的权重W（P）=Iq0·Wα1（q0，q1）·Wα2（q1，q2）···Wαk（qk−1，qk）·Fqk由WFA M表示的函数f：R可以等效地定义如下f（x）=ΣP是M的一条路，标为xW（P），x ∈ N.定义2.6一个函数f：f∈R被称为平均保持的如果1f（w）=M对于所有的w ∈ m，其中m = |Σ|.Σα∈Σf（wα）定义2.7如果WFA M表示的函数是平均保持的，则称它是平均保持的检验WFA是否是平均保持的一般条件在[10]中给出。WFAM是平均保持的，当且仅当Σ其中m = |Σ|.α∈ΣWα·F=mF，定义2.8如果每个状态的初始分布是0或1，则称WFA是i-正态的[13]。I qi = 0或I qi = 1，对所有的q i∈ Q。定义2.9如果每个状态的最终分布是0或1，则称WFA是f-正态的[13]，即对 所 有 的 q i ∈ Q ， F qi = 0或F qi = 1.SIVASUBRAMANYAM和 KRITHIVASAN164−≤≤--···定义2.10如果只有一个态具有非零的初始分布，则称WFA是I-正态的定义2.11如果只有一个态具有非零最终分布，则称WFA是F-正态的2.1使用WFA有限分辨率的灰度数字图像由2m × 2m像素（通常为7m × 11）组成，每个像素取一个实值（实际上数字化为0到2m × 11之间的值，通常为m= 8）。多分辨率图像是指兼容的2n ×2n分辨率图像的集合，其中n=0， 1，.我们将在2n × 2n分辨率下为每个像素分配一个长度为n的字母表n = 0， 1， 2， 3的单词长度小于k的字x将处理分辨率为2kJ 2KJ 其中kJ{<$}，标记为α，其中每个我 ：Q并×Q并−→R，1≤i≤n(iv) I：Qunion−→（−∞，∞）是初始分布。(v) F：Qunion−→（−∞，∞）是最终分布。其中Qunion= iQi。n-WFA的分量WFA中的每一个具有形式Mi=（Qi，Qn，Wi），1≤i≤n。 注意，这里QiJs不需要不相交。每个Wi是m m矩阵，其中m=Q并，并且这些矩阵是稀疏矩阵。I被认为是1m行向量，F被认为是m行向量。1列向量。 当将n-WFA表示为图形时，我们采用与世界粮食计划署类似的格式。从一个组件到另一个组件的过渡由虚线指示定义3.2一个n-WFA被称为是确定性的，如果它的每个组件WFA是确定性的。定义3.3一个n-WFA M定义一个函数f：f−→R，其中对于所有且x=α1α2···αk，f（x）=I·Wi1·Wi2···Wik·F其中运算“·”是矩阵乘法，并且1≤i1，i2，ik≤n。n-WFA的路径、路径的权重和平均保持函数的定义与WFA的定义类似我们考虑不同的接受模式，这取决于系统在每个n-分量中必须经历的步骤的数量。不同的接受模式有t-模式、*-模式、k-模式、k-模式和=k-模式.上述每种接受模式的描述如下：t-模式接受：具有非零状态的自动机WSIVASUBRAMANYAM和 KRITHIVASAN166α一≤ ≥..0F初始分发开始处理输入字符串。假设系统从组件i开始。在组件i中，系统遵循其转移函数由其权重矩阵W i给出作为任何WFA。控制权只从组件i转移到组件j如果系统到达一个状态qi ∈Qi和q∈Qj。如果q属于多于一个的Qj，则j的选择是不确定的。重复这个过程，如果系统在读取整个字符串后达到任何一个具有非零最终状态分布的状态，我们接受字符串。系统在哪个组件中并不重要。定义3.4t-模式中的n-WFA（ID）的瞬时描述由3元组（q，w，i）给出，其中q∈Q并，w∈N，1 ≤i≤ n。在n-WFA的这个ID中，q表示整个系统的当前状态，w表示输入字符串中尚未被读取的部分，i表示系统当前所处的组件的索引。ID之间的转换定义(i) （q，aw，i）<$（qJ，w，i）i <$Wi（q，qJ） /= 其中q∈Qi，qJ∈Q并，a ∈Σ∪{ϵ},w∈ Σ∗, 1≤i≤n(ii) （q，w，i）<$（q，w，j）i <$q∈Qj−Qi设是的自反和传递闭包（当我们考虑灰度图像={ 0， 1， 2， 3}时，w是像素的地址）。定义3.5被n-WFA接受的语言Γ =（Q，Wα，I，F）工作在T模式下的定义如下，- 是的- 是的（q，w，i），n，j），对于某个q，Lt（r）=w∈N。i≤n且q∈Q0i. 最终分配，1- 是的好吧. 也fΓ（w）=字符串w的权重，并且fΓ（w）> 0*-mode acceptance：具有非零初始分布状态的自动机开始处理输入字符串。假设系统从组件i开始处理。与终止模式（t模式）不同，这里没有限制.如果可能的话，自动机可以在任何时候将控制转移到任何其他组件，即，如果存在某个j使得q ∈ Qj，则系统可以将控制转移到组件J.如果有一个以上的j，则选择是不确定的。瞬时描述和系统在 * 模式下接受的语言可以类似地定义。在 *-模式中接受的语言表示为L（Γ）。=k-模式（k模式，k-模式）接受：具有以下特性的组件具有非零初始分布的状态开始处理输入串。假设系统从组件i开始处理。 系统仅在组件i中恰好完成k（kJ（kJ≤ k），kJ（kJ≥ k））步之后才将控制转移到另一个组件j，即，如果FSIVASUBRAMANYAM和 KRITHIVASAN167≤≥∈∈ ∈ ≤≤一一α一αα存在状态q Q j，则只有当系统已经完成了分量i中的k（kJ（kJk），kJ（kJk））个步骤时，才发生从分量i到分量j的转换。如果j有多个选择，则选择为非确定性地进行在上述三种推导模式中，n-WFA的瞬时描述和由它们生成的语言定义如下，定义3.6 n-WFA（ID）的瞬时描述由一个4元组（q，w，i，j）给出，其中q Q union，wn，1 i n，j是非负整数。在n-WFA的这个ID中，q表示整个系统的当前状态，w表示输入字符串中尚未被读取的部分;i表示系统当前所处的组件的索引，j表示系统已经处于第i个组件中的步骤数。只有当n-WFA在读取字符串之后在某个分量i中达到具有非零最终分布的状态时，我们才接受字符串，并且在=k-接受模式的情况下，假设它已经在分量i中完成了k步（它已经完成了某些步骤）。kJ（kJ≤k）阶在分量i≤k的情况下-接受模式或者在以下情况下，它已经在分量i中完成了一些kJ（kJ≥k）步≥k-验收模式）。n-WFA Γ在分别记为L=k（r），L≤k（r）和L≥k（r）.3.2不同模式被WFA接受的语言家族用L（WFA）表示定理3.7对于任何工作在t模式的n-WFA Γ，由它定义的函数可以由单个WFA定义。证明让Γ=（Q，ω，Wα，I，F）是工作在t模式的n-WFAW α=（W1，W2，···，Wn），并且分量具有状态Q1，Q2，···，Qn.考虑WFAM=（QJ，I j，WαJ，IJ， FJ），其中，QJ={[q，i]|q∈Qunio n，1≤i≤n} <${q0J}IJ：QJ−→（−∞，∞）是一个I-正态初始分布，使得IJ（q0J）=1和I J（q）=0，对于所有其他q∈QJFJ：QJ−→（−∞，∞）是such，使得FJ（q0J）=0且FJ（[q，i]）= F（q），q∈Q并，1 ≤i≤ n.WαJ 权矩阵定义如下：(i) W∈J（q0J，[q0，IJ]）=I（q0）such，其中q0∈Qij(ii) 对于每个qk，使得Wi（qj，qk）/= 0，a∈{n}，1≤i≤n，(a) 如果qk∈Qi，则Waj（[qj，i]，[qk，i]）=Wi（qj，qk）(b) 若qk∈Qj−Qi则WaJ（[qj，i]，[qk，j]=Wi（qj，qk）SIVASUBRAMANYAM和 KRITHIVASAN168···∈······0L∈···一一∈L0的1一个2一个kKαααWFA的构建清楚地表明，L（M）=Lt（Γ）所以Lt（Γ）∈ L（WFA）.此外，对于任意的字符串w = a1a2ak，设P =（q0q1qk，a1a2ak）是n-WFA Γ中长为k的路.该路径P的权重为W（p）=I q·Wi1（q0，q1）·Wi2（q1，q2）···Wi k（q k−1，q k）F q，1 ≤ i1，i2，···ik≤n. 路径由WFAM中的这个字符串w跟随，给出PJ=（q0Jq0·· ·qk，a1a2·· ·ak）并且该路径PJ的w∈ht为WJ（pJ）= IqJ·I[q0，i]·WaJ1（[q0，i]，[q1，i]）·WaJ2（[q1，i]，[q2，j]）WaJk（[qk−1，iJ][qk，jJ]）F[qk，jJ]. 通过这种构造，很明显W（P）=WJ（PJ），因此由n-WFA定义的函数fΓ等于由WFA M定义的函数f M。即fΓ（w）= f M（w），其中w∈ M（w）.定理3.8对于任意工作在 *-模的n-WFA Γ，我们有L（Γ）（WFA）。 此外，由工作在模式中的n-WFA Γ定义的函数可以以一个单一的WFA来定义。证明让Γ = （Q，ω，Wα，I，F）是工作在 * 模式的n-WFA，其中W α=（W1，W2，···，Wn），并且分量具有状态Q1，Q2，···，Qn.考虑WFAM=（QJ，I j，WαJ，IJ， FJ），其中，QJ={[q，i]|q∈Qunio n，1≤i≤n} <${q0J}IJ：QJ−→（−∞，∞）是I-正态初始分布，使得IJ（Q0J）=1和IJ（q）=0，对于所有其他q∈QJFJ：QJ−→（−∞，∞）满足FJ（q0J）=0且FJ（[q，i]）= F（q），q∈Q并，1 ≤i≤ n.WαJ 权矩阵定义如下：(i) W<$J（q0J，[q0，i]）=I（q0）such，其中q0∈Qi，1≤i≤n，(ii) 对于eachqy，有条件地证明了Wi（qs，qy）=/ 0，a∈εi{n}，1≤i≤n，WAJ（[qs，i]，[qy，j]）=Wi（qs，qy），1 ≤j≤n且qy∈QjWFA的构建清楚地表明，L（M）=L（Γ）所以L<$（Γ）∈ L（WF A）。同样，对于任何字符串w∈WFA，我们有fΓ（w）=fM（w），其中fΓ是由n-WFA，Γ定义的函数，fM是由WFA，M定义的函数✷定理3.9对于任意n-WFAΓ，n≥ 1，工作在 =k-模，我们有L=k（r） （WFA）。由在=k模式下工作的n-WFA Γ定义SIVASUBRAMANYAM和 KRITHIVASAN169单一WFA。SIVASUBRAMANYAM和 KRITHIVASAN170一一≤≤ ∈L一一αααααα证明设Γ =（Q，ω，Wα，I，F）是一个工作在=k-模式的n-WFA，其中W α=（W1，W2，···，Wn），并且分量具有状态Q1，Q2，···，Qn.考虑WFAM=（QJ，I j，WαJ，IJ， FJ），其中，QJ={[q，i，j]|q∈Qunio n，1≤i≤n，0≤j≤k} <${q0J}IJ：QJ−→（−∞，∞）是I-正态初始分布，使得IJ（Q0J）=1和IJ（q）=0，对于所有其他q∈QJFJ：QJ−→（−∞，∞）满足FJ（q0J）=0且FJ（[q，i，j]）=F（q），对所有q∈Q并，1≤i≤n， 0≤j≤kWαJ 权重矩阵定义如下，(i) W∈J（q0J，[q0，IJ，0]）=I（q0）such，其中q0∈QIJ(ii) 对于每个qy，使得Wi（qs，qy）/= 0，qs∈Qi，a∈Qi{n}，1≤i≤n，0≤j≤k(a) 如果jk那么WaJ（[qs，i，j−1]，[qy，i，j]）=Wi（qs，qy）(b) 如果j=k，则W∈J（[qs，i，k]，[qs，jJ，0]）= 1， 1≤jJ≤n，qs∈QjJ.WFA的构建清楚地表明，L（M）=L=k（r）所以L=k（Γ）∈L（W FA）.同样，对于任意字符串w∈WFA，我们有fΓ（w）=fM（w），其中fΓ是由n-WFA，Γ定义的函数，fM是由WFA，M定义的函数定理3.10对任意k-模的n-WFA Γ，有L≤k（Γ）（WFA）。 由n-WFA Γ定义的函数在k模式可以由单个WFA定义。证明设Γ =（Q，ω，Wα，I，F）是工作于≤k-模的n-WFA，其中W α=（W1，W2，···，Wn），分量态为Q1，Q2，···，Qn.考虑WFAM=（QJ，I j，WαJ，IJ， FJ），其中，QJ={[q，i，j]|q∈Qunio n，1≤i≤n，0≤j≤k} <${q0J}IJ：QJ−→（−∞，∞）是I-正态初始分布，使得IJ（Q0J）=1和IJ（q）=0，对于所有其他q∈QJFJ：QJ−→（−∞，∞）使得FJ（q0J）=0且FJ（[q，i，KJ]）=F（q），对所有q∈Q并，1≤i≤n， 1≤KJ≤kWαJ 权重矩阵定义如下，(i) W∈J（q0J，[q0，IJ，0]）=I（q0）such，其中q0∈QIJ(ii) 对于每个qy，使得Wi（qs，qy）/= 0，qs∈Qi，a∈Qi{n}，1≤i≤n，0≤j≤k +1(a) 如果 j-1

下载后可阅读完整内容，剩余1页未读，立即下载