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]

ProcedimentModifica

 
Simplificació d'una corba definida a trossos amb l'algorisme RDP.

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  , la qual té solució coneguda a través del Teorema mestre de  . En el pitjor dels casos la complexitat és  .

RDP no paramètricModifica

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íniesModifica

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

BibliografiaModifica

ReferènciesModifica

  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. DOI: 10.1007/s10514-007-9034-y.
  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ços externsModifica