Transformada de Fourier aplicada alalineamiento de imagenes multidimensionales

en GPUAlvaro Ordonez1, Francisco Arguello2 y Dora B. Heras1

Resumen— La alineacion de imagenes es una ta-rea previa fundamental en numerosas aplicacionesde imagenes. La gran cantidad de informacion quecontienen las imagenes multidimensionales puede serutilizada para conseguir alineaciones mas precisas.Ademas, la mayorıa de los algoritmos de alineacionignoran el tiempo de computo. En este artıculo pre-sentamos un algoritmo de alineacion de imagenes mul-tidimensionales basado en la transformada rapida deFourier, el analisis de componentes principales y lacombinacion de mapas log-polar. El algoritmo pro-puesto hace uso de la correlacion de fase para recu-perar los parametros que permiten alinear la imagen.Asimismo, se ha realizado una implementacion eficien-te sobre Unidades de Procesamiento Grafico (GPUs).Diferentes tecnicas de optimizacion, como el uso de bi-bliotecas CUDA optimizadas y el uso eficiente de lasdiferentes memorias, han sido aplicadas para obtenerel mejor rendimiento. Como resultado, el algoritmoes robusto y ha sido probado con diferentes imagenesconsiguiendo alineaciones de hasta una escala 6.0× pa-ra todos los angulos, y con una aceleracion de la imple-mentacion paralela en GPU de hasta 165.4× respectode la implementacion secuencial en CPU.

Palabras clave— Imagen multidimensional, alinea-cion de imagenes, teledeteccion, transformada de Fou-rier, GPU, CUDA.

I. Introduccion

ACTUALMENTE, gracias a los ultimos avancestecnologicos, la obtencion de imagenes multi-

dimensionales mediante sensores espectrales es massencilla que hace dos decadas. Estas imagenes se ca-racterizan por estar formadas por cientos de ban-das que cubren un amplio rango del espectro electro-magnetico [1]. Su uso se ha extendido a multitud deaplicaciones como la agricultura [2], control de ca-lidad [3], medicina [4], vigilancia [5], control medioambiental [6] o geologıa entre otras.

La alineacion de imagenes es una tarea previa fun-damental en muchas de estas aplicaciones. El proble-ma estudiado en este artıculo consiste en estimar latransformacion de similitud existente entre una ima-gen de referencia y una segunda imagen de la mis-ma escena pero capturadas en diferentes instantes detiempo. Existen diferentes algoritmos para resolver elproblema de alineacion automatica de imagenes [7],[8], [9].

Los metodos basados en la transformada de Fou-rier (FT) son muy eficientes ya que se usa la trans-formada rapida de Fourier (FFT) para calcular la

1Centro Singular de Investigacion en Tecnoloxıas da Infor-macion (CiTIUS), Universidade de Santiago de Compostela,e-mail: {alvaro.ordonez, dora.blanco}@usc.es.

2Departamento de Electronica e Computacion,Universidade de Santiago de Compostela, e-mail:francisco.arguello@usc.es.

correlacion cruzada entre las dos imagenes. Ademas,estos destacan por su resistencia al ruido, oclusio-nes, y otros defectos tıpicos que se pueden encontraren las imagenes de teledeteccion. Chen, Defrise, yDeconinck [10] propusieron en 1994 un metodo pa-ra alinear imagenes usando un mapa log-polar. Es-te metodo es tambien conocido como Fourier-MellinInvariant Symmetric Phase-Only Matched Filtering(FMI-SPOMF) [11], [12].

Otro enfoque en alineacion de imagenes es el que sebasa en metodos de deteccion de caracterısticas. Es-tos metodos extraen y emparejan caracterısticas re-levantes que son comunes entre las dos imagenes. Lascaracterısticas emparejadas nos permiten determinarla transformacion geometrica que es necesaria paraalinear las imagenes. El metodo Scale-Invariant Fea-ture Transform (SIFT) [13] ha demostrado ser uno delos mejores metodos de extraccion de caracterısticas.Destaca por su robustez ante cambios de iluminaciony de perspectiva, y es invariante a cambios de escalao rotacion. Estas propiedades lo convierten en un ex-celente metodo para la alineacion de imagenes [14],[15], [16]. A partir de la presentacion de SIFT se handesarrollado un gran numero de variantes y extensio-nes del mismo. El metodo Speeded-Up Robust Fea-tures (SURF) [17] fue desarrollado para disminuir elelevado tiempo de ejecucion de SIFT ası como paramejorar la distincion de los puntos caracterısticos.

Los cientos de bandas capturadas por los senso-res multidimensionales pueden ser consideradas co-mo una secuencia de imagenes a diferentes longitu-des de onda. Debido al tiempo de captura requeridoentre una longitud de onda y otra puede ser necesa-rio alinear las diferentes bandas de la imagen. Paraeste proposito en [18] proponen el uso de la informa-cion mutua multivariable como medida de similitud.En [19] han desarrollado metodos basados en la des-composicion mediante wavelets, deteccion de bordes,uso de informacion mutua y emparejamiento de ca-racterısticas para realizar reduccion de dimensionali-dad, alineado, y fusion de imagenes multisensor. En[20] se presenta un metodo basado en la transforma-da de Fourier para alinear las bandas de una imagenrecuperando la escala, rotacion y traslacion, y po-der ası construir cubos multidimensionales coheren-tes. Un esquema similar es el que se propone en [21].En cambio en [22] se presenta un metodo de alinea-miento de bandas basado en diferentes descriptoresde caracterısticas como SIFT, SURF, y Affine-SIFT(ASIFT).

Una tarea diferente es la alineacion de dos image-

Jornadas SARTECO 2017 67

nes multicanal. En [23] se presenta un metodo parala alineacion de dos imagenes multicanal usando unacorrelacion multivariable como medida de similitud.La mayorıa de los metodos de alineacion de este tipode imagenes son especıficos para el alineamiento dedatos medicos, tal como las angiografıas de resonan-cia magnetica (en ingles, ARM) y las imagenes deresonancia medica (en ingles, MRI) [24], [25].

En el campo de la teledeteccion se han propuestovarios metodos para la alineacion de imagenes multi-dimensionales. En [26] usan un algoritmo genetico co-mo tecnica de busqueda para estimar los parametrosoptimos que permiten alinear dos imagenes multies-pectrales. Este enfoque puede ser considerado comouna fusion de diferentes decisiones resultantes de laalineacion de varias bandas. En [27] proponen usarel algoritmo de esperanza-maximizacion (EM) pararesolver el problema de alineacion y fusion de image-nes. Los parametros de alineado son estimados maxi-mizando una funcion condicional de esperanza. [28]presenta un metodo de alineacion basado en la gene-racion de una red de puntos de control a partir dela construccion de una piramide de imagenes de di-ferentes resoluciones. Sin embargo ninguno de estosmetodos esta basado en la transformada de Fourier.

Por otro lado, la mayorıa de estos algoritmos igno-ran el tiempo de computacion. En aplicaciones dondees necesario obtener un resultado en tiempo real, eltiempo de ejecucion es crucial, por ejemplo, en unamision de busqueda y rescate o en control de danosy desastres. Las Unidades de Procesamiento Grafico(GPUs) han demostrado ser muy apropiadas para re-solver eficientemente diferentes problemas en proce-samiento de imagenes multidimensionales [29], [30],[31]. En la literatura podemos encontrar implemen-taciones de algoritmos en GPU para la alineacion deimagenes de 2 y 3 dimensiones [32], [33], [34], [35],pero ninguna de ellas aplicada a imagenes multidi-mensionales las cuales suelen centuplicar la cantidadde datos de una imagen normal y en las cuales existeuna alta correlacion en la informacion espectral.

En este artıculo se presenta la implementacion enGPU del algoritmo para alineacion de imagenes mul-tidimensionales llamado PCA-based HyperspectralFourier-Mellin (PCA-HFM). El metodo explota lainformacion espacial y espectral contenida en las di-ferentes bandas de las imagenes y esta basado en elanalisis de componentes principales (PCA), el algo-ritmo FMI-SPOMF, y la combinacion de mapas log-polar. Ha sido desarrollado en CUDA para obteneruna explotacion eficiente de la arquitectura GPU. Elresto del artıculo se organiza de la siguiente forma.En primer lugar, la Seccion II describe el algoritmo ysu implementacion en GPU. En la Seccion III se pre-sentan y discuten los resultados en terminos de preci-sion de alineado y tiempos de ejecucion. Por ultimo,en la Seccion IV se presentan las conclusiones.

II. Alineacion de imagenesmultidimensionales

En esta seccion se explican las diferentes etapas delalgoritmo PCA-HFM ası como su implementacion enGPU. El algoritmo se compone de 4 etapas (ver Fig.1). En la primera etapa se realiza una reduccion dedimensionalidad quedandonos solo con 8 componen-tes de cada imagen. A continuacion, se calculan losmapas log-polar de cada componente y se aplica lacorrelacion de fase a cada par de mapas. En la terce-ra etapa los diferentes mapas log-polar son combina-dos para integrar la informacion de todos los paresde componentes. Finalmente, en la ultima etapa, seprocesan los picos de mayor valor para volver aplicarla correlacion de fase sobre el dominio cartesiano yobtener la escala, rotacion y traslacion que permitealinear las imagenes.

A continuacion se introducen algunos conceptosfundamentales de programacion en CUDA, y se ex-plica en detalle la implementacion del algoritmo.

A. Fundamentos de programacion en CUDA

CUDA es una arquitectura de calculo paralelo deNVIDIA creada para explotar la gran potencia de lasGPUs en aplicaciones de cualquier ındole. Los pro-gramas en CUDA se construyen mediante funcionesparalelas llamadas kernels [36]. Cada kernel es ejecu-tado paralelamente por un conjunto de hilos. Esto es,cada hilo ejecuta una instancia del kernel siguiendoel modelo de programacion Una Instruccion, Multi-ples Hilos (en ingles, SIMT). Un warp es el numerode hilos que puede ejecutar de forma concurrente unmultiprocesador. El programador decide el numerode hilos a emplear en cada kernel y los organiza enuna rejilla de bloques. Una rejilla es un conjunto debloques que son ejecutados paralelamente y que sonindependientes. Un bloque es un conjunto de hilosque trabajan conjuntamente y comparten recursoscomo un mismo espacio en la memoria compartida.

En la nueva arquitectura Pascal, la jerarquıa dememoria ha cambiado. En comparacion con arqui-tecturas anteriores, en Pascal ya no es necesario se-leccionar como queremos dividir la cantidad de me-moria disponible entre la memoria compartida y lacache L1. Cada multiprocesador de la GPU GP104contiene 96 KB de memoria compartida dedicada y48 KB de memoria cache L1. Por otro lado, en Pas-cal, la memoria cache L1 puede actuar como unacache de texturas dependiendo de la carga de tra-bajo. Esta memoria cache unificada actua como unbuffer para realizar accesos coalescentes a memoria.Ademas, la GP104 cuenta con 2048 KB de memoriacache L2.

Con el fin de obtener el mejor rendimiento y re-ducir el tiempo computacional hemos empleado di-ferentes estrategias para explotar eficientemente laarquitectura de la GPU. Primeramente, el algoritmoha sido desarrollado ıntegramente en CUDA, redu-ciendo ası las transferencias de datos entre la CPUy GPU al inicio y al final de la ejecucion. Ademas,ha sido desarrollado minimizando el uso de memo-

68 Jornadas SARTECO 2017

Imagen dereferencia

Imagenobjetivo

Mapas

Fig. 1: Esquema del algoritmo PCA-HFM para la alineacion de dos imagenes multidimensionales en GPU.

ria necesaria, y para que haga un uso eficiente de losdiferentes tipos de memoria segun el caso. Cuandono sea necesario mantener los datos anteriores a uncalculo, la salida se escribira en las mismas posicionesde memoria si es posible (computaciones in-place).

En nuestra implementacion, generalmente, lasimagenes y otros datos de gran tamano se encuentranalmacenados en la memoria global, y es en esta dondese realizan la mayorıa de los computos al no existirreutilizacion ni accesos no coalescentes. Ademas, enlas arquitecturas actuales estos accesos a memoriaglobal son menos costosos gracias a las ultimas me-joras de las memorias caches.

La latencia de la memoria compartida es aproxi-madamente 100 veces menor que la latencia de accesoa memoria global no cacheada previamente. Es poreso que esta es usada en aquellos kernels donde se ac-cede numerosas veces a los mismos datos en memoriaglobal.

Por otro lado, la memoria de texturas funciona co-mo una cache de solo lectura que incluye filtrado porhardware y que como parte del proceso de lecturapuede realizar interpolacion lineal en punto flotan-te. Si se compara con el tıpico esquema de cache enCPU, la memoria de texturas esta optimizada paraacelerar accesos que sigan patrones de localidad es-pacial 2D. Es por eso que es ideal en calculos de in-terpolacion como el que se utiliza en la computaciondel mapa log-polar.

Por otro lado, NVIDIA proporciona bibliotecas op-timizadas en GPU con funciones muy utilizadas. Porejemplo, calculo matricial, procesado primitivo deimagenes, calculo de la FFT, entre otros. Se ha hechouso de las mismas para obtener el mejor rendimiento.

Se ha utilizado el NVIDIA Visual Profiler paraanalizar cada kernel e identificar posibles limitado-res del rendimiento. Usando esta herramienta se habuscado la configuracion para cada kernel que per-mita computarlo en el menor tiempo posible y obte-ner ocupaciones optimas de hardware. En general, losbloques son de 256 hilos, exceptuando los kernels delcalculo de las componentes principales (PCA) dondeun tamano de bloque de 512 hilos consigue un me-jor rendimiento. Del mismo modo, los tamanos debloque escogidos son multiplos del tamano de warp,actualmente 32 en todas las arquitecturas, lo que ga-rantiza que los accesos a memoria de los warps estenalineados con las lıneas de la cache.

Por ultimo, se han utilizado funciones de mas bajonivel para obtener una mejor precision y rendimiento[37], especialmente cuando estas funciones son llama-das desde bucles.

B. Alineacion de imagenes multidimensionales enGPU

En esta seccion se describe la implementacion enGPU del algoritmo de alineacion PCA-HFM com-puesto de 4 etapas.

B.1 Preprocesado e inicializaciones

El algoritmo comienza precomputando datos au-xiliares que seran necesarios repetidamente en lacomputacion del filtro pasa-alta y de los mapas log-polar. En esta primera etapa, se aplica una venta-na de Blackman a cada banda espectral de ambasimagenes para eliminar aquellas altas frecuencias queafectan gravemente a la precision de la alineacion[38]. Esta operacion consiste en una multiplicacionpunto a punto, es por eso que se computa en memo-ria global.

A continuacion, se aplica el metodo PCA para ob-tener las componentes principales de las imagenesmultidimensionales. Esto nos permite reducir la di-mension de las imagenes y obtener un nuevo conjuntode datos con NPCA componentes no correlacionadaspara cada imagen, y donde las primeras componen-tes retienen la mayor parte de la variacion presenteen los datos originales. Este computo se ha realizadomediante el metodo de descomposicion en autovalo-res (EVD) [39]. Para ello debemos primero centrarla imagen restando a cada pıxel el valor medio de subanda correspondiente usando para ello la funcioncublasSgemv de cuBLAS [40]. La matriz de cova-rianza es calculada usando la funcion cublasSgemm.Usando la funcion cusolverDnSgesvd de cuSOLVER[41] obtendremos los valores y vectores singulares dedicha matriz de covarianza. El ultimo paso para laobtencion de las PCs se realiza mediante la funcioncublasSgemm de cuBLAS, la cual realiza el produc-to entre la imagen y la conjugada transpuesta de lamatriz unitaria obtenida en la descomposicion.

Por ultimo, las imagenes son extendidas a un ta-mano potencia de 2 para obtener un computo de laFFT mas eficiente mediante cuFFT [42]. Al mismotiempo esto nos permite evitar divergencias pues notendremos que configurar mas hilos de los necesariosal ser el tamano de las imagenes multiplo del tamanode warp. Las imagenes son centradas en el nuevo ta-mano y se unifica el color de cada banda usando lamemoria compartida.

B.2 Mapas log-polar y correlacion de fase

La siguiente etapa, mapas log-polar y correlacionde fase, comienza con la transformacion de cada com-ponente principal de las dos imagenes al dominio dela frecuencia, mediante el uso de la FFT. Se ha usado

Jornadas SARTECO 2017 69

la librerıa cuFFT [43] para obtener el mejor rendi-miento en el computo de las transformadas.

A continuacion se aplica un filtro pasa-alta a ca-da componente. Este ya ha sido precomputado enla funcion de inicializaciones para ahorrar tiempo decomputo. Este simple filtro reduce los efectos de alia-sing, muy frecuentes en las las frecuencias mas debi-les de la transformada de Fourier, y que afectan a laprecision de la alineacion de imagenes usando meto-dos basados en la correlacion de fase [12].

Aplicado el filtro pasa-alta, el siguiente paso es cal-cular los mapas log-polar para poder recuperar losparametros de escala ρ0 y de rotacion θ0. La transfor-macion a coordenadas log-polar se realiza medianteinterpolacion sobre las componentes filtradas. Paraello es necesario realizar un gran numero de accesosa memoria y realizar interpolaciones, por lo que lamemoria de texturas es la mejor opcion en terminosde rendimiento como ya se ha dicho en la SeccionII-A.

Por ultimo, la correlacion de fase es computada encada par de mapas log-polar, uno de cada imagen.Este metodo de alineacion se basa en el teorema dedesplazamiento de la transformada de Fourier, por lacual un desplazamiento circular en el dominio espa-cial es equivalente a un desplazamiento de fase en eldominio de la frecuencia.

Supongamos que I1(x, y) y I2(x, y) son dos image-nes, donde (x, y) son sus coordenadas espaciales, yque I2(x, y) es una replica generada tras trasladarI1(x, y) (x0, y0) coordenadas,

I2(x, y) = I1(x+ x0, y + y0), (1)

por el teorema de desplazamiento sus transformadasde Fourier estan relacionadas

F2(u, v) = ei2π(ux0+vy0)F1(u, v), (2)

donde (u, v) son las coordenadas en el dominio de lafrecuencia e i es la unidad imaginaria.

Aplicando la correlacion de fase en el dominio dela frecuencia,

F1(u, v)F ∗2 (u, v)

|F1(u, v)F ∗2 (u, v)| = e−i2π(ux0+vy0), (3)

y, computando la transformada inversa de Fourier,obtenemos una matriz formada casi en su totalidadpor ceros excepto en el pico con coordenadas (x0, y0),el cual nos permite alinear las imagenes.

Para recuperar el factor de escalado y el angulode rotacion, en [10] se propone el uso de la transfor-mada log-polar de Fourier, tambien conocida comotransformada Fourier-Mellin. Supongamos que I2 esuna imagen replica de I1 pero escalada con un factorρ0 y rotada con un angulo θ0, esto es,

I2(x, y) = I1(ρ0(x cos θ0 + y sin θ0 + x0),

ρ0(−x sin θ0 + y cos θ0 + y0)),(4)

aplicando el teorema de desplazamiento de Fouriersobre las coordenadas polares (ρ, θ) obtenemos,

F2(ρ, θ) = ei(ωxx0+ωyy0)ρ−20 F1(ρ−10 ρ, θ + θ0), (5)

donde ωx = ρ cos θ y ωy = ρ sin θ.

Por otra parte, aplicando el modulo de la transfor-mada de Fourier y el logaritmo de radio ρ, tenemos

|F2(ln ρ, θ)| = ρ−20 |F1(ln ρ− ln ρ0, θ + θ0)|, (6)

donde ρ0 y θ0 pueden ser obtenidos aplicando nue-vamente el teorema de desplazamiento de Fourier yla correlacion de fase. En este caso, volveremos ob-tener una matriz con practicamente ceros en todassus posiciones con excepcion el pico con coordena-das (ln ρ0, θ0). El computo de las transformadas deFourier necesarias se realiza nuevamente usando labiblioteca cuFFT.

B.3 Composicion de mapas

Los mapas log-polar tras la correlacion son combi-nados en la etapa de composicion. Los diferentes ex-perimentos que hemos realizado han demostrado quepromediando estos mapas nos permite obtener mejo-res resultados, pues cada par de componentes PCAcontribuye independientemente en la correlacion defase atenuando aquellos falsos picos que nos llevarıana obtener unos parametros de alineacion incorrectos.

B.4 Procesado de picos

Una vez que los mapas de correlacion son combi-nados, obtenemos una matriz con ceros en casi todassus posiciones exceptuando algunas de estas. Si lasdos imagenes a alinear fueran iguales tan solo ob-tendrıamos un pico, es decir, un valor distinto de 0,cuyas coordenadas nos permiten alinear las image-nes. Pero debido a distorsiones y otros efectos se ob-tienen numerosos picos, y es por eso que debemosanalizar mas de uno en busca del que nos permitaalinear las imagenes.

Esta etapa esta formada por dos pasos: el procesa-do de los picos de los mapas de correlacion despuesde la log-polar para obtener el factor de escala y elangulo de rotacion, y el procesado de los picos enel dominio cartesiano tras corregir la rotacion y elescalado para obtener la traslacion.

En el primer paso de esta etapa, empezamos ana-lizando los NPeaks mayores picos de los mapas de co-rrelacion de la log-polar. Para eso primero se ordenanlos picos por magnitud usando la funcion sort by keyde la biblioteca Thrust. Esta biblioteca selecciona au-tomaticamente la implementacion mas eficiente paradicha ordenacion [44].

A partir de las coordenadas de cada uno de es-tos NPeaks picos obtenemos un factor de escala ρ0y un angulo de rotacion θ0. Con cada uno de es-tos pares de parametros se escala y se rota (θ0 yθ0 + π debido a la ambiguedad del mapa log-polar)la primera componente de la imagen objetivo utili-zando las funciones nppiRotate 32f C1R y nppiRe-sizeSqrPixel 32f C1R de la biblioteca NPP [45]. Deesta manera si el pico fuera el acertado se estarıancorrigiendo el escalado y rotacion de la imagen, tansolo faltarıa la traslacion.

70 Jornadas SARTECO 2017

(a) (b) (c) (d)

Fig. 2: Imagenes hiperespectrales de prueba comunes en el area de teledeteccion: (a) Pavia University, (b)Pavia Centre, (c) Indian Pines, y (d) Salinas.

El segundo paso de etapa etapa consiste en calcu-lar la correlacion de fase entre la primera componentede la imagen de referencia y las dos componentes ro-tadas y escaladas de la imagen de referencia. A con-tinuacion, seleccionamos el pico maximo de las doscorrelaciones que obtenemos por cada NPeak usandola funcion cublasIcamax de cuBLAS.

El pico maximo de los 2NPeaks mapas cartesianoses el que nos permite seleccionar cual de los NPeaks

picos es el pico log-polar que posiblemente alinee deforma correcta la imagen. Finalmente, las coordena-das del pico seleccionado en el mapa log-polar sonlos que determinan el factor de escala ρ0 y el angulode rotacion θ0, y las coordenadas del pico en el do-minio cartesiano es el que determina los parametrosde traslacion (x0, y0).

III. Resultados

En esta seccion se muestran las imagenes de prue-ba y condiciones experimentales ası como se presen-tan los resultados en terminos de precision de alinea-do y de tiempos de computo.

A. Condiciones experimentales

La version CPU del algoritmo ha sido ejecutadosobre un ordenador con un procesador quad-core In-tel Core i5-6600 a 3.3 GHz y 32 GB de RAM. Conrespecto a la implementacion en GPU, este se ha eje-cutado en una NVIDIA GeForce GTX 1070 con 15SMs con 128 nucleos CUDA cada uno. Los codigoshan sido compilados en un sistema operativo Linux,en concreto, usando gcc version 4.8.4 para la imple-mentacion en CPU, y nvcc y bibliotecas de NVIDIAversion 8.0.26 para la implementacion en GPU. To-das los computos se han realizado en punto flotantecon precision simple.

Se han usado seis imagenes para realizar los ex-perimentos de este trabajo. Estas han sido toma-das de los sensores ROSIS (Reflective Optics Sys-tem Imaging Spectrometer) y AVIRIS (Airborne Vi-sible/Infrared Imaging Spectrometer). El sensor RO-SIS captura 115 bandas en el rango espectral 0.43hasta 0.86 µm, correspondiendo principalmente al es-

pectro visible. El sensor AVIRIS captura 224 bandasen el rango espectral 0.4 hasta 2.5 µm, correspondien-te al espectro visible e infrarrojo.

Las cuatro primeras imagenes son comunmente co-nocidas en el area de la teledeteccion hiperespectral(ver Fig. 2). La primera imagen utilizada es la imagende la Universidad de Pavia (Italia). Es una imagentomada con el sensor ROSIS con 103 bandas ya quese han eliminado 12 bandas con ruido. El tamano dela imagen es 610 × 340 pıxeles con una resolucionespacial de 1.3 m por pıxel.

La segunda imagen tambien ha sido capturadapor ROSIS y se trata de la imagen del centro dePavia (Italia). Originalmente tenıa un tamano de1096 × 1096 pıxeles, pero una zona central con 381pıxeles de ancho fue eliminada al no contener da-tos, resultando la imagen final con un tamano de1096×715 pıxeles. Tambien fuero eliminadas 13 ban-das por contener ruido, quedando finalmente 102bandas con una resolucion espacial de 1.3 m porpıxel.

La tercera imagen, Indian Pines Test Site 3, es unaimagen de una zona agrıcola de Tippecanoe County(Indiana) y fue tomada por el sensor AVIRIS. Constade 220 bandas (cuatro fueron eliminadas) con reso-lucion espacial de 20 m por pıxel y tiene un tamanode 145× 145 pıxeles.

La cuarta imagen fue capturada por el sensor AVI-RIS sobre el Valle de Salinas (California). Es unaimagen de una zona rural con un tamano de 512×217pıxeles y 204 bandas, tras eliminar las correspondien-tes a la absorcion del agua y algunas bandas de ruido.Su resolucion espacial es de 3.7 m por pixel.

Las ultimas dos imagenes han sido capturadas porel sensor AVIRIS en la Bahıa de San Francisco (Ca-lifornia). Estan formadas en su mayorıa por zonas decultivo pero tambien por zonas edificadas. La prime-ra imagen fue tomada el 7/6/2013 y tiene un tamanooriginal de 11342×744 pıxeles con una resolucion es-pacial de 16.9 m por pıxel. La segunda imagen fuetomada el 11/06/2015 y tiene un tamano original de11247× 828 con una resolucion espacial de 17 m porpıxel. En la figura 3 se muestra el fragmento de ta-

Jornadas SARTECO 2017 71

TABLA I: Casos correctamente alineados para cada escena. El numero entre parentesis indica el numero deescalas que fueron recuperadas correctamente para todos los angulos.

Imagen PCA-HFM (8 PCs) PCA-HFM (1 PC) SIFT SURF

Pavia University 1/4× to 4.5× (11) 1/4× to 3.5× (9) 1/2× to 2.0× (4) 1/4× to 3.0× (8)Pavia Centre 1/4× to 6.0× (14) 1/4× to 5.5× (13) 1/5× to 2.5× (8) 1/6× to 5.5× (15)Indian Pines 1/2× to 3.5× (7) 1/2× to 3.0× (6) 1/2× to 1.0× (2) 1.0× (1)

Salinas 1/2× to 4.0× (8) 1/2× to 4.0× (8) (0) 1/2× to 1.5× (3)Bay Area Box Line 1/2× to 2.0× (3) 1.0× (1) 1/2× to 1.0× (2) 1.0× (1)

Promedio de escalas correctas (8.60) (7.40) (3.20) (5.60)

mano 1432 × 688 que ha sido seleccionado. Ambastienen 224 bandas espectrales y presentan, ademasdel problema de alineacion, cambios en la vegetacion,edificios, e infraestructuras.

Todas estas imagenes pueden ser descargadas dehttp://gitlab.citius.usc.es/hiperespectral/

RegistrationRepository.

(a) (b)

Fig. 3: Imagenes de prueba Bay Area Box Line 12capturadas por el sensor AVIRIS. (a) Fragmento detamano 1432×688 de la imagen tomada el 7/6/2013,y (b) Fragmento de tamano 1432× 688 de la imagentomada el 11/06/2015.

B. Resultados de precision de alineado

Para las cuatro primeras imagenes, las pruebas dealineado se han realizado sobre una version de la mis-ma rotada y escalada. De esta manera, podemos ana-lizar todos los detalles en un entorno controlado. Enel caso de las imagenes de la Bahıa de San Franciscose ha seleccionado la imagen de 2015 como imagenobjetivo y la imagen de 2013 como imagen de refe-rencia. Con el fin de extender nuestro rango de ex-perimentacion se han aplicado diferentes factores deescala y angulos de rotacion a la imagen que preten-demos alinear en ambos casos.

El procedimiento de la experimentacion ha sido elsiguiente. Se ha realizado una busqueda exhaustivacon factores de escala desde 1/6× hasta 7× en incre-mentos de 0.5× y con angulos de rotacion desde 0o

hasta 360o en incrementos de 5o (72 angulos). Paralos factores de escala mayores a 1× se ha manteni-

do el tamano original de la imagen seleccionando laparte central de la imagen escalada.

En la Tabla I se muestran las escalas correctamen-te recuperadas para todos sus 72 angulos para cadauna de las imagenes usando dos configuraciones di-ferentes del algoritmo propuesto PCA-HFM y dosmetodos relevantes de la literatura. La primera y se-gunda columnas muestran los resultados para nues-tra propuesta usando 8 y 1 componentes. La terceray cuarta columna muestran los resultados obtenidospara dos metodos basados en la extraccion de carac-terısticas, pues como se ha comentado en la Seccion1 son robustos a cambios de iluminacion, rotacion yescalado. Estos son los metodos SIFT [46] y SURF[17]. Para ambos algoritmos se ha realizado el empa-rejamiento de los puntos por fuerza bruta usando ladistancia euclıdea y se ha calculado la transformacionafın usando el metodo Random Sample Consensus(RANSAC). Debido a la arbitrariedad de RANSAC,se han realizado 50 ejecuciones para cada prueba dealineamiento. Ambos algoritmos son utilizados em-pleando la primera componente.

