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)

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...

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:

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

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: