METODO PARA CONSEGUIR UN CODIGO DE POSICION Y DECODIFICAR UN CODIGO DE POSICION.

Un método, que se lleva a cabo en un dispositivo de codificación,

para determinar un código (410) de posición que codifica al menos una primera coordenada x para un primer punto y para una primera dimensión en una superficie, que comprende:

recibir al menos la primera coordenada x como la señal de entrada al dispositivo (600) de codificación,

determinar, basándose en la coordenada x recibida, una secuencia parcial de una secuencia (PD) de números primaria, secuencia parcial que tiene una primera longitud predeterminada y corresponde a la coordenada x recibida, usándose dicha secuencia de números primaria para codificar posiciones en la primera dimensión y teniendo la propiedad de que cada secuencia parcial de una primera longitud predeterminada tiene un lugar determinado inequívocamente en la secuencia de números primaria;

caracterizado porque al menos una secuencia parcial de la secuencia (PD) de números primaria puede mapearse con una combinación de una secuencia parcial de cada una de al menos dos secuencias (A1-A4) de números secundarias, cada una de las cuales tiene una base menor que la base de la secuencia de números primaria y porque el dispositivo de codificación usa dichas al menos dos secuencias (A1-A4) de números secundarias para la determinación de la secuencia parcial de la secuencia de números primaria correspondiente a la coordenada x

Método para conseguir un código de posición y decodificar un código de posición.

Campo de la invención

La presente invención se refiere a códigos de posición.

Técnica de antecedente

El uso de códigos de posición en una superficie como herramienta para grabar de forma electrónica información que está escrita o dibujada en la superficie ya es conocido.

En el documento US 5.477.012 se describe un lápiz que detecta ópticamente un código de posición que consiste en diversos símbolos en una superficie. El lápiz decodifica el código de posición y genera pares de coordenadas que describen el movimiento del lápiz por la superficie. Cada posición se codifica mediante un símbolo específico. Si el código de posición va a codificar muchas posiciones, esto da como resultado la desventaja de que los símbolos se vuelven complejos y por tanto, difíciles de detectarse correctamente. Por otro lado, si los símbolos se hacen más grandes, disminuye la resolución.

En el documento WO 92/17859 se describe un código de posición en el que cada posición se codifica mediante una pluralidad de símbolos y cada símbolo contribuye a la codificación de más de una posición. Por tanto se codifican posiciones adyacentes mediante símbolos parcialmente compartidos.

En el anexo A del documento WO 92/17859 se proporciona el siguiente ejemplo de cómo puede formarse el código de posición y de cómo puede decodificarse una posición.

Pártase de las siguientes secuencias m: s=(0,0,1,0,1,1,1) y t=(0,1,1). Fórmese un patrón de codificación de posición haciendo que una primera columna en el patrón sea la misma que la secuencia s. Con el fin de formar las siguientes columnas, se mira la secuencia t. Si el primer elemento en la secuencia t es 0, entonces la segunda columna consiste en la secuencia s. Si en su lugar el primer elemento es 1, entonces la segunda columna consiste en la secuencia s con un desplazamiento circular de un paso. Se forman columnas subsiguientes de una manera correspondiente según los valores de los elementos en la secuencia t. Por tanto se obtiene el siguiente patrón:

Supóngase ahora que se quiere encontrar la posición de una superficie parcial con el siguiente subconjunto del patrón.

La primera columna en el subconjunto es (1,0,1). Esta subsecuencia aparece en la posición 2 en la secuencia s. Los desplazamientos circulares en el subconjunto son (1,1). Esta subsecuencia aparece en la posición 1 en la secuencia t. Los desplazamientos acumulados en el patrón son (0,0,1,2) y por tanto la posición vertical del subconjunto es 2+0=2. La posición del subconjunto en la superficie parcial es por tanto (1,2).

Este patrón tiene la ventaja de que puede codificarse basándose en usar símbolos sencillos, por ejemplo un primer símbolo para un cero y un segundo símbolo para un uno.

