ES2344330T3

ES2344330T3 - Metodo y dispositivo de procesamiento de datos.

Info

Publication number: ES2344330T3
Application number: ES08701088T
Authority: ES
Inventors: Alexandru Serbanescu
Original assignee: TomTom International BV
Current assignee: TomTom International BV
Priority date: 2007-01-10
Filing date: 2008-01-09
Publication date: 2010-08-24
Anticipated expiration: 2028-01-09
Also published as: CN101578633A; TW200844900A; JP2010519565A; EP2126847B1; DE602008001108D1; ATE466353T1; US20080166071A1; AR064839A1; EP2126847A1; RU2009130339A; AU2008204560A1; WO2008083981A1

Abstract

Un método de procesamiento de datos de píxeles (7) de un campo de vista (5), en el que el campo de vista comprende una parte de un mapa digital (1) que se mostrará e incluye un conjunto de píxeles (7), el mapa digital (1) comprende un conjunto de parches de datos (3) que incluyen al menos un punto de datos, y el campo de vista (5) incluye un conjunto de parches de dichos de datos (3), el método es caracterizado por: (i)identificar (504), para un dicho píxel (7), un parche de datos (3) en que dicho píxel se encuentra (7); (ii)ubicar (506-512) un borde (9) de dicho parche de datos (3) que se encuentra dentro de dicho campo de vista (5); (iii)procesar (522) todos los píxeles (7) de dicho campo de vista (5) que se encuentran dentro de dicho borde (9) para proporcionar un parche de datos procesados; (iv)ubicar (504-512), para cada uno de los parches de datos sin procesar (3) dentro del campo de vista (5) que sean adyacentes al borde (9) de un parche de datos procesado, un borde (9) de un parche de datos sin procesar (3) que se encuentra dentro de dicho campo de vista (5); (v)procesar (522), para cada uno de los parches de datos sin procesar (3) todos los píxeles sin procesar (7) que se encuentran dentro del borde de dicho parche de datos sin procesar (3) para así proporcionar un parche de datos procesados; y (vi)repetir los pasos (iv) y (v) hasta que todos los parches de datos (3) dentro de dicho campo de vista hayan sido procesados (5).

Description

Método y dispositivo de procesamiento de datos.

Campo de la invención

Esta invención se refiere a métodos y dispositivos de procesamiento de datos, particularmente pero no exclusivamente para píxeles de un campo de vista. Una representación ilustrativa de la presente invención se refiere a un dispositivo de navegación portátil (PND) que está configurado para mostrar dinámicamente un campo de vista que comprende una parte de un mapa digital.

Antecedentes de la invención

Una variedad de diferentes dispositivos de navegación portátiles han sido previamente propuestos (vea
www.garmin.com para varios ejemplos). Cada uno de estos dispositivos incluye una pantalla la cual es controlable por un procesador para mostrar una parte (en lo sucesivo "campo de vista") de un mapa digital almacenado en el dispositivo. En un ejemplo ilustrativo tales dispositivos pueden ser utilizados por excursionistas para ayudarles a ellos con la navegación mientras que viajan de un punto a otro. Algunos de tales dispositivos tienen capacidades de navegación satelital integradas (tal como capacidades de navegación GPS), similares a las que son bien conocidas en el arte, las cuales habilitan el dispositivo para determinar con precisión su posición actual y mostrarle al usuario un campo de vista en el cual el dispositivo, y por lo tanto el usuario, es actualmente ubicado. Otros dispositivos simplemente proporcionan al usuario un campo de vista que incluye una posición seleccionada por el usuario, y aún otros dispositivos proporcionan ambas funciones. Para proporcionar un campo de vista para mostrar, los dispositivos de este tipo suelen incluir un procesador que es configurado para recuperar los datos del mapa digital de un depósito dentro del dispositivo, y luego presentar una imagen de esos datos recuperados.

Típicamente la imagen del campo de vista mostrada por tales dispositivos incluye información tanto geográfica como topográfica. Por esto nos referimos que es habitual para el campo de vista incluir información de dos dimensiones (tal como la posición y forma de las características geográficas naturales y hechas por el hombre, por ejemplo, ríos, carreteras, etc.) también como una representación de la topografía (por ejemplo relieve de los contornos) del campo de vista visualizado. Algunos dispositivos transmiten información topográfica sombreando el campo de vista visualizado, y otros transmiten información topográfica aplicando contornos (líneas uniendo puntos de igual altura) o isóclinas (líneas de igual pendiente) de la información geográfica de dos dimensiones.

Mientras que tal funcionalidad es particularmente útil cuando se realiza como un software ejecutado por el procesador de un dispositivo de navegación personal, este también puede ser realizado como un software corriendo en una variedad de otros dispositivos electrónicos- incluyendo, sin limitación, teléfonos móviles, asistentes digitales portátiles, computadores personales y computadores de mesa.

Aunque la información topográfica puede ser representada en una variedad de maneras diferentes, sigue siendo el caso que con el fin de representar la altura (por ejemplo relativa al nivel del mar) de cada píxel del campo de vista que es visualizado es necesario recuperar la información de altura del mapa digital almacenado en el dispositivo y luego utilizar esta información para representar una imagen para mostrar. Suele ser el caso de que el procesamiento de imágenes de campos de vista es computacionalmente intensivo y como consecuencia, es importante procesar dichos datos de manera eficiente, si tales dispositivos funcionan eficientemente. Esto es particularmente el caso cuando la funcionalidad de este tipo es realizado en un dispositivo de soporte de mano donde la potencia de procesamiento disponible y la capacidad de memora está necesariamente limitada por el hecho de que el dispositivo debe ser relativamente compacto de modo que pueda fácilmente ser llevado por el usuario.

Una manera ilustrativa de almacenar los datos del mapa se representa esquemáticamente en la Fig. 1. En este ejemplo, los datos del mapa -en particular los datos de altura (entendiendo por tal la información de altura para ubicaciones geográficas específicas)- se almacenan en una cuadrícula 1 de parches de datos 3.

En este ejemplo cada parche de datos es una matriz de puntos de datos, por ejemplo una matriz de valores de altura tomados en ciertas ubicaciones (x, y) en la superficie de la tierra (podemos considerar para simplificar una cuadrícula uniformemente distribuida de las medidas tomadas cada 3'' de latitud o longitud). Los parches de datos son adyacentes y en este caso han sido marcados con sus índices de matriz (por ejemplo el parche de datos 11 es el primer parche en la primera fila, el parche de datos 21 es el primer parche en la segunda fila, y y así sucesivamente). Proyectado en la cuadrícula 1 hay una ventana rectangular 5 que representa una parte del mapa que es mostrada en la pantalla de visualización de un PND en cualquier momento (por ejemplo en el contexto de esta aplicación, "el campo de vista"). En este caso la ventana 5 está alineada con la cuadrícula, pero como será después descrita la ventana puede ser rotada con respecto a la cuadrícula (ya sea automáticamente como la posición de los cambios de dispositivo o en respuesta a una instrucción proporcionada por el usuario para girar el campo de vista visualizado).

En bajos niveles de aumento del mapa (en los que el aumento de la ventana cubre una proparte relativamente grande de la cuadrícula subyacente) la densidad de los píxeles del campo de vista 5 (los cuales corresponden a los píxeles de la pantalla) puede ser igual o mayor que la densidad de los puntos de datos. Sin embargo, en aumentos mayores del mapa típico del dispositivo en uso, la densidad de los píxeles normalmente será mucho menor que la densidad de los puntos de datos en el mapa correspondiente.

La Fig. 2 es una representación esquemática de la altura de los puntos de datos para un aumento mayor del mapa. En este ejemplo ilustrativo los puntos de medida de altura son indicados por estrellas, y los píxeles de un campo de vista que han sido proyectados dentro del mapa de altura los puntos de datos son indicados por círculos. La Fig. 2 muestra un área pequeña alrededor de las coordenadas 50.0N, 4.1E. Las estrellas (medidas de altura) son distribuidas aproximadamente cada 3''. Dado que el área representada es alrededor de la latitud 54.0N, cada paso horizontal es aproximadamente 56 m y cada paso vertical es aproximadamente 90 m (este es el caso que alrededor de los círculos paralelos al Ecuador se disminuyen a media que se aproximan a los polos).

Con el fin de interpretar los datos de altura para cada píxel en la pantalla, el procesador del PND implementa un algoritmo conocido para computar un coeficiente de sombreado para cada píxel. El coeficiente de sombreado para cada píxel es derivado de los valores de datos de puntos de altura en la proximidad de la proyección del correspondiente píxel en el mapa, y estos valores son leídos por el procesador de altura de los archivos de datos almacenados en el PND. Este proceso se repite cada vez que se procesa un nuevo campo de vista.

La velocidad a la que los datos pueden ser leídos desde un dispositivo de almacenamiento es a menudo el factor más significativo afectando a la velocidad de este proceso de interpretación. Una de las razones es que normalmente no se almacenan los elementos de datos individuales que tienen que ser leídos del dispositivo de almacenamiento del PND adyacentes entre sí, pero repartidos por todo el dispositivo de almacenamiento.

