Algoritmo de Ramer–Douglas–Peucker

El algoritmo de Ramer–Douglas–Peucker (RDP) es un algoritmo para reducir el número de puntos utilizados en la aproximación de una curva. La forma inicial del algoritmo fue independientemente propuesta en 1972 por Urs Ramer, en 1973 por David Douglas and Thomas Peucker^[1] y algunos más en la siguiente década.^[2] Este algoritmo también es conocido con el nombre de algoritmo de Douglas-Peucker.

Idea

El objetivo del algoritmo es, dada una curva compuesta por segmentos, encontrar una curva similar aproximada con menos puntos. El algoritmo define una diferencia basada en la máxima distancia entre la curva original y la curva simplificada. La curva simplificada consiste en una reducción de los puntos que definían la curva original.

Algoritmo

La curva inicial es una lista ordenada de puntos o segmentos y un umbral de error ε > 0.

El algoritmo construye una aproximación de la curva inicial mediante un proceso recursivo. Se toma como solución inicial el segmento que une los dos puntos extremos de la curva. Entonces, se busca el punto más alejado de dicho segmento (peor punto).

Si el peor punto está más cerca del segmento que el umbral de distancia ε, entonces se termina el proceso. Es seguro que el resto de puntos de la curva están a menor distancia que el umbral ε, y por lo tanto todos los puntos de la curva (salvo los extremos) pueden ser descartados.

Si el peor punto está más alejado que ε, entonces ese punto debe permanecer en la simplificación. El algoritmo hace dos llamadas recursivas a sí mismo para calcular la aproximación de dos curvas de menor longitud. Una con los puntos entre el primer y el peor punto y otra con los puntos entre el peor punto y el punto final de la curva.

Cuando se completa la recursión la nueva curva puede ser generada a partir de los puntos que han permanecido tras haber aplicado el algoritmo.

Pseudocódigo

function DouglasPeucker(PointList[], epsilon)
    // Busca el punto con la distancia máxima
    dmax = 0
    index = 0
    end = length(PointList)
    for i = 2 to ( end - 1) {
        d = shortestDistanceToSegment(PointList[i], Line(PointList[1], PointList[end])) 
        if ( d > dmax ) {
            index = i
            dmax = d
        }
    }
    // Si la distancia es mayor que epsilon, simplificar recursivamente
    if ( dmax > epsilon ) {
        // Llamada recursiva
        recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
        recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
 
        // Construcción de la lista resultado
        ResultList[] = {recResults1[1...end-1] recResults2[1...end]}
    } else {
        ResultList[] = {PointList[1], PointList[end]}
    }
    // Devolver el resultado
    return ResultList[]
end

RDP no paramétrico

La elección de ε es normalmente una distancia elegida por el usuario. Como la mayoría de métodos de ajuste de línea, aproximación poligonal o detección del punto dominante, es posible realizar una versión no paramétrica del algoritmo, calculando un valor para ε basándose en el uso del error vinculado debido a la digitalización o la cuantificación.^[3] El código MATLAB de la versión no paramétrica del algoritmo^[4] está disponible en línea.^[5]

Aplicaciones

El algoritmo es utilizado para el procesamiento de imágenes vectoriales y generalización cartográfica.

El algoritmo es ampliamente utilizado en robótica^[6] para realizar simplificaciones y eliminar ruido al medir distancias con telémetros giratorios.

Complejidad

La complejidad esperada por este algoritmo puede describirse con la recurrencia linear $T(n){=}2T({n \over 2})+O(n)$ , la cual tiene solución conocida a través del Teorema maestro de $T(n)\in \Theta (nlog(n))$ . De todos modos, la complejidad en el peor caso es $\Theta (n^{2})$ .

Otros algoritmos de simplificación de líneas

Entre otros algoritmos para la simplificación de líneas se encuentran:

Algoritmo de Visvalingam–Whyatt
Algoritmo de Reumann–Witkam
Algoritmo de simplificación Opheim
Algoritmo de simplificación Lang

Referencias

Urs Ramer, "An iterative procedure for the polygonal approximation of plane curves", Computer Graphics and Image Processing, 1(3), 244–256 (1972) doi 10.1016/S0146-664X(72)80017-0

David Douglas & Thomas Peucker, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature", The Canadian Cartographer 10(2), 112–122 (1973) doi 10.3138/FM57-6770-U75U-7727

John Hershberger & Jack Snoeyink, "Speeding Up the Douglas–Peucker Line-Simplification Algorithm", Proc 5th Symp on Data Handling, 134–143 (1992). UBC Tech Report TR-92-07 available at https://web.archive.org/web/20160414023022/http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07

R.O. Duda and P.E. Hart, "Pattern classification and scene analysis", (1973), Wiley, New York (https://web.archive.org/web/20110715184521/http://rii.ricoh.com/~stork/DHS.html)

Visvalingam, M., and Whyatt, J.D. "Line Generalisation by Repeated Elimination of the Smallest Area". (1992) CISRG Discussion Paper Series No 10, University of Hull, 16 pp (https://web.archive.org/web/20140210052537/http://www2.dcs.hull.ac.uk/CISRG/publications/DPs/DP10/DP10.html)

Notas

↑ Ver referencia para más detalles
↑ Heckbert, Paul S.; Garland, Michael (1997). Survey of polygonal simplification algorithms. p. 4.
↑ Prasad, Dilip K.; Leung, Maylor K.H.; Quek, Chai; Cho, Siu-Yeung (2012). «A novel framework for making dominant point detection methods non-parametric». Image and Vision Computing 30 (11): 843-859. doi:10.1016/j.imavis.2012.06.010.
↑ Prasad, Dilip K.; Quek, Chai; Leung, Maylor K.H.; Cho, Siu-Yeung (2011). A parameter independent line fitting method. 1st IAPR Asian Conference on Pattern Recognition (ACPR 2011), Beijing, China, 28-30 Nov. doi:10.1109/ACPR.2011.6166585.
↑ Prasad, Dilip K. «Matlab source code for non-parametric RDP». Consultado el 15 de octubre de 2013.
↑ Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland (2007). «A comparison of line extraction algorithms using 2D range data for indoor mobile robotics». Autonomous Robots 23 (2): 97. doi:10.1007/s10514-007-9034-y. Archivado desde el original el 17 de septiembre de 2010.

Enlaces externos

Datos: Q1251950

[1] Ver referencia para más detalles

[2] Heckbert, Paul S.; Garland, Michael (1997). Survey of polygonal simplification algorithms. p. 4.

[3] Prasad, Dilip K.; Leung, Maylor K.H.; Quek, Chai; Cho, Siu-Yeung (2012). «A novel framework for making dominant point detection methods non-parametric». Image and Vision Computing 30 (11): 843-859. doi:10.1016/j.imavis.2012.06.010.

[4] Prasad, Dilip K.; Quek, Chai; Leung, Maylor K.H.; Cho, Siu-Yeung (2011). A parameter independent line fitting method. 1st IAPR Asian Conference on Pattern Recognition (ACPR 2011), Beijing, China, 28-30 Nov. doi:10.1109/ACPR.2011.6166585.

[5] Prasad, Dilip K. «Matlab source code for non-parametric RDP». Consultado el 15 de octubre de 2013.

[6] Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland (2007). «A comparison of line extraction algorithms using 2D range data for indoor mobile robotics». Autonomous Robots 23 (2): 97. doi:10.1007/s10514-007-9034-y. Archivado desde el original el 17 de septiembre de 2010.

[1]

[2]

[3]

[4]

[5]

[6]