Una propiedad interesante de un patrón de codificación de posición de este tipo es, sin embargo, la capacidad de codificar un gran patrón con muchas posiciones únicas de modo que puede llevarse a cabo una determinación de posición en una superficie lo más grande posible. En el ejemplo anterior, el tamaño en la dirección vertical está limitado por la longitud de la secuencia s y el tamaño en la dirección horizontal por la longitud de la secuencia t. La longitud de estas secuencias no puede aumentarse sin límite ya que las secuencias deben tener la propiedad de que si se toma una subsecuencia de k bits, entonces esta subsecuencia sólo debe producirse en un único lugar en la secuencia. Un aumento en la longitud de la secuencia puede conllevar por tanto un aumento en la longitud de la subsecuencia y de este modo un aumento en la superficie parcial que necesita grabarse con el fin de poder determinar una posición.

En los documentos WO 01/26032, WO 01/26033 y WO 01/26034 se describe otro patrón de codificación de posición que se basa en los mismos principios básicos que los del documento WO 92/17859, pero que permite la codificación de un mayor número de posiciones.

En una realización de este patrón, se usa una primera secuencia de números que tiene la propiedad de que el lugar en la secuencia de números de cada subsecuencia o secuencia parcial de una longitud predeterminada se determina inequívocamente y esta secuencia de números se imprime en columnas sobre la superficie con diversas rotaciones o desplazamientos circulares. Sin embargo, en lugar de usar una segunda secuencia binaria (la secuencia t en el documento WO 92/17859) se permiten mayores desplazamientos circulares entre columnas adyacentes.

La superficie se divide adicionalmente en ventanas de código. Cada ventana de código comprende al menos tres columnas con secuencias de números y solapa las ventanas de código adyacentes por una secuencia de números. Usando los desplazamientos entre columnas adyacentes, se codifica la posición de la ventana de código a lo largo del eje x. Los desplazamientos entre las secuencias de números en una ventana de código definen por tanto una posición, teniendo la primera ventana de código la posición 0, la siguiente 1, y así sucesivamente.

Cuando se lee el código de posición, el dispositivo de lectura grabará sin embargo con frecuencia partes de dos ventanas de código. Para poder determinar la posición de las ventanas de código con respecto a la imagen leída del código de posición, se usan desplazamientos en un primer intervalo para indicar el desplazamiento menos significativo para la posición y desplazamientos en un segundo intervalo para otros desplazamientos en la posición.

La codificación de una coordenada y se lleva a cabo de una manera correspondiente.

Se ha encontrado que este código de posición funciona muy bien y permite la codificación de un número muy grande de posiciones. Existe, sin embargo, un deseo de mejorar las propiedades de corrección de errores del código de posición.

Supóngase, por ejemplo, que el último subconjunto que codifica inequívocamente una posición en la dirección x comprende cinco desplazamientos. A partir de estos cinco desplazamientos puede determinarse una posición de una ventana de código. Las posiciones de dos ventanas de código adyacentes difieren por tanto habitualmente sólo en el último dígito (el último desplazamiento). Para tres ventanas de código consecutivas los desplazamientos pueden ser, por ejemplo, como sigue:

25,15,34,18,3; 25,15,34,18,4; 25,15,34,18,5.

Un método común para detectar errores se basa en leer más información de la necesaria para la tarea en cuestión. Con la codificación mencionada anteriormente, es difícil leer información adicional que es adecuada para su uso para la detección de errores. Supóngase, por ejemplo, que un dispositivo de lectura graba los dos últimos desplazamientos de la primera de las tres ventanas de código anteriores, y los tres primeros desplazamientos de la siguiente ventana de código, esto es 18,3,25,15,34. Supóngase además que se produce un error que significa que se graba 18,4,25,15,34. La lectura de, por ejemplo, dos desplazamientos más, uno a cada lado de los cinco, no proporciona información adicional que posibilite detectar el error.

Si, cuando se codifica en la dirección x, se usa una secuencia de números con la propiedad de que cada secuencia parcial (subsecuencia) de una longitud predeterminada tiene un lugar determinado inequívocamente en la secuencia de números, se facilita una corrección de errores. Por otro lado, surge el problema práctico de que esta secuencia de números debe tener una base grande, esto es, que debe permitir grandes desplazamientos, si debe ser posible codificar muchas posiciones. Entonces se requiere una tabla muy grande para encontrar el lugar en la secuencia de números al que corresponde una secuencia parcial leída, que a su vez requiere una gran cantidad de memoria. Sin embargo, es deseable que la decodificación pueda llevarse a cabo en, por ejemplo, un dispositivo de lectura de mano con una memoria y capacidad de procesador limitadas. También es deseable que la codificación pudiera llevarse a cabo en dispositivos con una memoria y capacidad de procesador limitadas.

