Como se mencionó en el comentario, Livescribe utiliza un patrón de punto de la tecnología de la licencia de una compañía sueca Anoto. El patrón de puntos es más probable es que el cubierto por la patente de la
WO/03/038741.
Edward Aboufadel tiene un papel de la Posición de Codificación
lo que explica las ideas matemáticas detrás Anoto el patrón de puntos.
La construcción en esta respuesta utiliza ideas de Aboufadel del papel.
No es el utilizado por Livescribe ni el que explícitamente se discutió en Aboufadel del papel.
Todos los errores y los malentendidos de la mina.
Deje $P = \{ 0, 1, 2, \ldots, p - 1 \} \subset \mathbb{N}$ el conjunto de los enteros no negativos a menos que algún entero positivo $p$. Dado cualquier secuencia finita
$$A = (a_0, a_1, \ldots, a_{m-1}) \in P^{m}$$
Podemos extender a una secuencia de más de $\mathbb{Z}$ por periodicidad. yo.e
$$P^m \ni \mapsto A' = (\ldots una'_{-2},'_{-1},'_{0},'_1 un'_2,\ldots) \P^{\mathbb{Z}}
\;\;\text{ s.t. }\;\; un'_k = a_{k\!\pmod m}
\;\;\text{ para } k \in \mathbb{Z}
$$
Si existe un $n$ de manera tal que el $m$ finito subsecuencias de longitud $n$
$$
(un'_0, un'_1, \ldots,'_{n-1}),\,
(un'_1, un'_2, \ldots,'_{n}),\,
\ldots,\,
('_{m-1},'_{m}, \ldots,'_{n+m-2})$$
son todos distintos, vamos a llamar a la secuencia de $A'$ $p$- ary pseudo De Bruijn secuencia de orden de $n$ y la longitud de la $m$. En el caso especial $m = 2^n$, $A'$ se llama una secuencia De Bruijn.
La propiedad más importante de este tipo de secuencias es que si conocemos el valor de
$n$ términos consecutivos de una secuencia, vamos a conocer la posición relativa de los términos modulo $m$.
A partir de ahora, nos vamos a abusar de la notación con una caída de la $'$ y el uso de $A = (a_k)$ a representar tanto el original secuencia finita y genera una secuencia infinita.
Los siguientes son algunos ejemplos de binaria pseudo secuencias De Bruijn:
$$\begin{array}{lcl}
n = 4, m = 16 &:& A = (a_k) = 0000110101111001\ldots\\
n = 3, m = 8 &:& B = (b_k) = 00010111\ldots\\
n = 3, m = 7 &:& C = (c_k) = 0001011\ldots\\
n = 3, m = 5 &:& D = (d_k) = 00111\ldots\\
n = 3, m = 3 &:& E = (e_k) = 001\ldots
\end{array}$$
Aviso de las secuencias de $B,C,D,E$ por encima de todo tener un orden $n = 3$ y sus longitudes son relativos prime el uno al otro. Si construimos una secuencia hexadecimal $F = (f_k) \in \{ 0,\ldots, 15\}^{\mathbb{Z}}$ por
$$f_k = 8 b_k + 4 c_k + 2 d_k + e_k\quad\text{ for } k \in \mathbb{Z}$$
la secuencia de $F$ será un pseudo De Bruijn secuencia de orden de $3$ y la longitud
$\text{lcm}(8,7,5,3) = 840$.
Si se nos dan los valores de los tres (3)$f_k, f_{k+1}, f_{k+2}$, podemos
recuperar los valores de $k \pmod{840}$ por el siguiente procedimiento:
- desglose $( f_{k}, f_{k+1}, f_{k+2} )$ en sus bits, recuperar los valores de
$$
( b_k, b_{k+1}, b_{k+2} ),\,
( c_k, c_{k+1}, c_{k+2} ),\,
( d_k, d_{k+1}, d_{k+2} ),\,\text{ y }
( e_k, e_{k+1}, e_{k+2} )$$
- Desde $B$ es pesudo Bruijn con una longitud corta relativa $8$, se puede utilizar una tabla look-up
para descubrir el valor de $k \pmod{8}$.
- Si hacemos la misma cosa $C$, $D$ y $E$, vamos a descubrir el valor de $k \pmod{7}$,
$k \pmod{5}$ $k \pmod{3}$ respectivamente.
- A continuación, podemos utilizar teorema del resto Chino para recuperar el valor de $k \pmod{840}$.
Deje $\varphi : \mathbb{Z} \to \{0, \ldots, 15\}$ y
$X, Y : \mathbb{Z}^2 \to \{ 0, 1 \}$ ser las funciones definidas por
$$\varphi(x) = \sum_{k=0}^{x-1} f_k \pmod{16} \quad\text{ y }\quad
\begin{cases}
X(x,y) &= a_{y + \varphi(x)}\\
Y(x,y) &= a_{x + \varphi(y)}
\end{casos}$$
donde $(a_k) = A$ es el primer ejemplo de De Bruijn secuencias anteriores.
Para cada una de las $(x,y) \in [1,209] \times [1, 296]$, pongamos un punto cerca de $(x,y)$ basado en los valores de $X(x,y)$$Y(x,y)$:
$$\begin{array}{|cc:c|}
\hline
X(x,y) & Y(x,y) & \text{center}\\
\hline
0 & 0 & (x-0.1,y)\\
0 & 1 & (x+0.1,y)\\
1 & 0 & (x,y-0.1)\\
1 & 1 & (x,y+0.1)\\
\hline
\end{array}$$
Desde el rodado de la zona de la cámara, tiene dimensión $10\text{mm} \times 10\text{mm}$,
siempre contiene una $9 \times 9$ plaza de puntos. Para nuestra actual ubicación de puntos, sólo necesitamos el $4 \times 4$ plaza de puntos cerca del centro de la vista.
Digamos que la cámara ha decodificado los desplazamientos para un $4 \times 4$ plaza de puntos
y nos devuelven con dos $4 \times 4$ matriz de números binarios. Uno de $X$ y otro para $Y$. Veamos el $4 \times 4$ matriz de números binarios para $X$:
$$\begin{array}{r|cccc}
X & x & x+1 & x+2 &x+2\\
\hline
y & g_{00} & g_{10} & g_{20} & g_{30}\\
y+1 & g_{01} & g_{11} & g_{21} & g_{31}\\
y+2 & g_{02} & g_{12} & g_{22} & g_{32}\\
y+3 & g_{03} & g_{13} & g_{23} & g_{33}\\
\end{array}$$
A través de cualquier columna, dicen que la columna de la izquierda,
$$( g_{00}, g_{01}, g_{02}, g_{03}) =
(a_{y+\varphi(x)}, a_{y+\varphi(x)+1}, a_{y+\varphi(x)+2}, a_{y+\varphi(x)+3})$$
es una sub-secuencia de longitud $4$ para la secuencia De Bruijn $A$ cuyo fin también es $4$.
Podemos ver el valor de $y + \varphi(x) \pmod{16}$ a partir de una tabla de $16$ entradas.
Si hacemos lo mismo para las otras 3 columnas, vamos a obtener los valores de
$y + \varphi(x) + f_x \pmod{16}$, $y + \varphi(x) + f_x + f_{x+1}\pmod{16}$ y
$y + \varphi(x) + f_x + f_{x+1} + f_{x+2} \pmod{16}$ respectivamente.
Podemos combinar estas cuatro piezas de información para obtener los valores de $f_x$, $f_{x+1}$
y $f_{x+2}$. Por el procedimiento descrito anteriormente, se puede deducir el valor de $x$.
Por un procedimiento similar, se puede deducir el valor de $y$ de la $4 \times 4$ matriz de números binarios para $Y$.
Desde el pseudo secuencia De Bruijn $F = (f_k)$ tiene una longitud de $840$ mayor que la dimensión del papel, todos los "$4 \times 4$ plaza de puntos" son distintos.
