universidad de guayaquilrepositorio.ug.edu.ec/bitstream/redug/49499/1/b-cisc-ptg...de autor en forma...

UNIVERSIDAD DE GUAYAQUIL

FACULTAD DE CIENCIAS MATEMATICAS Y FISICAS

CARRERA DE INGENIERIA EN SISTEMAS

COMPUTACIONALES

Analisis de filtro de KALMAN en algoritmos de simplificacion

de trayectorias GPS lineales no lineales.

PROYECTO DE TITULACION

Previa a la obtencion del Tıtulo de:

INGENIERO EN SISTEMAS COMPUTACIONALES

AUTOR(A):

KEYLA PAULETTE CEDENO HERMIDA

ALEXANDER DANIEL MITE ORELLANA

TUTOR(A):

ING. GARY REYES ZAMBRANO M. SC.

GUAYAQUIL – ECUADOR

2020

APROBACION DEL TUTOR

En mi calidad de Tutor(a) del trabajo de titulacion, “ ANALISIS DE FILTRO DE KALMAN

EN ALGORITMOS DE SIMPLIFICACION DE TRAYECTORIAS GPS LINEALES Y NO

LINEALES.” elaborado por KEYLA PAULETTE CEDENO HERMIDA Y ALEXANDER

DANIEL MITE ORELLANA , Alumnos no titulados de la Carrera de Ingenierıa en Sistemas

Computacionales, Facultad de Ciencias Matematicas y Fısicas de la Universidad de Guayaquil,

previo a la obtencion del Tıtulo de Ingeniero en Sistemas, me permito declarar que luego de

haber orientado, estudiado y revisado, la apruebo en todas sus partes.

Atentamente

Ing. Gary Reyes Zambrano, Mgs.

TUTOR(A)

III

DEDICATORIA

Dedico el trabajo de titulacion a las personas

que siempre me apoyaron a lo largo de

esta carrera mis padres, mis hermanos, mi

enamorado y familia.

Keyla Paulette Cedeno Hermida

A mi madre por ser mi ejemplo a seguir. Hoy

que no estas sigues siendo mi pilar para con-

tinuar adelante.

Alexander Daniel Mite Orellana

IV

AGRADECIMIENTO

Agradezco a Dios por siempre mantenerme

de pie y en la lucha de ser alguien mejor en

la vida, a mis padres, hermanos y enamorado

por siempre guiarme, a mi tutor el Ing. Gary

Reyes Zambrano por la ayuda brindada a lo

largo de la carrera y la paciencia.

Keyla Paulette Cedeno Hermida

Al personal academico de la universidad de

Guayaquil, quienes supieron impartir con

mucho esfuerzo sus conocimientos.

Alexander Daniel Mite Orellana

V

TRIBUNAL DE PROYECTO DE TITULACION

Ing. Fausto Cabrera Montes, M.Sc.DECANO DE LA FACULTAD

CIENCIAS MATEMATICAS Y FISICAS

Ing. Gary Reyes Zambrano, Mgs.PROFESOR(A) TUTOR(A) DEL

PROYECTODE TITULACION

Ing. Gary Reyes Zambrano, Mgs.DIRECTOR DE LA CARRERA DE

INGENIERIA EN SISTEMASCOMPUTACIONALES

Ing. Marıa Isabel Galarza SoledispaPROFESOR(A) REVISOR DEL

PROYECTODE TITULACION

Ab. Juan Chavez Atocha, Esp.SECRETARIO

VI

DECLARACION EXPRESA

“La responsabilidad del contenido de este Proyecto de Ti-

tulacion, me corresponden exclusivamente; y el patrimonio

intelectual de la misma a la UNIVERSIDAD DE GUAYA-

QUIL”

Keyla Paulette Cedeno HermidaDEL TRABAJO DE TITULACION

Alexander Daniel Mite OrellanaDEL TRABAJO DE TITULACION

VII

CESION DE DERECHOS DE AUTOR

Ingeniero

Fausto Cabrera Montes, M.Sc.

Decano de la Facultad de Ciencias Matematicas y Fısicas

Presente.

A traves de este medio ındico a usted que proceda a realizar la entrega de la Cesion de Derechos

de Autor en forma libre y voluntaria del trabajo ”ANALISIS DE FILTRO DE KALMAN EN

ALGORITMOS DE SIMPLIFICACION DE TRAYECTORIAS GPS LINEALES Y NO

LINEALES.”, realizado como requisito previo para la obtencion del tıtulo de Ingeniero(a) en

Sistemas Computacionales, a la Universidad de Guayaquil.

Guayaquil, Octubre de 2020.

Keyla Paulette Cedeno HermidaC.I. N0 0924425960

Alexander Daniel Mite OrellanaC.I. N0 0953890597

VIII



CARRERA DE INGENIERIA EN SISTEMAS COMPUTACIONALES



Proyecto de Titulacion que se presenta como requisito para optar por el tıtulo de

INGENIERO(A) EN SISTEMAS COMPUTACIONALES

Autor(a): Keyla Paulette Cedeno Hermida

C.I. N0 0924425960

Alexander Danile Mite Orellana

C.I. N0 0953890597

Tutor(a): Ing. Gary Reyes Zambrano


IX

CERTIFICADO DE ACEPTACION DEL TUTOR(A)

En mi calidad de Tutor(a) del Proyecto de Titulacion, nombrado por el Consejo Directivo de la

Facultad de Ciencias Matematicas y Fısicas de la Universidad de Guayaquil.

CERTIFICO:

Que he analizado el Proyecto de Titulacion presentado por el(la) estudiante Keyla Pau-

lette Cedeno Hermida,Alexander Daniel Mite Orellana como requisito previo para optar por

el tıtulo de Ingeniero(a) en Sistemas Computacionales cuyo proyecto es:

ANALISIS DE FILTRO DE KALMAN EN ALGORITMOS DE SIMPLIFICACION DE

TRAYECTORIAS GPS LINEALES Y NO LINEALES.

Considero aprobado el trabajo en su totalidad.

Presentado por:

Keyla Paulette Cedeno Hermida N° 0924425960

Alexander Daniel Mite Orellana N° 0953890597

Tutor(a):

Firma


X



CARRERA DE INGENIERIA EN SISTEMAS

COMPUTACIONALES

AUTORIZACION PARA PUBLICACION DE PROYECTO DE TITULACION EN FORMATO

DIGITAL1. Identificacion del Proyecto de Titulacion

Nombre del Estudiante: Keyla Paulette Cedeno HermidaDireccion: Calle 37 y el oroTelefono: 0997939153 Email: [email protected]

Nombre del Estudiante: Alexander Daniel Mite OrellanaDireccion:Guasmo Norte. Coop Los Jazmines Mz E Sl16Telefono: 0982951323 Email: [email protected]

Facultad: Ciencias Matematicas y FısicasCarrera: Ingenierıa en Sistemas ComputacionalesProyecto de Titulacion al que opta:Profesor(a) Tutor(a): Ing. Gary Reyes Zambrano, Mgs.

Tıtulo del Proyecto de Titulacion: Analisis de filtro de KALMAN en algoritmos de simplifica-cion de trayectorias GPS lineales y no lineales.Palabras Claves: simplificacion, linealidad, simulada, filtrado, metricas.

2. Autorizacion de Publicacion de Version Electronica del Proyecto de TitulacionA traves de este medio autorizo a la Biblioteca de la Universidad de Guayaquil y a la Facultad deCiencias Matematicas y Fısicas a publicar la version electronica de este Proyecto de Titulacion.

Publicacion Electronica:

Inmediata Despues de 1 ano

Firma Estudiante(s):

Keyla Paulette Cedeno Hermida N° 0924425960

Alexander Daniel Mite Orellana N° 09538905973. Forma de envıo:El texto del Proyecto de Titulacion debe ser enviado en formato Word, como archivo .Doc, .RTF o .Pufpara PC. Las imagenes que la acompanen pueden ser: .GIF, .JPG o .TIFF.

DVDROM CDROM

XI

INDICE GENERAL

APROBACION DEL TUTOR III

DEDICATORIA IV

AGRADECIMIENTO V

TRIBUNAL DE PROYECTO DE TITULACION VI

DECLARACION EXPRESA VII

CESION DE DERECHOS DE AUTOR VIII

CERTIFICADO DE ACEPTACION DEL TUTOR(A) X

AUTORIZACION PARA PUBLICACION DE PROYECTO DE TITULACION EN

FORMATO DIGITAL XI

INDICE GENERAL XII

INDICE DE TABLAS XVI

INDICE DE FIGURAS XVIII

ABREVIATURAS XIX

SIMBOLOGIA XX

RESUMEN XXI

ABSTRACT XXII

INTRODUCCION 1

XII

CAPITULO I - PLANTEAMIENTO DEL PROBLEMA 2

Descripcion de la situacion problematica 2

Ubicacion del problema en un contexto . . . . . . . . . . . . . . . . . . . . . . . . . 2

Delimitacion del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Evaluacion del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Formulacion del problema 5

Causas y consecuencias del problema 6

Objetivos del proyecto 6

Objetivo general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Objetivo especıficos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Alcance del proyecto 7

Justificacion e importancia 8

Limitaciones del estudio 9

CAPITULO II - MARCO TEORICO 10

Antecedentes del estudio 10

Fundamentacion teorica 11

Hipotesis / Preguntas cientıficas a contestarse 27

Variables de la investigacion 27

Definiciones conceptuales 27

XIII

CAPITULO III - METODOLOGIA DE LA INVESTIGACION 30

Modalidad de la investigacion 30

Tipo de investigacion 30

Diseno metodologico de la investigacion 31

Metodologıa de investigacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

Poblacion y muestra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Procesamiento y analisis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Beneficiarios directos e indirectos del proyecto 58

Entregables del proyecto 58

Resultados 59

CAPITULO IV - CONCLUSIONES Y RECOMENDACIONES 66

Conclusiones 66

Recomendaciones 68

Referencias 69

BIBLIOGRAFIA 73

Anexo 1. Planificacion de actividades del proyecto . . . . . . . . . . . . . . . . . . 74

Anexo 2. Geo-localizacion del problema . . . . . . . . . . . . . . . . . . . . . . . . 75

Anexo 3. Carta de autorizacion del proyecto . . . . . . . . . . . . . . . . . . . . . . 76

Anexo 4. Fundamentacion legal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

Anexo 7. Validacion de expertos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

XIV

Anexo 15. Artıculo cientıfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

XV

INDICE DE TABLAS

Tabla 1. Delimitacion del problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Tabla 2. Matriz de causas y consecuencias del problema . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Tabla 3. Poblacion total de los conjuntos de datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Tabla 4. Tamano de la muestra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

Tabla 5. Nombres de las columnas que contiene los conjuntos de datos Beijing y Brasil . 36

Tabla 6. Nombres de las columnas que contiene los conjuntos de datos California . . . . . . 36

Tabla 7. Nombres de las columnas que contiene los conjuntos de datos Guayaquil y

Quito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

Tabla 8. Datos del Administrador de PostgreSQL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Tabla 9. Porcentajes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Tabla 10. Porcentaje de linealidad base de datos Beijing . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Tabla 11. Porcentaje de linealidad base de datos Brasil . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

Tabla 12. Porcentaje de linealidad base de datos California . . . . . . . . . . . . . . . . . . . . . . . . 43

Tabla 13. Porcentaje de linealidad base de datos Guayaquil . . . . . . . . . . . . . . . . . . . . . . . . 44

Tabla 14. Porcentaje de linealidad base de datos Quito. . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

Tabla 15. Filtro Kalman aplicado en los conjuntos de datos . . . . . . . . . . . . . . . . . . . . . . . . 47

Tabla 16. Resultados de la simplificacion con los algoritmos y epsilon escogido . . . . . . . 48

Tabla 17. Resultados de la evaluacion con las metricas en la simplificacion usando el

algoritmo RDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50


algoritmo TD-TR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

XVI

Tabla 19. Resultados de la simplificacion con los algoritmos con el epsilon escogido. . . . 52


algoritmo RDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54


algoritmo TD-TR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

Tabla 22. Trayectorias originales con los algoritmos de simplificacion y las trayectorias

con Filtro Kalman con los algoritmos de simplificacion de los conjuntos de datos . . . . . . . 56

Tabla 23. Media Douglas Peucker TD-TR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Tabla 24. Desviacion Estandar Douglas Peucker y TD-TR. . . . . . . . . . . . . . . . . . . . . . . . . 61

Tabla 25. Media del Filtrado Kalman con los algoritmo de simplificacion Douglas Peuc-

ker TD-TR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Tabla 26. Desviacion Estandar Douglas Peucker y TD-TR. . . . . . . . . . . . . . . . . . . . . . . . . 64

XVII

INDICE DE FIGURAS

Figura 1. Vision completa del Filtro Kalman. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Figura 2. Trayectoria Original y Trayectoria simplificada Douglas Peucker . . . . . . . . . . . 49

Figura 3. Trayectoria Original y Trayectoria simplificada TD-TR . . . . . . . . . . . . . . . . . . . 49

Figura 4. Trayectoria Filtrada y Trayectoria simplificada Douglas Peucker . . . . . . . . . . . . 53

Figura 5. Trayectoria Filtrada y Trayectoria simplificada TD-TR . . . . . . . . . . . . . . . . . . . 53

Figura 6. Media de los algoritmos de simplificacion Douglas Peucker y TD-TR . . . . . . . 60

Figura 7. Desviacion estandar de los algoritmos de simplificacion Douglas Peucker y

TD-TR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

Figura 8. Media del Filtrado Kalmann con los algoritmos de simplificacion Douglas

Peucker y TD-TR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

Figura 9. Desviacion Estandar del Filtrado Kalmann con los algoritmos de simplifica-

cion Douglas Peucker y TD-TR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

XVIII

ABREVIATURAS

GPS Sistema de Posicionamiento Global

RDP Ramer-Douglas-Peucker

TD-TR Top Down-Time Ratio

SD Distancia Espacial

DLM Modelos lineales dinamicos

XIX

SIMBOLOGIA

s Desviacion estandar

M(x) Media Aritmetica

xk Vector de Estado

Vk Ruido d Medicion

A Matriz de Estado

B Matriz de control

XX






Autor(a)(es): Keyla Paulette Cedeno HermidaC.I. N0 0924425960


Tutor(a): Ing. Gary Reyes Zambrano, Msg.

RESUMEN

En la actualidad el avance de nuevas tecnologıas con lo que respecta a la localizacion deun objeto en movimiento, se ha podido observar un gran incremento de los datos de unatrayectoria al igual que el ruido de ellas, acumulando muchos puntos de coordenadas llegandoa redundar y a tener datos invalidos e innecesarios. En el proyecto se realiza el proceso deevaluacion de los resultados que han sido adquiridos de las experimentaciones realizadas.Ademas de estudiar cual es el comportamiento que tiene el filtro de Kalman cuando es aplicadoa los algoritmos de simplificacion (Douglas Peucker y TD-TR) de trayectorias (GPS) lineales yno lineales. Para esto se utilizaron 5 conjuntos de bases de datos, tantos reales como simuladascirculares por motivos de pruebas. Para la validacion de los resultados se evaluaron 3 tiposde metricas como son: el tiempo de ejecucion, margen de error y la razon de compresion.Se concluye que al aplicar metodos estadısticos de la media y desviacion estandar, donde seobtuvieron resultados favorables con el filtro de kalman aplicados al algoritmo TD-TR, peroademas se pudo observar que en tiempo de ejecucion el algoritmo de Douglar Peucker destacamuchos mas en la investigacion.

Palabras clave: simplificacion, ruido, simulada, filtrado, metricas.

XXI






Autor(a)(es): Keyla Paulette Cedeno HermidaC.I. N0 0924425960


Tutor(a): Ing. Gary Reyes Zambrano, Msg.

ABSTRACT

At present, the advance of new technologies with regard to the location of a moving object, ithas been possible to observe a great increase in the data of a trajectory as well as the noise ofthem, accumulating many coordinate points, resulting in already have invalid and unnecessarydata. In the project, the process of evaluating the results that have been acquired from theexperiments carried out is carried out. In addition to studying the behavior of the Kalman filterwhen it is applied to the simplification algorithms (Douglas Peucker and TD-TR) of linear andnon-linear trajectories (GPS). For this, 5 sets of databases were used, both real and simulatedcircular for testing purposes. For the validation of the results in our thesis, 3 types of metricswere evaluated, such as: execution time, margin of error and compression ratio. We concludedthat statistical methods of the mean and standard deviation should be applied, where favorableresults were obtained with the Kalman filter applied to the TD-TR algorithm, but we could alsoobserve that at runtime the Douglar Peucker algorithm stands out many more in the research.

Key words: simplification, noise, simulated, filtering, metrics.

XXII

INTRODUCCION

Sin duda la tecnologıa ha llegado a formar parte de nuestra vida y cada dıa que pasa se

va convirtiendo en una herramienta de trabajo muy necesaria para todos, pero, ademas de todo

lo que ofrece el mundo tecnologico, uno de los campos que a diario se presenta necesario es el

de las trayectorias GPS, que a manera de estudio consta de varios subtemas muy importantes

para el funcionamiento optimo. La presente investigacion, se basa en la problematica que se

presenta al filtrar datos de trayectorias vehiculares. Al obtener los resultados de los algoritmos

de simplificacion, se observa que el algoritmo cumple con su funcion y se presentan trayectorias

comprimidas basadas en la informacion que se obtuvo del conjunto de datos, pero, al aplicar

el filtro de Kalman a estos mismos algoritmos, se pudo observar una diferencia favorable, ya

que el filtro suaviza la ruta de tal manera que se apega mas a un resultado exacto, filtrando

la informacion del conjunto de datos (latitud y longitud) usadas para la experimentacion y

demostracion de resultados diferentes, que, se obtienen con y sin el filtro de kalman.

El filtro es un procedimiento matematico que opera por medio de un mecanismo de

prediccion y correccion. En esencia el algoritmo pronostica el nuevo estado a partir de su esti-

macion previa anadiendo un termino de correccion proporcional al error de prediccion, de tal

forma que el ultimo es minimizado estadısticamente.(Ramırez, 2003)

1

CAPITULO I

PLANTEAMIENTO DEL PROBLEMA

Descripcion de la situacion problematica

Ubicacion del problema en un contexto

En la actualidad el desarrollo y el avance de nuevas tecnologıas con lo que respecta a la

localizacion de un objeto en movimiento, se ha podido observar un gran incremento de los datos

de una trayectoria al igual que el ruido de ellas, acumulando muchos puntos de coordenadas

llegando a redundar y a tener datos invalidos e innecesarios.(Zambrano y Veliz, 2016)

En las “Big Data” se podra visualizar y estudiar lo que son trayectorias lineales, que se

encuentran estructuradas por una base de coordenadas que estas mismas son producidas por la

actividad que genera un cuerpo que al momento de agruparse, establecera una lınea recta, las

trayectorias no lineales se definen como el movimiento de un cuerpo en diferentes rectas y que

al agruparse formaran curvas, parabolas, cırculos o elipse.

Se debe tener en cuenta que el gran almacenamiento de informacion en los que se

considera como “Big Data” son datos extremadamente utiles para el analisis, pero que no se

encuentra disponibles, al menos inicialmente de una manera estructurada, ya sea por la alta

velocidad con que son producidos o por los mecanismos a traves de los cuales son genera-

dos. Siendo ası, mas alla de la gran cantidad de informacion disponible hoy, las Big Data se

relacionan directamente a la capacidad de manipular y analizar datos multi-estructurados no

relacionados, que requieren de una interaccion rapida y adaptable.(Aguilar, 2016)

Debido a la gran cantidad de almacenamiento los algoritmos de simplificacion de tra-

yectorias vehiculares, permitiran disminuir el gran consumo de espacio logico en la base de