El documento US 5.661.506 da a conocer una superficie codificada ópticamente para lápices digitales. Cada píxel de la superficie...

1. Un método, que se lleva a cabo en un dispositivo de codificación, para determinar un código (410) de posición que codifica al menos una primera coordenada x para un primer punto y para una primera dimensión en una superficie, que comprende:

recibir al menos la primera coordenada x como la señal de entrada al dispositivo (600) de codificación,

determinar, basándose en la coordenada x recibida, una secuencia parcial de una secuencia (PD) de números primaria, secuencia parcial que tiene una primera longitud predeterminada y corresponde a la coordenada x recibida, usándose dicha secuencia de números primaria para codificar posiciones en la primera dimensión y teniendo la propiedad de que cada secuencia parcial de una primera longitud predeterminada tiene un lugar determinado inequívocamente en la secuencia de números primaria;

caracterizado porque al menos una secuencia parcial de la secuencia (PD) de números primaria puede mapearse con una combinación de una secuencia parcial de cada una de al menos dos secuencias (A1-A4) de números secundarias, cada una de las cuales tiene una base menor que la base de la secuencia de números primaria y porque el dispositivo de codificación usa dichas al menos dos secuencias (A1-A4) de números secundarias para la determinación de la secuencia parcial de la secuencia de números primaria correspondiente a la coordenada x.

2. Un método de acuerdo con la reivindicación 1, en el que determinar una secuencia parcial de la secuencia (PD) de números primaria comprende convertir el lugar en la secuencia de números primaria en un lugar en cada una de las secuencias (A1-A4) de números secundarias.

3. Un método de acuerdo con la reivindicación 2, en el que determinar una secuencia parcial de la secuencia (PD) de números primaria comprende además determinar para cada una de las secuencias (A1-A4) de números secundarias la secuencia parcial que corresponde al lugar determinado en la secuencia de números secundaria y determinar la secuencia parcial de la secuencia de números primaria basándose en las secuencias parciales así determinadas de las secuencias de números secundarias.

4. Un método de acuerdo con una cualquiera de las reivindicaciones 1-3, que comprende además codificar los números en la secuencia parcial de la secuencia de números primaria usando secuencias (S) parciales de una segunda longitud predeterminada de una secuencia de números principal cíclica, que tiene la propiedad de que el lugar en la secuencia de números principal cíclica de cada secuencia (S) parcial de la segunda longitud predeterminada se determina inequívocamente, codificándose los números en la secuencia parcial de la secuencia de números primaria como diferencias de las secuencias parciales de la secuencia de números principal cíclica.

5. Un método de acuerdo con la reivindicación 4, que comprende además proporcionar un código de posición que comprende una indicación de las secuencias parciales de la secuencia de números principal cíclica como señal de salida desde el dispositivo de codificación.

6. Método según la reivindicación 4 ó 5, que comprende además hacer que un dispositivo aplique las secuencias parciales de la secuencia de números principal en la superficie de modo que éstas se extiendan en una segunda dimensión y de modo que los números en la secuencia parcial de la secuencia de números primaria se extiendan en la primera dimensión.

7. Un método de acuerdo con una cualquiera de las reivindicaciones 4-6, que comprende además calcular una primera secuencia parcial entre las secuencias parciales de la secuencia de números principal cíclica sumando los x-1 primeros números en cada una de las secuencias de números secundarias repetidas cíclicamente.

8. Un método de acuerdo con la reivindicación 7, en el que los números en las secuencias de números secundarias se suman mediante el uso de sumas previamente calculadas de ciclos completos e incompletos de las secuencias de números secundarias.

9. Un método de acuerdo con la reivindicación 7 u 8, que comprende además recibir el lugar en la secuencia de números principal cíclica de la secuencia parcial para la coordenada x=0 como señal de entrada al dispositivo de codificación y usar el lugar de la coordenada x=0 para el cálculo de la primera secuencia parcial entre las secuencias parciales de la secuencia de números principal.

