Vectorización automática de una imagen binaria mediante K-means y degeneración de la triangulación de Delaunay

J.

Description

Resumen
En este artículo se presenta un método cuasi automático para extraer el esqueleto y la topología básica de una imagen binaria, obtenida por segmentación de una imagen color, correspondiente a la red lineal de carreteras. El proceso aplica la técnica K-means para establecer y estabilizar el conjunto inicial de nodos. A continuación construye el diagrama de Voronoi y la res-pectiva triangulación de Delaunay, para dar paso a la rectificación, serie de reiteraciones cuya finalidad es la degeneración de la triangulación mediante la sustitución automática de todos los triángulos por segmentos. Se sigue con la extracción de la topología que define los distintos objetos cartográficos y las conexiones entre los mismos como paso previo al ajuste y vectorización.
Abstract
In this paper a practically automatic method in order to extract the skeleton and the basic topology of a binary image is described. This image is obtained by color image segmentation, corresponding to the highways lineal net. The process applies the K-means technique in order to establish and stabilise the initial nodes group
next the Voronoi diagram and the respective Delau-nay triangulation is built. The rectification is made with a reiteration series whose purpose is the triangulation degeneration by the automatic substitution of all triangles for segments, and it is continued with the topology extraction. This topology defines the different cartographics objects, and the connections between them, as a previous step to the adjustment and vectorization.

Sujets

• Segmentación
• K-means clustering
• Voronoi
• Delaunay
• Segmentation
• Vectorization

Informations

• Publié par: erevistas
• Publié le: 01 janvier 2002
• Nombre de lectures: 59
• Langue: Español

Extrait