datos lo cual favorece para tener procesos mas rapidos en muy poco tiempo.

2

Deficiencia en la reduccion de ruido en los algoritmos de simplificacion de lıneas cuando

se procesan trayectorias GPS con caracterısticas diferentes.

Situacion conflicto nudos crıticos

Se presenta problema con el ruido en grandes conjuntos de “Big Data” que dificulta el

procesamiento y analisis para lo cual, la solucion a esto es encontrar un modelo rentable de

almacenamiento y procesamiento de datos que garantice datos especıficos y de calidad.

Aunque como se conoce el ruido se encuentra presente de una forma muy caracterıstica

en cualquier tipo de sistema teniendo esto en cuenta, se conoce que es la razon de que en varias

cosas se puede llegar a considerar muy difıcil hasta casi imposible eliminar totalmente el efecto

que es ocasionado por el ruido.

Debido a esto surge la necesidad de realizar investigaciones profundas acerca de la

compresion de trayectorias e investigaciones cientıficas asociadas a la reduccion de ruido. En

el filtro de Kalman, la necesidad es poder eliminar el ruido de una trayectoria trazada en una

ruta de la ciudad, para dar una suavidad en ella.(Ramırez, 2003)

Al filtro de Kalman se lo distingue como uno de los algoritmos fundamentales para

lograr valorar los sistemas dinamicos que son mostrados de manera estado-espacio. Es decir

que el sistema como se lo presenta resulta ser especificado por algunas variables a las cuales

se las nombra como estado, puesto que, esta misma abarca la informacion concerniente al

sistema a un punto cualquiera en el tiempo por completo. Teniendo en cuenta que esta misma

informacion tiene que dar acceso a la inferencia de la conducta del sistema anterior para con

esto lograr predecir la conducta o comportamiento que tomara en un futuro.

El filtro de Kalman se distingue mucho por la cualidad que posee de pronosticar en que

situacion de estado se encuentra un modelo tanto en el pasado, presente como en el futuro, aun

cuando la propia naturaleza exacta del sistema modelado se desconoce por completo.

Delimitacion del problema

Se procede a experimentar con los puntos de trayectorias proporcionadas de las bases

de datos escogidas para la optimizacion de resultados ineficientes y vacıos causados por las va-

riantes o no actualizaciones de datos. Limitando la efectividad en optimizacion de trayectorias.

3

Tabla 1

Delimitacion del problema

Delimitador Descripcion

Campo Estudio del filtro Kalman en trayectorias vehiculares

Area Investigacion

Aspecto Analisis del filtro Kalman.

Tema Analisis del filtro de KALMAN en algoritmos de sim-plificacion de trayectorias GPS lineales y no lineales.

Nota. La tabla refleja los delimitadores del problema en estudio y su respectiva descripcion detallandocada uno de ellos.

Evaluacion del problema

Los aspectos generales de evaluacion son:

• Delimitado: Influye demasiado en los resultados arrojados dentro de los experimen-

tos que limitan el uso de datos no optimos que ocasionan una influencia considerable

dentro de las trayectorias.

• Claro: Manejar grandes cantidades de informacion consume demasiados recursos

que son necesarios dentro de algun otro campo, el uso de herramientas y procesos

para este manejo ayuda en la segmentacion de los datos para un mejor estudio en la

toma de decisiones.

• Evidente: El analisis de Big data es la razon por la cual son utilizados diversos algo-

ritmos de optimizacion, el mal uso de estos provoca grandes problemas de resultados,

misma razon que al usarlos con poca experiencia se estarıa redundando en trayecto-

rias ineficientes o arrojandonos resultados mucho peores que los ya obtenidos sin el

uso de estos algoritmos.

• Concreto: El estudio y analisis del filtro kalman en bases de datos con puntos de

trayectorias GPS debe ser primordial para no caer en soluciones poco optimas que

ocasionen congestionamiento y una solucion poco eficaz.

4

• Relevante: Debido a la gran afluencia de datos y la gran cantidad de estudios gene-

rados dentro del campo existe un interes para lograr una efectividad en trayectorias

lineales y no lineales, de manera por el cual esta investigacion ayudara al inicio de

investigaciones con un enfoque mas comprensivo.

• Contextual: El punto se engloba en todo el contexto que conlleva el proyecto de

investigacion para que la universidad de Guayaquil tenga acceso a esta, ademas de

que se proporcionara ademas de un artıculo cientıfico en donde se lograra presentar

el proceso que se tomo para la investigacion.

• Factible: El estudio y puesta en practica del proyecto de investigacion, ayuda a pre-

venir problemas mucho mayores que de un inicio y danos a gran escala para diversos

campos empresariales, tanto economicos, de tiempo y recursos, por el mal manejo de

los algoritmos en Big Data.

Formulacion del problema

El estudio del proyecto ha evidenciado que existe mucho espacio en memoria usado

de las bases de datos que no es optima para una trayectoria de linealidad perfecta y debido a

la abundancia de puntos la necesidad de simplificar trayectorias por medio de algoritmos, han

hecho que se estudien y se investiguen sobre procesos que ayuden al manejo y uso de estas

Big Data que filtren la mejor informacion y los mejores puntos para obtener resultados que

beneficien.

Los problemas encontrados lograran solucionarse con el uso e integracion del filtro Kal-

man que permitira el manejo de grandes cantidades de puntos de trayectorias y su reduccion

del ruido optima.

5

Causas y consecuencias del problema

La dificultad que existe al medir cuan eficaz son los algoritmos de simplificacion de

lıneas en conjunto con el filtro de Kalman posee de ciertas consecuencias y casusas, que se

expresan a continuacion:

Tabla 2

Matriz de causas y consecuencias del problema

Causas Consecuencias

C1. Falta de evaluacion en los gru-pos de trayectorias.

E1. Estudio erroneo de los resultados arrojados por elfiltro.

C2. Uso de puntos redundantes entrayectorias lineales y no lineales.

E2. Un proceso lento y de una sobrecarga de espaciologico en la base de datos.

C3. Manejo inadecuado de algorit-mos de simplificacion en trayecto-rias lineales y no lineales

E3. Consumo elevado de recursos informaticos y re-bosamiento de capacidad de equipos

C4. No eliminar el ruido de una tra-yectoria trazada en una ruta de unagran ciudad.

E4. No da un suavizado en la trayectoria de una ruta.

Nota. La tabla refleja la lista de causas del problema en estudio con sus respectivas consecuencias luegode hacer un analisis causal preliminar.

Objetivos del proyecto

Objetivo general

Implementar el filtro de Kalman en algoritmos de simplificacion en lınea para mejorar

la reduccion del ruido en trayectorias GPS lineales y no lineales.

Objetivos especıficos

1. Elaborar el estado de arte y marco teorico acerca de la reduccion del ruido, filtros

de reduccion de ruido, filtro de Kalman, trayectorias lineales y no lineales.

2. Implementar y definir el modelo matematico para utilizar el filtro de Kalman en los

algoritmos de simplificacion en lınea identificados relevantes.

6

3. Experimentar con los algoritmos identificados y con 4 Conjuntos de datos (2 con

trayectorias lineales y 2 con trayectorias no lineales)

4. Validar los resultados obtenidos utilizando test estadısticos.

5. Elaborar un artıculo cientıfico.

Alcance del proyecto

En el proyecto se tomara en cuenta la investigacion de modelos matematicos y analisis

de filtro Kalman en los algoritmos referente a la disminucion de ruidos, teniendo en conside-

racion elementos o test estadısticos que ayuden a evaluar e identificar patrones para realizar

criterios con respecto a trayectorias en la ciudad de Guayaquil u otras ciudades con ayuda de

una base datos PostgreSQL que es un lenguaje de base de datos normalizado, utilizado por la

gran mayorıa de los servidores de bases de datos, que manejan bases de datos relacionales u

objeto-relacionales donde se muestre imagenes de trayectorias reales. (Sarrıa, s.f.)

La implementacion de un codigo de programacion en lenguaje R que es un entorno

de programacion para el analisis estadıstico y grafico de datos permitira realizar experimentos

y analisis de las diferentes bases de datos.(Avello Martınez y Seisdedo Losa, 2017). Ademas

de incluir formulas matematicas que permitan definir y demostrar si una trayectoria en cierto

tramo es lineal o no lineal.(Ibanez Asensio, Gisbert Blanquer, y Moreno Ramon, 2011)

Ademas se debera conocer el tipo de algoritmo Kalman apropiada para reduccion de

ruidos el cual se presentara en graficas para su respectivo experimentacion y estudio, el filtro

de Kalman “unscented” (UKF: Unscented Kalman Filter ) se puede considerar el resultado de

incorporar la UT al EKF para mejorar las aproximaciones que se hacen de los dos primeros

momentos de una variable aleatoria que resulta de propagar otra variable aleatoria (supuesta

gaussiana) a traves de una transformacion no lineal.(Pascual, 2004)

7

Hay que tener en consideracion que para la implementacion del algoritmo de filtro Kal-

man se deberıa tener un amplio conocimiento en el area de probabilidades, en especial con la

condicionalidad gaussiana que hace referencia a una generalizacion de una distribucion aplica-

da a un vector de infinitas variables (funcion), ası que la inferencia toma lugar en el espacio de

las funciones, de allı que el modelo es no parametrico, es decir, no se fija de antemano el numero

y la naturaleza de los parametros ademas como variables aleatorias, esto puede desarrollar una

limitante para su estudio.

Justificacion e importancia

En las trayectorias GPS se presentan problemas de desviacion GPS como tambien di-

versas fuentes de error, que podemos dividirlas tales como: localizacion en los satelites, en la

propagacion de las senales y en el receptor. Es decir, la trayectoria se desvıa del camino lo cual

provoca seguir el mismo recorrido, pero de manera menos precisa. (Lopez Valdes, 2010)

Lo cual ocasiona que el rendimiento en tiempo real al tratar de definir un ciclo y hacer

calculos con la tasa de depreciacion de los datos y montar un modelo de computacion en tiem-

po preciso influyan en los resultados que se obtengan de los analisis. Ademas, existen diversos

fenomenos que genera una gran cantidad de datos, lo cual por su extension dificulta el analisis

ya se con herramientas de aprendizaje.

Una de las maneras de reducir estas deficiencias en las big datos es con MapReduce

que es un modelo de programacion que se orienta a la implementacion de habilidades de pro-

cesamiento de variedades de conjuntos de datos que puede ser aplicado a una gran variedad

de tareas del mundo real. El modelo se lo utilizo en un principio por Google para resolver el

problema de ranking de paginas (“Page Rank”). El modelo se basa en los siguientes conceptos:

iteraciones sobre los datos de entrada, construccion de los pares clave-valor a partir de cada

pieza de entrada, agrupacion de los valores intermedios de acuerdo con las claves, iteracion

8

sobre los grupos resultantes y reduccion de cada grupo.(Hernandez-Leal, Duque-Mendez, y

Moreno-Cadavid, 2017)

La aplicacion de conocimientos en el desarrollo de algoritmos es de gran importancia,

el presente proyecto busca desarrollar alternativas en cuanto a simplificaciones de recorridos

y disminucion de ruidos con aplicaciones tales como modelos matematicos y algoritmos en

simplificacion de trayectorias GPS y programacion, se podra aplicar analisis de trayectorias

con filtro Kalman obteniendo resultados mas precisos y recursivos lo cual quiere decir que se

basa en estado de la actual posicion, velocidad, aceleracion.(Morales-Velazquez, Aparicio, y

Valdes, 2014)

El trabajo de investigacion estara en un perıodo de pruebas y verificacion de la misma,

lo cual hara una aportacion al repositorio investigativo de la Universidad de Guayaquil ademas

de beneficiar al desarrollo de conocimientos y formacion de estudiantes en diferentes areas

tales como programacion o geolocalizacion.

Limitaciones del estudio

La principal limitacion que se noto en la investigacion es el alcance que se podrıa darle

a los experimentos que se realizaran, por el uso de bases de datos con informacion antigua o con

pocos puntos de trayectorias, eso debido a los limitados recursos que obtuvimos para emplear-

los, ademas de que dicho problema de recursos y de informacion no actualizada representarıa

resultados ficticios, a diferencia de trabajar con trayectorias lineales actualizadas para quizas

mostrar un resultado real a algun problema cotidiano como serıa el flujo vehicular en horas de

congestionamiento.

9

CAPITULO II

MARCO TEORICO

Antecedentes del estudio

En los estudios realizados de los algoritmos de manejo de Big Data y en base al tema

investigado, se corroboro que algoritmos utilizados para el manejo de grandes datos de infor-

macion existen desde que el mundo se abrio paso al manejo de internet, lo cual comenzo a

generar grandes cantidades de datos, teniendo en cuenta que al igual que la sociedad, empresas

o entidades de informacion estudiaban soluciones acertadas para manejar dichos datos que se

centraban generando en masa a medida que lanzaban al mercado dispositivos tecnologicos para

mejora de empresas o de vida de la sociedad.

Cuando se habla de los sistemas de posicionamiento global en el ambiente social la

escases de conocimiento de lo que es y de que manera funciona es notable. El algoritmo de

simplificacion de lıneas fue escogido como uno de los principales procedimientos para de-

sarrollar, el cual se apoya en la eliminacion de la mayor cantidad de informacion y puntos

innecesarios.

Tomando en cuenta lo que se menciono, se eligio el filtro Kalman, un procedimien-

to matematico que actua por medio de un mecanismo de prediccion y correccion. En efecto,

el algoritmo predice el nuevo estado a partir de la evaluacion previa anadiendo un termino

de correccion proporcional al error de prediccion, de tal forma que el ultimo es minimizado

estadısticamente. (Pillajo y Sierra, s.f.)

10

Fundamentacion teorica

Para tener un enfoque general de ciertos temas los cuales son importantes conocer, es

idoneo presentar los conceptos y fundamentos de los cuales se encuentran basados, ya que,

contienen un alto grado de impacto para el desarrollo e implementacion del proyecto y que se

presentan a continuacion.

Sistema de Posicionamiento global

Mas conocido comunmente como GPS (Global Positioning System, en ingles) y como

su nombre lo indica es un sistema de localizacion que fue en primera instancia disenado por el

departamento de defensa de los EE. UU (USDOD, siglas en ingles) y puesto en uso en el ano

de 1995, con el unico objetivo de conocer la posicion, velocidad y tiempo de cualquier objeto

que se encuentre en el entorno del planeta.

El sistema necesita de 24 satelites que esten orbitando alrededor de la tierra y eso de

manera casi que obligatoria, ya que es el unico medio para que el sistema pueda determinar

datos de un objeto como: latitud, altitud y altitud, a traves de operaciones y calculos de las

coordenadas y por senales emitidas por los mismos. Considerando que no debe de estar el ob-

jeto en una zona especıfica, puesto que, al considerar el numero mınimo de satelites, se puede

determinar la ubicacion de cualquier objeto que se encuentre cualquier parte del planeta.(Fallas,

2002)

Trayectoria GPS

Estos son puntos producidos por objetos que se encuentren en movimiento, por lo ge-

neral estos puntos suelen ser de recorridos vehiculares. Lo mas destacado de la trayectoria

es que genera puntos continuos de la cualquier ruta que se haya seguido, permitiendo ası el

uso de esos mismos puntos para obtener mas conocimientos y realizar nuevos estudios sobre

los objetos en movimiento con las tecnicas de Clustering, que permitirıa agrupar puntos clave

del trafico vehicular o los recorridos que con mas frecuencia son utilizados por las personas

tomandolo como los mas optimos.(Campoverde, Mera, Escalante, y Carrasco, 2020)

11

Secuencia de puntos GPS (latitud, longitud)

Conformada principalmente por 2 componentes claves, las cuales son latitud y longitud,

mismas que serviran de apoyo para formar la trayectoria. Constan de posiciones que dividen su

trabajo. Norte-sur es la posicion del punto que viene dada por su valor de latitud, y, su longitud

el proceso que realiza es el de brindar informacion de su posicion este-oeste.

• Latitud es la medida del angulo formado por el plano ecuatorial con la lınea que

une a este punto al centro de la tierra, y que esta comprendido entre -90 grados y

90 grados por regla general, en la misma la ubicacion de hemisferio sur son para los

numeros negativos y su valor de latitud es de 0 grados en el Ecuador.

• Longitud basicamente contiene el mismo principio que la latitud, pero no podrıa

basarse en algo natural como lo tiene la latitud como referencia. Motivo por el cual

la referencia fue dispuesta arbitrariamente en el Meridiano de Greenwich el mismo

que atraviesa el “Real Observatorio de Greenwich” que se encuentra ubicado en las

afueras de la ciudad de Londres. Conociendo esto, la longitud de un punto es la me-

dida angular formada por el semiplano del eje de la tierra que cruza por el meridiano

de Greenwich y a su vez el semiplano del eje de la tierra que cruza por el punto.

(Astudillo Leon y Delgado Tello, 2012)

Pre-Procesamiento

Los dispositivos electronicos de hoy en dıa cuentan con posicionamiento de ubicacion y

capacidades de comunicacion remota e inalambrica, y no solo hablando de los celulares moviles

sino de todo dispositivo que ayuda a las personas a realizar tareas cotidianas, y, gracias a esto

logran guardar de manera local las ubicaciones en las que se encuentre al servidor, esto tambien

puede hacerse informando al servidor de sus ubicaciones de manera dinamica. En la actualidad

existe una gran demanda de ubicacion de objetos que se encuentren en movimiento de diversas

funciones basados en la ubicacion(LBS), dentro de las cuales encontramos los servicios de

datos de trafico, la administracion de flotas, la logıstica de transporte, los juegos que hoy en dıa

son pensados y desarrollados con ubicaciones, redes sociales que exigen y dependen de mane-

12

ra obligatoria de que se active la ubicacion puestos que para poder realizar ciertas funciones

dependen de la misma.

Los DBA o conocidos como administradores de bases de datos han realizado diversas

investigaciones para poder respaldar estos datos, ya que ellos son los mas conocedores del tema

en cuestion, acompanados de estudios sobre la ejecucion y desarrollo de conjuntos de datos de

objetos moviles(MOD).

El tener una toma de la trayectoria que ejecuta de manera exacta y de todo el pasaje

(camino que recorre un objeto en movimiento a traves del espacio en funcion del tiempo) com-

pleto de un objeto en movimiento es muy complicado ademas de costoso, ya que hoy en dıa

los mecanismos y hardware para obtener y almacenar en ellos los datos son muy limitados, y

, es por eso que para poder tener el movimiento continuo de un objeto se lo hace de manera

aproximada mas no exacta como puntos de ubicacion, es decir de manera superficial. Por tal

motivo mientras la trayectoria ofrezca muchos mas puntos se podra obtener un resultado mucho

mas preciso a comparacion de que si a la trayectoria se le extrajera pocos puntos.

Ahora bien, tomando lo anterior en cuenta se debe de realizar varios muestreos para

obtener muchos mas puntos y que los resultado sean exactos, pero al hacerlo se obtendrıan

grandes cantidades de datos que conllevara a realizar gastos exuberantes en infraestructura

como almacenamiento, comunicaciones y el mismo procesamiento de estos datos.

Las trayectorias tienen la posibilidad de acoplarse con un filtrado para lograr disminuir

el ruido existente y valuar algunas propiedades como lo son la velocidad y direccion, ya que las

trayectorias de manera general son medidas con un sensor, que contiene algun error, incluidos

valores atıpicos momentaneos. Para eso existen ciertas tecnicas que podrıan disminuir estos

errores como el filtrado medio y mediano, adicional a eso filtros como Kalman y el filtro de

particular podrıan brindar estimaciones de errores sobre los parametros de velocidad y direc-

cion.

Las ubicaciones de los objetos en movimiento rastreados en estos sistemas, se informan

al servidor de ubicacion de acuerdo a los esquemas de informes estipulados. las aplicaciones