10. Un método de acuerdo con una cualquiera de las reivindicaciones 7-9, que comprende además determinar una segunda secuencia parcial entre las secuencias parciales de la secuencia de números principal determinando el número d(x) en la secuencia parcial de la secuencia de números primaria que se codifica por las secuencias parciales primera y segunda de la secuencia de números principal.

11. Un método de acuerdo con la reivindicación 10, en el que el número d(x) que se codifica por las secuencias parciales primera y segunda de la secuencia de números principal se calcula como d(x)=dc(1,x)+b₁*dc(2,x)+...+b₁*...*b_n-1*dc(n,x) donde n es el número de secuencias de números secundarias, b_i es la base en la secuencia i de números secundaria y dc(i,x) es el número en el lugar x módulo I_i en la secuencia de números secundaria respectiva de longitud I_i.

12. Un método de acuerdo con una cualquiera de las reivindicaciones 1-11, que comprende además:

recibir una segunda coordenada y para el primer punto y para una segunda dimensión en la superficie como señal de entrada al dispositivo de codificación,

determinar, basándose en la coordenada y recibida, una secuencia parcial de una segunda secuencia de números primaria, secuencia parcial que tiene una tercera longitud predeterminada y corresponde a la coordenada y recibida, usándose dicha segunda secuencia de números primaria para codificar posiciones en la segunda dimensión y teniendo la propiedad de que cada secuencia parcial que tiene la tercera longitud predeterminada tiene un lugar determinado inequívocamente en la segunda secuencia de números primaria;

pudiendo mapearse al menos una secuencia parcial de la segunda secuencia de números primaria con una combinación de una secuencia parcial de cada una de al menos dos segundas secuencias de números secundarias, que tienen bases menores que la segunda secuencia de números primaria y que se usan por el dispositivo de codificación para la determinación de la secuencia parcial de la segunda secuencia de números primaria correspondiente a la coordenada y.

13. Un método de acuerdo con una cualquiera de las reivindicaciones anteriores, en el que:

el número de diferentes números en la secuencia (PD) de números primaria que pueden usarse para la codificación de posición es tal que el número puede factorizarse en al menos dos factores,

en el que se usa el mismo número de secuencias (A1-A4) de números secundarias que el número de factores, y

en el que cada uno de los factores forma la base en una secuencia de números secundaria respectiva.

14. Un método de acuerdo con una cualquiera de las reivindicaciones anteriores, en el que las longitudes de las secuencias (A1-A4) de números secundarias son relativamente primas en pares.

15. Un método de acuerdo con una cualquiera de las reivindicaciones anteriores, en el que cada una de las secuencias (A1-A4) de números secundarias tiene la propiedad de que cada secuencia parcial que tiene la primera longitud predeterminada, tiene un lugar determinado inequívocamente en la secuencia de números secundaria respectiva.

16. Un método de acuerdo con una cualquiera de las reivindicaciones anteriores, en el que la base de las secuencias (A1-A4) de números secundarias es como máximo 5, preferiblemente como máximo 3.

17. Un método de acuerdo con una cualquiera de las reivindicaciones anteriores, en el que las secuencias parciales de la secuencia (PD) de números primaria pueden mapearse de manera biyectiva con combinaciones de una secuencia parcial de cada una de las secuencias (A1-A4) de números secundarias.

18. Un método de acuerdo con una cualquiera de las reivindicaciones 1-3, en el que los números en la secuencia (PD) de números primaria se codifican usando secuencias parciales de una segunda longitud predeterminada de una secuencia de números principal cíclica, que tiene la propiedad de que el lugar en la secuencia de números principal cíclica de cada secuencia parcial de la segunda longitud predeterminada se determina inequívocamente, estando dispuestas las secuencias parciales de la secuencia de números principal cíclica en la superficie de modo que se definen números de diferencia que forman los números en la secuencia de números primaria.

19. Un método de acuerdo con la reivindicación 18, en el que las secuencias parciales de la secuencia de números principal cíclica están dispuestas en la superficie de modo que cada secuencia parcial se extiende en una segunda dimensión.

20. Un método de acuerdo con la reivindicación 18 ó 19, en el que sólo se utiliza un subconjunto de los números de diferencia que teóricamente pueden definirse usando las secuencias parciales de la secuencia de números principal, subconjunto que excluye números de diferencia que pueden definirse teóricamente de este tipo que son iguales a o casi cero.

21. Un método de acuerdo con una cualquiera de las reivindicaciones 18-20, en el que la secuencia de números principal es binaria y se selecciona de modo que no se produce ninguna secuencia parcial de una longitud predeterminada que sea más larga que la segunda longitud predeterminada en una forma hacia atrás o invertida en la secuencia de números principal.

22. Un método de acuerdo con una cualquiera de las reivindicaciones 18-21, en el que la secuencia de números principal es binaria y se selecciona de modo que no se produce ninguna secuencia parcial de una longitud predeterminada que sea más larga que la segunda longitud predeterminada con un bit invertido en la secuencia de números principal.

23. Un método de acuerdo con una cualquiera de las reivindicaciones 18-22, en el que la secuencia parcial de la secuencia de números principal, secuencia parcial que es de la segunda longitud predeterminada, consiste en seis números, y la secuencia parcial de la secuencia de números primaria, secuencia parcial que es de la primera longitud predeterminada, consiste en cinco números de diferencia.

24. Un método de acuerdo con una cualquiera de las reivindicaciones 18-23, en el que la secuencia M de números principal cíclica es la siguiente:

25. Un método de acuerdo con una cualquiera de las reivindicaciones anteriores, en el que la secuencia (PD) de números primaria contiene cincuenta y cuatro números diferentes y las secuencias (A1-A4) de números secundarias son cuatro en número, tres de las cuales tienen la base tres y una de las cuales tiene la base dos.

26. Un método de acuerdo con una cualquiera de las reivindicaciones anteriores, en el que las secuencias de números secundarias son las siguientes:

27. Un método de acuerdo con una cualquiera de las reivindicaciones 1-11, que comprende además codificar posiciones en una segunda dimensión en la superficie según una segunda secuencia de números primaria que tiene la propiedad de que el lugar en la segunda secuencia de números primaria de cada secuencia parcial de una tercera longitud predeterminada se determina inequívocamente, codificándose cada posición en la segunda dimensión por una de las secuencias parciales en la segunda secuencia de números primaria y pudiendo mapearse al menos una secuencia parcial de la segunda secuencia de números primaria con una combinación de una secuencia parcial de cada una de al menos dos segundas secuencias de números secundarias que tienen bases menores que la base de la segunda secuencia de números primaria y que se usan para la determinación de las secuencias parciales de la segunda secuencia de números primaria correspondiente a las posiciones en la segunda dimensión.

28. Un método de acuerdo con la reivindicación 27, en el que las secuencias de números primaria y secundaria para la codificación de posición en la primera y la segunda dimensión son las mismas.

29. Un método de acuerdo con una cualquiera de las reivindicaciones anteriores, que comprende además imprimir el código de posición con codificación gráfica en la superficie.

30. Un dispositivo para codificar posiciones, dispositivo que comprende una unidad de procesador o hardware de propósito especial adaptado para llevar a cabo un método de acuerdo con una cualquiera de las reivindicaciones 1-29.

31. Un método para decodificar un código (410) de posición que codifica al menos una primera coordenada (x;y) para un primer punto y una primera dimensión en una superficie, método que comprende identificar un primer número predeterminado de números que forman una secuencia parcial de una secuencia (PD) de números primaria basándose en una representación digital del código de posición, secuencia parcial que tiene un lugar P determinado inequívocamente en la secuencia de números primaria, lugar que corresponde a la primera coordenada;

caracterizado porque el lugar P de la secuencia parcial en la secuencia (PD) de números primaria se determina usando al menos dos secuencias (A1-A4) de números secundarias, cada una de las cuales tiene una base que es menor que la base de la secuencia de números primaria, en el que al menos una secuencia parcial de la secuencia de números primaria puede mapearse con una combinación de una secuencia parcial de cada una de las al menos dos secuencias de números secundarias.

32. Un método de acuerdo con la reivindicación 31, en el que determinar el lugar P de la secuencia parcial en la secuencia (PD) de números primaria comprende convertir la secuencia parcial de la secuencia de números primaria en una combinación de una secuencia parcial de cada una de las secuencias (725; 745) de números secundarias.

