Method in creating a symbol pattern, symbol pattern obtained thereby, method and system for finding a position in such symbol pattern and computer program product for performing the method
Method in creating a symbol pattern, symbol pattern obtained thereby, method and system for finding a position in such symbol pattern and computer program product for performing the method
 CN 1,981,259 B
 Filed: 07/05/2005
 Issued: 07/04/2012
 Est. Priority Date: 07/08/2004
 Status: Active Grant
First Claim
1. one kind is used for being printed on the paper or being displayed on the twodimensional symensional symbol pattern P on the computer screen when checkout equipment (400) ^{w}A part on find the position of this checkout equipment (400) when moving (wherein, this checkout equipment (400) comprise and is used for obtaining in said position (X, the symbol pattern P that Y) locates for X, method Y) ^{w}The image capture device (403) of image, this symbol pattern P ^{w}Have following attribute, that is, having definition shape and size is that any mask B of m value of symbol is unique at least, and this symbol pattern is based on value of symbol S _{k}Non repetitive sequence S form each value of symbol S _{k}Corresponding to x ^{k}The fixed linear combination of the coefficient C of the monomial in (mod P (x)), wherein, P (x) is territory F _{q}In any polynomial of degree n, and through forming this symbol pattern P according to the folding said sequence S of backrush scheme W ^{w}Wherein, realize said method by signal processing apparatus (411) in the checkout equipment (400) or the external unit of communicating by letter with checkout equipment (400), said method comprises:
 Retrieval is about the information of the relation between the coefficient C of value of symbol among the mask B and correspondence;
(X, the value of symbol of the said mask B of extraction in the said image of Y) locating to obtain from said position;
Through said relation from B _{X, Y}Calculate corresponding coefficient C _{X, Y}, wherein, B _{X, Y}For B in said position (X, the value of symbol of the extraction of Y) locating;
Coefficient C equals C among the sequence of calculation S _{X, Y}Position k;
With Positionbased k and backrush scheme W calculate said checkout equipment (400) at symbol pattern P ^{w}On said position (X, Y).
Chinese PRB Reexamination
Abstract
The invention relates to a method in creating a twodimensional symbol pattern which may be utilized to determine a position in a large area covered by the pattern, for example for recording handwritten information by means of a penlike instrument. The invention is useful for creating a symbol pattern having desired properties, namely that any sufficiently large observed part of the pattern is unique, enabling an unambiguous determination of position. The symbol pattern is based on a nonrepeating sequence of symbol values Sk that each corresponds to a fixed linear combination of the coefficients of the monomials in xk mod P(x), where P(x) is any polynomial of degree n in the field Fq. The symbol pattern is generated by folding the sequence according to a wrapping scheme. The invention also relates to methods and systems for finding the position of a group of observed symbol values in this symbol pattern and computer program products performing the methods.
27 Claims

1. one kind is used for being printed on the paper or being displayed on the twodimensional symensional symbol pattern P on the computer screen when checkout equipment (400) ^{w}A part on find the position of this checkout equipment (400) when moving (wherein, this checkout equipment (400) comprise and is used for obtaining in said position (X, the symbol pattern P that Y) locates for X, method Y) ^{w}The image capture device (403) of image, this symbol pattern P ^{w}Have following attribute, that is, having definition shape and size is that any mask B of m value of symbol is unique at least, and this symbol pattern is based on value of symbol S _{k}Non repetitive sequence S form each value of symbol S _{k}Corresponding to x ^{k}The fixed linear combination of the coefficient C of the monomial in (mod P (x)), wherein, P (x) is territory F _{q}In any polynomial of degree n, and through forming this symbol pattern P according to the folding said sequence S of backrush scheme W ^{w}Wherein, realize said method by signal processing apparatus (411) in the checkout equipment (400) or the external unit of communicating by letter with checkout equipment (400), said method comprises:

Retrieval is about the information of the relation between the coefficient C of value of symbol among the mask B and correspondence; (X, the value of symbol of the said mask B of extraction in the said image of Y) locating to obtain from said position; Through said relation from B _{X, Y}Calculate corresponding coefficient C _{X, Y}, wherein, B _{X, Y}For B in said position (X, the value of symbol of the extraction of Y) locating;
Coefficient C equals C among the sequence of calculation S _{X, Y}Position k;
WithPositionbased k and backrush scheme W calculate said checkout equipment (400) at symbol pattern P ^{w}On said position (X, Y).


2. the method that finds the position according to claim 1, wherein, said relation is for satisfying matrix equation B=TC and having at F _{q}On the transformation matrix T of order N=n.

3. the method that finds the position according to claim 1, wherein, said relation is for satisfying matrix equation B=T '"'"' C and having at F _{q}On the transformation matrix T '"'"' of order N=nj, wherein j is integer and 0≤
 j≤
n;
Wherein, said calculation procedure also comprises; Use B _{X, Y}=T '"'"' C _{X, Y}Calculating is about the coefficient C of correspondence _{X, Y}A plurality of separating;
Coefficient C equals C among the sequence of calculation S _{X, Y}A plurality of position candidate k;
Positionbased k and backrush scheme W compute sign pattern p ^{w}In a plurality of position candidate (X, Y);
WithRemove the false position candidate of the position of seeking.
 j≤

4. the method that finds the position according to claim 3 wherein, is removed said false position candidate through the inspection condition of continuity.

5. the method that finds the position according to claim 2 also comprises:
 for error correction, form test matrix H through the HT=0 that solves an equation;
Form HB _{X, Y}=h _{i}If h _{i}=0, then keep B _{X, Y}If, but h _{i}≠
0, then change at B _{X, Y}The value of symbol at i place, position.
 for error correction, form test matrix H through the HT=0 that solves an equation;

6. according to claim 3 or the 4 described methods that find the position, also comprise:
 , form test matrix H '"'"' through the H '"'"' T '"'"' that solves an equation=0 for error correction;
Form H '"'"' B _{X, Y}=h _{i}If h _{i}=0, then keep B _{X, Y}If, but h _{i}≠
0, then change at B _{X, Y}The value of symbol at i place, position.
 , form test matrix H '"'"' through the H '"'"' T '"'"' that solves an equation=0 for error correction;

7. the method that finds the position according to claim 2 also comprises:
 for each shape in the shape collection of mask B, calculated candidate transformation matrix T has at F up to the candidate transformation matrix T of such calculating _{q}On order N=n;
With the candidate transformation matrix T of selecting to calculate like this, to be used to B _{X, Y}=TC _{X, Y}Calculate corresponding coefficient C _{X, Y}
 for each shape in the shape collection of mask B, calculated candidate transformation matrix T has at F up to the candidate transformation matrix T of such calculating _{q}On order N=n;

8. according to claim 3 or the 4 described methods that find the position, also comprise:
 for each shape in the shape collection of mask B, calculated candidate transformation matrix T '"'"' is up to the candidate transformation matrix T of such calculating '"'"' have at F _{q}On order N=nj;
With the candidate transformation matrix T of selecting to calculate like this '"'"', to be used to B _{X, Y}=T '"'"' C _{X, Y}Calculate corresponding coefficient C _{X, Y}
 for each shape in the shape collection of mask B, calculated candidate transformation matrix T '"'"' is up to the candidate transformation matrix T of such calculating '"'"' have at F _{q}On order N=nj;

9. the method that finds the position according to claim 7 wherein, in said shape collection, increases continuously the quantity m of the value of symbol among the mask B.

10. the method that finds the position according to claim 8 wherein, in said shape collection, increases continuously the quantity m of the value of symbol among the mask B.

11. according to any one the described method that finds the position among the claim 14, wherein, said backrush scheme W comprises with backrush length w by row folding sequence S, and wherein, (X Y) is calculated as (k div w, k mod w) in the position.

12.
12., wherein, come with the algorithm of discrete logarithm that finds k that coefficient C equals C among the sequence of calculation S according to any one the described method that finds the position among the claim 14 _{X, Y}Position k, wherein, for said k, r _{k}≡  x ^{k}(mod P (x)) has coefficient C _{X, Y}

13.
13., wherein, some diverse locations of mask B are repeated this method according to any one the described method that finds the position among the claim 14.

14. the method that finds the position according to claim 13, wherein, it is fixing that the shape of mask B and said relation keep.

15. work as checkout equipment (400) and be printed on the paper or be displayed on the twodimensional symensional symbol pattern P on the computer screen for one kind ^{w}A part on find the position of this checkout equipment (400) when moving (wherein, this checkout equipment (400) comprise and is used for obtaining in said position (X, the symbol pattern P that Y) locates for X, system Y) ^{w}The image capture device (403) of image, this twodimensional symensional symbol pattern P ^{w}Have following attribute, that is, having definition shape and size is that any mask B of m value of symbol is unique at least, and this symbol pattern is based on value of symbol S _{k}Non repetitive sequence S form each value of symbol S _{k}Corresponding to x ^{k}The fixed linear combination of the coefficient C of the monomial in (mod P (x)), wherein, P (x) is territory F _{q}In any polynomial of degree n, and through forming this symbol pattern P according to the folding said sequence S of backrush scheme W ^{w}Said system comprises:

Be used for storing memory storage about the information of the relation between the value of symbol of B and the corresponding coefficient C;
WithBe suitable for the calculation element of following operation; (X, the value of symbol of the said mask B of extraction in the said image of Y) locating to obtain from said position; Through said relation from B _{X, Y}Calculate corresponding coefficient C _{X, Y}, wherein, B _{X, Y}For B in said position (X, the value of symbol of the extraction of Y) locating;
Coefficient C equals C among the sequence of calculation S _{X, Y}Position k;
WithPositionbased k and backrush scheme W calculate said checkout equipment (400) at symbol pattern P ^{w}On said position (X, Y).


16. the system that finds the position according to claim 15, wherein, said relation is for satisfying matrix equation B=TC and having at F _{q}On the transformation matrix T of order N=n.

17. the system that finds the position according to claim 15, wherein, said relation is for satisfying matrix equation B=T '"'"' C and having at F _{q}On the transformation matrix T '"'"' of order N=nj, wherein j is integer and 0≤
 j≤
n;
Wherein, said calculation element also is suitable for following operation; Use B _{X, Y}=T '"'"' C _{X, Y}Calculating is used for corresponding coefficient C _{X, Y}A plurality of separating;
Coefficient C equals C among the sequence of calculation S _{X, Y}A plurality of position k;
Positionbased k and backrush scheme W compute sign pattern P ^{w}In a plurality of position candidate (X, Y);
WithRemove the false position candidate of the position of seeking.
 j≤

18. the system that finds the position according to claim 17, wherein, said calculation element is suitable for removing said false position candidate through the inspection condition of continuity.

19. the system that finds the position according to claim 16 also comprises the error correction device that is suitable for following operation,, forms test matrix H through the HT=0 that solves an equation that is;
 Form HB _{X, Y}=h _{i}If h _{i}=0, then keep B _{X, Y}If, but h _{i}≠
0, then change at B _{X, Y}The value of symbol at i place, position.
 Form HB _{X, Y}=h _{i}If h _{i}=0, then keep B _{X, Y}If, but h _{i}≠

20. according to claim 17 or the 18 described systems that find the position, also comprise the error correction device that is suitable for following operation, that is, form test matrix H '"'"' through the H '"'"' T '"'"' that solves an equation=0;
 Form H '"'"' B _{X, Y}=h _{i}If h _{i}=0, then keep B _{X, Y}If, but h _{i}≠
0, then change at B _{X, Y}The value of symbol at i place, position.
 Form H '"'"' B _{X, Y}=h _{i}If h _{i}=0, then keep B _{X, Y}If, but h _{i}≠

21. the system that finds the position according to claim 16, wherein, said calculation element is suitable for following operation:
 for each shape in the shape collection of mask B, calculated candidate transformation matrix T has at F up to the candidate transformation matrix T of such calculating _{q}On order N=n;
With the candidate transformation matrix T of selecting to calculate like this, to be used to B _{X, Y}=TC _{X, Y}Calculate corresponding coefficient C _{X, Y}
 for each shape in the shape collection of mask B, calculated candidate transformation matrix T has at F up to the candidate transformation matrix T of such calculating _{q}On order N=n;

22. according to claim 17 or the 18 described systems that find the position, wherein, said calculation element is suitable for following operation:
 for each shape in the shape collection of mask B, calculated candidate transformation matrix T '"'"' is up to the candidate transformation matrix T of such calculating '"'"' have at F _{q}On order N=nj;
With the candidate transformation matrix T of selecting to calculate like this '"'"', to be used to B _{X, Y}=T '"'"' C _{X, Y}Calculate corresponding coefficient C _{X, Y}
 for each shape in the shape collection of mask B, calculated candidate transformation matrix T '"'"' is up to the candidate transformation matrix T of such calculating '"'"' have at F _{q}On order N=nj;

23. the system that finds the position according to claim 21, wherein, said calculation element is suitable for:
 in said shape collection, increase continuously the quantity m of the value of symbol among the mask B.

24. the system that finds the position according to claim 22, wherein, said calculation element is suitable for:
 in said shape collection, increase continuously the quantity m of the value of symbol among the mask B.

25. according to any one the described system that finds the position among the claim 1518, wherein, to the said system of some diverse location repetitive operations of mask B.

26. the system that finds the position according to claim 25, wherein, said calculation element is suitable for keeping shape and the said relation of mask B.

27. according to any one the described system that finds the position among the claim 1518, wherein, said calculation element is suitable for:
 come with the algorithm of discrete logarithm that finds k that coefficient C equals C among the sequence of calculation S _{X, Y}Position k, wherein, for said k, r _{k}≡
x ^{k}(mod P (x)) has coefficient C _{X, Y}
 come with the algorithm of discrete logarithm that finds k that coefficient C equals C among the sequence of calculation S _{X, Y}Position k, wherein, for said k, r _{k}≡
Specification(s)