El metodo propuesto PCA-HFM con 8 PCs es elque obtiene de media los mejores resultados, alinean-do correctamente 8.60 escalas frente a 7.40 usandosolo 1 PC. Realizando la composicion de los mapas decorrelacion de las 8 primeras componentes se descar-tan picos que nos llevarıan a alineaciones incorrectas,que es lo que sucede utilizando solo la primera com-ponente. Los algoritmos SURF y SIFT son los queobtienen peores resultados, 5.60 y 3.20 escalas co-rrectas, respectivamente. La capacidad limitada deestos metodos resida probablemente en la identifica-cion de los puntos caracterısticos cuando las image-nes presentan cambios. Para las imagenes con mejorresolucion espacial, Pavia Centre y Pavia University,es para las que se consigue alinear un mayor numerode escalas, 14 y 11, respectivamente.

B.1 Resultados de tiempos de computacion

En esta seccion comparan los tiempos de compu-tacion de la implementacion secuencial en CPU y laversion paralelizada en GPU del metodo propuesto,PCA-HFM con 8 PCs. Estos resultados se han ob-tenido realizando un promedio de 10 ejecuciones porexperimento. Todas las tablas muestran los tiemposen segundos y no incluyen los tiempos de lectura dedatos y de transferencias CPU-GPU, salvo que seindique lo contrario.

En la Tabla II se muestran los tiempos de utiliza-

72 Jornadas SARTECO 2017

TABLA II: Tiempos de ejecucion (en segundos) enCPU y en GPU detallados en funciones para la ali-neacion de las imagenes de la Bahıa de San Francisco.

Funcion CPU GPU Aceleracion

Blackman 0.122s 0.064s 1.9×PCA 2.058s 0.249s 8.2×Extension 0.126s 0.005s 25.4×FFT 9.881s 0.033s 297.2×High-pass 2.194s 0.015s 146.1×Log-polar 2.206s 0.015s 150.6×Correlacion de fase 131.076s 0.443s 296.0×Composicion 0.008s 0.001s 6.3×Ordenar picos 0.093s 0.004s 21.3×Escalar y rotar 35.985s 0.160s 225.3×Evaluacion de picos 0.239s 0.018s 13.2×

cion en CPU y GPU para el alineado de las image-nes de la Bahıa de San Francisco para cada funcionde la implementacion. La mayorıa del tiempo se haempleado en la computacion de la correlacion de fa-se, la FFT, y en el escalado y rotado de la primeracomponente. La correlacion de fase esta compuestapor varias transformadas FFT, y es utilizada repe-tidamente a lo largo del algoritmo. Esta, junto conla propia FFT, han sido las dos funciones que me-jor aceleracion han obtenido en su implementacionen GPU gracias al buen rendimiento de la bibliotecacuFFT. La operacion de escalado y rotacion tambienes muy costosa computacionalmente ya que conlle-va calculos aritmeticos e interpolaciones. El uso dela memoria de texturas ha permitido obtener unamuy buena aceleracion en el calculo de los mapaslog-polar.

TABLA III: Tiempos de ejecucion (en segundos) pa-ra las implementaciones en CPU y en GPU para cadaimagen.

Imagen CPU GPU CUDA Aceleracion

Pavia University 40.80s 0.28s 145.7×Pavia Centre 178.06s 0.85s 209.5×Indian Pines 2.32s 0.15s 15.5×Salinas 9.61s 0.20s 48.1×Bay Area 183.99s 1.01s 182.2×

La Tabla III muestra los tiempos de ejecucion delalgoritmo en CPU y en GPU para todas las image-nes. Las aceleraciones mas grandes se consiguen enlas imagenes de mayor tamano, 209.5× y 182.2× pa-ra las imagenes Pavia Centre y Bay Area, respecti-vamente.

TABLA IV: Tiempos de ejecucion (en segundos) pa-ra las implementaciones en CPU y en GPU para cadaimagen incluyendo los tiempos de lectura de image-nes y las transferencias CPU-GPU.

Imagen CPU GPU CUDA Aceleracion

Pavia University 40.94s 0.35s 118.7×Pavia Centre 178.65s 1.08s 165.4×Indian Pines 2.34s 0.17s 14.0×Salinas 9.78s 0.27s 36.2×Bay Area 185.81s 1.65s 113.0×

Los tiempos de ejecucion incluyendo los tiempos de

lectura de las imagenes y de transferencia de datosCPU-GPU son presentados en la Tabla IV. De igualforma, las mejores aceleraciones se consiguen en lasimagenes de mayor tamano.

IV. Conclusiones

En este artıculo se presenta un algoritmo de alinea-cion de imagenes multidimensionales en GPU, PCA-HFM. Esta basado en la transformada rapida de Fou-rier, el calculo de componentes principales median-te PCA, la correlacion de fase, y la combinacion demapas log-polar. Se han implementado una versionsecuencial en CPU y una version paralela en CUDApara su completa ejecucion en una GPU NVIDIA.

Se han realizado experimentos con 6 imagenes mul-tidimensionales con diferentes tamanos y de distin-tos sensores, consiguiendo resultados satisfactoriosen terminos de precision de alineado y en tiempo decomputo. Se ha llegado a alinear correctamente es-calas de hasta 6.0× para todos los angulos. Las fun-ciones mas costosas y mejor optimizadas son aque-llas que contienen calculos de FFTs, la correlacionde fase y la propia transformacion al dominio de lafrecuencia. Se han conseguido para la imagen PaviaCentre, con tamano 1096×715 pıxeles y 102 bandas,un tiempo de alineacion de 1.08s en GPU y una ace-leracion de 165.4× respecto de la version secuencialen CPU.

Agradecimientos