LBS envıan consultas al servidor de ubicacion para recuperar objetos de interes en movimiento

(ası como sus atributos, como ubicaciones y otros fenomenos) para cumplir diversas necesida-

13

des de la aplicacion. (Zheng y Zhou, 2011)

Trayectoria Generacion de datos

Una trayectoria es la ruta que toma un objeto en movimiento a traves del espacio en

funcion del tiempo, es decir que una serie de puntos de ubicacion con marca de tiempo podrıa

ser capturado. Y las cuales son denotadas como x1, y1, t1, x2, y2, t2, ..., xN, yN, tN donde xi,

yi representan las coordenadas geograficas del objeto en movimiento en el momento ti y N, es

el numero total de elementos de la serie.

Las coordenadas geograficas de tiempo pueden ser muestreadas al azar por un objeto

en movimiento, lo siguiente seria comprobar si dicho objeto tendrıa que transferir todos sus

datos de trayectorias muestreados al servidor de ubicacion quien es el servidor el encargado

de realizar la transferencia a la base de datos de objetos moviles, de esto claro, dependera los

requisitos de la aplicacion.

Al estar el objeto en movimiento ocurre la obtencion de datos, se supone, que dichos

datos de ubicacion que contiene son de gran precision. Por su parte se puede permitir un cierto

grado de error de las aplicaciones en funcion a sus requisitos, entonces, no se espera que la

precision sea alta de los datos en el servidor de ubicacion a comparacion como la del objeto en

movimiento.

La finalidad es disminuir la carga excesiva de comunicacion y almacenamiento de la

representacion de datos de la trayectoria sin que se vea en peligro la precision de la nueva

representacion de datos de la trayectoria. La propuesta de estas tecnicas es obtener en primer

lugar, todos los puntos de datos de ubicacion que han sido muestreados para luego comprimir

ese conjunto de datos para ir descartando los datos que son redundantes.(Zheng y Zhou, 2011)

Metricas de rendimiento y medidas de error

Se debe de tomar en cuenta que, para el tipo de tecnicas para reduccion de los datos en

lınea, la posicion actual del objeto debe de ser transmitida a la base de datos si es que la posicion

que se comento con anterioridad se encuentra en un gran error que dependera de la aplicacion.

Por esa razon, hay necesidad de encontrar metricas y medidas de error apropiadas para uso

en algoritmos y la evaluacion de su desempeno. A continuacion, se muestran las principales

14

metricas de rendimiento que se utilizan a menudo para evaluar la eficiencia y eficacia de estas

tecnicas de reduccion de datos de trayectoria.

• Tiempo de procesamiento: el tiempo de ejecucion tomado en el algoritmo de reduc-

cion de puntos en las trayectorias.

• Razon de compresion: la relacion entre el tamano de una trayectoria simplificada y

el tamano de su trayectoria original para indicar el porcentaje que se ha comprimido

o simplificado.

• Margen de error: indica el grado de desviacion de la trayectoria afectada con la

trayectoria original despues del proceso de simplificacion.

La medida de error y la tasa de compresion son utilizadas para determinar que tan

optimas son las tecnicas determinadas. Sabiendo que podrıa superar el intercambio entre las

metricas de eficacia. Debido a esto, estas tecnicas de reduccion de trayectorias se comparan

en un grafico de dichas metricas para localizar el frente de Pareto. Se puede observar que hay

espacio para definir mas medidas de error totalmente diferentes, mientras que el concepto de la

tasa de compresion es muy facil. En el resto de la seccion se cuestiona dos medidas de error,

cuando se conoce la distancia euclidiana perpendicular y la distancia euclidiana sincronizada en

el tiempo, las cuales son utilizadas e la literatura ya que tienen una implicacion que especifica

la imposicion permitida por la aplicacion y el rendimiento.

Tecnicas de compresion por lotes

Puesto que una trayectoria contiene una sucesion de puntos de datos de ubicacion mar-

cados con el tiempo, el algoritmo de compresion por lotes tiene como objetivo generar una

trayectoria aproximada descartando a su vez algunos puntos de ubicacion con algun tipo de

error que no influye en casi nada de la trayectoria original. Esto es similar al problema de

generalizacion de lıneas. Los trabajos realizados sobre la generalizacion de lıneas cartograficas

tienen como objetivo derivar datos de mapas en menor escala a partir de datos de mayor escala

y granularidad. El resultado, es de que se podrıa utilizar para disminuir el numero de puntos de

ubicacion en trayectorias y de esa manera ahorrar el espacio de almacenamiento.

15

-Algoritmo de Douglas-Peucker

El algoritmo de Douglas Peucker es calificado como el de mejor posicion a comparacion

de otros algoritmos. Propuesto por David Douglas Y Thomas Peucker en el ano de 1973, es un

algoritmo muy utilizado y conocido para emplear software de cartografıa y reduccion de lıneas.

Fundamentado en la localizacion de puntos crıticos partiendo de una tolerancia lineal,

los puntos crıticos formaran parte de la lınea simplificada y seran los encargados de que vayan

alcanzando una distancia perpendicular mucho mas grande a comparacion de la lınea inicial

que fue considerada de manera progresiva, esto porque los resultados del algoritmo deben ser

superior a la tolerancia dada inicialmente.(Garcia Tarira, 2017)

-Algoritmo de Visvalingam-Whyatt

Generalmente utilizado en el metodo de generalizacion, el proceso estara eliminando

los puntos menos significativos a medida que el proceso vaya avanzando. El algoritmo es util

cuando lo que se requiera sea disminuir el volumen del grafico. Este algoritmo consiste en

que se establezca una zona de tolerancia que sera la que sirva como area de efectividad, por

detras de esta, los puntos que se encuentren en estas seran eliminados, si sus correspondientes

triangulos tengan un area menor que la tolerancia dada.

El primer proceso se calculara las areas de todos los triangulos y se ira eliminando el

punto con menor area de efectividad, por consiguiente se realiza el calculo nuevamente de todas

las areas y se toma el mismo proceso anterior, se elimina el punto con menor area de efectividad

y ası el proceso continua de manera progresiva hasta que el numero de areas existentes consten

cada un valor mayor a la tolerancia estipulada.(Visvalingam y cols., 2016)

-Algoritmo TD – TR

El algoritmo de TD TR es basicamente la modificacion de Douglas Peucker en el cual

se aumenta el factor tiempo. Presentado por primera vez por dos grandes mentes como lo fue

Merarnia y Rolf, en su libro conocido como: tecnicas de compresion de espacio temporal para

objetos en movimiento.

Aunque el algoritmo tenga relacion con Douglas Peucker no es igual, ya que, la sim-

16

plificacion que con el algoritmo de Douglas Peucker se realiza solo con la posicion del objeto

tomando en cuenta los datos de latitud y longitud, esta al ser la modificacion de Peucker, incluye

un metodo para medir la distancia en relacion al tiempo que con llevo realizar un recorrido de

un punto “A” a un punto “B” en la trayectoria.(Meratnia y Rolf, 2004)

-Algoritmo Lang

Se define una region en la cual se deba de realizar la busqueda la misma que tendra

un tamano fijo, teniendo en cuenta que los primeros y ultimos puntos que se encuentren en

los lımites de la region seran parte del segmento inicialmente definido, el motivo por el cual

se define el segmento es que sera posteriormente usado para realizar el calculo de la distancia

perpendicular a cada punto intermedio.

Teniendo en cuenta que se debe de respetar el valor de tolerancia especificado, los valo-

res de la distancia ya calculados deben ser menores a la tolerancia porque si, en el caso llega a

superar, la region en la que se realiza la busqueda reducira su espacio eliminando ası su ultimo

punto de la region anterior y ası lo hara sucesivamente cuando el valor supere la tolerancia,

hasta cuando los calculos de todas las distancias sean menores a su tolerancia o dentro de la

region no existan puntos intermedios ya que si existieran serian eliminados de igual manera

definiendo una nueva region para busqueda tomando como inicio el ultimo punto de la region

de busqueda antigua para esa nueva region.

Algoritmo de compresion por lotes

Estas tecnicas describen en primera instancia un subconjunto de los puntos de ubica-

cion en la trayectoria original solo como una aproximacion. El tipo de algoritmos, el error

de aproximacion, medido por variantes de distancias euclidianas como la distancia euclidiana

perpendicular o la distancia euclidiana sincronizada en el tiempo, se utilizan para seleccionar

puntos de datos que representan la trayectoria original lo mas cerca posible.

Al argumentar que un punto de datos debe incluirse en la trayectoria aproximada siem-

pre que revele cambios en el curso de una trayectoria y que se pueda predecir la ubicacion de

un punto de datos entrante a partir del movimiento anterior, donde el punto de datos se puede

descartar de forma segura sin una perdida significativa de precision, ya que aporta poca infor-

17

macion. Es decir, existe una gran probabilidad de que un objeto en movimiento se mueva a la

misma velocidad y direccion con algunos cambios menores durante algun tiempo. Eso quiere

decir que, la ubicacion actual de un objeto en movimiento por lo general se puede predecir

a bajo costo utilizando la velocidad, la direccion y el tiempo desde que fue por ultima vez

observada la ubicacion.

-Algoritmo de Bellman-Ford

Desarrollado por Richard Bellman, Samuel End y Lester Ford. El algoritmo determina

la ruta mas corta que exista desde un punto a otro para lo cual es necesario un grafo de las

cuales sus aristas posean pesos. Comparado con el algoritmo de DIJKSTRA ya que brinda la

misma solucion de determinar la ruta mas corta y hasta en menor tiempo en comparacion con

Bellman- Ford, pero, la gran diferencia que existe entre estos 2 algoritmos es de que Bellman-

Ford al permitir pesos, se puede tener y operar con valores negativos y ası detectar la existencia

de un ciclo negativo.

El algoritmo inicia con un vertice de origen que debera ser ingresado, a diferencia de

Dijkstra que utiliza un metodo que abarca demasiado para seleccionar vertices de menor peso

y poder actualizar sus distancias por medio el paso de relajacion.

Bellman-Ford de manera mas optima relaja todas las aristas y lo hace —V— -1 veces,

siendo —V— igual al numero de vertices del grafo. (Renteria Reyes y Romero Oviedo, 2013)

Filtrado de trayectoria

Las trayectorias espaciales nunca llegan a ser precisas debido al ruido del sensor y otros

factores. En ocasiones ese error es aceptable, como cuando se usa GPS para identificar en que

ciudad se encuentra una persona. En otros casos, se puede aplicar diferentes tecnicas de filtrado

a la trayectoria para suavizar el ruido y potencialmente disminuir el error en las mediciones. En

el apartado se explica y demuestra algunas tecnicas de filtrado convencionales utilizando datos

de muestra. Algo de tener en cuenta de que el filtrado en algunas ocasiones no es necesario, es

mas en ocasiones raras se las utiliza para datos GPS. El filtrado es de mayor importancia en

situaciones en las que los datos de la trayectoria son en particular muy ruidosos, o cuando es

necesario derivar otros valores de ellos, como velocidad o direccion.

18

- Filtro de media

Es un filtro de ventana de clase lineal, que suaviza la senal o la imagen. El filtro trabaja

como un filtro pasa-bajas. La idea de un filtro de media es simple: reemplazar el valor de cada

pıxel en una imagen con el valor de la media (promedio) de sus vecinos, incluido el mismo.

Esto tiene el efecto de eliminar el valor de pıxel que no es representativo de su vecindad. El

filtro presenta ciertas desventajas: es bastante sensible a cambios locales y puede crear nuevas

intensidades de gris o de colorque no aparecıan antes en la imagen. A su vez, cuando el filtro se

topa con un borde, comienza a interpolarnuevos valores para los pıxeles en el borde y esto difu-

minara ese borde. Esto puede ser un problema si se requieren en la salida bordes delgados(Villa

y Yanez, 2017)

- Filtro de mediana

El filtro evalua cada pixel de la imagen y la reemplaza por la mediana de los pixeles

que se encuentran a su alrededor(vecinos). La mediana se la calula ordenando los valores de

los pixeles que se encuentren alrededor y seleccionando al que queda en medio. Cabe destacar

que es muy eficaz al estar removiendo el ruido mientras preserva los bordes.

El tipo de filtro no es un filtro lineal, aunque da muy buenos resultados en caso de ruido

de sal y pimienta, puesto que es independiente de aquellos valores que son significativamente

diferentes a los valores tıpicos de los pixeles vecinos.(Villa y Yanez, 2017)

- Filtro Kalman

Filtros como es el de Kalman y el de partıculas moldean el ruido de medicion ası tam-

bien como la dinamica de trayectoria a comparacion que los filtros que no emplean ningun

modelo de trayectoria como lo son el filtro de media y mediana. En Kalman, el proceso de

suavizar las mediciones de la trayectoria de cualquier objeto que se mueva por el aire expuesto

unicamente por la gravedad, como podrıa ser un balon de futbol es un ejemplo muy simple. Ya

que al realizar las mediciones de donde se encuentre a pelota son ruidosas al aplicarlo desde una

camara, aunque se podrıa dar ciertas restricciones a la trayectoria del objeto que en el caso serıa

la pelota utilizando leyes de fısica que para el conocedor del tema resultarıan faciles. El filtro

19

kalman funciona de manera de estimaciones que las mismas son basadas en algunos principios

de estados de movimiento que son de un orden mayor como el de la velocidad.

Kalman no es mas que un conjunto de ecuaciones matematicas que proporcionan una

solucion recursiva optima, a traves del metodo de mınimos cuadrados. El fin de resultado es de

calcular un estimador lineal optimo del estado de un sistema de t basado con la informacion que

se encuentra disponible en t-1 ademas de actualizar la informacion que se encuentra disponible

adicionalmente en t estas estimaciones lo que el filtro suponiendo que el sistema podrıa ser

explicado utilizando como herramienta un patron estocastico lineal, en el cual el error que esta

asociado tanto como en el sistema como en la informacion adicional que se acopla al mismo es

poseedor de una distribucion normal con media de valor cero y una varianza determinada.

Esta solucion es bien recibida ya que el filtro ejecuta el proceso de combinacion de la

informacion que se ha observado con lo ya sabido de manera previa acerca del comportamiento

del sistema para poder producir la estimacion del estado esperando que el error sea minimizado

de manera estatica. Como para acotar el termino recursivo se define como el proceso de recal-

cular la solucion cada vez y cuando que una nueva observacion o medida sea incorporada en el

sistema.(Ramırez, 2003)

- Las variables del Filtro Kalman

El filtro de Kalman trabaja principalmente con dos tipos de variables:

Vector de Estados Estimados:

Los componentes del vector de estados estimados, incluyen las siguientes variables:

• Variables de interes: entre las que se requieren en esta encontramos la posicion,

aceleracion, la razon de cambio en la aceleracion, entre otras.

• Variables no intrınsecas: son por las que no se tiene algun tipo de interes, pero

son usadas en el proceso de estimacion por ende son muy necesarias. Estas variables

podrıan incluir: los errores por disponibilidad selectiva de los satelites GPS, ademas

de que no se necesita conocer valores, por lo general. Pero, en el proceso si se esta

obligado a calcularlos para lograr optimizar la estimacion que brinda el receptor.

20

• Variables dinamicas: son las definidas para algunas aplicaciones que son especıfi-

cas, como medidas para algunos sensores, como por ejemplo un acelerometro, ya que

el filtro podrıa tener componentes de aceleracion y rotacion angular.

Matriz de Covarianza, medicion de la incertidumbre en la estimacion :

Estas ecuaciones son usadas para propagar el modelo de la matriz de covarianza, y manejar la

incertidumbre, tomando en cuenta como el ruido de los sensores y la dinamica incierta, contri-

buyen en la incertidumbre total para el calculo de la estimacion de los estados del sistema.

El Algoritmo de Filtro Kalman

Kalman estima el proceso que con anterioridad fue ejecutado, utilizando un tipo de

control de retroalimentacion, es decir, realiza una estimacion en algun momento en el tiempo y

ahı es cuando obtiene la retroalimentacion por medio de datos observados.

Esta definicion permite prever las ecuaciones utilizadas para poder derivar el filtro de

Kalman y estas se dividen en dos grupos. El grupo que actualiza el tiempo o ecuaciones de

prediccion y el grupo que actualiza los datos observados o simplemente ecuaciones de actuali-

zacion. El grupo que se encuentra en la primera posicion es la encargada de que se ejecute la

planificacion de un estado en el instante t teniendo en consideracion el estado en el instante t-1,

ademas de la nueva mejora de la matriz.

Como segundo grupo en cambio son los encargados de la retroalimentacion, mas senci-

llo de definirlo es que incorpora una nueva informacion dentro de la estimacion que estaba con

anterioridad con lo que Se logra alcanzar una valoracion excelente del estado.

Las formulas que ayudan al proceso de actualizacion del tiempo se podrıan nombrar

tambien como formulas de pronostico, en cambio las formulas que incorporan informacion

nueva se las conoce comunmente como formulas o ecuaciones que corrigen informacion, es

decir de correccion.

En efecto el algoritmo de estimacion final se la podrıa definir como un algoritmo de

pronostico que corrige para poder resolver cantidades de problemas. El proceso para lograr

implementar el filtro de Kalman es el que se presenta a continuacion:(Pillajo y Sierra, s.f.)

El proceso para implementar el filtro de Kalman es el siguiente:

21

• Construir el modelo: Como primera accion se fabrica un modelo, el mismo que

tendra relacion con las trayectorias que se van a analizar.

xk = Axk−1 + Buk + wk−1 (1)

xk: Vector de estado

ukk: Vector de control (acciones que aplicamos a la

dinamica del sistema para que se mueva)

k =k−1: Los subındices nos indica el instante de tiempo

al que se refiere el vector

A: matriz de estado

B: matriz de control

ukk: Tamano de la muestra

Necesitamos tambien una ecuacion de medicion:

zk = Hxk + Vk (2)

zk: La informacion de nuestros sensores, vector que trae

la informacion de los sensores.

xk: Variables de estado

Vk: Ruido de medicion

Se brindaran variables aleatorias wk y vk las cuales seran las que representen algun

error que se tenga en el proceso y de la medida cada uno con su variable respectiva.

Estas variables se las asume como independientes, es decir que no dependan la una

de la otra, la cual es el ruido blanco y la division de probabilidad normal:

p(w) N(0,Q) (3)

22

p(v) N(0,R) (4)

Q seria la matriz de covarianza del ruido propia del proceso y R es la covarianza del

tamano, que pueden o no tener un cambio en el tiempo, pero en general se asumen

que estas son constantes.

La matriz A se asume de una dimension NxN y relaciona el estado en el periodo

previo t−1 con el estado en el momento t. La matriz H de dimension MxN relaciona

el estado con la medicion Zt.

Estas matrices pueden cambiar en el tiempo, pero en general se asumen como cons-

tantes.(Miranda Gallegos, 2017)

• Actualizacion del tiempo (Prediccion):Son responsables de la proyeccion del es-

tado al momento k tomando como referencia el estado en el momento k − 1 y la

actualizacion intermedia de la matriz de covarianza del estado.

Proyectar el estado:

x∗k = Axk−1 + Buk (5)

Proyectar el error de covarianza:

P∗t = APk−1At + Q (6)

Ecuaciones de prediccion o actualizacion del estado y de la covarianza del error de

prediccion.

La matriz de covarianza inicial puede ser la matriz identidad.

• Actualizacion de medicion (Correccion):Estas son los encargados de que se tome

en cuenta la informacion que ha sido actualizada, es decir, que anexan informacion

actualizada a la estimacion efectuada con anterioridad para lograr una estimacion

optima del estado.

23

Computar la ganancia de Kalman:

Kk = P−k HT (HP−k HT + R)−1 (7)

Actualizar el estimado vıa zk:

