Algorisme de Ramer–Douglas–Peucker

L'algorisme de Ramer–Douglas–Peucker (RDP) és un algorisme per reduir el nombre de punts utilitzats en l'aproximació d'una corba. La forma inicial de l'algorisme va ser independentment proposada el 1972 per Urs Ramer, i el 1973 per David Douglas i Thomas Peucker i alguns altres en la dècada posterior.^[1]

L'algorisme és utilitzat en processament d'imatges vectorials i generalització cartogràfica. També és àmpliament utilitzant en robòtica per realitzar simplificacions i per mesurar distàncies amb telèmetres giratoris.^[2]

Procediment

L'objectiu de l'algorisme és, donada una corba composta per segments, trobar una corba similar aproximada amb menys punts. L'algorisme defineix una diferència basada en la màxima distància entre la corba original i la simplificada. La corba simplificada consisteix per tant en una reducció dels punts que definien la corba original.

Es parteix d'una corba inicial definida com una llista ordenada de punts o segments, i un marge d'error ε > 0. L'algorisme constitueix una aproximació de la corba inicial mitjançant un procés recursiu. Inicialment es fa el procediment sobre els dos punts extrems de la corba, traçant una línea recta entre ells. Llavors, es busca el punt més allunyat perpendicularment d'aquest segment (pitjor punt).

Si el pitjor punt està més a prop del segment que el marge d'error ε, el procés acaba, ja que vol dir que la resta de punts de la corba estan a menor distància de ε, i per tant tots els punts de la corba (excepte els extrems) poden ser descartats.
Si el pitjor punt està més allunyat del segment que ε, aquest punt ha de romandre en la simplificació. L'algorisme aplica dos mètodes recursius a si mateix per calcular l'aproximació de dues corbes de menor longitud, una amb els punts entre el primer i el pitjor punt, i l'altra amb els punts entre el pitjor punt i el final. A cadascuna d'elles se li torna a aplicar l'algorisme.

La complexitat esperada per aquest algorisme es pot descriure amb la recurrència linear $T(n){=}2T({n \over 2})+O(n)$ , la qual té solució coneguda a través del Teorema mestre de $T(n)\in O(nlog(n))$ . En el pitjor dels casos la complexitat és $O(n^{2})$ .

RDP no paramètric

L'elecció de ε normalment s'elegeix per l'usuari. Com en la majoria de mètodes de simplificació de línea, aproximació poligonal o detecció del punt dominant, és possible realitzar una versió no paramètrica de l'algorisme, calculant un valor per ε basant-se en l'ús de l'error vinculat a causa de la digitalització o la quantificació.^[3] El codi MATLAB de la versió no paramètrica de l'algorisme^[4] està disponible a la xarxa.^[5]

Altres algorismes de simplificació de línies

Algorisme de Visvalingam–Whyatt
Algorisme de Reumann–Witkam
Algorisme de simplificació d'Opheim
Algorisme de simplificació de Lang

Bibliografia

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

Referències

↑ Paul S. Hackbert, Michael Garland «Survey of polygonal simplification algorithms». School of Computer Science, 1997, pàg. 4.
↑ Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland «A comparison of line extraction algorithms using 2D range data for indoor mobile robotics». Autonomous Robots, 23, 2, 2007, pàg. 97. Arxivat de l'original el 17 de setembre de 2010. DOI: 10.1007/s10514-007-9034-y. Arxivat 2010-09-17 a Wayback Machine.
↑ Prasad, Dilip K.; Leung, Maylor K.H.; Quek, Chai; Cho, Siu-Yeung «A novel framework for making dominant point detection methods non-parametric». Image and Vision Computing, 30, 11, 2012, pàg. 843–859. DOI: 10.1016/j.imavis.2012.06.010.
↑ (2011) "A parameter independent line fitting method" a 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». [Consulta: 15 octubre 2013].^{[Enllaç no actiu]}

Enllaços externs

[1] Paul S. Hackbert, Michael Garland «Survey of polygonal simplification algorithms». School of Computer Science, 1997, pàg. 4.

[2] Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland «A comparison of line extraction algorithms using 2D range data for indoor mobile robotics». Autonomous Robots, 23, 2, 2007, pàg. 97. Arxivat de l'original el 17 de setembre de 2010. DOI: 10.1007/s10514-007-9034-y. Arxivat 2010-09-17 a Wayback Machine.

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

[4] (2011) "A parameter independent line fitting method" a 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». [Consulta: 15 octubre 2013].^{[Enllaç no actiu]}

[1]

[2]

[3]

[4]

[5]