Tesis Doctorado
Permanent URI for this collection
Browse
Browsing Tesis Doctorado by Subject "Algoritmos Computacionales"
Now showing 1 - 2 of 2
Results Per Page
Sort Options
Item Algoritmos para el cálculo de la cadena media.(Universidad de Concepción., 2019) Sánchez Mirabal, Pedro Aniel; Seco Naveiras, Diego; Abreu Salas, José IgnacioEl problema de la cadena media es NP-hard para muchas de sus formulaciones, específicamente cuando se emplea la distancia de edición de Levenshtein. Las heurísticas más competitivas aplicadas a este problema usan algoritmos basados en hacer perturbaciones sucesivas a una solución inicial, estos algoritmos son llamados perturbation-based iterative algorithms. La cadena inicial y la política para establecer un orden entre las posibles ediciones son esenciales en la eficiencia de estos algoritmos. En esta tesis se abordan estos sub-problemas. Primero, se estudia cómo una mejor clasificación de las posibles perturbaciones atendiendo a su calidad, tiene efectos en la convergencia de los algoritmos, como consecuencia de esto, se obtiene un nuevo ranking de perturbaciones, que no solamente tiene en cuenta lo que ocurre en relación con las cadenas en las que dicha perturbación está presente, si no, también con respecto al resto de las cadenas del conjunto. Luego, se muestra como la cadena inicial influye en el proceso, analizando principalmente dos variantes de inicialización para estos algoritmos, la cadena perteneciente al conjunto con menos distancia al resto, y la media de un subconjunto de la entrada del algoritmo. Este subconjunto mencionado anteriormente es determinado por los vecinos obtenidos al aplicar el algoritmo Half Space Proximal (HSP) a la cadena mediana del conjunto. De la misma forma, se proponen alternativas para la reducción del conjunto de datos a procesar, sustituyéndolo por un subconjunto de éste, con el fin de disminuir los costes computacionales de los algoritmos. Finalmente, se valida la calidad de los algoritmos obtenidos mediante algoritmos de optimización que resuelven este problema de forma óptima. En el proceso de validación se lleva a cabo un gran número de experimentos que dan soporte a las conclusiones obtenidas. En estos experimentos se muestra que el error de los algoritmos diseñados se encuentra bien acotado, obteniendo soluciones óptimas para los casos en que SAT o ILP logran determinar el ´óptimo. En los casos en que el óptimo no es determinado por SAT o ILP, la solución encontrada es mejor o igual, logrando obtenerla en un tiempo de cómputo menor.Item Multidimensional analysis for hyperspectral imaging systems A time, space and wavelength approach(Universidad de Concepción., 2014) Meza Narváez, Pablo Francisco; Torres Inostroza, SergioEn esta tesis, se propone un novedoso modelo de degradación a fín de imágenes para cámaras hiperespectrales de barrido (PBHCs), siguiendo un enfoque optoelectrónico y generando una representación matemática precisa del proceso de adquisición hiperespectral. El modelo de degradación de imagen es lineal y los parámetros asociados al ruido de franjas (SN) son asumidos espacialmente correlacionados, espectralmente independientes y desvinculados de la respuesta espectral de la cámara. La aplicabilidad de estos supuestos se verifió mediante una caracterización experimental de las cámaras hiperespectrales a nuestra disposición. Además, se asume que la información espacial, espectral, y temporal son altamente redundante debido a la alta resolución espectral y al rápido barrido temporal de las PBHCs modernas. De esta manera, y con base en el modelo de observación propuesto, se han desarrollado dos nuevos algoritmos multidimensionales de compensación de ruido de franjas (SNC) para PBHCs, los algoritmos multidimensionales de redes neuronales (NN) y de ajuste de momentos (MM). Los algoritmos explotan simultáneamente la información espacial y temporal contenida en una escena objetivo, así como la información espectral contenida en las imágenes espectrales adyacentes. La habilidad de los algoritmos de estimar y compensar los parámetros de SN, sujetos a las restricciones de la radiación de entrada, fue demostrada matemáticamente.Un algoritmo adicional ha sido incluido para relajar el supuesto de redundancia espectral, reduciendo la perdida de resolución espectral en el hipercubo. La aplicabilidad de los algoritmos SNC multidimensionales fue probada con exito en datos hiperespectrales reales adquiridos usando un prototipo de laboratorio, logrando comparativamente mejores imágenes compensadas que sus versiones unidimensionales. Se ha implementado una configuración experimental, basada en las cámaras hiperespectrales Photonfocus Hurricane y Xeva Xenics, para adquirir datos en el rango de 400-1000 [nm] y 900-1700 [nm], respectivamente. Vale la pena mencionar que ambas cámaras presentan patrones distintivos de ruido en términos de estructura espectral. Además, se utilizó una plataforma móvil para simular y sin-cronizar el procedimiento de barrido de las cámaras y, para fines de calibración, una lámpara de tungsteno uniforme fue instalada para asegurar una radiancia espectral igual entre las diferentes bandas. Además, para probar los algoritmos, se utilizaron los datos crudos recolectados desde el sensor CCD Earth-observing CHRIS/PROBA.