Aparte de la velocidad de interpretación, otros factores de importancia son la cantidad de memoria utilizada por el proceso y la calidad de la imagen interpretada. Estos tres criterios son para algunos dependientes uno del otro ya que una relajación de las restricciones impuestas por algún otro factor puede mejorar el desarrollo de otro. Por ejemplo, incrementado la resolución de la imagen probablemente reducirá la velocidad de procesamiento e incrementará la cantidad de memoria utilizada, mientras que -por el contrario- una disminución en la resolución de la imagen probablemente aumentará la velocidad del proceso de interpretación y disminuirá la cantidad de memoria utilizada.

Una forma de abordar el problema de almacenamiento de una matriz de elementos de datos para recuperación eficiente sería concatenar juntos y almacenar los elementos de datos de un parche de datos determinado, ya sea por fila o por columna. En tal caso un acuerdo dado para una fila determinada, por ejemplo, de un campo de vista podría ser fácilmente recuperar simplemente mediante la lectura de datos desde una posición de inicio de los datos concatenados (cuya posición de inicio corresponde al primer píxel de la fila de píxeles siendo procesados) a una posición final de los datos concatenados (cuya posición final corresponde al último píxel de la fila de píxeles que se están procesando). Tal acuerdo sería ventajoso en que no sería necesario leer todos los datos de los datos concatenados, simplemente los datos relevantes para la fila que está siendo procesada.

Si el campo de vista debe ser, como se indica en la Fig. 1, de norte a sur alineado con los puntos de datos de modo que la proyección de las filas de píxeles de la pantalla es paralela con las filas de puntos de datos de altura, entonces el ya mencionado proceso podría ser implementado y este sería relativamente fácil de cargar y procesar, a su vez, todas las filas o columnas necesarias de un parche determinado, y luego pasar al siguiente parche. Por ejemplo uno podría desplazarse a través de los píxeles de la primera fila del campo de vista de izquierda a derecha hasta que la proyección en el mapa alcanza un nuevo parche, procesar estos datos (los cuales incluyen la carga de los datos de altura correspondientes desde el número de línea del correspondiente parche, y computando el porcentaje sombreado), y luego pasar a la siguiente fila del campo de vista y repetir el proceso. Cuando la última fila de un parche determinado es alcanzada el proceso puede entonces ser reiniciado desde el píxel de la primera fila que es adyacente del píxel de la primera fila donde el procesamiento terminó previamente, y este proceso puede ser repetido hasta que todos los píxeles del campo de vista a ser mostrados han sido procesados.

Sin embargo si el campo de vista puede ser rotado con respecto al mapa de puntos de datos, como es mostrado en la Fig. 3 (ver también US 4,970,682), entonces tal proceso podría no funcionar correctamente. Por ejemplo, si consideramos el modo de reproducir la primera fila del campo de vista representado en la Fig. 3, este es inmediatamente aparente en la primera instancia en que los datos de puntos de altura de diferentes parches tendrán que ser recuperados, y en segunda instancia que los píxeles adyacentes de la fila pueden pertenecer a diferentes filas del mismo parche o incluso a diferentes filas de diferentes parches. En otras palabras, para reproducir las filas del campo de vista ahora sería necesario leer los datos no adyacentes para nuevos píxeles mientras en el ejemplo previamente descrito (donde el campo de vista es alineado norte-sur con el mapa) varios píxeles en una fila dada de la pantalla corresponden a varios valores de altura en la misma fila de datos.

A continuación si se procesa la segunda fila del campo de vista, probablemente sería necesario volver a cargar previamente parches cargados y tal vez también volver a cargar las filas de datos previamente cargadas del mapa. Recargar los parches de datos y los elementos de datos podría atrasar el proceso de reproducción, y estas demoras podrían agravarse aún más por el factor de que cada uno de los parches de datos tiene un encabezado que también tendría que ser cargado cada vez que el proceso de reproducción es conmutado de un parche a otro.

Varios intentos han sido hechos para abordar tales problemas. En un arreglo propuesto previamente, la reproducción dinámica de datos de altura (por los cuales nos referimos a, información topográfica reproducida mostrada cada vez que el campo de vista cambia) fue evitada completamente y pre procesar los datos de altura fue empleado en su lugar, no solamente en el contexto de una imagen sino también en el contexto de los datos de vector. Por ejemplo algunos dispositivos PND peatonales ofrecidos para la venta por Garmin International Inc. emplean isóclinas pre procesadas para algunas áreas geográficas bien definidas donde se soporta esta funcionalidad.

Una diferencia principal entre la reproducción dinámica y el pre procesamiento es que en el caso de una reproducción dinámica tal como isóclinas (siendo simplemente un ejemplo de la información topográfica) son computados cada vez que la vista actual es reproducida. Una ventaja de la reproducción dinámica es que esas isóclinas pueden ser más exactamente representadas en cualquier nivel de zoom del mapa. Otra ventaja de la reproducción dinámica es que la disposición de la información topográfica no es restringida solamente para aquellas áreas geográficas para las cuales las isóclinas han sido previamente calculadas, sino pueden en su lugar ser provistas por cualquier región donde esté disponible la información de altura. Aún otra ventaja es que como las isóclinas (por ejemplo) son dinámicamente reproducidas como se requiera, ya no es necesario almacenar información de una isóclina pre procesada.

En otro acuerdo, un proceso de reproducción dinámico fue propuesto en el cual los datos de altura disponibles fueron despojados a una trama de pequeño tamaño que contenía un subconjunto de datos que abarca el campo de vista. El concepto general de este enfoque fue que reduciendo la cantidad de datos a ser procesados, la reproducción dinámica podría proporcionar sin afectar negativamente el rendimiento del PND. Como ilustración, si imaginamos una situación donde la resolución actual de los datos de altura según el mapa digital es alrededor de una medida cada 3'' de latitud y longitud, entonces un subconjunto más fácilmente procesado puede ser creado considerando solo aquellas medidas de altura que se producen cada 300'', por ejemplo. De esta manera es posible cubrir un área que es lo suficientemente grande para contener alternativas del actual campo de vista por medio de un subconjunto razonablemente pequeño de puntos de datos de altura que pueden fácilmente ser procesados.

El principal inconveniente de este enfoque es que utilizando solo un subconjunto de los datos disponibles, la resolución inicial de los datos originales se pierde. En otras palabras, utilizando un subconjunto de datos inevitablemente significa que solo la información generalizada puede ser mostrada, y como resultado es probable que esta información generalizada no iguale correctamente (al menos al mismo grado que los datos disponibles actualmente) a la situación real en el terreno. Esta pérdida en la precisión es manifestada no solamente como una pérdida de información de altura detallada, sino también como una pérdida en la forma topográfica de las características geográficas representadas.

La presente invención, al menos en una realización de la misma, pretende abordar tales problemas. En particular un aspecto de la presente invención busca proporcionar un arreglo mediante el cual se puede proporcionar representación dinámica (en cualquier sistema) sin afectar negativamente a la calidad de la imagen generada, sin ralentizar excesivamente el proceso de reproducción, y sin tener que comprometer una cantidad relativamente grande de memoria rápida al proceso de reproducción.

Resumen de la invención

En búsqueda del precedente, una realización ahora preferida de la presente invención proporciona un método de procesamiento de datos para píxeles de un campo de vista, donde el campo de vista comprende una parte de un mapa digital a ser mostrado e incluye un conjunto de píxeles, el mapa digital comprende un conjunto de parches de datos que cada uno incluye al menos un punto de datos, y el campo de vista incluye un conjunto de dichos parches de datos, el método se caracteriza por: identificar, para dicho píxel, un parche de datos en el cual dicho píxel se encuentra; ubicar un borde de dicho parche de datos que se encuentre dentro de dicho campo de vista; procesar todos los píxeles de dicho campo de vista que se encuentren dentro de dicho borde para proporcionar un parche de datos procesador; ubicar, para cada uno de los parches de datos sin procesar dentro de un campo de vista que está junto al borde de un parche de datos procesados, un borde un parche de datos sin procesar que se encuentra dentro de dicho campo de vista; procesar, para cada parche de datos sin procesar, todos los parches de datos sin procesar que se encuentra dentro del borde de dicho parche de datos sin procesar para así proporcionar un parche de datos procesado; y repetir los pasos hasta que todos los parches de datos dentro de dicho campo de vista hayan sido procesados.

Otra realización ahora preferida de la presente invención se refiere a un dispositivo de procesamiento de datos configurado para procesar píxeles dentro de un campo de vista, donde el campo de vista comprende una parte de un mapa digital que se va a mostrar e incluye un conjunto de píxeles, el mapa digital comprende un conjunto de parches de datos los cuales cada uno incluyen al menos un punto de datos, y el campo de vista incluye un conjunto de dichos parches de datos, el dispositivo comprende: almacenamiento para dicho mapa digital; y un procesador para acceder al mapa digital almacenado en dicho depósito; caracterizado en que el dispositivo además comprende: un módulo de procesamiento de datos controlable por dicho procesador para:

(i).: identificar para dicho píxel, un parche de datos en el cual dicho píxel se encuentra;

(ii).: ubicar un borde para dicho parche de datos que se encuentra dentro de dicho campo de vista;

(iii).: procesar todos los píxeles de dicho campo de vista que se encuentra dentro de dicho borde para proporcionar un parche de datos procesado;

