公开/公告号CN1981259A
专利类型发明专利
公开/公告日2007-06-13
原文格式PDF
申请/专利权人 阿诺托股份公司;
申请/专利号CN200580022907.7
发明设计人 彼得·埃里克森;安德莱斯·比约克伦德;
申请日2005-07-05
分类号G06F3/033(20060101);G06K9/22(20060101);
代理机构中国国际贸易促进委员会专利商标事务所;
代理人康建忠
地址 瑞典隆德
入库时间 2023-12-17 18:46:19
法律状态公告日
法律状态信息
法律状态
2015-08-26
未缴年费专利权终止 IPC(主分类):G06F3/033 授权公告日:20120704 终止日期:20140705 申请日:20050705
专利权的终止
2012-07-04
授权
授权
2007-08-08
实质审查的生效
实质审查的生效
2007-06-13
公开
公开
相关申请的交叉引用
本申请要求第0401812-3号瑞典专利申请和第60/585,856号美国临时专利申请的利益，这两个专利申请都是于2004年7月8日提交的，其在此引入作为参考。
技术领域
本发明涉及一种创建二维符号图案的方法，该二维符号图案可用于确定该图案所覆盖的大区域中的位置，例如用于通过类似笔的器具记录手写信息。本发明对于创建具有能够进行位置的无歧义确定的期望属性的符号图案是有用的。
本发明还涉及用于找到该符号图案中的一组观察符号值的位置的方法和系统以及执行这些方法的计算机程序产品。
背景技术
在该领域中，以前就知道能形成可扫描到类似笔的器具中的图案，该类似笔的器具合并了用于计算笔相对于比如打印在纸上或显示在计算机屏幕上的图案的位置的计算机能力和存储器。
还已知通过线性反馈移位寄存器(LFSR)生成重复或非重复序列。非重复序列具有这样的属性，即，每个给定数量的连续值的子序列在该序列中仅出现一次。因此，在非重复序列中，无歧义地确定给定长度的每个子序列的位置。已知将这样的非重复序列卷成或折叠成二维符号图案并找到这样的图案中的位置。参见，例如，公布的专利申请US 2004/0085287、US 2004/0085302、US 2004/0086181和US2004/0086191，这些专利申请都已转让给微软公司。
发明内容
在现有技术中回卷(wrap)序列的问题在于没有方法断定通过回卷非重复序列而获得的这样的二维图案是否具有期望属性，即，该图案的任何足够大的观察部分是唯一的。如果它不是唯一的，则不可能无歧义地确定其位置。
本发明提供用公式表达用于控制符号图案中的观察组(掩模)和有效的非重复序列之间的关系的条件的工具。此外，本发明提供用于检测回卷序列是否具有用于位置确定的充分的属性以及用于恢复符号图案内的位置的有效技术。
在所附权利要求中限定了本发明。
附图说明
以下将参考附图详细地描述本发明，在附图中：
图1是实施为符号图案的回卷序列的示例；
图2是线性反馈移位寄存器的示意图；和
图3是定义符号图案的观察子集的示例性掩模的示意图。
图4是根据本发明实施例的笔形检测设备的部分剖面的示意侧视图。
具体实施方式
为了更好的理解，我们描述支持本发明的数学运算，这些数学运算中的一些也形成了现有技术的一部分。将使用以下术语和定义。
术语和定义
S 元素Sk的序列
L S的长度(k＝0至L-1)
PW 由序列S和回卷方案W形成的符号图案
P(x) n次多项式
n 多项式P(x)的次数和LFSR的大小
N T的秩
rk n次剩余多项式，其定义为在Fq[x]/P(x)中计算的rk≡xk(mod P(x))
Fq q阶有限域，其中典型地，但不是必须地，q＝2
G(f(x))辅助函数，比如，rk中的单项式xn-1的系数
W 回卷方案
w 回卷长度(当行向或列向回卷时)
B 掩模＝通过几何扫描图案(＝球)观察的元素的列矢量
B′ 同上，通过另一扫描图案观察的元素的列矢量
Bp 符号图案的子划分
m B的大小(＝“k×1”，如果为矩形扫描图案的话)；(m≥n)
C 剩余多项式rk的与序列S中的位置k对应的(大小为n的)系数的列矢量
T 变换矩阵T，满足B＝TC，T具有秩N＝n
T′ 变换矩阵T′，满足B＝T′C，T具有秩N＝n-j
X，Y 所寻找位置(比如，左顶角，或者，如果B为不规则形状，则为B的“第一”元素)
Bx，Y B(和B′)在所寻找位置(X，Y)处的元素
Cx，Y C中与所寻找位置(X，Y)对应的系数
k 在序列S中C中的系数等于Cx，Y的位置
H 满足HT＝0的检验矩阵，具有唯一非零列
hi H的列i，在B的位i处出现的出错位组
LFSR线性反馈移位寄存器
第一任务是创建具有期望属性的符号图案PW。这可通过形成和回卷长的非重复序列S然后检查由变换矩阵T表示的足够大的观察掩模和该序列之间的变换关系是否满足规定的条件来执行。图1中显示了符号图案的示例，在图1中，白和黑像素分别表示符号值1和0。因此，符号图案由有序的符号集形成，每个符号表示序列S的至少一个符号值或元素。
虽然以下讨论是基于由二进制符号值形成的序列S，但是本发明的基本原理一般可应用于任何基数的符号值(即，域Fq的任何阶数q)。
众所周知的是，线性反馈移位寄存器LFSR可用于生成这样的长的非重复二进制序列，即，任何足够大的子序列在该序列中是唯一的。大小为n的LFSR是包括n个位保持器和至少一个XOR门的简单的计算设备，例如如图2所示，n个位保持器标识为r0，r1，...，rn-1，它们沿闭合的有向电路连接。在离散时间t0，t1...，更新该设备。在时间tk，k＞0，用在指向每个位保持器的箭头端计算的值同时更新每个位保持器。在时间tk的内容Ck＝(c0(k)，c1(k)，...，cn-1(k)称作LFSR在时间tk的状态。在时间t0，状态比如为{1，0，0，...，0}。在每个时间tk，移出包含在rn-1中的位以生成二进制序列S的第k位。由于存在这样许多唯一的状态，所以生成的序列S可具有最多2n-1的周期，并且事实上，对于一些LFSR：s，序列的周期是这样长的。为了本发明的目的而期望的另一属性为在该周期中任何n个连续位的子序列为唯一的。
在图2的示例中，LFSR包括5个位保持器和XOR门。示出的LFSR表示多项式P(x)＝x5+x2+1，并且可根据P(x)和位保持器的初始值生成特定长度的非重复序列。在“Introduction to finite fields and theirapplication”，Chapter 6-Linear Recurring Sequences，by R.Lidl andH.Niederreiter，Revised Edition 1994，Cambridge University Press中会找到关于LFSR：s和生成重复和非重复序列的更多细节。
LFSR为生成序列的实际设备。幸运的是，LFSR还承认关于多项式环中的生成器方面的自然数数学处理，接下来我们将对其进行描述。
设F2为二进制域。设F2[x]为具有来自F2的系数的所有x多项式的域。最后，设F2[x]中的多项式P(x)的R(x，P(x))表示包括F2[x]/P(x)中的元素xk，k＝0，1，2，...的环(即，xk modulo P(x))，其中，每个单项式系数在F2中。在F2[x]中将xo-1除以P(x)的最小正数o称为环的阶数。
环R(x，P(x))用以下方式与LFSR相关。设n为P(x)的次数，并考虑在关于p(x)中的每个单项式xL的cL-1和cL之间具有XOR门的大小为n的LFSR。现在，由于乘以x对应于LFSR的移位，并且用于给出除以P(x)之后的余数的减法对应于XOR门的计算，所以观察到LFSR在时间tk的状态Ck＝(c0(k)，c1(k)，...，cn-1(k)遵守：