Revista de Teledetección. 2002. 17: 21-29.
Vectorización automática de una imagen binaria
mediante K-means y degeneración de la triangula-
ción de Delaunay
J. B. Mena
Área de Ciencias de la Escuela de Geodesia del Ejército.
(Darío Gazapo, 8. Madrid)
Departamento de Matemáticas de la Universidad de Alcalá de Henares.
(Campus Universitario. Escuela Politécnica. es)
RESUMEN ABSTRACT
En este artículo se presenta un método cuasi auto- In this paper a practically automatic method in
mático para extraer el esqueleto y la topología básica order to extract the skeleton and the basic topology of
de una imagen binaria, obtenida por segmentación de a binary image is described. This image is obtained
una imagen color, correspondiente a la red lineal de by color image segmentation, corresponding to the
carreteras. El proceso aplica la técnica K-means para highways lineal net. The process applies the K-means
establecer y estabilizar el conjunto inicial de nodos. A technique in order to establish and stabilise the initial
continuación construye el diagrama de Voronoi y la nodes group; next the Voronoi diagram and the res-
res-pectiva triangulación de Delaunay, para dar paso pective Delau-nay triangulation is built. The rectifica-
a la rectificación, serie de reiteraciones cuya finalidad tion is made with a reiteration series whose purpose is
es la degeneración de la triangulación mediante la the triangulation degeneration by the automatic subs-
sustitución automática de todos los triángulos por titution of all triangles for segments, and it is conti-
segmentos. Se sigue con la extracción de la topología nued with the topology extraction. This topology
que define los distintos objetos cartográficos y las defines the different cartographics objects, and the
conexiones entre los mismos como paso previo al connections between them, as a previous step to the
ajuste y vectorización. adjustment and vectorization.
PALABRAS CLAVE: segmentación, K-means, KEY WORDS: segmentation, K-means, Voronoi,
Voronoi, Delaunay, vectorización. Delaunay, vectorization.
diferentes órdenes de estadística (Mena, 2001), y laINTRODUCCIÓN
teoría de la evidencia de Dempster – Shafer (Shafer,
1976). En el ámbito concreto de la extracción deLa pretensión de la comunidad científica de obte-
elementos lineales, en particular de las vías dener cartografía de forma totalmente automatizada a
comunicación, tales técnicas permiten obtener, apartir de imágenes de satélite es, hoy por hoy, una
partir de la superposición de la imagen color geo-utopía. Sin embargo, los continuos estudios que se
rreferenciada de alta resolución con la capa vecto-realizan al respecto, unidos a la tecnología cada vez
rial del GIS, una imagen ráster binaria donde semás sofisticada sobre la que se apoya el GIS y el
destacan la práctica totalidad de los pixeles que for-tratamiento de imágenes, junto con las altas resolu-
man parte del objeto “carretera”. Esta imagen, trasciones que proporcionan satélites como HELIOS o
su depuración, nos servirá de base para acometer laIKONOS, hacen que el logro de dicho objetivo se
acerque progresivamente. vectorización y el posterior almacenamiento en el
En un marco general ya es posible conseguir GIS de las distintas entidades extraídas, consi-
guiéndose así la actualización del sistema. No obs-resultados aceptables en la extracción más o menos
automática de entidades cartográficas, por ejemplo tante, el proceso de vectorización de una imagen de
mediante aplicación del análisis de texturas bajo estas características no es simple. Nosotros hemos
N.º 17 - Junio 2002 21J. B. Mena
optado por la extracción inicial del esqueleto según EXTRACCION DEL ESQUELETO
el método que se describe a continuación, segui-
do de un análisis de la topología y del ajuste de Consideremos la imagen color de la Figura 1.a, y
la nube de puntos componentes de cada objeto la correspondiente imagen binaria 1.b resultante de
lineal. Una vez obtenidos los distintos objetos en aplicar a la primera nuestro método automático de
2-D, así como las conexiones entre los mismos, la extracción de entidades lineales orientado a carrete-
combinación con el MDT permitirá conseguir la ras en zonas rurales o semiurbanas (Mena, 2001).
geometría 3-D de los elementos y por tanto su
almacenamiento en la Base de Datos Cartográfica Definamos previamente el dominio D de la variable
(BDC) del GIS. Análogamente, un Sistema Basa- como el conjunto de los n pixeles p pertenecientes ali
do en el Conocimiento (SBC) podría, al menos área detectada (pixeles representados en blanco).
teóricamente, utilizar la información recogida en Evidentemente, cada uno de estos pixeles está caracte-
la Base de Datos Alfa-numérica (BDA) del GIS rizado por sus coordenadas (x , y ) en la imagen binaria.i i
para agregar los atributos correspondientes a la
geometría detectada.
K-means y diagrama de Voronoi
Aunque existen otros métodos de extracción del
esqueleto (Sanniti di Baja, 1994) y vectorización Para determinar la mejor aproximación posible
(Miravet, 1998), el que presentamos aquí, aparte de del esqueleto o línea media del conjunto D, comen-
ser sumamente sencillo, tiene la gran ventaja de zaremos por situar en el interior de D, y sólo aquí,
permitir, hasta un cierto límite que es función de un cierto número K de nodos h , bien de forma ale-
i
la estructura de la imagen binaria, la obtención atoria, bien distribuidos según el intervalo n/K en la
del esqueleto con la aproximación que se quiera, ordenación de D por abscisa y ordenada, o bien
determinándose implícitamente el grafo previo mediante cualquier otro criterio.
a la vectorización. Este proceso, alternativo a
(Doucette, 2001), lo subdividimos en las siguientes A continuación se procede a clasificar los n pixe-
fases sucesivas compuestas por las etapas que se les del conjunto D en K subconjuntos atendiendo a
indican: la mínima distancia euclídea respecto al total de los
nodos (Clustering). De este modo habremos conse-
1. Extracción del esqueleto: guido un número K de clusters cuyas líneas de con-
- K-means. tacto constituyen el diagrama de Voronoi del domi-
- Diagrama de Voronoi. nio D relativo a las posiciones iniciales de los K
- Triangulación de Delaunay. nodos. Esto es así debido a que en este momento
- Proceso degenerativo de rectificación. cada pixel p Œ D está incluido en el cluster corres-i
2. Topología: pondiente al nodo h Œ K más cercano, no conside-i
- Grafo del esqueleto. rándose pixel alguno que no pertenezca a D.
- Grafo principal.
3. Vectorización: Aplicando la técnica del clustering, seguidamen-
- Ajuste robusto condicionado. te calculamos el centro de gravedad de todos y cada
* Figura 1. Imágenes en color y binaria
Todas las figuras precedidas de asterisco se incluyen en el cuadernillo anexo de color
22 N.º 17 - Junio 2002Vectorización automática de una imagen binaria meidante K-means y degeneración...
Figura 2. K-means y diagrama de Voronoi.
uno de los clusters y movemos los K nodos a dichas más triángulos, dependiendo de su posición en el
posiciones. Este hecho implica una nueva clasifica- interior de D. Como ejemplo observemos en la
ción para el total de los pixeles de D, con la consi- Figura 3 la triangulación inicial, compuesta de 48
guiente variación de los clusters y del diagrama de trián-gulos, que se obtiene a partir del diagrama
Voronoi resultante. Reiterando sucesivamente el representado en 2.b.
proceso, conseguimos la estabilización del mismo
una vez se alcancen las posiciones definitivas de los
K nodos. Llegados a este punto se observa una Proceso degenerativo de rectificación
regular distribución en distancia de los nodos, así
como un diagrama de Voronoi V (D, K) caracterís- La triangulación obtenida en la etapa anterior
tico de tal distribución. En la Figura 2 presentamos puede especificarse mediante la notación T (K, t),
dichos resultados cuando se elige K = 105 para la donde K es el número inicial de nodos y t el núme-
imagen de la Figura 1.b. ro de triángulos que se han formado. En ella, pues-
to que lo pretendido es la determinación del esque-
leto, resulta evidente que éste se pone de manifies-
Triangulación de Delaunay to en aquellas zonas donde no existen triángulos,
siendo tales figuras un inconveniente para nuestros
El paso siguiente consiste en construir la triangu- propósitos. En consecuencia, aplicamos seguida-
lación de Delaunay relativa al diagrama V (D, K). mente un proceso degenerativo cuya finalidad es la
Como es sabido, esta tarea se consigue uniendo los conversión del par (K, t) en el correspondiente (K ,
m
centros de las regiones de Voronoi colindantes. 0), donde siempre K < K. En otras pala