Método para comprimir los datos de aceleración de una búsqueda de ruta.

Un método de creación de datos de mapa, que incluye datos de aceleración de búsqueda dispuestos para aumentar la velocidad a la que se puede planificar una ruta a través de un mapa electrónico,

el método que comprende usar al menos un aparato de procesamiento para procesar el mapa electrónico que comprende una pluralidad de segmentos navegables, que representan segmentos de una ruta navegable en el área cubierta por el mapa, que comprende hacer al aparato de procesamiento:

dividir el mapa en una pluralidad de regiones (600, 602, 604, 606, 608);

procesar los segmentos navegables a fin de generar un vector de bit (704) para al menos algunos de los segmentos navegables (700, 702) dentro de una región del mapa electrónico, dicho vector de bit que comprende una pluralidad de bits, cada uno que indica si el segmento navegable es parte de una ruta de coste mínimo a una de las otras regiones; y

procesar los vectores de bit generados para la región a fin de comprimir los datos,

caracterizado por que la comprensión incluye el cálculo de la correlación de bits en los vectores de bit y la coalescencia de dichos bits según la correlación calculada.

Método para comprimir los datos de aceleración de una búsqueda de ruta Campo de la invención La presente invención se refiere a un método informatizado de generación de datos de mapa y sistemas relacionados. En particular, pero no exclusivamente, el método de generación de datos de mapa se usa para facilitar la planificación de ruta entre al menos dos puntos según una función de coste predeterminada. Las realizaciones de la invención pueden generar datos de aceleración de búsqueda que, cuando se usan en una planificación de ruta, reducen el tiempo que lleva generar una ruta.

Antecedentes de la invención Los dispositivos de planificación de ruta (a menudo conocidos como Nav. por Satélite, Dispositivos de Navegación Portátiles (PND) o similares) junto con los sitios web accesibles a través de la Red Informática Mundial (WWW) tales como http://routes.tomtom.com/ son bien conocidos y permiten a un usuario de los mismos planificar una ruta entre dos puntos. Tal tecnología se puede conocer genéricamente como planificación de ruta electrónica o sólo planificación de ruta.

Los datos de mapas de tal planificación de ruta llegan de vendedores de mapas especialistas tales como Tele Atlas NV. Cuando se realiza en un PND tal planificación de ruta típicamente se usan datos de ubicación de un sistema de GPS. No obstante, otras aplicaciones pueden permitir a un usuario introducir su ubicación u otro punto a ser considerado para propósitos de planificación de ruta.

Tales datos de mapa comprenden una pluralidad de carreteras (y otros trayectos navegables) que se pueden describir como líneas – es decir vectores o segmentos de carretera (por ejemplo un punto de inicio, punto final, dirección de una carretera, con una carretera entera que está compuesta de muchos cientos de tales segmentos, cada uno definido únicamente por parámetros de dirección de punto de inicio/punto final) . Un mapa es entonces un conjunto de tales vectores de carretera, datos asociados con cada vector (límite de velocidad; dirección de viaje, etc.) más puntos de interés (POI) , más nombres de carreteras, más otros rasgos geográficos como límites de parques, límites de ríos, etc., todos los cuales se definen in términos de vectores. Todos los rasgos de mapa (por ejemplo vectores de carretera, POI, etc.) se definen típicamente en un sistema de coordenadas que corresponde con o se refiere al sistema de coordenadas GPS, permitiendo que la posición del dispositivo que se determina a través del sistema de GPS sea localizada sobre la carretera relevante mostrada en un mapa y para que una ruta óptima sea planificada a un destino.

Tales datos de mapa pueden ser extensos. Ello es conocido para mapas que cubren áreas que tienen por encima de 120.000.000 vectores y un ejemplo de tales datos de mapa sería un mapa que cubriría el área de Europa y Rusia. Por tanto, la planificación de una ruta usando tales datos de mapa es compleja y puede llevar mucho tiempo. También, se conoce que tal planificación de ruta es un compromiso entre precisión y tiempo.

La técnica anterior que ha considerado ideas en mejorar la velocidad a la que puede darse el encaminamiento incluye la US 6.636.800 que trata refinamientos de la estrategia de búsqueda mejor-primero A* adecuada para tamaños de mapa mucho más pequeños tales como la red de autopistas de Europa Occidental (que tiene aproximadamente 400.000 vectores) .

La tesis doctoral titulada “Engineering and Augmenting Route Planning Algorithms” de Daniel Delling (XP002612394) , y de fecha 10 de febrero de 2009, trata técnicas de aceleración para encaminamiento en escenarios aumentados, es decir dependientes del tiempo y de criterios múltiples.

El artículo titulado “Huffman Coding in Bit-Vector Compression” de Matti Jakobsson (XP0000949386) , y de fecha 1 de octubre de 1978, trata un caso especial de codificación de Huffman que hace posible codificar vectores de bit sin el uso de tablas de código.