El presente trabajo ha sido financiando por la Con-sellerıa de Cultura, Educacion e Ordenacion Univer-sitaria [GRC2014/008 y ED431G/08] y el Ministeriode Educacion, Cultura y Deporte [TIN2013-41129-P y TIN2016-76373-P], ambos cofinanciados por elFondo Europeo de Desarrollo Regional (FEDER).

Referencias

[1] David Landgrebe, “Hyperspectral image data analysis,”IEEE Signal Processing Magazine, vol. 19, no. 1, pp. 17–28, 2002.

[2] Driss Haboudane, John R Miller, Elizabeth Pattey, Pa-blo J Zarco-Tejada, and Ian B Strachan, “Hyperspec-tral vegetation indices and novel algorithms for predic-ting green lai of crop canopies: Modeling and validationin the context of precision agriculture,” Remote sensingof environment, vol. 90, no. 3, pp. 337–352, 2004.

[3] Laura M Dale, Andre Thewis, Christelle Boudry, IoanRotar, Pierre Dardenne, Vincent Baeten, and JuanA Fernandez Pierna, “Hyperspectral imaging applica-tions in agriculture and agro-food product quality andsafety control: a review,” Applied Spectroscopy Reviews,vol. 48, no. 2, pp. 142–159, 2013.

[4] Donald B Malkoff and William R Oliver, “Hyperspec-tral imaging applied to forensic medicine,” in BiOS 2000The International Symposium on Biomedical Optics. In-ternational Society for Optics and Photonics, 2000, pp.108–116.

[5] P WT Yuen and Mark Richardson, “An introductionto hyperspectral imaging and its application for security,surveillance and target acquisition,” The Imaging Scien-ce Journal, vol. 58, no. 5, pp. 241–253, 2010.

[6] Azadeh Ghiyamat and Helmi ZM Shafri, “A review onhyperspectral remote sensing for homogeneous and hete-rogeneous forest biodiversity assessment,” InternationalJournal of Remote Sensing, vol. 31, no. 7, pp. 1837–1856,2010.

[7] Suma Dawn, Vikas Saxena, and Bhudev Sharma, “Re-mote sensing image registration techniques: A survey,”

Jornadas SARTECO 2017 73

in International Conference on Image and Signal Pro-cessing. Springer, 2010, pp. 103–112.

[8] Manjusha Deshmukh and Udhav Bhosle, “A survey ofimage registration,” International Journal of Image Pro-cessing (IJIP), vol. 5, no. 3, pp. 245, 2011.

[9] Lisa Gottesfeld Brown, “A survey of image registrationtechniques,” ACM computing surveys (CSUR), vol. 24,no. 4, pp. 325–376, 1992.

[10] Qin-sheng Chen, Michel Defrise, and Frank Deconinck,“Symmetric phase-only matched filtering of Fourier-Mellin transforms for image registration and recogni-tion,” IEEE Transactions on pattern analysis and ma-chine intelligence, vol. 16, no. 12, pp. 1156–1168, 1994.

[11] B Dasgupta and BN Chatterji, “Fourier-Mellin trans-form based image matching algorithm,” IETE Journalof Research, vol. 42, no. 1, pp. 3–9, 1996.

[12] B Srinivasa Reddy and Biswanath N Chatterji, “Anfft-based technique for translation, rotation, and scale-invariant image registration,” IEEE transactions on ima-ge processing, vol. 5, no. 8, pp. 1266–1271, 1996.

[13] David G Lowe, “Distinctive image features from scale-invariant keypoints,” International journal of computervision, vol. 60, no. 2, pp. 91–110, 2004.

[14] Peter Schwind, Sahil Suri, Peter Reinartz, and AndreasSiebert, “Applicability of the sift operator to geometricsar image registration,” International Journal of RemoteSensing, vol. 31, no. 8, pp. 1959–1980, 2010.

[15] Yan Ke and Rahul Sukthankar, “Pca-sift: A more dis-tinctive representation for local image descriptors,” inComputer Vision and Pattern Recognition, 2004. CVPR2004. Proceedings of the 2004 IEEE Computer SocietyConference on. IEEE, 2004, vol. 2, pp. II–II.

[16] Qiaoliang Li, Guoyou Wang, Jianguo Liu, and ShaoboChen, “Robust scale-invariant feature matching for re-mote sensing image registration,” IEEE Geoscience andRemote Sensing Letters, vol. 6, no. 2, pp. 287–291, 2009.

[17] Herbert Bay, Tinne Tuytelaars, and Luc Van Gool, “Surf:Speeded up robust features,” Computer vision–ECCV2006, pp. 404–417, 2006.

[18] Jeffrey P Kern, Marios Pattichis, and Samuel D Stearns,“Registration of image cubes using multivariate mutualinformation,” in Signals, Systems and Computers, 2004.Conference Record of the Thirty-Seventh Asilomar Con-ference on. IEEE, 2003, vol. 2, pp. 1645–1649.

[19] Jacqueline Le Moigne, Arlene Cole-Rhodes, Roger East-man, Tarek El-Ghazawi, Kisha Johnson, S Knewpijit, Na-dine Laporte, Jeffrey Morisette, Nathan S Netanyahu,Harold S Stone, et al., “Multiple sensor image regis-tration, image fusion and dimension reduction of earthscience imagery,” in Information Fusion, 2002. Procee-dings of the Fifth International Conference on. IEEE,2002, vol. 2, pp. 999–1006.

[20] Hector Erives and Glenn J Fitzgerald, “Automated regis-tration of hyperspectral images for precision agriculture,”Computers and Electronics in Agriculture, vol. 47, no. 2,pp. 103–119, 2005.

[21] Jun Wang, Zhiyong Xu, and Jianlin Zhang, “Image regis-tration with hyperspectral data based on Fourier-Mellintransform,” International Journal of Signal ProcessingSystems, vol. 1, no. 1, 2013.

[22] Maria Vakalopoulou and Konstantinos Karantzalos, “Au-tomatic descriptor-based co-registration of frame hypers-pectral data,” Remote Sensing, vol. 6, no. 4, pp. 3409–3426, 2014.