Xk = X−k + Kk(zk − Hx−k) (8)

Actualizar el error de covarianza:

Pk = (1 − KkH)P−k (9)

La correccion comienza con el calculo de la ganancia, a continuacion realiza la esti-

macion a posterior y finalmente actualiza la matriz de covarianza a posterior.

24

Figura 1

Vision completa del Filtro Kalman

Elaborado: Keyla Cedeno, Alexander Mite.Fuente: (Ramırez, 2003)

- Filtro de Kalman Extendido

La funcion de el filtro es el de resolver el problema de la estimacion del estado que es

generado por un sistema no lineal que utiliza la expansion de la serie de Taylor que aproxima las

ecuaciones no lineales de estado y de observacion, sobre el valor actual estimado del estado de

igual manera provee un estimado de la varianza mınima del estado que esta basado en aquella

informacion estadıstica sobre el modelo.

El filtro de Kalman extendido, depende demasiado de la aplicacion especıfica pese a la

estabilidad y el desempeno del filtro de Kalman extendido. La eleccion es fundamentada en el

hecho que en general para sistemas no lineales, no hay un filtro de dimension finita.

Que logre resolver el problema de filtrado optimo de manera similar al filtro Kalman en

25

el caso lineal Gaussiano y el metodo de aproximacion mas accesible y mas sencillo de manejar

el problema del filtrado no lineal es precisamente el filtro de Kalman extendido.(Quintero y di

Sciascio, 2005)

- Filtro de Partıculas

El filtro de partıculas es similar al filtro de Kalman, ambos utilizan un modelo de me-

dicion y un modelo dinamico. El filtro de Kalman gana eficiencia asumiendo modelos lineales

(multiplicacion de matrices) mas ruido gaussiano. El filtro de partıculas relaja estas suposi-

ciones para un algoritmo mas general, aunque generalmente menos eficiente. Pero, como de-

muestran Hightower y Borriello, los filtros de partıculas son practicos para rastrear incluso en

dispositivos moviles. El filtro de partıculas recibe su nombre del hecho de que mantiene un

conjunto de ”partıculas”, cada una de las cuales representa una estimacion de estado. Se genera

un nuevo conjunto de partıculas cada vez que se dispone de una nueva medicion. Por lo general

hay cientos o miles de partıculas en el conjunto representan la distribucion de probabilidad de

estados posibles.

26

Hipotesis / Preguntas cientıficas a contestarse

¿La reduccion del ruido que realiza el filtro Kalman, mejora el rendimiento de los algo-

ritmos de simplificacion de puntos ?

Variables de la investigacion

En la investigacion que se presenta se llego reconocer las variables presentadas a conti-

nuacion que fueron escogidas:

Variable independiente: Coordenadas geograficas (latitud, longitud y tiempo) aplicando

el filtro de Kalman en algoritmos de simplificacion.

Variable dependiente: Metricas de rendimientos, razon de compresion y margen de

error.

Definiciones conceptuales

- Big Data

“Se refiere a las herramientas, los procesos y procedimientos que permitan a una orga-

nizacion crear, manipular y gestionar conjuntos de datos muy grandes y las instalaciones de

almacenamiento.” (Camargo-Vega, Camargo-Ortega, y Joyanes-Aguilar, 2015)

- Software Libre

“Es aquel que puede ser distribuido, modificado, copiado y usado; por lo tanto, debe

venir acompanado del codigo fuente para hacer efectivas las libertades que lo caracterizan.”

(Stallman, 2004)

- Sistema Gestor de Base de Datos

“Un sistema gestor de bases de datos o SGBD(aunque se suele utilizar mas a menudo

las siglas DBMS procedentes del ingles, Data Base Management System) es el software que

permite a los usuarios procesar, describir, administrar y recuperar los datos almacenados en una

base de datos.” (Cabello, 2010)

27

- Algoritmo

Un algoritmo es un conjunto ordenado y sistematico de reglas donde operaciones logi-

cas permiten realizar calculos para encontrar la solucion a un tipo de problema en concreto.

- Ruido

“El termino “ruido” admite dos interpretaciones segun se considere el punto de vista

fısico-objetivo o perceptivo-subjetivo. La primera se refiere al hecho de poseer un espectro

frecuencial continuo, es decir que contiene todas las frecuencias audibles, en contraposicion

con los sonidos tonales o pseudotonales que poseen solo un conjunto discreto de frecuencias

constitutivas. La segunda expresa simplemente que es “sonido no deseado”. No necesariamente

el hecho de ser “no deseado” implica que se lo rechace o que automaticamente produzca efectos

negativos. “No deseado” solo implica que no se lo busca especialmente, que no hay intencion

de escucharlo por sı mismo.” (Miyara, Pasch, Cabanellas, y Yanitelli, 2005)

- Ecuaciones

La ecuacion esta conformada por la igualdad en el cual se manifiesta como mınimo una

interrogante que debera ser mostrada al momento en que se resuelva el ejercicio.

- Desviacion Estandar

Presentada como en general la raız cuadrada de la varianza de la poblacion en especifica

o tambien de alguna variable aleatoria que este representada. (Espejo, 2017)

- Lenguaje de programacion R

R es un lenguaje de programacion de ordenadores dotado de un numero elevadısimo

de funciones matematicas y estadısticas y, sobre todo, graficas. El hecho de estar basado en

un lenguaje formal de ordenadores es lo que le da su tremenda flexibilidad. (El programa R,

herramienta clave en investigacion, 2017, pag. 18) Segun Gentelman el cual es considerado

uno de los padres de R, hay muy buenas razones para preferir R sobre otros lenguajes, funda-

mentalmente por sus buenos algoritmos estadısticos, la alta calidad de sus rutinas numericas, la

excelente integracion con herramientas de visualizacion de datos, la reproducibilidad y, sobre

28

todo, su gran capacidad de interactuar con otros lenguajes y de crear nuevas estructuras de

datos. (Turcotte y Vitek, 2019)

Paquete DLM

¨Los modelos de espacio de estados proporcionan una clase muy rica de modelos pa-

ra el analisis y pronostico de datos de series de tiempo. Se utilizan en un gran numero de

areas aplicadas fuera de las estadısticas, como econometrıa, procesamiento de senales, geneti-

ca, dinamica de poblaciones. Modelos lineales dinamicos (DLM) son una clase particular de

modelos de espacio de estados que permiten muchas de las inferencias relevantes, debe lle-

varse a cabo exactamente utilizando el filtro de Kalman, al menos en el caso de un modelo.

Al mismo tiempo, son lo suficientemente flexibles para capturar las caracterısticas principales

de una amplia gama de diferentes datos. La estimacion de parametros desconocidos en un

DLM requiere tecnicas numericas, pero el filtro de Kalman se puede utilizar en el caso como

un bloque de construccion para evaluar la probabilidad funcion o simulando los estados no

observables.”(Petris y An, 2010)

- PostgreSQL

PostgreSQL es un servidor de base de datos objeto relacional libre, ya que incluye ca-

racterısticas de la orientacion a objetos, como puede ser la herencia, tipos de datos, funciones,

restricciones, disparadores, reglas e integridad transaccional, liberado bajo la licencia BSD.

Como muchos otros proyectos open source, el desarrollo de PostgreSQL no es manejado por

una sola companıa, sino que es dirigido por una comunidad de desarrolladores y organizacio-

nes comerciales las cuales trabajan en su desarrollo, dicha comunidad es denominada el PGDG

(PostgreSQL Global Development Group).

29

CAPITULO III

METODOLOGIA DE LA INVESTIGACION

Modalidad de la investigacion

En la ejecucion de la investigacion propuesta se realiza el estudio del filtro de Kalman

con los algoritmos de simplificacion como lo son Douglas Peucker y TD-TR, calculando los

diversos parametros tal como la razon de compresion, tiempo de ejecucion y margen de error, de

las diferentes bases de datos que contienen trayectorias GPS con informacion real en el caso de

Beijing, Brasil y California, debido a que el tipo de informacion es de caracter publico y cuenta

con informacion legıtima recolectada por dispositivos GPS.Ademas de datos de trayectorias

circulares simuladas en el caso de Guayaquil y Quito que por razones de estudio y experimen-

tacion se procedio a crearla con datos del programa Google Earth Pro como MapSource ambos

programas gratuitos.

La experimentacion que se presenta radica en la seleccion de una base de datos ademas

de analizar y estudiar el comportamiento que tendra con el filtro de Kalman y estos mismos

datos aplicar los diferentes algoritmos de simplificacion y ası en base a resultados determinar

cual es la mejor manera de obtener los datos con una mejor compresion.

Tipo de investigacion

En el actual trabajo de investigacion se utilizara la investigacion de tipo experimental,

porque resulta mas apropiada al momento de obtencion y comparacion de los resultados.

30

Investigacion experimental

La investigacion experimental es un proceso que consiste en someter a un objeto o gru-

po de individuos, a determinadas condiciones, estımulos o tratamiento (variable independiente),

para observar los efectos o reacciones que se producen (variable dependiente)(Arias, 2012)

Diseno metodologico de la investigacion

El trabajo se desarrolla a partir de un conjunto de datos que contienen trayectorias GPS

que fueron obtenidas a partir de dispositivos que cumplen con dicha funcionalidad. Esta in-

formacion se la recopila debido a un vehıculo en movimiento. Los datos que se obtuvieron se

encuentran en los diferentes repositorios web, en el que detalla cada tabla y lugar en donde se

obtuvo esta informacion, que en su mayorıa se trata de trayectorias vehiculares.

Ya verificado el origen de los datos, se procede a su respectivo procesamiento en el

lenguaje de programacion correspondiente en el caso se eligio R para un primer caso de aplicar

a los datos de trayectorias originales los algoritmos de simplificacion y proceder a compa-

rar despues los datos originales con el filtro de Kalman y algoritmos de simplificacion, como

primero se realiza un proceso de filtrado, los datos que se obtienen seran la entrada para los

algoritmos de simplificacion obteniendo como salida una cantidad de datos menores a la que

se presenta en un principio.

Metodologıa de investigacion

Para el actual trabajo de investigacion se basa en la experimentacion de los datos origi-

nales con algoritmos de simplificacion y datos originales aplicando filtro Kalman y algoritmos

de simplificacion, en los datos que fueron encontrados en los repositorios web ademas de los

datos de coordenadas GPS simulados, se llevo a cabo los experimentos del cual se llego a con-

clusiones de identificacion de la linealidad de una trayectoria, ademas de como afecta los datos

31

originales cuando son procesados por los algoritmos de simplificacion y el comportamiento de

los datos al realizar el proceso de filtro de Kalman para despues realizar la simplificacion con

los algoritmos de Douglas Peucker y TD-TR, se tomo como variable dependiente reduccion de

ruidos en trayectorias lineales y no lineales y como variable independiente filtro de Kalman en

algoritmos de simplificacion.

Para el estudio de los algoritmos con el filtrado, de los resultados obtenidos se evaluaron

diferentes metricas como tiempo de ejecucion, margen de error y razon de compresion. Con el

tiempo de ejecucion sabremos el tiempo que tomo cada simplificacion de los conjunto de da-

tos. Con el margen de error obtendremos cuanta distorsion hay entre la trayectoria original y su

simplificada. La razon de compresion permitira conocer el porcentaje de datos resultantes de la

trayectoria original.

Poblacion y muestra

Poblacion. Como lo define (Leon y Gonzalez, 2020) “Cualquier conjunto de elementos

que tengan una o mas propiedades en comun definidas por el investigador y que puede ser de

toda la realidad, hasta un grupo muy reducido de fenomenos”. Se podrıa definir a la poblacion

como el conjunto de informacion que se encuentra en el Data Set el cual tendra como finalidad

ser estudiado y analizado para su respectiva experimentacion.

Muestra. De igual forma (Hernandez, Fernandez, y Baptista, 2014) define a la muestra

como “El subgrupo de la poblacion de interes sobre el cual se recolectaran datos, y que tiene

que definirse y delimitarse de antemano con precision, ademas de que debe ser representativo

a de la poblacion”. Entonces se puede dar como conclusion que muestra es un subconjunto del

cual se toma una proporcion del conjunto de la poblacion.

32

Poblacion

Para esta investigacion se tomara para iniciar, la informacion que se ha adquirido de la

data set que se encuentra de manera publica de Microsoft (Geolife) ya que posee informacion

necesaria y con la cantidad de datos GPS aptos para pruebas de Brasil, Beijing ademas de

california, a continuacion se presenta con claridad la informacion que tiene cada base de datos

ademas de la cantidad de registros que contiene cada una de la base de datos de las ciudades

anteriormente mencionadas.

Tabla 3

Poblacion total de los conjuntos de datos

Poblacion N°

Bejing 6.345.904

Brasil 14.096

California 914.684

Guayaquil 1.460

Quito 1.460

Nota. En esta tabla se muestra la poblacion total que contienen cada uno de los conjuntos de datos.

Como se puede observar en el Tabla 3 la cantidad de registros en las ciudades de Beijing,

Brasil y California presenta un amplio volumen, a diferencia de Guayaquil y Quito que presenta

un volumen mucho menor debido a que estas bases de datos son simuladas, cabe mencionar que

cada base de datos posee tamanos diferentes, esto ayuda a que se planteen diversos escenarios

de estudio para cada base de datos.

Tamano de la muestra

La informacion planteada en las bases de datos de las cinco ciudades, se fijo en realizar

un muestreo con lo que respecta a las bases de datos de Beijing del 0.98 % y Brasil del 77.85 %

de los datos debido a la cantidad extensa de datos y procesamiento del software y hardware

33

a utilizar, ademas de realizar estudios con diversos porcentajes para sı analizar el comporta-

miento del filtro de Kalman como de los algoritmos de simplificacion. Para los respectivos

experimentos se utilizara el 100 % de la base de datos de las ciudad de California, Guayaquil y

Quito debido a que dara una mayor apreciacion de los puntos comprimidos y optimizacion de

los mismos a excepcion de las bases de datos de Beijing y Brasil que se usara el valor muestral

que se detalla en la siguiente tabla.

Tabla 4

Tamano de la muestra

Poblacion Cantidad de poblacion % de la muestra Cantidad de muestra a usar

Beijing 6.345.904 0.98 % 62.138Brasil 18.107 77.85 % 14.096

California 914.684 100 % 914.684Guayaquil 1.460 100 % 1.460

Quito 1.460 100 % 1.460

Nota. La tabla refleja la poblacion total de los conjuntos de datos y la cantidad de muestra a usar.

34

Detalles de los conjuntos de datos reales

Se detallan la informacion de los conjuntos de datos reales Beijing, Brasil y California

ademas del tipo de datos utilizado en cada uno.

Base de datos Beijing

El conjunto de datos de trayectoria que se utilizo en el documento se recopilo de datos

GPS de taxi en Beijing, China, cuyos datos fueron registrados por diferentes registradores GPS

(latitud, longitud) y angulos en una region determinada.

Esta es una muestra del conjunto de datos de trayectoria de T-Drive que contiene tra-

yectorias de una semana de 10.357 taxis.

- La cantidad total de la poblacion de T Drive es de 6‘345.904 registros.

Base de datos Brasil

Modalidad de recoleccion de datos GPS: Consiste en trayectorias de usuarios que con-

ducen automoviles o toman autobuses recogidos por la aplicacion Go! Track. Cantidad de tra-

yectorias del conjunto de datos son 163, la fecha Inicio de la recoleccion de datos 2014-09-13

07:24:32, el tiempo a procesar en minutos 450843.316666667 minutos.

- La cantidad total de la poblacion es de 18.107 registros.

Base de datos California

Los datos de Mobile Century se recopilaron el 8 de febrero de 2008, como parte de

un proyecto conjunto UC Berkeley - Nokia, financiado por el Departamento de Transporte

de California, para respaldar la exploracion de usos de telefonos con GPS para monitorear el

trafico.

35

Tabla 5

Nombres de las columnas que contiene los conjuntos de datos Beijing y Brasil

Columnas Descripcion

longitud Longitud de la posicion del punto de la trayectoria en elmapa global

latitud Latitud de la posicion del punto de la trayectoria en el mapaglobal

fecha hora Tiempo en Timestamp de la trayectoria vehicular

id taxi Numero de identificador de cada punto GPS

Nota. Las columnas previamente descritas son las que se utilizaron para los experimentos con cada con-junto de datos.

- La cantidad total de la poblacion de California es de 914.684 registros.

Tabla 6

Nombres de las columnas que contiene los conjuntos de datos California


folder name Nombre de la carpeta de las rutas

file name Identificador de cada trayectoria





36

Detalles de los Conjunto de datos simulados

Base de datos Guayaquil y Quito

Debido a la experimentacion se decidio crear un conjunto de datos que no posean una

trayectoria lineal por lo cual se decidio formar una trayectoria de forma circular del que se

obtuvo informacion de los programas de Google Earth y Map Source, el cual con el primer

programa se procede a buscar la ubicacion y graficar la ruta (circular) para esta base de datos la

ubicacion que se escogio fue Ecuador tanto como Guayaquil y Quito, seleccionando las rutas

de solo redondeles de ambas ciudades y con el programa Map Source el cual muestra los puntos

de latitud y longitud de dicha trayectoria.

- Cada id que en total son 20 obtendra 73 puntos cada una, dando a la poblacion de 1.460

registros que tendra la base de datos.

Tabla 7

Nombres de las columnas que contiene los conjuntos de datos Guayaquil y Quito


id trayectoria Numero de identificador de cada punto GPS

puntos Secuencia de puntos de contiene el conjunto de datos



nombre Nombre que identifica cada trayectoria



37

Procesamiento y analisis

En el procesamiento y analisis se elaboran diferentes escenarios para detallar los resul-

tados de los diferentes experimentos, en el siguiente cuadro se muestra los datos de conexion

de la base de datos PostgreSQL.

Tabla 8

Datos del Administrador de PostgreSQL

Nombre de la base de datos PostgreSQL 12

Puerto del localhost 5432

Administrador pgAdmin

Nombre de la data set taxi

Nota. En esta tabla se muestran los datos que utilizo el administrador de PostgreSQL.

Aquı es donde se procede a cargar las diferentes bases datos publicas de Beijing, Brazil,

California y las bases de datos simuladas de Guayaquil y Quito.

La manera en la que se realizo es obteniendo un archivo .csv de la informacion de

Beijing, Brazil y California, adicional a esto se procede a borrar la cabecera del del archivo

para despues guardar y transformar ese archivo .csv a un txt con codificacion UTF-8, adicional

se debe de crear una tabla en PostgreSQL con los mismos tipos de datos del txt y con un script

se procede a llamar el archivo .txt.

La experimentacion se realiza usando el lenguaje de programacion RStudio permite

ejecutar los algoritmos de simplificacion y filtrado de Kalman.

Ademas de realizar estudios con diversos porcentajes para sı analizar el comportamiento

del filtro de Kalman como de los algoritmos de simplificacion con porcentajes muestrales del

25 %, 50 % y 100 %.

En el cuadro que se muestra a continuacion se detallan la cantidad de registros y valores

porcentuales en cada base de datos a ser estudiadas.

38

Tabla 9

Porcentajes

Porcentajes Beijing Brasil California Guayaquil Quito

25 % 15.535 3.524 228.671 365 36550 % 31.069 7.048 457.342 730 730

100 % 62.138 14.096 914.684 1.460 1.460

Nota. En esta tabla se muestran los porcentajes con los puntos que se utilizaron para los estudios inciales.

Una vez ya seleccionada de Bases de datos que sera utilizadas como punto de referencia

para poder comprar los datos en conjunto con los algoritmos de simplificacion efectuando el

proceso en el proyecto de investigacion, una vez que el proceso de obtencion de datos culmine,

el proceso a tomar es el de identificar y analizar el algoritmo que ofrezca un mejor resultado con

respecto al epsilon a utilizar, razon de comprension y margen de error, de ahı tendra origen para