La tesis titulada “Arc-Flag Compression Student Thesis” de Andreas Gemsa (XP002612411) , y de fecha 19 de diciembre de 2008, trata dos mecanismos diferentes de reducción del espacio necesario para almacenar marcas de arco.

Compendio de la invención Según un primer aspecto de la invención se proporciona un método de creación de datos de mapa según la reivindicación 1.

Preferiblemente, el método usa una función que varía con el tiempo asociada con al menos algún, y generalmente cada, segmento navegable de la red central para determinar si el segmento navegable es parte de la ruta de coste mínimo para al menos una de las regiones y registrar esta determinación en los datos de aceleración buscados. Los expertos apreciarán que generalmente cada segmento navegable, puede ser un nodo, dentro de los datos de mapa

puede tener la función que varía con el tiempo asociada con el mismo. Por ejemplo, la función que varía con el tiempo puede comprender la velocidad media en el segmento navegable en diversos intervalos de tiempo. Por ejemplo, la velocidad media se puede especificar en intervalos de 5 minutos o similares.

Preferiblemente, el método reduce el número de segmentos navegables a ser considerados en la creación de los datos de aceleración de búsqueda eliminando los segmentos navegables para formar una red central de segmentos navegables. Convenientemente, la red central se genera eliminando segmentos navegables para los que se pueden recuperar más tarde los datos de aceleración de búsqueda. Tal método es ventajoso dado que permite que los datos de aceleración de búsqueda sean determinados sustancialmente para todos los segmentos navegables dentro del mapa electrónico planificando por ello la ruta a ser acelerada desde cualquier segmento navegable dentro del mapa.

Algunas realizaciones de la invención pueden utilizar una cualquiera o más de las siguientes técnicas para eliminar segmentos navegables del mapa electrónico anterior a la creación de los datos de aceleración de búsqueda:

! cumplir un criterio predeterminado relacionado con la propiedad de la carretera;

! eliminar segmentos navegables de la red que forman parte de la red que son suficientemente pequeños según algún criterio predeterminado y que podrían ser desconectados del resto de la red eliminando un conjunto de segmentos navegables que cumplen algún criterio predeterminado adicional;

! colapsar nodos, lo cual ocurre en cruces entre segmentos navegables, uno sobre otro en situaciones predeterminadas; y

! colapsar nodos uno sobre otro si tienen dos o menos de dos segmentos navegables conectados al mismo.

Tales técnicas se consideran ventajosas dado que reducen el número de segmentos navegables que necesitan ser considerados durante la generación de los datos de aceleración de búsqueda lo que aumenta, quizás significativamente, la velocidad a la que se pueden crear los datos de aceleración de búsqueda.

Realizaciones de la invención pueden utilizar una cualquiera o más de las siguientes técnicas para comprimir los datos de aceleración de búsqueda una vez que han sido creados:

! Juntar bits sustancialmente correlacionados en los datos de aceleración de búsqueda a fin de reducir el número de bits a codificar de una manera sin pérdidas;

! Juntar bits correlacionados en los datos de aceleración de búsqueda a fin de realizar una comprensión con pérdidas;

! Reordenar bits en datos de aceleración de búsqueda juntados según sus correlaciones;

! Codificar con Huffman los datos de aceleración de búsqueda.

En algunas realizaciones los bits sustancialmente correlacionados se pueden considerar como casi correlacionados unos con otros, es decir puede haber pequeñas diferencias en los datos de aceleración de búsqueda que van a ser comprimidos. La cercanía de los datos de aceleración de búsqueda en cuyo punto se unen puede ser ajustable según un criterio predeterminado. De esta manera, las realizaciones de la invención que implementan tal coalescencia con pérdidas además reducen la huella de memoria ocupada por los datos de aceleración de búsqueda a costa de aumentar el procesamiento requerido para realizar la planificación de ruta usando los datos de aceleración de búsqueda.

Realizaciones de las que reordenar los datos de aceleración de búsqueda son ventajosas debido a que se puede aumentar la eficiencia a la que la compresión de Huffman puede comprimir los datos de aceleración de búsqueda.

Preferiblemente, el método divide el mapa electrónico en un conjunto de regiones jerárquicas de manera que el o cada segmento navegable se categoriza en al menos una región en cada nivel de la jerarquía.... [Seguir leyendo]

1. Un método de creación de datos de mapa, que incluye datos de aceleración de búsqueda dispuestos para aumentar la velocidad a la que se puede planificar una ruta a través de un mapa electrónico, el método que comprende usar al menos un aparato de procesamiento para procesar el mapa electrónico que comprende una pluralidad de segmentos navegables, que representan segmentos de una ruta navegable en el área cubierta por el mapa, que comprende hacer al aparato de procesamiento:

dividir el mapa en una pluralidad de regiones (600, 602, 604, 606, 608) ;

procesar los segmentos navegables a fin de generar un vector de bit (704) para al menos algunos de los segmentos navegables (700, 702) dentro de una región del mapa electrónico, dicho vector de bit que comprende 10 una pluralidad de bits, cada uno que indica si el segmento navegable es parte de una ruta de coste mínimo a una de las otras regiones; y

procesar los vectores de bit generados para la región a fin de comprimir los datos,

caracterizado por que la comprensión incluye el cálculo de la correlación de bits en los vectores de bit y la coalescencia de dichos bits según la correlación calculada.

2. El método según la reivindicación 1, en donde la compresión además incluye reordenar los bits en los vectores de bit (704) según la correlación calculada.

3. El método según la reivindicación 1 o 2, en donde la compresión además incluye la codificación de Huffman de los vectores de bit (704) .

4. El método según cualquier reivindicación precedente, en donde el mapa se divide en una pluralidad de regiones

jerárquicas (1906) de manera que cada segmento navegable se categoriza en al menos una región en cada nivel (600; 602, 604, 606, 608) de la jerarquía.

5. El método según cualquier reivindicación precedente, en donde la función que varía con la hora (752) está asociada con al menos algún, y generalmente cada, segmento navegable, y en donde las funciones que varían con la hora (752) se usan para determinar si el segmento navegable es parte de una ruta de coste mínimo a una de las otras regiones en una pluralidad de horas diferentes.

6. El método de la reivindicación 5, en donde la pluralidad de bits del vector de bit generado (704) cada uno indica si el segmento navegable es parte de una ruta de coste mínimo a una de las otras regiones en cualquiera de la pluralidad de diferentes horas.

7. El método según la reivindicación 5 o 6, en donde la función que varía con la hora (752) asociada con un

segmento navegable representa la velocidad media en el segmento navegable en una pluralidad de intervalos de tiempo.

8. El método según cualquier reivindicación precedente, que comprende:

reducir el número de segmentos navegables a ser considerado en la creación de los datos de aceleración de búsqueda eliminando segmentos para formar una red central de segmentos navegables (1902, 1904) .

9. El método según la reivindicación 8 en el que los segmentos navegables se eliminan del mapa electrónico (1902, 1904) anterior a la creación de los datos de aceleración de búsqueda según uno cualquiera o más de los siguientes criterios:

(i) eliminar segmentos navegables que cumplen un criterio predeterminado relacionado con la propiedad de la carretera;

(ii) colapsar nodos, lo que ocurre en confluencias entre segmentos navegables, unos en otros en situaciones predeterminadas; y

(iii) colapsar nodos unos sobre otros si tienen dos o menos de dos segmentos navegables conectados a los mismos.

10. El método según cualquier reivindicación precedente, en donde la pluralidad de segmentos navegables del

mapa electrónico cada uno tiene una pluralidad de nodos asociados con los mismos y cada uno tiene al menos un atributo asociado que representa un parámetro de la ruta navegable, el al menos un atributo asociado con un segmento navegable incluye cualquiera de los siguientes:

(i) el tipo del segmento navegable;

(ii) la velocidad media a lo largo del segmento navegable;

(iii) la longitud del segmento navegable; y

(iv) la conectividad del segmento navegable a otros segmentos navegables,

y en donde la categorización de cada uno de los segmentos navegables usa una valoración del al menos un atributo para asegurar que los nodos asociados con los segmentos navegables están equilibrados a través de las regiones 5 del mapa electrónico.

11. El método según cualquier reivindicación precedente, en donde la ruta de coste mínimo se determina según uno de los siguientes criterios de coste: la distancia más corta, el tiempo de viaje más corto; el de menos impacto ambiental; el de menos combustible usado; y el de menos CO2 generado.

12. El método según cualquier reivindicación precedente, en donde la primera pluralidad de bits del vector de bit

generado cada uno indica si el segmento navegable es parte de una ruta de coste mínimo a una de las otras regiones según un primer criterio de coste, y en donde una segunda pluralidad de bits del vector de bit generado cada uno indica si el segmento navegable es parte de una ruta de coste mínimo a una de las otras regiones según un segundo criterio de coste.

13. El método según cualquier reivindicación precedente, en donde los datos de mapa creados comprenden un fichero lateral que incluye los datos de aceleración de búsqueda, el fichero lateral que está asociado con el mapa electrónico usado para generar el fichero lateral.

14. Un dispositivo informático dispuesto para realizar el método de cualquiera de las reivindicaciones precedentes.

15. Un producto de programa informático que contiene instrucciones que, cuando se leen en una máquina, hacen a

la máquina realizar el método de cualquiera de las reivindicaciones 1 a 13, encarnado opcionalmente en un medio 20 legible por ordenador.