[23] Gustavo K Rohde, Sinisa Pajevic, Carlo Pierpaoli, andPeter J Basser, “A comprehensive approach for multi-channel image registration,” in International Workshopon Biomedical Image Registration. Springer, 2003, pp.214–223.

[24] Brian B Avants, Charles L Epstein, Murray Grossman,and James C Gee, “Symmetric diffeomorphic image re-gistration with cross-correlation: evaluating automatedlabeling of elderly and neurodegenerative brain,” Medi-cal image analysis, vol. 12, no. 1, pp. 26–41, 2008.

[25] Juan Ruiz-Alzola, C-F Westin, Simon K Warfield, C Al-berola, S Maier, and Ron Kikinis, “Nonrigid registrationof 3d tensor medical data,” Medical image analysis, vol.6, no. 2, pp. 143–161, 2002.

[26] Hani Mahdi and Aly A Farag, “Image registration inmultispectral data sets,” in Image Processing. 2002. Pro-ceedings. 2002 International Conference on. IEEE, 2002,vol. 2, pp. II–II.

[27] Siyue Chen, Qing Guo, Henry Leung, and Eloi Bosse, “A

maximum likelihood approach to joint image registrationand fusion,” IEEE Transactions on Image Processing,vol. 20, no. 5, pp. 1363–1372, 2011.

[28] Peter Bunting, Frederic Labrosse, and Richard Lucas,“A multi-resolution area-based technique for automa-tic multi-modal image registration,” Image and VisionComputing, vol. 28, no. 8, pp. 1203–1219, 2010.

[29] Zebin Wu, Jiafu Liu, Antonio Plaza, Jun Li, and ZhihuiWei, “GPU implementation of composite kernels for hy-perspectral image classification,” IEEE Geoscience andRemote Sensing Letters, vol. 12, no. 9, pp. 1973–1977,2015.

[30] Luis Ignacio Jimenez, Gabriel Martın, Sergio Sanchez,Carlos Garcıa, Sergio Bernabe, Javier Plaza, and AntonioPlaza, “GPU implementation of spatial–spectral prepro-cessing for hyperspectral unmixing,” IEEE Geoscienceand Remote Sensing Letters, vol. 13, no. 11, pp. 1671–1675, 2016.

[31] Javier Lopez-Fandino, Blanca Priego, Dora B Heras, andFrancisco Arguello, “GPU projection of ecas-ii segmen-ter for hyperspectral images based on cellular automata,”IEEE Journal of Selected Topics in Applied Earth Ob-servations and Remote Sensing, vol. 10, no. 1, pp. 20–28,2017.

[32] Alexander Kohn, Johann Drexl, Felix Ritter, MatthiasKonig, and Heinz-Otto Peitgen, “GPU accelerated ima-ge registration in two and three dimensions,” in Bildve-rarbeitung fur die Medizin 2006, pp. 261–265. Springer,2006.

[33] Pinar Muyan-Ozcelik, John D Owens, Junyi Xia, andSanjiv S Samant, “Fast deformable registration on theGPU: A CUDA implementation of demons,” in Compu-tational Sciences and Its Applications, 2008. ICCSA’08.International Conference on. IEEE, 2008, pp. 223–233.

[34] Alexander Kubias, Frank Deinzer, Tobias Feldmann,DIETRICH Paulus, BERND Schreiber, and Th Brunner,“2d/3d image registration on the GPU,” Pattern Recog-nition and Image Analysis, vol. 18, no. 3, pp. 381–389,2008.

[35] Ramtin Shams, Parastoo Sadeghi, Rodney Kennedy, andRichard Hartley, “Parallel computation of mutual infor-mation on the GPU with application to real-time regis-tration of 3d medical images,” Computer methods andprograms in biomedicine, vol. 99, no. 2, pp. 133–146,2010.

[36] Jason Sanders and Edward Kandrot, CUDA by Example:An Introduction to General-Purpose GPU Programming,Portable Documents, Addison-Wesley Professional, 2010.

[37] NVIDIA, “CUDA C Best Practices Guide,” Avai-lable: http://docs.nvidia.com/cuda/pdf/CUDA_C_Best_Practices_Guide.pdf, 2017, Accessed: 2017-04-05.

[38] Fredric J Harris, “On the use of windows for harmonicanalysis with the discrete Fourier transform,” Procee-dings of the IEEE, vol. 66, no. 1, pp. 51–83, 1978.

[39] Alberto S Garea, Dora B Heras, and Francisco Arguello,“GPU classification of remote-sensing images using ker-nel elm and extended morphological profiles,” Interna-tional Journal of Remote Sensing, vol. 37, no. 24, pp.5918–5935, 2016.

[40] NVIDIA, “cuBLAS Library User’s Guide,” Available:http://docs.nvidia.com/cuda/pdf/CUBLAS_Library.pdf, 2017, Accessed: 2017-04-05.

[41] NVIDIA, “cuSOLVER Library User’s Guide,” Available:http://docs.nvidia.com/cuda/pdf/CUSOLVER_Library.pdf, 2017, Accessed: 2017-04-05.

[42] NVIDIA, “cuFFT Library User’s Guide,” Available:http://docs.nvidia.com/cuda/pdf/CUFFT_Library.pdf, 2017, Accessed: 2017-05-02.

[43] NVIDIA, “cuFFT Library User’s Guide,” Available:http://docs.nvidia.com/cuda/pdf/CUFFT_Library.pdf, 2017, Accessed: 2017-04-05.

[44] NVIDIA, “Thrust Quick Start Guide,” Availa-ble: http://docs.nvidia.com/cuda/pdf/Thrust_Quick_Start_Guide.pdf, 2017, Accessed: 2017-04-05.

[45] NVIDIA, “NVIDIA Performance Primitives (NPP)v8.0 User’s Guide,” Available: http://docs.nvidia.com/cuda/pdf/NPP_Library_Image_Geometry.pdf, 2017, Ac-cessed: 2017-04-05.

[46] Ives Rey Otero, Anatomy of the SIFT Method, Ph.D.

thesis, Ecole normale superieure de Cachan-ENS Cachan,2015.

74 Jornadas SARTECO 2017