(iv).: Ubicar, para cada uno de cualquiera de los parches de datos sin procesar dentro del campo de vista que esta junto al borde de un parche de datos procesador, un borde de un parche de datos sin procesar que se encuentra dentro de dicho campo de vista;

(v).: procesar, para cada uno de los parches de datos sin procesar, todos los píxeles sin procesar que se encuentran dentro del borde de dicho parche de datos sin procesar para así proporcionar un parche de datos procesado; y

(vi).: repetir los pasos (iv) y (v) hasta que todos los parches de datos dentro de dicho campo de vista hayan sido procesados.

Otra realización ahora preferida de la presente invención se refiere a un software de computador que comprende uno o más módulos de software operable, cuando es ejecutado en un ambiente de ejecución, para causarle al procesador:

(i).: identificar, para un píxel de un campo de vista que comprende una parte de un mapa digital que se va a mostrar, un parche de datos en el cual dicho píxel se encuentra, donde el mapa digital comprende un conjunto de parches de datos el cual cada uno incluye al menos un punto de datos y dicho campo de vista comprende un conjunto de dichos píxeles;

(ii).: ubicar un borde de dicho parche de datos que se encuentra dentro de dicho campo de vista;

(iii).: procesar un borde de dicho parche de datos que se encuentra dentro de dicho campo de vista;

(iv).: ubicar, para cada uno de cualquiera de los parches de datos sin procesar dentro de un campo de vista que está junto al borde de un parche de datos procesador, un borde de un parche de datos sin procesar que se encuentra dentro de dicho campo de vista;

Una ventaja de un acuerdo implementando las enseñanzas de la invención es el uso sustancial de todos los datos de altura disponibles evitando la pérdida de calidad de imagen que podría ser inherente en un sistema que emplea valores interpolados desde un subconjunto de datos relativamente pequeño. Otra ventaja de un acuerdo que contiene las enseñanzas de la invención es que recargando los mismos datos (ya sea parches de encabezados o datos de elementos propios) pueden al menos ser reducidos sin incrementar la memoria en uso - en particular sin cargar todos los datos que podrían potencialmente ser necesarios en una memoria rápida (una solución que en la práctica sería muy probablemente imposible implementar de manera efectiva).

En términos generales una realización preferida de la invención puede ser resumida como un método que comprende los pasos de: (i) determinar la identidad de un parche de datos en el que se encuentra una proyección de un píxel, (ii) ubicar un borde para ese parche de datos, (iii) procesar píxeles dentro de dicho parche de datos para proporcionar un parche de datos procesados, (iv) ubicar un borde para cada parche de datos sin procesar contiguo a dicho parche de datos procesado, (v) procesar píxeles dentro de cada uno de dicho parche de datos sin procesar, y repetir los pasos (iv) y (v) hasta que todos los parches de datos de un campo de vista hayan sido procesados.

Las ventajas de estas realizaciones se exponen a continuación, y más detalles y características de cada una de estas realizaciones son definidas en las reivindicaciones dependientes que se acompañan y en otra parte en la siguiente descripción detallada.

Breve descripción de los dibujos

Varios aspectos de las enseñanzas de la presente invención, y los arreglos que contienen aquellas enseñanzas, serán en lo sucesivo descritas a modo de ejemplo ilustrativo con referencia a los dibujos que se acompañan, en los cuales:

La Fig. 1 es una representación esquemática de un mapa digital y una ventana superpuesta alineada con la misma;

La Fig. 2 es una representación esquemática de puntos de datos de altura para una ampliación mayor del mapa;

La Fig. 3 es una representación esquemática de un mapa digital y una ventana superpuesta, donde la ventana ha sido rotada con respecto al mapa;

La Fig. 4 es una ilustración esquemática de un Sistema de Posicionamiento Global (GPS);

La Fig. 5 es una ilustración esquemática de componentes electrónicos organizados para proporcionar un dispositivo de navegación;

La Fig.6 es una ilustración esquemática de la manera en la cual un dispositivo de navegación puede implementar las comunicaciones a través de un canal de comunicación;

Las Figs. 7A y 7B son vistas en perspectiva ilustrativas de un dispositivo de navegación;

La Fig. 8 es una representación esquemática de un software ejecutable por el dispositivo de la Fig. 5;

La Fig. 9A es una representación esquemática de una parte de un campo de vista;

Las Figs. 9B a 9F son representaciones esquemáticas de un mapa digital y una ventana superpuesta representadas en la Fig. 3 en diferentes puntos en el método de procesamiento de datos; y

La Fig. 10 es un diagrama de flujo ilustrando los pasos de un método por el cual las enseñanzas de la presente invención pueden ser implementadas.

Descripción detallada de las realizaciones preferidas

Una realización preferida de la presente invención será ahora descrita en el contexto de un software ejecutable por un dispositivo de navegación personal que incluye la capacidad de encontrar la posición GPS y tiene, en esta instancia, ambas funcionalidades de planeamiento de ruta y guía de ruta. Debe ser recordado, sin embargo, que esta descripción es simplemente ilustrativa de las enseñanzas de la presente invención y por lo tanto que la presente invención no debe interpretarse como limitada a un dispositivo de navegación personal que está provisto con funcionalidades de planeamiento de ruta y guía en ruta.

También debe recordarse que las enseñanzas de la presente invención son aplicables a cualquier tipo de dispositivo de computación (por ejemplo un teléfono de radio portátil, un asistente personal digital, o en efecto un recurso de computación de escritorio o en red) que está configurado para reproducir campos de vista, en particular aquellos que incluyen información topográfica. Mientras que la realización que se describe en lo sucesivo tiene una utilidad particular como un dispositivo de mano para excursionistas, ciclistas o personas a caballo, por ejemplo, será inmediatamente apreciado que no hay razón por qué las enseñanzas de la presente invención no podrían también o alternativamente ser implementadas en un dispositivo de navegación para vehículos (o como una parte integral de sistemas electrónicos de vehículos, o como un dispositivo independiente montable en un vehículo) como la visualización de la información topográfica podría proporcionarle al usuario una visión más realista de su entorno que puede ayudar al proceso de navegación.

La fig. 4 ilustra una vista de ejemplo de un Sistema de Posicionamiento Global (GPS), utilizable por dispositivos de navegación. Tales sistemas son conocidos y son usados para una variedad de propósitos. En general, el GPS es un sistema de navegación basado en un radio satélite capaz de determinar posición continua, velocidad, hora, y en algunos casos la información de dirección para un número de usuarios ilimitado. Anteriormente conocido como NAVSTAR, el GPS incorpora un conjunto de satélites los cuales orbitan la tierra en órbitas extremadamente precisas. Basado en estas órbitas precisas, los satélites de GPS pueden retransmitir su ubicación a cualquier número de unidades receptoras.

El sistema GPS es implementado cuando un dispositivo, especialmente equipado para recibir datos GPS, comienza a escanear frecuencias de radio para señales de satélite GPS. A medida que se recibe una señal de radio de un satélite GPS, el dispositivo determina la ubicación precisa de ese satélite por medio de un conjunto de diferentes métodos convencionales. El dispositivo continuará escaneando, en los mayores casos, por señales hasta que este adquiera al menos tres señales de satélite diferentes (señalando esa posición no es normal, pero puede ser determinada, con solo dos señales utilizando otras técnicas de triangulación). Implementando la triangulación geométrica, el receptor utiliza las tres posiciones conocidas para determinar su propia posición bidimensional en relación con los satélites. Esta puede ser hecha de una forma conocida. Adicionalmente, adquiriendo una señal de cuatro satélites permitirá al dispositivo receptor calcular su posición en tres dimensiones por el mismo cálculo geométrico de una forma conocida. Los datos de posición y velocidad pueden ser actualizados en tiempo real en una base continua por un número de usuarios ilimitado.

Como es mostrado en la Fig. 4, el sistema GPS es denotado generalmente por numeración de referencia 140. Un conjunto de satélites 120 están en órbita alrededor de la tierra 124. La órbita de cada satélite 120 no es necesariamente sincronizada con las órbitas de otros satélites 120 y, de hecho, es probablemente asincrónico. Un receptor GPS 140 se muestra recibiendo las señales del espectro de propagación del satélite GPS 160 desde varios satélites 120.

Las señales del espectro de propagación 160, continuamente transmitidas desde cada satélite 120, utilizan una frecuencia estándar altamente exacta realizado con un reloj atómico extremadamente exacto. Cada satélite 120, como parte de su señal de transmisión de datos 160, transmite una corriente de datos indicativa para ese satélite en particular 120. Es apreciado por aquellos expertos en el arte pertinente que el dispositivo receptor GPS 140 generalmente adquiere señales de un espectro de propagación de satélite GPS 160 de al menos tres satélites 120 para el dispositivo receptor GPS 140 para calcular su posición de dos dimensiones por triangulación. La adquisición de una señal adicional, resultante en señales 160 desde un total de cuatro satélites 120, permite al dispositivo receptor GPS 140 calcular su posición de tres dimensiones de una manera conocida.

La fig. 5 es una representación ilustrativa de componentes electrónicos de un dispositivo de navegación 200 de acuerdo a una realización preferida de la presente invención, en un formato de componente de bloque. Cabe señalar que el diagrama de bloque del dispositivo de navegación 200 no es inclusive de todos los componentes del dispositivo de navegación, pero es solo representativo de muchos componentes de ejemplo.