el siguiente proceso que es aplicar el filtro de Kalman que posterior se realizara comparaciones

de los de los puntos comprimidos y filtrados para su respectivo analisis.

39

Experimentacion Inicial

Criterio para calcular la linealidad de una trayectoria

Dentro de la geometrıa analıtica se utilizan figuras geometricas tales como la recta,

empleando expresiones algebraicas de calculo para poder representar la ecuacion y ası resolver

problemas, para el mismo se aplica un plano cartesiano (con coordenadas de X y Y) en el

que podemos representar una recta y a su vez, lograr determinar valores que satisfagan las

condiciones que se han determinado. Esta recta se podrıa expresar a traves de la ecuacion, en

la cual las variables del plano son x, y, esta expresion de variables se las podrıa nombrar como

la pendiente de la recta (m), ya que esta es el grado de inclinacion que adquiere la recta en

relacion a los ejes del plano x, y; la “b” letra que es representada en la expresion, es el termino

independiente que muestra el valor del punto exacto en el que se divide al eje vertical (y) dentro

del plano cartesiano.(Alvarado Maldonado, 2016)

A continuacion se detalla la formula de la pendiente de una recta:

m =Y2 − Y1

X2 − X1(10)

Resultados del calculo de la linealidad en los diferentes conjuntos de datos

Para los experimentos se procedio a tomar el 25 %, 50 % y 100 % de cada base de datos

de las ciudades a trabajar y se aplicar el metodo de la pendiente en las bases de datos de Beijing,

Brasil, California, Guayaquil y Quito.

40

Linealidad de conjuntos de datos reales

Base de datos Beijing

Tabla 10

Porcentaje de linealidad base de datos Beijing

Porcentaje de registrospara los experimentos

N° de puntos % de segmentos li-neales

% de segmentos nolineales

25 % 15.535 3.11 % 96.89 %50 % 31.069 1.83 % 98.17 %

100 % 62.138 1.05 % 98.95 %

Nota. En esta tabla se detallan los porcentajes de linealidad que contiene el conjunto de datos llamadoBeijing, separando dichos porcentajes como lineales y no lineales.

En el cual primero se tomo el 25 % de puntos que da un total de 15535 puntos en el

cual 483 puntos resultaron ser segmentos lineales con un porcentaje de 3.11 % mientras que

15052 puntos resultaron ser segmentos no lineales con un porcentaje de 96.89 % dando como

conclusion que el 25 % de la base de datos Beijing es una trayectoria No Lineal.

De la misma base de Beijing se tomo el 50 % de puntos que da un total de 31069 puntos

de los cuales 569 resultaron ser segmentos lineales con un porcentaje de 1.83 % a diferencia

de los segmentos no lineales que dan un total de puntos de 30500 puntos con un porcentaje de

98.17 % dando como conclusion que el 50 % de la base de Beijing es una trayectoria No Lineal.

Ası mismo se procede a tomar el 100 % de los puntos de la base de Beijing que es un

total de 62138 puntos dando como segmentos lineales 654 puntos mostrando un porcentaje

de 1.05 % mientras que los segmentos no lineales muestran un total de puntos de 61484 con

un porcentaje de 98.95 % dando como conclusion que el 100 % de la base de Beijing es una

trayectoria No Lineal.

41

Base de datos Brasil

Tabla 11

Porcentaje de linealidad base de datos Brasil




25 % 3.524 0.03 % 99.97 %50 % 7.048 0.11 % 99.89 %

100 % 14.096 0.09 % 99.91 %

Nota.En esta tabla se detallan los porcentajes de linealidad que contiene el conjunto de datos llamadoBrasil, separando dichos porcentajes como lineales y no lineales.

En el cual primero se tomo el 25 % de puntos que da un total de 3524 puntos en el

cual 1 punto resulto ser segmento lineal con un porcentaje de 0.03 % mientras que 3523puntos

resultaron ser segmentos no lineales con un porcentaje de 99.97 % dando como conclusion que

el 25 % de la base de datos Brasil es una trayectoria No Lineal.

De la misma base de Brasil se tomo el 50 % de puntos que da un total de 7048 puntos de

los cuales 8 puntos resultaron ser segmentos lineales con un porcentaje de 0.11 % a diferencia

de los segmentos no lineales que dan un total de puntos de 7040 puntos con un porcentaje de

99.89 % dando como conclusion que el 50 % de la base de Brasil es una trayectoria No Lineal.

Ası mismo se procede a tomar el 100 % de los puntos de la base de Brasil que es un



un porcentaje de 99.91 % dando como conclusion que el 100 % de la base de Brasil es una


42

Base de datos California

Tabla 12

Porcentaje de linealidad base de datos California




25 % 228.671 0.24 % 99.76 %50 % 457.341 0.25 % 99.75 %

100 % 914.684 0.15 % 99.85 %

Nota. En esta tabla se detallan los porcentajes de linealidad que contiene el conjunto de datos llamadoCalifornia, separando dichos porcentajes como lineales y no lineales.

En el cual primero se tomo el 25 % de puntos que da un total de 228671 puntos en

el cual 559 puntos resultaron ser segmentos lineales con un porcentaje de 0.24 % mientras

que 228112 puntos resultaron ser segmentos no lineales con un porcentaje de 99.76 % dando

como conclusion que el 25 % de la base de datos California es una trayectoria No Lineal. De

la misma base de California se tomo el 50 % de puntos que da un total de 457342 puntos de

los cuales 1165 resultaron ser segmentos lineales con un porcentaje de 0.25 % a diferencia de

los segmentos no lineales que dan un total de puntos de 456177 puntos con un porcentaje de

99.75 % dando como conclusion que el 50 % de la base de California es una trayectoria No

Lineal.

Ası mismo se procede a tomar el 100 % de los puntos de la base de California que es un



un porcentaje de 99.85 % dando como conclusion que el 100 % de la base de California es una


43

Linealidad de conjuntos de datos simulados

Ası mismo se procedio aplicar el metodo de la pendiente en la base de datos circulares

simuladas de Guayaquil y Quito a continuacion se detalla los resultados en las siguientes tablas:

Base de datos Guayaquil

Tabla 13

Porcentaje de linealidad base de datos Guayaquil




25 % 365 8.49 % 91.51 %50 % 730 6.85 % 93.15 %

100 % 1460 7.47 % 92.53 %


Se tomo el 25 % de puntos que da un total de 365 puntos en el cual 31 puntos resultaron

ser segmentos lineales con un porcentaje de 8.49 % mientras que 334 puntos resultaron ser

segmentos no lineales con un porcentaje de 91.51 % dando como conclusion que el 25 % de la

base de datos Guayaquil es una trayectoria No Lineal.

De la misma base se tomo el 50 % de puntos que da un total de 730 puntos de los cuales

31 resultaron ser segmentos lineales con un porcentaje de 6.85 % a diferencia de los segmentos

no lineales que dan un total de puntos de 680 puntos con un porcentaje de 93.15 % dando como

conclusion que el 50 % de la base de Guayaquil es una trayectoria No Lineal.

Ası mismo se procede a tomar el 100 % de los puntos de la base de Guayaquil que es

un total de 1460 puntos dando como segmentos lineales 109 puntos mostrando un porcentaje

de 7.47 % mientras que los segmentos no lineales muestran un total de puntos de 1351 con un

porcentaje de 92.53 % dando como conclusion que el 100 % de la base de Guayaquil es una


44

Base de datos Quito

Tabla 14

Porcentaje de linealidad base de datos Quito




25 % 365 8.49 % 91.51 %50 % 730 6.85 % 93.15 %

100 % 1460 8.08 % 91.92 %


En el cual primero se tomo el 25 % de puntos que da un total de 365 puntos en el cual 31

puntos resultaron ser segmentos lineales con un porcentaje de 8.49 % mientras que 334 puntos

resultaron ser segmentos no lineales con un porcentaje de 91.51 % dando como conclusion que

el 25 % de la base de datos Quito es una trayectoria No Lineal.

De la misma base de Quito se tomo el 50 % de puntos que da un total de 730 puntos de

los cuales 50 resultaron ser segmentos lineales con un porcentaje de 6.85 % a diferencia de los

segmentos no lineales que dan un total de puntos de 680 puntos con un porcentaje de 93.15 %

dando como conclusion que el 50 % de la base de Quito es una trayectoria No Lineal.

Ası mismo se procede a tomar el 100 % de los puntos de la base de Quito que es un total

de 1460 puntos dando como segmentos lineales 118 puntos mostrando un porcentaje de 8.08 %

mientras que los segmentos no lineales muestran un total de puntos de 1342 con un porcentaje

de 91.92 % dando como conclusion que el 100 % de la base de Quito es una trayectoria No

Lineal.

45

Conclusion parcial de la linealidad de los conjuntos de datos.

Como conclusion parcial con respecto a segmentos de puntos lineales y no lineales

referente con los valores mostrados en porcentajes y cantidad de puntos que presenta como

resultado que los conjuntos de datos reales de Beijing, Brasil y California como tambien los

conjuntos de datos simulados de Guayaquil y Quito aplicando el metodo matematico de la

pendiente son trayectorias no Lineales.

46

Experimentacion Final

Fase 1: Resultados del filtro Kalman con los conjuntos de datos

Se aplico el filtro de Kalman con ayuda del paquete en R llamado DLM a los datos ori-

ginales en el cuadro que se muestra a continuacion se observa el numero de puntos filtrados y el

numero puntos originales de longitud y latitud que coinciden con el porcentaje de los mismos,

ademas de mostrar la cantidad puntos filtrados con puntos originales que no coinciden.

Tabla 15

Filtro Kalman aplicado en los conjuntos de datos

Nombre de losconjuntos de datos

Cantidad depuntos

Puntoscoinciden

Puntos nocoinciden

Puntos en %coinciden

Beijing 62.138longitud 5.165 56.973 8.31 %latitud 5.310 56.828 8.55 %

Brasil 14.096longitud 138 13.958 0.98 %latitud 106 13.990 0.75 %

California 914.684longitud 596 914.088 0.07 %latitud 571 914.113 0.06 %

Guayaquil 1.460longitud 594 866 40.68 %latitud 575 885 39.38 %

Quito 1.460longitud 887 573 60.75 %latitud 637 823 43.63 %

Nota. En esta tabla se muestran los porcentajes de coincidencia comparando las trayectorias originalescon las trayectorias aplicado el Filtro Kalman.

Como se detalla en la tabla 15 se puede apreciar que la base de datos que tuvo una

mayor reduccion de ruidos en su trayectoria fue la de California teniendo un porcentaje de

coincidencia tanto de longitud como latitud de 0.07 % y 0.06 % respectivamente, mientras que

la base de datos de Beijing muestra valores de coincidencia superiores al 8 % lo cual se puede

concluir que existio menor reduccion de ruido.

Con respecto a la base de datos simuladas circulares Quito presento valores de coinci-

dencia elevados debido a que son trayectorias de menor volumen, por lo tanto en longitud y

47

latitud indica que existio menor reduccion de ruido con porcentajes de 60.75 % en longitud y

43.63 % en latitud.

Tal como lo menciona (Puertas Ramırez, 2018) mientras exista mayor cantidad de pun-

tos de trayectorias vehiculares de longitud y latitud esta tendra mas ruido a diferencia de una

trayectoria vehicular que contenga menor cantidad de puntos longitud y latitud tendra menor

ruido.

Fase 2: Resultados de los algoritmos de simplificacion con los conjuntos de datos originales

En la investigacion se procedio aplicar a los datos de trayectorias vehiculares los al-

goritmos de simplificacion a utilizar. Se realizaron diferentes experimentos con 5 valores de

epsilon el cual permite medir la reduccion de puntos que tendra el algoritmo.

AL momento de realizar la comparacion con los diferentes valores de epsilon se escogio

el que mejor se ajusta a resultados de simplificacion, debido a que cada epsilon recopila valores

diferentes en los datos de trayectorias.

Una vez ejecutado el script que contiene el algoritmo de simplificacion Douglas Peucker

y TD-TR en lenguaje de programacion R se obtuvieron los siguientes resultados mostrados a

continuacion:

Tabla 16

Resultados de la simplificacion con los algoritmos y epsilon escogido

Nombre delconjutos de datos

Cantidad depuntos iniciales

Puntos fina-les de RDP

Puntos fina-les de TD-TR

Epsilon

Beijing 62.138 11.386 16.895 0.001Brasil 14.096 1.117 1.505 0.001

California 914.684 61.562 87.960 0.0004Guayaquil 1.460 40 491 0.00001

Quito 1.460 79 364 0.00001

Nota. En la tabla se observan la cantidad de puntos resultantes de la simplificacion de los conjuntos dedatos, su cantidad de puntos iniciales y la tolerancia que utilizada en los algoritmos.

48

Figura 2

Trayectoria Original y Trayectoria simplificada Douglas Peucker

Nota. En esta figura se visualiza la trayectoria original y la trayectoria luego de la simplificacion con elalgoritmo de Douglas Peucker.

Figura 3

Trayectoria Original y Trayectoria simplificada TD-TR

Nota. En esta figura se visualiza la trayectoria original y la trayectoria luego de la simplificacion con elalgoritmo de TD-TR.

Evaluacion de los algoritmos a traves de metricas en los resultados.

- Algoritmo de Douglas Peucker

Se aplico el algoritmo de simplificacion de Douglas Peucker para la respectiva reduc-

cion de puntos en las trayectorias a usar teniendo en cuenta las metricas a usar para la diferen-

ciacion de algoritmos.

49

Tabla 17

Resultados de la evaluacion con las metricas en la simplificacion usando el algoritmoRDP

Nombre del con-junto de datos

Tiempo(seg) Razon decompresion( %)

Margen de error Tipo

Beijing 2016 seg 81.68 % 0.011 RealBrasil 80.28 seg 92.08 % 0.007 Real

California 26405 seg 93.27 % 0.001 RealGuayaquil 1.49 seg 97.26 % 0.011 Simulada

Quito 2.04 seg 94.59 % 0.003 Simulada

Nota. En la tabla se observan los valores de las metricas que presenta el algoritmo de RDP en relacioncon cada uno de los conjuntos de datos simplificados.

Los resultados que muestra el algoritmo son satisfactorio a lo que se refiere a razon

de comprension y margen de error, mientras que en tiempo de ejecucion existen valores muy

elevados.

En base a los resultados mostrados con respecto al tiempo de ejecucion la base de datos

de California muestra un valor elevado de 26405 segundos a diferencia de la base de datos de

Brasil que le tomo un menor tiempo con un valor de 80.28 segundos. En las bases de datos

circulares simuladas reflejan un tiempo de ejecucion menor debido a la cantidad de datos en

comparacion a la base de datos reales.

Con la siguiente metrica que es la razon de comprension se concluye que la trayectoria

de California tuvo una mayor comprension en los datos con un porcentaje de 93.26 % mientras

que las bases circulares simuladas presentaron un porcentaje de comprension superior al 90 %.

Con respecto ala ultima metrica que es margen de error el cual la base de dato que tuvo menor

distorsion con respecto a la trayectoria original fue California con un valor de 0.0007 mientras

que la base de datos de Beijing tuvo una mayor distorsion en los datos con un valor de 0.011.

Con las bases de datos circulares simuladas la que presento menor distorsion en los datos de

trayectoria fue la de Quito con un valor de 0.003.

50

- Algoritmo TD-TR

Para el siguiente experimento se tomo el algoritmo de simplificacion de TD-TR, tenien-

do en consideracion las mismas metricas anteriormente mencionadas y las bases de datos tanto

reales como simuladas.

Tabla 18

Resultados de la evaluacion con las metricas en la simplificacion usando el algoritmoTD-TR







Nota. En la tabla se observan los valores de las metricas que presenta el algoritmo de TD-TR en relacioncon cada uno de los conjuntos de datos simplificados.

Los valores de tiempo de ejecucion como razon de compresion disminuyen en compa-

racion del anterior algoritmo de simplificacion, en conclusion, la base de datos de California

tuvo un mayor tiempo de ejecucion con un valor de 14417 en segundos a diferencia de la

base de Brasil que tuvo un valor de 64.08 en segundos, a diferencia de las bases circulares

simuladas que presentan un tiempo de ejecucion menor debido a la cantidad de registros que se

presentan en cada una. Concluyendo con la razon de compresion la base de datos que presento

mas comprension de puntos con respecto a los datos originales fue la de California con un valor

de 90.38 % y la que tuvo un menor valor de compresion fue la base de datos de Beijing con

un valor de 72.81 % a diferencia de las bases de datos circulares simuladas que presentaron

valores de comprension bajos debido al tiempo simulado que se esta utilizando en las tablas.

Finalizando con el margen de error la base de datos de Brasil presenta una menor distorsion en

los puntos con un valor de 0.0001 mientras que la base de datos de Beijing presenta una mayor

51

distorsion con un valor de 0.013, mientras que en las bases circulares simuladas al igual que el

anterior algoritmo Quito es la que presenta menor distorsion con un valor de 0.007.

Fase 3: Resultados de los conjuntos de datos con el filtro de Kalman y algoritmos de simplifi-

cacion.

En el presente trabajo de investigacion se procedio a tomar los datos de trayectorias

reales para respectivo proceso el cual es el filtro de Kalman para despues aplicar los diferentes

algoritmos de simplificacion, con lo que respecta a filtro de Kalman se uso la librerıa DLM el

cual facilita el proceso para la reduccion de ruido que presente las bases de datos tanto reales

como las bases de datos circulares simuladas, como se lo menciona con anterioridad se realizo

diferentes experimentos en las cuales se escogio 5 epsilon, en el cual se procedio a elegir el

mejor valor que se ajuste a los resultados de simplificacion.

Una vez finalizada la experimentacion inicial se procede a tomar el script del filtro de

Kalman y ejecutarlos en los resultados de los algoritmos de simplificacion para despues eva-

luar y comparar el filtro con el algoritmo de simplificacion que reduce de manera significativa

el ruido que existe en las trayectorias GPS lineales y no Lineales, ademas de las trayectorias

circulares simuladas.

Tabla 19

Resultados de la simplificacion con los algoritmos con el epsilon escogido

Nombre delconjutos de datos

Cantidad depuntos iniciales

Puntos fina-les de RDP

Puntos fina-les de TD-TR

Epsilon

Beijing 62.138 11.920 17.012 0.001Brasil 14.096 1.217 1.631 0.001

California 914.684 62.986 43.968 0.0004Guayaquil 1.460 825 506 0.00001

Quito 1.460 641 354 0.00001

Nota. . En la tabla se observan la cantidad de puntos resultantes de la simplificacion de los conjuntos dedatos, su cantidad de puntos iniciales y la tolerancia que utilizada en los algoritmos.

52

Figura 4

Trayectoria Filtrada y Trayectoria simplificada Douglas Peucker

Nota. En esta figura se visualiza la trayectoria Filtrada y la trayectoria luego de la simplificacion con elalgoritmo de Douglas Peucker.

Figura 5

Trayectoria Filtrada y Trayectoria simplificada TD-TR

Nota. En esta figura se visualiza la trayectoria filtrada y la trayectoria luego de la simplificacion con elalgoritmo de TD-TR.

Evaluacion del filtro de Kalman con los algoritmos de simplificacion por medio de metricas

- Filtro Kalman con el Algoritmo de Douglas Peucker

Se aplico el filtro de Kalman DLM en los datos originales de las respectivas bases de

datos incluyendo las bases de datos circulares simuladas una vez obtenido los registros suavi-

zados (disminucion de ruido) se aplica el algoritmo de simplificacion de Douglas Peucker.

53

Tabla 20

Resultados de la evaluacion con las metricas en la simplificacion usando el algoritmoRDP




Beijing 1952 seg 80.82 % 0.011 RealBrasil 102 seg 91.37 % 0.006 Real



