Área de agregación en el mapa de generalización de la programación entera mixta

Área de agregación en el mapa de generalización de la programación entera mixta

Jan-Henrik Haunert y Alexander Wolff

Instituto de Cartografía y Geo informática, Universidad de Hannover, Hannover, Alemania; Departamento de Matemáticas y Ciencias de la Computación de la Universidad Técnica de Eindhoven, Eindhoven, Países Bajos.

(Recibida el 9 de enero de 2009; versión final recibida el 10 de septiembre de 2009).

Las bases de datos topográficas normalmente contienen áreas de diferentes clases de cubierta terrestre, comúnmente definiendo una partición planar, es decir, las lagunas y las superposiciones no están permitidos. Al reducir la escala de esa base de datos, algunas zonas se vuelven demasiado pequeñas para la representación y necesitan ser agregadas. Esto involuntariamente pero inevitablemente provoca cambios en las clases. En este artículo presentamos un método de optimización para el problema de agregación. Este método pretende minimizar los cambios de clases y crear formas compactas, sujetas a restricciones estrictas asegurando agregados de tamaño suficiente para la escala de destino. Para cuantificar los cambios de clase aplicamos una medida de distancia semántica. Damos una formulación de un problema teórico gráfico demostrando que el problema es NP-hard lo que significa que no podemos esperar encontrar un algoritmo eficaz. En lugar de ello, presentamos una solución de programación entera-mixta, que puede ser utilizada de forma óptima para resolver pequeños casos con los actuales softwares de optimización. A fin de procesar grandes conjuntos de datos, introducimos heurísticas especiales que permiten que ciertas variables se eliminen y el caso del problema se descomponga en casos independientes. Hemos probado nuestro método para un conjunto de datos topográficos de la base de datos oficial alemana ATKIS  con escala 1:50.000 de entrada y salida a escala 1:250.000. Para pequeños casos, comparamos los resultados de este enfoque con soluciones óptimas que fueron obtenidas sin la heurística. Comparamos los resultados para las grandes instancias con los actuales de un algoritmo iterativo y un enfoque de optimización alternativa por simulación. Estas pruebas nos permiten concluir que con la heurística definida, la optimización de nuestro método produce resultados de alta calidad para grandes conjuntos de datos en un tiempo corto.

1. Introducción

En los últimos años, los investigadores han realizado considerables progresos en la cuantificación de la calidad del mapa de generalización (Bard 2004, Cheng y Li 2006, Frank y Ester, 2006). Generalmente, Se han propuesto medidas para evaluar el resultado de los procedimientos de generalización. Por ejemplo, Cheng y Li (2006) discuten las medidas de calidad para los mapas de polígono, es decir, particiones del plano en regiones poligonales de diferentes clases. Los autores realizaron experimentos con diferentes configuraciones de un método simple de generalización: Las áreas que son demasiado pequeñas para la escala de destino se fusionan con las áreas próximas que potencialmente tienen diferentes clases. Se compararon los resultados con respecto a la zona que cambia su clase en la generalización, que ellos definen como medida global de "coherencia semántica'. En este articulo definiremos una medida de calidad similar basado en los cambios de clase. Nosotros, sin embargo, no sólo aplicaremos esta medida para evaluar la generalización de los algoritmos, sino también presentar un método de agregación que produzca resultados de máxima calidad bajo las restricciones dadas. Este método se basa en la programación entera-mixta, que es una técnica de optimización combinada. Aunque debemos introducir la heurística para procesar grandes conjuntos de datos, nuestro método produce exactamente el resultado óptimo para muestras pequeñas. Esto ofrece nueva posibilidades para evaluar el resultado de los métodos de generalización heurísticos.

Normalmente, dos diferentes problemas de generalización se distinguen: la obtención de una base de datos menos detallados a partir de uno dado y la derivación de un mapa gráfico, ya sea desde una base de datos o desde otro mapa. En este artículo vamos a abordar la generalización de la base de datos, que apunta a la abstracción de datos en lugar de la gráfica de eficacia. Como un requisito previo para la generalización automática de la base de datos, los organismos cartográficos nacionales en varios países han desarrollado especificaciones de base de datos, a menudo, la definición de las dimensiones mínimas que deben ser satisfechas en una escala (Afflerbach et al. 2004). A fin de garantizar la coherencia lógica, consideramos requisitos tales como las restricciones que definen el conjunto de generalización de soluciones factibles. Nos centramos en la generalización de las particiones planares ya que estos son comúnmente utilizados para representar la información de cobertura de la tierra. Esto implica que no podemos permitir espacios o áreas superpuestas. Un enfoque común para satisfacer las limitaciones de tamaño de una base de datos de estas características es la agrupación de zonas, es decir, combinar varios campos en uno solo. La mayoría de las veces esta tarea se resuelve mediante la fusión de las zonas pares iterativamente. El problema no ha sido abordado por la optimización aún. Evidentemente, dada las restricciones permiten encontrar diferentes soluciones viables.  Optimización de los medios para buscar la solución de la más alta calidad entre ellos. En los mapas de generalización, la calidad es a menudo expresada por un conjunto de limitaciones blandas, es decir, limitaciones que permiten diferentes grados de satisfacción. Por lo general, las restricciones son los conflictos y compromisos que se encuentran (Weibel y Dutton 1998). En nuestro enfoque, optimizamos la compacidad de formas y precisión semántica. Nuestra medida de este último se basa en cambios de clase. Los actuales planteamientos de problemas de optimización combinatoria en la generalización del mapa se basan principalmente en meta-heurística que iterativamente mejorar el mapa, tales como escalar la colina (Regnauld Galanda 2001, 2003), recocido simulado (Ware et al. 2003), o redes neuronales, que se aplican en la auto-organización mapas.

Algunos enfoques son capaces de organizar varios operadores de generalización.  Por ejemplo, el sistema de Galanda (2003), que se basa en un paradigma multi-agente, integra algoritmos para la reclasificación, la agregación, la tipificación, el desplazamiento, la exageración, el colapso, la eliminación, la ampliación, la simplificación y el suavizado.

Aunque nos centramos en la agregación de áreas, es necesaria una estrategia global. Una estrategia global, sin embargo, sólo puede tener éxito si los algoritmos subyacentes proporcionan soluciones de alta calidad. Por lo tanto, también vemos nuestro trabajo como una contribución a una mejor solución de toda la tarea. Para producir resultados muy generalizados, también hemos desarrollado un método para el colapso de área  (Haunert y Sester 2008) e implementando un algoritmo de simplificación líneal similar al de de Berg et al. (1998).  Proponemos aplicar estos procedimientos en sucesión: colapso de polígonos estrechos (por ejemplo, ríos), área de agregación y la simplificación de la línea. A partir de ahora, nos referimos al resultado del colapso interno como entrada.

...