El dispositivo de navegación 200 es ubicado dentro de una tapa (no mostrada). La tapa incluye un procesador 210 conectado a un dispositivo de entrada 220 y una pantalla 240. El dispositivo de entrada 220 puede incluir un dispositivo de teclado, un dispositivo de entrada de voz, un panel táctil y/o cualquier otro dispositivo de entrada conocido utilizado para ingresar información; y la pantalla 240 puede incluir cualquier tipo de pantalla tal como una pantalla LCD, por ejemplo. En un arreglo preferido en particular el dispositivo de entrada 220 y la pantalla 240 están integrados dentro de una entrada integrada y un dispositivo de visualización, incluyendo entradas en un teclado táctil y una pantalla táctil así el usuario necesita solamente tocar una parte de la pantalla 240 para seleccionar uno de una pluralidad de opciones de visualización o para activar uno de una pluralidad de botones virtuales.

El dispositivo de navegación puede incluir un dispositivo de salida 260, por ejemplo un dispositivo de salida audible (por ejemplo un altavoz). Como el dispositivo de salida 260 puede producir información audible para un usuario de un dispositivo de navegación 200, debería ser igualmente entendido que ese dispositivo de entrada 240 puede incluir un micrófono y también un software para recibir comandos de entrada de voz.

En el dispositivo de navegación 200, un procesador 210 está operativamente conectado a y ajustado para recibir información de entrada de un dispositivo de entrada 220 a través de una conexión 225, y operativamente conectado a al menos una pantalla 240 y un dispositivo de salida 260, por medio de conexiones de salida 245, para la misma salida de información. Además, el procesador 210 es operativamente conectado al almacenamiento 230 (el cual puede comprender uno o más chips de RAM y/o almacenamiento de datos mecánico tal como un disco duro o unidad de estado sólido) por medio de la conexión 235 y está además adaptado para recibir/enviar información desde/hacia entrada/salida puertos (I/O) 270 por medio de la conexión 275, donde el puerto I/O 270 es conectable a un dispositivo I/O 280 externo al dispositivo de navegación 200. El dispositivo I/O externo 280 puede incluir, pero no es limitado un dispositivo de escucha externo tal como un auricular por ejemplo. La conexión al dispositivo I/O 280 puede además ser una conexión cableada o inalámbrica a cualquier otro dispositivo externo tal como una unidad de estéreo de automóvil para operación de manos libres y/o para operación activada por voz por ejemplo, para conexión a un auricular o audífono, y/o para conexión a un teléfono móvil por ejemplo, donde la conexión al teléfono móvil puede ser usada para establecer una conexión de datos entre el dispositivo de navegación 200 y de internet o cualquier otra red por ejemplo, y/o para establecer una conexión a un servidor por medio de internet o alguna otra red por ejemplo. En un arreglo preferido en particular el puerto I/O puede comprender un puerto USB (bus serie universal) para habilitar el dispositivo a ser acoplado a un dispositivo informático externo (tal como una computadora de mesa) para así mismo intercambiar datos.

La Fig. 5 además ilustra una conexión operativa entre el procesador 210 y una antena receptora 250 a través de una conexión 255, donde la antena receptora 250 puede ser una antena receptora GPS por ejemplo. Se entenderá que la antena y el receptor designados por el numeral de referencia 250 son combinados esquemáticamente para ilustración, pero que la antena y el receptor pueden ser componentes ubicados separadamente, y que la antena puede ser una antena de parche GPS o una antena helicoidal por ejemplo.

Además, será entendido por aquellos con conocimientos comunes en el arte que los componentes electrónicos mostrados en la Fig. 5 son accionados por fuentes de potencia (no mostradas) de una forma convencional. Como será entendido por aquellos con conocimientos comunes en el arte, las diferentes configuraciones de los componentes mostrados en la fig. 5 son considerados a estar dentro del alcance de la presente aplicación. Por ejemplo, los componentes mostrados en la Fig. 5 pueden estar en comunicación el uno al otro a través de conexiones alámbricas y/o inalámbricas y similares. Así, el alcance del dispositivo de navegación 200 de la presente aplicación incluye un dispositivo de navegación portátil o de mano 200.

Además, el dispositivo de navegación portátil o de mano 200 de la Fig. 5 puede ser conectado o "acoplado" de una forma conocida a un vehículo tal como una bicicleta, una motocicleta, un coche o un barco por ejemplo. Tal dispositivo de navegación 200 es entonces extraíble de la ubicación de acoplamiento para uso de navegación portátil o de
mano.

Refiriéndose ahora a la Fig. 6, el dispositivo de navegación 200 puede establecer una conexión "móvil" o de red de telecomunicaciones con un servidor 302 por medio de un dispositivo móvil (no mostrado) (tal como un teléfono móvil, PDA, y/o cualquier dispositivo con tecnología de teléfono móvil) o cualquier otro medio para establecer una conexión digital (tal como una conexión digital por medio de la tecnología Bluetooth conocida por ejemplo). A partir de entonces, a través de su proveedor de servicios de red, el dispositivo móvil puede establecer una conexión de red (a través de internet por ejemplo) con un servidor 302. Como tal, una conexión de red "móvil" se establece entre el dispositivo de navegación 200 (la cual puede ser, y la mayoría de veces es móvil ya que viaja solo y/o en un vehículo) y el servidor 302 para proporcionar un "tiempo-real" o al menos una entrada muy "actualizada" de información.

El establecimiento de la conexión de red entre el dispositivo móvil (por medio del proveedor de servicios) y otro dispositivo tal como el servidor 302, utilizando internet (tal como la World Wide Web) por ejemplo, puede hacerse de una forma conocida. Este puede incluir el uso de un protocolo de capas TCP/IP por ejemplo. El dispositivo móvil puede utilizar cualquier número de comunicaciones estándar tales como CDMA, GSM, WAN, etc.

Como tal, una conexión de internet puede ser utilizada la cual es lograda por medio de una conexión de datos, por medio de un teléfono móvil o de una tecnología de teléfono móvil dentro del dispositivo de navegación 200, por ejemplo. Para esta conexión, se establece una conexión de internet entre el servidor 302 y el dispositivo de navegación 200. Esto puede hacerse, por ejemplo, a través de un teléfono móvil u otro dispositivo móvil y una conexión GPRS (Servicio General de Paquete de radio) (la conexión GPRS es una conexión de datos de alta velocidad para dispositivos móviles proporcionada por operadores de telecomunicaciones; el GPRS es un método para conectarse a inter-
net).

El dispositivo de navegación 200 puede además completar una conexión de datos con el dispositivo móvil, y eventualmente con internet y el servidor 302, por medio de la tecnología existente Bluetooth por ejemplo, de una forma conocida, donde el protocolo de datos puede utilizar cualquier número de estándares, tal como el GSRM, el Protocolo de Datos estándar para el GSM estándar, por ejemplo.

El dispositivo de navegación 200 puede incluir su propia tecnología de teléfono móvil dentro del dispositivo de navegación 200 en sí mismo (incluyendo una antena por ejemplo, u opcionalmente utilizando la antena interna del dispositivo de navegación 200). La tecnología del teléfono móvil dentro del dispositivo de navegación 200 puede incluir componentes internos como se especificó más arriba, y/o puede incluir una tarjeta insertable (por ejemplo un Módulo de identidad del Suscriptor o tarjeta SIM), completa con la tecnología del teléfono móvil necesaria y/o una antena por ejemplo. Como tal, la tecnología de teléfono móvil dentro del dispositivo de navegación 200 puede similarmente establecer una conexión de red entre el dispositivo de navegación 200 y el servidor 302, por medio de internet por ejemplo, de una forma similar a aquella de cualquier dispositivo móvil.

Para las características de teléfono GPRS, un dispositivo de navegación habilitado con Bluetooth puede ser usado para trabajar correctamente con el espectro de modelos de teléfonos móviles en constante cambio, fabricantes, etc., características específicas de modelo/fabricante pueden ser almacenadas en el dispositivo de navegación 200 por ejemplo. Los datos almacenados para esta información pueden ser actualizados.

En la Fig. 6 el dispositivo de navegación 200 es descrito que está en comunicación con el servidor 302 por medio de un canal de comunicaciones genérico 318 que puede ser implementado por cualquier número de diferentes arreglos. El servidor 302 y el dispositivo de navegación 200 pueden comunicarse cuando la conexión a través del canal de comunicaciones 318 se establece entre el servidor 302 y el dispositivo de navegación 200 (señalando que tal conexión puede ser una conexión de datos por medio de un dispositivo móvil, una conexión directa por medio de un computador personal o por medio de internet, etc.).

El servidor 302 incluye, además de otros componentes los cuales pueden no ser ilustrados, un procesador 304 operativamente conectado a una memoria 306 y además operativamente conectado, por medio de una conexión alámbrica o inalámbrica 314, a un dispositivo de almacenamiento masivo 312. El procesador 304 es además operativamente conectado al transmisor 308 y receptor 310, para transmitir y enviar información desde y hacia un dispositivo de navegación 200 por medio de un canal de comunicaciones 318. Las señales enviadas y recibidas pueden incluir datos, comunicaciones, y/u otras señales propagadas. El transmisor 308 y el receptor 310 pueden ser seleccionados o designados de acuerdo al requerimiento de comunicaciones y la tecnología de comunicaciones utilizada en el diseño de la comunicación para el sistema de navegación 200. Además, cabe señalar que las funciones del transmisor 308 y el receptor 310 pueden ser combinadas dentro de un transceptor de señal.

El servidor 302 está además conectado a (o incluye) un dispositivo de almacenamiento masivo 312, señalando que el dispositivo de almacenamiento masivo 312 puede ser acoplado al servidor 302 por medio del enlace de comunicación 314. El dispositivo de almacenamiento masivo 312 contiene un depósito de datos de navegación e información del mapa, y puede nuevamente ser un dispositivo separado del servidor 302 o puede ser incorporado dentro del servidor 302.

El dispositivo de navegación 200 está adaptado para comunicarse con el servidor 302 a través del canal de comunicaciones 318, e incluye un procesador, almacenamiento, etc. Como se describió previamente con respecto a la Fig. 5, así como el transmisor 320 y el receptor 322 para enviar y recibir señales y/o datos a través del canal de comunicaciones 318, señalando que estos dispositivos pueden además ser usados para comunicarse con los otros dispositivos del servidor 302. Además, el transmisor 320 y el receptor 322 son seleccionados o designados de acuerdo con los requerimientos de comunicaciones y la tecnología de comunicaciones utilizada en el diseño de comunicaciones para el dispositivo de navegación 200 y las funciones del transmisor 320 y el receptor 322 pueden ser combinadas dentro de un transceptor simple.

El software almacenado en la memoria del servidor 306 proporciona instrucciones para el procesador 304 y permite al servidor 302 proporcionar servicios al dispositivo de navegación 200. Un servicio proporcionado por el servidor 302 involucra las solicitudes de procesamiento del dispositivo de navegación 200 y transmitir los datos de navegación desde el almacenamiento de datos masivo 312 al dispositivo de navegación 200. Otro servicio proporcionado por el servidor 302 incluye procesar los datos de navegación utilizando varios algoritmos para una aplicación deseada y enviar los resultados de estos cálculos al dispositivo de navegación 200.

El canal de comunicación 318 generalmente representa el medio de propagación de la trayectoria que conecta el dispositivo de navegación 200 y el servidor 302. Ambos, el servidor 302 y el dispositivo de navegación 200 incluyen un transmisor para transmitir los datos a través del canal de comunicación y un receptor para recibir los datos que han sido transmitidos a través del canal de comunicación.

El canal de comunicación 318 no está limitado a una tecnología de comunicación en particular. Adicionalmente, el canal de comunicación 318 no está limitado a una tecnología de comunicación sencilla; esto es, el canal 318 puede incluir varios enlaces de comunicación que utilizan una variedad de tecnología. Por ejemplo, el canal de comunicación 318 puede ser adaptado para proporcionar una trayectoria para comunicaciones eléctricas, ópticas, y/o electromagnéticas, etc. Como tal, el canal de comunicación 318 incluye, pero no está limitado a, una o una combinación de lo siguiente: circuitos eléctricos, conductores eléctricos como hilos o cables coaxiales, cables de fibra óptica, convertidores, ondas de radiofrecuencia (RF), la atmósfera, espacio vacío, etc. Además, el canal de comunicación 318 puede incluir dispositivos intermedios como enrutadores, repetidores, estabilizadores, transmisores, y receptores, por ejemplo.

En un arreglo ilustrativo, el canal de comunicación 318 incluye redes de teléfono y computador. Además, el canal de comunicación 318 puede ser capaz de acomodar una comunicación inalámbrica tal como una frecuencia de radio, una frecuencia de microondas, una comunicación por infrarrojos, etc. Adicionalmente, el canal de comunicación 318 puede acomodar comunicaciones por satélite.

Las señales de comunicación transmitidas a través del canal de comunicación 318 incluyen, pero no están limitadas a, las señales como puedan ser requeridas o decididas para una tecnología de comunicación dada. Por ejemplo, las señales pueden ser adaptadas a ser usadas en una tecnología de comunicación celular tal como Acceso de Múltiple División de tiempo (TDMA), Accedo de Múltiple División de Frecuencia (FDMA), Acceso de Múltiple División de Código (CDMA), Sistema Global para Comunicaciones Móviles (GSM), etc. Ambas señales digital y análoga pueden ser transmitidas a través del canal de comunicación 318. Estas señales pueden ser moduladas, encriptadas y/o señales comprimidas como puede ser deseable para la tecnología de comunicación.

El servidor 302 incluye un servidor remoto accesible por el dispositivo de navegación 200 a través de un canal inalámbrico. El servidor 302 puede incluir un servidor de red ubicado en una red de área local (LAN), una red de área ancha (WAN), una red virtual privada (VPN), etc.

El servidor 302 puede incluir un computador personal tal como un computador de mesa o portátil, y el canal de comunicación 318 puede ser un cable conectado entre el computador personal y el dispositivo de navegación 200. Alternativamente, un computador personal puede ser conectado entre el dispositivo de navegación 200 y el servidor 302 para establecer una conexión de internet entre el servidor 302 y el dispositivo de navegación 200. Alternativamente, un teléfono móvil u otro dispositivo de mano pueden establecer una conexión inalámbrica a internet, para conectar el dispositivo de navegación 200 al servidor 302 por medio de internet.

El dispositivo de navegación 200 podría ir provisto de información desde el servidor 302 a través de descargas de información que pueden ser periódicamente actualizadas automáticamente o a un usuario conectando un dispositivo de navegación 200 al servidor 302 y/o puede ser más dinámica a una conexión más constante o frecuente que se realice entre el servidor 302 y el dispositivo de navegación 200 por medio de una conexión móvil inalámbrica y una conexión TCP/IP por ejemplo. Para varios cálculos dinámicos, el procesador 302 en el servidor 302 puede ser usado para manejar el volumen de las necesidades del procesamiento, sin embargo, el procesador 210 del dispositivo de navegación 200 puede también manejar muchos procesamientos y cálculos, a menudo independientes de una conexión a un servidor 302.

Como se indicó arriba en la Fig. 5, un dispositivo de navegación 200 incluye un procesador 210, un dispositivo de entrada 220, y una pantalla 240. El dispositivo de entrada 220, y la pantalla 240 están integrados en de una entrada integrada y un dispositivo de visualización para habilitar ambas entradas de información (por medio de entrada directa, selección de menú, etc.) y mostrar la información a través de una pantalla táctil, por ejemplo. Tal como una pantalla puede ser una entrada táctil LCD, por ejemplo, como es bien sabido por aquellos con conocimientos ordinarios en el arte. Además, el dispositivo de navegación 200 puede también incluir cualquier dispositivo de entrada adicional 220 y/o cualquier dispositivo de salida adicional 241, tal como dispositivos de entrada/salida por ejemplo.

Las Fig. 7A y 7B son vistas en perspectiva de un dispositivo de navegación 200. Como se mostró en la Fig. 7A, el dispositivo de navegación 200 puede ser una unidad que incluye una entrada integrada y un dispositivo de visualización 290 (un panel de pantalla táctil por ejemplo) y los otros componentes de la Fig. 5 (incluyendo pero no limitado a un receptor interno GPS 250, un microprocesador 210, un suministro de energía, sistemas de almacenamiento 230,
etc.)

Como se mostró en la Fig. 7B, cuando se consagró como un dispositivo de navegación de un vehículo, el dispositivo de navegación 200 puede ubicarse en un brazo 292, el cual por sí mismo puede ser asegurado a un tablero de instrumentos/ventana/etc. de un vehículo utilizando una ventosa 294. Este brazo 292 es un ejemplo de una estación de acomplamiento a la que se puede acoplar el dispositivo de navegación 200. Otro ejemplo podría ser una abrazadera conectable al manillar de una bicicleta.

Como se mostró en la Fig. 7B, el dispositivo de navegación 200 puede ser acoplado o de lo contrario conectado a un brazo 292 de la estación de acomplamiento por medio de la conexión instantánea del dispositivo de navegación 292 al brazo 292 por ejemplo. El dispositivo de navegación 200 puede ser giratorio en el brazo 292, como es mostrado por la flecha de la Fig. 4B. Para liberar la conexión entre el dispositivo de navegación 200 y la estación de acoplamiento, podría ser presionado un botón en el dispositivo de navegación 200, por ejemplo. Otros arreglos igualmente adecuados para acoplar y desacoplar el dispositivo de navegación a una estación de acoplamiento son bien conocidos por personas con conocimientos ordinarios en el arte.

Refiriéndonos ahora a la Fig. 8 de los dibujos que se acompañan, el procesador 210 y el almacenamiento 230 cooperan para establecer un BIOS (Sistema Básico de Entrada/Salida) 450 que funciona como una interfaz entre los componentes del hardware funcional 460 del dispositivo de navegación 200 y el software ejecutado por el dispositivo. El procesador entonces carga del almacenamiento 210 un sistema operativo 470 que proporciona un ambiente en el cual puede ejecutar el software de aplicación 480 (implementando algunas o todas las funcionalidades anteriormente descritas). De acuerdo con la realización preferida de la presente invención, parte de esta funcionalidad comprende un módulo de procesamiento de datos 490, la función que ahora se describirá en detalle.