Nota. En la tabla se observan los valores de las metricas que presenta el algoritmo de RDP en relacioncon cada uno de los conjuntos de datos simplificados.

Se observa en la tabla agregar numero de la tabla el tiempo de ejecucion en la base de

datos de California es mayor con un valor de 20595 en segundos con respecto a la base de

datos de Brasil el que obtuvo un valor de 102 en segundos, con respecto a las bases simuladas

circulares que presentan valores bajos de 11.73 y 9.58 en segundos debido a la cantidad de

registros que se tiene de cada una de ellas.

Con respecto a la razon de compresion se observa que la base de datos de California tu-

vo una mayor compresion en los datos con un valor de 93.11 % mientras que existio una menor

comprension en los datos en la base de datos de Beijing con un valor de 80.82 %, mientras que

en las bases simuladas en Quito existe una mayor compresion con un valor de 56.10 %.

Concluyendo con la metrica de margen de error la base de datos que presento menor

distorsion en los puntos es la de California con un valor de 0.006 mientras que la base de datos

de Beijing presenta una mayor distorsion en los datos con un valor de 0.011, con respecto a la

base simulada circular de Guayaquil presenta un valor de distorsion en los puntos con 0.0003 a

diferencia de Quito que supera ese porcentaje presentando un valor mayor.

54

- Filtro Kalman con el Algoritmo de TD-TR

Tabla 21

Resultados de la evaluacion con las metricas en la simplificacion usando el algoritmoTD-TR







Nota. En la tabla se observan los valores de las metricas que presenta el algoritmo de TD-TR en relacioncon cada uno de los conjuntos de datos simplificados.

Se aplico el filtro de Kalman DLM en los datos originales de las respectivas bases

de datos incluyendo las bases de datos circulares simuladas, una vez obtenido los registros

suavizados (disminucion de ruido) se aplica el algoritmo de simplificacion TD-TR.

Se observa en la tabla 21 de la tabla el tiempo de ejecucion varıa en cada base datos,

teniendo en cuenta que la base de datos de California presenta mayor valor con 11029 en segun-

dos mientras que Brasil presenta un valor menor de 76,85 en segundos, con respecto a las bases

de datos circulares simuladas presentan valores de 7.80 y 6.70 en segundos respectivamente.

Con la siguiente metrica de razon de comprension se puede observar que la base de datos de

California supera el 95.19 % en comprension de puntos a diferencia de las bases simuladas

de Guayaquil y Quito que presentan valores de comprension inferiores de 65.34 % y 75.75 %

respectivamente debido a la dispersion de los puntos.

Por ultimo, la metrica de margen de error en el cual las bases de Beijing y California

presentan valores similares lo cual indica que en ambas la distorsion de los puntos ha sido

tan significativa a diferencia de Brasil que tuvo un porcentaje de 0.0003 indicando una menor

distorsion, en las bases de datos simuladas circulares Guayaquil con respecto a Quito presenta

55

mayor distorsion en los puntos con un valor de 0007.

Evaluacion de las metricas, de trayectorias originales con los algoritmos de simplificacion

y las trayectorias con Filtro Kalman con los algoritmos de simplificacion de los conjuntos

de datos

Tabla 22

Trayectorias originales con los algoritmos de simplificacion y las trayectorias con FiltroKalman con los algoritmos de simplificacion de los conjuntos de datos




Beijing

81.68 seg 81.67 % 0.011 DP72.81 seg 72.82 % 0.013 TD-TR80.82 seg 80.82 % 0.011 K DP72.62 seg 72.62 % 0.0002 K TD-TR

Brasil


California


Guayaquil


Quito


Nota. En la tabla se observan los valores de las metricas que presenta el algoritmo de RDP y TD-TR enrelacion con cada uno de los conjuntos de datos simplificados con las trayectorias originales y trayecto-rias filtradas por el Kalman.

Ya finalizado los experimentos con sus respectivas fases se detalla el comportamiento

del conjunto de datos originales aplicando los diferentes procesos tales como reduccion de rui-

56

do y simplificacion de puntos por lo tanto como conclusion final se muestra que en el conjunto

de datos simulados de Guayaquil en la metrica de tiempo de ejecucion empleando el algoritmo

de simplificacion Douglas Peucker da el menor valor en lo que el algoritmo tarda en ejecutar

con un tiempo de 1.49 segundos, mientras que en el conjunto de datos de California utilizando

el algoritmo de simplificacion Douglas Peucker presento el mayor valor en tiempo de ejecucion

con 26405 segundos.

En cuanto a la razon de comprension utilizando el algoritmo de simplificacion Douglas

Peucker muestra una mayor compresion en los puntos de la trayectoria en el conjunto de da-

tos simulados de Guayaquil con un porcentaje de 97.26 % mientras que el menor resultado de

porcentaje de compresion de puntos la presento el filtro de Kalman aplicando algoritmo de sim-

plificacion Douglas Peucker con un porcentaje de 43.49 % en el conjunto de datos simulados

de Guayaquil.

Por ultimo se encuentra el margen de error en el cual el filtro de Kalman aplicando algo-

ritmo de simplificacion TD-TR presento el mayor valor con 0.290 en distorsion de puntos en el

conjunto de datos simulados de Quito, mientras que el conjunto de datos de Brasil manejando

el algoritmo de simplificacion TD-TR presento la menor cantidad de distorsion en puntos de

trayectorias con un valor de 0.0002.

En los resultados por parte de (Chalen Echeverrıa y Vasquez Choez, 2020) en que de-

muestran al igual que el experimento presentado que la razon de compresion y margen de error

son directamente proporcional, es decir, mientras exista mayor simplificacion en los puntos de

la trayectoria existira mayor distorsion en los puntos del mismo y viceversa.

57

Beneficiarios directos e indirectos del proyecto

Beneficiarios directos e indirectos del proyecto.

Se consideran como beneficiarios directos del proyecto de investigacion a:

• Profesores y estudiantes que deseen tener el conocimiento del comportamiento de los

datos en trayectorias vehiculares GPS aplicando reduccion de ruido que es el filtro

de Kalman y algoritmos de simplificacion.

• Profesionales que requieran informacion de trayectorias GPS suavizadas (sin ruido)

o informacion de trayectorias GPS comprimidas implementadas con los algoritmos

de simplificacion.

• Investigadores y tecnicos al disponer de conocimiento cientıfico para fortalecer la

ensenanza a nivel universitario y poder implementar estos tipos de informacion para

trabajos futuros.

Como beneficiarios indirectos estan las empresas y Universidades que realizan el es-

tudio de trayectorias y que cargan esta informacion a un repositorio web para su posterior

analisis.

Entregables del proyecto

Artıculo Cientıfico.

Se realizo un artıculo cientıfico en donde se plantean y describen los resultados de los

experimentos realizados en el trabajo de investigacion con la finalidad de compartir los resul-

tados obtenidos con la comunidad cientıfica e investigadores que estan inmersas en tema que

guardan relacion con el proyecto.

58

Resultados

Media y desviacion estandar de los datos simplificados con relacion a las metricas.

Media

Cantidad promedio al momento de sumar los datos y dividir para el total de datos. La

formula que se procedera a utilizar es la siguiente:

Pk =X1 + X2 + ..... + XN

N(11)

- Media de los algoritmos de simplificacion.

Como se muestra en la tabla 23 se calculo la media de las metricas de cada base de

datos tanto real como simuladas ya aplicados los algoritmos de simplificacion, en el cual se

obtuvieron los siguientes resultados:

Tabla 23

Media Douglas Peucker TD-TR

Tiempo de ejecucion(Seg) Razon de compre-sion %

Margen de error

Douglas Peucker 5701 seg 91.77 % 0.007TD - TR 2985 seg 78.79 % 0.005

Nota. En la tabla se observan los valores de la media por cada una de las metricas que se evaluaron paracada uno de los algoritmos.

Aplicado el calculo de la media en las metricas de algoritmos de simplificacion, se

muestra en el grafico agregar numero que Douglas Peucker es mayor con un tiempo de 5701

segundos con respecto a TD-TR que muestra un tiempo de 2985 segundos, se concluye que, en

tiempo de ejecucion TD-TR presenta menor tiempo de respuesta. Mientras con lo que respecta

a razon de compresion Douglas Peucker tiene un valor de 91.77 % a diferencia de TD-TR que

59

presenta un valor de 78.79 %, donde se determina que Douglas Peucker es optimo en lo que

respecta a comprension de puntos. Por ultimo, en margen de error Douglas Peucker presenta un

valor de 0.007 mientras que TD-TR muestra un valor de 0.005 donde se concluye que TD-TR

ofrece una menor distorsion de puntos.

Figura 6

Media de los algoritmos de simplificacion Douglas Peucker y TD-TR


Desviacion Estandar

La desviacion estandar es el tamano de separacion general, el cual muestra que tan

discontinuos estan los datos en relacion a la media. Para la desviacion estandar en tanto mayor

fuese esta, mucho mas grande sera la separacion que exista entre los datos.

δ =

√∑Ni=1(x1 + M(X))

N − 1(12)

60

- Desviacion Estandar de los algoritmos de simplificacion.

En la siguiente tabla se presenta la desviacion estandar de las metricas de cada base de

datos tanto real como simuladas ya aplicados los algoritmos de simplificacion, en el cual se

obtuvieron los siguientes resultados:

Tabla 24

Desviacion Estandar Douglas Peucker y TD-TR

Tiempo de ejecucion(Seg) Razon de compresion % Margen de error


Nota. En la tabla se observan los valores de la desviacion estandar por cada una de las metricas que seevaluaron para cada uno de los algoritmos.

Ya realizado el calculo de la desviacion estandar se obtuvo que en el tiempo de ejecu-

cion tuvo como mayor valor el algoritmo de Douglas Peucker dando como resultado 11606 el

cual se encuentra disperso con respecto a la media, en cambio el algoritmo de TD-TR muestra

un resultado de 6393 el cual tambien se encuentra disperso con relacion a la media pero en

menor cantidad.

Con respecto a la razon de comprension en los algoritmos de simplificacion de Douglas

Peucker y TD-TR muestran valores de 5.96 % y 10.60 % respectivamente, lo cual muestra una

menor dispersion en los datos con relacion a la media.

Los resultados obtenidos en el margen de error en el algoritmo de Douglas Peucker dio

como resultado en la desviacion estandar un valor de 0.005 el cual muestra una menor disper-

sion en los datos, mientras que en el algoritmo de TD-TR da como resultado un valor de 0.006

el cual es mayor a relacion con la media pero que no se encuentra alejado en la dispersion.

61

Figura 7

Desviacion estandar de los algoritmos de simplificacion Douglas Peucker y TD-TR

Nota. En esta figura se resumen la tipologıa de investigaciones, cada una de ellas, con caracterısticasclaramente definidas, que usted debera evaluar para seleccionarlas y aplicarlas en su proyecto de inves-tigacion.

- Media del Filtro de Kalman con los algoritmos de simplificacion.

Como se muestra en la tabla 25 se calculo la media de las metricas de cada base de datos

tanto real como simuladas ya aplicando el filtro de Kalman y los algoritmos de simplificacion,

en el cual se obtuvieron los siguientes resultados:

Tabla 25

Media del Filtrado Kalman con los algoritmo de simplificacion Douglas Peucker TD-TR




Aplicado el calculo de la media en el filtro de Kalman con algoritmos de simplificacion

en sus respectivas metricas, se muestra en la Figura 8 que Douglas Peucker es mayor con un

tiempo de 4534 segundos con respecto a TD-TR que muestra un tiempo de 2298 segundos, se

62

concluye que en tiempo de ejecucion TD-TR presenta menor tiempo de respuesta. Mientras con

lo que respecta a razon de compresion Douglas Peucker tiene un valor de 72.98 % a diferencia

de TD-TR que presenta un valor de 79.47 %, se concluye que TD-TR es optimo en lo que

respecta a comprension de puntos. Por ultimo, en margen de error Douglas Peucker presenta

un valor de 0.062 mientras que TD-TR muestra un valor de 0.007 se determina que TD-TR

ofrece una menor distorsion de puntos.

Figura 8

Media del Filtrado Kalmann con los algoritmos de simplificacion Douglas Peucker yTD-TR


63

- Desviacion Estandar del Filtro de Kalman con algoritmos de simplificacion.

Aplicado el calculo de la desviacion estandar en las diferentes metricas utilizando el fil-

tro de Kalman con los algoritmos de simplificacion a continuacion se presentan los resultados

obtenidos:

Tabla 26

Desviacion Estandar Douglas Peucker y TD-TR




Realizado los respectivos calculos de la desviacion estandar se obtuvo como resultado

en el tiempo de ejecucion que el filtro de Kalman con el algoritmo de simplificacion Douglas

Peucker tiene mayor dispersion con respecto a la media con un valor de 9017 mientras que el

filtro de Kalman con el algoritmo de simplificacion de TD-TR tambien tiene mayor dispersion

pero en menor cantidad con un valor de 4883.

Mientras que en la razon de compresion ambos resultados mostraron valores menores

lo cual indica que existe menor dispersion de puntos con valores de 22.13 % y 12.12 % respec-

tivamente.

Por ultimo tenemos la metrica de margen de error en donde el filtro con el algoritmo

de Douglas Peucker muestra un valor de 0,128 indicando que existe mayor dispersion de los

puntos con respecto a la media a diferencia del filtro con el algoritmo de TD-TR que presenta

un valor de 0,007 que es el mismo valor de media indicando que no existe ni menor, ni mayor

dispersion de los puntos.

Realizado los respectivos calculos de la desviacion estandar se obtuvo como resultado

en el tiempo de ejecucion que el filtro de Kalman con el algoritmo de simplificacion Douglas

64

Figura 9

Desviacion Estandar del Filtrado Kalmann con los algoritmos de simplificacion DouglasPeucker y TD-TR


Peucker tiene mayor dispersion con respecto a la media con un valor de 9017 seg mientras

que el filtro de Kalman con el algoritmo de simplificacion de TD-TR tambien tiene mayor

dispersion, pero en menor cantidad con un valor de 4883 seg, como en ambas existe variedad

en los datos los valores de la media no son confiables.

Mientras que en la razon de compresion ambos resultados mostraron valores menores

con respecto a la media lo cual indica que existe menor dispersion de puntos con valores de

22.13 % y 12.12 % respectivamente, presentando que dichos valores se encuentran mas agru-

pados con el valor de la media.

Por ultimo, la metrica de margen de error en donde el filtro con el algoritmo de Douglas

Peucker muestra un valor de 0.128 se indico que existe mayor dispersion de los puntos con

respecto a la media a diferencia del filtro con el algoritmo de TD-TR que presenta un valor de

0.007 que es el mismo valor de media indico que no existe ni menor, ni mayor dispersion de

los puntos.

65

CAPITULO IV

CONCLUSIONES Y RECOMENDACIONES

Conclusiones

• Conclusion 1: La investigacion esta orientado analisis de datos lineales y no lineales,

identificando el porcentaje de linealidad que contendra cada trayectoria, a su vez de

comprobar cual de los algoritmos de simplificacion presenta mejores resultados con

respecto al tiempo de ejecucion, razon de compresion y margen de error.

• Conclusion 2: Una vez revisado el estado de arte y marco teorico de los filtros de

reduccion de ruidos, se procedio a seleccionar el filtro de Kalman del paquete DLM

porque es el que mas se ajusta al conjunto de datos, siendo utilizado en trabajos de

investigaciones anteriores para la reduccion de ruidos en trayectorias GPS.

• Conclusion 3: En el trabajo de investigacion se realizo experimentos generando cier-

ta cantidad de puntos, suavizados y simplificados. Los parametros tomados en cuen-

ta fueron las variables de latitud y longitud en cada trayectoria, con el proposito de

concluir el filtrado de Kalman aplicando algoritmos de simplificacion, se obtuvieron

mejores resultado al momento de comprimir datos y reducir ruidos en los mismos,

se concluye que con el conjunto de datos de California , el filtro de Kalman y algo-

ritmo de simplificacion de TD-TR hubo un porcentaje mayor de compresion en la

trayectoria.

66

• Conclusion 4: Para validacion de resultados en el trabajo de investigacion se aplico

los metodos estadısticos de la media y deviacion estandar dando como mejor resul-

tado el filtro de Kalman con el algoritmo de TD-TR, pero en tiempo de ejecucion el

algoritmo de Douglas Peucker destaca en el estudio.

• Conclusion 5: En el trabajo investigativo se elaboro un artıculo cientıfico con la fi-

nalidad de ser publicado y compartir resultados con la comunidad cientıfica, ademas

que se incorporen como recurso bibliografico con disponibilidad a los interesados.

67

Recomendaciones

• Recomendacion 1: Es recomendable utilizar para los experimentos conjuntos de da-

tos que contengan mayor volumen, esto con el fin de determinar el comportamiento

que tendra el filtro de Kalman con los algoritmos de simplificacion en relacion al

suavizado, comprension de datos que fueron adquiridos.

• Recomendacion 2: A lo largo del proceso de investigacion presentado, se pudo reco-

nocer un paquete que proporciona R studio en un algoritmo de Kalman con nombre

de FKF, el mismo que posee ciertas propiedades semejantes al denominado paquete

DLM pero con una estructura de suavizados de ruido diferentes, motivo por el cual

se sugiere que se realice un estudio detallado del paquete para conocer con exactitud

cual serıa el impacto que tendrıa sobre las trayectorias de GPS.

• Recomendacion 3: Debido a la variedad de algoritmos de simplificacion de datos

que pueden funcionar en base a trayectorias vehiculares GPS, los resultados del ac-

tual trabajo de investigacion pueden utilizarse como bases para otros estudios de

investigacion y encontrar opciones de soluciones para reducir el ruido y la simplifi-

cacion de trayectorias GPS.

• Recomendacion 4: Se recomienda que se hagan estudios a otros tipos de filtro co-

mo lo es el filtro de partıculas, Los cuales son apropiados para disminuir el ruido

presente en las trayectorias, ademas de que se utilicen algun tipo de procedimiento

comparativo para poder determinar la efectividad de esta.

• Recomendacion 5: Para trabajos futuros se propone usar metodos matematicos que

permitan identificar porcentajes de circularidad en las diferentes bases de datos que

se procedan a descargar en los diferentes repositorios y bases de datos simuladas.

68

REFERENCIAS BIBLIOGRAFICAS

Referencias

Aguilar, L. J. (2016). Big data, analisis de grandes volumenes de datos en organizaciones.

Alfaomega Grupo Editor.

Alvarado Maldonado, A. (2016). La recta.

Arias, F. G. (2012). El proyecto de investigacion. introduccion a la metodologıa cientıfica. 6ta.

Fidias G. Arias Odon.

Astudillo Leon, J. P., y Delgado Tello, E. G. (2012). Sistema de localizacion monitoreo y

control vehicular basado en los protocolos gps/gsm/gprs (B.S. thesis).

Avello Martınez, R., y Seisdedo Losa, A. (2017). El procesamiento estadıstico con r en la

investigacion cientıfica. MediSur, 15(5), 583–586.

Cabello, M. V. N. (2010). Introduccion a las bases de datos relacionales. Vision Libros.

Camargo-Vega, J. J., Camargo-Ortega, J. F., y Joyanes-Aguilar, L. (2015). Conociendo big

data. Facultad de Ingenierıa, 24(38), 63–77.

Campoverde, V. A., Mera, A. A., Escalante, C. A., y Carrasco, J. G. (2020). Analisis de

trayectoria gps para la construccion de ciudades inteligentes. International Journal of

Innovation and Applied Studies, 29(3), 743–751.

Chalen Echeverrıa, A. C., y Vasquez Choez, A. H. (2020). Propuesta de simplificacion de

puntos en trayectorias gps con el uso de informacion topologica de la red de carreteras.

