Algoritmo de extracción de rectas

Capítulo 3

Algoritmo de Extracción de Rectas

El ROMEO lleva incorporado un láser que le permite saber los obstáculos que hay en su
entorno, y a la distancia a la que se encuentran. Lo que hace, es realizar un barrido de cierta
apertura numérica para determinar para cada valor del ángulo comprendido en ese rango, una
distancia al obstáculo. De esta forma, se obtiene un mapa local delentorno centrado en el
ROMEO. El láser mide una distancia para un valor del ángulo determinado, y eso no son más
que las coordenadas polares de un punto. Si se representan todos los puntos generados, el mapa
que se obtiene es el que se muestra en la figura 3.1.
Para el algoritmo de SLAM que se va a emplear, se supondrá que los obstáculos vendrán
definidos por rectas, no por puntos, es decir, quedichos obstáculos serán las paredes. Por ello, la
función del algoritmo de extracción de rectas es, a partir de un conjunto de puntos como pueden
ser los que aparecen en la figura 3.1, determinar las diferentes rectas que forman.
En la literatura se pueden encontrar muy diversos métodos que permiten extraer rectas a
partir de puntos. En [13] se pueden ver diferentes algoritmos y un cuadrocomparativo entre
ellos. Algunos de los algoritmos que ahí aparecen son el de Segmentación y Fusión, el de
RANSAC, el de la Transformada de Hough... [6], [14], [20].
El algoritmo de extracción de rectas que se empleará en el algoritmo de SLAM será el de
Segmentación y Fusión, ya que según [13] es el más rápido y de los que mejores resultados
proporcionan.
22

3.1. Algoritmo de Segmentación yFusión

Figura 3.1: Puntos obtenidos al realizar un barrido con el láser
1.-

Inicio: Conjunto s1 de N puntos. Se asigna s1 a una lista L.

2.-

Se ajusta una línea al siguiente conjunto si de puntos en L.

3.-

Se detecta el punto P cuya distancia dP a la línea sea mayor.

4.-

Si dP es menor que cierto umbral, volver al paso 2.

5.-

Sino, se divide por el punto P el conjuntosi en dos subconjuntos
si1 y si2 . Se sustituye si en L por si1 y si2 . Volver al paso 2.

6.-

Cuando todos los conjuntos en L se hayan analizado, fusionar
los segmentos colineales.
Tabla 3.1: Algoritmo de Segmentación y Fusión

3.1.

Algoritmo de Segmentación y Fusión

Los pasos de que consta este algoritmo son los que se describen en la tabla 3.1. Dicha
tabla muestra a grandesrasgos el procedimiento a seguir. Sin embargo, el proceso es algo más
3. Algoritmo de Extracción de Rectas

23

3.1. Algoritmo de Segmentación y Fusión
complejo, y hay que tener en cuenta una serie de condiciones adicionales. En la figura 3.2
aparece el diagrama de flujo completo del algoritmo, cuyos módulos se irán explicando uno por
uno a continuación.

3.1.1.

Situación inicialInicialmente, se dispone de un conjunto M de puntos en coordenadas polares, que son los
que proporciona el láser. Dicho conjunto puede ser por ejemplo el que aparecía en la figura 3.1.

3.1.2.

Filtrado según la distancia

Se puede observar que el alcance del láser es de unos 80 metros, ya que si no detectara
ningún obstáculo, los puntos describirían un arco de circunferencia. Dichos puntos nosirven
para detectar líneas, ya que en realidad no existen. Por tanto, se realizará un filtrado, de forma
que todos esos puntos queden fuera del conjunto de puntos a los que se le aplicará el algoritmo
de Segmentación y Fusión (S&F a partir de ahora). En la figura 3.3 puede verse la situación
anterior y posterior al proceso de filtrado.

3.1.3.

Cambio de coordenadas

Tras pasar los puntospor el filtro, el conjunto inicial de M , se reducirá a N puntos. Dicho
conjunto N se añade a la lista L.
Como ya se comentó anteriormente, el láser proporciona la distancia y el ángulo que hay
que girar para llegar a un obstáculo. Estos dos parámetros son las coordenadas polares de un
punto. Sin embargo, para poder aplicar de forma más eficiente el algoritmo de S&F es preferible
emplear...