En esta realización el dispositivo de navegación está configurado para generar -de una forma conocida- un mapa de navegación para mostrar que es representativo, en un modo de uso, del entorno local en el que se encuentra actualmente el dispositivo de navegación. Si el dispositivo de navegación está siendo usado para guiar a un excursionista, entonces el mapa de navegación mostrado puede describir parte de una ruta calculada entre un punto de inicio y un destino. Alternativamente, el dispositivo puede solamente describir el entorno local en el cual el dispositivo está actualmente ubicado (por ejemplo sin que una ruta haya sido generada). En otro modo de uso, el dispositivo puede ser empleado para permitir a un usuario hojear mapas y en este modo no puede haber ninguna ubicación actual del dispositivo, y a su vez el usuario puede ser solicitado a ingresar una ubicación de inicio para la visualización del mapa o la visualización del mapa puede comenzar automáticamente desde una ubicación predefinida - tal como la ubicación de la casa del usuario por ejemplo.

Como se mencionó anteriormente, las enseñanzas de la presente invención habilitan al dispositivo de navegación para reproducir dinámicamente un mapa de navegación que incluya información topográfica sin demorar el procesamiento indebidamente, pérdida de la calidad de la imagen sin gastar excesivamente la memoria.

Refiriéndose ahora a las Figs. 9B a 9F hay descritas varias etapas del método de procesamiento de datos de acuerdo a una realización preferida de la presente invención. En este caso se asume que las medidas de datos de altura son almacenadas en parches de datos de un grado por un grado cuadrado 3, con cada parche incluyendo un conjunto de medidas de datos. Como se mostró en la Fig. 9A, el campo de vista 5 (parte de la cual se muestra) comprende un conjunto de píxeles 7 uniformemente organizados en filas y columnas. También se muestra en la Fig. 9A un "borde" ilustrativo, del que se describirá la importancia más adelante.

Como es bien conocido en el arte, para computar información topográfica -por ejemplo un porcentaje de sombreado- para cada píxel 7 del campo de vista 5 es necesario recuperar los valores de medidas de altura que rodean la proyección de ese píxel en el mapa 1. En la mayoría de casos una memoria intermedia de datos consistente de dos filas de datos será suficiente, y para este ejemplo en particular una memoria intermedia de datos adecuada será preferiblemente menor a 5 K bytes en tamaño. Es probable que no se necesitará toda la memoria intermedia como no es necesario leer una fila de datos completos del almacenamiento, como solo un segmento de datos es muy probable que será necesario. Una memoria intermedia de esta magnitud es preferida, sin embargo, con el fin de que sea proporcionada suficiente memoria para casos extremos que pueden ser encontrados potencialmente. Como ahora se describirá, el procesamiento de los datos se realiza de tal forma que la recarga de los datos es reducida, y preferiblemente evitada completa-
mente.

En términos generales, el método funciona para agrupar píxeles 7 del campo de vista 5 por un parche de datos, y entonces procesarlos. Una vez que se han identificado las coordenadas de la cuadricula en el mapa 1 de los valores de altura correspondientes a cada píxel 7, los píxeles 7 a continuación pueden entonces ser organizados por filas antes de ser procesados fila por fila. Como ahora será explicado, implementando tales arreglos es posible evitar líneas de carga de cualquiera de parche varias veces.

Un elemento importante de este método es el "borde". En términos generales el borde de una realización comprende, al final de cada iteración del proceso (por ejemplo cuando todos los píxeles de un parche de datos dado han sido procesados y una imagen de ese parche ha sido reproducida), el índice de columna (por ejemplo el número de columna) de los píxeles procesados para cada fila de un campo de vista. El borde será cero en el inicio del proceso de reproducción para todas las filas del campo de vista e igual para la última columna de la fila (nuevamente para todas las filas) cuando el proceso de reproducción haya finalizado. Como será apreciado, esta es una forma efectiva para contar los píxeles 7 del campo de vista 5 que han sido procesados. La Fig. 9A incluye una representación esquemática de un borde ilustrativo 9, y para evitar confusiones cabe señalar que el borde 9 mostrado en la Fig. 9A es simplemente ilustrativo y no es representativo de los bordes descritos en las Figs. 9B a 9F.