(B.S. thesis). Universidad de Guayaquil. Facultad de Ciencias Matematicas y Fısicas . . . .

Espejo, M. R. (2017). Estimacion de la desviacion estandar. Estadıstica Espanola, 59(192),

37–44.

Fallas, J. (2002). Sistema de posicionamiento global. Universidad Nacional., Laboratorio de

teledeteccion y sistemas de informacion geografica. Escuela de Ciencias Ambientales y

69

Programa Regional en Manejo de Vida Silvestre. Universidad Nacional. Heredia, Costa

Rica.

Garcia Tarira, M. F. (2017). Analisis de algoritmos de compresion: Simplificacion de lineas

douglas-peucker, td-tr, visvalingam (Tesis Doctoral no publicada). Universidad de Gua-

yaquil. Facultad de Ciencias Matematicas y Fisicas . . . .

Hernandez, R., Fernandez, C., y Baptista, P. (2014). Metodologıa de la investigacion mcgraw-

hill. Mexico DF.

Hernandez-Leal, E. J., Duque-Mendez, N. D., y Moreno-Cadavid, J. (2017). Big data: una

exploracion de investigaciones, tecnologıas y casos de aplicacion. TecnoLogicas, 20(39),

17–24.

Ibanez Asensio, S., Gisbert Blanquer, J. M., y Moreno Ramon, H. (2011). El sistema de

coordenadas utm.

Leon, R. A. H., y Gonzalez, S. C. (2020). El proceso de investigacion cientıfica. Editorial

Universitaria (Cuba).

Lopez Valdes, E. (2010). Test de analisis de la precision en determinacion de trayectorias con

gps.

Meratnia, N., y Rolf, A. (2004). Spatiotemporal compression techniques for moving point

objects. En International conference on extending database technology (pp. 765–782).

Miranda Gallegos, J. L. (2017). Analisis de comparacion de rendimiento del algoritmo de

douglas-peucker con la incorporacion del filtro de kalman (Tesis Doctoral no publicada).

Universidad de Guayaquil. Facultad de Ciencias Matematicas y Fisicas . . . .

Miyara, F., Pasch, V., Cabanellas, S., y Yanitelli, M. (2005). Ruido y contenido semantico.

Segundas Jornadas Multidisciplinarias sobre Violencia Acustica Social, Rosario, Argen-

tina.

70

Morales-Velazquez, M. I., Aparicio, J., y Valdes, J. B. (2014). Pronostico de avenidas utilizando

el filtro de kalman discreto. Tecnologıa y ciencias del agua, 5(2), 85–110.

Pascual, A. (2004). Ekf y ukf: dos extensiones del filtro de kalman para sistemas no lineales

aplicadas al control de un pendulo invertido. Monografıa para el curso: Tratamiento

Estadıstico de Senales, 35.

Petris, G., y An, R. (2010). An r package for dynamic linear models. Journal of Statistical

Software, 36(12), 1–16.

Pillajo, C., y Sierra, J. E. (s.f.). El filtro de kalman.

Puertas Ramırez, D. (2018). Analisis y filtrado de datos de sistema de navegacion por satelite

para navegacion autonoma de vehıculos (B.S. thesis).

Quintero, O., y di Sciascio, F. (2005). Aplicacion del filtro de kalman extendido a un proceso

de fermentacion alcoholica en continuo. XI Reunion de Trabajo en Procesamiento de la

Informacion y Control RPIC.

Ramırez, A. S. (2003). El filtro de kalman. Documento de trabajo del Banco Central de Costa

Rica, elaborado en la Division Economica, Departamento de Investigaciones Economi-

cas.

Renteria Reyes, F., y Romero Oviedo, H. (2013). Diseno de los objetos de aprendizaje e

implementacion de la tematica de teoria de grafos aplicando tecnologias de informacion

y comunicacion tic para la asigantura de estructura de datos y analisis de algoritmos.

(Tesis Doctoral no publicada). Universidad Industrial de Santander, Escuela De Ing. De

Sistemas.

Sarrıa, F. A. (s.f.). Programacion en sql con postgresql. lınea]. Available: http://www. um.

es/geograf/sigmur/sigpdf/postgresql. pdf .

Stallman, R. (2004). Software libre para una sociedad libre. Madrid: Traficantes de Suenos,

71

2004.

Turcotte, A., y Vitek, J. (2019). Towards a type system for r. En Proceedings of the 14th

workshop on implementation, compilation, optimization of object-oriented languages,

programs and systems (pp. 1–5).

Villa, M. M., y Yanez, R. E. S. (2017). Fundamentos de la reduccion de ruido en imagenes.

JOVENES EN LA CIENCIA, 3(2), 2531–2536.

Visvalingam, J., Wang, H., Youssef, M. K., Devos, J., Gill, C. O., y Yang, X. (2016). Spatial

and temporal distribution of escherichia coli on beef trimmings obtained from a beef

packing plant. Journal of food protection, 79(8), 1325–1331.

Zambrano, G. R., y Veliz, R. N. H. (2016). Aplicaciones de algoritmos de trayectorias gps

en gadgets/[gps trajectories algorithms applications in gadgets]. International Journal of

Innovation and Applied Studies, 16(3), 549.

Zheng, Y., y Zhou, X. (2011). Computing with spatial trajectories. Springer Science &

Business Media.

72

BIBLIOGRAFIA

Xie, Z., Wang, H.,& Nu, L. (2011, June). The improved Douglas-Peucker algorithm based on

the contour character. In 2011 19th International Conference on Geoinformatics (pp.

1-5). IEEE.

Arranz Justel, J. J., Sanchez Tamargo, D., & Novoa Plasencia, A. (2010). ESTUDIO DE PRO-

CESOS Y HERRAMIENTAS APLICABLES A LA GENERALIZACION VECTO-

RIAL DE ENTIDADES LINEALES. Secretariado de publicaciones de la Universidad

de Sevilla, 33.

Brunsdon, C. (2007). Path estimation from GPS tracks.In Proceedings of the 9th International

In Proceedings of the 9th International Conference on GeoComputation.

National Centre for Geocomputation, Maynooth University..

73

Anexo 1.

Planificacion de actividades del proyecto

Elaboracion: Keyla Paulette Cedeno Hermida y Alexander Daniel Mite Orellana.Fuente: Propia.

74

Anexo 2.

Geo-localizacion del problema

Elaboracion: Keyla Paulette Cedeno Hermida y Alexander Daniel Mite Orellana.Fuente: Google Maps.

75

Anexo 3.

Carta de autorizacion del proyecto

76

Anexo 4.

Fundamentacion legal

El proyecto de investigacion sobre ”Analisis de filtro de KALMAN en algoritmos de

simplificacion de trayectorias GPS lineales y no lineales.”se apoya en los siguientes articulos:

ARTICULO DE LALOES

CONTEXTO

ART. 1 AMBITO

Esta Ley regula el sistema de educacion superior en el paıs, a losorganismos e instituciones que lo integran; determina derechos,deberes y obligaciones de las personas naturales y jurıdicas, y es-tablece las respectivas sanciones por el incumplimiento de las dis-posiciones contenidas en la Constitucion y la presente Ley.

ART. 2 OBJETOEsta Ley tiene como objeto definir sus principios, garantizar el derecho ala educacion superior de calidad que propenda a la excelencia, al accesouniversal, permanencia, movilidad y egreso sin discriminacion alguna.

Elaboracion: Keyla Cedeno, Alexander Mite.Fuente: Ley Organica de Educacion Superior.

CONSTITUCION DELA REPUBLICA DELECUADOR

CONTEXTO

ART. 350

El sistema de educacion superior tiene como finalidad la forma-cion academica y profesional con vision cientıfica y humanista; lainvestigacion cientıfica y tecnologica; la innovacion, promocion,desarrollo y difusion de los saberes y las culturas; la construccionde soluciones para los problemas del paıs, en relacion con los ob-jetivos del regimen de desarrollo.

ART. 385

El sistema nacional de ciencia, tecnologıa; innovacion y saberes ances-trales, en el marco del respeto al ambiente, la naturaleza, la vida, lasculturas y la soberanıa, tendra como finalidad:

1 Generar, adaptar y difundir conocimientos cientıficos y tec-nologicos.

2 Recuperar, fortalecer y potenciar los saberes ancestrales.

3 Desarrollar tecnologicas e innovaciones que impulsen la pro-duccion nacional, eleven la eficiencia y productividad, mejo-ren la calidad de vida y contribuyan a la realizacion del buenvivir.

Elaboracion: Keyla Cedeno, Alexander Mite.Fuente: Constitucion de la Republica del Ecuador.

77

GOBIERNO ACERCADEL USO DE SOFT-WARE LIBRE

CONTEXTO

ARTICULO 1Establecer como polıtica publica para las Entidades de la Administra-cion Publica Central la utilizacion de Software Libre en sus sistemas yequipamientos informaticos.

ARTICULO 2

Se entiende por Software Libre, a los programas de computacion que sepueden utilizar y distribuir sin restriccion alguna, que permitan su accesoa los codigos fuentes y que sus aplicaciones puedan ser mejoradas. Lascaracterısticas de estos programas de computacion contienen las siguien-tes libertades:

a) Utilizacion de programa con cualquier proposito de usocomun.

b) Distribucion de copias sin restriccion alguna.

c) Estudio y modificacion de programas (Requisito: codigofuente disponible)

d) Publicacion del programa mejorado (Requisito: codigo fuentedisponible)

ARTICULO 3

Las entidades de la administracion publica central previa a la instalaciondel software libre en sus equipos, deberan verificar la existencia de capa-cidad tecnica que brinde el soporte necesario para este tipo de software.

ARTICULO 4

Se faculta la utilizacion de software propietario (o libre) unica-mente cuando exista una solucion de software libre que supla lasnecesidades requeridas, o cuando este en riesgo de seguridad na-cional, o cuando el proyecto informatico se encuentre en un puntode no retorno.

ARTICULO 5Tanto para software libre como software libre como software pro-pietario, siempre y cuando se satisfagan los requerimientos.

ARTICULO 6

La subsecretaria de Informatica como organo regulador y ejecu-tor de las polıticas y proyectos informaticos en las entidades deGobierno Central debera realizar el control y seguimiento de esteDecreto.

ARTICULO 7

Encargue de la ejecucion de este decreto los senores MinistrosCoordinadores y el senor Secretario General de la AdministracionPublica y Comunicacion.

Elaboracion: Keyla Cedeno, Alexander Mite.Fuente: Gobierno Acerca del Uso de Software Libre .

78

CODIGO ORGANICO DE LA ECONOMIA SOCIAL DE LOS CONOCIMIENTOS,

CREATIVIDAD E INVENCION

Artıculo 104.- Obras susceptibles de proteccion.-La proteccion reconocida por el presente

Tıtulo recae sobre todas las obras literarias, artısticas y cientıficas, que sean originales y que

puedan reproducirse o divulgarse por cualquier forma o medio conocido o por conocerse. 12.-

SOFTWARE.

Artıculo 131.- Proteccion de software.-El software se protege como obra literaria. Dicha

proteccion se otorga independientemente de que hayan sido incorporados en un ordenador y

cualquiera sea la forma en que esten expresados, ya sea como codigo fuente; es decir, en forma

legible por el ser humano; o como codigo objeto; es decir, en forma legible por maquina, ya sea

sistemas operativos o sistemas aplicativos, incluyendo diagramas de flujo, planos, manuales de

uso, y en general, aquellos elementos que conformen la estructura, secuencia y organizacion

del programa. Se excluye de esta proteccion las formas estandar de desarrollo de software. En

este sentido, los documentos y textos producidos en las Instituciones de Educacion Superior

desarrollados con el objeto de obtener sus grados academicos y/o trabajos de facultad, son

autores intelectuales con el patrocinio de cada institucion, por lo tanto, son acreedores a los

derechos de proteccion intelectual dispuestos en la normativa vigente.

79

Anexo 7.

Validacion de expertos

80

CONSTANCIA DE JUICIO DE EXPERTO

81

INSTRUMENTO DE VALIDACION

82

Validacion del experto N° 2

83


84


85

Validacion del experto N° 3

86


87


88

JOURNAL OF SPATIAL INFORMATION SCIENCE

Number N (2020), pp. xx–yy doi:10.5311/JOSIS.YYYY.II.NNN

RESEARCH ARTICLE

Análisis de filtro de KALMAN enalgoritmos de simplificación de

trayectorias GPS lineales nolineales.

Keyla Paulette Cedeño Hermida and Alexander Daniel MiteOrellana

Facultad de Ciencias Matemáticas y Físicas, Universidad de Guayaquil, Ecuador

October 29, 2020

Abstract: En la actualidad el avance de nuevas tecnologías con lo que respecta a la lo-calización de un objeto en movimiento, se ha podido observar un gran incremento de losdatos de una trayectoria al igual que el ruido de ellas, acumulando muchos puntos de co-ordenadas llegando a redundar y a tener datos inválidos e innecesarios. En el proyecto serealiza el proceso de evaluación de los resultados que han sido adquiridos de las experi-mentaciones realizadas. Además de estudiar cual es el comportamiento que tiene el filtrode Kalman cuando es aplicado a los algoritmos de simplificación (Douglas Peucker y TD-TR) de trayectorias (GPS) lineales y no lineales. Para esto se utilizaron 5 conjuntos de basesde datos, tantos reales como simuladas circulares por motivos de pruebas. Para la vali-dación de los resultados se evaluaron 3 tipos de métricas como son: el tiempo de ejecución,margen de error y la razón de compresión. Se concluye que al aplicar métodos estadísticosde la media y desviación estándar donde se obtuvieron resultados favorables con el filtrode kalman aplicados al algoritmo TD-TR, pero además se pudo observar que en tiempo deejecución el algoritmo de Douglar Peucker destaca muchos más en la investigación.

Keywords: simplificación, ruido, simulada, filtrado, métricas.

1 Introducción

Sin duda la tecnología ha llegado a formar parte de la vida cotidiana y cada día que pasa seva convirtiendo en una herramienta de trabajo impresindible para todos. Dentro de lo que

© by the author(s) Licensed under Creative Commons Attribution 3.0 License CC©

2 CEDENO, MITE

ofrece el mundo tecnológico, uno de los campos que a diario se presenta necesario es el delas trayectorias GPS, que a manera de estudio consta de varios subtemas muy importantespara el funcionamiento óptimo. En el presente artículo se resalta la problemática que surgeal filtrar datos de trayectorias vehiculares. Al obtener los resultados de los algoritmos desimplificación, se observa que el algoritmo cumple con su función y presenta trayectoriasbasadas en la información que se obtiene del conjunto de datos, pero, al aplicar el filtro deKalman a estos mismos algoritmos, se observa una diferencia favorable, ya que lo que haceel filtro es segmentar la ruta de manera óptima, filtrando la información del conjunto dedatos (latitud y longitud) usadas para la experimentación y demostración de los diferentesresultados obtenidos con y sin el filtro de kalman.

El filtro es un procedimiento matemático que opera por medio de un mecanismo depredicción y corrección. En esencia el algoritmo pronostica el nuevo estado a partir de suestimación previa añadiendo un término de corrección proporcional al error de predicción,de tal forma que éste último es minimizado estadísticamente. [3]

El objetivo del artículo es implementar el filtro de Kalman en algoritmos de simplifi-cación en línea para mejorar la reducción del ruido en trayectorias GPS lineales y no lin-eales. El proyecto tomará en cuenta la investigación de modelos matemáticos y análisisde filtro Kalman en los algoritmos referente a la disminución de ruidos, teniendo en con-sideración elementos o test estadísticos que ayuden a evaluar e identificar patrones pararealizar criterios con respecto a trayectorias en la ciudad de Guayaquil u otras ciudadescon ayuda de una base datos PostgreSQL que es un lenguaje de base de datos normal-izado, utilizado por la gran mayoría de los servidores de bases de datos que manejan basesde datos relacionales u objeto-relacionales que muestre imágenes de trayectorias reales. [4]El resto del documento está estructurado de la siguiente manera. La sección 2 describe laliteratura sobre los algoritmos de simplificación de trayectorias e información referente alfiltro Kalman. La sección 3 presenta la implementación de los algoritmos de simplificaciónde trayectorias en datos que ya han sido filtrados por medio de Kalman y la evalución delos datos obtenidos después del proceso anteriormente mencionado. En la sección 4 se en-cuentra los resultados constituidos por la media y desviación de los datos con relación a lasmétricas. Y finalmente en la sección se encuentran las conclusiones del trabajo realizado.

2 Revisión de literatura

2.1 Algoritmos de simplificación de trayectorias

La evolución constante de la tecnología con relación a la ubicación geográfica y los múlti-ples requerimientos de usuarios exigiendo precisión y exactitud a la hora de localizar unobjeto en movimiento, han tenido como consecuencia el crecimiento de la información detrayectorias al igual que el ruido de ellas, acumulando muchos puntos de coordenadasllegando a redundar y a tener datos inválidos e innecesarios. [5]

Para evitar la acumulación de puntos de coordenadas innecesarios en las bases dedatos se emplea el algoritmo de Douglas-Peucker propuesto en 1973 por David Douglasy Thomas Peucker. Éste es la notación más popular y usada hoy en día para la reducciónde líneas debido a que minimiza el número de puntos en una curva parcialmente represen-tada por una serie de puntos. Algunos cartógrafos consideran que el algoritmo de DouglasPeucker es uno de los algoritmos de generalización de líneas más precisos disponibles, perootros piensan que es demasiado común en términos de tiempo de procesamiento. [1]

www.josis.org

SHORT TITLE FOR JOSIS ARTICLE 3

El algoritmo TD-TR se basa en un funcionamiento parecido al del algoritmo de Douglas– Peucker, el cual fue propuesto por Nirvana Meratnia y Rolf de By en su obra “Técnicas decompresión espacio temporal para objetos en movimiento”. La diferencia con el algoritmoanteriormente nombrado es que en esta notación la simplificación no solo se realiza con laposición de un objeto (latitud y longitud), si no que se le incluye una técnica de mediciónde distancia en relación al tiempo en que se realizó el recorrido desde un punto a otro de latrayectoria. Esta medición presenta otra diferencia entre el algoritmo de Douglas Peuckery TD–TR, debido a que ya no se calculará necesariamente una distancia perpendicular, sino que ahora se calcula la distancia entre dos puntos temporalmente sincronizadas en eltiempo.

2.2 Filtro Kalman

El filtro de Kalman consiste en un conjunto de ecuaciones matemáticas que proveen unasolución recursiva óptima, por el método de mínimos cuadrados. La meta de esta soluciónconsiste en calcular un estimador lineal, insesgado y óptimo del estado 3 de un sistema ent con base en la información disponible en t − 1, y actualizar, con la información adicionaldisponible en t, dichas estimaciones. El filtro se desempeña suponiendo que el sistemapuede ser descrito a través de un modelo estocástico lineal, en donde el error asociadotanto al sistema como a la información adicional que se incorpora en el mismo tiene unadistribución normal con media cero y varianza determinada. [3] La solución es óptima porcuanto el filtro combina toda la información observada y el conocimiento previo acerca delcomportamiento del sistema para producir una estimación del estado de tal manera que elerror es minimizado estadísticamente. El término recursivo significa que el filtro recalculala solución cada vez que una nueva observación o medida es incorporada en el sistema. [3]El filtro de Kalman trabaja principalmente con dos tipos de variables: primero se encuentrael Vector de Estados Estimados. Dentro de sus componentes se incluyen:

• Variables de interés: tales como la posición, velocidad, aceleración, razón de cambioen la aceleración, entre otras. Estas son las que se requieren o se necesitan.

• Variables no intrínsecas: aquellas que por las que no se tiene especial interés, sin em-bargo son necesarias en el proceso de estimación. El tipo de variables pueden incluir,por ejemplo, los errores por disponibilidad selectiva de los satélites GPS. General-mente no se necesita conocer sus valores, pero se esta obligado a calcularlos paramejorar la estimación del receptor.