33. Un método de acuerdo con la reivindicación 31 ó 32, que comprende además determinar el lugar en la secuencia de números secundaria respectiva de cada una de las secuencias parciales en la combinación (730) y determinar el lugar P en la secuencia de números de diferencia primaria basándose en la combinación de los lugares en las secuencias (735; 755) de números secundarias.

34. Un método de acuerdo con la reivindicación 32 ó 33, en el que convertir la secuencia parcial de la secuencia de números primaria en una secuencia parcial de cada una de las secuencias de números secundarias comprende convertir cada número d en la secuencia parcial de la secuencia de números primaria en un conjunto de números d₁,...,d_n, según lo siguiente: d=d₁+b_i*d₂+...b₁*b₂...*b_n-1*d_n, donde n es el número de secuencias de números secundarias y b_i es la base en la secuencia i de números secundaria.

35. Un método de acuerdo con una cualquiera de las reivindicaciones 32-34, en el que el lugar P en la secuencia de números primaria se determina usando el teorema chino del resto como:

P=(sum(i=1,n)((L/l_i)*p_i*q_i))(mod L)

donde L = prod(i=1,n)l_i, p_i es el lugar en la secuencia i de números secundaria, l_i es la longitud de la secuencia i de números secundaria y n es el número de secuencias de números secundarias y q_i*(L/l_i)=1(mod l_i).

36. Un método de acuerdo con una cualquiera de las reivindicaciones 31-35, que comprende además determinar una coordenada (xs;ys) adicional para el primer punto y la primera dimensión determinando el lugar en la secuencia de números principal de la secuencia parcial para la coordenada 0.

37. Un método de acuerdo con una cualquiera de las reivindicaciones 31-36, en el que el código (410) de posición codifica además una segunda coordenada (y;x) para la primera posición y para una segunda dimensión y que comprende además la etapa de identificar un tercer número predeterminado de números que forman una secuencia parcial de una segunda secuencia de números primaria, basándose en la representación digital del código de posición, secuencia parcial que tiene un lugar determinado inequívocamente en la segunda secuencia de números primaria, lugar que corresponde a la segunda coordenada; y de determinar el lugar de la secuencia parcial en la segunda secuencia de números primaria usando al menos dos segundas secuencias de números secundarias, cada una de las cuales tiene una base que es menor que la base de la segunda secuencia de números primaria.

38. Un método de acuerdo con una cualquiera de las reivindicaciones 31-37, en el que el método se lleva a cabo en un dispositivo de decodificación que recibe la representación digital del código de posición como señal de entrada y proporciona al menos la primera coordenada para el primer punto como señal de salida.

39. Un dispositivo para decodificar un código (410) de posición, que codifica al menos una primera coordenada para un primer punto y una primera dimensión en una superficie, dispositivo que comprende un sensor (14) para proporcionar una representación digital del código de posición que va a decodificarse, y un procesador (16) que está dispuesto para identificar un primer número predeterminado de números que forman una secuencia parcial de la secuencia (PD) de números primaria, basándose en la representación digital del código de posición, secuencia parcial que tiene un lugar P determinado inequívocamente en la secuencia de números primaria, lugar que corresponde a la primera coordenada;

caracterizado porque el dispositivo comprende además una memoria que almacena al menos dos secuencias (A1-A4) de números secundarias cada una de las cuales tiene una base que es menor que la base de la secuencia de números primaria, en el que al menos una secuencia parcial de la secuencia de números primaria puede mapearse con una combinación de una secuencia parcial de cada una de las al menos dos secuencias de números secundarias, y porque el procesador (16) está dispuesto además para determinar el lugar P en la secuencia de números primaria mediante las secuencias de números secundarias.

40. Un dispositivo de acuerdo con la reivindicación 39, en el que el procesador (16) está dispuesto además para convertir la secuencia parcial de la secuencia (PD) de números primaria en una combinación de una secuencia parcial de cada una de las secuencias (A1-A4) de números secundarias para determinar el lugar P de la secuencia parcial en la secuencia (PD) de números primaria.

41. Un dispositivo de acuerdo con la reivindicación 40, en el que el procesador (16) está dispuesto además para determinar el lugar en la secuencia (A1-A4) de números secundaria respectiva de cada una de las secuencias parciales en la combinación y determinar el lugar P en la secuencia (PD) de números de diferencia primaria basándose en la combinación de los lugares en las secuencias de números secundarias.