Refiriéndonos ahora a las Figs. 9A y 9B, el procesador invoca el módulo de procesamiento de datos 490 y determina que la proyección del primer píxel en la fila 0 (índice de píxel (0,0)) cae dentro del parche de datos 22 en el mapa digital 1. El módulo de procesamiento de datos entonces escanea (en esta realización) de izquierda a derecha desde el primer píxel en la fila 0 (índice de píxel: (0,0)) hasta que se alcanza el último píxel cayendo dentro del parche de datos 22 (es decir el índice de píxel: (0,2) en la Fig. 9A). El módulo de procesamiento de datos ajusta el borde de la fila 0 (IndicedeBorde(0)) a ser igual a la columna del ultimo píxel cayendo dentro del parche de datos 22 (en este ejemplo el índice de píxel: (0,2)), y entonces procede a escanear la siguiente fila (fila 1) de izquierda a derecha hasta que se alcanza el ultimo píxel cayendo dentro del parche de datos 22 (es decir índice de píxel: (1,2). El módulo de procesamiento de datos a continuación ajusta el borde para la fila 1 (IndicedeBorde(1)) a ser igual al índice de píxel de columna (1,2).

Este proceso se repite hasta que se alcanza la fila donde el primer píxel escaneado para esa fila ya no cae dentro del parche de datos 22, tras lo cual el módulo de procesamiento de datos determina que todos los píxeles cayendo dentro del parche 22 han sido procesados. En este punto, el módulo de procesamiento de datos tendrá que determinar el borde para el bloque 22 como sigue:

IndicedeBorde(0)=(2)

IndicedeBorde(1)=(2)

IndicedeBorde(2)=(3)

IndicedeBorde(3)=(4)

IndicedeBorde(4)=(3)

IndicedeBorde(5)=(1)

IndicedeBorde(6)=(0)

IndicedeBorde(7)=(0)

Una vez que el borde para el parche de datos 22 ha sido determinado, el módulo de procesamiento de datos agrega todos los píxeles pertenecientes al parche de datos 22 (por ejemplo todos los píxeles en cada fila entre la posición de inicio para esa fila y el IndicedeBorde determinado) a una lista, y luego implementa algoritmos conocidos para computar las coordenadas de la cuadrícula de los puntos de datos de altura (no mostrados) cercanos a cada uno de esos píxeles. El módulo de procesamiento de datos luego ordena la lista por el valor de la fila de las coordenadas de la cuadrícula y procesa los píxeles fila por fila utilizando algoritmos conocidos para aplicar información topográfica (tal como formaciones o isóclinas, por ejemplo) a los píxeles cuya proyección cae dentro del borde del parche de datos 22 y para reproducir el parche de datos a visualizar. La información topográfica a aplicarse se determinada en base a la altura de cada uno de esos píxeles calculado de los puntos de datos de altura correspondientes más cercanos. En un arreglo preferido este último paso es agrupado en varios pasos para evitar procesar una larga lista de datos, pero para simplicidad consideraremos que el módulo de procesamiento de datos procesa todos los datos relativos al parche de datos 22 a la vez.

Este proceso se repite para todos los parches, pero debe tenerse cuidado para asegurarse que los parches son procesados en el orden correcto. Si el módulo de procesamiento de datos 490 fuera simplemente un procesamiento continuo en la primera fila donde el IndicedeBorde indica que no se encontraron píxeles pertenecientes al parche de datos 22, entonces los píxeles por encima de la línea de puntos 8 en la Fig. 9B no serían procesados. En el contexto de la Fig. 9A, si el procesamiento fuera continuar en la fila 6, entonces los píxeles (5,2), (5,3), (5,4) y (5) no podrían ser procesados.

Como esto es indeseable, el módulo de procesamiento de datos es configurado para reanudar el procesamiento en una fila cero empezando con el píxel adyacente al IndicedeBorde previamente determinado para esa fila, en otras palabras en el índice de píxel: (fila n,(Indicedeborde(n) + 1)). Para el ejemplo ilustrado en la fig. 9A, el procesamiento de la fila cero se reanuda en el índice de píxel: (0,3) y continua hasta que el borde entre los parche de datos 23 y 24 (Fig. 9B) es alcanzado punto en el cual el IndicedeBorde (0) es ajustado al número de columna del último píxel correspondiente cuya proyección cae dentro del parche de datos 23. El Parche de datos 32 es procesado de una forma similar.

Una vez los parches 23 y 32 han sido escaneados, será como se muestra en la Fig. 9C y todos los píxeles no procesados previamente (por ejemplo todos los píxeles entre el borde 9 y los píxeles previamente procesados (designados por la región eclosionada 10) pueden ser ahora procesados de una forma previamente descrita.

Este proceso luego se repite para los parches de datos 24, 33 y 42, después de lo cual el borde será como el descrito en la Fig. 9D, y para los parches 34, 43 y 52 (aunque en este ejemplo solo habrá unos pocos píxeles para el parche de datos 52 que necesitan ser procesados), después de lo cual el borde será como se muestra en la Fig. 9E.

Cuando el procesamiento se mueve para considerar los parches 44 y 53, el IndicedeBorde para la fila cero ya ha alcanzado el número máximo de columna para este campo de vista 5, y como tal el procesamiento se reanuda en la primera fila donde el IndicedeBorde no es igual al número máximo de columna para este campo de vista. Una vez que los parches de datos 44 y 53 han sido procesados el borde tendrá que ser determinado como se describe esquemáticamente en la fig. 9F.

Cuando los parches de datos 44 y 52 han sido procesados, el procesamiento se reanuda en la primera fila del último parche de datos restantes -parche de datos 54- y cuando este parche ha sido procesado, todos los píxeles dentro del campo de vista 5 han sido procesados por el módulo de procesamiento de datos.

Una vez que el proceso descrito arriba ha sido completado, el procesador del dispositivo de navegación controla la pantalla para mostrar las imágenes reproducidas para cada parche de datos del campo de vista.

Como será evidente de lo que precede, de conformidad con el método descrito ha sido posible procesar todos los píxeles del campo de vista sin tener que volver a visitar (y por lo tanto recargar los datos para) cualquiera de los parches de datos previamente procesados. La ventaja de implementar el procesamiento de píxeles de esta manera es que evita la recarga de datos proporcionando una mejora en el rendimiento de tal magnitud que la interpretación dinámica de una imagen basada en toda la información de altura disponible para el campo de vista (en vez de simplemente un subconjunto de esa información) ahora es factible. Este es el caso particular cuando uno considera que los datos de altura probablemente tendrán un encabezado. Evitando regresar a cualquier parche dado es posible evitar tener que volver a cargar estos encabezados.

Refiriéndose ahora a la Fig. 10 los pasos del método que preceden se representan en un formato de diagrama de flujo más convencional, y ahora se describen en detalle.

Siguiendo la iniciación del método de procesamiento de datos, el módulo de procesamiento de datos 490 es cargado en la memoria por el procesador y ejecutado en el paso 500. En el paso 502, se definen las coordenadas (x,y) de un píxel de inicio del campo de vista (en este caso el píxel de inicio elegido se encuentra en (0,0) - es decir, el píxel en la primera columna (x) de la primera fila (y).

En el paso 504 se encuentra el píxel de inicio y se identifica el correspondiente parche de datos que incluye la proyección de ese píxel que es identificado. En el paso 506 está seleccionado el píxel en la siguiente columna adyacente, y se realiza un chequeo en el paso 508 para ver si este píxel está todavía dentro del campo de vista. Si el píxel no está en el campo de vista, el procesamiento continúa en el paso 514 descrito a continuación. Si el píxel está dentro del campo de vista, entonces el parche de datos en el que se encuentra la proyección de ese píxel está determinada en el paso 510, y se realiza un chequeo en el paso 512 para ver si se ha alcanzado un borde mediante la determinación si ha cambiado la identidad del parche de datos en la que se proyecta el píxel. Si un borde no ha sido alcanzado, el procesamiento vuelve al paso 506 ya mencionado.

Si se ha alcanzado un borde, entonces se entablece el IndicedeBorde para esa fila (y) en la columna del píxel anterior en el parche de datos en el paso 514, y el procesamiento avanza en el paso 516 a la siguiente fila (y+1) y el píxel adyacente en el IndicedeBorde para esa fila. En el paso 518 el parche de datos que incluye la proyección del píxel seleccionado en el paso 516, y se realiza un chequeo en el paso 520 si el parche de datos identificado en el paso 518 es el mismo parche de datos identificado en el paso 510. Si los parches son los mismos, el procesamiento para ese parche no se ha completado y el procesamiento vuelve al paso 506.

Si el parche identificado en el paso 518 es diferente al parche identificado en el paso 510, entonces el procesamiento de las filas para ese parche de datos se considera que se ha completado y en el paso 522 todos los píxeles que se proyectan dentro del borde (definido por el IndicedeBorde(y) para las filas de ese parche) se procesan en la forma antes mencionada, a saber las coordenadas de cuadrícula de los correspondientes puntos de datos de altura más cercanos a cada uno de esos píxeles son computados, se determinada la información topográfica apropiada para cada píxel y se procesa el parche de datos para la visualización.

En el paso 524, se realiza un chequeo para determinar si todos los píxeles en el campo de vista han sido procesados para determinar si el IndicedeBorde(y) para cada fila y es igual al valor máximo. Si todas las filas y píxeles han sido procesados, a continuación se muestra la imagen reproducida en el paso 526 para mostrar las imágenes individuales reproducidas de cada parche de datos, tras lo cual el procesamiento termina en el paso 528.

Si el IndicedeBorde(y) no es igual al máximo de todas las filas, entonces y se establece en el paso 530 a la primera fila en la que el IndicedeBorde(y) no es igual al valor máximo para este campo de vista, y x se establece en el paso 532 al píxel adyacente del píxel identificado por el IndicedeBorde para esa fila y, tras lo cual el proceso vuelve al paso 504 antes mencionado.

En términos muy generales el proceso implementando las enseñanzas de la presente invención puede ser definido como los pasos de ubicación del borde de un primer parche de datos en el cual se encuentra la proyección de un primer píxel, el procesamiento de píxeles para ese parche, y repetidamente: (a) identificar el borde de cada uno de los parches de datos sin procesar que comunica con un parche de datos previamente procesados y (b) procesar los píxeles de ese parche, hasta que se hayan procesado todos los parches de datos del campo de vista.

Será evidente para los precedentes que las realizaciones particulares de la invención que se describen aquí proporcionan un método mediante el cual el dato de altura actual (y no un subconjunto simplificado de ese dato) es utilizado para reproducir una imagen que incluye información topográfica, y en virtud de este arreglo se protege la exactitud y la consistencia del proceso de reproducción de altura. Una ventaja en particular de la realización preferida es que los gastos generales ubicados en un dispositivo de navegación por el método son suficientemente bajos como para que el dispositivo pueda proporcionar una reproducción dinámica de las imágenes - en particular las imágenes que incluyen información topográfica.

Por ejemplo, mientras que las realizaciones descritas en la descripción detallada precedente se refieren al GPS, debe señalarse que el dispositivo de navegación puede utilizar cualquier tipo de tecnología de detección de posición como una alternativa a (o de hecho además de) GPS. Por ejemplo el dispositivo de navegación puede utilizarse empleando otros sistemas satelitales de navegación global como el sistema Europeo Galileo. Igualmente, no se limita a un satélite base pero podría fácilmente funcionar mediante balizas de terreno o cualquier otro tipo de sistema que permita al dispositivo determinar su ubicación geográfica.

En otra modificación será inmediatamente apreciado por personas expertas en la materia que sería eminentemente posible, sin apartarse del alcance de la presente invención, a: (i) implementar columna por columna el procesamiento de parches de datos (en lugar de procesar fila por fila esos parches), (ii) comenzar a procesar desde una ubicación de píxel diferente a (0,0), y/o (iii) utilizar el método de procesamiento de datos de la presente invención para el procesamiento de otros tipos de datos (tal como datos vectoriales por ejemplo).

También será entendido por personas con conocimientos comunes en el arte que mientras la realización preferida implementa cierta funcionalidad por medio se software, esa funcionalidad podría igualmente ser implementada en hardware (por ejemplo por medio de uno o más ASICs (circuito integrado específico de aplicación) o de hecho por una combinación de hardware y software. Como tal, el ámbito de aplicación de la presente invención no debe interpretarse como limitado solo a ser implementado en software.

Una persona experta entenderá también que mientras las enseñanzas de la presente invención tienen una utilidad particular en circunstancias donde el campo de vista ha sido rotado con respecto al mapa digital, el método divulgado puede también ser utilizado cuando el campo de vista está alineado con el mapa digital. Como consecuencia de ello, el alcance de la presente invención no debe interpretarse como limitado únicamente a circunstancias donde el campo de vista ha sido rotado con respecto al mapa.

Claims

1. Un método de procesamiento de datos de píxeles (7) de un campo de vista (5), en el que el campo de vista comprende una parte de un mapa digital (1) que se mostrará e incluye un conjunto de píxeles (7), el mapa digital (1) comprende un conjunto de parches de datos (3) que incluyen al menos un punto de datos, y el campo de vista (5) incluye un conjunto de parches de dichos de datos (3), el método es caracterizado por:

(i): identificar (504), para un dicho píxel (7), un parche de datos (3) en que dicho píxel se encuentra (7);

(ii): ubicar (506-512) un borde (9) de dicho parche de datos (3) que se encuentra dentro de dicho campo de vista (5);

(iii): procesar (522) todos los píxeles (7) de dicho campo de vista (5) que se encuentran dentro de dicho borde (9) para proporcionar un parche de datos procesados;

(iv): ubicar (504-512), para cada uno de los parches de datos sin procesar (3) dentro del campo de vista (5) que sean adyacentes al borde (9) de un parche de datos procesado, un borde (9) de un parche de datos sin procesar (3) que se encuentra dentro de dicho campo de vista (5);

(v): procesar (522), para cada uno de los parches de datos sin procesar (3) todos los píxeles sin procesar (7) que se encuentran dentro del borde de dicho parche de datos sin procesar (3) para así proporcionar un parche de datos procesados; y

(vi): repetir los pasos (iv) y (v) hasta que todos los parches de datos (3) dentro de dicho campo de vista hayan sido procesados (5).

\vskip1.000000\baselineskip

2. Un método de acuerdo con la Reivindicación 1, donde el paso (i) incluye proyectar dicho píxel (7) de dicho campo de vista (5) en los parches de datos (3) de dicho mapa digital (1), y determinar la identidad del parche de datos (3) en el que se encuentra dicha proyección.

3. Un método de acuerdo con las Reivindicaciones 1 o 2, en el que el paso (ii) incluye el paso de procesamiento de píxeles en las proximidades de los píixeles del paso (i) para determinar la ubicación de dicho borde (9).

4. Un método de acuerdo con la Reivindicación 3, en el que el procesamiento de dicho píxel comprende determinar la identidad del parche de datos en el que se encuentra una proyección de dicho píxel en dicho mapa digital.

5. Un método de acuerdo con la Reivindicación 4, en el que se determina un borde a pasar cuando los píxeles adyacentes se identifican como asociados con diferentes parches de datos.

6. Un método de acuerdo con la Reivindicación 5, donde el procesamiento de píxeles en las proximidades de dicho píxel comprende un proceso iterativo, comenzando por el píxel del paso (i), en el que los píxeles más distantes del píxel del paso (i) son procesados progresivamente hasta que dicho borde es ubicado.

7. Un método de acuerdo con la Reivindicación 6, donde dicho proceso iterativo está configurado para procesar píxeles

-: progresivamente más distante del píxel del paso (i) en una determinada fila o columna de dicho campo de vista, o

-: para procesar los píxeles de la fila o columna en la que dicho píxel del paso (i) se encuentra para ubicar dicho borde en esa fila o columna, y a continuación procesar progresivamente las filas o columnas de dicho campo de vista que están más distantes de la fila o columna en la cual dicho píxel del paso (i) se encuentra para ubicar el borde en cada una de las filas o columnas hasta que se han identificado todas las filas o columnas que incluyen píxeles asociados con los parches de datos con el que dicho píxel del paso (i) está asociado.

\vskip1.000000\baselineskip

8. Un método de acuerdo con la Reivindicación 7, en el que cada dicho píxel está asociado con un índice de píxel, parte del índice de píxel identifica la ubicación del píxel en una fila o columna de dicho campo de vista, y localiza dicho borde para cada dicha fila o columna, incluye establecer un IndicedeBorde variable para esa fila o columna que sea igual a dicha parte del índice del píxel para el último de dichos píxeles identificados en dicho proceso iterativo para asociarse con el parche de datos con que dicho píxel del paso (i) está asociado.

9. Un método de acuerdo con la Reivindicación 8, en el que el índice de píxel incluye una primera parte identificando la fila de dicho campo de vista en el que dicho píxel es ubicado, y una segunda parte identificando la columna de dicho campo de vista en la que se encuentra dicho píxel.

10. Un método de acuerdo con la reivindicación 9, en el que dicho proceso iterativo está configurado para procesar píxeles por lo menos uno de (A) fila por fila, y la variable IndicedeBorde para cada fila se establece en la segunda parte del índice de píxel para el último de dichos píxeles identificado en dicho proceso iterativo para asociarse con el parche de datos con que dicho píxel de paso (i) está asociado y (B)columna por columna, y la variable IndicedeBorde para cada columna se establece en la primera parte del índice de píxel para el último de dichos píxeles identificado en dicho proceso iterativo para asociarse con el parche de datos con que dicho píxel de paso (i) está asociado.

11. Un método de acuerdo con cualquier reivindicación precedente, en el que cada píxel de dicho campo de vista tiene un índice de píxel, y el paso (iv) comprende, para cada parche de datos sin procesar, el paso de determinar un primer píxel de ese parche que debe ser procesado para ser un píxel adyacente a un píxel de un parche de datos previamente procesado que tiene un índice de píxel igual a una variable IndicedeBorde variable y una fila o columna con la que dicha variable de IndicedeBorde se asocia, dicho paso (iv) opcionalmente incluye el paso de procesamiento de píxeles en las proximidades de dicho primer píxel para determinar la ubicación de dicho borde (9).

12. Un método de acuerdo con la Reivindicación 11, en el que dicho paso determinante incluye el paso de selección de un primer píxel de cada parche de datos sin procesar para ser un píxel en la primera fila o columna de dicho parche de datos procesado para el que la variable del IndicedeBorde no es igual a un valor máximo.

13. Un método de acuerdo con cualquier reivindicación precedente, en el que el paso (iii) o (iv) comprende el paso de identificación, para cada dicho píxel asociado con un parche de datos determinado, al menos un punto de datos de dicho parche de datos que es cercano a una proyección de dicho píxel en dicho mapa digital.

14. Un método de acuerdo con la reivindicación 13, en el que al menos un punto de datos comprende información pertinente a la elevación de una ubicación geográfica dentro de dicho mapa digital.

15. Un método de acuerdo con la Reivindicación 14, que comprende el paso de computar un valor para cada dicho píxel que depende del valor del mismo al menos en el punto de datos más cercano.

16. Un método de acuerdo con la Reivindicación 15, en el que cada uno de dicho parche de datos incluye un conjunto de puntos de datos, y dicho paso de computación comprende un valor para cada dicho píxel que depende de los valores de esos puntos de datos en las cercanías de cada de dicho píxel.

17. Un método de acuerdo con la Reivindicación 16, donde dicho paso de computación comprende computar un valor para cada dicho píxel que depende de los valores de estos puntos de datos rodeando inmediatamente cada dicho píxel.

18. Un método de acuerdo con cualquiera de las Reivindicaciones 18 a 17, en el que dicho valor transmite información topográfica para cada dicho píxel, dicha información topográfica incluye opcionalmente un coeficiente de sombreado.

19. Un método de acuerdo con cualquiera de las Reivindicaciones 13 a 18, que comprende el paso de reproducir una imagen para ese parche de datos con el que dichos píxeles están asociados, y a continuación generar una imagen final para su visualización, dicha imagen final comprende un montaje de imágenes reproducidas para cada parche de datos dichos organizado de acuerdo con la ubicación correspondiente de dichos parches de datos en dicho campo de vista.

20. Un método de acuerdo con cualquier reivindicación precedente, en el que dicho campo de vista incluye al menos una parte de una determinada ruta entre la posición geográfica de inicio y las posiciones de destino.

21. Un método de acuerdo con cualquier reivindicación precedente, en el que dicho campo de vista incluye una posición actual de un dispositivo de navegación, dicho campo de vista opcionalmente está centrado en dicha posición actual.

22. Un dispositivo de procesamiento de datos adaptado para llevar a cabo los métodos de cualquiera de las reivindicaciones precedentes, e incluyendo al menos un procesador y un almacenamiento que contenga al menos un mapa digital.

23. Un dispositivo de acuerdo con la reivindicación 22 realizado como un dispositivo de navegación (200), dicho dispositivo además comprende: una pantalla (240) controlable por dicho procesador (210); una antena (250); y un receptor (250) para recibir las señales de los datos por medio de dicha antena, en el que dicho procesador (210) está configurado para determinar dichas señales de datos recibidas desde una ubicación actual de dicho dispositivo de navegación (200), para generar una imagen final del campo de vista que incluye dicha ubicación actual y las imágenes reproducidas para dichos parches de datos, y para controlar dicha imagen final de pantalla a pantalla, y dicho procesador (210) está configurado para repetir periódicamente la determinación de dicha posición actual y para invocar dicho módulo de procesamiento de datos para la generación de una nueva imagen final si una determinada ubicación para dicho dispositivo de navegación (200) pudiera diferir de dicha posición actual previamente
definida.

24. Un software de computador que comprende el software de uno o más módulos operables, cuando se ejecuta en un ambiente de ejecución, para crear un procesador (210) para:

(i): identificar (504), para un píxel (7) de un campo de vista que comprende una parte de un mapa digital que se va a mostrar, un parche de datos (3) en el cual dicho píxel (7) se encuentra, en el que el mapa digital comprende un conjunto de parches de datos que cada uno incluyen al menos un punto de datos y dicho campo de vista comprende un conjunto de dicho píxel;

(ii): ubicar un borde (9) de dicho parche de datos (3) que se encuentra dentro de dicho campo de vista (5);

(iii): procesar todos los píxeles (7) de dicho campo de vista (5) que se encuentran dentro de dicho borde (9) para proporcionar un parche de datos procesado;

(iv): ubicar, para cada uno de los parches de datos sin procesar (3) dentro del campo de vista (5) que son adyacentes (9) a un borde de un parche de datos procesados, un borde (9) de un parche de datos sin procesar (3) que se encuentra dentro de dicho campo de vista (5);

(v): procesar, para cada parche de datos sin procesar (3), todos los píxeles sin procesar (7) que se encuentran dentro del borde de dicho parche de datos sin procesar (3) para así proporcionar un parche de datos procesados; y

(vi): repetir los pasos (iv) y (v) hasta que todos los parches de datos (3) dentro de dicho campo de vista han sido procesados (5).