• Variables dinámicas: aquellas definidas para ciertas aplicaciones específicas, comomedidas para ciertos sensores. Por ejemplo, en el caso de un acelerómetro o un giro-scopio,el filtro puede tener componentes de aceleración y rotación angular.

También se encuentra la matriz de covarianza, medición de la incertidumbre en la esti-mación : Estas ecuaciones son usadas para propagar el modelo de la matriz de covarianza,y manejar la incertidumbre, tomando en cuenta como el ruido de los sensores y la dinámicaincierta, contribuyen en la incertidumbre total para el cálculo de la estimación de los esta-dos del sistema.

JOSIS, Number N (2020), pp. xx–yy

4 CEDENO, MITE

3 Implementación y evaluación

Se procede a realizar el análisis de los resultados obtenidos al emplear el filtro de Kalmanen los algoritmos de simplificación como lo son Douglas Peucker y TD-TR, calculando losdiversos parámetros tal como la razón de compresión, tiempo de ejecución y margen deerror de las diferentes bases de datos que contienen trayectorias GPS con información real.Además, se cuenta con datos de trayectorias circulares simuladas en el caso de Guayaquily Quito que por razones de estudio y experimentación se procedió a crearla con datos delprograma Google Earth Pro como MapSource, ambos programas son gratuitos. Se realizala experimentación de los datos originales con algoritmos de simplificación y datos orig-inales aplicando filtro Kalman y algoritmos de simplificación, con los datos que fueronencontrados en los repositorios web además de los datos de coordenadas GPS simulados.Con ayuda de los experimentos llevados a cabo se identificó la linealidad de una trayecto-ria, además del cambio de los datos originales cuando son procesados por los algoritmosde simplificación. También se observó el comportamiento de los datos al realizar el procesode filtro de Kalman para después realizar la simplificación con los algoritmos de DouglasPeucker y TD-TR. Se tomó como variable dependiente la reducción de ruidos en trayecto-rias lineales y no lineales y como variable independiente filtro de Kalman en algoritmos desimplificación.

Para el estudio de los algoritmos con el filtrado de los resultados obtenidos se evaluarondiferentes métricas como tiempo de ejecución, margen de error y razón de compresión. Conel tiempo de ejecución se conoce el tiempo que tomó cada simplificación de los conjuntode datos. Con el margen de error se obtiene cuanta distorsión hay entre la trayectoriaoriginal y la simplificada. La razón de compresión permitirá conocer el porcentaje de datosresultantes de la trayectoria original.

[2] “Cualquier conjunto de elementos que tengan una o más propiedades en comúndefinidas por el investigador y que puede ser de toda la realidad, hasta un grupo muyreducido de fenómenos”. Podemos definir a la población como el conjunto de informaciónque se encuentra en el Data Set el cual tendrá como finalidad ser estudiado y analizadopara su respectiva experimentación.

Se utilizará como base poblacional la información obtenida del Data Set público“Trayectorias GPS de Microsoft GeoLife” el cual contiene información de trayectorias GPSde ciudades como Brasil, Beijing y California, a continuación en la tabla 1 se presenta conclaridad la población total de los conjuntos de datos utilizado.

Población Cantidad de población 1 % de la muestra Cantidad de muestra a usarBeijing 6.345.904 0.98% 62.138Brasil 18.107 77.85% 14.096

California 914.684 100% 914.684Guayaquil 1.460 100% 1.460

Quito 1.460 100% 1.460

Table 1: Tamaño de la muestra

Se aplicó el filtro de Kalman con ayuda del paquete en R llamado DLM a los datosoriginales en el cuadro que se muestra a continuación se observa el número de puntosfiltrados y el número puntos originales de longitud y latitud que coinciden con el porcentajede los mismos, además de mostrar la cantidad puntos filtrados con puntos originales que

www.josis.org


no coinciden. En la tabla 2 se muestran los porcentajes de coincidencia comparando lastrayectorias originales con las trayectorias aplicado el Filtro Kalman.

Como se detalla en la tabla 2 la base de datos que tuvo una mayor reducción de rui-dos en su trayectoria fue la de California teniendo un porcentaje de coincidencia tanto delongitud como latitud de 0.07% y 0.06% respectivamente, mientras que la base de datosde Beijing muestra valores de coincidencia superiores al 8% lo cual se puede concluir queexistió menor reducción de ruido.

Nombre delos conjuntosde datos

Cantidadde puntos

Puntoscoinci-den

Puntos nocoinciden

Puntosen %coinciden

Beijing 62.138 longitudlatitud

5.1655.310

56.97356.828

8.31%8.55%

Brasil 14.096 longitudlatitud

138106

13.95813.990

0.98%0.75%

California 914.684 longitudlatitud

596571

914.088914.113

0.07%0.06%

Guayaquil 1.460 longitudlatitud

594575 866 885 40.68%

39.38%

Quito 1.460 longitudlatitud

887637 573 823 60.75%

43.63%

Table 2: Filtro Kalman aplicado en los conjuntos de datos.

Con respecto a las base de datos simuladas circulares Quito, se presentó valores decoincidencia elevados debido a que son trayectorias de menor volumen, por lo tanto enlongitud y latitud indica que existió menor reducción de ruido con porcentajes de 60.75%en longitud y 43.63% en latitud.

Se procedió a aplicar a los datos de trayectorias vehiculares los algoritmos de simpli-ficación a utlizar. Se realizaron diferentes experimentos con 5 valores de epsilon el cualpermite medir la reducción de puntos que tendrá el algoritmo. Al momento de realizarla comparación con los diferentes valores de epsilon se escogió el que mejor se ajusta aresultados de simplificación, debido a que cada epsilon recopila valores diferentes en losdatos de trayectorias.

Una vez ejecutado el script que contiene el algoritmo de simplificación Douglas Peuckery TD-TR en lenguaje de programación R se obtuvieron los siguientes resultados mostradosa continuación.En la tabla 3 se observan la cantidad de puntos resultantes de la simplifi-cación de los conjuntos de datos, su cantidad de puntos iniciales y la tolerancia que uti-lizada en los algoritmos.

Nombre del conjutosde datos

Cantidad de pun-tos iniciales

Puntos finalesde RDP

Puntos finalesde TD-TR Epsilon

Beijing 62.138 11.386 16.895 0.001Brasil 14.096 1.117 1.505 0.001California 914.684 61.562 87.960 0.0004Guayaquil 1.460 40 491 0.00001Quito 1.460 79 364 0.00001

Table 3: Resultados de la simplificación con los algoritmos y épsilon escogido


6 CEDENO, MITE

3.1 Evaluación del filtro de Kalman con los algoritmos de simplificaciónpor medio de métricas

3.1.1 Filtro Kalman con el Algoritmo de Douglas Peucker

Se aplicó el filtro de Kalman DLM en los datos originales de las respectivas bases de datosincluyendo las bases de datos circulares simuladas. Una vez obtenido los registros suaviza-dos (disminución de ruido) se aplicó el algoritmo de simplificación de Douglas Peucker.Enla tabla 4 se observan los valores de las métricas que presenta el algoritmo de RDP enrelación con cada uno de los conjuntos de datos simplificados.

Nombre del conjuntode datos Tiempo(seg)

Razón decompre-sión(%)

Margen de er-ror Tipo

Beijing 1952 seg 80.82% 0.011 RealBrasil 102 seg 91.37% 0.006 RealCalifornia 20595 seg 93.11% 0.001 RealGuayaquil 11.73 seg 43.49% 0.0003 SimuladaQuito 9.58 seg 56.10% 0.290 Simulada

Table 4: Resultados de la evaluación con las métricas en la simplificación usando el algo-ritmo RDP

Se observa en la tabla 4 el tiempo de ejecución en la base de datos de California es mayorcon un valor de 20595 en segundos con respecto a la base de datos de Brasil el que obtuvoun valor de 102 en segundos, con respecto a las bases simuladas circulares que presentanvalores bajos de 11.73 y 9.58 en segundos debido a la cantidad de registros que se tiene decada una de ellas.

Con respecto a la razón de compresión se observa que la base de datos de Californiatuvo una mayor compresión en los datos con un valor de 93.11% mientras que existió unamenor comprensión en los datos en la base de datos de Beijing con un valor de 80.82%,mientras que en las bases simuladas en Quito existe una mayor compresión con un valorde 56.10%.

Concluyendo con la métrica de margen de error la base de datos que presento menordistorsión en los puntos es la de California con un valor de 0.006 mientras que la base dedatos de Beijing presenta una mayor distorsión en los datos con un valor de 0.011, conrespecto a la base simulada circular de Guayaquil presenta un valor de distorsión en lospuntos con 0.0003 a diferencia de Quito que supera ese porcentaje presentando un valormayor.

3.1.2 Filtro Kalman con el Algoritmo de TD-TR

Se aplicó el filtro de Kalman DLM en los datos originales de las respectivas bases de datosincluyendo las bases de datos circulares simuladas, una vez obtenido los registros suaviza-dos (disminución de ruido) se aplica el algoritmo de simplificación TD-TR.

Se observa en la tabla 5 el tiempo de ejecución varía en cada base datos, teniendo encuenta que la base de datos de California presenta mayor valor con 11029 en segundosmientras que Brasil presenta un valor menor de 76,85 en segundos, con respecto a lasbases de datos circulares simuladas presentan valores de 7.80 y 6.70 en segundos respec-

www.josis.org


tivamente. Con la siguiente métrica de razón de comprensión se puede observar que labase de datos de California supera el 95.19% en comprensión de puntos a diferencia de lasbases simuladas de Guayaquil y Quito que presentan valores de comprensión inferiores de65.34% y 75.75% respectivamente debido a la dispersión de los puntos.

Por último, tenemos la métrica de margen de error en el cual las bases de Beijing y Cal-ifornia presentan valores similares lo cual indica que en ambas la distorsión de los puntosha sido tan significativa a diferencia de Brasil que tuvo un porcentaje de 0.0003 indicandouna menor distorsión, en las bases de datos simuladas circulares Guayaquil con respecto aQuito presenta mayor distorsión en los puntos con un valor de 0007.

Nombre del conjuntode datos

Tiempo(seg) Razón de compre-sión(%)

Margen de er-ror

Tipo

Beijing 368 seg 72.62% 0.013 RealBrasil 78.85 seg 88.43% 0.0003 RealCalifornia 11029 seg 95.19% 0.015 RealGuayaquil 7.80 seg 65.34% 0.007 SimuladaQuito 6.71 seg 75.75% 0.001 Simulada

Table 5: Resultados de la evaluación con las métricas en la simplificación usando el algo-ritmo TD-TR

4 Resultados

4.1 Media y desviación estándar de los datos simplificados con relacióna las métricas.

4.1.1 Media de los algoritmos de simplificación.

Como se muestra en la tabla 6 se calculó la media de las métricas de cada base de datos tantoreal como simuladas ya aplicados los algoritmos de simplificación, en el cual se obtuvieronlos siguientes resultados:

Tiempo de ejecución(Seg) Razón de compresión % Margen de errorDouglas Peucker 5701 seg 91.77% 0.007

TD - TR 2985 seg 78.79% 0.005

Table 6: Media Douglas Peucker TD-TR

Aplicado el cálculo de la media en las métricas de algoritmos de simplificación, se mues-tra en la figura 1 que Douglas Peucker es mayor con un tiempo de 5701 segundos conrespecto a TD-TR que muestra un tiempo de 2985 segundos, concluyendo que en tiempode ejecución TD-TR presenta menor tiempo de respuesta. Mientras con lo que respectaa razón de compresión Douglas Peucker tiene un valor de 91.77% a diferencia de TD-TRque presenta un valor de 78.79%, concluyendo que Douglas Peucker es óptimo en lo querespecta a comprensión de puntos. Por último, en margen de error Douglas Peucker pre-senta un valor de 0.007 mientras que TD-TR muestra un valor de 0.005 concluyendo queTD-TR ofrece una menor distorsión de puntos.


8 CEDENO, MITE

Figure 1: Media de los algoritmos de simplificación Douglas Peucker y TD-TR

4.1.2 Desviación Estándar de los algoritmos de simplificación.

La desviación estándar es la medida de dispersión en el cual se indica que tan dispersosse encuentran los datos con respecto a la media. En la tabla 7 se presenta los resultadosobtenidos del filtro de Kalman con los algoritmos de simplificación.


TD - TR 6393 seg 10.60% 0.006

Table 7: Desviación Estándar Douglas Peucker y TD-TR

Ya realizado el cálculo de la desviación estándar se obtuvo que en el tiempo de ejecucióntuvo como mayor valor el algoritmo de Douglas Peucker dando como resultado 11606 elcual se encuentra disperso con respecto a la media, a diferencia del algoritmo TD-TR quemuestra un resultado de 6393 el cual también se encuentra disperso con relación a la mediapero en menor cantidad.

Con respecto a la razón de comprensión en los algoritmos de simplificación de DouglasPeucker y TD-TR muestran valores de 5,96 y 10,60 respectivamente, lo cual muestra unamenor dispersión en los datos con relación a la media.

Los resultados que se obtuvieron en el margen de error en el algoritmo de DouglasPeucker dio como resultado en la desviación estándar un valor de 0,005 el cual muestra unamenor dispersión en los datos, mientras que en el algoritmo de TD-TR da como resultadoun valor de 0,006 el cual es mayor a relación con la media pero que no se encuentra alejadoen la dispersión.

www.josis.org


Figure 2: Desviación estandar de los algoritmos de simplificación Douglas Peucker y TD-TR

4.1.3 Media del Filtro de Kalman con los algoritmos de simplificación.

Como se muestra en la tabla 8 se calculó la media de las métricas de cada base de datos tantoreal como simuladas ya aplicando el filtro de Kalman y los algoritmos de simplificación, enel cual se obtuvieron los siguientes resultados:


TD - TR 2298 seg 79.47% 0.007

Table 8: Media del Filtrado Kalman con los algoritmo de simplificacion Douglas PeuckerTD-TR

Aplicado el cálculo de la media en el filtro de Kalman con algoritmos de simplificaciónen sus respectivas métricas, se muestra en la figura 3 que Douglas Peucker es mayor conun tiempo de 4534 segundos con respecto a TD-TR que muestra un tiempo de 2298 segun-dos, concluyendo que en tiempo de ejecución TD-TR presenta menor tiempo de respuesta.Mientras con lo que respecta a razón de compresión Douglas Peucker tiene un valor de72.98% a diferencia de TD-TR que presenta un valor de 79.47%, concluyendo que TD-TR esóptimo en lo que respecta a comprensión de puntos. Por último, en margen de error Dou-glas Peucker presenta un valor de 0.062 mientras que TD-TR muestra un valor de 0.007concluyendo que TD-TR ofrece una menor distorsión de puntos.


10 CEDENO, MITE

Figure 3: Media del Filtrado Kalmann con los algoritmos de simplificación DouglasPeucker y TD-TR

4.1.4 Desviación Estándar del Filtro de Kalman con algoritmos de simplificaciónn.

Aplicado el cálculo de la desviación estándar en las diferentes métricas utilizando el filtrode Kalman con los algoritmos de simplificación a continuación en la tabla 9 se presentanlos resultados obtenidos:


TD - TR 4883 seg 12.12% 0.007

Table 9: Desviación Estándar Douglas Peucker y TD-TR

Realizado los respectivos cálculos de la desviación estándar se obtuvo como resultadoen el tiempo de ejecución que el filtro de Kalman con el algoritmo de simplificación DouglasPeucker tiene mayor dispersión con respecto a la media con un valor de 9017 mientrasque el filtro de Kalman con el algoritmo de simplificación de TD-TR también tiene mayordispersión pero en menor cantidad con un valor de 4883.

Mientras que en la razón de compresión ambos resultados mostraron valores menoreslo cual indica que existe menor dispersión de puntos con valores de 22,13 y 12,12 respecti-vamente.

Por último tenemos la métrica de margen de error en donde el filtro con el algoritmode Douglas Peucker muestra un valor de 0,128 indicando que existe mayor dispersión delos puntos con respecto a la media a diferencia del filtro con el algoritmo de TD-TR quepresenta un valor de 0,007 que es el mismo valor de media indicando que no existe nimenor, ni mayor dispersión de los puntos.

www.josis.org


Figure 4: Desviación Estándar del Filtrado Kalmann con los algoritmos de simplificaciónDouglas Peucker y TD-TR

En la figura 4 se observa los valores de la desviación estándar por cada una de lasmétricas que se evaluaron para cada uno de los algoritmos.

Realizado los respectivos cálculos de la desviación estándar se obtuvo como resultadoen el tiempo de ejecución que el filtro de Kalman con el algoritmo de simplificación DouglasPeucker tiene mayor dispersión con respecto a la media con un valor de 9017 seg mientrasque el filtro de Kalman con el algoritmo de simplificación de TD-TR también tiene mayordispersión, pero en menor cantidad con un valor de 4883 seg, como en ambas existe var-iedad en los datos los valores de la media no son confiables.

Mientras que en la razón de compresión ambos resultados mostraron valores menorescon respecto a la media lo cual indica que existe menor dispersión de puntos con valoresde 22.13% y 12.12% respectivamente, presentando que dichos valores se encuentran másagrupados con el valor de la media.

Por último, tenemos la métrica de margen de error en donde el filtro con el algoritmode Douglas Peucker muestra un valor de 0.128 indicando que existe mayor dispersión delos puntos con respecto a la media a diferencia del filtro con el algoritmo de TD-TR quepresenta un valor de 0.007 que es el mismo valor de media indicando que no existe nimenor, ni mayor dispersión de los puntos.

5 Conclusiones

Al finalizar el presente estudio en base al análisis del filtro de Kalman con algoritmos desimplificación se logró concluir que, en la experimentación inicial los 5 conjuntos de datosa usar aplicado el método de la pendiente, en el cual indica que si el valor de la pendiente


12 CEDENO, MITE

en cada punto es igual, se trata de una trayectoria lineal, el estudio realizado indicó que el90% de los segmentos de los conjuntos de datos son no lineales.

Para validación de resultados en el trabajo de investigación se aplicó los métodos es-tadísticos de la media y deviación estándar dando como mejor resultado el filtro de Kalmancon el algoritmo de TD-TR, pero en tiempo de ejecución el algoritmo de Douglas Peuckerdestaca en el estudio.

6 Agradecimientos

El autor desea agradecer al personal académico de la Universidad de Guayaquil, quienessupieron impartir con mucho esfuerzo sus conocimientos.

References

[1] GARCIA TARIRA, M. F. Análisis de Algoritmos de Compresión: Simplificación de LineasDouglas-Peucker, TD-TR, Visvalingam. PhD thesis, Universidad de Guayaquil. Facultadde Ciencias Matematicas y Fisicas . . . , 2017.

[2] LEÓN, R. A. H., AND GONZÁLEZ, S. C. El proceso de investigación científica. EditorialUniversitaria (Cuba), 2020.

[3] RAMÍREZ, Á. S. El filtro de kalman. Documento de trabajo del Banco Central de Costa Rica,elaborado en la División Económica, Departamento de Investigaciones Económicas (2003).

[4] SARRÍA, F. A. Programación en sql con postgresql. línea]. Available: http://www. um.es/geograf/sigmur/sigpdf/postgresql. pdf .

[5] ZAMBRANO, G. R., AND VELIZ, R. N. H. Aplicaciones de algoritmos de trayectoriasgps en gadgets/[gps trajectories algorithms applications in gadgets]. International Jour-nal of Innovation and Applied Studies 16, 3 (2016), 549.

www.josis.org

universidad de guayaquilrepositorio.ug.edu.ec/bitstream/redug/49499/1/b-cisc-ptg...de autor en forma...

Documents